Shared resource arbitration method and apparatus

[0002] The present invention relates in general to shared resource access arbitration and in particular to methods and systems for providing flexibility to match the needs of a plurality of agents or requesters, each attempting to use a shared and common resource, such as memory in a data processing system.

[0003] An arbiter controls the granting of access to a shared resource, such as memory or a communication bus, among a number of agents or requesters. In the case of a memory resource, such requesters could include central processing units (CPUs), screen refresh DMA (direct memory access) processor, 3D drawing block DMA processor, 2D drawing block DMA processor, USB Interface, Ethernet Interface, and so forth. Each of these units contend for the common resource, but the requirements of each agent or requestor may change in accordance with the type of data processing being accomplished at any given time.

[0004] Known current methods for performing the arbitration task typically use complicated and inflexible scheduling techniques or else use extremely simple schemes that do not adapt well to changing system load. Examples of such techniques are designated in the art as “round robin,” fixed priority, multilevel priority, requester priorities that change based on the previous winner of the arbitrated resource, and so forth. One complicated arbitration system has dynamically switched between different ones of some of the aforementioned arbitration schemes depending upon system requirements at a given time.

[0005] It would be desirable to have a simple arbitration scheme that provides inherent flexibility to changing system requirements for a given set of agents or resource requesters while still allowing the addition of further agents where necessary to perform newly assigned tasks.

[0006] The present invention comprises a list driven arbitration method that can operate in at least two modes. In a boot mode, a list is used comprising all possible requesters and the arbiter uses a simple technique, such as “round robin,” to allocate the shared resource during the system initialization process. After initialization, the different or second list used specifies specific agents that will be allowed to access the shared resource. This second list, which typically will designate fewer unique agents than the boot list, can be dynamically changed, both as to agents named and as to interpretation of the list to allow great flexibility in accordance with system load requirements.

[0007] For a more complete understanding of the present invention, and its advantages, reference will now be made in the following Detailed Description to the accompanying drawings, in which:

[0008] FIG. 1 represents a data processing system incorporating an arbiter utilized in an embodiment of the invention;

[0009] FIG. 2 is a block diagram of an arbitration system incorporating an embodiment of the invention;

[0010] FIG. 3 is a flow diagram used in a data processing system incorporating an embodiment of the invention;

[0011] FIG. 4 is an example of a static or boot list utilized in an embodiment of the invention; and

[0012] FIG. 5 is an example of a dynamic or normal operation list used in an embodiment of the invention.

[0013] Referring to FIG. 1, a block 10 represents a data processing system including one or more CPUs, a monitor, one or more disk drives and so forth (none of which are specifically shown as they are well-known in the art). A shared memory resource block 12, within block 10, is specifically shown along with an arbiter 14. Agents or requesters for resource 12 are illustrated as agents 0, 1 and N and are further designated as 16, 18 and 20, respectively. Each of the agents are connected to arbiter 14 by request and grant links and are shown connected to memory 12 by a common bus 22.

[0014] In FIG. 2, the arbiter 14 is shown in more detail as comprising a control logic block 30 supplying signals to a list selector 32 and to a programming interface 34. The list selector 32 is connected to a boot or static list 36, a dynamic or normal operation list 38 and a dash line block 40 representing an optional second dynamic list as may be desirable in some preferred embodiments of the present invention. List selector 32 is also connected to a request match block 42 for supplying thereto priority and buddy agent designators on leads 44 and 46, respectively. Typically, the priority agent designator supplied on lead 44 would be obtained from any of the lists 36, 38 and 40 as determined by the control logic 30 or the programming interface 34. The buddy agent designator would be obtained from the specific entry access slot of the dynamic list being accessed at that time. The control logic 30 supplies a mode select signal on a lead 48 to the request match block 42 to tell the block 42 which, if any, of the possible alternate agents to pick if the higher priority agent is idle. The programming interface block 34 also supplies signals to a default agent block 50, as well as to block 42. As further shown, request match block 42 has request inputs from each of the agents and grant outputs to each of the agents.

[0015] The flow diagram of FIG. 3 starts with a boot mode decision block 70. If the system is still being initialized, the process proceeds to a select next boot agent block 72 from a boot list, such as shown in FIG. 4. Each of the entries of FIG. 4 are sequentially accessed in a “round robin” procedure. In other words, when each of the agents from first to last entry on the list have been checked for access requests in sequential order, the process returns to the first item on the list. A check is made in a decision block 74 to ascertain whether or not that agent has requested access to the shared resource 12. If not, the process proceeds to decision block 76 to determine whether or not initialization is complete and the boot mode has ended. If it is determined in block 74 that the selected agent has requested access, it is granted the access in block 78. When the selected agent has finished with memory 12, the process continues to block 76. If it is determined in block 76 that the system is still in the boot mode, the process returns to block 72 to select the next boot agent in the list. On the other hand, if it is determined in block 76 that initialization is complete, the process returns to the boot mode block 70 and then to a select next priority agent block 80. The process in decision block 82 checks to see if the selected priority agent for that entry has requested access to resource 12.

[0016] Priority agents and associated buddy agents are set forth in an example dynamic or normal list in FIG. 5. It may be noted that, as shown, there is a repeat of agents 1, 2 and 3 for each of 9 entries. Agents 4 and 5 in this example have less priority and are thus granted access only when one of the priority agents is temporarily idle.

