超级计算机原理与操作

超级计算机原理与操作（一）吴峻峰[e-mail]课程简介•课程对象：没有接触过超级计算机的学生•课程目的：讲解超级计算机的基本原理和基本操作知识•修这门课需要的预备知识：•对计算机的组成有一定的概念（有修过计算机组成原理更好）•学过C、C++编程•学过线性代数•课程考核形式：两次大作业（课程论文，同时提交电子和纸质版本，电子版发到[e-mail]，邮件标题学号+姓名+论文题目，论文用word或latex编写都可以）课程主要内容•1～3周：超级计算机的发展历史与基本架构原理•4～13周：超级计算机的基本操作与编程方法•14～18周：超级计算机上的并行计算案例（三个）参考资料下载链接：•SupercomputerArchitecture/PaulB.Schneck•ComputerOrganizationandDesign5thEd./DavidA.Petterson•并行计算导论/张林波等•并行计算导论/Grama等课程论文主题和形式•期中论文：超级计算机的过去、现在和未来•对于超级计算机的过去和现在的总结和分析，需要有理有据（要求有参考文献和引用标注）•对于超级计算机的未来的预测，可以充分发挥想象力，但必须有明确的观点和论据•期末论文：用超级计算机求解一个计算问题•计算问题任选，但必须在论文中有清楚的问题描述和分析•要求在课程提供的实验环境中编译和运行相关的求解算法程序（上机环境在期中公布）•要求在论文中介绍该程序中使用的算法的原理和基本步骤•要求把上机过程的主要操作写入论文中•要求论文有对程序的并行计算性能的分析和计算结果的检验第一课：超级计算机硬件架构内容提要：•超级计算机的硬件架构变革•参考资料：SupercomputerArchitecture/PaulB.Schneck全书•当代超级计算机的硬件架构•参考资料：并行计算导论/张林波等第一章计算机的基本组成硬件架构变革（1）•1956年，美国原子能委员会委托IBM构建IBM7030，要求比当时的计算机快100倍•IBM7030于1961年建成使用，主要的创新技术有：•指令并发技术•指令先行控制和数据预取技术硬件架构变革（1.1）•指令并发技术的引入（1961年IBM7030）•在此之前的计算机都是串行地执行指令的：•先取出指令的二进制码，再把二进制码解码成指令类型，再指定数据内存地址并读取相关操作数，再执行运算•指令的并发执行：•使用批量处理技术，批量读取指令，批量解码指令，批量读取操作数，批量执行指令•使用流水线技术，指令读取、指令解码、操作数读取和指令执行并发进行硬件架构变革（1.1）•指令流水线技术硬件架构变革（1.2）指令先行控制单元和数据预取•目的：利用指令执行和数据存取之间的并行性来解决指令读取和解释的延迟问题•原理：•在指令执行前从内存中预取相关数据•暂缓指令的执行，直到相关的数据可用硬件架构变革（2）•1965年Cray在ControlDataCorporation成功建造比IBM7030快三倍的CDC6600•主要的创新技术：•交叉式存储器（interleavedmemory）•功能级别并行•非线性指令调度机制硬件架构变革（2.1）•交叉式存储器•目的：解决中央处理器比内存快1至多个数量级的问题•方法：把内存地址交叉循环分配给多个内存模块（晶片）•效果：连续地址内存存取的效率昀大化，随机地址内存存取的效率提高硬件架构变革（2.1）交叉式存储器对随机内存存取的加速原理•设有m个内存模块，并设随机存取在这些模块的概率均等•对于k次随机存取：•都在同一模块中的概率为!#$%&,当m=8且k=8时大约为0.0012432•在两个不同模块中的概率为(!*!(+*!%,#,%&%,#$%&,当m=8且𝑘=8时大约为0.0304584•在i个不同模块中的概率为(!1!(+1!%2#2%&%2#$%&•都集中在同一个模块的概率很小硬件架构变革（2.2）功能级别并行（functionalparallelism）•原理：允许处理器中不同的功能单元无需等待不存在依赖关系的指令操作完成•常见功能单元：布尔运算单元、分支单元、除法单元、定点加法单元、浮点加法单元、增量单元、乘法单元、移位单元硬件架构变革（2.2）不可功能并行的判断•左上：功能冲突•左下：结果冲突•右上：直接依赖•右下：间接依赖硬件架构变革（2.3）非线性指令调度机制原理•无冲突、无依赖的指令可以同时做•方法：•判断功能单元的可用性•判断结果寄存器的可用性•判断输入操作数的可用性硬件架构变革（3）•1967年IBM360model91•主要创新技术：•数据总线•功能模块自治硬件架构变革（3.1）•数据总线•原理：代替处理器管理存储访问操作，让指令执行和存储访问可以得到较大程度的解耦•总线连接的功能模块：•主存储控制器•并口IO控制器•访问请求栈•存储地址寄存器•位置接受栈•存储数据缓冲硬件架构变革（3.2）•功能单元自治，实现更深层次的并发度：•指令控制单元•定点计算单元•浮点计算单元•主存储控制单元•并口IO单元硬件架构变革（4）•1971年，CDCstar-100•主要创新技术：•向量处理技术硬件架构变革（4.1）向量处理技术：•原理：•利用针对向量的计算指令的访问规则性来降低指令数据存取的延迟•针对向量运算来提高硬件运算效率•缺点：•不能向量化的指令成为性能瓶颈硬件架构变革（5）•1971年，ILLIACIV•主要创新技术：•大规模并行处理硬件架构变革（5.1）大规模并行处理：•用专用网络连接大量相同的处理器（不依赖于向量指令）•每个处理器都是自治的•通过网络来传输和交换数据•需要算法和程序来负责处理器之间的数据传输和交换硬件架构变革(6)•近年来，天河一号、天河二号、美国泰坦等•主要特性：异构计算+超大规模并行处理•异构计算：使用不同类型的处理器来处理不同类型的计算任务•GPU、XEONPHI等加速处理器处理适合于向量化处理的计算任务•CPU处理其它的计算任务•可以理解为向量处理和大规模并行处理的有机结合硬件架构变革（7）硬件变革总结：•关键点是并行计算•指令并发、指令先行控制、数据预取、功能级并行、非线性调度、数据总线和功能单元自治：指令级并行•交叉式存储器：内存访问级并行•向量处理技术：数据级并行•大规模并行处理：任务级并行硬件架构变革（8）•并行计算成为超级计算机的核心技术，其中一个重要原因是摩尔定律•摩尔定律：integratedcircuitresourcesdoubleevery18-24months（集成电路的电子元件集成能力每18到24个月翻一翻）•摩尔定律意味着，单纯靠提高单个处理器的速度（这要靠提高集成电路的集成度）对提升计算机的处理效率作用很有限•除了提高单个处理器的速度外，并行计算也能提升计算机的处理效率•其它原因：内存墙和能量墙等当代超级计算机的硬件架构(1)•并行计算的定义：•目的：•加快求解速度•扩大求解规模•方法：•数据分划：把数据集分划为多个子集•任务分解：将一个应用分解成多个子任务•处理器指派：把数据子集和子任务分配给不同的处理器（计算节点）•协作执行：各个处理器之间相互协同，并行地执行子任务当代超级计算机的硬件架构(1)•两种不同的目的：•加快求解速度：例如串行执行2个星期的计算任务，如果使用100个处理器能够加速50倍，那么执行时间就能缩短为6.72个小时•提高求解规模：例如在单个计算机上，受该计算机内存2G的限制，只能计算某方程10万个网格点的解，但该方程的结果要到1000万个网格点以上才能在应用中使用，这种情况下可以借助并行计算，使用100个计算节点，把问题求解规模扩大100倍当代超级计算机的硬件架构(2)•当代并行机体系结构1（内存外置型）•结点•互联网络•内存当代超级计算机的硬件架构(2)•当代并行机体系结构2（内存内置型）•结点•互联网络•内存当代超级计算机的硬件架构(3)•互联网络拓扑参数•并行机规模:并行机包含的结点总数，或者包含的CPU总数•结点的度:拓扑结构图中，以某个结点为端点的边的条数，称为该结点的度。结点的度表示，存在多少个结点，与该结点有直接的物理连接通道•结点距离:两个结点之间跨越的图的边的昀少条数•网络直径:网络中任意两个结点之间的昀长距离•折半宽度:对分图成相同规模的两个子图(它们的结点数相等，或者至多相差1)时，必须去掉的边的昀少条数当代超级计算机的硬件架构(4)•互联网络速度参数•点对点带宽:图中边对应的两个结点之间相互连接的物理通道的通信带宽•点对点延迟:图中任意两个结点之间的一次零长度消息传递必须花费的时间。延迟与结点间距离相关，其中所有结点之间的昀小延迟称为网络的昀小延迟，所有结点之间的昀大延迟称为网络的昀大延迟•对分带宽:对分图成相同规模的两个子图(它们的结点数相等，或者至多相差1)时，必须去掉的边对应的网络点对点带宽的昀小总和•总通信带宽:所有边对应的网络通信带宽之和当代超级计算机的硬件架构(5)评价一个互联网络的基本准则：固定并行机包含的结点个数，如果•点对点带宽越高•折半宽度越大•网络直径越小•点对点延迟越小则互联网络质量可以说越高当代超级计算机的硬件架构(5)通常情形下，图中任意两个结点之间的点对点延迟L与它们之间的距离m有一个简单的关系式其中，L0为相邻两个结点之间的延迟，δ表示消息跨越一个结点所需的开销。一般的，δL0.当代超级计算机的硬件架构(5)假设任意两个结点之间的点对点延迟为L，点对点带宽为B，则它们之间一次长度为N的消息传递的时间可近似写为:当代超级计算机的硬件架构(6)•静态拓扑结构•如果结点之间存在固定的物理连接，且在程序的执行过程中，结点间的连接方式不变，则称该并行机的互联网络拓扑结构是静态的•常见的结构：阵列(array)、环(ring)、网格(mesh)、网格环(torus，也叫环面)、树(tree)、超立方体(hypercube)、蝶网(butterfly)、Benes网等当代超级计算机的硬件架构(6)一维阵列拓扑：连接条件：当代超级计算机的硬件架构(6)环形拓扑：连接条件：当代超级计算机的硬件架构(6)网格拓扑：连接条件：当代超级计算机的硬件架构(6)•网格环形拓扑：•连接条件：当代超级计算机的硬件架构(6)•二叉树形拓扑：•网络直径为2logP，但折半宽度仅为1，不利于结点之间的大数据量通信当代超级计算机的硬件架构(6)•X-树形拓扑•提高折半宽度当代超级计算机的硬件架构(6)•超立方体拓扑•连接条件：d维超立方体(d=2)包含P2d个结点，结点i的二进制编号为结点i0i1…id-1和结点j0j1…jd-1相互连接的充要条件是：当代超级计算机的硬件架构(6)当代超级计算机的硬件架构(6)•一维阵列拓扑的网络直径为P，折半宽度为1•环形拓扑的网络直径为3,-1，折半宽度为2•d维网格拓扑的网络直径为∑𝑃−18%&9:,折半宽度为𝑚𝑖𝑛?∑(𝑃−B1)D•d维网络环拓扑的网络直径为∑𝑃/2−18%&9:,折半宽度为2𝑚𝑖𝑛∑𝑃−1B当代超级计算机的硬件架构(6)•二叉树形拓扑的网络直径为2𝑙𝑜𝑔𝑃,折半宽度为1•X-树拓扑的网络直径为2𝑙𝑜𝑔𝑃,折半宽度为2𝑙𝑜𝑔𝑃•d维超立方体拓扑的网络直径为𝑙𝑜𝑔𝑃,折半宽度为28%&当代超级计算机的硬件架构(7)•动态拓扑结构•结点之间无固定的物理连接，而是在连接路径的交叉点处用电子开关、路由器或仲裁器等提供动态连接•主要包含单一总线、多层总线、交叉开关、多级互联网络等类型当代超级计算机的硬件架构(7)•单一总线：连接处理器、存储模块和I/O设备等的一组导线和插座，在主设备(处理器)和从设备(存储器)之间传递数据，其特征主要为:•公用总线以分时工作为基础，各处理器模块分时共享总线带宽，即在同一个时钟周期，至多只有一个设备能占有总线;•总线带