信息科学技术学院

博士研究生开题报告

大规模集群系统的

计算资源与作业管理王韬北京大学信息科学技术学院·网络研究所

并行与分布式计算组

提纲第一部分：面临着的挑战第二部分：解决问题的若干思路第三部分：研究重点的确立第四部分：博士论文工作计划第一部分：面临着的挑战第一部分：面临着的挑战大规模集群中的计算资源与作业管理问题着手前的一些零散思考第二部分：解决问题的若干思路第三部分：研究重点的确立第四部分：博士论文工作计划集群系统，计算资源与作业管理集群系统－日益重要的高性能计算环境集群系统：网络技术连接起来的计算机组合，协同工作人们对计算资源的需求远远超过单处理器的发展具有最高性价比的高性能计算环境重要的领域－计算资源与作业管理人们可以制造峰值计算能力每秒几十万亿次的集群系统人们不知道应当如何充分利用这些计算能力不仅仅单个并行程序无法有效利用集群系统，多个程序（作业）同时运行时也很难充分利用集群系统资源性能－搭建集群系统的首要目的：使我们关注“计算资源与作业管理”领域的研究本研究的对象：大规模集群面向环境大规模集群系统可能的扩展：网格计算面临着的问题大规模环境，节点数目众多，连接复杂组成系统的各个节点计算能力可能不同可能有物理上的多层次拓扑系统需求：功能与性能最终要能够充分地利用系统的计算能力第一部分：面临挑战问题着手前的一些零散思考[1]集中式管理设立一个管理节点，对所有节点进行集中式管理管理节点具有全部系统信息，易于进行调度整个系统实现起来最简单可采用多管理节点相互备份功能，提高效率问题一：大规模系统中的单节点瓶颈所有资源管理工作由单一节点完成，这个节点负担大，且其它节点需等待此节点的处理结果所有信息集中在单一节点，当此节点失效时，系统重新产生管理节点的代价大问题二：大规模系统中的信息滞后通过网络通信，无法及时获取所有节点的资源信息资源管理信息产生后，很难及时通知到所有相关节点第一部分：面临挑战问题着手前的一些零散思考[2]完全分布式管理每个节点都含有其它节点的信息减轻了大规模系统中的单节点瓶颈问题

注意，在信息获取后，每节点对所有节点信息的整合工作所需工作量与集中式相同，但每节点只需产生自己的调度信息，且不必将此信息传递给其它节点未解决大规模系统中的信息滞后问题引发新的问题网络中消息数目过多

