【正文】 第 8章 多處理機(jī)? 內(nèi)容提要: 本章首先介紹多處理機(jī)的基本結(jié)構(gòu)與類(lèi)型，包括緊耦合多處理機(jī)、松耦合多處理機(jī)及多處理機(jī)中的 Cache一致性問(wèn)題。然后，講述并行多處理機(jī)中的關(guān)鍵技術(shù)，比如程序并行性分析、并行程序設(shè)計(jì)語(yǔ)言的基本概念、多處理機(jī)操作系統(tǒng)的基本特征及多處理機(jī)調(diào)度策略等。最后以具體示例闡述并行多處理機(jī)的發(fā)展趨勢(shì)。重點(diǎn)是緊耦合 /松耦合多處理機(jī)的組成及與 Cache的一致性、并行程序設(shè)計(jì)語(yǔ)言的基本概念、多處理機(jī)操作系統(tǒng)的基本特征以及多處理機(jī)調(diào)度策略等。難點(diǎn)是多處理機(jī)中的 Cache一致性和多處理機(jī)調(diào)度策略。第 8章 多處理機(jī) 多處理機(jī)的基本結(jié)構(gòu)與類(lèi)型 并行多處理機(jī)技術(shù) 并行多處理機(jī)的發(fā)展趨勢(shì) 多處理機(jī)的基本結(jié)構(gòu)與類(lèi)型 緊耦合多處理機(jī) 松耦合多處理機(jī) 多處理機(jī)中的 Cache一致性 多處理機(jī)是由多臺(tái)獨(dú)立的計(jì)算機(jī)組成，若按照 Flynn分類(lèi)法，這種結(jié)構(gòu)稱(chēng)為多指令流多數(shù)據(jù)流，即 MIMD型結(jié)構(gòu)。按照處理機(jī)的組成與連接方式，多處理機(jī)可分為兩種類(lèi)型，即緊耦合（ Tightly coupled） 多處理機(jī)和松耦合（ Loosely coupled） 多處理機(jī)。 緊耦合多處理機(jī) 緊耦合（ Tightly coupled） 多處理機(jī)是指各處理機(jī)通過(guò)系統(tǒng)中的共享主存實(shí)現(xiàn)相互之間的數(shù)據(jù)傳送及通信。各處理機(jī)有自己的局部存儲(chǔ)器，又共享共用存儲(chǔ)器。 其結(jié)構(gòu)如圖 ，由 p個(gè) 處理機(jī)、 m個(gè)存儲(chǔ)器模塊和 d個(gè)I/O通道組成。每個(gè)處理機(jī) Pi有一個(gè)容量不大的本地存儲(chǔ)器 LMi， 配置高速 Cache CMi。 各處理機(jī)通過(guò)互 連網(wǎng)絡(luò) PPIN實(shí)現(xiàn)互連，又通過(guò)互連網(wǎng)絡(luò) PMIN與共享存儲(chǔ)器連接，通 過(guò)互連網(wǎng)絡(luò) PIOIN與外部I/O通道連接。圖 緊耦合多處理機(jī)典型結(jié)構(gòu) 由于通過(guò)共享存儲(chǔ)器實(shí)現(xiàn)數(shù)據(jù)傳送和通信，因此速度快，效率高。但是處理機(jī)的臺(tái)數(shù)往往受到限制，主要有兩方面的因素。一是通過(guò)共享存儲(chǔ)器通信，故當(dāng)處理機(jī)的數(shù)量增大時(shí)，訪存沖突增多；二是處理機(jī)與主存之間的互連網(wǎng)絡(luò)的帶寬有限，當(dāng)處理機(jī)的數(shù)量增大時(shí)可能成為瓶頸。為此，常采用以下措施： ① 采用多模塊交叉存儲(chǔ)器結(jié)構(gòu)，以減少訪存沖突。 ② 每臺(tái)處理機(jī)有一個(gè)小容量的局部存儲(chǔ)器，存放核心代碼，減少對(duì)共享存儲(chǔ)器的訪問(wèn)。 ③ 每臺(tái)處理機(jī)配置一個(gè)高速 Cache， 以減少對(duì)主存的訪問(wèn)。 在構(gòu)成多處理機(jī)時(shí)，各處理機(jī)的內(nèi)部結(jié)構(gòu)可以相同，也可以不同；結(jié)構(gòu)形式可采取對(duì)稱(chēng)型，也可采取非對(duì)稱(chēng)型。下面主要介紹同構(gòu)對(duì)稱(chēng)型和異構(gòu)非對(duì)稱(chēng)型的結(jié)構(gòu)。 1. 同構(gòu)對(duì)稱(chēng)型多處理機(jī) 同構(gòu)對(duì)稱(chēng)型多處理機(jī)是指系統(tǒng)中各處理機(jī)的結(jié)構(gòu)及總線連接方式相同。 （ 1） Balance同構(gòu)對(duì)稱(chēng)型多處理機(jī) 如圖 ，處理機(jī)由 2～ 32個(gè) CPU組成，存儲(chǔ)器由 1～ 6個(gè)存儲(chǔ)體組成。每個(gè)處理機(jī)模塊由 1個(gè) 80386CPU、 浮點(diǎn)運(yùn)算器 Weitek1167及64KB的 Cache組成；每個(gè)存儲(chǔ)器模塊 MEM包含 8MB存儲(chǔ)體及一個(gè)存儲(chǔ)控制器，其容量可擴(kuò)展到 40MB。 處理機(jī)模塊、存儲(chǔ)器模塊直接與系統(tǒng)總線連接。系統(tǒng)總線通過(guò)磁盤(pán)控制器與外部磁盤(pán)陣列連接，通過(guò) SCSI總線與其它外部設(shè)備連接，另外還可通過(guò)總線適配器與局域網(wǎng)（ Ether） 或遠(yuǎn)程網(wǎng)（ ） 連接。圖 Balance同構(gòu)對(duì)稱(chēng)型多處理機(jī) （ 2）曙光一號(hào)同構(gòu)對(duì)稱(chēng)型多處理機(jī) 如圖 ，由 4個(gè) CPU和 4個(gè)存儲(chǔ)體組成。每個(gè)處理機(jī)由 1個(gè)MC88100和兩個(gè)包含 Cache的存儲(chǔ)控制器 MC88200組成，主存容量為64MB， 可擴(kuò)展到 768MB。 通過(guò)高速局部總線將 4個(gè) CPU和存儲(chǔ)器模塊連接起來(lái)，通過(guò)總線適配器和 I/O接口與遠(yuǎn)程網(wǎng)（ ）、 局域網(wǎng)（Ether） 以及 SCSI接口連接。圖 曙光一號(hào)同構(gòu)對(duì)稱(chēng)型多處理機(jī) 2. 異構(gòu)非對(duì)稱(chēng)型多處理機(jī) 是指系統(tǒng)中各處理機(jī)的結(jié)構(gòu)及與總線的連接方式可以不同，存儲(chǔ)器模塊的結(jié)構(gòu)也可以不同，其示意如圖 。除了主 CPU和主存之外，還有多個(gè)專(zhuān)用處理機(jī)。字符處理機(jī) CIOP與外部字符設(shè)備連接，數(shù)據(jù)處理機(jī) BIOP與外部數(shù)組設(shè)備連接，網(wǎng)絡(luò)處理機(jī) NIOP用于外部聯(lián)網(wǎng)，圖形處理機(jī) GIOP連接外部圖形設(shè)備， ACOP是向量處理機(jī)。圖 異構(gòu)非對(duì)稱(chēng)型多處理機(jī)示意圖 松耦合多處理機(jī) 松耦合（ Loosely coupled） 多處理機(jī)是由一些功能較強(qiáng)、相對(duì)獨(dú)立的計(jì)算機(jī)模塊組成；每個(gè)模塊至少包括一個(gè)功能較強(qiáng)的 CPU、 局部存儲(chǔ)器和I/O設(shè)備；相互之間以消息的方式進(jìn)行通信。如圖 ，每個(gè)計(jì)算機(jī)模塊有一個(gè)容量較大的局部存儲(chǔ)器，因此大 部分程序和數(shù)據(jù)處理是在本地進(jìn)行。當(dāng)不同模塊上運(yùn)行的進(jìn)程需要通信時(shí)，經(jīng)網(wǎng)絡(luò)通信接口 NI（ Network interface） 和消息傳送系統(tǒng) MTS（ Message transfer system），圖 松耦合多處理機(jī)示意圖 以消息的方式進(jìn)行。其中有的模塊本身就是一臺(tái)功能很強(qiáng)的結(jié)點(diǎn)計(jì)算機(jī)。 松耦合多處理機(jī)的連接方式基本上分為兩種類(lèi)型，即非層次結(jié)構(gòu)和層次結(jié)構(gòu)。 （ 1）非層次結(jié)構(gòu)的松耦合多處理機(jī) 圖 。各個(gè)結(jié)點(diǎn)機(jī)均通過(guò)網(wǎng)絡(luò)接口 NI與共用消息傳送系統(tǒng) MTS連接，從形式上來(lái)看，僅有一層。其中網(wǎng)絡(luò)接口 NI主要由數(shù)據(jù)通道和仲裁開(kāi)關(guān)組成，一方面控制數(shù)據(jù)傳送，另一方面負(fù)責(zé)多個(gè)計(jì)算機(jī)模塊同時(shí)請(qǐng)求訪問(wèn)消息傳送系統(tǒng)時(shí)的仲裁工作。 （ 2）層次結(jié)構(gòu)的松耦合多處理機(jī) 圖 ，是由 50個(gè) LSI—11小型機(jī)構(gòu)成的 C*m多處理機(jī)，采用多層總線結(jié)構(gòu)實(shí)現(xiàn)多層次連接。其中 Cm是基本計(jì)算機(jī)模塊，內(nèi)部采用 LSI—11總線，通過(guò)開(kāi)關(guān) S經(jīng)總線 MAP與其它 Cm連接。每條 MAP總線最多可連接14個(gè)計(jì)算機(jī)模塊 Cm， 構(gòu)成一個(gè)計(jì)算機(jī)模塊群。 KMAP與外部總線連接器，采用雙總線，以提高系統(tǒng)的可靠性。圖 C*m層次結(jié)構(gòu)多處理機(jī) 圖 C*m是一個(gè)三層總線的多處理機(jī)，其中模塊內(nèi)部訪存時(shí)間為 ， 模塊群間為 ， 群組間為 26μs。 其最大優(yōu)點(diǎn)是可擴(kuò)展性好，但級(jí)數(shù)太多時(shí)的性能價(jià)格比下降。 在松耦合多處理機(jī)中，各計(jì)算機(jī)模塊一般配有 Cache， 存在Cache一致性問(wèn)題。 在多處理機(jī)中，各處理機(jī)之間的互連方式比 SIMD計(jì)算機(jī)高一些，主要有總線方式、縱橫交叉開(kāi)關(guān)互連方式、多端口存儲(chǔ)器互連方式、多級(jí)互連網(wǎng)絡(luò)方式以及蟲(chóng)孔（ Wormhole） 尋徑方式等。 多處理機(jī)中的 Cache一致性 多處理機(jī)中各處理機(jī)都可能有一個(gè)局部 Cache， 這既要考慮各 Cache與共享主存的一致性，還要考慮各 Cache之間的一致性。下面首先說(shuō)明產(chǎn)生Cache不一致的途徑，然后介紹保持 Cache一致性的幾種措施。 1. 引起 Cache不一致的幾種途徑多個(gè)處理機(jī)用 Pi表示，各自 Cache用 Ci表示，引起 Cache不一致的主要途徑： （ 1） Cache改寫(xiě)不同步引起不一致性 當(dāng)某一 Pi執(zhí)行 Cache寫(xiě)操作，且用全寫(xiě)法改變了共享主存中的相應(yīng)區(qū)域，這時(shí)若其它 Cache不能隨之一起改變，將引起不一致性。 （ 2）進(jìn)程遷移引起 Cache不一致性 當(dāng)某 Pi在執(zhí)行某進(jìn)程時(shí)對(duì) Cache進(jìn)行了寫(xiě)操作，且采用替換時(shí)寫(xiě)回；若因某種原因使該進(jìn)程轉(zhuǎn)移到處理機(jī) Pi+1上執(zhí)行時(shí)，再讀 Cache， 則讀出的是沒(méi)有改寫(xiě)的內(nèi)容，即不一致性。 （ 3） I/O傳輸引起 Cache不一致性 當(dāng)某一或多個(gè)處理機(jī)的 Cache有主存某共享區(qū)域的副本時(shí)， Pi執(zhí)行 I/O操作時(shí)將輸入數(shù)據(jù)寫(xiě)入到共享主存的這一區(qū)域中，將引起 Cache與主存共享區(qū)域的不一致性；或者 Pi改寫(xiě)了 Cache， 而采取的是替換時(shí)寫(xiě)回策略，這時(shí)另一 Pi+1執(zhí)行輸出共享存儲(chǔ)器區(qū)域的操作，輸出的則是原來(lái)的內(nèi)容。 2. 保持 Cache一致性的三種措施 目前，解決多處理機(jī)中 Cache一致性的措施有多種，一是采用軟件的辦法，二是監(jiān)聽(tīng)一致性協(xié)議法，另一種是目錄表法 （ 1）軟件辦法 主要是借助于編譯程序進(jìn)行分析，使共享信息只存放在共享主存中，而不進(jìn)入多處理機(jī)的局部 Cache中。這樣，進(jìn)入 Cache中的信息不為其它處理機(jī)所共享。但是影響了 Cache的效率。 （ 2）監(jiān)聽(tīng)（ Snoopy） 一致性協(xié)議法 是在處理機(jī) Cache上設(shè)置一個(gè)部件，監(jiān)聽(tīng)總線操作。當(dāng)監(jiān)聽(tīng)到某 Pi有 Cache操作或使主存共享區(qū)域改變時(shí)，按約定協(xié)議處理。常用協(xié)議有兩種： ① 寫(xiě)無(wú)效協(xié)議：當(dāng)某一 Pi改寫(xiě)其 Cache中的數(shù)據(jù)后，使其它處理機(jī)中Cache的相應(yīng)副本無(wú)效。 ② 寫(xiě)更新協(xié)議：當(dāng)某一 Pi改寫(xiě)其 Cache中的數(shù)據(jù)后，將改寫(xiě)結(jié)果廣播到其余處理機(jī)的 Cache中，做相應(yīng)的拷貝。 （ 3）目錄表法 也稱(chēng)為目錄表協(xié)議，是在某處理機(jī) Pi修改 Cache和共享主存后，僅把修改信息發(fā)送到與該 Cache有相同副本的處理機(jī)，故此需要一個(gè)目錄表，記錄所有 Cache塊和共享數(shù)據(jù)塊的位置與狀態(tài)，其內(nèi)容主要是一些指針，表明塊拷貝的地址和是否進(jìn)行了寫(xiě)入的狀態(tài)。根據(jù)目錄表的構(gòu)成方式，可分為集中式和分布式兩種。集中式常用于集中共享主存的小型多處理機(jī)的 Cache一致性控制。分布式是將目錄分布到各個(gè)處理機(jī)上，每個(gè)存儲(chǔ)模塊有一個(gè)單獨(dú)的目錄存放所有 Cache的狀態(tài)信息。 并行多處理機(jī)技術(shù) 程序并行性分析 并行程序設(shè)計(jì)語(yǔ)言 多處理機(jī)操作系統(tǒng). 多處理機(jī)調(diào)度策略 程序并行性分析 多處理機(jī)的并行性主要表現(xiàn)在程序級(jí)或任務(wù)級(jí)。因此，能否把順序程序轉(zhuǎn)換成語(yǔ)義等價(jià)且可并行運(yùn)行的程序，是程序并行性分析的主要任務(wù)。這里，主要涉及程序中的數(shù)據(jù)相關(guān)和并行檢測(cè)技術(shù)。 1. 程序中數(shù)據(jù)相關(guān)性分析 雖然在多處理機(jī)上并行運(yùn)行的程序段是異步執(zhí)行的，但是由于它們是由某一順序程序轉(zhuǎn)換而來(lái)的，因此在程序段之間也可能存在象標(biāo)量流水線中所說(shuō)的相關(guān)性。這里，主要是數(shù)據(jù)相關(guān)。下面僅以賦值語(yǔ)句表示程序段 P， 來(lái)說(shuō)明三種常見(jiàn)的數(shù)據(jù)相關(guān)。 （ 1）數(shù)據(jù)相關(guān) 設(shè)程序段 P1和 P2如下： P1： A=B+C P2： D=A*C 由于程序段 P1中賦值號(hào)左邊的變量 A出現(xiàn)在 P2中賦值號(hào)右邊的變量集中，因此程序段 P2必須在 P1中求出 A的值以后才能執(zhí)行。于是稱(chēng)程序段 P2中的數(shù)據(jù)相關(guān)于 P1。 （ 2） 數(shù)據(jù)反相關(guān) 設(shè)程序段 P1和 P2如下： P1： A=B*C P2： C=D+E 由于程序段 P2中賦值號(hào)左邊的變量 C出現(xiàn)在 P1中賦值號(hào)右邊的變量集中，因此程序段 P1必須讀出變量 C的值以后 P2才能執(zhí)行。于是稱(chēng)程序段 P1中的數(shù)據(jù)反相關(guān)于 P2。 （ 3）數(shù)據(jù)輸出相關(guān) 設(shè)程序段 P1和 P2如下： P1： A=B+C P2： A=D*E 由于程序段 P1和 P2中賦值號(hào)左邊是同一變量 A， 且兩個(gè)程序段有先后之分，為了保證語(yǔ)義的正確性，必須保證程序段 P1先寫(xiě)入 A， 然后 P2才能寫(xiě)入。于是稱(chēng)程序段 P2的數(shù)據(jù)輸出相關(guān)于 P1。 2. 程序并行檢查 并行性檢查主要是檢查程序中是否有前述相關(guān)，常用方法有伯恩施坦（ Bernstein） 準(zhǔn)則。 在程序執(zhí)行過(guò)程中，常需使用輸入和輸出兩個(gè)變量集。若用 Ii表示程序段 Pi所要讀取主存的單元（變量）集， Qi表示所要寫(xiě)入主存的單元（變量）集，則程序段 P1和 P2能夠并行執(zhí)行的伯恩施坦準(zhǔn)則為： ① I1∩Q2=216。， 程序段 P1的輸入變量集與 P2的輸出變量集不相交。 ② I2∩Q1=216。， 程序段 P2的輸入變量集與 P1的輸出變量集不相交。 ③ Q1∩Q2=216。， 程序段 P1的輸出變量集與 P2的輸出變量集