Cache control unit with a cache request transaction-oriented protocol

• US 5,860,158 A
• Filed: 11/15/1996
• Issued: 01/12/1999
• Est. Priority Date: 11/15/1996
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Pai, Yet-Ping, Nguyen, Le T.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Lee, Felix B.
• Application Number:
  US08/751,149
• Time in Patent Office: 788 Days
• Field of Search: 711/119, 711/120, 711/130, 711/140, 711/118
• US Class Current: 711/118
• CPC Class Codes: G06F 12/084 with a shared cache

Abstract

A cache control unit and a method of controlling a cache. The cache is coupled to a cache accessing device. A first cache request is received from the device. A request identification information is assigned to the first cache request and provided to the requesting device. The first cache request may begin to be processed. A second cache request is received from the cache accessing device. The second cache request is assigned to the first cache request and provided to the requesting device. The first and second cache requests are finally fully serviced.

Claims

1. A method for controlling a cache, the cache being coupled to a device, the method comprising:

receiving by a cache controller a first cache request from the device;

providing by the cache controller a first request ID value corresponding to the first cache request to the device after receiving the first cache request;

initiating processing of the first cache request after receiving the first cache request;

receiving by the cache controller a second cache request from the device after receiving the first cache request;

providing by the cache controller a second request ID value corresponding to the second cache request to the device after receiving the second cache request;

initiating processing of the second cache request after receiving the second cache request; and

completing the processing of the first and second cache requests after receiving the second cache request.

2. The method of claim 1 wherein

the providing by the cache controller the first request ID value includes

providing a first unit ID identifying the device;

and

providing a first transaction ID uniquely distinguishing the first cache request from other cache requests; and

the providing by the cache controller the second request ID value includes

providing a second unit ID identifying the device; and

providing a second transaction ID uniquely identifying the second cache request from other cache requests.

3. A cache system comprising:

a cache for temporarily storing information; and

a cache control unit comprising;

access control logic for receiving and executing a plurality of cache accesses by a cache accessing device;

identification logic for assigning request identification information uniquely identifying each of the plurality of cache accesses, and for providing the request identification information to the cache accessing device, the identification logic capable of providing the request identification information prior to execution of the plurality of cache accesses by the access control logic; and

result logic for providing the request identification information and information requested by the cache accessing device to the cache accessing device if the cache access was a read.

4. The cache system of claim 3 wherein the cache comprises:

a store array having a plurality of lines for temporarily storing information; and

a tag array having a plurality of tag locations for storing a corresponding plurality of tags, the plurality of tag locations corresponding to the plurality of lines of the store array, each tag location storing a tag indicating an address of the information stored in a corresponding line of the store array.

5. The cache system of claim 4 wherein the store array further comprises:

an instruction store array having a plurality of lines for temporarily storing instruction information; and

a data store array having a plurality of lines for temporarily storing data information; and

wherein the tag array further comprises;

an instruction tag array having a plurality of instruction tag locations for storing a corresponding plurality of instruction tags, the plurality of instruction tag locations corresponding to the plurality of lines of the instruction store array, each instruction tag location storing an instruction tag indicating an address of the information stored in a corresponding line of the instruction store array; and

a data tag array having a plurality of data tag locations for storing a corresponding plurality of data tags, the plurality of data tag locations corresponding to the plurality of lines of the data store array, each data tag location storing a data tag indicating an address of the information stored in a corresponding line of the data store array.

6. The cache system of claim 3 wherein the cache further comprises:

an instruction cache for temporarily storing instruction information; and

a data cache for temporarily storing data information.

7. The cache system of claim 3 wherein the cache system is for providing temporary storage for a first device and a second device, the cache further comprising:

an instruction store array having a plurality of lines for temporarily storing instruction information for use by the first device;

an instruction store array having a plurality of lines for temporarily storing instruction information for use by the second device;

a data store array having a plurality of lines for temporarily storing data information for use by the first device; and

a data store array having a plurality of lines for temporarily storing data information for use by the second device;

