多核代谢物鉴别：分布式计算与并行算法

可在www.sciencedirect.com在线获取理论计算机科学电子笔记299（2013）53-60www.elsevier.com/locate/entcsPMG：多核代谢物鉴别1Mohammad Mahdi Jaghooria，b，c，2，Sung-Shik T.Q.Jongmansb，Frank de Boerb，JulioPeironzac，Jean-LoupFaulond，Theo Reijmersc和Thomas Hankemeierc荷兰阿姆斯特丹学术医学中心（AMC）数学和计算机科学中心（CWI），阿姆斯特丹，荷兰c莱顿药物研究学术中心（LACDR），荷兰莱顿d法国埃夫里系统和合成生物学研究所摘要分布式计算被认为是加速软件执行的一种很有前途的方法，产生了一系列有价值的安全高效的并发算法。随着多核处理器的普及，并行化已经成为人们关注的中心，并带来了新的挑战，特别是关于数十甚至数百个并行核的可扩展性。 在本文中，我们提出了一个可扩展的多核工具，为代谢组学社区。该工具解决了代谢物鉴定的问题，这是目前代谢组学管道中的瓶颈关键词：多核，Java并发，fork-join，可扩展性，代谢组学1引言代谢组学是研究代谢的中间分子和最终产物：生物体中的化学反应。例如，在21世纪初，Gavaghan等人表明，人们可以通过化学分析它们的尿液来区分白老鼠和黑老鼠[2]。代谢组学需要精心设计和高效的软件工具来分析实验室实验中获得的数据。目前，管道中的一个主要瓶颈是代谢物鉴定：确定了哪些特定的化学元素（即，原子）存在于（细胞、体液等的）特定样本中， 提出相应化合物的结构是不平凡的（即，分子），特别是在处理1这项工作得到了eBioGrid和荷兰代谢组学中心的支持，该中心是荷兰基因组学倡议/荷兰科学研究组织的一部分2电子邮件（通讯作者）：m. amc.uva.nl1571-0661 © 2013 Elsevier B. V.在CC BY-NC-ND许可下开放访问。http://dx.doi.org/10.1016/j.entcs.2013.11.00554M.M. Jaghoori et al. /Electronic Notes in Theoretical Computer Science 299（2013）53一种未知的代谢物通常，研究人员必须自己提出代谢物的候选这需要解决一个令人生畏的组合问题，具有潜在的巨大搜索空间。在本文中，我们描述了一个多核计算机辅助结构解析（CASE）工具，称为并行分子发生器（PMG），用于自动分子结构生成的Java实现。 PMG是开源CASE工具的演变，称为开放分子生成器（OMG）[8]。实现CASE工具的一种结构阐明的问题，然后可以映射到同构自由穷举图生成[5，第4节]。在第2节中，我们解释了所涉及的算法背后的主要思想。在第3节中，我们描述了使用Java的当代并发工具的PMG的两个并行实现。这些高级并发工具使编程更不易出错，并且具有高效和优化的实现。基于实验证据，我们将在第4节讨论它们的可扩展性和由此产生的加速比。本文的贡献有两个方面。 对于代谢组学，我们提供一个并行、可扩展、开源的CASE工具。该工具的开源性质允许进一步优化和添加许多其他相关功能。我们对计算机科学的贡献是评估和比较Java中的并发工具。我们以前没有看到过类似的研究，特别是关于fork/join框架的可能优点的研究[7]。此外，PMG可以被看作是为多核时代开发可扩展并行程序为了给出PMG的性能的粗略指示MolGen在最左边和中间的情况下优于PMG。然而，当提供结构的已知片段时，4诸如在最右边的情况下，PMG优于MolGen。图1：根据MolGen、OMG、PMG位居第二。2分子结构生成计算机辅助结构解析是指软件工具，给定一个元素组成（如C4H5N3O）生成每一个化学可能的分子结构与这些原子。这些工具通常使用图形作为分子的自然表示，其中原子和键之间3MolGen存在了20多年。参见http://www.molgen.de。4有时，实验室实验提供了关于整个分子结构的小片段的额外信息，CASE工具应该使用这些信息来修剪搜索空间。M.M. Jaghoori et al. /Electronic Notes in Theoretical Computer Science 299（2013）535513C15classSearchTree {Molecule molecule;//表示当前分子的数据结构public voidrun（）{列表搜索树>扩展return（）;for（searchTree em：extended）em.expand（）;} }个文件夹清单1. OMG的实现原子-转化为顶点和边。然后，双和三重化学键被平移到两个和三个平行的边缘。此外，每个顶点的最大度被设置为其对应原子的化合价：原子可以形成的键的最大数量（例如，一个碳原子最多可形成四个键）。从本质上讲， 结构 世代开始从未连接的顶点（原子）的集合中，并迭代地在它们之间添加边（键）。因此，该算法构建并探索了一个搜索树，类似于图2中的搜索树，其中每个叶节点代表一个完整的分子结构。在生成整个搜索树之后，该算法收集并返回叶子中的分子结构作为输出。然而，如图2所示，通过递增地添加边来进行的图的朴素构造可能导致重复的图（例如，在1234B152443512345一243C2513B2535节点D1和D2）和同构图图2：一个搜索树示例。(e.g.、在节点B1和B2中）。5结构生成算法应该过滤掉这些。否则，我们最终可能会有数百万个重复。进行这种过滤的一种方法称为有序生成：首先，我们定义边和图上的全序关系。 该算法将边e添加到当前中的图G中， 节点，如果e大于或等于G中的边。Colbourn和Read [1]已经表明，在这种设置中，仅扩展包含最小图的节点可以保证生成所有可能的图而不重复。清单1显示了OMG中使用的顺序结构生成算法的摘要（我们对其进行了并行化，请参见第3节）。它从一组没有键的原子开始。 在搜索树的每个节点中，OMG使用方法addOneBond 找到在现有分子结构中添加一个键的所有可能性。返回列表中的对象充当搜索树中的新节点，OMG随后以DFS方式扩展搜索树3PMG的两种实现通常，有两种方法可以使清单1中的源代码并行。第一种方法是在程序开始时决定将5同构图表示相同的分子，因此，图同构为结构生成算法提供了足够强的等式概念12124D1124D256M.M. Jaghoori et al. /Electronic Notes in Theoretical Computer Science 299（2013）53类SearchTree扩展了RecursiveAction {分子;public voidrun（）{List SearchTree> extended = addOneBond（）;for（searchTreeem：extended）em.fork（）;}}类SearchTree实现Runnable {Molecule molecule;public voidrun（）{List SearchTree> extended = addOneBond（）;for（searchTreeem：extended）如果（任务队列已满）em.run（）;elseexecutor.submit（em）;} }个文件夹搜索树的n个部分（假设n个并行核心）。这种方法的开销非常低，主要用于多台计算机的网格。然而，它在多核上不是最佳的，特别是对于这个问题，因为搜索树不平衡：一些部分可能很小，使得相应的核未被充分利用。另一种方法是将工作分解为数百万个小任务，避免未充分利用的风险。但是，如果任务太小，管理任务的开销将超过实际计算。在我们的例子中，每个节点的计算量是一个合适的任务大小。目前，Java在基本的Java线程之上提供了两个用于编写并发程序的高级框架：固定大小（FS）执行器服务框架[3]和fork/join（FJ）框架[7]。因为我们不确定这两个框架中哪一个在可伸缩性方面最适合我们的应用程序，所以我们编写了两个PMG实现：一个使用FS执行器服务，称为PMGFS，另一个使用FJ框架，称为 作为PMGFJ6。我们参考附录A，了解Java中执行器服务和fork/join并发的简短入门。清单2. PM GFS（左）和PMGFJ（右）的实现-抽象代码。PMGFS：固定大小的执行服务实现在具有n个核的机器上启动时，PMGFS创建具有n个工作线程的基本线程池执行器服务。将工作线程的数量固定为内核的数量可以利用所有可用内核，同时消除动态调整线程池大小的开销。（具有n个以上的工作线程会导致上下文切换开销。）清单2（左）显示了PMGFS中使用的并行结构生成算法的源代码摘要。与清单1中的顺序源代码相比，搜索树中的每个节点现在都对应于PMGFS中的一个潜在并行任务（SearchTree实现了Runnable-参见附录A）。处理节点时，PMGFS中的工作线程将其子节点作为新任务提交给执行器服务（使它们可供其他工作线程并行执行），或者直接处理它们 此选择取决于executor服务的任务队列，该队列保存挂起的任务：如果队列足够满（意味着队列包含足够的工作以供其他工作线程完成其当前任务），PMGFS中的工作线程将避免任务提交以减少共享任务队列上的争用。6见git：git.code.sf.net/p/pmgcoordination/pmgcoordination。M.M. Jaghoori et al. /Electronic Notes in Theoretical Computer Science 299（2013）5357C12H26C13H28C14H30C15H32基线加速比图三. 任务大小：（静态）阈值与动态大小。18 1816 1614 1412 1210 108 86 64 42 200 2 4 6 8 10 12 14 161800 2 4 6 8 10 12 14 16 18核心数量图四、 PMGF S.图五、 PMGF J.PMGFJ：Fork/Join-based Implementation在具有n个核的机器上启动时，PMGFJ创建具有大约n个工作线程的FJ执行器服务（由于其内部工作，FJ框架可能创建比n多几个工作线程）。清单2（右）显示了PMGFJ中使用的并行结构生成算法的源代码摘要。PMGFJ不是在执行器服务上调用submit，而是在FJ任务上调用fork（SearchTree扩展了RecursiveAction，后者扩展了ForkJoinTask-参见附录A）。因为在FJ框架中每个工作线程都有自己的（或多或少）私有任务队列，所以PMGFJ中的工作线程不需要检查任务队列的满度以减少争用。为了避免太小的任务，使用fork/join的推荐方法是使用阈值来停止创建并行任务（图3左图）。在非平衡搜索树中，阈值必须根据队列大小动态调整。在我们的实现中，我们进一步优化了这种技术，即使在达到阈值之后也保持了产生新任务的可能性（图3右侧）。通过即时决定是生成一个新任务还是继续执行，我们实际上是动态地改变了C12H26C13H28C14H30基线加速比58M.M. Jaghoori et al. /Electronic Notes in Theoretical Computer Science 299（2013）534可扩展性：实验和结果为了研究PMG的两个实现的可扩展性，我们在一台带有两个Intel Xeon E5- 2650 L处理器的机器上运行了它们，总共产生了16个内核。我们首先做了三个实验。在每个实验中，我们针对1≤i≤ 16个内核运行PMGFS和PMGFJ（在Linux上使用taskset命令限制 核的数量），并对每个i的八次运行的结果进行平均：我们在第一次实验中称它们为由12个碳原子和26个氢原子组成的小分子图4和图5显示了我们的实验结果。灰色基线表示线性加速（即，最佳可伸缩性）。为了使图5更有意义，我们计算了PMGFJ相对于两个内核而不是一个内核的加速比。否则，我们将观察到相当大的超线性加速（对于C14H30运行，我们仍然有一些超线性加速超线性加速比是由于FJ框架在少数核上的相对较差的性能，特别是对于n= 1，这是由簿记引起的。 然而，随着内核数量（或任务大小）的增加，簿记开销变得微不足道。因此，相对于两个核心的计算加速会产生更有意义的数字。PMGFS量表比PMGFJ更差; PMGFS的所有测量值均低于基线。然而，C12H26、C13H28和C14H30之间的改进表明，PMGFS的可扩展性随着任务数量或平均任务大小的增加而改进。为了进一步研究这一趋势，我们做了一个额外的实验，在这个实验中，我们在更大的分子C15H32上运行PMG FS（在同一台机器上，使用taskset对1 ≤i≤ 16个核心进行相同的配置）。同样，我们观察到加速的改善，尽管比以前少。这表明，在C15H32运行中观察到的加速接近PMGFS固有可扩展性的极限：对于非常大的分子，每当我们将核心数量加倍时，它就会快大约80%。虽然这是一个不错的结果，但PMGFJ的固有可伸缩性似乎接近最佳加速。因此，对于我们的应用程序，FJ框架优于ES框架。5结论这项工作的贡献可以从两个方面来看：计算机科学和代谢组学。首先，我们为代谢组学社区提供了一个多核心、可扩展、开源的代谢物鉴定工具。我们解释了所涉及的主要算法的工作原理，并描述了使用来自Java的不同并发框架的两种实现这种可扩展的工具在多核时代是必要的，可以通过购买新的硬件来更快地执行程序，就像在处理器速度停止增长之前的旧时代一样其次，我们提供了一个非平凡的现实世界的情况下，在Java中的并发工具的计算机科学社区的评估和基于大量的实验，我们得出结论，最近引入的fork/join框架-M.M. Jaghoori et al. /Electronic Notes in Theoretical Computer Science 299（2013）5359工作优于旧的Java技术（如预期）。作为未来的工作，我们正在制作一个库，它向程序员隐藏处理动态大小任务的复杂性，从而保持fork/join编程的简单性尽管如此，如果在fork/join的默认实现中采用这种方法，那么可以从底层优化中受益。引用[1] 科 尔伯 恩 角 和R. Read ， Orderly algorithms for graph generation， International Journal of ComputerMathematics7（1979），pp. 167比172[2] Gavaghan，C.，E.霍姆斯，E。伦茨岛Wilson和J. Nicholson，一种基于NMR的代谢组学方法，用于研究遗传菌株的生物化学后果，FEBS Letters484（2000），pp. 169-174。[3] Goetz，B.，T.作者：J. J. Holmes和D. Lea，[4] Gugis ch ， R. ， A.Ker ber ， A. 科 纳 特 河 LAue ， M.梅 林 格 角 Rücker 和 A.Wassermann ，MOLGEN5.0，分子结构生成器，Bentham Science Publishers Ltd（2012），提交。[5] 卡斯基山口 和P.OüsterG.G.，“用于编码和设计的分类算法”，数学中的算法和计算，Springer，2006年。[6] K e rb e r，A.， R. LAU E，T。 Grüner和M. Meringer，MOLGEN4.0，M ATCH通信。 数学Comput.Chem 37（1998），pp. 205-208[7] Lea，D.，一个Java Fork/Join框架，在：D. Gannon和P. Mehrotra，编辑，Proceedings of JAVA' 00，2000，pp. 36比43[8] Peirone，J.，M. Rojas-Cherto，D.Fichera，T.赖默斯湖Coulier，J.-L. Faulon和T.汉克梅尔，OMG：开放分子生成器，J. Cheminformatics4（2012），pp. 167比172附录：Java并发工具执行人服务早在早期，Java就对基于线程的并发提供了基本支持。然而，直接用线程编程是困难的。为了简化这一点，Java 5以java.util.concurrent包的形式扩展了这种支持，提供了新的更高级别的并发实用程序：旨在简化Java中的并发（多核）编程的类和接口。这个库包括一个执行器服务框架，它为Java添加了一种异步消息传递形式执行器服务接受异步方法调用，具体化为概念任务的提交。可以将实现Java的Runnable接口（任务不返回任何内容）或Callable接口（任务返回结果）的任何对象作为任务提交在这样的提交之后，所涉及的expert服务立即向subserver返回Future对象（即，异步方法的调用者）。然后子任务可以使用该对象来轮询所提交任务的完成情况（即，被调用方法的终止）或获得任务方法在内部，执行器服务为每个提交的任务分配一个随后执行该任务的工作线程为了避免为每个任务创建新工作线程的开销，执行器服务维护线程池。线程池可以包含静态或动态数量的60M.M. Jaghoori et al. /Electronic Notes in Theoretical Computer Science 299（2013）53工作线程。只要没有人向执行器服务提交任务，线程池中的工作线程就处于空闲状态。一旦任务变得可用，执行器服务就选择一个空闲的工作线程来执行该任务。一旦选定的线程完成任务，它将再次变为空闲状态，并可用于执行下一个任务。提交的任务数可以超过线程池中的工作线程数。为了处理这些情况，执行器服务有一个内部任务队列。每个提交的任务首先被分配到任务队列。线程池中的工作线程通过轮询队列来获取新任务Fork/Join框架Java 7扩展了Java 5的executor服务框架，为fork/join（FJ）算法提供了高级别和高度优化的支持[7]，这是经典分治的并发变体。本质上，该扩展由一个特殊的FJ执行器服务组成，线程可以向该服务提交特殊的FJ任务（即，抽象ForkJoinTask类的扩展，而不是Runnable/Callable接口的实现）。FJ框架在执行器服务的普通提交工具之上添加了一层抽象：线程“fork”任务，而不是“提交”任务。7类似地，线程不是接收Future对象来等待任务的结果，而是FJ executor服务的内部工作方式与基本的线程池executor服务有很大不同：FJexecutor服务维护多个任务队列（从概念上讲，线程池中每个工作线程一个任务队列），并应用工作窃取算法来防止工作线程在自己的任务队列已清空而另一个队列尚未清空时空闲私有任务队列的组合对于工作线程和工作窃取，FJ框架应该比基本线程池执行器服务提供更好的性能，至少对于那些适合FJ抽象的问题（即，涉及将问题递归分解为独立子问题的算法）。7从技术上讲，仍然可以直接将任务提交给FJ执行器服务，而不是将它们分叉，但这通常不是FJ框架的预期用途