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

International Conference on High Performance Computing & Simulation (HPCS)

作者： Myoupo, Jean Frederic Ngomade, Armel Nkonjoh Tchendji, Vianney Kengne Univ Picardie Jules Verne Comp Sci Lab MIS Amiens France Univ Dschang Dept Math & Comp Sci Dschang Cameroon

ISBN: (纸本)9781538678794

In this paper, new parallel algorithms based on the Coarse-Grained Multicomputer (CGM) model for solving the Longest Common Subsequence (LCS) problem with a string exclusion constraint (STR-EC-LCS) is presented. Based on a previous sequential algorithm, we propose two CGM parallel algorithms for STR-EC-LCS problem. We perform an experimental study of our two solutions to validate our theoretical predictions, and conclude that our first algorithm that minimizes idleness of the processors is better than the second. To the best of our knowledge, these algorithms are the first CGMbased parallel algorithms for the generalized-constrained-LCS problem.

关键词： parallel algorithms Constrained Longest Common Subsequence Dynamic Programming Coarse-Grained Multicomputer

来源：评论

学校读者我要写书评

暂无评论

A multilevel approach for the performance analysis of parallel algorithms

arXiv

引用

arXiv 2019年

作者： D'Amore, L. Mele, V. Romano, D. Laccetti, G. University of Naples Federico II Naples Italy CNR Naples Italy

We provide a multilevel approach for analysing performances of parallel algorithms. The main outcome of such approach is that the algorithm is described by using a set of operators which are related to each other according to the problem decomposition. Decomposition level determines the granularity of the algorithm. A set of block matrices (decomposition and execution) highlights fundamental characteristics of the algorithm, such as inherent parallelism and sources of overheads. Copyright © 2019, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for Generating Random Networks with Given Degree Sequences

引用

INTERNATIONAL JOURNAL OF parallel PROGRAMMING 2017年第1期45卷 109-127页

作者： Alam, Maksudul Khan, Maleq Virginia Tech Virginia Bioinformat Inst Dept Comp Sci Blacksburg VA 24061 USA Virginia Tech Virginia Bioinformat Inst Network Dynam & Simulat Sci Lab Blacksburg VA 24061 USA

Random networks are widely used for modeling and analyzing complex processes. Many mathematical models have been proposed to capture diverse real-world networks. One of the most important aspects of these models is degree distribution. Chung-Lu (CL) model is a random network model, which can produce networks with any given arbitrary degree distribution. The complex systems we deal with nowadays are growing larger and more diverse than ever. Generating random networks with any given degree distribution consisting of billions of nodes and edges or more has become a necessity, which requires efficient and parallel algorithms. We present an MPI-based distributed memory parallel algorithm for generating massive random networks using CL model, which takes time with high probability and O(n) space per processor, where n, m, and P are the number of nodes, edges and processors, respectively. The time efficiency is achieved by using a novel load-balancing algorithm. Our algorithms scale very well to a large number of processors and can generate massive power-law networks with one billion nodes and 250 billion edges in one minute using 1024 processors.

关键词： Massive Networks parallel algorithms Network Generator

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for islanded microgrid with photovoltaic and energy storage systems planning optimization problem: Material selection and quantity demand optimization

引用

COMPUTER PHYSICS COMMUNICATIONS 2017年 211卷 45-53页

作者： Cao, Yang Liu, Chun Huang, Yuehui Wang, Tieqiang Sun, Chenjun Yuan, Yue Zhang, Xinsong Wu, Shuyun Hohai Univ Coll Energy & Elect Engn Nanjing Jiangsu Peoples R China China Elect Power Res Inst Beijing Peoples R China State Grid Hebei Elect Power Co Shijiazhuang Peoples R China Nantong Univ Coll Elect Engn Nantong Peoples R China

With the development of roof photovoltaic power (PV) generation technology and the increasingly urgent need to improve supply reliability levels in remote areas, islanded microgrid with photovoltaic and energy storage systems (IMPE) is developing rapidly. The high costs of photovoltaic panel material and energy storage battery material have become the primary factors that hinder the development of IMPE. The advantages and disadvantages of different types of photovoltaic panel materials and energy storage battery materials are analyzed in this paper, and guidance is provided on material selection for IMPE planners. The time sequential simulation method is applied to optimize material demands of the IMPE. The model is solved by parallel algorithms that are provided by a commercial solver named CPLEX. Finally, to verify the model, an actual IMPE is selected as a case system. Simulation results on the case system indicate that the optimization model and corresponding algorithm is feasible. Guidance for material selection and quantity demand for IMPEs in remote areas is provided by this method. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Islanded microgrid with photovoltaic and energy storage systems Material selection Quantity demand optimization Time sequential simulation method parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for switching edges in heterogeneous graphs

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2017年 104卷 19-35页

作者： Bhuiyan, Hasanuzzaman Khan, Maleq Chen, Jiangzhuo Marathe, Madhav Virginia Tech Dept Comp Sci 2202 Kraft Dr Blacksburg VA 24061 USA Texas A&M Univ Dept Elect Engn & Comp Sci Kingsville TX 78363 USA Virginia Tech Biocomplex Inst Network Dynam & Simulat Sci Lab 1015 Life Sci Circle Blacksburg VA 24061 USA

An edge switch is an operation on a graph (or network) where two edges are selected randomly and one of their end vertices is swapped with each other. Edge switch operations have important applications in graph theory and network analysis, such as in generating random networks with a given degree sequence, modeling and analyzing dynamic networks, and in studying various dynamic phenomena over a network. The recent growth of real-world networks motivates the need for efficient parallel algorithms. The dependencies among successive edge switch operations and the requirement to keep the graph simple (i.e., no self-loops or parallel edges) as the edges are switched lead to significant challenges in designing a parallel algorithm. Addressing these challenges requires complex synchronization and communication among the processors leading to difficulties in achieving a good speedup by parallelization. In this paper, we present distributed memory parallel algorithms for switching edges in massive networks. These algorithms provide good speedup and scale well to a large number of processors. A harmonic mean speedup of 73.25 is achieved on eight different networks with 1024 processors. One of the steps in our edge switch algorithms requires the computation of multinomial random variables in parallel. This paper presents the first non-trivial parallel algorithm for the problem, achieving a speedup of 925 using 1024 processors. Published by Elsevier Inc.

关键词： Edge switch Random network generation Network dynamics Multinomial distribution parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel algorithms for error correction and transcriptome assembly of biological sequences

Efficient parallel algorithms for error correction and trans...

引用

作者： Sachdeva, Vipin Georgia Institute of Technology

学位级别：博士

Next-generation sequencing technologies have led to a big data age in biology. Since the sequencing of the human genome, the primary bottleneck has steadily moved from collection to storage and analysis of the data. The primary contributions of this dissertation are design and implementation of novel parallel algorithms for two important problems in bioinformatics – error-correction and transcriptome assembly. For error-correction, we focused on k-mer spectrum based error-correction application called Reptile. We designed a novel distributed memory algorithm that divided the k-mer and tiles amongst the processing ranks. This allows any hardware with any memory size per node to be employed for error-correction using Reptile's algorithm, irrespective of the size of the dataset. Our implementational achieved highly scalable results for E. Coli, Drosophila as well as the human datasets which consisted of 1.55 billion reads. Besides an algorithm that distributes k-mers and tiles between ranks, we have also implemented numerous heuristics that are useful to adjust the algorithm based on the hardware traits. We also implemented an extension of our parallel algorithm further by using pre-generating tiles and using collective messages to reduce the number of point to point messages for error-correction. Further extensions of this work have focused to create a library for distributed k-mer processing which has applications to problems in metagenomics. For transcriptome assembly, we have implemented a hybrid MPI-OpenMP approach for Chrysalis, which is part of the Trinity pipeline. Chrysalis clusters minimally overlapping contigs obtained from the prior module in Trinity called Inchworm. With this parallelization, we were able to reduce the runtime of the Chrysalis step of the Trinity workflow from over 50 hours to less than 5 hours for the sugarbeet dataset. We also employed this implementation to complete transcriptome of a 1.5 billion reads dataset pooled from different brea

关键词： HPC parallel algorithms Transcriptome assembly Error correction

来源：评论

学校读者我要写书评

暂无评论

New distributed algorithms in almost mixing time via transformations from parallel algorithms 32

New distributed algorithms in almost mixing time via transfo...

引用

32nd International Symposium on Distributed Computing, DISC 2018

作者： Ghaffari, Mohsen Li, Jason ETH Zurich Switzerland Carnegie Mellon University United States

ISBN: (纸本)9783959770927

