数据协调算法

㈠ 数据分析包括哪些算法

1. Analytic Visualizations(可视化分析)

不管是对数据分析专家还是普通用户，数据可视化是数据分析工具最基本的要求。可视化可以直观的展示数据，让数据自己说话，让观众听到结果。

2. Data Mining Algorithms(数据挖掘算法)

可视化是给人看的，数据挖掘就是给机器看的。集群、分割、孤立点分析还有其他的算法让我们深入数据内部，挖掘价值。这些算法不仅要处理大数据的量，也要处理大数据的速度。

3. Predictive Analytic Capabilities(预测性分析能力)

数据挖掘可以让分析员更好的理解数据，而预测性分析可以让分析员根据可视化分析和数据挖掘的结果做出一些预测性的判断。

4. Semantic Engines(语义引擎)

我们知道由于非结构化数据的多样性带来了数据分析的新的挑战，我们需要一系列的工具去解析，提取，分析数据。语义引擎需要被设计成能够从“文档”中智能提取信息。

5. Data Quality and Master Data Management(数据质量和数据管理)

数据质量和数据管理是一些管理方面的最佳实践。通过标准化的流程和工具对数据进行处理可以保证一个预先定义好的高质量的分析结果。

㈡ 大数据核心算法有哪些

1、A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。
2、集束搜索(又名定向搜索，Beam Search)——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。

3、二分查找(Binary Search)——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

4、分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。

5、Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

6、数据压缩——采取特定编码方案，使用更少的字节数(或是其他信息承载单元)对信息编码的过程，又叫来源编码。

7、Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

8、Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

9、离散微分算法(Discrete differentiation)。

㈢ 数据挖掘十大算法-

整理里一晚上的数据挖掘算法，其中主要引自wiki和一些论坛。发布到上作为知识共享，但是发现Latex的公式转码到网页的时候出现了丢失，暂时没找到解决方法，有空再回来填坑了。

——编者按

一、 C4.5

C4.5算法是由Ross Quinlan开发的用于产生决策树的算法[1]，该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法主要应用于统计分类中，主要是通过分析数据的信息熵建立和修剪决策树。

1.1 决策树的建立规则

在树的每个节点处，C4.5选择最有效地方式对样本集进行分裂，分裂规则是分析所有属性的归一化的信息增益率，选择其中增益率最高的属性作为分裂依据，然后在各个分裂出的子集上进行递归操作。

依据属性A对数据集D进行分类的信息熵可以定义如下：

划分前后的信息增益可以表示为：

那么，归一化的信息增益率可以表示为：

1.2 决策树的修剪方法

C4.5采用的剪枝方法是悲观剪枝法(Pessimistic Error Pruning，PEP)，根据样本集计算子树与叶子的经验错误率，在满足替换标准时，使用叶子节点替换子树。

不妨用K表示训练数据集D中分类到某一个叶子节点的样本数，其中其中错误分类的个数为J，由于用估计该节点的样本错误率存在一定的样本误差，因此用表示修正后的样本错误率。那么，对于决策树的一个子树S而言，设其叶子数目为L(S)，则子树S的错误分类数为：

设数据集的样本总数为Num，则标准错误可以表示为：

那么，用表示新叶子的错误分类数，则选择使用新叶子节点替换子树S的判据可以表示为：

二、KNN

最近邻域算法(k-nearest neighbor classification, KNN)[2]是一种用于分类和回归的非参数统计方法。KNN算法采用向量空间模型来分类，主要思路是相同类别的案例彼此之间的相似度高，从而可以借由计算未知样本与已知类别案例之间的相似度，来实现分类目标。KNN是一种基于局部近似和的实例的学习方法，是目前最简单的机器学习算法之一。

在分类问题中，KNN的输出是一个分类族群，它的对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。在回归问题中，KNN的输出是其周围k个邻居的平均值。无论是分类还是回归，衡量邻居的权重都非常重要，目标是要使较近邻居的权重比较远邻居的权重大，例如，一种常见的加权方案是给每个邻居权重赋值为1/d，其中d是到邻居的距离。这也就自然地导致了KNN算法对于数据的局部结构过于敏感。

三、Naive Bayes

在机器学习的众多分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive Bayesian Model，NBC)[3]。朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。

在假设各个属性相互独立的条件下，NBC模型的分类公式可以简单地表示为：

但是实际上问题模型的属性之间往往是非独立的，这给NBC模型的分类准确度带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型；而在属性相关性较小时，NBC模型的性能最为良好。

四、CART

CART算法(Classification And Regression Tree)[4]是一种二分递归的决策树，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分。在CART算法中主要分为两个步骤：将样本递归划分进行建树过程；用验证数据进行剪枝。

五、K-means

k-平均算法(k-means clustering)[5]是源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-means的聚类目标是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类。

5.1 k-means的初始化方法

