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

Recursive and parallel constructions of independent spanning trees in alternating group networks

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY 2020年第4期5卷 234-262页

作者： Huang, Jie-Fu Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan Taiwan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Inst Med Informat Int Ctr Sci Dev Shrimp Aquaculture 1 Univ Rd Tainan 701 Taiwan Natl Cheng Kung Univ Ctr Innovat FinTech Business Models Tainan Taiwan

In this paper, we propose a recursive algorithm and a parallel algorithm for constructing independent spanning trees in ANn. The main ideas of the recursive algorithm are to construct large trees from small trees, use triangle breadth-first search (TBFS) to build a frame of an IST, and use breadth-first search (BFS) to link the rest of the nodes. The main ideas of the parallel algorithm are to build frames through TBFS in parallel, and to use the specific rules to link the rest of the nodes in parallel. We prove the correctness of both algorithms for constructing ISTs in AN(n) . Both algorithms are accurate;furthermore, the parallel algorithm is more ecient than the recursive algorithm. (An extended abstract of this paper appeared in: Jie-Fu Huang and Sun-Yuan Hsieh 'Two methods for constructing independent spanning trees in alternating group networks' Proceedings of International Conference on Creative Lifestyle Computing (ICCLC), 2020.)

关键词： Independent spanning trees alternating group networks Cayley graph recursive algorithm parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A single-tree algorithm to compute the Euclidean minimum spanning tree on GPUs 22

A single-tree algorithm to compute the Euclidean minimum spa...

引用

Proceedings of the 51st International Conference on parallel Processing

作者： Andrey Prokopenko Piyush Sao Damien Lebrun-Grandie Oak Ridge National Laboratory United States of America

ISBN: (纸本)9781450397339

Computing the Euclidean minimum spanning tree (Emst) is a computationally demanding step of many algorithms. While work-efficient serial and multithreaded algorithms for computing Emst are known, designing an efficient GPU algorithm is challenging due to a complex branching structure, data dependencies, and load imbalances. In this paper, we propose a single-tree Borůvka-based algorithm for computing Emst on GPUs. We use an efficient nearest neighbor algorithm and reduce the number of the required distance calculations by avoiding traversing subtrees with leaf nodes in the same component. The developed algorithms are implemented in a performance portable way using ArborX, an open-source geometric search library based on the Kokkos framework. We evaluate the proposed algorithm on various 2D and 3D datasets, show and compare it with the current state-of-the-art open-source CPU implementations. We demonstrate 4-24 × speedup over the fastest multi-threaded implementation. We prove the portability of our implementation by providing results on a variety of hardware: AMD EPYC 7763, Nvidia A100 and AMD MI250X. We show scalability of the implementation, computing Emst for 37 million 3D cosmological dataset in under a 0.5 second on a single A100 Nvidia GPU.

关键词： GPU parallel algorithm Euclidean minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel Cycle Search in Large Graphs 25th

Efficient Parallel Cycle Search in Large Graphs

引用

25th International Conference on Database Systems for Advanced Applications (DASFAA)

作者： Qing, Zhu Yuan, Long Chen, Zi Lin, Jingjing Ma, Guojie East China Normal Univ Shanghai Peoples R China Nanjing Univ Sci & Technol Nanjing Peoples R China

ISBN: (纸本)9783030594152;9783030594169

Cycle is a fundamental structure in graphs. Motivated by the wide applications of cycle search, namely computing the cycles related to a vertex in the graph, we investigate efficient parallel algorithm to address the cycle search problem in large graphs. We first propose a two-phase paradigm tailored for the parallel cycle search problem. Based on the paradigm, we further devise a workload estimation method to improve the efficiency and scalability of the algorithm by balancing the work assigned to different threads. We experimentally evaluate our algorithms on real datasets and the results demonstrate the effectiveness of our approach.

关键词： Cycle search parallel algorithm Graph

来源：评论

学校读者我要写书评

暂无评论

CHEAPS2AGA: Bounding Space Usage in Variance-Reduced Stochastic Gradient Descent over Streaming Data and Its Asynchronous parallel Variants 20th

CHEAPS2AGA: Bounding Space Usage in Variance-Reduced Stochas...

引用

20th International Conference on algorithms and Architectures for parallel Processing (ICA3PP)

作者： Peng, Yaqiong Fei, Haiqiang Li, Lun Ding, Zhenquan Hao, Zhiyu Chinese Acad Sci Inst Informat Engn Beijing 100093 Peoples R China

ISBN: (纸本)9783030602390;9783030602383

