其它计算机科学 · 2026年10月18日(周日)

分布式计算、博弈论、信息论等。

arXiv cs.GT

MMS Allocation for Chores with Item Disposals

说明带物品处置的家务分配中的最大最小份额(MMS)问题

简介该论文研究网络平台上集体任务的公平分配问题,任务有异质的成本,目标是在尽量少地留下未分配任务的同时,保证每位参与者都能获得其原始实例中的最大最小份额(MMS)。作者证明,对任意至少四名参与者的实例,至多 n-3 次任务处置即可满足要求,并改进了 Barman 等人(2025)的 2m/11+n 界,去除了对任务数 m 的依赖。对四名参与者的情形,作者给出紧界:一次处置总是足够。

Shinuo Ma, Xiaowei Wu

arXiv cs.DB · cs.DC

VS-Flash: Harnessing Vector Search with Computational Memory-Semantic Flash

说明VS-Flash:借助计算型内存语义闪存加速向量检索

简介本文针对检索增强生成系统中向量数据库数据量超出主机内存的问题,提出VS-Flash。它把闪存作为可按内存语义访问的大容量空间,并依据查询和负载特征动态选择执行引擎:大批量查询交由计算型内存语义闪存设备处理,小批量低延迟查询在主机CPU上执行,两条路径共享同一份驻留数据。在三个十亿级数据集上,相比原版Milvus,其大批量检索吞吐量平均提升36.8倍,最高提升57.4倍;混合负载下,小请求的p99延迟最多降低24.8倍。

Donguk Kim, Sangjun Pae, Daeyoung Lee 等

arXiv cs.GT · cs.DS

Strategy recovery for Mean-Payoff Games is as hard as solving them from scratch

说明均值支付博弈的策略恢复与从零求解一样困难

简介本文研究确定性、零和、回合制的均值支付博弈(MPG),即在有限加权有向图上,两名玩家通过构造无限路径并比较边权极限平均值进行博弈。论文给出一种从求解MPG到策略恢复问题的简单归约,表明在不知道各顶点值的情况下,策略恢复与直接求解同样困难。即使已知另一方的最优策略和全部顶点值,为一方找到最优策略仍然困难。

Dani Dorfman, Uri Zwick

arXiv cs.DC · cs.PF · q-bio.GN

panvram: GPU-resident random access to a human pangenome cohort

说明panvram:人类泛基因组队列的GPU常驻随机访问方法

简介该论文提出panvram,用于反复抽取人类泛基因组中短序列片段的场景。它将每个组装版本存为相对参考序列的压缩块档案,并把这些档案汇集到GPU显存中。在558个单倍型组装上,默认q4k表示占用16.642 GB持久池(含解码参考),紧凑表示为11.634 GB;两者都是批量API测量的吞吐结果,并非同一环境的重复试验。

Yakiv Shavidze

arXiv cs.DC

From Last-Layer to Cross-Layer: One-Shot Joint Classifier Reconstruction for Federated Learning

说明从最后一层到跨层:联邦学习的一次性联合分类器重建

简介本文针对联邦学习中非独立同分布数据导致的分类器偏差问题,发现全局模型中间层表示构建的分类器往往优于最后一层。作者提出FLARE方法,在训练后通过一次前向传播收集各层类别统计量,由服务器构建跨层联合岭回归分类器,并用自适应耦合系数调节层间相关性。实验覆盖11个数据集和8种模型架构,称其作为即插即用后处理方法可将准确率提升11.35%,且仅增加一轮通信。

Zhenyan Liu, Hua Zhang, Haoran Gao 等

arXiv cs.DC · cs.NI

Off-Tree Forwarding for Accelerating Broadcasts from Arbitrary Sources in Plumtree

说明Plumtree中用于加速任意源广播的树外转发机制

简介Plumtree是一种在gossip覆盖网络中嵌入生成树的广播协议,但树是按首次广播构建的,对其他节点(尤其是叶节点)发起的广播可能产生较长绕路。本文提出概率性渗出(probabilistic exuding):源点附近的节点以指定概率通过非树链路额外转发消息,且不影响共享树。在1000节点随机正则覆盖网络的仿真中,对随机选取的源,所提方法使95分位投递延迟比Plumtree降低约40%。

Ryohei Banno

arXiv cs.GT

Non-Monetary Mechanisms for Stochastic Scheduling via Sampled Pairwise Externality Compensation

说明基于采样两两外部性补偿的随机调度非货币机制

简介本文研究在不使用货币的情况下,如何在存在私有随机需求、允许排队、且参与者可能策略性甚至恶意行动时分配共享资源。作者提出了一种名为采样两两外部性补偿器(SPEC)的在线资源分配范式,用采样估计替代精确的未来外部性计算以提高效率。在随机调度模型中,机制使每个参与者获得接近最优的最坏情况效用比例,并在过期概率趋近于零的长期极限下趋近于其理想效用的全部。

David X. Lin, Chido Onyeze, Giannis Fikioris 等

