陳智勇 唐成華 張瑞霞 秦董洪

摘要：針對(duì)計(jì)算機(jī)專業(yè)學(xué)生對(duì)程序設(shè)計(jì)感興趣的特點(diǎn)，從程序設(shè)計(jì)與問題求解課程中的某些知識(shí)點(diǎn)入手，闡述在計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程教學(xué)過程中采用的基于程序設(shè)計(jì)的啟發(fā)式教學(xué)方法。

關(guān)鍵詞：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)；教學(xué)方法；程序設(shè)計(jì)

0、引言

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生的一門專業(yè)基礎(chǔ)必修課，它主要圍繞計(jì)算機(jī)系統(tǒng)的軟硬件功能分配及各功能部件的優(yōu)化技術(shù)和量化分析方法，將計(jì)算機(jī)組成原理、操作系統(tǒng)、編譯原理、程序設(shè)計(jì)與問題求解等課程所學(xué)的軟硬件知識(shí)有機(jī)地結(jié)合起來，從而建立計(jì)算機(jī)系統(tǒng)的完整概念。學(xué)習(xí)本課程旨在使學(xué)生從總體結(jié)構(gòu)、系統(tǒng)分析的角度來理解和研究計(jì)算機(jī)系統(tǒng)，學(xué)習(xí)如何根據(jù)各種實(shí)際應(yīng)用的需要，綜合考慮軟硬件功能分配，設(shè)計(jì)和構(gòu)建合理的計(jì)算機(jī)系統(tǒng)，以及在一個(gè)已知的計(jì)算機(jī)系統(tǒng)上開發(fā)出高效的應(yīng)用程序、編譯器或操作系統(tǒng)，對(duì)于培養(yǎng)學(xué)生系統(tǒng)分析和解決問題的能力、抽象思維能力都有非常重要的作用。

1、啟發(fā)式教學(xué)方法

啟發(fā)式教學(xué)是指教師在教學(xué)過程中，根據(jù)教學(xué)任務(wù)和學(xué)習(xí)的客觀規(guī)律，從學(xué)生的實(shí)際出發(fā)，采用多種方式，以啟發(fā)學(xué)生的思維為核心，調(diào)動(dòng)其學(xué)習(xí)主動(dòng)性和積極性的一種教學(xué)方式。

在計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程的教學(xué)過程中，教師先給學(xué)生設(shè)置懸念，比如針對(duì)某一計(jì)算機(jī)技術(shù)的理論分析和量化研究，得出的結(jié)論與現(xiàn)代計(jì)算機(jī)采用的先進(jìn)技術(shù)不一致，然后再討論需要講解的內(nèi)容，從而提高學(xué)生的學(xué)習(xí)興趣。

比如，計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程中，教師在講授超標(biāo)量超流水線時(shí)，若假設(shè)基準(zhǔn)流水線的級(jí)數(shù)為k，超標(biāo)量發(fā)射度為m，超流水處理器為n倍頻，在不發(fā)生任何數(shù)據(jù)相關(guān)、控制相關(guān)和資源相關(guān)的前提下，共解釋N條指令，當(dāng)N趨于無窮大時(shí)，超標(biāo)量超流水線相對(duì)于基準(zhǔn)流水線的加速比為Sn=m.n。即微處理器的超標(biāo)量發(fā)射度m越大，則加速比越大，流水線的級(jí)數(shù)越多，則加速比越大。我們的提問是：①以前從Pentium Pro到P4微處理器的超標(biāo)量發(fā)射度一直為3，個(gè)人計(jì)算機(jī)使用的Core微處理器的超標(biāo)量發(fā)射度也只為4，為什么個(gè)人計(jì)算機(jī)的超標(biāo)量發(fā)射度沒有設(shè)計(jì)為8或16呢？②以前Pentium微處理器的指令流水線為5級(jí)，到P4時(shí)達(dá)到20級(jí)（實(shí)際可能會(huì)大于20級(jí)），而個(gè)人計(jì)算機(jī)使用的Core微處理器的有效流水線級(jí)數(shù)為什么卻只有14級(jí)呢？學(xué)生通過查閱參考書和網(wǎng)上資料，從硬件的復(fù)雜性、利用率、時(shí)鐘技術(shù)、功耗和實(shí)現(xiàn)成本，應(yīng)用程序的指令級(jí)并行性和編譯技術(shù)的實(shí)現(xiàn)難度等多個(gè)方面，對(duì)理淪分析的結(jié)果與現(xiàn)代微處理器設(shè)計(jì)采用技術(shù)的不一致性進(jìn)行解釋。

