【文章內(nèi)容簡介】 點和角結(jié)點的結(jié)點度分別為 3或 2。 (2) 環(huán)形網(wǎng) ? 可看做是直徑更短的另一種網(wǎng)格 ? 環(huán)形網(wǎng)沿陣列每行和每列都有環(huán)形連接 ? 一個 n n二元環(huán)網(wǎng) ? 結(jié)點度為 4 ? 直徑為 2*[n/2」 互連網(wǎng)絡(luò) 互連網(wǎng)絡(luò) 7. 超立方體 ? 一種二元 n立方體結(jié)構(gòu) ? 一般說來，一個 n立方體由 N=2n 個結(jié)點組成， 它們分布在 n維上，每維有兩個結(jié)點。 例 8個結(jié)點的 3立方體 4立方體 ? 一個 n立方體的結(jié)點度等于 n，也就是網(wǎng)絡(luò)的 直徑。 互連網(wǎng)絡(luò) 互連網(wǎng)絡(luò) 8. k元 n立方體網(wǎng)絡(luò) 環(huán)形、網(wǎng)絡(luò)形、環(huán)網(wǎng)形、二元 n立方體 (超立方 體 )等網(wǎng)絡(luò)都是 k元 n立方體網(wǎng)絡(luò)系統(tǒng)的拓?fù)渫瑯?gòu)體。 參數(shù) n: 立方體的維數(shù) k: 基數(shù)或者說是沿每個方向的結(jié)點數(shù) (多重性 )。 N=kn, (n=logkN) K元 n立方體的結(jié)點可用基數(shù)為 k的 n位地址 A=a0a1a2…an1來表示，其中 ai代表第 i維結(jié)點的位置。 按照慣例，低維 k元 n立方體稱為環(huán)網(wǎng)，而高維二 元 n立方體則稱為 超立方體。 互連網(wǎng)絡(luò) 例 一種 4元 3立方體網(wǎng)絡(luò) 互連網(wǎng)絡(luò) 動態(tài)連接網(wǎng)絡(luò) 1. 動態(tài)互連網(wǎng)絡(luò)的三個主要操作特征 ? 定時 ? 開關(guān) ? 控制 2. 根據(jù)級間連結(jié)方式，動態(tài)互連網(wǎng)絡(luò)分為 (1) 單級網(wǎng)絡(luò) 也稱循環(huán)網(wǎng)絡(luò) (2) 多級網(wǎng)絡(luò) 由一級以上的開關(guān)元件構(gòu)成。 這類網(wǎng)絡(luò)可以把任一輸入與任一輸出相連。 互連網(wǎng)絡(luò) ? 阻塞網(wǎng)絡(luò) 如果同時連接多個輸入輸出對時 ,可能會引 起開關(guān)和通信鏈路使用上的沖突。 大多數(shù)多級網(wǎng)絡(luò)都是阻塞網(wǎng)絡(luò)。 ? 非阻塞網(wǎng)絡(luò) 如果多級網(wǎng)絡(luò)通過重新安排連接方式可以 建立所有可能的輸入輸出之間的連接。 互連網(wǎng)絡(luò) ? 總線仲裁 ? 中斷處理 ? 一致性協(xié)議 ? 總線事務(wù)的處理 3. 幾類主要的開關(guān)網(wǎng)絡(luò) (1) 總線系統(tǒng) ? 優(yōu)點： 價格較低 帶寬較窄 ? 缺點： 容易產(chǎn)生故障 ? 總線研制中的重要問題 互連網(wǎng)絡(luò) ? 一種總線連接的多處理機系統(tǒng) (2) 交叉開關(guān)網(wǎng)絡(luò) 單級無阻塞置換網(wǎng)絡(luò) ? 每個交叉點是一個可以打開或關(guān)閉的開關(guān)， 提供源 (處理器 )和目的 (存儲器 )之間點對點 的連接通路。 ? 交叉點開關(guān)網(wǎng)絡(luò)中 n對處理器可以同時傳送 數(shù)據(jù)。 ? 交叉開關(guān)網(wǎng)絡(luò)的帶寬和互連特性最好。 ? 一種交叉開關(guān)網(wǎng)絡(luò) 互連網(wǎng)絡(luò) 互連網(wǎng)絡(luò) (3) 多端口存儲器 ① 主要思想 將所有交叉點仲裁邏輯和跟每個存儲器模 塊有關(guān)的開關(guān)功能移到存儲器控制器中。 ② 多端口存儲器結(jié)構(gòu)是一個折衷方案，它介于低 成本低性能的總線系統(tǒng)和高成本高帶寬的交叉 開關(guān)系統(tǒng)之間。 ③ 缺點 ? 十分昂貴 ? 不能擴(kuò)展 ? 當(dāng)系統(tǒng)配置很大時，需要大量的互連電纜和連接器 。 互連網(wǎng)絡(luò) ? 用于多處理機系統(tǒng)的 多端口存儲器結(jié)構(gòu) (4) 多級網(wǎng)絡(luò) 多級網(wǎng)絡(luò)可用于構(gòu)造大型多處理機系統(tǒng)。 ① 一種通用多級網(wǎng)絡(luò) 各種多級網(wǎng)絡(luò)的區(qū)別就在于所用開關(guān)模 塊和級間連接模式的不同。 互連網(wǎng)絡(luò) ? 由 a b開關(guān)模塊和級間構(gòu)成的通用多級互連網(wǎng)絡(luò)結(jié)構(gòu) ? 2 2開關(guān)四種可能的連接方式 ② Omega網(wǎng)絡(luò) 互連網(wǎng)絡(luò) ? 一個 16 16 Omega網(wǎng)絡(luò) 同 步 通常是使用硬件提供的有關(guān)同步指令 ， 通過用戶級軟件例程建立的 。 基本硬件原語 在多處理器同步中 ， 主要功能是一組能自動讀出后并進(jìn)行寫存儲單元的硬件原語 。 它們能夠自動讀／修改單元 。 通常情況下 ， 用戶不直接使用基本的硬件原語 ， 原語主要供系統(tǒng)程序員用來編制同步庫函數(shù) 。 第７章 多處理機 ? 功能： 將一個存儲單元的值和一個寄存器的值 進(jìn)行交換。建立一個鎖，鎖值為 “ 0”表示開鎖， 為 “ 1”表示上鎖。 ? 處理器加鎖時，將對應(yīng)于該鎖的存儲單元的值 交換為某個寄存器的值 “ 1”。如果返回值為“ 0”， 存儲單元的值此時已置換為 “ 1”，防止了別的進(jìn) 程競爭該鎖。 ? 實現(xiàn)同步的關(guān)鍵 : 操作的原子性 1. 典型操作 :原子交換（ atomic exchange） 同 步 2. 測試并置定（ test_and_set） 先測試一個值，如果符合條件則修改其值。 3. 讀取并加 1（ fetch_and_increment） 它返回存儲單元的值并自動增加該值。 4. 使用指令對 ? LL(load linked或 load locked)的取指令 ? SC(store conditional)的特殊存指令 同 步 例 實現(xiàn)對由 R1指出的存儲單元進(jìn)行原子交換操作 try： mov R3,R4 ll R2,0(R1) ； load linked sc R3,0(R1) ； store conditional beqz R3,try mov R4,R2 ；將取的值送往 R4 最終 R4和由 R1指向的單元值進(jìn)行原子交換 ， 在 ll和sc之間如有別的處理器插入并修改了存儲單元的值 ， sc將返回 “ 0”并存入 R3中 ， 從而使指令序列再重新循環(huán) 。 同 步 ? ll／ sc機制的一個 優(yōu)點 ：可用來構(gòu)造別的同步原語 例如： 原子的 fetchandincrement try： ll R2,0(R1) ； load linked addi R2,R2,＃ 1 sc R2,0(R1) ； store conditional beqz R2,try ? 指令對的實現(xiàn)必須跟蹤地址 由 ll指令指定一個寄存器，該寄存器存放著一個 單元地址，這個寄存器常稱為 連接寄存器 。 同 步 用一致性實現(xiàn)鎖 ? 采用多處理機的一致性機制來實現(xiàn)旋轉(zhuǎn)鎖。 ? 旋轉(zhuǎn)鎖 處理器環(huán)繞一個鎖不停地旋轉(zhuǎn)而請求獲得該鎖。 1. 無 Cache一致性機制 在存儲器中保存鎖變量，處理器可以不斷地通 過一個原子操作請求加鎖，比如先交換，再測試返 回值從而知道鎖的狀況。釋放鎖的時候，處理器可 簡單地將鎖置為 “ 0” 。 同 步 li R2，＃ 1 lockit： exch R2,0(R1) bnez R2， lockit ；是否已加鎖 ? 2. 機器支持 Cache一致性 將鎖緩沖進(jìn)入 Cache，并通過一致性機制使鎖值保 持一致。 同 步 ? ? 可使 “ 環(huán)繞 ” 的進(jìn)程對本地 Cache塊進(jìn)行操作； ? 可利用鎖訪問的局部性 ， 即處理器最近使用過 的鎖不久又會使用 。 ? 改進(jìn)旋轉(zhuǎn)鎖 (獲得第一條好處 ) 使其環(huán)繞過程僅對本地 Cache中鎖的拷貝進(jìn)行讀 ， 直到它返回 “ 0”確認(rèn)鎖可用 ， 然后再進(jìn)行加鎖交換操 作 。 使用鎖完畢后新競爭又開始進(jìn)行 。 同 步 lockit： lw R2， 0(R1) bnez R2， lockit li R2， ＃ 1 exch R2， 0(R1) bnez R2， lockit 。如鎖不為 0轉(zhuǎn)移 上面給出了對于三個處理器競爭鎖的操作 。 一旦處理器存入 “ 0”釋放鎖 ， 所有別的 Cache對應(yīng)塊均被作廢 ， 必須取新的值來更新它們鎖的拷貝 。 一個處理器 Cache會先獲得未加鎖值并執(zhí)行交換操作 ， 當(dāng)別的 Cache失效處理完后 ， 它們會發(fā)現(xiàn)已被加鎖 ， 所以又必須不停地測試環(huán)繞 。 同 步 表 三個處理機對鎖的使用 步驟 處理器 P0 處理器 P1 處理器 P2 鎖狀態(tài) 總線 /目錄操作 1 占有鎖 環(huán)繞測試 lock=0 環(huán)繞測試 lock=0 Shared 無 2 將鎖置為0 （ 收到作廢命令 ） (收到作廢命令 ) Exclusive P0發(fā)鎖變量作廢消息 3 Cache失效 Cache失效 Shared 總線 / 目 錄 處 理 P2 Cache失效 ,鎖從 P0寫回 4 總線 /目錄忙則等待 Lock=0 Shared P2 Cache失效處理 5 Lock=0 執(zhí)行交換 ， 導(dǎo)致 Cache失效 Shared P1Cache失效處理 6 執(zhí)行交換 ， 導(dǎo)致 Cache失效 交換完畢 ， 返回 0 置 lock=1 Exclusive 總線 / 目 錄 處 理 P2 Cache失效 ,發(fā)作廢消息 7 交換完畢 ， 返回 1 進(jìn)入關(guān)鍵處理段 Shared 總線 / 目 錄 處 理 P2 Cache失效 ， 寫回 8 環(huán)繞測試 lock=0 無 同 步 ? ll／ sc原語的另一個狀態(tài)：讀寫操作明顯分開 。 Ll不產(chǎn)生總線數(shù)據(jù)傳送 ， 這使下面代碼與使用經(jīng) 過優(yōu)化交換的代碼具有相同的特點： lockit： ll R2， 0(R1) ； loadlinked bnez R2， lockit li R2,， ＃ 1 sc R2， 0(R1) beqz R2， lockit ；如存失敗轉(zhuǎn)移 第一個分支形成環(huán)繞的循環(huán)體 ， 第二個分支解決了兩個同時請求鎖的處理器競爭問題 。 盡管旋轉(zhuǎn)鎖機制簡單并且具有強制性 ， 但難以將它擴(kuò)展到處理器數(shù)量很多的情況 。 同 步 同步性能問題 ? 簡單旋轉(zhuǎn)鎖不能很好地適應(yīng)可伸縮性 。 大規(guī)模機器 中所有的處理器會產(chǎn)生出大量的競爭問題 。 例 ： 設(shè)總線上有 10個處理器同時準(zhǔn)備對同一變量加鎖 。 假設(shè)每個總線事務(wù)處