多核編程技術(shù)課件

第8章多核并發(fā)（并行）程序設(shè)計(jì)主講:黎忠文2023/8/181第8章多核并發(fā)（并行）程序設(shè)計(jì)主講:黎忠文2023/8目錄8.1什么是多核并發(fā)(并行)程序設(shè)計(jì)8.2為什么要學(xué)習(xí)多核程序設(shè)計(jì)8.3多核并發(fā)程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/182目錄2023/8/428.1什么是多核并發(fā)（并行）程序設(shè)計(jì)8.1.1并發(fā)與并行的區(qū)別是什么？

并發(fā)與并行是兩個(gè)既相似而又不相同的概念：并發(fā)性，又稱共行性，是指能處理多個(gè)同時(shí)性活動(dòng)的能力；并行是指同時(shí)發(fā)生的兩個(gè)并發(fā)事件，具有并發(fā)的含義，而并發(fā)則不一定并行，也亦是說(shuō)并發(fā)事件之間不一定要同一時(shí)刻發(fā)生。本課程中并發(fā)和并行概念基本相同,都包含同時(shí)性,同時(shí)并發(fā)的概念含義更廣泛一些。

2023/8/1838.1什么是多核并發(fā)（并行）程序設(shè)計(jì)8.1.1并發(fā)與8.1.2什么是并行計(jì)算？并行計(jì)算是相對(duì)于串行計(jì)算來(lái)說(shuō)的，所謂并行計(jì)算分為時(shí)間上的并行和空間上的并行。時(shí)間上的并行就是指流水線技術(shù)，而空間上的并行則是指用多個(gè)處理器并發(fā)的執(zhí)行計(jì)算。并行計(jì)算科學(xué)中主要研究的是空間上的并行問(wèn)題。空間上的并行導(dǎo)致了兩類并行機(jī)的產(chǎn)生，按照Flynn的說(shuō)法分為：?jiǎn)沃噶盍鞫鄶?shù)據(jù)流（SIMD）和多指令流多數(shù)據(jù)流（MIMD）。我們常用的串行機(jī)也叫做單指令流單數(shù)據(jù)流（SISD）。8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)2023/8/1848.1.2什么是并行計(jì)算？8.1什么是多核并發(fā)（并行8.1.3

什么是多核處理器？?jī)蓚€(gè)或多個(gè)獨(dú)立運(yùn)行的內(nèi)核集成于同一個(gè)處理器上面雙核處理器=一個(gè)處理器上包含2個(gè)內(nèi)核多核處理器=一個(gè)處理器上包含2個(gè)或多個(gè)內(nèi)核Core0Core1FrontSideBus8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)2023/8/1858.1.3什么是多核處理器？Core0Core1Fron8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)8.1.4為什么要采用多核技術(shù)？2023/8/1868.1什么是多核并發(fā)（并行）程序設(shè)計(jì)8.1.4為什么8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)最終目標(biāo):提升用戶的體驗(yàn)?zāi)柖伞粩喟l(fā)展和改進(jìn)處理器的性能最大限度地利用越來(lái)越多的晶體管實(shí)現(xiàn)最優(yōu)的價(jià)值縮減處理時(shí)間，提高計(jì)算能力開(kāi)發(fā)平臺(tái)的新特性和新功能2023/8/1878.1什么是多核并發(fā)（并行）程序設(shè)計(jì)最終目標(biāo):提升用戶2005+Dual-andMulti-core2-waySMPsystem4Cores>4Threads2001Hyper-Threading2-waySMPsystem2Cores4Threads1995Multi-processing2-waySMPsystem2Cores2Threads通過(guò)并行方式改進(jìn)處理器的性能8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)2023/8/1882005+2-waySMPsystem20012-way8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)CacheExecutionStateStateBusCacheExecutionStateBusCacheExecutionStateBusCacheExecutionStateBusCacheExecutionStateBusPentium4withHTDualXeonProcessorsDualCore2Threads1Package2Threads2Packages2Threads1PackageTwoindependentexecutioncoresinthesameprocessor多核技術(shù)的發(fā)展2023/8/1898.1什么是多核并發(fā)（并行）程序設(shè)計(jì)CacheExecu幾種不同的技術(shù)HT–HyperThreading:

2threadsrunningonthesameprocessorcore處理器上的某些資源會(huì)被共享使用相同的緩存和運(yùn)算器DC–DualCore:

2executioncoresinthesameprocessorpackage共享系統(tǒng)總線與雙處理器的性能相同DP/MP–Dual/Multi-Processing:

2ormoreprocessorsinthesamesystem只共享系統(tǒng)總線，獨(dú)立緩存高性能，資源沖突少8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)2023/8/1810幾種不同的技術(shù)HT–HyperThreading:28.1什么是多核并發(fā)（并行）程序設(shè)計(jì)雙核技術(shù)VS.超線程技術(shù)雙核是真正意義上的雙處理器不會(huì)發(fā)生資源沖突每個(gè)線程擁有自己的緩存、寄存器和運(yùn)算器一個(gè)3.2GHzSmithfield在性能上并非等同于3.2GHzP4withHT的2倍HT使處理器的性能至少提升了1/3雙核的性能相當(dāng)于2塊non-HT處理器2023/8/18118.1什么是多核并發(fā)（并行）程序設(shè)計(jì)雙核技術(shù)VS.8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)Singlecore,WithHT(Eg.Pentium4ProcessorWithHT)IntegerandFloatingPointThreadsL2CacheandControlL2CacheandControl

