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 $\phi$ of any network is $\Omega(\sqrt[3]{n})$ , 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 $\Omega(\phi)$ . If is the number of processors and each of the nodes is connected with a constant number of nodes, by condition $p\phi \in O(d n)$ we see that not all nodes can be processors. An interesting case is -sided cube, where $n=s^3, p=s^2, \phi=3s, d=3$ . 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 $p\phi/k \in O(d n)$ .
communication is local. In this case $\Sigma_i p_i\phi_i \in O(d n)$ , where $\phi_i$ is the routing distance. If for example, 1/2 of communication is to processor itself, 1/4 to neighbor, etc, the condition becomes $p \in O(dn)$ . 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 $\log{n}$ 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 $\Theta(1/\sqrt{n})$ throughput per node. Hence, to provide constant throughput per node, wireless (sensor) networks of processor nodes should be made sparse by adding transmission media.

Кафедра Информатики и Математического Обеспечения

Sparse Networks: Balance of Processing and Communication