{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:23:31Z","timestamp":1758266611130,"version":"3.32.0"},"reference-count":43,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2006,10,24]],"date-time":"2006-10-24T00:00:00Z","timestamp":1161648000000},"content-version":"vor","delay-in-days":5166,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1992,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give practical algorithms, complexity analysis and implementation for one\u2010to\u2010all broadcasting, all\u2010to\u2010all personalized communication and matrix transpose (with two\u2010dimensional partitioning of the matrix) on hypercubes. We assume the following communication characteristics: circuit\u2010switched, e\u2010cube routing and one\u2010port communication model.<\/jats:p><jats:p>For one\u2010to\u2010all broadcasting, we give an algorithm that combines the well\u2010known recursive doubling algorithm[1] and the algorithm based on edgedisjoint spanning trees[2]. The measured times of the combined algorithm are always superior to those of the edge\u2010disjoint spanning tree algorithm and outperform the recursive doubling algorithm. For all\u2010to\u2010all personalized communication we propose a hybrid algorithm that combines the well\u2010known recursive doubling algorithm[3,4] and the recently proposed direct\u2010route algorithm[5,6] Our hybrid algorithm balances between data transfer time and start\u2010up time of these two algorithms, and its communication complexity is estimated to be better than the two previous algorithms for a range of machine parameters. For matrix transpose with two\u2010dimensional partitioning of the matrix, we relate a two\u2010phase algorithm to the previous result in Reference 7. The algorithm is predicted to be better than the recursive transpose algorithm[8] by n nearest\u2010neighbor communications[4]. It takes advantage of circuit\u2010switched routing and is congestion\u2010free within each phase. We also suggest a way of storing the matrix such that the transpose operation can be realized in one phase without congestion.<\/jats:p>","DOI":"10.1002\/cpe.4330040603","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:23:44Z","timestamp":1163780624000},"page":"427-457","source":"Crossref","is-referenced-by-count":18,"title":["Efficient communication primitives on hypercubes"],"prefix":"10.1002","volume":"4","author":[{"given":"Ching\u2010Tien","family":"Ho","sequence":"first","affiliation":[]},{"given":"M. T.","family":"Raghunath","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,24]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"H.SullivanandT. R.Bashkow \u2018A large scale homogeneous fully distributed parallel machine\u2019 inProceedings of the Fourth Annual Symposium on Computer Architecture March1977. pp.105\u2013124.","DOI":"10.1145\/633615.810659"},{"issue":"9","key":"e_1_2_1_3_2","first-page":"1249","article-title":"Spanning graphs for optimum broadcasting and personalized communication in hypercubes","volume":"38","author":"Johnsson S. Lennart","year":"1989","journal-title":"IEEE Tras."},{"key":"e_1_2_1_4_2","unstructured":"YousefSaadandMartin H.Schultz \u2018Data communication in hypercubes\u2019 Technical Report YALEU\/DCS\/RR\u2010428 Department of Computer Science Yale University October1985."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0609037"},{"key":"e_1_2_1_6_2","unstructured":"RiichiroTake \u2018An optimal routing method of all to all communication on hypercube networks\u2019 inthe 35th Igormation Processing Society of Japan 1987.in Japanese)."},{"key":"e_1_2_1_7_2","unstructured":"Steven R.Seidel \u2018Circuit\u2010switched vs. store\u2010and\u2010forward solutions to symmetric communication problems\u2019 inProc. of The Fourth Conference on Hypercubes Concurrent Computers and Applications March1989 pp.253\u2013255."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675778"},{"issue":"7","key":"e_1_2_1_9_2","first-page":"801","article-title":"A fast computer method for matrix transposing","volume":"21","author":"Eklundh J. O.","year":"1972","journal-title":"IEEE Tram."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/DMCC.1990.556323"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676393"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(87)90002-5"},{"key":"e_1_2_1_13_2","unstructured":"S.Lennart Johnsson \u2018Odd\u2010even cyclic reduction on ensemble architectures and the solution of tridiagonal systems of equations\u2019 Technical Report YALE\/DCS\/RR\u2010339 Department of Computer Science Yale University October1984."},{"key":"e_1_2_1_14_2","first-page":"108","volume-title":"Parallel Processing and Medium\u2010scale Multiprocessors","author":"Johnsson S. Lennart","year":"1989"},{"key":"e_1_2_1_15_2","first-page":"181","volume-title":"Hypercube Multiprocessors 1986","author":"Moler Cleve","year":"1987"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(87)90038-4"},{"key":"e_1_2_1_17_2","first-page":"161","volume-title":"Hypercube Multiprocessors 1986","author":"Geist G. A.","year":"1987"},{"key":"e_1_2_1_18_2","first-page":"223","volume-title":"Advanced Algorithms and Architectures for Signal Processing II","author":"Lennart Johnsson S.","year":"1987"},{"key":"e_1_2_1_19_2","unstructured":"S.Lennart Johnsson MichelJacqueminandChing\u2010TienHo \u2018High radix FFT on Boolean cube networks\u2019 Technical Report YALEU\/DCS\/RR\u2010751 Department of Computer Science. Yale University November1989)."},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"Franco P.PreparataandJ. E.Vuillemin \u2018The cube connected cycles: a versatile network for parallel computation\u2019 inProc. Twentieth Annual IEEE Symposium on Foundations of Computer Science 1979 pp.140\u2013147.","DOI":"10.1109\/SFCS.1979.43"},{"volume-title":"Computational Aspects of VLSI","year":"1984","author":"Ullman Jeffrey D.","key":"e_1_2_1_21_2"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90026-L"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"Geoffrey C.FoxandWojtekFurmanski \u2018Optimal communication algorithms for regular decompositions on the hypercube\u2019. inProceedings of the Third Conference on Hypercube Concurrent Computers and Applications ACM 1988 pp.648\u2013713.","DOI":"10.1145\/62297.62389"},{"volume-title":"Solving Problem on Concurrent Processors","year":"1988","author":"Fox G.","key":"e_1_2_1_24_2"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90033-6"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90039-C"},{"key":"e_1_2_1_27_2","unstructured":"S. LennartJohnssonandChing\u2010TienHo \u2018Maximizing channel utilization for all\u2010to\u2010all personalized communication on Boolean cubes\u2019 Technical report Thinking Machines Corporation November1990."},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0908023"},{"key":"e_1_2_1_29_2","doi-asserted-by":"crossref","unstructured":"S. F.Nugent \u2018The iPSC\/2 direct\u2010connect communications technology\u2019 inProc. of the 3rd Conf. on Hypercube Concurrent Computers and Applications ACM 1988 pp.51\u201360.","DOI":"10.1145\/62297.62305"},{"key":"e_1_2_1_30_2","doi-asserted-by":"crossref","unstructured":"RamuneArlauskas \u2018iPSC\/2 system: a second generation hypercube\u2019 inProc. of the 3rd Conf. on Hypercube Concurrent Computers and Applications ACM 1988 pp.38\u201342.","DOI":"10.1145\/62297.62303"},{"key":"e_1_2_1_31_2","doi-asserted-by":"crossref","unstructured":"PaulClose \u2018The iPSC\/2 node architecture\u2019 inProc. of the 3rd Conf. on Hypercube Concurrent Computers and Applications ACM 1988 pp.43\u201350.","DOI":"10.1145\/62297.62304"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330010103"},{"key":"e_1_2_1_33_2","doi-asserted-by":"crossref","unstructured":"Steven R.SeidelandThomas E.Schmiermund \u2018Refining the communication model for the Intel iPSC\/2\u2019 inProc. of The Fifth Distributed Memory Computing Conference April1990 pp.1334\u20131342.","DOI":"10.1109\/DMCC.1990.556394"},{"key":"e_1_2_1_34_2","unstructured":"PierreFraigniaud \u2018Complexity analysis of broadcasting in hypercubes with restricted communication capabilities\u2019 Technical report IMAG Ecole Normale Sup\u00e9rieure de Lyon 1989."},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","unstructured":"Michael J.Fischer \u2018Efficiency of equivalence algorithms\u2019 in E.R. Miller and W.J. Thatcher (Eds.) Complexity of Computer Computations 1972 pp.153\u2013167.","DOI":"10.1007\/978-1-4684-2001-2_14"},{"volume-title":"The Design and Analysis of Computer Algorithms","year":"1974","author":"Aho Alfred V.","key":"e_1_2_1_36_2"},{"key":"e_1_2_1_37_2","unstructured":"YousefSaadandMartin H.Schultz \u2018Topological properties of hypercubes\u2019 Technical Report YALEU\/DCS\/RR\u2010389 Department of Computer Science Yale University New Haven CT June1985."},{"key":"e_1_2_1_38_2","unstructured":"Ching\u2010TienHo \u2018Optimal communication primitives and graph embeddings on hypercubes\u2019 PhD thesis Yale University May1990."},{"volume-title":"Combinatorial Algorithms","year":"1977","author":"Reingold E. M.","key":"e_1_2_1_39_2"},{"key":"e_1_2_1_40_2","doi-asserted-by":"crossref","unstructured":"BulentAbali FusunOzgunerandAbdullaBataineh \u2018Load balanced sort on hypercube multiprocessors\u2019 inThe Fifth Distributed Memory Computing Conference IEEE 1990 pp.230\u2013236.","DOI":"10.1109\/DMCC.1990.555388"},{"key":"e_1_2_1_41_2","unstructured":"RajendraBoppanaandC. S.Raghavendra \u2018On optimal and practical routing methods for a massive data movement operation on hypercubes\u2019 Technical report University of Southern California March1990."},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/322169.322172"},{"key":"e_1_2_1_43_2","unstructured":"DavidNassimi \u2018A fault\u2010tolerant routing algorithm for BPC permutations on multistage interconnection networks\u2019 in 1989 International Conference on Parallel Processing Vol. I Penn State 1989 pp.278\u2013287."},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/359461.359481"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330040603","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330040603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T23:52:42Z","timestamp":1736639562000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330040603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,9]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1992,9]]}},"alternative-id":["10.1002\/cpe.4330040603"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330040603","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"type":"print","value":"1040-3108"},{"type":"electronic","value":"1096-9128"}],"subject":[],"published":{"date-parts":[[1992,9]]}}}