L1D-CacheandD-TLBSchedulersIntegerTraceCacheRename/AllocuopQueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPoint2threadscanbeexecutedatthesametime(perprocessor)ifthey’renotcompetingforthesameexecutionresource2023/8/18128.1什么是多核并發(fā)（并行）程序設(shè)計(jì)L2Cachea8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)Singlecore,WithHT(Eg.Pentium4ProcessorwithHT)TwoFloatingPointThreadsL2CacheandControlL2CacheandControl

L1D-CacheandD-TLBSchedulersIntegerTraceCacheRename/AllocuopQueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPoint2threadsCANNOTbeexecutedatthesametime(perprocessor)ifthey’recompetingforthesameexecutionresource(eg.2floatingpointthreadsinaP4Parchitecture)2023/8/18138.1什么是多核并發(fā)（并行）程序設(shè)計(jì)L2Cachea8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)Dualcore,WithoutHT(Eg.PentiumDProcessor)TwoFloatingPointThreadsL2CacheandControlL2CacheandControl

L1D-CacheandD-TLBSchedulersIntegerTraceCacheRename/AllocuopQueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPointL2CacheandControlL2CacheandControl

L1D-CacheandD-TLBSchedulersIntegerTraceCacheRename/AllocuopQueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPointEven2floatingpointthreadscanbeexecutedatthesametimenow(perprocessor)astherearemultiplefloatingpointexecutionunits2023/8/18148.1什么是多核并發(fā)（并行）程序設(shè)計(jì)L2Cachea8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)Dualcore,WithHT(Eg.DualCorePentiumProcessorExtremeEdition)SupportsHTMultipleIntegerandFloatingPointThreadsL2CacheandControlL2CacheandControl

L1D-CacheandD-TLBSchedulersIntegerTraceCacheRename/AllocuopQueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPointL2CacheandControlL2CacheandControl

L1D-CacheandD-TLBSchedulersIntegerTraceCacheRename/AllocuopQueuesBTBuCodeROM33DecoderBTB&I-TLBFloatingPointWithdualcore&HTtogether,maximum#ofthreadsthatcanbeexecutedatatimeis4perprocessor2023/8/18158.1什么是多核并發(fā)（并行）程序設(shè)計(jì)L2Cachea多核技術(shù)與超線程技術(shù)的結(jié)合產(chǎn)量…多功能…功效Core0Core1FrontSideBusDualCorewithHyper-Threading4threads/socket

Core0Core1FrontSideBusDualCore2threads/socket

8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)2023/8/1816多核技術(shù)與超線程技術(shù)的結(jié)合產(chǎn)量…多功能AMD與Intel雙核架構(gòu)的對(duì)比AMD

Opteron雙核架構(gòu)示意圖

Intel奔騰至尊版雙核架構(gòu)示意圖

8.1

什么是多核并發(fā)（并行）程序設(shè)計(jì)2023/8/1817AMD與Intel雙核架構(gòu)的對(duì)比AMDOpteron雙核架DualCore、SMP、Cluster體系結(jié)構(gòu)特性SMP（對(duì)稱多處理機(jī)）Cluster（集群）DualCore處理器單一主機(jī)，多個(gè)處理器多臺(tái)主機(jī)，有各自的處理器（一或多）單一主機(jī)，單一處理器，多個(gè)核心操作系統(tǒng)單一多個(gè)單一主要并行計(jì)算方式多進(jìn)程，內(nèi)存共享多進(jìn)程，基于消息傳遞多線程8.1什么是多核并發(fā)（并行）程序設(shè)計(jì)2023/8/1818DualCore、SMP、Cluster體系結(jié)構(gòu)特性SMP（8.2為什么要學(xué)習(xí)多核程序設(shè)計(jì)8.2.1背景：科學(xué)技術(shù)的發(fā)展呼喚巨大的、不斷增長(zhǎng)的計(jì)算能力中長(zhǎng)期天氣預(yù)報(bào)。每增加一天，要求計(jì)算速度增加一個(gè)數(shù)量級(jí)。三天百萬(wàn)次/sec，四天千萬(wàn)次/sec，五天億次/sec信息戰(zhàn)。關(guān)鍵是對(duì)信息的處理速度，如雷達(dá)信息的處理地震預(yù)報(bào)預(yù)測(cè)石油勘測(cè)生物信息處理……2023/8/18198.2為什么要學(xué)習(xí)多核程序設(shè)計(jì)8.2.1背景：科學(xué)技8.2.2提高計(jì)算能力的基本途徑器件：新工藝（超大規(guī)模集成電路）新材料（生物計(jì)算機(jī)、光計(jì)算機(jī)）系統(tǒng)結(jié)構(gòu)的改進(jìn)：主要是克服VonNeumann的瓶頸問(wèn)題。 流水線計(jì)算機(jī)、向量計(jì)算機(jī)、多處理機(jī)、并行計(jì)算機(jī)、集群。8.2為什么要學(xué)習(xí)多核程序設(shè)計(jì)2023/8/18208.2.2提高計(jì)算能力的基本途徑8.2為什么要學(xué)習(xí)多8.2.3現(xiàn)實(shí)狀況計(jì)算能力幾乎提高了上萬(wàn)倍，但是，實(shí)際的并行計(jì)算能力提高只有幾十倍。原因：不能利用計(jì)算機(jī)的并行處理能力。也就是沒(méi)有解決并行計(jì)算中的并行程序設(shè)計(jì)的問(wèn)題。其核心問(wèn)題是并行算法

