RIA: Hypercube-Based Systems

本研究的主要目标是解决为多层体系结构开发的应用程序算法映射问题，多层体系结构比标准金字塔体系结构更通用，到基于超立方体的系统。基于hypercube的系统在商业上是可用的，并且被科学界广泛使用，因为它们高度灵活、容错和高效。研究人员一直在成功地尝试解决将标准金字塔嵌入超立方体的问题。然而，这种嵌入并不能保证所有的多层算法都有很高的性能，因为嵌入过程没有考虑到特定算法的性能要求。这个项目将分为五个阶段。第一阶段将提出将多层结构嵌入超立方体的算法。第二阶段将涉及对第一阶段提出的嵌入算法进行细化，以使应用算法的精确计算和通信需求影响嵌入。第三阶段将尝试修改第二阶段提出的嵌入算法，使它们考虑到统计性能数据，以便适合非确定性和数据依赖的多层算法的映射。该项目的第四阶段将提出一类“多立方体”系统，虽然提供较少数量的通信通道，但可以产生与超立方体相当的性能。最后，将开发将多层算法映射到基于超立方体和多立方体系统的技术。分析技术和仿真结果将用来证明映射算法的有效性和效率。

The main objective of this research is to solve the problem of mapping application algorithms developed for multilevel architectures, which are more general than the standard-pyramid architecture, onto hypercube-based systems. Hypercube-based systems are commercially available and have widely been used by the scientific community because they are highly flexible, fault-tolerant, and efficient. Researchers have been trying with success, to solve the problem of embedding standard pyramids into hypercubes. However, such embeddings do not guarantee very high performance for all of the multilevel algorithms, because the performance requirements of particular algorithms are not taken into account by the embedding process. This project will evolve through five phases. The first phase will propose algorithms for embedding multilevel structures into hypercubes. The second phase will be involved in the refinement of the embedding algorithms proposed in the first phase, in such a way that the exact computation and communication requirements of the application algorithms should affect the embeddings. The third phase will attempt modifications of the embedding algorithms proposed in the second phase, so that they will be taking into account statistical performance data, in order to become suitable for the mapping of non-deterministic and data-dependent multilevel algorithms. The fourth phase of this project will propose a class of "multicube" systems, which, while providing smaller numbers of communication channels, can yield performance comparable to that of the hypercube. To conclude techniques for mapping multilevel algorithms onto hypercube-based and multicube systems will be developed. Analytical techniques and simulation results will be used to prove the effectiveness and efficiency of the mapping algorithms.