多核計算機的程序設計

　　采用多核處理器芯片構成計算機系統是一個(gè)片內多處理器的并行計算機系統。這種并行計算機系統過(guò)去只出現超級計算中心和集群計算機系統中?，F在，隨著(zhù)處理器芯片進(jìn)入多核時(shí)代，使得千家萬(wàn)戶(hù)的計算機系統都成為多處理器的并行計算機系統。這種并行計算機系統是一種并行進(jìn)程和并行線(xiàn)程的系統，多個(gè)進(jìn)程和線(xiàn)程可以真正地并行運行，而不是像在單處理器系統中那樣輪流地在CPU上運行。但是在多核系統中，原有的單個(gè)程序的運行速度并不能得到提高。要提高單個(gè)程序的運行性能，需要重新設計原有程序，將單個(gè)計算任務(wù)分解成多個(gè)并行的子任務(wù)，讓這些子任務(wù)分別在不同的處理器核上運行。這樣，需要采用不同的程序設計手段。隨著(zhù)多核時(shí)代的到來(lái)，并行程序設計將成為軟件行業(yè)的必備知識和技能。

　　多核與程序設計

　　與單處理器系統不同，運行在多處理器系統中的程序是多線(xiàn)程的程序。這種程序必須是可重入的，即程序代碼能夠被重疊地啟動(dòng)并且同時(shí)運行在多個(gè)上下文中，這些運行上下文構成多個(gè)線(xiàn)程。代碼的可重入意味著(zhù)在多次進(jìn)入同一段代碼的線(xiàn)程之間避免競態(tài)(race condition)現象。競態(tài)現象發(fā)生在對資源的共享訪(fǎng)問(wèn)情況下。當兩個(gè)運行的線(xiàn)程需要訪(fǎng)問(wèn)相同的數據結構或硬件資源時(shí)，兩個(gè)線(xiàn)程會(huì )因為資源的共享而相互干擾。為避免競態(tài)，需要建立起線(xiàn)程間的通信和同步機制。

　　數據競爭出現在兩個(gè)數據相關(guān)的線(xiàn)程之間。這時(shí)，線(xiàn)程的運行結果與線(xiàn)程的運行順序有關(guān)。例如，對于以下兩個(gè)線(xiàn)程：

　　// 線(xiàn)程1
　　t = x;
　　x = t + 1;
　　// 線(xiàn)程2
　　u = x;
　　x = u + 2;

　　兩個(gè)線(xiàn)程的并行運行情況有以下三種可能，導致三種不同的結果，使得x的分別為1、2和3，如表1所示。解決這個(gè)問(wèn)題需要采用同步機制和互斥機制。同步機制是并行系統中保持各并行程序正確運行的必要的控制機制。它用于在并行的線(xiàn)程之間進(jìn)行時(shí)間上的協(xié)調?；コ鈾C制則是實(shí)現同步機制的基礎。在單處理器系統中，這種機制可以建立在存儲器變量的基礎上。在單處理器系統中，線(xiàn)程的訪(fǎng)存操作本身就是一種互斥的機制。而在多核系統中，這種機制需要通過(guò)存儲器一致性機制和現成通信機制來(lái)實(shí)現。

　　并行程序的概念

　　多處理器系統并行程序設計中需要進(jìn)行任務(wù)劃分、數據劃分和數據流劃分。任務(wù)劃分的目的是使得各個(gè)處理器都能分配到平衡的工作負載，從而提高運算的并行性。數據劃分是將數據對象劃分成多個(gè)并行處理的數據子集。數據流劃分是根據數據的處理過(guò)程進(jìn)行劃分，在不同的處理階段進(jìn)行不同的數據劃分。

　　以下用兩個(gè)例子分別介紹在共享存儲器和分布存儲器多處理器系統進(jìn)行上節中對64000個(gè)數據累加的方法。在共享存儲器系統中，假定有8個(gè)處理器以單總線(xiàn)方式連接。在求和運算時(shí)，數據A存儲在集中共享的存儲器中，每個(gè)處理器對共享數據中的劃分成不同子集進(jìn)行訪(fǎng)問(wèn)和累加。設Pn為處理器數，所有處理器通過(guò)分別運行以下程序對子集中的數據進(jìn)行部分和計算：

　　sum[Pn]=0;
　　for(i=8000*Pn;i<8000*(Pn+1);i=i+1)
  　sum[Pn]=sum[Pn]+A[i];  /* sum the assigned areas  */

　　這個(gè)循環(huán)將子集的數據從共享存儲器中取出。然后將數據與部分和相加，形成部分和之后再求得總和。每個(gè)處理器的部分和也存放在共享的存儲器中，用一個(gè)數組sum[]表示這些部分和。

　　求總和的程序段必須在各個(gè)處理器的部分和都計算完成時(shí)才開(kāi)始進(jìn)行，因此需要一種同步機制來(lái)協(xié)調程序的執行時(shí)間。在并行程序中，必須明確規定關(guān)鍵點(diǎn)的同步。對于本例，求總和的程序可以采用synch()函數進(jìn)行同步操作。synch()函數是一個(gè)屏障同步函數，它使得所有處理器中的有關(guān)線(xiàn)程都執行到這一點(diǎn)時(shí)才繼續執行以后的指令，先到達同步點(diǎn)的線(xiàn)程必須等待。即當一個(gè)或部分線(xiàn)程調用這個(gè)函數時(shí)，函數不返回，只有當所有的線(xiàn)程都調用了這個(gè)函數時(shí)，這個(gè)函數才返回，使得所有的線(xiàn)程都可以進(jìn)行下一步的操作。

　　在分布消息傳遞型多處理器系統中，假設有64個(gè)處理器，通過(guò)某種互連網(wǎng)絡(luò )相互連接。進(jìn)行上述求和運算的第一步是進(jìn)行數據劃分，將數據子集分發(fā)到各局部存儲器中，數據子集存儲在各局部存儲器中后成為數組A1。計算步驟是先計算部分和，然后對部分和計算總和，程序為：

　　sum=0;
　　for(i=0;i<1000;i=i+1)     /* loop over each array  */
  　　sum=sum+A1[i];      /* sum the local arrays  */
　　limit=64;
　　half=64;       /* 64 processors in this MIMD  */
　　do {
  　　half=half/2;      /* send vs. receive dividing line  */
  　　if(Pn>=half && Pn<limit) send(Pn%half,sum);
  　　if(Pn<half) sum=sum+receive();
  　　limit=half;      /* upper limit of senders  */
　　} while (half>1);      /* exit with final sum  */

　　該程序同時(shí)運行在多個(gè)進(jìn)程或處理器中，因為都是在不同的地址空間訪(fǎng)問(wèn)數據，通過(guò)消息發(fā)送操作傳遞數據。程序的前三行計算部分和，后七行對部分和進(jìn)行求和。為了匯集各個(gè)進(jìn)程的部分和，這里程序將所有的處理器分成發(fā)送方和接收方，編譯程序需要將send函數轉換成對發(fā)送消息的庫函數調用，將receive函數轉換成對接受消息的庫函數調用。

　　并行程序的實(shí)現

　　并行程序中，任務(wù)的劃分可以由程序員完成，也可以由編譯程序完成。一般而言，實(shí)現并行程序設計的方法有3種：

　　1. 庫函數。庫函數方法在串行程序的標準庫的基礎上增加新的支持并行操作的函數。如MPI的消息傳遞庫和POSIX的Pthread多線(xiàn)程庫。庫函數方法比較容易實(shí)現，不需要改變編譯程序。但是程序中的并行性問(wèn)題沒(méi)有經(jīng)過(guò)編譯程序的檢查、分析、優(yōu)化。程序設計的難度較大，容易出現錯誤。

