プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリングアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
任意のプロセッサ間通信遅延時間を単一のパラメータγで抽象化した並列計算モデル上でタスクスケジューリング問題の最適解を求める問題は, 利用するプロセッサ数を任意に設定でき, かつ, すべてのタスクの処理時間が単位時間である場合にNP困難であり,近似精度2倍以内の一般のdagに対する近似アルゴリズムが知られている. 本論文では, 任意の形状のdag(directed acyclic graph)に対してスケジュールの実行時間の既知の下界を改良し, 完全2分木状のdagを対象としたスケジューリングアルゴリズムを示す. 更に改良した下界を用いて提案するアルゴリズムの近似精度をより正確に評価し, 少なくとも2から300の範囲のγと, ノード数100万以内の完全2分木に対して, 提案するアルゴリズムにより最適スケジュールの平均1.1倍から1.3倍以内程度の実行時間のスケジュールを得ることを示す. 更に, 本論文で提案するもう一つのアルゴリズムが, プロセッサ割当てが非常に単純であるにもかかわらず, 最適スケジュールの平均1.1倍から1.4倍以内程度のスケジュールを生成することを示す.
- 1997-04-25
著者
-
藤本 典幸
大阪大学大学院情報科学研究科
-
萩原 兼一
大阪大学基礎工学部情報工学科
-
首藤 勝
大阪大学大学院基礎工学研究科
-
首藤 勝
大阪大学基礎工学部情報工学科
-
藤本 典幸
大阪大学基礎工学部
-
首藤 勝
大阪大 大学院
-
柘植 宗俊
大阪大学基礎工学部情報工学科
-
柘植 宗俊
大阪大学大学院基礎工学研究科
関連論文
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(夏のデータベースワークショップ2007(データ工学,一般))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(検索エンジン応用,夏のデータベースワークショップ2007(データ工学,一般))
- Webを対象としたロボット型住所関連情報検索システムの開発(Web検索,データ工学論文)
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- R3Qによる進化型計算の中粒度Gridスケジューリング(グリッド)
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 術中における対話的な医用画像処理のための遠隔並列計算環境の構築 : 手術支援グリッドの実現に向けて
- 拡張されたヒープ領域管理機能をもつPASCAL処理系ELPH
- PASCALシンボリック・デバッガの作成
- 分枝限定法の並列化と並列計算機での実行
- 分枝限定法の並列化と並列計算機での実行
- 進化計算のためのグリッドコンピューティング
- 並列再帰の実行方式をプログラマが指定可能なコンパイラの評価
- 分割統治法アルゴリズムの効率的な並列化手法とそのコンパイラの実装
- 分割統治法プログラムを並列実行するコンパイル手法の提案と評価
- λコンピューティング環境におけるOpenMPアプリケーションによる共有メモリシステムの評価
- λコンピューティング環境におけるOpenMPライブラリの設計と実装(フォトニックネットワークシステム,光ルーチング,ブロードバンドアプリケーション,一般)
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- ベイジアンネットワークモデルを用いた衣服コーディネイト推薦システムの開発
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- デスクトップグリッド環境でのマルチジョブスケジューリングにおけるジョブの追い越しを防ぐジョブ優先度制御
- 余剰計算力を用いるグリッドのジョブスケジューリングにおける優先度制御の一手法(セッション2)
- A_002 企業イントラグリッドでのジョブ割当てアルゴリズムの比較評価(A分野:モデル・アルゴリズム・プログラミング)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法(データ工学, ディペンダビリティ, 一般)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップDBWS2005)
- ウェブマルチメディア検索のためのパーソナルシステム(データ可視化, 夏のデータベースワークショップ2005)
- グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム(シンポジウム)
- アルゴリズムの段階的学習を支援することを目的とした階層型アニメーションの実装と評価
- タスクスケジューリングを用いた並列プログラム生成におけるタスク粒度の調整とその評価
- タスク複製率とプロセッサ***率に着目したBSPスケジュール生成手法の提案
- 検索可能な樹状ヒストリ機能を備えたホワイトボードシステム"S.W.ボード"の提案と実装
- 会合における備忘録をもとに一次記録を検索参照する会合情報記録検索システムReSPoM(:知識と情報の共有)
- 検索可能な樹状ヒストリ機能を備えたホワイトボ-ドシステム"S.W.ボ-ド"の提案と実装
- 会合記録の関連性に着目した会合記録検索支援システムの実装
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- 会合における情報の関連性を記録するためのインタフェースの検討と評価
- 発想支援グループウェアの実施に及ぼすテキストベースコミュニケーションの影響(分散協調支援とその応用)
- チャットに注目した発想支援グループウェアのコミュニケーションに関する検討
- チャットに注目した発想支援グループウェアのコミュニケーションに関する検討
- インターネットを用いた多地点研究指導実験
- 音声に重点を置いたネットワークに関する検討
- 発想支援におけるマルチメディアコミュニケーションの各メディアの役割とその対応
- MI-Cluster : 術中医用画像処理を実現するPCクラスタシステム
- 制御の流れに重点をおいてアルゴリズム学習を支援するシステムの構想
- 段階的学習を支援することを目的とした階層的アニメーションの実装と評価
- 図形表現とテキスト表現を併用したプログラム実行状態の可視化
- 能動的学習を支援するためのアルゴリズムアニメーションの拡張法に関する考察
- ミニコンによるある連想記憶システムの作成について
- グループ知的生産支援システムSharedWadaman
- 知的生産支援システムWadaman
- 知的生産支援システムWadamanのグループウェア化の実現
- 知的生産支援システム Wadaman のグループウェア化 : SharedWadaman
- 知的生産支援システム Wadaman のグループウェア化 : SharedWadaman
- コミュニケーション手段が異なる分散協調型KJ法のインターネットを介した実施
- 共有メモリ式SIMD型並列アルゴリズム解析ツール
- プロセッサグループの動的分割による並列再帰プログラムの実現手法
- アニメーションを用いた並列アルゴリズム学習支援環境の構築
- 階層情報の3次元視覚化に関する評価
- スケーラビリティのあるWWW並列全文検索システム構築法の提案と評価
- 並列型全文検索システム構築のための手法の提案とその評価
- スケーラビリティを考慮した並列再帰の実行方式の提案と評価
- 計算グリッド上でのパラメータ・スウィープ計算を対象とした性能保証のある動的タスクスケジューリング
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信の一括化に適したタスクスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- 分散メモリ型並列計算機の通信特性を考慮したスケジューリングアルゴリズムの開発とその評価
- JPEGアルゴリズムにブロック比較法を適用した画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- 音声メニュー同時提示方法の提案と評価
- 動的なパラメータ指定機能をもつあるデバッグシステム
- 進化戦略のためのグリッド計算に関する一考察(進化・学習とロボティクス3)
- 分散メモリ型並列計算機による高解像度ボリュームレンダリング(バイオメトリクスシステムおよび一般)
- グリッド環境における独立粗粒度タスク集合の動的スケジューリングアルゴリズムの性能評価
- 並列アルゴリズムに適用した確率アルゴリズムの性能評価の試み (並列処理)
- タスクグラフ分割を用いた並列処理によるスケジューリングアルゴリズムBCSHの大規模細粒度グラフへの適用
- ビデオアーカイブを利用した学習を支援するシステムの提案
- ビデオアーカイブを利用した学習を支援するシステムの提案
- SPMD プログラムを生成する Work-Time C 処理系の実現
- 並列プログラムの性能改善支援機能を持つ性能解析システム : Gordini(並列処理)
- 並列プログラムの改善支援機能を持つ性能解析システムの開発
- 1対1プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム
- 一対一プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム
- 最小値関数を用いて適合度を算出するNRA検索アルゴリズムの改善
- 最小値関数により適合度を算出するNRA検索アルゴリズムの改善
- グリッド環境における計算ノードの故障を考慮した独立タスクのスケジューリングアルゴリズム
- MPI-PreDebugger : 通信依存解析に基づくメッセージ通信並列プログラム向けデバッグ支援ツール
- LogGPS : メッセージ通信プロトコルの切替えを考慮した高水準通信ライブラリ向けの並列計算モデル
- 平衡2分探索木に対する並列オンライン操作
- 3. ハードウェアアルゴリズムの設計法 3.2 ハードウェアアルゴリズムの記述と検証 (VLSI向きハードウェアアルゴリズム)
- 2. ハードウェアアルゴリズムの基礎理論 2.3 VLSIモデルと面積複雑度 (VLSI向きハードウェアアルゴリズム)
- パイプライン化による平衡2分探索木に対する並列操作
- システム記述用言語Cのポータブルコンパイラの作成