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