Offline and online aspects of defragmenting the module layout of a partially reconfigurable device

Sandor Fekete, Jan van der Veen, Ali Ahmadinia, Diana Gohringer, Mateusz Majer, Jurgen Teich

    Research output: Contribution to journalArticle

    Abstract

    Modern generations of field-programmable gate arrays (FPGAs) allow for partial reconfiguration. In an online context, where the sequence of modules to be loaded on the FPGA is unknown beforehand, repeated insertion and deletion of modules leads to progressive fragmentation of the available space, making defragmentation an important issue. We address this problem by proposing an online and an offline component for the defragmentation of the available space. We consider defragmenting the module layout on a reconfigurable device. This corresponds to solving a 2D strip packing problem. Problems of this type are NP-hard in the strong sense, and previous algorithmic results are rather limited. Based on a graph-theoretic characterization of feasible packings, we develop a method that can solve 2D defragmentation instances of practical size to optimality. Our approach is validated for a set of benchmark instances.

    Original languageEnglish
    Pages (from-to)1210-1219
    Number of pages10
    JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
    Volume16
    Issue number9
    DOIs
    Publication statusPublished - 1 Sep 2008

    Keywords

    • field-programmable gate arrays
    • defragmentation
    • modules

    Fingerprint Dive into the research topics of 'Offline and online aspects of defragmenting the module layout of a partially reconfigurable device'. Together they form a unique fingerprint.

  • Cite this