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

Using Floating-Point Intervals for Non-Modular Computations in Residue Number System

IEEE ACCESS 2020年 8卷 58603-58619页

作者： Isupov, Konstantin Vyatka State Univ Dept Elect Comp Machines Kirov 610000 Russia

The residue number system (RNS) provides parallel, carry-free, and high-speed arithmetic and is therefore a good tool for high-performance computing. However, operations such as magnitude comparison, sign computation, overflow detection, scaling, and division are difficult to perform in RNS, since it is problematic to determine the magnitude of an RNS number. In order to resolve this problem, we propose to compute the interval evaluation of the fractional representation of an RNS number in floating-point arithmetic of limited precision. No matter what the size of the moduli set and dynamic range, only small arithmetic operations are required, and most of the computations are performed in parallel with threads, which allows for efficient implementation of our method on many general-purpose computing platforms. Using this method, we propose new algorithms for magnitude comparison and general division in RNS and implement them for GPUs using the CUDA platform. We evaluate the performance of our algorithms on an NVIDIA GTX 1080 GPU using sets of 4 to 256 RNS moduli that provide dynamic ranges from 64 to 4096 bits. Experimental results show that the proposed new algorithms are efficient for large moduli sets and clearly outperform the existing RNS magnitude comparison and division algorithms in terms of execution time.

关键词： Heuristic algorithms Cathode ray tubes Dynamic range Signal processing algorithms Graphics processing units Memory management Cryptography Residue number system floating-point arithmetic non-modular operations magnitude comparison division high performance parallel algorithms graphics processing unit CUDA

来源：评论

学校读者我要写书评

暂无评论

Improving the Efficiency of SVM Classification With FHE

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2020年 15卷 1709-1722页

作者： Bajard, Jean-Claude Martins, Paulo Sousa, Leonel Zucca, Vincent Sorbonne Univ Lab Informat Paris 6 CNRS F-75006 Paris France Univ Lisbon Inst Super Tecn INESC ID P-1649004 Lisbon Portugal Univ Wollongong Inst Cybersecur & Cryptol Wollongong NSW 2522 Australia

In an ever more data-centric economy, machine learning models have risen in importance. With the large amounts of data companies collect, they are able to develop highly accurate models to predict the behaviours of their customers. It is thus important to safeguard the data used to build these models to prevent competitors from mimicking their services. In addition, as this type of techniques finds its way into areas that need to deal with more sensitive information, like the medical industry, the privacy of the data that needs to be classified also has to be ensured. Herein, this topic is addressed by homomorphically evaluating Support Vector Machine (SVM) models, in a way that guarantees that a client learns nothing about the model except for the classification of his data, and that the service provider learns nothing about the data. Whereas, previously, Fully Homomorphic Encryption (FHE) has mostly focused on either bit-wise or value-wise computations, SVMs present an additional challenge since they combine both: during an initial phase a kernel function is evaluated that makes use of real arithmetic, and during a second phase the sign bit has to be extracted. Novel techniques are herein proposed that allow for speedups of up to 2.7 and 6.6 for the evaluation of polynomials and the determination of sign, respectively, in comparison to the state of the art. Finally, it is shown that the proposed techniques do not deteriorate the classification accuracy of the SVM models.

关键词： Support vector machines Kernel Cryptography Biological system modeling Data models Companies Computational modeling Support vector machine homomorphic encryption computer arithmetic parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Multi-round cooperative search games with multiple players

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年 113卷 125-149页

作者： Korman, Amos Rodeh, Yoav CNRS Paris France Univ Paris Diderot Paris France Ort Braude Coll Karmiel Israel

A treasure is placed in one of M boxes according to a known distribution and k searchers are searching for it in parallel during T rounds. How can one incentivize selfish players so that the probability that at least one player finds the treasure is maximized? We focus on congestion policies C(l) specifying the reward a player receives being one of the l players that (simultaneously) find the treasure first. We prove that the exclusive policy, in which C(1) = 1 and C(l) = 0 for l > 1, yields a price of anarchy of (1 -(1 - 1/k)(k))(-1), which is the best among all symmetric reward policies. We advocate the use of symmetric equilibria, and show that besides being fair, they are highly robust to crashes of players. Indeed, in many cases, if some small fraction of players crash, symmetric equilibria remain efficient in terms of their group performance while also serving as approximate equilibria. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Algorithmic mechanism design parallel algorithms Collaborative search Fault-tolerance Price of anarchy Price of stability Symmetric equilibria

