论文部分内容阅读
在计算机领域中,有一类问题具有这样的特点:结果元素的计算依赖于前面连续几个已计算完成的元素,而且每次可以并行计算的元素个数是存在着一定的相互关系。本文把具有以上计算流程特征的问题描述模型称之为对角线模型。对角线模型的应用非常广泛,例如生物信息学中的局部序列比对算法、自然语言处理领域中的上下文无关文法等。而符合这个模型的算法,一般都要处理非常巨量的数据。而且随着社会的发展以及技术的进步,数据量以指数级的速度在增长。因此,提高这个模型的计算效率就显得越来越重要。为了满足高性能计算的需求,目前已经存在着多种多样的高性能计算平台。GPGPU平台是其中之一。相对于其他平台,GPGPU平台的优势在于可以在不增加硬件成本的条件,利用GPU固有的高计算能力和高并行性来提高算法的执行效率。而且随着硬件技术的进步以及OpenCL模型的提出,使得通用计算领域中的算法越来越来适合且容易地在这个新型平台上实现。因此,如何利用GPGPU平台来提高通用计算的速度已成为计算机研究的热点。在GPGPU平台上,已经有许多学者针对符合对角线模型的问题提出了解决方案。例如,Edans等人提出分块的思想来在GPGPU平台上实现大规模序列局部比对算法;Yan Zhang曾经在论文中提出在GPGPU平台上实现三对角线性方程组解法的。但是,这些文献皆是基于具体的问题而提出,不同的问题使用不同的方法。而并没有针对对角线模型提出一个通用解决方案。本文的意义在于为对角线模型提出一个通用解决方案使得这个模型可以容易且高效地映射到GPGPU平台上。首先,本文详细地描述了对角线模型,并仔细地分析了这个模型的特点。然后,分析GPGPU平台的特点以及一些通用性能优化原则。接着在前面的基础上,提出一个通用解决方案把问题模型映射到GPGPU平台上。最后,用四个符合对角线模型的典型案例验证方案的可行性以及有效性。从最后的实验结果可知,通用解决方案可以使得问题很容易地映射到GPGPU平台上。而且,实验数据说明每个问题都取得不错的实验效果。Smith-Waterman算法可以获得最高100x以上的性能提升,而平均情况也有50x左右。排序问题中的两个算法也取得了约为7、8倍的加速。而解三对角线性方程组算法则可以达到10倍的性能提升。上下文无关文法由于算法的特点,也取得了4~5倍的加速。