ヘテロジニアスBSPモデル上の2次元データ分割
スポンサーリンク
概要
- 論文の詳細を見る
HBSP(Heterogeneous Bulk-Synchronous Parallel)モデルは非同期式並列計算モデルであり,具体的な通信特性などは,いくつかのパラメタにより抽象化されている.本稿ではpプロセッサを用いたHBSPモデル上で,まずサイズn×nの2次元データに対し,各プロセッサP_iの速度S_iに応じてO(n^2s_i/？^<p-1>_<k=0>sk)個の部分データを割り当て,かつその部分データの縦横の長さの合計がO(n√<p>)となる分割法を示す.次に,その分割法を用いて行列積に対し内部計算時間O(n^3/？^<p-1>_<k=0>sk+L),通信時間O((n^2s_i/？^<p-1>_<k=0>sk+p/so)g+L)である並列アルゴリズムを提案する.
- 社団法人電子情報通信学会の論文
- 2002-09-23
著者
関連論文
- D-1-11 非同期膜計算による充足可能性問題とハミルトン路問題の解法(D-1.コンピュテーション,一般セッション)
- DNA計算における対数時間ソートアルゴリズム
- ヘテロジニアスBSPモデル上の2次元データ分割
- 選択問題を解くBSPモデル及びBSP^*モデル上の並列アルゴリズム
- 2値画像上の全最近点を求めるBSPモデル上の並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム(並列・分散)
- 選択問題を解くBSPモデルおよびBSPモデル上の並列アルゴリズム
- D-1-2 GRID 環境に適した効率の良い完全交換アルゴリズム
- 膜計算における基本演算アルゴリズム
- 検知領域交点を考慮した連結センサカバーアルゴリズム
- DNA計算による浮動小数点演算アルゴリズム
- 最小スループット制御を行うアクセスポイント選択手法
- A-006 局所探索を用いた集中型アクセスポイント選択アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- A-005 DNA計算におけるMAX-SATの解法(A分野:モデル・アルゴリズム・プログラミング)
- A-004 重み付けを用いた分散型アクセスポイント選択アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- A-003 DNA計算における乗算および除算アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- 無線LANにおけるAP選択戦略に関する検討(NW性能管理,NW品質,一般)
- 無線LANにおけるAP選択戦略に関する検討(NW性能管理,NW品質,一般)
- DNA計算における対数時間ソートアルゴリズム
- DNA計算における奇偶転換ソート及びシェアソートアルゴリズム
- DNA計算における奇偶転換ソート及びシェアソートアルゴリズム
- A-017 グリッド環境における完全交換に対するスケジューリングアルゴリズム(A.モデル・アルゴリズム・プログラミング)
- A-008 組み合わせ最適化アルゴリズムに基づく研究室配属システムの開発(A.モデル・アルゴリズム・プログラミング)
- A-003 DNAを用いた0-1整数計画問題の解法(A.モデル・アルゴリズム・プログラミング)
- Procedures for Multiple Input Functions with DNA Strands (Evolutionary Advancement in Fundamental Theories of Computer Science)
- D-1-4 DNA 計算における最大値計算および辞書演算
- 2値画像の重みつき距離変換を行なう並列アルゴリズム
- P-完全問題に対する幾つかの多項式的に加速する並列アルゴリズム
- D-1-7 Polynomially fast parallel algorithms for some P-complete problems
- タイマを用いる有限状態機械でモデル化されたシステムの検証手続き
- タイマを用いる有限状態機械でモデル化されたシステムの検証手続き
- Cost optimal parallel algorithms for $P$-complete problems (Algorithm Engineering as a New Paradigm)
- P2Pシステムにおける確率的弱コーラムシステムを用いた自己適応的探索手法(セッション4)
- D-1-4 抑制性ニューロンを用いたSN Pシステムにおける素因数分解(D-1.コンピュテーション,一般セッション)
- 2分木の平衡分解木を求めるコスト最適な並列アルゴリズム(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- ペイシェンス・ソートおよび最長昇順部分列問題に対するコスト最適な並列アルゴリズム
- スタックを用いた幅優先探索に関する並列アルゴリズム
- 辞書式順極大3和問題に対するBSPモデル上のコスト最適な並列アルゴリズム
- ソート点集合の凸包を求める定数通信ラウンドの並列アルゴリズム
- P完全問題に対するBSPモデル上の並列アルゴリズム
- JSPP '99参加報告(学術会合報告)
- P完全問題の実用的な並列性について
- メッシュ上でユークリッド距離変換を行う並列アルゴリズム
- 故障封じ込め自己安定プロトコルに対するタイマーを利用した合成手法
- 濃淡画像の連結成分を求める並列アルゴリズム