Sparse Networks: Balance of Processing and Communication
Ville Leppänen (University of Turku, Finland)Martti Penttonen (University of Kuopio, Finland)
In this talk we discuss the balance of processing and communication, in particular the need of bandwidth, and emphasize the concept of sparseness.
It was pointed out by Vitányi that in 3-dimensional world the
diameter of any network is
, where
is
the number of nodes, routers or processors. Hence, if processors are
allowed to send each others messages without target or frequency restriction,
the bandwidth per processor must be
.
If
is the number of processors and each of the
nodes is connected
with a constant number
of nodes,
by condition
we see that not all
nodes can be processors. An interesting case is
-sided cube, where
. This is called
a sparse mesh or torus,
depending whether circular paths are allowed.
In this kind of a structure, it is possible that
all processors send and receive at every step and the routing time
is still
per packet.
It may seem that sparseness is waste -- in our example nodes
are routers and only
nodes are processors.
That is the cost of the bandwidth -- they are necessary if the communication of the
processors is not restricted. Denser networks may work, if communication
is restricted, for example if
- communication is sparse. If only every
th step of the processor is communication, the condition becomes
.
- communication is local. In this case
, where
is the routing distance. If for example, 1/2 of communication is to processor itself, 1/4 to neighbor, etc, the condition becomes
. So, average routing time can be
per packet even if every node is a processor.
Examples of sparse networks are
- sparse meshes. We have studied coated meshes, where a cube of
routers is coated with processors, and sparse tori, where on any path of
an
-sided
-dimensional torus every
th node is a processor.
- sparse butterflies, sparse fat trees etc.
In SBPRAM (Saarbrücken PRAM)
processors are connected by a
layered butterfly of router nodes.
Also dynamic networks must be sparse, unless communication is sparse. In principle,
sparseness could be implemented by embedding in one of the above mentioned structures.
For example, Gupta and Kumar (1999) say that large scale wireless
networks can at best have
throughput per node.
Hence, to provide constant throughput per node, wireless (sensor) networks of
processor nodes should be made sparse by adding
transmission media.