精华内容
下载资源
问答
  • 并行选择排序
    2022-03-23 16:10:21

    快排逻辑

    快速排序是编程常用的排序方式,下面是快速排序的核心逻辑

     static void QuicksortSequential<T>(T[] arr, int left, int right) where T : IComparable<T>
     {
         if(right > left)
         {
             //pivot 左边的值小于arr[pivot].右边的值大于arr[pivot]
             int pivot = Partition(arr, left, right);
             //排序左边
             QuicksortSequential(arr, left, pivot - 1);
             //排序右边
             QuicksortSequential(arr, pivot + 1, right);
         }
     }
    

    这里的快速排序使用了递归的方式,可以发现排序左边和排序右边是互不影响的,这给并行运算提供了可行性,

    并行快排逻辑

    static void QuicksortParallel<T>(T[] arr,int left,int right)where T:IComparable<T>
    {
         if (right > left)
         {
             //防止线程开设过多反而速度变慢
             if (right - left < SEQUENTIAL_THRESHOLD)
             {
                 QuicksortSequential(arr, left, right);
             }
             else
             {
                 int pivot = Partition(arr, left, right);
                 //并行运算
                 Parallel.Invoke(new Action[] {
                     () => QuicksortParallel(arr,left,pivot - 1),
                     () => QuicksortParallel(arr,pivot + 1,right)
                 });
             }
         }
     }
    

    每开一个线程同样会造成性能的消耗,由于CPU核心数的限制,线程数超过一定数量反而会照成性能下降,所以加了一个SEQUENTIAL_THRESHOLD参数。使得要排序的单位小于他使,自动使用非并行的快速排序
    附上所有代码

    public class ParalleSort
    {
        const int SEQUENTIAL_THRESHOLD = 2048;
        //快速排序
        public static void QuicksortSequential<T>(T[] arr)where T:IComparable<T>
        {
            QuicksortSequential(arr, 0, arr.Length - 1);
        }
        //并行快速排序
        public static void QuicksortParallel<T>(T[] arr)where T : IComparable<T>
        {
            QuicksortParallel(arr, 0, arr.Length - 1);
        }
        /// <summary>
        /// 快排逻辑
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        static void QuicksortSequential<T>(T[] arr, int left, int right) where T : IComparable<T>
        {
            if(right > left)
            {
                //pivot 左边的值小于arr[pivot].右边的值大于arr[pivot]
                int pivot = Partition(arr, left, right);
                //排序左边
                QuicksortSequential(arr, left, pivot - 1);
                //排序右边
                QuicksortSequential(arr, pivot + 1, right);
            }
        }
        /// <summary>
        /// 并行排序逻辑
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        static void QuicksortParallel<T>(T[] arr,int left,int right)where T:IComparable<T>
        {
            if (right > left)
            {
                //防止线程开设过多反而速度变慢
                if (right - left < SEQUENTIAL_THRESHOLD)
                {
                    QuicksortSequential(arr, left, right);
                }
                else
                {
                    int pivot = Partition(arr, left, right);
                    //并行运算
                    Parallel.Invoke(new Action[] {
                        () => QuicksortParallel(arr,left,pivot - 1),
                        () => QuicksortParallel(arr,pivot + 1,right)
                    });
                }
            }
        }
        /// <summary>
        /// 区分数组大小值
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr"></param>
        /// <param name="low"></param>
        /// <param name="high"></param>
        /// <returns></returns>
        static int Partition<T>(T[] arr,int low,int high)where T:IComparable<T>
        {
            int pivotPos = (high + low) / 2;
            T pivot = arr[pivotPos];
            Swap(arr, low, pivotPos);
            int left = low;
            for(int i = low + 1; i <= high; i++)
            {
                if (arr[i].CompareTo(pivot) < 0)
                {
                    left++;
                    Swap(arr, i, left);
                }
            }
            Swap(arr, low, left);
            return left;
        }
        /// <summary>
        /// 交换
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="arr"></param>
        /// <param name="i"></param>
        /// <param name="j"></param>
        static void Swap<T>(T[] arr,int i,int j)
        {
            T tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    

    测试性能

    使用10000000个随机大小的数,分别使用快速排序,和并行快速排序,输出其消耗时间

    const int arrayNum = 10000000;
    int[] arr = new int[arrayNum];
    Random random = new Random();
    for(int i = 0; i < arrayNum; i++)
    {
        arr[i] = random.Next(0, arrayNum);
    }
    var arr2 = (int[])arr.Clone();
    Stopwatch w = new Stopwatch();
    w.Start();
    ParalleSort.QuicksortSequential(arr2);
    w.Stop();
    Console.WriteLine("快排序:{0}mm", w.ElapsedMilliseconds);
    w.Reset();
    w.Start();
    ParalleSort.QuicksortParallel(arr);
    w.Stop();
    Console.WriteLine("并行排序:{0}mm", w.ElapsedMilliseconds);
    

    输出如下
    在这里插入图片描述
    可以看到并行快排比普通快排快了4倍多

    更多相关内容
  • 只需两个时钟即可输出12个数据的排序结果,内容简单易懂
  • 为了实现快速排序算法的良好性能,对主元元素和编译器标志的选择进行了优化。为了优化性能,代码也被并行化并实现了尾递归。 由快速排序算法排序的数据是一个由 0.0 到 1.0 之间的非负双精度值组成的数组。
  • 并行计算实验快速排序的mpi并行实现以及omp并行实现
  • 2、熟悉快速排序并行算法 3、实现快速排序并行算法 3.2 实验环境及软件 单台或联网的多台PC机,Linux操作系统,MPI系统。 3.3实验内容 1、快速排序的基本思想 2、单处理机上快速排序算法 3、快速排序算法的...
  • 对于一个有序数组采取了取首位为基准的方法,快速排序的时间复杂度将会是(O (n^2)),这将会与冒泡排序无差别,针对其过程,对每次划分后的两个子区分别使用两个处理器完成递归排序,那么排序的效率将会有质的飞跃...
  • 并行计算mpi奇偶排序

    2018-12-16 15:45:43
    运用mpi实现奇偶排序,在不同的处理器之间通过消息传递完成奇偶index的数的交换,实现最终的数列排序
  • 归并排序并行和顺序归并排序算法
  • 检查在GPU上实现Radix排序的各种方法
  • 利用Pthread多线程工具 实现桶排序并行化,并在linux下调试通过。
  • 并行排序算法使用多个处理器对一组元素进行排序,以提高顺序排序算法的性能。 一般来说,排序算法的性能是根据输入大小在算法增长率方面进行评估的。 本文对并行冒泡排序的运行时间、并行加速比和并行效率进行了评估...
  • 该程序是在 gcc 4.7.3 和 openmp 3.1 上开发的。
  • 与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的...
  • 基于FPGA的并行全比较排序算法.pdf
  • // 1. A small-set insertion sort. We do this on any set with // 2. A partitioning kernel, which - given a pivot - separates an input // array into elements , and >pivot....// be launched to resolve each...
  • 基于并行加权排序和支持向量机融合的第二阶段特征选择算法
  • 不一样的排序算法【并行排序

    千次阅读 2018-03-15 20:24:24
    对于排序算法相信大家都不陌生,大部分排序的程序都是串行的排序算法,比如冒泡排序,插入...在介绍并行排序之前,我们有必要介绍一下奇偶排序,为了将串行排序算法改为并行排序,使用奇偶排序可以更加方便的修改...

    对于排序算法相信大家都不陌生,大部分排序的程序都是串行的排序算法,比如冒泡排序,插入排序,选择排序,堆排序等等,但是随着计算机的发展,现在的计算机都是多核的处理器,串行排序无法高效的利用CPU,为了更加有效的利用CPU,我们在这里介绍一下在并行世界中的排序算法。

    一、奇偶交换排序

    在介绍并行排序之前,我们有必要介绍一下奇偶排序,为了将串行排序算法改为并行排序,使用奇偶排序可以更加方便的修改程序为并行排序。

    1.什么是奇偶交换排序?
    奇偶排序分为两个阶段,奇交换和偶交换。奇交换就是将比较数组奇数索引以及与其相邻的之后的元素,偶交换就是比较数组偶数索引和其相邻的后续元素,并且,奇交换和偶交换总是成对出现,这样才能保证涉及到数组中的每一个元素。

    这里我们举一个例子,图解一下奇偶交换排序,假如这里我们对5,45,6,3,4 这五个数进行排序,下面我们来看看它具体是怎么进行奇偶交换的。(图画的有点丑哈_
    这里写图片描述
    通过上面的图解我们可以很清除的明白奇偶交换排序的原理。下面我们来写一下串行的奇偶交换排序的代码:

    package cn.just.thread.concurrent;
    /**
     * 奇偶排序
     * @author Shinelon
     *
     */
    public class OddEventSort {
    	public static void sort(int[] arr){
    		int exchange=1,start=0,temp;    //exchange记录当前循环是否进行了数据交换
    		while(exchange==1||start==1){	//start==1保证奇偶排序成对出现
    			exchange=0;		//没有发生交换
    			for(int i=start;i<arr.length-1;i+=2){	//刚开始进行偶排序
    				if(arr[i]>arr[i+1]){
    					temp=arr[i];
    					arr[i]=arr[i+1];
    					arr[i+1]=temp;
    					exchange=1;
    				}
    			}
    			if(start==0)
    				start=1;
    			else
    				start=0;
    		}
    	}
    	public static void main(String[] args) {
    		int[] a={12,25,45,78,69,45,58,26,78,49,12,2,23,5,89,45,78,58,20,19};
    		sort(a);
    		for(int i=0;i<a.length;i++){
    			System.out.println(a[i]);
    		}
    	}
    }
    
    

    二、并行排序
    下面我们开始今天的正题,现在我们就开始将上面的串行的排序方式修改为并行排序,此时我们已经很清楚的认识了奇偶交换排序,【它总是和奇索引或者偶索引对应的数据之后的数进行比较并且交换,这样就不会出现一个数既可以和它之前的数进行交换,也可以和它之后的数进行交换,从而在并行的模式下多个线程之间不会相互干扰,这是使用奇偶交换排序来进行并行排序的关键所在。】
    那么我们将怎么去分配线程的数量呢?并行的过程是怎么样的呢?我们还是以上面的数据为例进行讲解,在第一次偶交换的时候我们可以开启两个线程来分别交换5,45和6,3。同理,我们在接下来的奇交换时也开启两个线程来比较交换45,3和6,4。这样两个线程之间没有任务干扰,也不互相依赖,这样我们就正确的进行了并行排序。对于每次交换开启的线程数,我们可以通过以下方式来计算得到:

    threadNumber=arr.length/2-(arr.length%2==0?start:0);
    

    下面我们来写出完整的并行排序的程序:

    package cn.just.thread.concurrent;
    
    import java.util.concurrent.CountDownLatch;
    import java.util.concurrent.ExecutorService;
    import java.util.concurrent.Executors;
    
    /**
     * 并行排序
     * @author Shinelon
     *
     */
    public class CurrOddEventSort {
    	public static int exchange=1;
    	public static int[] arr={12,25,45,78,69,45,58,26,78,49,12,2,23,5,89,45,78,58,20,19};
    
    	public static  int getExchange() {
    		return exchange;
    	}
    
    	public static synchronized void setExchange(int exchange) {
    		CurrOddEventSort.exchange = exchange;
    	}
    	public static class OddEventSortTask implements Runnable{
    		int i;
    		CountDownLatch latch;
    		
    		public OddEventSortTask(int i, CountDownLatch latch) {
    			super();
    			this.i = i;
    			this.latch = latch;
    		}
    
    		public void sort(int[] arr){
    			int temp;
    				if(arr[i]>arr[i+1]){
    					temp=arr[i];
    					arr[i]=arr[i+1];
    					arr[i+1]=temp;
    					setExchange(1);
    			}
    			latch.countDown();
    		}
    
    		@Override
    		public void run() {
    			sort(arr);
    		}
    	}
    	public static void OddEventSort(int[] arr) throws InterruptedException {
    		ExecutorService pool=Executors.newCachedThreadPool();
    		int start=0;
    		while(getExchange()==1||start==1){
    			setExchange(0);
    			//偶数的数组长度,当start为1时,只有length/2-1个线程
    			CountDownLatch l=new CountDownLatch(arr.length/2-(arr.length%2==0?start:0));
    			for(int i=start;i<arr.length-1;i+=2)
    			pool.submit(new OddEventSortTask(i, l));
    			//等待所有线程结束
    			l.await();
    			if(start==1)
    				start=0;
    			else
    				start=1;
    		}
    	}
    	public static void main(String[] args) throws InterruptedException {
    		OddEventSort(arr);
    		for(int i=0;i<arr.length;i++){
    			System.out.println(arr[i]);
    		}
    	
    	}
    }
    
    

    上面的代码不是很难读懂,有的人可能不了解CountDownLatch ,这里我们简单介绍一下CountDownLatch ,它是多线程控制的一个工具类,是一个倒计时器,构造函数 new CountDownLatch(int number)中的参数number是开启的计时器数目,CountDownLatch.await()方法要求主线程等待所有线程池中所有任务都执行完。CountDownLatch.countDown()是当一个任务执行完后数目减去1。


    这里我们已经介绍完并行排序,在数据少的时候也许体现不出并行排序的优势,所以我们会选择串行排序,但是现在是大数据时代,当数据剧增时,并行排序就很有优势,效率很高,现在有很多大数据框架就是并行计算来处理海量数据的,感兴趣的小伙伴可以自己去了解,我们就介绍到这里(其实是比较菜,说不清楚,O(∩_∩)O哈哈~)。

    如果你想和我们一起学习探讨,可以扫码加群:
    在这里插入图片描述

    展开全文
  • 针对没有显式拓扑关系的质点云,提出了一种并行快速排序算法。 引入了莫顿阶并将其用于合并一维数据。 生成不规则模型的质量点云,对应的地址代码称为Morton码,这些点存储在八叉树结构链中。 然后使用基于欧几里得...
  • 朱莉娅排序 用于并行计算的并行 Julia 排序算法
  • 云计算-关于并行计算的排序问题.pdf
  • GPU 并行排序

    2018-04-22 17:28:08
    基于GPU 实现并行排序过程,大大加速了排序的效率,有加速比
  • 并行排序联接

    2021-02-14 08:23:29
    并行排序联接
  • 使用MPI计算的完整的PSRS(并行排序(parallel sorting by regular sampling))代码。并行计算课实验所用代码。
  • 【MPI、OpenMP】并行快速排序(C语言)

    千次阅读 2022-03-30 22:13:06
    (语言是C语言,有 例子+图 阐述原理,代码注释很全很详细)本文记录了使用MPI与OpenMP两种并行计算方法实现快速排序算法,主要分享一下自己的做法,希望大家不吝赐教。

    本文记录了使用MPI与OpenMP两种并行计算方法实现快速排序算法,题目是专业实验课上老师给的,主要分享一下自己的做法,希望大家不吝赐教(使用的语言是C语言,有例子+图阐述原理,代码注释很全)。

    快速排序算法并行实现

    1. 快速排序算法

    本篇文章主要针对快排算法的并行实现,所以大家如果有忘记快排算法的,可以参考一下这篇文章(快速排序算法原理及实现(单轴快速排序、三向切分快速排序、双轴快速排序)),这篇文章里面有动图,感觉还是挺不错的,有需要的朋友可以看看,其次再贴一个C语言实现串行快速排序算法的程序(快速排序算法(QSort,快排)及C语言实现),并行算法的实现核心还是围绕这个方法进行的。

    • 核心功能代码
      实现方式有挺多种的,我使用的是把数据data的第一个元素作为基准进行快排的,代码如下:
    int Partition(int* data, int start, int end)   //划分数据
    {
        int temp = data[start];   //以第一个元素为基准
        while (start < end) {
            while (start < end && data[end] >= temp)end--;   //找到第一个比基准小的数
            data[start] = data[end];
            while (start < end && data[start] <= temp)start++;    //找到第一个比基准大的数
            data[end] = data[start];
        }
        data[start] = temp;   //以基准作为分界线
        return start;
    }
    

    2. 并行快速排序原理

    此处主要讲MPI并行方式的原理,OpenMP的就想办法凑一些可以并行的代码就行。

    2.1 MPI快排并行原理

    除了快排本身的核心代码,该算法的核心问题是如何处理各个进程之间的通信。

    2.1.1 进程数为2的整数次方

    下面以四个进程为例,数据(下图中的星号 * 表示未排序的数据,不同颜色表示不同进程)可以被分发m = log24 = 2次,分发原则为:

    • 0进程首先分发数据给 0+2(m−1) = 2 进程,令m = m-1 = 1
    • 进而0进程剩余的数据分发给 0+2(m−1) = 1 进程;同理2进程将从进程0接收的数据分发给 2+2(m−1) = 3 进程;
    • 无进程可以分配了,则四个进程对各自数据进行快排(排完序的数据用▲表示);
    • 最后每个进程将快排的结果传给分配给自己数据的进程(此处:1给0,3给2,2给0,0输出 )。

    下图为分发数据与发送结果的过程
    4进程

    2.1.2 进程数为2的非整数次方

    当总进程数不是2的整数次方时,处理逻辑与上面稍有不同。
    再以总进程数为6为例,数据可以被分发m = log26 = 3次(向上取整),分发原则为:

    • 0进程首先分发数据给 0+2(m−1) = 4 进程,令m=m-1=2;
    • 0进程剩余的数据分发给 0+2(m−1) = 2 进程; 4进程将从进程0接收的数据分发给 4+2(m−1) = 6但是6进程不存在,因此在4进程内,使用循环一直令m=m-1,直到 4+2(m−1) 进程是存在的,此处需要将m减到1,才满足 4+2(m−1) = 5,5进程存在,所以4进程将数据分给5进程;
    • 而0到3这四个进程的数据分配,和上一个例子仅有四个进程的原则一致;
    • 无进程可以分配了,则六个进程对各自数据进行快排;
    • 最后每个进程将快排的结果传给分配给自己数据的进程 (此处:1给0,3给2,2给0;5给4,4给0,0输出)。

    下图为分发数据的过程
    6进程1
    下图为发送结果的过程
    6进程2

    2.2 OpenMP快排并行原理

    omp的原理也不难理解,凑出可并行的区域即可,当然也要分析题目,先从理论上判断是否适合多线程并行。
    下面代码的思路就是使用omp的sections设置并行域,需要注意的是,设置sections的时候,如果没有添加parallel,表示sections中的几个section是串行执行的;而加上parallel后表示每个section内部是串行的,而section之间是并行的(可以参考文章:OpenMp之sections用法)。

    void quickSort(int* data, int start, int end)  //并行快排
    {
        if (start < end) {
            int pos = Partition(data, start, end);
            #pragma omp parallel sections    //设置并行区域
            {
                #pragma omp section          //该区域对前部分数据进行排序
                quickSort(data, start, pos - 1);
                #pragma omp section          //该区域对后部分数据进行排序
                quickSort(data, pos + 1, end);
            }
        }
    }
    

    3. 完整代码与结果(含注释)

    3.1 MPI

    • 代码
    #include"mpi.h"
    #include<time.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    int Partition(int* data, int start, int end)   //划分数据
    {
        int temp = data[start];   //以第一个元素为基准
        while (start < end) {
            while (start < end && data[end] >= temp)end--;   //找到第一个比基准小的数
            data[start] = data[end];
            while (start < end && data[start] <= temp)start++;    //找到第一个比基准大的数
            data[end] = data[start];
        }
        data[start] = temp;   //以基准作为分界线
        return start;
    }
    
    void QuickSort(int* data, int start, int end)  //串行快排
    {
        if (start < end) {    //未划分完
            int r = Partition(data, start, end);   //继续划分,进行递归排序
            QuickSort(data, start, r - 1);
            QuickSort(data, r + 1, end);
        }
    }
    
    //求2的n次方
    int exp2(int n)
    {
        int i = 1;
        while (n-- > 0) i *= 2;
        return i;
    }
    
    //求以2为底n的对数,向下取整
    int log2(int n)
    {
        int i = 1, j = 2;
        while (j < n) {
            j *= 2;
            i++;
        }
        return i;
    }
    
    void paraQuickSort(int* data, int start, int end, int m, int id, int nowID, int N)
    {
        int i, j, r = end, length = -1;  //r表示划分后数据前部分的末元素下标,length表示后部分数据的长度
        int* t;
        MPI_Status status;
        if (m == 0) {   //无进程可以调用
            if (nowID == id) QuickSort(data, start, end);
            return;
        }
        if (nowID == id) {    //当前进程是负责分发的
            while (id + exp2(m - 1) > N && m > 0) m--;   //寻找未分配数据的可用进程
            if (id + exp2(m - 1) < N) {  //还有未接收数据的进程,则划分数据
                r = Partition(data, start, end);
                length = end - r;
                MPI_Send(&length, 1, MPI_INT, id + exp2(m - 1), nowID, MPI_COMM_WORLD);
                if (length > 0)   //id进程将后部分数据发送给id+2^(m-1)进程
                    MPI_Send(data + r + 1, length, MPI_INT, id + exp2(m - 1), nowID, MPI_COMM_WORLD);
            }
        }
        if (nowID == id + exp2(m - 1)) {    //当前进程是负责接收的
            MPI_Recv(&length, 1, MPI_INT, id, id, MPI_COMM_WORLD, &status);
            if (length > 0) {   //id+2^(m-1)进程从id进程接收后部分数据
                t = (int*)malloc(length * sizeof(int));
                if (t == 0) printf("Malloc memory error!");
                MPI_Recv(t, length, MPI_INT, id, id, MPI_COMM_WORLD, &status);
            }
        }
        j = r - 1 - start;
        MPI_Bcast(&j, 1, MPI_INT, id, MPI_COMM_WORLD);
        if (j > 0)     //负责分发的进程的数据不为空
            paraQuickSort(data, start, r - 1, m - 1, id, nowID, N);   //递归调用快排函数,对前部分数据进行排序
        j = length;
        MPI_Bcast(&j, 1, MPI_INT, id, MPI_COMM_WORLD);
        if (j > 0)     //负责接收的进程的数据不为空
            paraQuickSort(t, 0, length - 1, m - 1, id + exp2(m - 1), nowID, N);   //递归调用快排函数,对前部分数据进行排序
        if ((nowID == id + exp2(m - 1)) && (length > 0))     //id+2^(m-1)进程发送结果给id进程
            MPI_Send(t, length, MPI_INT, id, id + exp2(m - 1), MPI_COMM_WORLD);
        if ((nowID == id) && id + exp2(m - 1) < N && (length > 0))     //id进程接收id+2^(m-1)进程发送的结果
            MPI_Recv(data + r + 1, length, MPI_INT, id + exp2(m - 1), id + exp2(m - 1), MPI_COMM_WORLD, &status);
    }
    
    int main(int argc, char* argv[])
    {
        int* data;
        int rank, size;
        int i, j, m, r, n = atoi(argv[1]);   //随机数组的长度
        double start_time, end_time;
        MPI_Status status;
        MPI_Init(&argc, &argv);
        MPI_Comm_rank(MPI_COMM_WORLD, &rank);  //当前进程的进程号
        MPI_Comm_size(MPI_COMM_WORLD, &size);  //总进程数
        if (rank == 0) {   //根进程生成随机数组
            data = (int*)malloc(n * sizeof(int));
            srand(time(NULL) + rand());   //随机数种子
            for (i = 0; i < n; i++)
                data[i] = (int)rand();   //获取n个随机整数
        }
        m = log2(size);  //第一次分发需要给第2^(m-1)个进程
        start_time = MPI_Wtime();
        MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);  //广播n
        paraQuickSort(data, 0, n - 1, m, 0, rank, size);  //执行快排
        end_time = MPI_Wtime();
    
        if (rank == 0) {   //根进程输出并行时间
            for (i = 0; i < n && i < 10; i++)   //n太大时只输出前10个
                printf("%d ", data[i]);
            printf("\n并行时间:%lfs\n", end_time - start_time);
        }
        MPI_Finalize();
    }
    
    • 结果
      mpi

    3.2 OpenMP

    • 代码
    #include<stdio.h>
    #include<omp.h>
    #include<time.h>
    #include<stdlib.h>
    
    int Partition(int* data, int start, int end)   //划分数据
    {
        int temp = data[start];   //以第一个元素为基准
        while (start < end) {
            while (start < end && data[end] >= temp)end--;   //找到第一个比基准小的数
            data[start] = data[end];
            while (start < end && data[start] <= temp)start++;    //找到第一个比基准大的数
            data[end] = data[start];
        }
        data[start] = temp;   //以基准作为分界线
        return start;
    }
    
    void quickSort(int* data, int start, int end)  //并行快排
    {
        if (start < end) {
            int pos = Partition(data, start, end);
            #pragma omp parallel sections    //设置并行区域
            {
                #pragma omp section          //该区域对前部分数据进行排序
                quickSort(data, start, pos - 1);
                #pragma omp section          //该区域对后部分数据进行排序
                quickSort(data, pos + 1, end);
            }
        }
    }
    
    int main(int argc, char* argv[])
    {
        int n = atoi(argv[2]), i;   //线程数
        int size = atoi(argv[1]);   //数据大小
        int* num = (int*)malloc(sizeof(int) * size);
    
        double starttime = omp_get_wtime();
        srand(time(NULL) + rand());   //生成随机数组
        for (i = 0; i < size; i++)
            num[i] = rand();
        omp_set_num_threads(n);   //设置线程数
        quickSort(num, 0, size - 1);   //并行快排
        double endtime = omp_get_wtime();
    
        for (i = 0; i < 10 && i<size; i++)//输出前十个元素
            printf("%d ", num[i]);
        printf("\n并行时间:%lfs\n", endtime - starttime);
        return 0;
    }
    
    • 结果
      omp
    展开全文
  • 并行计算课程实验代码,c语言写的,在MacOS系统下的openmp的pi值计算和PSRS的实现,注释清晰,且PSRS处理了不整除的情况。懒得编译可使用我提供的run.sh脚本。加上待编译的文件作为参数即可。
  • 并行快速排序

    千次阅读 2019-06-27 07:36:47
    快速排序的基本思想:通过一轮排序使得数组“基本有序”,“基本有序”的意思是指以数组中数某下标的数为准,左边的数小于此数,右边的数大小此数,从而将数组分成两个待排序的数组。通过递归最终完成整个数组的排序...

    快速排序的基本思想:通过一轮排序使得数组“基本有序”,“基本有序”的意思是指以数组中数某下标的数为准,左边的数小于此数,右边的数大小此数,从而将数组分成两个待排序的数组。通过递归最终完成整个数组的排序。

     

    从快速排序的基本思想可以得出以下结论:

    通过一次排序分成2个待排序数组

    通过二次排序分成4个待排序数组

    ……

    通过n次排序分成2^n个待排序数组

    假设CPUNCore(Intel CPU的核数通常是2x次幂,AMD不一定),那么log2N次排序后就可以进行并行化操作,将N个数组分别放到NCore中进行计算,如下图所示

     

     

    下面是并行快速排序跟非并行快速排序的比较:

     

     

    上图是在Intel Q83004-Core  CPU 上运行的结果,可以发现多核并行节省了快速排序的时间,但效果并不显著。

    其主要原因在于:快速排序通常所选的Key是数组的第一个元素,通过一轮排序后分成的两个数组大小通常不相同(几乎不可能相同)。

    最差情况下并行将退化成串行。

    附测试源代码:


    using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace SortLib { public class ParallelQuickSort:QuickSort { int coreNum = 4; int pardepth = 0; public int CoreNum { get { return coreNum; } set { coreNum = value; pardepth = depth(value); } } public ParallelQuickSort(TestData _data) : base(_data) { } private static int depth(int core) { int depth = 0; while ((core = core / 2) > 0) depth++; return depth; } public override void DoSort() { Stopwatch sw = new Stopwatch(); sw.Start(); quickSort(0, data.Len - 1,0); sw.Start(); onFinished(this, new SortEventArgs(sw.ElapsedMilliseconds)); //base.DoSort(); } List<Action> pActions = new List<Action>(); public void quickSort(int start, int end, int depth) { if (start < end) { int pos = getKeyPos(start, end); if (depth == pardepth&&depth!=0)//此处并行 { sortUnit s1 = new sortUnit(this,start, pos - 1,depth+1); sortUnit s2 = new sortUnit(this, pos + 1, end, depth + 1); pActions.Add(new Action(s1.run)); pActions.Add(new Action(s2.run)); if (pActions.Count == (1<<pardepth)) { System.Threading.Tasks.Parallel.Invoke(pActions.ToArray()); } } else { quickSort(start, pos - 1,depth+1); quickSort(pos + 1, end,depth + 1); } } } } public class sortUnit { public ParallelQuickSort sorter; public int start; public int end; public int depth; public sortUnit(ParallelQuickSort sort, int _start, int _end, int _depth) { this.start = _start; this.end = _end; this.depth = _depth; this.sorter = sort; } private void sort() { } public void run() { sorter.quickSort(start, end, depth); } } } public class TestData:ICloneable { int len; private int[] data;// = new int[1000]; public int Len { get { return len; } set { len = value; } } public int[] Data { get { return data; } set { data = value; } } public void GenRandomData() { Random rd = new Random((int)DateTime.Now.Ticks); for (int i = 0; i < len; i++) { data[i] = rd.Next(int.MaxValue); } } public TestData(int _len) { this.len = _len; data = new int[len]; } public object Clone() { TestData newData = new TestData(this.len); newData.len = this.len; this.data.CopyTo(newData.data, 0); return newData; } } int MB = 1024*1024; SortLib.TestData data; public Form1() { InitializeComponent(); int len = 5 * MB; data = new SortLib.TestData(len); data.GenRandomData(); } private void button2_Click(object sender, EventArgs e) { SortLib.TestData newdata = (SortLib.TestData)data.Clone(); SortLib.ParallelQuickSort srt = new SortLib.ParallelQuickSort(newdata); srt.CoreNum = (int)numericUpDown1.Value; srt.Finished += new SortLib.SortFinished(srt_Finished); srt.DoSort(); }

     

    转载于:https://www.cnblogs.com/cattlecoder/archive/2013/01/12/2857711.html

    展开全文
  • 信息作为硕士论文的一部分,对C ++中实现的顺序排序算法与CUDA中实现的并行排序算法之间的比较进行了研究。 我们实现了七个算法:双音排序,多步双音排序,自适应双音排序,合并排序,快速排序,基数排序和样本排序...
  • 针对角对称矩阵的特征值分解问题,提出了一种新的排序Jacobi算法(S-Jacobi).该算法利用Jacobi旋转中的内角...另外,为S-Jacobi的并行实现提出的旋转度计算电路与传统Jacobi算法的情况相比,只需要少量的额外硬件资源.
  • 用MPI实现并行排序算法——奇偶交换排序(C++)

    千次阅读 多人点赞 2020-12-08 18:19:56
    本文主要讨论并行排序算法的实现,将串行的奇偶排序算法并行化。同时本文也涉及MPI通信安全方面的讨论,MPI_SendRecv函数提供了有关进程通信的调度,用它替代send和recv函数使程序更安全

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 156,635
精华内容 62,654
热门标签
关键字:

并行选择排序