40 research outputs found
Adaptive load balancing for HPC applications
No full textOne of the critical factors that affect the performance of many applications is load imbalance. Applications are increasingly becoming sophisticated and are using irregular structures and adaptive refinement techniques, resulting in load imbalance. Moreover, systems are becoming more complex. The number of cores per node is increasing substantially and nodes are becoming heterogeneous. High variability in the performance of the hardware components introduces further imbalance. Load imbalance leads to drop in system utilization and degrades the performance. To address the load imbalance problem, many HPC applications employ dynamic load balancing algorithms to redistribute the work and balance the load. Therefore, performing load balancing is necessary to achieve high performance.
Different application characteristics warrant different load balancing strategies. We need a variety of high-quality, scalable load balancing algorithms to cater to different applications. However, using an appropriate load balancer is insufficient to achieve good performance because performing load balancing incurs a cost. Moreover, due to the dynamic nature of the application, it is hard to decide when to perform load balancing. Therefore, deciding when to load balance and which strategy to use for load balancing may not be possible a priori.
With the ever increasing core counts on a node, there will be a vast amount of on-node parallelism. Due to the massive on-node parallelism, load imbalance occurring at the node level can be mitigated within the node instead of performing a global load balancing. However, having the application developer manage resources and handle dynamic imbalances is inefficient as well as is a burden on the programmer.
The focus of this dissertation is on developing scalable and adaptive techniques for handling load imbalance. The dissertation presents different load balancing algorithms for handling inter and intra-node load imbalance. It also presents an introspective run-time system, which will monitor the application and system characteristics and make load balancing decisions automatically.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-02-28 without embargo termsThe student, Harshitha Menon Gopalakrishnan Menon, accepted the attached license on 2016-10-10 at 10:41.The student, Harshitha Menon Gopalakrishnan Menon, submitted this Dissertation for approval on 2016-10-10 at 11:06.This Dissertation was approved for publication on 2016-10-10 at 15:37.DSpace SAF Submission Ingestion Package generated from Vireo submission #10184 on 2017-02-28 at 14:46:33Made available in DSpace on 2017-03-01T15:46:12Z (GMT). No. of bitstreams: 3
GOPALAKRISHNANMENON-DISSERTATION-2016.pdf: 3167124 bytes, checksum: 3805eeefaf0d8bb418f81e31e71b9c1e (MD5)
LICENSE.txt: 4233 bytes, checksum: aaabaf4ea94f344f80b3c530c2c6c712 (MD5)
PROQUEST_LICENSE.txt: 4579 bytes, checksum: 90750d1fd3fee240d8f30b40eae4defb (MD5)
Previous issue date: 2016-10-1
Applying Graph Partitioning Methods in Measurement-based Dynamic Load Balancing
No full textLoad imbalance in an application can lead to degradation of performance and a significant drop in system utilization. Achieving the best parallel efficiency for a program requires optimal load balancing which is an NP-hard problem. This paper explores the use of graph partitioning algorithms, traditionally used for partitioning physical domains/meshes, for measurement-based dynamic load balancing of parallel applica- tions. In particular, we present repartitioning methods that consider the previous mapping to minimize dynamic migration costs. We also discuss the use of a greedy algorithm in conjunction with iterative graph partitioning algorithms to reduce the load imbalance for graphs with heavily skewed load distributions. These algorithms are implemented in a graph partitioning toolbox called SCOTCH and we use CHARM++, a migratable objects based programming model, to experiment with various load balancing scenarios. To compare with different load balancing strategies based on graph partitioners, we have implemented METIS and ZOLTAN-based load balancers in CHARM++. We demonstrate the effectiveness of the new algorithms de- veloped in SCOTCH in the context of the NAS BT solver and two micro-benchmarks. We show that SCOTCH based strategies lead to better performance compared to other existing partitioners, both in terms of the application execution time and fewer number of objects migrated.Submitted by Harshitha Menon Gopalakrishnan Menon ([email protected]) on 2015-05-05T18:51:02Z
No. of bitstreams: 1
paper.pdf: 1029299 bytes, checksum: 47905608546312ca38fb1338e7835f45 (MD5)Made available in DSpace on 2015-05-05T18:51:02Z (GMT). No. of bitstreams: 1
paper.pdf: 1029299 bytes, checksum: 47905608546312ca38fb1338e7835f45 (MD5)
Previous issue date: 2015Ope
Meta-Balancer: automated load balancing based on application behavior
No full textWith the dawn of petascale, and with exascale in the near future, it has become significantly difficult to write parallel applications that fully exploit the processing
power, and scale to large systems. Load imbalance, both computationally and communication induced, presents itself as one of the important challenges in achieving scalability and high performance. Problem sizes and system sizes have become so large that manually handling the imbalance in dynamic
applications, and finding an optimum distribution of load has become a herculean task.
Charm++~\cite provides the user with a run time system that
performs dynamic load balancing. To enable Charm++ to perform load balancing
in an efficient manner, the user takes certain decisions such as when to load
balance and which strategy to use, and informs the Charm++ run-time system of
these decisions. Many a times, taking these important decisions involve hand
tuning each application by observing various runs of the application.
In this thesis, a Meta-Balancer which relieves the user from the
effort of making the load balancing related decisions, is presented. The Meta-Balancer
is a part of the Charm++ load balancing framework. It identifies the characteristics
of the application, and based on the principle of persistence and the accrued
information, makes load balancing related decisions. We study the performance of
the Meta-Balancer in the context of leanmd mini application.
We also evaluate the Meta-Balancer in the context of micro benchmarks such as kNeighbor and jacobi2D.
We also present several new load balancing strategies, that have been
incorporated into Charm++, and study their impact on the performance of applications.
These new strategies are: 1)RefineSwapLB, which is a refinement based load balancing strategy,
2)CommAwareRefineLB, which is a communication aware refinement strategy,
3)ScotchRefineLB, which is a refinement based graph partitioning strategy using
Scotch, a graph partitioner, and 4) ZoltanLB, which is a multicast
aware load balancing strategy using Zoltan, a hypergraph partitioner.Item withdrawn by Mark Zulauf ([email protected]) on 2012-04-26T18:39:23Z
Item was in collections:
University of Illinois Theses & Dissertations (ID: 1)
No. of bitstreams: 1
HarshithaMenon_GopalakrishnanMenon.pdf: 465208 bytes, checksum: 877d25bafc3828c410945f03aa74abc8 (MD5)Made available in DSpace on 2012-05-22T00:36:10Z (GMT). No. of bitstreams: 2
HarshithaMenon_GopalakrishnanMenon.pdf: 465208 bytes, checksum: 877d25bafc3828c410945f03aa74abc8 (MD5)
license.txt: 4074 bytes, checksum: d38c5b47ad04d78f319a61a6b8fcc67f (MD5
Virtual environment and its ground surface can influence locomotion while being immersed in virtual reality
No full textImmersive virtual reality (IVR) is an artificially designed environment that can be used to produce realistic and engaging environments which are being used actively in the field of healthcare through training and rehabilitation. The use of IVR nowadays ranges from training surgical operations in a safe environment to neurorehabilitation. IVR implementation for rehabilitation is more task-specific, enhances patients' attention during training, and provides visual feedback. Avatar, a virtual extension of the user, can be used to interact with the virtual environment and aid in postural adjustments during rehabilitation. Although IVR training of upper limbs is often seen, the research is ongoing for lower limbs. Walking activities in the real-world post-stroke are essential for active participation in the community and to reduce potential mental illness. There is ongoing research on how to implement walking activities in VR. This study aimed to explore the effect of visualizing different ground surfaces on gait patterns. Twelve healthy young participants were recruited for the experiment. Two scenes with a different ground surfaces -- ice and concrete -- were designed. A male and a female avatar were animated and implemented in the scene. The participants were asked to walk eight times in both. Trackers located at the left and right foot and pelvis were used to obtain kinematic parameters such as stride and step length and gait speed. The participants were asked to answer an embodiment questionnaire, which consisted of questions about body ownership, sense of agency, and location, after each scene. We found that the first kinematic values of stride and step lengths and gait speed were lower while walking over the virtual ice scene compared to concrete. Overall, the values of body ownership, and sense of agency were higher when compared to the control questions of body ownership and sense of agency, after each scene. The value of the sense of location after each scene was also higher. The present findings show that the participants embodied in both the scenes and the ground surface had a significant influence on their gait modification. Thus, implementing ground surfaces along with IVR in rehabilitation can benefit patients by helping them adapt their gait to the ground surface.Biomedical Engineerin
POSTER
No full textMany HPC applications require dynamic load balancing to achieve high performance and system utilization. Different applications have different characteristics and hence require different load balancing strategies. Invocation of a suboptimal load balancing strategy can lead to inefficient execution. We propose Meta-Balancer, a framework to automatically decide the best load balancing strategy. It employs randomized decision forests, a machine learning method, to learn a model for choosing the best load balancing strategy for an application represented by a set of features that capture the application characteristics.</jats:p
HPAC: An Approximate Programming Model with Utilities
No full textThis is a baseline implementation of the approximate programming model called HPAC. HPAC extends Clang/LLVM. HPAC supports two approximation techniques perforation and memoization. Perforation supports subclasses of the technique that define the pattern of the perforated loops. Memoization supports two sub-classes of approximate memoization, namely input (iACT), and output (TAF) memorization. Each sub-class can be further parameterized to fine-tune the behavior of the technique. Finally, the release contains a set of scripts that facilitate exploration of the approximation design space and identify opportunities for approximations
