On-Chip Bus Arbitration Method and Device Thereof

• US 20140189181A1
• Filed: 10/14/2011
• Published: 07/03/2014
• Est. Priority Date: 06/07/2011
• Status: Abandoned Application

• Current Assignee: Beijing Pkunity Microsystems Technology Company Limited
• Original Assignee: Beijing Pkunity Microsystems Technology Company Limited
• Inventors: Cheng, Xu, Feng, Yi, Liu, Dan, Tong, Dong
• Application Number:
  US14/124,792
• Publication Number:
  US 20140189181A1
• Time in Patent Office: Days
• US Class Current: 710/118
• CPC Class Codes: G06F 13/3625 using a time dependent access
• CPC Class Codes: G06F 13/374 using a self-select method with individual priority code comparator

Abstract

A method and device for on-chip bus arbitration are disclosed. The method includes: dividing devices into a first level, a second level and a third level from high to low; and in each arbitration period, calculating remaining processing time of each real-time transaction, and upgrading a device making a request required to be processed immediately to the first level in the current arbitration period; monitoring bandwidth usage amount of devices of the first level and the second level respectively, and downgrading a device whose bandwidth usage amount exceeds a preset bandwidth threshold value to the third level in the current arbitration period; and in devices making requests for a bus use right, if a device of the highest level is the device of the first level, authorizing the device of the first level; and if it is not the device of the first level, authorizing a device making continuous requests.

Claims

1. A method for on-chip bus arbitration, comprising:

dividing devices into a first level, a second level and a third level from high to low; and

in each arbitration period, executing the following steps;

calculating remaining processing time of each real-time transaction, and upgrading a device making a request required to be processed immediately to the first level in a current arbitration period;

monitoring a bandwidth usage amount of a device of the first level and a bandwidth usage amount of a device of the second level, and downgrading a device whose bandwidth usage amount exceeds a preset bandwidth threshold value to the third level in the current arbitration period; and

in devices making requests for a bus use right, when a device of a highest level is the device of the first level, authorizing the device of the first level; and

when the device of the highest level is not the device of the first level, authorizing a device making continuous requests;

wherein, the continuous requests are requests whose read-write types are the same as that of a last authorized transaction, and whose addresses hit a same row or different memory banks as an address of the last authorized transaction does.

2. The method according to claim 1, wherein, the step of authorizing a device making continuous requests comprises:

if no authorization period device exists, authorizing a device making continuous requests among devices of the highest level;

if a device whose level is higher than that of the authorization period device makes a request, authorizing a device making continuous requests among devices of a higher level; and

when no device of the higher level makes a request, judging whether a authorization period device makes continuous requests, if the authorization period device makes the continuous requests, authorizing the authorization period device; and

if the requests made by the authorization period device are discontinuous requests, authorizing a device making continuous requests among devices of the highest level;

wherein, the authorization period device refers to that;

when no authorization period device exists, and a device of the second level or a device of the third level is authorized, the authorized device is a authorization period device;

when a authorization period device exists, in a condition that the device whose level is higher than that of the authorization period device does not make a request, if the authorization period device makes continuous requests, or if the authorization period device does not make a request and a time interval between a current time and a moment at which the authorization period device made a request last time does not exceed a transaction interval of the authorization period device, the authorization period device is still a authorization period device; and

when a authorization period device exists and it is not the above case that the authorization period device is still a authorization period device, if a device of the second level or a device of the third level is authorized, the authorized device is a authorization period device;

wherein, the transaction interval is an interval existing between pending transactions sent by an identical device.

3. The method according to claim 2, wherein, the step of authorizing a device making continuous requests further comprises:

when a authorization period device exists and a device whose level is higher than that of the authorization period device does not make a request, if the authorization period device does not make a request, and when a time interval between a current time and a moment at which the authorization period device made a request last time does not exceed a transaction interval of the authorization period device, judging whether a device making continuous requests exists, if a device making continuous requests exists, authorizing the device making continuous requests, and if the device making continuous requests does not exist, not performing authorization.

4. The method according to claim 2, wherein, the step of authorizing a device making continuous requests further comprises:

when no device of the higher level makes a request, the authorization period device does not make a request and a time interval between a current time and a moment at which the authorization period device making a request last time exceeds a transaction interval of the authorization period device, judging whether other requests exist;

if no any other request exists, not performing authorization;

if other requests exist and a device of the highest level makes continuous requests, authorizing a device making continuous requests; and

if no continuous requests made by the device of the highest level exist among the other requests, performing authorization according to a Least Recently Serviced (LRS) principle.

