Christophe Rigaud
email: christophe.rigaud@univ-lr.fr

Antoine Doucet
email: antoine.doucet@univ-lr.fr

Mickaël Coustaty
email: mickael.coustaty@univ-lr.fr

Jean-Philippe Moreux
email: jean-philippe.moreux@bnf.fr

Competition on Post-OCR Text Correction

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

The accuracy of Optical Character Recognition (OCR) technologies considerably impacts the way digital documents are indexed, accessed and exploited [START_REF] Traub | Impact analysis of OCR quality on research tasks in digital archives[END_REF], [START_REF] Chiron | Impact of OCR errors on the use of digital libraries -towards a better access to information[END_REF]. During the last decades, OCR engines have been constantly improving and are today able to return exploitable results on mainstream documents. But in practice, digital libraries have on shelves many transcriptions with a quality below expectation. In fact, ancient documents with challenging layouts and various levels of conservation such as historical newspapers still resist to modern OCRs.

These challenges are addressed by the research project NewsEye 1 which is supporting this competition. It will introduce new concepts, methods and tools for digital humanities by providing enhanced access to historical newspapers for a wide range of users. With the tools and methods created by NewsEye, crucial user groups will be able to investigate views and perspectives on historical events and development and, as consequence, the project will change the way European digital heritage data is (re)searched, accessed, used and analyzed.

Moreover, formerly digitized resources processed with outdated OCRs are rarely re-sent through the latest stateof-the-art digitization pipeline, as priority is often given to the ever-growing masses of new arriving documents. In this context, OCR post-correction approaches, either used on former digitized documents or on fresh challenging documents, could strongly benefit digital libraries.

In this context, the competition was open to researchers from several fields (document analysis, natural language processing, data analysis, text data mining, machine learning...) to challenge their method(s) for improving/denoising OCRed texts. The benefit is double as it gives a global overview of the methods developed by the community and it sets down a common baseline for further works. An analysis of the state of the art shows that it remains difficult to find benchmarks to assess the performance of OCR correction algorithms.

The first post-OCR text correction competition took place during the ICDAR 2017 conference, it resulted in a publicly available dataset2 , evaluation tool3 and a paper [START_REF] Chiron | ICDAR2017 Competition on Post-OCR Text Correction[END_REF]. The text data consisted in more than 12 million characters from French and English languages and included both noisy OCRed texts and the corresponding aligned ground truth (Gold Standard).

This second edition of the competition focused on an almost twice as big and multilingual dataset with 22 million characters in 10 European languages. The dataset was distributed similarly to the first round, using the same evaluation metrics (see Section II-C) and script 2 .

II. COMPETITION SETUP

In this section we describe the two tasks, the dataset, the evaluation and the modalities given to the participants.

A. Task description

Contrary to the first edition of this competition, it has been decided to divide the challenge into two inter-dependent tasks (see Fig. 1), which means the participants have to propose an error detection scheme (task 1) in order to be able to participate on task 2 (error correction). This allowed participant to propose hybrid methods combining the two proposed task, even if the dataset is relatively noisy and thus could potentially lead to discouraging scores of error detection (and therefore correction). The two tasks of 1) detection and 2) correction are described below.

1) Task 1 -Detection of OCR errors: Given the raw OCRed text (no image provided), the participants were asked to provide the position and also the length of the suspected erroneous tokens. The length information is non-trivial; it is necessary in the case of words that are wrongly split (e.g. OCR-ed separators such as spaces, hyphens or line breaks).

2) Task 2 -Correction of OCR errors: Given the OCR errors in their context (position and length from Task 1), the participants were asked to provide, for each error, a ranked list of replacement candidates (the list may contain only one). The ability to provide multiple candidates enables the evaluation of semi-automated techniques as we will detail later.

B. Dataset

The proposed dataset accounts for 22M OCR-ed characters (754 025 tokens) along with the corresponding ground truth, with an unequally share of 10 European languages (see sources, quantities, mean CER µ and standard deviation CER σ in Table I). The digitized documents come from different collections available, among others, in national libraries or universities. The corresponding GT comes from initiatives such as HIMANIS 4 , IMPACT 5 , IMPRESSO 6 , Open data of National Library of Finland7 , GT4HistOCR [START_REF] Springmann | GT4HistOCR: Ground Truth for training OCR engines on historical documents in German Fraktur and Early Modern Latin[END_REF] and RECEIPT [START_REF] Artaud | Find it! fraud detection contest report[END_REF].

Degraded documents sometimes result in highly noisy OCR output and thus cannot reasonably be fully aligned with their GT. The unaligned sequences have not been included in the presented statistics (e.g. number of characters and error rates). Error rates vary according to the nature and the state of degradation of the documents. Historical books for example, due to their complex layout and their original fonts have been reported to be especially challenging for OCR engines with up to 50% of wrongly detected characters in some documents. A first part of the dataset (80%) was provided to the participants for training and testing purposes, and the rest (20%) has been used by the organizers for the evaluation. Figure 2 illustrates on a sample file the format provided to the participants. Tokens are simply space-separated sequences, with no restriction on punctuation. Examples of tokens: "i", "i'am", "bicycle?", "qm86-7lk.Qs'g". Tokens that are considered miss-aligned with the GT are indicated by the "#" signal. The "@" signal is used as padding symbol in the aligned sequences.

C. Evaluation modalities

We proposed two different scenarios to assess the performances of the methods submitted by the participants.

1) Task 1: As it is purely a matter of tokens being truly erroneous or not, this first task is evaluated with usual metrics: recall, precision and F-measure, the latter providing the official ranking of this task. The length information provided by the participants is automatically taken into account by default thanks to the alignment with the GT. For example, the two-token OCR error "we ar" supposed to be "wear" in the GT would penalize (regarding the recall) a solution with only the first token "we".

2) Task 2: The chosen metric for ranking considers for every token of the text sequence, a weighted sum of the Levenshtein distances between the correction candidates and the corresponding token in the Ground Truth. Consequently, best approaches are those that minimize this distance. Providing multiple candidates enables the evaluation on different modalities reflecting various scenarios. We propose to focus on the two following:

• Fully automated scenario, meant for the comparative evaluation of fully automatic OCR correction tools, where only the top 1 (highest-weighted word) in each list is taken into account.

• Semi-automated scenario, meant for the comparative evaluation of human-assisted correction tools, where a person typically picks the right correction within a list of system-generated candidate corrections. Thus, it takes into account the list of proposed corrections along with their weights, with an arbitrary limitation to the top 6 candidates.

The evaluation script was available to the participants before and during the competition from the first edition 8 . It computes the metrics presented above over either the training set or the full dataset, with the assumption that the input files are correctly formatted (see Figure 3). The choice of using a structured format key(pos,lenght) / value(candidates,weights) rather than asking fully corrected sequences has been motivated by the bias that would have implied any further alignment process between the participants results and the corresponding GT.

