Novel algorithms for placement and routing and their parallel implementations

With the rapid advances in VLSI process technology, layout synthesis is becoming increasingly complex. Parallel processing is fast becoming an attractive solution to reduce the inordinate amount of time spent in VLSI circuit design. In this thesis, we investigate algorithms and their parallel implementations for module placement, global routing for standard cells, and layout synthesis for clock trees.; Using the matrix perturbation approach, we present a fast and effective module placement algorithm which is based on the PROUD algorithm. The new modified PROUD algorithm performs significantly faster than the original PROUD algorithm. We subsequently propose a parallel version of the modified algorithm that combines both fine grain and coarse grain parallelism to obtain another order of magnitude improvement in the runtime with very little loss of the quality of the layout.; We propose three different parallel algorithms based on a state-of-the-art global router for area-minimization called TimberWolf 6.0. The first algorithm partitions the pins in a row-wise manner among the processors. The second algorithm partitions the nets and their corresponding pins among the processors. The third algorithm uses a hybrid approach. Both pin row partitioned algorithm and hybrid pin partitioned algorithms provide good speedup and quality.; By integrating high performance interconnection tree construction, wire-sizing, and switchable segment channel optimization together, we propose an adaptive timing-driven global routing algorithm which minimizes the timing delay as well as circuit area. In addition, we proposed a parallel algorithm to reduce the excessive running time of our timing-driven global router, which is the first work on parallel timing-driven global routing.; We propose two algorithms to get the exact zero skew wire-sizing for clock tree routing. Our experiments on benchmark clock trees show that one of the algorithms reduces the source sink delay significantly that of the clock trees with uniform wire sizes and keeps the clock skew zero. We also propose a parallel algorithm using a cluster-based clock tree construction algorithm and our zero skew wire-sizing algorithm.; Using the Message Passing Interface (MPI), all of our parallel algorithm were implemented on various multiprocessor systems for a variety of large layout benchmark circuits.