Instruction cache associative crossbar switch

Details Instruction cache associative crossbar switch Instruction cache associative crossbar switch

2000-09-08

2002-03-19

Vu, Viet D. (Department: 2154)

Electrical computers and digital processing systems: processing

Instruction issuing

Simultaneous issuance of multiple instructions

C712S024000, C712S207000, C712S213000, C712S234000

Reexamination Certificate

active

06360313

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to the architecture of computing systems, and in particular to an architecture in which individual instructions may be executed in parallel, as well as to methods and apparatus for accomplishing that.
A common goal in the design of computer architectures is to increase the speed of execution of a given set of instructions. One approach to increasing instruction execution rates is to issue more than one instruction per clock cycle, in other words, to issue instructions in parallel. This allows the instruction execution rate to exceed the clock rate. Computing systems that issue multiple independent instructions during each clock cycle must solve the problem of routing the individual instructions that are dispatched in parallel to their respective execution units. One mechanism used to achieve this parallel routing of instructions is generally called a “crossbar switch.”
In present state of the art computers, e.g. the Digital Equipment Alpha, the Sun Microsystems SuperSparc, and the Intel Pentium, the crossbar switch is implemented as part of the instruction pipeline. In these machines the crossbar is placed between the instruction decode and instruction execute stages. This is because the conventional approach requires the instructions to be decoded before it is possible to determine the pipeline to which they should be dispatched. Unfortunately, decoding in this manner slows system speed and requires extra surface area on the integrated circuit upon which the processor is formed. These disadvantages are explained further below.
SUMMARY OF THE INVENTION
We have developed a computing system architecture that enables instructions to be routed to an appropriate pipeline more quickly, at lower power, and with simpler circuitry than previously possible. This invention places the crossbar switch earlier in the pipeline, making it a part of the initial instruction fetch operation. This allows the crossbar to be a part of the cache itself, rather than a stage in the instruction pipeline. It also allows the crossbar to take advantage of circuit design parameters that are typical of regular memory structures rather than random logic. Such advantages include: lower switching voltages (200-300 milliamps rather than 3-5 volts); more compact design, and higher switching speeds. In addition, if the crossbar is placed in the cache, the need for many sense amplifiers is eliminated, reducing the circuitry required in the system as a whole.
To implement the crossbar switch, the instructions coming from the cache, or otherwise arriving at the switch, must be tagged or otherwise associated with a pipeline identifier to direct the instructions to the appropriate pipeline for execution. In other words, pipeline dispatch information must be available at the crossbar switch at instruction fetch time, before conventional instruction decode has occurred. There are several ways this capability can be satisfied: In one embodiment this system includes a mechanism that routes each instruction in a set of instructions to be executed in parallel to an appropriate pipeline, as determined by a pipeline tag applied to each instruction during compilation, or placed in a separate identifying instruction that accompanies the original instruction. Alternately the pipeline affiliation can be determined after compilation at the time that instructions are fetched from memory into the cache, using a special predecoder unit.
Thus, in one implementation, this system includes a register or other means, for example, the memory cells providing for storage of a line in the cache, for holding instructions to be executed in parallel. Each instruction has associated with it a pipeline identifier indicative of the pipeline to which that instruction is to be issued. A crossbar switch is provided which has a first set of connectors coupled to receive the instructions, and a second set of connectors coupled to the processing pipelines to which the instructions are to be dispatched for execution. Means are provided which are responsive to the pipeline identifiers of the individual instructions in the group supplied to the first set of connectors for routing those individual instructions onto appropriate paths of the second set of connectors, thereby supplying each instruction in the group to be executed in parallel to the appropriate pipeline.
In a preferred embodiment of this invention the associative crossbar is implemented in the instruction cache. By placing the crossbar in the cache all switching is done at low signal levels (approximately 200-300 millivolts). Switching at these low levels is substantially faster than switching at higher levels (5 volts) after the sense amplifiers. The lower power also eliminates the need for large driver circuits, and eliminates numerous sense amplifiers. Additionally by implementing the crossbar in the cache, the layout pitch of the crossbar lines matches the pitch of the layout of the cache.


