nach oben

The Journal of Supercomputing

Erschienen in:

01.01.2015

A fast placement algorithm for embedded just-in-time reconfigurable extensible processing platform

verfasst von: H. Daryanavard, M. Eshghi, A. Jahanian

Erschienen in: The Journal of Supercomputing | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Reasonable trade-off between the ASIC performance and GPP flexibility is the main objective of reconfigurable computing systems. Dynamic Reconfigurable computing platform using embedded just-in-time (JIT) compilation is the most flexible platform among others. All complex computing kernels can be translated to bitstream to be executed on FPGA using an embedded processor of dedicated specialized hardware. The main challenge in these systems is FPGA design automation time. Executing the CAD algorithms on embedded processor is too time-consuming and normally is not feasible for real applications. Placement is the most computative part of CAD algorithm. Therefore, a new FPGA placement algorithm is proposed in this paper which makes reasonable trade-off between execution time and quality of placement. The proposed algorithm includes two stages: force-directed placement and simulated annealing placement. The proposed algorithm is very low execution time to be useful in JIT compilation without considerable degradation on the quality of placement. Experimental results show \(2.33\times \) speedup in execution time in cost of 3 % overhead in channel tracks numbers.

Vorheriger Artikel Distributed optimization Grid resource discovery

Nächster Artikel The -Set consensus problem with weight consideration

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Koester M, Hagemeyer J, Porrmann M (2011) Design optimizations for tiled partially reconfigurable systems. IEEE Trans VLSI Syst 19(6):1048–1061. doi:10.1109/TVLSI.2010.2044902

Kingshuk K, Chattopadhyay A, Chen X, Kammler D, Hao L, Leupers R, Meyr H, Ascheid G (2008) A design flow for architecture exploration and implementation of partially reconfigurable processors. IEEE Trans VLSI Syst 16(10):1281–1294CrossRef

Marconi T (2014) Online scheduling and placement of hardware tasks with multiple variants on dynamically reconfigurable field-programmable gate arrays. Comput. Electr. Eng. 40(4):1215–1237CrossRef

Fazlali M, Zakerolhosseini A, Gaydadjiev G (2012) Efficient datapath merging for the overhead reduction of run-time reconfigurable systems. J Supercomput 59(2):636–657CrossRef

Sidiropoulos H, Siozios K (2012) On Supporting efficient partial reconfiguration with just-in-time compilation, IPDPS workshops, pp 328–335

Bergeron E, Feeley M, David J (2008) Hardware JIT compilation for off-the-shelf dynamically reconfigurable FPGAs. In: 17th international conference, CC, pp 178–192

Lysecky R, Vahid F, Tan S (2004) Dynamic FPGA routing for just-in-time FPGA compilation. In: Proceedings of the 41st design automation conference, 2004. IEEE, San Diego, CA, pp 954–959

Vahid F, Stitt G, Lysecky R (2008) Warp processing: dynamic translation of binaries to FPGA circuits. IEEE Comput Soc 41(7):40–46CrossRef

Lysecky R, Vahid F (2009) Design and implementation of a microblaze-based warp processor. ACM Tran Embed Comput Syst (TECS) 8(3):21–29

10.

Grudnitsky A, Bauer L (2012) Partial online-synthesis for mixed-grained reconfigurable architectures. Des Autom Test Europe Conf (DATE), pp 1555–1560

11.

Bauer L, Shafique M, Kreutz S, Henkel J (2008) Run-time system for an extensible embedded processor with dynamic instruction set. Des Autom Test Eur, 752–757

12.

http://newsroom.intel.com/community/intel_newsroom

13.

Coole J, Stitt G (2014) Fast, flexible high-level synthesis from OpenCL using reconfiguration contexts. Micro IEEE 34(1):42–53CrossRef

14.

Shaoshan L, Richard P, Alessandro F, Gaudiot J (2012) Minimizing the runtime partial reconfiguration overheads in reconfigurable systems. J Supercomput 61(3):894–911CrossRef

15.

Jang S, Chan B, Chung K (2009) WireMap: FPGA technology mapping for improved routability and enhanced LUT merging. ACM Trans Reconfig Technol Syst 2(2):1–23CrossRef

