In this thesis, we investigate the problem of scheduling in multi-computer system, i.e., given a set of interacting program modules, to which processor should each program module be assigned and when should each program module be executed. The scheduling problem is one of the most fundamental research topics for parallel computing, and has received much attention during the last decades. The objective of scheduling is to minimize the total execution time of the whole program, whoever, which is known to be NP-hard. Our scheduling policy has been developed under the KAPPA programming environment. KAPPA is programming aid for KAICUBE II, 5 dimentional hypercube multicomputer developed in Computer Engineering Research Laboratory. The input of KAPPA is a sequential-like program which contains sevral primitives for explicit parallelism. Dependency analysis, parallelization, scheduling, and target code generation are performed automatically in KAPPA. Experiments in KAICUBE II have shown that there is some extra execution time overhead due to communication primitives, which is ignored in previous scheduling schemes. The overhead is mainly due to the software delay for correct communication protocols and synchronization of communication data. Because of such overhead, existing scheduling algorithm result in errotic execution time analysis. In this thesis, we propose a scheduling algorithm which reflects the execution time overhead due to communication primitives and using this alogrithm we achive more accurate scheduling result. And also, it is shown that parallel program developement in KAPPA is very easy and efficient for message-passing model parallel programming environment.
