检索结果-内蒙古大学图书馆

7th Workshop on Irregular Applications - Architectures and algorithms (IA3)

作者： Zarins, Justs Weiland, Michele Univ Edinburgh Edinburgh Midlothian Scotland EPCC Edinburgh Midlothian Scotland

ISBN: (纸本)9781450351362

Synchronisation in the presence of noise and hardware performance variability is a key challenge that prevents applications from scaling to large problems and machines. Using asynchronous or semi-synchronous algorithms can help overcome this issue, but at the cost of reduced stability or convergence rate. In this paper we propose progressive load balancing to manage progress imbalance in asynchronous algorithms dynamically. In our technique the balancing is done over time, not instantaneously. Using Jacobi iterations as a test case, we show that, with CPU performance variability present, this approach leads to higher iteration rate and lower progress imbalance between parts of the solution space. We also show that under these conditions the balanced asynchronous method outperforms synchronous, semi-synchronous and totally asynchronous implementations in terms of time to solution.

关键词： asynchronous algorithm load balancing performance variability

来源：评论

学校读者我要写书评

暂无评论

Experimental Evaluation of Synchronous and asynchronous algorithms for Wireless Sensor Networks: The Case of Graph Matching

Experimental Evaluation of Synchronous and Asynchronous Algo...

引用

Innovations in Intelligent Systems and Applications Conference (ASYU)

作者： Cabuk, Umut Can Ersin, Ismail Dagdeviren, Orhan Ege Univ Int Comp Inst Izmir Turkey

ISBN: (纸本)9781728128689

Wireless sensor networks (WSNs) consist of tiny nodes that are capable of sensing the environment and transmitting the sensed data through wireless transceivers. Synchronous and asynchronous operations are two communication paradigms, which have different advantages and purposes. A WSN can be modeled as a graph that leads to use graph-theoretic structures such as graph matching, for various applications. A matching in a graph is a set of edges that do not have any common endpoint (node). Backup assignment and clustering are the most well-known applications of graph matching, where nodes incident to edges in a matching are backups of each other. In this paper, a detailed performance evaluation of synchronous and asynchronous operations in terms graph matching is provided. A synchronous and an asynchronous design of the Hoepman's algorithm, whose original was asynchronous, were considered. Extensive transmitted bit, energy and wall clock time measurements of these algorithms are given by comparing them in detail. The tests, which are carried out via TOSSIM simulations, showed that asynchronous operation is considerably faster, on the other side the synchronous algorithm is significantly more energy efficient.

关键词： Distributed Computing Wireless Sensor Networks asynchronous algorithm Synchronous algorithm Graph Matching Performance Evaluation

来源：评论

学校读者我要写书评

暂无评论

asynchronous STOCHASTIC APPROXIMATION algorithmS FOR NETWORKED SYSTEMS: REGIME-SWITCHING TOPOLOGIES AND MULTISCALE STRUCTURE

引用

MULTISCALE MODELING & SIMULATION 2013年第3期11卷 813-839页

作者： Yin, G. Yuan, Quan Wang, Le Yi Wayne State Univ Dept Math Detroit MI 48202 USA Wayne State Univ Dept Elect & Comp Engn Detroit MI 48202 USA

This work develops asynchronous stochastic approximation (SA) algorithms for networked systems with multiagents and regime-switching topologies to achieve consensus control. There are several distinct features of the algorithms: (1) In contrast to most of the existing consensus algorithms, the participating agents compute and communicate in an asynchronous fashion without using a global clock. (2) The agents compute and communicate at random times. (3) The regime-switching process is modeled as a discrete-time Markov chain with a finite state space. (4) The functions involved are allowed to vary with respect to time;hence, nonstationarity can be handled. (5) Multiscale formulation enriches the applicability of the algorithms. In the setup, the switching process contains a rate parameter epsilon > 0 in the transition probability matrix that characterizes how frequently the topology switches. The algorithm uses a step-size mu that defines how fast the network states are updated. Depending on their relative values, three distinct scenarios emerge. Under suitable conditions, it is shown that a continuous-time interpolation of the iterates converges weakly either to a system of randomly switching ordinary differential equations modulated by a continuous-time Markov chain or to a system of differential equations (an average with respect to certain measure). In addition, a scaled sequence of tracking errors converges to either a switching diffusion or a diffusion. Simulation results are presented to demonstrate these findings.

关键词： asynchronous algorithm stochastic approximation switching model random computation time nonstationarity consensus

来源：评论

学校读者我要写书评

暂无评论

asynchronous block-iterative primal-dual decomposition methods for monotone inclusions

引用

MATHEMATICAL PROGRAMMING 2018年第1-2期168卷 645-672页

