計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第7章-多處理機(jī)-資料下載頁
2025-08-16 01:40本頁面
【正文】 ? 根據(jù)運(yùn)算的基本對象，并行算法可以分為數(shù)值并行算法和非數(shù)值并行算法 ? 根據(jù)進(jìn)程之間的依賴關(guān)系，并行算法可以分為同步并行算法、異步并行算法和分布式并行算法 （ 2） 并行算法的設(shè)計(jì)方法 PCAM設(shè)計(jì)方法 ? 任務(wù)分解（ Partition）：將整個計(jì)算問題分解成一些小的子任務(wù)，其目的是盡量創(chuàng)造并行執(zhí)行的機(jī)會。 ? 通信設(shè)計(jì)（ Communication）：確定各子任務(wù)執(zhí)行中需要交換的數(shù)據(jù)和協(xié)調(diào)子任務(wù)的執(zhí)行所需要傳遞的消息，并由此檢測上面分解方式的合理性 ? 任務(wù)組合（ Agglomeration）：按算法在實(shí)際機(jī)器上執(zhí)行的性能要求和實(shí)現(xiàn)算法的代價(jià)來考察前兩個階段的結(jié)果，將一些小的任務(wù)組合成較大的任務(wù)以減少通信開銷和提高性能。 ? 處理機(jī)映射（ Mapping）：將每個子任務(wù)分配給一個處理機(jī)去完成，目標(biāo)是最小化全局執(zhí)行時(shí)間和通信開銷，最大化處理機(jī)利用率。 （ 3）效率分析 并行算法的執(zhí)行時(shí)間通常包含兩個部分：第一部分是通信時(shí)間（ tr），即數(shù)據(jù)從一個處理機(jī)經(jīng)由互連網(wǎng)絡(luò)或共享存儲器到達(dá)另一個處理機(jī)所需的時(shí)間；第二部分是計(jì)算時(shí)間（ tc ），即數(shù)據(jù)在處理機(jī)內(nèi)進(jìn)行算術(shù)運(yùn)算，邏輯運(yùn)算等所需的時(shí)間 并行算法的可擴(kuò)展性主要是指處理機(jī)數(shù)目對算法效率和算法執(zhí)行時(shí)間的影響。 我們把處理機(jī)數(shù)目增長速度看成是問題規(guī)模增長速度的函數(shù)，并把這個函數(shù)稱為并行算法的等效率函數(shù)（ IsoEfficiency，簡單記為 IsoE(p)）。利用這個等效率函數(shù)，我們可以通過簡單的表達(dá)式來判斷并行算法的可擴(kuò)展性。 ct記問題規(guī)模為 n，處理機(jī)個數(shù)為 P(n) ，則加速為 而算法的效率可以表示為 為了保持算法的效率不變，必須使得 . 這樣，在得到 和 后，通過簡單的變換就可以獲得等效率曲線，并由此判斷算法的可擴(kuò)展性 （ 4）并行性分析 ? 數(shù)據(jù)相關(guān)性分析 ①數(shù)據(jù)相關(guān)：若程序段 P1賦值號左邊的變量出現(xiàn)在程序段 P2賦值號右邊的變量集中，稱 P2數(shù)據(jù)相關(guān)于 P1。如 : P1:A=B+C P2:D=A*E 其中，變量 A是導(dǎo)致程序段數(shù)據(jù)相關(guān)的原因，為了保證程序執(zhí)行的語義正確性，程序段 P2必須在 P1中求出 A的值才能執(zhí)行。顯然， P1和 P2不能并行執(zhí)行。 ②數(shù)據(jù)反相關(guān)：若程序段 P2賦值號左邊的變量出現(xiàn)在程序段 P1賦值號右邊的變量集中，稱 P1數(shù)據(jù)反相關(guān)于 P2。例如： P1:A=B+C P2:C=D*E 其中， P1通過變量 C是反相關(guān)于 P2，程序段 P1必須讀出變量 C后程序段 P2才能執(zhí)行。顯然， P1和 P2不能并行執(zhí)行。 ③ 數(shù)據(jù)輸出相關(guān)：若程序段 P1和 P2賦值號左邊的變量相同，則稱 P2數(shù)據(jù)輸出相關(guān)于 P1。例如： P1:A=B+C P2:A=D*E 其中，由于兩個程序段賦值號左邊有相同變量 A，且程序段有先后之分，為了保證語義的正確性，必須保證程序段 P1和先寫入 A，然后才能允許 P2寫入 A。 ? 程序并行性檢測 程序并行性檢測主要是檢測程序中是否存在上述相關(guān)，常用的方法是伯恩斯坦（ Bernstein）準(zhǔn)則。在每一個程序的執(zhí)行過程中，通常需要使用輸入和輸出兩個變量集。若用 Ii來表示程序段 Pi所要讀取主存的變量集， Qi表示所要寫入主存的變量集，那么，程序段 P1和程序 P2能夠并行執(zhí)行的伯恩斯坦準(zhǔn)則為： ① I1∩Q2＝ 248。，即程序段 P1的輸入變量集和程序段 P2的輸出變量集不相交； ② I2∩Q1＝ 248。，即程序段 P2的輸入變量集和程序段 P1的輸出變量集不相交； ③ Q1∩Q2＝ 248。，即程序段 P1的輸出變量集和程序段 P2的輸出變量集不相交。 第五節(jié) 多處理機(jī)的性能 1. 任務(wù)粒度 任務(wù)粒度是衡量軟件進(jìn)程所含計(jì)算量的尺度。最簡單的表示粒度的方法是一個（程序段）中含有的指令數(shù)目。顆粒規(guī)模一般用細(xì)、中、粗粒度來描述。 （ 2）并行機(jī)模型 ? 基本模型 ? 通信開銷線性增加的模型 ? 完全重疊通信的模型 ? 具有多條通信鏈的模型 第六節(jié) 多處理機(jī)系統(tǒng)實(shí)例 1. CRAY T3E系統(tǒng) ?雙 向 三 維 環(huán) 網(wǎng) 鏈 接處 理 單 元 ( P E )A l p h a2 1 1 6 4本 地 主 存控 制 和 E 寄 存 器路 由 器S h e l l處 理 單 元 ( P E )A l p h a2 1 1 6 4本 地 主 存控 制 和 E 寄 存 器路 由 器S h e l l? ??磁 盤 、 磁 帶 、 網(wǎng) 絡(luò) 和 其 他 I / O 設(shè) 備?千 兆 環(huán) 通 道 T3E系統(tǒng)具有 8到 2176個處理單元（ PE）。每個處理單元具有 64 MB到 2 GB的 DRAM和一個具有六個方向的、每個方向的有效帶寬為 480 MB/s的路由單元。每個處理單元間由一個三維雙向環(huán)網(wǎng)互聯(lián)以提供快速通信，并由一些千兆環(huán)通道提供 I/O設(shè)備的連接 T3E系統(tǒng)的每個處理單元中有一個 DEC Alpha21164(EV5)微處理機(jī)。其外部是一個 shell電路，包括一個本地主存、一個控制芯片和一個路由芯片。系統(tǒng)（ Shell）邏輯時(shí)鐘為 75MHz，而 Alpha21164處理器時(shí)鐘為 300MHz，其峰值速度可達(dá) 600Mflop/s。本地主存提供 64MB到 2GB的容量以及 。路由芯片有 7個雙向端口， l個連向 PE，其余 6個是連到三維環(huán)網(wǎng)的 6個鏈接上。 T3E的處理單元沒有主板級高速緩存，而是使用 21164處理器中的高速緩存。 2 . SGI Origin 2022系列服務(wù)器 R 10000 R 10000C a c h e C a c h eH u b主存儲器目錄存儲X I O路由器節(jié)點(diǎn)節(jié)點(diǎn)節(jié)點(diǎn)節(jié)點(diǎn)節(jié)點(diǎn)節(jié)點(diǎn)路由器路由器路由器路由器路由器路由器 Origin 2022系統(tǒng)采用了 CRAY Link多重交叉開關(guān)互連技術(shù)，用于連接處理機(jī)、存儲器和 I/O設(shè)備 該系統(tǒng)結(jié)構(gòu)由結(jié)點(diǎn)、 I/O子系統(tǒng)、路由器和互聯(lián)網(wǎng)絡(luò)構(gòu)成，每個結(jié)點(diǎn)可安裝一個或兩個MIPS R10000微處理器（內(nèi)含第一級高速緩存，即 L1 Cache）、第二級高速緩存（ L2 Cache）、主存儲器、目錄存儲器及 Hub等。 Hub用于連接微處理器、存儲器、 I/O和路由器等。 Origin存儲器系統(tǒng)中，每個結(jié)點(diǎn)的主存儲器容量為4GB。結(jié)點(diǎn)的 Hub內(nèi)含 4個接口和交叉開關(guān)。存儲器接口能雙向傳送數(shù)據(jù)，最大傳輸率為 780 Mbps， I/O和路由器接口各有兩個半雙工傳送端口，最大傳輸率為 2 780 Mbps，即。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1