FPGA Defragmentation for Sustainable Performance in Reconfig(2)

Abstract ? Defragmentation is a fundamental resource management service allowing Reconfigurable Computing Systems (RCSs) to efficiently utilize resources when tasks are dispatched dynamically. Only well orchestrated interactions between these three compone

insights on the interplay between defragmentation, occupies a single cell. In this case, placement and scheduling. NN

22The paper is organized as a =1 1.

F1f1= = ∏i∏ N

i=1i=1 A N()III. QUANTIFYING DEFGRAMENTATION

One can view the reconfigurable fabric of an

Although F does not reach exactly 1 as shown, it FPGA chip as a square area containing an array of

2

2

2

smaller empty square areas called cells. In the context of FPGA chips, cells are equivalent to reconfigurable logic blocks (CLBs). Figure 2 shows tasks T1 and T2 occupying two and six cells respectively. The incoming task T3, consisting of six cells, cannot be placed on the chip although there is sufficient room left on the FPGA.

A) Fragmentation Factor

Let a and A be the area of a single empty cell and the entire chip respectively. Let N x N be the number of cells in an FPGA chip. Assume that a hole i consists of k cells. This hole yields a fragmentation factor

f=1kA∑

a=kak

i2=j=1

NaN2.

B) Fragmentation Metric Since the factor fk

i=N

2gets smaller as many cells are

made empty in the chip, it is scaled to reflect maximum fragmentation by subtracting it from 1 as F=1 ∏fi . F represents the fragmentation metric

i

of the FPGA chip at any moment.

C) Lowest Possible Fragmentation

An empty chip represents the lowest possible degree of fragmentation. In an empty chip, there is only a single empty area consisting of one hole whose area is N2a. In

1

this case, F=1 ∏f N2a i =1 f1=1 2 =0.

i=1 Na

D) Highest Possible Fragmentation

A highly fragmented chip resembles the checkerboard layout shown in Figure 3. Assuming N is even, the 2

number of holes in the chip is

N

2

where each hole

nevertheless approaches 1 as N gets larger. While this fragmentation metric is similar to the one proposed in [1], its semantics are totally different. Given this formulation of the fragmentation metric, any event that modifies the state of the reconfigurable fabric of the

chip can affect the value of F. Events which can do so consist of placing a task on the chip, purging a task from the chip, or moving a task from location to location on the chip. As a result, it is the responsibility of the placement and defragmentation process to constantly update F when these events are witnessed.

REFERENCES

[1] J. Tabero, J. Septien, H. Mecha, D. Mozos, and S. Roman, "Efficient Hardware Multitasking through Space Multiplexing in 2D RTR FPGAs," Euromicro Digital System Design

Conference, September 2003. [2] G. Wigley and D. Kearney, "The management of Applications

for Reconfigurable Computing Using an Operating System," The 7th Asia-Pacific Conference on Computer System Archicture, 2002, pp. 73-81. [3] G. Wigley and D. Kearney, "The First Real Operating System

for Reconfigurable Computers," Australian Computer Systems

Architecture Conference, Goaldcoast, Queensland, Australia,

2000, pp. 129-136.

[4] O. Diessel and G. Wigley, "Opportunities for Operating Systems

Research in Reconfigurable Computing," University of South Australia ACRC-99-018, Aug. 1999, available at .

[5] H. Walder, C. Steiger, and M. Platzner, "Fast Online Task

Placement on FPGAs: Free Space Partitioning and 2D-Hashing," International Parallel and Distributed Processing Symposium, April 2003.

[6] H. Walder and M. Platzner, "Non-preemptive Multitasking on

FPGAs: Task Placement and Footprint Transform," The 2nd International Conference on Engineering of Reconfigurable Systems and Architectures, June 2002, pp. 24-30.

[7] M. Handa and R. Vemuri, "An Efficient Algorithm for Finding

Empty Space for Online FPGA Placement," Design Automation Conference, San Diego, CA, June 2004, pp. 960-965.

[8] H. Walder and M. Platzner, "Online Scheduling for

Blockpartitioned Reconfigurable Devices," Design, Automation and Test in Europe, Mar. 2003, pp. 290-295.

[9] M. Handa and R. Vemuri, "Area Fragmentation in

Reconfigurable Operating Systems," Engineering of Reconfigurable Systems and Algorithms, Las Vegas, NV, June 2004.

[10] M. G. Gericota, G. R. Alves, M. L. Silva, and J. M. Ferreira,

"Run-Time Management of Logic Resources on Reconfigurable Systems," Design Automation and Test in Europe, March 2003, pp. 974-979.