Cilk: An Efficient Multithreaded Runtime System (2002)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall
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...
The Link Database: Fast Access to Graphs of the Web (2001)
Keith H. Randall, Raymie Stata, Rajiv G. Wickremesinghe, Janet L. Wiener
The Connectivity Server is a special-purpose database whose schema models the Web as a graph: a set of nodes (URLs) connected by directed edges (hyperlinks). The Link Database provides fast access to...
Keith H. Randall, Raymie Stata, Rajiv G. Wickremesinghe, Janet L. Wiener
graph where URLs are nodes and hyperlinks are directed edges. The Link Database provides fast access to the hyperlinks. To support a wide range of graph algorithms, we find it important to fit the...
Cilk: An Efficient Multithreaded Runtime System (2001)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall
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...
The Swift Java Compiler: Design and Implementation (2000)
Daniel J. Scales, Keith H. Randall, Sanjay Ghemawat, Jeff Dean
We have designed and implemented an optimizing Java compiler called Swift for the Alpha architecture. Swift translates Java bytecodes to optimized Alpha code, and uses static single assignment (SSA)...
Field Analysis: Getting Useful and Low-cost Interprocedural Information (2000)
Sanjay Ghemawat, Keith H. Randall, Daniel J. Scales
We present a new limited form of interprocedural analysis called field analysis that can be used by a compiler to reduce the costs of modern language features such as objectoriented programming,...
Field Analysis: Getting Useful and Low-cost Interprocedural Information (2000)
Sanjay Ghemawat, Keith H. Randall, Daniel J. Scales
We present a new limited form of interprocedural analysis called field analysis that can be used by a compiler to reduce the costs of modern language features such as objectoriented programming,...
The Implementation of the Cilk-5 Multithreaded Language (1999)
Matteo Frigo, Charles E. Leiserson, Keith H. Randall
The fifth release of the multithreaded language Cilk uses a provably good "work-stealing" scheduling algorithm similar to the first system, but the language has been completely redesigned and the...
Cilk: An Efficient Multithreaded Runtime System (1999)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou
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...
Cilk: An Efficient Multithreaded Runtime System (1998)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou
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...
Dag-Consistent Distributed Shared Memory (1998)
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
We introduce dag consistency, a relaxed consistency model for distributed shared memory which is suitable for multithreaded programming. We have implemented dag consistency in software for the Cilk...
Cilk : efficient multithreaded computing / (1998)
Randall, Keith H. (Keith Harold)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998.
43; 252; 003; 274; 489; 856; 000 possible positions of Rubik's cube, which is too many to exhaustively search with today's computers. We have developed a program, however, that can find the minimum...
Tim: A Timing Package for Two-Phase, Level-Clocked Circuitry (1997)
Marios C. Papaefthymiou, Keith H. Randall
Tim is a versatile and efficient tool for verifying and optimizing the timing of two-phase, level-clocked circuitry. Tim performs a variety of functions, such as timing verification, clock tuning,...
Dag-Consistent Distributed Shared Memory (1996)
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
We introduce dag consistency, a relaxed consistency model for distributed shared memory which is suitable for multithreaded programming. We have implemented dag consistency in software for the Cilk...
An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms (1996)
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
In this paper, we analyze the performance of parallel multithreaded algorithms that use dag-consistent distributed shared memory. Specifically, we analyze execution time, page faults, and space...
Cilk: An Efficient Multithreaded Runtime System (1996)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou
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...
Dag-Consistent Distributed Shared Memory (1996)
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
We introduce dag consistency, a relaxed consistency model for distributed shared memory which is suitable for multithreaded programming. We have implemented dag consistency in software for the Cilk...
Dag-Consistent Distributed Shared Memory (1996)
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
We introduce dag consistency, a relaxed consistency model for distributed shared memory which is suitable for multithreaded programming. We have implemented dag consistency in software for the Cilk...
Cilk: An Efficient Multithreaded Runtime System (1995)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou
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...
Parallel Algorithms for the Circuit Value Update Problem (1995)
Charles E. Leiserson, Keith H. Randall
The circuit value update problem is the problem of updating values in a representation of a combinational circuit when some of the inputs are changed. We assume for simplicity that each combinational...
Cilk: An Efficient Multithreaded Runtime System (1995)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou
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...
Cilk: An Efficient Multithreaded Runtime System (1995)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou
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...
Fmarios,randallg@lcs.mit.edu (1994)
Marios C. Papaefthymiou, Keith H. Randall
Tim is a versatile and efficient tool for verifying and optimizing the timing of two-phase, level-clocked circuitry. Tim performs a variety of functions, such as timing verification, clock tuning,...
An Experimental Comparison of Edge-Triggering and Level-Clocking (1994)
Leonard A. Gould, Keith H. Randall
Circuits implemented with two-phase level-clocked latches have the theoretical potential to operate faster and require less state than equivalent circuits implemented with edge-triggered latches. We...
Virtual Networks: Implementation and Analysis (1994)
Programming conventional parallel computers can be a difficult task because intricate measures are required to avoid deadlock. This problem exists because the network does not make any guarantees...
Virtual networks--implementation and analysis (1994)
Randall, Keith H. (Keith Harold)
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1994.
Virtual networks--implementation and analysis (1994)
Randall, Keith H. (Keith Harold)
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1994.
An experimental comparison of edge-triggering and level-clocking / (1993)
Randall, Keith H. (Keith Harold)
Thesis (B.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, and Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1993.
An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms (1970)
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
In this paper, we analyze the performance of parallel multithreaded algorithms that use dag-consistent distributed shared memory. Specifically, we analyze execution time, page faults, and space...
Cilk: An Efficient Multithreaded Runtime System (1970)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou
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...
Cilk: An Efficient Multithreaded Runtime System (1970)
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, Yuli Zhou
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...
Cilk 1.2 (Version Beta 1) Reference Manual (1970)
Robert D. Blumofe, Matteo Frigo, Michael Halbherr, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, ...
This document describes Cilk
Dag-Consistent Distributed Shared Memory (1970)
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
We introduce dag consistency, a relaxed consistency model for distributed shared memory which is suitable for multithreaded programming. We have implemented dag consistency in software for the Cilk...
Detecting Data Races in Cilk Programs that Use Locks (1970)
Mingdong Feng, Charles E. Leiserson, Keith H. Randall, Andrew F. Stark
When two parallel threads holding no locks in common access the same memory location and at least one of the threads modifies the location, a "data race" occurs, which is usually a bug. This paper...
An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms (1970)
Robert D. Blumofe, Matteo Frigo, Christopher F. Joerg, Charles E. Leiserson, Keith H. Randall
In this paper, we analyze the performance of parallel multithreaded algorithms that use dag-consistent distributed shared memory. Specifically, we analyze execution time, page faults, and space...
Cilk: Efficient Multithreaded Computing (1970)
Keith H. Randall, Charles E. Leiserson, H. Randall
This thesis describes Cilk, a parallel multithreaded language for programming contemporary shared memory multiprocessors (SMP's). Cilk is a simple extension of C which provides constructs for...
Using de Bruijn Sequences to Index a 1 in a Computer Word (1970)
Charles E. Leiserson, Harald Prokop, Keith H. Randall
Some computers provide an instruction to find the index of a 1 in a computer word, but many do not. This paper provides a fast and novel algorithm based on de Bruijn sequences to solve this problem....