1、圖靈機(jī)的思想與模型簡(jiǎn)介圖靈機(jī)的思想與模型簡(jiǎn)介Research Center on Intelligent Computing for Enterprises & Services,Harbin Institute of Technology戰(zhàn)德臣哈爾濱工業(yè)大學(xué) 教授.博士生導(dǎo)師教育部大學(xué)計(jì)算機(jī)課程教學(xué)指導(dǎo)委員會(huì)委員戰(zhàn)德臣 教授圖靈及其貢獻(xiàn)圖靈及其貢獻(xiàn)u圖靈圖靈(Alan Turing, 19121954)，出生于英國(guó)倫敦，19 歲入劍橋皇家學(xué)院，22 歲當(dāng)選為皇家學(xué)會(huì)會(huì)員。u1937 年，發(fā)表了論文論可計(jì)算數(shù)及其在判定問(wèn)題中的應(yīng)用，提出了圖靈機(jī)模型圖靈機(jī)模型，后來(lái)，馮諾依曼根據(jù)這個(gè)模型

2、設(shè)計(jì)出歷史上第一臺(tái)電子計(jì)算機(jī)。u1950 年，發(fā)表了劃時(shí)代的文章：機(jī)器能思考嗎?,成為了人工智能的開山之作。u計(jì)算機(jī)界于1966年設(shè)立了最高榮譽(yù)獎(jiǎng)：ACM圖靈圖靈獎(jiǎng)獎(jiǎng)。圖靈機(jī)的思想與模型簡(jiǎn)介圖靈機(jī)的思想與模型簡(jiǎn)介(1)圖靈是誰(shuí)圖靈是誰(shuí)?你能查閱一下哪些人獲得圖靈獎(jiǎng)了嗎？你能查閱一下哪些人獲得圖靈獎(jiǎng)了嗎？因?yàn)槭裁簇暙I(xiàn)而獲獎(jiǎng)呢？因?yàn)槭裁簇暙I(xiàn)而獲獎(jiǎng)呢？戰(zhàn)德臣 教授u所謂計(jì)算計(jì)算就是計(jì)算者(人或機(jī)器)對(duì)一條兩端可無(wú)限延長(zhǎng)的紙帶上的一串0或1，執(zhí)行指令一步一步地改變紙帶上的0或1，經(jīng)過(guò)有限步驟最后得到一個(gè)滿足預(yù)先規(guī)定的符號(hào)串的變換過(guò)程變換過(guò)程。什么是計(jì)算什么是計(jì)算10001110110011010110

3、0010110101由“程序”控制，一步步將輸入“轉(zhuǎn)換”為輸出輸入輸出程序通用機(jī)器通用機(jī)器圖靈機(jī)的思想與模型簡(jiǎn)介圖靈機(jī)的思想與模型簡(jiǎn)介(2)圖靈認(rèn)為什么是計(jì)算圖靈認(rèn)為什么是計(jì)算?戰(zhàn)德臣 教授圖靈機(jī)的思想圖靈機(jī)的思想是關(guān)于數(shù)據(jù)、指令、程序及程序是關(guān)于數(shù)據(jù)、指令、程序及程序/指令自動(dòng)執(zhí)行的基本思想。指令自動(dòng)執(zhí)行的基本思想。u 輸入被制成一串0和1的紙帶，送入機(jī)器中-數(shù)據(jù)數(shù)據(jù)。如00010000100011u 機(jī)器可對(duì)輸入紙帶執(zhí)行的基本動(dòng)作基本動(dòng)作包括：“翻轉(zhuǎn)0為1”，或 “翻轉(zhuǎn)1為0”, “前移一位”, “停止”。u 對(duì)基本動(dòng)作的控制-指令指令，機(jī)器是按照指令的控制選擇執(zhí)行哪一個(gè)動(dòng)作，指令也可以用

4、0和1來(lái)表示：01表示“翻轉(zhuǎn)0為1”(當(dāng)輸入為1時(shí)不變)，10表示“翻轉(zhuǎn)1為0”(當(dāng)輸入0時(shí)不變), 11表示“前移一位”, 00表示“停止”。u 輸入如何變?yōu)檩敵龅目刂瓶梢杂弥噶罹帉懸粋€(gè)程序程序來(lái)完成, 如: 011110110111011100u 機(jī)器能夠讀取程序，按程序中的指令順序讀取指令，讀一條指令執(zhí)行執(zhí)行一條指令。由此實(shí)現(xiàn)自動(dòng)計(jì)算自動(dòng)計(jì)算。圖靈機(jī)的思想與模型簡(jiǎn)介圖靈機(jī)的思想與模型簡(jiǎn)介(2)圖靈認(rèn)為什么是計(jì)算圖靈認(rèn)為什么是計(jì)算?戰(zhàn)德臣 教授u基本的圖靈機(jī)模型圖靈機(jī)模型為一個(gè)七元組,如右圖u幾點(diǎn)結(jié)論幾點(diǎn)結(jié)論:(1) 圖靈機(jī)是一種思想模型，它由一個(gè)控制器(有限狀態(tài)轉(zhuǎn)換器)，一條可無(wú)限延伸的