通常使用的初始化方法有Forgy和随机划分(Random Partition)方法。Forgy方法随机地从数据集中选择k个观测作为初始的均值点；而随机划分方法则随机地为每一观测指定聚类，然后执行“更新”步骤,即计算随机分配的各聚类的图心，作为初始的均值点。Forgy方法易于使得初始均值点散开，随机划分方法则把均值点都放到靠近数据集中心的地方；随机划分方法一般更适用于k-调和均值和模糊k-均值算法。对于期望-最大化(EM)算法和标准k-means算法，Forgy方法作为初始化方法的表现会更好一些。

5.2 k-means的标准算法

k-means的标准算法主要包括分配(Assignment)和更新(Update)，在初始化得出k个均值点后，算法将会在这两个步骤中交替执行。

分配(Assignment)：将每个观测分配到聚类中，使得组内平方和达到最小。

更新(Update)：对于上一步得到的每一个聚类，以聚类中观测值的图心，作为新的均值点。

六、Apriori

Apriori算法[6]是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。Apriori采用自底向上的处理方法，每次只扩展一个对象加入候选集，并且使用数据集对候选集进行检验，当不再产生匹配条件的扩展对象时，算法终止。

Apriori的缺点在于生成候选集的过程中，算法总是尝试扫描整个数据集并尽可能多地添加扩展对象，导致计算效率较低；其本质上采用的是宽度优先的遍历方式，理论上需要遍历次才可以确定任意的最大子集S。

七、SVM

支持向量机(Support Vector Machine, SVM)[7]是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

除了进行线性分类之外，SVM还可以使用所谓的核技巧有效地进行非线性分类，将其输入隐式映射到高维特征空间中，即支持向量机在高维或无限维空间中构造超平面或超平面集合，用于分类、回归或其他任务。直观来说，分类边界距离最近的训练数据点越远越好，因为这样可以缩小分类器的泛化误差。

八、EM

最大期望算法(Expectation–Maximization Algorithm, EM)[7]是从概率模型中寻找参数最大似然估计的一种算法。其中概率模型依赖于无法观测的隐性变量。最大期望算法经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望(E)，利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化(M)，最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

九、PageRank

PageRank算法设计初衷是根据网站的外部链接和内部链接的数量和质量对网站的价值进行衡量。PageRank将每个到网页的链接作为对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。

算法假设上网者将会不断点网页上的链接，当遇到了一个没有任何链接出页面的网页，这时候上网者会随机转到另外的网页开始浏览。设置在任意时刻，用户到达某页面后并继续向后浏览的概率，该数值是根据上网者使用浏览器书签的平均频率估算而得。PageRank值可以表示为：

其中，是被研究的页面集合，N表示页面总数，是链接入页面的集合，是从页面链接处的集合。

PageRank算法的主要缺点是的主要缺点是旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多外链，除非它是某个站点的子站点。

十、AdaBoost

