NDLI: A Comprehensive Study of Task Coalescing for Selecting Parallelism Granularity in a Two-Stage Bidiagonal Reduction

Content Provider	IEEE Xplore Digital Library
Author	Haidar, A. Ltaief, H. Luszczek, P. Dongarra, J.
Copyright Year	2012
Abstract	We present new high performance numerical kernels combined with advanced optimization techniques that significantly increase the performance of parallel bidiagonal reduction. Our approach is based on developing efficient fine-grained computational tasks as well as reducing overheads associated with their high-level scheduling during the so-called bulge chasing procedure that is an essential phase of a scalable bidiagonalization procedure. In essence, we coalesce multiple tasks in a way that reduces the time needed to switch execution context between the scheduler and useful computational tasks. At the same time, we maintain the crucial information about the tasks and their data dependencies between the coalescing groups. This is the necessary condition to preserve numerical correctness of the computation. We show our annihilation strategy based on multiple applications of single orthogonal reflectors. Despite non-trivial characteristics in computational complexity and memory access patterns, our optimization approach smoothly applies to the annihilation scenario. The coalescing positively influences another equally important aspect of the bulge chasing stage: the memory reuse. For the tasks within the coalescing groups, the data is retained in high levels of the cache hierarchy and, as a consequence, operations that are normally memory-bound increase their ratio of computation to off-chip communication and become compute-bound which renders them amenable to efficient execution on multicore architectures. The performance for the new two-stage bidiagonal reduction is staggering. Our implementation results in up to 50-fold and 12-fold improvement (~130 Gflop/s) compared to the equivalent routines from LAPACK V3.2 and Intel MKL V10.3, respectively, on an eight socket hexa-core AMD Opteron multicore shared-memory system with a matrix size of 24000 × 24000. Last but not least, we provide a comprehensive study on the impact of the coalescing group size in terms of cache utilization and power consumption in the context of this new two-stage bidiagonal reduction.
Starting Page	25
Ending Page	35
File Size	1315218
Page Count	11
File Format	PDF
ISBN	9781467309752
ISSN	15302075
DOI	10.1109/IPDPS.2012.13
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-05-21
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Kernel Tiles Layout Context Multicore processing Symmetric matrices Eigenvalues and eigenfunctions Dynamic Scheduling Bidiagonal Reduction Two-Stage Approach Tile Algorithms Bulge Chasing Granularity Analysis Power Profiling
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A comprehensive study of task coalescing for selecting parallelism granularity in a two-stage bidiagonal reduction.

An improved parallel singular value algorithm and its implementation for multicore hardware

Two-Stage Tridiagonal Reduction for Dense Symmetric Matrices Using Tile Algorithms on Multicore Architectures

High-performance bidiagonal reduction using tile algorithms on homogeneous multicore architectures

High Performance Bidiagonal Reduction using Tile Algorithms on Homogeneous Multicore Architectures

Two-stage tridiagonal reduction for dense symmetric matrices using tile algorithms on multicore architectures.

Enhancing Parallelism of Tile Bidiagonal Transformation on Multicore Architectures using Tree Reduction

High performance bidiagonal reduction using tile algorithms on homogeneous multicore architectures.

Enhancing parallelism of tile bidiagonal transformation on multicore architectures using tree reduction.

A Comprehensive Study of Task Coalescing for Selecting Parallelism Granularity in a Two-Stage Bidiagonal Reduction

Similar Documents

A comprehensive study of task coalescing for selecting parallelism granularity in a two-stage bidiagonal reduction.

An improved parallel singular value algorithm and its implementation for multicore hardware

Two-Stage Tridiagonal Reduction for Dense Symmetric Matrices Using Tile Algorithms on Multicore Architectures

High-performance bidiagonal reduction using tile algorithms on homogeneous multicore architectures

High Performance Bidiagonal Reduction using Tile Algorithms on Homogeneous Multicore Architectures

Two-stage tridiagonal reduction for dense symmetric matrices using tile algorithms on multicore architectures.

Enhancing Parallelism of Tile Bidiagonal Transformation on Multicore Architectures using Tree Reduction

High performance bidiagonal reduction using tile algorithms on homogeneous multicore architectures.

Enhancing parallelism of tile bidiagonal transformation on multicore architectures using tree reduction.

A Comprehensive Study of Task Coalescing for Selecting Parallelism Granularity in a Two-Stage Bidiagonal Reduction