并行計(jì)算機(jī)體系結(jié)構(gòu)復(fù)習(xí)

2023/2/61并行計(jì)算機(jī)體系結(jié)構(gòu)復(fù)習(xí)計(jì)算機(jī)系2023/2/62第一章概論§1.1引言1、計(jì)算機(jī)性能與結(jié)構(gòu)關(guān)系2、需求3、可行性2023/2/63§1.2并行處理的定義

定義：并行處理是一種有效的強(qiáng)調(diào) 開發(fā)計(jì)算過程中并行事件 的信息處理方式。并行事件：

同時(shí)性并發(fā)性流水線2023/2/64§1.2并行處理的定義信息處理廣義上包含數(shù)據(jù)處理、信息處理、知識處理和智能處理。

數(shù)據(jù)處理 信息處理 知識處理 智能處理認(rèn)真理解并行事件與信息處理含義2023/2/65§1.3開發(fā)并行性的途徑1、并行事件的獲取并行事件可以從不同的處理級獲?。鹤鳂I(yè)或程序級： 任務(wù)或進(jìn)程級：線程級：指令級：指令內(nèi)部操作級：2023/2/662、并行計(jì)算機(jī)結(jié)構(gòu)形式流水計(jì)算機(jī)陣列計(jì)算機(jī)多處理機(jī)和多計(jì)算機(jī)2023/2/67并行處理系統(tǒng)的發(fā)展過程多道程序、分時(shí)系統(tǒng)、虛擬存儲(chǔ)器多終端遠(yuǎn)程系統(tǒng)分布式系統(tǒng)多存儲(chǔ)器、多操作部件陣列處理機(jī)關(guān)聯(lián)處理機(jī)同構(gòu)型多處理機(jī)系統(tǒng)先行控制、高速緩存指令、操作宏流水線異構(gòu)型多處理機(jī)具有以自治性為特征的分布控制單處理機(jī)通過資源共享通過資源重復(fù)通過時(shí)間重疊

通過對多處理機(jī)系統(tǒng)的網(wǎng)絡(luò)化、多機(jī)互連、功能專用化得到前三種并行處理機(jī)系統(tǒng)2023/2/68§1.4并行處理機(jī)的分類

Flynn分類法Handler分類法按體系結(jié)構(gòu)分類現(xiàn)代并行機(jī)結(jié)構(gòu)分類2023/2/69Flynn分類法：MichaelJ.Flynn1966

