Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
EDA3.0: Implications to Logic Synthesis Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

2. Can Parallel Programming Revolutionize EDA Tools?

verfasst von : Yi-Shan Lu, Keshav Pingali

Erschienen in: Advanced Logic Synthesis

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Recent advances in parallel programming hold the promise of transforming the EDA tools area and changing the way we design, synthesize, and simulate circuits.
Traditional parallel programming technology was developed for computational science applications, which operate on dense and sparse matrices, and it is not useful for most EDA applications. However, in the past decade, there has been substantial progress in developing parallelization technology for graph applications. These advances were motivated primarily by the needs of large-scale parallel graph analytics, but this technology is useful for EDA applications since large graphs such as netlists are ubiquitous in this domain.
In this paper, we describe the Galois system, developed by our group at the University of Texas at Austin to make it easier to program large-scale graph applications and execute them in parallel. Algorithms from many problem domains including graph analytics, high-performance computing, and FPGA tools have been implemented successfully in Galois. These successes suggest that by working together, the EDA and parallel programming research communities can bring state-of-the-art parallel programming technology to bear on EDA tools, transforming this area.

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

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

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
Vorheriges Kapitel EDA3.0: Implications to Logic Synthesis
Nächstes Kapitel Emerging Circuit Technologies: An Overview on the Next Generation of Circuits
Fußnoten
1
Sparse direct methods are an exception, but even in these algorithms, a dependence graph, known as the elimination tree, is built before the algorithm is executed in parallel [5].
 
2
A more detailed description of the implementation of the Galois system can be found in our previous papers such as [31].
 
