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

doi:10.1109/TVLSI.2008.2000677

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 journal › Article › peer-review

9 Citations (Scopus)

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 language	English
Pages (from-to)	1210-1219
Number of pages	10
Journal	IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume	16
Issue number	9
DOIs	https://doi.org/10.1109/TVLSI.2008.2000677
Publication status	Published - 1 Sept 2008

Keywords

field-programmable gate arrays
defragmentation
modules

Access to Document

10.1109/TVLSI.2008.2000677

Cite this

@article{348d73f292224103b59ecd1830676f34,

title = "Offline and online aspects of defragmenting the module layout of a partially reconfigurable device",

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.",

keywords = "field-programmable gate arrays, defragmentation, modules",

author = "Sandor Fekete and {van der Veen}, Jan and Ali Ahmadinia and Diana Gohringer and Mateusz Majer and Jurgen Teich",

note = "<p>Originally published in: IEEE Transactions on Very Large Scale Integration (VLSI) Systems (2008), 16 (9), pp.1210-1219.</p>",

year = "2008",

month = sep,

day = "1",

doi = "10.1109/TVLSI.2008.2000677",

language = "English",

volume = "16",

pages = "1210--1219",

journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "9",

}

TY - JOUR

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

AU - Fekete, Sandor

AU - van der Veen, Jan

AU - Ahmadinia, Ali

AU - Gohringer, Diana

AU - Majer, Mateusz

AU - Teich, Jurgen

N1 - <p>Originally published in: IEEE Transactions on Very Large Scale Integration (VLSI) Systems (2008), 16 (9), pp.1210-1219.</p>

PY - 2008/9/1

Y1 - 2008/9/1

N2 - 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.

AB - 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.

KW - field-programmable gate arrays

KW - defragmentation

KW - modules

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-50549090198&partnerID=8YFLogxK

U2 - 10.1109/TVLSI.2008.2000677

DO - 10.1109/TVLSI.2008.2000677

M3 - Article

VL - 16

SP - 1210

EP - 1219

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IS - 9

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this