按指令流、數(shù)據(jù)流分類指令流－機(jī)器執(zhí)行指令的序列數(shù)據(jù)流－由指令調(diào)用的數(shù)據(jù)的序列單指令流單數(shù)據(jù)流SISD單指令流多數(shù)據(jù)流SIMD多指令流單數(shù)據(jù)流MISD多指令流多數(shù)據(jù)流MIMD§1.4并行處理機(jī)的分類2023/2/610T(c)=<K×K’,D×D’,W×W’>CPU數(shù)目能執(zhí)行流水線的CPU數(shù)目CPU所控制的ALU數(shù)目能執(zhí)行流水線的ALU數(shù)目ALU或PE中的位數(shù)ALU或PE中流水線的段數(shù)三元組分類法：WolfgangH?ndler1977年，Handler根據(jù)計(jì)算機(jī)系統(tǒng)中流水線和并行程度分類。從三個(gè)子系統(tǒng)級分析：處理機(jī)級PCU、算術(shù)邏輯部件級ALU、位級BIC§1.4并行處理機(jī)的分類2023/2/611向量流水機(jī)：陣列處理機(jī)：(含脈動(dòng)陣列）SIMD關(guān)聯(lián)處理機(jī)：具有聯(lián)想存儲(chǔ)，按內(nèi)容存取、邏輯操作等同步系統(tǒng)（統(tǒng)一時(shí)鐘）按體系結(jié)構(gòu)分類§1.4并行處理機(jī)的分類2023/2/612§1.4并行處理機(jī)的分類由獨(dú)立執(zhí)行指令的處理器構(gòu)成分布存儲(chǔ)系統(tǒng)：多個(gè)存儲(chǔ)器物理上分布集中存儲(chǔ)系統(tǒng)：存儲(chǔ)器物理上相對集中多處理機(jī)系統(tǒng)MIMD2023/2/613SIMD PVP并行向量處理機(jī) （ParallelVectorProcessor）SMP對稱多處理機(jī)

（SymmetricMultiprocessor）MPP大規(guī)模并行處理機(jī)（MassivelyParallelProcessor）DSM分布式共享存儲(chǔ)多處理機(jī)

（DistributedSharedMemory）COW工作站機(jī)群

（ClusterOfWorkstations）現(xiàn)代并行機(jī)結(jié)構(gòu)分類§1.4并行處理機(jī)的分類互2023/2/614并行處理系統(tǒng)性能上限分析（1）并行處理系統(tǒng)性能上限分析（2）2023/2/615H.T.Kung(1991)認(rèn)為并行處理中的三個(gè)關(guān)鍵問題：并行計(jì)算的計(jì)算模型－并行性 問題分解、任務(wù)的分配處理機(jī)之間的通信－可擴(kuò)展性 互連網(wǎng)的復(fù)雜性通用并行計(jì)算環(huán)境－可編程性 并行語言、并行編譯、并行應(yīng)用等2023/2/616第二章并行計(jì)算機(jī)模型以MIMD模式運(yùn)行的計(jì)算機(jī)系統(tǒng)包含多個(gè)處理機(jī)或計(jì)算機(jī)的單一計(jì)算機(jī)系統(tǒng)通過互連網(wǎng)將各處理機(jī)、計(jì)算機(jī)或存儲(chǔ)單元相連接§2.1概述2023/2/617基本特性：單處理機(jī)的能力和處理機(jī)陣列大小的乘積決定并行計(jì)算機(jī)系統(tǒng)的能力互連網(wǎng)絡(luò)決定解決問題的類型和系統(tǒng)的適應(yīng)能力控制方式分為集中式和分布式2023/2/618按通信方式按耦合度按控制方式

三者之間的關(guān)系2023/2/619從四個(gè)方面討論并行計(jì)算機(jī)模型并行計(jì)算機(jī)結(jié)構(gòu)模型并行計(jì)算機(jī)訪存模型并行計(jì)算機(jī)性能模型并行計(jì)算機(jī)Cache一致性2023/2/620SIMD PVP并行向量處理機(jī) （ParallelVectorProcessor）SMP對稱多處理機(jī)

（SymmetricMultiprocessor）MPP大規(guī)模并行處理機(jī)（MassivelyParallelProcessor）DSM分布式共享存儲(chǔ)多處理機(jī)

（DistributedSharedMemory）COW工作站機(jī)群

（ClusterOfWorkstations）§2.2并行處理機(jī)結(jié)構(gòu)模型互2023/2/621§2.3并行計(jì)算機(jī)訪存模型分類：均勻存儲(chǔ)訪問模型UMA非均勻存儲(chǔ)訪問模型NUMA全高速緩存存儲(chǔ)訪問模型COMA高速緩存一致性非均勻存儲(chǔ)訪問模型CC-NUMA非遠(yuǎn)程存儲(chǔ)訪問模型NORMA從系統(tǒng)訪問存儲(chǔ)器模式的角度來討論多處理機(jī)，與上面所討論的模型是并行計(jì)算機(jī)系統(tǒng)的兩個(gè)方面。

2023/2/622§2.4并行計(jì)算機(jī)性能模型粒度概述：粒度是衡量軟件進(jìn)程所含計(jì)算量的尺度設(shè)R代表程序的執(zhí)行時(shí)間，C代表用于通信的開銷，用R/C比值表示每一單位計(jì)算的開銷，即衡量任務(wù)粒度（TaskGranularity）大小的尺度。2023/2/623在粗粒度（Coarsegrain）并行情況下，R/C比值比較大，每個(gè)單位計(jì)算只需要少量的通信。在細(xì)粒度（Finegrain）并行情況下，R/C比值比較小，每個(gè)單位計(jì)算有很大的通信量和其它的開銷。細(xì)粒度并行性需要許多臺處理機(jī)，而粗粒度并行性只需較少臺數(shù)的處理機(jī)。

2023/2/624細(xì)粒度并行性：把一個(gè)程序盡可能地分解成能并行執(zhí)行的小任務(wù)。在極端情況下，一個(gè)小任務(wù)只完成一個(gè)操作。通常，一個(gè)小任務(wù)包含幾條指令。2023/2/625兩臺處理機(jī)系統(tǒng)任務(wù)分配擴(kuò)展到N臺處理機(jī)系統(tǒng)的任務(wù)分配通信開銷為線性的模型：額外開銷與計(jì)算過程重疊的模型：具有多條通信鏈路的模型：2023/2/626性能模型總結(jié)：多處理機(jī)系統(tǒng)結(jié)構(gòu)所需的額外開銷，包括調(diào)度，對共享資源的競爭，同步，處理機(jī)之間通信等，在串行機(jī)和向量機(jī)（或別的單指令流機(jī)）系統(tǒng)結(jié)構(gòu)中是不存在的。

2023/2/627當(dāng)運(yùn)行某個(gè)程序的處理機(jī)數(shù)目增加時(shí)，用于計(jì)算的那部分時(shí)間將減少，而額外開銷時(shí)間卻增加了。實(shí)際上，額外開銷的增加可能比處理機(jī)數(shù)目的線性增加更快。2023/2/628矛盾：

R/C要足夠小使能并行執(zhí)行的任務(wù)數(shù)目較多；

R/C要足夠大以免額外開銷太大。

即不能期待通過增加處理機(jī)數(shù)目來提高多機(jī)系統(tǒng)性能

2023/2/629軟硬件并行性匹配（粒度匹配）軟件并行性：與求解的問題有關(guān)，由程序的控制和數(shù)據(jù)的相關(guān)性決定，是算法、程序設(shè)計(jì)風(fēng)格和編譯優(yōu)化的函數(shù)。將求解問題分解為多個(gè)相關(guān)子任務(wù)，并可由一個(gè)有序圖來表示各子任務(wù)之間的關(guān)系。2023/2/630硬件并行性：

是價(jià)格和性能折衷的函數(shù)，顯示可以同時(shí)執(zhí)行操作的資源利用方式，說明處理機(jī)資源峰值的性能。軟件并行性反映用戶的需求；硬件并行性反映了系統(tǒng)的適應(yīng)性2023/2/631多機(jī)系統(tǒng)設(shè)計(jì)目標(biāo)：

使系統(tǒng)結(jié)構(gòu)和所求解問題（粒度）達(dá)到最佳匹配2023/2/632匹配過程：針對求解問題，將程序劃分為盡可能多的并行成分，以獲得最短計(jì)算時(shí)間；分析獲得可能的單處理機(jī)性能，最大處理機(jī)數(shù)目和互連網(wǎng)絡(luò)性能；根據(jù)要求，求得最佳粒度（加速比、性能價(jià)格比等）；結(jié)構(gòu)靈活性（適應(yīng)性）2023/2/633§2.5并行計(jì)算機(jī)Cache一致性引發(fā)Cache一致性的緣由Cache一致性維護(hù)策略基于總線監(jiān)聽協(xié)議基于目錄協(xié)議2023/2/634引發(fā)Cache一致性問題的緣由單機(jī)系統(tǒng)：寫操作引發(fā)的Cache和主存數(shù)據(jù)的不一致I/O讀引發(fā)的主存和Cache數(shù)據(jù)的不一致2023/2/635多處理機(jī)系統(tǒng)：共享數(shù)據(jù)寫操作引發(fā)的Cache與主存以及各Cache之間的數(shù)據(jù)不一致；進(jìn)程遷移引發(fā)的各Cache之間的數(shù)據(jù)不一致I/O操作造成的主存與各Cache中的數(shù)據(jù)不一致2023/2/636一致性的維護(hù)策略單機(jī)中的基本策略：寫通過WT（Write-Through)

