面向計(jì)算機(jī)體系結(jié)構(gòu)的程序優(yōu)化計(jì)算機(jī)科學(xué)導(dǎo)論第七講-wenkub
2022-08-29 14:46:21 本頁(yè)面
【正文】 棧 函數(shù)調(diào)用關(guān)系樹(shù) 9 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存 1. 初學(xué)編程時(shí)的認(rèn)識(shí) 2. 學(xué)習(xí)遞歸函數(shù)時(shí)的認(rèn)識(shí) 3. 學(xué)習(xí)動(dòng)態(tài)存儲(chǔ)分配時(shí)的認(rèn)識(shí) 通過(guò) malloc等函數(shù)申請(qǐng)的空 間安排在堆上 內(nèi)存的這種劃分是通過(guò)操作 系統(tǒng)和編譯器實(shí)現(xiàn)的 ， 不是在 硬件層面上的劃分 代 碼 靜 態(tài) 數(shù) 據(jù) 堆 棧 10 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存分層 – 內(nèi)存方面的 基本局限：構(gòu)造非常快的存儲(chǔ)器或者非常大的存儲(chǔ)器 都 是可能的 ， 但是構(gòu)造不出既快又大的存儲(chǔ)器 – 內(nèi)存分層是指整個(gè)內(nèi)存由 幾層不同速度和大小的存 儲(chǔ)器組成 ， 并且最靠近處 理器的那一層最快最小 虛擬內(nèi)存 (磁盤(pán) ) 物理內(nèi)存 2級(jí)緩存 1級(jí)緩存 寄存器 (處理器 ) 11 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存分層 虛擬內(nèi)存 (磁盤(pán) ) 物理內(nèi)存 2級(jí)緩存 1級(jí)緩存 寄存器 (處理器 ) 典型大小 2千兆字節(jié) 256兆 ?2千兆字節(jié) 128千 ?4兆字節(jié) 16?64千字節(jié) 32字 典型訪問(wèn)時(shí)間 3?15微秒 100?150納秒 40?60納秒 5?10納秒 1納秒 兩邊數(shù)據(jù)可能已過(guò)時(shí) 12 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存分層 – 程序的效率不僅取決于被執(zhí)行的指令數(shù) ， 還取決于執(zhí)行每條指令需要多長(zhǎng)時(shí)間 ， 而執(zhí)行一條指令的時(shí)間區(qū)別非常可觀 – 若 一個(gè)程序的大部分 存儲(chǔ) 訪問(wèn)都落在 這種 分層的較 快層次上 ， 則 平均內(nèi)存訪 問(wèn)時(shí)間就會(huì)縮短 虛擬內(nèi)存 (磁盤(pán) ) 物理內(nèi)存 2級(jí)緩存 1級(jí)緩存 寄存器 (處理器 ) 13 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存分層 – 寄存器由編譯器生成的代碼來(lái)管理 ， 虛擬內(nèi)存由操作系統(tǒng)管理 ， 其他各層被自動(dòng)管理 。 i n。由各 處理器都執(zhí)行這段代碼來(lái)完成計(jì)算 b = ceil (n/M)。 Z[i] = Z[i] ? Z[i]。 它能把緩存未命中次數(shù)降到最低 ， 因而使得程序獲得明顯的加速 24 程序中的局部性 ? 局部性與內(nèi)存分層 – 通常 ， 最快的緩存 沒(méi)有大到足以把 代碼和數(shù)據(jù) 同時(shí)放在其中 – 從 程序難以 看出哪部分代碼 和數(shù)據(jù) 會(huì)被頻繁使用 – 動(dòng)態(tài)調(diào)整最快緩存的內(nèi)容不可避免 – 把最近使用的指令保存在緩存是一種較好的最優(yōu)化利用內(nèi)存分層的策略 – 改變數(shù)據(jù)布局或計(jì)算次序也可以改進(jìn)程序數(shù)據(jù)訪問(wèn)的時(shí)間和空間局部性 25 ? 數(shù)據(jù)局部性 計(jì)算向量 X和 Y對(duì)應(yīng)元素差的平方 for (i = 0。 i n。 i++) { // 有較好的數(shù)據(jù)局部性 Z[i] = X[i] ? Y[i]。 j++) for (i = 0。 i++) for (j = 0。 – 為了獲得最好的性能，應(yīng)該讓外循環(huán)并行執(zhí)行 b = ceil (n/M)。 j n。 char name[10000][20]。 i n。 for (k = 0。 令 c = 4, n = 12 – 假定緩存足以放下 X所 有的緩存行 ， 則讀入 X 出現(xiàn) n2/c次緩存未命中 X, Y, Z: n?n for (i = 0。 j++) { Z[i][j] = 。 } 矩陣乘算法及其優(yōu)化 35 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 好 為 n2/c (即 Y 都可入緩存 ) 灰色表示在緩存中 36 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 好 為 n2/c (即 Y 都可入緩存 ) 灰色表示在緩存中 37 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 好 為 n2/c (即 Y 都可入緩存 ) 灰色表示在緩存中 38 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 好 為 n2/c (即 Y 都可入緩存 ) 灰色表示在緩存中 39 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 好 為 n2/c (即 Y 都可入緩存 ) 灰色表示在緩存中 40 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 好 為 n2/c (即 Y 都可入緩存 ) 灰色表示在緩存中 41 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 好 為 n2/c (即 Y 都可入緩存 ) 灰色表示在緩存中 42 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 好 為 n2/c (即 Y 都可入緩存 ) 灰色表示在緩存中 43 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的一行時(shí) ， 需要逐列訪問(wèn) Y的所有元素 矩陣乘算法及其優(yōu)化 完成 Z一行 元素 的計(jì)算過(guò) 程中，因取 Y而出現(xiàn)的緩存 未命中次數(shù) 最 壞 為 n3 (緩存 連 Y的一列數(shù) 據(jù)都不能駐留 ) 灰色表示在緩存中 44 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法 – 當(dāng)使用 X的
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1