Search

Pareto-based multi-objective evolutionary algorithms use non-dominated sorting as an intermediate step. These algorithms are easy to parallelize as various steps of these algorithms are independent of each other. Researchers have focused on the parallelization of non-dominated sorting in order to reduce the execution time of these algorithms. In this paper, we focus on one of the initial approaches for non-dominated sorting also known as naive approach, proposed by Srinivas et al. and explore the scope of parallelism in this approach. Parallelism is explored in the considered approach in three different ways considering Parallel Random Access Machine, Concurrent Read Exclusive Write model. The time and space complexities of three different parallel versions are also analyzed. Analysis of parallel algorithms is usually carried out under the assumption that an unbounded number of processors are available. Thus, the same assumption has been considered in our analysis too and we have obtained the maximum number of processors required for three parallel versions.

Motivated by the dynamic assortment offerings and item pricings occurring in e-commerce, we study a general problem of allocating finite inventories to heterogeneous customers arriving sequentially. We analyze this problem under the framework of competitive analysis, where the sequence of customers is unknown and does not necessarily follow any pattern. Previous work in this area, studying online matching, advertising, and assortment problems, has focused on the case where each item can only be sold at a single price, resulting in algorithms which achieve the best-possible competitive ratio of 1-1/e. In this paper, we extend all of these results to allow for items having multiple feasible prices. Our algorithms achieve the best-possible weight-dependent competitive ratios, which depend on the sets of feasible prices given in advance. Our algorithms are also simple and intuitive; they are based on constructing a class of universal ``value functions'' which integrate the selection of items and prices offered. Finally, we test our algorithms on the publicly-available hotel data set of Bodea et al. (2009), where there are multiple items (hotel rooms) each with multiple prices (fares at which the room could be sold). We find that applying our algorithms, as a ``hybrid'' with algorithms which attempt to forecast and learn the future transactions, results in the best performance.

The Parallel Random Access Machines (PRAM) abstraction is the simplest and most elegant algorithmic model for the design and analysis of parallel algorithms. It consists of different models categorized based on the underlying memory access mode used, the most powerful of which is the Concurrent Read Concurrent Write (CRCW) model. A PRAM algorithm describes a series of rounds, each of which consists of a collection of operations that can be executed concurrently within the same time step. However, the lack of support for concurrent memory accesses and the prevalence of asynchronous programming models led to the belief that implementing CRCW PRAM algorithms is unattainable and prompted many to avoid this model except for theoretical studies of optimal performance. In this work, we study the arbitrary and common concurrent writes in the CRCW PRAM model and explore implementation challenges on general-purpose systems. Moreover, we examine current practices for implementing common/arbitrary concurrent writes and propose a new efficient lightweight and thread-safe method to implement concurrent writes through leveraging atomic instructions. To demonstrate the efficacy of our method, we developed OpenMP kernels for classical CRCW PRAM algorithms and provide experimental results and comparisons based on run time performance measured over the x86 multicore architecture. Our results show a performance speedup compared to current practices up to 4.5x across all our benchmarks.

As computational resources become more efficient and data sizes grow, data movement is fast becoming the dominant cost in computing. Processing-in-Memory is emerging as a key technique for reducing costly data movement, by enabling computation to be executed on compute resources embedded in the memory modules themselves. This paper presents the Processing-in-Memory (PIM) model, for the design and analysis of parallel algorithms on systems providing processing-in-memory modules. The PIM model focuses on keys aspects of such systems, while abstracting the rest. Namely, the model combines (i) a CPU-side consisting of parallel cores with fast access to a small shared memory of size M words (as in traditional parallel computing), (ii) a PIM-side consisting of P PIM modules, each with a core and a local memory of size Θ(n/P) words for an input of size n (as in traditional distributed computing), and (iii) a network between the two sides. The model combines standard parallel complexity metrics for both shared memory (work and depth) and distributed memory (local work, communication time) computing. A key algorithmic challenge is to achieve load balance among the PIM modules in both their communication and their local work, while minimizing the communication time. We demonstrate how to overcome this challenge for an ordered search structure, presenting a parallel PIM-skiplist data structure that efficiently supports a wide range of batch-parallel queries and updates.

Non-dominated sorting is a crucial component of Pareto-based multi- and many-objective evolutionary algorithms. As the number of objectives increases, the execution time of a multi-objective evolutionary algorithm increases, too. Since multi-objective evolutionary algorithms normally have a low data dependency, research-ers have increasingly adopted parallel programming techniques to reduce their execution time. Evidently, it is also desirable to parallelize non-dominated sorting. There are some recent proposals which focus on the parallelization of non-dominated sorting, with a particular emphasis on a very well-known approach called fast non-dominated sorting. In this paper, however, we explore the scope of parallelism in an approach called divide-and-conquer based non-dominated sorting (DCNS), which we recently introduced. This paper explores the parallelism from a theoretical point of view. The parallelization of the DCNS approach has been explored considering the PRAM-CREW (Parallel Random Access Machine, Concurrent Read Exclusive Write) model. The analysis of parallel algorithms is usually carried out under the assumption that an unbounded number of processors are available. So, in our analysis, we have also considered the same assumption. The time and space complexities of the parallel version of the DCNS approach is obtained in different scenarios. The time complexity of the parallel version of the DCNS approach in different scenarios is proved to be $$\mathcal {O}(\log M + N)$$ . We have also obtained the maximum number of processors which can be required by the parallel version of the DCNS approach. The comparison of the parallel version of the DCNS approach with respect to some other approaches is also performed.

