并行计算(陈国良版)课后答案
第三章互连网络
对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。
答：
推广至M元树时，k级M元树总结点数N的表达式为：
N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m);
二元胖树如图所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络
答：8输入的完全混洗三级互联网络。
四元胖树如图所示，试问：每个内节点有几个子节点和几个父节点你知道那个机器使用了此种形式的胖树
答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。
试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么
答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4
B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6
一个N=2^k个节点的 de Bruijin 。
。。。试问：该网络的直径和对剖宽度是多少
答：N=2^k个节点的 de Bruijin网络直径d=k 对剖宽带w=2^(k-1)
一个N=2^n个节点的洗牌交换网络如图所示。试问：此网络节点度==网络直径==网络对剖宽度==
答：N=2^n个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4
一个N=（k+1）2^k个节点的蝶形网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度=
答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k
对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围）
答：
如图所示，信包的片0，1，2，3要分别去向目的地A，B，C，D。此时片0占据信道CB，片1占据信道DC，片2占据信道AD，片3占据信道BA。试问：
1）这将会发生什么现象
2）如果采用X-Y选路策略，可避免上述现象吗为什么
答： 1）通路中形成环，发生死锁
2）如果采用X-Y 策略则不会发生死锁。因为采用X-Y 策略时其实质是对资源（这里是通道）进行按序分配（永远是x 方向优先于y 方向，反方向路由是y 方向优先于x 方向），因此根据死锁避免的原则判断，此时不会发生死锁。
在二维网孔中，试构造一个与X-Y 选路等价的查表路由。 答： 所构造路由表描述如下：
1）每个节点包括两张路由表x 表和y 表
2）每个节点包含其以后节点信息，如节点【1，2】x 表内容为:【2，2】【3，2】y 表内容为：【1，3】 选路方法：
节点路由时进行查表：先查x 表即进行x 方向路由，如果查表能指明下一跳方向则直接进入下一跳。如果不能则继续查y 表，直到到达目的地。
第四章 对称多处理机系统
参照图，试解释为什么采用WT 策略进程从2P 迁移到1P 时，或采用WB 策略将包含共享变量X 的进程从1P 迁移到2P 时，会造成高速缓存的不一致。
处理器
高速缓存共享
存储器
迁移写通写总线
过回
之前
图 进程迁移所造成的不一致性
答：采用WT 策略进程从2P 迁移到1P 后，2P 写共享变量X 为X ’，并且更新主存数据为X ’，此时1P 共享变量值仍然为X ，与2P 和主存X ’不一致。采用WB 策略进程从1P 迁移到2P 后，
1P 写共享变量X 为X ’，但此时2P 缓存与主存变量值仍然为X ，造车不一致。
参照图所示，试解释为什么：①在采用WT 策略的高速缓存中，当I/O 处理器将一个新的数
据'X 写回主存时会造成高速缓存和主存间的不一致；②在采用WB 策略的高速缓存中，当直接从主存输出数据时会造成不一致。
处理器
I/O
（写直达）
总线
输入输出（写回）高速缓存I/O处理机
图 绕过高速缓存的I/O 操作所造成的不一致性
答：①中I/O 处理器将数据X ’写回主存，因为高速缓存采用WT 策略，此时P1和P2相应的高速缓存值还是X ，所以造成高速缓存与主存不一致。②直接从主存输出数据X ，因为高速缓存采用WB 策略，可能高速缓存中的数据已经被修改过，所以造成不一致。
4.3 试解释采用WB
策略的写更新和写无效协议的一致性维护过程。其中X 为更新前高速缓
存中的拷贝，'X 为修改后的高速缓存块，I 为无效的高速缓存块。
（b）处理器P 1执行写无效操作后
（c）处理器P 1执行写更新操作后
（a）写操作前
答：处理器P1写共享变量X 为X ’，写更新协议如图(c)所示，同时更新其他核中存在高速缓存拷贝的值为X ’;写无效协议如图(b)所示，无效其他核中存在高速缓存拷贝，从而维护了一致性过程。
4.4 两种基于总线的共享内存多处理机分别实现了Illinois MESI 协议和Dragon 协议，对
于下面给定的每个内存存取序列，试比较在这两种多处理机上的执行代价，并就序列及一致性协议的特点来说明为什么有这样的性能差别。序列①r1 w1 r1 w1 r2 w2 r2 w2 r3 w3 r3 w3；序列②r1 r2 r3 w1 w2 w3 r1 r2 r3 w3 w1；序列③r1 r2 r3 r3 w1 w1 w1 w1 w2 w3；所有的存取操作都针对同一个内存位置，r/w 代表读/写，数字代表发出该操作的处理器。假设所有高速缓存在开始时是空的，并且使用下面的性能模型：读/写高
速缓存命中，代价1个时钟周期；缺失引起简单的总线事务（如BusUpgr，BusUpd），60个时钟周期；缺失引起整个高速缓存块传输，90时钟周期。假设所有高速缓存是写回式。答：读写命中、总线事务、块传输分别简记为H、B、T。MESI协议：①BTH H H H BTH BH H H BTH BH H H 共5B+12H+3T=582时钟周期②BTH BTH BTH BH BTH BTH BTH BTH H BH BTH 共10B+12H+8T=1330时钟周期③BTH BTH BTH H BH H H H BTH BTH共6B+10H+4T=730时钟周期。Dragon协议：①BTH H H H BTH BTH H BTH BTH BTH H BTH 共7B+12H+7T=882时钟周期②BTH BTH BTH BTH BTH BTH H H H H BTTH BTH 共8B+12H+8T=1212时钟周期③BTH BTH BTH H BTH BTH BTH BTH BTH BTH 共9B+10H+9T=1360时钟周期。由结果得出，①、③序列用MESI 协议时间更少，而②序列用Dragon协议时间更少。综上可知，如果同一块在写操作之后频繁被多个核读操作采用Dragon协议更好一些，因为Dragon协议写操作后会更新其它核副本。如果一个同多次连续对同一块进行写操作MESI协议更有效，因为它不需要更新其它核副本，只需要总线事务无效其它核即可。
考虑以下代码段，说明在顺序一致性模型下，可能的结果是什么假设在代码开始执行时，所有变量初始化为0。
a.
P1P2P3
A=1U=A V=B
B=1W=A
b.
P1P2P3P4
A=1U=A B=1W=B
V=B X=A
答：顺序一致性模型性下，保护每个进程都按程序序来发生内存操作，这样会有多种可能结果，这里假设最简单情况，即P1、P2、P3依次进行。则a中U = V = W = 1，b中U=X=W=1，V=0。
4.6参照4.6.1中讨论多级高速缓存包含性的术语，假设L1和L2都是2-路组相联，n2>n1，
b1=b2，且替换策略用FIFO来代替LRU，试问包含性是否还是自然满足如果替换策略是随机替换呢
答：如果采用FIFO替换策略包含性自然满足，因为L1和L2都是2路组相联，FIFO保证了L1与L2在发生替换时会换出相同的缓存块，维护了包含性。如果采取随机替换策略，存在L1与L2替换不是相同块的情况，故不满足包含性。
4.7针对以下高速缓存情况，试给出一个使得高速缓存的包含性不满足的内存存取序列
L1 高速缓存容量32字节，2-路组相联，每个高速缓存块8个字节，使用LRU替换算法；
L2 高速缓存容量128字节，4-路组相联，每个高速缓存块8个字节，使用LRU替换算法。
答：假设m1、m2、m3块映射到一级Cache和二级Cache的同一组中，考虑如下内存存取序列R m1，R m2，R m1，R m3，由LRU替换算法知道，当R m3执行后，L1中被替换出的是m2，L2中被替换出的是m1，此时m1块在L1却不在L2中，不满足包含性。
4.8在中关于分事务总线的讨论中，依赖于处理器与高速缓存的接口，下面情况有可能发生：
一个使无效请求紧跟在数据响应之后，使得处理器还没有真正存取这个高速缓存块之前，该高速缓存块就被使无效了。为什么会发生这种情况，如何解决
答：考虑如下情景：SMP目录一致性协议中，核1读缺失请求数据块A，主存响应请求传送数据块A给核1，同时核2对数据块A进行写操作，到主存中查得核1拥有副本，向核1发使无效请求。如此，一个使无效请求紧跟在数据响应之后。解决方法，可以使每个核真正存取高速缓存块后向主存发回应，然后再允许其它对此块操作的使无效或其它请求。
4.9利用LL-SC操作实现一个Test&Set操作。
答：Test&Set： ll reg1,location /*Load-locked the location to reg1 */
bnz reg1,lock /* if locatin was locked,try again*/
mov reg2,1 /*set reg2 1*/
sc location,reg2 /*store reg2 conditional into location*/
4.10在4.7.4部分描述具有感觉反转的路障算法中，如果将Unlock语句不放在if条件语句
的每个分支中，而是紧接放在计数器增1语句后，会发生什么问题为什么会发生这个问题
答：再进入下一个路障时可能会发生计数器重新清0现象，导致无法越过路障。考虑如下情景：第一次进入路障时，最后两个进入路障的进程分别为1、2。假设最后进入路障的进程为2进程，2进程执行共享变量加一操作并解锁。然后2进程执行一条if条件语句，此时由于某种原因换出或睡眠，而此时共享变量的值已经为p。如果1进程此时正执行if条件语句，则清零计数器，设置标志，其它进程越过路障。到目前为止没有出现问题，问题出现在下一次进入路障。进程再一次进入路障，此时会执行共享变量加一操作。如果此时2进程被换入或被唤醒，会重新清零共享变量，使之前到达路障的进程的加一操作无效，导致无法越过路障。
第五章大规模并行处理机系统
简述大规模并行处理机的定义，原理和优点
答：并行处理机有时也称为阵列处理机，它使用按地址访问的随机存储器，以单指令流多数据流方式工作，主要用于要求大量高速进行向量矩阵运算的应用领域。并行处理机的并行性来源于资源重复，它把大量相同的处理单元（PE）通过互联网络（ICN）连接起来，在统一的控制器（CU）控制下，对各自分配来的数据并行地完成同一条指令所规定的操作。PE是不带指令控制部件的算术逻辑运算单元。并行处理机具有强大的向量运算能力，具有向量化功能的高级语言编译程序有助于提高并行处理机的通用性，减少编译时间。
并行处理机有两种基本结构类型，请问是哪两种并作简单介绍。
答：采用分布存储器的并行处理结构和采用集中式共享存储器的并行处理结构。分布式存储器的并行处理结构中，每一个处理机都有自己的存储器，只要控制部件将并行处理的程序分配至各处理机，它们便能并行处理，各自从自己的存储器中取得信息。而共享存储多处理机结构中的存储器是集中共享的，由于多个处理机共享，在各处理机访问共享存储器时会发生竞争。因此，需采取措施尽可能避免竞争的发生。
简单说明多计算机系统和多处理机系统的区别。
答：他们虽然都属于多机系统但是他们区别在于：（1）多处理机是多台处理机组成的单机系统，多计算机是多台独立的计算机。（2）多处理机中各处理机逻辑上受同一的OS控制，而多计算机的OS逻辑上独立.(3)多处理机间以单一数据，向量。数组和文件交互作用，多计
算机经通道或者通信线路以数据传输的方式进行。（4）多处理机作业，任务，指令，数据各级并行，多计算机多个作业并行。
举例说明MPP的应用领域及其采用的关键技术。
答：全球气候预报，基因工程，飞行动力学，海洋环流，流体动力学，超导建模，量子染色动力学，视觉。采用的关键技术有VLSI，可扩张技术，共享虚拟存储技术。
多处理机的主要特点包括
答：
（1）结构的灵活性。与SIMD计算机相比，多处理机的结构具有较强的通用性，它可以同时对多个数组或多个标量数据进行不同的处理，这要求多处理机能够适应更为多样的算法，具有灵活多变的系统结构。2）程序并行性。并行处理机实现操作一级的并行，其并行性存在于指令内部，主要用来解决数组向量问题；而多处理机的并行性体现在指令外部，即表现在多个任务之间。3）并行任务派生。多处理机是多指令流操作方式，一个程序中就存在多个并发的程序段，需要专门的程序段来表示它们的并发关系以控制它们的并发执行，这称为并行任务派生。
4）进程同步。并行处理机实现操作级的并行，所有处于活动状态的处理单元受一个控制器控制，同时执行共同的指令，工作自然同步；而多处理机实现指令、任务、程序级的并行，在同一时刻，不同的处理机执行着不同的指令，进程之间的数据相关和控制依赖决定了要采取一定的进程同步策略。
在并行多处理机系统中的私有Cache会引起Cache中的内容相互之间以及与共享存储器之间互不相同的问题，即多处理机的Cache一致性问题。请问有哪些原因导致这个问题
答：
1）出现Cache一致性问题的原因主要有三个：共享可写的数据、进程迁移、I/O传输。共享可写数据引起的不一致性。比如P1、P2两台处理机各自的本地高速缓冲存储器C1、C2中都有共享存储器是M中某个数据X的拷贝，当P1把X的值变成X/后，如果P1采用写通过策略，内存中的数据也变为X/，C2中还是X。如果通过写回策略，这是内存中还是X。在这两种情况下都会发生数据不一致性。2）进程迁移引起的数据不一致性。P1中有共享数据X的拷贝，某时刻P1进程把它修改为X/并采用了写回策略，由于某种原因进程从P1迁移到了P2上，它读取数据时得到X，而这个X是“过时”的。3） I/O传输所造成的数据不一致性。假设P1和P2的本地缓存C1、C2中都有某数据X的拷贝，当I/O处理机将一个新的数据X/写入内存时，就导致了内存和Cache之间的数据不一致性。
分别确定在下列两种计算机系统中，计算表达式所需的时间：s=A1*B1+A2*B2+…A4*B4。 a) 有4个处理器的SIMD系统；b) 有4个处理机的MIMD系统。假设访存取指和取数的时间可
以忽略不计；加法与乘法分别需要2拍和4拍；在SIMD和MIMD系统中处理器（机）之间每进行一次数据传送的时间为1拍；在SIMD系统中，PE之间采用线性环形互连拓扑，即每个PE与其左右两个相邻的PE直接相连，而在MIMD中每个PE都可以和其它PE有直接的的通路。
答：假设4个PE分别为PE0，PE1，PE2，PE3。利用SIMD计算机计算上述表达式，4个乘法可以同时进行，用时=4个时间单位；然后进行PE0到PE1，PE2到PE3的数据传送，用时=1个时间单位。在PE1和PE3中形成部分和，用时=2个时间单位。接着进行PE1到PE3的部分和传送，用时=1*2=2个时间单位。最后，在PE3中形成最终结果，用时=2个时间单位。因此，利用SIMD计算机计算上述表达式总共用时=4（乘法）+1（传送）+2（加法）+2（传送）+2（加法）=11个时间单位。而利用MIMD计算机计算上述表达式，除了在第二次传送节省1个时间单位以外，其他与SIMD相同。因此用时=4（乘法）+1（传送）+2（加法）+1（传送）+2（加法）=10个时间单位。
假定有一个处理机台数为p的共享存储器多处理机系统。设m为典型处理机每条执行执行时间对全局存储器进行访问的平均次数。
设t为共享存储器的平均存储时间，x为使用本地存储器的单处理机MIPS速率，再假定在多处理机上执行n条指令。
现在假设p=32,m=,t=1μs,要让多处理机的有效性能达到56MIPS，需要每台处理机的MIPS效率是多少
答：B
试在含一个PE的SISD机和在含n个PE且连接成一线性环的SIMD机上计算下列求内积的表达式：其中n=2k
∑=?
=
n
i
i i
B A
s
1
假设完成每次ADD操作需要2个单元时间，完成每次MULTIPLY操作需要4个单位时间，沿双向环在相邻PE间移数需1个单位时间
(1)SISD计算机上计算s需要多少时间
(2)SIMD计算机上计算s需要多少时间
(3)SIMD机计算s相对于SISD计算的加速比是多少
答：
(1) 4n+2(n-1) (2) 124-++n k (3) ()n
k n n ++-+23124
如果一台SIMD 计算机和一台流水线处理机具有相同的计算性能，对构成它们的主要部件分别有什么要求
答：一台具有n 个处理单元的SIMD 计算机与一台具有一条n 级流水线并且时钟周期为前者1/n 的流水线处理机的计算性能相当，两者均是每个时钟周
期产生n 个计算结果。但是，SIMD 计算机需要n 倍的硬件（n 个处理单元），而流水线处理机中流水线部件的时钟速率要求比前者快n 倍，同时还需要存储器的带宽也是前者的n 倍。
第六章 机群系统
试区分和例示下列关于机群的术语： 1）专用机群和非专用机群； 2）同构机群和异构机群； 3）专用型机群和企业型机群。 答：
1） 根据节点的拥有情况，分为专用机群和非专用机群，在专用机群中所有的资源是共享的，
并行应用可以在整个机群上运行，而在非专用机群中，全局应用通过窃取CPU 时间获得运行，非专用机群中由于存在本地用户和远地用户对处理器的竞争，带来了进程迁移和负载平衡问题。
2） 根据节点的配置分为同构机群和异构机群，同构机群中各节点有相似的的体系，并且使
用相同的操作系统，而异构机群中节点可以有不同的体系，运行的操作系统也可以不同。 3） 专用型机群的特点是紧耦合的、同构的，通过一个前端系统进行集中式管理，常用来代
替传统的大型超级计算机系统；而企业型机群是松耦合的，一般由异构节点构成，节点可以有多个属主，机群管理者对节点有有限的管理权。
试解释和例示一下有关单一系统映像的术语： 1）单一文件层次结构；
2）单一控制点；
3）单一存储空间；
4）单一进程空间；
5）单一输入/输出和网络。
答：
1）用户进入系统后所见的文件系统是一个单一的文件和目录层次结构，该系统透明的将本地磁盘、全局磁盘和其他文件设备结合起来。
2）整个机群可以从一个单一的节点对整个机群或某一单一的节点进行管理和控制。
3）将机群中分布于各个节点的本地存储器实现为一个大的、集中式的存储器。
4）所有的用户进程，不管它们驻留在哪个节点上，都属于一个单一的进程空间，并且共享一个统一的进程识别方案。
5）单一输入/输出意味着任何节点均可访问多个外设。单一网络是任一节点能访问机群中的任一网络连接。
就Solaris MC系统回答下列问题：
1）Solaris MC 支持习题中单一系统映像的哪些特征不支持哪些特征
2）对那些Solaris MC 支持的特征，解释一下Solaris MC是如何解决的。
答：
1）支持单一文件层次结构、单一进程空间、单一网络和单一I/O空间。不支持单一控制点和单一的存储空间。
2）Solaris使用了一个叫PXFS的全局文件系统GFS。PXFS文件系统的主要特点包括：单一系统映像、一致的语义及高性能。PXFS通过在VFS/vnode接口上截取文件访问操作实现单一系统映像，保证了单一文件层次结构。
Solaris MC提供了一个全局进程标示符pid可定位系统所有进程，一个进程可以迁移到其他节点，但它的宿主节点中总记录有进程的当前位置，它通过在Solaris核心层上面增加一个全局进程以实现单一进程空间，每个节点有一个节点管理程序，每个本地进程有一个虚拟进程对象vproc，vproc保留每个父进程和子进程的信息，实现了全局进程的管理。
单一网络和I/O空间通过一致设备命名技术和单一网络技术实现。
举例解释并比较以下有关机群作业管理系统的术语：
1）串行作业与并行作业；
2）批处理作业与交互式作业；
3）机群作业和外来作业；
4）专用模式、空间共享模式、时间共享模式；
5）独立调度与组调度。
答：
1）串行作业在单节点上运行，并行作业使用多个节点。
2）批处理作业通常需要较多的资源，如大量的内存和较长的CPU时间，但不需要迅速的反应；交互式作业要求较快的周转时间，其输入输出直接指向终端设备，这些工作一般不需要大量资源，用户期望它们迅速得到执行而不必放入队列中。
3）机群作业时通过使用JMS功能分布实现的用户作业，用户服务器位于任一主机节点，资源管理器跨越所有的机群节点。外来作业在JMS之外生成的，如NOW上的一个工作站拥有者启动的外部作业，它不提交给JMS。
4）专用模式：任一时候只有一个作业在机群上运行，任一时候也只有一个作业进程分配给一个节点。空间共享模式：多个作业可以在不重叠的节点区域上运行。时间共享模式：在专用模式和空间共享模式下，只有一个用户进程分配给一个节点，但是所有的系统进程或监护程序仍在同一个节点上运行。
5）独立调度：各节点OS进行自己的调度，但这会显著损坏并行作业的性能，因为并行作业的进程间需要交互。组调度：将并行作业的所有进程一起调度。一个进程激活时，所有进程都被激活。
针对LSF回答下列问题：
1）对LSF的四种作业类型各举一个例子；
2）举一个例子说明外来作业；
3）对一个有1000个服务器的机群，为什么LSF负载分配机制优于：1整个机群只有一个LIM
或者2所有LIM都是主机说明原因。
答：
1）交互式：用户使用lshosts命令就可以列出每个服务器节点的静态资源，实现交互。批处理：lsbatch实用程序允许通过LSF提交、监控和执行批处理作业。串行：用户一旦进入lstcsh shell，发送的每条命令自动在最适合的节点上执行。并行：lsmake实用程序是UNIX make实用程序时一个并行版本，允许在多个节点同时处理一个Makefile。2）不通过LSF执行的称为外来作业。例如执行一些本地作业：字处理，web网络浏览等。3）机群的服务器数目太多，如果只采用一个LIM会导致LIM的负责过重，不能及时的处理响应所有服务器的请求和分派所有机群作业；如果采用2会导致LIM之间相互交换负载信息过多，导致网络通信量过大。
为什么在分布式文件系统中，UNIX语义难以实现有哪些放松的文件共享语义采用放松的文件共享语义会有一些什么缺点
答：
在UNIX语义中，一个修改过的块应该立刻被所有其他应用程序见到。然而分布式的文件系统中，多个节点可能存放了同一文件块的拷贝，当其中一个节点修改文件可的拷贝时，其他节点不能立刻就知道，这就使得UNIX语义难以实现。放松的文件共享语义有：对话语义、类事物语义、不可改变的共享文件语义等。采用放松的文件共享语义要求应用程序员修改程序代码，以适用这种新的语义，这就增加了程序员的负担。
试解释在机群并行文件系统中，为什么采用软件RAID、高速缓存机制和预取能够提高文件系统性能。
答：
软件RAID是文件系统负责分布数据和维护容错级别，能够和RAID5有一样的性能，实现机群磁盘间的数据分布，提高了I/O系统的传输带宽。高速缓存是将应用程序要取的块放在CACHE中，根据局部性原理，应用程序可以基本上从CACHE中读取数据块，而不要通过读取内存或硬盘，提高了读取速度。预取是在真正读取数据块之前就将这些数据块读入内存，这也提高了I/O性能，改善了文件系统性能。
讨论并行文件系统协作化高速缓存的基本技术前提是什么这个前提有什么意义
答：
基本技术前提是互联网络的速度很快，一个节点需要的文件块在其他节点的缓存中，那么就不需要从磁盘读，而是直接从其他节点的缓存中读出。这个前提的意义是可以提高系统的性能，使得节点间的协作化缓存变得更有意义。
回答以下关于Berkeley NOW项目的问题：
1）Berkeley NOW项目支持单一系统映像的哪几个方面即单入口点、单文件层次结构、单控制点、单存储空间、单进程空间哪个的哪几项并解释如何支持。
2）解释Berkeley NOW项目用来提高性能的四个结构特征。
3）解释Berkeley NOW项目和SP机群四个体系结构的差异，并讨论各自的优点。
答：
1）通过用户级整个机群软件GLUNIX，提供单一系统映像。开发了一种新的无服务器网络文件系统xFS，以支持单一文件层次结构。
2）主动消息通信协议，支持有效的通信；机群软件GLUNIX提供单一的系统映像、资源管理和可用性；xFS支持可扩放性和单一文件层次结构的高可用性；软件框架WebOS构筑高可用性、渐增可扩放性。
3）SP机群的体系结构特征：每个节点都是RS/600工作站，并有自己的局部磁盘；每个节点内驻留一个完整的AIX；各节点通过其I/O总线连接到专门设计的多级高速网络；尽量使用标准工作站部件。这样的优点是简单性和灵活性。
考虑xFS，并回答下列问题：
1）解释xFS和集中式文件服务器的两个不同点，并讨论各自的优点；
2）解释xFS用来提高可用性的主要技术；
3）解释xFS用来减轻小—写问题的主要技术。
答：
1）无服务器文件系统xFS将文件服务的功能分布到机器的所有节点上，xFS中所有的服务
器和客户的功能由分散的所有节点实现之。这与集中文件服务器的中央存储、中央缓存、中央管理不同。xFS的优点是采用分布式管理和协同文件缓存以及冗余磁盘阵列，这提高了系统的可用性以及I/O的性能和吞吐量。集中式文件服务器会减少缓存的不一致性，管理简单。
2）xFS提高可用性的主要技术是采用廉价冗余磁盘阵列RAID。无工作站文件系统能用来生成软件RAID，以提高性能和高可用性。现在xFS使用单奇偶校验磁盘条。一个文件数据块在多个存储服务器节点上按条划分，在另一个节点上有奇偶校验块。如果一个节点失效，失效磁盘的内容，可利用其余盘和奇偶盘之异或操作重建之。
3）xFS使用日志条的方法解决小—写问题：每个用户首先将写接合到各用户的日志上；然后此日志采用日志段提交给磁盘，每个段系由K-1个日志片组成，它与奇偶校验片以道送给K个存储服务器。
第七章分布式共享存储系统
什么是分布式共享存储系统，它相对于共享存储系统与分布式系统有哪些优点
答：分布式共享存储系统，是把共享存储器分成许多模块并分布于各处理机之中。分布式系统中采用消息传递通信，性能提高了，但多地址空间不利于程序员编程。共享存储系统支持传统的单地址空间，但共享必然引起冲突，形成瓶颈，于是分布式共享存储系统结合两者的优点。
释放一致性模型(RC)把处理器一致性(PC)和弱一致性模型(WC)的优点结合在一起了。
试回答下面有关这些一致性模型的问题：
a)比较这三种一致性模型的实现要求。
b)评论每种一致性模型的优缺点。
答：a)处理器一致性要求：①在任一取数操作LOAD允许被执行之前，所有在同一处理器中先于这一LOAD的取数操作都已完成；②在任一存数操作STORE允许执行之前，所有在同一处理器中先于这一STORE的访存操作（包括取数操作和存数操作）都已完成。弱一致性模型要求：①同步操作的执行满足顺序一致性条件；②在任一普通访存操作允许被执行之前，所有在同一处理器中先于这一访存操作的同步操作都已完成；③在任一同步操作允许被执行之前，所
有在同一处理器中先于这一同步操作的普通访存操作都已完成。释放一致性模型要求：①在任一普通访存操作允许被执行之前，所有在同一处理器中先于这一访存操作的获取操作acquire都已完成；②在任一释放操作release允许被执行之前，所有在同一处理器中先于这一release的普通访存操作都已完成；③同步操作的执行满足顺序一致性条件。
b)三种模型对存储顺序要求逐渐降低，可优化程度逐渐增加，但是对程序员的要求也越来越高，所以释放性一致性是性能与复杂度的折中。
在DSM系统的顺序一致性存储模型下，有三个并行执行的进程如下所示，试问001110是不是一个合法的输出并加以解释。
P1P2P3
A=1;B=1;C=1;
Print(b,c);Print(a,c);Print(a,b);
答：不是一个合法输出。考虑顺序一致性存储模型，每个进程的程序序会被维护，那么无论哪个进程最后执行Print语句，则之前的A=1，B=1,C=1都已经完成，所以输出的两后两项必为11，所以001110不是合法输出。
试分类下面来自三个处理器的引用流的高速缓存缺失。假设每一个处理器的高速缓存只有一个4个字的高速缓存行，字W0到W3、W4到W7分别处于同一个高速缓存行。
如果一行有多个引用，我们假设P1在P2之前发射、P2在P3之前发射内存引用，符号 LD/ST Wi表示LOAD/STORE 字i。
答：操作序号3、6、8、12-15都是单操作。操作序号1、2、9-11为无关存储操作，由于不在同一块中。操作序号4、7为对同一缓存块的连续两次LD，需要按序进行。
假设系统中共有512个处理器和1GB主存，每个节点内有8个处理器对目录可见，一个高速缓存行的大小为64字节，那么在(a) 满位向量方案和(b) Dr i B(i=3)模型下目录的存储成本各是多少
答：分别为总容量的12.%和%。
细数一下中心目录与分布式目录方案的实现方法与各自的使用情况。
答：中心目录是用一个中心目录存放所有高速缓存目录的拷贝，中心目录能提供为保证一致性所需要的全部信息。因此，其容量非常大且必须采用联想方法进行检索，这和单个高速缓存的目录类似。大型多处理机系统采用中心目录会有冲突和检索时间过长两个缺点。
分布式目录方案是由Censier和Feautrier提出来。在分布式目录中每个存储器模块维护各自的目录，目录中记录着每个存储器块的状态和当前的信息，其中状态信息是本地的，而当前信息指明哪些高速缓存中有该存储器块的拷贝。
一般来说，在共享存储上实现中心目录，而在分布式系统上实现分布式目录方案更为合适一些，但这也并不是绝对的。
在研究DSM的读写代价和实现问题时有这样两种算法，即中央服务器算法和迁移算法：中央服务器算法是指使用一个中央服务器，负责为所有对共享数据的访问提供服务并保持共享数
据唯一的副本；迁移算法是指要访问的数据总是被迁移到访问它的节点中。两种算法图示如下：
中央服务器算法
迁移算法
现假设报文数量不会导致网络阻塞，服务员的阻塞没有严重到能够极大地延迟远程进程访问，访问本地数据的代价与远程访问代价相比微不足道，报文传递也是可靠的。
试分析两种算法的适合情况。
答：中央服务器算法，每次顾客发送数据请求到中央服务器，地址计算简单，适合多个顾客频繁轮流读写。迁移算法每次确定位置需要一定开销，适用于单个顾客频繁对数据读写，因为访问数据总是被迁移到访问节点里。
下面是运行在一个硬件维护高速缓存一致性的多处理机上的程序段，假设所有值初始为0。
P1 P2 P3 P4
A=1 U=A W=A A=2
V=A X =A
只有一个共享变量A，假设一个用户知道所有高速缓存拷贝的地址并且可直接对(不
需要和目录节点协商)拷贝进行更新，假设采用写更新协议。试构造出一个写原子性被违背的情况：
说明产生的结果违背了顺序一致性；
答：如果进程P1首先对含有共享变量A的数据块进行写操作，进程P2、P3执行U=A和W=A，分别将U、W置为1。此时P4对共享变量A进行写操作，并且同时更新P1、P2、P3中的值，此后P2、P3再执行V=A，X=A，此时V与X被置为了2。对于进程2来说，结果违背了顺序一致性。
参照下述代码段：
问：000000是不是PARM一致性内存模型的合法输出解释原因说明顺序一致性与PARM一致性区别
a=1; b=1; c=1;
Print(b, c); Print(a, c); Print(a, b);
(a)P1 (b) P2 (c)P3
答：在PARM一致性内存模型下，000000是合法输出，因为PARM不关注存储相关性，即同一进程程序序可以优化，这样各进程先执行打印完再执行赋值则出现如上情况。顺序一致性与PARM一致性的区别就是于是否关注存储相关性。
有两个并行的过程P1、P2（如下图所示），在顺序一致性模型下，试列出所有可能的6种语句交错执行顺序，使两进程不可能同时被kill。
a=1; b=1;
if(b= =0)kill(P2); if(a= =0)kill(P1);
(P1) (P2)
答：（1）a=1;
if(a= =0)kill(P1);
b=1;
if(b= =0)kill(P2);
(2) a=1;
b=1;
if(a= =0)kill(P1);
if(b= =0)kill(P2);
(3) b=1;
if(a= =0)kill(P1);
a=1;
if(b= =0)kill(P2);
(4) b=1;
if(a= =0)kill(P1);
if(b= =0)kill(P2);
a=1;
(5) a=1;
if(a= =0)kill(P1);
if(b= =0)kill(P2);
b=1;
(6) if(a= =0)kill(P1);
if(b= =0)kill(P2);
a=1;
b=1;
分析以上6种情况，在满足顺序一致性模型前提下，不会存在P1、P2同时被KILL的情况。
并行计算综述
并行计算综述 姓名：尹航学号：S131020012 专业：计算机科学与技术摘要：本文对并行计算的基本概念和基本理论进行了分析和研究。主要内容有：并行计算提出的背景，目前国内外的研究现状，并行计算概念和并行计算机类型，并行计算的性能评价，并行计算模型，并行编程环境与并行编程语言。 关键词：并行计算；性能评价；并行计算模型；并行编程 1. 前言 网络并行计算是近几年国际上并行计算新出现的一个重要研究方向，也是热门课题。网络并行计算就是利用互联网上的计算机资源实现其它问题的计算，这种并行计算环境的显著优点是投资少、见效快、灵活性强等。由于科学计算的要求，越来越多的用户希望能具有并行计算的环境，但除了少数计算机大户（石油、天气预报等）外，很多用户由于工业资金的不足而不能使用并行计算机。一旦实现并行计算，就可以通过网络实现超级计算。这样，就不必要购买昂贵的并行计算机。 目前，国内一般的应用单位都具有局域网或广域网的结点，基本上具备网络计算的硬件环境。其次，网络并行计算的系统软件PVM是当前国际上公认的一种消息传递标准软件系统。有了该软件系统，可以在不具备并行机的情况下进行并行计算。该软件是美国国家基金资助的开放软件，没有版权问题。可以从国际互联网上获得其源代码及其相应的辅助工具程序。这无疑给人们对计算大问题带来了良好的机遇。这种计算环境特别适合我国国情。 近几年国内一些高校和科研院所投入了一些力量来进行并行计算软件的应用理论和方法的研究，并取得了可喜的成绩。到目前为止，网络并行计算已经在勘探地球物理、机械制造、计算数学、石油资源、数字模拟等许多应用领域开展研究。这将在计算机的应用的各应用领域科学开创一个崭新的环境。 2. 并行计算简介[1] 2.1并行计算与科学计算 并行计算（Parallel Computing），简单地讲，就是在并行计算机上所作的计算，它和常说的高性能计算（High Performance Computing）、超级计算（Super Computing）是同义词，因为任何高性能计算和超级计算都离不开并行技术。
汽车成功案例
汽车成功案例 安全性问题 竞争优势 全球汽车工业对汽车安全性越来越重视，与安全强制法规相关的试验也在大量增加。目前碰撞安全问题在碰撞前、碰撞中和碰撞后阶段同时展开研究。在碰撞前阶段利用主动避撞系统；在碰撞中阶段利用车身结构、气囊展开、安全带张紧等措施减小伤害；在碰撞后阶段，主要关心油箱是否破裂以防止爆炸或起火。MSC.Software虚拟产品开发设计能够对每一个阶段进行设计研究。 碰撞前阶段 避免碰撞发生当然是车辆交通中最有效的降低伤亡的方法。而车辆的行为，例如车辆打滑、侧翻、或者车轮遇到冰路面将会发生何种状况等等可以利用虚拟样机来预测。在ADAMS/Car中结合多刚体和控制的仿真可以模拟从主动悬架到ABS制动器等系统的试验来增加主动安全性。通过同步调整机械、控制系统对车辆进行优化，可以大大缩短设计周期。 碰撞中阶段 一旦碰撞不可避免，气囊展开和座椅安全带的预张紧就成为减小伤害的关键因素，虚拟产品开发能够对这些系统进行优化。气囊展开可以利用SimOffice中的MSC Dytran，安全带约束系统的力可以利用多体仿真分析软件。在样车建造和法规试验之前进行虚拟试验可以大大地降低开发费用。法规试验中车辆各种性能可以用SimOffice中提供的有限元方法来进行精确地预测和研究。
碰撞仿真流程通常需要大量人力，管理仿真产生的海量数据也是一个挑战。模型组装、质量检查、定义工况、报告准备等方面如果引入流程自动化和数据管理则可以节省大量的人力。MSC.Software是领先的流程管理和自动化工具供应商，其产品MSC SOFY 和MSC SimManager都提供了汽车碰撞流程自动化的环境。将工作流程确定下来并进行客户化配置后，软件工具可以自动地生成代码来指导用户完成工作流程。例如，德国宝马(BMW)公司利用MSC SimManager建立碰撞仿真自动化流程，管理海量仿真数据，并且可以和供应商合作，使供应商可以上载各自相关的部件。 LSTC公司的领先的碰撞求解器LS-Dyna可以通过MSC Nastran（Sol700）的标准格式来调用。因此，适撞性和显著非线性问题都可以采用和NVH部门同样的模型，这样通过不同部门的协作可以节省大量的时间和费用。 碰撞后阶段 避免碰撞后起火取决于供油系统的完整性，该项安全要求 已在美国安全法规FMVSS301中有明确规定。车辆碰撞 后的燃油泄漏必须避免，MSC.Dytran采用拉格朗日和欧 拉技术，可以模拟碰撞中和碰撞后油箱的液固作用、结构 大变形、结构接触等问题。 MSC.SimManager也可以集成到碰撞后开发流程中，一 级供应商TI汽车公司采用MSC.SimManager管理油箱 开发过程中的冲击、压力真空、跌落、下陷等试验。 车辆动力学问题 矛盾 汽车工业需要在开发过程中减少时间和费用，同时推出创 新的产品。当前比较通用的策略是利用通用的开发平台、 共享部件开发众多系列车型。这就导致出现两个相互矛盾 的目标：一个是新系统的开发，另一个是通过共用平台和 零部件减少系统的变型。借助于虚拟产品开发可以有效地 满足这两个目标。
并行计算 - 练习题
2014年《并行计算系统》复习题 1.（15分）给出五种并行计算机体系结构的名称，并分别画出其典型结构。 ①并行向量处理机（PVP） ②对称多机系统（SMP） ③大规模并行处理机（MPP） ④分布式共享存储器多机系统（DSM）
⑤工作站机群（COW） 2.（10分）给出五种典型的访存模型，并分别简要描述其特点。 ①均匀访存模型（UMA）： 物理存储器被所有处理机均匀共享 所有处理机访存时间相同 适于通用的或分时的应用程序类型 ②非均匀访存模型（NUMA）： 是所有处理机的本地存储器的集合 访问本地LM的访存时间较短
访问远程LM的访存时间较长 ③Cache一致性非均匀访存模型（CC-NUMA）： DSM结构 ④全局Cache访存模型（COMA）： 是NUMA的一种特例，是采用各处理机的Cache组成的全局地址空间 远程Cache的访问是由Cache目录支持的 ⑤非远程访存模型（NORMA）： 在分布式存储器多机系统中，如果所有存储器都是专用的，而且只能被本地存储机访问，则这种访问模型称为NORAM 绝大多数的NUMA支持NORAM 在DSM中，NORAM的特性被隐匿的 3. （15分）对于如下的静态互连网络，给出其网络直径、节点的度数、对剖宽度，说明该网络是否是一个对称网络。 网络直径：8 节点的度数：2
对剖宽度：2 该网络是一个对称网络 4. （15分）设一个计算任务，在一个处理机上执行需10个小时完成，其中可并行化的部分为9个小时，不可并行化的部分为1个小时。问： （1）该程序的串行比例因子是多少，并行比例因子是多少？ 串行比例因子：1/10 并行比例因子:9/10 （2）如果有10个处理机并行执行该程序，可达到的加速比是多少？10/(9/10 + 1) = 5.263 （3）如果有20个处理机并行执行该程序，可达到的加速比是多少？10/(9/20 + 1)= 6.897 5.（15分）什么是并行计算系统的可扩放性？可放性包括哪些方面？可扩放性研究的目的是什么？ 一个计算机系统（硬件、软件、算法、程序等）被称为可扩放的，是指其性能随处理机数目的增加而按比例提高。例如，工作负载能力和加速比都可随处理机的数目的增加而增加。 可扩放性包括: 1.机器规模的可扩放性
有限元仿真技术的发展及其应用
有限元仿真技术的发展及其应用 许荣昌 孙会朝(技术研发中心) 摘 要:介绍了目前常用的大型有限元分析软件的现状与发展,对其各自的优势进行了分析,简述了有限元软件在冶金生产过程中的主要应用领域及其发展趋势,对仿真技术在莱钢的应用进行了展望。 关键词:有限元仿真 冶金生产 发展趋势 0 前言 自主创新,方法先行,创新方法是自主创新的根本之源,同时,随着市场竞争的日益激烈,冶金企业的产品设计、工艺优化也由经验试错型向精益研发方向发展,而有限元仿真技术正是这种重要的创新方法。近年来随着计算机运行速度的不断提高,有限元分析在工程设计和分析中得到了越来越广泛的应用,比如,有限元分析在冶金、航空航天、汽车、土木建筑、电子电器、国防军工、船舶、铁道、石化、能源、科学研究等各个领域正在发挥着重要的作用,主要表现在以下几个方面:增加产品和工程的可靠性;在产品的设计阶段发现潜在的问题;经过分析计算,采用优化设计方案,降低原材料成本;缩短产品研发时间;模拟试验方案,减少试验次数,从而减少试验成本。与传统设计相比,利用仿真技术,可以变经验设计为科学设计、变实测手段为仿真手段、变规范标准为分析标准、变传统分析技术为现代的计算机仿真分析技术,从而提高产品质量、缩短新产品开发周期、降低产品整体成本、增强产品系统可靠性,也就是增强创新能力、应变能力和竞争力(如图1、2) 。 图1 传统创新产品(工艺优化)设计过程为大循环 作者简介:许荣昌(1971-),男,1994年毕业于武汉钢铁学院钢铁冶金专业,博士,高级工程师。主要从事钢铁工艺技术研究工 作。 图2 现代CA E 创新产品(工艺优化)设计过程为小循环 1 主要有限元分析软件简介 目前,根据市场需求相继出现了各种类型的应用软件,其中NASTRAN 、ADI N A 、ANSYS 、 ABAQUS 、MARC 、MAGSOFT 、COS MOS 等功能强大的CAE 软件应用广泛,为实际工程中解决复杂的理论计算提供了非常有力的工具。但是,各种软件均有各自的优势,其应用领域也不尽相同。本文将就有限元的应用范围及当今国际国内C AE 软件的发展趋势做具体的阐述,并对与冶金企业生产过程密切相关的主要有限元软件ANSYS 、AB AQUS 、MARC 的应用领域进行分析。 M SC So ft w are 公司创建于1963年,总部设在美国洛杉矶,M SC M arc 是M SC Soft w are 公司于1999年收购的MARC 公司的产品。MARC 公司始创于1967年,是全球首家非线性有限元软件公司。经过三十余年的发展,MARC 软件得到学术界和工业界的大力推崇和广泛应用,建立了它在全球非线性有限元软件行业的领导者地位。随着M arc 软件功能的不断扩展,软件的应用领域也从开发初期的核电行业迅速扩展到航空、航天、汽车、造船、铁 道、石油化工、能源、电子元件、机械制造、材料工程、土木建筑、医疗器材、冶金工艺和家用电器等,成为许多知名公司和研究机构研发新产品和新技术的重要工具。在航空业M SC N astran 软件被美国联邦航空管理局(F AA )认证为领取飞行器适 13
并行计算-期末考试模拟题原题
Reviews on parallel programming并行计算英文班复习考试范围及题型：（1—10章） 1 基本概念解释；Translation (Chinese) 2 问答题。Questions and answer 3 算法的画图描述。Graphical description on algorithms 4 编程。Algorithms Reviews on parallel programming并行计算 1 基本概念解释；Translation (Chinese) SMP MPP Cluster of Workstation Parallelism, pipelining, Network topology, diameter of a network, Bisection width, data decomposition, task dependency graphs granularity concurrency process processor, linear array, mesh, hypercube, reduction,
prefix-sum, gather, scatter, thread s, mutual exclusion shared address space, synchronization, the degree of concurrency, Dual of a communication operation, 2 问答题。Questions and answer Chapter 1 第1章 1) Why we need parallel computing? 1）为什么我们需要并行计算？ 答： 2) Please explain what are the main difference between parallel computing and sequential computing 2）解释并行计算与串行计算在算法设计中的主要不同点在那里？ 答： Chapter 2 第2章 1) What are SIMD, SPMD and MIMD denote? 1）解释SIMD, SPMD 和 MIMD是什么含义。 答： 2) Please draw a typical architecture of SIMD and a typical architecture of MIMD to explan. 2）请绘制一个典型的SIMD的体系结构和MIMD的架构。 答：
并行计算(天津大学软件学院)
并行计算 一、并行计算概述 1.并行计算定义： 并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程。为执行并行计算，计算资源应包括一台配有多处理机（并行处理）的计算机、一个与网络相连的计算机专有编号，或者两者结合使用。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本―使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。 为利用并行计算，通常计算问题表现为以下特征： （1）将工作分离成离散部分，有助于同时解决； （2）随时并及时地执行多个程序指令； （3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。 并行计算是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。2.并行化方法 1)域分解 首先，确定数据如何划分到各个处理器 然后，确定每个处理器所需要做的事情 示例：求数组中的最大值 2)任务（功能）分解 首先，将任务划分到各个处理器 然后，确定各个处理器需要处理的数据 Example: Event-handler for GUI 二、并行计算硬件环境 1.并行计算机系统结构 1)Flynn分类 a. MIMD 多指令流多数据流(Multiple Instruction Stream Multiple Data Stream，简称MIMD)，它使用多个控制器来异步的控制多个处理器，从而实现空间上的并行性。 对于大多数并行计算机而言，多个处理单元都是根据不同的控制流程执行不同的操作，处理不同的数据，因此，它们被称作是多指令流多数据流计算机 b. SIMD 单指令流多数据流(Single Instruction Multiple Data)能够复制多个操作数，并把它们打包在大型寄存器的一组指令集，以同步方式，在同一时间内执行同一条指令。 以加法指令为例，单指令单数据（SISD）的CPU对加法指令译码后，执行部件先访问内存，取得第一个操作数；之后再一次访问内存，取得第二个操作数；随后才能进行求和运算。而在SIMD型的CPU中，指令译码后几个执行部件同时访问内存，一次性获得所有操作数进行运算。这个特点使SIMD特别适合于多媒体应用等数据密集型运算。 2)并行计算及结构模型 a. SMP SMP (Symmetric Multiprocessor) 采用商品化的处理器，这些处理器通过总线或交叉开关连接到共享存储器。每个处理器可等同地访问共享存储器、I/O设备和操作系统服务。 扩展性有限。
PCC性能改进
淮阴工学院 毕业设计外文资料翻译 学院：建筑工程学院 专业：土木工程房建方向 姓名：王玮 学号：1091401422 外文出处：MBTC DOT 3022 August 16 2012 附件： 1.外文资料翻译译文；2.外文原文。 指导教师评语： 签名： 年月日
以纳米技术为基础对硅酸盐 水泥混凝土的性能改进——第一阶段 Dr. R. Panneer Selvam ，Dr. Kevin Hall ，Sayantan Bhadra 摘要：对硅酸盐水泥混凝土(PCC)的纳米结构的基本认识是实现高性能和可持续性相关重大突破的关键。MBTC-研究(MBTC 2095/3004)使用分子动力学(MD)提供了对于水化硅酸钙(CSH)结构的新的理解(提供PCC强度和耐久性的主要成分);然而，由于MD方法能够考虑的原子数量，这项研究是有局限性的，特别是关于PCC中纳米水平上的力学性能。在这篇论文中为了断定CSH凝胶结构提出了离散元素法(DEM)，报告了三个阶段中第一阶段所取得的进展。给出了DEM研究所用的现有的免费软件和商法典。制定了一种内部的DEM规范，对粘性材料采用压痕式加载。样本模型计算合理的说明了DEM规范的发展及应用。 关键词：纳米技术，硅酸盐水泥混凝土，离散单元法 第一章：引言 混凝土是使用最多的建筑材料，同时也是科学了解最少的材料。混凝土的寿命由于收缩裂缝、拉伸裂缝等受到限制。这主要是由于水泥浆复杂的无定形的结构。对于铜或铁来说很容易从实验中发现原子结构。由于超过5个不同的原子结合在一起形成水泥浆或CSH(Murray等人，2010& Janikiram Subramaniam等人2009)，很难从实验来了解原子结构。对硅酸盐水泥混凝土(PCC)的纳米结构的基本认识是实现高性能和可持续性相关重大突破的关键。最近通过MBTC 2095/3004项目，使用分子动力学(MD)得出CSH原子结构的一些理解。Selvam教授和他的团队(2009 -2011)使用分子动力学(MD)建模提出了可能的CSH原子结构。从纳米水平到宏观水平进一步的相关性能的研究由于考量纳米长度变化时需要考虑的原子数量的限制而受到局限。 Nonat(2004)和Gauffinet(1998)等人观察到C-S-H凝胶有片晶型形态，薄片的大小约为60 ×30×5nm。从Dagleish拍摄的AFM图像（如图1.1）看出，CSH纤维可能的大小为60 nm x 300μm。为了理解这些纤维之间的相互作用，需要的计算尺
并行算法设计与分析考题与答案
《并行算法设计与分析》考题与答案 一、1.3，处理器PI的编号是： 解：对于n ×n 网孔结构,令位于第j行，第k 列（0≤j，k≤n-1）的处理器为P i（0≤i≤n2-1）。以16处理器网孔为例,n=4（假设j、k由0开始）： 由p0=p(j,k)=p(0,0) P8=p(j,k)=p(2,0) P1=p(j,k)=p(0,1) P9=p(j,k)=p(2,1) P2=p(j,k)=p(0,2) P10=p(j,k)=p(2,2) P3=p(j,k)=p(0,3) P11=p(j,k)=p(2,3) P4=p(j,k)=p(1,0) P12=p(j,k)=p(3,0) P5=p(j,k)=p(1,1) P13=p(j,k)=p(3,1) P6=p(j,k)=p(1,2) P14=p(j,k)=p(3,2) P7=p(j,k)=p(1,3) P15=p(j,k)=p(3,3) 同时观察i和j、k之间的关系，可以得出i的表达式为：i= j * n+k
一、1.6矩阵相乘（心动算法） a)相乘过程 设 A 矩阵= 121221122121 4321 B 矩阵=1 23443212121121 2 【注】矩阵元素中A(i,l)表示自左向右移动的矩阵，B(l,j)表示自上向下移动的矩阵，黑色倾斜加粗标记表示已经计算出的矩阵元素,如12, C(i,j)= C(i,j)+ A(i,l)* B(l,j) 1 2、
4、
6、
8、
10 计算完毕 b)可以在10步后完成，移动矩阵长L=7，4*4矩阵N=4,所以需要L+N-1=10
蒙特卡罗方法并行计算
Monte Carlo Methods in Parallel Computing Chuanyi Ding ding@https://www.wendangku.net/doc/3a5662330.html, Eric Haskin haskin@https://www.wendangku.net/doc/3a5662330.html, Copyright by UNM/ARC November 1995 Outline What Is Monte Carlo? Example 1 - Monte Carlo Integration To Estimate Pi Example 2 - Monte Carlo solutions of Poisson's Equation Example 3 - Monte Carlo Estimates of Thermodynamic Properties General Remarks on Parallel Monte Carlo What is Monte Carlo? ? A powerful method that can be applied to otherwise intractable problems ? A game of chance devised so that the outcome from a large number of plays is the value of the quantity sought ?On computers random number generators let us play the game ?The game of chance can be a direct analog of the process being studied or artificial ?Different games can often be devised to solve the same problem ?The art of Monte Carlo is in devising a suitably efficient game.
并行计算-习题及答案-第12章 并行程序设计基础
第十二章 并行程序设计基础 习题例题： 1、假定有n 个进程P(0)，P(1)，…，P(n -1)，数组元素][i a 开始时被分配给进程P(i )。试写出求归约和]1[]1[]0[-+++n a a a 的代码段，并以8=n 示例之。 2、假定某公司在银行中有三个账户X 、Y 和Z ，它们可以由公司的任何雇员随意访问。雇员们对银行的存、取和转帐等事务处理的代码段可描述如下： /*从账户X 支取￥100元*/ atomic { if (balance[X] > 100) balance[X] = balance[X]-100； } /*从账户Y 存入￥100元*/ atomic {balance[Y] = balance[Y]-100；} /*从账户X 中转￥100元到帐号Z*/ atomic { if (balance[X] > 100){ balance[X] = balance[X]-100； balance[Z] = balance[Z]+100； } } 其中，atomic {}为子原子操作。试解释为什么雇员们在任何时候（同时）支、取、转帐时，这些事务操作总是安全有效的。 3、考虑如下使用lock 和unlock 的并行代码： parfor (i = 0；i < n ；i++){ noncritical section lock(S)； critical section unlock(S)； }
假定非临界区操作取T ncs时间，临界区操作取T cs时间，加锁取t lock时间，而去锁时间可忽略。则相应的串行程序需n( T ncs + T cs )时间。试问： ①总的并行执行时间是多少？ ②使用n个处理器时加速多大？ ③你能忽略开销吗？ 4、计算两整数数组之内积的串行代码如下： Sum = 0； for(i = 0；i < N；i++) Sum = Sum + A[i]*B[i]； 试用①相并行；②分治并行；③流水线并行；④主-从行并行；⑤工作池并行等五种并行编程风范，写出如上计算内积的并行代码段。 5、图12.15示出了点到点和各种集合通信操作。试根据该图解式点倒点、播送、散步、收集、全交换、移位、归约与前缀和等通信操作的含义。 图12.15点到点和集合通信操作
高性能计算报告
高性能计算实验报告 学生姓名：X X 学号：XXXXXXXXXX 班号：116122 指导教师：郭明强 中国地质大学（武汉）信息工程学院 第一题
1.编写console程序 2.由下图看出，电脑是双核CPU 3.多线程程序，利用windowsAPI函数创建线程
代码 #include"stdafx.h" #include
} 第二题多线程实现计算e和π的乘积 代码 #include"stdafx.h" #include"windows.h" #define num_steps 2000000 #include 按照计算每一时刻动力反应是否需要求解线性方程组，可将直接积分法分为隐式积分方法和显式积分方法两类。 隐式积分法是根据当前时刻及前几时刻体系的动力反应值建立以下一时刻动力反应值为未知量的线性方程组，通过求解方程组确定下一时刻动力反应。隐式方法的研究和应用由来已久，常用的方法有线性加速度法、常平均加速度法、Newmark方法、Wilson-θ法、Houbolt 方法等。 显式积分法可由当前时刻及前几时刻的体系动力反应值直接外推下一时刻的动力反应值，不需要求解线性方程组，实现了时间离散的解耦。解方程组一般占整个有限元求解程序耗时的70％左右，因此，这一解耦技术对计算量的节省是可观的。 隐式方法大部分是无条件稳定的，显式方法为条件稳定。显式方法的稳定性可以按满足精度要求的空间步距确定满足数值积分稳定性要求的时问步距来实现。显式方法受条件稳定的限制，时间积分步长将取得较小，但计算经验表明，对于一些自由度数巨大且介质呈非线性的问题，显式法比隐式法所需的计算量要小得多。 因此，随着所考虑问题复杂性的增加，显式积分法得到重视。 对于显式与隐式有限元的理解 关键字: 有限元显式隐式 显式算法和隐式算法，有时也称为显式解法和隐式解法，是计算力学中常见的两个概念，但是它们并没有普遍认可的定义，下面只是我的一些个人理解。 一、两种算法的比较 1、显式算法 基于动力学方程，因此无需迭代；而静态隐式算法基于虚功原理，一般需要迭代计算。显式算法，最大优点是有较好的稳定性。 动态显式算法采用动力学方程的一些差分格式（如广泛使用的中心差分法、线性加速度法、Newmark法和wilson法等），不用直接求解切线刚度，不需要进行平衡迭代，计算速度快，时间步长只要取的足够小，一般不存在收敛性问题。因此需要的内存也比隐式算法要少。并且数值计算过程可以很容易地进行并行计算，程序编制也相对简单。但显式算法要求质量矩阵为对角矩阵，而且只有在单元积分点计算尽可能少时速度优势才能发挥, 因而往往采用减缩积分方法，容易激发沙漏模式，影响应力和应变的计算精度。 静态显式法基于率形式的平衡方程组与Euler向前差分法，不需要迭代求解。由于平衡方程式仅在率形式上得到满足，所以得出的结果会慢慢偏离正确值。为了减少相关误差，必须每步使用很小的增量。 除了欧拉向前差分法外，其它的差分格式都是隐式的方法，需要求解线性方程组。 2、隐式算法 隐式算法中，在每一增量步内都需要对静态平衡方程进行迭代求解，并且每次迭代都需要求解大型的线性方程组，这以过程需要占用相当数量的计算资源、磁盘空间和内存。该算法中的增量步可以比较大，至少可以比显式算法大得多，但是实际运算中上要受到迭代次数及非线性程度的限制，需要取一个合理值。 二、求解时间 第二章习题（P69-70） 一、复习题 1．简述冯?诺依曼原理，冯?诺依曼结构计算机包含哪几部分部件，其结构以何部件为中心？ 答：冯?诺依曼理论的要点包括：指令像数据那样存放在存储器中，并可以像数据那样进行处理；指令格式使用二进制机器码表示；用程序存储控制方式工作。这3条合称冯?诺依曼原理 冯?诺依曼计算机由五大部分组成：运算器、控制器、存储器、输入设备、输出设备，整个结构一般以运算器为中心，也可以以控制器为中心。 (P51-P54) 2．简述计算机体系结构与组成、实现之间的关系。 答：计算机体系结构通常是指程序设计人员所见到的计算机系统的属性，是硬件子系统的结构概念及其功能特性。计算机组成（computer organization）是依据计算机体系结构确定并且分配了硬件系统的概念结构和功能特性的基础上，设计计算机各部件的具体组成，它们之间的连接关系，实现机器指令级的各种功能和特性。同时，为实现指令的控制功能，还需要设计相应的软件系统来构成一个完整的运算系统。计算机实现，是计算机组成的物理实现, 就是把完成逻辑设计的计算机组成方案转换为真实的计算机。计算机体系结构、计算机组成和计算机实现是三个不同的概念，各自有不同的含义，但是又有着密切的联系，而且随着时间和技术的进步，这些含意也会有所改变。在某些情况下，有时也无须特意地去区分计算机体系结构和计算机组成的不同含义。 (P47-P48) 3．根据指令系统结构划分，现代计算机包含哪两种主要的体系结构？ 答：根据指令系统结构划分，现代计算机主要包含：CISC和RISC两种结构。 (P55) 4．简述RISC技术的特点？ 答：从指令系统结构上看，RISC 体系结构一般具有如下特点： (1) 精简指令系统。可以通过对过去大量的机器语言程序进行指令使用频度的统计，来选取其中常用的基本指令，并根据对操作系统、高级语言和应用环境等的支持增设一些最常用的指令; (2) 减少指令系统可采用的寻址方式种类，一般限制在2或3种; (3) 在指令的功能、格式和编码设计上尽可能地简化和规整，让所有指令尽可能等长; (4) 单机器周期指令，即大多数的指令都可以在一个机器周期内完成，并且允许处理器在同一时间内执行一系列的指令。 (P57-58) 5．有人认为，RISC技术将全面替代CISC，这种观点是否正确，说明理由？ 答：不正确。与CISC 架构相比较，RISC计算机具备结构简单、易于设计和程序执行效率高的特点，但并不能认为RISC 架构就可以取代CISC 架构。事实上，RISC 和CISC 各有优势，CISC计算机功能丰富，指令执行更加灵活，这些时RISC计算机无法比拟的，当今时代，两者正在逐步融合，成为CPU设计的新趋势。 (P55-59) 6．什么是流水线技术？ 答：流水线技术，指的是允许一个机器周期内的计算机各处理步骤重叠进行。特别是，当执行一条指令时，可以读取下一条指令，也就意味着，在任何一个时刻可以有不止一条指令在“流水线”上，每条指令处在不同的执行阶段。这样，即便读取和执行每条指令的时间保持不变，而计算机的总的吞吐量提高了。 (P60-62) 7．多处理器结构包含哪几种主要的体系结构，分别有什么特点？ 答：多处理器系统：主要通过资源共享，让共享输入/输出子系统、数据库资源及共享或不共享存储的一组处理机在统一的操作系统全盘控制下，实现软件和硬件各级上相互作用，达到时间和空间上的异步并行。 SIMD计算机有多个处理单元，由单一的指令部件控制，按照同一指令流的要求为他们 ANSYS高性能并行计算 作者：安世亚太雷先华 高性能并行计算主要概念 ·高性能并行计算机分类 并行计算机主要可以分为如下四类：对称多处理共享存储并行机（SMP，Symmetric Multi-Processor）、分布式共享存储多处理机（DSM，Distributied Shared Memory）、大规模并行处理机（MPP，Massively Parallel Processor）和计算机集群系统（Cluster）。 这四类并行计算机也正好反映了高性能计算机系统的发展历程，前三类系统由于或多或少需要在CPU、内存、封装、互联、操作系统等方面进行定制，因而成本非常昂贵。最后一类，即计算机集群系统，由于几乎全采用商业化的非定制系统，具有极高的性能价格比，因而成为现代高性能并行计算的主流系统。它通过各种互联技术将多个计算机系统连接在一起，利用所有被连接系统的综合计算能力来处理大型计算问题，所以又通常被称为高性能计算集群。高性能并行计算的基本原理就是将问题分为若干部分，而相连的每台计算机（称为节点）均可同时参与问题的解决，从而显著缩短解决整个问题所需的计算时间。 ·集群互联网络 计算机集群系统的互联网络大体上经历了从Ethernet到Giganet、Myrinet、Infiniband、SCI、Quadrics(Q-net)等发展历程，在“延时”和“带宽”两个最主要指标上有了非常大的改善，下表即是常用的互联方式： ANSYS主要求解器的高性能并行计算特性 ANSYS系列CAE软件体系以功能齐全、多物理场耦合求解、以及协同仿真而著称于世。其核心是一系列面向各个方向应用的高级求解器，并行计算也主要是针对这些求解器而言。 ANSYS的主要求解器包括： Mechanical：隐式有限元方法结构力学求解器； CFX ：全隐式耦合多重网格计算流体力学求解器； AUTODYN：显式有限元混合方法流固耦合高度非线性动力学求解器； LS-DYNA：显式有限元方法非线性结构动力学求解器； FEKO：有限元法、矩量法、高频近似方法相互混合的计算电磁学求解器； ·高性能并行计算的典型应用 现代CAE计算的发展方向主要有两个：系统级多体耦合计算和多物理场耦合计算，前者摒弃了以往只注重零部件级CAE仿真的传统，将整个对象的完整系统（如整机、整车）一次性纳入计算范畴；后者在以往只注重单一物理场分析（如结构力学、流体力学）的基础上，将影响系统性能的所有物理因素一次性纳入计算范畴，考虑各物理因素综合起来对分析对象的影响。因此，可以说，高性能并行计算也是CAE的发展方向，因为它是大规模CAE 应用的基石。例如，在航空航天领域，需要高性能并行计算的典型CAE应用有： –飞机/火箭/导弹等大型对象整体结构静力、动力响应、碰撞、安全性分析，整体外流场分析，多天线系统电磁兼容性及高频波段RCS分析，全模型流体－结构－电磁耦合分析；–航空发动机多级转子/静子联合瞬态流动分析，流体－结构－热耦合分析； –大型运载火箭/导弹发射过程及弹道分析…… · ANSYS求解器对高性能并行计算的支持 作为大型商用CAE软件的领头雁，ANSYS在对高性能并行计算的支持方面也走在所有CAE软件的前列，其各个求解器对高性能并行系统的支持可用下表描述： 第三章互连网络 对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。 答： 推广至M元树时，k级M元树总结点数N的表达式为： N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m); 二元胖树如图所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络 答：8输入的完全混洗三级互联网络。 四元胖树如图所示，试问：每个内节点有几个子节点和几个父节点你知道那个机器使用了此种形式的胖树 答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么 答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4 B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6 一个N=2^k个节点的 de Bruijin 。 。。。试问：该网络的直径和对剖宽度是多少 答：N=2^k个节点的 de Bruijin网络直径d=k 对剖宽带w=2^(k-1) 一个N=2^n个节点的洗牌交换网络如图所示。试问：此网络节点度==网络直径==网络对剖宽度== 答：N=2^n个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4 一个N=（k+1）2^k个节点的蝶形网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度= 答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围） 答： 如图所示，信包的片0，1，2，3要分别去向目的地A，B，C，D。此时片0占据信道CB，片1占据信道DC，片2占据信道AD，片3占据信道BA。试问： 1）这将会发生什么现象 2）如果采用X-Y选路策略，可避免上述现象吗为什么 答： 1）通路中形成环，发生死锁 计算机学院研究生《并行计算》课程 考试试题 （2010级研究生，2011.1） 1．（12分）定义图中节点u 和v 之间的距离为从u 到v 最短路径的长度。已知一个d 维的超立方体，1）指定其中的一个源节点s ，问有多少个节点与s 的距离为i ，其中0≤i ≤d 。证明你的结论。2）证明如果在一个超立方体中节点u 与节点v 的距离为i ，则存在i ！条从u 到v 的长度为i 的路径。 1)有i d C 个节点与s 的距离为i 。 证明：由超立方体的性质知： 一个d 维的超立方体的每个节点都可由d 位二进制来表示，则与某个节 点的距离为i 的节点必定在这d 位二进制中有i 位与之不同，那么随机从d 位中选择i 位就有i d C 种选择方式，即与s 的距离为i 得节点就有i d C 个。 2) 证明：由1）所述可知： 节点u 与节点v 的距离为i 则分别表示u 、v 节点的二进制位数中有i 位是不同的。设节点u 表示为：121D .........j j i j i d D D D D D +-+，节点v 表示为： ''121D .........j j i j i d D D D D D +-+，则现在就是要求得从 121D .........j j i j i d D D D D D +-+变换到''121D .........j j i j i d D D D D D +-+ 的途径有多 少种。那么利用组合理论知识可知共有*(1)*(2)*...*2*1i i i --即!i 中途径。所以存在i ！条从u 到v 的长度为i 的路径。 2．（18分）6个并行程序的执行时间，用I-VI 表示，在1-8个处理器上执行了测试。下表表示了各程序达到的加速比。 并行计算期末试题 适用专业：理工类 考试说明： 1、将试卷答案以学号命名为word文件，如115042101.doc，上传到 ftp://172.17.124.203/upload。 2、第一、二大题，直接将答案写在题后；第三、四题要求将程序补充、编写完 整并将运行结果截图插在题目后面。 一、简述题（每小题4分，共20分）。 1、简述openmp编译制导指令master,single,critical,atomic的功能。 1.master制导语句指定代码段只能被主线程执行 2.single编译制导语句指定内部代码只能由线程组中的一个线程执行。线程组中没有执行single语句的线程会一直等待代码块的结束，使用nowait子句除外。 3.critical制导语句表明域中的代码一次只能由一个线程执行，其他线程被阻塞在临界区 4.atomic制导语句指定特定的存储单元将被原子更新 2、简述openmp编译制导子句shared,private的功能？简述openmp编译制导指令threadprivate的功能。 1.private子句表示它列出的变量对于每个线程是局部的。 2.shared子句表示它所列出的变量被线程组中所有的线程共享，所有线程都能对它进行读写访问。 3.threadprivate语句使一个全局文件作用域的变量在并行域内变成每个线程私有，每个线程对该变量复制一份私有拷贝并在多个并行域中保持。 3、简述openmp函数omp_set_num_threads，omp_get_num_threads， omp_get_thread_num的功能；环境变量OMP_NUM_THREADS的功能。 omp_set_num_threads 高性能计算和网格技术 实验报告 实验题目OpenMP和MPI编程姓名 学号 专业计算机系统结构 指导教师 助教 所在学院计算机科学与工程学院论文提交日期 一、实验目的 本实验的目的是通过练习掌握OpenMP 和MPI 并行编程的知识和技巧。 1、熟悉OpenMP 和MPI 编程环境和工具的使用； 2、掌握并行程序编写的基本步骤； 3、了解并行程序调试和调优的技巧。 二、实验要求 1、独立完成实验内容； 2、了解并行算法的设计基础； 3、熟悉OpenMP和MPI的编程环境以及运行环境； 4、理解不同线程数，进程数对于加速比的影响。 三、实验内容 3.1、矩阵LU分解算法的设计： 参考文档sy6.doc所使用的并行算法： 在LU分解的过程中，主要的计算是利用主行i对其余各行j，(j>i)作初等行变换，各行计算之间没有数据相关关系，因此可以对矩阵A 按行划分来实现并行计算。考虑到在计算过程中处理器之间的负载均衡，对A采用行交叉划分：设处理器个数为p，矩阵A的阶数为n，??p =，对矩阵A行交叉划分后，编号为i(i=0,1,…,p-1)的处理器存有m/ n A的第i, i+p,…, i+(m-1)p行。然后依次以第0,1,…,n-1行作为主行，将 其广播给所有处理器，各处理器利用主行对其部分行向量做行变换，这实际上是各处理器轮流选出主行并广播。若以编号为my_rank的处理器的第i行元素作为主行，并将它广播给所有处理器，则编号大于等于my_rank的处理器利用主行元素对其第i+1,…,m-1行数据做行变换，其它处理器利用主行元素对其第i,…,m-1行数据做行变换。 根据上述算法原理用代码表示如下（关键代码）： for(k = 0;k显式有限元和隐式有限元
计算机体系结构 习题与答案
ANSYS高性能并行计算
并行计算(陈国良版)课后答案
并行计算试题及复习资料
并行计算期末试题-理工
并行计算实验报告(高性能计算与网格技术)