Search

Nearly thirty years ago, it was shown that \(\Omega (\sqrt {n})\) read/write registers are needed to solve randomized wait-free consensus among n processes. This lower bound was improved to n registers in 2018, which exactly matches known algorithms. The \(\Omega (\sqrt {n})\) space complexity lower bound actually applies to a class of objects called historyless objects, which includes registers, test-and-set objects, and readable swap objects. However, every known n-process obstruction-free consensus algorithm from historyless objects uses Ω (n) objects. In this paper, we give the first Ω (n) space complexity lower bounds on consensus algorithms for two kinds of historyless objects. First, we show that any obstruction-free consensus algorithm from swap objects uses at least n-1 objects. More generally, we prove that any obstruction-free k-set agreement algorithm from swap objects uses at least \(\lceil \frac{n}{k}\rceil - 1\) objects. The k-set agreement problem is a generalization of consensus in which processes agree on no more than k different output values. This is the first non-constant lower bound on the space complexity of solving k-set agreement with swap objects when k > 1. We also present an obstruction-free k-set agreement algorithm from n-k swap objects, which exactly matches our lower bound when k=1. Second, we show that any obstruction-free binary consensus algorithm from readable swap objects with domain size b uses at least \(\frac{n-2}{3b+1}\) objects. When b is a constant, this asymptotically matches the best known obstruction-free consensus algorithms from readable swap objects with unbounded domains. Since any historyless object can be simulated by a readable swap object with the same domain, our results imply that any obstruction-free consensus algorithm from historyless objects with domain size b uses at least \(\frac{n-2}{3b+1}\) objects. For b = 2, we show a slightly better lower bound of n-2. There is an obstruction-free binary consensus algorithm using 2n-1 readable swap objects with domain size 2, asymptotically matching our lower bound. [ABSTRACT FROM AUTHOR]

The sparse matrix–vector product (SpMV) is a fundamental computational kernel utilized in a diverse range of scientific and engineering applications. It is commonly used to solve linear and partial differential equations. The parallel computation of the SpMV product is a challenging task. Existing solutions often employ a fixed number of threads assignment to rows based on empirical formulas, leading to sub-optimal configurations and significant performance losses. Elegante, our proposed machine learning-powered tool, utilizes a data-driven approach to identify the optimal thread configuration for SpMV computations within a shared memory architecture. It accomplishes this by predicting the best thread configuration based on the unique sparsity pattern of each sparse matrix. Our approach involves training and testing using various base and ensemble machine learning algorithms such as decision tree, random forest, gradient boosting, logistic regression, and support vector machine. We rigorously experimented with a dataset of nearly 1000+ real-world matrices. These matrices originated from 46 distinct application domains, spanning fields like robotics, power networks, 2D/3D meshing, and computational fluid dynamics. Our proposed methodology achieved 62% of the highest achievable performance and is 7.33 times faster, demonstrating a significant disparity from the default OpenMP configuration policy and traditional practice methods of manually or randomly selecting the number of threads. This work is the first attempt where the structure of the matrix is used to predict the optimal thread configuration for the optimization of parallel SpMV computation in a shared memory environment. [ABSTRACT FROM AUTHOR]

This paper introduces software patterns (registration, acquire-release, and cache awareness) and data structures (Petri net, finite state machine, and protocol flag array) to support the coordinated execution of software activities (also called "components" or "agents"). Moreover, it presents and tests an implementation for Petri nets that supports real-time execution in shared memory for deployment inside one individual robot and separates event firing and handling, enabling distributed deployment between multiple robots. Experimental validation of the introduced patterns and data structures is performed within the context of activities for task execution, control and perception, and decision making for an application on coordinated navigation. [ABSTRACT FROM AUTHOR]

The research notes examine a shared memory created during the Russian war against Ukraine, as depicted in news coverage of global media outlets, and in Ukrainian-language competitive poetry from international free competitions and Ukrainian governmental art projects. The research goal is to explain the hidden dangers and consequences of war memorization. The author compares public collective evaluations of key metaphors used in news during the initial three weeks of war and analyzes key images in Ukrainian poetry from pre-war and wartime periods. Preliminary results of the secondary qualitative content analysis of news and analysis of group discussions with students specializing in different fields illustrate how the metaphors varied in terms of adequacy and artistic expressiveness due to societal evaluations. The findings of quantitative semantic analysis of Ukrainian-language poems highlight how the shift in key images correlates with the transition from a relatively peaceful context to an overtly military one. The knowledge gained contributes to a better understanding of memory weaponization and specific ways in which collective sensitivity is little influenced by media positions (pro-Ukrainian or non-pro-Ukrainian), being more dependent on a sense of morality. [ABSTRACT FROM AUTHOR]

