ACM Transactions on Design Automation of Electronic Systems · 2004 · 22 citations · 18 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsField-programmable Gate ArraysReconfigurable ComputingField-programmable Gate Array ArchitectureFpga ArchitectureProgrammable Logic DevicesRoutingRouting AlgorithmsRouting ArchitectureBoolean EquationsBoolean MinimizationBoolean SatisfiabilityBoolean Satisfiability ProblemCircuit SatisfiabilityConstraintsRouting Constraint SatisfactionRouting In Field-programmable Gate Arrays
Segmented channel routing is fundamental to the routing of row-based FPGAs. In this paper, we study segmented channel routability via satisfiability. Our method encodes the horizontal and vertical constraints of the routing problem as Boolean conditions. The routability constraint is satisfiable if and only if the net connections in the segmented channel are routable. Empirical results show that the method is time-efficient and applicable to large problem instances.
18
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
Efficient Conflict Driven Learning in a Boolean Satisfiability Solver
2001 · 666 citations