2004 · 10 citations · 3 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsField-programmable Gate ArraysReconfigurable ComputingConfigurable Logic BlocksField-programmable Gate Array ArchitectureFpga ArchitectureLayout OptimizationMemory Hierarchy OptimizationReconfigurable AcceleratorsArea OptimizationField-programmable Gate Arrays (Fpgas)Placement AlgorithmsPlacement ArchitectureWorst-case ComplexityWorst-case Optimization
In this paper, we present a fast algorithm for finding empty area on the FPGA surface with some rectangular tasks placed on it. We use a staircase datastructure to report the empty area in the form of a list of maximal empty rectangles. We model the FPGA surface using an innovative encoding scheme that improves runtime and reduces memory requirement of our algorithm. Worst-case time complexity of our algorithm is O(xy) where x is number of columns, y is number of rows and x.y is the total number of cells on the FPGA.
3
Mining for empty spaces in large data sets
Jeff Edmonds, Jarek Gryz, Dongming Liang et al. · Theoretical Computer Science · 2003 · 58 citations