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倍のメモリ使用量を削減できることがわかった。

関連論文リスト

Sparse Gradient Compression for Fine-Tuning Large Language Models [58.44973963468691]
ダウンストリームタスクのための微調整された大型言語モデル(LLM)は、広く利用されていることと、オープンソースモデルの利用が増加しているために、ますます重要になっている。微調整に伴う高メモリコストは、特にモデルのサイズが大きくなるにつれて大きな課題である。これらの制約に対処するためにスパース圧縮勾配(SGC)を提案する。
論文参考訳（メタデータ） (2025-02-01T04:18:28Z)
XKV: Personalized KV Cache Memory Reduction for Long-Context LLM Inference [9.65524177141491]
大規模言語モデル(LLM)推論は出力トークンを1つずつ生成し、多くの冗長な計算に繋がる。 KV-Cacheフレームワークは時間と空間の複雑さを妥協する。既存の研究では、推論精度に重要でないキャッシュデータの一部を削除することで、メモリ消費を減らすことができる。各レイヤのキャッシュサイズをパーソナライズしてカスタマイズすることで,メモリの大幅な削減が期待できることを示す。
論文参考訳（メタデータ） (2024-12-08T11:32:08Z)
ProMoE: Fast MoE-based LLM Serving using Proactive Caching [4.4026892123375605]
本稿では,プロアクティブキャッシュシステムProMoEについて紹介する。 ProMoEはプリフィルおよびデコード段階で平均2.20倍(最大3.21倍)と2.07倍(最大5.02倍)のスピードアップを達成する。
論文参考訳（メタデータ） (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)
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)
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)

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

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