馮.諾依曼計算機-機器級程序及其執(zhí)行

1、第3講 馮.諾依曼計算機：機器級程序及其執(zhí)行,理解“程序和數(shù)據(jù)如何被存儲、如何被執(zhí)行的”，有助于構(gòu)造和設(shè)計可執(zhí)行的算法和程序，有助于復雜環(huán)境下程序執(zhí)行機制的理解,基本目標: 理解程序及其硬件實現(xiàn)思維,基本思維：機器級算法與程序機器指令與指令系統(tǒng)存儲器存儲程序運算器與控制器機器級程序的執(zhí)行；算法程序化程序指令化指令存儲化執(zhí)行信號化,內(nèi)容提要,圖靈機的思想與模型簡介 -圖靈的貢獻 -圖靈機：計算機的理論模型 -指令、數(shù)據(jù)、程序與程序執(zhí)行,馮.諾依曼計算機：機器級程序及其執(zhí)行 2.2.1 圖靈機的思想與模型簡介,圖靈及其貢獻,圖靈(alan turing, 19121954)，出生于英國倫敦，19

2、歲入劍橋皇家學院，22 歲當選為皇家學會會員。 1937 年，發(fā)表了論文論可計算數(shù)及其在判定問題中的應用，提出了圖靈機模型，后來，馮諾依曼根據(jù)這個模型設(shè)計出歷史上第一臺電子計算機。 1950 年，發(fā)表了劃時代的文章：機器能思考嗎?,成為了人工智能的開山之作。 計算機界于1966年設(shè)立了最高榮譽獎：acm 圖靈獎,圖靈是誰,你能查閱一下哪些人獲得圖靈獎了嗎？因為什么貢獻而獲獎呢,所謂計算就是計算者(人或機器)對一條兩端可無限延長的紙帶上的一串0或1，執(zhí)行指令一步一步地改變紙帶上的0或1，經(jīng)過有限步驟最后得到一個滿足預先規(guī)定的符號串的變換過程,計算,10001110110,0110101,1000

3、1,0110101,由“程序”控制，一步步將輸入“轉(zhuǎn)換”為輸出,輸入,輸出,程序,通用機器,圖靈認為什么是計算,圖靈機的思想 是關(guān)于數(shù)據(jù)、指令、程序及程序/指令自動執(zhí)行的基本思想。 輸入被制成一串0和1的紙帶，送入機器中-數(shù)據(jù)。如00010000100011 機器可對輸入紙帶執(zhí)行的基本動作包括：“翻轉(zhuǎn)0為1”，或 “翻轉(zhuǎn)1為0”, “前移一位”, “停止”。 對基本動作的控制-指令，機器是按照指令的控制選擇執(zhí)行哪一個動作，指令也可以用0和1來表示：01表示“翻轉(zhuǎn)0為1”(當輸入為1時不變)，10表示“翻轉(zhuǎn)1為0”(當輸入0時不變), 11表示“前移一位”, 00表示“停止”。 輸入如何變?yōu)檩敵?/p>

4、的控制可以用指令編寫一個程序來完成, 如: 011110110111011100 機器能夠讀取程序，按程序中的指令順序讀取指令， 讀一條指令執(zhí)行一條指令。由此實現(xiàn)自動計算,基本的圖靈機模型為一個七元組,如右圖示意 幾點結(jié)論: (1) 圖靈機是一種思想模型，它由一個控制器(有限狀態(tài)轉(zhuǎn)換器)，一條可無限延伸的帶子和一個在帶子上左右移動的讀寫頭構(gòu)成。 (2) 程序是五元組形式的指令集。其定義了機器在一個特定狀態(tài)q下從方格中讀入一個特定字符x時所采取的動作為在該方格中寫入符號y, 然后向右移一格r (或向左移一格l或不移動n), 同時將機器狀態(tài)設(shè)為p供下一條指令使用,圖靈機是什么,圖靈機模型,圖靈機模

