精华内容
下载资源
问答
  • 快速排序并行实现MPI

    千次阅读 2019-04-26 15:34:46
    常规的快速排序,先在数组中选取一个基准点,将数组分区为小于基准点和大于基准点(相同的数可以到任一边),对分区的子数组递归的执行分区的操作,当子数组长度为1时退出递归。此时数组就完成了排序过程。 对快排的...

    简介

    常规的快速排序,先在数组中选取一个基准点,将数组分区为小于基准点和大于基准点(相同的数可以到任一边),对分区的子数组递归的执行分区的操作,当子数组长度为1时退出递归。此时数组就完成了排序过程。
    对快排的过程分析可以发现,分区以及对子数组排序的过程均可以并发执行,这里首先对数组进行分区,生成分区数组,为了保证不同分区不受到影响需要先完成分区再进行排序。
    处理器个数:4
    数组长度:1000
    具体过程为:先在0号处理器创建一个1000维的数组,将数组广播道所有处理器,在0处理器对数组进行partition,将根据pivot值划分为两个子数组,左边的数组仍然留在0号进程,右边子数组分配给1号处理器,然后对0号和1号处理器中的数组分别进行递归操作,将0处理器中数组分给2号处理器,将1号处理器数据分给3号处理器,当没有可用的处理器时,数据划分完毕,开始各自进行快速排序,排序结束后,逐级向上返回,最后数据全部返回0处理器,排序结束。

    代码

    	#include "StdAfx.h"
      	#include "stdafx.h"
      	#include"mpi.h"
    	#include<time.h>
      	#include<iostream>
      	#include <stdlib.h>
      	#include <stdio.h>
      	using namespace std;
      	#define TRUE 1
        #define SIZE 10000
      	
    	
    double wht_start_time,wht_end_time, end_time, start_time;  	
    int Partition(int *wht_data,int wht_start,int wht_end)
      {
      	int wht_pivo;
      	int wht_i, wht_j;
      	int wht_tmp;
      	wht_pivo=wht_data[wht_end];
      	wht_i=wht_start-1; /*wht_i(活动指针)*/
      	for(wht_j=wht_start;wht_j<wht_end;wht_j++)
      		if(wht_data[wht_j]<=wht_pivo)
      		{
      			wht_i++; /*wht_i表示比wht_pivo小的元素的个数*/
      			wht_tmp=wht_data[wht_i];
      			wht_data[wht_i]=wht_data[wht_j];
      			wht_data[wht_j]=wht_tmp;
      		}
      	wht_tmp=wht_data[wht_i+1];
      	wht_data[wht_i+1]=wht_data[wht_end];
      	wht_data[wht_end]=wht_tmp; /*以wht_pivo为分界,wht_data[wht_i+1]=wht_pivo*/
      	return wht_i+1;
      }
    
    void QuickSort(int *wht_data,int wht_start,int wht_end)
    {
      	int wht_r;
      	int wht_i;
      	if(wht_start<wht_end)
      	{
      		wht_r=Partition(wht_data,wht_start,wht_end);
      		QuickSort(wht_data,wht_start,wht_r-1);
      		QuickSort(wht_data,wht_r+1,wht_end);
      	}
    }
      	
    
    	/*功能:求2的wht_num次幂*/
    int exp2(int wht_num)
    {
      	int wht_i;
      	wht_i=1;
      	while(wht_num>0)
      	{
      		wht_num--;
      		wht_i=wht_i*2;
      	}
      	return wht_i;
    }
    
    
    	/*功能:求以2为底的wht_num的对数*/
    int log2(int wht_num)
    {
      	int wht_i, wht_j;
      	wht_i=1;
      	wht_j=2;
      	while(wht_j<wht_num)
      	{
      		wht_j=wht_j*2;
      		wht_i++;
      	}
      	if(wht_j>wht_num)
      		wht_i--;
      	return wht_i;
    }
      	 
      	 
      	/*
      	* 函数名: para_QuickSort
      	* 功能:并行快速排序,对起止位置为wht_start和wht_end的序列,使用2的wht_m次幂个处理器进行排序
      	* 输入:无序数组wht_data[1,n],使用的处理器个数2^wht_m
      	* 输出:有序数组wht_data[1,n]
      	*/
    
    
    void para_QuickSort(int *wht_data,int wht_start,int wht_end,int wht_m,int id,int MyID)
    {
    	int wht_i, wht_j;
      	int wht_r;
      	int MyLength;
      	int *wht_tmp;
      	MPI_Status status;
      	MyLength=-1;
      	/*如果可供选择的处理器只有一个,那么由处理器id调用串行排序*/
    	if(wht_m==0)
      	{
      		wht_start_time=MPI_Wtime();
      		if(MyID==id)
      		QuickSort(wht_data,wht_start,wht_end);
      		return;
      	}
      	wht_start_time=MPI_Wtime();
      	/*由第id号处理器划分数据,并将后一部分数据发送到处理器id+exp2(wht_m-1),对应于算法步骤(1.2,1.3)*/
      	if(MyID==id)
      	{
      		/*将当前的无序区R[1,n]划分成左右两个无序的子区R[1,wht_i-1]和R[wht_i,n](1≤wht_i≤n)*/
    		/*(1.2) Pid: wht_r=patrition(wht_data,wht_i,wht_j)*/
      		wht_r=Partition(wht_data,wht_start,wht_end);
      		MyLength=wht_end-wht_r;
      	/*(1.3) Pid swht_end wht_data[wht_r+1,wht_m-1] to P(id+2m-1) */
      	/* {MyLength表示发送缓冲区地址;*/
      	/* 发送元素数目为1; */
      	/* MyID是消息标签 } */
      		MPI_Send(&MyLength,1,MPI_INT,id+exp2(wht_m-1),MyID,MPI_COMM_WORLD);
      		/*若缓冲区不空,则第id+2m-1号处理器取数据的首址是wht_data[wht_r+1]*/
      		if(MyLength!=0)
      			MPI_Send(wht_data+wht_r+1,MyLength,MPI_INT,id+exp2(wht_m-1),MyID,MPI_COMM_WORLD);
      	}
      	/*处理器idex+p2(wht_m-1)接受处理器id发送的消息*/
      	if(MyID==id+exp2(wht_m-1))
      	{
      		MPI_Recv(&MyLength,1,MPI_INT,id,id,MPI_COMM_WORLD,&status);
      		if(MyLength!=0)
      		{
      			wht_tmp=(int *)malloc(MyLength*sizeof(int));
      			if(wht_tmp==0) printf("Malloc memory error!");
      				MPI_Recv(wht_tmp,MyLength,MPI_INT,id,id,MPI_COMM_WORLD,&status);
      		}
      	}
      	/*递归调用并行排序,对应于算法(1.4,1.5)*/
      	/*用2^wht_m-1个处理器对wht_start--(wht_r-1)的数据进行递归排序*/
      	wht_j=wht_r-1-wht_start;
      	MPI_Bcast(&wht_j,1,MPI_INT,id,MPI_COMM_WORLD);
      	/*(1.4) para_quicksort(wht_data,wht_i,wht_r-1,wht_m-1,id)*/
      	if(wht_j>0)
      		para_QuickSort(wht_data,wht_start,wht_r-1,wht_m-1,id,MyID);
      	/*用2^wht_m-1个处理器对(wht_r+1)--wht_end的数据进行递归排序*/
      	wht_j=MyLength;
      	MPI_Bcast(&wht_j,1,MPI_INT,id,MPI_COMM_WORLD);
      	/*(1.5) para_quicksort(wht_data,wht_r+1,wht_j,wht_m-1,id+2m-1)*/
      	if(wht_j>0)
      		para_QuickSort(wht_tmp,0,MyLength-1,wht_m-1,id+exp2(wht_m-1),MyID);
      	/*将排序好的数据由处理器id+exp2(wht_m-1)发回id号处理器,对应于算法/
      	/*(1.6) P(id+2m-1) swht_end wht_data[wht_r+1,wht_m-1] back to Pid */
      	if((MyID==id+exp2(wht_m-1)) && (MyLength!=0))
      		MPI_Send(wht_tmp,MyLength,MPI_INT,id,id+exp2(wht_m-1),MPI_COMM_WORLD);
      	if((MyID==id) && (MyLength!=0))
      		MPI_Recv(wht_data+wht_r+1,MyLength,MPI_INT,id+exp2(wht_m-1),id+exp2(wht_m-1),MPI_COMM_WORLD,&status);
      }
    
    /*串行快速排序*/
    int partition(int *array,int p,int r){
        int x=array[r];     //以最后一个作为主元(pivot element)
        int i=p-1;
        for(int j=p;j<r;++j){
            if(array[j]<x){
                i++;
                swap(array[i],array[j]);
            }
        }
        swap(array[r],array[i+1]);
        return i+1;
    }
    void quicksort(int *array,int p,int r){
        if(p<r){
            int q=partition(array,p,r);
            quicksort(array,p,q-1);
            quicksort(array,q+1,r);     
        }
    }
    
    	/*
      	* 函数名: main
      	* 功能:实现快速排序的主程序
      	* 输入:argc为命令行参数个数;
      	* argv为每个命令行参数组成的字符串数组。
      	* 输出:返回0代表程序正常结束
      	*/
    int main(int argc,char *argv[])
    {
    
    	double wht_dataSize;
      	int *wht_data;
    	int *wht_data1;
      	/*MyID表示进程标志符;SumID表示组内进程数*/
      	int MyID, SumID;
      	int wht_i, wht_j;
      	int wht_m, wht_r;
      	MPI_Status status;
      	/*启动MPI计算*/
      	MPI_Init(&argc,&argv);
      	/*MPI_COMM_WORLD是通信子*/
      	/*确定自己的进程标志符MyID*/
      	MPI_Comm_rank(MPI_COMM_WORLD,&MyID);
      	/*组内进程数是SumID*/
      	MPI_Comm_size(MPI_COMM_WORLD,&SumID);
      	/*根处理机(MyID=0)获取必要信息,并分配各处理机进行工作*/
    	if(MyID==0)
      	{
      		/*获取待排序数组的长度*/
      		wht_dataSize=SIZE;
      		wht_data=(int *)malloc(wht_dataSize*sizeof(int));
      		wht_data1=(int *)malloc(wht_dataSize*sizeof(int)); 
      	 
      		/*动态生成待排序序列*/
      		srand(396);
      		printf("排序前的随机数组为 :\n");
      		for(wht_i=0;wht_i<wht_dataSize;wht_i++)
      		{
      			wht_data[wht_i]=(int)rand();
    			wht_data1[wht_i]=wht_data[wht_i];
      			if(wht_i<100)
    				printf("%d ",wht_data[wht_i]);
      		}
    		printf("... ...\n");
      	}
      	wht_m=log2(SumID);
      	/* 从根处理器将数据序列广播到其他处理器*/
      	/*{"1"表示传送的输入缓冲中的元素的个数, */
      	/* "MPI_INT"表示输入元素的类型, */
      	/* "0"表示root processor的ID } */
      	MPI_Bcast(&wht_dataSize,1,MPI_INT,0,MPI_COMM_WORLD);
      	/*ID号为0的处理器调度执行排序*/
      	para_QuickSort(wht_data,0,wht_dataSize-1,wht_m,0,MyID);
      	wht_end_time=MPI_Wtime();
      	/*ID号为0的处理器打印排序完的有序序列*/
    	
      	if(MyID==0)
      	{
      		printf("排序后的有序数组为 :\n");
      		for(wht_i=0;wht_i<wht_dataSize;wht_i++)
      			if(wht_i<100)
    				printf("%d ",wht_data[wht_i]);
      		printf("... ...\n");
    		
    		/*计算串行时间*/
    		start_time=MPI_Wtime();
    		quicksort(wht_data1,0,SIZE-1);
    		end_time=MPI_Wtime();
      	
    		printf("并行时间 = %fs\n",wht_end_time-wht_start_time);
    		printf("串行时间 = %fs\n",end_time-start_time);
    		printf("加速比为:%f \n", (end_time-start_time)/(wht_end_time-wht_start_time));
      	}
      	 
      	MPI_Finalize(); //结束计算
    }
    

    执行结果

    在这里插入图片描述

    展开全文
  • 并行计算 c# 快速排序

    2015-12-15 15:52:10
    快速排序并行实现 串行并行时间 C#语言
  • 2、熟悉快速排序并行算法 3、实现快速排序并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的...
  • 2、熟悉快速排序并行算法 3、实现快速排序并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的...
  • 快速排序并行算法

    2012-05-17 12:48:45
    快速排序并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
  • 并行快速排序

    千次阅读 2014-04-09 16:10:45
    并行快速排序 感谢网友浅水清流投递本稿。 并发算法是多核时代开始流行的技术趋势,比如tbb,ppl都提供了大量有用的并发算法。 经典算法中,排序是一个很适合采用分治法并发的场合,比如快速排序。 ...

    并行快速排序

    感谢网友浅水清流投递本稿。

    并发算法是多核时代开始流行的技术趋势,比如tbbppl都提供了大量有用的并发算法。

    经典算法中,排序是一个很适合采用分治法并发的场合,比如快速排序

    常规的快速排序,先在数组中选取一个基准点,将数组分区为小于基准点和大于基准点(相同的数可以到任一边),对分区的子数组递归的执行分区的操作,当子数组长度为1时退出递归。此时数组就完成了排序过程。

    01 int partition(int* array, int left, int right)
    02 {
    03         int index = left;
    04         int pivot = array[index];
    05         swap(array[index], array[right]);
    06         for (int i=left; i<right; i++)
    07         {
    08                 if (array[i] > pivot)    // 降序
    09                         swap(array[index++], array[i]);
    10         }
    11         swap(array[right], array[index]);
    12         return index;
    13 }
    14  
    15 void qsort(int* array, int left, int right)
    16 {
    17         if (left >= right)
    18                 return;
    19         int index = partition(array, left, right);
    20         qsort(array, left, index - 1);
    21         qsort(array, index + 1, right);
    22 }

    对快排的过程分析可以发现,分区以及对子数组排序的过程均可以并发执行,这里首先对数组进行分区,生成分区数组,为了保证不同分区不受到影响需要先完成分区再进行排序。

    01 template <typename key, typename container >void parallel_sort(container & _container)template <typename key, typename container >
    02 void partition_less(std::vector<key> * vless, container * _container, key privot){
    03 for(size_t i = 0; i < (*_container).size(); i++){
    04         if ((*_container)[i] < privot){
    05             vless->push_back((*_container)[i]);
    06         }
    07     }
    08 }
    09  
    10 template <typename key,  typename container >
    11 void partition_more(std::vector<key> * vmore, container * _container, key privot){
    12 for(size_t i = 0; i < (*_container).size(); i++){
    13         if ((*_container)[i] >= privot){
    14             vmore->push_back((*_container)[i]);
    15         }
    16     }
    17 }

    在完成分区之后,递归执行排序操作,并将排序好的分区重新写入待排序数组。

    01 template <typename key, typename container >
    02 int sort_less(container * _container, std::vector<key> & vless, boost::atomic_uint32_t * depth){
    03     parallel_sort_impl<key>(&vless, *depth);
    04  
    05     for(size_t i = 0; i < vless.size(); i++){
    06         (*_container)[i] = vless[i];
    07     }
    08  
    09     return 0;
    10 }
    11  
    12 template <typename key, typename container >
    13 int sort_more(container * _container, std::vector<key> & vmore, boost::atomic_uint32_t * depth){
    14     parallel_sort_impl<key>(&vmore, *depth);
    15  
    16     size_t pos = (*_container).size()-vmore.size();
    17     for(size_t i = 0; i < vmore.size(); i++){
    18         (*_container)[i+pos] = vmore[i];
    19     }
    20  
    21     return 0;
    22 }
    23  
    24 template <typename key, typename container >
    25 void parallel_sort_impl(container * _container, boost::atomic_uint32_t & depth){
    26     if (_container->size() < threshold || depth.load() > processors_count()){
    27         std::sort(_container->begin(), _container->end());
    28     }else{
    29         key privot = (*_container)[_container->size()/2];
    30  
    31     std::vector<key> vless, vmore;
    32     auto partition_result = std::async(std::launch::async, partition_less<key, container>, &vless, _container, privot);
    33     partition_more(&vmore, _container, privot);
    34     partition_result.get();
    35  
    36         auto result = std::async(std::launch::async, sort_less<key, container>, _container, vless, &depth);
    37         sort_more(_container, vmore, &depth);
    38         result.get();
    39     }
    40 }

    这里采取了一个有趣的策略,就是通过数组的大小,计算出排序好的元素在原数组中的位置(这样即使是并发的访问数组,但是因为不同的线程各自访问的自己的下标位置,所以仍然是线程安全的),然后将排序好的数组直接写入到原数组,完成整个排序。

    这里的并发采用了c++11中的promise:http://imcc.blogbus.com/logs/174131661.html

    (全文完)如果您喜欢此文请点赞,分享,评论。


    展开全文
  • #pragma omp parallel default(none) shared(C,D,len2) //private(i)快速排序并行 { #pragma omp parallel sections { #pragma omp section quicksort(C,0,len2-1); //对C排序 #pragma omp section ...
  • MPI实现并行快速排序

    热门讨论 2010-05-11 11:38:27
    利用MPI实现快速排序并行算法,算法使用C语言实现
  • 4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序并行实现的流程图 8、完成快速排序并行算法的实现
  • 实验二 快速排序的MPI并行程序 一实验时间 2015年11月5日 二实验名称 快速排序的mpi并行化设计 三内容与要求 1内容快速排序以下简称快排是对冒泡排序的一种改进它的思想是通过一趟排序将要排序的数据分割成独立的两...
  • 并行环境下快速排序函数代码段,打开后更改后缀txt为cpp即可使用
  • 该程序是在 gcc 4.7.3 和 openmp 3.1 上开发的。
  • 实验二 快速排序的MPI并行程序 实验时间2015年11月5日 实验名称 快速排序的mpi并行化设计 内容与要求 1 内容快速排序(以下简称快排)是对冒泡排序的一种改进它的思想是通 过一趟排序将要排序的数据分割成独立的两部分...
  • 快速排序并行程序 QuickSort MPI

    热门讨论 2008-10-06 16:37:47
    用MPICH实现的快速排序算法,可以在高性能计算机环境下运行,大家可以学习一下
  • 如题所示,使用go语言编程实现并行快速排序算法,请大神们帮帮忙~
  • 我们班一起做出来的并行计算的杰作,值得收藏呀!!!
  • 针对没有显式拓扑关系的质点云,提出了一种并行快速排序算法。 引入了莫顿阶并将其用于合并一维数据。 生成不规则模型的质量点云,对应的地址代码称为Morton码,这些点存储在八叉树结构链中。 然后使用基于欧几里得...
  • 基于多线程的并行快速排序算法实现 1. 快速算法(Quick Sort)介绍 快速排序(Quick Sort)是一种经典的排序算法,基于递归实现,由于其实现方式简单可靠、平均时间复杂度为O(nlogn) (最坏情况O(n^2)), 被广泛采用。...

    基于多线程的并行快速排序算法实现

    1. 快速算法(Quick Sort)介绍

    快速排序(Quick Sort)是一种经典的排序算法,基于递归实现,由于其实现方式简单可靠、平均时间复杂度为O(nlogn) (最坏情况O(n^2)), 被广泛采用。一个QuickSort算法实现如下(基于c++):

    class Sorter {
    public:
        template<typename IterType>
        static void quicksort(IterType first, IterType last)
        {
            auto distance = std::distance(first, last);                  // #GGG
            if (distance < 2) {
                return;
            } else if (distance == 2 && (*first > *(first+1))) {
                std::swap(*first, *(first+1));
            }                                                            // #HHHH
    
            auto mid = partition(first, last);  // #AAA
            quicksort(first, mid);              // #BBB
            quicksort(mid+1, last);             // #CCC
         }
    
    private:
        template<typename IterType>
        static IterType partition(IterType first, IterType last)
        {
            // Always pick the last data as pivot, can be optimzed more
            auto pivot = *(last-1);
    
            IterType it1 = first;
            IterType it2 = first;
            while (it2+1 != last) {
                if (*it2 <= pivot) {
                    std::swap(*it1, *it2);
                    it1++;
                }
    
                it2++;
            }
    
            std::swap(*it1, *(last-1));
            return it1;
        }
    };

    下面是利用上述排序算法对整数数组进行排序的示例。

    vector<int> nums;
    // Populate vector with data ...
    Sorter::quick_sort(nums.begin(), nums.end());

    因为算法基于c++模板函数实现,所以可支持的数据类型不仅局限于vector, 还可以是支持迭代器操作的所有容器类型;容器元素类型也不仅局限于int,还可以是支持比较操作符(<=)任一数据类型如double、float, 甚至可以是自定义类型。

    2. 并行快速排序算法(Parallel Quick Sort)

    我们学习研究算法的目的是尽可能降低时间和空间复杂度,最大程度提高运行效率。当二者不可兼得时,应当根据具体产品/运行环境的侧重点不同,采取以空间换时间或时间换空间的方式来确保某一方面的性能。

    针对经典快速排序算法,后续有很多优化方法, 例如随机化标定点(pivot)、双路快排、三路快排等,但万变不离其踪,都是分而治之的思想,有兴趣可参考国内外资料,这里我们主要看一下如何利用多线程技术来提升排序的速度。

    我们可以注意到#AAA行对所有数据一分为三:小于pivot的数据(part1)/pivot/大于pivot的数据(part2),#BBB行和#CCC行分别对part1和part2进行排序,并且#BBB和#CCC是串行执行,如果能让它们并行运行,排序的速率将会大大提高。

    需要注意的是,我们本不能直接把#BBB或#CCC放入新进程执行,因为快速排序算法本身是基于迭代实现的,其退出条件为数据个数小于等于2(#GGG~#HHH),如果把#BBB或#CCC放入新进程,就意味着每次数据量大于2的迭代就会产生一个新进程,很快就会把系统进程资源耗光。为此我们采用固定线程数来实实现并行排序,具体做法如下:

    • 创建公共数据列表,并把要排序数据起始位置放入公共列表;
    • 创建固定个数进程并发执行排序函数
    • 在排序函数中,互斥访问公共数据列表, 执行以下逻辑
    (伪代码)
    while data is not sorted:
        if public_data_list is not empty:  
            first, last = public_data_list.pop_back()
            mid = partition(first, last)
            put(first, mid) into public_data_list
            put(mid+1, last) into public_data_list
        else:
            sleep until got nofitified that public_data_list is not empty

    具体实现,请参考parallel_quick_sort.

    3. 算法测试

    3.1 算法参数说明

    3.1.1 threads_num

    使用多少个线程进行排序,应该不大于当前机器CPU核数

    3.1.2 parallel_gate

    启动多线程排序的最小数据量,如果达不到,则使用传统快排算法。在数据量较小时,多线程排序并不占优势,因为:1)传统算法本身就很快,平均时间复杂度O(n*logn),当数据量小于1000时,现代硬件水平(Intel Core(TM) i5/i7等)可以在秒间完成; 2)线程创建/销毁、 锁竞争带来的开销相比排序本身时间消耗使得使用多线程有些得不偿失。

    另外,并行排序算法本质上是以空间换时间,我们最好收集下最大内存消耗,从而衡量下性能提升的代价是否可以接受或者是否适用于目标系统。

    3.2 上述并行排序算法涉及的参数,应根据实验结果进行最优化配置

    3.2.1使用下表对parallel_gate进行优化,根据测试结果parallel_gate_取值为5000时,算法性能最优:

    thread_num_ data numparallel_gate_ Time 
    25000000 1005s923ms150us 
    25000000 5005s712ms912us 
    25000000 10005s581ms731us 
    25000000 50005s237ms971us 
    25000000 100005s469ms624us 

    **注:** 所有测试结果均在配置为(Interl Core(TM) i7, 4Core CPU, 8GB Mem)的desktop机器上取得

    3.2.2使用下表对thread_num进行优化,根据测试结果,thread_num取值为4时,算法性能最优:相比单线程,性能提高了1倍左右

    thread_num_ num parallel_gate_ Time 
    15000000 5000 8s769ms37us 
    25000000 5000 5s723ms756us
    35000000 5000 4s908ms678us
    45000000 5000 4s469ms82us

     3.2.3 并行算法的内存开销

    并行排序算法的各线程间需要共享一个公共列表,列表每一项存储一对vector迭代器,所以我只要知道了运行期间公共列表最大条目数,就能计算出最大内存开销: Max_Mem_Usage = max_size_of_public_list * sizeof (vector::iterator) * 2

    当data_num=10000000, parallel_gate_=5000, thread_num=4时,公共列表在运行期间最大条目数为:204,总共消耗内存16KB。

     3.2.4 经典快速排序和并行快速排序算法的性能比较

    Algorithm thread_num_ data num|parallel_gateTime Memory 
    Traiditional Sorting410000000 5000 13s929ms527usO(1)*
    Parallel Sorting 410000000 5000 6s855ms574us16.8KB

    *: 经典快速排序的内存消耗只有有限个变量。

    4 总结

    本文首先回顾了经典快速排序算法,然后介绍了一种基于多线程的并行排序算法,最后结合实验对算法参数进行优化固定,并对比了经典算法和并行算法的性能,结果证明并行算法确实能极大提高排序速度。

    转载于:https://www.cnblogs.com/wangwenzhi2019/p/10977860.html

    展开全文
  • Java Fork/Join框架 Fork/Join框架是一种能够并行执行任务...使用Fork/Join框架进行并行计算不仅简单高效而且具有良好的并行性能,Fork/Join并行算法的核心是分治算法的并行实现。 如图1-2所示,其中:fork操作...

    Java Fork/Join框架

            Fork/Join框架是一种能够并行执行任务支持并行编程方式的Java框架。如图1-1所示,这个框架通过递归将一个大任务分解成若干个并行执行的子任务,待到所有子任务都执行完成,再合并所有子任务结果,最终得到原大任务的结果。

    图1-1 Fork/Join框架示意图

            使用Fork/Join框架进行并行计算不仅简单高效而且具有良好的并行性能,Fork/Join并行算法的核心是分治算法的并行实现。

    如图1-2所示,其中:fork操作是启动一个新的Fork/Join的并行子任务,而join操作则是等待所有子任务都执行完成。

    图1-2 fork、join操作关系图

            Fork/Join框架首先它支持使用者自定义需要并行执行的基本子任务的粒度,并且直接通过编程就可以做到;其次Fork/Join在内部设计上使用双端队列+工作窃取的调度策略保证了每一个worker线程可以不断的窃取任务进行执行,从而提高系统资源的利用率,如图1-3所示。

    图1-3 工作窃取示意图

            Fork/Join框架不仅可以让使用者在执行并行任务时对需要并行执行的任务的细粒度进行控制,而且能够充分利用多核CPU、多线程来提高并行计算的能力,使程序员可以在保证并发执行任务的细粒度的同时,还能使程序获得更好的并行度。

    Java Phaser工具类

            在Java中Phaser是解决控制多线程执行多阶段任务时需要同步协调问题的一种“阶段器”。它类似于并行计算中的同步屏障,但比同步屏障多了一个阶段控制的功能,Phaser相比传统的同步栅栏更加灵活并且可复用,最主要还是其具备对在多任务并发执行时对不同阶段的任务进行控制的能力。

    并行快速排序算法的设计

    一、串行快速排序算法的描述

            排序算法中的快速排序由C. A. R. Hoare在1960年提出,是一种通过数据比较对无序序列进行递归排序的算法。其基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

            设待排序的序列(数组)为data[0]……data[length-1],首先任意选取一个元素(默认通常选取第一个元素data[0])作为基准数,然后将所有比基准数小的元素放置在基准数的前面,所有比基准数大的元素放在基准数的后面,由此以基准数最后所落位置i作为分界线,将序列分割成两个子序列(数组)data[0]……data[i-1]和data[i+1]……data[length-1]。这个过程称为一趟快速排序。

            完整的快速排序算法通过对上述一趟快速排序过程进行反复的递归调用,最终实现对整个序列的排序。设一趟快速排序的过程为函数Partition(data, low, high),则完整的快速排序算法描述如下:

    public void Quicksort(int[] Data, int low, int high){

           if(low < high){

                  i = Partition(data, low, high);

                  Quicksort(data, low, i-1)

                  Quicksort(data, i+1, high)

           }

    } 

    二、并行快速排序算法的分析

            根据上一节对串行快速排序算法的简述,我们接下来将挖掘串行快速排序算法其程序和数据的内在并行性:

            (1)在Quicksort(data, low, high)函数中每一次递归调用时,其左序列和右序列分别对应的递归函数Quicksort(data, low, i-1)和Quicksort(data, i+1, high)所处理的序列数据之间不存在依赖性,因此这两次函数递归是可以同时进行的,由此将其递归的过程并行化,设计出一种基于任务划分的并行快速排序算法。

            (2)对于超大的待排序序列,可以考虑对其数据集进行分解,分解成一个个较小的子数据集,再通过并行的方式对每个子数据集进行相同的快速排序操作,最后再合并所有子数据集以得到最终的排序结果,以此为理论基础设计出一种基于数据分解的并行快速排序算法。

    两种并行快速排序算法的并行方式如表2-1所示,这两种并行算法不管是基于任务划分还是数据分解,其并行化的本质都是采用了分治法的思想。

    表2-1 快速排序算法并行方式说明表

    并行方式

    说明

    任务划分

    不同的程序段由多个不同的线程实现

    数据分解

    多个线程对不同的数据块进行相同的处理

    三、并行快速排序算法的设计

            (1)基于任务划分的并行快速排序算法的设计。算法概要:基于任务划分的并行快速排序算法的程序会从一个线程开始启动排序,随着程序中每一次进行递归调用都会生成原来程序段数量的2的指数倍个新的执行排序的程序段,由于这些程序段所处理的数据之间不存在依赖关系,所以这些新的程序段可以被绑定在新的线程上,然后由不同线程在不同内核上并行执行,从而达到加快排序时间的效果。

            基于任务划分的并行快速排序算法描述如下:

            ①设待排序数据集的数组为data,两个指针low和high表示对数组data从第low个元素到第high个元素(包括data[low]和data[high])进行排序,再建立一个forkJoinPool线程池,线程池默认线程数量为CPU核心数(可以自定义调整)。

            ②建立一个启动排序的任务QuickSortRecursiveAction,将data数组和low、high的值传递给任务QuickSortRecursiveAction。将QuickSortRecursiveAction提交到forkJoinPool线程池中开始执行排序。

            对排序任务QuickSortRecursiveAction,当其被开始执行时,执行步骤如下:

            (A)先判断low是否大于等于high,如果成立,则说明当前的排序任务已经结束(这是递归结束的标志),如果不成立,则开始执行排序任务。

            (B)排序任务先对传入的data数组中第low个元素到第high个元素进行一趟快速排序并得到基准数位置i = Partition(data, low, high),再将任务基于基准数划分为左右两个子任务leftQuickSortRecursiveAction(data, low, i-1)和rightQuickSortRecursiveAction(data, i+1, high),将两个子任务使用fork()操作提交到forkJoinPool线程池中,线程池中有空闲线程会自动绑定子任务进行执行。

            (C)从线程池开始执行排序任务QuickSortRecursiveAction直到线程池中所有线程不在活跃,说明所有任务全部执行完成,则任务完成。

            (2)基于数据分解的并行快速排序算法的设计。算法概要:通过分析待排序数据的依赖关系,对待排序数据集进行数据分解,将待排序数据集分解成若干个规模大小相似的数据块,再把分解后的每一个数据块分配给不同的线程,所有线程并行执行排序,最后再对所有数据块两两进行归并,得出一个完整的有序数据集

            基于数据分解的并行快速排序算法描述如下:

            ①设待排序数据集的数组为data,数据个数为length,创建一个forkJoinPool线程池,设置线程池默认线程数量VariableLibrary.ThreadCount,默认为CPU核心的数量;再为每两个线程创建一个同步栅栏Phaser,一个同步栅栏绑定一个或两个线程,最后创建归并任务MergeRecursiveTask。

        ②对data数组进行数据分解,各线程先获取自己的线程号i和总线程数量no = VariableLibrary.ThreadCount,然后根据线程数量对data数组进行切片,将待排序数据集平均分割为相同个数的短序列,这些短序列的长度len为data.length/no,第i个序列为data[(i-1)×len+1, (i-1)×len+2, …, i×len],其中i = 1, 2, …, no。每个线程传入参数(data, (i-1)*length/no+1, i*length/no)开始执行串行快速排序算法。

            ③任意一个线程执行结束调用其对应Phaser的awaitAdvance(0)方法,表示本线程的第0阶段(快速排序)任务已经结束,等待第1阶段(归并)任务开始,每个Phaser对应的所有线程都调用了awaitAdvance(0)方法时,表示相邻的两个数据块已经排序完成,可以直接进行归并任务。

            ④将相邻的两个数据块的参数信息(a, b)传入归并任务MergeRecursiveTask中,当其被开始执行时,执行步骤如下:

            新建一个数组newData,长度newData.length = a.length+b.length,将两个数据块对应的数组中的元素以顺序的排序方式归并到newData中,以此类推,两两归并,直到只有一个数据块时,归并任务结束。

          ⑤归并任务结束时调用Phaser的awaitAdvance(1)方法,则排序完成,返回排序结果newData。 

    并行快速排序算法的实现

            快速排序并行求解系统的三种快速排序算法(传统的串行快速排序算法oldSort()、基于任务划分的并行快速排序算法newSort1()、基于数据分解的并行快速排序算法newSort2())实现代码如下:

    package test.quicksort;
    
    import test.Global.VariableLibrary;
    import test.util.Util;
    import java.util.Arrays;
    import java.util.concurrent.*;
    
    /**
     * @program: myDemo
     * @description: 快速排序算法
     * @author: YOUNG
     * @create: 2021-03-06 01:59
     */
    public class SortUtil {
        //ForkJoinPool线程池
        private static ForkJoinPool forkJoinPool = null;
        //数据分解时所需要的辅助空间
        private static int[][] dataSet = null;
        //同步栅栏,用于显示同步
        private static Phaser[] mergePhaser = null;
    
        /**
         * 初始化ForkJoinPool线程池
         * 以及数据分解时需要用到的临时存储空间和同步栅栏
         *
         * @param i 线程池数量
         */
        public static void init(int i) {
            forkJoinPool = new ForkJoinPool(i);
            dataSet = new int[i][];
            mergePhaser = new Phaser[i];
        }
    
        /**
         * 传统的串行快速排序算法
         *
         * @param arr 待排序的数组
         * @return 已排序好的数组
         */
        public static int[] oldSort(int[] arr) {
            return QuickSort(arr, 0, arr.length - 1);
        }
    
        public static int[] QuickSort(int[] a, int left, int right) {
            //左边索引大于或者等于右边的索引就代表已经整理完成一组数据,递归结束
            if (left >= right) {
                //解决一个bug,return null
                return null;
            }
            int i = left;
            int j = right;
            int key = a[left];
            //组内一次找寻
            while (i < j) {
                /*寻找结束的条件:
                1,找到一个小于或者大于key的数
                2,没有符合条件1的,并且i与j的大小没有反转*/
                while (i < j && key <= a[j]) {
                    //向前寻找
                    j--;
                }
                //交换a[i]和a[j]的数值
                /*找到一个这样的数后就把它赋给前面的被拿走的i的值
                (如果第一次循环且key是a[left],那么就是给key)*/
                Swap(a, i, j);
                //i在当组内向前寻找
                while (i < j && key >= a[i]) {
                    i++;
                }
                Swap(a, i, j);
            }
            //组内回归中间数key
            a[i] = key;
            //左边分组递归
            QuickSort(a, left, i - 1);
            //右边分组递归
            QuickSort(a, i + 1, right);
            //i=j结束
            return a;
        }
    
        /**
         * 交换方法,交换数组中两个元素的值
         *
         * @param a 被操作的数组
         * @param i 需要交换的元素的下标
         * @param j 需要交换的另一个元素的下标
         */
        private static void Swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    
        /**
         * 基于任务划分的并行快速排序算法
         *
         * @param arr 待排序的数组
         */
        public static void newSort1(int[] arr) {
            forkJoinPool.execute(new concurrentQuickSort(arr, 0, arr.length - 1));
            //隐含同步
            do {
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            } while (!forkJoinPool.isQuiescent());
        }
    
        /**
         * 基于数据分解的并行快速排序算法
         *
         * @param arr 待排序的数组
         * @return 已排序好的数组
         */
        public static int[] newSort2(int[] arr) {
            int len = arr.length / VariableLibrary.ThreadCount;
            if (len == 0) {
                return SortUtil.oldSort(arr);
            }
            int i;
            int[] result = null;
            for (i = 0; i < VariableLibrary.ThreadCount; i++) {
                mergePhaser[i] = new Phaser();
            }
            for (i = 0; i < VariableLibrary.ThreadCount - 1; i++) {
                forkJoinPool.execute(new oldQuickSort(arr, len * i, len * (i + 1) - 1, len, mergePhaser[i]));
            }
            forkJoinPool.execute(new oldQuickSort(arr, len * i, arr.length - 1, len, mergePhaser[i]));
            final ForkJoinTask<int[]> submit = forkJoinPool.submit(new MyMerge(dataSet, 0, VariableLibrary.ThreadCount - 1));
            try {
                result = submit.get();
            } catch (InterruptedException | ExecutionException e) {
                e.printStackTrace();
            }
            return result;
        }
    
        private static class oldQuickSort extends RecursiveAction {
            int[] data;
            int start;
            int end;
            int len;
            Phaser phaser;
    
            public oldQuickSort(int[] data, int start, int end, int len, Phaser phaser) {
                this.data = data;
                this.start = start;
                this.end = end;
                this.len = len;
                this.phaser = phaser;
                phaser.register();
            }
    
            private oldQuickSort() {
            }
    
            @Override
            protected void compute() {
                SortUtil.QuickSort(data, start, end);
                dataSet[start / len] = Arrays.copyOfRange(data, start, end + 1);
                phaser.arrive();
            }
        }
    
        private static class MyMerge extends RecursiveTask<int[]> {
            int[][] dataSet;
            int start;
            int end;
    
            private MyMerge() {
            }
    
            public MyMerge(int[][] dataSet, int start, int end) {
                this.dataSet = dataSet;
                this.start = start;
                this.end = end;
            }
    
            @Override
            protected int[] compute() {
                if (end - start > 1) {
                    MyMerge myMerge1 = new MyMerge(dataSet, start, (start + end) / 2);
                    myMerge1.fork();
                    MyMerge myMerge2 = new MyMerge(dataSet, (start + end) / 2 + 1, end);
                    myMerge2.fork();
                    return Util.mergeArray(myMerge1.join(), myMerge2.join());
                } else if (end == start) {
                    mergePhaser[start].awaitAdvance(0);
                    return dataSet[start];
                } else {
                    mergePhaser[start].awaitAdvance(0);
                    mergePhaser[end].awaitAdvance(0);
                    return Util.mergeArray(dataSet[start], dataSet[end]);
                }
            }
        }
    
        private static class concurrentQuickSort extends RecursiveAction {
            int[] a;
            int left;
            int right;
    
            public concurrentQuickSort(int[] a, int left, int right) {
                this.a = a;
                this.left = left;
                this.right = right;
            }
    
            private concurrentQuickSort() {
            }
    
            @Override
            protected void compute() {
                if (left >= right) {
                    return;
                }
                int i = left;
                int j = right;
                int key = a[left];
                while (i < j) {
                    while (i < j && key <= a[j]) {
                        j--;
                    }
                    Swap(a, i, j);
                    while (i < j && key >= a[i]) {
                        i++;
                    }
                    Swap(a, i, j);
                }
                a[i] = key;
                concurrentQuickSort leftConcurrentQuickSort = new concurrentQuickSort(a, left, i - 1);
                leftConcurrentQuickSort.fork();
                concurrentQuickSort rightConcurrentQuickSort = new concurrentQuickSort(a, i + 1, right);
                rightConcurrentQuickSort.fork();
            }
        }
    }
    

    快速排序实验设计与结果分析

            使用求解系统进行排序实验,实验主要分为两组:第一组实验对50,000,000(5000万)、100,000,000(1亿)、200,000,000(2亿)的随机(随机整数组成)序列进行排序;第二组实验对100,000(10万)、200,000(20万)、400,000(40万)的逆序(由大到小排列的整数组成)序列进行排序。

            在每一组实验中都分别使用三种快速排序算法(传统的串行快速排序算法、基于任务划分的并行快速排序算法、基于数据分解的并行快速排序算法)对所有序列进行排序,对于并行的快速排序算法再通过修改线程数量(2个线程、4个线程、8个线程)进行对比实验。

            最终记录每一组实验中每一次对序列进行排序的时间,计算并行算法程序的加速比以及并行效率。系统成功排序的结果是序列中数据(整数)由小到大排列。

            两组实验一共需要进行42次排序求解,对比实验结果表明,基于数据分解的并行快速排序算法无论是对随机序列还是逆序序列进行排序求解都比串行快速排序算法在效率上都有着明显提高;基于任务划分的并行快速排序算法在对随机序列进行排序求解时,其效率也比串行快速排序算法高很多,但在对逆序序列进行排序求解时,其效率要低于串行快速排序算法,而且随着线程数量的增加,其效率不仅不提高反而越来越低。

    (第一组实验)快速排序算法效果分析表

                    线程数量P    

    数据规模                  并行方式  

    排序时间(s

    并行加速比

    并行效率(%

    P=2

    P=4

    P=8

    P=2

    P=4

    P=8

    P=2

    P=4

    P=8

    5000

    串行

    6.810

    5000

    并行(任务划分)

    3.596

    2.366

    1.656

    1.89

    2.88

    4.11

    94.69

    71.96

    51.40

    5000

    并行(数据分解)

    3.461

    2.125

    1.590

    1.97

    3.20

    4.28

    98.38

    80.12

    53.54

    1亿

    串行

    11.657

    1亿

    并行(任务划分)

    7.124

    4.696

    3.281

    1.64

    2.48

    3.55

    81.81

    62.06

    44.41

    1亿

    并行(数据分解)

    6.194

    4.271

    3.307

    1.88

    2.73

    3.52

    94.10

    68.23

    44.06

    2亿

    串行

    24.335

    2亿

    并行(任务划分)

    15.939

    9.596

    6.773

    1.53

    2.54

    3.59

    76.34

    63.40

    44.91

    2亿

    并行(数据分解)

    13.633

    9.064

    7.595

    1.79

    2.68

    3.20

    89.25

    67.12

    40.05

    (第二组实验)快速排序算法效果分

    线程数量P    

    数据规模       并行方式

    排序时间(s

    并行加速比

    并行效率(%

    P=2

    P=4

    P=8

    P=2

    P=4

    P=8

    P=2

    P=4

    P=8

    10万

    串行

    1.333

    10万

    并行(任务划分)

    1.427

    1.531

    1.549

    0.93

    0.87

    0.86

    46.71

    21.77

    10.76

    10万

    并行(数据分解)

    0.343

    0.140

    0.062

    3.89

    9.52

    21.50

    194.31

    238.04

    268.75

    20万

    串行

    4.761

    20万

    并行(任务划分)

    5.454

    5.666

    6.100

    0.87

    0.84

    0.78

    43.65

    21.01

    9.76

    20万

    并行(数据分解)

    1.303

    0.515

    0.204

    3.65

    9.24

    23.34

    182.69

    231.12

    291.73

    40万

    串行

    18.908

    40万

    并行(任务划分)

    20.730

    21.291

    22.318

    0.91

    0.89

    0.85

    45.61

    22.20

    10.59

    40万

    并行(数据分解)

    5.173

    1.932

    0.828

    3.66

    9.79

    22.84

    182.76

    244.67

    285.45

    (随机序列)排序时间图

    (逆序序列)排序时间图

    (随机序列)并行加速比图

    (随机序列)并行效率图

            在多核CPU中,以任务划分的方式进行的并行快速排序的并行加速比会随着线程数的增加而增加,数据规模越大,加速比增加得越快,而以数据分解的方式进行的并行快速排序的并行加速比虽然也随着线程数的增加而增加,但是当数据规模变大时,加速比增加趋势明显下降,这是因为基于数据分解的并行快速排序算法在其并行排序的第二大阶段(归并操作)时,为了两两归并子数据集,必须开辟一个临时存储空间用于存放归并好的临时子数据集,每一次归并操作中都会开辟一个临时存储空间。设线程数量为N 个,原始数据集大小为L,在整个归并阶段一共会并行执行N-1 次归并操作,在这期间总共开辟⌈log2N×L 大小的临时存储空间,所以当数据规模巨大时,开辟临时存储空间的时间已不能被忽略,最终会影响排序的效率,这也是其加速比上升趋势下滑的主要原因。

            两种并快速排序算法的并行效率都会随着线程数的增加而降低。但在小规模数据时,基于数据分解的并行快速排序算法的并行效率要高于基于任务划分的并行快速排序算法,但当增大数据规模时,基于数据分解的并行快速排序算法的并行效率下降趋势更明显,在当数据规模到达2亿时,其效率已经低于基于任务划分的并行快速排序算法,主要原因还是因为当数据规模巨大时,基于数据分解的并行快速排序算法需要开辟辅助存储空间巨大,开辟时间非常耗时,最终导致效率下降趋势明显。

    (逆序序列)并行加速比图

    (逆序序列)并行效率图

            在处理逆序序列时,基于任务划分的并行快速排序算法的并行加速比不仅一直小于1,而且随着线程数量的增加,其并行加速比反而越来越小,再结合(逆序序列)并行加速比图和逆序序列)并行效率图可以看出,基于任务划分的并行快速排序算法在处理逆序序列的情况下,所消耗的时间比串行快速排序算法要多,效率也不如串行快速排序算法。出现这一现象的原因是:快速排序算法是不稳定的。在正常情况下,设数据规模为n ,快速排序算法的平均时间复杂度和最好时间复杂度都是 ,但现在是使用快速排序算法对逆序序列进行排序,这时快速排序算法会退化成类似于冒泡排序的算法,这时其算法的最坏时间复杂度为 ,也就意味着算法的每一次递归都不再需要移动元素,即每一次递归时进行的一趟快速排序Partition(data, low, high)几乎不耗时,此时基于任务划分的并行快速排序算法将不再具有优势,因为每个并行执行的任务都是不耗时任务,几乎与串行执行没有多大差别,而且由于多线程之间的相互调度需要花费额外的时空开销,导致其不仅排序所花费的时间比串行快速排序算法多,其效率也不如串行快速排序算法,而且在随着线程数量的增加还会导致其线程之间相互调度的时空开销也增大,最终导致基于任务划分的并行快速排序算法的效率越来越低。

    快速排序时间复杂度图

             但是对于逆序序列,基于数据分解的并行快速排序算法与基于任务划分的并行快速排序算法呈完全相反的效果。结合各图可以得知,基于数据分解的并行快速排序算法对逆序序列排序所用的时间远远小于另外两种快速排序算法。从10万数据规模开始,基于数据分解的并行快速排序算法的加速比就远超设定的线程数量,甚至最后超过了CPU的最高线程数,而其并行效率从一开始就已经大于100%,并且随着线程数量的增加,其效率和加速比呈爆炸式的增长,增长的趋势随着数据规模的扩大也只是稍稍下滑。出现这一反常的现象的主要原因是:对于逆序序列,无论是快速排序算法的平均时间复杂度Onlog2n 和最好时间复杂度Onlog2n 都不在适用,处理逆序序列是快速排序的最坏情况,这时快速排序算法的最坏时间复杂度为On2 。根据快速排序时间复杂度图可以看出,随着需要排序数据规模的增长,在最坏情况下快速排序所花费的时间呈指数倍增加。正是因为这一原因,基于数据分解的并行快速排序算法在最坏情况下,因为其在并行执行快速排序之前会对待排序列(数据集)进行分解,将一个大的序列分解成若干的规模较小的子序列,在分解的过程中大大降低了数据规模,并且这些子序列快速排序又是并行执行的,虽然上文提到当待排序数据集的数据规模超大时,其归并操作时开辟内存空间的时空开销不可忽略,但这和指数级增长的排序时间相比是微不足道的,所以基于数据分解的并行快速排序算法在处理逆序序列时会比串行快速排序算法的排序时间要少很多,甚至其并行加速比远超线程数量。

    快速排序实验结果的性能分析

    基于任务划分的并行快速排序CPU资源利用率图

    基于数据分解的并行快速排序CPU资源利用率图

    传统的串行快速排序CPU资源利用率图

            由传统的串行快速排序CPU资源利用率图可以看出,传统的快速排序算法在运行期间CPU资源利用率并未达到100%,并且只有一两个CPU内核在交替运行,其余CPU内核均被闲置。再看图5-8和图5-9,使用两种并行快速排序算法可以充分利用CPU资源,在排序过程中CPU资源利用率均达到了100%,所有CPU内核都被充分利用,但两者有些许差异:

            在基于任务划分的并行快速排序CPU资源利用率图中,CPU的资源利用率在随着排序开始的上升过程和随着排序结束的下降过程中都是渐进的,这是因为基于任务划分的并行快速排序刚开始是只有一个排序任务,随着不断的划分,子任务不断增多,最终多个子任务并行执行,充分利用CPU资源,所以CPU资源利用率呈渐进上升趋势。而基于任务划分的并行快速排序的结束也因为每个子任务都是根据基准数来划分的,基准数的选取是具有不确定性的(第一个基准数除外,这里指第一个基准数之后的基准数选取都是不确定的),从而导致每个子任务的规模也是不一样的,所以排序结束过程中的每个子任务结束的时间都是不一样的,所以CPU的资源利用率呈渐进下降的趋势。

            在基于数据分解的并行快速排序CPU资源利用率图中,可以发现CPU资源利用率在排序过程中存在一次下降再重新上升的趋势,这是因为基于数据分解的并行快速排序有两个过程阶段,在第二阶段归并过程开始之前有一个显示同步的操作用于线程之间两两相互等待,最终才能两两归并,所以这就可能会导致CPU中部分内核因为等待而空闲,CPU整体资源利用率下降,但最终第一阶段并行排序过程会完全结束,任务进入第二阶段,所有归并任务仍然是并行执行的,这时CPU资源利用率又会重新上升。

            综上所述:基于任务划分和基于任务分解的两种并行快速排序算法均能发挥计算机处理器的100%性能,符合设计要求。

    展开全文
  • left := nums[0] //快速排序的轴 nums = nums[1:] //从左向右扫描数据 大于轴的放到greater里小于的放到less中 for _,num_data := range nums{ switch{ case num_data less = append(less,num_data) ...
  • 排序用于人类活动和个人计算机、智能手机等设备,并且在最新技术的发展中继续发挥着至关重要的作用。 QuickSort 算法一直被称为最快和最有效的排序算法之一。 它由 CAR Hoare 于 1961 年发明,并使用分而治之的策略...
  • 利用OpenMP实现并行快速排序算法

    千次阅读 2011-01-06 16:36:00
    sections将对两个子数组的快速排序函数用两个线程并行化执行,至于线程的创建和销毁我们不用管,只要告诉编译器哪里的代码需要并行执行就可以了,具体请看OpenMP资料。#include <stdio.h>#include <stdlib.h>#...
  • 用Parallel_For进行并行快速排序

    千次阅读 2009-06-03 14:29:00
    用Parallel_For进行并行快速排序作者: Zhouweiming 周伟明 (32 篇文章) 日期: 五月 31, 2009 在 10:43 上午 用Parallel_For进行并行快速排序 注:本文主要内容摘自笔者所著的《多核计算与程序设计》一书,略有...
  • 快速排序

    万次阅读 多人点赞 2017-03-18 18:11:48
    快速排序
  • C语言快速排序算法

    2015-10-15 09:49:03
    mpi 对快速排序并行化实现方法——C语言快速排序算法
  • 我将讨论如何使用英特尔C ++编译器和OpenMP 4.5库提供现代代码,该库基于上一篇文章中已讨论的并行代码来实现并行的“稳定”三向快速排序
  • sorty特定于类型的快速并发/并行排序库。 sorty是就地QuickSort实现(将InsertionSort作为子例程),不需要额外的内存。 调用相应的Sort *()以并发地进行排序,从而实现特定于类型的快速并发/并行排序库。 sorty是...
  • 有一些排序算法如归并排序、快速排序等可以分解为子问题的算法是可以使用多线程来加速排序的,之前做了个小实验,测试了下自己写的MergeSort::parallelSort、QuickSort::parallelSort以及Arrays::sort、Arrays::...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 57,399
精华内容 22,959
关键字:

快速排序并行