{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T06:57:58Z","timestamp":1648882678496},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Inter. Net."],"published-print":{"date-parts":[[2004,3]]},"abstract":"<jats:p> We investigate the average-case scalability of parallel algorithms executing on multicomputer systems whose static networks are k-ary d-cubes. Our performance metrics are isoefficiency function and isospeed scalability. For the purpose of average-case performance analysis, we formally define the concepts of average-case isoefficiency function and average-case isospeed scalability. By modeling parallel algorithms on multicomputers using task interaction graphs, we are mainly interested in the effects of communication overhead and load imbalance on the performance of parallel computations. We focus on the topology of static networks whose limited connectivities are constraints to high performance. In our probabilistic model, task computation and communication times are treated as random variables, so that we can analyze the average-case performance of parallel computations. We derive the expected parallel execution time on symmetric static networks and apply the result to k-ary d-cubes. We characterize the maximum tolerable communication overhead such that constant average-case efficiency and average-case average-speed could be maintained and that the number of tasks has a growth rate \u0398(P log P), where P is the number of processors. It is found that the scalability of a parallel computation is essentially determined by the topology of a static network, i.e., the architecture of a parallel computer system. We also argue that under our probabilistic model, the number of tasks should grow at least in the rate of \u0398(P log P), so that constant average-case efficiency and average-speed can be maintained. <\/jats:p>","DOI":"10.1142\/s0219265904001015","type":"journal-article","created":{"date-parts":[[2004,5,13]],"date-time":"2004-05-13T10:35:02Z","timestamp":1084444502000},"page":"27-45","source":"Crossref","is-referenced-by-count":0,"title":["AVERAGE-CASE SCALABILITY ANALYSIS OF PARALLEL COMPUTATIONS ON k-ARY d-CUBES"],"prefix":"10.1142","volume":"05","author":[{"given":"KEQIN","family":"LI","sequence":"first","affiliation":[{"name":"Department of Computer Science, State University of New York, New Paltz, New York 12561, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","volume-title":"Probability Concepts in Engineering Planning and Design, Volume II - Decision, Risk, and Reliability","author":"Ang A. H.-S.","year":"1984"},{"key":"rf2","volume-title":"An Introduction to Probability Theory and Its Applications, Vol. I","author":"Feller W.","year":"1968"},{"key":"rf3","volume-title":"Introduction to Parallel Computing","author":"Grama A.","year":"2003"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/88.242438"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/42411.42415"},{"key":"rf6","volume-title":"Scalable Parallel Computing","author":"Hwang K.","year":"1998"},{"key":"rf7","first-page":"483","volume":"12","author":"Indurkhya B.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/78607.78614"},{"key":"rf10","first-page":"279","volume":"21","author":"Li K.","journal-title":"Informatica \u2013 An International Journal of Computing and Informatics"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0895-7177(99)00083-7"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053300000072"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1145\/158439.158908"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/102868.102871"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1109\/88.481664"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90073-I"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1993.274941"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1993.1087"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1109\/71.285606"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1109\/71.476190"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1109\/M-PDT.1996.544440"}],"container-title":["Journal of Interconnection Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219265904001015","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T03:34:23Z","timestamp":1565148863000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219265904001015"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3]]},"references-count":20,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2004,3]]}},"alternative-id":["10.1142\/S0219265904001015"],"URL":"https:\/\/doi.org\/10.1142\/s0219265904001015","relation":{},"ISSN":["0219-2659","1793-6713"],"issn-type":[{"value":"0219-2659","type":"print"},{"value":"1793-6713","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,3]]}}}