Cache memory.

0001The present invention relates to a cache memory accord­ing to the preamble of claim 1.

0002One of the most important factors in the performance of a high speed, sophisticated computer is the performance of the associated memory system. It is now generally assumed that such a computer system will include the use of a cache memory to facilitate the handling of in­put and output information. It is known that the larger the capacity and the faster the speed of operation of a cache memory, the better the overall performance of the computer system.

0003The prior art shows various efforts to improve the per­formance of cache memories. These efforts have included the use of multiple cache memories in various organiza­tional relationships. For example, the use of separate cache memories for instructions and for data is known. Other cache designs use two caches in parallel in an odd-even interleave design so that memory access time for information from the cache for a string of data is improved. Other cache designs use different size caches in a hierarchical arrangement. Some of these cache de­signs are intended for use with more than one process­ing element or execution unit so that several different cache accesses may be initiated in a short time interval.

0004One of the difficulties typical of these prior art de­signs is that when a cache request is made, the cache must perform a search to determine if the information is available. If the cache access is successful, the information is provided to the requesting unit. If the information is not available, a cache miss routine is followed which summons the requested information from another level of memory while the requesting unit either waits or does something else. In most cache designs there is a significant time penalty if a cache miss oc­curs and the design is optimized so that cache misses are infrequent.

0005In the prior art, a multiprocessor environment has typ­ically provided a separate cache memory for each proc­essor. However, it is expensive and inefficient to pro­vide an independent cache for each processor when a common main memory is used. In addition, if more than one processor needs to use the same information, man­agement of multiple copies of information in different caches is difficult and complex. However, the prior art suggests a preference for managing multiple shared and/­or independent caches in a multiprocessor environment compared to the complexity or the inefficiency of man­aging a single cache in a multiprocessor environment. This is disclosed in the following prior art: U.S.A. patent number 4,169,284 entitled "Cache Control For Concurrent Access", assigned to the same assignee as the present invention, shows a cache memory control which provides two cache access timing cycles during each pro­cessor storage request cycle. Although this cache allows more than one access per cycle it represents a time in­terleaved cache and not a true simultaneous access cache.

0006U.S.A. patent number 4,371,929 entitled "Multiprocessor System with High Density Memory Set Architecture Includ­ing Partitionable Cache Store Interface To Shared Disk Drive Memory", assigned to the same assignee as the pre­sent invention, shows a cache memory with storage part­itions functioning on a time interleaved basis.

0007U.S.A. patent number 4,441,155 entitled "Page Controlled Cache Directory Addressing", assigned to the same assignee as the present invention, shows a cache addressing control system to reduce the cache miss rate.

0008U.S.A. patent number 4,442,487 entitled "Three Level Mem­ory Hierarchy Using Write And Share Flags", assigned to the same assignee as the present invention, shows differ­ent levels of cache and cache separated into private and shared cache systems. The private and shared cache systems are primarily separate caches with switching mechanisms between them and are not separate portions of the same cache. This design is intended to allow multiprocessor systems to share a memory facility without having the cross-interrogation requirements that would otherwise be necessary.

0009U.S.A. patent number 4,463,424 entitled "Method For Dy­namically Allocating LRU/MRU Managed Memory Among Con­current Sequential Processes", assigned to the same as­signee as the present invention, is a cache management system for separating a cache memory into partitions of allocated space based on the requirement of the process using the cache memory. The partitions are allocated by a supervisory process and are not physically deter­mined.

0010U.S.A. patent number 4,464,712 entitled "Second Level Cache Replacement Method and Apparatus", assigned to the same assignee as the present invention, treats a cache memory system as consisting of separate subsets of pages which are associated with a replacement flag mechanism to control access for replacement of cache contents.

0011U.S.A. patent number 4,484,267 entitled "Cache Sharing Control In A Multiprocessor" assigned to the same as­signee as the present invention, is a multiprocessing environment where each processor has a private cache. Each cache has a directory containing a sharing flag to control whether the associated cache line operates in a store-through or a store-in mode. This creates two dif­ferent types of cache operating modes for use in hand­ling both normal cache accesses and the cross-interrog­ation process with other caches.

0012There are other patents of interest in this field. U.S.A. patent number 4,503,501 shows cache memory space part­itioned into domains by a supervisory control system. U.S.A. patent number 4,493,033 shows a dual ported cache operating in a time interleaved manner. U.S.A. patent number 4,195,342 shows another dual ported interleaved cache arrangement. U.S.A. patent number 3,618,041 is an early patent showing segregation of instructions and operands into different caches. U.S.A. patent number 4,502,110 is a split cache having equal size operand and instruction memories.

0013IBM Technical Disclosure Bulletin, Vol. 22, No. 2, July 1979, pages 851 and 852, entitled "Partitioned Memory And Split SCE For Asymmetric Multiprocessor" shows an electronic fence under supervisory control for separat­ing a memory into two sections and restricting access to one of the two sections.

0014There is a continuing need for improvements in cache mem­ory design, particularly for cache designs that may be used to handle a large number of requests in a short time interval or essentially simultaneously.

0015The solution is an improved cache memory system which is described in the characterizing part of claim 1.

0016Further solutions and improvements are described in claims 2 - 20.

0017This improved cache memory offers particular advantages in an environment having multiple processing elements or multiprocessors but does not require or depend upon such an environment to display its advantages.

0018Multiprocessing in the context of a single CPU involves multiple instruction processing units and multiple ex­ecution processing units. In order to reduce the time required to execute an object program, it is desirable to process multiple instructions from that program in parallel, which then invoke multiple execution units in parallel. This practice involves multiple instruction decoders, parallel instruction streams, and "out-of-se­quence" executions. Since both the instructions and data operands are usually requested from cache, it is desirable to provide multiple cache ports and multiple, independent cache operations during a single CPU machine cycle.

