JP2000259498A - Instruction cache for multi-thread processor - Google Patents

Abstract

PROBLEM TO BE SOLVED: To reduce competitions between different threads by storing at least one part of a real address in the desired instruction to be retrieved in response to an instruction cache error corresponding to respective plural threads. SOLUTION: A CPU 101 for processing an instruction is provided with independent internal level 1 instruction cache 106 (L1I cache) and level 1 data cache 107 (L1D cache). The L1I cache 106 is composed of a directory array and an array of cached instructions and both the arrays are shared by all the threads and accessed by composing a hash function of the effective address of the desired instruction. Each entry of the directory array stores at least one part of the read address of a correspondent cache line in the array of cached instructions. Namely, at least one part of the read address in the desired instruction to be retrieved is stored in response to the instruction cache error corresponding to plural threads.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

FIELD OF THE INVENTION The present invention relates generally to digital data processing, and more particularly to digital computer processing.
The present invention relates to an instruction cache for providing an instruction to a processing unit of a system.

[0002]

2. Description of the Related Art Today's computer systems typically include a central processing unit (CPU) and a communication bus and memory.
Includes hardware needed to store, retrieve, and transfer information.
Also, hardware necessary for external communication, such as an input / output controller or a storage device controller, and devices such as a keyboard, a monitor, a tape drive, a disk drive, and a communication line connected to a network connected thereto. Is also included. The heart of the system is the CPU. The CPU executes instructions constituting the computer program and instructs operation of other system elements.

[0003] From a computer hardware perspective, most systems behave essentially the same. Processors can perform certain simple operations, such as arithmetic, logical comparisons, and data movement. However, each operation is performed extremely fast. Because there are programs that instruct the computer to perform a lot of these simple operations, the illusion that the computer is doing something sophisticated is created. What a user perceives as a new function or an improvement in a computer system is realized by executing the same simple operation at a higher speed. Therefore, as computer systems continue to improve, they need to be faster.

[0004] The speed (also called "throughput") of an entire computer system is roughly measured by the number of operations performed per unit time. Conceptually, the simplest of the possible improvements is to increase the clock speed of various components, in particular to increase the clock speed of the processor. For example, if they all run twice as fast and otherwise function exactly the same, the system will perform some tasks in half the time. Early computer processors consisted of a number of discrete components, resulting in significantly faster speeds by miniaturizing components, reducing the number of components, and ultimately making the entire processor an integrated circuit on a single chip. Has become possible. The miniaturization allowed the processor clock speed to increase, resulting in a faster system.

[0005] Despite the significant speed gains achieved with integrated circuits, there is an ever-increasing demand for faster computer systems. Hardware designers have further improved the speed by various techniques, such as increasing the degree of integration (that is, increasing the number of circuits integrated on a single chip) and further miniaturizing the circuit. We know that we cannot keep going indefinitely, and there is a limit to the processor's ability to keep increasing the clock speed. Against this background, there is interest in other approaches to speeding up the overall computer system.

[0006] Improving system throughput without changing the clock speed is possible using multiple processors. This is a practical method since the cost of the individual processors integrated into the integrated circuit chip is not high. While the potential benefits of using multiple processors are true, they do introduce architectural issues.
If you don't look into these issues,
It turns out that there are still many reasons to improve the speed of individual CPUs, whether using U or one CPU. Given a constant CPU clock speed, it is possible to further increase the speed of individual CPUs, that is, to increase the number of operations performed per second, by increasing the average number of operations per clock cycle. .

[0007] When designing high performance processors to increase CPU speed, it is common to employ instruction pipelining and the use of cache memory levels. When a pipeline instruction is executed, execution of a subsequent instruction can begin before the previously issued instruction ends. A cache memory stores frequently used data and other data close to the processor and can continue executing instructions in most cases without waiting for full access time of main memory.

[0008] The pipeline fails under certain circumstances. An instruction that depends on the result of a previously dispatched instruction but has not yet completed may cause the pipeline to stop functioning. For example, an instruction that relies on a load / store instruction for which the required data is not in the cache (ie, a cache miss) cannot be executed until the data is available from the cache. Keep the data you need in the cache needed to keep it running,
The high hit ratio, the number of times data is readily available from the cache for the number of data requests, cannot be ignored, especially in calculations involving large data structures. When a cache miss occurs, the pipeline may stall for several cycles. Then, if the data is not available most of the time, the total memory delay becomes a major problem. Although memory devices used for main memory are becoming faster, the speed gap between such memory chips and high-end processors is becoming larger. Therefore, the high-end
Considerable execution time of the processor is spent waiting for cache miss resolution.

It can be seen that reducing the amount of time the processor waits for some event, such as refilling the pipeline or retrieving data from memory, increases the average number of operations per clock cycle. An architectural innovation that addresses this problem is "multi-threaded" processing. In this approach, the workload is divided into a plurality of independent executable instruction sequences called threads. The CPU maintains the state of the threads at any moment. As a result, switching threads is relatively simple and fast.

[0010] The term "multithreading" differs from the definition of software in the field of computer architecture and refers to the subdivision of a task into multiple related threads in the software domain. Architecturally, threads may be independent. The term "hardware multithreading" is often used to distinguish between the two definitions. Here, the term "multithread" is used to mean hardware multithread.

There are two basic forms of multithreading. The traditional form is also referred to as "fine grain multithreading," in which processors interleave execution on a cycle basis to execute N threads in parallel. This creates a gap in the execution of each instruction in one thread, eliminating the need for the processor to wait for short delay events, such as refilling the instruction pipeline. Another multi-thread is also referred to as "coarse-grain multi-threading," in which multiple instructions are executed sequentially in one thread until a relatively long delay event, such as a cache miss, is detected by the processor.

Normally, in a multithread, in order to maintain a state of a plurality of threads, a processor
Registers are duplicated. For example, when a processor implementing an architecture sold as PowerPC (trademark) implements multi-threading, the processor needs to maintain N states to execute N threads. Thus, general purpose registers, floating point registers, condition registers, floating point status / control registers, count registers, link registers, exception registers,
The save / restore registers and dedicated registers are duplicated N times. Also, special buffers, such as segment lookaside buffers, may be duplicated, or each entry may be tagged with a thread number; otherwise, flushing must be performed on each thread switch. is there. It is also necessary to duplicate branch prediction mechanisms such as correlation registers and return stacks.

Normally, level 1 instruction cache, level 1
Data cache, functional unit, execution unit, etc.
Relatively large hardware structures are not duplicated. Duplicating a relatively large hardware structure that is otherwise the same may have some incremental or incremental performance benefits. However, such an approach requires weighing these incremental benefits and the required hardware. The cache consumes a significant amount of space on the processor chip that can be devoted to other uses. Therefore, the size of the cache and the number and function of the caches must be carefully selected.

For high performance designs, processor chips often employ a level one instruction cache (L1I cache). The L1 I-cache is a cache for holding instructions that are considered to be executed in a relatively short time.

Another problem arises when the L1 I-cache is used in a multi-threaded processor. The I-cache needs to support fast thread switching without excessive contention between threads. A way to avoid contention is to use a separate I-cache for each thread, which either consumes valuable hardware or makes the individual cache for one thread too small. It is desirable that all threads share a single L1 ICache without excessive contention between threads. Further, it is more convenient not to use a low-speed address translation mechanism as much as possible due to the cache access mechanism.

