Approximate arithmetic is a promising, new approach to low-energy designs while tackling reliability issues. We present a method to optimally distribute a given energy budget among adders in a dataflow graph so as to minimize expected errors. The method is based on new formal mathematical models and algorithms, which quantitatively characterize the relative importance of the adders in a circuit. We demonstrate this method on a finite impulse response filter and a Fast Fourier Transform. The optimized energy distribution yields 2.05X lower error in a 16-point FFT and images with SNR 1.42X higher than those achieved by the best previous approach.

The central theme of our work is the probabilistic and approximate design of embedded computing systems. This novel approach consists of two distinguishing aspects: (i) the design and implementation of embedded systems, using components which are susceptible to perturbations from various sources and (ii) a design methodology which consists of an exploration of a design space which characterizes the trade-off between quality of output and cost, to implement high performance and low energy embedded systems. In contrast with other work, our design methodology does not attempt to correct the errors introduced by components which are susceptible to perturbations, instead we design "good enough" systems. Our work has the potential to address challenges and impediments to Moore's law arising from material properties and manufacturing difficulties, which dictate that we shift from the current-day deterministic design paradigm to statistical and probabilistic designs of the future. In this paper, we provide a broad overview of our work on probabilistic and approximate design, present novel results in approximate arithmetic and its impact on digital signal processing algorithms, and sketch future directions for research.

On-demand routing protocols use route caches to make routing decisions. Due to mobility, cached routes easily become stale. To address the cache staleness issue, prior work in DSR used heuristics with ad hoc parameters to predict the lifetime of a link or a route. However, heuristics cannot accurately predict timeouts because topology changes are unpredictable. In this paper, we propose to proactively disseminate the broken link information to the nodes that have that link in their caches. We define a new cache structure called a cache table and present a distributed cache update algorithm. Each node maintains in its cache table the information necessary for cache updates. When a link failure is detected, the algorithm notifies all reachable nodes that have cached the link in a distributed manner. The algorithm does not use any ad hoc parameters, thus making route caches fully adaptive to topology changes. We show that the algorithm outperforms DSR with path caches and with Link-MaxLife, an adaptive timeout mechanism for link caches. We conclude that proactive cache updating is the key to the adaptation of on-demand routing protocols to mobility.

TCP performance is adversely affected by frequent route failures due to mobility in mobile ad hoc networks. Most of the recent attempts to improve TCP performance focused on transport layer mechanisms and several modifications to TCP were proposed to prevent it from invoking congestion control for packet losses caused by route failures. We present a new approach to improve TCP performance at the network layer: reducing route failures by making route caches in on-demand routing protocols adapt to topology changes quickly and efficiently. The route cache in on-demand routing protocols is used for routing decisions, however, due to frequent topology changes, cached routes easily become stale, seriously degrading TCP throughput. In our prior work, we proposed a distributed adaptive cache update algorithm to address the cache staleness issue in the dynamic source routing protocol (DSR), an important on-demand routing protocol. In this paper, we investigate the impact of this algorithm on TCP performance, without any modification to TCP. We show through detailed simulations that this algorithm significantly improves TCP throughput and reduces normalized routing overhead. We conclude that it is important to make route caches reflect topology changes quickly so that the effect of mobility on TCP is reduced.

Discovering frequent itemsets is a key problem in important data mining applications, such as the discovery of association rules, strong rules, episodes, and minimal keys. Typical algorithms for solving this problem operate in a bottom-up, breadth-first search direction. The computation starts from frequent 1-itemsets (the minimum length frequent itemsets) and continues until all maximal (length) frequent itemsets are found. During the execution, every frequent itemset is explicitly considered. Such algorithms perform well when all maximal frequent itemsets are short. However, performance drastically deteriorates when some of the maximal frequent itemsets are long. We present a new algorithm which combines both the bottom-up and the top-down searches. The primary search direction is still bottom-up, but a restricted search is also conducted in the top-down direction. This search is used only for maintaining and updating a new data structure, the maximum frequent candidate set. It is used to prune early candidates that would be normally encountered in the bottom-up search. A very important characteristic of the algorithm is that it does not require explicit examination of every frequent itemset. We evaluate the performance of the algorithm using well-known synthetic benchmark databases, real-life census, and stock market databases.