0019The cache memory according to the invention is an M sect­ioned or partitioned cache where M is preferably a power of 2 such as 8. The cache is capable of performing one event per partition per cycle or M events per cycle. The cache has N ports where N is equal to or less than M. N is machine specific but is usually less than M and fact­orable by 2. The embodiment discussed in this applica­tion is a cache with eight partitions and six ports be­cause these seem to be realizable and useful design fact­ors considering the appropriate measures of design com­plexity and performance improvement. The number of part­itions is not limited to 8 and may just as well be 4, 16 or 32. The cache is controlled using a partition look-­aside table (PLAT) which identifies the correct partition to access for information when a request is sent to cache.

0020Each cache partition operates independently and in paral­lel. Each partition may execute a store or fetch opera­tion on each machine cycle. Address switches, data bus switches and special control systems are provided so that any partition may be connected to any port. Thus, mult­iple combinations of partition to port connections can be controlled for each cycle so that the cache may execute a combination of N stores and fetches at each cycle. The cache is designed so that the number of partitions is equal to the number of set-associative bins in the design. The cache data placement is such that all data convention­ally allocated to a particular bin is also allocated to a corresponding real partition. That is, a cache line is fully contained within a single partition. Thus, a pro­cessor with multiple execution units may perform several stores or fetches at the same time when those requests are directed to different cache partitions.

0021A PLAT (partition look-aside table) controls the cache and stores a set of the more recently accessed cache line requests together with a partition assignment iden­tifier for the line address. Multiple PLAT's can be pro­vided for instruction requests and for operand requests.

0022Using the stored information, the PLAT directs machine produced addresses to the correct cache partition when it is determined that the information resides in cache. A miss in the PLAT does not mean a cache miss as that term is generally understood. If the partition informa­tion is not in the PLAT, the cache request is directed to all partitions and the cache directory simultaneously using a global request. If the information is found in cache as a result of a global request, the PLAT is updat­ed with the line address and partition identifier. If the information is not found in cache, a known cache miss routine is used, such as, use of a Directory Look-Aside Table (DLAT) and an access to main memory or a higher level of cache.

0023The cache miss-control-logic has, in part, an LRU (least recently used) algorithm which determines the location, or for this cache the partition number, in which to load the new line fetched from the higher level storage hier­archy. In this way, new cache lines are rotated to all partitions on a least-recently-used basis.

0024The embodiment of a partitioned cache shown here is re­ferred to as an L1 cache which is a private processor cache. An L2 or L3 cache is larger and closer to main memory than an L1 cache and may be shared. This L1 cache does not first execute a cast-out of the old line prior to the new line load operation since a store-thru L1 cache is implemented. That is, all store requests are sent to L1 and to at least one higher level of the stor­age hierarchy. Loading new line data into the cache re­sults in just one of M partitions being busy. <ul id="ul0001" list-style="none"><li>FIGURE 1 is a system diagram of a computer system having multiple central processing units incorporating a part­itioned cache according to the present invention ensuring a common storage hierarchy.</li><li>FIGURE 2 is a schematic diagram of an embodiment of a partitioned cache memory according to the present in­vention.</li><li>FIGURE 3 is a more detailed showing of the cache arrays, directory, address, data, and control busses of the part­itioned cache shown in FIGURE 2.</li><li>FIGURES 4A, 4B, 4C and 4D are in left to right order and show a detailed diagram of the control bus structure as­sociated with the partitioned cache memory shown in FIG­URE 2.</li><li>FIGURE 5A is a showing of the relationship of the direct­ory and partition structure in a cache memory according to the present invention as shown in FIGURE 2.</li><li>FIGURE 5B shows the organization of one of the address ports comprising the address bus shown in FIGURE 5A.</li><li>FIGURE 6 is a detailed showing of one of the fetch ports of a cache memory according to the embodiment shown in FIGURE 2.</li><li>FIGURE 7 is a detailed showing of an embodiment of a CPU store port according to the cache memory of FIGURE 2.</li><li>FIGURE 8 is a detailed showing of the PLAT structure of the cache memory shown in FIGURE 2.</li><li>FIGURE 9 is a showing of a schematic diagram of the structure of a data field in the instruction type PLAT according to the present invention.</li><li>FIGURE 10 is a showing of another structure of a data field in the data type PLAT according to the present in­vention.</li><li>FIGURES 11A and 11B are in left to right order of a show­ing of a partitioned cache directory and partitioned cache data array according to the present invention and operation with a single cache partition.</li><li>FIGURES 12A, 12B and 12C are each a detailed showing of different embodiments of the address structure of a part­itioned cache memory according to the present invention.</li><li>FIGURE 13 is a detailed showing of a fault tolerant structure for identifying and shutting off faulty part­itions according to the present invention.</li></ul>

0025Referring now to FIGURE 1, a computer system 10 is shown which contains multiple central processing units 12, 14 and so forth to unit 16. Each of the central processing units has an input and output connection to a system control element 18. The system control element 18 is connected to a L2 (level 2) memory or storage hierarchy 20 which in turn is connected to successive levels of storage hierarchy L3 which is labeled 22 and L4 which is labeled 24. Each of these levels is pro­gressively larger in capacity and further from the pro­cessor. The object is to have instructions and data as close to the central processing units as is possible for the size of memory involved. The use of multiple storage hierarchies in computer systems is known. The showing of these levels is illustrative of design prac­tice and not a particular requirement of the partition cache. The system control element 18 also has various channels 26, 28 and 30 which serve to provide connect­ions to the input-output devices which may be terminals, printers, disk-drives and the like.

0026Each central processing unit will contain instruction and execution hardware labeled generally 32, and hard­ware fault test logic labeled generally 40. The in­struction and execution hardware 32 allows each central processing unit to perform conventional kinds of computer operations. Associated with the central processing unit is a L1 (level 1) cache memory system which will be a partitioned cache memory 34 according to the present in­vention. Such a cache 34 contains M partitions of memory and is connected by data paths 36 to the instruction and execution hardware unit 32. Up to N data paths 36 may be used depending on the optimum data flow requirements intended for the instruction and execution unit.

0027A directory 38 is provided to facilitate finding informa­tion in a storage hierarchy which is called for by the instruction and execution hardware 32. Directory 38 is connected by control paths and data paths 39 to the in­struction and execution hardware 32.

