基于Linux數(shù)據(jù)鏈路層的MPI集群通信機(jī)制的設(shè)計(jì)與實(shí)現(xiàn)

在集群計(jì)算系統(tǒng)中，隨著系統(tǒng)規(guī)模的增大，通信效率是影響整個(gè)系統(tǒng)獲得高性能的關(guān)鍵因素之一。而隨著局域網(wǎng)傳輸性能的快速提高，Myrinet、Gigabit Ethernet和Infiniband等千兆位網(wǎng)絡(luò)設(shè)備已被廣泛使用，當(dāng)前影響集群節(jié)點(diǎn)間通信性能的瓶頸已經(jīng)從通信硬件的傳送開銷轉(zhuǎn)移到了通信處理軟件的開銷上，所以采用優(yōu)化的通信協(xié)議是降低通信成本、提高結(jié)點(diǎn)間通信的有效手段。

在當(dāng)前的集群通信應(yīng)用中,普遍采用兩類通信結(jié)構(gòu)，即核心級通信和用戶級通信。但由于它們設(shè)計(jì)的初衷并非是針對集群通信,所以并不適合當(dāng)前集群環(huán)境的特點(diǎn)。為此，本文通過分析這兩類通信結(jié)構(gòu)的特點(diǎn),提出了以核心級通信為基礎(chǔ)，旁路內(nèi)核中IP層及以上協(xié)議層,實(shí)現(xiàn)數(shù)據(jù)鏈路層直接與MPI通道接口層通信的新機(jī)制，并通過實(shí)驗(yàn)驗(yàn)證，為傳統(tǒng)集群的升級改造提供一種新的無連接、無差錯(cuò)控制，開銷小、延時(shí)低的通信機(jī)制。

1 基于數(shù)據(jù)鏈路層的集群通信結(jié)構(gòu)的提出

目前各種通信協(xié)議普遍采用兩種通信結(jié)構(gòu)，即核心級通信和用戶級通信[1]。

1.1 核心級通信

在核心級通信中，操作系統(tǒng)內(nèi)核控制著所有消息傳遞中的發(fā)送與接收處理，并且負(fù)責(zé)它們的緩沖管理和通信協(xié)議的實(shí)現(xiàn)，設(shè)備驅(qū)動(dòng)程序也是通過內(nèi)核來完成所有的硬件支持與協(xié)議軟件處理的任務(wù)，如圖1所示。在通信過程中，系統(tǒng)要經(jīng)過多次內(nèi)核態(tài)與用戶態(tài)之間的數(shù)據(jù)拷貝才能夠?qū)崿F(xiàn)數(shù)據(jù)的傳送。有數(shù)據(jù)表明[2]，一般奔騰處理器的內(nèi)存拷貝速率平均為70 Mb/s，但是由于操作系統(tǒng)在交換頁面時(shí)的 I/O 數(shù)據(jù)傳送都是阻塞操作，若出現(xiàn)缺頁中斷，其時(shí)延將會(huì)更大，所以頻繁的內(nèi)存拷貝操作的開銷將是影響整體性能的瓶頸所在。因此，對于通信效率要求較高的集群計(jì)算系統(tǒng)，核心級通信是不適合的。


1.2 用戶級通信

在用戶級通信中，操作系統(tǒng)內(nèi)核將網(wǎng)絡(luò)接口控制器NIC(Network Interface Controller)的寄存器和存儲器映射到用戶地址空間，允許用戶進(jìn)程旁路操作系統(tǒng)內(nèi)核從直接訪問NIC，直接將數(shù)據(jù)從用戶空間發(fā)送到網(wǎng)絡(luò)中進(jìn)行傳輸。通信事件處理的觸發(fā)采用查詢方式而不是中斷方式，由于旁路操作系統(tǒng)內(nèi)核，使得整個(gè)通信過程省掉了執(zhí)行系統(tǒng)調(diào)用、用戶態(tài)與核心態(tài)之間的數(shù)據(jù)拷貝及用戶與內(nèi)核的上下文切換等軟件上的開銷，進(jìn)而減少對主機(jī)CPU資源的占用,縮短通信操作的關(guān)鍵路徑，實(shí)現(xiàn)通信與計(jì)算的重疊。如圖2所示[3]。