Back8.2為什么要學(xué)習(xí)多核程序設(shè)計(jì)2023/8/18218.2.3現(xiàn)實(shí)狀況Back8.2為什么要學(xué)習(xí)多核程序8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境

及開(kāi)發(fā)方法8.3.1硬件系統(tǒng)

并行計(jì)算機(jī)系統(tǒng)分類按指令與數(shù)據(jù)分

SIMD，MIMD，SPMD，MPMD按存儲(chǔ)方式分 共享內(nèi)存，分布式內(nèi)存，分布式共享內(nèi)存2023/8/18228.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法8.3.1指令與數(shù)據(jù)SIMD(Single-InstructionMultiple-Data)，同時(shí)用相同的指令對(duì)不同的數(shù)據(jù)進(jìn)行操作MIMD(Multiple-InstructionMultiple-Data)，同時(shí)有多條指令對(duì)不同的數(shù)據(jù)進(jìn)行操作SPMD(Single-ProgramMultuple-Data)，同時(shí)執(zhí)行相同的程序?qū)Σ煌瑪?shù)據(jù)操作MPMD(Multiple-ProgramMultuple-Data)，同時(shí)有多個(gè)程序?qū)Σ煌臄?shù)據(jù)進(jìn)行操作8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1823指令與數(shù)據(jù)8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2存儲(chǔ)方式8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1824存儲(chǔ)方式8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法208.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法8.3.2軟件系統(tǒng)開(kāi)發(fā)人員已經(jīng)設(shè)計(jì)并實(shí)現(xiàn)了一些有趣的編程模型，有助于開(kāi)發(fā)并行應(yīng)用程序，最流行的就是用于共享內(nèi)存編程的OpenMP和用于分布式內(nèi)存編程的MPI。2023/8/18258.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法8.3.2.

共享內(nèi)存編程的OpenMP

OpenMP是一種工業(yè)標(biāo)準(zhǔn)的API設(shè)計(jì)規(guī)范，是由Sun、HP、IBM和Intel等多家頂級(jí)計(jì)算機(jī)廠商和軟件開(kāi)發(fā)商聯(lián)手推出的，其目的在于為軟件開(kāi)發(fā)人員提供一種通用的規(guī)范，使其可以很方便地設(shè)計(jì)新并行應(yīng)用程序或修改及并行化現(xiàn)有串行應(yīng)用程序，從而利用配置了多處理器計(jì)算系統(tǒng)的共享內(nèi)存?？梢浦残砸彩荗penMP的主要目標(biāo)之一，使用OpenMP開(kāi)發(fā)的并行應(yīng)用程序源代碼可由支持OpenMP的任何編譯器編譯，且編譯好的二進(jìn)制代碼可在目標(biāo)硬件平臺(tái)上運(yùn)行，以獲得出色的并行性能。8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1826.共享內(nèi)存編程的OpenMP8.3多核8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/18278.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/88.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法

最流行的本地編程語(yǔ)言Fortran和C/C++都支持OpenMP。上圖給出了分別以C/C++和Fortran編寫的簡(jiǎn)單OpenMP程序示例。在本例中，將y數(shù)組加到x數(shù)組這一循環(huán)迭代操作，是以并行方式執(zhí)行的。源代碼中的編譯指示、指令和編程API調(diào)用表示了OpenMP的結(jié)構(gòu)。OpenMP的結(jié)構(gòu)允許程序員指定并行區(qū)域、同步和數(shù)據(jù)作用域?qū)傩?，它還支持用于指定運(yùn)行時(shí)配置的環(huán)境變量，例如，環(huán)境變量OMP_NUM_THREADS指定了運(yùn)行時(shí)所使用的工作線程的數(shù)量。

2023/8/18288.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法最流行

分布式內(nèi)存編程的MPI什么是MPI？

是一個(gè)庫(kù)而不是一門語(yǔ)言 是一種標(biāo)準(zhǔn)或規(guī)范的代表而不特指某一個(gè)對(duì)它的具體實(shí)現(xiàn) 是一種消息傳遞編程模型并成為這種編程模型的代表和事實(shí)上的標(biāo)準(zhǔn) 對(duì)MPI的使用必須和特定的語(yǔ)言結(jié)合起來(lái)進(jìn)行：C,JAVA,FORTRAN目前主要的MPI實(shí)現(xiàn)

