Task distribution processing system and the method for subscribing computers to perform computing tasks during idle time

• US 6,112,225 A
• Filed: 03/30/1998
• Issued: 08/29/2000
• Est. Priority Date: 03/30/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wisebond, Marat, Kraft, Reiner, Lu, Qi
• Primary Examiner(s): Luu, Le Hien
• Assistant Examiner(s): Prieto, Beatriz
• Application Number:
  US09/050,608
• Time in Patent Office: 883 Days
• Field of Search: 709/100, 709/201, 709/219, 709/227, 709/304, 709/102, 709/205, 709/217, 709/224, 709/202, 713/323, 712/28, 364/200, 364/281, 364/3, 364/468
• US Class Current: 709/202
• 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
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

A computer executable "aggregate" task is processed by dividing it into subtasks and distributing the subtasks "on demand" to remotely located subscribing computers via a computer network. The aggregate task originates at a coordinating computer, coupled to one or more peripheral computers by appropriate communications links. The coordinating computer divides the aggregate task into multiple independent subtasks. Each peripheral computer begins to "subscribe" to the coordinating computer'"'"'s aggregate task by obtaining an "idle time activation program" from the coordinating computer, and then installing the program locally. The idle time activation program which may include a screen saver, activates automatically when the subscribing computer is inactive. Continuing the subscription process, each peripheral computer requests a subtask from the coordinating computer. In response, the coordinating computer distributes different subtasks among the subscribing computers, completing the subscription process. The subscribing computers automatically work on their respective subtasks whenever they are idle, as directed by the local idle time activation program. When a subscribing computer completes its subtask, it transmits results back to the coordinating computer. When results of all subtasks have been received from subscribing computers, the coordinating computer compiles and stores these results, concluding the aggregate task.

Claims

1. A method performing a computing task comprising operations of:

a coordinating computer receiving an aggregate computing task divisible into multiple independent subtasks;

announcing an opportunity for other computers to participate in the aggregate computing task, and in response, one or more subscribing computers submitting requests to participate in the aggregate computing task, the subscribing computers including one or more computers having principal functions distinct from the aggregate computing task;

the coordinating computer receiving the requests from subscribing computers, and in response, the coordinating computer assigning the subtasks by distributing the subtasks among the subscribing computers, and also sending an idle time activation program to each subscribing computer;

each subscribing computer installing the idle time activation program, whereupon the idle time activation program causes the subscribing computer to perform operations including working toward completion of the assigned subtask when the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal functions, and halting work toward completion of the assigned subtask when the subscribing computer is not in the predefined idle state; and

in response to each subscribing computer'"'"'s completion of its assigned subtask, transmitting results of the completed subtask to the coordinating computer.

2. The method of claim 1, the method further comprising:

in response to completion of a subscribing computer'"'"'s subtask, the subscribing computer submitting a request for another subtask to the coordinating computer, and the coordinating computer returning a new subtask.

3. The method of claim 1, where the idle time activation program further causes the subscribing computer, in response to halting work toward completion of the assigned subtask, to store intermediate results of the work and then to build upon the intermediate results upon resuming work toward completion of the assigned subtask.

4. The method of claim 1, the detecting of whether the subscribing computer is in a predefined idle state including:

determining that the computer is not in the idle state in response to occurrence of a predetermined hardware interrupt.

5. The method of claim 1, the predefined idle state comprising absence of input from one or more operator input devices coupled to the subscribing computer for a predetermined period of time.

6. The method of claim 1, the predefined idle state comprising a prescribed level of processing activity of the subscribing computer.

7. The method of claim 1, the predefined idle state comprising a prescribed level of input/output activity of the subscribing computer.

8. The method of claim 1, the operations further comprising:

utilizing the public Internet to conduct communications between the coordinating computer and the subscribing computers.

9. The method of claim 8, the operations further comprising:

detecting whenever the subscribing computer is in the idle state, performed by the idle time activation program.

