hostdepend/X86MAC64/util/X86MAC64/cuda/samples/6_Advanced/mergeSort/mergeSort_host.cpp

   1 /*
   2  * Copyright 1993-2013 NVIDIA Corporation.  All rights reserved.
   3  *
   4  * Please refer to the NVIDIA end user license agreement (EULA) associated
   5  * with this source code for terms and conditions that govern your use of
   6  * this software. Any use, reproduction, disclosure, or distribution of
   7  * this software and related documentation outside the terms of the EULA
   8  * is strictly prohibited.
   9  *
  10  */
  11
  12
  13
  14 #include <assert.h>
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <string.h>
  18 #include "mergeSort_common.h"
  19
  20
  21
  22 ////////////////////////////////////////////////////////////////////////////////
  23 // Helper functions
  24 ////////////////////////////////////////////////////////////////////////////////
  25 static void checkOrder(uint *data, uint N, uint sortDir)
  26 {
  27     if (N <= 1)
  28     {
  29         return;
  30     }
  31
  32     for (uint i = 0; i < N - 1; i++)
  33         if ((sortDir && (data[i] > data[i + 1])) || (!sortDir && (data[i] < data[i + 1])))
  34         {
  35             fprintf(stderr, "checkOrder() failed!!!\n");
  36             exit(EXIT_FAILURE);
  37         }
  38 }
  39
  40 static uint umin(uint a, uint b)
  41 {
  42     return (a <= b) ? a : b;
  43 }
  44
  45 static uint getSampleCount(uint dividend)
  46 {
  47     return ((dividend % SAMPLE_STRIDE) != 0) ? (dividend / SAMPLE_STRIDE + 1) : (dividend / SAMPLE_STRIDE);
  48 }
  49
  50 static uint nextPowerOfTwo(uint x)
  51 {
  52     --x;
  53     x |= x >> 1;
  54     x |= x >> 2;
  55     x |= x >> 4;
  56     x |= x >> 8;
  57     x |= x >> 16;
  58     return ++x;
  59 }
  60
  61 static uint binarySearchInclusive(uint val, uint *data, uint L, uint sortDir)
  62 {
  63     if (L == 0)
  64     {
  65         return 0;
  66     }
  67
  68     uint pos = 0;
  69
  70     for (uint stride = nextPowerOfTwo(L); stride > 0; stride >>= 1)
  71     {
  72         uint newPos = umin(pos + stride, L);
  73
  74         if ((sortDir && (data[newPos - 1] <= val)) || (!sortDir && (data[newPos - 1] >= val)))
  75         {
  76             pos = newPos;
  77         }
  78     }
  79
  80     return pos;
  81 }
  82
  83 static uint binarySearchExclusive(uint val, uint *data, uint L, uint sortDir)
  84 {
  85     if (L == 0)
  86     {
  87         return 0;
  88     }
  89
  90     uint pos = 0;
  91
  92     for (uint stride = nextPowerOfTwo(L); stride > 0; stride >>= 1)
  93     {
  94         uint newPos = umin(pos + stride, L);
  95
  96         if ((sortDir && (data[newPos - 1] < val)) || (!sortDir && (data[newPos - 1] > val)))
  97         {
  98             pos = newPos;
  99         }
 100     }
 101
 102     return pos;
 103 }
 104
 105
 106
 107 ////////////////////////////////////////////////////////////////////////////////
 108 // Merge step 1: find sample ranks in each segment
 109 ////////////////////////////////////////////////////////////////////////////////
 110 static void generateSampleRanks(
 111     uint *ranksA,
 112     uint *ranksB,
 113     uint *srcKey,
 114     uint stride,
 115     uint N,
 116     uint sortDir
 117 )
 118 {
 119     uint lastSegmentElements = N % (2 * stride);
 120     uint         sampleCount = (lastSegmentElements > stride) ? (N + 2 * stride - lastSegmentElements) / (2 * SAMPLE_STRIDE) : (N - lastSegmentElements) / (2 * SAMPLE_STRIDE);
 121
 122     for (uint pos = 0; pos < sampleCount; pos++)
 123     {
 124         const uint           i = pos & ((stride / SAMPLE_STRIDE) - 1);
 125         const uint segmentBase = (pos - i) * (2 * SAMPLE_STRIDE);
 126
 127         const uint lenA = stride;
 128         const uint lenB = umin(stride, N - segmentBase - stride);
 129         const uint   nA = stride / SAMPLE_STRIDE;
 130         const uint   nB = getSampleCount(lenB);
 131
 132         if (i < nA)
 133         {
 134             ranksA[(segmentBase +      0) / SAMPLE_STRIDE + i] = i * SAMPLE_STRIDE;
 135             ranksB[(segmentBase +      0) / SAMPLE_STRIDE + i] = binarySearchExclusive(srcKey[segmentBase + i * SAMPLE_STRIDE], srcKey + segmentBase + stride, lenB, sortDir);
 136         }
 137
 138         if (i < nB)
 139         {
 140             ranksB[(segmentBase + stride) / SAMPLE_STRIDE + i] = i * SAMPLE_STRIDE;
 141             ranksA[(segmentBase + stride) / SAMPLE_STRIDE + i] = binarySearchInclusive(srcKey[segmentBase + stride + i * SAMPLE_STRIDE], srcKey + segmentBase, lenA, sortDir);
 142         }
 143     }
 144 }
 145
 146
 147
 148 ////////////////////////////////////////////////////////////////////////////////
 149 // Merge step 2: merge ranks and indices to derive elementary intervals
 150 ////////////////////////////////////////////////////////////////////////////////
 151 static void mergeRanksAndIndices(
 152     uint *limits,
 153     uint *ranks,
 154     uint stride,
 155     uint N
 156 )
 157 {
 158     uint lastSegmentElements = N % (2 * stride);
 159     uint         sampleCount = (lastSegmentElements > stride) ? (N + 2 * stride - lastSegmentElements) / (2 * SAMPLE_STRIDE) : (N - lastSegmentElements) / (2 * SAMPLE_STRIDE);
 160
 161     for (uint pos = 0; pos < sampleCount; pos++)
 162     {
 163         const uint           i = pos & ((stride / SAMPLE_STRIDE) - 1);
 164         const uint segmentBase = (pos - i) * (2 * SAMPLE_STRIDE);
 165
 166         const uint lenA = stride;
 167         const uint lenB = umin(stride, N - segmentBase - stride);
 168         const uint   nA = stride / SAMPLE_STRIDE;
 169         const uint   nB = getSampleCount(lenB);
 170
 171         if (i < nA)
 172         {
 173             uint dstPosA = binarySearchExclusive(ranks[(segmentBase + 0) / SAMPLE_STRIDE + i], ranks + (segmentBase + stride) / SAMPLE_STRIDE, nB, 1) + i;
 174             assert(dstPosA < nA + nB);
 175             limits[(segmentBase / SAMPLE_STRIDE) + dstPosA] = ranks[(segmentBase + 0) / SAMPLE_STRIDE + i];
 176         }
 177
 178         if (i < nB)
 179         {
 180             uint dstPosA = binarySearchInclusive(ranks[(segmentBase + stride) / SAMPLE_STRIDE + i], ranks + (segmentBase + 0) / SAMPLE_STRIDE, nA, 1) + i;
 181             assert(dstPosA < nA + nB);
 182             limits[(segmentBase / SAMPLE_STRIDE) + dstPosA] = ranks[(segmentBase + stride) / SAMPLE_STRIDE + i];
 183         }
 184     }
 185 }
 186
 187
 188
 189 ////////////////////////////////////////////////////////////////////////////////
 190 // Merge step 3: merge elementary intervals (each interval is <= SAMPLE_STRIDE)
 191 ////////////////////////////////////////////////////////////////////////////////
 192 static void merge(
 193     uint *dstKey,
 194     uint *dstVal,
 195     uint *srcAKey,
 196     uint *srcAVal,
 197     uint *srcBKey,
 198     uint *srcBVal,
 199     uint lenA,
 200     uint lenB,
 201     uint sortDir
 202 )
 203 {
 204     checkOrder(srcAKey, lenA, sortDir);
 205     checkOrder(srcBKey, lenB, sortDir);
 206
 207     for (uint i = 0; i < lenA; i++)
 208     {
 209         uint dstPos = binarySearchExclusive(srcAKey[i], srcBKey, lenB, sortDir) + i;
 210         assert(dstPos < lenA + lenB);
 211         dstKey[dstPos] = srcAKey[i];
 212         dstVal[dstPos] = srcAVal[i];
 213     }
 214
 215     for (uint i = 0; i < lenB; i++)
 216     {
 217         uint dstPos = binarySearchInclusive(srcBKey[i], srcAKey, lenA, sortDir) + i;
 218         assert(dstPos < lenA + lenB);
 219         dstKey[dstPos] = srcBKey[i];
 220         dstVal[dstPos] = srcBVal[i];
 221     }
 222 }
 223
 224 static void mergeElementaryIntervals(
 225     uint *dstKey,
 226     uint *dstVal,
 227     uint *srcKey,
 228     uint *srcVal,
 229     uint *limitsA,
 230     uint *limitsB,
 231     uint stride,
 232     uint N,
 233     uint sortDir
 234 )
 235 {
 236     uint lastSegmentElements = N % (2 * stride);
 237     uint          mergePairs = (lastSegmentElements > stride) ? getSampleCount(N) : (N - lastSegmentElements) / SAMPLE_STRIDE;
 238
 239     for (uint pos = 0; pos < mergePairs; pos++)
 240     {
 241         uint           i = pos & ((2 * stride) / SAMPLE_STRIDE - 1);
 242         uint segmentBase = (pos - i) * SAMPLE_STRIDE;
 243
 244         const uint lenA = stride;
 245         const uint lenB = umin(stride, N - segmentBase - stride);
 246         const uint   nA = stride / SAMPLE_STRIDE;
 247         const uint   nB = getSampleCount(lenB);
 248         const uint    n = nA + nB;
 249
 250         const uint   startPosA = limitsA[pos];
 251         const uint     endPosA = (i + 1 < n) ? limitsA[pos + 1] : lenA;
 252         const uint   startPosB = limitsB[pos];
 253         const uint     endPosB = (i + 1 < n) ? limitsB[pos + 1] : lenB;
 254         const uint startPosDst = startPosA + startPosB;
 255
 256         assert(startPosA <= endPosA && endPosA <= lenA);
 257         assert(startPosB <= endPosB && endPosB <= lenB);
 258         assert((endPosA - startPosA) <= SAMPLE_STRIDE);
 259         assert((endPosB - startPosB) <= SAMPLE_STRIDE);
 260
 261         merge(
 262             dstKey  + segmentBase + startPosDst,
 263             dstVal  + segmentBase + startPosDst,
 264             (srcKey + segmentBase +      0) + startPosA,
 265             (srcVal + segmentBase +      0) + startPosA,
 266             (srcKey + segmentBase + stride) + startPosB,
 267             (srcVal + segmentBase + stride) + startPosB,
 268             endPosA - startPosA,
 269             endPosB - startPosB,
 270             sortDir
 271         );
 272     }
 273 }
 274
 275
 276
 277 ////////////////////////////////////////////////////////////////////////////////
 278 // Retarded bubble sort
 279 ////////////////////////////////////////////////////////////////////////////////
 280 static void bubbleSort(uint *key, uint *val, uint N, uint sortDir)
 281 {
 282     if (N <= 1)
 283     {
 284         return;
 285     }
 286
 287     for (uint bottom = 0; bottom < N - 1; bottom++)
 288     {
 289         uint savePos = bottom;
 290         uint saveKey = key[bottom];
 291
 292         for (uint i = bottom + 1; i < N; i++)
 293             if (
 294                 (sortDir && (key[i] < saveKey)) ||
 295                 (!sortDir && (key[i] > saveKey))
 296             )
 297             {
 298                 savePos = i;
 299                 saveKey = key[i];
 300             }
 301
 302         if (savePos != bottom)
 303         {
 304             uint t;
 305             t = key[savePos];
 306             key[savePos] = key[bottom];
 307             key[bottom] = t;
 308             t = val[savePos];
 309             val[savePos] = val[bottom];
 310             val[bottom] = t;
 311         }
 312     }
 313 }
 314
 315
 316
 317 ////////////////////////////////////////////////////////////////////////////////
 318 // Interface function
 319 ////////////////////////////////////////////////////////////////////////////////
 320 extern "C" void mergeSortHost(
 321     uint *dstKey,
 322     uint *dstVal,
 323     uint *bufKey,
 324     uint *bufVal,
 325     uint *srcKey,
 326     uint *srcVal,
 327     uint N,
 328     uint sortDir
 329 )
 330 {
 331     uint *ikey, *ival, *okey, *oval;
 332     uint stageCount = 0;
 333
 334     for (uint stride = SHARED_SIZE_LIMIT; stride < N; stride <<= 1, stageCount++);
 335
 336     if (stageCount & 1)
 337     {
 338         ikey = bufKey;
 339         ival = bufVal;
 340         okey = dstKey;
 341         oval = dstVal;
 342     }
 343     else
 344     {
 345         ikey = dstKey;
 346         ival = dstVal;
 347         okey = bufKey;
 348         oval = bufVal;
 349     }
 350
 351     printf("Bottom-level sort...\n");
 352     memcpy(ikey, srcKey, N * sizeof(uint));
 353     memcpy(ival, srcVal, N * sizeof(uint));
 354
 355     for (uint pos = 0; pos < N; pos += SHARED_SIZE_LIMIT)
 356     {
 357         bubbleSort(ikey + pos, ival + pos, umin(SHARED_SIZE_LIMIT, N - pos), sortDir);
 358     }
 359
 360     printf("Merge...\n");
 361     uint  *ranksA = (uint *)malloc(getSampleCount(N) * sizeof(uint));
 362     uint  *ranksB = (uint *)malloc(getSampleCount(N) * sizeof(uint));
 363     uint *limitsA = (uint *)malloc(getSampleCount(N) * sizeof(uint));
 364     uint *limitsB = (uint *)malloc(getSampleCount(N) * sizeof(uint));
 365     memset(ranksA,  0xFF, getSampleCount(N) * sizeof(uint));
 366     memset(ranksB,  0xFF, getSampleCount(N) * sizeof(uint));
 367     memset(limitsA, 0xFF, getSampleCount(N) * sizeof(uint));
 368     memset(limitsB, 0xFF, getSampleCount(N) * sizeof(uint));
 369
 370     for (uint stride = SHARED_SIZE_LIMIT; stride < N; stride <<= 1)
 371     {
 372         uint lastSegmentElements = N % (2 * stride);
 373
 374         //Find sample ranks and prepare for limiters merge
 375         generateSampleRanks(ranksA, ranksB, ikey, stride, N, sortDir);
 376
 377         //Merge ranks and indices
 378         mergeRanksAndIndices(limitsA, ranksA, stride, N);
 379         mergeRanksAndIndices(limitsB, ranksB, stride, N);
 380
 381         //Merge elementary intervals
 382         mergeElementaryIntervals(okey, oval, ikey, ival, limitsA, limitsB, stride, N, sortDir);
 383
 384         if (lastSegmentElements <= stride)
 385         {
 386             //Last merge segment consists of a single array which just needs to be passed through
 387             memcpy(okey + (N - lastSegmentElements), ikey + (N - lastSegmentElements), lastSegmentElements * sizeof(uint));
 388             memcpy(oval + (N - lastSegmentElements), ival + (N - lastSegmentElements), lastSegmentElements * sizeof(uint));
 389         }
 390
 391         uint *t;
 392         t = ikey;
 393         ikey = okey;
 394         okey = t;
 395         t = ival;
 396         ival = oval;
 397         oval = t;
 398     }
 399
 400     free(limitsB);
 401     free(limitsA);
 402     free(ranksB);
 403     free(ranksA);
 404 }
 405