此lab主要是針對(duì)CSAPP第四章的內(nèi)容，主要是學(xué)習(xí)設(shè)計(jì)和優(yōu)化Y86-64處理器，分成了3個(gè)部分，第一部分熟悉Y86-64指令，第二部分熟悉pipeline的設(shè)計(jì)，第三部分結(jié)合前兩部分綜合優(yōu)化，獲得盡可能低的CPE。

優(yōu)化建議

我相信大部分人都是來(lái)看partC的優(yōu)化的，所以先說(shuō)說(shuō)優(yōu)化思路，按著思路再自己試試，實(shí)在想不出來(lái)再看答案。

1. 必須添加iaddq指令；

2. 此lab，%rax默認(rèn)為0，不需要xor；

3. 循環(huán)展開；

4. 有數(shù)據(jù)冒險(xiǎn)，可以通過(guò)psim -g調(diào)試發(fā)現(xiàn)冒險(xiǎn)的地方，插入其他指令規(guī)避；

5. 有控制冒險(xiǎn)，要合理安排跳轉(zhuǎn)；

6. 一個(gè)測(cè)試條件可以同時(shí)跟jl、je、jg；

7. 著重優(yōu)化非循環(huán)部分/數(shù)據(jù)少的部分；

8. 需要用到三叉樹；

9. 劇透一下，hcl文件只改iaddq，通過(guò)優(yōu)化ncopy代碼是可以得滿分的。

進(jìn)階優(yōu)化：

1. 修改hcl文件，解決掉數(shù)據(jù)冒險(xiǎn)，可以看書的家庭作業(yè)4.57。

配置問(wèn)題

或者是環(huán)境配置問(wèn)題，畢竟lab很老了，很多東西都更新了，可以根據(jù)出現(xiàn)的錯(cuò)誤提示一步步解決。

1、可能需要安裝tcl、tk、flex、bison

2、可能要修改Makefile

Makefile中的TKINC的tcl頭文件路徑是tcl8.5，目前系統(tǒng)下載的是8.6，以后可能還會(huì)更新，改成對(duì)應(yīng)的版本號(hào)。

3、可能代碼發(fā)生了改變

tcl的代碼結(jié)構(gòu)發(fā)生了變化，改變了使用方法，不過(guò)可以添加-DUSE_INTERP_RESULT到Makefile中解決，忽略相關(guān)的警告。

4、可能提示找不到變量matherr

把它注釋掉就好，

第一部分

將examples.c中的三個(gè)函數(shù)改寫成Y86-64匯編程序，這個(gè)不難，沒啥好說(shuō)的，直接上代碼吧。

sum.ys

rsum.ys

copy_block.ys

第二部分

添加iaddq指令，目的是熟悉hcl語(yǔ)言，后續(xù)要用到iaddq。具體改動(dòng)看下面的diff，這個(gè)也不算難，理解了hcl可以很容易搞定。

第三部分

這部分才是這個(gè)lab的重頭戲，通過(guò)修改ncopy.ys和pipe-full.hcl讓ncopy.ys跑的盡可能快，幾個(gè)要求是：

1. ncopy要適用任意數(shù)組大??；

2. ncopy要能過(guò)YIS；

3. ncopy的目標(biāo)文件不能大于1000字節(jié)；

4. pipe-full.hcl要能過(guò)../y86-code 和 ../ptest的測(cè)試，尤其是這點(diǎn)，benchmark不檢查對(duì)錯(cuò)，如果psim有問(wèn)題，benchmark可能會(huì)得到很低的CPE，誤以為自己得了滿分。

3.1、代碼和模擬器測(cè)試：

1、保證代碼正確：

./correctness.pl

2、保證模擬器正確

(cd ../y86-code; make testpsim)

(cd ../ptest; make SIM=../pipe/psim TFLAGS=-i)

3、保證二者結(jié)合正確

./correctness.pl -p

通過(guò)了上面的測(cè)試，才能保證代碼和模擬器都OK。

