1、第二章數(shù)據(jù)表示與指令系統(tǒng)第1頁，共47頁。內(nèi)容提要 數(shù)據(jù)表示 尋址方式 指令系統(tǒng)的設(shè)計(jì)和改進(jìn)第2頁，共47頁。數(shù)據(jù)數(shù)據(jù)：數(shù)據(jù)是描述客觀事物的一些相互無關(guān)的符號(hào)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位。數(shù)據(jù)類型：除了是一組值的集合外，還定義了可作用 于這個(gè)集合上的操作集。目的：防止不同類型數(shù)據(jù)間的誤操作分類：基本數(shù)據(jù)類型、結(jié)構(gòu)數(shù)據(jù)類型第3頁，共47頁。1、基本數(shù)據(jù)類型基本數(shù)據(jù)類型包括:二進(jìn)制位及其位串整數(shù)及自然數(shù)(正整數(shù))實(shí)數(shù)(浮點(diǎn)數(shù))字符布爾數(shù) 第4頁，共47頁。由一組相互有關(guān)的數(shù)據(jù)元素組合而成的數(shù)據(jù)類型。常用的結(jié)構(gòu)數(shù)據(jù)類型有:向量數(shù)組字符串堆棧隊(duì)列記錄2、結(jié)構(gòu)數(shù)據(jù)類型第5頁，共47頁。2.1.1 數(shù)據(jù)表

2、示與數(shù)據(jù)結(jié)構(gòu)第6頁，共47頁。1、數(shù)據(jù)表示數(shù)據(jù)表示是指可由硬件直接識(shí)別和引用的數(shù)據(jù)類型.由硬件實(shí)現(xiàn)的數(shù)據(jù)類型。數(shù)據(jù)類型包含了數(shù)據(jù)取值集和可作用其上的操作集，所以，相應(yīng)的指令及處理部件是識(shí)別這些數(shù)據(jù)類型所必需的。即：對(duì)該數(shù)據(jù)類型的各種運(yùn)算操作都有相應(yīng)的實(shí)現(xiàn)硬件電路第7頁，共47頁。2、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指結(jié)構(gòu)數(shù)據(jù)類型的組織方式.它反映了在應(yīng)用中所用到的各種數(shù)據(jù)元素或信息單元間的結(jié)構(gòu)關(guān)系。除了數(shù)據(jù)表示之外的所有數(shù)據(jù)類型，一般都是數(shù)據(jù)結(jié)構(gòu)要研究的內(nèi)容。是由軟件實(shí)現(xiàn)的數(shù)據(jù)類型。數(shù)據(jù)表示和數(shù)據(jù)結(jié)構(gòu)都是數(shù)據(jù)類型的子集。硬件不能直接辨認(rèn)與處理的數(shù)據(jù)類型就要根據(jù)數(shù)據(jù)結(jié)構(gòu)的知識(shí)編制軟件轉(zhuǎn)化為硬件能處理的數(shù)據(jù)類型

3、第8頁，共47頁。2、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)研究的一個(gè)主要課題是:1)如何用最少的存儲(chǔ)空間來存儲(chǔ)這些數(shù)據(jù)結(jié)構(gòu)；2)采用什么樣的算法能最快、最簡(jiǎn)單地存儲(chǔ)和訪問這些數(shù)據(jù)結(jié)構(gòu).數(shù)據(jù)表示要考慮的是正確、可靠、便于機(jī)器處理和節(jié)省存儲(chǔ)空間。第9頁，共47頁。數(shù)據(jù)表示實(shí)質(zhì)上是軟、硬件的主要分界面之一。確定數(shù)據(jù)表示的實(shí)質(zhì)是一個(gè)有關(guān)軟硬件的取舍問題。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)首先要研究的一個(gè)內(nèi)容是：在所有數(shù)據(jù)類型中，哪些用硬件實(shí)現(xiàn)，哪些用軟件實(shí)現(xiàn)，并研究它們的實(shí)現(xiàn)方法。3、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)表示第10頁，共47頁。（1）關(guān)于基本數(shù)據(jù)表示的討論數(shù)的進(jìn)制選擇例：“二進(jìn)制表示”和“二-十進(jìn)制表示”的權(quán)衡； 二進(jìn)制表示在運(yùn)算速度、信息存儲(chǔ)

