版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
高性能矩阵乘法2024/12/82并行算法优化研究相对于传统面向对象串行算法的4个挑战:同步:两个或者多个线程协调其行为的过程通信:与线程之间交换数据相关的带宽和延迟问题负载均衡:多个线程之间工作量分布的情况,给各个线程(执行核)分配均匀的工作可扩展性:衡量在性能更加强劲的系统上运行软件时能否有效利用更多线程的指标, 观察应用程序在更高级的平台上运行 4核到8核线性增长2024/12/83多线程(核)设计主要分解模式任务分解: 对程序根据其执行的功能进行分解的过程数据分解: 将应用程序根据各任务所处理的数据而非按任务的天然特性来进行分解数据流分解: 研究数据在诸任务之间如何流动,根据任务之间的数据流关系对问题 进行分解模式分解方式任务级并行模式任务分解DivideandConquer任务/数据分解几何分解模式数据分解流水线模式数据流分解波峰(wavefront)模式数据流分解2024/12/84多线程(核)设计主要分解模式任务分解: 对程序根据其执行的功能进行分解的过程数据分解: 将应用程序根据各任务所处理的数据而非按任务的天然特性来进行分解数据流分解: 研究数据在诸任务之间如何流动,根据任务之间的数据流关系对问题 进行分解
分解方式设计说明任务分解不同的程序行为采用不同的线程实现常用于GUI应用程序数据分解多个线程对不同的数据块执行相同的操作常用于音频、图像处理和科学计算应用程序数据流分解一个线程的输出作为另一个线程的输入尤其应注意尽量消除启动和排空延迟2024/12/85矩阵乘法算法探讨
在工程科学计算中,矩阵乘积是最基本的运算 典型的n阶稠密方阵乘积算法的时间复杂度是O(n3)。 目前对大型矩阵乘积运算的处理主要是采用分治思想,将矩阵分布在多个节点上,但每个结点上的小矩阵仍要立方级乘法次数。 基于分之思想的两种划分策略:条形划分和块状(棋盘)划分的6种常见分布式矩阵乘法并行算法。
2024/12/86基于不同划分策略的矩阵乘法算法探讨
1、条形(stripedpartitioning)划分的矩阵乘法并行算法
行条划分 列条划分两两组合:行列、行行、列列、列行2024/12/87基于不同划分策略的矩阵乘法算法探讨
2、块状划分(checkerboardpartitioning)的矩阵乘法并行算法
称为棋盘划分Cannon
DescriptionforimplementationofMPIprogramtocomputeMatrixMatrixMultiplicationusingblockcheckerboardpartitioning
andCannonAlgorithm
2024/12/88Cannon
Objective
Computingthematrix-matrixmultiplicationonSMPSystem.UseblockcheckerboardpartitioningofthematricesandCannon'sAlgorithm.
AssumptionSizeofthesquarematricesp=q2andthesizeofsquarematricesAandBisevenlydivisiblebyq.
Itisassumedthatthenumberofblocksareequaltothenumberofprocessors.2024/12/89Cannon
Cannon'salgorithmisbasedoncartesianvirtualtopologyAandBaresquarematricesofsizenandCbetheoutput
matrix.Thesematricesaredivedintoblocksorsubmatricestoperformmatrix-matrixoperationsinparallelnxnmatrixAcanberegardedasqxqarrayofblocksAi,j(0<=i<q,0<=j<q)suchthateachblockisan(n/q)x(n/q)submatrixWeusep
processorstoimplementtheblockversionofmatrixmultiplicationinparallelbychoosingqasasquarerootof
p
andcomputeadistinctblockCi,joneachprocessor.2024/12/810传统并行
2024/12/811传统并行
ThematricesAandBare
partitionedintop
blocks,A
i,j
andBi,j
(0<=i<q,0<=j<q)ofsize
(n/qxn/q)
oneachprocess.Theseblocksaremappedontoaqxq
logicalmeshofprocesses.TheprocessesarelabeledfromP0,0toPq-1,q-1.2024/12/812传统并行
ProcessPi,jinitiallystoreblockmatricesAi,jandBi,jandcomputesblockCi,jofresultmatrix.TocomputesubmatrixCi,j,weneedallsubmatrices,Ai,kand
Bk,j(0
<=k<q).Toacquirealltherequiredblocks,anall-to-allbroadcastofmatrixAi,j's
isperformedineachrowandsimilarlyineachcolumnofmatrixBi,j's.MPIcollectivecommunicationisusedtoperformthisoperations.2024/12/813传统并行
AfterPi,jacquires,Ai,0,Ai,1,Ai,2
,Ai,q-1andB0,j
,B1,j
,B2,j
,Bq-1,j
,itperformstheserialblockmatrixtomatrixmultiplicationandaccumulatesthepartialblock
matrixCi,jofmatrixC.ToobtaintheresultantproductmatrixC,processeswithrank0gathersalltheblockmatricesbyusingMPI_Gather
collectivecommunicationoperation.2024/12/814Cannon
pprocessorsarrangedinqxqsquaregridofprocessorsandtheinputmatrices.AandBaredistributedamongtheprocessesincheckerboardfashion.ItresultsinconstructingpblockmatricesofAandB.Itusesonlypoint-to-pointcommunication
forcircularlyshiftingblocksofmatrixAandmatrixBamongpprocesses.
2024/12/815Cannon-inital
Thealgorithmproceedsinq
stages.ThefirststepinthisalgorithmistoperforminitialalignmentoftheblockmatrixAandblockmatrixB.TheblocksofmatrixAarecircularlyshiftedtothe
i
positionstoleftintherowofthesquaregridofprocesses,wherei
istherow
numberoftheprocessinthemesh.TheblocksofmatrixBarecircularlyshiftedj
positionsupwards,wherejisthecolumn
numberoftheprocessintheprocessesmesh.2024/12/816Cannon-inital2024/12/817Cannon-runningThealgorithmperformsthefollowingstepsineachstage:
1.MultiplytheblockofmatrixAandmatrixBandaddtheresultantmatrixtogettheblockmatrixC,whichisinitiallysettozero.
2.CircularlyshifttheblocksofmatrixAtoleftintherowsoftheprocessesandtheblocksofmatrixBupwardsinthecolumnsofthesquaregridofprocessesinawraparoundmanner.
2024/12/818Cannon-running2024/12/819Cannon-running2024/12/820书中Cannon-bug2024/12/821
MPI_SendandMPI_Recvisnotusedforpoint-to-pointcommunicationbecauseifalltheprocessescallMPI_SendorMPI_Recv
indifferentorderthedeadlockedsituationmayarise.
Howtofix?指派一个缓冲区,使用MPI_Irecv/MPI_Isend非阻塞式通讯函数,MPI_wait.MPI_Sendrecv.
2024/12/822Cannon-bug
死锁的问题 问题来源于main_shift()这个函数中MPI函数的使用。在Cannon-mpi代码的main_shift()模块中,文献中算法使用的是MPI的阻塞通信函数:MPI_Send/MPI_Recv,这就使得Cannon算法在执行循环左移和循环上移时,矩阵规模超过共享buff的容量时出现循环等待的死锁状况。 在曙光4000集群系统上,该算法的发生死锁的矩阵下限规模是200×200的浮点型矩阵。2024/12/823Cannon-bug原始(阻塞式)的main_shift模块:
voidmain_shift() { … /*将分块b左移位*/
MPI_Send(a,dl2,MPI_FLOAT,get_index(my_row,my_col-1, sp),1, MPI_COMM_WORLD);
MPI_Recv(a,dl2,MPI_FLOAT,get_index(my_row, my_col+1,sp),1, MPI_COMM_WORLD,&status); /*将分块b上移位*/
MPI_Send(b,dl2,MPI_FLOAT,get_index(my_row-1,my_col, sp),1, MPI_COMM_WORLD);
MPI_Recv(b,dl2,MPI_FLOAT,get_index(my_row+1, my_col,sp),1, MPI_COMM_WORLD,&status);
}2024/12/824Cannon-bug改进(非阻塞式)的main_shift模块
…
c[i*dl+j]+=a[i*dl+k]*b[j*dl+k]; //改进了的Cannon按行存取
/*将分块a左移位*/
MPI_Isend(a,dl2,MPI_FLOAT,get_index(my_row,my_col-1,sp),1,MPI_COMM_WORLD,&myrequest_s);
MPI_Irecv(buf,dl2,MPI_FLOAT,get_index(my_row,my_col+1,sp),1,MPI_COMM_WORLD,&myrequest_r);
MPI_Wait(&myrequest_s,&status);
MPI_Wait(&myrequest_r,&status);
memcpy(a,buf,sizeof(float)*dl2); /*将分块b上移位*/
MPI_Isend(b,dl2,MPI_FLOAT,get_index(my_row-1,my_col,sp),1,MPI_COMM_WORLD,&myrequest_s);
MPI_Irecv(buf,dl2,MPI_FLOAT,get_index(my_row+1,my_col,sp),1,MPI_COMM_WORLD,&myrequest_r);
MPI_Wait(&myrequest_s,&status);
MPI_Wait(&myrequest_r,&status);
memcpy(b,buf,sizeof(float)*dl2);2024/12/825Cannon-bugMPI_Irecv仅仅初始化接受操作,在与之对应的MPI_Wait函数的调用返回之前,将不能访问bufferMPI_Irecv函数返回时,handle指向一个MPI_Request对象,它代表了一个已近初始化了的通信操作。这个函数并不返回一个指向MPI_Status对象的指针,因为实际的接受操作并未完成。MPI_Wait会一直阻塞,直至参数handle所关联的操作完成,对发送来说,此时就可以向缓冲区写入新的值。而对接收来 说,便可以从缓冲区读取消息,而status所指向的MPI_Status对象包含了所接收消息的信息。新增加buf的目的就是防止在a还未发送出去的时候就recv内容至a中导致信息的错误,只有在MPI_Wait返回以后,再调用mencpy将buf的内容写回a中,完成更新。2024/12/826Cannon乘法mpi代码主要模块intget_index(introw,intcol,intsp)//处理器逻辑阵列坐标至rank号的转换
voidrandom_A_B()//随机生成矩阵A/Bvoidscatter_A_B() //rank=0的处理器向外分发A,B的相关块voidinit_alignment()//矩阵A/B初始对齐
Voidmain_shift()//分块矩阵左移和上移,并计算分块c这个模块就是我改造该算法的重点部位
voidcollect_c() //rank=0的处理器从其余处理器收集分块矩阵c
voidprint(float**m,char*str)//打印矩阵
intmain(intargc,chat*argv[])//主过程,cannon算法,矩阵相乘2024/12/827Cannon-review循环移位对齐左移上移分而治之的并行计算思想任务划分数据划分精简通讯All-to-AllPoint-to-Point每年进入夏季,由于气温高、湿度大,对幼儿的照顾要特别注意,以下是出国留学网为您搜集整理的育儿健康小常识1.不是所有宝宝都需额外补充维生素很多家长会问,孩子多大需要开始补充维生素?小婴儿是否需要补充维生素?刘主任表示,孩子多大补充维生素没有明确的界定,如果宝宝是吃母乳或奶粉,一般营养物质都足够、全面,不需要额外补充维生素,如果出现了某些症状,如缺乏维生素B或维生素C等,再有针对性的补充会更好。维生素D可以促进钙的吸收,小婴儿也应该补充,特别是纯母乳喂养的宝宝,如果没有补充维生素
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高三地理昼夜长短变化规律与计算专题教学设计
- 初中八年级信息技术语音识别技术教学设计
- 初中八年级物理第十章浮力专题复习教学设计
- 八年级地理上册《中国的地形》第二课时教学设计
- 高二英语 Unit 4 Body Language 单元复习与检测教学设计
- 高中信息技术必修1 教学设计:大数据典型应用与核心素养培育
- 八年级生物《生物的变异》分层进阶教学设计
- 高中心理健康教育“我自信我能行-构建自信心理”主题班会教学设计
- 九年级化学教学设计:跨学科实践《海洋资源的综合利用与制盐》
- 高中生物必修1《探究植物细胞吸水和失水》教学设计
- 2026年山东省潍坊市建设工程专业技术资格考试建筑工程题库及答案
- 湖北荆州市监利市2025-2026学年八年级上学期期末英语试题(含答案)
- 全国农业水产行业职业技能大赛水生物病害防治员选拔赛试题及答案
- 湖南省2027届高三九校联盟第一次联考英语试卷(含答案及解析)+听力原文及音频
- 2025年劳动关系协调员考试与答案解析三级试题含答案解析
- 政协提案知识及撰写培训课件
- 化工三废处理课件
- 养老院冬季安全知识培训内容课件
- 离散身份艺术表达-洞察及研究
- 青少年中医保健课件
- 《幼儿园班级管理 》课件-第四章 幼儿园班级安全管理
评论
0/150
提交评论