　　2. 新的語(yǔ)言構造。在原有的程序設計語(yǔ)言中增加新的構造語(yǔ)句，以表達并行的操作。在對并行構造語(yǔ)句進(jìn)行分析的時(shí)候，編譯程序可以進(jìn)行檢查，發(fā)現并行運行中存在的問(wèn)題和錯誤。但是這種方法需要采用新的編譯程序，并且增加了編譯程序的復雜性。

　　3. 編譯指導。在原有的語(yǔ)言中增加表達并行運算的編譯指導語(yǔ)句。編譯指導語(yǔ)句能夠被并行編譯程序識別，串行編譯程序則忽略這些語(yǔ)句。并行編譯程序跟據這些指導語(yǔ)句將相關(guān)代碼轉換成在并行計算機中運行的代碼。這種方法的例子如OpenMP。這種方法的特點(diǎn)是介于上述兩種方法之間。

　　多線(xiàn)程的編程需要利用操作系統或者軟件開(kāi)發(fā)環(huán)境提供的庫函數實(shí)現線(xiàn)程操作，線(xiàn)程操作函數包括線(xiàn)程的創(chuàng )建和消除、線(xiàn)程的啟動(dòng)運行和終止運行、線(xiàn)程同步機制的建立和刪除、線(xiàn)程互斥機制的建立和刪除、臨界區機制的建立和刪除等。最常見(jiàn)的創(chuàng )建新進(jìn)程或者新線(xiàn)程的機制是分叉和匯集(fork-join)，調用fork函數創(chuàng )建一個(gè)新的進(jìn)程或線(xiàn)程并制定進(jìn)程或線(xiàn)程的執行入口，調用join函數則可以結束新進(jìn)程或新線(xiàn)程的執行。在并行線(xiàn)程的程序設計中，程序員需要安排線(xiàn)程的創(chuàng )建、線(xiàn)程的同步和線(xiàn)程間的通信等，需要考慮到同一段代碼將在多個(gè)線(xiàn)程中同時(shí)運行而不能相互影響。因此，在采用庫函數方式下，多線(xiàn)程程序設計是對程序員的一個(gè)挑戰。

　　一般情況下，在消息傳遞型多處理器系統中，每個(gè)處理器執行的是各不相同的程序。每個(gè)結點(diǎn)上運行的進(jìn)程或線(xiàn)程的程序代碼都要由程序員分別編寫(xiě)，進(jìn)程和線(xiàn)程之間的通信通過(guò)MPI消息傳遞函數庫實(shí)現。程序員需要安排好每個(gè)結點(diǎn)的程序中消息的發(fā)送和對應的接收函數的調用，否則就會(huì )造成處理器間的等待，甚至死機。因此程序設計的工作量很大，而且程序的調試工作十分復雜。

　　多線(xiàn)程的并行運行可以在單個(gè)處理器上進(jìn)行，形成軟件多線(xiàn)程；也可以在支持多線(xiàn)程的處理器核、多個(gè)處理器核或者多個(gè)處理器芯片上運行，形成硬件多線(xiàn)程。多線(xiàn)程的運行情況可以用線(xiàn)程運行狀態(tài)時(shí)空圖來(lái)表示。圖1是較宏觀(guān)的線(xiàn)程時(shí)空圖的一個(gè)例子。圖中用不同的灰度的條形圖表示線(xiàn)程所處的不同狀態(tài)。其中，線(xiàn)程通信時(shí)間包括線(xiàn)程等待鎖的時(shí)間、同步操作花費的時(shí)間和消息發(fā)送與接收的時(shí)間。在軟件多線(xiàn)程方式下，各個(gè)線(xiàn)程輪流地使用處理器核資源。這一點(diǎn)在線(xiàn)程運行狀態(tài)時(shí)空圖上可以清楚地看到，同一個(gè)核上的線(xiàn)程運行的狀態(tài)相互不會(huì )出現重疊的情況，線(xiàn)程之間的通信也不是通過(guò)互連網(wǎng)絡(luò )直接進(jìn)行的，而是通過(guò)緩存空間進(jìn)行。在硬件多線(xiàn)程中，運行在多個(gè)邏輯處理器上的多線(xiàn)程具有不同的硬件資源，構成真正的并行運行方式。

