Analyzing Parallel Architectures With Algebraic Topology

点击翻译按钮获取中文摘要

An important aspect of a parallel architecture is the interconnection network, which can be represented as a graph. Many graphs have been proposed as suited to parallel computation. Previous research has partially answered the questions of which graphs to use for which problems and of which graphs are most generally useful for parallel processing. What has been lacking are uniform techniques and a comprehensive theory for analyzing parallel networks. The central thesis of this research project is that analogies to the mathematical theory of algebraic topology can provide a foundation for a theory of parallel networks. New topologies for graphs are defined that capture the essence of the graphs as parallel networks. Topological invariants are defined that facilitate comparison and evaluation of networks, and efficient algorithms are given to compute these invariants. The standard technique for simulating one parallel network by another is via graph embeddings. In the topological framework, a graph embedding is a special kind of continuous function between topolical spaces. Algorithms are given to compute the homotopology and homology groups of a graph and to compute the group homomorphisms induced by a graph embedding. Techniques are developed to prove upper and lower bounds on the ability of one network to simulate another. The ultimate result of this research is a unified mathematical theory of graphs as parallel architectures.