U.S.-France (INRIA) Cooperative Research: Specifying and Finding Solutions to Constraint and Search Problems

该奖项将支持美国和法国计算机科学家之间的合作研究。美国调查人员是：来自伊利诺伊大学厄巴纳分校的刘C.L.博士、爱德华·M·莱因戈尔德博士和纳丘姆·德肖维茨博士。法国合作者包括：南希大学的勒内·肖特博士和法国国家计算机科学与自动化研究所(INRIA)洛林校区的克劳德·基什内尔和迈克尔·鲁辛诺维奇。研究将集中在约束的算法求解和搜索算法的设计和分析上。作为一组约束条件，设计算法以寻找问题的最优或接近最优解决方案的任务已经从VLSI电路设计的进步所产生的需求中获得了额外的推动力。同时，一些现代编程语言(例如PROLOG)可以被视为搜索指定为约束集的程序的解决方案的系统。随着并行计算机的出现，在约束求解方面出现了新的问题。此外，未来的编程环境可能包含内置的定理证明器和约束求解器。需要开发用于分析搜索算法的技术。该项目将涉及VSLI研究的两个主要领域。在设计和综合领域，短期内的大部分工作将致力于物理设计的研究。从长远来看，研究人员将在更高级别的综合领域做出更大的努力，特别是在逻辑最小化、模块生成和状态分配等主题上。该项目将受益于这两个小组在集成电路物理设计方面的广泛和互补的专门知识。所要考虑的问题将在超大规模集成、超高级编程语言、自动推理以及设计有效的搜索和约束求解算法方面具有重要的应用。理论工作的结果将直接有利于我们设计多芯片模块的布线和布局，这是美国电子公司正在利用的一个非常重要的概念。

This award will support collaborative research between US and French computer scientists. The US investigators are: Dr. C.L. Liu, Dr. Edward M. Reingold and Dr. Nachum Dershowitz, all from the University of Illinois at Urbana. The French collaborators include: Dr. Rene Schott, University of Nancy and Claude Kirchner and Michael Rusinowitch, of the Lorraine campus of INRIA, the French National Institute for Research in Computer Science and Automation. The research will focus on algorithmic solution of restraints and the design and analysis of search algorithms. The task of designing algorithms for finding optimal or near-optimal solutions to problems as a set of constraints has received added impetus from needs engendered by advances in VLSI circuit design. At the same time, some modern programming languages (e.g. Prolog) can be viewed as systems that search for solutions to programs specified as sets of constraints. With parallel computers, new issues in constraint solving have arisen. Furthermore, future programming environments may contain built in theorem provers and constraint solvers. Techniques for analyzing search algorithms need to be developed. This project will address two major areas in VSLI research. In the design and synthesis area, most of the effort in the short term future will be devoted to research in physical design. In the long term, the investigators will build up their effort in the area of higher level synthesis, in particular, working on topics such as logic minimization, module generation and state assignment. The project will benefit from the extensive and the complementary expertise of the two groups in the physical design of integrated circuits. The problems to be considered will have important applications to very large scale integration, very high level programming languages, automated deduction and design of efficient search and constraint-solution algorithms. The results of the theoretical work will have a direct benefit to our ability to design the wiring and placement of multichip modules, a very important concept which is being exploited by US electronics firms.