Go backward to Hello, World! Go up to Tutorial Go forward to Long Integer Multiplication

Quicksort

// ----------------------------------------------------------------------------
// Quicksort
// ----------------------------------------------------------------------------
#include <rt++.h>

...

// ----------------------------------------------------------------------------
// sort <a/l/r> in parallel
// ----------------------------------------------------------------------------
int qsort(Array<float> a, int l, int r)
{
  if (r-l < MINSIZE) return(sort(a, l, r));

  int m0, m1;
  partition(a, l, r, a[(l+r)/2], &m0, &m1);

  Thread3<int, Array<float>, int, int> t0(qsort, a, l, m0);
  Thread3<int, Array<float>, int, int> t1(qsort, a, m1, r);

  Wait(t0); Wait(t1);
  return(0);
}

// ----------------------------------------------------------------------------
// RT++ main function
// ----------------------------------------------------------------------------
int qmain(int argc, char *argv[]) 
{
  while(...)
  {
    Array<float> a(S);
    ...
    qsort(a, 0, S);
  }
  return(0);
}

// ----------------------------------------------------------------------------
// C++ main function
// ----------------------------------------------------------------------------
int main(int argc, char *argv[]) 
{
  RT_Argument rtarg;
  ...
  rt_arg.proc = 3;
  rt_main(qmain, argc, argv, rtarg, 0);
  ...
}

This program operates on arrays of type Array<float>. Array is an RT++ type constructor whose objects can be used similar to C++ arrays but are automatically reclaimed when not referenced any more.  

The core of the program is the function qsort which takes an array $a$ that is to be sorted within the index range $[l\; ...r[$. If this index range is smaller than some threshold, the array is sorted sequentially. Otherwise, the array is partitioned according to some pivot element $e$ into three ranges $[l,m$₀[ (all elements less than $e$) $[m$₀,m₁[ (all elements equal to $e$) and $[m$₀,r[ (all elements greater than $e$). What remains to be done is to sort the array in the first and in the third subrange. This is the task of two concurrent threads (units of control) $t$₀ and $t$₁. When both threads have terminated, the whole array is sorted.

Let's take a closer look at such a thread declaration  

Thread3<int, Array<float>, int, int> t0(qsort, a, l, m0);

R qsort(A1, A2, A3)

Wait(t0)

Above skeleton omits a few ugly technical details that are only necessary because the GNU g++ compiler does not implement the full ANSI C++ standard yet (see here for details). The program namely has to contain also the following top-level declarations  

Atom(int); 
Atom(float);
Ref(Array<float>);
ThreadArg3(A, int, Array<float>, int, int);

ThreadArg3(A,...) declares that threads of the corresponding prototype are used (where A is an arbitrary unused identifier that is needed internally). Declarations of this kind have to be given for any thread type used by an RT++ program.

The good message is that these declarations are only needed in one object file; if your program is composed of multiple source files that are individually compiled and finally linked together, all necessary declarations can be collected in a single source file of the application.

In case none of the object files contains the required declarations, the linker complains with error messages as the following:  

qsort.o(.text+0xef8): undefined reference to `Type<int>::init'
qsort.o(.text+0xf0b): undefined reference to `Type<int>::scan'
qsort.o(.text+0x987): undefined reference to `Type<float>::init'
qsort.o(.text+0x9fe): undefined reference to `Type<float>::scan'
qsort.o(.text+0xee5): undefined reference to `Type<Array<float> >::scan'
qsort.o(.text+0xf39): undefined reference to `Type<Array<float> >::init'
qsort.o(.text+0xb6d): undefined reference to 
  `Type<ArgumentThread3<int, Array<float>, int, int> >::scan'

------------------------------------------------------------------------------
RT++ 1.0 (C) 1996 Wolfgang Schreiner <Wolfgang.Schreiner@risc.uni-linz.ac.at>
proc: 3, mem: 1000000, heap: 100032, blocks: 12, stack: 5000
------------------------------------------------------------------------------
RT++ GC 1 (1360 ms): 8 blocks with 42560 bytes in 30 (+ 0) ms.
RT++ GC 2 (1820 ms): 11 blocks with 64112 bytes in 20 (+ 0) ms.
RT++ GC 3 (2640 ms): 9 blocks with 53456 bytes in 20 (+ 0) ms.
RT++ GC 4 (3200 ms): 3 blocks with 15984 bytes in 30 (+ 0) ms.
RT++ GC: less than 25008 bytes heap (1 block per process) free.
RT++ GC: increase heap by 100032 bytes.
RT++ GC 5 (4670 ms): 7 blocks with 33520 bytes in 50 (+ 0) ms.
RT++ GC 6 (5120 ms): 16 blocks with 89952 bytes in 40 (+ 10) ms.
RT++ GC 7 (6350 ms): 14 blocks with 75008 bytes in 40 (+ 0) ms.
RT++ GC 8 (7140 ms): 14 blocks with 67344 bytes in 50 (+ 0) ms.
RT++ GC 9 (7890 ms): 18 blocks with 94864 bytes in 40 (+ 0) ms.
RT++ GC 10 (9170 ms): 4 blocks with 7664 bytes in 50 (+ 10) ms.
RT++ GC: less than 25008 bytes heap (1 block per process) free.
RT++ GC: increase heap by 100032 bytes.
RT++ GC 11 (10650 ms): 16 blocks with 74144 bytes in 60 (+ 10) ms.
RT++ GC 12 (11520 ms): 6 blocks with 17872 bytes in 70 (+ 0) ms.
RT++ GC: less than 25008 bytes heap (1 block per process) free.
RT++ GC: increase heap by 100032 bytes.
RT++ GC 13 (13170 ms): 41 blocks with 243984 bytes in 70 (+ 0) ms.
------------------------------------------------------------------------------
RT++ execution
        Return code:    0
        Real time(ms):  16650
        Proc time(ms):  16620
        All procs(ms):  46900
RT++ garbage collections
        Number:         13
        Increments:     3
        Waiting(ms):    30
        Collecting(ms): 570
        Blocks:         167
        Bytes:          880464
------------------------------------------------------------------------------

A hint concerning the number of processes used for the execution of an RT++ program: if the total process time of all processes is drastically smaller than the real time of program execution multiplied with the number of processes, the machine is probably overloaded i.e. not every process ready for execution finds a free processor. Consequently, only as many processes should be used for program execution as processors are idle (keeping in mind that in a multi-user system also other activities may be going on!). Likewise, if synchronization times for garbage collection phases get large, this is a sign that some process is not executing while other processes are waiting for garbage collection to begin.