Files in this item



application/pdf8410024.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Fault Tolerant Bus Communication Protocols for Computer Systems
Author(s):Pollard, Leonard Howard
Department / Program:Electrical Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Abstract:Bus systems form the communication medium for computers, and a great deal of effort has been devoted to detecting errors which occur as information is transferred from one module to another. In this thesis we look at the problem of not only detecting faults which occur, but continuing to function in the presence of those faults. The lines of a bus are grouped together into two classes: synchronous address and data lines, and the control lines which govern the action of the synchronous lines.
The fault model which is assumed for the synchronous lines includes not only the classical stuck-at fault, but also bridging faults and transient faults. Two algorithms are presented which use time redundancy to guarantee correct transfer of information in the presence of a single fault. One requires a single retry and is applicable for stuck-at faults and adjacent bridging faults. The other algorithm removes the adjacency requirement, but requires either one or two retrys, depending on the type of fault.
The modules comprising the protocol system are represented using state machines, and the action of the system is monitored by observing the states of the modules and the levels of the bus lines. A State Machine Language (SML) is developed to represent a protocol system. SML representations of the modules form the input to a protocol exercise system which simulates the actions of the system and identifies errors which occur.
Knowledge of the prescribed behavior of the control lines allows the presence of stuck-at faults to be detected by the use of time-out escape sequences. The knowledge of the behavior of the control lines also permits dual-rail control signals to be used to guarantee continued operation in the presence of single faults. The expected levels of the signals as the protocol sequences through its actions allow identification of lines which are stuck at an incorrect value; the incorrect line can then be ignored as the module continues to function. Three algorithms are presented which will convert state machines for single-rail control signals to state machines which accommodate dual-rail signals. The system cost associated with this technique consists of the additional lines needed for dual-rail control signals and for implementing the time redundant transfer algorithms, and the additional hardware needed to implement the algorithms. For a standard bus this means about a 40% increase in the number of lines and approximately doubling the hardware dedicated to the bus control function.
Issue Date:1983
Description:172 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1983.
Other Identifier(s):(UMI)AAI8410024
Date Available in IDEALS:2014-12-15
Date Deposited:1983

This item appears in the following Collection(s)

Item Statistics