16.

Sanjabi M, Miralaei N, Amanollahi S, Jahanian A (2012) ParSA: parallel simulated annealing placement algorithm for multi-core systems. Int Symp Comput Archit Digital Syst (CADS)

17.

Farkish A, Jahanian A (2012) Parallelizing the FPGA global routing algorithm on multi-core systems without quality degradation. Inst Electr Inf Commun Eng Electron Express J 8(24):35–39

18.

Lin M, Wawrzynek J (2010) Improving FPGA placement with dynamically adaptive stochastic tunneling. In: IEEE transaction on computer-aided design of integrated circuits and systems, vol 29, no 12, pp 1858–1869

19.

Andrew B, Kahng J (2011) VLSI physical design, from graph partitioning to timing closure. Springer, Berlin

20.

Tony F, Cong J, Kong T, Joseph R (2000) Multilevel optimization for large-scale circuit placement. ICCAD, Shanghai, pp 171–176

21.

Tony F, Cong J, Joseph R, Min X (2005) mPL6: a robust multilevel mixed-size placement engine. ISPD, Madrid, pp 227–229

22.

Areibi S, Grewal G, Banerji D, Du P (2007) Hierarchical FPGA placement. Can J Electr Comput Eng 32(1):53–64

23.

Ababei C (2009) Speeding up FPGA placement via partitioning and multithreading. Int J Reconfigurable Comput 2009:1–9. Art ID 514754. doi:10.1155/2009/514754

24.

Taghavi T, Yang X, Wang M, Sarrafzadeh M (2007) Dragon 2005: large scale mixed-sized placement tool. In: International symposium on physical design, ISPD design contest, pp 42–47

25.

Jarrod A, David A, Igor L (2007): Capo: congestion-driven placement for standard-cell and RTL netlists with incremental capability. In: Modern circuit placementseries on integrated circuits and systems, pp 97–133

26.

Vicente J, Lanchares J, Hermida R (2003) Placement by thermodynamic simulated annealing. Phys Lett A 317:415–423CrossRefMATH

27.

Tessier R (2002) Fast placement approaches for FPGAs. ACM Trans Des Autom Electron Syst 7:284–305CrossRef

28.

Maidee P, Ababei C, Bazargan K (2003) Fast timing-driven partitioning based placement for island style FPGAs. In: Proceedings of the 40th annual design automation conference, pp 598–603

29.

John A, Prithviraj B (1996) Parallel simulated annealing strategies for VLSI cell placement. In: VLSI design, pp 37–42

30.

Chen H, Cheng N, MacDonald J, Suaris P, Yao B, Zhu Z (2003) Analgebraic multigrid solver for analytical placement with layout based clustering. In: Proceedings of the IEEE/ACM design automation conference, pp 794–799

31.

Viswanathan N, Chris C (2005) FastPlace efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. IEEE Trans CAD Integr Circ Syst 24(5):722–733

32.

Robert C, Christian F, Laura R, Gary G (2012) A formal and empirical analysis of recombination for genetic algorithm-based approaches to the FPGA placement problem. CCECE, pp 1–6

33.

Andrzej K, Zbigniew N (2009) FPGA placement by using Hopfield neural network. J Microelectron Int 26:22–32

34.

Betz V, Rose J (2000) VPR and T-VPack: versatile packing, placement and routing for FPGAs package. ver. 4.30

35.

Chen G, Cong J (2005) Simultaneous timing-driven placement and duplication. In: Proceedings of the ACM/SIGDA 13th international symposium on FPGAs, Monterey, Calif., pp 51–59

36.

http://www.eecg.toronto.edu/vaughn/challenge/challenge.html

Titel: A fast placement algorithm for embedded just-in-time reconfigurable extensible processing platform
verfasst von: H. Daryanavard
M. Eshghi
A. Jahanian
Publikationsdatum: 01.01.2015
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 1/2015
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-014-1290-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2015

Embedding complete binary trees into parity cubes

SEATS: smart energy-aware task scheduling in real-time cloud computing

On the computational power of WECPAR

Distributed optimization Grid resource discovery

A survey of genome sequence assembly techniques and algorithms using high-performance computing

An improved nonlinear data dependence test