5、帶子和一個(gè)在帶子上左右移動(dòng)的讀寫頭構(gòu)成。(2) 程序是五元組程序是五元組形式的指令集形式的指令集。其定義了機(jī)器在一個(gè)特定狀態(tài)q下從方格中讀入一個(gè)特定字符X時(shí)所采取的動(dòng)作為在該方格中寫入符號(hào)Y, 然后向右移一格R (或向左移一格L或不移動(dòng)N), 同時(shí)將機(jī)器狀態(tài)設(shè)為p供下一條指令使用。圖靈機(jī)的思想與模型簡(jiǎn)介圖靈機(jī)的思想與模型簡(jiǎn)介(3)圖靈機(jī)是什么圖靈機(jī)是什么?圖靈機(jī)模型圖靈機(jī)模型戰(zhàn)德臣 教授圖靈機(jī)模型示例圖靈機(jī)模型示例。 (注:(q,X,Y,R(或L或N),p), 狀態(tài)圖中圓圈內(nèi)的是狀態(tài)，箭線上的是, 其含義見前頁(yè))執(zhí)行過(guò)程功能：將一串連續(xù)功能：將一串連續(xù)1的后面再加一位的后面再加一位1圖靈機(jī)的思

6、想與模型簡(jiǎn)介圖靈機(jī)的思想與模型簡(jiǎn)介(3)圖靈機(jī)是什么圖靈機(jī)是什么?0 0 1 1 1 1 0 0 0控制器控制器(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)：開始狀態(tài)S2：右移狀態(tài)：右移狀態(tài)S3：左移狀態(tài)：左移狀態(tài)S4：停機(jī)狀態(tài)：停機(jī)狀態(tài)0,0,R0 0 1 1 1 1 0 0 00 0 1 1 1 1 0 0 0(S1,0,0,R,S1)(S1,1,1,R,S2)0 0 1 1 1 1 0 0 0(S2

7、,1,1,R,S2)0 0 1 1 1 1 0 0 0(S2,0,1,L,S3)0 0 1 1 1 1 1 0 0(S3,1,1,L,S3)0 0 1 1 1 1 1 0 0(S3,0,0,N,S4)0 0 1 1 0 0 0 1 1你能否用另一個(gè)輸入模擬你能否用另一個(gè)輸入模擬一下這個(gè)程序的執(zhí)行呢一下這個(gè)程序的執(zhí)行呢?戰(zhàn)德臣 教授幾點(diǎn)結(jié)論幾點(diǎn)結(jié)論(續(xù)續(xù)):u(3)圖靈機(jī)模型圖靈機(jī)模型被認(rèn)為是計(jì)算機(jī)的基本理論模型-計(jì)算機(jī)是使用相應(yīng)的程序來(lái)完成任何設(shè)定好的任務(wù)。圖靈機(jī)是一種離散的、有窮的、構(gòu)造性的構(gòu)造性的問(wèn)題求解思路，一個(gè)問(wèn)題的求解可以通過(guò)構(gòu)造其圖靈機(jī)一個(gè)問(wèn)題的求解可以通過(guò)構(gòu)造其圖靈機(jī)(即程即程序

8、序)來(lái)解決來(lái)解決。u(4)圖靈認(rèn)為：凡是能用算法方法解決的問(wèn)題也一定能用圖靈機(jī)解決凡是能用算法方法解決的問(wèn)題也一定能用圖靈機(jī)解決; 凡是凡是圖靈機(jī)解決不了的問(wèn)題任何算法也解決不了圖靈機(jī)解決不了的問(wèn)題任何算法也解決不了-圖靈可計(jì)算性問(wèn)題。圖靈機(jī)的思想與模型簡(jiǎn)介圖靈機(jī)的思想與模型簡(jiǎn)介(3)圖靈機(jī)是什么圖靈機(jī)是什么?戰(zhàn)德臣 教授按計(jì)算規(guī)則按計(jì)算規(guī)則(程序程序)對(duì)輸入進(jìn)行變換對(duì)輸入進(jìn)行變換得到輸出得到輸出輸入輸入程序程序& &指令指令( (計(jì)算規(guī)則計(jì)算規(guī)則) )圖靈機(jī)的思想與模型簡(jiǎn)介圖靈機(jī)的思想與模型簡(jiǎn)介(4)小結(jié)小結(jié)?輸出輸出馮馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī): 思想與構(gòu)成思想與構(gòu)成Re

9、search Center on Intelligent Computing for Enterprises & Services,Harbin Institute of Technology戰(zhàn)德臣哈爾濱工業(yè)大學(xué) 教授.博士生導(dǎo)師教育部大學(xué)計(jì)算機(jī)課程教學(xué)指導(dǎo)委員會(huì)委員戰(zhàn)德臣 教授u19441945年間，馮.諾伊曼提出 “存儲(chǔ)程序”的計(jì)算機(jī)設(shè)計(jì)思想，并進(jìn)行了實(shí)踐，現(xiàn)代計(jì)算機(jī)普遍來(lái)講屬于馮.諾伊曼機(jī)體系。u馮.諾伊曼機(jī)的基本思想：l運(yùn)算運(yùn)算和存儲(chǔ)存儲(chǔ)分離分離l存儲(chǔ)程序存儲(chǔ)程序：指令和數(shù)據(jù)指令和數(shù)據(jù)以同等地位事先存于存儲(chǔ)器存于存儲(chǔ)器, 可按地址尋訪, 連續(xù)自動(dòng)執(zhí)行。連續(xù)自動(dòng)執(zhí)行。l五大部件構(gòu)

