基于GPU的化合物子结构在线检索方法研究

化合物结构检索是化学信息学的基本问题之一。随着网络化合物结构数据库的发展，对化合物结构实时在线检索的需要日益增加。具有NP完备性特点的子结构检索则是化合物结构在线检索中的难点。由于算法特性和单节点CPU计算性能的限制，大规模的网络化合物结构数据库通常采用大型CPU集群实现子结构的在线检索，以满足网络用户对速度的苛刻要求，其成本高、维护难。探索一种小集群实现的、低成本的、快速子结构在线检索系统具有重要意义。本项目采用高性能计算硬件GPU为切入点，研究单节点条件下利用GPU加速子结构检索的主要耗时环节如预筛过程中的分子指纹预筛环节和逐一匹配过程的Ullmann算法匹配环节的可行性。并在算法改造基础上实现符合GPU特点的编程及优化，研究不同层次下的任务分解和负载平衡策略，以达到探索单节点条件下计算性能极限的目的。最终建立可应用于大规模网络化合物结构数据库的低成本快速子结构在线检索方法。

化合物结构检索等信息的处理是化学信息学要解决的基本问题。子结构检索是化学结构信息处理过程的基本步骤，也是最耗时的一种检索方式。其本质为子图匹配，已被证明是一类NP完备性问题，即匹配检索时间随着原子数的增加呈指数级增长。人们在图论发展基础上结合化合物本身特征开发了很多子结构搜索算法。然而近年来算法的发展达到了一个瓶颈，没有出现性能极大提升的新算法。仅依靠算法改进对单机检索能力的提升已不能满足海量网络用户对大规模化合物结构数据库进行快速子结构在线检索的需要。GPU的出现为解决这一问题提供了新的机会。.GPU是专门设计用于处理计算密集和高度并行计算的硬件，适合处理计算密集型的数据并行问题。而在化合物子结构检索的两个主要过程“预筛选”和“逐一匹配”中存在着可以转化为数据并行问题的程序环节，且在检索时间中占有较大比例。.本项目采用数据库并行与算法并行相结合的方法，以GPU为加速手段，探索了一套低成本的、快速的化合物子结构在线检索方法，以期解决大规模网络化合物结构数据库在线子结构检索时面临的速度与成本的矛盾问题。.在执行期间本项目已按计划实现了预筛过程和逐一匹配环节GPU化程序改造。其中预筛过程重新设计了分子指纹存储数据结构，由逐位比对改为整数化指纹片断比对，并采用细粒化数据存储方式和线程组织方式分别进行调优，提高了计算并行度。同时，改进后的内存读取也符合全局内存合并访问的要求，最终实现了两个数量级的加速。.在子结构检索的逐一匹配过程中，采用了链式栈消解深度优先的递归算法，将各级树节点存储于栈中，依次检索。从构成分子的各单原子为根节点开始并行执行路径搜索，经过有限步得到扩展后的可能路径集合，再重新分配并行节点再次并行执行路径搜索，直至得到匹配路径。此算法采用链式整数数组模拟位集合，改写了相应的位集合操作，并重写了相应的路径搜索、存储和终止条件判断函数。考虑到GPU共享内存容量有限，加入了栈最大递归次数限制。但由于GPU共享内存较小，链式栈只能以有限次实现，导致数据多次进出内存，消耗了大量通信时间，目前子结构检索的逐一匹配步骤性能提升并不明显，仍有较大优化空间。未来可考虑内存优化及算法改进。.实际应用中以ChemDB Portal系统为测试平台，实现了GPU程序和化合物子结构检索网络平台的初步融合，得益于结构指纹预筛选两个数量级的加速，整体子结构检索得到了良好的加速效果。