next up previous
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 $ nxt$ or $ prv$ and whose elements point to binary trees; (ii) as SHSEL $ (n_4,tree)$=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 ($ n_4$, $ n_5$ and $ n_6$) 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 $ nxt$ or $ prv$.

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 [3]. 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.

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 up previous
Next: Barnes-Hut N-body simulation Up: Experimental results Previous: Progressive analysis
Rafael Asenjo Plaza 2002-02-19