Discovery Sagaサイレントキーワード俯瞰

マルチプロセッサシステム / 自動並列化コンパイラ / データローカライゼーション / 無同期細粒度並列処理 / データ分割配置 / ローカルメモリ / マルチグレイン並列処理 / データ転送オーバーヘッドの隠蔽 / データ分割配列 / データ転送オーバーヘッドの隠敵 / 並列アーキテクチャ / スケジューリング / シミュレーション

本研究では、マルチグレイン並列処理のためのデータローカライゼーション手法、及びデータローカライゼーションによっても除去できなかったプロセッサ間データ転送をプロセッサ上でのタスク処理とオーバラップさせデータ転送オーバーヘッドを隠蔽する技術を開発するとともに、コンパイラにおけるマシンコードスケジューリングの高度化とそれを支援するマルチプロセッサシステムアーキテクチャによりプロセッサ間データ転送順序の最適化も可能とする無同期近細粒度処理技術を開発した。さらにそれらの有効性をアーキテクチャシミュレータ上あるいは実際のスーパーコンピュータ富士通VPP500上で示した。具体的には、データローカライゼーション手法に関する研究では、配列データの自動分割手法(ループ整合分割)とローカルメモリへの割当て法(パ-シャルスタティックスケジューリング)を開発し、OSCARタイプ・アーキテクチャシミュレータ上で有効性を検証した。また、データ転送と処理のオーバーラッピングスケジューリング技術の開発では、Fortranプログラムを解析し富士通VPP500用の並列化拡張言語VPP Fortranを出力するコンパイラ(プリプロセッサ)を開発し、4プロセッサのVPP500上で平均で15%程度実行時間を短縮できることを確めた。
また、無同期近細粒度並列処理技術に関する研究では、高度なマシンコードスケジューリング技術をサポートするアーキテクチャを明確化するとともに、アーキテクチャシミュレータ上で無同期近細粒度並列処理におけるデータ転送順序最適化技術の性能評価を行い手法の有用性を確認した。以上の研究により、今後のベクトルパラレルスーパーコンピュータ、将来のシングルチッププロセッサのアーキテクチャ、及び自動並列化コンパイラに関する指針が得られた。
なお以上の研究成果は、14件の学会論文誌論文あるいは国際会議論文として発表するとともに、1件の学会誌論文として掲載決定、1件の査読付きシンポジウム論文、5件の研究会論文、12件の全国大会論文とした発表されている。

フレキシブル生産システム(FMS) / オペレーションズ・リサーチ(OR) / 柔軟性(flexibility) / スケジューリング / 組合せ最適化 / シミュレーション / ディスパッチング / 経路選択 / ディスパッチング規則 / 待ち行列網 / 投入部品選択問題 / 離散型シミュレーション / シミュレーテッド・アニーリング

本研究では、FMSに代表される最近の自動生産システムの柔軟性がディスパッチングや最適化といったスケジューリングに及ぼす影響の分析や、機械の柔軟性に伴う工程集約がスケジューリングに及ぼす影響の分析を中心に、生産の計画管理と柔軟性との関係を明らかにした。主な成果は、以下の通りである:
(1)FMSにおけるディスパッチング規則の性能: 柔軟性を有する自動生産システムが持つ、自動搬送装置、有限パレット、有限バッファ、品種ロットの存在等の特徴を念頭に置き、総納期遅れ等のロット関連評価尺度と稼働率等のショップ関連尺度を考慮してディスパッチング規則の性能評価と最適化を行った。その結果、経路選択の自由度がない状況下では、主に、(1)SPT(Shortes Processing Time first)規則のような負荷の小さいジョブを優先的に流す規則が、納期関連評価尺度に関しても良い性能を示すこと、(2)ロットの大きさを考慮に入れた簡単なディスパッチング規則が納期関連評価尺度の改善に大きく役立つこと等が明らかになった。
さらに、経路選択の柔軟性がディスパッチング規則の性能に及ぼす影響を、シミュレーションによって調べた。その結果、経路選択の柔軟性が高まるにつれて、加工時間が短いジョブを優先する規則の相対的優位性が低下することが判明した。このことから、ディスパッチング優先する規則の相対的優先性が低下することが判明した。このことから、ディスパッチング規則の性能が、システムの柔軟性と相互に関連することが明らかになるとともに、従来の規則がシステムの柔軟性を十分に考慮していないことが明らかになった。
(2)柔軟性を生かす"Cooperative Dispatching"の提案と評価: 経路選択の自由度によって得られたシステムの柔軟性を十分に生かすために、Cooperative Dispatchingというフレームワークを構築し、ジョブと機械の協調によって、ジョブの処理機械を決定する方法を提案し、シミュレーションによってその性能を評価した。提案する方法によって、納期遅れ、滞溜時間、稼働率の各評価尺度とも改善されることが分かった。
(3)FMSにけるディスパッチング規則の最適化: 品種(ロット)を明確に意識した「品種(ロット)管理」を採用するフレキシブル生産システム(FMS)を想定し、品種(ロット)の優先順序に基づくディスパッチング規則を考えるとき、評価尺度(納期遅れ)の最適化を図る品種の優先順序決定問題に対してシミュレーテッド・アニーリング法と離散型シミュレーションとを併用したアルゴリズムを構築し、その性能を評価した。

【研究分担者】
久保幹雄	東京商船大学	商船学部	助教授	(Kakenデータベース)
今泉淳	早稲田大学	理工学部	助手	(Kakenデータベース)
十代田三知男	早稲田大学	理工学部	教授	(Kakenデータベース)