ALL-TO-ALL BROADCASTING ALGORITHMS ON HONEYCOMB NETWORKS AND APPLICATIONS
Jean Carle, Jean‐Frédéric Myoupo, David Semé · Parallel Processing Letters · 1999
This paper presents two simple all-to-all broadcasting algorithms on honeycomb mesh. Consider a network with n processors, one has personalized routing strategy at each node and it requires a 3n communication time complexity. This communication time can be reduced to n because the computation time is always assumed to be much lower than the communication time. The other is based on a Hamiltonian path and has a 2n communication time complexity. We show how they can be used to get parallel solutions to a class of problems on honeycomb networks, among others Prefix Sums, Maximal Vectors, Maximal Sum Subsegment, Parenthesis Matching, Decoding Binary Tree, and Sorting. In our knowledge, these all-to-all broadcast algorithms are the only ones so far exhibited on a honeycomb.