Design, Implementation and Evaluation of Efficient Data Storage Algorithms in Segmented Memory Model

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorSoisalon-Soininen, Eljas
dc.contributor.authorHuttunen, Janne
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.supervisorSoisalon-Soininen, Eljas
dc.date.accessioned2014-11-11T12:04:05Z
dc.date.available2014-11-11T12:04:05Z
dc.date.issued2014-11-03
dc.description.abstractThe data structures and algorithms used for storing and manipulating the ever growing data sets are the most crucial factor that affects the performance of a computer based system. During the past decade or so, most systems have begun to provide a standard set of high performance data structures either as system libraries or via direct support in the programming languages. Some legacy systems however have not quite kept up with this development and still require additional effort from the programmer to achieve good performance scalability. The objective of this work is to design, implement and evaluate a suitable set of selected data structures on top of one such legacy system, the DX 200 telecommunications platform. This task is complicated by the somewhat eccentric nature of the platform including the memory model it uses. While the modern IA-32 CPU hardware still fully supports the segmented memory model, the world has almost completely moved on and left it behind. In practice this means that it is almost impossible to get any modern high quality tools like e.g. compilers for it and the performance of segment operations hasn't been nearly as aggressively optimized as other CPU functions. All these things always need to be taken into consideration when trying to implement high performance software for the platform and it is almost impossible to implement anything without making at least some trade-offs due to them. The end result of this work is a tested standard library for the DX 200 platform that implements two types of lists and three types of binary trees and can be used as a basis for future expansion and further evaluation of implementation alternatives. The evaluation done on the implementation clearly shows that even in this kind of system, the balanced trees scale very nicely while the array that is the only data structure provided natively by the used programming languages doesn't scale all that well. This result is totally in line with all the theoretical background and so for its part acts as further proof of the validity of the produced implementation.en
dc.description.abstractAlati kasvavien datajoukkojen tallennukseen ja käsittelyyn käytetyt tietorakenteet ja algoritmit ovat kaikista kriittisimmät tekijät, jotka vaikuttavat tietokonepohjaisen järjestelmän suorituskykyyn. Noin viimeisimmän kuluneen vuosikymmenen aikana useimmat järjestelmät ovat alkaneet tarjota yleistä joukkoa korkean suorituskyvyn tietorakenteita joko kirjastoina tai ohjelmointikielen tarjoaman suoran tuen kautta. Jotkin vanhat järjestelmät eivat kuitenkaan ole aivan pysyneet mukana tässä kehityksessä ja yhä vaativat ohjelmoijalta ylimääräistä vaivaa hyvän suorituskyvyn saavuttamiseksi. Tämän työn tavoite on suunnitella, toteuttaa ja evaluoida sopiva kokoelma tietorakenteita erään tällaisen järjestelmän – DX 200 -tietoliikennealustan – päällä. Tätä vaikeuttaa alustan jokseenkin erikoinen luonne mukaan lukien sen käyttämä muistimalli. Vaikka nykyaikainen IA-32 -suoritin yhä tukee segmentointia, maailma on lähes täysin siirtynyt eteenpäin ja jättänyt sen jälkeensa. Käytännössa on lähes mahdotonta saada sille mitään nykyaikaisia työkaluja, kuten kääntäjiä, eikä segmenttioperaatioita ole optimoitu läheskään yhtä aggressiivisesti kuin muita suorittimen toimintoja. Kaikki tämä tulee aina ottaa huomioon, kun yritetään toteuttaa alustalle suorituskykyistä ohjelmistoa ja on lähes mahdotonta toteuttaa mitään ilman vähintään joitain kompromisseja. Tämän työn lopputuloksena on testattu kirjasto DX 200 -alustalle, joka toteuttaa kaksi erityyppistä listaa ja kolme binääripuuta. Sitä voidaan myöhemmin tarvittaessa laajentaa tai käyttää erilaisten toteutusvaihtoehtojen tutkimiseen. Toteutukselle tehty testaus osoittaa, että myös tällaisessa järjestelmässä tasapainotetut puut skaalautuvat kauniisti toisin kuin taulukot, jotka ovat ainoa tietorakenne, jonka käytetyt ohjelmointikielet tarjoavat suoraan. Tämä tulos on täysin linjassa teoreettisten odotusten kanssa ja näin omalta osaltaan myös todistaa tehdyn toteutuksen oikeellisuuden.fi
dc.format.extent65 + 11
dc.format.mimetypeapplication/pdfen
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/14447
dc.identifier.urnURN:NBN:fi:aalto-201411123024
dc.language.isoenen
dc.programmeTietotekniikan koulutusohjelmafi
dc.programme.majorOhjelmistotekniikkafi
dc.programme.mcodeT3001fi
dc.rights.accesslevelopenAccess
dc.subject.keywordsegmenten
dc.subject.keywordmemory modelen
dc.subject.keywordalgorithmen
dc.subject.keywordbinary search treeen
dc.subject.keywordred-black treeen
dc.subject.keywordsplay treeen
dc.subject.keywordsegmenttifi
dc.subject.keywordmuistimallifi
dc.subject.keywordalgoritmifi
dc.subject.keywordbinäärinen hakupuufi
dc.subject.keywordpunamusta puufi
dc.subject.keywordsplay-puufi
dc.titleDesign, Implementation and Evaluation of Efficient Data Storage Algorithms in Segmented Memory Modelen
dc.titleTehokkaiden tiedonhallinta-algoritmien suunnittelu, toteutus ja evaluointi segmentoidussa muistimallissafi
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.digifolderAalto_92317
local.aalto.idinssi50050
local.aalto.openaccessyes
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
master_Huttunen_Janne_2014.pdf
Size:
697.66 KB
Format:
Adobe Portable Document Format