【正文】 = Z[i] ? Z[i]。 j++) for (i = 0。 char name[10000][20]。 j++) { Z[i][j] = 。 j++) for (k = kk。 矩陣乘算法及其優(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。 j++) for (k = kk。 i ii + b。 jj = jj + b) for (kk = 0。 k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]。 i min(n, b?(p+1))。 } for (i = 0。 //對(duì)應(yīng)元素差的平方 Z[i] = Z[i] ? Z[i]。面向計(jì)算機(jī)體系結(jié)構(gòu)的程序優(yōu)化 計(jì)算機(jī)科學(xué)導(dǎo)論第七講 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 陳意云 055163607043, 課 程 內(nèi) 容 ? 課程內(nèi)容 圍繞學(xué)科理論體系中的模型理論 , 程序理論和計(jì)算理論 1. 模型理論關(guān)心的問(wèn)題 給定模型 M，哪些問(wèn)題可以由模型 M解決；如何比較模型的表達(dá)能力 2. 程序理論關(guān)心的問(wèn)題 – 給定模型 M，如何用模型 M解決問(wèn)題 – 包括程序設(shè)計(jì)范型、 程序設(shè)計(jì)語(yǔ)言、程序設(shè)計(jì)、形式語(yǔ)義、類型論、程序驗(yàn)證、程序分析等 3. 計(jì)算理論關(guān)心的問(wèn)題 給定模型 M和一類問(wèn)題 , 解決該類問(wèn)題 需多少資源 本講座以矩陣乘算法為例，介紹圍繞體系結(jié)構(gòu)的優(yōu)化 2 講 座 提 綱 ? 基本知識(shí) – 內(nèi)存分層結(jié)構(gòu)、多處理器的體系結(jié)構(gòu) ? 并行計(jì)算 – 并行計(jì)算的常見(jiàn)方式、循環(huán)級(jí)并行 ? 程序中的局部性 – 時(shí)間局部性、空間局部性、代碼和數(shù)據(jù)局部性 ? 矩陣乘算法及 其 優(yōu)化 – 矩陣乘算法及分析、分塊的矩陣乘算法及分析 圍繞計(jì)算機(jī)體系結(jié)構(gòu)而不是抽象模型來(lái)討論 3 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存 1. 初學(xué)編程時(shí)的認(rèn)識(shí) – 計(jì)算機(jī)的重要組成部分 ， 由若干內(nèi)存單元組成 ，用于存放程序和數(shù)據(jù) ， 可以按地址存取 2. 學(xué)習(xí)遞歸函數(shù)時(shí)的認(rèn)識(shí) 例：快速排序 int a[11]。 i++) { //計(jì)算向量 X和 Y Z[i] = X[i] ? Y[i]。 i++) { Z[i] = Z[i] ? Z[i]。 for (i = b?p。 k n。 jj n。 kk = kk + b) for (i = ii。 j jj + b。 ii n。 k kk + b。 for (k = 0。 char name[20]。 i n。 } // 數(shù)據(jù)并行的例子 循環(huán)級(jí)并行 21 ? 循環(huán)級(jí)并行 – 對(duì)并行化來(lái)說(shuō) ， 任務(wù)級(jí)不像循環(huán)級(jí)那樣有吸引力 – 對(duì)一個(gè)程序而言 ， 獨(dú)立的任務(wù)數(shù)是一個(gè)常數(shù) ， 它不像典型的循環(huán)那樣 ， 獨(dú)立的計(jì)算單元隨迭代次數(shù)增加而增加 – 任務(wù)通常不是等規(guī)模的 ， 因此很難保證所有的處理器在所有時(shí)間都處于忙碌 循環(huán)級(jí)并行 22 程序中的局部性 ? 局部性的表現(xiàn) 大多數(shù)程序的大部分時(shí)間在執(zhí)行一小部分代碼 ， 并且僅涉及一小部分?jǐn)?shù)據(jù) 。 a[10] = 9999。 quickSort(1, 9)。 傳統(tǒng) 的 說(shuō)法 ： 程序 90％ 的時(shí)間消耗在執(zhí)行 10％ 的代碼上 （ 代碼的局部性 ） – 程序經(jīng)常包含許多決不會(huì)執(zhí)行的 代碼 ， 如 由組件和庫(kù)構(gòu)建的程序經(jīng)常僅用所提供功能的一小部分 – 程序 運(yùn)行時(shí) ， 通常 僅 一部分代碼被真正執(zhí)行 。 i++) for (i = 0。 … … … … } struct student st[10000]。 k n。 k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]。 ii = ii + b) for (jj = 0。 i++) for (j = jj。 kk n。 ii = ii + b) for (jj = 0。 for (k = 0。 – 為了獲得最好的性能，應(yīng)該讓外循環(huán)并行執(zhí)行 b = ceil (n/M)。 i n。 i n。 void quickSort(int m, int n) { void readArray(){int i。 } 該循環(huán)可并行執(zhí)行，把它變換成如下代碼。 i n。 i++) for (j = 0。 } 矩陣乘算法及其優(yōu)化 34 ? 矩陣乘算法 – 假定在計(jì)算 Z[i][j]的過(guò)程中 , 其值保存 在 寄存器中 ,則計(jì)算過(guò)程中不訪問(wèn)其內(nèi)存單元 ， 僅最后存儲(chǔ) 1次 – 假定 c個(gè)元素正好占滿 一個(gè)緩存行 ， 則 X的 1行散布在 n/c個(gè)緩存 行上 。 kk n。 i++) for (j = jj。 k kk + b。 k++) Z[i][j] = Z[i][j] + X[i][k] ? Y[k][j]。 j jj + b。 j n。 int num。 j n。 i++) { Z[i] = X[i] ? Y[i]。 a[0] = 9999。 } } } 允許聲明遞歸函數(shù)，存儲(chǔ)分配有什么變化 4 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存 需要分出一塊來(lái)作為數(shù)據(jù)棧 main 函數(shù)調(diào)用關(guān)系樹(shù) main 棧 5 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存 需要分出一塊來(lái)作為數(shù)據(jù)棧 main r 函數(shù)調(diào)用關(guān)系樹(shù) main int i r ( ) 棧 6 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存 需要分出一塊來(lái)作為數(shù)據(jù)棧 main q(1,9) r 函數(shù)調(diào)用關(guān)系樹(shù) main int i q (1, 9) int m, n 棧 7 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存 需要分出一塊來(lái)作為數(shù)據(jù)棧 main q(1,9) r p(1,9) q(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n 棧 函數(shù)調(diào)用關(guān)系樹(shù) 8 基 本 知 識(shí) ? 計(jì)算機(jī)內(nèi)存 需要分出一塊來(lái)作為數(shù)據(jù)棧 main q(1,9) r p(1,9) q(1,3) q(1,0) p(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n int i q (1, 0) int m, n 棧 函數(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)造