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

High Performance Computing, Networking, Storage and Analysis (SCC), SC Companion:

作者： Gerhard Niederbrucker Hana Straková Wilfried N. Gansterer Research Group Theory and Applications of Algorithms University of Vienna Austria

ISBN: (纸本)9781467362184

Most existing algorithms for parallel or distributed reduction operations are not able to handle temporary or permanent link and node failures. Only recently, methods were proposed which are in principal capable of tolerating link and node failures as well as soft errors like bit flips or message loss. A particularly interesting example is the pushflow algorithm. However, on closer inspection, it turns out that in this method the failure recovery often implies severe performance drawbacks. Existing mechanisms for failure handling may basically lead to a fall-back to an early stage of the computation and consequently slow down convergence or even prevent convergence if failures occur too frequently. Moreover, state-of-the-art fault tolerant distributed reduction algorithms may experience accuracy problems even in failure free systems. We present the push-cancel-flow (PCF) algorithm, a novel algorithmic enhancement of the push-flow algorithm. We show that the new push-cancel-flow algorithm exhibits superior accuracy, performance and fault tolerance over all other existing distributed reduction methods. Moreover, we employ the novel PCF algorithm in the context of a fully distributed QR factorization process and illustrate that the improvements achieved at the reduction level directly translate to higher level matrix operations, such as the considered QR factorization.

关键词： Fault tolerance permanent contact Distribute failure recovery algorithms Converge quick release failures factorization

来源：评论

学校读者我要写书评

暂无评论

Poster: Gossip-Based Distributed Matrix Computations

Poster: Gossip-Based Distributed Matrix Computations

引用

High Performance Computing, Networking, Storage and Analysis (SCC), SC Companion:

作者： Hana Strakova Wilfried N. Gansterer Research Group Theory and Applications of Algorithms University of Vienna Vienna Austria

EXTENDED ABSTRACT SUBMITTED SEPARATELY

关键词：

来源：评论

学校读者我要写书评

暂无评论

A fast solver for modeling the evolution of virus populations

A fast solver for modeling the evolution of virus population...

引用

Supercomputing Conference

作者： Gerhard Niederbrucker Wilfried N. Gansterer Research Group Theory and Applications of Algorithms University of Technology Vienna Austria

Solving Eigen's quasispecies model for the evolution of virus populations involves the computation of the dominant eigen vector of a matrix whose size N grows exponentially with the chain length of the virus to be modeled. Most biologically interesting chain lengths are so far well beyond the reach of existing algorithms and hardware. We show how to exploit the special properties of the problem under consideration and design a fast and accurate solver which reduces the complexity to Θ(N log 2 N). Our solver is even faster than existing approximative strategies and contrary to those it can also be applied to more general formulations of the quasispecies model. Substantial further improvements and high parallelism can be achieved for special fitness landscapes in the evolution model. Beyond theoretical analysis, we evaluate the performance of our new solver experimentally on a GPU with an OpenCL implementation and illustrate that it achieves speedup factors of more than 107 over standard approaches.

关键词： Vectors Computational modeling Eigenvalues and eigenfunctions RNA Complexity theory Mathematical model Error analysis

来源：评论

学校读者我要写书评

暂无评论

A Distributed Eigensolver for Loosely Coupled Networks

A Distributed Eigensolver for Loosely Coupled Networks

引用

Euromicro Conference on Parallel, Distributed and Network-Based Processing

作者： Hana Strakova Wilfried N. Gansterer Research Group Theory and Applications of Algorithms University of Vienna Vienna Austria

We introduce a new distributed eigensolver (dOI) for square matrices based on orthogonal iteration. In contrast to standard parallel eigensolvers, our approach performs only nearest neighbor communication and provides much more flexibility with respect to the properties of the hardware infrastructure on which the computation is performed. This is achieved by utilizing distributed summation methods with randomized communication schedules which do not require global synchronization across the nodes. Our algorithm is particularly attractive for loosely coupled distributed networks with arbitrary network topologies and potentially unreliable components. Our distributed eigensolver dOI is based on a novel distributed matrix-matrix multiplication algorithm and on an extension of a distributed QR factorization algorithm proposed earlier. We illustrate the advantages of dOI in terms of higher flexibility with respect to the underlying network and lower communication cost compared to a related distributed eigensolver by Kempe and McSherry. Moreover, we experimentally illustrate how the overall communication cost of dOI is further reduced by adapting the accuracy of each distributed summation during the orthogonal iteration process.

