计算机体系结构总结

计算机体系结构总结（通用6篇）

篇1：计算机体系结构总结

计算机体系结构的详尽描述

一.计算机系统结构的基本概念

1.计算机体系结构的概念

1964年G.M.Amdahl在介绍IBM360系统时提出：计算机系统结构是从程序员所看到的计算机属性，即程序员编写出能在机器上正确运行的程序所必须了解的概念性结构和功能特性。

系统结构是对计算机系统中各级界面的划分、定义及其上下功能的分配。

系统结构设计主要研究界面的属性的透明性的取舍。

计算机系统结构（体系结构）指的是传统机器级的系统结构。

计算机系统结构研究的是软、硬件之间的功能分配以及对传统机器级界面的确定。

2.计算机系统的多级层次结构

二.计算机指令集结构设计

根据五个因素对计算机指令集结构进行分类：在CPU中操作数的存储方法；指令中显式表示的操作数个数；操作数的寻址方式；指令集所提供的操作类型；操作数的类型和大小。其中1是最主要的区别 根据CPU内部存储单元类型，可将指令集结构分为

堆栈型指令集结构、累加器型指令集结构和通用寄存器型指令集结构。优缺点？堆栈型（其CPU中存储操作数的主要单元是堆栈）：是一种表示计算的简单模型；指令短小。不能随机访问堆栈，从而很难生成有效代码；同时，由于堆栈是瓶颈，所以很难被高效地实现。累加器型（其CPU中存储操作数的主要单元是累加器）：减少了机器的内部状态；指令短小。由于累加器是唯一的暂存器，这种机器的存储器通信开销最大。寄存器型（CPU中存储操作数的主要单元是通用寄存器）：易于生成高效的目标代码。所有操作数均需命名，且要显式表示，因而指令比较长

现代大多数机器均采用通用寄存器型指令集结构，原因：一是寄存器和CPU内部其他存储单元一样，要比存储器快；其次是对编译器而言，可以更加容易、有效地分配和使用寄存器。

寄存器－寄存器型（RR）优点：简单，指令字长固定，是一种简单的代码生成模型，各种指令的执行时钟周期数相近。缺点：和ALU指令中含存储器操作数的指令集结构相比，指令条数多，因而其目标代码量较大。

寄存器－存储器（RM）优点：可以直接对存储器操作数进行访问，容易对指令进行编码，且其目标代码量较小。缺点：指令中的操作数类型不同。在一条指令中同时对一个寄存器操作数和存储器操作数进行编码，将限制指令所能够表示的寄存器个数。由于指令的操作数可以存储在不同类型的存储器单元，所以每条指令的执行时钟周期数也不尽相同存储器－存储器型（MM）优点：是一种最紧密的编码方式，无需“浪费”寄存器保存变量。缺点：指令字长多种多样。每条指令的执行时钟周期数也大不一样，对存

储器的频繁访问将导致存储器访问瓶颈问题

CISC即复杂指令集计算机。它是增强指令功能，把越来越多的功能交由硬件来实行，并且指令的数量也是越来越多。RISC精简指令集计算机。它是尽可能的把指令集简化，不仅指令的条数少，而且指令的功能也比较简单。

三.流水线技术

流水线技术：将一个重复的时序过程分解成为若干个子过程，而每一个子过程都可有效地在其专用功能段上与其他子过程同时执行。

时空图：用来描述流水线的工作，横坐标表示时间，纵坐标代表流水线的各段。

流水技术有哪些特点？

1）流水过程由多个相联系的子过程组成，每个过程称为流水线的“级”或“段”。2）每个子过程由专用的功能段实现。3）各个功能段所需时间应尽量相等。4）流水线需要有“通过时间”，在此之后流水过程才进入稳定工作状态，每一个时钟周期(拍)流出一个结果。5）流水技术适合于大量重复的时序过程，只有在输入端能连续地提供任务，流水线的效率才能充分发挥。

多倍性：在系统受限的部件上，同时处于同一执行阶段的指令或数据的最大数目。

流水线分类

1按照流水线所完成的功能（1）单功能流水线：只能完成一种固定功能的流水线（2）多功能流水线：流水线的各段可以进行不同的连接，从而使流水线在不同的时间，或者在同一时间完成不同的功能。2按照同一时间内各段之间的连接方式（1）静态流水线：在同一时间内，流水线的各段只能按同一种功能的连接方式工作。2）动态流水线：在同一时间内，当某些段正在实现某种运算时，另一些段却在实现另一种运算。

3按照流水的级别（1）部件级流水线（运算操作流水线）：把处理机的算术逻辑部件分段，以便为各种数据类型进行流水操作。（2）处理机级流水线（指令流水线）：把解释指令的过程按照流水方式处理。（3）处理机间流水线（宏流水线）：由两个以上的处理机串行地对同一数据流进行处理，每个处理机完成一项任务。

4按数据表示（1）标量流水处理机：处理机不具有向量数据表示，仅对标量数据进行流水处理。（2）向量流水处理机：处理机具有向量数据表示，并通过向量指令对向量的各元素进行处理。

5按照流水线中是否有反馈回路（1）线性流水线：流水线的各段串行连接，没有反馈回路。（2）非线性流水线：流水线中除有串行连接的通路外，还有反馈回路。

流水线寄存器的作用：把数据和控制信息从一个流水段传送到下一个流水段。

消除流水线的瓶颈段:细分瓶颈段；重复设置瓶颈段。

价流水线的性能指标(1)吞吐率：指在单位时间内流水线所完成的任务数或输出结果的数量。(2)流水线的加速比：指m段流水线的速度与等功能的非流水线的速度之比。(3)效率：指流水线的设备利用率。

流水线相关的三种类型：

相关是指两条指令之间存在某种依赖关系。确定程序中指令之间存在什么样的相关，对于充分发挥流水线的效率有重要的意义。1.结构相关：当指令在重叠执行过程中，硬件资源满足不了指令重叠执行的要求，发生资源冲突时将产生“结构相关”；2.数据相关：当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就可能引起“数据相关”；3.控制相关：当流水线遇到分支指令和其他会改变PC值的指令时就会发生“控制相关”。

消除相关的基本方法：1让流水线暂停执行某些指令，而继续执行其他一些指令。2当一条指令被暂停时，在该暂停指令之后发射的所有指令都要被暂停，而在该暂停指令之前发射的指令则可继续执行，在暂停

期间，流水线不会取新的指令。

输入/输出方式：程序控制（程序等待、程序中断）、DMA、通道、I/O处理机

数据相关：对于两条指令i（在前）和j（在后），如果下述条件之一成立，则称指令j与指令i数据相关：

（1）指令j使用指令i产生的结果；（2）指令j与指令k数据相关，而指令k又与指令i数据相关。名相关

如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。指令j与指令i之间的名相关有以下两种：（1）反相关。如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关。反相关指令之间的执行顺序是必须严格遵守的，以保证i读的值是正确的。（2）输出相关。如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。输出相关指令的执行顺序是不能颠倒的，以保证最后的结果是指令j写进去的。

解决方法：换名技术，通过改变指令中操作数的名来消除名相关。

控制相关：由分支指令引起的相关。它需要根据分支指令的执行结果来确定后续指令是否执行。

流水线冲突

指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。

（1）结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。解决方法：流水化功能单元；资源重复；暂停流水线。（2）数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。根据指令对寄存器的读写顺序，可将数据冲突分为：写后读冲突；写后写冲突；读后写冲突。（3）控制冲突：流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。

四种解决数据冲突的方法：1）定向技术：在某条指令产生一个结果之前，其他指令并不真正需要该计算结果，如果将该计结果从其产生的地方直接送到其他指令需要它的地方，就可以避免暂停；2）暂停技术：设置一个“流水线互锁”的功能部件，一旦流水线互锁检测到数据相关，流水线暂停执行发生数据相关指令后续的所有指令，直到该数据相关解决为止。；3）采用编译器调度。当流水线中出现冲突时，编译器通过重新排列代码的顺序来消除流水线中的暂停，这种技术称为流水线调度4）重新组织代码顺序。流水线设计者有时会允许结构冲突的存在，原因：一是为了减少硬件开销，二是为了减少功能单元的延迟。

向量处理机：具有向量数据表示和相应向量指令的流水线处理机。

向量处理方式

(1)水平处理方式：向量计算是按行的方式从左到右横向地进行。若向量长度为N，则水平处理方式相当于执行N次循环。若使用流水线，在每次循环中可能出现数据相关和功能转换，不适合对向量进行流水处理。(2)垂直处理方式：适合对向量进行流水处理，向量运算指令的源/目向量都放在存储器内，使得流水线运算部件的输入、输出端直接与存储器相联，构成MM型（存储器－存储器）的运算流水线。(3)分组处理方式：适合流水处理。可设长度为n的向量寄存器，使每组向量运算的源/目向量都在向量寄存器中，流水线的运算部件输入、输出端与向量寄存器相联，构成RR型运算流水线。

提高向量处理机性能的方法：多个功能部件；链接技术；分段开采技术；多处理机系统