来源：评论

学校读者我要写书评

暂无评论

Where did the tumor start? An inverse solver with sparse localization for tumor growth models

引用

INVERSE PROBLEMS 2020年第4期36卷 045006-045006页

作者： Subramanian, Shashank Scheufele, Klaudius Mehl, Miriam Biros, George Univ Texas Austin Oden Inst Computat Engn & Sci 201 E 24th St Austin TX 78712 USA Univ Stuttgart Inst Parallel & Distributed Syst Univ Str 38 Stuttgart Germany

We present a numerical scheme for solving an inverse problem for parameter estimation in tumor growth models for glioblastomas, a form of aggressive primary brain tumor. The growth model is a reaction-diffusion partial differential equation (PDE) for the tumor concentration. We use a PDE-constrained optimization formulation for the inverse problem. The unknown parameters are the reaction coefficient (proliferation), the diffusion coefficient (infiltration), and the initial condition field for the tumor PDE. Segmentation of magnetic resonance imaging (MRI) scans drive the inverse problem where segmented tumor regions serve as partial observations of the tumor concentration. Like most cases in clinical practice, we use data from a single time snapshot. Moreover, the precise time relative to the initiation of the tumor is unknown, which poses an additional difficulty for inversion. We perform a frozen-coefficient spectral analysis and show that the inverse problem is severely ill-posed. We introduce a biophysically motivated regularization on the structure and magnitude of the tumor initial condition. In particular, we assume that the tumor starts at a few locations (enforced with a sparsity constraint on the initial condition of the tumor) and that the initial condition magnitude in the maximum norm is equal to one. We solve the resulting optimization problem using an inexact quasi-Newton method combined with a compressive sampling algorithm for the sparsity constraint. Our implementation uses PETSc and AccFFT libraries. We conduct numerical experiments on synthetic and clinical images to highlight the improved performance of our solver over a previously existing solver that uses standard two-norm regularization for the calibration parameters. The existing solver is unable to localize the initial condition. Our new solver can localize the initial condition and recover infiltration and proliferation. In clinical datasets (for which the ground truth is unknown), our sol

关键词： brain tumor growth models PDE constrained optimization compressive sampling parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Study of Fine-Grained, Irregular parallel Applications on a Many-Core Processor

Study of Fine-Grained, Irregular Parallel Applications on a ...

引用

作者： Edwards, James Alexander University of Maryland College Park

学位级别：Ph.D.

This dissertation demonstrates the possibility of obtaining strong speedups for a variety of parallel applications versus the best serial and parallel implementations on commodity platforms. These results were obtained using the PRAM-inspired Explicit Multi-Threading (XMT) many-core computing platform, which is designed to efficiently support execution of both serial and parallel code and switching between the two. Biconnectivity: For finding the biconnected components of a graph, we demonstrate speedups of 9x to 33x on XMT relative to the best serial algorithm using a relatively modest silicon budget. Further evidence suggests that speedups of 21x to 48x are possible. For graph connectivity, we demonstrate that XMT outperforms two contemporary NVIDIA GPUs of similar or greater silicon area. Prior studies of parallel biconnectivity algorithms achieved at most a 4x speedup, but we could not find biconnectivity code for GPUs to compare biconnectivity against them. Triconnectivity: We present a parallel solution to the problem of determining the triconnected components of an undirected graph. We obtain significant speedups on XMT over the only published optimal (linear-time) serial implementation of a triconnected components algorithm running on a modern CPU. To our knowledge, no other parallel implementation of a triconnected components algorithm has been published for any platform. Burrows-Wheeler compression: We present novel work-optimal parallel algorithms for Burrows-Wheeler compression and decompression of strings over a constant alphabet and their empirical evaluation. To validate these theoretical algorithms, we implement them on XMT and show speedups of up to 25x for compression, and 13x for decompression, versus bzip2, the de facto standard implementation of Burrows-Wheeler compression. Fast Fourier transform (FFT): Using FFT as an example, we examine the impact that adoption of some enabling technologies, including silicon photonics, would have on the perfo