The design of the L1 I-cache is a major challenge for high speed operation of the processor. If the I-cache miss rate is high, access is too slow, contention between separate threads is excessive, or it is difficult to maintain cache coherency, the processor will stop executing the next instruction. You will spend too much time waiting. To continue improving the processor, the L1 I-cache must efficiently meet these challenges, especially in multi-threaded environments.

[0017]

SUMMARY OF THE INVENTION It is an object of the present invention to provide an improved processor device.

It is another object of the present invention to provide an improved instruction cache for use in a multi-threaded processor.

Another object of the present invention is to reduce contention between threads of a multi-threaded processor accessing an instruction cache.

[0020]

SUMMARY OF THE INVENTION A multithreaded processor includes a level one instruction cache (L1 I-cache) that is shared by all threads. The L1 I-cache consists of a directory array and an array of cached instructions, both shared by all threads and accessed by constructing a hash function from the effective addresses of the desired instructions. Each entry in the directory array stores at least a portion of the real address of a corresponding cache line in the array of cached instructions. From there, the full real address of the instruction in the cache can be derived. Since there is an independent line fill sequencer for each thread,
While satisfying the cache line fill request of one thread, another thread can access the cache entry or prefetch the line for the executing thread.

In the preferred embodiment, the arrays are divided into sets, each set having one entry corresponding to each value of the hash function (N-way associative cache). The processor in this example maintains state information for two independent threads, and the instruction cache array is divided into two sets. However, the number of threads and cache associativity may vary. Each thread has independent access to cached instructions with the same hash value but different sets but less contention between different threads.

The I-cache is preferably an effective / real address table (Effective-to-Real Addr) which functions as a cache of an address translation table of the main memory.
essTable, ERAT). The ERAT includes a pair of an effective address part and a corresponding real address part. ER
The AT entry is accessed with a hash function of the effective address of the desired instruction. The effective address portion of the ERAT entry is then compared with the effective address of the desired instruction to confirm an ERAT hit. The corresponding real address portion is compared with the real address portion of the directory array to confirm a cache hit.

The line fill sequencer preferably operates in response to a cache miss. At that time, there is an ERAT entry of the requested effective address (ERAT hit). In that case, the full real address of the desired instruction can be constructed from the effective address of the ERAT and the information, eliminating the need to access the slow address translation mechanism of the main memory. The line fill sequencer accesses the memory directly using the configured real address.

Since there is an independent line fill sequencer for each thread, the threads can independently satisfy cache fill requests without waiting for each other. Also, the I-cache index is
Since the real page number corresponding to the entry is stored, cache coherency is simplified. In addition, ERAT
Using to associate valid and real page numbers often eliminates the need to access slow memory translation mechanisms. And the N-way associativity of the cache allows all threads to use a common cache without excessive thread contention.

[0025]

FIG. 1 illustrates the main hardware components of a single CPU computer system 100 employing an instruction cache architecture, according to a preferred embodiment of the present invention. The CPU 101 that processes the instruction
Independent internal level 1 instruction cache 106 (L1 I
Cache) and level 1 data cache 107 (L
1D cache). L1 I-cache 106
Stores an instruction executed by the CPU 101. L
The 1D cache is processed by the CPU 101.
Stores data other than instructions. CPU 101 is level 2
Connected to the cache (L2 cache) 108,
The cache 108 is used to hold both instructions and data. The memory bus 109 is connected to one L2 cache 108 or CPU 101 and the other main bus.
Data is transferred between the memories 102. CPU 101,
The L2 cache 108 and the main memory 102 also communicate with the system bus 110 via the bus interface 105. Various I / O processing units (IOP)
111 to 115 are connected to the system bus 110,
It supports communication with a variety of storage and I / O devices, such as direct access storage devices (DASD), tape drives, workstations, printers, remote communication lines that communicate with remote devices and other computer systems.

FIG. 1 conceptually shows the main components of the system 100, and the number and types of such components are not necessarily constant. In particular, multiple CPUs can be used in system 100. Such a multi-CPU system is shown in FIG. The system of FIG. 2 has four CPUs,
101A, 101B, 101C, 101D, and CP
U, L1 I-caches 106A, 106B,
106C, 106D, and L1 D cache 107
A, 107B, 107C and 107D. In addition, independent L2 caches 108A, 108B, 108C, 1
08D is associated with each CPU.

