Efficient allocation of FPGA area to multiple users in an operating system for reconfigurable computing

Reconfigurable computing allows field programmable gate arrays (FPGA) to form a platform for development of hardware circuits which have been traditionally custom manufactured as application specific integrated circuits (ASIC). Reconfigurable computing allows applications to execute in hardware which were previously implemented inefficiently in software because they could not be implemented in ASICs due to cost overheads. In order to support a software orientated development process for reconfigurable computing, we believe that a suitable operating system should be provided. The primary shared resource of the reconfigurable architecture is the FPGA area. A major service that must be provided by an operating system is the allocation of the FPGA area among different tasks. This contrasts with the need in a traditional OS to allocate the CPU to different tasks by time slicing. This paper describes three algorithms that can be used to perform this area allocation. The major requirements of such algorithms are that they execute in reasonable time and that the make the best use of the available area on the FPGA. In particular we are concerned that the algorithms do not fragment the FPGA area. If a large percentage of the FPGA area becomes unusable because the available remaining space is divided into disjoint sections, none of which are large enough to host any task, we say the area is fragmented. We show that an algorithm based on the Minkowski Sum strikes a good balance between fragmentation and execution time. The possible problem of a slow kernel (inner loop) of the Minkowski Sum algorithm can be overcome by executing parts of the kernel on the FPGA surface itself