Tuning Performance of Multi-threaded programs

Abstract

Diplomityö tarkastelee säikeistettyä ohjelmointia rinnakkaisohjelmoinnin ylemmällä hierarkiatasolla tarkastellen erityisesti hypersäikeistysteknologiaa. Työssä tarkastellaan hypersäikeistyksen hyviä ja huonoja puolia sekä sen vaikutuksia rinnakkaisalgoritmeihin. Työn tavoitteena oli ymmärtää Intel Pentium 4 prosessorin hypersäikeistyksen toteutus ja mahdollistaa sen hyödyntäminen, missä se tuo suorituskyvyllistä etua. Työssä kerättiin ja analysoitiin suorituskykytietoa ajamalla suuri joukko suorituskykytestejä eri olosuhteissa (muistin käsittely, kääntäjän asetukset, ympäristömuuttujat...). Työssä tarkasteltiin kahdentyyppisiä algoritmeja: matriisioperaatioita ja lajittelua. Näissä sovelluksissa on säännöllinen muistinkäyttökuvio, mikä on kaksiteräinen miekka. Se on etu aritmeettis-loogisissa prosessoinnissa, mutta toisaalta huonontaa muistin suorituskykyä. Syynä siihen on nykyaikaisten prosessorien erittäin hyvä raaka suorituskyky säännöllistä dataa käsiteltäessä, mutta muistiarkkitehtuuria rajoittaa välimuistien koko ja useat puskurit. Kun ongelman koko ylittää tietyn rajan, todellinen suorituskyky voi pudota murto-osaan huippusuorituskyvystä.

The thesis discusses the multithreaded programming as the upper level in parallel programming hierarchy, with focus on the hyper-threading technology. It discusses its pros and cons and its effects on various parallel algorithms. The motivation of this thesis is to understand hyper-threading as is implemented in Intel Pentium 4 processor and to enable its utilization where it brings performance advantage. A large set of benchmarking programs was executed in varying conditions (memory access pattern, compiler settings, environment variables…) to collect and analyze performance metrics. Two sets of algorithms were evaluated: matrix operations and sorting. These applications have regular data access pattern, which is a double sided weapon. While this is an advantage in arithmetic-logic processing, memory performance suffers. The reason is that the raw performance of today’s processors in processing regular data is very good, but memory architecture is limited by the size of caches and various buffers and once the problem size crosses certain limit, the actual performance can drop to a fraction of the top performance.