In order to solve a problem in parallel we need to undertake the fundamental step of splitting the computational tasks into parts, i.e. decomposing the problem solving. A whatever decomposition does not necessarily lead to a parallel algorithm with the highest performance. This topic is even more important when complex parallel algorithms must be developed for hybrid or heterogeneous architectures. We present an innovative approach which starts from a problem decomposition into parts (sub-problems). These parts will be regarded as elements of an algebraic structure and will be related to each other according to a suitably defined dependency relationship. The main outcome of such framework is to define a set of block matrices (dependency, decomposition, memory accesses and execution) which simply highlight fundamental characteristics of the corresponding algorithm, such as inherent parallelism and sources of overheads. We provide a mathematical formulation of this approach, and we perform a feasibility analysis for the performance of a parallel algorithm in terms of its time complexity and scalability. We compare our results with standard expressions of speed up, efficiency, overhead, and so on. Finally, we show how the multilevel structure of this framework eases the choice of the abstraction level (both for the problem decomposition and for the algorithm description) in order to determine the granularity of the tasks within the performance analysis. This feature is helpful to better understand the mapping of parallel algorithms on novel hybrid and heterogeneous architectures.

The paper describes the system of mass practical assignments formed in the framework of the course “Supercomputing Simulation and Technologies” at the Faculty of Computational Mathematics and Cybernetics at Lomonosov Moscow State University. The practical assignments were held for four years, from 2016 to 2019, and each year about 200 students of the second year of the magistracy passed through them. These practical assignments are aimed at developing skills in the efficient use of parallel computing systems and knowledge of properties of parallel algorithms. The basics of performing the described assignments is the deep analysis of parallel algorithms and use of the concept of the information structure of algorithms and programs. This concept is extremely important for writing efficient parallel programs, so it should be the cornerstone of modern IT education.

This letter proposes a unified GPU-parallelizable approach for robot forward dynamics (FD) computation based on the key fact that parallelism of prevailing FD algorithms benefits from the essential band sparsity of the joint space inertia (JSI) matrix or its inverse. The existing FD algorithms are categorized into three classes: direct JSI algorithms, propagation algorithms, and constraint force algorithms. Their associated systems of linear equations are transformed into a set of block bidiagonal (the first and second classes) and tridiagonal (the third class) linear systems, which can be conveniently and efficiently parallelized over the existing CPU–GPU programming platforms using various state-of-the-art parallel algorithms, such as parallel all-prefix sum (scan) and odd–even elimination. This high-level perspective allows unified and efficient implementation of all three classes of algorithms and also other potentially efficient algorithms, with the bonus that different algorithms can be swiftly compared to recommend problem-specific solutions.

The world around us may be viewed as a network of entities interconnected via their social, economic, and political interactions. These entities and their interactions form a social network. A social network is often modeled as a graph whose nodes represent entities, and edges represent interactions between these entities. These networks are characterized by the collective latent behavior that does not follow trivially from the behaviors of the individual entities in the network. One such behavior is the existence of hierarchy in the network structure, the sub-networks being popularly known as communities. Discovery of the community structure in a social network is a key problem in social network analysis as it refines our understanding of the social fabric. Not surprisingly, the problem of detecting communities in social networks has received substantial attention from the researchers. In this paper, we propose parallel implementations of recently proposed community detection algorithms that employ variants of the well-known quantum-inspired evolutionary algorithm (QIEA). Like any other evolutionary algorithm, a quantum-inspired evolutionary algorithm is also characterized by the representation of the individual, the evaluation function, and the population dynamics. However, individual bits called qubits, are in a superposition of states. As chromosomes evolve individually, the quantum-inspired evolutionary algorithms (QIEAs) are intrinsically suitable for parallelization. In recent years, programmable graphics processing units — GPUs, have evolved into massively parallel environments with tremendous computational power. NVIDIA® compute unified device architecture (CUDA®) technology, one of the leading general-purpose parallel computing architectures with hundreds of cores, can concurrently run thousands of computing threads. The paper proposes novel parallel implementations of quantum-inspired evolutionary algorithms in the field of community detection on CUDA-enabled GPUs. The proposed implementations employ a single-population fine-grained approach that is suited for massively parallel computations. In the proposed approach, each element of a chromosome is assigned to a separate thread. It is observed that the proposed algorithms perform significantly better than the benchmark algorithms. Further, the proposed parallel implementations achieve significant speedup over the serial versions. Due to the highly parallel nature of the proposed algorithms, an increase in the number of multiprocessors and GPU devices may lead to a further speedup.

We present an efficient distributed memory parallel algorithm for computing connected components in undirected graphs based on Shiloach-Vishkin’s PRAM approach. We discuss multiple optimization techniques that reduce communication volume as well as load-balance the algorithm. We also note that the efficiency of the parallel graph connectivity algorithm depends on the underlying graph topology. Particularly for short diameter graph components, we observe that parallel Breadth First Search (BFS) method offers better performance. However, running parallel BFS is not efficient for computing large diameter components or large number of small components. To address this challenge, we employ a heuristic that allows the algorithm to quickly predict the type of the network by computing the degree distribution and follow the optimal hybrid route. Using large graphs with diverse topologies from domains including metagenomics, web crawl, social graph and road networks, we show that our hybrid implementation is efficient and scalable for each of the graph types. Our approach achieves a runtime of 215 seconds using 32 K cores of Cray XC30 for a metagenomic graph with over 50 billion edges. When compared against the previous state-of-the-art method, we see performance improvements up to 24 $\times$ .

