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

• Official home page Message Passing Interface (MPI) Available : www. mpi-forum. org/
• official home page - Open MP, Available : www. openmp. org
• Sutter, H. , "The free lunch is over," Dr. Dobb's Journal, vol. 30, March 2005
• Per Stenstrom, The Paradigm Shift to MultiCores: Opportunities and Challenges, Appl. Comput. Math. (2007) 253-257
• VivekSarkar, Programming challenges for multicore Parallel systems, Presentation for Computer Science Department, Rice University. http://www. rice. edu
• McKinsley, Karthryn S. Automatic and Interactive Parallelization, PhD. Thesis, Computer Science, Rice University. Houston, Texas (1994) 12-32.
• 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.
• Minjang Kim, dynamic program analysis algorithms to assist parallelization, PhD. thesis proposal, Georgia Institute of Technology, 2011. pp 5-28.
• S. Sah and VinayG. Vaidya, Paradyn: A Dynamic Parallel Programming Tool, ICDCN, 12th International Conference on Distributed Computing and Networking, PhD forum (2010)
• ParMA - Parallel Programming for Multi-core Architectures, Available : http://www. parma-itea2. org
• Par4All homepage : URL : http://www. par4all. org
• 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
• 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.
• 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.
• 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.
• 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
• Andrew R. Bernat, Barton P. Miller, "Incremental Call-Path Profiling", Computer Sciences Department, University of Wisconsin. Madison, WI
• CathalBoogerd, Leon Moonen, "On the Use of Data Flow Analysis in Static Profiling", Software EvolutionResearch Lab, Delft University of Technology. The Netherlands
• "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
• NEC IMAPCAR Technical Document – www. nec. com
• Graham, Wagner and Susan, Efficient and Flexible Incremental Parsing, ACM Transactions of Programming Languages and Systems, Vol. 20 (1998)
• Barbara G. Ryder, A Position Paper on Compiler Time Program Analysis, Computer Science Dept. , Rutgers University (1997)
• Amdahl, Gene, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities". AFIPS Conference Proceedings, 1967, pp 483-485.
• Beth Tibbitts, PTP - PLDT Parallel Language Development Tools Overview, Status & Plans. Technical Report by IBM, (2007)
• 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)
• R. J. Abbott, Integrated Approach to Software Development. John Wiley and Sons (1986)
• 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
• 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
• 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)
• W. Ambrus, A Framework for Automatic Parallelization of Sequential Programs, Proceedings of the 7th International Conference on Volume 2 (2003) 11-13
• M. Girkar and C. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Transactions on Parallel and Distributed Systems (1992)
• Manish Gupta, SayakMukhopadhyay, Navin Sinha, ,Automatic Parallelization of Recursive Procedures, Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, (1999) 139 – 148
• 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)
• John Hughes , Why Functional Programming Matters Institutionen for Datavetenskap, Chalmers TekniskaHogskolaGteborg, SWEDEN, Circulated as Chalmers memo (1984)
• NirSavit, Dan Touitou, Software Transactional Memory, ACM-PODC, Ottawa Ontario, CA, 1995
• Official Website : "The Multicore Association", http:// www. multicore-association. org/
• NVIDIA Corporation. : NVIDIA CUDA Programming Guide. Technical Report. California. USA. (2008)
• 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
• Sudhakar Sah, Vinay G. Vaidya, A GPU Based Novel Design of Side Effect Analysis, ICOMEC, Goa, India, (2011) 137-143
• 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)
• 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
• 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
• 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)
• 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)
• 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/
• 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
• M. Kumar. "Measuring parallelism in computation-intensive scientific/engineering applications. " IEEE TOC, Sep 1988.
• Muhammed S. Al-Mulhem, Concurrent programming in VISO, Concurrency : Practice and Experience Concurrency, Pract. Exper. (2000) 281–288
• Pong M. I-pigs: An Interactive Graphical Environment for Concurrent Programming, Computer Journal (1991) 320 330
• Kramer J, Magee J, Ng K, "Graphical configuration programming", Computer 1989; 22(10):53–65.
• V. Sarkar,"Automatic partitioning of a program dependence graph into parallel tasks", In IBM Journal of Research and Development, pages 779–804, 1991.
• 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.
• 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
• 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)
• B. G. Ryder and M. C. Paull, "Incremental Data Flow Analysis Algorithms", ACM Transactions on Programming Languages and Systems. (1988) 1–50
• Cooper, D. Keith, K. Kennedy, Fast Interprocedural Alias Analysis. Principles of Programming Language, Austin TX, (1989) 49-59
• K. D. Cooper and K. Kennedy, Interprocedural Side-effect Analysis. ACM SIGPLAN Notices, Vol 39, Issue 4, (2004) 217-228
• 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
• 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
• Intel Parallel Advisor, Available : http://software. intel. com/en-us/articles/intel-parallel-advisor/
• M. Kulkarni, K. Pingali, B. Walter,G. Ramanarayanan, K. Bala, and L. P. Chew. "Optimistic Parallelism Requires Abstractions", In PLDI'07, pages 211–222.
• C. Upson, The Application Visualiation System: A Computational Environment for Scientific Visualization, IEEECOmputer Graphics and Applications, Vol. 9 (1989) 30-42.
• 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.
• 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.
• 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.
• 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
• Microsoft, CHESS: Find and Reproduce Heisenbugs in Concurrent Programs. http://research. microsoft. com/en-us/projects/chess/
• Intel Corporation, Intel Parallel Inspector. http://software. intel. com/en-us/articles/intel-parallel-inspector/
• 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.
• Microsoft, Concurrency Visualizer http://msdn. microsoft. com/en-us/library/dd537632. aspx/
• Intel Corporation, Intel Parallel Amplifier. http://software. intel. com/en-us/articles/intel-parallel-amplifier/
• Intel Corporation, Intel Parallel Advisor. http://software. intel. com/en-us/articles/intel-parallel-advisor/
• Prism: an analysis exploration and verification environment for software implementation and optimization on multicore architectures from CriticalBlue. http://www. criticalblue. com
• vfAnalyst: Analyze your sequential C code to create an optimized parallel implementation from VectorFabrics,http://www. vectorfabrics. com/
• 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
• 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
• 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)
• Das, D. and Wu, P. , "Experiences of using a dependence profiler to assist parallelization for multi-cores," in IPDPS Workshops, pp. 1–8, 2010.
• 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.
• 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
• 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.
• Das, D. and Wu, P. , "Experiences of using a dependence profiler to assist parallelization for multi-cores," in IPDPS Workshops, pp. 1–8, 2010
• 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.
• T. E. Anderson, and E. D. Lazowska. "Quartz: A tool for tuning parallel program performance. " In SIGMETRICS, vol. 18, 1990
• 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
• M. Kulkarni, M. Burtscher, R. Inkulu, K. Pingali, and C. Casc¸aval. "How much parallelism is there in irregular applications?" In PPoPP '09: 2009
• T. Harris and K. Fraser,"Language Support for Lightweight Transactions", In OOPSLA'03, pages 388–402, 2003
• 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)
• W. Blume, R. Doallo, R. Eigenmann, J. Grout, J. Hoeflinger, and T. Lawrence. "Parallel programming with Polaris", IEEE Computer (2002)
• M. Kim, H. Kim, and C. -K. Luk. "SD3: A scalable approach to dynamic data-dependence profiling. " Microarchitecture, IEEE/ACM International Symposium on, 2010
• 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.
• Official homepage, Cilk project – MIT homepage Available : www. supertech. csail. mit. edu/cilk/
• Official homepage, Erlang programming language homepage, Available : www. erlang. org
• Official homepage, Go Programming language : Available : www. golang. org
• Official homepage, Haskell programming language, Avaiable : www. haskell. org
• Intel Corporation, Intel Threading Building Blocks. http://www. threadingbuildingblocks. org/
• 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
• 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.
• U. Banerjee, "Dependence Analysis for Supercomputing", Kluwer Academic Publishers, Norwell, MA, 1988
• http://www. cri. ensmp. fr/pips/, accessed Oct 2011
• 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
• 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