Locality exploitation is essential to asymptotic energy minimization for
gate array netlist
evaluation. Naive implementations
that ignore locality, including flat crossbars and simple processors based
on monolithic memories, can require
O(N2) energy for an N node graph.
Specifically, it is important to exploit locality (1) to reduce
the size of the description of the graph, (2) to reduce data movement, and
(3) to reduce instruction movement. FPGAs exploit all three. FPGAs with a
Rent Exponent p<0.5 running designs with p<0.5 achieve
asymptotically optimal θ(N) energy. FPGA designs with p>0.5 and
implementations with metal
layers that grow as O(Np-0.5) require only O(Np+0.5) energy; this
bound can be achieved with O(1) metal layers with a novel
multicontext design that has heterogeneous context depth. In contrast, a
p>0.5 FPGA design on an implementation technology with O(1) metal layers
requires O(N2p) energy.
Copyright 2013 ACM,
This is the author's version of the work. It is posted here by permission
of ACM for your personal use. Not for redistribution. The definitive
version was published in the Proceedings of the
International Symposium on Field-Programmable Gate Arrays,
(FPGA2013, February 11--13 2013).