多核多線程技術(shù)

多核程序設(shè)計(jì)

參考資料：1.多核系列教材編寫(xiě)組.多核程序設(shè)計(jì).清華大學(xué)出版社,2007.92.DavidB.Kirk,Wen-meiW.Hwu著.陳曙暉,熊淑華譯.大規(guī)模并行處理器編程實(shí)踐.清華大學(xué)出版社,2010.93.MauriceHerlihy,NirShavit著.金海,胡侃譯.多處理器編程的藝術(shù).機(jī)械工業(yè)出版社,2009.84.RichardGerber,AartJ.C.Bik,KevinB.Smith等著,王濤,單久龍,孫廣中譯.軟件優(yōu)化技術(shù)——IA-32平臺(tái)的高性能手冊(cè)(第2版)

.電子工業(yè)出版社,2007.4多核程序設(shè)計(jì)

電子書(shū)及資料下載：

/zh-cn/articles/32067多核程序設(shè)計(jì)

第一章多核技術(shù)導(dǎo)論微處理器發(fā)展史1945年，世界上第一臺(tái)全自動(dòng)電子數(shù)字計(jì)算機(jī)ENIAC計(jì)算機(jī)的發(fā)展按照硬件工藝可以分為第一代（1946～1958）：電子管數(shù)字計(jì)算機(jī)。第二代（1958～1964）：晶體管數(shù)字計(jì)算機(jī)。第三代（1964～1971）：集成電路數(shù)字計(jì)算機(jī)。第四代(1971年以后）：大規(guī)模集成電路數(shù)字計(jì)算機(jī)。微處理器第一代微處理器(4位)：英特爾4004,8008第二代微處理器(8位)：采用NMOS工藝,采用匯編語(yǔ)言、BASIC、Fortran編程，使用單用戶操作系統(tǒng)。如英特爾8080,8085。第三代微處理器(16位)：以1978年英特爾的8086出現(xiàn)為起點(diǎn)。第四代微處理器(32位)：運(yùn)算模式包括實(shí)模式、保護(hù)模式和“虛擬86”。英特爾80386DX,80486,Pentium4…微處理器發(fā)展史微處理器發(fā)展史微處理器發(fā)展史并行計(jì)算機(jī)由一組處理單元組成，這組處理單元通過(guò)相互之間的通信與協(xié)作，以更快的速度共同完成一項(xiàng)大規(guī)模的計(jì)算任務(wù)。出現(xiàn)背景:60年代初期，晶體管以及磁芯存儲(chǔ)器的出現(xiàn)，處理單元變得越來(lái)越小，存儲(chǔ)器也更加小巧和廉價(jià)。出現(xiàn)規(guī)模不大的共享存儲(chǔ)多處理器系統(tǒng)，即大型主機(jī)（典型代表：IBM360）。60年代末期，同一個(gè)處理器開(kāi)始設(shè)置多個(gè)功能相同的功能單元，流水線技術(shù)也出現(xiàn)了，在處理器內(nèi)部的應(yīng)用大大提高了并行計(jì)算機(jī)系統(tǒng)的性能。兩個(gè)最主要的組成部分計(jì)算節(jié)點(diǎn)節(jié)點(diǎn)間的通信與協(xié)作機(jī)制并行計(jì)算機(jī)的弗林分類Flynn根據(jù)指令流和數(shù)據(jù)流的不同組織方式，把計(jì)算機(jī)系統(tǒng)的結(jié)構(gòu)分為以下四類：?jiǎn)沃噶盍鲉螖?shù)據(jù)流（SingleInstructionstreamSingleDatastream,SISD）單指令流多數(shù)據(jù)流（SingleInstructionstreamMultipleDatastream,SIMD）多指令流單數(shù)據(jù)流（MultipleInstructionstreamSingleDatastream,MISD）多指令流多數(shù)據(jù)流（MultipleInstructionstreamMultipleDatastream,MISD）并行計(jì)算機(jī)的弗林分類并行計(jì)算機(jī)系統(tǒng)絕大部分為MIMD系統(tǒng)，包括：并行向量機(jī)（PVP，ParallelVectorProcessor）；對(duì)稱多處理機(jī)（SMP,SymmetricMultiprocessor）；大規(guī)模并行處理機(jī)（MPP，MassivelyParallelProcessor）；機(jī)群（Cluster）；分布式共享存儲(chǔ)多處理機(jī)（DSM，DistributiedSharedMemory）并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類分布式存儲(chǔ)器的SIMD處理機(jī)含有多個(gè)同樣結(jié)構(gòu)的處理單元（PE），通過(guò)尋徑網(wǎng)絡(luò)以一定方式互相連接。每個(gè)PE有各自的本地存儲(chǔ)器（LM）。向量超級(jí)計(jì)算機(jī)（共享式存儲(chǔ)器SIMD）集中設(shè)置存儲(chǔ)器，共享的多個(gè)并行存儲(chǔ)器通過(guò)對(duì)準(zhǔn)網(wǎng)絡(luò)與各處理單元PE相連。在處理單元數(shù)目不太大的情況下很理想。對(duì)稱多處理器（SMP）一個(gè)計(jì)算機(jī)上匯集了一組處理器，各處理器之間共享內(nèi)存子系統(tǒng)以及總線結(jié)構(gòu)。并行向量處理機(jī)（PVP）使用定制的高帶寬網(wǎng)絡(luò)將向量處理器連向共享存儲(chǔ)器模塊使用大量的向量寄存器和指令緩沖器集群計(jì)算機(jī)由許多連在一起的獨(dú)立計(jì)算機(jī)組成，像一個(gè)單獨(dú)集成的計(jì)算機(jī)資源一樣協(xié)同工作，用來(lái)解決大型計(jì)算問(wèn)題。并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類對(duì)稱多處理共享存儲(chǔ)并行機(jī)（SMP）內(nèi)存模塊和處理器對(duì)稱地分布在互聯(lián)網(wǎng)絡(luò)的兩側(cè)，內(nèi)存訪問(wèn)屬典型的均勻訪問(wèn)模型。并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類SMP主要特征對(duì)稱共享存儲(chǔ)系統(tǒng)中任何處理器均可直接訪問(wèn)任何存儲(chǔ)模塊中的存儲(chǔ)單元和I/O模塊，且訪問(wèn)的延遲、帶寬和訪問(wèn)成功的概率是一致的。各個(gè)處理器之間的地位等價(jià)，操作系統(tǒng)可在任意處理器上運(yùn)行。單一的操作系統(tǒng)映像全系統(tǒng)只有一個(gè)操作系統(tǒng)駐留在共享存儲(chǔ)器中，它根據(jù)各個(gè)處理器的負(fù)載情況，動(dòng)態(tài)地分配各個(gè)進(jìn)程到各個(gè)處理器，并保持各處理器間的負(fù)載平衡。局部高速緩存cache及其數(shù)據(jù)一致性每個(gè)處理器均配備局部cache，它們可以擁有獨(dú)立的局部數(shù)據(jù)，但是這些數(shù)據(jù)必須與存儲(chǔ)器中的數(shù)據(jù)保持一致。低通信延遲各個(gè)進(jìn)程通過(guò)讀/寫(xiě)操作系統(tǒng)提供的共享數(shù)據(jù)緩存區(qū)來(lái)完成處理器間的通信，其延遲通常小于網(wǎng)絡(luò)通信的延遲。共享總線帶寬所有處理器共享總線的帶寬，完成對(duì)內(nèi)存模塊和I/O模塊的訪問(wèn)。支持消息傳遞、共享存儲(chǔ)并行程序設(shè)計(jì)并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類SMP典型代表SGIPOWERChallengeXL系列并行機(jī)（可擴(kuò)展至36個(gè)MIPSR10000微處理器）。COMPAQAlphaserver84005/440（含12個(gè)Alpha21264微處理器）。?HP9000/T600（含12個(gè)HPPA9000微處理器）。?IBMRS6000/R40（含8個(gè)RS6000微處理器）。并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類分布共享存儲(chǔ)并行機(jī)（DSM）內(nèi)存模塊局部在各個(gè)結(jié)點(diǎn)內(nèi)部，并被所有結(jié)點(diǎn)共享。這樣，可以較好地改善對(duì)稱多處理共享存儲(chǔ)并行機(jī)的可擴(kuò)展能力并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類DSM主要特征

以結(jié)點(diǎn)為單位，每個(gè)結(jié)點(diǎn)包含一個(gè)或多個(gè)CPU，每個(gè)CPU擁有自己的局部cache，并共享局部存儲(chǔ)器和I/O設(shè)備，所有結(jié)點(diǎn)通過(guò)高性能互聯(lián)網(wǎng)絡(luò)相互連接；物理上分布存儲(chǔ)：內(nèi)存模塊分布在各結(jié)點(diǎn)中，并通過(guò)高性能互聯(lián)網(wǎng)絡(luò)相互連接。單一的內(nèi)存地址空間：所有這些內(nèi)存模塊都由硬件進(jìn)行統(tǒng)一編址，并通過(guò)互聯(lián)網(wǎng)絡(luò)連接形成了并行機(jī)的共享存儲(chǔ)器。非一致內(nèi)存訪問(wèn)（NUMA）模式：由于遠(yuǎn)端訪問(wèn)必須通過(guò)高性能互聯(lián)網(wǎng)絡(luò)，而本地訪問(wèn)只需直接訪問(wèn)局部?jī)?nèi)存模塊，因此，遠(yuǎn)端訪問(wèn)的延遲一般是本地訪問(wèn)延遲的3倍以上。單一的操作系統(tǒng)映像：用戶只看到一個(gè)操作系統(tǒng)，它可以根據(jù)各結(jié)點(diǎn)的負(fù)載情況，動(dòng)態(tài)地分配進(jìn)程。并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類DSM主要特征

基于cache的數(shù)據(jù)一致性：通常采用基于目錄的cache一致性協(xié)議來(lái)保證各結(jié)點(diǎn)的局部cache數(shù)據(jù)與存儲(chǔ)器中數(shù)據(jù)的一致性。低通信延遲與高通信帶寬：專用的高性能互聯(lián)網(wǎng)絡(luò)使得結(jié)點(diǎn)間的延遲很小，通信帶寬可以擴(kuò)展。DSM并行機(jī)可擴(kuò)展到數(shù)百個(gè)結(jié)點(diǎn)，能提供每秒數(shù)千億次的浮點(diǎn)運(yùn)算性能。支持消息傳遞、共享存儲(chǔ)并行程序設(shè)計(jì)。并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類DSM典型代表

SGIOrigin–2000、SGIOrigin3800、SGIAltix并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類大規(guī)模并行機(jī)系統(tǒng)（MPP）大規(guī)模并行機(jī)系統(tǒng)是典型的分布存儲(chǔ)系統(tǒng)。并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類MPP典型特征

由數(shù)百個(gè)乃至數(shù)千個(gè)計(jì)算結(jié)點(diǎn)和I/O結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)相對(duì)獨(dú)立，并擁有一個(gè)或多個(gè)微處理器。這些結(jié)點(diǎn)配備有局部cache，并通過(guò)局部總線或互聯(lián)網(wǎng)絡(luò)與局部?jī)?nèi)存模塊和I/O設(shè)備相連接。這些結(jié)點(diǎn)由局部高性能網(wǎng)卡(NIC)通過(guò)高性能互聯(lián)網(wǎng)絡(luò)相互連接。它一般采用由多種靜態(tài)拓?fù)浣Y(jié)構(gòu)耦合而成的混合拓?fù)浣Y(jié)構(gòu)，其通信延遲和通信帶寬均明顯優(yōu)于機(jī)群互聯(lián)網(wǎng)絡(luò)。MPP的各個(gè)結(jié)點(diǎn)均擁有不同的操作系統(tǒng)映像。一般情況下，用戶可以將作業(yè)提交給作業(yè)管理系統(tǒng)，由它負(fù)責(zé)調(diào)度當(dāng)前最空閑、最有效的計(jì)算結(jié)點(diǎn)來(lái)執(zhí)行該作業(yè)。各個(gè)結(jié)點(diǎn)間的內(nèi)存模塊相互獨(dú)立，且不存在全局內(nèi)存單元的統(tǒng)一硬件編址。僅支持消息傳遞或者高性能Fortran并行程序設(shè)計(jì)，不支持全局共享的OpenMP并行程序設(shè)計(jì)模式。并行計(jì)算機(jī)從系統(tǒng)結(jié)構(gòu)角度分類機(jī)群（cluster）有三個(gè)明顯的特征

