Multi-entry fully associative transition cache

• US 6,000,011 A
• Filed: 12/09/1996
• Issued: 12/07/1999
• Est. Priority Date: 12/09/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Grosbach, Lyle E., Mounes-Toussi, Farnaz, Paulson, Peder J., Irish, John D., Freerksen, Donald Lee
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Ellis, Kevin L.
• Application Number:
  US08/761,378
• Time in Patent Office: 1,093 Days
• Field of Search: 711/118, 711/140, 711/128, 709/213, 709/231, 709/238, 710/5, 710/52
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0831 using a bus scheme, e.g. with bus monitoring or watching means

Abstract

A method and apparatus for handling commands and data associated therewith includes a data buffer and a command directory. The command directory receives and stores a command from at least one command source, and freely allocates an unused portion of the data buffer to the command. The data buffer stores the data associated with the command in the allocated portion of the data buffer. Based on status information also stored by the command directory with respect to each command, routing logic in the command directory, corresponding to each command sink, identifies which commands stored in the command buffer to route to the command sink, and routes the identified commands to the command sink. The routing logic also determines a priority of the identified commands and routes the identified commands in order of priority. The command directory also uses the status information to track the processing of commands.

Claims

1. A transition cache, comprising:

(a) a data buffer with N entries to store data in any entry;

(b) a fully associative directory with N entries to store commands, addresses, and state information associated with data;

(c) a plurality of read/write interfaces, at least one of said read/write interfaces connected to each of a plurality of command source/sinks each capable of sending and receiving a command or data to or from said connected read/write interface,

the transition cache to route and track commands between any of said plurality of command source/sinks.

2. The transition cache of claim 1, wherein said directory comprises:

(b1) a command buffer having N entries, each entry for storing a command; and

(b2) command acceptor logic, associated with each of said plurality of command source/sinks, receiving said command from a particular command source/sink, determining whether said command buffer can accept said received command, and if so, sending said received command to said command buffer.

3. The transition cache of claim 2, wherein said transition cache further comprises:

free buffer logic monitoring said command buffer, determining which of said N directory entries of said command buffer are unused based on said monitoring, and generating in response thereto an unused directory entry output; and

wherein

said command acceptor logic determines whether an unused directory exists based on said unused directory entry output.

4. The transition cache of claim 3, wherein

said free buffer logic supplies said command acceptor logic with a directory address of said unused directory entry;

said data buffer includes a data portion corresponding to each of the N directory entries in said command buffer; and

said command acceptor logic sends said received command to said unused directory entry based on said directory address, and said command acceptor logic supplies said directory address to said particular command source/sink such that if said particular command source/sink outputs said data corresponding to said received command, said data corresponding to said received command is output to a portion of said data buffer having an address corresponding to said directory address.

5. The transition cache of claim 3, wherein said command acceptor logic decodes said received command, and if said received command is a request type of command, said command acceptor logic determines whether at least one directory entry is unused, if at least one directory entry is unused, said command acceptor logic sends said received command to said unused directory entry.

14. The apparatus of claim 1, wherein

said directory maintains cache coherency state of the data stored in said data buffer.

6. An apparatus for handling commands and data associated therewith, comprising:

a data buffer;

a command directory receiving for storing a command from at least one command source, and freely allocating an unused portion of said data buffer to said command, said command directory also comprising;

a command buffer storing said command, said command buffer comprising free buffer logic to monitor and determine which of said directory entries of said command buffer are unused and in response thereto, to generate an unused directory entry output based on said determination;

command acceptor logic, associated with each command source, receiving said command and determining whether said command buffer can accept said received command, and if said command buffer can accept said received command and if so, sending said received command to said command buffer;

said command acceptor logic decodes said received command, and if said received command is a request type of command, said command acceptor logic determines whether at least three directory entries are unused, if at least three directory entries are unused, said command acceptor logic sends said received command to one of said unused directory entries.

7. An apparatus for handling commands and data associated therewith, comprising:

a data buffer;