10. A method for a subscribing computer to participate in an aggregate computing task, where the subscribing computer has a principal function distinct from the aggregate computing task, the method comprising the operations of:

in response to an announcement of an opportunity for computers to participate in an aggregate computing task, submitting a request to participate in the subscribing aggregate computing task;

receiving from the coordinating computer at least one of multiple independent subtasks of an aggregate computing task, and also receiving an idle time activation program;

installing the idle time activation program, whereupon the idle time activation program causes the subscribing computer to perform operations including working toward completion of the assigned subtask when the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal functions, and halting work toward completion of the assigned subtask when the subscribing computer is not in the predefined idle state; and

in response to the completion of the received subtask, transmitting results of the subtask to the coordinating computer.

11. The method of claim 10, the method further comprising:

in response to completion of a subscribing computer'"'"'s subtask, the subscribing computer submitting a request for another subtask to the coordinating computer, and the coordinating computer returning a new subtask.

12. The method of claim 10, where the idle time activation program further causes the subscribing computer, in response to halting work toward completion of the assigned subtask, to store intermediate results of the work, and then to build upon the intermediate results upon resuming work toward completion of the assigned subtask.

13. The method of claim 10, the detecting of whether the subscribing computer is in a predefined idle state including:

determining that the computer is not in the idle state in response to occurrence of a predetermined hardware interrupt.

14. The method of claim 10, the predefined idle state comprising absence of input from one or more operator input devices coupled to the subscribing computer for a predetermined period of time.

15. The method of claim 10, the predefined idle state comprising a prescribed level of processing activity of the subscribing computer.

16. The method of claim 10, the predefined idle state comprising a prescribed level of input/output activity of the subscribing computer.

17. The method of claim 10, the operations further comprising:

utilizing the public Internet to conduct communications between the coordinating computer and the subscribing computers.

18. The method of claim 17, the operations further comprising:

detecting whenever the subscribing computer is in the idle state, performed by the idle time activation program.

19. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations for a subscribing computer to participate in an aggregate computing task, where the subscribing computer has a principal function distinct from the aggregate computing task, the method being performed by a subscribing computer and comprising:

in response to an announcement of an opportunity for computers to participate in an aggregate computing task, submitting a request to participate in the subscribing aggregate computing task;

receiving from the coordinating computer at least one of multiple independent subtasks of an aggregate computing task, and also receiving an idle time activation program;

installing the idle time activation program, whereupon the idle time activation program causes the subscribing computer to perform operations including working toward completion of the assigned subtask when the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal functions, and halting work toward completion of the assigned subtask during periods when the subscribing computer is not in the predefined idle state; and

in response to the completion of the received subtask, transmitting results of the subtask to the coordinating computer.

20. The medium of claim 19, the method further comprising:

in response to completion of a subscribing computer'"'"'s subtask, the subscribing computer submitting a request for another new subtask to the coordinating computer, and the coordinating computer returning a new new subtask.

21. The medium of claim 19, where the idle time activation program further causes the subscribing computer, in response to halting work toward completion of the assigned subtask, to store intermediate results of the work, and then to build upon the intermediate results upon resuming work toward completion of the assigned subtask.

22. The medium of claim 19, the detecting of whether the subscribing computer is in a predefined idle state including:

determining that the computer is not in the idle state in response to occurrence of a predetermined hardware interrupt.

23. The medium of claim 19, the predefined idle state comprising absence of input from one or more operator input devices coupled to the subscribing computer for a predetermined period of time.

24. The medium of claim 19, the predefined idle state comprising a prescribed level of processing activity of the subscribing computer.

25. The medium of claim 19, the predefined idle state comprising a prescribed level of input/output activity of the subscribing computer.

26. The medium of claim 19, the operations further comprising:

utilizing the public Internet to conduct communications between the coordinating computer and the subscribing computers.

27. The medium of claim 26, the operations further comprising:

detecting whenever the subscribing computer is in the idle state, performed by the idle time activation program.

