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

IEEE/ACM international symposium on Microarchitecture (MICRO)

作者： Ahmed ElTantawy Tor M. Aamodt University of British Columbia

ISBN: (纸本)9781509035090

In the single-instruction multiple-threads (SIMT) execution model, small groups of scalar threads operate in lockstep. Within each group, current SIMT hardware implementations serialize the execution of threads that follow different paths, and to ensure efficiency, revert to lockstep execution as soon as possible. These constraints must be considered when adapting algorithms that employ synchronization. A deadlock-free program on a multiple-instruction multiple-data (MIMD) architecture may deadlock on a SIMT machine. To avoid this, programmers need to restructure control flow with SIMT scheduling constraints in mind. This requires programmers to be familiar with the underlying SIMT hardware. In this paper, we propose a static analysis technique that detects SIMT deadlocks by inspecting the application control flow graph (CFG). We further propose a CFG transformation that avoids SIMT deadlocks when synchronization is local to a function. Both the analysis and the transformation algorithms are implemented as LLVM compiler passes. Finally, we propose an adaptive hardware reconvergence mechanism that supports MIMD synchronization without changing the application CFG, but which can leverage our compiler analysis to gain efficiency. The static detection has a false detection rate of only 4%-5%. The automated transformation has an average performance overhead of 8.2%-10.9% compared to manual transformation. Our hardware approach performs on par with the compiler transformation, however, it avoids synchronization scope limitations, static instruction and register overheads, and debuggability challenges that are present in the compiler only solution.

关键词： System recovery Synchronization Hardware Graphics processing units Instruction sets Manuals programming

来源：评论

学校读者我要写书评

暂无评论

EXPLORING MPEG HEVC DECODER parallelISM FOR THE EFFICIENT PORTING ONTO MANY-CORE PLATFORMS

EXPLORING MPEG HEVC DECODER PARALLELISM FOR THE EFFICIENT PO...

引用

IEEE international Conference on Image Processing

作者： Damien de Saint Jorre Claudio Alberti Marco Mattavelli Simone Casale-Brunet EPFL SCI-STI-MM Ecole Polytechnique Federale de Lausanne

ISBN: (纸本)9781479957521

MPEG High Efficient Video Coding (HEVC) is likely to emerge as the video coding standard for HD and Ultra-HD TV resolutions. The two elements that push HEVC beyond the previous standards are a higher compression efficiency of about a factor of two, and the introduction of new coding tools, tiles and wavefront that are intended to ease the largely increased encoding complexity particularly for Ultra HD resolutions such as 4K and 8K. However, for HEVC decoder implementations, the achievement of the desired performance on massive parallel platforms cannot rely on the use of such optional (not enforced by MPEG profiles) tools. This paper reports results about the intrinsic parallelism of compliant HEVC decoding algorithms obtained by analyzing a dataflow implementation written using the standard language specified in ISO/IEC 23001-4 and structured attempting to maximize the algorithmic potential parallelism. The experimental results show what is the parallelism achieved by different dataflow architectures and how it can be further combined with the parallelism achieved by relying on tiles and wavefront, whenever they would be available, for porting a compliant HEVC decoder on massive parallel many-core platforms.

关键词： HEVC Data flow programming parallel HEVC decoder implementations

来源：评论

学校读者我要写书评

暂无评论

Efficient communication using total-exchange

Efficient communication using total-exchange

引用

international symposium on parallel Processing

作者： Satish Rao T. Suel T. Tsantilas M. Goudreau NCE Research Institute Princeton NJ USA Department of Computer Science Columbia University New York NY USA Department of Computer Science University of Central Florida Orlando FL USA

