Efficient Addition on Field Programmable Gate Arrays

摘要

We investigate average efficient adders for grid-based environments related to current Field Programmable Gate Arrays (FPGAs) and VLSI-circuits. Motivated by current trends in FPGA hardware design we introduce a new computational model, called the A -wired grid model. The parameter A describes the degree of connectivity of the underlying hardware. This model covers among others two-dimensional cellular automata for λ = 0 and VLSI-circuits for λ = 1. To formalize input and output constraints of such circuits we use the notion of input and output schemas. It turns out that the worst case time and area complexity are highly dependent on the specific choice of I/O schemas. We prove that a set of regular schemas supports efficient algorithms for addition where time and area bounds match lower bounds of a broad class of I/O schemas. We introduce new schemas for average efficient addition on FPGAs and show that addition can be done in expected time O(log log n) for the standard VLSI model and in expected time O((logn)~(2/1)) in the pure grid model. Furthermore, we investigate the rectangular area needed to perform addition with small error probability, called area with high probability. Finally, these results are generalized to the class of prefix functions.