分散記憶型マルチプロセッサにおけるフローショップスケジューリング問題の並列解法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,m機械,nジョブのフローショップスケジューリング問題に対する並列最適化アルゴリズムと分散記憶型マルチプロセッサ上への実装について述べる.ここで述べるアルゴリズムは,総所要時間最小化問題に対する分枝限定法を並列化し,更に,あるサイズより小さな部分問題を全探索することにより探索の効法化を実現したものである.アルゴリズムの性能は,分散記憶型マルチプロセッサnCUBE2上での並列実行と深さ優先探索の逐次実行との比較により評価した.この結果,N台のプロセッサを用いた場合,問題の条件により平均がN倍を超える速度向上が測定された,また,逐次の実行時間が比較的短い問題条件においても,ほとんどが減速することなく最適解を与えることが確かめられ,アルゴリズムの有効性を確認した.
- 社団法人電子情報通信学会の論文
- 1994-06-25
著者
-
岡本 秀輔
成蹊大学大学院工学研究科情報処理専攻
-
飯塚 肇
成けい大 大学院
-
飯塚 肇
成蹊大学大学院工学研究科情報処理専攻
-
渡辺 一衛
成蹊大学大学院工学研究科情報処理専攻
-
飯塚 肇
成蹊大学大学院工学研究科
関連論文
- 分散記憶型マシンにおける並列整数計画法
- B-021 PCクラスタにおける並列言語MpCとOpenMPの性能比較(B.ソフトウェア)
- B-42 分散共有メモリSMSにおける共有変数の分散割付API(リアルタイムと分散共有メモリ,B.ソフトウェア)
- 分散記憶型マルチプロセッサnCUBE2の性能評価
- 通信性能を考慮した自動並列化コンパイラのプロファイリング方式
- 同期モデルに基づく自動並列化コンパイラにおけるタスクスケジューリング方式
- 同期モデルに基づく自動並列化コンパイラ
- PRAMプログラムからPVMプログラムへの変換
- PRAMプログラムからpthreadプログラムへの変換
- RISC命令セットプログラムのVLIW命令セットプログラムへの変換
- コンピュータアーキテクチャの研究 : 思い出と期待
- 分散記憶型マルチプロセッサにおけるフローショップスケジューリング問題の並列解法
- 継承機能とランデブ方式による並列処理言語SPLANの拡張
- マルチスレッドによるメッセージ通信型並列処理言語SPLANの実現
- メッセージ通信型並列処理言語SPLAN
- nCUBE2における並列処理言語SPLANの実現
- B-030 マルチサーバMORPGにおける動的な管理データ割当て手法(ソフトウェア,一般論文)
- ハイパーキューブマルチプロセツサにおける整数計画法に対する並列Branch and Bound法
- 拡張現実感を利用したロボットシミュレーション環境の提案(一般,複合現実感,仮想都市,及び一般)