運(yùn)行./benchmark.pl查看最終的CPE和得分。

3.2、原始ncopy.ys和pipe-full.hcl得分

3.3、hcl添加iaddq指令，ncopy.ys改為iaddq指令，速度明顯提升；

3.4、循環(huán)展開

到此，需要進(jìn)一步對(duì)代碼動(dòng)手了，方法是第五章的循環(huán)展開，由于目標(biāo)代碼長(zhǎng)度1000bytes的限制，最多只能展開到10。另外，針對(duì)此lab，%rax默認(rèn)為0，可以去掉xorq %rax,%rax這句，不過(guò)實(shí)際應(yīng)用不能這樣。

剛開始的思路是先展開（8-10）次循環(huán)，剩下的展開4次循環(huán)，之后2次，最后1次，（簡(jiǎn)稱n421，以后都這么叫）通過(guò)判斷rdx選擇執(zhí)行的路徑組合，展開10次（10421）的CPE能到7.69，提升明顯。代碼見附1。

對(duì)于以上結(jié)果不滿意，復(fù)制3個(gè)數(shù)據(jù)會(huì)分成2+1，這比較慢，想想改為n4321，3也獨(dú)立出來(lái)，這次展開8次最快，CPE到7.60。代碼見附2。

仍然不滿意，4以下的路徑是3-2-1-0，

下圖可知1的權(quán)重很大，減少它的CPE很關(guān)鍵。

?

匯編可以一個(gè)條件執(zhí)行多個(gè)跳轉(zhuǎn)，而跳轉(zhuǎn)有小于（jl）、等于（je）和大于（jg），

所以可以用三叉樹構(gòu)建跳轉(zhuǎn)路徑，減少指令數(shù)。

因?yàn)樘幚砥饔蟹种ьA(yù)測(cè)，并且默認(rèn)是要跳轉(zhuǎn)的，所以要把概率大的或者緊要的部分緊挨著測(cè)試條件，因?yàn)橐坏╊A(yù)測(cè)錯(cuò)誤，就會(huì)多出兩條bubble。按照上面的樹，構(gòu)造出n4r213（r2表示root2，2是根，左在前，右在后，0第一個(gè)不算CPE，永遠(yuǎn)放到分支最后，而且可能會(huì)跟10沖突，故省略），我測(cè)試84r213最快，得到下面的結(jié)果，可見優(yōu)化有效，CPE已經(jīng)非常接近7.5了。這里還可以以1為根，感興趣的小伙伴可以自己測(cè)試，看看是快是慢。代碼見附3.

就差1.1就滿分了，繼續(xù)努力。我們發(fā)現(xiàn)循環(huán)展開部分已經(jīng)無(wú)法優(yōu)化了（最多是8、9、10的差別），后邊1、2、3也到頭了，問(wèn)題就在中間的4了。之前的代碼都是小于4的直接執(zhí)行0、1、2、3的部分，大于等于4的先執(zhí)行4次展開，再根據(jù)結(jié)果執(zhí)行0、1、2、3，這里就拖慢了性能，我們換個(gè)思路進(jìn)一步優(yōu)化。

?

這次我們把非循環(huán)部分都獨(dú)立出來(lái)，用上面樹的思想得到具體的數(shù)，然后直接跳到對(duì)應(yīng)的地方執(zhí)行，如下圖所示。這里以3為根，原因還是要盡量靠近循環(huán)次數(shù)少的，盡可能減少其指令數(shù)。（CPE=指令數(shù)/數(shù)據(jù)個(gè)數(shù)，數(shù)據(jù)越少，非復(fù)制部分占比越大。這里的定義好像跟第五章的CPE有點(diǎn)差別，我們知道這里啥意思就可以了）。

分支部分的代碼如下所示（9r31264578）：