系統(tǒng)由商用結(jié)點(diǎn)構(gòu)成，每個(gè)結(jié)點(diǎn)包含2-4個(gè)商用微處理器，結(jié)點(diǎn)內(nèi)部共享存儲(chǔ)。采用商用機(jī)群交換機(jī)連接結(jié)點(diǎn)，結(jié)點(diǎn)間分布存儲(chǔ)。在各個(gè)結(jié)點(diǎn)上，采用機(jī)群Linux操作系統(tǒng)、GNU編譯系統(tǒng)和作業(yè)管理系統(tǒng)。片上多核處理器架構(gòu)片上多核處理器（ChipMulti-Processor，CMP）就是將多個(gè)計(jì)算內(nèi)核集成在一個(gè)處理器芯片中，從而提高計(jì)算能力。按計(jì)算內(nèi)核的對(duì)等與否，CMP可分為同構(gòu)多核和異構(gòu)多核CPU核心數(shù)據(jù)共享與同步的通信機(jī)制：總線共享Cache結(jié)構(gòu)：每個(gè)CPU內(nèi)核擁有共享的二級(jí)或三級(jí)Cache，用于保存比較常用的數(shù)據(jù)，并通過(guò)連接核心的總線進(jìn)行通信?；谄匣ミB的結(jié)構(gòu)：每個(gè)CPU核心具有獨(dú)立的處理單元和Cache，各個(gè)CPU核心通過(guò)交叉開(kāi)關(guān)或片上網(wǎng)絡(luò)等方式連接在一起。給程序開(kāi)發(fā)者帶來(lái)的挑戰(zhàn)典型多核芯片架構(gòu)芯片組對(duì)多核的支持——固件固件是一種嵌入到硬件設(shè)備中的軟件。它通常燒寫(xiě)在flash等介質(zhì)中，可以被當(dāng)作一個(gè)二進(jìn)制映像文件由用戶從硬件設(shè)備中調(diào)用。固件是在集成電路只讀存儲(chǔ)器中的計(jì)算機(jī)程序，是可擦寫(xiě)可編程芯片，其上的程序可以通過(guò)專門的外部硬件進(jìn)行修改，但是不能被一般的應(yīng)用程序改動(dòng)。芯片組對(duì)多核的支持——固件(續(xù))BIOS（BasicInput/OutputSystem）作為系統(tǒng)硬件和操作系統(tǒng)之間的抽象層，主要用來(lái)初始化和配置系統(tǒng)的硬件，啟動(dòng)操作系統(tǒng)以及提供對(duì)系統(tǒng)設(shè)備底層的通訊。BIOS是連接CPU、芯片組和操作系統(tǒng)的固件，是IBM兼容計(jì)算機(jī)中啟動(dòng)時(shí)調(diào)用的固件代碼。由兩部分組成:上電自舉即POST（PowerOnSelfTest）和在線的中斷服務(wù)（主要由legacy操作系統(tǒng)使用）。計(jì)算機(jī)加電時(shí)BIOS從flash、PROM或是EPROM中啟動(dòng)并完成初始化，進(jìn)行加電自檢，對(duì)硬盤(pán)，內(nèi)存，顯卡，主板等硬件進(jìn)行掃描檢查，然后它將自己從BIOS內(nèi)存空間中解壓到系統(tǒng)的內(nèi)存空間中，并開(kāi)始從那里運(yùn)行。正在被以EFI（ExtensibleFirmwareInterface，可擴(kuò)展固件接口）為代表的新一代技術(shù)所取代。芯片組對(duì)多核的支持——固件(續(xù)2)EFI（可擴(kuò)展固件接口）在操作系統(tǒng)與平臺(tái)固件之間的軟件接口。EFI規(guī)范定義的接口包括包含平臺(tái)

信息的數(shù)據(jù)表和啟動(dòng)時(shí)及啟動(dòng)后的

服務(wù)。EFI啟動(dòng)管理器被用來(lái)選擇裝載操

作系統(tǒng)，不再需要專門的啟動(dòng)裝載

器機(jī)制輔助。Framework是一種固件的架構(gòu)，

它是EFI固件接口的一種實(shí)現(xiàn)，用

來(lái)完全替代傳統(tǒng)的BIOS。EFI對(duì)多核支持在Framework中定義了兩類處理器BSP（bootstrapprocessor），執(zhí)行EFI的初始化代碼，設(shè)置APIC環(huán)境，建立系統(tǒng)范圍的數(shù)據(jù)結(jié)構(gòu)，開(kāi)始并初始化AP。AP（applicationprocessor），在系統(tǒng)上電或重啟之后，AP會(huì)自己進(jìn)行一個(gè)簡(jiǎn)單的設(shè)置，然后就等待BSP發(fā)出Startup信號(hào)。Framework在多核計(jì)算機(jī)中初始化過(guò)程如下：SEC：從實(shí)模式切換到保護(hù)模式，處理不同的重啟事件、對(duì)每個(gè)處理器進(jìn)行緩存設(shè)置。PEI：做盡量少的硬件初始化，而把更多的留給DXE。DXE：對(duì)所有可用的硬件設(shè)備進(jìn)行初始化，為建立控制臺(tái)和啟動(dòng)操作系統(tǒng)提供必要的服務(wù)。BDS：建立所需的控制臺(tái)設(shè)備，在輸出控制臺(tái)上顯示用戶界面。當(dāng)系統(tǒng)最后選擇啟動(dòng)到操作系統(tǒng)時(shí)，EFI需要提交包括處理器在內(nèi)的有關(guān)信息。操作系統(tǒng)對(duì)多核處理器的支持方法調(diào)度與中斷對(duì)任務(wù)的分配進(jìn)行優(yōu)化。使同一應(yīng)用程序的任務(wù)盡量在一個(gè)核上執(zhí)行。對(duì)任務(wù)的共享數(shù)據(jù)優(yōu)化。由于CMP體系結(jié)構(gòu)共享二級(jí)緩存，可以考慮改變?nèi)蝿?wù)在內(nèi)存中的數(shù)據(jù)分布，使任務(wù)在執(zhí)行時(shí)盡量增加二級(jí)緩存的命中率。對(duì)任務(wù)的負(fù)載均衡優(yōu)化。當(dāng)任務(wù)在調(diào)度時(shí)，出現(xiàn)了負(fù)載不均衡，考慮將較忙處理器中與其他任務(wù)最不相關(guān)的任務(wù)遷移，以達(dá)到數(shù)據(jù)的沖突量小。輸入輸出系統(tǒng)多核體系處理器中，必須將中斷處理分發(fā)給一組核處理。存儲(chǔ)管理與文件系統(tǒng)庫(kù)函數(shù)做成非阻塞調(diào)用方式（需要保證數(shù)據(jù)同步的機(jī)制）使用多線程內(nèi)存分配操作系統(tǒng)對(duì)多核處理器的支持方法多核程序設(shè)計(jì)

第二章并行計(jì)算基礎(chǔ)并行和并發(fā)如果某個(gè)系統(tǒng)支持兩個(gè)或多個(gè)動(dòng)作（Action）同時(shí)存在，那么這個(gè)系統(tǒng)就是一個(gè)并發(fā)系統(tǒng)如果某個(gè)系統(tǒng)支持兩個(gè)或多個(gè)動(dòng)作同時(shí)執(zhí)行，那么這個(gè)系統(tǒng)就是一個(gè)并行系統(tǒng)并發(fā)程序可同時(shí)擁有兩個(gè)或多個(gè)線程。如果程序能夠并行執(zhí)行，則一定是運(yùn)行在多核處理器上，每個(gè)線程都將分配到一個(gè)獨(dú)立的處理器核上?！安⑿小备拍钍恰安l(fā)”概念的一個(gè)子集什么是并行計(jì)算并行計(jì)算（parallelcomputing）是指，在并行機(jī)上將一個(gè)應(yīng)用分解成多個(gè)子任務(wù)，分配給不同的處理器，各個(gè)處理器之間相互協(xié)同，并行地執(zhí)行子任務(wù)，從而達(dá)到加速求解速度，或者求解應(yīng)用問(wèn)題規(guī)模的目的。成功開(kāi)展并行計(jì)算，必須具備三個(gè)基本條件：并行機(jī)并行機(jī)至少包含兩臺(tái)或兩臺(tái)以上處理機(jī)，這些處理機(jī)通過(guò)互連網(wǎng)絡(luò)相互連接，相互通信。應(yīng)用問(wèn)題必須具有并行度也就是說(shuō)，應(yīng)用可以分解為多個(gè)子任務(wù)，這些子任務(wù)可以并行地執(zhí)行。將一個(gè)應(yīng)用分解為多個(gè)子任務(wù)的過(guò)程，稱為并行算法的設(shè)計(jì)。并行編程在并行機(jī)提供的并行編程環(huán)境上，具體實(shí)現(xiàn)并行算法，編制并行程序，并運(yùn)行該程序，從而達(dá)到并行求解應(yīng)用問(wèn)題的目的。并行計(jì)算的目的、目標(biāo)并行計(jì)算技術(shù)的主要目的：加速求解問(wèn)題的速度例如，給定某應(yīng)用，在單處理器上，串行執(zhí)行需要2周，這個(gè)速度對(duì)一般的應(yīng)用而言，是無(wú)法忍受的。于是，可以借助并行計(jì)算，使用100臺(tái)處理器，加速50倍，將執(zhí)行時(shí)間縮短為6.72個(gè)小時(shí)。提高求解問(wèn)題的規(guī)模例如，在單處理器上，受內(nèi)存資源2GB的限制，只能計(jì)算10萬(wàn)個(gè)網(wǎng)格，但是，當(dāng)前數(shù)值模擬要求計(jì)算千萬(wàn)個(gè)網(wǎng)格。于是，也可以借助并行計(jì)算，使用100個(gè)處理器，將問(wèn)題求解規(guī)模線性地?cái)U(kuò)大100倍。并行計(jì)算的主要目標(biāo)：在并行機(jī)上，解決具有重大挑戰(zhàn)性計(jì)算任務(wù)的科學(xué)、工程及商業(yè)計(jì)算問(wèn)題，滿足不斷增長(zhǎng)的應(yīng)用問(wèn)題對(duì)速度和內(nèi)存資源的需求。并行計(jì)算的研究?jī)?nèi)容并行計(jì)算的主要研究?jī)?nèi)容大致可分為四個(gè)方面：并行機(jī)的高性能特征抽取充分理解和抽取當(dāng)前并行機(jī)體系結(jié)構(gòu)的高性能特征，提出實(shí)用的并行計(jì)算模型和并行性能評(píng)價(jià)方法，指導(dǎo)并行算法的設(shè)計(jì)和并行程序的實(shí)現(xiàn)。并行算法設(shè)計(jì)與分析設(shè)計(jì)高效率的并行算法，將應(yīng)用問(wèn)題分解為可并行計(jì)算的多個(gè)子任務(wù)，并具體分析這些算法的可行性和效果。并行實(shí)現(xiàn)技術(shù)主要包含并行程序設(shè)計(jì)和并行性能優(yōu)化。并行應(yīng)用這是并行計(jì)算研究的最終目的。通過(guò)驗(yàn)證和確認(rèn)并行程序的正確性和效率，進(jìn)一步將程序發(fā)展為并行應(yīng)用軟件，應(yīng)用于求解實(shí)際問(wèn)題。同時(shí)，結(jié)合實(shí)際應(yīng)用出現(xiàn)的各種問(wèn)題，不斷地改進(jìn)并行算法和并行程序。并行計(jì)算示例N個(gè)數(shù)被分布存儲(chǔ)在P臺(tái)處理器，P臺(tái)處理器并行執(zhí)行N個(gè)數(shù)的累加和。首先，各個(gè)處理器累加它們各自擁有的局部數(shù)據(jù)，得到部分和；然后，P臺(tái)處理器執(zhí)行全局通信操作，累加所有部分和，得到全局累加和。并行計(jì)算機(jī)體系結(jié)構(gòu)組成并行計(jì)算機(jī)的各個(gè)部分：節(jié)點(diǎn)（node）構(gòu)成并行機(jī)的基本單位互聯(lián)網(wǎng)絡(luò)（interconnectnetwork）內(nèi)存（memory）內(nèi)存模塊與節(jié)點(diǎn)分離內(nèi)存模塊位于節(jié)點(diǎn)內(nèi)部多級(jí)存儲(chǔ)體系結(jié)構(gòu)為了解決內(nèi)存墻（memorywall）性能瓶頸問(wèn)題。在節(jié)點(diǎn)內(nèi)部的cache稱為二級(jí)cache（L2cache）。在處理器內(nèi)部更小的cache稱為一級(jí)cache（L1cache）。L1cache連接CPU寄存器和L2cache，負(fù)責(zé)緩存L2cache中的數(shù)據(jù)到寄存器中。多級(jí)存儲(chǔ)體系結(jié)構(gòu)并行計(jì)算機(jī)的多級(jí)存儲(chǔ)結(jié)構(gòu)主要包括兩個(gè)問(wèn)題：Cache的映射策略，即cache如何從內(nèi)存中取得數(shù)據(jù)進(jìn)行存儲(chǔ)；

