集群计算和室内定位算法

⑴ [高性能计算的三大研究领域]高性能计算领域的研究内容

科学计算、海量信息处理与检索以及正在普及的多核个人计算机是高性能计算的主要研究领域，由于领域的不同，对于高性能计算各自都有不同的研究重点。 美国宇航局(NASA)是超级计算机最大的用户之一

从起源来看，计算机系统的原始需求来自军事，如第一台计算机ENIAC是美国军队为了计算弹道而投资研制的。在随后的30年中，计大逗算机主要应用于与国家安全相关的领域，如核武器设计、密码破译等。到20世纪70年代末，高性能计算机开始应用于石油工业、汽车工业等资本密集型工业。随后，高性能计算机开始广泛进入各个行业，协助进行产品设计、用户分析等等。如医药公司使用高性能计算机辅助进行药物设计，可以大大节省新药的研发开支; 超市使用高性能计算机分析用户消费模式，以推出恰当促销措施等等。在这些领域，更高的计算性能就意味着在产品和服务方面的竞争优势。在科学研究领域，数值模拟方法成为现代科学方法的重要组成部分，这里更高的计算性能就意味着更快的科学发现速度。目前，高性能计算技术已成为促进科技创新和经济发展的重要手段，是一个国家综合国力的重要组成部分。本文将就高性能的几个最重要的应用领域进行介绍。
用高性能计算机解决科学挑战
许多重要的科学问题非常复杂，需要功能非常强大的计算机来进行数值模拟，这些问题被视作科学上的重大挑战，可以分为如下几类:
1. 量子化学、统计力学和相对论物理学;
搜纯2. 宇宙学和天体物理学;
3. 计算流体力学和湍流;
4. 材料设计和超导;
5. 生物学、制药研究、基因组序列分析、基因工程、蛋白质折叠、酶活动和细胞建模;
6. 药物、人类骨骼和器官建模;
7. 全球天气和环境建模。
这些重大世仿咐挑战问题大多可以看作传统的高性能计算应用的延伸，其特点是: 大部分是浮点密集型应用程序，并行算法要求多个并行进程之间进行较为频繁的通信和同步，而非简单的多个计算用例之间的并行，因此无法使用多台规模较小的系统来替代一台大规模系统。
这些重大挑战问题对计算能力的需求远远超出了现有的高性能计算机的性能。以量子化学计算为例，需要20T～100Tflops的持续计算能力才能够对目前进行的实际实验结果进行预测。在核聚变研究领域，需要20Tflops的持续计算能力才能够进行全规模的系统模拟。蛋白质折叠的计算需要1Tflops的持续计算速度。另一方面，重大挑战问题对数据的存储也提出了更高的要求，以计算生物学为例，进行蛋白质分析时需要使用的一台质谱仪每天就可以产生100GB的数据，50台质谱仪1天就可以产生5TB的数据。
目前，世界上最快IBM BlueGene/L的处理器个数为131072个，Linpack速度为280.6TFlops，达到了其峰值速度的76.5%（2005年11月数据）。但一般并行算法要比Linpack的通信更加频繁，访存局部性也没有Linpack好，这使得其并行效率相当低，通常仅能达到系统峰值速度的10％，甚至更低。为了能够有效地解决上述重大挑战性的问题，需要研制千万亿次高性能计算机系统，这就需要攻克系统结构、软件工具和并行算法等多方面的难关:

1. 能耗控制
随着现代处理器频率的增加，其功率也大幅度增加，最新处理器的功耗已经超过100W。这使得高性能计算系统本身的耗电问题已经十分严重。同时由于系统散发的大量热量，必须在机房中采用大功率的空调系统才能保持系统机房的正常温度。这两方面的因素造成系统的整体电能消耗非常巨大，维护成本很高。分析结果表明，未来系统主要的维护成本将来自系统的电能消耗。在研制千万亿次高性能计算机系统时，必须重视系统的能耗问题。
目前有几种方法来处理系统能耗问题，一是给处理器设定较低的工作电压，通过并行性来获得高性能，例如BlueGene/L处理器的工作频率仅有700Mhz，因此单个内核的处理能力远远低于其他高频率的处理器。但BlueGene/L通过大量的处理器来弥补单个处理器能力的不足，达到了较高的整体系统性能，并获得了优化的性能/能耗比。另一种方法是通过软件和硬件传感器确定和预测需要使用的部件和不需要使用的部件，然后将不需要立即使用的部分通过某种措施，如降低频率或完全关闭来减少其耗电量，从而达到降低整个系统功耗的目的。这方面的工作根据控制的粒度不同可分为芯片级、主板/BIOS级以及结点级。