关键词： Accuracy Topology Network topology Algorithm design and analysis Eigenvalues and eigenfunctions Signal processing algorithms Vectors

来源：评论

学校读者我要写书评

暂无评论

Evaluation of the Stretch S6 Hybrid Reconfigurable Embedded CPU Architecture for Power-Efficient Scientific Computing

引用

Procedia Computer Science 2012年 9卷 196-205页

作者： Thang Viet Huynh Manfred Mücke Wilfried N. Gansterer Graz University of Technology Signal Processing and Speech Communication Lab (SPSC) University of Vienna Research Group Theory and Applications of Algorithms (TAA)

Embedded CPUs typically use much less power than desktop or server CPUs but provide limited or no support for floating-point arithmetic. Hybrid reconfigurable CPUs combine fixed and reconfigurable computing fabrics to balance better execution performance and power consumption. We show how a Stretch S6 hybrid reconfigurable CPU (S6) can be extended to natively support double precision floating-point arithmetic. For lower precision number formats, multiple parallel arithmetic units can be implemented. We evaluate if the superlinear performance improvement of floating-point multiplication on reconfigurable fabrics can be exploited in the framework of a hybrid reconfigurable CPU. We provide an in-depth investigation of data paths to and from the S6 reconfigurable fabric and present peak and sustained throughput as a function of wide registers used and total operand size. We demonstrate the effect of the given interface when using a floating-point fused multiply-accumulate (FMA) SIMD unit to accelerate the LINPACK benchmark. We identify a mismatch between the size of the S6s reconfigurable fabric and the available interface bandwidth as the major bottleneck limiting performance which makes it a poor choice for scientific workloads relying on native support for floating-point arithmetic.

关键词： Scientific Computing Floating-Point Arithmetic Power-Aware Computing LINPACK Reconfigurable Hardware Computer Architecture

来源：评论

学校读者我要写书评

暂无评论

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More 13

Graph Products Revisited: Tight Approximation Hardness of In...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Parinya Chalermsook Bundit Laekhanukit Danupon Nanongkai IDSIA School of Computer Science McGill University Theory and Applications of Algorithms Research Group University of Vienna

ISBN: (纸本)9781611972511

Graph product is a fundamental tool with rich applications in both graph theory and theoretical computer science. It is usually studied in the form f(G * H) where G and H are graphs, * is a graph product and f is a graph property. For example, if f is the independence number and * is the disjunctive product, then the product is known to be multiplicative: f(G * H) = f(G)f(H). In this paper, we study graph products in the following non-standard form: f((G{direct +} H)*J) where G, H and J are graphs, and * are two different graph products and f is a graph property. We show that if f is the induced and semi-induced matching number, then for some products {direct +} and *, it is subadditive in the sense that f((G{direct +} H) * J) ≤ f(G* J)+f(H * J). Moreover, when f is the poset dimension number, it is almost subadditive.

关键词： Graph Products Approximation Hardness Poset Dimension subadditive Line graph Poset Fluorine (F) iodine dimensions theoretical computer science Discrete mathematics approximation

来源：评论

学校读者我要写书评

暂无评论

An O(n~2) Time Algorithm for Alternating Buchi Games 12

An O(n~2) Time Algorithm for Alternating Buchi Games

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Krishnendu Chatterjee Monika Henzinger IST Austria (Institute of Science and Technology Austria) Research Group Theory and Applications of Algorithms University of Vienna

ISBN: (纸本)9781611972108

Computing the winning set for Buchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is O{top}~(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the O{top}~(n·m) boundary by presenting a new technique that reduces the running time to O(n~2). This bound also leads to O(n~2) time algorithms for computing the set of almost-sure winning vertices for Buchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of {top}O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n~3)), and (3) in Markov decision processes (improving for m ＞ n~(4/3) an earlier bound of O(min(m~(1.5),m· n~(2/3))). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n~2), which is an improvement over earlier bounds for m ＞ n~(4/3). Finally, we show how to maintain the winning set for Buchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.

