Detecting available computers to participate in computationally complex distributed processing problem

• US 6,192,388 B1
• Filed: 06/20/1996
• Issued: 02/20/2001
• Est. Priority Date: 06/20/1996
• Status: Expired due to Term

• Current Assignee: Avid Technology Incorporated
• Original Assignee: Avid Technology Incorporated
• Inventors: Cajolet, Claude
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US08/667,837
• Time in Patent Office: 1,706 Days
• Field of Search: 395/670, 395/261, 395/672, 395/673, 395/674, 395/701, 395/704, 709/100, 709/102, 709/103, 709/104, 709/105, 709/108
• US Class Current: 718/100
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

A complex computational task is processed by a plurality of computers coupled to a network. A plurality of different computers (64-74) are each assigned a different portion of a distributed processing task by a problem dispatcher (88). Each computer determines if a local operator has not used a keyboard (43) or a mouse (40) for a predefined period of time. If not, a screen saving program is initiated and the computer begins monitoring the network to determine if a request for participation in a distributed processing task has been transmitted. Upon receiving such a request, the screen saver program responds, indicating that the computer is available to participate in the task. Each computer also sends characteristics to the problem dispatcher, which selects assistant computers to participate in the task. The problem dispatcher assigns specific portions of the task to each of the assistant computers until the task is completed. If a local operator interrupts, the portion of the task being processed by that computer is assigned to a different assistant computer. In this manner, the complex computational task is processed relatively quickly using only those computers that are available and have the appropriate capabilities.

Claims

1. A process for executing a complex computational task on a network having a plurality of independent interconnected workstations, each workstation including a computer processing unit and a user input device, the process comprising the steps of:

(i) identifying available workstations connected to a dispatching work station having a complex computational task to perform;

(ii) requesting computational characteristics and a local user profile from the identified workstations;

(iii) selecting, in response to the respective computational characteristics and local user profiles, at least one of the identified workstations for assisting in execution of the task to achieve a predetermined minimal efficiency;

(iv) dividing the task, in accordance with the respective computational characteristics and local user profiles, into portions for execution on the at least one selected workstation and the dispatching workstation;

(v) distributing the portions among the at least one selected workstation and the dispatching workstation; and

(vi) executing the distributed portions at the irrespective at least one selected workstation and the dispatching workstation to complete the task.

2. A process according to claim 1, wherein the step of identifying available workstations includes determining workstations where a predefined time interval has elapsed since a local user input.

3. A process according to claim 2, wherein the step of identifying includes querying a screen saver application.

4. A process according to claim 1, wherein the computational characterstics include at least one of memory available for execution of the portion, and a type designation of the identified workstation.

5. A process according to claim 1, wherein the local user profile includes an average user idle time.

6. A process according to claim 1, wherein the step of selecting includes choosing the identified workstations to optimize execution of the task.

7. A process according to claim 1, wherein the step of distributing includes determining an optimized distribution of the portions among a plurality of selected workstations in accordance with their respective computational characteristics and local user profiles.

8. A process according to claim 1, further including the steps of:

(vii) detecting a local user input at the at least one selected workstation; and

(viii) interrupting execution of the portion executing at the at least one selected workstation in response to the local user input.

9. A process according to claim 8, further including the step of:

(ix) redistributing the interrupted portion for execution at an unselected available workstation.

10. A method for rendering a graphics project over a network having a directing workstation preparing the graphics project, and a plurality of assistant workstations connected to the directing workstation through the network, each of the directing and assistant workstations including a computer processing unit and a user input device, the method comprising the steps of:

(i) querying the assistant workstations to determine available assistant workstations;

(ii) providing to the directing workstation computational characteristics and a local user profile for each of the available assistant workstations;

(iii) selecting a plurality of the available assistant workstations, according to their respective computational characteristics and local user profiles, to maximize efficiency of a graphics rendering task;

(iv) apportioning the rendering task among the selected assistant workstations and the directing workstation according to their respective computational characteristics and local user profiles;

(v) rendering the apportioned rendering task at the selected assistant workstations and directing workstation; and

