METHOD AND APPARATUS FOR TIME MANAGEMENT AND SCHEDULING FOR SYCHRONOUS PROCESSING ON A CLUSTER OF PROCESSING NODES

• US 20140101661A1
• Filed: 10/09/2012
• Published: 04/10/2014
• Est. Priority Date: 10/09/2012
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Levin, Jeffrey A., Rangan, Venkat, Vachon, Robert J.
• Granted Patent: US 9,373,074 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06N 3/049 Temporal neural networks, e.g. delay elements, oscillating neurons or pulsed inputs
• CPC Class Codes: G06N 3/10 Interfaces, programming languages or software development kits, e.g. for simulating neural networks

Abstract

Certain aspects of the present disclosure provide techniques for time management and scheduling of synchronous neural processing on a cluster of processing nodes. A slip (or offset) may be introduced between processing nodes of a distributed processing system formed by a plurality of interconnected processing nodes, to enable faster nodes to continue processing without waiting for slower nodes to catch up. In certain aspects, a processing node, after completing each processing step, may check for received completion packets and apply a defined constraint to determine whether it may start processing a subsequent step or not.

Claims

1. A method for processing by a first node in a distributed computing system formed by a plurality of interconnected nodes, comprising:

monitoring completion of jobs by other nodes in the distributed computing system; and

determining, after completing processing of a job in a current time interval, whether or not to start processing a job in a subsequent time interval based on at least one constraint and the monitored completion of jobs by other nodes.

2. The method of claim 1, wherein the at least one constraint allows the first node to start processing a job in the subsequent time interval before at least a second node has completed processing a job in the current time interval.

3. The method of claim 2, wherein the at least one constraint is defined by a value that specifies a maximum number of time intervals the first node is allowed to process ahead of the second node.

4. The method of claim 1, wherein at least one of the constraints prevents the first node from processing a job in the subsequent time interval before at least a second node has begun processing a job in an interval later than the subsequent time interval.

5. The method of claim 1, wherein monitoring completion of jobs by other nodes comprises receiving an indication from other nodes reporting completion of jobs.

6. The method of claim 5, wherein each indication provides a timestamp indicating an interval for which a corresponding job is completed by the node sending the indication.

7. The method of claim 6, further comprising:

determining a time offset for a connection between the first node and a second node, based on a difference in timestamps between the first node and at least a second node; and

wherein at least one of the constraints prevents the first node from processing a job in the subsequent time interval before at least a second node has begun processing a job in an interval later than a subsequent time interval adjusted based on the time offset.

8. The method of claim 5, wherein at least one of the other nodes does not send an indication for each interval.

9. The method of claim 8, further comprising assuming the at least one of the other nodes has completed processing jobs for time intervals prior to a time interval identified in the indication.

10. The method of claim 5, further comprising:

determining a time offset for the first node based on a timestamp in a first indication received upon joining the distributed computing system; and

utilizing the time offset to process indications received from other nodes.

11. The method of claim 1, further comprising:

maintaining a programmable timer for at least one connection between the first node and at least a second node;

wherein at least a first constraint allows the first node to process a job in the subsequent time interval if the programmable timer expires without receiving an indication from the second node.

12. The method of claim 11, wherein the first constraint allows the first node to process a job in the subsequent time interval if:

the programmable timer expires without receiving an indication from the second node;

or

the first node receives an indication from the second node prior to the programmable timer expiring.

13. An apparatus for processing by a first node in a distributed computing system formed by a plurality of interconnected nodes, comprising:

means for monitoring completion of jobs by other nodes in the distributed computing system; and

means for determining, after completing processing of a job in a current time interval, whether or not to start processing a job in a subsequent time interval based on at least one constraint and the monitored completion of jobs by other nodes.

14. The apparatus of claim 13, wherein the at least one constraint allows the first node to start processing a job in the subsequent time interval before at least a second node has completed processing a job in the current time interval.

15. The apparatus of claim 14, wherein the at least one constraint is defined by a value that specifies a maximum number of time intervals the first node is allowed to process ahead of the second node.

16. The apparatus of claim 13, wherein at least one of the constraints prevents the first node from processing a job in the subsequent time interval before at least a second node has begun processing a job in an interval later than the subsequent time interval.

17. The apparatus of claim 13, wherein the means for monitoring completion of jobs by other nodes comprises receiving an indication from other nodes reporting completion of jobs.

18. The apparatus of claim 17, wherein each indication provides a timestamp indicating an interval for which a corresponding job is completed by the node sending the indication.

19. The apparatus of claim 18, further comprising:

means for determining a time offset for a connection between the first node and a second node, based on a difference in timestamps between the first node and at least a second node; and

wherein at least one of the constraints prevents the first node from processing a job in the subsequent time interval before at least a second node has begun processing a job in an interval later than a subsequent time interval adjusted based on the time offset.

20. The apparatus of claim 17, wherein at least one of the other nodes does not send an indication for each interval.

21. The apparatus of claim 20, further comprising means for assuming the at least one of the other nodes has completed processing jobs for time intervals prior to a time interval identified in the indication.

22. The apparatus of claim 17, further comprising:

means for determining a time offset for the first node based on a timestamp in a first indication received upon joining the distributed computing system; and

means for utilizing the time offset to process indications received from other nodes.

23. The apparatus of claim 13, further comprising:

means for maintaining a programmable timer for at least one connection between the first node and at least a second node;

wherein at least a first constraint allows the first node to process a job in the subsequent time interval if the programmable timer expires without receiving an indication from the second node.

24. The apparatus of claim 23, wherein the first constraint allows the first node to process a job in the subsequent time interval if:

the programmable timer expires without receiving an indication from the second node;

or

the first node receives an indication from the second node prior to the programmable timer expiring.

25. An apparatus for processing by a first node in a distributed computing system formed by a plurality of interconnected nodes, comprising:

at least one processor configured to monitor completion of jobs by other nodes in the distributed computing system and determine, after completing processing of a job in a current time interval, whether or not to start processing a job in a subsequent time interval based on at least one constraint and the monitored completion of jobs by other nodes; and

a memory coupled with the at least one processor.

26. A computer program product for processing by a first node in a distributed computing system formed by a plurality of interconnected nodes, comprising computer readable medium having instructions stored thereon, the instructions executable by one or more processors for:

monitoring completion of jobs by other nodes in the distributed computing system; and

determining, after completing processing of a job in a current time interval, whether or not to start processing a job in a subsequent time interval based on at least one constraint and the monitored completion of jobs by other nodes.