Miss-aligned tokens (see "#" signals) are ignored for the computation of the different metrics. Also, given the complexity of dealing with hyphen correction, it has been decided to ignore the tokens containing an hyphen through the evaluation (like for the first edition of this competition). Thus, whether such errors are corrected or not, it does not impact on the final result.

D. Modalities and timeline of the competition

The competition was run in an open mode which mean that the participants must submit their formatted results but not their code. We have relied on the scientific integrity of the authors to follow the rules of the competition. The authors were free to participate, even on sub-parts of the dataset. The training set was made available mid-March 2019. The test set (without the GT), used for evaluating the different methods was made available on the 24 th of April with 5 days given for the teams to submit their results.

III. SUBMITTED METHODS

In total, 34 teams registered to the competition, for a final number of 5 submissions. Note that we received an extra answer from a Swedish team that applied their word-based method [START_REF] Hammarström | Poor man's ocr post-correction: Unsupervised recognition of variant spelling applied to a multilingual document collection[END_REF] but couldn't get more than 10-20% on the training dataset, so they decided to not submit their results. The following section gives a brief description of the 5 submitted methods. The descriptions were provided by their authors.

RAE1&2 -Team from Centro de Estudios de la RAE 9 , Spain

The method implemented using weighted finite-state transducers is an application of the noisy channel model to the optical character recognition error correction of historical texts. The model consists of an error model, a language model and a post-processing module.

Probabilistic character error models are estimated from the training corpus using longest common sub-sequence alignments of tokens which are compiled into weighted finite-state edit transducers. The error models are applied, allowing one edition at most and to address segmentation errors, to tokens, token splits, and concatenations of tokens.

Vocabulary and trigram language models are derived from the Google Books Ngram Corpus for English, French, German and Spanish and n-grams from the Finnish N-gram Corpus, version 1, (FNC1). These n-grams meet the characteristics of quantity and historical amplitude, but contain significant OCR errors. However, they are used under the hypothesis of a good signal to noise ratio.

Using the language model and the lattice of hypotheses generated by the error model, the best path is used to determine the best token sequence. Finally, since historical texts do not follow current standard spellings and typographical conventions, original token's case is restored and some heuristics are applied to punctuation.

CCC -Team from Clova AI, NAVER/LINE Corp., South Korea

Our method is Context-based Character Correction (CCC), using the pretrained language model BERT [START_REF] Devlin | BERT: pre-training of deep bidirectional transformers for language understanding[END_REF] known for its context awareness. Our detection model exploits the pretrained multilingual BERT. The BERT output of each sub-token is then plugged into convolutional layers and fully-connected layers to be classified. The model predictions of sub-tokens are merged into token-level predictions. If more than one sub-token of a token is predicted to be erroneous, then the token is erroneous. Our correction model is a character-level sequence to sequence model with the attention mechanism. The encoder is a bidirectional LSTM and the character embedding is shared between the encoder and the decoder. The encoder input is characters of erroneous tokens and corresponding context information from the BERT, fine-tuned at the detection phase. The decoder generates character-level corrections. The final correction of each erroneous token can be found by using beam search.

CSIITJ -Team from department of CSE 10 , IIT 11 Jodhpur, India

We propose a dictionary based solution to the invalid word proposals of an OCR output for English and French Text.

A dictionary based detection scheme is used to mark down OCR tokens not present in the dictionary. We augment the dictionary obtained from training data with external dictionaries 12 13 to generate our final dictionary of 370 098 unique words.

Given an erroneous OCR token o, we take a dictionary based approach, to generate a set of candidate valid words W , based on edit distance. Ranking amongst the candidate words is based on their likelihood given the error model captured through character ngram confusion matrices. 10 Computer Science & Engineering 11 Indian Institute of Technology 12 https://github.com/dwyl/english-words 13 https://github.com/words/an-array-of-french-words where P (o|w) is estimated using n-gram confusion matrices computed from the training set. P (W ), the word prior is based on the word frequencies in the training set. Laplace smoothing was used to deal missing values for n-gram confusion matrices and word frequencies.

UvA-seq2seq -Team from Netherlands eScience Center & University of Amsterdam, Netherlands

This approach applied mainly to task 1 which is based on character level seq2seq model (TensorFlow). The model contains multi-layer LSTM as a decoder and just tested on the English partition of the dataset. The fixed-length sequence of characters is fed to the model; we get the same-length characters in return as output. Based on the differences between the input and output, the positions of errors are identified. Furthermore, the model benefits from the pre-trained data of the 2017 edition of this competition to enrich the training dataset. Among various combinations, the model trained on English Monographs was fine-tuned for ICDAR 2019 with the highest score and the result was submitted to this competition.

CLAM -Team from IITB 14 -Monash Research Academy, India

The proposed method relies on the character level attention model with beam search used at decoder's output. We used the open source system OpenNMT 15 .

Training: To take care of real word errors as well as non word errors, at network's input we used the characters (with space as char delimiter) from input OCR word o t along with characters from few words (with $ as word delimiter) on its left: o t-l:t-1 and right: o t+1:t+r . We also append each input with a language flag and train our model jointly on all languages. At network's output we used the characters (with space as char delimiter) from Ground Truth word g t corresponding the input OCR word o t .

We analyzed the complete dataset and observe that there are at max 10 space related errors where OCR systems introduce fake spaces. To successfully remove such errors during test time we choose l = 10, r = 10.

Testing: We expect model to jointly learn the language as well as error patterns in OCR output. Since our model majorly abstains from changing the correct words, so for error detection the word that is changed by model is considered as erroneous, else correct. We also use edit distance to find the length of erroneous tokens. The changed word/words is/are considered as the suggestion for the error correction task.

IV. RESULTS AND DISCUSSION

Table II and III detail the results for each of the 10 languages on task 1 and 2 respectively. The metrics (Fmeasure and % of improvement) are the average for each of the 10 languages. The percentage of improvement is measured by comparing the weighted sum of the Levenshtein distances between no replacement, top 1 and top 5 replacement (see Section II-C2). The "x" symbol corresponds to no exploitable results (e.g. participation to some languages only). In the context of Task 2, the "=" symbol indicates an equal result for both the automatic and the semi-automatic approaches, which in most cases indicates that participants have provided only one candidate per correction. Note that the UVA method provided overlapping error positions which may have impacted the final score.

The Clova AI team is the best performer on Task 1 with their CCC method achieving the best average F-measure on every corpus language, from 0.67 on French up to 0.95 average F-measure on German, who the latter initially has an important CER (see Table I). Best scores are obtained for German for every team which participated in this language. It is also the language with the highest amount of data (413 703 tokens).