a plurality of tag arrays corresponding to the instruction and data store arrays, the plurality of tag arrays having a plurality of tag locations for storing a corresponding plurality of tags, the plurality of tag locations corresponding to the plurality of lines of the instruction and data store arrays, each tag location storing a tag indicating an address of the information stored in a corresponding line of the instruction and data store arrays.

8. The cache system of claim 3 wherein the cache system is for providing temporary storage for a plurality of devices, wherein the cache is an N-way cache, N being the number of devices in the plurality, the cache further comprising:

an instruction bank for each of the plurality of devices, the instruction bank having a plurality of lines for temporarily storing instruction information for use by each of the plurality of devices;

a data bank for each of the plurality of devices, the data bank having a plurality of lines for temporarily storing data information for use by each of the plurality of devices; and

a tag array for each of the plurality of devices, the tag array having a plurality of tag locations for storing a corresponding plurality of tags, the plurality of tag locations corresponding to the plurality of lines of the corresponding instruction and data banks, each tag location storing a tag indicating an address of the information stored in a corresponding line of the corresponding instruction and data banks.

9. The cache system of claim 3, wherein the access control logic executes each of the plurality of cache requests in a plurality of pipeline stages, the access control logic temporarily waiting to execute a stage of a first cache request while executing a stage of a second cache request received after the first cache request.

10. The cache system of claim 3 wherein

the cache accessing device is a first device of a plurality of cache accessing devices, the plurality of cache accessing devices including the first device and a second device;

the cache is for temporarily storing information for at least the first and second devices of the plurality of cache accessing devices;

the access control logic is for receiving and executing a plurality of cache accesses by the first and second devices;

the identification logic is for providing the request identification information to a corresponding each one of the first and second devices providing each cache access; and

the result logic is for providing the request identification information and the information requested by each one of the first and second device to a corresponding one of the first and second devices for each cache read.

11. The cache system of claim 10 wherein the access control logic includes:

receiving logic for receiving cache requests from the first device and a second device;

grant logic for granting access to the cache by the first device if a cache hit occurs for a first cache request from the first device for first information, and for granting access to the cache by the second device if a cache miss occurs for the first cache request and a cache hit occurs for a second cache request from the second device for second information; and

refill logic for fetching from a memory the first information if a cache miss occurs for the first cache request while the second device is granted access to the cache.

12. The cache system of claim 11 wherein the access control logic further includes:

hold logic for holding access to the cache by the second device if the cache is busy with a first granted access to the cache by the first device.

13. The cache system of claim 11 wherein the access control logic grants the first device access to the cache after first requested information is fetched from the memory if a cache miss occurred for the first cache request.

14. The cache system of claim 3, wherein

the cache system stores scalars and vectors;

the requests include scalar requests and vector requests; and

the access control logic includes logic for receiving and executing scalar requests and logic for receiving and executing vector requests.

15. A method for controlling a cache, the cache being coupled to at least one device, the method comprising:

receiving by a cache controller a first cache request from a first device of the at least one device;

providing by the cache controller a first request ID value corresponding to the first cache request to the first device after receiving the first cache request;

initiating processing of the first cache request after receiving the first cache request;

receiving by the cache controller a second cache request from a second device of the at least one device after receiving the first cache request;

providing by the cache controller a second request ID value corresponding to the second cache request to the second device after receiving the second cache request;

initiating processing of the second cache request after receiving the second cache request;

completing the processing of the first cache request after receiving the second cache request; and

completing the processing of the second cache request after receiving the second cache request.

16. The method of claim 15 wherein

the providing by the cache controller the first request ID value includes

providing a first unit ID uniquely identifying the first device;

and

providing a first transaction ID uniquely identifying the first cache request from other cache requests; and

the providing by the cache controller the second request ID value includes

providing a second unit ID uniquely identifying the second device; and

providing a second transaction ID uniquely identifying the second cache request from other cache requests.

17. The method of claim 15 wherein the first and second devices are the same device.

18. A method of controlling a cache, the cache coupled to a cache controller and a cache accessing device, the method comprising:

a first step of receiving a first cache request from the cache accessing device by the cache controller;

