The research component of this project will result in the design and development of portable parallel software for solving architectural-level optimization problems that arise in the design of VLSI systems. Several of these problems can be formulated as very large scale integer programs that can be solved in polynomial time using iterative relaxation techniques. The practical running times of these algorithms on serial computers can be prohibitively long, however, especially for interactive design environments. The scaleable parallel software developed in this project will be able to execute orders of magnitude faster than conventional serial code. It will thus enable VLSI designers to interactively explore their design space at an early stage in the design process and to efficiently consider several architectural alternatives before committing to any particular implementation. The educational part of this project aims at the seamless integration of parallel computation in the undergraduate and graduate curriculum. To that effect, two new courses will be developed at Yale. The first course will introduce undergraduates to the basics of serial and parallel computer systems organization. The second course will cover algorithms for computer-aided design of VLSI systems with a research focus on parallel electronic design automation. ***
