Parallel Merge Sort

Parallel Merge Sort

[R. Stegers]

I want to create a generic package which can sort an array with any type of
elements. The index is of the integer type. It is also required that the
merge sort is performed in parallel. I'm a C/C++-programmer with very
limited Ada experience. I think I got the idea of tasks/rendevous right. I
run into some problems here:

 - How can I dynamicaly allocate a temporary array (for which i don't know
the size in advance?) It seems inpossible to me.
 - How to create tasks from within a task: The subTask1 en subTask2
declarations generate errors: "Task type cannot be used as type mark within
its own body"

I hope someone can give me a hint. The code is below.

Thanks in advance,

Ruud



So far I created this definition and body (with some pseudo code):

*** SORT_PACKAGE.ADS ***
generic
  type element_type is private;
  with function "<=" (element1, element2 : element_type) return Boolean;
package SORT_PACKAGE is

  type element_array is array(integer range <>) of element_type;

  procedure Sort(InArray : in out element_array);

  task type mergeSortTask is
    entry doSort(InArray : in out element_array);
    entry awaitResult;
  end mergeSortTask;

end SORT_PACKAGE;


*** SORT_PACKAGE.ADB ***
with SORT_PACKAGE;

package body SORT_PACKAGE is

  procedure Sort(InArray : in out element_array) is
     baseTask : MergSortTask;
  begin
     baseTask.doSort(InArray);
  end Sort;

  task body MergeSortTask is
    subTask1 : MergeSortTask;
    subTask2 : MergeSortTask;
  begin

    accept doSort(InArray : in out element_array) do
      ** How to get the InArray to be used outside the doSort?? **
      -- Synchronize with the caller but return control
    end doSort;

    if (**array size > 1 element**)
      -- Actually sort the array here
      subTask1.doSort(**<1st half>**);
      subTask2.doSort(**<2nd half>**);

      -- Wait till both sub-task have finished sorting
      subTask1.awaitResult;
      subTask2.awaitResult;

      -- Merge both halfs here
      **...**
    endif

    accept awaitResult do
      -- When this point is reached, the work is done
    end awaitResult;

  end mergeSortTask;

end SORT_PACKAGE;

Re: Parallel Merge Sort

[Pat Rogers]

"R. Stegers" <rstegers@cs.vu.nl> wrote in message
news:a4juvf$67t$1@star.cs.vu.nl...
> I want to create a generic package which can sort an array with any type of
> elements. The index is of the integer type. It is also required that the
> merge sort is performed in parallel. I'm a C/C++-programmer with very
> limited Ada experience. I think I got the idea of tasks/rendevous right. I
> run into some problems here:
>
>  - How can I dynamicaly allocate a temporary array (for which i don't know
> the size in advance?) It seems inpossible to me.
>  - How to create tasks from within a task: The subTask1 en subTask2
> declarations generate errors: "Task type cannot be used as type mark within
> its own body"
>
> I hope someone can give me a hint. The code is below.

Hint: there is a well-known book on concurrent programming in Ada (:-) that
shows how to do this.....

Re: Parallel Merge Sort

[Adrian Hoe]

Pat Rogers wrote:
> 
> "R. Stegers" <rstegers@cs.vu.nl> wrote in message
> news:a4juvf$67t$1@star.cs.vu.nl...
> > I want to create a generic package which can sort an array with any type of
> > elements. The index is of the integer type. It is also required that the
> > merge sort is performed in parallel. I'm a C/C++-programmer with very
> > limited Ada experience. I think I got the idea of tasks/rendevous right. I
> > run into some problems here:
> >
> >  - How can I dynamicaly allocate a temporary array (for which i don't know
> > the size in advance?) It seems inpossible to me.
> >  - How to create tasks from within a task: The subTask1 en subTask2
> > declarations generate errors: "Task type cannot be used as type mark within
> > its own body"
> >
> > I hope someone can give me a hint. The code is below.
> 
> Hint: there is a well-known book on concurrent programming in Ada (:-) that
> shows how to do this.....


Alan Burns and Andy Welling's Concurrency in Ada, 1995, Cambridge
University Press.

This is an excellent book for concurrent programming in Ada.
-- 
                              -- Adrian Hoe
                              -- http://greenlime.com/users/adrian.hoe

Re: Parallel Merge Sort

[Adrian Hoe]