5. The method according to claim 2, wherein, the step of authorizing a device making continuous requests further comprises:

if no authorization period device exists and a device of the highest level does not make continuous requests, performing authorization according to the LRS principle;

if a device whose level is higher than that of the authorization period device does not make continuous requests, performing authorization according to the LRS principle; and

when no device of the higher level makes a request, and requests made by the authorization period device are discontinuous requests, if a device of the highest level does not make continuous requests, performing authorization according to the LRS principle.

6. A device for on-chip bus arbitration, comprising:

a setting module, configured to;

divide devices into a first level, a second level and a third level from high to low;

a real-time scheduling module, configured to;

in each arbitration period, calculate remaining processing time of each real-time transaction, and upgrade a device making a request required to be processed immediately to the first level in a current arbitration period;

a bandwidth allocation module, configured to;

in each arbitration period, monitor a bandwidth usage amount of a device of the first level and a bandwidth usage amount of a device of the second level, and downgrade a device whose bandwidth usage amount exceeds a preset bandwidth threshold value to the third level in the current arbitration period; and

a limited maintaining authorization arbitration module, configured to;

in each arbitration period, after the real-time scheduling module and the bandwidth allocation module adjust the levels, in devices making requests for a bus use right, when a device of a highest level is the device of the first level, authorize the device of the first level; and

when the device of the highest level is not the device of the first level, authorize a device making continuous requests;

wherein, the continuous requests are requests whose read-write types are the same as that of a last authorized transaction, and whose addresses hit a same row or different memory banks as an address of the last authorized transaction does.

7. The device according to claim 6, wherein, the limited maintaining authorization arbitration module is further configured to authorize the device making continuous requests by means of:

if no authorization period device exists, the limited maintaining authorization arbitration module authorizing a device making continuous requests among devices of the highest level;

if a device whose level is higher than that of the authorization period device makes a request, the limited maintaining authorization arbitration module authorizing a device making continuous requests among devices of a higher level; and

when no device of the higher level makes a request, the limited maintaining authorization arbitration module judging whether a authorization period device makes continuous requests, if the authorization period device makes the continuous requests, authorizing the authorization period device; and

if the requests made by the authorization period device are discontinuous requests, authorizing a device making continuous requests among devices of the highest level;

wherein, the authorization period device refers to that;

when no authorization period device exists, and a device of the second level or a device of the third level is authorized, the authorized device is a authorization period device;

when a authorization period device exists, in a condition that the device whose level is higher than that of the authorization period device does not make a request, if the authorization period device makes continuous requests, or if the authorization period device does not make a request and a time interval between a current time and a moment at which the authorization period device made a request last time does not exceed a transaction interval of the authorization period device, the authorization period device is still a authorization period device; and

when a authorization period device exists and it is not the above case that the authorization period device is still a authorization period device, if a device of the second level or a device of the third level is authorized, the authorized device is a authorization period device;

wherein, the transaction interval is an interval existing between pending transactions sent by an identical device.

8. The device according to claim 7, wherein,

the limited maintaining authorization arbitration module is further configured to:

when a authorization period device exists and a device whose level is higher than that of the authorization period device does not make a request, if the authorization period device does not make a request, and when a time interval between a current time and a moment at which the authorization period device made a request last time does not exceed a transaction interval of the authorization period device, judge whether a device making continuous requests exists, if a device making continuous requests exists, authorize the device making continuous requests, and if the device making continuous requests does not exist, not perform authorization.

9. The device according to claim 7, wherein,

the limited maintaining authorization arbitration module is further configured to:

when no device of the higher level makes a request, the authorization period device does not make a request and a time interval between a current time and a moment at which the authorization period device made a request last time exceeds a transaction interval of the authorization period device, judge whether other requests exist;

if no any other request exists, not perform authorization;

if other requests exist and a device of the highest level makes continuous requests, authorize a device making continuous requests; and

if no continuous requests made by the device of the highest level exist among the other requests, perform authorization according to a Least Recently Serviced (LRS) principle.

10. The device according to claim 6, wherein, the limited maintaining authorization arbitration module comprises:

a continuity calculation unit, a continuity screening unit, a timeout judgment unit, priority arbitration units, a multiple-choice device, a device number update unit and a state machine;

wherein;

the continuity calculation unit is configured to;

obtain a row address and read-write type of a transaction sequence authorized in a last arbitration period from the state machine, calculate whether a row address of each request and a row address of the last authorized transaction are identical or access different memory banks and whether a read-write type of each request and a read-write type of the last authorized transaction are identical, and eventually obtain continuity calculation results corresponding to all the devices, wherein, 1 represents continuity and 0 represents discontinuity;

