利用 openmp 实现在intel多核系统上基本排序算法性能比较

本文章因为参加投票，请大家转载时说明，谢谢。

投票地址：http://intel.csdn.net/multicoreblog/show.aspx?page=0 （请投对文章：），谢谢）

本篇文章通过使用 openMp 实现对基本排序算法的性能比较：

文章很简单，但是很实用，分别演示了如何使用 openMP 进行多核多线程程序开发，可以作为入门级朋友的

学习教材。如果想正确运行程序，您需要创建每个文件，同时命名一定要合适，否则您需要自己去重写

后面的 makefile 文件。

sorh.h 头文件

 
   view plain 
  
//sort.h head file  
#include <stdio.h>  
#include <time.h>  
#include <stdlib.h>  
 
 
#include <omp.h>  
#define NUM_THREADS 12  
typedef  float  KeyType;  
typedef  int KeyInt;  
typedef struct LNode  
{  
    KeyType key;  
    struct LNode* next;  
}LNode;  

sort.c 文件包含main 函数，相当于一个 client 实现对各个排序算法的并行调用。

这里采用了 openMp 指导语句 #pragma omp sections 实现结构块化，即把各个结构块划分到各自的线程上。实际上是一个任务分配区（work-sharing sections）的概念。通过 #pragma omp parallel

#pragma omp sections 指导OpenMp编译器和运行时库将应用程序中标示出的结构化块分配到用于执行并行区域的一

组线程上。这段例子还是非常有用的。

 
   view plain 
  
# sort.c  
#include "sort.h"  
/** 
** The program need assitant Functions  
** 
**/  
KeyType* randomCreat(int N);  
void DisPlay(int N, KeyType *p);  
int GetExponent(int N);  
KeyInt* Dlta(int exponent);    //build Dlta array for ShellSort  
void FindPrimes(int start, int end); //for Dlta Maybe this is a badlly method  
int TestForPrime(int val); //for Dlta   
void myKeyboardFunc( unsigned char key);  
  
/** 
** Bubble Sort Functions in Bubble.c 
**/  
KeyType* BubbleArgorithm(int N, KeyType *p);  
  
/** 
**Merge Sort Functions   in  Merge.c 
**/  
KeyType* MMSort(int N, KeyType* p);  
void MSort(KeyType *r1, KeyType *r2, int left, int m, int r);  
void MergeSort(KeyType *r1, KeyType *r2, int left, int right);  
  
/** 
**InsertSort  Functions in  InsertSort.c 
**/  
KeyType* InsertSort(int N, KeyType* p);  
  
/** 
**ShellSort Functions   in ShellSort.c 
**/  
KeyType* ShellSort(KeyType* p, KeyInt* dlta, int t, int N);  
void ShellInsert(KeyType* p, int dk, int N);  
  
/** 
**QuickSort Functions   in QuickSort.c 
**/  
  
KeyType* QuickSort(int N, KeyType* p);  
KeyType Partition(KeyType* p, int low, int high);  
void Qsort(KeyType* p, int low, int high);  
  
/** 
**BucketSort Functions  in BucketSort.c 
**/  
LNode** Bucket(int N);  //create Bucket according to N  
KeyType* BucketSort(LNode** bucket, KeyType* p, int N);  
  
