A REVIEW ON DEPENDENCE ANALYSIS AND PARALLELIZATION TECHNIQUES

With the new era of multicore processors it is required to improve the execution speed of the program. Consequently, developing parallel programs is the primary concern of the multicore era. The main challenge is to convert the sequential algorithm to parallel. Conversion of the sequential algorithm to parallel program without changing the output requires analyzing the set of constraints called dependency. Dependency specifies the basis for powerful transformation systems that enhance the implicit parallelism present within the program. The applications that are implemented with data structures like trees, queues and graphs is the most difficult problem for parallelization as these data structure deals with pointer. Graph Isomorphism is a technique of matching the structure of one graph with another and if only subpart of a graph is matched it is known as subgraph isomorphism. Graph and subgraph Isomorphism is one of the most highly-studied problems in the various field of computer science. In this paper we have studied the data dependency, control dependency, different parallelization techniques and the graph isomorphism problem. Keywords—Data dependency, Control dependency, Graph Isomorphism, Subgraph Isomorphism, Parallelization