Module Placement on FPGAs: Online FPGATris

When FPGAs (Field Programmable Gate Arrays) are reconfigured at runtime, module placement positions have to be determined. In the case of a two-dimensional layout of the reconfigurable chip, the packing problem has three dimensions when considering the execution time of the modules. This problem can be seen as solving a 3-D version of the game Tetris. Modules (our Tetris bricks) posses an arbitrary shaped groundplane and a height corresponding to their execution time. The task is to pack a random sequence of modules onto a two dimensional ground plane (the FPGA) such that the total execution time (the height of all the packed modules) is minimized.