Department of Computer Science, Stanford University, Stanford, California 94305, United States.
J Chem Inf Model. 2011 Sep 26;51(9):2345-51. doi: 10.1021/ci200235e. Epub 2011 Sep 7.
Similarity measures based on the comparison of dense bit vectors of two-dimensional chemical features are a dominant method in chemical informatics. For large-scale problems, including compound selection and machine learning, computing the intersection between two dense bit vectors is the overwhelming bottleneck. We describe efficient implementations of this primitive as well as example applications using features of modern CPUs that allow 20-40× performance increases relative to typical code. Specifically, we describe fast methods for population count on modern x86 processors and cache-efficient matrix traversal and leader clustering algorithms that alleviate memory bandwidth bottlenecks in similarity matrix construction and clustering. The speed of our 2D comparison primitives is within a small factor of that obtained on GPUs and does not require specialized hardware.
基于二维化学特征密集位向量比较的相似性度量方法是化学信息学中的主要方法。对于包括化合物选择和机器学习在内的大规模问题，计算两个密集位向量的交集是压倒性的瓶颈。我们描述了此原语的有效实现，以及使用现代 CPU 功能的示例应用，这些功能允许相对于典型代码提高 20-40 倍的性能。具体来说，我们描述了在现代 x86 处理器上进行种群计数的快速方法，以及缓存高效的矩阵遍历和领先聚类算法，这些算法缓解了相似性矩阵构建和聚类中的内存带宽瓶颈。我们的 2D 比较原语的速度与在 GPU 上获得的速度相差不大，并且不需要专用硬件。
