Patent Publication Number: US-6658556-B1

Title: Hashing a target address for a memory access instruction in order to determine prior to execution which particular load/store unit processes the instruction

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The present application is related to the following copending applications, which are filed on even date herewith and incorporated herein by reference: 
     (1) U.S. application Ser. No. 09/364,284; 
     (2) U.S. application Ser. No. 09/364,283; 
     (3) U.S. application Ser. No. 09/364,282; 
     (4) U.S. application Ser. No. 09/364,287; 
     (5) U.S. application Ser. No. 09/364,285; 
     (6) U.S. application Ser. No. 09/364,281; and 
     (7) U.S. application Ser. No. 09/364,286. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Technical Field 
     The present invention relates in general to data processing and, in particular, to the storage subsystem of a data processing system. Still more particularly, the present invention relates to a data processing system having asymmetrically partitioned load-store hardware. 
     2. Description of the Related Art 
     In order to capitalize on the high performance processing capability of a state-of-the-art processor core, the storage subsystem of a data processing system must efficiently supply the processor core with large amounts of instructions and data. Conventional data processing systems attempt to satisfy the processor core&#39;s demand for instructions and data by implementing deep cache hierarchies and wide buses capable of operating at high frequency. Although heretofore such strategies have been somewhat effective in staying apace of the demands of the core as processing frequency has increased, such strategies, because of their limited scalability, are by themselves inadequate to meet the data and instruction consumption demands of state-of-the-art and future processor technologies operating at 1 GHz and beyond. 
     SUMMARY OF THE INVENTION 
     To address the above and other shortcomings of conventional processor and data processing system architectures, the present invention introduces a processor having a hashed and partitioned storage subsystem. The processor includes at least one execution unit, an instruction sequencing unit coupled to the execution unit, and a cache subsystem including a plurality of caches that store data utilized by the execution unit. Each cache among the plurality of caches stores only data having associated addresses within a respective one of a plurality of subsets of an address space. 
     In one preferred embodiment, the execution units of the processor include a number of load-store units (LSUs) that each process only instructions that access data having associated addresses within a respective one of the plurality of address subsets. The load-store units can have diverse hardware such that a maximum number of instructions that can be concurrently executed is different for different load-store units or such that some of the load-store units are restricted to executing certain classes of instructions. 
     The processor may further be incorporated within a data processing system having a number of interconnects and a number of sets of system memory hardware that each have affinity to a respective one of the plurality of address subsets. All objects, features, and advantages of the present invention will become apparent in the following detailed written description. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein: 
     FIG. 1 depicts an illustrative embodiment of a multiprocessor data processing system in accordance with the present invention; 
     FIG. 2 illustrates a more detailed block diagram of a processor in the multiprocessor data processing system of FIG. 1; 
     FIG. 3A depicts a circuit that can implement an exemplary hashing algorithm on selected address bits; 
     FIG. 3B illustrates the bit positions of the address bits forming inputs to the exemplary hashing algorithm shown in FIG. 3A; 
     FIGS. 4A and 4B respectively depict more detailed block diagrams of the general purpose register file (GPRF) and floating-point register file (FPRF) of the processor of FIG. 2; 
     FIG. 5 is a block diagram of an exemplary embodiment of a compiler in accordance with the present invention; 
     FIG. 6 illustrates an exemplary embodiment of an instruction within the instruction set architecture (ISA) of the processor depicted in FIG. 2; and 
     FIG. 7 depicts a block diagram of an illustrative embodiment of a hash selection circuit in accordance with the present invention. 
    
    
     DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENT 
     With reference now to the figures and in particular with reference to FIG. 1, there is illustrated a high level block diagram of a multiprocessor data processing system in accordance with the present invention. As depicted, data processing system  8  includes a number of processors  10   a - 10   d , which each comprise a single integrated circuit including a processor core and an on-chip cache subsystem, as discussed further below. Processors  10   a - 10   d  are all connected to each of system interconnects  12   a - 12   d , which are in turn each coupled to a respective one of system memories  16   a - 16   d  through an associated one of memory controllers  14   a - 14   d.    
     According to an important aspect of the present invention, data processing system  8  implements a hashed and partitioned storage subsystem. That is, instead of the single memory controller and system memory implemented in many conventional data processing systems, the present invention partitions the system memory hardware into multiple memory controllers  14   a - 14   d  and multiple system memories  16   a - 16   d . System memories  16   a - 16   d  can each contain only a respective subset of all memory addresses, such that the disjoint subsets contained in all of system memories  16  together form the system memory data set. For example, each of system memories  16  may have a storage capacity of 2 GB for a total collective storage capacity of 8 GB. The subset of memory addresses assigned to each system memory  16  is determined by a hash algorithm implemented by each of processors  10   a - 10   d , as discussed further below. 
     Systems interconnects  12   a - 12   d  serve as conduits for transactions between processing units  10 , transactions between processing units  10  and memory controllers  14 , and transactions between-processors  10  or memory controllers  14  and other snoopers (e.g., I/O controllers) that may be coupled to system interconnects  12 . By virtue of the fact that each system interconnect  12  is connected to less than all of memory controllers  14  (and in the illustrated embodiment only one), each system interconnect  12  conveys only transactions that pertain to the addresses subset(s) assigned to the attached memory controller(s)  14 . Advantageously, system interconnects  12 , which may each be implemented as one or more buses or as a cross-point switch, can be implemented with the same or different architectures, bandwidths, and communication protocols, as will become apparent. 
     The hashing and partitioning of the storage subsystem of data processing system  8  is not limited in application to memory controllers  14  and system memories  16 , but preferably extends to the instruction fetch units (IFUs), load-store units (LSUs), register files, and cache subsystems of processors  10 . Referring now to FIG. 2, there is illustrated a high level-block diagram of a processor  10  within data processing system  8  of FIG.  1 . As shown, processor  10  includes three principal collections of circuitry: instruction sequencing unit  20 , execution units  22 ,  24   a - 24   d  and  26 , and data storage including register files  28  and  30  and cache subsystem  32 . 
     In the illustrative embodiment, cache subsystem  32 , which provides low latency storage for data and instructions likely to be processed by the execution units of processor  10 , includes level two (L 2 ) caches  34   a - 34   d  and bifurcated level one (L 1 ) instruction and data caches  36   a - 36   d  and  38   a - 38   d , respectively. In the illustrative embodiment, L 1  instruction caches  36  may be 32 kB each, L 1  data caches  38  may be 16 kB each, and L 2  caches  34  may be 512 kB each, for combined cache capacities of 128 kB of L 1  instruction cache, 64 kB of L 1  data cache, and 2 MB of L 2  cache. Of course, if desired, cache subsystem  32  may also include additional levels of on-chip or off-chip in-line or lookaside caches. 
     As indicated by the interconnection of L 1  caches  36  and  38  to respective L 2  caches  34   a - 34   d  and the interconnection of L 2 caches  34   a - 34   d  to respective system interconnects  12   a - 12   d , each L 1  cache  36 ,  38  and each L2 cache  34  can store only data and instructions having addresses within the subset of addresses contained in system memories  16  coupled to the associated interconnect. Thus, in the illustrated example, L 1  caches  36   a  and  38   a  and L 2  cache  34   a  can only cache data and instructions residing in system memory  16   a , L 1  caches  36   b  and  38   b  and L 2  cache  34   b  can only cache data and instructions residing in system memory  16   b , etc. 
     Instruction sequencing unit  20  contains a number of instruction fetch units (IFUs)  40   a - 40   d  that are each coupled to a respective one of L 1  instruction cache  36   a - 36   d . Thus, each IFU  40  has an affinity to a particular address subset. IFUs  40  independently fetch instructions from the associated L 1  instruction caches  36  and pass fetched instructions to either branch unit  42  or dispatch unit  44 , depending upon whether the instructions are branch or sequential instructions, respectively. Branch instructions are processed directly by branch unit  42 , but sequential instructions are opportunistically assigned by dispatch unit  44  to one of execution units  22 ,  24   a - 24   d  and  26  as execution resources (e.g., registers and a slot in completion buffer  46 ) become available. Dispatch unit  44  assigns instructions to execution units  22 ,  24   a - 24   d  and  26  according to instruction type and, if a load or store instruction, the target address of the instruction. In other words, integer and floating point instructions are dispatched to integer unit (IU)  22  and floating-point unit (FPU)  26 , respectively, while load and store instructions are dispatched to particular ones of LSUs  24   a - 24   d  after dispatch unit  44  hashes the target address specified by the instruction to determine which L 1  data cache  38  contains the target data. Thus, each of LSUs  24  executes only those load and store instructions targeting addresses within the particular address subset with which the associated L 1  cache has affinity. 
     The hash algorithm implemented by dispatch unit  44 , which is programmable and can be altered dynamically during operation of data processing system  8  as discussed below, can be based on any type of address (e.g., effective address, virtual address, or real (physical) address) or any combination of address types. Referring now to FIG. 3A, there is illustrated a block diagram of exemplary hashing circuit that utilizes five low order bits, which are present in effective, virtual, and real addresses, to hash an input address into one of four address subsets A-D. As shown in FIG. 3B, the five input bits, designated bits  52 - 56 , form the high order bits of the 12-bit page offset within both the N-bit (e.g., 64-bit) effective addresses  60  utilized by processors  10  and the 42-bit real addresses  62  utilized by cache subsystem  32 , memory controllers  14 , and other snoopers coupled to system interconnects  12 . In addition, the five selected bits form the low order bits of the index portion of the 42-bit real address  64  utilized to select a congruence class within L 2  caches  34 . As depicted in FIG. 3A, the exemplary hashing algorithm performs an exclusive-OR of bits  52 ,  54  and  56  (e.g., with an XOR gate  52 ) and an exclusive-OR of bits  53  and  55  (e.g., with an XOR gate  54 ) and decodes the two-bit result with a decoder  56  to select one of the four address subsets. 
     In the illustrative embodiment, dispatch unit  44  is the only point of centralization or interaction between the different instruction and data pipelines. As a consequence, if operations such as synchronizing instructions (e.g., SYNC) must be made visible to all caches or all system interconnects, dispatch unit  44  broadcasts such operations to all LSUs  24 . The synchronizing instructions are thereafter made visible on all system interconnects  12 . 
     Referring again to FIG. 2, general purpose register file (GPRF)  28  and floating-point register file (FPRF)  30  are utilized to temporarily store integer and floating-point operands consumed by and resulting from instruction execution. Thus, IU  22  is coupled to GPRF  28 , FPU  26  is coupled to FPRF  30 , and GPRF  28  and FPRF  30  are each coupled to one or more (and possibly all) of LSUs  24 . As shown in FIGS. 4A and 4B, which respectively illustrate more detailed views of GPRF  28  and FPRF  30 , each register file contains a respective set of rename registers  70 ,  72  for temporarily storing result data produced by the execution of instructions and a set of architected registers  74 ,  76  for storing operand and result data. Result data is transferred from rename registers  70 ,  72  to the associated set of architected registers  74 ,  76  following execution of an instruction under the direction of completion unit  46  within ISU  20 . 
     In accordance with the present invention, each of rename registers  70 ,  72  and architected registers  74 ,  76  may be partitioned between the various hashes so that only result data from instructions residing at and/or targeting addresses within the subset defined by a hash are stored in rename and architected registers associated with that hash. It is important to note that the number of registers allocated to each hash within each of register sets  70 ,  72 ,  74  and  76  can differ and the number of rename and architected registers allocated to each hash may be programmable or dynamically alterable during operation of processor  10 , for example, in response to an on-chip performance monitor  60  detecting a threshold number of dispatch stalls for instructions having addresses within a particular address subset. 
     There are several ways in which the enhanced parallelism of the hashed and partitioned storage subsystem of the present invention can be exploited. For example, a compiler can be optimized to allocate different classes of data, for example, instructions, data, and the instruction page table entries and data page table entries utilized for address translation, to different address subsets. Alternatively, the classes of data assigned to each address subset may be data for different types of applications, for example, technical or commercial. The compiler can also distribute variables accessed by software among the various address to maximize utilization of LSUs  24 . 
     With reference now to FIG. 5, there is depicted a block diagram of an illustrative embodiment of a compiler that implements the optimizations described above. In the illustrative embodiment, compiler  80  includes a scanner/parser  82  that, in response to receipt of an instruction set architecture (ISA) source program as an input, tokenizes the ISA source program and verifies program syntax according to a defined context-free grammar. Scanner/parser  82  outputs a syntactic structure representing the program to translator  84 . Translator  84  receives the output of scanner/parser  82  and generates either an intermediate code representation or target machine code after verifying that the constructs parsed by scanner/parser  82  are legal and meaningful in context. According to the illustrative embodiment, an optimizer  86  receives an intermediate code representation produced by translator  84  and optimizes the location of variables in memory, register utilization, etc., as described above by reference to a hashing algorithm known to be implemented by dispatch unit  44 . The optimized intermediate code output by optimizer  86  is then utilized by machine code generator  88  to produce a target machine code executable by a processor  10 . 
     Alternatively, or in addition to such compiler optimizations, the hashed and partitioned subsystem of the present invention can be exploited by incorporating an awareness of the hashing of memory addresses into the instruction set architecture (ISA) of processors  10 . For example, FIG. 6 illustrates an ISA instruction  90  that, in addition to conventional opcode and operand fields  92  and  94 , includes optional source and destination hash fields  96  and  98 . Thus, a programmer could be permitted, by supplying value(s) within hash fields  96  and  98 , to explicitly direct the compiler as to which address subset source data is drawn and the address subset to which result data is stored. 
     The above compiler and ISA mechanisms for directing data to selected address subsets are particularly advantageous when the hardware partitions having affinity with the various address subsets are individually tailored for the type and amount of data anticipated to be within each address subset. In other words, to enhance performance each hardware partition can be implemented differently from the others. For example, the hardware of some of LSUs  24  can be devoted to execution of only integer loads and stores (i.e., be connected to only GPRF  28 ), while the hardware of other LSUs  24  can be capable of executing only floating-point loads and stores (i.e., be connected to only FPRF  30 ). In addition, certain of LSUs  24  be implemented with duplicate hardware such that multiple load and store instructions targeting addresses within the address subset associated with those LSUs  24  by the hash algorithm can be executed in parallel. 
     Each level of cache can also be heterogeneous. For example, caches of the same type (e.g., L 1  instruction cache, L 1  data cache, and L 2  cache) can be designed or configured with differing sizes, associativities, coherence protocols, inclusivities, sectoring, replacement policies, and prefetch behaviors. Such diversity among caches is particularly useful if different data types are allocated to different address subsets. For example, if the compiler is optimized to assign all locks to a small address subset, the caches having affinity to that address subset can be limited to a small size to reduce access latency and therefore improve system performance on updates to shared data. The “lock” caches may also exhibit a different behavior from caches associated with other address subsets, for example, a store-through (or store-with-update) rather than a write-back protocol, to make the release of a lock visible to other processors  10  via a particular system interconnect  12  in response to execution of a store-conditional instruction. 
     As noted above, the implementation of diverse hardware components of the same type can also extend to system interconnects  12 , and can also extend to memory controllers  14  and system memories  16 . For example, a particular memory controller  14  in FIG. 1 can be implemented with duplicate memory controller hardware operating in parallel, and different memory controllers  14  can access the associated system memory  16  differently to retrieve a requested cache line of data (e.g., horizontal versus vertical slicing of memory). In addition, different system memories  16  can be implemented with differing memory technologies, for example, synchronous dynamic access memory (SDRAM) versus DRAM, differing module sizes, etc. 
     The hashed and partitioned storage subsystem of the present invention also preferably supports dynamic hash optimization and dynamic repair capability. In a conventional processor having only one cache at each level in a cache hierarchy and single instances of other storage subsystem circuitry, the occurrence of a double-bit ECC error in a particular cache or circuit would disable the processor. In contrast, if a double-bit ECC error (which is not correctable) is detected within a particular hardware partition of a processor  10  in accordance with the present invention, the hashing algorithm implemented by dispatch unit  44  can be altered dynamically to redistribute all addresses within the address subset associated with the defective partition to one or more of the other address subsets, thus idling the defective hardware (which may also be disabled). The hashing algorithm implemented by dispatch unit  44  can also be modified to redistribute the subsets to which memory addresses belong while retaining the full number of subsets, for example, to maximize LSU utilization, to improve address bus and/or data bus utilization or to reduce single-bit (soft) errors. 
     With reference now to FIG. 7, there is depicted an exemplary embodiment of a hash selection circuit that supports dynamic changes to the hashing algorithm implemented by dispatch unit  44 . Hash selection circuit  100  includes a number of hashing circuits  102  (one of which may be hashing circuit  50  of FIG. 3A) that each receive certain of the bits of effective address  60  as inputs and provide a hash output designating one of the hardware partitions. As noted above, the hashing algorithms implemented by hashing circuits  102  preferably differ, such that some of hashing circuits  102  hash addresses to fewer than all of the hardware partitions and others of hashing circuits  102  provide different hashes but still distribute addresses among all hardware partitions. The hash output of each hashing circuit  102  forms an input of multiplexer  104 , which selects one of the hash outputs as its output in response to select signal  106 . As illustrated, select signal  106  is derived from the contents of control register  108 , which may in turn be set by either or both of monitoring software and monitoring hardware (e.g., performance monitor  60 ). 
     Once a dynamic update has been made to the control register  108  of a processor  10  within data processing system  8 , coherent operation of data processing system  8  requires that a similar update be performed at each of the other processors  10 . These updates can be handled by sourcing special transactions from the updated processor  10  on system interconnects  12  or by execution of a software exception handler that writes a new value to each other control register  108 . To minimize the performance penalty associated with a dynamic hash update, L 2  caches  34  are preferably implemented such that full addresses are utilized and such that each L 2  cache  34  snoops all address transactions regardless of the address subset to which the address transactions belong. With this arrangement, a dynamic change in the address hash implemented by dispatch unit  44  would require only caches in a disabled hardware partition to be flushed. However, if each L 2  cache  34  only snoops address transactions for its assigned address subset, all LSUs  24  and caches within each hardware partition from which any address is reassigned would have to be flushed prior to enforcing a dynamic change in the hash. 
     As has been described, the present invention provides an improved processor and data processing system architecture having a hashed and partitioned storage subsystem. The present invention not only enhances performance through increased hardware parallelism, but also permits the various hardware partitions to be individually optimized for the type of data contained in each address subset. Advantageously, the address subset assigned to each hardware partition can be changed dynamically by updating the hash, thus permitting runtime optimization and dynamic repair capability. The hashed and partitioned architecture of the present invention is also highly scalable and supports future increases in processor operating frequency through the addition of more hardware partitions. 
     While the invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention. For example, although a compiler in accordance with the present invention can reside within the volatile and non-volatile storage of an operating data processing system, the compiler may alternatively be implemented as a program product for use with a data processing system. Such a program product can be delivered to a data processing system via a variety of signal-bearing media, which include, without limitation, non-rewritable storage media (e.g., CD-ROM), rewritable storage media (e.g., a floppy diskette or hard disk drive), and communication media, such as digital and analog networks. It should be understood, therefore, that such signal-bearing media, when carrying or encoding computer readable instructions that direct the functions of the present invention, represent alternative embodiments of the present invention.