Bernoulli Sparse Compiler Toolkit
The Bernoulli Sparse Compiler Toolkit (BSCT) automatically generates parallel and sequential sparse matrix codes, given the corresponding dense codes and the specification of the data formats. The main problems are the restructuring of computations to produce efficient simultaneous enumeration over multiple data structures, and the development of a proper interface for the specifcation of sparse matrix formats. BSCT solves this problems by viewing sparse and dense arrays as relations, and the execution of nested loops as the evaluation of relational quaeries. Experiements on the IBM SP-2 show that the performance of the code genreated by BSCT for common numerical kernels is competitive with hand-written libraries.
The theory underlying the BSCT can be found in Paul Stodghill's and Vladimir Kotlyar's dissertations. This mostly works is limited to matrix codes that are perfectly nested and dependence free. More recent work has removes these restrictions, but is not implemented in the BSCT.