|
Dietmar Lammers

Nodari Sitchinava: Locality-conscious parallel algorithms

Tuesday, 04.08.2015 11:30 im Raum SR 7

Mathematik und Informatik

As we solve problems with bigger input sizes, the time it takes to access data is no longer uniform as the traditional algorithmic models teach us. The modern systems are designed with deep memory hierarchies which include multiple levels of caches, NUMA DRAM design and slow but large disks available via virtual memory. The non-uniformity of memory access is even more apparent in parallel architectures: added computational power of the additional processors/cores increases the gap between the computational throughput and the memory throughput. In this talk, I will present the Parallel External Memory (PEM) model -- a theoretical model for multicores with memory hierarchies. The theoretical analysis of algorithms in this model more closely correlates with the actual runtimes on modern multicores, compared to traditional parallel models, such as PRAM. I will also show that algorithmic techniques designed in the PEM model can be used for developing better algorithms and lower bounds in other modern computation frameworks, such as general purpose graphics processing units (GPGPUs) and the MapReduce.



Angelegt am Wednesday, 29.07.2015 11:53 von Dietmar Lammers
Geändert am Monday, 03.08.2015 09:43 von N. N
[Edit | Vorlage]

Kolloquium der Informatik