FPGA Defragmentation for Sustainable Performance in Reconfig

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 represent …… 此处隐藏：5765字，全部文档内容请下载后查看。喜欢就下载吧 ……