Fault tolerant hypercube computer system architecture

• US 4,868,818 A
• Filed: 10/29/1987
• Issued: 09/19/1989
• Est. Priority Date: 10/29/1987
• Status: Expired due to Fees

• Current Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Madan, Herb. S., Chow, Edward
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Baker, Stephen M.
• Application Number:
  US07/113,956
• Time in Patent Office: 691 Days
• Field of Search: 371/11, 371/15, 371/16, 371/18, 371/22, 371/9, 371/62, 364/200 MS File, 364/900 MS File
• US Class Current: 714/4.1
• CPC Class Codes: G06F 11/0724 in a multiprocessor or a multi-core unit multiprocessors per se G06F15/80
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/2038 with a single idle spare processing component
• CPC Class Codes: G06F 11/2736 using a dedicated service processor for test
• CPC Class Codes: G11C 29/006 at wafer scale level, i.e. wafer scale integration [WSI]

Abstract

A fault-tolerant multi-processor computer system of the hypercube type comprising a hierarchy of computers of like kind which can be functionally substituted for one another as necessary. Communication between the working nodes is via one communications network while communications between the working nodes and watch dog nodes and load balancing nodes higher in the structure is via another communications network separate from the first. A typical branch of the hierarchy reporting to a master node or host computer (50) comprises, a plurality of first computing nodes (22); a first network of message conducting paths (30) for interconnecting the first computing nodes (22) as a hypercube (28'"'"'), the first network (30) providing a path for message transfer between the first computing nodes (22); a first watch dog node (40); and, a second network of message conducting paths (34) for connecting the first computing nodes (22) to the first watch dog node (40) independent from the first network (30), the second network (34) providing an independent path for test message and reconfiguration affecting transfers between the first computing nodes (22) and the first switch watch dog node (40). There is additionally, a plurality of second computing nodes (22); a third network of message conducting paths (30) for interconnecting the second computing nodes (22) as a hypercube (28'"'"'), the third network (30) providing a path for message transfer between the second computing nodes (22); a fourth network of message conducting paths (34) for connecting the second computing nodes (22) to the first watch dog node (40) independent from the third network (30) the fourth network (34) providing an independent path for test message and reconfiguration affecting transfers between the second computing nodes (22) and the first watch dog node (40); and, a first multiplexer disposed between the first watch dog node (40) and the second and fourth networks (34) for allowing the first watch dog node (40) to selectively communicate with individual ones of the computing nodes (22) through the second and fourth networks (34); as well as, a second watch dog node (40) operably connected to the first multiplexer whereby the second watch dog node (40) can selectively communicate with individual ones of the computing nodes (22) through the second and fourth networks (34). The branch is completed by a first load balancing node (

ORIGIN OF THE INVENTION

The invention described herein was made in the performance of work under a NASA contract and is subject to the provisions of Public Law 96-517 (35 USC 202) in which the Contractor has elected not to retain title.

Claims

1. A fault-tolerant multi-processor computer system of the hypercube type comprising:

(a) a plurality of first computing nodes;

(b) a first network of message conducting path means for interconnecting said first computing nodes as a hypercube, said first network providing a path for message transfer between said first computing nodes;

(c) a first watch dog node; and

,

(d) a second network of message conducting path means for directly connecting each of said first computing nodes to said first watch dog node independent from said first network, said second network providing an independent path for test message and reconfiguration affecting transfers between respective ones of said first computing nodes and said first watch dog node.

2. The fault-tolerant multi-processor computer system of claim 1 and additionally comprising:

(a) a plurality of second computing nodes;

(b) a third network of message conducting path means for interconnecting said second computing nodes as a hypercube, said third network providing a path for message transfer between said second computing nodes;

(c) a fourth network of message conducing path means for directly connecting each of said second computing nodes to said first watch dog node independent from said third network, said fourth network providing an independent path for test message and reconfiguration affecting transfers between respective ones of said second computing nodes and said first watch dog node; and

,

(d) first multiplexer means disposed between said first watch dog node and said second and fourth networks for allowing said first watch dog node to selectively communicate directly with individual ones of said computing nodes through said second and fourth networks.

3. The fault-tolerant multi-processor computer system of claim 2 and additionally comprising:

a second watch dog node operably connected to said first multiplexer means whereby said second watch dog node can selectively communicate directly with individual ones of said competing nodes through said second and fourth networks.

4. The fault-tolerant, multi-processor computer system of claim 3 and additionally comprising:

(a) a first load balancing node; and

(b) second multiplexer means connected between said first load balancing node and said first and second watch dog nodes for allowing said first load balancing node to selectively communicate directly with individual ones of said first and second watch dog nodes.

5. The fault-tolerant multi-processor computer system of claim 4 and additionally comprising:

thirteenth logic means in said first load balancing node for causing said first load balancing node to perform the tasks assigned to said first and second watch dog nodes when they are disabled using the messages in said first data storage means as necessary.

6. The fault-tolerant multi-processor computer system of claim 4 and additionally comprising:

fourteenth logic means in said first load balancing node for evaluating the task loading of said first and second watch dog nodes and their associated said computing nodes and for reassigning tasks from one of said watch dog nodes which is overburdened to the other of said watch dog nodes which is less burdened.

7. The fault-tolerant multi-processor computer system of claim 4 and additionally comprising:

(a) a plurality of third computing nodes;

(b) a fifth network of message conducting path means for interconnecting said third computing nodes as a hypercube, said fifth network providing a path for message transfer between said third computing nodes;

(c) a third watch dog node;

(d) a sixth network of message conducting path means for directly connecting each of said third computing nodes to said third watch dog node independent from said fifth network, said sixth network providing an independent path for test message and reconfiguration affecting transfers between respective ones of said third computing nodes and said third watch dog node;

(e) a plurality of fourth computing nodes;

(f) a seventh network of message conducting path means for interconnecting said fourth computing nodes as a hypercube, said seventh network providing a path for message transfer between said fourth computing nodes;

(g) an eighth network of message conducting path means for directly connecting each of said fourth computing nodes to said third watch dog node independent from said seventh network, said eighth network providing an independent path for test message and reconfiguration affecting transfers between respective ones of said fourth computing nodes and said third watch dog node;

(h) third multiplexer means disposed between said third watch dog node and said sixth and eighth networks for allowing said third watch dog node to selectively communicate directly with individual ones of said third and fourth computing nodes through said sixth and eighth networks;

(i) a fourth watch dog node operably connected to said third multiplexer means whereby said fourth watch dog node can selectively communicate directly with individual ones of said third and fourth computing nodes through said sixth and eighth networks;

(j) a second load balancing node; and

,

(k) fourth multiplexer means connected between said second load balancing node and said third and fourth watch dog nodes for allowing said second load balancing node to selectively communicate directly with individual ones of said third and fourth watch dog nodes.

8. The fault-tolerant multi-processor computer system of claim 1 and additionally comprising:

a first logic means in each of said first computing nodes for sending a copy of each message sent from one of said first computing nodes to another of said first computing nodes over said first network of message conducting path means to said first watch dog node over said second network of message conducting path means.

9. The fault-tolerant multi-processor computer system of claim 8 and additionally comprising:

second logic means in each of said first computing nodes for sending a copy of each acknowledgement of message handling competition sent from one of said first computing nodes to another of said first computing nodes over said first network of message conducting path means to said first watch dog node over said second network of message conducting path means.

10. The fault-tolerant multi-processor computer system of claim 9 and additionally comprising:

first data storage means in each of said first watch dog nodes for saving said copy of each message received from one of said first computing nodes until the associated said copy of acknowledgement of message handling completion is received.

11. The fault-tolerant multi-processor computer system of claim 10 and additionally comprising:

second data storage means in each said first watch dog node for listing the tasks assigned to each of said first computing nodes for execution.

12. The fault-tolerant multi-processor computer system of claim 11 and additionally comprising:

fourth logic means in said first watch dog node for evaluating the task loading of said first computing nodes and for reassigning tasks from ones of said first computing nodes which are task overburdened to others of said first computing nodes which are being under utilized.

13. The fault-tolerant multi-processor computer system of claim 11 and additionally comprising:

third logic means in said first watch dog node for causing said first watch dog node to perform the tasks assigned to a first computing node which is disabled using the messages in said first data storage means.

14. The fault-tolerant multi-processor computer system of claim 13 and additionally comprising:

eighth logic means in said first watch dog node for after initialization periodically and continuously sending test messages to each of said first computing nodes and for treating a said first computing node as disabled if it fails to respond to a said test message.

15. The fault-tolerant multi-processor computer system of claim 13 and additionally comprising:

(a) ninth logic means in each of said first computing nodes for after initialization periodically and continuously gathering and sending status reports on itself to said first watch dog node; and

(b) tenth logic means in said first watch dog node for treating a said first computing node as disabled if it fails to send a said status report.

16. The fault-tolerant multi-processor computer system of claim 13 and additionally comprising:

(a) eleventh logic means in each of said first computing nodes for informing said first watch dog node if it fails to complete a communication with another of said first computing nodes; and

,

(b) twelfth logic means in said watch dog node for sending an extra said test message to said another of said first computing nodes in response to said being informed to determine if said failure to complete a communication was due to said node'"'"'s being disabled.

17. A fault-tolerant multi-processor computer system of the hypercube type comprising:

(a) a plurality of first computing nodes;

(b) a plurality of second computing nodes;

(c) a plurality of third computing nodes;

(d) a plurality of fourth computing nodes;

(e) a first network of message conducting path means for interconnecting said first computing nodes as a hypercube, said first network providing a path for message transfer between said first computing nodes;

(f) a second network of message conducting path means for interconnecting said first computing nodes as a hypercube, said second network providing a path for message transfer between said second computing nodes;

(g) a third network of message conducting path means for interconnecting said third computing nodes as a hypercube, said third network providing a path for message transfer between said third computing nodes;

(h) a fourth network of message conducting path means for interconnecting said fourth computing nodes as a hypercube, said fourth network providing a path for message transfer between said fourth computing nodes;

(i) a first watch dog node;

(j) a second watch dog node;

(k) a third watch dog node;

(l) a fourth watch dog node;

(m) a fifth network of message conducting path means for directly connecting each of said first computing nodes to said first watch dog node independent from said first network, said fifth network providing an independent path for test message and reconfiguration affecting transfers between respective ones of said first computing nodes and said first watch dog node;

(n) a sixth network of message conducting path means for directly connecting each of said second computing nodes to said second watch dog node independent from said second network, said sixth network providing an independent path for test message and reconfiguration affecting transfers between respective ones of said second computing nodes and said second watch dog node;

(o) a seventh network of message conducting path means for directly connecting each of said third computing nodes to said third watch dog node independent from said third network, said seventh network providing an independent path for test message and reconfiguration affecting transfers between respective ones of said third computing nodes and said third watch dog node;

(p) an eighth network of message conducting path means for directly connecting each of said fourth computing nodes to said fourth watch dog node independent from said fourth network, said eighth network providing an independent path for test message and reconfiguration affecting transfers between respective ones of said fourth computing nodes and said fourth watch dog node;

(q) first multiplexer means disposed between said first and second watch dog nodes and said fifth and sixth networks for allowing said first and second watch dog nodes to selectively communicate directly with individual ones of said first and second computing nodes through said fifth and sixth networks;

(r) second multiplexer means disposed between third and fourth watch dog nodes and said seventh and eighth networks for allowing said third and fourth watch dog nodes to selectively communicate directly with individual ones of said third and fourth computing nodes through said seventh and eighth networks;

(s) a first load balancing node;

(t) a second load balancing node;

(u) third multiplexer means connected between said first load balancing node and said first and second watch dog nodes for allowing said first load balancing node to selectively communicate directly with individual ones of said first and second watch dog nodes;

(v) fourth multiplexer means connected between said second load balancing node and said third and fourth watch dog nodes for allowing said second load balancing node to selectively communicate directly with individual ones of said third and fourth watch dog nodes;

(w) a host computer; and

(x) a ninth network of message conducting path means connecting said host computer to said first and second load balancing nodes for providing an independent path for message transfer between said host computer, said first load balancing node and said second load balancing node.

18. The fault-tolerant multi-processor computer system of claim 17 and additionally comprising:

first logic means in each of said computing nodes for sending a copy of each message sent from one of said computing nodes to another of said computing nodes over said first, second, third and fourth networks of message conducting path means to said watch dog nodes over said fifth, sixth, seventh and eighth networks of message conducting path means.

19. The fault-tolerant multi-processor computer system of claim 18 and additionally comprising:

a second logic means in each of said computing nodes for sending a copy of each acknowledgement of message handling completion sent from one of said computing nodes to another of said computing nodes over said first, second, third and fourth networks of message conducting path means to said watch dog nodes over said fifth, sixth, seventh and eighth networks of message conducting path means.

20. The fault-tolerant multi-processor computer system of claim 19 and additionally comprising:

first data storage means in each of said watch dog nodes for saving said copy of each message received from one of said computing nodes until the associated said copy of acknowledgement of message handling completion is received.

21. The fault-tolerant multi-processor computer system of claim 17 and additionally comprising:

second data storage means in each of said watch dog nodes for listing tasks assigned to said computing nodes for execution.

22. The fault-tolerant multi-processor computer system of claim 21 and additionally comprising:

fourth logic means in said watch dog nodes for evaluating the task loading of said computing nodes and for reassigning tasks from ones of said computing nodes which are task overburdened to others of said computing nodes which are being under utilized.

23. The fault-tolerant multi-processor computer system of claim 21 and additionally comprising:

third logic means in said watch dog nodes for causing said watch dog node to perform the tasks assigned to a said computing node which is disabled using the messages in said first data storage means.

24. The fault-tolerant multi-processor computer system of claim 23 wherein:

said watch dog nodes include logic for after initialization periodically and continuously sending test messages to each of said computing nodes and for treating a said computing node as disabled if it fails to respond to a said test message.

25. The fault-tolerant multi-processor computer system of claim 23 wherein:

(a) each said computing node includes logic for after initialization periodically and continuously gathering an sending status reports on itself to a said watch dog node to which it is assigned; and

,

(b) said watch dog nodes include logic for treating an assigned said first computing node as disabled if it fails to send a said status report.

26. The fault-tolerant multi-processor computer system of claim 23 wherein:

(a) each said computing node includes logic for informing a said watch dog node if it fails to complete a communication with another of said computing nodes; and

,

(b) said watch dog nodes include logic for sending an extra said test message to said another of said computing nodes to determine if said failure to complete a communication was due to said node'"'"'s being disabled.

27. The fault-tolerant multi-processor computer system of claim 23 and additionally comprising:

fifth logic means in said load balancing nodes for causing said load balancing nodes to perform the tasks assigned to a said watch dog node when it is disabled using the messages in said first data storage means as necessary.

28. The fault-tolerant multi-processor computer system of claim 27 wherein:

said load balancing nodes include logic for after initialization periodically and continuously sending test messages to each of said watch dog nodes and for treating a said watch dog node as disabled if it fails to respond to a said test message.

29. The fault-tolerant multi-processor computer system of claim 27 wherein:

(a) each said watch dog node includes logic for after initialization periodically and continuously gathering and sending status reports on itself to a said load balancing node to which it is assigned; and

,

(b) said load balancing nodes include logic for treating an assigned said watch dog node as disabled if it fails to send a said status report.

30. In a fault-tolerant multi-processor computer system of the hypercube type comprising a plurality of computing nodes and a watch dog node, the improved method of operation comprising the steps of:

(a) connecting a first network of message conducting paths to interconnect the computing nodes as a hypercube and provide a path for message transfer between said computing nodes;

(b) connecting a second network of message conducting paths to directly connect each of the computing nodes to the watch dog node to provide an independent path for test message and reconfiguration affecting transfers between respective ones of the computing nodes and the watch dog node;

(c) employing the first network for all message transfers between the computing nodes; and

,

(d) employing the second network for all test message and reconfiguration affecting transfers between respective ones of the computing nodes and the watch dog node.

31. The method of claim 30 wherein the fault-tolerant multi-processor computer system of the hypercube type additionally comprises a plurality of second computing nodes and additionally comprising the steps of:

(a) connecting a third network of message conducting paths to interconnect the second computing nodes as a hypercube to provide a path for message transfer between said second computing nodes;

(b) connecting a fourth network of message conducting paths to directly connect each of the second computing nodes to the watch dog node independent from the third network to provide an independent path for test message and reconfiguration affecting transfers between respective ones of the second computing nodes and the second watch dog node; and

,

(c) employing the third network for all message transfers between the second computing nodes;

(d) employing the fourth network for all test message and reconfiguration affecting transfers between respective ones of the second computing nodes and the second watch dog node; and

,

(e) disposing first multiplexer means between the first watch dog node and the second and fourth networks to allow the first watch dog node to selectively communicate directly with individual ones of said computing nodes through said second and fourth networks.

32. The method of claim 31 and additionally comprising:

operably connecting a second watch dog node to the first multiplexer means whereby the second watch dog node can selectively communicate directly with individual ones of the computing nodes through the second and fourth networks.

33. The method of claim 32 wherein the fault-tolerant multi-processor computer system of the hypercube type additionally comprises a first load balancing node, and additionally comprising the step of:

connecting second multiplexer means between the first load balancing node and the first and second watch dog nodes to allow the first load balancing node to selectively communicate directly with individual ones of the first and second watch dog nodes.

34. The method of claim 33 and additionally comprising the step of:

sending a copy of each message sent from one of the computing nodes to another of the computing nodes over the first and third network of message conducting paths to the watch dog nodes over the second and fourth networks of message conducting paths.

35. The method of claim 34 and additionally comprising the step of:

sending a copy of each acknowledgment of message handling completion sent from one computing node to another over the first and third networks of message conducting paths to the watch dog nodes over the second and fourth networks of message conducting paths.

36. The method of claim 35 and additionally comprising the step of:

saving the copy of each message received from one of the computing nodes until the associated copy of acknowledgment of message handling completion is received.

37. The method of claim 36 and additionally comprising the step of:

maintaining in each watch dog node a list of the tasks assigned for execution to each of the computing nodes assigned to it.

38. The method of claim 37 and additionally comprising the step of:

after initialization having the watch dog nodes periodically and continuously evaluate the task loading of the computing nodes and reassign tasks from ones of computing nodes which are task overburdened to others of computing nodes which are being under utilized.

39. The method of claim 37 and additionally comprising the step of:

causing the watch dog nodes to perform the tasks assigned to a computing node which is disabled using the messages saved by the watch dog node.

40. The method of claim 39 and additionally including the steps of:

(a) after initialization having the watch dog nodes periodically and continuously send test messages to computing nodes assigned to them; and

,

(b) having the watch dog nodes treat a computing node as disabled if it fails to respond to a test message.

41. The method of claim 39 and additionally including the steps of:

(a) after initialization having each first computing node periodically and continuously gather and send status reports on itself to the first watch dog node; and

,

(b) having the first watch dog node treat a first computing node as disabled if it fails to send a status report.

42. The method of claim 39 and additionally including the steps of:

(a) having each first computing node inform a watch dog node if it fails to complete a communication with another of the first computing nodes; and

,

(b) having the watch dog nodes send an extra test message to a non-completing computing nodes to determine if the failure to complete a communication was due to the node'"'"'s being disabled.