Pat Rogers wrote:
> 
> "R. Stegers" <rstegers@cs.vu.nl> wrote in message
> news:a4juvf$67t$1@star.cs.vu.nl...
> > I want to create a generic package which can sort an array with any type of
> > elements. The index is of the integer type. It is also required that the
> > merge sort is performed in parallel. I'm a C/C++-programmer with very
> > limited Ada experience. I think I got the idea of tasks/rendevous right. I
> > run into some problems here:
> >
> >  - How can I dynamicaly allocate a temporary array (for which i don't know
> > the size in advance?) It seems inpossible to me.
> >  - How to create tasks from within a task: The subTask1 en subTask2
> > declarations generate errors: "Task type cannot be used as type mark within
> > its own body"
> >
> > I hope someone can give me a hint. The code is below.
> 
> Hint: there is a well-known book on concurrent programming in Ada (:-) that
> shows how to do this.....

Alan Burns and Andy Welling's Concurrency in Ada, 1995, Cambridge
University Press.

This is an excellent book for concurrent programming in Ada.
-- 
                              -- Adrian Hoe
                              -- http://greenlime.com/users/adrian.hoe

Re: Parallel Merge Sort

[tmoran]

>  - How can I dynamicaly allocate a temporary array (for which i don't know
> the size in advance?) It seems inpossible to me.
>  - How to create tasks from within a task: The subTask1 en subTask2
> declarations generate errors: "Task type cannot be used as type mark within
> its own body"

  Consider what would happen if you created an object of type MergeSortTask
where:
>  task body MergeSortTask is
>    subTask1 : MergeSortTask;
>    subTask2 : MergeSortTask;
>  begin
>  ...
  That object will require creation of two more MergeSortTasks, each of
which will create two more ..., all before you've even found out if there's
any data to sort.  So you will have to create the subtasks dynamically.
   type Pointer_To_MergeSortTask is access MergeSortTask;
   task body MergeSortTask is
     subTask1 : Pointer_To_MergeSortTask;
     subTask2 : Pointer_To_MergeSortTask;
   begin
   ...
    if (**array size > 1 element**)
      -- Actually sort the array here
      subTask1 := new MergeSortTask;
      subTask2 := new MergeSortTask;
      subTask1.doSort(**<1st half>**);
      subTask2.doSort(**<2nd half>**);

      -- Wait till both sub-task have finished sorting
      subTask1.awaitResult;
      subTask2.awaitResult;


>   accept doSort(InArray : in out element_array) do
>     ** How to get the InArray to be used outside the doSort?? **
>     -- Synchronize with the caller but return control
>   end doSort;
  You'll have to copy InArray, since you only have access to it for
the (short) time you are between the "accept" and the "end doSort".
You can't create the copy on the stack "Copy : element_array := InArray;"
since of course the stack is cut back at "end doSort", so you'll have
to create the copy on the heap and manually free it.
  type Pointer_To_Element_Array is access Element_Array;
  ...
  -- then inside the task body:
  My_Data : Pointer_To_Element_Array;
  ...
  accept doSort(InArray : in out element_array) do
    -- Create a local copy of InArray on the heap
    My_Data := new Element_Array'(InArray);
    -- Synchronize with the caller but return control
  end doSort;

But this is not what you want, of course, since it does not sort
InArray, but only a copy of it.  In particular, the code
     baseTask.doSort(InArray);
won't sort InArray - it will merely start up, and not wait for, a
set of tasks that will sort a copy of InArray.  One possible solution
is to make
    entry doSort     (InArray : in     element_array);
    entry awaitResult(InArray :    out element_array);
and return the sorted result at awaitResult time.

Re: Parallel Merge Sort

[R. Stegers]

Thanks a lot, this is exactly what I needed to know!

