第4講-大學(xué)計(jì)算機(jī)第4講-馮-諾依曼計(jì)算機(jī)器-程序執(zhí)行

圖靈機(jī)的思想與模型簡介圖靈(AlanTuring,1912~1954)，出生于英國倫敦，19歲入劍橋皇家學(xué)院，22歲當(dāng)選為皇家學(xué)會(huì)會(huì)員。1937年，發(fā)表了論文《論可計(jì)算數(shù)及其在判定問題中的應(yīng)用》，提出了圖靈機(jī)模型，后來，馮·諾依曼根據(jù)這個(gè)模型設(shè)計(jì)出歷史上第一臺(tái)電子計(jì)算機(jī)。1950年，發(fā)表了劃時(shí)代的文章：《機(jī)器能思考嗎?》,成為了人工智能的開山之作。計(jì)算機(jī)界于1966年設(shè)立了最高榮譽(yù)獎(jiǎng)：ACM圖靈獎(jiǎng)。圖靈機(jī)的思想與模型簡介(1)圖靈是誰?所謂計(jì)算就是計(jì)算者(人或機(jī)器)對一條兩端可無限延長的紙帶上的一串0或1，執(zhí)行指令一步一步地改變紙帶上的0或1，經(jīng)過有限步驟最后得到一個(gè)滿足預(yù)先規(guī)定的符號串的變換過程?！?0001110110011010110001…0110101由“程序”控制，一步步將輸入“轉(zhuǎn)換”為輸出輸入輸出程序通用機(jī)器圖靈機(jī)的思想與模型簡介(2)圖靈認(rèn)為什么是計(jì)算?圖靈機(jī)的思想是關(guān)于數(shù)據(jù)、指令、程序及程序/指令自動(dòng)執(zhí)行的基本思想。輸入被制成一串0和1的紙帶，送入機(jī)器中----數(shù)據(jù)。如00010000100011…機(jī)器可對輸入紙帶執(zhí)行的基本動(dòng)作包括：“翻轉(zhuǎn)0為1”，或“翻轉(zhuǎn)1為0”,“前移一位”,“停止”。對基本動(dòng)作的控制----指令，機(jī)器是按照指令的控制選擇執(zhí)行哪一個(gè)動(dòng)作，指令也可以用0和1來表示：01表示“翻轉(zhuǎn)0為1”(當(dāng)輸入為1時(shí)不變)，10表示“翻轉(zhuǎn)1為0”(當(dāng)輸入0時(shí)不變),11表示“前移一位”,00表示“停止”。輸入如何變?yōu)檩敵龅目刂瓶梢杂弥噶罹帉懸粋€(gè)程序來完成,如:011110110111011100…

機(jī)器能夠讀取程序，按程序中的指令順序讀取指令，讀一條指令執(zhí)行一條指令。由此實(shí)現(xiàn)自動(dòng)計(jì)算。圖靈機(jī)的思想與模型簡介(2)圖靈認(rèn)為什么是計(jì)算?用機(jī)器來模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程。圖靈機(jī)模型示例。(注:(q,X,Y,R(或L或N),p),狀態(tài)圖中圓圈內(nèi)的是狀態(tài)，箭線上的是<X,Y,R>,其含義見前頁)執(zhí)行過程功能：將一串連續(xù)1的后面再加一位1圖靈機(jī)的思想與模型簡介(3)圖靈機(jī)是什么?001111000控制器(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)S1S2S3S41,1,R1,1,R0,1,L1,1,L0,0,NS1：開始狀態(tài)S2：右移狀態(tài)S3：左移狀態(tài)S4：停機(jī)狀態(tài)0,0,R001111000001111000(S1,0,0,R,S1)(S1,1,1,R,S2)001111000(S2,1,1,R,S2)001111000(S2,0,1,L,S3)001111100(S3,1,1,L,S3)001111100(S3,0,0,N,S4)001100011你能否用另一個(gè)輸入模擬一下這個(gè)程序的執(zhí)行呢?幾點(diǎn)結(jié)論:圖靈機(jī)是一種思想模型，它由一個(gè)控制器(有限狀態(tài)轉(zhuǎn)換器)，一條可無限延伸的帶子和一個(gè)在帶子上左右移動(dòng)的讀寫頭構(gòu)成。圖靈認(rèn)為圖靈機(jī)可以用有限的、機(jī)械的步驟解決具體的計(jì)算問題，這些步驟稱為“算法”。圖靈機(jī)的思想與模型簡介(3)圖靈機(jī)是什么?圖靈機(jī)模型幾點(diǎn)結(jié)論(續(xù)):為設(shè)計(jì)計(jì)算機(jī)（硬件）指明了方向；

