Home // INFOCOMP 2015, The Fifth International Conference on Advanced Communications and Computation // View article

An Adaptive Load-balancer for Task-scheduling in FastFlow

Authors:
Md Moniruzzaman
Kamran Idrees
Michael Rossbory
Jose Gracia

Keywords: task scheduling; load balancing; heterogenous architecture; NUMA; FastFlow

Abstract:
Balancing the computational load of multiple concurrent tasks on heterogeneous architectures is one of the critical requirements for efficient usage of such systems. Load-imbalance is inherently present if the computation load is distributed non-uniformly across various tasks or if execution time for the same kind of tasks varies from one class of processing element to the other. Load-imbalance may however also arise from causes that are beyond the control of the user, as for instance operating system jitter, over-subscription of the available workers, interference and resource contention by concurrent tasks, etc. Writing a balanced parallel application requires careful analysis of the problem and good understating of various hardware architectures of the computing nodes. FastFlow is a C++ library that offers high-level parallel pattern abstractions on the user side, and lowers those onto efficiently implemented architecture specific skeletons. The default FastFlow scheduler, however, assigns tasks to workers in a round-robin fashion and is thus not well suited to handle load-imbalance. In this paper, we present an adaptive load-balancing task scheduler for FastFlow, a model for the expected relative per- formance of our adaptive scheduler over the default round-robin scheduler, and finally evaluate the quality of the implementation with low-level as well as two specific application benchmarks. We find that the adaptive load-balancer does not introduce additional overheads if load-imbalances are not present, and that our scheme is particularly efficient in mitigating the effect of thread over-subscription. Finally, we show that the proposed scheduler can lead to substantial performance gain for real industrial applications.

Pages: 6 to 12

Copyright: Copyright (c) IARIA, 2015

Publication date: June 21, 2015

Published in: conference

ISSN: 2308-3484

ISBN: 978-1-61208-416-9

Location: Brussels, Belgium

Dates: from June 21, 2015 to June 26, 2015