Thumbnail
Access Restriction
Open

Author George, Martyn A. ♦ Pink, Mathew J. ♦ Kearney, David A. ♦ Wigley, Grant B.
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Fpga Area ♦ Execution Time ♦ Available Area ♦ Major Service ♦ Good Balance ♦ Reconfigurable Architecture ♦ Efficient Allocation ♦ Application Specific ♦ Disjoint Section ♦ Allows Field Programmable Gate Array ♦ Operating System ♦ Development Process ♦ Major Requirement ♦ Minkowski Sum Algorithm ♦ Hardware Circuit ♦ Large Percentage ♦ Traditional O ♦ Allows Application ♦ Different Task ♦ Inner Loop ♦ Minkowski Sum ♦ Possible Problem ♦ Fpga Surface ♦ Reasonable Time ♦ Area Allocation ♦ Reconfigurable Computing ♦ Slow Kernel ♦ Suitable Operating System
Description 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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2002-01-01
Publisher Institution In: Proceedings of Engineering of Reconfigurable Systems and Algorithms