Automatic parallelization of divide and conquer algorithms

摘要: Divide and conquer algorithms are a good match for modern parallel machines: they tend to have large amounts of inherent parallelism work well with caches deep memory hierarchies. But these pose challenging problems parallelizing compilers. They usually coded as recursive procedures often use pointers into dynamically allocated blocks pointer arithmetic. All features incompatible the analysis in traditional compilers.This paper presents design implementation compiler that is designed parallelize divide whose subproblems access disjoint regions arrays. The foundation flow-sensitive, context-sensitive, interprocedural algorithm. A range symbolic build on information extract bounds accessed by (potentially recursive) allows find procedure calls can execute without violating data dependences. generates code executes parallel. We used several programs algorithms. Our results show perform exhibit speedup.