Parallel network optimization on a shared memory multiprocessor and application in VLSI layout compaction and wire balancing

Network optimization refers to the general class of optimization problems defined on graphs and networks. The transshipment and the dual transshipment problems generalize several of the network optimization problems. They can be used to formulate and solve a large class of industrial and engineering problems. As the complexity and sizes of these problems increase, there is a growing demand for more computing power. Parallel computing is one of the ways to meet this demand. This has motivated our work in this thesis on parallel network optimization.;Towards this end, we discuss the design and implementations of three parallel algorithms--one algorithm for the transshipment problem and two algorithms for the dual transshipment problem. We also consider an application of these algorithms in solving VLSI layout compaction and wire balancing problems.;Three basic network optimization algorithms serve as building blocks for our parallel algorithms. They are: Algorithm FEASIBLE to test feasibility of the dual transshipment problem, Algorithm SHORTEST-PATH to compute shortest paths and Algorithm MAX-FLOW to compute a maximum flow in a network. Our parallel algorithms for the dual transshipment problem extensively employ the notions of node/cluster firings and results from the theory of marked graphs.;Our parallel network primal dual method for the transshipment problem is based on the traditional network primal dual method. We show that Algorithm FEASIBLE can be adapted to initialize primal dual method. This obviates the need for constructing an auxiliary network. This is an attractive feature from the point of view of a parallel implementation.;Two new approaches--MNDS (Modified Network Dual Simplex) and CBDS (Cluster-Based Dual Simplex)--are developed for solving the dual transshipment problem. In both these approaches, we do not need to move from one basic solution to another. Constructing efficiently a basic feasible solution starting from a feasible solution and performing efficiently concurrent pivots without destroying feasibility are the distinguishing features of these two approaches. They differ from one another significantly in the way they construct a basic feasible solution. A new characterisation of the structure of the optimum solution of the dual transshipment problem is the basis of the CBDS method.;Finally, we show that the wire balancing problem in VLSI physical design can be formulated as a dual transshipment problem and that layout compaction is a special instance of this problem. In fact, layout compaction can be achieved using Algorithm FEASIBLE. We also introduce the integrated layout compaction and wire balancing problem and present a unified formulation of this problem using the dual transshipment problem.;A comparative experimental evaluation of our parallel algorithms is also provided.