Context Navigation

quickSort.cfa @ 4ff7ea3

Last change on this file since 4ff7ea3 was e8b5ba4, checked in by Peter A. Buhr <pabuhr@…>, 2 months ago
update how input/output files are opened
Property mode set to `100644`
File size: 6.9 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 : 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: //

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format