Determining the number of registers required for solving obstruction-free (or randomized wait-free) k-set agreement is an open problem that highlights important gaps in our understanding of the space complexity of synchronization. The best known upper bound on the number of registers needed to solve this problem among n > k processes is n k + 1 registers. No general lower bound better than 2 was known. We prove that any obstruction-free protocol solving k-set agreement among n >k processes must use at least n/k registers. In particular, we get a tight lower bound of exactly n registers for solving obstruction-free and randomized wait-free consensus. Our main tool is a simulation that serves as a reduction from the impossibility of deterministic waitfree k-set agreement. In particular, we show that if an obstruction-free protocol for k-set agreement uses fewer registers, then it is possible for k +1 processes to simulate the protocol and deterministically solve k-set agreement in a wait-free manner, which is impossible. An important aspect of the simulation is the ability of simulating processes to revise the past of simulated processes. We introduce an augmented snapshot object, which facilitates this. More generally, our simulation applies to the broad class of colorless tasks. We can use it to prove, for example, a lower bound on the number of registers needed to solve obstruction-free epsilon -approximate agreement, which matches the best known upper bound to within a factor of 2 when epsilon is sufficiently small. No general lower bound for this problem was known. Finally, we prove that any lower bound on the number of registers used by obstruction-free protocols applies to protocols that satisfy nondeterministic solo-termination. Hence, our lower bounds for obstruction-free protocols also hold for randomized wait-free protocols. [ABSTRACT FROM AUTHOR]

In embedded systems, tightly coupled memories (TCMs) are usually shared between multiple masters for the purpose of hardware efficiency and software flexibility. On the one hand, memory sharing improves area utilization, but on the other hand, this can lead to a performance degradation due to an increase in access conflicts. To mitigate the associated performance penalty, access interval prediction (AIP) has been proposed. In a similar fashion to branch prediction, AIP exploits program flow regularity to predict the cycle of the next memory access. We show that this structural similarity allows for adaption of state-of-the-art branch predictors, such as Prediction by Partial Matching (PPM) and the TAgged GEometric history length (TAGE) branch predictor. Our analysis on memory access traces reveals that PPM predicts 99 percent of memory accesses. As PPM does not lend itself to hardware implementation, we also present the PPM-based TAGE access interval predictor which attains an accuracy of over 97 percent outperforming all previously presented implementable AIP schemes. [ABSTRACT FROM AUTHOR]

This paper introduces software patterns (registration, acquire-release, and cache awareness) and data structures (Petri net, finite state machine, and protocol flag array) to support the coordinated execution of software activities (also called “components” or “agents”). Moreover, it presents and tests an implementation for Petri nets that supports real-time execution in shared memory for deployment inside one individual robot and separates event firing and handling, enabling distributed deployment between multiple robots. Experimental validation of the introduced patterns and data structures is performed within the context of activities for task execution, control and perception, and decision making for an application on coordinated navigation.