2. 高性能计算软件与算法
大规模并行处理硬件系统仅仅为高性能计算提供了一个平台，真正的功能还要通过高性能计算软件来完成。高性能计算软件与算法的主要工作可以分为3类:
（1） 提出具有较低理论复杂度或较好实际性能的串行算法
尽管可以通过并行计算来加快运算的速度，但并行处理往往需要较大的软件开发成本和硬件成本，因此在进行并行算法的开发之前，必须考察是否存在可以解决问题的更好串行算法。以整数排序问题为例，使用并行的冒泡排序算法，其效果还不如使用串行的快速排序算法。因此，高效的串行算法研究是高性能算法研究的重要课题。着名的算法包括线性规划问题的单纯型法、FFT、快速排序、矩阵特征值的QR算法、快速多极算法等。近年来在算法方面的突破使印度学者在素数判定问题上提出了多项式复杂度算法。
（2） 优化现有算法
算法只提供了理论上的性能，要在实际系统上获得高性能，必须对算法的实现进行优化。现代处理器大多使用多级Cache来隐藏访存延迟，因此必须根据目标系统的Cache参数来优化算法的访存行为。此外，许多处理器还提供了SIMD指令，合理使用这些指令可以达到较高的性能。许多优化的数学库，如ATLAS、Intel公司的MKL等已经为不同的体系结构，特别是Cache配置进行了特别优化，可以达到较高的执行效率，为优化算法实现提供了很好的帮助。
(3) 并行算法与并行应用的开发
并行算法的研究与串行算法有联系也有区别。优秀的串行算法并不一定适合并行化，某些时候在串行算法中并非最优的算法在并行实现时却能体现出较大的优势。对于千万亿次计算机而言，其处理器（核）个数在10万以上，并行应用的并行度需要达到数万个并行进程才能有效地利用千万亿次计算机。并行算法的三个主要优化目标是: 通信优化、负载平衡以及最大化并行区。通信优化的目标是尽量减少通信次数和通信量，减少由于处理器之间通信带宽限制引起的性能下降。在大规模并行程序中，负载平衡问题也非常突出，少数负载不平衡的任务会使得整体性能急剧下降。同样的，根据Amdahl定律，应用加速比的上限是串行区所占比例的倒数，即应用中1％的串行区域就会使得整个应用程序的加速比不可能超过100。因此，要在数万个并行进程的情况下取得理想的加速比给并行算法的开发提出了很大的挑战。

3. 系统可靠性与可管理性
随着系统内结点个数的增加，系统失效的可能性也随着增大。并行程序的特点是只要有一个并行进程失败，整个并行程序都执行不成功。对可靠性问题的处理方法之一是设法提高系统的稳定性，这包括硬件系统可靠性和软件系统的可靠性。但目前公认的结论是: 大规模系统的故障是在设计时必须考虑的前提条件，而并非可以通过技术手段加以解决的问题。因此，必须考虑如何在系统结点出现故障的情况下仍然能够保证系统服务质量不发生显着下降。
故障监测技术和动态系统重构技术可以用来减少或消除系统失效对应用的影响，即尽快隔离出现问题的结点，使得用户可以使用状态正常的结点进行计算。与系统动态重构技术类似的技术还有系统动态划分技术，主要用于向不同的用户提供相互独立的结点集，使得整个系统的管理和使用更加有效和安全。
但是上述技术仅能解决系统对新的应用的服务质量问题，无法保证已经执行的应用在某个计算结点出现问题后的处理。某些并行应用，如石油数据处理需要连续运行几十天的时间，一旦某个结点出现错误，会使得前面的计算前功尽弃，需要从头开始计算。并行检查点技术主要提供应用级的容错，即能够自动地定期记录并行程序的状态（称作检查点），在计算过程中某个结点发生失效后，可以从所记录的并行程序检查点恢复执行，避免了重新执行整个程序。

