面向計(jì)算機(jī)體系結(jié)構(gòu)的程序優(yōu)化計(jì)算機(jī)科學(xué)導(dǎo)論第七講-資料下載頁
2025-08-01 14:46本頁面
【正文】 是內(nèi)存的數(shù)據(jù) ， 則數(shù)據(jù)局部性好 矩陣乘算法及其優(yōu)化 在上述算法中 ， Y中一個(gè)數(shù)據(jù)的復(fù)用被 n2個(gè)乘加操作隔開 ,Y中 一個(gè)緩存行 的復(fù)用被 n個(gè)乘加操作隔開 62 Y[0,0]用于 Z[0,0]的計(jì)算， Y[0,0]在計(jì)算 Z[0,1]再用 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法的優(yōu)化 – 復(fù)用在緩存而不是內(nèi)存的數(shù)據(jù) ， 則數(shù)據(jù)局部性好 矩陣乘算法及其優(yōu)化 在一個(gè)處理器上 ， 數(shù)據(jù)只有被本處理器復(fù)用時(shí)才可能出現(xiàn)緩存命中 63 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法的優(yōu)化 – 復(fù)用在緩存而不是內(nèi)存的數(shù)據(jù) ， 則數(shù)據(jù)局部性好 矩陣乘算法及其優(yōu)化 改變數(shù)據(jù)布局和語句執(zhí)行次序都可能改進(jìn)緩存行的復(fù)用 64 j = 0, 1, … , n ?1 i = 0 X Y ? 矩陣乘算法的優(yōu)化 – 復(fù)用在緩存而不是內(nèi)存的數(shù)據(jù) ， 則數(shù)據(jù)局部性好 矩陣乘算法及其優(yōu)化 分塊計(jì)算是重排循環(huán)中迭代次序的較好方法 能極大地改進(jìn)程序的局部性 65 ? 分塊計(jì)算的示意圖 1. X和 Y的灰色部分進(jìn)行乘加運(yùn) 算 ， 可得到 Z的灰色部分的結(jié)果 2. X和 Y的灰色部分分別由若干 行和若干列構(gòu)成 3. 對(duì) X和 Y進(jìn)行分塊 ， 通過增加 循環(huán)來分塊計(jì)算 b n 矩陣乘算法及其優(yōu)化 X: Y: Z: 66 ? 分塊計(jì)算的示意圖 1. X和 Y的灰色部分進(jìn)行乘加運(yùn) 算 ， 可得到 Z的灰色部分的結(jié)果 2. X和 Y的灰色部分分別由若干 行和若干列構(gòu)成 3. 對(duì) X和 Y進(jìn)行分塊 ， 通過增加 循環(huán)來分塊計(jì)算 b n 矩陣乘算法及其優(yōu)化 X: Y: Z: 67 ? 分塊計(jì)算的示意圖 1. X和 Y的灰色部分進(jìn)行乘加運(yùn) 算 ， 可得到 Z的灰色部分的結(jié)果 2. X和 Y的灰色部分分別由若干 行和若干列構(gòu)成 3. 對(duì) X和 Y進(jìn)行分塊 ， 通過增加 循環(huán)來分塊計(jì)算 b n 矩陣乘算法及其優(yōu)化 X: Y: Z: 68 ? 分塊計(jì)算的示意圖 1. X和 Y的灰色部分進(jìn)行乘加運(yùn) 算 ， 可得到 Z的灰色部分的結(jié)果 2. X和 Y的灰色部分分別由若干 行和若干列構(gòu)成 3. 對(duì) X和 Y進(jìn)行分塊 ， 通過增加 循環(huán)來分塊計(jì)算 b n 矩陣乘算法及其優(yōu)化 X: Y: Z: 69 ? 矩陣乘算法的優(yōu)化 – 仍假定 n能由 b整除 , 假定 Z的元素已經(jīng)先行置初值 for (ii = 0。 ii n。 ii = ii + b) for (jj = 0。 jj n。 jj = jj + b) for (kk = 0。 kk n。 kk = kk + b) for (i = ii。 i ii + b。 i++) for (j = jj。 j jj + b。 j++) for (k = kk。 k kk + b。 k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]。 矩陣乘算法及其優(yōu)化 b n 70 ? 矩陣乘算法的優(yōu)化 – 仍假定 n能由 b整除 , 假定 Z的元素已經(jīng)先行置初值 – 前兩行程序表示以塊為單位進(jìn)行矩陣乘 – 第 3行程序表示 n/b個(gè) X和 Y的塊相乘得到 Z的一塊的結(jié)果 for (ii = 0。 ii n。 ii = ii + b) for (jj = 0。 jj n。 jj = jj + b) for (kk = 0。 kk n。 kk = kk + b) for (i = ii。 i ii + b。 i++) for (j = jj。 j jj + b。 j++) for (k = kk。 k kk + b。 k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]。 矩陣乘算法及其優(yōu)化 b n 71 ? 矩陣乘算法的優(yōu)化 – 仍假定 n能由 b整除 , 假定 Z的元素已經(jīng)先行置初值 – 從第 4到 8行的程序計(jì)算左上角為 X[ii][kk]和 Y[kk] [jj]的兩塊對(duì)左上角為 Z[ii][jj]的塊的貢獻(xiàn) for (ii = 0。 ii n。 ii = ii + b) for (jj = 0。 jj n。 jj = jj + b) for (kk = 0。 kk n。 kk = kk + b) for (i = ii。 i ii + b。 i++) for (j = jj。 j jj + b。 j++) for (k = kk。 k kk + b。 k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]。 矩陣乘算法及其優(yōu)化 b n 72 ? 分塊計(jì)算的示意圖 從第 4到 8行的程序計(jì)算左上角為 X[ii][kk]和 Y[kk][jj]的兩塊對(duì)左上角為 Z[ii][jj]的塊的貢獻(xiàn) 當(dāng)前： ii = 0， kk = 1， jj = 0 b n 矩陣乘算法及其優(yōu)化 X: Y: Z: 73 ? 矩陣乘算法的優(yōu)化 – 適當(dāng)選擇 b， 使 3個(gè)矩陣都有一個(gè)塊可以裝到緩存 – 把 X或 Y一塊取到緩存 ， 會(huì)出現(xiàn) b2/c次緩存未命中 – 對(duì)于 X和 Y的一對(duì)塊 ， 第 4到 8行的程序完成 b3次乘加計(jì)算 – 由于整個(gè)矩陣乘法需要 n3次乘加計(jì)算 ， 則取一對(duì)塊到緩存的總次數(shù)是 n3/b3（ b3源于上一條 ） – 對(duì)于 X和 Y的一對(duì)塊會(huì)有 2b2/c次緩存未命中 ， 因此緩存未命中的總次數(shù)是 2b2/c ? n3/b3 = 2n3/bc – 和先前的 O(n3)次緩存未命中相比 ， 在 b較大時(shí) ，2n3/bc能體現(xiàn)出分塊方法的好處 矩陣乘算法及其優(yōu)化 74 ? 矩陣乘算法的優(yōu)化 – 分塊技術(shù)可以用到內(nèi)存分層的每一層 ， 例如 ， 可以把 2?2矩陣乘的運(yùn)算對(duì)象都保存在寄存器中 – 緩存的實(shí)際情況不像這里介紹的這么簡單 ， 這里介紹的方法要依據(jù)緩存的約束進(jìn)行調(diào)整 矩陣乘算法及其優(yōu)化 75 小 結(jié) ? 本講座小結(jié) – 算法分析是比較算法優(yōu)劣的一個(gè)重要依據(jù) – 程序的運(yùn)行效率還依賴于體系結(jié)構(gòu)的很多特點(diǎn) ，有些特點(diǎn)沒有反映在描述算法的編程語言中 ， 導(dǎo)致僅基于編程語言的語義難以比較算法優(yōu)劣 – 熟悉體系結(jié)構(gòu) 、 算法分析 、 編程語言 、 編譯原理的程序員更有可能寫出效率較高的程序 ? 參考書 – 陳意云、張昱，編譯原理 (第 3版），高教出版社 本講的內(nèi)容取自該教材 76 小 結(jié) ? 相關(guān)課程 – 算法基礎(chǔ)、程序設(shè)計(jì)語言基礎(chǔ)、編譯原理、計(jì)算機(jī)體系結(jié)構(gòu)、并行計(jì)算 ? 研究方向 – 怎樣從現(xiàn)代體系結(jié)構(gòu)抽象出計(jì)算模型 – 在這些抽象模型上的算法分析方法 77
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1