int main(int argc, char *argv[])  
{  
   
    clock_t start, stop;   
    char any = 'c';  
    KeyType *p0, *p1, *p2, *p3, *p4, *p5;  
    LNode** bucket; //for BucketSort B【】  
    int N, i; //The size is sorted.  
      
    if(argc < 2)  
    {  
        printf("Enter random size  N=");  
        scanf_s("%d",&N);  
          
    }  
    else  
    {  
        N = atoi(argv[1]);  
    }  
/** 
** create sorted random copy 
**/  
p0 = randomCreat(N);                    //p0 for Merge-sort  
p1 = malloc(N*sizeof(KeyType));         //p1 for Bubble-sort  
p2 = malloc(N*sizeof(KeyType));         //p2 for Insert-sort  
p3 = malloc(N*sizeof(KeyType));         //p3 for Shell-sort  
p4 = malloc(N*sizeof(KeyType));         //p4 for Quick-sort  
p5 = malloc(N*sizeof(KeyType));         //p5 for Bucket-sort  
  
for( i=0; i<N; i++)  
{  
    p1[i] = p2[i] = p3[i] = p4[i] = p5[i] = p0[i];  
}  
//DisPlay(N, p0);  
/** 
** Start testing method of sort. 
** Use OpenMP create threads deal with methods  
** 
**/  
  
    #pragma omp parallel  
    {  
        #pragma omp sections nowait  
        {  
              
            /** 
                ** Merge sort  
                **  
                **/  
            #pragma omp section  
            {  
                start = clock();  
                p0 = MMSort(N, p0);  
                stop = clock();     
                printf("/b/b/b/b/bThe MergeSort      elapsed time = %g seconds,  The threads num is %d/n  ", (double)(stop - start) / CLOCKS_PER_SEC,(int)omp_get_thread_num());  
                //DisPlay(N, p0);  
                free(p0);  
            }  
            /** 
            ** Bubble sort 
            **/  
            #pragma omp section  
            {  
                start = clock();  
                p1 = BubbleArgorithm(N, p1);  
                stop = clock();     
                printf("/b/b/b/bThe BubbleSort     elapsed time = %g seconds, The threads num is %d/n  ", (double)(stop - start) / CLOCKS_PER_SEC,(int)omp_get_thread_num());  
                //DisPlay(N, p1);  
                free(p1);  
            }  
  
            /** 
            ** Insert-sort   
            **/  
            #pragma omp section  
            {  
                 start = clock();  
                 p2 = InsertSort(N, p2);  
                 stop = clock();     
                 printf("/b/b/b/bThe InsertSort     elapsed time = %g seconds,  The threads num is %d/n  ", (double)(stop - start) / CLOCKS_PER_SEC,(int)omp_get_thread_num());  
                // DisPlay(N, p2);  
                 free(p2);  
            }  
                /** 
                ** Shell-sort   
                **/  
            #pragma omp section  
            {  
                 start = clock();  
                 //According to N made dlta size and t size  
                 p3 = ShellSort(p3, Dlta(GetExponent(N)), GetExponent(N), N);  
                 stop = clock();     
                 printf("/b/b/b/bThe Shellsort      elapsed time = %g seconds,   The threads num is %d/n ", (double)(stop - start) / CLOCKS_PER_SEC,(int)omp_get_thread_num());  
                 //DisPlay(N, p3);  
                 free(p3);    
            }  
            /** 
            ** Quick-sort   
            **/  
            #pragma omp section  
            {  
                start = clock();  
                p4 = QuickSort(N, p4);  
                stop = clock();     
                printf("/b/b/b/bThe QuickSort      elapsed time = %g seconds,  The threads num is %d/n ", (double)(stop - start) / CLOCKS_PER_SEC,(int)omp_get_thread_num());  
                //DisPlay(N, p4);  
                free(p4);     
            }  
            /** 
            ** BucketSort  
            **/  
            #pragma omp section  
            {  
                start = clock();  
                bucket = Bucket(N);  
                p5 = (KeyType*)FindBucket(N, p5, bucket);  
                stop = clock();     
                printf("/b/b/b/bThe BucketSort     elapsed time = %g seconds,  The threads num is %d/n ", (double)(stop - start) / CLOCKS_PER_SEC,(int)omp_get_thread_num());  
                //DisPlay(N, p5);  
                free(p5);     
            }  
  
        }  
  
    }  
      
printf("/b/b/b/b/b/bPlease press /"q/" to quit program ..................!!!/n");  
  
  // any = getchar();  
   while(1)  
    {  
       if(getchar()=='q')  
         return 0;  
    }  
}  

 
   view plain 
  
// bubble.c 实现冒泡排序  
#include "sort.h"  
  
/** 
* bubbel argorithm    
* 第一次循环将最大的数放到最后，后面循环依次类推。 
*/  
  
KeyType* BubbleArgorithm(int N, KeyType *p)  
{  
   int i, j;  
   KeyType temp;  
   for(i=0; i<N; i++)  
       for(j=N-1; j>i; j--)  
           if(p[j]<p[j-1])  
           {  
               temp = p[j-1];  
               p[j-1] = p[j];  
               p[j] = temp;  
           }  
   return (p);  
}  

