Methods and structure for dynamic modifications to arbitration for a shared resource

[0001] 1. Field of the Invention

[0002] The present inventions relates to bus arbitration and in particular to a bus arbitration method and structure for using lookup tables for determining and applying parameters of arbitration for control of a shared resource.

[0003] 2. Related Patents

[0004] This patent is related to commonly owned U.S. patent application Ser. No. 10/162,960, filed 5 Jun. 2002, entitled METHODS AND STRUCTURE FOR IMPROVED FAIRNESS BUS ARBITRATION and is related to commonly owned U.S. patent application Ser. No. 10/164,240, filed 5 Jun. 2002, entitled METHODS AND STRUCTURE FOR STATE PRESERVATION TO IMPROVE FAIRNESS IN BUS ARBITRATION, both of which are hereby incorporated herein by reference.

[0005] 3. Discussion of Related Art

[0006] It is generally known in electronic systems to have multiple devices communicating over a shared electronic bus. In general, a first device (usually referred to as a master device) initiates an exchange of information with a second device (usually referred to as a slave device). It is also generally known in the art that a bus structure may permit multiple master devices and multiple slave devices to exchange information. Generally, one master device communicates with one or more slave devices to the exclusion of other master and slave devices in the system. In such a circumstance, a first master device desiring use of the bus for communication with a slave device must first obtain temporary exclusive control over the shared bus structure. A master device obtains temporary exclusive control of the shared bus by requesting the bus structure and awaiting an acknowledgment signal indicative of granting of the requested temporary exclusive access to the shared bus.

[0007] Typically, an arbiter device coupled to the shared bus structure receives a request for temporary exclusive control of the bus from each of several master devices and selects the next master device to obtain the requested temporary exclusive control. The arbiter receives request signals and returns grant (acknowledgment) signals to master devices to indicate request and granting of temporary exclusive control, respectively. This process is typically referred to as the bus arbitration. A number of well-known commercially applied bus structures support such multiple master devices sharing control of a bus. Though the specific timing and signals involved in arbitration may vary, all such buses support arbitration in some form.

[0008] It is common in the art for an arbiter device to utilize any of several well-known techniques for determining the next requesting master device to be granted temporary exclusive control of the shared bus structure. One simple technique is often referred to as “round-robin” in that each device may be granted temporary exclusive control of the shared bus in sequential order defined by an index number—usually a master device ID. When the last master device ID is granted temporary exclusive control over the bus, the first master device is again eligible for exclusive bus control. This sequential “round-robin” technique assures that each master device has a roughly equal opportunity to obtain temporary exclusive control of the shared bus structure.

[0009] Another common bus arbitration technique is to assign a priority to each master device. At any given point, a master device with the highest priority requesting temporary exclusive control of the shared bus will be granted control over the bus. Still other techniques combine features of both a priority-based scheme and round-robin arbitration techniques. For example, each master device may be assigned a priority and all master devices having the same particular priority level share the bus using a round-robin technique.

[0010] Strict round-robins arbitration generally provides equal access to the shared bus for all master devices. Standard priority-based bus arbitration algorithms are effective at assuring that the highest priority master devices can rapidly access the shared bus as compared to lower priority devices. However a problem with priority-based scheme is that the lowest priority devices may be effectively “starved” from access to the bus due to high frequency bus requests by higher priority master devices. By contrast, round-robin arbitration techniques preclude high priority master devices from obtaining necessary frequent access to a shared bus.

[0011] Hybrid techniques, as noted above, that combine features of both round-robin arbitration and priority-based arbitration still produce unfair results in some circumstances. For example, presume a plurality of master devices are requesting the bus all at the same first priority level (i.e., applying round-robin techniques within that priority level). A higher priority master device then requests and is granted the bus (since it is a higher priority than the plurality of devices at the first priority level). When the higher priority device relinquishes the bus, the plurality of devices at the first priority level again arbitrate using round-robin techniques.

[0012] The particular arbitration structures and methods appropriate to a system are determined by a system designer with consideration of parameters and circumstances of the particular system. Present arbitration techniques are generally algorithmic in nature and thus implemented as circuits performing a fixed function determined by the designer of the arbiter. This presents a problem where it is desirable to modify parameters of the arbitration technique after the arbiter is designed. Such changes require modification to the arbiter circuit design to modify the desired functionality of the arbiter. Further, it may be desirable to modify parameters of the arbitration process in response to measurement of operation of the system. Such dynamic alterations are not possible in present arbiter designs where a fixed circuit determines all parameters of the arbitration process.