向量链接技术：当两条向量指令出现“写后读”相关时，若它们不存在功能部件冲突和向量寄存器(源或目的)冲突，就有可能把它们所用的功能部件头尾相接，形成一个链接流水线，进行流水处理。

链接技术应用条件：1.无功能部件冲突2.无向量寄存器使用冲突 3.只有在前一条指令的第1个结果元素送入结果向量机寄存器的那个时钟周期才可以进行链接。4.当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时，要求先行指令产生运算结果的时间必须相等。5.要求进行链接执行的向量指令的向量长度必须相等。

四.指令级并行

指令级并行：当指令之间不存在相关时，它们可以在流水线中重叠起来并行执行。这种指令序列中存在的潜在并行性称为指令级并行。

静态调度技术：依靠编译器对代码进行静态调度，以减少相关和冲突。它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。静态调度通过把相关的指令拉开距离来减少可能产生的停顿。动态调度方法：在流水线中出现相关时，通过硬件重新安排指令的执行顺序，来调整相关指令实际执行时的关系，减少处理器空转。优点。（1）能够处理一些编译时情况不明的相关（比如涉及存储器访问的相关），并简化了编译器。（2）能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行。当然，动态调度的这些优点是以硬件复杂性的显著增加为代价的。

为了支持乱序执行，将5段流水线的译码（ID）段细分为两个段（1）流出：指令译码，并检查是否存在结构冲突。如果不存在结构冲突，就将指令流出。（2）读操作数：等待数据冲突消失（如果有的话），然后读操作数。

Tomasulo算法的核心思想① 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最少；② 通过寄存器换名来消除WAR冲突和WAW冲突。

Tomasulo算法的基本思想是：只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中。指令的执行结果也是直接送到等待数据的其他保留站中去。因而，对于连续的寄存器写，只有最后一个才真正更新寄存器中的内容。一条指令流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。指令流出逻辑和保留站相结合实现寄存器换名，从而完全消除了数据写后写和先读后写相关这类名相关。保留站：设置在运算部件的入口，每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息），包括操作码、操作数以及用于检测和解决冲突的信息。

动态分支预测技术

在程序运行时，根据分支指令过去的表现来预测其将来的行为。如果分支行为发生了变化，预测结果也跟着改变。动态分支预测技术的目的有两个：预测分支是否成功和尽快找到分支目标地址（或指令），从而避免因控制相关而造成流水线停顿。

需要解决两个关键问题（1）如何记录分支的历史信息；（2）如何根据这些信息来预测分支的去向（甚至取到指令）。

前瞻执行的基本思想。

对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到一个称为ROB的缓冲器中。等到相应的指令得到“确认”（即确实是应该执行的）后，才将结果写入寄存器或存储器。

五.存储层次

单级存储器的主要矛盾：速度越快，每位价格就越高。容量越大，每位价格就越低。容量越大，速度越慢。采取多级存储层次方法来解决。

从用户的角度来看，存储器的三个主要指标是：容量、速度和价格。

评价存储层次的主要参数:存储层次的平均每位价格、命中率或失效率、平均访问时间。

“Cache－主存”层次：在CPU和主存之间增加一级速度快、但容量较小而每位价格较贵的高速缓冲存储器。借助于辅助软硬件，它与主存构成一个有机的整体，以弥补主存速度的不足。

“主存－辅存”层次：目的是为了弥补主存容量的不足。它是在主存外面增加一个容量更大、每位价格更便宜、但速度更慢的存储器。它们依靠辅助软硬件的作用，构成一个整体。

主要区别是什么？

目的：为了弥补主存速度的不足；为了弥补主存容量的不足。存储管理的实现：全部由专用硬件实现；主要由软件实现。典型的块（页）大小：几十个字节；几百到几千个字节。CPU对第二级的访问方式：可直接访问；均通过第一级。不命中时CPU是否切换：不切换切换到其他进程

存储层次中应解决四个问题：映像规则：当把一个块调入高一层存储器时，可以放到哪些位置上。查找算法：当所要访问的块在高一层存储器中时，如何找到该块。替换算法：当发生失效时，应替换哪一块。写策略：当进行写访问时，应进行哪些操作。

地址映像方法，优缺点

（1）全相联映像。实现查找的机制复杂，代价高，速度慢。Cache空间的利用率较高，块冲突概率较低，因而Cache的失效率也低。

（2）直接映像。实现查找的机制简单，速度快。Cache空间的利用率较低，块冲突概率较高，因而Cache的失效率也高。

（3）组相联映像。组相联是直接映像和全相联的一种折中。

组相联Cache比相同容量的直接映像Cache的失效率低。由此是否可以得出结论：采用组相联Cache一定能带来性能上的提高？为什么？ 不一定。因为组相联命中率的提高是以增加命中时间为代价的，组相联需要增加多路选择开关。

Cache中，实现并行查找的方法：1用相联存储器实现。2用单体多字存储器和比较器来实现。替换算法

（1）随机法：简单、易于用硬件实现，但这种方法没有考虑Cache块过去被使用的情况，反映不了程序的局部性，所以其失效率比LRU的高。（2）先进先出法：容易实现。它虽然利用了同一组中各块进入Cache的顺序这一“历史”信息，但还是不能正确地反映程序的局部性。（3）最近最少使用法LRU：失效率最低。但是LRU比较复杂，硬件实现比较困难。

有效构建方法：在构建系统的过程中消除故障隐患，这样建立起来的系统就不会出现故障。

写策略

(1)写直达法：易于实现，而且下一级存储器中的数据总是最新的。

(2)写回法：速度快，写操作能以Cache存储器的速度进行。而且对于同一单元的多个写最后只需一次写回下一级存储器，有些“写”只到达Cache，不到达主存，因而所使用的存储器频带较低。

六.输入/输出系统

输入/输出系统简称I/O系统，它包括I/O设备以及I/O设备与处理机的连接。

总线按用途分类，总线可分为

(1)CPU存储器总线。CPU存储器总线比较短，通常具有较高的速度，并且要和存储器系统的速度匹配来优化带宽。(2)I/O总线。I/O总线要连接许多不同类型、不同带宽的设备，因而比较长，并且应遵循总线标准。

按设备定时方式分类，总线可分为

(1)同步总线。所有设备通过统一的总线系统时钟进行同步。成本低，因为它不需要设备之间互相确定时序的逻辑。缺点：总线操作必须以相同的速度运行。(2)异步总线。设备之间没有统一的系统时钟，设备自己内部定时。设备之间的信息传送用总线发送器和接收器控制。容易适应更广泛的设备类型，扩充总线时不用担心时钟时序和时钟同步问题。但在传输时，异步总线需要额外的同步开销。

输入输出系统概述

经历了3个阶段对应着3种方式：程序控制I/O（程序查询、中断驱动）、直接存储器访问（DMA）、I/O处理机方式（通道、外围处理机PPU）。

输入输出设备分外存和传输设备两大类。

总线设计

总线分类：半双工、全双工；

芯片级、板级（局部总线）、系统级；

专用总线、非专用总线。

根据信息传送方式的不同通道分为三种类型：

（1）字节多路通道：一种简单的共享通道，主要为多台低速或中速的外围设备服务。传送过程：通道每连接一个外围设备，只传送一个字节，然后又与另一台设备连接，并传送一个字节。

（2）数组多路通道：适于为高速设备服务。传送过程：每连接一台高速设备，一般传送一个数据块，传送完成后，又与另一台高速设备连接，再传送一个数据块。

（3）选择通道：为多台高速外围设备服务。传送过程：在选择通道中，通道每连接一个外围设备，就把这个设备的n个字节全部传送完成，然后再与另一台设备相连接。

通道处理机：能够执行有限I/O指令，并且能够被多台外围设备共享的小型DMA专用处理机。通道完成一次数据传输的主要过程？

(1)在用户程序中使用访管指令进入管理程序，由CPU通过管理程序组织一个通道程序，并启动通道。(2)通道处理机执行CPU为它组织的通道程序，完成指定的数据I/O工作。(3)通道程序结束后向CPU发中断请求。CPU响应这个中断请求后，第二次进入操作系统，调用管理程序对I/O中断请求进行处理。通道的主要功能8

(1)接收CPU发来的I/O指令，根据指令要求选择一台指定的外围设备与通道相连接。(2)执行CPU为通道组织的通道程序，从主存中取出通道指令，对通道指令进行译码，并根据需要向被选中的设备控制器发出各种操作命令。(3)给出外围设备的有关地址，即进行读／写操作的数据所在的位置。(4)给出主存缓冲区的首地址，这个缓冲区用来暂时存放从外围设备上输入的数据，或者暂时存放将要输出到外围设备中去的数据。(5)控制外围设备与主存缓冲区之间数据交换的个数，对交换的数据个数进行计数，并判断数据传送工作是否结束。(6)指定传送工作结束时要进行的操作。(7)检查外围设备的工作状态是正常或故障。根据需要将设备的状态信息送往主存指定单元保存。(8)在数据传输过程中完成必要的格式变换。

篇2：计算机体系结构总结

1.层次机构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构。这些层次依次为：微程序机器级，传统机器级，操作系统机器级，汇编语言机器级，高级语言机器级，应用语言机器级等。