buctet.c 文件实现桶排序

 
   view plain 
  
#include "sort.h"  
/** 
**According to N create B[N] for bucket 
**/  
LNode** Bucket(int N)  
{  
    int i=0;  
      
    LNode  *q, **p;  
    p = malloc(N*sizeof(LNode*));  
    //initialization p using OpenMP  
    #pragma omp parallel for private(i)  
    for(i=0; i<N; i++)  
    {  
        q = malloc(sizeof(LNode*));  
        q -> key = 0.0;  
        q -> next = NULL;  
        p[i] = q;  
    }  
      
    return (p);  
}  
//Function is insert a Node to a order LinkList  
KeyType* FindBucket(int N, KeyType* p, LNode** q)  
{  
    int i, j=0;  
    long tmp;  
    LNode *ele;  
    KeyType* finall;  
    for(i=0; i<N; i++)  
    {  
        tmp = (long)(p[i] * N);  
        ele = malloc(sizeof(LNode*));  
        ele->key = p[i];  
        ele->next = NULL;  
        q[tmp]->next = (LNode*)LinkInsert(q[tmp]->next, ele);  
    }  
  
    finall = malloc(N*sizeof(KeyType));     
    for(i=0; i<N; i++)  
    {  
        while(q[i]->next)  
        {  
                finall[j]= q[i] -> next -> key;  
                q[i] ->next = q[i] -> next->next;  
                j++;  
        }  
    }    
    return (finall);  
}  
//Function is insert a Node to a order LinkList  
LNode* LinkInsert(LNode *LinkList, LNode *p)  
{  
    LNode *current, *head;  
  
    current = LinkList;  
    head = NULL;      
    while((current != NULL) && (current->key < p->key))  
    {  
            head = current;  
            current = current->next;  
    }  
    p->next = current;  
    if( head == NULL )  
    {  
        current = p;  
        return current;  
    }  
    else  
    {  
        head->next = p;  
        return head;  
    }  
}  

InsertSort.c

 
   view plain 
  
#include "sort.h"  
  
/** 
** @function:   Insert sort 
** @ 
**/  
KeyType* InsertSort(int N, KeyType* p)  
{  
   int i, j;  
   KeyType tmp;  
   for(i=0; i<N-1; ++i)  
    {  
       if(p[i+1] < p[i])  
        {  
           tmp = p[i+1];  
           p[i+1] = p[i];  
           for(j = i; tmp < p[j]; --j)  
               p[j+1] = p[j];  
           p[j+1] = tmp;  
        }         
    }  
   return (p);  
}  

Merge.c

 
   view plain 
  
#include "sort.h"  
  
  
/** 
** 
** mSort  
**  
** i is left  j is middle k is left 
** 
*/  
void MSort(KeyType *r1, KeyType *r2, int left, int m, int r)  
{  
    int i = left, j = m + 1,  k = left;  
  
    while((i <= m)&&(j <= r))  
    {  
        if(r1[i] <= r1[j])  
        {  
            r2[k++] = r1[i++];  
  
        }  
        else  
        {  
            r2[k++] = r1[j++];  
        }  
    }//end while   
      
    //将剩余的人r1 内容复制到 r2 中  
    while(i <= m)  
    {  
        r2[k++] = r1[i++];  
    }      
    //将剩余的人r1 内容复制到 r2 中  
    while(j <= r)  
    {  
        r2[k++] = r1[j++];  
    }  
  
    //修改r1内容  
    for(k=1; k <= r; k++)  
    {  
        r1[k] = r2[k];  
    }  
}  
  
/**  
* MergeSort 
*/  
void MergeSort(KeyType *r1, KeyType *r2, int left, int right)  
{  
    int middle;   
    if(left < right)  
    {  
        middle = ((left + right) >> 1);  
        #pragma omp parallel  
        {  
            #pragma omp sections nowait  
            {  
                #pragma omp section  
                MergeSort(r1, r2, left, middle);  
                #pragma omp section  
                MergeSort(r1, r2, middle + 1, right );    
            }  
              
        }  
        MSort(r1, r2, left, middle, right);  
    }  
}  
  
