Graph Embeddings: Their Relation to Layout and Parallel Architectures

首席研究员正在解决在VLSI设计布局和并行算法到并行计算结构的映射中出现的图嵌入问题。在布局方面，Hambrusch博士正在研究由多层模型驱动的问题，包括线性排列和将非平面问题划分为平面问题的问题。使用的成本措施是单根和总电线长度以及层数。在并行处理方面，问题是将源互连网络嵌入到较小规模的主机网络中。重点是树状和网状网络以及源网络的算法行为。这种嵌入将针对源网络算法中使用的并行函数和子程序进行定制。

The principal investigator is addressing graph embedding issues arising in layout of VLSI designs and mapping of parallel algorithms to parallel computing structures. With respect to layout, Dr. Hambrusch is investigating problems motivated by multilayer models, including problems of linear arrangement and partitioning nonplanar problems into planar ones. Cost measures used are individual and total wire length, and number of layers. With respect to parallel processing, the problem is the embedding of a source interconnection network into a host network of smaller size. Concentration is on tree and mesh-like networks and the algorithmic behavior of the source network. Such embeddings will be tailored towards the parallel functions and subroutines used in the algorithm for the source network.