Recursos de colección
Caltech Authors (143.226 recursos)
Repository of works by Caltech published authors.
Group = Computer Science Technical Reports
Repository of works by Caltech published authors.
Group = Computer Science Technical Reports
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....
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.
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.
[none]
[none]
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...
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...
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.
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.
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.
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.
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...
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...
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...
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.
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...
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.
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.
Mosteller, R. C.
N/A
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...