Arrow Research search

Author name cluster

Guy E. Blelloch

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

SODA Conference 2015 Conference Paper

Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel

  • Julian Shun
  • Yan Gu 0001
  • Guy E. Blelloch
  • Jeremy T. Fineman
  • Phillip B. Gibbons

We show that simple sequential randomized iterative algorithms for random permutation, list contraction, and tree contraction are highly parallel. In particular, if iterations of the algorithms are run as soon as all of their dependencies have been resolved, the resulting computations have logarithmic depth (parallel time) with high probability. Our proofs make an interesting connection between the dependence structure of two of the problems and random binary trees. Building upon this analysis, we describe linear-work, polylogarithmic-depth algorithms for the three problems. Although asymptotically no better than the many prior parallel algorithms for the given problems, their advantages include very simple and fast implementations, and returning the same result as the sequential algorithm. Experiments on a 40-core machine show reasonably good performance relative to the sequential algorithms.

Details

FOCS Conference 2007 Conference Paper

Strongly History-Independent Hashing with Applications

  • Guy E. Blelloch
  • Daniel Golovin

We present a strongly history independent (SHI) hash table that supports search in O(l) worst-case time, and insert and delete in O(l) expected time using O(n) data space. This matches the bounds for dynamic perfect hashing, and improves on the best previous results by Naor and league on history independent hashing, which were either weakly history independent, or only supported insertion and search (no delete) each in O(l) expected time. The results can be used to construct many other SHI data structures. We show straightforward constructions for SHI ordered dictionaries: for n keys from {l, .. ., n k } searches take O(log log n) worst-case time and updates (insertions and deletions) O(log log n) expected time, and for keys in the comparison model searches take O(log n) worst-case time and updates O(log n) expected time. We also describe a SHI data structure for the order-maintenance problem. It supports comparisons in O(l) worst-case time, and updates in 0(1) expected time. All structures use O(n) data space.

Details

AAAI Conference 1986 Conference Paper

CIS: A Massively Concurrent Rule-Based System

  • Guy E. Blelloch

Recently researchers have suggested several computational models in which, one programs by specifying large networks of simple devices. Such models are interesting because they go to the roots of concurrency - the circuit level. A problem with the models is that it is unclear how to program large systems and expensive to implement many features that are taken for granted m symbolic programming languages. This paper describes the Concurrent Inference System (CIS), and its implementation on a massively concurrent network model of computation. It shows how much of the functionality of current rule-based systems can be implemented in a straightforward manner within such models. Unlike conventional implementations of rule-based systems in which the inference engine and rule sets are clearly divided at run time, CIS compiles the rules into a large static concurrent network of very simple devices. In this network the rules and inference engine are no longer distinct. The Thinking Machines Corporation, Connection Machine - a 65, 536 processor SIMD computer - is then used to run the network. On the current implementation, real time user system interaction is possible with up to 100, 000 rules.

PDF Details