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

Supercomputing Conference

作者： Venkatesan T. Chakaravarthy Shivmaran S. Pandian Saurabh Raje Yogish Sabharwal Toyotaro Suzumura Shashanka Ubaru IBM Research India IBM T.J. Watson Research Center USA

ISBN: (数字)9781450384421

ISBN: (纸本)9781665483902

We present distributed algorithms for training dynamic Graph Neural Networks (GNN) on large scale graphs spanning multi-node, multi-GPU systems. To the best of our knowledge, this is the first scaling study on dynamic GNN. We devise mechanisms for reducing the GPU memory usage and identify two execution time bottlenecks: CPU-GPU data transfer; and communication volume. Exploiting properties of dynamic graphs, we design a graph difference-based strategy to significantly reduce the transfer time. We develop a simple, but effective data distribution technique under which the communication volume remains fixed and linear in the input size, for any number of GPUs. Our experiments using billion-size graphs on a system of 128 GPUs shows that: (i) the distribution scheme achieves up to 30x speedup on 128 GPUs; (ii) the graph-difference technique reduces the transfer time by a factor of up to 4.1x and the overall execution time by up to 40%.

关键词： Training High performance computing Heuristic algorithms Graphics processing units Data transfer Graph neural networks distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Mechanism Design for Large Scale Network Utility Maximization

Mechanism Design for Large Scale Network Utility Maximizatio...

引用

Annual Conference on Information Sciences and Systems (CISS)

作者： Meng Zhang Deepanshu Vasal Northwestern University

Network utility maximization (NUM) is a general framework for designing distributed optimization algorithms for networks. Existing studies proposed (economic) mechanisms to solve the NUM but largely neglected the issue of large-scale implementation. In this paper, we present the Large-Scale Vickery-Clark-Grove (VCG) Mechanism for NUM with a simpler payment rule. The Large-Scale VCG Mechanism maximizes the network utility and achieves individual rationality and budget balance. We show that, as the number of agents approaches infinity, each agent's incentive to misreport converges quadratically to zero. For practical implementation, we introduce a modified mechanism that possesses an additional important technical property, superimposability, which makes it able to be built upon any (potentially distributed) algorithm that optimally solves the NUM Problem and ensures agents to obey the algorithm.

关键词： Economics distributed algorithms Optimization

来源：评论

学校读者我要写书评

暂无评论

A Fast Jamming Waveform Design Method for Deployment in Precision Electronic Warfare Scenario

A Fast Jamming Waveform Design Method for Deployment in Prec...

引用

Science and Technology Innovation (IAECST), International Academic Exchange Conference on

作者： Kedi Zhang Jing Wang Qingsong Zhou Jianyun Zhang College of Electronic Engineering National University of Defense Technology Hefei China College of Computer National University of Defense Technology Changsha China

ISBN: (纸本)9781665402682

Precision electronic warfare (PREW) is a focused energy delivery application that has been recently developed to address a number of issues associated with present electronic warfare approaches. However, current efforts to design jamming waveforms appropriate to the ultra-sparse and distributed arrays employed in PREW scenarios have had limited success. This paper addresses the issue by proposing a cyclic algorithm for the first time to facilitate the rapid design of constant-modulus jamming waveforms suitable for deployment in PREW scenarios. The jamming effects of the waveforms generated by the proposed algorithm are analyzed via numerical computations under a standard PREW scenario. The proposed algorithm is demonstrated to provide reasonable constant-modulus jamming waveforms suitable for deployment in PREW scenarios in a relatively short time.

关键词： Technological innovation Design methodology Electromagnetic scattering Jamming Covariance matrices Electromagnetics distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Collision-free allocation of temporally constrained tasks in multi-robot systems

引用

ROBOTICS AND AUTONOMOUS SYSTEMS 2019年 119卷 151-172页

作者： D'Emidio, Mattia Khan, Imran Univ LAquila Dept Comp Sci Informat Engn & Math DISIM Via Vetoio I-67100 Laquila Italy Gran Sasso Sci Inst Via F Crispi I-67100 Laquila Italy

