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

International Conference for High Performance Computing, Networking, Storage and Analysis (HPC)

作者： Selvitopi, Oguz Ekanayake, Saliya Guidi, Giulia Awan, Muaaz G. Pavlopoulos, Georgios A. Azad, Ariful Kyrpides, Nikos Oliker, Leonid Yelick, Katherine Buluc, Aydin Lawrence Berkeley Natl Lab Appl Math & Computat Res Div Berkeley CA 94720 USA Microsoft Corp Redmond WA USA Univ Calif Berkeley Berkeley CA USA Lawrence Berkeley Natl Lab NERSC Berkeley CA USA BSRC Alexander Fleming Inst Fundamental Biomed Res 34 Fleming St Vari 16672 Greece Indiana Univ Bloomington IN USA Lawrence Berkeley Natl Lab Joint Genome Inst Berkeley CA USA

ISBN: (纸本)9781665454445

Similarity search is one of the most fundamental computations that are regularly performed on ever-increasing protein datasets. Scalability is of paramount importance for uncovering novel phenomena that occur at very large scales. We unleash the power of over 20,000 GPUs on the Summit system to perform all-vs-all protein similarity search on one of the largest publicly available datasets with 405 million proteins, in less than 3.5 hours, cutting the time-to-solution for many use cases from weeks. The variability of protein sequence lengths, as well as the sparsity of the space of pairwise comparisons, make this a challenging problem in distributed memory. Due to the need to construct and maintain a data structure holding indices to all other sequences, this application has a huge memory footprint that makes it hard to scale the problem sizes. We overcome this memory limitation by innovative matrix-based blocking techniques, without introducing additional load imbalance.

关键词： High performance computing Computational biology Proteins Protein similarity search parallel algorithms Sparse matrices

来源：评论

学校读者我要写书评

暂无评论

parallel and distributed paradigms for community detection in social networks: A methodological review

引用

EXPERT SYSTEMS WITH APPLICATIONS 2022年第0期187卷 115956-115956页

作者： Naik, Debadatta Ramesh, Dharavath Gandomi, Amir H. Gorojanam, Naveen Babu Indian Inst Technol Indian Sch Mines Dept Comp Sci & Engn Dhanbad Bihar India Univ Technol Sydney Dept Engn & Informat Technol Ultimo NSW Australia

Community detection in social networks is the process of identifying the cohesive groups of similar nodes. Detection of these groups can be helpful in many applications, such as finding networks of protein interaction in biological networks, finding the users of similar mind for ads and suggestions, finding a shared research field in collaborative networks, analyzing public health, future link prediction in social networks, analyzing criminology, and many more. However, with the increase in the number of profiles and content shared on social media platforms, the analysis is often time-consuming and exhaustive. In order to speed up and optimize the community detection process, parallel processing and Shared/Distributed memory techniques are widely used. Despite community detection has widespread use in social networks, no attempt has ever been made to compile and systematically discuss research efforts on the emerging subject of identifying parallel and distributed methods for community detection in social networks. Most of the surveys described the serial algorithms used for community detection. Our survey work comes under the scope of new design techniques, exciting or novel applications, components or standards, and applications of an educational, transactional, and co-operational nature. This paper accommodates and presents a systematic literature review with state-of-the-art research on the application of parallel processing and Shared/Distributed techniques to determine communities for social network analysis. Advanced search strategy has been performed on several digital libraries for extracting several studies for the review. The systematic search landed in finding 3220 studies, among which 65 relevant studies are selected after conducting various screening phases for further review. The application of parallel computing, shared memory, and distributed memory on the existing community detection methodologies have been discussed thoroughly. More specifically,

关键词： Social Networks Community Detection parallel algorithms Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

PPBT: A High Performance parallel Search Tree 28

PPBT: A High Performance Parallel Search Tree

引用

28th Annual IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC)

作者： Guan, Jiawen Fan, Rui ShanghaiTech Univ Shanghai Peoples R China

ISBN: (纸本)9781665410168

Search trees are one of the most important and widely used data structures, and parallelization is an effective method to improve their performance. However, many existing parallel search trees incur high synchronization costs and low memory I/O efficiency, which limits their performance. We propose PPBT, a batched parallel search tree which minimizes synchronization by partitioning the tree using novel algorithms and minimizing I/O cost using buffering. We give a new sequential algorithm for batch processing on search trees with optimal I/O efficiency for insert and delete operations, and also present a fast parallel algorithm for joining disjoint search trees. We show experimentally that PPBT is over 6x faster than the state-of-the-art parallel tree in [1] and over 40x faster than the concurrent search tree in [7], and achieves 21x speedup using 32 threads. PPBT's throughput on searches is lower due to reduced opportunities for buffering, but is still 1.3x that of [1]. In addition, PPBT has good response times for searches, for example completing 100K searches in under 1 ms in a tree with 10M elements.

关键词： parallel algorithms data structures search tree cache efficiency

来源：评论

学校读者我要写书评

