Search

The balanced hypercube B H n plays an essential role in large-scale parallel and distributed computing systems. With the increasing probability of edge faults in large-scale networks and the widespread applications of Hamiltonian paths and cycles, it is especially essential to study the fault tolerance of networks in the presence of Hamiltonian paths and cycles. However, existing researches on edge faults ignore that it is almost impossible for all faulty edges to be concentrated in a certain dimension. Thus, the fault tolerance performance of interconnection networks is severely underestimated. This paper focuses on three measures, t -partition-edge fault-tolerant Hamiltonian, t -partition-edge fault-tolerant Hamiltonian laceable, and t -partition-edge fault-tolerant strongly Hamiltonian laceable, and utilizes these measures to explore the existence of Hamiltonian paths and cycles in balanced hypercubes with exponentially faulty edges. We show that the B H n is 2 n − 1 -partition-edge fault-tolerant Hamiltonian laceable, 2 n − 1 -partition-edge fault-tolerant Hamiltonian, and (2 n − 1 − 1) -partition-edge fault-tolerant strongly Hamiltonian laceable for n ≥ 2. Comparison results show the partitioned fault model can provide the exponential fault tolerance as the value of the dimension n grows. • Based on the partitioned fault model, this paper propose three novel indicators for the balanced hypercubes B H n. • B H n is 2 n − 1 (resp. 2 n − 1 − 1)-partition-edge fault-tolerant (resp. strongly) Hamiltonian laceable. • Comparison results show the partitioned fault model can provide exponential fault tolerance as the dimension n grows. [ABSTRACT FROM AUTHOR]

Water distribution networks (WDNs) are one of the largest infrastructures in society. Various methods for formulation and hydraulic analysis of water distribution networks, including numerical and non-numerical methods, have been previously proposed. Due to the complexity, the nonlinearity of the hydraulic equations of water distribution networks, and the need for multiple executions and uncertainties in parameters, solving the hydraulic model of water distribution networks has high time complexity. In this paper, a parallel computational architecture based on the concept of cellular automata is proposed to accelerate the numerical solution of the steady-state water distribution network model. Taylor series is proposed to solve hydraulic equations. The presented architecture was implemented as a parallel hardware platform on a field-programmable gate array. The performance of the proposed method was compared with EPANET software for networks with different complexities and topologies. The results show that the proposed parallel algorithm can accelerate the hydraulic analysis of regular water distribution networks up to 700 times and 250 times for small and large networks, respectively. • Proposed CA architectures to solve a system of non-linear equations on a fine-grain parallel architecture. • An efficient method to reduce computation time for hydraulic analysis of water networks. • The synthesizable hardware descriptions were generated through design automation. • Accelerate the hydraulic analysis of WDNs up to 700 times compared to EPANET, a well-known hydraulic analysis tool. [ABSTRACT FROM AUTHOR]

• We present a theoretical framework that can be used for analyzing, and quantifying the performance of parallel algorithms designed for MS based omics data. • We prove the lower communication bounds for the existing parallel algorithms. • We also prove lower communication bounds that can be theoretically achieved by parallel algorithms for MS based omics analysis. • Extensive experimentation for state of the art tools confirms our theoretical results. • This is first proof of any communication bounds for parallel algorithms for MS based omics. Mass spectrometry (MS) based omics data analysis require significant time and resources. To date, few parallel algorithms have been proposed for deducing peptides from mass spectrometry-based data. However, these parallel algorithms were designed, and developed when the amount of data that needed to be processed was smaller in scale. In this paper, we prove that the communication bound that is reached by the existing parallel algorithms is Ω (m n + 2 r q p) , where m and n are the dimensions of the theoretical database matrix, q and r are dimensions of spectra, and p is the number of processors. We further prove that communication-optimal strategy with fast-memory M = m n + 2 q r p can achieve Ω (2 m n q p) but is not achieved by any existing parallel proteomics algorithms till date. To validate our claim, we performed a meta-analysis of published parallel algorithms, and their performance results. We show that sub-optimal speedups with increasing number of processors is a direct consequence of not achieving the communication lower-bounds. We further validate our claim by performing experiments which demonstrate the communication bounds that are proved in this paper. Consequently, we assert that next-generation of provable , and demonstrated superior parallel algorithms are urgently needed for MS based large systems-biology studies especially for meta-proteomics, proteogenomic, microbiome, and proteomics for non-model organisms. Our hope is that this paper will excite the parallel computing community to further investigate parallel algorithms for highly influential MS based omics problems. [ABSTRACT FROM AUTHOR]