2.翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。

解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。

解释比翻译花的时间多，存储空间占用少。

3.虚拟机：用软件实现的机器。以区别于由硬件或固件实现的实际机器。

4.计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。5.透明性：在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。

三种分类：Fllynn，冯氏，Handler。

6.计算机组成：计算机系统结构的逻辑实现，计算机实现：计算机组成的物理实现，一种体系结构可以有多种组成。一种组成可以有多种实现。

址。3寄存器寻址是指在指令的地址码部分直接给出操作数所在的寄存器编号。而所需的操作数就在这个寄存器中4.寄存器间接寻址，寄存器给的不是操作数而是操作数地址，可以用这一地址去读写存储器相关单元。

三．数据表示与指令系统设计 1.数据表示：是指能由机器硬件直接识别、可以被指令系统直接调用的数据类型。

数据结构:研究的是面向系统软件、应用领域所需要处理的各种数据类型，研究这些数据类型的逻辑结构和物理结构之间的关系，并给出相应的算法。数据表示是结构的组成元素，都是数据类型的子集。是硬软件交界面。

2.定点数：数据表示中小数点位置固定的数据，分为纯整数和纯小数.纯整数：最大数（Rm的n次-1）最小数（-Rm的n次）表数个数（Rm的n+1次）

纯小数：最大数（1-Rm的-n次）最小数（-Rm的-n次）表数个数（Rm的n+1次）。

3.浮点数

第一种：

单精度：A =(-1)S*2E-127 *1.F 双精度：A =(-1)S*2E-1023 *1.F

7.冯诺依曼特点：1.机器以运算器为中心2.采用存储程序原理3.存储器是按地址访问的，线性编址的空间4.控制流由指令流产生5.指令由操作码和地址码组成6.数据以二进制编码表示，采用二进制运算。

范围：1to(2-2的-23次)

Nmreerg

8.计算机应用的发展可以归纳为：数据处理，信息处理，知识处理，智能处理。

9.同型号的计算机。系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不

兼容机：由不同公司厂家生产的具有相同系统结构的计算机。10.软件兼容：一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。差别只是执行时间的不同。

向上（下）兼容：按某档计算机编制的程序，不加修改就能运行于比它高（低）档的计算机。向后（前）兼容：按某个时期投入市场的某种型号计算机编制的程序，不加修改地就能运行于在它之后（前）投入市场的计算机。

软件具有兼容性和可移植性

硬件软件逻辑上等效 11.解决软件可移植性：采用系列机，模拟和仿真，采用统一高级语言。

11.模拟：用软件的方法在一台现有的计算机上实现另一台计算机的指令系统。

仿真：用一台现有计算机上的微程序去解释实现另一台计算机的指令系统。

12.MIPS:每秒百万条指令

MFLOPS：每秒百万条浮点运算指令。无法体现机器性能

指令条数 MIPS指令条数Te=执行时间106MIPS106MFLOPS程序中的浮点操作次数12.大概率事件优先原则：是计算机体系结构设计中最重要和最常用的原则，基本思想CPU执行时间106是：对于大概率事件，赋予它优先的处理权和资源使用权，以获得全局的最优结果。13.Amdahl定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高，受限于该部件的执行时间占总执行时间的百分比。14.15.可改进部分在原系统计算时间中所占比例：改进部分采用改进措施后比没有采用改进措施前性能提高的倍数：Fe

Se

T 1FT0FeFT01n T 0eST01FeeSSnTn1FFeeeeCPU CPU时钟周期数 时间=SCPU时间=CPU时钟周期数时钟周期长度e 时钟频率CPU时钟周期数CPU时间 = CPIIC时钟周期长度= ICCPICPI = IC时钟频率16.IC：执行指令条数

CPI：平均时钟周期数

MIPS=f(MHz)/ CPI

17.程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。包括时间局部性和空间局部性。时间局部性：程序即将用到的信息很可能是目前正在使用的信息。空间局部性：程序即将用到的信息很可能与目前正在使用的信息在空间上相邻或接近。

CPU时间=用户CPU时间和系统CPU时间。

二．现代计算机组成

1.冯诺依曼体系：1运算器和控制器成为中央处理机，CPU是硬件系统核心，用于数据加工处理，完成各种算术，逻辑运算及各种控制功能。2存储器是记忆设备，分内存和外存。3输入输出设备是计算机与外界交换信息的装置。

2.CPU：由控制器，运算器和寄存器组成。控制器是计算机控制中心，运算器是计算机对数据进行加工处理的中心，寄存器是CPU内部临时存储单元，容量小速度快。3.寻址方式：解决的是指令中如何提供操作数及操作数地址等问题。

分为立即数寻址，直接寻址，寄存器寻址，寄存器间接寻址，变址寻址，基址寻址，相对寻址。4.设备和算法的总称。存储系统：计算机中存放程序和数据的各种存储设备，控制部件及管理信息调度的主要指标：大容量，高速度，低价格。

5.程序访问局部性原因：1程序进行时，除了少部分的转移和过程调用指令外，大多数情况下仍是顺序执行。2过程调用深度值大多数情况不超过5，3程序中存在循环结构 4.7.程序中包括许多对数据结构的处理输入输出系统作用：1.提供人机交互接口。

2.完成数据格式的转换。3.是重要的存储媒介。4.为各领域提供应用手段。

8.件提供互连和信息传输的一组公共信号线。总线:是多个系统功能部件之间进行数据传送的公共通路，或者说是能为多个功能部

工作原理：当多个设备连接在总线上时，其中一个设备发出的信号可以为其他所有设备接收，但是在某个时段内，只有一个设备能成功发出信号，总线数据传输过程分为：总线申请与裁决，总线寻址，数据传送及错误检测等。

9.单总线结构：所有部件，设备连接到这组总线。结构简单，成本低，易于接入新的设备，不利于提高总线的数据传输率。

10.双总线结构：CPU和主存间设置一组高速存储总线。

11.三总线结构：在双总线基础上增加一组从存储器到高速I/O的总线，DMA总线、主存总线用于CPU和主存之间的信息传送；I/O总线用于CPU和各个I/O之间进行信息传输；DMA总线用于高速外设和主存之间的信息交换。DMA和主存总线不能同时访问主存。

目前常用——Cache总线，主存总线，I/O总线三级总线结构。

12.配。CPU

和 接口功能I/O处理匹配：数据缓冲功能，接受和执行：速度不匹配，时序不匹配，信息格式不匹配，信息类型不匹CPU命令功能，信号转换功能，地址译码和设备选择功能，中断管理功能，可编程功能。

13.操作数地址。四种基本寻址方式区别2直接寻址是指在指令的地址码部分给出的就是操作数在存储器中的地：1立即数寻址指令的地址码部分就是指令操作数，而不是第二种：m:尾数的值

e：阶码的值

Rm：尾数的基

Re：阶码的基

p：尾数长度

q：阶码长度m e

3.四种舍入法：截断法，舍入法，恒置法，查表舍入法。

4.常用的编址方式：隐含编址，统一编址，独立编址。

隐含编址：操作码隐含了其寻址方式。统一编址：将I/O端口地址和存储器地址合为一体，进行统一编址。

独立编址：将I/O与存储器分别单独编址。

5.寻址技术：系统寻找数据或其他有用信息的地址的技术。

寻址方式：指令系统中如何形成所要访问的数据的地址。

三类面向：面向主存，面向寄存器，面向堆栈。6.逻辑地址：计算机系统的各个源程序或程序段是从自己的零地址开始分配地址空间的。

物理地址：程序调入主存中占用的实际地址称为物理地址。

7.数的类型。指令一般由操作码和地址码组成。

地址码包括操作数地址，地址的附加信息和寻址方式等信息。

操作码通常包括指令的操作种类和所用的操作 8.指令格式优化：操作码优化+地址码优化。

9.息量。操作码优化可以通过信息源熵和信息冗余衡量。

操作码编码分为：固定长度编码，Huffman

编码和扩展编码。信息源熵是信息源所含的平均信

10.Huffman编码不是唯一的，操作码的平均码长是唯一的，且肯定是可用二进制位编码平均码长最短的编码。

信息冗余=（实际平均码长-H）/实际平均码长

11.地址码个数选择标准：程序的存储量（越小越好）和程序的执行速度（越快越好）。12.地址码指令：1零地址指令，只有操作码没有地址码。2一地址指令，包含一个地址字段。3二地址指令，两个操作数地址，源和目标地址。4三地址指令，两个源操作地址，一个目标操作数地址。

13.DLX指令格式：I类指令，J类指令，R类指令。

14.的目的存储器基地址I类指令：1.Store指令： 2.LordOP指令：为操作码，OP为操作码，Ra为要读取的源寄存器地址，Ra为要写入的目的寄存器地址，Rb为要写入Rb为要读取的源存储器基地址。3移位指令格式：Ra：要写入的目的寄存器地址，Rs是要进行移位操作的源寄存器，保留10位，5位Imm是移位的位数

