PALMA: ARM 기반 임베디드 시스템을 위한 경량 트로피컬 대수 라이브러리

PALMA: A Lightweight Tropical Algebra Library for ARM-Based Embedded Systems

트로피컬 대수, 여기에는 최대-플러스, 최소-플러스 및 관련 이드empotent 반환환과 같은 개념이 포함되며, 이는 많은 최적화 문제를 고전 대수에서 비선형적인 문제를 선형적으로 처리할 수 있는 통합적인 프레임워크를 제공합니다. 이러한 특성 때문에 트로피컬 방법은 최단 경로, 스케줄링, 처리량 분석 및 이산 이벤트 시스템에 특히 적합합니다. 이론적으로 성숙하고 실용적으로 중요한 반면, 기존의 트로피컬 대수 구현은 주로 데스크톱 또는 서버 환경을 대상으로 하며, 자원 제약이 있는 임베디드 플랫폼에서는 활용하기 어렵습니다. 본 논문에서는 PALMA (Parallel Algebra Library for Max-plus Applications)라는 경량의, 의존성이 없는 C 라이브러리를 소개합니다. PALMA는 트로피컬 선형 대수를 ARM 기반 임베디드 시스템에 적용할 수 있도록 설계되었습니다. PALMA는 SIMD 가속을 활용한 제네릭 반환환 추상화를 구현하여, 최단 경로, 병목 경로, 도달 가능성, 스케줄링 및 처리량 분석을 지원하는 단일 컴퓨팅 프레임워크를 제공합니다. 이 라이브러리는 다섯 가지 트로피컬 반환환, 밀집 및 희소 (CSR) 표현, 트로피컬 클로저 및 최대 사이클 평균 계산을 통한 스펙트럴 분석을 지원합니다. Raspberry Pi 4에서 PALMA를 평가한 결과, 최대 2,274 MOPS의 성능을 보였으며, 단일 소스 최단 경로 문제에서 기존 Bellman-Ford 알고리즘보다 최대 11.9배 빠른 속도를 달성했습니다. 또한, 실시간 제어 워크로드에 대해 10 마이크로초 미만의 스케줄링 시간을 보여주었습니다. UAV 제어, IoT 라우팅 및 제조 시스템에 대한 사례 연구를 통해 트로피컬 대수가 임베디드 하드웨어에서 효율적이고 예측 가능하며 통합적인 최적화를 가능하게 한다는 것을 보여줍니다. PALMA는 MIT 라이선스 하에 오픈 소스 소프트웨어로 공개되었습니다.

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.