如果在Cache1中修改一個(gè)數(shù)據(jù)，則需要立即在主存中修改該數(shù)據(jù)寫回WB(Write-Back)在Cache1中的修改修改一個(gè)數(shù)據(jù)，當(dāng)該數(shù)據(jù)被替換時(shí)再寫回主存（在相當(dāng)長時(shí)間內(nèi)，主存和Cache1數(shù)據(jù)不一致）2023/2/637

多機(jī)系統(tǒng)中cache一致性維護(hù)策略的改進(jìn)：

基本思路：

及時(shí)更新主存和各Cache中的數(shù)據(jù)或作廢其數(shù)據(jù)。

更新法（Write-Update)

作廢法（Write-Invalidate)

2023/2/638根據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)，采用不同方法維護(hù)各Cache之間及Cache與主存的一致性。播寫法（監(jiān)聽總線協(xié)議，適合總線結(jié)構(gòu)）目錄表法2023/2/6393.監(jiān)聽總線協(xié)議

(1)采用WT策略的一致性維護(hù)(2)采用WB策略的一致性維護(hù)2023/2/6404.基于目錄的協(xié)議全映射目錄有限目錄鏈?zhǔn)侥夸?023/2/641第三章互連網(wǎng)絡(luò)§3.1網(wǎng)絡(luò)特性

在網(wǎng)絡(luò)中，計(jì)算機(jī)、處理機(jī)、存儲(chǔ)器和I/O等稱為結(jié)點(diǎn)。各結(jié)點(diǎn)通過互連網(wǎng)連接交換信息。一般網(wǎng)絡(luò)是由有向或無向圖來表示。結(jié)點(diǎn)數(shù)決定網(wǎng)絡(luò)規(guī)模。

2023/2/642靜態(tài)互連網(wǎng)——由結(jié)點(diǎn)和結(jié)點(diǎn)直接相連，連接方式固定不變動(dòng)態(tài)互連網(wǎng)——由開關(guān)實(shí)現(xiàn)，可以動(dòng)態(tài)改變結(jié)點(diǎn)之間連接幾個(gè)主要的參數(shù)2023/2/643§3.2尋徑函數(shù)

尋徑函數(shù)：五個(gè)基本尋經(jīng)函數(shù)2023/2/644各種互連函數(shù)與其逆函數(shù)之間有如下關(guān)系：2023/2/645部分互連函數(shù)之間的關(guān)系：2023/2/646§3.3靜態(tài)互連網(wǎng)絡(luò)

按不同的拓?fù)浣Y(jié)構(gòu)，連接結(jié)點(diǎn)的入出端。每種連接以一種尋徑函數(shù)表示。若存在m中連接，用m個(gè)尋徑函數(shù)表示。既一個(gè)結(jié)點(diǎn)可以與多個(gè)結(jié)點(diǎn)直接連接。一個(gè)靜態(tài)互連網(wǎng)絡(luò)SW，可表示為：

SW={f1,f2。。。。。Fm}當(dāng)和沒有直接連接的結(jié)點(diǎn)通信時(shí)，需要循環(huán)使用該互連網(wǎng)絡(luò)各種靜態(tài)互連網(wǎng)及其改進(jìn)的變形，它的結(jié)點(diǎn)度和網(wǎng)絡(luò)直徑2023/2/647§3.4動(dòng)態(tài)互連網(wǎng)絡(luò)三種形式：總線結(jié)構(gòu)——操作過程及控制過程，仲裁器、菊花鏈全互連開關(guān)——開關(guān)形式多級交叉開關(guān)網(wǎng)——各種多級開關(guān)2023/2/648當(dāng)多個(gè)結(jié)點(diǎn)同時(shí)申請使用總線，引發(fā)總線沖突，需要總線仲裁。兩種總線仲裁處理方法：

排隊(duì)器——優(yōu)先權(quán)編碼器 菊花鏈——靜態(tài)菊花鏈、動(dòng)態(tài)菊花鏈2023/2/649多級互連網(wǎng)絡(luò)：速度高，靈活性好，傳輸率低于完全開關(guān)網(wǎng)絡(luò)，適用于PE較多的情形。其性能特點(diǎn)反映在以下三個(gè)方面： 開關(guān)形式 級間拓?fù)浣Y(jié)構(gòu) 控制方式2023/2/650

4）

控制方式對各個(gè)交換開關(guān)進(jìn)行控制的方式有三種：(1)

級控制：同一級開關(guān)只用一個(gè)控制信號，處于同一狀態(tài)(2)單元控制：每一個(gè)開關(guān)都有自己單獨(dú)的控制信號(3)部分級控制：用i+1個(gè)控制信號控制第i級0≤i≤n-1，共(n+1)n/2個(gè)控制信號交換開關(guān)上的字母表示對該開關(guān)的控制信號，若不同開關(guān)寫同一字母，表示它們用同一種控制信號。2023/2/651ABDEFHIJLCGK0123456701234567012345670213465702134657041526370415263760123457ε(0)β(2)

ε(0)β(3)

ε(0)σn

–1

STARAN網(wǎng)

5.

幾種常見的多級互連網(wǎng)絡(luò)(1)

STARAN網(wǎng)絡(luò)：2023/2/6522)

Omega網(wǎng)絡(luò)——多級混洗交換網(wǎng)絡(luò)

由n級相同的網(wǎng)絡(luò)構(gòu)成，每一級包含一個(gè)完全混洗連接及隨后一列2n-1個(gè)4功能交叉開關(guān)單元，采用單元控制方式，一般形式：7012345670415263760124502461357ABCDEFGHIJKL實(shí)質(zhì)為STARAN網(wǎng)入出交換，并交換一下F、G位置，但不改變拓?fù)溥B接。0123456704152637601234502134657ABCDEGFHIJKL3σε（0）σε（0）σε（0）2023/2/6533)

Parker網(wǎng)絡(luò)——基準(zhǔn)網(wǎng)絡(luò)2023/2/654基準(zhǔn)網(wǎng)的遞歸構(gòu)成：任何一個(gè)N×N的互連網(wǎng)絡(luò)，可以由兩個(gè)N/2×N/2的子網(wǎng)絡(luò)組成。2023/2/655阻塞網(wǎng)絡(luò)——同時(shí)實(shí)現(xiàn)兩對或多對之間的連接時(shí)，可能因爭用數(shù)據(jù)通路而發(fā)生沖突無阻塞網(wǎng)——可以同時(shí)實(shí)現(xiàn)任意結(jié)點(diǎn)對之間的連接重按排網(wǎng)——經(jīng)過重新安排，可以同時(shí)實(shí)現(xiàn)任意對結(jié)點(diǎn)之間的連接2023/2/6564）Benes網(wǎng)2023/2/657010123235)Cantor網(wǎng)2023/2/658(6)

榕樹(Banyan)網(wǎng)絡(luò)

采用2×2帶仲裁的開關(guān)從左到右，結(jié)點(diǎn)編址的第i位控制第i級開關(guān)的輸出若采用a×b開關(guān)，結(jié)點(diǎn)采用b進(jìn)制編址每個(gè)根結(jié)點(diǎn)對應(yīng)下面各級都是一顆樹榕樹網(wǎng)可以實(shí)現(xiàn)以目標(biāo)結(jié)點(diǎn)地址尋址2023/2/6597）Delta網(wǎng)分組混洗：設(shè)有N=q×c張牌，分為q組，每組c張。取每組第1張排到輸出，然后每組取第2張排列到輸出，依次類推，直至把N張牌分完。4組混洗2023/2/660Delta網(wǎng)構(gòu)成：用a×b的開關(guān)可以構(gòu)成an×bn的網(wǎng)絡(luò)用a組混洗進(jìn)行級間連接從左到右分別為0級至n-1級 開關(guān)輸出和結(jié)點(diǎn)編址以b進(jìn)制表示

{dn-1,dn-2……..d1d0}b用di

位控制第i級開關(guān)模塊開關(guān)模塊數(shù) 當(dāng)a=b，（an-bn)/(a-b)

其它，nbn-12023/2/661§3.5消息傳遞機(jī)制計(jì)算機(jī)系統(tǒng)設(shè)計(jì)方案：2023/2/6622023/2/663消息格式尋徑方式-四種尋徑方式死鎖和虛擬通道包沖突策略維序?qū)そ?jīng)廣播與選播2023/2/664四種包沖突策略比較：阻塞法：控制簡單，但可能會(huì)引起大面積阻塞揚(yáng)棄法：控制簡單，重發(fā)效果未知，可能加大網(wǎng)絡(luò)負(fù)載虛擬直通法：不會(huì)浪費(fèi)已經(jīng)分配的資源，但需要一個(gè)能存放整個(gè)包的緩沖區(qū)，包緩沖區(qū)不可能做在尋徑芯片上，要用存儲(chǔ)器作為緩沖區(qū)，可能會(huì)有較大的存儲(chǔ)延遲。繞道法：繞道結(jié)果未知，需要按某種算法尋徑2023/2/665

第四章任務(wù)分配與調(diào)度§4.1多機(jī)操作系統(tǒng)概述1.主要特征：并行性——多機(jī)操作系統(tǒng)的主要目標(biāo)是增強(qiáng)程序執(zhí)行的并行性，以獲得更高的系統(tǒng)處理能力，提高系統(tǒng)的運(yùn)算速度，滿足各應(yīng)用領(lǐng)域?qū)τ?jì)算機(jī)系統(tǒng)性能的需求2023/2/6662.多機(jī)操作系統(tǒng)分類主從式——操作系統(tǒng)僅在指定的主處理機(jī)上運(yùn)行。主處理機(jī)管理整個(gè)系統(tǒng)并為從處理機(jī)分配任務(wù)，從處理機(jī)通過軟中斷或訪管訪問主機(jī)。2023/2/667單獨(dú)管理——每個(gè)處理機(jī)具有自己的操作系統(tǒng)或管理程序，按照自身需要，獨(dú)立運(yùn)行和管理。2023/2/668浮動(dòng)管理——主處理機(jī)可以從一個(gè)處理機(jī)浮動(dòng)到另一個(gè)處理機(jī)，任何處理機(jī)均可成為主處理機(jī)。2023/2/669§4.2任務(wù)分配——調(diào)度策略1、概述調(diào)度——為了優(yōu)化某個(gè)目標(biāo)函數(shù)，在一組具有任意特性的處理機(jī)中對一組進(jìn)程進(jìn)行調(diào)度。調(diào)度主要作出兩個(gè)決定：決定把程序和數(shù)據(jù)分配到物理存儲(chǔ)器的什么位置決定每個(gè)進(jìn)程在哪個(gè)處理機(jī)上運(yùn)行2023/2/670調(diào)度算法是對一組給定進(jìn)程進(jìn)行調(diào)度的過程，目的是研究處理機(jī)的分配和進(jìn)程調(diào)度技術(shù)，以達(dá)到使用最少數(shù)量的處理機(jī)在最短時(shí)間內(nèi)完成并行程序。調(diào)度算法效率： 當(dāng)調(diào)度算法可以描述為一個(gè)多項(xiàng)式算法，效率較高 當(dāng)調(diào)度算法可以描述為一個(gè)指數(shù)算法，效率較低2023/2/671與調(diào)度相關(guān)的一些性能指標(biāo)（參數(shù)）最小完成時(shí)間所需最少處理機(jī)數(shù)目最小平均流處理機(jī)最大利用率處理機(jī)最小空閑時(shí)間2023/2/672一般情況下，尋找最優(yōu)的調(diào)度算法不一定是最好的調(diào)度算法或不存在最優(yōu)調(diào)度算法。所以最優(yōu)調(diào)度算法往往指為合理的調(diào)度算法2023/2/673長期進(jìn)程調(diào)度短期進(jìn)程調(diào)度兩類調(diào)度：確定性調(diào)度不確定性調(diào)度2023/2/674兩種調(diào)度方法：搶先調(diào)度——一個(gè)任務(wù)完成之前允許被打斷，以后可以接續(xù)恢復(fù)執(zhí)行的調(diào)度非搶先調(diào)度——當(dāng)一臺處理機(jī)分配給某個(gè)任務(wù)后，該處理機(jī)為該任務(wù)提供服務(wù)直至該任務(wù)完成2023/2/675粒度組合與調(diào)度做并行程序設(shè)計(jì)時(shí)要回答兩個(gè)基本問題：（1）如何將程序劃分成并行模塊、子任務(wù)以獲得最短執(zhí)行時(shí)間。（2）計(jì)算中的并發(fā)粒度為多大會(huì)比較理想。與問題以及機(jī)器有關(guān)，需要在并行性與調(diào)度開銷之間做折衷。2023/2/676最小平均流時(shí)間調(diào)度

設(shè)多機(jī)系統(tǒng)為異構(gòu)型或各處理機(jī)速度不同。已知每個(gè)任務(wù)在每個(gè)處理機(jī)上的執(zhí)行時(shí)間，對于一組相互獨(dú)立的任務(wù)，可獲得最小平均流時(shí)間。 對于m個(gè)處理機(jī)和n個(gè)任務(wù)，有m×n的矩陣表示每個(gè)任務(wù)在不同處理機(jī)上的執(zhí)行時(shí)間，Tij表示任務(wù)Tj在處理機(jī)Pi上的執(zhí)行時(shí)間。2023/2/6773、不確定性調(diào)度不確定性調(diào)度的基本思路：(1)進(jìn)一步探索進(jìn)程執(zhí)行時(shí)間的規(guī)律，以獲得任務(wù)的執(zhí)行時(shí)間或相應(yīng)的數(shù)據(jù)(2)在運(yùn)行過程中保證各處理機(jī)滿負(fù)荷運(yùn)行2023/2/678排隊(duì)調(diào)度 設(shè)有P個(gè)處理機(jī)和無界要求服務(wù)的任務(wù)隊(duì)列，已知任務(wù)到達(dá)的時(shí)間間隔概率分布，處理機(jī)處理時(shí)間的概率分布，并且任務(wù)到達(dá)時(shí)間間隔和處理時(shí)間概率分布相互獨(dú)立。利用排隊(duì)模型可以求得任務(wù)響應(yīng)的平均時(shí)間或給出任務(wù)平均響應(yīng)時(shí)間，求所需的處理機(jī)數(shù)目。（經(jīng)過統(tǒng)計(jì)，任務(wù)到達(dá)服從愛爾郎Erlang分布）2023/2/679動(dòng)態(tài)負(fù)載平衡兩個(gè)含義：（1）在程序執(zhí)行過程中對任務(wù)進(jìn)行分解和分配，將任務(wù)從一臺處理機(jī)向另一臺處理機(jī)調(diào)動(dòng)（2）將任務(wù)從重載處理機(jī)向空載或輕載處理機(jī)上遷移動(dòng)態(tài)調(diào)度的依據(jù)，系統(tǒng)狀態(tài)信息。需要通過交換信息了解系統(tǒng)狀態(tài)兩種交換方式：同步方式：按固定時(shí)間互通信息 （多長時(shí)間互通一次信息？）異步方式：因某一事件觸發(fā)互通信息2023/2/680負(fù)載平衡策略接收者負(fù)載平衡——在任務(wù)并行執(zhí)行過程中，當(dāng)某處理機(jī)空載時(shí)，按“征兵協(xié)議”向周圍結(jié)點(diǎn)發(fā)出征載請求，鄰近的重載處理機(jī)進(jìn)行響應(yīng)，相互建立聯(lián)系。發(fā)送者負(fù)載平衡——在任務(wù)并行執(zhí)行過程中，重載處理機(jī)按“招標(biāo)協(xié)議”向外廣播尋求幫助?？蛰d處理機(jī)收到請求，給予響應(yīng)?！罢鞅鴧f(xié)議”適用于負(fù)載比較平衡的系統(tǒng)“招標(biāo)協(xié)議”適用于負(fù)載不平衡的系統(tǒng)2023/2/681幾個(gè)基本參數(shù)：負(fù)載——處理機(jī)運(yùn)行的用戶程序沒有完成的工作量。包括計(jì)算時(shí)間和通信時(shí)間。往往與具體的求解問題有關(guān)，需要按一定的方法估算。負(fù)載閾值——處理機(jī)負(fù)載的某一界限值。當(dāng)某未完成任務(wù)的負(fù)載低于此值，就不適于再分解。 設(shè)任務(wù)P的計(jì)算時(shí)間為Tp，分解為兩個(gè)子任務(wù)P1，P2。計(jì)算時(shí)間為Tp/2。若任務(wù)通信時(shí)間為Tc，當(dāng)Tp/2<Tc時(shí)，并行處理失效。所以負(fù)載閾值T>2Tc。2023/2/682輕載——處理機(jī)負(fù)載小于負(fù)載閾值重載——處理機(jī)負(fù)載大于負(fù)載閾值空載——處理機(jī)空閑負(fù)載平衡——處理機(jī)均重載或處理機(jī)為空載和輕載2023/2/683第五章并行程序設(shè)計(jì)概況§4.1概述并行程序設(shè)計(jì)與算法、系統(tǒng)結(jié)構(gòu)有密切的關(guān)系。并行性的關(guān)鍵在算法。研究并行算法及程序設(shè)計(jì)，是多機(jī)系統(tǒng)的一個(gè)重要研究課題。其中相關(guān)問題是十分重要和難以解決的問題之一。2023/2/684并行性級作業(yè)級、程序級進(jìn)程級、任務(wù)級線程級進(jìn)程是并行程序的基本單位程序數(shù)據(jù)分解－幾個(gè)劃分2023/2/685并行程序設(shè)計(jì)模型共享變量模型

消息傳遞模型數(shù)據(jù)并行模型面向?qū)ο竽Ｐ?/p>

2023/2/686§4.2并行性條件1.數(shù)據(jù)相關(guān) 值相關(guān)

流相關(guān)反相關(guān)輸出相關(guān)2023/2/687控制相關(guān)

S2的執(zhí)行與否取決于S1的執(zhí)行結(jié)果并行性檢測

Bernstein準(zhǔn)則（伯恩斯坦1966）程序中的相關(guān)性處理－基本塊

2023/2/688例：P1:C=D×EP2: M=G+CP3: A=B+CP4: C=L+MP5: F=G/E交換性：Pi//PjPj//Pi結(jié)合性：Pi//Pj//Pk(Pi//Pj)//PkPi//(Pj//Pk)無傳遞性：Pi//PjPj//Pk無Pi≠Pk

2023/2/689§4.3并行語言與編譯器并行語言特征優(yōu)化特性：可用性可擴(kuò)展性兼容性可移植性2023/2/690向量化——用向量指令取代串行程序中的一段代碼并行化——用并行指令描述串行程序中可并行執(zhí)行的程序段并行語言結(jié)構(gòu)向量化:

并行化：三種主要并行結(jié)構(gòu)

cobegin-coend

Fork——Join程序結(jié)構(gòu)

parfor并行循環(huán)結(jié)構(gòu)：2023/2/691§6.1引言馮·諾依曼機(jī)的基本特征:

“程序存儲(chǔ)、順序執(zhí)行、二進(jìn)制、五大部件組成、共享數(shù)據(jù)”計(jì)算機(jī)模型。相關(guān)性是并行處理的關(guān)鍵問題并行處理計(jì)算的發(fā)展，兩條路線：對馮·諾依曼機(jī)結(jié)構(gòu)改進(jìn)，適應(yīng)并行處理，解決相關(guān)性問題提出非馮·諾依曼結(jié)構(gòu)

第六章數(shù)據(jù)流計(jì)算機(jī)2023/2/692四種驅(qū)動(dòng)方式計(jì)算機(jī)模型

按控制機(jī)制對計(jì)算機(jī)模型分類，Treleaven教授提出劃分為四種驅(qū)動(dòng)方式：控制驅(qū)動(dòng)數(shù)據(jù)驅(qū)動(dòng)需求驅(qū)動(dòng)模式匹配驅(qū)動(dòng)2023/2/693控制驅(qū)動(dòng)模型

這是傳統(tǒng)的馮·諾依曼型結(jié)構(gòu)基本特征：命令式語言程序順序執(zhí)行，指令的執(zhí)行次序受指令計(jì)數(shù)器的控制，即由程序員指定序列操作其中：“共享數(shù)據(jù)，順序執(zhí)行”與并行性有密切關(guān)系2023/2/694數(shù)據(jù)驅(qū)動(dòng)模型

程序中任意一條指令中所需的操作數(shù)（數(shù)據(jù)令牌）到齊，立即啟動(dòng)執(zhí)行（稱為“點(diǎn)火”）。一條指令的運(yùn)算結(jié)果又流向下一條指令，作為下一條指令的操作數(shù)來驅(qū)動(dòng)此指令的啟動(dòng)執(zhí)行能充分地利用程序中指令級并行性不存在共享數(shù)據(jù)，也不存在指令計(jì)數(shù)器，指令啟動(dòng)執(zhí)行的時(shí)機(jī)僅取決于操作數(shù)具備與否。只要有足夠多的處理單元，凡是相互間不存在數(shù)據(jù)相關(guān)的指令都可以并行執(zhí)行2023/2/695需求驅(qū)動(dòng)模型

一個(gè)操作僅在需要用到其輸出結(jié)果時(shí)才開始啟動(dòng)。如果這時(shí)該操作由于操作數(shù)未到而不能得到輸出結(jié)果，則該操作再去啟動(dòng)能得到它的各個(gè)輸入數(shù)的操作，也可能那些操作還要去啟動(dòng)另外一些操作，這樣就把需求鏈一直延伸下去，直至遇到常數(shù)或外部輸入的數(shù)據(jù)已經(jīng)到達(dá)為止，然后再反方向地去執(zhí)行運(yùn)算。2023/2/696

計(jì)算的運(yùn)行是由謂詞模式匹配加以驅(qū)動(dòng)的，程序的執(zhí)行主要適合于求解非數(shù)值的符號演算。面向智能的計(jì)算機(jī)就是基于“模式匹配驅(qū)動(dòng)”的計(jì)算機(jī)。

模式匹配驅(qū)動(dòng)2023/2/697§6.2數(shù)據(jù)流計(jì)算機(jī)基本工作思路數(shù)據(jù)流計(jì)算機(jī)不共享數(shù)據(jù)，一條指令執(zhí)行后不送存儲(chǔ)器保存，以供其他指令共享，而是直接流向需要該結(jié)果的指令，作為新的操作數(shù)供下一條指令使用。每個(gè)操作數(shù)經(jīng)過指令的一次使用后便消失。如果若干條指令要求使用相同的數(shù)據(jù)，那么就需要事先復(fù)制該數(shù)據(jù)的若干個(gè)副本，分別供多條指令使用。2023/2/698數(shù)據(jù)流驅(qū)動(dòng)的特點(diǎn)

指令的執(zhí)行是由數(shù)據(jù)可用性來驅(qū)動(dòng)，而不是由程序計(jì)數(shù)器來控制。任何指令只要操作數(shù)可用，應(yīng)該說是做好了執(zhí)行的準(zhǔn)備。數(shù)據(jù)驅(qū)動(dòng)程序中的指令不用任何方式來排定次序。數(shù)據(jù)直接保存在指令內(nèi)，不是存在共享存儲(chǔ)器中。2023/2/699計(jì)算結(jié)果（數(shù)據(jù)令牌）直接在指令間傳遞。一條指令產(chǎn)生的數(shù)據(jù)可被復(fù)制成多份副本直接送給所有缺乏數(shù)據(jù)的指令。數(shù)據(jù)令牌一旦被一條指令使用后，它就不能再被其它指令重復(fù)使用。不需要共享存儲(chǔ)器，不需要程序計(jì)數(shù)器，不需要控制定序器。2023/2/6100數(shù)據(jù)流計(jì)算機(jī)指令結(jié)構(gòu)指令主要由操作包(OperationPacket)和數(shù)據(jù)令牌(DataToken)兩部分組成操作包由操作碼(OperationCode)，一個(gè)或幾個(gè)源操作數(shù)(SourceData)及后繼指令地址(NextAddress)等等組成數(shù)據(jù)令牌通常由結(jié)果數(shù)值和目標(biāo)地址等組成。其中的結(jié)果值是上條指令的運(yùn)算結(jié)果，而目標(biāo)地址直接取自上條指令的后繼指令地址，如果一條指令的運(yùn)算結(jié)果要送往幾個(gè)目的地，則分別形成幾個(gè)數(shù)據(jù)令牌，多個(gè)數(shù)據(jù)令牌同時(shí)在各個(gè)操作部件之間傳送，允許有多條指令并行執(zhí)行。2023/2/6101數(shù)據(jù)流驅(qū)動(dòng)四個(gè)性質(zhì)：

異步(Asynchrony)只要本條指令所需要的數(shù)據(jù)令牌都到達(dá)，指令即可獨(dú)立地執(zhí)行，而不必關(guān)心其他指令及數(shù)據(jù)的情況如何。并行性(Parallelism)可同時(shí)地并行執(zhí)行多條指令，而且這種并行性通常是隱含的。函數(shù)性(Functionalism)由于不使用共享的數(shù)據(jù)存儲(chǔ)單元，所以數(shù)據(jù)流程序不會(huì)產(chǎn)生諸如改變存儲(chǔ)字這樣的副作用。也可以說，數(shù)據(jù)流運(yùn)算是純函數(shù)性的。局部性(Locality)操作數(shù)不是作為“地址”變量，而是作為數(shù)據(jù)令牌直接傳送，因此數(shù)據(jù)流運(yùn)算沒有產(chǎn)生長遠(yuǎn)影響的后果，運(yùn)算效果具有局部性。2023/2/6102單賦值規(guī)則。單賦值的含義是指在程序中每個(gè)變量只能賦值一次，即同一變量在賦值語句的左部只允許出現(xiàn)一次，不允許對同一變量進(jìn)行多次賦值。遵循單賦值規(guī)則。這有利于運(yùn)算并行性的開發(fā)，同時(shí)也可防止“副作用”。所謂“副作用”是指在程序執(zhí)行過程中修改了某些參數(shù)的值指令的執(zhí)行次序由數(shù)據(jù)依賴關(guān)系確定，指令執(zhí)行規(guī)則簡單地僅受數(shù)據(jù)相關(guān)性約束。控制變量的應(yīng)用范圍

數(shù)據(jù)流語言基本特征：2023/2/61033.數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)