MPICH:/mpi/mpich Chimp:ftp://ftp.epcc.ed.ac.uk/pub/packages/chimp/release/ Lam :/lam/8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1829分布式內(nèi)存編程的MPI8.3多核并發(fā)（MPI并行程序設(shè)計(jì)平臺(tái)由標(biāo)準(zhǔn)消息傳遞函數(shù)及相關(guān)輔助函數(shù)構(gòu)成，多個(gè)進(jìn)程通過(guò)調(diào)用這些函數(shù)（類似調(diào)用子程序），進(jìn)行通信；

一個(gè)程序同時(shí)啟動(dòng)多份，形成多個(gè)獨(dú)立的進(jìn)程，在不同的處理機(jī)上運(yùn)行，擁有獨(dú)立的內(nèi)存空間，進(jìn)程間通信通過(guò)調(diào)用MPI函數(shù)來(lái)實(shí)現(xiàn)；每個(gè)進(jìn)程開(kāi)始執(zhí)行時(shí)，將獲得一個(gè)唯一的序號(hào)（rank）。例如啟動(dòng)P個(gè)進(jìn)程，序號(hào)依次為0，1，…，P-1；MPI并行進(jìn)程的實(shí)現(xiàn)8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1830MPI并行程序設(shè)計(jì)平臺(tái)由標(biāo)準(zhǔn)消息傳遞函數(shù)及相關(guān)輔助函數(shù)構(gòu)成，

消息傳遞是相對(duì)于進(jìn)程間通信方式而言的，與具體并行機(jī)存儲(chǔ)模式無(wú)關(guān)，任何支持進(jìn)程間通信的并行機(jī)，均可支持消息傳遞并行程序設(shè)計(jì)；幾乎有共享和分布存儲(chǔ)并行計(jì)算環(huán)境均支持進(jìn)程間的消息傳遞通信；進(jìn)程0發(fā)送一個(gè)整數(shù)給進(jìn)程1；進(jìn)程1將該數(shù)加1，傳遞給進(jìn)程2；進(jìn)程2再將該數(shù)加1，再傳遞給進(jìn)程3；依次類推，最后，進(jìn)程N(yùn)-1將該數(shù)傳遞給進(jìn)程0，由進(jìn)程1負(fù)責(zé)廣播該數(shù)給所有進(jìn)程，并打印輸出。

進(jìn)程1傳遞信息進(jìn)程3傳遞信息進(jìn)程2傳遞信息進(jìn)程0傳遞信息8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1831消息傳遞是相對(duì)于進(jìn)程間通信方式而言的，與具體并行機(jī)存儲(chǔ)模8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法8.3.3多核并發(fā)（并行）開(kāi)發(fā)方法PRAM模型，BSP模型，logP模型，C3模型功能設(shè)計(jì)，分治設(shè)計(jì)，平衡樹(shù)設(shè)計(jì)，倍增設(shè)計(jì)2023/8/18328.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法8.3.38.3.4多核并發(fā)（并行）開(kāi)發(fā)的四個(gè)階段劃分(Partitioning)：分解成小的任務(wù)，開(kāi)拓并發(fā)性；通訊(Communication)：確定諸任務(wù)間的數(shù)據(jù)交換，監(jiān)測(cè)劃分的合理性；組合(Agglomeration)：依據(jù)任務(wù)的局部性，組合成更大的任務(wù)；映射(Mapping)：將每個(gè)任務(wù)分配到處理器上，提高算法的性能。8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/18338.3.4多核并發(fā)（并行）開(kāi)發(fā)的四個(gè)階段8.3多核并PCAM設(shè)計(jì)過(guò)程8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1834PCAM設(shè)計(jì)過(guò)程8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)劃分判據(jù)劃分是否具有靈活性？劃分是否避免了冗余計(jì)算和存儲(chǔ)？劃分任務(wù)尺寸是否大致相當(dāng)？任務(wù)數(shù)與問(wèn)題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1835劃分判據(jù)8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法20通訊通訊是PCAM設(shè)計(jì)過(guò)程的重要階段；劃分產(chǎn)生的諸任務(wù)，一般不能完全獨(dú)立執(zhí)行，需要在任務(wù)間進(jìn)行數(shù)據(jù)交流；從而產(chǎn)生了通訊；功能分解確定了諸任務(wù)之間的數(shù)據(jù)流；諸任務(wù)是并發(fā)執(zhí)行的，通訊則限制了這種并發(fā)性；8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1836通訊8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023通訊判據(jù)所有任務(wù)是否執(zhí)行大致相當(dāng)?shù)耐ㄓ?是否盡可能的局部通訊？通訊操作是否能并行執(zhí)行?同步任務(wù)的計(jì)算能否并行執(zhí)行？8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1837通訊判據(jù)8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法20組合組合是由抽象到具體的過(guò)程，是將組合的任務(wù)能在一類并行機(jī)上有效的執(zhí)行；合并小尺寸任務(wù)，減少任務(wù)數(shù)。如果任務(wù)數(shù)恰好等于處理器數(shù)，則也完成了映射過(guò)程；通過(guò)增加任務(wù)的粒度和重復(fù)計(jì)算，可以減少通訊成本；保持映射和擴(kuò)展的靈活性，降低軟件工程成本；8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1838組合8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023組合判據(jù)增加粒度是否減少了通訊成本？重復(fù)計(jì)算是否已權(quán)衡了其得益？是否保持了靈活性和可擴(kuò)放性？組合的任務(wù)數(shù)是否與問(wèn)題尺寸成比例?是否保持了類似的計(jì)算和通訊？有沒(méi)有減少并行執(zhí)行的機(jī)會(huì)？8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1839組合判據(jù)8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法20映射每個(gè)任務(wù)要映射到具體的處理器，定位到運(yùn)行機(jī)器上；任務(wù)數(shù)大于處理器數(shù)時(shí)，存在負(fù)載平衡和任務(wù)調(diào)度問(wèn)題；映射的目標(biāo)：減少算法的執(zhí)行時(shí)間并發(fā)的任務(wù)不同的處理器任務(wù)之間存在高通訊的同一處理器映射實(shí)際是一種權(quán)衡，屬于NP完全問(wèn)題8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1840映射8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023映射判據(jù)采用集中式負(fù)載平衡方案，是否存在通訊瓶頸？采用動(dòng)態(tài)負(fù)載平衡方案，調(diào)度策略的成本如何？8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法2023/8/1841映射判據(jù)8.3多核并發(fā)（并行）程序設(shè)計(jì)環(huán)境及開(kāi)發(fā)方法208.4.1網(wǎng)絡(luò)處理器的由來(lái)

