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

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

關鍵詞：計算機系統(tǒng)結構；教學方法；程序設計

0、引言

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

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

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

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

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

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

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

2.1累加求和算法

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

【程序1】s=0；

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

s=s十A[i]；

學過計算機系統(tǒng)結構課程后，我們會知道程序1的循環(huán)體內存在關于變量s的先寫后讀數據相關。由于現代微處理器設計采用了超流水線技術，程序l的編程方法會大大降低流水線解釋的效率。要改進程序l，必須學習計算機系統(tǒng)結構課程的以下知識：什么叫數據相關，什么叫超流水線，為什么先寫后讀數據相關會影響流水解釋的速度，在計算機系統(tǒng)硬件設計和軟件設計過程中如何消除數據相關？在提出問題后，教師逐一講解相應的理論知識，然后從學生感興趣的程序設計的角度介紹程序1的改進方法，這里采用了遞歸折疊技術，如程序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]；

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

2.2計算點積算法

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

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

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

2.3矩陣乘算法

在學習程序設計與問題求解課程時，若計算兩個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所示的矩陣乘算法，內循環(huán)中的A[i，k]具有空間局部性，而B[k，j]不具有空間局部性。也就是說，當n的值較大時，對B[k，j]的訪問每次都會出現Cache不命中，從而降低程序的執(zhí)行速度，因此我們在編寫矩陣乘算法時，要考慮的第一個問題是：如何修改程序，才能提高程序執(zhí)行過程中CPU訪問Cache的命中率？要解決這個問題必須學習計算機系統(tǒng)結構課程的以下知識：什么叫程序的局部性、什么叫Cache的命中率、存儲體系的結構，增強程序的局部性為什么可以提高Cache的命中率，用戶編程時和操作系統(tǒng)調度時如何考慮程序的局部性等。

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

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

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

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

3、結語

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