[0017] Returning to FIG. 3, it will be noted that if the selected priority agent has requested access, it is granted in block 84. When the agent has completed access, a decision block 86 is entered in one preferred embodiment of the invention. If there is no boot mode change, the process returns from block 86 to 80 for selecting the next priority agent from the list of FIG. 5. If there is a boot change, the process returns to block 70.

[0018] Referring to FIGS. 1, 3 and 5, if the decision block 82 determines that the selected priority agent has not made a request (i.e., it is temporarily idle), a decision block 88 is entered to determine if the buddy mode is enabled in accordance with the programming interface block 34 of FIG. 1. If the buddy mode is enabled, the listed buddy agent for the selected entry is checked. If the selected entry is 2, according to FIG. 5, the priority agent would be agent 3 and the buddy would be agent 5. If agent 5 has requested access, this request is granted in block 90. When agent 5 has completed access to resource 12, the process then proceeds to block 86.

[0019] If the determination in block 88 is NO to either of buddy enablement or to the selected buddy requesting access, the process continues to a decision block 92 where a default enablement is checked along with whether or not the one or more default agents are requesting access. If there is a default enablement, as well as an access request, it will be granted in accordance with block 94 before returning to block 86. If there is either no default enablement or no default agent access request, the process goes from block 92 directly to block 86.

[0020] One or more default agents may be enabled. This enabling notification is supplied by programming interface 34 to both the logic 30 and the request block 42. The arbiter 14 of FIG. 2 illustrates the possibility of primary and auxiliary default agents. It will thus be apparent, from the above, that when the arbiter 14 is using the dynamic list for selecting which agent is to be granted access to the resource 12, great flexibility may be provided in accordance with system requirements at the time. In other words, the selections from the dynamic list may be either just the priority agents or it may select a designated buddy agent in instances when the priority agents are temporarily idle. Further, one or more default agents may be allowed access when all higher priority agents are idle at a given access selection time.

[0021] From the above, it may be determined that in a linear dynamic mode situation where the buddy agent is not enabled, but two default agents are enabled, the access would be determined by the following table for each entry position of the table in FIG. 5.

[0022] When the buddy mode is used and two default agents are enabled, the following table may be used to determine access for each entry position of the table of FIG. 5.

[0023] The arbitration method can operate in several different modes. During initialization, each of the agents that may need access to the shared resource are given access in accordance with a fixed or static list as shown in FIG. 4. During the initialization process, many of these agents will not require access to the given resource and thus the selector will cycle through the list many times while giving access to the shared resource to only a few of the many listed agents. When initialization is complete, this change is detected in the decision block 76 and the list selector 32 stops selecting the static list of block 36 and changes to the dynamic list of 38, an example of which is shown in FIG. 5.

[0024] In the example of FIG. 5, Agents 1, 2, and 3 are shown as “priority” agents that must be guaranteed access to memory. Agents 4 and 5 are lower priority agents that are only granted access to memory if the priority agents do not require access. In such a situation, Agent 6 may be designated in block 50 as a default agent that is very low priority and is only granted access if no primary/buddy agent pair needs to access memory.

[0025] The arbiter of FIG. 2 may have one or more default agents included in the list of FIG. 5 (although not presently shown), which would eliminate the need for block 50 in FIG. 2. The list selector 32 would additionally have default agent outputs when one or more defaults were enabled in accordance with the programming interface 34 and system requirements.

[0026] The flow diagram of FIG. 3 allows for the arbiter to be returned to the boot mode when system conditions are altered and the dynamic list needs to be modified. This change in boot mode condition is detected in decision block 86 of FIG. 3. When the dynamic list modification is complete, this action or step is detected in block 70 and the arbiter (and, accordingly, the list selector 32) returns to assigning access on the basis of the newly modified dynamic list 38

[0027] A further preferred embodiment of the invention is use of a second dynamic list (shown in FIG. 2 as dash line block 40) to help with mode changes. With two dynamic lists, the presently unused or non-selected list can be changed while the other list is being used. Once the non-selected list is correctly modified or updated, the arbiter can be told to ‘switch lists.’ At a graceful or timely point in the selection process, the arbiter changes lists and the previously used list is now available to be modified while the newly selected list is being used for arbitration. This provides a “ping-pong” type operation (i.e., one is used while the other is changed).

[0028] Typically, the list of FIG. 5 will allow for more entries than there are agents. In this manner, it is possible to allocate more access to the shared resource to a given agent by entering that agent in the list more than once. As shown, FIG. 5 illustrates 9 entries. If the buddy mode is not enabled, agent 1 could be listed for every other of the first 8 entries (1, 3, 5, 7) with agents 2 and 3 entered in the intermediate entries 2, 4, 6, and 8. In such a situation, entry 9 may be left blank, or a non-existent agent could be listed and the flow diagram of FIG. 3 would determine that there was no request for that entry. However, agent 1 would be allowed access 50% of the time.

[0029] The list may either be a fixed length as shown, or may contain an end of list designation to specify the last valid entry in the list, whereby the flow diagram returns to the beginning of the list upon detecting the stated end of list designation.

[0030] Although the invention has been described with reference to specific embodiments, these descriptions should not be construed in a limiting sense. Various modifications and rearrangements of the disclosed embodiments, as well as alternative embodiments of the invention, will become apparent to persons skilled in the art upon reference to the description of the invention. It is therefore contemplated that the claims will cover any such modifications or embodiments that fall within the true scope and spirit of the invention.