Allocation heuristics and defragmentation measures for reconfigurable systems management

A novel technique is proposed for the management of a 2D reconfigurable device in order to get true hardware multitasking. We use a Vertex List Set to keep track of the free area boundary. This structure contains the best candidate locations for the task, and several heuristics are proposed to select one of them, based in fragmentation and adjacency. A Look-Ahead heuristic that anticipates the next known event is also proposed. A metric is used to estimate the fragmentation status of the FPGA, based on the number of holes and their shape. Defragmentation measures are taken when needed.