关键词： Computer engineering Computer science manycore processor parallel algorithms PRAM XMT

来源：评论

学校读者我要写书评

暂无评论

ConcurrentHull: A Fast parallel Computing Approach to the Convex Hull Problem 15th

ConcurrentHull: A Fast Parallel Computing Approach to the Co...

引用

15th International Symposium on Visual Computing, ISVC 2020

作者： Masnadi, Sina LaViola, Joseph J. University of Central Florida OrlandoFL United States

ISBN: (纸本)9783030645557

The convex hull problem has practical applications in mesh generation, file searching, cluster analysis, collision detection, image processing, statistics, etc. In this paper, we present a novel pruning-based approach for finding the convex hull set for 2D and 3D datasets using parallel algorithms. This approach, which is a combination of pruning, divide and conquer, and parallel computing, is flexible to be employed in a distributed computing environment. We propose the algorithm for both CPU and GPU (CUDA) computation models. The results show that ConcurrentHull has a performance gain as the input data size increases. Providing an independently dividable approach, our algorithm has the benefit of handling huge datasets as opposed to other approaches presented in this paper which failed to manage the same datasets. © 2020, Springer Nature Switzerland AG.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

High-Quality Fault Resiliency in Fat Trees

引用

IEEE MICRO 2020年第1期40卷 44-49页

作者： Gliksberg, John Capra, Antoine Louvet, Alexandre Javier Garcia, Pedro Sohier, Devan Versailles St Quentin En Yvelines Univ Versailles France Atos Paris France Castilla La Mancha Univ Ciudad Real Spain Atos BXI Projects 2 Paris France Atos Multiple BXI Projects Paris France Castilla La Mancha Univ Comp Architecture & Technol Ciudad Real Spain

Coupling regular topologies with optimized routing algorithms is key in pushing the performance of interconnection networks of supercomputers. In this article, wepresent Dmodc, a fast deterministic routing algorithmfor parallel generalized fat trees (PGFTs), whichminimizes congestion risk even undermassive network degradation caused by equipment failure. Dmodc computes forwarding tables witha closed-formarithmetic formula by relying on a fast preprocessing phase. This allowscomplete rerouting of networks with tens of thousands of nodes in less than a second. In turn, this greatly helps centralized fabric management react to faults with high-quality routing tables and has no impact on running applications in current and future very large scale high-performance computing clusters.

关键词： Deterministic algorithms Fault Tolerant Computing Mainframes Minimisation Multiprocessor Interconnection Networks Network Routing parallel algorithms parallel Machines Topology Trees Mathematics High Quality Fault Resiliency Coupling Regular Topologies Optimized Routing algorithms Fast Deterministic Routing Algorithm parallel Generalized Fat Trees Massive Network Degradation Equipment Failure Closed Form Arithmetic Formula Fast Preprocessing Phase High Quality Routing Tables Very Large Scale High Performance Computing Clusters Dmodc Algorithm PGFT Interconnection Networks Supercomputers Congestion Risk Minimization Centralized Fabric Management Network Rerouting Routing Protocols Network Topology Degradation Optical Switches Clustering algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimization for Multi-Join Queries on the GPU

引用

IEEE ACCESS 2020年 8卷 118380-118395页

作者： Hu, Xue-Xuan Xi, Jian-Qing Tang, De-You South China Univ Technol Sch Comp Sci & Engn Guangzhou 510006 Peoples R China South China Univ Technol Sch Software Engn Guangzhou 510006 Peoples R China

Multi-join queries are important operations in data management systems and data integration systems, and their efficiency has attracted the attention of researchers. In recent years, graphics processing units (GPUs) have developed rapidly and become a powerful tool for parallel computing, providing a new idea for multi-join query optimization. This paper studies the use of GPU technology to optimize multi-join queries and focuses on two points: 1) a multi-phase optimization strategy and 2) optimization methods of each stage. For the first point, we discuss a two-phase optimization strategy on the GPU and prove the effectiveness of this strategy. For the second point, we provide an establishment method of a minimum cost join tree on the GPU, the parallel execution methods of intra-join and inter-join on the GPU, and a strategy of scheduling multiple joins to execute in parallel on the GPU. Experimental results show that the multi-join query optimization proposed in this paper improves the efficiency of multi-join queries, especially in the case of high load and complex join queries, achieving higher throughput than that of previous optimization algorithms.