4、空間方面有優(yōu)勢(shì) 但二進(jìn)制轉(zhuǎn)換為十進(jìn)制費(fèi)時(shí)，而且有誤差。 二-十進(jìn)制（BCD碼）表示所需的存儲(chǔ)空間大。事務(wù)處理的出現(xiàn)，需要大量的十進(jìn)制數(shù)，增加了十進(jìn)制運(yùn)算指令和相應(yīng)的運(yùn)算硬件。第11頁，共47頁。字長(zhǎng)的確定例：定點(diǎn)數(shù)和浮點(diǎn)數(shù)表示的字長(zhǎng)的權(quán)衡 過短：表示范圍小，表示精度低，容易造成運(yùn)算溢出和機(jī)器零。 過長(zhǎng)：主存空間開銷大 定長(zhǎng)表示和某些語言的語義不一致 如COBOL語言提供了可變長(zhǎng)數(shù)據(jù)結(jié)構(gòu)；有力支持了串?dāng)?shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。 為把可變長(zhǎng)數(shù)據(jù)映象為定長(zhǎng)數(shù)據(jù)表示，將增加編譯的復(fù)雜性和編譯時(shí)間。折中的辦法：多種定長(zhǎng)數(shù)據(jù)表示，按位編址（1）關(guān)于基本數(shù)據(jù)表示的討論第12頁，共47頁。（2）數(shù)據(jù)表示的設(shè)計(jì)原則如何確

5、定數(shù)據(jù)表示是計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)設(shè)計(jì)人員要解決的難題之一。第13頁，共47頁。確定哪些數(shù)據(jù)類型用數(shù)據(jù)表示來實(shí)現(xiàn)的原則:1) 縮短程序的運(yùn)行時(shí)間，2) 減少CPU與主存儲(chǔ)器之間的通信量3) 考慮這種數(shù)據(jù)表示的通用性和利用率。堆棧機(jī)：對(duì)棧數(shù)據(jù)結(jié)構(gòu)高效，但矩陣運(yùn)算效率卻很低。樹型結(jié)構(gòu)機(jī)器：對(duì)樹數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)高效，但堆棧、 向量、鏈表等結(jié)構(gòu)的實(shí)現(xiàn)低效。（2）數(shù)據(jù)表示的設(shè)計(jì)原則第14頁，共47頁。例1 如果用定點(diǎn)數(shù)據(jù)表示實(shí)現(xiàn)浮點(diǎn)運(yùn)算，處理機(jī)的運(yùn)算速度要降低兩個(gè)數(shù)量級(jí)。 如果用一臺(tái)定點(diǎn)運(yùn)算速度為每秒1千萬次的計(jì)算機(jī)做科學(xué)計(jì)算，它的實(shí)際運(yùn)算速度將低于每秒十萬次。用定點(diǎn)運(yùn)算指令來實(shí)現(xiàn)32位的浮點(diǎn)運(yùn)算時(shí)，平均要執(zhí)行1

6、00條以上的指令。CPU與主存儲(chǔ)器之間的通信量也將增加100多倍。第15頁，共47頁。例2 實(shí)現(xiàn)AA+B，A和B均為200200的矩陣。如果在沒有向量數(shù)據(jù)表示的計(jì)算機(jī)系統(tǒng)上實(shí)現(xiàn)，編譯為IBM370機(jī)器的目標(biāo)代碼有6條指令，其中4條指令要執(zhí)行4*104次。因此，CPU與主存儲(chǔ)器之間的通信量為：取指令：2+4 40 000條，讀或?qū)憯?shù)據(jù)：3 40 000個(gè)，共訪問主存儲(chǔ)器7 40 000次以上。第16頁，共47頁。例2 實(shí)現(xiàn)AA+B，A和B均為200200的矩陣。如果在有向量數(shù)據(jù)表示的計(jì)算機(jī)系統(tǒng)上實(shí)現(xiàn)，只需要一條指令。從而減少了CPU與主存儲(chǔ)器之間的通信量：少取指令4 40 000次，程序執(zhí)行時(shí)間