高性能计算与海量信息处理

人类所产生的信息量以指数速度增长，如何存储、检索和利用这些信息为信息技术提出了重要挑战。从20世纪90年代开始，互联网的飞速发展给信息的传播与服务提供了新的机遇。传统的信息服务系统以数据库为中心，典型应用是OLTP（事务联机处理）。而以Google为代表的海量信息检索与处理服务是另一类重要应用，以Google集群系统为代表的系统体现了高性能计算系统的另一个发展方向。
信息检索与处理服务系统的特点与科学计算非常不同，对处理系统也提出了不同的要求:
1. 信息处理与服务应用需要频繁访问动态的数据结构，包含很多不可预测的分支，使得现有超标量处理器中的许多技术，如分支预测、数据预取、乱序和推测执行等功能无法很好地发挥作用，应用的指令级并行性较差。
2. 大部分信息处理与服务应用具有较好的数据并行性，可以很容易地在分布式系统上执行。以信息检索为例，一个信息检索请求可以被分配到多个服务器上进行并行检索，最后再将搜索结果统一处理返回给用户。这个过程中大多数的访问是只读的数据，并行任务之间的通信非常少，并行效率比较高。
3. 系统的性能指标一般不以单个服务请求的响应时间为量度，而更关注系统整体的吞吐率。以搜索引擎为例，信息服务系统更重视在1分钟内能够完成的用户搜索次数，而对单次搜索在0.5秒内完成还是1秒内完成并不特别敏感。
4. 系统需要很高的可靠性和可维护性。可靠性是对服务而言的，即组成的系统必须能够近乎不间断地为用户提供服务。可维护性是指系统的更换与维修可以简单快捷地完成，新更换的结点可以快捷地加入到系统中。
5. 低成本。这包括系统构建成本和总拥有成本两部分。海量信息处理和服务所需的系统规模极为庞大，Google Cluster在2003年就达到了15000台计算机的规模。如此巨大规模的系统，需要尽可能地降低成本。
为了能够有效满足上述信息处理与服务系统的要求，人们对于如何高效地构建相应的服务系统也展开了研究与实践:
1. 使用副本技术通过软件提供可靠性
在大规模系统中，单个系统结点的失效是不可避免的。现有的通过冗余底层硬件提高系统可靠性的方式，比如冗余电源、RAID技术等，成本较高，性价比较差。相反，在信息服务系统中可以广泛使用软件提供服务级别的可靠性。主要的方法是采用副本，即将服务和数据复制到多个系统结点上，即使单个系统结点的可靠性不是很高，多个副本提供了服务所需的可靠性。另一个使用副本技术的优点在于其提高系统可靠性的同时也提高了系统的性能，即保存副本的多个系统结点可以同时向用户提供服务。
2. 注重系统的性能/价格比
由于信息服务系统应用容易并行的特点，采用大量低端系统组合的方法比使用少量高端系统在性能价格比方面更具有优势（此处所指的低端系统是指1～2个CPU的PC机或入门服务器，高端系统是指大规模处理器服务器，如HP 的Superdom服务器、IBM的P690服务器等）。此外，信息服务系统与用于科学计算的高性能系统面临同样的挑战: 能耗问题。在大规模信息处理与服务系统中，电费成本（包括系统本身耗电和空调系统耗电）将占有总拥有成本的很大一部分。因此，在选用系统时，应选择性能/能耗比较高的系统也是一个重要的原则。
(3) 使用多内核处理器
由于信息服务程序的特点，它更适合使用多个简单内核构成的处理器，这些简单内核仅需要按序执行，并使用较短的流水线。由于信息服务应用的指令级并行度较差，按序执行不会造成太多的性能下降，但可以节省复杂的乱序执行单元电路，从而可以降低功耗。另一方面，较短的流水线可以降低分支预测失效的开销。
并行计算与个人计算机
随着半导体工艺的发展，单个芯片上能够集成的元件个数还将在5～10年内遵循摩尔定律继续以指数级增长。但是当前的芯片散热技术已无法支持芯片频率的进一步提高，而通过提高发射宽度、提高分支预测效率以及数据预取等进一步在体系结构上提高单线程执行速度的方法也逐渐失去了有效性。多内核芯片通过在一个芯片内集成多个处理器内核，采用线程级并行提高处理器性能，已成为微处理器的主要发展趋势。IBM公司在几年前就推出了双内核Power芯片，Intel公司和AMD在2005年推出的双内核芯片更是标志着多内核技术进入了普及阶段。支持更多核心的处理器芯片也正在快速涌现，如Sun公司已经推出了8核的Nigeria芯片，用于面向提高吞吐率的服务器应用; IBM则联合索尼和东芝推出了面向娱乐应用的9内核Cell芯片。Intel公司甚至已经在计划100内核以上的处理器。
多核处理器的出现给计算机的使用带来了新的挑战。随着多内核处理器的普及，成千上万的桌面电脑将成为并行计算机。目前在桌面机上执行的应用程序大多数是单线程程序，无法有效利用多内核处理器提供的能力。如何有效地在个人电脑上利用多个处理器内核成为高性能计算领域一个重要的研究课题，从目前的趋势来看主要有以下几个方向:
1.使用多任务带来的并发性
Intel的 双核ViiV家用电脑是这方面的典型例子。ViiV电脑的典型使用模式是一个人在客厅使用ViiV电脑看电影，另一个在自己的房间里使用同一台电脑玩游戏，两个人使用同一台电脑中的不同处理器内核，从而达到了有效发挥双核能力的目的。但这种依靠多个用户同时使用一台电脑的模式具有很大局限性，因为家庭成员的个数是有限的，对于4内核以上的多内核处理器，这种模式无法提供有效的支持。
2.聚合多内核的能力，加速串行程序的执行速度
计算机科学家们正在研究一种称作推测多线程（TLS: Thread-Level Speculation）的技术，该技术可以自动分析串行程序，推测其中能够并行执行的部分，在多个内核上并行执行。但一旦发现并行执行的部分有冲突，就撤销其中一个冲突线程的执行，执行补偿操作并重新执行该线程。推测多线程技术的优点在于无需用户干预就可以在多内核系统上加速现有单线程程序，其缺点在于对于性能提高的幅度有限,大约在4内核系统上仅能比在单个内核上提高性能30％，而且再增加内核数，其加速比也不会显着增加。因此，这种方式也无法支持更多内核的处理器。
另一种有前途的技术是自动并行化技术。自动并行化技术可以在编译时识别程序中的并行性，并将其转化为多线程并行程序。过去的自动并行化技术主要是面向SMP系统的，但不是很成功，原因是对真实应用程序，自动并行化无法得到满意的加速比。一个程序通过自动并行化在4 CPU的SMP系统上得到20%的加速比是不能令人满意的，因为4 CPU的系统通常价格是单CPU价格的10倍以上，自动并行化无法提供性能价格比上的优势。但是对于多内核系统，如果能够在四内核系统上通过自动并行化得到20％的加速比，应该是比较令人满意的结果，因为这些内核是“免费”提供给用户的，即用户无法用四内核处理器1/4的价格购买一个单内核处理器。因此，多内核处理器在家用电脑上的普及，将大大降低人们对自动并行化效果的期望，使得自动并行化技术重新被接受和应用。
3. 并行化现有的桌面应用
既然采用多内核处理器加速串行应用无法充分利用多内核处理器的能力，那么并行化现有的桌面应用就成为了一个重要选择。这方面的研究主要是分析现有的桌面应用，对有代表性的应用进行手工并行化，这些研究试图回答下面的问题: 哪些桌面应用能够被有效并行化，哪些不能？并行化本身的难度有多大？应如何改进现有的编程模型、编程工具以及系统软件来更好地支持应用的并行化？
研究表明，桌面系统上的大部分应用，如图像处理、3D图形运算、多媒体数据编码与解码、数据与文本挖掘、文本与媒体搜索、游戏与博弈等都可以有效地被并行化，并在多内核系统上得到有效的执行。但是，手工程序并行化的开销仍然很大，并行程序员需要了解并行计算的有关知识，并对计算机体系结构、操作系统、编译原理等有一定了解才能写出有效率的并行程序。并行编程模型与并行编程工具还需要提供更好的支持，以帮助并行程序员开发、调试并行程序。
今天，高性能计算技术已成为整个计算机领域的引领技术。多内核处理器的出现，使得并行计算技术将很快普及到我们的每台计算机，渗入到我们生活的方方面面，这是计算机产业发展史上的一个重大变革，对我国而言是一次难得的机会。在“十一五”期间，我国将进一步加强对高性能计算技术研究的支持，注重引导企业应用高性能计算技术促进产业升级和科技创新，同时更加特别重视高性能计算技术的教育培训工作，在高校的理工专业广泛开设并行程序设计课程，培养更多了解和使用高性能计算技术的人才，在此次变革中实现跨越性的发展。