This paper presents oneapproach for parallel algorithms representation. The proposed model is practiceoriented and its name is AMPA (Agenda Model for Parallel Algorithms) due tobasic blocks organization like a schedule. The model uses classical Master/Slaveparadigm. One parallel merge sorting algorithm based on quick sort is presentedwith the discussed AMPA model and also three known representation approaches(description with natural language, pseudo code and PRAM). A survey of professionalopinion about AMPA and other approaches is conducted. The results show thatmost of the interviewed people chooseAMPA as the best way to understand the algorithm.

An edge switch is an operation on a graph (or network) where two edges are selected randomly and one of their end vertices is swapped with each other. Edge switch operations have important applications in graph theory and network analysis, such as in generating random networks with a given degree sequence, modeling and analyzing dynamic networks, and in studying various dynamic phenomena over a network. The recent growth of real-world networks motivates the need for efficient parallel algorithms. The dependencies among successive edge switch operations and the requirement to keep the graph simple (i.e., no self-loops or parallel edges) as the edges are switched lead to significant challenges in designing a parallel algorithm. Addressing these challenges requires complex synchronization and communication among the processors leading to difficulties in achieving a good speedup by parallelization. In this paper, we present distributed memory parallel algorithms for switching edges in massive networks. These algorithms provide good speedup and scale well to a large number of processors. A harmonic mean speedup of 73.25 is achieved on eight different networks with 1024 processors. One of the steps in our edge switch algorithms requires the computation of multinomial random variables in parallel. This paper presents the first non-trivial parallel algorithm for the problem, achieving a speedup of 925 using 1024 processors.

Modern homogeneous parallel platforms are composed of tightly integrated multicore CPUs. This tight integration has resulted in the cores contending for various shared on-chip resources such as Last Level Cache (LLC) and interconnect, leading to resource contention and non-uniform memory access (NUMA). Due to these newly introduced complexities, the performance and energy profiles of real-life scientific applications on these platforms are not smooth and may deviate significantly from the shapes that allowed traditional and state-of-the-art load balancing algorithms to minimize their computation time. In this paper, we propose new model-based methods and algorithms for minimization of time and energy of computations for the most general shapes of performance and energy profiles of data parallel applications observed on the modern homogeneous multicore clusters. We formulate the performance and energy optimization problems and present efficient algorithms of complexity $O(p^2)$ solving these problems where $p$ is the number of processors. It is important to note that the globally optimal solutions found by these algorithms may not load-balance the application. We experimentally study the efficiency and scalability of our algorithms for two data parallel applications, matrix multiplication and fast Fourier transform, on a modern multicore CPU and clusters of such CPUs. We also demonstrate the optimality of solutions determined by our algorithms.

We present parallel lightweight algorithms to construct wavelet trees, rank and select structures, and suffix arrays in a shared-memory setting. The work and depth of our first parallel wavelet tree algorithm match those of the best existing parallel algorithm while requiring asymptotically less memory and our second algorithm achieves the same asymptotic bounds for small alphabet sizes. Our experiments show that they are both faster and more memory-efficient than existing parallel algorithms. We also present an experimental evaluation of the parallel construction of rank and select structures, which are used in wavelet trees. Next, we design the first parallel suffix array algorithm based on induced copying. Our induced copying requires linear work and polylogarithmic depth for constant alphabets sizes. When combined with a parallel prefix doubling algorithm, it is more efficient in practice both in terms of running time and memory usage compared to existing parallel implementations. As an application, we combine our algorithms to build the FM-index in parallel.

Parallel programming patterns are built upon a foundation of serial programming patterns to maximize the efficiency of parallel code and effectively use parallel resources available in a given system. This work focuses on using NVIDIA GPUs with the CUDA C library for parallel computing. The goal is to implement parallel versions of a genetic algorithm using the Map and Fork-Join parallel patterns to improve its performance. The intent is to demonstrate that the parallel patterns can be implemented on the CUDA platform and achieve increases in speedup, efficiency, and scalability with the parallel genetic algorithms. A comparative assessment of the two parallel patterns is conducted by configuring them to evaluate instances of the Travelling Salesman Problem (TSP) using different data sets. This assessment considers each algorithm’s run time performance, their use of system resources, and their required overhead.

Analysis of parallel algorithms for graphics processors allows you to determine the bottlenecks of the algorithm that affect its performance on a particular computing system. Algorithms can be analyzed both at the AGM level and at the level of the CPU-GPU system. Despite the fact that the model does not reflect the overlap of the execution of computational operations and operations of access to the global memory, but estimates the upper limit of the execution time of the algorithm on the AGM, in any parallel algorithms for the AGM it is necessary to reduce this parameter of the algorithm due to the large number of clock cycles spent by the multiprocessor to implement global memory access operations.

Many sorting algorithms have been proposed and implemented in previous years. These algorithms are usually judged by their performance in term of algorithm growth rate according to the input size. Efficient sorting algorithm implementation is important for optimizing the use of other algorithms such as searching algorithms, load balancing algorithms, etc. In this paper, parallel Quicksort, parallel Merge sort, and parallel MergeQuicksort algorithms are evaluated and compared in terms of the running time, speedup, and parallel efficiency. These sorting algorithms are implemented using Message Passing Interface (MPI) library, and results have been conducted using IMAN1 supercomputer. Results show that the run time of parallel Quicksort algorithm outperforms both Merge sort and Merge-Quicksort algorithms. Moreover, on large number of processors, parallel Quicksort achieves the best parallel efficiency of up to 88%, while Merge sort and MergeQuicksort algorithms achieve up to 49% and 52% parallel efficiency, respectively.