7、縮短了一半以上。第17頁，共47頁。因此，在設(shè)計(jì)計(jì)算機(jī)系統(tǒng)時(shí)，對(duì)于數(shù)據(jù)類型，系統(tǒng)結(jié)構(gòu)設(shè)計(jì)者要做的是：確定哪些數(shù)據(jù)類型全部用硬件實(shí)現(xiàn)，即數(shù)據(jù)表示；哪些數(shù)據(jù)類型用軟件實(shí)現(xiàn)，即數(shù)據(jù)結(jié)構(gòu)；哪些數(shù)據(jù)類型可由硬件給予適當(dāng)支持,即由軟件和硬件共同實(shí)現(xiàn),并確定軟件與硬件的適當(dāng)比例關(guān)系.第18頁，共47頁。2.1.2 高級(jí)數(shù)據(jù)表示第19頁，共47頁。傳統(tǒng)的馮諾依曼計(jì)算機(jī)中，指令本身指明了操作數(shù)據(jù)類型.例如對(duì)于加法指令，在IBM 370中就要分成定點(diǎn)加、浮點(diǎn)加、十進(jìn)制加等15種加法指令。高級(jí)語言中，同一種運(yùn)算操作，只采用一個(gè)操作符.如 A=A+Breal A,B;A=A+B;int A,B;A=A+B;float

8、 A,B;A=A+B;第20頁，共47頁。自定義數(shù)據(jù)表示 帶標(biāo)志符的數(shù)據(jù)表示 數(shù)據(jù)描述符 向量數(shù)據(jù)表示 堆棧數(shù)據(jù)表示第21頁，共47頁。1、帶標(biāo)志符的數(shù)據(jù)表示數(shù)據(jù)字的格式類型標(biāo)志 數(shù)據(jù)值這種表示要求對(duì)每一個(gè)數(shù)據(jù)都附加類型標(biāo)志 B-5000設(shè)置了1位標(biāo)志，用來區(qū)分?jǐn)?shù)據(jù)字是操作數(shù)還是描述符。 B-6500和B-7500設(shè)置了3位標(biāo)志，可區(qū)分8種類型。第22頁，共47頁。R-2設(shè)置了10位標(biāo)志符。信息類型位（ 2位）直接標(biāo)志位（4位）奇偶位（1位）寫封鎖位（1位）軟件定義捕捉位（2位）信息類型位直接標(biāo)志位數(shù)值二進(jìn)制數(shù)、十進(jìn)制數(shù)、整數(shù)、實(shí)數(shù)、字符串、單精度數(shù)、雙精度數(shù)地址絕對(duì)地址、相對(duì)地址、鏈接中的地

9、址1、帶標(biāo)志符的數(shù)據(jù)表示第23頁，共47頁。帶標(biāo)志符數(shù)據(jù)表示的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：1）減少指令種類，簡(jiǎn)化指令系統(tǒng)與程序設(shè)計(jì)；2）簡(jiǎn)化了編譯器的構(gòu)造，并加快了編譯過程；3）便于一致性檢查（由硬件檢測(cè)）；4）由硬件實(shí)現(xiàn)數(shù)據(jù)類型的轉(zhuǎn)換，可進(jìn)一步簡(jiǎn)化編譯器，并縮短變換時(shí)間；5）支持了數(shù)據(jù)庫系統(tǒng)的實(shí)現(xiàn)與數(shù)據(jù)類型無關(guān)的要求；6）為軟件調(diào)試和應(yīng)用軟件的開發(fā)提供了支持。第24頁，共47頁。帶標(biāo)志符數(shù)據(jù)表示的優(yōu)缺點(diǎn)使用帶標(biāo)志符數(shù)據(jù)表示的主要問題是： 1）程序占用的主存空間增加若有BA程序所占的存儲(chǔ)空間反而節(jié)省第25頁，共47頁。使用帶標(biāo)志符數(shù)據(jù)表示的主要問題是： 2）指令執(zhí)行速度將減慢（但宏觀性能有利）.3）必須用專門

