【正文】 ? 在多核體系中，必須將中斷請求分發(fā)給一組核處理。當(dāng)系統(tǒng)中有多個核在并行執(zhí)行時，必須有一個能夠?qū)⒔邮盏降闹袛嗾埱蠓职l(fā)給能夠提供服務(wù)（處理該請求）的核的機制。 虛擬化技術(shù) ? 虛擬化技術(shù)：是指對計算機資源進行的抽象，是在系統(tǒng)、應(yīng)用或用戶與資源進行交互時，對計算機資源的物理特性進行隱藏的一種技術(shù)。 ? 分類： （ 1）平臺虛擬化：由指定硬件平臺上的宿主軟件來實行，為其他軟件提供一個模擬的計算機環(huán)境。其他軟件通常都是完整的操作系統(tǒng)，就像安裝在獨立的硬件平臺上一樣運行。 （ 2）資源虛擬化：它是被擴展到具體系統(tǒng)資源的虛擬化，它涉及資源的合并、劃分以及簡化的模擬等作用。 并行計算基礎(chǔ) 并行計算機體系結(jié)構(gòu) ? 組成并行計算機的各個部分： – 節(jié)點（ node） – 互聯(lián)網(wǎng)絡(luò)（ interconnect work） – 內(nèi)存 （ memory） 內(nèi)存模塊與節(jié)點分離 內(nèi)存模塊位于節(jié)點內(nèi)部 ? cache的映射策略指的是內(nèi)存塊和 cache線之間如何建立相互映射關(guān)系。 ? 直接映射策略（ direct mapping strategy） – 每個內(nèi)存塊只能被唯一的映射到一條 cache線中 ? K－路組關(guān)聯(lián)映射策略 （ Kway set association mapping strategy） – Cache被分解為 V個組，每個組由 K條 cache線組成，內(nèi)存塊按直接映射策略映射到某個組，但在該組中，內(nèi)存塊可以被映射到任意一條 cache線。 ? 全關(guān)聯(lián)映射策略 （ full association mapping strategy） – 內(nèi)存塊可以被映射到 cache中的任意一條 cache線。 并行計算機訪存模型 ? UMA（ Uniform Memory Access）模型 – 物理存儲器被所有節(jié)點共享； – 所有節(jié)點訪問任意存儲單元的時間相同； – 發(fā)生訪存競爭時，仲裁策略平等對待每個節(jié)點，即每個節(jié)點機會均等； – 各節(jié)點的 CPU可帶有局部私有高速緩存； – 外圍 I/O設(shè)備也可以共享，且每個節(jié)點有平等的訪問權(quán)利。 ? NUMA（ NonUniform Memory Access）模型 – 物理存儲器被所有節(jié)點共享，任意節(jié)點可以直接訪問任意內(nèi)存模塊； – 節(jié)點訪問內(nèi)存模塊的速度不同，訪問本地存儲模塊的速度一般是訪問其他節(jié)點內(nèi)存模塊的 3倍以上； – 發(fā)生訪存競爭時，仲裁策略對節(jié)點可能是不等價的； – 各節(jié)點的 CPU可帶有局部私有高速緩存 （ cache）； – 外圍 I/O設(shè)備也可以共享，但對各節(jié)點是不等價的。 并行計算機訪存模型 (續(xù) ) ? COMA（ CacheOnly Memory Access）模型 – 各處理器節(jié)點中沒有存儲層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間； – 利用分布的高速緩存目錄 D進行遠程高速緩存的訪問； – COMA中的高速緩存容量一般都大于 2級高速緩存容量； – 使用 COMA時，數(shù)據(jù)開始時可以任意分配，因為在運行時它最終會被遷移到要用到它的地方。 ? NORMA（ NoRemote Memory Access）模型 – 所有存儲器都是私有的； – 絕大多數(shù) NORMA都不支持遠程存儲器的訪問； – 在 DSM中， NORMA就消失了。 并行計算機訪存模型 (續(xù) ) ? 并行計算機系統(tǒng)的不同訪存模型分類 并行計算模型 ? SIMD同步并行計算模型 – 共享存儲的 SIMD模型（ PRAM模型） – 分布存儲的 SIMD模型（ SIMD互聯(lián)網(wǎng)絡(luò)模型） ? MIMD異步并行計算模型 – 異步 PRAM模型 – BSP模型 – LogP模型 – C3模型 SIMD同步并行計算模型 ? SIMD共享存儲模型（ PRAM模型） – PRAMEREW （ ExclusiveRead and ExclusiveWrite），不允許同時讀和同時寫； – PRAMCREW （ ConcurrentRead and ExclusiveWrite） ，允許同時讀但不允許同時寫； – PRAMCRCW （ ConcurrentRead and ConcurrentWrite） ，允許同時讀和同時寫； ? 優(yōu)點： – 適合于并行算法的表達、分析和比較； – 使用簡單，很多諸如處理器間通信、存儲管理和進程同步等并行計算機的低級細節(jié)均隱含于模型中； – 易于設(shè)計算法和稍加修改便可運行在不同的并行計算機上； – 且有可能加入一些諸如同步和通信等需要考慮的方面。 SIMD分布存儲模型 ? 采用一維線性連接的 SIMD模型，簡記為 SIMDLC ? 采用網(wǎng)孔連接的 SIMD模型，簡記為 SIMDMC ? 采用樹形連接的 SIMD模型，簡記為 SIMDTC ? 采用樹網(wǎng)連接的 SIMD模型，簡記為 SIMDMT ? 采用立方連接的 SIMD模型，簡記為 SIMDCC ? 采用立方環(huán)連接的 SIMD模型，簡記為 SIMDCCC ? 采用洗牌交換連接的 SIMD模型，簡記為 SIMDSE ? 采用蝶形連接的 SIMD模型，簡介為 SIMDBF ? 采用多級互聯(lián)網(wǎng)絡(luò)連接的 SIMD模型，簡記為 SIMDMIN MIMD異步計算模型 —APRAM模型 ? APRAM特點 : – 每個處理器都有其本地存儲器、局部時鐘和局部程序； – 處理器間的通信經(jīng)過共享全局存儲器； – 無全局時鐘，各處理器異步地獨立執(zhí)行各自的指令； – 處理器任何時間依賴關(guān)系需明確地在各處理器的程序中加入同步（路）障（ Synchronization Barrier）； – 一條指令可在非確定但有限的時間內(nèi)完成。 ? APRAM模型中有四類指令 : – 全局讀，將全局存儲單元中的內(nèi)容讀入本地存儲器單元中； – 局部操作，對本地存儲器中的數(shù)執(zhí)行操作，其結(jié)果存入本地存儲器中； – 全局寫，將本地存儲器單元中的內(nèi)容寫入全本地存儲器單元中； – 同步，同步是計算中的一個邏輯點，在該點各處理器均需等待別的處理器到達后才能繼續(xù)執(zhí)行其局部程序。 MIMD異步計算模型 —BSP模型 ? 作為計算機語言和體系結(jié)構(gòu)之間的橋梁，由以下述三個參數(shù)描述分布存儲的并行計算機模型： – 處理器 /存儲器模塊（下文簡稱處理器）； – 處理器模塊之間點到點信息傳遞的路由器； – 執(zhí)行以時間間隔 L為周期的路障同步器。 ? 特點： – 將處理器和路由器分開，強調(diào)了計算任務(wù)和通信任務(wù)的分開，而路由器僅施行點到點的消息傳遞，不提供組合、復(fù)制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網(wǎng)絡(luò)拓撲，又簡化了通信協(xié)議； – 采用路障方式的以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負擔(dān)； – 在分析 BSP模型的性能時，假定局部操作可在一個時間步內(nèi)完成，而在每一超級步中，一個處理器至多發(fā)送或接受 h條消息（ hrelation）。 MIMD異步計算模型 —LogP,C3模型 ? LogP模型是一種分布存儲的、點到點通信的多處理機模型，其中通信網(wǎng)絡(luò)由一組參數(shù)來描述，但它并不涉及到具體的網(wǎng)絡(luò)結(jié)構(gòu)，也不假定算法一定要用顯式的消息傳遞操作進行描述。 ? C3（ Computation, Communication, Congestion）模型是一個與體系結(jié)構(gòu)無關(guān)的粗粒度的并行計算模型，旨在能反映計算復(fù)雜度，通信模式和通信期間潛在的擁擠等因素對粗粒度網(wǎng)絡(luò)算法的影響。 并行編程環(huán)境 ? 比較流行的并行編程環(huán)境主要有 3類：消息傳遞、共享存儲和數(shù)據(jù)并行 特征 消息傳遞 共享存儲 數(shù)據(jù)并行 典型代表 MPI, PVM OpenMP HPF 可移植性 所有主流并行計算機 SMP, DSM SMP, DSM, MPP 并行粒度 進程級大粒度 線程級細粒度 進程級細粒度 并行操作方式 異步 異步 松散同步 數(shù)據(jù)存儲模式 分布式存儲 共享存儲 共享存儲 數(shù)據(jù)分配方式 顯式 隱式 半隱式 學(xué)習(xí)入門難度 較難 容易 偏易 可擴展性 好 較差 一般 并行編程標(biāo)準(zhǔn) ? 數(shù)據(jù)并行語言標(biāo)準(zhǔn) – Fortran90, HPF(1992), Fortran95/2022:顯式數(shù)據(jù)分布描述,并行 DO循環(huán) . ? 線程庫標(biāo)準(zhǔn) (Thread Library) – Win32 API. – POSIX threads線程模型 . ? 編譯制導(dǎo) (Compiler Directives) – OpenMP : portable shared memory parallelism ? 消息傳遞庫標(biāo)準(zhǔn) (Message Passing Libraries) – MPI : Message Passing Interface – PVM : Parallel Virtual Machine 數(shù)據(jù)并行編程 共享變量編程 消息傳遞編程 并行編程標(biāo)準(zhǔn)歸類 ? 所有并行編程標(biāo)準(zhǔn)可分為以下三類 : – 數(shù)據(jù)并行 ? HPF, Fortran90 ? 用于 SMP, DSM – 共享編程 ? OpenMP ? 用于 SMP, DSM – 消息傳遞 ? MPI, PVM ? 用于所有并行計算機 ? 三者可混合使用 : – 如對以 SMP為節(jié)點的 Cluster來說 , 可以在節(jié)點間進行消息傳遞 ,在節(jié)點內(nèi)進行共享變量編程 . 并行編程模型 ? 共享存儲模型 – 在共享存儲編程模型里，任務(wù)共享一個共用的地址空間，它們在這個共享空間進行異步的讀寫。 – 像“鎖 /信號量”這樣不同的機制將會用來控制對共享存儲的訪問。 – 從程序員的觀點，這種模式的好處是沒有數(shù)據(jù)所有權(quán)的概念，因此沒必要在任務(wù)之間明確地規(guī)定數(shù)據(jù)通信。程序開發(fā)通常會比較簡單。 – 一個重要的性能上的缺點是理解和管理局部的數(shù)據(jù)變得更加困難。 – 實現(xiàn)：在共享存儲平臺，本地編譯程序?qū)⒂脩舫绦蜃兞糠g成全局存儲空間中實際的存儲地址。 并行編程模型 ? 消息傳遞模型 – 一組任務(wù)在計算的時候使用它們自己的局部存儲器。多個任務(wù)可以駐留在同一臺機器，或者跨任意數(shù)量的機器。 – 任務(wù)之間通過發(fā)送和接受消息的數(shù)據(jù)通信來交換數(shù)據(jù)。 – 數(shù)據(jù)傳送通常需要每個進程協(xié)同操作來完成。比如一個發(fā)送操作必須有一個對應(yīng)的接收操作。 并行編程模型 – 實現(xiàn) : ? 1992年 , MPI（消息傳遞接口）論壇成行，其主要目標(biāo)是制定消息傳遞實現(xiàn)的標(biāo)準(zhǔn)接口 ? MPI現(xiàn)在是實際上的消息傳遞的工業(yè)標(biāo)準(zhǔn)，實際上替代了所有其它的用于生產(chǎn)工作的消息傳遞實現(xiàn)。大多數(shù)并行平臺會提供至少一個 MPI的實現(xiàn)。少數(shù)還提供完整的MPI2的實現(xiàn)。 ? 對于共享存儲結(jié)構(gòu)， MPI通常實現(xiàn)的時候不用網(wǎng)絡(luò)進行任務(wù)通信。它通常處于性能的考慮，用共享存儲（存儲器拷貝）來實現(xiàn)。 并行編程模型 ? 數(shù)據(jù)并行模型 – 大多數(shù)并行工作都是在一個數(shù)據(jù)集中去完成。數(shù)據(jù)集通常組織成一個共同的結(jié)構(gòu)，比如數(shù)組或者多維數(shù)組。 – 一組任務(wù)共同地工作在相同的數(shù)據(jù)結(jié)構(gòu)，然而每個任務(wù)工作在這個數(shù)據(jù)結(jié)構(gòu)的不同部分。 – 任務(wù)用相同的操作執(zhí)行它那部分工作，比如“給每個數(shù)組元素加 4?！? 并行編程模型 – 在共享存儲結(jié)構(gòu)中，所有的任務(wù)可以通過全局存儲器來訪問數(shù)據(jù)結(jié)構(gòu)。 – 在分布式存儲結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)是分散的，并以“組塊”的方式存在于每個任務(wù)的局部存儲器中。 并行編程模型 – 實現(xiàn) ? 高性能 Fortran (HPF): 將 Fortran 90擴展，支持?jǐn)?shù)據(jù)并行的程序設(shè)計 –包含 Fortran 90中的一切 –增加了指導(dǎo)編譯器如何分布數(shù)據(jù)的功能 –增加了能夠改進生成代碼優(yōu)化的功能 –增加了數(shù)據(jù)并行的結(jié)構(gòu) (現(xiàn)在是 Fortran 95的一部分 ) ? 編譯器指導(dǎo)語句 : 允許程序員指定數(shù)據(jù)的分布和對齊。Fortran 實現(xiàn)是最常見的并行平臺。 ? 這種模式的分布式存儲實現(xiàn)通常由編譯器轉(zhuǎn)換程序到標(biāo)準(zhǔn)代碼來調(diào)用消息傳遞庫（通常是 MPI）去分布數(shù)據(jù)到所有處理器。所有的消息傳遞對程序員是透明的。 并行編譯器 ? 并行編譯過程 并行計算性能評測 ? 并行程序執(zhí)行時間 – 等于從并行程序開始執(zhí)行到所有進程執(zhí)行完畢，墻上時鐘走過的時間，也稱為墻上時間 （ wall clock time）。對各個進程，墻上時間可進一步分解為計算 CPU時間、通信CPU時間、同步開銷時間、同步導(dǎo)致的進程空閑時間。 ? 并行程序性能評價方法 – 浮點峰值性能與實際浮點性能 – 數(shù)值效率和并行效率 ? 加速比性能定律 – Amdahl定律 – Gustafson定律 – Sun和 Ni定律 135 程序性能優(yōu)化方法 ? 串行程序性能優(yōu)化 – 調(diào)用高性能庫，比如優(yōu)化的 BLAS， FFTW等； – 選擇適當(dāng)?shù)木幾g器優(yōu)化選項； – 合理