0028The hardware fault test logic 40 monitors the address, data and control paths to and from the I to E hardware, directory and cache. Should a failure occur in any of these paths, a fault latch associated with a particular failure may be set for diagnostic, recovery, or otherwise corrective actions.

0029The other central processing units connected to the same system control element 18 will have similar internal structures providing for instruction and execution, a lo­cal partitioned cache memory, and an appropriate direct­ory to access the contents of the storage hierarchy.

0030Referring now to FIGURE 2, the structure of a partition­ed cache and PLAT according to the present invention is shown. A cache memory having M cache partitions 50 is shown. In this case, for convenience, eight cache part­itions are shown in this particular embodiment. This appears to be an appropriate number for many purposes to provide a manageable level of control as well as provid­ing the advantages that may be obtained in a partitioned cache memory.

0031The various cache partitions 50 are connected by a data bus switch mechanism 52 to N data bus ports. In this case, six data bus ports are used because it appears to be an appropriate number to work effectively with a cache memory having eight partitions and for the requirements of the hypothetical processor with which this system will be used.

0032The data bus switch 52 is under the control of an input control bus unit 54 which provides appropriate switching control signals for the data bus ports. The cache also has an output control bus unit 56 which controls the output data bus structure. The input control bus unit 54 is con­nected to an input address switch 58 which assigns request­ed addresses to the appropriate partitions under the con­trol of an address request bus 60. The input control bus unit 54 is also connected to the data-bus switch 52 which assigns the data-bus ports to the addressed partition.

0033Input control bus unit 54 is connected with two control busses 62 and 64. Control bus 62 is the C1 bus which handles global requests of the cache unit. A global re­quest of the cache unit is one which is directed to all partitions of the cache simultaneously. This will be ex­plained in greater detail later. Control bus 64 is the C2 bus which handles local requests of the cache unit which are directed to a specific selected partition. These lo­cal requests of the cache unit will be explained in great­er detail later.

0034Output control bus unit 56 is connected to the C3 bus 66 which handles local output control signals from the cache. The significance of the local output requests will be ex­plained later but it may be observed that since any con­tents of the cache reside in a specific partition, only specific partitions will be producing output requests and therefore all output requests are local and cannot be glo­bal.

0035Each central processor unit (CPU) will have various arith­metic and logic units associated with it. In FIGURE 2, a central processor unit having various elements 70, 72, 74 and 76 is shown. These units may be of any type desired and they consist of various combinations of arithmetic, logic or instruction processing elements. Each of the data busses from the data bus switch 52 is connected to this group of central processor units through a combina­tion of fetch buffers and store buffers to provide the plurality of input and output data paths to the central processing units. Thus, in a case where six data busses are proposed, three of the data busses may be connected with fetch buffers 80, 82 and 84 while two of the busses are connected to store buffers 86 and 88. All of these buffers are connected to the central processing unit and its various elements.

0036The central processor generates requests for the memory hierarchy to a plurality of address generating mechanisms 90, 92, 94, 96 and 98. The address generating units are connected to an associated PLAT so that the central pro­cessor has a plurality of PLAT units 100, 102, 104, 106 and 108. Addresses generated are placed on an address bus for each address generating mechanism on the address request bus 60 as well as to the associated PLAT. Each PLAT when it receives an input address may generate a global request of the partitioned cache on the C1 bus or a local request of the partitioned cache on using a se­lected one of the C2 busses.

0037The PLAT's each have an input bus from the output con­trol bus unit 56 containing local input control signals. In general, when a central processor logic unit, such as logic unit 70 makes a request of memory, the address generating unit such as 90, produces an address request on the address request bus 60. This request goes both to address switch 58 and to the PLAT 100. If the PLAT can identify the partition of the cache in which the re­quested information is located, a request on the local request bus 64 is generated to the input control bus unit 54. This causes the address switch 58 to direct the re­quested address only to the particular partition in the cache containing the requested information. The data-bus switch out 52 is then switched to provide the requested information from the particular partition in which it is located to the particular requesting unit for which the information was obtained. In the case where the PLAT cannot identify a particular partition, the global re­quest bus 62 is activated and the address switch provides the address to all partitions of the cache memory.

0038A line fetch buffer 110 is provided so that if requested information is not in the cache 50, a request may be passed to the next level of memory in the hierarchy for the requested information. The line fetch buffer there­fore is connected to one of the data bus ports of the cache, and in this example, is shown as being connected to the Nth or last port. The line fetch buffer is also connected to the address request bus 60 and to the con­trol bus 64 or control signals. The data bus from the next level of storage hierarchy is shown schematically at 112. It is important to note that the line fetch buf­fer 110 only requires access to a single selected cache partition when storing the contents of the line fetch buffer into cache. The other cache partitions may oper­ate normally when the line fetch buffer is storing into cache. See FIGURE 13 also.

0039Generally, the operation of the system shown in FIGURE 2 may be described in the following fashion.

0040The cache is divided into a plurality of sections or part­itions and each partition operates independently and in parallel with the others. Each partition may execute a store or a fetch operation on each machine cycle. Address switches 58, data bus switches 52, and the appropriate control systems are provided so that any partition may be connected to any input or output port. Thus, multiple combinations of partition and port connections may be activated during a single cycle of memory operation. This permits the cache to execute a combination of stores and fetches in a single machine cycle equal to or less than the number of ports.

0041The number of partitions is equal to the number of set-­associative bins chosen for the cache design. The cache data placement is such that all data conventionally al­located to a particular bin is now allocated to occur corresponding to a physical partition.

0042The partition look-aside table (PLAT) is incorporated in­to the processor design. The exact logical and physical placement of the PLAT is as to the designer and may de­pend on machine organization. One appropriate location for one or more PLAT's is close to the address generating hardware in the processor. Multiple PLAT's can be used for handling a typical central processor organization. For example, one type of PLAT may be ideally designed for handling instruction requests and another type may be used for data operand requests. Multiple copies of either type may be used, individually, by the CPU logic units.