© 2016 We describe parallel algorithms for computing maximal cardinality matching in a bipartite graph on distributed-memory systems. Unlike traditional algorithms that match one vertex at a time, our algorithms process many unmatched vertices simultaneously using a matrix-algebraic formulation of maximal matching. This generic matrix-algebraic framework is used to develop three efficient maximal matching algorithms with minimal changes. The newly developed algorithms have two benefits over existing graph-based algorithms. First, unlike existing parallel algorithms, cardinality of matching obtained by the new algorithms stays constant with increasing processor counts, which is important for predictable and reproducible performance. Second, relying on bulk-synchronous matrix operations, these algorithms expose a higher degree of parallelism on distributed-memory platforms than existing graph-based algorithms. We report high-performance implementations of three maximal matching algorithms using hybrid OpenMP-MPI and evaluate the performance of these algorithm using more than 35 real and randomly generated graphs. On real instances, our algorithms achieve up to 200 × speedup on 2048 cores of a Cray XC30 supercomputer. Even higher speedups are obtained on larger synthetically generated graphs where our algorithms show good scaling on up to 16,384 cores.

Frequent sequence mining is well known and well studied problem in datamining. The output of the algorithm is used in many other areas like bioinformatics, chemistry, and market basket analysis. Unfortunately, the frequent sequence mining is computationally quite expensive. In this paper, we present a novel parallel algorithm for mining of frequent sequences based on a static load-balancing. The static load-balancing is done by measuring the computational time using a probabilistic algorithm. For reasonable size of instance, the algorithms achieve speedups up to $\approx 3/4\cdot P$ where $P$ is the number of processors. In the experimental evaluation, we show that our method performs significantly better then the current state-of-the-art methods. The presented approach is very universal: it can be used for static load-balancing of other pattern mining algorithms such as itemset/tree/graph mining algorithms.

The current microprocessors are concentrating on the multiprocessor or multi - core system architecture. The parallel algorithms are recently focusing on multi - core system to take full utilization of multiple processors available in the system. The design of parallel algorithm and performance measurement is the major issue on today's multi - core environment. Numerical problems arise in almost every branch of science which requires fast solution. In this paper we have presented parallel algorithms for computing the solution of system of non - linear equations and approximate the simple zeros of polynomial equations. The experimental results reveal that the performances of parallel algorithms are better than sequential. We implemented the parallel algorithms using multithreading features of OpenMP.

We expose a systematic approach for developing distributed-memory parallel matrix-matrix multiplication algorithms. The journey starts with a description of how matrices are distributed to meshes of nodes (e.g., MPI processes), relates these distributions to scalable parallel implementation of matrix-vector multiplication and rank-1 update, continues on to reveal a family of matrix-matrix multiplication algorithms that view the nodes as a two-dimensional (2D) mesh, and finishes with extending these 2D algorithms to so-called three-dimensional (3D) algorithms that view the nodes as a 3D mesh. A cost analysis shows that the 3D algorithms can attain the (order of magnitude) lower bound for the cost of communication. The paper introduces a taxonomy for the resulting family of algorithms and explains how all algorithms have merit depending on parameters such as the sizes of the matrices and architecture parameters. The techniques described in this paper are at the heart of the Elemental distributed-memory line...

Evolutionary algorithms (EAs) are a large family of heuristic optimization algorithms. They are problem independent and have been applied in various optimization problems. Thus, general analysis tools are especially appealing for guiding the analysis of EAs in various situations. This paper develops the switch analysis approach for running time analysis of EAs, revealing their average computational complexity. Unlike previous analysis approaches that analyze an algorithm from scratch, the switch analysis makes use of another well-analyzed algorithm and, by contrasting them, can lead to better results. We investigate the power of switch analysis by comparing it with two commonly used analysis approaches, the fitness level method and the drift analysis. We define the reducibility between two analysis approaches for comparing their power. By the reducibility relationship, it is revealed that both the fitness level method and the drift analysis are reducible to the switch analysis, as they are equivalent to specific configurations of the switch analysis. We further show that the switch analysis is not reducible to the fitness level method, and compare it with the drift analysis on a concrete analysis case (the discrete linear problem). The reducibility study might shed some light on the unified view of different running time analysis approaches.

We propose to design new algorithms for motion planning problems using the well-known Domain Subdivision paradigm, coupled with "soft" predicates. Unlike the traditional exact predicates in computational geometry, our primitives are only exact in the limit. We introduce the notion of resolution-exact algorithms in motion planning: such an algorithm has an "accuracy" constant K 1 , and takes an arbitrary input "resolution" parameter e 0 such that: if there is a path with clearance Ke, it will output a path with clearance e / K ; if there are no paths with clearance e / K , it reports "NO PATH". Besides the focus on soft predicates, our framework also admits a variety of global search strategies including forms of the A* search and probabilistic search.Our algorithms are theoretically sound, practical, easy to implement, without implementation gaps, and have adaptive complexity. Our deterministic and probabilistic strategies avoid the Halting Problem of current probabilistically complete algorithms. We develop the first provably resolution-exact algorithms for motion-planning problems in SE ( 2 ) = R 2 i? S 1 . To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms.

In this work, a parallel arithmetic program for the MD (molecular dynamics) simulation study of a large-sized system is proposed and reformed, based on the previous program with PVM (Parallel Virtual Machine) model applied in a small-sized system for liquid metals. Our methodology is combined with the MPI (message passing interface) and OpenMP (Open Multiple Processing) programming model using the spatial domain decomposition method, conquering the problems occurred in PVM model and enlarging the scale of simulated system. Comparing with the previous small-sized system consisting of 50,000–100,000 atoms, the large-sized system is consist of 5,000,000–10,000,000 atoms and the simulation results are more closely to the real situation of the simulated system. In this paper, the performance of parallel program using MPI + OpenMP model is analyzed, showing better speedup, parallel efficiency, and scalability. Finally, we adopt many physical evaluation methods to verify the validity of the simulation results, including pair distribution function, bond-type index analysis, atomic clusters analysis and visualizing analysis. From these physical results, it is clear that the simulation results are in good agreement with the experimental results, which confirm the correctness of the program in simulation.

