Decentralized Load Balancing for Highly Irregular Search Problems

In this paper, we present a Dynamic Load Balancing (DLB) policy for problems characterized by a highly irregular search tree, whereby no reliable workload prediction is available. DLB approaches based on global statistics are known to provide optimal load balancing performance, while randomized tech...

Full description

Saved in:
Bibliographic Details
Main Authors: Di Fatta, G., Berthold, M.R.
Format: Conference Proceeding
Language:English
Subjects:
Biology computing
Fault tolerance
Grid computing
Load management
Partitioning algorithms
Peer to peer computing
Scalability
Search problems
Statistical distributions
Workstations
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we present a Dynamic Load Balancing (DLB) policy for problems characterized by a highly irregular search tree, whereby no reliable workload prediction is available. DLB approaches based on global statistics are known to provide optimal load balancing performance, while randomized techniques provide high scalability. The proposed method combines both advantages and adopts distributed job-pools and a randomized polling policy. The method has been successfully adopted in a parallel search algorithm for sugbraph mining. The work load distribution process of the parallel application is based on a dynamic partitioning of the search space and a peer-to-peer communication framework. The effectiveness of the DLB method has been evaluated on a molecular biology dataset. The distributed application with the novel DLB method has shown good scalability and close-to linear speedup in a distributed network of workstations. Moreover, fault tolerance and dynamic resource aggregation make it suitable for largescale, multi-domain, heterogeneous environments, such as computational Grids.
ISSN:1530-1346
2642-7389
DOI:10.1109/ISCC.2006.56