信息科学技术学院

博士研究生开题报告大规模集群系统的计算资源与作业管理王韬[e-mail]北京大学信息科学技术学院·网络研究所并行与分布式计算组·网络研究所提纲第一部分：面临着的挑战第二部分：解决问题的若干思路第三部分：研究重点的确立第四部分：博士论文工作计划信息科学技术学院·网络研究所第一部分：面临着的挑战第一部分：面临着的挑战大规模集群中的计算资源与作业管理问题着手前的一些零散思考第二部分：解决问题的若干思路第三部分：研究重点的确立第四部分：博士论文工作计划信息科学技术学院·网络研究所集群系统，计算资源与作业管理集群系统－日益重要的高性能计算环境集群系统：网络技术连接起来的计算机组合，协同工作人们对计算资源的需求远远超过单处理器的发展具有最高性价比的高性能计算环境重要的领域－计算资源与作业管理人们可以制造峰值计算能力每秒几十万亿次的集群系统人们不知道应当如何充分利用这些计算能力不仅仅单个并行程序无法有效利用集群系统，多个程序（作业）同时运行时也很难充分利用集群系统资源性能－搭建集群系统的首要目的：使我们关注“计算资源与作业管理”领域的研究信息科学技术学院·网络研究所本研究的对象：大规模集群面向环境大规模集群系统可能的扩展：网格计算面临着的问题大规模环境，节点数目众多，连接复杂组成系统的各个节点计算能力可能不同可能有物理上的多层次拓扑系统需求：功能与性能最终要能够充分地利用系统的计算能力第一部分：面临挑战信息科学技术学院·网络研究所问题着手前的一些零散思考[1]集中式管理设立一个管理节点，对所有节点进行集中式管理管理节点具有全部系统信息，易于进行调度整个系统实现起来最简单可采用多管理节点相互备份功能，提高效率问题一：大规模系统中的单节点瓶颈所有资源管理工作由单一节点完成，这个节点负担大，且其它节点需等待此节点的处理结果所有信息集中在单一节点，当此节点失效时，系统重新产生管理节点的代价大问题二：大规模系统中的信息滞后通过网络通信，无法及时获取所有节点的资源信息资源管理信息产生后，很难及时通知到所有相关节点第一部分：面临挑战信息科学技术学院·网络研究所问题着手前的一些零散思考[2]完全分布式管理每个节点都含有其它节点的信息减轻了大规模系统中的单节点瓶颈问题注意，在信息获取后，每节点对所有节点信息的整合工作所需工作量与集中式相同，但每节点只需产生自己的调度信息，且不必将此信息传递给其它节点未解决大规模系统中的信息滞后问题引发新的问题网络中消息数目过多获取信息时，集中式算法中只需要N-1条（对）消息，而完全分布式算法需要N*(N-1)条消息，或者N-1条广播当系统规模变大时，由于所得其它节点的信息可能滞后，各节点进行分布式资源管理所需协调工作更加复杂第一部分：面临挑战信息科学技术学院·网络研究所问题着手前的一些零散思考[3]跨网络管理大规模集群系统中的一部分可能处于一个内部子网外界只能访问子网内连接到外部网络的节点解决方法将子网内连接到外部网络的节点作为“代理”，系统管理“代理”，“代理”管理内网于是，如何有效地将这种“代理”纳入到整体模型中就成为一个与性能相关的问题第一部分：面临挑战信息科学技术学院·网络研究所问题着手前的一些零散思考[4]信息的获取与处理系统需要什么样的信息，才能够有效地进行下一步的资源与作业管理工作信息越丰富，越有助于资源管理的精确性信息越丰富，各节点负担越大、通过网络传输的数据量越大、资源管理的所需算法越复杂各节点的存在信息与资源信息定时检测：心跳处理器、内存、网络……物理资源信息和可用资源信息处理节点的动态加入与退出第一部分：面临挑战信息科学技术学院·网络研究所第二部分：解决问题的若干思路第一部分：面临着的挑战第二部分：解决问题的若干思路直观想法：分层次进行资源管理理论方面的三大问题综合考虑：猜想中的信息团模型第三部分：研究重点的确立第四部分：博士论文工作计划信息科学技术学院·网络研究所直观想法：分层次进行资源管理思想根源一台计算机的资源管理，应该对离它越近的计算机影响越大，因此可以将相隔近的计算机组成小系统，小系统之间再管理在不同网络的两个计算机系统之间的影响应当较小试图解决在大规模集群系统中的若干问题单节点瓶颈管理消息过多、管理复杂信息滞后、跨网络管理第二部分：若干思路信息科学技术学院·网络研究所对于资源的分层次管理思想系统的层次化分解与组合根据性能及网络情况，将系统分为若干子系统每个子系统内部进行管理，再将子系统作为整体进行管理可以根据需要，进行子系统分解与组合对层次化管理思想的分析它只是一个指导思想：“层次化的管理原则”人类的经验表明，层次化的管理原则是正确的关键在于，如何将这个思想原则，对应成实际的模型与系统第二部分：若干思路信息科学技术学院·网络研究所层次化管理思想的两个方面理论与实现理论方面：这种分层次进行资源管理相关的资源、作业模型是什么、如何交互（管理模型）实现方面：如何在大规模的实际集群系统上高效实现分层次进行资源管理实现方面需要理论方面进行指导理论方面需要实现方面作为表现极大的挑战性世界上尚未出现令人信服的模型世界上更未出现完全高效的系统这正是我们的机遇，同时也是严峻的挑战本报告中主要讨论理论方面最后部分将简单介绍实现方面的一些考虑第二部分：若干思路信息科学技术学院·网络研究所理论方面的三大问题大规模集群系统的机器模型是什么哪些计算资源是重要的；如何描述；性能参数是什么这些计算资源在大规模系统中的逻辑拓扑是什么能有效利用这些计算资源的任务模型是什么如何描述任务的需求如何动态预知任务对资源的需求情况层次化管理的逻辑模型和性能模型是什么如何根据给定的机器描述与作业/任务描述，得到最适合的管理方式，并指导下一步的调度策略及算法如何根据逻辑模型得到的结论，给出性能参数以及对性能的预测与评价只要解决了这三个问题，就解决了理论方面的问题第二部分：若干思路信息科学技术学院·网络研究所对理论方面的分析一：机器模型机器模型计算资源逻辑拓扑任务模型管理模型第二部分：若干思路信息科学技术学院·网络研究所机器模型之计算资源重要的计算资源处理器、内存、网络，……重要的信息资源静态信息：各计算机计算资源的固有性质资源动态信息：各计算机的计算资源的当前可用情况信息表述多元组表示：C,M,N统一数值表示尚需更加深入的认识需要确定信息表述的方法需要给出性能参数与性能公式第二部分：若干思路信息科学技术学院·网络研究所机器模型之逻辑拓扑层次化树状结构－系统节点树树中的每个节点，代表一个子系统父节点代表其全部子节点每个父节点只需对其子节点进行资源管理全部叶子节点是系统的实际物理节点引入概念：信息点与信息负责点信息点：在子系统内，代表一个子节点的计算机信息负责点：在子系统内含有整个子系统信息的计算机、对外代表整个子系统可以适应大规模集群系统子系统的构造参考实际网络结构对于N个节点的系统，层数为O(logN)动态可扩展性可将不同网络的系统组织成更大系统、甚至可扩展到Grid系统需要考虑节点的动态加入与退出机制第二部分：若干思路信息科学技术学院·网络研究所关于系统层次划分的思考需要一个指导方法，使系统可能达到最大服务能力适应层次化管理思想参考实际网络结构，在各种实际系统中指导如何划分层次决定每一层次需要什么样的计算资源信息（以及负载信息）几点在大规模集群系统中的具体目标避免单节点瓶颈产生较少的管理消息使管理尽量简单化，尽量不影响计算机本身计算避免信息滞后问题实现跨网络管理处理节点的动态加入与退出两点猜想各层所需信息不同：似乎是显然的最底层应小规模且对等第二部分：若干思路信息科学技术学院·网络研究所猜想：最底层应小规模且对等相对集中式管理的优势每台计算机都有子系统全部信息利于避免单节点失效资源管理时能够更有效地统筹全局进行资源管理时无需等待主节点处理结果可以随意选择一台计算机作为信息负责点，如最轻负载可避免传统分布式处理方法的不足各计算机一定在同一子网中，可利用高效组播获取信息当计算机数目少的时候，信息滞后问题可忽略，可认为所有信息都即时准确，故可采用相对简单的算法实现分布式资源管理猜想小结最底层计算机数目应较少（例如10个），形成信息团第二部分：若干思路信息科学技术学院·网络研究所机器模型逻辑拓扑小结基本描述层次化树状结构可以适应大规模集群系统动态可扩展性两点猜想：各层所需信息不同、最底层应小规模且对等尚需工作上述描述仅仅是理论的前身，需要证明与细化非最底层应当如何组织尚未清楚图示：一种可能的系统逻辑图第二部分：若干思路信息科学技术学院·网络研究所学界对机器模型的相关研究关于计算资源的表示从传统的只考虑处理器信息，到考虑内存、网络、IPC资源等信息越来越注重实际系统：开始考虑多层次、异构结构等实际问题一个面向层次化结构的研究F.D.Sacerdoti,…,D.E.Culler,“WideAreaClusterMonitoringwithGanglia”,ProcIEEECluster2003Conference偶然发现此文章关于机器模型方面与我们的猜想很相象，除了“最底层小规模且对等”；间接坚定了我们的信心没有解决每个层次应该提供什么样的信息，只是同样阐述“更高层提供更综合的信息”的原则没有提及每个层次的系统应当如何组织的问题另一个相关研究：从网格信息提供的角度考虑问题第二部分：若干思路信息科学技术学院·网络研究所对理论方面的分析二：任务模型机器模型任务模型任务描述需求预知管理模型第二部分：若干思路信息科学技术学院·网络研究所考察学界现有的任务模型[1]最直观的任务描述方法任务所需要的处理器个数任务在某个处理器上的执行时间任务之间的执行序关系目前任务描述方法的不足多数研究假定每个任务在每个处理器上的执行时间已知、任务之间的通信时间也已知有些研究假定任务工作量相等，有些假定任务间无关系顶尖的期刊中也有很多这样的情况（如IEEETPDS，2004.4.,SchedulingStrategiesforMaster-SlaveTaskingonHeterogeneousProcessorPlatforms）第二部分：若干思路信息科学技术学院·网络研究所考察学界现有的任务模型[2]近年来开始考虑切合实际的任务模型着眼点转向任务对资源的需求最初只考虑对处理器时间的需求，后来开始考虑内存、I/O等需求GlobusToolkit3中使用RSL2语言（ResourceSpecificationLanguage）来沟通任务对资源的需求：一种XML进一步思考：要求任务提供对资源的需求是否合理？任务能否提供准确的资源需求任务在运行时的资源需求是否是不变量最近开始出现如何动态对任务需求进行预知的研究不要求任务在运行前提供准确的资源需求运行时动态处理第二部分：若干思路信息科学技术学院·网络研究所任务模型之任务描述对资源需求的描述对不同资源分别处理：将对各种资源的需求描述为一个N元组，按照顺序进行配对，如处理器数目、处理器时间，内存，I/O，IPC；N元组的顺序也是一个考虑因素统一参数：将对不同资源的需求通过某些算法统一归结为一个参数；如统一成处理器利用率等精确度与简单性的权衡任务之间关系的描述已有经验：LilyTask并行模型中的任务关系待研究问题提供什么样的资源参数供任务进行描述第二部分：若干思路信息科学技术学院·网络研究所任务模型之动态需求预知感知任务运行时对资源的需求利用系统调用，可以得知任务对CPU、内存等计算资源的使用情况使用资源预