the results form continuity vectors; and

requests of the device of the first level are defaulted as discontinuous;

the continuity screening unit is configured to;

obtain a level of a device currently making a request from the state machine, and screen continuity state vectors of a current request of the highest level from the continuity vectors, and send the continuity state vectors to the state machine;

the priority arbitration units comprise a first priority arbitration unit, a second priority arbitration unit and a third priority arbitration unit;

the first priority arbitration unit is configured to;

input a request status of each device and a bitwise-and result of the continuity state vectors screened by the continuity screening unit, and calculate a first authorization result;

the second priority arbitration unit is configured to;

input a request status of each device and a bitwise-and result of continuity vectors of a request of the device of the highest level, and calculate a second authorization result; and

the third priority arbitration unit is configured to;

directly input a request status of each device, and calculate a third authorization result;

wherein, the request status is that;

1 represents that a request is made, and 0 represents that there is no request;

the multi-choice device is configured to;

select one of the first authorization result, the second authorization result, the third authorization result and 0 to serve as a current authorization result to be output according to an indication of the state machine, and input the current authorization result to the timeout judgment unit and the device number update unit;

the device number update unit is configured to;

when the multi-choice device selects the current authorization result, according to the current authorization result, a number of devices of each level and an LRS sequence of devices of an identical level at the current moment obtained from the state machine, update a priority order among the devices for the next arbitration;

the timeout judgment unit is configured to;

calculate how many periods had passed from a moment at which a device in the authorization period made a last request to a current moment, and judge whether a number of the periods exceeds a transaction interval of the device, and input a judgment result to the state machine; and

the state machine is configured to;

determine an authorization situation which should be currently adopted by an arbiter according to state information, the continuity vectors, the continuity state vectors, levels and the request statuses, and indicate the multi-choice device to make choices.

11. The device according to claim 7, wherein, the limited maintaining authorization arbitration module comprises:

a continuity calculation unit, a continuity screening unit, a timeout judgment unit, priority arbitration units, a multiple-choice device, a device number update unit and a state machine;

wherein;

the continuity calculation unit is configured to;

obtain a row address and read-write type of a transaction sequence authorized in a last arbitration period from the state machine, calculate whether a row address of each request and a row address of the last authorized transaction are identical or access different memory banks and whether a read-write type of each request and a read-write type of the last authorized transaction are identical, and eventually obtain continuity calculation results corresponding to all the devices, wherein, 1 represents continuity and 0 represents discontinuity;

the results form continuity vectors; and

requests of the device of the first level are defaulted as discontinuous;

the continuity screening unit is configured to;

obtain a level of a device currently making a request from the state machine, and screen continuity state vectors of a current request of the highest level from the continuity vectors, and send the continuity state vectors to the state machine;

the priority arbitration units comprise a first priority arbitration unit, a second priority arbitration unit and a third priority arbitration unit;

the first priority arbitration unit is configured to;

input a request status of each device and a bitwise-and result of the continuity state vectors screened by the continuity screening unit, and calculate a first authorization result;

the second priority arbitration unit is configured to;

input a request status of each device and a bitwise-and result of continuity vectors of a request of the device of the highest level, and calculate a second authorization result; and

the third priority arbitration unit is configured to;

directly input a request status of each device, and calculate a third authorization result;

wherein, the request status is that;

1 represents that a request is made, and 0 represents that there is no request;

the multi-choice device is configured to;

select one of the first authorization result, the second authorization result, the third authorization result and 0 to serve as a current authorization result to be output according to an indication of the state machine, and input the current authorization result to the timeout judgment unit and the device number update unit;

the device number update unit is configured to;

when the multi-choice device selects the current authorization result, according to the current authorization result, a number of devices of each level and an LRS sequence of devices of an identical level at the current moment obtained from the state machine, update a priority order among the devices for the next arbitration;

the timeout judgment unit is configured to;

calculate how many periods had passed from a moment at which a device in the authorization period made a last request to a current moment, and judge whether a number of the periods exceeds a transaction interval of the device, and input a judgment result to the state machine; and

the state machine is configured to;

determine an authorization situation which should be currently adopted by an arbiter according to state information, the continuity vectors, the continuity state vectors, levels and the request statuses, and indicate the multi-choice device to make choices.

12. The device according to claim 8, wherein, the limited maintaining authorization arbitration module comprises:

a continuity calculation unit, a continuity screening unit, a timeout judgment unit, priority arbitration units, a multiple-choice device, a device number update unit and a state machine;

wherein;

the continuity calculation unit is configured to;

