式の分割による並列化アルゴリズムESHとその評価
スポンサーリンク
概要
- 論文の詳細を見る
式の変数の定義される時間, 変数の参照可能時間と演算優先順位に注目した変数レベルの並列化のためのアルゴリズムESHを提案する. ESHでは同一優先順位を持つ変数間の演算を1つにまとめて未決定ノードとし原始プログラムから決定ノードと未決定ノードの混在した不完全タスクグラフを生成する. このタスクグラフからノードを取り出したとき未決定ノードであれば変数の参照可能時間の早い変数間の2項演算をプロセッサに割り当てて未決定ノードを分解し, 決定ノードを生成する. 決定ノードであればDuplication Scheduling Heuristic (DSH) によってスケジューリングする. すべてのノードが決定ノードになったときスケジューリングは完了する. ESHでは複数の文間に内在する並列性を最適化できるだけでなく, 最適な計算木が生成される. 16個のプログラムを用いて4種類のプロセッサモデルと細粒度マルチプロセッサMSBM上でESHと, ツリーハイトリダクション (THR) とDSHの併用, LR構文解析 (LR) とDSHの併用との比較を行った. その結果, すべてのプログラムで速度向上比はESH≧ (THR+DSH) ≧ (LR+DSH) であった. ESHのLR+DSHに対する速度向上比の平均は1.16であった. 一方THR+DSHのLR+DSHに対する速度向上比の平均は1.07であった.
- 一般社団法人情報処理学会の論文
- 1997-09-15
著者
-
岩根 雅彦
九州工業大学工学部
-
岩根 雅彦
九州工業大学大学院工学研究院
-
松田 孝史
九州工業大学工学部
-
小島 和広
九州工業大学工学部電気工学科:(現)九州旅客鉄道株式会社
-
宇野 総一
九州工業大学 工学部
-
濱田 智雄
九州工業大学工学部電気工学科
-
松田 孝史
九州工業大学工学部電気工学科
-
濱田 智雄
九州工業大学工学部電気工学科:(現)松下電器産業株式会社半導体開発本部
-
岩根 雅彦
九州工業大学大学院工学研究系
関連論文
- セミプログラマブルハードウェアによる画像フィルタ用バッファリング手法の検討(研究速報)
- HW/SWコデザインにおける共有アドレス空間を介した統一的なモジュール間インタフェースの実現法(仕様,設計,移植)
- HW/SWコデザインにおける共有アドレス空間を介した統一的なモジュール間インタフェースの実現法(仕様,設計,移植,組込技術とネットワークに関するワークショップETNET2007)
- チップマルチプロセッサの同期付きキャッシュメモリに対するミスペナルティ隠蔽機構(計算機アーキテクチャ)
- FMMにおける融合型処理とソフトウェア構成
- メモリアクセスを伴ったプログラムのFPGA実装に適したハードウェアアーキテクチャ(システムアーキテクチャ,リコンフィギャラブルシステムとその応用論文)
- HW/SWコデザインにおける共有アドレス空間を介した統一的なモジュール間インタフェースの実現法(仕様,設計,移植)
- HW/SWコデザインにおける共有アドレス空間を介した統一的なモジュール間インタフェースの実現法(仕様,設計,移植,組込技術とネットワークに関するワークショップETNET2007)
- 細粒度並列計算機MSBMの開発
- 教育用TCP/IPパケットアナライザの試作
- FPGAによるバリア同期用機能メモリの開発
- FMMのホスト同期機能を用いたタスクの複数並列実行とその性能予測
- FPGAベースオンチップマルチプロセッサにおける同期付きキャッシュメモリの実装と評価
- C_001 プログラマブルなロードストアユニットと演算部が協調する再構成可能プロセッサアーキテクチャ(C分野:ハードウェア)
- 再構成可能コンピューティングのための実環境を考慮した評価用テストベッドRCPII(リコンフィギャラブルシステム, リコンフィギャラブルシステム, 一般)
- 同期共有変数キャッシュの同期状態を拡張した効果
- 高密度実装クラスタにおける同期・通信処理方式の検討(ARC-8 : 相互結合網I)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- C言語からVHDLへの変換における並列処理(ARC-5 : 並列処理モデル)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- 疑似グローバルクロックを用いた高精度実行時間測定(ARC-3:専用プロセッサと時刻管理)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- 再構成可能プロセッサ486RCPによる再構成可能ハイパープロセッサの予備実験
- 共有変数の同期を考慮したキャッシュ構成とその予備実験
- バス結合共有メモリ型マルチプロセッサにおけるバリア同期機構の評価(システムLSIの設計技術と設計自動化)
- 1チップ再構成可能コンピューティングシステムの開発
- 1チップ再構成可能コンピューティングシステムの開発
- マルチプロセッサにおける共有変数用キャッシュ
- システム指向型情報工学実験における計算機アーキテクチャ教育
- 動的バリア同期管理機構をもった並列計算機MDBM/FMM
- 並列/分散ソフトウェア開発支援環境の構築
- 細粒度マルチプロセッサMSBM
- 細粒度並列処理のためのハイブリッドスケジューリングシステム : スケジューラによるバリア同期管理手法
- バス結合共有メモリ型マルチプロセッサにおける面状バリア同期機構
- マルチマイクロプロセッサMDBM/FMMの開発
- Beowulfクラスタにおける高精度実行時間測定の検討と評価
- 同期通信用メモリに対する並列化手法と評価
- 同期通信用メモリに対する並列化手法と評価
- マルチプロセッサオンチップにおけるCAMを用いた同期通信用メモリ
- 2D-7 関係データベースを利用した並列化コンパイラの開発
- CAMによる同期通信機構を持ったマルチプロセッサの開発
- CAMを用いた同期機能付き共有レジスタ構成
- 式の分割による並列アルゴリズムESHのスーパースカラ・プロセッサでの評価
- ニューラルネットを用いたエッジ抽出(一般講演-ニューラルネット・解析法・フラクタル-)
- 位相構造を考慮した微小線分特徴の抽出について
- 式の分割による並列化アルゴリズムESHとその評価
- 式の分割による並列化アルゴリズムESH
- 式の自動分割による並列化アルゴリズム
- FMMにおける割込み機能およびその性能予測
- ファジィ制御用プログラミング言語の開発とその応用
- メンバ-シップ関数教示実時間ファジィ制御システムとその倒立振子制御への応用
- 同期通信用メモリにおけるカウンタとブロッキングの効果
- ある格子結合型並列計算機における数値計算への応用
- FMMにおける動的なグループ構成のためのPU管理
- FMMのバリア同期機能を用いたタスクの複数並列実行とその性能予測
- メンバ-シップ関数教示実時間ファジィ制御システムとその倒立振子制御への応用
- ファジィ制御用プログラミング言語の開発とその応用