T-106.290 Ohjelmoinnin laboratoriotyöt

Tiedon esitysmuodon merkitys suorituskyvylle

Yleiskuvaus: Tässä tehtävässä tutustutaan tiedon sijoittelun (data layout) merkitykseen ohjelmien suorituskyvylle. Sama perustietorakenne voidaan sijoittaa muistiin useilla tavoilla. Nykyiset konearkkitehtuurit (välimuistit) ovat nopeita sellaisille tavoille, joissa tieto pystytään käsittelevään paikallisesti.

Tehtävä: Toteuta suunnattu verkko käyttäen kolmea tiedon sijoitustapaa tai tietorakennetta. (Voit siis muuttaa sekä tietorakennetta että sen sijoittelua muistiin.) Solmujen muistiin sijoittelun lisäksi voit vaihdella seuraajalistojen sijoittelua. Mittaa sijoittelutapojen vaikutus verkon syvyyshaulle.

Kirjallisuus:

Black, J.R., Marten, C.U. and Hongbin, Q. Graph and Hashing Algorithms for Modern Architectures: Desing and Performance. Proceeding of the second Workshop on Algorithm Engineering WAE'98, Saarbrücken, August 20-22, 1998.

Chilimbi, T.M., Hill, M.D. and Larus, J.R. Cache-conscious structure layout. In Proceedings of the ACM SIGPLAN'99 Conference on Programming Language Design and Implementation, May 1999.

Cormen, T.H., Leiserson, C.E. and Rivest, R.L. Introduction to Algorithms. MIT Press, Cambridge, 1986.

Grunwald, D., Zorn, B. and Henderson, R. Improving the Cache Locality of Memory Allocation. In Proceedings of the ACM SIGPLAN'93 Conference on Programming Language Design and Implementation, June 1993.

Stallings, W., Computer Organization and Architecture, Prentice-Hall International, Inc., 1996.