In the preferred embodiment, each CPU can maintain the state of two threads, and switches execution between threads at some delay event. In other words, the CPU executes one thread (the active thread) until some delay event that the CPU has to wait for is detected (coarse grain multi-thread 1).
Form). However, the present invention can be implemented by changing the number of thread states of each CPU, and interleave the execution of instructions from each thread on a cycle basis (fine
It is also possible to switch the thread according to (grain / multithread) or other criteria.

FIG. 3 is a diagram of the main components of the CPU 101. CPU 101 is shown in more detail than in FIGS. 1-3, according to a preferred embodiment. In this example, the components of FIG. 3 are integrated on one semiconductor chip. CPU10
1 is an instruction unit 201, an execution unit 211,
And a storage control unit 221. Generally, instruction unit 2
01 obtains an instruction from the L1 I-cache 106, determines an operation to decode and execute the instruction, determines a branch condition, and controls the flow of the program. Execution unit 21
1 performs an arithmetic operation or a logical operation on the data in the register, and loads or stores the data. Storage control device 2
21 accesses the data in the L1 data cache or takes a memory or interface external to the CPU that needs to fetch or store instructions and data.

The instruction unit 201 includes the branch unit 20
2, buffers 203, 204, 205, and decode /
A dispatch unit 206 is included. Instructions from L1 I-cache 106 are loaded from L1 I-cache instruction bus 232 into one of three buffers. The sequential buffer 203 stores 16 instructions in the current execution sequence. The branch buffer 205 stores eight instructions from the branch destination. These are speculatively loaded into the buffer 205 before branch evaluation if a branch is taken. The thread switch buffer 204 stores eight instructions of the inactive thread. If you need to switch from the currently active thread to the inactive thread, these instructions are immediately available. Decode / dispatch unit 206 receives and decodes the current instruction to be executed from one of the buffers to ascertain the operation or branch condition to be executed.
Branch unit 202 evaluates branch conditions to control program flow and refills buffers from L1 I-cache 106 by sending the effective address of the desired instruction on L1 I-cache address bus 231.

The execution unit 211 includes an S pipe 213,
M pipe 214, R pipe 215, and general purpose register 2
Includes 17 banks. The registers 217 are divided into two sets, each of which corresponds to each thread. R pipe 215
Is a pipeline arithmetic unit that performs some of the functions of simple integer arithmetic and logic. M-pipe 214 is a pipeline arithmetic unit that performs a relatively large set of operations and logic functions. The S pipe 213 is a pipeline device that executes load and store. Floating point unit (FPU) 212 and its associated floating point registers 216 are used for complex floating point operations that typically require several cycles. Floating point register 21
6 is divided into two sets corresponding to each thread, similarly to the general-purpose register 217.

The storage control device 221 is a memory management device 2
22, an L2 cache directory 223, an L2 cache interface 224, an L1 data cache 107, and a memory bus interface 225. The L1 D-cache is an on-chip cache used for data (rather than instructions). The L2 cache directory 223 is a directory of the contents of the L2 cache 108. The L2 cache interface 224 handles direct data transfer to and from the L2 cache 108. Memory bus interface 22
5 handles data transfer on the memory bus 109. The data transfer of the memory bus 109 is performed by the main memory 10.
2 or an L2 cache unit associated with another CPU. Memory management device 222
Is responsible for routing data access to various units. For example, if the S pipe 213 is loaded
When processing a command, if the data needs to be loaded into a register, the memory management unit will store the data in L1 D
It can be fetched from cache 107, L2 cache 108, or main memory 102. The memory management device 222 determines where to obtain the data. Since the L1 Dcache 107 can be directly accessed similarly to the L2 cache directory 223, the unit 222 stores the data in the L1 Dcache 1
07 or in the L2 cache 108. If the data is not in the on-chip L1 D-cache 107 or L2 cache 108, the memory bus
9 is fetched.

Although various components of the CPU have been described, many components not shown can be used in the CPU of the preferred embodiment, which are not essential to an understanding of the present invention. For example, a typical design would require the addition of dedicated registers, some of which would need to be duplicated per thread. The number, type, and arrangement of the components in the CPU 101 need not be constant. For example, the number and configuration of buffers and caches, the number and function of execution unit pipelines, arrays and sets that make up registers, and the like can be changed, and dedicated floating point processing hardware may or may not be used.

Instruction unit 201 ideally decodes in decode / dispatch unit 206,
It provides a stream of instructions for execution by the execution unit 211. The L1 I-cache 106 must respond to an access request with a minimum delay. When the requested instruction is actually in the L1 I-cache, the decode / dispatch unit 20
6 must be able to respond and fill the corresponding buffer without having to wait. The L1 I-cache cannot respond (i.e., the requested instruction is
When not in the cache), a relatively long path to the memory manager 222 via the cache fill bus 233 must be taken. In that case, the instructions may be obtained from the L2 cache 108, from the main memory 102, and possibly from disk or other storage. Also, if there are multiple processors in system 100, the instructions are:
It can also be obtained from the L2 cache of another processor. In either case, the instruction unit 201 may switch threads depending on the delay time when fetching an instruction from a remote location. That is, the active thread becomes inactive, the previously inactive thread becomes active, and the instruction unit 201 begins processing instructions of the previously inactive thread held in the thread switch buffer 204. .

FIG. 4 shows the main components of the L1 I-cache 106 in accordance with the preferred embodiment in more detail than FIGS. The L1 I-cache 106 includes an effective / real address table (ERAT) 301, an I-cache directory array 302, and an I-cache instruction array 30.
3 inclusive. I-cache instruction array 303 stores the actual instructions sent to instruction unit 201 for execution. The I-cache directory array 302 stores a set of information, such as real page numbers and valid bits, to manage the instruction array 303, and in particular to determine whether the desired instruction is actually in the instruction array 303. . E
The RAT 301 stores a pair of a valid page number and a real page number, and is used to associate a valid address with a real address.

The CPU 101 of the preferred embodiment supports a plurality of address translation levels, as shown by the logic in FIG. There are three basic addressing structures: an effective address 801, a virtual address 802, and a real address 803. “Effective address” refers to an address generated by the instruction unit 201 to refer to the instruction. That is, this is the address in terms of the user's executable code. The effective address can be generated in various conventional ways. For example, the upper address bits of a dedicated register (which do not change often, such as when a new task starts running), the concatenation of lower address bits from an instruction, the offset calculated from the address of a general register, It is generated as an offset from the instruction. The effective addresses in this embodiment are 64 bits and numbered from 0 to 63 (0 is the most significant bit). "Virtual address"
Is an operating system structure used to separate the address space of different users. In other words, if each user can refer to the entire range of effective addresses, it is necessary to map the effective address space of different users to a relatively large virtual address space to avoid contention. The virtual address is not a physical entity in the sense that it is stored in a register, but has a total 80-bit logical structure obtained by connecting the 52-bit virtual segment ID 814 and the lower 28 bits of the effective address. "Real address" refers to the physical location in memory 102 where the instruction is stored. The real address is 40 bits, 24 to 63
(24 is the most significant bit).

As shown in FIG. 11, the effective address 801
Contains a 36-bit valid segment ID 811, a 16-bit page number 812, and a 12-bit byte index 813, where the valid segment ID occupies the most significant bit position. The virtual address 802 is obtained by converting a 36-bit valid segment ID 811 into a 52-bit virtual segment ID.
814 and the resulting virtual segment ID 814
To the page number 812 and the byte index 813 to form an effective address. The real address 803 is derived from the virtual address by mapping the virtual segment ID 814 and page number 812 to a 52-bit real page number 815 and concatenating the real page number with the byte index 813. Since a page of main memory is 4K (or 2 @ 12) bytes, the byte index 813 (the least significant 12 address bits) specifies an address within the page and determines whether the address is a valid address, a virtual address, or a real address. Same whether or not. The high order bits specify the page and are therefore also called "valid page numbers" or "real page numbers".

The computer system 100 has a CP
The effective address generated by U101 is stored in memory 102
There is an address translation mechanism that translates to a real address. This address translation mechanism uses the valid segment I
A segment table mechanism 821 that maps D811 to a virtual segment ID 814, and a virtual page ID 814 that maps the virtual segment ID 814 and the page number 812 to a real page number 815.
Page table mechanism 822 that maps to Although shown as a single entity for convenience in FIG. 11, these mechanisms actually include a plurality of tables and registers at different levels. That is, there is a complete page table and a complete segment table in main memory 102, and the various smaller data caches of these tables are stored in CPU 101 itself or in the L2 cache. There is also a translation mechanism for directly translating an effective address to a real address under certain conditions (not shown).

The CPU 101 supports address conversion as shown in FIG. 11, but also supports simpler address designation. Specifically, the CPU 101 of the preferred embodiment
Operates in either "tag active" or "tag inactive" mode. The different modes indicate different addressing and support different operating systems. The bits of the machine status register (dedicated register) record the current operation mode. The full addressing translation described above is used in "tag inactive" mode. "Tag active"
In mode, the effective address is the same as the virtual address (ie, since the effective segment ID 811 is mapped directly to the virtual segment ID 813 without lookup, the upper 16 bits of the virtual segment ID are always 0). The CPU 101 also operates in an effective = real address addressing mode (described later).

The translation from a valid address to a real address requires multiple levels of table lookup. In addition, access to this mechanism is significantly slower than access to on-chip cache memory because the parts of the address translation mechanism are located remotely from the CPU chip and are associated with the memory 102. E
Since the RAT 301 stores some of the information maintained by the address translation mechanism and maps the effective address to the real address, in most cases the effective address and the effective address are stored in the L1 I-cache without having to access the address translation mechanism. It can be considered as a small cache that can associate real addresses at high speed.

The instruction unit 201 is the I-cache 10
6, when requesting an instruction and providing the effective address of the requested instruction, the I-Cache quickly determines whether the requested instruction is actually in the cache, returns the instruction if it is present, and returns If not, it is necessary to start processing to acquire the instruction from somewhere (L2 cache, main memory, etc.). In the normal case, the instruction is actually L1
In the I-cache 106, the following processing occurs in parallel in the I-cache as shown in FIG. a) According to the effective address from the instruction device 201, ERA
The entry at T301 is accessed to derive a valid page number and an associated real page number. b) The entry in the directory array 302 is accessed by the effective address from the instruction device 201, and a pair of real page numbers is derived. c) The entry in the instruction array 303 is accessed by the effective address from the instruction unit 201 to derive a cache line pair containing the instruction.