This paper investigates the impact of communication between optimization algorithms running in parallel. In particular, we focus on the weighted maximum cut (WMAXCUT) problem and compare different communication strategies between teams of GES algorithms running in parallel. The results obtained by teams encourage the development of team algorithms. They were significantly better than the algorithmic portfolio (no communication) approach and suggest that the communication between algorithms running in parallel is a promising research direction.

We propose a novel computational model for GPUs. Known parallel computational models such as the PRAM model are not appropriate for evaluating GPU-based algorithms. Our model, called AGPU , abstracts the essence of current GPU architectures such as global and shared memory, memory coalescing and bank conflicts. Using our model, we can evaluate asymptotic behavior of GPU algorithms more efficiently than the known models and we can develop algorithms that run fast on real GPU devices. As a showcase, we analyze the asymptotic behavior of basic existing algorithms including reduction, prefix scan, and comparison sorting. We further develop new algorithms by detecting and resolving performance bottlenecks of the existing algorithms. Our reduction algorithm has the optimal time and I/O complexities and works with non-commutative operators. Our com- parison sorting algorithm has the optimal I/O complexity. Additionally, we show our algorithms run faster than the existing algorithms not only in theory but also in practice.

The existing researches of fast parallel algorithms for DCT-based real-valued discrete Gabor transform and expansion are limited to theoretical analysis. In this paper, parallel computing based implementations of parallel lattice structure algorithm are presented. The communication issues are not considered in original algorithms which enable the efficiency lower than serial fast algorithm in implementation. In view of this, improved implementation methods are proposed both for transform and expansion. The recursive part of the original algorithms is expanded into an iterative form. This makes the interprocess communication converted into serial calculation. Thus, each parallel channel (i.e., process in parallel computing) in the improved method is independent, thereby reducing the interprocess communication greatly. Finally, algorithms are tested on a parallel computer. The experimental results are compared and analyzed, which indicate that the proposed implementation methods are attractive for real-time signal processing as compared to the existing parallel lattice structure algorithm and the fastest serial algorithm.

Over the years many interesting and efficient parallel algorithms have been developed to solve a wide variety of problems, but not much attention has been paid to studying the inherent parallelism in sequential algorithms---i.e., understanding the depth of their dependence structure, and how shallow dependence structures might beused to develop efficient parallel implementations. In this talk I will describe recent work on analyzing the dependence depth of iterative sequential algorithms---ones that loop over a collection of elements. Many of these algorithms have deep dependence chains in the worst case, but shallow chains (polylog w.h.p.) if the elements are randomly ordered. Examples include many fundamental algorithms: the Knuth shuffle for random permutations, sorting by insertion into a binary search tree, greedy maximal independent set (MIS), greedy maximal matching, greedy graph-coloring, counting cycles in a permutation, incremental k-dimensional linear programming, and incremental 2d Delaunay triangulation. An advantage of the approach is that it can lead to very simple and efficient parallel algorithms. Our MIS algorithm, for example can be coded in a dozen or so lines, and is significantly faster than Luby's algorithm on modern multicore machines. Also the approach encourages snapping the view that sequential and parallel algorithms are distinct, and instead thinking of algorithms, in general, as collections of instructions with dependences among them.

Adaptive Dynamic Programming (ADP) with critic-actor architecture is a useful way to achieve online learning control. The algorithm Gaussian-Kernel Adaptive Dynamic Programming (GK-ADP) that has been developed before has a kind of two-phase iteration, which not only approximates value function, but also optimizes hyper-parameters simultaneously. However, just like most iteration algorithms are applied in practice, the scale of sample set will increase as the complexity of the system increases, and it will induce a high computation cost. In order to speed up computation, a practical acceleration method using parallel computation for GK-ADP is presented in this paper. To realize parallel computation, a high efficient configuration based on CUDA is designed, in which a group of GPUs work in parallel to compute the most complex part of GK-ADP. The comparison test illustrates that the computation burden which hinders GK-ADP's application is reduced to a large extent when the parallel computing is introduced.

Parallel join algorithms have received much attention in recent years, due to the rapid development of massively parallel systems such as MapReduce and Spark. In the database theory community, most efforts have been focused on studying worst-optimal algorithms. However, the worst-case optimality of these join algorithms relies on the hard instances having very large output sizes. In the case of a two-relation join, the hard instance is just a Cartesian product, with an output size that is quadratic in the input size.In practice, however, the output size is usually much smaller. One recent parallel join algorithm by Beame et al.[8] has achieved output-optimality, i.e., its cost is optimal in terms of both the input size and the output size, but their algorithm only works for a 2-relation equi-join, and has some imperfections. In this paper, we first improve their algorithm to true optimality. Then we design output-optimal algorithms for a large class of similarity joins. Finally, we present a lower bound, which essentially eliminates the possibility of having output-optimal algorithms for any join on more than two relations.

This chapter introduces parallel scan (prefix-sum), an important parallel computation pattern and the concept of work-efficiency for parallel algorithms. It introduces three styles of kernels: Kogge-Stone, Brent-Kung, and two-phase hybrid. Each of these kernels presents a different tradeoff in terms of work-efficiency, speed, and complexity. The chapter then introduces two hierarchical parallel scan algorithms that are designed to process arbitrarily long input lists while maintaining work efficiency.

