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

30th annual acm symposium on Applied Computing, SAC 2015

ISBN: (纸本)9781450331968

The proceedings contain 367 papers. The topics discussed include: inference of disease-specific gene interaction network using a Bayesian network learned by genetic algorithm;P-SaMI: a data-flow pattern to perform massively-parallel molecular docking experiments using a fully-flexible receptor model;a new approach to biometric recognition based on hand geometry;shape description based on bag of salience points;OR-PCA with dynamic feature selection for robust background subtraction;compact and discriminative approach for encoding spatial-relationship of visual words;an architecture of recommender system for scientific paper;evolving decision-tree induction algorithms with a multi-objective hyper-heuristic;collective preferences in evolutionary multi-objective optimization: techniques and potential contributions of collective intelligence;color image quantization using interactive genetic algorithm;and benchmarking motion sensing devices for rehabilitative gaming.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Help! 15

Help!

引用

34th annual acm symposium on Principles of Distributed Computing (PODC)

作者： Censor-Hillel, Keren Petrank, Erez Timnat, Shahar Technion Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781450336178

A fundamental challenge in designing concurrent data structures is obtaining efficient wait-free implementations, in which each operation completes regardless of the behavior of other operations in the system. The most common paradigm for guaranteeing wait-freedom is to employ a helping mechanism, in which, intuitively, fast processes help slow processes complete their operations. Curiously, despite its abundant use, to date, helping has not been formally defined nor was its necessity rigorously studied. In this paper we initiate a rigorous study of the interaction between wait-freedom and helping. We start with presenting a formal definition of help, capturing the intuition of one thread helping another to make progress. Next, we present families of object types for which help is necessary in order to obtain wait-freedom. In other words, we prove that for some types there are no linearizable wait-free help-free implementations. In contrast, we show that other, simple types, can be implemented in a linearizable wait-free manner without employing help. Finally, we provide a universal strong primitive for implementing wait-free data structures without using help. Specifically, given a wait-free help-free fetch&cons object, one can implement any type in a wait-free help-free manner.

关键词： parallel algorithms Concurrent Data Structures Progress Guarantees Wait-Freedom Help

来源：评论

学校读者我要写书评

暂无评论

Session details: Session 9: parallel and Distributed algorithms 15

Session details: Session 9: Parallel and Distributed Algorit...

引用

Proceedings of the 27th acm symposium on parallelism in algorithms and architectures

作者： Benjamin Moseley Washington University in St. Louis

No abstract available.

ISBN: (纸本)9781450335881

No abstract available.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Sequential Random Permutation, List Contraction and Tree Contraction are Highly parallel 15

Sequential Random Permutation, List Contraction and Tree Con...

引用

annual acm-Society for Industrial and Applied Mathmatics symposium on Discrete algorithms

作者： Julian Shun Yan Gu Guy E. Blelloch Jeremy T. Fineman Phillip B. Gibbons Carnegie Mellon University Georgetown University Intel Labs and Carnegie Mellon University

ISBN: (纸本)9781510813311

We show that simple sequential randomized iterative algorithms for random permutation, list contraction, and tree contraction are highly parallel. In particular, if iterations of the algorithms are run as soon as all of their dependencies have been resolved, the resulting computations have logarithmic depth (parallel time) with high probability. Our proofs make an interesting connection between the dependence structure of two of the problems and random binary trees. Building upon this analysis, we describe linear-work, polylogarithmic-depth algorithms for the three problems. Although asymptotically no better than the many prior parallel algorithms for the given problems, their advantages include very simple and fast implementations, and returning the same result as the sequential algorithm. Experiments on a 40-core machine show reasonably good performance relative to the sequential algorithms.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in parallel 15

Using Optimization to Break the Epsilon Barrier: A Faster an...

引用

annual acm-SIAM symposium on Discrete algorithms

作者： Zeyuan Allen-Zhu Lorenzo Orecchia MIT CSAIL MIT Math

ISBN: (纸本)9781510813311

