Algorithmic and Combinatorial Advances in VLSI Design Theory

在超大规模集成电路系统的设计和制造中，实际问题往往以固定参数实例为特征。例如，这样的参数可以表示芯片上允许的轨道数或通信链路的负载能力。通过固定这些参数，可以将注意力集中在系统的物理可实现性质上，而不是抽象的方面。主要研究集成电路设计中的固定参数算法和组合问题。复杂理论、图论、良偏序理论和代数编码理论等领域中强大的新兴技术，在某些情况下，正被用于考虑诸如电路布局、排列、嵌入和路由等实用问题。第二个问题是组织和利用协同工作的大型处理器集合的一般问题。这样就解决了系统组织、利用、映射和模拟的问题。本研究以集成电路设计理论为基础，对我们理解集成电路设计过程和方法具有重要意义。首席研究员是该领域公认的专家研究人员，具有新颖想法的历史，并有继续进行良好研究的潜力。他们在获得资助的头两年做了出色的研究。这导致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.