Computer system

• US 5,025,369 A
• Filed: 08/25/1988
• Issued: 06/18/1991
• Est. Priority Date: 08/25/1988
• Status: Expired due to Fees

• Current Assignee: RWE-DEA Aktiengesellschaft für Mineraloel und Chemie
• Original Assignee: David Schwartz Enterprises Incorporated
• Inventors: Schwartz, David J.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US07/236,493
• Time in Patent Office: 1,027 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A multilevel distributed computer system for distributed processing preferably includes a plurality of personal computers. A task inputted to the system is divided into a plurality of portions. As many of the portions as possible are distributed for processing on the lowest level of the system. Those portions unprocessed on the lowest level are distributed for processing on the next lowest level. Remaining unprocessed portions of the task are distributed to available computers on successively higher levels of the system until all of the task have been distributed for processing.

Claims

1. A multilevel computer system including high level computing means and low level computing means, comprising:

said high level computer means including at least one computer and operable for receiving a task, for distributing one or more portions of the task to said low level computer means for processing based on the availability, as determined by said high level computer means, of the low level computer means to process said one or more portions of the task, and for processing, if currently available, all undistributed portions of the task;

said low level computer means including at least two computers and operable for receiving an additional task, for processing, if currently available, portions of the additional task, for distributing for processing those portions of the unprocessed additional task to high level computer means based on the availability, as determined by said low level computer means, of the high level computer means to process one or more portions of the unprocessed additional task, and for processing portions of the task received from said high level computer means; and

communications link means for transferring portions of the task within the computer system, said communications link means including first link means and second link means, said first link means coupling said at least one computer of said high level computer means to said at least two computers of said low level computer means, each of said second link means coupling said at least two computers of said low level computer means together;

wherein the availability of said low level computer means is communicated to said high level computer means and the availability of said high level computer means is communicated to said low level computer means along said first link means; and

wherein the number of first and second link means associated with at least one of the at least two computers of said low level computer means are unequal.

2. The computer system of claim 1, wherein the number of first link means and the number of second link means associated with each computer of said low level computer means are unequal.

3. The computer system of claim 1, wherein said first link means are operable for transferring portions of the task and additional task bidirectionally.

4. The computer system of claim 3, wherein said second link means are operable for transferring portions of the task and additional task unidirectionally.

5. The computer system of claim 3, wherein said second link means are operable for transferring portions of the task and additional task bidirectionally.

6. The computer system of claim 1, wherein said high level computer means and said low level computer means are operable for processing different portions of the task at the same time.

7. The computer system of claim 6, wherein said high level computer means and said low level computer means are operable for processing different portions of the additional task at the same time.

8. The computer system of claim 1, further including a lower level computer means operable for receiving a further additional task, for processing, if currently available, portions of the further additional task and for distributing for processing those portions of the further additional task unprocessed by the lower level computer means to low level computer means based on the availability, as determined by said lower level computer means, of said low level computer means to process one or more portions of the unprocessed further additional task and for distributing for processing through said communications link means any remaining portions of the further additional task unprocessed by said low level computer means to said high level computer means based on the availability, as determined by said low level computer means, of said high level computer means to process one or more portions of the further additional task unprocessed by said low level computer means.

9. The computer system of claim 8, wherein said lower level computer means includes at least three computers and wherein said communications link means includes third link means and fourth link means, said third link means coupling said at least two computers of said low level computer means to said at least three computers of said lower level computer means, said fourth link means coupling said at least three computers of said lower level computer means together wherein the number of third link means and the number of fourth link means coupled to one of the computers on the lower level computer means are unequal.

10. The computer system of claim 9, wherein the number of third link means and the number of fourth link means associated with each computer of said lower level computer means are unequal.

11. The computer system of claim 8, wherein said high level means, low level means and lower level means are operable for processing different portions of the task at the same time.

12. The computer system of claim 8, wherein said high level computer means, low level computer means and lower level computer means are operable for processing different portions of the additional task at the same time.

13. The computer system of claim 8, wherein said high level computer means, low level computer means and lower level computer means are operable for processing different portions of the further additional task at the same time.

14. The computer system of claim 9, wherein the third link means are operable for transferring portions of the task, additional task and further additional task bidirectionally.

15. The computer system of claim 14, wherein the fourth link means are operable for transferring portions of the task, additional task and further additional task unidirectionally.

16. The computer system of claim 14, wherein the fourth link means are operable for transferring portions of the task, additional task and further additional task bidirectionally.

17. The computer system of claim 9, wherein each computer within the computer system is substantially similar in construction.

18. The computer system of claim 9, wherein each computer within the computer system is a personal type computer.

19. The computer system of claim 9, wherein each computer within the lower level computer means is coupled to at least one other computer within the lower level computer means through two fourth link means whereby the lower level computer means forms a ring of computers.

