概要 - 時砂並べ：新しい並列ソートアルゴリズムとその実装
タイトル
時砂並べ：新しい並列ソートアルゴリズムとその実装
時間
2025-07-22 08:08:29
著者
{"Daniel Bascones","Borja Morcillo"}
カテゴリ
{cs.AR,B.5.0}
リンク
http://arxiv.org/abs/2507.16326v1
PDF リンク
http://arxiv.org/pdf/2507.16326v1
概要
時沙漏並列ソートは、並列入力とシリアル出力で大規模データセットを効率的にソートするために設計された革新的な並列ソートアルゴリズムです。このアルゴリズムは、最初の要素の出力に対して log(n)の遅延を達成し、合計ソート時間は n + log(n)です。特に大規模データセットの迅速なソートが必要な量子LDPCデコードなどのアプリケーションに非常に有用です。 時沙漏並列ソートアルゴリズムは、比較器の木構造に基づいており、各ノードには2つの出力レジスタがあります。これにより、伝統的なソートアルゴリズムで発生する可能性のある「泡」効果を避けられます。これにより、アルゴリズムは入力サイズに対して恒常的な重い経路を維持し、非常に拡張可能な設計が実現されます。 このアルゴリズムはFPGAに実装され、量子LDPC符号化のためのBP-OSD（確率変数伝播 - 詳細統計デコーダ）実装に成功して統合されました。この実装は、誤り修正符号のリアルタイムデコードなどの実世界のアプリケーションにおけるアルゴリズムの能力を示しています。 時沙漏並列ソートアルゴリズムの主要な特徴は以下の通りです： - O(n)のハードウェア複雑度 - 最初の要素の出力に対するlog(n)の遅延 - 合計ソート時間はn + log(n) - 恒常的な重い経路を持つ拡張可能な設計 - 並列入力とシリアル出力での大規模データセットのソートに適しています 時沙漏並列ソートアルゴリズムは、並列ソートアルゴリズムにおいて重要な進歩を遂げており、大規模データセットの迅速なソートが必要なアプリケーションに対して非常に効率的かつ拡張可能なソリューションを提供しています。
推奨論文
FD4QC：金融詐欺検出のための古典的および量子ハイブリッド機械学習の適用 技術報告
ApproxGNN：近似計算のためのデザイン空間探索におけるパラメータ予測のための事前トレーニングGNN
各方向同性リメッシュおよび角度間最適化
2025年インタースピーチ音声アクセスプロジェクトチャレンジ
TyDi QA-WANA: 西アと北アフリカの言語における情報探索型質問応答のための基準
画像とテキストの連携強化のための学習可能なリトリーブと放射線報告書生成のための融合
MMBench-GUI: グラフィカルユーザインターフェースエージェントのための階層的多プラットフォーム評価フレームワーク
均一なデジットシリアルモジュラス算術を使用する高性能パイプラインNTTアクセラレータ
データシートからの自動HEMTモデル構築：多様な知能と事前知識なしの最適化を通じて
計算統計の難解性から生じるトレードオフ