系列文章目錄

第一章、為什么要并行計算?

為什么要并行計算？

為什么要關心并行，單處理器已經足夠快了嗎？

為什么不研制更快的單處理器系統，為什么要研制并行系統，為什么研制多處理器系統？

為什么不能撰寫程式，將串行程式自動轉換成可以充分使用多處理器的的并行程式？

1.1 為什么需要不斷提升的性能

??我們現在所需要考慮的問題復雜性增加，例如：氣候模擬，蛋白質折疊，藥物發現，能源研究，資料分析等問題，需要更加強大的計算能力，普通的串行計算過于緩慢，

1.2 為什么需要構建并行系統

??單處理器性能大幅度提升到主要原因之一是日益增長的集成電路的晶體管密度，隨著尺寸的減小，處理器主頻增加，能夠提供更高的性能，但是卻導致了能耗增加 ，大量能源以熱能形式散失，而處理器等電子元件作業環境的溫度越高，其不可靠性會增加，但是當前空氣冷卻已經達到了極限，

??所以如果要構造更快、更加復雜的單處理器，不如防止在一個芯片上放置多個簡單的處理器，這稱作多核處理器，

約定：本文中 核(core) 與 處理器(processer/CPU) 代表同一意思，

1.3 為什么要撰寫并行程式

1.3.1 簡介

??為了達到充分利用多核處理器，使得程式更快的運行，渲染的影像更加逼真，需要將串行程式改寫為并行程式，以提高運行速度和處理器的利用率，串行程式同一時間實際上只能使用一個CPU，無法發揮多核處理器對于程式速度的提升效果，所以我們不能簡單地撰寫串行程式，我們應該撰寫并行程式發掘多核處理器的潛能，

??對于一個串行程式：除非事先定義好的高效的全域演算法，編譯器很難發現一個高效的方法充分利用多核處理器，所以我們需要撰寫程式，對于某一串行結構，將其進行 并行化 ，但是當程式復雜性增加，這一改寫的程序會更加的復雜，追求高效的并行化將變得更加困難，

1.3.2 實體

??計算n個數的值然后進行累加求和，串行程式代碼：

sum = 0;
for(int i=0; i<n; i++)
{
	x = Compute_value(i)
	sum += x;
}

??假設我們有p個核，且 p<<n，那么可以將這n個資料分成p份，每個核只大約需要求n/p個值以及它們的和，

my_sum = 0;
my_first_i = ... ;
my_last_i = ... ;
for(int my_i = my_first_i; my_i < my_last_i; my_i++) 
{
	my_x = Compute_value(my_i)
	my_sum += my_x;
}

??其中my_為當前核的私有變數，

??所有核完成計算之后，可以由0號核將其結果進行匯總：

if(It is core 0) 
{
	sum = my_sum;
	for(each core other than itself) 
	{
		value = recieve_Value_From_Cores();
		sum += value
	}
}
else
	send_MySum();

??或者是采用另一種方式匯總，每兩個核之間，由一個核進行結果相加，然后得到 ? p / 2 ? \lceil p/2 \rceil ?p/2?個結果，反復這一操作，得到最終結果，如下圖：

??顯然，對于p個核，方法2需要進行p次操作，方法1只需要 log ? 2 p \log_2 p log2?p次，
??但是除非我們定義好使用方法2，一般來說，編譯器很難采用方法2而不是方法1，這就是為什么我們需要撰寫并行程式，而不能指望編譯器或者其他軟體完成這一項操作，

1.4 怎樣撰寫并行程式

1.4.1 簡介

??撰寫并行程式，大部分的基本思想都是將任務 分配 給各個核，有兩種廣泛的方法： 任務并行 (task-parallelism) 和 資料并行 (data-parallelism)，任務并行是指將解決問題的各個任務分配到各個核上執行，每個核執行的操作不同；資料并行是將解決問題所需要處理的資料分配給各個核，每個核執行的操作大致一致，

??不同的核之間的需要進行的協調包括：

• 通訊：一個或者多個核將自己的部分或全部結果發送給其他的核，
• 負載平衡：即期望每個核分配的作業資料的數目大致相同，
• 同步：大多數系統中，核不會自動同步，而是在自己的空間內部作業，

??目前，功能最強大的并行程式是通過 顯式 并行結構撰寫的，即使用擴展C/C++ 撰寫的，但是這樣的并行程式即便只是在單核處理器上運行，也會遵照并行的要求運行，比較復雜，

1.4.2 根據1.3.2實體講解

??通訊： 可以看到，最終某些核需要將計算結果發送其他核，這就是一種通訊，

??負載平衡： 所有核的作業量大致相等，可以避免由于作業分配不平均導致某些核運行較快，會閑置等待其他核完成作業，

??同步： 假設所有的資料不需要計算，而是從標準輸入stdin中讀入，使用0號核來初始化陣列x，那么我們期望其他的核不會立即開始運行，而是等到0號核完成讀入資料、初始化x陣列之后才開始運行，我們期望有一個同步點，在這個點的時候核會在這里等待，知道所有的核都到達之和才繼續執行，例如：

if(It is core 0)
	for(int i=0; i<n; i++)
		scanf("%d", &x[i]);
Synchronize_core();		//	同步點
Calculate();			//	計算

1.5 學習目標

??學習撰寫顯示并行程式，學習目標如下：

• 學會利用C語言及C原因三個擴展： 訊息傳遞介面 (Message-Passing Interface, MPI)、POSIX執行緒 (POSIX threads, Pthreads)、OpenMP 來撰寫基本的并行程式，

??這三種拓展與并行系統相關，我們關注兩種并行系統，詳細可見第二章：

• 共享記憶體系統 (shared-memory system)：每個核能夠共享訪問計算機記憶體，每一個核都能夠讀寫記憶體所有區域，可以通過檢測更新共享記憶體資料來協調各個核，Pthreads和OpenMP為共享記憶體系統設計，
• 分布式記憶體系統 (distributed-memory system)：每個核擁有自己的私有記憶體，核之間的通訊是顯示的，必須使用類似于網路中發送訊息的機制進行通訊，MPI為分布式記憶體系統設計，

1.6 并發、并行、分布式

??并發計算 (concurrent computing)、并行計算 (parallel computing) 和 分布式計算 (distributed computing) 的主要區別如下：

• 并發計算：一個程式的多個任務在同一個時段內可以 同時執行，
• 并行計算：一個程式通過多個任務 緊密協作 來解決某個問題，
• 分布式計算：一個程式需要與其他程式協作來解決某個問題，

??并行程式和分布式程式都是并發的，某些程式例如多任務作業系統也是并發的，因為即使在單核計算機上，多個任務也能在同一時間段內 同時執行，并行程式和分布式程式沒有明確的分界線，

??并行程式往往在多個核上執行多個任務，這些核在物理空間上更靠近，通過共享記憶體或者是高速網路連接，并行計算核之間的協調比較頻繁，開銷較低，是細粒度的，并且比較可靠，并行計算程序執行時間較短，

??分布式程式更加“松耦合”(loosely coupled)，任務是在多個計算節點上執行的，計算節點相隔較遠且任務是獨立創建的行程完成的，分布式計算核之間的協調不頻繁，粗粒度的，并且不是很可靠，分布式計算程序執行時間較長，