作者简介
陈文光
清华大学计算机博士，清华大学计算机系副教授，863高性能计算机评测中心副主任。曾任Opportunity International Inc.总工程师。主要研究领域为并行计算的编程模型、并行化编译和并行应用分析。

链接:高性能计算发展趋势
随着应用的需求与计算机技术本身的发展，近年来高性能计算的发展体现出一些新的特点，可以用“大，宽，小”来代表这三个特点:
“大”是指高性能计算系统向更大规模发展，处理器个数可达10万个以上，主要用于解决超大规模的数值模拟问题。
“宽”是指在传统的数值计算之外，高性能计算系统正越来越广泛地应用于信息处理和服务领域，为海量信息的存储与检索以及网络服务提供有效的保证。
“小”是指多内核CPU的出现和普及，将使得今后的每台个人计算机都成为并行计算机，如何有效地利用个人计算机的多个内核是对高性能计算技术提出的新挑战。

⑵ hadoop的maprece常见算法案例有几种

基本MapRece模式

计数与求和
问题陈述:
有许多文档，每个文档都有一些字段组成。需要计算出每个字段在所有文档中的出现次数或者这些字段的其他什么统计值。例如，给定一个log文件，其中的每条记录都包含一个响应时间，需要计算出平均响应时间。
解决方案:
让我们先从简单的例子入手。在下面的代码片段里，Mapper每遇到指定词就把频次记1，Recer一个个遍历这些词的集合然后把他们的频次加和。

