A Study on Parallel Processing for VLSI Layout

本研究所得结果总结如下：1。构建块布局算法的开发：我们开发了一种分层布局方法，该方法以分层方式确定布局和详细路线。此外，我们设计了一个最优的线性时间算法来分配通道引脚。门阵列布局算法的发展：我们开发了一种在门阵列芯片中定时驱动单元放置的算法。此外，我们还设计了一种具有超小区路由的大型门阵列全局路由方法。这些方法可以很容易地修改为并行算法，与现有方法相比，可以在较短的计算时间内获得更好的结果。并行算法开发系统的开发：我们在工作站上实现了一个用于评估并行算法的模拟器。仿真器的计算模型为共享内存共享总线型多处理器。仿真器可以生成详细的缓存命中率等仿真数据。我们还开发了一种用于顺序循环DOACROSS并行化的处理器调度算法，从而使并行算法的有效执行成为可能。并行布局算法的发展：我们设计了一种并行算法来解决图的划分问题，这是VLSI布局设计中的基本问题之一。从理论和实验两方面对该算法进行了评价。我们还开发了一种基于并行图划分算法的并行模块放置算法。这些算法表明，在VLSI版图设计中引入并行处理可以在较短的设计时间内获得良好的设计效果。

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.