Loading...
Please wait, while we are loading the content...
Similar Documents
A new FPGA detailed routing approach via search-based Boolean satisfiability (2002)
| Content Provider | CiteSeerX |
|---|---|
| Author | Nam, Gi-Joon Sakallah, Karem A. Rutenbar, Rob A. |
| Abstract | Abstract—Boolean-based routing methods transform the geo-metric FPGA routing task into a large but atomic Boolean func-tion with the property that any assignment of input variables that satisfies the function specifies a valid routing solution. Previous at-tempts at FPGA routing using Boolean methods were based on bi-nary decision diagrams which limited their scopes, because of size limitations, to only individual FPGA channels. Thus, FPGA layouts were decomposed into channel-wise slices that are handled sepa-rately, and those individual channel slices were stitched together later. In this paper, we present a new search-based satisfiability (SAT) FPGA detailed routing formulation that handles all chan-nels in an FPGA simultaneously. The formulation has the virtue that it considers all nets concurrently allowing higher degrees of freedom for each net, in contrast to the classical one-net-at-a-time approaches and is able to prove the unroutability of a given cir-cuit by demonstrating the absence of a satisfying assignment to the routing Boolean function. To demonstrate the effectiveness of this method, we first present comparative experimental results between integer linear programming (ILP)-based routing, which is an alter-native concurrent method, and SAT-based routing. We also present the first comparisons of search-based Boolean SAT routing results to other conventional routers and offer the first evidence that SAT methods can actually demonstrate the unroutability of a layout. Preliminary experimental results suggest that our approach com-pares very favorably with both the ILP-based approach and con-ventional FPGA routers. Index Terms—Boolean satisfiability, field programmable gate arrays, routing. I. |
| File Format | |
| Journal | IEEE Trans. Comput.-Aided Design Integr. Circuits Syst |
| Language | English |
| Publisher Date | 2002-01-01 |
| Access Restriction | Open |
| Subject Keyword | Search-based Boolean Satisfiability New Fpga Boolean Method New Search-based Satisfiability Ilp-based Approach Index Term Boolean Satisfiability Approach Com-pares Input Variable Sat-based Routing Satisfying Assignment Boolean Function Individual Channel Slice Geo-metric Fpga Valid Routing Solution Classical One-net-at-a-time Approach Search-based Boolean Sat First Evidence Present Comparative Experimental Result Atomic Boolean Func-tion Alter-native Concurrent Method Preliminary Experimental Result Conventional Router First Comparison Abstract Boolean-based Routing Method Sat Method Previous At-tempts Bi-nary Decision Diagram Integer Linear Programming Field Programmable Gate Array Con-ventional Fpga Router Size Limitation Channel-wise Slice Individual Fpga Channel |
| Content Type | Text |
| Resource Type | Article |
