《（毕业设计论文）并行算法在多核环境下的设计与实现》由会员分享，可在线阅读，更多相关《（毕业设计论文）并行算法在多核环境下的设计与实现（61页珍藏版）》请在金锄头文库上搜索。
1、精品毕业设计（论文）毕业设计（论文）题 目 并行算法在多核环境下的设计与实现学学 院院计算机与电子信息学院计算机与电子信息学院专专 业业计算机科学与技术计算机科学与技术学学 号号0807100321姓姓 名名指导教师指导教师二零一二年五月二十五日二零一二年五月二十五日精品摘 要在信息激增的年代，我们强烈地要求计算机的处理器更快更强，在这种压力之下，双核乃至多核应运而生，多核时代已经来临。多核技术在多线程多任务等领域发挥着极大的作用，因而对软件的运行效率以及软件的开发起到了很大的影响。在多核对软件起着重大的影响的同时，它也面临着一些问题，如能耗、性能瓶颈等都是未来要解决的问题。本文根据多核的特点
2、，简略分析快速排序及顺序查找算法的思想及其描述，并详细分析其内在并行性，提出算法基于多核虚拟环境下的改进方法，设计出适合多核平台的并行算法，使用 OpenMP 并行编程模型来实现；重点分析 PAM 聚类算法，PAM 算法是一种寻找初始聚类中心的新方法，算法首先计算样本间的距离，然后根据样本点之间的距离寻找有可能是一类的数据，依据这些样本点形成初始聚类中心从而得到更好的聚类效果。实验结果都表明并行算法对多核环境有很好的适应性，算法在多核环境下比在传统环境下具有更高的运行效率。关键词：多核 OpenMP 并行计算 快速排序 顺序查找 PAM 算法精品Research and Implementat
3、ion of Parallel algorithm in Multicore EnvironmentAbstractIn the information explosion era, we strongly demand computer processors faster and stronger, in this kind of pressure, binucleated and multinucleated emerge as the times require, multi-core era has arrived. In the field of multi-threaded mul
4、ti-tasking, multi-core technology play a great role, and thus play a very significant impact on the operating efficiency of the software and software development. In a multi-check software plays a significant impact at the same time, it is also facing some problems, such as energy consumption, perfo
5、rmance bottlenecks are the future issues to be addressed. Based on the characteristics of multi-core, This article will briefly analyze the idea of quick sort and sequential search algorithm and its description of its inherent parallelism, and present the improved algorithm is based on multi-core vi
6、rtual environment, to design a parallel algorithm for multi-core platform. This article will focus on analyzing the PAM clustering algorithm, the PAM algorithm is looking for a new method of initial cluster centers, the algorithm first calculate the distance between samples, then based on the distan
7、ce between sample points to find a class data, based on these sample points to form the initial cluster centers in order to get better clustering results. The experimental results show that parallel algorithms for multi-core environments have a good adaptability.The algorithm has a higher operating
8、efficiency in multi-core environment than in the traditional environment.Key words：Multicore OpenMP Parallel computing Quicksort Sequential search PAM algorithm精品精品目 录摘 要 .IAbstract.II目 录 .I第一章 绪论.11.1 单核 CPU 的发展限制11.2 多核的引进11.3 多核的现状2第二章 多核技术简介.42.1 多核概述42.1.1 多核 CPU 硬件架构.52.1.2 多核编程模型.52.2 单核与多核的区
9、别62.2.1 单核、多处理器以及多核结构之间的简单对比.62.2.2 超线程技术与多核体系结构的联系与区别.72.2.3 单核与多核平台上的多线程技术对比.72.2 多核对开发人员的影响72.3 多核计算发展趋势82.4 潜在的问题92.5 OpenMP 编程简介.102.5.1 OpenMP 基本原理及特征102.5.2 OpenMP 程序设计与实现112.5.3 OpenMP 编程环境12第三章 排序和查找在多核环境下的研究与实现.143.1 并行计算平台143.2 多核并行设计方法143.2 基本算法研究163.2.1 快速排序算法.163.2.2 顺序查找算法.193.2.3 实验结
10、果分析.21精品第四章 PAM 算法在多核环境下的改进与研究.234.1 聚类算法简介234.2 PAM 算法研究.244.2.1 算法思想.244.2.2 算法过程.244.2.3 中心选择算法.254.3 PAM 算法的改进.254.3.1 PAM 算法优化254.3.2 并行 PAM 算法实现264.4 实验结果分析27第五章 总结.295.1 本文的主要工作和贡献295.2 下一步的工作29参考文献.30附录.32英文参考文献译文.32英文参考文献原文.34程序源代码.37致谢.56精品第一章 绪论1.1 单核 CPU 的发展限制从 20 世纪 70 年代开始，处理器得到了突飞猛进的发
11、展，许多知名厂家如 Intel1、AMD2和 IBM3等都已经将他们的芯片流水线从单核处理器的生产转变成了多核处理器的生产，纷纷推出了一代又一代处理器，造就了处理器发展史上一座又一座的里程碑，这已经促使计算机供应商将他们的重心转移到销售拥有多核的台式计算机，如 Dell、HP 和 Apple 等。随着处理器集成晶体管数量的增多，主频越来越高，而处理器的性能也越来越强大。早在 1965 年，Intel CEO 戈登摩尔就已经预见了处理器的发展趋势，提出了著名的摩尔定律4芯片的晶体管数量每一年半增长一倍左右。摩尔定律从 20 世纪 70 年代起，一直引导着计算机行业以及半导体行业的前进，在过去的
12、30 年里，处理器的发展也在不断的验证这个定律。到了 21 世纪，摩尔定律在受到广泛关注的同时，它的局限性也遭到了越来越多的争议5-6。我们知道，处理器性能的提高，依赖于两个方面的原因：一是半导体工艺的逐渐进步，二是处理器体系结构的不断发展。它们相辅相成，互相刺激、促进对方的发展。但是到了 21 世纪，随着芯片制作工艺的不断进步，从体系结构来看，传统的处理器体系结构技术已经面临瓶颈，很难单纯地靠通过提高主频来提升性能，且主频的提高同时也带来功耗的提高，这也是直接促使单核转向多核的深层次原因；从应用需求来看，日益复兴的多媒体、科学计算、虚拟化等多个应用领域都呼唤更为强大的计算能力。在这样的背景下
13、，各主流处理器厂商纷纷将产品战略转向多线程、多内核。1.2 多核的引进在单核发展遇到瓶颈后，目前的芯片厂商的目光都转向了多核 CPU 的开发，通过多核 CPU 进行并行计算来提高计算的性能7。单 CPU 的计算能力是无法与多 CPU 的计算能力相比的，现在使用的很多服务器都是多 CPU精品的，所以即使未来单核的运算和管理能得到突破，计算机硬件中也仍然需要有多个 CPU 以获取更高的性能，软件中仍需要采取多核计算以取得更高的性能。多核计算将成为未来发展的趋势，多核编程也将成为程序员必须掌握的一门技术。多核内的多线程运行是并行的，即多个线程同时执行，同一时刻可以有多个线程执行。多核体系8通过增加计
14、算机中物理处理器的数量来有效的利用线程的并行性。多核处理器系统多个线程或者进程能够在多个处理器内核上同时执行，它支持真正意义上的并行操作。并行计算9能够降低单个问题求解的时间，增加问题求解规模，提高问题求解精度，与在多机上同时执行多个串行程序相比，具有更高的可用性以及吞吐率。研究表明，多核处理器相比相同工艺及相同面积的单核处理器具有如下优势：1、逻辑简单：相对于超标量微处理器结构和超长指令字结构而言，单芯片多处理器结构的控制逻辑复杂性要明显低很多。相应的单芯片多处理器的硬件实现必然要简单得多。2、高主频：单芯片多处理器结构的控制逻辑相对简单，包含极少的全局信号，因此在同等工艺条件下，单芯片多处
15、理器的硬件实现要比超标量微处理器和超长指令字微处理器具有更高的工作频率。3、低通信延迟：由于多个处理器集成在一块芯片上，且采用共享Cache 或者内存的方式，多线程的通信延迟明显降低。4、低功耗：调节电压频率、负载优化分布等，可有效降低 CMP 功耗。5、设计和验证周期短：微处理器厂商一般采用现有的成熟多核处理器作为处理器核心，从而可缩短设计和验证周期，节省研发成本。1.3 多核的现状多核概念的出现，要追溯到 1995 年。在 2002 年推出的超线程概念可以说是桌面多核处理器的模拟概念，直到 2005 年双核处理器的推出，多核开始启航，2006 年四核处理器预期推出宣布多核时代的来临。近年来
16、，微处理器走多核之路已经不仅仅是一个口号，它已经成为我们每天必须面对的现实，2007 年，通观市场上的 PC 机、服务器、笔记本电脑，采用多核精品处理器已经成为主流。多核 CPU 相对于单核产品的一个最突出的优势就是出色的多任务处理性能，对于本身有此需求的用户来说，这自然是一大福音，可以更为迅速地提升工作效率，通俗地说是可以在同一时间内让电脑干更多的事情，比如我们打开 IE 浏览器上网，看似简单的一个操作，实际上浏览器进程会调用代码解析、Flash 播放、多媒体播放、Java、脚本解析等一系列线程，这些线程可以并行地被多核处理器处理，因而运行速度会加快。从单核到双核，多任务性能的提升是非常明显的，但是从双核到四核，提升的幅度就相对减少，并不是简单的“双倍”关系。因此，随着核心数量的增加，在软、硬件上如何更好地提高多核产品的并行处理效率将是今后厂商努力发展的一个方向。另一方面，对于并不习惯多任务操作的用户来说，使用多核处理器是否存在着浪费资源的现象呢？其实根据目前所作的调查，即使是非常“专一”的用
