Parallel computing system, method and architecture

• US 20030177240A1
• Filed: 12/04/2002
• Published: 09/18/2003
• Est. Priority Date: 12/04/2001
• Status: Active Grant

• Current Assignee: Simtone Corporation
• Original Assignee: Powerllel Corporation (Simtone Corporation)
• Inventors: Gulko, Abraham, Mellor, David
• Granted Patent: US 7,174,381 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083
• CPC Class Codes: G06F 8/456 Parallelism detection
• 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/505 considering the load
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

A parallel or computing system and method make use of a plurality of adapters each affording a specific type of processing algorithm. At each point in an application, an adapter is identified, to parallelize that portion of the application. The process involves associating an appropriate adapter with the application portion, parsing the application portion to define tasks that may be distributed over the available computers. Combined with the parallelized program is a software server that is designed to cooperate with the adapters to control and supervise distributed processing functions. Such functions include mapping, load balancing, and error detection and correction. Also included are functions that cause the results of the computing to be coordinated in real-time and returned appropriately, according to the application. In addition to the parallelized program and server, an application created by the present invention is provided with the functionality of virtual middleware, which interfaces with and controls existing forms of middleware.

Claims

1. A method for parallelizing an application, comprising the steps of:

providing a plurality of adapters each affording a specific type of processing algorithm;

at successive portions in an application, identifying an adapter appropriate for parallelizing that portion of the application;

associating the identified adapter with the portion;

generating a code segment which represents the functionality of for each identified portion and which includes a call to a client-server library;

including a call to the client-server library in the application which, at run-time, launches said codes segment from a main entry point in each respective code segment in lieu of executing the portion.

2. The method of claim 1, wherein, at run-time, the client-server library returns values to the application as a result of launching said code segments.

3. The method of claim 1, including the additional steps of providing a software server, the server cooperating with the adapters to control and supervise distributed processing of one or more of said code segments.

4. The parallel computing method of claim 3, wherein the distributed processing functions include at least one of mapping, load balancing, and error detection and correction.

5. The parallel computing method of claim 3, wherein the distributed processing functions coordinate results of the computing in real-time and return said results according to the application.

6. A method for running a parallelized application in which a pool of work is to be performed, comprising the steps of:

using a master server that operates in a master mode, instantiating a stateless server which contains a first object including a code segment suitable for processing work from the pool;

dispatching from the master server to the stateless server a first portion of work from the pool;

reporting to the master server a progress of the first portion of work dispatched to the stateless server; and

distributing additional portions of work from the master server to the stateless server once a prescribed amount of work progress has been reported by the stateless server.

7. The method of claim 6, including the additional steps of:

establishing the stateless server in a slave mode prior to the reporting step; and

performing the first portion of work on the stateless server.

8. The method of claim 6, including the additional steps of:

establishing the stateless server in a master mode prior to the reporting step;

instantiating a plurality of further servers, a set of said further servers operating in a slave mode;

splitting the first portion of work for performance by said further servers;

performing the split first portion of work at said further servers; and

advising the stateless server of the progress of the first portion of work performed by said further servers.

9. The method of claim 8, wherein the splitting step comprises splitting the first portion of work from the pool into overlapping parts.

10. The method of claim 8, wherein the splitting step comprises splitting the first portion of work from the pool into overlapping parts.

11. The method of claim 6, including the additional steps of:

monitoring at the master server the progress reported by the stateless server; and

redistributing from the master server the first portion of work from the pool to a different stateless server in the event that a prescribed criterion is not met.

12. The method of claim 11, wherein the prescribed criterion is that a progress measure has advanced by a threshold amount since a prior reporting step.

13. The method of claim 11, including the additional step of terminating the first portion of work running on the stateless server.

14. The method of claim 6, wherein the first portion of work has a first size, the method including the additional steps of:

analyzing the progress reported to the master server by the stateless server;

establishing a second size for said additional portions of the work in the pool to be distributed to the stateless server in response to the analyzing step; and

distributing additional portions of work from the master server to the stateless server with each additional portion having the second size,

whereby the master server balances the load to the stateless servers in real-time in order to maintain the prescribed amount of work progress below 100%.

15. The method of claim 14, wherein the second size is different than the first size.

16. The method of claim 14, wherein the second size is the same as the first size.

17. The method of claim 6, wherein the first portion of work has a first size, the method including the additional steps of:

establishing the stateless server in a master mode prior to the reporting step,

instantiating a plurality of further servers, a set of said further servers operating in a slave mode;

splitting the first portion of work for performance by said further servers;

performing the split first portion of work at said further servers;

reporting to the stateless server the progress of the first portion of work performed by said further servers;

analyzing the progress reported to the stateless server;

establishing a second size for said additional portions of the work in the pool to be distributed to said further servers in response to the analyzing step; and

distributing additional portions of work from the stateless server to said further servers with each additional portion having the second size,

whereby the stateless server balances the load to said further servers in real-time in order to maintain the prescribed amount of work progress below 100%.

18. A method for running a parallelized application, comprising the steps of:

obtaining a portion of an application at a first server, the portion containing an algorithm to process and an interface to a crosscaller;

executing the portion at the first server in a master mode;

calling the interface to obtain global data for use as an input to the algorithm executing at the server;

replicating the portion from the first server to at least one other resource; and

permitting the replicated portion to dynamically select whether to operate in a master or slave mode.

19. The method of claim 18 including the additional step of monitoring the distributed portions for stalls/dead threads.