An efficient algorithm for finding empty space for online FPGA placement

• Main Authors: Handa, Manish, Vemuri, Ranga
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm design and analysis; Application software; Applied computing > Arts and humanities > Architecture (buildings) > Computer-aided design; Applied computing > Physical sciences and engineering > Engineering > Computer-aided design; Applied sciences; Circuit properties; Design engineering; Design. Technologies. Operation analysis. Testing; Digital circuits; Electric, optical and optoelectronic circuits; Electronic circuits; Electronics; Exact sciences and technology; Field programmable gate arrays; Hardware > Electronic design automation > Physical design (EDA) > Placement; Hardware > Electronic design automation > Physical design (EDA) > Wire routing; Integrated circuit interconnections; Integrated circuits; Permission; Programmable logic arrays; Reconfigurable logic; Routing; Runtime; Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices
• ISSN: 0738-100X
• DOI: 10.1145/996566.996820

A fast and efficient algorithm for finding empty area is necessary for online placement, task relocation and defragmentation on a partially reconfigurable FPGA. We present an algorithm that finds empty area as a list of overlapping maximal rectangles. Using an innovative representation of the FPGA, we are able to predict possible locations of the maximal empty rectangles. Worst-case time complexity of our algorithm is O(xy) where x is the number of columns, y is the number of rows and x.y is the total number of cells on the FPGA. Experiments show that, in practice, our algorithm needs to scan less than 15% of the FPGA cells to make a list of all maximal empty rectangles.