在網(wǎng)絡(luò)發(fā)展初期，網(wǎng)絡(luò)傳輸?shù)乃俾瘦^低，帶寬一般不超過(guò)155Mb/s(SONET的OC-3)，這個(gè)時(shí)期的網(wǎng)絡(luò)處理設(shè)備一般是基于CPU，即通過(guò)在CPU上運(yùn)行相關(guān)軟件來(lái)實(shí)現(xiàn)各種網(wǎng)絡(luò)功能。這種方法有很大的好處是有很大的靈活性，可以通過(guò)更新軟件來(lái)完善原有的功能或加入新的功能。這種方法能滿足當(dāng)時(shí)的網(wǎng)絡(luò)處理性能要求。網(wǎng)絡(luò)通信的瓶頸是帶寬而不是處理器的性能。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/18428.4.1網(wǎng)絡(luò)處理器的由來(lái)8.4IXP2400平臺(tái)上

隨著光纖通訊的出現(xiàn)，網(wǎng)絡(luò)帶寬已經(jīng)達(dá)到了10Gb/s(OC-192)甚至40Gb/s（OC-768）,大大超過(guò)了通用CPU的處理速度。帶寬已經(jīng)不是網(wǎng)絡(luò)的瓶頸，而基于軟件的節(jié)點(diǎn)設(shè)備逐漸變成了網(wǎng)絡(luò)的瓶頸。因此，需要想辦法提高網(wǎng)絡(luò)設(shè)備的性能。這時(shí)先出現(xiàn)的是ASIC（ApplicationSpecificIntegratedCircuit,專用集成電路）。ASIC通過(guò)把指令或計(jì)算邏輯固化到硬件中，由此獲得很高的處理速度。因此它能夠滿足網(wǎng)絡(luò)設(shè)備對(duì)性能的要求。ASIC在完成規(guī)定的處理工作方面是相當(dāng)出色的，但是，它也有不足之處，開(kāi)發(fā)周期太長(zhǎng)和不可編程的弊端。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1843隨著光纖通訊的出現(xiàn)，網(wǎng)絡(luò)帶寬已經(jīng)達(dá)到了10Gb/s(正因?yàn)樯厦娴膬煞N方案都不能很好的完成網(wǎng)絡(luò)處理的要求。因此，一種新的可編程、專門用于網(wǎng)絡(luò)處理的的處理器就出現(xiàn)了。它既有網(wǎng)絡(luò)服務(wù)所需的高性能，又有高靈活性。網(wǎng)絡(luò)處理其通過(guò)良好的體系結(jié)構(gòu)設(shè)計(jì)和專門針對(duì)網(wǎng)絡(luò)處理優(yōu)化的部件，提供了一個(gè)可編程控制環(huán)境，可以很好的解決硬件加速和軟件可擴(kuò)展的問(wèn)題。它同通用的處理器的不同之處在于：網(wǎng)絡(luò)處理器是為優(yōu)化包處理而設(shè)計(jì)的，它將包以其到達(dá)的速度送到下一個(gè)節(jié)點(diǎn);而通用處理器則要處理范圍很大的各種指令。同時(shí)，如果需要新的功能或新的標(biāo)準(zhǔn)，網(wǎng)絡(luò)處理器可通過(guò)編程來(lái)實(shí)現(xiàn)，以滿足各種各樣的網(wǎng)絡(luò)應(yīng)用。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1844正因?yàn)樯厦娴膬煞N方案都不能很好的完成網(wǎng)絡(luò)處理的要求。因此，一通用處理器，ASIC和網(wǎng)絡(luò)處理器的比較表8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1845通用處理器，ASIC和網(wǎng)絡(luò)處理器的比較表8.4IXP248.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)8.4.2網(wǎng)絡(luò)處理器的體系結(jié)構(gòu)