Stochastic Gradient Descent (SGD) is widely used to train a machine learning model over large datasets, yet its slow convergence rate can be a bottleneck. As a remarkable family of variance reduction techniques, memory algorithms such as SAG and SAGA have been proposed to accelerate the convergence rate of SGD. However, these algorithms need to store per training data point corrections in memory. The unlimited space usage feature is impractical for modern large-scale applications, especially over data points that arrive over time (referred to as streaming data in this paper). To overcome this weakness, this paper investigates the methods that bound the space usage in the state-of-the-art family of variance-reduced stochastic gradient descent over streaming data, and presents CHEAPS2AGA. At each step of updating the model, the key idea of CHEAPS2AGA is always reserving N random data points as samples, while re-using information about past stochastic gradients across all the observed data points with limited space usage. In addition, training an accurate model over streaming data requires the algorithm to be time-efficient. To accelerate the model training phase, CHEAPS2AGA embraces a lock-free data structure to insert new data points and remove unused data points in parallel, and updates the model parameters without using any locking. We conduct comprehensive experiments to compare CHEAPS2AGA to prior related algorithms suited for streaming data. The experimental results demonstrate the practical competitiveness of CHEAPS2AGA in terms of scalability and accuracy.

关键词： Machine learning Stochastic gradient descent Streaming data parallel algorithm Multicore

来源：评论

学校读者我要写书评

暂无评论

A Cloud-Based parallel Space-Saving algorithm for Big Networking Data

引用

IEEE ACCESS 2018年 6卷 45886-45898页

作者： He, Dazhong Yang, Yang Liu, Jun Beijing Univ Posts & Telecommun Ctr Data Sci Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Sch Informat & Commun Engn Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Beijing Lab Adv Informat Networks Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Beijing Key Lab Network Syst Architecture & Conve Beijing 100876 Peoples R China

As the network continues to evolve, completely analyzing the traffic requires immeasurable resources. In situations of processing enormous streaming data, the most significant k items (Top-k) are more interesting, and some streaming algorithms are deployed due to relatively limited memory and also limited processing time per item. Space-saving is such one of the most popular algorithms for computation of frequent and Top-k elements in data streams. In this paper, this algorithm is implemented in the cloud for analyzing big networking data, and an empirical formula of the counter number is derived for efficiently maintaining Top-k items. Meanwhile, easily understandable proof manner is presented to prove the merging ability of Space-saving algorithm, and some experiments are conducted to affirm the effectiveness of the algorithm.

关键词： Network traffic Top-k streaming algorithm parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Accelerating Pattern Matching Using a Novel parallel algorithm on GPUs

引用

IEEE TRANSACTIONS ON COMPUTERS 2013年第10期62卷 1906-1916页

作者： Lin, Cheng-Hung Liu, Chen-Hsiung Chien, Lung-Sheng Chang, Shih-Chieh Natl Taiwan Normal Univ Dept Technol Applicat & Human Resource Dev Taipei 106 Taiwan Natl Tsing Hua Univ Dept Math Hsinchu 30013 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30013 Taiwan

Graphics processing units (GPUs) have attracted a lot of attention due to their cost-effective and enormous power for massive data parallel computing. In this paper, we propose a novel parallel algorithm for exact pattern matching on GPUs. A traditional exact pattern matching algorithm matches multiple patterns simultaneously by traversing a special state machine called an Aho-Corasick machine. Considering the particular parallel architecture of GPUs, in this paper, we first propose an efficient state machine on which we perform very efficient parallel algorithms. Also, several techniques are introduced to do optimization on GPUs, including reducing global memory transactions of input buffer, reducing latency of transition table lookup, eliminating output table accesses, avoiding bank-conflict of shared memory, coalescing writes to global memory, and enhancing data transmission via peripheral component interconnect express. We evaluate the performance of the proposed algorithm using attack patterns from Snort V2.8 and input streams from DEFCON. The experimental results show that the proposed algorithm performed on NVIDIA GPUs achieves up to 143.16-Gbps throughput, 14.74 times faster than the Aho-Corasick algorithm implemented on a 3.06-GHz quad-core CPU with the OpenMP. The library of the proposed algorithm is publically accessible through Google Code.

关键词： Graphics processing units pattern matching parallel algorithm Aho-Corasick

来源：评论

学校读者我要写书评

暂无评论

parallel BURA Based Numerical Solution of Fractional Laplacian with Pure Neumann Boundary Conditions 12th

Parallel BURA Based Numerical Solution of Fractional Laplaci...

引用

12th International Conference on Large-Scale Scientific Computations (LSSC)

作者： Bencheva, Gergana Kosturski, Nikola Vutov, Yavor Bulgarian Acad Sci Inst Informat & Commun Technol Sofia Bulgaria

ISBN: (纸本)9783030410322;9783030410315

The study is motivated by the increased usage of fractional Laplacian in the modeling of nonlocal problems like anomalous diffusion. We present a parallel numerical solution method for the nonlocal elliptic problem: -Delta(alpha)u = f, 0 < alpha < 1, -partial derivative u(x)/partial derivative n = g(x) on partial derivative Omega, Omega subset of IRd. The Finite Element Method (FEM) is used for discretization leading to the linear system A(alpha)u = f, where A is a sparse symmetric and positive semidefinite matrix. The implemented method is based on the Best Uniform Rational Approximation (BURA) of degree k, r(alpha,k), of the scalar function t(alpha), 0 <= t <= 1. The related approximation of A(-alpha) f can be written as a linear combination of the solutions of k local problems. The latter are found using the preconditioned conjugate gradient method. The method is applicable to computational domains with general geometry. Linear finite elements on unstructured tetrahedral meshes with local refinements are used in the presented numerical tests. The behavior of the relative error, the number of Preconditioned Conjugate Gradient (PCG) iterations, and the parallel time is analyzed varying the parameter alpha is an element of{0.25, 0.50, 0.75}, the BURA degree k is an element of{5, 6,..., 12}, and the mesh size.

