# Presentation: 865652

## PLASMA(Parallel Linear Algebra for Scalable Multicore Architectures)‏

- The Innovative Computing Laboratory
- University of Tennessee Knoxville

## Why Multicore?

*The ILP Wall*

*The Memory Wall*

*The Power Wall*

- ILP is expensive and does not generate much concurrency

- TLP provides higher concurrency

- Power consumption grows with MHz3

- Latency is completely exposed

- Latency can be hidden using multithreading

- Single core

- Multicore

- Power consumption grows linearly with the number of transistors

- Why Multicore?

## Programming for Multicores

- Programming for Multicores

**fine granularity:**** **
**high parallelism degree is needed**
**cores are (and probably will be) associated with relatively small local memories**
**asynchronicity:**** **
**high parallelism degree make synchronizations a bigger bottleneck**
**hide the latency**

## Developing Parallel Algorithms

**LAPACK**

**Threaded**
**BLAS**

**PThreads**

**OpenMP**

**parallelism**

- s

**LAPACK**

**sequential**
**BLAS**

**PThreads**

**OpenMP**

**parallelism**

**sequential**
**BLAS**

- Developing Parallel Algorithms

## Developing Parallel Algorithms: why?

** ****strict synchronizations**
** ****poor parallelism**
** ****poor scalability**

- Developing Parallel Algorithms: why?

## Tiled Cholesky Factorization

**   ****for all **
**      ****do DTRSM on**
**   ****end**
**   ****for all**
**      ****do DGEMM on **
**   ****end**
**end**

- Tiled Cholesky Factorization

**In some cases it is possible to use the LAPACK algorithm breaking the elementary operations into tiles.****	****Cholesky:**

## Tiled LU Factorization

**DGETRF:**

**DGESSM:**

**DSSSSM:**

- Tiled LU Factorization

**In many cases different algorithms are needed which must be invented or can be found in literature. LU and QR:**

## Tiled LU Factorization

- Tiled LU Factorization

**In many cases different algorithms are needed which must be invented or can be found in literature. LU and QR:**

## Tiled LU Factorization

**DGETRF**

**k=1, j=2**
**DGESSM**

**k=1, j=3**
**DGESSM**

**k=1, i=2**
**DTSTRF**

**k=1, i=2, j=2**
**DSSSSM**

**k=1, i=2, j=3**
**DSSSSM**

**k=1, i=3**
**DTSTRF**

**k=1, i=3, j=2**
**DSSSSM**

**k=1, i=3, j=3**
**DSSSSM**

- Tiled LU Factorization

## Block Data Layout

- Column-Major

- Block data layout

- Block Data Layout

**Fine granularity may require novel data formats to overcome****the limitations of BLAS on small chunks of data.**

## Graph Driven Asynchronous Execution

**DTSTRF**

**DGETRF**

**DGESSM**

**DSSSSM**

- Graph Driven Asynchronous Execution

**The whole factorization can be represented as a DAG:**

**Tasks can be scheduled asynchronously and in any order as long as dependencies are not violated.**

**nodes:**** tasks that operate on tiles**
**edges:**** dependencies among tasks**

## Graph Driven Asynchronous Execution

- Priorities:

- Graph Driven Asynchronous Execution

**A critical path can be defined as the shortest path that connects all the nodes with the higher number of outgoing edges. **

## Fork-Join vs Asynchronous

**Time**

**Idle time**

**Fork-Join**

**Asynchronous**

- Fork-Join vs Asynchronous

## Performance: Cholesky

## Performance: QR

## Performance: LU

## Contacts

**http://icl.cs.utk.edu/~buttari**

**http://www-math.cudenver.edu/~langou**

**http://icl.cs.utk.edu/~kurzak**

**http://netlib.org/utk/people/JackDongarra**

**http://icl.cs.utk.edu**