obtain a row address and read-write type of a transaction sequence authorized in a last arbitration period from the state machine, calculate whether a row address of each request and a row address of the last authorized transaction are identical or access different memory banks and whether a read-write type of each request and a read-write type of the last authorized transaction are identical, and eventually obtain continuity calculation results corresponding to all the devices, wherein, 1 represents continuity and 0 represents discontinuity;

the results form continuity vectors; and

requests of the device of the first level are defaulted as discontinuous;

the continuity screening unit is configured to;

obtain a level of a device currently making a request from the state machine, and screen continuity state vectors of a current request of the highest level from the continuity vectors, and send the continuity state vectors to the state machine;

the priority arbitration units comprise a first priority arbitration unit, a second priority arbitration unit and a third priority arbitration unit;

the first priority arbitration unit is configured to;

input a request status of each device and a bitwise-and result of the continuity state vectors screened by the continuity screening unit, and calculate a first authorization result;

the second priority arbitration unit is configured to;

input a request status of each device and a bitwise-and result of continuity vectors of a request of the device of the highest level, and calculate a second authorization result; and

the third priority arbitration unit is configured to;

directly input a request status of each device, and calculate a third authorization result;

wherein, the request status is that;

1 represents that a request is made, and 0 represents that there is no request;

the multi-choice device is configured to;

select one of the first authorization result, the second authorization result, the third authorization result and 0 to serve as a current authorization result to be output according to an indication of the state machine, and input the current authorization result to the timeout judgment unit and the device number update unit;

the device number update unit is configured to;

when the multi-choice device selects the current authorization result, according to the current authorization result, a number of devices of each level and an LRS sequence of devices of an identical level at the current moment obtained from the state machine, update a priority order among the devices for the next arbitration;

the timeout judgment unit is configured to;

calculate how many periods had passed from a moment at which a device in the authorization period made a last request to a current moment, and judge whether a number of the periods exceeds a transaction interval of the device, and input a judgment result to the state machine; and

the state machine is configured to;

determine an authorization situation which should be currently adopted by an arbiter according to state information, the continuity vectors, the continuity state vectors, levels and the request statuses, and indicate the multi-choice device to make choices.

13. The device according to claim 9, wherein, the limited maintaining authorization arbitration module comprises:

a continuity calculation unit, a continuity screening unit, a timeout judgment unit, priority arbitration units, a multiple-choice device, a device number update unit and a state machine;

wherein;

the continuity calculation unit is configured to;

obtain a row address and read-write type of a transaction sequence authorized in a last arbitration period from the state machine, calculate whether a row address of each request and a row address of the last authorized transaction are identical or access different memory banks and whether a read-write type of each request and a read-write type of the last authorized transaction are identical, and eventually obtain continuity calculation results corresponding to all the devices, wherein, 1 represents continuity and 0 represents discontinuity;

the results form continuity vectors; and

requests of the device of the first level are defaulted as discontinuous;

the continuity screening unit is configured to;

obtain a level of a device currently making a request from the state machine, and screen continuity state vectors of a current request of the highest level from the continuity vectors, and send the continuity state vectors to the state machine;

the priority arbitration units comprise a first priority arbitration unit, a second priority arbitration unit and a third priority arbitration unit;

the first priority arbitration unit is configured to;

input a request status of each device and a bitwise-and result of the continuity state vectors screened by the continuity screening unit, and calculate a first authorization result;

the second priority arbitration unit is configured to;

input a request status of each device and a bitwise-and result of continuity vectors of a request of the device of the highest level, and calculate a second authorization result; and

the third priority arbitration unit is configured to;

directly input a request status of each device, and calculate a third authorization result;

wherein, the request status is that;

1 represents that a request is made, and 0 represents that there is no request;

the multi-choice device is configured to;

select one of the first authorization result, the second authorization result, the third authorization result and 0 to serve as a current authorization result to be output according to an indication of the state machine, and input the current authorization result to the timeout judgment unit and the device number update unit;

the device number update unit is configured to;

when the multi-choice device selects the current authorization result, according to the current authorization result, a number of devices of each level and an LRS sequence of devices of an identical level at the current moment obtained from the state machine, update a priority order among the devices for the next arbitration;

the timeout judgment unit is configured to;

calculate how many periods had passed from a moment at which a device in the authorization period made a last request to a current moment, and judge whether a number of the periods exceeds a transaction interval of the device, and input a judgment result to the state machine; and

the state machine is configured to;

determine an authorization situation which should be currently adopted by an arbiter according to state information, the continuity vectors, the continuity state vectors, levels and the request statuses, and indicate the multi-choice device to make choices.