We describe the development of a one-credit course to promote AI literacy at the University of Texas at Austin. In response to a call for the rapid deployment of class that would serve a broad audience in Fall of 2023, we designed a 14-week seminar-style course that incorporated an interdisciplinary group of speakers who lectured on topics ranging from the fundamentals of AI to societal concerns including disinformation and employment. University students, faculty, and staff, and even community members outside of the University were invited to enroll in this online offering: The Essentials of AI for Life and Society. We collected feedback from course participants through weekly reflections and a final survey. Satisfyingly, we found that attendees reported gains in their AI literacy. We sought critical feedback through quantitative and qualitative analysis, which uncovered challenges in designing a course for this general audience. We utilized the course feedback to design a three-credit version of the course that is being offered in Fall of 2024. The lessons we learned and our plans for this new iteration may serve as a guide to instructors designing AI courses for a broad audience.

There are many applications for which we want to learn a latent scale for subjective properties, such as the excitement of a photo or the legibility of a font; however, obtaining human-labeled data is costly and time-consuming. One oft-used method for acquiring these labels, despite the cost being quadratic in the number of items, is the method of pairwise comparisons since this method minimizes the effect of biases and generally can be used effectively outside of a controlled environment.

Scientific ray tracing now can include realistic shading and material properties, but tracing rays of various depths to conclusion through partitioned data is inefficient. For such data, many ray scheduling methods have demonstrated improved rendering performance. However, synchronicity and non-adaptivity inherent in prior methods hinder further performance optimizations. In this paper, we attempt to relax these constraints. Specifically, we incorporate prediction models capable of dynamically adjusting levels of speculation in ray-data queries, making ray scheduling highly adaptable to a spectrum of scene characteristics. In addition, we organize rays in a tree of speculation nodes, where speculation is coordinated pairwise within a subtree of adaptive ray groups, facilitating concurrency and parallelism. Compared to prior non-predictive methods, we achieve up to three times higher throughput for volume and geometry rendering on a distributed system, making our method fit for both interactive and offline applications.

This paper presents a new Single Source Shortest Path (SSSP) algorithm for GPUs. Our key advancement is an improved work scheduler, which is central to the performance of SSSP algorithms. Previous GPU solutions for SSSP use simple work schedulers that can be implemented efficiently on GPUs but that produce low quality schedules. Such solutions yield poor work efficiency and can underutilize the hardware due to a lack of parallelism. Our solution introduces a more sophisticated work scheduler---based on a novel highly parallel approximate priority queue---that produces high quality schedules while being efficiently implementable on GPUs.

This paper proposes a methodology for exploiting approximate computing to reduce the time and energy requirements of Simultaneous Localization and Mapping (SLAM) algorithms, which are used in important problem domains like robotics and autonomous driving in which autonomous agents navigate through unknown environments. Algorithms for SLAM use sensors to probe the environment, integrate this information into a map of the surroundings (mapping), and determine where the agent is in this map (localization). Visual SLAM algorithms use cameras as sensors. They can be used in places where GPS information is not available, %such as inside buildings, but they have high computational requirements, leading to poor performance and high energy usage on embedded platforms.

Simultaneous Localization and Mapping (SLAM) is the problem of constructing a map of a mobile agent's environment while localizing the agent within the map. Dense SLAM algorithms perform reconstruction and localization at pixel granularity. These algorithms require a lot of computational power, which has hindered their use on low-power resource-constrained devices. Approximate computing can be used to speed up SLAM implementations as long as the approximations do not prevent the agent from navigating correctly through the environment. Previous studies of approximation in SLAM have assumed that the entire trajectory of the agent is known before the agent starts, and they have focused on offline controllers that set approximation knobs at the start of the trajectory. In practice, the trajectory is usually not known ahead of time, and allowing knob settings to change dynamically opens up more opportunities for reducing computation time and energy. In this paper, we describe SLAMBooster, an application-aware, online control system for dense SLAM that adaptively controls approximation knobs during the motion of the agent. SLAMBooster is based on a control technique called proportional-integral-derivative (PID) controller but our experiments showed this application-agnostic controller led to an unacceptable reduction in localization accuracy. To address this problem, SLAMBooster also exploits domain knowledge for controlling approximation by performing smooth surface detection and pose correction. We implemented SLAMBooster in the open-source SLAMBench framework and evaluated it on more than a dozen trajectories from both the literature and our own study. Our experiments show that on the average, SLAMBooster reduces the computation time by 72% and energy consumption by 35% on an embedded platform, while maintaining the accuracy of localization within reasonable bounds. These improvements make it feasible to deploy SLAM on a wider range of devices.

