Fast Boolean matching for field-programmable gate arrays

Kai Zhu, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A key step in technology mapping for non lookup-table (such as multiplexor) based FPGAs 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. Comparing to the matching algorithm by searching for isomorphism on all different BDDs, the new algorithm is much faster with a modest increase of memory requirement.

Original languageEnglish (US)
Title of host publicationEuropean Design Automation Conference - Proceedings
Editors Anon
PublisherPubl by IEEE
Pages352-357
Number of pages6
ISBN (Print)0818643528
StatePublished - Dec 1 1993
Externally publishedYes

Publication series

NameEuropean Design Automation Conference - Proceedings

Fingerprint

Field programmable gate arrays (FPGA)
Binary decision diagrams
Table lookup
Data storage equipment

ASJC Scopus subject areas

  • Control and Systems Engineering

Cite this

Zhu, K., & Wong, D. F. (1993). Fast Boolean matching for field-programmable gate arrays. In Anon (Ed.), European Design Automation Conference - Proceedings (pp. 352-357). (European Design Automation Conference - Proceedings). Publ by IEEE.

Fast Boolean matching for field-programmable gate arrays. / Zhu, Kai; Wong, D. F.

European Design Automation Conference - Proceedings. ed. / Anon. Publ by IEEE, 1993. p. 352-357 (European Design Automation Conference - Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Zhu, K & Wong, DF 1993, Fast Boolean matching for field-programmable gate arrays. in Anon (ed.), European Design Automation Conference - Proceedings. European Design Automation Conference - Proceedings, Publ by IEEE, pp. 352-357.
Zhu K, Wong DF. Fast Boolean matching for field-programmable gate arrays. In Anon, editor, European Design Automation Conference - Proceedings. Publ by IEEE. 1993. p. 352-357. (European Design Automation Conference - Proceedings).
Zhu, Kai ; Wong, D. F. / Fast Boolean matching for field-programmable gate arrays. European Design Automation Conference - Proceedings. editor / Anon. Publ by IEEE, 1993. pp. 352-357 (European Design Automation Conference - Proceedings).
@inproceedings{b776d6f0544944d890f99cca4e0dd5e0,
title = "Fast Boolean matching for field-programmable gate arrays",
abstract = "A key step in technology mapping for non lookup-table (such as multiplexor) based FPGAs 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. Comparing to the matching algorithm by searching for isomorphism on all different BDDs, the new algorithm is much faster with a modest increase of memory requirement.",
author = "Kai Zhu and Wong, {D. F.}",
year = "1993",
month = "12",
day = "1",
language = "English (US)",
isbn = "0818643528",
series = "European Design Automation Conference - Proceedings",
publisher = "Publ by IEEE",
pages = "352--357",
editor = "Anon",
booktitle = "European Design Automation Conference - Proceedings",

}

TY - GEN

T1 - Fast Boolean matching for field-programmable gate arrays

AU - Zhu, Kai

AU - Wong, D. F.

PY - 1993/12/1

Y1 - 1993/12/1

N2 - A key step in technology mapping for non lookup-table (such as multiplexor) based FPGAs 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. Comparing to the matching algorithm by searching for isomorphism on all different BDDs, the new algorithm is much faster with a modest increase of memory requirement.

AB - A key step in technology mapping for non lookup-table (such as multiplexor) based FPGAs 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. Comparing to the matching algorithm by searching for isomorphism on all different BDDs, the new algorithm is much faster with a modest increase of memory requirement.

UR - http://www.scopus.com/inward/record.url?scp=0027886698&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027886698&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027886698

SN - 0818643528

T3 - European Design Automation Conference - Proceedings

SP - 352

EP - 357

BT - European Design Automation Conference - Proceedings

A2 - Anon, null

PB - Publ by IEEE

ER -