10、的指令完成標(biāo)志符的初始化.帶標(biāo)志符數(shù)據(jù)表示的優(yōu)缺點(diǎn)第26頁，共47頁。2、數(shù)據(jù)描述符數(shù)據(jù)描述符專門用來描述要訪問的數(shù)據(jù)的特性.主要是用來描述復(fù)雜和多維結(jié)構(gòu)的數(shù)據(jù)類型。 指明這是一個(gè)數(shù)據(jù)描述符指明所描述數(shù)據(jù)的各種特征指明所描述數(shù)據(jù)的長(zhǎng)度，即數(shù)組中元素個(gè)數(shù)指明所描述的一組數(shù)據(jù)的首址。描述符標(biāo)志位特征標(biāo)志數(shù)據(jù)塊長(zhǎng)度數(shù)據(jù)塊起始地址第27頁，共47頁。B-6700計(jì)算機(jī)的數(shù)據(jù)描述符數(shù)據(jù)格式描述符格式000數(shù)據(jù)101長(zhǎng)度地址標(biāo)志位標(biāo)志位(8位)另一描述符體系整塊或單個(gè)數(shù)據(jù)連續(xù)或分段存貯只讀或可寫字或串單精度或雙精度長(zhǎng)度塊內(nèi)元素的個(gè)數(shù)地址塊中首元素的地址第28頁，共47頁。數(shù)據(jù)描述符與帶標(biāo)志符的不同 標(biāo)志符

11、要與每個(gè)數(shù)據(jù)相連，兩者合起來存在一個(gè)存儲(chǔ)器單元中，描述單個(gè)數(shù)據(jù)的類型特征 描述符則和數(shù)據(jù)分開存放，專門用來描述要訪問的數(shù) 據(jù)是整塊數(shù)據(jù)還是單塊數(shù)據(jù)，訪問該數(shù)據(jù)塊或數(shù)據(jù)元素 需要的地址以及其他特征等信息。是對(duì)它所指向的數(shù)據(jù) 塊的共性描述，為數(shù)據(jù)塊中所有數(shù)據(jù)字所共享.第29頁，共47頁。操作碼XY000000101101101101地址生成邏輯指令數(shù)據(jù)數(shù)據(jù).主存儲(chǔ)器描述符描述符的工作過程第30頁，共47頁。例：一維數(shù)組的描述第31頁，共47頁。按行描述按列描述1013101410141014000(a11)000(a12)000(a13)000(a14)000(a21)000(a22)000(a2

12、3)000(a24)000(a31)000(a32)000(a33)000(a34)1014例：二維數(shù)組的描述第32頁，共47頁。3、向量數(shù)據(jù)表示例如，若要計(jì)算ci=ai+bi-4, i=4，5，11的向量加法時(shí)，用C語言實(shí)現(xiàn)： for(i=4;i=11;i+) ci=ai+bi-4;各條目標(biāo)碼指令只能順序執(zhí)行。向量加 A向量參數(shù) B向量參數(shù) C向量參數(shù) 第33頁，共47頁。向量參數(shù)（基地址，位移量，向量長(zhǎng)度） :指向向量的第一個(gè)元素 向量長(zhǎng)度 用于校驗(yàn)地址是否越界 基地址位移量起始地址 指向?qū)嶋H參加運(yùn)算的第一個(gè)元素 向量的有效長(zhǎng)度 第34頁，共47頁。Ce=11-4+1A0A1A2A3A4A

