next up previous contents
Next: Statistical Models Up: Analytical Modeling Previous: Modeling with Scalar Parameters

Modeling with Functions

 

In order to express the effects of hardware and software parameters on the execution time, several researchers adopt mathematical functions instead of scalar values in their models. Using functions improves the flexibility and expressiveness of the models, but can also increase the complexity of the models, due to the need to determine the shape and coefficients of the functions. Scalar parameter models are a simplified case of modeling with functions, where the functions are constants.

An experimental approach for performance optimization is presented in [Brewer1995]. The idea is to have a library containing various implementations of common procedures and their models. By providing several coordinated implementations in one library, we greatly increase the chance that at least one performs well on each target platform. The models are created from environment variables, their possible values, and the possible terms that will compose the formula model. The models are fittings (calculated via least squares minimization) of the terms given by the user to some profiling data. Results indicate that the approach provides good prediction of the best implementation for a given architecture, but the numerical predictions are not accurate. This approach is not able to capture the influence of machine configurations on the procedure behavior. Data placement, for example, can change completely the behavior of a procedure. Procedures that perform well in isolation may perform poorly due to the amount of communication caused by the data placement that precedes them.

A data reference modeling technique to estimate cache miss ratios in cache-coherent multiprocessors is proposed in [Tsai and Agarwal1993]. Cache behavior is captured as a function of the problem size, number of processors, and cache line size. It can also be expressed via the number of accesses, remote writes, and first-time fetches. They consider only two kinds of misses: cold start and write invalidations. They do not make any assumptions regarding access probabilities, rather they derive the cache behavior ``exactly'' from the algorithm (via mental simulation). The derivation of cache misses by algorithm inspection is not a generally applicable technique, especially for applications with complex communication patterns. Also, the mental simulation technique does not treat misses related to synchronization variables. Results show that the predictions are accurate for data-independent algorithms, but not as good for data-dependent examples. They used simulation to validate their results, and the maximum error in predictions was about 18%. This approach differs from other functional work (e.g., [Brewer1995]) in the sense that the models produced are descriptive (i.e. the models express the internal behavior of the parallel system). Descriptive models are very important in understanding the behavior of parallel systems.

In the approaches presented above, there is an interesting contrast concerning how the functions and their coefficients are determined. In [Brewer1995], they focus on empirically approximate functions that are not descriptive. Tsai and Agrawal infer the functions explicitly from the program behavior but without an empirical-based determination of coefficients. The common point in all examples is the use of functions (instead of scalar values) to express the influence of environmental factors on the models. Non-descriptive models do not help in understanding the performance of parallel programs, however, approaches like [Tsai and Agarwal1993], which rely entirely on the user's knowledge to generate descriptive models, are not desirable as well, because of the effort and expertise required from the user.


next up previous contents
Next: Statistical Models Up: Analytical Modeling Previous: Modeling with Scalar Parameters

Wagner Meira
Wed Feb 28 15:37:47 EST 1996