ヘテロ型大規模並列環境の階層型タスクスケジューリングの提案と評価
スポンサーリンク
概要
- 論文の詳細を見る
我々は大規模な広域分散環境における並列処理を目的とした,タスク並列スクリプト言語MegaScriptを開発している.本言語による並列処理で高性能を達成するには,依存のあるタスク群を非均質環境に効率良くスケジューリングする手法が必要である.しかし,高精度な静的スケジューリングは計算コストが非常に高く,タスクが完全独立でないため単純な動的スケジューリングでは高性能が期待できない.そこで,階層型にスケジューラを配置し,複数の方式を併用するハイブリッド型のスケジューリング方式を提案する.本手法では実行環境のホスト群およびスケジューリング対象であるタスクネットワークを階層モデル化し,階層型スケジューラによる段階的なスケジューリングを行う.上位スケジューラでは抽象モデルによる高速な大域スケジューリングを行い,下位スケジューラでは個々のタスク・ホストに対する詳細な局所スケジューリングを行うことで,大規模なスケジューリングを効率良く扱うことができる.また,動的スケジューリングを併用することで,実行環境の性能変動などによる影響を補正する.抽象シミュレーションにより本手法の評価を行った結果,均質環境用の詳細スケジューリングと比べ,階層型スケジューリングでは7-10倍程度の速度向上が得られ,タスク数/ホスト数が10 000/1 000規模の場合,約1/44の時間でスケジューリングを行うことができた.
- 一般社団法人情報処理学会の論文
- 2009-01-27
著者
-
松本 真樹
三重大学大学院工学研究科
-
片野 聡
三重大学大学院工学研究科
-
佐々木 敬泰
三重大学大学院工学研究科
-
大野 和彦
三重大学大学院工学研究科
-
近藤 利夫
三重大学大学院工学研究科
-
中島 浩
京都大学学術情報メディアセンター
-
片野 聡
三重大学大学院工学研究科:(現)(株)デンソー
関連論文
- 非均質環境における適応型スケジューリング手法の提案と評価(並列分散処理,情報爆発論文)
- 可変パイプライン段数プロセッサの段数切替えスケジューラの設計と評価(ARC-3:アーキテクチャ2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- タスク並列スクリプト言語のビジュアル開発環境の構築(HPC-6 : 開発・実行環境)
- specMEM : 同期操作に対するメモリ・アクセスの投機的実行機構
- 同期操作に対するメモリ・アクセスの投機的実行の評価
- 非均質環境における適応型スケジューリング手法の提案と評価
- リフレッシュピクチャの冗長符号化による低遅延動画像符号化のH.264への適用性(画像符号化,通信・ストリーム技術,及び一般)
- リフレッシュピクチャの冗長符号化による低遅延動画像符号化のH.264への適用性(画像符号化,通信・ストリーム技術,及び一般)
- リフレッシュピクチャの冗長符号化による低遅延動画像符号化のH.264への適用性(画像符号化,通信・ストリーム技術,及び一般)
- 可変パイプラインを用いた低消費エネルギープロセッサの設計と評価(プロセッサ・アーキテクチャ)
- タスク並列スクリプト言語処理系におけるユーザレベル機能拡張機構(分散コンピューティング)
- 並列デバッガにおける情報視覚化手法
- 非均質環境における選択型スケジューリング手法
- 可変レベルキャッシュ用モード切換手法のマルチコア環境への適用と評価
- 大規模ワークフローを対象とする動的スケジューリング手法における静的情報の利用
- IP開発ツール設計に於けるシステム設計から機器開発での問題点と対策
- 可変段数パイプラインプロセッサのチップ試作と評価
- 静的解析による並列論理型言語KL1のメッセージ通信最適化
- KLICにおけるゴール・スケジューリング最適化
- 並列論理型言語処理系KLICにおける通信の高速化
- 並列論理型言語KL1の最適化手法
- 並列論理型言語KL1の最適化手法
- 可変パイプライン段数プロセッサのためのメモリアクセスに着目した細粒度なモード切換えコントローラ(高性能コンピュータシステム,デザインガイア2009-VLSI設計の新しい大地-)
- 高性能かつ低消費電力を実現する可変レベルキャッシュのモード切換アルゴリズムの改良と評価(高性能コンピュータシステム,デザインガイア2009-VLSI設計の新しい大地-)
- VSPプロセッサ用パイプラインレジスタ(LDS-cell)の低電力化手法の提案と評価
- モデル図とコードを併用する大規模並列プログラミングの支援環境
- ヘテロ型大規模並列環境の階層型タスクスケジューリングの提案と評価
- 拡張テンプレート複数併用法と探索区域予測を組み合わせるH.264対応の高効率動き検出法(画像符号化,通信・ストリーム技術,一般)
- 拡張テンプレート複数併用法と探索区域予測を組み合わせるH.264対応の高効率動き検出法(画像符号化,通信・ストリーム技術,及び一般)
- 拡張テンプレート複数併用法と探索区域予測を組み合わせるH.264対応の高効率動き検出法(画像符号化,通信・ストリーム技術,及び一般)
- 拡張テンプレート複数併用法と探索区域予測を組み合わせるH.264対応の高効率動き検出法(画像符号化,通信・ストリーム技術,及び一般)
- 可変段数パイプラインアーキテクチャ(VSP)の更なる低消費電力化手法の提案とLSI設計(コンピュータシステム技術,先端的コンピュータシステム技術及び一般)
- 高性能と低消費電力を両立する可変パイプライン構造の再構成デバイスへの適用(ARC-3:アーキテクチャ2,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- 4K-1 配列の縮退表現による大規模並列タスクネットワークの実装効率化(情報爆発時代における分散処理とセキュリティ,一般セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 大規模ワークフローを対象とする動的スケジューリング手法における静的情報の利用
- 可変レベルキャッシュ用モード切換手法のマルチコア環境への適用と評価
- 不均質環境におけるタスクネットワークの静的スケジューリング手法(HPC-3 : スケジューリング)
- タスクネットワークの解析情報を用いたスケジューリング手法
- VSPプロセッサ用パイプラインレジスタ (LDS-cell) の低電力化手法の提案と評価
- 6K-5 広域分散環境における大規模タスク群の挙動を求める高速シミュレータ(情報爆発時代における並列分散処理技術,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- メガスケール環境シミュレータAnastasiaにおける詳細シミュレーション(HPC-10 :クラスタソフトウェア)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- タスク並列スクリプト言語処理系における広域分散実行方式
- 効率の良い広域分散対応のタスク並列スクリプト言語の実現(HPC-9: 並列プログラミング)
- 拡張テンプレートを複数併用するHDTV用4画素精度動きベクトル検出器の構成(プロセッサ, DSP, 画像処理技術及び一般)
- 拡張テンプレートを複数併用するHDTV用4画素精度動きベクトル検出器の構成(プロセッサ, DSP, 画像処理技術及び一般)
- 拡張テンプレートを複数併用するHDTV用4画素精度動きベクトル検出器の構成(プロセッサ, DSP, 画像処理技術及び一般)
- 拡張テンプレートを複数併用するHDTV用4画素精度動きベクトル検出器の構成(プロセッサ, DSP, 画像処理技術及び一般)
- D-11-23 拡張テンプレートを複数併用するHDTV用4画素精度動き検出器の構成(D-11. 画像工学A(画像基礎・符号化), 情報・システム2)
- D-11-22 照合用拡張テンプレートを複数併用する階層型動き検出(D-11. 画像工学A(画像基礎・符号化), 情報・システム2)
- 分散計算システムWDC用基本ライブラリの構築
- 2000-HPC-82-25 分散計算システムWDCの設計と実装
- Spilt-output Latchを用いたSemi-static TSPC DFFの提案と評価 (VLSI設計技術)
- 共有メモリ・マルチプロセッサの分散シミュレーションのための参照フィルタ方式
- 拡張テンプレート動き検出用4画素精度ビット切り詰め型探索ユニットの設計(ディジタル・情報家電,放送用,ゲーム機用システムLSI,回路技術(一般,超高速・低電力・高機能を目指した新アーキテクチャ))
- 可変レベルキャッシュの書き戻しペナルティ軽減手法の提案(キャッシュ及びプリフェッチ)
- キャッシュ階層動的切り替えによる低消費電力化(ARC-7 : 低消費電力アーキテクチャ,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- VSP(Variable Stages Pipeline)の低消費電力、高性能化(ARC-7 : 低消費電力アーキテクチャ,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- D-11-34 階層探索用の4画素精度ビット切り詰め型ブロックマッチング法(D-11.画像工学A(画像基礎・符号化),一般講演)
- D-11-13 リフレッシュスライスの送出後回しによる低遅延動画像符号化(その2)(D-11.画像工学A(画像基礎・符号化),一般講演)
- 中粒度並列処理用ハードウェア同期処理機構の提案(通信アーキテクチャ)
- ハードウェアスケジューラによるLinux上での近細粒度並列処理の高速化(セキュアシステムとスケジューラ)
- D-11-40 リフレッシュスライスの送出後回しによる低遅延動画像符号化(D-11.画像工学A(画像基礎・符号化),一般講演)
- 適応的に階層実行するら旋状動き探索(画像・映像処理)
- リフレッシュピクチャの冗長符号化による低遅延動画像符号化のH.264への適用性 (放送技術)
- 拡張テンプレート動き検出用4画素精度ビット切り詰め型探索ユニットの設計 (コンシューマエレクトロニクス)
- J-079 段階的探索開始位置決定による螺旋状動き探索の高効率化(J.グラフィクス・画像)
- J-026 テレビ映像に入るパルスノイズの実時間除去方式(J.グラフィクス・画像)
- 巻き戻し実行をサポートする並列プログラムデバッガ
- 並列プログラムデバッギングのための巻き戻し実行機構
- タスク並列スクリプト言語処理系におけるユーザレベルの機能拡張を可能とする機構(HPC-9: 並列プログラミング)
- 大規模分散計算環境シミュレータの設計と実装
- GPGPUにおけるデータ転送自動化コンパイラの設計
- 適応型手法の改良による大規模な実ワークフローの高速スケジューリング
- MegaScriptにおける大規模ワークフローの縮約機構の設計
- イン・オーダ・パイプラインに適した可変パイプライン段数プロセッサ制御機構の実装と評価
- 静的解析と動的処理の組合せによるエージェント指向並列言語Orgelのスケジューリング
- 静的解析と動的処理の組合せによるエージェント指向並列言語Orgelのスケジューリング
- プロセスネットワークを宣言的に記述する並列言語
- エージェント指向並列言語Orgelの静的解析による最適化
- マルチエージェントパラダイムと宣言的通信ストリームに基づく並列言語
- 可変パイプライン構造による低消費電力技術を用いた浮動小数点演算器の実装および評価(ARC-3: 低電力アーキテクチャ1, 2005年並列/分散/協調処理に関する『武雄』サマー・ワークショップ(SWoPP武雄2005)-研究会・連続同時開催-)
- クロック系消費電力に着目した可変段数パイプラインプロセッサの低電力化(計算機システム)
- タスク並列スクリプト言語におけるストリーム通信の改良(HPC-1 : 並列プログラミング)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- 配列の縮約表現による大規模ワークフローの効率的実装手法
- 静的情報を用いた動的再スケジューリングのオーバヘッド削減手法
- タスクネットワークの形状に基づく並列スクリプト言語のスケジューラ(一般講演1)
- Split-output Latchを用いたSemi-static TSPC DFFの提案と評価(論理設計1,システムオンシリコンを支える設計技術)
- J-078 適応的なフィルタリングを用いた画像の性質にロバストな動き探索(J.グラフィクス・画像)
- 方向別拡張テンプレートを複数併用する粗密探索構成の動き検出法(画像・映像処理)
- 三段階対応の可変レベルキャッシュのマルチスレッドアプリケーションを用いた評価
- ヘテロジニアスマルチプロセッサ環境を対象としたAMBAバスフレームワークの設計と評価
- J-075 リフレッシュピクチャの分割送出による動画像符号化の遅延低減(J.グラフィクス・画像)
- 可変パイプライン段数アーキテクチャへのパワーゲーテイング適用による低消費エネルギー効果の評価(設計手法及び一般,デザインガイア2011-VLSI設計の新しい大地-)
- 可変パイプライン段数アーキテクチャへのパワーゲーティング適用による低消費エネルギー効果の評価
- GPGPUのシェアードメモリを利用する自動最適化機構
- タイル・ライン変換機能を備えた動き探索用ロードバッファの提案(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- タイル・ライン変換機能を備えた動き探索用ロードバッファの提案(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- タイル・ライン変換機能を備えた動き探索用ロードバッファの提案(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- タイル・ライン変換機能を備えた動き探索用ロードバッファの提案(システムLSIの応用と要素技術,プロセッサ,DSP,画像処理技術及び一般)
- FabScalarを用いた可変段数パイプライン構造を有するスーパスカラプロセッサの詳細設計(マイクロアーキテクチャ,並列/分散/協調とディペンダブルコンピューティング及び一般)