An FPGA task allocator with preliminary First-Fit 2D packing algorithms

This paper presents a novel light footprint and fast execution allocator for dynamically placing hardware tasks onto partially-damaged and resource-limited FPGA chips. The aim of the allocator´s placement algorithm is to maximize the overall task acceptance rate in presence of spontaneously occurring faults in chip´s silicon. Towards this objective, a novel placement algorithm: Empty Area Compaction (EAC) with its preliminary version: First-Fit, is proposed. Additionally, a set of observations are presented, targeting on optimizing the algorithm and accelerating its execution time, in the case of two parameters: chip granularity and algorithm´s pipeline structure. Based on these, a First Fit allocator has been implemented on a low cost Xilinx PicoBlaze soft processor, accelerating the placement decision to be made within 10 μs.