暂无评论

Local Mending 1

引用

29th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Balliu, Alkida Hirvonen, Juho Melnyk, Darya Olivetti, Dennis Rybicki, Joel Suomela, Jukka Gran Sasso Sci Inst Laquila Italy Aalto Univ Espoo Finland IST Austria Klosterneuburg Austria

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to "patch a hole." We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log* n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Pi can be solved in O(log* n), there is always a restriction. Pi' subset of Pi that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Theta(log n), or Theta(n), while in general graphs the structure is much more diverse.

关键词： Mendability Fault tolerance LCL problems Distributed algorithms parallel algorithms Dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Poster: The Problem-Based Benchmark Suite PBBS), V2 27

Poster: The Problem-Based Benchmark Suite PBBS), V2

引用

27th ACM SIGPLAN Symposium on Principles and Practice of parallel Programming (PPoPP)

作者： Anderson, Daniel Blelloch, Guy E. Dhulipala, Laxman Dobson, Magdalen Sun, Yihan Carnegie Mellon Univ Pittsburgh Pittsburgh PA USA Univ Maryland Coll Park MD USA UC Riverside Riverside Riverside CA USA

ISBN: (纸本)9781450392044

The Problem-Based Benchmark Suite (PBBS) is a set of benchmark problems designed for comparing algorithms, implementations and platforms. For each problem, the suite defines the problem in terms of the input-output relationship, and supplies a set of input instances along with input generators, a default implementation, code for checking correctness or accuracy, and a timing harness. The suite makes it possible to compare different algorithms, platforms (e.g. CPU vs CPU), and implementations using different programming languages or libraries. The purpose is to better understand how well a wide variety of problems parallelize, and what techniques/algorithms are most effective. The suite was first announced in 2012 with 14 benchmark problems. Here we describe some significant updates. In particular, we have added nine new benchmarks from a mix of problems in text processing, computational geometry and machine learning. We have further optimized the default implementations;several are the fastest available for multicore CPUs, often achieving near perfect speedup on the 72 core machine we test them on. The suite now also supplies significantly larger default test instances, as well as a broader variety, with many derived from real-world data.

关键词： benchmarking parallel algorithms performance

来源：评论

学校读者我要写书评

暂无评论

Beyond worst-case analysis Observed low depth for a P-complete problem 13

Beyond worst-case analysis Observed low depth for a P-comple...

引用

13th International Workshop on Programming Models and Applications for Multicores and Manycores (PMAM) part of PPoPP Conference

作者： Vishkin, Uzi Univ Maryland College Pk MD 20742 USA

ISBN: (纸本)9781450393393

The performance of a simple parallel algorithm for 3CNF Horn-SAT is observed. The algorithm requires linear work. The algorithm also exhibits low parallel time ("depth") for central Horn-SAT formulae benchmarks. The work optimality of the algorithm, its observed low depth, P-completeness of the problem and algorithm-specific modeling put together demonstrate a way for going beyond worst-case for parallel algorithms. The questioning of the near exclusivity of the worst-case analysis mode in typical algorithms courses has received considerable attention recently for a broad range of algorithms. The current paper suggests a new line, unique to parallel algorithms, for questioning the worst-case analysis mode, dramatically undermining the broad perception that a P-completeness result is nothing short of "a nightmare for parallel processing", as phrased in an authoritative textbook.

关键词： parallel algorithms P-Completeness Beyond worst-case

来源：评论

学校读者我要写书评

暂无评论

parallel Filtered Graphs for Hierarchical Clustering

arXiv

引用

arXiv 2023年

作者： Yu, Shangdi Shun, Julian MIT CSAIL

Given all pairwise weights (distances) among a set of objects, filtered graphs provide a sparse representation by only keeping an important subset of weights. Such graphs can be passed to graph clustering algorithms to generate hierarchical clusters. In particular, the directed bubble hierarchical tree (DBHT) algorithm on filtered graphs has been shown to produce good hierarchical clusters for time series data. We propose a new parallel algorithm for constructing triangulated maximally filtered graphs (TMFG), which produces valid inputs for DBHT, and a scalable parallel algorithm for generating DBHTs that is optimized for TMFG inputs. In addition to parallelizing the original TMFG construction, which has limited parallelism, we also design a new algorithm that inserts multiple vertices on each round to enable more parallelism. We show that the graphs generated by our new algorithm have similar quality compared to the original TMFGs, while being much faster to generate. Our new parallel algorithms for TMFGs and DBHTs are 136–2483x faster than state-of-the-art implementations, while achieving up to 41.56x self-relative speedup on 48 cores with hyper-threading, and achieve better clustering results compared to the standard average-linkage and complete-linkage hierarchical clustering algorithms. We show that on a data set, our algorithms produce clusters that align well with human experts’ classification. Copyright © 2023, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for the concurrent atomistic-continuum methodology

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2022年 463卷 1页