為算法和程序設(shè)計(jì)（軟件）提供了理論依據(jù)；

----計(jì)算機(jī)是使用相應(yīng)的程序來完成任何設(shè)定好的任務(wù)。圖靈機(jī)是一種離散的、有窮的、構(gòu)造性的問題求解思路，一個(gè)問題的求解可以通過構(gòu)造其圖靈機(jī)(即程序)來解決。圖靈認(rèn)為：凡是能用算法方法解決的問題也一定能用圖靈機(jī)解決;凡是圖靈機(jī)解決不了的問題任何算法也解決不了----圖靈可計(jì)算性問題。圖靈機(jī)的思想與模型簡介(3)圖靈機(jī)是什么?按計(jì)算規(guī)則(程序)對輸入進(jìn)行變換得到輸出輸入程序&指令(計(jì)算規(guī)則)輸入/輸出都是0和1的形式表達(dá)圖靈機(jī)的思想與模型簡介(4)小結(jié)?輸出程序和指令也是0和1的形式表達(dá)程序可用狀態(tài)轉(zhuǎn)換圖來表達(dá)馮.諾依曼計(jì)算機(jī):思想與構(gòu)成1944~1945年間，馮.諾伊曼提出

“存儲(chǔ)程序”的計(jì)算機(jī)設(shè)計(jì)思想，并進(jìn)行了實(shí)踐，現(xiàn)代計(jì)算機(jī)普遍來講屬于馮.諾伊曼機(jī)體系。馮.諾伊曼機(jī)的基本思想：運(yùn)算和存儲(chǔ)分離存儲(chǔ)程序：指令和數(shù)據(jù)以同等地位事先存于存儲(chǔ)器,可按地址尋訪,連續(xù)自動(dòng)執(zhí)行。五大部件構(gòu)成：運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備和輸出設(shè)備指令和數(shù)據(jù)用二進(jìn)制表示，指令由操作碼和地址碼組成以運(yùn)算器為中心，控制器負(fù)責(zé)解釋指令，運(yùn)算器負(fù)責(zé)執(zhí)行指令馮.諾依曼計(jì)算機(jī):思想與構(gòu)成(1)什么是馮.諾依曼計(jì)算機(jī)?以運(yùn)算器為中心的馮.諾依曼計(jì)算機(jī)構(gòu)成圖馮.諾依曼計(jì)算機(jī):思想與構(gòu)成(2)馮.諾依曼計(jì)算機(jī)的結(jié)構(gòu)是怎樣的?

