并行計算第二篇并行算法的設計(編輯修改稿)
2025-02-03 10:53 本頁面
【文章內容簡介】 – 由 Valiant(1990)提出的，“塊”同步模型，是一種異步 MIMDDM模型，支持消息傳遞系統(tǒng)，塊內異步并行，塊間顯式同步。 ? 模型參數(shù) – p：處理器數(shù) (帶有存儲器 ) – l：同步障時間 (Barrier synchronization time) – g：帶寬因子 (time steps/packet)=1/bandwidth BSP模型 ? 計算過程 由若干超級步組成， 每個超級步計算模式為左圖 ? 優(yōu)缺點 強調了計算和通訊的分離， 提供了一個編程環(huán)境，易于 程序復雜性分析。但需要顯 式同步機制，限制至多 h條 消息的傳遞等。 各 處 理 器局 部 計 算全 局 通 信路 障 同 步圖 4 . 3 logP模型 ? 基本概念 – 由 Culler(1993)年提出的，是一種分布存儲的、點到點通訊的多處理機模型，其中通訊由一組參數(shù)描述，實行隱式同步。 ? 模型參數(shù) – L： work latency – o： munication overhead – g： gap=1/bandwidth – P： processors 注： L和 g反映了通訊網(wǎng)絡的容量 logP模型 ? 優(yōu)缺點 捕捉了 MPC的通訊瓶頸，隱藏了并行機的網(wǎng)絡拓撲、路由、協(xié)議，可以應用到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進行算法描述、設計和分析。 ? BSP vs. LogP – BSP?LogP： BSP塊同步 ?BSP子集同步 ?BSP進程對同步＝LogP – BSP可以常數(shù)因子模擬 LogP， LogP可以對數(shù)因子模擬 BSP – BSP＝ LogP+Barriers－ Overhead – BSP提供了更方便的程設環(huán)境， LogP更好地利用了機器資源 – BSP似乎更簡單、方便和符合結構化編程 作業(yè)（ 1） 1. TOP500 綜述 2. 應用舉例：新聞報道等 3. 選擇某個型號的高性能計算機，撰寫調研報告 4. 顧乃杰等，基于斐波那契序列的多播算法 5. Brent定理的證明和意義 6. BSP編程方法調研 23 模型與下界 ? 不同的 PRAM模型的相互模擬 ? 下界 ? NP完全理論 ? P完全理論 不同的 PRAM模型的相互模擬 ? 不同的 PRAM模型 – PRAMEREW – PRAMCREW – PRAMCRCW ? CPRAMCRCW ? APRAMCRCW ? PPRAMCRCW ? 計算能力是相當?shù)? PRAMEREW模擬 PPRAMCRCW ? 定理 1：一條 p處理器 PPRAMCRCW模型上的指令，可在 p處理器 PRAMEREW模型上用 O(logp)的時間實現(xiàn)。 ? 證明思路： – 并發(fā)讀指令和并發(fā)寫指令 – (PPRAMCRCW) 并發(fā)讀指令 ：處理器 Qi讀取 Mi單元中的內容 – (PRAMEREW)處理器 Pi 設置數(shù)對 Mi, i ? Mi, i 按照字典序排序：時間 O(logp) ? 第一分量相同的數(shù)對組成塊（通過樹播送數(shù)據(jù)，完成數(shù)據(jù)分布） ? Pi讀取對于 Mi, i 的數(shù)據(jù)：時間 O(1) – 并發(fā)寫指令：使用三元組 地址，處理器號，待寫數(shù)據(jù) ? 推論： TEREW =O(TPCRCW logp ) PRAMCRCW之間的模擬 ? CPRAM_CRCW上算法可在 APRAM_CRCW上正確執(zhí)行 ? APRAM_CRCW上算法可在 PPRAM_CRCW上正確執(zhí)行 ? 似乎計算能力是按 CPRAM_CRCW， APRAM_CRCW，PPRAM_CRCW依次增強的。在對處理器數(shù)目或對共享存儲的容量不加限制時，三個模型是等效的。 ? 最左俘獲問題： p個處理器，“活躍”或者“非活躍”。每個活躍的處理器有標記，值為 0或 1。 當且僅當處理器是編號最小的活躍處理器，標記為 1。 CPR
環(huán)評公示相關推薦
鄂ICP備17016276號-1