Option pricing is one of the most active Financial Economics research fields. Black-Scholes-Merton option pricing theory states that risk-neutral density is lognormal. However, markets' pieces of evidence do not support that assumption. More realistic assumptions impose substantial computational burdens to calculate option pricing functions. Risk-neutral density is a pivotal element to price derivative assets, which can be estimated through nonparametric kernel methods. A significant computational challenge exists for determining optimal kernel bandwidths, addressed in this study through a parallel computing algorithm performed using Graphical Processing Units. The paper proposes a tailor-made Cross-Validation criterion function used to define optimal bandwidths. The selection of optimal bandwidths is crucial for nonparametric estimation and is also the most computationally intensive. We tested the developed algorithms through two data sets related to intraday data for VIX and S&P500 indexes. • An example of such big data environments is information associated with financial options contracts. • Second, we developed methods to estimate the risk-neutral density as a pivotal element for options pricing. • Third, we found that nonparametric methods should be adapted for estimating the second derivatives, which relate to the risk-neutral densities. • Fourth, the proposed adaptations imply significant computational burdens defining bandwidths for nonparametric estimators. • Fifth, we found that parallel computing procedures can reduce computational times, compatible with needed dynamic updating. [ABSTRACT FROM AUTHOR]

The L -ary n -dimensional hamming graph K L n is one of the most attractive interconnection networks for parallel processing and computing systems. Analysis of the link fault tolerance of topology structure can provide the theoretical basis for the design and optimization of the interconnection networks. The k -component edge-connectivity c λ k (G) of an interconnection network G , is the minimum number of set of faulty links, such that these malfunctions disconnect the network G with at least k connected subnetworks. It gives a more precise quantitative analysis of indicators of the robustness of a parallel distributed system in the event of faulty links. Let t = ⌊ n 2 ⌋ if L is even, and t = ⌈ n 2 ⌉ if L is odd. In this paper, we prove that the (k + 1) -component edge-connectivity of L -ary n -dimensional hamming graphs is c λ k + 1 (K L n) = (L − 1) n k − e x k (K L n) 2 for k ≤ L t , n ≥ 7 , where e x k (K L n) represents the maximum degree sum of the subgraph induced by all k processors of K L n. As the exact values of (k + 1) -component edge-connectivity of K L n oscillate greatly, an efficient O (log ⁡ N) algorithm is designed to determine the exact values of c λ k + 1 (K L n) for each k ≤ L t and N = L n. Our result improves those of Xu et al. [33] and Liu et al. [27]. • The (k + 1) -component edge-connectivity of L -ary n -dimensional hamming graphs K L n is explored. • Determine the exact value of c λ k + 1 (K L n) for each k ≤ L t and n ≥ 7 , where t = ⌊ n 2 ⌋ if L is even, and t = ⌈ n 2 ⌉ if L is odd. • An efficient O (l o g N) algorithm is designed to determine the exact value of c λ k + 1 (K L n) for each k ≤ L t and N = L n. [ABSTRACT FROM AUTHOR]

