原子のないバイナリーフォーキングモデルのための低深さ並列アルゴリズム【JST・京大機械翻訳】

Ahmad Zafar; Chowdhury Rezaul; Das Rathish; Ganapathi Pramod; Gregory Aaron; Javanmard Mohammad Mahdi

プレプリント

J-GLOBAL ID：202202205928375850 整理番号：22P0186210

原子のないバイナリーフォーキングモデルのための低深さ並列アルゴリズム【JST・京大機械翻訳】

Low-Depth Parallel Algorithms for the Binary-Forking Model without Atomics

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (6件)： , , , , ,
資料名：
発行年： 2020年08月30日プレプリントサーバーでの情報更新日： 2020年09月02日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

バイナリフォーキングモデルは並列計算モデルであり,Blellochらによって形式的に定義され,そこではスレッドが同時の子供スレッドを再帰的に,そして非同期的にフォークできる。モデルは,nタスクまたはスレッドをスパウンまたは同期させるためのΘ(logn)のコストを発生した。バイナリフォーキングモデルは,マルチコア共有メモリマシン上で,現代のマルチスレッドプログラミング言語を用いて実行される並列アルゴリズムの性能を現実的に捉える。対照的に,広く研究された理論的PRAMモデルは,産卵および同期スレッドのコストを考慮しない,そして結果として,PRAMモデルにおける最適性能限界を達成するアルゴリズムは,バイナリフォーキングモデルにおいて最適でないかもしれない。しばしば,アルゴリズムはバイナリーフォーキングモデルの最適性能限界を達成するために再設計する必要がある,そして,非一定の同期コストがタスクを困難にする。バイナリフォーキングモデルは,いくつかの同期オーバヘッドを低減するための原子{emテストアンドセット}(TS)命令の使用を可能にするが,そのような命令のアベイラビリティはハードウェアに関する強い要求を課し,それらを用いてアルゴリズムの携帯性を制限する可能性がある。本論文では,ランタイムシステムによって実装される接合操作の内部で,著者らのアルゴリズムにおけるロックと原子命令の使用を回避する。本論文では,3つの基本的問題,即ち,Strassen(およびStrassen様)行列乗算(MM),比較ベースソーティング,および高速Fourier変換(FFT)に対して,原子のないバイナリフォーキングモデルにおいて,効率的な並列アルゴリズムを設計したものである。”Strassen(およびStrassen-like)行列乗算(MM),比較ベースソーティング,および高速Fourier変換(FFT)。すべての結果は,原子のある場合と無い場合の両方で,バイナリーフォーキングモデルにおける対応する問題に対する既知の結果を改善する。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

ディジタル計算機方式一般

, ,

前のページに戻る