Bus Master Which Selectively Attempts to Fill Complete Entries in a Cache Line

The subject invention relates generally to bus masters and, more particularly, to a bus master which operates in conjunction with a cache memory.

In general, cache memories are arranged as a plurality of "lines", each containing a plurality of "entries" which share a common "tag address", and a corresponding number of "valid" bits which when set indicate the validity of the respective entries in the particular cache line. In normal operation, required operands are requested from a conventional system memory by an appropriate system bus master. If a requested operand is present in the cache memory, the cache provides that operand and the system memory request is aborted. If the requested operand is not in the cache, the operand will be provided by the system memory. Simultaneously, the operand will be stored in the cache, so long as the operand is sufficient to fill a full entry. Typically, the bus master then fetches the other operands having the same tag address in the system memory, to fill the entire cache line. However, if an operand (or some portion of an operand) is fetched that is insufficient in either size or alignment to fill an entire entry, the operand is not cached at all, and the bus master makes no further attempts to fill the other entries in the same cache line.

Accordingly, it is an object of the present invention to provide a bus master which selectively attempts to fill entire entries in a cache line.

These and other objects are achieved in a bus master which transfers a requested operand from a memory into an entry in a cache line having a selected tag address, wherein the operand or portion thereof provided by the memory during the initial (and perhaps only) bus cycle of an operand transfer cycle may be insufficient in either size or alignment to fill an entire entry in the cache line. In accordance with the present invention, the bus master comprises: size determining logic for determining if the operand (or portion thereof) provided by the memory during the initial bus cycle will fill the entire entry, and for providing an entry fill signal if the operand (portion) is insufficient to fill that entry; and bus cycle control logic, responsive to the entry fill signal, for transferring additional operands adjacent in said memory to said requested operand sufficient to fill said entry during respective subsequent bus cycles.

FIG. 1, illustrates in block diagram form, a data processing system having a bus master which cooperates with a cache memory in accordance with the present invention.

FIG. 2 illustrates the format of a line in the cache memory shown in FIG. 1.

FIG. 3 illustrates in block diagram form, a cache entry fill state machine of the bus master shown in FIG. 1.

FIG. 4 illustrates in block diagram form, the detailed inputs and outputs of the PLA portion of the state machine shown in FIG. 3.

FIG. 5 illustrates the timing signals used in the state machine shown in FIG. 4.

FIG. 6 illustrates in table form, the inputs and outputs of the PLA shown in FIG. 4.

FIG. 7 illustrates suitable logic for selectively disabling the state machine of FIG. 4.

Shown in FIG. 1 is a data processing system 10 comprised of a bus master 12 which requests operands via an address bus 14, and a system memory 16 which provides the requested operands via a data bus 18, with each operand transfer being coordinated via a control bus 20 during an operand transfer cycle which may include more than one bus cycle. In the illustrated form, a conventional cache memory 22 provides a high-speed store for a selected number of the most recently transferred operands. In the preferred form, the data bus 18 is 32-bits wide, but the bus master 12 and the system memory 16 are specially adapted to coordinate the transfer of byte (8-bit), word (16-bit) and longword (32-bit) operands. In this form, the data bus 18 is longword aligned with respect to the system memory 16, but the operands themselves may be aligned in the system memory 16 on any byte boundary. Thus, due to either operand size or address misalignment, some operand transfer cycles may consist of multiple bus cycles, with only a portion of the full operand being transferred each bus cycle. It follows, therefore, that only a portion of the transfer capacity of the data bus 18 will be required during at least some, if not all, of these bus cycle system of this type is shown and described in detail in U.S. Pat. No. 4,633,4337 and the description thereof is hereby incorporated herein by reference.

In the preferred form shown in FIG. 2, each "line" of the cache memory 22 consists of four longword "entries", a "valid" bit for each entry, and a "tag address" common to all four of the entries. Since there are only four valid bits, one for each entry, any transferred operand which is less than a longword in length cannot be cached. Thus, for example, if the transferred operand is less than a longword in length, say only a byte, the operand cannot be cached and, in prior art systems, would have to be retrieved from the system memory 16 each time it is required. Similarly, since the entries are longword aligned, any transferred operand that is not longword aligned in the system memory 16 cannot be cached either. Thus, for example, a longword operand which is aligned on a non-longword boundary in the system memory 16 will "span" two entries in the cache memory 22 but fill neither.