关键词： Graph games Buchi objectives Graph algorithms Dynamic graph algorithms Computer-aided verification Graph algorithms Buchi Game theory mining Bound Markov chain Runtime

来源：评论

学校读者我要写书评

暂无评论

Distributed Gram-Schmidt orthogonalization based on dynamic consensus

Distributed Gram-Schmidt orthogonalization based on dynamic ...

引用

Asilomar Conference on Signals, Systems & Computers

作者： Ondrej Slučiak Hana Straková Markus Rupp Wilfried N. Gansterer Institute of Telecommunications Vienna University of Technology Austria Research Group Theory and Applications of Algorithms University of Vienna Austria

We propose a novel distributed QR factorization algorithm for orthogonalizing a set of vectors in a wireless sensor network. The algorithm originates from the classical Gram-Schmidt orthogonalization which we formulate in a distributed way using the dynamic consensus algorithm. In contrast to existing distributed QR factorization algorithms, all elements of matrices Q and R are computed simultaneously and updated iteratively after each transmission. Assuming synchronous message broadcasting and communication only with neighboring nodes without any central computing unit (fusion center), we prove convergence of the algorithm. We investigate the algorithm in terms of numerical accuracy and we discuss the influence of the initial data distribution on the algorithm performance. Moreover, we provide a comparison with existing distributed QR algorithms in terms of communication cost and memory requirements, and we illustrate the comparison by simulations.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: Maintaining large dense subgraphs on dynamic networks 12

Brief announcement: Maintaining large dense subgraphs on dyn...

引用

2012 ACM Symposium on Principles of Distributed Computing, PODC'12

作者： Sarma, Atish Das Lall, Ashwin Nanongkai, Danupon Trehan, Amitabh eBay Research Labs. eBay Inc. San Jose CA United States Department of Mathematics and Computer Science Denison University Granville OH United States Theory and Applications of Algorithms Research Group University of Vienna Vienna Austria Information Systems Group Faculty of Industrial Engineering and Management Technion Haifa Israel

ISBN: (纸本)9781450314503

In distributed networks, some groups of nodes may have more inter-connections, perhaps due to their larger bandwidth availability or communication requirements. In many scenarios, it may be useful for the nodes to know if they form part of a dense subgraph, e.g., such a dense subgraph could form a high bandwidth backbone for the network. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs (subgraphs that the member nodes are aware of). The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model in the sense that only messages of O(log n) size are permitted, where n is the number of nodes in the network. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that approximate both the densest subgraph, i.e., the subgraph of the highest density in the network, and the at-least-k-densest subgraph (for a given parameter k), i.e., the densest subgraph of size at least k. We give a (2 + Ε)-approximation algorithm for the densest subgraph problem. The at-least-k-densest subgraph is known to be NP-hard for the general case in the centralized setting and the best known algorithm gives a 2-approximation. We present an algorithm that maintains a (3+Ε)-approximation in our distributed, dynamic setting. Our algorithms run in O(Dlog1+Ε n) time. © 2012 Authors.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

DISTRIBUTED DECORRELATION IN SENSOR NETWORKS WITH APPLICATION TO DISTRIBUTED PARTICLE FILTERING

DISTRIBUTED DECORRELATION IN SENSOR NETWORKS WITH APPLICATIO...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Michael Moldaschl Wilfried N. Gansterer Ondrej Hlinka Florian Meyer Franz Hlawatsch University of Vienna Research Group Theory and Applications of Algorithms Vienna Austria Institute of Telecommunications Vienna University of Technology Vienna Austria

ISBN: (纸本)9781479928941

Most distributed statistical signal processing methods assume conditionally uncorrelated sensor measurements although this assumption is often not satisfied. Here, we propose a distributed algorithm for decorrelating the sensor measurements in a wireless sensor network. The algorithm employs a matrix-valued Chebyshev approximation to achieve an approximate decorrelation using only local computations and communication between neighboring sensors. We apply the algorithm to consensus-based distributed particle filtering in a target tracking problem with correlated measurement noises. Simulations show that the decorrelation yields a substantial accuracy improvement while causing only a small communication overhead.

关键词： Decorrelation Chebyshev approximation Approximation algorithms Atmospheric measurements Particle measurements Vectors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：