a fully associative command directory receiving and storing a command from one of a plurality of command source/sinks each of which may send or receive a command to said command directory, said command directory freely allocating an unused portion of said data buffer to said command, and generating status information associated with said received command, said status information indicating, at least, which of said one of plurality of command source/sinks to which to route said received command, and includes a command buffer storing said received command and said status information;

said data buffer storing data associated with said command in said allocated portion of said data buffer

and said apparatus further including,

routing logic, corresponding to each of said plurality of command source/sinks, identifying which commands stored in said command buffer to route to said corresponding command source/sink based on said status information, and routing said identified commands to said command source/sink.

8. The apparatus of claim 7, wherein each routing logic determines a priority of said identified commands, and routes said identified commands in order of priority determined by the type of command.

9. The apparatus of claim 8, wherein

each command stored by said command buffer belongs to one of a plurality of command priority groups;

and

said routing logic determines a priority of an identified command based on which one of said command priority groups said identified command belongs.

10. The apparatus of claim 8, wherein said routing logic changes priority of said identified commands based on a raise priority signal.

11. An apparatus for handling commands and data associated therewith, comprising:

a data buffer;

a command directory receiving and storing a command from at least one command source, said command belonging to one of a plurality of command priority groups, freely allocating an unused portion of said data buffer to said command, and generating status information associated with said received command, said status information indicating, at least, a command sink to which to route said received command, and includes a command buffer storing said received command and said status information;

said data buffer storing data associated with said command in said allocated portion of said data buffer

routing logic, corresponding to each command sink, including a programmable priority register storing a code which indicates a priority of said command priority groups, identifying which commands stored in said command buffer to route to said corresponding command sink based on said status information, determining a priority of said identified commands based on said code stored in said programmable priority register, and routing said identified commands to said command sink in order of priority.

12. An apparatus for handling commands and data associated therewith, comprising:

a data buffer;

a command directory receiving and storing a command from at least one command source, and freely allocating an unused portion of said data buffer to said command;

said data buffer storing data associated with said command in said allocated portion of said data buffer,

said command directory further comprising a command buffer storing said command; and

command acceptor logic, associated with each command source, receiving said command, determining whether said command buffer can accept said received command, and if so, sending said received command to said command buffer;

wherein

said command buffer receives status information associated with said command, said status information indicating, at least, a command sink to which to route said command; and

said apparatus further includes,

routing logic, corresponding to each command sink, identifying which commands stored in said command buffer to route to said corresponding command sink based on said status information, and routing said identified commands to said command sink; and

wherein

said command acceptor includes dependency logic determining whether said received command depends on performance of a command currently stored by said command buffer, and if said received command depends on performance of a command currently stored by said command buffer, said dependency logic sends said command buffer dependency information, as part of said status information, corresponding to said received command indicating said dependency; and

said routing logic checks said status information corresponding to said command prior to routing said received command, and if said status information indicates said dependency, said routing logic prohibits routing of said received command.

13. A transition cache, comprising:

(a) a data buffer with N entries to store data in any entry;

(b) a directory with N entries to store commands, addresses, and state information associated with data;

(c) a plurality of interfaces, each of said interfaces connected to one of a plurality of command sources and one of a plurality of command sinks,

said directory to store and update status information of a received command between said command source and at least one command sink, said transition cache to route and track commands between any command source and any command sink.

15. An apparatus for handling commands and data associated therewith, comprising:

a data buffer;

a command directory receiving and storing a command from at least one command source, and freely allocating an unused portion of said data buffer to said command;

said data buffer storing data associated with said command in said allocated portion of said data buffer and said command directory maintaining cache coherency state of data stored in said data buffer, wherein

said data buffer stores a line of cache associated with said command; and

said command directory stores memory image coherency information as MESI state information, where MESI stands for modified, exclusive, shared, and invalid, corresponding to said line of cache, said memory image coherency information being transferred to said command directory from said command source.

16. The apparatus of claim 15, wherein said command buffer updates said MESI state information based on signals received from command sinks.

