SEMINAR
DEPARTMENT OF COMPUTER ENGINEERING
ABSTRACT
BALANCING COMPUTATION LOAD AND COMMUNICATION OVERHEAD WITH
MULTILEVEL SOM ALGORITHM
Erdoğan BIKMAZ
M.S. in Computer Engineering
Supervisor: Asst. Prof. Atilla Gürsoy
July 10, 2001
Today, execution time of big programs such as data-analysis tasks, large-scale problems, scientific computations, engineering problems are continuing as a big bottleneck for computers. To solve this problem, we prefer to distribute all these loads to parallel computers by using some algorithms. One of these algorithms for static load balancing problem is Kohonen Self-Organizing Maps (SOM) which preserves the neighborhood relationship of tasks. During the implementation of SOM algorithm there are two important points that will effect the performance of the algorithm which are computation cost and communication cost.
Our main aim is distributing all loads in such a way that minimizes the execution time of SOM algorithm. We know that, distributing the loads in an equal way is not enough for load balancing because communication cost of a program which is inevitable during the communication of processors between each other, brings some extra overhead to the execution time of program. We tried to minimize this extra overhead and added it to the total cost of each processor. We improve the load balancing algorithm to minimize and balance the communication overhead by proposing new processor connection graphs. We propose algorithm, which is balancing the number of messages, that balances not only computational load but also communication overhead. The results show that, our algorithm outperforms the other task mapping algorithms on the view of load balancing.
After balanced partitioning, we tried to minimize execution of SOM algorithm by Multilevel approach and we have gotten better performance.
The seminar will be on July 10, 2001
at 10:00 in EA502