Field of the Invention:
The present invention relates to real-time shared-resource transactions. More specifically, the present invention relates to client devices that periodically request access to the shared resource.

Background and Prior Art:
The problem of selecting which client gains access to a memory device such as a DRAM or a DDR or a SDDR or any other similar type of memory is the same basic problem as solved in real time systems commonly used for scheduling tasks on a CPU, or scheduling access to a shared hardware resource. The theories in this area have been under development since the early 70''s, and are reasonably advanced. While there are a number of approaches to scheduling, the simplest and possibly most robust is a static priority based schedule based on Rate Monotonic Scheduling.

One of such documents that describe an arbitration method is EP 1 398 696, contents of which is incorporated herein as reference.

The limitations and disadvantages of conventional and traditional approaches of arbitration are apparent to one of skill in the art, including for example, the limitation of the arbitration method to effectively handle request from multiple clients with disparate traffic characteristics and hence, there exists a strong need to provide arbitration methods that are effective and at the same time, simple to implement.

Object of the Invention:
The object of the present invention is to provide an arbitration method that effectively handles requests from multiple clients with disparate traffic characteristics.

The object of the present invention is also to provide a system wherein arbitration method that effectively handles requests from multiple clients with disparate traffic characteristics is implemented.

Summary of the Invention:
Accordingly, the present invention provides a request arbitration method for arbitrating requests from a plurality of clients requesting access to a shared real-time resource, said method comprising the steps of receiving requests from the said plurality of clients, automatically allocating a predetermined initial priority level (IPL) for each of the requests thus received, wherein the priority values thus allocated to the requests from a particular client are selected from a priority level group (PLG) allocated to that client based on a predetermined priority level allocation method; and changing the priority level of a particular request from the initial priority level (IPL) to a final priority level (FPL), if the said request is not serviced within a predetermined time period (Tth), a value of the said final priority level (FPL) being equal to or greater than a value of the said initial priority level (IPL).

The present invention also provides a system comprising: a real time resource; a plurality of clients connected to the real time resource and sharing the same; wherein the plurality of clients are connected to the real time resource through an arbitration unit which is configured to receive requests from the said plurality of clients, automatically allocate a predetermined initial priority level (IPL) for each of the requests thus received, wherein the priority values thus allocated to the requests from a particular client are selected from a priority level group (PLG) allocated to that client based on a predetermined priority level allocation method; and change the priority level of a particular request from the initial priority level (IPL) to a final priority level (FPL), if the said request is not serviced within a predetermined time period (Tth), a value of the said final priority level (FPL) being equal to or greater than a value of the said initial priority level (IPL).

The following paragraphs are provided in order to describe the best mode of working the invention and nothing in this section should be taken as a limitation of the claims.

Brief Description of the Accompanying Drawings:
In order that the invention may be readily understood and put into practical effect, reference will now be made to exemplary embodiments as illustrated with reference to the accompanying drawings, where like reference numerals refer to identical or functionally similar elements throughout the separate views. The figures together with a detailed description below, are incorporated in and form part of the specification, and serve to further illustrate the embodiments and explain various principles and advantages, in accordance with the present invention where:

Figure 1 illustrates the overall flow chart of the arbitration method in accordance with the teachings of the present invention.

Figure 2 illustrates the priority levels including the initial and the final priority levels allocated to multiple clients in accordance with a first example.

Figure 3 illustrates the priority levels including the initial and the final priority levels allocated to multiple clients in accordance with a second example.

Figure 4 illustrates the method for allocating the initial priority level and the method of changing the same to final priority level in respect of a two-client based system.

Figure 5 illustrates the overall block diagram of the system that implements the request arbitration method.

Figure 6 illustrates block diagram of the arbitration unit in accordance with an embodiment of the present invention.

Skilled artisans will appreciate that elements in the drawings are illustrated for simplicity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the drawings may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.

Detailed Description of the Preferred Embodiments:
Before describing in detail embodiments that are in accordance with the present invention, it should be observed that the embodiments reside primarily in combinations of method steps related to requests arbitration applied during the process of real-time sharing of a resource.

Accordingly, the method steps have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having benefit of the description herein.

The terms “comprises”, “comprising”, or any other variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method that comprises a list of steps does not include only those steps but may include other steps not expressly listed or inherent to such process, method. Similarly, one or more elements in a system or apparatus proceeded by “comprises… a” does not, without more constraints, preclude the existence of other elements or additional elements in the system or apparatus.