The Clova AI team is the best performer on task 2 as well with their CCC method achieving the best average % of improvement in 8 of 10 languages, from 6% for Spanish to 24% for German. On this task, the IITB team achieved the best performance for Finnish with their CLAM method, 44% improvement in average. Also, the team from the Centro de Estudio de la RAE performed best on French with 26% average improvement with their RAE1 method. For those who provided multiple correction candidates, we sometimes observed slightly better results for the automatic mode than for the semi-automatic mode, but also big drops which shows the limited interest of this latest type of evaluation. The same observation has been done during the 2017 edition of this competition.

Some participants have rightly pointed out some inaccuracies in the GT such as missing or incorrect corrections. The dataset, given its important size and its nature (manually annotated, OCR/GT automatically aligned) is obviously imperfect. Those inaccuracies, although rare, can still trouble both the training (by misleading the final model) and the evaluation phase (by wrongly considering a right correction).

The dataset will be made available on the competition website 16 and submitted to http://tc11.cvc.uab.es after IC-DAR 2019 conference.

V. CONCLUSION

This paper describes the second ICDAR competition on post-OCR text correction. The challenges consisted of two tasks similar to the first edition: 1) error detection and 2) error correction, with the difference of the second task being dependent on the first task. For this edition, we proposed a much larger and multilingual dataset of 22M OCR-ed symbols along with an aligned ground truth. The data came from newspapers, historical books and shopping receipts, covering 10 European languages. This competition demonstrated, through formatted results provided by the participants, the performance of their systems exposed to this specific dataset and to the metrics described in this paper.

Concerning the first task (error detection), the Clova AI team performed the best with a maximum error detection of 95% for German. Its authors proposed a context-based character correction (CCC) method based on the pretrained multi-language model BERT, plugged into convolutional and fully-connected layers for the final classification.

Concerning the second task, (error correction), the Clova AI team also performed the best on 8 of 10 languages using context information from BERT, fine-tuned at the detection phase. IITB team achieved the best performance for Finnish using a character level attention model (CLAM). The team from the Centro de Estudio de la RAE performed best for French.

The submissions that resulted in low scores in the context of this competition could of course work better on different conditions (datasets, languages, formats and metrics).

Comparing to the previous edition of this competition, we see an improvement of the overall error detection performance which has been improved by most of the methods. We also observe that the presented methods generalize well over the proposed multilingual dataset.

In perspective, it would be interesting to test a less complex format for the evaluation with full sequences provided as an input instead of a list of positions/corrections. This would require a posterior automatic alignment phase (e.g. [START_REF] Yalniz | A fast alignment scheme for automatic ocr evaluation of books[END_REF]) with its pros (easier for participants), its cons (difficult support of multiple correction candidates) and its risks (miss-alignment). In a nutshell, this competition has illustrated the difficulty of the proposed tasks on a multilingual dataset. It highlights that the amount of data seems to be more determinant than the language itself for the tested methods. However, this competition also highlighted the strong interest of the community for this topic, which is of primary interest for enhancing the access to patrimonial content from digital libraries.

Figure 1 .

 1 Figure 1. Two tasks: error detection and error correction (from detected errors).

Figure 2 .

 2 Figure 2. Sample of the training set provided to the participants.

Figure 3 .

 3 Figure 3. Format expected for submissions to both Task 1 and 2 (JSON).

  Formally, w * = arg max w∈W P (w|o) = arg max w∈W P (o|w)P (W ) (1)

Table I

 I SOURCES, QUANTITIES AND CHARACTER ERROR RATES (µ, σ)

		INVOLVED IN ALL LANGUAGES OF THE DATASET
	Lang.	Source	# file	# character	µ CER	σ CER
	BG 1	IMPACT	200	399 636	14.96	12.49
	CZ 1	IMPACT	200	274 130	5.79	12.07
	DE 1	IMPRESSO	102	575 416	13.54	14.45
	DE 2	IMPACT	200	494 328	39.67	16.09
	DE 3	Dta19	7 623	10 018 258	24.22	3.26
	DE 4	EML	321	509 757	23.95	3.94
	DE 5	KA	654	818 711	24.19	3.64
	DE 6	ENHG	773	935 014	30.47	3.00
	DE 7	RIDGES	415	527 845	24.20	3.63
	EN 1	IMPACT	200	243 107	21.28	20.25
	ES 1	IMPACT	200	517 723	27.51	17.96
	FI 1	NFL open	393	1 960 345	5.67	3.94
	FR 1	HIMANIS	1 172	2 792 067	7.14	10.09
	FR 2	IMPACT	200	227 039	15.48	13.94
	FR 3	RECEIPT	1 968	742 574	9.27	10.91
	NL 1	IMPACT	200	764 648	26.84	23.42
	PL 1	IMPACT	200	307 144	38.16	18.09
	SL 1	IMPACT	200	261 060	10.16	15.83
	10	18	15 221 22 368 802	20.14	11.50

Table II SUMMARIZED

 II RESULTS FOR TASK 1 FOR EACH PROPOSED METHOD

						Task 1 (F-measure)
	Language	BG	CZ	DE	EN	ES	FI	FR	NL	PL	SL
	Nb tokens 31 164 12 569 413 703 11 443 23 328 54 606 147 432 35 170 13 928 16 682
	CCC	0.77	0.70	0.95	0.67	0.69	0.84	0.67	0.71	0.82	0.69
	CLAM	0.68	0.41	0.93	0.45	0.56	0.51	0.45	0.61	0.72	0.54
	CSIITJ	x	x	x	0.45	x	x	0.42	x	x	x
	RAE1	x	x	0.90	0.53	0.62	0.44	0.42	x	x	x
	RAE2	x	x	0.89	0.57	0.60	0.46	0.45	x	x	x
	UVA	x	x	x	0.47	x	x	x	x	x	x
						Table III
			SUMMARIZED RESULTS FOR TASK 2 FOR EACH PROPOSED METHOD
						Task 2 (% improvement)
					Auto (top1) / Semi (weighted mean on top5)
	Language	BG	CZ	DE	EN	ES	FI	FR	NL	PL	SL
	CCC	9 / 8	6 / =	24 / =	11 / =	11 / 6	8 / =	5 / =	12 / 10	17 / 16	14 / 12
	CLAM	-2 / -3	-1 / =	-7 / =	0.4 / =	-1 / -5	44 / =	4 / =	-3 / =	-2 / =	0 / -1
	CSIITJ	x	x	x	2 / 1	x	x	x	x	x	x
	RAE1	x	x	15 / =	9 / =	7 / =	7 =	26 / =	x	x	x
	RAE2	x	x	14 / =	6 / =	7 / =	6 / =	20 / =	x	x	x
	UVA	x	x	x	0 / =	x	x	x	x	x	x

