We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Reseach Article

A Review of Parallelization Tools and Introduction to Easypar

by Sudhakar Sah, Vinay G. Vaidya
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 56 - Number 12
Year of Publication: 2012
Authors: Sudhakar Sah, Vinay G. Vaidya
10.5120/8944-3108

Sudhakar Sah, Vinay G. Vaidya . A Review of Parallelization Tools and Introduction to Easypar. International Journal of Computer Applications. 56, 12 ( October 2012), 30-34. DOI=10.5120/8944-3108

@article{ 10.5120/8944-3108,
author = { Sudhakar Sah, Vinay G. Vaidya },
title = { A Review of Parallelization Tools and Introduction to Easypar },
journal = { International Journal of Computer Applications },
issue_date = { October 2012 },
volume = { 56 },
number = { 12 },
month = { October },
year = { 2012 },
issn = { 0975-8887 },
pages = { 30-34 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume56/number12/8944-3108/ },
doi = { 10.5120/8944-3108 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:58:39.625872+05:30
%A Sudhakar Sah
%A Vinay G. Vaidya
%T A Review of Parallelization Tools and Introduction to Easypar
%J International Journal of Computer Applications
%@ 0975-8887
%V 56
%N 12
%P 30-34
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Multicore processors have paved the way to increase the performance of any application by the virtue of benefits of parallelization. However, exploiting parallelism from a program is not easy, as it requires parallel programming expertise. In addition, manual parallelization is a cumbersome, time consuming and inefficient process. A number of tools proposed in the past ease the effort of parallel programming. This paper presents a classification of such parallelization tools. The classification is based on different eras of tool development, role playedby these tools in various parallelization stages, and features provided by parallel program assistance tools. Classification of tools concludes with a discussion on requirements of futuristic parallelization tools. Finally, this paper proposesour on-going work about the development of a parallel program assistance tool called EasyPar, which is a parallel program assistance tool.

References
  1. Official home page Message Passing Interface (MPI) Available : www. mpi-forum. org/
  2. official home page - Open MP, Available : www. openmp. org
  3. Sutter, H. , "The free lunch is over," Dr. Dobb's Journal, vol. 30, March 2005
  4. Per Stenstrom, The Paradigm Shift to MultiCores: Opportunities and Challenges, Appl. Comput. Math. (2007) 253-257
  5. VivekSarkar, Programming challenges for multicore Parallel systems, Presentation for Computer Science Department, Rice University. http://www. rice. edu
  6. McKinsley, Karthryn S. Automatic and Interactive Parallelization, PhD. Thesis, Computer Science, Rice University. Houston, Texas (1994) 12-32.
  7. Tournavitis, G. and Franke, B. , "Semi-automatic extraction and exploitation of hierarchical pipeline parallelism using profiling information," in Proceedings of the 19th international conference on Parallel architectures and compilation techniques, PACT '10, (New York, NY, USA), pp. 377–388, ACM, 2010.
  8. Minjang Kim, dynamic program analysis algorithms to assist parallelization, PhD. thesis proposal, Georgia Institute of Technology, 2011. pp 5-28.
  9. S. Sah and VinayG. Vaidya, Paradyn: A Dynamic Parallel Programming Tool, ICDCN, 12th International Conference on Distributed Computing and Networking, PhD forum (2010)
  10. ParMA - Parallel Programming for Multi-core Architectures, Available : http://www. parma-itea2. org
  11. Par4All homepage : URL : http://www. par4all. org
  12. Chirag Dave, HansangBae, Seung-Jai Min, Seyong Lee, Rudolf Eigenmann, and Samuel Midkiff, "cetus: a sourceto-source compiler infrastructure for multicores", Computer, Vol. 42, no. 12, pp. 36-42, Dec. 2009, doi:10. 1109/MC. 2009. 385
  13. B. Q. Warber, C. R. Brode and F. L. Orlando, DEEP: a development environment for parallel programs. , Parallel Processing Symposium, IPPS/SPDP (1998) 588-593.
  14. Peter Kacsuk, Gabor Dozsa, TiborFadgyas, Robert Lovas, "The GRED Graphical Editor for the GRADE Parallel Program Development Environment", Budapest, Hungary : MTA-SZTAKI Computer and Automation Research Institute, Hungarian Academy of Science.
  15. G. Tournavitis, Z. Wang, B. Franke,M. O'Boyle, "Towards a holistic approach to auto-parallelization: integrating profile-driven parallelism detection and machine-learning based mapping", PLDI '09, pp 177-187.
  16. Karl Fuerlinger, Michael Gerndt, Jack Dongarra, On Using Incremental Profiling for the Performance Analysis of Shared Memory Parallel Applications, Lecture Notes in Computer Sciences, (2007) 62-71
  17. Andrew R. Bernat, Barton P. Miller, "Incremental Call-Path Profiling", Computer Sciences Department, University of Wisconsin. Madison, WI
  18. CathalBoogerd, Leon Moonen, "On the Use of Data Flow Analysis in Static Profiling", Software EvolutionResearch Lab, Delft University of Technology. The Netherlands
  19. "On Using Incremental Profiling for the Performance Analysis of Shared Memory Parallel Applications", Innovative Computing Laboratory", Department of Computer Science, University of Tennessee. Technical Report
  20. NEC IMAPCAR Technical Document – www. nec. com
  21. Graham, Wagner and Susan, Efficient and Flexible Incremental Parsing, ACM Transactions of Programming Languages and Systems, Vol. 20 (1998)
  22. Barbara G. Ryder, A Position Paper on Compiler Time Program Analysis, Computer Science Dept. , Rutgers University (1997)
  23. Amdahl, Gene, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities". AFIPS Conference Proceedings, 1967, pp 483-485.
  24. Beth Tibbitts, PTP - PLDT Parallel Language Development Tools Overview, Status & Plans. Technical Report by IBM, (2007)
  25. S. P. Amarasinghe, J. M. Anderson, M. S. Lam and C. W. Tseng, An Overview of the SUIF Compiler for Scalable Parallel Machines, Seventh SIAM Conference on Parallel Processing for Scientific Computing (1995)
  26. R. J. Abbott, Integrated Approach to Software Development. John Wiley and Sons (1986)
  27. Ravichandran K. M. , Bhaskar P, Annamalai. S. P. and Dr. A. P. Shanthi, Automatic Inter-procesural Parallelism, Department of Computer Science, College of Engineering, Guindy, Anna University
  28. David A. Bader, Rucheek H. Sangani , Introduction to SWARM Software and Algorithms for Running on Multicore processors, Tutorial, Georgia Institute of Technology Available- http://multicore-swarm. sourceforge. net
  29. Ashwin Kumar, Aasish Kumar Pappu, Sarath Kumar, K. , SudipSanyal, "Hybrid Approach for Parallelization of Sequential Code with Function Level and Block Level Parallelization", Parallel Computing in Electrical Engineering, (2006)
  30. W. Ambrus, A Framework for Automatic Parallelization of Sequential Programs, Proceedings of the 7th International Conference on Volume 2 (2003) 11-13
  31. M. Girkar and C. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Transactions on Parallel and Distributed Systems (1992)
  32. Manish Gupta, SayakMukhopadhyay, Navin Sinha, ,Automatic Parallelization of Recursive Procedures, Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, (1999) 139 – 148
  33. R. Rugina and M. Rinard, Automatic Parallelization of Divide and Conquer Algorithms, In Proc. ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming, Atlanta, GA (1999)
  34. John Hughes , Why Functional Programming Matters Institutionen for Datavetenskap, Chalmers TekniskaHogskolaGteborg, SWEDEN, Circulated as Chalmers memo (1984)
  35. NirSavit, Dan Touitou, Software Transactional Memory, ACM-PODC, Ottawa Ontario, CA, 1995
  36. Official Website : "The Multicore Association", http:// www. multicore-association. org/
  37. NVIDIA Corporation. : NVIDIA CUDA Programming Guide. Technical Report. California. USA. (2008)
  38. E. T. Hvannberg, M. S. Krishnamoorthy, An Object-based Parallel Programming Assistant, Proceeedings of the ACM SIGPLAN Workshop on Object-Based Concurrent Programming. Vols. 24, Issue 4, (1998) 200-202
  39. Sudhakar Sah, Vinay G. Vaidya, A GPU Based Novel Design of Side Effect Analysis, ICOMEC, Goa, India, (2011) 137-143
  40. Eileen Kraemer, John T. Stasko, Towards Flexible Control of the Temporal Mapping from Concurrent Program Events to Animations. Graphics, Technical Report-Visualization and Usability Center, Georgia Institute of Technology. Atlanta, GA (1994)
  41. Karl Fuerlinger, Michael Gerndt, Jack Dongarra, On Using Incremental Profiling for the Performance Analysis of Shared Memory Parallel Applications, Lecture notes in Computer science, Springer, Berlin, Volume 4641 62-71
  42. U. Ismail, "Incremental call-graph construction for the eclipse IDE", University of Waterloo Technical Report No. CS-2009-07, David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada
  43. M. W. Hall, J. M. Anderson, S. P. Amarasinghe, B. R. Murphy, S. -W. Liao, and E. Bu. "Maximizing multiprocessor performance with the SUIF compiler", IEEE Computer, (1996)
  44. Saturnino Garcia, DonghwanJeon, Chris Louie, Sravanthi Kota Venkata, and Michael Bedford Taylor, Bridging the Parallelization Gap: Automating Parallelism Discovery and Planning, HotPar, 2nd USENIX workshop on hot topics in parallelism, Poster presentation (2010)
  45. U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan, A Practical Automatic Polyhedral Parallelizer and Locality Optimizer, Programming Language Design and Implementation, Vol. 43, Issue 6, (2008) http://pluto-compiler. sourceforge. net/
  46. Hannu-MattiJärvinen, MikkoTiusanen, and Antti T. x`Virtanen, Convit, a Tool for Learning Concurrent Programming, Software Systems Institute, Department of Information Science Tampere University of Technology, Finland
  47. M. Kumar. "Measuring parallelism in computation-intensive scientific/engineering applications. " IEEE TOC, Sep 1988.
  48. Muhammed S. Al-Mulhem, Concurrent programming in VISO, Concurrency : Practice and Experience Concurrency, Pract. Exper. (2000) 281–288
  49. Pong M. I-pigs: An Interactive Graphical Environment for Concurrent Programming, Computer Journal (1991) 320 330
  50. Kramer J, Magee J, Ng K, "Graphical configuration programming", Computer 1989; 22(10):53–65.
  51. V. Sarkar,"Automatic partitioning of a program dependence graph into parallel tasks", In IBM Journal of Research and Development, pages 779–804, 1991.
  52. M. C. Rinard, D. J. Scales, and M. S. Lam. "Jade: A High-Level, Machine-Independent Language for Parallel Programming". IEEE Computer, 26(6):pp 28–38, 1993.
  53. T. J. Marlowe and B. G. Ryder, "An Efficient Hybrid Algorithm for Incremental Data Flow Analysis", In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages. (1990) 184–196
  54. J. Yur, and B. G. Ryder, Incremental analysis of the MOD problem for C. Laboratory for Computer Science Research Technical Report LCSR-TR-254, Department of Computer Science, Rutgers University (1995)
  55. B. G. Ryder and M. C. Paull, "Incremental Data Flow Analysis Algorithms", ACM Transactions on Programming Languages and Systems. (1988) 1–50
  56. Cooper, D. Keith, K. Kennedy, Fast Interprocedural Alias Analysis. Principles of Programming Language, Austin TX, (1989) 49-59
  57. K. D. Cooper and K. Kennedy, Interprocedural Side-effect Analysis. ACM SIGPLAN Notices, Vol 39, Issue 4, (2004) 217-228
  58. Z. Li, P. C. Yew and C. Zhu, An Efficient Data Dependence Analysis for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, Volume 1, Issue 1. ( 1990) 26-34
  59. D. Cooper, Keith, and K. Kennedy, "Efficient Computation of Flow Insensitive Interprocedural Summary",Proc of SIGPLAN ' 84 Symp. On Compiler Constr. , Montreal, Quebec, Vol. 19, No. 6 (June 1984) 247-258
  60. Intel Parallel Advisor, Available : http://software. intel. com/en-us/articles/intel-parallel-advisor/
  61. M. Kulkarni, K. Pingali, B. Walter,G. Ramanarayanan, K. Bala, and L. P. Chew. "Optimistic Parallelism Requires Abstractions", In PLDI'07, pages 211–222.
  62. C. Upson, The Application Visualiation System: A Computational Environment for Scientific Visualization, IEEECOmputer Graphics and Applications, Vol. 9 (1989) 30-42.
  63. Ronsse, M. and De Bosschere, K. , "Recplay: a fully integrated practical record/replay system," ACM Trans. Comput. Syst. , vol. 17, no. 2, pp. 133–152,1999.
  64. Steffan, J. G. , Colohan, C. B. , Zhai, A. , and Mowry, T. C. , "A scalable approach to thread-level speculation," in Proceedings of the 27th annual international symposium on Computer architecture, ISCA '00, (New York, NY, USA), pp. 1–12, ACM, 2000.
  65. Park, S. , Lu, S. , and Zhou, Y. , "Ctrigger: exposing atomicity violation bugs from their hiding places," in Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, ASPLOS '09, (New York, NY, USA), pp. 25–36, ACM, 2009.
  66. Yu, Y. , Rodeheffer, T. , and Chen, W. , "Racetrack: efficient detection of data race conditions via adaptive tracking," in Proceedings of the twentieth ACM symposium on Operating systems principles, SOSP '05, (New York, NY, USA), pp. 221–234, ACM, 2005
  67. Microsoft, CHESS: Find and Reproduce Heisenbugs in Concurrent Programs. http://research. microsoft. com/en-us/projects/chess/
  68. Intel Corporation, Intel Parallel Inspector. http://software. intel. com/en-us/articles/intel-parallel-inspector/
  69. Serebryany, K. and Iskhodzhanov, T. , "ThreadSanitizer: data race detection in practice," in Proceedings of the Workshop on Binary Instrumentation and Applications, WBIA '09, (New York, NY, USA), pp. 62–71, ACM, 2009.
  70. Microsoft, Concurrency Visualizer http://msdn. microsoft. com/en-us/library/dd537632. aspx/
  71. Intel Corporation, Intel Parallel Amplifier. http://software. intel. com/en-us/articles/intel-parallel-amplifier/
  72. Intel Corporation, Intel Parallel Advisor. http://software. intel. com/en-us/articles/intel-parallel-advisor/
  73. Prism: an analysis exploration and verification environment for software implementation and optimization on multicore architectures from CriticalBlue. http://www. criticalblue. com
  74. vfAnalyst: Analyze your sequential C code to create an optimized parallel implementation from VectorFabrics,http://www. vectorfabrics. com/
  75. Rul, S. , Vandierendonck, H. , and De Bosschere, K. , "Extracting coarse-grain parallelism in general-purpose programs",PPoPP '08, (New York, NY, USA), pp. 281–282, ACM, 2008
  76. Zhang, X. , Navabi, A. , and Jagannathan, S. , "Alchemist: A transparent dependence distance profiling infrastructure," in Proceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO '09, (Washington, DC, USA), pp. 47–58, IEEE Computer Society, 2009
  77. B. Lucas, G. D. Abraham, N. S. Collins, D. A. Epstein, D. L. Gresh, K. P. McAuliffe, An Architecture for a Scientific Visualization System, IEEE Computer Society Press Proceedings of Visualization (1992)
  78. Das, D. and Wu, P. , "Experiences of using a dependence profiler to assist parallelization for multi-cores," in IPDPS Workshops, pp. 1–8, 2010.
  79. Jeon, D. , Garcia, S. , Louie, C. , and Taylor, M. B. , "Kismet: parallel speedup estimates for serial programs," in Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications, OOPSLA '11, (New York, NY, USA), pp. 519–536, ACM, 2011.
  80. KorbinianMolitorisz, JochenSchimmel, Frank Otto, Automatic Parallelization Using AutoFutures, Automatic Parallelization Using AutoFutures, Multicore Software Engineering, Performance, and Tools, Lecture Notes in Computer Science Volume 7303, 2012, pp 78-81
  81. Moseley, T. , Connors, D. A. , Grunwald, D. , and Peri, R. , "Identifying potential parallelism via loop-centric profiling," in Proceedings of the 4th international conference on Computing frontiers, CF '07, (New York, NY, USA), pp. 143–152, ACM, 2007.
  82. Das, D. and Wu, P. , "Experiences of using a dependence profiler to assist parallelization for multi-cores," in IPDPS Workshops, pp. 1–8, 2010
  83. N. R. Tallent, and J. M. Mellor Crummey. "Effective performance measurement and analysis of multithreaded applications. " In PPoPP '09: Proceedings of the ACM SIGPLAN symposium on Principles and practice of parallel program- ming, 2009.
  84. T. E. Anderson, and E. D. Lazowska. "Quartz: A tool for tuning parallel program performance. " In SIGMETRICS, vol. 18, 1990
  85. Y. He, C. Leiserson, and W. Leiserson. "The Cilkview Scalability Analyzer. " In SPAA '10, Proceedings of the Symposium on Parallelism in Algorithms and Architectures, 2010
  86. M. Kulkarni, M. Burtscher, R. Inkulu, K. Pingali, and C. Casc¸aval. "How much parallelism is there in irregular applications?" In PPoPP '09: 2009
  87. T. Harris and K. Fraser,"Language Support for Lightweight Transactions", In OOPSLA'03, pages 388–402, 2003
  88. William F. Appelbe, John T. Stasko, Eileen Kraemer, "Applying Program Visualization Techniques to Aid Parallel and Distributed Program Development. ", Dept. of Computer Science, Georgia Institute of Technology. Atlanta, GA, Technical Report. GIT-CC 91/31 (1993)
  89. W. Blume, R. Doallo, R. Eigenmann, J. Grout, J. Hoeflinger, and T. Lawrence. "Parallel programming with Polaris", IEEE Computer (2002)
  90. M. Kim, H. Kim, and C. -K. Luk. "SD3: A scalable approach to dynamic data-dependence profiling. " Microarchitecture, IEEE/ACM International Symposium on, 2010
  91. Aditi Athavale, Priti Ranadive, M. N. Babu, Prasad Pawar, Sudhakar Sah, Vinay G. Vaidya, Chaitanya Rajguru, "Automatic Sequential to Parallel Code Conversion - The S2P Tool and Performance Analysis", Journal of Computing, GSTF, Oct 2011.
  92. Official homepage, Cilk project – MIT homepage Available : www. supertech. csail. mit. edu/cilk/
  93. Official homepage, Erlang programming language homepage, Available : www. erlang. org
  94. Official homepage, Go Programming language : Available : www. golang. org
  95. Official homepage, Haskell programming language, Avaiable : www. haskell. org
  96. Intel Corporation, Intel Threading Building Blocks. http://www. threadingbuildingblocks. org/
  97. M. W. Hall, B. R. Murphy, S. P. Amarasinghe, S. Liao, and M. S. Lam. "Interprocedural Analysis for Parallelization", In LCPC'06, pp 61–80
  98. Saturnino Garcia, DonghwanJeon, Chris Louie, Sravanthi Kota Venkata, and Michael Bedford Taylor,"Bridging the Parallelization Gap: Automating Parallelism Discovery and Planning", HotPar, 2nd USENIX workshop on hot topics in parallelism, Poster presentation, 2010.
  99. U. Banerjee, "Dependence Analysis for Supercomputing", Kluwer Academic Publishers, Norwell, MA, 1988
  100. http://www. cri. ensmp. fr/pips/, accessed Oct 2011
  101. Gabriele Jost, Haoqiang Jin, Jesus Labarta, and JuditGimenez, "Interfacing Computer Aided Parallelization and Performance Analysis", ICCS'03 International conference on Computational science, 2003 pp 181-190
  102. C. Ding, X. Shen, K. Kelsey, C. Tice, R. Huang, and C. Zhang. Software Behavior Oriented Parallelization. In PLDI'07, pages 223–234, San Diego, CA
Index Terms

Computer Science
Information Sciences

Keywords

Interactive Parallelization Parallel Program Assist Automatic Parallelization Parallel Programming Tools Multicore