Thursday, September 8, 2011

Another ParaSail example that compiles and runs

Here is a version of parallel Quicksort that now compiles and runs through the ParaSail compiler. This is parallel but non-recursive. It uses a parallel pair of continue loop statements rather than recursion.  It uses "slicing" on the array.  A[..] takes an array and returns a "slice" of the array that contains all elements of the array.  After partitioning the array, the code splits into two threads and then continues with a left "slice" and a right "slice" of the array.  The "<=>" operator performs a swap operation.

There is a simple Test_Sort test function at the bottom.  It uses a very simple random number generator to populate an array and then sort it (twice).

At the very bottom we have the result of running the program.
```interface Sorting<Array_Type is Indexable<Comparable<>, Countable<>>> is
func Quicksort(var A : Array_Type);
// Sort Arr according to the sorting op "<" which returns
// True if Left must appear before Right in the sorted order.
// Before returns False if Left = Right.
end interface Sorting;

class Sorting is
exports
func Quicksort(var A : Array_Type) is
// Handle short arrays directly.  Partition longer arrays.
for Arr : Slice<Array_Type> => A[..] while Length(Arr) > 1 loop
if Length(Arr) == 2 then
if Arr[Arr.Last] < Arr[Arr.First] then
// Swap elements
Arr[Arr.First] <=> Arr[Arr.Last];
end if;
else
// Partition array
const Mid := Arr[Arr.First + Length(Arr)/2];
var Left := Arr.First;
var Right := Arr.Last;
until Left > Right loop
var New_Left := Right+1;
var New_Right := Left-1;
block
// Find item in left half to swap
for I in Left .. Right forward loop
if not (Arr[I] < Mid) then
// Found an item that can go into right partitition
New_Left := I;
if Mid < Arr[I] then
// Found an item that *must* go into right part
exit loop;
end if;
end if;
end loop;
||
// Find item in right half to swap
for J in Left .. Right reverse loop
if not (Mid < Arr[J]) then
// Found an item that can go into left partitition
New_Right := J;
if Arr[J] < Mid then
// Found an item that *must* go into left part
exit loop;
end if;
end if;
end loop;
end block;

if New_Left > New_Right then
// Nothing more to swap
// Exit loop and recurse on two partitions
Left := New_Left;
Right := New_Right;
exit loop;
end if;

// Swap items
Arr[New_Left] <=> Arr[New_Right];

// continue looking for items to swap
Left := New_Left + 1;
Right := New_Right - 1;
end loop;

// At this point, "Right" is right end of left partition
// and "Left" is left end of right partition
// and the partitions don't overlap
// and neither is the whole array
// and everything in the left partition can precede Mid
// and everything in the right partition can follow Mid
// and everything between the partitions is equal to Mid.
{Left > Right;
Right < Arr.Last;
Left > Arr.First;
(for all I in Arr.First .. Right => not (Mid < Arr[I]));
(for all J in Left .. Arr.Last => not (Arr[J] < Mid));
(for all K in Right+1 .. Left-1 =>
not (Mid < Arr[K]) and not (Arr[K] < Mid))}

then
// continue with two halves in parallel
continue loop with Arr[Arr.First .. Right];
||
continue loop with Arr[Left .. Arr.Last];
end if;
end loop;
end func Quicksort;
end class Sorting;

func Random(var Seed : Univ_Integer; Mult, Mod : Univ_Integer)
-> Univ_Integer is
Seed := Seed * Mult mod Mod;
return Seed;
end func Random;

func Test_Sort(Len : Univ_Integer) is
// For Random
const Mult := 7**5;
const Mod := 2**31 - 1;
var Seed := Len;
Println("Seed = " | Seed | ", Mult = " | Mult | ", Mod = " | Mod);

type My_Sorter is Sorting<Vector<Univ_Integer>>;
var Vec : Vector<Univ_Integer> := [];

for I in 1..Len loop
Vec |= Random(Seed, Mult, Mod) mod 100;
end loop;

var Vec2 := Vec;

Println("Before sort, Vec = ");
for I in 1 .. Length(Vec) forward loop
Print(" " | Vec[I]);
if I < Length(Vec) then
Print(",");
end if;
end loop;
Print("\n");

My_Sorter::Quicksort(Vec);

Println("After sort, Vec = ");
for I in 1 .. Length(Vec) forward loop
Print(" " | Vec[I]);
if I < Length(Vec) then
Print(",");
end if;
end loop;
Print("\n");

My_Sorter::Quicksort(Vec2);

Println("After 2nd sort, Vec2 = ");
for I in 1 .. Length(Vec2) forward loop
Print(" " | Vec2[I]);
if I < Length(Vec2) then
Print(",");
end if;
end loop;
Print("\n");

end func Test_Sort;
```
Here is the result of compiling and running the program. "aaa.psi" contains the standard ParaSail library of modules. "qsort6.psl" is given above. We are using the compiler interactively here, so we can run stand-alone ParaSail operations. It also can run non-interactively, by giving "-command <operation> <param1> ..." after the list of source file names on the command line. When in interactive mode, it dumps out some virtual machine threading statistics after the user "quit"s. These are at the very bottom. In this example, we have 21 threads active simultaneously at one point during execution.
```% pslc aaa.psi qsort6.psl
Parsing aaa.psi
Parsing qsort6.psl
---- Beginning semantic analysis ----
52 trees in library.
Done with First pass.
Done with Second pass.
Done with Pre codegen pass.
Done with Code gen.
Command to execute: Test_Sort 20

Seed = 20, Mult = 16807, Mod = 2147483647
Before sort, Vec =
40, 86, 55, 37, 30, 52, 80, 49, 49, 34, 71, 30, 88, 40, 93, 90, 29, 80, 71, 93
After sort, Vec =
29, 30, 30, 34, 37, 40, 40, 49, 49, 52, 55, 71, 71, 80, 80, 86, 88, 90, 93, 93
After 2nd sort, Vec2 =
29, 30, 30, 34, 37, 40, 40, 49, 49, 52, 55, 71, 71, 80, 80, 86, 88, 90, 93, 93
Command to execute: quit