1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Recer
7 method Rece(term t, counts [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)

这种方法的缺点显而易见，Mapper提交了太多无意义的计数。它完全可以通过先对每个文档中的词进行计数从而减少传递给Recer的数据量:

1 class Mapper
2 method Map(docid id, doc d)
3 H = new AssociativeArray
4 for all term t in doc d do
5 H{t} = H{t} + 1
6 for all term t in H do
7 Emit(term t, count H{t})

如果要累计计数的的不只是单个文档中的内容，还包括了一个Mapper节点处理的所有文档，那就要用到Combiner了:

1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Combiner
7 method Combine(term t, [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)
12
13 class Recer
14 method Rece(term t, counts [c1, c2,...])
15 sum = 0
16 for all count c in [c1, c2,...] do
17 sum = sum + c
18 Emit(term t, count sum)

应用：Log 分析, 数据查询

整理归类

问题陈述:
有一系列条目，每个条目都有几个属性，要把具有同一属性值的条目都保存在一个文件里，或者把条目按照属性值分组。 最典型的应用是倒排索引。
解决方案：
解决方案很简单。 在 Mapper 中以每个条目的所需属性值作为 key，其本身作为值传递给 Recer。 Recer 取得按照属性值分组的条目，然后可以处理或者保存。如果是在构建倒排索引，那么 每个条目相当于一个词而属性值就是词所在的文档ID。
应用：倒排索引， ETL
过滤 (文本查找)，解析和校验
问题陈述:
假设有很多条记录，需要从其中找出满足某个条件的所有记录，或者将每条记录传换成另外一种形式（转换操作相对于各条记录独立，即对一条记录的操作与其他记录无关）。像文本解析、特定值抽取、格式转换等都属于后一种用例。
解决方案:
非常简单，在Mapper 里逐条进行操作，输出需要的值或转换后的形式。
应用：日志分析，数据查询，ETL，数据校验

分布式任务执行

问题陈述:
大型计算可以分解为多个部分分别进行然后合并各个计算的结果以获得最终结果。
解决方案: 将数据切分成多份作为每个 Mapper 的输入，每个Mapper处理一份数据，执行同样的运算，产生结果，Recer把多个Mapper的结果组合成一个。
案例研究： 数字通信系统模拟
像 WiMAX 这样的数字通信模拟软件通过系统模型来传输大量的随机数据，然后计算传输中的错误几率。 每个 Mapper 处理样本 1/N 的数据，计算出这部分数据的错误率，然后在 Recer 里计算平均错误率。
应用：工程模拟，数字分析，性能测试
排序
问题陈述:
有许多条记录，需要按照某种规则将所有记录排序或是按照顺序来处理记录。
解决方案: 简单排序很好办 – Mappers 将待排序的属性值为键，整条记录为值输出。 不过实际应用中的排序要更加巧妙一点， 这就是它之所以被称为MapRece 核心的原因（“核心”是说排序？因为证明Hadoop计算能力的实验是大数据排序？还是说Hadoop的处理过程中对key排序的环节？）。在实践中，常用组合键来实现二次排序和分组。
MapRece 最初只能够对键排序， 但是也有技术利用可以利用Hadoop 的特性来实现按值排序。想了解的话可以看这篇博客。
按照BigTable的概念，使用 MapRece来对最初数据而非中间数据排序，也即保持数据的有序状态更有好处，必须注意这一点。换句话说，在数据插入时排序一次要比在每次查询数据的时候排序更高效。
应用：ETL，数据分析

非基本 MapRece 模式

迭代消息传递 (图处理)

问题陈述：
假设一个实体网络，实体之间存在着关系。 需要按照与它比邻的其他实体的属性计算出一个状态。这个状态可以表现为它和其它节点之间的距离， 存在特定属性的邻接点的迹象， 邻域密度特征等等。
解决方案：
网络存储为系列节点的结合，每个节点包含有其所有邻接点ID的列表。按照这个概念，MapRece 迭代进行，每次迭代中每个节点都发消息给它的邻接点。邻接点根据接收到的信息更新自己的状态。当满足了某些条件的时候迭代停止，如达到了最大迭代次数（网络半径）或两次连续的迭代几乎没有状态改变。从技术上来看，Mapper 以每个邻接点的ID为键发出信息，所有的信息都会按照接受节点分组，recer 就能够重算各节点的状态然后更新那些状态改变了的节点。下面展示了这个算法：

1 class Mapper
2 method Map(id n, object N)
3 Emit(id n, object N)
4 for all id m in N.OutgoingRelations do
5 Emit(id m, message getMessage(N))
6
7 class Recer
8 method Rece(id m, [s1, s2,...])
9 M = null
10 messages = []
11 for all s in [s1, s2,...] do
12 if IsObject(s) then
13 M = s
14 else // s is a message
15 messages.add(s)
16 M.State = calculateState(messages)
17 Emit(id m, item M)

一个节点的状态可以迅速的沿着网络传全网，那些被感染了的节点又去感染它们的邻居，整个过程就像下面的图示一样：

案例研究： 沿分类树的有效性传递
问题陈述：
这个问题来自于真实的电子商务应用。将各种货物分类，这些类别可以组成一个树形结构，比较大的分类（像男人、女人、儿童）可以再分出小分类（像男裤或女装），直到不能再分为止（像男式蓝色牛仔裤）。这些不能再分的基层类别可以是有效（这个类别包含有货品）或者已无效的（没有属于这个分类的货品）。如果一个分类至少含有一个有效的子分类那么认为这个分类也是有效的。我们需要在已知一些基层分类有效的情况下找出分类树上所有有效的分类。
解决方案：
这个问题可以用上一节提到的框架来解决。我们咋下面定义了名为 getMessage和 calculateState 的方法：

1 class N
2 State in {True = 2, False = 1, null = 0},
3 initialized 1 or 2 for end-of-line categories, 0 otherwise
4 method getMessage(object N)
5 return N.State
6 method calculateState(state s, data [d1, d2,...])
7 return max( [d1, d2,...] )

案例研究：广度优先搜索
问题陈述：需要计算出一个图结构中某一个节点到其它所有节点的距离。
解决方案： Source源节点给所有邻接点发出值为0的信号，邻接点把收到的信号再转发给自己的邻接点，每转发一次就对信号值加1：

1 class N
2 State is distance,
3 initialized 0 for source node, INFINITY for all other nodes
4 method getMessage(N)
5 return N.State + 1
6 method calculateState(state s, data [d1, d2,...])
7 min( [d1, d2,...] )

案例研究：网页排名和 Mapper 端数据聚合
这个算法由Google提出，使用权威的PageRank算法，通过连接到一个网页的其他网页来计算网页的相关性。真实算法是相当复杂的，但是核心思想是权重可以传播，也即通过一个节点的各联接节点的权重的均值来计算节点自身的权重。

1 class N
2 State is PageRank
3 method getMessage(object N)
4 return N.State / N.OutgoingRelations.size()
5 method calculateState(state s, data [d1, d2,...])
6 return ( sum([d1, d2,...]) )

要指出的是上面用一个数值来作为评分实际上是一种简化，在实际情况下，我们需要在Mapper端来进行聚合计算得出这个值。下面的代码片段展示了这个改变后的逻辑 （针对于 PageRank 算法）：

1 class Mapper
2 method Initialize
3 H = new AssociativeArray
4 method Map(id n, object N)
5 p = N.PageRank / N.OutgoingRelations.size()
6 Emit(id n, object N)
7 for all id m in N.OutgoingRelations do
8 H{m} = H{m} + p
9 method Close
10 for all id n in H do
11 Emit(id n, value H{n})
12
13 class Recer
14 method Rece(id m, [s1, s2,...])
15 M = null
16 p = 0
17 for all s in [s1, s2,...] do
18 if IsObject(s) then
19 M = s
20 else
21 p = p + s
22 M.PageRank = p
23 Emit(id m, item M)

应用：图分析，网页索引

值去重 （对唯一项计数）
问题陈述: 记录包含值域F和值域 G，要分别统计相同G值的记录中不同的F值的数目 (相当于按照 G分组).
这个问题可以推而广之应用于分面搜索（某些电子商务网站称之为Narrow Search）
Record 1: F=1, G={a, b}
Record 2: F=2, G={a, d, e}
Record 3: F=1, G={b}
Record 4: F=3, G={a, b}

Result:
a -> 3 // F=1, F=2, F=3
b -> 2 // F=1, F=3
d -> 1 // F=2
e -> 1 // F=2

解决方案 I:
第一种方法是分两个阶段来解决这个问题。第一阶段在Mapper中使用F和G组成一个复合值对，然后在Recer中输出每个值对，目的是为了保证F值的唯一性。在第二阶段，再将值对按照G值来分组计算每组中的条目数。
第一阶段：

1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...]])
3 for all category g in [g1, g2,...]
4 Emit(record [g, f], count 1)
5
6 class Recer
7 method Rece(record [g, f], counts [n1, n2, ...])
8 Emit(record [g, f], null )

