More Web Proxy on the site http://driver.im/

article

Free access

An FPGA task placement algorithm using reflected binary gray space filling curve

Authors:

Senoj Joseph Olakkenghil,

K. BaskaranAuthors Info & Claims

International Journal of Reconfigurable Computing, Volume 2014

Article No.: 5, Page 5

https://doi.org/10.1155/2014/495080

Published: 01 January 2014 Publication History

PDF eReader Publisher Site

Abstract

With the arrival of partial reconfiguration technology, modern FPGAs support tasks that can be loaded in (removed from) the FPGA individually without interrupting other tasks already running on the same FPGA. Many online task placement algorithms designed for such partially reconfigurable systems have been proposed to provide efficient and fast task placement. A new approach for online placement of modules on reconfigurable devices, by managing the free space using a run-length based representation. This representation allows the algorithm to insert or delete tasks quickly and also to calculate the fragmentation easily. In the proposed FPGA model, the CLBs are numbered according to reflected binary gray space filling curve model. The search algorithm will quickly identify a placement for the incoming task based on first fit mode or a fragmentation aware best fit mode. Simulation experiments indicate that the proposed techniques result in a low ratio of task rejection and high FPGA utilization compared to existing techniques.

References

[1]

K. Bazargan, R. Kastner, and M. Sarrafzadeh, "Fast template placement for reconfigurable computing systems," IEEE Design and Test of Computers, vol. 17, no. 1, pp. 68-83, 2000.

Digital Library

[2]

H. Walder, C. Steiger, and M. Platzner, "Fast online task placement on FPGAs: free space partitioning and 2D-hashing," in Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS '03), p. 178, IEEE-CS Press, 2003.

Digital Library

[3]

