GENESIS: Parallel Application Placement onto Reconfigurable Architectures (Invited for the Special Issue on Runtime Management)
Authors: 
Dionysios Diamantopoulos, Kostas Siozios, Sotirios Xydis, Dimitrios SoudrisAuthors Info & Claims
Article No.: 18, Pages 1 - 26
Abstract
Placement is though as the most time-consuming processes in physical implementation flows for reconfigurable architectures, while it highly affects the quality of derived application implementation, as it has impact on the maximum operating frequency. Throughout this article, we propose a novel placer, based on genetic algorithm, targeting to FPGAs. Rather than relevant approaches, which are executed sequentially, the new placer exhibits inherent parallelism, which can benefit from multicore processors. Experimental results prove the effectiveness of this solution, as it achieves average reduction of execution runtime and application’s delay by 67× and 16%, respectively.
References
[1]
Cristinel Ababei. 2009. Speeding up FPGA placement via partitioning and multithreading. Int. J. Reconfig. Comp.
[2]
Gene M. Amdahl. 1967. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the AFIPS Spring Joint Computing Conference, Vol. 30. 483--485.
[3]
Vaughn Betz and Jonathan Rose. 1997. VPR: A new packing, placement and routing tool for FPGA research. In FPL. Lecture Notes in Computer Science. Springer, 213--222.
[4]
Vaughn Betz, Jonathan Rose, and Alexander Marquardt (Eds.). 1999. Architecture and CAD for Deep-Submicron FPGAs. Springer, New York, NY.
[5]
Andrea Casotto, Fabio Romeo, and Alberto L. Sangiovanni-Vincentelli. 1987. A parallel simulated annealing algorithm for the placement of macro-cells. IEEE Trans. CAD Integr. Circuits Syst. 6, 5, 838--847.
[6]
Alexander Choong, Rami Beidas, and Jianwen Zhu. 2010. Parallelizing simulated annealing-based placement using GPGPU. In FPL. IEEE, 31--34.
[7]
Paul Darwen and Xin Yao. 1995. A dilemma for fitness sharing with a scaling function. In Proc. of the 1995 IEEE Int’l Conf. on Evolutionary Computation (ICEC’95). IEEE Press, 166--171.
[8]
D. Diamantopoulos, K. Siozios, S. Xydis, and D. Soudris. 2013. A framework for supporting parallel application placement onto reconfigurable platforms. In Proceedings of the PARMA Workshop, HiPEAC Conference, Berlin, Germany.
[9]
John M. Emmert and Dinesh Bhatia. 1999. Tabu Search: Ultra-fast placement for FPGAs. In FPL. Lecture Notes in Computer Science, Vol. 1673. Springer, New York, NY, 81--90.
[10]
Sonke Hartmann. 2002. A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics (NRL) 49, 5, 433--448.
[11]
Tzung-Pei Hong and Hong-Shung Wang. 1996. A dynamic mutation genetic algorithm. In Proceedings of the 1996 International Conference on Systems, Man, and Cybernetics, Vol. 3. 2000--2005.
[12]
ITRS. 2012. International Technology Roadmap for Semiconductors. Retrieved from http://www.itrs.net/.
[13]
Peter Jamieson. 2010. Revisiting genetic algorithms for the FPGA placement problem. In GEM. 16--22.
[14]
V. Kalenteridis, H. Pournara, K. Siozos, K. Tatas, N. Vassiliadis, I. Pappas, G. Koutroumpezis, S. Nikolaidis, S. Siskos, D. J. Soudris, and A. Thanailakis. 2005. A complete platform and toolset for system implementation on fine-grain reconfigurable hardware. Microprocess. Microsyst. 29, 6, 247--259.
[15]
Tapas Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu. 2002. An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24, 7 (2002), 881--892.
[16]
Saul A. Kravitz and Rob A. Rutenbar. 1987. Placement by simulated annealing on a multiprocessor. IEEE Trans. CAD of Integr. Circuits Syst. 6, 4 (1987), 534--549.
[17]
Julien Lamoureux and Steven J. E. Wilton. 2003. On the interaction between power-aware FPGA CAD algorithms. In Proceedings of the 2003 IEEE/ACM International Conference on Computer-Aided Design. 701--708.
[18]
A. Livnat, C. Papadimitriou, J. Dushoff, and M. Feldman. 2008. A mixability theory for the role of sex in evolution. Proc. Natl. Acad. Sci. USA 105, 50 (2008), 19803--19808.
[19]
Adrian Ludwin and Vaughn Betz. 2011. Efficient and deterministic parallel placement for FPGAs. ACM Trans. Design Autom. Electr. Syst. 16, 3, 22.
[20]
Adrian Ludwin, Vaughn Betz, and Ketan Padalia. 2008. High-quality, deterministic parallel placement for FPGAs on commodity hardware. In FPGA. ACM, New York, NY, 14--23.
[21]
P. Moscato and J. F. Fontanari. 1990. Convergence and finite-time behavior of simulated annealing. Adv. Appl. Probab. 18 (1990), 747--771.
[22]
Edmund M. A. Ronald. 1995. When selection meets seduction. In Proceedings of the 6th International Conference on Genetic Algorithms. Morgan Kaufmann, Philadelphia, PA, 167--173.
[23]
Jonathan Rose, W. Martin Snelgrove, and Zvonko G. Vranesic. 1988. Parallel standard cell placement algorithms with quality equivalent to simulated annealing. IEEE Trans. CAD of Integr Circuits Syst 7, 3, 387--396.
[24]
Yaska Sankar and Jonathan Rose. 1999. Trading quality for compile time: ultra-fast placement for FPGAs. In FPGA. 157--166.
[25]
N. Selvakkumaran and G. Karypis. 2003. Multi-objective hypergraph partitioning algorithms for cut and maximum subdomain degree minimization. In Proceedings of the International Conference on Computer Aided Design (ICCAD’03). 726--733.
[26]
E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, Robert K. Brayton, and Alberto L. Sangiovanni-Vincentelli. 1992. SIS: A System for Sequential Circuit Synthesis. Technical Report No. UCB/ERL M92/41, University of California, Berkeley, CA.
[27]
Donald Shepard. 1968. A two-dimensional interpolation function for irregularly-spaced data. In Proceedings of the 1968 23rd ACM National Conference (ACM’68). 517--524.
[28]
H. Sidiropoulos, K. Siozios, P. Figuli, D. Soudris, and M. Hubner. 2012. On supporting efficient partial reconfiguration with just-in-time compilation. In Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum. 328--335.
[29]
H. Sidiropoulos, K. Siozios, and D. Soudris. 2011. A methodology and tool framework for supporting rapid exploration of memory hierarchies in FPGAs. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL’11). 238--243.
[30]
G. Smecher, S. Wilton, and G. G. F. Lemieux. 2009. Self-hosted placement for massively parallel processor arrays. In Proceedings of the International Conference on Field-Programmable Technology (FPT’09). 159--166.
[31]
R. E. Smith and Claudio Bonacina. 2003. Mating restriction and niching pressure: Results from agents and implications for general EC. In Proc. of the Genetic and Evolutionary Computation Conf. Lecture Notes in Computer Science, Vol. 2724. Springer-Verlag, 1382--1393.
[32]
M. Srinivas and Lalit M. Patnaik. 1994. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans. Syst. Man Cybern. 24, 4, 656--667.
[33]
Russell Tessier. 2002. Fast placement approaches for FPGAs. ACM Trans. Design Autom. Electr. Syst. 7, 2 (2002), 284--305.
[34]
Chuan-Kang Ting, Sheng-Tun Li, and Chungnan Lee. 2003. On the harmonious mating strategy through tabu search. Inf. Sci. 156, 3--4 (2003), 189--214.
[35]
Chris C. Wang and Guy G. Lemieux. 2011. Scalable and deterministic timing-driven parallel placement for FPGAs. In FPGA. 153--162.
[36]
Ellen E. Witte, Roger D. Chamberlain, and Mark A. Franklin. 1991. Parallel simulated annealing using speculative computation. IEEE Trans. Parallel Distrib. Syst. 2, 4 (1991), 483--494.
[37]
Michael G. Wrighton and Andr M. Dehon. 2003. Hardware-assisted simulated annealing with application for fast FPGA placement. In Proceedings of the International Symposium on Field-Programmable Gate Arrays. ACM Press, New York, NY, 33--42.
[38]
S. Xydis, A. Bartzas, I. Anagnostopoulos, D. Soudris, and K. Pekmestzi. 2010. Custom multi-threaded dynamic memory management for multiprocessor system-on-chip platforms. Embedded Computer Systems (SAMOS), 2010 International Conference on. IEEE, 102--109.
[39]
Vittorio Zaccaria, Gianluca Palermo, Fabrizio Castro, Cristina Silvano, and Giovanni Mariani. 2010. Multicube Explorer: an open source framework for design space exploration of chip multi-processors. In Proceedings of the ARCS Workshops. 325--331.
Index Terms
- GENESIS: Parallel Application Placement onto Reconfigurable Architectures (Invited for the Special Issue on Runtime Management)
Recommendations
MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs
In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...
GPlace3.0: Routability-Driven Analytic Placer for UltraScale FPGA Architectures
Optimizing for routability during FPGA placement is becoming increasingly important, as failure to spread and resolve congestion hotspots throughout the chip, especially in the case of large designs, may result in placements that either cannot be routed ...
Routability-driven placement for hierarchical mixed-size circuit designs
DAC '13: Proceedings of the 50th Annual Design Automation ConferenceA wirelength-driven placer without considering routability could introduce irresolvable routing-congested placements. Therefore, it is desirable to develop an effective routability-driven placer for modern mixed-size designs employing hierarchical ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2015
443 pages
Copyright © 2015 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 21 January 2015
Accepted: 01 January 2014
Revised: 01 November 2013
Received: 01 June 2013
Published in TECS Volume 14, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 124Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)4
Reflects downloads up to 30 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in