Time: Monday, 19 March 2001, 11.15 - 13.00
Place: N037 at DIKU

The defence will be held in Danish/Nordisk.

Abstract:

The pure-C cost model, a simple but realistic model for analysing the performance of programs, was first presented by Katajainen and Träff in 1997. The model was refined by Bojesen, Katajainen and Spork in 1999 in to include the cost of cache misses. In this thesis the model is further refined to include the cost of branch mispredictions. Furthermore, it is discussed how to modify the pure-C cost model to account for the instruction level parallelism of today's superscalar processors.

The efficiency of various mergesort and binary search programs is analysed under the refined model.

It is concluded that branch prediction has a considerable effect on the performance of programs and that the refinement of the pure-C cost model does to some extent improve the accuracy of the model. In spite of this it is concluded that the pure-C model is not sufficient for describing modern computers. The effect of instruction level parallelism need to be taken into account as well.