In any of the above cases, ERAT31
0, the directory array 302, and the input to any one of the instruction arrays 303 do not depend on the output of any one of these components, so none of the above processing can be performed before starting. There is no need to wait for completion.
Next, ERAT 301, directory array 302,
The output of the instruction array 303 is processed as follows.

A) The valid page number from ERAT 301 is compared in comparator 304 with the same address bits of the valid address from instruction unit 201. If they match, there is an ERAT "hit". b) The actual page number from the ERAT 301 is
At 5 and 306, each of the real page numbers from the directory array 302 is compared. If any match, and if there is an ERAT hit, there is an I-cache "hit". That is, the requested instruction is actually in the I-cache 106, specifically in the instruction array 303. c) The output of the comparison of the real page numbers from the ERAT 301 and the directory
Are selected (using the select multiplexer 307).

By executing these processes in parallel,
The delay when the desired instruction is actually in the I-cache is minimized. Regardless of whether the desired instruction is in the I-cache, there is some data at the output of the I-cache to the instruction unit 201. The independent I-cache hit signal indicates to the instruction device 201 that the output data actually has the desired instruction. When there is no I-cache hit signal, the instruction device 201 ignores the output data. The processing executed by the I-cache 106 in the case of a cache miss will be described later.

FIGS. 5 and 6 show the ERAT 301 and its related control structure in detail. ERAT 301 is an 82 bit x 128 array (i.e., there are 128 entries, each entry being 82 bits). Each ERAT entry is a part of an effective address (bits 0 to 4).
6), a part of the real address (bits 24 to 51), and an additional bit (described later).

ERAT 301 is accessed by constructing a hash function of bits 45-51 of the effective address (EA) along with the control lines. A control line (MT) which indicates whether multithreading is active (multithreading can be turned off in the preferred embodiment CPU design);
Two active thread lines (ActT) that indicate which of the two threads is active. The hash function is as follows.

(Equation 1)

This is a 7-bit function, and
Enough to specify the entry. Selection logic 40
1 selects a corresponding ERAT entry according to the hash function described above.

The comparator 304 compares bits 0 to 46 of the effective address generated by the instruction device 201 with the effective address part of the selected ERAT entry. Bits 47 to 51 of the effective address from the instruction device 201
Was used to construct the hash function, so that a match in bits 0-46 is sufficient to guarantee a match in the fully valid page number portion of the address, bits 0-51. The match between these two address parts is determined by the ER
The actual page number of the AT (RA24: 51) is actually
This means a real page number corresponding to the page number (EA0: 51) of the effective address specified by the instruction device 201. Therefore, the effective address part stored in the ERAT entry is not strictly meaning but may be called an effective page number. However, in the preferred embodiment, only bits 0 through 46 of the valid page number are included.

In some cases, the CPU 101
It operates in a special addressing mode, such as the real mode (E = R). When operating in this mode, the lower 40 of the effective address generated by the instruction device 201
Bits (that is, EA24: 63) are assigned to the real address (RA2
4:63). Normally, this mode is reserved for low-level operating system functions that work relatively efficiently if they are always stored at the same real address location. As shown in FIGS. 5 and 6, the control line E = R
Is active, ERAT 301 is effectively bypassed. That is, the selection multiplexer 402 sets E =
If R is false, RA2 from selected ERAT entry
4:51 is selected as the real page number (RPN) and E =
When R is true, EA 24:51 is selected from the instruction device 201. If E = R is true, ERAT is regarded as a hit regardless of the comparison result of the comparator 304.

Since the ERAT effectively bypasses the address translation mechanism previously described in conjunction with FIG. 8, the ERAT partially copies the access control information included in the normal address translation mechanism. That is, the conversion from the effective address to the real address is usually performed by confirming the access right based on additional information included in the segment table mechanism 821, the page table mechanism 822, and the like. ERAT
301 caches some of this information, eliminating the need to reference these address translation mechanisms. ERA
For more information on the operation of T, see U.S. patent application Ser. No. 08 / 966,706, Nov. 10, 1997, "Effective-To-
Real Address Cache Managing Apparatus and Method "
Please refer to.

The ERAT entry contains a parity bit,
Includes protection bits and access control bits. Especially ERAT
Each entry includes a cache inhibit bit, a problem state bit, and an access control bit. Also, the individual array 403 (1 bit × 128) includes one valid bit associated with each ERAT entry. In addition, tags
The mode bit pairs are stored in individual registers 404. The valid bits from array 403 are the corresponding ERA
Record whether the T entry is valid. Various conditions cause processor logic (not shown) to reset the valid bit, resulting in a subsequent access to the corresponding ERAT entry to reload the entry. The cache inhibit bit is used to inhibit writing of the requested instruction to I-cache instruction array 303.
That is, the address range may include an ERAT entry, but there may be a case where it is desired to avoid caching an instruction in the I-cache in this address range. In that case, a request for an instruction in this address range causes a line fill sequence logic (described later).
Obtains the requested instruction, but the instruction is not written to array 303 (the directory array 302 is not updated). The problem state bit records the "problem state" of the executing thread (i.e., supervisor or user) at the time the ERAT entry is loaded. Threads running in the supervisor state generally have greater access rights than threads in the problem state. ERA in a certain state
If the T entry is loaded, the problem state is subsequently changed, and the currently executing thread may not be able to access addresses in the range of the ERAT entry, and this information will be verified when the ERAT is accessed. There is a need. The access control bits also record access information when the ERAT entry is loaded and are checked at the time of access. Tag mode bit 404 records the tag mode of the processor (tag active or tag inactive) when ERAT is loaded. One tag mode bit is associated with each half (64 entries) of the ERAT. This is ERA
Selected using the 0 bit of the T HASH function. Tag mode affects the interpretation of effective addresses,
Changing the tag mode means that the real page number of the ERAT entry is not considered reliable.
If the tag mode changes, it is assumed that it will not change very often. Thus, if a change is detected, all corresponding half entries in the ERAT are marked invalid and eventually reloaded.

The ERAT logic 405 is connected to the selector 30
4 outputs, valid = real mode, various bits mentioned above,
And a signal for controlling the use state of the RPN output of the selection multiplexer and the maintenance of the ERAT based on bits of a machine state register (not shown) of the CPU.
In particular, logic 405 includes an ERAT hit signal 410,
A protection exception signal 411, an ERAT miss signal 412, and a cache inhibit signal 413 are generated.

The ERAT hit signal 410 indicates that the RPN output of the select multiplexer 402 can be used as a true real page number corresponding to the requested valid address. This signal can be asserted when valid = real (bypass ERAT), or when comparator 304 detects a match, there is no protection exception, and no specific condition to force an ERAT miss,
Active. This can be expressed by the following logic.