10、成：運(yùn)算器運(yùn)算器、控制器控制器、存儲(chǔ)器存儲(chǔ)器、輸入設(shè)備輸入設(shè)備和輸出設(shè)備輸出設(shè)備l指令和數(shù)據(jù)用二進(jìn)制二進(jìn)制表示，指令由操作碼和地址碼組成l以運(yùn)算器為中心，控制器負(fù)責(zé)解釋指令，運(yùn)算器負(fù)責(zé)執(zhí)行指令馮馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī): 思想與構(gòu)成思想與構(gòu)成(1)什么是馮什么是馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī)? 馮.諾依曼(Von.Neumann)計(jì)算機(jī)戰(zhàn)德臣 教授以運(yùn)算器為中心的馮以運(yùn)算器為中心的馮.諾依曼計(jì)算機(jī)構(gòu)成圖諾依曼計(jì)算機(jī)構(gòu)成圖馮馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī): 思想與構(gòu)成思想與構(gòu)成(2)馮馮.諾依曼計(jì)算機(jī)的結(jié)構(gòu)是怎樣的諾依曼計(jì)算機(jī)的結(jié)構(gòu)是怎樣的? 部件有哪些部件有哪些? 部件的關(guān)系怎樣部件的關(guān)系怎樣

11、? 戰(zhàn)德臣 教授以存儲(chǔ)器為中心的現(xiàn)代計(jì)算機(jī)構(gòu)成圖以存儲(chǔ)器為中心的現(xiàn)代計(jì)算機(jī)構(gòu)成圖馮馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī): 思想與構(gòu)成思想與構(gòu)成(3)存儲(chǔ)器為中心與運(yùn)算器為中心相比的優(yōu)點(diǎn)在哪里存儲(chǔ)器為中心與運(yùn)算器為中心相比的優(yōu)點(diǎn)在哪里? 同樣是五個(gè)部件，以不同的結(jié)構(gòu)來(lái)連接，便體現(xiàn)了不同的性能同樣是五個(gè)部件，以不同的結(jié)構(gòu)來(lái)連接，便體現(xiàn)了不同的性能-這就是這就是“系統(tǒng)系統(tǒng)”：強(qiáng)調(diào)：強(qiáng)調(diào)“結(jié)構(gòu)結(jié)構(gòu)”，強(qiáng)調(diào)部件連接后的整體性、協(xié)同性，強(qiáng)調(diào)部件連接后的整體性、協(xié)同性戰(zhàn)德臣 教授運(yùn)算器存儲(chǔ)器控制臺(tái)控制器(1)(1)(3)(3)(10)(10)(5)(5)(2)(2)(4)(4)(6)(6)(1)啟動(dòng)控制器工作(2)

12、發(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)(7)(8)(8)(9)(9)馮馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī): 思想與構(gòu)成思想與構(gòu)成(4)馮馮.諾依曼計(jì)算機(jī)的工作原理是怎樣的諾依曼計(jì)算機(jī)的工作原理是怎樣的? 工作原理工作原理戰(zhàn)德臣 教授計(jì)算機(jī)的基本部件計(jì)算機(jī)的基本部件uCPU：中央處理單元(Central Process Unit)，將運(yùn)算器和控制器集

13、成在一塊芯片上，形成微處理器。uCPU、主存儲(chǔ)器、主存儲(chǔ)器、I/O設(shè)備及總線成為現(xiàn)代計(jì)算機(jī)的四大核心部件。設(shè)備及總線成為現(xiàn)代計(jì)算機(jī)的四大核心部件。總線總線馮馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī): 思想與構(gòu)成思想與構(gòu)成(5)什么是什么是CPU? 現(xiàn)代計(jì)算機(jī)的幾大部件是什么現(xiàn)代計(jì)算機(jī)的幾大部件是什么? 現(xiàn)代計(jì)算機(jī)里面，一個(gè)微處理器現(xiàn)代計(jì)算機(jī)里面，一個(gè)微處理器(芯片芯片)可能包含多個(gè)可能包含多個(gè)CPU，即多核，即多核.戰(zhàn)德臣 教授運(yùn)算器運(yùn)算器中央處理單元中央處理單元CPU控制器控制器(主或內(nèi)主或內(nèi)) 存儲(chǔ)器存儲(chǔ)器程序程序數(shù)據(jù)數(shù)據(jù)程序與數(shù)程序與數(shù)據(jù)的保存據(jù)的保存程序執(zhí)行與程序執(zhí)行與數(shù)據(jù)計(jì)算數(shù)據(jù)計(jì)算馮馮.諾依曼

14、計(jì)算機(jī)諾依曼計(jì)算機(jī): 思想與構(gòu)成思想與構(gòu)成(6)小結(jié)小結(jié)戰(zhàn)德臣 教授基本目標(biāo)基本目標(biāo): : 理解程序是如何被執(zhí)行的理解程序是如何被執(zhí)行的基本思維：基本思維：機(jī)器級(jí)算法與程序機(jī)器級(jí)算法與程序機(jī)器指令與機(jī)器指令與指令系統(tǒng)指令系統(tǒng)存存儲(chǔ)器儲(chǔ)器存儲(chǔ)程序存儲(chǔ)程序運(yùn)算器與控制器運(yùn)算器與控制器機(jī)器級(jí)程序的執(zhí)行機(jī)器級(jí)程序的執(zhí)行；算法程序化算法程序化程序指令化程序指令化指令存儲(chǔ)化指令存儲(chǔ)化執(zhí)行信號(hào)化執(zhí)行信號(hào)化馮馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī): 思想與構(gòu)成思想與構(gòu)成(7)在在“馮馮.諾依曼機(jī)執(zhí)行程序的基本思維諾依曼機(jī)執(zhí)行程序的基本思維”中的位置中的位置? 自動(dòng)存取：存儲(chǔ)器的工作原理自動(dòng)存?。捍鎯?chǔ)器的工作原理Rese

