Distributed computation utilizing idle networked computers
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
256 Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification