集群計算和室內定位演算法

⑴ [高性能計算的三大研究領域]高性能計算領域的研究內容

科學計算、海量信息處理與檢索以及正在普及的多核個人計算機是高性能計算的主要研究領域，由於領域的不同，對於高性能計算各自都有不同的研究重點。 美國宇航局(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）計劃，它使用一定數量現成的個人計算機組成集群來實現科學應用。