To exploit parallelism on shared memory parallel computers (SMPCs), it is natural to focus on decomposing the computation (mainly by distributing the iterations of the nested Do-Loops). In contrast, on distributed memory parallel computers (DMPCs), the decomposition of computation and the distribution of data must both be handled---in order to balance the computation load and to minimize the migration of data. We propose and validate experimentally a method for handling computations and data synergistically to minimize the overall execution time on DMPCs. The method is based on a number of novel techniques, also presented in this article. The core idea is to rank the "importance" of data arrays in a program and specify some of the dominant. The intuition is that the dominant arrays are the ones whose migration would be the most expensive. Using the correspondence between iteration space mapping vectors and distributed dimensions of the dominant data array in each nested Do-loop, allows us to design algorithms for determining data and computation decompositions at the same time. Based on data distribution, computation decomposition for each nested Do-loop is determined based on either the "owner computes" rule or the "owner stores" rule with respect to the dominant data array. If all temporal dependence relations across iteration partitions are regular, we use tiling to allow pipelining and the overlapping of computation and communication. However, in order to use tiling on DMPCs, we needed to extend the existing techniques for determining tiling vectors and tile sizes, as they were originally suited for SMPCs only. The overall method is illustrated on programs for the 2D heat equation, for the Gaussian elimination with pivoting, and for the 2D fast Fourier transform on a linear processor array and on a 2D processor grid.

Parallel computing on local area networks is generally based on mechanisms that specifically target the properties of the local area network environment. However, these mechanisms do not effectively extend to wide area networks due to issues such as heterogeneity, security, and administrative boundaries. We present a system which enables application programmers to write parallel programs in Java and allows Java-capable browsers to execute parallel tasks. It comprises a virtual machine model which isolates the program from the execution environment, and a runtime system realizing this virtual machine on the Web. Load balancing and fault masking are transparently provided by the runtime system.

Java, in combination with Web browsers' abilities to load and execute untrusted Java applets in a secure fashion, has made computing over the Web a possibility. Now the challenge is to fully utilize this potential, given the limitations imposed by browsers. This paper presents KnittingFactory, an infrastructure to facilitate Web-based computing, which addresses this challenge. It supports building distributed applications, specifically those consisting of Java applets executing in browsers. It is composed of: (i) a distributed name service to assist users in locating other participants of a distributed computation via standard browsers; (ii) an embedded class server to eliminate the need for external HTTP servers for serving applet code; and (iii) a technique for direct applet-to-applet communication. In this paper, we describe the design and implementation of KnittingFactory and demonstrate its benefits by applying it to three distinct areas of Web-based computing. First, we apply our distributed name service to a client/server architecture to enable RMI clients to locate servers on unknown hosts. Second, we use the embedded class server to extend the capability of Charlotte, a parallel computing environment. Finally, we build a collaborative application using our direct applet-to-applet communication technique which does not require a forwarding agent. © 1998 John Wiley & Sons, Ltd.

We introduce a shared memory software prototype system for executing programs with nested parallelism on a network of workstations. This programming model exhibits a very convenient and natural programming style and provides functionality similar to a subset of Compositional C++. Such programming model is especially suitable for computations whose complexity and parallelism emerges only during their execution, as in divide and conquer problems. To both support and take advantage of the flexibility inherent in the programming model, we develop an architecture, which distributes both the shared memory management and the computation, removing bottlenecks inherent in centralization, thus also providing scalability and dependability. The system supports also dynamic load balancing, and fault tolerance-both transparently to the programmer. The prototype performs well using the realistic platforms of non-dedicated network of workstation. We describe encouraging performance experiments on a network in which some of the machines became slow unpredictably (to the application program). The system coped well with such dynamic behavior.

Our main result in this paper is a parallel algorithm for suffix-prefix- ($s - p$-) matching that has optimal speedup on a concurrent-read/concurrent-write parallel random-access machine (CRCW PRAM). Given a string of length m, the algorithm runs in time $O(\log m)$ using ${m / {\log m}}$ processors. This algorithm is important because we utilize s–p matching as a fundamental building block to solve several pattern- and string-matching problems, such as the following: 1. string matching; 2. multitext/multipattern string matching; 3. multidimensional pattern matching; 4. pattern-occurrence detection; 5. on-line string matching. In particular, our techniques and algorithms are the first to preserve optimal speedup in the context of pattern matching in higher dimensions and are the only known ones to do so for dimensions $d > 2$.