This paper describes demonstrative software simulator "E14", helpful in studying on an ordinary PC essentials of parallel calculations. It contains five virtual processors with identical instruction set, one of which controls the other four. Simulator has several mechanisms of data exchange between processors, so it can be used for studying both architectures with shared and distributed memory. Parallel architecture of "E14" naturally extends classical single-processor one, hence proposed approach makes students' knowledge more systematic. "E14" may also be employed as a platform for the estimation of parallel algorithms' performance. The example, considered in the paper, clearly demonstrates how data exchange between processors may essentially degrade speedup, predicted by Amdahl's law.

Mining class association rules (CARs) is an essential, but time-intensive task in Associative Classification (AC). A number of algorithms have been proposed to speed up the mining process. However, sequential algorithms are not efficient for mining CARs in large datasets while existing parallel algorithms require communication and collaboration among computing nodes which introduces the high cost of synchronization. This paper addresses these drawbacks by proposing three efficient approaches for mining CARs in large datasets relying on parallel computing. To date, this is the first study which tries to implement an algorithm for parallel mining CARs on a computer with the multi-core processor architecture. The proposed parallel algorithm is theoretically proven to be faster than existing parallel algorithms. The experimental results also show that our proposed parallel algorithm outperforms a recent sequential algorithm in mining time.

Parallel algorithms for distributed memory computers should be granular, in which case the set of algorithmic operations is split into sets known as computation grains, or tiles. Conditions are proposed and proved under which data is used in the same granular computation process where it was determined. These conditions can be used to estimate the number of communication operations in alternative versions of parallel algorithms.

The high intensity of research and modeling in fields of mathematics, physics, biology and chemistry requires new com- puting resources. For the big computational complexity of such tasks computing time is large and costly. The most efficient w ay to increase efficiency is to adopt parallel principles. Purp ose of this paper is to present the issue of parallel computing with em- phasis on the analysis of parallel systems, the impact of commu- nication delays on their efficiency and on overall execution time. Paper focuses is on finite algorithms for solving systems of l in- ear equations, namely the matrix manipulation (Gauss elimina- tion method, GEM). Algorithms are designed for architectures with shared memory (open multiprocessing, openMP), distributed- memory (message passing interface, MPI) and for their combina- tion (MPI + openMP). The properties of the algorithms were an- alytically determined and they were experimentally verifie d. The conclusions are drawn for theory and practice.

We revisit the classical problem of the reduction collective operation in a heterogeneous environment. We discuss and evaluate four algorithms that are non-clairvoyant, that is, they do not know in advance the computation and communication costs. On the one hand, Binomial-stat and Fibonacci-stat are static algorithms that decide in advance which operations will be reduced, without adapting to the environment; they were originally defined for homogeneous settings. On the other hand, Tree-dyn and Non-Commut-Tree-dyn are fully dynamic algorithms, for commutative or non-commutative reductions. We show that these algorithms are approximation algorithms with constant or asymptotic ratios. We assess the relative performance of all four non-clairvoyant algorithms with heterogeneous costs through a set of simulations. Our conclusions hold for a variety of distributions. Copyright © 2014 John Wiley & Sons, Ltd.

With the industry-wide switch to multicore and manycore architectures, parallel computing has become the only venue in sight for continued growth in application performance. In order for the performance of an application to grow with future generations of hardware, a significant portion of its computation must be done with scalable parallel algorithms. It is therefore important to develop and deploy as many scalable parallel algorithms as possible. This paper takes a critical look at the major challenges involved in the development of scalable parallel algorithms and points to needs for compiler tool innovations to help address these challenges.

It becomes more and more important to design high-speed parallel cryptographic algorithms due to a growing need for information security. Conic curves cryptography is a new developing direction in the field of information security in recent years and there are less works focused on the parallel encryption algorithms for conic curves crypto system. This paper proposes four parallel algorithms for conic curves cryptosystem over finite field GF(2 n ). One parallel algorithm of modular-multiplication is designed by analyzing its data dependency and making some modifications of several steps. In order to figure out the average runtime, we consider the probability distributions of different cases to compute the mathematical expectation. The operations of point-addition, point-double and pointmultiplication, three fundamental point operations in conic curves cryptosystem over finite field GF(2 n ), are paralleled based on this parallel algorithm of modular-multiplication and two parallel algorithms we proposed before. Time complexities and speedup ratios of the parallel algorithms and the sequential algorithms are calculated to make the quantitative comparison. The performance evaluation shows better efficiencies of the proposed parallel algorithms compared to the traditional algorithms.

We propose a parallel algorithm for computing exact solutions to the problem of minimizing the number of multileaf collimator apertures needed in step-and-shoot intensity modulated radiotherapy. These problems are very challenging particularly as the problem size increases. Here, we investigate how advanced parallel computing methods can be applied to these problems with a focus on the issues that are peculiar to parallel search algorithms and do not arise in their serial counterparts. A previous paper by the authors presented the MU---RD method for solving such problems using a serial constraint programming based search method. This method is being used as the starting point for a parallel implementation. The key challenges in creating a parallel implementation are ensuring that the CPUs are not starved of work and avoiding unnecessary computation due to the rearrangement of the search order in the parallel version. We show that efficient parallel optimisation is possible by dynamically changing the way work is split with potentially multiple tree search processes as well as parallel search of nodes. A weakly sorted queueing system is used to ensure appropriate prioritisation of tasks. Numerical results are presented to demonstrate the effectiveness of our algorithms in scaling from 8 to 64 CPUs.