作者： Diaz, Adrian Gu, Boyang Li, Yang Plimpton, Steven J. McDowell, David L. Chen, Youping Univ Florida Dept Mech & Aerosp Engn Gainesville FL 32611 USA Sandia Natl Labs Albuquerque NM 87185 USA Georgia Inst Technol Woodruff Sch Mech Engn Atlanta GA 30332 USA Georgia Inst Technol Sch Mat Sci & Engn Atlanta GA 30332 USA

In this work we present a parallel algorithm for the Concurrent Atomistic Continuum (CAC) formulation that can be integrated into existing molecular dynamics codes. The CAC methodology is briefly introduced and its parallel implementation in LAMMPS is detailed and then demonstrated through benchmarks that compare CAC simulation results with corresponding all-MD (molecular dynamics) results. The parallel efficiency of the algorithm is demonstrated when simulating systems represented by both atoms and finite elements. The verification benchmarks include dynamic crack propagation and branching in a Si single crystal, wave propagation and scattering in a Si phononic crystal, and phonon transport through the phase interface in a PbTe/PbSe heteroepitaxial system. In each of these benchmarks the CAC algorithm is shown to be in good agreement with MD-only models. This parallel CAC algorithm thus offers one of the first scalable multiscale material simulation methodologies that relies solely on atomic-interaction models. (c) 2022 Published by Elsevier Inc.

关键词： Concurrent atomistic-continuum method Molecular dynamics Nonequilibrium processes parallel algorithms LAMMPS

来源：评论

学校读者我要写书评

暂无评论

MatPIM: Accelerating Matrix Operations with Memristive Stateful Logic

MatPIM: Accelerating Matrix Operations with Memristive State...

引用

IEEE International Symposium on Circuits and Systems (ISCAS)

作者： Leitersdorf, Orian Ronen, Ronny Kvatinsky, Shahar Technion Israel Inst Technol Viterbi Fac Elect & Comp Engn Haifa Israel

ISBN: (纸本)9781665484855

The emerging memristive Memory Processing Unit (mMPU) overcomes the memory wall through memristive devices that unite storage and logic for real processing-in-memory (PIM) systems. At the core of the mMPU is stateful logic, which is accelerated with memristive partitions to enable logic with massive inherent parallelism within crossbar arrays. This paper vastly accelerates the fundamental operations of matrix-vector multiplication and convolution in the mMPU, with either fullprecision or binary elements. These proposed algorithms establish an efficient foundation for large-scale mMPU applications such as neural-networks, image processing, and numerical methods. We overcome the inherent asymmetry limitation in the previous in-memory full-precision matrix-vector multiplication solutions by utilizing techniques from block matrix multiplication and reduction. We present the first fast in-memory binary matrixvector multiplication algorithm by utilizing memristive partitions with a tree-based popcount reduction ( 39x faster than previous work). For convolution, we present a novel in-memory inputparallel concept which we utilize for a full-precision algorithm that overcomes the asymmetry limitation in convolution, while also improving latency (2x faster than previous work), and the first fast binary algorithm (12x faster than previous work).

关键词： Memristor processing-in-memory parallel algorithms matrix multiplication convolution

来源：评论

学校读者我要写书评

暂无评论

A class of parallel doubly stochastic algorithms for large-scale learning

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2020年第1期21卷 4718-4768页

作者： Aryan Mokhtari Alec Koppel Martin Takáč Alejandro Ribeiro Department of Electrical and Computer Engineering The University of Texas at Austin Austin TX Computational and Information Sciences Directorate U.S. Army Research Laboratory Adelphi MD Industrial and Systems Engineering Lehigh University Bethlehem PA Department of Electrical and Systems Engineering University of Pennsylvania Philadelphia PA

We consider learning problems over training sets in which both, the number of training examples and the dimension of the feature vectors, are large. To solve these problems we propose the random parallel stochastic algorithm (RAPSA). We call the algorithm random parallel because it utilizes multiple parallel processors to operate on a randomly chosen subset of blocks of the feature vector. RAPSA is doubly stochastic since each processor utilizes a random set of functions to compute the stochastic gradient associated with a randomly chosen sets of variable coordinates. algorithms that are parallel in either of these dimensions exist, but RAPSA is the first attempt at a methodology that is parallel in both the selection of blocks and the selection of elements of the training set. In RAPSA, processors utilize the randomly chosen functions to compute the stochastic gradient component associated with a randomly chosen block. The technical contribution of this paper is to show that this minimally coordinated algorithm converges to the optimal classifier when the training objective is strongly convex. Moreover, we present an accelerated version of RAPSA (ARAPSA) that incorporates the objective function curvature information by premultiplying the descent direction by a Hessian approximation matrix. We further extend the results for asynchronous settings and show that if the processors perform their updates without any coordination the algorithms are still convergent to the optimal argument. RAPSA and its extensions are then numerically evaluated on a linear estimation problem and a binary image classification task using the MNIST handwritten digit dataset.

关键词： stochastic optimization large-scale learning asynchronous methods parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：