https://www.newseye.eu

https://l3i.univ-larochelle.fr/ICDAR2017PostOCR

https://git.univ-lr.fr/gchiro01/icdar2017/tree/master

http://www.himanis.org

https://www.digitisation.eu

https://impresso-project.ch

https://digi.kansalliskirjasto.fi/opendata

https://git.univ-lr.fr/gchiro01/icdar2017

Indian Institute of Technology Bombay

http://opennmt.net

https://l3i.univ-larochelle.fr/ICDAR2019PostOCR

ACKNOWLEDGMENT

This work has been supported by the European Union's Horizon 2020 research and innovation programme under grant 770299 (NewsEye). We are grateful to all libraries and institutions that allowed the use of their material for this competition.


Emmanuel Jeannot

Richard Sartori

Improving MPI Application Communication Time with an Introspection Monitoring Library

Keywords: MPI, monitoring, communication optimization, HPC MPI, control, optimisation des communication, calcul haute performance

In this report we describe how to improve communication time of MPI parallel applications with the use of a library that enables to monitor MPI applications and allows for introspection (the program itself can query the state of the monitoring system). Based on previous work, this library is able to see how collective communications are decomposed into point-to-point messages. It also features monitoring sessions that allow suspending and restarting the monitoring, limiting it to specific portions of the code. Experiments show that the monitoring overhead is very small and that the proposed features allow for dynamic and efficient rank reordering enabling up to 2-time reduction of communication parts of some program.

Introduction

To cope with application requirements in terms of speed, precision or memory, the use of supercomputers has emerged as a dominant solution. To program parallel applications onto distributed memory systems, MPI (Message Passing Interface) is the de facto standard. MPI defines how distributed processes exchange data through point-to-point messages as well as collective or one-sided communications.

Being able to write parallel applications whose performance is close to the peak of the target machine is still a very difficult challenge. It requires to design an efficient parallel algorithm, to optimize data structure, to cope with load imbalance, etc. One of the main problems is the way data are exchanged, and allocated. This is of tremendous importance for the overall application performance as when an application (weakly) scales it spends more time in communication. Hence, among all the difficulties, understanding how the processes of the application communicate and coping with data locality is key. To do so, it requires to be able to monitor the application behavior and take decision (at launch time or at runtime) on the process mapping, the communicator composition, and the way communications are executed.

Monitoring MPI applications has been proposed in many tools [START_REF] Trahay | Selecting points of interest in traces using patterns of events[END_REF][START_REF] Knüpfer | Score-P: A Joint Performance Measurement Run-Time Infrastructure for Periscope, Scalasca, TAU, and Vampir[END_REF][START_REF] Keller | Implementation and Usage of the PERUSE-Interface in Open MPI[END_REF]. However, these monitoring tools are designed for performance analysis, performance debugging and post-morten analysis. Having a monitoring tool to perform runtime optimization requires it to be able to perform introspection during execution. This means that this tool should be able to query the state of the monitoring during execution. In [START_REF] Bosilca | Online Dynamic Monitoring of MPI Communications[END_REF], a subset of the authors of this paper proposed a low-level MPI monitoring component for Open MPI [START_REF] Gabriel | Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation[END_REF]. Such a component is based on MPI Tool Information Interface which is a low-level API of MPI to query performance variables of the MPI runtime systems. For a given MPI Process, such interface is able to gather the number of messages and the amount of data exchanged with other ranks. However, it is very low level and requires a deep understanding of the MPI Tool Information Interface. In this paper, we leverage on this previous work to provide a higher-level and more abstracted introspection library for MPI. It enables the application to query its specific state through a simple API during the execution. In particular the proposed library features the notion of monitoring sessions which can be suspended and resumed for monitoring only specific part of the code. Different sessions can overlap, monitor specific types of communications (point-to-point, collective or one-sided) and be attached to a specific communicator enabling a precise understanding of the behavior of the application during the execution. It provides a C and Fortran interface. Last, we monitor communication once a collective has been decomposed into its point-to-point messages: this unique feature enables to gather the affinity between processes (i.e. the amount of data that is exchanged and hence how close should each processes be mapped to each other).

The goal of this paper is to describe the proposed introspection library and to show that it enables to optimize the communication time of parallel MPI applications. We detail the notion of session, its usage and a specific use-case (dynamic rank reordering). We provide extensive experiments to compare it with hardware counters, assess its low overhead, and show how to optimize communications through rank reordering.

This paper is organized as follows. Related work is presented in Section 2 and the background in Section 3. In Section 4 we describe in detail the library. The dynamic rank reordering technique and algorithm are depicted in Section 5. We present the experimental results in Section 6. We discuss issues and problems in Section 7 and we give our concluding remarks in Section 8. The artifact description is given after the References in Section ??.

Related Work

Monitoring an MPI application can be achieved in many ways but in general relies on intercepting the MPI API calls and delivering aggregated information. We present here some examples of such tools.

PMPI is a customizable profiling layer that allows tools to intercept MPI calls. Therefore, when a communication routine is called, keeping track of the processes involved and the amount of data exchanged is possible. This approach has drawbacks, however. First, managing MPI datatypes is awkward and requires a conversion at each call. Also, PMPI cannot comprehend some of the most critical data movements, because an MPI collective is eventually implemented by point-to-point communications, and yet the participants in the underlying data exchange pattern cannot be guessed without knowledge of the collective algorithm implementation. A reduce operation is, for instance, often implemented with an asymmetric tree of point-to-point sends/receives in which every process has a different role (i.e., root, intermediary, and leaves). Known examples of stand-alone libraries using PMPI are DUMPI [START_REF] Curtis L Janssen | A simulator for large-scale parallel computer architectures[END_REF] and mpiP [START_REF] Jeffrey | Statistical scalability analysis of communication operations in distributed applications[END_REF].

EZtrace [START_REF] Trahay | Selecting points of interest in traces using patterns of events[END_REF] is a tool for analyzing and monitoring MPI programs. These tools launches the MPI executable and capture all point-to-point communication in a set of files. Each file corresponds to a process and describes its communication behavior with the other processes. However, it only allows for post-mortem and static analysis of the trace. It is not possible for the MPI program to monitor itself and change its behavior at runtime according to the communication pattern. Similarly to PMPI-based tools, this approach has an API-level granularity, and is unconcerned with detailed information about collective calls.

