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

International Symposium on parallel and Distributed Processing (IPDPS)

作者： Xu T. Liu Jesun Firoz Sinan Aksoy Ilya Amburg Andrew Lumsdaine Cliff Joslyn Brenda Praggastis Assefaw H. Gebremedhin University of Washington USA Washington State University USA Pacific Northwest National Lab USA Pacific Northwest National Lab USA

Hypergraphs offer flexible and robust data representations for many applications, but methods that work directly on hypergraphs are not readily available and tend to be prohibitively expensive. Much of the current analysis of hypergraphs relies on first performing a graph expansion – either based on the nodes (clique expansion), or on the hyperedges (line graph) − and then running standard graph analytics on the resulting representative graph. However, this approach suffers from massive space complexity and high computational cost with increasing hypergraph size. Here, we present efficient, parallel algorithms to accelerate and reduce the memory footprint of higher-order graph expansions of hypergraphs. Our results focus on the hyperedge-based s-line graph expansion, but the methods we develop work for higher-order clique expansions as well. To the best of our knowledge, ours is the first framework to enable hypergraph spectral analysis of a large dataset on a single shared-memory machine. Our methods enable the analysis of datasets from many domains that previous graph-expansion-based models are unable to provide. The proposed s-line graph computation algorithms are orders of magnitude faster than state-of-the-art sparse general matrix-matrix multiplication methods, and obtain approximately 2–31× speedup over a prior state-of-the-art heuristic-based algorithm for $s$ -line graph computation.

关键词： Distributed processing Distribution strategy Heuristic algorithms Memory management Approximation algorithms Sparse matrices parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling parallel identical machines to minimize makespan: A parallel approximation algorithm

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2019年 133卷 221-231页

作者： Ghalami, Laleh Grosu, Daniel Wayne State Univ Dept Comp Sci 5057 Woodward Ave Detroit MI 48202 USA

Approximation algorithms for scheduling parallel machines have been studied for decades, leading to significant progress in terms of their approximation guarantees. The algorithms that provide near optimal performance are not feasible to use in practice due to their huge execution time requirements, thus underscoring the importance of developing efficient parallel approximation algorithms with near-optimal performance guarantees that are suitable for execution on current parallel systems, such as multi-core systems. We present the design and analysis of a parallel approximation algorithm for the problem of scheduling jobs on parallel identical machines to minimize makespan. The design of the parallel approximation algorithm is based on the best existing polynomial-time approximation scheme (PTAS) for the problem. To the best of our knowledge, this is the first practical parallel approximation algorithm for the minimum makespan scheduling problem that maintains the approximation guarantees of the sequential PTAS and it is specifically designed for execution on shared-memory parallel machines. We implement and run the algorithm on a large multi-core system and perform an extensive experimental analysis on data generated from realistic probability distributions. The results show that our proposed parallel approximation algorithm achieves significant speedup with respect to both the sequential PTAS and the CPLEX-based solver that solves the mixed integer program formulation of the problem. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Scheduling Approximation algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Exploiting Reduced Precision for GPU-based Time Series Mining

Exploiting Reduced Precision for GPU-based Time Series Minin...

引用

International Symposium on parallel and Distributed Processing (IPDPS)

作者： Yi Ju Amir Raoofy Dai Yang Erwin Laure Martin Schulz Max Plank Computing and Data Facility Technical University of Munich NVIDIA GmbH

The mining of multi-dimensional time series is a crucial step in gaining insights into data obtained from physical systems and from monitoring infrastructures. A widely accepted approach for this challenge is the matrix profile, which, however, is computationally very expensive. It relies on calculating large correlation matrices coupled with sort operations across all dimensions of the data, as well as on performing inclusive scans. All of these steps are inherently data parallel and can, therefore, benefit from execution on GPUs, and even more so from horizontal scaling on multiple GPUs. In addition, the nature of the matrix profile calculation allows the exploitation of reduced precision on GPUs. This offers further improvements to enable the analysis of ever growing data sets in real-world scenarios. Based on these motivations, we introduce the first parallel algorithm for multi-dimensional matrix profile on multiple GPUs exploiting reduced precision modes and provide a highly opti-mized implementation using novel optimization techniques. On one NVIDIA A100 GPU, our implementation achieves a 54x performance improvement in comparison to an optimized single-node execution on a state-of-the-art CPU-based implementation relying on double-precision computation and an additional factor of 1.4x when switching to reduced precision while maintaining sufficient accuracy. We study the accuracy and performance trade-offs for our proposed algorithm in detail and present synthetic and real-world case studies to demonstrate how the reduced precision improves the performance, while accomplishing sufficiently accurate results.

