Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR96-053 | 20th March 1997 00:00

Geometric Approach for Optimal Routing on Mesh with Buses Revision of: TR96-053

RSS-Feed




Revision #1
Authors: Yosi Ben-Asher, Ilan Newman
Accepted on: 20th March 1997 00:00
Downloads: 1143
Keywords: 


Abstract:


The architecture of 'mesh of buses'
is an important model in parallel computing.
Its main advantage is that the additional broadcast capability can be used
to overcome the main disadvantage of the mesh, namely
its relatively large diameter.
We show that the addition of buses indeed accelerates routing times.
Furthermore, unlike in the `store and
forward' model, the routing time becomes proportional to the network load,
resulting in decreasing in routing time for a smaller number of packets.

We consider 1-1 routing of $m$ packets in
a $d$-dimensional mesh with $n^d$ processors and $d\cdot n^{d-1}$
buses (one per row and column).
The two standard models of accessing the buses are considered and
compared: CREW, in which only one processor may transmit at any
given time on a given bus, and the CRCW
model in which several processors may attempt to transmit at the
same time (getting a noise signal as a result).
We design a routing algorithm that routes $m$ packets
in the CREW model in $O(m^{\frac 1 d} + n^{\frac 1 {d+1}})$
steps. This result holds for $m \leq n^{\frac{2d}{3}}$ for $d \geq 3$
and unconditionally for $d=2$.
A matching lower bound is also proved.
In the CRCW case we show an algorithm of $O(m^{\frac 1 d}
\log n)$ and a lower
bound of $\Omega(m^{\frac 1 d})$. It is shown that the difference between
the models is essentially due to the improved capability of estimating
threshold functions in the CRCW case.


Paper:

TR96-053 | 6th August 1996 00:00

Geometric Approach for Optimal Routing on Mesh with Buses





TR96-053
Authors: Yosi Ben-Asher, Ilan Newman
Publication: 14th October 1996 12:17
Downloads: 1225
Keywords: 


Abstract:

The architecture of 'mesh of buses' is an important model in parallel computing. Its main advantage is that the additional broadcast capability can be used to overcome the main disadvantage of the mesh, namely its relatively large diameter. We show that the addition of buses indeed accelerates routing times. Furthermore, unlike in the `store and forward' model, the routing time becomes proportional to the network load, result



ISSN 1433-8092 | Imprint