ASP-DAC 2004: Asia and South Pacific Design Automation Conference 2004 (IEEE Cat. No.04EX753) · 2004 · 46 citations · 21 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureDesign AutomationDesign OptimizationFpga ArchitectureHigh-level SynthesisRegister AllocationRoutingRouting ArchitectureVery-large-scale Integration LayoutBipartite MatchingHigh-level Synthesis RoutingMultiplexer DesignNp-complete ProblemsPlacement AlgorithmsPower ConsumptionPower Consumption OptimizationVlsi Implementation
Data path connection elements, such as multiplexers, consume a significant amount of area on a VLSI chip, especially for FPGA designs. Multiplexer optimization is a difficult problem because both register binding and port assignment to reduce total multiplexer connectivity during high-level synthesis are NP-complete problems. We first formulate a k-cofamily-based register binding algorithm targeting the multiplexer optimization problem. We then further reduce the multiplexer width through an efficient port assignment algorithm. Experimental results show that we are 44% better overall than the left-edge register binding algorithm on the total usage of multiplexer inputs and 7% better than a bipartite graph-based algorithm. For large designs, we are able to achieve significantly better results consistently. After technology mapping, placement and routing for an FPGA architecture, it shows considerably positive impacts on chip area, delay and power consumption.
21
Synthesis and optimization of digital circuits
Choice Reviews Online · 1994 · 2.4K citations
Engineering, Computer Engineering, Electrical Engineering +17
A Decomposition Theorem for Partially Ordered Sets
R. P. Dilworth · Annals of Mathematics · 1950 · 987 citations