4.有一个立即数指令：Ra为目的寄存器地址，Rd为源操作数地址，Imm为立即数。5.条件分支指令：Rb为判断跳转条件，Rb空缺，Imm为16位偏移量。6.寄存器跳转指令：Ra空缺，Rb15.J为跳转的目的基地址，类指令：OP，0-25位在跳转指令中为跳转地址，在中断指令中为中断向量号。Imm为跳转的偏移地址。

16.R类指令：1.算术/逻辑运算指令：OP为操作码，Ra为目的寄存器，Rs，Rt为源寄存器，Func包含四位指令扩展功能码和6位保留。2.移位指令：OP为操作码，Rd为移位目的寄存器，Rs为移位源操作数寄存器，Rt为移位位数寄存器，Func同上。3.第一类寄存器间数据传输指令：OP为操作码，Rd为目的寄存器，Rs，Rt保留，Func同上。4.第二类寄存器间数据传输指令：OP为操作码，Rd空缺，Rs为移位源操作数寄存器，Rt空缺，Func同上

17.CISC（Complex Instruction Set Computer）：复杂指令集计算机

缺点：1.各种指令的使用频率相差悬殊 2.带来了计算机体系结构的复杂性 3.不利于单片集成 4.运行速度慢 5.不利于采用先进的计算机体系结构技术来提高性能。

18.RISC(Reduced Instruction Set Computer): 精简指令集计算机

设计原则：1.选取使用频率最高的指令，并补充一些最有用的指令 2.每条指令功能尽可能简单，并在一个机器周期内完成 3.所有指令长度相同 4.只有Load和Store才能防问存储器，其余在寄存器中进行 5.以简单有效的方式支持高级语言。

19.的指令使用量则很少，仅占整个程序使用量的二八定理：20%的指令反复地执行，使用量占据整个程序使用量20%。80%：而剩下80%20.现代微处理机主频提升的原因：先延迟，功耗。

21.3.计算机价格的发展趋势。计算机系统设计中设计者应考虑的因素

：1.技术发展趋势 2.计算机使用的发展趋势 22.线延迟墙：随着集成电路工艺的进步，芯片内晶体管大小不断变小，其逻辑门延迟也随之减小，而走线延迟所占的比重也随之越来越大，导致电路频率不能随着工艺的减小而线性减小。

23.指令集结构设计考虑的问题以及解决方法：1.指令及功能设计：RISC和CISC。2.寻址方式设计：可以对基准程序进行测试统计，查看使用频度，确定寻址方式。3.操作数表示和操作数类型：浮点型，整形，字符型。4.寻址方式表示：寻址方式可以编入操作码（速度快，增大了CPU译码难度）也可以单独处理（速度慢，易于指令扩展）5.指令集格式设计：固定长，可变长，混合编码。

24.指令集基本要求：完整性，规整性，高效率，兼容性。

25.区别不同指令集结构的主要因素：区别不同指令集结构的主要因素是CPU中用来存储操作数的存储单元。据此可将指令分为堆栈结构、累加器结构和通用寄存器结构。四，存储系统

1.存储器容量Sm=W*l*m。W为存储体字长，l为每个存储体字数，m为并行存储体个数。访问时间TA：存储器从接到访存申请到信息被读到数据总线上所需时间。存储周期TM：是连续启动一个存储体所需要的时间间隔，一般大于TA。频宽Bm：存储器可以提供的数据传输率。容量大价格低，速度越快价格越高，容量越大速度越慢。2.存储系统目的：1.组织好速度，容量，价格不同的存储器，2.使这个存储器速度接近速度最快的存储器。3.存储容量接近容量最大的存储器。4.单位价格接近最便宜。3.命中率H：由CPU产生的逻辑地址在存储器M访问到指定信息的概率。

4.平均访问时间T=H*T1+(1-H)*T2 提高存储器系统速度两条途径：1.提高命中率。2.使构成存储系统的相邻两个存储器速度之比不要太大。

5.虚拟存储器：是“主存-辅存”存储层次的发展和完善，它使该存储层次具有辅存容量，接近主存的等效速度和辅存的每位价格。多个进程共享主存空间。

6.虚拟地址：是应用程序员对程序进行翻译生成的访问地址，它表示的存储空间为虚存空间。实地址：是指主存储器或磁盘存储器的物理地址，表示的存储空间为主存物理空间。

7.地址映像：虚拟存储器中虚拟地址和物理地址之间的对应关系的规则。

8.地址变换：虚拟存储系统按照某种地址映像方式把虚拟地址变换为主存实地址。9.虚拟存储器工作原理：页式虚拟存储器是比较广泛的一种。把主存储器，磁盘存储器和虚拟存储器都分成固定大小的页，每一页容纳字数相同。当用户要访问虚拟存储器时，必须给出多用户虚地址Av；如果未命中，必须访问辅存，需要进行外部地址变换；如果主存储器中没有空页，利用某种替换算法处理。

10.管理方式：1.段式：将虚地址通过段表找到段的基地址，然后形成物理地址，访问存储器。2.页式。3.段页式：把实存机械的等分成固定大小的页，把程序按模块分段，每个段分成与主存页面大小相同的页，每道程序通过一个段表和相应于每段的一组页表来进行定位。

10.页面替换算法：1.随机替换算法（RAND）：利用软件或硬件的随机数发生器来确定11.中断源：把凡能向CPU提出中断请求的各种因素统称为中断源。

中断软硬功能分配：一是中断响应时间，二是灵活性。要在硬件的快速性和软件的灵活性之间进行综合权衡。必须硬件：保存中断点和进入中断服务程序入口。必须软件：中断服务和返回到中断点。

12.中断屏蔽：为提高中断系统灵活性，可以动态改变中断源优先级

用处：(1)在中断优先级由硬件确定了的情况下，改变中断源的中断服务顺序。(2)决定设备是否采用中断方式工作。(3)在多处理机系统中，把外围设备的服务工作分配到不同的处理机中。

13.四种I/O工作方式：程序控制，中断，DMA I/O处理机。

六．流水线技术

1.指令执行过程：1.取指令。按照指令计数器的内容访问主存。2.分析指令。对指令寄存器中的指令进行译码分析。3.执行指令。对操作数进行运算处理，完成指定功能。2.重叠方式：1.顺序执行方式（串行执行）。T=3nt，控制简单，利用率低，速度慢。2.一次重叠方式：指第i条指令的执行阶段和第i+1条指令的取指令阶段同时进行。T=（1+2n）t,利用率中，速度中，控制复杂。3.二次重叠方式：指第i条指令的执行阶段，第i+1条指令的分析阶段和第i+2条指令的取指令阶段同时进行。T=（2+n）t，利用率高，速度快，需要解决问题：1.必须有独立的取指令部件，指令分析部件和指令执行部件。2.要解决访问主存冲突问题。

3.解决访问主存冲突问题：1.把主存分成两个独立编址的存储器，一个指令存储器，一个数据存储器。2.主存采用低位交叉编址的秉性存储器。3.采用先行控制技术。

4.先行指令缓冲栈：平滑主存和指令分

析器的工作。指令分析器：从先行指令

缓冲栈取得指令后就行预处理。先行操

作栈：是指令分析器和运算控制器之间的一个缓冲存储器。先行读书栈：平滑

运算器与主存储器的工作。后行写数栈 主存储器中被替换页的页号。2.先进先出替换算法(FIFO)：选择最早装入主存的页作为被替换的页。3.近期最少使用算法：选择近期最少访问的页面作为被替换页面。4.最久没用使用的算法(LFU)：把近期最久没有访问过的页面作为被替换的页面。5.最后的算法应该是选择将来最久不被访问的页面作为被替换的页面，命中率一定最高，但只是理想标准。

11.为页数减少了。虚拟存储器性能2.主存容量，当主存容量增加到一定值，对命中率影响不大。：1.页面大小，当页大小增加到一定值时，命中率反而降低，是因3.页面调度方式：分页方式，请求页式，预取式+请求页式结合。

12.13.Cache命中时间：高速缓冲存储器是在：访问Cache命中时所用的时间。CPU与主存之间设置的一个高速度，小容量存储器。

失效率：CPU访存时，在一级存储器 中找不到所需信息的概率。

失效开销：CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。

Cache平均访问时间=命中时间+失效率*失效开销。14.Cache与虚拟存储器的不同：1.Cache与主存之间以块为单位进行数据交换。2.两级存储器的速度比不同。3.CPU和Cache之间和CPU与主存之间都有直接通路。4.Cache系统以提高存储系统速度为目标，虚拟存储系统以扩大存储系统容量为目标。

13.基本工作原理：Cache与主存分成大小相同的块，主存地址由块号B和块内地址W组成，Cache地址由块号b和块内地址w组成。由于块相等，块内地址相同。、15.复杂）地址映像及变换方式：主存中的任意一块可以映像到：1.全相联映像及变换（利用率最高，冲突概率最低，实现最Cache中任意一块位置上。2.直接相联映像及变换（利用率最低，冲突概率最高，实现最简单）：虽然也是多对一，但一个主存块只能映像到Cache的一个特定块上去。3.组相联映像及变换：把主存按Cache容量分区，主存中各区和Cache再按同样大小分成相同数量的组，组内按同样大小分成相同数量的块，主存组到Cache组间采用直接映像方式，两个对应的组的块之间采用全相联映像方式。4.段相联映像方式：实质上是组相联的特例。5.位选择组相联及其变换：与一般组相联映像方式不同，Cache仍然分组，主存不分组。