As multicore processors become ubiquitous, the improved performance available to parallel programs is a great motivation to computationally demanding evolutionary algorithms (EAs) to turn into parallel EAs (PEAs) and to be able to exploit the power of multicores. Parallel computing is a powerful way to reduce the computation time and to improve the quality of EAs solutions. To the stochastic nature of EAs, the known variability of the parallel programs execution times on multicores adds more complexity on PEAs performance evaluations. Performance evaluation methodologies need to adequately deal with the non-determinism in the experimental set. To obtain correct conclusions it is necessary to apply rigorous statistical procedures. The usual estimation of the speedup of a parallel program as the ratio of the sequential execution time and the parallel execution time may not be appropriated if some care is not taken. A correct estimation of the speedup as a performance measure is presented. A method based on the factorial experimental design is proposed to identify which are the significant factors on the performance of a PEA executed on a multicore processor. A case study of the performance analysis of a PEA solving a benchmark test function is presented.

The motif finding problem is one of the important and challenging problems in bioinformatics. A variety of sequential algorithms have been proposed to find exact motifs, but the running time is still not suitable due to high computational complexity of finding motifs. In this paper we parallelize three efficient sequential algorithms which are HEPPMSprune, PMS5 and PMS6. We implement the algorithms on a Dual Quad-Core machine using openMP to measure the performance of each algorithm. Our experiment on simulated data show that: (1) the parallel PMS6 is faster than the other algorithms in case of challenging instances, while the parallel HEPPMSprune is faster than the other algorithms in most of solvable instances; (2) the scalability of parallel HEPPMSprune is linear for all instances, while the scalability of parallel PMS5 and PMS6 is linear in case of challenging instances only; (3) the memory used by HEPPMSprune is less than that of the other algorithms. NPRP Grant No. 4-1454-1-233 from the Qatar National Research Fund (a member of Qatar Foundation). Scopus

The scientific research community has reached a stage of maturity where its strong need for high-performance computing has diffused into also everyday life of engineering and industry algorithms. In efforts to satisfy this need, parallel computers provide an efficient and economical way to solve large-scale and/or time-constrained problems. As a consequence, the end-users of these systems have a vested interest in defining the asymptotic time complexity of parallel algorithms to predict their performance on a particular parallel computer. The asymptotic parallel time complexity of data-dependent algorithms depends on the number of processors, data size, and other parameters. Discovering the main other parameters is a challenging problem and the clue in obtaining a good estimate of performance order. Great examples of these types of applications are sorting algorithms, searching algorithms and solvers of the traveling salesman problem (TSP). This article encompasses all the knowledge discovery aspects to the problem of defining the asymptotic parallel time complexity of data-dependent algorithms. The knowledge discovery methodology begins by designing a considerable number of experiments and measuring their execution times. Then, an interactive and iterative process explores data in search of patterns and/or relationships detecting some parameters that affect performance. Knowing the key parameters which characterise time complexity, it becomes possible to hypothesise to restart the process and to produce a subsequent improved time complexity model. Finally, the methodology predicts the performance order for new data sets on a particular parallel computer by replacing a numerical identification. As a case of study, a global pruning traveling salesman problem implementation (GP-TSP) has been chosen to analyze the influence of indeterminism in performance prediction of data-dependent parallel algorithms, and also to show the usefulness of the defined knowledge discovery methodology. The subsequent hypotheses generated to define the asymptotic parallel time complexity of the TSP were corroborated one by one. The experimental results confirm the expected capability of the proposed methodology; the predictions of performance time order were rather good comparing with real execution time (in the order of 85%).

We provide parallel algorithms for large-scale matrix completion on problems with millions of rows, millions of columns, and billions of revealed entries. We focus on in-memory algorithms that run either in a shared-memory environment on a powerful compute node or in a shared-nothing environment on a small cluster of commodity nodes; even very large problems can be handled effectively in these settings. Our ASGD, DSGD-MR, DSGD++, and CSGD algorithms are novel variants of the popular stochastic gradient descent (SGD) algorithm, with the latter three algorithms based on a new "stratified SGD" approach. All of the algorithms are cache-friendly and exploit thread-level parallelism, in-memory processing, and asynchronous communication. We investigate the performance of both new and existing algorithms via a theoretical complexity analysis and a set of large-scale experiments. The results show that CSGD is more scalable, and up to 60 % faster, than the best-performing alternative method in the shared-memory setting. DSGD++ is superior in terms of overall runtime, memory consumption, and scalability in the shared-nothing setting. For example, DSGD++ can solve a difficult matrix completion problem on a high-variance matrix with 10M rows, 1M columns, and 10B revealed entries in around 40 min on 16 compute nodes. In general, algorithms based on SGD appear to perform better than algorithms based on alternating minimizations, such as the PALS and DALS alternating least-squares algorithms.

Algorithms have historically been evaluated in terms of the number of arithmetic operations they performed. This analysis is no longer sufficient for predicting running times on today's machines. Moving data through memory hierarchies and among processors requires much more time (and energy) than performing computations. Hardware trends suggest that the relative costs of this communication will only increase. Proving lower bounds on the communication of algorithms and finding algorithms that attain these bounds are therefore fundamental goals. We show that the communication cost of an algorithm is closely related to the graph expansion properties of its corresponding computation graph. Matrix multiplication is one of the most fundamental problems in scientific computing and in parallel computing. Applying expansion analysis to Strassen's and other fast matrix multiplication algorithms, we obtain the first lower bounds on their communication costs. These bounds show that the current sequential algorithms are optimal but that previous parallel algorithms communicate more than necessary. Our new parallelization of Strassen's algorithm is communication-optimal and outperforms all previous matrix multiplication algorithms.

