Engineering Scalable Parallel Sorting Algorithms

Speaker: Michael Axtmann and Peter Sanders , Karlsruhe Institute of Technology

Date: Monday, July 13, 2020

Time: 2:00 PM to 3:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/meeting/register/tJUrdOqopj8uHdO4gUyVMnfglOFEqIye_Je0 (Registration required)

Event Type: Seminar

Room Description: https://mit.zoom.us/meeting/register/tJUrdOqopj8uHdO4gUyVMnfglOFEqIye_Je0 (Registration required)

Host: Julian Shun, MIT CSAIL

Contact: Julian Shun, jshun@mit.edu, lindalynch@csail.mit.edu

Relevant URL: http://fast-code.csail.mit.edu/

Speaker URL: https://algo2.iti.kit.edu/english/2419.php, https://algo2.iti.kit.edu/english/sanders.php

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, fast-code-seminar@lists.csail.mit.edu, pl@csail.mit.edu, commit@lists.csail.mit.edu

Reminder Subject: TALK: Engineering Scalable Parallel Sorting Algorithms

Abstract:

Sorting is one of the most fundamental "basic toolbox" operations that
is used in many applications. Implementing fast sorting algorithms
requires carefully engineering algorithms that take various aspects of
modern computer architecture into account, e.g., caches,
branch-prediction, multithreading, NUMA, latency and volume of
communication. Thus, studying sorting algorithms is also a good case
study in algorithm engineering in general.

After briefly introducing the methodology of algorithm engineering, we
take a close look at inplace super-scalar sample sort which, arguably,
is the currently best general purpose shared-memory parallel sorting
algorithm. We then go beyond a single machine looking at scalable
distributed-memory sorting with hundreds of thousands of cores. We argue
that scalability analysis is a key to understanding which algorithm
works best for what input size.

Bio:

Michael Axtmann is a PhD student of Peter Sanders working on the subject
of this talk. He obtained his Master of Science degree at KIT where he
wrote his master's thesis on bioinformatics algorithms in cooperation
with SAP. Besides working on shared-memory and distributed sorting
algorithms, Michael Axtmann is interested in parallel high performance
algorithms and Big Data. For example, he was one of three PhD candidates
who developed the concepts of the distributed Big Data framework Thrill
in a research project with six master students.

Peter Sanders received his PhD in computer science from Universität
Karlsruhe in 1996. After 7 years at the Max-Planck-Institute for
Informatics in Saarbrücken he returned to Karlsruhe as a full professor
in 2004. He works at the Informatics Department of KIT in
the Institute for Theoretical Computer Science. Peter Sanders won a
number of prices among them the DFG
Leibniz Award 2012 and a 2020 ERC advanced grant for the project
"Engineering Scalable Algorithms for the Basic Toolbox -- ScAlBox" both
projects come with about 2.5 million Euros of research money. He has
more than 250 publications, mostly on algorithms for
large data sets. This includes parallel algorithms (sorting, data
structures, multi-core algorithm libraries, load balancing,
communication scheduling, e.g., using network coding,...), memory
hierarchies (caches, disks, storage servers,...), graph algorithms
(route planning, graph partitioning...), randomized algorithms, full
text indices, etc. He is very active in promoting the methodology of
algorithm engineering that integrates design, analysis, implementation,
and experimental evaluation of algorithms. His industrial projects
include companies like BMW, Google, NEC, SAP, and several smaller
companies working on route planning, logistics and search engines.

Research Areas:
Algorithms & Theory, Computer Architecture, Programming Languages & Software

Impact Areas:
Big Data

See other events that are part of the Fast Code 2020 - 2021.

Created by Julian J. Shun at Monday, July 06, 2020 at 6:16 PM.