15、arch Center on Intelligent Computing for Enterprises & Services,Harbin Institute of Technology戰(zhàn)德臣哈爾濱工業(yè)大學(xué) 教授.博士生導(dǎo)師教育部大學(xué)計(jì)算機(jī)課程教學(xué)指導(dǎo)委員會(huì)委員戰(zhàn)德臣 教授 存儲(chǔ)器的基本結(jié)構(gòu)存儲(chǔ)器的基本結(jié)構(gòu)自動(dòng)存取：存儲(chǔ)器的工作原理自動(dòng)存取：存儲(chǔ)器的工作原理(1)什么是存儲(chǔ)器什么是存儲(chǔ)器? 存儲(chǔ)器 宿舍樓存儲(chǔ)單元房間存儲(chǔ)位(存0或存1)床位(住人/不住人)地址編碼An-1A0房間號(hào)單元控制線Wi房間鑰匙輸出緩沖器公共的走廊及大門 概念映射概念映射從存儲(chǔ)器與宿舍樓的概念對(duì)比從存儲(chǔ)器與宿

16、舍樓的概念對(duì)比中，你能發(fā)現(xiàn)什么異同嗎？中，你能發(fā)現(xiàn)什么異同嗎？戰(zhàn)德臣 教授 存儲(chǔ)器內(nèi)部的實(shí)現(xiàn)示例存儲(chǔ)器內(nèi)部的實(shí)現(xiàn)示例u當(dāng)?shù)刂肪€和數(shù)據(jù)線間連接有二極管時(shí)，則存儲(chǔ)的是1，否則，存儲(chǔ)的是0n當(dāng)?shù)刂肪€和數(shù)據(jù)線間連接有二極管時(shí)，由地址線決定其是輸出1或0，即：當(dāng)?shù)刂肪€為高電平時(shí)，則輸出1，而當(dāng)?shù)刂肪€為低電平時(shí)，則輸出0；n沒(méi)有連接的，則不受地址線影響，始終輸出低電平0； 二極管二極管ROM結(jié)構(gòu)示例結(jié)構(gòu)示例(2位地址控制位地址控制4個(gè)信息單元個(gè)信息單元, 每個(gè)信息單元是每個(gè)信息單元是4位位0/1碼碼) 自動(dòng)存?。捍鎯?chǔ)器的工作原理自動(dòng)存?。捍鎯?chǔ)器的工作原理(2)存儲(chǔ)器是怎樣存儲(chǔ)存儲(chǔ)器是怎樣存儲(chǔ)0和和1的的?

17、 又是怎樣控制存取的又是怎樣控制存取的? 戰(zhàn)德臣 教授二極管二極管ROM結(jié)構(gòu)示例結(jié)構(gòu)示例(2位地址控制位地址控制4個(gè)信息單元個(gè)信息單元, 每個(gè)信息單元是每個(gè)信息單元是4位位0/1碼碼) 11101011001011111100000101 存儲(chǔ)器內(nèi)部的實(shí)現(xiàn)示例存儲(chǔ)器內(nèi)部的實(shí)現(xiàn)示例2-4地址譯碼器地址譯碼器自動(dòng)存?。捍鎯?chǔ)器的工作原理自動(dòng)存?。捍鎯?chǔ)器的工作原理(2)存儲(chǔ)器是怎樣存儲(chǔ)存儲(chǔ)器是怎樣存儲(chǔ)0和和1的的? 又是怎樣控制存取的又是怎樣控制存取的? 0101將地址編碼轉(zhuǎn)換為地址單元控制信號(hào)將地址編碼轉(zhuǎn)換為地址單元控制信號(hào)類比類比:將房間號(hào)轉(zhuǎn)換成房間鑰匙將房間號(hào)轉(zhuǎn)換成房間鑰匙戰(zhàn)德臣 教授 存儲(chǔ)矩陣

18、的邏輯控制關(guān)系示例存儲(chǔ)矩陣的邏輯控制關(guān)系示例110010000101同一條數(shù)據(jù)線上各連接點(diǎn)之間是“或”關(guān)系同一地址線上各連接點(diǎn)之間是“與”關(guān)系Dj是數(shù)據(jù)線Wi是地址線地址編碼線與地址線有點(diǎn)連接，無(wú)點(diǎn)不連接Ak是地址編碼線地址線與數(shù)據(jù)線有點(diǎn)連接，無(wú)點(diǎn)不連接高/低電平信號(hào)，即0,1，通過(guò)連接點(diǎn)相互傳遞上半?yún)^(qū)通過(guò)“與”關(guān)系產(chǎn)生地址線上的最終信號(hào)傳遞到下半?yún)^(qū)自動(dòng)存?。捍鎯?chǔ)器的工作原理自動(dòng)存取：存儲(chǔ)器的工作原理(2)存儲(chǔ)器是怎樣存儲(chǔ)存儲(chǔ)器是怎樣存儲(chǔ)0和和1的的? 又是怎樣控制存取的又是怎樣控制存取的? D3 = W0 OR W2D2 = W1 OR W2 OR W3D1 = W1 OR W2D0 = W

