US4807228A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of spare capacity use for fault detection in a multiprocessor system
Assignee: Nokia Bell Labs
•
Filing: 1987-03-18
•
Granted: 1989-02-21
•
Expires: 2007-03-18
Abstract
Abstract A method of detecting and identifying faulty processors in a multiprocessor system. A processing task is assigned when possible to two processors, a primary processor and a secondary processor if a second idle processor is available. In one embodiment, the operations of a secondary processor are preempted and that processor is reassigned as primary for another task if no idle processor is available when the task is initiated. In a second embodiment, the operations of a secondary processor are not preempted, and a new task is queued until an idle processor becomes available. If a secondary processor completes a task, its results are compared with the results of the primary processor. Disagreement messages are broadcast to a central controller in a nondistributed embodiment and to all the processors in the system in a distributed embodiment. The disagreement messages are periodically analyzed by the controller or by each processor. In the distributed embodiment, the analysis algorithm is such that each nonfaulty processor identifies the same subset of faulty processors.
Inventors
- 👤 Anton T. Dahbura
- 👤 William J. Hery
- 👤 Krishan K. Sabnani
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 22:24
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/16; G06F11/1629; G06F11/1654; G06F11/165; G06F11/22; G06F11/1641
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
150 words
A method of detecting faults in a multiprocessor system in which processing tasks are executed by plural ones of the processors and the results from each of the processors compared, CHARACTERTIZED BY the steps of ascertaining if one or more of the processors are idle response to an initiation of a computing task and, if so, assigning the task to a primary idle one of the processors if an idle processor is available, assigning the task to a secondary processor if a second idle processor is available, if a secondary processor is assigned, comparing the task results of the primary and secondary processors, setting an indication in a disagreement table that the primary and secondary processors disagree if the task results of the primary and secondary processors do not compare, and periodically analyzing indications in the disagreement table according to a predetermined algorithm to determine faulty ones of the processors.
Claim 2
Independent Claim
150 words
A method of detecting faults in a multiprocessor system in which processing tasks are executed by plural ones of the processors and the results from each of the processors compared, CHARACTERTIZED BY the steps of ascertaining if one or more of the processors are idle response to an initiation of a computing task and, if so, assigning the task to a primary idle one of the processors if an idle processor is available, assigning the task to a secondary processor if a second idle processor is available, if a secondary processor is assigned, comparing the task results of the primary and secondary processors, setting an indication in a disagreement table that the primary and secondary processors disagree if the task results of the primary and secondary processors do not compare, and periodically analyzing indications in the disagreement table according to a predetermined algorithm to determine faulty ones of the processors.
Claim 3
Dependent Claim
58 words
The method of claim 1 further CHARACTERIZED BY the step of determining if any processor is assigned as a secondary processor for any other task if no processor is idle at the ascertaining step and, if so, preempting the processing operations of a secondary processor and assigning the preempted processor as a primary processor for the instant task.
Claim 4
Dependent Claim
20 words
The method of claim 1 wherein the system further comprises a central controller for performing the steps of the method.
Claim 5
Dependent Claim
20 words
The method of claim 1 wherein the steps of result comparing and periodic analyzing are performed by the individual processors.
Claim 6
Dependent Claim
26 words
The method of claim 3 further CHARACTERIZED IN THAT each processor transmits a result message to the central controller when the processor has completed a task.
Claim 7
Dependent Claim
54 words
The method of claim 5 further CHARACTERIZED IN THAT, in response to receipt of a first result message from a processor, the central controller ascertains if a second processor is assigned to perform the task associated with the first result message and, if so, waits to receive a result message from the second processor.
Claim 8
Dependent Claim
62 words
The method of claim 6 further CHARACTERIZED IN THAT the controller compares the first and second result messages and, in the event the messages do not compare, sets a first indication in the disagreement table that the first processor disagrees with the second processor, and sets a second indication in the disagreement table that the second processor disagrees with the first processor.
Claim 9
Dependent Claim
26 words
The method of claim 7 further CHARACTERIZED IN THAT the central controller reinitiates task processing operations if the first and second result messages do not compare.
Claim 10
Dependent Claim
33 words
The method of claim 7 wherein the step of periodically analyzing the disagreement table is further CHARACTERIZED BY marking as faulty each of two processors associated with each indication in the disagreement table.
Claim 11
Dependent Claim
18 words
The method of claim 4 further CHARACTERIZED IN THAT an individual disagreement table is maintained by each processor.
Claim 12
Dependent Claim
40 words
The method of claim 10 further CHARACTERIZED IN THAT when a processor has completed a task, it ascertains if a second processor is assigned to perform the same task and, if so, transmits a result message to the second processor.
Claim 13
Dependent Claim
82 words
The method of claim 11 further CHARACTERIZED IN THAT, in the event a second processor is assigned to perform the task, the first processor waits until a result message is received from the second processor, compares its results with that of the second processor and, if the results do not compare, sets a first indication in its disagreement table that it disagrees with the second processor, and sets a second indication in its disagreement table that the second processor disagrees with it.
Claim 14
Dependent Claim
26 words
The method of claim 12 further CHARACTERIZED IN THAT each processor disagreeing with another processor transmits a disagreement message to all processors identifying the disagreeing processors.
Claim 15
Dependent Claim
23 words
The method of claim 13 further CHARACTERIZED IN THAT the disagreement message contains an encoded identification of the processor transmitting the disagreement message.
Claim 16
Dependent Claim
40 words
The method of claim 14 further CHARACTERIZED IN THAT a processor receiving a disagreement message verifies that the encoded identification of the processor transmitting the disagreement message matches the identify of one of the disagreeing processors contained in the message.
Claim 17
Dependent Claim
44 words
The method of claim 15 further CHARACTERIZED IN THAT a processor receiving a disagreement message ignores the message if the encoded identification of the processor transmitting the disagreement message does not match the identity of one of the disagreeing processors contained in the message.
Claim 18
Dependent Claim
59 words
The method of claim 16 further CHARACTERIZED IN THAT a processor receiving a disagreement message sets a first indication in its disagreement table that a first processor identified in the disagreement message disagrees with a second processor identified in the message and sets a second indication in its disagreement table that the second processor disagrees with the first processor.
Claim 19
Dependent Claim
42 words
The method of claim 17 wherein the step of periodically analyzing a disagreement table is further CHARACTERIZED BY each processor analyzing its individual disagreement table and marking as faulty each of two processors associated with each fault indication in the disagreement table.
Claim 20
Dependent Claim
47 words
The method of claim 18 further CHARACTERIZED IN THAT the system comprises a central controller for administering task assignments of the individual processors and IN THAT the step of each processor analyzing its disagreement table is initiated by a start analysis message received from the central controller.
Claim 21
Dependent Claim
25 words
The method of claim 19 further CHARACTERIZED IN THAT each processor transmits a list of faulty processors to the central controller after the fault analysis.
Claim 22
Dependent Claim
33 words
The method of claim 20 further CHARACTERIZED IN THAT the central controller marks as faulty for task assignments purposes the set of processors common to all of the fault lists from the processors.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-02-21 | 1992-08-22 | 1993-02-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-02-21 | 1996-08-22 | 1997-02-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-02-21 | 2000-08-22 | 2001-02-21 | $7700.00 | Window Closed / Lapsed |