基于PC机资源的分布式计算系统中相干任务求解方法及其优势

© 2014 Anatoly Kalyaev，Iakov Korovin.出版社：Elsevier B.V.由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 9（2014）131 - 1372014年AASRI电路与信号处理会议（CSP 2014）利用空闲PC机解决相干任务Anatoly Kalyaeva *，Iakov Korovina南方联邦大学多处理器计算系统科学研究所，2，塔甘罗格347922，俄罗斯摘要本文提出了一种基于PC机资源的分布式计算系统中相干任务求解的新方法。这些资源的参数是动态变化的，这使得它很难在分布式计算中的应用。该方法采用多智能体方法，通过智能体的主动控制，实现了分布式计算系统中个人计算机的有效利用，并通过智能体之间的交互，分散调度任务求解过程。为了解决每一个传入的连贯任务，系统的代理联合成社区，这使得它更容易调度和执行计算。该方法的主要优点是降低了分布式计算系统的创建和维护成本。© 2014作者。出版社：Elsevier B. V.这是CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。美国应用科学研究所科学委员会负责同行评议关键词：分布式计算系统;多智能体系统;相干任务;社区;主动智能体;分散系统。1. 介绍使用分布式个人计算资源来解决复杂任务的想法出现在三十多年前，但由于全球和本地联网的进展不同，* 通讯作者。电话：+ 7-952-5666699;传真：+7-952-5666699.电子邮件地址：anatoly@kalyaev.net。2212-6716 © 2014作者出版社：Elsevier B.诉 这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/3.0/）。美国应用科学研究所科学委员会负责的同行评审doi：10.1016/j.aasri.2014.09.021132Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 9（2014）131组织开始使用基于这些资源的分布式计算系统（CS）。最初是在21世纪初提出的全球资源信息数据库[1]。今天，这种系统的相关性增长，由网络和个人计算机的进步提供动力。在分析一些广泛分布的分布式CS [2][3]时，我们注意到它们中的大多数都有局限性：这些系统中的一部分只能解决容易分解的非相干任务，而另一部分只能基于一组类似的专用计算节点。然而，今天的网络连接了许多个人计算机，几乎所有这些计算机都没有完全加载。在分布式CS中使用这样的个人计算机（PC）的主要问题是由于它们的所有者的动作而随时改变它们的参数（例如性能等）。另一个问题是许多不同的PC在一个分布式CS中共存的概率。所有这些都使得任务的有效分配和求解过程变得非常复杂。解决连贯的任务，在这样的分布式CS的基础上私人PC协作是相当困难的任务。今天，在解决连贯任务的同时有效加载分布式CS是一个挑战[5]。然而，解决这样的任务的情况下，PC的参数动态变化是更难的，这就是为什么创建新的方法来组织分布式计算的相干任务是非常重要的任务。2. 基于PC机的这种新方法基于多智能体方法[6]和集体决策原则[7]。在所提出的分布式CS组织方法中，我们试图避免专用服务器，并对分布式CS进行分散组织[8]。分布式CS的每台PC都安装了主动代理软件。系统中程序Agent之间的交互实现了任务求解的调度过程我们面临的第一个问题出现了，因为分布式CS可以由不同的PC机的任何时刻。这就是为什么用户和分布式CS之间的交互是复杂的，因为用户不知道在哪里发送他的任务。为了解决这个问题，我们决定使用被动服务节点，作为“公告板”（BB）[9]。所提出的分散式分布式CS的结构图如图1所示。Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 9（2014）131133图1.分布式CS可以看出，分布式CS分为三层。执行计算节点（图中的ECN）执行这种分布式CS中的几乎所有服务任务。Agent在分布式CS中调度用户任务的求解过程。为了解决连贯的任务，他们创建了专门的社区。系统可能会遇到PC机的故障，PC机计算能力的变化，网络带宽的减少，以及所有这些都可能导致任务求解时间的增加。在所有这些情况下，代理社区必须改变其组成，以便及时解决用户指定的任务。一般来说，在分散式分布式CS中解决传入任务的方法可以描述如下。系统的用户形成需要解决的任务，设置解决任务的时间要求，并确定用于解决的虚拟支付，该虚拟支付由一些虚拟点表示。之后，用户将所有任务数据发送到分布式CS的公告板。分布式CS的主动代理监视BB并寻找传入的任务。如果某个Agent发现新的任务，则对每个任务的求解收益进行评估，然后选择最有利的任务。之后，Agent加入社区解决选定的任务，并采取一些子任务来解决。每次新的代理加入社区，它评估任务解决的时间。如果社区的表现足以及时解决任务，社区就会停止扩张。当新的智能体加入社区时，它开始执行子任务，在执行子任务的过程中，智能体会监控其PC的参数。如果参数的变化导致超过用户指定的任务解决时间，社区开始接受新的代理。当社区解决任务时，产生结果的代理将其发送给用户，然后使社区自行解散[10]。为了更容易理解所提出的方法，我们决定将其分为3个阶段： ·任务的正式表示; ·创建社区; ·子任务的分配。让我们更详细地描述阶段。134Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 9（2014）1312.1. 任务的形式化表示首先，用户必须以正确的形式呈现任务，让分布式CS执行解决方案。我们决定用任务信息图（TIG）的形式来表示系统中的任务。TIG是一个图，其中顶点表示用户任务的子任务，弧表示子任务之间的数据传输。在TIG G（Q，X）中，每个顶点qi表示第i个子任务。对于每个子任务，用户指定估计的计算复杂度Yi。每个弧x（qi，qj）被指定为从子任务qi到子任务qj的传输中的数据量Wij。为了方便起见，我们决定以多层并行形式（MPF）呈现TIG，以简化任务图的进一步并行化。要做到这一点，图的所有顶点都应该根据以下规则划分为子集Vi：如果弧x（qm，qn）将层j连接到层k，则意味着j k。当TIG在MPF中表示时，我们可以容易地评估任务的并行计算的数量和社区中用于解决该任务的代理的最大数量作为MPF TIG层中的顶点的最大数量。在下一步中，用户必须指定最大时间来解决他的任务和优先级。完成所有步骤后，用户将任务发送到分布式CS的任何公告板。2.2. 创建社区当用户将任务发送到分布式CS的公告板时，分布式CS的节点开始在社区中协作，这将允许在用户指定的时间内解决任务[11]。在创建代理社区时，分散的分布式CS遵循以下步骤：1. BB接收新传入任务的数据并将传入任务标记为2. 代理Aj在分布式CS的公告板上查找未完成的任务。对于每个找到的任务，座席将收到：a所找到的任务的A TIG G; b任务的优先级Pc子任务qi（i = 1，K）状态（“就绪”/“工作”/“新”）;e由任务M提供的代理的最大数量;3. 代理Aj评估解决所有发现的未完成任务的收益a代理Aj从最有利可图的开始对任务的盈利能力值（P / Y）进行排名; b代理Aj从列表中查找下一个任务。如果列表为空，则转到步骤4; c代理Aj接收社区中的代理的参数和代理的数量N;d如果N = M，则代理转到步骤3b;e代理计算社区是否有足够的PC在用户指定的时间内解决任务，如果是，则代理从未完成的任务列表中删除该任务并进行到步骤3b;f代理Aj加入社区;g如果代理的性能（通过公式（1）找到）足以在指定的时间内完成用户的任务，则代理在公告板上将任务标记为完成;4. 如果代理Aj已经成功加入社区，则进行到步骤5，否则代理进入待机模式一段时间并进行到步骤2;5. 如果任务标记为完成，则表示社区已成功创建，座席开始解决任务。上述步骤使分布式CS的Agent形成一个社区，及时解决到来的一致性任务社区中的代理集取决于它们的实际性能。然后，社区Agent需要有效地分配子任务，使任务在用户指定的时间内得到解决。Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 9（2014）1311352.3. 子任务的分配一旦分布式CS的代理成功地创建了社区，他们必须在他们的PC之间执行子任务的分配：1. 当社区中的某个Agent空闲（没有子任务需要解决）时，该Agent向社区中的所有Agent发送消息，使它们开始空闲子任务分配过程。2. 参与社区各Agent在TIG中寻找下一个未解子任务qR并在该Agent的PC上计算其求解时间的过程;3. 代理Aj将结果值发送给社区的所有代理;4. 当社区中的所有代理接收到所有值时，它们选择最低的执行时间。能够负担得起这一时间的代理As采取子任务qR，将其标记为“工作”并开始其解决方案;5. 代理A，从所有代理请求任务qR的解所需的数据，这些代理是通过传入弧与顶点qR连接的顶点子集的所有者;6. 如果其中一个智能体完成了某个子任务的决策，则将该子任务标记为“已解决”;7. 在解决每个子任务后，代理使用其计算复杂度YR和决策时间Tsol来确定其PC的当前性能Sj，Sj =YR / Tsol，并将结果值发送给所有其他代理和公告板;8. Agent估计社区的特征，以确定任务是否可以在指定的时间内解决。如果社区无法解决任务，则Agent将其标记为“未完成”，社区的创建重新开始;9. 如果有任何未解决的子任务，则转到步骤1;10. 如果代理完成了用户任务中最后一个子任务的求解，它将结果数据发送到公告板，然后发送给用户。该算法的主要优点是能够根据分布式计算系统中个人计算机的实际参数来调整计算过程。两个算法允许解决相干任务的分布式CS基于个人计算机的参数变化。下一步是探索所提出的方法和算法的有效性。3.实验和结果由于基于PC机资源的分布式CS系统中参数较多，且几乎不可能在实际硬件上进行实验，因此本文提出的算法在解决相干任务时的效率是一个非常困难的问题。这就是为什么我们必须创建程序，它允许对包含多达1000台PC的分布式CS进行建模，解决多达250个任务。[12]第10条。右边的表格显示了分布式CS的一组任务、它们的状态（“新”/“求解”/“已求解”）及其参数（求解的最大时间、复杂度、求解的虚拟点的数量等）。此表中的每个任务都有不同的颜色。分布式CS PC的可视化表示可以在中心找到。每个圆圈代表建模的PC，其颜色与PC上正在解决的任务的颜色相匹配。实验研究的主要目标是所提出的算法的效率的实际证明，但我们也想评估由于分散计算的调度在PC上的处理器时间的相对损失。这就是为什么我们必须用不同的PC和计算机网络参数进行几系列实验的原因。在研究所提出的算法时，我们使用了我们在南方联邦大学工作的一些类型的真实任务[13]。我们决定使用PC的实际负载百分比，这可以显示由于组织目的而导致的处理器时间损失，以及及时解决的任务百分比，这显示了最终用户的系统效率。在分布式CS中有许多重要的参数，这就是为什么我们决定使用实验计划：我们将参数分为三组：初级（系统参数）（P），次级（特定任务和PC的参数）（S）和三级（用户条件136Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 9（2014）131参数）（T）。最后，我们决定探索分布式CS的以下参数的影响：分布式CS中的PC机数量（P1），传入任务的频率（P2），PC机的计算能力（S1），网络带宽（S2），任务的计算复杂度（S3），任务的子任务之间发送的数据量（S4），优先级（T1），子任务的数量（T2），解决任务的时间（T3）。对于一级参数，我们决定使用绝对值，对于二级参数使用相对值，对于三级参数使用有限的随机值。为了使结果更精确，由于随机值，我们进行了三次每个实验。结果表明，PC的实际负载百分比良好：从72%到92%。这意味着由于组织而损失的时间占总时间的8%到28%。在相同方向的现代研究[5]表明，在分布式CS中解决相干任务的平均效率约为40%，这意味着所提出的方法是有效的。结论本文提出了一种新的基于个人计算机资源的分布式计算系统中相干任务的求解方法。为了达到有效利用个人计算机的能力，提出的方法使用多智能体的方法。该方法的主要优点是降低了分布式计算系统的创建和维护成本。这种方法已经成功地用于油田设备的决策支持、预测和诊断系统[15-18]。作者计划的下一步研究是建立分布式CS的功能原型，这将允许创建真正的分布式计算系统的基础上的科学实验室的计算机。确认该论文的发表是由于俄罗斯基础研究基金的财政支持，项目13-08- 01172，14-08-00776和14-08-00800。引用[1] 福斯特岛Kesselman角和Tuecke，S.（2001年）的第10页。网格剖析：实现可扩展的虚拟组织。国际高性能计算应用杂志，15（3）。200-222. 2001年[2] Thain，D.，Tannenbaum，T.，Livny，M.（2005年）。Distributed Computing in Practice：TheCondor Experience Concurrency and Computation：Practice and Experience，Vol. 17，No. 2-4，323-356，2005.[3] Berman，F.沃尔斯基河（2003年）的报告。使用AppLeS在网格上进行自适应计算，IEEETransactions on Parallel and Distributed Systems，Vol.14，369[4] Poleshaev P.N.（2012年）。实验研究算法的任务规划网格系统与模拟器，材料的国际会议[5] Ivashko E.E.，Golovin A.S.（2012年）。BOINC-GRID /“高性能计算”HPC-UA'2012国际会议材料的计算效率[6] 伍尔德里奇湾（2002年）的报告。多智能体系统导论，约翰威利父子有限公司，2002年，366页。[7] 塔拉索夫足球俱乐部（2002年）的报告。从多智能体系统到智能组织，2002年。[8]Kalyaev A.I.（2011年）。全球资源信息数据库社区代理人的分散组织管理人，会议录Anatoly Kalyaev和Iakov Korovin/AASRI Procedia 9（2014）131137的SFU。Technical sciences，2008，2011，230-238.[9] Kalyaev A.I，Melnik E.V.（2010）.关于网格计算的分散组织的一种方式，极端机器人技术-与青年科学家学校元素的会议材料-2010。- P. 73比75[10] Kalyaev A.I.（2013年）。Multiagent Approach for Building Distributed Adaptive ComputingSystem，Procedia Computer Science，第18卷，2013年，第2193-2202页。[11] Kalyaev A.I.（2012年）。分布式网格中分布式计算自适应组织的方法和算法，计算机与信息技术Hera ld of o mu t o n technologies 2004年4月，2 0 1 2日。–28-33[12] Melnik E.V.，Kalyaev A.I.（2010年）。分散组织全球资源信息数据库计算、信息通信和计算技术的一种方式-乌兰乌德，2010年。- 第160 -162页[13] Hisamutdinov M.V.，科罗温公司，Kalyaev A.I.（2013年）。进化算法在油田设备故障预测人工神经网络训练过程中的应用，2013年第二届计算机、通信、控制与自动化国际研讨会（3CA 2013）会议录。- 亚特兰蒂斯出版社第253-257页。[14] Gorelova G.V.，Radchenko S.A.，Melnik E.V.，Kalyaev A.I.（2007年）。在研究分布式计算组织的新方法和算法时的实验计划，计算机和信息技术先驱报，2001年，2007年。–49-5 6[15] Korovin，Ya. S.，卡利亚耶夫（2013年）。A.I.提高石油公司企业网络数据传输系统效率的方法和算法。Neftyanoe Khozyaistvo - Oil Industry，Moscow，2009，pp. 96-10 0.[16] Korovin，Ya. S.（2007年）。基于神经网络的潜油电泵控制决策支持系统。NeftyanoeKhozyaistvo -OilI industry，Moscow，2001，pp.80-83[17] Korovin，Ya. S.，Khisamutdinov，M.V.，Tkachenko，M.G.（2013年）。应用进化算法和人工神经网络预测油田设备工况。NeftyanoeKh ozyaistv o-OilI ndustry，2012，pp.128比132[18] Korovin，Ya. S.，Tkachenko，M.G.，Kononov，S.V.（2012）.基于数据挖掘技术的油田设备状态诊断。NeftyanoeKhozyaistvo-Oi lIndustry，2009年，第109页。 116- 118.