<tmoran@acm.org> schreef in bericht
news:0sgb8.36$hk2.28284109@newssvr14.news.prodigy.com...
> >  - How can I dynamicaly allocate a temporary array (for which i don't
know
> > the size in advance?) It seems inpossible to me.
> >  - How to create tasks from within a task: The subTask1 en subTask2
> > declarations generate errors: "Task type cannot be used as type mark
within
> > its own body"
>
>   Consider what would happen if you created an object of type
MergeSortTask
> where:
> >  task body MergeSortTask is
> >    subTask1 : MergeSortTask;
> >    subTask2 : MergeSortTask;
> >  begin
> >  ...
>   That object will require creation of two more MergeSortTasks, each of
> which will create two more ..., all before you've even found out if
there's
> any data to sort.  So you will have to create the subtasks dynamically.
>    type Pointer_To_MergeSortTask is access MergeSortTask;
>    task body MergeSortTask is
>      subTask1 : Pointer_To_MergeSortTask;
>      subTask2 : Pointer_To_MergeSortTask;
>    begin
>    ...
>     if (**array size > 1 element**)
>       -- Actually sort the array here
>       subTask1 := new MergeSortTask;
>       subTask2 := new MergeSortTask;
>       subTask1.doSort(**<1st half>**);
>       subTask2.doSort(**<2nd half>**);
>
>       -- Wait till both sub-task have finished sorting
>       subTask1.awaitResult;
>       subTask2.awaitResult;
>
>
> >   accept doSort(InArray : in out element_array) do
> >     ** How to get the InArray to be used outside the doSort?? **
> >     -- Synchronize with the caller but return control
> >   end doSort;
>   You'll have to copy InArray, since you only have access to it for
> the (short) time you are between the "accept" and the "end doSort".
> You can't create the copy on the stack "Copy : element_array := InArray;"
> since of course the stack is cut back at "end doSort", so you'll have
> to create the copy on the heap and manually free it.
>   type Pointer_To_Element_Array is access Element_Array;
>   ...
>   -- then inside the task body:
>   My_Data : Pointer_To_Element_Array;
>   ...
>   accept doSort(InArray : in out element_array) do
>     -- Create a local copy of InArray on the heap
>     My_Data := new Element_Array'(InArray);
>     -- Synchronize with the caller but return control
>   end doSort;
>
> But this is not what you want, of course, since it does not sort
> InArray, but only a copy of it.  In particular, the code
>      baseTask.doSort(InArray);
> won't sort InArray - it will merely start up, and not wait for, a
> set of tasks that will sort a copy of InArray.  One possible solution
> is to make
>     entry doSort     (InArray : in     element_array);
>     entry awaitResult(InArray :    out element_array);
> and return the sorted result at awaitResult time.

Re: Parallel Merge Sort

[Peter Hermann]

R. Stegers <rstegers@cs.vu.nl> wrote:
> Thanks a lot, this is exactly what I needed to know!

one line of response and hundred lines of repetition!
you must be certainly not aware of your unfairness.

Re: Parallel Merge Sort

[R. Stegers]

> one line of response and hundred lines of repetition!
> you must be certainly not aware of your unfairness.

You're absolutely right.

Re: Parallel Merge Sort

[R. Stegers]

Maybe someone can help me solve one final little issue.

The parallel Merge Sort works fine now. But when I want to use it I cannot
directly declare for example an integer array:

  package IntSort is new SORT_PACKAGE(integer, compareInt);
  use IntSort;

  -- This declaration does not work when I want to use ar as a parameter in
a call to Sort.
  ar : integer array(1..3);

  -- Instead I have to use this.
  ar : IntSort.element_array(1.. 3);

  sort(ar);

This is the declaration of the package:

  generic
    type element_type is private;
    with function "<=" (element1, element2 : element_type) return Boolean;
  package SORT_PACKAGE is

    type element_array is array(integer range <>) of element_type;

    procedure Sort(InArray : in out element_array);

    < ... >
  end SORT_PACKAGE;

I figured that since 'type' creates a new type, which cannot be interchanged
(?) with the original type I would have to use Subtype instead.
Unfortunately the compiler won't accept...

It's only a minor issue but if you want to do it right...

Does anybody know if it's possible??

Re: Parallel Merge Sort

[Jeffrey Carter]

"R. Stegers" wrote:
> 
> Maybe someone can help me solve one final little issue.
> 
> The parallel Merge Sort works fine now. But when I want to use it I cannot
> directly declare for example an integer array:
> 
>   package IntSort is new SORT_PACKAGE(integer, compareInt);
>   use IntSort;
> 
>   -- This declaration does not work when I want to use ar as a parameter in
> a call to Sort.
>   ar : integer array(1..3);

This is invalid Ada. You might be trying to say

Ar : array (1 .. 3) of Integer;

Now Ar is of an anonymous array type. Since procedure Sort requires a
variable of type Element_Array, obviously this variable won't work.

> 
>   -- Instead I have to use this.
>   ar : IntSort.element_array(1.. 3);

This Ar has the correct type, which is why it works.

If your package were defined as

generic
   type Element is private;
   type Element_Array is array (Positive range <>) of Element;
...

Then you could write

type Integer_Array is array (Positive range <>) of Integer;