第二阶段：

1 class Mapper
2 method Map(record [f, g], null)
3 Emit(value g, count 1)
4
5 class Recer
6 method Rece(value g, counts [n1, n2,...])
7 Emit(value g, sum( [n1, n2,...] ) )

解决方案 II:
第二种方法只需要一次MapRece 即可实现，但扩展性不强。算法很简单-Mapper 输出值和分类，在Recer里为每个值对应的分类去重然后给每个所属的分类计数加1，最后再在Recer结束后将所有计数加和。这种方法适用于只有有限个分类，而且拥有相同F值的记录不是很多的情况。例如网络日志处理和用户分类，用户的总数很多，但是每个用户的事件是有限的，以此分类得到的类别也是有限的。值得一提的是在这种模式下可以在数据传输到Recer之前使用Combiner来去除分类的重复值。

1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...] )
3 for all category g in [g1, g2,...]
4 Emit(value f, category g)
5
6 class Recer
7 method Initialize
8 H = new AssociativeArray : category -> count
9 method Rece(value f, categories [g1, g2,...])
10 [g1', g2',..] = ExcludeDuplicates( [g1, g2,..] )
11 for all category g in [g1', g2',...]
12 H{g} = H{g} + 1
13 method Close
14 for all category g in H do
15 Emit(category g, count H{g})

