{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:19:33Z","timestamp":1725495573804},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540563204"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/3-540-56320-2_57","type":"book-chapter","created":{"date-parts":[[2007,11,19]],"date-time":"2007-11-19T10:53:33Z","timestamp":1195469613000},"page":"155-174","source":"Crossref","is-referenced-by-count":4,"title":["Horizons of parallel computation"],"prefix":"10.1007","author":[{"given":"Gianfranco","family":"Bilardi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franco P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"9_CR1","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0216053","volume":"16","author":"H. Alt","year":"1987","unstructured":"Alt, H., Hagerup, T., Mehlhorn, K., Preparata, F.P.: Simulation of idealized parallel computers on more realistic ones, S1AM Journal on Computing, 16, 5 (1987) 808\u2013835","journal-title":"S1AM Journal on Computing"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Bay, P., Bilardi, G.: Deterministic on-line routing on area-universal networks. Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 297\u2013306, October 1990","DOI":"10.1109\/FSCS.1990.89548"},{"issue":"8","key":"9_CR3","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/135226.135227","volume":"35","author":"G. Bell","year":"1992","unstructured":"Bell, G.: A teraflop before its time, Comm. of the ACM, 35, 8 (1992), 26\u201347","journal-title":"Comm. of the ACM"},{"issue":"2","key":"9_CR4","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S.N. Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems, Journal of Computer and Systems Sciences, 28, 2 (1984), 300\u2013342","journal-title":"Journal of Computer and Systems Sciences"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01840437","volume":"1","author":"G. Bilardi","year":"1986","unstructured":"Bilardi, G., Preparata, F. P.: Area-time lower-bound techniques with application to sorting, Algorithmica, 1, (1986), 65\u201391","journal-title":"Algorithmica"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1109\/JSSC.1982.1051799","volume":"17","author":"G. Bilardi","year":"1982","unstructured":"Bilardi, G., Pracchi, M., Preparata, F.P.: A critique of network speed in VLSI models of computation, IEEE Journal Solid-State Circuits, 17 (1982), 696\u2013702","journal-title":"IEEE Journal Solid-State Circuits"},{"issue":"2","key":"9_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R.P. Brent","year":"1974","unstructured":"Brent, R.P.: The parallel evaluation of general arithmetic expressions, Journal of the ACM, 21, 2 (1974)201\u2013206","journal-title":"Journal of the ACM"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1145\/3828.3834","volume":"32","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B., Monier, L.: A model of computation for VLSI with related complexity results, Journal of the ACM, 32, (1985) 573\u2013588","journal-title":"Journal of the ACM"},{"issue":"3","key":"9_CR9","first-page":"308","volume":"9","author":"S.A. Cook","year":"1974","unstructured":"Cook, S.A.: An observation of time-storage tradeoff, JCSS, 9, 3, (1974)308\u2013316","journal-title":"JCSS"},{"key":"9_CR10","first-page":"99","volume":"27","author":"S.A. Cook","year":"1981","unstructured":"Cook, S.A.: Towards a complexity theory of synchronous parallel computation, Enseign. Math. 27, (1981) 99\u2013124","journal-title":"Enseign. Math."},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"Cook, S.A., Reckhow, R.A.: Time bounded random access machines, Journal of Comput. System Science, 7 (1973) 354\u2013375","journal-title":"Journal of Comput. System Science"},{"issue":"12","key":"9_CR12","doi-asserted-by":"publisher","first-page":"1901","DOI":"10.1109\/PROC.1966.5273","volume":"54","author":"M.J. Flynn","year":"1966","unstructured":"Flynn, M.J.: Very high-speed computing systems, Proc. IEEE 54, 12, (1966), 1901\u20131909","journal-title":"Proc. IEEE"},{"key":"9_CR13","unstructured":"Greenberg, R. I., Leiserson, C.E.: Randomized routing on fat-trees. In Micali, S., editor, Randomness and Computation, 345\u2013374. JAI Press, Inc., 1989."},{"key":"9_CR14","unstructured":"Herley, K., Bilardi, G.: Deterministic simulations of PRAMs on bounded-degree networks, Proceedings of the 26th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, (1988), 1084\u20131093"},{"issue":"4","key":"9_CR15","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1145\/48014.350550","volume":"35","author":"A. Karlin","year":"1988","unstructured":"Karlin, A., Upfal, E.: Parallel hashing \u2014 an efficient implementation of shared memory, Journal of the ACM, 35, 4(1988) 876\u2013892","journal-title":"Journal of the ACM"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Ramachandran, V.: Parallel algorithms for shared-memory machines, Handbook of Theoretical Computer Science: Algorithms and Complexity (J.v. Leeuwen, ed.) Elsevier-The MIT Press, 1990","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(90)90192-K","volume":"71","author":"C.P. Kruskal","year":"1990","unstructured":"Kruskal, C.P., Rudolf, L., Snir, M.: A complexity theory of efficient parallel algorithms, Theoretical Computer Science, 71 (1990) 95\u2013132","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"9_CR18","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1109\/MC.1982.1653825","volume":"15","author":"H.T. Kung","year":"1982","unstructured":"Kung, H.T.: Why systolic architectures? Computer Magazine, 15, 1, (1982), 37\u201346","journal-title":"Computer Magazine"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: The Circuit Value problem is logspace complete for P, SIGACT News 7, 1(1975), 18\u201320","journal-title":"SIGACT News"},{"key":"9_CR20","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes, Morgan Kaufmann, 1991"},{"key":"9_CR21","volume-title":"Ph.D. dissertation","author":"F.T. Leighton","year":"1981","unstructured":"Leighton, F.T.: Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI, Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, Massachusetts, September 1981"},{"issue":"10","key":"9_CR22","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1109\/TC.1985.6312192","volume":"C-34","author":"C.E. Leiserson","year":"1985","unstructured":"Leiserson, C.E.: Fat-trees: Universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, C-34, 10 (1985) 892\u2013900","journal-title":"IEEE Transactions on Computers"},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01762110","volume":"3","author":"C.E. Leiserson","year":"1988","unstructured":"Leiserson, C.E., Maggs, B.M.: Communication-efficient parallel algorithms for distributed random-access machines. Algorithmica, 3 (1988) 53\u201377","journal-title":"Algorithmica"},{"key":"9_CR24","unstructured":"Mead, C., Conway, L.: Introduction to VLSI Systems, Addison-Wesley, 1980"},{"issue":"4","key":"9_CR25","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF00264615","volume":"21","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K., Vishkin, U.: Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, 21, 4 (1984) 339\u2013374","journal-title":"Acta Informatica"},{"issue":"5","key":"9_CR26","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1109\/TC.1977.1674863","volume":"C-26","author":"M.C. Pease","year":"1977","unstructured":"Pease, M.C.: The indirect binary n-cube microprocessor array, IEEE Transactions on Computers, C-26, 5, (1977), 458\u2013473","journal-title":"IEEE Transactions on Computers"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Pippenger, N.: On simultaneous resource bounds, Proceedings of the 20th IEEE Symposium Foundation of Computer Sicence, (1979) 307\u2013311","DOI":"10.1109\/SFCS.1979.29"},{"issue":"5","key":"9_CR28","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1145\/358645.358660","volume":"24","author":"F.P. Preparata","year":"1981","unstructured":"Preparata, F.P., Vuillemin, J.: The cube-connected cycles: A versatile network for parallel computation, Communications of the ACM, 24, 5 (1981)300\u2013309","journal-title":"Communications of the ACM"},{"key":"9_CR29","doi-asserted-by":"crossref","unstructured":"Ranade, A.G.: How to emulate shared memory, Proceedings of the 28th Annual Symposium on the Foundations of Computer Science,(1987), 185\u2013192","DOI":"10.1109\/SFCS.1987.32"},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"Rosenberg, A.L.: Three-dimensional integrated circuitry. In H.T. Kung, B. Sproull, and G. Steele, editors, Proceedings of the CMU Conference on VLSI Systems and Computations, Computer Science Press (1981), 69\u201380","DOI":"10.1007\/978-3-642-68402-9_9"},{"key":"9_CR31","first-page":"241","volume":"298","author":"B. J. Smith","year":"1981","unstructured":"Smith, B. J.: Architecture and applications of the HEP multiprocessor system, Signal Processing IV, 298, (1981), 241\u2013248","journal-title":"Signal Processing IV"},{"key":"9_CR32","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1146\/annurev.cs.01.060186.001445","volume":"1","author":"L. Snyder","year":"1986","unstructured":"Snyder, L.: Type architectures, shared memory, and the corollary of modest potential, Annual Review of Computer Science, 1 (1986) 289\u2013317","journal-title":"Annual Review of Computer Science"},{"key":"9_CR33","unstructured":"Thompson, C.D.: A Complexity Theory for VLSI. Ph.D. dissertation, Carnegie-Mellon University, August 1980"},{"issue":"1","key":"9_CR34","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/7531.7926","volume":"34","author":"E. Upfal","year":"1987","unstructured":"Upfal, E., Wigderson, A.: How to share memory in a distributed system, Journal of the ACM, 34, 1(1987) 116\u2013127","journal-title":"Journal of the ACM"},{"issue":"8","key":"9_CR35","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L.G. Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation, Communications of the ACM, 33, 8 (1990), 103\u2013111","journal-title":"Communications of the ACM"},{"key":"9_CR36","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: General purpose parallel architectures, Handbook for Theor. Computer Science [J.v. Leeuwen, ed.], Elsevier-MIT Press, 1990","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"issue":"2","key":"9_CR37","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"C-30","author":"L.G. Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits, IEEE Transactions on Computers, C-30, 2, (1981) 135\u2013140","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","Future Tendencies in Computer Science, Control and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56320-2_57.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T00:49:08Z","timestamp":1619570948000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56320-2_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540563204"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-56320-2_57","relation":{},"subject":[]}}