網(wǎng)絡(luò)處理器是一種專門用于網(wǎng)絡(luò)包處理的CPU，它的設(shè)計(jì)充分結(jié)合了網(wǎng)絡(luò)環(huán)境中數(shù)據(jù)流的特點(diǎn)。網(wǎng)絡(luò)處理器由兩類硬件功能單元組成，即網(wǎng)絡(luò)處理單元（NetworkProcessorUnit，NPU）和專用的智能協(xié)處理單元。NPU是網(wǎng)絡(luò)處理器核心，它提供高速、大容量的數(shù)據(jù)包智能處理功能，其中包括數(shù)據(jù)包解析、分類和轉(zhuǎn)發(fā)等，因此網(wǎng)絡(luò)處理器單元經(jīng)常被稱為數(shù)據(jù)包處理引擎（PacketProcessEngine,PPE）,而不同的協(xié)處理器則實(shí)現(xiàn)幀分段、重組、分組分類查找、隊(duì)列緩沖管理、順序管理、存儲(chǔ)器控制和多播支持等功能。2023/8/18468.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)8.48.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)網(wǎng)絡(luò)處理器結(jié)構(gòu)如下圖:2023/8/18478.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)網(wǎng)絡(luò)處8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)其主要部分說(shuō)明如下：a)片內(nèi)處理器

網(wǎng)絡(luò)處理器內(nèi)部包含多個(gè)片內(nèi)處理器，構(gòu)成多處理器單元。片內(nèi)處理器可分為核心處理器和處理引擎兩種類型。前者用于系統(tǒng)維護(hù)和管理，后者用于快速數(shù)據(jù)處理，提供分類、調(diào)度等多種服務(wù)功能。處理引擎可以包括多個(gè)硬件線程，每個(gè)線程都有一套專門的硬來(lái)存放程序運(yùn)行的上下文，可實(shí)現(xiàn)線程切換的零開(kāi)銷。b）高速I/O接口單元

網(wǎng)絡(luò)處理器有多個(gè)I/O接口單元，包括物理鏈路接口、存儲(chǔ)接口、存儲(chǔ)器接口以及其他外部處理單元的接口等。2023/8/18488.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)其主要8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)c)內(nèi)部高速總線

以上多組處理器和I/O接口單元通過(guò)內(nèi)部高速總線連接在一起，組成高速數(shù)據(jù)通路結(jié)構(gòu)，從而提供強(qiáng)大的硬件并行處理能力。d)存儲(chǔ)器

網(wǎng)絡(luò)處理器的存儲(chǔ)器一般有數(shù)個(gè)不同性能的存儲(chǔ)結(jié)構(gòu)，以適應(yīng)不同的應(yīng)用任務(wù)。e)專業(yè)指令集

片內(nèi)轉(zhuǎn)發(fā)引擎一般具有專業(yè)的精簡(jiǎn)指令集，這些指令都經(jīng)過(guò)針對(duì)網(wǎng)絡(luò)數(shù)據(jù)吹的優(yōu)化，例如數(shù)據(jù)讀寫、狀態(tài)判斷、堆棧操作、哈希查找等。f)專業(yè)組件（協(xié)處理器）

使用高速處理的通用功能模塊，來(lái)提高系統(tǒng)性能。2023/8/18498.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)c)8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)8.4.3Intel網(wǎng)絡(luò)處理器Intel網(wǎng)絡(luò)處理器是Intel公司為快速實(shí)現(xiàn)網(wǎng)絡(luò)通信服務(wù)而開(kāi)發(fā)生產(chǎn)的，它具有高速，并行性處理的特點(diǎn)。Intel網(wǎng)絡(luò)處理器有Ixp1200，Ixp2400，Ixp2800等。Intel網(wǎng)絡(luò)處理器的技術(shù)基礎(chǔ)是Intel互聯(lián)網(wǎng)交換架構(gòu)（IntelInternetExchangeArchitecture）,簡(jiǎn)稱IntelIXA。IntelIXA包括三個(gè)主要部分：IntelXScale技術(shù)、微引擎技術(shù)（microengine）和IntelIXA可移動(dòng)架構(gòu)。2023/8/18508.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)8.4XScale

：通用RISC處理器，用于初始化、管理芯片和高層應(yīng)用、網(wǎng)絡(luò)處理任務(wù)。微引擎：N個(gè)可編程的專用網(wǎng)絡(luò)數(shù)據(jù)處理器，主要用于處理數(shù)據(jù)包。IntelIXA可移動(dòng)架構(gòu)：一個(gè)易于使用的可編程模塊化框架，允許不同網(wǎng)絡(luò)處理器上的軟件代碼的移植和重用。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1851XScale：通用RISC處理器，用于初始化、管理芯片和高IXP2400網(wǎng)絡(luò)處理器簡(jiǎn)介IXA是用于Internet數(shù)據(jù)交換設(shè)備的處理器系統(tǒng)結(jié)構(gòu)，它使得Internet設(shè)備由傳統(tǒng)的固定協(xié)議、低效率走向具有軟件升級(jí)功能的高效率可編程設(shè)備。IXP2400是IXA系統(tǒng)結(jié)構(gòu)的一個(gè)具體處理器產(chǎn)品。其外部特性如下圖