The importance of adapting networks of workstations for use as parallel processing platforms is well established. However current solutions do not always address important issues that exist in real networks. External factors like the sharing of resources, unpredictable behavior of the network and failures, are present in multiuser networks and must be addressed. CALYPSO is a prototype software system for writing and executing parallel programs on non-dedicated platforms, based on COTS networked workstations operating systems, and compilers. Among notable properties of the system are: (1) simple programming paradigm incorporating shared memory constructs and separating the programming and the execution parallelism, (2) transparent utilization of unreliable shared resources by providing dynamic load balancing and fault tolerance, and (3) effective performance for large classes of coarse-grained computations. We present the system and report our initial experiments and performance results in settings that closely resemble the dynamic behavior of a "real" network. Under varying work-load conditions, resource availability and process failures, the efficiency of the test program we present ranged from 84% to 94% bench-marked against a sequential program.

One of the most sought after software innovation of this decade is the construction of systems using off-the-shelf-workstations that actually deliver and even surpass, the power and reliability of supercomputers. Using completely novel techniques: eager scheduling, evasive memory layouts and dispersed data management it is possible to build an execution environment for parallel programs on workstation networks. These techniques were originally developed in a theoretical framework for an abstract machine which models a shared memory asynchronous multiprocessor. The network of workstations platform presents an inherently asynchronous environment for the execution of our parallel program. This gives rise to substantial problems of correctness of the computation and of proper automatic load balancing of the work amongst the processors, so that a slow processor will not hold up the total computation. A limiting case of asynchrony is when a processor becomes infinitely slow, i.e. fails. Our methodology copes with all these problems, as well as with memory failures. An interesting feature of this system is that it is neither a fault-tolerant system extended for parallel processing nor is it parallel processing system extended for fault tolerance. The same novel mechanisms ensure both properties.

An n-thread parallel program p is large-grained if in every parallel step the computations on each of the threads are complex procedures requiring numerous processor instructions. This practically relevant style of programs differs from PRAM programs in its large granularity and the possibility that within a parallel step the computations on different threads may considerably vary in size. Let M be an n-processor asynchronous parallel system, with no restriction on the degree of asynchrony and without any specialized synchronization mechanisms. It is a challenging theoretical as well as practically important problem to ensure correct execution of P on such a parallel machine. Let P be a large-grained program requiring total work W for its execution on a synchronous a-processor parallel system. We present a transformation (compilation) of P into a program C(P) which correctly and efficiently effects the computation of P on the asynchronous machine M. Under moderate assumptions on the granularity of threads and the size of the program variables, execution of C(P) requires just O(Wlog* n) expected total work, and the memory space overhead is a small multiplicative constant.>

In this paper, we address the problem of automatically transforming arbitrary programs written for an ideal parallel machine to run on a completely asynchronous machine. We present a transformation which can be applied to an ideal program such that the resulting program's execution on an asynchronous machine is work and space efficient, relative to the ideal program from which it is derived. Above all, the transformation will guarantee that the ideal program will execute in a continually progressive manner on the asynchronous machine; these instructions are not universal. Furthermore, the individual processors can get delayed for arbitrary amounts of time while executing any instruction. In contrast, previous work relied either on the asynchronous machine having universal read-modify-write instructions as primitives, or on limited asynchrony by restricting the relative speeds of the processors.

Forest matching is a fundamental step in solving various problems defined on terms such as term matching. We describe the first optimal speedup parallel algorithm for solving the forest matching problem. Our algorithm runs in time O(log n) using nlog n processors on a CRCW PRAM, given a forest of n nodes as input. We use this algorithm to design the first optimal speedup parallel algorithm for solving the term matching problem. We also extend these algorithms to run on the weaker CREW PRAM with optimal speedup as well. This will involve a simple randomization scheme for simulating concurrent writes through a use of hashing.

