岡本 秀輔

スーパスカラコンピュータのように動的に並列性を抽出するのではなく,命令の種類別並列性を静的に抽出するPN computerでは,プログラムの構築の善し悪しがその性能に大きく影響する.PN用プログラムは,基本ブロックごとの並列化,それらの接続という手順で生成されるが,後者においては両ブロック間の整合をうまくとることが重要である.特に実行の流れの分岐や合流部分ではこの整合が乱れることが多い.本論文ではこの不整合の原因を明らかにし,その対策方法について述べる.

This paper describes a new parallel algorithm for solving the m-machines, n-jobs flow-shop scheduling problem as well as its implementation on a distributed memory multiprocessor. The algorithm is basically a parallelization of the usual branch-and-bound method. It also takes advantage of the all-search method to keep the efficiency of parallel processing reasonably high when subproblems become smaller than a certain size. The performance evaluation is done by comparing the parallel execution of this algorithm on the nCUBE2 multiprocessor and the sequential execution of the branch-and-bound with depth-first search algorithm. The result shows that the mean speedup ratio for some conditions of the problem is more than the number of processors, and the mean speedup ratio for the conditions on which the sequential executions complete quickly is not smaller than 1.

This paper describes a new parallel algorithm for solving n-job, m-machine flow-shop problems. The algorithm is basically a parallelization of the usual branch-and-bound method. It also takes advantage of all search method to keep high efficiency of parallel processing, when the subproblem becomes smaller than certain size. It is shown that its implementation on both nCUBE2 and LUNA88k2 gives very good performance characteristics.

本論文では,m機械,nジョブのフローショップスケジューリング問題に対する並列最適化アルゴリズムと分散記憶型マルチプロセッサ上への実装について述べる.ここで述べるアルゴリズムは,総所要時間最小化問題に対する分枝限定法を並列化し,更に,あるサイズより小さな部分問題を全探索することにより探索の効法化を実現したものである.アルゴリズムの性能は,分散記憶型マルチプロセッサnCUBE2上での並列実行と深さ優先探索の逐次実行との比較により評価した.この結果,N台のプロセッサを用いた場合,問題の条件により平均がN倍を超える速度向上が測定された,また,逐次の実行時間が比較的短い問題条件においても,ほとんどが減速することなく最適解を与えることが確かめられ,アルゴリズムの有効性を確認した.