19、0 OR W1 OR W3W0 = (NOT A0) AND (NOT A1)W1 = A0 AND (NOT A1)W2 = (NOT A0) AND A1W3 = A0 AND A1戰(zhàn)德臣 教授用多個(gè)存儲(chǔ)器芯片可搭建容量更大的存儲(chǔ)器用多個(gè)存儲(chǔ)器芯片可搭建容量更大的存儲(chǔ)器 利用4個(gè)256x8存儲(chǔ)器芯片擴(kuò)展出1024x8存儲(chǔ)器的電路圖半導(dǎo)體存儲(chǔ)器芯片示例半導(dǎo)體存儲(chǔ)器芯片示例自動(dòng)存取：存儲(chǔ)器的工作原理自動(dòng)存取：存儲(chǔ)器的工作原理(3)存儲(chǔ)器芯片容量不夠了怎么辦存儲(chǔ)器芯片容量不夠了怎么辦?問(wèn)：從概念的角度，你能說(shuō)說(shuō)存儲(chǔ)器擴(kuò)展要解決什么問(wèn)題嗎問(wèn)：從概念的角度，你能說(shuō)說(shuō)存儲(chǔ)器擴(kuò)展要解決什么問(wèn)題嗎? 提示

20、：地址編碼空間提示：地址編碼空間, 存儲(chǔ)字長(zhǎng)存儲(chǔ)字長(zhǎng).戰(zhàn)德臣 教授存儲(chǔ)單元存儲(chǔ)單元( (的內(nèi)容的內(nèi)容) )(存儲(chǔ)單元的存儲(chǔ)單元的)地址地址地址地址 空間空間存儲(chǔ)存儲(chǔ) 字長(zhǎng)字長(zhǎng)自動(dòng)存?。捍鎯?chǔ)器的工作原理自動(dòng)存取：存儲(chǔ)器的工作原理(4)小結(jié)小結(jié)?存儲(chǔ)存儲(chǔ) 容量容量戰(zhàn)德臣 教授基本目標(biāo)基本目標(biāo): : 理解程序是如何被執(zhí)行的理解程序是如何被執(zhí)行的基本思維：基本思維：機(jī)器級(jí)算法與程序機(jī)器級(jí)算法與程序機(jī)器指令與機(jī)器指令與指令系統(tǒng)指令系統(tǒng)存存儲(chǔ)器儲(chǔ)器存儲(chǔ)程序存儲(chǔ)程序運(yùn)算器與控制器運(yùn)算器與控制器機(jī)器級(jí)程序的執(zhí)行機(jī)器級(jí)程序的執(zhí)行；算法程序化算法程序化程序指令化程序指令化指令存儲(chǔ)化指令存儲(chǔ)化執(zhí)行信號(hào)化執(zhí)行信號(hào)化自

21、動(dòng)存?。捍鎯?chǔ)器的工作原理自動(dòng)存取：存儲(chǔ)器的工作原理(5)在在“馮馮.諾依曼機(jī)執(zhí)行程序的基本思維諾依曼機(jī)執(zhí)行程序的基本思維”中的位置中的位置? 機(jī)器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序Research Center on Intelligent Computing for Enterprises & Services,Harbin Institute of Technology戰(zhàn)德臣哈爾濱工業(yè)大學(xué) 教授.博士生導(dǎo)師教育部大學(xué)計(jì)算機(jī)課程教學(xué)指導(dǎo)委員會(huì)委員戰(zhàn)德臣 教授問(wèn)題問(wèn)題-計(jì)算機(jī)如何計(jì)算一個(gè)運(yùn)算式計(jì)算機(jī)如何計(jì)算一個(gè)運(yùn)算式?機(jī)器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序(1)如何計(jì)算一個(gè)運(yùn)算式如

22、何計(jì)算一個(gè)運(yùn)算式?8 32 + 2 3 + 6運(yùn)算器存儲(chǔ)器控制臺(tái)控制器計(jì)算機(jī)的計(jì)算機(jī)的構(gòu)成構(gòu)成(概念概念)戰(zhàn)德臣 教授算法算法-從從馮馮.諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī)的角度的角度可在機(jī)器上執(zhí)行的求解問(wèn)題的操作規(guī)則及步驟, 被稱為可執(zhí)行的算法。機(jī)器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序(2)什么是算法什么是算法?問(wèn)：怎么看待算法節(jié)省的步數(shù)問(wèn)：怎么看待算法節(jié)省的步數(shù)? -算法需要算法需要“優(yōu)化優(yōu)化”戰(zhàn)德臣 教授000001 00 00000111000100 00 00001010操作碼操作碼 地址碼地址碼(如取數(shù)，加法等操作如取數(shù)，加法等操作)(操作中的數(shù)據(jù)的來(lái)源操作中的數(shù)據(jù)的來(lái)源)機(jī)器指令機(jī)器指令

