Browse Prior Art Database

The Balanced Cube: A Concurrent Data Structure

IP.com Disclosure Number: IPCOM000147855D
Original Publication Date: 1985-Jun-20
Included in the Prior Art Database: 2007-Mar-28
Document File: 40 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Dally, William J.: AUTHOR [+3]

Abstract

William J. Dally Charles L. Seitz June 20. 1985(note: revised from February 1985 version) This paper describe6 the balanced cube, a new data structure for implementing ordered sets. Conventional data etructures such as heaps, balanced trees and B-trees have root bottlenecks which limit their potential concurrency land make them unable to take advantage of the computing potential of concurrent machines. The balanced cube achieves greater concurrency by eliminating the root bottleneck; an operation in the balanced cube can be initiated from any node. The throughput of the bdanced cube on a concurrent computer is o(&) compared with O(1) for a conventional data structure. Operations on the bdanced cube are shown to be deadlock free aud consistent with a sequential execution ordered by completion time. Abstract 1 Introduction The appearance of concurrent computers such as the Caltech Cosmic Cube [I] is creating a need for algorithms and data structures which can exploit concurrency. To date these machines have been employed primarily for numerical calculations where the structure of the data is closely matched to the cormnunications structure of the machine. If these machines are to be applied effectively to non-numerical problems, new data structures and algorithms are required.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 5% of the total text.

Page 1 of 40

The Balanced Cube: A Concurrent Data Structure

William J. Dally Charles L. Seitz

             June 20. 1985
(note: revised from February
1985 version)

Abstract

This paper describe6 the balanced cube, a new data structure for implementing ordered sets. Conventional data etructures such as heaps, balanced trees and B-trees have root bottlenecks which limit their potential concurrency land make them unable to take advantage of the computing potential of concurrent machines. The balanced cube achieves greater concurrency by eliminating the root bottleneck; an operation in the balanced cube can be initiated from any node. The throughput of the bdanced cube on a concurrent computer is

o(&) compared with O(1) for a conventional data structure. Operations on the bdanced cube are shown to be deadlock free aud consistent with a sequential execution ordered by completion time.

[This page contains 1 picture or other non-text object]

Page 2 of 40

[This page contains 1 picture or other non-text object]

Page 3 of 40

1 Introduction

The appearance of concurrent computers such as the Caltech Cosmic Cube [I] is creating a need for algorithms and data structures which can exploit concurrency. To date these machines have been employed primarily for numerical calculations where the structure of the data is closely matched to the cormnunications structure of the machine. If these machines are to be applied effectively to non-numerical problems, new data structures and algorithms are required.

Sequential computers spend a large fraction of their time manipulating ordered sets of data. For th- operations to be performed efficiently on a concurrent computer a new data structure for ordered sets in required. Conventional ordered set data structures such as heaps, balanced trees and B-trees [2] have a single root node through which all operations must pass. Thia root bottleneck limits the potential concurrency of tree structures making them unable to take advantage of the power of concurrent computers. Their maximum throughput is O(1). This paper proposes a new data structure for implementing ordered sets, the balanced cube, which offers significantly improved concurrency.

The balanced cube eliminates the root bottleneck allowing it to achieve a throughput of o(&). Concurrency in the balanced cube ia achieved through uniformity. With the exception of the balancing algorithm, all nodes are equals. An operation may originate at any node and need not pam through a root bottleneck as in a tree structure. In keeping with the spirit of a homogeneous machine, the balanced cube is a homogeneous data structure.

The balanced cube's topology ia well matched to binary n-cube multiprocessors. The bal- anced cube maps members of an ordered set to subcubes of a binary n-cube. A Gray code mapping is used to preserve the linear adjacency of the ordered set in the Hammi...