Recursos de colección

Caltech Authors (147.820 recursos)

Repository of works by Caltech published authors.

Group = Computer Science Technical Reports

Mostrando recursos 1 - 20 de 489

  1. Quantifying Near-Threshold CMOS Circuit Robustness

    Keller, Sean; Bhargav, Siddharth S.; Moore, Chris; Martin, Alain J.
    In order to build energy efficient digital CMOS circuits, the supply voltage must be reduced to near-threshold. Problematically, due to random parameter variation, supply scaling reduces circuit robustness to noise. Moreover, the effects of parameter variation worsen as device dimensions diminish, further reducing robustness, and making parameter variation one of the most significant hurdles to continued CMOS scaling. This paper presents a new metric to quantify circuit robustness with respect to variation and noise along with an efficient method of calculation. The method relies on the statistical analysis of standard cells and memories resulting an an extremely compact representation of robustness data....

  2. An Axiomatic Definition of Synchronization Primitives

    Martin, Alain J.
    The semantics of a pair of synchronization primitives is characterized by three fundamental axioms: boundedness, progress, and fairness. The class of primitives fulfilling the three axioms is semantically defined. Unbuffered communication primitives, the symmetrical P and V operations, and the usual P and V operations are proved to be the three instances of this class. The definitions obtained are used to prove a series of basic theorems on mutual exclusion, producer-consumer coupling, deadlock, and linear and circular arrangements of communicating buffer-processes. An implementation of P and V operations fulfilling the axioms is proposed.

  3. 25 Years Ago: The First Asynchronous Microprocessor

    Martin, Alain J.
    Twenty-five years ago, in December 1988, my research group at Caltech submitted the world’s first asynchronous (“clockless”) microprocessor design for fabrication to MOSIS. We received the chips in early 1989; testing started in February 1989. The chips were found fully functional on first silicon. The results were presented at the Decennial Caltech VLSI Conference in March of the same year. The first entirely asynchronous microprocessor had been designed and successfully fabricated. As the technology finally reaches industry, and with the benefit of a quarter-century hindsight, here is a recollection of this landmark project.

  4. Proceedings of the Caltech Conference on Very Large Scale Integration, held at the California Institute of Technology 22 - 24 January 1979 ; Organized by the Caltech Computer Science Department and the Caltech Industrial Associates Office


  5. Proceedings of the Second Caltech Conference on Very Large Scale Integration, held at the California Institute of Technology 19-21 January, 1981 ; Organized by the Caltech Computer Science Department and the Caltech Industrial Associates Office, and sponsored by Caltech Industrial Associates and the National Science Foundation


  6. RIOT: a simple graphical assembly tool

    Trimberger, Stephen; Rowson, Jim
    Errors in the chip assembly process are harder to find than errors in cell design, since they belong to no specific part of the design, but rather to the assembly as a whole. Assembly errors are more costly than call design errors also, since they often go unnoticed until late in the design cycle. Interactive graphic tools typically require that assembly be done with primitive graphical operations, which are inappropriate far the assembly task. Language-based tools give more powerful assembly operations, but remove the two dimensional view of the chip necessary to visualize many assembly operations. Riot is a simple Interactive graphical tool...

  7. Concurrent fault simulation of MOS digital circuits

    Schuster, Michael D.; Bryant, Randal E.
    The concurrent fault simulation technique is widely used to analyse the behavior of digital circuits in the presence of faults. We show how this technique can be applied to metal-oxide-semiconductor (MOS) digital circuits when modeled at the switch-level as a set of charge storage nodes connected by bidirectional transistor switches. The algorithm we present is capable of analysing the behavior of a wide variety of MOS circuit failures, such as stuck-at-zero or stuck-at-one nodes, stuck-open or stuck-closed transistors, or resistive opens or shorts. We have implemented a fault simulator FMOSSIM based on this algorithm. The capabilities and the peformance of this program demonstrate the advantages of combining...

  8. New techniques for ray tracing procedurally defined objects

    Kajiya, James T.
    We present new algorithms for efficient ray tracing of three procedurally defined objects: fractal surfaces, prisms, and surfaces of revolution. The fractal surface algorithm performs recursive subdivision adaptively. Subsurfaces which cannot intersect a given ray are culled from further consideration. The prism algorithm transforms the three dimensional ray-surface intersection problem into a two dimensional ray-curve intersection problem, which is solved by the method of strip trees. The surface of revolution algorithm transforms the three dimensional ray-surface intersection problem into a two dimensional curve-curve intersection problem, which again is solved by strip trees.

  9. VLSI algorithms for Doolittle's, Crout's, and Cholesky's methods

    Johnsson, Lennart
    In order to take full advantage of the emerging VLSI technology it is required to recognize its limited communication capability and structure algorithms accordingly. In this paper concurrent algorithms for the methods of Crout, Doolittle and Cholesky are described and compared with concurrent algorithms for Gauss' , Given's and Householder's method. The effect of pipe lining the computations in two dimensional arrays is given special attention.

  10. Minimum propagation delays in VLSI

    Mead, Carver; Rem, Martin
    In this paper we demonstrate that it is possible to achieve propagation delays that are logarithmic in the lengths of the wires, provided the connection pattern is designed to meet rather strong constraints. These constraints are, in effect, satisfied only by connection patterns that exhibit a hierarchical structure. We also show that, even at the ultimate physical limits of the technology, the propagation for reasonably sized VLSI chips is dominated by these considerations, rather than by the speed of light.

  11. A new channel routing algorithm

    Chan, Wan S.
    This paper presents a new algorithm for solving the two-layer channel routing problem with doglegging. Based on a set of intuitive and reasonable heuristics, the algorithm tries to obtain a channel routing configuration with a minimum number of tracks. For every benchmark problem tested, the algorithm gives a routing configuration with the smallest number of tracks reported in the literature.

  12. A mathematical approach to modelling the flow of data and control in computational networks

    Johnsson, Lennart; Cohen, Danny
    This paper proposes a mathematical formalism for the synthesis and qualitative analysis of computational networks that treats data and control in the same manner. Expressions in this notation are given a direct interpretation in the implementation domain. Topology, broadcasting, pipelining, and similar properties of implementations can be determined directly from the expressions. This treatment of computational networks emphasizes the space/time tradeoff of implementations. A full instantiation in space of most computational problems is unrealistic, even in VLSI (Finnegan [4]). Therefore, computations also have to be at least partially instantiated in the time domain, requiring the use of explicit control mechanisms, which typically cause...

  13. An integrative approach to engineering data and automatic project coordination

    Segal, Richard L.
    A new approach to integration of automation environments is necessary in order to overcome some fundamental limitations of current methods. The most common request for integration comes when an organization finds itself with many design systems and representations most of which cannot communicate directly. Solutions to this problem have required either a proliferation of translations between systems, or the provision of a central data base with which all applications must communicate. Another aspect of integration is the provision of mechanisms which keep track of the status of design. The working - release method along with version control techniques is well known...

  14. Pipelined linear equation solvers and VLSI

    Johnsson, Lennart
    Many of the commonly used methods for solution of linear systems of equations on sequential machines can be given a concurrent formulation. The concurrent algorithms take advantage of independence of operations in order to reduce the time complexity of the methods. During the course of computations specified by the algorithm data has to be routed to the various places of computation. Pipelining can be used to avoid broadcasting in VLSI arrays for computation. Pipelining will in general allow for a reduced cycle time but may force data to be spread out in time, as is the case for Gaussian elimination. What the...

  15. On the Correctness of Sliding Window Protocols

    Van de Snepscheut, Jan L. A.
    In this note some struggles with the sliding window protocol and the special case known as the alternating bit protocol, are reported. We try to give a correctness proof, and discover that we cannot do so for one of the versions of the sliding window protocol. One may either require channels that satisfy stronger assumptions or, as we will do, adapt the protocol and stick to the weaker assumptions. The alternating bit protocol can be traced back to [Bartlett]. We have been unable to trace back the origins of the sliding window protocols; [Stenning] discusses one of the versions and lists networks using related protocols.

  16. Toward a mathematical theory of perception

    Kajiya, James Thomas
    A new technique for the modelling of perceptual systems called formal modelling is developed. This technique begins with qualitative observations about the perceptual system, the so-called perceptual symmetries, to obtain through mathematical analysis certain model structures which may then be calibrated by experiment. The analysis proceeds in two different ways depending upon the choice of linear or nonlinear models. For the linear case, the analysis proceeds through the methods of unitary representation theory. It begins with a unitary group representation on the image space and produces what we have called the fundamental structure theorem. For the nonlinear case, the analysis makes essential use of infinite-dimensional manifold theory. It begins with a Lie group action...

  17. A Comparison of MOS PLAs

    Trimberger, Stephen
    This paper discusses Pl.A designs in three MOS technologies: NMOS, CMOS/SOS and CMOS-Bulk. The purpose of this paper is not to introduce a new and exciting PLA design, nor is it to recommend one fabrication technology over another. Its purpose is to use PLAs as a standard, hopefully familiar layout strategy so that new designers can get a better understanding of the advantages and disadvantages of all three technologies from a designer's viewpoint. It is hoped that this paper will provide more data to those who must select a technology for their integrated circuit fabrication.

  18. A Computational Array for the QR-Method

    Johnsson, Lennart
    The QR-method is a method for the solution of linear system of equations. The matrix R is upper triangular and Q is a unitary matrix. In equation solving Q is not always computed explicitly. The matrix R can be obtained by applying a sequence of unitary transformations to the matrix defining the system of equations. Householder's method or Given's method can be used to determine unitary transformation matrices. This paper describes a concurrent algorithm and corresponding array for computing the triangular matrix R by Householder transformations. Particular attention is given to issues such as broadcasting and pipelining.

  19. An Experimental Composition Tool

    Mosteller, R. C.

  20. Ray tracing parametric patches

    Kajiya, James T.
    This paper describes an algorithm that uses ray t racing techniques to display bivariate polynomial surface patches. A new intersection algorithm is developed which uses ideas from algebraic geometry to obtain a numerical procedure for finding the intersection of a ray and a patch without subdivision. The algorithm may use complex coordinates for the (u, v)-parameters of the patches. The choice of these coordinates makes the computations more uniform, so that there are fewer special cases to be considered. In particular, the appearance and disappearance of silhouette edges can be handled quite naturally. The uniformity of these techniques may be suitable for...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.