KeyType* MMSort(int N, KeyType *r)  
{  
    KeyType *tmp;  
    if((tmp = malloc(N * sizeof(KeyType))))  
    {  
        MergeSort(r, tmp, 0, N-1);  
        free(tmp);  
        return (r);  
    }  
    else  
    {  
        printf("malloc is failed !!!");  
        return (r);  
    }  
}  
  
//因为参与投票，文章版权所有请不要转发。 唐炜  

QuickSort.c 快速排序可以实用两个线程分别对各个待排序队列实现递归排序

 
   view plain 
  
#include "sort.h"  
  
/** 
**@function: QuickSort 
**@author: Tang Wei 
** 
**/  
KeyType Partition(KeyType* p, int low, int high)  
{  
    KeyType tmp = p[low]; //pivotkey  
    while(low < high)  
    {  
        while((low < high) && (p[high] >= tmp))   
            --high;  
        p[low] = p[high];  
        while((low < high) && (p[low] <= tmp))  
            ++low;  
        p[high] = p[low];  
    }  
    p[low] = tmp;  
    return low;   
}  
  
void Qsort(KeyType* p, int low, int high)  
{  
    int pivotLocation;  
    if(low < high)  
    {  
        pivotLocation = Partition(p, low, high);  
        #pragma omp parallel   
        {     
            #pragma omp sections nowait  
            {  
                #pragma omp section  
                Qsort(p, low, pivotLocation-1);  
                #pragma omp section  
                Qsort(p, pivotLocation+1, high);  
            }  
        }  
    }  
}  
KeyType* QuickSort(int N, KeyType* p)  
{  
    Qsort(p, 0, N-1);  
    return(p);  
}  

rand.c

 
   view plain 
  
#include "sort.h"  
  
/** 
* 生成随即序列 
* 
*/  
  
  
KeyType* randomCreat(int N)  
{  
    int i=0;  
    KeyType *p;  
    p = malloc(N * sizeof(KeyType));  
      
    for(i=0; i<N; i++)  
        p[i] = rand()/(RAND_MAX+1.0);   
    return (p);  
}  
  
void DisPlay(int N, KeyType *p)  
{  
    while(N>0)  
        printf("/b/b/b/b/b/b/bp[%d]:=%f/n",N, p[--N]);  
}  
void myKeyboardFunc( unsigned char key)  
{  
    switch ( key ) {  
        case 'q':                    //****bobc  
                // exit program        
                exit(0);             //****bobc  
    }  
}  

ShellSort.c

 
   view plain 
  
#include "sort.h"  
static       int gProgress    = 0,  
                 gPrimesFound = 0;  
long             globalPrimes[20];  
  
  
/** 
**@function:   Shell Sort 
**/  
void ShellInsert(KeyType* p, int dk, int N)  
{  
    int i, j;  
    KeyType tmp;  
    for(i = dk + 1; i < N; ++i)  
    {  
        if(p[i] < p[i - dk])  
        {  
            tmp = p[i];  
            for(j = i - dk; j>0 && (tmp < p[j]); j-=dk)  
                p[j + dk] = p[j];  
            p[j + dk] = tmp;  
        }  
    }  
}  
  
KeyType* ShellSort(KeyType* p, KeyInt* dlta, int t, int N)  
{  
    int k;  
    for(k = 0; k < t; ++k)  
        ShellInsert(p, dlta[k], N);  
    free(dlta);  
    return (p);  
}  
/** 
** 
** First, calculate t for dlat[]  
** Second, insert dlta[] with primes numbers 
** Third, return dlta 
*/  
int GetExponent(int N)  
{  
    int exponent = (int)(log10(N)/log10(2));  
    return exponent;  
}  
int* Dlta(int exponent)  
{  
    //int exponent = (int)(log10(N)/log10(2));  
    KeyInt* p;  
    int i;  
    p = malloc(exponent*sizeof(KeyInt));  //assign space for dlta;  
    FindPrimes(1, 100);  
    for(i=0; i<exponent-1; i++)  
    {  
        //printf("i: =%d,  exponent-2-i=%d, globalPrimes[exponent-1-i]:=%d/n", i,exponent-1-i, globalPrimes[exponent-i]);  
        p[i] = globalPrimes[exponent-i];  
    }  
    p[exponent-1] = 1;  
    return (p);  
}  
  