Match_304 is a signal from the comparator 304, and EA0: 46 from the instruction device 201 is ERAT.
Indicates that it matches EA0: 46 of the entry, and Val
id is the value of the valid bit from array 403.

(Equation 2)

The protection exception signal 411 indicates that the ERAT entry contains valid data, but that the currently executing process is not authorized to access the desired instruction. ERA
The T miss signal 412 indicates that the requested ERAT entry does not have the desired real page number or is not considered reliable, and in either case, the ERAT entry needs to be reloaded. Cache inhibit signal 413
Prevents the requested instruction from being cached in the instruction array 303. These signals are derived by the following logic.

(Equation 3)

Here, ERAT (Pr) is a problem status bit from the ERAT entry. ERAT (AC) is an access control bit from the ERAT entry. ERAT (CI) is a cache inhibit bit from the ERAT entry. MSR (TA) is a machine status register. MSR (Us) is the user status bit from the machine status register Tag_404 is the selected tag from the register 404
bit

FIG. 7 details the I-cache directory array 302 and its associated control structure. I
The cache directory array includes a 66-bit × 512 array 502 that holds real page numbers and specific control bits, and a 1-bit × 512 array 503 that stores MRU (most-recently-used) bits. Array 50
2 and 503 are physically independent, but logically 1
Can be treated as one array. Array 502 is logically 2
Divided into sets. First 33 of each array entry
The bits belong to the first set (set 0) and the last 33 bits of each entry belong to the second set (set 1). Each entry of array 502 has a 28-bit real page number (ie, real address bits 24-51) corresponding to set 0, four significant bits of set 0, a parity bit of set 0, and a 28-bit set 1 bit. It contains the real page number, the four significant bits of set 1, and the parity bit of set 1.

FIG. 8 illustrates the I-cache instruction array 303 and its associated control structure in detail. I-cache instruction array 303 includes a 64-byte by 2048 array, which, like directory array 502, is logically divided into two sets. The first 32 bytes of each array entry belong to set 0, and the remaining 32 bytes belong to set 1. Each entry of the instruction array 303 is
It includes eight instructions (4 bytes each) that can be executed by the processor corresponding to set 0, and eight instructions (4 bytes each) that can be executed by the processor corresponding to set 1.

Each entry in directory array 502 is associated with a contiguous group of four entries in instruction array 303. This contiguous group of four entries in one set (set 0 or 1) is called a cache line, and a single entry in either set is called a cache subline. The selection logic 601 has independent access to each entry (ie, a pair of cache sublines, one from each of set 0 and set 1), but corresponding to each cache line or a group of four sublines. The array 502 has only one real page number. Therefore, the four cache sublines constituting the cache line are filled as a group by one cache line filling operation (described later).

In the preferred embodiment, the cache line of the instruction array 303 contains 128 bytes and the cache line
7 addresses to specify a byte in the space of the line
Bits (address bits 57-63). Address bits 57 and 58 specify one of the four cache sublines in the cache line. The real address of the cache line is specified by real address bits 24-56. Effective address
Bits 48-56 (corresponding to the lower address bits of the cache line) are used to select entries in arrays 502 and 503. Selection logic 50
1 is a direct decode of these address bits.
This is effectively a simple hash function. That is, the possible combinations of valid address bits 48-56 are 2
There are nine, but 233 possible real addresses for the cache line
Individuals (combinations of real address bits 24-56) are mapped to this array. Similarly, valid address bits 48-58 (corresponding to the lower address bits of the cache sub-line) are used to select an entry in instruction array 303, and select logic 601
Direct decoding of these address bits. The real address of the cache subline of the instruction array 303 is
Valid address bits 52 through 58 (EA 52:58)
And the real page number of the corresponding entry and set of the directory array 502 (RA24: 51), concatenated with

Since each entry has two real page numbers (from set 0 and set 1), the I-cache directory contains two real page numbers corresponding to each 9-bit combination of effective address bits 48-56. There are numbers (and two cache lines in the instruction array 303). From this characteristic, it is possible to avoid I-cache contention between threads.

Since the selection logic 501 functions as a sparse hash function, there is no guarantee that any of the real page numbers contained in the entries of the array 502 will correspond to the fully valid address page number of the desired instruction. In order to confirm the correspondence, both the selected real page numbers are compared with the page number output 411 of the ERAT 301 using the comparators 305 and 306. At the same time as this comparison, the valid address bits 57, 58 cause the array 502
Of the four valid bits of the set 0 (selector 504) and the set 1
Of the four valid bits (selector 505) is selected. The valid bit selected corresponds to the cache subline of the desired instruction. These are ANDed with the outputs of the corresponding comparators 305, 306 to generate a pair of signals indicating the respective set match. The logical OR of these signals is ANDed with the ERAT hit signal 410 to generate an I-cache hit signal 510 indicating that the desired instruction is actually in the L1 I-cache.

As described above, selection logic 601
Accesses the entry ("subline" pair) of the instruction array 303 using the effective address of the desired instruction provided by the instruction device. Selector 602 selects a subline from set 0 of array 303 or a bypass subline value from cache write bus 604. The bypass subline value is used when a cache line is being filled after a cache miss. In that case, the first instruction array 3
There is no need to write to 03. Thus, a small amount of time is saved by bypassing the instruction array during a cache fill operation. The bypass subline value is also used when the cache inhibit line 413 is active.

The selector 603 is connected to the set selection line 51
Depending on the value of 1, select the output of selector 602 or a subline from set 1 of array 303. Set select line 511 is HIGH when there is a cache hit in half of cache set 1. That is, the comparator 306 outputs the real page number 411 from the ERAT.
And a set 1 real page number from the selected entry of the directory array 502 is detected. The corresponding subline valid bit selected by selector 505 is valid, set select line 511 goes HIGH, and selector 603 selects a subline from set 1 of array 303. In other cases (including cache misses), the output of selector 602 is selected. The output of selector 603 is 32 bytes of data representing eight instructions from consecutive memory locations. This is sent to the instruction unit 201 for writing to the sequential buffer 203, thread buffer 204, or branch buffer. If a cache miss occurs, I-cache hit line 510 goes LOW and the output of selector 603 is ignored (ie, not written to one of the buffers of instruction unit 201). If there is a cache hit (line 510 active), the MRU bit of the array corresponding to the selected directory entry is updated with the value of set select line 511.

The above description relates to the situation where the retrieved instruction is actually in the I-cache. When there is an I-cache miss, there are two possibilities. a) There is an ERAT hit but the instruction is not in the instruction array or b) there is an ERAT miss. If there is an ERAT hit, the desired cache line can be filled much faster. Since the real page number is in ERAT, the desired data is known to be in main memory (and may be in the L2 cache). In the logic of the L1 I-cache 106,
Constructing the full real address of the desired instruction from the ERAT data is possible without accessing external address translation mechanisms, and this data can be fetched directly from the L2 cache or memory. E
In the event of a RAT miss, an external address translation mechanism will need to be accessed to configure the real address of the desired instruction and, if necessary, to update the ERAT with a new real page number. In that case, the desired data may not be present at all in main memory,
It must be read from a secondary storage device such as a disk drive. In theory, the desired instruction is actually
There is a possibility of an ERAT miss when at 3, but this is considered a rare case. Therefore, when there is an ERAT miss, line filling of the instruction array is started at the same time.