2、基于程序設(shè)計(jì)的啟發(fā)式教學(xué)方法

基于程序設(shè)計(jì)的啟發(fā)式教學(xué)方法是以學(xué)生熟悉的程序設(shè)計(jì)算法為例，先從計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的角度指出“本科低年級(jí)程序設(shè)計(jì)算法中存在的不足，然后再討論面向不同的計(jì)算機(jī)系統(tǒng)如何去解決問題；在解決問題的過程中，將涉及的知識(shí)逐步展開，討論與計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)相關(guān)的理論知識(shí)。

2.1累加求和算法

在學(xué)習(xí)程序設(shè)計(jì)與問題求解課程時(shí)，若計(jì)算 s=∑A[i]，其c語言描述的核心代碼如程序1所示。

【程序1】s=0；

for（i=l；i=256；i++）

s=s十A[i]；

學(xué)過計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程后，我們會(huì)知道程序1的循環(huán)體內(nèi)存在關(guān)于變量s的先寫后讀數(shù)據(jù)相關(guān)。由于現(xiàn)代微處理器設(shè)計(jì)采用了超流水線技術(shù)，程序l的編程方法會(huì)大大降低流水線解釋的效率。要改進(jìn)程序l，必須學(xué)習(xí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程的以下知識(shí)：什么叫數(shù)據(jù)相關(guān)，什么叫超流水線，為什么先寫后讀數(shù)據(jù)相關(guān)會(huì)影響流水解釋的速度，在計(jì)算機(jī)系統(tǒng)硬件設(shè)計(jì)和軟件設(shè)計(jì)過程中如何消除數(shù)據(jù)相關(guān)？在提出問題后，教師逐一講解相應(yīng)的理論知識(shí)，然后從學(xué)生感興趣的程序設(shè)計(jì)的角度介紹程序1的改進(jìn)方法，這里采用了遞歸折疊技術(shù)，如程序2所示。

【程序2】len=128；

for（i=1；i<=8；i++）

{

for（j=l；j<=len：j++）

A[j]=A[j]+A[j+len]；

len=len/2；

}

s=A[1]；

有同學(xué)說程序1的時(shí)間復(fù)雜度為O（n），程序2的時(shí)間復(fù)雜度為O（n2），那是針對(duì)傳統(tǒng)馮.諾依曼計(jì)算機(jī)而言的，我們學(xué)習(xí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程的目的就是讓學(xué)生逐步轉(zhuǎn)變觀念，學(xué)會(huì)面向計(jì)算機(jī)體系結(jié)構(gòu)的編程方法j在程序l中，循環(huán)體串行執(zhí)行了256次，由于現(xiàn)代微處理器采用了超流水線技術(shù)，且運(yùn)算器設(shè)計(jì)采用了相關(guān)專用通路，流水解釋指令時(shí)在時(shí)間上各指令之間盡管有部分重疊，即并非絕對(duì)地串行，但由于連續(xù)兩次迭代間存在關(guān)于s的先寫后讀數(shù)據(jù)相關(guān)，會(huì)造成流水線性能的下降。在程序2中的內(nèi)循環(huán)中，由于連續(xù)兩次迭代間不存在關(guān)于A[i]的先寫后讀數(shù)據(jù)相關(guān)，故可連續(xù)地流水解釋指令，只有外循環(huán)對(duì)應(yīng)的循環(huán)體串行執(zhí)行了8次（在流水解釋指令時(shí)也并非絕對(duì)地串行）。數(shù)組分量的個(gè)數(shù)越多，程序2執(zhí)行的時(shí)間就越短。

2.2計(jì)算點(diǎn)積算法

在學(xué)習(xí)程序設(shè)計(jì)與問題求解課程時(shí)，若計(jì)算s=∑A[i]*B[i]，其c語言描述的核心代碼如程序3所示。

【程序3】s=0；

for（i=l；i=256；i++）

s=s+A[i]*B[i]；

由程序1和程序2可知，程序3的連續(xù)兩次迭代間存在關(guān)于s的先寫后讀數(shù)據(jù)相關(guān)，同時(shí)在計(jì)算s=s+A[i]*B[i]時(shí)，若A[i]*B[i]的結(jié)果不生成，則無法進(jìn)行加法運(yùn)算。因?yàn)楝F(xiàn)代微處理器采用超流水線技術(shù)，乘法指令的執(zhí)行需要多個(gè)時(shí)鐘周期，在執(zhí)行循環(huán)體時(shí)，會(huì)頻繁地進(jìn)行乘法和加法的功能切換，按程序3編程，會(huì)大大降低指令流水解釋的速度。要改進(jìn)程序3，必須學(xué)習(xí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程的以下知識(shí)：什么叫多功能流水線，什么叫先寫后讀數(shù)據(jù)相關(guān)，為什么頻繁的功能切換會(huì)影響流水解釋的速度，在計(jì)算機(jī)系統(tǒng)硬件設(shè)計(jì)和軟件設(shè)計(jì)過程中如何消除數(shù)據(jù)相關(guān)，用戶編程時(shí)如何考慮應(yīng)用程序的并行性？在提出問題后，逐一講解相應(yīng)的理論知識(shí)，然后從學(xué)生感興趣的程序設(shè)計(jì)的角度介紹程序3的改進(jìn)方法。解決方法是先將程序變?yōu)榭上蛄炕糠趾蜌w約求和部分，再將歸約求和部分采用程序2所示的遞歸折疊技術(shù)，來加速求和操作，如程序4所示。

【程序4】for（i=l；i=256；j++）/可向量化部分/

C[i]=A[i]*B[i]；

len=128；/歸約求和部分/

for（i=l；i<=8；i++）

{

for（j=l；j<=len：j++）

C[j]=C[j]+C[j+len]；

len=len/2；

}

s=C[1]；

若微處理器為單核單發(fā)射超流水微處理器，由于可向量化部分的每條乘法指令之間不存在數(shù)據(jù)相關(guān)，盡管處理器在每個(gè)時(shí)鐘周期只發(fā)射一條乘法指令，但在一個(gè)指令周期內(nèi)可并發(fā)解釋多條指令；若微處理器為單核多發(fā)射超標(biāo)量超流水處理器，則按程序4的編程方法，處理器可在每個(gè)時(shí)鐘周期同時(shí)發(fā)射多條指令，即在一個(gè)指令周期內(nèi)并發(fā)解釋的指令數(shù)可成倍增加。對(duì)于現(xiàn)代微處理器，均采用了超標(biāo)量超流水技術(shù)，程序4的編程方法將大大提高程序的執(zhí)行速度。

若微處理器為共享L3 Cache的同構(gòu)多核處理器，如Core i7，同時(shí)采用多個(gè)計(jì)算引擎進(jìn)行并行處理，用戶在編程時(shí)需根據(jù)計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)，考慮如何用顯式的語句說明程序的并行性特征，以便編譯器對(duì)應(yīng)用程序編譯后，能生成在特定計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)中運(yùn)行的高效的目標(biāo)代碼；若用戶用順序的程序設(shè)計(jì)語言編程，作為編譯器設(shè)計(jì)者還需考慮如何將順序代碼轉(zhuǎn)換成面向計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的并行代碼；為提高程序的執(zhí)行速度，操作系統(tǒng)還需進(jìn)一步考慮如何進(jìn)行任務(wù)調(diào)度和負(fù)載平衡等。若一個(gè)大型任務(wù)在分布式共享主存的多機(jī)系統(tǒng)中運(yùn)行，任務(wù)調(diào)度和負(fù)載平衡需綜合考慮計(jì)算時(shí)間、并行性開銷、交互開銷，以及多機(jī)系統(tǒng)采用的互聯(lián)網(wǎng)絡(luò)、時(shí)延容忍技術(shù)等多個(gè)方面，情況會(huì)更加復(fù)雜。

