マルチコア上のk最短単純経路アルゴリズムの実験的比較【JST・京大機械翻訳】

Ajwani Deepak; Duriakova Erika; Hurley Neil; Meyer Ulrich; Schickedanz Alexander

文献

J-GLOBAL ID：202002281732118930 整理番号：20A1504407

マルチコア上のk最短単純経路アルゴリズムの実験的比較【JST・京大機械翻訳】

An Empirical Comparison of k-Shortest Simple Path Algorithms on Multicores

出版者サイト複写サービスで全文入手
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A1504407&from=J-GLOBAL&jstjournalNo=D0698C") }}

著者 (5件)： , , , ,
資料名：
号： ICPP 2018 ページ： 1-12 発行年： 2018年
JST資料番号： D0698C 資料種別：会議録 (C)
記事区分：原著論文発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

ループの少ないk最短経路(KSP)問題を考察した。この問題は少なくとも過去20年間連続設定で研究されているが,良好な並列実装は知られていない。本論文では,(i)様々なKSPアルゴリズムと発見的最適化の最初の系統的経験的比較,(ii)これらの逐次アルゴリズムの様々な並列実装を慎重に操作し,(iii)異なるグラフクラスに対する最良のアルゴリズムと並列化戦略を決定するために,グラフクラスとマルチコアアーキテクチャの範囲におけるこれらの並列実装の広範囲な研究を行う。最良の無向KSPアルゴリズムO(k(m+nlogn))の最悪ケース複雑性は,ポピュラーで,かなり単純な有向KSPアルゴリズムO(kn(m+nlogn))のものよりかなり良いが,2つのアルゴリズムは,小直径グラフに関するそれらの経験的性能に関してかなり競争力があることがわかった。さらに,少数の簡単な最適化が,これらのKSPアルゴリズム間のギャップをもっと多く埋めるのに役立つことを示した。しかしながら,中程度から大きな直径グラフでは,無向KSPアルゴリズムは,逐次および並列設定の両方において,有向アルゴリズムよりもかなり高速である。並列化戦略に関して,並列Δステッピングアルゴリズムによって最短経路サブルーチンを単純に置き換えることは,ランダムグラフに関する多くのKSPアルゴリズムのための良いスピードアップを提供することができる。対照的に,歪度分布を持つグラフに対して,異なる偏差を並列化し,次に残りのスレッドとの偏差の中で最短経路計算を並列化するより複雑な戦略は,より良い性能を提供した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

, ,
, , , 【Automatic Indexing@JST】

著者キーワード (4件)： , , ,

グラフ理論基礎 , 数値計算 , 計算機網 , 計算理論

, , ,

前のページに戻る