We show that many classical optimization problems – such as (1 ± )-approximate maximum flow, shortest path, and transshipment – can be computed in τmix(G)·no(1) rounds of distributed message passing, where τmix(G) is the mixing time of the network graph G. This extends the result of Ghaffari et al. [PODC’17], whose main result is a distributed MST algorithm in τmix(G)· 2O(log n log log n) rounds in the CONGEST model, to a much wider class of optimization problems. For many practical networks of interest, e.g., peer-to-peer or overlay network structures, the mixing time τmix(G) is small, e.g., polylogarithmic. On these networks, our algorithms bypass the Ω( n + D) lower bound of Das Sarma et al. [STOC’11], which applies for worst-case graphs and applies to all of the above optimization problems. For all of the problems except MST, this is the first distributed algorithm which takes o(n) rounds on a (nontrivial) restricted class of network graphs. Towards deriving these improved distributed algorithms, our main contribution is a general transformation that simulates any work-efficient PRAM algorithm running in T parallel rounds via a distributed algorithm running in T · τmix(G) · 2O(log n) rounds. Work- and time-efficient parallel algorithms for all of the aforementioned problems follow by combining the work of Sherman [FOCS’13, SODA’17] and Peng and Spielman [STOC’14]. Thus, simulating these parallel algorithms using our transformation framework produces the desired distributed algorithms. The core technical component of our transformation is the algorithmic problem of solving multi-commodity routing – that is, roughly, routing n packets each from a given source to a given destination – in random graphs. For this problem, we obtain a new algorithm running in 2O(log n) rounds, improving on the 2O(log n log log n) round algorithm of Ghaffari, Kuhn, and Su [PODC’17]. As a consequence, for the MST problem in particular, we obtain an improved distributed algorithm running

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma

Deterministic parallel algorithms for fooling polylogarithmi...

引用

作者： Harris, David G. Department of Computer Science University of Maryland A.V. Williams Building 8223 Paint Branch Drive College ParkMD20742 United States

Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low (almost-) independence. A series of papers, beginning with Luby (1993) and continuing with Berger and Rompel (1991) and Chari et al. (2000), showed that these techniques can be combined to give deterministic parallel algorithms for combinatorial optimization problems involving sums of w-juntas. We improve these algorithms through derandomized variable partitioning, reducing the processor complexity to essentially independent of w and time complexity to linear in w. As a key subroutine, we give a new algorithm to generate a probability space which can fool a given set of neighborhoods. Schulman (1992) gave an NC algorithm to do so for neighborhoods of size w ≤ O(log n). Our new algorithm is in NC1, with essentially optimal time and processor complexity, when w = O(log n);it remains in NC up to w = polylog(n). This answers an open problem of Schulman. One major application of these algorithms is an NC algorithm for the Lovász Local Lemma. Previous NC algorithms, including the seminal algorithm of Moser and Tardos (2010) and the work of Chandrasekaran et. al (2013), required that (essentially) the bad-events could span only O(log n) variables;we relax this to polylog(n) variables. We use this for an NC2 algorithm for defective vertex coloring, which works for arbitrary degree graphs. © 2018 ACM.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for an Implicit CFD Solver on Tree-Based Grids 14th

引用

14th International Conference on parallel Computing Technologies (PaCT)

作者： Pavlukhin, Pavel Menshov, Igor Keldysh Inst Appl Math Moscow 125047 Russia Res & Dev Inst Kvant Moscow 125438 Russia

ISBN: (纸本)9783319629322;9783319629315

parallel implementation of the implicit LU-SGS solver is considered. It leads to the graph coloring problem. A novel recursive graph coloring algorithm has been proposed that requires only three colors on 2: 1 balanced quadtree-based meshes. The algorithm has been shown to allow simple parallel implementations, including GPU architectures, and is fully coherent with local grid coarsing/refining procedures resulting in highly effective co-execution with local grid adaptation.

关键词： CFD CUDA LU-SGS Implicit schemes parallel algorithms Tree-based grids AMR

来源：评论

学校读者我要写书评

暂无评论

parallel algorithms for the Computation of Cycles in Relative Neighborhood Graphs 46

Parallel Algorithms for the Computation of Cycles in Relativ...

引用

46th International Conference on parallel Processing Workshops (ICPPW)

作者： Sundar, Hari Khurd, Parmeshwar Univ Utah Sch Comp Salt Lake City UT 84112 USA Netflix Inc Scotts Valley CA USA

ISBN: (纸本)9781538610428

We present parallel algorithms for computing cycle orders and cycle perimeters in relative neighborhood graphs. This parallel algorithm has wide-ranging applications from microscopic to macroscopic domains, e.g., in histopathological image analysis and wireless network routing. Our algorithm consists of the following steps (sub-algorithms): (1) Uniform partitioning of the graph vertices across processes, (2) parallel Delaunay triangulation and (3) parallel computation of the relative neighborhood graph and the cycle orders and perimeters. We evaluated our algorithm on a large dataset with 6.5 Million points and demonstrate excellent fixed-size scalability. We also demonstrate excellent isogranular scalability up to 131K processes. Our largest run was on a dataset with 13 billion points on 131K processes on ORNL's Cray XK7 "Titan" supercomputer.

关键词： Feature extraction Partitioning algorithms parallel algorithms Wireless networks Microscopy Scalability Three-dimensional displays

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：