• A history of parallel and distributed computing (PDC) technology evolution, from the late 1990s to the present. • Specific ways in which teaching PDC has changed during that timespan. • Descriptions and pictures of a wide variety of Beowulf clusters. • Select software tools specifically designed for PDC education. • A dozen insights reflecting the author's experiences as a PDC educator. Much has changed about parallel and distributed computing (PDC) since the author began teaching the topic in the late 1990s. This paper reviews some of the key changes to the field and describes their impacts on his work as a PDC educator. Such changes include: the availability of free implementations of the message passing interface (MPI) for distributed-memory multiprocessors; the development of the Beowulf cluster; the advent of multicore architectures; the development of free multithreading languages and libraries such as OpenMP; the availability of (relatively) inexpensive manycore accelerator devices (e.g., GPUs); the availability of free software platforms like CUDA, OpenACC, OpenCL, and OpenMP for using accelerators; the development of inexpensive single board computers (SBCs) like the Raspberry Pi, and other changes. The paper details the evolution of PDC education at the author's institution in response to these changes, including curriculum changes, seven different Beowulf cluster designs, and the development of pedagogical tools and techniques specifically for PDC education. The paper also surveys many of the hardware and software infrastructure options available to PDC educators, provides a strategy for choosing among them, and provides practical advice for PDC pedagogy. Through these discussions, the reader may see how much PDC education has changed over the past two decades, identify some areas of PDC that have remained stable during this same time period, and so gain new insight into how to efficiently invest one's time as a PDC educator. [ABSTRACT FROM AUTHOR]

The h -restricted edge connectivity λ h is an important parameter to measure the reliability of massive parallel computing system. The λ h of G is the minimum cardinality of a set of edges in G , if any, whose deletion disconnects G , and every remaining component has minimum degree at least h. The arrangement graph is a generalization of the star graph, but its order is more flexible than that of the star graph. This paper investigates the h -restricted edge connectivity of the (n , k) -arrangement graph A n , k , and determines that λ 1 (A n , k) = 2 k (n − k) − 2 , λ 2 (A n , k) = 3 k (n − k) − 6 with k ≤ n − 2. • We study a generalized edge reliability of arrangement graph. • We investigate the h -restricted edge connectivity of the (n , k) -arrangement graph A n , k. • We determine that λ 1 (A n , k) = 2 k (n − k) − 2 , and λ 2 (A n , k) = 3 k (n − k) − 6 with k ≤ 2. [ABSTRACT FROM AUTHOR]

• We analyze the first independent security analysis of PHEMAP, a PUF based protocol. • We present the first third party security analysis of Salted PHEMAP. • We propose two basic/salted PUF based mutual authentication protocols. • We analyze the security of the proposed schemes through formal and informal methods. Recently, using Physical Unclonable Functions (PUF) to design lightweight authentication protocols for constrained environments such as the Internet of Things (IoT) has received much attention. In this direction, Barbareschi et al. recently proposed PHEMAP in Journal of Parallel and Distributed Computing , a PUF based mutual authentication protocol. Also, they extended it to the later designed Salted PHEMAP, for low-cost cloud-edge (CE) IoT devices. This paper presents the first third-party security analysis of PHEMAP and Salted PHEMAP to the best of our knowledge. Despite the designer's claim, we show that these protocols are vulnerable to impersonation, de-synchronization, and traceability attacks. The success probability of the proposed attacks is '1', while the complexity is negligible. In addition, we introduce two enhanced lightweight authentication protocols based on PUF chains (called PBAP and Salted PBAP), using the same design principles as PHEMAP and Salted PHEMAP. With the performance evaluation and the security analysis, it is justified that the two proposed schemes are practically well suited for use in resource-constrained IoT environments. [ABSTRACT FROM AUTHOR]

