Browsing by Author "Krishnamurthy, Sridhar"
Results Per Page
Sort Options
Item On Designing Parallel Algorithms with Applications to VLSI Routing(1992) Krishnamurthy, Sridhar; JaJa, J.F.; ISRData 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.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.
Item Parallel Algorithms for VLSI Layout.(1989) JaJa, Joseph F.; Krishnamurthy, Sridhar; ISREfficient automatic layout tools are clearly essential for designing complex VLSI systems. Recent efforts have been directed toward developing parallel algorithms to handle the different subproblems involved in the layout phase. Some of these algorithms have been shown to offer significant speed-ups over the sequential ones. In this chapter, basic parallel techniques that have been found to be effective for handling problems arising in the layout phase are reviewed. In particular, parallel algorithms for problems arising in paffitioning, placement and routing are discussed. The algorithms used to handle these problems can be classified into two broad categories: iterative or direct. The iterative techniques such as simulated annealing and the Kernighan-Lin algorithm are very effective for partitioning and placment. The direct methods seem to be dominant in routing. These methods and some new methods are discussed in the general context of parallel processing. Efficient algorithms for the shared-memory model and for distributed-memory multiprocessors such as the hypercube are described. In addition, several special-purpose hardware for placement and routing are also outlined and their merits discussed.Item Provably Good Parallel Algorithms for Channel Routing of Multi- terminal Nets.(1988) Krishnamurthy, Sridhar; JaJa, Joseph F.; ISRWe consider the channel routing problem of a set of multi- terminal nets in the knockknee model. We develop a new approach to route all the nets within d + ALPHA tracks, where d is the channel density, and 0 < ALPHA < d, such that the corresponding layout can be realized with three layers. Both the routing and the layer assignment algorithms have linear time sequential implementations. In addition both can be implemented on the CREW- PRAM model in O( n/p + log n) time, with p processors, 1 < p < n and n is the size of the input.