Fugu-MT 論文翻訳(概要): EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding

論文の概要: EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding

arxiv url: http://arxiv.org/abs/2408.11341v1
Date: Wed, 21 Aug 2024 04:55:10 GMT
ステータス: 処理完了
システム内更新日: 2024-08-22 18:19:12.461763
Title: EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding
Title（参考訳）: EHL*:超高速ユークリッドパスフィニングのためのメモリ予算インデックス化
Authors: Jinchun Du, Bojie Shen, Muhammad Aamir Cheema,
Abstract要約: EHL(Euclidean Hub Labeling)は、超高速なクエリパフォーマンスを提供する。 EHLはメモリオーバーヘッドが大幅に増加し、大規模なマップに最大数十ギガバイトのストレージが必要になる。 EHL*と呼ばれる改良版を導入し、これらの制限を克服した。
参考スコア（独自算出の注目度）: 9.722055526529926
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The Euclidean Shortest Path Problem (ESPP), which involves finding the shortest path in a Euclidean plane with polygonal obstacles, is a classic problem with numerous real-world applications. The current state-of-the-art solution, Euclidean Hub Labeling (EHL), offers ultra-fast query performance, outperforming existing techniques by 1-2 orders of magnitude in runtime efficiency. However, this performance comes at the cost of significant memory overhead, requiring up to tens of gigabytes of storage on large maps, which can limit its applicability in memory-constrained environments like mobile phones or smaller devices. Additionally, EHL's memory usage can only be determined after index construction, and while it provides a memory-runtime tradeoff, it does not fully optimize memory utilization. In this work, we introduce an improved version of EHL, called EHL*, which overcomes these limitations. A key contribution of EHL* is its ability to create an index that adheres to a specified memory budget while optimizing query runtime performance. Moreover, EHL* can leverage preknown query distributions, a common scenario in many real-world applications to further enhance runtime efficiency. Our results show that EHL* can reduce memory usage by up to 10-20 times without much impact on query runtime performance compared to EHL, making it a highly effective solution for optimal pathfinding in memory-constrained environments.
Abstract（参考訳）: ユークリッド短経路問題(Euclidean Shortest Path Problem、ESPP)は、多角形障害物を持つユークリッド平面の最も短い経路を見つけることを含む、多くの実世界の応用において古典的な問題である。現在の最先端ソリューションであるEuclidean Hub Labeling (EHL)は、超高速なクエリパフォーマンスを提供し、実行効率を1～2桁向上させる。しかし、このパフォーマンスはメモリオーバーヘッドの大きなコストを伴い、大規模なマップ上では最大数十ギガバイトのストレージを必要とするため、携帯電話や小型デバイスのようなメモリ制限のある環境での適用性が制限される可能性がある。さらに、EHLのメモリ使用量はインデックス構築後にのみ決定でき、メモリ実行時のトレードオフを提供するが、メモリ使用率を完全に最適化するものではない。本研究では,これらの制限を克服するEHL*と呼ばれる改良版を導入する。 EHL*の重要なコントリビューションは、クエリランタイムのパフォーマンスを最適化しながら、指定されたメモリ予算に準拠したインデックスを作成する機能である。さらに、EHL*は、多くの実世界のアプリケーションで一般的なシナリオである、既知のクエリ分散を活用して、ランタイム効率をさらに高めることができる。その結果,ETL*はクエリ実行時の性能に大きな影響を与えることなく,最大10～20倍のメモリ使用量を削減できることがわかった。

関連論文リスト

