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

Threading Statistics:
 Num_Initial_Thread_Servers : 10
 Num_Dynamically_Allocated_Thread_Servers : 0
 Max_Waiting_Threads (for server task): 6
 Max_Active : 21
 Max_Active_Masters : 17
 Max_Sub_Threads_Per_Master : 6
 Max_Waiting_For_Threads (to finish): 113

No comments:

Post a Comment