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

A Deterministic parallel Algorithm for Bipartite Perfect Matching

COMMUNICATIONS OF THE ACM 2019年第3期62卷 109-115页

作者： Fenner, Stephen Gurjar, Rohit Thierauf, Thomas Univ South Carolina Columbia SC 29208 USA CALTECH Pasadena CA 91125 USA Aalen Univ Aalen Germany

A fundamental quest in the theory of computing is to understand the power of randomness. It is not known whether every problem with an efficient randomized algorithm also has one that does not use randomness. One of the extensively studied problems under this theme is that of perfect matching. The perfect matching problem has a randomized parallel (NC) algorithm based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. It is a long-standing open question whether this algorithm can be derandomized. In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic parallel (quasi-NC) algorithm for the bipartite perfect matching problem. Derandomization of the Isolation Lemma means that we deterministically construct a weight assignment so that the minimum weight perfect matching is unique. We present three different ways of doing this construction with a common main idea.

关键词： Perfect Lemma parallel algorithms deterministic Random Number Generators TWO-COMPONENT

来源：评论

学校读者我要写书评

暂无评论

A parallel Algorithm for Community Detection in Social Networks, Based on Path Ana vs is and Threaded Binary Trees

引用

IEEE ACCESS 2019年 7卷 20499-20519页

作者： Souravlas, Stavros Sifaleras, Angelo Katsavounis, Stefanos Univ Macedonia Dept Appl Informat Thessaloniki 54636 Greece Democritus Univ Thrace Dept Prod & Management Engn Xanthi 67100 Greece

Several synchronous applications are based on the graph-structured data;among them, a very important application of this kind is community detection. Since the number and size of the networks modeled by graphs grow larger and larger, some level of parallelism needs to be used, to reduce the computational costs of such massive applications. Social networking sites allow users to manually categorize their friends into social circles (referred to as lists on Facebook and Twitter), while users, based on their interests, place themselves into groups of interest. However, the community detection and is a very effortful procedure, and in addition, these communities need to be updated very often, resulting in more effort. In this paper, we combine parallel processing techniques with a typical data structure like threaded binary trees to detect communities in an efficient manner. Our strategy is implemented over weighted networks with irregular topologies and it is based on a stepwise path detection strategy, where each step finds a link that increases the overall strength of the path being detected. To verify the functionality and parallelism benefits of our scheme, we perform experiments on five real-world data sets: Facebook (R), Twitter (R), Google+(R), Pokec, and LiveJournal.

关键词： Community detection parallel algorithms binary trees social circles

来源：评论

学校读者我要写书评

暂无评论

Arbitrarily parallel Turbo Decoding for Ultra-Reliable Low Latency Communication in 3GPP LTE

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2019年第4期37卷 826-838页

作者： Xiang, Luping Brejza, Matthew E. Maunder, Robert G. Al-Hashimi, Bashir M. Hanzo, Lajos Univ Southampton Sch Elect & Comp Sci Southampton SO17 1BJ Hants England

In order to meet the latency requirements of the ultra-reliable low latency communication (URLLC) mode of the third-generation partnership project's long term evolution (LTE) mobile communication standard, this paper proposes a novel turbo decoding algorithm that supports an arbitrarily high degree of parallel processing, facilitating significantly higher processing throughputs and substantially lower processing latencies than the state-of-the-art (SOTA) LTE turbo decoder. As in conventional turbo decoding algorithms, the proposed Arbitrarily parallel Turbo Decoder (APTD) decomposes each frame of information bits into a sequence of windows, where the bits within different windows are processed simultaneously using forward and backward recursions in a serial manner. However, in contrast to conventional turbo decoding algorithms, the APTD does not require different windows to be composed of an identical number of bits, which allows the use of an arbitrary number of windows and hence an arbitrary degree of parallelism, when decoding information bits of an arbitrary frame length. Furthermore, conventional turbo decoding algorithms alternate between simultaneously processing the windows in the upper decoder and those in the lower decoder. By contrast, the APTD processes the odd-indexed windows in the upper decoder at the same time as the even-indexed windows in the lower decoder and alternates between this and the reversed arrangement, hence further improving the decoding throughput and latency. Furthermore, the APTD achieves a reduced hardware resource requirement by calculating the extrinsic information based only on the outputs of the forward recursions, rather than based on both the forward and backward recursions of conventional turbo decoding algorithms. We demonstrate that the proposed APTD achieves superior latency, throughput, and computational efficiency than the SOTA LTE turbo decoder at all frame lengths, but particularly at the short frame lengths that are t

