最长公共子序列(LCS)是解决在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题(不改变序列顺序)。最长公共子序列问题是很多领域中的经典问题,比如计算生物学、数据挖掘、文本编辑等领域,也是数据比较程序和生物信息学应用的基础。目前的解决LCS问题的方法都是基于动态规划。随着生物序列数据库规模的不断增长,并行序列比较算法发挥越来越重要的作用。基于位并行的LCS算法,将每个字符映射为计算机字word的一个二进制位,同时可以对32个字符进行操作,减少了操作数目,达到一种细粒度的并行。虽然计算速度相对提升了一些,但是随着大数据的产生,需要处理的数据越来越多,仅仅利用CPU进行计算已跟不上数据产生的速度,利用高性能计算加速卡进行加速迫在眉睫。基于KNC、KNL加速卡的计算机集群则是发挥了更大的优势,能让我们获得更大程度的并行,取得更高的程序性能。在本论文中,我们提出了 XLCS,通过在Intel Xeon Phi集群上应用基于位操作的并行实现来加速LCS算法。我们设计了一个异步数据传输与计算框架,计算与数据传输处理同时进行,可以掩盖掉大部分的IO通信;在单节点内部,利用向量化、openmp多线程等提高算法性能,同时设计分段矩阵计算方法,减少序列换入换出缓存的频率,提高缓存命中率。在集群多节点之间,利用MPI进行多线程的通信,将集群节点分为主节点与计算节点,主节点负责数据分发预处理、结果搜集处理,计算节点负责计算,计算完成将结果返回给主节点。通过以上技术手段,充分利用分布式资源,实现在集群上对LCS算法的优化。实验性能评估表明XLCS在单一Xeon Phi 31S1P卡上获得了3.61TCUPS峰值性能,在单一 Xeon Phi 7210卡上获得了 8.20TCUPS峰值性能。与在3块M2090GPUs卡上实现的并行LCS算法OCS相比,XLCS分别在KNC平台和KNL平台取得了 3.6倍和8.1倍加速比。XLCS在天河2号超级计算机上运行16个计算节点,获得了 93.84TCUPS性能。在郑州大学的KNL集群上,XLCS使用32个计算节点,获得了 312.30TCUPS性能。据我们目前所知,这是基于位并行的LCS算法在Xeon Phi集群上的首次实现。我们可以在https://github.com/wxiaoning/LongestCommon-Subsequence 上获取到本文的XLCS源代码。