A central question in parallel computing is to determine the extent to which one can write parallel programs using a high-level, general-purpose, and architecture-independent programming language and have them executed on a variety of parallel and distributed architectures without sacrificing efficiency. A large body of research suggests that, at least in theory, general-purpose parallel computing is indeed possible provided certain conditions are met: an excess of logical parallelism in the program, and the ability of the target architecture to efficiently realize balanced communication patterns. The canonical example of a balanced communication pattern is an h-relation, in which each processor is the origin and destination of at most h messages. A plethora of protocols has been designed for routing h-relations in a variety of networks. The goal has been to minimize the value of h while guaranteeing delivery of the messages within a time constant factor from optimal. In this paper we describe protocols that meet the most stringent efficiency requirement, namely delivery of messages within time that is a lower order additive term from the best achievable. Such protocols are called 1-optimal. While these protocols achieve 1-optimality only for heavily loaded networks, that is, for large values of h, they are remarkable for their simplicity in that they only use the total-exchange communication primitive. The total-exchange can be realized in many networks using very simple, contention-free, and extremely efficient schemes. The technical contribution of this paper is a protocol to route random h-relations in an N-processor network using /sup h///sub N/(1+o(1))+O(log log N) total-exchange rounds with high probability. Using message duplication, we can improve the bound to /sup h///sub N/(1+o(1))+O(log*N). This improves upon the /sup h///sub N/(1+o(1))+O(log N) bound of Gerbessiotis and Valiant. While our theoretical improvements are modest, our experimental results sho

关键词： parallel processing Concurrent computing National electric code Computer science Routing protocols Optical computing Computer languages Computer architecture Phase change random access memory Context

来源：评论

学校读者我要写书评

暂无评论

High-Performance Radio Telescope Array Data Processing Framework

High-Performance Radio Telescope Array Data Processing Frame...

引用

General Assembly and Scientific symposium, URSI

作者： Max W. Hawkins Daniel J. Czech David H.E. MacMahon Steve Croft Andrew P.V. Siemion University of Alabama Tuscaloosa AL University of California at Berkeley Berkeley CA SETI Institute Mountain View CA

As radio telescope projects grow larger with more antennas observing wider bandwidths, data rates are rapidly increasing. The Square Kilometer Array and other next generation observatories will usher in an era of exascale data and beyond [1]. This necessitates an equivalent increase in data transfers, processing speeds, and emphasis on real-time analysis. Reducing the performance gap between high-level science algorithm development (frequently in Python) and real-time, production code would allow astronomers to better utilize the hardware available to them. To enable this, we create a high-level array data processing pipeline framework in the Julia programming language, featuring templates for modular data processing algorithms. We demonstrate its performance with a spectral kurtosis algorithm and show that the new interface does not introduce significant processing overhead. In future work, we will explore the signal processing potential of new hardware accelerators present in modern GPUs. Such accelerators promise improved performance along with new programming challenges.

关键词： Codes Radio astronomy Array signal processing Pipelines Signal processing algorithms parallel processing Market research

来源：评论

学校读者我要写书评

暂无评论

Implementation of parallel sparse Cholesky factorization on GPU

Implementation of parallel sparse Cholesky factorization on ...

引用

international Conference on Computer Science and Network Technology (ICCSNT)

作者： Dan Zou Yong Dou National Laboratory for Parallel and Distribution Processing National University of Defense Technology Changsha China

ISBN: (纸本)9781467329637

Direct methods for solving large sparse symmetric positive-definite linear systems of equations are popular because of their generality and robustness. The main bottleneck is the sparse Cholesky factorization, which exhibits irregular memory access behavior and unbalanced workload. In the past 10 years, many sparse Cholesky factorization algorithms have emerged, exploiting new architectural features. However, programming techniques currently employed on these platforms are not sufficient to implement sparse Cholesky factorization on many-core graphics processing units (GPUs) due to mismatches between irregular problem structures and single-instruction multiple-thread GPU architectures. In the present paper, we propose a task-based software approach for the parallel sparse Cholesky factorization aimed at heterogeneous computing platforms with GPU accelerators. The tasks are generated by CPU. An efficient task-scheduling mechanism guarantees the correct ordering of task execution and ensures a load balanced execution on GPU. Comparisons are made with the existing solver using problems arising from a range of practical applications. The experiment results show that the proposed approach can substantially improve the performance of sparse Cholesky factorization on GPU with 2.7×-4× speedup.

关键词： Sparse Cholesky factorization GPU Cholesky factorisation Graphics Processing Unit GRAPPER PICK UP Task execution

来源：评论

学校读者我要写书评

暂无评论

Analysis of streaming social networks and graphs on multicore architectures

Analysis of streaming social networks and graphs on multicor...

引用

international Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Jason Riedy Henning Meyerhenke David A. Bader David Ediger Timothy G. Mattson Georgia Institute of Technology Atlanta GA USA Institute for Theoretical Informatics Karlsruhe Institute of Technology Karlsruhe Germany Microprocessor and Programming Research Laboratory Intel Corporation DuPont WA USA

Analyzing static snapshots of massive, graph-structured data cannot keep pace with the growth of social networks, financial transactions, and other valuable data sources. We introduce a framework, STING (Spatio-Temporal Interaction Networks and Graphs), and evaluate its performance on multicore, multisocket Intel ® -based platforms. STING achieves rates of around 100 000 edge updates per second on large, dynamic graphs with a single, general data structure. We achieve speedups of up to 1000× over parallel static computation, improve monitoring a dynamic graph's connected components, and show an exact algorithm for maintaining local clustering coefficients performs better on Intel-based platforms than our earlier approximate algorithm.

关键词： Social network services Approximation algorithms Heuristic algorithms Kernel Monitoring Data structures Algorithm design and analysis

来源：评论

学校读者我要写书评

暂无评论

parallel genetic algorithm with social interaction for solving constrained global optimization problems

Parallel genetic algorithm with social interaction for solvi...

引用

international Conference of Soft Computing and Pattern Recognition (SOCPAR)

作者： Rodrigo Lisbôa Edson Koiti Yasojima Rodrigo M. S. de Oliveira Marco A. Florenzano Mollinetti Otávio Noura Teixeira Roberto C. Limão de Oliveira Pereira Electrical Engineering Post Graduation Program Federal University of Pará (UFPA) Belém Pará Brazil Systems Optimization Laboratory Tsukuba University Tsukuba Ibaraki Japan Electrical Engineering Post Graduation Program Federal University of Pará (UFPA) Belém Pará Brazil Laboratory of Electromagnetics (LeMag) Federal University of Pará (UFPA) Belém Pará Brazil Laboratory of Bionspired Computing (LCBIO) Federal University of Pará (UFPA) Belém Brazil Pará

The following paper introduces a parallel approach to a social variant of the Genetic Algorithm, called parallel Genetic Algorithm with Social Interaction (PSIGA). The algorithm is based on social games involving game theory, and it is implemented using the OpenMP API, which is based on the shared memory programming model for multiple processor architectures. The main contribution of this approach is the parallelization using the Shared Memory of the Social Interaction Genetic Algorithm (SIGA) in order to achieve faster and better optimality than its nonparallel counterpart for global optimization problems with restrictions. For means of performance assessment, the algorithm is tested on four instances of engineering design problems and the obtained results compared with the Genetic Algorithm with Social Interaction (SIGA) implemented in sequential programming model.

关键词： Genetic algorithms Sociology Statistics Optimization Games Game theory Instruction sets

来源：评论

学校读者我要写书评

暂无评论

An Analysis of Lazy and Eager Limited Preemption Approaches under DAG-Based Global Fixed Priority Scheduling

An Analysis of Lazy and Eager Limited Preemption Approaches ...

引用

international symposium on Object-Oriented Real-Time Distributed Computing

作者： Maria A. Serrano Alessandra Melani Sebastian Kehr Marko Bertogna Eduardo Quiñones Universitat Politecnica de Catalunya (UPC) Barcelona Spain Barcelona Supercomputing Center (BSC) Barcelona Spain Scuola Superiore Sant’ Anna Pisa Italy DENSO AUTOMOTIVE Deutschland GmbH University of Modena and Reggio Emilia Modena Italy

DAG-based scheduling models have been shown to effectively express the parallel execution of current many-core heterogeneous architectures. However, their applicability to real-time settings is limited by the difficulties to find tight estimations of the worst-case timing parameters of tasks that may arbitrarily be preempted/migrated at any instruction. An efficient approach to increase the system predictability is to limit task preemptions to a set of pre-defined points. This limited preemption model supports two different preemption approaches, eager and lazy, which have been analyzed only for sequential task-sets. This paper proposes a new response time analysis that computes an upper bound on the lower priority blocking that each task may incur with eager and lazy preemptions. We evaluate our analysis with both, synthetic DAG-based task-sets and a real case-study from the automotive domain. Results from the analysis demonstrate that, despite the eager approach generates a higher number of priority inversions, the blocking impact is generally smaller than in the lazy approach, leading to a better schedulability performance.

