並列計算環境上の超大規模組合せ最適化基本技術の研究

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

Efficient Algorithms are discussed for the very large combinatorial optimization problems emerging in the layout design for VLSI.The objectives of this project are as follows.(1) Formulate problems so as to make it possible to apply not heuristic algorithms but the optimum ones whose optimality are theoretically proven to then,(2) Formulate problems as goal programming problems to solve complicated combinatorial optimization problems,(3) Apply parallel processing techniques to reduce processing time.For attaining (1) and (2), in the research and development of algorithms for initial placement, placement improvement, global routing and detailed routing, the problems are formulated as linear or non-linear programming problems. This is because those problems are formulated as goal programming problems in order to optimize the conflicting objective functions such as electrical performances and layout size at the same time. To solve these problems the randomized algorithm is used and its performance is experimentally evaluated, The results show that it is likely that this technique generates better solution though the processing time is longer than before.To reduce the processing time, the area-division parallel processing is devised. This parallel processing consists of the division of the layout area and the net list, the layout process of the much smaller scale problems and the merge of the generated solutions. For attaining (3), a parallel processing platform is experimentally developed by using the Voyager and then it is evaluated. As a result, it is concluded that this platform is useful for our system.The layout system consisting of the placement and routing processes has not yet been developed. However, the performance of each process is independently evaluated by developing its own data input and output programs. In the near future, efforts must be concentrated to the development of the layout system so as to evaluate this system against actual benchmark data.