   Next: Barnes-Hut N-body simulation Up: Experimental results Previous: Progressive analysis

## Working example and sparse matrix codes

We first refer in this subsection to the code that generates, traverses, and modifies the data structure presented in Fig. 3 (a). A compact representation of the resulting RSRSG for the last sentence of the code can be seen in Fig. 3 (b). Although we do not show the code due to space constraints, we have to mention that this code presents an additional difficulty due to some tree permutations being carried out during data structure modification. Summarizing, after the compiler analyzes this code, the compact representation of the resulting RSRSG for the last sentence of the program (Fig. 3 (b)) accurately describes the data structure depicted in Fig. 3 in the sense that: (i) the compiler successfully detects the doubly linked list which is acyclic by selectors or and whose elements point to binary trees; (ii) as SHSEL =0, we can say that two different items of the header list cannot point to the same tree; (iii) at the same time, as no tree node ( , and ) is shared, we can say that different trees do not share items; and (iv) the same happens for the doubly linked list pointed to by the tree leaves: all the lists are independent, there are no two leaves pointing to the same list, and these lists are acyclic by selectors or .

Besides this, our compiler has also analyzed three sparse codes which generate, traverse, and modify complex dynamic data structures. A more detailed description of these codes and the compiler results is in . However, we just summarize here the functionality of these codes, for which the compiler generates very accurate RSRSGs that precisely describe the real data structure used in the codes.

• Sparse matrix-vector multiplication. Here we deal with an irregular code which implements a sparse matrix by vector multiplication, where the vectors are doubly linked lists and the matrix is a doubly linked list with pointers to other doubly linked lists which store the matrix rows.

• Sparse matrix-matrix multiplication. This code implements a sparse matrix by matrix multiplication, . All the sparse matrices are also stored as a doubly linked list with pointers to sparse rows. Note that matrix A grows during the multiplication process.

• Sparse LU factorization. This code solves non-symmetric sparse linear systems by applying the LU factorization of the sparse matrix. Here, the sparse matrix is a list of pointers to sparse columns. However, this code is much more complex to analyze due to the partial pivoting and column permutation which takes place in the factorization in order to provide numerical stability and preserve the sparseness.

As we mentioned, all these codes are accurately analyzed in the compiler L1 level. However, in Table 1 we also present time and memory requirements of levels L2 and L3 to illustrate how increasing the number of properties of the compiler usually leads to higher compilation times and larger memory pools. For the Sparse LU factorization, our compiler runs out of memory in L2 and L3 in our 128 MB Pentium III and, therefore, only values for L1 level are provided. The exception in Table 1 is due to the Barnes-Hut N-body simulation which is described next.   Next: Barnes-Hut N-body simulation Up: Experimental results Previous: Progressive analysis
Rafael Asenjo Plaza 2002-02-19