With reference to figure 1 it can be noticed that in accordance with an embodiment of the present invention, the present invention provides a request arbitration method for arbitrating requests from a plurality of clients requesting access to a shared real-time resource, said method comprising the steps of:
a. receiving requests from the said plurality of clients (S101),
b. automatically allocating (S103) a predetermined initial priority level (IPL) for each of the requests thus received, wherein the priority values thus allocated to the requests from a particular client are selected from a priority level group (PLG) allocated to that client based on a predetermined priority level allocation method; and
c. changing (S105) the priority level of a particular request from the initial priority level (IPL) to a final priority level (FPL), if the said request is not serviced within a predetermined time period (Tth), a value of the said final priority level (FPL) being equal to or greater than a value of the said initial priority level (IPL).

As can be seen from figure 2, in an embodiment of the present invention, the priority level group (PLG) comprises at least one initial priority level (IPL), the value of which can vary from a lowest priority level to a highest priority level. In figure 2, the lowest priority level is represented by a value equal to 1 and a highest priority level is represented by a value equal to 7. However, other values can be allocated to each of the priority levels. In the present example under consideration, figure 2 illustrates providing 7 distinct priority levels (including the lowest and the highest priority level). However, in actual practice, lesser or more number of distinct priority levels can be defined.

By way of example, in respect of a client which is identified in figure 2 by the name “ENQ”, the priority level group comprises one initial priority level (IPL), which is allocated a value equal to “3”. Similarly, in respect of a client identified by the name “DSP_Cache”, comprises one initial priority level (IPL), which is allocated a value equal to “1”. Depending upon the nature of tasks that can be provided by a client, the user can choose the value of the priority level to be given to a particular client.

As can be observed from figure 2, in respect of one or more clients, the priority level group (PLG) comprises two initial priority levels (IPL), the values of the said two initial priority levels (IPL) are not equal to each other. By way of example, in respect of the clients identified by the name “DQ”, “CoppenQ”, “FLM”, etc. the priority level group (PLG) comprises two initial priority levels (IPL) namely a first initial priority level (whose value varies depending upon the client) and a second initial priority level (whose value in varies depending upon the client).

As can be observed from figure 3, which provides a second example of the priority level groups allocated to the multiple clients, the priority level group (PLG) allocated to a particular client may be selected independent of the priority level group(s) (PLG) allocated to other client(s). Particularly, in one more embodiment of the present invention, the value of the at least one initial priority level (IPL) contained in the priority level group (PLG) allocated to a particular client is selected independent of the value of the at least one initial priority level (IPL) contained in the priority level group(s) (PLG) allocated to other client(s). Alternatively, the values of the two initial priority levels (IPL) contained in the priority level group (PLG) allocated to a particular client are selected independent of the values of the two initial priority levels (IPL) contained in the priority level group(s) (PLG) allocated to other client(s).

Similar to the selection of the PLG and/or the IPL, the final priority level (FPL) allocated to a particular client is selected independent of the final priority level(s) allocated to other client(s).

Although in each of figure 2 and figure 3 for the sake of simplicity, the final priority level allocated to a particular client has been selected to be equal to the maximum value among the priority level group thus already allocated to that client (i.e. explicitly showing support for the criteria a value of the said final priority level (FPL) being equal to a value of the initial priority level (IPL) contained in the PLG), it is possible to define a final priority level (FPL) which is distinct from the initial priority levels (IPL) contained in the PLG.

In a further more embodiment of the present invention, the predetermined time period (Tth) allocated to a particular client is selected independent of the predetermined time period(s) allocated to other client(s). As can be seen from figure 4, in a case wherein an arbitration is required to be performed between two clients namely R and B sending requests R1, R2, R3 and R4 and B1, B2, B3, B4, B5, B6, B7, B8 and B9 respectively, the predetermined time period (Tth) allocated to the client R (i.e. T1) can be set independent of the predetermined time period allocated to the client B (i.e. T2). In an embodiment of the present invention, the predetermined time period (Tth) for a particular client is calculated starting from a last time a command from that particular client is serviced.

In another embodiment of the present invention, if the priority level group (PLG) thus allocated to a particular client comprises two distinct initial priority levels (IPL), for the predetermined time period (Tth) immediately after a last command from that client is serviced, the request(s) thus received from that particular client is allocated a first initial priority level. As can be observed from figure 4, the request R3, which is received prior to expiry of the time period T1 (as calculated from the time period when the Request R2 is serviced) is allocated the first initial priority level in accordance with the aforesaid embodiment.

In yet another embodiment of the present invention, if the priority level group (PLG) thus allocated to a particular client comprises two distinct initial priority levels (IPL) and if no request is received for the predetermined time period (Tth) immediately after a last command from that client is serviced, the request thus received thereafter is allocated a second initial priority level. As can be once again observed from figure 4, the request R2, which is received after to expiry of the time period T1 (as calculated from the time period when the Request R1 is serviced) is allocated the second initial priority level in accordance with the aforesaid embodiment.