A series of online multi-task learning (OMTL) algorithms have been proposed to avoid the expensive training cost and poor adaptability of traditional batch multi-task learning (MTL) algorithms in recent years. However, these OMTL algorithms usually assume that all tasks are closely related, which may not hold in practical scenarios. More importantly, their theoretical reliability is weakened due to the lack of proof on the cumulative regrets. To overcome these limitations, we present a robust online multi-task classification framework (ROM) and its two optimization algorithms (ROM-PGD, ROM-RDA). The proposed algorithms can not only automatically capture the common features among all tasks and individual features for each task, but also identify the potential existence of outlier task. Theoretically, we prove that the regret bounds of these two algorithms are sub-linear compared with the best separating algorithm in hindsight. Empirical studies on both synthetic and real-world datasets also demonstrate the effectiveness of our proposed algorithms when compared with the state-of-the-art OMTL algorithms.

Genetic Algorithms are generally used to draw a similarity between the Genetic mutation and Cross Over within populations from the field of biology. Genetic algorithms are highly and significantly parallel in nature and performance. These types of algorithms can be used to solve many other important problems such as the Graph Partitioning problem that deals with partitioning of graph, the famous Travelling salesman problems etc. Implementation of these algorithm shows a trade-off between Genetic search capable qualities and execution performance qualities. In this paper we worked in order to improvise the execution performance rate of algorithms, those particular implementations with lesser communications between populations are considered best and highly efficient. In this same direction, we tried to present an algorithm using discrete small subpopulation groups. Therefore, this particular implementation tries to reduce the quality of search of the algorithm. Thus, we tried to improve the quality of this type of search by having a centralized population system. Here, we analyzed some of the other alternatives for the implementation of these algorithms on distributed memory architectures in which centralized data can be significantly implemented. Prediction of tertiary protein structure is also presented in the paper as an example in which we tried to implement these alternatives of parallel algorithms on it. In the last section, we tried to summarize the performance analysis of the various proposed architectures. KeywordsAlgorithms, Protein Structure Prediction, Parallel Genetic Algorithms, Distributed Memory Architecture In cross over transformation, the individual pieces of solution are completely swapped to give new solutions and their fitness is tested upon for results. After finishing crossover, the concept of mutation is applied which involves random selection of new characteristics for the solution obtained. The termination is completely based on pre- defined number of steps or a pre-specified level of optimality for future reference as well. Genetic Algorithms significantly provides alternative methods for solving the problem and consistently performs other traditional methods efficiently without any errors. Most of the real world problems that involves finding of optimal parameter may seem to be difficult for traditional methods but are ideal for Genetic Algorithms in many cases. Although these are highly skilful in solving hard problems, they might also take longer execution times as compared to others. To counter this execution delay problem, scientists resorted to exploit the parallel nature of Genetic Algorithms. Thus, these came to be known as parallel genetic algorithms. Their implementation generally involves very similar issues as other parallel algorithms do which are explained in terms of granularity, synchronization and locality of reference etc. In

The widespread usage of random graphs has been highlighted in the context of database applications for several years. This because such data structures turn out to be very useful in a large family of database applications ranging from simulation to sampling, from analysis of complex networks to study of randomized algorithms, and so forth. Amongst others, Erdos-Renyi @C"v","p is the most popular model to obtain and manipulate random graphs. Unfortunately, it has been demonstrated that classical algorithms for generating Erdos-Renyi based random graphs do not scale well in large instances and, in addition to this, fail to make use of the parallel processing capabilities of modern hardware. Inspired by this main motivation, in this paper we propose and experimentally assess a novel parallel algorithm for generating random graphs under the Erdos-Renyi model that is designed and implemented in a Graphics Processing Unit (GPU), called PPreZER. We demonstrate the nice amenities due to our solution via a succession of several intermediary algorithms, both sequential and parallel, which show the limitations of classical approaches and the benefits due to the PPreZER algorithm. Finally, our comprehensive experimental assessment and analysis brings to light a relevant average speedup gain of PPreZER over baseline algorithms.

For many applications in signal processing and control it is crucial that estimates of the state vector in a dynamic system can be obtained in real time. This poses the problem of producing algorithms that are fast enough to enable online execution. In this article, it is investigated how two of the most popular and powerful state estimation algorithms, the Kalman filter and the particle filter, can be efficiently implemented in parallel on a multicore architecture. The proposed parallel implementations are analyzed in terms of hardware requirements, such as memory bandwidth and available cache memory, to provide the desired speedup. The algorithms are exemplified by and evaluated in an adaptive filtering and a bearings-only tracking application. In the cases when original algorithms have been modified for parallelization, the accuracy of the estimates obtained is evaluated in comparison with that of the sequential algorithm. It is found that linear speedup, in the number of cores used, can indeed be achieved without loss of accuracy, for both state estimation algorithms.

this paper a survey on current trends in parallel computing has been studied that depicts all the aspects of parallel computing system. A large computational problem that can not be solved by a single CPU can be divided into a chunk of small enough subtasks which are processed simultaneously by a parallel computer. The parallel computer consists of parallel computing hardware, parallel computing model, software support for parallel programming. Parallel performance measurement parameters and parallel benchmarks are used to measure the performance of a parallel computing system. The hardware and the software are specially designed for parallel algorithm and programming. This paper explores all the aspects of parallel computing and its usefulness. Keywordscomputing, parallel computing hardware, parallel model, parallel benchmarks.