Dynamic fault-tolerant parallel processing system for performing an application function with increased efficiency using heterogeneous processors

• US 5,349,682 A
• Filed: 01/31/1992
• Issued: 09/20/1994
• Est. Priority Date: 01/31/1992
• Status: Expired due to Fees

• Current Assignee: Parallel Iron LLC (IPNav)
• Original Assignee: Parallel Iron LLC (IPNav)
• Inventors: Rosenberry, Steven
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): SHAH, ALPESH
• Application Number:
  US07/829,098
• Time in Patent Office: 963 Days
• Field of Search: 395/800, 395/650, 395/575, 395/200, 395/375, 371/9.1, 371/11.3, 371/12, 371/62, 371/68.3
• US Class Current: 718/102
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/3877 using a slave processor, e.g. coprocessor peripheral processor G06F13/12; vector processor G06F15/8053
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

A parallel processing system performs an application function by a plurality of processing unit contained within a single network. The parallel processing system includes at least one slave unit connected to a common network and capable of processing a specified amount of data at a particular processing speed. At least one master unit, which may include a local slave unit, is connected to the common network and initiates an application function to be processed by the slave units. The slave units are polled to determine the processing power of each slave unit, the resources available to each slave unit and the availability of each slave unit. One or more slave units are engaged in processing the application function. If a plurality of slave units are selected, the application function is divided into a plurality of portions of data and each portion is assigned and communicated to a specific slave unit for processing. Predetermined calculations are performed on each portion of data by each slave unit.

Claims

1. A parallel processing system for performing an application function by a plurality of processing units contained within a common network, the parallel processing system comprising:

a plurality of slave units connected to the common network, each slave unit adapted to process a given amount of data specified by the application function at a particular processing power, each slave unit providing an indication of availability, present status, processing power, and resources available;

at least one master unit connected to said slave units and said common network, said master unit initiating an application function which is to be processed by said slave units, said master unit providing an indication of processing power and resources available;

pro-active polling means for polling said slave units and master unit to determine the processing power of each slave unit and the master unit, the resources available to each slave unit and said master unit, and the availability of each slave unit;

receiving means for receiving from each slave unit and master unit the processing power and resources available to each slave unit and the master unit;

selecting means for selecting one or more slave units to be engaged in processing said application function, said selection based upon the received processing power and resources available to each slave unit and the master unit and the availability of each slave unit;

dividing means for dividing said application function in a manner defined by the application function into a plurality of specified portions of data, each specified portion of data being assigned and communicated to a different specific slave unit for processing; and

calculating means for performing predetermined calculations defined by the application function on each said specified portion of data by each slave unit;

each slave unit including means for being accessible for performing local processing, the local processing having priority over and discontinuing the processing of the specified portion of data assigned to the slave unit, the master unit including means for having the option to select an alternate unit for processing the specified portion of data assigned to a slave unit performing local processing, the alternate unit being selected from the master unit and available slave units.

2. A parallel processing system according to claim 1, further including merging means defined by the application function for optionally merging each calculated portion of data at said master unit, said merged data representing a processed application function.

3. A parallel processing system according to claim 1 wherein said polling means further includes estimating means for estimating the processing power of each slave unit.

4. A parallel processing system according to claim 1, wherein said common network is a local area network.

5. A parallel processing system according to claim 1, wherein said master unit can be any one of the processing units located within the common network.

6. A parallel processing system according to claim 5, wherein said master unit includes a local slave unit.

7. A parallel processing system according to claim 6, wherein said local slave unit performs at least a portion of the processing of the application function.

8. A parallel processing system according to claim 1, further comprising fault tolerance means for determining the present status of each slave unit and for detecting an uncompleted calculated portion of data.

9. A parallel processing system according to claim 1, further comprising fault tolerance means for determining the present status of each slave unit and for detecting a fault occurring at the slave unit.

10. A parallel processing system according to claim 8, further comprising data assigning means for assigning a portion of data which has been originally assigned to a remote slave unit which is still calculating the portion of data to another slave unit for performing calculation functions on the assigned data.

11. A parallel processing system according to claim 9, further comprising data assigning means for assigning a portion of data originally assigned to a failed remote slave unit to another slave unit to perform the predetermined calculations on the assigned data.