20. The computer system of claim 19, wherein each computer within the low level computer means is coupled to at least one other computer within the low level computer means through two second link means whereby the low level computer means forms a ring of computers.

21. The computer system of claim 20, wherein each computer means within the low level computer means is coupled to at least one other computer within the low level computer means through two second link means whereby the low level computer means forms a ring of computer means.

22. The computer system of claim 9, wherein the number of third link means is greater than the number of fourth link means.

23. The computer system of claim 1, wherein each computer within the computer system is substantially similar in construction.

24. The computer system of claim 23, wherein each computer within the computer system is a personal type computer.

25. The computer system of claim 1, wherein each computer within the low level computer means is coupled to at least one other computer within the low level computer means through two second link means whereby the low level computer means forms a ring of computers.

26. The computer system of claim 1, wherein the number of first link means is greater than the number of second link means.

27. A multilevel computer system including high level computer means and low level computer means, comprising:

said high level computer means including at least one computer and operable for receiving a task, for distributing one or more portions of the task to said low level computer means for processing based on the availability, as determined by said high level computer means, of the low level computer means to process one or more portions of the task and for processing, if currently available, all undistributed portions of the task;

said low level computer means including at least two computers and operable for receiving an additional task, for processing, if currently available, portions of the additional task, for distributing for processing those portions of the unprocessed additional task to high level computer means based on the availability, as determined by said low level computer means, of said high level computer means to process one or more portions of the unprocessed additional task and for processing portions of the task received from said high level computer means; and

communications link means for transferring portions of the task within the computer system, said communications link means including first link means and second link means, said first link means coupling said at least one computer of said high level computer means to said at least two computers of said low level computer means and operable for transferring portions of the task and additional task bidirectionally, each of said second link means coupling said at least two computers of said low level computer means together;

wherein the availability of said low level computer means to process one or more portions of the task is communicated to said high level computer means and the availability of said high level computer means to process one or more portions of the unprocessed additional task is communicated to said low level computer means along said first link means; and

wherein the number of first link means and the number of second link means associated with each computer of said low level computer means are unequal and wherein said high level computer means and said low level computer means are operable for processing different portions of the task at the same time and for processing different portions of the additional task at the same time and wherein each computer within the low level computer means is coupled to at least one other computer within the low level computer means through two second link means whereby the low level computer means forms a ring of computers.

28. A method of distributed processing within a network of computers, comprising:

arranging the network as a multilevel system including at least one high level computer and at least two low level computers;

establishing a communications link which includes first link means and second link means wherein the low level computers are coupled together through the second link means and at least one high level computer is coupled to the at least two low level computers through the first link means and wherein the number of first and second links associated with each low level computer are unequal;

distributing one or more portions of a task to be processed by low level computers along the communications links based on the availability of the low level computers to process said one or more portions of the task, said availability being previously communicated to the at least one high level computer along the first link means;

processing the distributed portions of the task by the currently available low lever computers; and

processing all undistributed portions of the task by the at least one high level computer; and

processing portions of an additional task by at least one of the at least two low level computers which are currently available for processing, and distributing for processing along the communications link those portions of the additional task unprocessed by the low level computers to any currently available high level computer.

29. The method of claim 28, further including processing different portions of the task at the same time.

30. The method of claim 28, further including processing different portions of the additional task at the same time.

31. The method of claim 28, further including transferring portions of the task along the first link means bidirectionally.

32. The method of claim 28, further including transferring portions of the task along the second link means bidirectionally.

33. The method of claim 28, further including transferring portions of the task along the second link means unidirectionally.

34. The method of claim 28, wherein arrangement of the network includes providing that each computer within the system is of substantially the same construction.

35. The method of claim 28, wherein establishment of the communications link includes coupling each low level computer to at least one other low level computer through two second link means whereby the low level computers form a ring of computers.

36. A method of distributed processing within a network of computers, comprising:

arranging the network as a multilevel system including at least one high level computer and at least two low level computers;

establishing a communications link which includes first link means and second link means wherein the low level computers are coupled together through the second link means to form a ring of computers and the at least one high level computer is coupled to the at least two low level computers through the first link means and wherein the number of first and second links associated with each low level computer are unequal;

distributing portions of a task to be processed by currently available low level computers along the communications link based on the availability of the low level computers to process one or more portions of the task, said availability being previously communicated to the at least one high level computer along the first link means;

processing the distributed portions of the task by currently available low level computers;

processing, if currently available, all undistributed portions of the task by the at least one high level computer;

processing portions of an additional task by currently available low level computers;

distributing for processing along the communications link those portions of the additional task unprocessed by the low level computers to the at least one high level computer based on the availability of the at least one high level computer to process one or more portions of the unprocessed additional task, said availability of the at least one high level computer being previously communicated to at least one of the low level computers along the first link mean; and

