Transforming gate-level Boolean logic into functionally equivalent lookup tables (LUTs) is a key step in the compilation of a design into field-programmable gate arrays (FPGAs). Tools typically deploy a sequence of logic optimizations, with an aim to accomplish a mapping that minimizes the total LUT count and the depth of the longest logic path.

The authors start with two important observations. One is that the “fixed predetermined sequence of ... logic transformations” in the tools may not always produce “high-quality logic structures,” as different sequences of transformations work better in different designs. The second observation is that merely improving the logic structure does “not necessarily translate to reduced LUT count or depth.”

With these limitations in mind, Liu and Zhang propose a “parallelized iterative improvement” approach to LUT mapping (PIMap). Here, the mapping results are used to guide a series of randomly selected structural optimizations iteratively. To overcome the runtime overhead of the approach, the framework offers techniques to decompose the larger netlist into smaller sub-netlists, which can be optimized in parallel.

The paper is organized well, starting with a concise overview of the existing methods and how PIMap compares to them. After briefly presenting experimental results on an arithmetic benchmark that show the correlation between gate count and LUT count when the optimization objective is varied, the authors suggest that across several designs, using a single objective alone limits the quality of the mapping, and can be further improved by switching to the second objective. It forms a motivation for the PIMap flow, which the rest of the paper describes in depth.

Though the various underlying pieces of the approach are already known, the authors organize those into a new scheme that can be effective and potentially produce better results. Since the proposed methods use random selection, reproducing the same result from one run to another can be a challenge. The sizes of the designs used in the results section are tiny when compared to modern designs; it is not clear how the approach scales with size and requires further experimentation.

Overall, the paper will be of interest to industrial practitioners as well as researchers in the domain.