　　OpenMP與多核程序設計

　　OpenMP標準在1997年形成，作為編寫(xiě)可移植的多線(xiàn)程應用程序的API。OpenMP是對基本語(yǔ)言的擴展，標準內容可以從www.openmp.org上獲得。OpenMP適用于共享存儲器的多處理器系統，線(xiàn)程間通過(guò)共享變量傳遞數據結果。

　　OpenMP的程序設計模型提供了一種與平臺無(wú)關(guān)的編譯指導命令(pragma)、編譯指示符、函數調用和環(huán)境變量，顯式地告訴編譯程序在應用程序如何使用并行性，在哪里使用并行性。它提供了一個(gè)編寫(xiě)可移植的多線(xiàn)程應用程序的API，可以實(shí)現循環(huán)程序的多線(xiàn)程化。許多循環(huán)程序可通過(guò)插入一條pragma變成多線(xiàn)程的，只要相關(guān)性不妨礙程序的并行執行。OpenMP支持多線(xiàn)程間的同步和局部數據變量，它采用分叉和匯集(fork-join)的執行模式建立多線(xiàn)程，使得編譯和運行庫能夠有效地編譯和運行程序，減少線(xiàn)程執行的開(kāi)銷(xiāo)。通過(guò)將實(shí)現細節留給編譯程序和實(shí)時(shí)運行庫，程序員不需要對線(xiàn)程的創(chuàng )建和刪除進(jìn)行編程，可以將精力集中于確定哪些循環(huán)程序段需要并行化，以及如何測試并行線(xiàn)程的性能。程序員不需要對線(xiàn)程的同步操作進(jìn)行詳細編程，也不需要在程序中增加大量的代碼來(lái)創(chuàng )建、初始化、管理和終止線(xiàn)程以實(shí)現并行性。用戶(hù)對串行程序添加編譯指導命令的過(guò)程就類(lèi)似于進(jìn)行顯式并行程序設計。

　　OpenMP可以對循環(huán)程序進(jìn)行按循環(huán)迭代的任務(wù)劃分，創(chuàng )建多個(gè)線(xiàn)程，每個(gè)線(xiàn)程完成若干個(gè)循環(huán)迭代的計算子任務(wù)。例如，以下循環(huán)程序是加入了OpenMP編譯指導的程序：

   #pragma omp parallel for
   for (i=0; i<MAX; i++)
   A[i] = c*A[i] + B[i];

　　其中，pragma表示編譯指導命令，表示這是一條編譯指令；omp表示它是OpenMP的編譯指令，采用OpenMP的規范；parallel表示對下面一條語(yǔ)句進(jìn)行并行化，表示多線(xiàn)程并行代碼區域的開(kāi)始；for表示對for循環(huán)語(yǔ)句進(jìn)行多線(xiàn)程分解。這樣，這段程序將被生成多個(gè)線(xiàn)程的代碼。每個(gè)線(xiàn)程完成循環(huán)中的一個(gè)迭代。對于多重循環(huán)，OpenMP只能將最外層的循環(huán)分解成并行多線(xiàn)程，OpenMP的循環(huán)程序分解不能嵌套進(jìn)行。

　　在大的應用程序中，關(guān)鍵的循環(huán)體中常常有遞歸操作。循環(huán)程序中最常見(jiàn)的相關(guān)性是遞歸相關(guān)性。為此，OpenMP提供了一種遞歸(reduction)子句，它有效地結合一些變量的算術(shù)遞歸運算對循環(huán)中的變量進(jìn)行計算。對于存在遞歸相關(guān)性的情況，可以采用遞歸的編譯指令reduction。例如，對于以下求和的遞歸循環(huán)程序：

