Traffic simulation design ideas based on object-oriented programming and modelling theory are used to analyse the datastructure of a simulation system for a traffic network. A traffic network simulation consists of v...
详细信息
ISBN:
(纸本)1845641795
Traffic simulation design ideas based on object-oriented programming and modelling theory are used to analyse the datastructure of a simulation system for a traffic network. A traffic network simulation consists of vehicles, links, intersections and signal controls. By defining the class in C++ language, this paper establishes objects of traffic network units, describes the variables and functions of their members in detail and exactly expresses the relationship between nodes and links in a traffic network. It constructs the shared data of the traffic network simulation based on a standard library function of template and object-classes of the traffic network. It uses SQL database technology to access the parallel data structure. Thus it can reduce the occupation of memory resources and increase the speed of data access. Each simulation unit can access the network data expediently. Finally, by simulating a traffic network made of four intersections in Changchun city, results indicate that the simulation speed increases 2.5 times and the error rate is less than 10%. Hence, a distributed parallel data structure based on object-oriented programming is the foundation for improving speed and for benefiting the traffic network simulation.
We see a resurgence of datalog in a variety of applications, including program analysis, networking, data integration, cloud computing, and security. The large-scale and complexity of these applications need the effic...
详细信息
We see a resurgence of datalog in a variety of applications, including program analysis, networking, data integration, cloud computing, and security. The large-scale and complexity of these applications need the efficient management of data in relations. Hence, datalog implementations require new datastructures for managing relations that (1) are parallel, (2) are highly specialized for datalog evaluation, and (3) can accommodate different workloads depending on the applications concerning memory consumption and computational efficiency. In this article, we present a datastructure framework for relations that is specialized for shared-memory paralleldatalog implementations such as the souffle datalog compiler. The datastructure framework permits a portfolio of different datastructures depending on the workload. We also introduce two concrete parallel data structures for relations, designed for various workloads. Our benchmarks demonstrate a speed-up of up to 6x by using a portfolio of datastructures compared with using a B-tree alone, showing the advantage of our datastructure framework.
Adaptive hp finite element methods (FEM), in which both grid size h and local polynomial order p are dynamically altered, generate computations that require dynamic and irregular patterns of data storage, access and c...
详细信息
Adaptive hp finite element methods (FEM), in which both grid size h and local polynomial order p are dynamically altered, generate computations that require dynamic and irregular patterns of data storage, access and computation, making their parallelization very difficult. We show here that such applications can be parallelized easily if we use a good spatially local ordering of all data for organizing storage, distribution and access, and schedule computation using a "owner-computes" rule. This ordering results in a global index space which can be partitioned to distribute the data, locally used in hashing schemes and B-trees for the necessary dynamic memory management, and used in designing efficient solution schemes. (C) 2000 Elsevier Science B.V. All rights reserved.
A parallel data structure that gives optimized memory layout for problems involving iterative solution of sparse linear systems is developed, and its efficient implementation is presented. The proposed method assigns ...
详细信息
A parallel data structure that gives optimized memory layout for problems involving iterative solution of sparse linear systems is developed, and its efficient implementation is presented. The proposed method assigns a processor to a problem subdomain, and sorts data based on the shared entries with the adjacent subdomains. Matrix-vector-product communication overhead is reduced and parallel scalability is improved by overlapping inter-processor communications and local computations. The proposed method simplifies the implementation of parallel iterative linear equation solver algorithms and reduces the computational cost of vector inner products and matrix-vector products. Numerical results demonstrate very good performance of the proposed technique.
We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such datastructure to efficiently implement a tru...
详细信息
We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such datastructure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of THETA(p) highest priority items and insertions of THETA(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n.
This paper studies parallel algorithms for the longest increasing subsequence (LIS) problem. Let.. be the input size and k be the LIS length of the input. Sequentially, LIS is a simple problem that can be solved using...
详细信息
ISBN:
(纸本)9781450395458
This paper studies parallel algorithms for the longest increasing subsequence (LIS) problem. Let.. be the input size and k be the LIS length of the input. Sequentially, LIS is a simple problem that can be solved using dynamic programming (DP) in O(n log n) work. However, parallelizing LIS is a long-standing challenge. We are unaware of any parallel LIS algorithm that has optimal O(n log n) work and non-trivial parallelism (i.e., (O) over tilde (k) or o(n) span). This paper proposes a parallel LIS algorithm that costs O(n log k) work, (O) over tilde (k) span, and O(n) space, and is much simpler than the previous parallel LIS algorithms. We also generalize the algorithm to a weighted version of LIS, which maximizes the weighted sum for all objects in an increasing subsequence. To achieve a better work bound for the weighted LIS algorithm, we designed parallel algorithms for the van Emde Boas (vEB) tree, which has the same structure as the sequential vEB tree, and supports work-efficient parallel batch insertion, deletion, and range queries. We also implemented our parallel LIS algorithms. Our implementation is light-weighted, efficient, and scalable. On input size 10(9), our LIS algorithm outperforms a highly-optimized sequential algorithm (with O(n log k) cost) on inputs with k <= 3 x 10(5). Our algorithm is also much faster than the best existing parallel implementation by Shen et al. (2022) on all input instances.
暂无评论