高燕军,,,,2

(1.太原理工大学 信息工程学院,山西 晋中 030600;2.昆士兰科技大学 电机工程及计算机科学学院,澳大利亚 布里斯班4001)

0 概述

全比较是一类特殊的计算问题,广泛存在于生物信息学、生物测定学和数据挖掘等领域[1]。在生物信息学中,通过比较不同物种的基因序列对谱系关系进行推断[2]。在生物测定学的研究中,一个典型的全比较问题是通过对生物测定学数据库中的大量数据进行成对比较来识别人的生理特征的,如面部识别、指形判断、手掌扫描[3]。在数据挖掘中,相似矩阵的计算是分类和聚类分析中的一个关键步骤,它表示被考虑对象之间的相似度[4-5]。序列比对、聚类分析[6]以及当前的研究热点全局网络比对均属于计算生物学和生物信息学中典型的全比较计算问题[7]。

全比较计算代表了一种典型的计算模式,即数据集中的每个数据都要和该数据集中的其他所有的数据做一次比较计算[8-9]。当数据集中的文件个数或者文件所包含的数据变大时,全比较计算的规模随之变大[10]。当前,针对一些特定领域的全比较问题已有解决方法被提出,如著名的BLAST[11]和ClustalW[12]。然而,这些方法要求在系统中的每个节点上存储所有的数据文件,增加了时间开销和通信成本,而且需要巨大的存储空间。此外,分布式系统(如开源的分布式处理框架Hadoop[13])被广泛地用于解决大规模的数据密集型的计算问题,包括全比较计算[14]。然而,由于没有考虑比较任务和数据之间的依赖关系,基于Hadoop的数据分配策略对于全比较计算是低效的[15]。……