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

Flexible and scalable Particle-in-Cell Methods With Adaptive Mesh Refinement for Geodynamic Computations

GEOCHEMISTRY GEOPHYSICS GEOSYSTEMS 2018年第9期19卷 3596-3604页

作者： Gassmoller, Rene Lokavarapu, Harsha Heien, Eric Puckett, Elbridge Gerry Bangerth, Wolfgang Univ Calif Davis Dept Earth & Phys Sci Davis CA 95616 USA Univ Calif Davis Computat Infrastruct Geodynam Davis CA 95616 USA Univ Calif Davis Dept Math Davis CA 95616 USA Colorado State Univ Dept Math Ft Collins CO 80523 USA

Particle-in-cell (PIC) methods couple mesh-based methods for the solution of continuum mechanics problems with the ability to advect and evolve properties on particles. PIC methods have a long history and numerous applications in geodynamic modeling. However, they are historically either implemented in sequential codes or in parallel codes with structured, statically partitioned meshes. Yet today's codes increasingly use adaptive mesh refinement (AMR) of unstructured coarse meshes, dynamic repartitioning, and scale to thousands of processors. Optimally balancing the work per processor for a PIC method in these environments is a difficult problem, and many existing implementations are not sufficient for this task. Thus, there is a need to revisit these algorithms for future applications. Here we describe challenges and solutions to implement PIC methods in the context of large-scale parallel geodynamic modeling codes that use dynamically changing meshes. We also provide guidance for how to address bottlenecks that impede the efficient implementation of these algorithms and demonstrate with numerical tests that our algorithms can be implemented with optimal complexity and that they are suitable for large-scale, practical applications. We provide a reference implementation in the Advanced Solver for Problems in Earth's ConvecTion (ASPECT), an open source code for geodynamic modeling built on the *** finite element library.

关键词： Particle in cell method Adaptive mesh refinement Geodynamic software Numerical modeling High performance computing scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

Accurate, Fast and scalable Kernel Ridge Regression on Parallel and Distributed Systems 18

Accurate, Fast and Scalable Kernel Ridge Regression on Paral...

引用

32nd International Conference on Supercomputing (ICS)

作者： You, Yang Demmel, James Hsieh, Cho-Jui Vuduc, Richard Univ Calif Berkeley Berkeley CA 94720 USA Univ Calif Davis Davis CA USA Georgia Tech Atlanta GA USA

ISBN: (纸本)9781450357838

Kernel Ridge Regression (KRR) is a fundamental method in machine learning. Given an n-by-d data matrix as input, a traditional implementation requires Theta(n(2)) memory to form an n-by-n kernel matrix and Theta(n(3)) flops to compute the final model. These time and storage costs prohibit KRR from scaling up to large datasets. For example, even on a relatively small dataset (a 520k-by-90 input requiring 357 MB), KRR requires 2 TB memory just to store the kernel matrix. The reason is that n usually is much larger than d for real-world applications. On the other hand, weak scaling becomes a problem: if we keep d and n/p fixed as p grows (p is machines), the memory needed grows as Theta(p) per processor and the flops as Theta(p(2)) per processor. In the perfect weak scaling situation, both the memory needed and the flops grow as T(1) per processor (i.e. memory and flops are constant). The traditional Distributed KRR implementation (DKRR) only achieved 0.32% weak scaling efficiency from 96 to 1536 processors. We propose two new methods to address these problems: the Balanced KRR (BKRR) and K-means KRR (KKRR). These methods consider alternative ways to partition the input dataset into p different parts, generating p different models, and then selecting the best model among them. Compared to a conventional implementation, KKRR2 (optimized version of KKRR) improves the weak scaling efficiency from 0.32% to 38% and achieves a 591x speedup for getting the same accuracy by using the same data and the same hardware (1536 processors). BKRR2 (optimized version of BKRR) achieves a higher accuracy than the current fastest method using less training time for a variety of datasets. For the applications requiring only approximate solutions, BKRR2 improves the weak scaling efficiency to 92% and achieves 3505x speedup (theoretical speedup: 4096x).

