ADVANCED COMPILER OPTIMIZATIONS FOR SPARSE COMPUTATIONS

Regular data dependence checking on sparse codes usually results in ve ry conservative estimates of the actual dependences occurring at run-t ime. Clearly, this is caused by the usage of compact data structures n ecessary to exploit sparsity in order to reduce storage requirements a nd computational time. However, if the compiler is presented with dens e code and automatically converts it into code operating on sparse dat a structures, then the dependence information obtained by analysis of the original code can be used to exploit potential concurrency in the generated sparse code. In this paper, we explore synchronization gener ating and manipulating techniques based on this concept. (C) 1995 Acad emic Press Inc.