source: tests/concurrency/examples/quickSort.cfa@ d32679d5

Last change on this file since d32679d5 was c26bea2a, checked in by Peter A. Buhr <pabuhr@…>, 2 years ago

first attempt at renaming directory tests/concurrent to tests/concurrency to harmonize with other concurrency directory names
  • Property mode set to 100644
File size: 6.5 KB
Line 
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 : Wed Feb 12 18:24:47 2020
14// Update Count : 177
15//
16
17#include <fstream.hfa>
18#include <stdlib.hfa>
19#include <kernel.hfa>
20#include <thread.hfa>
21#include <string.h> // strcmp
22
23thread Quicksort {
24 int * values; // communication variables
25 int low, high, depth;
26};
27
28void ?{}( Quicksort & qs, int values[], int size, int depth ) {
29 qs.[values, low, high, depth] = [values, 0, size, depth];
30} // Quicksort
31
32void 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
85bool 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
92void 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
98int 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 ( i; 200 ) { // 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: //
Note: See TracBrowser for help on using the repository browser.