In any stored-program computer system, information is constantly transferred between the memory and the instruction processor. Machine instructions are a major portion of this traffic. Since transfer bandwidth is a limited resource, inefficiency in the encoding of instruction information (low code density) can have definite hardware and performance costs.

Introduces a nested-predicate scheme for fault tolerance, called Nest. Nest provides a formal comprehensive model for fault-tolerant parallel algorithms and a general methodology for designing reliable applications for multiprocessor systems. The model relies on the formalization of concepts for fault tolerance by means of three nested system predicates and on properties ruling their interrelationships. This rigorous framework facilitates the study of the specific properties that enable an algorithm to tolerate faults. The consequence of that is the outline of systematic design techniques that can be used to add fault tolerance properties to algorithms while preserving their functional characteristics.>

A class of algorithms suitable for fault-tolerant execution in multiprocessor systems by exploiting the existing embedded redundancy in the problem variables is characterized. Because of this unique property, no extra computations need be superimposed on the algorithm in order to provide redundancy for fault recovery, as well as fault detection in some cases. A forward recovery scheme is thus used with very low time overhead. The method is applied to the implementation of two iterative algorithms: solution of Laplace equations by Jacobi's method and the calculation of the invariant distribution of a Markov chain. Experiments show less than 15% performance degradation for significant problem instances in fault-free situations, and as low as 2.43% in some cases. The extra computation time needed for locating and recovering from a detected fault does not exceed the time necessary to execute a single iteration. The fault-detection procedures provide fault coverage close to 100% for faults causing errors that affect the correctness of the computations.>

A tree-based interconnection architecture (called KYKLOS) for multicomputer systems is proposed. While the general form of the topology consists of multiple m-ary trees sharing a common set of leaf nodes, the focus is on the dual-tree case. One version of the dual-tree KYKLOS involves a bottom tree where the ordering of descendants of nodes at every level is an m-way shuffle. This architecture provides fault tolerance and vastly improved properties over the simple double tree while retaining the simplicity and low fan-out of the m-ary tree. Different routing strategies are presented and network properties as a function of routing strategy are investigated. The O(N/sup 2/) congestion at the root of the m-ary tree is reduced to O(N/sup 1.5/) while average normalized communication latencies are decreased. Applications of this architecture to facilitate parallel input/output (I/O) access and parallel processing of database operations such as the relational join are studied.>

An algorithm to route packets in rectangular SW-banyans is described. A packet-switching scheme is modeled on single-sided and double-sided SW-banyans. Effects of queue lengths and processor configurations on performance are studied. Prevention of deadlocks in the network is discussed. Simulation results suggest a scheme with varying queue lengths for different levels of the network to optimize performance, and that the length be limited. The algorithm presented is able to take advantage of the network traffic information stored at a node and dynamically route a packet through a shortest path which has the least load.>

Construction algorithms for rectangular and nonrectangular CC-banyan networks, as well as routing algorithms for double-ended and single-ended rectangular and nonrectangular CC-banyan networks, are presented. The time complexities of the routing algorithms are O(l), where l is the number of stages in the network.>

article Free Access Share on Dynamic, distributed resource configuration on SW-banyans Authors: John Feo Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, Texas Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, TexasView Profile , Roy Jenevein Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, Texas Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, TexasView Profile , J. C. Browne Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, Texas Departments of Computer Sciences and Computer and Electrical Engineering, The University of Texas at Austin, Austin, TexasView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 268–275https://doi.org/10.1145/327070.327233Published:01 June 1985Publication History 0citation156DownloadsMetricsTotal Citations0Total Downloads156Last 12 Months7Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problems of resource allocation, configuration and reconfiguration and network control must be solved before reconfigurable array computers can be effectively utilized. The interconnection networks proposed for these systems vary so that there has been no common or optimal solution proposed to these problems. This paper defines and describes the objectives, design, implementation and use of a network controller for a reconfigurable array computer, the Texas Reconfigurable Array Computer (TRAC). The objectives for the network controller are defined by management of the system state, the requirements of the operating system for functionality and the interface the network presents to the operating system. These objectives may be expected to have at least some commonality across most reconfigurable network architectures. The structure of the network controller given herein may offer guidance for development of controllers for other reconfigurable network architectures.