Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-06-26
2001-07-03
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C365S230040, C365S049130, C711S127000
Reexamination Certificate
active
06256709
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a cache of a super-scalar microprocessor, and more particularly, the present invention relates to a method for sustaining a high-fetch bandwidth across multiple cache lines in a wide issue processor.
2. Description of the Related Art
The current generation of superscalar microprocessors have a high instruction bandwidth which necessitates the spanning of adjacent lines of address space in the instruction cache (“i-cache” herein). Also, due to power and area restrictions, typically only single-ported RAM cell are considered in the implementation of the i-cache array structure. As discussed in more detail below, these factors contribute to what is referred to herein as a “line-crossing” event. Line crossing occurs if a cache access for a given set of instructions requires access to more than one line of the cache simultaneously.
FIG. 1
illustrates a two-way set associative cache structure typically employed as an i-cache interfacing with main memory in an
8
-issue superscalar machine. (Although not shown, an external cache may be interposed between the i-cache and main memory.) The i-cache is identified by reference numeral
102
and the main memory by reference numeral
104
. The main memory
104
is divided into multiple groups (512 in this example) of eight-instruction (8i) lines, or 32-byte blocks. The numbers in parentheses denote the line or block number, whereby line (
1
) follows line (
0
), line (
2
) follows line (
1
), and so on. The memory
104
is depicted as byte aligned to relate it to cache-line sizes. Any two lines of each group of the main memory
104
may be stored in an associated set of the i-cache
102
. In other words, any two lines of group
0
of main memory
104
can be stored in set
0
of i-cache
102
, any two lines of group
1
of main memory
104
can be stored in set
1
of i-cache
102
, and so on. The two instruction lines of each set of the i-cache
102
are stored in the two “ways” of the set, i.e., “way
0
” and “way
1
”. The i-cache is capable of outputting one line (or one way) of instructions at a time.
Reference is now made to
FIG. 2
for an explanation of a line crossing event in the i-cache of
FIG. 1. A
line crossing event is caused by a branch instruction in the executing program. Consider, for example, the case of sixteen instructions
0
-
15
stored in order in consecutive lines
202
and
204
of main memory
206
. Reference character B
1
denotes a branch “in” to instruction
3
, and reference character B
2
denotes a branch “out” at instruction
10
. Thus, a set of 8 instructions is to be executed in the span of these two branches B
1
and B
2
. However, notwithstanding the capability of the i-cache
102
to output 8 instructions (
1
line) at a time, two cache access cycles are needed in this example. That is, a first cycle is needed to source five instructions, and a second cycle is needed to source three instructions. As shown in
FIG. 2
, way
0
of set
0
contains instructions
3
-
7
, and way
0
of set
1
contains instructions
8
-
10
. Keeping in mind that a single line or way is output at a time from the i-cache, a line crossing event occurs in which a cache access for a set of 8 instructions (or eight 32 bit words) requires accessing more than one 32-byte line of the cache. Since, in the example of an 8-issue machine, the processor pipeline is capable of processing eight instructions, line crossing creates inefficiencies in program execution.
In the absence of branch instructions, the program code would simply execute in order from one instruction to the next as stored in the i-cache, and there would rarely be a need to access the middle of a cache line. In fact, however, branch instructions are quite common. Moreover, line-crossing is an event that can be expected to occur at even higher frequencies given the large instruction bandwidth requirements of next-generation microprocessors. It is anticipated that 1 branch per set of instructions fetched per cycle will be encountered on average. The occurrence of a branch would lead to a line crossing event unless the branch address is aligned to an 8-word (32 byte) boundary in the main memory. In addition, once a branch causes a line crossing event, line crossing may continue to occur until there is a branch out of the address space. Line crossing events, requiring multiple cache accesses, thus have the potential to substantially slow processing speeds.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to overcome one or more drawbacks associated with the conventional i-cache architecture discussed above.
It is a further object of the present invention to provide a method for sustaining high-fetch bandwidth across multiple cache lines in a wide issue machine.
It is yet another object of the invention to provide a method which allows for the accessing of multiple data spanning two cache lines in a single access cycle.
To achieve the above and other objects, the present invention provides a method for storing two-way set associative data having odd and even number sets of data and two ways of data per set, said method comprising: storing odd number sets of the two-way set associative data in an odd set data bank such that the two ways of each odd number set are aligned horizontally within said odd set data bank; and storing even number sets of the two-way set associative data in an even set data bank such that the two ways of each even number set are aligned horizontally within said even set data bank.
According to another aspect of the invention, the method further comprises aligning said odd set data bank horizontally with said even set data bank such that each odd number set is aligned horizontally with a next or previous even number set.
According to another aspect of the invention, the two-way set associative data contains x sets, and each of the odd and even set data banks have a data height of x/2 lines.
According to yet another aspect of the invention, each way is for storing y words and wherein a data word width of each of said odd and even set data banks is 2y words. In one example, x equals 512 and y equals 8.
According to still another aspect of the invention, the odd and even set banks are implemented by single-ported RAM cells.
According to another aspect of the invention, the method further comprises bit interleaving the four ways of the horizontally aligned sets.
REFERENCES:
patent: 4736293 (1988-04-01), Patrick
patent: 4905188 (1990-02-01), Chuang et al.
patent: 5182802 (1993-01-01), Dillard
patent: 5390139 (1995-02-01), Smith et al.
patent: 5474825 (1995-12-01), Yonezawa et al.
patent: 5555529 (1996-09-01), Hose, Jr. et al.
patent: 5854761 (1998-12-01), Patel et al.
Cherabuddi Rajasekhar
Panwar Ramesh
Patel Sanjay
Talcott Adam R.
Peikari B. James
Rosenthal & Osha L.L.P.
Sun Microsystems Inc.
LandOfFree
Method for storing data in two-way set associative odd and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for storing data in two-way set associative odd and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for storing data in two-way set associative odd and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2522032