Fast Boolean matching for field-programmable gate arrays

Kai Zhu; D.F. Wong

doi:10.1109/EURDAC.1993.410661

Fast Boolean matching for field-programmable gate arrays

Kai Zhu, D.F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding

8 Citations (Scopus)

Abstract

A key step in technology mapping for non-lookup-table (such as multiplexer) based FPGAs (field programmable gate arrays) is to determine whether a given function can be implemented by the logic module. A new algorithm is presented for solving this problem. The algorithm is based on a character string representation of binary decision diagrams. Such representation leads to a matching algorithm which requires only a few string comparisons for each matching operation. When compared to the matching algorithm by searching for isomorphism on all different BDDs (binary decision diagrams), the new algorithm is much faster with a modest increase of memory requirement. For example, the experimental results showed that in matching all three-input Boolean function against Actel's ACT1 logic module, the new algorithm is 634 times faster by using 19.9% more memory.

Original language	English
Title of host publication	Proceedings of EURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference
Publisher	IEEE
Pages	352-357
Number of pages	6
ISBN (Print)	0818643501
DOIs	https://doi.org/10.1109/EURDAC.1993.410661
Publication status	Published - 24 Sept 1993
Event	EURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference - Hamburg, Germany Duration: 20 Sept 1993 → 24 Sept 1993 https://ieeexplore.ieee.org/xpl/conhome/3227/proceeding

Publication series

Name	European Design Automation Conference

Conference

Conference	EURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference
Country/Territory	Germany
City	Hamburg
Period	20/09/93 → 24/09/93
Internet address	https://ieeexplore.ieee.org/xpl/conhome/3227/proceeding

User-Defined Keywords

Field programmable gate arrays
Boolean functions
Data structures
Clustering algorithms
Logic arrays
Libraries
Logic functions
Boolean algebra
Pins
Logic gates

Access to Document

10.1109/EURDAC.1993.410661

Cite this

@inproceedings{4cd00e3da0a24fff8f96b28d932a0908,

title = "Fast Boolean matching for field-programmable gate arrays",

abstract = "A key step in technology mapping for non-lookup-table (such as multiplexer) based FPGAs (field programmable gate arrays) is to determine whether a given function can be implemented by the logic module. A new algorithm is presented for solving this problem. The algorithm is based on a character string representation of binary decision diagrams. Such representation leads to a matching algorithm which requires only a few string comparisons for each matching operation. When compared to the matching algorithm by searching for isomorphism on all different BDDs (binary decision diagrams), the new algorithm is much faster with a modest increase of memory requirement. For example, the experimental results showed that in matching all three-input Boolean function against Actel's ACT1 logic module, the new algorithm is 634 times faster by using 19.9% more memory.",

keywords = "Field programmable gate arrays, Boolean functions, Data structures, Clustering algorithms, Logic arrays, Libraries, Logic functions, Boolean algebra, Pins, Logic gates",

author = "Kai Zhu and D.F. Wong",

year = "1993",

month = sep,

day = "24",

doi = "10.1109/EURDAC.1993.410661",

language = "English",

isbn = "0818643501",

series = "European Design Automation Conference",

publisher = "IEEE",

pages = "352--357",

booktitle = "Proceedings of EURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference",

address = "United States",

note = "EURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference ; Conference date: 20-09-1993 Through 24-09-1993",

url = "https://ieeexplore.ieee.org/xpl/conhome/3227/proceeding",

}

TY - GEN

T1 - Fast Boolean matching for field-programmable gate arrays

AU - Zhu, Kai

AU - Wong, D.F.

PY - 1993/9/24

Y1 - 1993/9/24

N2 - A key step in technology mapping for non-lookup-table (such as multiplexer) based FPGAs (field programmable gate arrays) is to determine whether a given function can be implemented by the logic module. A new algorithm is presented for solving this problem. The algorithm is based on a character string representation of binary decision diagrams. Such representation leads to a matching algorithm which requires only a few string comparisons for each matching operation. When compared to the matching algorithm by searching for isomorphism on all different BDDs (binary decision diagrams), the new algorithm is much faster with a modest increase of memory requirement. For example, the experimental results showed that in matching all three-input Boolean function against Actel's ACT1 logic module, the new algorithm is 634 times faster by using 19.9% more memory.

AB - A key step in technology mapping for non-lookup-table (such as multiplexer) based FPGAs (field programmable gate arrays) is to determine whether a given function can be implemented by the logic module. A new algorithm is presented for solving this problem. The algorithm is based on a character string representation of binary decision diagrams. Such representation leads to a matching algorithm which requires only a few string comparisons for each matching operation. When compared to the matching algorithm by searching for isomorphism on all different BDDs (binary decision diagrams), the new algorithm is much faster with a modest increase of memory requirement. For example, the experimental results showed that in matching all three-input Boolean function against Actel's ACT1 logic module, the new algorithm is 634 times faster by using 19.9% more memory.

KW - Field programmable gate arrays

KW - Boolean functions

KW - Data structures

KW - Clustering algorithms

KW - Logic arrays

KW - Libraries

KW - Logic functions

KW - Boolean algebra

KW - Pins

KW - Logic gates

UR - https://ieeexplore.ieee.org/document/410661/

U2 - 10.1109/EURDAC.1993.410661

DO - 10.1109/EURDAC.1993.410661

M3 - Conference proceeding

SN - 0818643501

T3 - European Design Automation Conference

SP - 352

EP - 357

BT - Proceedings of EURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference

PB - IEEE

T2 - EURO-DAC 93 and EURO-VHDL 93- European Design Automation Conference

Y2 - 20 September 1993 through 24 September 1993

ER -

Fast Boolean matching for field-programmable gate arrays

Abstract

Publication series

Conference

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this