28. A system to distributively perform a processing task divisible into multiple independent subtasks, comprising:

a coordinating computer, comprising;

a task scheduler programmed to distribute multiple subtasks of an aggregate computing task among multiple different subscribing compilers by performing operations comprising;

announcing an opportunity for other computers to participate in an aggregate computing task from one or more subscribing computers having principal functions distinct from the aggregate computing task, the aggregate computing task being divisible into multiple independent subtasks;

assigning the subtasks by distributing the subtasks among the subscribing computers;

a result manager programmed to formulate a completed result by compiling completed subtasks of the subscribing computers;

one or more communications links coupled to the coordinating computer; and

the subscribing computers, each coupled to the communications links and comprising;

a task manager programmed to perform operations to submit requests to the coordinating computer for subtasks, receive assigned subtasks, and submit results of completed subtasks to the coordinating computer, the operations comprising;

in response to the announcement, submitting a request to participate in the subscribing aggregate computing task;

receiving from the coordinating computer at least one of the multiple subtasks;

idle mode detector to detect whenever the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal functions; and

a task execution engine responsive to the idle mode detector to work toward completion of the received subtask when the subscribing computer is in the predefined idle state and halt work toward completion of the subtask when the subscribing computer is not in the predetermined idle state.

29. The system of claim 28, the task manager being responsive to completion of a subtask to submit a request for a new subtask to the coordinating computer.

30. The system of claim 28, the task execution engine being responsive to each halting of work toward completion of the subtask to store intermediate results of the work, the task executing engine proceeding from the intermediate results when next working toward completion of the received subtask.

31. The system of claim 28, idle time activation module detecting whether the subscribing computer is in a predefined idle state comprising:

determining that the computer is not in the idle state in response to occurrence of a predetermined hardware interrupt.

32. The system of claim 28, the predefined idle state comprising absence of input from one or more operator input devices coupled to the subscribing computer for a predetermined period of time.

33. The system of claim 28, the predefined idle state comprising a prescribed level of processing activity of the subscribing computer.

34. The system of claim 28, the predefined idle state comprising a prescribed level of input/output activity of the subscribing computer.

35. The system of claim 28, the idle mode detector including a screen saver program that performs the detecting of whenever the subscribing computer is in the predefined idle state, the screen saver further activating a video display preserving function whenever the subscribing computer is in the predefined idle state.

36. A subscribing computer configured to participate in distributed performance of an aggregate computing task divisible into multiple independent subtasks, the subscribing computer having a principal function unrelated to the aggregate computing task, the subscribing computer comprising:

task manager programmed to perform operations to submit requests to the coordinating computer for subtasks, receive assigned subtasks, and submit results of completed subtasks to the coordinating computer the operations comprising;

in response to an announcement of an opportunity for computers to participate in an aggregate computing task, submitting a request to participate in the subscribing aggregate computing task;

receiving from the coordinating computer at least one of multiple independent subtasks of an aggregate computing task;

an idle mode detector to detect whenever the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal functions; and

a task execution engine, responsive to the idle mode detector to work toward completion of the received subtask when the subscribing computer is in the predefined idle state and halt work toward completion of the subtask when the subscribing computer is not in the predefined idle state.

37. A system to distributively perform a processing task divisible into multiple independent subtasks, comprising:

a coordinating computer, comprising;

task scheduling means for distributing multiple subtasks of an aggregate computing task among multiple different subscribing compilers by;

announcing an opportunity for other computers to participate in an aggregate computing task from one or more subscribing computers having principal functions distinct from the aggregate computing task, the aggregate computing task being divisible into multiple independent subtasks;

assigning the subtasks by distributing the subtasks among the subscribing computers;

result managing means for formulating a completed result by compiling completed subtasks of the subscribing computers;

communications means coupled to the coordinating computer; and

the subscribing computers, each coupled to the communications means and comprising;

task managing means for submitting requests to the coordinating computer for subtasks, receiving assigned subtasks, and submitting results of completed subtasks to the coordinating computer by;

