{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T17:11:27Z","timestamp":1697908287908},"reference-count":15,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":7749,"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":[[1986,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the VLSI circuit, the area occupied by the circuit and the time required for computation are important measures of evaluation. Thompson, Brent and Kung have proposed a VLSI model to evaluate the VLSI circuit by the area <jats:italic>A<\/jats:italic> and the computation time <jats:italic>T.<\/jats:italic> It is an important problem to examine the change of the area and the computation time when a certain practical assumption is imposed on the VLSI model. This paper shows that when an assumption that the input and the output are connected at the boundary of the circuit (called boundary\u2010layout assumption) is imposed on the VLSI model, relations <jats:italic>AT<\/jats:italic> = \u03c9(max(<jats:italic>n, m<\/jats:italic>)) and <jats:italic>AT<\/jats:italic><jats:sup>a<\/jats:sup> = \u03c9(max(<jats:italic>n, m<\/jats:italic>)[max(log <jats:italic>N<\/jats:italic>, log <jats:italic>M<\/jats:italic>)]<jats:italic>a<\/jats:italic>) (\u03b1 &gt; 1) are produced for the nontrivial class of <jats:italic>n<\/jats:italic>\u2010input, <jats:italic>m<\/jats:italic>\u2010output logic functions. Above, <jats:italic>N<\/jats:italic> is the maximum of <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub>, \u2026, <jats:italic>N<\/jats:italic><jats:sub>m<\/jats:sub>, where <jats:italic>Ni<\/jats:italic> is the number of inputs on which the <jats:italic>i<\/jats:italic>th output depends, and <jats:italic>Mj<\/jats:italic> is the maximum of <jats:italic>M<\/jats:italic>1, \u2026, <jats:italic>Mn<\/jats:italic>, where <jats:italic>Mj<\/jats:italic> is the number of outputs which depends on the <jats:italic>j<\/jats:italic>th input. When the boundary\u2010layout assumption is not imposed, <jats:italic>AT<\/jats:italic>\u03b1 = \u03c9(max(<jats:italic>n, m<\/jats:italic>){max(log <jats:italic>N<\/jats:italic>, log <jats:italic>M<\/jats:italic>)}\u03b1\u20101) (\u03b1 \u2265 1) holds. Consequently, for this class of functions, the boundary\u2010layout assumption properly affects <jats:italic>AT<\/jats:italic>\u03b1 (\u03b1 \u2265 1). It is shown also by an actual example that there exist functions which achieve the lower bounds.<\/jats:p>","DOI":"10.1002\/scj.4690170608","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T12:03:35Z","timestamp":1183809815000},"page":"67-75","source":"Crossref","is-referenced-by-count":1,"title":["Area\u2010time complexity on a vlsi model with boundary layout assumption"],"prefix":"10.1002","volume":"17","author":[{"given":"Koichi","family":"Wada","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ken'Ichi","family":"Hagihara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nobuki","family":"Tokura","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":"R.P.BrentandH.T.Kung. The area\u2010time complexity of binary multiplication Tech Rep. CMU\u2010CS\u201379\u2013136 Dept. of Comput. Sci. Carnegie\u2010Mellon Univ. (July1979)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90034-4"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90021-1"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"B.ChazelleandL.Monier. A model of computation for VLSI with related complexity results Tech. Rep. CMU\u2010CS\u201381\u2013107 Dept.of Comput. Sci. Carnegie\u2010Mellon Univ. (Feb.1981).","DOI":"10.1145\/800076.802485"},{"key":"e_1_2_1_6_2","first-page":"709","article-title":"Effects of practical assumption in area complexity of VLSI computation time","volume":"12","author":"Hagihara K.","year":"1983","journal-title":"Trans. I.E.C.E., Japan (Section E), z"},{"key":"e_1_2_1_7_2","volume-title":"Graph Theory","author":"Harary F.","year":"1971"},{"key":"e_1_2_1_8_2","unstructured":"H. T.Kung.Let's design algorithms for VLSI systems Tech. Rep. CMU\u2010CS\u201379\u2013151 Dept. of Comput. Sci. Carnegie\u2010Mellon Univ. (Jan.1979)."},{"key":"e_1_2_1_9_2","volume-title":"Introduction to VLSI Systems","author":"Mead C. A.","year":"1979"},{"key":"e_1_2_1_10_2","unstructured":"J.Savage. Area\u2010time tradeoffs for matrix multiplication and related problems in VLSI models Tech. Rep. CS\u201350 Dept. of Comput. Sci. Brown Univ. (Aug.1979)."},{"key":"e_1_2_1_11_2","unstructured":"C. D.Thompson. A complexity theory for VLSI Tech. Rep. CMU\u2010CS\u201380\u2013140 Dept. of Comput. Sci. Carnegie\u2010Mellon Univ. (Aug.1980)."},{"key":"e_1_2_1_12_2","unstructured":"K.Wada K.HagiharaandN.Tokura. The complexity of logic function in terms of the area\u2010time product Tech. Rep. I.E.C.E. Japan Q\u201377 (Nov.1981)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676463"},{"key":"e_1_2_1_14_2","first-page":"504","article-title":"Construction of logic function with optimum area\u2010time product","volume":"4","author":"Wada K.","year":"1984","journal-title":"Trans. (D) I.E.C.E."},{"key":"e_1_2_1_15_2","first-page":"1080","article-title":"Area of logic function in VLSI","volume":"8","author":"Yasuura K.","year":"1982","journal-title":"Trans. (D) I.E.C.E."},{"key":"e_1_2_1_16_2","unstructured":"K.YasuuraandYajima. Complexity of logic function realizing regular logic function sequence Winter LA Symposium (Feb.1983)."}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690170608","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690170608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T17:00:13Z","timestamp":1697821213000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690170608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1]]},"references-count":15,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1986,1]]}},"alternative-id":["10.1002\/scj.4690170608"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690170608","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,1]]}}}