スケーラブルな共有メモリハイパーグラフ分割【JST・京大機械翻訳】

Gottesbueren Lars; Heuer Tobias; Sanders Peter; Schlag Sebastian

プレプリント

J-GLOBAL ID：202202205625582054 整理番号：22P0202149

スケーラブルな共有メモリハイパーグラフ分割【JST・京大機械翻訳】

Scalable Shared-Memory Hypergraph Partitioning

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

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

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

ハイパーグラフ分割は,データ配置を最適化し,高性能コンピューティングアプリケーションにおける通信容量を最小化するための重要な前処理ステップである。絶えず増大する問題サイズに対処するために,その解品質が既存の逐次アルゴリズムと競合している高速並列分割アルゴリズムを開発することがますます重要になっている。この目的のために,著者らは,逐次,高品質分割システムによって使用される多くの技術の並列実装による最初の共有メモリマルチレベル超グラフ分割器であるMt-KaHyParを提示し,並列コミュニティ検出をガイダンスとして,並列再帰的バイ分割を作業-ストレッシング,スケーラブルラベル伝搬精密化アルゴリズム,および古典的FMアルゴリズムの最初の完全並列直接k-ウェイ定式化を用いて,並列の分割アルゴリズムを使用した。種々のアプリケーションドメインからのインスタンスの大規模ベンチマークセットで行った実験により,提案アプローチのスケーラビリティと有効性を実証した。64コアを用いて,51までの自己相対高速化と23.5の高調波平均高速化を観測した。解品質に関して,著者らは,分散超グラフ分割器Zoltanを,インスタンスの95%に優し,一方,また,2.1の因子であった。ちょうど4つのコアで,Mt-KaHyParは最速の逐次マルチレベル分割器PaToHよりもわずかに速く,一方,すべての事例の83%でより良い解を生成した。逐次高品質分割器KaHyParは,特に最大フローベース精密化を用いるとき,著者らの並列アプローチより良い解を見つける。しかし,これは,かなり長い実行時間のコストで来る。【JST・京大機械翻訳】

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

数値計算

前のページに戻る