International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 9, No. 9, 8 Sep. 2017
Cover page and Table of Contents: PDF (size: 950KB)
Performance Analysis of a System that Identifies the Parallel Modules through Program Dependence Graph
Full Text (PDF, 950KB), PP.37-45
Views: 0 Downloads: 0
Author(s)
Shanthi Makka
1,*
B.B.Sagar
2
Index Terms
Abstract Syntax Tree, Program Dependence Graph, Control Dependence Graph, Data Dependence Graph, Performance Analysis, Parallel Modules
Abstract
We have proposed a new approach to identify segments, which can be executed simultaneously, or coextending to achieve high computational speed with optimized utilization of available resources. Our suggested approach is divided into four modules. In first module we have represented a program segment using Abstract Syntax Tree (AST) along with an algorithm for constructing AST and in second module, this AST has been converted into Program Dependence Graph (PDG), the detailed approach has been described in section II, The process of construction of PDG is divided into two steps: First we construct a Control Dependence Graph (CDG, In second step reachability definition algorithm has been used to identify data dependencies between the various modules of a program by constructing Data Dependence Graph (DDG). In third module an algorithm is suggested to identify parallel modules, i.e., the modules that can be executed simultaneously in the section III and in fourth module performance analysis is discussed through our approach along with the computation of time complexity and its comparison with sequential approach is demonstrated in a pictorial form.
Cite This Paper
Shanthi Makka, B.B.Sagar, "Performance Analysis of a System that Identifies the Parallel Modules through Program Dependence Graph", International Journal of Intelligent Systems and Applications(IJISA), Vol.9, No.9, pp.37-45, 2017. DOI:10.5815/ijisa.2017.09.05
Reference
[1]Mathieu Verbaere, Ran Ettinger and Oege de Moor JunGL. A Scripting Language for Refactoring, 28th International Conference on Software Engineering, pp. 172–181, 2006.
[2]Makka Shanthi, and B. B. Sagar. "A New Approach for Optimization of Program Dependence Graph using Finite Automata." Indian Journal of Science and Technology 9.38 (2016).
[3]G. E. Moore, “Readings in Computer Architecture. chapter Cramming more components onto integrated circuits,” Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2000, pp.56-59.
[4]D. Dig, "A refactoring approach to parallelism," Software, IEEE 28.1 (2011): 17-22.
[5]Baxter, Ira D., et al. "Clone detection using abstract syntax trees." Software Maintenance, 1998. Proceedings, International Conference on. IEEE, 1998.
[6]KUCK, D. J., KUHN, R. H., PADUA, D. A., LEASURE, B., AND WOLFE, M. Dependence graphs and compiler optimizations. In 8th Annual ACM Symposium on Principles of Programming Languages (Williamsburg, VA, Jan. 26-28,1981), ACM, New York, 207-218.
[7]OTTENSTEIN, K. J. Data-flow graphs as an intermediate program form. Ph.D. dissertation, Computer Sciences Dept., Purdue University, Lafayette, IN, August 1978.
[8]AHO, A. V., SETHI, R., AND ULLMAN, J. D. Compilers: Principles, Techniques, and Took. Addison-Wesley, 1986. [An alternative reference is this book’s predecessor, AHO, A. V. AND ULLMAN, J. D. Principles of Compiler Design. Addison-Wesley, 1977.)
[9]W. F. Opdyke, Refactoring: A Program Restructuring Aid in Designing Object-Oriented Application Frameworks Ph.D. thesis, University of Illinois at Urbana Champaign, 1992.
[10]Pearce, David J., and Paul HJ Kelly. "A dynamic topological sort algorithm for directed acyclic graphs." Journal of Experimental Algorithmics (JEA) 11 (2007): 1-7.
[11]M. Aldinucci, M. Danelutto, P. Kilpatrick, M. Meneghin, and M. Torquati. Accelerating Code on Multi-cores with FastFlow. In Euro-Par, pages 170–181, 2011.
[12]Ferrante, Jeanne, Karl J. Ottenstein, and Joe D. Warren. "The program dependence graph and its use in optimization." ACM Transactions on Programming Languages and Systems (TOPLAS) 9.3 (1987): 319-349.
[13]Jain, Sanjay, and Efim Kinber. "Parallel learning of automatic classes of languages." International Conference on Algorithmic Learning Theory. Springer International Publishing, 2014.
[14]Alhazov, Artiom, Chang Li, and Ion Petre. "Computing the graph-based parallel complexity of gene assembly." Theoretical Computer Science 411.25 (2010): 2359-2367.
[15]Korel, Bogdan. "The program dependence graph in static program testing."Information Processing Letters 24.2 (1987): 103-108.
[16]Meinke, Karl. "Topological methods for algebraic specification." Theoretical computer science 166.1 (1996): 263-290.
[17]Toda, Seinosuka. "On the complexity of topological sorting." Information processing letters 35.5 (1990): 229-233.
[18]Tekchandani, Rajkumar, Rajesh Bhatia, and Maninder Singh. "Semantic code clone detection for Internet of Things applications using reaching definition and liveness analysis." The Journal of Supercomputing (2016): 1-28.
[19]Harrold, Mary Jean, Brian Malloy, and Gregg Rothermel. "Efficient construction of program dependence graphs." ACM SIGSOFT Software Engineering Notes. Vol. 18. No. 3. ACM, 1993.
[20]Ghiya, Rakesh, and Laurie J. Hendren. "Connection analysis: A practical interprocedural heap analysis for C." International Journal of Parallel Programming 24.6 (1996): 547-578.
[21]Singh, Paramvir. "Hybrid Black Hole Algorithm for Bi-Criteria Job Scheduling on Parallel Machines." International Journal of Intelligent Systems and Applications 8.4 (2016): 1.