12. A parallel processing system according to claim 1 wherein said master unit is adapted to process a particular application function as a single execution process.

13. A method for performing parallel processing of an application function by a plurality of processing units contained within a single network, said processing units including a plurality of slave units, each slave unit adapted to process a specified amount of data defined by the application function at a particular processing power, and at least one master unit contained within the network, said master unit initiating the application function which is to be processed and including a local slave unit, each slave unit being accessible for performing local processing, the local processing having priority over and discontinuing the processing of the specified amount of data, said method comprising the steps of:

a) estimating at each slave unit the processing power of the slave unit;

b) polling each slave unit pro-actively to determine the processing power and availability of each slave unit;

c) receiving the processing power and availability of each slave unit;

d) selecting a number of slave units to be engaged in processing said application function, said selection based upon the received processing power and availability of each slave unit;

e) dividing said application function in a manner defined by the application function into specified portions of data;

f) assigning each specified portion of data to a different specific selected slave unit;

g) performing at each specific selected slave unit predetermined calculations defined by said application function on each said specified portion of data and producing calculated specified portions of data; and

h) optionally selecting an alternate unit for processing the specified portion of data assigned to a slave unit performing local processing, the alternate unit being selected from the master unit and available slave units.

14. A method according to claim 13 further comprising the step of:

h) merging, as defined by the application function, the calculated specified portions of data at said master unit to provide a processed application function.

15. A method according to claim 13, further comprising the steps of:

i) determining which remote slave units have not completed calculating their assigned portion of data; and

j) assigning the specified portion of data originally assigned to the remote slave unit to another slave unit.

16. A method according to claim 13, further comprising the steps of:

k) determining which remote slave units have failed; and

l) assigning the specified portion of data originally assigned to the failed remote slave unit to another slave unit.

17. A parallel processing system for performing an application function by a plurality of processing units contained within a common network, the parallel processing means comprising:

a plurality of remote slave units, each remote slave unit being interconnected to other remote slave units by a common network and adapted to process a specified amount of data defined by the application function at a particular processing power, said remote slave units providing indications of availability, processing power, and resources available;

a master unit connected to said remote slave units and said common network, said master unit initiating an application function which is to be processed by said remote slave units, said master unit providing an indication of processing power and resources available;

pro-active retrieving means for retrieving from said slave units and said master unit the processing power of each remote slave unit and the master unit, the resources available to each remote slave unit and the master unit, and the availability of each remote slave unit;

selecting means for selecting a number of remote slave units to be engaged in processing said application function, said selection based upon the processing power, the resources available, and the availability retrieved from each remote slave unit; and

dividing means for dividing said application function in a manner defined by said application function into specified portions of data, each specified portion of data being assigned to a different specific remote slave unit for processing;

each slave unit including means for being accessible for performing local processing, the local processing having priority over and discontinuing the processing of the specified portion of data assigned to the slave unit, the master unit including means for having the option to select an alternate unit for processing the specified portion of data assigned to a slave unit performing local processing, the alternate unit being selected from the master unit and available slave units.

18. A parallel processing system according to claim 17, wherein said master unit includes a local slave unit.

19. A parallel processing system according to claim 18, wherein said local slave unit receives a specified portion of data for processing.

20. A parallel processing system according to claim 17, further comprising calculating means for performing predetermined calculations defined by said application function on said specified portions of data by said remote slave units and said local slave unit.

21. A parallel processing system according to claim 20, further comprising optional merging means defined by the application function for merging each calculated portion of data at said master unit, said merged data representing a processed application function.

22. A parallel processing system according to claim 17, wherein said master unit can be any processing unit located within the common network.

23. A parallel processing system according to claim 21, further comprising fault tolerating means for detecting at a completion of a given event those remote slave units which are still calculating a portion of data.

24. A parallel processing system according to claim 23, further comprising data assigning means for assigning the portion of data which has originally been assigned to said remote slave unit which is still calculating the portion of data to another slave unit for performing the calculating functions on the assigned data.

25. A parallel processing system according to claim 21, further comprising fault tolerating means for detecting at a completion of a given event those remote slave units which have failed.

26. A parallel processing system according to claim 25, further comprising data assigning means for assigning the portion of data originally assigned to a failed remote slave unit to another slave unit to perform the predetermined calculations on the assigned data.