5、型示例。 (注:圓圈內(nèi)的是狀態(tài)，箭線上的是，其含義見前頁,執(zhí)行過程,功能：將一串1的后面再加一位1,控制器,s1,s2,s3,s4,1,1,r,1,1,r,0,1,l,1,1,l,0,0,n,s1：開始狀態(tài) s2：右移狀態(tài) s3：左移狀態(tài) s4：停機狀態(tài),0,0,r,s1,0,0,r,s1,s1,1,1,r,s2,s2,1,1,r,s2,s2,0,1,l,s3,s3,1,1,l,s3,s3,0,0,n,s4,幾點結(jié)論(續(xù)): (3)圖靈機模型被認為是計算機的基本理論模型 -計算機是使用相應的程序來完成任何設(shè)定好的任務(wù)。圖靈機是一種離散的、有窮的、構(gòu)造性的問題求解思路，一個問題的求解可以通過構(gòu)造

6、其圖靈機(即程序)來解決。 (4)圖靈認為：凡是能用算法方法解決的問題也一定能用圖靈機解決; 凡是圖靈機解決不了的問題任何算法也解決不了-圖靈可計算性問題,馮.諾依曼計算機: 思想與構(gòu)成 -存儲程序原理 -馮.諾依曼計算機的構(gòu)成,馮.諾依曼計算機：機器級程序及其執(zhí)行 2. 2. 2 馮.諾依曼計算機: 思想與構(gòu)成,19441945年間，馮.諾伊曼提出 “存儲程序”的計算機設(shè)計思想，并進行了實踐，現(xiàn)代計算機普遍來講屬于馮.諾伊曼機體系。 馮.諾伊曼機的基本思想： 運算和存儲分離 存儲程序：指令和數(shù)據(jù)以同等地位事先存于存儲器, 可按地址尋訪, 連續(xù)自動執(zhí)行。 五大部件構(gòu)成：運算器、控制器、存儲器、

7、輸入設(shè)備和輸出設(shè)備 指令和數(shù)據(jù)用二進制表示，指令由操作碼和地址碼組成 以運算器為中心，控制器負責解釋指令，運算器負責執(zhí)行指令,什么是馮.諾依曼計算機,馮.諾依曼(von.neumann)計算機,以運算器為中心的馮.諾依曼計算機構(gòu)成圖,馮.諾依曼計算機的結(jié)構(gòu)是怎樣的? 部件有哪些? 部件的關(guān)系怎樣,以存儲器為中心的現(xiàn)代計算機構(gòu)成圖,存儲器為中心與運算器為中心相比的優(yōu)點在哪里,同樣是五個部件，以不同的結(jié)構(gòu)來連接，便體現(xiàn)了不同的性能-這就是“系統(tǒng)”：強調(diào)“結(jié)構(gòu)”，強調(diào)部件連接后的整體性、協(xié)同性,運算器,存儲器,控制臺,控制器,1)啟動控制器工作,2)發(fā)送第1條指令地址,3)取出指令并分析指令,4)執(zhí)

8、行指令：發(fā)送操作數(shù)x所在地址,5)執(zhí)行指令：取出操作數(shù)x,10)執(zhí)行指令：通知運算器計算a乘x,11)繼續(xù)后續(xù)指令的取指、執(zhí)行,6)發(fā)送下一條指令地址,7)取出指令并分析指令,8)執(zhí)行指令：發(fā)送操作數(shù)a所在地址,9)執(zhí)行指令：取出操作數(shù)a,馮.諾依曼計算機的工作原理是怎樣的,工作原理,計算機的基本部件 cpu：中央處理單元(central process unit)，將運算器和控制器集成在一塊芯片上，形成微處理器。 cpu、主存儲器、i/o設(shè)備及總線成為現(xiàn)代計算機的四大核心部件,總線,什么是cpu? 現(xiàn)代計算機的幾大部件是什么,現(xiàn)代計算機里面，一個微處理器(芯片)可能包含多個cpu，即多核,自