关键词： Graphics processing units Heuristic algorithms parallel algorithms Optimization methods Estimation GPU multi-join query parallel optimization two-phase optimization strategy

来源：评论

学校读者我要写书评

暂无评论

Enhanced parallelization of the incremental 4D-Var data assimilation algorithm using the Randomized Incremental Optimal Technique

引用

QUARTERLY JOURNAL OF THE ROYAL METEOROLOGICAL SOCIETY 2020年第728期146卷 1351-1371页

作者： Bousserez, Nicolas Guerrette, Jonathan J. Henze, Daven K. Univ Colorado Mech Engn Boulder CO 80309 USA NOAA Chem Sci Div Boulder CO USA

Incremental 4D-Var is a data assimilation algorithm used routinely at operational numerical weather prediction (NWP) centres worldwide. The algorithm solves a series of quadratic minimization problems (inner-loops) obtained from linear approximations of the forward model around nonlinear trajectories (outer-loops). Since most of the computational burden is associated with the inner-loops, many studies have focused on developing computationally efficient algorithms to solve the least-square quadratic minimization problem, in particular through time parallelization. This paper presents the first implementation and testing of a recently proposed method for parallelizing incremental 4D-Var, the Randomized Incremental Optimal Technique (RIOT), which replaces the traditional sequential conjugate gradient (CG) iterations in the inner-loop of the minimization with fully parallel randomized singular value decomposition (RSVD) of the preconditioned Hessian of the cost function. RIOT is tested using the standard Lorenz-96 model (L-96) as well as two realistic high-dimensional atmospheric source inversion problems based on aircraft observations of black carbon concentrations. A new outer-loop preconditioning technique tailored to RSVD was introduced to improve convergence stability and performance. Results obtained with the L-96 system show that the performance improvement from RIOT compared to standard CG algorithms increases significantly with nonlinearities. Overall, in the realistic black carbon source inversion experiments, RIOT reduces the wall-clock time of the 4D-Var minimization by a factor of 2 to 3, at the cost of a factor of 4 to 10 increase in energy cost due to the large number of parallel cores used. Furthermore, RIOT enables reduction of the wall-clock time computation of the analysis-error covariance matrix by a factor of 40 compared to a standard iterative Lanczos approach. Finally, as evidenced in this study, implementation of RIOT in an operational NWP syste

关键词： data assimilation parallel algorithms 4D variational assimilation RIOT

来源：评论

学校读者我要写书评

暂无评论

A parallel Algorithm for Constructing Two Edge-disjoint Hamiltonian Cycles in Locally Twisted Cubes

A Parallel Algorithm for Constructing Two Edge-disjoint Hami...

引用

2020 International Computer Symposium, ICS 2020

作者： Li, Shun-Yu Chang, Jou-Ming Pai, Kung-Jui National Taipei University of Business Institute of Information and Decision Sciences Taipei Taiwan Ming Chi University of Technology Department of Industrial Engineering and Management New Taipei City Taiwan

ISBN: (纸本)9781728192550

The locally twisted cube LTQn is a variation of the hypercube Qn, and the diameter of LTQn is only about half of the diameter of Qn. For interconnection networks, some efficient communication algorithms can be designed based on the ring structure. In addition, two edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant Hamiltonicity for the interconnection network. Hung [Theoretical Computer Science 412, 4747-4753, 2011] designed an O(n2n) time algorithm to construct two edge-disjoint Hamiltonian cycles in LTQn. In this paper, we provide parallel algorithms for each vertex in LTQn to determine which two edges were adopted in the first or second Hamiltonian cycles, respectively. By connecting these edges, we can construct two edge-disjoint Hamiltonian cycles in LTQn where n ≥ 4. © 2020 IEEE.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：