13、5A6A7A8A9A10A11AbAd=4As=4Ae=11-4+1C0C1C2C3C4C5C6C7C8C9C10C11CbCd=4Cs=4B0B1B2B3B4B5B6B7Bd=0Bb=Bs=0Be=7-0+1c(i)=a(i)+b(i-4)例：ci=ai+bi-4, i=4，5，11第35頁，共47頁。（1）向量處理機(jī)向量處理機(jī)（ Vector Processor ）：具有向量表示和相應(yīng)向量運(yùn)算指令的計(jì)算機(jī)。標(biāo)量處理機(jī)（ Scalar Processor ）：不具有向量表示和相應(yīng)向量運(yùn)算指令的計(jì)算機(jī)。第36頁，共47頁。（2）向量數(shù)據(jù) 向量的表示 數(shù)組 A=(a0,a1,a2,an-1) a

14、i為A的元素，可以為定點(diǎn)數(shù)、浮點(diǎn)數(shù)、整數(shù)等 向量在主存中的存放原則： 規(guī)律性、地址計(jì)算簡(jiǎn)單、訪存沖突小 元素相鄰存放 元素等間距存放第37頁，共47頁。壓縮一般要分為兩步實(shí)現(xiàn)：1)先形成一個(gè)向量Z，它是一個(gè)“位向量”，用來指明稀疏向量中各元素的狀況及所在位置。2)根據(jù)Z向量的內(nèi)容將稀疏向量中與Z向量中“1”元素相對(duì)應(yīng)的向量元素存入指定存儲(chǔ)單元，轉(zhuǎn)變成壓縮向量.稀疏向量: 含有大量零元素的向量.（3）稀疏向量第38頁，共47頁。A0A1(0)A2(0)A3A4A5(0)A6(0)A7A0A3A4A7 A0 A1 A2 A3 A4 A5 A6 A7 1 0 0 1 1 0 0 1稀疏向量 壓縮向量

15、 Z向量（有序向量） 第39頁，共47頁。4、堆棧數(shù)據(jù)表示堆棧機(jī)器： 具有堆棧數(shù)據(jù)表示的機(jī)器。第40頁，共47頁。堆棧機(jī)器特點(diǎn)： (1)有若干高速寄存器組成的硬件堆棧，并附加控制電路讓它與主存中的堆棧區(qū)在邏輯上組成一個(gè)整體，使堆棧的訪問速度是寄存器的，容量是主存的。 (2)有很豐富的堆棧操作類指令且功能很強(qiáng)，可直接對(duì)堆棧中的數(shù)據(jù)進(jìn)行各種運(yùn)算和處理。 (3)有力地支持高級(jí)語言程序的編譯（逆波蘭式）。 (4)有力地支持子程序的嵌套和遞歸調(diào)用。 第41頁，共47頁。5、定點(diǎn)數(shù)據(jù)表示幾乎所有的計(jì)算機(jī)都支持二進(jìn)制定點(diǎn)數(shù)據(jù)表示.通常采用二進(jìn)制定點(diǎn)數(shù)據(jù)表示的有：符號(hào)數(shù)值反碼補(bǔ)碼偏移二進(jìn)制碼第42頁，共47頁。6、浮點(diǎn)表示法任意一個(gè)二進(jìn)制數(shù)N總可以寫成下面的形式： N=m2emfefem尾數(shù)的符號(hào)位階碼的符號(hào)位階碼的值尾數(shù)的值第43頁，共47頁。浮點(diǎn)數(shù)據(jù)表示的通用性好，利用率高，所以在以科學(xué)計(jì)算為主的計(jì)算機(jī)系統(tǒng)中，設(shè)置浮點(diǎn)數(shù)據(jù)表示必不可少的。第44頁，共47頁。研究浮點(diǎn)數(shù)表示方式的主要目的是:用盡