FIGS. 9 and 10 show the logic of the main high-speed line fill sequencer, that is, the control logic for generating a cache line fill in the event of an ERAT hit or in the event of a cache miss. . The high-speed line fill sequencer logic includes a pair of line fill start logic 701 and registers 710 and 711 for storing line fill request parameters for suspending the completion of the line fill operation (LF each).
Addr0, LFAddr1).

The LFAddr registers 710 and 711 each correspond to one of two threads. That is, LFA
ddr0 710 is in thread 0, LFAddr1 7
11 corresponds to the thread 1. When the instruction device 201 issues an instruction request during the execution of the thread 0, the request parameter is stored in the LFAddr0 register 710, and similarly, the request during the execution of the thread 1 is the LFA
The data is stored in the ddr1 register 711. (If multithreading is off, only the LFAddr0 register 710 is used.) The LFAddr registers 710, 711 each store only one line fill request. Therefore, if an ERAT hit and an I-cache miss occur while a thread has pending line fill requests for the same thread, the second request must be delayed.

The LFAddr registers each include valid address bits 48-58 (EA 48:58), real address bits 24-51 (RA 24:51), set bits, and a request pending ("R") bit. The address bits are used to generate the real address of the memory of the cache line to be filled and to write to the directory array 502 and the instruction array 303 when the cache line is returned. The set bit determines which set (set 0 or set 1) of directory array 502 or instruction array 303 is to be written. Request pending (“R”) bit is L
1 when an undecided request enters the FAddr register
And reset when the line fill request is completed (reset logic not shown).

The line fill start logic 701 has as inputs an ERAT hit line 410, an I-cache hit line 510, and an active thread control line (Act) that specifies which thread is active.
T), and LFAddr0 register 710 and LFAdd
The request pending bits (represented as “R0” and “R1”, respectively) from the r1 register 711 are received. A line fill request is initiated when there is an ERAT hit, when there is an I-cache miss, and when no line fill request is currently pending in the LFAddr register corresponding to the currently active thread ( The line fill request line 703 becomes active). LFAdd corresponding to currently active thread with ERAT hit and I-cache miss
If there is a pending line fill request in the r register, the I-cache will indicate the pending line fill request.
Wait for the request to complete (reset the "R" bit) before starting a new line fill request. The logical relationship between these inputs and outputs can be expressed as follows.

(Equation 4)

When a line fill request is initiated, the line fill start logic causes the write signal 70
4, 705 and the request parameter is LFA
Written to ddr registers 710, 711. Either one of the write signals 704, 705 may always be active. When either one of the write signals 704, 705 becomes active, EA 48:58 (from the L1 I-cache address bus 231), RA 24:51 (from path 411, ERAT 301), and the set bit from the set logic 720 Is stored in the LFAddr register corresponding to the currently active thread.
At the same time, the request pending bit of the register is set to 1. The write signal is logically derived as follows.

(Equation 5)

The directory array 502 and the instruction array 303 are divided into two sets (set 0 and set 1).
Because each is indexed with the same hash function, the cache lines from the line fill request can be written to any set logically. The set to which the cache line is written is determined by the set logic 720 at the time the line fill request is issued and stored in the corresponding LFAddr register set bit. Generally, the set selected is the LRU set of cache lines to be filled. That is, the set is the inverse of the MRU bit corresponding to the entry in directory array 502 that is indexed by the hash function. However, in the special case where there is a pending line fill request in an inactive thread and this pending line fill fills the same cache line, the set selected is the pending line fill request for the inactive thread. The opposite of the set selected for the request. Therefore, the line
Locking the set at the beginning of the fill request will result in a live lock (ie, two pending line fill requests trying to write to the same set)
Is avoided.

FIGS. 9 and 10 show how to use the information stored in the register 710. FIG. A similar data path from register 711 is not shown for convenience. The address of the cache subline containing the requested instruction is derived from the address information stored in the corresponding LRAddr register. Specifically, the actual page number (RA24: 5
1) is concatenated with bits EA 52:58 to get the real address of the cache subline. This is shown as feature 712 in FIGS. This is not necessarily an individual register, but merely a representation of the address combination from one corresponding bit of the LFAddr register. Line Fill Request Line 7
03 starts a data request to the memory management device 222 and
The address indicated as 2 is transferred. Thread tag
The bits are also transferred, and the L1 I-cache control logic can then determine the LFAddr register to associate with the returned instruction. Next, the memory management device stores the requested instruction in the L2 cache 108, the main memory 102,
Or from another source.
If the requested instruction is available from the memory manager 222, it is transferred on the bus 233 to the L1 I-cache along with the thread tag bit.

When the requested instruction is returned on bus 233, a control signal is generated and data is written to directory array 502 and instruction array 303. Specifically, EAs 48:56 from corresponding LFAddr registers 710, 711 are used to select an entry in array 502. The set bit from the LFAddr register, along with the control signal,
6, 707 is used to generate a write signal for one half of array 502, and the state of the set bit is written to either half of array 502 (ie, write signal lines 706, 707). Is active). The real page number (RA24: 51) from the LFAddr register is written to the half-array 502 determined by the set bit, the entry selected by EA 48:51. The MRU bits in the directory array are updated at the same time.

In parallel with the above operation, EA 48:56 from the LFAddr register is used to select an entry in the instruction array 303, and the set bit from the LFAddr register is similarly written to half of the array. Used to generate a signal. The data written to this location is data (a series of instructions) from the bus 233 and sent to the LF data bus 604 shown in FIG. However, when filling the instruction array 303, only one subline can be written at a time. The LF data bus 604 sends one subline at a time (32 bytes). The complete subline is selected by selection logic 601 using EA 48:56 from the LFAddr register and two address bits 57, 58 provided by sequence logic (not shown). Therefore, four write cycles are required to fill the entire cache line.

When the real page number of the updated instruction array entry is written to directory array 502,
Four valid bits (one for each subline) are initially set to invalid. As successive sub-lines are written into instruction array 303, directory array 50
The two corresponding valid bits are updated to indicate that the data is valid. If the write of a cache line on successive write cycles as described above needs to be interpreted for any reason, the directory
Array 502 contains the correct information.

In the case of an ERAT miss, the output of the real page number of the selection multiplexer 402 is not reliable. Before performing any other processing, it is necessary to convert the page number portion of the effective address from the instruction device 201 into a real page number. The ERAT_Miss line 412 triggers the address translation mechanism shown in FIG. The hardware that actually performs this conversion is not part of the ICache 106. Part of the hardware can be incorporated in the CPU 201, and other hardware can be located in the main memory 102 or the like. This address translation typically requires more cycles than the line fill operation described above. ERAT
Following the mistake, when the translated real page number is returned,
In parallel with this, the real page number is used for updating the ERAT 301, written to the corresponding LFAddr register (710 or 711), and the line fill operation is started. In that case, in theory, the requested instruction is already in the cache regardless of the ERAT miss, but this is considered a rare enough case that a line fill operation can be performed immediately rather than waiting for the ERAT entry to be filled. To improve performance.