[0013] It is evident from the above discussion that a need exists for improved flexibility in designing arbitration processes and in particular a need exists to enable flexible, dynamic alterations to arbitration processes in a system.

[0014] The present invention solves the above and other problems, thereby advancing the state of the useful arts, by providing an arbiter structure and associated arbitration methods that are easily modified. Parameters of the arbitration process are defined by table entries. An appropriate table entry is selected based on status of selected predicates evaluated within the system. Predicates are defined that evaluate common attributes and signals of a system design. Each predicate evaluates to a binary encoded value comprising one or more binary values. The binary values are selected for each master device (also referred to herein as “channel”) participating in the arbitration structure and process. The present binary values of the selected predicates are then combined to form an index into a lookup table to determine the associated channel's priority in a priority-based arbitration circuit. The lookup table may be stored in any suitable memory structure including register or latch arrays or standard memory components such as RAM or ROM.

[0015] The table lookup feature allows the dynamic adjustment of priorities for channels involved in the arbitration process. Modification of the table entries obviates the need for re-design of the arbiter circuit or the associated system board to accommodate changes in the arbitration structure and logic for the system. Simple alteration of the selection of predicates for each channel permits further flexibility in the design of a system without requiring changes to the arbiter circuit design per se.

[0016] The improved flexibility realized in application of the structures and methods of the present invention enhances the re-usability of a standard arbiter circuit design. A standardize arbiter circuit may be re-used in numerous applications by simply modifying the parameter selections and modifying the contents of the lookup table.

[0017] A first feature of the invention therefore provides an apparatus in a system having a shared resource shared by multiple channels, the apparatus comprising: an index value generator associated with each channel of the multiple channels for determining an index value from input signals associated with the system; a lookup table associated with each channel and coupled to the index value generator for generating an arbitration priority value associated with the index value; and an arbiter coupled to each lookup table associated with each channel to arbitrate for control of the shared resource among the multiple channels in accordance with the arbitration priority values generated by each the lookup table.

[0018] Another aspect of the invention further provides that the index value generator comprises: a predicate selector for selecting predicates to be applied to the input signals; and a predicate evaluator for evaluating selected predicates by applying the input signals to the selected predicates.

[0019] Another aspect of the invention further provides a second signal source for generating a second signal value, such that the predicate evaluator generates the binary value as a function of the input signal and the second signal value.

[0020] Another aspect of the invention further provides that the second signal source comprises: a memory for storing the second signal value.

[0021] Another aspect of the invention further provides that the lookup table comprises a register array and such that the index value selects a corresponding register of the register array.

[0022] Another aspect of the invention further provides that the lookup table comprises a latch array and such that the index value selects a corresponding latch of the latch array.

[0023] Another aspect of the invention further provides that the lookup table comprises a memory and such that the index value accesses a corresponding location of the memory.

[0024] Another feature of the invention therefore provides a system comprising: a shared resource; a plurality of channels; an arbiter coupled to each of the plurality of channels and coupled to the shared resource to coordinate access by the plurality of channels to the shared resource such that the arbiter includes: a predicate computation element associated with each channel of the plurality of channels for determining an index value for each channel based on attributes of the system; and a channel selection element coupled to each the predicate computation element to select a next channel to be granted access to the shared resource based on the index value for each channel.

[0025] Another aspect of the invention further provides that the arbiter further includes: a lookup table coupled between each the predicate computation element and the channel selection element to translate the index value determined by each the predicate computation element to a priority value, such that the channel selection element selects the next channel based on the priority value of each the channel.

[0026] Another feature of the invention provides a method in a system having an arbiter coupling a plurality of channels to a shared resource to coordinate access to the shared resource by the plurality of channels, the method for improved flexibility in arbitration comprising the steps of: evaluating at least one attribute of the system; determining an index value for each channel of the plurality of channels according to a predicate function of the at least one attribute; and selecting a next channel of the plurality of channels to receive access to the shared resource in accordance with each the index value.

[0027] Another aspect of the invention further provides that the step of evaluating includes the step of: detecting signal values within the system.

[0028] Another aspect of the invention further provides that a predicate function is associated with each channel of the plurality of channels and such that the step of determining comprises the step of: determining an index value for each channel according to a predicate function corresponding to each channel.

[0029] Another aspect of the invention further provides that the step of: using the index value with a lookup table to determine a priority value corresponding to the index value, such that the step of selecting comprises the step of: selecting the next channel in accordance with each the priority value.

