Method and apparatus for time management and scheduling for sychronous processing on a cluster of processing nodes

• US 9,373,074 B2
• Filed: 10/09/2012
• Issued: 06/21/2016
• 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.
• Primary Examiner(s): PATEL, HIREN P
• Application Number:
  US13/647,772
• Publication Number:
  US 20140101661A1
• Time in Patent Office: 1,351 Days
• Field of Search: None
• 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/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 which maintain their own relative time, comprising:

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

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

determining a time offset for a connection between the first node and the second node, based on a difference in timestamps between the first node and at least the second node, wherein each of the timestamps indicates an interval for which a corresponding job is completed by a respective node,

wherein the at least one constraint is defined by a value that specifies a maximum number of jobs the first node is allowed to process ahead of a second node, and the at least one constraint prevents the first node from processing a job in the subsequent time interval of the first node before at least the second node has begun processing a job in an interval later than a subsequent time interval of the first node adjusted based on the time offset.

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

3. The method of claim 1, wherein monitoring completion of jobs by other nodes comprises receiving an indication from a respective node of the other nodes reporting completion of jobs.

4. The method of claim 3, wherein each of the indications provides a timestamp indicating the interval for which a corresponding job is completed by the respective node of the other nodes sending the indication.

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

6. The method of claim 5, 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.

7. The method of claim 3, 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 one or more of the indications received from the respective other nodes.

8. The method of claim 1, further comprising:

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

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

9. The method of claim 8, wherein based on at least the first constraint, the first node processes 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.

10. An apparatus for processing by a first node in a distributed computing system formed by a plurality of interconnected nodes which maintain their own relative time, comprising:

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

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

means for determining a time offset for a connection between the first node and the second node, based on a difference in timestamps between the first node and at least the second node wherein each of the timestamps indicates an interval for which a corresponding job is completed by a respective node,

wherein the at least one constraint is defined by a value that specifies a maximum number of jobs the first node is allowed to process ahead of a second node, and the at least one constraint prevents the first node from processing a job in the subsequent time interval of the first node before at least the second node has begun processing a job in an interval later than a subsequent time interval of the first node adjusted based on the time offset.

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

12. The apparatus of claim 10, wherein the means for monitoring completion of jobs by other nodes comprises receiving an indication from a respective node of the other nodes reporting completion of jobs.

13. The apparatus of claim 12, wherein each of the indications provides a timestamp indicating the interval for which a corresponding job is completed by the respective node of the other nodes sending the indication.

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

15. The apparatus of claim 14, 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.

16. The apparatus of claim 12, 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 one or more of the indications received from the respective other nodes.

17. The apparatus of claim 10, further comprising:

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

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

18. The apparatus of claim 17, wherein based on at least the first constraint, the first node processes 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.

19. An apparatus for processing by a first node in a distributed computing system formed by a plurality of interconnected nodes which maintain their own relative time, comprising:

at least one processor configured to monitor completion of jobs by other nodes in the distributed computing system, determine, after completing processing of a job in a current time interval of the first node, whether or not to start processing a job in a subsequent time interval of the first node based on at least one constraint and the monitored completion of jobs by other nodes, and determine a time offset for a connection between the first node and the second node, based on a difference in timestamps between the first node and at least the second node, wherein each of the timestamps indicates an interval for which a corresponding job is completed by a respective node,

wherein the at least one constraint is defined by a value that specifies a maximum number of jobs the first node is allowed to process ahead of a second node and the at least one constraint prevents the first node from processing a job in the subsequent time interval of the first node before at least the second node has begun processing a job in an interval later than a subsequent time interval of the first node adjusted based on the time offset; and

a memory coupled with the at least one processor.

20. A non-transitory computer readable medium for processing by a first node in a distributed computing system formed by a plurality of interconnected nodes which maintain their own relative time, the non-transitory 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;

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

determining a time offset for a connection between the first node and the second node, based on a difference in timestamps between the first node and at least the second node, wherein each of the timestamps indicates an interval for which a corresponding job is completed by a respective node,

wherein the at least one constraint is defined by a value that specifies a maximum number of jobs the first node is allowed to process ahead of a second node, and the at least one constraint prevents the first node from processing a job in the subsequent time interval of the first node before at least the second node has begun processing a job in an interval later than a subsequent time interval of the first node adjusted based on the time offset.