パワーリスト記述からのハイパキューブアルゴリズムの生成(計算論,計算モデル)
スポンサーリンク
概要
- 論文の詳細を見る
Misraが提案したパワーリストは,並列再帰構造を仕様記述するためのデータ構造である. Achatz and Schulteはパワーリスト関数による仕様記述から,相互結合網非依存の超データ並列アルゴリズムを生成する手法を提案した.Achatzらが対象としたのは分割統治型のパワーリスト関数であり,その他のパワーリスト関数についてアルゴリズムを生成できない.我々は相互結合網をハイパキューブに制限することでAchatzらの手法を拡張した同種分解可能,交差分解可能と呼ぶ二つのパワーリスト関数のクラスを提案する.そして,それらの関数から時間計算量がO(n)であるn次元ハイパキューブアルゴリズムが生成可能であることを示す.
- 社団法人電子情報通信学会の論文
- 2007-11-01
著者
関連論文
- 16セグメントディスプレイ上の英字パターンの一斉射撃問題
- k-グラフ生成文法
- 点の次数3以下のグラフに対する2部グラフ化問題
- 変換履歴の再利用による高レベルのプログラム変換
- 6N-10 MPIプログラムのためのランダム遅延によるUnit Testing Framework(数値計算とコンパイラ技術,学生セッション,アーキテクチャ)
- AND-EXOR論理式の簡単化並列アルゴリズム
- 拡張前提式を用いたATMSの並列化
- リフレクション原理によるフレームシステムの拡張
- 可逆論理回路のToffoliゲート数の下界(研究速報)
- AND-EXOR論理式最小化アルゴリズム
- AND-EXOR論理式最小化アルゴリズム
- AND-EXOR論理式最小化アルゴリズム
- D-1-3 アレンジメントグラフのスターグラフへの埋め込み
- パワーリスト記述からのハイパキューブアルゴリズムの生成(計算論,計算モデル)