{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T00:10:19Z","timestamp":1736640619042,"version":"3.32.0"},"reference-count":21,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,20]],"date-time":"2006-10-20T00:00:00Z","timestamp":1161302400000},"content-version":"vor","delay-in-days":6077,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1990,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We review various properties of irregular graphs and suggest that they may provide useful maps for connecting processors together in distributed\u2010memory MIMD machines. In particular, for many applications the performance of a system in an irregular configuration can be expected to exceed by far that of systems in standard configurations such as hypercubes and tori, which are poor over many performance measures. Techniques are discussed which allow the construction of near\u2010optimal or optimal graphs with respect to various measures of goodness, including diameter, mean interprocessor distance and worst through\u2010routing load. We conclude that where regularity is not important, irregular graphs will almost always outperform standard, regular ones.<\/jats:p>","DOI":"10.1002\/cpe.4330020105","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:06:58Z","timestamp":1163779618000},"page":"55-78","source":"Crossref","is-referenced-by-count":9,"title":["What price regularity?"],"prefix":"10.1002","volume":"2","author":[{"given":"Dominic M. N.","family":"Prior","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael G.","family":"Norman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicholas J.","family":"Radcliffe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lyndon J.","family":"Clarke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,20]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1988.0096"},{"key":"e_1_2_1_3_2","first-page":"187","volume-title":"Distributed Computing","author":"Dally W. J.","year":"1986"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"J. F.Palmer \u2018The NCUBE family of high\u2010performance parallel computer systems\u2019 in Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications G. Fox (ed) 1988 pp.847\u2013852.","DOI":"10.1145\/62297.62415"},{"volume-title":"Random Graphs","year":"1985","author":"Bollob\u00e1s B\u00e9la","key":"e_1_2_1_5_2"},{"key":"e_1_2_1_6_2","unstructured":"Moore (c.1958)."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"J.Peterson E.Chow H.Madan \u2018A high\u2010speed message\u2010driven communication architecture\u2019 in Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems 1988.","DOI":"10.1145\/55364.55399"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"E.Chow H.Madan J.Peterson D.Grunwald andD.Reed \u2018Hyperswitch network for the hyperswitch computer\u2019 in 15th Annual Symposium on Computer Architecture 1988.","DOI":"10.1145\/633625.52411"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1137\/0211027","article-title":"A scheme for fast parallel communication","volume":"11","author":"Valiant L. G.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_10_2","unstructured":"E.Felten R.Morison S.Otto K.Barish R.Fatland andF.Ho \u2018Chess on the hypercube\u2019 in Proc. Second Hypercube Conf. Knoxville."},{"key":"e_1_2_1_11_2","unstructured":"G. V.Wilson \u2018MOBY plays chess: a multi\u2010processor chess program based on homogeneous search\u2019 Edinburgh Concurrent Supercomputer Project Technical Report (forthcoming)."},{"volume-title":"Adaptation in Natural and Artificial Systems","year":"1975","author":"Holland J. H.","key":"e_1_2_1_12_2"},{"key":"e_1_2_1_13_2","unstructured":"M. G.Norman A Genetic Approach to Topology Optimisation for Multiprocessor Architectures Edinburgh Preprint 88\/451 1988(to be published)."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"S.Lin \u2018Computer solutions of the travelling salesman problem\u2019 Bell. Syst. Tech. J. 2245\u20132269(1965).","DOI":"10.1002\/j.1538-7305.1965.tb04146.x"},{"volume-title":"The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimisation","year":"1985","author":"Lawler E. L.","key":"e_1_2_1_15_2"},{"key":"e_1_2_1_16_2","first-page":"758","article-title":"A combinatorial problem","volume":"49","author":"de Brujn N. G.","year":"1946","journal-title":"Koninkl, Nederl. Acad. Wetensch. Proc. Ser. A"},{"volume-title":"Proceedings of the 8th Technical Meeting of the Occam User Group","year":"1988","author":"Norman M. G.","key":"e_1_2_1_17_2"},{"key":"e_1_2_1_18_2","unstructured":"M. G.Norman andS.Wilson \u2018TITCH: topology independent transputer communications harness\u2019 Edinburgh Concurrent Supercomputer Project User Note 1988."},{"key":"e_1_2_1_19_2","unstructured":"NeilMiller \u2018Exploring multiple transputer arrays\u2019 INMOS Technical note #24 1988."},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"C. L.Seitz W. C.Athas C. M.Flaig A. J.Martin J.Seizovic C. S.Steele andW\u2010K.Su \u2018The architecture and programming of the Ametek Series 2010 Multicomputer\u2019 in Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications Volume I G. Fox (ed.) 1988 pp.33\u201336.","DOI":"10.1145\/62297.62302"},{"key":"e_1_2_1_21_2","unstructured":"M. G.Norman D. M. N.Prior andN. J.Radcliffe \u2018Our favourite compact graphs\u2019 Edinburgh Concurrent Supercomputer Project Technical Report #6 1989."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(86)90008-0"}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330020105","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330020105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T23:51:44Z","timestamp":1736639504000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330020105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1990,3]]}},"alternative-id":["10.1002\/cpe.4330020105"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330020105","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"type":"print","value":"1040-3108"},{"type":"electronic","value":"1096-9128"}],"subject":[],"published":{"date-parts":[[1990,3]]}}}