In this research, we have investigated parallel algorithms for several CAD tools with the objective of reducing the design turnaround times of the CAD tools, and to enable larger CAD problems to be solved. All the tools are developed using the Message-Passing Interface (MPI).
In the area of global routing, we have developed a parallel algorithm for timing driven global routing. By integrating high-performance interconnection tree construction, wire sizing, and switchable segment channel optimization together, we have developed an adaptive timing driven global routing algorithm that minimizes the timing delay as well as the ciricuit area. Experimental results on various MCNC routing benchmarks showed speedups of 3 on 8 processors on an IBM J-40 shared memory multiprocessor.
In the area of behavioral synthesis, we have developed some parallel algorithms for simultaneous scheduling, binding, and floorplanning. In comparison to traditional approaches which separates high-level synthesis from physical design, we have devised an algorithm where these stages interact closely. This results in solutions with lower latency and area, but require increased computation times. Exerimental results on a set of synthesis benchmarks showed speedups of about 7.8 on 8 processors on an IBM SP2 message-passing multicomputer.
In the area of power estimation, we have developed a comprehensive study of parallel algorithms for power estimation using exhaustive simulation and Monte Carlo simulation on combinational and sequential circuits. We have developed both pattern partitioned and circuit partitioned parallel algorithms. Speedups of 11 on 16 processors using pattern partitioned approaches, and speedups of 7 on 16 processors using circuit partitioned approaches were obtained on an IBM SP-2 message-passing multicomputer.
Finally, in the area of behavioral simulation, we have developed an efficient sequential VHDL simulator based on compiled event driven simulation. Two approaches to parallelizing compiled VHDL simulation have been developed, one is based on fine grain task scheduling, and another is based on coarse grain partitioning based on fanin cones. While the first algorithm did not result in any speedups, the second algorithm acheived speedups of about 3 on 8 processors of an IBM J-40 shared memory multiprocessor.
This project was supported by NSF and DARPA and supported 5 Ph.D., 1 M.S. and 1 undergraduate student. It resulted in 5 journal and 20 conference publications. One of these papers received the Best Paper award at the VLSI Test Symposium, in April 1998. 2 Ph.D students graduated (Gagan Hasteer, Sumit Roy) and 1 M.S. student graduated (Victor Kim) during this period.