靜態(tài)數(shù)據(jù)流計(jì)算機(jī)基本點(diǎn)：數(shù)據(jù)令牌不帶任何標(biāo)號，每條有向分支線上在某一個(gè)時(shí)刻只能傳送一個(gè)數(shù)據(jù)令牌，每個(gè)結(jié)點(diǎn)一次只能執(zhí)行一個(gè)操作。執(zhí)行規(guī)則：結(jié)點(diǎn)的每一條輸入分支線上都有一個(gè)令牌出現(xiàn)（數(shù)據(jù)分支線上出現(xiàn)的數(shù)據(jù)令牌，控制分支線上出現(xiàn)攜帶結(jié)點(diǎn)操作所要求控制信號的控制令牌），而且輸出分支線上沒有令牌時(shí)，該結(jié)點(diǎn)的操作才能夠被執(zhí)行。具有數(shù)據(jù)令牌，還有控制令牌，由這兩種令牌同時(shí)來決定結(jié)點(diǎn)的操作是否執(zhí)行2023/2/6104兩種實(shí)現(xiàn)可重入代碼的并發(fā)調(diào)用方法重入代碼復(fù)制 當(dāng)數(shù)據(jù)流程序需要調(diào)用一段可重入代碼時(shí)，復(fù)制這段代碼形成一個(gè)副本被調(diào)用執(zhí)行。執(zhí)行結(jié)束后把結(jié)果送到輸出端保留，以備其它指令應(yīng)用，副本隨即消失。問題：復(fù)制過程開銷大，程序副本占大量的存儲(chǔ)空間。動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)2023/2/6105馮.諾依曼結(jié)構(gòu)可重入代碼的遞歸調(diào)用均是一次調(diào)用總是在上次調(diào)用之后進(jìn)行。每時(shí)刻僅有一個(gè)可重入代碼的副本在運(yùn)行，從而保證了多次調(diào)用的順序。數(shù)據(jù)流機(jī)的并行可能并發(fā)調(diào)用同一個(gè)可重入代碼，即同一時(shí)刻有多個(gè)副本在運(yùn)行，流動(dòng)著不同次的操作數(shù)，流動(dòng)路徑的不同可能導(dǎo)致產(chǎn)生結(jié)果的時(shí)間不同，引發(fā)不同次操作數(shù)的混亂。帶標(biāo)志數(shù)據(jù)令牌 對同一次調(diào)用的重入代碼中的數(shù)據(jù)令牌加相同的標(biāo)志2023/2/6106基本點(diǎn)：每個(gè)數(shù)據(jù)令牌都帶有標(biāo)號（令牌標(biāo)號及其他特征信息），從而使數(shù)據(jù)流程圖中的一條有向分支線上可同時(shí)傳送（帶不同標(biāo)號）幾個(gè)數(shù)據(jù)令牌不需要用控制令牌來確認(rèn)指令間數(shù)據(jù)令牌的傳送。采用一個(gè)專門硬件（匹配部件）對數(shù)據(jù)令牌中的標(biāo)號進(jìn)行符合比較并加以識別。2023/2/6107數(shù)據(jù)流計(jì)算機(jī)的優(yōu)點(diǎn)

高度并行運(yùn)算。。流水線異步操作。與VLSI技術(shù)相適應(yīng)。有利于提高軟件生產(chǎn)能力2023/2/6108數(shù)據(jù)流計(jì)算機(jī)的缺點(diǎn)

操作開銷過大不能有效利用傳統(tǒng)計(jì)算機(jī)的研究成果數(shù)據(jù)流語言尚不完善2023/2/6109需要解決的幾個(gè)主要問題

合理的劃分并行性，減少開銷

多級并行（作業(yè)，進(jìn)程，函數(shù)級），一部分在編譯時(shí)完成，一部分在運(yùn)行時(shí)完成）復(fù)合函數(shù)、過程級（循環(huán)，數(shù)組等操作）的并行（Gajks,Motooka等人）同步與異步結(jié)合 函數(shù)級異步，指令級同步。

程序如何分解并如何把程序模塊分配給各處理部件。

研制易于使用，易于由硬件實(shí)現(xiàn)的高級數(shù)據(jù)流語言。

2023/2/6110第七章可擴(kuò)展性,時(shí)延包容性與順序一致性2023/2/6111§7.1可擴(kuò)展設(shè)計(jì)原理一、可擴(kuò)展性概念一般并行計(jì)算機(jī)系統(tǒng)擴(kuò)展性認(rèn)為可擴(kuò)展為成百或成千個(gè)處理器。實(shí)際上應(yīng)是整個(gè)系統(tǒng)各方面都是可擴(kuò)展的。處理機(jī)可擴(kuò)展存儲(chǔ)器可擴(kuò)展（容量、帶寬等）互連網(wǎng)絡(luò)可擴(kuò)展協(xié)議可擴(kuò)展應(yīng)用性能可擴(kuò)展2023/2/6112兩種并行系統(tǒng)的擴(kuò)展性：基于總線共享存儲(chǔ)結(jié)構(gòu)基于Internet的分布系統(tǒng)

可擴(kuò)展性設(shè)計(jì)的目標(biāo)是以通信結(jié)構(gòu)為基礎(chǔ)的折中。2023/2/6113二、可擴(kuò)展范圍1、資源可擴(kuò)展性

通過增加機(jī)器規(guī)模、存儲(chǔ)部件規(guī)模以及軟件規(guī)模等方法，使系統(tǒng)具有更高性能或功能。

規(guī)模擴(kuò)展：增加PE數(shù)，包括相應(yīng)網(wǎng)絡(luò)、接口等子系統(tǒng)及對擴(kuò)大的系統(tǒng)進(jìn)行編程。

資源擴(kuò)展：增加MEM容量，包括Cache和磁盤等。

軟件擴(kuò)展：包括擴(kuò)展操作系統(tǒng)、編譯器、數(shù)學(xué)和工程庫、應(yīng)用軟件和編程環(huán)境。2023/2/6114

2、應(yīng)用可擴(kuò)展性機(jī)器規(guī)?？蓴U(kuò)展性：

問題規(guī)?？蓴U(kuò)展性3、技術(shù)可擴(kuò)展性代可擴(kuò)展性：異構(gòu)可擴(kuò)展性：空間可擴(kuò)展性