Context Navigation

quickSort.cfa @ ad47ec4

Last change on this file since ad47ec4 was 3ac5fd8, checked in by Peter A. Buhr <pabuhr@…>, 3 months ago
first attempt changing end-of-file to an exception
Property mode set to `100644`
File size: 7.0 KB

Rev	Line
[764b4b2]	1	//
[2e457d8]	2	// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
	3	//
[90449e4]	4	// The contents of this file are covered under the licence agreement in the
	5	// file "LICENCE" distributed with Cforall.
[764b4b2]	6	//
[90449e4]	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.
[764b4b2]	9	//
[90449e4]	10	// Author : Peter A. Buhr
	11	// Created On : Wed Dec 6 12:15:52 2017
	12	// Last Modified By : Peter A. Buhr
[3ac5fd8]	13	// Last Modified On : Sat Aug 17 13:59:15 2024
	14	// Update Count : 199
[764b4b2]	15	//
[90449e4]	16
[40002c5]	17	#include <fstream.hfa> // sin/sout
	18	#include <stdlib.hfa> // convert
[73abe95]	19	#include <thread.hfa>
[40002c5]	20	#include <math.hfa> // sqrt
[90449e4]	21	#include <string.h> // strcmp
	22
	23	thread Quicksort {
[f0322e20]	24	int * values; // communication variables
[90449e4]	25	int low, high, depth;
	26	};
	27
[f0322e20]	28	void ?{}( Quicksort & qs, int values[], int size, int depth ) {
[921cd82]	29	qs.[values, low, high, depth] = [values, 0, size, depth];
[90449e4]	30	} // Quicksort
	31
[f0322e20]	32	void main( Quicksort & qs ) { // thread starts here
[90449e4]	33	// nested routines: information hiding
	34
[f0322e20]	35	void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) {
[90449e4]	36	qs.values = values; qs.low = low; qs.high = high; qs.depth = depth;
	37	} // Quicksort
	38
[f0322e20]	39	void sort( int values[], int low, int high, int depth ) {
[90449e4]	40	int left, right; // index to left/right-hand side of the values
[f0322e20]	41	int pivot; // pivot value of values
	42	int swap; // temporary
[90449e4]	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;
[fdf4efb]	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
[90449e4]	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
[40002c5]	84	// convert(...) throws out_of_range or invalid_argument
	85	ExceptionDecl( cmd_error );
[edb6f79]	86
[90449e4]	87	int main( int argc, char * argv[] ) {
[40002c5]	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 ?
[90449e4]	96	choose ( argc ) {
	97	case 4:
[40002c5]	98	depth = convert( argv[3] ); // invalid integer ?
	99	if ( depth < 0 ) throw ExceptionInst( cmd_error );
[f0322e20]	100	fallthrough;
	101	case 3:
[40002c5]	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 );
[f0322e20]	106	} // choose
	107	} else { // sort file
	108	choose ( argc ) {
[40002c5]	109	case 4:
	110	depth = convert( argv[3] ); // invalid integer ?
	111	if ( depth < 0 ) throw ExceptionInst( cmd_error );
[90449e4]	112	fallthrough;
[40002c5]	113	case 3: case 2:
	114	if ( strcmp( argv[1], "d" ) != 0 ) {
	115	try { // open input file first as output creates file
	116	open( unsortedfile, argv[1] );
	117	} catch( open_failure * ) { // open failed ?
	118	serr \| "Error! Could not open unsorted input file \"" \| argv[1] \| "\"";
	119	throw ExceptionInst( cmd_error );
	120	} // try
[90449e4]	121	} // if
[40002c5]	122	if ( argc > 2 && strcmp( argv[2], "d" ) != 0 ) {
	123	try {
	124	open( sortedfile, argv[2] );
	125	} catch( open_failure * ) { // open failed ?
	126	serr \| "Error! Could not open sorted output file \"" \| argv[2] \| "\"";
	127	throw ExceptionInst( cmd_error );
	128	} // try
	129	} // if
	130	fallthrough;
	131	case 1: ; // defaults
	132	default: // wrong number of options
	133	throw ExceptionInst( cmd_error );
[90449e4]	134	} // choose
[f0322e20]	135	} // if
[40002c5]	136	} catch( exception_t * ) { // catch any
	137	exit \| "Usage: " \| argv[0] \| // TERMINATE
	138	" ( [ unsorted-file \| 'd' [ sorted-file \| 'd' [ depth (>= 0) ] ] ]"
	139	" \| -t size (>= 0) [ depth (>= 0) ] )";
	140	} // try
[90449e4]	141
	142	enum { ValuesPerLine = 22 }; // number of values printed per line
	143
[40002c5]	144	sortedfile \| nlOff; // turn off auto newline
	145
	146	if ( size == -1 ) { // generate output ?
[3ac5fd8]	147	int * values = 0p;
	148	try {
	149	for () {
	150	unsortedfile \| size; // read number of elements in the list
	151	values = aalloc( size ); // values to be sorted, too large to put on stack
	152	for ( counter; size ) { // read unsorted numbers
	153	unsortedfile \| values[counter];
	154	if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile \| nl \| " ";
	155	sortedfile \| values[counter];
	156	if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile \| ' ';
	157	} // for
	158	sortedfile \| nl;
	159
	160	if ( size > 0 ) { // values to sort ?
	161	Quicksort QS = { values, size - 1, 0 }; // sort values
	162	} // wait until sort tasks terminate
	163	for ( counter; size ) { // print sorted list
	164	if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile \| nl \| " ";
	165	sortedfile \| values[counter];
	166	if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile \| ' ';
	167	} // for
	168	sortedfile \| nl \| nl;
	169
	170	delete( values );
	171	values = 0p;
[90449e4]	172	} // for
[3ac5fd8]	173	} catch( end_of_file * ) {
[90449e4]	174	delete( values );
[3ac5fd8]	175	} // try
[40002c5]	176	} else { // timing
	177	PRNG prng;
[90449e4]	178	processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
[40002c5]	179	int * values = aalloc( size ); // values to be sorted, too large to put on stack
[90449e4]	180
[fdf4efb]	181	for ( counter; size ) { // generate unsorted numbers
[90449e4]	182	values[counter] = size - counter; // descending values
	183	} // for
[40002c5]	184
	185	unsigned int times = sqrt( size );
	186	for ( unsigned int counter = 0; counter < times; counter += 1 ) {
	187	swap( values[0], values[prng(size)] ); // randomize unsorted numbers
[fdf4efb]	188	} // for
[90449e4]	189	{
[f0322e20]	190	Quicksort QS = { values, size - 1, depth }; // sort values
[90449e4]	191	} // wait until sort tasks terminate
	192
[3aa1d22]	193	// for ( counter; size - 1 ) { // check sorting
[90449e4]	194	// if ( values[counter] > values[counter + 1] ) abort();
	195	// } // for
	196
	197	delete( values );
	198	} // if
	199	} // main
	200
[fdf4efb]	201	// 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
	202
[90449e4]	203	// Local Variables: //
	204	// tab-width: 4 //
[f8cd310]	205	// compile-command: "cfa quickSort.cfa" //
[90449e4]	206	// End: //

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

Download in other formats:

Original Format