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

parallel Multidimensional Lookahead Sorting Algorithm

IEEE ACCESS 2019年 7卷 75446-75463页

作者： Gebali, Fayez Taher, Mohamed Zaki, Ahmed M. El-Kharashi, M. Watheq Tawfik, Ayman Univ Victoria Dept Elect & Comp Engn Victoria BC V8W 3P6 Canada Ain Shams Univ Fac Engn Comp & Syst Engn Dept Cairo 11517 Egypt Ajman Univ Elect Engn Dept Ajman U Arab Emirates

This paper presents a new parallel structured lookahead multidimensional sorting algorithm. Our algorithm can be based on any sequential sorting algorithm. The amount of parallelism can be controlled using several parameters such as the number of threads, word size, memory/processor communication overhead, and the dimension of the algorithm. The proposed technique is ideally suited for general purpose graphic processing units and shared-memory massively parallel processor systems. It ensures that data being processed exhibits temporal and spatial locality to maximize the utilization of processor cache. The algorithm achieves a speedup even when a single processor is used. A lookahead algorithm is also proposed to achieve even higher speedup. The performance of the proposed algorithm is verified numerically and experimentally.

关键词： Lookahead multicore execution parallel algorithms sorting algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel demand side auction mechanism for dynamic and efficient resource allocation

引用

IET CONTROL THEORY AND APPLICATIONS 2019年第15期13卷 2399-2406页

作者： Wang, Peng Zou, Suli Ma, Zhongjing BIT Sch Automat Beijing 100081 Peoples R China Swiss Fed Inst Technol Dept Informat Technol & Elect Engn Automat Control Lab CH-8092 Zurich Switzerland

Effective allocation mechanisms are required for infinitesimally divisible demand side resources capturing self-interest and non-cooperation among the users who consume the resources, in order to achieve efficient resource allocation maximising the social welfare with decentralisation of information sharing and decision making. The authors study an auction based mechanism to allocate the demand side resource, where a set of users who consume resources game with each other by bidding. The proposed auction mechanism fits into the progressive second price (PSP) mechanism, which follows a Vickrey-Clarke-Groves type payment. These kind of mechanisms admit incentive compatibility and existence of the efficient Nash equilibrium (NE). Furthermore, considering the fairness and privacy of the bidders as well as limitation of sequential algorithms in practical applications, the authors present a parallel updating algorithm in which all the bidders synchronously update their bids to achieve the efficient NE. By rigorous theoretical analyses, the proposed algorithm is guaranteed to converge to a bid profile which is shown to be the efficient NE. Numerical simulations demonstrate the performance of the proposed auction mechanism and parallel algorithm.

关键词： pricing decision making game theory resource allocation electronic commerce parallel algorithms parallel demand auction mechanism efficient resource allocation effective allocation mechanisms parallel algorithm numerical simulation parallel updating algorithm efficient Nash equilibrium Vickrey-Clarke-Groves type payment progressive second price mechanism resources game demand side resource decision making information sharing self-interest infinitesimally divisible demand

来源：评论

学校读者我要写书评

暂无评论

Fast computation of 2D and 3D Legendre moments using multi-core CPUs and GPU parallel architectures

引用

JOURNAL OF REAL-TIME IMAGE PROCESSING 2019年第6期16卷 2027-2041页

作者： Hosny, Khalid M. Salah, Ahmad Saleh, Hassan, I Sayed, Mahmoud Zagazig Univ Fac Comp & Informat Dept Informat Technol Zagazig 44519 Egypt Zagazig Univ Fac Comp & Informat Dept Comp Sci Zagazig 44519 Egypt Egyptian Atom Energy Author Dept Radiat Engn Cairo Egypt