arXiv cs.DC

Ineffective Occupancy in Heterogeneous GPU Clusters: Prediction, Contribution Analysis, and Readiness-Aware Scheduling

说明异构GPU集群中的无效占用:预测、贡献分析与就绪感知调度

简介本文针对异构GPU集群中作业已分配GPU却长期无法就绪、造成算力浪费的现象,在阿里巴巴GPU集群追踪数据中发现52.70%的执行记录从未就绪,并称之为“无效占用”。作者提出就绪感知调度(RAS),仅使用准入时可观测的九个属性预测就绪概率并据此重排准入顺序,在按机器分组的五折划分下梯度提升模型的ROC-AUC为0.8187。结果显示,RAS将无效占用比例从43.64%降至27.15%,并将八卡及以上大请求的有效覆盖率从46.11%提高到63.18%,且未牺牲容量利用率。

Tao Zhang, Bin Liao

★★★★☆ 值得关注
arXiv cs.DC 有代码

Triple Overlap in Pipelined Krylov Methods on Multi-GPU Systems

说明多 GPU 系统中流水线 Krylov 方法的三重重叠实现

简介本文提出一种三重重叠的流水线预条件共轭梯度法(Pipe-PCG)与流水线稳定双共轭梯度法(Pipe-BiCGStab)求解器实现,在计算、集合通信与点对点通信之间实现并发执行。实验在 MareNostrum 5 与 Leonardo 超算上进行,与 PETSc 及双流 NCCL 基线比较。结果显示,在 64 个 GPU 上相对双流基线的几何平均加速比约为 1.23 至 1.33 倍(Pipe-BiCGStab 约 1.30 倍),大规模实验最高提速 35%(Pipe-PCG)和 33%(Pipe-BiCGStab)。

看点将计算-通信重叠扩展为三流并发执行集合通信、P2P与计算核,相对两流基线有实质改进,在多达512 GPU上测试并给出明确加速。

Sinan Ekmek\c{c}iba\c{s}{\i}, James D. Trotter, Johannes Langguth 等

★★★★☆ 值得关注
arXiv cs.IT · math.IT

A Self-Coupling Gaussian Extremal Inequality for Information-Constrained Optimal Transport with Applications to Rate-Distortion-Perception

说明信息受限最优传输的自耦合高斯极值不等式及其在率失真感知中的应用

简介本文研究两个同分布副本之间达到目标相关性所需的最少互信息,证明在给定均值与协方差下,高斯分布的最小信息代价最大,即高斯极值不等式。证明采用中点粘合构造,并将其应用于率失真感知问题,在无限共同随机性及二次失真和Wasserstein-2感知度量下确立高斯极值性;对有限共同随机性情形也给出类似结果。

看点提出自耦合问题的高斯极值不等式并以中点粘合证明,改进了率失真感知理论的已知结论,证明严格且有应用。

Jiayang Zou, Jun Chen, Ayfer \"{O}zg\"{u}r 等

arXiv cs.DC

Mixed-Precision GPU Acceleration for Confidence Regions of Spatial Excursion Sets

说明空间超越集置信区域的混合精度GPU加速

简介本文提出一种GPU加速框架,用于计算空间超越集(场值超过阈值的区域)的内、外置信区域,以量化不完整且含噪声观测下的空间范围不确定性。该框架结合自适应分块混合精度运算与分布式任务执行,加速泛克里金、条件高斯模拟与置信区域校准。实验显示,在合适的精度容差下,经验覆盖率接近双精度参考值及名义90%置信水平,海洋表层盐度实验的结果也与双精度参考高度一致。

Xiran Zhang, Sameh Abdulah, Qinglei Cao 等

★★★★☆ 值得关注
arXiv cs.MS · cs.DC · cs.NA

Emulating DGEMM and ZGEMM with INT8 Matrix Engines on Intel Arc GPUs: Ozaki Scheme II on the Xe2 Architecture

说明在 Intel Arc GPU 上用 INT8 矩阵引擎模拟 DGEMM 与 ZGEMM:Xe2 架构上的 Ozaki 方案 II

简介本文提出首个面向 Intel GPU 的 Ozaki 方案 II 实现,基于 SYCL 与 oneMKL,完整提供 dgemm/zgemm 接口。该方法把浮点矩阵乘法转化为若干精确的 INT8 乘积加中国剩余定理重构,乘积个数决定精度。在 Intel Arc Pro B60 上,模拟 DGEMM 最高达到 21.1 TFLOP/s,约为原生 FP64 DGEMM 的 12 至 28 倍;模拟 ZGEMM 最高 27.4 TFLOP/s。

看点首次将Ozaki方案II移植到Intel GPU并针对Xe2架构做了多项优化,实测性能提升显著,且与原生FP64对比充分。

Rostislavs Rostovskis, Aleksandrs Platonenko

arXiv cs.DC

PlaneZip: Lossless Bit-Plane Compression of Training Activations Offloaded over PCIe

