第六章
1、試分析陣列處理機特點
（1）陣列處理機提高速度是利用資源重復，利用并行性中的同時性；
（2）處理單元同等地擔負起各種運算，其設(shè)備利用率可能不那么高；
（3）速度提高在硬件價格大幅度下降情況下，潛力巨大；
（4）互連網(wǎng)絡對系統(tǒng)性能影響顯著；
（5）互連網(wǎng)絡使陣列處理機比固定結(jié)構(gòu)的單功能流水線靈活；
（6）陣列處理機結(jié)構(gòu)和所采用并行算法緊密聯(lián)系；
（7）陣列處理機還必須提高標量處理速度。
總之，陣列處理機實質(zhì)上是專門對付數(shù)組運算的處理單元陣列組成的處理機、專門從事處理單元陣列控制及標量處理的處理機和專門從事輸入輸出及操作系統(tǒng)管理的處理機組成的一個異構(gòu)型多處理機系統(tǒng)。
2、試比較陣列機的兩種基本形式
（1）分布式存儲器陣列機。a、各處理單元PE有局部存儲器，被分布數(shù)據(jù)只能被本處理單元直接訪問。b、在控制部件CU內(nèi)有主存儲器。運行時所有指令都在CU中，只把適合并行處理的“向量類”指令播給各PE，并控制各PE并行執(zhí)行。c、各PE可通過互連網(wǎng)ICN交換數(shù)據(jù)。d、PE通過CU連到管理處理機SC上，用于管理系統(tǒng)資源。
（2）集中式共享存儲器陣列機。a、K個存儲體集中組成，經(jīng)互連網(wǎng)絡為全部N個處理單元共享。其中K等于數(shù)據(jù)處理單元數(shù)。b、互連網(wǎng)用于處理單元與存儲分體之間進行轉(zhuǎn)接構(gòu)成數(shù)據(jù)通路。
3、試比較多級互連的幾種網(wǎng)絡
ATRAN——拓撲結(jié)構(gòu)：第I級交換單元處于交換方式時，實現(xiàn)Cubei；控制方式：級控制分級控制；交換單元：二功能交換單元。
間接二進制N方體——拓撲結(jié)構(gòu)：第I級交換單元處于交換方式時，實現(xiàn)Cubei；控制方式：單元控制；交換單元：二功能交換單元。
多級混洗omega——拓撲結(jié)構(gòu)：每一級有一個全混拓撲和一列四功能交換單元；控制方式：單元控制；交換單元：四功能交換單元。
多級PM2I——拓撲結(jié)構(gòu)：每級按PM2I連接；控制方式：級控制或單元控制；交換單元：二功能交換單元。
全排列Benes——拓撲結(jié)構(gòu)：三維立方體多級網(wǎng)絡與它的逆網(wǎng)絡連在一起，省去中間重復一級；控制方式：單元控制；交換單元：二功能交換單元。
4、試說明間接二進制n方體網(wǎng)絡是阻塞式網(wǎng)絡
N個端要實現(xiàn)任意排列，應有N！種。
而單元控制的N=lnN/ln2級間接二進制方體網(wǎng)絡中，每級有N/2個開關(guān)，N級互連網(wǎng)交換開關(guān)總數(shù)為（NlnN/ln2）/2.
要實現(xiàn)入、出端的一一映射，每個開關(guān)只能取直接或交換兩種功能。
所以開關(guān)狀態(tài)總共有2^[（NlnN/ln2）/2]，即N^（N/2）種。
當N>2時，N^（N/2）
所以它無法表示所有N！排列，所以當多個入出端同時連接時可能發(fā)生沖突，即間接二進制N方體網(wǎng)絡是阻塞式網(wǎng)絡。
5、試比較互連網(wǎng)動態(tài)拓撲結(jié)構(gòu)的兩種形式
動態(tài)單極網(wǎng)絡指網(wǎng)絡只有有限幾個連接，必須經(jīng)循環(huán)多次通過，才能實現(xiàn)任意兩個處理單元之間的信息傳送。節(jié)省設(shè)備，但通過時間長，對網(wǎng)絡控制要求高。
動態(tài)多極網(wǎng)絡指由多個動態(tài)單極網(wǎng)絡串聯(lián)組成的網(wǎng)絡。通過時間短，靈活性好，可利用不同單極互連網(wǎng)絡組合成有不同特征和連接模式的多級互連網(wǎng)絡。缺點是：增加設(shè)備和成本。
6、試比較單級互連的幾種函數(shù)
Cube
相連的2個處理單元其二進制編號只有一位不同。Cubei，其第i位取反。有l(wèi)ogN（以2為底，下同）種函數(shù)，任意兩點距離是logN，最多使用logN次函數(shù)可實現(xiàn)任意入出端連接，可逆。
PM2I
J號處理單元直接連接的結(jié)點是J±2^i（0≤i≤logN-1）。PM2±i（j）=j±2^i（0≤i≤logN-1，0≤j≤N-1.有2logN-1種函數(shù)，任意兩點距離是N/2，最多使用2次函數(shù)可實現(xiàn)任意端連接，可逆。
混洗
每個結(jié)點連到另一個二進制結(jié)點最低位是其位的結(jié)點。Shuffer（Pn-1……P1P0）=Pn-2……P1P0Pn-1.有2種函數(shù)，任意兩點距離是2logN-1，最多使用2logN-1次函數(shù)可實現(xiàn)任意入出端的連接，不可逆。
7、單指令流多數(shù)據(jù)流的并行處理機在系統(tǒng)組成上應包含哪些部分和功能？
重復設(shè)置大量的處理單元用規(guī)整靈活的互連函數(shù)互連，組成處理單元陣列；
用專門的并行算法對數(shù)組、向量中的元素進行并行處理；
用一臺高性能處理機來進行標量處理和控制互連網(wǎng)絡的連接；
用一臺管理處理機來運行系統(tǒng)程序和輸入輸出任務。
8、什么是全排列網(wǎng)絡？實現(xiàn)全排列網(wǎng)絡有哪兩種方法？
可實現(xiàn)N個入端的所有N！種排列的網(wǎng)絡稱全排列網(wǎng)絡，即N個端所有一到一的傳送都不會發(fā)生傳送路徑使用沖突的互連網(wǎng)絡。
實現(xiàn)全排列網(wǎng)絡的出方法有：
在多級互連網(wǎng)絡的輸出端設(shè)置鎖存器，使輸出端的數(shù)據(jù)再多級互連網(wǎng)絡；
將兩個多級互連網(wǎng)絡，即一個正網(wǎng)絡和一個逆網(wǎng)絡串接起來，合并掉中間的一級，組成2logN-1級的多級網(wǎng)絡。
1、試分析陣列處理機特點
（1）陣列處理機提高速度是利用資源重復，利用并行性中的同時性；
（2）處理單元同等地擔負起各種運算，其設(shè)備利用率可能不那么高；
（3）速度提高在硬件價格大幅度下降情況下，潛力巨大；
（4）互連網(wǎng)絡對系統(tǒng)性能影響顯著；
（5）互連網(wǎng)絡使陣列處理機比固定結(jié)構(gòu)的單功能流水線靈活；
（6）陣列處理機結(jié)構(gòu)和所采用并行算法緊密聯(lián)系；
（7）陣列處理機還必須提高標量處理速度。
總之，陣列處理機實質(zhì)上是專門對付數(shù)組運算的處理單元陣列組成的處理機、專門從事處理單元陣列控制及標量處理的處理機和專門從事輸入輸出及操作系統(tǒng)管理的處理機組成的一個異構(gòu)型多處理機系統(tǒng)。
2、試比較陣列機的兩種基本形式
（1）分布式存儲器陣列機。a、各處理單元PE有局部存儲器，被分布數(shù)據(jù)只能被本處理單元直接訪問。b、在控制部件CU內(nèi)有主存儲器。運行時所有指令都在CU中，只把適合并行處理的“向量類”指令播給各PE，并控制各PE并行執(zhí)行。c、各PE可通過互連網(wǎng)ICN交換數(shù)據(jù)。d、PE通過CU連到管理處理機SC上，用于管理系統(tǒng)資源。
（2）集中式共享存儲器陣列機。a、K個存儲體集中組成，經(jīng)互連網(wǎng)絡為全部N個處理單元共享。其中K等于數(shù)據(jù)處理單元數(shù)。b、互連網(wǎng)用于處理單元與存儲分體之間進行轉(zhuǎn)接構(gòu)成數(shù)據(jù)通路。
3、試比較多級互連的幾種網(wǎng)絡
ATRAN——拓撲結(jié)構(gòu)：第I級交換單元處于交換方式時，實現(xiàn)Cubei；控制方式：級控制分級控制；交換單元：二功能交換單元。
間接二進制N方體——拓撲結(jié)構(gòu)：第I級交換單元處于交換方式時，實現(xiàn)Cubei；控制方式：單元控制；交換單元：二功能交換單元。
多級混洗omega——拓撲結(jié)構(gòu)：每一級有一個全混拓撲和一列四功能交換單元；控制方式：單元控制；交換單元：四功能交換單元。
多級PM2I——拓撲結(jié)構(gòu)：每級按PM2I連接；控制方式：級控制或單元控制；交換單元：二功能交換單元。
全排列Benes——拓撲結(jié)構(gòu)：三維立方體多級網(wǎng)絡與它的逆網(wǎng)絡連在一起，省去中間重復一級；控制方式：單元控制；交換單元：二功能交換單元。
4、試說明間接二進制n方體網(wǎng)絡是阻塞式網(wǎng)絡
N個端要實現(xiàn)任意排列，應有N！種。
而單元控制的N=lnN/ln2級間接二進制方體網(wǎng)絡中，每級有N/2個開關(guān)，N級互連網(wǎng)交換開關(guān)總數(shù)為（NlnN/ln2）/2.
要實現(xiàn)入、出端的一一映射，每個開關(guān)只能取直接或交換兩種功能。
所以開關(guān)狀態(tài)總共有2^[（NlnN/ln2）/2]，即N^（N/2）種。
當N>2時，N^（N/2）
所以它無法表示所有N！排列，所以當多個入出端同時連接時可能發(fā)生沖突，即間接二進制N方體網(wǎng)絡是阻塞式網(wǎng)絡。
5、試比較互連網(wǎng)動態(tài)拓撲結(jié)構(gòu)的兩種形式
動態(tài)單極網(wǎng)絡指網(wǎng)絡只有有限幾個連接，必須經(jīng)循環(huán)多次通過，才能實現(xiàn)任意兩個處理單元之間的信息傳送。節(jié)省設(shè)備，但通過時間長，對網(wǎng)絡控制要求高。
動態(tài)多極網(wǎng)絡指由多個動態(tài)單極網(wǎng)絡串聯(lián)組成的網(wǎng)絡。通過時間短，靈活性好，可利用不同單極互連網(wǎng)絡組合成有不同特征和連接模式的多級互連網(wǎng)絡。缺點是：增加設(shè)備和成本。
6、試比較單級互連的幾種函數(shù)
Cube
相連的2個處理單元其二進制編號只有一位不同。Cubei，其第i位取反。有l(wèi)ogN（以2為底，下同）種函數(shù)，任意兩點距離是logN，最多使用logN次函數(shù)可實現(xiàn)任意入出端連接，可逆。
PM2I
J號處理單元直接連接的結(jié)點是J±2^i（0≤i≤logN-1）。PM2±i（j）=j±2^i（0≤i≤logN-1，0≤j≤N-1.有2logN-1種函數(shù)，任意兩點距離是N/2，最多使用2次函數(shù)可實現(xiàn)任意端連接，可逆。
混洗
每個結(jié)點連到另一個二進制結(jié)點最低位是其位的結(jié)點。Shuffer（Pn-1……P1P0）=Pn-2……P1P0Pn-1.有2種函數(shù)，任意兩點距離是2logN-1，最多使用2logN-1次函數(shù)可實現(xiàn)任意入出端的連接，不可逆。
7、單指令流多數(shù)據(jù)流的并行處理機在系統(tǒng)組成上應包含哪些部分和功能？
重復設(shè)置大量的處理單元用規(guī)整靈活的互連函數(shù)互連，組成處理單元陣列；
用專門的并行算法對數(shù)組、向量中的元素進行并行處理；
用一臺高性能處理機來進行標量處理和控制互連網(wǎng)絡的連接；
用一臺管理處理機來運行系統(tǒng)程序和輸入輸出任務。
8、什么是全排列網(wǎng)絡？實現(xiàn)全排列網(wǎng)絡有哪兩種方法？
可實現(xiàn)N個入端的所有N！種排列的網(wǎng)絡稱全排列網(wǎng)絡，即N個端所有一到一的傳送都不會發(fā)生傳送路徑使用沖突的互連網(wǎng)絡。
實現(xiàn)全排列網(wǎng)絡的出方法有：
在多級互連網(wǎng)絡的輸出端設(shè)置鎖存器，使輸出端的數(shù)據(jù)再多級互連網(wǎng)絡；
將兩個多級互連網(wǎng)絡，即一個正網(wǎng)絡和一個逆網(wǎng)絡串接起來，合并掉中間的一級，組成2logN-1級的多級網(wǎng)絡。