We consider the problem of broadcasting on torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. In this paper, we obtain an optimal broadcasting algorithm that uses pd time steps for a d-dimensional torus with (2d+1)/sup p/ nodes in each side of the torus. Using this algorithm, we show that a broadcasting on a d-dimensional mesh with the same size can be done in pd+p+d-1 time steps.
展开▼
机译:我们考虑使用电路交换,半双工和链路绑定通信在环面和网状网络上广播的问题。在本文中,我们获得了一种优化的广播算法,该算法对d维环面使用pd时间步长,环面的每一侧都有(2d + 1)/ sup p /个节点。使用该算法,我们表明可以在pd + p + d-1时间步长上完成具有相同大小的d维网格上的广播。
展开▼