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

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

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

0、引言

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

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

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

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

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

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

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

2.1累加求和算法

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

【程序1】s=0；

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

s=s十A[i]；

學(xué)過計算機系統(tǒng)結(jié)構(gòu)課程后，我們會知道程序1的循環(huán)體內(nèi)存在關(guān)于變量s的先寫后讀數(shù)據(jù)相關(guān)。由于現(xiàn)代微處理器設(shè)計采用了超流水線技術(shù)，程序l的編程方法會大大降低流水線解釋的效率。要改進程序l，必須學(xué)習(xí)計算機系統(tǒng)結(jié)構(gòu)課程的以下知識：什么叫數(shù)據(jù)相關(guān)，什么叫超流水線，為什么先寫后讀數(shù)據(jù)相關(guān)會影響流水解釋的速度，在計算機系統(tǒng)硬件設(shè)計和軟件設(shè)計過程中如何消除數(shù)據(jù)相關(guān)？在提出問題后，教師逐一講解相應(yīng)的理論知識，然后從學(xué)生感興趣的程序設(shè)計的角度介紹程序1的改進方法，這里采用了遞歸折疊技術(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的時間復(fù)雜度為O（n），程序2的時間復(fù)雜度為O（n2），那是針對傳統(tǒng)馮.諾依曼計算機而言的，我們學(xué)習(xí)計算機系統(tǒng)結(jié)構(gòu)課程的目的就是讓學(xué)生逐步轉(zhuǎn)變觀念，學(xué)會面向計算機體系結(jié)構(gòu)的編程方法j在程序l中，循環(huán)體串行執(zhí)行了256次，由于現(xiàn)代微處理器采用了超流水線技術(shù)，且運算器設(shè)計采用了相關(guān)專用通路，流水解釋指令時在時間上各指令之間盡管有部分重疊，即并非絕對地串行，但由于連續(xù)兩次迭代間存在關(guān)于s的先寫后讀數(shù)據(jù)相關(guān)，會造成流水線性能的下降。在程序2中的內(nèi)循環(huán)中，由于連續(xù)兩次迭代間不存在關(guān)于A[i]的先寫后讀數(shù)據(jù)相關(guān)，故可連續(xù)地流水解釋指令，只有外循環(huán)對應(yīng)的循環(huán)體串行執(zhí)行了8次（在流水解釋指令時也并非絕對地串行）。數(shù)組分量的個數(shù)越多，程序2執(zhí)行的時間就越短。

2.2計算點積算法

在學(xué)習(xí)程序設(shè)計與問題求解課程時，若計算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)，同時在計算s=s+A[i]*B[i]時，若A[i]*B[i]的結(jié)果不生成，則無法進行加法運算。因為現(xiàn)代微處理器采用超流水線技術(shù)，乘法指令的執(zhí)行需要多個時鐘周期，在執(zhí)行循環(huán)體時，會頻繁地進行乘法和加法的功能切換，按程序3編程，會大大降低指令流水解釋的速度。要改進程序3，必須學(xué)習(xí)計算機系統(tǒng)結(jié)構(gòu)課程的以下知識：什么叫多功能流水線，什么叫先寫后讀數(shù)據(jù)相關(guān)，為什么頻繁的功能切換會影響流水解釋的速度，在計算機系統(tǒng)硬件設(shè)計和軟件設(shè)計過程中如何消除數(shù)據(jù)相關(guān)，用戶編程時如何考慮應(yīng)用程序的并行性？在提出問題后，逐一講解相應(yīng)的理論知識，然后從學(xué)生感興趣的程序設(shè)計的角度介紹程序3的改進方法。解決方法是先將程序變?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)，盡管處理器在每個時鐘周期只發(fā)射一條乘法指令，但在一個指令周期內(nèi)可并發(fā)解釋多條指令；若微處理器為單核多發(fā)射超標(biāo)量超流水處理器，則按程序4的編程方法，處理器可在每個時鐘周期同時發(fā)射多條指令，即在一個指令周期內(nèi)并發(fā)解釋的指令數(shù)可成倍增加。對于現(xiàn)代微處理器，均采用了超標(biāo)量超流水技術(shù)，程序4的編程方法將大大提高程序的執(zhí)行速度。

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

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

2.3矩陣乘算法

在學(xué)習(xí)程序設(shè)計與問題求解課程時，若計算兩個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]；

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

在程序5中，由于語句“C[i，j]=C[i，j]]+A[i，k]*B[k，j]；"編譯后會生成兩條目標(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)迭代中還會頻繁出現(xiàn)關(guān)于C[i，j]的先寫后讀數(shù)據(jù)相關(guān)，由于現(xiàn)代微處理器設(shè)計時均采用了超流水線技術(shù)，存在的數(shù)據(jù)相關(guān)會大大降低流水線的效率，因此要考慮的第二個問題是：如何修改程序，才能消除程序中的數(shù)據(jù)相關(guān)？

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

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

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

3、結(jié)語

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