8-隣接格子結合網による奇偶変換ソート
スポンサーリンク
概要
- 論文の詳細を見る
筆者は先に8-隣接格子結合網によるバイトニック・マージソートのアルゴリズムを報告したが、本文では奇偶変換ソートを包線(wraparound)を持つ8-隣接格子結合網に適用した二次元ソーティング・アルゴリズムについて述べる。本アルゴリズムはmin_sortと呼ばれる基本演算を繰り返し実行するだけで行主体順序のソートを行う。ソーティング時間Tは要素数をN=n×nとしたとき、T=3n(2t_r+t_c)である。ここで、t_rは隣接したプロセッサ間での単位転送時間であり、t_cは単位比較交換時間である。なお、要素数Nは、N=n_x×n_y, n_x=2i, n_y=2j)で,i,j>1であるが、以下N=n×nとして説明する。また、そのソーティング時の要素の移動経路が螺旋状に見えることから、本アルゴリズムを螺旋ソート(spiral sort)と呼ぶことにする。
- 1989-03-15
著者
関連論文
- 並列FFTアルゴリズムと並列計算機への実装
- 8-隣接格子結合網による奇偶変換ソート
- 8隣接プロセッサ・アレイによるニューラルネットワークの並列処理
- 8隣接プロセッサ・アレイによるニューラルネットワークの並列処理
- 平板音さの共振周波数と振動姿態
- 双共振音さとそのメカニカル・フィルタへの応用について
- 高速LANのための負荷適応型帯域割当て方式
- 負荷適応型高速LANプロトコル
- 高速LANのための適応型リングプライオリティ自己トークンプロトコル (マルチメディア通信と分散処理)
- リングプライオリティ型自己トークンプロトコルの性能解析
- 分散共有メモリ型並列計算機上での並列FFTアルゴリズムの実装評価
- 分散情報共有システムATRASにおけるインタラクティブ・ユーザ・インタフェース
- 分散情報共有システムATRASにおけるインタラクティブ・ユーザ・インタフェース
- 分散情報探索のための情報管理エージェント
- 進化的情報探索エージェントについて
- 基数Rの並列FFTアルゴリズムの通信コスト
- ネットワーク上に分散した情報の共有について
- 自己トークンプロトコルによる高速リングLAN
- グローバル通信を用いた並列FFTアルゴリズムと超並列計算機への実装
- リングプライオリティ型自己トークンLAN
- 自己トークンプロトコルによる高速リングLANsの公正さの解析
- ATMネットワークのABRサービスに対する自己検知型輻輳制御方式
- パケット交換網のウインドウ・フロ-制御機構における受信動作の解析
- ウインドウ機構の性能評価
- ウインドウ機構の発見的近似解析(技術談話室)
- S形音片の共振周波数と振動姿態
- 静止画送信を制御するATMネットワークのファジィ・ポリシング機構
- ファジィ集合理論を用いたATMネットワークのためのポリシング機構の設計
- ファジィ集合理論を用いたATMネットワークのためのポリシング機構の設計
- 8隣接格子網の性能評価
- わずかにランダム性をもつソ-スからのランダム性の抽出
- 並列FFTと通信時間の評価
- 8隣接プロセッサ・アレイによる並列2-D FFT アルゴリズム