部件有哪些?部件的關(guān)系怎樣?以存儲(chǔ)器為中心的現(xiàn)代計(jì)算機(jī)構(gòu)成圖馮.諾依曼計(jì)算機(jī):思想與構(gòu)成(3)存儲(chǔ)器為中心與運(yùn)算器為中心相比的優(yōu)點(diǎn)在哪里?同樣是五個(gè)部件，以不同的結(jié)構(gòu)來連接，便體現(xiàn)了不同的性能----這就是“系統(tǒng)”：強(qiáng)調(diào)“結(jié)構(gòu)”，強(qiáng)調(diào)部件連接后的整體性、協(xié)同性運(yùn)算器存儲(chǔ)器控制臺(tái)控制器(1)(3)(10)(5)(2)(4)(6)(1)啟動(dòng)控制器工作(2)發(fā)送第1條指令地址(3)取出指令并分析指令(4)執(zhí)行指令：發(fā)送操作數(shù)x所在地址(5)執(zhí)行指令：取出操作數(shù)x(10)執(zhí)行指令：通知運(yùn)算器計(jì)算a乘x(11)繼續(xù)后續(xù)指令的取指、執(zhí)行…(6)發(fā)送下一條指令地址(7)取出指令并分析指令(8)執(zhí)行指令：發(fā)送操作數(shù)a所在地址(9)執(zhí)行指令：取出操作數(shù)a(7)(8)(9)馮.諾依曼計(jì)算機(jī):思想與構(gòu)成(4)馮.諾依曼計(jì)算機(jī)的工作原理是怎樣的?CPU：中央處理單元(CentralProcessUnit)，將運(yùn)算器和控制器集成在一塊芯片上，形成微處理器。CPU、主存儲(chǔ)器、I/O設(shè)備及總線成為現(xiàn)代計(jì)算機(jī)的四大核心部件。總線馮.諾依曼計(jì)算機(jī):思想與構(gòu)成(5)什么是CPU?現(xiàn)代計(jì)算機(jī)的幾大部件是什么?現(xiàn)代計(jì)算機(jī)里面，一個(gè)微處理器(芯片)可能包含多個(gè)CPU，即多核.運(yùn)算器中央處理單元CPU控制器(主或內(nèi))存儲(chǔ)器程序數(shù)據(jù)程序與數(shù)據(jù)的保存程序執(zhí)行與數(shù)據(jù)計(jì)算馮.諾依曼計(jì)算機(jī):思想與構(gòu)成(6)小結(jié)自動(dòng)存?。捍鎯?chǔ)器的工作原理自動(dòng)存?。捍鎯?chǔ)器的工作原理(1)什么是存儲(chǔ)器?用來在計(jì)算機(jī)中存儲(chǔ)CPU可直接訪問的數(shù)據(jù)主存儲(chǔ)器的工作速度和容量對計(jì)算機(jī)系統(tǒng)整體性能影響極大主存儲(chǔ)器容量基本計(jì)量單位為字節(jié)（Byte）目前常見的內(nèi)存容量多為2GB,4GB,8GB自動(dòng)存?。捍鎯?chǔ)器的工作原理(2)主存儲(chǔ)器地址訪問方式訪問主存儲(chǔ)器使用地址訪問方式存儲(chǔ)地址一個(gè)存儲(chǔ)單元或相鄰幾個(gè) 存儲(chǔ)單元的開始地址CPU的字長通常為4個(gè)字節(jié)（32位）或8個(gè)字節(jié)（64位），因此CPU讀寫內(nèi)存數(shù)據(jù)的方式也通常是每次4個(gè)字節(jié)或8個(gè)字節(jié)程序中的變量和存儲(chǔ)單元相對應(yīng)變量名字對應(yīng)于存儲(chǔ)單元地址變量內(nèi)容對應(yīng)于存儲(chǔ)單元中的數(shù)據(jù)指針的內(nèi)容是存儲(chǔ)地址存儲(chǔ)單元(的內(nèi)容)(存儲(chǔ)單元的)地址地址空間存儲(chǔ)字長自動(dòng)存?。捍鎯?chǔ)器的工作原理(4)小結(jié)?存儲(chǔ)容量機(jī)器指令與機(jī)器級程序機(jī)器指令與機(jī)器級程序(1)如何計(jì)算一個(gè)運(yùn)算式?832+23+6運(yùn)算器存儲(chǔ)器控制臺(tái)控制器計(jì)算機(jī)的構(gòu)成(概念)機(jī)器指令與機(jī)器級程序(2)算法00000100000001110001000000001010操作碼地址碼(如取數(shù)，加法等操作)(操作中的數(shù)據(jù)的來源)機(jī)器指令是CPU可以直接分析并執(zhí)行的指令，一般由0和1的編碼表示。指令操作碼+地址碼；000001

0000000100000001

0000001100000001

0000001000機(jī)器指令與機(jī)器級程序(3)機(jī)器指令是怎樣的?機(jī)器指令與機(jī)器級程序(4)怎樣用機(jī)器指令表達(dá)算法?“3”存儲(chǔ)在8號存儲(chǔ)單元“8”存儲(chǔ)在9號存儲(chǔ)單元“2”存儲(chǔ)在10號存儲(chǔ)單元“6”存儲(chǔ)在11號存儲(chǔ)單元機(jī)器級算法機(jī)器指令機(jī)器級程序計(jì)算832+23+6的程序;計(jì)算ax2+bx+c的程序。機(jī)器指令與機(jī)器級程序(5)將機(jī)器級程序和數(shù)據(jù)裝載進(jìn)存儲(chǔ)器中?機(jī)器級程序存儲(chǔ)器程序與數(shù)據(jù)以同等地位存于存儲(chǔ)器中高級語言程序的示例計(jì)算ax2+bx+c其中a,x,b,c是變量。變量的地址是由編譯程序在編譯過程中自動(dòng)分配的，也即是說編譯器根據(jù)當(dāng)時(shí)編譯的情況，分配a,x,b,c為8號，9號，10號，11號存儲(chǔ)單元，并產(chǎn)生上述的機(jī)器指令程序機(jī)器指令與機(jī)器級程序(6)高級語言程序和機(jī)器有什么關(guān)系呢?機(jī)器指令與機(jī)器級程序(7)小結(jié)?符號化、計(jì)算化再語義化自然/社會(huì)問題程序化執(zhí)行化機(jī)器級算法的結(jié)果機(jī)器級程序--機(jī)器指令運(yùn)算器和控制器：執(zhí)行機(jī)器級算法自然/社會(huì)問題的求解結(jié)果執(zhí)行用0/1編碼：指令和數(shù)據(jù)存儲(chǔ)器：0/1存與取0/1化信號化存儲(chǔ)機(jī)器級程序的執(zhí)行過程模擬機(jī)器級程序的執(zhí)行過程模擬(1)裝配一臺(tái)計(jì)算機(jī)--運(yùn)算器(數(shù)據(jù))寄存器0000000000000011000000000000100000000000000000000000000000000000算術(shù)、邏輯及移位運(yùn)算R0R1運(yùn)算器(數(shù)據(jù))寄存器算術(shù)邏輯部件R0=R1

