Graph Embeddings: Their Relation to Layout and Parallel Architectures

图嵌入：它们与布局和并行架构的关系

• 批准号: 8715652
• 负责人: Susanne Hambrusch
• 金额: $ 7.69万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-01-15 至 1990-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8715652&HistoricalAwards=false
• 关键词: Graph; Embeddings; Their; Relation; Layout

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.

首席研究员正在解决图形嵌入问题 超大规模集成电路设计的布局和并行映射中出现的 算法到并行计算结构。 相对于 布局，Hambrusch博士正在调查的问题， 多层模型，包括线性排列和 将非平面问题分解为平面问题。 成本措施 所使用的是单独的和总的导线长度以及层数。 对于并行处理，问题在于嵌入 将源互连网络连接到主机网络， 更小的尺寸。 重点是树状和网状网络 以及源网络的算法行为。 等 嵌入将针对并行功能进行定制， 源网络算法中使用的子程序。