Papers
Browse academic papers referenced in production code
How to make ad-hoc polymorphism less ad hoc
This paper presents type classes, a new approach to ad-hoc polymorphism. Type classes permit overloading of arithmetic operators such as multiplication, and generalise the "eqtype variables" of Standard ML. Type classes extend the Hindley/Milner poly...
More iteration space tiling.
Subdividing the iteration space of a loop into blocks or tiles with a fixed maximum size has several advantages. Tiles become a natural candidate as the unit of work for parallel task scheduling. Synchronization between processors can be done between...
Compacting garbage collection with ambiguous roots
Many modern garbage collectors [4] recover space by copying. Using an initial "root" set of pointers which are stored in known locations, all accessible objects are copied into a "new space". Two of the attractive properties of such a collector are t...
Reconstruction filters in computer-graphics
Problems of signal processing arise in image synthesis because of transformations between continuous and discrete representations of 2D images. Aliasing introduced by sampling has received much attention in graphics, but reconstruction of samples int...
An efficient algorithm for sequential random sampling
We examine several methods for drawing a sequential random sample of n records from a file containing N records. Method D is recommended for general use. The algorithm is on-line (so that CPU time can be overlapped with I/O), has a small constant mem...
The program dependence graph and its use in optimization
In this paper we present an intermediate program representation, called the program dependence graph ( PDG ), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only...
Graph-Based Algorithms for Boolean Function Manipulation
In this paper we present a new data structure for representing Boolean functions and an associated set of manipulation algorithms. Functions are represented by directed, acyclic graphs in a manner similar to the representations introduced by Lee [1] ...
The Least Weight Subsequence Problem (Extended Abstract)
The least weight subsequence (LWS) problem is introduced, and is shown to be equivalent to the classic minimum path problem for directed graphs. A special case of the LWS problem is shown to be solvable in O(n log n) time generally and, for certain w...
Automatic loop interchange.
Parallel and vector machines are becoming increasingly important to many computation intensive applications. Effectively utilizing such architectures, particularly from sequential languages such as Fortran, has demanded increasingly sophisticated com...
Color image quantization for frame buffer display
Algorithms for adaptive, tapered quantization of color images are described. The research is motivated by the desire to display high-quality reproductions of color images with small frame buffers. It is demonstrated that many color images which would...
Dependence Graphs and Compiler Optimizations.
Dependence graphs can be used as a vehicle for formulating and implementing compiler optimizations. This paper defines such graphs and discusses two kinds of transformations. The first are simple rewriting transformations that remove dependence arcs....
Linear Hashing: A New Tool for File and Table Addressing.
AbstractPolyhydroxyethers were synthesized from monoalkali metal salts of diphenols and 1‐halo‐2,3‐epoxyalkanes in a one‐step reaction in dipolar, aprotic solvents as reaction media. They were also synthesized from alkali metal salts of diphenols, di...
The serializability of concurrent database updates
ABSTRACT A sequence of interleaved user transactions in a database system may not be ser:ahzable, t e, equivalent to some sequential execution of the individual transactions Using a simple transaction model, it ~s shown that recognizing the transacti...
On a Real-Time Scheduling Problem
We study the problem of scheduling periodic-time-critical tasks on multiprocessor computing systems. A periodic-time-critical task consists of an infinite number of requests, each of which has a prescribed deadline. The scheduling problem is to speci...
An Extension of the String-to-String Correction Problem
article Free Access Share on An Extension of the String-to-String Correction Problem Authors: Robert A. Wagner Department of Systems and Information Sciences, Vanderbilt University, Nashville, TN Department of Systems and Information Sciences, Vander...