Another tool for analyzing and monitoring MPI programs is Score-P [START_REF] Knüpfer | Score-P: A Joint Performance Measurement Run-Time Infrastructure for Periscope, Scalasca, TAU, and Vampir[END_REF]. It is based on different but partially redundant analyzers that have been gathered within a single tool to allow both online and offline analysis. It uses Periscope and TAU, live profiling tools that evaluates performances and tries to track bottlenecks in both communication and memory accesses. Score-P relies also on Scalasca [START_REF] Geimer | The scalasca performance toolset architecture[END_REF] and Vampir [START_REF] Knüpfer | The vampir performance analysis toolset[END_REF] for post-mortem analysis of event traces, with a graphical representation. Score-P relies on MPI wrappers and call-path profiles for online monitoring. Nevertheless, the application monitoring support offered by these tools is kept outside of the library, which means access to the implementation details and the communication pattern of collective operations once decomposed is limited.

PERUSE [START_REF] Keller | Implementation and Usage of the PERUSE-Interface in Open MPI[END_REF] takes a different approach, in that it allows the application to register callbacks that will be raised at critical moments in the point-to-point request lifetime. This method provides an opportunity to gather information on state-changes inside the MPI library and gain detailed insight on what type of data (i.e., point-to-point or collectives) is exchanged between processes, as well as how and when. This technique has been used in [START_REF] Brown | Tracing Data Movements Within MPI Collectives[END_REF][START_REF] Keller | Implementation and Usage of the PERUSE-Interface in Open MPI[END_REF].

In [START_REF] Bosilca | Online Dynamic Monitoring of MPI Communications[END_REF], a subset of the authors of this paper proposed a low-level MPI monitoring component for Open MPI [START_REF] Gabriel | Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation[END_REF]. This paper presented the design and evaluation of a communication monitoring infrastructure developed in the Open MPI software stack and able to expose a dynamically configurable level of detail about the application communication patterns. This component combines the advantages of the MPI Tool Information Interface interface to configure a flexible low-level implementation to provide efficient and dynamically configurable message-passing monitoring capabilities. As it is a component inside the Open MPI stack, it is able to decompose collective operations into to their point-to-point expression: the monitoring component is plugged into the stack once messages are buffers to be sent to another MPI process. This is a strong advantage compared to all other approaches as it provides a better view of the actual messages exchanged during a collective communication. Moreover, of all types of communications supported by the MPI-3 standard (including one-sided communications and I/O).

Inria 3 Background

The proposed library is based on a monitoring interface [START_REF] Bosilca | Online Dynamic Monitoring of MPI Communications[END_REF] developed by a subset of the authors. As presented above, this component was developed in Open MPI and used the MPI Tool Information Interface.

The Open MPI Project [START_REF] Gabriel | Open MPI: Goals, Concept, and Design of a Next Generation MPI Implementation[END_REF] is a comprehensive implementation of the MPI 3.1 standards [6] that was started in 2003, taking ideas from four earlier institutionally-based MPI implementations. It is developed and maintained by a consortium of academic, laboratory, and industry partners, and distributed under a modified BSD open source license. It supports a wide variety of CPU and network architectures that is used in the HPC systems. It is also the base for a number of vendors commercial MPI offerings, including Mellanox, Cisco, Fujitsu, Bull, and IBM. The Open MPI software is built on the Modular Component Architecture (MCA) [START_REF] Barrett | Analysis of the Component Architecture Overhead in Open MPI[END_REF], which allows for compile or runtime selection of the components used by the MPI library. This modularity enables experiments with new designs, algorithms, and ideas to be explored, while fully maintaining functionality and performance. In the context of this study, we take advantage of this functionality to seamlessly interpose our profiling components along with the highly optimized components provided by the stock Open MPI version. MPI Tool Information Interface, is an interface that has been added in the MPI-3 standard [START_REF]MPI: A Message-Passing Interface Standard[END_REF]. It allows MPI developers, or third party, to offer a portable interface to different tools. These tools may be used to monitor applications, measure its performances, or profile it. MPI Tool Information Interface is an interface that eases the addition of external functions to a MPI library. It also allows the user to control and monitor given internal variables of the runtime system. In [START_REF] Bosilca | Online Dynamic Monitoring of MPI Communications[END_REF], a component was developed within this interface to precisely record the message exchanges between nodes during MPI applications execution. This component is available within Open MPI since version 4.0. The number of messages and the amount of data exchanged are recorded, including or excluding internal communications (such as those generated by the implementation of the collective algorithms). This component can be activated at launch-time though --mca pml_monitoring_enable value on the mpirun command line to set the monitoring mode where value can be: 0 monitoring (and component) is disabled.

1 monitoring is enabled, with no distinction between user issued and library issued messages.

≥ 2 monitoring enabled, with a distinction between messages issued from the library (internal) and messages issued from the user (external).

However, this component is extremely low level. It requires to manipulate low-level features of the MPI Tool Information Interface and does not provide high-level semantics such as sessions or easy ways to gather monitored results from the different nodes.

Precise monitoring can be used to optimize process placement. Process placement is an optimization strategy that takes into account the affinity of processes (represented by a communication matrix) and the machine topology to decrease the communication costs of an application [START_REF] Hoefler | An overview of topology mapping algorithms and techniques in high-performance computing[END_REF]. Various algorithms to compute such a process placement exist, one being TreeMatch [START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF] (designed by a subset of the authors of this report). We can distinguish between static process placement which is computed from traces of previous runs, and dynamic placement, that can be implemented by rank reordering, computed during the application execution (See experiments in Section 6).

Library Description

General Description

The main interest of the MPI_Monitoring Library is to provide a higher-level interface by allowing the user to simply monitor its code and access the collected data. It mostly rely on low-level MPI Tool Information Interface features, mainly performance variable, that remain hidden to the user.

The MPI_Monitoring Library only defined one opaque datatype, MPI_M_msid (which stands for Monitoring Session IDentifier), that can only be used through the function of this library. They allow the user to create and act on monitoring sessions attached to a given communicator. While the session is active, the number and size of the messages exchanged between processors of the communicator are recorded and can later be obtained. Note that it also records communications that do not go through the communicator, as long as both processors belong to it. For example, a monitoring session attached to the communicator that splits even and odd processors will record all exchanges between processors 0 and 2, even if some communications use the communicator MPI_COMM_WORLD.

All these functions are prefixed by MPI_M_ and their name does not contain any other capital letter, to respect the MPI convention. All functions are thread-safe. However they are not interrupt-safe (due to non-interrupt-safe MPI routines). They must be used in a proper environment that can be set using init and finalize, and both must be called between MPI_Init and MPI_Finalize as well. As other collective MPI routines, the MPI_Monitoring Library functions must be called by all processes of the given communicator, the only exception being get_info. Note that init and finalize could be called multiple times as long as their environment do not overlap, but it is simpler to call them along with MPI_Init and MPI_Finalize.