16.提高Cache性能方法：1.命中率与容量关系。2.命中率与块大小关系。3.命中率与组数关系：Cache容量一定时，分组的数目对命中率的影响是很明显的，随着分组数目增加，组内的块数减少，命中率下降。4.命中率与Cache组织方式间的关系：容量一定，全相联命中率比直接相联高。

17.体，避免存储体冲突。提高主存性能方法：增加存储器宽度，采用简单的多体交叉存储器，采用独立存储

18.从哪几方面改进主存性能：降低失效率，减少失效开销，减少Cache命中时间。

五．输入输出系统

1.输入输出系统：把处理机与主存储器之外的部分统称为输入输出系统。包括输入输出设备、输入输出接口和输入输出软件等。

2.输入输出系统特点：1.异步性：各个设备按照自己时钟工作。2.与设备无关性：设有独立于具体设备的标准接口。3.实时性。针对异步性，采用自治控制方针，针对与设备无关性，采用分类处理方法，针对实时性，采用层次结构的方法。

3.基本输入输出方式：1.程序查询方式：不断查询I/O准备情况。2.中断输入输出方式。3.直接存储器访问方式（DMA）：主存和I/O设备交换信息时，无需处理中断服务程序。

4.通道方式。5.I/O处理机方式

4.DMA特点：1.主存储器可以被CPU访问，也可以被外围设备访问。2.外设与主存之间传送数据不需要执行程序，也不动用CPU中的资源。3.在DMA开始之前，CPU要对DMA控制器进行初始化。

5.总线分类：1.在计算机结构中所在位置：片内总线，片总线，内总线，外总线。2.传递信息类型：数据总线，地址总线，控制总线。3.信息传送方向：单向和双向。4.总线用途：CPU-存储器总线和I/O总线。5.信息在总线上传送方式：同步和异步。

6.总线仲裁：解决的是多个设备竞争使用总线的管理问题，由总线仲裁逻辑线路完成。7.总线控制方式：1.集中式串行链接控制：选择算法简单，可扩充性好，可靠性差，灵活性差，分配速度低。2.集中式定时查询控制：灵活性好，可靠性高，可扩充性差，辅助总线多，分配速度低。3.集中式独立请求控制：分配速度高，灵活性好，可靠性高，辅助总线多，可扩充性差，复杂价格高。

8.步通信。总线的通行方式4.双向互锁异步通信。：1.单向源控式异步通信。2.单向目控式异步通信。3.双向非互锁异9.总线指标：总线宽度：通常指其一次操作可以传输的数据位数。总线频率：是总线工作的最高频率时钟

单个数据传送周期数。

10.中断：当出现异常情况或者特殊请求时，计算机停止现行程序的运行，转向对这些异常情况或特殊请求的处理，处理结束后再返回到现行程序的间断处。

：是主存储器与运算器之间的一个缓冲

存储器。

4.执行指令部件完全独立的工作。并始终处于忙碌状态。先行控制技术是缓冲技术和预处理技术的结合。

使取指令部件，分析指令部件和

5.流水线技术：流水线技术是指将一个重复的时序过程分解为若干个子过程，每一个子过程都可有效地在其专用功能段上与其他子过程同时执行。

6.时空图：横坐标表示时间：即输入到流水线中的各个任务在流水线中所经过的时间；纵坐标表示空间：即流水线的各个子过程。从横坐标方向看，流水线中的各个功能部件在逐个连续地完成自己的任务。

从纵坐标方向看，在同一个时间段内有多个流水段在同时工作，执行不同的任务。

7.流水线特点：1.把一个大的功能部件分解为多个独立的功能部件。2.每一个功能部件后面都有一个缓冲寄存器，3.工作一般分为时间段，装入时间，装满和排空时间。4.流水线中各段时间应尽量相等，长的功能段将成为其瓶颈，造成堵塞和断流。5.流水线技术适合大量同类任务，只有向连续不断提供任务，其效率才能充分发挥。8.行分段，再把这些部件分段相互连接而成。它使得运算操作能够按流水方式进行。这流水线分类：1.按级别分：部件级流水线（运算操作流水线）：把处理机中的部件进种流水线也称为运算操作流水线。处理机级流水线（指令流水线）：它是把指令的执行过程按照流水方式进行处理，即把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。

处理机间流水线（宏流水线）：它是把多个处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入。

2.按反馈回路分：线性流水线（各段逐个串接起来）非线性流水线（除了有串行连接，还有反馈回路）3.功能多少分：单功能和多功能。4.同一时间各段连接方式：静态（指同一时段，多功能流水线中各个流水段只能按照一个固定方式连接，实现固定功能）和动态（指同一时段，多功能流水线中各段可以按照不同方式连接，同时执行多种功能）。5.按数据表示分：标量处理机（只能同时对一个或一对标量操作数进行运算或操作指令）和向量处理机（可以同时处理相同类型的多个或多对数据）。

8.吞吐率：单位时间内流水线完成的任务数或输出的结果数。TP=N/Tk

N:任务数，Tk完成n个任务所用的时间。

最大吞吐率受限于瓶颈子过程，要提高最大吞吐率，设法取消瓶颈功能段。方法有：1.将流水线瓶颈部分再细分。2.重复设置瓶颈功能段，让多个瓶颈部件并行工作。

9.加速比：是指完成一批任务时，不采用流水线所用时间与采用流水线所用的时间之比。S=T0/Tk。T0:顺序方式下执行时间 最大加速比与流水线的功能段数相等。10.效率：是指流水线的设备利用率。时空图上是n个任务占的时空区和k个功能段总的时空区之比

E=T0/KTk

E=TP*t

E=S/k 11.12.相关包括资源相关：资源相关，数据相关，控制相关。：指多条指令进入流水线后，同一时间争用同一功能部件从而发生的冲突。一般采用延迟执行和细分功能部件来解决。

数据相关:又称局部相关，指令在流水线中执行时，使得原来对操作数的访问顺序发生变化，对数据的读写操作顺序不同于指令在顺序方式下执行时的顺序，从而导致对数据的访问发生错误。

数据相关分为：先写后读，先读后写，写后写。

解决方法有：推迟处理，设置专用路径。

控制相关：又称全局相关，是由程序执行转移类指令而引起的相关。它的影响范围比较大，会引起程序执行方向的改变。解决方法有：改进硬件功能，采用预测分支失败机制，采用延迟分支机制。

13.码。减少条件转移对流水线的影响3.转移预测技术。分为静态转移预测和动态转移预测。：1.延迟转移技术和指令取消技术。2.提前形成条件14.静态转移预测：指在处理机的硬件和软件设计完成后，转移预测的方向就已经确定，在程序实际执行过程中，转移预测的方向不能改变。分为：软件猜测法，硬件猜测法和设置两个指令缓冲栈。

15.动态转移预测技术：是根据近期转移是否成功的历史记录来预测下一次转移的方向，它能够随程序的执行过程动态地改变转移的预测方向。分为：在指令Cache中记录转移历史记录，转移目标地址缓冲栈，转移指令功能缓冲栈。

16.中断：中断请求是随机发生的，不可预知的。

不精确断点：凡是已经进入流水线的指令都执行完成，断点就是最后进入流水线的那条指令的地址。

精确断点：是对于在流水线中同时执行的多条指令，如果有哪一条指令由于程序错误或者故障发出中断申请，断点就是那条指令的地址。

17.过程中，可能会多次通过同一个功能段或越过某个功能段。非线性流水线的调度技术：在非线性流水线中，功能段间有反馈回路，任务在执行

如果每个时钟周期向流水线送入一个新任务，将会发生多个任务争用同一个功能段的冲突现象。

一张非线性流水线的预约表可能与多个非线性流水线的连接图相对应；一个非线性流水线的连接图也可能与多个非线性流水线的预约表相对应。

19.非线性流水线的启动距离：是指向一条非线性流水线的输入端连续输入两个任务之间的时间间隔，它通常用时钟周期数表示。

非线性流水线调度的任务：就是找出一个最小的启动循环周期，按照这个周期向流水线输入任务，流水线的各个功能段都不会发生冲突。同时，非线性流水线的吞吐率和效率最高。

20.水线的状态图（当初始冲突向量确定后，状态图就是唯一的，由于不同的预约表可能非线性流水线的调度方法步骤：1.写出禁止向量和初始冲突向量。2.画出非线性流产生相同的初始冲突向量，因此从预约表可以画出状态图，但从状态图不能得到预约表）。3.求出最小启动循环（指平均启动距离最小的启动循环）和最小平均启动距离。4.求平均启动距离最小的恒定循环。

21.多指令流水线技术：在一般流水线标量处理机的基础上，提出提高指令级并行的高性能超级处理机，让单个处理机在每个时钟周期里可以执行多条指令。

22.超标量处理机：指在一个时钟周期内能够同时发射两条或者两条以上的指令的处理机。