关键词： Turbo decoding FPTD parallel algorithms latency throughput

来源：评论

学校读者我要写书评

暂无评论

parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2019年第2期73卷 575-601页

作者： Munguia, Lluis-Miquel Oxberry, Geoffrey Rajan, Deepak Shinano, Yuji Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Lawrence Livermore Natl Lab Computat Engn Div Livermore CA 94550 USA Zuse Inst Berlin Dept Optimizat Takustr 7 D-14195 Berlin Germany

PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve mixed integer programs (MIPs) with a dual-block angular structure, which is characteristic of deterministic-equivalent stochastic mixed-integer programs. In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator, a universal framework for parallelizing B&B tree search that has been sucessfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.

关键词： MIPs Stochastic MIPs parallel algorithms parallel Branch and Bound

来源：评论

学校读者我要写书评

暂无评论

Improved parallel Resampling Methods for Particle Filtering

引用

IEEE ACCESS 2019年 7卷 47593-47604页

作者： Nicely, Matthew A. Wells, B. Earl Univ Alabama Dept Elect & Comp Engn Huntsville AL 35805 USA

Particle filter techniques are common methods used to estimate the evolving state of nonlinear, non-Gaussian time-variant systems by utilizing a periodic sequence of noisy measurements. The accuracy of particle filter methods has often been shown to be superior to other state estimation techniques, such as the extended Kalman filter (EKF), for many applications. Unfortunately, the high computational cost and highly nondeterministic runtime behavior of particle filters often preclude their use in hard, real-time environments, where filter response must meet the strict timing requirements of the application. Particle filter algorithms are composed of three main stages: prediction, update, and resampling. General purpose graphics processing units (GPGPUs) have been successfully employed in previous research to accelerate the computation of both the prediction and update stages by exploiting their natural fine-grain parallelism. This research focuses on accelerating the resampling stage for GPGPU execution, which has been much more difficult to parallelize due to it's apparent inherent sequentially. This paper introduces a novel GPGPU implementation of the systematic and stratified resampling algorithms that exploit the monotonically increasing nature of the prefix-sum and the evolutionary nature of the particle weighting process to allow the re-indexing portion of the algorithms to occur in a two-phase, multi-threaded manner. This resulting measured factor of performance improvement for the systematic and stratified algorithms was 15x and 32x, respectively, over the serial implementations.

关键词： Graphics processing units parallel algorithms parallel architectures parallel programming particle filters state estimation resampling

来源：评论

学校读者我要写书评

暂无评论

Heterogeneous Island Models and Their Application to Recommender Systems and Electric Vehicle Charging

引用

INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS 2020年第3-4期29卷

作者： Balcar, Stepan Pilat, Martin Charles Univ Prague Fac Math & Phys Malostranske Namesti 25 Prague 11800 Czech Republic

In this paper we describe a general framework for parallel optimization based on the island model of evolutionary algorithms. The framework runs a number of optimization methods in parallel with periodic communication. In this way, it essentially creates a parallel ensemble of optimization methods. At the same time, the system contains a planner that decides which of the available optimization methods should be used to solve the given optimization problem and changes the distribution of such methods during the run of the optimization. Thus, the system effectively solves the problem of online parallel portfolio selection. The proposed system is evaluated in a number of common benchmarks with various problem encodings as well as in two real-life problems - the optimization in recommender systems and the training of neural networks for the control of electric vehicle charging.

关键词： Evolutionary algorithms parallel algorithms recommender systems electric vehicle charging

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel algorithms for computing the sum, the prefix-sums, and the summed area table on the memory machine models

Optimal parallel algorithms for computing the sum, the prefi...

引用

作者： Nakano, Koji Department of Information Engineer-ing Hiroshima University Higashihiroshima-shi Japan

