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.