Board Allocation Algorithm for the Resource Management System of FiC

When using FPGA clusters for Multi-access Edge Computing (MEC), some tasks need multiple FPGA boards, so it is necessary to allocate each task to several boards that are not currently in use on the FPGA cluster. In order to maintain constant communication bandwidth and latency, we should allocate them in contiguous areas of a group of FPGAs. The current task allocation method for our FPGA clusters searches for Maximum Empty Rectangles (MER) based on Scan Line Algorithm (SLA). However, in this algorithm, the allocation target is restricted to a rectangular shape, which makes the cluster utilization inefficient. In this paper, we devise a more flexible algorithm called Non-Rectangular (NR) allocation and attempt to improve allocation efficiency. NR allocation provides the hybrid method, which chooses column-major allocation and row-major allocation. By using this proposed hybrid method, we have made it possible to allocate non-rectangular areas while maintaining contiguous regions by considering the board's position after allocation. Simulation results show a 42% improvement in the total waiting time compared to the conventional method.