論文の概要: PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU

• arxiv url: http://arxiv.org/abs/2401.06089v1
• Date: Thu, 11 Jan 2024 18:08:56 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-12 13:35:44.308089
• Title: PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU
• Title（参考訳）: PANDORA:GPU上の単一リンククラスタリングのための並列デンドログラム構築アルゴリズム
• Authors: Piyush Sao, Andrey Prokopenko, Damien Lebrun-Grandi\'e
• Abstract要約: Pandoraは、hdbscanを含む単一リンク階層クラスタリングのためのデンドログラムを効率的に構築するための新しい並列アルゴリズムである。 Pandoraは、最初のデンドログラムの構築のためにツリーを単純化し、完全なデンドログラムを段階的に再構築するユニークなツリー収縮メソッドを通じて、課題に対処する。
• 参考スコア（独自算出の注目度）: 0.11172147007388976
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents \pandora, a novel parallel algorithm for efficiently constructing dendrograms for single-linkage hierarchical clustering, including \hdbscan. Traditional dendrogram construction methods from a minimum spanning tree (MST), such as agglomerative or divisive techniques, often fail to efficiently parallelize, especially with skewed dendrograms common in real-world data. \pandora addresses these challenges through a unique recursive tree contraction method, which simplifies the tree for initial dendrogram construction and then progressively reconstructs the complete dendrogram. This process makes \pandora asymptotically work-optimal, independent of dendrogram skewness. All steps in \pandora are fully parallel and suitable for massively threaded accelerators such as GPUs. Our implementation is written in Kokkos, providing support for both CPUs and multi-vendor GPUs (e.g., Nvidia, AMD). The multithreaded version of \pandora is 2.2$\times$ faster than the current best-multithreaded implementation, while the GPU \pandora implementation achieved 6-20$\times$ on \amdgpu and 10-37$\times$ on \nvidiagpu speed-up over multithreaded \pandora. These advancements lead to up to a 6-fold speedup for \hdbscan on GPUs over the current best, which only offload MST construction to GPUs and perform multithreaded dendrogram construction.
• Abstract（参考訳）: 本稿では,hdbscanを含む単一リンク階層クラスタリングのためのデンドログラムを効率的に構築する並列アルゴリズムである \pandora を提案する。 最小分散木(MST)からの伝統的なデンドログラム構築法は、特に実世界のデータに共通する歪んだデンドログラムにおいて、凝集法や分割法のような効率よく並列化できないことが多い。 \pandoraは、最初のデンドログラム構築のためにツリーを単純化し、それから徐々に完全なデンドログラムを再構築するユニークな再帰的木収縮法によってこれらの課題に対処する。 このプロセスは、デンドログラムの歪みから独立して、漸近的に作業最適化を行う。 \pandoraのすべてのステップは完全に並列であり、GPUのような大規模スレッドのアクセラレータに適している。 実装はKokkosで記述されており、CPUとマルチベンダGPU(Nvidia、AMDなど)の両方をサポートしています。 マルチスレッドバージョンの \pandora は現在のベストマルチスレッド実装よりも2.2$\times$ 速く、GPU \pandora の実装は \amdgpu 上で 6-20$\times$ と 10-37$\times$ を達成している。 これらの進歩は、GPU上での \hdbscan の6倍のスピードアップにつながり、これはGPUに MST の構築をオフロードし、マルチスレッドのdendrogram 構築を実行するだけである。

関連論文リスト

• Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks [2.264332709661011]
  ell_1,infty$ノルムの時間複雑性は、$mathbbRntimes m$の行列に対して$mathcalObig(n m big)$のみであることを示す。 実験により、我々の予測は、実際の最速のユークリッドアルゴリズムの2倍高速であることが示されている。
  論文  参考訳（メタデータ） (2024-05-03T13:21:49Z)
• Enabling Multi-threading in Heterogeneous Quantum-Classical Programming Models [53.937052213390736]
  量子カーネルの並列実行を可能にするために,C++ベースの並列コンストラクトを導入する。 予備的な性能の結果は、カーネル毎に12スレッドのベルカーネルを2回実行し、カーネルを次々に実行する並列性能が向上したことを示している。
  論文  参考訳（メタデータ） (2023-01-27T06:48:37Z)
• Accelerating Barnes-Hut t-SNE Algorithm by Efficient Parallelization on Multi-Core CPUs [59.18990342943095]
  t-SNEは高次元データを視覚化するための最も一般的な埋め込み技術の一つである。 BH t-SNEアルゴリズムは既存のCPU実装では非効率である。 Acc-t-SNEはScikit-learnよりも最大261倍、4倍高速で、daal4pyの最先端のBH t-SNE実装である。
  論文  参考訳（メタデータ） (2022-12-22T06:38:40Z)
• PLSSVM: A (multi-)GPGPU-accelerated Least Squares Support Vector Machine [68.8204255655161]
  Support Vector Machines (SVM) は機械学習で広く使われている。 しかし、現代的で最適化された実装でさえ、最先端ハードウェア上の大きな非自明な高密度データセットにはうまくスケールしない。 PLSSVMはLVMのドロップイン代替として使用できる。
  論文  参考訳（メタデータ） (2022-02-25T13:24:23Z)
• Sequence Parallelism: Making 4D Parallelism Possible [10.08109995764072]
  我々は、入力シーケンスの長さ制限を破り、GPU上で長いシーケンスでトレーニングするのに役立つシーケンス並列性を提案する。 リングオールリデューサにインスパイアされたリングスタイル通信と自己アテンション計算を統合し,リング自己アテンション(RSA)を提案する。
  論文  参考訳（メタデータ） (2021-05-26T13:40:58Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  我々は,超効率的なサイストリックアレイベースの多用途ハードウェアアクセラレータである textitVersaGNN を提案する。 textitVersaGNNは平均3712$times$ speedup with 1301.25$times$ energy reduction on CPU、35.4$times$ speedup with 17.66$times$ energy reduction on GPUを達成している。
  論文  参考訳（メタデータ） (2021-05-04T04:10:48Z)
• Systolic Computing on GPUs for Productive Performance [2.8064596842326575]
  我々は,GPU上で動作する高性能なシストリックアレイを生産的に構築する言語とコンパイラを提案する。 プログラマは、データフローのプロジェクションを線形シストリック配列に指定し、プロジェクションの詳細な実装はコンパイラに任せる。 コンパイラは指定されたプロジェクションを実装し、リニアシストリックアレイをGPUのSIMD実行ユニットとベクトルレジスタにマッピングする。
  論文  参考訳（メタデータ） (2020-10-29T18:49:54Z)
• GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensembles [0.8057006406834467]
  本稿では,グラフィック処理ユニット上での大規模並列計算に適したツリーサップアルゴリズムを提案する。 我々は,最先端のマルチコアCPU実装を用いて,SHAP値の最大19倍,SHAP値の最大340倍の高速化を実現する。
  論文  参考訳（メタデータ） (2020-10-27T00:55:07Z)
• Hybrid Models for Learning to Branch [81.93868699246214]
  我々はCPUマシン上で効率的な分岐を行うための新しいハイブリッドアーキテクチャを提案する。 提案アーキテクチャは,GNNの表現力と分岐処理のための計算コストの低い多層パーセプトロン(MLP)を組み合わせる。
  論文  参考訳（メタデータ） (2020-06-26T21:03:45Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。