緩和スケジューラの下での並列増分アルゴリズムに対する効率保証【JST・京大機械翻訳】

Alistarh Dan; Koval Nikita; Nadiradze Giorgi

プレプリント

J-GLOBAL ID：202202204922953910 整理番号：22P0125238

緩和スケジューラの下での並列増分アルゴリズムに対する効率保証【JST・京大機械翻訳】

Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers

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

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

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

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

グラフ処理および計算幾何学におけるいくつかの古典的問題を,増分アルゴリズムによって解決し,そしてそれは,計算を,共有状態に作用する一連の小タスクに分割し,そしてそれは,次第に更新した。そのようなアルゴリズムの逐次変形は,通常,タスクを行うべきである固定(時々ランダム)順序を指定するが,そのようなアルゴリズムを並列化する標準手法は,この制約を緩和し,アウトオブオーダ並列実行を可能にする。これは,Dijkstraの単一ソース最短経路アルゴリズム(SSSP)の並列実装と並列Delaunayメッシュ三角形分割の場合である。多くのソフトウェアフレームワークは,この方法でインクリメンタル計算を並列化するが,この緩和秩序アプローチが任意の複雑性保証を提供できるかどうかはまだ十分に理解されていない。本論文では,この問題に対処し,緩和スケジューラを介して並列化したとき,一連の増分アルゴリズムによって提供される効率保証を解析した。Delaunayメッシュ三角形分割および挿入によるソーティングのようなアルゴリズムに対して,最大優先度反転に関してkの最大緩和因子を有するスケジューラは,O(log(n)ポリ(k))の最大量の廃棄仕事を導入し,そこでは,nは実行すべきタスクの数である。SSSPでは,追加作業はO(poly(k)d_max/w_min)であり,d_maxは2つのノード間の最大距離であり,w_minは最小である。n≫kの実用的な設定では,緩和のオーバヘッドが緩和スケジューラの改善されたスケーラビリティによって勝ることを示唆する。負側では,比較的良性の緩和スケジューラに対してさえも,スケジューラ緩和により,あるアルゴリズムが本質的に非自明な量の廃棄仕事を生じることを示す下限を提供する。【JST・京大機械翻訳】

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

オペレーティングシステム , ディジタル計算機方式一般 , 専用演算制御装置

, , ,

前のページに戻る