in response to the announcement, submitting a request to participate in the subscribing aggregate computing task;

receiving from the coordinating computer at least one of multiple independent subtasks of an aggregate computing task;

idle mode detector means for detecting whenever the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal function;

task execution engine means responsive to the idle mode detector for working toward completion of the received subtask when the subscribing computer is in the predefined idle state and halting work toward completion of the subtask when the subscribing computer is not in the predefined idle state.

38. A subscribing computer configured to participate in distributed performance of an aggregate computing task divisible into multiple independent subtasks, the subscribing computer having a principal function unrelated to the aggregate computing task, the subscribing computer comprising:

task managing means for submitting requests to the coordinating computer for subtasks, receiving assigned subtasks, and submitting results of completed subtasks to the coordinating computer by;

in response to an announcement of an opportunity for computers to participate in an aggregate computing task, submitting a request to participate in the subscribing aggregate computing task;

receiving from the coordinating computer at least one of multiple independent subtasks of an aggregate computing task;

idle mode detecting means for detecting whenever the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal functions; and

task execution means responsive to the idle mode detector means for working toward completion of the received subtask when the subscribing computer is in the predetermined idle state and halting work toward completion of the subtask when the subscribing computer is not in the predefined idle state.

39. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a coordinating computer to perform operations to complete an aggregate computing task, the operations comprising:

receiving an aggregate computing task, divisible into multiple independent subtasks;

obtaining agreement to participate in the aggregate computing task from one or more subscribing computers having principal functions unrelated to the aggregate computing task;

assigning the subtasks by distributing the subtasks among the subscribing computers, and also sending an idle time activation program causing the subscribing computer to perform operations including;

working toward completion of the assigned subtask when the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal functions; and

halting work toward completion of the assigned subtask when the subscribing computer is not in the predefined idle state; and

in response to completion of the subscribing computer'"'"'s subtask, transmitting results of the subtask to the coordinating computer.

40. A coordinating computer for performing an aggregate computing task divisible into multiple independent subtasks, comprising:

a task scheduler, programmed to distribute subtasks among multiple different subscribing compilers by performing operations comprising;

obtaining agreement to participate in an aggregate computing task from one or more subscribing computers having principal functions unrelated to the aggregate computing task;

assigning the subtasks by distributing the subtasks among the subscribing computers, and also sending an idle time activation program causing the subscribing computer to perform operations including;

working toward completion of the assigned subtask when the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s principal functions; and

halting work toward completion of the assigned subtask when the subscribing computer is not in the predefined idle state; and

in response to completion of the subscribing computer'"'"'s subtask, transmitting results of the subtask to the coordinating computer;

a result manager, programmed to formulate a completed result by compiling completed subtasks of the subscribing computers.

41. A method of doing business, comprising operations of:

operators of one or more subscribing computers submitting requests to participate in an aggregate computing task distinct from each subscribing computer'"'"'s existing activities;

in response to the requests, the coordinating computer assigning subtasks of an aggregate computing task divisible into multiple independent subtasks, the assignment including distributing the subtasks among the subscribing computers and also sending an idle time activation program to each subscribing computer;

each subscribing computer receiving and installing the idle time activation program, whereupon the idle time activation program causes the subscribing computer to perform operations including working toward completion of the assigned subtask when the subscribing computer is in a predefined idle state with respect to the subscribing computer'"'"'s existing activities, and halting work toward completion of the assigned subtask when the subscribing computer is not in the predefined idle state; and

in response to each subscribing computer'"'"'s completion of its assigned subtask, transmitting results of the completed subtask to the coordinating computer; and

the coordinating computer assimilating the transmitted results.

42. The method of claim 41, the operations further comprising:

prior to the submittal of requests to participate, encouraging computer operators to participate in the aggregate computing task by offering compensation therefor;

the operations further comprise providing compensation to managers of the subscribing computers in exchange for their computers'"'"' work toward completion of their respective assigned subtasks.