Top

Published in:

2018 | OriginalPaper | Chapter

2. Can Parallel Programming Revolutionize EDA Tools?

Authors : Yi-Shan Lu, Keshav Pingali

Published in: Advanced Logic Synthesis

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

previous chapter EDA3.0: Implications to Logic Synthesis

next chapter Emerging Circuit Technologies: An Overview on the Next Generation of Circuits

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].

A more detailed description of the implementation of the Galois system can be found in our previous papers such as [31].

D.A. Bader, K. Madduri, Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors, in High Performance Computing, HiPC’05 (2005)

U. Brandes, T. Erlebach (eds.), Network Analysis: Methodological Foundations (Springer, Heidelberg, 2005)MATH

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

K.M. Chandy, J. Misra, The drinking philosophers problem. ACM Trans. Program. Lang. Syst. 6(4), 632–646 (1984)CrossRef

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

P. Feautrier, Some efficient solutions to the affine scheduling problem: one dimensional time. Int. J. Parallel Prog. 21(5), 313–347 (1992)CrossRefMATHMathSciNet

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

M. Gort, J. Anderson, Deterministic multicore parallel routing for FPGAs, in International Conference on Field Programmable Technology (ICFPT’10) (2010)

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.

IWLS, IWLS 2005 benchmarks. http://iwls.org/iwls2005/benchmarks.html (2005)

11.

J. JaJa, An Introduction to Parallel Algorithms (Addison-Wesley, Boston, 1992)MATH

12.

R.M. Karp, V. Ramachandran, A survey of parallel algorithms for shared-memory machines. Technical Report UCB/CSD-88-408, EECS Department, University of California, Berkeley (1988). http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/5865.html

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.

V. Kotlyar, K. Pingali, P. Stodghill, A relational approach to the compilation of sparse matrix programs, in Euro-Par ’97: Proceedings of the Third International Euro-Par Conference on Parallel Processing (Springer, London, 1997), pp. 318–327. ISBN 3-540-63440-1. http://iss.ices.utexas.edu/Publications/Papers/EUROPAR1997.pdf CrossRefMATH

16.

M. Kulkarni, D. Nguyen, D. Prountzos, X. Sui, K. Pingali, Exploiting the commutativity lattice, in PLDI (2011)

17.

J. Lee, W.-S. Han, R. Kasperovics, J.-H. Lee, An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proc. VLDB Endow. 6(2), 133–144 (2012). ISSN 2150-8097. doi:10.14778/2535568.2448946. http://dx.doi.org/10.14778/2535568.2448946

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.

A. Lenharth, D. Nguyen, K. Pingali, Parallel graph analytics. Commun. ACM 59(5), 78–87 (2016). ISSN 0001-0782. doi:10.1145/2901919. http://doi.acm.org/10.1145/2901919

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.

M. Mendez-Lojo, A. Mathew, K. Pingali, Parallel inclusion-based points-to analysis, in Proceedings of the 24th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA’10), October 2010. http://iss.ices.utexas.edu/Publications/Papers/oopsla10-mendezlojo.pdf

26.

U. Meyer, P. Sanders, Delta-stepping: a parallel single source shortest path algorithm, in Proceedings of the 6th Annual European Symposium on Algorithms, ESA ’98 (Springer, London, 1998), pp. 393–404. ISBN 3-540-64848-8. http://dl.acm.org/citation.cfm?id=647908.740136

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.

D. Nguyen, A. Lenharth, K. Pingali, A lightweight infrastructure for graph analytics, in Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13 (ACM, New York, 2013), pp. 456–471. ISBN 978-1-4503-2388-8. doi:10.1145/2517349.2522739. http://doi.acm.org/10.1145/2517349.2522739 CrossRef

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.

J.R. Ullmann, Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. J. Exp. Algorithm. 15, 1.6:1.1–1.6:1.64 (2011) ISSN 1084-6654. doi:10.1145/1671970.1921702. http://doi.acm.org/10.1145/1671970.1921702

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

Title: Can Parallel Programming Revolutionize EDA Tools?
Authors: Yi-Shan Lu
Keshav Pingali
Publisher: Springer International Publishing
Book: Advanced Logic Synthesis
Print ISBN: 978-3-319-67294-6

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

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