Change search
ReferencesLink to record
Permanent link

Direct link
Performance Optimisation of Discrete-Event Simulation Software on Multi-Core Computers
KTH, School of Computer Science and Communication (CSC).
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Prestandaoptimering av händelsestyrd simuleringsmjukvara på flerkärniga datorer (Swedish)
Abstract [en]

SIMLOX is a discrete-event simulation software developed by Systecon AB for analysing logistic support solution scenarios. To cope with ever larger problems, SIMLOX's simulation engine was recently enhanced with a parallel execution mechanism in order to take advantage of multi-core processors. However, this extension did not result in the desired reduction in runtime for all simulation scenarios even though the parallelisation strategy applied had promised linear speedup. Therefore, an in-depth analysis of the limiting scalability bottlenecks became necessary and has been carried out in this project. Through the use of a low-overhead profiler and microarchitecture analysis, the root causes were identified: atomic operations causing a high communication overhead, poor locality leading to translation lookaside buffer thrashing, and hot spots that consume significant amounts of CPU time. Subsequently, appropriate optimisations to overcome the limiting factors were implemented: eliminating the expensive operations, more efficient handling of heap memory through the use of a scalable memory allocator, and data structures that make better use of caches. Experimental evaluation using real world test cases demonstrated a speedup of at least 6.75x on an eight-core processor. Most cases even achieve a speedup of more than 7.2x. The various optimisations implemented further helped to lower run times for sequential execution by 1.5x or more. It can be concluded that achieving nearly linear speedup on a multi-core processor is possible in practice for discrete-event simulation.

Abstract [sv]

SIMLOX är en kommersiell mjukvara utvecklad av Systecon AB, vars huvudsakliga funktion är en händelsestyrd simuleringskärna för analys av underhållslösningar för komplexa tekniska system. För hantering av stora problem så används parallellexekvering för simuleringen, vilket i teorin borde ge en nästan linjär skalning med antal trådar. Prestandaförbättringen som observerats i praktiken var dock ytterst begränsad, varför en ordentlig analys av skalbarheten har gjorts i detta projekt. Genom användandet av ett profileringsverktyg med liten overhead och mikroarkitektur-analys, så kunde orsakerna hittas: atomiska operationer som skapar mycket overhead för kommunikation, dålig lokalitet ger fragmentering vid översättning till fysiska adresser och dåligt utnyttjande av TLB-cachen, och vissa flaskhalsar som kräver mycket CPU-kraft. Därefter implementerades och testade optimeringar för att undvika de identifierade problem. Testade lösningar inkluderar eliminering av dyra operationer, ökad effektivitet i minneshantering genom skalbara minneshanteringsalgoritmer och implementation av datastrukturer som ger bättre lokalitet och därmed bättre användande av cache-strukturen. Verifiering på verkliga testfall visade på uppsnabbningar på åtminstone 6.75 gånger på en processor med 8 kärnor. De flesta fall visade på en uppsnabbning med en faktor större än 7.2. Optimeringarna gav även en uppsnabbning med en faktor på åtminstone 1.5 vid sekventiell exekvering i en tråd. Slutsatsen är därmed att det är möjligt att uppnå nästan linjär skalning med antalet kärnor för denna typ av händelsestyrd simulering.

Place, publisher, year, edition, pages
2016.
Keyword [en]
cache hierarchy, caches, communication overhead, data structures, discrete-event simulation, heap memory, linear speedup, logistic support, low-overhead profiler, memory allocator, microarchitecture, microarchitecture analysis, multi-core, optimisation, parallel execution, profiler, runtime, scalability, scalability bottlenecks, scalable memory allocator, simulation, translation lookaside buffer, translation lookaside buffer thrashing, TLB
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-191132OAI: oai:DiVA.org:kth-191132DiVA: diva2:954999
External cooperation
Systecon AB, Stockholm
Educational program
Master of Science - Computer Science
Supervisors
Examiners
Available from: 2016-08-25 Created: 2016-08-24 Last updated: 2016-08-25Bibliographically approved

Open Access in DiVA

fulltext(4040 kB)4 downloads
File information
File name FULLTEXT01.pdfFile size 4040 kBChecksum SHA-512
b00606e77884ea2847ff20327cee39d963e18d18675560f30ca0dcec60eb1ab0c6f17ea8c590d88a22bac0712fc5ba94824fba31e85caca55237d9ecd0441267
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 4 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 29 hits
ReferencesLink to record
Permanent link

Direct link