关键词： Time series analysis Layout Graphics processing units Switches Data mining Synchronization parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient VLSI architecture for the parallel dictionary LZW data compression algorithm

引用

IET CIRCUITS DEVICES & SYSTEMS 2019年第5期13卷 576-583页

作者： Safieh, Malek Freudenberger, Juergen Univ Appl Sci HTWG Konstanz ISD Constance Germany

The Lempel-Ziv-Welch (LZW) algorithm is an important dictionary-based data compression approach that is used in many communication and storage systems. The parallel dictionary LZW (PDLZW) algorithm speeds up the LZW encoding by using multiple dictionaries. This simplifies the parallel search in the dictionaries. However, the compression gain of the PDLZW depends on the partitioning of the address space, i.e. on the sizes of the parallel dictionaries. This work proposes an address space partitioning technique that optimises the compression rate of the PDLZW. Numerical results for address spaces with 512, 1024, and 2048 entries demonstrate that the proposed address partitioning improves the performance of the PDLZW compared with the original proposal. These address space sizes are suitable for flash storage systems. Moreover, the PDLZW has relative high memory requirements which dominate the costs of a hardware implementation. This work proposes a recursive dictionary structure and a word partitioning technique that significantly reduce the memory size of the parallel dictionaries.

关键词： encoding data compression VLSI dictionaries flash memories parallel algorithms storage management compression rate PDLZW address space sizes flash storage systems recursive dictionary structure word partitioning technique dictionary-based data compression approach space partitioning technique VLSI architecture address space partitioning technique compression gain parallel search LZW encoding Lempel-Ziv-Welch algorithm parallel dictionary LZW data compression algorithm parallel dictionaries

来源：评论

学校读者我要写书评

暂无评论

parallel Traversal of Large Ensembles of Decision Trees

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2019年第9期30卷 2075-2089页

作者： Lettich, Francesco Lucchese, Claudio Nardini, Franco Maria Orlando, Salvatore Perego, Raffaele Tonellotto, Nicola Venturini, Rossano Univ Fed Ceara BR-60020181 Fortaleza CE Brazil Ca Foscari Univ Venice I-30123 Venice Italy CNR ISTI I-56127 Pisa Italy Univ Pisa I-56126 Pisa Italy

Machine-learnt models based on additive ensembles of regression trees are currently deemed the best solution to address complex classification, regression, and ranking tasks. The deployment of such models is computationally demanding: to compute the final prediction, the whole ensemble must be traversed by accumulating the contributions of all its trees. In particular, traversal cost impacts applications where the number of candidate items is large, the time budget available to apply the learnt model to them is limited, and the users' expectations in terms of quality-of-service is high. Document ranking in web search, where sub-optimal ranking models are deployed to find a proper trade-off between efficiency and effectiveness of query answering, is probably the most typical example of this challenging issue. This paper investigates multi/many-core parallelization strategies for speeding up the traversal of large ensembles of regression trees thus obtaining machine-learnt models that are, at the same time, effective, fast, and scalable. Our best results are obtained by the GPU-based parallelization of the state-of-the-art algorithm, with speedups of up to 102.6x.

关键词： Efficient machine learning learning-to-rank decision tree ensembles parallel algorithms SIMD NUMA multiprocessors GPUs

来源：评论

学校读者我要写书评

暂无评论

parallel reachability analysis of hybrid systems in XSpeed

引用

INTERNATIONAL JOURNAL ON SOFTWARE TOOLS FOR TECHNOLOGY TRANSFER 2019年第4期21卷 401-423页