关键词： Computational modeling Interference Real-time systems Processor scheduling Computer architecture Analytical models parallel programming

来源：评论

学校读者我要写书评

暂无评论

A Family of Scheduling algorithms for Hybrid parallel Platforms

引用

international JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2018年第1期29卷 63-90页

作者： Kedad-Sidhoum, Safia Monna, Florence Mounie, Gregory Trystram, Denis Univ Paris 06 UPMC Sorbonne Univ UMR 7606LIP6 F-75005 Paris France Univ Grenoble Alpes 655 Ave Europe F-38334 Saint Ismier France

More and more parallel computing platforms are built upon hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like General Purpose Graphics Processing Units (GPGPUs). We present in this paper a new method for scheduling efficiently parallel applications with m CPUs and k GPGPUs, where each task of the application can be processed either on an usual core (CPU) or on a GPGPU. We consider the problem of scheduling n independent tasks with the objective to minimize the time for completing the whole application (makespan). This problem is NP-hard, thus, we present two families of approximation algorithms that can achieve approximation ratios of 2q+1/2q + epsilon or 2(q+1/2q+1) + epsilon for any integer q >= 1 when only one GPGPU is considered, and 2q+1/2q + 1/2qk + epsilon or 2(q+1/2q+1 + 1/(2q+1)k + epsilon k >= 2 GPGPUs, where is an arbitrary small value which corresponds to the target accuracy of a binary search. The proposed method is based on a dual approximation scheme that uses a dynamic programming algorithm. The associated computational costs are for the first (resp. second) family in O(n(2)k(q+1)m(q)) (resp. O(n(2) k(q+2)m(q+1))) per step of dual approximation. The greater the value of parameter q, the better the approximation, but the more expensive the computational cost. Finally, we propose a relaxed version of the algorithm which achieves a running time in O(n log n) with a constant approximation bound of 2. This last result is compared to the state-of-the-art algorithm HEFT. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes.

关键词： Scheduling approximation algorithms parallel heterogeneous systems

来源：评论

学校读者我要写书评

暂无评论

Pipette: Improving Core Utilization on Irregular Applications through Intra-Core Pipeline parallelism

Pipette: Improving Core Utilization on Irregular Application...

引用

IEEE/ACM international symposium on Microarchitecture (MICRO)

作者： Quan M. Nguyen Daniel Sanchez MIT CSAIL

ISBN: (数字)9781728173832

ISBN: (纸本)9781728173849

Applications with irregular memory accesses and control flow, such as graph algorithms and sparse linear algebra, use high-performance cores very poorly and suffer from dismal IPC. Instruction latencies are so large that even SMT cores running multiple data-parallel threads suffer poor *** find that irregular applications have abundant pipeline parallelism that can be used to boost utilization: these applications can be structured as a pipeline of stages decoupled by queues. Queues hide latency very effectively when they allow producer stages to run far ahead of consumers. Prior work has proposed decoupled architectures, such as DAE and streaming multicores, that implement queues in hardware to exploit pipeline parallelism. Unfortunately, prior decoupled architectures are ill-suited to irregular applications, as they lack the control mechanisms needed to achieve decoupling, and target decoupling across cores but suffer from poor utilization within each core due to load imbalance across *** present Pipette, a technique that enables cheap pipeline parallelism within each core. Pipette decouples threads within the core using architecturally visible queues. Pipette's ISA features control mechanisms that allow effective decoupling under irregular control flow. By time-multiplexing stages on the same core, Pipette avoids load imbalance and achieves high core IPC. Pipette's novel implementation uses the physical register file to implement queues at very low cost, putting otherwise-idle registers to use. Pipette also adds cheap hardware to accelerate common access patterns, enabling fine-grain composition of accelerated accesses and general-purpose computation. As a result, Pipette outperforms data-parallel implementations of several challenging irregular applications by gmean 1.9× (and up to 3.9×).

关键词： Multicore processing Instruction sets Pipelines Computer architecture parallel processing Registers Acceleration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：