Multiprocessor System-on-Chips (MPSoCs) computing architectures are gaining popularity due to their high-performance capabilities and exceptional Quality-of-Service (QoS), making them a particularly well-suited computing platform for computationally intensive workloads and applications. Nonetheless, The scheduling and allocation of a single task set with precedence restrictions on MPSoCs have presented a persistent research challenge in acquiring energy-efficient solutions. The complexity of this scheduling problem escalates when subject to conditional precedence constraints between the tasks, creating what is known as a Conditional Task Graph (CTG). Scheduling sets of Periodic Conditional Task Graphs (PCTGs) on MPSoC platforms poses even more challenges. This paper focuses on tackling the scheduling challenge for a group of PCTGs on MPSoCs equipped with shared memory. The primary goal is to minimize the overall anticipated energy usage, considering two distinct power models: dynamic and static power models. To address this challenge, this paper introduces an innovative scheduling method named Energy Efficient Successor Tree Consistent Earliest Deadline First (EESEDF). The EESEDF approach is primarily designed to maximize the worst-case processor utilization. Once the tasks are assigned to processors, it leverages the earliest successor tree consistent deadline-first strategy to arrange tasks on each processor. To minimize the overall expected energy consumption, EESEDF solves a convex Non-Linear Program (NLP) to determine the optimal speed for each task. Additionally, the paper presents a highly efficient online Dynamic Voltage Scaling (DVS) heuristic, which operates in O(1) time complexity and dynamically adjusts the task speeds in real-time. We achieved the average improvement, maximum improvement, and minimum improvement of EESEDF+Online-DVS 15%, 17%, and 12%, respectively compared to EESEDF alone. Furthermore, in the second set of experiments, we compared EESEDF against state-of-the-art techniques LESA and NCM. The results showed that EESEDF+Online-DVS outperformed these existing approaches, achieving notable energy efficiency improvements of 25% and 20% over LESA and NCM, respectively. Our proposed scheduler, EESEDF+Online-DVS, also achieves significant energy efficiency gains compared to existing methods. It outperforms IOETCS-Heuristic by approximately 13% while surpassing BESS and CAP-Online by impressive margins of 25% and 35%, respectively.

Following a long period of neglect, research on different facets of collective memory is now developing apace in the human and social sciences, as well as at their interface with psychology and neuroscience. This resolutely multidisciplinary renewal of interest in memory sciences has given rise to a plethora of concepts with diverse meanings (e.g., social frameworks of memory, collective, shared, collaborative, social memory). The purpose of the present study was to provide a conceptual overview from a historical perspective, and above all to clarify concepts that are often used interchangeably, even though they refer to very different realities. Based on recent research in psychology and neuroscience, we use the concept of collective memory to refer to the operations of individual systems of consciousness. Collective memory is not the memory of a collective, but that of its individual members, either as members of social groups (shared memory) or as participants in social interactions (collaborative memory). Drawing on the contributions of contemporary sociology, we show that social memory is not collective memory, as it refers not to individual systems of consciousness, but to social systems. More specifically, it is the outcome of communication operations which, through redundancy and repetition, perform a continuous and selective re-imprinting of meaning that can be used for communication. Writing, printing and the new communication technologies constitute the three historical stages in the formation and development of an autonomous social memory, independent of living memories and social interactions. In the modern era, mass media fulfill an essential function of social memory, by sorting between forgetting and remembering on a planetary scale. When thinking about the articulation between collective memory and social memory, the concept of structural coupling allows us to identify two mechanisms by which individual systems of consciousness and social systems can interact and be mutually sensitized: schemas and scripts, and social roles. Transdisciplinary approach spearheads major methodological and conceptual advances and is particularly promising for clinical practice, as it should result in a better understanding of memory pathologies, including PTSD, but also cognitive disorders in cancer (chemobrain) or in neurodegenerative diseases. [ABSTRACT FROM AUTHOR]

With the development of engineering technology, engineering has higher requirements for the accuracy and the scale of simulation calculation. The computational efficiency of traditional serial programs cannot meet the requirements of engineering. Therefore, reducing the calculation time of the temperature control simulation program has important engineering significance for real-time simulation of temperature field and stress field, and then adopting more reasonable temperature control and crack prevention measures. GPU parallel computing is introduced into the temperature control simulation program of massive concrete to solve this problem and the optimization is carried out. Considering factors such as GPU clock rate, number of cores, parallel overhead and Parallel Region, the improved GPU parallel algorithm analysis indicator formula is proposed. It makes up for the shortcomings of traditional formulas that focus only on time. According to this formula, when there are enough threads, the parallel effect is limited by the size of the parallel domain, and when the parallel domain is large enough, the efficiency is limited by the parallel overhead and the clock rate. This paper studies the optimal Kernel execution configuration. Shared memory is utilized to improve memory access efficiency by 155%. After solving the problem of bank conflicts, an accelerate rate of 437.5× was realized in the subroutine of the matrix transpose of the solver. The asynchronous parallel of data access and logical operation is realized on GPU by using CUDA Stream, which can overlap part of the data access time. On the basis of GPU parallelism, asynchronous parallelism can double the computing efficiency. Compared with the serial program, the accelerate rate of inner product matrix multiplication of the GPU asynchronous parallel program is 61.42×. This study further proposed a theoretical formula of data access overlap rate to guide the selection of the number of CUDA streams to achieve the optimal computing conditions. The GPU parallel program compiled and optimized by the CUDA Fortran platform can effectively improve the computational efficiency of the simulation program for concrete temperature control, and better serve engineering computing. [ABSTRACT FROM AUTHOR]

