On Designing Parallel Algorithms with Applications to VLSI Routing

Abstract

Data parallel programming provides a simple and powerful framework for designing parallel algorithms that can be mapped efficiently onto a variety of parallel architectures. The model associates a virtual processor as the fundamental unit of parallelism and the computation is expressed in terms of the operations performed by the virtual processors. Each virtual processor can access the memory of any other virtual processor. The algorithms are then evaluated based on two important parameters, time and work. Time refers to the number of time units required by the algorithm, where during each time unit a number of concurrent operations can take place. The work refers to the total number of operations needed to execute the algorithm.<P>This dissertation work on parallel algorithms consists of two parts. The first part develops new computational paradigms for designing efficient parallel algorithms for several important problems in VLSI layout, including channel routing and the problem of routing wires around a rectangle. The second part concerns the evaluation of parallel algorithms. In addition to the time and work parameters, we introduce a third parameter called the communication delay, to model the cost of inter- processor communication. Because of the introduction of the new parameter, scheduling the operations of the parallel algorithm onto physical processors, (so as to optimize the total running time) is no longer an easy task. We so that parallel algorithms that can be represented in the form of arbitrary trees, can be scheduled on p processors, on the new model, such that the resulting makespan is no more than a factor of 3 from the optimal.