The last improvements in programming languages and models have focused on simplicity and abstraction; leading Python to the top of the list of the programming languages. However, there is still room for improvement when preventing users from dealing directly with distributed and parallel computing issues. This paper proposes and evaluates AutoParallel, a Python module to automatically find an appropriate task-based parallelisation of affine loop nests and execute them in parallel in a distributed computing infrastructure. It is based on sequential programming and contains one single annotation (in the form of a Python decorator) so that anyone with intermediate-level programming skills can scale up an application to hundreds of cores. The evaluation demonstrates that AutoParallel goes one step further in easing the development of distributed applications. On the one hand, the programmability evaluation highlights the benefits of using a single Python decorator instead of manually annotating each task and its parameters or, even worse, having to develop the parallel code explicitly (e.g., using OpenMP, MPI). On the other hand, the performance evaluation demonstrates that AutoParallel is capable of automatically generating task-based workflows from sequential Python code while achieving the same performances than manually taskified versions of established state-of-the-art algorithms (i.e., Cholesky, LU, and QR decompositions). Finally, AutoParallel is also capable of automatically building data blocks to increase the tasks' granularity; freeing the user from creating the data chunks, and re-designing the algorithm. For advanced users, we believe that this feature can be useful as a baseline to design blocked algorithms. ; This work has been supported by the Spanish Government through contracts SEV2015-0493 and TIN2015-65316-P, and by Generalitat de Catalunya through contract 2014-SGR-1051. Cristian Ramon-Cortes predoctoral contract is financed by the Ministry of Economy and Competitiveness under the contract BES-2016-076791. ; Peer Reviewed ; Postprint (author's final draft)
Hardware performance has been increasing through the addition of computing cores rather than throughincreasing their frequency since the early 2000s.This means that parallel programming is no longer optional should you need to make the best use ofthe hardware at your disposal.Yet many programs are still written sequentially: parallel programming introduces numerousdifficulties.Amongst these, it is notably hard to determine whether a sequence of a program can be executed inparallel, i.e. preserving its behaviour as well as its overall result.Even knowing that it is possible to parallelise a piece of code, doing it correctly is anotherproblem.In this thesis, we present two approaches to make writing parallel software easier.We present an active library (using C++ template metaprogramming to operate during the compilaéetionprocess) whose purpose is to analyse and parallelise loops.To do so, it builds a representation of each processed loop using expression templates through anembedded language.This allows to know which variables are used and how they are used.For the case of arrays, which are common within loops, it also acquires the index functions.The analysis of this information enables the library to identify which instructions in the loop canbe run in parallel.Interdependent instructions are detected by knowing the variables and their access mode for eachinstruction.Given a group of interdependent instructions and the known index functions, the library decides ifthe instructions can be run in parallel or not.We want this library to help developers writing loops that will be automatically parallelisedwhenever possible and run sequentially as without the library otherwise.Another focus is to provide this to serve as a framework to integrate new methods for parallelisingprograms and extended analysis rules.We introduce another active library that aims to help developers by assisting them in writingparallel software instead of fully automating it.This library uses algorithmic skeletons to let the developer describe its algorithms with both itssequential and parallel parts by assembling atomic execution patterns such as a series of tasks or aparallel execution of a repeated task.This description includes the data flow, that is how parameters and function returns aretransmitted.Usually, this is automatically set by the algorithmic skeleton library, however it gives thedeveloper greater flexibility and it makes it possible, amongst other things, for our library toautomatically transmit special parameters that must not be shared between parallel tasks.One feature that this allows is to ensure repeatability from one execution to another even forstochastic algorithms.Considering the distribution of tasks on the different cores, we even reduce the number of thesenon-shared parameters.Once again, this library provides a framework at several levels.Low-level extensions consist of the implementation of new execution patterns to be used to buildskeletons.Another low-level axis is the integration of new execution policies that decide how tasks aredistributed on the available computing cores.High-level additions will be libraries using ours to offer ready-to-use algorithmic skeletons forvarious fields. ; L'écriture de programmes parallèles, par opposition aux programmes classiques séquentiels et n'utilisant donc qu'un processeur, est devenue une nécessité. En effet, si jusqu'au début du millénaire la puissance de calcul des ordinateurs dépendait principalement de la fréquence du processeur, elle est maintenant liée au nombre de cœurs de calcul qui sont de plus en plus nombreux. Pourtant, à cause des difficultés introduites par la parallélisation, la plupart des programmes sont toujours écrits de manière classique. En particulier, il peut être compliqué de déterminer, étant donné une sous partie d'un programme, si la parallélisation est possible, c'est-à-dire si elle n'introduira pas un changement de comportement du programme. Cependant, même en sachant précisément ce qui peut être parallélisé, le faire correctement est aussi une tâche difficile. Cette thèse présente deux approches pour simplifier l'écriture de programmes parallèles. Nous proposons une bibliothèque active -- par métaprogrammation template, elle agit durant la compilation -- qui acquiert des informations à propos d'une portion de programme, correspondant à une boucle, au moyen de patrons d'expression. Celles-ci sont utilisées pour analyser les instructions et identifier lesquelles peuvent être exécutées en parallèle. Cette analyse repose sur deux niveaux de connaissance : l'ensemble des variables utilisées en distinguant les accès en lecture de ceux en écriture, et, puisqu'il s'agit souvent de tableaux, des fonctions d'indice. Les variables et leur mode d'accès permettent de savoir quelles instructions sont interdépendantes tandis que les fonctions d'indice nous servent à déterminer, pour un groupe d'instructions, s'il est possible de procéder à une exécution parallèle des itérations de la boucle. L'objectif de cette bibliothèque est de proposer un cadre, à la fois pour les développeurs afin d'écrire des boucles qui seront automatiquement exécutées en parallèle si cela est possible, mais aussi à un niveau plus élevé pour intégrer de nouvelles méthodes de parallélisation ou d'autres règles à utiliser pour l'analyse. Nous proposons également une seconde bibliothèque, active elle aussi, orientée sur la parallélisation assistée en utilisant la technique des squelettes algorithmiques comme interface pour le développeur. Celle-ci permet de représenter des algorithmes complets comme des assemblages de motifs d'exécution : séquence de tâches ; exécution répétée d'une tâche en parallèle ; . En utilisant cette connaissance, nous pouvons mettre en place des choix dans la manière de répartir les tâches exécutées en parallèle sur les différents processeurs. Par ailleurs, nous avons choisi d'expliciter l'expression de la transmission des données entre les tâches, contrairement à ce qui est habituellement fait.Grâce à cela, la bibliothèque automatise notamment la transmission de paramètres qui ne doivent pas être partagés par des tâches parallèles. Cela nous permet en particulier de garantir la répétabilité des exécutions y compris lorsque, par exemple, les tâches utilisent des nombres pseudo-aléatoires. En tenant compte de la politique d'exécution choisie et des nombres de processeurs possibles, nous réduisons la quantité nécessaire de ces paramètres ne devant pas être partagés. Ainsi, cette seconde bibliothèque propose elle aussi un cadre de programmation à plusieurs niveaux. Celle-ci est extensible au niveau de ses politiques d'exécution ou des motifs pour la construction des squelettes algorithmiques. On peut l'utiliser pour définir une variété de squelettes algorithmiques, lesquels serviront ensuite à un développeur pour écrire des programmes dont la parallélisation sera facilitée.
Hardware performance has been increasing through the addition of computing cores rather than through increasing their frequency since the early 2000s. This means that parallel programming is no longer optional should you need to make the best use of the hardware at your disposal. Yet many programs are still written sequentially: parallel programming introduces numerous difficulties. Amongst these, it is notably hard to determine whether a sequence of a program can be executed in parallel, i.e. preserving its behaviour as well as its overall result. Even knowing that it is possible to parallelise a piece of code, doing it correctly is another problem. In this thesis, we present two approaches to make writing parallel software easier.We present an active library (using C++ template metaprogramming to operate during the compilation process) whose purpose is to analyse and parallelise loops. To do so, it builds a representation of each processed loop using expression templates through an embedded language. This allows to know which variables are used and how they are used. For the case of arrays, which are common within loops, it also acquires the index functions. The analysis of this information enables the library to identify which instructions in the loop can be run in parallel. Interdependent instructions are detected by knowing the variables and their access mode for each instruction. Given a group of interdependent instructions and the known index functions, the library decides if the instructions can be run in parallel or not. We want this library to help developers writing loops that will be automatically parallelised whenever possible and run sequentially as without the library otherwise. Another focus is to provide this to serve as a framework to integrate new methods for parallelising programs and extended analysis rules.We introduce another active library that aims to help developers by assisting them in writing parallel software instead of fully automating it. This library uses algorithmic skeletons to let the developer describe its algorithms with both its sequential and parallel parts by assembling atomic execution patterns such as a series of tasks or a parallel execution of a repeated task. This description includes the data flow, that is how parameters and function returns are transmitted. Usually, this is automatically set by the algorithmic skeleton library, however it gives the developer greater flexibility and it makes it possible, amongst other things, for our library to automatically transmit special parameters that must not be shared between parallel tasks. One feature that this allows is to ensure repeatability from one execution to another even for stochastic algorithms. Considering the distribution of tasks on the different cores, we even reduce the number of these non-shared parameters. Once again, this library provides a framework at several levels. Low-level extensions consist of the implementation of new execution patterns to be used to build skeletons. Another low-level axis is the integration of new execution policies that decide how tasks are distributed on the available computing cores. High-level additions will be libraries using ours to offer ready-to-use algorithmic skeletons for various fields. ; L'écriture de programmes parallèles, par opposition aux programmes « classiques » séquentiels et n'utilisant donc qu'un processeur, est devenue une nécessité. En effet, si jusqu'au début du millénaire la puissance de calcul des ordinateurs dépendait principalement de la fréquence du processeur, elle est maintenant liée au nombre de cœurs de calcul qui sont de plus en plus nombreux. Pourtant, à cause des difficultés introduites par la parallélisation, la plupart des programmes sont toujours écrits de manière « classique ». En particulier, il peut être compliqué de déterminer, étant donné une sous partie d'un programme, si la parallélisation est possible, c'est-à-dire si elle n'introduira pas un changement de comportement du programme. Cependant, même en sachant précisément ce qui peut être parallélisé, le faire correctement est aussi une tâche difficile. Cette thèse présente deux approches pour simplifier l'écriture de programmes parallèles.Nous proposons une bibliothèque active – par métaprogrammation template, elle agit durant la compilation – qui acquiert des informations à propos d'une portion de programme, correspondant à une boucle, au moyen de patrons d'expression. Celles-ci sont utilisées pour analyser les instructions et identifier lesquelles peuvent être exécutées en parallèle. Cette analyse repose sur deux niveaux de connaissance : l'ensemble des variables utilisées en distinguant les accès en lecture de ceux en écriture, et, puisqu'il s'agit souvent de tableaux, des fonctions d'indice. Les variables et leur mode d'accès permettent de savoir quelles instructions sont interdépendantes tandis que les fonctions d'indice nous servent à déterminer, pour un groupe d'instructions, s'il est possible de procéder à une exécution parallèle des itérations de la boucle. L'objectif de cette bibliothèque est de proposer un cadre, à la fois pour les développeurs afin d'écrire des boucles qui seront automatiquement exécutées en parallèle si cela est possible, mais aussi à un niveau plus élevé pour intégrer de nouvelles méthodes de parallélisation ou d'autres règles à utiliser pour l'analyse.Nous proposons également une seconde bibliothèque, active elle aussi, orientée sur la parallélisation assistée en utilisant la technique des squelettes algorithmiques comme interface pour le développeur. Celle-ci permet de représenter des algorithmes complets comme des assemblages de motifs d'exécution : séquence de tâches ; exécution répétée d'une tâche en parallèle ; . En utilisant cette connaissance, nous pouvons mettre en place des choix dans la manière de répartir les tâches exécutées en parallèle sur les différents processeurs. Par ailleurs, nous avons choisi d'expliciter l'expression de la transmission des données entre les tâches, contrairement à ce qui est habituellement fait. Grâce à cela, la bibliothèque automatise notamment la transmission de paramètres qui ne doivent pas être partagés par des tâches parallèles. Cela nous permet en particulier de garantir la répétabilité des exécutions y compris lorsque, par exemple, les tâches utilisent des nombres pseudo-aléatoires. En tenant compte de la politique d'exécution choisie et des nombres de processeurs possibles, nous réduisons la quantité nécessaire de ces paramètres ne devant pas être partagés. Ainsi, cette seconde bibliothèque propose elle aussi un cadre de programmation à plusieurs niveaux. Celle-ci est extensible au niveau de ses politiques d'exécution ou des motifs pour la construction des squelettes algorithmiques. On peut l'utiliser pour définir une variété de squelettes algorithmiques, lesquels serviront ensuite à un développeur pour écrire des programmes dont la parallélisation sera facilitée.
Wannier90 is an open-source computer program for calculating maximally-localised Wannier functions (MLWFs) from a set of Bloch states. It is interfaced to many widely used electronic-structure codes thanks to its independence from the basis sets representing these Bloch states. In the past few years the development of Wannier90 has transitioned to a community-driven model; this has resulted in a number of new developments that have been recently released in Wannier90 v3.0. In this article we describe these new functionalities, that include the implementation of new features for wannierisation and disentanglement (symmetry-adapted Wannier functions, selectively-localised Wannier functions, selected columns of the density matrix) and the ability to calculate new properties (shift currents and Berry-curvature dipole, and a new interface to many-body perturbation theory); performance improvements, including parallelisation of the core code; enhancements in functionality (support for spinor-valued Wannier functions, more accurate methods to interpolate quantities in the Brillouin zone); improved usability (improved plotting routines, integration with high-throughput automation frameworks), as well as the implementation of modern software engineering practices (unit testing, continuous integration, and automatic source-code documentation). These new features, capabilities, and code development model aim to further sustain and expand the community uptake and range of applicability, that nowadays spans complex and accurate dielectric, electronic, magnetic, optical, topological and transport properties of materials. ; The WDG acknowledges financial support from the NCCR MARVEL of the Swiss National Science Foundation, the European Union's Centre of Excellence E-CAM (Grant No. 676531), and the Thomas Young Centre for Theory and Simulation of Materials (Grant No. TYC-101). ; Peer reviewed
Introduction2021 will herald the next census in England and Wales. The Office for National Statistics (ONS) have a goal of publishing outputs within one year, 4 months earlier than in 2011. Since we produce estimates rather than counts, the linkage of the 2021 Census to the Census Coverage Survey which comprises ~710,000 person and ~370,000 household records, has to be carried out in record time (eight weeks) whilst maintaining incredibly high accuracy (less than 0.1% false positives and 0.25% false negatives).
Objectives and ApproachOur approach is to utilise the ONS Distributed Access Platform to write automated matching algorithms that are both efficient and accurate. These methods use parallelisation to speed things up, active machine learning to iteratively improve our parameters, and associative matching to squeeze every last match out automatically without impairing the accuracy.
As in 2011, we will be using clerical matchers to resolve cases that cannot be matched automatically. Speeding up the clerical matching process is imperative. We have therefore developed a pre-search algorithm that takes the hard work out of clerical matching by replacing clerical searching (here's a record can you find a match?) with clerical resolution (here are two or more records, do they match?).
ResultsAs a result of our improvements we estimate that we have increased our automatic matching rates from 70% to 91% for person matching, and from 60% to 95% for household matching, without loss of accuracy. However, the biggest gains in terms of speed are delivered by our pre-search algorithm which, at the current iteration, is limiting false negatives to ~0.13% according to the 2011 gold standard.
ConclusionWe estimate that overall our improvements will mean that in 2021 we will need less than half the clerical resource that was required in 2011 and will meet our eight-week deadline.
