Re: Parallel Merge Sort

["R. Stegers" <rstegers@cs.vu.nl>]

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.