論文の概要: Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths

• arxiv url: http://arxiv.org/abs/2307.16652v1
• Date: Mon, 31 Jul 2023 13:32:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-01 14:33:30.270673
• Title: Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths
• Title（参考訳）: 分割局所深さに対するシーケンシャルおよび共有メモリ並列アルゴリズム
• Authors: Aditya Devarakonda, Grey Ballard
• Abstract要約: PaLDは相対距離に基づいて対関係の強さを同定する手法である。 性能最適化戦略を導入し、ベースラインのシーケンシャルな実装に対して、最大29ドル以上のシーケンシャルなスピードアップを実現した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we design, analyze, and optimize sequential and shared-memory parallel algorithms for partitioned local depths (PaLD). Given a set of data points and pairwise distances, PaLD is a method for identifying strength of pairwise relationships based on relative distances, enabling the identification of strong ties within dense and sparse communities even if their sizes and within-community absolute distances vary greatly. We design two algorithmic variants that perform community structure analysis through triplet comparisons of pairwise distances. We present theoretical analyses of computation and communication costs and prove that the sequential algorithms are communication optimal, up to constant factors. We introduce performance optimization strategies that yield sequential speedups of up to $29\times$ over a baseline sequential implementation and parallel speedups of up to $19.4\times$ over optimized sequential implementations using up to $32$ threads on an Intel multicore CPU.
• Abstract（参考訳）: 本研究では,分割局所深度(PaLD)に対する逐次的および共有メモリ並列アルゴリズムの設計,解析,最適化を行う。 一組のデータポイントとペア距離が与えられた場合、PaLDは相対距離に基づいてペア関係の強さを識別する方法であり、そのサイズとコミュニティ内絶対距離が大きく変化しても、密度と疎いコミュニティ内の強い結びつきを識別することができる。 ペアワイズ距離の三重項比較によってコミュニティ構造解析を行う2つのアルゴリズム変種を設計した。 本稿では,計算コストと通信コストの理論的解析を行い,逐次アルゴリズムが通信の最適であることを示す。 私たちは、ベースラインのシーケンシャル実装よりも最大29\times$、intelのマルチコアcpu上で最大32ドルのスレッドを使用して最適化されたシーケンシャル実装よりも最大19.4\times$の並列スピードアップをもたらすパフォーマンス最適化戦略を導入します。

関連論文リスト

• Parallelization of the K-Means Algorithm with Applications to Big Data Clustering [0.23020018305241333]
  LLoydのアルゴリズムを使ったK-Meansクラスタリングは、与えられたデータセットをKの異なるクラスタに分割する反復的なアプローチである。 このプロジェクトでは2つの異なるアプローチを比較します。
  論文  参考訳（メタデータ） (2024-05-20T14:18:36Z)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。 具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。 これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
  論文  参考訳（メタデータ） (2024-03-06T15:06:11Z)
• Performance Embeddings: A Similarity-based Approach to Automatic Performance Optimization [71.69092462147292]
  パフォーマンス埋め込みは、アプリケーション間でパフォーマンスチューニングの知識伝達を可能にする。 本研究では, 深層ニューラルネットワーク, 密度およびスパース線形代数合成, および数値風速予測ステンシルのケーススタディにおいて, この伝達チューニング手法を実証する。
  論文  参考訳（メタデータ） (2023-03-14T15:51:35Z)
• Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
  本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。 我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。 また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
  論文  参考訳（メタデータ） (2022-06-27T10:54:24Z)
• Rank-based Non-dominated Sorting [0.0]
  我々は、高額な支配比較を避けるために、ソート安定性と順序情報を利用した非支配的なソート手法であるランクソートを導入する。 2つのアルゴリズム的変種が提案されている: 1つはRandOrdinal (RO) で、支配性を決定するために順序付き階数比較(英語版)(ordinal rank comparisons)を用いており、O(N) 空間を必要とする。 NSGA2アルゴリズムと合成ベンチマークを用いた実験シミュレーションにおいて,提案手法の有効性を他の手法と比較した。
  論文  参考訳（メタデータ） (2022-03-25T13:59:42Z)
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain [6.824747267214373]
  本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。 従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。 我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
  論文  参考訳（メタデータ） (2021-06-08T23:13:27Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• Parallel Training of Deep Networks with Local Updates [84.30918922367442]
  ローカル並列性(Local Parallelism)は、グローバルバックプロパゲーションを切り捨てられたレイヤワイズバックプロパゲーションに置き換えることで、ディープネットワーク内の個々のレイヤのトレーニングを並列化するフレームワークである。 我々は、様々なアーキテクチャセットにわたるビジョンと言語領域の両方で結果を示し、局所的並列性は特に高コンピュートなシステムにおいて有効であることを見出した。
  論文  参考訳（メタデータ） (2020-12-07T16:38:45Z)
• Minimal Filtering Algorithms for Convolutional Neural Networks [82.24592140096622]
  我々は,M=3,5,7,9,11の基本的なフィルタリング操作を実装するための完全並列ハードウェア指向アルゴリズムを開発した。 各ケースにおける提案アルゴリズムの完全な並列ハードウェア実装は、組込み乗算器の数を約30%削減する。
  論文  参考訳（メタデータ） (2020-04-12T13:18:25Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。 本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。 提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
  論文  参考訳（メタデータ） (2020-02-10T10:11:31Z)

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

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