0043The PLAT's will store a set of most recently accessed L1 line addresses together with a partition identifier for each such line address. The PLAT's will then direct ma­chine generated addresses to the correct L1 cache part­ition in a high percentage of the L1 cache access re­quests. Such requests are called local requests and use the local control line bus 64. A PLAT miss will require that the generated address be directed to all partitions simultaneously to determine the partition allocated to the corresponding L1 line. In this case, the global con­ trol line bus 62 will be used. At this time a new entry is made in the PLAT's storing the line address and part­ition identifier, subsequent store or fetch requests to the same L1 line will be directed to the correct part­ition until the entry is aged from the PLAT.

0044Ideally the best performance from a partitioned cache memory according to the present invention would result with the number of ports equal to the number of part­itions, and if each port was connected with a partition on every excess cycle. However, physical constraints such as the number of input and output connections per memory array chip may limit the maximum number of ports.

0045There is a direct correspondence between address ports and data ports. That is, address port 1 is connected to address switch 58 which is provided for data port 1 which in turn is connected to data bus switch 52 and so forth. These port pairs are fixed in the hardware. Fur­thermore, each data port is either a fetch port or a store port when uni-directional bus drivers are used. With duplex drivers and data switches at the CPU ports, each port may serve as both a fetch and a store port. However, for purposes of this description, the ports are described as one directional ports either as fetch ports or store ports.

0046As stated before, the address switch may function in either the global request mode or the local request mode. A global request causes one of the addresses presented to the address switch to be presented to all the partitions of the cache simultaneously. Thus, the address is switched simultaneously to all directory elements and all cache memory partitions. This is based on control of the global control bus 62. The global control cycle executes as with a conventional cache in the sense that, if the data is valid in the cache, one of the eight directory elements will compare positive and raise a selected gate to the corresponding cache partition. This output is then switched to the requesting data port bus. One global request may be executed in a single machine cycle.

0047A local request causes an address to be switched to the selected one of the M cache partitions and the directory is not used for the handling of the local requests. During a single machine cycle as many local request ad­dresses may be switched to the cache partitions as there are ports to the cache memory. This is dependent upon each of the local request addresses being to a different partition so that each of the partitions which are ad­dressed may be uniquely connected to a single port. Mul­tiple requests to the same partition on consecutive ma­chine cycles are allowed. The input control busses 62 and 64 determine for each individual address port whether the requesting address is a global request or local re­quest and which port is accessed. If the request is a local request, the control bus 64 codes the partition identifier for the target cache line.

0048The data bus switch 52 is used to switch the outputs from the partitioned cache arrays 50 to the data bus ports for fetch requests, and to switch inputs from the data bus ports to the partitioned cache arrays for store requests. Whenever the requesting address is a global request, in­dicating a PLAT miss, and the data is actually found in the cache, in addition to returning the requested data to the CPU, the partition identifier is also returned to the CPU on the control bus 66 so that the PLAT adds that in­formation to its array. A new entry is created in the PLAT storing both the target cache line address and the partition identifier. Subsequent references to that cache line will result in PLAT hits and local requests.

0049In this example the cache has N direct access ports where N is fixed at the number 6 and the central processor unit is assigned N-1 direct access ports to the cache. Thus, the processor has one less port accessing the cache than the cache has ports. In this case, the processor is as­signed five direct access ports to the cache. The last port is reserved for put-away operations of the line fetch buffer 110. For the case of a unidirectional buffer, each port is either a fetch port or a store port. In this ex­ample, ports 1, 2 and 3 are assigned to fetch buffers 80, 82 and 84 and ports 4, 5 and 6 are assigned as store ports to store buffer 86, store buffer 88 and the line fetch buffer 110. Each port is terminated at the CPU with fetch or store buffers. These buffers may vary in size depending on their optimum design and the bus transfer size, for ex­ample, 8 to 512 bytes.

0050The individual subdivisions of the CPU are symbolic and are intended to portray the CPU design in which many operations are executing in parallel and therefore re­quire multiple accesses per cycle to the cache to reduce the average cycles per instruction. One or more of the subdivisions may be thought to be an instruction process­or, a fixed point arithmetic unit, a floating point arithmetic unit, a vector processor, and so forth to illustrate various possible computer functions. The best allocation of cache ports to a CPU function, is based on CPU design optimization, including the optimum mix of store and fetch ports to total the number of provided ports to the cache.

0051Each central processor subdivision such as 70, 72, 74, and 76, in addition to its processor function have the hardware capability to generate an address when cache data is needed for instruction fetches, operand fetches, or operand stores. This is indicated by the provision of address generating units 90, 92, 94, 96, and 98. The address generation may result from incrementing a count­er, reading an address from an array stack, taking the result from an address generating adder and so forth. After the address is provided, the address is placed on the address request bus 60 where it is provided to the local PLAT, such as PLAT 100, 102, 104, 106 or 108 as well as to the address switch 58 and to the line fetch buffer 110. The line address is tested in the local PLAT. If a PLAT miss occurs, the PLAT places a bit on the global control bus 62 to indicate a global request for that PLAT. If a PLAT hit occurs, a bit is placed on one of the positions of the local request control bus 64 to indicate the partition to which that address should be directed. The placing of this bit on the position of the local control bus indicates both the presence of the local request and identifies the partition for the re­quested data in the cache.

0052Although, the system in FIGURE 2 provides one PLAT for each CPU logic unit, a variety of PLAT arrangements are possible, depending on the design requirements. It may be desirable to have different types of PLAT's for dif­ferent types of functions. Each type may then be re­plicated at each CPU logic unit which performs that function. For example, one type is ideally provided for data operand fetches and stores. Each type may then have multiple copies strategically located in the CPU logic partitions. Each PLAT is a small register array with, for example, (1-4) comparators, and duplication of hardware is not difficult due to the comparatively small amount of hardware required for each PLAT. Multiple comparators may be provided since a "set-associative" arrangement of the PLAT arrays improve their performance.

