Exploiting Data Sparsity In Covariance Matrix Computations on Heterogeneous Systems

الموضوعات

علوم تطبيقية وتكنولوجية

الملخص

Covariance matrices are ubiquitous in computational sciences, typically describing the correlation of elements of large multivariate spatial data sets. For example, covari- ance matrices are employed in climate/weather modeling for the maximum likelihood estimation to improve prediction, as well as in computational ground-based astronomy to enhance the observed image quality by filtering out noise produced by the adap- tive optics instruments and atmospheric turbulence. The structure of these covariance matrices is dense, symmetric, positive-definite, and often data-sparse, therefore, hier- archically of low-rank. This thesis investigates the performance limit of dense matrix computations (e.g., Cholesky factorization) on covariance matrix problems as the number of unknowns grows, and in the context of the aforementioned applications. We employ recursive formulations of some of the basic linear algebra subroutines (BLAS) to accelerate the covariance matrix computation further, while reducing data traffic across the memory subsystems layers. However, dealing with large data sets (i.e., covariance matrices of billions in size) can rapidly become prohibitive in memory footprint and algorithmic complexity. Most importantly, this thesis investigates the tile low-rank data format (TLR), a new compressed data structure and layout, which is valuable in exploiting data sparsity by approximating the operator. The TLR com- pressed data structure allows approximating the original problem up to user-defined numerical accuracy. This comes at the expense of dealing with tasks with much lower arithmetic intensities than traditional dense computations. In fact, this thesis con-solidates the two trends of dense and data-sparse linear algebra for HPC. Not only does the thesis leverage recursive formulations for dense Cholesky-based matrix al- gorithms, but it also implements a novel TLR-Cholesky factorization using batched linear algebra operations to increase hardware occupancy and reduce the overhead of the API. Performance reported of the dense and TLR-Cholesky shows many-fold speedups against state-of-the-art implementations on various systems equipped with GPUs. Additionally, the TLR implementation gives the user flexibility to select the desired accuracy. This trade-off between performance and accuracy is, currently, a well-established leading trend in the convergence of the third and fourth paradigm, i.e., HPC and Big Data, when moving forward with exascale software roadmap.

روابط وملفات

التعريف والنوع

رقم الوثيقة

eccb4d63-7605-42c7-b639-0bd44bedbdc3

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل دكتوراة

نوع الملف

pdf text

أسماء الملفات

1699058_1.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":" David E. Keyes","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":"Ali M. Charara","title_ar":"اعداد","title_en":"Preparation"}]

اللغة

English

المصدر والدورية

اسم المصدر

Exploiting Data Sparsity In Covariance Matrix Computations on Heterogeneous Systems

المحتوى والصفحات

عدد الصفحات

0

كلمات الباحثين

covariance matrix , data sparse , Dense Linear Algebra , GPU tile low-rank , Hierarchical

إشراف وإعداد

الإشراف

David E. Keyes

الإعداد

Ali M. Charara

الاقتباسات الببليوغرافية