获取信息时，集中式算法中只需要N-1条（对）消息，而完全分布式算法需要N*(N-1)条消息，或者N-1条广播当系统规模变大时，由于所得其它节点的信息可能滞后，各节点进行分布式资源管理所需协调工作更加复杂第一部分：面临挑战问题着手前的一些零散思考[3]跨网络管理大规模集群系统中的一部分可能处于一个内部子网外界只能访问子网内连接到外部网络的节点解决方法将子网内连接到外部网络的节点作为“代理”，系统管理“代理”，“代理”管理内网于是，如何有效地将这种“代理”纳入到整体模型中就成为一个与性能相关的问题第一部分：面临挑战问题着手前的一些零散思考[4]信息的获取与处理系统需要什么样的信息，才能够有效地进行下一步的资源与作业管理工作信息越丰富，越有助于资源管理的精确性信息越丰富，各节点负担越大、通过网络传输的数据量越大、资源管理的所需算法越复杂各节点的存在信息与资源信息定时检测：心跳处理器、内存、网络……物理资源信息和可用资源信息处理节点的动态加入与退出第一部分：面临挑战第二部分：解决问题的若干思路第一部分：面临着的挑战第二部分：解决问题的若干思路直观想法：分层次进行资源管理理论方面的三大问题综合考虑：猜想中的信息团模型第三部分：研究重点的确立第四部分：博士论文工作计划直观想法：：分层次进进行资源管管理思想根源一台计算机机的资源管管理，应该该对离它越越近的计算算机影响越越大，因此此可以将相相隔近的计计算机组成成小系统，，小系统之之间再管理理在不同网络络的两个计计算机系统统之间的影影响应当较较小试图解决在在大规模集集群系统中中的若干问问题单节点瓶颈颈管理消息过过多、管理理复杂信息滞后、、跨网络管管理第二部分：：若干思路路对于资源的的分层次管管理思想系统的层次次化分解与与组合根据性能及及网络情况况，将系统统分为若干干子系统每个子系统统内部进行行管理，再再将子系统统作为整体体进行管理理可以根据需需要，进行行子系统分分解与组合合对层次化管管理思想的的分析它只是一个个指导思想想：“层次次化的管理理原则”人类的经验验表明，层层次化的管管理原则是是正确的关键在于，，如何将这这个思想原原则，对应应成实际的的模型与系系统第二部分：：若干思路路层次化管理理思想的两两个方面理论与实现现理论方面：：这种分层层次进行资资源管理相相关的资源源、作业模模型是什么么、如何交交互（管理理模型）实现方面：：如何在大大规模的实实际集群系系统上高效效实现分层层次进行资资源管理实现方面需需要理论方方面进行指指导理论方面需需要实现方方面作为表表现极大的挑战战性世界上尚未未出现令人人信服的模模型世界上更未未出现完全全高效的系系统这正是我们们的机遇，，同时也是是严峻的挑挑战本报告中主主要讨论理理论方面最后部分将将简单介绍绍实现方面面的一些考考虑第二部分：：若干思路路理论方面的的三大问题题大规模集群群系统的机机器模型是是什么哪些计算资资源是重要要的；如何何描述；性性能参数是是什么这些计算资资源在大规规模系统中中的逻辑拓拓扑是什么么能有效利用用这些计算算资源的任任务模型是是什么如何描述任任务的需求求如何动态预预知任务对对资源的需需求情况层次化管理理的逻辑模模型和性能能模型是什什么如何根据给给定的机器器描述与作作业/任务务描述，得得到最适合合的管理方方式，并指指导下一步步的调度策策略及算法法如何根据逻逻辑模型得得到的结论论，给出性性能参数以以及对性能能的预测与与评价只要解决了了这三个问问题，就解解决了理论论方面的问问题第二部分：：若干思路路对理论方面面的分析一一：机器模模型机器模型计算资源逻辑拓扑任务模型管理模型第二部分：：若干思路路机器模型之之计算资源源重要的计算算资源处理器、内内存、网络络，……重要的信息息资源静态信信息：各计计算机计算算资源的固固有性质资源动态信信息：各计计算机的计计算资源的的当前可用用情况信息表述多元组表示示：<C,M,N>统一数值表表示尚需更加深深入的认识识需要确定信信息表述的的方法需要给出性性能参数与与性能公式式第二部分：：若干思路路机器模型之之逻辑拓扑扑层次化树状状结构－系统节点树树树中的每个个节点，代代表一个子子系统父节点代表表其全部子子节点每个父节点点只需对其其子节点进进行资源管管理全部叶子节节点是系统统的实际物物理节点引入概念：：信息点与信信息负责点点信息点：在在子系统内内，代表一一个子节点点的计算机机信息负责点点：在子系系统内含有有整个子系系统信息的的计算机、、对外代表表整个子系系统可以适应大大规模集群群系统子系统的构构造参考实实际网络结结构对于N个节节点的系统统，层数为为O(logN)动态可扩展展性可将不同网网络的系统统组织成更更大系统、、甚至可扩扩展到Grid系统统需要考虑节节点的动态态加入与退退出机制第二部分：：若干思路路关于系统层层次划分的的思考需要一个指指导方法，，使系统可可能达到最最大服务能能力适应层次化化管理思想想参考实际网网络结构，，在各种实实际系统中中指导如何何划分层次次决定每一层层次需要什什么样的计计算资源信信息（以及及负载信息息）几点在大规规模集群系系统中的具具体目标避免单节点点瓶颈产生较少的的管理消息息使管理尽量量简单化，，尽量不影影响计算机机本身计算算避免信息滞滞后问题实现跨网络络管理处理节点的的动态加入入与退出两点猜想各层所需信信息不同：似乎是显显然的最底层应小小规模且对对等第二部分：：若干思路路猜想：最底底层应小规规模且对等等相对集中式式管理的优优势每台计算机机都有子系系统全部信信息利于避免单单节点失效效资源管理时时能够更有有效地统筹筹全局进行资源管管理时无需需等待主节节点处理结结果可以随意选选择一台计计算机作为为信息负责责点，如最最轻负载可避免传统统分布式处处理方法的的不足各计算机一一定在同一一子网中，，可利用高高效组播获获取信息当计算机数数目少的时时候，信息息滞后问题题可忽略，，可认为所所有信息都都即时准确确，故可采采用相对简简单的算法法实现分布布式资源管管理猜想小结最底层计算算机数目应应较少（例例如10个个），形成成信息团第二部分：：若干思路路机器模型逻逻辑拓扑小小结基本描述层次化树状状结构可以适应大大规模集群群系统动态可扩展展性两点猜想：：各层所需需信息不同同、最底层层应小规模模且对等尚需工作上述描述仅仅仅是理论论的前身，，需要证明明与细化非最底层应应当如何组组织尚未清清楚图示：一种种可能的系系统逻辑图图第二部分：：若干思路路学界对机器器模型的相相关研究关于计算资资源的表示示从传统的只只考虑处理理器信息，，到考虑内内存、网络络、IPC资源等信信息越来越注重重实际系统统：开始考考虑多层次次、异构结结构等实际际问题一个面向层层次化结构构的研究F.D.Sacerdoti,……,,“WideAreaClusterMonitoringwithGanglia””,ProcIEEECluster2003Conference偶然发现此此文章关于于机器模型型方面与我我们的猜想想很相象，，除了“最最底层小规规模且对等等”；间接接坚定了我我们的信心心没有解决每每个层次应应该提供什什么样的信信息，只是是同样阐述述“更高层层提供更综综合的信息息”的原则则没有提及每每个层次的的系统应当当如何组织织的问题另一个相关关研究：从从网格信息息提供的角角度考虑问问题第二部分：：若干思路路对理论方面面的分析二二：任务模模型机器模型任务模型任务描述需求预知管理模型第二部分：：若干思路路考察学界现现有的任务务模型[1]最直观的任任务描述方方法任务所需要要的处理器器个数任务在某个个处理器上上的执行时时间任务之间的的执行序关关系目前任务描描述方法的的不足多数研究假假定每个任任务在每个个处理器上上的执行时时间已知、、任务之间间的通信时时间也已知知有些研究假假定任务工工作量相等等，有些假假定任务间间无关系顶尖的期刊刊中也有很很多这样的的情况（如如IEEETPDS，2004.4.,SchedulingStrategiesforMaster-SlaveTaskingonHeterogeneousProcessorPlatforms）第二部分：：若干思路路考察学界现现有的任务务模型[2]近年来开始始考虑切合合实际的任任务模型着眼点转向向任务对资资源的需求求最初只考虑虑对处理器器时间的需需求，后来来开始考虑虑内存、I/O等需需求GlobusToolkit3中中使用RSL2语言言（ResourceSpecificationLanguage）来沟通通任务对资资源的需求求：一种XML进一步思考考：要求任任务提供对对资源的需需求是否合合理？任务能否提提供准确的的资源需求求任务在运行行时的资源源需求是否否是不变量量最近开始出出现如何动动态对任务务需求进行行预知的研研究不要求任务务在运行前前提供准确确的资源需需求运行时动态态处理第二部分：：若干思路路任务模型之之任务描述述对资源需求求的描述对不同资源源分别处理理：将对各各种资源的的需求描述述为一个N元组，按按照顺序进进行配对，，如<处理理器数目、、处理器时时间，内存存，I/O，IPC>；N元元组的顺序序也是一个个考虑因素素统一参数：：将对不同同资源的需需求通过某某些算法统统一归结为为一个参数数；如统一一成处理器器利用率等等精确度与简简单性的权权衡任务之间关关系的描述述已有经验：：LilyTask并行模型型中的任务务关系待研究问题题提供什么样样的资源参参数供任务务进行描述述第二部分：：若干思路路任务模型之之动态需求求预知感知任务运运行时对资资源的需求求利用系统调调用，可以以得知任务务对CPU、内存等等计算资源源的使用情情况使用资源预预期函数来来定量地预预知资源需需求系统定时或或者不定时时地得到任任务的当时时针对某个个资源的使使用情况利用刚刚得得到的当前前资源使用用情况UCUR和上次的资资源使用情情况UOLD，计算预期期的资源需需求UEXP例如使用平平滑函数进进行预期：：UEXP=a∙UCUR+(1-a)∙UOLD待研究问题题监控哪些资资源；采用用什么资源源预期函数数第二部分：：若干思路路对理论方面面的分析三三：管理模模型机器模型任务模型管理模型逻辑模型性能模型第二部分：：若干思路路管理模型之之逻辑模型型基本策略完全分时共共享会严重重影响大规规模计算的的性能因此采用具有分时性性质的分区区共享重要问题对于机器模模型中的不不同的子系系统内部，，应当采用用什么样的的调度框架架，达到最最短平均响响应时间或或者最大吞吞吐率各个子系统统之间应当当如何交互互、如何协协作处理任任务，能够够实现系统统服务能力力最大化？？第二部分：：若干思路路对逻辑模型型重要问题题的思考子系统内部部的调度框框架显然，不同同层次的各各个子系统统的调度策策略应当不不同可以提供若若干有效的的调度策略略供子系统统选择对每个子系系统，需要要找到在它它内部最有有效的调度度策略可能最有效效的调度策策略与待处处理的任务务集相关也许每个子子系统中最最有效的调调度策略不不止一个需要进一步步的仔细研研究面向子系统统的管理猜想：信息息负责点分分层连动制制在子系统内内部，信息息点向信息息负责点负负责信息负责点点代表自己己所在的子子系统向上上层系统负负责子系统首先先在子系统统内部进行行任务处理理，超出处处理能力时时通过信息息负责点提提交到上层层系统处理理有很多具体体细节需要要思考，如如信息负责责点如何形形成等第二部分：：若干思路路子系统处理理任务过程程[1]第二部分：：若干思路路NX1NX2NY1NY2NZ1NZ2NUx|CXNUy|CYNUz|CZCUTAll1、、子子系系统统X首首先先把把任任务务TAll在X内内部部面面向向NXi进行行处处理理X子系系统统处处理理任任务务过过程程[2]第二二部部分分：：若若干干思思路路NX1NX2NY1NY2NZ1NZ2NUx|CXNUy|CYNUz|CZCUTIM2、、当当X能能力力不不足足时时，，通通过过CX将无无法法完完成成的的部部分分任任务务TIM提交交到到UUT1T2子系系统统处处理理任任务务过过程程[3]第二二部部分分：：若若干干思思路路NX1NX2NY1NY2NZ1NZ2NUx|CXNUy|CYNUz|CZCU3、、U把把TIM面向向NUi进行行，，选选定定一一个个（（或或多多个个））信信息息点点，，例例如如NUz，即即CZT1T2TIMU子系系统统处处理理任任务务过过程程[4]第二二部部分分：：若若干干思思路路NX1NX2NY1NY2NZ1NZ2NUx|CXNUy|CYNUz|CZCU4、、Z把把通通过过CZ得到到的的TIM在Z内内部部面面向向NZi进行行处处理理T1T2ZTIM子系系统统处处理理任任务务的的最最终终结结果果第二二部部分分：：若若干干思思路路NX1NX2NY1NY2NZ1NZ2NUx|CXNUy|CYNUz|CZCUTIM1TIM2T1T2现在在，，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.1－2003.12（（结题检查““优”）；协协助导师具体体负责IBM《共享享大学研究（（SUR）》》项目，北京京大学课题““北京大学网网格建设”；；2003.2－2005.1；协协助导师具体体负责Intel《《HPC03》项目，，北京大学课课题TaskSchedulingMechanism&ProgramSupportingEnvironmentforIntelItanium2SMPClusterSystem（PONo.4507076701），3万万美元（来自自Intel公司）；2003.11－2004.10；；实际负责人人正在进行的科科研项目Intel《《ParallelCacheSimulator》》项目（PONo.4507105230），2万美美元（来自Intel公公司）；2004.7－－2005.6；实际负负责人国家自然科学学基金重点项项目《网络计计算环境综合合试验平台》》，北京大学学子课题《网网络计算资源源服务中间件件》（90412010，人民币150万元，，国家拨款））；2004.7－2008.6；；主要参加人人附：文章与专专利第一作者文章章王韬、刘敏，，“LilyTask任任务并行程序序设计框架与与范例”，《《高性能计算算技术》，2004年第第3期（6月月）TaoWang,NanDi,JianShen,YanTang,“LilyTaskProgrammingModelandItsImplementationsonSMP&Cluster”,Proc.IASTEDInternationalConferenceonParallelandDistributedComputingandSystems2003,pp.301-306(PDCS2003,MarineDelRey,USA.Nov,2003)[EIIndexed]TaoWang,XiaomingLi,“LilyTaskProgramFramework––AnApproachtoTaskParallelProgrammingParadigm”,InternationalConferenceonParallelAlgorithmsandComputingEnvironments2003(ICPACE2003,HongKong,Oct,2003)[Notpublishedinpublic]TaoWang,XiaomingLi,“LilyTask-ATask-OrientedParallelComputationModel”,X.Zhouetal.(Eds.):APPT2003,LNCS2834,pp.157-161,2003,Springer-VerlagBerlinheidelberg2003[SCI,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，，《多媒体网网站的拆分及及重现方法》》，李晓明、、王冲、王韬韬；已授权结束谢谢大家欢迎提问王韬附录：作业管管理系统示例例典型的作业管管理系统－PBS系列商业版本PBSPro的的特性简介免费版本OpenPBS的局限典型的作业管管理系统－PBS系列总体情况最初由NASA在20世世纪90年代代早期开发目的是面向集集群系统提供供有效的作业业管理服务分化为免费的的OpenPBS和商业业化的PBSPro免费版本被广广为使用大多数HPC集成厂商为为用户提供OpenPBS作为作业业管理部件业界最著名的的集群系统管管理软件Scali集成成了OpenPBS商业版本PBSPro的的主要特性图形化和命令令行用户界面面提交批处理和和交互作业查询作业、队队列以及系统统状态跟踪作业的进进展作业优先级与与相关性用户可以指定定作业的优先先级用户可以指定定批处理作业业之间的关系系，包括：执执行顺序、同同步，以及依依照其它作业业执行的成功功与否来决定定是否运行自动的负载平平衡集群调度系统统提供多种负负载平衡策略略根据硬件配置置、资源可用用情况以及键键盘动作等情情况采取行动动错误处理和冗冗余可以被配置成成容错模式当主服务器失失效时，从服服务器可以顶顶替正在运行的作作业，以及队队列中的作业业不会被影响响商业版本PBSPro的的其它特性实现安全和访问控控制作业记帐全面的应用编编程接口不同系统间的的用户名称映映射利用桌桌面计计算机机空闲闲处理理器时时间支持广泛的的运行行平台台，包包括SMP集群群分布式式集群群，甚甚至可可以在在广域域网上上资源预预留自动文文件传传输并行作作业，，可使使用MPI、MPL、PVM和HPF等计算网网格，，支持持GlobusToolkit免费版版本OpenPBS的局局限使用性性的局局限只支持持类Unix系系统不支持持SMP集集群系系统只支持持较小小规模模的集集群环环境没有完完善的的使用用文档档功能性性的局局限只有轮轮询的的负载载平衡衡策略略不支持持抢先先式作作业调调度不支持持利用用桌面面计算算机空空闲时时间不支持持资源源预留留不支持持容错错不支持持网格格计算算理论模模型：：LilyTask并行行计算算模型型处理任任务并并行的的基础础模型型描述任任务关关系图图实现任任务关关系驱驱动有效地地描述述并实实现多多个问问题协协同工工作STARTLilyTask计计算模模型中中的基基本概概念（（1））任务：：解决决一个个问题题所需需要完完成的的一段段工作作，这这个工工作具具有如如下两两个性性质：：只有在在这段段工作作启动动前能能够接接收其其它工工作传传递的的数据据只有在在这段段工作作完成成后才才能够够向其其它工工作传传递数数据任务间间关系系：一一个具具有指指向性性的有有序四四元组组<源任任务,源源任务务数据据,目目标标任务务,目目标标任务务数据据位置置>从“源源任务务”指指向““目标标任务务”，，标志志着源源任务务完成成时，，需要要将指指定的的源任任务数数据，，放入入目标标任务务的指指定数数据位位置中中一条关关系描描述的的数据据传递递（可可以为为空））完成成后，，标志志着这这条关关系的的完成成同时表表达着着任务务启动动条件件：一一个任任务可可以启启动，，当且且仅当当所有有指向向它的的任务务间关关系已已经完完成LilyTask计计算模模型中中的基基本概概念（（2））任务组组，简简化任任务间间关系系的描描述形形式任务关关系图图、任任务关关系驱驱动STARTLilyTask计计算模模型的的命题题命题描述任任务关关系图图，实实现任任务关关系驱驱动的的LilyTask计算算模型型能够够有效效地描描述并并实现现多个个子问问题协协同工工作基础认认定一个问问题可可以分分解为为多个个子问问题（（也许许递归归继续续分解解），，这些些子问问题协协同工工作，，共同同完成成待解解决问问题问题之之间可可以进进行数数据传传递除了最最初工工作的的问题题，一一个问问题必必须由由另外外一个个问题题通知知运行行，我我们将将这个个过程程称作作“激激活””；我我们假假定最最初工工作的的问题题也是是由一一个特特殊问问题““系统统”激激活；；因此此全部部问题题都需需要被被“激激活””LilyTask计计算模模型的的正确确性（（1））引理1：一一个问问题可可以分分解成成一个个或者者多个个子问问题，，每个个子问问题内内部串串行工工作证明：：如果果某个个子问问题内内部不不是串串行工工作，，那么么必可可被继继续分分解成成若干干子问问题，，直到到串行行工作作为止止引理2：任任一内内部串串行工工作的的问题题，如如果它它与其其它问问题交交换数数据，，那么么它可可以划划分成成一个个或者者多个个具有有串行行关系系的子子问题题，每每个子子问题题只在在工作作开始始时接接收其其它问问题传传递过过来的的数据据，工工作结结束时时向其其它问问题传传递数数据，，运行行过程程中其其数据据不受受其它它问题题影响响证明：：1））任何何交换换数据据，都都可分分为接接受数数据、、发送送数据据两种种不同同操作作，这这两个个操作作是阻阻塞的的；其其它操操作不不会影影响问问题中中的数数据2）问问题内内部串串行工工作，，所以以”接接受数数据””、””发送送数据据”、、”其其它工工作””必不不在同同一时时刻，，且互互不影影响；；3）我我们可可以用用“其其它工工作[work]””、““接受受数据据[recv]”、、“发发送数数据[send]””将将此问问题划划分为为几个个工作作块，，即[work]、、[recv]、[send]的的一个个排列列4）我我们在在这个个排列列中插插入若若干特特殊的的[recv]和[send]，，这些些特殊殊的[recv]和和[send]都是是空操操作；；使原原有排排列变变为一一个规规则排排列[recv][work][send]………5）把把规则则排列列中的的每个个[recv][work][send]块定定义为为一个个子问问题，，这些些子问问题串串行工工作，，完成成原有有问题题6）由由（1）（（2））可知知，[work]过过程中中数据据不受受其它它问题题影响响LilyTask计计算模模型的的正确确性（（2））引理3：任一内内部串串行工工作的的问题题，如如果它它激活活其它它N个个问题题，那那么它它可以以划分分成至至多N＋1个具具有串串行执执行关关系的的子问问题，，其它它N个个问题题只能能被某某个子子问题题运行行结束束时激激活证明：：类似似引理理2的的证明明，我我们将将问题题划分分为““工作作[work]”、、“激激活[invoke]””两种种不同同的操操作类类，每每个[invoke]类类包含含相邻邻的若若干激激活操操作；；最后后我们们得到到一个个排序序；如如果第第一个个操作作是[invoke]类类，就就在前前面插插入一一个空空操作作的[work]类类；从从第一一个排排序开开始，，将每每个相相邻的的[work][invoke]定义义为一一个子子问题题；由由于最最多有有N个个[invoke]类，，考虑虑到最最后一一个[work]也也许没没有[invoke]与与其对对应，，那么么最多多就可可划分分为最最多N+1个具具有串串行执执行关关系的的子问问题，，每个个子问问题结结束的的时候候，激激活其其它问问题（（最后后一个个子问问题也也许不不激活活其它它问题题）LilyTask计计算模模型的的正确确性（（3））引理4：任任何问问题，，都可可以分分解成成若干干子问问题协协同工工作，，每个个子问问题内内部串串行工工作，，只在在启动动前前前接收收其它它子问问题传传递过过来的的数据据，结结束后后向其其它子子问题题传递递数据据，运运行过过程中中其数数据不不受其其它子子问题题影响响；我我们将将这种种子问问题，，称作作“任任务””证明：由由引理（（1）（（2）得得证引理5：：如果一一个任务务Ta要要向任务务Tb传传递数据据，Tb一定应应该在Ta结束束后开始始；如果果我们定定义关系系，说明明Ta要要向Tb传递数数据，那那么这个个关系从时序序角度讲讲具有反反自反性性、传递递性与反反对称性性，即关系是是拟序关关系证明：1）按照照任务的的定义，，任务的的过程[recv][work][send]是是串行行的；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）如果果有向图图存在一一个环，，设这个个环的顶顶点为T1T2…TpT1，由由引理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计算算模型中中的任务务树“叶子节节点”对对应着任任务关系系图中的的节点任务树中中的关系系，是通通过任务务关系图图中的关关系变化化而来如果原有有的所有有任务都都没有子子任务，，这颗树树的第一一层子任任务就是是任务关关系图STARTLilyTask计算算模型对对BSP模型的的模拟命题所有在BSP模模型上的的算法，，都可以以在LilyTask计算模模型上实实现证明BSP模模型可以以变换为为只有一一层任务务的LilyTask模型将BSP模型的的SuperStep对应到到LilyTask模模型中的的任务组组将BSP模型的的每个SuperStep中中的每个个计算进进程对应应到LilyTask模型中中的每个个相应任任务组中中的任务务将BSP模型中中的数据据传递对对应到LilyTask模型型中的任任务关系系LilyTask模型型在这种种对应下下完全模模拟了BSP模模型从另外一一个角度度证明了了LilyTask计计算模型型的正确确性返回具有分时时性质的的分区共共享分区共享享将各个节节点根据据预处理理任务集集的需要要划分为为若干相相对独立立的小系系统，在在小系统统上为任任务提供供全部资资源从任务本本身的观观点上看看效率最最高；但但从全局局的观点点上看，，容易造造成资源源浪费三种改进进技术：：分组调调度、作作业回填填、进程程迁移具有分时时性质的的分区共共享最大程度度上避免免资源浪浪费对有明确确分区需需求的任任务进行行分区共共享对没有分分区需求求的任务务在未分分配分区区中进行行分时共共享当某已经经分配的的分区资资源空闲闲时，系系统有权权力向此此分区分分配其它它任务，，但需保保障原本本任务优