Instrumentation of OpenMP task scheduling

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorHirvisalo, Vesa
dc.contributor.authorRasa, Marko
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.supervisorHeljanko, Keijo
dc.date.accessioned2015-05-13T09:49:05Z
dc.date.available2015-05-13T09:49:05Z
dc.date.issued2015-05-11
dc.description.abstractParallel computing models, such as tasking, are increasingly important as the modern processors are scaled mostly by adding processor cores instead of increasing clock speed. Scheduling the tasks requires computational resources and can be implemented with either software or hardware. The goal of the thesis has been to develop a measurement system that is able to yield the basic tasking performance metrics of parallel program execution. The main challenge in developing such system is the overhead caused by the measuring, especially when tasks are extremely fine grained. An additional aim for the thesis has been understanding the scheduling properties of OpenMP task parallelism model. We selected version 4.9 of the GCC compiler and its runtime (GOMP) as the concrete target of our study. The parts of the OpenMP 4.0 specification that are essential for the study are implemented by the compiler. The task scheduling operates by assigning tasks to worker threads. In doing so, it handles dependence structures and task queues, which require synchronisation to ensure correct operation. The studied GOMP implementation uses locking for that purpose. We designed and implemented a measuring system using software performance counters by instrumenting the runtime system (GOMP) and hardware counters by calling PAPI (Performance Application Programming Interface) functions inside the runtime system. We tested the measurement system by implementing a task parallel version of AES (Advanced Encryption Standard), which yields small granularity tasks. In our tests we observed parallel scaling up to four threads, at which point lock congestion rose rapidly. To understand the performance of our measurement systems, we compared the performance of instrumented and non-instrumented versions of the runtime system. The developed measurement system yields low overhead.en
dc.description.abstractRinnakkaislaskentamallit kuten tehtävärinnakkaisuus ovat yhä tärkeämpiä modernien suorittimien skaalautuessa enimmäkseen suoritinytimien lisäämisellä kellotaajuuden kasvattamisen sijaan. Tehtävien vuoronnus vaatii laskentaresursseja ja voidaan toteuttaa joko ohjelmistolla tai laitteistolla. Tämän työn tavoite on ollut kehittää mittausjärjestelmä, joka antaa perusmittareita tehtävärinnakkaisuuden tehokkuudesta. Päähaaste järjestelmän kehittämisessä on mittauksen aiheuttama kuormitus, erityisesti kun tehtävät ovat erittäin hienojakoisia. Lisätavoite työlle on ollut ymmärtää vuoronnuksen ominaisuuksia OpenMP:n tehtävärinnakkaismallissa. Valitsimme version 4.9 GCC kääntäjästä ja sen ajonaikaisen järjestelmän (GOMP) konkreettiseksi kohteeksi tutkimukselle. Kääntäjä toteuttaa työlle oleelliset osat OpenMP 4.0 määritelmästä. Tehtävien vuoronnus toimii jakamalla tehtäviä työsäikeille. Tämän mahdollistamiseksi sen täytyy käsitellä riippuvuusrakenteita ja tehtäväjonoja, jotka vaativat koordinointia. Tutkittu GOMP toteutus käyttää lukkoja tähän tarkoitukseen. Suunnittelimme ja toteutimme mittausjärjestelmän käyttämällä ohjelmistotehokkuuslaskureita instrumentoimalla ajonaikaisen järjestelmän (GOMP) ja laitteistotehokkuuslaskureita kutsumalla PAPI (Performance Application Programming Interface) funktioita ajonaikaisen järjestelmän sisällä. Testasimme mittausjärjestelmän toteutteuttamalla tehtävärinnakkaisen version AES:stä (Advanced Encryption Standard), joka tuottaa pienijakoisia tehtäviä. Testeissä havaitsimme rinnakkaista skaalautumista neljään säikeeseen asti, jonka jälkeen lukon ruuhkautuminen kasvoi nopeasti. Mittausjärjestelmämme suorituskyvyn ymmärtämiseksi vertasimme instrumentoidun ja instrumentoimattoman ajonaikaisen järjestelmän suorituskykyä. Kehitetyllä mittausjärjestelmällä on matala mittauskuormitus.fi
dc.format.extent58
dc.format.mimetypeapplication/pdfen
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/16034
dc.identifier.urnURN:NBN:fi:aalto-201505142687
dc.language.isoenen
dc.programmeTietotekniikan koulutusohjelmafi
dc.programme.majorOhjelmistotekniikkafi
dc.programme.mcodeT3001fi
dc.rights.accesslevelopenAccess
dc.subject.keywordparallelen
dc.subject.keywordtask parallelismen
dc.subject.keywordruntime systemen
dc.subject.keywordmeasuringen
dc.subject.keywordOpenMPen
dc.titleInstrumentation of OpenMP task schedulingen
dc.titleOpenMP tehtävävuoronnuksen instrumentointifi
dc.typeG2 Pro gradu, diplomityöen
dc.type.okmG2 Pro gradu, diplomityö
dc.type.ontasotMaster's thesisen
dc.type.ontasotDiplomityöfi
dc.type.publicationmasterThesis
local.aalto.idinssi51339
local.aalto.openaccessyes
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
master_Rasa_Marko_2015.pdf
Size:
441.24 KB
Format:
Adobe Portable Document Format