Brief Announcement: Parallel Depth First vs. Work Stealing Schedulers on CMP Architectures (2009)
Vasileios Liaskovitis, Shimin Chen, Phillip B. Gibbons, Anastassia Ailamaki, Guy E. Blelloch, Babak Falsafi, ...
In chip multiprocessors (CMPs), limiting the number of off-chip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in...
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice (2009)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract—We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference (2009)
Srinath Sridhar, Fumei Lam, Guy E. Blelloch, R. Ravi, Russell Schwartz
Abstract—Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in...
Uniquely Represented Data Structures for Computational Geometry (2009)
Guy E. Blelloch, Daniel Golovin
Abstract. We present new techniques for the construction of uniquely represented data structures in a RAM, and use them to construct efficient uniquely represented data structures for orthogonal...
Space Profiling for Parallel Functional Programs (2009)
Daniel Spoonhower, Guy E. Blelloch, Robert Harper, Phillip B. Gibbons
This paper presents a semantic space profiler for parallel functional programs. Building on previous work in sequential profiling, our tools help programmers to relate runtime resource use back to...
Space Profiling for Parallel Functional Programs (2009)
Daniel Spoonhower, Guy E. Blelloch, Robert Harper, Phillip B. Gibbons
This paper presents a semantic space profiler for parallel functional programs. Building on previous work in sequential profiling, our tools help programmers to relate runtime resource use back to...
Structures General Terms (2009)
Umut A. Acar, Guy E. Blelloch, Robert Harper
We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...
Abstract Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors (2009)
Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, Marco Zagha
This paper considers issues of memory performance in shared memory multiprocessors that provide a high-bandwidth net-work and in which the memory banks are slower than the processors. We are...
Abck W. Aspray, A. G. Bromley, M. Campbell-kelly, P. E. Ceruzzi, W. M. Beynon, ...
technologies for empirical modelling in graphics. In Proc. Eurographics
Abstract Space-E cient Scheduling of Parallelism with Synchronization Variables (2008)
Guy E. Blelloch, Phillip B. Gibbons
Recent work on scheduling algorithms has resulted in provable bounds on the space taken by parallel computations in relation to the space taken by sequential computations. The results for online...
Strongly History-Independent Hashing with Applications (2008)
We present a strongly history independent (SHI) hash table that supports search in O(1) worst-case time, and insert and delete in O(1) expected time using O(n) data space. This matches the bounds for...
Selective Memoization \Lambda (2008)
Umut A. Acar, Guy E. Blelloch, Robert Harper
Abstract We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that...
1 Prefix Sums and Their Applications (2008)
Experienced algorithm designers rely heavily on a set of building blocks and on the tools needed to put the blocks together into an algorithm. The understanding of these basic blocks and tools is...
Compact Dictionaries for Variable-Length Keys and Data, with Applications (2008)
Daniel K. Blandford, Google Inc, Guy E. Blelloch
We consider the problem of maintaining a dynamic dictionary T of keys and associated data for which both the keys and data are bit strings that can vary in length from zero up to the length w of a...
Abstract A Comparison of Sorting Algorithms for the Connection Machine CM-2 (2008)
Guy E. Blelloch, Bruce M. Maggs, C. Greg, Plaxton Stephen, J. Smith, ...
We have implemented three parallel sorting algorithms on the Con-nection Machine Supercomputer model CM-2: B atcher’s bitonic sort, a parallel radix sor ~ and a sample sort similar to Reif and...
Abstract Adaptive Memoization ∗ (2008)
Umut A. Acar, Guy E. Blelloch, Robert Harper
Memoization may be reviewed as a mechanism for re-using a computation—if a function is re-applied to the same argument we may re-use the previous computation to determine the result, rather than...
Room Synchronizations, Guy E. Blelloch, Perry Cheng
We present a class of synchronization called room synchronizations and show how this class can be used to implement asynchronous parallel queues and stacks with constant time access (assuming a...
Abstract A Comparison of Sorting Algorithms for the Connection Machine CM-2 (2008)
Guy E. Blelloch, C. Greg Plaxton, Charles E. Leiserson, Stephen J. Smith, Bruce M. Maggs, Marco Zagha
We have implemented three parallel sorting algorithms on the Connection Machine Supercomputer model CM-2: Batcher's bitonic sort, a parallel radix sort, and a sample sort similar to Reif and...
Abck W. Aspray, A. G. Bromley, M. Campbell-kelly, P. E. Ceruzzi, W. M. Beynon, ...
technologies for empirical modelling in graphics. In Proc. Eurographics
Guy E. Blelloch, Yossi Matias Y, Marco Zagha
For years, the computation rate of processors has been much faster than the access rate of memory banks, and this divergence in speeds has been constantly increasing in recent years. As a result,...
Umut A. Acar, Guy E. Blelloch, Robert Harper
We present techniques for incremental computing by introducing adaptive functional programming. As an adaptive program executes, the underlying system represents the data and control dependences in...
Abstract Scan Primitives for Vector Computers* (2008)
Siddhartha Chatterjee, Guy E. Blelloch
Ibis paper describes an optimized implementation of a set of mm (also called ah-prefix-sums) primitives on a single processor of a CRAY Y-MP, and demonstrates that their use leads to greatly improved...
Abstract Implementation of a Portable Nested Data-Parallel Language (2008)
Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha
This paper gives an overview of the implementation of Nesl, a portable nested data-parallel language. This language and its implementation are the rst to fully support nested data structures as well...
Srinath Sridhar, Guy E. Blelloch, R. Ravi, Russell Schwartz
The production of large quantities of diploid genotype data has created a need for computational methods for largescale inference of haplotypes from genotypes. One promising approach to the problem...
A Semantic Framework for Scheduling Parallel Programs (2008)
Daniel Spoonhower, Guy E. Blelloch, Robert Harper
Abstract. Declarative parallel programs offer deterministic results, allowing the language implementation to schedule parallel tasks in any order. However, program performance hinges crucially on the...
Abstract Implementation of a Portable Nested Data-Parallel Language (2008)
Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha
This paper gives an overview of the implementation of Nesl, a portable nested data-parallel language. This language and its implementation are the rst to fully support nested data structures as well...
Guy E. Blelloch, Omar Ghattas, Gary L. Miller, Noel J. Walkington, James F. Antaki, Bartley P. Griffith, ...
We propose to develop advanced parallel geometric and numerical algorithms and software for simulating complex flows with dynamic interfaces. The development of scalable, parallel highaccuracy...
Brief Announcement: Parallel Depth First vs. Work Stealing Schedulers on CMP Architectures (2008)
Vasileios Liaskovitis, Shimin Chen, Phillip B. Gibbons, Anastassia Ailamaki, Guy E. Blelloch, Babak Falsafi, ...
In chip multiprocessors (CMPs), limiting the number of off-chip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in...
Abstract Adaptive Memoization ∗ (2008)
Umut A. Acar, Guy E. Blelloch, Robert Harper
Memoization may be viewed as a mechanism for re-using a computation—if a function is re-applied to the same argument we may re-use the previous computation to determine the result, rather than...
Self-Adjusting Programming (2008)
Umut Acar Guy, Guy E. Blelloch, Matthias Blume, Robert Harper
This papers proposes techniques for writing self-adjusting programs that can adjust to any change to their data (e.g., inputs, decisions made during the computation) etc. We show that the techniques...
Mixed Integer Linear Programming for Maximum Parsimony Phylogeny Inference (2008)
Srinath Sridhar, Fumei Lam, Guy E. Blelloch, R. Ravi, Russell Schwartz
Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny...
Provably good multicore cache performance for divide-and-conquer algorithms (2008)
Guy E. Blelloch, Rezaul A. Chowdhury, Phillip B. Gibbons, Vijaya Ramachandran, Shimin Chen, Michael Kozuch
This paper presents a multicore-cache model that reflects the reality that multicore processors have both per-processor private (L1) caches and a large shared (L2) cache on chip. We consider a broad...
Space-Efficient Dynamic Orthogonal Point Location, Segment Intersection, and Range Reporting (2008)
We describe an asymptotically optimal data-structure for dynamic point location for horizontal segments. For n line-segments, queries take O(log n) time, updates take O(log n) amortized time and the...
Space Profiling for Parallel Functional Programs (2008)
Daniel Spoonhower, Guy E. Blelloch, Phillip B. Gibbons, Robert Harper
This paper presents a semantic space profiler for parallel functional programs. Building on previous work in sequential profiling, our tools help programmers to relate runtime resource use back to...
Uniquely Represented Data Structures for Computational Geometry (2008)
Guy E. Blelloch, Daniel Golovin, Virginia Vassilevska
We present new techniques for the construction of uniquely represented data structures in a RAM, and use them to construct efficient uniquely represented data structures for orthogonal range queries,...
A new combinatorial approach to sparse graph problems (2008)
Guy E. Blelloch, Virginia Vassilevska, Ryan Williams
Abstract. We give a new combinatorial data structure for representing arbitrary Boolean matrices. After a short preprocessing phase, the data structure can perform fast vector multiplications with a...
Direct maximum parsimony phylogeny reconstruction from genotype data (2007)
Sridhar, Srinath, Lam, Fumei, Blelloch, Guy E, Ravi, R, Schwartz, Russell
Abstract Background Maximum parsimony phylogenetic tree reconstruction from genetic variation data is a fundamental problem in computational genetics with many practical applications in population...
Cvl: A C Vector Library Manual Version 2 (2007)
Guy Blelloch Siddhartha, Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Margaret Reid-miller, Jay Sipelstein, ...
Cvl is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....
Room Synchronizations, Guy E. Blelloch, Perry Cheng
We present a class of synchronization called room synchronizations and show how this class can be used to implement asynchronous parallel queues and stacks with constant time access (assuming a...
Eric J. Schwabe, Guy E. Blelloch, Anja Feldmann, Omar Ghattas, John R. Gilbert, David R. O'hallaron, ...
This paper is a report on ongoing work in developing automated systems for the partitioning, placement, and routing of data that is necessary for the efficient parallel solution of large problems in...
Umut A. Acar, Guy E. Blelloch, Robert Harper
Memoization may be viewed as a mechanism for re-using a computation---if a function is re-applied to the same argument we may re-use the previous computation to determine the result, rather than...
Cvl: ACVector Library Manual Version 2 (2007)
Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Margaret Reid-miller, Jay Sipelstein, Marco Zagha
Cvl is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....
Theory of Computing Systems (2007)
Guy E. Blelloch, Perry Cheng, Phillip B. Gibbons
Abstract. This paper presents a scalable solution to the group mutual exclusion problem, with applications to linearizable stacks and queues, and related problems. Our solution allows entry and exit...
Scheduling threads for constructive cache sharing on CMPs (2007)
Chen, Shimin, Gibbons, Phillip B., Kozuch, Michael, Liaskovitis, Vasileios, Ailamaki, Anastassia, Blelloch, Guy E., ...
Scheduling threads for constructive cache sharing on CMPs (2007)
Shimin Chen, Phillip B. Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia Ailamaki, Guy E. Blelloch, ...
In chip multiprocessors (CMPs), limiting the number of offchip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which...
Efficiently finding the most parsimonious phylogenetic tree via linear programming (2007)
Srinath Sridhar, Fumei Lam, Guy E. Blelloch, R. Ravi
Abstract. Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in...
Strongly history-independent hashing with applications (2007)
We present a strongly history independent (SHI) hash table that supports search in O(1) worst-case time, and insert and delete in O(1) expected time using O(n) data space. This matches the bounds for...
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice (2007)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at most once in...
Algorithms for Analyzing Intraspecific Sequence Variation (2007)
Srinath Sridhar, Guy E. Blelloch, R. Ravi
the official policies, either expressed or implied, of any sponsoring institution, the U.S. government or any other entity
Scheduling threads for constructive cache sharing on CMPs (2007)
Chen, Shimin, Gibbons, Phillip B., Kozuch, Michael, Liaskovitis, Vasileios, Ailamaki, Anastassia, Blelloch, Guy E., ...
In chip multiprocessors (CMPs), limiting the number of offchip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which...
Scheduling threads for constructive cache sharing on CMPs (2007)
Shimin Chen, Phillip B. Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia Ailamaki, Guy E. Blelloch, ...
In chip multiprocessors (CMPs), limiting the number of offchip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in which...
Implementation of a Portable Nested Data-Parallel Language (2006)
Blelloch, Guy E., Chatterjee, Siddhartha, Hardwick, Jonathan C., Sipelstein, Jay, Zagha, Marco
This paper gives an overview of the implementation of NESL, a portable nested data-parallel language. This language and its implementation are the first to fully support nested data structures as...
Parallel depth first vs. work stealing schedulers on CMP architectures (2006)
Liaskovitis, Vasileios, Chen, Shimin, Gibbons, Phillip B., Ailamaki, Anastassia, Blelloch, Guy E., Falsafi, Babak, ...
In chip multiprocessors (CMPs), limiting the number of off-chip cache misses is crucial for good performance. Many multithreaded programs provide opportunities for constructive cache sharing, in...
Kinetic algorithms via self-adjusting computation (2006)
Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, Jorge L. Vittes
Abstract. Define a static algorithm as an algorithm that computes some combinatorial property of its input consisting of static, i.e., non-moving, objects. In this paper, we describe a technique for...
Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees (2006)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract. We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction (2006)
Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Srinath Sridhar
Abstract. We consider the problem of finding a Steiner minimum tree in a hypercube. Specifically, given n terminal vertices in an m dimensional cube and a parameter q, we compute the Steiner minimum...
Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees (2006)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract. We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Traceable Data Structures (2006)
Umut A. Acar, Guy E. Blelloch, Srinath Sridhar, Virginia Vassilevska
We consider the problem of tracking the history of a shared data structure so that a user can efficiently view any previous version of the structure (persistence), and efficiently recover information...
Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction (2006)
Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, Srinath Sridhar
Abstract. We consider the problem of finding a Steiner minimum tree in a hypercube. Specifically, given n terminal vertices in an m dimensional cube and a parameter q, we compute the Steiner minimum...
Kinetic algorithms via self-adjusting computation (2006)
Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, Jorge L. Vittes
Abstract. Define a static algorithm as an algorithm that computes some combinatorial property of its input consisting of static, i.e., non-moving, objects. In this paper, we describe a technique for...
Strongly History Independent Hashing with Deletion (2006)
Guy E. Blelloch, Daniel Golovin
We present a strongly history independent (SHI) hash table that is fast, space efficient, and supports deletions. A hash table that supports deletions is SHI if it has a canonical memory...
An experimental analysis of self-adjusting computation (2006)
Umut A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper
Self-adjusting computation uses a combination of dynamic dependence graphs and memoization to efficiently update the output of a program as the input changes incrementally or dynamically over time....
A New Algorithm for the Reconstruction of (2005)
Kedar Dhamdhere, Srinath Sridhar, Guy E. Blelloch, Eran Halperin, R. Ravi, ...
In this paper, we consider the problem of reconstructing near-perfect phylogenetic trees using binary characters. A perfect phylogeny assumes that every character mutates at most once in the...
A New Algorithm for the Reconstruction of Near-Perfect Binary Phylogenetic Trees (2005)
Kedar Dhamdhere, Srinath Sridhar, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
In this paper, we consider the problem of reconstructing near-perfect phylogenetic trees using binary characters. A perfect phylogeny assumes that every character mutates at most once in the...
Effectively sharing a cache among threads (2004)
Guy E. Belloch, Phillip B. Gibbons, Guy E. Blelloch
OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in
Umut A. Acar, Guy E. Blelloch, Robert Harper
We combine adaptivity and memoization to obtain an incremental computation technique that dramatically improves performance over adaptivity and memoization alone. The key contribution is adaptive...
Dynamizing Static Algorithms, with Applications to Dynamic Trees and History Independence (2004)
Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, Shan Leung
We describe a machine model for automatically dynamizing static algorithms and apply it to historyindependent data structures. Static programs expressed in this model are dynamized automatically by...
An Experimental Analysis of a Compact Graph Representation (2004)
Daniel K. Blandford, Guy E. Blelloch, Ian A. Kash
In previous work we described a method for compactly representing graphs with small separators, which makes use of small separators, and presented preliminary experimental results. In this paper we...
Evaluation of the Haplotype Motif Model using the Principle of Minimum Description (2004)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, R. Ravi, Russell Schwartz
length We apply minimum description length (MDL) principles to evaluate the merit of relaxing the rigidity of block models of haplotype structure. We accomplish this by developing an MDL formulation...
Effectively Sharing a Cache Among Threads (2004)
Guy Blelloch Carnegie, Guy E. Blelloch, Phillip B. Gibbons
We compare the number of cache misses M1 for running a computation on a single processor with cache size C1 to the total number of misses Mp for the same computation when using p processors or...
Umut A. Acar, Guy E. Blelloch, Robert Harper
We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...
Space-efficient finger search on degree-balanced search trees (2003)
Guy E. Blelloch, Bruce M. Maggs, Shan Leung, Maverick Woo
We show how to support the finger search operation on degree-balanced search trees in a space-efficient manner that retains a worst-case time bound of O(log d), where d is the difference in rank...
Compact representations of separable graphs (2003)
Daniel K. Blandford, Guy E. Blelloch, Ian A. Kash
We consider the problem of representing graphs compactly while supporting queries efficiently. In particular we describe a data structure for representing n-vertex unlabeled graphs that satisfy an...
Umut A. Acar, Guy E. Blelloch, Robert Harper
We combine adaptivity and memoization to obtain an incremental computation technique that dramatically improves performance over adaptivity and memoization alone. The key contribution is adaptive...
Umut A. Acar, Guy E. Blelloch, Robert Harper
We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...
Umut Acar Guy, Guy E. Blelloch, Robert Harper
We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...
Space-Efficient Finger Search on Degree-Balanced Search Trees (2003)
Guy E. Blelloch, Bruce M. Maggs
We show how to support the finger search operation on degree-balanced search trees in a space-efficient manner that retains a worst-case time bound of O(log d), where d is the difference in rank...
Umut A. Acar, Guy E. Blelloch, Robert Harper
We combine adaptivity and memoization to obtain an incremental computation technique that dramatically improves performance over adaptivity and memoization alone. The key contribution is adaptive...
Space-efficient finger search on degree-balanced search trees (2003)
Guy E. Blelloch, Bruce M. Maggs, Shan Leung, Maverick Woo
An extended abstract of this paper has appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003. This paper was last revised on April 15, 2003. We show how to support the finger search...
Umut A. Acar, Guy E. Blelloch, Robert Harper
We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...
Compact representations of simplicial meshes in two and three dimensions (2003)
Daniel K. Blandford, Guy E. Blelloch, David E. Cardoze
We describe data structures for representing simplicial meshes compactly while supporting online queries and updates efficiently. Our data structure requires about a factor of five less memory than...
Umut A. Acar, Guy E. Blelloch, Robert Harper
Although memoization is a powerful technique and can dramatically improve performance, it is often difficult to apply effectively. This is because significant performance improvements require the...
Umut Acar Guy, Guy E. Blelloch, Robert Harper
We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...
Compact Representations of Simplicial Meshes in Two and Three Dimensions (2003)
Daniel K. Blandford, Guy E. Blelloch, David E. Cardoze, Clemens Kadow
We describe data structures for representing simplicial meshes compactly while supporting online queries and updates eciently. Our representation requires about a factor of ve less memory than the...
Space-efficient finger search on degree-balanced search trees (2003)
Guy E. Blelloch, Bruce M. Maggs, Shan Leung, Maverick Woo
We show how to support the finger search operation on degree-balanced search trees in a space-efficient manner that retains a worst-case time bound of O(log d), where d is the difference in rank...
Umut A. Acar, Guy E. Blelloch, Robert Harper
We combine adaptivity and memoization to obtain an incremental computation technique that dramatically improves performance over adaptivity and memoization alone. The key contribution is adaptive...
Adaptive functional programming (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...
Adaptive functional programming (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...
Adaptive functional programming (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remained limited in...
Adaptive functional programming (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remained limited in...
Adaptive functional programming (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...
Adaptive functional programming (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation adapts its output to match changes to the input. Many techniques have been proposed for certain classes of adaptive computations, especially for particular applications such...
Adaptive functional programming (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...
Adaptive functional programming (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...
Adaptive Functional Programming \Lambda (2002)
Umut A. Acar, Guy E. Blelloch, Robert Harper
Abstract An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain...
Adaptive Functional Programming (2001)
Umut A. Acar, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remained limited in...
Adaptive Functional Programming (2001)
Umut Acar Guy, Guy E. Blelloch, Robert Harper
An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...
The data locality of work stealing (2000)
This paper studies the data locality of the work-stealing scheduling algorithm on hardware-controlled shared-memory machines. We present lower and upper bounds on the number of cache misses using...
The data locality of work stealing (2000)
This paper studies the data locality of the work-stealing scheduling algorithm on hardware-controlled shared-memory machines. We present lower and upper bounds on the number of cache misses using...
A Parallel Dynamic-Mesh Lagrangian Method For Simulation Of Flows With Dynamic Interfaces (2000)
James F. Antaki, Guy E. Blelloch, Omar Ghattas, Ivan Malcevic, Gary L. Miller, ...
. Many important phenomena in science and engineering, including our motivating problem of microstructural blood flow, can be modeled as flows with dynamic interfaces. The major challenge faced in...
The Data Locality of Work Stealing (2000)
Umut A. Acar, Guy E. Blelloch, Robert D. Blumofe
This paper studies the data locality of the work-stealing scheduling algorithm on hardware-controlled shared-memory machines. We present lower and upper bounds on the number of cache misses using...
The data locality of work stealing (2000)
Umut A. Acar, Guy E. Blelloch, Robert D. Blumofe
This paper studies the data locality of the work-stealing scheduling algorithm on hardware-controlled shared-memory machines, where movement of data to and from the cache is solely controlled by the...
Space-efficient scheduling of nested parallelism (1999)
Girija J. Narlikar, Guy E. Blelloch
Many of today’s high-level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much...
Space-Efficient Scheduling of Nested Parallelism (1999)
Girija J. Narlikar, Guy E. Blelloch
This paper presents an on-line scheduling algorithm that is provably space-efficient and timeefficient for nested parallel languages. For a computation with depth D and serial space requirement S 1 ,...
Parallel Solutions to Geometric Problems on the Scan Model of Computation. (1998)
Blelloch, Guy E., Little, James J.
This paper describes several parallel algorithms that solve geometric problems. The algorithms are based on a vector model of computation - the scan-model. The purpose of this paper is both to show...
Four Vector-Matrix Primitives. (1998)
Agrawal, Ajit, Blelloch, Guy E., Krawitz, Robert L., Phillips, Cynthia A.
This paper discusses a set of powerful primitive matrix operations which allow easy specification of parallel matrix routines. It demonstrates via the hypercube implementation that the additional...
NESL: A Nested Data-Parallel Language (Version 2.6), (1998)
This report describes NESL, a strongly-typed, applicative, data-parallel language. NESL is intended to be used as a portable interface for programming a variety of parallel and vector supercomputers,...
Class Notes: Programming Parallel Algorithms CS 15-840B (Fall 1992), (1998)
Blelloch, Guy E., Hardwick, Jonathan C.
These are the lecture notes for CS 15-840B, a hands-on class in programming parallel algorithms. The class was taught in the fall of 1992 by Guy Blelloch, using the programming, language NESL. It...
Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors, (1998)
Blelloch, Guy E., Heroux, Michael A., Zagha, Marco
In this paper we present a new technique for sparse matrix multiplication on vector multiprocessors based on the efficient implementation of a segmented sum operation. We describe how the segmented...
CVL: A C Vector Library Manual. Version 2, (1998)
Blelloch, Guy E., Hardwick, Jonathan C., Sipelstein, Jay, Chatterjee, Siddhartha, Reid-Miller, Margaret
CVL is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....
List Ranking and List Scan on the CRAY C-90. (1998)
Reid-Miller, Margaret, Blelloch, Guy E.
List ranking and list scan are two primitive operations used in many parallel algorithms that use list, trees, and graph data structures. But vectorizing and parallelizing list ranking is a challenge...
NESL User's Manual (for NESL Version 3.1). (1998)
Blelloch, Guy E., Sipelstein, Jay, Hardwick, Jonathan C., Zagha, Marco
This manual is a supplement to the language definition of NEsL version 3.1. It describes how to use the NEsL system interactively and covers features for accessing on-line help, debugging, profiling,...
NESL: A Nested Data-Parallel Language. (Version 3.1), (1998)
This report describes NESL, a strongly-typed, applicative, data-parallel language. NESL is intended to be used as a portable interface for programming a variety of parallel and vector computers, and...
Pthreads for Dynamic Parallelism, (1998)
Narlikar, Girija J., Blelloch, Guy E.
Expressing a large number of lightweight, parallel threads in a shared address space significantly eases the task of writing a parallel program. Threads can be dynamically created to execute...
An Experimental Analysis of Parallel Sorting Algorithms (1998)
Guy E. Blelloch, C. Greg Plaxton, Charles E. Leiserson, Stephen J. Smith, Bruce M. Maggs, Marco Zagha
We have developed a methodology for predicting the performance of parallel algorithms on real parallel machines. The methodology consists of two steps. First, we characterize a machine by enumerating...
Pthreads for dynamic and irregular parallelism (1998)
Girija J. Narlikar, Guy E. Blelloch
High performance applications on shared memory machines have been typically written in a coarse grained style, with one heavyweight thread per processor. In comparison, programming with a large...
Fast Set Operations Using Treaps (1998)
Guy E. Blelloch, Margaret Reid-miller
We present parallel algorithms for union, intersection and difference on ordered sets using random balanced binary trees (treaps [26]). For two sets of size n and m (m n) the algorithms run in...
Pthreads for Dynamic Parallelism (1998)
Girija J. Narlikar, Guy E. Blelloch
Expressing a large number of lightweight, parallel threads in a shared address space significantly eases the task of writing a parallel program. Threads can be dynamically created to execute...
Accounting for memory bank contention and delay in high-bandwidth multiprocessors (1997)
Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, Marco Zagha
Abstract—For years, the computation rate of processors has been much faster than the access rate of memory banks, and this divergence in speeds has been constantly increasing in recent years. As a...
Pipelining with Futures (1997)
Guy E. Blelloch, Margaret Reid-miller
Pipelining has been used in the design of many PRAM algorithms to reduce their asymptotic running time. Paul, Vishkin and Wagener (PVW) used the approach in a parallel implementation of 2-3 trees....
Space-efficient scheduling of parallelism with synchronization variables (1997)
Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, Girija J. Narlikar
Recent work on scheduling algorithms has resulted in provable bounds on the space taken by parallel computations in relation to the space taken by sequential computations. The results for online...
A framework for space and time efficient scheduling of parallelism (1996)
Girija J. Narlikar, Guy E. Blelloch
Many of today’s high level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much...
Developing a practical projection-based parallel delaunay algorithm (1996)
Guy E. Blelloch, Gary L. Miller, Dafna Talmor
In this paper we are concerned with developing a practical parallel algorithm for Delaunay triangulation that works well on general distributions, particularly those that arise in Scientific...
A framework for space and time efficient scheduling of parallelism (1996)
Girija J. Narlikar, Guy E. Blelloch
Many of today's high level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much...
A Provable Time and Space Efficient Implementation of NESL (1996)
In this paper we prove time and space bounds for the implementation of the programming language Nesl on various parallel machine models. Nesl is a sugared typed -calculus with a set of array...
Guy E. Blelloch, Bruce M. Maggs
t. Hence, an algorithm that takes time t on a P-processor machine performs work W = P t. In either case, the work roughly captures the actual cost to perform the computation, assuming that the cost...
Guy E. Blelloch, Bruce M. Maggs
Introduction The subject of this chapter is the design and analysis of parallel algorithms. Most of today's algorithms are sequential, that is, they specify a sequence of steps in which each...
A Provably Time-Efficient Parallel Implementation of Full Speculation (1996)
Speculative evaluation, including leniency and futures, is often used to produce high degrees of parallelism. Existing speculative implementations, however, may serialize computation because of their...
Programming Parallel Algorithms (1996)
This paper is also available on the World-Wide Web at:
A Framework for Space and Time Efficient Scheduling of Parallelism (1996)
Girija Narlikar Guy, Guy E. Blelloch
Many of today's high level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much...
Space-Efficient Implementation of Nested Parallelism (1996)
Girij J. Narlikar, Guy E. Blelloch
Many of today's high level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much...
Guy E. Blelloch, Bruce M. Maggs
Introduction The subject of this chapter is the design and analysis of parallel algorithms. Most of today's computer algorithms are sequential, that is, they specify a sequence of steps in which...
Programming Parallel Algorithms (1996)
In the past 20 years there have been a huge number of algorithms designed for parallel computers, most which have been designed for one of the variants of the Parallel Random Access Machine (PRAM)...
A Framework for Space and Time Efficient Scheduling of Parallelism (1996)
Girija J. Narlikar, Guy E. Blelloch
Many of today's high level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much...
A Provably Time-Efficient Parallel Implementation of Full Speculation (1996)
Speculative evaluation, including leniency and futures, is often used to produce high degrees of parallelism. Understanding the performance characteristics of such evaluation...
Programming parallel algorithms (1996)
Guy E. Blelloch, Bruce M. Maggs
The subject of this chapter is the design and analysis of parallel algorithms. Most of today’s algorithms are sequential, that is, they specify a sequence of steps in which each step consists of a...
NESL user’s manual (for NESL version 3.1 (1995)
Guy E. Blelloch, Jay Sipelstein, Jonathan C. Hardwick, Marco Zagha
This manual is a supplement to the language de nition of Nesl version 3.1. It describes how to use the Nesl system interactively and covers features for accessing on-line help, debugging, pro ling,...
Provably efficient scheduling for languages with fine-grained parallelism (1995)
Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias
Abstract. Many high-level parallel programming languages allow for fine-grained parallelism. As in the popular work-time framework for parallel algorithm design, programs written in such languages...
NESL User's Manual (For NESL Version 3.1) (1995)
Guy E. Blelloch, Jay Sipelstein, Jonathan C. Hardwick, Marco Zagha
This manual is a supplement to the language definition of NESL version 3.1. It describes how to use the NESL system interactively and covers features for accessing on-line help, debugging, profiling,...
Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors (1995)
Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, Marco Zagha
This paper considers issues of memory performance in shared memory multiprocessors that provide a high-bandwidth network and in which the memory banks are slower than the processors. We are concerned...
School Of, Guy E. Blelloch, Jay Sipelstein, Jonathan C. Hardwick, Marco Zagha
This manual is a supplement to the language definition of Nesl version 3.1. It describes how to use the Nesl system interactively and covers features for accessing on-line help, debugging, profiling,...
NESL: A Nested Data-Parallel Language (Version 3.1) (1995)
This report describes Nesl, a strongly-typed, applicative, data-parallel language. Nesl is intended to be used as a portable interface for programming a variety of parallel and vector computers, and...
Provably Efficient Scheduling for Languages with Fine-Grained Parallelism (1995)
Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias
Many high-level parallel programming languages allow for fine-grained parallelism. As in the popular work-time framework for parallel algorithm design, programs written in such languages can express...
Implementation of a Portable Nested Data-Parallel Language (1994)
Guy Blelloch Siddhartha, Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha
This paper gives an overview of the implementation of NESL, a portable nested data-parallel language. This language and its implementation are the first to fully support nested data structures as...
The Hidden Cost of Low Bandwidth Communication (1994)
Guy E. Blelloch, Bruce M. Maggs, Gary L. Miller
peak and achievable performance. One of the conclusions that can be drawn from these benchmarks is that machines with high communication bandwidth perform well across the board, whereas peak...
Parallel Solutions to Geometric Problems in the Scan Model of Computation (1994)
James J. Little, Guy E. Blelloch, Guy E. Blelloch
This paper describes several parallel algorithms that solve geometric problems. The algorithms are based on a vector model of computation---the scan-model. The purpose of this paper is both to show...
List Ranking and List Scan on the CRAY C-90 (1994)
Margaret Reid-miller, Guy E. Blelloch
List ranking and list scan are two primitive operations used in many parallel algorithms that use list, trees, and graph data structures. But vectorizing and parallelizing list ranking is a challenge...
List Ranking and List Scan on the CRAY C-90 (1994)
List ranking and list scan are two primitive operations used in many parallel algorithms that use list, trees, and graph data structures. But vectorizing and parallelizing list ranking is a challenge...
Implementation of a Portable Nested Data-Parallel Language (1994)
Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha
This paper gives an overview of the implementation of NESL, a portable nested data-parallel language. This language and its implementation are the first to fully support nested data structures as...
All Evaluation of Sorting as a Supercomputer Benchmark (preliminary version) (1993)
Guy E. Blelloch, Leonardo Dagum, Stephen J. Smith, Kurt Thearling, Marco Zagha I
We propose that sorting be considered an important benchmark for both scientific and com-mercial applications of supercomputers. The purpose of a supercomputer benchmark is to exercise various system...
Class notes: Programming parallel algorithms (1993)
Guy E. Blelloch, Jonathan C. Hardwick
These are the lecture notes for CS 15-840B, a hands-on class in programming parallel algorithms. The class was taught in the fall of 1992 by Guy Blelloch, using the programming language NESL. It...
NESL: A nested data-parallel language (version 2.6 (1993)
The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or...
Class notes: Programming parallel algorithms (1993)
Guy E. Blelloch, Jonathan C. Hardwick
These are the lecture notes for CS 15-840B, a hands-on class in programming parallel algorithms. The class was taught in the fall of 1992 by Guy Blelloch, using the programming language NESL. It...
School Of Computer, Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Margaret Reid-miller, Jay Sipelstein, ...
Cvl is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....
Cvl: A C Vector Library - Manual Version 2 (1993)
Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Margaret Reid-miller, Jay Sipelstein, Marco Zagha
CVL is a library of low-level vector routines callable from C. This library includes a wide variety of vector operations such as elementwise function applications, scans, reduces and permutations....
Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors (1993)
Guy E. Blelloch, Michael A. Heroux, Marco Zagha
In this paper we present a new technique for sparse matrix multiplication on vector multiprocessors based on the efficient implementation of a segmented sum operation. We describe how the segmented...
NESL: A Nested Data-Parallel Language (Version 2.6) (1993)
This report describes Nesl, a strongly-typed, applicative, data-parallel language. Nesl is intended to be used as a portable interface for programming a variety of parallel and vector supercomputers,...
Implementation of a Portable Nested Data-Parallel Language (1993)
Guy E. Blelloch, Jonathan C. Hardwick, Jay Sipelstein, Marco Zagha, Siddhartha Chatterjee
This paper gives an overview of the implementation of NESL, a portable nested data-parallel language. This language and its implementation are the first to fully support nested data structures as...
Solving Linear Recurrences with Loop Raking (1992)
Guy E. Blelloch, Siddhartha Chatterjee, Marco Zagha
We present a variation of the partitionmethod for solving m th -order linear recurrences that is well-suited to vector multiprocessors. The algorithm fully utilizes both vector and multiprocessor...
Solving Linear Recurrences with Loop Raking (1992)
Guy Blelloch School, Guy E. Blelloch, Marco Zagha, Siddhartha Chatterjee, Prof Guy, E. Blelloch
We present a variation of the partition method for solving linear recurrences that is wellsuited to vector multiprocessors. The algorithm fully utilizes both vector and multiprocessor capabilities,...
A comparison of sorting algorithms for the connection machine cm-2 (1991)
Guy E. Blelloch, Charles E. Leiserson, Stephen J. Smith, Thinking Machines Corp
Abstract We have evaluated the implementation of many parallel sorting algorithms proposed in the literature. We selected the three most promising and implemented highly tuned versions on the...
A Comparison of Sorting Algorithms for the Connection Machine CM-2 (1991)
Guy Blelloch Carnegie, Guy E. Blelloch, C. Greg Plaxton, Charles E. Leiserson, Stephen J. Smith, Bruce M. Maggs, ...
We have implemented three parallel sorting algorithms on the Connection Machine Supercomputer model CM-2: Batcher's bitonic sort, a parallel radix sort, and a sample sort similar to Reif and...
Size and Access Inference for Data-Parallel Programs (1991)
Siddhartha Chatterjee Guy, Guy E. Blelloch, Allan L. Fisher
Data-parallel programming languages have many desirable features, such as single-thread semantics and the ability to express fine-grained parallelism. However, it is challenging to implement such...
Size and Access Inference for Data-Parallel Programs (1991)
Siddhartha Chatterjee, Guy E. Blelloch, Allan L. Fisher
Data-parallel programming languages have many desirable features, such as single-thread semantics and the ability to express fine-grained parallelism. However, it is challenging to implement such...
Radix Sort For Vector Multiprocessors (1991)
We have designed a radix sort algorithm for vector multiprocessors and have implemented the algorithm on the CRAY Y-MP. On one processor of the Y-MP, our sort is over 5 times faster on large sorting...
A Comparison of Sorting Algorithms for the Connection Machine CM-2 (1991)
Guy E. Blelloch, C. Greg Plaxton, Charles E. Leiserson, Stephen J. Smith, Bruce M. Maggs, Marco Zagha
We have implemented three parallel sorting algorithms on the Connection Machine Supercomputer model CM-2: Batcher's bitonic sort, a parallel radix sort, and a sample sort similar to Reif and...
Collection-Oriented Languages (1991)
Jay Sipelstein, Guy E. Blelloch
Several programming languages arising from widely diverse practical and theoretical considerations share a common high-level feature: their basic data type is an aggregate of other more primitive...
Collection-Oriented Languages (1991)
Jay Sipelstein, Guy E. Blelloch
This research was supported in part by the Defense Advanced Research Projects Agency (DOD) and monitored by the Avionics Laboratory, Air Force Wright Aeronautical Laboratories, Aeronautical Systems...
Scan Primitives for Vector Computers (1990)
Siddhartha Chatterjee, Guy E. Blelloch, Marco Zagha
This paper describes an optimized implementation of a set of scan (also called allprefix -sums) primitives on a single processor of a CRAY Y-MP, and demonstrates that their use leads to greatly...
Prefix Sums and Their Applications (1990)
Experienced algorithm designers rely heavily on a set of building blocks and on the tools needed to put the blocks together into an algorithm. The understanding of these basic blocks and tools is...
VCODE: A Data-Parallel Intermediate Language (1990)
Guy E. Blelloch, Siddhartha Chatterjee
This paper introduces VCODE, an intermediate language for data-parallel computations. VCODE is designed to allow easy porting of data-parallel languages, such as C*, PARALATION LISP, and Fortran 8x,...
Scan primitives and parallel vector models /--Guy E. Blelloch. (1989)
"October 5, 1989."
Parallel Solutions to Geometric Problems on the Scan Model of Computation (1988)
Blelloch, Guy E., Little, James J.
This paper describes several parallel algorithms that solve geometric problems. The algorithms are based on a vector model of computation---the scan-model. The purpose of this paper is both to show...
Parallel Solutions to Geometric Problems on the Scan Model of Computation (1988)
Blelloch, Guy E., Little, James J.
This paper describes several parallel algorithms that solve geometric problems. The algorithms are based on a vector model of computation---the scan-model. The purpose of this paper is both to show...
Scan primitives and parallel vector models / (1988)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1989.
AFL-1 : a programming language for massively concurrent computers / (1986)
Supervised by Thomas Knight.
AFL-1 : a programming language for massively concurrent computers / (1986)
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1986.