節(jié)點(diǎn)內(nèi)部或者節(jié)點(diǎn)之間內(nèi)存的訪問(wèn)模式。cache原理cache以cache線為基本單位，每條cache包含L個(gè)字，每個(gè)字8個(gè)字節(jié)。例如，L=4，則表示cache線包含4*8=32個(gè)字節(jié)。內(nèi)存空間分割成塊（block），每個(gè)塊大小與cache線長(zhǎng)度一致，數(shù)據(jù)在內(nèi)存和cache之間的移動(dòng)以cache線為基本單位。Fori=1toMA[i]=A[i]+2*B[i]如果操作數(shù)存在cache中，稱該次訪問(wèn)是命中的，否則，該次操作是“撲空”的。無(wú)Cache，訪問(wèn)內(nèi)存2M次；有cache，訪問(wèn)內(nèi)存2M/L次多級(jí)存儲(chǔ)體系結(jié)構(gòu)cache的映射策略指的是內(nèi)存塊和cache線之間如何建立相互映射關(guān)系。直接映射策略（directmappingstrategy）每個(gè)內(nèi)存塊只能被唯一的映射到一條cache線中K－路組關(guān)聯(lián)映射策略（K-waysetassociationmappingstrategy）Cache被分解為V個(gè)組，每個(gè)組由K條cache線組成，內(nèi)存塊按直接映射策略映射到某個(gè)組，但在該組中，內(nèi)存塊可以被映射到任意一條cache線。全關(guān)聯(lián)映射策略（fullassociationmappingstrategy）內(nèi)存塊可以被映射到cache中的任意一條cache線。并行計(jì)算機(jī)訪存模型UMA（UniformMemoryAccess）均勻存儲(chǔ)訪問(wèn)模型物理存儲(chǔ)器被所有節(jié)點(diǎn)共享；所有節(jié)點(diǎn)訪問(wèn)任意存儲(chǔ)單元的時(shí)間相同；發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略平等對(duì)待每個(gè)節(jié)點(diǎn)，即每個(gè)節(jié)點(diǎn)機(jī)會(huì)均等；各節(jié)點(diǎn)的CPU可帶有局部私有高速緩存；外圍I/O設(shè)備也可以共享，且每個(gè)節(jié)點(diǎn)有平等的訪問(wèn)權(quán)利。NUMA（Non-UniformMemoryAccess）模型物理存儲(chǔ)器被所有節(jié)點(diǎn)共享，任意節(jié)點(diǎn)可以直接訪問(wèn)任意內(nèi)存模塊；節(jié)點(diǎn)訪問(wèn)內(nèi)存模塊的速度不同，訪問(wèn)本地存儲(chǔ)模塊的速度一般是訪問(wèn)其他節(jié)點(diǎn)內(nèi)存模塊的3倍以上；發(fā)生訪存競(jìng)爭(zhēng)時(shí)，仲裁策略對(duì)節(jié)點(diǎn)可能是不等價(jià)的；各節(jié)點(diǎn)的CPU可帶有局部私有高速緩存（cache）；外圍I/O設(shè)備也可以共享，但對(duì)各節(jié)點(diǎn)是不等價(jià)的。并行計(jì)算機(jī)訪存模型COMA（Cache-OnlyMemoryAccess）模型各處理器節(jié)點(diǎn)中沒(méi)有存儲(chǔ)層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間利用分布的高速緩存目錄D進(jìn)行遠(yuǎn)程高速緩存的訪問(wèn)COMA中的高速緩存容量一般都大于2級(jí)高速緩存容量使用COMA時(shí)，數(shù)據(jù)開(kāi)始時(shí)可以任意分配，因?yàn)樵谶\(yùn)行時(shí)它最終會(huì)被遷移到要用到它的地方NORMA（No-RemoteMemoryAccess）模型所有存儲(chǔ)器都是私有的；絕大多數(shù)NORMA都不支持遠(yuǎn)程存儲(chǔ)器的訪問(wèn)；在DSM（分布式共享存儲(chǔ)）中，NORMA就消失了。并行計(jì)算機(jī)訪存模型并行計(jì)算機(jī)系統(tǒng)的不同訪存模型分類并行計(jì)算模型計(jì)算模型是對(duì)計(jì)算機(jī)的抽象計(jì)算模型為設(shè)計(jì)、分析和評(píng)價(jià)算法提供基礎(chǔ)馮·偌依曼機(jī)就是一個(gè)理想的串行計(jì)算模型但現(xiàn)在還沒(méi)有一個(gè)通用的并行計(jì)算模型并行計(jì)算模型SIMD同步并行計(jì)算模型共享存儲(chǔ)的SIMD模型（PRAM模型）PRAM，ParallelRandomAccessMachine并行隨機(jī)存取模型分布存儲(chǔ)的SIMD模型（SIMD互聯(lián)網(wǎng)絡(luò)模型）MIMD異步并行計(jì)算模型異步PRAM模型BSP模型LogP模型C3模型SIMD同步并行計(jì)算模型SIMD共享存儲(chǔ)模型（PRAM模型）是一種抽象的并行計(jì)算模型，模型中：假定存在著一個(gè)容量無(wú)限大的共享存儲(chǔ)器；有有限或無(wú)限各功能相同的處理器，且均具有簡(jiǎn)單的算術(shù)運(yùn)算和邏輯判斷功能；在任何時(shí)刻各處理器均可以通過(guò)共享存儲(chǔ)單元交換數(shù)據(jù)。SIMD同步并行計(jì)算模型SIMD共享存儲(chǔ)模型（PRAM模型）根據(jù)處理器對(duì)共享存儲(chǔ)單元同時(shí)讀寫(xiě)的限制，模型分為：PRAM-EREW（Exclusive-ReadandExclusive-Write），不允許同時(shí)讀和同時(shí)寫(xiě)PRAM-CREW（Concurrent-ReadandExclusive-Write），允許同時(shí)讀但不允許同時(shí)寫(xiě)PRAM-CRCW（Concurrent-ReadandConcurrent-Write），允許同時(shí)讀和同時(shí)寫(xiě)SIMD同步并行計(jì)算模型SIMD共享存儲(chǔ)模型（PRAM模型）優(yōu)點(diǎn)：適合于并行算法的表達(dá)、分析和比較；使用簡(jiǎn)單，很多諸如處理器間通信、存儲(chǔ)管理和進(jìn)程同步等并行計(jì)算機(jī)的低級(jí)細(xì)節(jié)均隱含于模型中；易于設(shè)計(jì)算法和稍加修改便可運(yùn)行在不同的并行計(jì)算機(jī)上；有可能加入一些諸如同步和通信等需要考慮的方面。SIMD同步并行計(jì)算模型SIMD共享存儲(chǔ)模型（PRAM模型）控制單元P1LMP2LMPnLM互連網(wǎng)絡(luò)全局共享存儲(chǔ)器SIMD-PRAM模型MIMD同步并行計(jì)算模型MIMD-PRAM模型控制器1P1LMP2LMPnLM互連網(wǎng)絡(luò)全局共享存儲(chǔ)器控制器2控制器nMIMD異步計(jì)算模型——APRAM模型APRAM模型特點(diǎn):每個(gè)處理器都有其本地存儲(chǔ)器、局部時(shí)鐘和局部程序處理器間的通信經(jīng)過(guò)共享全局存儲(chǔ)器無(wú)全局時(shí)鐘，各處理器異步地獨(dú)立執(zhí)行各自的指令處理器任何時(shí)間依賴關(guān)系需明確地在各處理器的程序中加入同步（路）障（SynchronizationBarrier）一條指令可在非確定但有限的時(shí)間內(nèi)完成。APRAM模型中有四類指令:全局讀，將全局存儲(chǔ)單元中的內(nèi)容讀入本地存儲(chǔ)器單元中局部操作，對(duì)本地存儲(chǔ)器中的數(shù)執(zhí)行操作，其結(jié)果存入本地存儲(chǔ)器中全局寫(xiě)，將本地存儲(chǔ)器單元中的內(nèi)容寫(xiě)入全本地存儲(chǔ)器單元中同步，同步是計(jì)算中的一個(gè)邏輯點(diǎn)，在該點(diǎn)各處理器均需等待別的處理器到達(dá)后才能繼續(xù)執(zhí)行其局部程序MIMD異步計(jì)算模型——BSP模型大同步并行BSP(BulkSynchronousParallel)模型作為計(jì)算機(jī)語(yǔ)言和體系結(jié)構(gòu)之間的橋梁，由以下述三個(gè)參數(shù)描述分布存儲(chǔ)的并行計(jì)算機(jī)模型：處理器/存儲(chǔ)器模塊（下文簡(jiǎn)稱處理器）處理器模塊之間點(diǎn)到點(diǎn)信息傳遞的路由器執(zhí)行以時(shí)間間隔L為周期的路障同步器特點(diǎn)：將處理器和路由器分開(kāi)，強(qiáng)調(diào)了計(jì)算任務(wù)和通信任務(wù)的分開(kāi)，而路由器僅施行點(diǎn)到點(diǎn)的消息傳遞，不提供組合、復(fù)制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網(wǎng)絡(luò)拓?fù)?，又?jiǎn)化了通信協(xié)議采用路障方式的以硬件實(shí)現(xiàn)的全局同步是在可控的粗粒度級(jí)，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無(wú)過(guò)分的負(fù)擔(dān)在分析BSP模型的性能時(shí)，假定局部操作可在一個(gè)時(shí)間步內(nèi)完成，而在每一超級(jí)步中，一個(gè)處理器至多發(fā)送或接受h條消息（h-relation）MIMD異步計(jì)算模型——LogP模型LogP模型是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通信的多處理機(jī)模型，其中通信網(wǎng)絡(luò)由一組參數(shù)來(lái)描述，但它并不涉及到具體的網(wǎng)絡(luò)結(jié)構(gòu)，也不假定算法一定要用顯式的消息傳遞操作進(jìn)行描述。L（Latency）源處理機(jī)與目的處理機(jī)進(jìn)行消息（一個(gè)或幾個(gè)字）通信所需要的等待或延遲時(shí)間的上限。o（overhead）處理機(jī)準(zhǔn)備發(fā)送或準(zhǔn)備接受每個(gè)消息的時(shí)間開(kāi)銷（包括操作系統(tǒng)核心開(kāi)銷和網(wǎng)絡(luò)軟件開(kāi)銷），在這段時(shí)間里處理機(jī)不能執(zhí)行其他操作。g（gap）一臺(tái)處理機(jī)連續(xù)兩次發(fā)送或連續(xù)兩次接受消息時(shí)的最小時(shí)間間隔，其倒數(shù)即為處理機(jī)的通信帶寬。P（Processor）處理機(jī)的個(gè)數(shù)。MIMD異步計(jì)算模型——LogP模型揭示了分布存儲(chǔ)并行計(jì)算機(jī)的性能瓶頸，用L、o、g三個(gè)參數(shù)刻畫(huà)了通信網(wǎng)絡(luò)的特性，但屏蔽了網(wǎng)絡(luò)拓?fù)?、選路算法和通信協(xié)議等具體細(xì)節(jié)參數(shù)g反映了通信帶寬在任何時(shí)刻，最多只能有[L/g]條消息從一個(gè)處理器傳到另一個(gè)處理器，這就是網(wǎng)絡(luò)容限，當(dāng)一臺(tái)處理機(jī)發(fā)送的消息達(dá)到這個(gè)容限時(shí)，在發(fā)送的消息就會(huì)被阻塞；在網(wǎng)絡(luò)容限范圍內(nèi)，點(diǎn)到點(diǎn)傳送一條消息的時(shí)間為(2*o+L)。設(shè)想LogP模型中的L、o、g都為0，那么LogP模型就等同于PRAM模型MIMD異步計(jì)算模型——C3模型C3（Computation,Communication,Congestion）模型是一個(gè)與體系結(jié)構(gòu)無(wú)關(guān)的粗粒度的并行計(jì)算模型，旨在能反映計(jì)算復(fù)雜度，通信模式和通信期間潛在的擁擠等因素對(duì)粗粒度網(wǎng)絡(luò)算法的影響。C3模型強(qiáng)調(diào)用共用的通信操作來(lái)開(kāi)發(fā)粗粒度的并行算法BSP、LogP模型采用點(diǎn)到點(diǎn)的消息傳遞來(lái)進(jìn)行通信，復(fù)雜的通信操作由編程實(shí)現(xiàn)各種計(jì)算模型比較模型屬性PRAMAPRAMBSPLogPC3體系結(jié)構(gòu)SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM計(jì)算模式同步異步異步異步異步同步方式自動(dòng)同步路障同步路障同步隱式同步路障同步模型參數(shù)單位時(shí)間步d,讀/寫(xiě)時(shí)間B,同步時(shí)間p,處理器數(shù)g,帶寬因子l,同步間隔L,通信延遲o,額外開(kāi)銷g,帶寬因子P,處理器數(shù)l,信包長(zhǎng)度s,發(fā)送建立時(shí)間h,通信延遲計(jì)算粒度細(xì)粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式讀/寫(xiě)共享變量讀/寫(xiě)共享變量發(fā)送/接收消息發(fā)送/接收消息發(fā)送/接收消息地址空間全局地址空間單地址空間單/多地址空間單/多地址空間多地址空間并行編程方法編寫(xiě)正確的串行程序分析：找出并發(fā)性找出包含獨(dú)立計(jì)算的熱點(diǎn)（Hotspot）位置。熱點(diǎn)是指一段包含了大量操作的代碼設(shè)計(jì)與實(shí)現(xiàn)：采用線程來(lái)實(shí)現(xiàn)算法并行算法是適合在并行機(jī)上實(shí)現(xiàn)的算法測(cè)試正確性：檢測(cè)并修復(fù)在線程化時(shí)引入的錯(cuò)誤性能調(diào)優(yōu)：消除性能瓶頸并行算法分類并行算法根據(jù)運(yùn)算基本對(duì)象的不同可分為：數(shù)值并行算法主要為數(shù)值計(jì)算方法而設(shè)計(jì)的并行算法；非數(shù)值并行算法主要為符號(hào)運(yùn)算而設(shè)計(jì)的并行算法，如圖論算法、遺傳算法等。并行算法分類根據(jù)并行進(jìn)程間相互執(zhí)行順序關(guān)系的不同可分為：同步并行算法進(jìn)程間由于運(yùn)算執(zhí)行順序而必須相互等待的并行算法，如通常的向量算法、SIMD算法、MIMD并行機(jī)上進(jìn)程間需要相互等待通信結(jié)果的算法等；異步并行算法進(jìn)程間執(zhí)行相對(duì)獨(dú)立，不需要相互等待的一種算法，通常針對(duì)消息傳遞MIMD并行機(jī)設(shè)計(jì)，其主要特征是在計(jì)算的整個(gè)過(guò)程中均不需要等待，而是根據(jù)最新消息決定進(jìn)程的繼續(xù)或終止；獨(dú)立并行算法進(jìn)程間執(zhí)行是完全獨(dú)立的，計(jì)算的整個(gè)過(guò)程不需要任何通信。并行算法分類根據(jù)各進(jìn)程承擔(dān)的計(jì)算任務(wù)粒度的不同，可分為：細(xì)粒度并行算法通常指基于向量和循環(huán)級(jí)并行的算法；中粒度并行算法通常指基于較大的循環(huán)級(jí)并行；大粒度并行算法通常指基于子任務(wù)級(jí)并行的算法，例如通常的基于區(qū)域分解的并行算法，它們是當(dāng)前并行算法設(shè)計(jì)的主流。并行編程環(huán)境比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲(chǔ)和數(shù)據(jù)并行：共享存儲(chǔ)并行編程基于線程級(jí)細(xì)粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持?jǐn)?shù)據(jù)的共享存儲(chǔ)，所以并行編程的難度較小，但一般情況下，當(dāng)處理機(jī)個(gè)數(shù)較多時(shí)，其并行性能明顯不如消息傳遞編程；消息傳遞并行編程基于大粒度的進(jìn)程級(jí)并行，具有最好的可擴(kuò)展性，幾乎被所有當(dāng)前流行的各類并行計(jì)算機(jī)所支持，其具有較好的可擴(kuò)展性。消息傳遞并行編程只能支持進(jìn)程間的分布式存儲(chǔ)模式，即各個(gè)進(jìn)程只能支持訪問(wèn)其局部?jī)?nèi)存空間，而對(duì)其他進(jìn)程的局部?jī)?nèi)存空間的訪問(wèn)只能通過(guò)消息傳遞來(lái)實(shí)現(xiàn)，因此，學(xué)習(xí)和使用消息傳遞并行編程的難度均大于共享存儲(chǔ)和數(shù)據(jù)并行這兩種編程模式。

