Browsing LCS Technical Memos (1974 - 2003) by Author "Leiserson, Charles E."
Now showing items 1-11 of 11
-
An Application of Number Theory to the Organization of Raster Graphics Memory
(1984-04)A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ... -
Cilk: An Efficient Multithreaded Runtime System
(1996-01)Cilk (pronounced "silk") is a C-based runtime system for multithreaded parallel programming. In this paper, we document the efficiency of the Cilk work-stealing scheduler, both empirically and analytically. We show that ... -
Communication-efficient Parallel Graph Algorithms
(1986-12)Communication bandwidth is a resource ignored by most parallel random-access machine (PRAM) models. This paper shows that many graph problems can be solved in parallel, not only with polylogarithmic performance, but with ... -
How to Assemble Tree Machines
(1984-03)Many researchers have proposed that ensembles of processing elements be organized as trees. This paper explores how large tree machines can be assembled efficiently from smaller components. A principal constraint considered ... -
A Mixed Integer Linear Programming Problem Which is Efficiently Solvable
(1985-07)Efficient algorithms are known for the simple linear programming problem where each inequality is of the form xj-xi<=aij. Furthermore, these techniques extend to the integer linear programming variant of the problem. This ... -
Optimizing Synchronous Systems
(1982-03)The complexity of integrated-circuit chips produced today makes it feasible to build inexpensive, special-purpose subsystems that rapidly solve sophisticated problems on behalf of a general-purpose host computer. This paper ... -
Randomized Routing on Fat-trees
(1986-05)Fat-trees are a class of routing networks for hardware-efficient paralle computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the ... -
Retiming Synchronous Circuitry
(1986-05)This paper shows how the technique of retiming can be used to transform a given sycnhronous circuit into a more efficient circuit under a variety of different cost criteria. We model a circuit as a graph, and we give an ... -
A Space-efficient Algorithm for Finding the Connected Components of Rectangles in the Plane
(1987-02)We present an algorithm for determining the connectivity of a set of N rectangles in the plane, a problem central to avoiding aliasing in VLSI design rule checkers. Previous algorithms for this problem either worked slowly ... -
Wafer-scale Integration of Systolic Arrays
(1983-02)VLSI technologists are fast developing wafer-scale integration. Rather than partitioning a silicon wafer into chips as is usually done, the idea behind wafer-scale integration is to assemble an entire system (or network ...