processing the distributed portions of the additional task by one or more currently available high level computers;

wherein different portions of the task are processed at the same time and different portions of the additional task are processed at the same time and wherein portions of the task are transferred along the first link means bidirectionally.

37. A multilevel computer system including high level computing means and low level computing means, comprising:

communications link means for transferring portions of a task within the computer system, said communications link means including first link means and second link means;

said high level computer means including at least one computer means and operable for receiving the task, for distributing for processing portions of the task to said low level computer means based on the availability, as determined by said high level computer means, of said low level computer means to process one or more portions of the task, said availability being previously communicated to said high level computer means along said first link means of said communication link means and for processing, if currently available, all undistributed portions of the task;

said low level computer means including at least two computer means and operable for processing received portions of the task from the high level computer means, one of said at least two computer means operable for receiving an additional task and for processing, if currently available, portions of the additional task;

said high level computer means also operable for receiving from one of said at least two computer means of said low level computer means portions of the unprocessed additional task and for distributing, for processing those portions of the unprocessed additional task to the other of said at least two computer means for processing by the latter based on the availability of the other of said at least two computer means to process one or more portions of the unprocessed additional task, said availability of the other of said at least two computer means being previously communicated to said high level computer means from the other of said at least two computer means along said first link means and, if available, processing of those portions of the unprocessed additional task undistributed to said other of said at least two computer means;

said communications link means also for communicating to said high level computer means along said first link means from said low level computer means the current availability of said low level computer means to process one or more portions of the task and for communicating to said high level computer along said first link means from the other of said at least two computer means the current availability of the other of said at least two computer means to process one or more portions of the unprocessed additional task, said first link means coupling said at least one computer means of said high level computer means to said at least two computer means of said low level computer means, each of said second link means coupling said at least two computer means of said low level computer means together;

wherein the number of first link means and the number of second link means coupled to one of the at least two computer means of said low level computer means are unequal.

38. The computer system of claim 37, wherein the number of first link means and the number of second link means associated with each computer means of said low level computer means are unequal.

39. The computer system of claim 37, wherein said first link means are operable for transferring portions of the task and additional task bidirectionally.

40. The computer system of claim 39, wherein said second link means are operable for transferring portions of the task and additional task unidirectionally.

41. The computer system of claim 39, wherein said second link means are operable for transferring portions of the task and additional task bidirectionally.

42. The computer system of claim 37, wherein said high level computer means and said low level computer means are operable for processing different portions of the task at the same time.

43. The computer system of claim 42, wherein said high level computer means and said low level computer means are operable for processing different portions of the additional task at the same time.

44. The computer system of claim 43, further including lower level computer means which includes at least three computer means and operable for processing received portions of the task and additional task, one of said at least three computer means operable for receiving a further additional task and processing, if currently available, portions of the further additional task, and wherein one of said at least two computer means of said low level computer means is also operable for receiving from said one of said at least three computer means of said lower level computer means portions the unprocessed further additional task and for distributing for processing, if available, those portions of the unprocessed further additional task to the other two of said at least three computer means of said lower level computer means and, if available, processing those portions of the unprocessed further additional task undistributed to said other two of said at least three computer means.

45. The computer system of claim 44, wherein said high level computer means is further operable for receiving from said one of at least two computer means of said low level computer means portions of the undistributed unprocessed further additional task and for distributing for processing, if available, those portions of the undistributed unprocessed further additional task to the other of said at least two computer means and, if available, processing those portions of the undistributed unprocessed further additional task which are not distributed to said other of said at least two computer means.

46. The computer system of claim 44, wherein said communications link means includes third link means and fourth link means, said third link means coupling said at least two computer means of said low level computer means to said at least three computer means of said lower level computer means, said fourth link means coupling said at least three computer means of said lower level computer means together wherein the number of third link means and the number of fourth link means coupled to one of the computer means on the lower level computer means are unequal.

47. The computer system of claim 46, wherein the number of third link means and the number of fourth link means associated with each computer means of said lower level computer means are unequal.

48. The computer system of claim 46, wherein the third link means are operable for transferring portions of the task, additional task and further additional task bidirectionally.

49. The computer system of claim 48, wherein the fourth link means are operable for transferring portions of the task, additional task and further additional task unidirectionally.

50. The computer system of claim 48, wherein the fourth link means are operable for transferring portions of the task, additional task and further additional task bidirectionally.

51. The computer system of claim 46, wherein each computer means within the computer system is substantially similar in construction.

52. The computer system of claim 46, wherein each computer means within the computer system is a personal type computer.

53. The computer system of claim 46, wherein each computer means within the lower level computer means is coupled to at least one other computer means within the lower level computer means through two fourth link means whereby the lower level computer means forms a ring of computer means.

54. The computer system of claim 44, wherein said high level computer means, low level computer means and lower level computer means are operable for processing different portions of the task at the same time.