As can be further observed from figure 4, if a request is not serviced within a predetermined time period (Tth), the priority level of the particular request is changed from the initial priority level (IPL) to a final priority level (FPL). In this regard, it can be noticed that the request R4 from the client R is not serviced prior to expiry of the time period T1 (calculated from the time when the request R3 from the said client R is serviced). Hence, immediately after expiry of the expiry of the time period T1, the priority level of the request R4 is changed (in the present case from 1 to 6).

Similarly, with respect to the client identified as “B”, it can be observed that the first request B1 arrives and is allocated the first initial priority level (this is because the said request arrives before expiry of the time period (T2) calculated from the time when a last command from that client is serviced). Thereafter, it can be observed, that the request B2 arrives after expiry of the time period (T2) and hence, is automatically allocated the second initial priority level in accordance with the aforesaid embodiment. Similarly, the request B3 arrives after expiry of the time period (T2) and hence, is automatically allocated the second initial priority level in accordance with the aforesaid embodiment. Thereafter, each of the requests B4 to B9 are received before expiry of the time period (T2) calculated from the time when a last command from that client is serviced and hence, each of the said request is allocated the first initial priority level.

Thus, it can be observed, that the system automatically allocates a predetermined initial priority level based on a predetermined priority level allocation method, one of which has been described above by way of example and thereafter, monitors as to whether a particular request from a particular client is pending for a time period which is equal to the predetermined time period (Tth). If it is determined that there exists a particular request which has not been serviced for a period equal to the predetermined time period (Tth), the arbitration method changes the priority level of the particular request from the initial priority level (IPL) to a final priority level (FPL).

It may be observed that the predetermined time period (Tth) represents the maximum time period taken to change the priority level of an un-serviced request from the initial priority level (IPL) to the final priority level (FPL). In a further embodiment of the present invention, the time period taken to change the priority level of an un-serviced request from the initial priority level (IPL) to the final priority level (FPL) can vary from a zero value to the predetermined time period (Tth).

In the present invention, the arbitration method does not de-bar a particular request from being serviced merely because the request is having a low priority level. By way of example, each of the requests B3 to B9 are serviced first despite that they have a first initial priority level (as the first initial priority level for the client B is greater than the first initial priority level for the client R). The method at the same time, keeps track of the request R4 from the client R and once it is determined that the said request R4 could not be serviced for a time period equal to Tth (which in the present case corresponds to T1), changes the priority value of the said request R4 from the initial priority level to the final priority level (FPL), which in the present case has been set such that it is higher than both of the initial as well as the final priority levels for the client B. Thus, this ensures that once resources become available immediately after the priority value of the request R4 has been changed, the said request can be serviced. This ensures that the request R4 is serviced before the request B9 is serviced.

Although the arbitration method has been described above with a two-client example situation, the example has been chosen to enable easy understanding of the concept of the arbitration being proposed in the present invention. The arbitration method is applicable irrespective of the number of clients which share the real time resource.

With reference to figure 5, there is shown an illustrative system wherein the request arbitration method has been implemented, wherein the system comprises:
a real time resource (501);
a plurality of clients (5031 to 503n) connected to the real time resource (501) and sharing the same;
characterized in that the plurality of clients are connected to the real time resource through an arbitration unit (505) which is configured to receive requests from the said plurality of clients, automatically allocate a predetermined initial priority level (IPL) for each of the requests thus received, wherein the priority values thus allocated to the requests from a particular client are selected from a priority level group (PLG) allocated to that client based on a predetermined priority level allocation method; and change the priority level of a particular request from the initial priority level (IPL) to a final priority level (FPL), if the said request is not serviced within a predetermined time period (Tth), a value of the said final priority level (FPL) being equal to or greater than a value of the said initial priority level (IPL).

It will be appreciated that embodiments of the invention described herein (especially the arbitration unit) may be comprises of one or more conventional processors and unique stored program instructions that control the one or more processors to implement, in conjunction with certain non-processor circuits, some, most, or all of the arbitration functions described herein. Alternatively, some or all of the arbitration functions could be implemented by a state machine that has no stored program instructions or in one or more application specific integrated circuits (ASICs), in which each function or some combinations of certain of the functions are implemented as custom logic.

Of course, a combination of the two approaches could be used. Thus, method and means for these functions have been described herein. Further, it is expected that one of ordinary skill, notwithstanding possibly significant effort and many design choices motivated by, for example, available time, current technology, and economic considerations, when guided by the concepts and principles disclosed herein will be readily capable of generating such software instructions and programs and ICs with minimal experimentation.
With reference to figure 6, there is shown an illustrative block diagram of the arbitration unit, wherein the arbitration unit comprises: a multiplexer (601) and a DDR controller (602) operationally connected to the said multiplexer to perform the arbitration method as described in the present invention.
The foregoing detailed description has described only a few of the many possible implementations of the present invention. Thus, the detailed description is given only by way of illustration and nothing contained in this section should be construed to limit the scope of the invention. The claims are limited only by the following claims, including the equivalents thereof.

