Self-organizing hardware processing entities that cooperate to execute requests

• US 6,611,906 B1
• Filed: 04/30/2000
• Issued: 08/26/2003
• Est. Priority Date: 04/30/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: McAllister, Curtis R., Douglas, Robert C.
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US09/560,928
• Time in Patent Office: 1,213 Days
• Field of Search: 711/141, 711/144, 711/151, 711/145, 711/156, 711/120, 711/121, 711/168, 711/153, 711/152, 710/5, 710/39, 710/22-24, 710/107, 710/263, 370/412, 370/383, 707/100, 709/205, 709/102, 709/104, 709/105
• US Class Current: 711/168
• CPC Class Codes: G06F 13/1673 using buffers

Abstract

A hardware-based linked list queues memory transactions in a memory controller. The memory controller includes a plurality of memory controller agents. Each agent has a head flag, a tail flag, and a next agent field, thereby allowing the agents to be arranged into linked lists. Memory transactions are received from cacheable entities of a computer system at an incoming memory transaction dispatch unit via an interconnection fabric. The incoming transactions are then presented to the plurality of agents. For each incoming read transaction, one of the agents will accept the transaction. If there are pending memory read transactions for the memory line, then the accepting agent joins a linked list of agents that are queued up to access that memory line. The accepting agent drives its index out onto a bus that connects all agents. One agent in the linked list will have its tail flag set, and that agent will clear its tail flag and latch into its next agent field the index provided by the accepting agent. Also, the accepting agent will set its tail flag to indicate that it is now at the end of the linked list. When the head agent finishes a transaction, the head agent advances the list by notifying the next agent that it is now the new head agent. The old head agent then clears a valid flag, indicating that it can now accept a new transaction, and the new head agent sets its head flag.

Claims

1. A number of hardware processing entities that cooperate together to organize themselves into linked lists, each cooperating hardware processing entity comprising:

a coupling to a bus by which the hardware processing entity intercommunicates with other hardware processing entities;

stored data that includes flags to indicate whether or not the hardware processing entity is currently executing a request, an identifier that identifies the request, a stored flag indicating whether or not the hardware processing entity occupies a head position within a linked list, a stored flag indicating whether or not the hardware processing entity occupies a tail position within a linked list, and a link identifying a next hardware processing entity within a linked list in which the hardware processing entity currently resides; and

control logic that

recognizes requests broadcast to the bus,

accepts requests identified by the stored data, and

executes those accepted requests that the hardware processing entity identifies as directly executable, and, for those accepted requests that the hardware processing entity identifies as not directly executable, recruits another hardware processing entity to execute the accepted not directly executable requests, the other hardware processing entity cooperating with the hardware processing entity to link itself to a linked list associated with a subject of the request.

2. The number of hardware processing entities of claim 1 wherein, by executing those requests that the hardware processing entity identifies as directly executable, and by recruiting another hardware processing entity to execute those accepted requests that the hardware processing entity identifies as not directly executable, the number of hardware processing entities cooperate to organize themselves into linked lists in orders that ensure a proper overall execution order for requests directed to the hardware processing entities.

3. The number of hardware processing entities of claim 2 wherein the linked lists on which the number of hardware processing entities cooperate to organize themselves are never searched, and wherein a hardware processing entity adds itself to a linked list in order to execute a request in two or less clock cycles.

4. The number of hardware processing entities of claim 1 wherein, when the hardware processing entity completes execution of a request, the hardware processing entity removes itself from a linked list, promoting a next hardware processing entity on the linked list to a head position, allowing the next hardware processing entity to execute a next request for which the next hardware processing entity was recruited to execute.

5. The number of hardware processing entities of claim 4 wherein a hardware processing entity removes itself from a linked list following execution of a request in two or less clock cycles.

6. A method for organizing cooperating hardware processing entities that process requests, the method comprising:

providing a number of hardware processing entities that cooperate to process requests, each hardware processing entity comprising

a coupling to the communications medium,

stored data, and

control logic that

recognizes requests broadcast to communications medium,

accepts requests identified by the stored data, and

executes those accepted requests that the hardware processing entity identifies as directly executable, and, for those accepted requests that the hardware processing entity identifies as not directly executable, recruits another hardware processing entity to execute the accepted not directly executable requests, the other hardware processing entity cooperating with the hardware processing entity to link itself to a linked list associated with a subject of the request; and

coupling the number of hardware processing entities to a communications medium by which the hardware processing entities intercommunicate with one another other;

wherein, by executing those requests that the hardware processing entity identifies as directly executable, and by recruiting another hardware processing entity to execute those accepted requests that the hardware processing entity identifies as not directly executable, the number of hardware processing entities cooperate to organize themselves on linked lists in orders that ensure a proper overall execution order for requests directed to the hardware processing entities.

7. The method of claim 6 further including never searching the linked lists on which the number of hardware processing entities cooperate to organize themselves.

8. The method of claim 7 wherein a hardware processing entity adds itself to a linked list in order to execute a request in two or less clock cycles.

9. The method of claim 6 wherein, when a hardware processing entity completes execution of a request, the hardware processing entity removes itself from a linked list, promoting a next hardware processing entity on the linked list to a head position, and thus allowing the next hardware processing entity to execute a next request for which the next hardware processing entity was recruited to execute.

10. The method of claim 9 wherein a hardware processing entity removes itself from a linked list following execution of a request in two or less clock cycles.