Distributed computation utilizing idle networked computers

• US 6,009,455 A
• Filed: 04/20/1998
• Issued: 12/28/1999
• Est. Priority Date: 04/20/1998
• Status: Expired due to Fees

• Current Assignee: John F. Doyle
• Original Assignee: John F. Doyle
• Inventors: Doyle, John F.
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/063,257
• Time in Patent Office: 617 Days
• Field of Search: 709/102, 709/105, 709/106, 709/201, 709/202, 709/203, 709/204, 709/205, 709/208, 709/220, 709/223, 709/226, 709/248, 709/300
• US Class Current: 709/201
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

The present invention utilizes the otherwise unproductive minutes and hours when a networked client computer is not in use by a local human operator. The method and system described herein allow multiple partitioned computations to be queued for distribution to any number of client computers when the clients indicate their availability. Availability may be determined by the same criteria used to activate screen-saver programs, i.e., a predetermined time without any keyboard or mouse input. Application programs are designed to accept a common calling sequence. An application-independent master control program coordinates the distribution of computation segments, the combination of partial results, and the formatting of the final result. An application-independent client control program reports availability of client computers, downloads application program files, invokes the application to compute partial results for a range of computation segments, and uploads the partial results to the master computer. One class of distributed computation supported is finding the minimum or maximum value of a calculated target cell in a spreadsheet, based on a number of input cells taking values within a specified range.

Claims

1. A method for performing one or more distributed computations on a plurality of general purpose computers that are connected by a communications network, each distributed computation comprising a hierarchy of (i) one or more subordinate computation segments distributed among the computers, each segment producing a segment result, and (ii) one or more combine functions that combine the results of subordinate computation segments into a combined result, the hierarchy arranged such that a topmost combine function produces a final result, wherein the method comprises:

providing a master computer;

providing a plurality of client computers;

executing on the master computer a master control program, where the master control program is applications independent and includes a qualification algorithm and an assignment algorithm;

executing on each client computer an availability algorithm;

connecting the availability algorithms to the master control program via a communications network;

providing a job request means in signal connection to the master control program;

providing a job output means in signal connection to the master control program;

submitting one or more job requests for distributed computation via the job request means to the master control program, each job request including one or more files or file references required to perform the distributed computation, the files or file references including an executable job computation module;

determining by the availability algorithm asynchronously on each of one or more client computers whether the client computer is an available client;

for each available client,

(a) sending an availability message from the available client via the network to the master control program, where the availability message signals the readiness of the available client to participate in one or more distributed computations,

(b) determining by the qualification algorithm in the master control program whether the available client shall be declared a selected client for a particular job request,

for each selected client for a particular job request;

(a) executing on the selected client a client control program, where the client control program is application independent;

(b) defining by the assignment algorithm in the master control program a segment group package containing one or more computation segments and the combine function,

(c) downloading the segment group package to the selected client via the network,

(d) computing the group result by performing the computation segments and group combine function under the control of the client control program on the selected client,

(e) communicating the group result via the network to the master control program;

computing the final result by the combine algorithm in the master computer;

communicating the result to the job output means via a job output signal;

whereby, through the use of idle time on a plurality of networked general purpose computers, the results of distributed computations are produced more economically than they could be produced using dedicated computers.

2. The method of claim 1, wherein the availability algorithm is embodied in a program activated by a screen saver feature of the client computer'"'"'s operating system.

3. The method of claim 1, wherein the availability algorithm is embodied in a program executed on a periodic, scheduled basis.

4. The method of claim 1 where the client control program is executed by a network browser.

5. The method of claim 1 where the availability algorithm is executed by a network browser.

6. The method of claim 1 where the availability algorithm includes functions of one or more parameters selected from the group consisting of:

time of user inactivity, pattern of user activity, time-of-day, day-of-week, scheduled holidays.

7. The method of claim 1 where the master control program and the client control program invoke copies of a single executable job computation module in distinct modes, the distinct modes performing functions including one or more from the group consisting of:

calculate the number of subordinate computation segments based on the contents of one or more files included or referenced in the job request,

calculate one or more computation segment results,

perform the combine function,

format the final result for storage or presentation on the output means.

8. The method of claim 1, wherein the master control program calculates

(a) a download time required to download the segment group package to each selected client and

(b) a compute time required by the each selected client to compute the group result,

wherein the assignment algorithm adaptively computes the preferred number of computation segments in an segment group package based on previously calculated download times and compute times for one or more selected clients, whereby the total time required to produce the final result is reduced.