23、-機(jī)器語(yǔ)言機(jī)器語(yǔ)言u(píng)機(jī)器指令是CPU可以直接分析并執(zhí)行的指令，一般由0和1的編碼表示。u指令指令 操作碼操作碼 + 地址碼地址碼；000001 0000000100000001 0000001100000001 0000001000機(jī)器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序(3)機(jī)器指令是怎樣的機(jī)器指令是怎樣的? 戰(zhàn)德臣 教授機(jī)器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序(4)怎樣用機(jī)器指令表達(dá)算法怎樣用機(jī)器指令表達(dá)算法? “3”存儲(chǔ)在存儲(chǔ)在8號(hào)存儲(chǔ)單元號(hào)存儲(chǔ)單元“8”存儲(chǔ)在存儲(chǔ)在9號(hào)存儲(chǔ)單元號(hào)存儲(chǔ)單元“2”存儲(chǔ)在存儲(chǔ)在10號(hào)存儲(chǔ)單元號(hào)存儲(chǔ)單元“6”存儲(chǔ)在存儲(chǔ)在11號(hào)存儲(chǔ)單元號(hào)存儲(chǔ)單元機(jī)器級(jí)機(jī)器級(jí)算法

24、算法機(jī)器機(jī)器 指令指令機(jī)器機(jī)器 級(jí)程序級(jí)程序戰(zhàn)德臣 教授計(jì)算計(jì)算832+23+6的程序的程序;計(jì)算計(jì)算ax2+bx+c的程序。的程序。機(jī)器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序(5)將機(jī)器級(jí)程序和數(shù)據(jù)裝載進(jìn)存儲(chǔ)器中將機(jī)器級(jí)程序和數(shù)據(jù)裝載進(jìn)存儲(chǔ)器中?機(jī)器機(jī)器 級(jí)程序級(jí)程序存儲(chǔ)器存儲(chǔ)器程序與數(shù)據(jù)以程序與數(shù)據(jù)以同等地位存于同等地位存于存儲(chǔ)器中存儲(chǔ)器中戰(zhàn)德臣 教授高級(jí)語(yǔ)言程序的示例高級(jí)語(yǔ)言程序的示例計(jì)算ax2+bx+c其中a,x,b,c是變量。變量的地址是由編譯程序在編譯過(guò)程中自動(dòng)分配的，也即是說(shuō)編譯器根據(jù)當(dāng)時(shí)編譯的情況，分配a,x,b,c為8號(hào)，9號(hào)，10號(hào)，11號(hào)存儲(chǔ)單元，并產(chǎn)生上述的機(jī)器指令程序機(jī)

25、器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序(6)高級(jí)語(yǔ)言程序和機(jī)器有什么關(guān)系呢高級(jí)語(yǔ)言程序和機(jī)器有什么關(guān)系呢?戰(zhàn)德臣 教授機(jī)器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序(7)小結(jié)小結(jié)?符號(hào)化、符號(hào)化、計(jì)算化計(jì)算化再語(yǔ)再語(yǔ)義化義化程序化程序化執(zhí)行化執(zhí)行化機(jī)器級(jí)算法機(jī)器級(jí)算法的結(jié)果的結(jié)果機(jī)器級(jí)程序機(jī)器級(jí)程序-機(jī)器指令機(jī)器指令運(yùn)算器和控運(yùn)算器和控制器：執(zhí)行制器：執(zhí)行機(jī)器級(jí)機(jī)器級(jí)算法算法執(zhí)行執(zhí)行用用0/1編碼：編碼：指令和數(shù)據(jù)指令和數(shù)據(jù)存儲(chǔ)器：存儲(chǔ)器：0/1存與取存與取0/1化化信號(hào)化信號(hào)化存儲(chǔ)存儲(chǔ)戰(zhàn)德臣 教授基本目標(biāo)基本目標(biāo): : 理解程序是如何被執(zhí)行的理解程序是如何被執(zhí)行的 基本思維：基本思維：機(jī)器級(jí)算法與

26、程序機(jī)器級(jí)算法與程序機(jī)器指令與機(jī)器指令與指令系統(tǒng)指令系統(tǒng)存存儲(chǔ)器儲(chǔ)器存儲(chǔ)程序存儲(chǔ)程序運(yùn)算器與控制器運(yùn)算器與控制器機(jī)器級(jí)程序的執(zhí)行機(jī)器級(jí)程序的執(zhí)行；算法程序化算法程序化程序指令化程序指令化指令存儲(chǔ)化指令存儲(chǔ)化執(zhí)行信號(hào)化執(zhí)行信號(hào)化機(jī)器指令與機(jī)器級(jí)程序機(jī)器指令與機(jī)器級(jí)程序(8)在在“馮馮.諾依曼機(jī)執(zhí)行程序的基本思維諾依曼機(jī)執(zhí)行程序的基本思維”中的位置中的位置? 機(jī)器級(jí)程序的執(zhí)行機(jī)制機(jī)器級(jí)程序的執(zhí)行機(jī)制Research Center on Intelligent Computing for Enterprises & Services,Harbin Institute of Technolog

