混合架构超算并行程序设计与应用习题答案

第一章绪论1.请简述超级计算机的作用。超级计算机(Supercomputer，简称超算)作为国之重器，在科学计算(如生物大分子模拟预测、新药物研制、核反应堆模拟、新材料研究、地震模拟、气象模拟)、国防军事(如密码破译、先进武器开发)、人工智能(如大规模机器学习训练)、动画渲染及可视化等领域发挥着越来越重要的作用。2.什么是计算流体力学？计算流体力学(CFD)是科学计算领域的典型代表，下面从CFD的几个具体实例来看应用领域对计算能力更强的超算的需求。复杂外形湍流的数值模拟一直是CFD领域的研究热点、难点。常见的湍流数值模拟方法有直接数值模拟(DNS)、大涡模拟(LES)和雷诺平均Navier-Stokes模拟(RANS)等。3.请简述熟悉超算体系结构。对体系结构特性的了解，可以直接指导上层算法和软件的高效实现与优化。对现代异构混合计算硬件的多级存储结构(内存、L2cache、L1数据cache、LI指cache可编程的片上小缓存等),需要了解其存储空间大小、访存带宽与延迟及访存特性(如GPU上sharedmemory的bank冲突)等。4.如何贴合硬件体系结构的性能优化技术？基于超算硬件体系结构，结合超算上的编程模型与算法实现，开展算法的性能优化，是进一步提升应用软件性能的关键。这需要了解程序的性能分析评价指标和性能分析方法开展程序性能建模。在此基础上，开展高效访存模式、高效数据传输模式、计算指令、任务调度优化等内容研究。5.什么是并行编程方法与并行算法？并行编程方法与并行算法是进行高性能计算应用和算法库实现的重点，也是不可跳过的环节。基于超算硬件，需要了解超算厂商提供的用于驱动硬件进行高效计算的API接口如HIP、CUDA、OpenMP、神威的CRTS等。第二章异构混合架构概述1.查询最新的TOP500榜单，统计超算使用的芯片类型、厂商和数量。在本次超算500强榜单当中，采用AMD芯片的超算系统总量增加到了101套，正式突破了一百大关，同比增加达到38%。在本次榜单当中，第一次进入榜单的超算系统当中，有84%的超算系统采用了AMD芯片。除了在整体数量和新进数量方面表现亮眼之外，在顶尖排名当中，AMD的表现也十分不俗，在前十当中，AMD芯片占据了四位，在前二十当中，AMD芯片占据了12位。本次排名第一的全球顶尖超算依然是美国的Frontier，而这一台超算是搭载了全套的AMD方案。处理器采用了第三代的EPYC，加速卡则是AMD的InstinctMI250X。再加上AMD刚发布不久的第四代EPYC刚开始上市就被中东部署的ShaheenIII所采用。2.目前TOP500榜单，最有名的是按照浮点计算性能排行。思考是否还有其他排序标准，以及它们侧重点的区别。除性能排行榜TOP500榜单为，大会还公布了侧重能效的Green500（全球最高能效超级计算机）榜单，排在首位的则是Henri超算。它是基于联想ThinkSystemSR670V2。CPU为Intel的Icelake架构至强Platinum8362，GPU则是NVIDIA的H10080GBPCIe显卡。3.查阅相关资料，比较GPU、DCU等加速设备之间的不同点及优缺点。CPU对于现代计算任务有几个明显的优势：灵活性——CPU是一种通用处理器，可以处理许多任务，以及多个活动之间的多任务。在许多情况下更快——在处理RAM中的数据处理、I/O操作和操作系统管理等操作时，CPU比GPU更快。精度——CPU可以支持比GPU精度更高的中等数学运算，这对于许多用例来说都很重要。高速缓存——CPU有一个很大的本地高速缓存，这让它们可以处理大量的线性指令。硬件兼容性——CPU兼容所有类型的主板和系统设计，而GPU需要专门的硬件支持。与GPU相比，CPU有以下缺点：并行处理——CPU不太擅长处理需要数百万个相同操作的任务，因为它们的并行性有限。发展较慢——CPU是一项非常成熟的技术，已经达到其发展的极|限，而GPU有更大的改进潜力。兼容性——几种类型的CPU，包括x86和ARM处理器，以及软件可能不兼容所有类型。GPU的独特优势包括：高数据吞吐量——GPU可以对许多数据点并行执行相同的操作，因此它可以以CPU无法比拟的速度处理大量数据。大规模并行—个GPU有数百个核心，使其能够执行大规模并行计算。适用于专门的用例——GPU可以为深度学习、大数据分析、基因组测序等专门任务提供巨大的加速。与CPU相比，GPU的缺点包括：多任务——GPU可以大规模执行一项任务，但不能执行通用计算任务。成本——单个GPU目前比CPU贵得多。专门的大型GPU系统成本可达数十万美元。处理复杂性——GPU可能难以处理结构不完善的任务。它们无法有效地处理分支逻辑、顺序操作或其他复杂的编程模式。4.查阅相关资料，选择3个先进超算，比较它们针对数值模拟机器学习等专业领域，在芯片设计、指令集等方面做出的优化。日本的富岳超级计算机在排名中较为靠前，但是，该计算机出现了排名不确定的问题。富岳超级计算机是由日本国家信息通信技术研究所开发的，用于芯片设计、天气预报等领域。但是，在2019年的超级计算机排名中，该计算机的排名不确定，因为该计算机的数据存在错误。此外，光环计算机研究中心研发的日本京超计算机也曾遭遇排名不确定的问题。中国的超级计算机曾经得过多次冠军。但是，在2023年的排名中，中国的超级计算机排名居于第七的位置。需要指出的是，中国的超级计算机的性能已经更新了至少超过2代以上，性能的速度之快被誉为世界最快，但是排名的确存在一定的不确定性。5.访问超算中心主页，查询手册，了解超算资源的申请方式，以及计算节点的登录和使用方式。一、申请账号首先，需要在超级计算机的官方网站上申请账号。申请时需要提供个人信息和研究领域等相关信息。申请通过后，会收到一封邮件，其中包含账号和密码等信息。二、登录系统使用超级计算机需要通过SSH协议登录系统。在Windows系统中，可以使用PuTTY等SSH客户端软件进行登录。在Linux和Mac系统中，可以使用终端进行登录。登录时需要输入账号和密码。6.完成单机的Linpack性能测试(建议使用HPL)，有条件可采用多机互连实现。linpack测试包括三类，linpack100、linpack1000和hpl。在上述三种测试中，linpack100对数组的求解规模为100阶的稠密线性代数方程组，它只允许采用编译优化选项进行优化，不得更改代码，甚至代码中的注释也不得修改。linpack1000的求解规模为1000阶的线性代数方程组，为了达到指定的精度要求，可以在不改变计算量的前提下做算法和代码上做优化。而hpl即highperformancelinpack，也叫高度并行计算基准测试，它对阶次n没有限制，即求解规模可以改变，除基本算法(计算量)不可改变外，可以采用其它任何优化方法。前两种测试运行规模较小，已不是很适合现代计算机的发展，因此现在使用较多的测试标准为hpl，而且阶次n也是linpack测试必须指明的参数。目前linpack测试中，hpl配置文件中n的取值往往会根据测试者的经验，根据内存容量的80％左右相应地取值。但由于各类服务器的实际配置和应用场景的不同，对应的最佳性能往往会存在一定偏差，使得测试结果不能达到最优。因此，需要提出一种linpack测试的优化方法，通过相应的算法在测试中选出最优的阶次n从而得到最优的测试结果。7.用OpenMP、MPI分别实现计算值的并行程序，记录串行程序和并行程序的执行时间及使用的核数。MPI可以在多个计算节点之间传递数据，并使这些节点在同一时间执行不同的计算任务，从而实现并行计算。在使用MPI进行并行计算开发时，需要将计算任务划分为多个子任务，并将这些子任务分配给不同的计算节点。每个节点都需要执行自己的计算任务，并将计算结果传递给其他节点。这需要使用MPI提供的一些函数来实现8.讨OpenMP+MPI并行(节点内用OpenMP，节点间用MPI)和纯MPI(节点内和节点间都用MPI)并行两种方案的优劣。MPI和OpenMP是两种常用的并行计算技术，它们分别用于分布式计算机系统和共享内存计算机系统中。使用这些技术可以将计算任务划分为多个子任务，并将这些子任务分配给不同的计算节点或CPU核心。这些技术提供了一些函数或指令来实现数据传输和任务分配。在实现并行计算应用时，需要根据具体的需求选择适合的技术和工具。9.总结本章并行编程语言各自的应用场景，包括编译器、硬件设备、是否支持分布式内存等。程序访问完一个存储区域往往会访问接下来的区域，这个原理成为局部性。在访问完一个内存区域（指令或者数据），程序会在不久的将来（时间局部性）访问邻近的区域（空间局部性）。第三章异构混合架构性能分析理论1.实际加速比无法达到理想加速比的原因有哪些?随着处理器数量的增加，问题的规模(工作负载)保持不变；目标是更快地运行相同大小的问题；在理想情况下，当处理器规模是基准测试的规模的n倍时，其运行时间应该为基准程序的1/n，即理想的加速比应该为n。2.在并行度为p的情况下，某一并行程序的加速比是p-1(相对于单处理器下的情况),根据Amdahl定律，该程序的串行负载比是多少?Amdahl定律计算公式：S=1/(1-a+a/n)S:加速比a:并行计算部分所占比例n:并行处理节点个数(处理器个数)3.某一并行程序在单处理机上运行时，10%的运行时间花费在不可并行化的串行函数中，90%的运行时间花费在可以并行化的函数中。问该程序在多处理机上运行，以单处理器为基准，当并行规模扩大多少倍时，该程序的加速比才能达到5?该程序可达到的最大加速比是多少?加速比=优化前系统耗时/优化后系统耗时所谓加速比就是优化前的耗时和优化后的耗时的比值。加速比越高，表明优化效果越明显。根据这个公式，如果CPU处理器数量趋于无穷，那么加速比与系统的串行化比例成反比，也就说