We study the design of nearly-linear-time algorithms for approximately solving positive linear programs. Both the parallel and the sequential deterministic versions of these algorithms require O(ε~(-4)) iterations, a dependence that has not been improved since the introduction of these methods in 1993 by Luby and Nisan. Moreover, previous algorithms and their analyses rely on update steps and convergence arguments that are combinatorial in nature, and do not seem to arise naturally from an optimization viewpoint. In this paper, we leverage insights from optimization theory to construct a novel algorithm that breaks the longstanding O(ε~(-4)) barrier. Our algorithm has a simple analysis and a clear motivation. Our work introduces a number of novel techniques, such as the combined application of gradient descent and mirror descent, and a truncated, smoothed version of the standard multiplicative weight update, which may be of independent interest.

关键词： algorithms parallel Lines linear programming Optimization theory descent Respite Care

来源：评论

学校读者我要写书评

暂无评论

ARC 2014: A Multidimensional FPGA-Based parallel DBSCAN Architecture

引用

acm TRANSACTIONS ON RECONFIGURABLE TECHNOLOGY AND SYSTEMS 2015年第1期9卷 2-2页

作者： Scicluna, Neil Bouganis, Christos-Savvas Univ London Imperial Coll Sci Technol & Med Dept Elect & Elect Engn London SW7 2AZ England

Clustering large numbers of data points is a very computationally demanding task that often needs to be accelerated in order to be useful in practical applications. This work focuses on the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm, which is one of the state-of-the-art clustering algorithms, and targets its acceleration using an FPGA device. The article presents an optimized, scalable, and parameterizable architecture that takes advantage of the internal memory structure of modern FPGAs in order to deliver a high-performance clustering system. Post-synthesis simulation results show that the developed system can obtain mean speedups of 31 x in real-world tests and 202 x in synthetic tests when compared to state-of-the-art software counterparts running on a quad-core 3.4GHz Intel i7-2600k. Additionally, this implementation is also capable of clustering data with any number of dimensions without impacting the performance.

关键词： Design algorithms Performance Clustering DBSCAN FPGA parallel hardware architectures

来源：评论

学校读者我要写书评

暂无评论

Exploring the Design Space of SPMD Divergence Management on Data-parallel architectures 47

Exploring the Design Space of SPMD Divergence Management on ...

引用

47th annual IEEE/acm International symposium on Microarchitecture (MICRO)

作者： Lee, Yunsup Grover, Vinod Krashinsky, Ronny Stephenson, Mark Keckler, Stephen W. Asanovic, Krste Univ Calif Berkeley Berkeley CA 94720 USA NVIDIA Santa Clara CA USA Univ Texas Austin Austin TX 78712 USA

ISBN: (纸本)9781479969982

Data-parallel architectures must provide efficient support for complex control-flow constructs to support sophisticated applications coded in modern single-program multiple-data languages. As these architectures have wide datapaths that process a single instruction across parallel threads, a mechanism is needed to track and sequence threads as they traverse potentially divergent control paths through the program. The design space for divergence management ranges from software-only approaches where divergence is explicitly managed by the compiler, to hardware solutions where divergence is managed implicitly by the microarchitecture. In this paper, we explore this space and propose a new predication-based approach for handling control-flow structures in data-parallel architectures. Unlike prior predication algorithms, our new compiler analyses and hardware instructions consider the commonality of predication conditions across threads to improve efficiency. We prototype our algorithms in a production compiler and evaluate the tradeoffs between software and hardware divergence management on current GPU silicon. We show that our compiler algorithms make a predication-only architecture competitive in performance to one with hardware support for tracking divergence.

关键词： Vectors Hardware Computer architecture Registers Optimization Software Support vector machines

来源：评论

学校读者我要写书评

暂无评论

Hypergraph Partitioning for parallel Sparse Matrix-Matrix Multiplication 15

Hypergraph Partitioning for Parallel Sparse Matrix-Matrix Mu...

引用

Proceedings of the 27th acm symposium on parallelism in algorithms and architectures

