Graph Embeddings: Their Relation to Layout and Parallel Architectures

首席研究员正在解决图形嵌入问题 超大规模集成电路设计的布局和并行映射中出现的 算法到并行计算结构。 相对于 布局，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.