{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:30:46Z","timestamp":1762299046992,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T00:00:00Z","timestamp":1553990400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>\n            In this article, we address the problem of finding an optimal schedule for all-to-all personalized message communication among the processors in a multiprocessor system where every processor has a unique message for every other processor. When there are\n            <jats:italic>n<\/jats:italic>\n            processors and \u230a\n            <jats:italic>n<\/jats:italic>\n            \/2\u230b parallel databus or channels for message communications, there exist algorithms that require\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time for assigning the databus\/channels to the processor-pairs to obtain a schedule with minimum number of time slots. However, in recent massively parallel processing systems with a huge number of processors, the number\n            <jats:italic>k<\/jats:italic>\n            of available databus\/channels is usually much smaller than \u230a\n            <jats:italic>n<\/jats:italic>\n            \/2\u230b. Thus, in each round of communication, only\n            <jats:italic>k<\/jats:italic>\n            processor-pairs (\n            <jats:italic>k<\/jats:italic>\n            &lt; \u230a\n            <jats:italic>n<\/jats:italic>\n            \/2\u230b) can exchange their messages in parallel. We address this general case of all-to-all personalized communication and present a new technique for scheduling the channels among processor-pairs where only\n            <jats:italic>k<\/jats:italic>\n            &lt; \u230a\n            <jats:italic>n<\/jats:italic>\n            \/2\u230b databus\/channels are available. We show that the proposed technique is optimal for all values of\n            <jats:italic>n<\/jats:italic>\n            other than 2\n            <jats:italic>k<\/jats:italic>\n            &lt;\n            <jats:italic>n<\/jats:italic>\n            &lt; 3\n            <jats:italic>k<\/jats:italic>\n            . For 2\n            <jats:italic>k<\/jats:italic>\n            &lt;\n            <jats:italic>n<\/jats:italic>\n            &lt; 3\n            <jats:italic>k<\/jats:italic>\n            , we show that the required number of rounds may be more than the lower bound of \u2308\n            <jats:italic>n<\/jats:italic>\n            \/(\n            <jats:italic>n<\/jats:italic>\n            \u22121)2\n            <jats:italic>k<\/jats:italic>\n            \u2309 by at most 11%, and proving the optimality of our technique remains as an open problem in this case.\n          <\/jats:p>","DOI":"10.1145\/3329867","type":"journal-article","created":{"date-parts":[[2019,6,25]],"date-time":"2019-06-25T12:20:20Z","timestamp":1561465220000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimal Schedule for All-to-All Personalized Communication in Multiprocessor Systems"],"prefix":"10.1145","volume":"6","author":[{"given":"Dibakar","family":"Saha","sequence":"first","affiliation":[{"name":"Department of Mathematics, Indian Institute of Technology Guwahati, Assam, India"}]},{"given":"Koushik","family":"Sinha","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Southern Illinois University, Carbondale, IL 62901, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,24]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1109\/MCOM.2013.6658665"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/2.73"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of International Conference on Distributed Computing and Internet Technology, LNCS","volume":"6536","author":"Banerjee Satyajit","unstructured":"Satyajit Banerjee , Atish Datta Chowdhury , Koushik Sinha , and Subhas K. Ghosh . 2011. Contention free many-to-many communication scheduling for high performance clusters . In Proceedings of International Conference on Distributed Computing and Internet Technology, LNCS , vol. 6536 . Springer, 150--161. Satyajit Banerjee, Atish Datta Chowdhury, Koushik Sinha, and Subhas K. Ghosh. 2011. Contention free many-to-many communication scheduling for high performance clusters. In Proceedings of International Conference on Distributed Computing and Internet Technology, LNCS, vol. 6536. Springer, 150--161."},{"unstructured":"Shahid H. Bokhari. 1991. Multiphase complete exchange on a circuit switched hypercube. Retrieved from https:\/\/apps.dtic.mil\/dtic\/tr\/fulltext\/u2\/a232830.pdf.  Shahid H. Bokhari. 1991. Multiphase complete exchange on a circuit switched hypercube. Retrieved from https:\/\/apps.dtic.mil\/dtic\/tr\/fulltext\/u2\/a232830.pdf.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/12.485374"},{"volume-title":"Proceedings of Scalable High Performance Computing Conference. IEEE, 300--306","author":"Shahid","unstructured":"Shahid H. Bokhari and Harry Berryman. 1992. Complete exchange on a circuit switched mesh . In Proceedings of Scalable High Performance Computing Conference. IEEE, 300--306 . Shahid H. Bokhari and Harry Berryman. 1992. Complete exchange on a circuit switched mesh. In Proceedings of Scalable High Performance Computing Conference. IEEE, 300--306.","key":"e_1_2_1_6_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/71.642949"},{"key":"e_1_2_1_8_1","first-page":"10","article-title":"Dynamic load balancing of virtual machines using QEMU-KVM","volume":"46","author":"Chandak Akshay","year":"2012","unstructured":"Akshay Chandak , Krishnakant Jaju , Akshay Kanfade , Amit Joshi , and Pushkar Lohiya . 2012 . Dynamic load balancing of virtual machines using QEMU-KVM . Int. J. Comput. Appl. 46 , 6 (2012), 10 -- 14 . Akshay Chandak, Krishnakant Jaju, Akshay Kanfade, Amit Joshi, and Pushkar Lohiya. 2012. Dynamic load balancing of virtual machines using QEMU-KVM. Int. J. Comput. Appl. 46, 6 (2012), 10--14.","journal-title":"Int. J. Comput. Appl."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1016\/j.tcs.2009.10.026"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1016\/S0196-6774(02)00004-4"},{"key":"e_1_2_1_11_1","first-page":"111","article-title":"HyperTransport I\/O link specification","volume":"1","author":"HyperTransport Technology Consortium et\u00a0al.","year":"2008","unstructured":"HyperTransport Technology Consortium et\u00a0al. 2008 . HyperTransport I\/O link specification . Revision 1 (2008), 111 -- 118 . Retrieved from https:\/\/xdevs.com\/doc\/AMD\/_HyperTransport\/_Specification\/HyperTransport%20IO%20Link%20Specification.%20%5Brev.3.00a%5D.%5B2006-11-22%5D.1.pdf. HyperTransport Technology Consortium et\u00a0al. 2008. HyperTransport I\/O link specification. Revision 1 (2008), 111--118. Retrieved from https:\/\/xdevs.com\/doc\/AMD\/_HyperTransport\/_Specification\/HyperTransport%20IO%20Link%20Specification.%20%5Brev.3.00a%5D.%5B2006-11-22%5D.1.pdf.","journal-title":"Revision"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1109\/JETCAS.2012.2193835"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.37236\/1898"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.4153\/CJM-1965-045-4"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1007\/s10766-007-0047-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1109\/TPDS.2007.19"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1109\/SURV.2012.020212.00049"},{"key":"e_1_2_1_18_1","volume-title":"Parallel Computing: Design and Analysis of Algorithms","author":"Grama A.","year":"2003","unstructured":"A. Grama , G. Karypis , and A. Gupta . 2003 . An Introduction to Parallel Computing: Design and Analysis of Algorithms . Addison-Wesley , Reading, MA . A. Grama, G. Karypis, and A. Gupta. 2003. An Introduction to Parallel Computing: Design and Analysis of Algorithms. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_19_1","volume-title":"Combinatorial Theory","author":"Hall Marshall","unstructured":"Marshall Hall , Jr. 1986. Combinatorial Theory ( 2 nd ed.). John Wiley 8 Sons, New York. Marshall Hall, Jr. 1986. Combinatorial Theory (2nd ed.). John Wiley 8 Sons, New York.","edition":"2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1112\/jlms\/s1-10.37.26"},{"volume-title":"Graph Theory","author":"Harary Frank","unstructured":"Frank Harary . 1969. Graph Theory . Addison-Wesley . Frank Harary. 1969. Graph Theory. Addison-Wesley.","key":"e_1_2_1_21_1"},{"unstructured":"Intel. 2018a. Intel Xeon Phi Processor 7210. Retrieved from https:\/\/ark.intel.com\/products\/94033\/Intel-Xeon-Phi-Processor-7210-16GB-1_30-GHz-64-core.  Intel. 2018a. Intel Xeon Phi Processor 7210. Retrieved from https:\/\/ark.intel.com\/products\/94033\/Intel-Xeon-Phi-Processor-7210-16GB-1_30-GHz-64-core.","key":"e_1_2_1_22_1"},{"unstructured":"Intel. 2018b. Intel Xeon Processor E5-2683 v4. Retrieevd from https:\/\/ark.intel.com\/products\/91766\/Intel-Xeon-Processor-E5-2683-v4-40M-Cache-2_10-GHz.  Intel. 2018b. Intel Xeon Processor E5-2683 v4. Retrieevd from https:\/\/ark.intel.com\/products\/91766\/Intel-Xeon-Processor-E5-2683-v4-40M-Cache-2_10-GHz.","key":"e_1_2_1_23_1"},{"unstructured":"Kapil D. Joshi. 1997. Applied Discrete Structures. New Age International.   Kapil D. Joshi. 1997. Applied Discrete Structures. New Age International.","key":"e_1_2_1_24_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.5555\/2523721.2523744"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1109\/MICRO.2014.55"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/1005847.1005874"},{"volume-title":"Guide to Wireless Ad Hoc Networks","author":"Lipman Justin","unstructured":"Justin Lipman , Hai Liu , and Ivan Stojmenovic . 2009. Broadcast in ad hoc networks . In Guide to Wireless Ad Hoc Networks . Springer , 121--150. Justin Lipman, Hai Liu, and Ivan Stojmenovic. 2009. Broadcast in ad hoc networks. In Guide to Wireless Ad Hoc Networks. Springer, 121--150.","key":"e_1_2_1_28_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1016\/S0166-218X(02)00504-8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1002\/jgt.3190090104"},{"key":"e_1_2_1_31_1","volume-title":"MPI: A Message-Passing Interface Standard. Version 3.1.","author":"Forum MPI","year":"2015","unstructured":"MPI Forum . 2015 . MPI: A Message-Passing Interface Standard. Version 3.1. Retrieved from www.mpi-forum.org. MPI Forum. 2015. MPI: A Message-Passing Interface Standard. Version 3.1. Retrieved from www.mpi-forum.org."},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/183019.183046"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1016\/j.jpdc.2015.10.005"},{"key":"e_1_2_1_34_1","volume-title":"V. Ch. Venkaiah, and C. R. Subramanian.","author":"Prasant A.","year":"2007","unstructured":"A. Prasant , Gopal Kishore Kothapalli , V. Ch. Venkaiah, and C. R. Subramanian. 2007 . Various one-factorizations of complete graphs. Retrieved from https:\/\/pdfs.semanticscholar.org\/9d06\/210bb12aaafc4d22bcc723f9258cfb658ae5.pdf. A. Prasant, Gopal Kishore Kothapalli, V. Ch. Venkaiah, and C. R. Subramanian. 2007. Various one-factorizations of complete graphs. Retrieved from https:\/\/pdfs.semanticscholar.org\/9d06\/210bb12aaafc4d22bcc723f9258cfb658ae5.pdf."},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/2464996.2465434"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1007\/3-540-45706-2_112"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1007\/978-3-540-92295-7_54"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1016\/j.jpdc.2008.01.008"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1109\/71.899938"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1023\/A:1025765910100"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1145\/2597652.2597662"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1016\/S0167-8191(97)00041-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1109\/TNET.2013.2264633"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1007\/978-3-319-41321-1_20"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1109\/71.841742"},{"volume-title":"Proceedings of the 18th Annual Symposium on High Performance Interconnects (HOTI\u201910)","author":"Ziakas Dimitrios","unstructured":"Dimitrios Ziakas , Allen Baum , Robert A. Maddox , and Robert J. Safranek . 2010. Intel quickpath interconnect architectural features supporting scalable system architectures . In Proceedings of the 18th Annual Symposium on High Performance Interconnects (HOTI\u201910) . IEEE, 1--6. Dimitrios Ziakas, Allen Baum, Robert A. Maddox, and Robert J. Safranek. 2010. Intel quickpath interconnect architectural features supporting scalable system architectures. In Proceedings of the 18th Annual Symposium on High Performance Interconnects (HOTI\u201910). IEEE, 1--6.","key":"e_1_2_1_46_1"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329867","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3329867","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:23Z","timestamp":1750206383000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329867"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,31]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3329867"],"URL":"https:\/\/doi.org\/10.1145\/3329867","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2019,3,31]]},"assertion":[{"value":"2017-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}