Legendre moments and their invariants for 2D and 3D image/objects are widely used in image processing, computer vision, and pattern recognition applications. Reconstruction of digital images by nature required higher-order moments to get high-quality reconstructed images. Different applications such as classification of bacterial contamination images utilize high-order moments for feature extraction phase. For big size images and 3D objects, Legendre moments computation is very time-consuming and compute-intensive. This problem limits the use of Legendre moments and makes them impractical for real-time applications. Multi-core CPUs and GPUs are powerful processing parallel architectures. In this paper, new parallel algorithms are proposed to speed up the process of exact Legendre moments computation for 2D and 3D image/objects. These algorithms utilize multi-core CPUs and GPUs parallel architectures where each pixel/voxel of the input digital image/object can be handled independently. A detailed profile analysis is presented where the weight of each part of the entire computational process is evaluated. In addition, we contributed to the parallel 2D/3D Legendre moments by: (1) a modification of the traditional exact Legendre moment algorithm to better fit the parallel architectures, (2) we present the first parallel CPU implementation of Legendre moment, and (3) we present the first parallel CPU and GPU acceleration of the reconstruction phase of the Legendre moments. A set of numerical experiments with different gray-level images are performed. The obtained results clearly show a very close to optimal parallel gain. The extreme reduction in execution times, especially for 8-core CPUs and GPUs, makes the parallel exact 2D/3D Legendre moments suitable for real-time applications.

关键词： Legendre moments Multi-core CPUs GPUs Image reconstructions Profile analysis parallel algorithms Image classification

来源：评论

学校读者我要写书评

暂无评论

Exaflops biomedical knowledge graph analytics 22

Exaflops biomedical knowledge graph analytics

引用

Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

作者： Ramakrishnan Kannan Piyush Sao Hao Lu Jakub Kurzak Gundolf Schenk Yongmei Shi Seung-Hwan Lim Sharat Israni Vijay Thakkar Guojing Cong Robert Patton Sergio E. Baranzini Richard Vuduc Thomas Potok Oak Ridge National Laboratory Advanced Micro Devices Inc. University of California San Francisco Georgia Institute of Technology

We are motivated by newly proposed methods for mining large-scale corpora of scholarly publications (e.g., full biomedical literature), which consists of tens of millions of papers spanning decades of research. In this setting, analysts seek to discover relationships among concepts. They construct graph representations from annotated text databases and then formulate the relationship-mining problem as an all-pairs shortest paths (APSP) and validate connective paths against curated biomedical knowledge graphs (e.g., Spoke). In this context, we present Coast (Exascale Communication-Optimized All-Pairs Shortest Path) and demonstrate 1.004 EF/s on 9,200 Frontier nodes (73,600 GCDs). We develop hyperbolic performance models (HyPerMod), which guide optimizations and parametric tuning. The proposed Coast algorithm achieved the memory constant parallel efficiency of 99% in the single-precision tropical semiring. Looking forward, Coast will enable the integration of scholarly corpora like PubMed into the Spoke biomedical knowledge graph.

关键词： high-performance computing shortest path problem parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel accelerated Custom Correlation Coefficient calculations for genomics applications

引用

parallel COMPUTING 2019年 84卷 15-23页

作者： Joubert, Wayne Nance, James Climer, Sharlee Weighill, Deborah Jacobson, Daniel Oak Ridge Natl Lab 1 Bethel Valley Rd Oak Ridge TN 37831 USA Univ Tennessee Bredesen Ctr Interdisciplinary Res & Grad Educ 444 Greve Hall 821 Volunteer Blvd Knoxville TN 37996 USA Univ Missouri 1 Univ Blvd311 Express Scripts Hall St Louis MO 63121 USA

The massive quantities of genomic data being made available through gene sequencing techniques are enabling breakthroughs in genomic science in many areas such as medical advances in the diagnosis and treatment of diseases. Analyzing this data, however, is a computational challenge insofar as the computational costs of the relevant algorithms can grow with quadratic, cubic or higher complexity-leading to the need for leadership scale computing. In this paper we describe a new approach to calculations of the Custom Correlation Coefficient (CCC) between Single Nucleotide Polymorphisms (SNPs) across a population, suitable for parallel systems equipped with graphics processing units (GPUs) or Intel Xeon Phi processors. We describe the mapping of the algorithms to accelerated processors, techniques used for eliminating redundant calculations due to symmetries, and strategies for efficient mapping of the calculations to many-node parallel systems. Results are presented demonstrating high per-node performance and near-ideal parallel scalability with rates of more than nine quadrillion (9 x 10(15)) elementwise comparisons achieved per second with the latest optimized code on the ORNL Titan system, this being orders of magnitude faster than rates achieved using other codes and platforms as reported in the literature. Also it is estimated that as many as 90 quadrillion (90 x 10(15)) comparisons per second may be achievable on the upcoming ORNL Summit system, an additional 10X performance increase. In a companion paper we describe corresponding techniques applied to calculations of the Proportional Similarity metric for comparative genomics applications. (C) 2019 Elsevier B.V. All rights reserved.

