深入理解計(jì)算機(jī)系統(tǒng)第二版資料家庭作業(yè)答案

1、. .PAGE84 / NUMPAGES84 HYPERLINK :/ 深入理解計(jì)算機(jī)系統(tǒng)(第二版) 家庭作業(yè) 第二章 HYPERLINK :/ t _blank 深入理解計(jì)算機(jī)系統(tǒng) HYPERLINK :/ t _blank 二進(jìn)制2.55-2.57略2.58intis_little_endian()inta =1;return*(char*)&a);2.59(x&0 xFF) | (y&0 xFF)2.60unsignedreplace_byte(unsignedx,unsignedcharb,inti)return(x&(0 xFF(i3)|(b(i(sizeof(int)-1)1)=-

2、1;2.63對(duì)于sra，主要的工作是將xrsl的第w-k-1位擴(kuò)展到前面的高位。這個(gè)可以利用取反加1來實(shí)現(xiàn)，不過這里的加1是加1(w-k-1)。如果x的第w-k-1位為0，取反加1后，前面位全為0，如果為1，取反加1后就全是1。最后再使用相應(yīng)的掩碼得到結(jié)果。對(duì)于srl，注意工作就是將前面的高位清0，即xsra & (1(w-k) - 1)。額外注意k=0時(shí)，不能使用1(w-k)，于是改用2k;intw =sizeof(int) 3;unsigned z =1k;intw =sizeof(int)*8;unsigned z =216);x=(x 8);x=(x 4);x=(x 2);x=(x 1

3、);return!(x&1);x的每個(gè)位進(jìn)行異或，如果為0就說明是偶數(shù)個(gè)1，如果為1就是奇數(shù)個(gè)1。那么可以想到折半縮小規(guī)模。最后一句也可以是 return (x1)&12.66根據(jù)提示想到利用或運(yùn)算，將最高位的1或到比它低的每一位上，忽然想如果x就是10000000.該如何讓每一位都為1。于是便想到了二進(jìn)擴(kuò)展。先是x右移1位再和原x進(jìn)行或，變成1100000.，再讓結(jié)果右移2位和原結(jié)果或，變成11110000.，最后到16位，變成11111111.。intleftmost_one(unsigned x)x|=(x1);x|=(x2);x|=(x4);x|=(x8);x|=(x16);retur

4、nx(x1);2.67A.32位機(jī)器上沒有定義移位32次。B.beyond_msb變?yōu)?231。C.定義 a = 115; a=15; set_msb = a1; beyond_msb = a2;2.68感覺中文版有點(diǎn)問題，注釋和函數(shù)有點(diǎn)對(duì)應(yīng)不上，于是用英文版的了。個(gè)人猜想應(yīng)該是讓x的最低n位變1。intlower_one_mask(intn)return(2n)|(x(w-n-1)=(n-1);return!x|!(x);2.71A.得到的結(jié)果是unsigned，而并非擴(kuò)展為signed的結(jié)果。B.使用int，將待抽取字節(jié)左移到最高字節(jié)，再右移到最低字節(jié)即可。intxbyte(unsigne

5、d word,intbytenum)intret = word(3-bytenum)24;2.72A.size_t是無符號(hào)整數(shù)，因此左邊都會(huì)先轉(zhuǎn)換為無符號(hào)整數(shù)，它肯定是大于等于0的。B.判斷條件改為if(maxbytes 0 & maxbytes = sizeof(val)2.73請(qǐng)先參考2.74題。可知：t = a + b時(shí)，如果a，b異號(hào)（或者存在0），則肯定不會(huì)溢出。如果a，b均大于等于0，則t=0就是負(fù)溢出。于是，可以利用三個(gè)變量來表示是正溢出，負(fù)溢出還是無溢出。intsaturating_add(intx,inty)intw =sizeof(int)=(w-1);y=(w-1);t=

6、(w-1);intpos_ovf =x&y&t;intneg_ovf = x&y&t;intnovf =(pos_ovf|neg_ovf);return(pos_ovf & INT_MAX)|(novf & ans)|(neg_ovf & INT_MIN);2.74對(duì)于有符號(hào)整數(shù)相減，溢出的規(guī)則可以總結(jié)為：t = a-b;如果a, b 同號(hào)，則肯定不會(huì)溢出。如果a=0 & b0，則只有當(dāng)t=0時(shí)才算溢出。如果a=0，則只有當(dāng)t=0時(shí)才算溢出。不過，上述t肯定不會(huì)等于0，因?yàn)楫?dāng)a，b不同號(hào)時(shí)：1) a!=b，因此a-b不會(huì)等于0。2) a-b = abs(a) + abs(b) = abs(TM

7、ax) + abs(TMin)=(2w - 1)所以，a，b異號(hào)，t，b同號(hào)即可判定為溢出。inttsub_ovf(intx,inty)intw =sizeof(int)=(w-1);y=(w-1);t=(w-1);return(x!= y) & (y = t);順便整理一下匯編中CF，OF的設(shè)定規(guī)則(個(gè)人總結(jié)，如有不對(duì)之處，歡迎指正)。t = a + b;CF: (unsigned t) (unsigned a) 進(jìn)位標(biāo)志OF: (a0 = b0) & (t0 != a0)t = a - b;CF: (a=0) | (a0 = b0) & t0) 退位標(biāo)志OF: (a0 != b0) & (

8、b0 = t0)匯編中，無符號(hào)和有符號(hào)運(yùn)算對(duì)條件碼（標(biāo)志位）的設(shè)定應(yīng)該是一樣的，但是對(duì)于無符號(hào)比較和有符號(hào)比較，其返回值是根據(jù)不同的標(biāo)志位進(jìn)行的。詳情可以參考第三章3.6.2節(jié)。2.75根據(jù)2-18，不難推導(dǎo)， (x*y)_h = (x*y)_h + x(w-1)*y + y(w-1)*x。unsignedunsigned_high_prod(unsigned x,unsigned y)intw =sizeof(int)(w-1)*y+x*(y(w-1);當(dāng)然，這里用了乘法，不屬于整數(shù)位級(jí)編碼規(guī)則，聰明的辦法是使用int進(jìn)行移位，并使用與運(yùn)算。即 (int)x(w-1) & y 和 (int)

9、y(w-1) & x。注：不使用long long來實(shí)現(xiàn)signed_high_prod(int x, int y)是一件比較復(fù)雜的工作，而且我不會(huì)只使用整數(shù)位級(jí)編碼規(guī)則來實(shí)現(xiàn)，因?yàn)樾枰褂醚h(huán)和條件判斷。下面的代碼是計(jì)算兩個(gè)整數(shù)相乘得到的高位和低位。intuadd_ok(unsigned x,unsigned y)returnx+y= x;voidsigned_prod_result(intx,inty,int&h,int&l)intw =sizeof(int)3;h =0;l =(y&1)?x:0;for(inti=1;ii)&1)h+=(unsigned)x(w-i);if(!uadd_

10、ok(l,xi)h+;l+=(x(w-1)*y)+(y(w-1)*x);最后一步計(jì)算之前的h即為unsigned相乘得到的高位。sign_h = unsign_h - (x(w-1) & y) - (y(w-1) & x);sign_h = unsign_h + (x(w-1) * y) + (y(w-1) * x);2.76A. K=5: (x2) + xB. K=9: (x3) + xC. K=30: (x5) - (x1)D. K=-56: (x3) - (xk，再考慮舍入。舍入的條件是xk;intw =sizeof(int)(w-1)&(x&(1k)-1);returnans;2.78

11、這相當(dāng)于計(jì)算(x 3，當(dāng)然，需要考慮x為負(fù)數(shù)時(shí)的舍入。先看上述表達(dá)式，假設(shè)x的位模式為b(w-1), b(w-2), . , b(0)，那么我們需要計(jì)算：b(w-1),b(w-2),b(w-3), . ,b(0), 0, 0+ b(w-1),b(w-2),.,b(2), b(1), b(0)最后需要右移3位。因此我們可以忽略下方的b(1),b(0)。于是就計(jì)算(x2) + x，再右移一位即是所求答案。不過考慮到(x2) + x可能也會(huì)溢出，于是就計(jì)算(x3) + (x1)，這個(gè)顯然是不會(huì)溢出的。再看看b(0)+b(2)會(huì)不會(huì)產(chǎn)生進(jìn)位，如果產(chǎn)生進(jìn)位，則再加一。最后考慮負(fù)數(shù)的舍入。負(fù)數(shù)向0舍入的條

12、件是x0 & (x2)&1;intans =(x3)+(x1);intw =sizeof(int)(w-1)&(x&7);returnans;2.79不懂題意，感覺就是2.78。2.80A. 1w-n0n: (1n) - 1)B. 0w-n-m1n0m: (1n) - 1) y，而-y依然是Tmin，所以-x -y。B. true，補(bǔ)碼的加減乘和順序無關(guān)（如果是右移，則可能不同）。C. false，當(dāng)x=-1, y=1時(shí)，x + y = 0 xFFFFFFFE，而(x+y) = 0 xFFFFFFFF。D. true，無符號(hào)和有符號(hào)數(shù)的位級(jí)表示是一樣的。E. true，最后一個(gè)bit清0，對(duì)于

13、偶數(shù)是不變的，對(duì)于奇數(shù)相當(dāng)于-1，而TMin是偶數(shù)，因此該減法不存在溢出情況。所以左邊總是=x。2.82A. 令x為無窮序列表示的值，可以得到x*2k = Y + x。所以 x = Y/(2k - 1)。B. (a)1/7, (b)9/15 = 3/5, (c)7/63 = 1/92.83浮點(diǎn)數(shù)的一個(gè)特點(diǎn)就是，如果大于0，則可以按unsigned位表示的大小排序。如果小于0則相反。注意都為0的情況即可。所以條件是：(ux1)=0 & (uy= uy) |(sx & sy & ux =n的情況下才能成立。這時(shí)，s=0,e=n+2(k-1)-1,f=11.1。值為2(n+1)-1。C.最小的規(guī)格化

14、數(shù)為2(1-bias)即2(-2(k-1)+2)，所以其倒數(shù)值V為2(2(k-1)-2)，所以M為1.00000，f部分為全0，E=2(k-1)-2，e部分為2(k-1)-2 + bias = 2k - 3，即為11.101。位表示為0-11.101-00.0。2.85描述擴(kuò)展精度值十進(jìn)制最小的正非規(guī)格化數(shù)2(-63)*2(-214+2)3.6452e-4951最小的正規(guī)格化數(shù)2(-214+2)3.3621e-4932最大的規(guī)格化數(shù)(264-1)*2(214-1-63)1.1897e+49322.86描述HexMEV-00 x80000-62-最小的值10 x3F01257/2560257*2

15、(-8)2560 x470018-最大的非規(guī)格化數(shù)0 x00FF255/256-62255*2(-70)-inf0 xFF00-Hex為0 x3AA00 x3AA0416/256-5416*2（-13）=13*2(-8)2.87格式A格式B位值位值1 01110 001-9/161 0110 0010-9/160 10110 1012080 1110 10102081 00111 110-7/10241 0000 0111-7/10240 00000 1016/2170 0000 000001 11011 000-40961 1111 0000-inf0 11000 1007680 1111

16、0000inf沒有特別明白轉(zhuǎn)換成最接近的，然后又說向+inf舍入的含義。按理說，舍入到+inf就是向上舍入，而并不是找到最接近的。表格中是按最接近的進(jìn)行舍入，并且如果超出圍則認(rèn)為是inf。如果都按+inf進(jìn)行舍入，那么第四行格式B將是0 0000 0001。2.88A. false，float只能精確表示最高位1和最低位的1的位數(shù)之差小于24的整數(shù)。所以當(dāng)x=TMAX時(shí)，用float就無法精確表示，但double是可以精確表示所有32位整數(shù)的。B. false，當(dāng)x+y越界時(shí)，左邊不會(huì)越界，而右邊會(huì)越界。C. true，double可以精確表示所有正負(fù)253以的所有整數(shù)。所以三個(gè)數(shù)相加可以精確

17、表示。D. false，double無法精確表示264以所有的數(shù)，所以該表達(dá)式很有可能不會(huì)相等。雖然舉例子會(huì)比較復(fù)雜，但可以考慮比較大的值。E. false，0/0.0為NaN，(非0)/0.0為正負(fù)inf。同號(hào)inf相減為NaN，異號(hào)inf相減也為被減數(shù)的inf。2.89float的k=8, n=23。 bias = 27 - 1 = 127。最小的正非規(guī)格化數(shù)為2(1-bias-n) = 2-149。最小的規(guī)格化數(shù)為2(0-bias)*2 = 2-126。最大的規(guī)格化數(shù)（二的冪）為2(28-2 - bias) = 2127。因此按各種情況把區(qū)間分為TMin, -148 -149, -125

18、 -126, 127 128, TMax。floatfpwr2(intx)/* Result exponent and fraction */unsigned exp,frac;unsigned u;if(x -149)/* Too small. Return 0.0 */exp =0;frac =0;elseif(x-126)/* Denormalized result */exp =0;frac =1(x+149);elseif(x128)/* Normalized result. */exp = x+127;frac =0;else/* Too big. Return +oo */exp

19、 =255;frac =0;/* Pack exp and frac into 32 bits */u = exp31;unsigned exp =(fb23)&0 xFF;unsigned frac = fb&0 x7FFFFF;returnexp =0 xFF&frac!=0;boolis_inf(float_bits fb)unsigned sign = fb31;unsigned exp =(fb23)&0 xFF;unsigned frac = fb&0 x7FFFFF;returnexp =0 xFF&frac =0;inttestFun(float_bits(*fun1)(flo

20、at_bits),float(*fun2)(float)unsigned x =0;do/test for all 232 valuefloat_bits fb =fun1(x);floatff =fun2(u2f(x);if(!is_float_equal(fb,ff)printf(%x errorn,x);return0;x+;while(x!=0); printf(Test OKn);return1;最后的testFun是用來測(cè)試fun1和fun2是否對(duì)每種可能的輸入都輸出一樣的值，fun1為題中所要求的函數(shù)，fun2為float版本。這個(gè)函數(shù)大概會(huì)運(yùn)行2到3分鐘，也可以寫多線程，利用多

21、核處理器求解。2.91float_bitsfloat_absval(float_bits f)if(is_nan(f)returnf;elsereturnf&0 x7FFFFFFF;floatfloat_absval_f(floatf)if(is_nan(f2u(f)returnf;elsereturnfabs(f);測(cè)試即調(diào)用testFun(float_absval, float_absval_f);在測(cè)試的時(shí)候發(fā)現(xiàn)0 x7F800001的時(shí)候不對(duì)了。后來debug了一下，發(fā)現(xiàn)u2f的時(shí)候，會(huì)篡改原值。即令x = 0 x7F800001。則f2u(u2f(x)會(huì)變成0 x7FC00001。奇

22、怪的nan，第22位一定是1。我將f2u和u2f里用memcpy也同樣是不行。所以，我將testFun中的一個(gè)條件變成了：if(!is_float_equal(fb, ff) &!is_nan(fb)這個(gè)bug實(shí)在是不知道怎么回事。想了想，這和高位低位排列是無關(guān)的。這個(gè)bug還是之后再找吧。也有可能是硬件本身的原因了。注：C庫中也提供了isnan()函數(shù)。2.92float_bitsfloat_negate(float_bits f)if(is_nan(f)returnf;elsereturnf0 x80000000;floatfloat_negate_f(floatf)if(isnan(f)

23、returnf;return-f;就是將最高位反位。2.93float_bitsfloat_half(float_bits f)unsigned sign = f31;unsigned exp =(f23)&0 xFF;unsigned frac = f&0 x7FFFFF;if(exp =0)returnsign1)+(frac&1)&(frac1)&1);elseif(exp =1)returnsign31|(11)+(frac&1)&(frac1)&1);elseif(exp!=255)returnsign31| (exp-1)31;unsigned exp =(f23)&0 xFF;u

24、nsigned frac = f&0 x7FFFFF;if(exp =0)returnsign31|frac1;elseif(exp254)returnsign31|(exp+1)23|frac;elseif(exp =254)returnsign31|0 xFF0?i:-i;intsign = i0?0:1;intw =sizeof(int)=0;j-)/找到最高位if(xj)&1)break;unsigned bias =127;unsigned exp,frac;exp = bias+j;if(j=23)frac = x(j-23);unsigned mask =(1(1(j-24)fr

25、ac+;/需要舍入到大值elseif(x&mask)=1(j-24)&(frac&1)frac+;/舍入到偶數(shù)if(frac =(124)exp+;/舍入到偶數(shù)超過(124) - 1，指數(shù)需要再加1returnsign31|exp31;intexp =(f23)&0 xFF;intfrac =(f&0 x7FFFFF)|(123);exp-=127;if(exp=31)return0 x80000000;/絕對(duì)值不大于231（123)frac=(23-exp);returnsign?-frac : frac;voidtest2()intx =0;dointm =float_f2i(x);int

26、n =(int)u2f(x);if(m!= n)printf(error in %x:%d %dn,x,m,n);return;x+;while(x!=0);printf(Test OKn);在exp=31上犯了小錯(cuò)誤。開始寫成=32了。其實(shí)1這個(gè)整數(shù)就是exp=0的。而int絕對(duì)值不會(huì)超過231-1，因此1.0000.小數(shù)點(diǎn)右移不會(huì)到超過30次（否則就越界了），所以exp=30。而這里剛好用TMin來表示越界，因此不用關(guān)心TMin的表示。 HYPERLINK :/ 深入理解計(jì)算機(jī)系統(tǒng)(第二版) 家庭作業(yè) 第三章 3.54intdecode2(intx,inty,intz)intret;z-=

27、 y;/line 2ret = z;/line 3ret=15;/line 5returnret*(zx);3.55大概算法如下：x的高32位為xh，低32位為xl。y的符號(hào)位擴(kuò)展成32位之后為ys（ys為0或者-1）。dest_h = (xl*ys)_l + (xh*y)_l + (xl*y)_hdest_l = (xl*y)_l注意，所有的乘法都是unsigned*unsigned。也就是說對(duì)于 1*(-1)，如果存入兩個(gè)寄存器中，那么高32位是0，低32位是-1。相當(dāng)于 1*(UNSIGNED_MAX)。3.56注意n在這里是一個(gè)很小的數(shù)，用8位就能表示，也可以用n=n%256表示。寄存

28、器 變量esi xebx nedi resultedx maskintloop(intx,intn)intresult =1431655765;intmask;for(mask =1n)result=(mask&x);returnresult;3.57xp?*xp:0這個(gè)語句是不能被編譯成條件傳送語句的。因?yàn)槿绻菞l件傳送語句，那么不論xp為什么，*xp都會(huì)被計(jì)算。我們要寫一個(gè)和該功能完全一樣的能編譯成條件傳送語句的函數(shù)。于是，我們要想辦法不使用*xp，而使用一個(gè)替代的指向0的非空指針。intcread_alt(int*xp)intt =0;int*p = xp?xp:&t;return*p;

29、3.58MODE_A: result =*p1;*p1 =*p2;break;MODE_B: result =*p1+*p2;*p2 = result;break;MODE_C: result =*p1;*p2 =15;break;MODE_D:*p2 =*p1;MODE_E: result =17;break;default: result =-1;break;3.59intswitch_prob(intx,intn)intresult = x;switch(n)case0 x28:case0 x2a:result=3;break;case0 x2c:result=3;result-= x;

30、case0 x2d:result*= result;case0 x29:/也可以不要default:result+=0 x11;returnresult;中間有一句話沒明白，匯編第12行 lea 0 x0(%esi), %esi3.60對(duì)于ARST，Aijk 的位置是 A(,i*S*T+j*T+k,4)。由匯編代碼可知：S*T = 63;T = 9;R*S*T = 2772/4;所以得 R=11, S=7, T=9。3.61感覺可以用-j，而不是比較j和var_prod_ele(intn,intAnn,intBnn,inti,intk)intj = n-1;intresult =0;for(;

31、j!=-1;-j)result+= Aij*Bjk;returnresult;但是這樣得到的結(jié)果仍然會(huì)使用到存儲(chǔ)器。按下面的代碼，循環(huán)里面貌似就沒有用到存儲(chǔ)器。但是用到了一個(gè)常量4，就是增加a的時(shí)候，會(huì)add 4。只需要result，a，e，b，4n這五個(gè)變量。intvar_prod_ele(intn,intAnn,intBnn,inti,intk)intresult =0;int*a =&Ai0;int*b =&B0k;int*e =&Ain;for(;a!=e;)result+=*a*b;b+=n;a+;returnresult;下面是其匯編代碼的循環(huán)部分：edi是4*n，ebx和edx分

32、別是b和a，esi是e，eax是result。ecx是用于存儲(chǔ)乘法的寄存器。L4:movl(%ebx), %ecximull(%edx), %ecxaddl%ecx, %eaxaddl%edi, %ebxaddl$4, %edxcmpl%edx, %esijneL4我怎么感覺前面那個(gè)程序，編譯器應(yīng)該也會(huì)自動(dòng)優(yōu)化。3.62M = 76/4 = 19;i在edi中，j在ecx中;inttranspose(intM,intAMM)inti,j; for(i=0;iM;+i)int*a =&Ai0;int*b =&A0i;for(j=0;jxap-idx的地址。ecx存儲(chǔ)的是bp（地址）。ap的地址是

33、 bp + 4 + i*size(A)我們知道，ap-x0 的地址是 bp + 4 + i*size(A) + pos(x)，pos(x)為結(jié)構(gòu)體A中x的偏移。那么ap-xap-idx 的地址是 bp + 4 + i*size(A) + pos(x) +4*(ap-idx)。所以 4*edx + 8 = 4 + i*size(A) + pos(x) + 4*(ap-idx)。所以，不難猜測(cè)，pos(x)=4，也就是說，在A中，首先是idx，再是x數(shù)組。那么，我們看ap-idx在哪里計(jì)算過。到第10行，edx的結(jié)果是 7i + bp4 + 28*i，bp4 + 28*i是什么呢？它很可能是bp中

34、的ai的首地址。我們先這樣猜測(cè)，于是size(A) = 28，并且bp4+28*i的值為ap-idx。另一方面：4*edx = 28*i + 4*bp4+28*i = i*size(A) + 4*(ap-idx)。所以，我們的猜想是正確的。因此，size(A) = 28，里面包含了一個(gè)int idx和一個(gè)數(shù)組int x6?？偣灿卸嗌賯€(gè)A呢？CNT = 196/size(A) = 7。3.67A.e1.p: 0e1.x: 4e2.y: 0e2.next: 4B.總共需要8個(gè)字節(jié)。C.不難知道，賦值前后都應(yīng)該是整數(shù)。edx就是參數(shù)up（一個(gè)指針）。最后結(jié)果是用eax - (edx)得到的，說明(e

35、dx)是整數(shù)，即up-_ 為整數(shù)，肯定是表示的e2.y。再看看之前的eax，eax是由(eax)所得，說明到第3行后，eax是個(gè)指針。它是由(ecx)得到的，說明ecx在第二行也是個(gè)指針。而ecx是通過*(up+4)得到的，所以ecx是一個(gè)union指針next，即up-e2.next;到第三行，eax為*(ecx)，且是一個(gè)指針，所以eax在第三行為int* p，即up-e2.next-e1.p。所以，賦值符號(hào)后面的表達(dá)式就為 *(up-e2.next-e1.p) - up-e2.y再看看前面。最終賦值的地址是 ecx+4，而ecx那時(shí)候是一個(gè)next指針，而(next+4)必須是一個(gè)int

36、，也不難推測(cè)它是e1.x。因此前面就為 up-e2.next-e1.x。結(jié)果如下：voidproc(union ele*up)up-e2.next-e1.x =*(up-e2.next-e1.p)-up-e2.y;3.68版本一：使用getcharvoidgood_echo()charc;intx =0;while(x=getchar(),x!=n&x!=EOF)putchar(x);版本二：使用fgetsvoidgood_echo()constintBufferSize =10;charsBufferSize;inti;while(fgets(s,BufferSize,stdin)!=NUL

37、L)for(i=0;si;+i)putchar(si);if(ival;tp = tp-left;returnret;作用是從根一直遍歷左子樹，找到第一個(gè)沒有左子樹的節(jié)點(diǎn)的值。3.70longtraverse(tree_ptr tp)longv = MAX_LONG;if(tp!= NULL)v =min(traverse(tp-left),traverse(tp-right);/Line16 cmovle: if(r12v);/Line20 cmovle: if(raxrbx) rax=rbx;returnv;當(dāng)然，如果要用三目條件表達(dá)式的話：longtraverse(tree_ptr tp

38、)longv = MAX_LONG,rv,lv;if(tp!= NULL)lv =traverse(tp-left);rv =traverse(tp-right);v = lvrv?lv : rv;/Line16 cmovle: if(r12tp-v?tp-v : v;/Line20 cmovle: if(raxrbx) rax=rbx;returnv;函數(shù)的目的是找到樹的所有節(jié)點(diǎn)的值中最小的一個(gè)。 HYPERLINK :/ 深入理解計(jì)算機(jī)系統(tǒng)(第二版) 家庭作業(yè) 第四章 4.43沒有正確執(zhí)行pushl %esp，pushl %esp是將esp當(dāng)前的容入棧。如果REG是esp，那么代碼是先減去

39、了esp，然后將減了4以后的REG移入了esp。修改：（我只能想到利用其它的寄存器）movl REG, %eaxsubl $4, %espmovl %eax, (%esp)4.44也沒有正確執(zhí)行popl %esp，因?yàn)閜opl %esp是將當(dāng)前棧頂?shù)闹捣湃雃sp。如果REG是esp，那么最后得到esp是棧頂值減4之后的值。movl (%esp), %eaxaddl $4, %espmovl %eax, REG4.45我沒有按書上給的例子寫，而是自己寫了一個(gè)冒泡。voidbubble(int*data,intcount)if(count =0)return;inti,j;int*p,*q;for

40、(i=count-1;i!=0;i-)p = data,q = data+1;for(j=0;j!=i;+j)if(*p*q)intt =*p;*p =*q;*q = t;p+,q+;Y86：(movl就沒有區(qū)分那么細(xì)了，因?yàn)樘闊┝恕?data:#（從地地址往高地址）$5, $2, $7, $4, $3, $6, $1, $8movl $8, %ecxpushl %ecx #count = 8movl data, %ecxpushl %ecx #push datacall bubblehaltbubble:pushl%ebpmovl%esp, %ebppushl%esipushl%ebxpu

41、shl%edxmovl8(%ebp), %edx #edx = datamovl12(%ebp), %esi #esi = countandl%esi, %esijebubbleEnd#count=0movl $1, %eaxsubl%eax, %esi #count-jebubbleEnd#count=1OuterLoop:movl%edx, %ecx# p = data (ecx)pushl%esi# to save one regInnerLoop:movl(%ecx), %eaxmovl4(%ecx), %ebxsubl%eax, %ebxmovl 4(%ecx), %ebxjgNoS

42、wapmovl%eax, %ebx#swap, so ebx is greatermovl 4(%ecx), %eaxNoSwap:movl%eax, (%ecx)movl %ebx, 4(%ecx)movl $4, %eaxaddl%eax, %ecxmovl $1, %eaxsubl%eax, %esijneInnerLooppopl%esimovl $1, %eaxsubl%eax, %esijneOuterLoopbubbleEnd:popl%edxpopl%ebxpopl%esimovl%ebp, %esppopl%ebpret4.46InnerLoop改成：（edx是循環(huán)利用）mo

43、vl(%ecx), %edxInnerLoop:movl%edx, %eaxmovl4(%ecx), %ebxsubl%ebx, %eax # compare *p and *(p+1)cmovl%ebx, %edx #edx is maxmovl (%ecx), %eaxcmovg %ebx, %eax #%eax is minmovl%edx, 4(%ecx)movl%eax, (%ecx)movl $4, %eaxaddl%eax, %ecxmovl $1, %eaxsubl%eax, %esijneInnerLoop4.47我們可以明確的是，這條指令完成的任務(wù)為，ebp - M4cur

44、_ebpesp - cur_ebp + 4取指階段 icode:ifun = D:0valP = PC + 1譯碼階段 valB = R%ebp執(zhí)行階段 valE = valB + 4 訪存階段 valM = M4valB寫回階段 R%esp = valE R%ebp = valM4.48取指階段icode:ifun = M1PC = C:0 rA:rB = M1PC+1 valC = M4PC+2 valP = PC + 6譯碼階段 valB = RrB執(zhí)行階段 valE = valB + valC SetCC訪存階段 寫回階段 RrB = valE 4.494.50取指bool need_

45、regids =icode in IRRMOVL, IOPL, IPUSHL, IPOPL,IIRMOVL, IRMMOVL, IMRMOVL,IADDL;bool need_valC =icode in IIRMOVL, IRMMOVL, IMRMOVL, IJXX, ICALL,IADDL;譯碼和寫回int srcA = icode in IRRMOVL, IRMMOVL, IOPL, IPUSHL : rA;icode in IPOPL,IRET : RESP;1 : RNONE; # Dont need register;int srcB = icode in IOPL, IRMMOV

46、L, IMRMOVL,IADDL : rB;icode in IPUSHL, IPOPL, ICALL, IRET : RESP;icode in ILEAVE : REBP;1 : RNONE; # Dont need register;int dstE = icode in IRRMOVL& Cnd: rB;icode in IIRMOVL, IOPL,IADDL : rB;icode in IPUSHL, IPOPL, ICALL, IRET,ILEAVE : RESP;1 : RNONE; # Dont write any register;int dstM = icode in IM

47、RMOVL, IPOPL:rA; icode in ILEAVE : REBP;1 : RNONE; # Dont write any register;執(zhí)行int aluA = icode in IRRMOVL, IOPL : valA;icode in IIRMOVL, IRMMOVL, IMRMOVL,IADDL : valC;icode in ICALL, IPUSHL:-4;icode in IRET, IPOPL,ILEAVE:4;# Other instructions dont need ALU;int aluB = icode in IRMMOVL, IMRMOVL, IOP

48、L, ICALL,IPUSHL, IRET, IPOPL,ILEAVE, IADDL : valB;icode in IRRMOVL, IIRMOVL:0;# Other instructions dont need ALU;bool set_cc = icode in IOPL,IADDL;訪存int mem_addr = icode in IRMMOVL, IPUSHL, ICALL, IMRMOVL : valE;icode in IPOPL, IRET : valA;icode in ILEAVE : valB;# Other instructions dont need addres

49、s;bool mem_read = icode in IMRMOVL, IPOPL, IRET,ILEAVE;4.51 - 4.56感覺蠻麻煩的，不想寫啊。4.57A.發(fā)現(xiàn)加載/使用冒險(xiǎn)的邏輯公式：( E_icode in IMRMOVL, IPOPL & E_dstM in d_srcA, d_srcB)&!(E_icode = IMRMOVL & D_icode = IPUSHL);B.e_valA = (E_icode=IPUSH) & (M_dstM=E_srcA) : m_valM; 1 : E_valA; ;4.58版本1，在預(yù)測(cè)正確的情況下執(zhí)行7條指令，預(yù)測(cè)錯(cuò)誤時(shí)執(zhí)行9條指令并插

50、入一個(gè)bubble。版本2，執(zhí)行8條指令，但是在外部循環(huán)需要多執(zhí)行3條指令,否則就需要多用一個(gè)寄存器。暫時(shí)沒有想到好的辦法。光從循環(huán)看來，版本2平均執(zhí)行次數(shù)比版本1要少，因?yàn)榭梢约僭O(shè)預(yù)測(cè)錯(cuò)誤的概率是50%。 HYPERLINK :/ 深入理解計(jì)算機(jī)系統(tǒng)(第二版) 家庭作業(yè) 第五章 5.15A.關(guān)鍵路徑是%xmm1更新路徑上的加法。B. CPE下界是浮點(diǎn)加法的延遲。C. 兩個(gè)load操作的吞吐量界限。（我覺得是2.00）D. 因?yàn)槌朔ú辉陉P(guān)鍵路徑上，乘法也是流水線執(zhí)行的，其限制因素為吞吐量界限。整個(gè)程序的限制因素為最后的浮點(diǎn)數(shù)加法的延遲，這個(gè)延遲對(duì)float和double都是3.00。書上之前說

51、關(guān)鍵路徑，現(xiàn)在其實(shí)可以再仔細(xì)分析一下(以下屬于個(gè)人分析)：把執(zhí)行指令寫出了就明了了。以整數(shù)為例：一樣底色表示這些指令在一個(gè)循環(huán)執(zhí)行，以與同一個(gè)循環(huán)的初始值：所以我覺得整數(shù)的時(shí)候CPE是2.00，可是為什么是3.00呢？浮點(diǎn)數(shù)的話，延遲是3.00沒問題。時(shí)間線xmm1_add單元xmm1mul單元發(fā)射load單元發(fā)射rdx_add單元rdx的值10load1add+020load2+13load1add+14load2+25load1add+26mul(load延遲4)load2.7.80mul9add整數(shù)mul延遲為3010added整數(shù)加法延遲為1mul11add12added5.16voi

52、dinner4(vec_ptr u,vec_ptr v,data_t*dest)longinti;intlength =vec_length(u);data_t*udata =get_vec_start(u);data_t*vdata =get_vec_start(v);data_t sum =(data_t)0;intlimit = length-2;for(i =0;ilimit;i+)sum = sum+udatai*vdatai;sum = sum+udatai+1*vdatai+1;sum = sum+udatai+2*vdatai+2;for(;ilength;+i)sum = s

53、um+udatai*vdatai;*dest = sum;A. 因?yàn)閘oad吞吐量為1.00，每計(jì)算一個(gè)值需要兩次load，所以CPE不可能低于2.00。B. 關(guān)鍵路徑上仍然有N個(gè)浮點(diǎn)加法，所以循環(huán)展開并沒有改變5.17A. load執(zhí)行單元的吞吐量B. IA32可用寄存器實(shí)際只有6個(gè)，而三路展開需要i, limit, udata, vdata，以與存儲(chǔ)udatai, vdatai的寄存器，所以肯定有些循環(huán)變量會(huì)溢出到寄存器，這會(huì)影響效率。（至于為什么是2.67以與為什么四路展開的整數(shù)會(huì)是2.33，還不是很清楚）。5.18voidinner4(vec_ptr u,vec_ptr v,data_

54、t*dest)longinti;intlength =vec_length(u);data_t*udata =get_vec_start(u);data_t*vdata =get_vec_start(v);data_t sum =(data_t)0;intlimit = length-2;for(i =0;ilimit;i+)intx1 = udatai*vdatai;intx2 = udatai+1*vdatai+1;intx3 = udatai+2*vdatai+2;sum = sum+(x1+x2+x3);for(;ilength;+i)sum = sum+udatai*vdatai;*

55、dest = sum;5.19void*optimized_memset(void*s,intc,size_t n)unsignedintK =sizeof(unsignedlong);unsignedchar*schar =(unsignedchar*)s;unsignedlong*lchar;unsignedlongfill =0;inti =0;for(i =0;iK;i+)fill+=(c&0 xff)(i= K)*lchar+= fill;n-= K;/不知道這里如果用+和-會(huì)不會(huì)影響整體的效率schar =(unsignedchar*)lchar;while(n)/剩余的n*sch

56、ar+=(unsignedchar)c;-n;returns;5.20doublepoly_optimized(doublea,doublex,intdegree)longinti;doubleresult =0;doubles =0,powx4 =1;doublex2 = x*x;doublex4 = x2*x2;longintlimit = degree-3;for(i =0;i= limit;i+=4)doublev1 = ai+ai+1*x;doublev2 = ai+2+ai+3*x;v1 = v1+v2*x2;s = s+v1*powx4;powx4*= x4;for(;i= de

57、gree;+i)s+= ai*powx4;powx4*= x;returns;關(guān)鍵路徑就是一個(gè)浮點(diǎn)數(shù)乘法，因此CPE是浮點(diǎn)乘法延遲的1/4，然而每次計(jì)算都需要load 4個(gè)值，所以CPE還是1.00。5.21voidpsum(floata,floatp,longintn)longinti;intv = 0;for(i=0;in-1;i+=2)intv1 = ai;intv2 = ai+1;v2 = v1+v2;pi= v + v1;pi+1= v + v2; v = v+v2;for(;in;i+)v = v+ai;pi= v;5.22假設(shè)最開始需要100T的時(shí)間，那么A需要20T，B需要30

58、T，C需要50T。將B提到3倍，也就是B需要10T，那么總時(shí)間為80T。將C提到1.5倍，也就是C需要33.3T，那么總時(shí)間為83.3T。所以提高B會(huì)使得性能更優(yōu)。 HYPERLINK :/ 深入理解計(jì)算機(jī)系統(tǒng)(第二版) 家庭作業(yè) 第六章 6.23我們可以認(rèn)為，磁道沿半徑方向是均勻分布的。假設(shè)半徑為r的磁盤總的磁道是K，那么除掉部的x*r（磁道數(shù)為x*K），剩下的磁道數(shù)為 (1-x)*K。那么總?cè)萘繛?2*pi*x*r*(1-x)*K，其中pi，r和K都是常數(shù)，那么只剩下x*(1-x)。這個(gè)函數(shù)在x = 0.5的時(shí)候取最大。6.24T_seek =3 msT_maxrotate = 60*10

59、00/12000 ms = 5 msT_avgrotate = 0.5*T_maxrotate =2.5 msT_transfer = T_maxrotate/500 =0.01 msT = T_seek + T_avgrotate + T_transfer = 5.51 ms6.253MB文件，我們假設(shè)1MB = 1000KB，而1KB = 1024B（這個(gè)好算一些）。那么3MB文件就有3000個(gè)邏輯塊（扇區(qū)），需要讀6個(gè)磁道。T_maxrotate = 5 msT_transfer = 0.01 msA.最好情況是6個(gè)磁道都在一個(gè)柱面上，只需要尋一次道，而且文件是順序存儲(chǔ)。T = T_seek + 0.5*T_maxrotate + 6*T_maxrotate = 35.5msB. 最差的情況 3000*(T_seek + 0.5*T_maxroate + T_transfer) = 16530ms6.26高速緩存mCBEStsb1322048441282372232204845121300233220488125621834322048812822813532204832164216563220483241623456.27高速緩存mCBEStsb1328192161512199423240964425622823324096481282372432204832416224