Illustrations and descriptions of logic circuits that are not essential for understanding the present invention are omitted here for convenience. For example, logic to maintain the MRU bits in array 502, logic to detect parity errors and take corrective action, etc. are omitted.

In the preferred embodiment, the ERAT is used to provide a real address (part of the real page number) to compare with the real page number of the directory array for the purpose of verifying a cache hit. This design is desirable because ERAT provides high speed conversion to real page numbers. Fast translation does not depend on the response time of the underlying address translation mechanism. This avoids certain restrictions for the system designer. In other words, a basic address translation mechanism for translating addresses at the high speed required to support one cycle of response time in the I-cache is not required. However, in another embodiment, the instruction cache can be configured without an ERAT, as described herein. In that case, a basic address translation mechanism is used to provide a real page number that is compared to the real page number of the directory array. In another embodiment, another mechanism could be used to provide the real page number, either internal or external to the L1 I-cache.

The number of cache associativity is equal to the number of threads in the preferred embodiment. This is useful to avoid thread contention for a common cache. Alternatively, however, it is possible to design a cache in which the number of threads is not the same as the cache associativity, as described here. For example, if the number of threads supported by the processor is large, cache associativity as high as the number of threads is not necessary to avoid contention. In that case, in theory, there is a possibility of contention when the associativity is smaller than the number of threads, but it is considered that the possibility is sufficiently small, so that it is within an allowable range to reduce the cache associativity. Furthermore, even if there is a possibility of some contention, there is a case where the cache associativity is set to 1 in some cases.

In summary, the following matters are disclosed regarding the configuration of the present invention.

(1) A multi-threaded computer processing device which supports the execution of a plurality of threads, a plurality of register sets respectively corresponding to each of the plurality of threads, and decode logic for decoding an instruction. , An instruction device including sequence logic for generating an effective address of an instruction to be executed, and an instruction cache for providing the instruction in response to a desired effective address generated by the instruction device, the instruction cache comprising: A) a directory array, wherein there are a plurality of entries, each containing a part of the real address of the instruction, and an entry is selected using the desired effective address; and b) a plurality of entries, each of which contains the directory The directory includes at least one instruction associated with an entry of the array; An instruction array in which a re-array entry is selected using the desired effective address; and c) a real address of a desired instruction, each of which corresponds to the plurality of threads and is retrieved in response to an instruction cache miss. And a plurality of line fill registers storing at least a portion of the multi-threaded computer processing device. (2) the instruction cache includes: d) a plurality of entries, each entry including a part of an effective address and a part of a real address, and an entry selected using the desired effective address. The address translation array and the portion of the real address of the desired instruction stored in the line fill register are stored in the valid /
The multi-thread computer processing device according to (1), wherein the multi-thread computer processing device is obtained from an entry of a real address translation array. (3) the instruction cache includes: e) comparing the portion of the effective address from the entry in the effective / real address translation array with a corresponding portion of the desired effective address, -The multi-threaded computer processing device according to (2), further including a comparator for determining a hit. (4) The directory array has N sets (N> 1)
And each of the directory array entries includes a portion of a plurality of real addresses of an instruction, and the real address portions are respectively associated with the N of the directory array.
Belonging to a corresponding one of the sets, the instruction array is divided into N sets, each set corresponding to the set of directory arrays, the instruction array entries each including a plurality of instructions, each instruction being the instruction The multi-thread according to (1), which belongs to said N sets of arrays.
Computer processing equipment. (5) The multi-thread computer processing device is N
The multi-thread computer processing device according to (4), which supports execution of a thread. (6) the line fill registers each include a set field, the set field specifying a set of the N sets in which a desired instruction to be retrieved is stored after retrieval; A multi-threaded computer processing device as described. (7) the instruction cache is: e) associating the portion of the real address of the instruction from the associated portion of the selected entry of the directory array with the desired validity; The multi-threaded computer processing device according to (4), further including N comparators for determining a cache hit by comparing with a common part of a real address associated with the address. (8) The instruction cache includes: d) a plurality of entries, each entry including a part of an effective address and a part of a real address, and an entry is selected using the desired effective address. The multi-thread of claim 4 including a real address translation array, wherein the portion of the real address of the desired instruction stored in the line fill register is obtained from an entry in the valid / real address translation array. -Computer processing equipment. (9) the instruction cache is: e) associating the portion of the real address of the instruction from the associated portion of the selected entry of the directory array with the desired validity, each associated with the set of directory arrays; Determining a cache hit in comparison with the intersection of the real addresses associated with the address; and the intersection of the real address associated with the desired effective address to be compared to determine the cache hit, The multi-threaded computer processing device according to (8), further comprising N comparators obtained from the valid / real address translation array entry. (10) A multi-threaded computer processing device, comprising: a plurality of register sets each corresponding to a thread; decode logic for decoding an instruction; and sequence logic for generating an effective address of an instruction to be executed. An instruction cache for providing instructions in response to a desired effective address generated by the instruction cache, the instruction cache having a plurality of entries, divided into N sets (N>1); The entries each include N parts, each entry part being associated with a set of the N sets, including a portion of the real address of the instruction, and selecting an entry using the desired effective address. There is an array and a plurality of entries, each entry associated with an entry of the directory array, , Wherein each set corresponds to the set of directory arrays and includes N portions, and each entry portion is associated with a set of the N sets of the instruction array and includes at least one And an array of instructions, each of which is associated with a set of the directory arrays, and from an associated portion of the selected entries of the directory array, the entries being selected using the desired effective address. N comparators comparing the portion of the real address of the instruction with a common portion of the real address associated with the desired effective address to determine a cache hit. apparatus. (11) The multi-thread computer processing device according to (10), wherein the multi-thread computer processing device supports execution of N threads. (12) The instruction cache includes: d) a plurality of entries, each entry including a part of an effective address and a corresponding part of a real address, and an entry is selected using the desired effective address; Effectiveness/
The common portion of the real address associated with the desired effective address, including the real address translation array and compared by the comparator to determine a cache hit, is derived from an entry in the effective / real address translation array. The multi-thread computer processing device according to (10), which is acquired.

[Brief description of the drawings]

FIG. 1 is a diagram of the main hardware components of a single CPU computer system in accordance with a preferred embodiment of the present invention.

FIG. 2 is a diagram of the main hardware components of a computer system with multiple CPUs, according to a preferred embodiment of the present invention.

FIG. 3 is a diagram of a central processing unit of a computer system according to a preferred embodiment.

FIG. 4 is a diagram of the main components of an L1 instruction cache according to a preferred embodiment.

FIG. 5 is a diagram of a valid / real address table and associated control structure in accordance with a preferred embodiment.

FIG. 6 is a diagram of a valid / real address table and associated control structure in accordance with a preferred embodiment.

FIG. 7 is a diagram of an L1 instruction cache and its associated control structure according to a preferred embodiment.

FIG. 8 is a diagram of an instruction array of an L1 instruction cache and associated control structures according to a preferred embodiment.

FIG. 9 is a diagram of the main control logic for generating a cache line fill in accordance with a preferred embodiment.

