第七章
1、簡述緊耦合和松耦合的多機系統(tǒng)結(jié)構(gòu)
各處理機之間通過互連網(wǎng)絡(luò)共享主存的緊耦合多處理機。緊耦合系統(tǒng)由P臺處理機，m個存儲器模塊，d個I/O通道和3個互連網(wǎng)絡(luò)構(gòu)成。處理機-存儲器網(wǎng)絡(luò)實現(xiàn)處理機與各存儲模塊的連接。處理機中斷信號網(wǎng)絡(luò)實現(xiàn)多處理機之間的互連。處理機-I/O互連網(wǎng)絡(luò)實現(xiàn)處理機與外設(shè)的連接。每個處理機可自帶局部存儲器，也可自帶Cache.存儲器模塊可采用流水工作方式。緊耦合系統(tǒng)多用于并行作業(yè)中的多任務(wù)，一般處理機是同構(gòu)的。
各處理機間通過共享I/O子系統(tǒng)、通道或通信線路實現(xiàn)機間通信，不共享主存的是松耦合系統(tǒng)。松散耦合多處理機由P個處理機，一個通道，一個仲裁開關(guān)和消息傳送系統(tǒng)。每個處理機帶有一個局部存儲器和一組I/O設(shè)備。在仲裁開關(guān)的通道中有高速通信存儲，用來緩沖傳送的信息塊。松散耦合多處理機較適合粗粒度的并行計算。
2、簡述對樹形結(jié)構(gòu)進行變換的過程
首先利用交換律把相同的運算集中在一起。然后利用結(jié)合律把參加這些運算的操作數(shù)配對，盡可能并行運算，從而組成樹高最小的子樹。最后再把這些子樹結(jié)合起來，用分配律進一步降低樹高。
3、試比較3種類型的多處理機操作系統(tǒng)
主從型：管理程序只在一臺處理機上運行。硬件結(jié)構(gòu)簡單，控制簡單，但對主機可靠性要求高，靈活性差。為目前大多數(shù)多處理機操作系統(tǒng)采用，工作負荷固定，從處理機能力明顯低于主處理機，或由功能差別大的多個處理機組成的異構(gòu)型系統(tǒng)。
各自獨立型：控制分散到多臺處理機，共同完成對整個系統(tǒng)的控制工作。適合分布計算模式，對主機依賴性差，可靠性高；但實現(xiàn)復(fù)雜，共享表格訪問沖突，處理機負荷平衡較困難。適用于松耦合處理機系統(tǒng)。
浮動型：管理程序在處理機間浮動。靈活性高，但發(fā)生訪問表格沖突，設(shè)計較困難。適合緊耦合多處理機系統(tǒng)，特別是共享主存和I/O子系統(tǒng)的同構(gòu)多處理機系統(tǒng)。
4、比較多處理機系統(tǒng)中數(shù)據(jù)相關(guān)的處理方式
并行 順序串行 交換串行
“先讀后寫” 可以（有條件） 可以 不可以
“寫-寫” 可以（有條件） 可以 不可以
“先寫后讀” 不允許 可以 特殊情況可以
“先讀后寫”和“先寫后讀” 必須 不允許 不允許
無任何相關(guān) 可以 可以 可以
5、多處理機系統(tǒng)與并行處理機的主要差別是什么？多處理機系統(tǒng)主要解決的技術(shù)問題是什么？
有差別的原因是并行性等級不同，多處理機系統(tǒng)是任務(wù)級并行，并行處理機是操作級并行。具體講：
1）結(jié)構(gòu)靈活性不同。
2）程序并行性等級不同。軟硬件支持不同。
3）并行任務(wù)派生的方式不同。并行處理機能否并行工作由指令決定；多處理機必須有專門指令指明程序段能否并行執(zhí)行，派生的任務(wù)數(shù)是動態(tài)變化的。
4）進程同步。并行處理機工作同步是自然的，而多處理機必須采取同步措施。
5）資源分配和任務(wù)調(diào)度，多處理機比并行處理機任務(wù)調(diào)度復(fù)雜。
多處理機必須解決的技術(shù)問題：
1）硬件結(jié)構(gòu)上多處理機、主存、I/O子系統(tǒng)之間應(yīng)有高帶寬、低價格、靈活無規(guī)則的互連，盡可能不發(fā)生信息傳送的路徑?jīng)_突。
2）從并行語言、并行算法、編譯等上，限度地開發(fā)出程序的并行性，實現(xiàn)多處理機各級的全面并行。
3）大的任務(wù)如何細分成多個子任務(wù)、任務(wù)的粒度選擇。
4）從操作系統(tǒng)上解決好多處理機間、并行任務(wù)的分配、調(diào)度和資源分配；任務(wù)或進程間的同步死鎖和競爭等問題的解決。
5）系統(tǒng)的重組及良好的編程環(huán)境。
6、簡述JOIN語句和FORK語句的基本功能。
FORK m的功能：
1）準備好新進程啟動和執(zhí)行的必須信息。
2）將空閑處理機分配給派生的新進程，若沒有，則排隊等待。
3）繼續(xù)在原處理機上執(zhí)行FORK m語句的原進程。
JOIN n的功能：
1）JOIN語句將計數(shù)器初始化為0；
2）執(zhí)行一次JOIN語句，計數(shù)器+1，并與n比較。
3）若相等，則允許進程通過JOIN語句，計數(shù)器清0，進程繼續(xù)執(zhí)行。
4）若不相等，則執(zhí)行JOIN語句的進程結(jié)束，釋放處理機。
7、試比較機間互連的幾種形式。
總線形式：處理機與外部存儲器模塊通過總線相連。結(jié)構(gòu)簡單、成本低、擴展性好；但總線失效敏感，存在總線爭用。適合處理機較少、系統(tǒng)信息流量少、機數(shù)可擴充情況。
環(huán)形互連：各處理機點點相加成環(huán)。結(jié)構(gòu)簡單、成本低、不爭用總線；但信息傳輸有延遲。適合處理機較少、使用高寬帶的光纖通信、系統(tǒng)流量高、機數(shù)可擴充的情況。
交叉開關(guān)：用縱橫開關(guān)陣列將存儲器模塊、I/O通道相連。不爭用開關(guān)；但開關(guān)陣列復(fù)雜，設(shè)備量較大。適合處理機數(shù)較多（但不超過16）、系統(tǒng)流量大、處理機數(shù)可擴充的情況。
多端口存儲器：將交叉開關(guān)移到存儲器接口中。不爭用總線，但存儲器接口復(fù)雜，較難控制。適合處理機數(shù)少、不能擴充（一般是2臺），系統(tǒng)流量高的情況。
開關(guān)樞紐結(jié)構(gòu)：把交叉開關(guān)設(shè)置在各處理機或接口內(nèi)部。所有開關(guān)樞紐數(shù)量少，可用較短路徑與處理機連接；但開關(guān)樞紐較復(fù)雜。適合處理機數(shù)多、可擴充、分布結(jié)構(gòu)情況。
8、多處理機在結(jié)構(gòu)與并行性方面與陣列處理機有什么不同？
結(jié)構(gòu)方面：陣列處理機的互連較規(guī)整，有一定專用性，互連的處理單元數(shù)量大；多處理機要采用更靈活多變的結(jié)構(gòu)，實現(xiàn)復(fù)雜的互連模式，互連的處理機數(shù)量少。
并行性方面：陣列處理機是操作級并行，是并行性的同時性；多處理機是作業(yè)、程序、任務(wù)級的并行，同時包含指令內(nèi)部操作間的并行，是并行性的并發(fā)性。
9、多處理機中的并行性表現(xiàn)在哪些方面？開發(fā)多處理機的并行性有哪些途徑？
多處理機主要實現(xiàn)作業(yè)之間、程序段之間、任務(wù)之間的并行，也可包含有指令級、指令內(nèi)部各微操作之間的并行。
多處理機的并行性可利用并行算法、并行程序設(shè)計語言、并行編譯、并行操作系統(tǒng)以及指令硬件等多種途徑來開發(fā)和實現(xiàn)。
1、簡述緊耦合和松耦合的多機系統(tǒng)結(jié)構(gòu)
各處理機之間通過互連網(wǎng)絡(luò)共享主存的緊耦合多處理機。緊耦合系統(tǒng)由P臺處理機，m個存儲器模塊，d個I/O通道和3個互連網(wǎng)絡(luò)構(gòu)成。處理機-存儲器網(wǎng)絡(luò)實現(xiàn)處理機與各存儲模塊的連接。處理機中斷信號網(wǎng)絡(luò)實現(xiàn)多處理機之間的互連。處理機-I/O互連網(wǎng)絡(luò)實現(xiàn)處理機與外設(shè)的連接。每個處理機可自帶局部存儲器，也可自帶Cache.存儲器模塊可采用流水工作方式。緊耦合系統(tǒng)多用于并行作業(yè)中的多任務(wù)，一般處理機是同構(gòu)的。
各處理機間通過共享I/O子系統(tǒng)、通道或通信線路實現(xiàn)機間通信，不共享主存的是松耦合系統(tǒng)。松散耦合多處理機由P個處理機，一個通道，一個仲裁開關(guān)和消息傳送系統(tǒng)。每個處理機帶有一個局部存儲器和一組I/O設(shè)備。在仲裁開關(guān)的通道中有高速通信存儲，用來緩沖傳送的信息塊。松散耦合多處理機較適合粗粒度的并行計算。
2、簡述對樹形結(jié)構(gòu)進行變換的過程
首先利用交換律把相同的運算集中在一起。然后利用結(jié)合律把參加這些運算的操作數(shù)配對，盡可能并行運算，從而組成樹高最小的子樹。最后再把這些子樹結(jié)合起來，用分配律進一步降低樹高。
3、試比較3種類型的多處理機操作系統(tǒng)
主從型：管理程序只在一臺處理機上運行。硬件結(jié)構(gòu)簡單，控制簡單，但對主機可靠性要求高，靈活性差。為目前大多數(shù)多處理機操作系統(tǒng)采用，工作負荷固定，從處理機能力明顯低于主處理機，或由功能差別大的多個處理機組成的異構(gòu)型系統(tǒng)。
各自獨立型：控制分散到多臺處理機，共同完成對整個系統(tǒng)的控制工作。適合分布計算模式，對主機依賴性差，可靠性高；但實現(xiàn)復(fù)雜，共享表格訪問沖突，處理機負荷平衡較困難。適用于松耦合處理機系統(tǒng)。
浮動型：管理程序在處理機間浮動。靈活性高，但發(fā)生訪問表格沖突，設(shè)計較困難。適合緊耦合多處理機系統(tǒng)，特別是共享主存和I/O子系統(tǒng)的同構(gòu)多處理機系統(tǒng)。
4、比較多處理機系統(tǒng)中數(shù)據(jù)相關(guān)的處理方式
并行 順序串行 交換串行
“先讀后寫” 可以（有條件） 可以 不可以
“寫-寫” 可以（有條件） 可以 不可以
“先寫后讀” 不允許 可以 特殊情況可以
“先讀后寫”和“先寫后讀” 必須 不允許 不允許
無任何相關(guān) 可以 可以 可以
5、多處理機系統(tǒng)與并行處理機的主要差別是什么？多處理機系統(tǒng)主要解決的技術(shù)問題是什么？
有差別的原因是并行性等級不同，多處理機系統(tǒng)是任務(wù)級并行，并行處理機是操作級并行。具體講：
1）結(jié)構(gòu)靈活性不同。
2）程序并行性等級不同。軟硬件支持不同。
3）并行任務(wù)派生的方式不同。并行處理機能否并行工作由指令決定；多處理機必須有專門指令指明程序段能否并行執(zhí)行，派生的任務(wù)數(shù)是動態(tài)變化的。
4）進程同步。并行處理機工作同步是自然的，而多處理機必須采取同步措施。
5）資源分配和任務(wù)調(diào)度，多處理機比并行處理機任務(wù)調(diào)度復(fù)雜。
多處理機必須解決的技術(shù)問題：
1）硬件結(jié)構(gòu)上多處理機、主存、I/O子系統(tǒng)之間應(yīng)有高帶寬、低價格、靈活無規(guī)則的互連，盡可能不發(fā)生信息傳送的路徑?jīng)_突。
2）從并行語言、并行算法、編譯等上，限度地開發(fā)出程序的并行性，實現(xiàn)多處理機各級的全面并行。
3）大的任務(wù)如何細分成多個子任務(wù)、任務(wù)的粒度選擇。
4）從操作系統(tǒng)上解決好多處理機間、并行任務(wù)的分配、調(diào)度和資源分配；任務(wù)或進程間的同步死鎖和競爭等問題的解決。
5）系統(tǒng)的重組及良好的編程環(huán)境。
6、簡述JOIN語句和FORK語句的基本功能。
FORK m的功能：
1）準備好新進程啟動和執(zhí)行的必須信息。
2）將空閑處理機分配給派生的新進程，若沒有，則排隊等待。
3）繼續(xù)在原處理機上執(zhí)行FORK m語句的原進程。
JOIN n的功能：
1）JOIN語句將計數(shù)器初始化為0；
2）執(zhí)行一次JOIN語句，計數(shù)器+1，并與n比較。
3）若相等，則允許進程通過JOIN語句，計數(shù)器清0，進程繼續(xù)執(zhí)行。
4）若不相等，則執(zhí)行JOIN語句的進程結(jié)束，釋放處理機。
7、試比較機間互連的幾種形式。
總線形式：處理機與外部存儲器模塊通過總線相連。結(jié)構(gòu)簡單、成本低、擴展性好；但總線失效敏感，存在總線爭用。適合處理機較少、系統(tǒng)信息流量少、機數(shù)可擴充情況。
環(huán)形互連：各處理機點點相加成環(huán)。結(jié)構(gòu)簡單、成本低、不爭用總線；但信息傳輸有延遲。適合處理機較少、使用高寬帶的光纖通信、系統(tǒng)流量高、機數(shù)可擴充的情況。
交叉開關(guān)：用縱橫開關(guān)陣列將存儲器模塊、I/O通道相連。不爭用開關(guān)；但開關(guān)陣列復(fù)雜，設(shè)備量較大。適合處理機數(shù)較多（但不超過16）、系統(tǒng)流量大、處理機數(shù)可擴充的情況。
多端口存儲器：將交叉開關(guān)移到存儲器接口中。不爭用總線，但存儲器接口復(fù)雜，較難控制。適合處理機數(shù)少、不能擴充（一般是2臺），系統(tǒng)流量高的情況。
開關(guān)樞紐結(jié)構(gòu)：把交叉開關(guān)設(shè)置在各處理機或接口內(nèi)部。所有開關(guān)樞紐數(shù)量少，可用較短路徑與處理機連接；但開關(guān)樞紐較復(fù)雜。適合處理機數(shù)多、可擴充、分布結(jié)構(gòu)情況。
8、多處理機在結(jié)構(gòu)與并行性方面與陣列處理機有什么不同？
結(jié)構(gòu)方面：陣列處理機的互連較規(guī)整，有一定專用性，互連的處理單元數(shù)量大；多處理機要采用更靈活多變的結(jié)構(gòu)，實現(xiàn)復(fù)雜的互連模式，互連的處理機數(shù)量少。
并行性方面：陣列處理機是操作級并行，是并行性的同時性；多處理機是作業(yè)、程序、任務(wù)級的并行，同時包含指令內(nèi)部操作間的并行，是并行性的并發(fā)性。
9、多處理機中的并行性表現(xiàn)在哪些方面？開發(fā)多處理機的并行性有哪些途徑？
多處理機主要實現(xiàn)作業(yè)之間、程序段之間、任務(wù)之間的并行，也可包含有指令級、指令內(nèi)部各微操作之間的并行。
多處理機的并行性可利用并行算法、并行程序設(shè)計語言、并行編譯、并行操作系統(tǒng)以及指令硬件等多種途徑來開發(fā)和實現(xiàn)。