a second step of providing a first request ID to the cache accessing device by the cache controller after the first step;

a third step of storing the first request ID by the cache accessing device after the second step;

a fourth step of receiving a second cache request from the cache accessing device by the cache controller after the first step;

a fifth step of providing a second request ID to the cache accessing device by the cache controller after the fourth step;

a sixth step of storing the second request ID by the cache accessing device after the fifth step;

a seventh step of processing the first cache request after the second step; and

an eighth step of processing the second cache request after the fifth step.

19. The method of claim 18 further comprising:

a ninth step of providing a cache request result and the corresponding request ID to the cache accessing device after each corresponding cache request is processed, if a cache request result is required by the corresponding cache request.

20. The method of claim 19 wherein the ninth step comprises:

a tenth step of providing a first cache request result and the first request ID to the cache accessing device after the seventh step;

an eleventh step of recognizing the request ID by the cache accessing device after the tenth step;

an twelfth step of receiving and storing the first cache request result by the cache accessing device after the eleventh step;

a thirteenth step of providing a second cache request result and the second request ID to the cache accessing devices after the eighth step;

a fourteenth step of recognizing the request ID by the cache accessing device after the thirteenth step; and

a fifteenth step of receiving and storing the second cache request result by the cache accessing device after the fourteenth step.

21. The method of claim 18 wherein

the first cache request is received by the cache controller from a first cache accessing device;

and

the second cache request is received by the cache controller from a second cache accessing device.

22. The method of claim 21, wherein

the first step comprises:

receiving the first cache request by the cache controller; and

receiving a first device ID identifying the first cache accessing device to the cache controller; and

the fourth step comprises;

receiving the second cache request by the cache controller; and

receiving a second device ID identifying the second cache accessing device to the cache controller.

23. The method of claim 22 wherein

the second step comprises:

providing the first device ID identifying the first cache accessing device; and

providing a first transaction ID identifying the first cache request; and

the fifth step comprises;

providing the second device ID identifying the second cache accessing device; and

providing a second transaction ID identifying the second cache request.

24. The method of claim 21 further comprising:

a ninth step of providing a cache request result and the corresponding device and transaction IDs to the cache accessing devices after each corresponding cache request is processed, if a cache request result is required by the corresponding cache request.

25. The method of claim 24 wherein the ninth step comprises:

a tenth step of providing a first cache request result and the first device and transaction IDs to the cache accessing devices after the seventh step;

an eleventh step of recognizing the first device IDs by the first cache accessing device after the tenth step;

an twelfth step of receiving and storing the first cache request result by the first cache accessing device after the eleventh step;

a thirteenth step of providing a second cache request result and the second device and transaction IDs to the cache accessing devices after the eighth step;

a fourteenth step of recognizing the second device ID by the second cache accessing device after the thirteenth step; and

a fifteenth step of receiving and storing the second cache request result by the second cache accessing device after the fourteenth step.

26. A cache control unit for controlling a cache system, the cache control unit comprising:

means for receiving requests from a cache requesting device into a request queue;

means for stalling further requests until pending requests are serviced;

means for providing request identification information to the cache requesting device, the request identification information uniquely identifying each request received from a cache requesting device;

means for servicing the requests, including means for servicing a second received request before a first received request is serviced;

means for providing requested information from a cache line and corresponding request identification information to a requesting device;

means for providing requested information and corresponding request identification information to a requesting device after a cache line is refilled from the memory;

means for refilling information from a memory when a cache miss occurs;

means for writing a dirty cache line to the memory; and

means for writing from the cache to the memory.

27. The cache control unit of claim 26, wherein

the cache system stores scalars and vectors;

the requests include scalar requests and vector requests; and

the means for servicing the requests includes means for servicing scalar requests and vector requests.

28. The cache control unit of claim 26 further comprising a general purpose processor interface state machine for interfacing with a general purpose processor, the general purpose processor interface state machine comprising:

a start state for receiving requests from a general purpose processor, the general purpose processor interface state machine remaining in the start state when no requests are made by the general purpose processor;