ProMoE: Fast MoE-based LLM Serving using Proactive Caching [2.041412657843408]
Mixture-of-Experts (MoE)モデルは、計算中にモデルのパラメータのサブセットだけを活性化することでこの問題を軽減する。本稿では,中間モデルを用いた新しいプロアクティブキャッシングシステムProMoEを提案する。評価の結果,ProMoEはプリフィルおよびデコード段階で平均2.13倍,2.84倍のスピードアップを達成した。
論文参考訳（メタデータ） (2024-10-29T15:31:27Z)
vTensor: Flexible Virtual Tensor Management for Efficient LLM Serving [53.972175896814505]
大規模言語モデル(LLM)は様々なドメインで広く使われ、数百万の日次要求を処理する。大規模言語モデル(LLM)は様々なドメインで広く使われ、数百万の日次要求を処理する。
論文参考訳（メタデータ） (2024-07-22T14:37:58Z)
Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers [58.5711048151424]
SPARSEK Attention(SPARSEK Attention)は、計算およびメモリ障害を克服するために設計された、新しいスパースアテンション機構である。提案手法では,各クエリに対して一定数のKVペアを選択するために,スコアリングネットワークと差別化可能なトップkマスク演算子であるSPARSEKを統合する。実験結果から,SPARSEK注意は従来のスパースアテンション法よりも優れていた。
論文参考訳（メタデータ） (2024-06-24T15:55:59Z)
LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
経路計画はロボット工学と自律航法における基本的な科学的問題である。 A*やその変種のような伝統的なアルゴリズムは、パスの妥当性を保証することができるが、状態空間が大きくなるにつれて、計算とメモリの非効率が著しく低下する。本稿では, A* の正確なパスフィニング能力と LLM のグローバルな推論能力とを相乗的に組み合わせた LLM ベースの経路計画法を提案する。このハイブリッドアプローチは、特に大規模シナリオにおいて、パス妥当性の完全性を維持しながら、時間と空間の複雑さの観点からパスフィニング効率を向上させることを目的としている。
論文参考訳（メタデータ） (2024-06-20T01:24:30Z)
S3D: A Simple and Cost-Effective Self-Speculative Decoding Scheme for Low-Memory GPUs [7.816840847892339]
投機的復号法(SD)は、LLM推論で実現可能な相当な高速化のために、かなりの量の研究の注目を集めている。本研究では,Skippy Simultaneous Speculative Decoding (S3D)を提案する。提案手法は,最小限のアーキテクチャ変更とデータトレーニングを必要としながら,最高のパフォーマンス・メモリ比の1つを達成した。
論文参考訳（メタデータ） (2024-05-30T17:54:35Z)
JORA: JAX Tensor-Parallel LoRA Library for Retrieval Augmented Fine-Tuning [16.86356520836045]
本稿では,Llama-2モデルのPEFT互換微調整のための新しいフレームワークについて紹介する。我々のフレームワークは、JAXのジャスト・イン・タイム(JIT)コンパイルと、効率的なリソース管理のためにテンソルシャーディングを独自に利用しています。実験では,Hugging Face/DeepSpeed実装を4GPUで実装するのに対して,GPUあたりのVRAMは半分以下であるのに対して,ランタイムでは12倍以上の改善が見られた。
論文参考訳（メタデータ） (2024-03-17T23:02:04Z)
Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuning [67.44661423463927]
本稿では,ZOをパラメータの慎重に選択したサブセットにのみ適用するメモリ効率のゼロ階最適化手法であるSparse MeZOを紹介する。その結果,Sparse-MeZO はオーバーヘッドを伴わずに,MeZO 上での性能と収束速度を安定的に向上することを示した。
論文参考訳（メタデータ） (2024-02-24T07:22:04Z)
Pre-gated MoE: An Algorithm-System Co-Design for Fast and Scalable Mixture-of-Expert Inference [23.207326766883405]
Mixture-of-Experts (MoE)は、計算要求を比例的にスケールアップすることなく、モデルサイズをスケールすることができる。プレゲートMOEは、スパース専門家活性化の動的性質を緩和する新しいプレゲート機能を用いている。我々は、Pre-gated MoEが、同じレベルのモデル品質を維持しながら、パフォーマンスを改善し、GPUメモリ消費を減らすことを実証した。
論文参考訳（メタデータ） (2023-08-23T11:25:37Z)
Energy-efficient Task Adaptation for NLP Edge Inference Leveraging Heterogeneous Memory Architectures [68.91874045918112]
Adapter-ALBERTは、様々なタスクにわたる最大データ再利用のための効率的なモデル最適化である。検証されたNLPエッジアクセラレータ上でシミュレーションを行うことにより、モデルを不均一なオンチップメモリアーキテクチャにマッピングする利点を実証する。
論文参考訳（メタデータ） (2023-03-25T14:40:59Z)
Enhanced Multi-Objective A* with Partial Expansion [22.45142249108214]
グラフ上に現れる多目的短経路問題(MO-SPP)は、複数の目的を最適化しながら経路の集合を決定する。この問題に対処するため,複数のMOA*アルゴリズムが最近開発された。この作業は,MOA*の高メモリ消費を,実行時にほとんど増加せずに削減することを目的としている。
論文参考訳（メタデータ） (2022-12-06T05:48:11Z)
NumS: Scalable Array Programming for the Cloud [82.827921577004]
タスクベース分散システム上でNumPyのような表現を最適化する配列プログラミングライブラリであるNumSを提案する。これはLoad Simulated Hierarchical Scheduling (LSHS)と呼ばれる新しいスケジューラによって実現される。 LSHSは、ネットワーク負荷を2倍減らし、メモリを4倍減らし、ロジスティック回帰問題において実行時間を10倍減らし、Rayの性能を向上させる。
論文参考訳（メタデータ） (2022-06-28T20:13:40Z)

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

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