所示。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1852IXP2400網(wǎng)絡(luò)處理器簡(jiǎn)介8.4IXP2400平臺(tái)上8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì).IntelIXP2400網(wǎng)絡(luò)處理器外部特性2023/8/18538.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì).In1個(gè)IntelXScaleCore8個(gè)微引擎多級(jí)存儲(chǔ)結(jié)構(gòu)Scratchpad存儲(chǔ)器2個(gè)QDRSRAM控制器1個(gè)DDRDRAM控制器媒體交換結(jié)構(gòu)（MSF）SHaC單元PCI控制器IXP2400典型系統(tǒng)結(jié)構(gòu)8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)IXP2400的典型模塊系統(tǒng)結(jié)構(gòu)2023/8/18541個(gè)IntelXScaleCoreIXP2400典型系統(tǒng)IntelXScaleCore處理器基于ARMV5TE的通用32位RISC處理器，主頻600MHz。負(fù)責(zé)芯片的初始化、管理，而且能夠完成高層網(wǎng)絡(luò)處理任務(wù)。不支持浮點(diǎn)指令集在IntelXScaleCore處理器上編程與在通用處理器上編程沒(méi)有太大不同返回8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1855IntelXScaleCore處理器返回8.4IXP8個(gè)微引擎每個(gè)IXP2400處理器帶有8個(gè)主頻為600MHz的微引擎（MicroEngine，以下簡(jiǎn)稱ME），分為兩個(gè)簇。每簇4個(gè)ME，且有獨(dú)立的命令總線和SRAM總線，兩個(gè)簇共享一條DRAM總線。ME擁有專門為處理網(wǎng)絡(luò)數(shù)據(jù)開(kāi)發(fā)的指令集，包括50多條針對(duì)比特、字節(jié)或長(zhǎng)字的不同的算術(shù)運(yùn)算和邏輯運(yùn)算指令。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/18568個(gè)微引擎8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）8個(gè)微引擎每個(gè)ME有4k的指令空間，還擁有本地存儲(chǔ)器、通用寄存器、傳輸寄存器、相鄰寄存器和乘法等部件。每個(gè)ME可運(yùn)行8個(gè)硬件支持的線程，線程之間的切換是無(wú)耗時(shí)的，因?yàn)槊總€(gè)線程擁有自己獨(dú)立的寄存器組、程序計(jì)數(shù)器等。返回8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/18578個(gè)微引擎返回8.4IXP2400平臺(tái)上多核程序并發(fā)（并多級(jí)存儲(chǔ)體系結(jié)構(gòu)除了每個(gè)微引擎單獨(dú)擁有的本地存儲(chǔ)器外，IXP2400還擁有：

1個(gè)16K字節(jié)的板載便箋存儲(chǔ)器（Scratchpad）

1個(gè)DDRSDRAM控制器（最高支持1GB）