应用：日志分析，用户计数
互相关
问题陈述：有多个各由若干项构成的组，计算项两两共同出现于一个组中的次数。假如项数是N，那么应该计算N*N。
这种情况常见于文本分析（条目是单词而元组是句子），市场分析（购买了此物的客户还可能购买什么）。如果N*N小到可以容纳于一台机器的内存，实现起来就比较简单了。
配对法
第一种方法是在Mapper中给所有条目配对，然后在Recer中将同一条目对的计数加和。但这种做法也有缺点：
使用 combiners 带来的的好处有限，因为很可能所有项对都是唯一的
不能有效利用内存

1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 for all item j in [i1, i2,...]
5 Emit(pair [i j], count 1)
6
7 class Recer
8 method Rece(pair [i j], counts [c1, c2,...])
9 s = sum([c1, c2,...])
10 Emit(pair[i j], count s)

Stripes Approach（条方法？不知道这个名字怎么理解）
第二种方法是将数据按照pair中的第一项来分组，并维护一个关联数组，数组中存储的是所有关联项的计数。The second approach is to group data by the first item in pair and maintain an associative array (“stripe”) where counters for all adjacent items are accumulated. Recer receives all stripes for leading item i, merges them, and emits the same result as in the Pairs approach.
中间结果的键数量相对较少，因此减少了排序消耗。
可以有效利用 combiners。
可在内存中执行，不过如果没有正确执行的话也会带来问题。
实现起来比较复杂。
一般来说， “stripes” 比 “pairs” 更快