并行編程環(huán)境比較流行的并行編程環(huán)境主要有3類：消息傳遞、共享存儲(chǔ)和數(shù)據(jù)并行特征消息傳遞共享存儲(chǔ)數(shù)據(jù)并行典型代表MPI,PVMOpenMPHPF可移植性所有主流并行計(jì)算機(jī)SMP,DSMSMP,DSM,MPP并行粒度進(jìn)程級(jí)大粒度線程級(jí)細(xì)粒度進(jìn)程級(jí)細(xì)粒度并行操作方式異步異步松散同步數(shù)據(jù)存儲(chǔ)模式分布式存儲(chǔ)共享存儲(chǔ)共享存儲(chǔ)數(shù)據(jù)分配方式顯式隱式半隱式學(xué)習(xí)入門難度較難容易偏易可擴(kuò)展性好較差一般編程語(yǔ)言與編譯器在科學(xué)計(jì)算領(lǐng)域?qū)Σ⑿芯幊讨С忠呀?jīng)取得相當(dāng)成功的三項(xiàng)技術(shù)：自動(dòng)并行化數(shù)據(jù)并行語(yǔ)言HPF共享存儲(chǔ)并行編程接口OpenMP編程語(yǔ)言與編譯器自動(dòng)并行始于20世紀(jì)70年代的自動(dòng)向量化。20世紀(jì)80年代中期，基于依賴分析的向量化工具成熟，成為向量機(jī)的標(biāo)準(zhǔn)。自動(dòng)化并行本身不足以解決并行程序設(shè)計(jì)問(wèn)題。此領(lǐng)域的研究重點(diǎn)逐步轉(zhuǎn)向基于語(yǔ)言的策略研究，即從用戶那里獲得更多的信息，同時(shí)利用自動(dòng)并行化技術(shù)來(lái)減輕程序設(shè)計(jì)的負(fù)擔(dān)。依賴分析：搜索確定對(duì)同一數(shù)據(jù)結(jié)構(gòu)的哪些引用是訪問(wèn)同一存儲(chǔ)單元的編程語(yǔ)言與編譯器數(shù)據(jù)并行編程：HPF高性能Fortran(HPF)的思想是使數(shù)據(jù)管理的多數(shù)細(xì)節(jié)自動(dòng)并行化HPF提供了一個(gè)指令集，通過(guò)注釋形式的指令來(lái)擴(kuò)展變量類型的說(shuō)明，能夠?qū)?shù)組的數(shù)據(jù)布局進(jìn)行相當(dāng)詳細(xì)的控制。對(duì)顯式并行機(jī)制的說(shuō)明相當(dāng)有限，通過(guò)系統(tǒng)而非程序員把任務(wù)分配給處理機(jī)。編程語(yǔ)言與編譯器共享存儲(chǔ)并行編程：OpenMP1997年由SiliconGraphics領(lǐng)導(dǎo)的工業(yè)協(xié)會(huì)推出了OpenMP是一個(gè)與Fortran77和C語(yǔ)言綁定的并行編程接口OpenMP指令在單機(jī)編譯器上被當(dāng)作注釋而忽略通過(guò)parallelsection指令獲得任務(wù)并行#pragmaompparallelfor…提供了鎖變量用于線程間細(xì)粒度同步是適合于具有一致性訪存的共享存儲(chǔ)計(jì)算機(jī)的編程接口并行計(jì)算性能評(píng)測(cè)并行程序執(zhí)行時(shí)間從并行程序開(kāi)始執(zhí)行到所有進(jìn)程執(zhí)行完畢，墻上時(shí)鐘走過(guò)的時(shí)間，也稱為墻上時(shí)間（wallclocktime）。并行計(jì)算性能評(píng)測(cè)并行程序執(zhí)行時(shí)間對(duì)各個(gè)進(jìn)程，墻上時(shí)間可進(jìn)一步分解為計(jì)算CPU時(shí)間、通信CPU時(shí)間、同步開(kāi)銷時(shí)間、同步導(dǎo)致的進(jìn)程空閑時(shí)間計(jì)算CPU時(shí)間：進(jìn)程指令執(zhí)行所花費(fèi)的CPU時(shí)間，包括程序本身的指令執(zhí)行占用的時(shí)間（用戶時(shí)間）和系統(tǒng)指令花費(fèi)的時(shí)間；通信CPU時(shí)間：進(jìn)程通信花費(fèi)的CPU時(shí)間；同步開(kāi)銷時(shí)間：進(jìn)程同步花費(fèi)的時(shí)間；進(jìn)程空閑時(shí)間：進(jìn)程空閑時(shí)間是指并行程序執(zhí)行過(guò)程中，進(jìn)程所有空閑時(shí)間總和（如進(jìn)程阻塞式等待其他進(jìn)程的消息時(shí)。此時(shí)CPU通常是空閑的，或者處于等待狀態(tài)）并行計(jì)算性能評(píng)測(cè)并行程序性能評(píng)價(jià)方法浮點(diǎn)峰值性能與實(shí)際浮點(diǎn)性能峰值性能等于CPU內(nèi)部浮點(diǎn)乘加指令流水線條數(shù)、每條流水線每個(gè)時(shí)鐘周期完成的浮點(diǎn)運(yùn)算次數(shù)、處理器主頻三者的乘積實(shí)際浮點(diǎn)性能等于并行程序的總的浮點(diǎn)運(yùn)算次數(shù)和并行程序執(zhí)行時(shí)間的比值數(shù)值效率和并行效率并行計(jì)算性能評(píng)測(cè)并行加速比與效率在處理器資源獨(dú)享的前提下，假設(shè)某個(gè)串行應(yīng)用程序在某臺(tái)并行機(jī)單處理器上的執(zhí)行時(shí)間為TS，而該程序并行化后，P個(gè)進(jìn)程在P個(gè)處理器并行執(zhí)行所需要的時(shí)間為TP

，則該并行程序在該并行機(jī)上的加速比SP

可定義為：效率定義為：并行計(jì)算性能評(píng)測(cè)加速比性能定律——Amdahl定律能夠計(jì)算并行程序相對(duì)于最優(yōu)串行算法在性能提升上的理論最大值——他將程序劃分為可加速與不可加速兩大部分，程序總的加速比是一個(gè)關(guān)于程序中這兩部分所占比例以及可加速部分性能加速程度的函數(shù)Amdahl定律:f表示執(zhí)行程序中串行部分的比例，p表示處理器核的數(shù)量。假設(shè)最優(yōu)串行算法的執(zhí)行時(shí)間為一個(gè)單位時(shí)間（也就是分子為1）。處理器核在數(shù)量上能夠無(wú)限制的增加，但是無(wú)限的處理器核卻并不能帶來(lái)性能上的無(wú)限增長(zhǎng)，無(wú)論如何，程序性能上的總是有個(gè)上限，這個(gè)要受限于串行部分所占的比例。