如果系统中有50%的代码必须串行化，那么系统的最大加速比为2。4.假设某问题的工作负载为W，可并行部分的负载Wp占总负载的60%，其余部分的负载Ws占总负载的40%。以单处理器为基准，在并行度为10时，分别求固定负载和固定时间下的加速比。略。5.通过nvidia-smi或者rocm-smi等命令输出硬件的相关信息，计算GPU的理论性能和理论带宽。nvidia-smi—NVIDIA

SystemManagementInterfaceprogram即英伟达系统管理界面程序。

nvidia-smi（也称为NVSMI）为来自Fermi和更高体系结构系列的nvidiaTesla、Quadro、GRID和GeForce设备提供监控和管理功能。GeForceTitan系列设备支持大多数功能，为GeForce品牌的其余部分提供的信息非常有限。NVSMI是一种跨平台工具，支持所有标准NVIDIA驱动程序支持的Linux发行版，以及从WindowsServer2008R2开始的64位版本的Windows。6.编写benchmark测试当前计算机的有效性能和有效带宽。1.基准测试代码文件必须是_test.go结尾，和单元测试一样；2.基准测试的函数以Benchmark开头；3.参数须为*testing.B；4.基准测试函数不能有返回值；5.b.ResetTimer是重置计时器，这样可以避免for循环之前的初始化代码的干扰；6.b.StopTimer()停止计时器7.b.N是基准测试框架提供的，Go会根据系统情况生成，不用用户设定，表示循环的次数，因为需要反复调用测试的代码，才可以评估性能。7.实际运行中影响程序达到理论性能和理论带宽的因素有哪些?（1）网络设备（交换机、路由器、集线器）；（2）拓扑结构（即网络构造形状，如星型、环状）；（3）数据类型；（4）用户的数量；（5）客户机与服务器（如系统总线、磁盘性能、网络适配器、硬件防火墙）；（6）电力系统和自然灾害引起的故障率。8.考虑如下的算法(7-pointstencil)，求其计算密度，其中，new数组和old数组都是三维的双精度浮点数组，dim数值足够大。确定物体的质量：使用天平等工具测量物体的质量，记录下质量值。确定物体的体积：物体的体积可以使用各种方法进行测量，例如水位移法、容积法等。不同的物体可以选择不同的方法进行体积测量。计算密度：使用物体的质量和体积计算密度，即密度=质量/体积。单位换算：密度的单位通常为克/立方厘米（g/cm³），有时也可以使用千克/立方米（kg/m3）等单位。需要根据实际需要进行单位换算。注意小数点精度：在计算密度时需要注意小数点精度，保留适当的位数可以更好地反映出物体的密度。确定物体的质量：使用天平等工具测量物体的质量，记录下质量值。9.以NVIDIATeslaV100为例，画出其roofline性能模型。略。10.阅读roofline性能模型的原始论文或相关报告，探讨考虑cache等多级存储后roofline性能模型的改进。1.提升平台的宽带2.采用片上mem或者片上cache融合的方案，获得更大带宽3.采用多算子多步骤融合4.提升模型的计算强度第四章CPU高性能程序设计1.利用MPI或者OpenMP并行编程模型，实现密阵与向量的乘法，并测试不同MPI进程或者OpenMP线程下的性能。效率：测试不同连通域数目的数据、不同机器环境（单机和集群）、不同并行编程模型（MPI和OpenMP）对二次扫描并行算法效率的影响。测试环境a）单节点CPU：两颗Intel(R)QuadCoreE5645Xeon(R)CPU，共12核；内存：80GB；操作系统：LinuxCentOS64位。b）高性能集群（4个计算节点，1个存储节点）CPU：两颗Intel(R)QuadCoreE5645Xeon(R)CPU，共12核；内存：32GB；操作系统：LinuxCentOS64位；节点间文件系统：NetworkFileSystem（NFS）。c）测试数据两个相同数据量（18640×22260）的二值栅格图像，一个连通域为3个（简单图），一个连通域为10433个（复杂图）。2.完成函数积分的向量化指令程序开发。略。3.用MPI集合通信(如MPIReduce)改写4.31节中的MPI梯形积分程序。梯形积分法原理用a和b之间的梯形面积来近似替代a和b之间函数与x轴围成的面积,当a和b之间的区间分的越来越细的时候,近似值就会不断逼近真实值。4.利用MPI点对点通信，实现MPI_Allreduce功能;并讨论是否还有其他更高效的实现方法。点对点通信来实现求和、求积等功能，但是对于找到所有进程中的最大值、最小值的功能来说，可能就比较繁琐了。而且，点对点通信最后一般都由一个进程（通常是0号进程）来做总结的工作，例如各个进程的部分和传给0号进程，然后0号进程求总和。这样所有分支汇集在一起的做法会导致各个进程的工作量分配不均，某些进程比较闲，某些进程比较忙的状况。