Article Free Access Share on Combining tentative and definite executions for very fast dependable parallel computing Authors: Z. M. Kedem Ecole des Hautes Etudes en Informatique, Université René Descartes, 45, rue des Saints-Pères, 75006 Paris, France and Department of Computer Science, New York University, 251 Mercer St., New York, NY Ecole des Hautes Etudes en Informatique, Université René Descartes, 45, rue des Saints-Pères, 75006 Paris, France and Department of Computer Science, New York University, 251 Mercer St., New York, NYView Profile , K. V. Palem IBM Research Division, T. J. Watson Research Center, P. O. Box 704, Yorktown Heights, NY IBM Research Division, T. J. Watson Research Center, P. O. Box 704, Yorktown Heights, NYView Profile , A. Raghunathan Computer Science Division, University of California, Davis, CA and New York University Computer Science Division, University of California, Davis, CA and New York UniversityView Profile , P. G. Spirakis Computer Technology Institute, Patras University, P. O. Box 1122, 26110 Patras, Greece Computer Technology Institute, Patras University, P. O. Box 1122, 26110 Patras, GreeceView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 381–390https://doi.org/10.1145/103418.103459Published:03 January 1991Publication History 57citation260DownloadsMetricsTotal Citations57Total Downloads260Last 12 Months14Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A parallel computing system becomes increasingly prone to failure as the number of processing elements in it increases.In this paper, we describe a completely general strategy that takes an arbitrary step of an ideal CRCW PRAM and automatically translates it to run efficiently and robustly on a PRAM in which processors are prone to failure.The strategy relies on efficient robust algorithms for solving a core problem, the Certified Write-All Problem.This problem characterizes the core of robustness, because, as we show, its complexity is equal to that of any general strategy for realizing robustness in the model.We analyze the expected parallel time and work of various algorithms for solving this problem.Our results are a non-trivial generalization of Brent's

Concurrency control protocols based on two-phase locking are a popular family of locking protocols that preserve serializability in general (unstructured) database systems. A concurrency control algorithm (for databases with no inherent structure) is presented that is practical, non two-phase, and allows varieties of serializable logs not possible with any commonly known locking schemes. All transactions are required to predeclare the data they intend to read or write. Using this information, the protocol anticipates the existence (or absence) of possible conflicts and hence can allow non-two-phase locking. It is well known that serializability is characterized by acyclicity of the conflict graph representation of interleaved executions. The two-phase locking protocols allow only forward growth of the paths in the graph. The Five Color protocol allows the conflict graph to grow in any direction (avoiding two-phase constraints) and prevents cycles in the graph by maintaining transaction access information in the form of data-item markers. The read and write set information can also be used to provide relative immunity from deadlocks.

Consideration is given to transforming depth p-nested for loop algorithms into q-dimensional systolic VLSI arrays where 1>

The complex system formalism is utilized for describing structural and behavioral properties of complexly structured systems. A complex system is a production system that models a database with complex objects and explicitly supports time and nondeterminism. Consequently, complex systems can be used to predict the evolution of databases. To obtain predictions about future behavior, a futuristic query language is defined. A query optimisation algorithm is provided for a subset of this language. In general, complex systems do not yield unique answers to futuristic queries because of the inherent nondetermination. Therefore, an optimal control problem is formulated that finds behavior satisfying user-defined goals. Subsequently, such goals can be converted into additional system constraints, thus reducing nondeterminism and providing for the optimal system's behavior.>

Behavior of relational databases is studied within the framework of Relational Discrete Event Systems (RDE-Ses) and Models (RDEMs). Production system and recurrence equation RDEMs are introduced, and their expressive powers are compared. Non-deterministic behavior is defined for both RDEMs and the expressive power of deterministic and non-deterministic production rule programs is also compared. This comparison shows that non-determinism increases expressive power of production systems. A formal concept of a production system interpreter is defined, and several specific interpreters are proposed. One interpreter, called parallel deterministic, is shown to be better than others in many respects, including the conflict resolution module of OPS5.

A simple programmable linear systolic array capable of solving a large number of problems drawn from a variety of applications is designed. The methodology is applicable to problems solvable by sequential algorithms that can be specified as nested FOT-loops of arbitrary depth. The algorithms of this form that can be computed on the array include 25 algorithms dealing with signal and image processing, algebraic computations, matrix arithmetic, pattern matching, database operations, sorting, and transitive closure. Assuming bounded I/O, for 18 of those algorithms the time and storage complexities are optimal, and therefore no improvement can be expected by utilizing dedicated special-purpose linear systolic arrays designed for individual algorithms.>

The mapping of algorithms structured as depth-p nested FOR loops into special-purpose systolic VLSI linear arrays is addressed. The mappings are done by using linear functions to transform the original sequential algorithms into a form suitable for parallel execution on linear arrays. A feasible mapping is derived by identifying formal criteria to be satisfied by both the original sequential algorithm and the proposed transformation function. The methodology is illustrated by synthesizing algorithms for matrix multiplication and a version of the Warshall-Floyd transitive closure algorithm.>

