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”
Paweł Czarnul, Grzegorz Gołaszewski, Grzegorz Jereczek et al. · 2020
The following topics are dealt with: parallel processing; multiprocessing systems; resource allocation; multi-threading; message passing; application program interfaces; cloud computing; optimisation; program compilers; parallel architectures.
Cited by 1
Joseph Victor Raj, Jane Shirley · Fachbereich Informatik (University of Stuttgart) · 2018
Cited by 0
Zhijia Hu, Masato Takeichi, Hideya Iwasaki · 1998
Data parallelism is currently one of the most successful models for programming massively parallel computers. The central idea is to evaluate a uniform collection of data in parallel by simultaneously manipulating each data element in the collection. Despite many of its promising features, the current approach suffers from two problems. First, the main parallel data structures that most data parallel languages currently support are restricted to simple collection data types like lists, arrays or similar structures. But other useful data structures like trees have not been well addressed. Second, parallel programming relies on a set of parallel primitives that capture parallel skeletons of interest. However, these primitives are not well structured, and efficient parallel programming with these primitives is difficult. In this paper, we propose a polytypic framework for developing efficient parallel programs on most data structures. We showhow a set of polytypic parallel primitives can be formally defined for manipulating most data structures, how these primitives can be successfully structured into a uniform recursive definition, and how an efficient combination of primitives can be derived from a naive specification program. Our framework should be significant not only in development of new parallel algorithms, but also in construction of parallelizing compilers.
Cited by 1
Cyril Crassin · 2012
Joseph Fourier University (UJF), Grenoble, France. ARTIS Team (LJK-INRIA). Dissertation topic: Interactive exploration and rendering of large and detailed volumetric scenes. Working on hierarchical GPU data structures and algorithms for volume raycasting and raytracing of very large animated voxels based scenes (eg. clouds). Main aspects: rendering, volume visibility and large data sets management (out-of-core), GPU complex structures creations, procedural details.
Cited by 0
Elizabeth Johnson · 1996
Introduction Reusable software components are of primary importance for software developers. Unfortunately, until very recently C++ provided no standard basic data structures (such as linked lists and vectors) or algorithms. Instead, each new software project included a development phase for these basic structures. Algorithms would then be created to operate on these structures. If the structures changed, the algorithms needed to be modified. Each programming team also had to be concerned about efficiency of data structure access and algorithms. This problem is particularly acute in the parallel programming realm, where data structures must be built to utilize concurrency whenever possible. With no widely accepted standard of serial data structures, the parallel data structures roam even farther afield. Each new parallel C++ library provides either non-standard tools to build and support data structures or includes a set of specialized data structures. Clearly, if cost-effect
Cited by 0
Robert Bernecky · 1997
Syntax Tree (AST) Tokenized Source APL Source Code subfn main C macros PARALLEL TOKENIZER PARALLEL SYNTAX ANALYZER STATIC SINGLE ASSIGNMENT TRANSFORMER PARALLEL DATA FLOW ANALYZER PARALLEL CODE GENERATOR OSC & CC Figure 1.2: Structure of APEX 6 Chapter 2 Compiler Data Structures Since a compiler is effectively a transformer of data structures, an understanding of its operation will be facilitated by a summary of the salient data structures and files associated with APEX. We will start with an examination of the input file, proceed through intermediate representations, and conclude with the compiler's output file. The data structures used within APEX are numerous, but most of them, being ephemeral, are not germane to a general understanding of APEX structure and operation. A few data structures, however, persist in APEX and serve as the mechanism by which information is passed from phase to phase within the compiler. We now introduce these files and inter-phas...
Cited by 0
P. Wesseling, E. Oñate, J. Périaux (eds et al. · 2008
grid data-structures Abstract. This paper covers a description of the algorithms and data-structures used in the parallel DLR TAU-Code Adaptation tool. Attention is given to the basic algorithms of the parallel anisotropic refinement and de-refinement, as well as the data-structures for distributed grids and grid hierarchy. The parallelization issues for distributed data are discussed along with the dynamic repartitioning and the load-balancing algorithm. To demonstrate the dynamic character of the TAU-Code adaptation, we choose a simulation for a complex aircraft configuration and perform a parallel CFD calculation using varying numbers of CPUs. The obtained results show good parallel scalability with respect to memory and CPU-time consumption. 1
Cited by 0
Venkatesh Kannan, Geoff Hamilton · 2016
Programs that operate over recursive data structures may contain potential parallel computations. Writing parallel programs, even when aided by parallel skeletons, is very challenging, requires intricate analysis of the underlying algorithm and often uses inefficient intermediate data structures. Very few automated parallelisation methods that address a wide range of programs and data types exist. In this paper, we present a transformation method for functional programs defined over any recursive data types. Our method encodes the inputs of a program so that the transformed program is more likely to contain instances of polytypic fold skeletons, and less likely to contain inefficient intermediate data structures. With parallel implementations for these skeletons, the transformed programs can potentially be evaluated on hardware such as multi-core CPUs and/or GPUs.
Cited by 5
Alexandros V. Gerbessiotis, Ros V. Gerbessiotis, Ros V. Gerbessiotis et al. · 1997
In this work we present efficient and practical randomized data structures on the Bulk-Synchronous Parallel (BSP) model of computation along with an experimental study of their performance. In particular, we study data structures for the realization of Parallel Priority Queues (PPQs) and Parallel Dictionaries (PDs). We show that our algorithms are communication efficient and achieve optimality to within small multiplicative constant factors for a wide range of parallel machines. We also present an experimental study of our PPQ algorithms on a variety of parallel platforms, including the SGI Power Challenge and the Cray T3D. Keywords BSP model - randomized algorithms - randomized data structures - hashing - parallel priority queues - parallel dictionaries. The work of the first author was supported in part by EPSRC(UK) under grant GR/K16999, and the second author was supported by a Bodossaki Foundation Graduate Scholarship. 1 Introduction In this work we present an architecture ind...
Cited by 0
H Ikram, Andrew C. Brady, Daniel Anderson et al. · 2025
Dynamic tree data structures maintain a forest while supporting insertion and deletion of edges and a broad set of queries in O(log n) time per operation. Such data structures are at the core of many modern algorithms. Recent work has extended dynamic trees to support batches of requests in parallel, and these parallel batch-dynamic trees are now used in several parallel algorithms.
Cited by 1Open access
Susumu Nishimura · 2006
This paper proposes a modal extension of Separation Logic [8, 11] for reasoning about data-parallel programs that manipulate heap allocated linked data structures. Separation Logic provides a formal means for expressing allocation of disjoint sub-structures, which are to be processed in parallel. A modal operator is also introduced to relate the global property of a parallel operation with the local property of each sequential execution running in parallel. The effectiveness of the logic is demon-strated through a formal reasoning on the parallel list scan algorithm featuring the pointer jumping technique. 1
Cited by 0
Mert Hidayetoğlu, Levent Gürel · 2014
We present two memory reduction methods for the parallel multilevel fast multipole algorithm. One of these methods uses data structures out of core, and the other parallelizes the data structures related to input geometry. With these methods, large-scale electromagnetic scattering problems can be solved on modest parallel computers.
Cited by 5
Joonseon Ahn, Joonseon Ahn, Taisook Han et al. · 2007
Data-parallelism is considered as a paradigm that can solve many difficulties of parallel programming such as portability and readability. But the scope of parallelism is restricted to regular arrays because irregular data lead to irregular communications and their implementation often requires particular effort for balanced data distribution. We propose a data-parallel functional language that handles irregular data structures with recursive types. The language expresses the distribution of recursive data with parallel variables in formal parameter patterns. The parallel executions on distributed data are represented by recursive calls which use parallel variables as parameters. We implement the language based on the vector model. We represent the recursive data structures with a set of vectors and transform operations on each node to vector operations. To transform the parallel recursion to vector operations, we must classify computations of a parallel function based on the condition...
Cited by 0
W. Homer Carlisle · ACM Transactions on Programming Languages and Systems · 1995
In parallel programming languages multityped data structures may be shared by two or more processes. Process I/O to these structures is assumed to be physically interleaved but logically parallel. This article addresses a syntactic mechanism to specify a type for such structures and extends an example language and its type-checking algorithm to these structures.
Cited by 0Open access
Neelakantan Sundaresan, Dennis Gannon · 2007
Data-parallelism is a widely used model for parallel programming. Control structures like parallel DO loops, and data structures like collections have been used to express data-parallelism. In typical implementations, these constructs are ' at ' in the sense that only one data-parallel operation is active at any time. To model applications that can exploit overlap of synchronization and computation in data-parallel tasks, or that have independent but limited data-parallelism, or that depict static or hierarchical nested parallelism, a more dynamic model is required. This paper describes how to combine light-weight thread mechanism with object-oriented methodologies to provide light-weight
Cited by 0
Charlie Hu, Y. Charlie, Hu S. Lennart et al. · 1997
We present a general data parallel formulation for highly irregular problems in High Performance Fortran (HPF). Our formulation consists of (1) a method for linearizing irregular data structures (2) a data parallel implementation (in HPF) of graph partitioning algorithms applied to the linearized data structure, (3) techniques for expressing irregular communication and nonuniform computations associated with the elements of linearized data structures. We demonstrate and evaluate our formulation on a parallel, hierarchical N--body method for the evaluation of potentials and forces of nonuniform particle distributions. Our experimental results demonstrate that efficient data parallel (HPF) implementations of highly nonuniform problems are feasible with the proper language/compiler/runtime support. Our data parallel N--body code provides a much needed "benchmark" code for evaluating and improving HPF compilers. 1 Introduction Data parallel programming provides an effective way to write ...
Cited by 0
Hiroya Matsuba, Motohiko Matsuda, Masatoshi Kawai · 2019
This paper proposes Pyne, a parallel programming framework for developing parallel simulations. Pyne is designed such that parallel applications are developed with sequential programming. Pyne provides a programming environment in which programmers select data structures, define the sequence of operations for the data, and implement some sequential functions to describe the detailed calculation rules for the operations. Pyne automatically creates parallel data structures and performs parallel executions. This paper discusses the programming interface and runtime optimization algorithms that enable the parallel programming model. We evaluated Pyne by implementing a fluid dynamics simulation with both Pyne and a state-of-the-art parallel library. The results show that Pyne succeeds at reducing the code size by 70%, while maintaining performance and scalability.
Cited by 0
Klaus Birken · 1994
The parallel implementation of algorithms based on dynamic data structures on architectures with distributed memory access leads to various technical problems as for data redundancy, consistency and load balancing. The DDD library allows easier development of those dynamic parallel algorithms. This document contains the complete specification of the DDD library interface, including a detailed reference manual, the memory manager specification and a list of DDD errors. Chapter 1 Introduction DDD (short for dynamic distributed data) is a library for implementing parallel programs based on algorithms which use dynamic data structures on MIMD computers. It is based on a corresponding formal model of distributed data structures, which assists the application programmer in designing the distributed structure as well as in developing a correct data parallelization method (cf. [3]). Most of the technical problems of parallel implementations on distributed memory machines (cf. [5]) can be ...
Cited by 0
Jian Nong, Xi He, Jia Chen et al. · Mathematics · 2024
R-tree is an important multi-dimensional data structure widely employed in many applications for storing and querying spatial data. As GPUs emerge as powerful computing hardware platforms, a GPU-based parallel R-tree becomes the key to efficiently port R-tree-related applications to GPUs. However, traditional tree-based data structures can hardly be directly ported to GPUs, and it is also a great challenge to develop highly efficient parallel tree-based data structures on GPUs. The difficulty mostly lies in the design of tree-based data structures and related operations in the context of many-core architecture that can facilitate parallel processing. We summarize our contributions as follows: (i) design a GPU-friendly data structure to store spatial data; (ii) present two parallel R-tree construction algorithms and one parallel R-tree query algorithm that can take the hardware characteristics of GPUs into consideration; and (iii) port the vector map overlay system from CPU to GPU to demonstrate the feasibility of parallel R-tree. Experimental results show that our parallel R-tree on GPU is efficient and practical. Compared with the traditional CPU-based sequential vector map overlay system, our vector map overlay system based on parallel R-tree can achieve nearly 10-fold speedup.
Cited by 1Open access
Nodari Sitchinava, Advisor Michael, T. Goodrich et al. · 2005
Research Interests Computational models for multicores and GPUs, parallel external memory and cache-oblivious algorithms, parallel data structures, energy-efficient computation, distributed processing of massive data Education
Cited by 0