关键词： Distributed Machine Learning scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

Host Profit Maximization for Competitive Viral Marketing in Billion-Scale Networks

Host Profit Maximization for Competitive Viral Marketing in ...

引用

37th IEEE Conference on Computer Communications (IEEE INFOCOM)

作者： Zhu, Yuqing Li, Deying Calif State Univ Los Angeles Dept Comp Sci Los Angeles CA 90032 USA Renmin Univ China Sch Informat Beijing Peoples R China

ISBN: (纸本)9781538641286

We study the problem to maximize the profit for a social network host who offers viral marketing to multiple company campaigners. Each campaigner has its special interest for social network users, and she pays the host commission when a target user adopts her product. The campaigners decide the cost they are willing to pay for viral marketing, and the host collects cost from all campaigners and uses it for marketing. We call our optimization problem Competitive PROfit maximization for the host (CPro), and its solution is the seed allocation for campaigners, such that the profit (commission) campaigners given hack to the host is maximized. CPro is NP-hard with a non-monotone and non-submodular objective function, which means existing techniques in influence or profit maximization cannot give guaranteed performance. To solve this issue, we design an efficient approximation algorithm that works on billion-scale networks, and more importantly, we give the performance hound of our algorithm. As far as we know, this is the first bounded scalable approximation algorithm for competitive profit maximization. A comprehensive set of experiments are set on various real networks with up to several billion edges from diverse disciplines, and our solution identifies the top choices for the host in only a few minutes on network that contains 1.5 billion edges.

关键词： scalable algorithm Profit Maximization Competitive influence Viral Marketing

来源：评论

学校读者我要写书评

暂无评论

SSDMiner: A scalable and Fast Disk-Based Frequent Pattern Miner 7th

SSDMiner: A Scalable and Fast Disk-Based Frequent Pattern Mi...

引用

7th International Conference on Emerging Databases - Technologies, Applications, and Theory (EDB)

作者： Chon, Kang-Wook Kim, Min-Soo DGIST Daegu South Korea

ISBN: (纸本)9789811065200;9789811065194

Frequent itemset mining is widely used as a fundamental data mining technique. Recently, there have been proposed a number of disk-based methods. However, the existing methods still do not have a good scalability due to large-scale intermediate data and non-trivial disk I/Os. We propose SSDMiner, a new fast and scalable disk-based method for frequent itemset mining that is based on Apriori-like method and has no intermediate data and small disk I/O overheads by exploiting SSD. We propose a concept of bitmap chunks for storing transactional database in disks and a fast support counting based on bitmap chunks. Through experiments, we demonstrate that SSDMiner has the enhanced scalability and the good performance similar to that in memory-based methods with robustness.

关键词： Frequent pattern mining scalable algorithm SSD Disk-based algorithm

来源：评论

学校读者我要写书评

暂无评论

Enumerating Trillion Subgraphs On Distributed Systems

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2018年第6期12卷 71-71页

作者： Park, Ha-Myung Silvestri, Francesco Pagh, Rasmus Chung, Chin-Wan Myaeng, Sung-Hyon Kang, U. Korea Adv Inst Sci & Technol Daejeon South Korea Univ Padua Padua Italy IT Univ Copenhagen Copenhagen Denmark Chongqing Univ Technol Chongqing Peoples R China Seoul Natl Univ Seoul South Korea

