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.
