プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
スポンサーリンク
概要
- 論文の詳細を見る
PapadimitriouとYannakakis`の並列計算機のアーキテクチャ独立モデルに対して,単位時間のタスクのみからなる完全2分木状のタスク依存グラフを対象としたタスクスケジューリングアルゴリズムを2つ示す.さらにスケジュールの実行時間の既知の下界を改良する.一般のdag(directed acyclic graph)に対するタスクスケジューリング問題の最適解を求める問題は,対象を単位時間のタスクのみからなるdagに限定してもNP困難であることと,近似精度2倍以内の一般のdagに対する近似アルゴリズムが知られているが,本論文で提案するアルゴリズムにより,2から10000のすべての整数の範囲のプロセッサ間通信遅延τと,高さ20以内の完全2分木に対して,実行時間が最適スケジュールの平均1.1倍から1.3倍以内程度のスケジュールが得られることを実験的に示す.さらに,生成されるスケジュールの(必要プロセッサ数×実行時間)を実験的に評価して,2つのアルゴリズムの応用範囲について考察する.
- 1994-03-10
著者
-
藤本 典幸
大阪大学大学院情報科学研究科
-
首藤 勝
大阪大学大学院基礎工学研究科
-
首藤 勝
大阪大学基礎工学部情報工学科
-
藤本 典幸
大阪大学基礎工学部
-
魚井 宏高
大阪大学基礎工学部
-
萩原 兼一
奈良先端科学技術大学院大学
-
首藤 勝
大阪大 大学院
-
柘植 宗俊
大阪大学大学院基礎工学研究科
-
柘植 宗俊
奈良生端科学技術大学院大学
関連論文
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(夏のデータベースワークショップ2007(データ工学,一般))
- ウェブを対象としたロボット型検索による指定地理座標周辺の住所関連情報検索手法の提案(検索エンジン応用,夏のデータベースワークショップ2007(データ工学,一般))
- Webを対象としたロボット型住所関連情報検索システムの開発(Web検索,データ工学論文)
- 協調フィルタリングを用いて個人の嗜好を反映するレシピ検索手法の提案
- R3Qによる進化型計算の中粒度Gridスケジューリング(グリッド)
- GPUの汎用計算環境CUDAによる主記憶上の大規模なテキストに対する高速な全文検索の検討(アプリケーション高速化,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2008))
- 術中における対話的な医用画像処理のための遠隔並列計算環境の構築 : 手術支援グリッドの実現に向けて
- 進化計算のためのグリッドコンピューティング
- 並列再帰の実行方式をプログラマが指定可能なコンパイラの評価
- 分割統治法アルゴリズムの効率的な並列化手法とそのコンパイラの実装
- 分割統治法プログラムを並列実行するコンパイル手法の提案と評価
- λコンピューティング環境における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型並列アルゴリズム解析ツール
- プロセッサグループの動的分割による並列再帰プログラムの実現手法
- アニメーションを用いた並列アルゴリズム学習支援環境の構築
- スケーラビリティのあるWWW並列全文検索システム構築法の提案と評価
- 並列型全文検索システム構築のための手法の提案とその評価
- スケーラビリティを考慮した並列再帰の実行方式の提案と評価
- 計算グリッド上でのパラメータ・スウィープ計算を対象とした性能保証のある動的タスクスケジューリング
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信遅延を考慮した完全k分木の近似タスクスケジューリングアルゴリズム
- 通信の一括化に適したタスクスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリングアルゴリズム
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリング手法
- 分散メモリ型並列計算機の通信特性を考慮したスケジューリングアルゴリズムの開発とその評価
- JPEGアルゴリズムにブロック比較法を適用した画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- JPEGアルゴリズムにおけるブロックの類似性を活かした画像圧縮法の改善と評価
- 進化戦略のためのグリッド計算に関する一考察(進化・学習とロボティクス3)
- 分散メモリ型並列計算機による高解像度ボリュームレンダリング(バイオメトリクスシステムおよび一般)
- グリッド環境における独立粗粒度タスク集合の動的スケジューリングアルゴリズムの性能評価
- 並列アルゴリズムに適用した確率アルゴリズムの性能評価の試み (並列処理)
- 並列アルゴリズムに適用した確率アルゴリズムの性能評価の試み
- 遠隔ゼミナール支援システムのインターネットを介した適用と評価 (マルチメディア分散・協調コンピューティング)
- 遠隔ゼミ支援システムRemote Wadamanの開発と適用
- 遠隔ゼミ支援システムの3地点運用を考慮した改良
- KJ法文章のVA手法に基づく評価法の提案と実装
- タスクグラフ分割を用いた並列処理によるスケジューリングアルゴリズムBCSHの大規模細粒度グラフへの適用
- 遠隔研究指導支援システムの開発
- ビデオアーカイブを利用した学習を支援するシステムの提案
- ビデオアーカイブを利用した学習を支援するシステムの提案
- SPMD プログラムを生成する Work-Time C 処理系の実現
- 並列プログラムの性能改善支援機能を持つ性能解析システム : Gordini(並列処理)
- 並列プログラムの改善支援機能を持つ性能解析システムの開発
- 1対1プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム
- 一対一プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム
- 最小値関数を用いて適合度を算出するNRA検索アルゴリズムの改善
- 最小値関数により適合度を算出するNRA検索アルゴリズムの改善
- グリッド環境における計算ノードの故障を考慮した独立タスクのスケジューリングアルゴリズム
- MPI-PreDebugger : 通信依存解析に基づくメッセージ通信並列プログラム向けデバッグ支援ツール
- LogGPS : メッセージ通信プロトコルの切替えを考慮した高水準通信ライブラリ向けの並列計算モデル
- 内容と構造を対象としたKJ法B型文章評価方法の提案と適用
- 動画アイコンの開発と適用
- 動画アイコンの開発と適用
- ペトリネットによるKJ法B型文章の構造の評価に関する検討
- インターネットを介して実施した分散協調型KJ法に関する考察
- 平衡2分探索木に対する並列オンライン操作
- パイプライン化による平衡2分探索木に対する並列操作