Within the environment, the user can manage monitoring sessions using either start, suspend, continue or reset. It allows the user to precisely define the portion of the code to watch. The unique initial start put the session in its "active" state, and must match a final suspend. The monitoring session can be put in a "suspended" state using suspend, and later be put back in the "active" state using continue. The code is only watched while the session is in the "active" state. The function reset can be used on a session in the "suspended" state to put the data it contains back to zero. Note that if the session is in the "suspended" (resp. "active") state, suspend (resp. continue) cannot be called again. Another important feature is that sessions are completely independent and hence different sessions can overlap similar part of the code is necessary.

It is left to the user to properly use free on each started monitoring session to avoid memory leak. The recorded data can be copied in the user's buffers through get_data, allgather_data and rootgather_data.

The function get_data will copy the data specific to the process that called it into a buffer of this process. Even if it seems to be a function that could be called by only one process, it must be called by all that belong to the communicator of the session. It has two output parameters. one to get the amount of data exchanges sent to the other processes an other for the number of sent messages. However, parameters can vary among processes, and the special value MPI_M_DATA_IGNORE can be used to get rid of the unwanted data. The function allgather_data is equivalent to a call to get_data followed with a call to MPI_Allgather, such that all processes receive the collected data from all processes as a 2D matrix represented by a 1D array in row major format. The function rootgather_data act similarly, but it takes an additional parameter, root, and only processes whose rank is root will receive the data.

It is left to the user to give large enough buffers to store the recorded data. The minimal Inria required size can be obtained with the function get_info. The user can also use flush and rootflush to directly save the data in a file. Those functions act similarly to get_data and rootgather_data, but they need a proper filename instead of buffers. All functions meant to obtain data require a flag argument to specify which of kind of communication the data is wanted (point-to-point, collective, one-sided or any combination of the previous options). Note that some collective MPI routines might generate point-to-point zero-length messages.

As accessing the data uses collective MPI routines that the user does not want to record along with dynamic memory allocation, the data can only be accessed while the session is in the "suspended" state and not already freed. Note that data is stored using arrays of unsigned long int, and therefore a code with a lot of communications may cause overflows.

Usage

To properly use monitoring sessions, one should call MPI_M_init right after MPI_Init and MPI_M_finalize right before MPI_Finalize to set a proper environment. Then, create a different MPI_M_msid variable, automatically allocated, for each monitoring session wanted, in a scope that contains both the code to monitor and where the data need to be used. These sessions are completely independent from one another, therefore monitored portions of the code can overlap. Start the recording with MPI_M_start and stop it with MPI_M_suspend. If on wants to interrupt the monitoring session and then restart it, s/he can use MPI_M_suspend and MPI_M_continue, in this order. Once the monitoring is done, data can be obtained through multiple functions, it depends on how the data will be used. Sessions can be freed when the data they contain is no longer needed. A simple example will follow in Listing 2.

Complete API

For the sake of comprehensiveness, we provide here the complete function list as well as the different constant that can be used. The MPI_Monitoring Library comes with an interface that allows its usage within a Fortran code. The datatype MPI_M_msid is replaced by the type integer, and each function possesses an additional parameter which is used to transmit the return value.

MPI_M_init

Common Example

Here is an example to find out how MPI uses point-to-point communications to implements MPI_Barrier. Note that this code is not fully complete as it does not check any return value, but it gives an idea on how this library can be used.

Listing 2: Produces a file that described all point-to-point messages used to implement MPI_Barrier

RR n°9292

MPI_Barrier ( MPI_C OMM_WO RLD ) ; MPI_M_suspend ( id ) ; M PI _M _ ro ot f lu s h ( id , 0 , " barrier " , MPI_ M_P2P_ ONLY ) ; MPI_M_free ( id ) ; MPI _M_fin alize () ; MPI_Finalize () ; return 0; } Note that the only portion of the code that is being watched is between the calls to MPI_M_start and MPI_M_suspend, and this portion could possibly contain anything else.

Case with Several Collectives in a Program

As said above, the MPI monitoring component sees collectives once they have been decomposed into point-to-point messages. However, it is not able to distinguish between different calls: the monitoring aggregates all the sent operation into the same MPI_T variable. However, thanks to the sessions we are able to solve the problem of being able to distinguish which send operation belong to which collective. Indeed, it is sufficient to create one session per MPI collective call the programmer wants to distinguish (e.g. two MPI different collective calls). In this case, the amount of data sent will be copied and stored in different buffers within the introspection library. As the library is designed such that the sessions can overlap or be nested, any kind of situations can be monitored thanks to the session mechanism.

Rank Reordering with Introspection Monitoring

Here, we explain how the introspection monitoring can be used to compute an optimized communicator where ranks are reordered and that allows for optimizing communications.

Rank reordering is intended to be used in the case where one want, at some point of the execution, to optimize the application locality but cannot migrate processes because they are not allocated to resources in the same address space. Instead of migrating processes, rank reordering is a dual approach, where the rank assigned to each process is changed and in some case data is exchanged between processes. Similarly to load balancing, The cost of exchanging data might impair the gain of rank reordering. Finding the good trade-off is out of the scope of this paper and is, for now, left to the designer of the application.

Communicator reordering was proposed in [START_REF] Mercier | Improving mpi applications performance on multicore clusters with rank reordering[END_REF] for the case where the application is first monitored and then re-executed. Here, the algorithm described in Figure 1, does not require to restart the application.

Assume that you have a parallel program that performs an iterative computation using a function called compute_iteration. This function takes two parameters the (iteration number and a communicator). The first iteration (line 4) is monitored by our tool. Then, the number of data exchanged between all the ranks (size_mat) is gathered on rank 0. We compute a new mapping 1 of the processes in order to minimize communication cost (line 8). The output of this call is an array -k-of n integers (n is the number of MPI processes: the size of the original communicator). The array k describes an optimized mapping -based on the topology of the machine and the gathered communication pattern of the application -in order to minimize the communications. More precisely, k is such that in order to minimize communication cost, Process i should be executed on the process the k[i]. This array is then broadcast among all the MPI processes (line 10). A new communicator (opt_comm) is then computed such that MPI process of rank i in the original communicator gets rank k[i] in opt_comm (line 11). Indeed, as the second parameter (color) of MPI_Comm_split is the same for all ranks, all MPI processes are put in the same communicator. It might be then required to redistribute the data (line 12) before executing the remaining iterations on the optimized communicator: this requires to know the vector k on all ranks such that any useful data is sent from rank k[i] to rank i in the original communicator. The tricky part of the algorithm is actually line 11. Indeed, the fact that to optimize communication, process k[i] is mapped by TreeMatch onto processing unit i is equivalent of having rank i in the original communicator becomes rank k[i] in the optimized communicator.

Experimental Results

The experiment of Sec 6.1 was performed on two nodes having an Infiniband EDR card and a Xeon 6140 Processor at 2.3 GHz.

