【作者】 林江；

【导师】 唐敏； 童若锋；

【作者基本信息】 浙江大学 ， 计算机应用技术， 2011， 硕士

【摘要】 当前市场主流处理器的发展趋势是多核化／众核化,即通过提高处理器核心数目保持计算性能的持续增长。最新的图形处理器已经能够提高兆级的FLOPS理论峰值,远远超出了市场主流多核CPU。本文以国家自然科学基金项目(60803054)、浙江省自然科学基金项目(Y1100069)和AMD-浙江大学合作项目为研究背景,针对流式计算模型及其应用展开研究,主要工作包括：1、在NVIDIA CUDA平台上实现了基因序列比对的分值计算部分。本文设计实现的Diamond Tiled Wavefront算法的效率能够达到传统的Tiled Wavefront算法的1.7倍,更充分的利用GPU的并行性,更快的返回两个序列串的局部最大匹配值。2、在NVIDIA CUDA平台上实现了基因序列比对的精确比对部分。本文设计实现的流式序列比对算法首次在GPU上实现精确返回各元素的位置匹配结果。3、在ATI Stream平台上实现了三维模型凸包生成算法。在GPU上解决了CPU代码中大量应用vector、queue、map数据结构的问题。同时本文也介绍了一些用于辅助或优化上述算法实现的通用流式算法。4、在NVIDIA GeForce GTX285和ATI Radeon 5870图形处理器上使用CUDA和OpenCL实现了以上算法,并使用一系列模型进行了测试。本文算法对于基于GPU的算法加速研究具有一定的通用意义,并能延伸到其他生物计算、几何处理等领域的相关问题。更多还原

【Abstract】 The current trend of commodity processors is towards developing mulit-core/many-core processors. By increasing the number of processor cores, the peak performances are keeping high-speed improvement. The latest graphics processor units (GPUs) are capable of achieving tera FLOPS in theory, which is superior to the commodity multi-core CPUs. This paper focuses on the research of stream computing model on GPU and its applications. The research is supported in part by National Natural Science Foundation (60803054), Zhejiang Provincial Natural Science Foundation (Y1100069) and AMD-Zhejiang University cooperation project. The main contributions are:1. We achieved the score calculation of biological sequence alignment on NVIDIA CUDA. Designed and implemented a new parallel algorithm named Diamond Tiled Wavefront algorithm, which can achieve the efficiency 1.7 times the traditional Tiled Wavefront algorithm’s, better utilize the GPU parallelism, and faster return the local maximum match value of two sequences.2. We achieved the accurate full alignment of biological sequence alignment on CUDA. As we know, the stream sequence alignment algorithm we designed and implemented was the first GPU parallel algorithm that returns the accurate full alignment results.3. We achieved a new parallel algorithm of 3D convex hull generation on ATI Stream. The algorithm implemented map, queue and vector data structures in GPU. We also introduced other stream algorithms that used to aid and to optimize the algorithms mentioned above.4. We achieved the above algorithms in NVIDIA GeForce GTX285 and ATI Radeon 5870 GPU, using CUDA and OpenCL separately. And a series of models were tested.Our algorithms are general accelerating techniques on GPU, and can be extended to other problems in bioinformatics and geometric processing fields.更多还原