Minimal Full-Access Interconnection Networks for Parallel Processing

随着低成本微型计算机的出现，现在可以构建网络来互连多个处理器和存储器，以实现更快的计算速度。在这个研究项目中，首席研究员(PI)将研究使用动态互连网络互连的紧耦合处理器。一般而言，问题在于提供一种互连处理元件集合的手段，使得任何两个处理元件都可以获得直接通信路径。这将允许动态重新配置。PI建议使用尽可能少的级数来研究提供完全访问(即每一输入访问每一输出的能力)的一类互连网络--PI将其称为“最小完全访问”(MFA)的网络。以下是预期的研究成果：o MFA网络结构性质的刻画。O关于MFA网络的特定子类可实现的排列集合的结果，以及这些结果与其他网络类可实现的排列的比较。O用于路由MFA网络的高效算法。O允许将一个网络动态重新配置为更适合手头应用的另一个网络的技术。O对所研究的网络进行简单的修改，以提高容错能力。O判定网络结构和功能等价性的算法。这项工作有望产生新的网络类别，并为所有互连网络的基本理论提供基础。它还有望影响(d，k)图问题和某些矩阵方程的解。

With the advent of low-cost microcomputers, it is now feasible to construct networks for interconnecting many processor and memories to achieve higher speed of computation. In this research project, the principal investigator (PI) will study tightly-coupled processors interconnected using a dynamic interconnection network. In very general terms, the problem is to provide a means of interconnecting a collection of processing elements so that any two processing elements can obtain a direct communication path. This will allow dynamic reconfigurations. The PI proposes to study the class of interconnection networks that provide full access (i.e., the ability for every input to access every output) using the fewest possible number of stages--networks which the PI refers to as "minimal full-access" (MFA). The following are expected research results: o Characterizations of structural properties of MFA networks. o Results on the set of permutations realizable by particular subclasses of MFA networks and how the results compare to permutations realizable by other classes of networks. o Efficient algorithms for routing MFA networks. o Techniques for allowing dynamic reconfigurations of one network into another better suited for applications at hand. o Simple modifications of the networks studied, to allow for increased fault tolerance. o Algorithms for deciding structural and functional equivalence of networks. This work is expected to produce new classes of networks, as well as provide a basis for an underlying theory of all interconnection networks. It is also expected to impact the (d,k) graph problem and the solution of certain matrix equations.