How can we find patterns from an enormous graph with billions of vertices and edges? The subgraph enumeration, which is to find patterns from a graph, is an important task for graph data analysis with many applications, including analyzing the social network evolution, measuring the significance of motifs in biological networks, observing the dynamics of Internet, and so on. Especially, the triangle enumeration, a special case of the subgraph enumeration, where the pattern is a triangle, has many applications such as identifying suspicious users in social networks, detecting web spams, and finding communities. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks;however, they suffer from the massive shuffled data resulting in a very long processing time. In this article, we propose scalable methods for enumerating trillion subgraphs on distributed systems. We first propose PTE (Pre-partitioned Triangle Enumeration), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read. We also propose PSE (Pre-partitioned Subgraph Enumeration), a generalized version of PTE for enumerating subgraphs that match an arbitrary query graph. Experimental results show that PTE provides 79 times faster performance than recent distributed algorithms on real-world graphs, and succeeds in enumerating more than 3 trillion triangles on the ClueWeb12 graph with 6.3 billion vertices and 72 billion edges. Furthermore, PSE successfully enumerates 265 trillion clique subgraphs with 4 vertices from a subdomain hyperlink network, showing 47 times faster performance than the state of the art distributed subgraph enumeration algor

关键词： Triangle enumeration subgraph enumeration big data graph algorithm scalable algorithm distributed algorithm network analysis

来源：评论

学校读者我要写书评

暂无评论

Influential Node Tracking on Dynamic Social Network: An Interchange Greedy Approach

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2017年第2期29卷 359-372页

作者： Song, Guojie Li, Yuanhao Chen, Xiaodong He, Xinran Tang, Jie Peking Univ Key Lab Machine Percept Beijing 100871 Peoples R China Univ Southern Calif Dept Comp Sci Los Angeles CA 90089 USA Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China

As both social network structure and strength of influence between individuals evolve constantly, it requires tracking the influential nodes under a dynamic setting. To address this problem, we explore the Influential Node Tracking (INT) problem as an extension to the traditional Influence Maximization problem (IM) under dynamic social networks. While the Influence Maximization problem aims at identifying a set of k nodes to maximize the joint influence under one static network, the INT problem focuses on tracking a set of influential nodes that keeps maximizing the influence as the network evolves. Utilizing the smoothness of the evolution of the network structure, we propose an efficient algorithm, Upper Bound Interchange Greedy (UBI) and a variant, UBI+. Instead of constructing the seed set from the ground, we start from the influential seed set we found previously and implement node replacement to improve the influence coverage. Furthermore, by using a fast update method by calculating the marginal gain of nodes, our algorithm can scale to dynamic social networks with millions of nodes. Empirical experiments on three real large-scale dynamic social networks show that our UBI and its variants, UBI+ achieves better performance in terms of both influence coverage and running time.

关键词： Influence maximization influential nodes tracking social network scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

Single- and multi-level network sparsification by algebraic distance

引用

JOURNAL OF COMPLEX NETWORKS 2017年第3期5卷 352-388页

作者： John, Emmanuel Safro, Ilya Clemson Univ Sch Comp 821 McMillan Rd Clemson SC 29634 USA

Network sparsification methods play an important role in modern network analysis when fast estimation of computationally expensive properties (such as the diameter, centrality indices and paths) is required. We propose a method of network sparsification that preserves a wide range of structural properties. Depending on the analysis goals, the method allows to distinguish between local and global range edges that can be filtered out during the sparsification. First we rank edges by their algebraic distances and then we sample them. We also introduce a multilevel framework for sparsification that can be used to control the sparsification process at various coarse-grained resolutions. Based primarily on the matrix-vector multiplications, our method is easily parallelized for different architectures.

关键词： networks sparsification multilevel methods software scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

Scaling Deep Learning on GPU and Knights Landing clusters 17

Scaling Deep Learning on GPU and Knights Landing clusters

引用

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

作者： You, Yang Buluc, Aydin Demmel, James Univ Calif Berkeley Comp Sci Div Berkeley CA 94720 USA LBNL Comp Sci Div Berkeley CA USA Univ Calif Berkeley Berkeley CA USA

ISBN: (数字)9781450351140

ISBN: (纸本)9781450351140