Following a long period of neglect, research on different facets of collective memory is now developing apace in the human and social sciences, as well as at their interface with psychology and neuroscience. This resolutely multidisciplinary renewal of interest in memory sciences has given rise to a plethora of concepts with diverse meanings (e.g., social frameworks of memory, collective, shared, collaborative, social memory). The purpose of the present study was to provide a conceptual overview from a historical perspective, and above all to clarify concepts that are often used interchangeably, even though they refer to very different realities. Based on recent research in psychology and neuroscience, we use the concept of collective memory to refer to the operations of individual systems of consciousness. Collective memory is not the memory of a collective, but that of its individual members, either as members of social groups (shared memory) or as participants in social interactions (collaborative memory). Drawing on the contributions of contemporary sociology, we show that social memory is not collective memory, as it refers not to individual systems of consciousness, but to social systems. More specifically, it is the outcome of communication operations which, through redundancy and repetition, perform a continuous and selective re-imprinting of meaning that can be used for communication. Writing, printing and the new communication technologies constitute the three historical stages in the formation and development of an autonomous social memory, independent of living memories and social interactions. In the modern era, mass media fulfill an essential function of social memory, by sorting between forgetting and remembering on a planetary scale. When thinking about the articulation between collective memory and social memory, the concept of structural coupling allows us to identify two mechanisms by which individual systems of consciousness and social systems can interact and be mutually sensitized: schemas and scripts, and social roles. Transdisciplinary approach spearheads major methodological and conceptual advances and is particularly promising for clinical practice, as it should result in a better understanding of memory pathologies, including PTSD, but also cognitive disorders in cancer (chemobrain) or in neurodegenerative diseases.

Parallel computing on distributed heterogeneous architectures (e.g. computing clusters with multiple CPUs and GPUs) can significantly improve the computational efficiency and scalability of complicated algorithms, but it is theoretically and technically complex. Parallel raster processing libraries reduce the development complexity of parallel raster algorithms by hiding parallel computing details; however, no existing library sufficiently utilizes distributed heterogeneous computing resources. A general-purpose raster processing library (mcRPL) combining multi-process parallelism and multi-thread parallelism is proposed to enable parallel raster processing on distributed heterogeneous architectures with multiple CPUs and GPUs. Additionally, an adaptive hardware assignment strategy is proposed to fully utilize available processors in various hardware environments. A series of task-processing strategies are adopted to aim toward maximizing the utilization of the computing capacity of involved processors. Experiments revealed that two raster algorithms parallelized using mcRPL for spatiotemporal data fusion and land-use change simulation were 170.7- and 143.2-fold faster than original serial algorithms using 8 and 16 GPUs, respectively. While hiding the details of mixed parallelism and reducing the development complexity, mcRPL provides user-friendly interfaces for the development of parallel raster algorithms to enhance computational performance and enable large-scale raster computing tasks with extensive data volumes. [ABSTRACT FROM AUTHOR]

Sparse matrix-vector multiplication (SpMV) is central to many scientific, engineering, and other applications, including machine learning. Compressed Sparse Row (CSR) is a widely used sparse matrix storage format. SpMV using the CSR format on GPU computing platforms is widely studied, where the access behavior of GPU is often the performance bottleneck. The Ampere GPU architecture recently from NVIDIA provides a new asynchronous memory copy instruction, memcpy_async, for more efficient data movement in shared memory. Leveraging the capability of this new memcpy_async instruction, we first propose the CSR-Partial-Overlap to carefully overlap the data copy from global memory to shared memory and computation, allowing us to take full advantage of the data transfer time. In addition, we design the dynamic batch partition and the dynamic threads distribution to achieve effective load balancing, avoid the overhead of fixing up partial sums, and improve thread utilization. Furthermore, we propose the CSR-Full-Overlap based on the CSR-Partial-Overlap, which takes the overlap of data transfer from host to device and SpMV kernel execution into account as well. The CSR-Full-Overlap unifies the two major overlaps in SpMV and hides the computation as much as possible in the two important access behaviors of the GPU. This allows CSR-Full-Overlap to achieve the best performance gains from both overlaps. As far as we know, this paper is the first in-depth study of how memcpy_async can be potentially applied to help accelerate SpMV computation in GPU platforms. We compare CSR-Full-Overlap to the current state-of-the-art cuSPARSE, where our experimental results show an average 2.03x performance gain and up to 2.67x performance gain. [ABSTRACT FROM AUTHOR]

