Group Action Graphs and Parallel Architectures
Fred S. Annexstein, Marc Baumslag, Arnold L. Rosenberg · SIAM Journal on Computing · 1990
The authors develop an algebraic framework that exposes the structural kinship among the deBruijn, shuffle-exchange, butterfly, and cube-connected cycles networks and illustrate algorithmic benefits that ensue from the exposed relationships. The framework builds on two alge-braically specified genres of graphs: A group action graph (GAG, for short) is given by a set V of vertices and a set $\Pi$ of permutations of V : For each $v \in V$ and each $\pi \in \Pi$, there is an arc labeled $\pi$ from vertex v to vertex $v \pi$. A Cayley graph is a $\operatorname{GAG}(V, \Pi)$, where V is the group ${\bf {\operatorname{Gr}}}(\Pi)$ generated by $\Pi$ and where each $\pi \in \Pi$ acts on each $g \in {\bf {\operatorname{Gr}}} (\Pi)$ by right multiplication. The graphs $({\bf {\operatorname{Gr}}}(\Pi), \Pi)$ and $(V, \Pi)$ are called associated graphs. It is shown that every ${\operatorname{GAG}}$ is a quotient graph of its associated Cayley graph. By applying such general results, the authors determine the following: • The butterfly network (a Cayley graph) and the deBruijn network (a ${\operatorname{GAG}}$) are associated graphs. • The cube-connected cycles network (a Cayley graph) and the shuffle-exchange network (a ${\operatorname{GAG}}$) are associated graphs. • The order-n instance of both the butterfly and the cube-connected cycles share the same underlying group, but have slightly different generator sets $\Pi$. By analyzing these algebraic results, it is delimited, for any Cayley graph $\mathcal{G}$ and associated $\operatorname{GAG} \mathcal{H}$, a family of “leveled” algorithms which run as efficiently on $\mathcal{H}$ as they do on (the much larger) $\mathcal{G}$. Further analysis of the results yields new, surprisingly efficient simulations by the shuffle-oriented networks (the shuffle-exchange and deBruijn networks) of like-sized butterfly-oriented networks (the butterfly and cube-connected cycles networks): • An N-vertex butterfly-oriented network can be simulated by the smallest shuffle-oriented network that is big enough to hold it with slowdown $O(\log \log N)$. This simulation is exponentially faster than the anticipated logarithmic slowdown. The mappings that underlie the simulation can be computed in linear time; and they afford one an algorithmic tech-nique for translating any program developed for a butterfly-oriented architecture into an equivalent program for a shuffle-oriented architecture, the latter program incurring only the indicated slowdown factor.