但是，采用用戶級通信協(xié)議時(shí)，通信過程中的所有操作均在用戶空間中進(jìn)行，當(dāng)用戶程序出錯(cuò)或有惡意用戶進(jìn)行破壞時(shí)，系統(tǒng)就很容易被破壞。這是因?yàn)橄到y(tǒng)數(shù)據(jù)結(jié)構(gòu)中不僅包含本進(jìn)程（或并行任務(wù)）及其相關(guān)信息，同時(shí)也包含與本進(jìn)程無關(guān)的其他進(jìn)程（或并行任務(wù)）的相關(guān)信息。若某一用戶（并行任務(wù)）出錯(cuò)或失誤，都將會(huì)影響到其他用戶（并行任務(wù)）的執(zhí)行,因而很難保證系統(tǒng)的安全性和可靠性，也無法保證并行任務(wù)間的相互獨(dú)立性。

1.3 基于數(shù)據(jù)鏈路層通信

為了既能保證系統(tǒng)安全、可靠以及并行任務(wù)間相互獨(dú)立，同時(shí)又能降低通信成本，本文提出了一種以核心級通信為基礎(chǔ)的基于數(shù)據(jù)鏈路層的通信結(jié)構(gòu)，即在操作系統(tǒng)內(nèi)核（以Linux內(nèi)核為例）中旁路IP層、INET Socke層和BSD Socket層，使得數(shù)據(jù)鏈路層直接與應(yīng)用程序的通道接口層通信。如圖3所示。

圖3中陰影部分表示通信關(guān)鍵路徑上數(shù)據(jù)鏈路層。在該通信結(jié)構(gòu)下，系統(tǒng)在通信的關(guān)鍵路徑上將通過內(nèi)存映射和內(nèi)存拷貝兩種技術(shù)實(shí)現(xiàn)通信。在發(fā)送消息時(shí)，系統(tǒng)通過內(nèi)存映射技術(shù)將消息映射到內(nèi)核中的緩沖區(qū)，注冊協(xié)議標(biāo)識，并調(diào)用數(shù)據(jù)鏈路層函數(shù)對其進(jìn)行封包發(fā)送；在接收消息時(shí)，系統(tǒng)通過數(shù)據(jù)鏈路層的MAC地址進(jìn)行尋址、接收消息，并通過內(nèi)存拷貝直接將消息傳送到用戶空間中的應(yīng)用程序，實(shí)現(xiàn)點(diǎn)到點(diǎn)通信。

與用戶級通信結(jié)構(gòu)相比，基于數(shù)據(jù)鏈路層的通信結(jié)構(gòu)在通信關(guān)鍵路徑上只增加了一次內(nèi)存拷貝的開銷。同時(shí)，由于保留了數(shù)據(jù)鏈路層的通信，進(jìn)而為系統(tǒng)的安全性、可靠性和并行任務(wù)間的獨(dú)立性提供了保障。此外，該通信結(jié)構(gòu)可以屏蔽系統(tǒng)的硬件信息，使得在應(yīng)用程序中不再出現(xiàn)與系統(tǒng)通信硬件有關(guān)的操作。

與核心級通信結(jié)構(gòu)相比，該通信結(jié)構(gòu)在通信關(guān)鍵路徑上減少了協(xié)議處理開銷、數(shù)據(jù)拷貝次數(shù)和冗余的差錯(cuò)校驗(yàn)，進(jìn)而提高了系統(tǒng)的通信效率。

2 MPI的通信

MPI（Message Passing Interface）是為基于消息傳遞的并行程序設(shè)計(jì)提供一個(gè)高效、可擴(kuò)展、統(tǒng)一的編程環(huán)境，是目前主流的并行編程模式，也是分布式并行系統(tǒng)的主要編程環(huán)境。在集群環(huán)境中MPI并行程序設(shè)計(jì)中使用的通信模式有阻塞通信、非阻塞通信和組通信，其中阻塞通信和非阻塞通信屬于點(diǎn)對點(diǎn)通信，而點(diǎn)對點(diǎn)通信也正是MPI其他通信的基礎(chǔ)。

在阻塞通信中，當(dāng)發(fā)送調(diào)用函數(shù)MPI_Send后即被阻塞，這時(shí)，系統(tǒng)會(huì)將發(fā)送緩沖區(qū)中的數(shù)據(jù)拷貝到系統(tǒng)緩沖區(qū)，由系統(tǒng)負(fù)責(zé)發(fā)送消息，而發(fā)送者的操作只在拷貝操作完成時(shí)結(jié)束并返回，不必等待發(fā)送完成。但是，如果系統(tǒng)緩沖區(qū)不足或消息過長，導(dǎo)致拷貝失敗，則發(fā)送者將被阻塞，直到消息發(fā)送完成為止；同樣，當(dāng)接收者在調(diào)用函數(shù)MPI_Recv后會(huì)被阻塞，直至收到匹配的消息為止[3]。

