Index: tests/concurrency/examples/.expect/boundedBufferEXT.txt =================================================================== --- tests/concurrency/examples/.expect/boundedBufferEXT.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/.expect/boundedBufferEXT.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,1 @@ +total:400000 Index: tests/concurrency/examples/.expect/boundedBufferINT.txt =================================================================== --- tests/concurrency/examples/.expect/boundedBufferINT.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/.expect/boundedBufferINT.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,1 @@ +total:400000 Index: tests/concurrency/examples/.expect/datingService.txt =================================================================== --- tests/concurrency/examples/.expect/datingService.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/.expect/datingService.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,1 @@ +done Index: tests/concurrency/examples/.expect/gortn.txt =================================================================== --- tests/concurrency/examples/.expect/gortn.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/.expect/gortn.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,3 @@ +0 +2.5 +1 2 Index: tests/concurrency/examples/.expect/matrixSum.txt =================================================================== --- tests/concurrency/examples/.expect/matrixSum.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/.expect/matrixSum.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,1 @@ +10000 Index: tests/concurrency/examples/.expect/quickSort.txt =================================================================== --- tests/concurrency/examples/.expect/quickSort.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/.expect/quickSort.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,32 @@ +25 6 8 -5 99 100 101 7 +-5 6 7 8 25 99 100 101 + +1 -3 5 +-3 1 5 + + + + +9 8 7 6 5 4 3 2 1 0 +0 1 2 3 4 5 6 7 8 9 + +1 2 3 4 5 +1 2 3 4 5 + +5 4 3 2 1 +1 2 3 4 5 + +3 1 5 4 2 +1 2 3 4 5 + + + + +1 1 1 1 1 +1 1 1 1 1 + +29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 + 7 6 5 4 3 2 1 0 +0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 + 22 23 24 25 26 27 28 29 + Index: tests/concurrency/examples/.in/quickSort.txt =================================================================== --- tests/concurrency/examples/.in/quickSort.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/.in/quickSort.txt (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,10 @@ +8 25 6 8 -5 99 100 101 7 +3 1 -3 5 +0 +10 9 8 7 6 5 4 3 2 1 0 +5 1 2 3 4 5 +5 5 4 3 2 1 +5 3 1 5 4 2 +0 +5 1 1 1 1 1 +30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Index: tests/concurrency/examples/boundedBufferEXT.cfa =================================================================== --- tests/concurrency/examples/boundedBufferEXT.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/boundedBufferEXT.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,126 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// boundedBufferEXT.c -- +// +// Author : Peter A. Buhr +// Created On : Wed Apr 18 22:52:12 2018 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Jan 16 22:36:34 2020 +// Update Count : 15 +// + +#include // random +#include +#include +#include +#include // getpid + +//Duration default_preemption() { return 0; } + +enum { BufferSize = 50 }; + +forall( T ) { + monitor Buffer { + int front, back, count; + T elements[BufferSize]; + }; // Buffer + + void ?{}( Buffer(T) & buffer ) with( buffer ) { [front, back, count] = 0; } + + int query( Buffer(T) & buffer ) { return buffer.count; } // read-only, no mutual exclusion + + T remove( Buffer(T) & mutex buffer ); // forward + + void insert( Buffer(T) & mutex buffer, T elem ) with( buffer ) { + if ( count == BufferSize ) waitfor( remove : buffer ); + elements[back] = elem; + back = ( back + 1 ) % BufferSize; + count += 1; + } // insert + + T remove( Buffer(T) & mutex buffer ) with( buffer ) { + if ( count == 0 ) waitfor( insert : buffer ); + T elem = elements[front]; + front = ( front + 1 ) % BufferSize; + count -= 1; + return elem; + } // remove +} + +enum { Sentinel = -1 }; + +thread Producer { + Buffer(int) & buffer; + unsigned int N; +}; +void main( Producer & prod ) with( prod ) { + for ( i; 1 ~= N ) { + yield( random( 5 ) ); + insert( buffer, 1 ); + } // for +} +void ?{}( Producer & prod, Buffer(int) * buffer, int N ) { + &prod.buffer = buffer; + prod.N = N; +} + +thread Consumer { + Buffer(int) & buffer; + int & sum; // summation of producer values +}; +void main( Consumer & cons ) with( cons ) { + sum = 0; + for () { + yield( random( 5 ) ); + int item = remove( buffer ); + if ( item == Sentinel ) break; // sentinel ? + sum += item; + } // for +} +void ?{}( Consumer & cons, Buffer(int) * buffer, int & sum ) { + &cons.buffer = buffer; + &cons.sum = ∑ +} + +enum { Prods = 4, Cons = 5 }; +Producer * prods[Prods]; +Consumer * cons[Cons]; + +int main() { + Buffer(int) buffer; + int sums[Cons]; + int i; + processor p; + + //srandom( getpid() ); + srandom( 1003 ); + + for ( i; Cons ) { // create consumers + cons[i] = new( &buffer, sums[i] ); + } // for + for ( i; Prods ) { // create producers + prods[i] = new( &buffer, 100000 ); + } // for + + for ( i; Prods ) { // wait for producers to finish + delete( prods[i] ); + } // for + for ( i; Cons ) { // generate sentinal values to stop consumers + insert( buffer, Sentinel ); + } // for + int sum = 0; + for ( i; Cons ) { // wait for consumers to finish + delete( cons[i] ); + sum += sums[i]; + } // for + sout | "total:" | sum; +} + +// Local Variables: // +// tab-width: 4 // +// compile-command: "cfa boundedBufferEXT.cfa" // +// End: // Index: tests/concurrency/examples/boundedBufferINT.cfa =================================================================== --- tests/concurrency/examples/boundedBufferINT.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/boundedBufferINT.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,126 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// boundedBuffer.c -- +// +// Author : Peter A. Buhr +// Created On : Mon Oct 30 12:45:13 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Fri Jun 21 08:20:46 2019 +// Update Count : 90 +// + +#include // random +#include +#include +#include +#include // getpid + +//Duration default_preemption() { return 0; } + +enum { BufferSize = 50 }; + +forall( T ) { + monitor Buffer { + condition full, empty; + int front, back, count; + T elements[BufferSize]; + }; // Buffer + + void ?{}( Buffer(T) & buffer ) with( buffer ) { [front, back, count] = 0; } + + int query( Buffer(T) & buffer ) { return buffer.count; } // read-only, no mutual exclusion + + void insert( Buffer(T) & mutex buffer, T elem ) with( buffer ) { + if ( count == BufferSize ) wait( empty ); + elements[back] = elem; + back = ( back + 1 ) % BufferSize; + count += 1; + signal( full ); + } // insert + + T remove( Buffer(T) & mutex buffer ) with( buffer ) { + if ( count == 0 ) wait( full ); + T elem = elements[front]; + front = ( front + 1 ) % BufferSize; + count -= 1; + signal( empty ); + return elem; + } // remove +} + +enum { Sentinel = -1 }; + +thread Producer { + Buffer(int) & buffer; + unsigned int N; +}; +void main( Producer & prod ) with( prod ) { + for ( i; 1 ~= N ) { + yield( random( 5 ) ); + insert( buffer, 1 ); + } // for +} +void ?{}( Producer & prod, Buffer(int) * buffer, int N ) { + &prod.buffer = buffer; + prod.N = N; +} + +thread Consumer { + Buffer(int) & buffer; + int & sum; // summation of producer values +}; +void main( Consumer & cons ) with( cons ) { + sum = 0; + for () { + yield( random( 5 ) ); + int item = remove( buffer ); + if ( item == Sentinel ) break; // sentinel ? + sum += item; + } // for +} +void ?{}( Consumer & cons, Buffer(int) * buffer, int & sum ) { + &cons.buffer = buffer; + &cons.sum = ∑ +} + +int main() { + Buffer(int) buffer; + enum { Prods = 4, Cons = 5 }; + Producer * prods[Prods]; + Consumer * cons[Cons]; + int sums[Cons]; + int i; + processor p; + + //srandom( getpid() ); + srandom( 1003 ); + + for ( i; Cons ) { // create consumers + cons[i] = new( &buffer, sums[i] ); + } // for + for ( i; Prods ) { // create producers + prods[i] = new( &buffer, 100000 ); + } // for + + for ( i; Prods ) { // wait for producers to finish + delete( prods[i] ); + } // for + for ( i; Cons ) { // generate sentinal values to stop consumers + insert( buffer, Sentinel ); + } // for + int sum = 0; + for ( i; Cons ) { // wait for consumers to finish + delete( cons[i] ); + sum += sums[i]; + } // for + sout | "total:" | sum; +} + +// Local Variables: // +// tab-width: 4 // +// compile-command: "cfa boundedBufferINT.cfa" // +// End: // Index: tests/concurrency/examples/boundedBufferTHREAD.cfa =================================================================== --- tests/concurrency/examples/boundedBufferTHREAD.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/boundedBufferTHREAD.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,130 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2018 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// boundedBufferTHREAD.c -- +// +// Author : Peter A. Buhr +// Created On : Wed Apr 18 22:52:12 2018 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Jan 16 23:09:43 2020 +// Update Count : 25 +// + +#include // random +#include +#include +#include +#include // getpid + +//Duration default_preemption() { return 0; } + +enum { BufferSize = 50 }; + +//forall( otype T ) { + thread Buffer { + int front, back, count; + int elements[BufferSize]; + }; // Buffer + + void ?{}( Buffer & buffer ) with( buffer ) { [front, back, count] = 0; } + + int query( Buffer & buffer ) { return buffer.count; } // read-only, no mutual exclusion + + void insert( Buffer & mutex buffer, int elem ) with( buffer ) { + elements[back] = elem; + } // insert + + int remove( Buffer & mutex buffer ) with( buffer ) { + return elements[front]; + } // remove + + void main( Buffer & buffer ) with( buffer ) { + for () { + waitfor( ^?{} : buffer ) { + break; + } or when ( count != 20 ) waitfor( insert : buffer ) { + back = (back + 1) % 20; + count += 1; + } or when ( count != 0 ) waitfor( remove : buffer ) { + front = (front + 1) % 20; + count -= 1; + } // waitfor + } // for + } // main +//} + +enum { Sentinel = -1 }; + +thread Producer { + Buffer & buffer; + unsigned int N; +}; +void main( Producer & prod ) with( prod ) { + for ( i; 1 ~= N ) { + yield( random( 5 ) ); + insert( buffer, 1 ); + } // for +} +void ?{}( Producer & prod, Buffer * buffer, int N ) { + &prod.buffer = buffer; + prod.N = N; +} + +thread Consumer { + Buffer & buffer; + int & sum; // summation of producer values +}; +void main( Consumer & cons ) with( cons ) { + sum = 0; + for () { + yield( random( 5 ) ); + int item = remove( buffer ); + if ( item == Sentinel ) break; // sentinel ? + sum += item; + } // for +} +void ?{}( Consumer & cons, Buffer * buffer, int & sum ) { + &cons.buffer = buffer; + &cons.sum = ∑ +} + +int main() { + Buffer buffer; + enum { Prods = 4, Cons = 5 }; + Producer * prods[Prods]; + Consumer * cons[Cons]; + int sums[Cons]; + int i; + processor p; + + //srandom( getpid() ); + srandom( 1003 ); + + for ( i; Cons ) { // create consumers + cons[i] = new( &buffer, sums[i] ); + } // for + for ( i; Prods ) { // create producers + prods[i] = new( &buffer, 100000 ); + } // for + + for ( i; Prods ) { // wait for producers to finish + delete( prods[i] ); + } // for + for ( i; Cons ) { // generate sentinal values to stop consumers + insert( buffer, Sentinel ); + } // for + int sum = 0; + for ( i; Cons ) { // wait for consumers to finish + delete( cons[i] ); + sum += sums[i]; + } // for + sout | "total:" | sum; +} + +// Local Variables: // +// tab-width: 4 // +// compile-command: "cfa boundedBufferTHREAD.cfa" // +// End: // Index: tests/concurrency/examples/datingService.cfa =================================================================== --- tests/concurrency/examples/datingService.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/datingService.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,117 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// datingService.c -- +// +// Author : Peter A. Buhr +// Created On : Mon Oct 30 12:56:20 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sun Sep 27 15:42:25 2020 +// Update Count : 40 +// + +#include // random +#include +#include +#include +#include // getpid + +enum { CompCodes = 20 }; // number of compatibility codes + +monitor DatingService { + condition Girls[CompCodes], Boys[CompCodes]; + unsigned int GirlPhoneNo, BoyPhoneNo; +}; // DatingService + +unsigned int girl( DatingService & mutex ds, unsigned int PhoneNo, unsigned int ccode ) with( ds ) { + if ( is_empty( Boys[ccode] ) ) { // no compatible boy ? + wait( Girls[ccode] ); // wait for boy + GirlPhoneNo = PhoneNo; // make phone number available + } else { + GirlPhoneNo = PhoneNo; // make phone number available + signal_block( Boys[ccode] ); // restart boy to set phone number + } // if + // sout | "Girl:" | PhoneNo | "is dating Boy at" | BoyPhoneNo | "with ccode" | ccode; + return BoyPhoneNo; +} // DatingService girl + +unsigned int boy( DatingService & mutex ds, unsigned int PhoneNo, unsigned int ccode ) with( ds ) { + if ( is_empty( Girls[ccode] ) ) { // no compatible girl ? + wait( Boys[ccode] ); // wait for girl + BoyPhoneNo = PhoneNo; // make phone number available + } else { + BoyPhoneNo = PhoneNo; // make phone number available + signal_block( Girls[ccode] ); // restart girl to set phone number + } // if + // sout | " Boy:" | PhoneNo | "is dating Girl" | GirlPhoneNo | "with ccode" | ccode; + return GirlPhoneNo; +} // DatingService boy + +unsigned int girlck[CompCodes]; +unsigned int boyck[CompCodes]; + +thread Girl { + DatingService & TheExchange; + unsigned int id, ccode; +}; // Girl + +void main( Girl & g ) with( g ) { + yield( random( 100 ) ); // don't all start at the same time + unsigned int partner = girl( TheExchange, id, ccode ); + girlck[id] = partner; +} // Girl main + +void ?{}( Girl & g, DatingService * TheExchange, unsigned int id, unsigned int ccode ) { + &g.TheExchange = TheExchange; + g.id = id; + g.ccode = ccode; +} // Girl ?{} + +thread Boy { + DatingService & TheExchange; + unsigned int id, ccode; +}; // Boy + +void main( Boy & b ) with( b ) { + yield( random( 100 ) ); // don't all start at the same time + unsigned int partner = boy( TheExchange, id, ccode ); + boyck[id] = partner; +} // Boy main + +void ?{}( Boy & b, DatingService * TheExchange, unsigned int id, unsigned int ccode ) { + &b.TheExchange = TheExchange; + b.id = id; + b.ccode = ccode; +} // Boy ?{} + +int main() { + DatingService TheExchange; + Girl * girls[CompCodes]; + Boy * boys[CompCodes]; + + srandom( /*getpid()*/ 103 ); + + for ( i; (unsigned int)CompCodes ) { + girls[i] = new( &TheExchange, i, i ); // TheExchange constructor needs unsigned int + boys[i] = new( &TheExchange, i, CompCodes - ( i + 1 ) ); + } // for + + for ( i; CompCodes ) { + delete( boys[i] ); + delete( girls[i] ); + } // for + + for ( i; CompCodes ) { + if ( girlck[ boyck[i] ] != boyck[ girlck[i] ] ) abort(); + } // for + + printf( "done\n" ); // non-empty .expect file +} // main + +// Local Variables: // +// tab-width: 4 // +// compile-command: "cfa datingService.cfa" // +// End: // Index: tests/concurrency/examples/gortn.cfa =================================================================== --- tests/concurrency/examples/gortn.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/gortn.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,43 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2019 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// gortn.cfa -- compare waitfor and go channels +// +// Author : Peter A. Buhr +// Created On : Wed Feb 20 08:02:37 2019 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Jan 16 22:43:40 2020 +// Update Count : 5 +// + +#include +#include + +struct Msg { int i, j; }; +thread GoRtn { int i; float f; Msg m; }; +void ^?{}( GoRtn & mutex ) {} +void mem1( GoRtn & mutex gortn, int i ) { gortn.i = i; } +void mem2( GoRtn & mutex gortn, float f ) { gortn.f = f; } +void mem3( GoRtn & mutex gortn, Msg m ) { gortn.m = m; } + +void main( GoRtn & gortn ) with( gortn ) { + for () { + waitfor( mem1 : gortn ) sout | i; + or waitfor( mem2 : gortn ) sout | f; + or waitfor( mem3 : gortn ) sout | m.i | m.j; + or waitfor( ^?{} : gortn ) break; + } +} +int main() { + GoRtn gortn; // start thread + mem1( gortn, 0 ); + mem2( gortn, 2.5 ); + mem3( gortn, (Msg){ 1, 2} ); +} // wait for completion + +// Local Variables: // +// tab-width: 4 // +// End: // Index: tests/concurrency/examples/matrixSum.cfa =================================================================== --- tests/concurrency/examples/matrixSum.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/matrixSum.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,61 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// matrixSum.cfa -- +// +// Author : Peter A. Buhr +// Created On : Mon Oct 9 08:29:28 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Wed Feb 20 08:37:53 2019 +// Update Count : 16 +// + +#include +#include +#include + +thread Adder { + int * row, cols, & subtotal; // communication +}; + +void ?{}( Adder & adder, int row[], int cols, int & subtotal ) { + adder.[ row, cols ] = [ row, cols ]; // expression disallowed in multi-member access + &adder.subtotal = &subtotal; +} + +void main( Adder & adder ) with( adder ) { // thread starts here + subtotal = 0; + for ( c; cols ) { + subtotal += row[c]; + } // for +} + +int main() { + /* const */ int rows = 10, cols = 1000; + int matrix[rows][cols], subtotals[rows], total = 0; + processor p; // add kernel thread + + for ( r; rows ) { + for ( c; cols ) { + matrix[r][c] = 1; + } // for + } // for + Adder * adders[rows]; + for ( r; rows ) { // start threads to sum rows + adders[r] = &(*malloc()){ matrix[r], cols, subtotals[r] }; +// adders[r] = new( matrix[r], cols, &subtotals[r] ); + } // for + for ( r; rows ) { // wait for threads to finish + delete( adders[r] ); + total += subtotals[r]; // total subtotals + } // for + sout | total; +} + +// Local Variables: // +// tab-width: 4 // +// compile-command: "cfa matrixSum.cfa" // +// End: // Index: tests/concurrency/examples/multiSort.cfa =================================================================== --- tests/concurrency/examples/multiSort.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/multiSort.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,121 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2022 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// multiSort.c -- compute sort single array multiple times +// make sure sorting works, thread don't screw up +// and trampolines work on thread stacks +// +// Author : Peter A. Buhr +// Created On : Tue 05 24 11:34:23 2022 +// Last Modified By : +// Last Modified On : +// Update Count : +// + +#include +#include +#include +#include +#include + +forall(T) { + struct MyVec2 { + T val1; + T val2; + }; + + forall(| Equality( T )) + int ?!=?( MyVec2(T) lhs, MyVec2(T) rhs ) { return lhs.val1 != rhs.val1 || lhs.val2 != rhs.val2; } + + forall(| Relational(T)) { + static inline int ? rhs.val1) return false; + if(lhs.val2 < rhs.val2) return true; + if(lhs.val2 > rhs.val2) return false; + return false; + } + } + + forall(| { T random( void ); }) + MyVec2(T) random( void ) { + MyVec2(T) r; + r.val1 = random(); + r.val2 = random(); + return r; + } +} + + + +const unsigned nthreads = 7; +const unsigned nvecs = 313; +barrier bar = { nthreads + 1 }; +const MyVec2(long int) * original; + +thread Sorter { + MyVec2(long int) * copy; +}; + +void ^?{}( Sorter & mutex this ) { + free(this.copy); +} + +// Make this a polymorphic call to prevent thunks from being hosted +forall( T | Relational(T) | sized(MyVec2(T)) ) +void block_sort( MyVec2(T) * vals, size_t dim ) __attribute__((noinline)) { + MyVec2(T) dummy = vals[0]; + block( bar ); + + qsort(vals, dim); +} + + +void main( Sorter & this ) { + this.copy = aalloc(nvecs); + for(i; nvecs) { + this.copy[i] = original[i]; + } + + block_sort(this.copy, nvecs); +} + +int main() { + sout | "Generating"; + MyVec2(long int) * local = aalloc( nvecs ); + for(i; nvecs) { + local[i] = random(); + } + + original = local; + + sout | "Launching"; + + processor p; { + Sorter sorters[nthreads]; + + block( bar ); + + sout | "Sorting"; + + qsort(local, nvecs); + + sout | "Checking"; + + for(i; nthreads) { + const MyVec2(long int) * copy = join( sorters[i] ).copy; + for(j; nvecs) { + if(copy[j] != original[j]) { + sout | "Error at thread" | i | ", index" | j | ": data doesn't match!"; + } + } + } + } + + free(local); + + sout | "Done"; +} Index: tests/concurrency/examples/quickSort.cfa =================================================================== --- tests/concurrency/examples/quickSort.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/quickSort.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,189 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// quickSort.c -- In-place concurrent quick-sort: threads are created to partition to a specific depth, then sequential +// recursive-calls are use to sort each partition. +// +// Author : Peter A. Buhr +// Created On : Wed Dec 6 12:15:52 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Wed Feb 12 18:24:47 2020 +// Update Count : 177 +// + +#include +#include +#include +#include +#include // strcmp + +thread Quicksort { + int * values; // communication variables + int low, high, depth; +}; + +void ?{}( Quicksort & qs, int values[], int size, int depth ) { + qs.[values, low, high, depth] = [values, 0, size, depth]; +} // Quicksort + +void main( Quicksort & qs ) { // thread starts here + // nested routines: information hiding + + void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) { + qs.values = values; qs.low = low; qs.high = high; qs.depth = depth; + } // Quicksort + + void sort( int values[], int low, int high, int depth ) { + int left, right; // index to left/right-hand side of the values + int pivot; // pivot value of values + int swap; // temporary + + //verify(); // check for stack overflow due to recursion + + // partition while 2 or more elements in the array + if ( low < high ) { + pivot = values[low + ( high - low ) / 2]; + left = low; + right = high; + + // partition: move values less < pivot before the pivot and values > pivot after the pivot + do { + while ( values[left] < pivot ) left += 1; // changed values[left] < pivot + while ( pivot < values[right] ) right -= 1; + if ( left <= right ) { + swap = values[left]; // interchange values + values[left] = values[right]; + values[right] = swap; + left += 1; + right -= 1; + } // if + } while ( left <= right ); + + // restrict number of tasks to slightly greater than number of processors + if ( depth > 0 ) { + depth -= 1; + Quicksort lqs = { values, low, right, depth }; // concurrently sort lower half + Quicksort rqs = { values, left, high, depth }; // concurrently sort upper half + // Quicksort lqs = { values, low, right, depth }; // concurrently sort lower half + // sort( values, left, high, depth ); // concurrently sort upper half + } else { + sort( values, low, right, 0 ); // sequentially sort lower half + sort( values, left, high, 0 ); // sequentially sort upper half + } // if + } // if + } // sort + + with( qs ) { + sort( values, low, high, depth ); + } // with +} // main + + +bool convert( int & val, const char * nptr ) { // convert C string to integer + char * eptr; + int temp = strto( nptr, &eptr, 10 ); // do not change val on false + // true => entire string valid with no extra characters + return *nptr != '\0' && *eptr == '\0' ? val = temp, true : false; +} // convert + +void usage( char * argv[] ) { + sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )"; + exit( EXIT_FAILURE ); // TERMINATE! +} // usage + + +int main( int argc, char * argv[] ) { + ifstream & unsortedfile = sin; + ofstream & sortedfile = sout; // default value + int depth = 0, size; + + if ( argc != 1 ) { // do not use defaults + if ( argc < 2 || argc > 4 ) usage( argv ); // wrong number of options + if ( strcmp( argv[1], "-t" ) == 0 ) { // timing ? + &unsortedfile = (ifstream *)0; // no input + choose ( argc ) { + case 4: + if ( ! convert( depth, argv[3] ) || depth < 0 ) usage( argv ); + fallthrough; + case 3: + if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv ); + } // choose + } else { // sort file + choose ( argc ) { + case 3: + &sortedfile = new( (const char *)argv[2] ); // open the output file + if ( fail( sortedfile ) ) { + serr | "Error! Could not open sorted output file \"" | argv[2] | "\""; + usage( argv ); + } // if + fallthrough; + case 2: + &unsortedfile = new( (const char *)argv[1] ); // open the input file + if ( fail( unsortedfile ) ) { + serr | "Error! Could not open unsorted input file \"" | argv[1] | "\""; + usage( argv ); + } // if + } // choose + } // if + } // if + sortedfile | nlOff; // turn off auto newline + + enum { ValuesPerLine = 22 }; // number of values printed per line + + if ( &unsortedfile ) { // generate output ? + for () { + unsortedfile | size; // read number of elements in the list + if ( eof( unsortedfile ) ) break; + int * values = alloc( size ); // values to be sorted, too large to put on stack + for ( counter; size ) { // read unsorted numbers + unsortedfile | values[counter]; + if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " "; + sortedfile | values[counter]; + if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' '; + } // for + sortedfile | nl; + if ( size > 0 ) { // values to sort ? + Quicksort QS = { values, size - 1, 0 }; // sort values + } // wait until sort tasks terminate + for ( counter; size ) { // print sorted list + if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " "; + sortedfile | values[counter]; + if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' '; + } // for + sortedfile | nl | nl; + + delete( values ); + } // for + if ( &unsortedfile != &sin ) delete( &unsortedfile ); // close input/output files + if ( &sortedfile != &sout ) delete( &sortedfile ); + } else { + processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads + + int * values = alloc( size ); // values to be sorted, too large to put on stack + for ( counter; size ) { // generate unsorted numbers + values[counter] = size - counter; // descending values + } // for + for ( i; 200 ) { // random shuffle a few values + swap( values[rand() % size], values[rand() % size] ); + } // for + { + Quicksort QS = { values, size - 1, depth }; // sort values + } // wait until sort tasks terminate + + // for ( counter; size - 1 ) { // check sorting + // if ( values[counter] > values[counter + 1] ) abort(); + // } // for + + delete( values ); + } // if +} // main + +// 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 + +// Local Variables: // +// tab-width: 4 // +// compile-command: "cfa quickSort.cfa" // +// End: // Index: tests/concurrency/examples/quickSort.generic.cfa =================================================================== --- tests/concurrency/examples/quickSort.generic.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) +++ tests/concurrency/examples/quickSort.generic.cfa (revision c26bea2aa0f87b4b070349c5801adc32fb0d4cf9) @@ -0,0 +1,186 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// quickSort.c -- In-place concurrent quick-sort: threads are created to partition to a specific depth, then sequential +// recursive-calls are use to sort each partition. +// +// Author : Peter A. Buhr +// Created On : Wed Dec 6 12:15:52 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Fri Jun 21 08:28:20 2019 +// Update Count : 149 +// + +#include +#include +#include +#include +#include // strcmp + +forall( T | { int ? pivot after the pivot + do { + while ( values[left] < pivot ) left += 1; // changed values[left] < pivot + while ( pivot < values[right] ) right -= 1; + if ( left <= right ) { + swap = values[left]; // interchange values + values[left] = values[right]; + values[right] = swap; + left += 1; + right -= 1; + } // if + } while ( left <= right ); + + // restrict number of tasks to slightly greater than number of processors + if ( depth > 0 ) { + depth -= 1; + Quicksort(T) rqs = { values, low, right, depth }; // concurrently sort upper half + //Quicksort lqs( values, left, high, depth ); // concurrently sort lower half + sort( values, left, high, depth ); // concurrently sort lower half + } else { + sort( values, low, right, 0 ); // sequentially sort lower half + sort( values, left, high, 0 ); // sequentially sort upper half + } // if + } // if + } // sort + + with( qs ) { + sort( values, low, high, depth ); + } // with + } // main +} + +bool convert( int & val, const char * nptr ) { // convert C string to integer + char * eptr; + int temp = strto( nptr, &eptr, 10 ); // do not change val on false + // true => entire string valid with no extra characters + return *nptr != '\0' && *eptr == '\0' ? val = temp, true : false; +} // convert + +void usage( char * argv[] ) { + sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )"; + exit( EXIT_FAILURE ); // TERMINATE! +} // usage + + +#define ELEMTYPE int + +int main( int argc, char * argv[] ) { + ifstream & unsortedfile = sin; + ofstream & sortedfile = sout; // default value + int depth = 0, size; + + if ( argc != 1 ) { // do not use defaults + if ( argc < 2 || argc > 4 ) usage( argv ); // wrong number of options + if ( strcmp( argv[1], "-t" ) == 0 ) { // timing ? + &unsortedfile = (ifstream *)0; // no input + choose ( argc ) { + case 4: + if ( ! convert( depth, argv[3] ) || depth < 0 ) usage( argv ); + fallthrough; + case 3: + if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv ); + } // choose + } else { // sort file + choose ( argc ) { + case 3: + &sortedfile = new( (const char *)argv[2] ); // open the output file + if ( fail( sortedfile ) ) { + serr | "Error! Could not open sorted output file \"" | argv[2] | "\""; + usage( argv ); + } // if + fallthrough; + case 2: + &unsortedfile = new( (const char *)argv[1] ); // open the input file + if ( fail( unsortedfile ) ) { + serr | "Error! Could not open unsorted input file \"" | argv[1] | "\""; + usage( argv ); + } // if + } // choose + } // if + } // if + sortedfile | nlOff; // turn off auto newline + + enum { ValuesPerLine = 22 }; // number of values printed per line + + if ( &unsortedfile ) { // generate output ? + for () { + unsortedfile | size; // read number of elements in the list + if ( eof( unsortedfile ) ) break; + ELEMTYPE * values = alloc( size ); // values to be sorted, too large to put on stack + for ( counter; size ) { // read unsorted numbers + unsortedfile | values[counter]; + if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " "; + sortedfile | values[counter]; + if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' '; + } // for + sortedfile | nl; + if ( size > 0 ) { // values to sort ? + Quicksort(ELEMTYPE) QS = { values, size - 1, 0 }; // sort values + } // wait until sort tasks terminate + for ( counter; size ) { // print sorted list + if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " "; + sortedfile | values[counter]; + if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' '; + } // for + sortedfile | nl | nl; + + delete( values ); + } // for + if ( &unsortedfile != &sin ) delete( &unsortedfile ); // close input/output files + if ( &sortedfile != &sout ) delete( &sortedfile ); + } else { + processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads + + ELEMTYPE * values = alloc( size ); // values to be sorted, too large to put on stack + for ( counter; size ) { // generate unsorted numbers + values[counter] = size - counter; // descending values + } // for + { + Quicksort(ELEMTYPE) QS = { values, size - 1, depth }; // sort values + } // wait until sort tasks terminate + + // for ( counter; size - 1 ) { // check sorting + // if ( values[counter] > values[counter + 1] ) abort(); + // } // for + + delete( values ); + } // if +} // main + +// Local Variables: // +// tab-width: 4 // +// compile-command: "cfa quickSort.generic.cfa" // +// End: //