Array of parallel programmable processing engines and deterministic method of operating the same

• US 20040006584A1
• Filed: 06/06/2003
• Published: 01/08/2004
• Est. Priority Date: 08/08/2000
• Status: Active Grant

• Current Assignee: Transwitch Corporation
• Original Assignee: Transwitch Corporation
• Inventors: Vandeweerd, Ivo
• Granted Patent: US 7,401,333 B2
• Time in Patent Office: Days
• US Class Current: 718/107
• CPC Class Codes: G06F 2117/04 Clock gating
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking
• CPC Class Codes: G06F 30/3308 using simulation
• CPC Class Codes: G06F 9/30014 with variable precision
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

The present invention provides an array of parallel programmable processing engines interconnected by a switching network. At least some of the processing engines execute a thread, and at least some threads communicate with each other through communication objects either internally within one processing engine or through the network. A scheduling step of the parallel programmable processing engines is initiated by one or more events, an event being defined by a change of a state variable of a communication object. The array comprises:

means for scheduling a scheduling step of the processing engines, the scheduling means comprising means for executing at least a first set of threads in parallel,

means for updating state values of communications objects in response to the parallel executing step, and

means for repeatedly and sequentially scheduling the executing means and the updating means until no more events occur.

The present invention also provides a deterministic method of operating such an array.

Claims

1. An array of parallel programmable processing engines interconnected by a switching network, at least some of the processing engines executing a thread, at least some threads communicating with each other through communication objects either internally within one processing engine or through the network, a scheduling step of the parallel programmable processing engines being initiated by one or more events, an event being defined by a change of a state variable of a communication object, a scheduling step comprising a delta cycle convergence step.

2. An array according to claim 1, wherein the delta cycle convergence step comprises the following steps:

step 1. the parallel processing engines being scheduled so that at least a first set of threads are executed in parallel, and

step 2. then state values of communication objects are updated,

step 3. if an event occurs in steps 1 and 2, steps 1 and 2 are repeated until no more events occur.

4. The array according to any of claims 1 to 3, wherein the programmable processing engines have at least one memory and the communication objects comprise a data structure of a mapping into memory of at least one of signals, containers and queues.

5. The array according to any of claims 1 to 4 wherein the set of threads comprises those threads that are sensitive to one or more events initiating the scheduling step.

6. The array according to any previous claim wherein the array of parallel programmable processing engines executes a system level model, the system level model comprising a plurality of concurrent processes at least some of which communicate with each other, each process being a primitive process or a further system level model, and executing a thread on one of the processing engines of the array of parallel programmable processing engines executes a primitive process.

7. The array according to any of claims 4 to 6, wherein a queue is implemented as a FIFO memory.

8. The array according to any of claims 4 to 7, further comprising a data structure in memory of the state values of the communication objects stored in memory for a number of scheduling steps.

9. The array according to any of claims 6 to 8, wherein the system level model is a model of physical processes.

26. A computer program product stored on a computer usable medium, comprising:

computer readable program means for controlling execution of an array of parallel programmable processing engines according to any of claims 1 to 9.

3. An array of parallel programmable processing engines interconnected by a switching network, at least some of the processing engines executing a thread, at least some threads communicating with each other through communication objects either internally within one processing engine or through the network, a scheduling step of the parallel programmable processing engines being initiated by one or more events, an event being defined by a change of a state variable of a communication object, the array comprising:

means for scheduling a scheduling step of the processing engines,

the scheduling means comprising means for executing at least a first set of threads in parallel,

means for updating state values of communication objects in response to the parallel executing step, and

means for repeatedly and sequentially scheduling the executing means and the updating means until no more events occur.

10. A deterministic method of operating an array of parallel programmable processing engines interconnected by a switching network, at least some of the processing engines executing a thread, at least some threads communicating with each other through communication objects either internally within one processing engine or through the network, a scheduling step of the parallel programmable processing engines being initiated by one or more events, an event being defined by a change of a state variable of a communication object, a scheduling step comprising a delta convergence cycle step.

11. A method according to claim 10, wherein the delta cycle convergence step comprises the following steps:

step 1. the parallel processing engines being scheduled so that at least a first set of threads are executed in parallel, and

step 2. then state values of communication objects are updated,

step 3. if an event occurs in steps 1 and 2, steps 1 and 2 are repeated until no more events occur.

