Matching-Based Algorithm for FPGA Channel Segmentation Design
Resource
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 20 (6): 784-791
Journal
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Journal Volume
20
Journal Issue
6
Pages
784-791
Date Issued
2001
Date
2001
Author(s)
Abstract
Process technology advances have made multimillion gate field programmable gate arrays (FPGAs) a reality. A key issue that needs to be solved in order for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. Channel segmentation designs have been studied to some degree in much of the literature; the previous methods are based on experimental studies, stochastic models, or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a problem of finding the optimal segmentation architecture for two input routing instances and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient multilevel matching-based algorithm for general channel segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work.
Subjects
Detailed routing; Interconnect; Layout; Physical design; Routing
Other Subjects
Algorithms; Computer simulation; Graph theory; Interconnection networks; Logic design; Polynomials; Random processes; Theorem proving; Channel segmentation design; Graph theoretic formula; Matching based algorithm; Multilevel matching based algorithm; Polynomial time optimal algorithm; Field programmable gate arrays
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
07.pdf
Size
287.37 KB
Format
Adobe PDF
Checksum
(MD5):bad09fea86e07a06353b5a476af391cb