This paper extends the reach of General Purpose GPU programming by presenting a software architecture that supports efficient fine-grained synchronization over global memory. The key idea is to transform global synchronization into global communication so that conflicts are serialized at the thread block level. With this structure, the threads within each thread block can synchronize using low latency, high-bandwidth local scratchpad memory. To enable this architecture, we implement a scalable and efficient message passing library. Using Nvidia GTX 1080 ti GPUs, we evaluate our new software architecture by using it to solve a set of five irregular problems on a variety of workloads. We find that on average, our solutions improve performance over carefully tuned state-of-the-art solutions by 3.6×.

Approximate computing trades off accuracy of results for resources such as energy or computing time. There is a large and rapidly growing literature on approximate computing that has focused mostly on showing the benefits of approximate computing. However, we know relatively little about how to control approximation in a disciplined way. In this paper, we address the problem of controlling approximation for non-streaming programs that have a set of "knobs" that can be dialed up or down to control the level of approximation of different components in the program. We formulate this control problem as a constrained optimization problem, and describe a system called Capri that uses machine learning to learn cost and error models for the program, and uses these models to determine, for a desired level of approximation, knob settings that optimize metrics such as running time or energy usage. Experimental results with complex benchmarks from different problem domains demonstrate the effectiveness of this approach.

GPUs employ massive multithreading and fast context switching to provide high throughput and hide memory latency. Multithreading can Increase contention for various system resources, however, that may result In suboptimal utilization of shared resources. Previous research has proposed variants of throttling thread-level parallelism to reduce cache contention and improve performance. Throttling approaches can, however, lead to under-utilizing thread contexts, on-chip interconnect, and off-chip memory bandwidth. This paper proposes to tightly couple the thread scheduling mechanism with the cache management algorithms such that GPU cache pollution is minimized while off-chip memory throughput is enhanced. We propose priority-based cache allocation (PCAL) that provides preferential cache capacity to a subset of high-priority threads while simultaneously allowing lower priority threads to execute without contending for the cache. By tuning thread-level parallelism while both optimizing caching efficiency as well as other shared resource usage, PCAL builds upon previous thread throttling approaches, improving overall performance by an average 17% with maximum 51%.

Traditional evolved virtual creatures [1] are actuated using unevolved, uniform, invisible drives at joints between rigid segments. In contrast, this paper shows how such conventional actuators can be replaced by evolvable muscle drives that are a part of the creature's physical structure. Such a muscle-drive system replaces control intelligence with meaningful morphological complexity. For instance, the experiments in this paper show that control intelligence sufficient for locomotion or jumping can be moved almost entirely from the brain into the musculature of evolved virtual creatures.

Modern high performance processors require memory systems that can provide access to data at a rate that is well matched to the processor's computation rate. Common to such systems is the organization of memory into local high speed memory banks that can be accessed in parallel. Associative look up of values is made efficient through indexing instead of associative memories. These techniques lose effectiveness when data locations are not mapped uniformly to the banks or cache locations, leading to bottlenecks that arise from excess demand on a subset of locations. Address mapping is most easily performed by indexing the banks using a mod (2 N) indexing scheme, but such schemes interact poorly with the memory access patterns of many computations, making resource conflicts a significant memory system bottleneck. Previous work has assumed that prime moduli are the best choices to alleviate conflicts and has concentrated on finding efficient implementations for them. In this paper, we introduce a new scheme called Arbitrary Modulus Indexing (AMI) that can be implemented efficiently for all moduli, matching or improving the efficiency of the best existing schemes for primes while allowing great flexibility in choosing a modulus to optimize cost/performance trade-offs. We also demonstrate that, for a memory-intensive workload on a modern replay-style GPU architecture, prime moduli are not in general the best choices for memory bank and cache set mappings. Applying AMI to set of memory intensive benchmarks eliminates 98% of bank and set conflicts, resulting in an average speedup of 24% over an aggressive baseline system and a 64% average reduction in memory system replays at reasonable implementation cost.