從這個(gè)例子可以看出，作為計(jì)算機(jī)專業(yè)的學(xué)生，不僅要學(xué)會(huì)編寫應(yīng)用程序，而且還需要了解計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)，使編寫出來的應(yīng)用程序能在特定的計(jì)算機(jī)系統(tǒng)上高效運(yùn)行，同時(shí)還需掌握并行編程、并行算法、編譯技術(shù)、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)等多方面的知識(shí)。

2.3矩陣乘算法

在學(xué)習(xí)程序設(shè)計(jì)與問題求解課程時(shí)，若計(jì)算兩個(gè)n×n的矩陣相乘，即C=AxB，其C語言描述的核心代碼如程序5所示。

【程序5】for（i_l；i<=n；i++）

fr（j=l；j<=n；j++）

for（k=l；k<=n；k++）

C[iJ]=C[ij]+A[i，k]*B[kj]；

因?yàn)榫仃囋卦诖鎯?chǔ)空間的存放順序是按行主順序排列，按照程序5所示的矩陣乘算法，內(nèi)循環(huán)中的A[i，k]具有空間局部性，而B[k，j]不具有空間局部性。也就是說，當(dāng)n的值較大時(shí)，對(duì)B[k，j]的訪問每次都會(huì)出現(xiàn)Cache不命中，從而降低程序的執(zhí)行速度，因此我們?cè)诰帉懢仃嚦怂惴〞r(shí)，要考慮的第一個(gè)問題是：如何修改程序，才能提高程序執(zhí)行過程中CPU訪問Cache的命中率？要解決這個(gè)問題必須學(xué)習(xí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程的以下知識(shí)：什么叫程序的局部性、什么叫Cache的命中率、存儲(chǔ)體系的結(jié)構(gòu)，增強(qiáng)程序的局部性為什么可以提高Cache的命中率，用戶編程時(shí)和操作系統(tǒng)調(diào)度時(shí)如何考慮程序的局部性等。

在程序5中，由于語句“C[i，j]=C[i，j]]+A[i，k]*B[k，j]；"編譯后會(huì)生成兩條目標(biāo)代碼，相當(dāng)于“x-A[i，k]*B[k，j]；”和“C[i，j]=C[i，j]+x；”，這兩條語句之間存在關(guān)于x的先寫后讀數(shù)據(jù)相關(guān)。在第三層循環(huán)迭代中還會(huì)頻繁出現(xiàn)關(guān)于C[i，j]的先寫后讀數(shù)據(jù)相關(guān)，由于現(xiàn)代微處理器設(shè)計(jì)時(shí)均采用了超流水線技術(shù)，存在的數(shù)據(jù)相關(guān)會(huì)大大降低流水線的效率，因此要考慮的第二個(gè)問題是：如何修改程序，才能消除程序中的數(shù)據(jù)相關(guān)？

