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