This paper extends and evaluates a family of dynamic ray scheduling algorithms that can be performed in-situ on large distributed memory parallel computers. The key idea is to consider both ray state and data accesses when scheduling ray computations. We compare three instances of this family of algorithms against two traditional statically scheduled schemes. We show that our dynamic scheduling approach can render data sets that are larger than aggregate system memory and that cannot be rendered by existing statically scheduled ray tracers. For smaller problems that fit in aggregate memory but are larger than typical shared memory, our dynamic approach is competitive with the best static scheduling algorithm.

In the 19 years since Karl Sims' landmark publication on evolving virtual creatures (Sims, 1994), much of the future work he proposed has been implemented, having a significant impact on multiple fields including graphics, evolutionary computation, and artificial life. There has, however been one notable exception to this progress. Despite the potential benefits, there has been no clear increase in the behavioral complexity of evolved virtual creatures (EVCs) beyond the light following demonstrated in Sims' original work.

We present a new rigging and skinning method which uses a database of partial rigs extracted from a set of source characters. Given a target mesh and a set of joint locations, our system can automatically scan through the database to find the best-fitting body parts, tailor them to match the target mesh, and transfer their skinning information onto the new character. For the cases where our automatic procedure fails, we provide an intuitive set of tools to fix the problems. When used fully automatically, the system can generate results of much higher quality than a standard smooth bind, and with some user interaction, it can create rigs approaching the quality of artist-created manual rigs in a small fraction of the time.

We present a new rigging and skinning method which uses a database of partial rigs extracted from a set of source characters. Given a target mesh and a set of joint locations, our system can automatically scan through the database to find the best-fitting body parts, tailor them to match the target mesh, and transfer their skinning information onto the new character. For the cases where our automatic procedure fails, we provide an intuitive set of tools to fix the problems. When used fully automatically, the system can generate results of much higher quality than a standard smooth bind, and with some user interaction, it can create rigs approaching the quality of artist-created manual rigs in a small fraction of the time.

Abstract We present a new system for robustly performing Boolean operations on linear, 3D polyhedra. Our system is exact, meaning that all internal numeric predicates are exactly decided in the sense of exact geometric computation. Our BSP‐tree based system is 16‐28× faster at performing iterative computations than CGAL's Nef Polyhedra based system, the current best practice in robust Boolean operations, while being only twice as slow as the non‐robust modeler Maya. Meanwhile, we achieve a much smaller substrate of geometric subroutines than previous work, comprised of only 4 predicates, a convex polygon constructor, and a convex polygon splitting routine. The use of a BSP‐tree based Boolean algorithm atop this substrate allows us to explicitly handle all geometric degeneracies without treating a large number of cases.

We have developed a filter-based framework where several fundamentally different techniques can be combined to provide fully automated and efficient heuristic solutions to verification and possibly other NP-complete problems. Such an integrated methodology is far more robust and efficient than any single existing technique on a wide variety of circuits. Our methodology has been applied to verify the ISCAS 85 benchmark circuits and efficient verification results have been presented on a large set of industrial circuits which could not be verified using several published techniques and commercial verification tools available to us.

Combinational verification is a co-NP complete problem. However, in reality, several techniques exist which perform reasonably well on many practical circuits. Also, it is often found that while one technique efficiently verifies a given circuit it fails badly on another circuit, whereas a certain other technique is efficient on the latter circuit but cannot handle the former circuit. Therefore, clearly, a robust verification methodology cannot depend on any single technique. Our goal in this research is to build a verification methodology whose performance is more immune to circuit variations. We have developed a methodology where several fundamentally different techniques can be combined to provide efficient heuristic solutions to combinational verification, and possibly other intractable problems as well. Such an integrated methodology is far more robust and efficient on a majority of combinational verification problems than any single existing technique. In this paper, we discuss the methodology in detail and present verification results using a fully automated prototype of the proposed methodology. Using this methodology, we can verify many circuits which could not be efficiently verified using any published techniques available to us, and even by some popular commercial combinational verification programs.

