Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 630 papers for “Embarrassingly parallel”

An Embarrassingly Parallel Model Counter

Zheng Xu, Minghao Yin, Jean-Marie Lagniez · 2025

Model counting (also known as #SAT) is a fundamental problem in knowledge representation and reasoning, with applications ranging from probabilistic inference to formal verification. However, state-of-the-art model counters are limited by computational resources on a single machine. In this paper, we propose a novel distributed framework for model counting, exploiting the embarrassingly parallel nature of the problem. By decomposing the search space into independent subproblems and distributing them across different computation nodes, our approach achieves near-linear scalability on practical instances. Extensive experiments on standard benchmarks demonstrate both the effectiveness and efficiency of our framework.

Cited by 0Open access

EMINENT: Embarrassingly Parallel Mutation Testing

Pablo C. Cañizares, Mercedes G. Merayo, Alberto Núñez · Procedia Computer Science · 2016

During the last decade, the fast evolution in communication networks has facilitated the development of complex applications that manage vast amounts of data, like Big Data applications. Unfortunately, the high complexity of these applications hampers the testing process. Moreover, generating adequate test suites to properly check these applications is a challenging task due to the elevated number of potential test cases. Mutation testing is a valuable technique to measure the quality of the selected test suite that can be used to overcome this difficulty. However, one of the main drawbacks of mutation testing lies on the high computational cost associated to this process. In this paper we propose a dynamic distributed algorithm focused on HPC systems, called EMINENT, which has been designed to face the performance problems in mutation testing techniques. EMINENT alleviates the computational cost associated with this technique since it exploits parallelism in cluster systems to reduce the final execution time. In addition, several experiments have been carried out on three applications in order to analyse the scalability and performance of EMINENT. The results show that EMINENT provides an increase in the speed-up in most scenarios.

Cited by 5Open access

Hybrid Embarrassingly Parallel on heterogeneous platform

Chunye Gong, Jie Liu, Jin Qin et al. · 2010

The Embarrassingly Parallel (EP) is one kernel benchmark of NAS Parallel Benchmarks (NPB). EP generates pairs of Gaussian Random Deviates (GRDs) of large random numbers which produced by Linear Congruential Generator (LCG). In this paper, the Hybrid EP is efficient implemented on CPU/GPU heterogeneous platform. Experimental results show that the Hybrid EP is 11.98 times faster than equivalent multicore CPU and outperforms equivalent GPU by 7.52%.

Cited by 4

Embarrassingly parallel autoconstructive multilayer perceptron neural networks

Felipe Farias · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 2022

The present thesis proposes a method to automatically construct Multilayer Per-ceptron Artificial Neural Networks (MLP) to help non-expert users to still create robust models without the need to worry about the best combination of the number of neurons and activation functions by using specific splitting strategies, training parallelization, and multi-criteria model selection techniques. In order to do that, a data splitting algorithm (Similarity Based Stratified Splitting) was developed to produce statistically similar splits in order to better explore the feature space and consequently train better models. These splits are used to independently train several MLPs with different architectures in parallel (ParallelMLPs), using a modified matrix multiplication that takes advantage of the principle of locality to speed up the training of these networks from 1 to 4 orders of magnitude in CPUs and GPUs, when compared to the sequential training of the same models. It allowed the evaluation of several architectures for the MLPs in a very short time to produce a pool with a considerable amount of complex models. Furthermore, we were able to analyze and propose optimality conditions of theoretical optimal models and use them to automatically define MLP architectures by performing a multi-criteria model selection, since choosing a single model from an immense pool is not a trivial task. The code will be available at <https://github.com/fariasfc/parallel-mlps>.

Cited by 0

Asymptotically exact, embarrassingly parallel MCMC. arXiv:1311.4780v2

Willie Neiswanger, Chong Wang, Eric P. Xing · 2014

Communication costs, resulting from synchro-nization requirements during learning, can greatly slow down many parallel machine learning algorithms. In this paper, we present a parallel Markov chain Monte Carlo (MCMC) algorithm in which subsets of data are pro-cessed independently, with very little com-munication. First, we arbitrarily partition data onto multiple machines. Then, on each machine, any classical MCMC method (e.g., Gibbs sampling) may be used to draw samples from a posterior distribution given the data subset. Finally, the samples from each ma-chine are combined to form samples from the full posterior. This embarrassingly parallel algorithm allows each machine to act inde-pendently on a subset of the data (without communication) until the final combination stage. We prove that our algorithm generates asymptotically exact samples and empirically demonstrate its ability to parallelize burn-in and sampling in several models. 1

Cited by 0

Embarrassingly parallel MCMC using deep invertible transformations

Diego Mesquita, Paul Blomstedt, Samuel Kaski · arXiv (Cornell University) · 2019

While MCMC methods have become a main work-horse for Bayesian inference, scaling them to large distributed datasets is still a challenge. Embarrassingly parallel MCMC strategies take a divide-and-conquer stance to achieve this by writing the target posterior as a product of subposteriors, running MCMC for each of them in parallel and subsequently combining the results. The challenge then lies in devising efficient aggregation strategies. Current strategies trade-off between approximation quality, and costs of communication and computation. In this work, we introduce a novel method that addresses these issues simultaneously. Our key insight is to introduce a deep invertible transformation to approximate each of the subposteriors. These approximations can be made accurate even for complex distributions and serve as intermediate representations, keeping the total communication cost limited. Moreover, they enable us to sample from the product of the subposteriors using an efficient and stable importance sampling scheme. We demonstrate the approach outperforms available state-of-the-art methods in a range of challenging scenarios, including high-dimensional and heterogeneous subposteriors.

Cited by 5Open access

Embarrassingly Parallel Variational Inference in Nonconjugate Models

Willie Neiswanger, Chong Wang, Eric P. Xing · arXiv (Cornell University) · 2015

We develop a parallel variational inference (VI) procedure for use in data-distributed settings, where each machine only has access to a subset of data and runs VI independently, without communicating with other machines. This type of "embarrassingly parallel" procedure has recently been developed for MCMC inference algorithms; however, in many cases it is not possible to directly extend this procedure to VI methods without requiring certain restrictive exponential family conditions on the form of the model. Furthermore, most existing (nonparallel) VI methods are restricted to use on conditionally conjugate models, which limits their applicability. To combat these issues, we make use of the recently proposed nonparametric VI to facilitate an embarrassingly parallel VI procedure that can be applied to a wider scope of models, including to nonconjugate models. We derive our embarrassingly parallel VI algorithm, analyze our method theoretically, and demonstrate our method empirically on a few nonconjugate models.

Cited by 9Open access

Embarrassingly Parallel MCMC using Deep Invertible Transformations.

Diego Mesquita, Paul Blomstedt, Samuel Kaski · Research Explorer (The University of Manchester) · 2019

While MCMC methods have become a main work-horse for Bayesian inference, scaling them to large distributed datasets is still a challenge. Embarrassingly parallel MCMC strategies take a divide-and-conquer stance to achieve this by writing the target posterior as a product of subposteriors, running MCMC for each of them in parallel and subsequently combining the results. The challenge then lies in devising efficient aggregation strategies. Current strategies tradeoff between approximation quality, and costs of communication and computation. In this work, we introduce a novel method that addresses these issues simultaneously. Our key insight is to introduce a deep invertible transformation to approximate each of the subposteriors. These approximations can be made accurate even for complex distributions and serve as intermediate representations, keeping the total communication cost limited. Moreover, they enable us to sample from the product of the subposteriors using an efficient and stable importance sampling scheme. We demonstrate that the approach outperforms available state-of-the-art methods in a range of challenging scenarios, including high-dimensional and heterogeneous subposteriors.

Cited by 3Open access

Flexibilité et Portabilité pour Embarrassingly Parallel Search

Samvel Balassanian Dersarkissian, Arnaud Malapert · HAL (Le Centre pour la Communication Scientifique Directe) · 2020

Constraint programming is a paradigm for solving combinatorial problems. Yet solving complex problems may be a lengthy process. Embarrassingly Parallel Search (EPS) is "a simple and efficient method for solving constraint programming problems in parallel". While EPS is a very generic method, its implementations are strongly dependent on the machine architecture for which they were written. We suggest a new communication architecture for EPS's inner workings such that it becomes usable on different machine architectures. Then we exhibit a prototype that combines partitioning and portfolio methods implementing that architecture.

Cited by 0Open access

Legio: Fault Resiliency for Embarrassingly Parallel MPI Applications

Rocco, Roberto, Gadioli, Davide, Palermo, Gianluca · arXiv (Cornell University) · 2021

Due to the increasing size of HPC machines, the fault presence is becoming an eventuality that applications must face. Natively, MPI provides no support for the execution past the detection of a fault, and this is becoming more and more constraining. With the introduction of ULFM (User Level Fault Mitigation library), it has been provided with a possible way to overtake a fault during the application execution at the cost of code modifications. ULFM is intrusive in the application and requires also a deep understanding of its recovery procedures. In this paper we propose Legio, a framework that lowers the complexity of introducing resiliency in an embarrassingly parallel MPI application. By hiding ULFM behind the MPI calls, the library is capable to expose resiliency features to the application in a transparent manner thus removing any integration effort. Upon fault, the failed nodes are discarded and the execution continues only with the non-failed ones. A hierarchical implementation of the solution has been also proposed to reduce the overhead of the repair process when scaling towards a large number of nodes. We evaluated our solutions on the Marconi100 cluster at CINECA, showing that the overhead introduced by the library is negligible and it does not limit the scalability properties of MPI. Moreover, we also integrated the solution in real-world applications to further prove its robustness by injecting faults.

Cited by 0Open access

Multi-objective embarrassingly parallel search for constraint programming

M. Yasuhara, Toshiyuki Miyamoto, Kazuma Mori et al. · 2015

Optimization plays an important role in various disciplines of engineering. Multi-objective optimization is usually characterized by a Pareto front. In large scale multi-objective optimization problems, determining an optimal Pareto front consumes large time. Thus, parallel computing is used to speed up the search. Constraint programming is one of the logic-based optimization techniques for solving combinatorial optimization problems. Kotecha et al. proposed a constraint programming-based strategy to determine an optimal Pareto front. Regin et al. proposed a parallel search for constraint programming, called the embarrassingly parallel search. In this paper, we propose the multi-objective embarrassingly parallel search for multi-objective constraint optimization, which combines the two strategies.

Cited by 5

Legio: fault resiliency for embarrassingly parallel MPI applications

Roberto Rocco, Davide Gadioli, Gianluca Palermo · The Journal of Supercomputing · 2021

Abstract Due to the increasing size of HPC machines, dealing with faults is becoming mandatory due to their high frequency. Natively, MPI cannot handle faults and it stops the execution prematurely when it finds one. With the introduction of ULFM, it is possible to continue the execution, but it requires complex integration with the application. In this paper we propose Legio, a framework that introduces fault resiliency in embarrassingly parallel MPI applications. Legio exposes its features to the application transparently, removing any integration difficulty. After a fault, the execution continues only with the non-failed processes. We also propose a hierarchical alternative, which features lower repair costs on large communicators. We evaluated our solutions on the Marconi100 cluster at CINECA with benchmarks and real-world applications, showing that the overhead introduced by the library is negligible and it does not limit the scalability properties of MPI.

Cited by 5Open access

Parallelization of constraint programming using embarrassingly parallel search

Derval, Guillaume · Digital Access to Libraries (Université catholique de Louvain (UCL), l'Université de Namur (UNamur) and the Université Saint-Louis (USL-B)) · 2016

Constraint programming solvers have a serial architecture, and do not take advantage of the parallel computing power available nowadays in our multi-core computers and in the cloud. Multiple solutions to remedy at this situation have emerged, such as Work-Stealing or Multi-threaded Portfolio Search, which allow to run multiple solvers and make them communicate in order to find solutions of the initial problem. However, these techniques scale badly with a high number of workers. Embarrassingly Parallel Search is a recent method that aims at parallelizing solving of constraint satisfaction problems, by dividing them in numerous subproblems, and sharing them between multiple solvers. The high number of subproblems ensures proper balancing between the multiple workers. Previous works have shown nearly linear speedups and superiority of EPS over other methods on some problems. This master's thesis proposes a new implementation of EPS over the OscaR-CP solver, with an innovative architecture based on a symbolic layer, called OscaR-Modeling, that is inspired by Objective-CP, a state-of-the-art modeling language. An analysis of the influence of the decomposition method over the speedup is made, and a new decomposition, called Cartesian Product Iterative Refinement, is proposed. EPS is originally made for solving constraint satisfaction problems; this master's thesis introduces an adaptation for constraint optimization problems. A study of various methods to share the objective function bound is conducted. Finally, an overview of the performances of EPS on OscaR-Modeling is given, and shows linear and super-linear speedups, even on more than one thousand threads.

Cited by 0Open access

Grid Approach to Embarrassingly Parallel CPU-Intensive Bioinformatics Problems

Heinz Stockinger, Marco Pagni, Lorenzo Cerutti et al. · 2006

Bioinformatics algorithms such as sequence alignment methods based on profile-HMM (Hidden Markov Model) are popular but CPU-intensive. If large amounts of data are processed, a single computer often runs for many hours or even days. High performance infrastructures such as clusters or computational Grids provide the techniques to speed up the process by distributing the workload to remote nodes, running parts of the work load in parallel. Biologists often do not have access to such hardware systems. Therefore, we propose a new system using a modern Grid approach to optimise an embarrassingly parallel problem. We achieve speed ups by at least two orders of magnitude given that we can use a powerful, world-wide distributed Grid infrastructure. For large-scale problems our method can outperform algorithms designed for mid-size clusters even considering additional latencies imposed by Grid infrastructures.

Cited by 19