55. The computer system of claim 44, wherein said high level computer means, low level computer means and lower level computer means are operable for processing different portions of the additional task at the same time.

56. The computer system of claim 44, wherein said high level computer means, low level computer means and lower level computer means are operable for processing different portions of the further additional task at the same time.

57. The computer system of claim 46, wherein the number of third link means is greater than the number of fourth link means.

58. The computer system of claim 37, wherein each computer means within the computer system is substantially similar in construction.

59. The computer system of claim 58, wherein each computer means within the computer system is a personal type computer.

60. The computer system of claim 37, wherein each computer means within the low level computer means is coupled to at least one other computer means within the low level computer means through two second link means whereby the low level computer means forms a ring of computer means.

61. The computer system of claim 37, wherein the number of first link means is greater than the number of second link means.

62. A multilevel computer system including high level computer means and low level computer means, comprising:

communications link means for transferring the portions of a task within the computer system, said communications link means including first link means and second link means;

said high level computer means including at least one computer means and operable for receiving a task, for distributing portions of the task to said low level computer means for processing of said portions based on the availability of the low level computer means to process one or more portions of the task, said availability being previously communicated to said high level computer means from said low level computer means along first link means of communication link means and for processing, if currently available, all undistributed portions of the task;

said low level computer means including at least two computer means and operable for processing received portions of the task from the high level computer means, one of said at least two computer means operable for receiving an additional task and for processing, if currently available, portions of the additional task;

said high level computer means also operable for receiving from said one of said at least two computer means of said low level computer means portions of the unprocessed additional task and for distributing for processing those portions of the unprocessed additional task to the other of said at least two computer means based on the availability of the other said at least two computer means to process one or more portions of the unprocessed additional task, said availability of the other of said at least two computer means being previously communicated to said high level computer means from the other of said at least two computer means along said first link means, and, if available, processing those portions of the unprocessed additional task undistributed to said other of said at least two computer means;

said communications link means also for communicating to said high level computer means along said first link means from said low level computer means the current availability of said low level computer means to process one or more portions of the task and for communicating to said high level computer means along said first link means from the other of said at least two computer means the current availability of the other of said at least two computer means to process one or more portions of the unprocessed additional task, said first link means coupling said at least one computer means of said high level computer means to said at least two computer means of said low level computer means and operable for transferring the portions of the task and additional task bidirectionally, each of said second link means coupling said at least two computer means of said low level computer means together;

wherein the number of first link means and the number of second link means associated with each computer means of said low level computer means are unequal and wherein said high level computer means and said low level computer means are operable for processing different portions of the task at the same time and for processing different portions of the additional task at the same time and wherein each computer means within the low level computer means is coupled to at least one other computer means within the low level computer means through two second link means whereby the low level computer means forms a ring of computers.

63. A method of distributed processing within a network of computers, comprising:

arranging the network as a multilevel system including at least one high level computer and at least two low level computers;

establishing a communications link which includes first link means and second link means wherein the low level computers are coupled together through the second link means and at least one high level computer is coupled to the at least two low level computers through the first link means and wherein the number of first and second link means associated with each low level computer are unequal;

distributing along the first link means portions of the task to be processed by currently available low level computers based on the availability of the low level computers to process one or more portions of the task, said availability being previously communicated to said at least one high level computer from at least one of the at least two low level computers along said first link means;

processing the distributed portions of the task by the currently available low level computers;

processing, if currently available, all undistributed portions of the task by the at least one high level computer;

processing, if currently available, portions of an additional task by one of the at least two low level computers;

distributing along the first link means those portions of the additional task unprocessed by said one of the at least two low level computers to the at least one high level computer if the other of said at least two low level computers is currently available for processing of the additional task;

distributing along the first link means, if available, those portions of the additional task to the other of said at least two low level computers based on the availability of the other of said at least two low level computers to process one or more portions of the unprocessed additional task, said availability of the other of said at least two low level computers being previously communicated to said at least one high level computer from the other of said at least two low level computers along said first link means;

processing by the second of said at least two low level computers the received portions of the additional task; and

processing, if available, by the at least one high level computer the unprocessed portions undistributed to the second of the at least two low level computers.

64. The method of claim 63, further including processing different portions of the task at the same time.

65. The method of claim 63, further including processing different portions of the additional task at the same time.

66. The method of claim 63, further including transferring portions of the task along the first link means bidirectionally.

67. The method of claim 66, further including transferring portions of the task along the second link means bidirectionally.

68. The method of claim 66, further including transferring portions of the task along the second link means unidirectionally.

69. The method of claim 63, wherein arrangement of the network includes providing that each computer within the system is of similar construction.

70. The method of claim 63, wherein establishment of the communications link includes coupling each low level computer to at least one other low level computer through two second link means whereby the low level computers form a ring of computers.