Global communication algorithms for Cayley graphs
作者： Vance Faber
DOI:
关键词:
摘要: We discuss several combinatorial problems that arise when one looks at computational algorithms for highly symmetric networks of processors. More specifically, we are interested in minimal times associated with four communication tasks (defined more precisely below): universal broadcast, every processor has a vector it wishes to broadcast all the others; accumulation, receive sum vectors being sent by other processors; exchange, exchange each processor; and global summation, wants processors
arxiv.org
harvard.edu参考文章(6)
Gert Sabidussi, Vertex-transitive Graphs. Monatshefte für Mathematik. ,vol. 68, pp. 426- 438 ,(1964) , 10.1007/BF01304186
Gannon, Van Rosendale, On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms IEEE Transactions on Computers. ,vol. 33, pp. 1180- 1194 ,(1984) , 10.1109/TC.1984.1676393
Maurice Tchuente, Permutation Factorization on Star-Connected Networks of Binary Automata Siam Journal on Algebraic and Discrete Methods. ,vol. 6, pp. 537- 540 ,(1985) , 10.1137/0606052
Olaf M Lubeck, V Faber, Modeling the performance of hypercubes: A case study using the particle-in-cell application parallel computing. ,vol. 9, pp. 37- 52 ,(1988) , 10.1016/0167-8191(88)90017-8
C. Berge, Graphs and hypergraphs ,(1973)
Fan R K Chung, Spectral Graph Theory ,(1996)