🚀 go-pugleaf

In this happy new year of 1993, in next week's (Wed, January 13)

                        S E M I N A R
                             ON
            COMBINATORICS, ALGORITHMS AND GEOMETRY

there will be a talk by

		J\"org Keller (CWI)
on

=============================================================================
	Fast Parallel Permutation Algorithms

Abstract:
We investigate the task of permuting $n$ data items on a PRAM with $p$
processors. The task is trivial if $n$ additional cells of global memory
are available. Each processor moves $n/p$ items to the additional storage
and then writes these items back in permuted order.

However, if the additional storage is less than $n$, the task gets
more difficult. Because not all items can be backed up, at least some of
them have to be permuted without additional storage. This can be done by
starting with an item $x$ and following the cycle
$x,\pi(x),\pi(\pi(x)),\ldots,x$. At most two items have to be backed up,
no matter how long the cycle is.

We consider three cases, where the permutation is
- fixed.
- a linear function $\pi(x)=ax\bmod n$.
- arbritrary.

For the first case, Aggarwal, Chandra and Snir (1989) give an optimal
solution if $p\leq n^{1-\epsilon}$. However, their algorithm has large
constant factors that make it impractical.

For the second case, an optimal algorithm is given for $p\leq n/\log n$.
This algorithm exploits the regular structure of the cycles for linear
permutations.

For the third case, a family of algorithms $({\cal A}_k)_k$ is given for
$p=n/\log n$. The algorithms show a time-space tradeoff. ${\cal A}_k$
needs time $D\log n\log^{(k)} n$, where $\log^{(k)} n$ denotes $k$ times
application of $\log$ to $n$. The storage requirements for ${\cal A}_k$
are $n$ global bits, $n/\log n$ global memory cells if $k\geq 2$, and
$D\log n/\log^{(k-1)} n$ local memory cells per processor if $k\geq 2$.
We present simulation results that hint that in practice even
${\cal A}_1$ has an acceptable run time.
=============================================================================

Contact Persons: J. Tromp (020 592 4078) and A. Gerards (020 592 4045)
                 (tromp@cwi.nl)              (bgerards@cwi.nl)
Frequency:       2nd and 4th Wednesday of the month
Time:            Wednesday, 14.15-16.00.
Place:           Room M280
                 Centrum voor Wiskunde en Informatica,
                 Kruislaan 413,
                 1098 SJ Amsterdam.