9. The method of claim 1, wherein the job request means communicates resource requirements in conjunction with requests for distributed computation, wherein the availability algorithm (i) determines a resource profile including the existence and configuration of specific resources on the client computer and (ii) communicates the profile to the master control program, wherein the qualification algorithm compares the resource requirements of each request to the resource profile of each available client in selecting the available client to be a selected client.

10. The method of claim 9, wherein resource requirements include one or more requirements selected from the group consisting of:

(a) a particular spreadsheet program is previously installed on the client computer,

(b) a particular operating system is previously installed on the client computer,

(c) a particular CPU type or family is installed on the client computer,

(d) a specified amount of disk space is available on the client computer, and

(e) a specified amount of main CPU memory is installed on the client computer.

11. A system for performing one or more distributed computations on a plurality of general purpose computers that are connected by a communications network, each distributed computation comprising a hierarchy of (i) one or more subordinate computation segments distributed among the computers, each segment producing a segment result, and (ii) one or more combine functions that combine the results of subordinate computation segments into a combined result, the hierarchy arranged such that a topmost combine function produces a final result, wherein the system comprises:

a master computer;

a job request means in signal connection to the master computer used to submit one or more job requests for distributed computation, the job request including one or more files or file references required to perform the distributed computation, the files or file references including an executable job computation module;

a plurality of client computers;

a communications network connecting the client computers to the master computer;

an availability algorithm executing on each client computer, where the availability algorithm determines whether the client computer is an available client;

an availability signal from the availability algorithm on each of the available clients sent via the network to the master control program, where the signal indicates the readiness of each available client to participate in one or more distributed computations;

a client control program on each selected client that;

(a) computes the group result by performing the assigned computation segments and group combine function,

(b) communicates the group result via the network to the master control program;

a job output means in signal connection to the master computer, the job output means used to present and/or store of the results of distributed computation;

a master control program executing on the master computer, where the master control program is applications independent and includes logic for accepting job requests, coordinating the execution of computation segments by client computers, collecting group results sent by the client computers, computing the final result by the combine function, communicating the final result to the job output means via a job output signal;

a qualification algorithm subordinate to the master control program, the qualification algorithm determining, for each available client, whether the available client shall be declared a selected client for a particular job request,

an assignment algorithm subordinate to the master control program, the assignment algorithm (i) defining for a selected client a segment group package containing one or more computation segments and the combine function and (ii) downloading the segment group package to the selected client via the network,

whereby, through the use of idle time on a plurality of networked general purpose computers, the results of distributed computations are produced more economically than they could be produced using dedicated computers.

12. The system of claim 11, wherein the availability algorithm is embodied in a program activated by a screen saver function of the client computer'"'"'s operating system.

13. The system of claim 11, wherein the availability algorithm is embodied in a program executed on a periodic, scheduled basis.

14. The system of claim 11 where the client control program is executed by a network browser.

15. The system of claim 11 where the availability algorithm is executed by a network browser.

16. The system of claim 11 where the availability algorithm includes functions of one or more parameters selected from the group consisting of time of user inactivity, pattern of user activity, time-of-day, day-of-week, scheduled holidays.

17. The system of claim 11 where the master control program and the client control program invoke copies of a single executable job computation module in distinct modes, the distinct modes performing functions including one or more from the group consisting of:

calculate the number of subordinate computation segments based on input files,

calculate one or more computation segment results,

perform the combine function,

format the final result for presentation on the output means.

18. The system of claim 11, wherein the master control program calculates

(a) a download time required to download the segment group package to each selected client and

(b) a compute time required by the each selected client to compute the group result,

wherein the assignment algorithm adaptively computes the preferred number of computation segments in a segment group package based on previously calculated download times and compute times for one or more selected clients, whereby the total time required to produce the final result is reduced.

19. The system of claim 11, wherein the job request means communicates resource requirements in conjunction with requests for distributed computation, wherein the availability algorithm (i) determines a resource profile including the existence and configuration of specific resources on the client computer, and (ii) communicates the profile to the master control program, and wherein the qualification algorithm compares the resource requirements of each request to the resource profile of each available client in selecting the available client to be a selected client.

20. The system of claim 19, wherein resource requirements include one or more requirements selected from the group consisting of

(a) a particular spreadsheet program is previously installed on the client computer,

(b) a particular operating system is previously installed on the client computer,

(c) a particular CPU type or family is installed on the client computer,

(d) a specified amount of disk space is available on the client computer,

(e) a specified amount of main CPU memory is installed on the client computer.