In order to facilitate the cacheing of as many operands as possible (and thus maximize the efficiency of the data processing system 10 as a whole), the bus master 12 is specially adapted in accordance with the present invention to detect when a transferred operand is insufficient in either size or alignment to fill an entire entry, and to automatically transfer sufficient additional operands adjacent in the system memory 16 to the requested operand to fill the entire entry in the cache line. In general, these "adjacent" operands would be all other bytes having the same tag and entry address bits as the requested operand or portion thereof. The transfers of these "nonrequested" operands (but which are required to fill-out cache entries) are preferably interspersed with transfers of the requested operands, even if to do so the latter transfers must be delayed. In many systems, any delays in processing activity will be more than compensated for by the increased "hit rate" in the cache memory 22.

Shown in FIG. 3 is a simplified form of a state machine 24 in the bus master 12 which coordinates the transfer of operands from the system memory 16 and the filling of entries in the state cache memory 22. In the preferred form, the machine 24 receives the following control inputs: the low order two bits of the address of the requested operand (REQ[AI,A0]), the encoded size of the requested operand (REQ[Sl,S0]), and the encoded "size" of the data port between the bus master 12 and the system memory 16 (SIZ[DSl,DS0]). In response to these signals (and others discussed below), the state machine 24 provides the following output signals: the low order two bits of the address to be sent to the system memory 16 during the next bus cycle (NXT[Al,A0]), the encoded size of the operand to be requested from the system memory 16 during the next bus cycle (NXT[Sl,S0]), a signal that indicates whether the next bus cycle is a special cycle to transfer an operand that was not requested but is required to fill an entry in the cache line (NXT[EFILL]), a signal that indicates that a cache entry FIG. 11 cycle has been completed (CYCOM), and a signal that indicates that the operand cycle has been completed (OPCOM). The state machine 24 also internally recirculates the following as status inputs: the low order two bits of the address being sent to the system memory 16 during the current bus cycle (CUR[Al,A0]), and the EFILL signal being output during the current bus cycle (CUR[EFILL]). A more detailed block diagram of the state machine 24 is shown in FIG. 4, which operates on a six-stage clock shown in FIG. 5. The state table for the PLA shown in FIG. 4 is shown in FIG. 6. The operation of the state machine 24 is typified by the following three (3) sets of examples:

In Case 1A, a single 8-bit byte is requested from an address in the system memory 16 having low order address bits [A3,A0]of [0011](i.e., byte [3]in the cache line), and the memory 16 is capable of providing the requested operand via a port that is only 8-bits wide. As can be seen, the operand transfer cycle is completed at the end of the first bus cycle, but the state machine 24 continues to run three (3) successive bus cycles in order to fill the remaining three (3) bytes (i.e., bytes [0,2]) of the corresponding entry [00]in the cache 22. At the end of the fourth bus cycle, the entire entry [00] has been filled and is marked valid.

In Case 1B, the same 8-bit byte [3] is requested, but the memory 16 is now capable of providing the requested operand via a port that is 16-bits wide. As in Case 1A, the operand transfer cycle is completed at the end of the first bus cycle, but two (2) adjacent bytes [2,3] are simultaneously transferred. Thus, the state machine 24 needs to run only one (1) additional bus cycle in order to fill the remaining two (2) bytes [0,1] of the corresponding entry [00] in the cache 22. At the end of the second bus cycle, the entire entry [00] has been filled and marked valid.

In Case 1C, the same 8-bit byte [3] is requested, but the memory 16 is now capable of providing the requested operand via a port that is 32-bits wide. As in Cases 1A and 1B, the operand transfer cycle is completed at the end of the first bus cycle, but four (4) adjacent bytes [0,1,3,] are simultaneously transferred. Thus, the state machine 24 needs to run no additional bus cycles in order to fill the corresponding entry [00] in the cache 22, and the entry [00] is immediately marked valid.