并行計(jì)算性能評(píng)測(cè)Amdahl定律告訴我們：可并行計(jì)算量占主要比重通過(guò)并行化，增加的額外計(jì)算量所占比重有限：這些計(jì)算量由各個(gè)處理器/執(zhí)行內(nèi)核分?jǐn)傄凶銐虻牟⑿卸?并行子任務(wù)數(shù)量)，實(shí)現(xiàn)負(fù)載均衡：?jiǎn)栴}規(guī)模越大，并行度也越大數(shù)據(jù)并行大規(guī)模數(shù)據(jù)處理數(shù)據(jù)規(guī)模與處理器/執(zhí)行內(nèi)核的規(guī)模比率要適當(dāng)只有上述三個(gè)特征都滿足了，采用并行處理技術(shù)才有意義程序性能優(yōu)化串行程序性能優(yōu)化

是并行程序性能優(yōu)化的基礎(chǔ)，一個(gè)好的并行程序首先應(yīng)該擁有良好的單機(jī)性能，影響程序單機(jī)性能的主要因素是程序的計(jì)算流程和處理器的體系結(jié)構(gòu)。程序性能優(yōu)化串行程序性能優(yōu)化調(diào)用高性能庫(kù)許多著名的高性能數(shù)學(xué)程序庫(kù)如優(yōu)化的BLAS、FFTW等，由于經(jīng)過(guò)廠商或第三方針對(duì)特定處理機(jī)進(jìn)行的專門優(yōu)化，其性能一般大大優(yōu)于用戶自行編寫(xiě)的同樣功能的程序段或子程序。程序性能優(yōu)化串行程序性能優(yōu)化調(diào)用高性能庫(kù)

BLAS(BasicLinearAlgebraSubroutines)是一組高質(zhì)量的基本向量、矩陣運(yùn)算子程序。最早的BLAS是一組Fortran函數(shù)和子程序，后來(lái)又發(fā)展了其他語(yǔ)言接口，包括C、Java等。BLAS的官方網(wǎng)址在/blas/國(guó)內(nèi)鏡像為/blas/。BLAS的主要貢獻(xiàn)是將高性能代數(shù)計(jì)算程序的開(kāi)發(fā)同針對(duì)特定機(jī)器的性能優(yōu)化獨(dú)立開(kāi)來(lái)：代數(shù)算法程序的開(kāi)發(fā)者只需要運(yùn)用適當(dāng)?shù)姆謮K技術(shù)將計(jì)算過(guò)程變成矩陣、向量的基本運(yùn)算并調(diào)用相應(yīng)的BLAS子程序而不必考慮與計(jì)算機(jī)體系結(jié)構(gòu)相關(guān)的性能優(yōu)化問(wèn)題。線性代數(shù)軟件包如LAPACK、ScaLAPACK等都是基于這一思想設(shè)計(jì)的。程序性能優(yōu)化串行程序性能優(yōu)化調(diào)用高性能庫(kù)

FFTW(TheFastestFourierTransformintheWest)是一個(gè)免費(fèi)的快速富氏變換(FFT)軟件包，開(kāi)發(fā)者是麻省理工學(xué)院的MatteoFrigo和StevenG.Johnson，下載網(wǎng)址：

該軟件包用C語(yǔ)言開(kāi)發(fā)，其核心技術(shù)(編碼生成器)采用面向?qū)ο笳Z(yǔ)言Caml編寫(xiě)。FFTW能自動(dòng)適應(yīng)系統(tǒng)硬件，可移植性很強(qiáng)。它能計(jì)算一維和多維離散傅立葉變換，其數(shù)據(jù)類型可以是實(shí)型、復(fù)型或半復(fù)型。該軟件通過(guò)方案(plan)和執(zhí)行器(executor)與用戶進(jìn)行接口，內(nèi)部結(jié)構(gòu)及其復(fù)雜性對(duì)用戶透明，速度快。內(nèi)部編譯器、代碼生成器利用AST（AbstractSyntaxTree）在運(yùn)行時(shí)生成適合所運(yùn)行的機(jī)器的代碼并自我優(yōu)化。程序性能優(yōu)化串行程序性能優(yōu)化選擇適當(dāng)?shù)木幾g器優(yōu)化選項(xiàng)現(xiàn)代編譯器在編譯時(shí)能夠?qū)Τ绦蜻M(jìn)行優(yōu)化從而提高所生成的目標(biāo)代碼的性能。這些優(yōu)化功能通常通過(guò)一組編譯選項(xiàng)來(lái)控制。比較通用的優(yōu)化選項(xiàng)有“-O”、“-O0”、“-O2”、“-O3”等，“-O0”表示不做優(yōu)化，“-O1”、“-O2”、“-O3”等表示不同級(jí)別的優(yōu)化，優(yōu)化級(jí)別越高，生成的代碼的性能可能會(huì)越好，但采用過(guò)高級(jí)別的優(yōu)化會(huì)大大降低編譯速度，并且可能導(dǎo)致錯(cuò)誤的運(yùn)行結(jié)果。通常，“-O2”的優(yōu)化被認(rèn)為安全的。程序性能優(yōu)化串行程序性能優(yōu)化合理定義數(shù)組維數(shù)在進(jìn)行連續(xù)數(shù)據(jù)訪問(wèn)時(shí)應(yīng)該使得地址的增量與內(nèi)存體數(shù)的最大公約數(shù)盡量小，特別要避免地址增量正好是體數(shù)的倍數(shù)。注意嵌套循環(huán)的順序，盡量改善數(shù)據(jù)訪問(wèn)的局部性通用的原則就是盡量使最內(nèi)層循環(huán)的數(shù)據(jù)訪問(wèn)連續(xù)進(jìn)行程序性能優(yōu)化串行程序性能優(yōu)化數(shù)據(jù)分塊當(dāng)處理大數(shù)組時(shí)，對(duì)數(shù)組、循環(huán)進(jìn)行適當(dāng)分塊有助于同時(shí)改善訪存的時(shí)間和空間局部性。DOI=1,NDOJ=1,NA(I)=A(I)+B(J)ENDDOENDDO對(duì)數(shù)組B進(jìn)行分塊，S為分塊大小，改寫(xiě)上述程序：DOJ=1,N,SDOI=1,NDOJJ=J,MIN(J+S-1,N)A(I)=A(I)+B(JJ)ENDDOENDDOENDDO當(dāng)S≥N時(shí)，相當(dāng)于原始循環(huán)；當(dāng)S=1時(shí)相當(dāng)于交換I和J的循環(huán)順序。根據(jù)cache大小選擇適當(dāng)?shù)腟值，使得B(J:J+S-1)能夠被容納在cache中，可以改善對(duì)數(shù)組B的訪問(wèn)的時(shí)間局部性。程序性能優(yōu)化串行程序性能優(yōu)化循環(huán)展開(kāi)是另一個(gè)非常有效的程序優(yōu)化技術(shù)。它除了能夠改善數(shù)據(jù)訪問(wèn)的時(shí)間和空間局部性外，還由于增加了每步循環(huán)中的指令與運(yùn)算的數(shù)目，亦有助于CPU多個(gè)運(yùn)算部件的充分利用。DOI=1,ND=D+A(I)ENDDO將它進(jìn)行4步循環(huán)展開(kāi)的代碼如下：DOI=1,MOD(N,4)D=D+A(I)ENDDODOI=MOD(N,4)+1,N,4D=D+A(I)+A(I+1)+A(I+2)+A(I+3)ENDDO上面的代碼中第一個(gè)循環(huán)用于處理N除以4的余數(shù)，第二個(gè)循環(huán)是展開(kāi)后的循環(huán)。程序性能優(yōu)化串行程序：求小于N的全部素?cái)?shù)voidmain(){intnumber;//小于N的素?cái)?shù)個(gè)數(shù)； intprimes[n];//從primes[0]–primes[number-1]中存放生成的素?cái)?shù)； inti,j,k; primes[0]=2; for(i=3,j=1;i<n;i++){//從整數(shù)3開(kāi)始檢查i是否為素?cái)?shù) for(k=0;primes[k]*primes[k]<i;k++)//依次檢查i是否可以被前面的素?cái)?shù)整除 if(i%primes[k]==0)break; if(primes[k]*primes[k]>i){//如果i不能被前面的素?cái)?shù)整除//則將它作為新素?cái)?shù)存入數(shù)組

primes[j]=i; j++; } }}程序性能優(yōu)化并行程序性能優(yōu)化最主要的是選擇好的并行算法和通信模式減少通信量、提高通信粒度提高通信粒度的有效方法就是減少通信次數(shù)，盡可能將可以一次傳遞的數(shù)據(jù)合并起來(lái)一起傳遞全局通信盡量利用高效集合通信算法對(duì)于標(biāo)準(zhǔn)的集合通信，如廣播、規(guī)約、數(shù)據(jù)散發(fā)與收集等，盡量調(diào)用MPI標(biāo)準(zhǔn)庫(kù)函數(shù)挖掘算法的并行度，減少CPU空閑等待具有數(shù)據(jù)相關(guān)性的計(jì)算過(guò)程會(huì)導(dǎo)致并行運(yùn)行的部分進(jìn)程空閑等待.在這種情況下，可以考慮改變算法來(lái)消除數(shù)據(jù)相關(guān)性程序性能優(yōu)化并行程序性能優(yōu)化負(fù)載平衡必要時(shí)使用動(dòng)態(tài)負(fù)載平衡技術(shù)，即根據(jù)各進(jìn)程計(jì)算完成的情況動(dòng)態(tài)地分配或調(diào)整各進(jìn)程的計(jì)算任務(wù)。動(dòng)態(tài)調(diào)整負(fù)載時(shí)要考慮負(fù)載調(diào)整的開(kāi)銷及由于負(fù)載不平衡而引起的空閑等待對(duì)性能的影響，尋找最優(yōu)負(fù)載調(diào)整方案。通信、計(jì)算的重疊讓通信和計(jì)算重疊進(jìn)行，利用計(jì)算時(shí)間來(lái)屏蔽通信時(shí)間。實(shí)現(xiàn)方法一般基于非阻塞通信，先發(fā)出非阻塞的消息接受或發(fā)送命令，然后處理與收發(fā)數(shù)據(jù)無(wú)關(guān)的計(jì)算任務(wù)，完成計(jì)算后再等待消息收發(fā)的完成。通過(guò)引入重復(fù)計(jì)算來(lái)減少通信，即以計(jì)算換通信由于當(dāng)前大部分并行計(jì)算機(jī)的計(jì)算速度遠(yuǎn)遠(yuǎn)大于通信速度，并且在一些情況下，當(dāng)一個(gè)進(jìn)程計(jì)算時(shí)，別的進(jìn)程往往處于空閑等待狀態(tài)，因而適當(dāng)引入重復(fù)計(jì)算可以提高程序的總體性能。程序性能優(yōu)化并行程序：求小于N的全部素?cái)?shù)pThread_prime并行編譯器并行編譯器大致由三部分組成：流分析確定源代碼中數(shù)據(jù)和控制的相關(guān)性程序優(yōu)化將代碼變換成與之等效的的更好形式，以挖掘硬件潛力代碼生成將代碼從一種描述轉(zhuǎn)換成另一種中間形式的描述并行編譯器并行編譯過(guò)程并行編譯器流分析要使程序并行地執(zhí)行，首先要進(jìn)行相關(guān)性分析（DependencyAnalysis）四種相關(guān)形式：流相關(guān)：從Si～Sj存在執(zhí)行通路，且Si至少有一個(gè)輸出被用作Sj的輸入反相關(guān)：Sj緊接Si，且Sj的輸出被作為Si的輸入輸出相關(guān)：兩條語(yǔ)句往相同的變量里寫(xiě)控制相關(guān)：語(yǔ)句Sj的執(zhí)行與否依賴于語(yǔ)句Si并行編譯器代碼優(yōu)化代碼向量化（CodeVectorization）:把標(biāo)量程序中的由一種可向量化循環(huán)完成的操作變換成向量操作。代碼并行化（CodeParallelization）:并行代碼的優(yōu)化是將一個(gè)程序展開(kāi)成多線程以同時(shí)供多臺(tái)處理機(jī)并行執(zhí)行，其目的是要減少總的執(zhí)行時(shí)間。代碼生成并行代碼生成（CodeGeneration）涉及到將優(yōu)化后的中間形式的代碼轉(zhuǎn)換程可執(zhí)行的具體的機(jī)器目標(biāo)代碼。包括執(zhí)行次序、指令選擇、寄存器分配、負(fù)載平衡、并行粒度、代碼調(diào)度以及后優(yōu)化（Postoptimization）等問(wèn)題。多核程序設(shè)計(jì)