(vi) assembling the rendered task at the directing workstation to provide a rendered digital graphics project.

11. A method according to claim 10, wherein the step of querying includes determining assistant workstations where a predefined time interval has elapsed since a local user input.

12. A method according to claim 11, wherein the step of querying includes querying a screen saver application.

13. A method according to claim 10, wherein the computational characteristics include at least one of memory available for execution of the portion, and a type designation of the available assistant workstation.

14. A method according to claim 10, wherein the local user profile includes an average user idle time.

15. A method according to claim 10, wherein the step of selecting includes selecting available assistant workstations to optimize execution of the rendering task.

16. A method according to claim 10, wherein the step of apportioning includes optimizing execution of the rendering task in accordance with the computational characteristics and local user profiles of the selected assistant workstations.

17. A method according to claim 10, further including the steps of:

(a) detecting a local user input at one of the selected assistant workstations;

(b) interrupting execution of the portion of the rendering task apportioned to the detected assistant workstation; and

(c) assigning the interrupted portion for execution at an unselected available assistant workstation.

18. A system for processing a complex computational task among a plurality of independent workstations interconnected over a network, each workstation including a computer processing unit and a user input device, comprising:

a dispatcher for transmitting a request to workstations connected to a dispatching workstation having a complex computational task to perform;

an inactivity detector at each said workstations for receiving the request and providing an availability response if a local user idle time exceeds a predefined time;

selection means at the dispatcher for requesting processing characteristics and a local user profile from available workstations, and for selecting, in response to the respective computational characteristics and local user profiles, at least one of the available workstations for assisting in execution of the task with at least a predetermined minimal efficiency; and

apportioning means at the dispatcher for dividing the task into portions for execution on the at least one selected workstation and the dispatching workstation, and for distributing the portions among the at least one selected workstation and the dispatching workstation.

19. A system according to claim 18, wherein the inactivity detector includes a screen saver application.

20. A system according to claim 18, wherein the computational characteristics include at least one of memory available for execution of the portion, and a type designation of the available assistant workstation.

21. A system according to claim 18, wherein the local user profile includes an average user idle time.

22. A system according to claim 18, further including a user input detector for detecting a user input at the at least one selected workstation.

23. A system according to claim 22, further including a interrupter for interrupting execution of the portion when a user input is detected.

24. A system according to claim 23, wherein the apportioning means assigns the interrupted portion to an unselected available workstation.

25. A system according to claim 18, wherein the complex computational task is a graphics rendering task.

26. A graphics rendering system, comprising:

a directing workstation having a graphics rendering task to perform;

a plurality of assistant workstations connected to the directing workstation through a network, each of the directing and assistant workstations including a computer processing unit and a user input device;

a dispatcher at the directing workstation for transmitting an assistance request to the assistant workstations;

an inactivity detector at each said assistant workstations for receiving the request and providing an availability response if a local user idle time exceeds a predefined interval;

selection means at the dispatcher for requesting processing characteristics and a local user profile from available assistant workstations, and for selecting, in response to the respective computational characteristics and local user profiles, at least one of the available workstations for assisting in execution of the rendering task with at least a predetermined minimal efficiency;

apportioning means at the dispatcher for dividing the task into portions for execution on the at least one selected workstation and the dispatching workstation, and for distributing the portions among the at least one selected workstation and the dispatching workstation; and

assembling means for assembling the executed portions to form rendered graphics project.

27. A rendering system according to claim 26, wherein the inactivity detector includes a screen saver application.

28. A rendering system according to claim 26, wherein the computational characteristics include at least one of memory available for execution of the portion, and a type designation of the available assistant workstation.

29. A rendering system according to claim 26, wherein the local user profile includes an average user idle time.

30. A rendering system according to claim 26, further including a user input detector for detecting a user input at the at least one selected workstation.

31. A rendering system according to claim 30, further including a interrupter for interrupting execution of the portion when a user input is detected.

32. A rendering system according to claim 31, wherein the apportioning means assigns the interrupted portion to an unselected available workstation.