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

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Soisalon-Soininen, Eljas
dc.contributor.author Huttunen, Janne
dc.date.accessioned 2014-11-11T12:04:05Z
dc.date.available 2014-11-11T12:04:05Z
dc.date.issued 2014-11-03
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/14447
dc.description.abstract The 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.abstract Alati 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.extent 65 + 11
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Design, Implementation and Evaluation of Efficient Data Storage Algorithms in Segmented Memory Model en
dc.title Tehokkaiden tiedonhallinta-algoritmien suunnittelu, toteutus ja evaluointi segmentoidussa muistimallissa fi
dc.type G2 Pro gradu, diplomityö en
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword segment en
dc.subject.keyword memory model en
dc.subject.keyword algorithm en
dc.subject.keyword binary search tree en
dc.subject.keyword red-black tree en
dc.subject.keyword splay tree en
dc.subject.keyword segmentti fi
dc.subject.keyword muistimalli fi
dc.subject.keyword algoritmi fi
dc.subject.keyword binäärinen hakupuu fi
dc.subject.keyword punamusta puu fi
dc.subject.keyword splay-puu fi
dc.identifier.urn URN:NBN:fi:aalto-201411123024
dc.programme.major Ohjelmistotekniikka fi
dc.programme.mcode T3001 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Soisalon-Soininen, Eljas
dc.programme Tietotekniikan koulutusohjelma fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account