Topological Properties of Interconnection Networks for Parallel Processors. A Unified Approach. Appendix E

摘要

Two methods are used to speed up the execution of a computational task. One is new technology development and the other is the exploitation of parallelism in the computation. To take an advantage of the parallelism in a task requires the utilization of parallel computer architectures. At a certain high level of abstraction a parallel computer system is represented as a graph where the nodes represent processors, memories, or other devices, and the edges represent the communication links. In this thesis the following problems of parallel processing are studied. First is a theoretical study of topological properties of interconnection networks. Second is a case study of a network design for a real-time system. Lastly, the use of SIMD(Single Instruction Stream Multiple Data Stream) networks for performing 'shuffles'. A general model that can be used to describe networks and systems with arbitrary topologies is developed. Based upon the of morphism of groups, the concept of morphism of systems is developed. The morphism of systems is called quasimorphism and allows a method of comparison between topologically arbitrary parallel computer systems. The quasimorphism is used to study the emulation of one system by another.