第三章多線程編程方法綜述進(jìn)程定義：進(jìn)程是具有一定獨(dú)立功能的程序關(guān)于一個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)?？杀硎境伤脑M（P,C,D,S），其中P是程序代碼，C是進(jìn)程的控制狀態(tài)，D是進(jìn)程的數(shù)據(jù)，S是進(jìn)程的執(zhí)行狀態(tài)。狀態(tài)：運(yùn)行態(tài)(Run):進(jìn)程占有處理機(jī)資源,正在運(yùn)行;就緒態(tài)(Ready):進(jìn)程本身具備運(yùn)行條件,但由于處理機(jī)的個(gè)數(shù)少于可運(yùn)行進(jìn)程的個(gè)數(shù),暫未投入運(yùn)行;等待態(tài)(Wait):

進(jìn)程本身不具備運(yùn)行條件，即使分給它處理機(jī)也不能運(yùn)行.進(jìn)程正等待某一個(gè)事件的發(fā)生,如等待某一資源被釋放，等待與該進(jìn)程相關(guān)的I/O傳輸?shù)耐瓿尚盘?hào)等。進(jìn)程狀態(tài)間轉(zhuǎn)換當(dāng)一個(gè)就緒進(jìn)程獲得處理機(jī)時(shí),其狀態(tài)由就緒變?yōu)檫\(yùn)行；當(dāng)一個(gè)運(yùn)行進(jìn)程被剝奪處理機(jī)時(shí),其狀態(tài)由運(yùn)行變?yōu)榫途w；當(dāng)一個(gè)運(yùn)行進(jìn)程因某事件受阻時(shí),如所申請(qǐng)資源被占用,啟動(dòng)I/O傳輸未完成,其狀態(tài)由運(yùn)行變?yōu)榈却?；?dāng)所等待事件發(fā)生時(shí),如得到申請(qǐng)資源,I/O傳輸完成,其狀態(tài)由等待變?yōu)榫途w。進(jìn)程進(jìn)程控制塊(ProcessControlBlock，PCB):標(biāo)志進(jìn)程存在的數(shù)據(jù)結(jié)構(gòu)，其中包含系統(tǒng)對(duì)進(jìn)程管理需要的全部信息。進(jìn)程標(biāo)識(shí)用戶標(biāo)識(shí)進(jìn)程狀態(tài)調(diào)度參數(shù)現(xiàn)場(chǎng)信息家族聯(lián)系程序地址當(dāng)前打開(kāi)文件消息隊(duì)列指針資源使用情況進(jìn)程隊(duì)列指針進(jìn)程進(jìn)程的組成

進(jìn)程控制塊：由于進(jìn)程控制塊中包含程序的地址信息，通過(guò)它可以找到程序在內(nèi)存或外存的存放地址，也就找到了整個(gè)進(jìn)程.PCB存于系統(tǒng)空間，只有操作系統(tǒng)能夠?qū)ζ浯嫒。脩舫绦虿荒茉L問(wèn).實(shí)際上用戶甚至感覺(jué)不到PCB的存在；程序：進(jìn)程的“軀體”，其中包括代碼和數(shù)據(jù)兩個(gè)部分.現(xiàn)代操作系統(tǒng)都支持程序共享的功能，這就要求代碼是“純”的，即在運(yùn)行期間不修改自身。數(shù)據(jù)一般包括靜態(tài)變量、動(dòng)態(tài)堆和動(dòng)態(tài)棧。進(jìn)程進(jìn)程的表示PCB程序PCB代碼數(shù)據(jù)+堆棧系統(tǒng)空間用戶空間（a）（b）進(jìn)程進(jìn)程的隊(duì)列為實(shí)現(xiàn)對(duì)進(jìn)程的管理，系統(tǒng)需要按照某種策略將進(jìn)程排成若干隊(duì)列，由于PCB是進(jìn)程的代表，因而進(jìn)程隊(duì)列實(shí)際上是由進(jìn)程PCB構(gòu)成的隊(duì)列.因?yàn)樵撽?duì)列通常由鏈的形式實(shí)現(xiàn)的，所以也稱PCB鏈。系統(tǒng)中的進(jìn)程隊(duì)列分為如下三類：就緒隊(duì)列、等待隊(duì)列、運(yùn)行隊(duì)列。進(jìn)程進(jìn)程的隊(duì)列就緒隊(duì)列整個(gè)系統(tǒng)一個(gè)。所有處于就緒狀態(tài)的進(jìn)程按照某種組織方式排在這一隊(duì)列中。等待隊(duì)列每個(gè)等待事件一個(gè)，當(dāng)進(jìn)程等待某一事件時(shí)，進(jìn)入與該事件相關(guān)的等待隊(duì)列中；當(dāng)某事件發(fā)生時(shí)，與該事件相關(guān)的一個(gè)或多個(gè)進(jìn)程離開(kāi)相應(yīng)的等待隊(duì)列，進(jìn)入就緒隊(duì)列。運(yùn)行隊(duì)列在單CPU系統(tǒng)中只有一個(gè)，在多CPU系統(tǒng)中每個(gè)CPU各有一個(gè)，每個(gè)隊(duì)列中只有一個(gè)進(jìn)程，指向運(yùn)行隊(duì)列頭部的指針被稱作運(yùn)行指示字。進(jìn)程進(jìn)程的類型系統(tǒng)進(jìn)程——運(yùn)行操作系統(tǒng)程序，完成操作系統(tǒng)的某些功能；用戶進(jìn)程——運(yùn)行用戶程序，直接為用戶服務(wù)。進(jìn)程的特性并發(fā)性：與其它進(jìn)程一道在宏觀上同時(shí)向前推進(jìn)；動(dòng)態(tài)性：進(jìn)程是執(zhí)行中的程序.此外進(jìn)程的動(dòng)態(tài)性還體現(xiàn)在如下兩個(gè)方面：首先，進(jìn)程是動(dòng)態(tài)產(chǎn)生、動(dòng)態(tài)消亡的；其次，在進(jìn)程的生存期內(nèi)，其狀態(tài)處于經(jīng)常性的動(dòng)態(tài)變化之中；獨(dú)立性：進(jìn)程是調(diào)度的基本單位，它可以獲得處理機(jī)并參與并發(fā)執(zhí)行；交往性：進(jìn)程在運(yùn)行過(guò)程中可能會(huì)與其它進(jìn)程發(fā)生直接或間接的相互作用；異步性：每個(gè)進(jìn)程都以其相對(duì)獨(dú)立、不可預(yù)知的速度向前推進(jìn)；結(jié)構(gòu)性：每個(gè)進(jìn)程有一個(gè)控制塊PCB。

進(jìn)程兩個(gè)特征資源特征，包括程序執(zhí)行所必需的計(jì)算資源，例如程序代碼、內(nèi)存地址空間、文件系統(tǒng)、I/O設(shè)備、程序計(jì)數(shù)器、寄存器、?？臻g等執(zhí)行特征，包括在進(jìn)程執(zhí)行過(guò)程中動(dòng)態(tài)改變的特征，例如指令路徑（即進(jìn)程執(zhí)行的指令序列）、進(jìn)程的控制與執(zhí)行狀態(tài)等。進(jìn)程通訊現(xiàn)代操作系統(tǒng)提供基本的系統(tǒng)調(diào)用函數(shù)，允許位于同一臺(tái)處理機(jī)或不同處理機(jī)的多個(gè)進(jìn)程之間相互交流信息三種表現(xiàn)形式：通信：進(jìn)程間的數(shù)據(jù)傳遞稱為進(jìn)程間通信。兩個(gè)進(jìn)程間傳遞的數(shù)據(jù)稱為消息；這種操作稱為消息傳遞同步：同步是使位于相同或不同處理機(jī)中的多個(gè)進(jìn)程之間相互等待的操作，它要求進(jìn)程的所有操作均必須等待到達(dá)某個(gè)控制狀態(tài)之后才進(jìn)行。聚集（或規(guī)約）：聚集將位于相同或不同處理機(jī)中的多個(gè)進(jìn)程的局部結(jié)果綜合起來(lái)，通過(guò)某種操作，產(chǎn)生一個(gè)新的結(jié)果，存儲(chǔ)在某個(gè)指定的或者所有的進(jìn)程的變量中。具體實(shí)現(xiàn)：在共享存儲(chǔ)環(huán)境中，通過(guò)讀/寫(xiě)操作系統(tǒng)通過(guò)的共享數(shù)據(jù)緩存區(qū)來(lái)實(shí)現(xiàn)在分布式存儲(chǔ)網(wǎng)絡(luò)環(huán)境中，通過(guò)網(wǎng)絡(luò)通信來(lái)實(shí)現(xiàn)進(jìn)程通訊

定義：進(jìn)程之間的互斥、同步及信息交換統(tǒng)稱進(jìn)程通訊(Inter-ProcessCommunication，IPC)低級(jí)通訊：將進(jìn)程互斥與進(jìn)程同步稱作進(jìn)程之間的低級(jí)通訊；高級(jí)通訊：進(jìn)程之間大數(shù)據(jù)量的傳遞稱作進(jìn)程之間的高級(jí)通訊。

進(jìn)程通訊的模式進(jìn)程通訊主要有兩種模式:共享內(nèi)存模式和消息模式。共享內(nèi)存模式相互通訊的進(jìn)程之間需要有公共內(nèi)存,一組進(jìn)程向該公共內(nèi)存中寫(xiě),另一組進(jìn)程由該公共內(nèi)存中讀,如此便實(shí)現(xiàn)了進(jìn)程之間的信息傳遞。需要解決兩個(gè)問(wèn)題:為相互通訊的進(jìn)程之間提供公共內(nèi)存；為訪問(wèn)公共內(nèi)存提供必要的同步機(jī)制。信息傳遞模式（通訊通過(guò)兩個(gè)基本的系統(tǒng)調(diào)用命令,即發(fā)送命令和接收命令）直接方式間接方式進(jìn)程通訊的模式直接方式：是指相互通訊的進(jìn)程之間在通訊時(shí)直呼其名,發(fā)送者在發(fā)送時(shí)要指定接收者的名字,接收者在接收時(shí)要指定發(fā)送者的名字兩種系統(tǒng)調(diào)用形式：對(duì)稱形式——通訊形式的特點(diǎn)是一對(duì)一的，調(diào)用命令：send(R,M)：將消息M發(fā)給進(jìn)程R；receive(S,N)：由進(jìn)程S處接收消息至N。非對(duì)稱形式——通訊形式的特點(diǎn)是多對(duì)一的，調(diào)用命令：send(R,M)：將消息M發(fā)給進(jìn)程R；receive(pid,N)：接受消息至N，返回pid為發(fā)送進(jìn)程標(biāo)識(shí)。信息傳遞兩種途徑：有緩沖途徑無(wú)緩沖途徑進(jìn)程通訊的模式間接方式：是指相互通訊的進(jìn)程之間在通訊時(shí)不是直呼對(duì)方名字,而是指明一個(gè)中間媒體,即信箱,進(jìn)程之間通過(guò)信箱來(lái)實(shí)現(xiàn)相互間的通訊.此時(shí),系統(tǒng)所提供的高級(jí)通訊原語(yǔ)以信箱取代進(jìn)程．發(fā)送和接收原語(yǔ)如下：send(MB,M)：將消息M發(fā)送到信箱MB；receive(MB,N)：由信箱MB中接收消息至N。進(jìn)程的創(chuàng)建與撤銷

進(jìn)程創(chuàng)建

