Research in the field of parallel computer architectures and parallel algorithms has been very successful in recent years, and further progress isto be expected. On the other hand, the question of basic principles of the architecture of universal parallel computers and their realizations is still wide open. The answer to this question must be regarded as mostimportant for the further development of parallel computing and especially for user acceptance. The First Heinz Nixdorf Symposium brought together leading experts in the field of parallel computing and its applications to discuss the state of the art, promising directions of research, and future perspectives. It was the first in a series of Heinz Nixdorf Symposia,intended to cover varying subjects from the research spectrum of the Heinz Nixdorf Institute of the University of Paderborn. This volume presents the proceedings of the symposium, which was held in Paderborn in November 1992. The contributions are grouped into four parts: parallel computation models and simulations, existing parallel machines, communication and programming paradigms, and parallel algorithms.

This thesis provides a comparative analysis of various interconnection networks and multiprocessor systems. The Shuffle-Exchange multistage interconnection Network (SEN) and its variants are evaluated and compared. Comparison is based on reliability, composite measures of performance and reliability, and cost. Closed-form expressions for the computation of the available bandwidth for multiprocessor systems with a capability of graceful degradation are developed. The time dependent reliability of the SEN and three fault-tolerant schemes aimed at improving system reliability are examined. These schemes are the redundant network, the extra stage network, and the network augmented with intrastage links. Exact closed-form expressions for the time-dependent reliability of the N x N Shuffle-Exchange Network (SEN), the 8 x 8 and 16 x 16 SEN with an additional stage (SEN+), and the 4 X 4 and 8 X 8 Augmented SEN (ASEN) are derived. Upper and lower bounds useful for the analysis of larger SEN+ and ASEN networks are derived. Performability analysis of a complete multiprocessor system is conducted.