如果用戶編程時(shí)采用熟悉的通用算法進(jìn)行矩陣乘的應(yīng)用程序設(shè)計(jì)，如程序5，那么對(duì)于編譯器而言，如何解決上述兩個(gè)問題？

復(fù)習(xí)C語言程序設(shè)計(jì)課程中二維數(shù)組的定義、計(jì)算機(jī)組成原理和匯編語言程序設(shè)計(jì)課程中數(shù)組在Cache和主存空間的存放位置，在展開介紹了計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程中有關(guān)Cache地址和主存地址格式設(shè)計(jì)、Cache的地址映像與變換、替換算法、調(diào)度算法等知識(shí)后，那么如何從程序設(shè)計(jì)者的角度解決第一個(gè)問題？具體方法是將程序5中的語句“fOr（j=1；j<=n；j++）”與“for（k=1；k<=n；k++）”位置對(duì)調(diào)，對(duì)調(diào)后程序執(zhí)行過程中的數(shù)據(jù)訪問和Cache命中率的提高留給學(xué)生自己分析；解決第二個(gè)問題的方法可參考程序4進(jìn)行編程。

從這個(gè)例子可以看出，作為一個(gè)計(jì)算機(jī)專業(yè)的學(xué)生，進(jìn)行一個(gè)簡(jiǎn)單的程序設(shè)計(jì)，不僅要懂得程序設(shè)計(jì)的知識(shí)，還要掌握匯編語言程序設(shè)計(jì)、計(jì)算機(jī)組成原理、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、編譯原理等課程的相關(guān)知識(shí)，才能真正設(shè)計(jì)或編譯出一個(gè)面向計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的能高效執(zhí)行的高級(jí)語言源程序或目標(biāo)程序。

3、結(jié)語

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程涉及的專業(yè)知識(shí)面廣、內(nèi)容抽象，但我們通過采用啟發(fā)式教學(xué)方法，特別是采用基于程序設(shè)計(jì)的啟發(fā)式教學(xué)方法，從學(xué)生感興趣的程序設(shè)計(jì)與問題求解入手，以舉例的方式，引導(dǎo)學(xué)生從面向傳統(tǒng)馮·諾依曼體系結(jié)構(gòu)計(jì)算機(jī)的編程思想，逐步過渡到面向現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)的編程思想。在解決問題的過程中，教師將涉及的知識(shí)逐步展開，討論與計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課程相關(guān)的理論知識(shí)，以及該課程與計(jì)算機(jī)專業(yè)其他專業(yè)基礎(chǔ)課程之間的關(guān)系；讓學(xué)生知道只有學(xué)好計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)這門課程，才能編寫出更加高效的應(yīng)用程序和系統(tǒng)軟件實(shí)踐證明，該教學(xué)方法的應(yīng)用，不僅激發(fā)了學(xué)生的學(xué)習(xí)興趣，也讓學(xué)生認(rèn)識(shí)到了學(xué)習(xí)專業(yè)基礎(chǔ)課程的重要性。