FPGA Defragmentation for Sustainable Performance in Reconfig(2)
时间:2025-07-10
时间:2025-07-10
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.
…… 此处隐藏:2388字,全部文档内容请下载后查看。喜欢就下载吧 ……上一篇:教育随笔:怎样让学生自己批改作文
下一篇:DTS等格式的无损音乐刻录