信息科学技术学院

博士研究生开题报告大规模集群系统的计算资源与作业管理,王韬wangtao北京大学信息科学技术学院网络研究所并行与分布式计算组,2005.3.21,提纲,第一部分：面临着的挑战第二部分：解决问题的若干思路第三部分：研究重点的确立第四部分：博士论文工作计划,第一部分：面临着的挑战,第一部分：面临着的挑战大规模集群中的计算资源与作业管理问题着手前的一些零散思考第二部分：解决问题的若干思路第三部分：研究重点的确立第四部分：博士论文工作计划,集群系统，计算资源与作业管理,集群系统日益重要的高性能计算环境集群系统：网络技术连接起来的计算机组合，协同工作人们对计算资源的需求远远超过单处理器的发展具有最高性价比的高性能计算环境重要的领域计算资源与作业管理人们可以制造峰值计算能力每秒几十万亿次的集群系统人们不知道应当如何充分利用这些计算能力不仅仅单个并行程序无法有效利用集群系统，多个程序（作业）同时运行时也很难充分利用集群系统资源性能搭建集群系统的首要目的：使我们关注“计算资源与作业管理”领域的研究,本研究的对象：大规模集群,面向环境大规模集群系统可能的扩展：网格计算面临着的问题大规模环境，节点数目众多，连接复杂组成系统的各个节点计算能力可能不同可能有物理上的多层次拓扑系统需求：功能与性能最终要能够充分地利用系统的计算能力,第一部分：面临挑战,问题着手前的一些零散思考1,集中式管理设立一个管理节点，对所有节点进行集中式管理管理节点具有全部系统信息，易于进行调度整个系统实现起来最简单可采用多管理节点相互备份功能，提高效率问题一：大规模系统中的单节点瓶颈所有资源管理工作由单一节点完成，这个节点负担大，且其它节点需等待此节点的处理结果所有信息集中在单一节点，当此节点失效时，系统重新产生管理节点的代价大问题二：大规模系统中的信息滞后通过网络通信，无法及时获取所有节点的资源信息资源管理信息产生后，很难及时通知到所有相关节点,第一部分：面临挑战,问题着手前的一些零散思考2,完全分布式管理每个节点都含有其它节点的信息减轻了大规模系统中的单节点瓶颈问题注意，在信息获取后，每节点对所有节点信息的整合工作所需工作量与集中式相同，但每节点只需产生自己的调度信息，且不必将此信息传递给其它节点未解决大规模系统中的信息滞后问题引发新的问题网络中消息数目过多获取信息时，集中式算法中只需要N-1条（对）消息，而完全分布式算法需要N*(N-1)条消息，或者N-1条广播当系统规模变大时，由于所得其它节点的信息可能滞后，各节点进行分布式资源管理所需协调工作更加复杂,第一部分：面临挑战,问题着手前的一些零散思考3,跨网络管理大规模集群系统中的一部分可能处于一个内部子网外界只能访问子网内连接到外部网络的节点解决方法将子网内连接到外部网络的节点作为“代理”，系统管理“代理”，“代理”管理内网于是，如何有效地将这种“代理”纳入到整体模型中就成为一个与性能相关的问题,第一部分：面临挑战,问题着手前的一些零散思考4,信息的获取与处理系统需要什么样的信息，才能够有效地进行下一步的资源与作业管理工作信息越丰富，越有助于资源管理的精确性信息越丰富，各节点负担越大、通过网络传输的数据量越大、资源管理的所需算法越复杂各节点的存在信息与资源信息定时检测：心跳处理器、内存、网络物理资源信息和可用资源信息处理节点的动态加入与退出,第一部分：面临挑战,第二部分：解决问题的若干思路,第一部分：面临着的挑战第二部分：解决问题的若干思路直观想法：分层次进行资源管理理论方面的三大问题综合考虑：猜想中的信息团模型第三部分：研究重点的确立第四部分：博士论文工作计划,直观想法：分层次进行资源管理,思想根源一台计算机的资源管理，应该对离它越近的计算机影响越大，因此可以将相隔近的计算机组成小系统，小系统之间再管理在不同网络的两个计算机系统之间的影响应当较小试图解决在大规模集群系统中的若干问题单节点瓶颈管理消息过多、管理复杂信息滞后、跨网络管理,第二部分：若干思路,对于资源的分层次管理思想,系统的层次化分解与组合根据性能及网络情况，将系统分为若干子系统每个子系统内部进行管理，再将子系统作为整体进行管理可以根据需要，进行子系统分解与组合对层次化管理思想的分析它只是一个指导思想：“层次化的管理原则”人类的经验表明，层次化的管理原则是正确的关键在于，如何将这个思想原则，对应成实际的模型与系统,第二部分：若干思路,层次化管理思想的两个方面,理论与实现理论方面：这种分层次进行资源管理相关的资源、作业模型是什么、如何交互（管理模型）实现方面：如何在大规模的实际集群系统上高效实现分层次进行资源管理实现方面需要理论方面进行指导理论方面需要实现方面作为表现极大的挑战性世界上尚未出现令人信服的模型世界上更未出现完全高效的系统这正是我们的机遇，同时也是严峻的挑战本报告中主要讨论理论方面最后部分将简单介绍实现方面的一些考虑,第二部分：若干思路,理论方面的三大问题,大规模集群系统的机器模型是什么哪些计算资源是重要的；如何描述；性能参数是什么这些计算资源在大规模系统中的逻辑拓扑是什么能有效利用这些计算资源的任务模型是什么如何描述任务的需求如何动态预知任务对资源的需求情况层次化管理的逻辑模型和性能模型是什么如何根据给定的机器描述与作业/任务描述，得到最适合的管理方式，并指导下一步的调度策略及算法如何根据逻辑模型得到的结论，给出性能参数以及对性能的预测与评价,只要解决了这三个问题，就解决了理论方面的问题,第二部分：若干思路,对理论方面的分析一：机器模型,机器模型计算资源逻辑拓扑任务模型管理模型,第二部分：若干思路,机器模型之计算资源,重要的计算资源处理器、内存、网络，重要的信息资源静态信息：各计算机计算资源的固有性质资源动态信息：各计算机的计算资源的当前可用情况信息表述多元组表示：统一数值表示尚需更加深入的认识需要确定信息表述的方法需要给出性能参数与性能公式,第二部分：若干思路,机器模型之逻辑拓扑,层次化树状结构系统节点树树中的每个节点，代表一个子系统父节点代表其全部子节点每个父节点只需对其子节点进行资源管理全部叶子节点是系统的实际物理节点引入概念：信息点与信息负责点信息点：在子系统内，代表一个子节点的计算机信息负责点：在子系统内含有整个子系统信息的计算机、对外代表整个子系统可以适应大规模集群系统子系统的构造参考实际网络结构对于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元组，按照顺序进行配对，如；N元组的顺序也是一个考虑因素统一参数：将对不同资源的需求通过某些算法统一归结为一个参数；如统一成处理器利用率等精确度与简单性的权衡任务之间关系的描述已有经验：LilyTask并行模型中的任务关系待研究问题提供什么样的资源参数供任务进行描述,第二部分：若干思路,任务模型之动态需求预知,感知任务运行时对资源的需求利用系统调用，可以得知任务对CPU、内存等计算资源的使用情况使用资源预期函数来定量地预知资源需求系统定时或者不定时地得到任务的当时针对某个资源的使用情况利用刚刚得到的当前资源使用情况UCUR和上次的资源使用情况UOLD，计算预期的资源需求UEXP例如使用平滑函数进行预期：UEXP=aUCUR+(1-a)UOLD待研究问题监控哪些资源；采用什么资源预期函数,第二部分：若干思路,对理论方面的分析三：管理模型,机器模型任务模型管理模型逻辑模型性能模型,第二部分：若干思路,管理模型之逻辑模型,基本策略完全分时共享会严重影响大规模计算的性能因此采用具有分时性质的分区共享重要问题对于机器模型中的不同的子系统内部，应当采用什么样的调度框架，达到最短平均响应时间或者最大吞吐率各个子系统之间应当如何交互、如何协作处理任务，能够实现系统服务能力最大化？,第二部分：若干思路,对逻辑模型重要问题的思考,子系统内部的调度框架显然，不同层次的各个子系统的调度策略应当不同可以提供若干有效的调度策略供子系统选择对每个子系统，需要找到在它内部最有效的调度策略可能最有效的调度策略与待处理的任务集相关也许每个子系统中最有效的调度策略不止一个需要进一步的仔细研究面向子系统的管理猜想：信息负责点分层连动制在子系统内部，信息点向信息负责点负责信息负责点代表自己所在的子系统向上层系统负责子系统首先在子系统内部进行任务处理，超出处理能力时通过信息负责点提交到上层系统处理有很多具体细节需要思考，如信息负责点如何形成等,第二部分：若干思路,子系统处理任务过程1,第二部分：若干思路,TAll,1、子系统X首先把任务TAll在X内部面向NXi进行处理,X,子系统处理任务过程2,第二部分：若干思路,TIM,2、当X能力不足时，通过CX将无法完成的部分任务TIM提交到U,U,T1,T2,子系统处理任务过程3,第二部分：若干思路,3、U把TIM面向NUi进行，选定一个（或多个）信息点，例如NUz，即CZ,T1,T2,TIM,U,子系统处理任务过程4,第二部分：若干思路,4、Z把通过CZ得到的TIM在Z内部面向NZi进行处理,T1,T2,Z,TIM,子系统处理任务的最终结果,第二部分：若干思路,TIM1,TIM2,T1,T2,现在，X和Z都有任务在运行,管理逻辑模型小结,两个重要问题对于子系统内部调度框架的思考信息负责点分层连动制似乎都是“显而易见”的想法但是把整个理论完善起来并不容易关键在于能否根据此理论实现高效的实用系统尚属初步的研究阶段，具有很大的研究空间尚需工作模型的具体细节，如一个任务所需处理器个数超过任何一个最底层子系统怎么办？需要证明，将猜想转变为理论结合管理性能模型进一步优化实现高效的实用系统,第二部分：若干思路,管理模型之性能模型,尚未开始研究必须在得出基本逻辑模型后才可进行将与逻辑模型交互发展得到基本性能模型后，结合实测数据，指导逻辑模型的优化优化后的逻辑模型，得到优化的性能模型,第二部分：若干思路,学界对管理模型的相关研究,还没有一个针对大规模的，可能具有计算能力异构性质的、多层并行性的集群系统的完善的逻辑模型和性能模型考察IEEETPDS近5年的文章所有的模型都缺少理论上的完善面向实际系统的资源管理和调度策略都是基于自提出的启发式算法，只是用“实验数据”来说明问题基本没有见到完善的、统一的多层次管理模型可能的多层次管理：网格系统GlobusTookit3GRAM,第二部分：若干思路,综合考虑,理论研究机器模型、任务模型、管理模型集中体现：猜想中的信息团模型以信息团为基础，分层次连动管理,第二部分：若干思路,信息团模型的自然简单描述,基础描述参考网络自然拓扑等情况，最底层组成多个子系统，每个由少量（如10台）计算机构成对等结构，形成信息团这些信息团子系统可以继续组织成多个层次，各个层次所需信息的空间粒度及时间粒度不同各子系统间使用分层连动制进行交互基本的任务管理策略：具有分时性质的分区共享主要优势可在大规模集群系统中充分利用系统计算资源层次化管理，可将多个不同网络的系统组织成更大系统，适应Grid环境,第二部分：若干思路,对信息团模型形式化的初步考虑,传统问题给定资源集R、任务集T存在调度方法D(R,T)，将T分配到R上执行分配时间为TS，完成时间为TU求D(R,T)，使任一的R、T，TS+TU为最小值本身是一个NP难问题我们问题的特殊点实际的大规模集群系统R规模大，且描述R复杂T中的任一任务，所需资源与所用时间可能事先未知对应理论模型的三个部分机器模型资源集任务模型任务集管理模型调度方法点击此处进入详细讨论,第二部分：若干思路,第三部分：研究重点的确立,第一部分：面临着的挑战第二部分：解决问题的若干思路第三部分：研究重点的确立已有的理论基础与实际系统主要研究点的选择第四部分：博士论文工作计划,已有的相关理论基础与实际系统,关于理论模型LilyTask并行计算模型描述任务关系图，实现任务关系驱动关于计算资源与作业管理集群系统资源获取LilyCRM集群系统信息查看LilyView集群作业管理系统LilyJM关于并行程序运行环境任务并行语言与运行时库系统LilyTask有关任务并行的认识、实际系统实现的经验已有6篇相关论文发表/被接收，其中1篇SCI、ISTP索引，1篇EI索引，1篇计算机学报,第三部分：研究重点,集群系统资源获取LilyCRM,在集群系统中获取节点信息可以获取节点的计算资源信息和进程信息节点可以动态加入、退出集群系统同时支持Linux、Windows的节点已经实现基本的分层次信息获取通过标准/proc文件系统将信息提供给使用者由硕士研究生沈坚实际完成,第三部分：研究重点,集群系统资源查看LilyView,可看作LilyCRM的一个客户端实际完成者：本科生段孟成,第三部分：研究重点,集群作业管理LilyJM,在集群上的作业管理系统集群上直接面向最终用户的系统用户提交脚本，脚本中含有多个作业以作业为单位，在集群系统中进行调度现有实现提供对作业现有状态、输出结果的查询系统可根据节点资源情况（CPU负载）进行作业调度支持集群中动态加入的节点可以实现作业级容错已经在并行组内部和北京大学科学与工程计算中心试用由硕士研究生刘敏实际完成,第三部分：研究重点,对潜在研究点的分析,选取主要研究点的原则意义、难度、深度、可行性机器模型：计算资源、逻辑拓扑已经有一些基本想法（层次化树状结构）能够采取拿来主义；可以安排给硕士研究生进行任务模型：任务描述、需求预知学界已经开始进行较深入的研究容易借鉴别人的成果；同样可以安排给硕士研究生进行管理模型：逻辑模型、性能模型处于核心模型：此方面问题的解决，意味着能够对大规模集群系统计算资源的高效利用难度较大，需要深入细致的理论分析、猜想与试验学界尚未有完全令人信服的，针对大规模集群系统的完善模型可行性：前面的思考、已有的基础与自己的信心,第三部分：研究重点,确定下来的主要研究点,管理模型之逻辑模型各子系统内部的任务调度方法信息负责点分层连动制尚需工作：具体细节与证明尚需工作：结合性能模型进一步优化管理模型之性能模型必要的研究，与管理逻辑模型交互发展必须在得出基本逻辑模型后才可进行,第三部分：研究重点,非主要研究点的工作安排,非主要研究点机器模型：计算资源、逻辑拓扑任务模型：任务描述、需求预知也需要进行深入研究并非不重要，而是没有被选择作为博士论文中的具体研究点已经进行了初步的思考，形成了研究基础安排硕士研究生进行下一步的研究工作继续负责总体构思与指导工作,第三部分：研究重点,第四部分：博士论文工作计划,第一部分：面临着的挑战第二部分：解决问题的若干思路第三部分：研究重点的确立第四部分：博士论文工作计划工作内容工作安排,预期成果表现,直接表现：理论模型中的管理模型完善并证明管理逻辑模型形成精细的管理性能模型成为如何充分有效利用大规模集群系统的核心理论依据间接表现：理论中其它部分理论模型中机器模型的研究（沈坚，硕士研究生）理论模型中任务模型的研究（刘敏，硕士研究生）实际系统高效的，性能达到国际前列的实际管理系统，并在ChinaGrid北京大学主节点上提供稳定的高质量服务最大效率地使用集群系统，达到最高的经济效益成为网格计算的基础,第四部分：工作计划,待解决的具体问题,针对博士论文主要研究点的问题在不同子系统中对于任务的调度框架是什么如何形成各子系统的信息负责点子系统之间（父子、兄弟）之间应当如何交互工作管理性能模型是什么：框架、公式与参数其它需要同时解决的问题如何刻画系统的计算资源；有效形成计算资源逻辑拓扑如何描述任务；预测任务的使用情况一些具体技术问题，例如如何实现对任务可占用的资源使用率的精确控制与“拿来主义”的接口，如对于硬件资源的监控与报警（CPU温度、风扇转速等）的结合需要并行组的共同努力,第四部分：工作计划,对于理论的研究方法与路线,提出逻辑模型猜想需要得到系统内调度方法、系统间联系方式在理论分析的基础上，提出模型假设（包括参数），并试验验证，必要时反复此过程实验验证逻辑模型并进行优化与其它系统进行性能对比；调整、优化逻辑模型得出基本性能模型并验证根据调整优化后的逻辑模型，得到基本性能模型进行实验验证、调整性能模型最终优化逻辑模型、性能模型根据初步得到的性能模型的指导，得出最终的逻辑模型根据最终的逻辑模型，得到最终的性能模型完成证明,第四部分：工作计划,进度安排,先期阶段：一年时间，已完成初步探索、工作基础第一阶段：进一步探讨2005年3月2005年5月（3个月）完成更加深入的调研，初步提出理论逻辑模型初步实现原型系统，并在ChinaGrid北大主节点上调试通过第二阶段：深入研究2005年6月2005年8月（3个月）得到实验数据、进一步细化理论逻辑模型得到基本性能模型优化实用系统，在ChinaGrid北大主节点上提供稳定服务撰写一篇投稿论文第三阶段：总结收获2005年9月-2005年11月（3个月）完成最终的逻辑模型、性能模型；完成模型证明完成博士论文,第四部分：工作计划,附：主要的科研项目,已结束的科研项目国家自然科学基金重点项目并行程序设计关键技术（69933020，人民币90万元，国家拨款），北京大学子项目；2000.12003.12（结题检查“优”）；协助导师具体负责IBM共享大学研究（SUR）项目，北京大学课题“北京大学网格建设”；2003.22005.1；协助导师具体负责IntelHPC03项目，北京大学课题TaskSchedulingMechanism&ProgramSupportingEnvironmentforIntelItanium2SMPClusterSystem（PONo.4507076701），3万美元（来自Intel公司）；2003.112004.10；实际负责人正在进行的科研项目IntelParallelCacheSimulator项目（PONo.4507105230），2万美元（来自Intel公司）；2004.72005.6；实际负责人国家自然科学基金重点项目网络计算环境综合试验平台，北京大学子课题网络计算资源服务中间件（90412010，人民币150万元，国家拨款）；2004.72008.6；主要参加人,附：文章与专利,第一作者文章王韬、刘敏，“LilyTask任务并行程序设计框架与范例”，高性能计算技术，2004年第3期（6月）TaoWang,NanDi,JianShen,YanTang,“LilyTaskProgrammingModelandItsImplementationsonSMP&Cluster”,Proc.IASTEDInternationalConferenceonParallelandDistributedComputingandSystems2003,pp.301-306(PDCS2003,MarineDelRey,USA.Nov,2003)EIIndexedTaoWang,XiaomingLi,“LilyTaskProgramFrameworkAnApproachtoTaskParallelProgrammingParadigm”,InternationalConferenceonParallelAlgorithmsandComputingEnvironments2003(ICPACE2003,HongKong,Oct,2003)NotpublishedinpublicTaoWang,XiaomingLi,“LilyTask-ATask-OrientedParallelComputationModel”,X.Zhouetal.(Eds.):APPT2003,LNCS2834,pp.157-161,2003,Springer-VerlagBerlinheidelberg2003SCI,ISTPIndexed王韬、李晓明，“SMPCluster:如何开发两级并行”，计算机工程与科学，Vol.24NO.4，2002非第一作者文章邸楠，王韬，李晓明，“LilyTask任务并行环境中基于任务关系的初始任务分配算法”，接收在计算机学报沈坚，王韬，李晓明，“任务并行程序设计模型LilyTask在分布存储环境下的设计与实现”，接收在计算机工程与科学谢欣、王韬、李晓明，“一种支持动态网站生成的模型与系统”，计算机应用研究，2004年第四期王冲、王韬、李晓明，“多媒体网站拆分与重现：Java的一种应用”，全国第五届Java技术及应用学术交流会，2002.9，北京LILong,LIXiaoming,WANGTao,“APARALLELI/OMETHODFORSMPCLUSTERS”,IASTEDInternationalConferenceonNetworks,ParallelandDistributedProcessing,andApplications(NPDPA2002,Tsukuba,Japan.Oct,2002)发明专利01141419.7，多媒体网站的拆分及重现方法，李晓明、王冲、王韬；已授权,结束,谢谢大家欢迎提问,王韬wangtao,附录：作业管理系统示例,典型的作业管理系统PBS系列商业版本PBSPro的特性简介免费版本OpenPBS的局限,典型的作业管理系统PBS系列,总体情况最初由NASA在20世纪90年代早期开发目的是面向集群系统提供有效的作业管理服务分化为免费的OpenPBS和商业化的PBSPro免费版本被广为使用大多数HPC集成厂商为用户提供OpenPBS作为作业管理部件业界最著名的集群系统管理软件Scali集成了OpenPBS,商业版本PBSPro的主要特性,图形化和命令行用户界面提交批处理和交互作业查询作业、队列以及系统状态跟踪作业的进展作业优先级与相关性用户可以指定作业的优先级用户可以指定批处理作业之间的关系，包括：执行顺序、同步，以及依照其它作业执行的成功与否来决定是否运行自动的负载平衡集群调度系统提供多种负载平衡策略根据硬件配置、资源可用情况以及键盘动作等情况采取行动错误处理和冗余可以被配置成容错模式当主服务器失效时，从服务器可以顶替正在运行的作业，以及队列中的作业不会被影响,本页资料来自：,商业版本PBSPro的其它特性,实现安全和访问控制作业记帐全面的应用编程接口不同系统间的用户名称映射利用桌面计算机空闲处理器时间支持广泛的运行平台，包括SMP集群分布式集群，甚至可以在广域网上资源预留自动文件传输并行作业，可使用MPI、MPL、PVM和HPF等计算网格，支持GlobusToolkit,本页资料来自：,免费版本OpenPBS的局限,使用性的局限只支持类Unix系统不支持SMP集群系统只支持较小规模的集群环境没有完善的使用文档功能性的局限只有轮询的负载平衡策略不支持抢先式作业调度不支持利用桌面计算机空闲时间不支持资源预留不支持容错不支持网格计算,本页资料来自：/product_comparison.html,理论模型：LilyTask并行计算模型,处理任务并行的基础模型描述任务关系图实现任务关系驱动有效地描述并实现多个问题协同工作,LilyTask计算模型中的基本概念（1）,任务：解决一个问题所需要完成的一段工作，这个工作具有如下两个性质：只有在这段工作启动前能够接收其它工作传递的数据只有在这段工作完成后才能够向其它工作传递数据任务间关系：一个具有指向性的有序四元组从“源任务”指向“目标任务”，标志着源任务完成时，需要将指定的源任务数据，放入目标任务的指定数据位置中一条关系描述的数据传递（可以为空）完成后，标志着这条关系的完成同时表达着任务启动条件：一个任务可以启动，当且仅当所有指向它的任务间关系已经完成,LilyTask计算模型中的基本概念（2）,任务组，简化任务间关系的描述形式任务关系图、任务关系驱动,LilyTask计算模型的命题,命题描述任务关系图，实现任务关系驱动的LilyTask计算模型能够有效地描述并实现多个子问题协同工作基础认定一个问题可以分解为多个子问题（也许递归继续分解），这些子问题协同工作，共同完成待解决问题问题之间可以进行数据传递除了最初工作的问题，一个问题必须由另外一个问题通知运行，我们将这个过程称作“激活”；我们假定最初工作的问题也是由一个特殊问题“系统”激活；因此全部问题都需要被“激活”,LilyTask计算模型的正确性（1）,引理1：一个问题可以分解成一个或者多个子问题，每个子问题内部串行工作证明：如果某个子问题内部不是串行工作，那么必可被继续分解成若干子问题，直到串行工作为止引理2：任一内部串行工作的问题，如果它与其它问题交换数据，那么它可以划分成一个或者多个具有串行关系的子问题，每个子问题只在工作开始时接收其它问题传递过来的数据，工作结束时向其它问题传递数据，运行过程中其数据不受其它问题影响证明：1）任何交换数据，都可分为接受数据、发送数据两种不同操作，这两个操作是阻塞的；其它操作不会影响问题中的数据2）问题内部串行工作，所以”接受数据”、”发送数据”、”其它工作”必不在同一时刻，且互不影响；3）我们可以用“其它工作work”、“接受数据recv”、“发送数据send”将此问题划分为几个工作块，即work、recv、send的一个排列4）我们在这个排列中插入若干特殊的recv和send，这些特殊的recv和send都是空操作；使原有排列变为一个规则排列recvworksend5）把规则排列中的每个recvworksend块定义为一个子问题，这些子问题串行工作，完成原有问题6）由（1）（2）可知，work过程中数据不受其它问题影响,LilyTask计算模型的正确性（2）,引理3：任一内部串行工作的问题，如果它激活其它N个问题，那么它可以划分成至多N1个具有串行执行关系的子问题，其它N个问题只能被某个子问题运行结束时激活证明：类似引理2的证明，我们将问题划分为“工作work”、“激活invoke”两种不同的操作类，每个invoke类包含相邻的若干激活操作；最后我们得到一个排序；如果第一个操作是invoke类，就在前面插入一个空操作的work类；从第一个排序开始，将每个相邻的workinvoke定义为一个子问题；由于最多有N个invoke类，考虑到最后一个work也许没有invoke与其对应，那么最多就可划分为最多N+1个具有串行执行关系的子问题，每个子问题结束的时候，激活其它问题（最后一个子问题也许不激活其它问题）,LilyTask计算模型的正确性（3）,引理4：任何问题，都可以分解成若干子问题协同工作，每个子问题内部串行工作，只在启动前前接收其它子问题传递过来的数据，结束后向其它子问题传递数据，运行过程中其数据不受其它子问题影响；我们将这种子问题，称作“任务”证明：由引理（1）（2）得证引理5：如果一个任务Ta要向任务Tb传递数据，Tb一定应该在Ta结束后开始；如果我们定义关系，说明Ta要向Tb传递数据，那么这个关系从时序角度讲具有反自反性、传递性与反对称性，即关系是拟序关系证明：1）按照任务的定义，任务的过程recvworksend是串行的；Tb在开始的时候需要Ta的数据，而Ta只有在结束的时候才能够发送数据，因此Ta没有结束的时候，Tb无法得到Ta的数据，也就无法运行；所以Tb一定应该在Ta结束后开始2）就一次运行而言，Ta无法在自己结束后开始，所以TaTa为假，因此Ta具有反自反性3）设TaTb,TbTc，因为时间顺序性，TaTc，于是具有传递性4）由于是反自反、传递的，因此是反对称的引理6：如果一个任务Ta激活任务Tb，我们定义关系激活=，那么这个关系=从时序角度讲具有反自反性、传递性与反对称性，即=关系是拟序关系证明：1）激活是一个简单的单向，具有时间顺序性的关系2）参照引理4可证,LilyTask计算模型的正确性（4）,定理1：任何任务，都可以分解成若干子任务,这些子任务内部串行执行，且只有在子任务开始的时候接收数据、子任务结束的时候发送数据；如果把这些子任务的每次运行作为顶点，把子任务之间的数据传递作为有向边，就构成了一个有向无环图DAG任务数据传递图证明：1）由引理4，且由于基础的数据传递是单向的，因此任务的每次运行与数据传递构成了有向图2）如果有向图存在一个环，设这个环的顶点为T1T2TpT1，由引理5可知，具有传递性，反对称性，矛盾；因此有向图无环定理2：任何任务，都可以分解成若干子任务,这些子任务内部串行执行，且只有在子任务开始的时候接收数据、子任务结束的时候发送数据，在子任务结束的时候可能激活其它任务；如果把这些子任务的每次运行作为顶点，把子任务之间的数据传递作为有向边，仍然构成一个DAG任务数据传递图；如果把子任务之间的激活关系作为有向边，就构成了另一个有向无环图DAG任务运行激活图证明：1）按照引理3，可以将定理1得到的任何任务，串行划分成若干子任务，只有在每个子任务结束的时候激活其它任务2）对于（1）中划分成的若干子任务，只有在每个子任务结束的时候才能激活其它任务；每一个任务的子任务之间都存在数据传递，且只在子任务运行前从上一个子任务处接受数据、运行后向下一个子任务发送数据；按照定理1，所有的任务的子任务及其数据传递关系可以构成一个任务数据传递图3）按照引理6，把子任务之间的激活关系作为有向边，就构成了另一个有向无环图DAG任务运行激活图,LilyTask计算模型的正确性（5）,定理3：任何任务，都可以分解成若干子任务和若干任务间关系，这些子任务内部串行执行，且不与其它任务交换数据；如果把这些子任务的每次运行作为顶点，把这些任务间关系Rt作为有向边，就构成了一个有向无环图DAG任务关系图。任务关系图可以同时表达任务数据传递图和任务运行激活图证明：1）首先按照任务运行激活图的方法划分任务；再把子任务开始时和结束时的数据传递、激活消息定义为任务间关系，构造任务关系图2）将任务关系图中的任务间关系集合划分成两个部分，一个是指定源任务数据和目标任务变量的部分，命名为集合Ct；一个是没有指定源任务数据和目标变量的部分，命名为集合Ci3）与任务运行激活图具有相同任务的任务数据传递图中的边“任务间的数据传递”集合与Ct一一对应，表达含义也相同（没有传递完不能继续运行work阶段），因此任务关系图完全能够表达任务数据传递图4）任务运行激活图中的边“任务间的激活关系”与Ci一一对应，表达含义也相同（没有激活不能运行），因此任务关系图完全能够表达任务激活图正确性得证按照定理3，证明“基于任务关系图，实现任务关系驱动的LilyTask计算模型能够描述并实现多个子问题协同工作”,LilyTask计算模型的有效性,按照计算模型的算法设计过程定义任务描述任务间的关系通知系统，开始按照任务关系运行任务（关系驱动）任务关系模型比照激活模型的优势实际上，将两个DAG合并成一个DAG简单，无需每个任务都显式激活自顶而下的设计模式，对应思考问题的过程使高效的系统实现成为可能有效性得证至此，命题“描述任务关系图，实现任务关系驱动的LilyTask计算模型能够有效地描述并实现多个子问题协同工作”得证,LilyTask计算模型中的层次性任务,为了对应层次思考问题的过程，定义一个任务内部不必是严格串行执行，它可以继续分解成若干子任务，只要分解过程中满足任务封闭性即可如果一个任务具有子任务，那么它完成，当且仅当它的所有子任务完成规定一个任务，它代表整个问题，是所有其它任务的祖先规定只有具有同一个任务的子任务之间才能描述任务间关系如果不同任务的两个子任务之间存在任务间关系，则对这两个子任务分别向上追溯，找到某两个具有相同父任务的祖先任务，在这两个祖先任务之间描述任务间关系实际上，一个具有若干子任务的任务可以理解成原有任务关系图中的若干任务“合并”而成的只有“最终”子任务才是实际工作任务，其所有父任务的意义在于“层次性包容”与关系描述,LilyTask计算模型中的任务树,“叶子节点”对应着任务关系图中的节点任务树中的关系，是通过任务关系图中的关系变化而来如果原有的所有任务都没有子任务，这颗树的第一层子任务就是任务关系图,LilyTask计算模型对BSP模型的模拟,命题所有在BSP模型上的算法，都可以在LilyTask计算模型上实现证明BSP模型可以变换为只有一层任务的LilyTask模型将BSP模型的SuperStep对应到LilyTask模型中的任务组将BSP模型的每个SuperStep中的每个计算进程对应到LilyTask模型中的每个相应任务组中的任务将BSP模型中的数据传递对应到LilyTask模型中的任务关系LilyTask模型在这种对应下完全模拟了BSP模型从另外一个角度证明了LilyTask计算模型的正确性,返回,具有分时性质的分区共享,分区共享将各个节点根据预处理任务集的需要划分为若干相对独立的小系统，在小系统上为任务提供全部资源从任务本身的观点上看效率最高；但从全局的观点上看，容易造成资源浪费三种改进技术：分组调度、作业回填、进程迁移具有分时性质的分区共享最大程度上避免资源浪费对有明确分区需求的任务进行分区共享对没有分区需求的任务在未分配分区中进行分时共享当某已经分配的分区资源空闲时，系统有权力向此分区分配其它任务，但需保障原本任务优先使用资源对于提出明确资源需求的任务，采用预留资源的分时共享方法来保障任务的需求,预留资源的分时共享方法,保证某个任务对某些资源的占用需要任务向系统请求预留资源涉及到改变资源对任务的分配情况不代表在任何时刻都分配给任务请求的预留资源：任务的资源预留信息不一定很合适对作业资源的调整策略作业开始时，系统根据预留资源信息UREV分配资源定时或不定时地计算预期资源UEXP根据UREV与UEXP的比较情况进行调整，分配实际资源A例如，如果任务上次分配资源小于预留资源，而预期资源超过预留资源，那么实际分配资源A=minUREV,(1+e)*UCUR，e是一个预定义的常量,返回,系统需求,系统功能要求动态得到所有节点的存在信息：心跳对所有节点的资源进行信息获取与控制涉及到资源查看、作业的分配，以及并行作业的任务分配（负载平衡）有时需要进行跨网络的管理系统性能要求要具有实时性：及时获得必要信息，且不能影响集群系统正常工作要避免单节点失效：如果某一节点失效，不影响（或尽量少影响）系统整体最重要：真正充分利用系统资源需要能够处理大规模集群系统,返回,系统节点树,注意：在实质上，只能计算机之间进行交互，所以父节点实际上不能直接与子节点交互，而必须有一个计算机来代表非叶节点,返回,引入概念：信息点与信息负责点,引入概念目的子系统为逻辑概念，提供信息的工作必须由实际计算机完成信息点与信息负责点是实际的计算机，实现了逻辑与物理概念上的统一信息点与信息负责点在子系统内，代表一个子节点的计算机称为信息点，在子系统内部提供本子节点的信息存在某计算机，它作为子系统内的信息点的同时，也含有此子系统的整体信息；它可以代表整个子系统，被称作这个子系统的信息负责点信息负责点代表子系统时，在上层系统就是一个信息点,第二部分：若干思路,实际系统、系统节点树与信息点,U为较高层系统，X、Y、Z为较低的同层子系统，每层系统都有若干信息点NUi、NXi、NYi、NZi和一个信息负责点CU、CX、CY、CZ,第二部分：若干思路,返回,选择主要研究点的原则,首要原则研究要有意义机器模型、任务模型、管理模型所有的三大问题中的六小问题都有意义深度、难度与可行性所研究问题要有深度和难度应当是别人没有研究好的当然要有可行性最终要能够成为一套完备的理论主要研究点应该构成理论中的亮点其它部分要有研究安排,返回,机器模型的形式化探索1,系统的层次化表示系统集SYSTEMS用变量SX来表示某个系统，则SXSYSTEMS设某SX有若干个子系统，则其中第j个子系统表示为：设