SCHEDULING DEVICE

• US 20160103710A1
• Filed: 12/18/2015
• Published: 04/14/2016
• Est. Priority Date: 06/19/2013
• Status: Abandoned Application

• Current Assignee: Sun Pharmaceutical Industries Limited
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Shachar, Yaron, Peleg, Yoav, Tal, Alex, Umansky, Alex, Xiong, Lixia, Lu, Yuchun
• Application Number:
  US14/974,320
• Publication Number:
  US 20160103710A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 49/00 Packet switching elements

Abstract

The invention relates to a scheduling device for receiving a set of requests and providing a set of grants to the set of requests, the scheduling device comprising: a lookup vector prepare unit configured to provide a lookup vector prepared set of requests depending on the set of requests and a selection mask and to provide a set of acknowledgements to the set of requests; and a prefix forest unit coupled to the lookup vector prepare unit, wherein the prefix forest unit is configured to provide the set of grants as a function of the lookup vector prepared set of requests and to provide the selection mask based on the set of grants.

Claims

1. A scheduling device for receiving a set of requests and providing a set of grants to the set of requests, the scheduling device comprising:

a lookup vector prepare unit configured to merge a set of requests and a selection mask in order to provide a lookup vector prepared set of requests and to provide a set of acknowledgements to the set of requests; and

a prefix forest unit coupled to the lookup vector prepare unit, wherein the prefix forest unit is configured to provide the set of grants as a function of the new set of requests and to provide the selection mask based on the set of grants.

2. The scheduling device of claim 1, comprising:

a rate limiting unit coupled to the lookup vector prepare unit, wherein the rate limiting unit is configured to limit a rate of the set of requests according to a scheduling scheme in order to provide a rate-limited set of requests, accordingly, the set of requests merged by the lookup vector prepare unit is the rate-limited set of requests.

3. The scheduling device of claim 2, wherein the rate limiting unit is configured to filter requests of requestor-groups that have passed a configurable rate of acknowledgments.

4. The scheduling device of claim 2, wherein the scheduling scheme is based on queue groups the set of requests and the set of acknowledgements are assigned to.

5. The scheduling device of claim 4, wherein the rate limiting unit comprises:

a set of bucket buffers, each bucket buffer assigned to one of the queue groups for storing acknowledgements of the set of acknowledgements assigned to the one of the queue groups.

6. The scheduling device of claim 1, wherein the prefix forest unit comprises a prefix tree.

7. The scheduling device of claim 6, wherein an output of the prefix forest unit is determined as a set Z of numbers and for each number Z_i in Z it holds that X_i+Y_i=Z_i.

8. The scheduling device of claim 7, wherein the prefix forest unit is configured to compare a couple of X_i and Y_i in Z to a known set of options.

9. The scheduling device of claim 7, wherein the prefix tree is configured to provide for a number of N input values a number of P results, wherein the result f_z(i) of the prefix tree for an input v(i) and an integer number i is determined according to the following formula:

10. The scheduling device of claim 9, wherein the prefix tree is configured to provide the selection mask in order to differentiate between the results being greater than P and the results being smaller or equal than P.

11. A method for scheduling a set of requests and providing a set of grants to the set of requests, the method comprising:

merging a set of requests and a selection mask in order to provide a lookup vector prepared set of requests and a set of acknowledgements to the set of requests; and

providing the set of grants as a function of the new set of requests and providing the selection mask based on the set of grants.

12. The method of claim 11, further comprising:

limiting a rate of the set of requests according to a scheduling scheme in order to provide a rate-limited set of requests, accordingly, the set of requests merged by the lookup vector prepare unit is the rate-limited set of requests.

13. The method of claim 12, wherein merging the set of requests and a selection mask comprises:

masking a current set of requests based on the selection mask to provide a masked set of requests;

merging the masked set of requests with the rate-limited set of requests to provide the current set of requests; and

shifting the current set of requests based on a shifted version of the selection mask to provide the lookup vector prepared set of requests.