NDLI: Dynamic parallel tree contraction (extended abstract)

Please wait, while we are loading the content...

An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract)

A comparison of parallel algorithms for connected components

Improved bounds for routing and sorting on multi-dimensional meshes

2d-bubblesorting in average time O(√N lg N)*

Parallel sorting by over partitioning

Efficient compilation of high-level data parallel algorithms

SIMD instruction cache

Improved parity-declustered layouts for disk arrays

Scheduling trees using FIFO queues: a control-memory tradeoff

Studying overheads in massively parallel MIN/MAX-tree evaluation

List ranking and list scan on the Cray C-90

Dynamic parallel tree contraction (extended abstract)

Experiences with parallel N-body simulation

Bandwidth-based lower bounds on slowdown for efficient emulations of fixed-connection networks

AT2 bounds for a class of VLSI problems and string matching

An Ω(√ log log n) lower bound for routing in optical networks

Programming DEC-Alpha based multiprocessors the easy way (extended abstract)

Diffracting trees (preliminary version)

On testing cache-coherent shared memories

Modeling communication in parallel algorithms: a fruitful interaction between theory and systems?

Scheduling parallelizable tasks to minimize average response time

Job scheduling in rings

An analysis of diffusive load-balancing

Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract)

Efficient low-contention parallel algorithms

Constructive deterministic PRAM simulation on a mesh-connected computer

An optical simulation of shared memory

Construction of the mesh and the torus tolerating a large number of faults

O(log2 n) time efficient parallel factorization of dense, sparse separable, and banded matrices

How much can we speedup Gaussian elimination with pivoting?

Efficient algorithms for all-to-all communications in multi-port message-passing systems

An architecture for optimal all-to-all personalized communication

Communication efficient matrix multiplication on hypercubes

A model for multi-grained parallelism (extended abstract)

Increasing network bandwidth on meshes

Bounds on the greedy routing algorithm for array networks

Minimal adaptive routing on the mesh with bounded queue size

Segment router: a novel router design for parallel computers

Dynamic parallel tree contraction (extended abstract)

Content Provider	ACM Digital Library
Author	Reif, John H. Tate, Stephen R.
Abstract	Parallel tree contraction has been found to be a useful and quite powerful tool for the design of a wide class of efficient graph algorithms. We propose a corresponding technique for the parallel solution of incremental problems. As our computational model, we assume a variant of the CRCW PRAM where we can dynamically activate processors by a forking operation.We consider a dynamic binary tree T of ≤ n nodes and unbounded depth. We describe a procedure, which we call the dynamic parallel tree contraction algorithm, which incrementally processes various parallel modification requests and queries:(1)parallel requests to add or delete leaves of T, or modify labels of internal nodes or leaves of T, and also(2) parallel tree contraction queries which require recomputingvalues at specified nodes. Each modification or query is with respect to a set of nodes U in T.Our dynamic parallel tree contraction algorithm is a randomized algorithm that takes O(log(\|U\|log n)) expected parallel time using O(\|U\|log n/log(\|U\|log n) processors. We give a large number of applications (with the same bounds), including:(a) maintaining the usual tree properties (such as number of ancestors, preorder, etc.),(b) Eulerian tour,(c) expression evaluation, (d) least common ancestor, and(e) canonical forms of trees. Previously, there where no known parallel algorithms for incrementally maintaining and solving such problems in parallel time less than &THgr;(log n).In deriving our incremental algorithms, we solve a key subproblem, namely a processor activation problem, within the same asymptotic bounds, which may be useful in the design of other parallel incremental algorithms. This algorithm uses an interesting persistent parallel data structures involving a non-trivial construction.In a subsequent paper, we apply our dynamic parallel tree contraction technique to various incremental graph problems: maintaining various properties, (such as coloring, minimum covering set, maximum matching, etc.). of parallel series graphs, outerplanar graphs, Helin networks, bandwidth-limited networks, and various other graphs with constant separator size.
Starting Page	114
Ending Page	121
Page Count	8
File Format	PDF
ISBN	0897916719
DOI	10.1145/181014.181050
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1994-08-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dynamic parallel tree contraction* (extended abstract).

Dynamic parallel tree contraction (extended abstract) (1994).

Dynamic parallel tree contraction (extended abstract).

Abstract Dynamic Parallel Tree Contraction ∗ (Extended Abstract)

Dynamic parallel tree contraction (1994)

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation

Towards automatic parallelization of tree reductions in dynamic programming

Dynamic Parallel Tree Contraction

Communication-optimal parallel minimum spanning tree algorithms (extended abstract)

Dynamic parallel tree contraction (extended abstract)

Similar Documents

Dynamic parallel tree contraction* (extended abstract).

Dynamic parallel tree contraction (extended abstract) (1994).

Dynamic parallel tree contraction (extended abstract).

Abstract Dynamic Parallel Tree Contraction ∗ (Extended Abstract)

Dynamic parallel tree contraction (1994)

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation

Towards automatic parallelization of tree reductions in dynamic programming

Dynamic Parallel Tree Contraction

Communication-optimal parallel minimum spanning tree algorithms (extended abstract)

Dynamic parallel tree contraction (extended abstract)