In Case 2A, a misaligned 16-bit word is requested from an address in the system memory 16 having low order address bits [A3,A0] of [0111] (i.e. bytes [7,8]), and the memory 16 is capable of providing the requested operand via a port that is only 8-bits wide. As can be seen, the operand transfer cycle is not completed until the end of the fifth bus cycle, because the state machine 24 runs three (3) intervening bus cycles, in order to fill the remaining three (3) bytes [4,5,6] of the corresponding entry [01] in the cache 22. At the end of the fourth bus cycle, the entry [01] has been filled, and is marked valid. By the end of the fifth bus cycle, the operand transfer cycle is complete, but the machine 24 continues to run three (3) more bus cycles to fill the remaining three (3) bytes [9,A,B] of the next entry [10] in the cache 22.

In Case 2B, the same 16-bit word [7,8] is requested, but the memory 16 is now capable of providing the requested operand via a port that is 16-bits wide. As a result, the operand transfer cycle is now completed at the end of the third bus cycle, because the state machine 24 must run only one (1) intervening bus cycle in order to fill the remaining two (2) bytes [4,5] of the corresponding entry [01] in the cache 22. At the end of the second bus cycle, the entry [01] has been filled, and is marked valid. By the end of the fourth bus cycle, the next entry [10] in the cache 22 is filled and marked valid.

In Case 2C, the same 16-bit word [7,8] is requested, but the memory 16 is now capable of providing the requested operand via a port that is 32-bits wide. Accordingly, the operand transfer cycle is completed at the end of the second bus cycle. Entry [01] is completely filled by the first bus cycle and marked valid, and entry [10] is completely filled by the second bus cycle.

In Case 3A, a misaligned 32bit longword is requested from an address in the system memory 16 having low order address bits [A3,A)] of [1010] (i.e., bytes [A,D]), and the memory 16 is capable of providing the requested operand vis a port that is only 8-bits wide. As can be seen, the operand transfer cycle is not completed until the end of the sixth bus cycle, because the state machine 24 runs two (2) intervening bus cycles in order to fill the remaining two (2) bytes [8,9] of the corresponding entry [10] in the cache 22. At the end of the fourth bus cycle, the entry ]10] has been filled, and is marked valid. By the end of the sixth bus cycle, the operand transfer cycle is complete, but the state machine 24 runs two (2) more bus cycles to fill the next entry [11] in the cache 22.

In Case 3B, the same 32-bit longword [A,D] is requested, but the memory 16 is now capable of providing the requested operand via a port that is 16-bits wide. As a result, the operand transfer cycle is now completed at the end of the third bus cycle, because the state machine 24 must run only one (1) intervening bus cycle in order to fill the remaining two (2) bytes [8,9] of the corresponding entry [10] in the cache 22. At the end of the second bus cycle, the entry [10] has been filled, and is marked valid. By the end of the fourth bus cycle, the next entry [11] in the cache 22 is filled and marked valid.

In Case 3C, the same 32-bit longword [A,D] is requested, but the memory 16 is now capable of providing the requested operand via a port that is 32-bits wide. Accordingly, the operand transfer cycle is completed at the end of the second bus cycle. Entry[10] is filled by the first bus cycle and marked valid, and entry [11] is filled by the second bus cycle and marked valid.

In some circumstances, it may be desirable to inhibit the entry filling activities of the bus master 12, for example, if the cache memory 22 is itself disabled or if the processing activity is too critical to be delayed while the cache entries are filled. In general, the entry filling operation of the state machine 24 can be disabled as shown in FIG. 3 by blocking the recirculation of the EFILL signal via an AND gate 26 in response to a disable (DISABLE) signal. However, if the DISABLE signal is dynamic and might occur during an entry fill cycle, the logic shown in FIG. 7 would be more appropriate, since the latter includes an additional pair of gates 28 and 30 to force the CYCOM signal if the DISABLE signal is received while an entry fill cycle (NXT[EFILL]) is in progress or about to begin.

Although the present invention has been described herein in the context of a preferred embodiment, alternate embodiments may be made without departing from the spirit and scope of the present invention. For example, state machine 24 may be implemented in any of a number of well known forms, and the functionality thereof may be embodied in a micromachine if desired. In systems lacking dynamic bus sizing, the state machine 24 may be significantly simplified. If the size of the entries in a cache line is different, the size detecting criteria of the state machine 24 must be appropriately adjusted.