/** 
  这是采用分别取线程号的方法实现并行 
*/  
void FindPrimes(int start, int end)  
{  
int i, k;  
omp_set_num_threads(NUM_THREADS);  
  
if (start <= 2) globalPrimes[gPrimesFound++] = 2;  
#pragma omp parallel for private(i)  
        for(i = start; i <= end; i += 2 )  
        {  
            if( TestForPrime(i) )  
            {  
                //这里需要设置临界区否则 globalPrimes[] 里面的内容不合适  
                #pragma omp critical  
                globalPrimes[gPrimesFound++] = i;  
                //printf("prime : %d/n", globalPrimes[gPrimesFound]);  
            }  
        }  
  
}  
  
int TestForPrime(int val)  
{  
    int limit, factor = 3;  
  
    limit = (long)(sqrtf((float)val)+0.5f);  
    while( (factor <= limit) && (val % factor))  
        factor ++;  
  
    return (factor > limit);  
}  
//因为参与投票，文章版权所有请不要转发。 唐炜  

MAKEFILE.mak 我这里建立了一个 program 包，将所有的文件放到这个目录里面，如果您不一样的话，请修改

makefile文件 CPP_PROJ = $(CFLAGS) /Qopenmp -c ../program 内容 /Qopenmp 为打开Qopenmp选项，

编译器支持openMP， ../program 为目录

 
   view plain 
  
##################################################################################  
########### You must use Intel C++ Compiler                            ###########  
########### C++ Build Environment for applications running on IA-32    ###########  
########### command line> nmake /f MAKEFILE.mak                        ###########  
###########                                                            ###########  
##################################################################################  
 
####### Compiler, tools and options  
CPP=icl.exe  
!IF "$(CPP)" == "icl.exe"  
LINK=xilink.exe  
!ELSE  
LINK=link.exe  
!ENDIF  
CF       = -O3  
LF       =   
CFLAGS   = $(CF)    
LFLAGS   = $(LF)  
CPP_PROJ = $(CFLAGS) /Qopenmp -c  ../program  
SRCS     =    *.cpp  
OBJS     =    *.obj  
TARGET   =    sort.exe  
 
####### Files  
SOURCES = sort.c rand.c Merge.c Bubble.c InsertSort.c Shellsort.c QuickSort.c BucketSort.c  
  
OBJECTS =  sort.obj rand.obj Merge.obj Bubble.obj InsertSort.obj ShellSort.obj QuickSort.obj BucketSort.obj  
 
####### Implicit rules  
.SUFFIXES: .cpp .cxx .cc .c  
  
.cpp.obj:  
    $(CPP) -c $(CPP_PROJ) -Fo$@ $<  
  
.cxx.obj:  
    $(CPP) -c $(CPP_PROJ) -Fo$@ $<  
  
.cc.obj:  
    $(CPP) -c $(CPP_PROJ) -Fo$@ $<  
  
.c.obj:  
    $(CPP) -c $(CPP_PROJ) -Fo$@ $<  
 
 
####### Build rules  
  
all: $(TARGET)  
$(TARGET): $(OBJECTS) $(LIBS)   
    $(LINK)  $(LFLAGS) $(LDFLAGS) /OUT:$(TARGET) $(LIBS) $(OBJECTS)   
  
  
  
clean:  
    -@erase *.obj  
    -@erase *.bak  
    -@erase *.exe  
 
####### Compile  
  
$(OBJECTS): $(SOURCES)  
    $(CPP) -c $(CPP_PROJ) $(SOURCES)  
 
 
####### Libraries  

秒客网

利用 openmp 实现在intel多核系统上基本排序算法性能比较

相关文章

利用 openmp 实现在intel多核系统上 基本排序算法性能比较

相关文章

利用 openmp 实现在intel多核系统上基本排序算法性能比较