非阻塞通信主要是通過實(shí)現(xiàn)計(jì)算與通信的重疊，進(jìn)而提高整個(gè)程序的執(zhí)行效率。對于非阻塞通信，不必等到通信操作完全結(jié)束后才可返回，而是由特定的通信硬件完成通信操作。在通信硬件執(zhí)行通信操作的同時(shí)，處理機(jī)可以同時(shí)進(jìn)行計(jì)算操作，這樣便實(shí)現(xiàn)了通信與計(jì)算的重疊。發(fā)送者調(diào)用函數(shù)MPI_Isend或接收者調(diào)用數(shù)MPI_Irecv后，處理機(jī)便可執(zhí)行其他計(jì)算任務(wù)。在發(fā)送(接收)操作開始時(shí)，發(fā)送者(接收者)使用請求句柄(request handler)，MPI通過檢查請求來決定發(fā)送(接收)操作是否完成，發(fā)送者（接收者）通過調(diào)用MPI_Test來確定發(fā)送（接收）操作是否完成。在發(fā)送或接收操作期間，發(fā)送者不能更改發(fā)送緩沖區(qū)中的內(nèi)容，接收者也不能使用接收緩沖區(qū)中的內(nèi)容。若發(fā)送者(接收者)調(diào)用函數(shù)MPI_Wait，則發(fā)送者(接收者)會(huì)被阻塞，直到發(fā)送(接收)操作完成才能返回[4]。

由此可知，MPI點(diǎn)到點(diǎn)通信在發(fā)送緩沖區(qū)、接收緩沖區(qū)和內(nèi)核中的系統(tǒng)緩沖區(qū)之間進(jìn)行傳遞，并由內(nèi)核發(fā)送或接收系統(tǒng)緩沖區(qū)中的消息，本文提出的新通信機(jī)制就是圍繞著系統(tǒng)緩沖區(qū)展開的。

3 基于數(shù)據(jù)鏈路層的MPI通信機(jī)制的設(shè)計(jì)與實(shí)現(xiàn)

若要實(shí)現(xiàn)本文所提出的基于數(shù)據(jù)鏈路層的集群通信機(jī)制，則需要開發(fā)一個(gè)中間件DLMC（Data_link Layer MPI Communication）用于提供雙方進(jìn)行通信的底層交換協(xié)議、數(shù)據(jù)包校驗(yàn)、用戶空間與內(nèi)核空間的數(shù)據(jù)交換和重傳機(jī)制等。這里需要注意的問題有：

(1)編譯方式

對于Linux內(nèi)核編譯分為直接編譯進(jìn)內(nèi)核和通過模塊編譯加載進(jìn)內(nèi)核。本系統(tǒng)采用模塊加載的方式進(jìn)行編譯,其理由是由于系統(tǒng)是在傳統(tǒng)Linux網(wǎng)絡(luò)下進(jìn)行的修改，只有MPI計(jì)算才會(huì)用到此中間件，而對于計(jì)算之外的部分仍然要依靠傳統(tǒng)的TCP/IP。例如計(jì)算前期的準(zhǔn)備工作，雖然模塊加載比直接編譯的效率低，但它可以隨意動(dòng)態(tài)加載和卸載，這樣不僅靈活，而且有利于開發(fā)、調(diào)試等工作。

(2)用戶空間和內(nèi)核空間之間的數(shù)據(jù)交換

基于數(shù)據(jù)鏈路層的通信進(jìn)程是在內(nèi)核空間運(yùn)行的，而MPI進(jìn)程是在用戶空間進(jìn)行的，所以需要在用戶空間和內(nèi)核空間進(jìn)行通信。通過利用Linux內(nèi)核機(jī)制，在用戶空間緩存頁面以及物理頁面之間建立映射關(guān)系，將物理內(nèi)存映射到進(jìn)程的地址空間，從而達(dá)到直接內(nèi)存訪問的目的。

在Linux中，對于高端物理內(nèi)存(896 MB之后)，并沒有與內(nèi)核地址空間建立對應(yīng)的關(guān)系(即虛擬地址=物理地址+PAGE_OFFSET)，所以不能使用諸如get_free_pages()函數(shù)進(jìn)行內(nèi)存分配,而必須使用alloc_pages()來得到struct *page結(jié)構(gòu)，然后將其映射到內(nèi)核地址空間，但此時(shí)映射后的地址并非和物理地址相差PAGE_OFFSET[5]。為實(shí)現(xiàn)內(nèi)存映射技術(shù)，其具體使用方法是：使用alloc_pages()在高端存儲器區(qū)得到struct *page結(jié)構(gòu)，然后調(diào)用kmap(struct *page)在內(nèi)核地址空間PAGE_OFFSET+896M之后的地址空間中建立永久映射。DLMC首先讓內(nèi)核得到用戶空間中發(fā)送緩沖區(qū)的頁信息，再將其映射到內(nèi)核地址空間，并且返回內(nèi)核虛擬地址，以供DLMC直接將發(fā)送緩沖區(qū)中的數(shù)據(jù)傳遞到數(shù)據(jù)鏈路層進(jìn)行發(fā)送，這樣就完成了用戶地址空間到內(nèi)核地址空間的映射。

