Minimal Full-Access Interconnection Networks for Parallel Processing

随着低成本微型计算机的出现， 可以构造用于互连多个处理器网络 和存储器以实现更高的计算速度。 在这 研究项目，主要研究者（PI）将研究 紧密耦合的处理器使用动态 互联网 一般来说，问题是提供一种方法， 互连处理元件的集合，使得任何 两个处理元件可以获得直接通信路径。 这将允许动态重新配置。 PI建议 研究互连网络的类别， 访问（即，每个输入访问每个输出的能力） 使用尽可能少的阶段-网络，PI 它被称为“最小完全访问”（MFA）。 以下是预期的研究结果： o MFA网络结构特性的表征。 o关于可通过特定 MFA网络的子类以及结果与 可由其他类别的网络实现的置换。 用于路由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.