Race conditions, which occur when compute workers do not synchronise correctly, are considered undesirable in parallel computing, as they introduce often-unintended stochastic behaviour. This study presents an asynchronous parallel algorithm with a race condition, and demonstrates that it reaches a superior solution faster than the equivalent synchronous algorithm without the race condition. Specifically, a parallel simulated annealing algorithm that solves a graph mapping problem (placement) is used to explore this. This paper illustrates how problem size and degree of parallelism affects both the collision rate caused by the race condition, and convergence time. The asynchronous approach reaches a superior solution in half the time of the equivalent synchronous approach. The solver presented here can be applied to application deployment in distributed systems, and the concept can be applied to problems solvable by global optimisation methods, where fitness errors can be tolerated in exchange for faster execution. • Performance gains from asynchronous algorithms are worth the race condition. • Parallel simulated annealing applied to placement problems. • Race conditions are stochastic behaviours, and can be used constructively. • Implications for optimisation problems in high-performance computing. [ABSTRACT FROM AUTHOR]

As GPUs are being used for general purpose computations, applications with different memory access requirements have emerged. In spite of the growing demand, only few GPU coherence protocols and memory models have been explored in research, and even fewer models have been implemented in products. However, in the CPU domain a diverse range of memory models for parallel programming have been proposed, which explore the interplay between performance and programmability. Sequential consistency (SC) is one of the strict memory models. It provides the most programmer intuitive execution of memory operation but it imposes strict ordering restrictions on memory operations that cause performance overhead. Hence, implementing and supporting SC is one of the most challenging tasks in any computing platform, and GPUs are no exception. As such in this paper, we propose a GPU architecture that implements SC memory model with minimal performance and power overhead. We achieve this goal by designing a mechanism to detect races between different streaming multiprocessors (SMs) dynamically at runtime. The race is detected using a signature-based mechanism to keep track of sets of unseen updates for each SM which significantly reduces the hardware implementation cost, with a small increase in invalidation traffic. Our experiments show that dynamic race detection can be used to implement sequential consistency with 5% performance overhead. [ABSTRACT FROM AUTHOR]

The Intel DPC++ Compatibility Tool is a component of the Intel oneAPI Base Toolkit. This tool automatically transforms CUDA code into Data Parallel C++ (DPC++), thus assisting in the migration process. DPC++ is an implementation of the programming standard for heterogeneous computing known as SYCL, which unifies the development of parallel applications on CPUs, GPUs or even FPGAs. This paper analyzes the DPC++ Compatibility Tool by considering the manual intervention required and the problems encountered while migrating the Rodinia benchmarks. For this suite, this tool achieves an impressive rate of almost 87% for code successfully migrated. Moreover, a comparative study of the performance obtained by the migrated code was carried out, showing a moderate overhead in most of the migrated examples. Finally, a performance comparison on different devices was also performed. • Performance and portability are big challenges in heterogeneous computing. • Intel DPC++ Compatibility Tool transforms CUDA code into Data Parallel C++ (DPC++) easing the migration process. • A comparative study of the performance obtained by the migrated code is performed with Rodinia benchmarks. [ABSTRACT FROM AUTHOR]

Mutual information can effectively measure the correlation between categorical attributes. However, it is found to be quite computationally intensive and time consuming process for enormous size and different distribution data sets. It involves steps for computation of marginal entropies, probability distribution and so on. Spark is a fast, general-purpose parallel framework designed specifically for large-scale data processing. Main motivation of this paper is to provide an intelligent method for parallel mutual information calculation based on Spark computing environment with maintaining the synchronization between different computing nodes. Proposed method named MiCS-P has been able to execute with different number of computing nodes, and gives significant speedup working with different dimensions and sizes of data sets. The MiCS-P algorithm adopts column-wise transformation scheme, which is conducive to the calculation of mutual information between a large number of feature pairs. And to alleviate imbalanced load causing long execution times, we implement a two-phase virtual partitioning scheme running on Spark. • A Spark-based parallel mutual-information computing system is proposed for categorical data. • A column-wise transformation is designed and implemented on Spark. • A virtual partitioning scheme is utilized on Spark to mitigate the data skewness issue. • Extensive experiments are carried out to evaluate MiCS-P. [ABSTRACT FROM AUTHOR]