(3)校驗(yàn)與重傳機(jī)制

由于數(shù)據(jù)鏈路層的傳輸是一種不可靠的網(wǎng)絡(luò)傳輸方式,涉及到對傳輸數(shù)據(jù)進(jìn)行數(shù)據(jù)校驗(yàn)重傳等工作?？紤]到局域網(wǎng)或者機(jī)對機(jī)傳輸?shù)姆€(wěn)定性和可靠性，系統(tǒng)校驗(yàn)方式使用簡單的數(shù)據(jù)校驗(yàn)和，重傳機(jī)制使用選擇重傳ARQ方案。當(dāng)出現(xiàn)差錯(cuò)必須重傳時(shí)，不必重復(fù)傳送已經(jīng)正確到達(dá)接收端的數(shù)據(jù)幀，而只重傳出錯(cuò)的數(shù)據(jù)幀或計(jì)時(shí)器超時(shí)的數(shù)據(jù)幀，以避免網(wǎng)絡(luò)資源的浪費(fèi)。

(4)中斷機(jī)制

由于本系統(tǒng)改變了TCP/IP的傳輸機(jī)制，所以需要對發(fā)出的數(shù)據(jù)包進(jìn)行協(xié)議標(biāo)識。系統(tǒng)在初始化階段，調(diào)用內(nèi)核的dev_add_pack()函數(shù)向內(nèi)核注冊了標(biāo)識為Ox080A的網(wǎng)絡(luò)數(shù)據(jù)處理函數(shù)。在發(fā)送數(shù)據(jù)包時(shí),系統(tǒng)先通過kmap()函數(shù)將MPI的發(fā)送緩沖區(qū)sendbuff映射到內(nèi)核映射緩沖區(qū)sysbuff，以軟中斷的方式通知系統(tǒng)，申請分配一個(gè)新的SKB來存儲sysbuff里的數(shù)據(jù)包，調(diào)用dev_queue_xmit函數(shù)，使數(shù)據(jù)包向下層傳遞，并清空sysbuff，釋放SKB。在接收端需要向內(nèi)核注冊相應(yīng)的硬件中斷處理函數(shù)，在接收到數(shù)據(jù)后喚醒上層的處理函數(shù)，并在netif_receive_skb函數(shù)（net/core/dev.c）中屏蔽將SKB包向上層傳遞的語句，改為將SKB里的數(shù)據(jù)以MPI數(shù)據(jù)包格式通過copy_to_user函數(shù)拷貝到MPI的接收緩沖區(qū)recvbuff中，完成數(shù)據(jù)的接收,其傳輸過程如圖4所示。


4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)結(jié)果和方法

本實(shí)驗(yàn)環(huán)境是一個(gè)4節(jié)點(diǎn)的Beowulf集群系統(tǒng)，每個(gè)節(jié)點(diǎn)包含一個(gè)PIV處理器和2 GB內(nèi)存，操作系統(tǒng)采用Redhat Linux Enterprise 5,并行集群軟件為OPEN MPI 1.3。由于條件所限，加之實(shí)驗(yàn)規(guī)模較小，本實(shí)驗(yàn)采用MPI自帶的函數(shù)MPI_Wtime()來采集MPI計(jì)算的開始時(shí)間和結(jié)束時(shí)間，取二者的時(shí)間差作為程序的運(yùn)行時(shí)間并對其進(jìn)行比較和分析。

由于本實(shí)驗(yàn)的目的是要測試基于數(shù)據(jù)鏈路層的通信機(jī)制的可行性，而該通信機(jī)制是在TCP/IP協(xié)議基礎(chǔ)之上構(gòu)建的，所以本實(shí)驗(yàn)對象將以單機(jī)系統(tǒng)、基于TCP/IP的MPI集群和基于DLMC的MPI集群作為參照平臺進(jìn)行測試。在實(shí)驗(yàn)用例設(shè)計(jì)上，考慮到兩種MPI集群的通信機(jī)制中的傳輸路徑不同，所以采用如下兩種測試方案：

