2008
Operations on basic data structures such as queues, prior-ity queues, stacks, and counters can dominate the execution time of a parallel program due to their frequency and their coordination and contention overheads. There are consid-erable performance payoffs in developing highly-optimized, asynchronous, distributed, cache-conscious, parallel imple-mentations of such data structures. Such implementations may employ a variety of tricks to reduce latencies and avoid serial bottlenecks, as long as the semantics of the data struc-ture are preserved. The complexity of the implementation and the difficulty in reasoning about asynchronous systems increases concerns regarding possible bugs in the implemen-tation. In this paper, we consider black box procedures for test-ing whether a parallel data structure behaved correctly. We present the first systematic study of algorithms and hard-ness results for such testing procedures, focusing on queues, priority queues, stacks, and counters, under various impor-tant scenarios. Our results demonstrate the importance of selecting test data such that distinct values are inserted into the data structure (as appropriate). In such cases, we present an O(n) time algorithm for testing linearizable queues, an O(nlog n) time algorithm for testing lineariz-able priority queues, and an O(np’) time algorithm for test-ing non-linearizable queues, where n is the number of data structure operations and p is the number of processors. In contrast, we show that testing such data structures for exe-cutions with arbitrary input values is NP-complete. Our re-sults also help clarify the thresholds between scenarios that admit polynomial time solutions and those that are NP-complete. Our algorithms are the first nontrivial algorithms for these problems.
Cited by 0
Chengcheng Yu, Fan Xia, Qunyan Zhang et al. · Lecture notes in computer science · 2014
Cited by 2
Andrew Rau-chaplin · 1990
Abstract, In this paper, we study the problem of implementing standard data structures on a hypercube multiprocessor. We present a technique for fficiently executing multiple independant search processes on a class of graphs called ordered h-level graphs. We show how this technique can be utilized to implement a segment tree on a hypercube, thereby obtainig O(logZn) time algorithms for sotving the next element search problem, the trapezoidal decomposition probtem, the triangulation problem, and the (multiple) planar point location problem. 1
Cited by 0
Justin R. Porter, Maxwell I. Zimmerman, Gregory R. Bowman · The Journal of Chemical Physics · 2019
Markov state models (MSMs) are quantitative models of protein dynamics that are useful for uncovering the structural fluctuations that proteins undergo, as well as the mechanisms of these conformational changes. Given the enormity of conformational space, there has been ongoing interest in identifying a small number of states that capture the essential features of a protein. Generally, this is achieved by making assumptions about the properties of relevant features-for example, that the most important features are those that change slowly. An alternative strategy is to keep as many degrees of freedom as possible and subsequently learn from the model which of the features are most important. In these larger models, however, traditional approaches quickly become computationally intractable. In this paper, we present enspara, a library for working with MSMs that provides several novel algorithms and specialized data structures that dramatically improve the scalability of traditional MSM methods. This includes ragged arrays for minimizing memory requirements, message passing interface-parallelized implementations of compute-intensive operations, and a flexible framework for model construction and analysis.
Cited by 62Open access
Sankardeep Chakraborty, Seungbum Jo, Kunihiko Sadakane et al. · Lecture notes in computer science · 2021
Cited by 5
Karl Fürlinger, Tobias A. Fuchs, Roger Kowalewski · arXiv (Cornell University) · 2016
We present DASH, a C++ template library that offers distributed data\nstructures and parallel algorithms and implements a compiler-free PGAS\n(partitioned global address space) approach. DASH offers many productivity and\nperformance features such as global-view data structures, efficient support for\nthe owner-computes model, flexible multidimensional data distribution schemes\nand inter-operability with STL (standard template library) algorithms. DASH\nalso features a flexible representation of the parallel target machine and\nallows the exploitation of several hierarchically organized levels of locality\nthrough a concept of Teams. We evaluate DASH on a number of benchmark\napplications and we port a scientific proxy application using the MPI two-sided\nmodel to DASH. We find that DASH offers excellent productivity and performance\nand demonstrate scalability up to 9800 cores.\n
Cited by 0Open access
Frank Dehne, Andrew Rau‐Chaplin · Lecture notes in computer science · 1990
Cited by 4
V. N. Chugunov, Yuri Vassilevski · Russian Journal of Numerical Analysis and Mathematical Modelling · 2003
A parallel version of a multigrid method [Z. Chen, On the convergence of Galerkin-multigrid methods for nonconforming finite elements. East-West J. Numer. Math. (1999) 7, No. 2, 79–104.] for a face-oriented nonconforming finite element space is considered. Primary attention is focused on a data structure providing simple implementation. In particular, a technique of parallelization is derived in a logically consistent way from a set of a priori formulated requirements to the parallel implementation.
Cited by 1
Constantin Siniolkis · Oxford University Research Archive (ORA) (University of Oxford) · 1998
<p>The objective of this thesis is the unified investigation of a wide range of fundamental parallel methods that are transportable amongst pragmatic parallel machines having different number of processors, different periodicity of global synchronization and different bandwidth of inter-processor communication. The computational model adopted is the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of parallel machines into three numerical parameters <em>p</em>, <em>L</em> and <em>g</em>, that quantify, respectively, processors, periodicity and bandwidth - the model differentiates memory that is local to a processor from memory that is non-local, yet, for the sake of universality, does not differentiate network proximity. The BSP parameters <em>p</em>, <em>L</em> and <em>g</em>, together with the problem size <em>n</em>, are employed to measure the performance, and consequently, the transportability of parallel methods across machines having different values of these parameters.</p> <p>We show that optimality to within small multiplicative constant factors close to <em>one</em> can be achieved for a multiplicity of fundamental computational problems by transportable algorithms and data structures that can be applied for a wide range of values of the BSP parameters. While these algorithms and data structures are fairly simple themselves, description of their performance in terms of these parameters is somewhat complicated. The main reward for quantifying these complications, is that it enables software to be written once and for all that can be migrated efficiently amongst a variety of parallel machines. The methods considered in this thesis - both theoretically and experimentally - embody deterministic and randomized techniques for the efficient realization of fundamental algorithms (broadcasting, computing parallel-prefixes, load-balancing, list-contracting, merging, sorting, integer-sorting, selecting, searching and hashing), data structures (heaps, search trees and hash tables) and applications (computational geometry, parallel model simulations and structured query language primitives).</p>
Cited by 0Open access
Constantin Siniolkis · Oxford University Research Archive (ORA) (University of Oxford) · 1998
The objective of this thesis is the unified investigation of a wide range of fundamental parallel methods that are transportable amongst pragmatic parallel machines having different number of processors, different periodicity of global synchronization and different bandwidth of inter-processor communication. The computational model adopted is the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of parallel machines into three numerical parameters <em>p</em>, <em>L</em> and <em>g</em>, that quantify, respectively, processors, periodicity and bandwidth - the model differentiates memory that is local to a processor from memory that is non-local, yet, for the sake of universality, does not differentiate network proximity. The BSP parameters <em>p</em>, <em>L</em> and <em>g</em>, together with the problem size <em>n</em>, are employed to measure the performance, and consequently, the transportability of parallel methods across machines having different values of these parameters. We show that optimality to within small multiplicative constant factors close to <em>one</em> can be achieved for a multiplicity of fundamental computational problems by transportable algorithms and data structures that can be applied for a wide range of values of the BSP parameters. While these algorithms and data structures are fairly simple themselves, description of their performance in terms of these parameters is somewhat complicated. The main reward for quantifying these complications, is that it enables software to be written once and for all that can be migrated efficiently amongst a variety of parallel machines. The methods considered in this thesis - both theoretically and experimentally - embody deterministic and randomized techniques for the efficient realization of fundamental algorithms (broadcasting, computing parallel-prefixes, load-balancing, list-contracting, merging, sorting, integer-sorting, selecting, searching and hashing), data structures (heaps, search trees and hash tables) and applications (computational geometry, parallel model simulations and structured query language primitives).
Cited by 0Open access
Kunal Agrawal, Jeremy T. Fineman, Kefu Lu et al. · 2014
Although concurrent data structures are commonly used in practice on shared-memory machines, even the most efficient concurrent structures often lack performance theorems guaranteeing linear speedup for the enclosing parallel program. Moreover, efficient concurrent data structures are difficult to design. In contrast, parallel batched data structures do provide provable performance guarantees, since processing a batch in parallel is easier than dealing with the arbitrary asynchrony of concurrent accesses. They can limit programmability, however, since restructuring a parallel program to use batched data structure instead of concurrent data structure can often be difficult or even infeasible.
Cited by 26
Hancheng Wang, Haipeng Dai, S. J. Chen et al. · IEEE Transactions on Parallel and Distributed Systems · 2025
Approximate membership query (AMQ) data structures can approximately determine whether an element exists in a given dataset. They are widely used in parallel and distributed systems (e.g., high-performance databases, distributed cache systems, and bioinformatics systems) to avoid unnecessary dataset accesses, thereby accelerating massive data processing. For AMQ data structures used in the above systems, achieving high throughput, low false positive rate, and large capacity objectives simultaneously is critical but challenging. Porting AMQ data structures from DRAM to persistent memory makes it possible to achieve the above three objectives simultaneously, but this porting is not a trivial task. Specifically, existing AMQ data structures generate numerous random accesses and/or sequential writes on persistent memory, resulting in poor throughput. Therefore, in the conference version of this paper, we proposed a novel AMQ data structure called wormhole filter, which achieves high throughput on persistent memory, thereby achieving the above three objectives simultaneously. In this journal version, we extend our prior work by introducing parallel wormhole filters to enhance parallel performance. Additionally, we integrate parallel wormhole filters into the LevelDB database system to show that porting AMQ data structures to persistent memory significantly improves system endto-end throughput. Theoretical analysis and experimental results show that wormhole filters significantly outperform state-of-theart AMQ data structures. For example, wormhole filters achieve 12.06× insertion throughput, 1.98× positive lookup throughput, and 8.82× deletion throughput of the best competing baseline.
Cited by 1
Christophe Jaillet, Michaël Krajecki · Lecture notes in computer science · 2008
Cited by 1
Amr F. Fahmy, Robert A. Wagner · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · 1995
We present algorithms for the transportation of data in parallel and distributed systems that would enable programmers to transport or distribute a data structure by issuing a function call. Such a functionality is needed if programming distributed memory systems is to become commonplace. The distribution problem is defined as follows. We assume that n records of a data structure are scattered among p processors where processor qi holds ri records, 1 ≤ i ≤ p. The problem is to redistribute the records so that each processor holds [n/p] records. We solve the problem in the minimum number of parallel data-permutation operations possible, for the given initial record distribution. This means that we use max(mxr - [n/p], [n/p] - mnr) parallel data transfer steps, where mxr = max(ri) and mnr = min(ri) for 1 ≤ i ≤ p. Having solved the distribution problem, it then remains to transport the data structure from the memory of one processor to another. In the case of dynamically allocated data structures, we solve the problem of renaming pointers by creating an intermediate name space. We also present a transportation algorithm that attempts to hide the cost of making a local copy for the data structure which, is necessary since the data structure could be scattered in the memory of the sender.
Cited by 0Open access
Hoefler, K., Mueller, M., Schwarzer, S. (Stuttgart Univ. (Germany). Inst. fuer Computeranwendungen) et al. · OpenGrey (Institut de l'Information Scientifique et Technique) · 2000
Cited by 0
Hogen, G., Loogen, R. · RWTH Publications (RWTH Aachen) · 1992
Cited by 0
Raffaele Giancarlo, Roberto Grossi · Journal of Complexity · 1999
Cited by 0
Van‐Dat Cung, Salah Dowaji, Bertrand LeCun et al. · DIMACS series in discrete mathematics and theoretical computer science · 1997
Cited by 13
Shigeru Kusakabe, Taku Nagai, Kentaro Inenaga et al. · 2002
Dataflow-based fine-grain parallel data-structures provide high-level abstraction to easily write programs with potentially high parallelism. In order to show the feasibility of a fine-grain dataflow paradigm, we implement a non-strict dataflow language on off-the-shelf computers, including a distributed-memory parallel machine. The results of preliminary experiments indicate that the inefficiency related to fine-grain parallel arrays in the naive distributed-memory implementation is mainly caused by the address generation for distributed data. To reduce overhead, we introduce a two-level table addressing technique that can efficiently generate addresses. The results of performance evaluation indicate that this technique is useful to improve the performance at a practical level even on off-the-shelf computers.
Cited by 0
R. Kothe, H.T. Vierhaus · 2010
Test technologies for integrated circuits have traditionally tried to maximise test data compression rates, because these are essential for keeping test time and costs low. However, power consumption during the test process is a problem that has been addressed on recently. Excessive power consumption may result in thermal stress and increased voltage drops within the circuit, which implies increasing signal delays. Thereby even fully-functional circuits may fail during delay testing. Therefore, in this paper a flexible concept is proposed which combines test pattern compression using a scan controller concept and reduction of power consumption during the fast capture cycles of transition delay tests. Essentially, this concept consists of a Greedy algorithm, which fills X-rich pattern with 0s or 1s step-by-step, and an event-driven logic and power consumption simulator, which calculates the costs of these steps. The implemented concept is applied to X-rich test sets of ISCAS'89, ITC'99 benchmarks and OpenSparc cores. Results show a best case with 96 percent test data reduction combined with 32 percent less peak capture power. With this concept it is also possible to reduce the peak power for shift-in, launch and shift-out cycles by over 50 percent.
Cited by 2