17. An apparatus for handling commands and data associated therewith, comprising:

a data buffer;

a command directory receiving and storing a command from at least one command source, and freely allocating an unused portion of said data buffer to said command, and generating status information associated with said received command, said status information indicating, at least, a command sink to which to route said received command, and includes a command buffer storing said received command and said status information;

said data buffer storing data associated with said command in said allocated portion of said data buffer

and said apparatus further including,

routing logic, corresponding to each command sink identifying which commands stored in said command buffer to route to said corresponding command sink based on said status information, and routine said identified commands to said command sink wherein routing logic includes means for transferring a command output from a command source directly to said corresponding command sink prior to said command being stored in said command buffer.

18. A method for handling commands and data associated therewith, comprising:

(a) receiving a command from any of a plurality of command sources operatively connected to a transition cache;

(b) storing said command in a command buffer in said transition cache;

(c) freely allocating an unused portion of a data buffer in said transition cache to said command; and

(d) storing data associated with said command in said allocated portion of said data buffer,

(e) storing and updating in said command buffer status information of said command between any of said plurality of command sources and any of a plurality of command sinks.

19. The method of claim 18, further comprising:

(e) maintaining cache coherency state in said command buffer for said data stored in said data buffer.

20. The method of claim 19, wherein step (b) comprises:

(b1) determining whether said command buffer can accept said command; and

(b2) storing said command in said command buffer if said command buffer can accept said command.

21. The method of claim 20, wherein said command buffer includes a plurality of directory entries, each directory entry for storing a command;

and

said step (b1) determines whether said command buffer includes an unused directory entry, and includes the substeps of

(b11) decoding said command to determine if said command is a request type of command, and

(b12) determining whether at least one directory entry is unused; and

said step (b2) includes the substep of,

(b21) storing said command in said directory entry if at least one directory entry is unused when said step (b11) determines that said command is a request type of command.

22. A method for handling commands and data associated therewith, comprising:

(a) receiving a command from at least one command source;

(b) storing said command in a command buffer, comprising

(b1) determining whether said command buffer can accept said command; and

(b2) storing said command in said command buffer if said command buffer can accept said command;

(c) freely allocating an unused portion of a data buffer to said command; and

(d) storing data associated with said command in said allocated portion of said data buffer,

wherein said command buffer includes a plurality of directory entries, each directory entry for storing a command; and

said step (b1) determines whether said command buffer includes an unused directory entry, and includes the substeps of

(b11) decoding said command to determine if said command is a request type of command, and

(b12) determining whether at least three directory entries are unused; and

said step (b2) includes the substeps of,

(b21) storing said command in said unused directory entry of said command buffer if an unused directory entry exists and said step (b11) determines that said command is not a request type of command, and

(b22) storing said command in one of said directory entries if at least three directory entries are unused when said step (b11) determines that said command is a request type of command.

23. A method for handling commands and data associated therewith, comprising:

(a) receiving a command from any of a plurality of command source/sinks each capable of sending and receiving said command to or from a command buffer;

(b) storing said command in said command buffer;

(c) freely allocating an unused portion of a data buffer to said command; and

(d) storing data associated with said command in said allocated portion of said data buffer;

(e) storing status information associated with said command in said command buffer, said status information indicating, at least, one of said plurality of command source/sinks to which to route said command;

(f) identifying, for each of said plurality of command source/sinks, which commands stored in said command buffer to route to said command source/sink based on said status information; and

(g) routing said identified commands to said command source/sink.

24. The method of claim 23, wherein said step (g) comprises:

(g1) determining a priority of said identified commands based on the type of command; and

(g2) routing said identified commands in order of priority.

25. The method of claim 24, wherein each command stored by said command buffer belongs to one of a plurality of command priority groups having a predetermined order of priority;

and

said step (g1) identifies to which one of said command priority groups each identified command belongs; and

said step (g2) routes said identified commands based on membership in a command priority group.

26. A method for handling commands and data associated therewith, comprising:

(a) receiving a command from at least one command source;

