Title :
A load balancing algorithm for bus-oriented systems
Author :
Joshi, Bharat S. ; Hosseini, Seyed ; Vairavan, K.
Author_Institution :
Math. & Comput. Sci., Western Carolina Univ., Cullowhee, NC, USA
Abstract :
We report the results of a study of the performance of a load balancing algorithm for bus-oriented systems based on graph coloring. In this algorithm the processors use local knowledge for the purpose of load balancing. Node coloring concept is used to group the processors. This avoids the selection/rejection operations encountered in many load balancing algorithms proposed in the literature. Also, there is no central controller and the algorithm is easily adaptable to changes in the system configurations. The interconnection network of the system is modeled by a graph where the nodes represent buses and an edge between two nodes in the graph implies that the two buses are connected through a common processor. The primary performance metrics used are the average response time of the system and the system distance. We express the analytical results in terms of upper and lower bounds on these metrics
Keywords :
directed graphs; graph colouring; multiprocessor interconnection networks; parallel architectures; resource allocation; software performance evaluation; system buses; average response time; bus-oriented systems; central controller; graph coloring; interconnection network; load balancing algorithm; local knowledge; lower bounds; node coloring; performance; performance metrics; selection rejection operations; system configurations; system distance; upper bounds; Centralized control; Computer science; Control systems; Delay; Heuristic algorithms; Load management; Mathematics; Measurement; Modeling; Multiprocessor interconnection networks;
Conference_Titel :
Parallel and Distributed Processing, 1996., Eighth IEEE Symposium on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-8186-7683-3
DOI :
10.1109/SPDP.1996.570357