作者： Combettes, Patrick L. Eckstein, Jonathan UPMC Univ Paris 06 Lab Jacques Louis Lions CNRS UMR 7598 F-75005 Paris France Rutgers State Univ Dept Managemement Sci & Informat Syst Piscataway NJ 08854 USA Rutgers State Univ RUTCOR Piscataway NJ 08854 USA

We propose new primal-dual decomposition algorithms for solving systems of inclusions involving sums of linearly composed maximally monotone operators. The principal innovation in these algorithms is that they are block-iterative in the sense that, at each iteration, only a subset of the monotone operators needs to be processed, as opposed to all operators as in established methods. Flexible strategies are used to select the blocks of operators activated at each iteration. In addition, we allow lags in operator processing, permitting asynchronous implementation. The decomposition phase of each iteration of our methods is to generate points in the graphs of the selected monotone operators, in order to construct a half-space containing the Kuhn-Tucker set associated with the system. The coordination phase of each iteration involves a projection onto this half-space. We present two related methods: the first method provides weakly convergent primal and dual sequences under general conditions, while the second is a variant in which strong convergence is guaranteed without additional assumptions. Neither algorithm requires prior knowledge of bounds on the linear operators involved or the inversion of linear operators. Our algorithmic framework unifies and significantly extends the approaches taken in earlier work on primal-dual projective splitting methods.

关键词： asynchronous algorithm Block-iterative algorithm Duality Monotone inclusion Monotone operator Primal-dual algorithm Splitting algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed asynchronous Optimization Framework for the MISO Interference Channel

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2014年第22期62卷 5809-5824页

作者： Wesemann, Stefan Fettweis, Gerhard P. Tech Univ Dresden Vodafone Chair Mobile Commun Syst Dresden Germany

We study the distributed optimization of transmit strategies in a multiple-input, single-output (MISO) interference channel (IFC). Existing distributed algorithms rely on strictly synchronized update steps by the individual users. They require a global synchronization mechanism and potentially suffer from the synchronization penalty caused by e. g., backhaul communication delays and fixed update sequences. We establish a general optimization framework that allows asynchronous update steps. The users perform their computations at arbitrary instants of time and do not wait for information that has been sent to them. Based on certain bounds on the amount of asynchronism that is present in the execution of the algorithm, we are able to characterize its convergence. As illustrated by our numerical results, the proposed algorithm is not excessively slowed down by neither communication delays, nor by specific update orders, and thus enables faster convergence to (local) optimal solution.

关键词： MISO interference channel sum-utility maximization distributed beamforming asynchronous algorithm onvergence of numerical methods

来源：评论

学校读者我要写书评

暂无评论

asynchronous Lagrangian scenario decomposition

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2021年第1期13卷 1-50页

作者： Aravena, Ignacio Papavasiliou, Anthony Lawrence Livermore Natl Lab Livermore CA 94550 USA Catholic Univ Louvain CORE Louvain La Neuve Belgium

We present a distributed asynchronous algorithm for solving two-stage stochastic mixed-integer programs (SMIP) using scenario decomposition, aimed at industrial-scale instances of the stochastic unit commitment (SUC) problem. The algorithm is motivated by large differences in run times observed among scenario subproblems of SUC instances, which can result in inefficient use of distributed computing resources by synchronous parallel algorithms. Our algorithm performs dual iterations asynchronously using a block-coordinate subgradient descent method which allows performing block-coordinate updates using delayed information, while candidate primal solutions are recovered from the solutions of scenario subproblems using heuristics. We present a high performance computing implementation of the asynchronous algorithm, detailing the operations performed by each parallel process and the communication mechanisms among them. We conduct numerical experiments using SUC instances of the Western Electricity Coordinating Council system with up to 1000 scenarios and of the Central Western European system with up to 120 scenarios. We also conduct numerical experiments on generic SMIP instances from the SIPLIB library (DCAP and SSLP). The results demonstrate the general applicability of the proposed algorithm and its ability to solve industrial-scale SUC instances within operationally acceptable time frames. Moreover, we find that an equivalent synchronous parallel algorithm would leave cores idle up to 80.4% of the time on our realistic test instances, an observation which underscores the need for designing asynchronous optimization schemes in order to fully exploit distributed computing on real world applications.

关键词： asynchronous algorithm Stochastic programming Unit commitment High performance computing

来源：评论

学校读者我要写书评

暂无评论

asynchronous PARALLEL SUCCESSIVE OVERRELAXATION FOR THE SYMMETRIC LINEAR COMPLEMENTARITY-PROBLEM

引用