[0030] Another aspect of the invention further provides that the system includes a plurality of predicate functions and such that the method further comprises: selecting a predicate function for each channel, such that the step of determining comprises the step of: determining the index value according to the selected predicate function.

[0034] While the invention is susceptible to various modifications and alternative forms, a specific embodiment thereof has been shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that it is not intended to limit the invention to the particular form disclosed, but on the contrary, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

[0035] FIG. 1 is a block diagram of a system 100 having multiple master devices 104 through 110 and multiple slave devices 112 through 116 (shared resources) coupled to a shared system bus 152. Arbiter 102 includes the improvements of the present invention as parameters and associated lookup tables 103 used to flexibly define the operation of the arbiter. Those of ordinary skill in the art will recognize that slave devices 112 through 116 represent any shared resource in such a system. For example, a shared resource may be an I/O controller device coupled to a bus such that a master device must obtain temporary exclusive control of the bus and controller as a shared resource. Or, for example, the shared resource may be a memory controller for controlling a memory subsystem coupled through the memory controller to a plurality of master devices. Numerous other examples of slave devices (shared resources) will be readily apparent to those of ordinary skill in the art.

[0036] Request and grant signals associated with each master device 104 through 110 are exchanged with arbiter 102 via bus 150. In general, each master device 104 through 110 (also referred to herein as “channels”) requests temporary exclusive control of bus 152 by applying a bus request signal to its associated signal path of bus 150. The arbiter 102 receives all such bus request signals from all master devices 104 through 110 and selects the next master device presently requesting temporary exclusive ownership of bus 152 to which the requested ownership will be granted. A grant signal is applied to an associated signal path of bus 150 to grant the request of the next selected master device.

[0037] As noted above, any of several well-known arbitration techniques may be used within arbiter 102. In a priority-based arbitration architecture, each master devices is associated with a particular priority level. When multiple master devices simultaneously request temporary ownership of bus 152, arbiter 102 selects the highest priority such requesting master device to receive the requested temporary exclusive ownership of bus 152.

[0038] As noted above, in such a priority-based arbitration architecture, the association of a device with a priority level is typically selected by the designer at the time of the system design. Design considerations include a number of factors whereby a designer determines the appropriate prioritization of the various channels (master devices). Further as noted above, modifications to such a fixed arbitration architecture are difficult in that they require re-design of the arbiter circuit and potentially changes to the system board. A more flexible architecture is provided by the present invention wherein parameters involved in prioritization determinations, predicates to evaluate the parameters and priority values resulting from such evaluations may be dynamically selected and altered by a designer without requiring re-design of the arbiter circuits or system board.

[0039] Those skilled in the art will recognize that the architecture depicted in FIG. 1 is intended as exemplary of a wide variety of bus architectures that may benefit from the improved fairness techniques and structure of the present invention. In particular, those skilled in the art will recognize that any number of master devices may be used in conjunction with such a system structure limited only by the specifications of the particular system bus selected by the designer. Further, any number of slave devices (shared resources), limited only by the requirements and specifications of the selected system bus, may be present in such a system 100.

[0040] Still further, those of ordinary skill in the art will recognize that any of several well-known system bus architectures may be selected for a system bus 152 and arbitration signals on bus 150. In particular, in one exemplary preferred embodiment, bus 150 and 152 together may be an AMBA AHB compliant high-performance system bus architecture. A number of other common, commercial bus structures as well as customized proprietary bus structures may also benefit from the features of the present inventions. Those skilled in the art will further recognize that signals applied to bus 150 and system bus 152 are typically integrated in a single bus structure rather than two distinct bus structures as depicted in FIG. 1. Signals applied to bus 150 are shown in FIG. 1 as separate from system bus 152 only to simplify the description in that signals applied to bus 150 relate exclusively to bus arbitration processing to exchange signals between master devices 104 through 110 and arbiter 102.

[0041] FIG. 2 is a block diagram providing additional details of an exemplary preferred embodiment of the present invention for enhancing flexibility in application of a priority-based arbiter. Parameters associated with determining the priority for each channel are provided as inputs to the enhanced arbiter. The particular parameters of a particular arbiter application will be specific to that system. Numerous examples of signals relevant to determining priority of a channel will be readily apparent to those of ordinary skill in the art. Exemplary of such parameter signals might be FIFO status where a channel includes a FIFO for exchanging data with the shared resource controlled by the arbiter (i.e., FIFO full, FIFO empty, FIFO near full, etc.). Other examples might include the memory bank presently active where the shared resource managed by the arbiter is a memory device having multiple banks of memory. The presently active bank of memory may be an important factor in adjusting the priority of channels participating in arbitration for control of the shared memory resource. Such dynamic adaptation of the priorities may be beneficial in an arbitration structure to favor a channel that is requesting access to the same presently active bank of the shared memory resource.

