Method for arbitrating access to a shared resource

• US 20050080967A1
• Filed: 10/14/2004
• Published: 04/14/2005
• Est. Priority Date: 10/14/2003
• Status: Active Grant

• Current Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Inventors: Agaesse, Jean-Francois, Ries, Gilles
• Granted Patent: US 7,404,024 B2
• Time in Patent Office: Days
• US Class Current: 710/240
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines

Abstract

A method for arbitrating access to a resource shared by several electronic elements. Each element is allocated a first counting value and a first penalty, the first counting value is decremented in synchronization with a clock signal, and is incremented by a value equal to the first penalty every time the element is selected for an access cycle. When several elements are simultaneously waiting to access the shared resource, an element is selected to access the resource if its first counting value is lower than or equal to a determined threshold, and is lower than the first counting values of the other elements having sent an access request.

Claims

1. A method for arbitrating access to a resource shared by several electronic elements and accessible according to access cycles clocked by a clock signal, wherein each element wishing to access the shared resource sends an access request, the method comprising:

allocating each element a first counting value and a first penalty;

decrementing or incrementing the first counting value of each element, in synchronization with the clock signal;

incrementing or decrementing the first counting value of each element,, by a value equal to the first penalty, every time the element is selected for an access cycle; and

when several elements are simultaneously waiting to access the shared resource, selecting an element to access the resource if its first counting value is lower than or equal, or respectively higher than or equal, a determined threshold, and if its first counting value is lower, or respectively higher, than the first counting values of the other elements having sent an access request.

2. The method according to claim 1 wherein an element is selected whatever its first counting value, if it is the only element requesting access to the shared resource.

3. The method according to claim 1 wherein, when two elements likely to be selected have the same first counting value, the element to be selected is designated by applying a predetermined selection rule.

4. The method according to claim 1 wherein the access requests may concern several successive access cycles and, when an element having sent an access request concerning several access cycles is selected, access to the shared resource is granted to the element for the number of access cycles requested, even if, after the first access cycle of the element, the element can no longer be selected by virtue of its first counting value.

5. The method according to claim 4 wherein the first counting value of an element is inhibited when the element does not send an access request for a determined number of access cycles.

6. The method according to claim 1 wherein:

each element is allocated a second counting value and a second penalty;

the second counting value of each element is incremented, or decremented, by a value equal to the second penalty, every time the element is selected; and

when several elements are simultaneously waiting to access the shared resource, if no element can be selected by virtue of its first counting value, the element selected is the one the second counting value of which is lower, or respectively higher, than the second counting values of the other elements having sent an access request.

7. The method according to claim 6 wherein the second counting value of an element is maintained at a determined value when the element does not send an access request for a determined number of access cycles.

8. The method according to claim 7 wherein the second counting value of an element that has not sent any access request for a determined number of access cycles, is maintained at the determined value equal to the lowest second counting value of the elements sending access requests.

9. The method according to claim 6 wherein the first counting value of each element is incremented, or respectively decremented, by a value equal to the first penalty, every time the element is selected by virtue of its second counting value, and reciprocally the second counting value of each element is also incremented, or respectively decremented, by a value equal to the second penalty, every time the element is selected by virtue of its first counting value.

10. The method according to claim 6, wherein the access requests may concern several successive access cycles and, when an element having sent an access request concerning several access cycles is selected, access to the shared resource is granted to the element for the number of access cycles requested, even if, after the first access cycle of the element, the element can no longer be selected by virtue of its first and second counting values.

11. The method according to claim 1, applied to a device wherein the shared resource is a data bus linked to one or several peripheral circuits through an access multiplexer circuit, the electronic elements being master circuits relative to the peripheral circuits.

12. The method according to claim 11 wherein the access multiplexer circuit supplies control signals designating the master circuit selected at each access cycle, and wherein the control signals are used to identify the counting values that must be decremented or incremented at each access to the data bus.

13. A device for arbitrating access to a resource shared by several electronic elements, the shared resource being accessible according to access cycles clocked by a clock signal, each element wishing to access the shared resource having to send an access request, the device comprising:

first registers for storing, for each element, a first penalty individually allocated to each element;

first counters for individually allocating to each element a first counting value, and for decrementing, or incrementing, the first counting value in synchronization with the clock signal, and incrementing, or respectively decrementing, the first counting value by a value equal to the first penalty, every time the corresponding element is selected for an access cycle; and

a first comparison circuit for supplying, when several elements are simultaneously waiting to access the shared resource, a first selection signal designating an element the first counting value of which is lower than or equal, or respectively higher than or equal, to a determined threshold, and the first counting value of which is lower, or respectively higher, than the first counting values of the other elements having sent an access request.

14. The device according to claim 13, further comprising:

means for selecting an element that is the only element requesting access to the shared resource, whatever the first counting value of the element is.

15. The device according to claim 13 wherein, when two elements have the same first counting value, the first comparison circuit is arranged for selecting one of these elements according to a predetermined selection rule.

16. The device according to claim 13, further comprising a circuit for managing the first counters to inhibit the first counting value of an element that has not sent an access request for a determined number of access cycles.

17. The device according to claim 13, further comprising:

second registers for storing, for each element, a second penalty individually allocated to each element;