关键词： High performance computing parallel algorithms NVIDIA (R) GPU Intel (R) xeon phi Comparative genomics Vector similarity metrics Custom Correlation Coefficient

来源：评论

学校读者我要写书评

暂无评论

parallel algorithm portfolios with performance forecasting

引用

OPTIMIZATION METHODS & SOFTWARE 2019年第6期34卷 1231-1250页

作者： Souravlias, D. Kotsireas, I. S. Pardalos, P. M. Parsopoulos, K. E. Helmut Schmidt Univ Dept Logist Management Hamburg Germany Wilfrid Laurier Univ Dept Phys & Comp Sci Waterloo ON Canada Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA Natl Res Univ Higher Sch Econ Lab Algorithms & Technol Network Anal Nizhnii Novgorod Russia Univ Ioannina Dept Comp Sci & Engn Ioannina Greece

We propose a novel algorithm portfolio model that incorporates time series forecasting techniques to predict online the performance of its constituent algorithms. The predictions are used to allocate computational resources to the algorithms, accordingly. The proposed model is demonstrated on parallel algorithm portfolios consisting of three popular metaheuristics, namely tabu search, variable neighbourhood search, and multistart local search. Moving average and exponential smoothing techniques are employed for forecasting purposes. A challenging combinatorial problem, namely the detection of circulant weighing matrices, is selected as the testbed for the analysis of the proposed approach. Experimental evidence and statistical analysis provide insight on the performance of the proposed algorithms and reveal the benefits of using forecasting techniques for resource allocation in algorithm portfolios.

关键词： Algorithm portfolios metaheuristics resource allocation performance forecasting parallel algorithms combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

A semi-Automatic Approach for parallel Problem Solving using the Multi-BSP Model

引用

PROGRAMMING AND COMPUTER SOFTWARE 2019年第8期45卷 517-531页

作者： Alaniz, M. Nesmachnow, S. Univ Republica Herrera y Reissig 565 Montevideo Uruguay

The Multi-Bulk Synchronous parallel (Multi-BSP) model is a recently proposed parallel programming model for multicore machines that extends the classic Bulk Synchronous parallel model. Multi-BSP aims to be a useful model to design algorithms and estimate their running time. This model heavily relies on the right computation of parameters that characterize the hardware. Of course, the hardware utilization also depends on the specific features of the problems and the algorithms applied to solve them. This article introduces a semi-automatic approach for solving problems applying parallel algorithms using the Multi-BSP model. First, the specific multicore computer to use is characterized by applying an automatic procedure. After that, the hardware architecture discovered in the previous step is considered in order to design a portable parallel algorithm. Finally, a fine tuning of parameters is performed to improve the overall efficiency. We propose a specific benchmark for measuring the parameters that characterize the communication and synchronization costs in a particular hardware. Our approach discovers the hierarchical structure of the multicore architecture and compute both parameters for each level that can share data and make synchronizations between computing units. A second contribution of our research is a proposal for a Multi-BSP engine. It allows designing algorithms by applying a recursive methodology over the hierarchical tree already built by the benchmark, focusing on three atomic functions based in a divide-and-conquer strategy. The validation of the proposed method is reported, by studying an algorithm implemented in a prototype of the Multi-BSP engine, testing different parameter configurations that best fit to each problem and using three different high-performance multicore computers.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Triangle Counting Through Cover-Edges

arXiv

引用

arXiv 2022年