说明PlaneZip:对经 PCIe 卸载的训练激活值进行无损比特平面压缩

简介训练时在显存有限的条件下,部分激活值会被换出到主机内存或丢弃后重算。本文提出 PlaneZip,在数据拷贝路径上压缩被换出的张量,并据此调整换出规划。它为每个128字节块选择最小的编码方式,并预测压缩比以规划链路时间。在五个模型的激活值上,其压缩效果优于零值压缩,并在模拟中降低了重算开销。

Zhufan Gu, Qizhe Tang, Yuxin Wang 等

arXiv cs.IT · math.IT

Convergence of Denoising Diffusion Probabilistic Models: A Rényi Divergence Perspective

说明去噪扩散概率模型的收敛性:基于Rényi散度的分析

简介本文研究去噪扩散概率模型(DDPM)的收敛性,采用比总变差、KL散度和Wasserstein距离更强的Rényi散度作为度量。作者建立了DDPM的Rényi散度刻画,指出总误差可分解为混合误差、离散化误差和分数估计误差。文中还给出了达到α-Rényi散度下ε精度的迭代复杂度,并将分析推广到临界阻尼DDPM。

Wenliang Liu, Santiago Mazuelas, Guanding Yu 等

★★★★★ 值得关注
arXiv cs.GT · econ.TH

Improved Approximation and Tight Competition for Simple Auctions

说明简单拍卖的改进近似与紧竞争保证

简介本文研究单一加性买家、各物品估值相互独立的简单拍卖。在物品满足正则性条件时,作者证明分开出售与整体打包所得收益之间的近似关系是紧的,并回答了 Beyhaghi 等人(EC 2025)提出的开放问题。对一般独立物品,文章把近似系数从先前结果的 6 和 5.2 改进到 2.645,并把已知下界从 2 提高到 2.11。

看点改进了多物品拍卖的近似因子与下界,并给出回答公开问题的紧界,证明严格。

Yichen Huang

arXiv physics.soc-ph · cs.DC · cs.SI

A mechanism for collective foraging: percolating recruitment cascades coupled to a maximum-entropy field

说明集体觅食机制:耦合最大熵场的渗流招募级联

简介该论文提出一种集体觅食模型:发现资源的个体会通过线性阈值级联招募同伴,且招募过程会随个体移动改变通信网络,形成自限制的聚集与释放循环。作者称,在未经人工调参的情况下,发现招募、边际价值式离开斑块以及Levy搜索与局部开发切换等行为会同时出现。在资源稀疏且聚集时,收获量最多可达单独搜索的7.6倍。

Galen J. Wilkerson

arXiv cs.DC · cs.SY · eess.SY

HEL: A Heterogeneous Extensible Layer for GPU-Resident Runtime Orchestration

说明HEL:面向GPU常驻运行时编排的异构可扩展层

简介该论文介绍了一个名为HEL的GPU常驻运行时系统,它基于在用户应用整个生命周期内持续存在的有状态服务构建。程序员将工作负载表达为生成类协程任务的应用,由HEL运行时负责调度与执行,支持同步与异步任务、带运行时依赖的任务、批量提交和自动重试。论文通过生产者-消费者、主机RPC基准测试以及PFPL压缩案例进行评估,结果显示在GPU利用率不足的情况下,以及能够隐藏任务延迟的场景中,HEL具有性能优势。

Agnieszka M. {\L}upi\'nska, Serban D. Porumbescu, John D. Owens

arXiv math.ST · cs.IT · eess.SP

Sample complexity of weak-signal latent-variable models

说明弱信号隐变量模型的样本复杂度

简介本文研究弱信号条件下隐变量模型的参数估计,信号强度参数β越小,观测与未知参数的依赖越弱。作者在β的幂级数展开下分析似然比,证明若参数在r阶才首次全局可辨识,则达到固定精度至少需要约β^{-2r}个样本。文中还给出了最大似然估计和矩估计达到该速率的条件,并将框架应用于加性噪声信道和指数族模型等结构化模型。

Amnon Balanov, Tamir Bendory, and Dan Edidin

★★★★☆ 值得关注
arXiv math.CO · cs.DM · cs.IT

Optimal single-track Gray codes from Gray-ordered necklaces

说明基于 Gray 序项链的最优单轨 Gray 码

简介单轨 Gray 码是一种循环 Gray 码,其每一列都是第一列的循环移位。对于素数长度 n,最长周期为 2^n−2,此问题自 1996 年提出以来一直未解决。作者证明,Degni 与 Drisko(2007)关于项链反射 Gray 码序的一个猜想,蕴含每个素数长度都存在最优单轨 Gray 码;该蕴含已在 Lean 4 中形式化,并结合计算验证了 n≤47 的奇素数情形。

看点将Degni-Drisko猜想与单轨格雷码联系,解决了素数长度下的开放问题方向;证据包括形式化和分阶段计算验证,影响限于子领域。

Chris Dzoba