A. Ahmadinia and J. Teich, "Speeding up on-line placement for Xilinx FPGA by reducing configuration overhead," in Proceedings of the International Conference on Very Large Scale Integration of System on Chip (VLSI-SoC '03), pp. 118-122, Bavaria, Germany, December 2003.

[4]

A. Ahmadinia, C. Bobda, M. Bednara, and J. Teich, "A new approach for on-line placement on reconfigurable devices," in Proceedings of the 18th International, Parallel and Distributed Processing Symposium (IPDPS '04), pp. 134-140, 2004.

[5]

A. Ahmadinia, C. Bobda, and J. Teich, "A dynamic scheduling and placement algorithm for reconfigurable hardware," in Proceedings of the International Conference on Architecture of Computing Systems (ARCS '04), pp. 125-139, 2004.

[6]

A. Ahmadinia, C. Bobda, S. P. Fekete, J. Teich, and J. C. van der Veen, "Optimal free-space management and routing-conscious dynamic placement for reconfigurable devices," IEEE Transactions on Computers, vol. 56, no. 5, pp. 673-680, 2007.

Digital Library

[7]

M. Handa and R. Vemuri, "An integrated online scheduling and placement methodology," in Proceedings of the International Conference on Field Programmable Logic and Application, pp. 444-453, Leuven, Belgium, August 2004.

[8]

M. Handa and R. Vemuri, "Area fragmentation in reconfigurable operating systems," in Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms, pp. 77-83, CSREA, June 2004.

[9]

M. Handa and R. Vemuri, "An efficient algorithm for finding empty space for online FPGA placement," in Proceedings of the 41st Design Automation Conference (DAC '04), pp. 960-965, June 2004.

Digital Library

[10]

J. Tabero, J. Septién, H. Mecha, and D. Mozos, "Task placement heuristic based on 3D-adjacency and look-ahead in reconfigurable systems," in Proceedings of the Asia and South Pacific Design Automation Conference, pp. 396-401, January 2006.

Digital Library

[11]

J. Tabero, J. Septién, H. Mecha, and D. Mozos, "A low fragmentation heuristics for task placement in 2D RTR hardware management," in Proceedings of the 14th International Conference on Field Programmable Logic and Application (FPL '04), Lecture Notes in Computer Science, pp. 241-250, Leuven, Belgium, September 2004.

[12]

J. Tabero, J. Septien, H. Mecha, and D. Mozos, "Vertex list approach to 2D HW multitasking management in RTR FPGAs," in Proceedings of the Conference on Design of Circuits and Integrated Systems (DCIS '03), pp. 545-550, Ciudad Real, Spain, November 2003.

[13]

M. Tomono, M. Nakanishi, S. Yamashita, K. Nakajima, and K. Watanabe, "A new approach to online FPGA placement," in Proceedings of the 40th Annual Conference on Information Sciences and Systems (CISS '06), pp. 145-150, Princeton, NJ, USA, March 2006.

[14]

C. Jin, D. Qingxu, H. Xiuqiang, and G. Zonghua, "An efficient algorithm for online management of 2D area of partially reconfigurable FPGAs," in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE '07), pp. 1-6, April 2007.

Digital Library

[15]

T. Marconi and T. Mitra, "A novel online hardware task scheduling and placement algorithm for 3D partially reconfigurable FPGAs," in Proceedings of the International Conference on Field-Programmable Technology (FPT '11), pp. 1-6, New Delhi, India, December 2011.

[16]

T. Marconi, Y. Lu, K. Bertels, and G. Gaydadjiev, "Intelligent merging online task placement algorithm for partial reconflgurable systems," in Proceedings of the Conference on Design, Automation and Test in Europe (DATE '08), pp. 1346-1351, March 2008.

Digital Library

[17]

Q. Deng, F. Kong, N. Guan, L. Mingsong, and W. Yi, "Online placement of real time tasks on 2D partially run time reconfigurable FPGAs," in Proceedings of the 5th IEEE International Symposium on Embedded Computing (SEC '08), pp. 20-25, 2008.

Digital Library

[18]

T.-Y. Lee, C.-C. Hu, and C.-C. Tsai, "Adaptive free space management of online placement for reconfigurable systems," in Proceedings of the International MultiConference of Engineers and Computer Scientists (IMECS '10), pp. 322-326, Hong Kong, March 2010.

[19]

T. Y. Lee, C. C. Hu, and C. C. Tsai, "Multi-strategy online placement for dynamically partial reconfigurable device," in Proceedings of the International Conference on High-Speed Circuits Design, pp. H-20-H-26, October 2009.

[20]

M. M. Bassiri and H. S. Shahhoseini, "A new approach in on-line task scheduling for reconfigurable computing systems," in Proceedings of the 21st IEEE International Conference on Application-Specific Systems, Architectures and Processors, pp. 321-324, July 2010.

[21]

C. Steiger, H. Walder, and M. Platzner, "Operating systems for reconfigurable embedded platforms: online scheduling of real-time tasks," IEEE Transactions on Computers, vol. 53, no. 11, pp. 1393-1407, 2004.

Digital Library

[22]

C. Steiger, H. Walder, M. Platzner, and L. Thiele, "Online scheduling and placement of real-time tasks to partially reconfigurable devices," in Proceedings of the 24th IEEE International Real-Time Systems Symposium (RTSS '03), pp. 224-235, Cancun, Mexico, December 2003.

Digital Library

[23]

C. Steiger, H. Walder, and M. Platzner, "Heuristics for online scheduling real-time tasks to partially reconfigurable devices," in Proceedings of the 13th International Conference on Field Programmable Logic and Application (FPL '03), pp. 575-584, Lisbon, Portugal, September 2003.

[24]

I. Belaid, F. Muller, and M. Benjemaa, "Off-line placement of hardware tasks on FPGA," in Proceedings of the 19th International Conference on Field Programmable Logic and Applications (FPL '09), pp. 591-595, Prague, Czech Republic, September 2009.

[25]

A. A. Elfarag, H. M. El-Boghdadi, and S. I. Shaheen, "Fragmentation aware placement in reconfigurable devices," in Proceedings of the 6th IEEE International Workshop on System on Chip for Real Time Applications (IWSOC '06), pp. 37-44, December 2006.

[26]

M. Esmaeildoust, M. Fazlali, A. Zakerolhosseini, and M. Karimi, "Fragmentation aware placement algorithm for a reconfigurable system," in Proceedings of the 2nd International Conference on Electrical Engineering, pp. 1-5, March 2008.

[27]

Y. Lu, T. Marconi, G. Gaydadjiev, and K. Bertels, "An on-line task placement algorithm for partially reconfigurable systems," in Proceedings of the Architecture and Compiler for Embedded Systems (ACES '07), Edegem, Belgium, September 2007.

[28]

Y. Lu, T. Marconi, G. Gaydadjiev, and K. Bertels, "An efficient algorithm for free resources management on the FPGA," in Proceedings of the Conference on Design, Automation and Test in Europe (DATE '08), pp. 1095-1098, Munich, Germany, March 2008.

Digital Library

[29]

J. Gehr and J. Schneider, "Measuring fragmentation of two-dimensional resources applied to advance reservation grid scheduling," in Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID '09), pp. 276-283, May 2009.

Digital Library

Cited By

Zhu S(2018)Hardware implementation based on FPGA of semaphore management in μC/OS-II real-time operating systemInternational Journal of Grid and Utility Computing10.1504/IJGUC.2015.0706776:3/4(192-199)Online publication date: 16-Dec-2018
https://dl.acm.org/doi/10.1504/IJGUC.2015.070677

Recommendations

FPGA placement using space-filling curves: Theory meets practice

Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The ...
Hardware accelerated FPGA placement

A key advantage of field-programmable gate arrays (FPGAs) over full-custom and semi-custom devices is that they provide relatively quick implementation from concept to physical realization. However, as modern FPGAs reach close to one million logic ...
Clock-Aware FPGA Placement Contest
ISPD '17: Proceedings of the 2017 ACM on International Symposium on Physical Design

Modern FPGA device contains complex clocking architecture on top of FPGA logic fabric. To best utilize FPGA clocking architecture, both FPGA designers and EDA tool developers need to understand the clocking architecture and design best methodology/...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Reconfigurable Computing

International Journal of Reconfigurable Computing Volume 2014, Issue

January 2014

176 pages

ISSN:1687-7195

EISSN:1687-7209

Issue’s Table of Contents

Publisher

Hindawi Limited

London, United Kingdom

Publication History

Accepted: 24 January 2014

Published: 01 January 2014

Revised: 30 December 2013

Received: 30 September 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
36
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu S(2018)Hardware implementation based on FPGA of semaphore management in μC/OS-II real-time operating systemInternational Journal of Grid and Utility Computing10.1504/IJGUC.2015.0706776:3/4(192-199)Online publication date: 16-Dec-2018
https://dl.acm.org/doi/10.1504/IJGUC.2015.070677

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents