并行計算機體系結構復習

2023/2/61并行計算機體系結構復習計算機系2023/2/62第一章概論§1.1引言1、計算機性能與結構關系2、需求3、可行性2023/2/63§1.2并行處理的定義

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

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

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

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

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

按指令流、數(shù)據流分類指令流－機器執(zhí)行指令的序列數(shù)據流－由指令調用的數(shù)據的序列單指令流單數(shù)據流SISD單指令流多數(shù)據流SIMD多指令流單數(shù)據流MISD多指令流多數(shù)據流MIMD§1.4并行處理機的分類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根據計算機系統(tǒng)中流水線和并行程度分類。從三個子系統(tǒng)級分析：處理機級PCU、算術邏輯部件級ALU、位級BIC§1.4并行處理機的分類2023/2/611向量流水機：陣列處理機：(含脈動陣列）SIMD關聯(lián)處理機：具有聯(lián)想存儲，按內容存取、邏輯操作等同步系統(tǒng)（統(tǒng)一時鐘）按體系結構分類§1.4并行處理機的分類2023/2/612§1.4并行處理機的分類由獨立執(zhí)行指令的處理器構成分布存儲系統(tǒng)：多個存儲器物理上分布集中存儲系統(tǒng)：存儲器物理上相對集中多處理機系統(tǒng)MIMD2023/2/613SIMD PVP并行向量處理機 （ParallelVectorProcessor）SMP對稱多處理機

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

（DistributedSharedMemory）COW工作站機群

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

三者之間的關系2023/2/619從四個方面討論并行計算機模型并行計算機結構模型并行計算機訪存模型并行計算機性能模型并行計算機Cache一致性2023/2/620SIMD PVP并行向量處理機 （ParallelVectorProcessor）SMP對稱多處理機

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

（DistributedSharedMemory）COW工作站機群

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

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

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

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

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

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

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

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

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

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

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

多機系統(tǒng)中cache一致性維護策略的改進：

基本思路：

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

更新法（Write-Update)

作廢法（Write-Invalidate)

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

(1)采用WT策略的一致性維護(2)采用WB策略的一致性維護2023/2/6404.基于目錄的協(xié)議全映射目錄有限目錄鏈式目錄2023/2/641第三章互連網絡§3.1網絡特性

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

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

尋徑函數(shù)：五個基本尋經函數(shù)2023/2/644各種互連函數(shù)與其逆函數(shù)之間有如下關系：2023/2/645部分互連函數(shù)之間的關系：2023/2/646§3.3靜態(tài)互連網絡

按不同的拓撲結構，連接結點的入出端。每種連接以一種尋徑函數(shù)表示。若存在m中連接，用m個尋徑函數(shù)表示。既一個結點可以與多個結點直接連接。一個靜態(tài)互連網絡SW，可表示為：

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

排隊器——優(yōu)先權編碼器 菊花鏈——靜態(tài)菊花鏈、動態(tài)菊花鏈2023/2/649多級互連網絡：速度高，靈活性好，傳輸率低于完全開關網絡，適用于PE較多的情形。其性能特點反映在以下三個方面： 開關形式 級間拓撲結構 控制方式2023/2/650

4）

控制方式對各個交換開關進行控制的方式有三種：(1)

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

ε(0)β(3)

ε(0)σn

–1

STARAN網

5.

幾種常見的多級互連網絡(1)

STARAN網絡：2023/2/6522)

Omega網絡——多級混洗交換網絡

由n級相同的網絡構成，每一級包含一個完全混洗連接及隨后一列2n-1個4功能交叉開關單元，采用單元控制方式，一般形式：7012345670415263760124502461357ABCDEFGHIJKL實質為STARAN網入出交換，并交換一下F、G位置，但不改變拓撲連接。0123456704152637601234502134657ABCDEGFHIJKL3σε（0）σε（0）σε（0）2023/2/6533)

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

榕樹(Banyan)網絡

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

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

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

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

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

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

消息傳遞模型數(shù)據并行模型面向對象模型

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

流相關反相關輸出相關2023/2/687控制相關

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

Bernstein準則（伯恩斯坦1966）程序中的相關性處理－基本塊

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

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

并行化：三種主要并行結構

cobegin-coend

Fork——Join程序結構

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

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

第六章數(shù)據流計算機2023/2/692四種驅動方式計算機模型

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

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

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

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

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

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

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

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

數(shù)據流語言基本特征：2023/2/61033.數(shù)據流計算機結構

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

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

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

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

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

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

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

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

可擴展性設計的目標是以通信結構為基礎的折中。2023/2/6113二、可擴展范圍1、資源可擴展性

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

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

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

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

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

問題規(guī)模可擴展性3、技術可擴展性代可擴展性：異構可擴展性：空間可擴展性