• The EasyPAP environment allows students to really focus on parallelism while developing OpenMP, OpenCL or MPI kernels. • Interactive display of increasingly optimized variants of a 2D kernel help to popularize HPC. • Linking CPUs and image tiles in monitoring windows allow to better understand scheduling policies. • Linking tasks and image tiles when visualizing port mortem execution traces help to diagnose parallel efficiency issues. This paper presents EasyPAP , an easy-to-use programming environment designed to help students to learn parallel programming. EasyPAP features a wide range of 2D computation kernels that the students are invited to parallelize using Pthreads, OpenMP, OpenCL or MPI. Execution of kernels can be interactively visualized, and powerful monitoring tools allow students to observe both the scheduling of computations and the assignment of 2D tiles to threads/processes. By focusing on algorithms and data distribution, students can experiment with diverse code variants and tune multiple parameters, resulting in richer problem exploration and faster progress towards efficient solutions. We present selected lab assignments which illustrate how EasyPAP improves the way students explore parallel programming. [ABSTRACT FROM AUTHOR]

• Heterogeneous parallel computing is rarely taught in required undergraduate courses. • Concepts of heterogeneous computing can be taught even in CS1 and CS2. • Pollack's Rule and Amdahl's Law help motivate the shift to heterogeneous processors. • Using ARM processors, an instructor can show a low-power mode and SIMD operations. Heterogeneous architectures have emerged as a dominant platform, not only in high-performance computing but also in mobile processing, cloud computing, and the Internet of Things (IoTs). Because the undergraduate computer science curriculum includes so many topics, adding a new course as a required part of the curriculum without increasing the number of hours to graduation is difficult. Integration of heterogeneous computing requires a module-driven approach in which coverage of the topics is broken down into smaller units and dispersed throughout the curriculum. The module-driven approach has been successfully implemented in introducing parallel and distributed computing concepts. In this paper, we present a set of four teaching modules that introduce fundamental concepts in heterogeneous computing in lower-division computer science courses. The goal of these modules is not to teach students how to program heterogeneous systems but rather to expose them to this emerging trend and prepare them for material in future classes. Although concepts are covered at a high level, the modules emphasize active learning and include lab assignments that provide students with hands-on experience. We also present initial evaluation results for two of these modules based on their use in undergraduate courses at Texas State University. The results are quite encouraging both in terms of learning outcomes and student engagement and interest. [ABSTRACT FROM AUTHOR]

• The generalized k -connectivity κ k (G) is the maximum number of internally disjoint trees connecting any k vertices of G. • The substructure properties of the n -dimensional augmented cube A Q n are given. • The results of κ 3 (A Q n) = 2 n − 2 for n = 3 or n ≥ 5 are derived. • κ 3 (A Q 4) = 5 is derived. Given a connected graph G and S ⊆ V (G) with | S | ≥ 2 , a tree T in G is called an S -Steiner tree (or S -tree for short) if S ⊆ V (T). Two S -trees T 1 and T 2 are internally disjoint if E (T 1) ∩ E (T 2) = ∅ and V (T 1) ∩ V (T 2) = S. The packing number of internally disjoint S -trees, denoted as κ G (S) , is the maximum size of a set of internally disjoint S -trees in G. For an integer k ≥ 2 , the generalized k -connectivity (abbr. κ k -connectivity) of a graph G is defined as κ k (G) = min { κ G (S) | S ⊆ V (G) and | S | = k }. The n -dimensional augmented cube, denoted as A Q n , is an important variant of the hypercube that possesses several desired topology properties such as diverse embedding schemes in applications of parallel computing. In this paper, we focus on the study of constructing internally disjoint S -trees with | S | = 3 in A Q n. As a result, we completely determine the κ 3 -connectivity of A Q n as follows: κ 3 (A Q 4) = 5 and κ 3 (A Q n) = 2 n − 2 for n = 3 or n ≥ 5. [ABSTRACT FROM AUTHOR]