作业4
1. 并行程序有哪些设计模型,试分析比较其主要模型特点。
- 隐式并行模型
隐式并行(Implicit Parallelisn)是相对显式并行(Explicit Parallelism)而言的,后者是指程序的并行性由程序员利用专门的语言结构、编译制导或库函数调用等在源代码中给予明显的指定;前者,程序员未明确地指定并行性,而让编译器和运行(时)支持系统自动地开拓它,本节先讨论隐式并行程序设计模型;而显式并行程序设计模型,包括数据并行。
- 数据并行模型
数据并行(Data Parallel)模型既可以在SIMD计算机上实现,也可以在SPMD计算机上实现,这取决于粒度大小。SIMD程序着重开发指令级细粒度的并行性。SPMD程序着重开发子程序级中粒度的并行性。数据并行程序设计强调的是局部计算和数据选路操作,它比较适合于使用规则网络、模板和多维信号/图像数据集来求解细粒度的应用问题。数据并行操作的同步是在编译时而不是在运行时完成的。硬件同步则是通过控制器执行SIMD程序的锁步操作来完成的。在同步的SIMD程序中,所有PE间的通信则直接由硬件控制,除所有PE间操作需锁步外,PE间的数据通信也是以锁步方式进行的。这些同步指令的执行和数据选路操作使得SIMD计算机在开发大型数组,大型网格或网状数据的空间并行性时相当有效。
- 消息传递模型
在消息传递(Message Passing)模型中,驻留在不同处理器节点上的进程可以通过网络传递消息相互通信。消息可以是指令、数据、同步信号或中断信号等。在消息传递并行程序中,用户必须明确地为进程分配数据和负载,它比较适合于开发大粒度的并行性,这些程序是多线程的和异步的,要求显式同步(如路障等)以确保正确地执行顺序。然而这些进程均有其分离的地址空间。消息传递模型比数据并行模型灵活,两种广泛使用的标准库PVM和 MPI使消息传递程序大大增强了可移植性。消息传递程序不仅可执行在共享变量的多处理机上,而且可执行在分布存储的多计算机上。
- 共享变量模型
在共享变量(Shared-Variable)模型中,驻留在各处理器上的进程可以通过读写公共存储器中的共享变量相互通信。它与数据并行模型的相似之处在于它有一个单一的全局名字空间,它与消息传递模型的相似之处在于它是多线程的和异步的。然而数据是驻留在单一共享地址空间中,因此不需要显式分配数据,而工作负载既可显式也可隐式分配。通信通过共享的读写变量隐式完成,而同步必须是显式的,以保持进程执行的正确顺序。
2. 详细描述并行度与并行粒度的相互关系,并简要分析其对并行计算性能在影响。
- 并行度是一个指标,表示一台计算机可以或正在同时执行多少个操作。它对于描述并行程序和多处理器系统的性能特别有用。一个在并行计算机上运行的程序可能在不同时间利用不同数量的处理器。对于每个时间段,用于执行程序的处理器数量被定义为并行程度。对于一个给定的程序,并行度与时间的函数关系图被称为并行度曲线。
- 并行粒度(或粒度大小)是对该任务执行的工作量(或计算量)的度量。粒度的另一个定义考虑了多个处理器或处理元素之间的通信开销。它将粒度定义为计算时间与通信时间的比率,其中,计算时间是执行任务计算所需的时间,通信时间是处理器之间交换数据所需的时间。粒度通常以特定任务中执行的指令数来衡量。或者,也可以根据程序的执行时间来指定粒度,结合计算时间和通信时间。
- 粒度会影响并行计算机的性能。使用细粒度或小任务会产生更多的并行性,从而提高速度。但是,同步开销、调度策略等会对细粒度任务的性能产生负面影响。单独增加并行度并不能提供最佳性能。为了减少通信开销,可以增加粒度。粗粒度任务具有较少的通信开销,但它们通常会导致负载不平衡。因此,在细粒度和粗粒度并行性这两个极端之间实现了最佳性能。各种研究已经提出了他们的解决方案,以帮助确定最佳粒度以帮助并行处理。寻找最佳晶粒尺寸取决于许多因素,并且因问题而异。
3. 列举MPI主要的基本函数,描述每个函数的作用与使用。
- MPI启动:MPI程序通过调用
MPI_Init
函数进入MPI环境,并完成所有的初始化工作,这个函数通常是MPI程序的第一个函数调用。其格式如下:int MPI Init(int * argc, char ** *argv)
- MPI结束:MPI程序通过调用
MPI_Finalize
函数从MPI环境中退出,它是MPI程序的最后一个 MPI函数调用,否则程序的执行结果是不可预知的。其格式如下:int MPI_Finalize(void)
- 获取进程编号:MPI程序通过
MPI_Comm_rank
函数调用获取当前进程在指定通信域中的编号,有了该编号,不同的进程就可以将自身和其他进程区分开来,从而实现进程间的并行和合作。其格式如下:int MPI_Comm_rank(MPI_Comm comm, int * rank)
- 获取进程数:MPI程序通过调用
MPI_Comm_size
函数获取指定通信域的进程个数,进程可根据它来确定自己应该完成的任务比例。其格式如下:int MPI_Comm_size(MPI_Comm comm, int * size)
- 消息发送:
MPI_Send
函数用于发送一个消息到目标进程。其格式如下:int MPI_Send (void * buf, int count, MPI_Datatype dataytpe, int dest, int tag, MPI_Commcomm)
该函数将起始地址为
buf
的count
个datatype
类型的数据发送给目标进程,目标进程在通信域comm
中的编号由dest
标识。同时,发送方在发送该消息时给它加上一个标签tag
,用于把本次发送的消息和本进程发送给同一目标进程的其他消息区分出来。
- 消息接收:
MPI_Recv
函数用于从指定进程接收一个消息。其格式如下:int MPI_Recv (void * buf, int count,MPI_Datatype datatyepe, int source, int tag, MPI_Comm comm, MPI_Status * status)
该函数从源进程接收一个消息,并且该消息的标签应该和参数
tag
一致,源进程在通信域comm
中的编号由source
标识。消息接收后存放在起始地址为buf
的接收缓冲区,该缓冲区由count
个datatype
类型的连续数据元素组成。接收到的消息长度必须小于或等于接收缓冲区的长度,因为如果接收到的消息过大,MPI
并不截断,从而导致缓冲区溢出。
4. 分析下列代码段中通信域的功能与作用:
//Process 0:
MPI_Send(msg1, count1, MPI_INT, 1, tag1, comm1);
parallel_fft(...);
//Process 1:
MPI_Recv(msg1, count1, MPI_INT, 0, tag1, comm1);
parallel_fft(...);
- 说明代码段中通信域的计算功能;
- 如果在
parallel_fft(...)
中又包含另一个发送程序:分析此时通信域的作用。if (my_rank==0) MPI_Send(msg2, count1, MPI_INT, 1, tag1, comm2);
① 不可能保证
tag1
和tag2
一定取了不同的值: 标签是由用户定义的整数值,用户可能会出错。即使用户不会弄错,也难以或不可能保证
tag1
和tag2
有不同的值。函数parallel_fft()
可能是由其它用户写的,或者它是一个库例程。这样,用户可能不知道tag2
的值。即使用户总能知道
tag2
的值,仍然可能出错。因为MPI_Recv
例程可能决定使用一个通配的(wildcard)
标签MPI_Any_tag
。② 在
parallel_fft()
中的通信使用不同的通信子,它可能包含相同的进程组(如, 进程0
和1
),但每个通信子有系统指定的不同的上下文,与comm1
的不同。因此,MPI_Recv
不再有偶然会从parallel_fft()
的MPI_Send
中接收msg2
的危险了。
作业3
1. 列举主要的并行计算模型,详细描述它们的主要设计思想,并就其主要模型特点加以分析比较。
PRAM模型 PRAM(Parallel Random Access Machine)模型,即并行随机存取机器,也称之为共享存储的SIMD模型,是一种抽象的并行计算模型。在这种模型中,假定存在着一个容量无限大的共享存储器;有有限或无限个功能相同的处理器,且其均具有简单的算术运算和逻辑判断功能;在任何时刻各处理器均可通过共享存储单元相互交换数据。
异步PRAM模型 分相PRAM(Phase PRAM)模型是一个异步的PRAM模型,简记之为 APRAM,系由卜个处理器组成,其特点是每个处理器都有其局存,局部时钟和局部程序;处理器间的通信经过共享全局存储器;无全局时钟,各处理器异步地独立执行各自的指令;处理器任何时间依赖关系需明确地在各处理器的程序中加入同步(路)障(Synchronization Barrier);一条指令可在非确定(无界)但有限的时间内完成。
BSP模型 BSP( Bulk Synchronous Parallel)模型,字面的含义是“大”同步模型(相应地,APRAM模型也称作“轻量”同步模型),早期最简单的版本称为XPRAM模型,它是计算机语言和体系结构之间的桥梁,并以下述3个参数来描述分布存储的多计算机模型:①处理器/存储器模块(下文也简称为处理器),②施行处理器/存储器模块对之间点到点传递消息的选路器,③执行以时间间隔L为周期的所谓路障同步器。所以BSP模型将并行机的特性抽象为3个定量参数p、g、L,分别对应于处理器数、选路器吞吐率(亦称带宽因子)、全局同步之间的时间间隔。
LogP模型 LogP模型(LogP Model)是一种分布存储的、点到点通信的多处理机模型,其中通信网络由一组参数来描述,但它并不涉及具体的网络结构,也不假定算法一定要用显式的消息传递操作进行描述。很凑巧,LogP恰好是以下几个定量参数的拼写组合:①L(Latency)表示在网络中消息从源到目的地所产生的延迟;o(Over-head)表示处理器发送或接收-条消息所需的额外开销(包含操作系统核心开销和网络软件开销),在此期间内它不能进行其他操作;3 g(Gap)表示处理器可连续进行消息发送或接收的最小时间间隔;④p(Processor)表示处理器/存储器模块数。很显然,g的倒数相应于处理器的通信带宽;而L和g反映了通信网络的容量。L,o和g都可以表示成处理器周期(假定一个周期完成一次局部操作,并定义为一个时间单位)的整倍数。
比较
模型/属性 PRAM APRAM BSP LogP 体系结构 SlMD-SM MIMD-SM MIMD-DM MIMD-DM 计算模式 同步计算 异步计算 异步计算 异步计算 同步方式 自动同步 路障同步 路障同步 隐式同步 模型参数 1
(单位时间步)d,B
d:读/写时间
B:同步时间p,g,L
p:处理器数
g:带宽因子
L:同步间隔L,o,g,p
L:通信延迟
o:额外开销
g:带宽因子
p:处理器数计算粒度 细粒度/中粒度 中粒度/大粒度 中粒度/大粒度 中粒度/大粒度 通信方式 读/写共享变量 读/写共享变量 发送/接收消息 发送/接收消息 编程地址空间 全局地址空间 单一地址空间 单地址/多地址空间 单地址/多地址空间
2. 并行算法的常用设计技术有哪些?它们的基本思想是什么?
- 划分设计技术
- 1.1 均匀划分技术
n个元素A[1..n]分成p组,每组A[(i-1)n/p+1..in/p],i=1~p
- 1.2 方根划分技术
n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)],i=1~n^(1/2)
- 1.3对数划分技术
n个元素A[1..n]分成A[(i-1)logn+1..ilogn],i=1~n/logn
- 1.4功能划分技术
n个元素A[1..n]分成等长的p组,每组满足某种特性。
- 分治设计技术
将输入划分成若干个规模相等的子问题;同时(并行地)递归求解这些子问题;并行地归并子问题的解,直至得到原问题的解。
- 平衡树设计技术
以树的叶结点为输入,中间结点为处理结点,由叶向根或由根向叶逐层进行并行处理。
- 倍增设计技术
又称指针跳跃(pointerjumping)技术,特别适合于处理链表或有向树之类的数据结构;当递归调用时,所要处理数据之间的距离逐步加倍,经过k步后即可完成距离为2k的所有数据的计算。
- 流水线设计技术
将算法流程划分成p个前后衔接的任务片断,每个任务片断的输出作为下一个任务片断的输入;所有任务片断按同样的速率产生出结果。
3. 什么是PCAM设计方法学,它包括哪些内容?解释每个阶段的功能含义和应完成的任务内容?
PCAM是Partitioning(划分)、Communication(通信)、Agglomeration(组合)和Mapping(映射)的缩写,它们表示了使用此法设计并行算法的四个阶段:任务划分、通信分析、任务组合和处理器映射,简称划分、通信、组合、映射。PCAM是一种设计方法学,是实际设计并行算法的自然过程。PCAM设计方法的思想是:先尽量开拓算法的并发性和满足算法的可扩展性,然后着重优化算法的通信成本和全局执行时间。具体来说,在任务划分和通信分析阶段主要考虑算法的并发性和可扩展性等与机器无关的特性。在任务组合和处理器映射阶段主要考虑局部性和其它与性能有关的问题。各阶段的任务如下:
划分:将整个计算任务分解成一些小任务,其目的是尽量开拓并行执行的可能性;
通信:确定小任务执行中需要进行的通信,为组合做准备;
组合:按性能要求和实现的代价来考察前两阶段的结果,适当地将一些小任务组合成更大的任务以提高性能、减少通信开销;
映射:将组合后的任务分配到处理器上,其目标是使全局执行时间和通信开销尽量小,使处理器的利用率尽量高。
4. 两个非降有序序列:A=(0,1,2,7,9,11,16,17,18,19,23,24,25,27,28,30,33,34),B=(3,4,5,6,8,10,12,13,14,15,20,21,22,26,29,31)。按算法7.3即PRAM上对数划分算法,将其进行对数划分,并最终将它们归并之。
=> logm = log16 = 4 => j[1] = rank(blogm:A) = rank(b4:A) = rank(6:A) = 3, j[2] = … = 18 B0: 3,4,5,6 B1: 8,10,12,13,14,15,20,21,22,26,29,31
A0: 0,1,2 A1: 7,9,11,16,17,18,19,23,24,25,27,28,30,33,34 A和B归并化为(A0, B0)和(A1, B1)的归并
作业2
1. 分别构造顶点数为N=64的超立方网络和4-立方环网络,并对其节点度、网络直径和对剖宽度进行比较。
节点度 网络直径 对剖宽度 N=64的超立方网络 6 6 32 4-立方环网络 4 9 8
2. 什么是并行计算机系统中的多处理机Cache一致性问题?试分析说明有哪些原因导致这个问题?
并行计算机系统在缓存方面有困难,因为它可能在多个位置存储相同的值,有可能导致程序执行不正确。这些计算机需要一个缓存一致性系统,它可以跟踪缓存值并有策略地清除它们,从而确保程序的正确执行。
总线窥探是跟踪哪些值正在被访问(因此应该被清除)的最常用方法之一。
设计大型、高性能的高速缓存一致性系统是计算机结构中一个非常困难的问题。因此,共享内存计算机架构的扩展性不如分布式内存系统好。
3. 基于并行计算体系结构的基本模型,分析比较云计算系统与大数据计算模型系统的结构特征和应用特点。
序号 大数据 云计算 01 大数据是指规模巨大且随时间快速增长的数据。 云计算是指通过互联网按需提供计算资源。 02 大数据包括结构化数据、非结构化数据以及半结构化数据。 云计算服务包括基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)。 03 数据量、数据的速度、数据的多样性、数据的真实性和数据的价值被认为是大数据的5个最重要特征。 IT资源的按需供应、广泛的网络访问、资源池、弹性和计量服务被认为是云计算的主要特征。 04 大数据的目的是组织大量的数据,从中提取有用的信息,并利用这些信息来改善业务。 云计算的目的是在云中存储和处理数据,或利用远程IT服务,而无需实际安装任何IT资源。 05 分布式计算被用于分析数据和提取有用的信息。 互联网被用来从不同的云供应商那里获得基于云的服务。 06 大数据管理允许集中的平台,提供备份和恢复,维护成本低。 云计算服务具有成本效益、可扩展性和稳健性。 07 大数据的一些挑战是数据的多样性、数据存储和整合、数据处理和资源管理。 云计算的一些挑战是可用性、转型、安全问题、收费模式。 08 大数据指的是巨大的数据量,其管理和有用的信息提取。 云计算指的是远程IT资源和不同的互联网服务模式。 09 大数据被用来描述巨大的数据和信息量。 云计算用于在远程服务器上存储数据和信息,同时利用远程基础设施处理数据。 10 一些产生大数据的来源包括社交媒体数据、电子商务数据、气象站数据、物联网传感器数据等。 一些提供云计算服务的云计算供应商有亚马逊网络服务(AWS)、微软Azure、谷歌云平台、IBM云服务等。 来源: Difference between Big Data and Cloud Computing - GeeksforGeeks.
作业1
1. 比较PVP、SMP、MPP、DSM、COW和Constellation几种并行计算机体系结构模型的特点。
PVP: 并行向量处理机。系统中包含了少量的高性能专门设计定制的向量处理器VP(Vector Processor),每个至少具有1G flops的处理能力。系统中使用了专门设计的高带宽的交叉开关网络向VP连向共享存储模块,存储器可以M/s字节的速度向处理器提供数据。这样的机器通常不使用高速缓存,而是使用大量的向量寄存器和指令缓冲器。
SMP: 对称多处理机。SMP系统使用商品微处理器(具有片上或外置高速缓存),他们经由高速总线(或交叉开关)连向共享存储器。这种机器主要应用于商务,例如数据库、在线事务处理系统和数据仓库等。重要的是系统是对称的,每个处理器可等同地方问共享存储,限制系统中的处理器不能太多(一般小于64个),同时总线和交叉开关互连一旦做成也难于扩展。
MPP:大规模并行处理机。MMP一般是指超大型(Very Large-Scale)计算机系统,他具有如下特征: ①处理结点采用商用微处理器; ②系统中有物理上的分布式存储器;③采用高通信带宽和低延迟的互联网络(专门设计和定制的); ④能扩放至成百上千乃至上万个处理器;⑤它是一种异步的MIMD机器,程序系由多个进程组成,每个都有其私有地址空间,进程间采用传递消息相互作用。MMP的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。
DSM:分布式共享存储。高速缓存目录DIR用以支持分布高速缓存的一致性。DSM和SMP的主要差别是,DSM在物理上有分布在各个节点中的局存,从而形成了一个共享的存储器。对用户而言,系统硬件和软件提供了一个单地址的编程空间。DSM相对于MPP的优越性是编程较容易。
COW:工作站机群。COW的重要界限和特征是:①COW的每一个节点都是一个完整的工作站(不包括监视器、键盘、鼠标等),这样的节点有时叫做“无头工作站”,一个节点也可以是一台PC或SMP;②各节点通过一种低成本的商品(标准)网络(如以太网、FDDI和ATM开关等)互连(有的商用机群也使用定做的网络);③各节点内总是有本地磁盘,而MPP节点内却没有;④节点内的网络接口是松散耦合到I/O总线上的,而MPP内的网络接口是连到处理节点的存储总线上的,因而可谓是紧耦合式的;⑤一个完整的操作系统驻留在每个节点中,而MPP中通常只有一个微核,COW的操作系统是工作站UNIX,加上一个附加的软件层,以支持单一系统映像、并行度、通信和负载平衡等。现今,MPP和COW之间的界限越来越模糊。机群相对于MPP有性能/价格比高的优势,所以在发展可扩放并行计算机方面呼声很高。
Constellation:星群。有三个明显的特征:系统由结点构成,每个结点是一台共享存储或者分布共享存储的并行机子系统,包含数十、数百、乃至上千个微处理器,计算功能强大;采用商用机群交换机连接结点,结点间分布存储;在各个结点上,运行专用的结点操作系统、编译系统和作业管理系统。
2. 比较UMA、NUMA、COMA、CC-NUMA、NCC-NUMA和NORMA几种存储访问结构模型的特点。
UMA是Uniform Memory Access(均匀存储访问)模型的缩写。在这种并行机中所有的处理器均匀共享物理存储器。所有处理器访问任何存储字需要相同的时间(此即为均匀存储访问名称的来源)。每台处理器可以有私有高速缓存。
NUMA是Non-Uniform Memory Access(非均匀存储访问)模型的缩写。在NUMA中,共享存储器在物理上是分布的,所有的本地存储器构成了全局地址空间。NUMA与UMA的区别在于处理器访问本地存储器和群内共享存储器比访问远程存储器或全局共享存储器快(此即非均匀存储访问名称的由来)。
COMA是Cache-Only Memory Architecture(全高速缓存存储结构)模型的缩写。COMA实际是NUMA的一种特例,将NUMA中的分布存储器换成高速缓存就得到了COMA。在COMA中,每个结点上没有存储层次结构,所有的高速缓存构成了全局地址空间。访问远程高速缓存要借助分布的高速缓存目录。
CC-NUMA是Cache-Coherent Non-Uniform Memory Access(高速缓存一致性非均匀存储访问)模型的缩写。CC-NUMA结构的并行机实际上是将一些SMP机作为结点互连起来而构成的并行机。这样可以改善SMP机的可扩展性。绝大多数商用CC-NUMA多处理机系统使用基于目录的高速缓存一致性协议;它的存储器在物理上是分布的,所有的局部存储器构成了共享的全局地址空间(所以它实际上是一个DSM系统),因此它保留了SMP易于编程的优点。它最显著的优点是程序员无需明确地在结点上分配数据,系统的硬件和软件开始时自动在各结点分配数据。在程序运行过程中,高速缓存一致性硬件会自动地将数据移至需要它的地方。CC-NUMA注重开拓数据的局部性和增强系统的可扩展性。在实际应用中,大多数的数据访问都可在本结点内完成,网络上传输的主要是高速缓存无效性信息而不是数据。CC-NUMA和COMA的共同特点是它们都对高速缓存一致性提供硬件支持。
NCC-NUMA(Non-Cache Coherent Non-Uniform Memory Access)相较于CC-NUMA,没有对高速缓存的一致性提供硬件支持。
NORMA是No-Remote Memory Access(非远程存储访问)模型的缩写。在NORMA中,所有的存储器都是处理器私有的,仅能由其处理器访问。各处理器之间通过消息传递方式通信。MPP多采用这种结构。
作业0
1. 简述本课程主要内容,结合自我认识,说明其在本学科知识体系中的地位和作用。
- 本课程主要内容
并行计算一般是指许多指令得以同时进行的计算模式。在同时进行的前提下,可以将计算的过程分解成小部分,之后以并发方式来加以解决。电脑软件可以被分成数个运算步骤来执行。为了解决某个特定问题,软件采用某个算法,以一连串指令执行来完成。传统上,这些指令都被送至单一的中央处理器,以循序方式执行完成。在这种处理方式下,单一时间中,只有单一指令被执行。并行运算采用了多个运算单元,同时执行,以解决问题。
- 在本学科知识体系中的地位和作用
并发性是在计算机科学中,同一个系统拥有多个计算进程,这些进程有同时执行与的潜在交互特性,因此系统会有相当多个执行路径且结果可能具有不确定性。并发计算可能会在具备多核心的同一个芯片中交错运行,以优先分时线程在同一个处理器中执行,或在不同的处理器执行。一些数理模型已经为解决一般的并发计算问题而发展,包括Petri网、进程、PRAM模型和演员模型。
2. 如何理解并行计算的性能指标?网调高性能计算机最新排名国际TOP10和国内TOP10,并就其中主要性能评测指标进行解释。
- 基本指标
- 执行时间
- 工作负载
- 访问性能
- 加速比评测:
- Amdahl定理
- Gustafson定理
- Sun-Ni定理
- 可扩放性标准
- 等效率标准
- 等速度标准
- 平均延迟标准
- 高性能计算机国际最新排名TOP10
- 高性能计算机国内最新排名TOP10