27、y戰(zhàn)德臣哈爾濱工業(yè)大學(xué) 教授.博士生導(dǎo)師教育部大學(xué)計(jì)算機(jī)課程教學(xué)指導(dǎo)委員會(huì)委員戰(zhàn)德臣 教授機(jī)器級(jí)程序的執(zhí)行機(jī)制機(jī)器級(jí)程序的執(zhí)行機(jī)制(1)裝配一臺(tái)計(jì)算機(jī)裝配一臺(tái)計(jì)算機(jī)-運(yùn)算器運(yùn)算器(數(shù)據(jù)數(shù)據(jù))寄存器寄存器00000000 0000001100000000 0000100000000000 0000000000000000 00000000算術(shù)、邏輯及移位運(yùn)算R0R1運(yùn)算器運(yùn)算器p(數(shù)據(jù)數(shù)據(jù))寄存器寄存器p算術(shù)邏輯部件算術(shù)邏輯部件R0 = R1 R0 (賦值賦值, R0既是一個(gè)操作數(shù)，又保存運(yùn)算結(jié)果既是一個(gè)操作數(shù)，又保存運(yùn)算結(jié)果)。其中其中 為算術(shù)、邏輯及移位運(yùn)算符為算術(shù)、邏輯及移位運(yùn)算符戰(zhàn)德臣

28、教授時(shí)鐘與節(jié)拍發(fā)生器信號(hào)控制00000000 00000000000001 0000001000PCIR00000000 0000001100000000 0000100000000000 0000000000000000 00000000算術(shù)、邏輯及移位運(yùn)算R0R1控制器控制器運(yùn)算器運(yùn)算器(數(shù)據(jù)數(shù)據(jù))寄存器寄存器機(jī)器級(jí)程序的執(zhí)行機(jī)制機(jī)器級(jí)程序的執(zhí)行機(jī)制(2)裝配一臺(tái)計(jì)算機(jī)裝配一臺(tái)計(jì)算機(jī)控制器控制器p程序計(jì)數(shù)器程序計(jì)數(shù)器PCp指令寄存器指令寄存器p信號(hào)控制器信號(hào)控制器p時(shí)鐘與信號(hào)發(fā)生器時(shí)鐘與信號(hào)發(fā)生器注：PC：程序計(jì)數(shù)器-存儲(chǔ)下一要執(zhí)行指令的地址IR：指令寄存器-存儲(chǔ)當(dāng)前指令內(nèi)容 信號(hào)控制線

29、數(shù)據(jù)線 地址線戰(zhàn)德臣 教授時(shí)鐘與節(jié)拍發(fā)生器信號(hào)控制00000000 00000000000001 0000001000PCIR00000000 0000001100000000 0000100000000000 0000000000000000 00000000算術(shù)、邏輯及移位運(yùn)算00000100 0000100000000000 00000000地址地址內(nèi)容內(nèi)容R0R1存儲(chǔ)器存儲(chǔ)器( (內(nèi)存內(nèi)存) )控制器控制器運(yùn)算器運(yùn)算器(數(shù)據(jù)數(shù)據(jù))寄存器寄存器p存儲(chǔ)單元地址存儲(chǔ)單元地址p存儲(chǔ)單元內(nèi)容存儲(chǔ)單元內(nèi)容機(jī)器級(jí)程序的執(zhí)行機(jī)制機(jī)器級(jí)程序的執(zhí)行機(jī)制(3)裝配一臺(tái)計(jì)算機(jī)裝配一臺(tái)計(jì)算機(jī)存儲(chǔ)器存儲(chǔ)器程序程序

30、& &指令指令戰(zhàn)德臣 教授u不同的指令，由一組不同的電信號(hào)構(gòu)成不同的指令，由一組不同的電信號(hào)構(gòu)成u同一指令的電信號(hào)在時(shí)鐘與節(jié)拍的控制下按次序產(chǎn)生與傳輸同一指令的電信號(hào)在時(shí)鐘與節(jié)拍的控制下按次序產(chǎn)生與傳輸u一條指令占用一個(gè)或多個(gè)機(jī)器周期，一個(gè)機(jī)器周期又分為多個(gè)節(jié)拍一條指令占用一個(gè)或多個(gè)機(jī)器周期，一個(gè)機(jī)器周期又分為多個(gè)節(jié)拍u最小的時(shí)間區(qū)隔單位最小的時(shí)間區(qū)隔單位-時(shí)鐘周期時(shí)鐘周期機(jī)器級(jí)程序的執(zhí)行機(jī)制機(jī)器級(jí)程序的執(zhí)行機(jī)制(4)指令是怎樣被執(zhí)行的指令是怎樣被執(zhí)行的? 指令執(zhí)行指令執(zhí)行問(wèn)：機(jī)器的問(wèn)：機(jī)器的“主頻主頻”指的是什么指的是什么?時(shí)鐘周期、時(shí)鐘周期、節(jié)拍與節(jié)拍與 機(jī)器周期機(jī)器周期指