WE CLAIM:

1. A request arbitration method for arbitrating requests from a plurality of clients requesting access to a shared real-time resource, said method comprising the steps of:
a. receiving requests from the said plurality of clients,
b. automatically allocating a predetermined initial priority level (IPL) for each of the requests thus received, wherein the priority values thus allocated to the requests from a particular client are selected from a priority level group (PLG) allocated to that client based on a predetermined priority level allocation method; and
c. changing the priority level of a particular request from the initial priority level (IPL) to a final priority level (FPL), if the said request is not serviced within a predetermined time period (Tth), a value of the said final priority level (FPL) being equal to or greater than a value of the said initial priority level (IPL).

2. The request arbitration method as claimed in claim 1, wherein the priority level group (PLG) comprises at least one initial priority level (IPL), the value of which can vary from a lowest priority level to a highest priority level.

3. The request arbitration method as claimed in claim 1, wherein the priority level group (PLG) comprises two initial priority levels (IPL), the values of the said two initial priority levels (IPL) are not equal to each other.

4. The request arbitration method as claimed in claim 1, wherein the priority level group (PLG) allocated to a particular client is selected independent of the priority level group(s) (PLG) allocated to other client(s).

5. The request arbitration method as claimed in any of the preceding claims, wherein the value of the at least one initial priority level (IPL) contained in the priority level group (PLG) allocated to a particular client is selected independent of the value of the at least one initial priority level (IPL) contained in the priority level group(s) (PLG) allocated to other client(s).

6. The request arbitration method as claimed in any of the preceding claims, wherein the values of the two initial priority levels (IPL) contained in the priority level group (PLG) allocated to a particular client are selected independent of the values of the two initial priority levels (IPL) contained in the priority level group(s) (PLG) allocated to other client(s).

7. The request arbitration method as claimed in claim 1, wherein the final priority level (FPL) allocated to a particular client is selected independent of the final priority level(s) allocated to other client(s).

8. The request arbitration method as claimed in claim 1, wherein the predetermined time period (Tth) allocated to a particular client is selected independent of the predetermined time period(s) allocated to other client(s).

9. The request arbitration method as claimed in claim 1, wherein the predetermined time period (Tth) for a particular client is calculated starting from a last time a command from that particular client is serviced.

10. The request arbitration method as claimed in any of the preceding claims, wherein if the priority level group (PLG) thus allocated to a particular client comprises two distinct initial priority levels (IPL), for the predetermined time period (Tth) immediately after a last command from that client is serviced, the request(s) thus received from that particular client is allocated a first initial priority level.

11. The request arbitration method as claimed in any of the preceding claims, wherein if the priority level group (PLG) thus allocated to a particular client comprises two distinct initial priority levels (IPL) and if no request is received for the predetermined time period (Tth) immediately after a last command from that client is serviced, the request thus received thereafter is allocated a second initial priority level.

12. The request arbitration method as claimed in claim 1, wherein the predetermined time period (Tth) represents the maximum time period taken to change the priority level of an un-serviced request from the initial priority level (IPL) to the final priority level (FPL).

13. The request arbitration method as claimed in any of the preceding claims, wherein the time period taken to change the priority level of an un-serviced request from the initial priority level (IPL) to the final priority level (FPL) can vary from a zero value to the predetermined time period (Tth).

14. A system implementing an arbitration method as claimed in claim 1, comprising:
a real time resource;
a plurality of clients connected to the real time resource and sharing the same;
characterized in that the plurality of clients are connected to the real time resource through an arbitration unit which is configured to receive requests from the said plurality of clients, automatically allocate a predetermined initial priority level (IPL) for each of the requests thus received, wherein the priority values thus allocated to the requests from a particular client are selected from a priority level group (PLG) allocated to that client based on a predetermined priority level allocation method; and change the priority level of a particular request from the initial priority level (IPL) to a final priority level (FPL), if the said request is not serviced within a predetermined time period (Tth), a value of the said final priority level (FPL) being equal to or greater than a value of the said initial priority level (IPL).

15. A request arbitration method for arbitrating requests from a plurality of clients requesting access to a shared real-time resource substantially as herein described with reference to the foregoing description and the accompanying drawings.

16. A system implementing an arbitration method substantially as herein described with reference to the foregoing description and the accompanying drawings.

Dated this 31st day of December, 2008

G. Deepak Sriniwas
Of K & S Partners
Attorney for the Applicants