0053FIGURE 3 shows the embodiment of the partitioned cache 50 of FIGURE 2 in greater detail. The global bus 62 services ports 1 through 5 of the central processor. Each bit of the global control bus indicates the requesting unit of the central processing unit. Bus 62 does not have a glo­bal position although it could have, since the put away of the line fetch buffer is always a local request which knows the correct cache partition to access; based on LRU logic. Each PLAT type has a local control out bus C3 shown schematically at numeral 66. This description in­dicates one type for instruction addresses and a second type for data addresses. Each may have multiple connect­ions to multiple PLAT copies. This control bus 66 returns the partition identifier, determined by a global directory search, to be stored in the particular PLAT's for a new entry. Port 6 is shown in FIGURE 2, and is used for line put away and does not use a local C3 output control bus because it receives its partition identifier for store re­quests from the least recently used (LRU) control system, shown in more detail in FIGURE 13. The output control bus C3 also includes a valid store line to be described later. Also indicated in the figure is the internal structure of the partitioned cache. Each partition in­cludes an address switch, a partition directory, the act­ual cache memory array and data bus switches.

0054Referring now to FIGURES 4A, 4B, 4C and 4D, each of the eight cache partitions of the cache memory 50 as shown in FIGURE 2 is shown with its directory array, and memory stack elements and directory elements are shown connected to the control bus structure. The address and data busses are not shown in this figure but are shown in greater de­tail in other figures. All the lines of the global control bus in 62 are directed to all eight of the directory ele­ments, DIR.1 through DIR.8. The local control bus C2 is broken into six component groups of control lines, each component having one line for each memory stack. Thus, the component lines of the local bus in 64 are each directed to a target partition memory stack of the memory array.

0055The lines of the local control bus out 66 are derived from a register in each of the directory elements. In this description, the register has three bits which have the following functions: Bit 1 is a partition identifier to indicate an instruction type PLAT; Bit 2 is a partition identifier to indicate a data type PLAT and Bit 3 is a valid store indicator line. The reg­isters for the directory elements may have other compositions and functions as necessary in the memory structure. The local output busses for each bit in the register in the directories have a unique line so that the particular cache partition directory originating a signal can be identified. The local output busses thus receive the partition identifier bit resulting from a global request and the valid store (V/S) line if the store interrogate of the directory element is positive. Note that the store interrogation operation and valid store line generation is performed for both global fetch and global store requests. The store interrogate operation involves testing various control bits in the directory such as the valid bit, exclusive bit, storage key bits, etc.

0056Referring now to FIGURE 5, the cache address bus 60A is connected to each of the eight partitions of the cache 50 according to the present invention.

0057Similarly, the output data busses D1, D2, and D3 as well as the input data busses D4, D5 and D6 are connected to fetch or store data from or into any partition. Each partition has a separate directory element which may, for example, be on a stand alone associative array chip. Both the directory and cache partitions have address switches whereas just the cache partitions have data bus switches. The various address switches for the various partitions are shown schematically.

0058For example, partition 1 of cache 50 has an address switch 150 connected to the address bus 60A. Data bus switches 152 and 154 are also associated with the first partition. The directory element associated with the first partition has address switch 156 connected to the directory address bus 60B. The other cache partitions and directory elements are similarly organized. Note that the address bus 60 of FIGURES 2 and 3 is composed of two parts, address bus 60A and 60B of FIGURE 5B. Each port of address bus 60 is composed of three fields as shown in FIGURE 5B. The directory 38 requires the mid and high-order bits from each address port; whereas the cache requires the mid and low-order bits from each address port.

0059Referring now to FIGURES 6 and 7 two different embodi­ments of central processing ports are illustrated for use with the present invention. In FIGURE 6, a central processor port 200 is shown which may be used as a fetch port for either instructions or for data operands to be executed. The port contains a PLAT 202, an ad­dress request logic unit 204, a central processor in­struction, logic, or arithmetic unit 206, an input buffer 208 and it may contain a local store 210. The PLAT has its C3 local output control line 212, its C1 global control line 214 and its local C2 input control line 216 shown together with the number of bits re­quired for the operation in each case. The address gen­eration unit 204 produces 27 bit addresses and the buffer unit 208 is designed to receive 144 bit quad­word at a time.

0060In FIGURE 7, the CPU port 220 is configured as a storage port having a PLAT 222, an address request logic unit 224, a CPU logic unit 226, a data buffer 228, and a lo­cal store 230. Again, the PLAT has a C3 local output control line 232, a C1 global output control line 234 and a C2 local input control line 236. In addition, the PLAT has a valid store (V/S) line 238. Buffer 228 is de­ signed to handle quadwords of 144 bits. The valid store line 238 is input to PLAT 222 so that when the port issues a store request, the valid store condition can be determined at the PLAT.

0061Referring now to FIGURE 8, the logic operation of a PLAT is illustrated. The C3 local output bus 302 emerges from a switching gate system 304 while the C2 local input control bus 306 is connected to a gate 308 and the C1 global control bus 310 is connected to a gate 312. A central processor unit 320 has an address generation mechanism 322 which provides addresses on an address bus 324 to the partitioned cache and also to the PLAT on bus 326. The address is provided to a comparator 328 which records either a hit on line 330 to gate unit 308 or a miss on line 332 to gate unit 312 depending upon whether a miss or a hit in the PLAT is recorded, the global con­trol signal is sent on C1 line 310 or the C2 local con­trol signal is sent on lines 306 showing the location in the partitioned memory found by the PLAT.

0062In the normal course of operation, the CPU 320 will in­voke its address generation hardware 322 placing the re­questing address on the output address bus 324. At the same time the address is sent to the PLAT 300 where one or more addresses of that congruence class are read from the PLAT array. The remaining high order bits of the address are compared for each PLAT set associative entry.

0063A PLAT hit will cause one of eight bits stored in the partition identifier array field of the PLAT to be out­gated to the corresponding one of eight positions of the C2 control bus 306. This indicates a local request to the designated cache partition.

