next up previous
Next: Working example and sparse Up: Experimental results Previous: Experimental results


Progressive analysis

As we have seen, the set of properties associated with a node allows the compiler to keep in separate nodes those memory locations with different properties. Obviously, the number of nodes in the RSRSGs depends on the number of properties and also on the range of values these properties can take. The higher the number of properties the better the accuracy in the memory configuration representation, but also the larger the RSRSGs and memory wastage.

Fortunately, not all the properties are needed to achieve a precise description of the data structure in all the codes. That is, simpler codes can be successfully analyzed as fewer properties are taken into account, and complex programs will need more compilation time and memory due to all the properties that have to be considered. Bearing this in mind, we have implemented the compiler to carry out a progressive analysis which starts with fewer constraints to summarize nodes, but, when necessary, these constraints are increased to reach a better approximation of the data structure used in the code.

More precisely, the compiler analysis comprises three levels: $ L_1$, $ L_2$, and $ L_3$, from less to more complexity as we explain next:

With this compiler we have analyzed several C codes: the one described in Sect. 2.1 (working example), the sparse Matrix by vector multiplication, the sparse Matrix by Matrix multiplication, the Sparse LU factorization, and the Barnes-Hut code. The first four codes were successfully analyzed in the first level of the compiler, $ L1$. However, for the Barnes-Hut program the highest accuracy of the RSRSGs was obtained in the last level, $ L3$, as we explain in Sect. 5.3. All these codes where analyzed by our compiler in a Pentium III 500 MHZ with 128 MB main memory. The time and memory required by the compiler are summarized in Table 1. The particular aspects of these codes are described next.


Table 1: Time and space required by the compiler to analyze several codes
  Working Ex. S.Mat-Vec S.Mat-Mat S.LU fact. Barnes-Hut
Level L1 / L2 / L3 L1 / L2 / L3 L1 / L2 / L3 L1 L1 / L2 / L3
Time 0'09''/0'15''/0'16'' 0'03''/0'05''/0'07'' 0'51''/1'36''/1'57 12'15'' 12'45''/1'27''/2'33''
Space (MB) 2.11/2.78/3.02 1.37/1.85/2.17 8.13/11.45/12.68 99.46 37.82/8.82/8.94



next up previous
Next: Working example and sparse Up: Experimental results Previous: Experimental results
Rafael Asenjo Plaza 2002-02-19