Graph coloring is often used in parallelizing scientific computations that run in distributed and multi-GPU environments;it identifies sets of independent data that can be updated in parallel. Many algorithms exist fo...
详细信息
Graph coloring is often used in parallelizing scientific computations that run in distributed and multi-GPU environments;it identifies sets of independent data that can be updated in parallel. Many algorithms exist for graph coloring on a single GPU or in distributed memory, but to the best of our knowledge, hybrid MPI+GPU algorithms have been unexplored until this work. We present several MPI+GPU coloring approaches based on the distributed coloring algorithms of Gebremedhin et al. and the shared-memory algorithms of Deveci et al. The on-node parallel coloring uses implementations in KokkosKernels, which provide parallelization for both multicore CPUs and GPUs. We further extend our approaches to compute distance-2 and partial distance-2 colorings, giving the first known distributed, multi-GPU algorithm for these problems. In addition, we propose a novel heuristic to reduce communication for recoloring in distributed graph coloring. Our experiments show that our approaches operate efficiently on inputs too large to fit on a single GPU and scale up to graphs with 76.7 billion edges running on 128 GPUs.
Synchronous and asynchronous algorithms are presented for distributed minimax optimization. The objective here is to realize the minimization of the maximum of component functions over the standard multi-agent network...
详细信息
Synchronous and asynchronous algorithms are presented for distributed minimax optimization. The objective here is to realize the minimization of the maximum of component functions over the standard multi-agent network, where each node of the network knows its own function and it exchanges its decision variable with its neighbors. In fact, the proposed algorithms are standard consensus and gossip based subgradient methods, while the original minimax optimization is recast as minimization of the sum of component functions by using a p-norm approximation. A scalable step size depending on the approximation ratio p is also presented in order to avoid slow convergence. Numerical examples illustrate that the algorithms with this step size work well even in the high approximation ratios.
Determining the network size is a critical process in numerous areas (e.g., computer science, logistic, epidemiology, social networking services, mathematical modeling, demography, etc.). However, many modern real-wor...
详细信息
Determining the network size is a critical process in numerous areas (e.g., computer science, logistic, epidemiology, social networking services, mathematical modeling, demography, etc.). However, many modern real-world systems are so extensive that measuring their size poses a serious challenge. Therefore, the algorithms for determining/estimating this parameter in an effective manner have been gaining popularity over the past decades. In the paper, we analyze five frequently applied distributed consensus gossip-based algorithms for network size estimation in multi-agent systems (namely, the Randomized gossip algorithm, the Geographic gossip algorithm, the Broadcast gossip algorithm, the Push-Sum protocol, and the Push-Pull protocol). We examine the performance of the mentioned algorithms with bounded execution over random geometric graphs by applying two metrics: the number of sent messages required for consensus achievement and the estimation precision quantified as the median deviation from the real value of the network size. The experimental part consists of two scenarios-the consensus achievement is conditioned by either the values of the inner states or the network size estimates-and, in both scenarios, either the best-connected or the worst-connected agent is chosen as the leader. The goal of this paper is to identify whether all the examined algorithms are applicable to estimating the network size, which algorithm provides the best performance, how the leader selection can affect the performance of the algorithms, and how to most effectively configure the applied stopping criterion.
It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the termination detection problem are obtai...
详细信息
It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the termination detection problem are obtained by applying transformations to garbage collection algorithms. The transformation can be applied to collectors of the ''mark-and-sweep'' type as well as to reference-counting garbage collectors. As examples, the scheme is used to transform the distributed reference-counting protocol of Lermen and Maurer, the weighted-reference-counting protocol, the local-reference-counting protocol, and Ben-Ari's mark-and-sweep collector into termination detection algorithms. Known termination-detection algorithms as well as new variants are obtained.
In this paper, the optimal variational generalized Nash equilibrium(v-GNE) seeking problem in merely monotone games with linearly coupled cost functions is investigated, in which the feasible strategy domain of each a...
详细信息
In this paper, the optimal variational generalized Nash equilibrium(v-GNE) seeking problem in merely monotone games with linearly coupled cost functions is investigated, in which the feasible strategy domain of each agent is coupled through an affine constraint. A distributed algorithm based on the hybrid steepest descent method is first proposed to seek the optimal v-GNE. Then, an accelerated algorithm with relaxation is proposed and analyzed, which has the potential to further improve the convergence speed to the optimal v-GNE. Some sufficient conditions in both algorithms are obtained to ensure the global convergence towards the optimal v-GNE. To illustrate the performance of the algorithms, numerical simulation is conducted based on a networked Nash-Cournot game with bounded market capacities.
Energy efficiency remains a critical design issue for wireless sensor networks. How to maintain the network connectivity and, at the same time, to minimize the energy consumption is a very challenging problem. Differe...
详细信息
Energy efficiency remains a critical design issue for wireless sensor networks. How to maintain the network connectivity and, at the same time, to minimize the energy consumption is a very challenging problem. Different from many previous excellent results, we explore the topology control problem for heterogeneous wireless sensor networks. Our objective is to propose distributed topology control algorithms, where only local information is kept for all of the nodes. The experimental results show the strengths of the proposed algorithms in the average edge length and the average link length.
The rapid growth of distributed energy resources motivates the application of distributed optimization algorithms for solving optimal power flow (OPF) problems. Using distributed optimization to solve OPF problems req...
详细信息
ISBN:
(纸本)9781665499224
The rapid growth of distributed energy resources motivates the application of distributed optimization algorithms for solving optimal power flow (OPF) problems. Using distributed optimization to solve OPF problems requires repeated data sharing between agents responsible for different regions of the power system. The performance of distributed optimization algorithms depends on the integrity of the shared data and the communications between the agents. This paper investigates the vulnerability of a distributed algorithm called Auxiliary Problem Principle (APP) with respect to cyberattacks on the communications between the agents. We propose cyberattack models that manipulate the shared data between neighboring agents to achieve an objective such as driving the algorithm to converge to a suboptimal solution. We investigate the convergence characteristics of the APP algorithm in the context of the DC optimal power flow (DC OPF) problem with and without manipulating the shared data. Last, we demonstrate how trained neural networks can provide highly accurate attack detection.
In this paper we develop algorithms for distributed computation of a broad range of estimation and detection tasks over networks with arbitrary but fixed connectivity. The distributed algorithms we develop are linear ...
详细信息
In this paper we develop algorithms for distributed computation of a broad range of estimation and detection tasks over networks with arbitrary but fixed connectivity. The distributed algorithms we develop are linear dynamical systems that generate sequences of approximations to the desired computation. The algorithms are locally constructed at each node by exploiting only locally available and macroscopic information about the network topology. We present methods for designing these distributed algorithms so as to optimize the convergence rates to the desired computation and demonstrate their performance characteristics in the context of a problem of signal estimation from multi-node signal observations in Gaussian noise.
In this paper we apply distributed kernel regression methods to perform sensor network localization. This follows up on earlier work where a centralized kernel regression algorithm was considered to perform localizati...
详细信息
In this paper we apply distributed kernel regression methods to perform sensor network localization. This follows up on earlier work where a centralized kernel regression algorithm was considered to perform localization. Here we examine the tradeoffs between using distributed algorithms versus centralized algorithms in terms of communication costs, computational costs, and performance of the estimate. Simulation results demonstrate that distributed methods work well with comparable performance to centralized algorithms with less communication costs.
Reconstructing compressed sensing signals involves solving an optimization problem. An example is Basis Pursuit (BP) [1], which is applicable only in noise-free scenarios. In noisy scenarios, either the Basis Pursuit ...
详细信息
Reconstructing compressed sensing signals involves solving an optimization problem. An example is Basis Pursuit (BP) [1], which is applicable only in noise-free scenarios. In noisy scenarios, either the Basis Pursuit Denoising (BPDN) [1] or the Noise-Aware BP (NABP) [2] can be used. Consider a distributed scenario where the dictionary matrix and the vector of observations are spread over the nodes of a network. We solve the following open problem: design distributed algorithms that solve BPDN with a column partition, i.e., when each node knows only some columns of the dictionary matrix, and that solve NABP with a row partition, i.e., when each node knows only some rows of the dictionary matrix and the corresponding observations. Our approach manipulates these problems so that a recent general-purpose algorithm for distributed optimization can be applied.
暂无评论