23-06-2014, 09:55 AM
A Fast Parallel Algorithm for Routing in
Permutation Networks
[attachment=65180]
INTRODUCTION
APERMUTATION network (also known as a rearran-
- geable network) is a system in which some number of
terminals called inputs, an equal number of other terminals
called outputs, and some number of switches are interconnected
by means of wires to achieve the following condition:
given any one-to-one correspondence between the inputs and
the outputs, an appropriate set of switches can be closed to
establish independent paths from the inputs to their corresponding
outputs. A permutation network with η inputs and
η outputs will be called an n-permuter.
PARALLEL RANDOM ACCESS COMPUTERS
Whenever we claim a complexity bound for an algorithm
we ought to be precise about the model of computation assumed.
In the case of parallel computations the problem of
finding models that are realistic in some sense, and at the same
time also sufficiently elegant and fundamental, is particularly
acute. In this section we shall sketch one approach to this
problem. The family of models we suggest is intended as a
standard for expressing asymptotic results about parallel
computations by a set of synchronized processors sharing
common memory (e.g., [11], [18]). The routing algorithm for
permutation networks typifies the kinds of applications for
which this model is well motivated, since it requires little
memory and performs a system function for which it may be
expedient to have speed at the expense of much hardware.
The model is an extension of the random access computer
(RAC) defined in [3], and will be defined here in terms of the
terminology and description to be found there. A Parallel
RAC, denoted by RAC/'*(X), is a machine with π processors,
each having κ registers and instruction set / . Each register and
each word in main memory consists of λ binary bits and the
number of such words in main memory is 2 \ Each processor
executes a fixed program and each instruction in it takes unit
time.
Permutation Networks
[attachment=65180]
INTRODUCTION
APERMUTATION network (also known as a rearran-
- geable network) is a system in which some number of
terminals called inputs, an equal number of other terminals
called outputs, and some number of switches are interconnected
by means of wires to achieve the following condition:
given any one-to-one correspondence between the inputs and
the outputs, an appropriate set of switches can be closed to
establish independent paths from the inputs to their corresponding
outputs. A permutation network with η inputs and
η outputs will be called an n-permuter.
PARALLEL RANDOM ACCESS COMPUTERS
Whenever we claim a complexity bound for an algorithm
we ought to be precise about the model of computation assumed.
In the case of parallel computations the problem of
finding models that are realistic in some sense, and at the same
time also sufficiently elegant and fundamental, is particularly
acute. In this section we shall sketch one approach to this
problem. The family of models we suggest is intended as a
standard for expressing asymptotic results about parallel
computations by a set of synchronized processors sharing
common memory (e.g., [11], [18]). The routing algorithm for
permutation networks typifies the kinds of applications for
which this model is well motivated, since it requires little
memory and performs a system function for which it may be
expedient to have speed at the expense of much hardware.
The model is an extension of the random access computer
(RAC) defined in [3], and will be defined here in terms of the
terminology and description to be found there. A Parallel
RAC, denoted by RAC/'*(X), is a machine with π processors,
each having κ registers and instruction set / . Each register and
each word in main memory consists of λ binary bits and the
number of such words in main memory is 2 \ Each processor
executes a fixed program and each instruction in it takes unit
time.