병렬계산의 스케쥴링에있어서 유전자알고리즘에관한 연구 = A Study on the Genetic Algorithms for the Scheduling of Parallel Computation

다국어 초록 (Multilingual Abstract)

For parallel processing, the compiler partitions a loaded program into a set of tasks and makes a schedule for the tasks that will minimize parallel processing time for the loaded program. Building an optimal schedule for a given set of partitioned tasks of a program has known to be NP-complete.
In this paper we introduce a GA(Genetic Algorithm)-based scheduling method in which a choromosome consists of two parts of a string which decide the number and order of tasks on each processor. An additional computation is used for feasibility constraint in the chromosome.
By granularity theory, a partitioned program is categorized into coarse-grain or fine-grain types. There exist good heuristic algorithms for coarse-grain type partitioning. We suggested another GA adaptive to the coarse-grain type partitioning. The infeasibility of chromosome is overcome by the encoding and operators.
The number of processors are decided while the GA find the minimum parallel processing time.