Programming Pipelined CAD Applications on Message Passing Architectures

Programming applications in computer aided design of VLSI is difficult on parallel architectures, especially pipelined implementations derived from their sequential counterparts by algorithmic partitioning. The difficulty is primarily due to lack of good program development environments and tools. Our solution, applicable to message-passing architectures, is based upon a definition of a road class of nonlinear pipeline configurations and an synchronous data-driven model for pipeline stage interactions. It provides object-oriented definitions of stages and interconnecting channels. These objects are embedded in C++ so that the correctness of application programs can be tested on a workstation in a simulated environment. The simulation is so instrumented to provide data useful in assessing relative computational loading and balancing of stages. Thus a good part of program development can take place in the environment of a workstation familiar to the programmer. Two non-trivial applications are developed to illustrate these ideas.