超流水线处理机：指在一个时钟周期内分时发射多条指令的处理机。

篇3：计算机软件应用体系结构模型研究

0前言

1946年在美国宾夕法尼亚大学, 世界上第一台电子计算机ENIAC的诞生, 成为了一个衡量国家综合国力强弱的重要指标。从第一代计算机的诞生至今, 计算机经历了晶体管计算机时代、小规模集成电路的计算机时代以及超大规模集成电路时代。到目前为止, 计算机软件应用体系结构模型领域研究已相当成熟, 根据计算机数据与用户之间所存在的层次划分, 可将计算机软件应用划分为两层应用体系结构模型、多层应用体系结构模型以及单层应用体系结构模型三种软件体系结构模式[1]。

1 计算机软件应用的两层应用体系结构模型

计算机软件应用的两层应用体系结构模型主要是将商业规则与用户界面有效地结合起来组成计算机应用程序的客户端中。计算机数据的读取、储存以及查询都是由不同的系统完成的。例如我们熟悉的Client/Server属于两层应用体系结构, 大部分应用在局域网中。

两层应用体系结构模型中还有一种应用情况, 以用户界面独立成为一层, 将商业规则与数据处理相结合组成另一层。体现出计算机商业规则, 通过两层应用体系结构将计算机数据库内的存储过程实现。存储过程可以说是计算机数据库系统中的一个重要部分, 数据库服务器体现了每一个存储过程与操作。此外, 在存储过程中, 用户可以通过客户端查询与停用[2]。

两层应用体系结构模型的优势, 可以使每个用户同时对相同的数据进行读取与储存, 使每个用户都能与主服务器连接, 即每个用户都可以访问。同样两层应用体系结构模型的不足之处也十分明显, 那就是服务器端的负载问题。当用户人数过多时, 会加大服务器端的负载量, 造成系统承受不了过多用户而系统崩溃的现象。

2 多层应用体系结构模型

多层应用体系结构模型是由商业规则客户端中分立出来的, 不需要将各应用层与网络物理拓扑之间一一的对应, 可以根据用户的要求与条件, 对系统进行分布在不同的位置[3]。

通过多层应用体系结构模型可以进行所以商业过程, 例如商业规则的处理与正确执行等。多层应用体系结构模型不可以直接进行计算机数据的存取, 有利于保障计算机数据的安全性与完整性。多层应用体系结构模型在进行应用系统的修改时, 对其他部分不会产生任何影响。因为每一层之间通过接口互相连接, 不影响计算机内部程序的变化, 这也是多层应用体系结构模型的优势。同时多层应用体系结构模型也有利于计算机应用程序的管理、维护、复用等功能。

3 单层应用体系结构模型

计算机软件应用的单层应用体系结构模型是指通过单一的应用层, 实现计算机数据的管理、用户界面、数据管理、应用程序等功能。计算机中的数据是物理上处于远端的位置, 并且数据的存取逻辑是计算机应用程序中的一个重要组成部分。在单层体系结构中, 数据的处理通常采用文件夹来实现, 而不是数据库。应用程序自己进行定义如何进行数据的读取、存储以及逻辑运算等[4]。此外, 在单层应用体系还可以进行文字处理以、应用文件的存取以及数据文档的管理功能。现在我们生活中常用的计算机Windows XP或者是Windows7应用操作系统都是属于单层应用体系结构模型。单层应用体系结构模型的优势是可以将计算机应用程序的前期分析与设计简单化, 易于用户的理解与操作, 同时单层应用体系结构模型也存在着一定的不足, 即在用户操作程序后期的维护与管理上显得有些不足, 这是由于计算机在进行任何改动时, 哪怕是一个字符, 都可能会影响计算机的正常运行。

4 结语

21世纪是信息化时代, 随着科学技术的不断发展, 人们的生活也越来越离不开计算机等电子产品。随着计算机在各个行业中的不断应用, 加强计算机软件应用体系结构模型的研究, 了解计算机软件应用系统结构, 加大对计算机软件应用系统结构的开发与应用, 可以促进计算机软件应用体系的开发与利用[5]。

参考文献

[1]童益民.计算机软件应用体系结构模型研究[J].中国高新技术企业, 2011, 36 (11) :149-153

[2]殷仲磊, 赵广鹏.关于计算机数据库入侵检测技术的几点思考[J].软件, 2012, 33 (5) :70-72

[3]周枫.软件体系结构模型的分析及研究[J].昆明理工大学学报 (理工版) , 2012, 29 (20) 114-116

[4]李芳芳.基于分布式结构的教学管理信息系统的设计[J].软件, 2012, 33 (5) :127-128

篇4：计算机体系结构软件模拟技术

关键词：计算机体系 软件模拟 精度

当前社会早已进入了计算机时代，人们的日常生活和工作都离不开计算机辅助，计算机技术也不断更新，变得更为复杂，处理器技术也越来越复杂。现在单片处理器的晶体管数量已超过10亿。这样就给计算机系统的制造带来了资金成本和时间成本上的大幅度增加。为了解决这个问题，计算机体系结构软件模拟技术就成为研发人员的首选。这种技术可以精确到时钟级别，从根本上解决了计算机体系结构研发的长时间和高成本问题。

1 计算机体系结构软件模拟技术的发展历程

1.1 萌芽阶段 计算机体系结构软件模拟技术的发展经历了一个漫长的过程。计算机软件模拟技术的结构虽然已经建立，但是处理器技术并不完善，对系统运行也不能进行合理控制，由于处理器的工作效率低下，所以控制软件的设计也非常缓慢，计算机体系结构的软件模拟技术在不断的探索中缓慢前行。上世纪八十年代，我国的计算机技术有了长足发展，经过长期不懈的研究，我国计算机系统在独立操作数据驱动和处理器高效利用技术两方面有了新的突破。至此，软件系统可以在计算机上进行更好地运行，计算机系统的控制也更为便捷。计算机的运行是以收集和处理技术为基础的。所以，在计算机应用软件技术的研发过程中要收集大量的数据，并结合计算机基础知识在计算机处理器平台上对软件系统进行构建和设计。这是计算机体系结构软件模拟技术发展的重要前提，技术人员由此掌握了计算机软件系统建设的大量数据经验。

1.2 技术研发阶段 研发人员运用性能分析模拟技术改良了计算机系统，这样，团建模拟技术就可以在处理器中进行合理运用。计算机系统的质量得到了大幅度的提高，软件模拟技术也开始被广泛运用在计算机系统结构软件的研发中。计算机体系结构软件的模拟技术可以对系统运行进行更加顺利和有效的控制，再結合性能分析模拟技术，计算机系统的研发成本急剧下降。这样就降低了技术研发阶段的风险，从根本上节省了大量的时间成本和资金成本，保障了研发单位的经济利益。在技术研发时，还要考虑到计算机系统升级、实际应用，使计算机技术的实用性大幅度提高，计算机系统的工作能力成倍增加。

2 开发计算机体系结构软件模拟技术面临的问题

2.1 设备的研发难度非常之高 计算机是一套非常复杂的系统，如果笼统地将计算机的各种特点都运用软件系统模拟是几乎不可能实现的。面对这个问题，研究人员采用了计算机系统的层次划分技术，使原本复杂的计算机系统变得相对简单化。计算机体系结构就是将计算机系统根据组成机构进行层次划分。简化后的计算机系统的复杂性依然很高，给模拟设备的开发造成了很大困难，目前计算机体系结构软件模拟设备的开发主要利用C语言来进行，这种串行结构编程语言给模拟器的实际开发造成了长时间、高成本的问题。

2.2 模拟设备精度低，运作效果差 模拟设备的精度低，效率差也是计算机体系结构软件模拟设备开发中遇到的问题，在开发过程中，对模拟器的具体要求未能进行准确的分析研究；未能透彻理解计算机体系结构的真正目的等都大大增加了错误率。另外，一般的研究开发人员将整体的运行效果用检测流程中的部分程序指令代替，造成了模拟设备精度低的问题。

3 计算机体系结构软件模拟技术开发中问题的应对策略

3.1 将检测流程中的执行指令进行合理减少 性能检测流程中标准化指令是不能改变的，但是可以在此基础上对系统性能检测流程中的执行指令进行科学而合理的减少和更正，使模拟器的运行结构能表现整体运行效果。这样就可以使模拟器的运作时间大幅度减少，缩短运行周期。

3.2 对模拟程序的指令数量进行适当减少 选择准确的模拟程序指令代替原系统整体运作结果，对模拟程序的指令数量进行适当减少，可以提高模拟系统的精确度。在选择模拟程序指令的时候，可以采取抽样选择程序指令或者是直接结构连续性指令的方式。一般来说都是采用抽样统计的方式选取程序指令，因为其精准度更高。

4 结语

当前社会已进入数字化和信息化时代，计算机技术在人们的日常生活和工作中运用程度越来越高，人们对计算机的性能也不断提出更高的要求。因此，计算机体系结构软件的模拟技术的运用也越来越广泛，成为软件开发必不可少的条件。计算机应用功能的完善需要开发人员不断探索和研究。在开发过程中，技术人员要采用正确而有效的方式应对开发过程中出现的各种问题。这样才能有效降低软件开发的周期，节省开发成本，并开发出实用性高的计算机应用软件。

