轻量级库让嵌入式设备也能高效运行热带代数优化计算
PALMA: A Lightweight Tropical Algebra Library for ARM-Based Embedded Systems
- 基于ARM架构设计，支持多种热带半环的通用计算框架
- 在树莓派4上实现2274 MOPS峰值性能，调度求解低于10微秒
- 适合无人机、物联网和制造系统等实时嵌入式优化场景
热带代数（如max-plus、min-plus及相关的幂等半环）为众多非线性优化问题提供了统一框架，使其在经典代数下呈线性特性。该性质使其特别适用于最短路径、调度、吞吐量分析与离散事件系统。尽管理论成熟且应用广泛，现有实现多面向桌面或服务器环境，难以在资源受限的嵌入式平台使用。本文提出PALMA（用于最大值路径应用的并行代数库），一个无依赖、轻量级的C语言库，将热带线性代数引入基于ARM的嵌入式系统。PALMA采用通用半环抽象与SIMD加速内核，支持单一流程实现最短路径、瓶颈路径、可达性、调度与吞吐量分析。支持五种热带半环、稠密与稀疏（CSR）表示、热带闭包及通过最大环均值计算的谱分析。在Raspberry Pi 4上的评估显示，峰值性能达2,274 MOPS，单源最短路径相比传统Bellman-Ford速度提升最高达11.9倍，实时控制任务的调度求解时间低于10微秒。无人机控制、物联网路由与制造系统的案例研究证明，热带代数可在嵌入式硬件上实现高效、可预测且统一的优化。PALMA已作为MIT许可的开源软件发布。
原文摘要 · Abstract (English)
Tropical algebra, including max-plus, min-plus, and related idempotent semirings, provides a unifying framework in which many optimization problems that are nonlinear in classical algebra become linear. This property makes tropical methods particularly well suited for shortest paths, scheduling, throughput analysis, and discrete event systems. Despite their theoretical maturity and practical relevance, existing tropical algebra implementations primarily target desktop or server environments and remain largely inaccessible on resource-constrained embedded platforms, where such optimization problems are most acute. We present PALMA (Parallel Algebra Library for Max-plus Applications), a lightweight, dependency-free C library that brings tropical linear algebra to ARM-based embedded systems. PALMA implements a generic semiring abstraction with SIMD-accelerated kernels, enabling a single computational framework to support shortest paths, bottleneck paths, reachability, scheduling, and throughput analysis. The library supports five tropical semirings, dense and sparse (CSR) representations, tropical closure, and spectral analysis via maximum cycle mean computation. We evaluate PALMA on a Raspberry Pi 4 and demonstrate peak performance of 2,274 MOPS, speedups of up to 11.9 times over classical Bellman-Ford for single-source shortest paths, and sub-10 microsecond scheduling solves for real-time control workloads. Case studies in UAV control, IoT routing, and manufacturing systems show that tropical algebra enables efficient, predictable, and unified optimization directly on embedded hardware. PALMA is released as open-source software under the MIT license.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。