Post-Placement Interconnect Entropy

We introduce the concept of post-placement interconnect entropy: the minimal number of bits required to describe a well-placed netlist, which has connection lengths distributed according to Rent's rule. The entropy is a function of the number N of cells in the netlist and the Rent exponent p. We derive an expression for the entropy per cell and show that it converges as N approaches infinity. The entropy provides an achievable lower bound on the number of configuration bits in a programmable logic device (PLD) or field-programmable gate array (FPGA)] and a useful measure of its routing flexibility. Specific numerical values are computed for practical situations. For example, any scalable FPGA composed of 4-input lookup table cells would require 31 configuration bits per cell. We compare this to the actual number of configuration bits in a standard FPGA architecture. We generalize the bound to dimensions higher than two, and show that for any p there is an optimal dimension that minimizes the bound.