Boolean Matching for Complex PLBs in LUT-based FPGAs with Application to Architecture Evaluation

In this project, we study new Boolean matching techniques for complex programmable logic blocks (PLBs) in LUT-based FPGAs. A complex PLB consists of interconnected LUTs (possibly of different sizes) and logic gates.

Each PLB can be configured not only as a K-input LUT but also to implement some wide functions of more than K inputs. Our Boolean matching techniques includes simple disjoint decomposition, bi-decomposition, partially-dependent decomposition, and Shannon expansion. Applying these techniques, we fully characterize functions for the XC4000 CLB and the XC5200 CLB in the Xilinx FPGA family.

We evaluate four PLB architectures based on their capabilities on implementing functions of up to 7 inputs extracted from MCNC benchmarks. Experiments show that the XC4000 CLB can implement up to 98% of 6-input functions and 88% of 7-input functions, while two of the other three PLB architectures have a smaller cost in terms of logic capability per silicon area.

Cong, J., Y. Hwang "Boolean Matching for Complex PLBs in LUT based FPGAs with Application to Architecture Evaluation" Proc. ACM International Symposium on FPGA, Monterey, CA., Feb. 1998, pp. 27-34.