Resource Allocation for Hardware Implementations of Map

The map operation, in which a function is applied indepen-dently to each element in a collection to produce a new col-lection, appears in many settings and is easy to parallelize. While a straightforward implementation in hardware will consist of multiple functional units with buffers to balance variable execution times, the best trade-off between these two components is not obvious. Too many buffers wastes re-sources that could otherwise perform computation; too few buffers causes functional units to lie idle waiting for empty buffers. Our work considers this abstract problem, derives worst-case workload distributions, then shows how to trade functional units for buffers to maximize throughput. Our re-sults can be used by designers and compilers alike to produce efficient parallel implementations of map. 1