[0042] Parameters pertaining to channel 1 are applied as signals on path 240. Parameter computation and index generator element 200 receives all such parameters associated with determining the priority of channel 1 and determines an index value from the present value of the parameter signals applied to input path 240. The index value so determined is applied via path 250 to lookup table 210 which, in turn, selects a priority value from a lookup table location identified by the index value. The priority value so determined from lookup table 210 is then applied via path 260 to channel selection element 220. Channel selection element 220 may use any of several well-known techniques to select a channel, including strict priority encoding as well as priority in combination with other techniques such as round-robin or improved fairness techniques as described in related patent applications incorporated herein by reference. In preferred embodiments, the priority related values determined by operation of elements 200 and 210 are used as at least one input to the channel selection processing of element 220.

[0043] Parameter computation and index generator element 202 similarly receives parameters on path 242 and determines an index value applied via path 252 to lookup table 212. Lookup table 212 then applies a present priority value derived from the lookup table location so identified and applies the priority value via path 260 to channel selection 220. In like manner parameters associated with Channel “n” are applied to path 244 as input to parameter computation and index generator element 204. The index value to so determined by element 204 is then applied via path 254 as an input to lookup table 214. Lookup table 214 then selects the identified priority value and applies it as an output on path 264 for processing by channel selection 220. Channel selection 220 receives the priority values for each channel, selects the channel indicating the highest priority and applies the selected channel identifier to path 266 for further processing within the arbiter.

[0044] Details of the structure of a parameter computation and index generator elements 200, 202 and 204 is provided further herein below with respect to the FIG. 3. Lookup table 210, 212 or 214 may be implemented as any of several equivalent structures including, a register array, a latch array, or a memory device including, for example, a RAM or ROM memory component. An index value applied to the lookup table structure (210, 212 or 214) selects an element within the lookup table containing a priority value corresponding to the generated index value. Where lookup table 210, 212 or 214 is implemented as a register array or latch array, the index value applied as an input to the lookup table directly selects one of the various registers or latches. The priority value stored in the selected register or latch is then applied as the output of the corresponding lookup table element (210, 212 or 214). Where lookup table 210, 212 or 214 is implemented as a standard memory component (i.e., a RAM or ROM memory element), the index value generated and applied as an input to the lookup table is used as a memory location to retrieve the priority value stored in the addressed memory element.

[0045] Those of ordinary skill in the article readily recognize a variety of lookup table structures that may be used in conjunction with the present invention. Further, those of ordinary skill in the art will recognize a variety of priority encoding techniques to receive the priority values associated with each of the channels participating in the arbitration and for selecting an appropriate channel for granting of access to the shared resource. Details of such a priority encoder and other aspects of a priority-based arbiter are well-known to those of ordinary skill in the art. Exemplary priority encoding schemes and arbiter structures are presented in the related applications incorporated herein.

[0046] Further, those of ordinary skill in the art will recognize that any number of channels may be associated with such an architecture as required for a particular system application. Still further, any number of parameters may be associated with the parameter computation and index generation elements 200, 202 and 204. FIG. 2 is therefore intended merely as representative of a wide variety of equivalent embodiments of such an architecture providing flexible definition of arbitration parameters and priority determinations therefrom.

[0047] FIG. 3 is a block diagram providing additional details of the structure of a parameter computation and index generation element (200, 202 or 204 of FIG. 2). Predicate A evaluator 302 applies parameter signals received on path 240 to the first predicate (predicate A) for evaluating the applied parameters and generating and output index value. As discussed further herein below, a predicate may be any desired function to evaluate a received input parameter value. Numerous examples of typical predicate evaluations are provided further herein below.

[0048] The index value generated by evaluation of predicate A evaluator 302 is applied via path 352 to form a portion of index value 320. If the evaluation of the predicate defined by predicate A evaluator 302 requires additional parameter values, such parameter values are supplied by element 304 associated with evaluator 302. These other parameter values may include constant or threshold values used for comparison with input parameter signals in evaluating the predicate. As noted above, such parameter values may be stored in a programmable element so that parameter values may be adapted dynamically in response to operation of the system. Examples of such other parameter values are discussed herein below along with exemplary predicate evaluations.