因此MPI的开发人员就开发了集合通信这样的技术，优化了内部的算法，使其能尽可能平均各个进程的工作量，而且基本上能适应各种数据量和使用环境。5.完成GEMM的串行程序开发，并完成不同循环顺序的运行时间、浮点运算性能测试，利用相关工具分析cache缺失次数。其中，矩阵大小可根据实际配置自定。略。6.有条件的可安装Imtelvtune或者Score-P性能分析工具，选择一个并行软件进行性能分析。IntelVTuneProfiler是一个全平台的性能分析工具，可以帮助你快速发现和分析应用程序及整个系统的性能瓶颈。工具支持分析本地或远程的Windows，Linux及Android应用，这些应用可以部署在CPU，GPU，FPGA等硬件平台上。支持分析的语言包括：DPC++，C，C++，C#，Fortran，OpenCL，Python，Go，Java，汇编等。7.讨论本章涉及的相关性能分析工具的大致原理和分类(如是基于采样的还是基于硬件计数的)，讨论性能分析工具对程序真实性能的影响。发现性能问题：性能测试工具可以模拟大量的用户访问，通过对应用程序的性能指标进行监控和分析，发现隐藏在代码中的性能问题和瓶颈。改善用户体验：应用程序的性能不仅影响到程序运行速度，还会直接影响到用户体验。通过性能测试工具的分析结果，可以定位程序的性能瓶颈并采取措施来提升用户体验。优化程序设计：性能测试工具可以帮助开发人员评估各种技术选项对应用程序性能的影响，并提供实际数据支持，从而优化程序设计，提高应用程序的效率、可靠性和扩展性。保证系统可靠性：在商业应用程序中，系统的可靠性至关重要，特别是面对大量用户访问和流量峰值时。通过性能测试工具的测试，可以确定系统的强度和可靠性，确保系统在不同负荷下的运行稳定性。降低成本：使用性能测试工具可以及早发现和解决性能问题，避免后期修复的高成本和长时间停机带来的经济损失。加速软件开发周期：通过使用性能测试工具，可以及早发现性能问题，加快问题解决的进程，从而缩短开发周期，提高软件交付效率。安全性保障：一些性能测试工具也可以检测应用程序中的安全漏洞，以便开发人员及时更新和维护代码，保证系统的安全性。8.GEMM的MPI版本开发与性能分析。作为并行程序的底层通信接口，它的执行效率对并行程序的并行性能有很大的影响。第五章神威异构众核程序设计1.对比GPU或DCU架构，比较神威加速硬件(即从核)进行计算与通信(指访问主存)相互重叠的方案的区别，以及各方案的优缺点。（1）通用性差。这是神威设计初期就带来的弱点。（2）无法用GPU，很多基于GPU的人工智能无法应用，使得神威在人工智能领域很难发挥超算的作用。（3）功耗大（因为内核数量巨大），所以在性能/功耗指标上不占优势。2.编写程序测试从核访问主存的访存带宽和访问LDM带宽。略。3.神威超算上的存储层次有哪些?它们的访存特点是什么?低级存储器是存储器层次中最低的一层，通常采用机械或电子方式存储和读取数据。低级存储器的主要作用是存储启动程序和随机访问数据。它的特点是存储密度低、读写速度较慢，但可靠性高、稳定性好。低级存储器通常由磁盘、光盘、软盘、闪存等构成。其中，磁盘是最常用的低级存储器，它通过电机驱动实现数据的读写操作。光盘和软盘则主要用于存储数据，它们的优点是存储密度高、读写速度较慢但可靠性高、稳定性好。中间存储器是存储器层次中的第二层，通常采用电子或磁存储介质。中间存储器的主要作用是存储程序和数据，以便在主存储器中更快地访问和存储数据。中间存储器通常由高速缓存、固态硬盘、闪存等构成。高速缓存是计算机系统中最常用的中间存储器，它通常由高速的集成电路构成，用于存储主存储器中访问频率较高的数据。固态硬盘则是一种采用闪存存储介质的中间存储器，它的优点是读写速度极快、可靠性高、稳定性好。高级存储器是存储器层次中的最高一层，通常采用光学或声学存储介质。高级存储器的主要作用是存储长期数据，以便在需要时进行读取和存储。高级存储器通常由蓝光光盘、录音带、光存储器等构成。蓝光光盘是一种采用激光读取数据的存储器，它的优点是存储密度高、读写速度较慢但可靠性高、稳定性好。录音带则是一种采用声波读取数据的存储器，它的优点是存储密度低、读写速度较慢但可靠性高、稳定性好。4.考虑本章stencil示例部分，对从核上的内循环代码，实现其向量化改写，并测试性能。1.确定待优化的循环操作。首先，我们需要确定需要优化的循环操作。通常情况下，循环操作的次数较多，耗时也比较长，因此优化循环操作可以大幅提高代码效率。2.将循环操作转换为向量操作在确定需要优化的循环操作后，我们可以将其转化为向量操作。3.利用现有函数库进行向量化操作为了简化向量化操作的步骤，我们可以利用现有向量化操作的步骤，我们可以利用现有的函数库进行向量化操作。4.优化代码实现完成向量化操作后，我们还可以通过优化代码实现进一步提高代码效率。5.考虑本章stencil示例部分，当矩阵中一行较长，LDM不足以存储5行数据时，应如何解决?可运用STM和LDM加上后缀进行压栈和出栈。6.利用神威的从核阵列，实现稀疏矩阵向量乘法，其中，稀疏矩阵采用CSR格式存储(CSR格式介绍参见第8章)。略。7.评估本章5.2.3节的矩阵乘法实现的访存带宽和计算性能，并讨论如何进一步提高计算性能。1、使用缓存。缓存可以提供更快的访问速度，并降低内存访问开销。在矩阵乘法运算中，多次访问相同矩阵元素时，使用缓存可以有效提高计算效率。2、采用分块算法。分块算法将矩阵分割成若干小矩阵，每次计算一小块，从而减少了矩阵的大小，减少了计算量。3、利用多核处理器。多核处理器可以同时实现多个矩阵乘法计算，有效提高计算效率。4、使用SIMD指令。SIMD指令是单指令多数据指令，可以同时处理多个数据，有效提高计算效率。5、利用GPU加速。GPU拥有很高的计算性能，可以有效加速矩阵乘法运算，提高计算效率。6、使用矩阵复用技术。矩阵复用技术可以将原来需要执行的多次矩阵乘法运算合并为一次，有效降低计算量。7、采用矩阵分解算法。矩阵分解算法可以将大矩阵分解成若干小矩阵，进而减少计算量，提高计算效率。第六章面向DCU架构的程序设计与优化1.对比NVIDIAGPU和DCU在硬件架构上的差异。GPU是显卡中间的一块芯片。显卡就是一块大板子。其次,cuda是通用并行计算架构。GPU进行图像的渲染,但是并不是所有的GPU均支持浮点计算,其计算的原理区别在于是否存在CUDA通用并行计算架构的运算平台。DCU整体硬件架构类似于GPU架构,DCU硬件架构也通过PCI-E总线与CPU相连,这就表明DCU更多是作为协处理(加速器)的存在,用于加速计算密集型计算步骤,而不能取代CPU的主导地位。2.如何测量DCU的L1datacache大小及LIdatacacheline大小?首先设计一个用于测量x86系统上cache层次结构的方案然后设计出相应的代码;然后,运行你的代码获得相应的测试数据。最后,根据测试数据分析你的x86机器有几级cache,各自容量是多大。3.尝试通过rocm-smi等命令输出的信息，计算DCU的理论访存带宽和理论峰值性能。略。4.实现6.7节的各种reduce算法，并测试比较其性能差异。大数据量的情况下依然时for循环完胜，但是reduce胜在写法简便，不用额外定义太多属性就能完成简单的数据分组。5.利用LDS实现矩阵转置，矩阵大小为1024x1024和208x2048两种，并分析bank冲突情况，尝试解决bank冲突。要解决bank冲突，首先我们要了解一下共享内存的地址映射方式。

