University of Twente Student Theses
Using static weight estimation of general trees to efficiently parallelize the execution of DEMKit Simulation Models
Lüpkes, Niklas (2020) Using static weight estimation of general trees to efficiently parallelize the execution of DEMKit Simulation Models.
PDF
337kB |
Abstract: | To aid the development of control mechanisms of smart grids, the “Decentralized Energy Management Simulation and Demonstration Toolkit” (DEMKit) was developed. It may be used to test and evaluate control algorithms by simulating complex (smart) energy grids. This research paper discusses the inherent problems of the models’ structure, a general tree, which hinders the setup of multi-processed simulations. An algorithm to automate the division of weighted general trees is presented, to spread workload and exploit parallelism. Weighted Tree Distribution (WTD) reduces a tree to a predefined number of leaves, based on tree contraction and respecting existing structures. Here, makespan minimization is used to optimize the distribution. The algorithm is tested using 1429 randomly generated trees of varying size. The tests confirm the time complexity of O(n log n) and yield an average of efficiency of 1.58. Finally, WTD is integrated into DEMKit, where it is subjected to different models and distributed over four processes. The implemented automated model distribution performs best if the distributed structures are independent. |
Item Type: | Essay (Bachelor) |
Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
Subject: | 54 computer science |
Programme: | Computer Science BSc (56964) |
Awards: | TSCiT Best Paper Award |
Link to this item: | https://purl.utwente.nl/essays/82238 |
Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Repository Staff Only: item control page