search query: @supervisor Soisalon-Soininen, Eljas / total: 163
reference: 9 / 163
« previous | next »
Author:Huttunen, Janne Tapio
Title:Design, Implementation and Evaluation of Efficient Data Storage Algorithms in Segmented Memory Model
Tehokkaiden tiedonhallinta-algoritmien suunnittelu, toteutus ja evaluointi segmentoidussa muistimallissa
Publication type:Master's thesis
Publication year:2014
Pages:xi + 65 s. + liitt. 11      Language:   eng
Department/School:Perustieteiden korkeakoulu
Main subject:Ohjelmistotekniikka   (T3001)
Supervisor:Soisalon-Soininen, Eljas
Instructor:
Electronic version URL: http://urn.fi/URN:NBN:fi:aalto-201411123024
OEVS:
Electronic archive copy is available via Aalto Thesis Database.
Instructions

Reading digital theses in the closed network of the Aalto University Harald Herlin Learning Centre

In the closed network of Learning Centre you can read digital and digitized theses not available in the open network.

The Learning Centre contact details and opening hours: https://learningcentre.aalto.fi/en/harald-herlin-learning-centre/

You can read theses on the Learning Centre customer computers, which are available on all floors.

Logging on to the customer computers

  • Aalto University staff members log on to the customer computer using the Aalto username and password.
  • Other customers log on using a shared username and password.

Opening a thesis

  • On the desktop of the customer computers, you will find an icon titled:

    Aalto Thesis Database

  • Click on the icon to search for and open the thesis you are looking for from Aaltodoc database. You can find the thesis file by clicking the link on the OEV or OEVS field.

Reading the thesis

  • You can either print the thesis or read it on the customer computer screen.
  • You cannot save the thesis file on a flash drive or email it.
  • You cannot copy text or images from the file.
  • You cannot edit the file.

Printing the thesis

  • You can print the thesis for your personal study or research use.
  • Aalto University students and staff members may print black-and-white prints on the PrintingPoint devices when using the computer with personal Aalto username and password. Color printing is possible using the printer u90203-psc3, which is located near the customer service. Color printing is subject to a charge to Aalto University students and staff members.
  • Other customers can use the printer u90203-psc3. All printing is subject to a charge to non-University members.
Location:P1 Ark Aalto  2001   | Archive
Keywords:segment
memory model
algorithm
binary search tree
red-black tree
splay tree
segmentti
DX 200
muistimalli
algoritmi
binäärinen hakupuu
punamusta puu
splay-puu
Abstract (eng):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.
Abstract (fin):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.
ED:2014-11-16
INSSI record number: 50050
+ add basket
« previous | next »
INSSI