REFERENCES:
patent: 4437149 (1984-03-01), Pomerene et al.
patent: 4833599 (1989-05-01), Colwell et al.
patent: 4847755 (1989-07-01), Morrison et al.
patent: 4933837 (1990-06-01), Freidin
patent: 5055997 (1991-10-01), Sluijter et al.
patent: 5057837 (1991-10-01), Colwell et al.
patent: 5081575 (1992-01-01), Hiller et al.
patent: 5101341 (1992-03-01), Circello et al.
patent: 5121502 (1992-06-01), Rau et al.
patent: 5129067 (1992-07-01), Johnson
patent: 5151981 (1992-09-01), Westcott et al.
patent: 5179680 (1993-01-01), Colwell et al.
patent: 5197137 (1993-03-01), Kumar et al.
patent: 5203002 (1993-04-01), Wetzel
patent: 5214763 (1993-05-01), Blaner et al.
patent: 5226169 (1993-07-01), Gregor
patent: 5233696 (1993-08-01), Suzuki
patent: 5239654 (1993-08-01), Ing-Simmons et al.
patent: 5297255 (1994-03-01), Hamanaka et al.
patent: 5297281 (1994-03-01), Emma et al.
patent: 5299321 (1994-03-01), Iizuka
patent: 5333280 (1994-07-01), Ishikawa et al.
patent: 5337415 (1994-08-01), DeLano et al.
patent: 5355460 (1994-10-01), Eickemeyer et al.
patent: 5367694 (1994-11-01), Ueno
patent: 5442760 (1995-08-01), Rustad et al.
patent: 5459844 (1995-10-01), Eickemeyer et al.
patent: 5500942 (1996-03-01), Eickemeyer et al.
patent: 5761470 (1998-06-01), Yoshida
patent: 5819088 (1998-10-01), Reinders
patent: 5922065 (1999-07-01), Hull
patent: 0 363 222 (1990-04-01), None
patent: 0 426 393 (1991-05-01), None
patent: 0 449 661 (1991-10-01), None
patent: 0463296 (1992-01-01), None
patent: 0 463 299 (1992-01-01), None
patent: 0 496 928 (1992-08-01), None
patent: 0 652 510 (1995-05-01), None
patent: WO 98/38791 (1998-09-01), None
Adams et al., “HARP: A Statically Scheduled Multiple-Instruction-Issue Architecture and it Compiler”,Technical Report 163,University of Hertfordshire, Hatfield, Herts UK, pp. 1-8, Sep. 1993.
Agerwala et al., “High Performance Reduced Instruction Set Processors”, RC 12434 (#55845),Computer Science,Jan. 9, 1987.
Allison, DEC 7000/10000 Model 600 AXP Multiprocessor Server,IEEE,1063-6390/93, pp. 456-464 (1993).
Anderson, D.W. et al. [1967] “The IBM 360 model 91: Processor Philosophy and instruction handling.” IBM J. Research and Development 11:1 (Jan.) pp. 8-24.
Arya et al., “An Architecture for High Instruction Level Parallelism”, pp. 1-21, Jan. 1995.
Bakoglu et al., “The IBM RISC system/6000 processor: hardware overview”,IBM J. Res. Develop.,34(1):12-22 (Jan., 1990).
Beck et al., “The Cydra 5 Minisupercomputer: Architecture and Implementation”,J. Supercomputing,7:143-179 (1993).
Butler, et al., “Single Instruction Stream Parallelism Is Greater than Two”, 1991 ACM, pp. 276-286.
Case et al., “DEC Enters Microprocessor Business With Alpha”,Microprocessor Report,6(3):1,6-14, (Mar. 4, 1992).
Chang et al., “Comparing Static and Dynamic Code Scheduling for Multiple-Instruction-Issue Processors”,Proceedings of the 24thInternational Symposium on Microarchitectures—MICRO24,pp. 1-9, 1991.
Charlesworth, A.E., [1981]. “An approach to scientific processing: The architecture design of the AP-120B/FPS-164 family” Computer 14:9 (Sep.), pp. 18-27.
Ch

Affiliated with

Also associated with

Rating

Instruction cache associative crossbar switch does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Instruction cache associative crossbar switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction cache associative crossbar switch will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2855947