a hold state for granting a first request but holding the first request while a second request is serviced, the general purpose processor interface state machine transitioning from the start state to the hold state when a request is received from the general purpose processor and granted by the cache control unit and the cache control unit is servicing a second request, the general purpose processor interface state machine remaining in the hold state until the second request is serviced, the general purpose processor interface state machine transitioning to the tag state when the second request is serviced;

a tag state for checking for address tag matches for granted requests, the general purpose processor interface state machine transitioning from the start state to the tag state when the cache control unit is ready to service the granted requests, the general purpose processor interface state machine transitioning from the hold state to the tag state when the cache control unit is ready to service the granted requests;

a miss state for sending a cache fill request to a memory, the general purpose processor interface state machine transitioning from the tag state to the miss state when a cache miss occurs;

a data state for returning requested information to the cache requesting device, the general purpose processor interface state machine transitioning from the tag state to the data state when a cache hit occurs, the general purpose processor interface state machine transitioning from the miss state to the data state when the cache fill request is serviced by the memory.

29. The cache control unit of claim 26 further comprising a bus interface state machine for interfacing with a bus, the bus coupled with a memory, the bus interface state machine comprising:

an idle state for receiving requests from a cache requesting device, the bus interface state machine remaining in the idle state when no requests are received;

a request state for requesting access to the bus, the bus interface state machine transitioning to the request state from the idle state when access to the memory by the cache system is required, the bus interface state machine remaining in the request state when the cache system has not been granted access to the bus;

a first greater state for granting bus access to the cache system for a first data group having a first size, the bus interface state machine transitioning to the first greater state from the request state when the bus grants bus access to the cache system, the bus interface state machine transitions from the first greater state to the idle state when the first size access is complete;

a second greater state for granting bus access to the cache system for a second data group, the first data group and the second data group together having a second size greater than the first size, the bus interface state machine transitioning to the second greater state from the first greater state when the bus grants bus access to the cache system for a second size access, the bus interface state machine transitions from the second greater state to the idle state when the second size access is complete;

a third greater state for granting bus access to the cache system for a third data group, the first, second and third data groups together having a third size greater than the second size, the bus interface state machine transitioning to the third greater state from the second greater state when the bus grants bus access to the cache system for a third size access, the bus interface state machine transitions from the third greater state to the idle state when the third size access is complete; and

a fourth greater state for granting bus access to the cache system for a fourth data group, the first, second, third and fourth data groups together having a fourth size greater than the third size, the bus interface state machine transitioning to the fourth greater state from the third greater state when the bus grants bus access to the cache system for a fourth size access, the bus interface state machine transitions from the fourth greater state to the idle state when the fourth size access is complete.

30. The cache control unit of claim 26 further comprising a data receiver state machine for receiving data, the data receiver state machine comprising:

an idle state for awaiting receipt of data responsive to a request from a cache accessing device, the data receiver state machine remaining in the idle state when the data is not being received;

a first state for receiving a first data portion having a first size, the data receiver state machine transitioning to the first state from the idle state when the request has been serviced by the means for servicing the requests;

a second state for receiving a second data portion having a second size greater than the first size if the request from the cache accessing device was for data having the second size, the data receiver state machine transitioning to the second state from the first state when the request from the cache accessing device was for data having the second size;

a third state for receiving a third data portion having a third size greater than the second size if the request from the cache accessing device was for data having the third size, the data receiver state machine transitioning to the third state from the second state when the request from the cache accessing device was for data having the third size;

a fourth state for receiving a fourth data portion having a fourth size greater than the third size if the request from the cache accessing device was for data having the fourth size, the data receiver state machine transitioning to the fourth state from the third state when the request from the cache accessing device was for data having the fourth size;

a refill state for refilling the cache system with the data received responsive to a request from a cache accessing device, the data including the data portions received, the data receiver state machine transitioning to the refill state from the first state when the cache accessing device requested data having the first size and the first data portion is received, the data receiver state machine transitioning to the refill state from the second when the cache accessing device requested data having the second size and the second data portion is received, the data receiver state machine transitioning to the refill state from the third state when the cache accessing device requested data having the third size and the third data portion is received, the data receiver state machine transitioning to the refill state from the fourth state when the cache accessing device requested data having the fourth size and the fourth data portion is received; and

