FPGA Defragmentation for Sustainable Performance in Reconfigurable Computers

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

This document is an author-formatted work. The definitive version for citation appears as:

A. Ejnioui and R. F. DeMara, “ Area Reclamation Metrics for SRAM-based Reconfigurable Device,” in the Proceedings of The International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA’05), Las Vegas, Nevada, U.S.A, June 27 – 30, 2005.

FPGA Defragmentation for Sustainable Performance

in Reconfigurable Computers

A. Ejnioui and R. F. DeMara

Department of Electrical and Computer Engineering

University of Central Florida Orlando, Florida 32816-2450 U.S.A

Abstract Defragmentation is a fundamental system of an RCS provides services to support the resource management service allowing Reconfigurable dispatching of computation tasks to the FPGA chip in Computing Systems (RCSs) to efficiently utilize order to accelerate the running applications. These resources when tasks are dispatched dynamically. services consist of scheduling the tasks, placing the Only well orchestrated interactions between these tasks on the FPGA, and performing defragmentation if three components can sustain the highest possible task placement fails. In addition, the operating system performance level for applications running on these can provide services to control configuration swapping RCSs. While scheduling and placement have been in and out of the FPGA chip for the purpose of extensively studied, defragmentation and its impact on supporting task placement and defragmentation [4]. As overall system performance is still not well understood. the application continues its execution, tasks are added This paper quantifies factors related to and deleted in a dynamic fashion leaving ultimately the defragmentation that can affect performance in terms reconfigurable fabric of the chip highly fragmented. and provides upper and lower bounds on fragmentation during sustained execution. II. PREVIOUS WORK Several placement studies have been previously

undertaken in which different algorithmic approaches I. INTRODUCTION

The key to exploiting an RCS is the virtualization of for task placement are proposed [1, 5-7]. Regardless of hardware whereby the fabric of a reconfigurable device how efficient task placement can be, the reconfigurable can be reused ad-infinitum to execute many fabric will eventually reach an advanced fragmented computations concurrently subject only to area and state where task placement becomes extremely difficult. performance constraints. However, these achievements Unless the tasks already placed on the chip are moved required the involvement of highly skilled digital and compacted as fast as possible, task placement designers in compiling and mapping these applications cannot be performed, and subsequently application onto the reconfigurable resources of the RCS. Recently, performance cannot be sustained at the same level. To several efforts went into developing software reach this goal, defragmentation has to be performed in environments that ease the compiling process of the the most efficient manner without severely disrupting application on RCSs [1]. Other efforts went further by the progress of the application execution. In fact, proposing operating systems fitted to manage the defragmentation should aim at bringing the overall hardware resources of an RCS [2, 3]. While there are performance back up to its previous level before the arguments for and against the development of operating fragmentation of the FPGA chip has reached a severe systems for RCSs, their primary benefit stems from level. Whereas task scheduling [1, 8] and placement [1, their support for multi-tasking. Multi-tasking requires 7] [5, 6] have been studied in depth, no significant facilities to schedule and place the computational tasks studies have been published to understand the impact of onto the reconfigurable fabric of the FPGA chips defragmentation on application performance [9]. Such embedded within the RCS. In general, the operating studies could ultimately help in gaining meaningful

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.

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

Figure 2. Fragmentation of FPGA chip.

Figure 3. Fragmentation states with equal empty areas.

本文来源：https://www.bwwdw.com/article/0jlj.html