建立一個(gè)PCB，并對(duì)其內(nèi)容進(jìn)行初始化；為該進(jìn)程分配必要的存儲(chǔ)空間，并加載所要執(zhí)行的程序(在UNIX系統(tǒng)中需要通過(guò)另外一個(gè)系統(tǒng)調(diào)用execl實(shí)現(xiàn))；將PCB送入就緒隊(duì)列。進(jìn)程撤銷完成使命的進(jìn)程需要終止自己并告知操作系統(tǒng)，系統(tǒng)將對(duì)進(jìn)程進(jìn)行善后處理(收集進(jìn)程狀態(tài)信息、通知其父進(jìn)程等)，之后將收回進(jìn)程所占有的所有資源(打開(kāi)文件、內(nèi)存等)，最后撤銷其PCB。，非正常終止也將進(jìn)入操作系統(tǒng)進(jìn)行善后處理。線程的概念進(jìn)程不適合細(xì)粒度的共享存儲(chǔ)并行程序設(shè)計(jì)。線程（thread）是進(jìn)程上下文（context）中執(zhí)行的代碼序列，又被稱為輕量級(jí)進(jìn)程（lightweightprocess），是進(jìn)程內(nèi)的一個(gè)相對(duì)獨(dú)立的執(zhí)行流。進(jìn)程可由單個(gè)線程來(lái)執(zhí)行，即通常所說(shuō)的串行執(zhí)行；或者由多個(gè)線程來(lái)并行執(zhí)行，此時(shí)，多個(gè)線程將共享該進(jìn)程的所有資源特征，并可以使用不同的CPU，對(duì)不同的數(shù)據(jù)進(jìn)行處理，從而達(dá)到提高進(jìn)程執(zhí)行速度的目的。線程的概念在支持多線程的系統(tǒng)中：進(jìn)程成為資源分配和保護(hù)的實(shí)體線程是被調(diào)度執(zhí)行的基本單元。進(jìn)程的資源包括進(jìn)程的地址空間，打開(kāi)的文件和I/O等屬于同一個(gè)進(jìn)程的線程共享該進(jìn)程的代碼段和數(shù)據(jù)段，打開(kāi)的文件，信號(hào)等還包含各自的線程ID，線程執(zhí)行狀態(tài)，CPU寄存器狀態(tài)和棧線程的概念進(jìn)程和線程的區(qū)別進(jìn)程——是指程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度運(yùn)行的一個(gè)獨(dú)立單位，有時(shí)也稱為活動(dòng)、路徑或任務(wù)。操作系統(tǒng)中引入進(jìn)程的目的，是為了使多個(gè)程序并發(fā)執(zhí)行，以改善資源利用率及提高系統(tǒng)的吞吐量。操作系統(tǒng)中再引入線程則是為了減少程序并發(fā)執(zhí)行時(shí)所付出的時(shí)空開(kāi)銷，使操作系統(tǒng)具有更好的并發(fā)性。進(jìn)程是資源的分配單位。線程——是進(jìn)程中的一個(gè)實(shí)體，是被系統(tǒng)調(diào)度和分配的基本單元。每個(gè)程序至少包含一個(gè)線程，那就是主線程。線程自己只擁有很少的系統(tǒng)資源（如程序計(jì)數(shù)器、一組寄存器和棧），但它可與同屬一個(gè)進(jìn)程的其他線程共享所屬進(jìn)程所擁有的全部資源。同一進(jìn)程中的多個(gè)線程之間可以并發(fā)執(zhí)行，從而更好地改善了系統(tǒng)資源的利用率。線程是CPU的調(diào)度單位。線程是“進(jìn)程中的一條執(zhí)行路徑或線索”或“進(jìn)程中的一個(gè)可調(diào)度實(shí)體”線程的概念單線程與多線程處理器模型線程的概念線程的概念線程的優(yōu)點(diǎn)上下文切換速度快：由同一進(jìn)程中的一個(gè)線程切換到另一個(gè)線程只需改變寄存器和棧，包括程序和數(shù)據(jù)在內(nèi)的地址空間不變；系統(tǒng)開(kāi)銷?。簞?chuàng)建線程比創(chuàng)建進(jìn)程所需完成的工作少，因而對(duì)于客戶請(qǐng)求，服務(wù)器動(dòng)態(tài)創(chuàng)建線程比動(dòng)態(tài)創(chuàng)建進(jìn)程具有更高的響應(yīng)速度；通訊容易：由于同一進(jìn)程中的多個(gè)線程地址空間共享，一個(gè)線程寫(xiě)到數(shù)據(jù)空間的信息可以直接被該進(jìn)程中的另一線程讀取，方便快捷；終止一個(gè)線程比終止一個(gè)進(jìn)程的代價(jià)要小。線程的概念調(diào)度在傳統(tǒng)的操作系統(tǒng)中，CPU調(diào)度和分派的基本單位是進(jìn)程。而在引入線程的操作系統(tǒng)中，則把線程作為CPU調(diào)度和分派的基本單位，進(jìn)程則作為資源擁有的基本單位，從而使傳統(tǒng)進(jìn)程的兩個(gè)屬性分開(kāi)，線程便能輕裝運(yùn)行，從而顯著地提高系統(tǒng)的并發(fā)性。同一進(jìn)程中線程的切換不會(huì)引起進(jìn)程切換，從而避免了昂貴的系統(tǒng)調(diào)用。但是在由一個(gè)進(jìn)程中的線程切換到另一進(jìn)程中的線程時(shí)，依然會(huì)引起進(jìn)程切換。線程的概念并發(fā)性

在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個(gè)進(jìn)程中的多個(gè)線程之間也可以并發(fā)執(zhí)行，因而使操作系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)的吞吐量。例：在一個(gè)未引入線程的單CPU操作系統(tǒng)中，若僅設(shè)置一個(gè)文件服務(wù)進(jìn)程，當(dāng)它由于某種原因被封鎖時(shí)，便沒(méi)有其他的文件服務(wù)進(jìn)程來(lái)提供服務(wù)。在引入了線程的操作系統(tǒng)中，可以在一個(gè)文件服務(wù)進(jìn)程中設(shè)置多個(gè)服務(wù)線程。當(dāng)?shù)谝粋€(gè)線程等待時(shí)，文件服務(wù)進(jìn)程中的第二個(gè)線程可以繼續(xù)運(yùn)行；當(dāng)?shù)诙€(gè)線程封鎖時(shí)，第三個(gè)線程可以繼續(xù)執(zhí)行，從而顯著地提高了文件服務(wù)的質(zhì)量以及系統(tǒng)的吞吐量。線程的概念系統(tǒng)開(kāi)銷

不論是引入了線程的操作系統(tǒng)，還是傳統(tǒng)的操作系統(tǒng)，進(jìn)程都是擁有系統(tǒng)資源的一個(gè)獨(dú)立單位，它可以擁有自己的資源。一般地說(shuō)，線程自己不擁有系統(tǒng)資源（也有一點(diǎn)必不可少的資源），但它可以訪問(wèn)其隸屬進(jìn)程的資源。亦即一個(gè)進(jìn)程的代碼段、數(shù)據(jù)段以及系統(tǒng)資源（如已打開(kāi)的文件、I/O設(shè)備等），可供同一進(jìn)程的其他所有線程共享。線程的概念擁有資源

由于在創(chuàng)建或撤消進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O設(shè)備等。因此，操作系統(tǒng)所付出的開(kāi)銷將顯著地大于在創(chuàng)建或撤消線程時(shí)的開(kāi)銷。在進(jìn)行進(jìn)程切換時(shí)，涉及到整個(gè)當(dāng)前進(jìn)程CPU環(huán)境的保存環(huán)境的設(shè)置以及新被調(diào)度運(yùn)行的進(jìn)程的CPU環(huán)境的設(shè)置。線程切換只需保存和設(shè)置少量寄存器的內(nèi)容，并不涉及存儲(chǔ)器管理方面的操作。因此進(jìn)程切換的開(kāi)銷遠(yuǎn)大于線程切換的開(kāi)銷。由于同一進(jìn)程中的多個(gè)線程具有相同的地址空間，致使它們之間的同步和通信的實(shí)現(xiàn)也變得比較容易。線程的概念線程的結(jié)構(gòu)線程的概念線程控制塊(ThreadControlBlock，TCB)：線程控制塊是標(biāo)志線程存在的數(shù)據(jù)結(jié)構(gòu)，其中包含系統(tǒng)對(duì)于線程進(jìn)行管理所需要的全部信息線程的實(shí)現(xiàn)方式用戶級(jí)線程(UserLevelThread)在用戶層通過(guò)線程庫(kù)來(lái)實(shí)現(xiàn)核心級(jí)線程(KernelLevelThread)由操作系統(tǒng)直接支持硬件線程(HardwareThread)。硬件線程就是線程在硬件執(zhí)行資源上的表現(xiàn)形式。用戶級(jí)線程和內(nèi)核級(jí)線程用戶級(jí)線程和內(nèi)核級(jí)線程用戶級(jí)線程庫(kù)是用于用戶級(jí)線程管理的例程包，支持線程的創(chuàng)建、終止，以及調(diào)度線程的執(zhí)行并保存和恢復(fù)線程的上下文，這些操作都在用戶空間進(jìn)行，無(wú)需內(nèi)核的支持。核心級(jí)線程所有管理操作都是由操作系統(tǒng)內(nèi)核完成的。內(nèi)核保存線程的狀態(tài)和上下文信息，當(dāng)一個(gè)線程執(zhí)行了引起阻塞的系統(tǒng)調(diào)用時(shí)，內(nèi)核可以調(diào)度該進(jìn)程的其他線程執(zhí)行。在多處理器系統(tǒng)上，內(nèi)核可以分派屬于同一進(jìn)程的多個(gè)線程在多個(gè)處理器上運(yùn)行，提高進(jìn)程執(zhí)行的并行度。組合模式有的操作系統(tǒng)提供了組合的線程模式，在Solaris中，用戶創(chuàng)建的多個(gè)用戶級(jí)線程被映射到一些內(nèi)核線程上，內(nèi)核線程的數(shù)目可能少于用戶級(jí)線程的數(shù)目。用戶級(jí)線程用戶級(jí)線程和內(nèi)核級(jí)線程用戶級(jí)線程優(yōu)點(diǎn)：線程不依賴于操作系統(tǒng)，可以采用與問(wèn)題相關(guān)的調(diào)度策略，靈活性好；同一進(jìn)程中的線程切換不需進(jìn)入操作系統(tǒng)，因而實(shí)現(xiàn)效率較高；有關(guān)線程的所有管理工作都由在用戶級(jí)實(shí)現(xiàn)的線程庫(kù)來(lái)支持。用戶級(jí)線程缺點(diǎn)：同一進(jìn)程中的多個(gè)線程不能真正并行；由于線程對(duì)操作系統(tǒng)不可見(jiàn)，調(diào)度在進(jìn)程級(jí)別，某進(jìn)程中的一個(gè)線程通過(guò)系統(tǒng)調(diào)用進(jìn)入操作系統(tǒng)受阻，該進(jìn)程的其它線程也不能運(yùn)行。用戶級(jí)線程特征：戶級(jí)線程的創(chuàng)建和管理等操作無(wú)須內(nèi)核參與，操作更快并行性不高，一個(gè)線程被系統(tǒng)阻塞后，整個(gè)進(jìn)程被阻塞用戶級(jí)線程和內(nèi)核級(jí)線程核心級(jí)線程通過(guò)系統(tǒng)調(diào)用由操作系統(tǒng)創(chuàng)建，線程的控制結(jié)構(gòu)TCB保存于操作系統(tǒng)空間，線程狀態(tài)轉(zhuǎn)換由操作系統(tǒng)完成，線程是CPU調(diào)度的基本單位。用戶級(jí)線程和內(nèi)核級(jí)線程核心級(jí)別線程的優(yōu)點(diǎn)是并發(fā)性好，在多CPU環(huán)境中同一進(jìn)程中的多個(gè)線程可以真正并行執(zhí)行

核心級(jí)別線程的缺點(diǎn)是線程控制和狀態(tài)轉(zhuǎn)換需要進(jìn)入操作系統(tǒng)完成，系統(tǒng)開(kāi)銷比較大.

