| 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 : Fri Oct 18 16:43:26 2024
|
|---|
| 14 | // Update Count : 200
|
|---|
| 15 | //
|
|---|
| 16 |
|
|---|
| 17 | #include <fstream.hfa> // sin/sout
|
|---|
| 18 | #include <stdlib.hfa> // convert
|
|---|
| 19 | #include <thread.hfa>
|
|---|
| 20 | #include <math.hfa> // sqrt
|
|---|
| 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, low, high, depth] = [values, 0, size, 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 | // convert(...) throws out_of_range or invalid_argument
|
|---|
| 85 | ExceptionDecl( cmd_error );
|
|---|
| 86 |
|
|---|
| 87 | int main( int argc, char * argv[] ) {
|
|---|
| 88 | ifstream unsortedfile = sin; // default values
|
|---|
| 89 | ofstream sortedfile = sout;
|
|---|
| 90 | // Must be signed because of the conversion routine.
|
|---|
| 91 | intmax_t depth = 0;
|
|---|
| 92 | intmax_t size = -1; // -1 means time mode not activated
|
|---|
| 93 |
|
|---|
| 94 | try {
|
|---|
| 95 | if ( 1 < argc && strcmp( argv[1], "-t" ) == 0 ) { // time mode ?
|
|---|
| 96 | choose ( argc ) {
|
|---|
| 97 | case 4:
|
|---|
| 98 | depth = convert( argv[3] ); // invalid integer ?
|
|---|
| 99 | if ( depth < 0 ) throw ExceptionInst( cmd_error );
|
|---|
| 100 | fallthrough;
|
|---|
| 101 | case 3:
|
|---|
| 102 | size = convert( argv[2] ); // invalid integer ?
|
|---|
| 103 | if ( size < 0 ) throw ExceptionInst( cmd_error );
|
|---|
| 104 | default: // wrong number of options
|
|---|
| 105 | throw ExceptionInst( cmd_error );
|
|---|
| 106 | } // choose
|
|---|
| 107 | } else { // sort file
|
|---|
| 108 | choose ( argc ) {
|
|---|
| 109 | case 4:
|
|---|
| 110 | depth = convert( argv[3] ); // invalid integer ?
|
|---|
| 111 | if ( depth < 0 ) throw ExceptionInst( cmd_error );
|
|---|
| 112 | fallthrough;
|
|---|
| 113 | case 3: case 2:
|
|---|
| 114 | // open input file first as output creates file
|
|---|
| 115 | if ( strcmp( argv[1], "d" ) != 0 ) {
|
|---|
| 116 | open( unsortedfile, argv[1] );
|
|---|
| 117 | } // if
|
|---|
| 118 | if ( argc > 2 && strcmp( argv[2], "d" ) != 0 ) {
|
|---|
| 119 | open( sortedfile, argv[2] );
|
|---|
| 120 | } // if
|
|---|
| 121 | fallthrough;
|
|---|
| 122 | case 1: ; // defaults
|
|---|
| 123 | default: // wrong number of options
|
|---|
| 124 | throw ExceptionInst( cmd_error );
|
|---|
| 125 | } // choose
|
|---|
| 126 | } // if
|
|---|
| 127 | } catch( open_failure * ) { // open failed ?
|
|---|
| 128 | exit | "Error! Could not open unsorted input file \"" | argv[1] | "\"";
|
|---|
| 129 | } catch( open_failure * ) { // open failed ?
|
|---|
| 130 | exit | "Error! Could not open sorted output file \"" | argv[2] | "\"";
|
|---|
| 131 | } catch( exception_t * ) { // catch any
|
|---|
| 132 | exit | "Usage: " | argv[0] | // TERMINATE
|
|---|
| 133 | " ( [ unsorted-file | 'd' [ sorted-file | 'd' [ depth (>= 0) ] ] ]"
|
|---|
| 134 | " | -t size (>= 0) [ depth (>= 0) ] )";
|
|---|
| 135 | } // try
|
|---|
| 136 |
|
|---|
| 137 | enum { ValuesPerLine = 22 }; // number of values printed per line
|
|---|
| 138 |
|
|---|
| 139 | sortedfile | nlOff; // turn off auto newline
|
|---|
| 140 |
|
|---|
| 141 | if ( size == -1 ) { // generate output ?
|
|---|
| 142 | int * values = 0p;
|
|---|
| 143 | try {
|
|---|
| 144 | for () {
|
|---|
| 145 | unsortedfile | size; // read number of elements in the list
|
|---|
| 146 | values = aalloc( size ); // values to be sorted, too large to put on stack
|
|---|
| 147 | for ( counter; size ) { // read unsorted numbers
|
|---|
| 148 | unsortedfile | values[counter];
|
|---|
| 149 | if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " ";
|
|---|
| 150 | sortedfile | values[counter];
|
|---|
| 151 | if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
|
|---|
| 152 | } // for
|
|---|
| 153 | sortedfile | nl;
|
|---|
| 154 |
|
|---|
| 155 | if ( size > 0 ) { // values to sort ?
|
|---|
| 156 | Quicksort QS = { values, size - 1, 0 }; // sort values
|
|---|
| 157 | } // wait until sort tasks terminate
|
|---|
| 158 | for ( counter; size ) { // print sorted list
|
|---|
| 159 | if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " ";
|
|---|
| 160 | sortedfile | values[counter];
|
|---|
| 161 | if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
|
|---|
| 162 | } // for
|
|---|
| 163 | sortedfile | nl | nl;
|
|---|
| 164 |
|
|---|
| 165 | delete( values );
|
|---|
| 166 | values = 0p;
|
|---|
| 167 | } // for
|
|---|
| 168 | } catch( end_of_file * ) {
|
|---|
| 169 | delete( values );
|
|---|
| 170 | } // try
|
|---|
| 171 | } else { // timing
|
|---|
| 172 | PRNG prng;
|
|---|
| 173 | processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
|
|---|
| 174 | int * values = aalloc( size ); // values to be sorted, too large to put on stack
|
|---|
| 175 |
|
|---|
| 176 | for ( counter; size ) { // generate unsorted numbers
|
|---|
| 177 | values[counter] = size - counter; // descending values
|
|---|
| 178 | } // for
|
|---|
| 179 |
|
|---|
| 180 | unsigned int times = sqrt( size );
|
|---|
| 181 | for ( unsigned int counter = 0; counter < times; counter += 1 ) {
|
|---|
| 182 | swap( values[0], values[prng(size)] ); // randomize unsorted numbers
|
|---|
| 183 | } // for
|
|---|
| 184 | {
|
|---|
| 185 | Quicksort QS = { values, size - 1, depth }; // sort values
|
|---|
| 186 | } // wait until sort tasks terminate
|
|---|
| 187 |
|
|---|
| 188 | // for ( counter; size - 1 ) { // check sorting
|
|---|
| 189 | // if ( values[counter] > values[counter + 1] ) abort();
|
|---|
| 190 | // } // for
|
|---|
| 191 |
|
|---|
| 192 | delete( values );
|
|---|
| 193 | } // if
|
|---|
| 194 | } // main
|
|---|
| 195 |
|
|---|
| 196 | // 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
|
|---|
| 197 |
|
|---|
| 198 | // Local Variables: //
|
|---|
| 199 | // tab-width: 4 //
|
|---|
| 200 | // compile-command: "cfa quickSort.cfa" //
|
|---|
| 201 | // End: //
|
|---|