9、動存?。捍鎯ζ鞯墓ぷ髟?-存儲器的自動讀寫,馮.諾依曼計算機：機器級程序及其執(zhí)行 2.2.3 自動存取：存儲器的工作原理,存儲器的基本結(jié)構(gòu),存儲器電路結(jié)構(gòu)概念圖,什么是存儲器,概念映射,從存儲器與宿舍樓的概念對比中，你能發(fā)現(xiàn)什么異同嗎,存儲器內(nèi)部的實現(xiàn)示例 當?shù)刂肪€和數(shù)據(jù)線間連接有二極管時，則存儲的是1，否則，存儲的是0 當?shù)刂肪€和數(shù)據(jù)線間連接有二極管時，由地址線決定其是輸出1或0，即：當?shù)刂肪€為高電平時，則輸出1，而當?shù)刂肪€為低電平時，則輸出0； 沒有連接的，則不受地址線影響，始終輸出低電平0,二極管rom結(jié)構(gòu)示例 (2位地址控制4個信息單元, 每個信息單元是4位0/1碼,存儲器是怎樣存儲

10、0和1的? 又是怎樣控制存取的,二極管rom結(jié)構(gòu)示例 (2位地址控制4個信息單元, 每個信息單元是4位0/1碼,1,1,1,0,1,0,1,1,0,0,1,0,1,1,1,1,1,1,0,0,0,0,0,1,0,1,存儲器內(nèi)部的實現(xiàn)示例,2-4地址譯碼器,0,1,0,1,存儲矩陣的邏輯控制關(guān)系示例,1,1,0,0,1,0,0,0,0,1,0,1,同一條數(shù)據(jù)線上各連接點之間是“或”關(guān)系,同一地址線上各連接點之間是“與”關(guān)系,dj是數(shù)據(jù)線,wi是地址線,地址編碼線與地址線有點連接，無點不連接,ak是地址編碼線,地址線與數(shù)據(jù)線有點連接，無點不連接,高/低電平信號，即0,1，通過連接點相互傳遞,上半?yún)^(qū)

11、通過“與”關(guān)系產(chǎn)生地址線上的最終信號傳遞到下半?yún)^(qū),d3 = w0 or w2 d2 = w1 or w2 or w3 d1 = w1 or w2 d0 = w0 or w1 or w3,w0 = (not a0) and (not a1) w1 = a0 and (not a1) w2 = (not a0) and a1 w3 = a0 and a1,用多個存儲器芯片可搭建容量更大的存儲器,利用4個256x8存儲器芯片擴展出1024x8存儲器的電路圖,半導體存儲器芯片示例,存儲器芯片容量不夠了怎么辦,問：從概念的角度，你能說說存儲器擴展要解決什么問題嗎? 提示：地址編碼空間, 存儲字長,機器級

12、程序 -機器指令 -機器級算法與程序,馮.諾依曼計算機：機器級程序及其執(zhí)行 2.2.4 機器級程序,算法-從馮.諾依曼計算機的角度 可在機器上執(zhí)行的求解問題的操作規(guī)則及步驟, 被稱為可執(zhí)行的算法,2.2.4 機器級程序 什么是算法,問：怎么看待算法節(jié)省的步數(shù)? -算法需要“優(yōu)化,機器指令 機器指令是cpu可以直接分析并執(zhí)行的指令，一般由0和1的編碼表示。 指令 操作碼 + 地址碼； 機器語言,000001 0000000100,000001 0000001100,000001 0000001000,機器指令是怎樣的,機器級程序,832+23+6; ax2+bx+c,怎樣用機器指令表達算法,高級

13、語言程序的示例 計算ax2+bx+c 其中a,x,b,c是變量。 變量的地址是由編譯程序在編譯 過程中自動分配的，也即是說編 譯器根據(jù)當時編譯的情況，分配 a,x,b,c為8號，9號，10號，11號 存儲單元，并產(chǎn)生上述的機器指 令程序,高級語言程序和機器有什么關(guān)系呢,機器級程序的執(zhí)行機制 -運算部件與控制部件 -指令的信號化與節(jié)拍化,馮.諾依曼計算機：機器級程序及其執(zhí)行 2.2.5 機器級程序的執(zhí)行機制,計算機各部件內(nèi)部的簡單構(gòu)成關(guān)系,運算器、控制器里面有什么,寄存器 算術(shù)邏輯部件 程序計數(shù)器pc 指令寄存器 信號控制器 時鐘與信號發(fā)生器 存儲單元地址 存儲單元內(nèi)容,不同的指令，由一組不同的電信號構(gòu)成 同一指令的電信號在時鐘與節(jié)拍的控制下按次序產(chǎn)生與傳輸 一條指令占用一個或多個機器周期，一個機器周期又分為多個節(jié)拍 最小的時間區(qū)隔單位-時鐘周期,指令是怎樣被執(zhí)行的,指令執(zhí)行,時鐘周期、節(jié)拍與機器周期,問：機器的“主頻”指的是什么,機器級程序的執(zhí)行過程模擬 -程序的硬件執(zhí)行過程,機器級程序的執(zhí)行過程模擬,第1條指令在一個機器周期內(nèi)完成。其中讀取和執(zhí)行分別在t0、t1和t2、t3節(jié)拍內(nèi)完成。(示意,一條指令是怎樣被執(zhí)行的,一條指令的執(zhí)行,一條指令的執(zhí)行,第1條指令在一個機器周期內(nèi)完成。其中讀取和執(zhí)行分別在t