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

fYear

1994

fDate

2-6 May 1994

Firstpage

370

Lastpage

374

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Massively Parallel Computing Systems, 1994., Proceedings of the First International Conference on

Conference_Location

Ischia

Print_ISBN

0-8186-6322-7

Type

conf

DOI

10.1109/MPCS.1994.367057

Filename

367057