The Neural Development Simulator, NeuroDevSim, is a Python module that simulates the most important aspects of brain development: morphological growth, migration, and pruning. It uses an agent-based modeling approach inherited from the NeuroMaC software. Each cycle has agents called fronts execute model-specific code. In the case of a growing dendritic or axonal front, this will be a choice between extension, branching, or growth termination. Somatic fronts can migrate to new positions and any front can be retracted to prune parts of neurons. Collision detection prevents new or migrating fronts from overlapping with existing ones. NeuroDevSim is a multi-core program that uses an innovative shared memory approach to achieve parallel processing without messaging. We demonstrate linear strong parallel scaling up to 96 cores for large models and have run these successfully on 128 cores. Most of the shared memory parallelism is achieved without memory locking. Instead, cores have only write privileges to private sections of arrays, while being able to read the entire shared array. Memory conflicts are avoided by a coding rule that allows only active fronts to use methods that need writing access. The exception is collision detection, which is needed to avoid the growth of physically overlapping structures. For collision detection, a memory-locking mechanism was necessary to control access to grid points that register the location of nearby fronts. A custom approach using a serialized lock broker was able to manage both read and write locking. NeuroDevSim allows easy modeling of most aspects of neural development for models simulating a few complex or thousands of simple neurons or a mixture of both. [ABSTRACT FROM AUTHOR]

The Neural Development Simulator, NeuroDevSim, is a Python module that simulates the most important aspects of brain development: morphological growth, migration, and pruning. It uses an agent-based modeling approach inherited from the NeuroMaC software. Each cycle has agents called fronts execute model-specific code. In the case of a growing dendritic or axonal front, this will be a choice between extension, branching, or growth termination. Somatic fronts can migrate to new positions and any front can be retracted to prune parts of neurons. Collision detection prevents new or migrating fronts from overlapping with existing ones. NeuroDevSim is a multi-core program that uses an innovative shared memory approach to achieve parallel processing without messaging. We demonstrate linear strong parallel scaling up to 96 cores for large models and have run these successfully on 128 cores. Most of the shared memory parallelism is achieved without memory locking. Instead, cores have only write privileges to private sections of arrays, while being able to read the entire shared array. Memory conflicts are avoided by a coding rule that allows only active fronts to use methods that need writing access. The exception is collision detection, which is needed to avoid the growth of physically overlapping structures. For collision detection, a memory-locking mechanism was necessary to control access to grid points that register the location of nearby fronts. A custom approach using a serialized lock broker was able to manage both read and write locking. NeuroDevSim allows easy modeling of most aspects of neural development for models simulating a few complex or thousands of simple neurons or a mixture of both.Code available athttps://github.com/CNS-OIST/NeuroDevSim.

