基于加速器的多核架构数据流任务编程的并行系统

基于加速器若昂·比森特·费雷拉·利马引用此版本：若昂·维森特·费雷拉·利马。一个基于加速器的多核架构数据流任务编程的并行系统。其他[cs.OH]。格勒诺布尔大学;南里奥格兰德联邦大学英语NNT：2014GRENM 092。电话：01151787v2HAL Id：tel-01151787https://theses.hal.science/tel-01151787v22015年9月16日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaireTHAPOSE为了获得等级格勒诺布尔大学博士在格勒诺布尔大学和南里奥格兰德联邦大学之间的联合教学机构中准备专业：信息2005年1月6日至2006年8月7日Présentée par若昂·比森特·费雷拉·利马Bruno RAFFIN和Nicolas MAILLARD的演讲Vincent DANJEAN的著作准备格勒诺布尔干部信息学院信息、信息学和信息学博士课程中的数学、科学和技术博士课程基于加速器Thèse soutenue publiquement le5 mai 2014，devant le jury composé de：M.菲利普·O A. 导航南里奥格兰德联邦大学校长M. Jairo PANETTACPTEC/INPE，特别报告员M.皮埃尔·曼内巴克蒙斯大学讲师，特别报告员Mme Andrea CHARúMaster de Confécement，Universidade Federal de Santa Maria，ExaminatriceM.布鲁诺·拉芬Chargé de Recherche，Université de Grenoble，Directeur de thèseM.尼古拉斯·梅拉德南里奥格兰德联邦大学校长摘要在这篇论文中，我们提出了研究问题的任务并行与数据依赖的多核架构与加速器。我们使用MOAIS团队（INRIA Rhône-Alpes）开发的XKaapi运行时系统来定位这些架构首先研究了多GPU体系结构的异步执行和调度问题。使用统计学的工作窃取显示出显著的性能结果，但没有考虑不同资源的计算能力。接下来，我们设计了一个调度框架和一个性能模型来支持XKaapi运行时的调度策略最后，我们在本机执行中对英特尔至强融核协处理器进行了实验评估。我们的结论是双重的。首先，我们得出结论，数据流任务编程可以在加速器上高效，加速器可能是GPU或英特尔至强融核协处理器。其次，不同调度策略的运行时支持是必不可少的。成本模型在非常常规的计算上提供了显著的性能结果，而工作窃取可以在运行时对不平衡做出反应。关键词：并行编程，加速器，任务并行性，数据流依赖，工作窃取。雷苏莫Uma Ferramenta para Ummação com Dependência de Dados emArquiteturas Multicore com AceleradoresEsta tese tesa os desafios no uso de tarefas de tarefas com dependências de dados emarquiteturas multi-CPU com aceleradores.在XKaapi之前，我们没有MOAIS（INRIARhône-Alpes）的研究小组，而是在工作的基础上进行研究。Em um primeiro momento ， este trabalho propôs extensives ao XKaapi a fim desobre- por transferência de dados com execução através de operaçés concorrentes emGPU，em conjunto com escalonamento por roubo de tarefas em multi-GPU.我们的实验结果表明，我们支持多GPU的可扩展性和Apesar da localidade de dados，o roubode tarefas não pondera a capacidade de processamento das unidades de processamentodisponíveis.我们研究的是升级战略，预测执行速度，以及客户执行模式。开发一个关于XKaapi的扩展框架，以便实现扩展的不同算法。您可以使用XKaapi的协处理器来本地执行英特尔至强融核。这是一个结论。首先，我们还没有得出结论，我们的计算机模型依赖于高效的数据处理器，例如GPUs和英特尔至强融核协处理器。此外，我们还可以使用不同的升级战略。我们使用的定制模式没有规则算法的背景，因为我们的目标是在执行速度上失去平衡。Palavras-chave：西班牙语，aceleradores，西班牙语，dependência de dados，西班牙语roubo de tarefas。简历Vers un Support Exécutif avec Dépendance de Données pourles Architectures Multicour avec des Accéléração在这种情况下，我们不希望出现这样的情况，因为我们需要在具有加速功能的多功能机器中使用多个组件。Lasolutionproposéeaétévelop péeenutilisantl' i n t er fa ce d ep r o g r a mm a t io n h a ut e n i v ea u X K aa p i du p r o j et M O A I S d e l ' I N R I A R<$n e- A l p es.D' a bor d n o u s a v o n s ét ud i é d es quues t io n s li és à un e a pp r o c h e d ' ex écut io n t a l em en t a s y n cr o n e et l 'or d o n an n cem en t p a r v ol d e t r a v a v a il s u rd es a r c h i t t ect u r es m u l t i- GP U.Levolde travail avec localité de données amontré des résultats significatifs ， mais il ne prend pas en compte des différentsresources de calcul. Ensuite nous avons conçu une interface etunemodèlecobaltquipettentd'écri r e d es p oli t i qu es d ' or d o n n a n ce m e n t s u r X K aa p i. Finalement on aévalué XKaapi sur un coprocesseur Intel Xeon Phi en modenatif.不需要任何提示。 D' a bor d n ou s a v o n s m o n t r é q u e l e m o d èl e p r o g r a mma tion data-flow peut être efficace sur des accéléraktels que des GPU ou des cocrocesses-seur s In t el X eo n P h i. 因此，我们可以通过以下方式解决问题： Lesmodèlesdec orécutprécuttttt' o b t en i r d e p er for r n ce s i nifica t i fs s s u r des calculs très réguliers，tandisque le vol de travail permet de redistributer la charge en co u r s d ' ex écut t io n.格言：Programmation parallèle，accélérateur，parallélisme de tâche，dependance dedonnées，vol de travail.内容图表.表格一览表算法列表1介绍11.1动机11.2假设21.3目标21.4捐款31.5上下文41.6论文大纲4I并行编程72 背景92.1并行架构92.1.1架构模型102.1.2内存系统102.1.3通用处理器112.1.4众核和异构架构112.1.5异构机器：同上162.1.617份2.2编程模型182.2.1消息传递202.2.2共享内存202.2.3分布式共享内存212.2.4数据和任务的并行性212.2.5讨论222.3调度算法222.3.1偷工作232.3.2异构最早完成时间252.3.3异构系统的算法2.3.4讨论282.4摘要283 编程环境313.1共享内存编程313.1.1OpenMP 313.1.2Cilk和Cilk++32X内容3.1.3线程构建块。. . . . . . . . . . . . . . . . . . . . . . .333.1.4 Athapascan/KAAPI。. . . . . . . . . . . . . . . . . . . . . . . . . .343.2异构体系结构。. . . . . . . . . . . . . . . . . . . . . . . . . .363.2.1 CUDA、OpenCL和OpenACC。. . . . . . . . . . . . . . . . . . .373.2.2 Charm++。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .393.2.3 StarPU。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .403.2.4 StarSs和Ompss。. . . . . . . . . . . . . . . . . . . . . . . . . . .403.2.5用于迭代计算的KAAPI扩展。. . . . . . . . . . .423.2.6英特尔至强融核协处理器编程。. . . . . . . . . . . . . .443.2.7其他高级工具。. . . . . . . . . . . . . . . . . . . . . . . .453.3摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .454 XKaapi智能系统474.1概览. 474.2Kaapi++接口484.3第51章偷工减料4.3.1数据结构524.3.2并发窃取请求534.3.3减少偷窃开销534.4数据流计算534.4.1实施例544.5摘要55II捐款575支持多GPU架构595.1Kaapi++用户注释605.2GPU工作者和任务执行615.3CPU和GPU之间的并发操作625.3.1Kstream结构625.3.2滑动窗625.4内存管理635.4.1软件缓存645.4.2一致性655.5日程安排655.5.1偷工作5.5.2数据感知工作窃取（H1）665.5.3本地感知工作窃取（H2）665.6实验675.6.1平台与环境685.6.2基准. 685.6.3并发操作685.6.4性能结果70X内容5.6.5工作窃取启发式的比较735.6.6多CPU性能影响765.7摘要776 多CPU和多GPU系统6.1调度框架806.1.1任务列表和任务描述符概述806.1.2分布式调度算法816.1.3Pop，Push，and Steal（英语：Pop，Push，andSteal）6.1.4Prologue andEpilogue钩子836.2性能模型846.2.1预测数据传输846.2.2任务的性能建模6.3基于XKaapi 856.3.1本地意识工作窃取866.3.2异质最早完成时间866.3.3分布式对偶近似876.4实验876.4.1平台与环境886.4.2A.方法886.4.3基准896.4.4业绩906.4.5讨论. 936.5摘要957英特尔至强融核协处理器99上对本机模式的支持7.1螺纹位置1007.2偷工作1017.3实验1027.3.1平台与环境1027.3.2Xeon与XeonPhi 103的7.3.3血浆：Cholesky、LU和QR 1097.3.4BOTS：FFT、Health、SparseLU和Strassen 1117.4讨论1147.5摘要1148 结论1178.1捐款1188.2前景1198.2.1第119条指令8.2.2XKaapi基准测试1208.2.3英特尔至强融核扩展1208.2.4并行自适应算法8.2.5ExascaleSystems 121X内容参考书目123III《古兰经》137一 Cholesky overXKaapi 139A.1平铺Cholesky算法139A.2XKaapi数据流版本140A.3并行对角分解141A.4带注释的版本B XKaapi性能模型结果149B.1基于历史的模型结果149B.2通信带宽结果149C 使用XKaapi、OmpSs和StarPU 151的C.1Cholesky 152C.2分块矩阵乘法152C.3摘要152D 出版物155图目录1.1本论文贡献的时间轴（绿框）42.1多核（左）和众核（右）微处理器之间的设计差异。该多核布局基于来自最近微处理器的基本模型，并且众核布局类似于GPU架构表示122.2支持CUDA的GPU架构概述。......................................................................142.3第一个线程束上的GPU分支发散示例2.4Intel Knights Corner的微体系结构图，简化以说明这些芯通过双向环162.5使用hwloc的英特尔至强融核5110 P协处理器的拓扑。...............................172.6具有两个六核CPU和八个Tesla C2050 GPU的相同硬件拓扑172.7应用程序和硬件之间的并行桥，桥代表了发送并行编程模型192.8具有共享段的PGAS编程模型的内存视图ing全局空间，以及每个线程的私有段213.1使用OpenMP任务进行斐波那契计算的示例323.2斐波那契数计算的递归实现（左）与其Cilk版本（右）相同。每次递归调用spawn都会异步创建一个新任务。sync关键字用于等待先前创建任务并汇总其结果333.3斐波那契数列的英特尔TBB任务示例。.....................................................343.4递归版本的斐波那契序列与Athapascan接口。.......................................... 363.5Athapascan模型37上的Fibonacci依赖图3.6KAAPI运行时结构。................................................................................ 373.7Charm++ GPU管理器的代码示例，任务提交到GPU393.8矢量缩放的StarPU程序示例3.9使用OmpSs注释进行多版本化的矩阵乘法示例423.10 C++ KAAPI多任务定义实现实例。 左边是CPU实现，以及右侧的GPU实现433.11 使用英特尔卸载编译器444.1KAAPI和XKaapi运行时的比较。.................................................................484.2来自C++函数的Kaapi++任务签名示例494.3将C++函数映射到Kaapi++任务494.4Kaapi++比较在数据库的数据和数据库的数据之间进行分配。504.5创建Kaapi++任务...........................................................................................................XIV图目录4.6使用CPU和GPU实现的Kaapi++多版本514.7Kaapi++分块矩阵乘积的简化示例554.8分块矩阵产物565.1Kaapi++API 60中的调度提示示例5.2XKaapi的多GPU架构一个核心致力于控制目标GPU 615.3最近GPU卡中的顺序和并发操作5.4用于跟踪共享数据的有效副本的XKaapi kmd结构5.5多GPU实验的相同硬件拓扑5.6性能结果来自DGEMMon Idrock，用于单个CPU和单个GPU，以及不同的块大小.......................................................................................................................695.7Cholesky在Idrock上针对单CPU和单GPU的性能结果，块大小为1024×1024.......................................................................................................715.8DGEMM性能高达8个GPU。矩阵大小为16384 <$16384，块大小为1024<$1024...................................................................................................................715.9使用16384× 16384矩阵和块的多GPU Cholesky分解尺寸10241024725.10 比较我们的三个工作窃取算法在8个GPU上的DGEMM矩阵大小为4096040960 745.11 DPOTRF在八个GPU和四个CPU上的矩阵性能结果尺寸4096040960 755.12 Cholesky在8个GPU和4个CPU上的工作窃取算法的可扩展性与一个GPU和一个CPU执行相比755.13 Cholesky在4 CPU和8GPU上的XKaapi默认和本地感知工作窃取算法重叠的影响765.14 矩阵大小为6144的平行对角线Cholesky的图4个GPU（红色）和最多4个CPU（蓝色）776.1XKaapi调度框架的通用调度循环6.2XKaapi 83上一种调度策略的C语言数据结构6.3为调度策略的实验结果确定硬件拓扑896.4矩阵产品（DGEMM）的性能结果916.5Cholesky（DPOTRF）92的性能结果6.6LU（DGETRF）93的性能结果6.7QR（DGEQRF）94的性能结果7.1英特尔至强融核1017.2XKaapi、OpenMP和Intel的Fibonacci加速优于顺序执行Cilk Plus（输入N=38）1047.3XKaapi的NQueens基准测试（N=17）的时间与阈值，英特尔Cilk Plus和OpenMP 1057.4XKaapi、英特尔Cilk Plus的NQueens基准测试（N=17）的可扩展性OpenMP 1067.5使用XKaapi和Intel Cilk的左视Cholesky分解示例加107图目录XV7.6Cholesky针对XKaapi、OpenMP和Intel Cilk Plus的基准测试结果，矩阵大小为8192× 8192，图块大小为256× 256。仅测量了MKL在英特尔至强融核上，并在英特尔至强Sandy Bridge上省略。.............1087.7针对XKaapi、OpenMP和Intel Cilk Plus的Cholesky基准测试结果，矩阵大小为16384× 16384，切片大小为512× 512。MKL只是在英特尔至强融核上测量，在英特尔至强Sandy Bridge上忽略。1087.8来自PLASMA的Cholesky因子分解结果，矩阵大小为8192< $8192英特尔至强融核1117.9LU分解结果来自PLASMA，矩阵大小为8192× 8192，英特尔至强融核1117.10 来自PLASMA的QR分解结果，矩阵大小为8192× 8192，英特尔至强融核1127.11 BOTS基准测试FFT、Health、SparseLU和Strassen的初步结果Intel XeonPhi 1138.1基于OpenMP 4.0标准A.1为乔莱斯基计划进行数据处理数据是真实的--在执行之前注册，并在结束时注册141A.2 使用XKaapi C++ API（kaapi++）实现左向Cholesky它还显示了任务签名及其参数和访问模式作为并行CPU版本142A.3Cholesky算法的TRSM任务的实现。此任务使用具有任务签名以及CPU和GPU版本的...................................................................................................多版本控制144A.4Cholesky分解145的所得数据流图（DFG）A.5带XKaapi 146的两级Cholesky版本A.6带有XKaapi编译器147B.1性能模型得出的任务的时间（左）和加速比（右）CPU和GPU版本。 y轴使用对数刻度B.2性能模型中使用的通信带宽近似值。150C.1矩阵大小为10240 μ m的Cholesky分解的性能结果10240和块大小1024 1024 152C.2矩阵大小为10240μ m的矩阵乘法的性能结果10240和块大小1024 1024 153表的列表2.1系统....................................................................................................................18中所有处理单元的相同峰值性能以及估计的DGEMM性能5.1以GB为单位的DGEMM的内存传输，矩阵顺序为16384 <$16384，块大小为1024 <$1024。输入和输出数据传输的总和为8 GB。 725.2Cholesky的内存传输以GB为单位，矩阵大小为16384<$16384，块大小为1024< $1024。 输入和输出数据传输的总和为4 GB。735.3使用4个GPU和可变数量CPU的性能结果（以GFlop/s为单位）767.1Intel Xeon Sandy BridgeIntel XeonPhi 1097.2用于英特尔至强融核实验的PLASMA方法和参数PLASMA的参数是基质尺寸、块尺寸（NB）和内部尺寸。块大小（IB）...........................................................................................................1107.3英特尔至强融核112上BOTS的输入参数和运行时开销算法列表1最早完成时间不均匀。..................................................................................262XKaapi 54中的数据流计算3数据感知工作窃取以减少数据传输664本地感知工作窃取以减少缓存失效675一个工人wj81..................................................................................................6异构最早完成时间（push_activated）867分布式对偶逼近（push_activated）888XKaapi算法窃取英特尔至强融核102上的任务9Cholesky因式分解的平铺算法