在共享内存中，连续的32-bits字被分配到连续的32个bank中，这就像电影院的座位一样：一列的座位就相当于一个bank，所以每行有32个座位，在每个座位上可以“坐”一个32-bits的数据(或者多个小于32-bits的数据，如4个char型的数据，2个short型的数据)；而正常情况下，我们是按照先坐完一行再坐下一行的顺序来坐座位的，在sharedmemory中地址映射的方式也是这样的。6.利用warpvote函数，实现统计bitmap中的比特1的数量的统计。(考虑bitmap分别位于localmemory和devicememory中)。第一步是统计每2位中1的个数。由于每2位数字最多可包含2个1,所以需要分别统计两次。如下:i&F”仅保留奇数位置的1,(i>>1)&F仅保留偶数位置的1。二者相加得到每2位具有1的个数。同样,再统计每4位上的1的格式,将0011抽象成一个大的1即可得到相似的代码。7.实现密矩阵(该密矩阵中较多位置为0)转CSR格式的算法，并在DCU或GPU上测试。在Matlab中，可以使用sparse函数创建稀疏矩阵，并使用spmattimes函数将其转换为CSR。转换为CSR格式的矩阵ia和ja都是从1开始枚举的索引，而不是从0开始。如果需要与其他语言（如C++、Python等）交互，需要注意这种差异。8.思考占用率问题:哪些因素会影响CU内被调度进来执行的Block数量?正在执行的进程已经执行完毕或遇到异常情况，需要调度新的进程；执行中，进程自己调用了阻塞原语将自己阻塞起来进入睡眠等状态，需要调度新的进程执行；执行中，进程调用了P原语，从而因资源不足而被阻塞，需要调度新的进程；执行中，进程调用了V原语，从而激活了等待资源的进程队列；进程提出

