Solving layout compaction and wire-balancing problem using linear programming on the Monsoon multiprocessor

The theme of this work is parallel computing for a CAD application. The layout compaction and wire-balancing problem in VLSI physical design can be formulated as a dual transshipment problem (DTP) which can be written as a linear programming problem and solved using the network dual simplex (NDS) algorithm. The goal of our work is to implement this algorithm using an implicitly parallel functional language called Id on a small shared memory Monsoon dataflow multiprocessor and study the features of this declarative language to determine quantitatively the amount of parallelism exposed in each feature. In the process, we also examine the parallelism in each phase of the application. We observed that Id's functional features (Higher-order functions, tuples, list and array comprehension, etc.) played a major role to extract the parallelism from our codes. The atomic M-structure allows processes to interact freely, hence, contributing to the parallelism. The resultant parallelism amounted to an average of 20 to 25 operations per cycle. In this thesis, we compare sequential pivoting with concurrent pivoting strategy in the NDS algorithm. From the experiments, we show that the loss of basicity after concurrent pivoting and then, retaining it makes the NDS slower due to the poor performance of the 0-token spanning-tree building method. Moreover, both pivoting strategies show almost the same amount of parallelism