Revisiting Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolver from Algorithmic Perspective
Ruiyi Zhan, Dajun Huang, Lu Shi, Shaoshuai Zhang
AI 速读 基于摘要
作者提出仅用每个合并节点的首末两行边界行构成递推来携带分治状态,将持久内存从二次降为线性,并在 CPU 与 GPU 上按去膨胀后的有效秩做细粒度调度。
cs.DC · math.NA
查看原文摘要
Divide-and-conquer (D&C) is the natural parallel strategy for symmetric tridiagonal eigenvalue decomposition, yet eigenvalue-only solvers fall back to serial QR algorithm because the quadratic transform state each merge carries exhausts memory at scale. In this paper, we demonstrate that each merge stage in D&C needs only two boundary rows, the first and last rows of a node's eigenvector block, and these close into a recurrence whose parent rows follow from its children's and local merge data alone, so the state is carried up the tree with nothing replayed and persistent memory drops from quadratic to linear. Because this state keeps no replay workspace, adapting the schedule to each merge's post-deflation active rank is a scheduling choice, so both CPU and GPU spend finer-grained parallelism only where substantial secular work survives. We evaluate optimized CPU and GPU implementations, with complexity and correctness analysis, against QR, bisection, and D&C routines in standard libraries.
Confidential virtual machines (CVMs) based on trusted execution environments (TEEs) enable new privacy-preserving solutions. Yet, they leave side-channel leakage outside their threat model, shifting the responsibility of mitigating such attacks to developers. However, mitigations are either not generic or too slow for practical use, and developers currently lack a systematic, efficient way to measure and compare leakage across real-world deployments. In this paper, we present SNPeek, an open-source toolkit that offers configurable side-channel tracing primitives on production AMD SEV-SNP hardware and couples them with statistical and machine-learning-based analysis pipelines for automated leakage estimation. We apply SNPeek to three representative workloads that are deployed on CVMs to enhance user privacy-private information retrieval, private heavy hitters, and Wasm user-defined functions-and uncover previously unnoticed leaks, including a covert channel that exfiltrates data at 497 kbit/s. The results show that SNPeek pinpoints vulnerabilities and guides low-overhead mitigations based on oblivious memory and differential privacy, giving practitioners a practical path to deploy CVMs with meaningful confidentiality guarantees.