I/O请求后，被阻塞，需要调用新进程；在分时系统中，已分配的时间片用完了；在可剥夺式调度方式中，在就绪队列中某进程的优先级更高，高于当前执行的进程。9.编程实现深度学习中的卷积操作。矩阵卷积我们希望可以定义这样一个矩阵。:输入矩阵和我们所定义的矩阵进行矩阵相乘就可以完成卷积计算。这个矩阵称为卷积矩阵,它是对卷积核kernel进行重新排列之后获得的。举个例子:3x3的卷积核参数如下:我们对这个3x3卷积核重新排列得到了一个4x16的矩阵:上面就是一个卷积矩阵(convolutionmatrix)。每一行定义了一个卷积操作。10.如何评估程序的实际访存带宽和实际峰值性能?思考哪些程序或算法是计算密集型，哪些程序是访存密集型?访存密集型算子主要包括以下两种类型：IO密集（比如LookupTableFindV2，Gather等）；计算复杂度低（比如Shape，二元运算符max,min,sub,add)。这些算子在CTR模型领域主要集中在特征网络中，也可以理解为特征工程环节。第七章异构混合架构上的算法设计1.利用7.1.3部分的洗牌函数编写设备端函数计算wavefront内数据的最大值。略。2.利用7.1.3部分的洗牌函数编写设备函数计算wavefront内数据的总和。根据波前结构函数dwavefront的基本定义计算大口径望远镜主镜原始面形的两个正交方向的结构函数。3.在习题2的基础上，面向DCU、GPU平台，设计并实现设备端求和算法。二叉树求和的过程非常好理解:先将相邻的处理器数据收集起来,求和后再次重复,直到求出总和,最后沿着二叉树的路径将求和结果往下传导。虽然二叉树求和算法的实现相较于蝶式求和更容易理解,但实现起来却相对吃力,并且还会更加耗时。因为它还要求将数据从根部传下来,多了一个要实现的阶段。4.修改7.1.3部分的wavefrontScan算法为ExclusiveScan实现。波前整形算法（Wavefrontalgorithm）是常见的用于求解最短路径问题的一种算法。该算法利用了动态规划的思想，通过不断地更新每个节点的最短路径信息，最终得到整个图上的最短路径。具体来说，波前整形算法通常需要从起点开始向外扩展波浪，每次将波浪边界上的节点进行更新，直到扩展到终点为止。在每次扩展波浪时，需要计算出当前波浪边界上的节点向外扩展一步后可以到达的所有新节点，并更新这些新节点的最短路径信息。5.阅读Decoupled-Lookback算法对应的论文，并尝试实现。略。6.面向DCU、GPU平台，设计稠密矩阵转稀疏CSR格式的高效算法。首先需要有一个稠密矩阵，此处记作adj，将稠密矩阵adj转为稀疏矩阵adj_sp，查看稀疏矩阵adj_sp中的各个属性。7.修改7.2.3部分的GEMM算法，使其可以分别设置每个thread处理矩阵A的行数与矩阵B的列数。gemm算法是一种将卷积过程转化为GEMM过程的优化方法，适用于各种BLAS库。相比于其他方法，gemm算法在速度上更快。此外，Winograd方法也被广泛使用，特别是在cudnn中。Strassen算法是一种时间复杂度低于O(N^3)的算法，但在大卷积核情况下优势不明显。在ConvNet中，FFT时间开销较大，不常用。8.面向DCU、GPU平台，设计密矩阵转置算法。矩阵(包括稀疏矩阵)的转置,就是将矩阵中的所有元素的行标和列标进行互换。因为实现矩阵转置的前提是将矩阵存储起来,数据结构中提供了3种存储矩阵的结构,分别是三元组顺序表、行逻辑链接的顺序表和十字链表。9.尝试在GEMM计算前对矩阵A进行转置操作，统计矩阵A转置后GEMM用时并计算其FLOPS。略。10.思考SpMV中vector-row算法的缺点。(1)在内部进行插入删除操作效率低。(2)只能在vector的最后进行push和pop，不能在vector的头进行push和pop。(3)当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放。11.实现高效的DCU或GPU上的排序算法(提示:flashsort、双调排序、merge排序等)。在从内核内部启动内核之前，检查两个标准。首先，检查我们是否已经达到硬件允许的最大深度限制。其次，我们需要检查子数组中要排序的元素数量是否小于扭曲大小(32)。如果其中一个是真的，那么我们必须按顺序进行简单选择排序，而不是启动新的内核。12.阅读论文StructuralAgnosticSpMV:AdaptingCSR-AdaptiveforIrregularMatrices尝试复现论文中的CSR-AdaptiveSpMV算法。或者阅读论文Globallyhomogeneous,locallyadaptivesparsematrix-vectormultiplicationontheGPU，尝试复现按非零元素分割的SpMV算法。测试并分析该算法在不规则稀疏矩阵(不同行非零元素差别很大)下的性能。略。第八章异构混合架构常用算法库1.比较BLAS与LAPACK的区别和关系。LAPACK，其名为LinearAlgebraPACKage的缩写，是⼀以Fortran编程语⾔写的，⽤于数值计算的函式集。LAPACK提供了丰富的⼯具函式，可⽤于诸如解多元线性⽅程式、线性系统⽅程组的最⼩平⽅解、计算特征向量、⽤于计算矩阵QR分解的Householder转换、以及奇异值分解等问题。BLAS（BasicLinearAlgebraSubprograms，基础线性代数程序集）是⼀个应⽤程序接⼝（API）标准，⽤以规范发布基础线性代数操作的数值库（如⽮量或矩阵乘法）。该程序集最初发布于1979年，并⽤于创建更⼤的数值程序包（如LAPACK）。在⾼性能计算领域，BLAS被⼴泛使⽤。例如，LINPACK的运算成绩则很⼤程度上取决于BLAS中⼦程序DGEMM的表现。2.根据本章提示的主要代码片段，实现cuBLAS、cuSPARSE与CuSOLVER的示例。cuBlas用来处理dense的向量矩阵运算,cuSparse用来处理稀疏矩阵,cuSolver用来求解大规模稀疏矩阵方程。3.调用rocSPARSE函数，实现矩阵不同稀疏存储格式的转换。(1)将存储的有效数据行优先存储改为按列优先存储(转置后的