Dependency analysis system and method

Details Dependency analysis system and method Dependency analysis system and method

2004-06-24

2009-08-25

Zhen, Wei Y (Department: 2191)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S159000, C717S161000

Reexamination Certificate

active

07581215

ABSTRACT:
We present a technique to perform dependence analysis on more complex array subscripts than the linear form of the enclosing loop indices. For such complex array subscripts, we decouple the original iteration space and the dependence test iteration space and link them through index-association functions. The dependence analysis is performed in the dependence test iteration space to determine whether the dependence exists in the original iteration space. The dependence distance in the original iteration space is determined by the distance in the dependence test iteration space and the property of index-association functions. For certain non-linear expressions, we show how to transform it to a set of linear expressions equivalently. The latter can be used in dependence test with traditional techniques. We also show how our advanced dependence analysis technique can help parallelize some otherwise hard-to-parallelize loops.

REFERENCES:
patent: 4833606 (1989-05-01), Iwasawa et al.
patent: 5317734 (1994-05-01), Gupta
patent: 5842022 (1998-11-01), Nakahira et al.
patent: 5852734 (1998-12-01), Komatsu et al.
patent: 5901318 (1999-05-01), Hsu
patent: 5974538 (1999-10-01), Wilmot, II
patent: 6282704 (2001-08-01), Iitsuka
patent: 6374403 (2002-04-01), Darte et al.
patent: 6516463 (2003-02-01), Babaian et al.
patent: 6615403 (2003-09-01), Muthukumar et al.
patent: 6651246 (2003-11-01), Archambault et al.
patent: 2004/0098711 (2004-05-01), Song et al.
patent: 2004/0123280 (2004-06-01), Doshi et al.
U Pugh et al., “Constraint-Based Array Dependency Analysis”, ACM, pp. 635-678, 1998.
V Pugh et al. “Nonlinear Array Dependency Analysis”, University of Maryland, College Park, MD, pp. 1-11, 1994.
Pugh et al., “Constraint-Based Array Dependency Analysis,” ACM, pp. 635-678, 1998.
Pugh et al., “Nonlinear Array dependency Analysis,” University of Maryland, College Park, Maryland, pp. 1-11, 1994.

Affiliated with

Also associated with

Rating

Dependency analysis system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dependency analysis system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dependency analysis system and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4084012