A Study on Parallel Processing for VLSI Layout

点击翻译按钮获取中文摘要

Results obtained in this research are summarized below.1. Development of algorithms for building-block layout : We developed a hierarchical floorplanning method which determines floorplan and detailed routing together in a hierarchial fashion. Furthermore, we devised an optimal linear time algorithm for channel pin assignment.2. Development of algorithms for gate-array layout : We developed an algorithm for timing-driven placement of cells in a gate-array chip. Furthermore, we devised a global routing method for large gate-array with over-the-cell routing. These methods can be easily modified to parallel algorithms, which can obtain better results in short computation time compared with existing methods.3. Development of a parallel algorithm development system : We implemented a simulator for evaluating parallel algorithms on a workstation. Computation model of the simulator was a shared memory shared bus type multiprocessor. The simulator can produce a detailed simulation data such as hit ratio of cache. We also developed a processor scheduling algorithm for DOACROSS parallelization of sequential loops so that efficient execution of parallel algorithms becomes possible.4. Development of parallel layout algorithms : We devised a parallel algorithm for the problem of partitioning a graph, which is one of the fundamental problems in VLSI layout design. The algorithm was evaluated from both theoretical and experimental points of view. We also developed a parallel module placement algorithm based on a parallel graph partitioning algorithm. These algorithms showed that introducing parallel processing into VLSI layout design is quite effective to obtain good design in a short design time.