ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Digital Library logoTake a look at the new version of this page: [ beta version ]. Tell us what you think.
A complexity theory for VLSI
 
Purchase a copyPurchase a copy
Source
Pages: 148  
Year of Publication: 1980
Order Number:AAI8100621
Author
Clark David Thompson
Publisher
Carnegie Mellon University  Pittsburgh, PA, USA
Bibliometrics
Downloads (6 Weeks): n/a,   Downloads (12 Months): n/a,   Citation Count: 66
Additional Information:

cited by   collaborative colleagues  

Tools and Actions: Review this Doctoral Thesis  

CITED BY  67
Gloria Kissin, Upper and lower bounds on switching energy in VLSI, Journal of the ACM (JACM), v.38 n.1, p.222-254, Jan. 1991
M. T. Raghunath , A. Ranade, Designing interconnection networks for multi-level packaging, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.772-781, December 1993, Portland, Oregon, United States
Andrew C. Yao, The entropic limitations on VLSI computations(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.308-311, May 11-13, 1981, Milwaukee, Wisconsin, United States
Gloria Kissin, Measuring energy consumption in VLSI circuits: A foundation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.99-104, May 05-07, 1982, San Francisco, California, United States
C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States
Shimon Even , Roni Kupershtok, Layout area of the hypercube: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.366-371, January 06-08, 2002, San Francisco, California
Michael J. Quinn , Narsingh Deo, Parallel graph algorithms, ACM Computing Surveys (CSUR), v.16 n.3, p.319-348, Sept. 1984
Sujit Dey , Pradip K. Srimani, Parallel VLSI computation of all shortest paths in a graph, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.373-379, February 1988, Atlanta, Georgia, United States
Juraj Karhuäki , Sebastian Seibert , Juhani Karhumaki , Hartmut Klauck , Georg Schnitger, Communication complexity method for measuring nondeterminism in finite automata, Information and Computation, v.172 n.2, p.202-217, January 29, 2002
Alok Aggarwal , Ashok Chandra , Prabhakar Raghavan, Energy consumption in VLSI circuits, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.205-216, May 02-04, 1988, Chicago, Illinois, United States
Yefim Dinitz , Shimon Even , Roni Kupershtok , Maria Zapolotsky, Some compact layouts of the butterfly, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.54-63, June 27-30, 1999, Saint Malo, France
Mikhail J. Atallah , S. Rao Kosaraju, Graph Problems on a Mesh-Connected Processor Array, Journal of the ACM (JACM), v.31 n.3, p.649-667, July 1984
Yosee Feldman , Ehud Shapiro, Spatial machines: a more realistic approach to parallel computation, Communications of the ACM, v.35 n.10, p.60-73, Oct. 1992
G. Bilardi , F. P. Preparata, Size-time complexity of Boolean networks for prefix computations, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.436-442, January 1987, New York, New York, United States
Bernard Chazelle , Louis Monier, A model of computation for VLSI with related complexity results, Journal of the ACM (JACM), v.32 n.3, p.573-588, July 1985
Bernard Chazelle , Louis Monier, A model of computation for VLSI with related complexity results, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.318-325, May 11-13, 1981, Milwaukee, Wisconsin, United States
Micah Adler , John Byers, AT2 bounds for a class of VLSI problems and string matching, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.140-146, June 27-29, 1994, Cape May, New Jersey, United States
A Aggarwal, Tradeoffs for VLSI models with subpolynomial delay, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.59-68, May 06-08, 1985, Providence, Rhode Island, United States
M. R. Samatham , D. K. Pradhan, A multiprocessor network suitable for single-chip VLSI implementation, ACM SIGARCH Computer Architecture News, v.12 n.3, p.328-339, June 1984
Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981
A Siegel, Aspects of information flow in VLSI circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.448-459, May 28-30, 1986, Berkeley, California, United States
G. Bilardi , F. P. Preparata, Size-time complexity of Boolean networks for prefix computations, Journal of the ACM (JACM), v.36 n.2, p.362-382, April 1989
John J. Granacki , Alice C. Parker, The effect of register-transfer design tradeoffs on chip area and performance, Proceedings of the 20th conference on Design automation, p.419-424, June 27-29, 1983, Miami Beach, Florida, United States
P Raghavan , C D Thompson, Provably good routing in graphs: regular arrays, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.79-87, May 06-08, 1985, Providence, Rhode Island, United States
Paul Bay , Gianfranco Bilardi, Deterministic on-line routing on area-universal networks, Journal of the ACM (JACM), v.42 n.3, p.614-640, May 1995
Aythan Avior , Tiziana Calamoneri , Shimon Even , Ami Litman , Arnold L. Rosenberg, A tight layout of the butterfly network, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.170-175, June 24-26, 1996, Padua, Italy
Chi-Hsiang Yeh , Behrooz Parhami , E. A. Varvarigos , H. Lee, VLSI layout and packaging of butterfly networks, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.196-205, July 09-13, 2000, Bar Harbor, Maine, United States
Richard Cole , Alan Siegel, Optimal VLSI circuits for sorting, Journal of the ACM (JACM), v.35 n.4, p.777-809, Oct. 1988
Daniel Kleitman , Frank Thomson Leighton , Margaret Lepley , Gary L. Miller, New layouts for the shuffle-exchange graph(Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.278-292, May 11-13, 1981, Milwaukee, Wisconsin, United States
Nian-Feng Tzeng, Design of a highly reliable cube-connected cycles architecture, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.776-785, November 18-22, 1991, Albuquerque, New Mexico, United States
Frank Thomson Leighton, A layout strategy for VLSI which is provably good (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.85-98, May 05-07, 1982, San Francisco, California, United States
Dina Bitton , David J. DeWitt , David K. Hsaio , Jaishankar Menon, A taxonomy of parallel sorting, ACM Computing Surveys (CSUR), v.16 n.3, p.287-318, Sept. 1984
Gianfranco Bilardi , Kieran T. Herley , Andrea Pietracaprina , Geppino Pucci , Paul Spirakis, BSP vs LogP, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.25-32, June 24-26, 1996, Padua, Italy
Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States
T. N. Mudge , B. A. Makrucki, Probabilistic analysis of a crossbar switch, ACM SIGARCH Computer Architecture News, v.10 n.3, p.311-320, April 1982
Jonathan W. Greene , Abbas El Gamal, Configuration of VLSI Arrays in the Presence of Defects, Journal of the ACM (JACM), v.31 n.4, p.694-717, Oct. 1984
G. L. Miller , W. Thurston, Separators in two and three dimensions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.300-309, May 13-17, 1990, Baltimore, Maryland, United States
Ronald I. Greenberg , Lee Guan, On the area of hypercube layouts, Information Processing Letters, v.84 n.1, p.41-46, 16 October 2002
N. F. Tzeng, Reconfiguration and Analysis of a Fault-Tolerant Circular Butterfly Parallel System, IEEE Transactions on Parallel and Distributed Systems, v.4 n.8, p.855-863, August 1993
Allan L. Fisher , H. T. Kung, Synchronizing large VLSI processor arrays, ACM SIGARCH Computer Architecture News, v.11 n.3, p.54-58, June 1983
Guihai Chen , Francis C. M. Lau, Tighter Layouts of the Cube-Connected Cycles, IEEE Transactions on Parallel and Distributed Systems, v.11 n.2, p.182-191, February 2000
Micah Adler , John W. Byers , Richard M. Karp, Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, United States
Bhabani P. Sinha , Pradip K. Srimani, A new parallel multiplication algorithm and its VLSI implementation, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.366-372, February 1988, Atlanta, Georgia, United States
Si-Qing Zheng, Compressed Tree Machines, IEEE Transactions on Computers, v.43 n.2, p.222-225, February 1994
Mary Mehrnoosh Eshaghian, Parallel Algorithms for Image Processing on OMC, IEEE Transactions on Computers, v.40 n.7, p.827-833, July 1991
Ronald I. Greenberg, The Fat-Pyramid and Universal Parallel Computation Independent of Wire Delay, IEEE Transactions on Computers, v.43 n.12, p.1358-1364, December 1994
Antonio Fernández , Kemal Efe, Efficient VLSI Layouts for Homogeneous Product Networks, IEEE Transactions on Computers, v.46 n.10, p.1070-1082, October 1997
B. P. Sinha , P. K. Srimani, Fast Parallel Algorithms for Binary Multiplication and their Implementation on Systolic Architectures, IEEE Transactions on Computers, v.38 n.3, p.424-431, March 1989
Kemal Efe , Antonio Fernández, Mesh-Connected Trees: A Bridge Between Grids and Meshes of Trees, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1281-1291, December 1996
Kemal Efe , Antonio Fernández, Products of Networks with Logarithmic Diameter and Fixed Degree, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.963-975, September 1995
G. Alia , E. Martinelli, On the Lower Bound to the VLSI Complexity of Number Conversion from Weighted to Residue Representation, IEEE Transactions on Computers, v.42 n.8, p.962-967, August 1993
F. Thomson Leighton , Bruce M. Maggs, Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks, IEEE Transactions on Computers, v.41 n.5, p.578-587, May 1992
N. T. Jarwala , D. K. Pradhan, TRAM: A Design Methodology for High-Performance, Easily Testable, Multimegabit RAMs, IEEE Transactions on Computers, v.37 n.10, p.1235-1250, October 1988
A. Agarwal, Limits on Interconnection Network Performance, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.398-412, October 1991
Giuseppe Alia , Enrico Martinelli, A VLSI Modulo m Multiplier, IEEE Transactions on Computers, v.40 n.7, p.873-878, July 1991
M. R. Samatham , D. K. Pradhan, The de Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI, IEEE Transactions on Computers, v.38 n.4, p.567-581, April 1989
Henry N. Adorna, 3-Party message complexity is better than 2-party ones for proving lower bounds on the size of minimal nondeterministic finite automata, Journal of Automata, Languages and Combinatorics, v.7 n.4, p.419-432, September 2002
Terry Tao Ye , Giovanni De Micheli , Luca Benini, Analysis of power consumption on switch fabrics in network routers, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
Binay Sugla , David A. Carlson, Extreme Area-Time Tradeoffs in VLSI, IEEE Transactions on Computers, v.39 n.2, p.251-257, February 1990
G. Bilardi , F. P. Preparata, A minimum area VLSI network for O(logn) time sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.64-70, December 1984
Ginfranco Bilardi , Scot W. Hornick , Majid Sarrafzadeh, Optimal VLSI architectures for multidimensional DFT (preliminary version), ACM SIGARCH Computer Architecture News, v.19 n.1, p.45-52, March 1991
Rahul Garg , Yogish Sabharwal, MPI and communication---Software routing and aggregation of messages to optimize the performance of HPCC randomaccess benchmark, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida
Sabyasachi Dey , Bhargab B. Bhattacharya , Malay K. Kundu , Arijit Bishnu , Tinku Acharya, A Co-processor for Computing the Euler Number of a Binary Image using Divide-and-Conquer Strategy, Fundamenta Informaticae, v.76 n.1-2, p.75-89, January 2007
Terry Tao Ye , Luca Benini , Giovanni De Micheli, Packetized On-Chip Interconnect Communication Analysis for MPSoC, Proceedings of the conference on Design, Automation and Test in Europe, p.10344, March 03-07, 2003
G. Bilardi , S. W. Hornick , M. Sarrafzadeh, Optimal VLSI architectures for multidimensional DFT, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.265-272, June 18-21, 1989, Santa Fe, New Mexico, United States
Sandeep N. Bhatt , Gianfranco Bilardi , Geppino Pucci, Area-time tradeoffs for universal VLSI circuits, Theoretical Computer Science, v.408 n.2-3, p.143-150, November, 2008
Aydin O. Balkan , Gang Qu , Uzi Vishkin, Mesh-of-trees and alternative interconnection networks for single-chip parallelism, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.17 n.10, p.1419-1432, October 2009
Collaborative Colleagues:
Clark David Thompson: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player