{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T05:51:02Z","timestamp":1698213062595},"reference-count":23,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":4827,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1994,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Multi\u2010PSI is a distributed\u2010memory MIMD (multiple\u2010instruction, multiple\u2010data) computer that has 64 processors. Problems of knowledge processing, which are the object of the Multi\u2010PSI, must be divided into many partial problems in order to achieve a favorable load balance because a characteristic of the computation is the dynamic loss of uniformity. This, however, has the danger of increasing the communication overhead. Therefore, in order to constrain the communication overhead and achieve a favorable load balance, in this paper, we propose a programming method oriented to the above problem. In this methodology, the problem is formulated as multiple communicating objects and the degrees of freedom in the load allocation are maintained. On the other hand, when the load is allocated, the communication objects are estimated from the system performance and the objects' characteristics, and the processing granularity is adjusted so that it is within the tolerance. This program methodology was applied to the three program developments of the shortest path problem, the LSI routing problem, and logic simulation; each was implemented with high efficiency. For example, in the shortest path program, 260,000 small\u2010grained objects were distributed over 64 processors and reached about 75% efficiency. In addition, in the logic simulation composed of 12,000 objects (gates), a high absolute efficiency of 99 thousand events\/second and a 48\u2010fold increase in speed with 64 processors were obtained. Along with confirming the effectiveness of this programming methodology, these results demonstrated. that high efficiency can be realized in parallel processing for some degree of granularity even in a distributed\u2010memory parallel computer.<\/jats:p>","DOI":"10.1002\/scj.4690250102","type":"journal-article","created":{"date-parts":[[2007,7,8]],"date-time":"2007-07-08T01:44:09Z","timestamp":1183859049000},"page":"17-36","source":"Crossref","is-referenced-by-count":0,"title":["Parallel processing on the multi\u2010PSI computer and its evaluation \u2014 a programming paradigm based on a small\u2010grain highly concurrent object model"],"prefix":"10.1002","volume":"25","author":[{"given":"Kazuo","family":"Taki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nobuyuki","family":"Ichiyoshi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"T.Chikayama. Operating System PIMOS and Kernel Language KL1. Proc. Int. Conf. on Fifth Generation Computer Systems FGCS'92 (June1992)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"issue":"3","key":"e_1_2_1_4_2","first-page":"378","article-title":"LSI Routing Program Based on a Parallel Object Model","volume":"33","author":"Idachi H.","year":"1992","journal-title":"Journal of the Information Processing Society of Japan"},{"key":"e_1_2_1_5_2","unstructured":"H.Date Y.Matsumoto M.Hoshi H.Kato K.KimuraandK.Taki.LSI\u2010CAD Programs on Parallel Inference Machine. Proc. FGCS'92 (July1992)."},{"key":"e_1_2_1_6_2","volume-title":"Solving Problems On Concurrent Processors, 1","author":"Fox G.","year":"1988"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"M.FuruichiK.TakiandN.Ichiyoshi.A multilevel load balancing scheme for OR\u2010parallel exhaustive search programs on the Multi\u2010PSI. Proc. 2nd ACM SIGPLAN Sympo. PPOPP'90 pp.50\u201359(1990).","DOI":"10.1145\/99164.99170"},{"issue":"11","key":"e_1_2_1_8_2","first-page":"1366","article-title":"One Method for Wire Segment Searching with High Routing Efficiency","volume":"26","author":"Hitoshi K.","year":"1985","journal-title":"Journal of the Information Processing Society of Japan"},{"issue":"3","key":"e_1_2_1_9_2","first-page":"387","article-title":"Parallel Logic Simulation in Virtual Time","volume":"33","author":"Matsumoto Y.","year":"1993","journal-title":"Journal of the Information Society of Japan"},{"key":"e_1_2_1_10_2","unstructured":"Y.MatsumotoandK.Taki. Parallel Logic Simulator Based on Time Warp and its Evaluation. Proc. FGCS'92 (June1992)."},{"key":"e_1_2_1_11_2","unstructured":"K.Nakajima Y.Inamura N.Ichiyoshi K.RokusawaandT.Chikayama.Distributed Implementation of KL1 on the Multi\u2010PSI\/V2. Proc. Sixth Int. Conf. on Logic Programming pp.436\u2013451(June1989)."},{"key":"e_1_2_1_12_2","unstructured":"K.NakajimaandN.Ichiyoshi.Evaluation of Inter\u2010processor Communication in the KL1 Implementation on the Multi\u2010PSI. ICOT Technical Report TR\u2010531 (1990)."},{"key":"e_1_2_1_13_2","unstructured":"H.NakashimaandK.Nakajima. Hardware Architecture of the Sequential Inference Machine: PSI\u2010II. Proc. 1987 Symposium on Logic Programming pp.104\u2013113(Sep.1987)."},{"key":"e_1_2_1_14_2","unstructured":"K.Nitta K.TakiandN.Ichiyoshi. Experimental Parallel Inference Software. Proc. FGCS'92 (June1992)."},{"key":"e_1_2_1_15_2","unstructured":"S.Onishi Y.Matsumoto K.NakajimaandK.Taki.Evaluation of the KL1 Language System on the Multi\u2010PSI in Proc. Workshop on Parallel Implementation of Languages for Symbolic Computation (July 1990) Also ICOT Technical Report TR\u2010585."},{"key":"e_1_2_1_16_2","first-page":"18","article-title":"An Efficient Termination Detection and Abortion Algorithm for Distributed Processing Systems","volume":"1","author":"Rokusawa K.","year":"1988","journal-title":"Proc. 1988 ICPP"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/72551.72555"},{"key":"e_1_2_1_18_2","unstructured":"Y.Takeda H.Nakashima K.Masuda T.ChikayamaandK.Taki.A Load Balancing Mechanism for Large Scale Multiprocessor Systems and its Implementation. Proc. FGCS'88 (Nov.1988)."},{"key":"e_1_2_1_19_2","first-page":"411","volume-title":"The Parallel Software Research and Development Tool: Multi\u2010PSI System. Programming of Future Generation Computers","author":"Taki K.","year":"1988"},{"key":"e_1_2_1_20_2","unstructured":"K.Taki. Parallel Inference Machine PIM. Proc. FGCS'92 (June1992)."},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"K.Ueda.Guarded Horn Clauses: A Parallel Logic Programming Language with the Concept of a Guard. ICOT Technical Report TR\u2010208 (1986).","DOI":"10.1007\/3-540-16479-0_17"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/33.6.494"},{"key":"e_1_2_1_23_2","first-page":"83","article-title":"The Implementation and Evaluation of the Shortest Path Problem on the Multi\u2010PSI","volume":"89","author":"Wada K.","year":"1989","journal-title":"Research Data on Information Processing Computer Architecture"},{"key":"e_1_2_1_24_2","unstructured":"K.WadaandN.Ichiyoshi.A study of mapping locally message exchanging algorithms on a loosely\u2010coupled multiprocessor. ICOT Technical Report TR\u2010587 (1990)."}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690250102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690250102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T05:56:07Z","timestamp":1698126967000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690250102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1994,1]]}},"alternative-id":["10.1002\/scj.4690250102"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690250102","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,1]]}}}