Robust performance optimization using padding nodes and separator sets

作     者：Tamiya, Y 

作者机构：Fujitsu Labs Ltd Kawasaki Kanagawa 2118588 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (电子信息通信学会汇刊：电子学、通信及计算机科学基础)

年 卷 期：2001年第E84A卷第11期

页      面：2739-2745页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：timing optimization separator set network flow algorithm 

摘      要：In this paper we present two contributions for a set of local transformations (a selection set) to improve a performance of a very large circuit. The first contribution is an idea of padding node and multi-separator-set. We have proven that combination of padding node and multi-separator-set provides the optimum selection set. The second contribution is our heuristic method to find a semi-optimum multi-separator-set, which uses a network flow algorithm. Our method is robust for very large circuits, because its memory usage and calculation time are linear and polynomial order with the size of the circuit. We have compared our method with Singh s selection function method, which provides the optimum selection set and is the best method in literature to date. Our method has successfully optimized delays of all circuits, while Singh s selection function method has aborted with three large circuits because of memory overflow. The results also has shown our method has a comparable capability in delay optimization to Singh s method, although our method is heuristic.