An FPGA task allocator with preliminary First-Fit 2D packing algorithms
Chuan Hong, Khaled Benkrid, Xabier Iturbe, Ahmet T. Erdogan, Tughrul Arslan · 2011
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.