A Theoretical Investigation on CMOL FPGA Cell Assignment Problem

The hybrid CMOS/nano circuits (CMOL) field-programmable gate array (FPGA) is a promising nanotechnology that has the potential to be accepted by industry in the future. However, a primary question to be addressed is whether or not all circuits can be mapped on CMOL architecture. In contrast to traditional placement and routing problems, CMOL cell assignment has the constraint that each gate can only be wired to a limited number of gates in its neighborhood. Under such a restriction, not all circuits are directly placeable. This paper presents two theoretical results concerning whether a combinatorial circuit is placeable in CMOL FPGA. For any finite connection domain, we prove the existence of a few nonplaceable circuits under certain conditions. Given a reasonable connection domain size, we show that any combinatorial circuit can be transformed to an equivalent circuit which is placeable. These results conclude that the CMOL cell assignment problem is solvable but circuit modification has to be part of the placement procedure.