作者： Bader, David A. Li, Fuhuan Ganeshan, Anya Gundogdu, Ahmet Lew, Jason Alvarado Rodriguez, Oliver Du, Zhihui Department of Data Science New Jersey Institute of Technology NewarkNJ United States

Counting and finding triangles in graphs is often used in real-world analytics to characterize cohesiveness and identify communities in graphs. In this paper, we propose the novel concept of a cover-edge set that can be used to find triangles more efficiently. We use a breadth-first search (BFS) to quickly generate a compact cover-edge set. Novel sequential and parallel triangle counting algorithms are presented that employ cover-edge sets. The sequential algorithm avoids unnecessary triangle-checking operations, and the parallel algorithm is communication-efficient. The parallel algorithm can asymptotically reduce communication on massive graphs such as from real social networks and synthetic graphs from the Graph500 Benchmark. In our estimate from massive-scale Graph500 graphs, our new parallel algorithm can reduce the communication on a scale 36 graph by 1156x and on a scale 42 graph by 2368x. © 2022, CC BY.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel approach of a Galerkin-based methodology for predicting the compressive strength of the lightweight aggregate concrete

引用

CONSTRUCTION AND BUILDING MATERIALS 2019年 219卷 56-68页

作者： Migallon, Violeta Navarro-Gonzalez, Francisco Penades, Jose Villacampa, Yolanda Univ Alicante Dept Ciencia Comp & Inteligencia Artificial E-03071 Alicante Spain Univ Alicante Dept Matemat Aplicada E-03071 Alicante Spain

A methodology based on the Galerkin formulation of the finite element method has been analyzed for predicting the compressive strength of the lightweight aggregate concrete using ultrasonic pulse velocity. Due to both the memory requirements and the computational cost of this technique, its parallelization becomes necessary for solving this problem. For this purpose a mixed MPI/OpenMP parallel algorithm has been designed and different approaches and data distributions analyzed. On the other hand, this Galerkin methodology has been compared with multiple linear regression models, regression trees and artificial neural networks. Based on different measures of goodness of fit, the effectiveness of the Galerkin methodology, compared with these statistical techniques for data mining, is shown. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Galerkin Modelling parallel algorithms Compressive strength prediction Concrete

来源：评论

学校读者我要写书评

暂无评论

SCALABLE parallel algorithms FOR MASSIVE SCALE-FREE GRAPHS

SCALABLE PARALLEL ALGORITHMS FOR MASSIVE SCALE-FREE GRAPHS

引用

作者： ROGER ALLAN PEARCE Texas A&M University

学位级别：博士

Efficiently storing and processing massive graph data sets is a challenging prob- lem as researchers seek to leverage "Big Data" to answer next-generation scientific questions. New techniques are required to process large scale-free graphs in shared, distributed, and external memory. This dissertation develops new techniques to parallelize the storage, computation, and communication for scale-free graphs with high-degree vertices. Our work facilitates the processing of large real-world graph datasets through the development of parallel algorithms and tools that scale to large computational and memory resources, overcoming challenges not addressed by exist- ing techniques. Our aim is to scale to trillions of edges, and our research is targeted at leadership class supercomputers, clusters with local non-volatile memory, and shared memory systems. We present three novel techniques to address scaling challenges in processing large scale-free graphs. We apply an asynchronous graph traversal technique using prioritized visitor queues that is capable of tolerating data latencies to the external graph storage media and message passing communication. To accommodate large high-degree vertices, we present an edge list partitioning technique that evenly parti- tions graphs containing high-degree vertices. Finally, we propose a technique we call distributed delegates that distributes and parallelizes the storage, computation, and communication when processing high-degree vertices. The edges of high-degree ver- tices are distributed, providing additional opportunities for parallelism not present in existing methods. We apply our techniques to multiple graph algorithms: Breadth-First Search, Single Source Shortest Path, Connected Components, K-Core decomposition, Trian- gle Counting, and Page Rank. Our experimental study of these algorithms demon- strates excellent scalability on supercomputers, clusters with non-volatile memory, and shared memory systems. Our study includes multi

关键词： parallel algorithms graph algorithms scale-free graphs graph partitioning Thesis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：