上圖右邊只是示意圖，具體實(shí)現(xiàn)還需要優(yōu)化，因?yàn)閙rmovq和rmmovq 如果前后挨著，會(huì)有裝載/使用冒險(xiǎn)，第二條rmmovq指令會(huì)產(chǎn)生一個(gè)暫停，這會(huì)降低性能，可以使用加載轉(zhuǎn)發(fā)技術(shù)，修改hcl文件解決這個(gè)問(wèn)題，不過(guò)我們先不動(dòng)hcl文件，想辦法在它們之間插入一條其他指令，取代這個(gè)暫停就好，具體辦法是把上一條指令的判斷正負(fù)插入他們中間，如下：（可讀性非常差，一不小心就混亂了，一定要仔細(xì)）

通過(guò)以上努力，我們得到了最終的版本，實(shí)測(cè)展開9次和10次CPE=7.49，滿分啦。代碼見附4。

到此，只增加iaddq指令的優(yōu)化就做到這里了，或許還能提高，就交給感興趣的小伙伴自行嘗試吧。

3.5、加載轉(zhuǎn)發(fā)

之前的版本雖然滿分但還是有缺陷，或者是不可避免的會(huì)有一個(gè)暫停（如下圖，rdx為8），

或者是執(zhí)行一條沒用的跳轉(zhuǎn)（如下圖，rdx為7，跳到這里），

這都是裝載/使用冒險(xiǎn)帶來(lái)的副作用，看來(lái)必須把它解決掉才能得到完美的版本。加載轉(zhuǎn)發(fā)具體原理可以看原書家庭作業(yè)4.57，我們?cè)谔砑觟addq指令的pipe-ful.hcl文件中進(jìn)一步做以下修改：

重新make并測(cè)試，都OK就得到了改進(jìn)版的psim。

這樣在ncopy里寫代碼就沒有之前的限制了，mrmovq和rmmovq可以挨著，沒有暫停。這里我人為加了個(gè)要求，就是寄存器只用調(diào)用者保存的，因?yàn)閷?shí)際寫程序，用被調(diào)用者保存寄存器是需要入棧和出棧的，這里雖沒有要求，但規(guī)范還是要的。

此時(shí)的性能瓶頸就只在分支的安排上了，展開越多，分支的可能性越多，腦子想哪個(gè)更快難度很大，具體效果還需要實(shí)驗(yàn)，我實(shí)測(cè)展開10次最好，分支是10r312645789，CPE=7.40，這已經(jīng)超過(guò)文檔中老師的最好7.48，其他分支情況可能是7.44、7.45、7.46，差距不是太大。我都懷疑自己是不是弄錯(cuò)了，希望小伙伴們也試試，看能否復(fù)現(xiàn)。

最優(yōu)版本ncopy代碼如下：

最優(yōu)版本pipe-full.hcl如下：

這里或許沒人看，我就說(shuō)點(diǎn)悄悄話，我們通過(guò)上面的過(guò)程可以看到，修改指令和循環(huán)展開獲取的性能提升非常明顯，這些優(yōu)化是顯而易見的，也是比較容易的，性價(jià)比很高。而后續(xù)的優(yōu)化包括分支優(yōu)化、加載轉(zhuǎn)發(fā)，提升不算大，但是難度卻不小，花了大量的時(shí)間，CPE的提升只有0.1，性價(jià)比不高。

不過(guò)，容易的誰(shuí)都能做到，而能把不容易的做到，才能體現(xiàn)出自己產(chǎn)品的優(yōu)勢(shì)。很多好的系統(tǒng)和處理器或許就是在這些細(xì)節(jié)上有精益求精的要求，日積月累下讓這些小的優(yōu)勢(shì)積累成了大的壁壘，成為了自己產(chǎn)品的核心競(jìng)爭(zhēng)力。個(gè)人認(rèn)為不應(yīng)該忽視這些細(xì)枝末節(jié)的優(yōu)化，累積的多了就會(huì)成為突變。

俗話說(shuō)：不積跬步無(wú)以至千里，或許就是這個(gè)道理。

附1：10421

?

附2：84321

?

附3：84r213

?

附4：滿分-只改iaddq指令

?

?