1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 H = new AssociativeArray : item -> counter
5 for all item j in [i1, i2,...]
6 H{j} = H{j} + 1
7 Emit(item i, stripe H)
8
9 class Recer
10 method Rece(item i, stripes [H1, H2,...])
11 H = new AssociativeArray : item -> counter
12 H = merge-sum( [H1, H2,...] )
13 for all item j in H.keys()
14 Emit(pair [i j], H{j})

应用：文本分析，市场分析
参考资料：Lin J. Dyer C. Hirst G. Data Intensive Processing MapRece
用MapRece 表达关系模式
在这部分我们会讨论一下怎么使用MapRece来进行主要的关系操作。
筛选（Selection）

1 class Mapper
2 method Map(rowkey key, tuple t)
3 if t satisfies the predicate
4 Emit(tuple t, null)

投影（Projection）
投影只比筛选稍微复杂一点，在这种情况下我们可以用Recer来消除可能的重复值。

1 class Mapper
2 method Map(rowkey key, tuple t)
3 tuple g = project(t) // extract required fields to tuple g
4 Emit(tuple g, null)
5
6 class Recer

⑶ 集群计算的集群计算(Cluster Computing)

在计算机中，集群（clustering）是使用多个计算机，如典型的个人计算机或UNIX工作站，多个存储设备和记忆冗余的互连线路来组成一个对用户来说单一的、高可用的系统。集群计算（clustering computing）能够被用来实现负载均衡。集群的倡导者提出，对一个企业来说，集群在许多情况下能够达到99.999%的可用性。集群的一个主要思路是，对外接来说，集群就像是一个唯一的系统。
集群的一个常用用途就是在一个高流量的网站中实现负载均衡。一个网页请求被送到“管理者”服务器，然后此服务器决定此请求由几个相同Web服务器中的哪一个进行处理。这种Web Farm（根据配置有时候被这样称呼）将能够提升通信量和处理速度。
集群最早是在20世纪80年代DEC的VMS系统中出现的，IBM的sysplex是与集群接近的大型主机系统。微软、Sun微系统，以及其它主导硬件和软件流的公司提供有集群包，并保证提供可扩展性和可用性。随着通信量和可用性保证的增加，集群的整个部分或局部零件的大小与数量都可以增加。
集群计算还可以被用来进行低廉的并行计算，这些并行计算通常为科学研究或其它需要并行运算的应用服务。一个着名的例子就是裴欧沃夫（Beowulf）计划，它使用一定数量现成的个人计算机组成集群来实现科学应用。