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.