[0049] In like manner, predicate B evaluator 306 applies input signals from path 240 to a defined predicate for generating an index value applied to output path 356 (forming a second portion of index value 320). As above, additional parameter values stored in element 308 may be used by predicate B evaluator 306 to generate the output index value. Similarly, predicate C evaluator 310 evaluates input signals on path 240 along with other parameter values retrieved from element 312 to generate an index value applied to path 360.

[0050] Index value 320 applies the concatenated partial index values generated by predicate evaluators 302, 306 and 310 to generate a composite index value 320 for application to path 250 and, in turn, for application to an associated lookup table as discussed above.

[0051] Those of ordinary skill in the art will readily recognize that any number of predicates may be associated with such a parameter computation and index generator element 200. Further, those of ordinary skill in the art will recognize that the output index value generated by each predicate evaluator may be a single bit value (i.e., a Boolean value) or may be a multi-bit value representing additional portions of the index value.

[0052] Typical predicates include the ability to test input parameter signals applied to the predicate evaluator against other values or against any arbitrary Boolean or arithmetic function. Examples of such predicates that may be useful in a variety of systems include:

Exemplary predicate “A”

OUTPUT VALUE←input bit vector==constant

[0053] This exemplary predicate compares an input parameter bit vector against a constant parameter. The arbitrary constant parameter value is preferably retrieved from the parameter storage element associated with the predicate evaluator for this predicate.

Exemplary predicate “B”

OUTPUT VALUE←input bit vector>threshold

[0054] This exemplary predicate compares an input parameter bit vector against a threshold parameter. The arbitrary threshold parameter value is preferably retrieved from the parameter storage element associated with the predicate evaluator for this predicate.

Exemplary predicate “C”

OUTPUT VALUE←input bit

[0055] This exemplary predicate returns the state of the input bit signal as its output value.

Exemplary predicate “D”

OUTPUT VALUE←combinatorial function of input signals 1 . . . x

[0056] This exemplary predicate returns a combinatorial logic function applied to any number of input signal values. The logic function may be any combinatorial logic function useful for the arbiter application.

Exemplary predicate “E”

OUTPUT VALUE←input bit vector

[0057] This exemplary predicate returns the state of the input bit vector signal as its output value. The input vector may be for example a state vector or a counter value.

[0058] Those of ordinary skill in the art will readily recognize a wide variety of predicate functions such as those described above for use in particular system applications. In essence, any evaluation function that may be implemented in combinatorial logic may be implemented as a predicate to be applied to a set of input signals to generate a corresponding output signal.

[0059] Using exemplary predicates as described above, the following describes a simple exemplary system applying the features of the present invention to enhance flexibility in arbiter design. In the following two channel example, it should be assumed that the desired arbiter function would perform a function algorithmically described as follows:

[0060]

	if (channel 2 input vector “B” > threshold “B”) // predicate “B”
	select channel 2
	else
	if (channel 1 bit vector “A” == constant “A”) // predicate “A”
	select channel 1
	else
	if (channel 2 bit “C”) // predicate “C”
	select channel 2
	else if (channel 1 signal “C”) // predicate “C”
	select channel 1
	endif
	endif
	endif
Expressed using the index generation and lookup table structures of the present
invention, the index generation would generate a 2-bit index value
(channel—1—index[1:0] and channel—1—index[1:0]) as follows:
	channel—1—index[0] ← input bit A == constant A (apply predicate “A”)
	channel—1—index[1] ← input signal C (apply predicate “C”)
	channel—2—index[0] ← input signal B > threshold B (apply predicate “B”)
	channel—2—index[1] ← input signal C (apply predicate “C”)

The lookup tables for this example would appear as follows:

[0061]

	Output Priority
	Applied Index Channel 1
	00	1
	01	3
	10	1
	11	3
	Applied Index Channel 2
	00	2
	01	4
	10	2
	11	4

[0062] Those of ordinary skill in the art will recognize that the above example is not intended to limit the invention to a particular arbitration application. Rather, a wide variety of arbitration applications may be encoded into the structures and methods of the present invention.

[0063] While the invention has been illustrated and described in the drawings and foregoing description, such illustration and description is to be considered as exemplary and not restrictive in character, it being understood that only the preferred embodiment and minor variants thereof have been shown and described and that all changes and modifications that come within the spirit of the invention are desired to be protected.