参考文献：

[1]许建卫，陈明宇，杨伟，潘晓雷，郑规，赵健博，孙凝晖.计算机体系结构模拟器技术和发展[J].系统仿真学报，2009（20）.

[2]包云岗，许建卫，陈明宇，樊建平.一种新型计算机体系结构模拟器的研究与实现[J].系统仿真学报，2007（07）.

[3]沈绪榜，刘泽响，王茹.计算机体系结构的统一模型[J].计算机学报，2007（05）.

篇5：计算机体系结构总结

电子线路--微程序机器级--传统机器级--操作系统级---汇编语言级--高级语言级--应用语言级 4.Amdahl定律：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占用总执行时间的比例有关。

5.9.CPU时间：一个程序所花的CPU时间（CPU的执行时间，不包括I/O等待时间）。CPU时间=CPU时钟周期数*时钟周期长度=CPU时钟周期数/频率 CPU时间 ＝（CPI×IC（指令条数））/ 频率

时钟周期：由于计算机的时钟速度是固定的，它的运行周期称为时钟周期。10.CPI（Cycle Per instruction）：每条指令执行时所花费的平均时钟周期数。IC：每个时钟周期平均执行的指令条数

CPI ＝ CPU时钟周期数 / IC 则 CPU时间 ＝（CPI×IC）/ 频率

11.Te：一个标准测速程序的全部执行时间 Ti:其中所有第i种指令的累计时间

13.MIPS(每秒百万条指令数):衡量机器性能的唯一可靠的标准就是真正的执行程序的时间，可以用MIPS来作为衡量程序执行时间的一个指标。优点：直观、方便。主要缺点:(1)不同指令的执行速度差别很大(2)指令使用频度差别很大（3）有相当多的非功能性指令

单元2 2.数据表示是指计算机硬件能够直接识别，可以被指令系统直接调用的那些数据类型。例如：定点、逻辑、浮点、十进制、字符、字符串、堆栈和向量等

3.数据表示原则：1）缩短程序的运行时间。2）减少CPU与主存储器之间的通信量。3）这种数据表示的通用性和利用率

4.零地址空间个数：三个零地址空间，两个零地址空间，一个零地址空间，隐含编址方式。并行存储器的编址技术：高位交叉编址，低位交叉编址。

7.高位交叉编址：扩大存储器容量。低位交叉编址：提高存储器速度。

者一个存储器操作数。对于存储器操作数来说，由寻址方式确定的存储器地址为有效地址。9.多种寻址方式：显著地减少程序的指令条数，可能增加计算机的实现复杂度和指令的CPI。10.寻址方式：立即数寻址方式，寄存器寻址方式，主存寻址方式（直接寻址、间接寻址、变址寻址），堆栈寻址方式。

11.指令格式的设计：确定指令字的编码方式，包括操作码字段和地址码字段的编码和表示方式。

指令格式的优化：如何用最短的位数来表示指令的操作信息和地址信息。12.操作码的三种编码方法：固定长度、Huffman编码、扩展编码 操作码优化的程度可以用信息熵来衡量。

Hpilog2pii1n

表示用二进制编码表示n个码点时，理论上的最短平均编码长度。信息冗余量为：R=1-（H/平均码长）

13.码长表示法：哈弗曼树、2-4等长扩展编码，1-2-3-5（3-4）扩展编码、2-8扩展编码法、3-7扩展编码法：长码的前缀不能是短码的操作码 14.码点表示法：15/15/15，8/64/512，计算扩展码点：

1.若(16-x):(2的6次方-1)x=1:9 x=2，则扩展码点为2 则双地址的范围为：0000-1101（14条）

单地址为：1110 *** **0，1111 *** **0 126条

零地址为：1110 111 111 *** ***，1111 111 111 *** *** 128条 2.单地址范围：2的6次方-1=63 1111 000 000--1111 111 110 双地址范围：2的（6－2）次方-1=15 0000-1110 零地址范围：1111 1111 1100 0000----1111 1111 1111 1111 15.单地址指令范围为：2的n次方-1（留一个扩展码点）

双地址：2的n-2次方-1 零地址：2的n次方

缩短地址码长度的方法：用一个短地址码表示一个大地址空间

用间址寻址方式、变址寻址方式、寄存器间接寻址方式缩短地址码长度 17.CISC（Complex Instruction Set Computer）：复杂指令系统

增强指令功能，把越来越多的功能交由硬件来实现，且指令的数量也是越来越多。18.RISC（Reduced Instruction Set Computer）：精简指令系统 减少CPI是RISC思想的精华: Ｐ＝Ｉ· CPI · Ｔ

Ｐ是执行这个程序所使用的总的时间；Ｉ是这个程序所需执行的总的指令条数； 尽可能地把指令系统简化，不仅指令的条数少，而且指令的功能也比较简单。

RISC的设计是力争一个最小化的指令集，每条指令只执行一个基本的计算，复杂的运算由基本指令构成的子程序来完成。为了达到最高速度，RISC设计限定指令为固定长度，并使得能在一个时钟周期内执行一条指令。

19.设计RISC机器遵循的原则：1）采用简单而又统一的指令格式，并减少寻址方式；指令字长都为32位或64位。2）指令的执行在单个机器周期内完成；(采用流水线机制)。3）只有load和store指令才能访问存储器，其它指令的操作都是在寄存器之间进行；4）大多数指令都采用硬连逻辑来实现；5）强调优化编译器的作用，为高级语言程序生成优化的代码；6）充分利用流水技术来提高性能 单元三

2.存储器的主要性能：速度、容量、价格

3.Cache存储系统：由Cache和主存储器构成。主要目的：提高存储器速度 4.虚拟存储系统：由主存储器和硬盘构成。主要目的：扩大存储器容量 5.虚拟存储系统：磁盘的地址空间而并不能被一般的指令访问，而主存储器的地址空间对于使用者来说又太小。所以虚拟存储器系统为使用者另外设计一个虚拟地址空间，比主存储器的实际空间大很多，采用与主存储器同样的随机访问方式。

6.命中率定义：CPU访问存储系统时，在M1中找到所需信息的概率。H=N1/(N1+N2)其中：N1是对M1存储器的访问次数,N2是对M2存储器的访问次数

整个存储系统的访问时间可以采用M1和M2的访问周期T1、T2及命中率H来表示H=H*T1+(1-H)*T2 访问效率e=T1/T=T1/[(H乘T1)+(1-H)T2]=1/[H+(1-H)T2/T1]=f(H,T2/T1)提高存储系统速度的两条途径:一是提高命中率H;二是两个存储器的速度不要相差太大。并行访问存储器的冲突：取指冲突，读操作数冲突，写操作数冲突，读写冲突。7.三种虚拟存储器：段式虚拟存储器、页式虚拟存储器、段页式虚拟存储器。

虚拟存储器的工作原理：1）多用户虚拟地址。2）主存地址。3）程序执行时要根据虚拟地址找到主存地址。4）虚拟地址和主存地址之间的关系由地址映像体现出，而在程序执行时通过地址变换将用户程序中的虚拟地址变成主存的实地址

虚拟存储器的页面替换算法：随机算法，先进先出算法，最久没有使用算法，最优替换算法 cache替换算法:随机法,先进先出法FIFO,最近最少使用法LRU(堆栈法)8.影响命中率的因素：（1）程序在执行过程中的页地址流况；（2）所采用的页面替换算法；（3）页面大小；（4）主存储器的容量（5）所采用的页面调度算法。9.（1）Cache命中率随着他的容量的增大而提高；（2）（组相连映射）当cache的容量一定时，命中率随着cache块的增大而提高。（3）在组相连映射中命中率随着组数的增加而减小10.两种cache更新算法：写直达法和写回法。Cache预取算法：按需预取，恒预取，不命中预取。

11.Cache的地址映象与变换：

1.全相联映象：主存中的任一块可以被放置到Cache中的任意一个位置。

特点：空间利用率最高，冲突概率最低，实现最复杂。

2.直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。

特点：空间利用率最低，冲突概率最高，实现最简单。3.组相联映象：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。

组相联是直接映象和全相联的一种折衷。

第四章：输入输出系统

输入输出系统的特点：异步性、实时性、与设备无关性

基本输出输出方式：程序控制方式、中断方式、DMA方式（直接存储器访问方式）程序控制特点：优点：灵活性很好。可以很容易地改变各台外围设备的优先级 缺点：实现处理机与外围设备并行工作困难。

中断方式特点：(1)CPU与外围设备能够并行工作。(2)能够处理异常事件。

(3)数据的输入和输出都要经过CPU。(4)用于连接低速外围设备。

DMA方式特点：(1)外围设备的访问请求直接发往主存储器，数据的传送过程不需要CPU的干预。(2)全部用硬件实现，不需要做保存现场和恢复现场等工作。(3)DMA控制器复杂，需要设置数据寄存器、设备状态控制寄存器、主存地址寄存器、设备地址寄存器和数据交换个数计数器及控制逻辑等。(4)在DMA方式开始和结束时，需要处理机进行管理。DMA操作过程包括三个阶段：DMA请求、DMA响应和数据传送、传送结束