Multi-robot systems (mRs) are a reference solution for many prominent real-world applications, e.g. management of warehouses or exploration of unknown environments. One of the most fundamental computational problems in MRS is that of planning the assignment of tasks to robots when such tasks have deadlines, i.e. constraints on when the execution must take place. The problem, when multiple objective functions of interest need to be optimized, is both NP-Hard and hard to approximate, and few heuristics are known in the literature to handle it. Unfortunately, none of them guarantees that the trajectories used by the robots when moving between tasks' locations are collision-free at planning time. Rather, they implement a reactive behavior, i.e. they abort the execution of a planned task whenever something goes wrong, e.g. trajectories of robots intersect or a deadline is missed due to some obstacle. This approach induces negative effects on the global performance of the system in the form of waste of energy, due to high distances traveled by the fleet members, or in the form of high convergence time to execute tasks. Therefore, planning the assignments of temporally constrained tasks with the guarantee of avoiding collisions can be a desirable feature for multi-robot systems. In this paper, we present CFAT-D (Collision-Free Allocation of Tasks having Deadlines), a new algorithm that can allocate temporally constrained tasks while guaranteeing that used trajectories are collision-free at planning time. We prove CFAT-D to be correct and showcase its effectiveness through an extensive experimental evaluation. Finally, we provide a roadmap toward the practical implementation of the new strategy in real-world environments. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Multi-robot systems distributed algorithms Task allocation Path planning Algorithm engineering Scheduling

来源：评论

学校读者我要写书评

暂无评论

Efficient and Parallel Separable Dictionary Learning

Efficient and Parallel Separable Dictionary Learning

引用

International Conference on Parallel and distributed Systems (ICPADS)

作者： Cristian Rusu Paul Irofti Faculty of Automatic Control and Computers University Politehnica Bucharest Bucharest Romania Faculty of Mathematics and Computer Science Research Center for Logic Optimization and Security (LOS) University of Bucharest Bucharest Romania

ISBN: (纸本)9781665408790

Separable, or Kronecker product, dictionaries provide natural decompositions for 2D signals, such as images. In this paper, we describe a highly parallelizable algorithm that learns such dictionaries which reaches sparse representations competitive with the previous state of the art dictionary learning algorithms from the literature but at a lower computational cost. We highlight the performance of the proposed method to sparsely represent image and hyperspectral data, and for image denoising.

关键词： Training Dictionaries Conferences Machine learning Computational efficiency distributed algorithms Image denoising

来源：评论

学校读者我要写书评

暂无评论

On asynchronous rendezvous in general graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 753卷 80-90页

作者： Bampas, Evangelos Blin, Lelia Czyzowicz, Jurek Ilcinkas, David Labourel, Arnaud Potop-Butucaru, Maria Tixeuil, Sebastien Aix Marseille Univ LIS Marseille France CNRS Paris France Univ Evry Val Essonne Sorbonne Univ CNRS LIP6 F-75005 Paris France Univ Quebec Gatineau PQ Canada CNRS LaBRI Paris France Univ Bordeaux Bordeaux France Sorbonne Univ CNRS LIP6 F-75005 Paris France

A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. (C) 2018 Published by Elsevier B.V.

关键词： distributed algorithms Asynchronous Mobile agents General graphs Rendezvous

来源：评论

学校读者我要写书评

暂无评论

Online Leader Selection for Collective Tracking and Formation Control: The Second-Order Case

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2019年第4期6卷 1415-1425页

作者： Franchi, Antonio Giordano, Paolo Robuffo Michieletto, Giulia Univ Toulouse CNRS LAAS F-31400 Toulouse France Univ Rennes IRISA INRIA CNRS Rennes France Univ Padua Dept Informat Engn I-35100 Padua Italy

In this paper, we deal with a double control task for a group of interacting agents that have second-order dynamics. Adopting the leader-follower paradigm, the given multiagent system is required to maintain a desired formation and to collectively track a velocity reference provided by an external source only to a single agent at time, called the "leader." We prove that it is possible to optimize the group performance by persistently selecting online the leader among the agents. To do this, we first define a suitable error metric that is able to capture the tracking performance of the multiagent group while maintaining a desired formation through a (even time-varying) communication-graph topology. Then, we show that this depends on the algebraic connectivity and on the maximum eigenvalue of the Laplacian matrix of a special directed graph depending on the selected leader. By exploiting these theoretical results, we finally design a fully distributed adaptive procedure that is able to periodically select online the optimum leader among the neighbors of the current one. The effectiveness of the proposed solution against other possible strategies is confirmed by numerical simulations.

关键词： Decentralized control distributed agent systems distributed algorithms mobile agents multiagent systems

