蔡德霞， 钟 诚， 韦兴柳， 林孔升

（广西大学 计算机与电子信息学院，广西 南宁 530004）

任意2序列公共元素的查找问题可应用于数据库、统计、运筹学和组合学等领域。文献［1］研究了由有序序列x和y组成的排序矩阵上的并行查找问题，并指出可使用排序矩阵上的并行查找思想来实现任意2序列公共元素的查找问题。文献［2］设计了PRAM模型上任意2序列公共元素的并行查找算法。近年来，多核结构发展成为微处理器的主流，它支持缓存高效和线程级并行［3］，具有高度的并行处理能力［4］。文献［5］采取将线性方程组的增广矩阵按行划分并合理分布到各级缓存，各个处理核以多线程方式并行计算矩阵行的方法，设计了多核系统上线程级并行求解n阶线性方程组的算法。文献［6］利用软件多线程技术和多核结构中的多级Cache机制，基于可分负载理论的最优原则，针对Multisets数据序列的特点，提出一种多轮非周期性的数据序列最优分配模型，进而设计实现进程级与线程级并行的Multisets排序算法。文献［7］从综合提高多核计算机共享二级缓存的利用率、矩阵存储的数据结构优化、计算与访存重叠操作、缓存无关等角度出发，提出适合矩阵乘积问题并行计算的数据分布和调度策略，设计实现非递归、高效和可扩展的矩阵乘积并行算法。

本文采用数据多级分块技术、数据局部性原理和循环并行优化方法，充分利用多核处理器的多级存储和多线程技术，设计实现多核系统上存储高效、线程级并行、扩展性好的任意2序列公共元素的并行查找算法。……