a ready state for providing the data to the cache accessing device, the data receiver state machine transitioning to the ready state from the refill state when the cache system has been refilled, the data receiver state machine remaining in the ready state until the cache accessing device reads the data, the data receiver state machine transitioning from the ready state to the idle state when the cache accessing device reads the data.

31. The cache control unit of claim 26 further comprising a read state machine, the read state machine comprising:

an idle state, the read state machine entering the idle state after the cache control unit is reset, the read state machine remaining in the idle state until the cache control unit is ready to receive a read request;

a run state for receiving a read request from a cache requesting device, the read state machine transitioning to the run state from the idle state when the cache control unit is ready to receive a read request;

a stall state for preventing new read requests from being accepted, the read state machine transitioning to the stall state from the run state when additional resources are required to service the read operation;

a data ready state for driving data returned from a memory to the cache requesting device, the read state machine transitioning to the data ready state from the run state when the data has been driven to the cache requesting device;

a write back state for writing back a first dirty vector to a memory, the read state machine transitioning to the write back state from the run state when one dirty vector is to be written to the memory, the read state machine remaining in the write back state until the first dirty vector is written to the memory;

a next write back state for writing back a second dirty vector, the read state machine transitioning to the next write back state from the write back state when a subsequent dirty vector is to be written to the memory, the read state machine transitioning from the next write back state to the run state when the second dirty vector has been written to the memory.

32. The cache control unit of claim 31 wherein the read state machine

remains in the idle state when no request is received;

remains in the idle state when a request is received and the request is granted but later revoked; and

transitions to the run state when a request is received, granted and not revoked.

33. The cache control unit of claim 31 wherein the read state machine, when in the stall state, saves the address of an additional read request and revokes a read grant for the additional read request.

34. The cache control unit of claim 31 wherein

the cache control unit further includes an address queue for temporarily storing read addresses for accessing a memory;

the read state machine transitions to the stall state when a clean read miss occurs and address queue is full; and

the read state machine transitions to the stall state when a dirty read miss occurs and the address queue is full.

35. The cache control unit of claim 31 wherein

the cache control unit further includes a write back latch for latching a dirty vector;

and

the read state machine transitions to the stall state when a dirty read miss occurs and the write back latch is full.

36. The cache control unit of claim 26 further comprising a write state machine, the write state machine comprising:

an idle state, the write state machine entering the idle state after the cache control unit is reset;

a run state for receiving a write request from a cache requesting device, the write state machine transitioning to the run state from the idle state when the cache control unit is ready to receive a write request;

a stall state for preventing new write requests from being accepted, the write state machine transitioning to the stall state from the run state when additional resources are required to service the write operation;

a refill state for a cache refill write wherein data is received from a memory, aligned if necessary and loaded into the cache, the write state machine transitioning to the refill state from the run state when data is returned from the memory to the cache;

a write back state for writing back a first dirty vector to a memory, the write state machine transitioning to the write back state from the run state when one dirty vector is to be written to the memory;

a next write back state for writing back a second dirty vector, the write state machine transitioning to the next write back state from the write back state when the first dirty vector has been written to the memory and a subsequent dirty vector is to be written to the memory, the write state machine transitioning from the next write back state to the run state when the second dirty vector has been written to the memory.

37. The cache control unit of claim 36 wherein the write state machine further comprises:

a memory low write state for bypassing the cache to write a first vector to the memory, the write state machine transitioning to the memory low write state from the run state when the first vector is to be written to a low vector location, the write state machine transitioning from the memory low write state to the stall state when the address queue is full; and

a memory high write state for bypassing the cache to write a second vector to the memory, the write state machine transitioning to the memory high write state from the run state when the second vector is to be written to a high vector location, the write state machine transitioning to the memory high write state from the memory low write state when both the first and second vectors are to be written into the low and high vector locations, respectively.