Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 10,000 papers for “parallel data structures”

Implicitly Synchronized Data Types: Data Structures for Modular Parallel Programming

Martin C. Rinard · 1998

data types promote modular programming by encapsulating state and operations on that state. In parallel environments abstract data types must also encapsulate the concurrency generation and synchronization code required for their correct use and present interfaces that require no information about the global concurrency pattern. An abstract data type is said to be implicitly synchronized if it meets these requirements. Implicitly synchronized abstract data types promote modular parallel software and help programmers manage the complexity of developing parallel programs. This paper defines the concept of implicitly synchronized abstract data types and shows how the implicitly parallel language Jade supports their development and use. Keywords: Parallel programming, abstract data types Over the last decade, research in parallel computer architecture has led to the development of many new parallel machines. Collectively, these machines have the potential to increase dramatically the res...

Cited by 0

Range search in parallel using distributed data structures

Sridhar Radhakrishnan, S. S. Iyengar, S. Rajanarayanan · 2002

The range search problem involves obtaining a set of data points (tuples, records) satisfying a query which specifies a range of values on each dimension, (attribute) of the data. A parallel algorithm for range searching is developed, using the concept of distributed data structures. The range tree proposed by J.L. Bentley (1980) is used as the data structure to be distributed. It is shown that O(log n) search time can be effected for a range search on n three-dimensional points using (2.log/sup 2/n-10.logn+12) processors, and thus is optimal for the range tree distribution. The authors present a nontrivial implementation technique on the hypercube parallel architecture with which the above time and processor bound can be achieved without any communication overhead. The algorithm can easily be generalized for the case of d-dimensional range search.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 5

Fine-grained parallel traversals of irregular data structures

Bin Ren, Gagan Agrawal, James R. Larus et al. · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2012

Fine-grain data parallelism is increasingly common in mainstream processors in the form of long vectors and on-chip GPUs. This paper develops compiler and runtime support to exploit such data parallelism for non-numeric, non-graphic, irregular parallel tasks that perform simple computations while traversing many independent, irregular data structures, like trees and graphs. We vectorize the traversal of trees and graphs by treating a set of irregular data structures as a parallel control-flow graph and compiling the traversal into a domain-specific bytecodes. We produce a SIMD interpreter for these bytecodes, so each lane of a SIMD unit traverses one irregular data structure. Despite the overhead of interpretation, we demonstrate significant increases in single-core performance over optimized baselines.

Cited by 1Open access

HCL: Distributing Parallel Data Structures in Extreme Scales

Hariharan Devarajan, Anthony Kougkas, Keith Bateman et al. · 2020

Most parallel programs use irregular control flow and data structures, which are perfect for one-sided communication paradigms such as MPI or PGAS programming languages. However, these environments lack the presence of efficient function-based application libraries that can utilize popular communication fabrics such as TCP, Infinity Band (IB), and RDMA over Converged Ethernet (RoCE). Additionally, there is a lack of high-performance data structure interfaces. We present Hermes Container Library (HCL), a high-performance distributed data structures library that offers high-level abstractions including hash-maps, sets, and queues. HCL uses a RPC over RDMA technology that implements a novel procedural programming paradigm. In this paper, we argue a RPC over RDMA technology can serve as a high-performance, flexible, and co-ordination free backend for implementing complex data structures. Evaluation results from testing real workloads shows that HCL programs are 2x to 12x faster compared to BCL, a state-of-the-art distributed data structure library.

Cited by 8

Multisearch Techniques: Parallel Data Structures on Mesh-Connected Computers

Frank Dehne Z, Russ Miller X, Mikhail J. Atallah Y et al. · 1996

The multisearch problem is de ned as follows. Given a data structure D modeled as a graph with n constant-degree nodes, perform O(n) searches on D. Let r be the length of the longest search path associated with a search process, and assume that the paths are determined \\on-line&amp;amp;quot;. That is, the search paths may overlap arbitrarily. In this paper, we solve the multisearch problem for certain classes of graphs in O ( p p n n+r log n) time on a p n p n mesh-connected computer. For many data structures, the search path traversed when answering one search query has length r = O(log n). For these cases, our algorithm processes O(n) suchqueries in asymptotically optimal ( p n) time. The classes of graphs we consider contain many of the important

