Advanced compiler optimizations for sparse computations
Aart J. C. Bik, Harry A. G. Wijshoff · 1993
Regular data dependence checking onsparsecodesusually resultsin very conservative estimates of actual dependences that will occur at run-time.Clearly, this is caused by the usage of compact data structures that are necessary to exploit sparsity in order to reduce storage requirements and computational time.However, if the compiler is presented with dense code and automatically converts it into code that operates on sparse data structures, then the dependence information obtained by analysis on the original code can be used to exploit potential concurrency inthe generated code.In this paper we present synch~onization generating and manipulating techniques that are based on this concept. PreliminariesIn this section we summarize data dependence theory, and discuss the elimination of dependence by automatic conversion into sparse code.