　　sum = 0;
　　for (i=0; i < 100; i++)
　　{
　　sum += array[i];
　　}
　　如果分解成多個(gè)線(xiàn)程的話(huà)，sum變量就是線(xiàn)程之間的共享變量?？梢约尤脒f歸的OpenMP編譯指令，變成：
　　sum = 0;
　　#pragma omp parallel for reduction(+;sum)
　　for (i=0; i < 100; i++)
　　{
　　sum += array[i];
　　}
　　這時(shí)，OpenMP能夠處理各個(gè)線(xiàn)程對共享變量的訪(fǎng)問(wèn)互斥性，不需要應用程序員操心。

　　在編寫(xiě)多線(xiàn)程程序時(shí)，理解哪些數據是共享的、哪些數據是私有的成為一個(gè)極其重要的問(wèn)題。OpenMP將這種區別通過(guò)一套子句呈現給程序員，例如shared、private和default。OpenMP還可以有條件地進(jìn)行并行執行，方法是使用if子句，該子句可以被加到任何并行結構上。如下面的例子中，在循環(huán)次數大于16時(shí)才啟動(dòng)并行線(xiàn)程，以避免多線(xiàn)程帶來(lái)的開(kāi)銷(xiāo)：

　　#pragma omp parallel for if(n>=16)
　　for ( k = 0; k < n; k++ ) fn2(k);

　　一個(gè)循環(huán)程序可以分解成大量的線(xiàn)程，將這些線(xiàn)程分配給處理器時(shí)需要考慮各處理器的負載平衡，使得所有的處理器差不多同時(shí)完成各自的線(xiàn)程，良好的負載平衡可以獲得最佳的并行處理性能，程序中必須進(jìn)行有效的循環(huán)程序的線(xiàn)程調度和劃分。OpenMP能夠自動(dòng)根據運行的環(huán)境確定最佳線(xiàn)程的數量，以實(shí)現使用任意個(gè)數線(xiàn)程都能具有良好性能的程序。因此，OpenMP是一個(gè)容易入門(mén)的多線(xiàn)程程序設計手段。

　　并行程序軟件工具

　　并行程序設計環(huán)境包括并行程序調試器。并行程序調試器應當能夠通過(guò)對程序代碼的分析發(fā)現程序中問(wèn)題，應當能夠快速準確地定為這些問(wèn)題。對并行程序的分析包括數據相關(guān)性分析、鎖的分析等，分析出并行程序中的數據競爭現象和死鎖現象等程序員難以看出的問(wèn)題。集群系統的調試器是一種能夠在跨平臺、異構開(kāi)發(fā)環(huán)境中的使用的并行程序開(kāi)發(fā)工具。

　　并行程序的優(yōu)化包括分析程序中各個(gè)函數之間的調用關(guān)系，從而分析程序中的關(guān)鍵調用路徑；分析程序中的熱點(diǎn)，即執行時(shí)間最長(cháng)地函數；分析線(xiàn)程的負載平衡情況等。多線(xiàn)程的程序中包含多個(gè)執行流，這些執行流在同步點(diǎn)上是相互相關(guān)的。關(guān)鍵路徑是其中執行時(shí)間最長(cháng)的執行路徑。例如，對于圖2(a)所示的線(xiàn)程執行流，在時(shí)間軸上的關(guān)鍵路徑的例子如圖2(b)所示，其中關(guān)鍵路徑用特粗線(xiàn)表示，中粗線(xiàn)表示非關(guān)鍵路徑上執行的線(xiàn)程，細線(xiàn)表示空閑的線(xiàn)程。良好的并行程序設計環(huán)境應當能夠分析出這種關(guān)鍵路徑，從而為程序減少程序的總體執行時(shí)間提供幫助。在圖3示的線(xiàn)程流程圖上，線(xiàn)程1是貫穿整個(gè)執行流程的線(xiàn)程，成為主線(xiàn)程。其余線(xiàn)程是在需要并行執行的期間建立的線(xiàn)程，成為子線(xiàn)程。