AdaBoost方法[10]是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器Ck。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器Ck[，并且如此迭代地进行下去。

AdaBoost方法的自适应在于：前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中，AdaBoost方法相对于大多数其它学习算法而言，不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱（比如出现很大错误率），但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，同样也能提升分类效果。

引用

[1] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.

[2] Altman, N. S. An introction to kernel and nearest-neighbor nonparametric regression. The American Statistician. 1992, 46 (3): 175–185. doi:10.1080/00031305.1992.10475879

[3] Webb, G. I.; Boughton, J.; Wang, Z. Not So Naive Bayes: Aggregating One-Dependence Estimators. Machine Learning (Springer). 2005, 58 (1): 5–24. doi:10.1007/s10994-005-4258-6

[4] decisiontrees.net Interactive Tutorial

[5] Hamerly, G. and Elkan, C. Alternatives to the k-means algorithm that find better clusterings (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 2002

[6] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994.

[7] Cortes, C.; Vapnik, V. Support-vector networks. Machine Learning. 1995, 20 (3): 273–297. doi:10.1007/BF00994018

[8] Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39 (1):1–38, 1977

[9] Susan Moskwa. PageRank Distribution Removed From WMT. [October 16, 2009]

[10] Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855

㈣ GPU和CPU之间是如何协调数据处理的

因为设计的目标不同，当今的CPU和GPU功能上有本质的不同。作为通用处理器的CPU，顾名思义，它是设计用来处理通用任务的处理、加工、运算以及系统核心控制等等的。CPU中包含的最基本部件有算术逻辑单元和控制单元，CPU的微架构是为高效率处理数据相关性不大的计算类、复杂繁琐的非计算类的等等百花八门的工作而优化的，在处理日常繁复的任务中应付自如。

计算机的“灵魂”——操作系统，以及几乎100%的系统软件都主要仰仗CPU来顺利运行。CPU面对的算术、逻辑运算以及控制处理是非常繁琐和复杂的，面对处理的数据和信息量不仅数量多而是种类多。CPU运算和控制多面手的这种设计，让它在计算机中得心应手，位置不可动摇。

GPU设计的宗旨是实现图形加速，现在最主要的是实现3D 图形加速，因此它的设计基本上是为3D图形加速的相关运算来优化的，如z-buffering 消隐，纹理映射(texture mapping)，图形的坐标位置变换与光照计算(transforming & lighting)等等。这类计算的对象都是针对大量平行数据的，运算的数据量大，但是运算的类型却并不复杂，大多类似和雷同，计算性强但是逻辑性不强，如矩阵运算就是图形运算的典型特性。

如今的游戏，单单从图象的生成来说大概需要下面四个步骤：

1、Homogeneous coordinates（齐次坐标）
2、Shading models（阴影建模）
3、Z-Buffering（Z-缓冲）
4、Texture-Mapping（材质贴图）
在这些步骤中，显示部分（GPU）只负责完成第三、四步，而前两个步骤主要是依靠 CPU 来完成。而且，这还仅仅只是3D图象的生成，还没有包括游戏中复杂的AI运算。场景切换运算等等……无疑，这些元素还需要CPU去完成，这就是为什么在运行《魔兽世界》的时候，当场景切换时再强劲的显卡都会出现停顿的现象。
对于需要CPU进行大量AI运算的游戏来说，在固定的显示分辨率下，CPU的架构越强、主频越高的确有一定的优势。着名的FPS第一人称设计游戏——CSS，就是一个很好的例子。当你开启了30个左右的机器人，在大混战的时候就很容易体现出高端CPU与入门级CPU之间的区别了。
打造一套完整的游戏 PC 系统，CPU和显卡的搭配应该相得益彰，高成低就或低成高就都是不平衡的组合方式。

第一代 GPU 首先，CPU将数据传递给GPU进行处理，数据先进入T&L单元中的Transform Engine，在这里，数据将以顶 点的形式接受视野范围的判断，当处理单元判断某部分顶点处于观察者的视线范围以外时，Transform Engine将把这部分顶点“剪除”以使其不会 干扰后续的流水线操作, 具个简单的例子：当你在某FPS游戏中突然打开狙击枪的狙击镜，视野变成了一个圆形的空洞，而其他部分则为黑色，这时 Transform Engine将去除这个圆形视野范围以外的所有顶点，不过，这里进行的只是视野范围的判断，Transform Engine去除在 你的视线范围内但是被其它东西挡住了的物体，另外，每一个三角形可能被旋转，放大/缩小，上升，下降，左偏，右移等。 这就是多边形转换转换。 Transform Engine根据你的视角，改变了由程序提供的组成3D物体的顶点的坐标。经过Lighting Engine处理后的图象经过判断 处理后的数据将流入T&L单元中的Lighting Engine，根据光源的类型，距离，角度，数目，应用方式等不同参数，每一个多边形都会有 不同的光影表现和光影关系，因而需要不同的光线函数予以表征，在Lighting Engine中，处理单元将根据软件提出的光源分布情况为每个顶点计算 出它所具有的光线矢量，以便后续进行的光线纹理贴图，着色等操作
经过Lighting Engine处理的画面
其实，经由T&L单元处理过的数据还只是抽象的数据，并不是具体的图形，上面两副图仅仅是方便读者进行想象的示意图。
接下来数据将流入Setup Engine，在这里，运算单元将进行三角形的设置工作，这是整个绘图过程中最重要的一个步骤，Setup Engine甚 至直接影响着一块GPU的执行效能。三角形的设置过程是由一个一个的多边形组成的，或者是用更好的三角形代替原来的三角形。在三维图像中可能会有些三角形 被它前面的三角形挡住，但是在这个阶段3D芯片还不知道哪些三角形会被挡住。所以三角形建立单元接收到的是一个个由三个顶点组成的完整三角形。三角形的每 个角（或顶点）都有对应的X轴、Y轴和Z轴坐标值，这些坐标值确定了它们在3D景物中的位置。同时，三角形的设置也确定了像素填充的范围
经过Setup Engine处理的画面
最终着色完毕的画面
在三角形设置完毕后，T&L单元的全部运算就完成了。接下来数据将进入NV15独有的NSR像素处理单元进行一定的像素处理，接着流入像素流水线 进行后续的纹理像素填充等操作，这部分操作在DriectX7.0中的变化并不明显，基本的渲染填充过程与过去的显卡几无二异
T&L虽然再一定程度上缓解了CPU运算能力的不济所带来的瓶颈，使得系统在图形方面的资源得到了再分配和增强，但同时，T&L也将新的矛盾转到了GPU上
T&L是一组相对固定的简单的图形函数，所实现的特效受到了函数本身语句的限制，虽然这种固定的指令集设计可以带来比较高的执行效率，但这种设置 使得DX7下所能实现的特效受到了指令集的约束，许多逼真的特效无法实现，程序员的思想也被限定在一个相对狭窄的范围内。
2、我要看到你飘逸的秀发和迷人的微笑—可编程Shader以及第二代GPU
DriectX8.0在传统T&L的基础上加入了两个新的概念—可编程的Vertex Shader和Piexl Shader，同样的，第二代 GPU的标志就是硬件级别的可编程Shader运算，代表产品为NV2X（Geforce3/4Ti），R2XX（Radeon8500）等
可编程Shader的复杂程度远非T&L可比，为了方便大家理解第二代GPU的特点，我们先来认识一下什么是可编程Shader，以及可编程Shader运算单元
可编程Vertex Shader及顶点处理器：
可编程Vertex Shader让程序员能够对特定物体，甚至整个画面的每一个顶点，指定特别的运算程序，却不需要CPU介入。每一个顶点都携带相当多 的信息，比如坐标，重量，法线，颜色，纹理坐标，雾和点大小数据。顶点处理器能够以简短的程序来改变上述这些信息。 这些小程序直接由顶点着色引擎本身执 行，不必劳驾CPU。 典型的T&L引擎将程序员限制在3D运算的光影转换之前， 在有了顶点处理器的支持之后，游戏设计师对游戏场景里的3D物 体能够为所欲为的操纵变化，而且不需要用到中央处理器。
这导致了一场革新，程序可以改变顶点的坐标，这样基本上改变物体的形状，以达到更接近真实的移动、移动残影、混色、内插（在两种外型间转换），以及变形， 比如改变角色脸部的骨骼和皮肤一个产生一个适时的微笑。也可改变顶点上的颜色数据和纹理坐标，物体表面的颜色达到设计师所想要的色彩效果、投影、凹凸贴图 设置（如Blinn Bump mapping）或者其它投射的纹理。光源也可以为程序员随心所欲的调整，不再像过去那样需要对光源的效果进行笨拙的光线 纹理贴图，而这些在以前是不可想象的。这一切都归功于可编程Vertex Shader和顶点处理器的出现
Blinn Bump mapping
可编程Piexl Shader以及像素处理器
在NV15中，nVidia曾经尝试加入一个叫NSR的像素处理单元，它可以在数据进入像素流水线之前对每个像素进行一系列运算操作，虽然同为每像素操 作，但NSR与Piexl Shader可不能同日而语， NSR对于像素的运算只有7种，同T&L一样，它依然是固定模式的，程序员依然要依照 规定好的条条框框写出程序，而Piexl Shader则不同，我们可以用许多不同方式去编程，以实现不同的特效，下面就是一般的像素处理器所具备的特 性：
· 阴影贴图
· 快速纹理载入
· 影像乘法，对称核心
· 支持4096x4096或512x512x512 纹理
· 立方体贴图每边可4096x4096x32-位
· 支持YUYV的纹理（自动转换成RGB三原色）
· 支持全景贴图
可以指向任何一个图像，如背景缓冲区（back buffer），而可直接当作纹理使用
· 边缘色彩及边缘纹理
· 硬件同步化读/写
对同一张纹理的读及写允许全流水线操作。
可以对背景缓冲区着色，然后马上能当作纹理使用
· Pass through colors
· 支持DX6规格的环境凹凸/亮度贴图（就是环境凹凸贴图）
· 简单的纹理，S,T 在alpha/红(AB)及蓝/绿 (BG)
· 等向的双方向性反射分布功能光源
· 内积产生色彩贴图或Z坐标
· 真实反射凹凸贴图
这看起来似乎有点抽象，简单的说，可编程Piexl Shader实现了一个非常重要的特效—真实的毛发
古老街道上昏暗灯光中的狼人
在3D渲染中，渲染真实的毛发一直是一件非常困难的事情，大量的多边形给多边形生成带来了严峻的考验，而每一根毛发之间复杂多变的即时光影关系更不是几个简单固定的指令所能实现的。Piexl Shader的可编程性和运算能力很好的解决了这个问题
好啦，现在让我们来看看第二代GPU是如何完整处理一个画面的吧
首先，来自CPU的各种物理参数进入GPU，Vertex Shader将对顶点数据进行基本的判断，如果没有需要处理的Vertex效果，则顶点数据直 接进入Transform&Lighting Unit进行传统的T&L操作以节约时间提高效率，如果需要处理各种Vertex效果，则 Vertex Shader将先对各种Vertex Programs的指令进行运算，一般的Vertex Programs中往往包含了过去转换，剪 切，光照运算等所需要实现的效果，故经由Vertex Shader处理的效果一般不需要再进行Transform&Lighting操作；另 外，当遇到涉及到曲面镶嵌（把曲面，比如弓形转换成为多边形或者三角形）的场合时，CPU可以直接将数据交给Vertex Shader进行处理
另外，在DX8.0的Transform过程中，Vertex Shader可以完成Z值的剔除，也就是Back Face Culling—阴面隐去，这就意味着除了视野以外的顶点外，视野内被前面顶点遮住的顶点也会被一并剪除，这大大减轻了需要进行操作的顶点数目
接下来，经由Vertex Shader处理完成的各种数据将流入Setup Engine，在这里一如既往的进行三角形的设置工作，到这里为止，Vertex Shader的工作就完成了
过去，设置好的三角形本来应该带着各自所有的参数进入像素流水线内进行纹理填充和渲染，但现在则不同，在填充之前我们还需要进行Piexl Shader的操作
其实Piexl Shader并非独立存在的，它位于纹理填充单元之后，数据流入像素流水线后先进入纹理填充单元进行纹理填充，然后便是 Piexl Shader单元，经由Piexl Shader单元进行各种处理运算之后再进入像素填充单元进行具体的着色，再经由雾化等操作后，一个完整 的画面就算完成了
值得注意的是，第二代GPU中普遍引入了独立的显示数据管理机制，他们位于Vertex Shader，Setup Engine以及像素流水线之间，负 责数据的更有效率的传输、组合，各种无效值的剔除，数据的压缩以及寄存器的管理等工作，这个单元的出现对整个GPU的工作效率的保证其到了至管重要的作 用。
HyperZ系列：HyperZ技术本身就是一种类似nVIDIA的“Z-封闭甄别”的技术，但是比nVIDIA还更进一步。它的主要功能简单说来就是分 析在Z轴上的场景，被遮挡的就会被忽略掉，只渲染我们能看到的部分场景；然后对渲染过的Z轴场景进行压缩处理，数据的压缩可减少他所占用的空间，从而在存 取Z-Buffer数据的时候可以保留更多的显存带宽。而且这是一种画面质量没有损害的压缩算法，并不影响画面质量。最后一步就是把经过渲染的场景中的Z -Buffer信息立刻清除掉，这样就更加大了显存带宽的利用率。
LMA（光速显存架构）系列：光速显存架构采用的第一个技术是“显存交错控制”技术， LMA中的显存控制器划分成了4个独立的显存控制单元，每个单元最 大可以进行32bit图形相关数据的存取工作，并且这4个单元之间以及它们和图形处理单元之间都保持密切的通讯联系，并随时协调平衡各个子单元之间的数据 流量，因此整体来看LMA的显存控制单元还是可以进行128bit数据的存储，但是保证了显存带宽的充分利用。光速显存架构采用的第二个技术是“无损Z压 缩算法”。传统的图形芯片对于每个待渲染的图形象素都要进行Z轴数据的读写工作，因此存储这些数据的Z缓存一向是消耗显存带宽的大户。LMA中集成了硬件 “无损Z压缩”单元，采用“无损Z压缩算法”对Z－缓存数据进行4:1的完全无损压缩。 光速显存架构采用的第三个技术是“Z-封闭甄别”。排除了图象中 被遮盖住而不可见的部分，这样GPU就不做隐面模型构建(节省处理器的多边形运算资源),并且渲染管线也不对隐面进行渲染(无需从帧缓存中读写隐面资料数 据,节省渲染管线的象素和纹理生成资源并完全消灭了隐面资料对显存带宽的占用)。最后，LMA还包括了4组高速Cache，对数据传输进行缓冲。
3、梦中的镜花水月—可编程Shader2.0以及第三代GPU
当你第一次看到3Dmark03中的MotherNature时，你有没有感觉到震撼？
更加宽泛的色彩范围能够使得图形的逼真度上升，这就是Shader2.0的由来，Shader2.0的核心实际上就是以扩大指令数目以及FLOAT数据形 式的应用来提高色彩表达的精确度，而第三代GPU的Shader单元也由此而具备了高精度FLOAT色彩数据的运算能力。从一般角度来讲，第三代GPU同 第二代GPU相比在基本的操作控制形式等方面并没有本质的区别，但是由于Shader2.0更大的指令长度和指令个数，以及通用程序+子程序调用的程序形 式等使得第三代GPU在处理高精度的庞大指令时效率上有了明显的提升，同时也使得第三代GPU的可编程性跃上了一个新的台阶
让我们来看看第三代GPU到底有哪些改进吧
Vexter Shader部分
第三代GPU的顶点处理器部分除了一般的操作功能外还具备流程控制能力，包括循环，跳跃以及子程序调用等，这些控制指令以及更多向量（或标量）寄存器的应 用使得顶点处理器能够以更高的效率执行Vertex Programs，提高了Vertex的处理速度。同时，加大的指令长度和指令数量使得顶点处理器的 功能得到了进一步的强化。另外，在第三代GPU中，传统的T&L数据将完全交由顶点处理器来执行，Transform& Lighting Unit将彻底被顶点处理器“吞并”，这也是第三代GPU的一个重要特点
Piexl Shader部分
第二代GPU的Piexl Shader只能实现INT数据的运算，这势必会带来最终运算结果的不精确，而数据的不精确导致了颜色表现的不准确，干扰了最 终画面的质量以及效果的表现，第三代GPU的重点改进就是运算单元和寄存器所支持的运算格式，现在Piexl Shader可以进行更高精度的FLOAT 运算和输出，从而使得图形的色彩显示更加精确
暴光正确的图象
数据精度不当而无法实现的特种暴光
另外，第三代GPU的像素处理器每周期所能处理的材质以及指令也分别增加了数倍，这些新特性使得第三代GPU可以处理各种复杂程度的效果，营造一个更为真实的3D画面，比如更加真实的水面效果
INT Piexl Shader所表现的水面效果
FLOAT Piexl Shader所表现的水面效果
传统的INT无法表现宽泛的波浪效果，程序员害怕数据精度范围狭窄引起的上溢或者下溢的发生而不得不在一个很小的物理参数范围内控制涟漪水面所需的波长、 波浪的大小、移动速度以及反射和折射效果等，现在，由于数据精度的提升，像素处理器完全可以处理一个非常宽泛的数据精度范围，避免数据的溢出，这就使得更 加真实的水面效果得以被表现。第三代GPU的代表是NV3X系列，R3XX系列等，其中R3XX系列的基本处理方式和顺序与第二代GPU在本质上基本相 同，仅仅是Vertex Shader和Piexl Shader的具体操作细节和运算精度上有些许不同，而NV3X虽然在基本原理上也与之大略相同，但 从流水线的角度来看则与完全不同，应该算是个“异类”。产生过程，只分析一下NV3X
以NV35为例：
首先，他具有8个纹理帖图单元，但8个纹理贴图单元并不在固定分布于每一条Piexl流水线，而是集簇在一起，根据情况来搭配，可以是4*2、8*1。
其次，他具有12条Shader流水线，但没有全盘采用浮点渲染流水线，而只是把12条Shader流水线中的8条做成具备浮点处理能力;不过全部12条Shader流水线都具备Fixed-Point Shader的执行能力。
另外，NV3X将流水线后部的各种渲染单元，如雾化，Alpha混合等大幅削减，使得流水线在一定程度上公用这些单元
NV30的构架组成形式基本上与之相当，只是数目上略有不同
由于这个构架并不是传统意义上的4*2或者8*1的固定构架，我们不能象过去那样说NV35“每个流水线具有2个纹理帖图单元”或者“每条管线具有3个Shader流水线”……我们只能说“NV35单位周期可以完成8次左右的纹理贴图或者12次Shader操作”
另外，由于NV3X对于Fixed-Point Shader的支持精度是FP16和FP32，同时NV3X的Shader流水线的单位Fixed- Point Shader处理精度是16位，所以当遇到32位Fixed-Point Shader数据时，能进行Fixed-Point Shader 数据处理的8条Shader流水线也会根据情况进行搭配来运算32位的Fixed-Point Shader数据
Pixel Programs往往是由多条指令构成的，不同的指令需要不同的执行时间来完成，每个像素必须在应用在它“身上”的Pixel Shader 操作完成后才能由像素流水线写入到帧缓存里。故此，对于应用了Piexl Shader的像素实际上是需要多个以上的周期才能写入到帧缓存里，如果采用8 条完整的渲染流水线的话， 流水线后面的雾化、色彩混合等单元很多时候都会处在等待阶段，这部分单元需要占用的晶体管数量不在少数，如果这样浪费就怪可惜 的，砍掉后其中的雾化等单元后，对整体的性能虽然有一些影响，但是却可以把节省下来的晶体管用于加强Pixel Shader的功能和性能上来，同时可以 保证比较高的多重纹理效率，利大于弊。
简单的，这个有点诡异的体系节省晶体管的同时能确保相对较好的Pixel Shader效能，同时还有极高的多重贴图效能
nVidia本指望4条Pixel管线+ 12条Shader流水线的设计能够在现在以及未来较长的一段时间的游戏里提供超过4条甚至8条 Pixel Pipeline显卡的效能。不过，实际情况却与nVidia的初衷有些背道而驰，Shader的完美应用带来的一个结果就是越来越好的非多 纹理光效果，传统的多纹理贴图才能表现的很好的光效果现在只需要进行一次贴图或者直接使用Shader就可以达到，这使得NV3X的设计成为了空架子，实 用意义大大降低，而在单纹理处理过程中由于NV3X的后续效果单元被削减，它的渲染效能注定没有传统的完整流水线高，另外，由于DX9中的最终FP精度被 定义为FP24，这导致了NV3X的相对低下的FP效能。最终，本来“先进”的NV3X构架落的个整体效能低下的下场
从本质上来讲，图形数据在NV3X中的实际处理过程依然是沿着顶点处理器—Setup Engine—像素流水线的顺序进行的，这与R3XX以及所有的第二代GPU是相同的
天堂的入口—可编程Shader3.0，DriectX Next以及未来的GPU
在微软刚刚公布的Driect9.0C中，Vertex Shader和Piexl Shader已经具有了几乎相同的能力，而在nVidia新发布的第 四代GPU—NV40中，我们发现Vertex Shader包含了4个纹理取样器，可以使用texld指令进行查表操作， NV40可以在一个 shader pass里完成4个纹理的读取，这个对于通用替换贴图而言相当的重要，有了vertex texturing功能后， vertex shader就能读取纹理信息直接映射到顶点上，以实现displacement mapping（位移映射）等等效果，用不同的纹理和较 少的顶点传输时间就能实现外形复杂、平滑的模型，这表明GPU中Vertex Shader的功能正在逐渐接近Piexl Shader。随着GPU的发 展，未来GPU中的Vertex Shader和Piexl Shader最终将被合并成一个统一的处理单元—Intergrated Shader，两 种处理单元将使用完全相同的语法以及指令集，Shader的统一将带来完全不同与现在的数据执行处理方式，GPU的内部结构将发生本质的变化， Intergrated Shader带来了更低晶体管数目的解决方案，以更少的晶体管数目来完成现在需要数亿晶体管才能完成的功能，同时统一 Shader将引出类似全通用I/O接口的设计以利资源的更合理的传输和分配，同时，为了解决越来越庞大的数据量，虚拟显存、无限资源访问以及帧缓冲操作 等技术的引入也势在必行。另外，我们在DirectX Next中还发现了整数指令集，处理器等特殊的定义，这些新颖的设计为我们勾勒出了未来GPU的轮 廓
整数指令集
在编程中不必在担心指令限制是一个很大的进步，不过想使得GPU更为通用还需要更多的工作。一个需要提高的主要区域就是整数处理能力。目前基于在着色器中 处理的所有数据都是浮点，这对于大多数显卡操作而言是没有问题的，不过不适合动态分支预测、非内插式显存搜索（如顶点缓冲的索引）等操作。在目前的GPU 中，唯一的内存寻址就是纹理查找，使用的也是浮点值。这样的情况对于纹理定位而言没有什么问题，不过对于通用内存寻址而言就不合适了，这里的连续内存块可 以完全彼此没有关联，采用内插式查找没有任何意义。微软对于这样的情况，在4.0版的Shader模型中引入了全新的、完整的整数指令集。拓扑处理器实际 上，目前的显卡可以在某些情况下新生成三角形，比如在用到直线以及点的时候。大多数的娱乐级显卡只具备对三角形进行光栅化处理的能力，这也就意味着所有的 点、线就必须转化为三角形。点和线在最后都将以2个三角形结束，这样就需要用到2-6个顶点（根据索引方式的不同而变化）。从本质上来说，这样的做法是有 益处的，通过可编程的管线，显示先前应该遮蔽的场景也就无需通过CPU，而可以通过微软的“拓扑处理器”直接完成。从逻辑上来说，这个拓扑处理器和镶嵌单 元是相互独立的，这个处理器在两种操作集中均可以使用。由目前的趋势来看，未来的GPU将向着高运算能力，高精度，高通用性的方向发展，GPU在工作方式 上将越来越接近CPU，由于高通用性等CPU特性的引入，GPU可能在一定程度上替代一部分CPU在非绘图领域的工作，也许在未来我们会看到由全GPU组 成的图形工作站。尽管未来GPU需要面对由于这些改进而带来得的诸多问题，尤其是通用性导致的效率低下，比如Intergrated Shader的效率 低下，但随着时间的推移，各种问题都将会得到妥善的解决。

㈤ 分布式存储中，怎样使用paxos算法保证数据的一致性

在分布式系统中，我们经常遇到多数据副本保持一致的问题，在我们所能找到的资料中该问题讲的很笼统，模模糊糊的，把多个问题或分类糅合在一起，难以理解。在思考和翻阅资料后，通俗地把一致性的问题可分解为2个问题：
1、任何一次修改保证数据一致性。
2、多次数据修改的一致性。
在弱一致性的算法，不要求每次修改的内容在修改后多副本的内容是一致的，对问题1的解决比较宽松，更多解决问题2，该类算法追求每次修改的高度并发性，减少多副本之间修改的关联性，以获得更好的并发性能。例如最终一致性，无所谓每次用户修改后的多副本的一致性及格过，只要求在单调的时间方向上，数据最终保持一致，如此获得了修改极大的并发性能。
在强一致性的算法中，强调单次修改后结果的一致，需要保证了对问题1和问题2要求的实现，牺牲了并发性能。本文是讨论对解决问题1实现算法，这些算法往往在强一致性要求的应用中使用。
解决问题1的方法，通常有两阶段提交算法、采用分布式锁服务和采用乐观锁原理实现的同步方式,下面分别介绍这几种算法的实现原理。

两阶段提交算法

在两阶段提交协议中，系统一般包含两类机器（或节点）：一类为协调者（coordinator），通常一个系统中只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成，在正常的执行下，这两个阶段的执行过程如下所述：
阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）。
在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
阶段2：提交阶段（commit phase）。
在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。
举个例子：A组织B、C和D三个人去爬长城：如果所有人都同意去爬长城，那么活动将举行；如果有一人不同意去爬长城，那么活动将取消。用2PC算法解决该问题的过程如下：
首先A将成为该活动的协调者，B、C和D将成为该活动的参与者。
阶段1：A发邮件给B、C和D，提出下周三去爬山，问是否同意。那么此时A需要等待B、C和D的邮件。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排，则发邮件告诉A它们同意下周三去爬长城。由于某种原因，D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候，D发现了A的邮件，然后查看日程安排，发现周三当天已经有别的安排，那么D回复A说活动取消吧。
阶段2：此时A收到了所有活动参与者的邮件，并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D，下周三爬长城活动取消。此时B、C回复A“太可惜了”，D回复A“不好意思”。至此该事务终止。
两阶段提交算法在分布式系统结合，可实现单用户对文件（对象）多个副本的修改，多副本数据的同步。其结合的原理如下：
1、客户端（协调者）向所有的数据副本的存储主机（参与者）发送：修改具体的文件名、偏移量、数据和长度信息，请求修改数据，该消息是1阶段的请求消息。
2、存储主机接收到请求后，备份修改前的数据以备回滚，修改文件数据后，向客户端回应修改成功的消息。 如果存储主机由于某些原因（磁盘损坏、空间不足等）不能修改数据，回应修改失败的消息。
3、客户端接收发送出去的每一个消息回应，如果存储主机全部回应都修改成功，向每存储主机发送确认修改的提交消息；如果存在存储主机回应修改失败，或者超时未回应，客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。
4、存储主机接收到客户端的提交消息，如果是确认修改，则直接回应该提交OK消息；如果是取消修改，则将修改数据还原为修改前，然后回应取消修改OK的消息。
5、 客户端接收全部存储主机的回应，整个操作成功。
在该过程中可能存在通信失败，例如网络中断、主机宕机等诸多的原因，对于未在算法中定义的其它异常，都认为是提交失败，都需要回滚，这是该算法基于确定的通信回复实现的，在参与者的确定回复（无论是回复失败还是回复成功）之上执行逻辑处理，符合确定性的条件当然能够获得确定性的结果哲学原理。

分布式锁服务

分布式锁是对数据被外界修改持保守态度，在整个数据处理过程中将数据处于锁定状态，在用户修改数据的同时，其它用户不允许修改。
采用分布式锁服务实现数据一致性，是在操作目标之前先获取操作许可，然后再执行操作，如果其他用户同时尝试操作该目标将被阻止，直到前一个用户释放许可后，其他用户才能够操作目标。分析这个过程，如果只有一个用户操作目标，没有多个用户并发冲突，也申请了操作许可，造成了由于申请操作许可所带来的资源使用消耗，浪费网络通信和增加了延时。
采用分布式锁实现多副本内容修改的一致性问题， 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致， 可以对整个文件修改设置一把锁，修改时申请锁，修改这个文件的多个副本，确保多个副本修改的一致，修改完成后释放锁；也可以对文件分段，或者是文件中的单个字节设置锁， 实现更细颗粒度的锁操作，减少冲突。
常用的锁实现算法有Lamport bakery algorithm （俗称面包店算法）， 还有Paxos算法。下面对其原理做简单概述。

Lamport面包店算法

是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport（英语：Leslie Lamport）发明。
Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。
把该算法原理与分布式系统相结合，即可实现分步锁。

Paxos算法

该算法比较热门，参见WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。节点通信存在两种模型：共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby，而Chubby使用Paxos算法来保证备份的一致性。

采用乐观锁原理实现的同步

我们举个例子说明该算法的实现原理。如一个金融系统，当某个操作员读取用户的数据，并在读出的用户数据的基础上进行修改时（如更改用户帐户余额），如果采用前面的分布式锁服务机制，也就意味着整个操作过程中（从操作员读出数据、开始修改直至提交修改结果的全过程，甚至还包括操作员中途去煮咖啡的时间），数据库记录始终处于加锁状态，可以想见，如果面对几百上千个并发，这样的情况将导致怎样的后果。
乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ Version）记录机制实现。何谓数据版本？即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
对于上面修改用户帐户信息的例子而言，假设数据库中帐户信息表中有一个 version 字段，当前值为 1 ；而当前帐户余额字段（ balance ）为 $100 。
操作员 A 此时将其读出（version=1 ），并从其帐户余额中扣除 $50（$100-$50 ）。
在操作员 A 操作的过程中，操作员B也读入此用户信息（ version=1 ），并从其帐户余额中扣除 $20 （ $100-$20 ）。
操作员 A 完成了修改工作，将数据版本号加一（ version=2 ），连同帐户扣除后余额（ balance=$50 ），提交至数据库更新，此时由于提交数据版本大于数据库记录当前版本，数据被更新，数据库记录 version 更新为 2 。
操作员 B 完成了操作，也将版本号加一（ version=2 ）试图向数据库提交数据（ balance=$80 ），但此时比对数据库记录版本时发现，操作员 B 提交的数据版本号为 2 ，数据库记录当前版本也为 2 ，不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略，因此，操作员 B 的提交被驳回。这样，就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员A 的操作结果的可能。
乐观锁机制与分布式系统相结合上， 我整理了伪代码如下：
obj 操作的目标
vlaue 修改的值
atom_update_ver 每个目标上的版本，每次修改该值递增
set( obj, value)
{
//从每个节点上取出修改前的对象版本
get original_ver = obj.atom_update_ver from each node;
//将值赋到每个节点的obj目标
set obj = value from each node;
//条件修改每个节点的obj版本，目标版本加一
//比较和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功递归修改

该算法未考虑节点下线、失效等问题，在后续我将分析采用乐观锁原理实现一致性算法，解决问题2、节点失效、通信失败等问题。

㈥ process variables是什么意思

process variables
网络 过程变量; 工艺的变量集合; 过程参数; 工艺参数; 制程变数;
[例句]A universal method of data reconciliation based on classifying all processvariables by matrix decomposition is proposed.
基于矩阵分解方法对过程变量进行分类，提出了一种广泛适用的数据协调算法。