2個(gè)獨(dú)立的QDRSRAM控制器（每個(gè)控制器最高支持64MB）。除本地存儲(chǔ)器外，其他存儲(chǔ)器由所有微引擎以及IntelXScalecore共享。表9-1是各種存儲(chǔ)器的特性。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1858多級(jí)存儲(chǔ)體系結(jié)構(gòu)8.4IXP2400平臺(tái)上多核程序并發(fā)（ixp2400各級(jí)存儲(chǔ)器對(duì)照表返回8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1859ixp2400各級(jí)存儲(chǔ)器對(duì)照表返回8.4IXP2400平媒體交換結(jié)構(gòu)接口（MSF）媒體交換結(jié)構(gòu)接口是數(shù)據(jù)進(jìn)出IXP2400處理器的接口，包括接收和發(fā)送緩存。接收和發(fā)送的過(guò)程是一個(gè)復(fù)雜的對(duì)微包(mpacket)進(jìn)行分割和重組的操作。微包是由完整數(shù)據(jù)包切割成具有固定大小的數(shù)據(jù)塊。通過(guò)把數(shù)據(jù)分組被分割成了小的微包，MSF呈現(xiàn)給程序員的接口就是一個(gè)獨(dú)立于物理MSF設(shè)備或分組格式得收發(fā)任務(wù)。返回8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1860媒體交換結(jié)構(gòu)接口（MSF）返回8.4IXP2400平臺(tái)上SHaC單元包括3個(gè)主要的子塊：便箋存儲(chǔ)器（ScratchpadMemory）散列單元（HashUnit）CAP（CSRAccessProxy）便箋存儲(chǔ)器就是前面介紹的多級(jí)存儲(chǔ)的一員散列單元是一個(gè)多項(xiàng)式散列加速器，IntelXScale核心處理器和微引擎用它來(lái)負(fù)責(zé)散列的計(jì)算，它能夠根據(jù)同樣大小的關(guān)鍵字產(chǎn)生48位、64位以及128位的散列值。CAP單元包含一些全片的控制狀態(tài)寄存器；它們提供特殊的內(nèi)部處理器通信特征，以允許微引擎之間以及微引擎與核心之間靈活、高效的通信。返回8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1861SHaC單元返回8.4IXP2400平臺(tái)上多核程序并發(fā)（PCI控制器IXP2400的PCI單元支持64位遵循PCIRev2.2的輸入輸出接口。PCI用來(lái)連接宿主處理器和PCI外圍設(shè)備。它在66MHz頻率時(shí)支持64位接口；支持主從設(shè)備。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1862PCI控制器8.4IXP2400平臺(tái)上多核程序并發(fā)（并行網(wǎng)絡(luò)處理器的技術(shù)特點(diǎn)以上描述的IXP2400特殊的硬件體系結(jié)構(gòu)使它將通用處理器靈活以及ASIC高速的優(yōu)點(diǎn)集于一身，擁有一系列技術(shù)特點(diǎn)，成為下一代網(wǎng)絡(luò)的核心技術(shù)。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1863網(wǎng)絡(luò)處理器的技術(shù)特點(diǎn)以上描述的IXP2400特殊的硬件體系結(jié)可編程性：這是通過(guò)提供界面友好而功能強(qiáng)大的編程、調(diào)試和性能評(píng)價(jià)等軟件環(huán)境來(lái)實(shí)現(xiàn)的，從而改變ASIC靈活性差的缺點(diǎn)。并行處理：網(wǎng)絡(luò)處理器可實(shí)現(xiàn)不同級(jí)別的并行處理。通過(guò)流水線實(shí)現(xiàn)指令級(jí)的并行，通過(guò)硬件線程實(shí)現(xiàn)線程級(jí)的并行，通過(guò)片內(nèi)多處理器結(jié)構(gòu)實(shí)現(xiàn)處理器級(jí)的并行。高速數(shù)據(jù)處理：網(wǎng)絡(luò)處理器需要具有線速處理的能力，以避免節(jié)點(diǎn)設(shè)備成為瓶頸。其硬件結(jié)構(gòu)為此提供了保證。深層包處理能力：根據(jù)不同的服務(wù)要求，對(duì)2～7層的數(shù)據(jù)分組采用“存儲(chǔ)--處理--轉(zhuǎn)發(fā)”數(shù)據(jù)分組處理模式以實(shí)現(xiàn)復(fù)雜的QOS、安全控制、負(fù)載均衡等功能模塊。NP的出現(xiàn)，標(biāo)志著設(shè)備對(duì)數(shù)據(jù)分組的處理能力從低層處理過(guò)渡到高層細(xì)化處理。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1864可編程性：這是通過(guò)提供界面友好而功能強(qiáng)大的編程、調(diào)試和性能評(píng)模塊化設(shè)計(jì)：網(wǎng)絡(luò)處理器體系結(jié)構(gòu)的模塊化也包含不同的層次:硬件層面和軟件層面的模塊化。通過(guò)模塊化設(shè)計(jì)，力圖在保持高性能的基礎(chǔ)上獲得很好的可擴(kuò)展性和靈活性，并能使設(shè)備廠商容易研發(fā)不同性能和不同特性的設(shè)備。

可擴(kuò)展性：網(wǎng)絡(luò)處理器的可擴(kuò)展性同樣包含硬件可擴(kuò)展性和服務(wù)可擴(kuò)展性。前者指網(wǎng)絡(luò)處理器除了可以用來(lái)研制小型設(shè)備，還可以通過(guò)交換機(jī)構(gòu)的連接研制大型設(shè)備。后者是指可以在對(duì)原有軟件結(jié)構(gòu)做很小改動(dòng)的基礎(chǔ)上加入新的服務(wù)和功能。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1865模塊化設(shè)計(jì)：網(wǎng)絡(luò)處理器體系結(jié)構(gòu)的模塊化也包含不同的層次:硬8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)控制層面管理層面數(shù)據(jù)層面網(wǎng)絡(luò)設(shè)備軟件的三個(gè)層面8.4.4基于IntelIXP網(wǎng)絡(luò)處理器的軟件設(shè)計(jì)2023/8/18668.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)控制層網(wǎng)絡(luò)設(shè)備軟件的三個(gè)層面數(shù)據(jù)層面包括慢速數(shù)據(jù)通道和快速數(shù)據(jù)通道。快速數(shù)據(jù)通道是由微引擎負(fù)責(zé)處理的數(shù)據(jù)轉(zhuǎn)發(fā)通道，大部分?jǐn)?shù)據(jù)包通過(guò)此通道完成處理與轉(zhuǎn)發(fā)。慢速數(shù)據(jù)通道：由通用RISC核負(fù)責(zé)處理一些例外復(fù)雜的數(shù)據(jù)包，如數(shù)據(jù)包分段、帶擴(kuò)展頭部的數(shù)據(jù)包處理等?？刂茖用嫣幚砀鞣N通信協(xié)議。轉(zhuǎn)發(fā)表和狀態(tài)信息維護(hù)。管理層面安裝配置接口。策略管理接口。系統(tǒng)管理、統(tǒng)計(jì)、計(jì)費(fèi)。8.4IXP2400平臺(tái)上多核程序并發(fā)（并行）設(shè)計(jì)2023/8/1867網(wǎng)絡(luò)設(shè)備軟件的三個(gè)層面8.4IXP2400平臺(tái)上多核程序MicroenginePipelineControlPlaneProtocolStackControlPlanePDKCoreComponen