second counters for individually allocating to each element a second counting value, and for incrementing, or decrementing, the second counting value by a value equal to the second penalty, every time the corresponding element is selected for an access cycle; and

a second comparison circuit for supplying, when several elements are simultaneously waiting to access the shared resource, a second selection signal designating an element the second counting value of which is lower, or respectively higher, than the second counting values of the other elements having sent an access request.

18. The device according to claim 17 wherein the first and second selection signals are applied to a multiplexer circuit the output of which supplies a general selection signal equal to the second selection signal when the first comparison circuit does not find an element to select, otherwise being equal to the first selection signal.

19. The device according to claim 17 wherein the first counting value of each element is incremented, or respectively decremented, by a value equal to the first penalty, every time the element is selected by virtue of its second counting value, and reciprocally the second counting value of each element is incremented, or respectively decremented, by a value equal to the second penalty every time the element is selected by virtue of its first counting value.

20. The device according to claim 17, further comprising a circuit for managing the second counters to maintain the second counting value of an element at a determined value when the element does not send an access request for a determined number of access cycles.

21. The device according to claim 20 wherein the circuit for managing the second counters maintains the second counting value of an element that has not sent any access request for a determined number of access cycles, at a value equal to the lowest second counting value of the elements sending access requests.

22. The device according to claim 17, further comprising a circuit for managing access requests in bursts that is arranged for maintaining the selection of a selected element, even if, after the first access cycle granted to the element, this element cannot be selected by virtue of its first or second counting value.

23. The device according to claim 17, further comprising an access multiplexer circuit for linking a selected element to the shared resource at each access cycle.

24. The device according to claim 23 wherein the access multiplexer circuit supplies control signals designating the master circuit selected at each access cycle, the control signals being applied to the counters as load signals, for loading the first or the second penalty.

25. The device according to claim 17 wherein the shared resource is a bus linked to one or several peripheral circuits, the electronic elements being master circuits relative to the peripheral circuits.

26. A method for arbitrating access to a resource shared by several electronic elements and accessible according to access cycles clocked by a clock signal, wherein each element wishing to access the shared resource sends an access request, the method comprising:

allocating to the elements respectively first counting values and respectively first penalty values;

decrementing or incrementing the first counting values in synchronization with of the clock signal;

selecting one of the elements;

incrementing the first counting value of the selected element by the first penalty value of the selected element in response to the selecting step if the first counting values are decremented in synchronization with the clock signal;

decrementing the first counting value of the selected element by the first penalty value of the selected element in response to the selecting step if the first counting values are incremented in synchronization with the clock signal;

when plural of the elements are waiting to be selected;

determining whether any of the waiting elements has a first counting value that has attained a minimum access threshold;

if there is only one of the waiting elements that has a first counting value that has attained the minimum access threshold, then selecting the one element; and

if there are plural of the waiting elements having first count values that have attained the minimum access threshold, then selecting one of the waiting elements based on a comparison of the first counting values of the waiting elements with each other.

27. The method according to claim 26 wherein, when two waiting elements have the same first counting value, then selecting one of the two waiting element having the same first counting value by applying a predetermined selection rule.

28. The method according to claim 26 wherein the first counting value of an element is inhibited when the element does not send an access request for a determined number of access cycles.

29. The method according to claim 26 further comprising:

allocating to the elements a second counting value and a second penalty value;

incrementing or decrementing the second counting value of each element by the second penalty value of the element in synchronization with the clock signal, each time the element is selected; and

when several elements are simultaneously sending access requests for the shared resource;

granting access to the element with the second counting value which is lower than the second counting values of the other elements that are sending an access request, if no element can be selected by virtue of its first counting value and the second counting values are decremented in synchronization with the clock signal each time an element is selected; and

granting access to the element with the second counting value which is higher than the second counting values of the other elements that are sending an access request, if no element can be selected by virtue of its first counting value and the second counting values are incremented in synchronization with the clock signal each time an element is selected.

30. The method according to claim 29 wherein the second counting value of an element is maintained at a determined value when the element does not send an access request for a determined number of access cycles.

31. The method according to claim 30 wherein the second counting value of an element that has not sent any access request for a determined number of access cycles, is maintained at the determined value equal to the lowest second counting value of the elements sending access requests.

32. The method according to claim 29 wherein the first counting value of each element is incremented by a value equal to the first penalty, every time the element is selected by virtue of its second counting value and the first counting value is decremented in synchronization with each cycle of the clock;

and the second counting value of each element is incremented by a value equal to the second penalty, every time the element is selected by virtue of its first counting value and the second counting value is decremented each time the element is selected by virtue of its first counting value;

or

the first counting value of each element is decremented by a value equal to the first penalty, every time the element is selected by virtue of its second counting value and the first counting value is incremented in synchronization with each cycle of the clock; and

the second counting value of each element is decremented by a value equal to the second penalty, every time the element is selected by virtue of its first counting value and the second counting value is incremented each time the element is selected by virtue of its first counting value.

33. The method according to claim 29, wherein the access requests may request a plural number of successive access cycles and, when an element having requested a plural number of successive access cycles is selected, access to the shared resource is granted to the element for the number of access cycles requested, even if, after the first access cycle of the element, the element can no longer be selected by virtue of its first and second counting values.