A new Boolean function representation scheme, the Indexed Binary Decision Diagram (IBDD), is proposed to provide a compact representation for functions whose Ordered Binary Decision Diagram (OBDD) representation is intractably large. We explain properties of IBDDs and present algorithms for constructing IBDDs from a given circuit. Practical and effective algorithms for satisfiability testing and equivalence checking of IBDDs, as well as their implementation results, are also presented. The results show that many functions, such as multipliers and the hidden-weighted-bit function, whose analysis is intractable using OBDDs, can be efficiently accomplished using IBDDs. We report efficient verification of Booth multipliers, as well as a practical strategy for polynomial time verification of some classes of unsigned array multipliers.

This paper addresses the problem of verifying the correctness of gate-level implementations of large synchronous sequential circuits with respect to their higher level specifications in a hardware description language (HDL). The verification strategy is to verify containment of the finite state machine (FSM) represented by the HDL description in the gate-level FSM by computing pairs of compatible states. This formulation of the verification problem dissociates the verification process from the specification of initial states, whose encoding may be unknown or obscured during optimization and also enables verification of reset circuitry. To make verification of large circuits with merged data path and control tractable, the concept of strong containment is introduced. This is a conservative approach which exploits correspondence between data path-registers in the two descriptions without requiring any correspondence between the control units. We also present an important result and associated proof that computation of pairs of equivalent or compatible states can be achieved by considering subsets of the circuit outputs. Consequently, verification of circuits with large and diverse input-output sets, which was previously intractable due to lack of a single effective variable order for the binary decision diagrams (BDD's), is now feasible. Experimental results are presented for the verification of several industry level circuits.

It is reasonable to project that continuing progress in micro-electronics will lead to computing systems based on circuit elements with switching times on the order of a few picaseconds. Such speeds are likely beyond the capabilities of CMOS. One promising technology is Rapid Single Flux Quantum (RSFQ) circuits based on super-conducting Josephson junction devices. However, for such high-speed technologies, clock skew even over short distances can make synchronous circuit design prohibitively difficult. We have introduced a variant of delay insensitive (DI) asynchronous logic called conservative delay insensitive (CDI) logic which has particularly nice properties for use in RSFQ technology. Not only does it solve high-speed clocking problems, but its primitive elements appear to be more efficiently implementable in RSFQ technology than are traditional Boolean logic primitives and its property of minimizing the creation and destruction of signal pulses avoids some difficult implementation issues in RSFQ.

Design-rule checking, whose efficiency depends greatly on the speed in finding an object's neighbors, is an indispensable component of any VLSI design process. Given a design, the objects it contains are usually represented by their smallest enclosing rectangles, and neighbor search is defined as the operation to find, among the collection of rectangles, the ones that are within the specified distance of a rectangle. Commonly, the rectangles are stored in a tree structure, and a region query that searches the tree starting at its root is used to find a rectangle's neighbors. In this paper, we introduce the hinted quad tree, or HQT, that supports neighbor searches directly without always starting a search at the root of the tree. We show that HQT achieves the highest neighbor-search performance among the data structures compared and uses a reasonable amount of storage.

This paper presents a new verification methodology to prove that a high level HDL description of a synchronous sequential circuit satisfies certain desired behavior or that it is free of certain malicious behavior. The correctness specifications are modeled as state machines with some transitions having unspecified inputs. We show that this suffices for specification of a large class of properties, including both safety and liveness properties. The properties are described as VHDL programs to enable the designer to simulate them for sample inputs and gain some measure of confidence in their correctness. Experimental results are presented for the Viper microprocessor.

Automatic verification of implementations against their specifications in the design hierarchy is largely based on state machine comparison. This paper presents a simple technique that exploits information about correspondence between registers in the data path to enable abstraction of data path registers and make automatic verification of circuits with large date paths tractable. Correspondence between registers which encode the control states is not required. This generality enables efficient verification of large circuits with data paths structured differently, as well as verification against specifications devoid of structural information. Results are presented for the verification of realistic circuits at different levels in the design hierarchy.>

Introduces some new methods for estimating the "importance" of a variable in a Boolean function, and uses them to compute variable orders for OBDD construction. These measures are based on information theoretic criteria, and require the computation of the entropy of a variable in a given function. These entropy measures prove quite effective in distinguishing the importance of variables. Experimental results show this to be a very encouraging approach to help in the solution of this well known problem.>

Rosenberg compared linked lists, quad trees with bkector lists, and W trees, and

In any stored-program computer system, information is constantly transferred between the memory and the instruction processor. Machine instructions are a major portion of this traffic. Since transfer bandwidth is a limited resource, inefficiency in the encoding of instruction information (low code density) can have definite hardware and performance costs.

A parallel algorithm for finding triconnected components on a CRCW PRAM is presented. The time complexity of the algorithm is $O(\log n)$, and the processor-time product is $O((m + n)\log \log n)$, where n is the number of vertices and m is the number of edges of the input graph. The algorithm, like other parallel algorithms for this problem, is based on open ear decomposition, but it uses a new technique, local replacement, to improve the complexity. Only the need to use the subroutines for connected components and integer sorting, for which no optimal parallel algorithm that runs in $O(\log n)$ time is known, prevents the algorithm from achieving optimality.

A practical model for probabilistic fault diagnosis is presented. Unlike PMC-based models, the model allows testers to conduct multiple tests on the same processor. This allows the design of efficient probabilistic diagnosis algorithms with good asymptotic behavior, with minimal constraints on the connection structure of the multiprocessor system, in contrast to other deterministic and probabilistic approaches. In practical cases, the number of immediate neighbors of any processor need be no greater than two, which implies that the algorithm can be applied to any practical homogeneous parallel architecture. It is also shown how to make efficient use of tests by allowing the number of testing processors, and the number of tests performed by a processor to be traded off in achieving asymptotically accurate diagnosis.>

A VLSI two-layer channel router designed to find solutions which minimize both wiring area and number of vias simultaneously is presented. The method, called topological channel routing, analyzes the topological relationship of wires before the wires are mapped onto the channel. A unique layout design rule called an interleaving mesh is used. The interleaving mesh prohibits long wires on one layer from overlapping with wires on the other layer, and thus has smaller crosstalk of signals because of smaller capacitive couplings between those wires on different layers. Experimental results show that the algorithm generates very good solutions. For example, a height of 41 for Deutsch's Difficult Example without any parallel overlaps of wires has been obtained and simultaneously, with a via count of 186, which is one of the best results ever reported in the literature.>

The authors present a novel method for verifying the equivalence of two Boolean functions. Each function is hashed to an integer code by assigning random integer values to the input variables and evaluating its integer-valued representation. The equivalence of two functions can be verified with a very low probability of error. The probability of error can be exponentially decreased by making multiple runs. Results indicate significant time and space advantages for this method over deterministic techniques. Some functions known to require space (and time) exponential in the number of input variables for deterministic verification require only polynomial resources using the proposed technique.>

A probabilistic comparison algorithm is presented which requires O(f log n) bits to be transmitted to identify the corrupt pages in a file (where n is the number of pages and f is the maximum number of pages that could be corrupted), which improves on previous results on the growth of communicated bits as functions of both n and of f. If both copies compared are corrupt, only twice the number of bits is required as for the previous case. Further, if multiple copies are used for comparison, then the product of the number of copies times the number of bits sent from each of these copies to the comparison site grows as O(f log n). A lower bound which establishes the optimality of the algorithm to within a constant factor is provided.>

A novel method is proposed for the two-layer topological channel routing problem. The authors' algorithm takes geometric information into consideration when a topological solution is obtained. Experimental results show that the algorithm generates very good solutions. For example, the authors have obtained a height of 41 for Deutsch's difficult example without any parallel overlaps of wires while simultaneously achieving a via count of 219.>

Rapid developments in the design of algorithms for rendering globally illuminated scenes have taken place in the past five years. Net energy methods such as the hemicube and other radiosity algorithms have become very effective at computing the energy balance for scenes containing diffusely reflecting objects. Such methods first break up a scene description into a relatively large number of elements, or possibly several levels of elements. Energy transfers among these elements are then determined using a variety of means. While much progress has been made in the design of energy transfer algorithms, little or no attention has been paid to the proper generation of the mesh of surface elements. This paper presents a technique for adaptively creating a mesh of surface elements as the energy transfers are computed. The method allows large numbers of small elements to be placed at parts of the scene where the most active energy transfers occur without requiring that other parts of the scene be needlessly subdivided to the same degree. As a result, the computational effort in the energy transfer computations can be concentrated where it has the most effect.

The authors present a ray-tracing algorithm for volume rendering designed to work efficiently when the data of interest is distributed sparsely through the volume. A simple preprocessing step identifies the voxels representing features of interest. Frequently this set of voxels, arbitrarily distributed in three-dimensional space, is a small fraction of the original voxel grid. A median-cut space partitioning scheme, combined with bounding volumes to prune void spaces in the resulting search structure, is used to store the voxels of interest in a k-d tree. The k-d tree is used as a data structure. The tree is then efficiently ray-traced to render the voxel data. The k-d tree is view independent, and can be used for animation sequences involving changes in positions of the viewer or positions of lights. This search structure has been applied to render voxel data from MRI, CAT scan, and electron density distributions.>

Production testing of a digital circuit requires the generation of a sequence of tests and their application to the circuit being tested. Currently, in test application, the output of the circuit under test is compared to a known correct output for each test. The method has some drawbacks likely to become more critical in the near future. In homogeneous systems of identical integrated circuits of silicon wafers, testing can be done in another way, i.e. by applying a common test to several processing elements at once and comparing the results produced by them. The authors analyze such schemes and show that they are inherently as accurate as current methods that use assumed correct results for production testing. Since this approach could allow wafers to be tested for production faults significantly more quickly than by using a probe tester, the results indicate that it can provide an attractive alternative to current methods for production testing of silicon wafers.>

We present a technique for modeling global illumination which allows a wide variety of reflectance functions. Scene coherence is exploited in a preprocessing step in which the geometry is analyzed using iterative techniques. Memory is traded for speed, in anticipation of the high memory capacities of workstations of the future. The algorithm operates well over a wide range of time and image quality constraints: realistic results may be produced very quickly while very accurate results require more time and space. The method can be extended for animation and parallelization.

An approach to two-layer channel routing using a layout model which utilizes the channel area more efficiently than the traditional layout model is presented. The model allows horizontal and vertical wire segments to be placed on both layers while avoiding the crosstalk problem. In order to have as many nets without vias as possible, the crossing relationship among the nets is determined before they are mapped onto a channel. Preliminary experimental results are very encouraging.>

Raster graphics displays are almost always refreshed out of a frame buffer in which a digital representation of the currently visible image is kept. The availability of the frame buffer as a two-dimensional memory array representing the displayable area in a screen coordinate system has motivated the development of algorithms that take advantage of this memory for more than just picture storage. The classic example of such an algorithm is the depth buffer algorithm for determining visible surfaces of a three-dimensional scene. This paper constitutes a first attempt at a disciplined analysis of the power of a frame buffer seen as a computational engine for use in graphics algorithms. We show the inherent power of frame buffers to perform a number of graphics algorithms in terms of the number of data fields (registers) required per pixel, the types of operations allowed on these registers, and the input data. In addition to upper bounds given by these algorithms, we prove lower bounds for most of them and show most of these algorithms to be optimal. One result of this study is the introduction of new frame buffer algorithms for computing realistic shadows and for determining the convex intersection of half spaces, an operation important in computational geometry and in rendering objects defined using planes rather than polygons. Another result is that it shows clearly the relationships between different and important areas of research in computer graphics, such as visible surface determination, compositing, and hardware for smart frame buffers.

This paper presents a formal model of linear array processors suitable for VLSI implementation as well as graph representations of programs suitable for execution on such a model. A distinction is made between correct mapping and correct execution of such graphs on this model and the structure of correctly mappable graphs are examined. The formalism developed is used to synthesize algorithms for this model.

A locking protocol is a set of rules governing the manner in which the database entities may be accessed. Such a protocol usually employs several kinds of locks. Most of the previous work in this area has assumed that once a transaction acquires a particular kind of lock on a data item it is not allowed to convert this lock to another kind. In this paper we perform a systematic study of the consequences of allowing lock conversions in non-two-phase locking protocols, and show how this leads to increased concurrency and affects deadlock-freedom. The non-two-phase protocols that we study are the very general guard protocols defined for databases in which a directed acyclic graph structure can be superimposed on the data items. We present very natural generalizations of these protocols, including correctness proofs, and develop deadlock removal methods.

Matrix multiplication algorithms have been proposed for VLSI array processors. Random defects in the silicon wafer and fabrication errors render processors and data paths in the array faulty, and may cause the algorithm to fail despite a significant number of nonfaulty processors. This correspondence presents a robust VLSI array processor for matrix multiplication. The array is driven by a host computer as a peripheral and the I/O bandwidth required to drive the array is a constant, independent of the problem size. Multiplication of two n x n matrices requires O(n) processors and has a time complexity of O(n2) cydes.

The basic problem which limits both yields and chip sizes is the fact that circuits created using current design techniques will not function correctly in the presence of even a single flaw of sufficient size anywhere on the chip. In this work we examine the problem of constructing chips up to the size of a wafer which operate correctly despite the presence of such flaws. This can be accomplished by building on the wafer a nearest-neighbor network of small, independent, asynchronously communicating modules. A specific algorithm to be performed by the wafer is then mapped onto a fault-free subgraph of the network. We are interested in algorithms which map naturally onto a linear array of identical processors. Construction of fault-tolerant implementations of these algorithms is addressed in two contexts. First we consider the general problem of finding a fault-free subgraph of the host network which is isomorphic to the linear array required to solve a problem. We then examine ways to tailor a specific, known algorithm to the fault-tolerant context.

Research on concurrency control mechanisms for database systems has had as a primary goal the discovery of techniques for allowing increased levels of concurrent execution of transactions. In this paper, we study this problem in the context of non-two-phase locking protocols which are defined for data bases in which a directed acyclic graph structure is superimposed on the data items. We introduce a new lock mode, called INV, with properties fundamentally different from locking modes previously studied and show how this allows increased concurrency. Through the introduction of the INV mode of locking we have enunciated a new principle of the theory of data base concurrency control. This principle involves the separation of the effects of the commutativity and compatibility of data manipulation operations. We then examine how the introduction of such a lock mode affects the occurrence of deadlocks in a system. Certain conditions under which deadlock-freedom is maintained are identified, and simple methods for removing deadlocks in other situations are presented.

The problem of removing deadlocks from concurrent database systems using the two-phase locking protocol is considered. In particular, for systems which use no a priori information about transaction behavior in order to avoid deadlocks, it has generally been assumed necessary to totally remove and restart some transaction involved in a deadlock in order to relieve the situation. In this paper, a new approach to deadlock removal in such systems based on partial rollbacks is introduced. This approach does not in general require the total removal of a transaction to eliminate a deadlock. The task of optimizing deadlock removal using this method is discussed for systems allowing both exclusive and shared locking. A method is given for implementing this approach with no more storage overhead than that required for total removal and restart.

A recurrent problem in generating realistic pictures by computers is to represent natural irregular objects and phenomena without undue time or space overhead. We develop a new and powerful solution to this problem by modeling objects as sample paths of stochastic processes. Of particular interest are those stochastic processes which previously have been found to be useful models of the natural phenomena to be represented. One such model applicable to the representation of terrains, known as “fractional Brownian motion”, has been proposed by B. Mandelbrot.