Method for arbitrating access to a shared resource

• US 7,404,024 B2
• Filed: 10/14/2004
• Issued: 07/22/2008
• Est. Priority Date: 10/14/2003
• Status: Expired due to Fees

• Current Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SA (STMicroelectronics NV)
• Inventors: Agaesse, Jean-Francois, Ries, Gilles
• Primary Examiner(s): Rinehart; Mark
• Assistant Examiner(s): Spittle; Matthew D
• Application Number:
  US10/966,623
• Publication Number:
  US 20050080967A1
• Time in Patent Office: 1,377 Days
• Field of Search: 710/116, 710/123, 710/240, 710/107, 710/244, 713/400, 713/500, 713/502
• US Class Current: 710/244
• 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 plural electronic elements and accessible according to access cycles clocked by a clock signal, the method comprising:

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

modifying, in a first numerical direction, the first counting value of each element, in synchronization with the clock signal;

modifying, in a second numerical direction opposite to the first numerical direction, 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 the plural electronic elements are simultaneously waiting to access the shared resource, selecting one of the plural electronic elements to access the resource if its first counting value reaches a threshold, and if its first counting value exceeds in the first numerical direction, the first counting values of the other elements that are simultaneously waiting to access the shared resource, wherein;

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

the second counting value of each element is modified in the second numerical direction, by a value equal to the second penalty, every time the element is selected;

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 exceeds in the first numerical direction the second counting values of the other elements having sent an access request; and

the first counting value of each element is modified in the second numerical direction, 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 modified in the second numerical direction, by a value equal to the second penalty, every time the element is selected by virtue of its first counting value.

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 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.

7. The method according to claim 6 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.

8. 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 and second counting values.

9. 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.

10. The method according to claim 9 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 which of the counting values is modified at each access to the data bus.

11. A device for arbitrating access to a resource shared by plural electronic elements, the shared resource being accessible according to access cycles clocked by a clock signal, the device comprising:

first storage elements 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 modifying, in a first numerical direction, the first counting value in synchronization with the clock signal, and modifying, in a second numerical direction opposite to the first numerical direction, the first counting value by a value equal to the first penalty, every time the corresponding element is selected for an access cycle;

a first comparison circuit for supplying, when the plural electronic elements are simultaneously waiting to access the shared resource, a first selection signal designating an element the first counting value of which reaches a threshold, and the first counting value of which exceeds in the first numerical direction the first counting values of the other elements having sent an access request;

second storage elements 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 modifying in the second numerical direction, the second counting value by a value equal to the second penalty, every time the corresponding is selected for an access cycle; and

a second comparison circuit for supplying, when the plural electronic elements are simultaneously waiting to access the shared resource, a second selection signal designating an element the second counting value of which exceeds in the first numerical direction the second counting values of the other elements having sent an access request, wherein the first counting value of each element is modified in the second numerical direction, 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 modified in the second numerical direction, by a value equal to the second penalty every time the element is selected by virtue of its first counting value.

12. The device according to claim 11, 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.

13. The device according to claim 11 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.

14. The device according to claim 11, 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.

15. The device according to claim 11, further comprising a multiplexer circuit structured to output 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.

16. The device according to claim 11, 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.

17. The device according to claim 16 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.

18. The device according to claim 11, 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.

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

20. The device according to claim 19 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.

21. The device according to claim 11 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.

22. A method for arbitrating access to a resource shared by plural electronic elements and accessible according to access cycles clocked by a clock signal, the method comprising:

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

modifying, in a first numerical direction, the first counting values in synchronization with the clock signal;

selecting one of the elements;

modifying, in a second numerical direction opposite to the first numerical direction, the first counting value of the selected element by the first penalty value of the selected element in response to the selecting step;

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;

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;

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

modified in the second numerical direction 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 plural elements are simultaneous waiting for the shared resource;

granting access to the element with the second counting value which exceeds in the first numerical direction the second counting values of the other elements that are waiting, if no element can be selected by virtue of its first counting value;

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.

23. The method according to claim 22 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.

24. The method according to claim 22 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.

25. The method according to claim 22 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.

26. The method according to claim 25 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.

27. The method according to claim 22, 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.