关键词： BURA Fractional diffusion Neumann boundary conditions Unstructured meshes parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Modeling performance of the multiscale fluid numerical solver on large-scale parallel computers 2020

Modeling performance of the multiscale fluid numerical solve...

引用

4th International Conference on High Performance Compilation, Computing and Communications (HP3C)

作者： Guo, Xiao-Wei Li, Chao Natl Univ Def Technol Coll Comp Inst Quantum Informat Changsha Hunan Peoples R China Natl Univ Def Technol Coll Comp State Key Lab High Performance Comp Changsha Hunan Peoples R China

ISBN: (纸本)9781450376914

The BCF(Brownian Configuration Fields) method is one of the most promising multi-scale approaches for simulating complex fluids. As a novel parallel algorithm, the MCDPar algorithm could be used to significantly reduce the time cost of BCF-based multi-scale fluid simulations. In this paper, we focus on the parallel performance model for a MCDPar solver on massively parallel computers. A theoretical model to predicting the overall time cost is proposed and the key parameters are fitted through experimental results. This performance model explains the significant performance improvement observed previously and could be used for cost estimation and parameter design.

关键词： parallel algorithm fluid simulation BCF method performance model

来源：评论

学校读者我要写书评

暂无评论

High-Speed Channel Equalization Applying parallel Bayesian Machine Learning

High-Speed Channel Equalization Applying Parallel Bayesian M...

引用

IEEE International Symposium on Electromagnetic Compatibility (IEEE EMC) / Virtual Symposium on Signal and Power Integrity (SIPI)

作者： Kiguradze, Zurab Dikhaminjia, Nana Tsiklauri, Mikheil He, Jiayi Mutnury, Bhyrav Chada, Arun Drewniak, James Missouri Univ Sci & Technol Missouri S&T EMC Lab Rolla MO 65409 USA Ilia State Univ Dept Nat Sci & Engn 3-5 Kakutsa Cholokashvili Ave GE-0162 Tbilisi Georgia Dell Enterprise Prod Grp One Dell WayMS RR5-31 Round Rock TX 78682 USA

ISBN: (纸本)9781728174303

Recovering attenuated signals caused by different issues including connections between connectors and chips of the devices, channel loss, and crosstalk is a challenging problem. Equalization is the most popular way to restore distorted signals. Different optimization algorithms are used to find the best tap coefficients for each equalization that improves eye opening and decreases the bit error rate (BER). Nowadays algorithms of equalization mainly operate to reduce the difference between input and output signals. In turn, this will increase eye height indirectly, but direct maximization of the eye height will restore the signal even better. The paper proposes a new efficient optimization of joint Feed-Forward Equalization (FFE) and Decision Feedback Equalization (DFE) for binary as well as multilevel signals. Unlike to above-mentioned method, which is a linear optimization problem, direct maximization of the eye height applying joint FFE and DFE is a non-linear problem and cannot be solved analytically. Paper proposes the black-box function optimization using the regular as well as parallel Bayesian machine learning to find the best tap coefficients for joint FFE and DFE equalization. The efficiency of the parallel Bayesian algorithm is shown for binary NRZ (nonreturn-to-zero) and PAM4 (Pulse Amplitude Modulation) signals.

关键词： Equalization DFE FFE Optimal selection of tap coefficients Joint optimization Bayesian Optimization parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

parallel and Distributed algorithm for Partial Coordination in Massive MIMO Networks 25

Parallel and Distributed Algorithm for Partial Coordination ...

引用

25th IEEE Annual International Symposium on Personal, Indoor, and Mobile Radio Communication (PIMRC)

作者： Wan, Qian Niu, Kai Lin, Jiaru Beijing Univ Posts & Telecommun Key Lab Universal Wireless Commun Minist Educ Beijing Peoples R China

ISBN: (纸本)9781479949120

We propose a parallel and distributed algorithm for the problem of beamformer design and power allocation in multi-cell massive multiple-input multiple-output (MIMO) networks. Inter-cell coordination and overlapping clusters are considered to enhance the system performance. To overcome the tight coupling induced by inter-cell coordination and overlapping clusters, we formulate the system into a two-layered framework. In this framework, the problem is decomposed into independent subproblems which are naturally solvable in a parallel and distributed manner. For each subproblem, an efficient parallel algorithm is proposed to speed up the convergence rate. The simulation results show that our inter-cell coordination strategy can approach the performance achieved by a high-quality limited inter-cell coordination strategy at low signal-to-noise ratio (SNR), and outperform it at high SNR. Moreover, the proposed parallel algorithm enjoys great parallelization speedup with moderate transmit power consumption.

关键词： parallel algorithm Partial Coordination Massive MIMO Beamformer Design

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：