Cited by 0

Data Parallel Programming: Modeling of Some Hierarchic Control Structures

Paolo Cremonesi, Nello Scarabottolo · 2008

This paper constitutes a further step in the analysis of distributed-memory MIMD parallel machines used in dataparallel applications. In particular, this analysis considers the problem of managing the software-level interactions among various processing nodes whenever the program cannot be classified as fully data parallel because it requires some processing of data belonging to different partitions (i.e., assigned to different nodes). In previous papers, it has been shown by the authors that an efficient way of dealing with the above problem is constituted by a hierarchic control structure, decentralizing and parallelizing the management of information exchanges., Various hierarchic control structures have already been modeled in order to identify the most promising ones. In this paper, we adopt closed queuing network models to have a better insight into the expected behavior of the most effective hierarchic control structures. 1.

Cited by 0

Synchronization costs in parallel programs and concurrent data structures

Vitalii Aksenov · theses.fr (ABES) · 2018

To use the computational power of modern computing machines, we have to deal with concurrent programs. Writing efficient concurrent programs is notoriously difficult, primarily due to the need of harnessing synchronization costs. In this thesis, we focus on synchronization costs in parallel programs and concurrent data structures.First, we present a novel granularity control technique for parallel programs designed for the dynamic multithreading environment. Then in the context of concurrent data structures, we consider the notion of concurrency-optimality and propose the first implementation of a concurrency-optimal binary search tree that, intuitively, accepts a concurrent schedule if and only if the schedule is correct. Also, we propose parallel combining, a technique that enables efficient implementations of concurrent data structures from their parallel batched counterparts. We validate the proposed techniques via experimental evaluations showing superior or comparable performance with respect to state-of-the-art algorithms.From a more formal perspective, we consider the phenomenon of helping in concurrent data structures. Intuitively, helping is observed when the order of some operation in a linearization is fixed by a step of another process. We show that no wait-free linearizable implementation of stack using read, write, compare&swap and fetch&add primitives can be help-free, correcting a mistake in an earlier proof by Censor-Hillel et al. Finally, we propose a simple way to analytically predict the throughput of data structures based on coarse-grained locking.

Cited by 2Open access

Improving Between-Shot Fusion Data Analysis with Parallel Structures

C. Nieter · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2005

In the Phase I project we concentrated on three technical objectives to demonstrate the feasibility of the Phase II project: (1) the development of a parallel MDSplus data handler, (2) the parallelization of existing fusion data analysis packages, and (3) the development of techniques to automatically generate parallelized code using pre-compiler directives. We summarize the results of the Phase I research for each of these objectives below. We also describe below additional accomplishments related to the development of the TaskDL and mpiDL parallelization packages.

Cited by 1Open access

Continuous functions and parallel algorithms on concrete data structures

Brookes, S. D., Geva, Shai · KiltHub Repository · 2018

Abstract: "We report progress in two closely related lines of research: the semantic study of sequentiality and parallelism, and the development of a theory of intensional semantics. We generalize Kahn and Plotkin's concrete data structures to obtain a cartesian closed category of generalized concrete data structures and continuous functions. The generalized framework continues to support a definition of sequential functions. Using this ccc as an extensional framework, we define an intensional framework -- a ccc of generalized concrete data structures and parallel algorithms.This construction is an instance of a more general and more widely applicable category-theoretic approach to intensional semantics, encapsulating a notion of intensional behavior as a computational comonad, and employing the co-Kleisli category as an intensional framework. We discuss the relationship between parallel algorithms and continuous functions, and supply some operational intuition for the parallel algorithms. We show that our parallel algorithms may be seen as a generalization of Berry and Curien's sequential algorithms."

Cited by 0Open access