作者： Grey Ballard Alex Druinsky Nicholas Knight Oded Schwartz Sandia National Laboratories Livermore CA USA Lawrence Berkeley National Laboratory Berkeley CA USA University of California Berkeley Berkeley CA USA Hebrew University Jerusalem Israel

ISBN: (纸本)9781450335881

The performance of parallel algorithms for sparse matrix-matrix multiplication is typically determined by the amount of interprocessor communication performed, which in turn depends on the nonzero structure of the input matrices. In this paper, we characterize the communication cost of a sparse matrix-matrix multiplication algorithm in terms of the size of a cut of an associated hypergraph that encodes the computation for a given input nonzero structure. Obtaining an optimal algorithm corresponds to solving a hypergraph partitioning problem. Our hypergraph model generalizes several existing models for sparse matrix-vector multiplication, and we can leverage hypergraph partitioners developed for that computation to improve application-specific algorithms for multiplying sparse matrices.

关键词： communication costs communication lower bounds sparse matrix-matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Simple parallel and Distributed algorithms for Spectral Graph Sparsification 14

Simple Parallel and Distributed Algorithms for Spectral Grap...

引用

26th acm symposium on parallelism in algorithms and architectures (SPAA)

作者： Koutis, Ioannis Univ Puerto Rico Rio Piedras Comp Sci Dept San Juan PR 00925 USA

ISBN: (纸本)9781450328210

We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling. Leveraging the algorithms of Baswana and Sen for computing spanners, we obtain the first distributed spectral sparsification algorithm. We also obtain a parallel algorithm with improved work and time guarantees. Combining this algorithm with the parallel framework of Peng and Spielman for solving symmetric diagonally dominant linear systems, we get a parallel solver which is much closer to being practical and significantly more efficient in terms of the total work.

关键词： parallel algorithms Distributed algorithms Spectral Sparsification SDD linear systems

来源：评论

学校读者我要写书评

暂无评论

Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovasz Local Lemma 15

Lopsidependency in the Moser-Tardos framework: Beyond the Lo...

引用

annual acm-Society for Industrial and Applied Mathmatics symposium on Discrete algorithms

作者： David G. Harris Department of Applied Mathematics University of Maryland

ISBN: (纸本)9781510813311

The Lopsided Lovasz Local Lemma (LLLL) is a powerful probabilistic principle which has been used in a variety of combinatorial constructions. While this principle began as a general statement about probability spaces, it has recently been transformed into a variety of polynomial-time algorithms. The resampling algorithm of Moser & Tardos is the most well-known example of this. A variety of criteria have been shown for the LLLL; the strongest possible criterion was shown by Shearer, and other criteria which are easier to use computationally have been shown by Bissacot et al, Pegden, and Kolipaka & Szegedy. We show a new criterion for the Moser-Tardos algorithm to converge. This criterion is stronger than the LLLL criterion, and in fact can yield better results even than the full Shearer criterion. This is possible because it does not apply in the same generality as the original LLLL; yet, it is strong enough to cover many applications of the LLLL in combinatorics. We show a variety of new bounds and algorithms. A noteworthy application is for k-SAT, with bounded occurences of variables. As shown in Gebauer, Szabo, and Tardos, a k-SAT instance in which every variable appears L ≤ 2~(k+1)/(e(k+1)) times, is satisfiable. Although this bound is asymptotically tight (in k), we improve it to L ≤ (2~(k+1)(1-1/k)~k)/(k-1) - 2/k which can be significantly stronger when k is small. We introduce a new parallel algorithm for the LLLL. While Moser & Tardos described a simple parallel algorithm for the Lovasz Local Lemma, and described a simple sequential algorithm for a form of the Lopsided Lemma, they were not able to combine the two. Our new algorithm applies in nearly all settings in which the sequential algorithm works - this includes settings covered by our new stronger LLLL criterion.

关键词： parallel algorithms Lemma winning and haulage machine sequential algorithm Combinatorics algorithms Probability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：