A shared-memory counter is a widely-used and well-studied concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. In Jayanti et al (SIAM J Comput, 30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read-write registers, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this work, we address this gap. We show that n-process, wait-free and linearizable counters can be implemented from read-write registers with O (log 2 n) amortized step complexity. This is the first counter algorithm from read-write registers that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is within a logarithmic factor of the optimal. The worst-case step complexity of the construction remains linear, which is optimal. This is obtained thanks to a new max register construction with O (log n) amortized step complexity in executions of arbitrary length in which the value stored in the register does not grow too quickly. We then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel [1] in which we "plug" our max register implementation to show that it remains linearizable while achieving O (log 2 n) amortized step complexity. [ABSTRACT FROM AUTHOR]

Approximate Computing techniques are finding a central role in modern applications, by optimizing architectures to relax some computation but with a constrained inaccuracy. In many applications, the FFT algorithm is invariably applied and there is a need for approximate low energy hardware solutions to the FFT. The paper thus proposes an approximate, fixed-point, in-place, shared memory architecture for FFT. It is well observed that the energy at FFT I/Os is not strictly contiguous, hence the proposed FFT exploits this window to tune the error. The proposed FFT and its associated butterfly unit is constructed to efficiently incorporate approximate Toom–Cook multiplication. As said, a supporting function in error correction based on the sparsity patterns, is a feature of this design. The design synthesized at 32 n m shows on average, a 48.6% and 52.8% improvement in consumption of area and energy, respectively, with as less error as 0.1% with pruning. • Approximate Computing can exploit error resilience of the applications to reduce chip resources. • FFT is a fundamental block on chip and approximating FFT can accelerate many applications. • The proposed FFT is based on approximate Toom-Cook multiplication that has a reduced number of sub-multiplications. • Pre-computing the evaluations in Toom-Cook multiplication of the twiddle factors in the butterfly provides additional savings. • This design allows a secondary mode of operation in FFT to trade-off sparsity in the FFT outputs with the error in the final FFT sequence. [ABSTRACT FROM AUTHOR]

Summary: With the rise of multi‐core processors with a large number of cores, the need for shared memory reduction that performs efficiently on a large number of cores is more pressing. Efficient shared memory reduction on these multi‐core processors will help share memory programs be more efficient. In this article, we propose a reduction method combined with a barrier method that uses SIMD read/write instructions to combine barrier signaling and reduction value to minimize memory/cache traffic between cores, thereby reducing barrier latency. We compare different barriers and reduction methods on three multi‐core processors and show that the proposed combining barrier/reduction methods are 4 and 3.5 times faster than respectively GCC 11.1 and Intel 21.2 OpenMP 4.5 reduction. [ABSTRACT FROM AUTHOR]

High-performance computing (HPC) systems enable scientific advances through simulation and data processing. The heterogeneity in HPC hardware and software increases the application complexity and reduces its maintainability and productivity. This work proposes a prototype implementation for a parallel pattern-based source-to-source compiler to address these challenges. The prototype limits the complexity of parallelism and heterogeneous architectures to parallel patterns that are optimized towards a given target architecture. By applying high-level optimizations and a mapping between parallel patterns and execution units during compile time, portability between systems is achieved. The compiler can address architectures with shared memory, distributed memory, and accelerator offloading. The approach shows speedups for seven of the nine supported Rodinia benchmarks, reaching speedups of up to twelve times. Porting LULESH to the Parallel Pattern Language (PPL) shows a compression of code size by 65% (3.4 thousand lines of code) through a more concise expression and a higher level of abstraction. The tool's limitations include dynamic algorithms that are challenging to analyze statically and overheads during the compile time optimization. This paper is an extended version of a previous PMAM publication (Schmitz et al., 2024). [ABSTRACT FROM AUTHOR]

With the development of engineering technology, engineering has higher requirements for the accuracy and the scale of simulation calculation. The computational efficiency of traditional serial programs cannot meet the requirements of engineering. Therefore, reducing the calculation time of the temperature control simulation program has important engineering significance for real-time simulation of temperature field and stress field, and then adopting more reasonable temperature control and crack prevention measures. GPU parallel computing is introduced into the temperature control simulation program of massive concrete to solve this problem and the optimization is carried out. Considering factors such as GPU clock rate, number of cores, parallel overhead and Parallel Region, the improved GPU parallel algorithm analysis indicator formula is proposed. It makes up for the shortcomings of traditional formulas that focus only on time. According to this formula, when there are enough threads, the parallel effect is limited by the size of the parallel domain, and when the parallel domain is large enough, the efficiency is limited by the parallel overhead and the clock rate. This paper studies the optimal Kernel execution configuration. Shared memory is utilized to improve memory access efficiency by 155%. After solving the problem of bank conflicts, an accelerate rate of 437.5× was realized in the subroutine of the matrix transpose of the solver. The asynchronous parallel of data access and logical operation is realized on GPU by using CUDA Stream, which can overlap part of the data access time. On the basis of GPU parallelism, asynchronous parallelism can double the computing efficiency. Compared with the serial program, the accelerate rate of inner product matrix multiplication of the GPU asynchronous parallel program is 61.42×. This study further proposed a theoretical formula of data access overlap rate to guide the selection of the number of CUDA streams to achieve the optimal computing conditions. The GPU parallel program compiled and optimized by the CUDA Fortran platform can effectively improve the computational efficiency of the simulation program for concrete temperature control, and better serve engineering computing.

In static temporal networks, the Earliest Arrival Time (EAT) problem is to calculate the earliest possible time of arrival at a set of vertices from a given source vertex. Applications of the EAT problem include designing efficient evacuation planning in dynamic scenarios, optimal journey planning in transport networks, and optimal flow management in supply chains. There exist several solutions for the EAT problem in the literature, however, there is limited work on GPU (Graphics Processing Unit) based solutions to leverage the capabilities of the high throughput accelerator for better performance. Further, there is also a need for more efficient methods to process the inherent earliest arrival dependencies in a transport network. In this paper, we propose a suite of five incremental (GPU) algorithms for the one-to-all Earliest Arrival Time problem in public transport networks. The Selective-check-version is the most optimized approach and hence, the key algorithm. It uses an edge coloring based approach to trace the time-respectingness of paths and processing the in-edges in a sorted order based on their arrival times. Its key characteristic is that it is very fast for the best-case networks where all temporal paths are time-respecting. For the Selective-check version, we observed an average speedup of 6.45 against the Serial Connection-scan algorithm and 2.77 w.r.t. the Edge-version algorithm.

In the wind tunnel experiment, the existing CPU-based optical flow method takes too long to solve the velocity field of the fluorescent oil film, while the GPU-based optical flow method has the problem of insufficient utilization of GPU resources.To this end, a real-time measurement method of GPU fluorescent oil film motion path based on fluorescent oil film image segmentation and critical constraints is proposed.The fluorescent oil film time-series image is divided into blocks and processed in parallel according to the resources of the GPU, and the corresponding optical flow parallel computing strategy is created, that is, the advantages of the parallel pipeline architecture of the GPU and the shared memory are fully utilized to realize the optical flow calculation of each parallel block.At the same time, combined with the critical constraints between blocks, the number of iterative calculations is controlled by the iterative difference of the speed matrix of each block as a symbol.The experimental results show that the method proposed in this paper is 2 789.5 times faster than the traditional CPU-based optical flow method under the condition of ensuring the calculation accuracy of the velocity field of the fluorescent oil film motion, and the average speed of the GPU optical flow method of the whole frame image is improved.10.09 times and the real-time solution speed can reach 90 frames per second.

We present a new parallel algorithm for probabilistic graphical model optimization. The algorithm relies on data-parallel primitives (DPPs), which provide portable performance over hardware architecture. We evaluate results on CPUs and GPUs for an image segmentation problem. Compared to a serial baseline, we observe runtime speedups of up to 13X (CPU) and 44X (GPU). We also compare our performance to a reference, OpenMP-based algorithm, and find speedups of up to 7X (CPU).

We present a new parallel algorithm for probabilistic graphical model optimization. The algorithm relies on data-parallel primitives (DPPs), which provide portable performance over hardware architecture. We evaluate results on CPUs and GPUs for an image segmentation problem. Compared to a serial baseline, we observe runtime speedups of up to 13X (CPU) and 44X (GPU). We also compare our performance to a reference, OpenMP-based algorithm, and find speedups of up to 7X (CPU).

Blockchain technologies can enable secure computing environments among mistrusting parties. Permissioned blockchains are particularly enlightened by companies, enterprises, and government agencies due to their efficiency, customizability, and governance-friendly features. Obviously, seamlessly fusing blockchain and cloud computing can significantly benefit permissioned blockchains; nevertheless, most blockchains implemented on clouds are originally designed for loosely-coupled networks where nodes communicate asynchronously, failing to take advantages of the closely-coupled nature of cloud servers. In this paper, we propose an innovative cloud-oriented blockchain – CloudChain, which is a modularized three-layer system composed of the network layer, consensus layer, and blockchain layer. CloudChain is based on a shared-memory model where nodes communicate synchronously by direct memory accesses. We realize the shared-memory model with the Remote Direct Memory Access technology, based on which we propose a shared-memory consensus algorithm to ensure presistence and liveness, the two crucial blockchain security properties countering Byzantine nodes. We also implement a CloudChain prototype based on a RoCEv2-based testbed to experimentally validate our design, and the results verify the feasibility and efficiency of CloudChain. [ABSTRACT FROM AUTHOR]

Tensor computations are important mathematical operations for applications that rely on multidimensional data. The tensor–vector multiplication (TVM) is the most memory-bound tensor contraction in this class of operations. This article proposes an open-source TVM algorithm which is much simpler and efficient than previous approaches, making it suitable for integration in the most popular BLAS libraries available today. Our algorithm has been written from scratch and features unit-stride memory accesses, cache awareness, mode obliviousness, full vectorization and multi-threading as well as NUMA awareness for non-hierarchically stored dense tensors. Numerical experiments are carried out on tensors up to order 10 and various compilers and hardware architectures equipped with traditional DDR and high bandwidth memory (HBM). For large tensors the average performance of the TVM ranges between 62% and 76% of the theoretical bandwidth for NUMA systems with DDR memory and remains independent of the contraction mode. On NUMA systems with HBM the TVM exhibits some mode dependency but manages to reach performance figures close to peak values. Finally, the higher-order power method is benchmarked with the proposed TVM kernel and delivers on average between 58% and 69% of the theoretical bandwidth for large tensors. [ABSTRACT FROM AUTHOR]

Summary: The tomographic reconstruction is a powerful diagnostic tool in nuclear fusion experiments for the determination of the shape and position of the plasma. However, neural networks are emerging as a suitable alternative to conventional plasma tomography algorithms. In order to train such AI/ML based models, we need large‐scale, diversified image data for learning and evaluation which is difficult to obtain from real experiments. Accuracy and real‐time response is also critical, therefore in this article we propose an effective shared memory based parallel algorithm for synthetic imaging diagnostic data generation. The practicality of the proposed parallel algorithm has been evaluated experimentally by comparing it to the sequential algorithm on two different computing architectures. We observe a maximum speedup of 21 at 32 threads and demonstrate that our proposed parallel algorithm scales well over a range of image sizes. The proposed parallel algorithm can be used to obtain the synthetic images within a few seconds which is very important for real time applications. We also provide an analysis on the importance of choosing the right scheduling type and optimum chunk size to obtain the maximum speedup. [ABSTRACT FROM AUTHOR]

Recent advances in non-volatile main memory (NVM) technology have spurred research on algorithms that are resilient to intermittent failures that cause processes to crash and subsequently restart. In this paper we present a Recoverable Mutual Exclusion (RME) algorithm that supports abortability. Our algorithm guarantees FCFS and a strong liveness property: processes do not starve even in runs consisting of infinitely many crashes, provided that a process crashes at most a finite number of times in each of its attempts. On DSM and Relaxed-CC multiprocessors, a process incurs O (min (k , log n)) RMRs in a passage and O (f + min (k , log n)) RMRs in an attempt, where n is the number of processes that the algorithm is designed for, k is the point contention of the passage or the attempt, and f is the number of times that p crashes during the attempt. On a Strict CC multiprocessor, the passage and attempt complexities are O(n) and O (f + n) , respectively. Our algorithm uses only the read, write, and CAS operations, which are commonly supported by multiprocessors. Attiya, Hendler, and Woelfel proved that, with any mutual exclusion algorithm, a process incurs at least Ω (log n) RMRs in a passage, if the algorithm uses only the read, write, and CAS operations (in: Proc. of the Fortieth ACM Symposium on Theory of Computing, New York, NY, USA, 2008). This lower bound implies that the worst-case RMR complexity of our algorithm is optimal for the DSM and Relaxed CC multiprocessors. This paper is an expanded version of our conference paper as reported by Jayanti and Joshi (in: Atig and Schwarzmann (eds) Networked Systems. Springer International Publishing, Cham, 2019), which presented the first Recoverable Mutual Exclusion (RME) algorithm that supports abortability. This algorithm from our conference paper (in: Atig and Schwarzmann (eds) Networked Systems. Springer International Publishing, Cham, 2019) admits starvation when there are infinitely many aborts in a run. In this paper, we fix this shortcoming and prove the algorithm's properties by identifying an inductive invariant. [ABSTRACT FROM AUTHOR]