来源：评论

学校读者我要写书评

暂无评论

Deterministic Leader Election Takes Θ(D plus log n) Bit Rounds

引用

ALGORITHMICA 2019年第5期81卷 1901-1920页

作者： Casteigts, A. Metivier, Y. Robson, J. M. Zemmari, A. Univ Bordeaux Bordeaux INP LaBRI UMR CNRS 5800 351 Cours Liberat F-33405 Talence France

Leader election is, together with consensus, one of the most central problems in distributed computing. This paper presents a distributed algorithm, called STT, for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size O(log n), where n is the number of processors. It elects a leader in O(D + log n) rounds, where D is the diameter of the network, with messages of size O(1). Thus it has a bit round complexity of O(D + log n). This substantially improves upon the best known algorithm whose bit round complexity is O (D log n). In fact, using the lower bound by Kutten et al. (J ACM 62(1):7:1-7:27, 2015) and Kutten et al. (Theor Comput Sci 561:134-143, 2015) and a result of Dinitz and Solomon (Theor Comput Sci 384(2-3):168-183, 2007), we show that the bit round complexity of STTis optimal (up to a constant factor), which is a significant step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as n or D, and the pipelining technique we introduce to break the O (D log n) barrier is general.

关键词： ELECTIONS distributed computing distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Privacy Preserving Modified Projection Subgradient Algorithm for Multi-Agent Online Optimization

Privacy Preserving Modified Projection Subgradient Algorithm...

引用

IEEE Symposium Series on Computational Intelligence (SSCI)

作者： Jiaojiao Yan Jinde Cao School of Mathematics Southeast University Nanjing China

ISBN: (纸本)9781728190495

This paper studies the distributed online optimization problem with the property of privacy preservation over multi-agent system, where the communication topology is a fixed and strongly connected digraph. We only assume that the weight matrix is row stochastic, which relaxes the assumption of doubly stochastic in some literature and is easier to implement than the column stochastic weight matrix. A virtual agent associated with each agent is added which only communicates with the agent itself and performs gradient iterative update. The original agent only communicates with the original neighbors and virtual agent. A distributed online algorithm is designed by using gradient readjustment technology combined with distributed projection subgradient method. It is proved that the proposed algorithm can achieve the purpose of privacy preservation while realizing the sublinear regret bound. Finally, an example is provided to validate the performance of the algorithm.

关键词： Privacy Topology Linear matrix inequalities distributed algorithms Optimization Computational intelligence Multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

Asynchronous Arbitrary Pattern Formation: the effects of a rigorous approach

引用

distributed COMPUTING 2019年第2期32卷 91-132页

作者： Cicerone, Serafino Di Stefano, Gabriele Navarra, Alfredo Univ Aquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy Univ Perugia Dept Math & Comp Sci Via Vanvitelli 1 I-06123 Perugia Italy

Given any multiset F of points in the Euclidean plane and a set R of robots such that |R|=|F|, the Arbitrary Pattern Formation (APF) problem asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections, uniform scalings. Initially, each robot occupies a distinct position. When active, a robot operates in standard Look-Compute-Move cycles. Robots are asynchronous, oblivious, anonymous, silent and execute the same distributed algorithm. So far, the problem has been mainly addressed by assuming chirality, that is robots share a common left-right orientation. We are interested in removing such a restriction. While working on the subject, we faced several issues that required close attention. We deeply investigated how such difficulties were overcome in the literature, revealing that crucial arguments for the correctness proof of the existing algorithms have been neglected. The systematic lack of rigorous arguments with respect to necessary conditions required for providing correctness proofs deeply affects the validity as well as the relevance of strategies proposed in the literature. Here we design a new deterministic distributed algorithm that fully characterizes APF showing its equivalence with the well-known Leader Election problem in the asynchronous model without chirality. Our approach is characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness. In addition to the relevance of our achievements, our techniques might help in revising previous results. In fact, it comes out that well-established results like (Fujinaga et al. in SIAM J Comput 44(3):740-785, 2015), more recent approaches like (Bramas and Tixeuil, in: Proceedings of the 35th ACM SIGACT-SIGOPS symposium on principles of distributed computing (PODC), 2016;Bramas and Tixeuil, in: Proceedings of the 18th interna

关键词： distributed algorithms Mobile robots Asynchrony Pattern formation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：