Title :
Fast Boolean matching for field-programmable gate arrays
Author :
Zhu, Kai ; Wong, D.F.
Author_Institution :
Dept. of Comput. Sci., Texas Univ., Austin, TX, USA
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 :
Boolean functions; computational complexity; field programmable gate arrays; logic CAD; logic design; programmable logic arrays; Actel´s ACT1 logic module; Boolean matching; FPGAs; binary decision diagrams; character string representation; field-programmable gate arrays; matching algorithm; memory requirement; multiplexer; technology mapping; three-input Boolean function; Boolean algebra; Boolean functions; Clustering algorithms; Data structures; Field programmable gate arrays; Libraries; Logic arrays; Logic functions; Logic gates; Pins;
Conference_Titel :
Design Automation Conference, 1993, with EURO-VHDL '93. Proceedings EURO-DAC '93., European
Conference_Location :
Hamburg
Print_ISBN :
0-8186-4350-1
DOI :
10.1109/EURDAC.1993.410661