12. The method according to any of claims 10 or 11, wherein the threads communicate through signals and/or queues and/or containers.

13. The method according to claim 12, wherein the programmable processing engines have at least one memory further comprising a step of a mapping into memory at least one of signals, containers and queues.

14. The method according to any of claims 10 to 13 wherein the set of threads comprises those threads that are sensitive to one or more events initiating the scheduling step.

15. The method according to any of the claims 10 to 14 wherein the array of parallel programmable processing engines executes a system level model, the system level model comprising a plurality of concurrent processes at least some of which communicate with each other, each process being a primitive process or a further system level model, and executing a thread on one of the array of parallel programmable processing engines executes a primitive process.

16. The method according to any of claims 13 to 15, wherein the state values of the communications objects are stored in memory for a number of scheduling steps.

17. The method according to claim 15 or 16, wherein the system level model is a model of physical processes.

25. A computer program product directly loadable into the internal memory of a digital computer, comprising software code portions for performing the steps of any of claims 10 to 20 or 23 to 24 when said product is run on a computer.

27. A computer program product stored on a computer usable medium, comprising:

computer readable program means for controlling execution of threads on an array of parallel processing engines according to any of claims 10 to 20 or 23 to 24.

18. A method for configuring an array of parallel programmable processing engines interconnected by a switching network, the array being adapted for delta cycle convergence, the configuration step comprising:

transmitting from a near location a representation of a process to be run on the array to a remote location where a further processing engine carries out any of the methods in accordance with the present invention, and

receiving at a near location a configuration file for the array.

19. The method according to claim 18 wherein at least some of the processing engines execute a thread, at least some threads communicate with each other through communication objects either internally within one processing engine or through the network, a scheduling step of the parallel programmable processing engines being initiated by one or more events, an event being defined by a change of a state variable of a communication object, the delta cycle convergence step comprising:

step 1. the parallel processing engines being scheduled so that at least a first set of threads are executed in parallel, and

step 2. then state values of communication objects are updated,

step 3. if an event occurs in steps 1 and 2, steps 1 and 2 are repeated until no more events occur.

20. The method according to claim 18 or 19 further comprising the step of loading the configuration file onto an array of processors.

21. A compiler for receiving a high level description of a computer program and for generating a compiled file for loading onto an array of parallel programmable processing engines interconnected by a switching network, wherein the compiler generates the configuration file such that when configured the array executes a delta cycle convergence step.

22. The compiler according to claim 21 wherein the compiled file when loaded onto the array causes at least some of the processing engines to execute a thread, at least some threads communicating with each other through communication objects either internally within one processing engine or through the network, a scheduling step of the parallel programmable processing engines being initiated by one or more event, an event being defined by a change of a state variable of a communication object, the delta cycle convergence step comprising:

step 1. the parallel processing engines being scheduled so that at least a first set of threads are executed in parallel, and

step 2. then state values of communication objects are updated,

step 3. if an event occurs in steps 1 and 2, steps 1 and 2 are repeated until no more events occur.

24. The method according to claim 21 wherein the compiled file when loaded onto the array causes at least some of the processing engines to execute a thread, at least some threads communicating with each other through communication objects either internally within one processing engine or through the network, a scheduling step of the parallel programmable processing engines being initiated by one or more events, an event being defined by a change of a state variable of a communication object, the delta cycle convergence step comprising:

step 1. the parallel processing engines being scheduled so that at least a first set of threads are executed in parallel, and step 2. then state values of communication objects are updated, step 3. if an event occurs in steps 1 and 2, steps 1 and 2 are repeated until no more events occur.

23. A method of receiving a high level description of a computer program and generating a compiled file for loading onto an array of parallel programmable processing engines interconnected by a switching network, comprising generating the configuration file such that when configured the array executes a delta cycle convergence step.

28. Processing node for use in an array of parallel programmable processing elements interconnected by a switching network, the processing node comprising a processing element, a memory and a communication interface for communicating with other processing nodes in the switching network, the processing node being adapted for delta cycle convergence.

29. Processing node according to claim 28, wherein the adaptation for delta cycle convergence is a software program running on the processing element.

30. Processing node according to claim 28, wherein the adaptation for delta cycle convergence is a hardware scheduling unit.

31. Processsing node according to claim 28, wherein the adaptation for delta cycle convergence comprises an operating system for the processing engine adapted for delta cycle convergence.