A comparative study of two dynamic load balancing techniques as a means to increase performance in shared memory parallel computing

Abstract

With the proliferation of multicore computing devices ranging from notebooks, tablets and smart phones, parallel computing is becoming the norm of most software developers. With the ultimate goal being increasing computing speed, shrewd load balancing becomes a key requirement to optimize the performance of these multicore systems. This study compares the performance of two dynamic load balancing techniques, namely centralized dynamic load balancing and cyclic load balancing, using real world problems. The problems used are matrix multiplication, linear search and selection sort. The parameters used in performance comparison are processing time and processor idle time. Based on the experiments carried out, centralized dynamic load balancing performed better in matrix multiplication in terms of processing time with the highest recorded average time for a 4000*4000 square matrix being 1,111.083 seconds compared to 1498.398438 seconds for cyclic load balancing. Cyclic load balancing algorithm performed better for sorting and searching problems by recording average highest processing times of 15.17908969 seconds for a sort size of 40,000 and 0.003357 seconds for a search size of 80,000 compared to 15.20170313 seconds and 0.00493915 seconds respectively from centralized dynamic load balancing algorithm. From the results obtained, it is recommended to use centralized dynamic load balancing algorithm for mathematical computations while for non-mathematical computations it is recommended to use cyclic load balancing algorithm.

Keywords: Multicore, parallel computing, load balancing.