0064A PLAT miss will raise the single bit C1 global request line on bus 310. A PLAT miss will also enable the gates which store the requesting address and the partition identifier which is returned on the C3 control bus 302. A new entry is thus created in the PLAT in response to a global request. This new store entry in the PLAT is invoked by new store box 334 when it gets a miss indica­tion from line 332 and it is able to place the address it receives from 324 into the address array of the PLAT 300.

0065In general the PLAT array 300 is a set-associative array. Multiple sets, Set A, Set B etc., are examined in paral­lel for each congruence address. Each set compartment of the PLAT has an individual set of output gates 308, address compare 328, global gate 312, input gates 304 and 334. The output gates 308 are "OR'ed together" since just one congruence address may hit on a PLAT cycle. In a similar manner, the outputs 310 from each set gate 312 are combined to form a single C1 request line. In this case, the outputs 310 are AND'ed together since a miss must occur from all set-associative compara­tors before a global request C1 is initiated on bus 310. On the input side of the PLAT, the address bus 326 and control bus 302 may be gated to any one of the set-asso­ciative compartments, to Set A or to Set B, etc., as de­termined by the LRU logic when a new PLAT entry is crea­ted.

0066FIGURE 9 shows the type of PLAT entry data field which might be used for a PLAT design to deal with instruct­ions. An address field 400 contains addresses while a partition identifier 402 shows the partition of the cache containing that address. A control field 404 is provided which contains a valid bit field 406 and a field 408 for parity and other miscellaneous control functions.

0067FIGURE 10 shows the type of PLAT entry which might be used for a data type of PLAT. An address field 400 is provided together with a partition identifier field 402. However, the control field 412 may be slightly different. A valid bit entry 406 is provided, and a valid store bit 414 is also included. In addition, an additional field 416 is provided for parity and other miscellaneous con­trol functions as before. The PLAT type shown in FIG­URES 9 and 10 is intended for possible operation in the presence of an expanded central processing unit CPU buf­fer which might take the form of a local cache (L0). In this case, the directory for the local cache and the PLAT may operate in parallel. After the address generate function occurs, the address is sent to the address re­quest bus, the PLAT, the local cache directory, and the local cache array.

0068A hit in the local cache directory causes data to be out­gated from the local cache array to the associated cen­tral processing element and the other address paths are to be disregarded. A miss at the local cache directory combined with a hit in the PLAT results in a local re­quest to the L1 partitioned cache. A local directory miss combined with a PLAT miss results in a global request to the partitioned cache.

0069The difference between the two types of PLAT entry shown in FIGURES 9 and 10 is the presence of the valid store bit 414 in the data type PLAT entry. This bit is set to be on at the time that a new entry is created in the data type PLAT, which will be after a global request. At this time a store interrogate operation is executed at the partitioned cache directory. This involves testing the storage keys, valid bit, exclusive bit, and other func­tions in the cache. If this test is positive, then the valid store bit in the partitioned cache directory is set on for that new entry in the data type PLAT, otherwise it is set off. Any subsequent store request to that part­itioned cache line while the entry remains valid in the PLAT, executes as a single cycle store. Such stores are transmitted as local store requests to the partitioned cache. Note that any invalidate issue to the partition­ed cache is also issued to the associated PLAT.

0070Referring now to FIGURES 11A and 11B which are viewed in left to right order, a partitioned cache is shown with its control and data flow paths. A directory partition is associated with a single cache array partition 502 shown with its stack of memory locations. A cache priority gate 504 receives the C2 local control bus 506 and C1 global control bus in 508, also shown in FIGURE 4A. The output of priority logic 504 is input to OR gates 510 and 512 as well as to read gate switch 514 and write gate switch 516. An address bus switch 518 receives an input from priority logic 504 and directs addresses to the cache array partition 502. The output of OR gate 510 is a write gate select bus 520 and the output of OR gate 512 is a read gate select bus 522. OR gate 510 receives an input 560 from directory 500 and OR gate 512 receives an input 558 from directory 500.

0071Cache directory 500 receives an input address bus 60B through an address bus switch 542. The address bus switch 542 is controlled by priority gate 544 which has as in­put, the C1 global control bus 508. Priority gate 544 also provides an output to gates 548 which have as an output the input control signals for the C3 local bus 550 which is connected to the associated PLAT. The output of the cache directory array 500 consists of a data out bus 552 and inputs to logic units 554 and 556. Units 554 and 556 produce a valid read output bus 558 and a valid write output bus 560 respectively.

0072To illustrate the operation of cache partition 502, prior­ity logic unit 504 receives control bus inputs 506 and 508. If a local request is determined on the basis of C2 con­trol input 506, one of six addresses is switched from the address bus to the cache array by address switch 518. The data bus which corresponds to the selected address is also selected by bus select control line 530 for read opera­tions or bus select line 532 for writing operations. The read gate select line 522 or the write gate select line 520 are also enabled by the priority logic for local read and write requests. Thus, a cache partition may execute a single cycle store or fetch operation without use of the cache directory. For fetch operation, the second clock cycle cache operation is used to transfer the requested data to the requesting central processor element. For store operations, the second cache cycle is not required.

0073If a global request is determined, the priority logic of the cache array 544 and the directory 500 select and switch a common address using switch 542. The cache array will likewise select the corresponding address bus with switch 518, as before, but in this case will not generate the read or write gate control lines 522 and 520 respect­ively. Instead, these lines are generated from the com­ pare and test logic 554 and 556 of the directory 500. In the global case, the valid read line 558 enables the selected read gates to the selected data bus. The valid write line 560 enables the selected write gates such that the cache array 502 may execute the store operation on the following cycle. Thus, for a global request the first cycle of cache operation performs the array access and data bus switch for a fetch, and a store interrogate function for a store request. The second cycle of cache operation is used to transfer the requested data for a fetch or to cycle the cache array 502 for the store re­quest. For global requests, the partition identifier and valid store lines are generated by gates 548 and returned on the C3 busses to update the new PLAT entry.

0074Global requests have a higher priority than any local re­quest. Priority for both global requests and local re­quests will be determined by a predetermined sequence of port positions.