特點(diǎn)并行性高，多個(gè)線程可被同時(shí)調(diào)度充分利用多處理器創(chuàng)建和管理代價(jià)高用戶級(jí)線程和內(nèi)核級(jí)線程多線程的映射模型對(duì)于實(shí)現(xiàn)了用戶級(jí)線程和內(nèi)核級(jí)線程的操作系統(tǒng)，用戶級(jí)線程和內(nèi)核級(jí)線程之間的可以有不同的映射方式。多對(duì)一模型一對(duì)一模型多對(duì)多模型多線程的映射模型多對(duì)一模型多對(duì)一模型把多個(gè)用戶級(jí)線程映射到一個(gè)內(nèi)核級(jí)線程。線程的管理在用戶空間實(shí)現(xiàn)，所以效率高。當(dāng)一個(gè)線程因調(diào)用系統(tǒng)調(diào)用被阻塞時(shí)，整個(gè)進(jìn)程被阻塞。用戶級(jí)線程不能在多處理器上并發(fā)執(zhí)行，不支持內(nèi)核級(jí)線程的操作系統(tǒng)使用多對(duì)一模型。一對(duì)一模型一對(duì)一模型把每個(gè)用戶級(jí)線程影射到一個(gè)內(nèi)核級(jí)線程。當(dāng)一個(gè)線程阻塞時(shí)，其他線程仍然可以運(yùn)行。實(shí)例：Windows95/98/NT/2000OS/2多線程的映射模型多對(duì)多模型多對(duì)多模型將m個(gè)用戶級(jí)線程影射到n個(gè)內(nèi)核級(jí)線程，m≥n。用戶可以創(chuàng)建所需要的用戶級(jí)線程，通過(guò)分配適當(dāng)數(shù)目的內(nèi)核級(jí)線程獲得并發(fā)執(zhí)行的優(yōu)勢(shì)并節(jié)省系統(tǒng)資源。例：Solaris2

多線程的映射模型線程生命周期線程的標(biāo)識(shí)通常用一個(gè)整數(shù)來(lái)標(biāo)識(shí)一個(gè)線程線程的創(chuàng)建自動(dòng)創(chuàng)建從main函數(shù)開(kāi)始的主線程調(diào)用函數(shù)庫(kù)接口創(chuàng)建一個(gè)新的線程（pthread_create）線程的終止執(zhí)行完畢，或者調(diào)用了pthread_exit主線程退出導(dǎo)致整個(gè)進(jìn)程會(huì)終止線程狀態(tài)的轉(zhuǎn)換線程的狀態(tài)就緒（ready）：線程等待可用的處理器。運(yùn)行（running）：線程正在被執(zhí)行。阻塞（blocked）：線程正在等待某個(gè)事件的發(fā)生（比如I/O的完成，試圖加鎖一個(gè)被上鎖的互斥量）。終止（terminated）：線程從起始函數(shù)中返回或者調(diào)用pthread_exit。線程的應(yīng)用許多任務(wù)在邏輯上涉及多個(gè)控制流，控制流具有內(nèi)在的并發(fā)性，當(dāng)其中一些控制流被阻塞時(shí)，另外一些控制流仍可繼續(xù)。在沒(méi)有線程支持的條件下，只能采用單進(jìn)程或多進(jìn)程模式，單進(jìn)程不能表達(dá)多控制流，多進(jìn)程開(kāi)銷大而且在無(wú)共享存儲(chǔ)空間的條件下進(jìn)程間交往困難。采用多線程一方面可以提高應(yīng)用程序的并行性，另一方面也使程序設(shè)計(jì)簡(jiǎn)潔明晰。例：Word文字編輯工具、Web服務(wù)器等。多線程程序設(shè)計(jì)為什么要多線程程序設(shè)計(jì)某些應(yīng)用具有內(nèi)在的多個(gè)控制流結(jié)構(gòu)，這些控制流具有合作性質(zhì)，需要共享內(nèi)存，采用多線程易于對(duì)問(wèn)題建模，從而得到最自然的解決算法；在需要多控制流的應(yīng)用中，多線程比多進(jìn)程在速度上具有絕對(duì)優(yōu)勢(shì)，統(tǒng)計(jì)測(cè)試表明，線程的建立速度比進(jìn)程的建立速度快100倍，進(jìn)程內(nèi)線程間的切換速度與進(jìn)程間切換速度也有數(shù)量級(jí)之差；采用多線程可以提高處理機(jī)與設(shè)備之間的并行性.在單控制流情形下，啟動(dòng)設(shè)備的進(jìn)程進(jìn)入核心后將被阻塞，此時(shí)該進(jìn)程的其它代碼也不能執(zhí)行.若此時(shí)無(wú)其它可運(yùn)行程序，處理機(jī)將被閑置.多線程結(jié)構(gòu)在一個(gè)線程等待時(shí)，其它線程可以繼續(xù)執(zhí)行，從而使設(shè)備和處理機(jī)并行工作；在多核環(huán)境下，多線程可以并行執(zhí)行，既可提高資源利用效率，又可提高進(jìn)程推進(jìn)速度。多線程機(jī)制多核處理器的基本結(jié)構(gòu)是共享存儲(chǔ)的，多線程程序設(shè)計(jì)技術(shù)被認(rèn)為是能夠充分挖掘共享存儲(chǔ)系統(tǒng)性能潛力的最有效的技術(shù)。多線程機(jī)制的優(yōu)點(diǎn)：創(chuàng)建一個(gè)線程比創(chuàng)建一個(gè)進(jìn)程代價(jià)要??；線程之間的切換比進(jìn)程間的切換代價(jià)?。怀浞掷枚嗵幚砥?；數(shù)據(jù)共享；快速響應(yīng)特性；多線程編程可以使程序更加更加模塊化，簡(jiǎn)化程序邏輯。多線程機(jī)制在多處理器系統(tǒng)上，如果一個(gè)應(yīng)用具有如下特征，就可以利用多線程技術(shù)達(dá)到目標(biāo)：前臺(tái)后臺(tái)操作；異步處理；需要加速執(zhí)行；模塊化程序結(jié)構(gòu)。多線程環(huán)境下的進(jìn)程控制語(yǔ)義單線程環(huán)境下的進(jìn)程控制接口在多線程環(huán)境下語(yǔ)義可能會(huì)發(fā)生變化，包括進(jìn)程創(chuàng)建、進(jìn)程終止、進(jìn)程執(zhí)行、信號(hào)處理等操作。

進(jìn)程創(chuàng)建創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用完成后，被創(chuàng)建的新進(jìn)程復(fù)制調(diào)用進(jìn)程的內(nèi)容，當(dāng)進(jìn)程的一個(gè)線程中創(chuàng)建一個(gè)子進(jìn)程，新的進(jìn)程可以復(fù)制整個(gè)進(jìn)程（包括所有線程）也可以只復(fù)制調(diào)用線程的內(nèi)容；執(zhí)行新的程序在進(jìn)程中執(zhí)行新的程序，函數(shù)的語(yǔ)義在多線程環(huán)境下沒(méi)有發(fā)生大的變化。exec將會(huì)終止所有的線程，用新的程序覆蓋進(jìn)程的地址空間，并開(kāi)始執(zhí)行新的程序；多線程環(huán)境下的進(jìn)程控制語(yǔ)義進(jìn)程結(jié)束在任何一個(gè)線程中調(diào)用exit將會(huì)結(jié)束整個(gè)進(jìn)程，另外從主線程返回也等同于調(diào)用exit而導(dǎo)致進(jìn)程結(jié)束。如果要從線程中退出則調(diào)用專用的線程退出函數(shù)。信號(hào)處理信號(hào)是UNIX系統(tǒng)中通知進(jìn)程的重要機(jī)制。信號(hào)可能是同步的也可能是異步的。發(fā)送給進(jìn)程的信號(hào)在多線程環(huán)境下有多種選擇：發(fā)送給引發(fā)信號(hào)的線程；發(fā)送給所有的線程；發(fā)送個(gè)特定的線程；指定一個(gè)線程處理所有的信號(hào)。多線程帶來(lái)的問(wèn)題由于線程共享同一進(jìn)程的內(nèi)存空間，多個(gè)線程可能需要同時(shí)訪問(wèn)同一個(gè)數(shù)據(jù)。對(duì)共享數(shù)據(jù)的并發(fā)訪問(wèn)可能導(dǎo)致數(shù)據(jù)的不一致性.如果沒(méi)有正確的保護(hù)措施，對(duì)共享數(shù)據(jù)的訪問(wèn)會(huì)造成數(shù)據(jù)的不一致和錯(cuò)誤。競(jìng)爭(zhēng)條件若干進(jìn)程并發(fā)地訪問(wèn)并且操縱共享數(shù)據(jù)的情況;共享數(shù)據(jù)的值取決于哪個(gè)進(jìn)程最后完成;防止競(jìng)爭(zhēng)條件，并發(fā)進(jìn)程必須被同步.線程的同步例：如果一個(gè)進(jìn)程有一個(gè)共享變量counter，兩個(gè)線程producer和consumer，線程producer執(zhí)行counter++，線程consumer執(zhí)行counter--，這兩個(gè)操作都需要多個(gè)機(jī)器指令來(lái)完成，Counter=5counter++counter--register1=counterregister2=counterregister1=register1+1register2=register2-1counter=register1counter=register2可能的序列：Producer:register1=counter(register1=5)Producer:register1=register1+1(register1=6)Consumer:register2=counter(register2=5)Consumer:register2=register2-1(register2=6)Producer:counter=register1(counter=6)Consumer:counter=register2(counter=4)線程的同步同步：一組進(jìn)程（線程）,為了協(xié)調(diào)其推進(jìn)速度,在某些點(diǎn)處需要相互等待與相互喚醒,進(jìn)程之間這種相互制約的關(guān)系稱作進(jìn)程同步，簡(jiǎn)稱同步(synchronization).進(jìn)程同步是進(jìn)程之間直接的相互作用形式,是合作進(jìn)程之間有意識(shí)的行為,這種相互作用只發(fā)生在相關(guān)的進(jìn)程之間。進(jìn)程合作(cooperation)：一組進(jìn)程，如果它們單獨(dú)不能正常進(jìn)行,但并發(fā)可以正常進(jìn)行,稱這種現(xiàn)象為進(jìn)程合作，參與合作的進(jìn)程稱作合作進(jìn)程(cooperatingprocess)。線程的同步同步例子：要求:(1)關(guān)車門后方能啟動(dòng)車輛;(2)到站停車后方能開(kāi)車門.同步機(jī)制

同步機(jī)制：用于實(shí)現(xiàn)進(jìn)程間同步的工具稱作同步機(jī)制，亦稱同步設(shè)施(synchronizationmechanism)同步機(jī)制應(yīng)當(dāng)滿足如下幾個(gè)基本要求:描述能力夠用：即用此種同步機(jī)制應(yīng)當(dāng)能夠描述操作系統(tǒng)及并發(fā)程序設(shè)計(jì)中所遇到的各種同步問(wèn)題；可以實(shí)現(xiàn)；效率高；使用方便。順序程序程序的順序性包括內(nèi)部順序性和外部順序性。內(nèi)部順序性：對(duì)于一個(gè)進(jìn)程來(lái)說(shuō),它的所有指令是按序執(zhí)行的；外部順序性,對(duì)于多個(gè)進(jìn)程來(lái)說(shuō),所有進(jìn)程是依次執(zhí)行的。P1活動(dòng):a1a2a3a4，P2活動(dòng):b1b2b3b4順序執(zhí)行時(shí),有如下兩種情形:情形1:a1a2a3a4b1b2b3b4情形2:b1b2b3b4a1a2a3a4線程的同步順序程序的特性順序性：處理機(jī)嚴(yán)格按照指令次序依次執(zhí)行，即僅當(dāng)一條指令執(zhí)行完后才開(kāi)始執(zhí)行下一條指令；封閉性：程序在執(zhí)行過(guò)程中獨(dú)占系統(tǒng)中的全部資源，該程序的運(yùn)行環(huán)境只與其自身動(dòng)作有關(guān)，不受其它程序及外界因素影響；可再現(xiàn)性：程序的執(zhí)行結(jié)果與執(zhí)行速度無(wú)關(guān)，而只與初始條件有關(guān)，給定相同的初始條件，程序的任意多次執(zhí)行一定得到相同的執(zhí)行結(jié)果.線程的同步并發(fā)程序程序的并發(fā)性含義：內(nèi)部并發(fā)性，對(duì)于一個(gè)進(jìn)程來(lái)說(shuō)，它的所有指令可能按序執(zhí)行，也可能不按次序執(zhí)行；外部并發(fā)性：對(duì)于多個(gè)進(jìn)程來(lái)說(shuō)，所有進(jìn)程是交叉(interleave)