(b) storing said command in a command buffer, said command belonging to one of a plurality of command priority groups having a predetermined order of priority;

(c) freely allocating an unused portion of a data buffer to said command; and

(d) storing data associated with said command in said allocated portion of said data buffer;

(e) storing status information associated with said command in said command buffer, said status information indicating, at least, a command sink to which to route said command;

(f) identifying, for each command sink which commands stored in said command buffer to route to said command sink on said status information; and

(g) routing said identified commands to said command sink by;

(g1) storing a code which indicates a priority of said command priority groups in a programmable priority register;

(g2) determining a priority of said identified commands based on said code stored in said programmable priority register by identifying which one of said command priority groups each identified command belongs; and

(g3) routing said identified commands in order of priority based on membership in a command priority group.

27. The method of claim 26, wherein said step (g2) changes priority of said identified commands based on a raise priority signal.

28. A method for handling commands and data associated therewith, comprising:

(a) receiving a command from at least one command source;

(b) storing said command in a command buffer, comprising

(b1) determining whether said command buffer can accept said command; and

(b2) storing said command in said command buffer if said command buffer can accept said command;

(c) freely allocating an unused portion of a data buffer to said command; and

(d) storing data associated with said command in said allocated portion of said data buffer,

(e) storing status information associated with said command in said command buffer, said status information indicating, at least, a command sink to which to route said command; and

(f) identifying, for each command sink, which commands stored in said command buffer to route to said corresponding command sink based on said status information;

(g) routing said identified commands to said command sink; and

wherein

said step (b1) includes the step of,

(b11) determining whether said command depends on performance of a command currently stored by said command buffer; and

said step (e) includes the step of,

(e1) outputting, to said command buffer, dependency information, as part of said status information, corresponding to said command which indicates said dependency if said step (b11) determines that said command depends on performance of a command currently stored by said command buffer; and

said step (g) includes the steps of,

(g1) checking said status information corresponding to said command prior to routing said command, and

(g2) prohibiting routing of said command if said status information indicates said dependency.

29. A method for handling commands and data associated therewith, comprising:

(a) receiving a command from at least one command source;

(b) storing said command in a command buffer;

(c) freely allocating an unused portion of a data buffer to said command; and

(d) storing data associated with said command in said allocated portion of said data buffer; and

(e) storing in said command buffer MESI state information, where MESI stands for modified, exclusive, shared, and invalid, corresponding to each cache line stored in said data buffer.

30. The method of claim 29, further comprising:

(f) updating said MESI state information based on signals received from command sinks.

31. A method for handling commands and data associated therewith, comprising:

(a) receiving a command from at least one command source;

(b) storing said command in a command buffer;

(c) freely allocating an unused portion of a data buffer to said command; and

(d) storing data associated with said command in said allocated portion of said data buffer;

(e) storing status information associated with said command in said command buffer, said status information indicating, at least, a command sink to which to route said command;

(f) identifying, for each command sink, which commands stored in said command buffer to route to said command sink based on said status information;

(g) routing said identified commands to said command sink; and

(h) transferring a command output from a command source directly to said corresponding command sink prior to said command being stored in said command buffer.

32. A transition cache for handling commands and data in a data processing system, comprising:

a fully associative cache having multiple entries to store data required by any of all of a plurality of commands and said transition cache to route and track said data and said any of all of the plurality of commands from any one of all of a plurality of command sources and to any one of all of a plurality of command sinks in the data processing system.

33. An apparatus for handling commands and data associated therewith, comprising:

(a) means for receiving any of a plurality of commands from any of a plurality of command sources;

(b) means for storing said command in a command buffer;

(c) means for freely allocating an unused portion of a data buffer to said command; and

(d) means for storing data associated with said command in said allocated portion of said data buffer;

(e) means for routing and tracking said command between any one of said plurality of command sources to any one of a plurality of command sinks, each of said plurality of command sources capable of sending a command to each of said command sinks and each of said command sinks capable of sending commands to each of said command sources.