　　分析線(xiàn)程的運行狀態(tài)對于優(yōu)化多線(xiàn)程程序設計十分重要，這種分析有助于程序員了解哪些程序段是影響整個(gè)程序運行時(shí)間的關(guān)鍵。從線(xiàn)程之間關(guān)系的角度，可以將線(xiàn)程的運行狀態(tài)分成以下4種：

　　·巡航狀態(tài)。這時(shí)線(xiàn)程處于獨立的執行狀態(tài)，保持高速運行，線(xiàn)程的運行不受其他線(xiàn)程的影響，也不影響其他線(xiàn)程的運行。

　　·開(kāi)銷(xiāo)狀態(tài)。這是線(xiàn)程操作的開(kāi)銷(xiāo)，如線(xiàn)程的創(chuàng )建、關(guān)閉等。

　　·阻塞狀態(tài)。這時(shí)線(xiàn)程正在等待外部事件，如同步和通信的等待。

　　·影響狀態(tài)。這時(shí)線(xiàn)程處于執行狀態(tài)，它阻礙了其他線(xiàn)程的執行，其他線(xiàn)程正在等待該線(xiàn)程。

　　線(xiàn)程的并行化狀況反映系統中創(chuàng )建的線(xiàn)程數量，可以分成空閑(idel)、串行(serial)、偏少(under-subscribed)、并行(parallel)和偏多(oversubscribed)幾種情況。程序員在調試程序中去分析這種線(xiàn)程數量狀況是一件煩瑣的事情，通常借助于并行程序調試工具。

　　支持這種線(xiàn)程調試和優(yōu)化軟件工具如Intel的Vtune。Vtune是一個(gè)性能測試工具軟件，能夠從程序的試運行中收集系統性能數據，顯示出性能數據的時(shí)空圖，包括顯示函數調用關(guān)系圖和程序中的熱點(diǎn)。通過(guò)這個(gè)軟件工具，可以對各種計算機系統的軟件性能進(jìn)行分析測試，包括各種采用Intel系統結構的嵌入式系統和多核的桌上型計算機系統，從而對并行程序進(jìn)行調試和優(yōu)化。該軟件具有Windows版本和Red Hat Linux版本。

　　Vtune使用高級性能分析技術(shù)查找性能瓶頸，能夠提供程序流程的圖形化視圖，以幫開(kāi)發(fā)人員快速確定關(guān)鍵函數和調用順序并獲得程序執行情況的高級別算法視圖。Vtune能夠對程序的運行中進(jìn)行實(shí)時(shí)采樣，經(jīng)過(guò)分析后顯示出線(xiàn)程的關(guān)鍵路徑(critical path view)，可以在線(xiàn)程時(shí)空圖上標出線(xiàn)程的運行狀態(tài)(timeline view)，可以統計出線(xiàn)程在各種狀態(tài)下所經(jīng)歷的時(shí)間比例(profile view)，還可以分析出線(xiàn)程并行的狀況以及時(shí)間比例(thread view)。調用關(guān)系圖中清晰地顯示出程序的流程，包括子程序調用關(guān)系以及程序的關(guān)鍵路徑。

　　Vtune的分析功能包括熱點(diǎn)分析。所謂熱點(diǎn)是指系統中發(fā)生大量活動(dòng)的位置，如cache失效、分支預測失效、流水線(xiàn)停頓等。在Vtune中使用“計數器監視器”可以在運行時(shí)跟蹤系統活動(dòng)與資源消耗情況，幫助快速確定系統層面的性能問(wèn)題。