毕业并行算法在多核环境下的研究与实现.pptVIP

计科 082班 ： 尹丽琼 指导老师：杨柳 研究结果 3 选题的背景、意义和要完成的任务 1 研究的方法和过程 2 总结 4 选题的背景、意义和要完成的任务 1 选题的背景 1、单核发展遇到瓶颈； 2、日益复兴的多媒体、科学计算、虚拟化等多个应用领域都呼唤更为强大的计算能力。 选题的背景、意义和要完成的任务 1 选题的意义 1、多核支持真正意义上的并行操作； 2、并行计算能够降低单个问题求解的时间。 选题的背景、意义和要完成的任务 1 要完成的任务 1、简单分析在多核环境下的快速排序算法和顺序查找算法； 2、详细分析在多核环境下的PAM算法。 研究的方法 研究的方法和过程 2 分析算法的内在并行性 分析并实现非多核环境下的串行算法 算法在多核环境下的并行实现 串行算法 分析算法 并行算法 快速排序算法的研究过程 研究的方法和过程 2 单核环境下快速排序算法的实现 串行算法 经过一趟排序以后，算法存在并行性 分析算法 对划分后的两个序列分别用两个线程递归完成 并行算法 void QuickSort_parallel(code array[],int Begin, int End) { int r; if(BeginEnd) { r=Partition(array,Begin,End);//Partition返回枢纽元素的数组下标 #pragma omp parallel { #pragma omp sections nowait { #pragma omp section { QuickSort_parallel(array,Begin,r); } #pragma omp section { QuickSort_parallel(array,r+1,End); } } } } } 顺序查找算法的研究过程 研究的方法和过程 2 单核环境下顺序查找算法的实现 串行算法 对数据进行分区后，算法存在并行性 分析算法 将子区间分配给不同的线程并行执行 并行算法 PAM算法的研究过程 研究的方法和过程 2 算法思想： PAM算法采用的是划分的思想及最小化类内差异准则来对数据对象进行聚类，此过程通过中心点的迭代轮换来完成。 首先随机选择k（k代表要划分的簇个数）个对象作为每个簇的初始中心，并将剩余的对象分别根据它们与中心点间的距离分配给最近的一个簇；然后反复地用非中心点替换中心点，不断地改进聚类的质量。直到聚类质量不发生变化时则算法收敛。每次迭代，PAM只选出最优的方案，也就是使得簇内差异和减少最多的方案，进行中心点替换。 处理流程： 输入：聚类个数K，以及包含N个数据对象的样本集。 输出：满足标准的K个聚类。 处理流程： （1）从N个数据对象中任意选择K个对象作为初始聚类中心； （2）根据每个聚类中所有对象的中心对象，计算样本集中每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分； （3）重新计算每个（有变化）聚类的中心对象； （4）循环上述流程（2）到（3），直到每个聚类不再发生变化为止。 PAM算法的研究过程 研究的方法和过程 2 将数据对象分组成具有高相似度的K个簇 串行算法 计算中心替换代价及替换中心点时具有并行性 分析算法 用不同的线程来计算各簇的中心点以及各中心点的替换 并行算法 int GetIndex(double value,double * c) //value为当前点，c为中心点集 { int i=0; int index=i; double min=fabs(value-c[i]); #pragma omp critical #pragma omp parallel for for(i=0;iK;i++) { #pragma omp critical (min) if(fabs(value-c[i])min) //如果比当前距离更小，更新最小的中心点序号和距离值 { index=i; min=fabs(value-c[i]); } } return index; } 共享存储并行编程语言 研究的方法和过程 2 实验平台 快速排序和顺序查找算法研究结果 研究结果 3 PAM算法研究结果 本设计的收获：巩固了旧的知识、学到了新的技术、增强了自主学习的能力。 本设计