Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
quickSort.c
Go to the documentation of this file.
1 /*
2 * quickSort.c
3 * Hitmap example
4 * Parallel Quick-Sort algorithm for generic numbers of native type 'double'
5 *
6 * v1.0
7 * (c) 2013, Arturo Gonzalez-Escribano
8 */
9 
10 /*
11  * <license>
12  *
13  * Hitmap v1.2
14  *
15  * This software is provided to enhance knowledge and encourage progress in the scientific
16  * community. It should be used only for research and educational purposes. Any reproduction
17  * or use for commercial purpose, public redistribution, in source or binary forms, with or
18  * without modifications, is NOT ALLOWED without the previous authorization of the copyright
19  * holder. The origin of this software must not be misrepresented; you must not claim that you
20  * wrote the original software. If you use this software for any purpose (e.g. publication),
21  * a reference to the software package and the authors must be included.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS" AND ANY
24  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
25  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
26  * THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
27  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Copyright (c) 2007-2015, Trasgo Group, Universidad de Valladolid.
34  * All rights reserved.
35  *
36  * More information on http://trasgo.infor.uva.es/
37  *
38  * </license>
39 */
40 
41 #include <stdio.h>
42 #include <stdlib.h>
43 #include <hitmap.h>
44 
45 hit_tileNewType( double );
46 
49 
50 #define swap(a,b) { double c=a; a=b; b=c; }
51 
52 /* PROTOTYPES */
53 void parallelQuickSort( HitTile_double *data, HitLayout whole ) ;
54 int sequentialPivoting( double pivot, HitTile_double data ) ;
55 void initV( HitTile_double tileV ) ;
56 
57 // ALTERNATIVE USING qsort(3), SLOWER
58 #ifdef USE_QSORT3
59 int comparisonOp( const void *a, const void *b ) {
60  const double *da = (const double *)a;
61  const double *db = (const double *)b;
62  if ( *da < *db ) return -1;
63  else if ( *da == *db ) return 0;
64  else return 1;
65 }
66 #endif
67 
68 /* A. MAIN */
69 int main(int argc, char *argv[]){
70  hit_comInit( &argc, &argv );
71 
72  int numElems;
73 
74  /* 0. READ PARAMETER */
75  if ( argc < 2 ) {
76  fprintf(stderr, "Usage: %s <numElems>\n", argv[0] );
77  exit( 1 );
78  }
79  else {
80  numElems = atoi( argv[1] );
81  if ( numElems < 0 ) {
82  fprintf(stderr, "Usage: %s <numElems>\n", argv[0] );
83  exit( 1 );
84  }
85  }
86 
87  /* 1. INIT CLOCKS */
89  hit_clockStart( mainClock );
90  hit_clockReset( seqCompClock );
91 
92  /* 2. CREATE VIRTUAL TOPOLOGY */
93  HitTopology topo = hit_topology( plug_topPlain );
94 
95  /* 3. DECLARE FULL VECTOR WITHOUT MEMORY */
96  HitTile_double V;
97  hit_tileDomain( &V, double, 1, numElems );
98 
99  /* 4. COMPUTE ORIGINAL PARTITION */
100  HitLayout lay = hit_layout(plug_layBlocks, topo, hit_tileShape( V ) );
101 
102  /* 5. CREATE AND ALLOCATE LOCAL TILE */
103  HitTile_double tileV;
104  hit_tileSelect( &tileV, &V, hit_layShape(lay) );
105  hit_tileAlloc( &tileV );
106 
107  /* 6. INITIALIZE LOCAL TILE */
108  initV( tileV );
109 
110  /* 7. START RECURSIVE PARTITION AND SORTING */
111  parallelQuickSort( &tileV, lay );
112 
113  /* 8. CLOCK RESULTS */
114  hit_clockStop( mainClock );
115  hit_clockReduce( lay, mainClock );
116  hit_clockReduce( lay, seqCompClock );
117  hit_clockPrintMax( mainClock );
118  hit_clockPrintMax( seqCompClock );
119 
120 #ifdef WRITE_RESULT
121  /* 9. WRITE RESULT VECTOR */
122  hit_tileTextFileWrite( &tileV, "V.result.dtxt", HIT_FILE_ARRAY, HIT_FILE_DOUBLE, 14, 12 );
123 #endif
124 
125  /* 10. FREE RESOURCES */
126  hit_tileFree( tileV );
127  hit_layFree( lay );
128  hit_topFree( topo );
129 
130  hit_comFinalize();
131  return 0;
132 }
133 
134 
135 /* B. INITIALIZE VECTOR */
136 void initV( HitTile_double tileV ) {
137  int i;
138 
139  /* 1. RANDOM SEED */
140  srand48( 364543 );
141 
142  /* 2. COMPUTE SEED AT FIRST ELEMENT */
143  for (i=0; i < hit_tileDimBegin( tileV, 0 ); i++) drand48();
144 
145  /* 3. INIT VALUES */
146  hit_tileForDimDomain( tileV, 0, i )
147  hit_tileElemAt( tileV, 1, i ) = drand48();
148 
149 #ifdef WRITE_DATA
150  /* 4. WRITE V ON FILE FOR CHECKING */
151  hit_tileTextFileWrite( &tileV, "V.orig.dtxt", HIT_FILE_ARRAY, HIT_FILE_DOUBLE, 14, 12 );
152 #endif
153 }
154 
155 
156 /* C. FUNCTION TO COMPUTE SEQUENTIAL PIVOTING */
157 int sequentialPivoting( double pivot, HitTile_double data ) {
158 
159  int lo = 0;
160  int hi = hit_tileCard( data )-1;
161 
162  double save = hit_tileElemAt1( data, lo );
163 
164  while( lo < hi ) {
165  /* SEARCH BACKWARD FOR LESSER THAN PIVOT */
166  while ( hit_tileElemAt1( data, hi ) >= pivot && ( lo < hi )) { hi--; }
167  if ( lo != hi )
168  {
169  hit_tileElemAt1( data, lo ) = hit_tileElemAt1( data, hi );
170  lo++;
171  }
172 
173  /* SEARCH FORWARD FOR GREATER THAN PIVOT */
174  while ( hit_tileElemAt1( data, lo ) <= pivot && lo < hi ) { lo++; }
175  if (lo != hi)
176  {
177  hit_tileElemAt1( data, hi ) = hit_tileElemAt1( data, lo );
178  hi--;
179  }
180  }
181  hit_tileElemAt1( data, lo ) = save;
182 
183  /* RETURN VALUE */
184  if ( save <= pivot ) return lo + 1;
185  else return lo;
186 }
187 
188 
189 /* D. COMPLETE SEQUENTIAL QUICKSORT */
190 int sequentialQuickSort( HitTile_double data, int begin, int end ) {
191 
192  if ( begin >= end ) return 0;
193 
194  int lo = begin;
195  int hi = end;
196 
197  double pivot = hit_tileElemAt1( data, begin );
198 
199  while( lo < hi ) {
200  /* SEARCH BACKWARD FOR LESSER THAN PIVOT */
201  while ( hit_tileElemAt1( data, hi ) >= pivot && ( lo < hi )) { hi--; }
202  if ( lo != hi )
203  {
204  hit_tileElemAt1( data, lo ) = hit_tileElemAt1( data, hi );
205  lo++;
206  }
207 
208  /* SEARCH FORWARD FOR GREATER THAN PIVOT */
209  while ( hit_tileElemAt1( data, lo ) <= pivot && lo < hi ) { lo++; }
210  if (lo != hi)
211  {
212  hit_tileElemAt1( data, hi ) = hit_tileElemAt1( data, lo );
213  hi--;
214  }
215  }
216  hit_tileElemAt1( data, lo ) = pivot;
217 
218  /* RECURSION */
219  sequentialQuickSort( data, begin, lo );
220  sequentialQuickSort( data, lo+1, end );
221 
222  /* RETURN VALUE */
223  return lo;
224 }
225 
226 /* E. PARALLEL QUICKSORT ALGORITHM */
227 void parallelQuickSort( HitTile_double *data, HitLayout whole ) {
228  HitTile_double left, right;
229  int leftCard, totalLeftCard, totalRightCard;
230 
231  /* 1. STOP RECURSION */
232  /* 1.a. TRIVIAL CASE: NON ACTIVE IN THE LAYOUT */
233  if ( ! hit_layImActive( whole ) ) return;
234  /* 1.b. TRIVIAL CASE: ONE DATA ELEMENT IF THE WHOLE LAYOUT */
235  if ( hit_shapeCard( hit_layFullShape( whole) ) <= 1 ) return;
236  /* 1.c. TRIVIAL SEQUENTIAL CASES FOR ONLY ONE ACTIVE PROCESS */
237  if ( hit_layNumActives( whole ) == 1 ) {
238  if ( hit_tileCard( *data ) <= 1 ) return;
239  if ( hit_tileCard( *data ) == 2 ) {
240  if ( hit_tileGet( *data, 1, 0 ) > hit_tileGet( *data, 1, 1 ) )
241  swap( hit_tileElemAt( *data, 1, 0 ), hit_tileElemAt( *data, 1, 1 ) );
242  return;
243  }
244  }
245 
246  /* OPTIMIZATION: FOR ONLY ONE ACTIVE PROCESS, USE A COMPLETE SEQUENTIAL QUICKSORT */
247  if ( hit_layNumActives( whole ) == 1 ) {
248  hit_clockContinue( seqCompClock );
249 #ifdef USE_QSORT3
250  // SLOWER ALTERNATIVE USING qsort(3)
251  qsort( data->data, (size_t)hit_tileCard(*data), sizeof(double), comparisonOp );
252 #else // DIRECT IMPLEMENTATION USING Hitmap TILES
253  sequentialQuickSort( *data, 0, hit_tileCard(*data)-1 );
254 #endif
255  hit_clockStop( seqCompClock );
256  return;
257  }
258 
259  /* 2. CHOOSE PIVOT */
260  /* 2.a. LOCAL PIVOT */
261  double pivot = hit_tileGet( *data, 1, 0 );
262  /* 2.b. MORE THAN ONE ACTIVE PROCESS: PIVOT IS THE MEAN OF LOCAL PIVOTS IN ALL ACTIVE PROCs. */
263  if ( hit_layNumActives( whole ) > 1 ) {
264  HitTile_double pivotTile;
265  hit_tileSingle( &pivotTile, pivot, double );
267  &HIT_TILE_NULL, &pivotTile, HIT_DOUBLE, HIT_OP_SUM_DOUBLE ) );
268  pivot = pivot / hit_layNumActives( whole );
269  }
270 
271  /* 3. SEQUENTIAL PIVOTING OF LOCAL DATA: RETURNS THE NUMBER OF ELEMENTS SMALLER THAN pivot */
272  hit_clockContinue( seqCompClock );
273  leftCard = sequentialPivoting( pivot, *data );
274  hit_clockStop( seqCompClock );
275 
276  /* 4. SELECT LOCAL SUBTILEs */
277  hit_tileSelect( &left, data, hit_shape( 1, hit_sigStd( leftCard ) ) );
278  hit_tileSelect( &right, data, hit_shape( 1, hit_sig( leftCard, hit_tileCard( *data )-1, 1 ) ) );
279 
280  /* 5. OPTIMIZATION FOR ONLY ONE ACTIVE PROCESS: SEQUENTIAL RECURSION USING THE ORIGINAL ARRAY */
281  if ( hit_layNumActives( whole ) == 1 ) {
282  parallelQuickSort( &left, whole );
283  parallelQuickSort( &right, whole );
284  return;
285  }
286 
287  /* 6. ALL-REDUCE THE CARDINALITY OF LOCAL LEFT PARTS */
288  HitTile_double leftCardTile;
289  hit_tileSingle( &leftCardTile, leftCard, int );
290  HitTile_double totalLeftCardTile;
291  hit_tileSingle( &totalLeftCardTile, totalLeftCard, int );
293  & leftCardTile, & totalLeftCardTile, HIT_INT, HIT_OP_SUM_INT ) );
294  totalRightCard = hit_shapeCard( hit_layFullShape(whole) ) - totalLeftCard;
295 
296  /* 7. SPLIT WORK IN WEIGHTED GROUPS, ACCORDING TO TOTAL LEFT vs. RIGHT CARDINALITIES */
297  double weights[2] = { totalLeftCard, totalRightCard };
298  HitShape twoElements = hit_shape( 1, hit_sigStd( 2 ) );
299  HitTopology activesTopo = hit_layActivesTopology(whole);
300  HitLayout groups = hit_layout( plug_layIndependentLB, activesTopo, twoElements, weights );
301  hit_topFree( activesTopo );
302 
303  /* 8. REDISTRIBUTE THE left,right PARTS TO THE PROCS. IN THE CORRESPONDING GROUP */
304  /* 8.a. DECLARE THE DOMAIN OF VIRTUAL left AND right ARRAYS */
305  HitShape leftGlobalShp = hit_shapeSubset( hit_layFullShape(whole), hit_shapeStd( 1, totalLeftCard ) );
306  HitShape rightGlobalShp = hit_shapeSubset( hit_layFullShape(whole), hit_shape( 1, hit_sig( totalLeftCard, totalLeftCard+totalRightCard-1, 1 ) ) );
307 
308  /* 8.b. COMPUTE LAYOUTS FOR THE DATA REDISTRIBUTION */
309  HitTopology gt0 = hit_layGroupTopo( groups, hit_lgr_elementGroup( groups, 0 ) );
310  HitTopology gt1 = hit_layGroupTopo( groups, hit_lgr_elementGroup( groups, 1 ) );
311  HitLayout leftLayout = hit_layout( plug_layBlocks, gt0, leftGlobalShp );
312  HitLayout rightLayout = hit_layout( plug_layBlocks, gt1, rightGlobalShp );
313 
314  /* 8.c. ALLOCATE BUFFERS FOR LOCAL PARTS */
315  HitTile_double newLeft, newRight;
316  hit_tileDomainShapeAlloc( &newLeft, double, hit_layShape( leftLayout ) );
317  hit_tileDomainShapeAlloc( &newRight, double, hit_layShape( rightLayout ) );
318 
319  /* 8.d. DATA REDISTRIBUTION */
320  hit_patternDoOnce( hit_patternRedistribute( whole, &left, &newLeft, HIT_DOUBLE, 1 ) );
321  hit_patternDoOnce( hit_patternRedistribute( whole, &right, &newRight, HIT_DOUBLE, 1 ) );
322 
323  /* 9. FREE MEMORY SPACE OF ORIGINAL DATA BEFORE RECURSION */
324  hit_tileFree( *data );
325 
326  /* 10. RECURSIVE CALLS */
327  if ( hit_layHasElem( groups, 0 ) ) parallelQuickSort( &newLeft, leftLayout );
328  if ( hit_layHasElem( groups, 1 ) ) parallelQuickSort( &newRight, rightLayout );
329 
330  /* 11.a. IF THE GROUP HAS BOTH, LEFT AND RIGHT PARTS, REDISTRIBUTE THEM IN ORDER */
331  if ( hit_layHasElem( groups, 0 ) && hit_layHasElem( groups, 1 ) ) {
332  hit_tileAlloc( data );
333  hit_tileSelectArrayCoords( &left, data, hit_shapeIntersect( hit_tileShape( *data ), leftGlobalShp ) );
334  hit_tileSelectArrayCoords( &right, data, hit_shapeIntersect( hit_tileShape( *data ), rightGlobalShp ) );
335 
336  hit_patternDoOnce( hit_patternRedistribute( whole, &newLeft, &left, HIT_DOUBLE, 0 ) );
337  hit_patternDoOnce( hit_patternRedistribute( whole, &newRight, &right, HIT_DOUBLE, 0 ) );
338  hit_tileFree( newLeft );
339  hit_tileFree( newRight );
340  }
341  /* 11.b. IF THE GROUP HAS ONLY LEFT, OR ONLY RIGHT PART, IT IS THE OUTPUT */
342  else if ( hit_layHasElem( groups, 0 ) ) *data = newLeft;
343  else if ( hit_layHasElem( groups, 1 ) ) *data = newRight;
344  //else *data = *(HitTile_double *)&HIT_TILE_NULL;
345 
346  /* 12. FREE RESOURCES */
347  hit_layFree( groups );
348  hit_layFree( leftLayout );
349  hit_layFree( rightLayout );
350  hit_topFree( gt0 );
351  hit_topFree( gt1 );
352 }
#define hit_layFullShape(lay)
Definition: hit_layout.h:642
#define hit_shape(nd,...)
Definition: hit_sshape.h:175
HitClock seqCompClock
Definition: quickSort.c:48
#define hit_layShape(lay)
Definition: hit_layout.h:650
#define hit_tileNewType(baseType)
Definition: hit_tile.h:163
#define hit_clockSynchronizeAll()
Definition: hit_utils.h:55
HitOp HIT_OP_SUM_INT
Definition: hit_com.c:63
#define HIT_INT
Definition: hit_com.h:74
#define hit_shapeStd(nd,...)
Definition: hit_sshape.h:295
HitShape hit_shapeIntersect(HitShape sh1, HitShape sh2)
Definition: hit_shape.c:123
void srand48(long)
#define hit_tileElemAt(var, ndims,...)
Definition: hit_tile.h:519
#define hit_tileSingle(tile, var, type)
Definition: hit_tile.h:266
#define hit_clockContinue(c)
Definition: hit_utils.h:121
HitTopology hit_layGroupTopo(HitLayout lay, int groupId)
Definition: hit_layout.c:2318
#define hit_tileAlloc(var)
Definition: hit_tile.h:319
#define hit_topology(name,...)
Definition: hit_topology.h:308
HitRanks HIT_RANKS_NULL
Definition: hit_topology.c:68
#define HIT_FILE_DOUBLE
Definition: hit_tile.h:189
HitClock mainClock
Definition: cannonAsync.c:55
#define hit_tileCard(var)
Definition: hit_tile.h:763
#define hit_tileSelect(newVar, oldVar, shape)
Definition: hit_tile.h:453
#define hit_clockPrintMax(c)
Definition: hit_utils.h:175
#define hit_tileDomainShapeAlloc(newVarP, baseType, shape)
Definition: hit_tile.h:354
void parallelQuickSort(HitTile_double *data, HitLayout whole)
Definition: quickSort.c:227
#define hit_tileDimBegin(var, dim)
Definition: hit_tile.h:786
#define hit_clockReset(c)
Definition: hit_utils.h:78
#define hit_tileTextFileWrite(var, file, coord, datatype, s1, s2)
Definition: hit_tile.h:1011
void hit_topFree(HitTopology topo)
Definition: hit_topology.c:129
#define hit_layHasElem(lay, element)
Definition: hit_layout.h:947
HitOp HIT_OP_SUM_DOUBLE
Definition: hit_com.c:66
void hit_comInit(int *pargc, char **pargv[])
Definition: hit_com.c:111
#define hit_comDoOnce(com)
Definition: hit_com.h:1003
HitPattern hit_patternRedistribute(HitLayout lay, void *tileP1, void *tileP2, HitType baseType, int flagCompact)
Definition: hit_pattern.c:653
#define hit_layImActive(lay)
Definition: hit_layout.h:797
HitShape hit_shapeSubset(HitShape sh1, HitShape sh2)
Definition: hit_shape.c:157
#define hit_tileDomain(newVarP, baseType, numDims,...)
Definition: hit_tile.h:286
#define swap(a, b)
Definition: quickSort.c:50
void hit_layFree(HitLayout lay)
Definition: hit_layout.c:2251
#define hit_clockStop(c)
Definition: hit_utils.h:109
#define HIT_FILE_ARRAY
Definition: hit_tile.h:201
int main(int argc, char *argv[])
Definition: cannonAsync.c:62
int sequentialPivoting(double pivot, HitTile_double data)
Definition: quickSort.c:157
#define hit_tileSelectArrayCoords(newVar, oldVar, shape)
Definition: hit_tile.h:494
#define hit_comReduce(lay, root, tilePSend, tilePRecv, baseType, operation)
Definition: hit_com.h:725
#define hit_lgr_elementGroup(lay, element)
Definition: hit_layout.h:938
int sequentialQuickSort(HitTile_double data, int begin, int end)
Definition: quickSort.c:190
HitTile HIT_TILE_NULL
Definition: hit_tile.c:63
int hit_layNumActives(HitLayout lay)
Definition: hit_layout.c:2213
#define hit_tileForDimDomain(tile, dim, index)
Definition: hit_tile.h:587
#define hit_layout(name, topo,...)
Definition: hit_layout.h:415
HitLayout lay
Definition: heat.c:107
HitTopology hit_layActivesTopology(HitLayout lay)
Definition: hit_layout.c:2372
#define hit_tileFree(var)
Definition: hit_tile.h:369
#define HIT_DOUBLE
Definition: hit_com.h:78
void initV(HitTile_double tileV)
Definition: quickSort.c:136
double drand48()
#define hit_tileShape(var)
Definition: hit_tile.h:723
void hit_comFinalize()
Definition: hit_com.c:159
#define hit_clockReduce(lay, c)
Definition: hit_utils.h:139
#define hit_clockStart(c)
Definition: hit_utils.h:87
#define hit_patternDoOnce(pat)
Definition: hit_pattern.h:170