Abstract

Today, every computer is a parallel computer, with two, four, or more processor cores simultaneously carrying out various tasks. We can harness this power to perform a large-scale demanding task by letting the cores work together, dividing the computational work evenly among them, while trying to limit the amount of communication between them.

Part I

In this lecture, I will present recent developments in the field of high-performance computing, such as hierarchical architectures with both shared and distributed memory, available libraries for parallel programming, and a number of basic examples of parallel algorithms such as sorting and sparse matrix-vector multiplication. A more advanced example is the training and deployment of an artificial neural network, which is directly related to sparse or dense matrix-vector multiplication. In my explanations, I will assume a simple model for parallel computation, the bulk synchronous parallel (BSP) model and a two-level extension, hybrid BSP.

Part II

Networks are everywhere: social networks such as Facebook and Twitter connect billions of people. The brain has billions of neurons. These people or neurons are the nodes in the network and typically they are connected to a limited set of neighbours, defined by either friendships, followers, or dendrites and axons. The network can change over time, by new friendships or new followers, deleted friendships, and in case of the brain due to its plasticity.
Mathematically, networks are modelled as graphs, with vertices as the nodes of the network and edges as the connections.

In this lecture, I will present parallel algorithms for analysing large-scale networks. Counting triangles in a network is a widely used basic operation in network analytics, giving the so-called clustering coefficient, an important network characteristic. Triangle counting can be parallelised well and we will see how this is done. Another example algorithm is weighted graph matching, which is used in the realm of online dating (matchmaking) services, but also in less romantic applications such as assigning jobs to workers or detecting communities in social networks. in social networks.

About

Rob Bisseling is a full professor in Scientific Computing at the Mathematics Institute of Utrecht University. He is author of the book “Parallel scientific computation: a structured approach using BSP”, Oxford University Press, 2004, with a second edition expected to appear Fall 2019.

Previously, he worked as a research mathematician at Shell Research, Amsterdam, where he investigated the application of parallel computing in oil refinery optimization and polymer modelling. He received a BSc degree in mathematics, physics, and astronomy in 1977 and an MSc degree in mathematics in 1981, both from the Catholic University of Nijmegen, and a PhD degree in theoretical chemistry in 1987 from the Hebrew University of Jerusalem, Israel.

He is co-author of the BSPlib standard (1997) for parallel computing using the BSP model and of several open-source software packages: Mondriaan for partitioning sparse matrices (2002); SAWdoubler for counting self-avoiding walks on a lattice (2012); and the BSP libraries MulticoreBSP for Java (2012), MulticoreBSP for C (2014), and Bulk for C++ (2018).

At Utrecht University, he teaches the MSc course Parallel Algorithms (every year since 1993); he has also taught courses on Networks, Scientific Computing, and Mathematics for Industry. His research interests are numerical and combinatorial scientific computing in general, and parallel algorithms, sparse matrix computations, graph algorithms, and their application in Big Data in particular.

Rob Bisseling is a full professor in Scientific Computing at the Mathematics Institute of Utrecht University. You can read more about him on his website.