Manish Parashar, James C. Browne · 1995
This paper presents the design and implementation of dynamic distributed data-structures to support parallel adaptive (multigrid) finite difference codes based on hierarchical adaptive mesh-refinement (AMR) techniques for the solution of partial differential equations. The abstraction provided by the datastructures is a dynamic hierarchical grid where operations on the grid are independent of its distribution across processors in a parallel execution environment, and of the number of levels in the grid hierarchy. The distributed dynamic data-structures have been implemented aspart of a computational toolkit for the Binary Black-Hole NSF Grand Challenge project.
Cited by 0
Guoxi Liu, Federico Iuricich · IEEE Transactions on Visualization and Computer Graphics · 2023
Unstructured meshes are characterized by data points irregularly distributed in the Euclidian space. Due to the irregular nature of these data, computing connectivity information between the mesh elements requires much more time and memory than on uniformly distributed data. To lower storage costs, dynamic data structures have been proposed. These data structures compute connectivity information on the fly and discard them when no longer needed. However, on-the-fly computation slows down algorithms and results in a negative impact on the time performance. To address this issue, we propose a new task-parallel approach to proactively compute mesh connectivity. Unlike previous approaches implementing data-parallel models, where all threads run the same type of instructions, our task-parallel approach allows threads to run different functions. Specifically, some threads run the algorithm of choice while other threads compute connectivity information before they are actually needed. The approach was implemented in the new Accelerated Clustered TOPOlogical (ACTOPO) data structure, which can support any processing algorithm requiring mesh connectivity information. Our experiments show that ACTOPO combines the benefits of state-of-the-art memory-efficient (TTK CompactTriangulation) and time-efficient (TTK ExplicitTriangulation) topological data structures. It occupies a similar amount of memory as TTK CompactTriangulation while providing up to 5x speedup. Moreover, it achieves comparable time performance as TTK ExplicitTriangulation while using only half of the memory space.
Cited by 8
Erez Petrank · 2012
The complexity of parallel data structures is often measured by two major factors: the throughput they provide and the progress they guarantee. Progress guarantees are particularly important for systems that require responsiveness such as real-time systems, operating systems, interactive systems, etc. Notions of progress guarantees such as lock-freedom, wait-freedom, and obstruction-freedom that provide different levels of guarantees have been proposed in the literature [4, 6]. Concurrent access (and furthermore, optimistic access) to shared objects makes the management of memory one of the more complex aspects of concurrent algorithms design. The use of automatic memory management greatly simplifies such algorithms [11, 3, 2, 9]. However, while the existence of lock-free garbage collection has been demonstrated [5], the existence of a practical automatic memory manager that supports lock-free or wait-free algorithms is still open. Furthermore, known schemes for manual reclamation of unused objects are difficult to use and impose a significant overhead on the execution [10].
Cited by 7
Maassen, A. · RWTH Publications (RWTH Aachen) · 1992
Cited by 0
Aleksandar Prokopec · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2014
LAMP1
Cited by 15Open access
., Mads Ruben Burgdorff Kristensen, ., Brian Vinter · Open Journal Systems (Global Science & Technology Forum) · 2014
In this paper, we introduce a model for managing abstract data structures that map to arbitrary distributed memory architectures.It is difficult to achieve scalable performance in data-parallel applications where the programmer manipulates abstract data structures rather than directly manipulating memory.On distributed memory architectures such abstract data-parallel operations may require communication between nodes.Therefore, the underlying system has to handle communication efficiently without any help from the user.Our data model splits data blocks into two sets --local data and remote data --and schedules the sub-block by availability at runtime.We implement the described model in DistNumPy --a highproductivity programming library for Python.We go on to evaluate the implementation using a representative distributed memory system --a Cray XE-6 Supercomputer --up to 2048 cores.The benchmarking results demonstrate scalable good performance.
Cited by 0Open access
Mads Ruben Burgdorff Kristensen, Brian Vinter · Research at the University of Copenhagen (University of Copenhagen) · 2012
In this paper, we introduce a model for managing abstract data structures that map to arbitrary distributed memory architectures. It is difficult to achieve scalable performance in data-parallel applications where the programmer manipulates abstract data structures rather than directly manipulating memory. On distributed memory architectures such abstract data-parallel operations may require communication between nodes. Therefore, the underlying system has to handle communication efficiently without any help from the user. Our data model splits data blocks into two sets -- local data and remote data -- and schedules the sub-block by availability at runtime. We implement the described model in DistNumPy -- a high-productivity programming library for Python. We go on to evaluate the implementation using a representative distributed memory system -- a Cray XE-6 Supercomputer -- up to 2048 cores. The benchmarking results demonstrate scalable good performance.
Cited by 0
Yanda Chen, Chen Zhao, Yu Zhou et al. · arXiv (Cornell University) · 2024
Pre-trained language models (LMs) are capable of in-context learning (ICL): they can adapt to a task with only a few examples given in the prompt without any parameter update. However, it is unclear where this capability comes from as there is a stark distribution shift between pre-training text and ICL prompts. In this work, we study what patterns of the pre-training data contribute to ICL. We find that LMs' ICL ability depends on $\textit{parallel structures}$ in the pre-training data -- pairs of phrases following similar templates in the same context window. Specifically, we detect parallel structures by checking whether training on one phrase improves prediction of the other, and conduct ablation experiments to study their effect on ICL. We show that removing parallel structures in the pre-training data reduces LMs' ICL accuracy by 51% (vs 2% from random ablation). This drop persists even when excluding common patterns such as n-gram repetitions and long-range dependency, showing the diversity and generality of parallel structures. A closer look at the detected parallel structures indicates that they cover diverse linguistic tasks and span long distances in the data.
Cited by 0Open access
Guy E. Blelloch, Yan Gu, Julian Shun et al. · 2018
In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by emerging non-volatile memory technologies with read performance being close to that of random access memory but writes being significantly more expensive in terms of energy and latency. We design algorithms for planar Delaunay triangulation, k -d trees, and static and dynamic augmented trees. Our algorithms are designed in the recently introduced Asymmetric Nested-Parallel Model, which captures the parallel setting in which there is a small symmetric memory where reads and writes are unit cost as well as a large asymmetric memory where writes are $ømega$ times more expensive than reads. In designing these algorithms, we introduce several techniques for obtaining write-efficiency, including DAG tracing, prefix doubling, and α-labeling, which we believe will be useful for designing other parallel write-efficient algorithms.
Cited by 13Open access
Brookes, S. D., Geva, Shai · KiltHub Repository · 2018
Abstract: "Building on Kahn and Plotkin's theory of concrete data structures and sequential functions, Berry and Curien defined an intensional model of sequential algorithms between concrete data structures. In this paper we report on an attempt to develop a similar intensional model of concurrent computation. We present a notion of parallel algorithm between concrete data structures, together with suitable application and currying operations. We define an intensional strictness ordering on parallel algorithms, with respect to which application is well behaved (at first order types).We define the input-output function computed by a parallel algorithm, and we show that every parallel algorithm computes a continuous function. Thus, a parallel algorithm may be viewed as a continuous function together with a parallel computation strategy. In contrast, a Berry-Curien sequential algorithm may be viewed as a sequential function together with a sequential computation strategy. The intensional strictness ordering on parallel algorithms corresponds to the pointwise ordering on the functions they compute, in the same sense that the set inclusion ordering used by Berry and Curien on sequential algorithms corresponds to the stable ordering on the functions they compute.We believe that the ideas and results presented here constitute a first step towards a fuller understanding of the intensional semantics of parallelism, even though the model presented here is not yet general enough to provide a satisfactory account of higher order algorithms, and lacks a notion of composition for algorithms. We present some ideas for overcoming these deficiencies, and some directions for further research."
Cited by 0Open access
Grün, S. · JuSER (Forschungszentrum Jülich) · 2012
Cited by 0
Arman Safarnejadian, Wei Shi, Leslie A. Rusch et al. · 2024
We use a nonlinear frequency-dependent digitalto-analog converter model to study performance versus parallelization. We contrast shared and multiple sources, we quantify trade-offs in signal-to-noise ratio, phase noise, and distortion for 1.6 Tb/s at 28.7-115.3 Gbaud.
Cited by 1
Antal Tátrai · ELTE Digital Institutional Repository (EDIT) (Eötvös Loránd University) · 2012
Bibliogr.: fol. 84-86., PhD ertekezes, Eotvos Lorand Tudomanyegyetem (Budapest), 2012, Osszefoglalas angol es magyar nyelven
Cited by 0Open access
Aleksandar Prokopec, Dmitry Petrashko, Martin Odersky · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2014
With the rise of multicores, there is a trend of supporting data-parallel collection operations in general purpose programming languages. These operations are highly parametric, incurring abstraction performance penalties. Furthermore, data-parallel operations must scale when applied to irregular workloads. Work-stealing is a proven technique for load balancing irregular workloads, but general purpose work-stealing also suffers abstraction penalties. We present a generic data-parallel collections design based on work-stealing for shared-memory architectures that overcomes abstraction penalties through callsite specialization of data-parallel operation instances. Moreover, we introduce \\textit{work-stealing iterators} that allow fine-grained and efficient work-stealing for particular data-structures. By eliminating abstraction penalties and making work-stealing data-structure-aware we achieve up to 60x better performance compared to JVM-based approaches and 3x speedups compared to tools such as Intel TBB.
Cited by 10Open access
Silesian Digital Library (Silesian Library) · 2007
Cited by 0
Qi Hua, Nail A. Gumerovb, Ramani Duraiswamia · 2016
We present efficient algorithms to build data structures and the lists needed for fast multipole methods. The algorithms are capable of being efficiently implemented on both serial, data parallel GPU and on distributed architectures. With these algorithms it is possible to map the FMM efficiently on to the GPU or distributed heterogeneous CPU-GPU systems. Further, in dynamic problems, as the distribution of the particles change, the reduced cost of building the data structures improves performance. Using these algorithms, we demonstrate example high fidelity simulations with large problem sizes by using FMM on both single and multiple heterogeneous computing facilities equipped with multi-core CPU and many-core GPUs.
Cited by 0
Brock, Benjamin Acker · eScholarship (California Digital Library) · 2022
Running programs across multiple nodes in a cluster of networked computers, such as in a supercomputer or commodity datacenter system,is increasingly important across multiple domains, including data science, machine learning, and scientific computing. This is brought on by a combination of increasing data sizes, which push beyond the memory capacity of a single node, and increasing computational demands from new, more elaborate simulations, models, and applications.However, writing parallel programs for clusters of computers remains a difficult task, particularly for programs that are irregular in terms ofdata distribution or access pattern. Many parallel programs today are still written using communication libraries like MPI or OpenSHMEM, which require users to explicitly manage low-level details. While high-level parallel programming languages and libraries do exist, and these can make implementing certain types of programs much easier, developers often have to expend significant effort building custom infrastructure and data structures for their applications.This thesis argues that a large part of the reason why parallel programming remains difficult is a lack of high-level distributed data structures analogous to the data structures that have become ubiquitous in sequential programming environments like C++ and Python. These especially include irregular data structures like hash tables and queues that may require fine-grained memory accesses along with synchronization. This thesis examines techniques for building high-level, cross-platform distributed data structures using one-sided remote memory operations like remote put, remote get, and remote atomics. These memory access primitives allow for a high degree of asynchrony, enabling better performance by removing synchronization bottlenecks and allowing a high degree of overlap between communication and computation. They can also be efficiently executed directly by the network hardware in modern supercomputer and commodity datacenter networks, removing the need to synchronize with remote processes.This thesis examines several RDMA-based distributed data structures, including hash tables, Bloom filters, queues, and dense and sparse matrices. We provide a performance model for evaluating the cost of RDMA-based distributed data structure methods in terms of their component remote memory operations, and demonstrate how this model can be extended to support GPUs in addition to conventional CPUs.
Cited by 0
Yanda Chen, Chen Zhao, Zhou Yu et al. · 2024
Pre-trained language models (LMs) are capable of in-context learning (ICL): they can adapt to a task with only a few examples given in the prompt without any parameter update.However, it is unclear where this capability comes from as there is a stark distribution shift between pre-training text and ICL prompts.In this work, we study what patterns of the pretraining data contribute to ICL.We find that LMs' ICL ability depends on parallel structures in the pre-training data-pairs of phrases following similar templates in the same context window.Specifically, we detect parallel structures by checking whether training on one phrase improves prediction of the other, and conduct ablation experiments to study their effect on ICL.We show that removing parallel structures in the pre-training data reduces LMs' ICL accuracy by 51% (vs 2% from random ablation).This drop persists even when excluding common patterns such as n-gram repetitions and long-range dependency, showing the diversity and generality of parallel structures.A closer look at the detected parallel structures indicates that they cover diverse linguistic tasks and span long distances in the data.
Cited by 1Open access
Ivan Tsmots, V.Ya. Antoniv · Scientific Bulletin of UNFU · 2016
Сформовано вимоги і вибрано інтегрований підхід до розроблення НВІС-пристроїв сортування чисел, який охоплює розроблення паралельних алгоритмів сортування масивів чисел методом вставки та нових НВІС-структур пристроїв для їх реалізації. Удосконалено алгоритми сортування масивів чисел методом вставки, розроблено узгоджені потокові графи алгоритмів сортування масивів чисел методом вставки, особливістю яких є можливість змінювати інтенсивність сортування чисел вибором кількості каналів і розрядності надходження чисел. Синтезовано паралельні і паралельно-потокові НВІС-структури сортування чисел методом вставки та визначено їх швидкодію.
Cited by 4Open access
Science September October, David Kranz, Donald Yeung et al. · 1992
In Proceedings of 'econd Workshop on Languages, Compilers, and Run-Time Environments for Distributed Memory Multiprocessors, October 1992.
Cited by 0