ICT数学问题

华为十大问题:大规模网络近似计算问题

发布时间:2022-07-01 文:任疆

问题背景:

信息社会的快速发展引发了数据规模的爆炸式增长,科学计算、社交媒体和金融分析等大规模应用中的计算和存储需求远远超出了现有可用资源。预计未来十年,全球数据中心管理的信息量将增长 50倍,而处理器数量将仅增长10倍。不断增长的性能需求将很快超过计算资源、存储资源和电力资源等的增长速度。因此,仅靠过度配置资源并不能解决计算机行业在不久的将来面临的难题。

由于大数据具有规模巨大、动态变化、可靠性低等特点,一些实际的大数据应用中,最优解是难以计算或者不必要的,追求可以高效计算并且满足需求的近似结果具有非常重要的意义。近似计算(approximate computing)技术由于极高的效率增益而成为此领域的潜在方向。

近似计算技术起源于20世纪 70年代,用于在多项式时间内求得NP困难问题的近似解,现在已经应用到更多的应用场景,例如图像与信号处理、机器学习、科学计算、金融分析和数据库查询等。现有的近似计算技术可以分为如下3个不同层次:

(1) 计算单元和存储单元层次

通过浮点运算器FPU的精度缩放和存储器DRAM/SRAM的刷新率和电压的调整实现对特定计算模块的近似以提高计算效率和降低能耗。

(2) 近似计算算法

通过高效的降维算法和高维优化理论和算法实现对大数据近似查询处理。

(3) 近似计算架构

通过采用不精确硬件和神经网络加速器等引入全新的系统架构来降低计算的精度以实现计算效率的提高。

图 1Sketch


问题定义:

前面讨论了近似计算的3个层次,在理论和算法层面,值得作为一个重点来进行深入研究。Sketch算法最早由Flajolet和 Martin提出,算法的示意图如图1,基本原理如图2。由于在数学上具有由高维空间投影到低维空间的保距性,因而该算法作为一个非常有潜力的近似算法被应用于高维数据降维等领域。由于具有良好的数学性质,Sketch算法还被广泛应用于流级别的网络测量方法中,其可以做到逐报文测量,通过将大量的数据存储在有限的空间内,实现高速网络测量。Sketch算法利用Hash计算的均匀散列性质,利用固定内存空间重叠记录信息,在测量理论的支撑下,实现近似精确的测量信息恢复,相比于传统方法,大大减少计算和存储的开销。Sketch算法的本质,是将高维空间数据映射到子空间,利用概率论方法保证数据恢复精度。该算法的优点是内存占用小、操作简单以及便于硬件操作实现。然而,传统的Sketch算法所达成的准确度与流量本身特征相关,只能保证少部分大象流的测量精度,而对大部分小鼠流的测量误差较大。

2Sketch 基本原理

压缩感知(compressed sensing,CS)是一种信号处理技术,可在低维向量中获取高维信号。2004年左右,Candès等证明了在已知信号稀疏性的情况下,能以欠采样方式重建原信号,这一理论也是压缩感知的基石。

CS和Sketch算法使用了相同的数学形式(基于矩阵形式的信号感知)。一个自然的问题是:能否基于CS理论重构Sketch算法实现对全体流量的低开销、近似无误差测量?

由于资源限制和测量位置的不可控问题,例如在所有的城域网接入网关上部署流量探针会面临用户设备的可支持性和需要操作用户测设备等困难,往往无法直接测量流量矩阵数据。但是,部分流量数据的获得却是可能的,例如可以在网络的核心节点上部署流量探针探测部分流量,或者是可以获得传输链路上的汇总流量数据,然后基于流量数据之间的时间和空间上的相关性通过矩阵恢复/补齐和压缩感知等方法计算整体流量矩阵的近似值。然而,由于涉及到大规模矩阵的计算问题,大规模流量矩阵计算的准确性和效率仍然面临很大的挑战。

未来研究方向:

利用压缩感知/张量理论/随机矩阵理论,实现超大规模数据近似计算,是解决网络级数据近似计算的主要工作方向,在相关理论的研究应用中,我们认为应该针对网络数据的特点,进一步研究如下几个方向:

(1) 网络数据的时空相关性导致的张量/矩阵的低秩性;

(2) 考虑多个时间片数据的连续变化性质,研究时间维度上的光滑性;

(3) 在理论上建立算法精度与近似算法的关系,找到高精度、低复杂度的近似算子。



附件下载: