第9章并行體系結(jié)構(gòu)

第9章

并行體系結(jié)構(gòu)計(jì)算機(jī)組成與系統(tǒng)結(jié)構(gòu)第9章并行系統(tǒng)結(jié)構(gòu)9.1并行處理系統(tǒng)概述9.2指令級高度并行的處理機(jī)9.3超長指令字處理機(jī)9.4超線程和多核處理器9.5向量處理機(jī)9.6并行處理機(jī)9.7多處理機(jī)與多計(jì)算機(jī)9.1并行處理機(jī)系統(tǒng)概述

并行處理是指能同時(shí)執(zhí)行兩個(gè)或多個(gè)處理的一種計(jì)算方法。并行處理系統(tǒng)則是指同時(shí)執(zhí)行多個(gè)任務(wù)或多條指令或同時(shí)對多個(gè)數(shù)據(jù)項(xiàng)進(jìn)行處理的計(jì)算機(jī)系統(tǒng)。9.1.1系統(tǒng)結(jié)構(gòu)中的并行性1.并行性的含義與并行性級別

并行性包含同時(shí)性和并發(fā)性二重含義。

同時(shí)性——兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生。

并發(fā)性——兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。9.1并行處理機(jī)系統(tǒng)概述

從計(jì)算機(jī)系統(tǒng)中執(zhí)行程序的角度來看，并行性等級從低到高可以分為5級。它們分別是：指令內(nèi)部并行——一條指令內(nèi)部各個(gè)微操作之間的并行。指令級并行——多條指令的并行執(zhí)行。線程級并行——并行執(zhí)行兩個(gè)或兩個(gè)以上的線程。任務(wù)或進(jìn)程間并行——多個(gè)任務(wù)或程序段的并行執(zhí)行。作業(yè)或程序間并行——多個(gè)作業(yè)或多道程序的并行。9.1并行處理機(jī)系統(tǒng)概述

從計(jì)算機(jī)系統(tǒng)中處理數(shù)據(jù)的并行性來看，并行性等級從低到高可以分為：位串字串——同時(shí)只對一個(gè)字的一位進(jìn)行處理，這是最基本的串行處理方式，沒有并行性。位并字串——同時(shí)對一個(gè)字的全部位進(jìn)行處理，不同字之間是串行。位片串字并——同時(shí)對許多字的同一位（稱為位片）進(jìn)行處理，這種方式具有較高的并行性，開始進(jìn)入并行處理領(lǐng)域。全并行——同時(shí)對許多字的全部或部分位進(jìn)行處理。這是最高一級的并行。9.1并行處理機(jī)系統(tǒng)概述

并行性是貫穿于計(jì)算機(jī)信息加工的各個(gè)步驟和階段的，從這個(gè)角度來看，并行性等級又可分為：存儲器操作并行——可以采用單體多字、多體單字或多體多字方式在一個(gè)存儲周期內(nèi)訪問多個(gè)字，進(jìn)而采用按內(nèi)容訪問方式在一個(gè)存儲周期內(nèi)用位片串字并或全并行方式實(shí)現(xiàn)對存儲器中大量字的高速并行比較、檢索、更新、變換等操作。典型的例子就是并行存儲器系統(tǒng)和以相聯(lián)存儲器為核心構(gòu)成的相聯(lián)處理機(jī)。處理器操作步驟并行——處理器操作步驟可以指一條指令的取指、分析、執(zhí)行等操作步驟，也可指如浮點(diǎn)加法的求階差、對階、尾數(shù)加、舍入、規(guī)格化等具體操作的執(zhí)行步驟。處理器操作步驟并行是將操作步驟或具體操作的執(zhí)行步驟在時(shí)間上重疊流水地進(jìn)行。典型的例子就是流水線處理機(jī)。9.1并行處理機(jī)系統(tǒng)概述處理器操作并行——為支持向量、數(shù)組運(yùn)算，可以通過重復(fù)設(shè)置大量處理單元，讓它們在同一控制器的控制下，按照同一條指令的要求對多個(gè)數(shù)據(jù)組同時(shí)操作。典型的例子就是陣列處理機(jī)。指令、任務(wù)、作業(yè)并行——這是較高級的并行，雖然它也可包含如操作、操作步驟等較低等級的并行，但原則上與操作級并行是不同的。指令級以上的并行是多個(gè)處理機(jī)同時(shí)對多條指令及有關(guān)的多數(shù)據(jù)組進(jìn)行處理，而操作級并行是對同一條指令及其有關(guān)的多數(shù)據(jù)組進(jìn)行處理。因此，前者構(gòu)成的是多指令流多數(shù)據(jù)流計(jì)算機(jī)，后者構(gòu)成的則是單指令流多數(shù)據(jù)流計(jì)算機(jī)。典型的例子是多處理機(jī)系統(tǒng)。9.1并行處理機(jī)系統(tǒng)概述2.開發(fā)并行性的途徑

時(shí)間重疊資源重復(fù)資源共享9.1并行處理機(jī)系統(tǒng)概述時(shí)間重疊

在并行性概念中引入時(shí)間因素，讓多個(gè)處理過程在時(shí)間上相互錯(cuò)開，輪流重疊地使用同一套硬件設(shè)備的各個(gè)部分，以加快硬件周期而贏得速度。9.1并行處理機(jī)系統(tǒng)概述資源重復(fù)

在并行性概念中引入空間因素，通過重復(fù)設(shè)置硬件資源來提高可靠性或性能。9.1并行處理機(jī)系統(tǒng)概述資源共享

利用軟件的方法讓多個(gè)用戶按一定時(shí)間順序輪流地使用同一套資源，以提高利用率，這樣也可以提高整個(gè)系統(tǒng)的性能。多道程序、分時(shí)系統(tǒng)就是遵循這一途徑而產(chǎn)生的。資源共享不只限于硬件資源的共享，也包括軟件、信息資源的共享。9.1并行處理機(jī)系統(tǒng)概述9.1.2并行處理系統(tǒng)的分類 Flynn分類法，它按照指令流和數(shù)據(jù)流的多倍性特征對計(jì)算機(jī)系統(tǒng)進(jìn)行分類。

指令流：計(jì)算機(jī)執(zhí)行的指令序列。

數(shù)據(jù)流：由指令流調(diào)用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和中間結(jié)果。

多倍性：在系統(tǒng)性能瓶頸部件上同時(shí)處于同一執(zhí)行階段的指令或數(shù)據(jù)的最大可能個(gè)數(shù)。9.1并行處理機(jī)系統(tǒng)概述按照指令流和數(shù)據(jù)流的不同組織方式，有：

數(shù)據(jù)流指令流單多單SISDSIMD多MISDMIMD9.1并行處理機(jī)系統(tǒng)概述

單指令流單數(shù)據(jù)流（SISD）；

單指令流多數(shù)據(jù)流（SIMD）；

多指令流單數(shù)據(jù)流（MISD）；

多指令流多數(shù)據(jù)流（MIMD）。9.1并行處理機(jī)系統(tǒng)概述

傳統(tǒng)的單處理機(jī)屬SISD類型，它每次只對一條指令譯碼，并只對一個(gè)操作部件分配數(shù)據(jù)。CUPUMMISDSSISD9.1并行處理機(jī)系統(tǒng)概述PUMMISDS1SIMDCUPUPUDS2DSnMM…… SIMD類型以并行處理機(jī)為代表，系統(tǒng)中有多個(gè)相同的PU，但由單一的CU控制，多個(gè)各自的數(shù)據(jù)完成同一條指令規(guī)定的操作。從CU看，指令順序（串行）執(zhí)行，從PU看，數(shù)據(jù)并行執(zhí)行。9.1并行處理機(jī)系統(tǒng)概述MMDSMISDPUIS1CUMM……PUIS2CUPUISnCU…………9.1并行處理機(jī)系統(tǒng)概述 MISD類型的系統(tǒng)具有n個(gè)PU，按n條不同指令的要求對同一數(shù)據(jù)流及其中間結(jié)果進(jìn)行不同的處理。一個(gè)PU的輸出又作為另一個(gè)PU的輸入。過去認(rèn)為，與MISD類型對應(yīng)的機(jī)器實(shí)際上并不存在，因?yàn)閹讞l指令對同一個(gè)數(shù)據(jù)進(jìn)行不同處理，它要求系統(tǒng)在指令級上并行，而在數(shù)據(jù)級上又不并行，這是不太現(xiàn)實(shí)的。但現(xiàn)在也有些學(xué)者有不同的看法，在有些文獻(xiàn)中將超標(biāo)量處理機(jī)以及超長指令字計(jì)算機(jī)等看作是MISD類型。9.1并行處理機(jī)系統(tǒng)概述 MIMD類型是能實(shí)現(xiàn)作業(yè)、任務(wù)、指令、數(shù)組各級全面并行的多機(jī)系統(tǒng)，它包括了大多數(shù)多處理機(jī)及多計(jì)算機(jī)系統(tǒng)。MMMIMDPUIS1CUMM……PUIS2CUPUISnCU…………DS1DS2DSn第9章并行系統(tǒng)結(jié)構(gòu)9.1并行處理系統(tǒng)概述9.2指令級高度并行的處理機(jī)9.3超長指令字處理機(jī)9.4超線程和多核處理器9.5向量處理機(jī)9.6并行處理機(jī)9.7多處理機(jī)與多計(jì)算機(jī)9.2指令級高度并行的處理機(jī)9.2.1超標(biāo)量處理機(jī)

超標(biāo)量處理機(jī)采取設(shè)置m條指令流水線同時(shí)并行工作，每隔一個(gè)Δt最多可流出m條指令，即每個(gè)基本時(shí)鐘周期同時(shí)取多條指令、同時(shí)譯碼多條指令，同時(shí)執(zhí)行多條指令，同時(shí)寫回多個(gè)運(yùn)算結(jié)果。9.2指令級高度并行的處理機(jī)

m=3的超標(biāo)量處理機(jī)的指令流水線執(zhí)行圖，同時(shí)發(fā)射3條指令，每個(gè)時(shí)鐘周期取3條指令。9.2指令級高度并行的處理機(jī)2.超標(biāo)量處理機(jī)性能

指令級并行度為(m,1)的超標(biāo)量處理機(jī)，執(zhí)行N條指令所用的時(shí)間為：超標(biāo)量處理機(jī)相對于單流水線普通標(biāo)量處理機(jī)的加速比為：9.2指令級高度并行的處理機(jī)即：

當(dāng)N→∞時(shí)，在沒有資源沖突，沒有數(shù)據(jù)相關(guān)和控制相關(guān)的理想情況下，超標(biāo)量處理機(jī)的加速比的最大值為：S(m,1)MAX=m9.2指令級高度并行的處理機(jī)9.2.2超流水線處理機(jī)

超標(biāo)量處理機(jī)采用的是空間并行性，通過增加硬件資源為代價(jià)來換取處理機(jī)性能。而超流水線處理機(jī)采用的是時(shí)間并行性，通過各硬件部件充分重疊工作來提高處理機(jī)性能，只需增加少量硬件，以更小的節(jié)拍工作。1.超流水線處理機(jī)的指令執(zhí)行

超流水線處理機(jī)在一個(gè)時(shí)鐘周期內(nèi)可以分時(shí)發(fā)射多條指令，假設(shè)每個(gè)時(shí)鐘周期Δt分時(shí)地發(fā)射n條指令，則每隔Δt’就流出一條指令，此時(shí)Δt’=Δt/n，即每隔1/n個(gè)時(shí)鐘周期發(fā)射一條指令，流水線周期為1/n個(gè)時(shí)鐘周期。9.2指令級高度并行的處理機(jī)每個(gè)時(shí)鐘周期分時(shí)發(fā)送3條指令的超流水線處理機(jī)的指令流水線執(zhí)行圖6.679.2指令級高度并行的處理機(jī)2.超流水線處理機(jī)性能

指令級并行度為（1,n）的超流水線處理機(jī)，執(zhí)行N條指令所的時(shí)間為：

超流水線處理機(jī)相對于單流水線普通標(biāo)量處理機(jī)的加速比為：9.2指令級高度并行的處理機(jī)即：

當(dāng)N→∞時(shí)，在沒有資源沖突，沒有數(shù)據(jù)相關(guān)和控制相關(guān)的理想情況下，超流水線處理機(jī)的加速比的最大值為：S(1,n)MAX=n9.2指令級高度并行的處理機(jī)9.2.3超標(biāo)量超流水線處理機(jī)

把超標(biāo)量與超流水線技術(shù)結(jié)合在一起，就成為超標(biāo)量超流水線處理機(jī)。1.超標(biāo)量與超流水線處理機(jī)的指令執(zhí)行

超標(biāo)量超流水線處理機(jī)在一個(gè)時(shí)鐘周期內(nèi)分時(shí)發(fā)射指令n次，每次同時(shí)發(fā)射指令m條，每個(gè)時(shí)鐘周期總共發(fā)射指令m×n條。9.2指令級高度并行的處理機(jī)

每個(gè)時(shí)鐘周期發(fā)射3次，每次3條指令的超標(biāo)量超流水線處理機(jī)的指令流水線執(zhí)行圖。每個(gè)時(shí)鐘周期分n個(gè)格，每格發(fā)射m條指令。當(dāng)m和n都為3時(shí)，每個(gè)時(shí)鐘周期發(fā)射9條指令。9.2指令級高度并行的處理機(jī)2.超標(biāo)量超流水線處理機(jī)性能

指令級并行度為（m,n）的超標(biāo)量超流水線處理機(jī)，連續(xù)執(zhí)行N條指令所需要的時(shí)間為：

超標(biāo)量超流水線處理機(jī)相對于單流水線標(biāo)量處理機(jī)的加速比為：9.2指令級高度并行的處理機(jī)即：

當(dāng)N→∞時(shí)，在沒有資源沖突，沒有數(shù)據(jù)相關(guān)和控制相關(guān)的理想情況下，超標(biāo)量超流水線處理機(jī)加速比的最大值為：S(m,n)MAX＝mn9.2指令級高度并行的處理機(jī)9.2.4指令級并行處理機(jī)性能比較

指令級并行度（ILP）是指一個(gè)時(shí)鐘周期內(nèi)流水線上流出的指令數(shù)。常規(guī)標(biāo)量流水線的ILP≤1。超標(biāo)量處理機(jī)假設(shè)每個(gè)時(shí)鐘周期發(fā)射m條指令，則有1＜ILP≤m。超流水線處理機(jī)假設(shè)每個(gè)時(shí)鐘周期Δt分時(shí)地發(fā)射n條指令，則有1＜ILP≤n。超標(biāo)量超流水線處理機(jī)則集中了超標(biāo)量和超流水線處理機(jī)的特點(diǎn)，則有1＜ILP≤m×n。第9章并行系統(tǒng)結(jié)構(gòu)9.1并行處理系統(tǒng)概述9.2指令級高度并行的處理機(jī)9.3超長指令字處理機(jī)9.4超線程和多核處理器9.5向量處理機(jī)9.6并行處理機(jī)9.7多處理機(jī)與多計(jì)算機(jī)9.3超長指令字處理機(jī)

超長指令字（VLIW）是一種非常長的指令組合，它把許多條指令連在一起，增加了運(yùn)算的速度。在這種處理機(jī)中，編譯器把許多簡單、獨(dú)立的指令組合到一條指令字中。當(dāng)這個(gè)指令字從主存中取出放到處理器中時(shí)，它們被容易地分解成幾條簡單的指令，這些簡單的指令被分派到一些獨(dú)立的執(zhí)行單元去執(zhí)行。9.3.1VLIW處理機(jī)的特點(diǎn)

超長指令字處理機(jī)在一個(gè)時(shí)鐘周期內(nèi)可以發(fā)射一條超長指令字中的多條基本指令，實(shí)現(xiàn)多條指令的并行執(zhí)行，它與同樣具有多發(fā)射指令的超標(biāo)量處理機(jī)不同，超標(biāo)量處理機(jī)指令的并行性是由處理模塊硬件來檢驗(yàn)，無須編譯保證。由于超長指令字處理機(jī)的指令并行調(diào)度由編譯完成，運(yùn)行時(shí)不需要檢驗(yàn)，因此VLIW方式簡化了控制電路，使得它的結(jié)構(gòu)簡單，芯片制造成本低，能耗小。9.3超長指令字處理機(jī)超長指令字處理機(jī)的指令流水線執(zhí)行圖。并行操作是在流水線的執(zhí)行階段進(jìn)行的。并行執(zhí)行3個(gè)操作，相當(dāng)于指令并行度為3。9.3超長指令字處理機(jī)VLlW處理機(jī)的主要特點(diǎn)是：①

超長指令字的生成是由編譯器來完成的，由它將串行的操作序列合并為可并行執(zhí)行的指令序列，以最大限度實(shí)現(xiàn)操作并行性。②

單一的控制流，只有一個(gè)控制器，每個(gè)時(shí)鐘周期啟動一條長指令。③

超長指令字被分成多個(gè)控制字段，每個(gè)字段直接獨(dú)立地控制每個(gè)功能部件。④

含有大量的數(shù)據(jù)通路和功能部件。由于編譯器在編譯時(shí)已解決可能出現(xiàn)的數(shù)據(jù)相關(guān)和資源沖突，故控制硬件比較簡單。9.3超長指令字處理機(jī)9.3.2VLIW處理機(jī)的基本結(jié)構(gòu) VLlW處理機(jī)的一個(gè)超長指令字包含多個(gè)操作字段，每個(gè)字段可與相應(yīng)的功能部件對應(yīng)。這些操作字段包括可并行執(zhí)行的多個(gè)運(yùn)算器控制指令字段、若干個(gè)存儲器控制指令字段和其他操作控制字段。各運(yùn)算部件和共享的大容量寄存器堆直接相連，以便提供運(yùn)算所需要的操作數(shù)或存放運(yùn)算結(jié)果，對數(shù)據(jù)的讀/寫操作也可以通過存儲器指令字段對指定存儲模塊中的存儲單元進(jìn)行。運(yùn)行時(shí)不需要用軟件或硬件來檢測其并行性，而直接由超長指令字來控制機(jī)器中多個(gè)相互獨(dú)立的功能部件并行操作。雖然這種字段控制方式的思路來自于微程序控制器的水平微指令方式，但微指令只對一個(gè)運(yùn)算部件進(jìn)行控制，而VLIW是對多個(gè)功能部件并行控制。9.3超長指令字處理機(jī)

實(shí)際上，VLIW的實(shí)現(xiàn)是由編譯器將多條可以發(fā)送的基本指令捆綁在一條超長指令字中?；诙鄠€(gè)可以同時(shí)執(zhí)行的功能部件的支持，實(shí)現(xiàn)多條指令的并行執(zhí)行。第9章并行系統(tǒng)結(jié)構(gòu)9.1并行處理系統(tǒng)概述9.2指令級高度并行的處理機(jī)9.3超長指令字處理機(jī)9.4超線程和多核處理器9.5向量處理機(jī)9.6并行處理機(jī)9.7多處理機(jī)與多計(jì)算機(jī)9.4超線程和多核處理器9.4.1指令級并行與線程級并行

進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。線程是進(jìn)程的一個(gè)實(shí)體，是CPU調(diào)度和分派的基本單位，它是比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位。線程自己基本上不擁有系統(tǒng)資源，只擁有一點(diǎn)在運(yùn)行中必不可少的資源（如程序計(jì)數(shù)器，一組寄存器和堆棧），但是它可與同屬一個(gè)進(jìn)程的其他的線程共享進(jìn)程所擁有的全部資源。

簡單地說，一個(gè)程序包含著若干個(gè)進(jìn)程，一個(gè)進(jìn)程又包含著若干個(gè)線程。即：程序>進(jìn)程>線程。每個(gè)線程對CPU來說是一個(gè)程序的細(xì)小部分，為了提升CPU的速度，迫切需要一個(gè)能支持同時(shí)處理2個(gè)線程以上的處理器，這就是線程級并行。9.4超線程和多核處理器9.4.2超線程技術(shù)

超線程（HT）簡單地說就是將一個(gè)物理CPU當(dāng)作兩個(gè)邏輯CPU使用，使CPU可以同時(shí)執(zhí)行多重線程，從而發(fā)揮更大的效率。超線程技術(shù)利用特殊的硬件指令，把兩個(gè)邏輯內(nèi)核模擬成兩個(gè)物理芯片，讓單個(gè)處理器都能使用線程級并行計(jì)算，進(jìn)而兼容多線程操作系統(tǒng)和應(yīng)用軟件，減少了CPU的閑置時(shí)間，提高了CPU的運(yùn)行效率。

超線程技術(shù)可以使操作系統(tǒng)或者應(yīng)用軟件的多個(gè)線程同時(shí)運(yùn)行于一個(gè)超線程處理器上，其內(nèi)部的兩個(gè)邏輯處理器共享一組處理器執(zhí)行單元，并行完成加、乘、加載等操作。這樣做可以使得處理器的處理能力提高30%，因?yàn)樵谕粫r(shí)間里應(yīng)用程序可以充分使用芯片的各個(gè)運(yùn)算單元。9.4超線程和多核處理器

超線程技術(shù)可以使處理器在某一時(shí)刻同步并行處理更多指令和數(shù)據(jù)（多個(gè)線程）。所以，超線程是一種可以將CPU內(nèi)部暫時(shí)閑置處理資源充分“調(diào)動”起來的技術(shù)。

超線程技術(shù)實(shí)現(xiàn)的前提條件是需要五大支持，即CPU支持、主板芯片組支持、主板BIOS支持、操作系統(tǒng)支持和應(yīng)用軟件支持。只有滿足這些條件，才能使得系統(tǒng)效能得到提升。9.4超線程和多核處理器9.4.3多核處理技術(shù)1．雙核處理器

雙核處理器是指在一個(gè)處理器上集成兩個(gè)運(yùn)算核心，從而提高計(jì)算能力。每個(gè)核由一個(gè)獨(dú)立處理器的所有組件所組成，可以獨(dú)立運(yùn)行程序指令（多指令），可以訪問存儲器的不同部分（多數(shù)據(jù)）。

雙核處理器并不能達(dá)到1+1=2的效果，也就是說，雙核處理器并不會比同頻率的單核處理器提高一倍的性能。雙核處理器的優(yōu)勢在于多線程應(yīng)用，如果只是處理單個(gè)任務(wù)，運(yùn)行單個(gè)程序，也許雙核處理器與同頻率的單核得到的效果是一樣的。9.4超線程和多核處理器2．超線程技術(shù)與雙核心技術(shù)的區(qū)別

在操作系統(tǒng)中都同樣被識別為兩個(gè)處理器，它們究竟是不是一樣的呢？這個(gè)問題確實(shí)具有迷惑性。其實(shí)，可以簡單地把雙核心技術(shù)理解為兩個(gè)“物理”處理器，是一種“硬”的方式；而超線程技術(shù)只是兩個(gè)“邏輯”處理器，是一種“軟”的方式。9.4超線程和多核處理器3．多核多線程技術(shù)

多核處理器也被稱為片上多處理機(jī)（CMP），這是多處理機(jī)的一種特殊形式，是實(shí)現(xiàn)TLP的一種新型體系結(jié)構(gòu)。目前多核處理器的應(yīng)用范圍已覆蓋了多媒體計(jì)算、嵌入式設(shè)備、個(gè)人計(jì)算機(jī)、商用服務(wù)器和高性能計(jì)算機(jī)等眾多領(lǐng)域。 CMP在一個(gè)芯片上集成多個(gè)微處理器核，每個(gè)微處理器核實(shí)質(zhì)上都是一個(gè)相對簡單的單線程微處理器或者比較簡單的多線程微處理器，這樣多個(gè)微處理器核就可以并行地執(zhí)行程序代碼，因而具有了較高的線程級并行性。9.4超線程和多核處理器

按照單芯片多處理器上的處理器是否相同，可以分為同構(gòu)CMP和異構(gòu)CMP。同構(gòu)CMP在一塊芯片中集成多個(gè)相同的處理器核，同一個(gè)任務(wù)可以分配給任意一個(gè)核處理，簡化了任務(wù)分配。異構(gòu)CMP中包含了不同結(jié)構(gòu)的處理器核，有事務(wù)處理型的、也有計(jì)算型的。用不同類型的處理器核處理不同的任務(wù)，是異構(gòu)體系結(jié)構(gòu)處理器的優(yōu)勢所在。第9章并行系統(tǒng)結(jié)構(gòu)9.1并行處理系統(tǒng)概述9.2指令級高度并行的處理機(jī)9.3超長指令字處理機(jī)9.4超線程和多核處理器9.5向量處理機(jī)9.6并行處理機(jī)9.7多處理機(jī)與多計(jì)算機(jī)9.5向量處理機(jī)9.5.1向量處理的基本概念

由于向量中的各個(gè)元素很少相關(guān)，而且一般都是進(jìn)行相同的運(yùn)算或處理，所以與標(biāo)量運(yùn)算相比，向量運(yùn)算更能發(fā)揮出流水線的效能。但是，如果處理方式不當(dāng)，也會造成相關(guān)或頻繁的功能切換，使流水線性能得不到充分的發(fā)揮。

對向量的運(yùn)算可以采用3種不同的處理方式。例如，要計(jì)算D=A×(B+C)，其中，A、B、C、D都是具有N個(gè)元素的向量，應(yīng)該采用什么樣的處理方式才能最充分發(fā)揮流水線的效能呢？9.5向量處理機(jī)1.橫向處理方式

如果采用逐個(gè)求D向量元素的方法，即訪存取ai、bi、ci元素，按上述算術(shù)表達(dá)式求出di，再取ai+1、bi+1、ci+1，求di+1，被稱為橫向（水平）處理方法。每個(gè)di元素的計(jì)算至少需要用到加、乘兩條指令，分別進(jìn)行bi+ci→k和k×ai→di。

橫向處理方式對逐個(gè)分量進(jìn)行處理。假設(shè)中間結(jié)果為T(I)，則運(yùn)算過程為：9.5向量處理機(jī)逐個(gè)分量進(jìn)行處理：假設(shè)中間結(jié)果為T(I)

計(jì)算第1個(gè)分量：

T(1)

＝B(1)＋C(1)

D(1)＝A(1)×T(1)

計(jì)算第2個(gè)分量：

T(2)

＝B(2)＋C(2)

D(2)＝A(2)×T(2)

……

計(jì)算最后一個(gè)分量：

T(N)

＝B(N)＋C(N)

D(N)＝A(N)×T(N)

這種方式會出現(xiàn)N次先寫后讀相關(guān)，并引起流水線2N次的功能切換，使流水線的吞吐率下降，所以，橫向處理方式不適合于流水處理向量處理機(jī)，而適宜于標(biāo)量機(jī)上用循環(huán)程序?qū)崿F(xiàn)。9.5向量處理機(jī)2.縱向處理方式

縱向處理方式，也稱為垂直處理方式，先將B和C向量元素對的相加運(yùn)算計(jì)算完，中間結(jié)果暫存到k1～kN中，然后再縱向進(jìn)行所有對應(yīng)元素的乘法運(yùn)算。即先完成全部的bi+ci→ki（i從1到N），然后再完成全部的ki×ai→di（i從1到N）。采用縱向處理方式的運(yùn)算過程為：9.5向量處理機(jī)T(1)=B(1)+C(1)T(2)=B(2)+C(2)?T(N)=B(N)+C(N)D(1)=A(1)×T(1)D(2)=A(2)×T(2)?D(N)=A(N)×T(N)9.5向量處理機(jī)采用向量指令則只需要下面兩條指令：VADD B，C，TVMUL A，T，D

這種方式只需一次功能切換，也僅有一次先寫后讀相關(guān)，有利于發(fā)揮出流水機(jī)線的性能，適合于在向量處理機(jī)中應(yīng)用。由于向量長度一般較長，難以用大量的高速寄存器來存放中間變量，所以往往采用存儲器－存儲器型的流水線處理。9.5向量處理機(jī)3.縱橫處理方式

縱橫處理方式又稱為分組處理方式，它是將上述兩種方式相結(jié)合，組內(nèi)按縱向方式處理，組間采用橫向方式處理。

向量寄存器的長度是有限的，例如，每個(gè)向量寄存器有64個(gè)寄存器。若以n為一組，當(dāng)向量長度N大于向量寄存器長度n時(shí)，需要分組處理。

分組方法是N=k×n+r，其中r為余數(shù)，共分k+1組。9.5向量處理機(jī)采用縱向處理方式運(yùn)算過程為：

第1組：

T(1,n)=B(1,n)+C(1,n)

D(1,n)=A(1,n)×T(1,n)

第2組：

T(n+1,2n)=B(n+1,2n)＋C(n+1,2n)

D(n+1,2n)=A(n+1,2n)×T(n+1,2n) ?

最后第k+1組：

T(kn+1,N)=B(kn+1,N)+C(kn+1,N)

D(kn+1,N)=A(kn+1,N)+T(kn+1,N)9.5向量處理機(jī)

每組用兩條向量指令，發(fā)生數(shù)據(jù)相關(guān)兩次，其中組內(nèi)發(fā)生數(shù)據(jù)相關(guān)一次，組間切換時(shí)發(fā)生數(shù)據(jù)相關(guān)一次。

縱橫處理方式的優(yōu)點(diǎn)是減少了訪問主存儲器的次數(shù)，中間變量T不用寫入主存儲器?？v橫處理方式用于寄存器－寄存器結(jié)構(gòu)的向量處理機(jī)中。9.5向量處理機(jī)9.5.2向量流水處理機(jī)1.向量處理機(jī)的指令系統(tǒng)

在普通計(jì)算機(jī)中，機(jī)器指令的基本操作對象是標(biāo)量，而向量處理機(jī)除了有標(biāo)量處理功能外還具有功能齊全的向量運(yùn)算指令系統(tǒng)。2.向量流水處理機(jī)的結(jié)構(gòu)舉例

向量流水處理機(jī)的結(jié)構(gòu)因具體機(jī)器不同而不同。有兩種典型的結(jié)構(gòu)：存儲器－存儲器型結(jié)構(gòu)和寄存器－寄存器型結(jié)構(gòu)。縱向處理方式宜采用前者，而分組處理方式則宜采用后者。9.5向量處理機(jī)9.5.3并行向量處理機(jī)

為了更有效地提高向量處理性能，新型向量機(jī)采用了多處理機(jī)體系結(jié)構(gòu)，用時(shí)間并行+空間并行技術(shù)實(shí)現(xiàn)向量處理的高速化。

并行向量處理機(jī)（PVP）一般由若干臺高性能向量處理機(jī)（VP）構(gòu)成。這些向量處理機(jī)是專門設(shè)計(jì)和定制的，擁有很高的向量處理性能。PVP中經(jīng)常采用專門設(shè)計(jì)的高帶寬的交叉開關(guān)網(wǎng)絡(luò)，把各VP與共享存儲器模塊（SM）連接起來。這樣的機(jī)器通常不使用Cache，而是使用大量的向量寄存器和指令緩沖器。并行向量處理機(jī)屬于MIMD結(jié)構(gòu)。第9章并行系統(tǒng)結(jié)構(gòu)9.1并行處理系統(tǒng)概述9.2指令級高度并行的處理機(jī)9.3超長指令字處理機(jī)9.4超線程和多核處理器9.5向量處理機(jī)9.6并行處理機(jī)9.7多處理機(jī)與多計(jì)算機(jī)9.6并行處理機(jī)

并行處理機(jī)也稱為陣列處理機(jī)，它由多個(gè)重復(fù)設(shè)置的相同處理單元（PE）構(gòu)成，這些PE按照一定方式互連成陣列，在同一個(gè)控制部件（CU）的控制下，對各自所分配的不同數(shù)據(jù)完成同一條指令規(guī)定的操作。9.6.1并行處理機(jī)原理1.并行處理機(jī)的特點(diǎn)

并行處理機(jī)從CU看，指令是串行執(zhí)行的，從PE看，數(shù)據(jù)是并行處理的，所以按照Flynn分類法，它屬于操作級并行的SIMD計(jì)算機(jī)。9.6并行處理機(jī)①

速度快，而且潛力大。②

模塊性好，生產(chǎn)和維護(hù)方便。③

可靠性高，容易實(shí)現(xiàn)容錯(cuò)和重構(gòu)。④

效率低（與流水線處理機(jī)、向量處理機(jī)等比較）。通常作為專用計(jì)算機(jī)，因此，在很大程度上依賴于并行算法。

并行處理機(jī)依靠的是資源重復(fù)，而不是時(shí)間重疊，它的每個(gè)處理單元要擔(dān)負(fù)多種處理功能，其效率要低一些。另一方面，它依靠增加PE個(gè)數(shù)，與流水線處理機(jī)主要依靠縮短時(shí)鐘周期相比，其提高速度的潛力要大得多。9.6并行處理機(jī)9.6.2陣列處理機(jī)的結(jié)構(gòu)1．分布式存儲器的陣列處理機(jī)結(jié)構(gòu)

在采用分布式存儲器結(jié)構(gòu)的陣列處理機(jī)中，每個(gè)PEi都有自己的局部存儲器PEMi。PEMi中存放著本PEi直接訪問的數(shù)據(jù)?？刂撇考–U）內(nèi)的主存儲器（CUM）用來存放系統(tǒng)程序、用戶程序和標(biāo)量數(shù)據(jù)。在執(zhí)行用戶程序時(shí)，所有指令都在控制部件中進(jìn)行譯碼，把只適合串行處理的標(biāo)量或控制指令留給控制部件自己執(zhí)行，把只適合并行處理的向量類指令“播送”給各個(gè)PE，控制處于“活躍”的那些PE并行執(zhí)行。在運(yùn)算過程中，PE間可通過互連網(wǎng)絡(luò)（ICN）來交換數(shù)據(jù)?；ミB網(wǎng)絡(luò)的連通路徑選擇也由控制部件統(tǒng)一控制。管理處理機(jī)（SC）用于管理系統(tǒng)資源，運(yùn)行操作系統(tǒng)。分布式存儲器結(jié)構(gòu)是SIMD陣列機(jī)的主流。9.6并行處理機(jī)9.6并行處理機(jī)2．集中式共享存儲器的陣列處理機(jī)結(jié)構(gòu)

采用集中設(shè)置存儲器方案，存儲體的個(gè)數(shù)大于處理單元的個(gè)數(shù)。在采用集中式共享主存結(jié)構(gòu)的陣列處理機(jī)中，K個(gè)存儲分體的數(shù)據(jù)經(jīng)互連網(wǎng)絡(luò)（ICN）為全部N個(gè)處理單元所共享，要求K≥N。此時(shí)，ICN的作用是在處理單元與存儲器分體之間進(jìn)行轉(zhuǎn)接構(gòu)成數(shù)據(jù)通路，希望各PE能高效靈活地動態(tài)與不同的存儲體相連，使盡可能多的PE能無沖突地訪問共享的主存模塊。9.6并行處理機(jī)9.6并行處理機(jī)9.6.3ILLIACⅣ機(jī)的互連結(jié)構(gòu)

超級計(jì)算機(jī)ILLIACⅣ是第一臺全面使用大規(guī)模集成電路作為邏輯元件和存儲器的計(jì)算機(jī)，它是一臺使用分布式存儲器結(jié)構(gòu)的陣列處理機(jī)。ILLIACⅣ有64個(gè)處理部件PUi（每個(gè)PU都包含處理單元PE、局部存儲器PEM和存儲器邏輯部件MLU），排列成8×8的方陣。9.6并行處理機(jī)9.6并行處理機(jī)

任何一個(gè)處理部件PUi只能直接與其上、下、左、右4個(gè)近鄰PUi-8（mod64）、PUi+8（mod64）、PUi-1（mod64）和PUi=1（mod64）直接相連。循此規(guī)則，同一列的上下兩端的PU連成環(huán)，左右每一行右端的PU與下一行左端的PU相連，最下面一行的右端的PU與最上面一行左端的PU相連，從而形成一個(gè)閉合的螺旋線陣列。處理部件所用的互連模式用到了PM2I互連函數(shù)中的4個(gè)函數(shù)，即PM2±0和PM2±3。

在這種陣列中，步距不等于±1或±8的任意處理單元之間，經(jīng)過軟件尋找，最多不超過7步傳送即可完成數(shù)據(jù)的傳送。9.6并行處理機(jī)

例如：從PU0到PU36的距離：采用普通網(wǎng)格必須8步：

PU0

PU1

PU2

PU3

PU4

PU12

PU20

PU28

PU36

或PU0

PU8

PU16

PU24

PU32

PU33

PU34

PU35

PU36

或……（等于8步的很多，大于8步的更多）。如果采用閉合螺旋線，只需要7步：

PU0

PU63

PU62

PU61

PU60

PU52

PU44

PU36

或PU0

PU63

PU55

PU47

PU39

PU38

PU37

PU36

或……9.6并行處理機(jī)9.6并行處理機(jī)9.6.4陣列處理機(jī)的并行算法1．矩陣加

在陣列處理機(jī)上，解決矩陣加法是最簡單的一維情形。若有兩個(gè)8×8的矩陣A、B相加，所得結(jié)果矩陣C也是一個(gè)8×8的矩陣。只需把A、B居于相應(yīng)位置的分量存放在同一個(gè)PEM內(nèi)，且在全部64個(gè)PEM中，令A(yù)的分量均為同一地址α，B的分量單元均為同一地址α+1，而結(jié)果矩陣C的各個(gè)結(jié)果分量也相應(yīng)存放于各PEM同一地址α+2的單元內(nèi)。這樣，只需用下列3條ILLIACⅣ的匯編指令就可以一次實(shí)現(xiàn)矩陣相加：9.6并行處理機(jī)LDA ALPHA

；全部(α)由PEMi送PEi的累加器RGAi

ADRN ALPHA+1；全部(α+1)與(RGAi)進(jìn)行浮點(diǎn)規(guī)格加法，結(jié)果送RGAi

STA ALPHA+2；全部(RGAi)由PEi送PEMi的α+2單元，這里，0≤i≤63

從這個(gè)例子可以看出單指令流（3條指令順序執(zhí)行）多數(shù)據(jù)流（64個(gè)元素并行相加）以及數(shù)組并行的“全并行”的工作特點(diǎn)。由于是64個(gè)處理單元在并行操作，速度提高為順序處理的64倍。9.6并行處理機(jī)9.6并行處理機(jī)2.矩陣乘

由于矩陣乘是二維數(shù)組運(yùn)算，故它比循環(huán)加要復(fù)雜一些。設(shè)A、B和C為3個(gè)8×8的二維矩陣。若給定A和B，則為計(jì)算C=A*B的64個(gè)分量，可用下列公式其中，0≤i≤7且0≤j≤7。9.6并行處理機(jī)

需要經(jīng)過I、J和K三重循環(huán)完成。每重循環(huán)執(zhí)行8次，總共需要512次乘、加的時(shí)間，此外每次還應(yīng)包括執(zhí)行循環(huán)控制、判別等其他操作需花費(fèi)的時(shí)間。如果在SIMD陣列處理機(jī)上運(yùn)算，則可用8個(gè)處理單元并行計(jì)算矩陣C(I,J)的某一行或某一列，即將J循環(huán)或I循環(huán)轉(zhuǎn)化成一維的向量處理，從而消去了一重循環(huán)。9.6并行處理機(jī)

3．累加和

這是一個(gè)將N個(gè)數(shù)的順序相加過程轉(zhuǎn)變?yōu)椴⑿邢嗉舆^程的問題。為了得到各項(xiàng)累加的部分和及最后的總和，要用到處理單元中的活躍標(biāo)志位。只有處于活躍狀態(tài)的處理單元，才能執(zhí)行相應(yīng)的操作。9.6并行處理機(jī)9.6.5互連網(wǎng)絡(luò)基本概念

為了在輸入結(jié)點(diǎn)與輸出結(jié)點(diǎn)之間建立對應(yīng)關(guān)系，互連網(wǎng)絡(luò)有三種表示方法：(1)互連函數(shù)表示法：

如：f(xn-1…x1x0)=x0xn-2…x1xn-1

自變量和函數(shù)可以用二進(jìn)制表示，也可以用十進(jìn)制等表示。(2)圖形表示法9.6并行處理機(jī)（3）輸入輸出對應(yīng)表示法

互連網(wǎng)絡(luò)輸入輸出對應(yīng)表示法把互連函數(shù)表示為：輸入： 0 1 …N-1輸出：f(0) f(1)…

f(N-1)

這種方法表示對應(yīng)的輸入和輸出相連。例如，N=8交換置換關(guān)系的這種表示形式為：輸入:01234567輸出:103254769.6并行處理機(jī)9.6.6基本的單級互連網(wǎng)絡(luò)

1．立方體單級網(wǎng)絡(luò)

三維立方體結(jié)構(gòu)的每一個(gè)頂點(diǎn)（網(wǎng)絡(luò)的結(jié)點(diǎn)）代表一個(gè)處理單元，共有8個(gè)處理單元，用直角坐標(biāo)系上zyx三位二進(jìn)制碼編號。它所能實(shí)現(xiàn)的入、出端連接如同立方體各頂點(diǎn)間能實(shí)現(xiàn)的互連一樣，即每個(gè)處理單元只能直接連到其二進(jìn)制編號的某一位取反的其他3個(gè)處理單元上。如010只能連到000、011、110，不能直接連到對角線上的001、100、101、111。所以，三維立方體單級網(wǎng)絡(luò)有3種互連函數(shù)：Cube0、Cube1、Cube2。Cubei函數(shù)表示相連的入端和出端的二進(jìn)制編號只在右起第i位（i=0，1，2）上0、1互反，其余各位代碼都相同。9.6并行處理機(jī)9.6并行處理機(jī) Cube0中，只有頂點(diǎn)的二進(jìn)制編碼的最右一邊位不同的頂點(diǎn)之間可直接相連，如001與000，100與101，111與110相連。任意兩個(gè)結(jié)點(diǎn)之間最大距離為3，如000與111之間通過000→001→011→111可達(dá)，其距離為3。同時(shí)，任意兩個(gè)結(jié)點(diǎn)之間有3條路徑，000與111之間除前述路徑外，還有000→100→101→111和000→010→110→111兩條路徑可達(dá)。9.6并行處理機(jī)

推廣到n維的情形，N個(gè)節(jié)點(diǎn)的立方體單級網(wǎng)絡(luò)共有n=log2N種互連函數(shù)，即

式中，0≤i≤n-1，Pi為入端號二進(jìn)制碼的第i位。當(dāng)維數(shù)n＞3時(shí)，稱為超立方體(HyperCube)網(wǎng)絡(luò)。9.6并行處理機(jī)2．PM2I單級互連網(wǎng)絡(luò)

PM2I單級互連網(wǎng)絡(luò)是“加減2i”單級互連網(wǎng)絡(luò)的簡稱，能實(shí)現(xiàn)與j號處理單元直接相連的是編號為j±2i的處理單元，即： PM2+i(j)=j+2imodN PM2-i(j)=j-2imodN其中，0≤i≤n-1，0≤j≤N-1，n=log2N。

因此，它共有2n個(gè)互連函數(shù)。由于總存在PM2+(n-1)=PM2-(n-1)，所以實(shí)際上，PM2I互連網(wǎng)絡(luò)只有2n-1種不同的互連函數(shù)。PM2-(n-1)=PM2+(n-1)的推導(dǎo)如下： j-2n-1=(j+2n-2n-1)modN=j+2n-19.6并行處理機(jī)

對于N=8的PM2I互連網(wǎng)絡(luò)的互連函數(shù)有PM2+0、PM2-0、PM2+1、PM2-1、PM2±2等5個(gè)不同的互連函數(shù)，它們分別為：PM2+0=j+20(mod8)： (01234567)PM2-0=j-20(mod8)： (76543210)PM2+1=j+21(mod8)： (0246)(1357)PM2-1=j-21(mod8)： (6420)(7531)PM2±2=j±22(mod8)： (04)(15)(26)(37)其中，(01234567)表示0連到1，1連到2，2連到3，…，7連到0；(0246)表示0連到2，2連到4，…。9.6并行處理機(jī)9.6并行處理機(jī)3．混洗交換單級互連網(wǎng)絡(luò)

這種互連網(wǎng)絡(luò)由全混洗和交換兩個(gè)互連函數(shù)組成，先混洗后交換。n維全混洗互連函數(shù)表示為：Shuffle(Pn-1Pn-2…P1P0)=Pn-2Pn-3…P0Pn-1式中，n=log2N，Pn-1Pn-2…P1P0為入端編號的二進(jìn)制碼。新的最高位被移到最低位，相當(dāng)于將處理單元的二進(jìn)制編號中的最高位循環(huán)左移到最低位。9.6并行處理機(jī)9.6并行處理機(jī)

由于全混洗互連網(wǎng)絡(luò)不能實(shí)現(xiàn)編號為全“0”和全“1”的處理單元與其他單元的連接，所以還需引入Cube0交換函數(shù)。這就是全混交換單級網(wǎng)絡(luò)，N=8的全混洗交換互連網(wǎng)絡(luò)連接如圖，圖中實(shí)線表示交換，虛線表示全混洗。第9章并行系統(tǒng)結(jié)構(gòu)9.1并行處理系統(tǒng)概述9.2指令級高度并行的處理機(jī)9.3超長指令字處理機(jī)9.4超線程和多核處理器9.5向量處理機(jī)9.6并行處理機(jī)9.7多處理機(jī)與多計(jì)算機(jī)9.7多處理機(jī)與多計(jì)算機(jī)

多處理機(jī)系統(tǒng)與多計(jì)算機(jī)系統(tǒng)是有差別的。多處理機(jī)系統(tǒng)是由多臺處理機(jī)組成的計(jì)算機(jī)系統(tǒng)，它們受邏輯上統(tǒng)一的操作系統(tǒng)控制；而多計(jì)算機(jī)系統(tǒng)則是由多臺獨(dú)立的計(jì)算機(jī)組成的系統(tǒng)，各計(jì)算機(jī)分別在邏輯上獨(dú)立的操作系統(tǒng)控制下運(yùn)行。9.7多處理機(jī)與多計(jì)算機(jī)9.7.1多處理機(jī)和多計(jì)算機(jī)的耦合度

多處理機(jī)系統(tǒng)和多計(jì)算機(jī)系統(tǒng)可以統(tǒng)稱為多機(jī)系統(tǒng)。多處理機(jī)系統(tǒng)中的各處理機(jī)都可有自己的控制部件，可帶自己的局部存儲器，能執(zhí)行各自的程序，它們都受邏輯上統(tǒng)一的操作系統(tǒng)控制，處理機(jī)間以文件、單一數(shù)據(jù)或向量、數(shù)組等形式交互作用，全面實(shí)現(xiàn)作業(yè)、任務(wù)、指令、數(shù)據(jù)各級的并行。多計(jì)算機(jī)系統(tǒng)中的各計(jì)算機(jī)分別在邏輯上獨(dú)立的操作系統(tǒng)控制下運(yùn)行，機(jī)間可以互不通信，即使通信也只是經(jīng)通道或通信線路以文件或數(shù)據(jù)集形式進(jìn)行，實(shí)現(xiàn)多個(gè)作業(yè)間的并行。9.7多處理機(jī)與多計(jì)算機(jī)

根據(jù)物理連接的緊密程度和交叉作用能力的強(qiáng)弱，可將多機(jī)分為緊耦合系統(tǒng)和松耦合系統(tǒng)兩種不同的類型。（1）緊耦合系統(tǒng)

緊耦合系統(tǒng)也稱為直接耦合系統(tǒng)。在這種系統(tǒng)中，各處理機(jī)通過公共硬件資源（例如共享存儲器和I/O系統(tǒng)）實(shí)現(xiàn)機(jī)間通信和同步，這些處理機(jī)在同一操作系統(tǒng)控制下協(xié)同求解大而復(fù)雜的計(jì)算。緊耦合多處理機(jī)中的處理機(jī)共享全局地址空間，共享存儲器，處理機(jī)之間需要嚴(yán)格同步。為了減少訪問主存沖突，主存采用模m多體交叉存取。同時(shí)，處理機(jī)可自帶小容量局部存儲器或再加上自帶Cache存儲器。通常將緊耦合處理機(jī)稱為多處理機(jī)。9.7多處理機(jī)與多計(jì)算機(jī)（2）松耦合系統(tǒng)

松耦合系統(tǒng)也稱為間接耦合系統(tǒng)。多個(gè)處理機(jī)之間通過通道、通信線路或通信網(wǎng)絡(luò)、消息傳遞系統(tǒng)實(shí)現(xiàn)處理機(jī)之間的通信和同步。各處理機(jī)都有一個(gè)容量較大的局部存儲器，用于存放其常用的指令和數(shù)據(jù)，擁有各自的輸入輸出設(shè)備，并分別受各自獨(dú)立操作系統(tǒng)管理，本身就構(gòu)成了一臺完整的計(jì)算機(jī)。松耦合系統(tǒng)中的處理機(jī)沒有全局地址空間，無共享存儲器，處理機(jī)之間的通信不需要同步。通常將松耦合處理機(jī)稱為多計(jì)算機(jī)。9.7多處理機(jī)與多計(jì)算機(jī)1.多處理機(jī)分類（1）同構(gòu)型多處理機(jī)

基于資源重復(fù)，由大量同類型或是功能相同的處理機(jī)組成。把一道程序分解為若干個(gè)相互獨(dú)立的程序段或稱任務(wù)，分別指定給各個(gè)處理機(jī)并行的加以執(zhí)行。同時(shí)提高容錯(cuò)能力，進(jìn)而提高可靠性。（2）異構(gòu)型多處理機(jī)

基于時(shí)間重疊，由負(fù)責(zé)不同功能的多個(gè)專用處理機(jī)組成。將任務(wù)分解成能夠串行執(zhí)行的子任務(wù)，分給各個(gè)處理機(jī)按順序完成。不同任務(wù)在時(shí)間上重疊執(zhí)行。

（3）分布式多處理機(jī)

基于資源共享，多個(gè)處理機(jī)協(xié)作完成任務(wù)的處理。各處理機(jī)之間通過通信網(wǎng)絡(luò)相互通信，由統(tǒng)一的操作系統(tǒng)對各個(gè)分布的軟、硬資源進(jìn)行統(tǒng)一管理。9.7多處理機(jī)與多計(jì)算機(jī)2.多處理機(jī)的特點(diǎn)與并行處理機(jī)（SIMD）相比，多處理機(jī)（MIMD）具有以下特點(diǎn)：（1）結(jié)構(gòu)靈活性

多個(gè)處理機(jī)由多個(gè)指令部件分別控制，通過公共硬件或互連網(wǎng)絡(luò)實(shí)現(xiàn)處理器之間的通信。多處理機(jī)在結(jié)構(gòu)上具有更大靈活性和更強(qiáng)的通用性。（2）程序并行性

多處理機(jī)并行性主要體現(xiàn)在指令外部，即表現(xiàn)在多個(gè)任務(wù)之間，必須綜合研究算法、程序語言、編譯、操作系統(tǒng)、指令、硬件等，從多種途徑挖掘各種可能存在的并行性，因此程序并行性的識別較難。并行處理機(jī)并行性僅存在于指令內(nèi)部，其并行性識別較易。9.7多處理機(jī)與多計(jì)算機(jī)（3）并行任務(wù)派生

多處理機(jī)采用多指令流操作模式，一個(gè)程序中就可能存在著多個(gè)并發(fā)的程序段，因此需要由專用指令或語句顯式指明各程序段的并發(fā)關(guān)系，控制它們并發(fā)執(zhí)行，使一個(gè)任務(wù)執(zhí)行時(shí)可派生出另一些任務(wù)與它并行執(zhí)行。并行處理機(jī)由指令反映數(shù)據(jù)間能否并行計(jì)算，并啟動多個(gè)處理單元并行工作。（4）進(jìn)程同步