DMA方式的特点：(1)外围设备的访问请求直接发往主存储器，数据的传送过程不需要CPU的干预。(2)全部用硬件实现，不需要做保存现场和恢复现场等工作。(3)DMA控制器复杂，需要设置数据寄存器、设备状态控制寄存器、主存地址寄存器、设备地址寄存器和数据交换个数计数器及控制逻辑等。(4)在DMA方式开始和结束时，需要处理机进行管理。

中断屏蔽：设置中断屏蔽有三个用处：(1)在中断优先级由硬件确定了的情况下，改变中断源的中断服务顺序。(2)决定设备是否采用中断方式工作。(3)在多处理机系统中，把外围设备的服务工作分配到不同的处理机中。

中断屏蔽的实现方法：1）每级中断源设置一个中断屏蔽位。2）改变处理机优先级

中断屏蔽以后，中断源的优先级不会发生改变，动态的改变服务的顺序，响应的顺序由硬件决定，无法改变。

两种方法的不同：(1)两者使用的概念不同。前者使用中断屏蔽； 后者使用中断优先级(2)需要屏蔽码的位数不同。前者所需要的屏蔽位数比较多； n：log2（n+1）

(3)可屏蔽的中断源数量和种类不同。前者可以任意屏蔽掉一个或几个中断源，后者只能屏蔽掉比某一个优先级低的中断源

通道的种类：字节多路通道(为多台低速或中速的外设服务,打印机)、选择通道(为多台高速外围设备服务)、数组多路通道(适用于高速设备；磁盘等设备)；

字节多路通道能够正常的工作，即不丢失数据，可以采用以下几种方式：（1）：增加通道的最大流量；（2）：动态改变设备的优先级；（3）：增加缓冲存储器；

第五章：标量处理机

流水线技术：把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其它的子过程并行进行。

线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。

非线性流水线：流水线中除了有串行的连接外，还有反馈回路 流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。

吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量 Tp=n/Tk n：任务数 Tk：处理完成n个任务所用的时间 流水线的瓶颈段：流水线中这种时间最长的段。

解决流水线瓶颈问题的常用方法：细分瓶颈段，重复设置瓶颈段

加速比：完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比。假设：不使用流水线（即顺序执行）所用的时间为Ts，使用流水线后所用的时间为Tk，则该流水线的加速比为：S=Ts/Tk 流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。

流水线冲突有3种类型：结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。控制冲突：流水线遇到分支指令和其它会改变PC值的指令所引起的冲突 1：流水线：流水线需要有通过时间和排空时间

通过时间：第一个任务从进入流水线到流出结果所需的时间。排空时间：最后一个任务从进入流水线到流出结果所需的时间 时间最长的段将成为流水线的瓶颈

按照流水线中是否有反馈回路可以分为线性流水线与非线性流水线 非线性流水线的调度问题：确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突——争用流水段

流水线的性能指标：吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量 TP=n/T(n:任务数 T：处理完成n个任务所用的时间)多指令流水线技术：CPI<1 超标量处理机：多流水线的调度问题：顺序发射顺序完成；顺序发射乱序完成；乱序发射乱序完成;超标量处理机：一个时钟周期内能够同时发射多条指令的处理机 超流水处理机:一个周期内能够分时发射多条指令的处理机

超标量超流水处理机:超标量技术和超处理机技术的结合。即在一个时钟周期中分时发射n次，每次同时发射m条指令。超标量超流水线处理机在一个时钟周期发射nm条指令。超流水处理机与超标量处理机比较：(1)提高处理机性能的不同方法：超标量处理机是通过增加硬件资源为代价来换取处理机性能的;超流水线处理机则通过各硬件部件充分重叠工作来提高处理机性能。(2)两种不同并行性：超标量处理机采用的是空间并行性;超流水处理机采用的是时间并行性。

相对性能顺序（高-低）:超标量处理机,超标量超流水线处理机，超流水线处理机

第六章：向量处理机

向量由一组有序、具有相同类型和位数的元素组成，特别适合流水处理；

在有些流水线处理机中，为了充分发挥流水线处理机的效率，实现高性能计算，设置了向量数据表示和相应的向量指令，称为向量处理机

不具有向量数据表示和相应的向量指令的流水线处理机，称为标量处理机 向量处理机的结构：存储器-存储器型结构（向量长度不受限）；寄存器-寄存器型结构(讲过)两条向量指令占用功能流水线和向量寄存器的4种情况：（1）：指令不相关（2）：功能部件冲突（3）：源寄存器冲突（4）：目的寄存器冲突 采用链接技术：具有先写后读的两条指令；当前一条指令的结果寄存器是后一条指令的源寄存器、且不存在任何其他冲突时，就用链接技术；

篇6：计算机体系结构总结

1.1 算法

算法：是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程。算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。

(1)确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；

(2)有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；

(3)可行性，算法原则上能够精确地执行；

(4)拥有足够的情报。

算法效率的度量—算法复杂度：算法时间复杂度和算法空间复杂度。★★★

算法时间复杂度：指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。

算法空间复杂度：指执行这个算法所需要的内存空间。

1.2 数据结构的基本概念

数据结构：指相互有关联的数据元素的集合。

数据结构研究的三个方面：

(1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；

(2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

(3)对各种数据结构进行的运算。

线性结构的条件，(一个非空数据结构)：

(1)有且只有一个根结点；(2)每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1.3 线性表及其顺序存储结构

线性表的顺序存储结构具有以下两个基本特点：

(1)线性表中所有元素所占的存储空间是连续的；

(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

顺序表的运算：查找、插入、删除。

1.4线性链表

数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。

结点由两部分组成：

(1)用于存储数据元素值，称为数据域；

(2)用于存放指针，称为指针域，用于指向前一个或后一个结点。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

链式存储方式即可用于表示线性结构，也可用于表示非线性结构。

线性链表的基本运算：查找、插入、删除。

1.5栈和队列★★★★

栈：限定在一端进行插入与删除的线性表。

其允许插入与删除的一端称为栈顶，用指针top表示栈顶位置。

不允许插入与删除的另一端称为栈底，用指针bottom表示栈底。

栈按照―先进后出‖(FILO)或―后进先出‖(LIFO)组织数据，栈具有记忆作用。

栈的存储方式有顺序存储和链式存储。

栈的基本运算：

(1)入栈运算，在栈顶位置插入元素；

(2)退栈运算，删除元素(取出栈顶元素并赋给一个指定的变量)；

(3)读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。

队列：指允许在一端(队尾)进入插入，而在另一端(队头)进行删除的线性表。

用rear指针指向队尾，用front指针指向队头元素的前一个位置。

队列是―先进先出‖(FIFO)或―后进后出‖(LILO)的线性表。

队列运算：

(1)入队运算：从队尾插入一个元素;

(2)退队运算：从队头删除一个元素;

计算循环队列的元素个数：

―尾指针减头指针‖，若为负数，再加其容量即可。

即:

当 尾指针-头指针>0 时,尾指针-头指针

当 尾指针-头指针<0 时,尾指针-头指针+容量

计算栈的个数:

栈底 –栈顶 +1

1.6 树与二叉树 ★★★★★

1、树的基本概念

树是一种简单的非线性结构，其所有元素之间具有明显的层次特性。

在树结构中，每一个结点只有一个前件，称为父结点。

没有前件的结点只有一个，称为树的根结点，简称树的根。

每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件的个数称为该结点的度。

所有结点中最大的度称为树的度。

树的最大层次称为树的深度。

2、二叉树及其基本性质

满足下列两个特点的树,即为二叉树

(1)非空二叉树只有一个根结点；

(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

二叉树基本性质：★★★★

性质1 在二叉树的第k层上，最多有

个结点。

性质2 深度为m的二叉树最多有个 个结点。

性质3 在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。

性质4 具有n个结点的二叉树，其深度至少为数部分

3、满二叉树与完全二叉树

满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。

，其中

表示取

的整

完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

下图a表示的是满二叉树，下图b表示的是完全二叉树：

4、二叉树的遍历 ★★★★

二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种：

(1)前序遍历(DLR)：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

(2)中序遍历(LDR)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

(3)后序遍历(LRD)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点.该二叉树前序遍历为:F C A D B E G H P

该二叉树中序遍历为:A C B D F E H G P

该二叉树后序遍历为:A B D C H P G E F

1.7 查找技术

查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

查找结果：（查找成功：找到；查找不成功：没找到。）

平均查找长度：查找过程中关键字和给定值比较的平均次数。

查找分为: 顺序查找 二分法查找对于长度为n的有序线性表，最坏情况只需比较查找需要比较n次。

1.8 排序技术

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

1、交换类排序法（冒泡排序，快速排序）

2、插入类排序法（简单插入排序，希尔排序）

3、选择类排序法（简单选择排序，堆排序）

冒泡排序法,快速排序法,简单插入排序法,简单选择排序法,最坏需要比较的次数为n(n-1)/2

次，而顺序

希尔排序,最坏需要比较的次数为