Penn Logo
Vertical Line

Implementation of Computation Group


Location, Location, Location---The Role of Spatial Locality in Asymptotic Energy Minimization

André DeHon
Proceedings of the International Symposium on Field-Programmable Gate Arrays, pp. 137--146, (FPGA2013, February 11--13, 2013)

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, Inc. 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).

Room# 315, 200 South 33rd Street, Electrical and Systems Engineering Department, Philadelphia, University of Pennsylvania, PA 19104.