Optimal Constraint Graph Generation Algorithm for Layout Compaction Using Enhanced Plane-Sweep Method (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
This paper presents an optimal constraint graph generation algorithm for graph-based one-dimensional layout compaction. The first published algorithm for this problem was the shadow-propagation algorithm. However, without sophisticated implementation of a shadow-front, complexity of the algorithm could fall into O(n^2), where n is the number of layout objects. Although our algorithm, called the enhanced plane-sweep based graph generation algorithm, is an extension of the shadow-propagation algorithm, such a drawback is resolved by introducing an enhanced plane-sweep technique. The algorithm maintains multiple shadow-fronts simultaneously by storing them in a work-list called previous-boundary. Since a balanced search tree is selected for implementation of the work-list, total complexity of the algorithm is O(n log n) which is optimal. Experimental results show that the enhanced plane-sweep based graph generation algorithm runs in almost linear time with respect to the number of layout objects and is faster than the perpendicular plane-sweep algorithm which is also optimal in terms of time complexity.
- 社団法人電子情報通信学会の論文
- 1993-04-25
著者
-
SATO Masao
the Department of Electronics, Information and Communication Engineering, Waseda University
-
OHTSUKI Tatsuo
the Department of Electronics, Information and Communication Engineering, Waseda University
-
Ohtsuki Tatsuo
The Department Of Electronics And Communication Engineering School Of Science And Engineering Waseda
-
Sato Masao
The Department Of Electronics Information And Communication Engineering Waseda University
-
Awashima Toru
The Department Of Electronics And Communication Engineering School Of Science And Engineering Waseda
-
Sato Masao
The Department Of Electronics And Communication Engineering School Of Science And Engineering Waseda
関連論文
- A Performance-Oriented Simultaneous Placement and Global Routing Algorithm for Transport-Processing FPGAs (Special Section on VLSI Design and CAD Algorithms)
- Simultaneous Placement and Global Routing for Transport-Processing FPGA Layout (Special Section on VLSI Design and CAD Algorithms)
- A High-Level Synthesis System for Digital Signal Processing Based on Data-Flow Graph Enumeration (Special Section on VLSI Design and CAD Algorithms)
- A Fast Elliptic Curve Cryptosystem LSI Embedding Word-Based Montgomery Multiplier (System LSIs and Microprocessors, VLSI Design Technology in the Sub-100nm Era)
- A New Hardware/Software Partitioning Algorithm for DSP Processor Cores with Two Types of Register Files(Special Section on VLSI Design and CAD Algorithms)
- Area and Delay Estimation in Hardware/Software Cosynthesis for Digital Signal Processor Cores(Special Section on VLSI Design and CAD Algorithms)
- CAM Processor Synthesis Based on Behavioral Descriptions (Special Section on VLSI Design and CAD Algorithms)
- A Hardware / Software Cosynthesis System for Digital Signal Processor Cores with Two Types of Register Files (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
- Optimal Constraint Graph Generation Algorithm for Layout Compaction Using Enhanced Plane-Sweep Method (Special Section on Discrete Mathematics and Its Applications)
- Placement, Routing, and Compaction Algorithms for Analog Circuits (Special Section on JTC-CSCC '92)
- A Fast Scheduling Algorithm Based on Gradual Time-Frame Reduction for Datapath Synthesis
- An FPGA Layout Reconfiguration Algorithm Based on Global Routes for Engineering Changes in System Design Specifications(Special Section on Discrete Mathematics and Its Applications)