MATHEMATICAL PROGRAMMING 1988年第2期42卷 347-361页

作者： DELEONE, R MANGASARIAN, OL 1.Computer Sciences Department University of Wisconsin 53706 Madison WI USA

Convergence is established for asynchronous parallel successive overrelaxation (SOR) algorithms for the symmetric linear complementarity problem. For the case of a strictly diagonally dominant matrix convergence is achieved for a relaxation factor interval of (0, 2] with line search, and (0, 1] without line search. Computational tests on the Sequent Symmetry S81 multiprocessor give speedup efficiency in the 43%–91% range for the cases for which convergence is established. The tests also show superiority of the asynchronous SOR algorithms over their synchronous counterparts.

关键词： Linear complementarity parallel algorithms asynchronous algorithm successive overrelaxation

来源：评论

学校读者我要写书评

暂无评论

asynchronous distributed localization in networks with communication delays and packet losses

引用

AUTOMATICA 2018年 96卷 134-140页

作者： Huang, Xu-Zhou Tian, Yu-Ping Southeast Univ Sch Automat Nanjing 210096 Jiangsu Peoples R China Minist Educ Key Lab Measurement & Control Complex Syst Engn Nanjing 210096 Jiangsu Peoples R China

This paper studies the problem of determining sensor locations in a large sensor network using only relative distance (range) measurement. Based on the barycentric coordinate representation, we propose a totally asynchronous distributed algorithm under DILOC framework due to independence of sensor update instants and unreliable networks with communication delays and packet losses. Through modeling the asynchronous algorithm as a linear difference equation with time-varying delays, we prove that the location estimates of sensors are globally convergent to the true coordinates if: (1) time interval between any two consecutive update instants is bounded from below and above, (2) communication delays and successive packet losses between sensors are finite. Simulation examples are provided to demonstrate the effectiveness of the theoretical result. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Network localization asynchronous algorithm Barycentric coordinate Time-varying delay Packet loss

来源：评论

学校读者我要写书评

暂无评论

Parallel synchronous and asynchronous space-decomposition algorithms for large-scale minimization problems

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2000年第1期17卷 85-107页

作者： Liu, CS Tseng, CH Natl Chiao Tung Univ Dept Mech Engn Appl Optimum Design Lab Hsinchu 30050 Taiwan

Three parallel space-decomposition minimization (PSDM) algorithms, based on the parallel variable transformation (PVT) and the parallel gradient distribution (PGD) algorithms (O.L. Mangasarian, SIMA Journal on Control and Optimization, vol. 33, no. 6, pp. 1916-1925.), are presented for solving convex or nonconvex unconstrained minimization problems. The PSDM algorithms decompose the variable space into subspaces and distribute these decomposed subproblems among parallel processors. It is shown that if all decomposed subproblems are uncoupled of each other, they can be solved independently. Otherwise, the parallel algorithms presented in this paper can be used. Numerical experiments show that these parallel algorithms can save processor time, particularly for medium and large-scale problems. Up to six parallel processors are connected by Ethernet networks to solve four large-scale minimization problems. The results are compared with those obtained by using sequential algorithms run on a single processor. An application of the PSDM algorithms to the training of multilayer Adaptive Linear Neurons (Madaline) and a new parallel architecture for such parallel training are also presented.

关键词： unconstrained minimization parallel algorithm parallel training synchronous algorithm asynchronous algorithm decomposition method

来源：评论

学校读者我要写书评

暂无评论

asynchronous Distributed Nonlinear Estimation Over Directed Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2024年第2期11卷 2062-2073页

作者： Wang, Qianyao Yu, Rui Meng, Min Tongji Univ Coll Elect & Informat Engn Dept Control Sci & Engn Shanghai 201804 Peoples R China Tongji Univ Res Inst Intelligent Autonomous Syst Shanghai 201804 Peoples R China

In this article, asynchronous distributed nonlinear estimation under directed networks is studied, where each agent updates its own estimate without waiting for other agents. The aim of each agent is to estimate the parameter of interest based on local, nonlinear and noisy measurements, together with neighbors' information received through network communication. To this end, a novel asynchronous distributed nonlinear estimator is proposed. By constructing an augmented system, it is rigorously proved that under some mild assumptions, the distributed estimator achieves consistent parameter estimates by selecting appropriate stepsizes. Furthermore, we also analyze the asymptotic property of the weighted estimate error sequence, including the asymptotic mean and asymptotic covariance. Finally, simulation results are given to verify the effectiveness of the devised algorithm.

关键词： Estimation Convergence Sensors Cost function Symmetric matrices Symbols Noise measurement asynchronous algorithm directed communication topologies distributed estimation nonlinear sensing model

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：