多處理機(jī)實(shí)現(xiàn)的是作業(yè)、任務(wù)、指令、數(shù)據(jù)等各個(gè)級別的并行，同一時(shí)刻，不同處理機(jī)執(zhí)行著不同的指令，進(jìn)程之間的數(shù)據(jù)相關(guān)和控制依賴決定了要采取一定的進(jìn)程同步策略。各進(jìn)程的同步需要采取特殊措施來保證。并行處理機(jī)實(shí)現(xiàn)指令內(nèi)數(shù)據(jù)操作的并行，受同一控制器控制，工作自然是同步的。9.7多處理機(jī)與多計(jì)算機(jī)（5）資源分配和調(diào)度

多處理機(jī)執(zhí)行并發(fā)任務(wù)所需要的處理機(jī)的數(shù)目是不固定的，所需資源的品質(zhì)和數(shù)量變化復(fù)雜，因此必須解決好動態(tài)資源分配和任務(wù)調(diào)度問題，以獲得更好性能和更高效率。并行處理機(jī)只需用屏蔽手段來控制實(shí)際參加并行操作的處理單元數(shù)目。9.7多處理機(jī)與多計(jì)算機(jī)9.7.3多處理機(jī)結(jié)構(gòu)1.共享存儲器結(jié)構(gòu)

各處理機(jī)通過互連網(wǎng)絡(luò)共享存儲器和I/O設(shè)備，并通過共享存儲器相互聯(lián)系。任何一個(gè)處理機(jī)對存儲單元的任何修改對其他處理機(jī)都是可見的。為了減少訪存沖突，存儲器由多個(gè)并行的存儲體組成。9.7多處理機(jī)與多計(jì)算機(jī)共享存儲器結(jié)構(gòu)的多處理機(jī)系統(tǒng)具有以下特點(diǎn)：①

各處理機(jī)共享存儲空間，并通過對共享存儲器的讀/寫實(shí)現(xiàn)相互通信。②

對存儲單元的任何修改對其他處理機(jī)都是可見的。③

存儲器訪問延遲低，但擴(kuò)展性差。

根據(jù)訪存時(shí)間是否相同，共享存儲器結(jié)構(gòu)又細(xì)分為兩種結(jié)構(gòu)：均衡存儲器訪問（UMA）結(jié)構(gòu)和非均衡存儲器訪問（NUMA）結(jié)構(gòu)。

均衡存儲器訪問（UMA）結(jié)構(gòu)也被稱為集中式共享存儲器結(jié)構(gòu)。非均衡存儲器訪問（NUMA）結(jié)構(gòu)也被稱為分布式共享存儲器結(jié)構(gòu)。9.7多處理機(jī)與多計(jì)算機(jī)2.分布式存儲器結(jié)構(gòu)

分布式存儲器結(jié)構(gòu)也被稱為非遠(yuǎn)程存儲訪問（NORMA）模型。各處理機(jī)擁有自己的本地存儲器，在本地操作系統(tǒng)控制下獨(dú)立工作。各處理機(jī)的本地存儲器是私有的，不能被其他處理機(jī)訪問。各處理機(jī)借助互連網(wǎng)絡(luò)、通過消息傳遞機(jī)制相互通信，實(shí)現(xiàn)數(shù)據(jù)共享。大規(guī)模并行處理機(jī)（MPP）、機(jī)群等采用了這種結(jié)構(gòu)。9.7多處理機(jī)與多計(jì)算機(jī)9.7多處理機(jī)與多計(jì)算機(jī)分布式存儲器結(jié)構(gòu)的多處理機(jī)具有以下特點(diǎn)：①

各處理機(jī)擁有自己的本地存儲器，可以獨(dú)立工作，訪問本地存儲器速度快。②

各處理機(jī)的本地存儲器不能被其他處理機(jī)訪問。③

各處理機(jī)借助互連網(wǎng)絡(luò)、通過消息傳遞機(jī)制相互通信。④

結(jié)構(gòu)靈活，擴(kuò)展性較好。⑤

任務(wù)傳輸以及任務(wù)分配算法復(fù)雜，通常要設(shè)計(jì)專有算法。⑥

處理機(jī)之間的訪問延遲較大。⑦

需要高帶寬的互連。9.7多處理機(jī)與多計(jì)算機(jī)9.7.4多處理機(jī)的Cache一致性1.多Cache一致性問題的產(chǎn)生

Cache是提高系統(tǒng)性能的一種常用手段，多處理機(jī)也廣泛應(yīng)用Cache。在多處理機(jī)中，各處理機(jī)上對本地Cache中共享數(shù)據(jù)的修改（寫入）會引起不同處理機(jī)上Cache內(nèi)容互不相同，以及Cache內(nèi)容與共享存儲器中內(nèi)容互不相同，從而產(chǎn)生Cache一致性問題。

在共享存儲器結(jié)構(gòu)的多處理機(jī)中，導(dǎo)致多處理機(jī)多Cache不一致問題的原因有3個(gè)：共享可寫數(shù)據(jù)、I/O傳輸和進(jìn)程遷移。其中進(jìn)程遷移是指把一個(gè)尚未執(zhí)行完的進(jìn)程調(diào)度到另一個(gè)空閑的處理機(jī)中去執(zhí)行，使系統(tǒng)負(fù)載平衡。對于I/O傳輸和進(jìn)程遷移而導(dǎo)致的Cache不一致可以分別通過禁止I/O通道與處理機(jī)共享Cache以及禁止進(jìn)程遷移來解決。9.7多處理機(jī)與多計(jì)算機(jī)2.多Cache一致性問題解決方法

所有Cache一致性問題解決方法的目標(biāo)都是讓最近使用的本地變量進(jìn)入到適當(dāng)?shù)腃ache，并允許讀寫，與此同時(shí)，使用某種方法維護(hù)在多個(gè)Cache中的共享變量的一致性。解決Cache一致性的方法分為兩類：硬件方法和軟件方法。9.7多處理機(jī)與多計(jì)算機(jī)9.7.5多處理機(jī)的機(jī)間互連形式1．總線

總線形式對機(jī)數(shù)少的多處理機(jī)來說具有結(jié)構(gòu)簡單，成本低，可擴(kuò)充性好的優(yōu)點(diǎn)，但總線的性能和可靠性嚴(yán)重受物理因素制約?？偩€形式需要使用相應(yīng)的總線控制機(jī)構(gòu)和總線仲裁算法來解決總線的訪問沖突。2．環(huán)形

環(huán)形互連形式采用點(diǎn)點(diǎn)連接，允許持有令牌的處理機(jī)向環(huán)上發(fā)送信息，信息經(jīng)環(huán)形網(wǎng)絡(luò)不斷地向下一臺處理機(jī)傳遞。環(huán)形互連的控制簡單，非常適合于高帶寬的光纖通信，但環(huán)中的信息傳輸延遲較大。9.7多處理機(jī)與多計(jì)算機(jī)3．交叉開關(guān)

交叉開關(guān)形式用縱橫開關(guān)陣列將橫向的處理機(jī)P及I/O通道與縱向的存儲器模塊M連接起來。4．多級交叉開關(guān)

為了克服單級大規(guī)模交叉開關(guān)硬件量太大，成本過高的缺點(diǎn)，可通過用多個(gè)較小規(guī)模的交叉開關(guān)“串聯(lián)”和“并聯(lián)”，構(gòu)成多級交叉開關(guān)網(wǎng)絡(luò)，以取代單級的大規(guī)模交叉開關(guān)。5．多端口存儲器

多端口存儲器形式是將分布于交叉開關(guān)陣列中的控制、轉(zhuǎn)移和優(yōu)先級仲