The main contribution of this paper is to show optimal parallel algorithms to compute the sum, the prefix-sums, and the summed area table on two memory machine models, the Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM). The DMM and the UMM are theoretical parallel computing models that capture the essence of the shared memory and the global memory of GPUs. These models have three parameters, the number p of threads, and the width w of the memory, and the memory access latency /. We first show that the sum of n numbers can be computed in O{ JJ + ^ + / log ri) time units on the DMM and the UMM. We then go on to show that Cl(^ + ^ + Hog ri) time units are necessary to compute the sum. We also present a parallel algorithm that computes the prefix-sums of n numbers in O(j;+ ^j + Hog ri) time units on the DMM and the UMM. Finally, we show that the summed area table of size V'' x V'' can be computed in O time units on the DMM and the UMM. Since the computation of the prefix-sums and the summed area table is at least as hard as the sum computation, these parallel algorithms are also optimal. © 2013 The Institute of Electronics, Information and Communication Engineers.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Model-driven transformations for mapping parallel algorithms on parallel computing platforms 2

Model-driven transformations for mapping parallel algorithms...

引用

2nd International Workshop on Model-Driven Engineering for High Performance and CLoud Computing, MDHPCL 2013 - Co-located with 16th International Conference on Model Driven Engineering Languages and Systems, MODELS 2013

作者： Arkin, Ethem Tekinerdogan, Bedir Aselsan MGEO Ankara Turkey Bilkent University Dept. of Computer Engineering Ankara Turkey

One of the important problems in parallel computing is the mapping of the parallel algorithm to the parallel computing platform. Hereby, for each parallel node the corresponding code for the parallel nodes must be implemented. For platforms with a limited number of processing nodes this can be done manually. However, in case the parallel computing platform consists of hundreds of thousands of processing nodes then the manual coding of the parallel algorithms becomes intractable and error-prone. Moreover, a change of the parallel computing platform requires considerable effort and time of coding. In this paper we present a model-driven approach for generating the code of selected parallel algorithms to be mapped on parallel computing platforms. We describe the required platform independent metamodel, and the model-to-model and the model-to-text transformation patterns. We illustrate our approach for the parallel matrix multiplication algorithm. Copyright © 2013 for the individual papers by the papers' authors.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Write-Efficient algorithms and Data Structures for Computational Geometry 18

Parallel Write-Efficient Algorithms and Data Structures for ...

引用

30th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Blelloch, Guy E. Gu, Yan Shun, Julian Sun, Yihan Carnegie Mellon Univ Pittsburgh PA 15213 USA MIT CSAIL Cambridge MA USA

ISBN: (纸本)9781450357999

In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by emerging non-volatile memory technologies with read performance being close to that of random access memory but writes being significantly more expensive in terms of energy and latency. We design algorithms for planar Delaunay triangulation, k-d trees, and static and dynamic augmented trees. Our algorithms are designed in the recently introduced Asymmetric Nested-parallel Model, which captures the parallel setting in which there is a small symmetric memory where reads and writes are unit cost as well as a large asymmetric memory where writes are omega times more expensive than reads. In designing these algorithms, we introduce several techniques for obtaining write-efficiency, including DAG tracing, prefix doubling, and alpha-labeling, which we believe will be useful for designing other parallel write-efficient algorithms.

关键词： asymmetric nested-parallel model kd-trees priority tree parallel algorithms interval tree delaunay triangulation computational geometry augmented trees data structure write-efficient algorithms asymmetric read and write costs range tree non-volatile memory

来源：评论

学校读者我要写书评

暂无评论

System Level Real-Time Simulation and Hardware-in-the-Loop Testing of MMCs

引用

ENERGIES 2021年第11期14卷 3046页

作者： Difronzo, Michele Biswas, Md Multan Milton, Matthew Ginn, Herbert L. Benigni, Andrea Univ South Carolina Coll Engn & Comp 301 Main St Columbia SC 29208 USA Rhein Westfal TH Aachen Chair Methods Simulating Energy Syst D-52062 Aachen Germany Forschungszentrum Juelich Inst Energy & Climate Res Energy Syst Engn IEK 10 D-52428 Julich Germany

In this paper we present an approach for real-time simulation and Hardware-in-the-Loop (HIL) testing of Modular Multilevel Converters (MMCs) that rely on switching models while supporting system level analysis. Using the Latency Based Linear Multistep Compound (LB-LMC) approach, we achieved a 50 ns simulation time step for systems composed of several MMC converters and for converters of various complexity. To facilitate system level testing, we introduce the use of a serial communication-based (Aurora) interface for HIL testing of MMC converters and we analyzed the effect that communication latency has on the accuracy of the HIL test. The simulation and HIL results are validated against an MMC laboratory prototype.

关键词： Field Programmable Gate Arrays (FPGAs) switching converters Modular Multilevel Converters (MMCs) parallel algorithms real-time systems power system simulation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：