Title :
Solving the mapping problem with a genetic algorithm on the MasPar-1
Author :
Kalinowski, Tomasz
Author_Institution :
Inst. of Comput. Sci., Polish Acad. of Sci., Warsaw, Poland
Abstract :
Good mapping algorithms can significantly reduce the total execution time of a program. However, the mapping problem is NP-complete. Consequently, heuristic methods should be used. Massively parallel systems allow the implementation of genetic algorithms running on large populations. In this paper, an algorithm based on a neighbourhood model is presented. The program has been implemented on 4096-processor MasPar-1 multicomputer. Experimental results for three genetic operators are presented and compared. The influence of initialisation strategies and selection techniques is also considered. A new initialization strategy based on grouping of adjacent tasks into approximately equal clusters is proposed
Keywords :
genetic algorithms; multiprocessing programs; multiprocessing systems; MasPar-1; NP-complete; adjacent tasks; genetic algorithm; heuristic methods; initialisation strategies; mapping problem; neighbourhood model; selection techniques; Biological cells; Computer science; Concurrent computing; Evolution (biology); Genetic algorithms; Genetic mutations; Parallel machines; Space exploration; Stochastic processes; Traveling salesman problems;
Conference_Titel :
Massively Parallel Computing Systems, 1994., Proceedings of the First International Conference on
Conference_Location :
Ischia
Print_ISBN :
0-8186-6322-7
DOI :
10.1109/MPCS.1994.367057