Training neural networks has become a big bottleneck. For example, training ImageNet dataset on one Nvidia K20 GPU needs 21 days. To speed up the training process, the current deep learning systems heavily rely on the hardware accelerators. However, these accelerators have limited on-chip memory compared with CPUs. We use both self-host Intel Knights Landing (KNL) clusters and multi-GPU clusters as our target platforms. From the algorithm aspect, we focus on Elastic Averaging SGD (EASGD) to design algorithms for HPC clusters. We redesign four efficient algorithms for HPC systems to improve EASGD's poor scaling on clusters. Async EASGD, Async MEASGD, and Hogwild EASGD are faster than existing counterpart methods (Async SGD, Async MSGD, and Hogwild SGD) in all comparisons. Sync EASGD achieves 5.3X speedup over original EASGD on the same platform. We achieve 91.5% weak scaling efficiency on 4253 KNL cores, which is higher than the state-of-the-art implementation.

关键词： Distributed Deep Learning Knights Landing scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

PARALLEL RANDOMIZED AND MATRIX-FREE DIRECT SOLVERS FOR LARGE STRUCTURED DENSE LINEAR SYSTEMS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2016年第5期38卷 S508-S538页

作者： Liu, Xiao Xia, Jianlin De Hoop, Maarten V. Purdue Univ Dept Math W Lafayette IN 47907 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We design efficient and distributed-memory parallel randomized direct solvers for large structured dense linear systems, including a fully matrix-free version based on matrix-vector multiplications and a partially matrix-free one. The dense coefficient matrix A has an off-diagonal low-rank structure, as often encountered in practical applications such as Toeplitz systems and discretized integral and partial differential equations. A distributed-memory parallel framework for randomized structured solution is shown. scalable adaptive randomized sampling and hierarchical compression algorithms are designed to approximate A by hierarchically semiseparable (HSS) matrices. Systematic process grid storage schemes are given for different HSS forms. Parallel hierarchical algorithms are proposed for the resulting HSS forms. As compared with existing work on parallel HSS methods, our algorithms have several remarkable advantages, including the matrix-free schemes that avoid directly using dense A, a synchronized adaptive numerical rank detection, the integration of additional structures into the HSS generators, and much more flexible choices of the number of processes. Comprehensive analysis is conducted and shows that the communication costs are significantly reduced by up to an order of magnitude. Furthermore, we improve the original matrix-free HSS construction algorithm by avoiding some instability issues and by better revealing the nested rank structures. Tests on large challenging dense discretized matrices related to three-dimensional scattering fully demonstrate the superior efficiency and scalability of the direct solvers. For example, for a 10(6) x10(6) dense discretized matrix, the partially matrix-free HSS construction takes about 4,500 seconds with 512 processes, while the solution takes only 0.63 second. The storage savings is more than 30 times. The fully matrix-free solver takes slightly longer but is more flexible and accurate.

关键词： distributed memory scalable algorithm randomized compression matrix-free direct solver HSS matrix tree structure

来源：评论

学校读者我要写书评

暂无评论

Advances in patch-based adaptive mesh refinement scalability

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2016年 89卷 65-84页

作者： Gunney, Brian T. N. Anderson, Robert W. Lawrence Livermore Natl Lab Ctr Appl Sci Comp L-561 Livermore CA 94550 USA

Patch-based structured adaptive mesh refinement (SAMR) is widely used for high-resolution simulations. Combined with modern supercomputers, it could provide simulations of unprecedented size and resolution. A persistent challenge for this combination has been managing dynamically adaptive meshes on more and more MPI tasks. The distributed mesh management scheme in SAMRAI has made some progress SAMR scalability, but early algorithms still had trouble scaling past the regime of 105 MPI tasks. This work provides two critical SAMR regridding algorithms, which are integrated into that scheme to ensure efficiency of the whole. The clustering algorithm is an extension of the tile-clustering approach, making it more flexible and efficient in both clustering and parallelism. The partitioner is a new algorithm designed to prevent the network congestion experienced by its predecessor. We evaluated performance using weak- and strong-scaling benchmarks designed to be difficult for dynamic adaptivity. Results show good scaling on up to 1.5M cores and 2M MPI tasks. Detailed timing diagnostics suggest scaling would continue well past that. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Adaptive mesh refinement Dynamic adaptivity scalable algorithm Partitioning algorithm Clustering algorithm Data locality

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：