整数計画問題としてのループ並列実行時間の下限算出問題
スポンサーリンク
概要
- 論文の詳細を見る
並列処理の分野において、プログラムの並列実行時間の見積りは、静的スケジューリング、自動並列化等の応用で重要な問題である。特に、プログラム中のループには多くの並列実行可能部分が潜在するため、ループ部の並列実行時間の見積りに対する需要は大きい。ループ全体の並列実行時間の下限は、ループを展開したコードの依存グラフを生成し、そのクリティカルパスのコストを算出することにより得ることができるが、この方法はループの大きさに対するスケーラビリティの点で劣る。本稿では、ループを展開することなく、ループを展開したコードの依存グラフのクリティカルパスのコスト-すなわちループ全体の並列実行時間の下限-を算出する問題を、整数計画問題に帰貴させ、単体法ならびに分技限定法を用いて解く。これにより、問題解決にかかる時間はループの大きさに依存せず、大規模なループの並列実行時間の下限の算出が可能となる。
- 一般社団法人情報処理学会の論文
- 1996-01-22
著者
-
荒木 啓二郎
奈良先端科学技術大学院大学
-
福田 晃
奈良先端科学技術大学院大学
-
中西 恒夫
奈良先端科学技術大学院大学情報科学研究科
-
城 和貴
奈良先端科学技術大学院大学
-
Polychronopoulos Constantine
Center For Supercomputing Research And Development University Of Illinois At Urbana-champaign
-
Polychronopoulos Constantine
奈良先端科学技術大学院大学 情報科学研究科
関連論文
- 関数型言語指向プロセッサアーキテクチャ
- OSレベルでのリソース・リザベーションのメディア並列処理に対する効果
- マルチメディア同期機構の試作と評価
- マルチメディア処理におけるOSレベルでのリソース・リザベーション
- QOSに基づいたマルチメディアOS
- PDE-IIにおけるリソースのリザベーションに関する考察
- オンチップマルチプロセッシングアーキテクチャ : ロック機構
- プログラマブルデバイスを用いた可変構造シミュレーションシステムの開発
- プログラマブルデバイスを用いた可変構造シミュレーションシステム
- Ad Hoc Networkでの相対位置情報を用いた車車間通信システム
- 放送により配信される位置依存情報のキャッシュ方式(モバイルコンピューティング)
- 複数の通信メディアを利用した階層型データの効率的転送の実装モデル
- 移動経路情報を利用した路車間通信方式のシミュレーションによる評価
- STRAP : 移動を考慮した空間的時間的資源割当てプロトコル(マルチメディア通信と分散処理)
- 移動計算機における位置依存情報のキャッシュ方式に関する考察
- 移動経路情報を利用したデータ転送方式のシミュレーションによる評価
- 移動計算機環境における階層型データのためのキャッシュシステム
- 移動を考慮した空間的時間的資源割り当てプロトコルの提案とその適応
- STRAP:移動を考慮した空間的時間的資源割り当てプロトコルに関する提案
- 配列参照パターンによるプログラム並列化・最適化支援
- 並列化支援のためのデータ依存の3次元視覚化
- 複合グラフを用いた階層タスクグラフの視覚化
- エージェントの挙動の表現法について : 交渉による集結の一例
- B-7-128 マルチキャストのための再送制御方式の基礎検討
- 相互結合型ニューラルネットワークを用いた連想記憶の記憶容量のGAによる進化
- クラスタ型NUMAマルチプロセッサにおけるメモリ協調スケジューリング方式
- メモリ管理を考慮したNUMAマルチプロセッサにおける2レベルスケジューリングの評価
- 分散型構造解析手法の負荷分散への適用
- モジュール構成のマルチプロセッサ・スケジューリング・シミュレータ
- Net Newsのためのキャッシングアルゴリズム(ネットワークソフトウェア)
- NetNewsにおける必要な記事の自動選択法
- NetNewsにおける必要な記事の自動選択法
- NetNewsのためのキャッシュシステム
- NetNewsのためのキャッシュシステム
- ニュースグループごとに配送方式を自動変更するNetNewsシステムの評価
- ニュースグループごとに配送方式を自動変更するNetNewsシステムの評価
- NUMAマルチプロセッサにおけるメモリ管理を考慮した2レベルスケジューリング
- リアルタイムモニタリング機能を実装したハードウェアスケジューラの設計と実装
- リアルタイムモニタリング機能を実装したハードウェアスケジューラの設計と実装
- 並列性と移植性をもつユーザレベルスレッドライブラリーPPLの設計および実装
- 並列性と移植性を考慮したユーザレベル・スレッドライブラリPPLの実装と評価
- 並列性と移植性を考慮したユーザレベル・スレッドライブラリPPLの実装と評価
- 帯域予約されたネットワーク上の連続メディア送信 (マルチメディア通信と分散処理)
- 広帯域大規模分散環境における時間の共有 : グループ同期
- 広帯域大規模分散環境における時間の共有 : イベント同期
- OSレベルでのリソース・リザベーションのメディア並列処理に対する効果
- マルチメディア統合環境におけるQoS管理機構
- PDE-IIにおけるリソース・スキーマの提案
- PDE-IIにおけるマルチメディアアプリケーションの実装について
- PDE-IIにおける実時間同期のための周期スレッドの提案
- リリース・コンシステンシ・モデルとその実現の形式的仕様記述について
- 分散共有メモリの形式的仕様記述について
- リリース・コンシステンシ・モデルとその実現の形式的仕様記述について
- ニューラルネットワークによるプログラム分割アルゴリズムの改善
- 実用的な近似解を与えるプログラム分割アルゴリズム
- 実用的な近似解を与えるプログラム分割アルゴリズム
- Communication-Parallelism Graphによるデータ自動分割手法
- ワークステーションクラスタにおけるSCIDDLEライブラリの評価
- 2000-ARC-139-25 可変構造シミュレーションシステムRiSPの機能拡張
- スライシングによるデータ型のデバッグ
- 並列OS"K1"の実装と性能評価
- 並列OS"K1"の実装と性能評価
- マイクロカーネル構成OSにおけるマルチプロセスサーバとマルチスレッドサーバの比較
- マイクロカーネル構成OSにおけるシステムサーバの構成法
- 移動計算機の情報発信環境における階層型データのためのキャッシュシステム
- オンチップマルチプロセッシングアーキテクチャにおけるメモリシステム
- 多項式における剰余区間演算誤差削減のための演算規則
- 2000-ARC-139-8 剰余区間演算規則とその応用例
- HTGの最適化手法への適応に関する考察
- CDP^2アルゴリズム : データ分割グラフ上での統合的データ・プログラム分割アルゴリズム
- HDPG:階層データ分割グラフ
- フラッシュメモリファイルシステムにおけるメモリ割当ての効果システムソフトウェアの新しい潮流
- 移動計算機からマルチメディア情報を効率的に提供するツールキットWORの設計と実装(マルチメディアネットワークシステム)
- 組込みシステム向けフラッシュメモリファイルシステムの設計
- 移動計算機から位置依存情報を提供するサービスアプリケーションの構築
- 2000-OS-85-15 組み込み向けOSにおけるデバイスドライバの自動生成について
- UNIX系OSにおけるデバイスドライバの抽象化と生成システムの実現(特集:システムソフトウエアの新しい潮流)
- 移動計算機情報発信環境のためのToolkitの設計と実装(特集:システムソフトウエアの新しい潮流)
- 電車模型制御用ソフトウエアシステムの設計
- 電車模型制御用ソフトウエアシステムの設計
- 組込システム向け実行環境の自動生成 : δプロジェクトの構想
- 移動計算機のための帯域の狭いネットワーク環境を考慮した情報発信機構(マルチメディア通信プロトコル)
- 組込み機器向けOSの移植性を考慮した割込み機能の抽象化
- OS間の差異を吸収するデバイスドライバ自動生成システムの設計
- カーネル内スケジューリングポリシの動的置換
- 動的保護が可能な動的構築機構を有するオペレーティングシステム・サーバの実現と評価 (新しいシステムソフトウェア)
- ユーザレベルスレッドライブラリPPLにおける柔軟なスケジューリング機構 (新しいシステムソフトウェア)
- 組み込みシステム向けオペレーティングシステムの構成
- 組み込み用フラッシュメモリファイルシステムの設計
- 2000-ARC-139-24 コードサイズを縮小する組込み向けプロセッサと目的コードの協調生成
- 分散環境上で共有メモリ空間とメッセージパッシング型通信機構を提供する並列記述言語処理系ParaDisEの試作と評価
- カーネルスケジューラの動的置換
- OMT法による並列化コンパイラ中間言語フレームワークの構築
- ループによって運ばれる依存を有するループの並列実行時間の見積り
- 整数計画問題としてのループ並列実行時間の下限算出問題
- PDE-IIにおけるメディア間同期機構の実現に対する考察
- PDE-IIの概要 : QOSに基づいたマルチメディア処理モデル
- QOSに基づいて電子メディアツールの評価
- 周期スレッドを用いたマルチメディアデータの同期処理
- 対人的コミュニケーションにおける電子的メディアの特性と効果