FIG. 10 is a diagram of the main control logic for generating a cache line fill in accordance with a preferred embodiment.

FIG. 11 is a diagram of address translation according to a preferred embodiment.

[Explanation of symbols]

100 System 101, 101A, 101B, 101C, 101D C
PU 102 Main memory 105 Bus interface 106, 106A, 106B, 106C, 106D Level 1 instruction cache (L1 I cache) 107, 107A, 107B, 107C, 107D Level 1 data cache (L1 D cache) 108, 108A, 108B, 108C, 108D Level 2 cache (L2 cache) 109 Memory bus 110 System bus 111, 112, 113, 114, 115 I / O processing unit (IOP) 201 Instruction unit 202 Branch unit 203 Sequential buffer 204 Switching buffer 205 Branch Buffer 206 Decode / Dispatch Unit 211 Execution Unit 212 Floating Point Unit (FPU) 213 S Pipe 214 M Pipe 215 R Pipe 16 Floating-point register 217 General-purpose register 221 Storage controller 222 Memory management device 223 L2 cache directory 224 L2 cache interface 225 Memory bus interface 232 L1 I-cache instruction bus 233 Cache fill bus 301 Effective / real address table (ERAT) 302 I-cache directory array 303 I-cache instruction array 304, 305, 306 Comparator 310 ERAT 310 403 Individual array 404 Individual register 405 ERAT logic 410 ERAT hit signal 411 Protection exception signal 412 ERAT miss signal 413 Cache inhibit signal 501 , 601 selection logic 502 66-bit × 512 array 503 1-bit × 512 array 50 , 602 selector 510 I cache hit signal 511 set select line 604 cache write bus 801 effective address 701 line fill start logic 704, 705 write signal 710, 711 LFAddr register 720 set logic 802 virtual address 803 real address 814 virtual segment ID 811 36-bit valid segment ID 812 16-bit page number 813 12-bit byte index 814 52-bit virtual segment ID 815 52-bit real page number 821 Segment table mechanism 822 Page table mechanism

──────────────────────────────────────────────────続 き Continued on the front page (51) Int.Cl. ⁷ Identification FI theme coat ゛ (Reference) G06F 12/12 G06F 12/12 A (72) Inventor Richard William Doing USA 55901, Rochester, Minnesota, Fiftina Inns Street, North West 2532 (72) Inventor Ronald Nick Carla United States 55991, Zambro Falls, MN, East Ryans Bay Road, Box 77A, Rail Road 1 (72) Inventor Stephen Joseph Schwein 17902-A Jubilee Way, Lakeville, MN 55044 United States 55044

Claims (12)

[Claims] 1. A multi-threaded computer processing device, comprising: a plurality of register sets each supporting execution of a plurality of threads, each corresponding to each of the plurality of threads; decoding logic for decoding instructions; An instruction device including sequence logic for generating an effective address of an instruction to be executed; and an instruction cache for providing the instruction in response to a desired effective address generated by the instruction device, the instruction cache comprising: a) a directory array, where there are a plurality of entries, each containing a portion of the real address of the instruction, and the entry is selected using the desired effective address; The directory associated with an entry of the array and including at least one instruction; An instruction array in which an entry in the array is selected using the desired effective address; and c) at least a real address of a desired instruction, each of which corresponds to the plurality of threads and is retrieved in response to an instruction cache miss. A multi-threaded computer processing device including a plurality of line fill registers for storing a portion. 2. The instruction cache, comprising: d) a plurality of entries, each entry including a portion of a valid address and a portion of a real address, wherein an entry is selected using the desired valid address. 2. The multi-thread of claim 1, wherein the real address translation array and the portion of the real address of the desired instruction stored in the line fill register are obtained from an entry in the valid / real address translation array. -Computer processing equipment. 3. The instruction cache further comprises: e) comparing the portion of the effective address from the entry in the effective / real address translation array with a corresponding portion of the desired effective address. 3. The multi-threaded computer processing device of claim 2, including a comparator that determines a translation array hit. 4. The directory array includes N sets (N sets).
> 1), wherein each of the directory array entries includes a portion of a plurality of real addresses of an instruction;
The real address portions each belong to a corresponding set of the N sets of the directory array, the instruction array is divided into N sets, each set corresponding to the set of directory arrays, The multi-threaded computer processing apparatus of claim 1, wherein each entry includes a plurality of instructions, each instruction belonging to said N sets of said instruction array. 5. The multi-threaded computer processing device of claim 4, wherein said multi-threaded computer processing device supports N-thread execution. 6. The line fill registers each include a set field, the set field comprising:
5. The multi-threaded computer processing device of claim 4, wherein the desired instruction to be searched specifies a set of the N sets that are stored after the search. 7. The instruction cache includes: e) each associated with the set of directory arrays, and retrieving the portion of an instruction's real address from an associated portion of a selected entry of the directory array to the desired address. 5. The multi-threaded computer processing device of claim 4, further comprising N comparators for determining a cache hit as compared to a common portion of the real address associated with the effective address of the multi-threaded address. 8. The instruction cache includes: d) a plurality of entries, each entry including a part of an effective address and a part of a real address, and an entry is selected using the desired effective address; 5. The multi-function system according to claim 4, further comprising a valid / real address translation array, wherein said portion of a real address of a desired instruction stored in said line fill register is obtained from an entry in said valid / real address translation array. Thread computer processing unit. 9. The instruction cache further comprises: e) each associated with the set of directory arrays, and retrieving the portion of an instruction's real address from an associated portion of a selected entry of the directory array to the desired portion. Determining a cache hit in comparison with a common portion of a real address associated with the effective address of the first one, and comparing the common portion of the real address associated with the desired valid address to be compared to determine the cache hit 9. The multi-threaded computer processing device of claim 8, further comprising: N comparators obtained from the valid / real address translation array entries. 10. A multi-threaded computer processing device, comprising: a plurality of register sets each corresponding to a thread; decode logic for decoding instructions; and sequence logic for generating effective addresses of instructions to be executed. And an instruction cache for providing an instruction in response to a desired effective address generated by the instruction device. The instruction cache has a plurality of entries and is divided into N sets (N> 1). Each of the entries includes N portions, each entry portion being associated with a set of the N sets, including a portion of a real address of an instruction, and selecting an entry using the desired effective address. There is a directory array and a plurality of entries, each entry associated with an entry in the directory array. And a plurality of instructions, each of which corresponds to the set of directory arrays and includes N portions, each entry portion being associated with a set of the N sets of the instruction array. An array of instructions, each including at least one instruction, wherein an entry is selected using the desired effective address, each associated with a set of the directory arrays, and associated with the selected entry of the directory arrays. N comparators comparing the portion of the real address of the instruction from the portion with a common portion of the real address associated with the desired effective address to determine a cache hit; -Computer processing equipment. 11. The multi-threaded computer processing device supports N threads of execution.
A multi-threaded computer processing device as described. 12. The instruction cache includes: d) a plurality of entries, each entry including a part of an effective address and a corresponding part of a real address, and the entry is selected using the desired effective address. Valid /
The common portion of the real address associated with the desired effective address, which is compared by the comparator to determine a cache hit, includes a real address translation array from the entry in the effective / real address translation array. The multi-threaded computer processing device of claim 10, obtained.