Load balancing in parallel computing: an evolutionary approach

Simona Dinu; Gabriel Raicu

doi:10.1117/12.2643056

2 March 2023 Load balancing in parallel computing: an evolutionary approach

Simona Dinu, Gabriel Raicu

Proceedings Volume 12493, Advanced Topics in Optoelectronics, Microelectronics, and Nanotechnologies XI; 124931M (2023) https://doi.org/10.1117/12.2643056
Event: Advanced Topics in Optoelectronics, Microelectronics and Nanotechnologies 2022, 2022, Constanta, Romania

Abstract

The assignment of work uniformly, across an available group of processors, represent an important problem in parallel computing. The efficiency of the workload balancing is obtained by a proper partitioning strategy, which is a challenging task. Partitioning is an important concept connected to various other problems in modern computing field and also an extensively-studied problem in graph-based analysis. The computational graph in parallel computing model defines units of computations (or tasks) as nodes and data dependencies (or communications) between units as edges. A k-way graph balanced partitioning algorithm is proposed, with the objectives of partitioning the graph nodes into k equal sized disjoint components, while minimizing the number of edges crossing between components. This edge partition model is suggestive for mapping computations to processors, while reducing the interprocessors communications. The partitioning problem turned out to be a NP-hard problem of combinatorial optimization, so we proposed a Genetic Algorithm with fuzzy adaptation of parameters for determining optimal partitions within a reasonable amount of time. The performance of the partitions was assessed based on two performance metrics, namely density and conductance. Based on randomly generated application workflows, experiments with different values of k were performed to demonstrate computational capabilities of the proposed algorithm.

Citation Download Citation

Simona Dinu and Gabriel Raicu "Load balancing in parallel computing: an evolutionary approach", Proc. SPIE 12493, Advanced Topics in Optoelectronics, Microelectronics, and Nanotechnologies XI, 124931M (2 March 2023); https://doi.org/10.1117/12.2643056

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available