Concurrent Bkd-tree
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3091568Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Sammendrag
Moderne CPUer utgis med fler og fler beregningsenheter. For å utnytte det økende antallet kjerner på moderne CPUer, bør programmer utvikles for å håndtere samkjørende og flertrådede arbeidsbelastninger. Med dette utgangspunktet har en flerdimensjonal datastruktur kalt Balansert Kd-tre(Bkd-tre) blitt utvalgt som et studieobjekt.
Fokuset på denne masteren omhandler utviklingen og ytelsestesting av et serielt Bkd-tre, en flerdimensjonalt indeks. Funnene blir deretter brukt som en generell mal for å modernisere datastrukturen og tilpasse løsningen til å kunne utnytte flere tråder og samkjøring.
Flere tester og konfigurasjoner av det Samkjørende Bkd-treet har blitt profilert og ytelsestestet. De overordnede resultatene indikerer at tidsbruk på kommunikasjon burde reduseres hvor det er mulig og at flertrådet ytelse i stor grad avhenger av å redusere kommunikasjonen mellom tråder. Det Samkjørende Bkd-treet er testet både på en bærbar datamaskin og på en større server. Resultatene konkluderer med viktigheten av å utnytte konfigurasjoner som drar nytte av maskinvaren til den gitte maskinen. Funnene indikerer viktigheten av å tilpasse arbeidsmengden basert på systemet og at bruk av alle tråder kan redusere ytelsen i dataintensive applikasjoner, da flere tråder må dele hurtigbufferen. Konfigurasjonen bør også gjenspeile den forventede arbeidsmengden, enten ved å opprette store strukturer for å støtte leseytelse eller mindre strukturer for å øke antall innsettinger per sekund(IPS).
Sluttresultatet er et Samkjørende Bkd-tre som oppnår en gjennomsnittlig trådeffektivitet på 34,8% under innsettinger i datatunge arbeidsmengder med 4228 innsettinger per sekund(IPS), i en nær optimal konfigurasjon. Modern CPUs are released with more and more computational units. To take advantage of the increasing number of cores on modern CPUs, programs should be created to support concurrent and multithreaded workloads. With this starting point, a multidimensional structure called a Balanced Kd-tree(Bkd-tree) have been taken as a study subject.
This thesis covers the creation and benchmarking of a serial Bkd-tree, a multidimensional index. The findings is further used as a general blueprint for modernizing the data structure and improving the solution by utilizing multithreading and concurrency.
Multiple tests and configurations of the Concurrent Bkd-tree have been profiled and benchmarked. The overall results indicate that synchronization overhead should be avoided were possible and that multithreaded performance is largely dependent on reducing communication between threads. The Concurrent Bkd-tree is tested in both a laptop and server environment and the results conclude the importance of utilizing configurations which benefit the hardware of the given machine. Findings indicate the importance of tuning the workload based on the system and that utilizing all threads may slow down performance in data intensive application due to multiple threads sharing the cache.The configuration should also reflect the the expected workload, either creating large structures to support read performance or smaller structures to increase Inserts per Second(IPS).
The final result is a Concurrent Bkd-tree which demonstrates an average thread efficiency of 34.8% during inserts in data intensive workloads with 4228 Inserts per Second(IPS), in a close to optimal configuration.