(1)計(jì)算圓周率，主要測試系統(tǒng)的數(shù)學(xué)函數(shù)浮點(diǎn)計(jì)算性能，以點(diǎn)對點(diǎn)短消息傳輸為主；

(2)計(jì)算求解三對角方程組，主要測試通信和計(jì)算的平衡，以點(diǎn)對點(diǎn)長消息傳輸為主。

4.2 性能分析

(1)計(jì)算圓周率，如表1所示。

測試結(jié)果表明,在精度值設(shè)為10-8，精確值比較大時(shí)，基于TCP/IP的集群(4個(gè)進(jìn)程)的運(yùn)行時(shí)間是19.540 237 s，單機(jī)系統(tǒng)（單進(jìn)程）運(yùn)行時(shí)間是84.798 166 s，并行運(yùn)算效果明顯。在精度值設(shè)為10-4，精確值比較小時(shí)，基于TCP/IP的集群（4個(gè)進(jìn)程）的運(yùn)行時(shí)間是0.026 346 s，單機(jī)系統(tǒng)（單進(jìn)程）運(yùn)行時(shí)間是0.013 742 s，這是由于并行運(yùn)算過程中,參與運(yùn)算的機(jī)器需要通過網(wǎng)絡(luò)傳遞消息，若計(jì)算量規(guī)模不大，則在網(wǎng)絡(luò)傳輸上花費(fèi)的時(shí)間會(huì)比較多，所以反不如單機(jī)的運(yùn)行速度快。從基于DLMC的集群與基于TCP/IP的集群運(yùn)行結(jié)果對比看，在精度值較大時(shí)，前者略微快于后者，而在精度值較小時(shí)，后者略快于前者，這主要是因?yàn)榛赥CP/IP的MPI集群在發(fā)送和接收的整個(gè)過程中，需要2次數(shù)據(jù)拷貝，即發(fā)送緩沖區(qū)到內(nèi)核的拷貝和內(nèi)核到接收緩沖區(qū)的拷貝，同時(shí)還有經(jīng)過各協(xié)議層的開銷。而基于DLMC的MPI集群在整個(gè)的傳輸過程中，通過使用內(nèi)存映射，只需要1次數(shù)據(jù)拷貝，同時(shí)旁路IP層及以上各協(xié)議層，在這種以短消息傳輸為主的測試中使得DLMC集群不能發(fā)揮其在網(wǎng)絡(luò)傳輸上的優(yōu)勢，所以在精度值較大時(shí)，二者相差無幾；在精度值較小時(shí)，反而基于TCP/IP的集群更快一些，這是因?yàn)閮?nèi)存映射和內(nèi)核操作所引入的開銷大于1次內(nèi)存拷貝開銷而造成性能的下降。

(2)計(jì)算求解三對角方程組，如表2所示。

由測試結(jié)果表明，在傳輸消息較小時(shí)，基于DLMC的MPI集群花費(fèi)的時(shí)間略微小于基于TCP/IP的MPI集群，這說明此時(shí)基于內(nèi)存映射和內(nèi)核調(diào)用等操作的開銷要高于兩次數(shù)據(jù)拷貝的開銷，造成網(wǎng)絡(luò)延遲略高。但隨著傳輸消息規(guī)模的增大,特別是消息大小超過1 MB時(shí)，基于內(nèi)存映射和數(shù)據(jù)鏈路層協(xié)議的DLMC相對于具有2次內(nèi)存拷貝的多協(xié)議機(jī)制的網(wǎng)絡(luò)延時(shí)要小得多，這樣使得系統(tǒng)的整體運(yùn)行時(shí)間明顯低于傳統(tǒng)的TCP/IP集群。

由上分析可知，基于Linux數(shù)據(jù)鏈路層的集群通信機(jī)制是可行的。在該機(jī)制下構(gòu)建的MPI集群系統(tǒng)完成了無IP條件下的數(shù)據(jù)傳輸，并且支持多用戶調(diào)用，在傳輸過程中減少了協(xié)議開銷、和內(nèi)存拷貝次數(shù)，相比于TCP/IP傳輸有一定提高。但是基于數(shù)據(jù)鏈路層協(xié)議的特點(diǎn)，該機(jī)制只能在局域網(wǎng)范圍內(nèi)運(yùn)行，所以集群節(jié)點(diǎn)數(shù)量或規(guī)模會(huì)受到一定的限制，只能適合中小集群系統(tǒng)的應(yīng)用。由于實(shí)驗(yàn)條件的有限，對集群通信系統(tǒng)未能充分驗(yàn)證，希望在今后的研發(fā)工作中能夠進(jìn)一步加強(qiáng)。