Method and apparatus for node pruning a multi-processor system for maximal, full connection during recovery

• US 6,002,851 A
• Filed: 01/28/1997
• Issued: 12/14/1999
• Est. Priority Date: 01/28/1997
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Tandem Computers Incorporated (HP Inc.)
• Inventors: Basavaiah, Murali, Krishnakumar, Karoor S.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): WRIGHT, NORMAN M
• Application Number:
  US08/790,030
• Time in Patent Office: 1,050 Days
• Field of Search: 395/182.02, 395/182.09, 395/185.1, 395/200.51, 395/800.15, 395/182.1
• US Class Current: 714/4.5
• 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/1425 by reconfiguration of node membership

Abstract

A method and apparatus for achieving maximal, full connection in a multi-processor system having a plurality of processors. Each of the multiple processors has a respective memory. The invention includes communicatively connecting the processors. Following a disruption in the communicative connection, the invention collects connectivity information on one of the processors and selects certain of the processors to cease operations, based on the connectivity information collected. The invention further communicates the selection to each of the processors communicatively coupled to the one processor. The selected processors cease operations.

Claims

1. In a multi-processor system having a plurality of processors each having a respective memory, a method for achieving maximal, full connection, said method comprising:

communicatively connecting said plurality of processors;

collecting connectivity information on a first of said plurality of processors following a disruption in said communicative connection;

ceasing to collect connectivity information on said first of said plurality of processors; and

selecting on said first of said plurality of processors certain of said plurality of processors to cease operations, based on said connectivity information collected.

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

communicating said selection to each of said plurality of processors communicatively coupled to said first of said plurality of processors.

3. The method of claim 2 further comprising the step of:

communicating said selection from each of said plurality of processors communicatively coupled to said first processor.

4. The method of claim 1 further comprising the step of:

ceasing operations on said certain processors.

5. The method of claim 1 wherein said step of collecting comprises

collecting connectivity information on each of said plurality of processors.

6. The method of claim 1 wherein said step of ceasing to collect comprises

ceasing to collect connectivity information on said first of said plurality of processors when said connectivity information indicates that said plurality of processors is fully connected.

7. The method of claim 1 wherein said step of ceasing to collect comprises

ceasing to collect connectivity information on said first of said plurality of processors when a predetermined amount of time has elapsed.

8. The method of claim 1 wherein said step of selecting comprises

selecting said first of said plurality of processors as one of said certain processors to cease operations.

9. The method of claim 8 further comprising the step of

selecting another of said plurality of processors to next function as said first of said plurality of processors.

10. The method of claim 1 wherein said step of selecting comprises

representing said multi-processor system as a graph;

then listing all maximal, fully connected subgraphs;

and

then selecting one of said maximal, fully connected subgraphs.

11. The method of claim 10 wherein said step of listing comprises

listing all disconnects in said graph, based on said connectivity information collected;

initializing a solution set to include said graph, fully connected and with all vertices;

successively applying each of said listed disconnects to each member of said solution set.

12. The method of claim 11 wherein said step of collecting comprises

collecting connectivity information in an N×

N matrix, where N is the number of said plurality of processors; and

said steps of initializing and successively applying comprise

computing a set including all dead processors among said plurality of processors;

converting said matrix into canonical form.

13. The method of claim 10 wherein said step of selecting comprises

selecting the one of said maximal, fully connected subgraphs with the greatest number of vertices.

14. The method of claim 10 wherein said step of selecting comprises

selecting the largest of said maximal, fully connected subgraphs that also contains a predetermined, preferred processor.

15. The method of claim 10 wherein said step of selecting comprises

selecting one of said maximal, fully connected subgraphs based on a predetermined survival priority.

16. The method of claim 1 wherein said step of selecting comprises

representing said multi-processor system as a graph;

counting a count of disconnects in said graph;

determining said count of disconnects as more than a predetermined number; and

then selecting a fully connected subgraph on a criterion other than maximum connectivity.

17. The method of claim 16 wherein said step of determining comprises

determining said count of disconnects as more than 8.

18. The method of claim 1 wherein said step of collecting comprises

collecting connectivity information in an N×

N matrix, where N is the number of said plurality of processors.

19. A computer system comprising:

a communications network;

a plurality of processors, communicatively connected by means of said communications network;

each of said plurality of processors having a respective memory wherein is located a computer program for causing said computer system to achieve maximal, full connection by

collecting connectivity information on a first of said plurality of processors following a disruption in said communicative connection;

ceasing to collect connectivity information on said first of said plurality of processors; and

selecting on said first of said plurality of processors certain of said plurality of processors to cease operations, based on said connectivity information collected.

20. The method of claim 19 further comprising the step of:

communicating said selection to each of said plurality of processors communicatively coupled to said first of said plurality of processors.

21. The method of claim 20 further comprising the step of:

communicating said selection from each of said plurality of processors communicatively coupled to said first of said plurality of processors.

22. The method of claim 19 wherein said step of collecting comprises

collecting connectivity information on each of said plurality of processors.

23. An article of manufacture comprising a medium for data storage wherein is located a computer program for causing a multiprocessor system having a plurality of processors to achieve maximal, full connection by

communicatively connecting said plurality of processors;

collecting connectivity information on a first of said plurality of processors following a disruption in said communicative connection;

ceasing to collect connectivity information on said first plurality of processors; and

selecting on said first of said plurality of processors certain of said plurality of processors to cease operations, based on said connectivity information collected.

24. An article of manufacture comprising a medium for data storage wherein is located a computer program for causing a multiprocessor system having a plurality of processors, including a first processor, to achieve maximal, full connection by

communicatively connecting said plurality of processors;

collecting connectivity information on each of said plurality of processors following a disruption in said communicative connection;

ceasing to collect connectivity information on said first processors; and

selecting on said first processor certain of said plurality of processors to cease operations, based on said connectivity information collected.

25. The method of claim 24 further comprising the step of:

communicating said selection to each of said plurality of processors communicatively coupled to said first processor.

26. The method of claim 25 further comprising the step of:

communicating said selection from each of said plurality of processors communicatively coupled to said first processor.

27. The method of claim 24 wherein said step of selecting comprises

selecting said first processor as one of said certain processors to cease operations.

28. The method of claim 27 further comprising the step of

selecting another of said plurality of processors to next function as said first processor.