下载文档原格式
并行算法设计一、引言并行算法是指在多核处理器或分布式系统上同时执行多个子任务，以提高计算效率和处理速度的一种计算模式。
随着计算机硬件技术的不断发展，越来越多的问题需要借助并行算法来解决。
本文将介绍并行算法的设计原则和常见的设计模式，以及在实际应用中的一些注意事项。
二、并行算法设计原则1. 任务划分原则：并行算法的基础是将原本串行执行的任务划分成多个独立的子任务，并通过适当的调度算法分配给不同的处理器进行并行执行。
任务划分应尽量保持任务的独立性，避免数据依赖关系过多，以提高并行度和性能。
2. 数据分布原则：在设计并行算法时，应根据不同任务的计算量和数据量合理规划数据分布方式。
对于计算密集型任务，可以将数据均匀划分给多个处理器；对于数据密集型任务，可以采用数据分布策略来平衡负载和减少数据通信的开销。
3. 通信和同步原则：并行算法中，处理器间的通信和同步操作是必不可少的。
在设计并行算法时，应考虑如何减少通信和同步的开销，以提高整体的算法性能。
可以通过减少数据传输量、合理设置同步点等方式来优化并行算法的通信和同步操作。
4. 任务调度原则：任务调度是指将多个子任务合理地分配给不同的处理器进行执行的过程。
合理的任务调度策略可以提高并行算法的负载均衡性和吞吐量，并减少处理器间的竞争情况。
在设计并行算法时，应考虑任务划分和任务调度的关系，选择合适的调度策略来优化算法性能。
三、并行算法设计模式1. 分治法：分治法是指将一个大问题分解成多个相互独立的小问题，并通过递归的方式将小问题的解合并成大问题的解。
在设计并行算法时，可以将原问题划分成多个子问题，分配给不同的处理器并行解决，最后将子问题的解合并得到最终结果。
2. 数据并行：数据并行是指将数据划分成多个子集，分配给不同的处理器并行处理。
对于同一类操作，各处理器可以独立计算自己所负责的数据子集，最后将各处理器计算得到的结果合并得到最终结果。
3. 流水线：流水线是指将一个任务划分成多个子任务，并通过不同的处理器按照一定的顺序依次执行。
计算机组成原理中的流水线与并行处理计算机组成原理是指计算机的各个组成部分及其相互关系的原理。
其中，流水线与并行处理是计算机组成原理中的两个重要概念。
本文将从流水线和并行处理的定义、特点、应用以及优缺点等方面进行论述。
一、流水线的定义和特点流水线技术是一种将复杂的任务分解为若干个互相依赖的子任务，并通过时序控制将其分别交给不同的处理单元进行执行的技术。
它可以提高计算机的执行效率和吞吐量。
与串行处理相比，流水线处理具有以下特点：1.任务分解：将复杂的任务分解为多个子任务，每个子任务由不同的处理单元负责执行。
2.流水线寄存器：通过在流水线各个阶段之间插入流水线寄存器，实现了各个阶段之间的数据传递和暂存，确保了数据的正确性和稳定性。
3.并行操作：不同的处理单元可以并行执行不同的任务，提高了计算机的并行处理能力。
4.随机任务执行：由于流水线中的各个阶段是独立的，因此可以随机运行和停止任务，提高了计算机的灵活性。
二、并行处理的定义和特点并行处理是指同时利用多个处理器或者多个处理单元并行执行多个任务的处理方式。
它可以大幅提升计算机系统的运算速度和处理能力。
并行处理的特点如下：1.任务分配：将大任务分解为多个小任务，并分配给多个处理单元同时执行。
2.任务协调：通过合理的任务调度算法，协调各个处理单元之间的任务执行顺序和数据传递，确保整个系统的稳定性和正确性。
3.资源共享：各个处理单元之间可以共享资源，如内存、缓存等，提高资源利用率。
4.计算效率提高：通过多个处理单元同时执行任务，大幅提高了计算效率和处理速度。
三、流水线与并行处理的应用流水线和并行处理在计算机领域被广泛应用，以下是几个常见的应用示例：1.超级计算机：超级计算机通常采用并行处理的方式，利用多个处理器同时进行计算，以提高计算能力。
2.图形处理器：图形处理器（GPU）采用流水线技术，将图像处理任务分解为多个子任务，通过流水线处理实现高效的图形渲染和计算。
流水线与并行处理1. 概述流水线技术导致了关键路径的缩短，从而可以提高时钟速度或采样速度，或者可以在同样速度下降低功耗。
在并行处理中，多个输出在一个时钟周期内并行地计算。
这样，有效采样速度提高到与并行级数相当的倍数。
与流水线类似，并行处理也能够用来降低功耗。
考虑3阶有限冲激响应（FIR ）数字滤波器：y(n) = ax(n) + bx(n-1) + cx(n-2) （1-1）其框图实现示意图如图1所示：图1 一个3阶FIR 滤波器关键路径（或者处理一个新样点所需要的最小时间）由1个乘法与2个加法器时间来限定。
如果T M 是乘法所用的时间，T A 是加法操作需要的时间，T sample 是采样周期，则必须满足：T sample ≥ T M + 2T A （1-2）因而，采样频率（f sample ）（也称为吞吐率或迭代速率），由下式给出：f sample ≤ A M T T 21 （1-3）流水线采用沿着数据通路引入流水线锁存器（本人理解是寄存器）的方法来减小有效关键路径（effective critical path ）。
并行处理提高采样频率是采用复制硬件的方法，以使几个输入能够并行的处理，而几个输出能够在同一时间产生出来。
2. FIR 数字滤波器的流水线其流水线实现是通过引入两个附加锁存器而得到的，如图2所示：图2 流水线FIR滤波器，其中垂直虚线代表一个前馈割集关键路径现在由T M + 2T A减小为T M + T A。
在这种安排下，当左边的加法器启动当前迭代计算的同时，右边的加法器正在完成前次迭代结果的计算。
必须注意到，在一个M级流水线系统中，从输入到输出的任一路径上的延时原件数目是（M-1）,它要大于在原始时序电路中同一路径上的延时元件数。
虽然流水线技术减小了关键路径，但是它付出了增加迟滞（latency）的代价。
迟滞实质上是流水线系统第一个输出数据的时间与原来时序系统第一个输出数据时间相比的滞后。
并行计算的基本概念并行计算是指同时执行多个计算任务的一种计算方法。
与串行计算相比，并行计算可以大幅提高计算效率，减少计算时间。
在并行计算中，多个任务可以被同时执行，任务之间可以相互独立执行或者相互协作完成。
任务并行是指将一个计算任务拆分成多个子任务，在不同的处理器上并行执行。
每个子任务都是相对独立的，可以独立地进行计算，并最终将计算结果合并。
任务并行适用于将一个大型计算任务分解成多个子任务并行执行的情况，每个子任务之间没有数据依赖。
数据并行是指将问题的数据集合分成多个部分，在不同的处理器上并行执行相同的计算任务。
每个处理器都负责处理部分数据，并最终将计算结果合并。
数据并行适用于将一个相同计算任务应用于多个数据元素的情况，每个处理器之间没有数据依赖。
流水线并行是指将一个计算任务拆分成多个阶段，在不同的处理器上并行执行不同的阶段，任务的执行流经过多个处理器，并最终将计算结果合并。
流水线并行适用于一个计算任务可以被划分成多个可以并行执行的阶段的情况，每个阶段之间有数据依赖。
并行计算还需要考虑负载均衡和数据同步的问题。
负载均衡是指将任务分配给不同的处理器时，尽量确保各个处理器的负载大致相当。
如果负载不均衡，会导致一些处理器的利用率较低，从而降低整体的计算效率。
负载均衡可以通过动态调整任务分配策略或者任务划分的方式来实现。
数据同步是指在并行计算中，处理器之间需要共享或者交换数据的过程。
数据同步主要包括数据传输和数据通信两个环节。
数据传输是指将数据从一个处理器传输到另一个处理器的过程，可以通过共享内存、消息传递或者文件系统等方式实现。
数据通信是指处理器之间交换数据的过程，可以通过消息传递等方式实现。
并行计算除了可以在多个处理器上进行，并且还可以通过分布式计算系统进行。
分布式计算是指将计算任务分布到不同的计算节点上，每个计算节点可以有多个处理器，通过网络连接进行通信和协作。
分布式计算可以进一步提高计算效率和扩展性，适用于处理大规模计算任务的场景。
处理大规模并行计算的方法近年来，随着计算机技术的飞速发展，大规模并行计算成为了处理大数据和高性能计算的重要手段。
在处理大规模并行计算的过程中，选择合适的方法和技术能够显著提高计算效率和性能。
本文将介绍几种常用的处理大规模并行计算的方法，并探讨其优缺点和适用场景。
一、任务并行任务并行是指将一个大任务分解为多个小任务，并将这些小任务分配给不同的处理单元同时进行计算的方式。
这种方法可以充分利用多台计算机或多个CPU的计算能力，从而提高计算速度和效率。
任务并行的关键是任务的划分和调度，通过合理的任务划分和调度策略，可以实现任务之间的负载均衡，进一步提高计算性能。
二、数据并行数据并行是指将大规模数据分割成多个小数据块，并将这些小数据块分配给不同的处理单元同时进行计算的方式。
这种方法适用于需要对大量数据进行相同操作的场景，如图像处理、数据挖掘等。
数据并行的关键是数据的划分和通信，通过适当的数据划分和高效的通信机制，可以加快计算速度和降低通信开销。
三、流水线并行流水线并行是指将一个大的计算过程分解为多个子计算过程，并通过流水线的方式进行计算。
在流水线并行中，每个子计算过程可以由不同的处理单元并行执行，从而提高计算效率。
流水线并行适用于计算过程具有一定的顺序性和高度可并行性的情况，如图像处理、视频编码等。
然而，流水线并行也面临着任务之间的依赖关系和流水线的平衡问题，需要合理设计和管理。
四、共享内存并行共享内存并行是指多个处理单元共享同一块内存空间，并通过读取和写入内存来进行通信和协调的方式。
这种方法具有内存访问速度快、通信成本低的优势，适用于需要频繁共享数据和协同计算的场景，如并行搜索算法、图计算等。
共享内存并行的关键是处理好并发访问冲突和数据一致性的问题，确保计算结果的准确性和一致性。
综上所述，处理大规模并行计算的方法包括任务并行、数据并行、流水线并行和共享内存并行等。
选择合适的方法取决于具体的应用场景和需求，需要综合考虑计算规模、计算复杂度、数据通信等因素。
习题一1、解释下列术语计算机系统的外特性：通常所讲的计算机系统结构的外特性是指机器语言程序员或编译程序编写者所看到的外特性，即由他们所看到的计算机的基本属性（概念性结构和功能特性）。
计算机系统的内特性：计算机系统的设计人员所看到的基本属性，本质上是为了将有关软件人员的基本属性加以逻辑实现的基本属性。
模拟：模拟方法是指用软件方法在一台现有的计算机上实现另一台计算机的指令系统。
可移植性：在新型号机出台后，原来开发的软件仍能继续在升级换代的新型号机器上使用，这就要求软件具有可兼容性，即可移植性。
可兼容性是指一个软件可不经修改或只需少量修改，便可由一台机器移植到另一台机器上运行，即同一软件可应用于不同环境。
Amdahl 定律：系统中对于某一部件采用某种更快的执行方式所能获得的系统性能改进程度，取决于这种执行方式被使用的频度或占总执行时间的比例。
虚拟机（Virtual Machine ）：指通过软件模拟的具有完整硬件系统功能的、运行在一个完全隔离环境中的完整计算机系统。
6、7、假定求浮点数平方根的操作在某台机器上的一个基准测试程序中占总执行时间的20%，为了增强该操作的性能，可采用两种不同的方法：一种是增加专门的硬件，可使求浮点数平方根操作的速度提高为原来的20倍；另一种方法是提高所有浮点运算指令的速度，使其为原来的2倍，而浮点运算指令的执行时间在总执行时间中占30%。
试比较这两种方法哪一种更好些。
答：增加硬件的方法的加速比23.120/2.0)2.01(11=+-=p S ,另一种方法的加速比176.12/3.0)3.01(12=+-=p S ，经计算可知Sp1>Sp2第一种方法更好些。
9、假设高速缓存Cache 的工作速度为主存的5倍，且Cache 被访问命中的概率为90%，则采用Cache 能使整个存储系统获得多高的加速比？ 答：加速比%10)(%90'⨯++⨯==tc tm tc tmT T S ，其中tm=5tc ，代入公式，得到加速比S=3.33。
并行计算的分类随着计算机技术的不断发展，计算能力和算法的复杂程度也得到了大幅提升，但是在某些场景下，单个计算机的计算能力和运行速度已经无法满足需求。
并行计算应运而生，可以利用多个计算机或者处理器同时进行计算任务，进而提高计算速度和效率。
并行计算的分类可以从不同角度进行区分，下面是常见的并行计算分类。
1.按照并行度分类并行度是指在并行计算中，可同时执行的任务数目。
根据并行度的不同，可以将并行计算分为以下几类。
（1）任务并行：任务并行是指将大的计算任务分为多个小的子任务，然后将子任务分配给多个处理器进行同时计算。
这种并行化策略可以极大地提高计算速度和效率。
例如，在图像处理中，可以将一幅图像分成多个子区域，然后交给多个处理器并行计算。
（2）数据并行：数据并行是指将大的数据集分为多份，然后将数据分配给多个处理器进行计算。
例如，在机器学习中，可以将数据集分为多份，然后交给多个处理器进行同时训练。
（3）管道并行：管道并行是指将多个处理器按照流水线方式进行组合，每个处理器负责一道计算工序，然后将结果传递给下一个处理器。
例如，在视频处理中，可以将视频编码器和解码器按照流水线方式进行组合，提高视频处理的效率。
（4）混合并行：混合并行是指以上所述所有并行化方式的混合使用。
2.按照计算资源分类根据计算资源的不同，可以将并行计算分为以下几类。
（1）集中式并行计算：集中式并行计算是指将多个处理器或者计算机集中在一个计算中心进行协同工作，以完成一些大规模计算任务。
例如，在云计算中，可以将多个计算机集成在同一数据中心，来实现大规模的计算任务。
（2）分散式并行计算：分散式并行计算通常是通过网络进行协同工作，各个计算机或者处理器之间互相通讯，协同完成计算任务。
例如，在分布式系统中，每个计算机负责执行一部分计算任务，并将结果传递给其他计算机进行处理。
3.按照工作量分配策略分类根据工作量分配策略的不同，可以将并行计算分为以下几类。
（1）静态数据分配：静态数据分配是指将数据集按照静态的方法分配给各个处理器进行计算。
并行计算算法设计与分析一、引言在现代计算机系统中，并行计算已经成为一种重要的技术手段。
并行计算算法的设计与分析是研究并行计算的核心内容之一。
本文将详细介绍并行计算算法的设计与分析方法，并讨论其在实际应用中的意义与挑战。
二、并行计算算法的分类1. 数据并行算法数据并行算法采用将计算任务分割为多个子任务，每个子任务在不同的处理单元上并行执行的方式。
典型的数据并行算法包括矩阵乘法算法、并行排序算法等。
2. 任务并行算法任务并行算法是将计算任务分解为多个相互独立的子任务，并行执行的方式。
各个子任务之间没有数据依赖关系，可以同时进行计算。
典型的任务并行算法包括并行搜索算法、并行图算法等。
3. 流水线并行算法流水线并行算法是将计算任务分解为多个阶段，不同处理单元在不同阶段上并行执行，通过流水线的方式提高计算效率。
典型的流水线并行算法包括多级缓存机制的并行计算算法、指令级并行计算算法等。
三、并行计算算法的设计方法1. 并行分解并行分解是指将原始的计算任务分解为多个子任务的过程。
在并行分解过程中，需要考虑任务的划分方式、任务之间的依赖关系以及负载均衡等问题。
2. 并行通信并行通信是指多个处理单元之间的信息传递与同步。
在并行计算算法的设计中，合理的并行通信方式能够提高计算效率。
常用的并行通信方式包括消息传递接口MPI、共享内存等。
3. 并行合并并行合并是指将多个子任务的计算结果合并为最终的结果的过程。
在并行合并过程中，需要考虑合并方式以及结果的正确性验证等问题。
四、并行计算算法的分析方法1. 速度up与加速比速度up表示并行计算与串行计算相比的计算速度提升程度。
加速比表示并行计算中处理单元数量增加时，计算速度相对于串行计算的提升比例。
通过对速度up与加速比的分析，可以评估并行算法的性能优劣。
2. 并行性的度量与评估并行性是指并行计算中各个子任务可以同时进行的程度。
通过对并行性的度量与评估，可以确定并行计算算法的最佳并行度。
流水线的工作原理
流水线的工作原理是将一个任务拆分成多个子任务，并由多个处理单元按照顺序进行并行处理，从而实现提高任务处理效率的目的。
具体来说，流水线工作原理分为以下几个步骤：
1. 任务拆分：将一个任务分解成多个子任务，每个子任务具有一定的独立性，可以并行处理。
2. 指令执行阶段划分：将每个子任务划分为不同的阶段，每个阶段需要不同类型的处理单元进行处理。
3. 并行处理：每个处理单元在每个阶段对应的子任务上进行处理，各个处理单元同时工作，形成并行处理的效果。
4. 流水线寄存器：流水线中的每个阶段之间通过流水线寄存器进行数据传输，保证各个阶段之间的数据同步。
5. 流水线冲突处理：由于流水线中各个阶段同时进行，可能会出现数据相关等冲突，需要通过添加硬件逻辑或进行优化来解决这些冲突，以保证流水线的正常工作。
6. 结果合并：当所有子任务完成处理后，将各个处理单元输出的结果合并得到最终的任务结果。
通过以上步骤，流水线能够将一个任务分解并并行处理，充分利用硬件资源，提高任务处理的效率和速度。
但是流水线也会因为流水线寄存器的引入，导致任务执行速度下降，同时需要处理冲突问题，因此需要根据具体情况进行流水线设计和优化。
1.交叉存储器实质上是一种_模块式_存储器，它能_并行_执行_多个_独立的读写操作，（流水）方式执行多个独立的读写操作。
2.32位浮点数格式中,符号位为1位,阶以码为8位,尾数为23位。
则它所能表示的最大规格表示范围规格化近零数非规格化近零数3.IEEE754标准规定的64位浮点数格式中，一个浮点数由符号位S 1位、阶码E 11位、尾数M 52位三个域组成。
其中阶码E的值等于指数的真值e加上一个固定偏移值+127。
则它能表示的最大规格化正数为4.一组相联映射的Cache，有128块，每组4块，主存共有16384块，每块64个字，则主存地址共20位，其中主存字块标记应为9位，组地址应为5位，Cache地址共13位。
5.CPU存取出一条指令并执行该指令的时间叫（指令周期），它通常包含若干个（CPU周期），而后者又包含若干个（时钟周期）。
3.十进制数在计算机内有两种表示形式：（字符串）形式和（压缩的十进制数串）形式。
前者主要用在非数值计算的应用领域，后者用于直接完成十进制数的算术运算。
4.一个较完善的指令系统，应当有数据处理、数据存储、数据传送、程序控制四大类指令。
5.机器指令对四种类型的数据进行操作。
这四种数据类型包括地址数值字符逻辑型数据。
6.CPU中保存当前正在执行的指令的寄存器是（指令寄存器，指示下一条指令地址的寄存器是（程序寄存器，保存算术逻辑运算结果的寄存器是（数据缓冲寄冲器和（?状态寄存器）。
12.挂接在总线上的多个部件（只能分时向总线发送数据，但可同时从总线接收数据;）。
13.在冯诺依曼体制中，计算机硬件系统是由输入设备、输出设备、控制器、存储器和运算器等五大部件组成。
14.补码加减所依据的基本关系是(X+Y)补=X补+Y补和(X-Y)补=X补+(-Y)补。
15.按照微命令的形成方式，可将控制器分为组合逻辑控制器和微程序控制器两种基本类型。
16.CPU对信息传送的控制方式主要分为直接程序传送方式、程序中断传送方式、DMA传送方式等3种。
数据流处理中的流水线架构设计与优化研究随着大数据时代的到来，数据处理的需求也越来越高。
在处理大规模数据时，传统的串行处理方式已经无法满足需求，因此流水线架构成为了一种重要的数据处理方式。
本文将探讨数据流处理中的流水线架构设计与优化研究。
一、流水线架构的基本概念与原理流水线架构是一种将复杂任务分解为多个简单任务，并通过流水线的方式依次处理的架构。
在数据处理中，流水线架构可以将数据处理过程划分为多个阶段，每个阶段负责不同的任务，从而提高整体处理的效率。
流水线架构的基本原理是任务并行化和流水线化。
任务并行化指的是将一个大任务划分为多个小任务，并同时进行处理。
流水线化则是将任务划分为多个阶段，每个阶段负责不同的任务，任务之间通过数据流进行连接。
通过任务并行化和流水线化，可以充分利用计算资源，提高数据处理的效率。
二、流水线架构设计的关键问题在设计流水线架构时，需要考虑以下几个关键问题：1. 任务划分：如何将一个大任务划分为多个小任务，并确定每个任务的输入和输出。
2. 阶段划分：如何将任务划分为多个阶段，并确定每个阶段的任务和数据流。
3. 数据流控制：如何控制数据在流水线中的流动，避免数据冲突和数据丢失。
4. 同步与通信：如何在不同的阶段之间进行同步和通信，确保数据的正确处理。
5. 效率与延迟：如何在提高处理效率的同时，尽量减少处理延迟。
三、流水线架构优化的方法与技术为了进一步提高流水线架构的效率，可以采用以下几种优化方法与技术：1. 流水线分段：将流水线划分为多个段，每个段包含多个阶段。
通过流水线分段，可以减少不同阶段之间的通信和同步开销，提高整体处理的效率。
2. 数据预取：在流水线中引入数据预取机制，提前将需要的数据加载到缓存中，减少数据访问延迟。
3. 流水线重排：通过重新排序流水线中的任务顺序，使得关键路径上的任务能够尽早执行，减少整体处理的延迟。
4. 数据缓存：在流水线中引入数据缓存，将频繁使用的数据存储在高速缓存中，以减少对内存的访问。
一、填空题1.目前的CPU包括、和CACHE。
2.CPU的四个主要功能是、、和。
3.CPU从主存取出一条指令并执行该指令的时间叫，它常用若干个来表示，而后者又包含若干个。
4.在程序执行过程中，控制器控制计算机的运行总是处于、分析指令和的循环当中。
5.由于数据通路之间的结构关系，微操作可分为和两种。
6.微指令格式中，微指令的编码通常采用以下三种方式：、和7.硬布线控制器的基本思想是：某一控制信号是译码输出、信号、信号和状态反馈信息的逻辑函数。
8.时序信号产生器提供机器所需的时序信号，在硬联线控制器中，时序信号采用三级体制，在微程序控制器中，一般采用二级体制。
9.微程序设计技术是利用方法设计的一门技术，具有等一系列优点。
10.并行处理技术主要有三种形式：并行、并行和并行。
11.流水CPU中的主要问题是：相关、相关和相关。
12.RISC CPU具有的三个要素是：、和13.多媒体CPU是带有技术的处理器，它是一种技术，特别适合于处理。
14.微程序控制器由、、三大部分组成，其中是ROM存储器，用来存放。
二、单项选择题1.在CPU中跟踪指令后继地址的寄存器是A．MAR B．PC C．IR D．PSW2.同步控制是A．只适用于CPU控制的方式B．只适用于外围设备控制的方式C．由统一时序信号控制的方式D．所有指令执行时间都相同的方式3.下列部件中不属于控制器的是A．IR B．操作控制器C．PC D．PSW4.计算机操作的最小时间单位是A．时钟周期B．指令周期C．CPU周期D．微指令周期三、简答题1.计算机内有哪两股信息在流动？如何区分它们？2.解释机器指令和微指令的关系四、综合题1.已知CPU结构如下图所示，其中包括一个累加器AC、一个状态寄存器和其他几个寄存器。
各部分之间的连线表示数据通路，箭头表示信息传递方向。
试完成以下工作：①写出图中四个寄存器A、B、C、D的名称和作用；②简述完成指令ADD Y的数据通路（Y为存储单元地址，本指令功能为(AC)+(Y)→AC）。
一、简答题（2题）相关概念、原理、方法说明及比较分析例题1：解释下列术语层次机构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每一层以一种不同的语言为特征。
虚拟机：用软件实现的机器。
翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。
解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。
执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。
计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。
透明性：在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。
计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻辑设计等。
计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。
软件兼容：一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。
差别只是执行时间的不同。
兼容机：由不同公司厂家生产的具有相同系统结构的计算机。
模拟：用软件的方法在一台现有的计算机(称为宿主机)上实现另一台计算机(称为虚拟机)的指令系统。
仿真：用一台现有计算机(称为宿主机)上的微程序去解释实现另一台计算机(称为目标机)的指令系统。
并行性：计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。
只要在时间上相互重叠，就存在并行性。
它包括同时性与并发性两种含义。
时间重叠：在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。
资源重复：在并行性概念中引入空间因素，以数量取胜。
通过重复设置硬件资源，大幅度地提高计算机系统的性能。
并行计算的参考题目1、讨论某一种算法的可扩放性时，一般指什么？88答：讨论某一种算法的可扩放性时，实际上是指该算法针对某一特定机器结构的可扩放性2、使用“Do in Parallel”语句时，表示的是什么含义105答：表示算法的若干步要并行执行3、并行计算机的存储访问类型有哪几种？26答：存储访问类型有：UMA（均匀存储访问）、NUMA（非均匀存储访问）、COMA（全高速缓存存储访问）、CC-NUMA（高速缓存一致性非均匀存储访问）、NORMAl（非远程存储访问）4、什么是同步？它有什么作用？如何实现？107答：同步是在时间上强使各执行进程在某一点必须相互等待。
作用：确保个处理器的正确工作顺序以及对共享可写数据的正确访问（互斥访问）。
实现方法：用软件、硬件和固件的方法实现。
5 在并行加速比的计算中，常用的三种加速比定律分别是哪三种？（P83）答：常用的三种加速比定律分别是：适用于固定计算负载的Amdahl定律，适用于可扩放问题的Gustafson定律和受限于存储器的Sun和Ni定律。
6、试比较Amdahl定律、Gustafson定律、Sun和Ni定律三种加速定律的应用场合。
83 答：Amdahl定律适用于固定计算负载的问题Gustafson定律适用于可扩放性问题Sun和Ni定律适用于受限于存储器的问题。
7.并行算法的基本设计技术有哪些？它们的基本思想是什么？139答：(1)基本技术有：划分设计技术(又分为均匀划分技术、方根划分技术、对数划分技术和功能划分技术)、分治设计技术、平衡树设计技术、倍增设计技术、流水线设计技术等。
(2)基本思想分别如下：a.划分设计技术：(P139) 将一原始问题分成若干部分，然后各部分由相应的处理器同时执行。
b.分治设计技术：(P144)将一个大二复杂的问题分解成若干特性相同的子问题分而治之。
若所得的子问题规模仍嫌过大，可反复使用分治策略，直至很容易求解诸子问题为止。
1、讨论某一种算法的可扩放性时，一般指什么？88答：讨论某一种算法的可扩放性时，实际上是指该算法针对某一特定机器结构的可扩放性2、使用“Do in Parallel”语句时，表示的是什么含义105答：表示算法的若干步要并行执行3、并行计算机的存储访问类型有哪几种？26答：存储访问类型有：UMA（均匀存储访问）、NUMA（非均匀存储访问）、COMA（全高速缓存存储访问）、CC-NUMA（高速缓存一致性非均匀存储访问）、NORMAl（非远程存储访问）4、什么是同步？它有什么作用？如何实现？107答：同步是在时间上强使各执行进程在某一点必须相互等待。
作用：确保个处理器的正确工作顺序以及对共享可写数据的正确访问（互斥访问）。
实现方法：用软件、硬件和固件的方法实现。
5 在并行加速比的计算中，常用的三种加速比定律分别是哪三种？（P83）答：常用的三种加速比定律分别是：适用于固定计算负载的Amdahl定律，适用于可扩放问题的Gustafson定律和受限于存储器的Sun和Ni定律。
6、试比较Amdahl定律、Gustafson定律、Sun和Ni定律三种加速定律的应用场合。
83 答：Amdahl定律适用于固定计算负载的问题Gustafson定律适用于可扩放性问题Sun和Ni定律适用于受限于存储器的问题。
7.并行算法的基本设计技术有哪些？它们的基本思想是什么？139答：(1)基本技术有：划分设计技术(又分为均匀划分技术、方根划分技术、对数划分技术和功能划分技术)、分治设计技术、平衡树设计技术、倍增设计技术、流水线设计技术等。
(2)基本思想分别如下：a.划分设计技术：(P139) 将一原始问题分成若干部分，然后各部分由相应的处理器同时执行。
b.分治设计技术：(P144)将一个大二复杂的问题分解成若干特性相同的子问题分而治之。
若所得的子问题规模仍嫌过大，可反复使用分治策略，直至很容易求解诸子问题为止。
c.平衡树设计技术：(P149)将输入元素作为叶节点构筑一颗平衡二叉树，然后自叶向根往返遍历。
