グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム(<特集>シンポジウム)
スポンサーリンク
概要
- 論文の詳細を見る
タスクスケジューリング問題の目的関数として最も一般的なものはメイクスパンである.しかし計算グリッドを対象とする場合, 計算グリッドを構成する各計算機の余剰計算力は時間の経過につれて変化するため, 2番目に小さいメイクスパンは最適メイクスパンよりいくらでも大きくなりうる.このため, スケジュールの評価基準をメイクスパンとする場合は, 計算グリッドを対象とするタスクスケジューリング問題に近似アルゴリズムは一般には存在しない.本論文では, スケジュールの新しい評価基準として, 余剰計算力の消費量を用いることを提案する.さらに本論文では, この評価基準の最小化を目的として, 同じサイズのn個の独立粗粒度タスクをmプロセッサの計算グリッドに動的にスケジューリングする問題に対して, (1+m(log_e(m-1)+1)/n)-近似アルゴリズムを提案する.提案アルゴリズムは計算グリッドの性能予測をまったく必要としない.提案アルゴリズムの近似率は, プロセッサ数を固定してタスク数を大きくしていくと急激に最適値に近づいていく.この結果は, プロセッサ数にくらべてタスク数が相応に大きい場合は, 各プロセッサの負荷が動的にどのように変動しようとも, その予測なしに, パラメータ・スウィープ型アプリケーションが消費する余剰計算力をほぼ最適に抑えられることを示している.
- 一般社団法人情報処理学会の論文
- 2005-06-15
著者
関連論文
- CUDAによる高速なコーンビーム再構成の実装と性能評価(プログラミング環境,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- D-11-80 GPUによるTotal Variation Minimization法の高速化(D-11.画像工学,一般セッション)
- GPUグリッドにおいて描画および科学計算を並行処理するための制御手法(カーネル)
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(夏のデータベースワークショップ2007(データ工学,一般))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(検索エンジン応用,夏のデータベースワークショップ2007(データ工学,一般))
- Webを対象としたロボット型住所関連情報検索システムの開発(Web検索,データ工学論文)
- GPUによるOSEM再構成の高速化及び精度評価(医用システム,システム開発論文)
- 大規模データセットを可視化するための効率の良い並列ボリュームレンダリング(並列処理応用)
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- GPUによるOSEM再構成の高速化および精度評価(基盤技術1)
- R3Qによる進化型計算の中粒度Gridスケジューリング(グリッド)
- 時系列ボリュームレンダリングの描画速度を調節するための非可逆圧縮手法
- GPUを用いたコーンビーム再構成の性能評価と精度検証(画像再構成)
- 複数のCUDA互換GPUによるストリーム処理のためのミドルウェア
- CUDAカーネルの性能を解析するための実行履歴生成ツール
- CUDAプログラムにおいてストリーム処理を支援するミドルウェア
- GPUクラスタによる高速なアミノ酸配列データベース検索
- CUDAによるパラメータ・スイープアプリケーションの高速化
- CUDAを用いた高速なモルフォロジー演算
- CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 統合開発環境CUDAを用いたGPUでの配列アライメントの高速化手法(メモリアクセス,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- CUDAによる全点対最短経路問題の高速化(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- CUDAによる高速なコーンビーム再構成の実装と性能評価(プログラミング環境,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 統合開発環境CUDAを用いたGPUでの配列アライメントの高速化手法(メモリアクセス,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- GPU上での高速なブロック化フロイド・ワーシャル法
- 複数の並列計算環境に対応したMapReduceのPythonによる実装
- 術中における対話的な医用画像処理のための遠隔並列計算環境の構築 : 手術支援グリッドの実現に向けて
- 術中二次元/三次元剛体位置合せのための並列化手法(ディペンダブルコンピューティング)
- GPUを用いてコーンビームCTのボリューム再構成を高速化する手法(一般セッション,センシング技術とその応用)
- GPU内部におけるプロセッサ間の命令移動による高速化ツール
- GPUアプリケーションを高速化するための命令割当て方式(GPU応用)
- デスクトップ・ボリュームレンダリングのための解像度制御によるビデオメモリ使用量削減(ハードウエアによるCG処理およびCG一般)
- 並列再帰の実行方式をプログラマが指定可能なコンパイラの評価
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- デスクトップグリッド環境でのマルチジョブスケジューリングにおけるジョブの追い越しを防ぐジョブ優先度制御
- A_002 企業イントラグリッドでのジョブ割当てアルゴリズムの比較評価(A分野:モデル・アルゴリズム・プログラミング)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップDBWS2005)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップ2005)
- グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム(シンポジウム)
- PCクラスタを用いた並列非剛体位置合わせ手法の性能評価(可視化・レジストレーション)
- タスク複製率とプロセッサ***率に着目したBSPスケジュール生成手法の提案
- グリッド環境において計算結果を効率よく再利用するための通信量削減(HPC-2 : 通信方式)
- D-16-7 GPUを用いた逐次近似法によるコーンビーム再構成の高速化(D-16.医用画像,一般セッション)
- GPUを用いたアウトオブコアなコーンビーム再構成の高速化
- 検索可能な樹状ヒストリ機能を備えたホワイトボードシステム"S.W.ボード"の提案と実装
- 会合における備忘録をもとに一次記録を検索参照する会合情報記録検索システムReSPoM(:知識と情報の共有)
- 検索可能な樹状ヒストリ機能を備えたホワイトボ-ドシステム"S.W.ボ-ド"の提案と実装
- 会合記録の関連性に着目した会合記録検索支援システムの実装
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- スケール不変な格子を生成する適応格子細分化法アプリケーションのための計算量予測手法(アルゴリズム理論)
- グリッドアプリケーションの実行時間を短縮するための計算結果再利用機構の評価
- 適応格子細分化法を用いる画像処理のための実行時間予測手法(ポスターセッション)
- 汎用グラフィクスハードウェアを用いた2次元/3次元剛体位置合わせの高速化(コンピュータグラフィックス)
- 汎用グラフィクスハードウェアを用いた2方向投影による2次元/3次元剛体位置合わせ(再構成他, 医用画像一般)
- 汎用グラフィクスハードウェアを用いた2次元/3次元剛体位置合わせの高速化(HPCシステム)
- フラクタル解析による適合格子細分化法の計算量予測
- 短時間処理向け資源管理を実現するためのGlobus Toolkitの性能評価(グリッド(2), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- PCクラスタを用いた2次元/3次元剛体位置合わせの高速処理(レジストレーション・イメージマッチング)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- MI-Cluster : 術中医用画像処理を実現するPCクラスタシステム
- 夢はバラ色 予測医学基盤オープンプラットフォームの構築に向けて
- 手術ロボットのための医用画像処理技術 : 最近の進展と将来の方向 : 日本学術振興会未来開拓学術推進事業「術中における多次元画像の獲得と利用」の成果を中心として
- GPUによる高速なコーンビーム再構成:円軌道装置のためのRGBAデータへの詰め込み
- GPUを用いてコーンビームCTのボリューム再構成を高速化する手法(一般セッション,センシング技術とその応用)
- 複数の並列計算環境に対応した MapReduce の Python による実装
- B-007 実時間グリッド計算のための資源割当システムの設計(B.ソフトウェア)
- 分散メモリ型並列計算機を用いた非剛体レジストレーションの並列化
- プロセッサグループの動的分割による並列再帰プログラムの実現手法
- 並列型画像処理ライブラリの高効率化(JAMITセッション)
- 3次元並列型画像処理ライブラリ開発における基礎的検討(再構成他, 医用画像一般)
- GPGPUアプリケーションの開発を支援するための性能モデル(GPU応用)
- スケーラビリティのあるWWW並列全文検索システム構築法の提案と評価
- D-11-90 大規模なマルチスケールボリュームレンダリングのための先読み手法の検討(D-11.画像工学D(画像処理・計測),一般講演)
- GPUによる高速な全変動最小化
- GPUを装備する計算機を計算資源とするグリッドにおける資源選択手法の検討
- (83)通常講義の中でのPBL演習の試み(第21セッション 創成教育(I))
- ボリュームレンダリングにおける効率的なテクスチャ参照
- インタプリタ型汎用生体シミュレータinsilicoSimのGPUによる高速化
- 系列パターン抽出のMapReduce実装におけるタスク分割方式の検討
- JPEGアルゴリズムにブロック比較法を適用した画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- 進化戦略のためのグリッド計算に関する一考察(進化・学習とロボティクス3)
- 共有した電子ノートにおけるビデオシーンの注目度を利用する学習支援システム
- 累積不透明度の伝搬による並列ボリュームレンダリングの計算量削減(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(CPSY-6並列分散ソフトウェア)
- 投影面分割に基づく階層的な画像合成手法を用いた並列ボリュームレンダリング
- 投影面分割に基づく階層的な画像合成手法を用いた並列ボリュームレンダリング(高速ネットワークとマルチメディアアプリケーション)
- GPUによる高速な全変動最小化(計算機システム)
- GPUグリッドによる高速な塩基配列アライメント(HPC-5 : アプリケーションI)
- CUDAプログラムにおけるメモリ参照効率を解析するための実行履歴生成手法
- 遺伝子配列に対するペアワイズアライメントのGPUによる高速化
- 重複排除ストレージにおけるSHA-1計算のSSEによるスループット向上手法
- GPUにおいてパラメータスイープを高速化するための並列方式
- 正規化相互情報量に基づく非剛体位置合わせのCUDAによる高速化(位置合わせ・神経回路,ポスターティーザー1,統計モデルとその応用,医用画像一般)