R0(賦值,R0既是一個(gè)操作數(shù)，又保存運(yùn)算結(jié)果)。其中為算術(shù)、邏輯及移位運(yùn)算符時(shí)鐘與節(jié)拍發(fā)生器信號控制00000000000000000000010000001000PCIR0000000000000011000000000000100000000000000000000000000000000000算術(shù)、邏輯及移位運(yùn)算R0R1控制器運(yùn)算器(數(shù)據(jù))寄存器機(jī)器級程序的執(zhí)行過程模擬(1)裝配一臺(tái)計(jì)算機(jī)—控制器程序計(jì)數(shù)器PC指令寄存器信號控制器時(shí)鐘與信號發(fā)生器注：PC：程序計(jì)數(shù)器---存儲(chǔ)下一要執(zhí)行指令的地址IR：指令寄存器---存儲(chǔ)當(dāng)前指令內(nèi)容信號控制線數(shù)據(jù)線地址線時(shí)鐘與節(jié)拍發(fā)生器信號控制00000000000000000000010000001000PCIR0000000000000011000000000000100000000000000000000000000000000000算術(shù)、邏輯及移位運(yùn)算00000100000010000000000000000000地址內(nèi)容R0R1(數(shù)據(jù))寄存器機(jī)器級程序的執(zhí)行過程模擬(1)裝配一臺(tái)計(jì)算機(jī)——存儲(chǔ)器程序&指令數(shù)據(jù)運(yùn)算器控制器存儲(chǔ)器時(shí)鐘與節(jié)拍發(fā)生器信號控制寄存器00000000000000000000010000001000--(隨機(jī)的數(shù)值)--(隨機(jī)的數(shù)值)--(隨機(jī)的數(shù)值)--(隨機(jī)的數(shù)值)算術(shù)、邏輯及移位運(yùn)算00000100000010000000000000000000地址內(nèi)容R0R1PCIR運(yùn)算器控制器存儲(chǔ)器機(jī)器級程序的執(zhí)行過程模擬(2)第1條指令的讀取時(shí)鐘與節(jié)拍發(fā)生器信號控制寄存器00000000000000010000010000001000--(隨機(jī)的數(shù)值)0000000000000011--(隨機(jī)的數(shù)值)--(隨機(jī)的數(shù)值)算術(shù)、邏輯及移位運(yùn)算00000000000000110000000000001000地址內(nèi)容控制R0R0R1000001PCIR--(隨機(jī)的數(shù)值)0000000000000000運(yùn)算器控制器存儲(chǔ)器機(jī)器級程序的執(zhí)行過程模擬(3)第1條指令的執(zhí)行時(shí)鐘與節(jié)拍發(fā)生器信號控制寄存器00000000000000010001000000001001--(隨機(jī)的數(shù)值)0000000000000011--(隨機(jī)的數(shù)值)--(隨機(jī)的數(shù)值)算術(shù)、邏輯及移位運(yùn)算00010000000010010000000000000001地址內(nèi)容R0R1PCIR0000010000001000運(yùn)算器控制器存儲(chǔ)器機(jī)器級程序的執(zhí)行過程模擬(4)第2條指令的讀取時(shí)鐘與節(jié)拍發(fā)生器信號控制寄存器0000000000000010000100000000100100000000000010000000000000000011--(隨機(jī)的數(shù)值)--(隨機(jī)的數(shù)值)R0算術(shù)、邏輯及移位運(yùn)算R100000000000010000000000000001001地址內(nèi)容控制R1000100PCIR--(隨機(jī)的數(shù)值)00000000000