0075For simplicity, a small PLAT array is illustrated in FIGURE 12, one which can store eight entries each with contents as illustrated in FIGURES 9 and 10. In cache array terminology this array has eight congruence class address positions, and one set associativity, Set A. This array has dimensions (8×1). Larger PLAT arrays may be constructed by replicating the components of FIGURE 12. Each replication in the horizontal direc­tion adds eight additional entries and one additional set; i.e. Set B (8×2), Set C (8×3), etc. Alternatively, each replication in the vertical direction adds eight additional entries, thereby increasing the congruence class addresses by eight while retaining a single set associativity, Set A. Such an array has dimension (16×1).

0076If, for example, 32 entries were determined to be an optimum number, the PLAT array could be arranged: (8×4), (16×2), or (32×1). In any chosen arrangement of the PLAT, the required number of comparators, 636 of FIGURE 12, is equal to the set associativity, one per set.

0077Also referring to FIGURE 12, the address generator 600 provides a decoded set of address lines 602 to the PLAT, the number of decoded lines are determined by the number of congruence classes. The address bits used to decode the congruence class select lines are determined by the partitioned L1 cache line size, and are the "lowest-order" bits of the portion of the address normally used to address the L1 Directory, Address Bus 60B of FIGURE 5. For a PLAT with eight congruence classes, three lower-­order bits are used to decode eight congruence class select lines, four low-order bits to decode sixteen, etc. In cases where the generated address is obtained from an AGEN adder, the AGEN adder may generate the decoded form of the congruence class select bus 602 directly, rather than generating the encoded form which would then require the decode operation.

0078Referring to FIGURES 12A and 5, the working of a PLAT is shown. Address generator 600 creates the requested address 664 and sends certain of these address bits to the cache on cache address bus 60A, to the directory on directory address bus 60B, and to the address compare circuit 636. Also, in parallel, address generator 600 sends the eight bit congruence line select bus 602 to the PLAT. For any requesting address just one of eight lines of bus 602 is active. Depending on the active line, one of eight addresses from PLAT entries 604, 606, 608, 610, 612, 614, 616, or 618 are gated to a common bus 662 to the compare circuit 636. Gates 620, 622, 624, 626, 628, 630, 632, or 634 perform the address gating. An equal comparison of the generated address 664 with the selected address 662 results in a positive hit on output line 640. Line 640 then provides a signal to gates 642, 644, 646, 648, 650, 652, 654 and 656 which combine with congruence lines select bus 602 to out-gate one of the partition I/D fields from the PLAT entries 604, 606, 608, 610, 612, 614, 616, or 618 to the common bus 660. The bus 660 is then sent to the partitioned cache as one of the local-in C2 components of control bus 64 of FIGURES 4A, 4B, 4C and 4D. An unequal comparison of compare circuit 636 results in a miss signal 638 on the C1 global request bus. The signal line 638 is sent to the parti­tion cash and directory as one of the global-in C1 com­ponents of control bus 62 of FIGURES 4A, 4B, 4C and 4D.

0079FIGURE 12B is a variation of FIGURE 12A and is used for any CPU port assigned as a fetch port for instructions or data operands. Here, the valid bit, in addition to the address field, is gated from the PLAT entries 604 through 618 by gates 620 through 634 to common bus 662. The compare circuit 636 examines the valid bit input line in addition to performing the address compare as before. If the valid bit is yes, or valid, (cache conventions usually use the up or one state for invalid and the down or zero state for valid), then compare circuit 636 deter­mines a hit on line 640 or a miss on line 634 based on the address compare operation as before. If the valid bit is no (invalid) then the miss line 638 is forced and the address compare operation is ignored.

0080Whenever a new entry is created in the PLAT, the valid bit is set to yes (zero state). However, during normal CPU processing events it may be necessary to set the entry invalid prior to aging the entry from the PLAT by LRU logic. Such events are, for example, if a new cache line is brought into the partitioned L1 cache then any entry in the PLAT referring to the old line is marked invalid. Also, in a multiple CPU environment, it is com­mon that one CPU will request that another CPU mark a cache line invalid. In this case, any entry in the PLAT is also marked invalid. The actual occurrence of the need to invalidate a PLAT entry is very infrequent, but it is included for accuracy and completeness.

0081FIGURE 12C is a variation of FIGURE 12B and is used by any CPU port assigned as a store port for data operands. Here both the valid bit (V) and valid store bit (V/S) are gated from the PLAT entry to the compare circuit 636. In this case, both the valid state AND the valid store state must be present, in addition to the positive address compare state, before the hit condition is de­termined on line 640. If either the valid state OR the valid store state conditions are not present, then the miss line 638 is again forced, and the address compare is ignored. Whenever a new entry is created in the PLAT due to a PLAT miss, the store interrogate operation is performed at the L1 directory. If this test is positive, then the valid store state is recorded in the PLAT entry. Subsequent store requests result in PLAT hits on line 640 and do not require the store interrogate operation in the directory.

0082In normal cache operation, it is not unusual to have a valid, read only data line in L1 cache, as well as a valid entry in the PLAT corresponding to that line. If the line had been requested "read only" by the L1 cache, then the store interrogate test would be negative and the invalid store state would be set in the PLAT for that entry. A subsequent store request to that line would result in a PLAT miss and a global request of the L1 directory. The read only state would then be deter­mined, and the L1 cache controls would request the store­-privilege-state from the SCE element of FIGURE 1. When the store privilege is eventually granted, the store-­privilege-state is recorded in the L1 directory. Then any subsequent store request to that line may result in a positive indicator from the store interrogate test, and the valid-store indicator set in the PLAT entry.

0083FIGURE 13 shows a special, fault tolerant feature of this partitioned cache. This feature tolerates major failures of the cache data array and directory components while avoiding a system outage or interruption of service to the user of the computer. Such failures would result in a degraded performance of the cache subsystem for the period of time until a repair action corrects the fault(s). For example, an entire directory element may fail (called a chip kill) or one to all of the data chips associated with a single cache partition may fail. In these cases the failed partition is logically decoupled from the cache subsystem resulting in a 12.5% loss in the cache capacity for a partitioned cache with eight partitions (note that a 12.5% loss in cache capacity does not re­sult in a 12.5% degradation of service, but rather a substantially smaller percent due to the nature of cache performance as a function of its capacity). A second major such failure prior to the repair action would re­sult in the loss of a second partition and a combined reduction in cache capacity of 25%, etc. For the above cases in present cache subsystems, the entire CPU would be lost until the repair action was completed. To most users a small loss in performance during critical opera­ting periods is acceptable, whereas a computer outage could have severe consequences.