Literatur
1.
D.A. Bader, K. Madduri, Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors, in High Performance Computing, HiPC’05 (2005)
2.
U. Brandes, T. Erlebach (eds.), Network Analysis: Methodological Foundations (Springer, Heidelberg, 2005)MATH
3.
G. Bronevetsky, D. Marques, K. Pingali, P. Stodghill, C3: a system for automating application-level checkpointing of MPI programs. Languages and Compilers for Parallel Computing (Springer, New York, 2004), pp. 357–373
4.
K.M. Chandy, J. Misra, The drinking philosophers problem. ACM Trans. Program. Lang. Syst. 6(4), 632–646 (1984)CrossRef
5.
I.S. Duff, A.M. Erisman, J.K. Reid, Direct Methods for Sparse Matrices (Oxford University Press, New York, 1986). ISBN 0-198-53408-6MATH
6.
P. Feautrier, Some efficient solutions to the affine scheduling problem: one dimensional time. Int. J. Parallel Prog. 21(5), 313–347 (1992)CrossRefMATHMathSciNet
7.
J.E. Gonzalez, Y. Low, H. Gu, D. Bickson, C. Guestrin, Powergraph: distributed graph-parallel computation on natural graphs, in Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, Berkeley, CA, 2012, pp. 17–30. USENIX Association. ISBN 978-1-931971-96-6. http://​dl.​acm.​org/​citation.​cfm?​id=​2387880.​2387883
8.
M. Gort, J. Anderson, Deterministic multicore parallel routing for FPGAs, in International Conference on Field Programmable Technology (ICFPT’10) (2010)
9.
M.A. Hassaan, M. Burtscher, K. Pingali, Ordered vs unordered: a comparison of parallelism and work-efficiency in irregular algorithms, in Proceedings of the 16th ACM symposium on Principles and Practice of Parallel Programming, PPoPP ’11 (ACM, New York, 2011), pp. 3–12. ISBN 978-1-4503-0119-0. doi:http://​doi.​acm.​org/​10.​1145/​1941553.​1941557.​ http://​iss.​ices.​utexas.​edu/​Publications/​Papers/​ppopp016s-hassaan.​pdf
10.
11.
J. JaJa, An Introduction to Parallel Algorithms (Addison-Wesley, Boston, 1992)MATH
12.
13.
K. Kennedy, J. Allen (eds.) Optimizing Compilers for Modern Architectures: A Dependence-Based Approach (Morgan Kaufmann, San Francisco, 2001)
14.
I. Kodukula, N. Ahmed, K. Pingali, Data-centric multi-level blocking, in PLDI ’97: Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation (ACM, New York, 1997), pp. 346–357. ISBN 0-89791-907-6. doi:http://​doi.​acm.​org/​10.​1145/​258915.​258946.​ http://​iss.​ices.​utexas.​edu/​Publications/​Papers/​PLDI1997.​pdf
15.
16.
M. Kulkarni, D. Nguyen, D. Prountzos, X. Sui, K. Pingali, Exploiting the commutativity lattice, in PLDI (2011)
17.
18.
A. Lenharth, K. Pingali, Scaling runtimes for irregular algorithms to large-scale NUMA systems. Computer 48(8), 35–44 (2015)CrossRef
19.
A. Lenharth, D. Nguyen, K. Pingali, Priority queues are not good concurrent priority schedulers, in European Conference on Parallel Processing (Springer, Berlin/Heidelberg, 2015), pp. 209–221
20.
21.
D.B. Loveman, High performance fortran. IEEE Parallel Distrib. Technol. Syst. Appl. 1(1), 25–42 (1993)CrossRef
22.
Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, J.M. Hellerstein, Graphlab: a new parallel framework for machine learning, in Conference on Uncertainty in Artificial Intelligence (UAI), July 2010
23.
D. Mackay, Information Theory, Inference and Learning Algorithms (Cambridge University Press, Cambridge, 2003)MATH
24.
G. Malewicz, M.H. Austern, A.J. Bik, J.C. Dehnert, I. Horn, N. Leiser, G. Czajkowski, Pregel: a system for large-scale graph processing - “abstract”, in Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC ’09 (ACM, New York, 2009), pp. 6–6 ISBN 978-1-60558-396-9. doi:10.1145/1582716.1582723. http://​doi.​acm.​org/​10.​1145/​1582716.​1582723
25.
26.
27.
J. Misra, Distributed discrete-event simulation. ACM Comput. Surv. 18(1), 39–65 (1986), ISSN 0360-0300. doi:http://​doi.​acm.​org/​10.​1145/​6462.​6485
28.
Y.O.M. Moctar, P. Brisk, Parallel FPGA routing based on the operator formulation, in Proceedings of the 51st Annual Design Automation Conference, DAC ’14 (2014).
29.
R. Nasre, M. Burtscher, K. Pingali, Data-driven versus topology-driven irregular computations on GPUs, in Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium, IPDPS ’13 (Springer, London, 2013)
30.
D. Nguyen, K. Pingali, Synthesizing concurrent schedulers for irregular algorithms, in Proceedings of International Conference Architectural Support for Programming Languages and Operating Systems, ASPLOS ’11, pp. 333–344 (2011). ISBN 978-1-4503-0266-1. doi:10.1145/1950365.1950404. http://​doi.​acm.​org/​10.​1145/​1950365.​1950404
31.
32.
R.W. Numrich, J. Reid, Co-array fortran for parallel programming, in ACM Sigplan Fortran Forum, vol. 17 (ACM, New York, 1998), pp. 1–31
33.
K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M.A. Hassaan, R. Kaleem, T.-H. Lee, A. Lenharth, R. Manevich, M. Méndez-Lojo, D. Prountzos, X. Sui, The TAO of parallelism in algorithms, in Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’11, pp. 12–25 (2011). ISBN 978-1-4503-0663-8. doi:10.1145/1993498.1993501. http://​doi.​acm.​org/​10.​1145/​1993498.​1993501
34.
D. Prountzos, R. Manevich, K. Pingali, K.S. McKinley, A shape analysis for optimizing parallel graph programs, in Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’11 (ACM, New York, 2011), pp. 159–172. ISBN 978-1-4503-0490-0. doi:http://​doi.​acm.​org/​10.​1145/​1926385.​1926405.​ http://​www.​cs.​utexas.​edu/​users/​dprountz/​popl2011.​pdf
35.
J.R. Shewchuk, Triangle: engineering a 2D quality mesh generator and delaunay triangulator, in Applied Computational Geometry: Towards Geometric Engineering, ed. by M.C. Lin, D. Manocha. Lecture Notes in Computer Science, vol. 1148 (Springer, Berlin, 1996), pp. 203–222. From the First ACM Workshop on Applied Computational Geometry
36.
J. Shun, G.E. Blelloch, Ligra: a lightweight graph processing framework for shared memory, in Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP, pp 135–146 (2013)CrossRef
37.
P.-N. Tan, M. Steinbach, V. Kumar (eds.), Introduction to Data Mining (Pearson Addison Wesley, Boston, 2005)
38.
39.
L.G. Valiant, A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990). ISSN 0001-0782. doi:http://​doi.​acm.​org/​10.​1145/​79173.​79181
40.
S.C. Woo, M. Ohara, E. Torrie, J.P. Singh, A. Gupta, The splash-2 programs: characterization and methodological considerations, in Proceedings of the 22nd Annual International Symposium on Computer Architecture, ISCA ’95 (ACM, New York, 1995), pp. 24–36. ISBN 0-89791-698-0. doi:10.1145/223982.223990. http://​doi.​acm.​org/​10.​1145/​223982.​223990
Metadaten
Titel
Can Parallel Programming Revolutionize EDA Tools?
verfasst von
Yi-Shan Lu
Keshav Pingali
Copyright-Jahr
2018
Buch
Advanced Logic Synthesis

Print ISBN: 978-3-319-67294-6

Electronic ISBN: 978-3-319-67295-3

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-67295-3_2

Neuer Inhalt

    Bildnachweise