Computation with No Memory, and Rearrangeable Multicast Networks
Serge Burckel, Emeric Gioan, Emmanuel Thomé
Abstract
We investigate the computation of mappings from a set
Sn to itself with in situ programs,
that is using no extra variables than the input, and performing
modifications of one component at a time, hence using no extra
memory. In this paper, we survey this problem introduced in previous
papers by the authors, we detail its close relation with rearrangeable
multicast networks, and we provide new results for both viewpoints. A
bijective mapping can be computed by 2n-1 component
modifications, that is by a program of length 2n-1, a
result equivalent to the rearrangeability of the concatenation of two
reversed butterfly networks. For a general arbitrary mapping, we give
two methods to build a program with maximal length
4n-3. Equivalently, this yields rearrangeable multicast
routing methods for the network formed by four successive butterflies
with alternating reversions. The first method is available for any set
S and practically equivalent to a known method in network
theory. The second method, a refinement of the first, described when
|S| is a power of 2, is new and allows more
flexibility than the known method. For a linear mapping, when
S is any field, or a quotient of an Euclidean domain
(e.g. ℤ/sℤ for any integer s),
we build a program with maximal length 2n-1. In this
case the assignments are also linear, thereby particularly efficient
from the algorithmic viewpoint, and giving moreover directly a program
for the inverse when it exists. This yields also a new result on
matrix decompositions, and a new result on the multicast properties of
two successive reversed butterflies. Results of this flavour were
known only for the boolean field ℤ/2ℤ.
Full Text: PDF PostScript