*sum+=array[i];
returnNULL;
}
19.Giveagoodoptiontocomputeforloadbalancing.(n=16andthereare4processors)
20.Pleaselistthewaysforimprovingperformance.
Option#1:
BuyFasterHardware
Option#2:
Modifythealgorithm
Option#3:
Modifythedatastructures
Option#4:
Modifytheimplementation
Option#5:
Useconcurrency
21、Ifacodeis10%sequential,andthereare4processors,pleasecalculatethespeedup.
F=10%
T1=0.1T1+0.9T1
T4=0.1T1+0.9T1/4=0.325T1
Speedup=T1/T4=3.077
22.Pleaseshowtheprocessofn-pipelinedexecutionof4taskstoachievehigherthroughput(i.e.numberoftaskspertimeunit)ifeachtaskhas4sequentialstageswhichtake1,2,5,1timeunitrespectively.
time=1+2+5*4+1=24
23.128个双路2.66GHzIntelNehalem四核处理器计算节点的HPC集群,其峰值计算是多少
128*2*2.66G*4*4(一个时钟周期可进行4次浮点运算)=10,895GFlops
24.并行计算提出的原因
提高性能和存储能力;使用户和计算机之间相互协调;获得一个问题的逻辑结构;处理独立的物理设备
25.并行的三大问题:
性能,准确性,可编程性Programmability
RISC:
ReducedInstructionSetComputing
CISC:
ComplexInstructionSetComputer
MIPS:
MillionInstructionsPerSecond
ILP:
InstructionLevelParallelism指令层并行.
SMT:
SimultaneousMultiThreading同时多线程
SMP:
SymmetricMulti-Processors
SISD:
Singleinstructionsingledata
SIMD:
Singleinstructionmultipledata单指令流多数据流
MIMD:
Multipleinstructionsmultipledata
MISD:
Multipleinstructionssingledata
MPP:
MassivelyParallelProcessor大规模并行处理器
26.在一个CPU中可通过几种技术实现并发机制
流水线:
Pipelining,RISC体系结构
如果一个处理器要处理若干个任务,且每个任务有相同的n个步骤组成,不同部分又可同时执行,则处理器可采取流水线方式处理这些任务。
流水线的任务是获得高的吞吐量。
当任务数很多时,系统吞吐量接近于1/最大子任务持续时间
RISC的思想是:
使所有指令由相同数量的持续时间相同的步骤。
MPI:
MassagePassingInterface是消息传递函数库的标准规范.
GPU:
GraphicProcessingUnit图形处理器
27.Parallelcomputing:
单一系统,众核处理同一任务。
时间上的并行就是指流水线技术,而空间上的并行则是指用多个处理器并发的执行计算。
28.并行计算优势:
处理器总体性能更强;总体内存更大。
29.HPC集群峰值计算能力
一套配置256个双路X5560处理器计算节点的HPC集群X5560:
2.8GHzIntelX5560Nehalem四核处理器
目前主流的处理器每时钟周期提供4个双精度浮点计算峰值计算性能:
2.8GHz*4Flops/Hz*4Core*2CPU*256节点=22937.6GFlops
Gflops=10亿次,所以22937Gflops=22.937TFlops=22.937万亿次每秒的峰值性能
CUDA:
ComputeUnifiedDeviceArchitecture通用并行计算架构,显卡厂商推出的运算平台。
30.ParallelSpeedup
评价一个并行算法的性能的重要参数是:
并行加速度。
Speedup(p)=T1/Tp
每个并行程序都有串行部分和并行部分:
T1=fT1+(1-f)T1;Tp=fT1+(1-f)T1/p
因此:
Speedup(p)=1/(f+(1-f)/p)
=p/(fp+1-f)≦1/f
31.并行效率ParallelEfficiency:
Effp=Sp/p
32.负载均衡LoadBalancingPleaseshowtheidealprocessforcomputingSUM(f
(1)+f
(2)+…+f(8))ifweassumethatthereare3processorsandconsiderloadbalancing.
一种可能:
Processor0:
F1
F4
F7
147
Processor1:
F2
F5
F8
368
Processor2:
F3
F6
36
14
25
147368
12345678
负载均衡:
平衡所有处理器之间的计算量。
α:
计算f(n)所花时间,β:
两数相加所花时间。
设计并行程序:
(目标是使并行加速度达到最大)
(1)分解任务,确定可并行执行的部分,将大任务分解成多个可并行执行的小任务。
尽量使所有处理器都有任务处理,但是也要避免太多太小的任务。
(2)分配任务,将每个任务分配到线程中。
尽量保证负载均衡。
(3)指挥控制,主要是管理数据和协调多个线程之间的通信。
尽量保证线程执行的正确性,减少串行化部分和同步开销。
(4)映射,将线程映射到处理器上执行。
e.g.:
s=f(A[1])+…+f(A[n])
(1)Decomposition
computingeachf(A[j])
n-foldparallelism,wherenmaybe>>p
computingsums
(2)Assignment
threadksumssk=f(A[k*n/p])+…+f(A[(k+1)*n/p-1])
thread1sumss=s1+…+sp(forsimplicityofthisexample)
thread1communicatesstootherthreads
(3)Orchestration
startingupthreads
communicating,synchronizingwiththread1
(4)Mapping
processorjrunsthreadj
MFlops:
Millionsoffloatingpointoperations/sec
POSIX:
PortableOperatingSystemInterfaceofUnix可移植操作系统接口
33.Thread线程:
可作为独立单元被调度的一连串代码。
(process进程)
34.编写多线程代码时要注意的问题
(1)负载均衡
(2)正确的存取共享变量(通过互斥代码或互斥锁实现)
35.
用户级线程:
多对一映射。
不需要系统支持,操作开销小。
一个线程阻塞时其他线程也要阻塞。
内核级线程:
一对一映射。
每个内核线程调度相互独立,OS完成线程的操作。
在一个处理器上每个内核线程可并行执行,一个线程阻塞时其他线程也可以被调度。
线程调度开销大,OS要适应线程数目的变化。
36.多线程
pthread_t:
thetypeofathread
pthread_create():
createsathread
pthread_mutex_t:
thetypeofamutexlock
pthread_mutex_lock():
lockamutex
pthread_self():
Returnsthethreadidentifierforthecallingthread
intpthread_create(pthread_t*thread,pthread_attr_t*attr,
void*(*start_routine)(void*),void*arg);
(1)计算数组元素之和
structarguments
{
double*array;
intsize;
double*sum;
}
intmain(intargc,char*argv)
{
doublearray[100];
doublesum;
pthread_tworker_thread;
structarguments*arg;
arg=(structarguments*)calloc(1,sizeof(structarguments));
arg->array=array;
arg->size=100;
arg->sum=∑
if(pthread_create(&worker_thread,NULL,do_work,(void*)arg))
{
fprintf(stderr,”Errorwhilecreatingthread\n”);
exit
(1);
}
...
}
void*do_work(void*arg){
structarguments*argument;
inti,size;
double*array;
double*sum;
argument=(structarguments*)arg;
size=argument->size;
array=argument->array;
sum=argument->sum;
*sum=0;
for(i=0;i*sum+=array[i];
returnNULL;
}
voidpthread_exit(void*retval);
intpthread_join(pthread_tthread,void**value_ptr);用来等待一个线程的结束,这个函数是一个线程阻塞的函数,调用它的函数将一直等待到被等待的线程结束为止,当函数返回时,被等待线程的资源被收回。
intpthread_kill(pthread_tthread,intsig);
(2)
intmain(intargc,char*argv){
doublearray[100];
doublesum;
pthread_tworker_thread;
structarguments*arg;
void*return_value;
arg=(structarguments*)calloc(1,sizeof(structarguments));
arg->array=array;
arg->size=100;
arg->sum=∑
if(pthread_create(&worker_thread,NULL,do_work,(void*)arg)){
fprintf(stderr,”Errorwhilecreatingthread\n”);
exit
(1);
}
...
if(pthread_join(worker_thread,&return_value)){
fprintf(stderr,”Errorwhilewaitingforthread\n”);
exit
(1);
}
}
RDMA,RemoteDirectMemoryAccess,远程直接存储器存储,通过•Zero-copy和•Kernelbypass技术实现。
37.InfiniBand的最低通讯延迟是多少?
高吞吐率(40Gb/s点对点和120Gb/s连接;消息传递接近90M/s;发送接收和RDMA操作通过0复制),低延迟(1~1.3usecMPI端对端;RDMA操作0.9~1usInfiniband延迟)
38.计算科学与理论科学和实验科学是人类认识自然的三大支柱。
39..应用领域:
美国HPCC计划,包括:
磁记录技术、新药设计、高速民航、催化作用、燃料燃烧、海洋建模、臭氧损耗、数字解析、大气污染、蛋白质结构设计、图像理解、密码破译。
40.HPC衡量单位:
十亿次Gflop/s,万亿次Tflop/s,千万亿次Pflop/s。
41.Linpack是国际上最流行的用于测试高性能计算机系统浮点性能的benchmark。
通过对高性能计算机采用高斯消元法求解一元N次稠密线性代数方程组的测试,评价高性能计算机的浮点性能。
42.共享存储对称多处理机系统(SMP,SharedMemoryProcessor),任意处理器可直接访问任意内存地址,且访问延迟、带宽、几率都是等价的;系统是对称的。
43.Cluster集群:
将多个计算机系统通过网络连接起来如同一个系统一样提供服务,可以获得高并行处理能力、高可用性、负载均衡和管理便捷性。
44.Cluster技术进步的必然:
高性能处理器、高速网络、集群OS和管理系统、并行/分布计算工具以及软件。
45.并行计算Parallelcomputing:
单一系统,众核处理同一任务;分布式计算Distributedcomputing:
将多系统用调度器松散的结合起来,处理相关任务;网格计算GridComputing:
用软件和网络将多系统和多处理器紧耦合,共同处理同一任务或相关任务。
46.并行计算的两大优势:
处理器总体性能更强,总体内存更大。
47.并行式计算的分类:
1)sharedmemory(共享内存),可以分为统一内存访问Uniformmemoryaccess(UMA)即所有处理器访存相同和Non-uniformmemoryaccess(NUMA)访存延迟取决于数据存储位置;2)distributedmemory(分布式内存)。
可分为大规模并行处理器MassivelyParallelProcessor(MPP)和集群Cluster。
48.对称多处理器SMP与全局内存通过总线或交叉开关crossbar互联。
优点编程模型简单,问题总线带宽会饱和,交叉开关规模会随处理器个数增加而增大。
缺点不宜扩展,限制了SMP的规模。
49.集群优势:
通用的高性能、高可用性、高扩展性和高性价比。
50.分布式内存编程模型:
MPI
51.共享内存编程模型:
OpenMP,Pthreads
52.并行粒度:
PVM/MPI、Threads、Compilers、CPU。
53.消息传递是当前并行计算领域的一个非常重要的并行程序设计方式.
54.MPI是一个库,而不是一门语言;MPI是一种消息传递编程模型,是提供一个实际可用的、可移植的、高效的和灵活的消息传递接口标准.
55.消息传送机制:
阻塞方式,必须等到消息从本地送出之后才可以执行后续的语句;非阻塞方式,不须等到消息从本地送出就可以执行后续的语句,并不保证资源的可再用性。
56.并行加速的木桶理论:
一个给定问题中的并行加速比受此问题的串行部分限制。
57..对于并行计算来说,最危险的缺陷就是将一个计算问题变成了一个通信问题:
这种问题一般发生在各个节点为了保持同步而传输数据的时间超过了CPU进行计算的时间,常见网络Infiniband,10GE,GE,Myrinet。
58.GPU,C-G混合架构。
第二次课:
蒋运宏
59.VMM,VirtualMachineMonitor,虚拟机监控程序。
60.VMM的基本特征:
Equivalen