Board-level multiterminal net assignment for the partial cross-bar architecture

Author

Song, Xiaoyu ; Hung, William N N ; Mishchenko, Alan ; Chrzanowska-Jeske, Malgorzata ; Kennings, Andrew ; Coppola, Alan

Author_Institution

Dept. of Electr. & Comput. Eng., Portland State Univ., OR, USA

Volume

11

Issue

3

fYear

2003

fDate

6/1/2003 12:00:00 AM

Firstpage

511

Lastpage

514

Abstract

This paper presents a satisfiability-based method for solving the board-level multiterminal net routing problem in the digital design of clos-folded field-programmable gate array (FPGA) based logic emulation systems. The approach transforms the FPGA board-level routing task into a Boolean equation. Any assignment of input variables that satisfies the equation specifies a valid routing. We use two of the fastest Boolean satisfiability (SAT) solvers: Chaff and DLMSAT to perform our experiments. Empirical results show that the method is time-efficient and applicable to large layout problem instances.

Keywords

Boolean algebra; computability; field programmable gate arrays; logic CAD; multiterminal networks; network routing; Boolean satisfiability; Chaff; DLMSAT; board-level multiterminal net routing; circuit layout; clos-folded field programmable gate array; digital design; logic emulation; partial cross-bar architecture; Emulation; Engines; Equations; Field programmable gate arrays; Logic arrays; Logic design; Pins; Reconfigurable logic; Routing; Very large scale integration;

fLanguage

English

Journal_Title

Very Large Scale Integration (VLSI) Systems, IEEE Transactions on

Publisher

ieee

ISSN

1063-8210

Type

jour

DOI

10.1109/TVLSI.2003.812322

Filename

1218223