31、令執(zhí)行的信號(hào)化指令執(zhí)行的信號(hào)化-即在節(jié)拍即在節(jié)拍控制下有序地發(fā)出各種電信號(hào)控制下有序地發(fā)出各種電信號(hào)戰(zhàn)德臣 教授計(jì)算機(jī)各部件內(nèi)部的簡(jiǎn)單構(gòu)成關(guān)系計(jì)算機(jī)各部件內(nèi)部的簡(jiǎn)單構(gòu)成關(guān)系機(jī)器級(jí)程序的執(zhí)行機(jī)制機(jī)器級(jí)程序的執(zhí)行機(jī)制(5)機(jī)器級(jí)程序被裝載進(jìn)存儲(chǔ)器中機(jī)器級(jí)程序被裝載進(jìn)存儲(chǔ)器中p寄存器寄存器p算術(shù)邏輯部件算術(shù)邏輯部件p程序計(jì)數(shù)器程序計(jì)數(shù)器PCp指令寄存器指令寄存器p信號(hào)控制器信號(hào)控制器p時(shí)鐘與信號(hào)發(fā)生器時(shí)鐘與信號(hào)發(fā)生器p存儲(chǔ)單元地址存儲(chǔ)單元地址p存儲(chǔ)單元內(nèi)容存儲(chǔ)單元內(nèi)容控制器控制器運(yùn)算器運(yùn)算器存儲(chǔ)器存儲(chǔ)器( (內(nèi)存內(nèi)存) )程序程序& &指令指令數(shù)據(jù)數(shù)據(jù)戰(zhàn)德臣 教授基本目標(biāo)基本目標(biāo):

32、: 理解程序是如何被執(zhí)行的理解程序是如何被執(zhí)行的基本思維：基本思維：機(jī)器級(jí)算法與程序機(jī)器級(jí)算法與程序機(jī)器指令與機(jī)器指令與指令系統(tǒng)指令系統(tǒng)存存儲(chǔ)器儲(chǔ)器存儲(chǔ)程序存儲(chǔ)程序運(yùn)算器與控制器運(yùn)算器與控制器機(jī)器級(jí)程序的執(zhí)行機(jī)器級(jí)程序的執(zhí)行；算法程序化算法程序化程序指令化程序指令化指令存儲(chǔ)化指令存儲(chǔ)化執(zhí)行信號(hào)化執(zhí)行信號(hào)化機(jī)器級(jí)程序的執(zhí)行機(jī)制機(jī)器級(jí)程序的執(zhí)行機(jī)制(6)在在“馮馮.諾依曼機(jī)執(zhí)行程序的基本思維諾依曼機(jī)執(zhí)行程序的基本思維”中的位置中的位置? 機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬Research Center on Intelligent Computing for Enterprises

33、& Services,Harbin Institute of Technology戰(zhàn)德臣哈爾濱工業(yè)大學(xué) 教授.博士生導(dǎo)師教育部大學(xué)計(jì)算機(jī)課程教學(xué)指導(dǎo)委員會(huì)委員戰(zhàn)德臣 教授時(shí)鐘與節(jié)拍發(fā)生器信號(hào)控制00000000 00000000000001 0000001000PCIR00000000 0000001100000000 0000100000000000 0000000000000000 00000000算術(shù)、邏輯及移位運(yùn)算00000100 0000100000000000 00000000地址地址內(nèi)容內(nèi)容R0R1(數(shù)據(jù)數(shù)據(jù))寄存器寄存器機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬(

34、1)程序和數(shù)據(jù)已經(jīng)裝入存儲(chǔ)器中如何執(zhí)行呢程序和數(shù)據(jù)已經(jīng)裝入存儲(chǔ)器中如何執(zhí)行呢?程序程序& &指令指令數(shù)據(jù)數(shù)據(jù)運(yùn)算器運(yùn)算器控制器控制器存儲(chǔ)器存儲(chǔ)器戰(zhàn)德臣 教授時(shí)鐘與節(jié)拍發(fā)生器信號(hào)控制寄存器寄存器00000000 00000000000001 0000001000-(隨機(jī)的數(shù)值)-(隨機(jī)的數(shù)值)-(隨機(jī)的數(shù)值)-(隨機(jī)的數(shù)值)算術(shù)、邏輯及移位運(yùn)算00000100 0000100000000000 00000000地址內(nèi)容R0R1PCIR運(yùn)算器運(yùn)算器控制器控制器存儲(chǔ)器存儲(chǔ)器機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬(2)第第1條指令的讀取條指令的讀取戰(zhàn)德臣 教授時(shí)鐘與節(jié)拍發(fā)生器

35、信號(hào)控制寄存器寄存器00000000 00000001000001 0000001000-(隨機(jī)的數(shù)值)00000000 00000011-(隨機(jī)的數(shù)值)-(隨機(jī)的數(shù)值)算術(shù)、邏輯及移位運(yùn)算00000000 0000001100000000 00001000地址內(nèi)容控制控制R0R0R1000001PCIR-(隨機(jī)的數(shù)值)00000000 00000000運(yùn)算器運(yùn)算器控制器控制器存儲(chǔ)器存儲(chǔ)器機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬(3)第第1條指令的執(zhí)行條指令的執(zhí)行戰(zhàn)德臣 教授時(shí)鐘與節(jié)拍發(fā)生器信號(hào)控制寄存器寄存器00000000 00000001000100 0000001001-(隨機(jī)的數(shù)值)00000000 00000011-(隨機(jī)的數(shù)值)-(隨機(jī)的數(shù)值)算術(shù)、邏輯及移位運(yùn)算00010000 0000100100000000 00000001地址內(nèi)容R0R1PCIR000001 0000001000運(yùn)算器運(yùn)算器控制器控制器存儲(chǔ)器存儲(chǔ)器機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬機(jī)器級(jí)程序的執(zhí)行過(guò)程模擬(4)第第2條指令的讀取條指令的讀取戰(zhàn)德