We conducted our experiments with parallel applications on an OmniPath 100 Gb/s cluster of the PlaFRIM experimental testbed. Each node features two Haswell Intel Xeon E5-2680 v3 with 12 cores (2.5 GHz) each. Each node has 128 GB of 2133 MHz memory (5.3 GB/core).

If not detailed, for each experiments we use one MPI process per core or 24 MPI processes per node. This enables us to test the scalability and the overhead of the proposed solution.

The source, documentation and test of the library can be downloaded on the Inria gforge using this url: svn checkout svn://scm.gforge.inria.fr/svnroot/mpi-introsp-mon.

Comparison with Hardware Counters

In order to assess if the monitoring actually measures what is sent to the network, we have done the following experiment. An MPI program with 2 processes on different nodes send a random amount of data (between 1 and 800 Kb) and then sleeps between 50 and 1000 ms. In the same program, a thread monitors the network traffic. We use two kinds of monitoring systems: the library we present in this paper and the hardware counters of the network card of the machine. On Linux, the number of bytes sent by an Infiniband card is available in the /sys/class/infiniband/.../counters/port_xmit_data file. The number read in this file has to be multiply by the number of planes of the card (in general 4): see [START_REF]Understanding mlx5 Linux Counters and Status Parameters[END_REF] for more details. The monitoring frequency is 10 ms and we use the reset features of the library session to monitor only what has happened between two measurements. In Fig. 2, we show the results for the Hardware counters (top) and our MPI introspection monitoring (bottom). It is a time series where the x-axis represents the time (in seconds) and the y-axis the amount of data that is monitored (in Kb). In both cases we see that the monitoring sees precisely what is actually sent to the network and the time difference is barely visible. This means that, once the introspection monitoring library has monitored some data they are almost immediately sent to the network. However, the advantage of the monitoring library compared to the hardware counter method is twofold. First, it is portable: it does not require to find the right file to be read on the target machine (in the /sys pseudo-filesystem), if only it exists. Second and more importantly, it provides a higher semantic as with the introspection monitoring, the rank of the sender and the receiver is attached to the sent data, which is impossible to see with the hardware counters of the network card.

Overhead

In order to measure the effective impact caused by the library on the monitored code, a simple test was used. It consists of a small code that is being run twice, one with and one without monitoring, both runs being timed. The code simply performs a reduce, transferring an arbitrary amount of data through MPI_COMM_WORLD. Different number of MPI processes are used 48 (2 nodes), The results are shown in Fig. 4. The error bar is the 95% confidence interval computed with the student T test using unpaired measures and unequal variance. q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 2 4 10 0 10 1 10 2 10 3 10 4 Size (byte) Time Difference (µs) NP q q q 192 48 96

Figure 4: Impact of the library on the monitored code (x log-scale): time difference between monitoring execution and non-monitoring execution. (positive values mean that execution with monitoring is slower than without). Each point is the difference of the average of 180 measurements and the error bar is the 95% confidence interval (unpaired T test with unequal variance).

We plot only the data for small message size as this is in these cases that the overhead can be seen. Results show that most of the time the overhead is not statistically significant. In the worst case, the monitoring overhead is less than 5 µs.

Collective Optimization

In order to show the usefulness of a monitoring system being able to decompose collective communication into their point-to-point expression, we have designed an experiment that features rank reordering as explained in Section 5 using the communication matrix built with the monitored point-to-point messages. Here, we have taken two collective operations. A "one to all" collective (Broadcast) and a "all to one collective (Reduce). If monitored at a high-level (before the decomposition into point-to-point), it would not be possible to see the individual messages that are sent to execute the collective operation. Here, thanks to the monitoring library, each individual message is recorded, then ranks are reordered using a process placement algorithm we have developed (TreeMatch [START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF]). The goal is to re-arrange the ranks, such that, the ones that communicate the most are close to each other on the target machine. The results are depicted in Fig. 5. We plot the collective operation runtime versus the buffer size. The time "without monitoring" is obtained by mapping the ranks in a round-robin fashion as it would be done without any specification given by the user. Thanks to the precise monitoring, we are able to optimize the collective communication runtime for all the buffer size. For the reduce operation we see that, for 96 MPI processes (4 nodes), the runtime is reduced from 15.16 s to 7.57s for 2.10 8 integers. For 48 MPI processes (2 nodes), the runtime reduction is 8.28s to 5.59s for 2.10 8 integers. For the broadcast operation, the reduction is 16.34s to 10.24s for 96 ranks and 2.10 8 integers. For 48 processes, the runtime is reduced from 6.21s to 3.35s for 2.10 8 integers. For 192 MPI processes, the runtime is reduced form 11.92s to 5.01s (resp. 15.11s to 4.46s) for the reduce operation (resp the broadcast) for 2.10 8 integers.

Rank Reordering Micro-Benchmark

To exemplify the possibility of doing runtime optimization through the introspection monitoring library we have designed a benchmark where group of ranks perform an MPI_Allgather at each iteration. The processes mapping is such that for each group of ranks, their communicators span different nodes. Then, we perform a rank reordering for each group to optimize their data locality. Results are shown in Fig. 6. We display a heat map for three different number of processes (48, 96 and 192 i.e 2, 4 and 8 nodes). On the x-axis we have the size of the data (in number of integers) and on the y-axis the number of iterations. We measure the time t1 for n Inria iterations then the time t2 for the reordering the process and the time t3 of n iterations after the reordering2 . Here, to show the gain of the reordering we measure only the communication time and we compute the percentage of gain, taking into account the reordering overhead, as 100(t1 -(t2 + t3))/t1. As expected, we see that when the number of iterations is low or when the buffer size is small, the percentage of gain is lower than 0%. This means that the time to reorder plus the time to execute loops after reordering is greater than the time without reordering. In all these cases, the communication time is very small (never greater than 2 ms) and much higher than the reordering cost. However, as soon as the buffer size is large enough or the number of iterations is high, the reordering cost is amortized enabling a better execution time than the non-reorder case alone. In the best cases ,the gain is more than 95% (almost a 2-time improvement): this is the case for 48 processes and 100 iterations or more for the 100 000 MPI_INT buffer size (or 1000 iterations or more for the 10 000 buffer size).

Rank Reordering on Conjugate Gradient

The conjugate gradient algorithm is an iterative algorithm that computes the solution of a system of linear systems whose matrix is symmetric and positive-definite. Such algorithm is perfectly suited for the reordering use-case as the communication pattern of each iteration is the same. Hence, we can monitor the first iteration, build the communication matrix, compute a new mapping and apply a rank reordering as explained in Sec. [START_REF] Cores | An application-level solution for the dynamic reconfiguration of mpi applications[END_REF].

