Algorithmic and Combinatorial Advances in VLSI Design Theory

在超大规模集成电路系统的设计和制造中， 通常以固定参数实例为特征。 例如， 参数可以表示芯片上允许的轨道数量，或者 通信链路的负载容量。 通过固定这些参数， 注意力可以集中在物理上可实现的性质， 系统而不是抽象的方面。 研究集中在 IC设计的固定参数算法和组合问题。 强大的，在某些情况下，新兴的技术， 复杂性理论，图论，良好偏序理论， 代数编码理论被用于考虑这种务实的 电路布局、排列、嵌入和布线等问题。 一 第二个推力是组织和利用大型 协同工作的处理器集合。 因此，制度问题 正在解决组织、利用、映射和仿真问题。 本文的研究是集成电路设计理论方面的研究，对我国的集成电路设计具有重要意义。 了解IC设计流程和方法。 校长 调查人员被公认为该领域的专家研究人员， 新颖想法的历史，以及继续产生良好成果的潜力 research. 他们在前两年做了出色的研究 年的补助金。 这导致了15篇论文发表在 档案文献（参考期刊），10篇正在参考，以及 许多在会议记录和书籍。 先前NSF支持的结果 评审员一致对先前NSF的结果非常积极 支持. 他们说，研究结果的质量和 已经对IC理论界产生了影响。 很明显 先前的支持允许发展的想法，导致这一点 提议

In the design and manufacturing of VLSI systems, practical problems are often characterized by fixed parameter instances. For example, such a parameter may represent the number of tracks permitted on a chip or the load capacity of a communications link. By fixing such parameters, attention can be focused on the physically realizable nature of the system rather than abstract aspects. Research is concentrated on fixed-parameter algorithmic and combinatorial problems of IC design. Powerful and, in some cases, emergent techniques from the fields of complexity theory, graph theory, well-partial-order theory, and algebraic coding theory are being used in considering such pragmatic issues as circuit layout, arrangement, embedding, and routing. A second thrust is the general problem of organizing and utilizing large collections of processors working in concert. Thus problems of system organization, utilization, mapping, and emulation are being addressed. The proposed research is on IC design theory, and is important to our understanding of the IC design process and methodology. The Principal Investigators are recognized as expert researchers in this area, have a history of novel ideas, and the potential to continue producing good research. They have done outstanding research during the first two years of the grant. This has resulted in fifteen papers published in the archival literature (refereed journals), ten being refereed, and many in conference proceedings and books. RESULT FROM PRIOR NSF SUPPORT Reviewers were uniformly very positive about the results from prior NSF support. They said the research results were of quality and had already made an impact on the IC theory community. It is clear that the prior support permitted development of the ideas leading to this proposal.