package Sort is new Sort_Package (Element => Integer, Element_Array =>
Integer_Array, ...);

Ar : Integer_Array (1 .. 3);

...

Sort.Sort (Inarray => Ar);

Even better might be

generic
   type Element is private;
   type Index is (<>);
   type Element_Array is array (Index range <>) of Element;
...

Then your instantiation would read

package Sort is new Sort_Package
   (Element => Integer, Index => Positive, Element_Array =>
Integer_Array);

However, I suspect you would have to modify most of your use of indices
in Sort_Package if you did this.

-- 
Jeffrey Carter

Re: Parallel Merge Sort

[tmoran]

Your Sort_Package declares an array type that it knows how to sort, which
means that anyone using it must use its array type.  Take a look at
Barnes' "Programming in Ada 95", 2nd edition, p. 396, or "A generic
sorting procedure" in John English's "Ada 95 The Craft of Object-Oriented
Programming" (online via www.adapower.com) where they take the more
general approach of passing in the array type as a parameter:
  generic
    type Index is (<>);
    type Item is private;
    type Collection is array(Index range <>) of Item;
    with function "<"(X,Y:Item) return Boolean;
  procedure Sort(C : in out Collection);

Re: Parallel Merge Sort

[Kenneth Almquist]

tmoran@acm.org wrote:
>>   accept doSort(InArray : in out element_array) do
>>     ** How to get the InArray to be used outside the doSort?? **
>>     -- Synchronize with the caller but return control
>>   end doSort;
>   You'll have to copy InArray, since you only have access to it for
> the (short) time you are between the "accept" and the "end doSort".

The alternative is to have the task directly access the data to be sorted.

-- Sort the elements stored in array A.  The remaining parameters are
-- there to let us mimimize memory usage.  B is an array with the same
-- bounds as A, used for scratch storage.  If Store_In_B is true, then
-- the result will be placed in B rather than A.

procedure Parallel_Sort(A, B : in out Element_Array; Store_In_B : Boolean) is

    task type Sort_Task (First, Last : Positive) is
        -- no entries;
    end  Sort_Task;

    task body Sort_Task is
    begin
        Parallel_Sort(A(First .. Last), B(First .. Last), not Store_In_B);
    end Sort_Task;

    ...

begin
    ...

    -- Split the data into two halves and sort them recursively.
    Split := A'First + Size/2;
    declare
	Task_1 : Sort_Task(A'First, Split);
	Tast_2 : Sort_Task(Split + 1, A'Last);
    begin
	-- Nothing to do here except wait for the tasks to complete,
	-- and we don't have to write any code to do that.  In Ada,
	-- when a task goes out of scope we automaticly block until
	-- the task completes.
	null;
    end;

    -- Now merge the two halves.  If Store_In_B is true, then the
    -- two halves are stored in A; otherwise they are in B.
    ...

end Parallel_Sort;

				Kenneth Almquist

Re: Parallel Merge Sort

[Nick Roberts]

On Fri, 15 Feb 2002 22:34:07 +0100, "R. Stegers" <rstegers@cs.vu.nl>
strongly typed:

>I want to create a generic package which can sort an array with any type of
>elements. The index is of the integer type. It is also required that the
>merge sort is performed in parallel. I'm a C/C++-programmer with very
>limited Ada experience. I think I got the idea of tasks/rendevous right. I
>run into some problems here:
>...

Ruud, may I ask you please, what is this? Is it an academic exercise, or is
it for a genuine application? If the latter, would you please describe the
application and your target hardware; in particular, what kind of data are
you are sorting, how many are you sorting, and why. (Any speed calculations
you may have made would also be relevant.)

-- 
Nick Roberts

Re: Parallel Merge Sort

[R. Stegers]

I have to say it's only an academic excercise. We have a course called
'Principles of programming languages'. 5 Assignments in 5 different
languages (Prolog, Perl, Ada, SmallTalk and Gofer) have to be programmed.

As you can see, the 5 languages give an impression of the different language
types (imperative, oo, functional, logical).

The assignment for Ada is to write a parallel merge-sort which can sort a
list of any type.

If you'r interested in my sollution I can email my source to you. It's
working fine now. To make it work for huge lists it has to be adapted. Now
for every split of the list, two new tasks are created while the previously
tasks are suspended. This creates quite a lot of task (threads) which might
be avoided (but that cannot be part of the assignment which stated that a
task should create two new sub-tasks every time the list is split into 2).

Ruud