Design, Implementation and Evaluation of Efficient Data Storage Algorithms in Segmented Memory Model
Loading...
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2014-11-03
Department
Major/Subject
Ohjelmistotekniikka
Mcode
T3001
Degree programme
Tietotekniikan koulutusohjelma
Language
en
Pages
65 + 11
Series
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.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.Description
Supervisor
Soisalon-Soininen, EljasThesis advisor
Soisalon-Soininen, EljasKeywords
segment, memory model, algorithm, binary search tree, red-black tree, splay tree, segmentti, muistimalli, algoritmi, binäärinen hakupuu, punamusta puu, splay-puu
