Minimum Cut Linear Arrangement of p-q Dags for VLSI Layout of Adder Trees (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within n^<0(1)> time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.
- 社団法人電子情報通信学会の論文
- 1999-05-25
著者
-
TAKAGI Kazuyoshi
Graduate School of Information Science, Nagoya University
-
TAKAGI Naofumi
Department of Information Engineering, Nagoya University
-
Takagi Kazuyoshi
Graduate School Of Information Schience Nara Institute Of Schience And Technology
-
Takagi Kazuyoshi
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Takagi Naofumi
Department Of Information Engineering Nagoya Univerity
-
Takagi Naofumi
Department Of Communications And Computer Engineering Kyoto University
関連論文
- A VLSI Architecture for Output Probability Computations of HMM-Based Recognition Systems with Store-Based Block Parallel Processing
- Automated Passive-Transmission-Line Routing Tool for Single-Flux-Quantum Circuits Based on A* Algorithm
- A Method of Sequential Circuit Synthesis Using One-Hot Encoding for Single-Flux-Quantum Digital Circuits(Superconducting Electronics)
- Logic Synthesis Method for Dual-Rail RSFQ Digital Circuits Using Root-Shared Binary Decision Diagrams(VLSI Design Technology and CAD)
- Floating-Point Euclidean Norm Computing Circuit
- Digit-Recurrence Algorithm for Computing Reciprocal Square-Root(Regular Section)
- A Hardware Algorithm for Integer Division Using the SD2 Representation(VLSI Design Technology and CAD)
- A VLSI Architecture for Output Probability Computations of HMM-Based Recognition Systems with Store-Based Block Parallel Processing
- Computational Power of Nondeterministic Ordered Binary Decision Diagrams and Their Subclasses (Special Section on Discrete Mathematics and Its Applications)
- Minimum Cut Linear Arrangement of p-q Dags for VLSI Layout of Adder Trees (Special Section on Discrete Mathematics and Its Applications)
- Proposal of a Desk-Side Supercomputer with Reconfigurable Data-Paths Using Rapid Single-Flux-Quantum Circuits
- 100GHz Demonstrations Based on the Single-Flux-Quantum Cell Library for the 10kA/cm^2 Nb Multi-Layer Process
- Automated Passive-Transmission-Line Routing Tool for Single-Flux-Quantum Circuits Based on A^* Algorithm
- A Clock Scheduling Algorithm for High-Throughput RSFQ Digital Circuits
- Comparisons of Synchronous-Clocking SFQ Adders
- Pipelined Bipartite Modular Multiplication
- Pipelined Bipartite Modular Multiplication
- Hardware Algorithm for Computing Reciprocal of Euclidean Norm of a 3-D Vector(VLSI Design Technology and CAD)
- Pipelined Bipartite Modular Multiplication
- Pipelined Bipartite Modular Multiplication
- Fast Modular Multiplication by Processing the Multiplier from Both Sides in Parallel
- Fast Modular Multiplication by Processing the Multiplier from Both Sides in Parallel
- Layout-Driven Skewed Clock Tree Synthesis for Superconducting SFQ Circuits
- Fast Modular Multiplication by Processing the Multiplier from Both Sides in Parallel
- A Multiple-Precision Modular Multiplication Algorithm with Triangle Additions
- A Hardware Algorithm for Modular Division Based on the Extended Euclidean Algorithm
- A Digit-Recurrence Algorithm for Cube Rooting
- A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm(VLSI Design Technology and CAD)
- A VLSI Architecture with Multiple Fast Store-Based Block Parallel Processing for Output Probability and Likelihood Score Computations in HMM-Based Isolated Word Recognition