0084The basis for the fault tolerance is that cache data as­sociated with a particular cache line is totally con­tained within a single cache partition and its address control information is totally contained within a single directory element which may be on a single chip. Also, a store-through L1 cache is used. This provides a du­plicate, valid copy of all L1 cache data in at least one higher level of the storage hierarchy. Thus, if a major failure as described should occur, the hardware detects the failure and decouples the failed partition(s), but no data is lost. In effect, the data resident in the failed and decoupled partition(s) will be refetched, L2 to L1, on demand by the processor but into a different partition of the cache which is still functional. In essence, the data in the failed partition(s) appears to the CPU the same as any non-resident cache data which must be fetched on an L1 miss.

0085The operation of the fault tolerant mechanism is shown in FIGURE 13. Hardware fault test logic 40 is active during all cache transactions. This includes, for ex­ample, parity testing of address, data and control busses 36 and 39 in a conventional manner. An invalid partition indicating register 702 is provided to store eight bits, each bit corresponding to one of eight cache partitions. Should a major failure occur, fault test hardware 40 sets on the corresponding bit in invalid partition indicating register 702 with input bus 700. Also, provided are LRU logic and tables 708. In normal events, LRU logic 708 monitors cache address bus 60A and cache control busses C2, 64 and C3, 66, and maintains an up-to-date LRU array 712. The C2 control bus indicates the active accessed partition number for local cache references; whereas the C3 control bus indicates the active responding partition number for global cache references. This array 712 stores one encoded entry for each congruence class of the cache 34 and directory 38. In essence each entry in the LRU array 712 stores a pointer, or partition number, of the partition to be used next to store the new line if a cache miss occurs. A conventional, partitioned LRU algorithm may also be used to maintain the current LRU entries in the LRU array.

0086The LRU logic 708 also monitors the contents of the in­valid partition indication register 702 on bus 704. Should any bit, or bits, be set on in 702, these bits act as an override to the LRU logic 708, such that those partitions will not be selected as input to the LRU array 712. Rather, LRU 708 will choose LRU entries to array 712 based on valid partition indicators in the register 702. Whenever an L1 cache miss occurs, the requesting address is sent to the LRU array 712 on bus 714. The LRU array 712 loads the partition number cor­responding to that requesting address congruence class onto bus 716, which is sent to the line fetch buffer 110 and is stored in partition number (PN) register 720. The requesting address is also sent to buffer 110 and is stored in address register (AR) register 724. The new line fetch is sent to buffer 110 from L2 on bus 112 and is stored in buffer 726. The line put away operation follows the line fetch operation. Here the cache re­ quest address A6 is placed on bus 60, the partition id­entity, C2 control bus, is placed on bus 64 by decoder 722, and the line data is placed on the store-bus port N of FIGURE 2 and FIGURE 13.

0087The hardware of FIGURE 13 decouples the failed part­ition(s) from future assignment of new cache data until a repair action corrects the fault(s). The time of the repair action occurrence is chosen at the convenience of the user. At this time the contents of the invalid part­ition indicating register 702 are returned to the valid state. Also, at the time of detection of a fault occur­rence, certain housekeeping tasks are understood. These include a scan of the LRU array on bus 718 to reset any invalid entry based on the new value of the invalid part­ition indicating register 702. Also, all PLAT arrays should be cleared so that no partition indicators point to faulty partitions, and inhibit addresses on address busses 60A and 60B directed to faulty partition(s) as determined by register 702.

0088Some additional features of the overall operation of the partitioned cache and PLAT according to the present in­vention will now be discussed.

0089One of the features is that a majority of store opera­tions will now be completed in a single cache cycle. This is achieved by the elimination of the store interrogate cycle from each local store operation of the cache. The store interrogate operation will be performed once on global store or fetch operations due to a PLAT miss. At this time a new entry occurs in the PLAT, and a valid or invalid store bit is set for that entry. Subsequent store requests with the valid store bit on in the PLAT will execute in a single cycle. Single cycle store opera­tions will reduce the number of cycles required for a store instruction, and reduce the average cycles per in­struction overall, thereby increasing the processor in­struction execution speed.

0090The line put-away operation will be accomplished with min­imum partition cache interference to the central processor. Put-away partition cache store cycles from a line fetch buffer will busy just one of the (M) partitions and will be activated only for those cycles when that partition is otherwise idle. This will allow larger cache lines to be used advantageously thereby improving the ratio of cache instructions per miss and improved PLAT hit ratios.

0091The critical cache access paths are contained within two chip crossings of presently available chips for all (N) parallel operational ports. This means that each of N simultaneously operative ports have one or two cycles of access. Local stores including line put away operations execute in a single cycle access per store block, while all other operations have a two-cycle access. Present single-ported cache organizations have a two-cycle access for both stores and fetches and are restricted to one operation per cycle.

0092The partitioned cache has greater availability due to high fault tolerant features. Conventional cache struc­tures carry parity checking but not error correction. If a single bit hard error occurs to a cache line or direct­ory bin, then a delete bit carried in the directory may be set by hardware controls to decouple that cache com­partment for further use until a repair operation is nec­essary. Both the conventional and partitioned cache uses decoupled failure mechanism. However if a complete cache or directory chip is lost, creating a chip kill, a system failure results in a conventional cache for the entire cache. The partitioned cache extends the delete bit con­cept to delete partition. Thus, for a chip kill, one partition of the cache is lost and a system failure is avoided.

0093A variety of designs are available to vary the output data block size associated with the individual cache ports and data busses. Variations of the base cache design, including provisions for a central processor design which uses a separate L0 cache structure are possibilities.