作者： Gurung, Amit Ray, Rajarshi Bartocci, Ezio Bogomolov, Sergiy Grosu, Radu Natl Inst Technol Meghalaya Shillong Meghalaya India Vienna Univ Technol Vienna Austria Australian Natl Univ Canberra ACT Australia

Reachability analysis techniques are at the core of the current state-of-the-art technology for verifying safety properties of cyber-physical systems (CPS). The current limitation of such techniques is their inability to scale their analysis by exploiting the powerful parallel multi-core architectures now available in modern CPUs. Here, we address this limitation by presenting for the first time a suite of parallel state-space exploration algorithms that, leveraging multi-core CPUs, enable to scale the reachability analysis for linear continuous and hybrid automaton models of CPS. To demonstrate the achieved performance speedup on multi-core processors, we provide an empirical evaluation of the proposed parallel algorithms on several benchmarks comparing their key performance indicators. This enables also to identify which is the ideal algorithm and the parameters to choose that would maximize the performances for a given benchmark.

关键词： Hybrid systems Reachability analysis Support functions parallel algorithms Multi-core processors Breadth-first-search

来源：评论

学校读者我要写书评

暂无评论

parallel Optimization of Trajectory Planning and Tracking for Three-Body Tethered Space System

引用

IEEE-ASME TRANSACTIONS ON MECHATRONICS 2019年第1期24卷 240-247页

作者： Shi, Gefei Zhu, Zhanxia Zhu, Zheng Hong Northwestern Polytech Univ Sch Astronaut Natl Key Lab Aerosp Flight Dynam Xian 710072 Shaanxi Peoples R China York Univ Dept Mech Engn Toronto ON M3J 1P3 Canada

This paper develops a new piecewise parallel optimal control scheme to suppress the libration of a three-body tethered system in circular orbits with a climber. Optimal control is achieved by controlling the tension in tether via regulation of tether length at the end body and the climber speed to minimize the Coriolis' effect. Thus, the total tether length of the system is no longer constant, which is different from the classical three-body tethered system and more effective in libration suppression. To facilitate the space implementation, the original optimal control scheme is split into two parallel phases on a dual-CPU system to reduce computational burden. Phase I predicts an optimal reference state trajectory for the next time interval piecewise by an open-loop optimization with a grossly simplified three-body tethered system model. Phase II tracks the predicted reference trajectory at the current time interval simultaneously by a closed-loop receding horizon control using a full dynamic model. The simulation results reveal that the newly proposed parallel optimal control scheme is able to suppress the libration of the three-body tethered system by controlling tether tension only. Moreover, by controlling the climber's speed adaptively, the libration angles of the tethered system can be suppressed with a shorter transfer period compared with the constant climber speed.

关键词： Attitude control moving climber optimal control parallel algorithms partial space elevator space technology three-body tethered system

来源：评论

学校读者我要写书评

暂无评论

Data-Centric Workloads with MPI_Sort

SSRN

引用

SSRN 2022年

作者： Zulian, Patrick Bader, Seif Ben Fourestey, Gilles Krause, R. Rossinelli, Diego Università della Svizzera Italiana Euler institute Lugano Switzerland Swiss Federal Institute of Technology Lausanne Switzerland The Wavelet Lab Lugano Switzerland

Sorting is a fundamental task in computing and plays a central role in information technology. The advent of rack-scale and warehouse-size data processing shaped the architecture of data analysis platforms towards supercomputing. In turn, established techniques on supercomputers have become relevant to a wider range of application domains. This work is concerned with multi-way mergesort with exact splitting on distributed memory architectures. At its core, our approach leverages a novel and parallel algorithm for multi-way selection problems. Remarkably concise, the algorithm relies on MPI_Allgather and MPI_ReduceScatter_block , two collective communication schemes that find hardware support in most high-end networks. A software implementation of our approach is used to process the Terabyte-size Data Challenge 2 signal, released by the SKA radio telescopes organization. On the supercomputer considered herein, our approach is observed to outperform the state of the art by up to 2.6X using 9216 cores. Our implementation is released as a compact open source library compliant to the MPI programming model. By supporting the most popular elementary key types, and arbitrary fixed-size value types, the library can be straightforwardly integrated into third-party MPI-based software. © 2022, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：