ベンズINのための並列パーミュテーションアルゴリズムの下限値の導出

• Item type: SIG Technical Reports(1)
• 公開日: 1988-03-10
• タイトル: ベンズINのための並列パーミュテーションアルゴリズムの下限値の導出
• タイトル / 言語: en
• タイトル: Lower Bound Derivation of Parallel Permutation Algorithm for Benes Network - With Restricted Parallelism
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東北大学電気通信研究所
• 著者所属: 東北大学電気通信研究所
• 著者所属: 東北大学電気通信研究所
• 著者所属(英): en
• 著者所属(英): Research Institute of Electrical Communication, Tohoku University
• 著者所属(英): en
• 著者所属(英): Research Institute of Electrical Communication, Tohoku University
• 著者所属(英): en
• 著者所属(英): Research Institute of Electrical Communication, Tohoku University
• 著者名: アィサムA, ハミド; 白鳥, 則郎; 野口, 正一
• 著者名(英): Issam, A.Hamid; Norio, Shiratori; Shoichi, Noguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では、ベンズIN(Interconnection Network)において、制限された並列性について議論し、並列パーミュテーションアルゴリズムの下限値として、O((Φ/N)log_εN)を導出する。ここで、Nは入力の数、Φは計算モデルを構成する処理要素の総数、εは直接に結合されている隣接する処理要素の数を示す。この下限値は、N≫Φ（これを制限された並列性と呼ぶ）の場合に有用である。また、NやΦに加えて、εが並列パーミュテーションアルゴリズムの複雑さに影響を与えることを証明する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This companion paper has discussed the limited restriction of parallelism, such that we have derived the lower bound of parallel permutation algorithms as O((Φ/N) log_εN), where ε, is the number of the neighboring Processing Elements(PEs) directly connected, Φ is the total number of PEs consisting the general nonshared memory computation model, and N is the number of data elements that represents the permutation. This bound is useful in case that, N≫Φ (restricted parallelisim) when the number of the data items are much bigger than the total number of PEs, therefore each PE will compute a subpermutation of 「N/Φ〓 data items. We have proven that ε, (in addition to N and Φ) affect the complexity of the (dynamic) parallel permutation algorithm which has been shown that it is not completely parallelizable on any ε-parallel computational model.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 1988, 号 19(1987-ARC-070), p. 1-7, 発行日 1988-03-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会