大数据并行与交互式计算.pdf

大数据并行与交互式计算 Parallel and Interactive Computing of Big Data 陈国良 摘要： 在计算理论中，计算复杂类主要研究P类与 NP类两大类问题。在大数据的情况下，为了提高P 类问题的求解速度，可采用并行方法，其中一个实 例就是NC类并行计算；为了改进NP类问题的求解 质量，可采用交互方法，其中一个实例就是IP类交 互计算。本报告，首先简要介绍一下预备知识，包 括计算模型与计算复杂性，问题的确定性与非确定 性求解，P类与NP类基础知识等；然后讨论一下P 类问题的并行求解与NP类问题的交互求解；最后 在结论中根据目标，研究对策和具体实施方案，概 括出大数据计算的总体框架。 2 目 录 1. 计算模型与计算复杂性 (1) 图灵机 （TM ）模型与并行随机存取（PRAM ）模型 (2) 计算复杂性 2. 问题的确定性与非确定性求解 (1) 确定图灵机与问题确定性求解 (2) 非确定图灵机与问题非确定性求解 3. P类问题与NP类问题 (1) P类问题及其多项式时间求解 (2) NP类问题及其多项式时间验证 (3) NP难（NPH ）、NP完全（NPC ）与P完全（PC ）问题 4. P类问题的并行求解 (1) 计算模型 (2) NC类并行计算 5. NP类问题的交互求解 (1) 计算模型 (2) IP类交互计算 6. 结论：大数据计算框架 (1) 目标1与目标2 (2) 对策1与对策2 (3) 实施1与实施2 3 详解思路 1. 预备知识 (1) 计算复杂性（Computing Complexity ）：多项式/对数多项式函数 (2) 计算复杂类（Computing Complexity Classes ）：P类与NP类/NC类与 IP类 (3) 算法设计（Design Algorithms ）：求解算法与验证算法 2. 研究问题的动机 (1) 即使低阶多项式解，在大数据情况下也变成Intractable：例如快速线 性扫描E级一维数组，也需要长达数年时间！ (2) 怎么办？ ① 采用并行办法以提高计算速度（例如P类问题） ② 采用交互办法以改进求解质量（例如NP类问题） 3. 大数据计算应包括大数据的表示、设计、分析和计算： (1) BD表示：可采用度量空间（用数组和距离两个参数表示数据的本征 特征）。 (2) BD设计：①静态（离线）：采用N→K约减算法和MR归约算法； ②动态（在线）：采用流式增量算法。 (3) BD分析：在生命周期内，要对计算函数f(n)和计算变量D 同时分析： 前者侧重因果分析；后者侧重关联分析。 (4) BD计算：①P类问题，采用并行NC类计算； ②NP类问题，采用交互IP类计算。 4 1、计算模型与计算复杂性 (1) 图灵机（TM ）模型与并行随机存取（PRAM ）模型 ① 图灵机 （TM ：Turing Machine ）模型：它是对一条两端可无限延长的纸 带上的0和1符号执行操作，一步一步地改变纸带上0或1的值，经过有限 步骤，最终得到一个满足预先要求的符号串变换。 ② 并行随机存取 （PRAM：Parallel Random Access Machine ）模型：它是由 一个容量无限大的共享