| 1 | //
|
|---|
| 2 | // Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
|
|---|
| 3 | //
|
|---|
| 4 | // The contents of this file are covered under the licence agreement in the
|
|---|
| 5 | // file "LICENCE" distributed with Cforall.
|
|---|
| 6 | //
|
|---|
| 7 | // quickSort.c -- In-place concurrent quick-sort: threads are created to partition to a specific depth, then sequential
|
|---|
| 8 | // recursive-calls are use to sort each partition.
|
|---|
| 9 | //
|
|---|
| 10 | // Author : Peter A. Buhr
|
|---|
| 11 | // Created On : Wed Dec 6 12:15:52 2017
|
|---|
| 12 | // Last Modified By : Peter A. Buhr
|
|---|
| 13 | // Last Modified On : Thu Oct 10 13:58:18 2019
|
|---|
| 14 | // Update Count : 176
|
|---|
| 15 | //
|
|---|
| 16 |
|
|---|
| 17 | #include <fstream.hfa>
|
|---|
| 18 | #include <stdlib.hfa>
|
|---|
| 19 | #include <kernel.hfa>
|
|---|
| 20 | #include <thread.hfa>
|
|---|
| 21 | #include <string.h> // strcmp
|
|---|
| 22 |
|
|---|
| 23 | thread Quicksort {
|
|---|
| 24 | int * values; // communication variables
|
|---|
| 25 | int low, high, depth;
|
|---|
| 26 | };
|
|---|
| 27 |
|
|---|
| 28 | void ?{}( Quicksort & qs, int values[], int size, int depth ) {
|
|---|
| 29 | qs.values = values; qs.low = 0; qs.high = size; qs.depth = depth;
|
|---|
| 30 | } // Quicksort
|
|---|
| 31 |
|
|---|
| 32 | void main( Quicksort & qs ) { // thread starts here
|
|---|
| 33 | // nested routines: information hiding
|
|---|
| 34 |
|
|---|
| 35 | void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) {
|
|---|
| 36 | qs.values = values; qs.low = low; qs.high = high; qs.depth = depth;
|
|---|
| 37 | } // Quicksort
|
|---|
| 38 |
|
|---|
| 39 | void sort( int values[], int low, int high, int depth ) {
|
|---|
| 40 | int left, right; // index to left/right-hand side of the values
|
|---|
| 41 | int pivot; // pivot value of values
|
|---|
| 42 | int swap; // temporary
|
|---|
| 43 |
|
|---|
| 44 | //verify(); // check for stack overflow due to recursion
|
|---|
| 45 |
|
|---|
| 46 | // partition while 2 or more elements in the array
|
|---|
| 47 | if ( low < high ) {
|
|---|
| 48 | pivot = values[low + ( high - low ) / 2];
|
|---|
| 49 | left = low;
|
|---|
| 50 | right = high;
|
|---|
| 51 |
|
|---|
| 52 | // partition: move values less < pivot before the pivot and values > pivot after the pivot
|
|---|
| 53 | do {
|
|---|
| 54 | while ( values[left] < pivot ) left += 1; // changed values[left] < pivot
|
|---|
| 55 | while ( pivot < values[right] ) right -= 1;
|
|---|
| 56 | if ( left <= right ) {
|
|---|
| 57 | swap = values[left]; // interchange values
|
|---|
| 58 | values[left] = values[right];
|
|---|
| 59 | values[right] = swap;
|
|---|
| 60 | left += 1;
|
|---|
| 61 | right -= 1;
|
|---|
| 62 | } // if
|
|---|
| 63 | } while ( left <= right );
|
|---|
| 64 |
|
|---|
| 65 | // restrict number of tasks to slightly greater than number of processors
|
|---|
| 66 | if ( depth > 0 ) {
|
|---|
| 67 | depth -= 1;
|
|---|
| 68 | Quicksort lqs = { values, low, right, depth }; // concurrently sort lower half
|
|---|
| 69 | Quicksort rqs = { values, left, high, depth }; // concurrently sort upper half
|
|---|
| 70 | // Quicksort lqs = { values, low, right, depth }; // concurrently sort lower half
|
|---|
| 71 | // sort( values, left, high, depth ); // concurrently sort upper half
|
|---|
| 72 | } else {
|
|---|
| 73 | sort( values, low, right, 0 ); // sequentially sort lower half
|
|---|
| 74 | sort( values, left, high, 0 ); // sequentially sort upper half
|
|---|
| 75 | } // if
|
|---|
| 76 | } // if
|
|---|
| 77 | } // sort
|
|---|
| 78 |
|
|---|
| 79 | with( qs ) {
|
|---|
| 80 | sort( values, low, high, depth );
|
|---|
| 81 | } // with
|
|---|
| 82 | } // main
|
|---|
| 83 |
|
|---|
| 84 |
|
|---|
| 85 | bool convert( int & val, const char * nptr ) { // convert C string to integer
|
|---|
| 86 | char * eptr;
|
|---|
| 87 | int temp = strto( nptr, &eptr, 10 ); // do not change val on false
|
|---|
| 88 | // true => entire string valid with no extra characters
|
|---|
| 89 | return *nptr != '\0' && *eptr == '\0' ? val = temp, true : false;
|
|---|
| 90 | } // convert
|
|---|
| 91 |
|
|---|
| 92 | void usage( char * argv[] ) {
|
|---|
| 93 | sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )";
|
|---|
| 94 | exit( EXIT_FAILURE ); // TERMINATE!
|
|---|
| 95 | } // usage
|
|---|
| 96 |
|
|---|
| 97 |
|
|---|
| 98 | int main( int argc, char * argv[] ) {
|
|---|
| 99 | ifstream & unsortedfile = sin;
|
|---|
| 100 | ofstream & sortedfile = sout; // default value
|
|---|
| 101 | int depth = 0, size;
|
|---|
| 102 |
|
|---|
| 103 | if ( argc != 1 ) { // do not use defaults
|
|---|
| 104 | if ( argc < 2 || argc > 4 ) usage( argv ); // wrong number of options
|
|---|
| 105 | if ( strcmp( argv[1], "-t" ) == 0 ) { // timing ?
|
|---|
| 106 | &unsortedfile = (ifstream *)0; // no input
|
|---|
| 107 | choose ( argc ) {
|
|---|
| 108 | case 4:
|
|---|
| 109 | if ( ! convert( depth, argv[3] ) || depth < 0 ) usage( argv );
|
|---|
| 110 | fallthrough;
|
|---|
| 111 | case 3:
|
|---|
| 112 | if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv );
|
|---|
| 113 | } // choose
|
|---|
| 114 | } else { // sort file
|
|---|
| 115 | choose ( argc ) {
|
|---|
| 116 | case 3:
|
|---|
| 117 | &sortedfile = new( (const char *)argv[2] ); // open the output file
|
|---|
| 118 | if ( fail( sortedfile ) ) {
|
|---|
| 119 | serr | "Error! Could not open sorted output file \"" | argv[2] | "\"";
|
|---|
| 120 | usage( argv );
|
|---|
| 121 | } // if
|
|---|
| 122 | fallthrough;
|
|---|
| 123 | case 2:
|
|---|
| 124 | &unsortedfile = new( (const char *)argv[1] ); // open the input file
|
|---|
| 125 | if ( fail( unsortedfile ) ) {
|
|---|
| 126 | serr | "Error! Could not open unsorted input file \"" | argv[1] | "\"";
|
|---|
| 127 | usage( argv );
|
|---|
| 128 | } // if
|
|---|
| 129 | } // choose
|
|---|
| 130 | } // if
|
|---|
| 131 | } // if
|
|---|
| 132 | sortedfile | nlOff; // turn off auto newline
|
|---|
| 133 |
|
|---|
| 134 | enum { ValuesPerLine = 22 }; // number of values printed per line
|
|---|
| 135 |
|
|---|
| 136 | if ( &unsortedfile ) { // generate output ?
|
|---|
| 137 | for () {
|
|---|
| 138 | unsortedfile | size; // read number of elements in the list
|
|---|
| 139 | if ( eof( unsortedfile ) ) break;
|
|---|
| 140 | int * values = alloc( size ); // values to be sorted, too large to put on stack
|
|---|
| 141 | for ( counter; size ) { // read unsorted numbers
|
|---|
| 142 | unsortedfile | values[counter];
|
|---|
| 143 | if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " ";
|
|---|
| 144 | sortedfile | values[counter];
|
|---|
| 145 | if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
|
|---|
| 146 | } // for
|
|---|
| 147 | sortedfile | nl;
|
|---|
| 148 | if ( size > 0 ) { // values to sort ?
|
|---|
| 149 | Quicksort QS = { values, size - 1, 0 }; // sort values
|
|---|
| 150 | } // wait until sort tasks terminate
|
|---|
| 151 | for ( counter; size ) { // print sorted list
|
|---|
| 152 | if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " ";
|
|---|
| 153 | sortedfile | values[counter];
|
|---|
| 154 | if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
|
|---|
| 155 | } // for
|
|---|
| 156 | sortedfile | nl | nl;
|
|---|
| 157 |
|
|---|
| 158 | delete( values );
|
|---|
| 159 | } // for
|
|---|
| 160 | if ( &unsortedfile != &sin ) delete( &unsortedfile ); // close input/output files
|
|---|
| 161 | if ( &sortedfile != &sout ) delete( &sortedfile );
|
|---|
| 162 | } else {
|
|---|
| 163 | processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
|
|---|
| 164 |
|
|---|
| 165 | int * values = alloc( size ); // values to be sorted, too large to put on stack
|
|---|
| 166 | for ( counter; size ) { // generate unsorted numbers
|
|---|
| 167 | values[counter] = size - counter; // descending values
|
|---|
| 168 | } // for
|
|---|
| 169 | for ( int i = 0; i < 200; i +=1 ) { // random shuffle a few values
|
|---|
| 170 | swap( values[rand() % size], values[rand() % size] );
|
|---|
| 171 | } // for
|
|---|
| 172 | {
|
|---|
| 173 | Quicksort QS = { values, size - 1, depth }; // sort values
|
|---|
| 174 | } // wait until sort tasks terminate
|
|---|
| 175 |
|
|---|
| 176 | // for ( counter; size - 1 ) { // check sorting
|
|---|
| 177 | // if ( values[counter] > values[counter + 1] ) abort();
|
|---|
| 178 | // } // for
|
|---|
| 179 |
|
|---|
| 180 | delete( values );
|
|---|
| 181 | } // if
|
|---|
| 182 | } // main
|
|---|
| 183 |
|
|---|
| 184 | // for depth in 0 1 2 3 4 5 ; do echo "sort 500000000 values with ${depth} depth" ; time -f "%Uu %Ss %E %Mkb" a.out -t 500000000 ${depth} ; done
|
|---|
| 185 |
|
|---|
| 186 | // Local Variables: //
|
|---|
| 187 | // tab-width: 4 //
|
|---|
| 188 | // compile-command: "cfa quickSort.cfa" //
|
|---|
| 189 | // End: //
|
|---|