In this paper, we have taken the conjugate gradient code from the NAS parallel benchmark 3.3 [START_REF]The nas parrallel benchmarks[END_REF] called CG. We have designed two functions one to start the monitoring and one to compute the reordering. The CG code uses only the MPI_COMM_WORLD communicator. In order to apply the reordering we have changed this to a global variable which is assigned to MPI_COMM_WORLD at the beginning of the program and to the new computed communicator after the reordering phase has been done. To avoid redistributing the data, we have used the fact that the CG code has an initialization phase that does one iteration of the conjugate gradient algorithm. We monitor this initialization phase to compute the optimized communicator. In order to be fair, the time of the reordering is added to the whole timing of the application.

In the NAS suite, the number of processes of the CG code is a power of two. We use three values (64, 128, 256) and 3, 6 and 11 nodes respectively. As the number of cores per node is 24, some cores are spared. Hence, we use and compare three different initial mappings: a random mapping, a round-robin mapping (RR) where rank i is mapping on the i th leftmost core and standard where no binding is used.

Also, to avoid interference with the other running applications, we have used nodes that are on the same 100 Gb/s switch.

Results are depicted in Fig 7 . We show the gain of the reordering vs. without reordering (ratio greater than 1 show a gain for the reordering case). On the X-axis, we vary the number of MPI processes (from 64 to 256). Each bar is different class from B (small problem size) to D (large problem size) 3 . Each graph has three rows that show three types of initial mapping described in the previous paragraph (Random, Round-Robin or Standard). In Fig. 7a the y-axis is the ratio of execution time. We see that all the ratios are greater than 1, meaning that the reordering is beneficial. In general the ratio is decreasing with the problem size (the class), this is due to the fact that the larger the problem the longer the execution time and, even if the gain difference is larger, the smaller the ratio. To see what is the actual gain in terms of communication, we have measured the gain of the reordering but only for the communication time to do so we have added a timer that measures the time spent by rank 0 in MPI calls. The results are shown in Fig 7b . In this case the ratios are much greater (both timings are reduced by the same amount) and show, in some cases, up to a 1.9x improvement. Another interesting fact is that in case of the random mapping the gain is not better than the round-robin mapping. This is due to the fact that the remapping algorithm we use (TreeMatch) is sensitive to the initial mapping: in the case of the random initial mapping it is not able to provide a reordering as good as with the round robin initial mapping. This is an issue out of the scope of the paper and will be tackled in future work.

Discussion

In most of our experiments, we have 1 MPI process per core. However, having many MPI processes per nodes does not help to exhibit communication optimization. Hence, we think that our results would show even more gain in the case where we use more nodes and less MPI process per nodes. Apart from rank reordering, being able to understand how the application communicates can be useful in many other cases. For instance, in [START_REF] Cores | An application-level solution for the dynamic reconfiguration of mpi applications[END_REF] we used the dynamic and introspection monitoring to compute the communication matrix during the execution of an MPI application. The goal was to perform elastic computations in case of node failures or when new nodes are available. The runtime system migrated MPI processes when the number of computing resources changed: the placement of such processes was computed according to the topology and the communication matrix. Recently, in [START_REF] Tseng | Towards Portable Online Prediction of Network Utilization using MPI-level Monitoring[END_REF], we use the introspection monitoring to detect and predict network usage using machine learning technique. Here, the goal is to determine when the network is under-utilized in order to fetch checkpoint to the storage.

Reordering is interesting if the mapping algorithm is fast enough. In the experiments we have shown that reordering 256 MPI Processes has a negligible impact on the whole duration (up to 0.02 seconds). One might wonder what happens in the case of a larger number of processors. In table 1 we display the mapping computation time of TreeMatch for very large settings (up to a communication matrix of order 65 536). We see that even for such large input size the time to compute the reordering is less than 100s.

Conclusion

Being able to query the state of the MPI software stack is very important as it enables runtime optimization. In particular this enables to optimize the way communications are carried out on a distributed memory parallel machine. In this paper we have proposed an introspection library. This high-level library features sessions that allows for watching specific part of the application, is able to see how collectives are decomposed into point-to-point communications, provide a C as well as a Fortran API and is freely available. We have carried-out experiments that show that the library captures precisely what is sent to the network card with a very small overhead. Thanks to its ability to see how collective are decomposed in point-to-point, we have been able to optimize tree-based collective at runtime. Last, we have presented a dynamic rank reordering algorithm and show that, as long as the communication cost is large enough, the reordering cost is amortized leading to almost 2-time performance improvement.

This library is based on a monitoring module available only in Open MPI (version 4.0 or later). The advantage of such a library is that it hides the low-level MPI tool variables and command. Hence, if a monitoring module would be developed in another MPI implementation (such as MPICH), our proposed library could easily be ported such implementation enabling a better portability.

  MPI_M_start ( MPI_COMM_WORLD , & id ) ;

8 kFigure 1 :

 81 Figure 1: Reordering Algorithm for Iterative Computation

Figure 2 :

 2 Figure 2: Hardware Counters vs. Introspection Monitoring (time series)

Figure 3 :

 3 Figure 3: Hardware Counters vs. Introspection Monitoring (cumulative)

  MPI_Reduce (MPI_MAX) walltime (x and y log-scale) for 48, 96 and 192 ranks and various buffer sizes. Binary Tree algorithm. MPI_Bcastwalltime (x and y log-scale) for 48, 96 and 192 ranks and various buffer sizes. Binomial Tree algorithm.

Figure 5 :

 5 Figure 5: MPI Collective Optimization

Figure 6 :

 6 Figure 6: Heatmap of the gain (in percent) of using reordering while varying the number of iterations and the buffer size. Green values: reordering pays off. Red values: reordering overhead is too high.

Figure 7 :

 7 Figure7: NAS benchmark conjugate gradient reordering gain. The gain is the ratio of the nonreordered case vs the reordered case: ratio greater than one means that the reordering is faster. Y-axis in log-scale. We plot different class of the CG kernel (B to D) and each row is a different initial mapping (random, round-robin or standard).

Table 1 :

 1 Reordering computation time for large input size

	Com Matrix size	8 192 16 384 32 768 65 536
	Reordering time in s	2.6	6.3	20.9	88.7

RR n°9292

In the experiments, we will use the TreeMatch algorithm[START_REF] Jeannot | Process Placement in Multicore Clusters: Algorithmic Issues and Practical Techniques[END_REF], but any other relevant algorithm can be used.Inria

timings are the average of the maximum time on all the ranks of 6 runs RR n°9292

We do not show the class A as the timing are very small (less than 0.1 s) and the reordering is not useful Inria

avenue de la Vieille Tour 33405 Talence Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgment

We would like to thank Guillaume Mercier for fruitful discussion on the reordering strategy. The PlaFRIM experimental testbed is being developed with support from Inria, LaBRI, IMB, and other entities: Conseil Régional d'Aquitaine, FeDER, Université de Bordeaux, and CNRS.