This paper presents initial results on the problem of allocation of the available VLSI chip’s area among various functional components such as I/Q pads, memory cells, and internal wiring. First, a general lower bound for any chip computing a transitive function is derived; this bound is tight for certain functions. The arguments used in the various derivations are later used to specify which of the components are critical depending on the relative sizes of the chip and the number of variables of the function to be computed. The general lower bound is powerful enough that many of the previously proved lower bounds (which could account only for some of the functional requirements) are obtained as explicit special cases of the new result.

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.

This paper is concerned with the problem of developing a family of locking protocols which employ both SHARED and EXCLUSIVE locks and which ensure the consistency of database systems that are accessed concurrently by a number of asynchronously running transactions.First, a general result concerning extensions of all protocols that employ EXCLUSIVE locks only to also employ SHARED locks is presented.Then a famdy of protocols apphcable to database systems that are modeled by directed acydtc graphs Is presented.

This paper is concerned with the problem of ensuring the integrity of database systems that are accessed concurrently by a number of independent asychronously running transactions. It is assumed that the database system is partitioned into small units that are referred to as the database entities. The relation between the entities is represented by a directed acyclic graph in which the vertices correspond to the database entities and the arcs correspond to certain access rights. We develop a family of non-two-phase locking protocols for such systems that will be shown to ensure serializability and deadlock-freedom. This family is sufficientdy general to encompass all the previously developed non-two-phase lose locking protocols as well as a number of new protocols. One of these new protocols that seems to be particularly useful is also presented in this paper.

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.

This paper describes a new algorithm for solving the hidden surface (or line) problem, to more rapidly generate realistic images of 3-D scenes composed of polygons, and presents the development of theoretical foundations in the area as well as additional related algorithms. As in many applications the environment to be displayed consists of polygons many of whose relative geometric relations are static, we attempt to capitalize on this by preprocessing the environment's database so as to decrease the run-time computations required to generate a scene. This preprocessing is based on generating a “binary space partitioning” tree whose in order traversal of visibility priority at run-time will produce a linear order, dependent upon the viewing position, on (parts of) the polygons, which can then be used to easily solve the hidden surface problem. In the application where the entire environment is static with only the viewing-position changing, as is common in simulation, the results presented will be sufficient to solve completely the hidden surface problem.

The problems of locking and consistency m database systems are examined It is assumed that each transacuon, when executed alone, transforms a consistent state into a consistent state A set of conditions is derived to guarantee that when transactions are processed concurrently, the results are the same as would be obtained by processing the transactmns serially These conditions are used to estabhsh a locking protocol in Merarchmal database systems The locking protocol allows transaeuons to request new locks after releasing a lock.However, a data item may be locked at most once as a result of each transacUon It ~s shown that the protocol ensures consistency and that tt ts deadlock free.

This paper is concerned with the problem of developing locking protocols for ensuring the consistency of database systems that are accessed concurrently by a number of independent transactions. It is assumed that the database is modelled by a directed acyclic graph whose vertices correspond to the database entities, and whose arcs correspond to certain locking restrictions. Several locking protocols are presented. The weak protocol is shown to ensure consistency and deadlock-freedom only for databases that are organized as trees. For the databases that are organized as directed acyclic graphs, the strong protocol is presented. Discussion of SHARED and EXCLUSIVE locks is also included.

The principal calculation performed by all visible surface algorithms is the determination of the visible polygon at each pixel in the image. Of the many possible speedups and efficiencies found for this problem, only one published algorithm (developed almost a decade ago by a group at General Electric) took advantage of an observation that many visibility calculations could be performed without knowledge of the eventual viewing position and orientation—once for all possible images. The method is based on a “potential obscuration” relation between polygons in the simulated environment. Unfortunately, the method worked only for certain objects; unmanagable objects had to be manually (and expertly!) subdivided into managable pieces.

A new method for estabhshlng lower bounds on the number of multlphcatlons and divisions reqmred to compute rational functions is described The method is based on combining two known methods, dlmenstonahty and rate of growth The method is apphed to several problems and new lower bounds are obtained

No abstract available.

A notion of rank or independence for arbitrary sets of rational functions is developed, which bounds from below the number of additions and subtractions required of all straight-line algorithms which compute those functions. This permits a uniform derivation of the best lower bounds known for a number of familiar sets of rational functions. The result is proved without the use of substitution arguments. This not only provides an interesting contrast to standard approaches for arithmetic lower bounds, but also allows the algebraic setting to be somewhat generalized.

In this paper we describe a new method for establishing lower bounds for the number of multiplications and divisions required to compute rational functions. We shall start by reminding the reader of some standard notations.