Re: Parallel Merge Sort

[tmoran@acm.org]

>  - 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.