Jérémy Castéra

Pierre Clément

THE GENETIC DETERMINISM OF HUMAN PERFORMANCES. A COMPARISON BETWEEN TEACHERS' CONCEPTIONS IN FINLAND AND FRANCE

Keywords: Scientific knowledge, values, innatism, human genetics, teachers, Finland, France, PISA

Finland has the best mean sciences scores among the OECD countries while France is in the OECD average (PISA 2006). Nevertheless, when measuring interactions between knowledge and values in teachers' conceptions, the comparison between the two countries shows surprising results. In the context of the European research project Biohead-Citizen, in-service and pre-service teachers filled out a questionnaire including 31 questions related to the genetic determinism of human performances. The samples (732 in France, 306 in Finland) comprised Primary School teachers and Secondary School Biology and Language teachers. The answers to the questions dealing with only scientific knowledge, or with only social values, did not differ with the country. Nevertheless, there are very significant differences for the interactions between knowledge and values mainly related to innatism: for instance, Finnish teachers more agree with the proposition "there are genetic factors in parents that predispose their children to be good in school" (or "good violinists"); or with "It is for biological reasons that women more often than men take care of housekeeping". Our results are analysed with different statistical tests including multivariate analyses. They are then discussed, taking into account the respective content of school textbooks in the two countries.

Introduction: biological and social context

The debate between nature and culture is outdated, both being necessarily in constant interaction [START_REF] Atlan | La fin du "tout génétique[END_REF][START_REF] Jacquard | L'avenir n'est pas écrit[END_REF], Kupiec & Sonigo 2001[START_REF] Lewontin | La triple hélice. Les gènes, l'organisme[END_REF]. This interaction between the genome and its environment (called "epigenetics": [START_REF] Morange | Quelle place pour l'épigénétique[END_REF] is a new paradigm in biology: is it introduced in the school curricula? The European research project BIOHEAD-Citizen (2004-2008) worked on this question, analysing the syllabuses and school textbooks in 19 countries, as well as the teachers' conceptions on this topic. This is a "question vive" with an important social challenge. The philosopher [START_REF] Canguilhem | Idéologie et rationalité dans l'histoire des sciences de la vie[END_REF] defined the explanation of complex social features by only the human genes as an ideology inside Life Sciences. Some psychologists, [START_REF] Keller | In genes we trust: The biological component of psychological essentialism and its relationships to mechanisms of motivated social cognition[END_REF] in Germany or Dambrun (2007) in France, focused the link between this ideology and intolerant attitudes as sexism or racism. Can we find some link between innatism, sexism and racism in teachers' conceptions?

While [START_REF] Simonneaux | Les bio-technologies de la reproduction animale chez les bovins : approche didactique et muséologique[END_REF], as well as Abou [START_REF] Tayeh | La Biologie entre opinions et connaissances : Les conceptions d'étudiants libanais sur le cerveau. in L'actualité de la recherche en didactique des sciences et des techniques[END_REF], showed that students' opinions are more difficult to change than their scientific knowledge, [START_REF] Kochkar | Les déterminismes biologiques. Analyse des conceptions et des changements conceptuels consécutifs à un enseignement sur l'épigenèse cérébrale chez des enseignants et des apprenants tunisiens[END_REF] showed that some knowledge about the cerebral epigenesis decreases the beliefs in innatism. Can we find a link between teachers' opinions and their scientific knowledge? To answer to this question, we decided to focus our analysis on two countries evaluated as very different by PISA (2006): Finland obtained the best sore on the scale of the "scientific literacy" and France obtained a score just under the OECD average. Concerning the topic "human genetics", and its possible link with ideologies as innatism, sexism or racism, are there differences among the French and Finnish teachers' conceptions?

The innatism is still present in the syllabuses and textbooks of the both countries: [START_REF] Castéra | Genetic determinism is school textbooks: a comparative study conducted among sixteen countries[END_REF] showed a great frequency of the words "genetic program" in French biology textbooks for student 14-16 years old and even more in Finnish biology textbooks for students 16-19 years old. What are the teachers' conceptions on innatism in these two countries?

Rationale: research questions

Are there differences among Finnish and French teachers related to scientific knowledge on human genetics as well as on cerebral epigenesis? Are there differences among Finnish and French teachers related to ideologies as innatism, sexism or racism?

Are there interactions between scientific knowledge and values of Finnish and French teachers?

Methods

Questionnaire

The questionnaire included 31 questions dealing with the topic "human genetics". Some of them concerned sexist or racist positions, some others the innate determinism of human beings features, and the others the scientific knowledge related to human genetic and cerebral epigenesis. Most of the questions of our questionnaire are built to evaluate possible interaction between K and V (knowledge and values). The values are linked to the sexist ideology vs equality between men and women, to racist ideology when considering a "genetic superiority" of some ethnic groups, or only to the ideology of innatism, as the genetic determinism of human features or performances. The end of the questionnaire was related to personal characteristics of each responder (gender, age, religious or political opinions, etc.). The questionnaire has been built during 2 years, with a pilot test and other processes to select, to translate and to validate the questions [START_REF] Clément | Biology, Health and Environmental Education for better Citizenship: teachers' conceptions and textbook analysis in 19 countries[END_REF].

Samples 1038 teachers filled in the questionnaire in Finland (306) and in France (732). In each country, six categories of samples were defined in a well-balanced way: in-service teachers of primary schools (InP), in-service teachers of secondary schools in biology (InB) or in language (InL), pre-service teachers of primary (PreP) or secondary schools in biology (PreB) or in language (PreL).

Data analysis

Data from these questionnaires are handled by classical statistical analyses as well as by multivariate analyses (Principal Component Analysis, Between-analysis and Principal Component Analysis with respect to orthogonal Instrumental Variables). The measure of significance was done by Chi² test or by a Monte Carlos test from the between-class analyses [START_REF] Munoz | Des méthodes statistiques originales pour analyser les conceptions d'enseignants de plusieurs pays à partir d'un questionnaire sur des questions vives[END_REF][START_REF] Munoz | Teachers' conceptions of nature and environment in 16 countries[END_REF].

Results

The Principal Component Analysis shows strong inter-individuals differences mainly linked to the questions dealing with innatism (component 1) but also to some questions related to scientific knowledge (component 2). The orthogonality of the two components shows their relative independence.

A between-class analysis differentiating the six samples shows that the scientific knowledge differentiates biologists from other teachers in both countries, in the same way for each country.

The between analysis differentiating the two countries shows very clear differences among the teachers of the two countries (figure 1a), differences that are very significant (Monte Carlo test: figure 1b, p< 0.0001). In this analysis, the questions differentiating the most the two countries are listed in the table 1. The question that has the most weight in this "effect country" is the question B10 (figure 2): "There are genetic factors in parents that predispose their children to be good in school"? Only 3% of Finnish teachers disagree (while 61% of French teachers do) ; 29% of Finnish teachers agree, 79% agree or rather agree (while only 3% and 18% of French teachers do). The difference between Finland and France is highly significant (Chi² test, p-value < 2.2e -16 ).

(a) (b)

A The table 1 lists the 13 questions which significantly differentiate the Finnish and French teachers' conceptions. The less but significant difference is dealing with racism: B35 (figure 3): "Ethnic groups are genetically different and that is why some are superior to others." Only 78% of Finnish teachers disagree with this proposition, while 93% of French teachers do. The difference is clearly significant (Chi2 test after the Bonferroni's correction: p-value < 0.001).

Table 1 -List of the 13 questions differentiating the Finnish and French teachers' conceptions (from the between analysis presented in figure 1). For each question, it was a Likert' scale of 4 boxes, from "I agree" to "I don't agree". The figure 2 is illustrating the most important difference (B10) and the figure 3 the less but still significant difference (A35). (…) = The answers to the other 18 questions are not significantly differentiating Finnish and French teachers' conceptions. D1 B10 -0,62 There are genetic factors in parents that predispose their children to be good in school B20 -0,59 There are genetic factors in parents that predispose their children to become very good violinists B4 -0,57 Human social behaviour is partly directed by genes B14 -0,51 There are genetic factors in parents that predispose their children to be aggressive A38 -0,50 It is for biological reasons that women more often than men take care of housekeeping A24 -0,40 If clones of Mozart could be obtained, they all would be excellent musicians A3 -0,40 If clones of Einstein could be obtained, they all would be very intelligent B11 -0,36 There are genetic factors in parents that predispose their children to become homosexual B8 -0,35 There are genetic factors in parents that predispose their children to become alcoholics A31 -0,27 When a couple has already had two girls, the chances that their third child be a boy are higher A36 -0,21 Men might be more able to think logically than women, because men might have different brain bilateral symmetry A35 -0,17 Ethnic groups are genetically different and that is why some are superior to others (…) (…) A30 + 0,20 It is important that there are as many women as men in parliaments

The answers to 18 questions, from the 31 ones related to the topic of biological determinism of human features or performances, don't differentiate Finnish from French teachers: the questions focused on only scientific knowledge (except A31: table 1); those related to identical twins and those related to interactions between scientific knowledge and values dealing with sexism or feminism., with the important exception of two of these questions (listed in the table 1): A38 ("It is for biological reasons that women more often than men take care of housekeeping") and A36 ("Men might be more able to think logically than women, because men might have different brain bilateral symmetry"). The question A30, dealing with only social values (the number of women in the Parliament), is also significantly differentiating the Finnish and French teachers' conceptions.

The answers that differentiate the most Finnish from French teachers are linked to innatism. They are mainly dealing with the questions of the genetic factors of parents that predispose their children to be good at school (B10), or very good violinist (B20), or aggressive (B14), or homosexual (B11) or even alcoholic (B8). The Finnish teachers' answers could be a priori interpreted not as innatism, but as telling with the "genetic part" in the double determinism of these features or performances. The same argument could be proposed to interpret Finnish answers to the question B4 (table 1), more agreeing with the proposition: "Human social behaviour is partly directed by genes". Nevertheless, the answers to the two questions related to clones (A24 and A3: table 1) clarify the innatism of many Finnish teachers. Considering that clones of Einstein (A3) or of Mozart (A24) would be very intelligent of excellent musicians is considering that these performances have a genetic support.

A paper presented at the European Science Education Research Association 2009 Conference

Istanbul, Turkey August 31 September 1, 2009Finally, we can conclude that Finnish teachers are more innatist than French teachers. Is this innatism linked to other ideologies as sexism or racism? We saw in introduction that this link has been proved in some situations Figure 2 -Percentages of French and Finnish teachers' answers to the proposition B10: "There are genetic factors in parents that predispose their children to be good in school" Figure 3 -Percentages of French and Finnish teachers' answers to the proposition A35: "Ethnic groups are genetically different and that is why some are superior to others." [START_REF] Keller | In genes we trust: The biological component of psychological essentialism and its relationships to mechanisms of motivated social cognition[END_REF]Dambrun 2007). Nevertheless: (i) the weight of these questions in the between analysis is clearly less important than the weight of the questions related to innatism (figure 1 andtable 1) and (ii) for more questions related to feminist / sexist conceptions, there is no significant difference between the Finnish and French answers. This last point is less surprising considering the feminist reputation of Scandinavian countries, while the sexism of some Finnish teachers, expressed through their answers to 3 questions (A38, A36 and A30) is more surprising. It can be linked with the innatism of these teachers. In these cases, there is a clear interaction between K and V (scientific knowledge and values). This interaction has been found also among the scientists themselve, when the famous Journal Nature published a more ideological than scientific agenda concerning the cerebral lateralisation of men and women [START_REF] Clément | Using complex images in the popularization of science : Scientific or ideological agenda ? in "Multimedia learning : cognitive and instructional issues[END_REF][START_REF] Vidal | Quand l'idéologie envahit la science du cerveau[END_REF] An other analysis of our results shows that, in Finland, the biology teachers are more innatist than their non biologist colleagues. The figure 4 is illustrating this point from the answers to the question B10. This figure also shows that the innatism is stronger for in-service teachers than for the pre-service ones: this is a generation effect that we will describe more precisely in an other work. This complementary result suggest two conclusions: (i) the more important level of innatism in Finland could be linked to the way biology was taught and (ii) it could be also linked to the history of the country, more memorised by the oldest teachers.

Conclusions and Implications

In conclusion, the differences pointed by PISA (2006), related to the students' scientific literacy, are not linked, for this precise topic (biological determinism of human features and performances), with differences of teachers' knowledge. There is no significant difference between the Finnish and French answers for almost all the questions dealing with only scientific knowledge (related to human genetic and to cerebral epigenesis).

Nevertheless, there are important differences between Finnish and French answers related to the genetic determinism of human features, behaviour or performances. The convergence of answers from several kinds of questions related to this topic shows a clear innatism in a majority of Finnish teachers answers, and even more when they are biologist and in-service teachers. Moreover, this innatism is partly correlated to some sexist and even racist answers.

This conclusion is illustrating interactions between the taught science (the scientific knowledge K) and implicit values (V). It also shows that the indicators used by international surveys on the scientific literacy (as PISA 2006) are generally ignoring the values that can be linked to some scientific knowledge. Taking more into account these values is an important challenge not only for the international evaluations, but also for the teachers training and the science teaching / learning. Why these differences between Finland and France? The explanation is not so easy and must be object of more research. We can just propose some very hypothetical suggestions:

The biology syllabuses and textbooks are still teaching an implicit innatism in Finland with a great occurrence of the terms « genetic program » [START_REF] Castéra | Genetic determinism is school textbooks: a comparative study conducted among sixteen countries[END_REF]. The researchers in biology are more and more claiming that the use of these two words is to be avoided, in the research as well as in the biology teaching [START_REF] Atlan | La fin du "tout génétique[END_REF][START_REF] Jacquard | L'avenir n'est pas écrit[END_REF]. This change is just starting in the French syllabuses and textbooks (Forrissier & Clément 2003). The delay of this change (the DTD = Delay of the Didactic Transposition: Quessada & Clément 2007) is apparently longer in Finland, probably for socio-historical reasons that are still to be analysed.

France is the country of the Revolution, with an early separation between politics and religion (promotion of secular structures: « laïcité »). The history of Finland is very different.

The great debate between innate and/or acquired was very strong in the French media, the most famous French scientists and philosophers being against fatalism from a strong genetic determinism. It was possibly different in Finland?

In our samples, half of French teachers are agnostic or atheist when 2/3 of Finnish teachers are Protestant (Lutheran, when French Protestants are mainly Calvinist): are genes taking the relay of God in the determinism of human behaviour and performances?

Figure 1 -

 1 Figure 1 -Between analysis differentiating the French teachers' conceptions from the Finnish teachers' conceptions on genetic determinism. (a) -Each box inserts half of the values. The overlapping of the two countries is very reduced. (b) -Randomization test (Monte Carlo): the 1000 essays by chance (histogram at left) are very far from the observed value (at right). The difference between the two countries is very significant (p < 0.0001).

Figure 4 -

 4 Figure 4 -Answers of the six Finnish sub-samples to the question B10 "There are genetic factors in parents that predispose their children to be good in school". InB = in-service Biology teachers (secondary schools) ; InP = inservice Primary schools teachers ; PreB = pre-service biology teachers ; inL = in-service Language (Finnish) teachers (secondary schools) ; PreL = pre-service Language (Finnish) teachers ; PreP = pre-service Primary schools teachers.

  paper presented at the European Science Education Research Association 2009 Conference

	Istanbul, Turkey
	August 31 September 1, 2009

  ).

		A paper presented at the European Science Education Research Association 2009 Conference
											Istanbul, Turkey
											August 31 September 1, 2009
							B10
	France
											Don't agree
											Rather not agree
											Rather agree
											Agree
	Finland
	0%	10%	20%	30%	40%	50%	60%	70%	80%	90%	100%
							A35
	France										Don't agree
											Rather not agree
											Rather agree
											Agree
	Finland
		0%	20%		40%		60%	80%	100%

Acknowledgements

This work has been supported by the European Research Project BIOHEAD-Citizen (Specific Targeted Research n° 506015, FP6, Priority 7: "Biology, Health and Environmental Education for better Citizenship", 2004Citizenship", -2008)). We particularly thank Anna Liisa Kosonen ( Faculty of Education, University of Joensuu, Box-86, 57101-Savonlinna, Finland) who had an essential role in the translation of the questionnaire in Finnish and then in gathering the filled questionnaires from the precise six Finnish samples.


Matthieu Dorier
email: matthieu.dorier@irisa.fr

Shadi Ibrahim
email: shadi.ibrahim@inria.fr

Gabriel Antoniu
email: gabriel.antoniu@inria.fr

Rob Ross
email: rross@mcs.anl.gov

Omnisc'IO: A Grammar-Based Approach to Spatial and Temporal I/O Patterns Prediction

Keywords: Exascale, HPC, Storage, I/O, Prediction, Grammar, Omnisc'IO

The increasing gap between the computation performance of post-petascale machines and the performance of their I/O subsystem has motivated many I/O optimizations including prefetching, caching, and scheduling techniques. In order to further improve these techniques, modeling and predicting spatial and temporal I/O patterns of HPC applications as they run has became crucial.

In this paper we present Omnisc'IO, an approach that builds a grammar-based model of the I/O behavior of HPC applications and uses it to predict when future I/O operations will occur, and where and how much data will be accessed. Omnisc'IO is transparently integrated into the POSIX and MPI I/O stacks and does not require any modification in applications or higherlevel I/O libraries. It works without any prior knowledge of the application and converges to accurate predictions within a couple of iterations only. Its implementation is efficient in both computation time and memory footprint.

I. INTRODUCTION

Existing petascale computing platforms often fail to meet the I/O performance requirements of applications running at scale. This weakness of the I/O system relative to computing capabilities is part of a trend that is worsening as we develop ever more capable computing platforms, and we expect the next generation of systems to have an even larger gap [START_REF] Geist | Major Computer Science Challenges at Exascale[END_REF]. Moreover, most HPC applications exhibit a periodic behavior, alternating between computation, communication, and I/O phases. The I/O phases are commonly used for coordinated checkpointing and/or analysis or visualization output. They produce bursts of activity in the underlying storage system [START_REF] Liu | On the Role of Burst Buffers in Leadership-Class Storage Systems[END_REF], [START_REF] Liu | Automatic Identification of Application I/O Signatures from Noisy Server-Side Traces[END_REF] that further limit the overall scalability of the HPC application and potentially interfere with other applications running concurrently on the platform [START_REF] Dorier | CALCioM: Mitigating I/O Interference in HPC Systems through Cross-Application Coordination[END_REF].

To alleviate the performance penalty of the I/O bottleneck in petascale systems, researchers have explored techniques such as prefetching, caching, and scheduling [START_REF] Dorier | CALCioM: Mitigating I/O Interference in HPC Systems through Cross-Application Coordination[END_REF], [START_REF] He | KNOWAC: I/O Prefetch via Accumulated Knowledge[END_REF], [START_REF] Tran | Automatic ARIMA Time Series Modeling for Adaptive I/O Prefetching[END_REF] to improve I/O performance. The effectiveness of such techniques strongly depends on a certain level of knowledge of the I/O access patterns: prefetching and caching indeed require the location of future accesses (i.e., spatial behavior), while I/O scheduling leverages estimations of I/O requests interarrival time (i.e., temporal behavior). The key challenges inherent in these techniques include the proper comprehension and exploitation of the application's I/O behavior within the I/O stack itself [START_REF] He | I/O Acceleration with Pattern Detection[END_REF], [START_REF] He | KNOWAC: I/O Prefetch via Accumulated Knowledge[END_REF]. Hence, modeling and predicting the applications I/O behavior are of utmost importance.

While predicting the I/O patterns of HPC applications has long been an important goal in large-scale supercomputers, researchers have focused mainly on statistical methods (e.g., hidden Markov models (HMM) [START_REF] Oly | Markov Model Prediction of I/O Requests for Scientific Applications[END_REF] and ARIMA models [START_REF] Tran | Automatic ARIMA Time Series Modeling for Adaptive I/O Prefetching[END_REF]). These approaches often focus exclusively on either spatial or temporal I/O behaviors. Furthermore, they require a large number of observations to accomplish good prediction; hence, they either need long execution time (several runs in some cases) [START_REF] Byna | Parallel I/O Prefetching using MPI File Caching and I/O Signatures[END_REF] or are doomed to offline trace-based training [START_REF] Madhyastha | Learning to Classify Parallel Input/Output Access Patterns[END_REF] in order to converge. Our work addresses the limitations of current prediction systems and takes a step toward intelligent I/O management of HPC applications in next-generation post-petascale supercomputers [START_REF] Isaila | Making the Case for Reforming the I/O Software Stack of Extreme-Scale Systems[END_REF] that is capable of run-time analysis and adaptation to the I/O behavior of applications. To this end, we present the design and implementation of Omnisc'IO, a grammar-based approach for modeling and predicting the I/O behavior of any HPC application.

The intuition behind Omnisc'IO is that, on the one hand, while statistical models are appropriate mostly for phenomena that exhibit a random behavior, the (mostly) deterministic behavior of HPC applications, inherent from their code structure, makes other representations of their I/O behavior possible. On the other hand, formal grammars, as natural models to form a sequence of symbols, have been widely applied to areas of text compression, natural language processing, music processing, and macromolecular sequence modeling [START_REF] Kieffer | Grammar-Based Codes: A New Class of Universal Lossless Source Codes[END_REF] [START_REF] Nevill-Manning | Inferring Sequential Structure[END_REF]. Therefore, an approach based on formal grammars is suitable for I/O behavior modeling, since it detects the hierarchical nature of the code that produced the I/O patterns, with its nested loops and stacks of function calls. To the best of our knowledge, grammar-based models have never been used in the context of HPC applications. Omnisc'IO is the first prediction system that adopts this appealing approach. Contributions: Omnisc'IO builds a grammar-based model of the I/O behavior of any HPC application and uses it to predict when future I/O operations will occur (i.e., predict the interarrival time between I/O requests), as well as where and how much data will be accessed (i.e., predict the file being accessed as well as the location -offset and size-of the data within this file). It learns its model at run time using an algorithm inspired by Sequitur [START_REF] Nevill-Manning | Identifying Hierarchical Structure in Sequences: A Linear-Time Algorithm[END_REF]. Sequitur is designed to build a grammar from a sequence of symbols and has been used mainly in the area of text compression; one of the main challenges in our work was to turn it into an algorithm capable of making predictions. In this respect, our algorithmic contribution is much more general than its application to I/O pattern prediction.

Omnisc'IO is transparently integrated into the POSIX and MPI I/O stacks and does not require any modification in applications or higher-level I/O libraries. It works without any prior knowledge of the application, and it converges to accurate predictions within a couple of iterations. Its implementation is efficient both in computation time (less than a few microseconds to update the model on a recent x86 hardware) and in memory footprint. Omnisc'IO is evaluated with four real HPC applications -CM1, Nek5000, GTC, and LAMMPS-using a variety of I/O backends ranging from simple POSIX to Parallel HDF5 on top of MPI-I/O. Our experiments show that Omnisc'IO achieves from 79.5% to 100% accuracy in spatial prediction (percentage of matching between the predicted segment and the effectively accessed segment) and an average precision of temporal predictions (absolute difference between the predicted and the actual date of the next accesses) ranging from 0.2 seconds to less than a millisecond. Goals: The primary goal for Omnisc'IO, and the focus of this paper, is modeling the I/O behavior of any HPC application and using this model to accurately predict the spatial and temporal characteristics of future I/O operations. Omnisc'IO can therefore be applied at the core of many I/O optimizations, including prefetching, caching, or scheduling.

In order not to undermine the generality of our approach, this paper does not present the use of Omnisc'IO in a particular context (i.e., prefetching, caching, or scheduling). Others have already demonstrated the benefits of applying I/O predications to enhance the performance in each of these techniques [START_REF] Oly | Markov Model Prediction of I/O Requests for Scientific Applications[END_REF], [START_REF] Tran | Automatic ARIMA Time Series Modeling for Adaptive I/O Prefetching[END_REF], [START_REF] Byna | Parallel I/O Prefetching using MPI File Caching and I/O Signatures[END_REF], [START_REF] Madhyastha | Learning to Classify Parallel Input/Output Access Patterns[END_REF]. We focus our study on the prediction capabilities of Omnisc'IO.

The paper is organized as follows. Section II presents our contribution, followed by an extensive evaluation of its prediction capabilities in Section III. Related work that has attempted spatial and/or temporal I/O access predictions in HPC applications is presented in Section IV. Section V presents our conclusions and suggestions for future work.

II. OMNISC'IO APPROACH

This section first gives an overview of Omnisc'IO, then dives into its technical and algorithmic details.

A. Overview of Omnisc'IO

Figure 1 presents an overview of Omnisc'IO. Omnisc'IO captures each atomic request to the file system (open, close, read, write) in a transparent manner, without requiring any change in the application or I/O libraries. At each operation, Omnisc'IO operates as follows.

1) The context in which the operation is executed is extracted by recording the call stack of the program (upper-left part of Figure 1(a)). This is a known technique [START_REF] Gniady | Program-Counter-Based Pattern Classification in Buffer Caching[END_REF] that helps capture the structure of the code that issues the I/O operations. The context is abstracted as a context symbol (a in the figure).

2) A grammar-based model of the stream of context symbols (upper-right part of Figure 1(a)) is updated by using the Sequitur algorithm. Sequitur has been applied to text compression in the past [START_REF] Kieffer | Grammar-Based Codes: A New Class of Universal Lossless Source Codes[END_REF] because of its ability to detect several occurrences of substrings in a text and to store them into grammar rules. We have adapted it to model the repetitive behavior of an HPC application, represented as a stream of context symbols. The application of Sequitur to the field of application behavior modeling is novel and constitutes part of our contribution.

3) Spatial (size, offset, file) and temporal (interarrival time) access patterns are recorded in tables associating context symbols or transitions among symbols with access patterns (lowerleft part of Figure 1(a)). The intuition is (for the example of the access size) that a given context symbol will often be associated with the same access size or with a reduced number of sizes whose sequence can also be learned. 4) We improved on the Sequitur algorithm to make predictions of future context symbols. It then becomes easy to predict the characteristics of future accesses by looking up the access patterns associated to the predicted context symbols in the aforementioned tables (lower-right part of Figure 1(a)) Turning Sequitur into a prediction system is a challenge that, to the best of our knowledge, has never been addressed before. The algorithmic details of our prediction model therefore constitutes another important part of our contribution.

B. Algorithmic and technical description

As shown in Figure 1(b), Omnisc'IO is integrated within the POSIX I/O layer and the ADIO layer in MPI-I/O. In the following, we provide more details on the four steps described above.

1) Tracking applications behavior:

To give a context to each atomic I/O operation, we use the libc backtrace function to retrieve the list of stacked program counters (array of void * pointers). When called within a function f, this list of addresses characterizes the series of return addresses that leads from f back to main. Different calls to f in distinct places in the program (or libraries) lead to different call stack traces. Omnisc'IO calls backtrace within wrappers of I/O functions, stores the returned array in a dictionary, and associates it with a unique integer. In the following, such integers are called context symbols and represent the context in which an I/O operation occurs.

Omnisc'IO is based on the observation that (1) a particular context is likely to be associated with fixed parameters (e.g., two calls to write within the same context are likely to involve the same amount of data); (2) transitions between two contexts can also be associated with fixed parameters (tracking the evolution of the offset can be done by tracking transitions between contexts) and with little-varying transition times; and, most important, (3) the stream of context symbols is eventually predictable, and a model of it can be built at run time.

In our prototype, we overloaded the POSIX I/O functions (write, read...) and the libc functions (fwrite, fread...) using a preloaded shared library. In MPI-I/O we added an intermediate layer within the ADIO layer in ROMIO, a popular implementation of MPI-I/O [START_REF] Thakur | On Implementing MPI-IO Portably and with High Performance[END_REF], to track the lowest-level I/O functions that access files metadata (open, close...) and atomic functions that access contiguous blocks of data and are used by more elaborate I/O algorithms.

While working at the lowest level of the I/O stack is necessary to capture the I/O behavior at a fine grain (i.e., a series of atomic requests to the file system), the use of backtraces lets Omnisc'IO have information also on the upper layers that issued the I/O, including I/O middleware, libraries, and the application itself. a) Learning the grammar of the application: While capturing a stream of symbols representing the behavior of the application, we aim to predict the next symbols given past observations. Omnisc'IO models the stream of symbols using a context-free grammar. This grammar is learned at run time using an algorithm inspired by Nevill-Manning and Witten's Sequitur algorithm [START_REF] Nevill-Manning | Identifying Hierarchical Structure in Sequences: A Linear-Time Algorithm[END_REF].

As background, a context-free grammar G is a quadruple (Σ, V, R, S), where Σ is a finite set of terminal symbols (in our case the symbols defined by the call stack traces); V is a finite set of nonterminal symbols disjoint from Σ; R is a finite relation from V to (V ∪ Σ) * , usually written as a set of rules in the form A → x 1 ...x k , where x i ∈ (V ∪ Σ); and S ∈ V is a starting symbol. In the following, we call x i the nested symbols of A.

Sequitur builds a context-free grammar from a stream of symbols by updating the grammar at each input. It starts with a single rule S. At each new input x, it appends x to the end of rule S and recursively enforces two constraints:

Digram uniqueness: Any sequence of two symbols ab ∈ (V ∪ Σ) 2 (digram) cannot appear more than once in all rules. If one does, a new rule R → ab is created, and the constraints are enforced recursively.

Rule utility: All rules should be instantiated at least twice. If a rule appears only once, its instance is replaced by the content of the rule, the rule is deleted, and the constraints are enforced recursively.

Examples of context-free grammars are given in Table I, some of which violate the Sequitur constraints. In the following, the grammar built from the context symbols is called the main grammar of Omnisc'IO. Sequitur has a linear worst-case b) Predictions using the grammar model: Sequitur builds a grammar from a stream of symbols, but it does not predict the next incoming symbols from past observations. Therefore, we enriched the algorithm to be able to make such a prediction.

This improvement works by marking some of the terminal symbols in the grammar as predictors. This predictor characteristic is extended to nonterminal symbols by using the following constraints:

Predictor nesting: A nonterminal can be a predictor only if at least one of its nested symbols is a predictor.

Predictor utility: If symbol x (terminal or not) is a predictor in rule Y , then there exists at least one rule Z such that an instance of Y is a predictor in Z.

These constraints enforce that (1) if the grammar contains at least one predictor, then rule S contains at least one predictor, and (2) all the terminal predictors of the grammar can be reached from a predictor in S (proofs of these properties are trivial). The relations linking predictors together form a direct acyclic graph within the tree structure of the grammar. These two structural properties have to be carefully preserved when updating the grammar.

In order to make predictions from the set of predictors, two operations are defined, respectively, to update the set of predictors and to find new ones.

Updating predictors:

We call incrementing a predictor the operation that consists of unmarking a symbol previously marked as a predictor and marking as a predictor the symbol that immediately follows it in the rule where it appears. Updating predictors consists of first unmarking all terminal predictors that did not correctly predict the last input, enforcing the predictor's constraints, and then incrementing all remaining terminal predictors. If a predictor is the last symbol of a rule, then nonterminal predictors that reference it are incremented recursively. Examples of this operation are shown in Table II, where predictor symbols are marked in red and underlined.

Discovering predictors: If all predictors have been removed

because none of them correctly predicted the last input, a new step is necessary to rebuild a set of predictors. This step is completed by navigating through the grammar and The predictors are marked in red and underlined. In the first input, a does not match and disappears from the set of predictors, c matches and is incremented to d, and A stays a predictor. In the second example, d matches but has no successor in rule A; thus A is incremented to e in rule S.

The resulting models correspond to the grammars before the input is appended and Sequitur's constraints are applied.

Before Update Input After Update

S → abAAe c S → abAAe A → cd A → cd S → abAAe d S → abAAe A → cd A → cd

TABLE III:

Discovery of new predictors matching the last input (b, appended at the end of rule S). The predictors are marked in red and underlined. The symbol b becomes a predictor wherever it appears, and recursively any rule that leads to an occurrence of b becomes a predictor. The predictors are then updated to predict the next expected input (here c or e).

Before Discovery After Discovery After Update

S → abAAeb S → abAAeb S → abAAeb A → cdb A → cdb A → cdb
setting as predictors all symbols matching with the last symbol of rule S (after insertion of the last input). Parent rules are also set as predictors recursively wherever they appear. Note that the last symbol of rule S may be a nonterminal, which forces new predictors to be searched only within the context of its corresponding rule and thus reduces the number of predictors and narrows down the prediction. An example of this operation is shown in Table III. After the discovery of these new predictors, an update is necessary.

The prediction of the model corresponds to the set of terminal symbols marked as predictors after inserting a new input, updating the predictors, and enforcing the constraints. Although statistical methods could be used to weight each predicted symbol with a probability of appearance, considering equal probability for all predicted symbols appeared to be sufficient to achieve good results in our experiments.

To implement our algorithm, we reused the simple C++ code provided by the authors of Sequitur. 1 For comparison, the original code has 358 lines, whereas our improved version has 982 (without counting the I/O wrappers and the code related to access tables, which is explained later).

2) Context-aware access behavior: The final step in Omnisc'IO is the actual bookkeeping of per-context access behavior. This is done differently for each type of tracked metrics.

a) Tracking access sizes: Access sizes are tracked on a per-context symbol basis, so that predicting the next context symbol helps in predicting the next access size. As shown in Section III, most context symbols are always associated with the same access size each time they are encountered in an execution, making it easy to predict the exact size of the next accesses given a correct prediction of the next context symbols.

For the minority of symbols associated with several access sizes, Omnisc'IO keeps track of all access sizes encountered and builds a grammar from this sequence of sizes. The sizes constitute the terminal symbols of this grammar, which we call a local size grammar. The local size grammar associated with a context symbol is updated whenever the context symbol is encountered, and it evolves independently of the main grammar and independently of local size grammars attached to other symbols. It can then be used to make predictions of the size.

If the number of different access sizes observed for a given symbol is too large (typically larger than a configurable constant N ), the local size grammar is replaced by a simple average, minimum value and maximum value that are updated whenever the context symbol is encountered. For our experiments, after analyzing the distributions of different access sizes per symbol, we choose N = 24.

More elaborate methods could be implemented to predict the access sizes for context symbols that exhibit apparently random sizes. We show in Section III, however, that the three cases presented above have been sufficient to cover the behavior of all our applications. b) Tracking offsets: Many prefetching systems, including those implemented in the Linux kernel [START_REF] Wu | Sequential File Prefetching in Linux[END_REF], are based on the assumptions of consecutive accesses; that is, the next operation is likely to start from the offset where the previous one ended. As we will show in our experiments, this assumption is held for the POSIX-based applications that we tested, but it fails for applications that use a higher-level library such as HDF5. Indeed such libraries often move the offset pointer backward or forward to write headers, footers, and metadata.

To predict the offset of the next operation, we define the notion of offset transformation. An offset transformation can (1) leave the offset as it was at the end of the previous operation (consecutive access transformation), (2) set it to a specific absolute value (absolute transformation), or (3) set it to a value relative to the offset after the previous operation (relative transformation). Since it is not possible at low level to distinguish between absolute and relative transformations, Omnisc'IO uses absolute transformations only for operations that reset the offset to 0 (open and close). All other nonconsecutive offset transformations are considered relative to the previous offset.

Omnisc'IO associates transitions between context symbols with offset transformations the same way it associates context symbols with access sizes. For instance, if symbol B follows A in the execution and A left the offset at a value from which B starts, then the transition A → B is associated with a sequential transformation. When a transition encounters different types of offset transformations, Omnisc'IO builds a local offset grammar for the transition. Local offset grammars are the counterpart of local size grammars for offset transformations. If the grammar associated with a transition grows too large (more than 24 symbols in our experiments), Omnisc'IO switches back to always predicting a sequential offset transformation for this transition of context symbols. c) Tracking files pointers: For the prediction of offsets to work properly, Omnisc'IO needs to know that two consecutive operations work on the same file or that an operation works on a new file or a file that has already been accessed earlier. This is particularly important when accesses to multiple files interleave. The prediction of files accessed is done by recording opened file pointers and associating transitions between symbols to changes of file pointers. Since in our experiments the case of interleaved accesses to different files did not appear, we will not study this particular aspect further.

d) Tracking interarrival times: To keep track of the time between the end of an operation and the beginning of the next one, Omnisc'IO uses a table associating transitions between context symbols to statistics on the measured time. These statistics include the minimum and maximum observed, the average, and the variance. We prefer these statistics rather than keeping only the average because they represent the minimum required to answer (1) whether an operation will immediately follow (maximum, minimum, average, and variance close to 0); (2) whether the next operation will follow in a predictable amount of time (maximum, minimum, and average close to each other, small variance); or (3) whether the time before the next operation is more unpredictable or depends on parameters that are not captured by our system (large minimum-maximum interval, large variance). Thus, these statistics, while minimal, give us confidence in the predicted interarrival time, which may be important in the context of scheduling, for example.

To quickly react to changes in interarrival times, Omnisc'IO also keeps a weighed interarrival average time, updated every time the transition between symbols is encountered by using the following formula,

T weighed x→y ← T weighed x→y + T 2 , (1)
where x → y is the observed transition between context symbols x and y and T is the measured interarrival time. This weighed average is more efficient at making predictions of interarrival time, especially in a context where this interarrival time varies a lot between different observations of the same transition.

3) Overall prediction process and API: At each operation, Omnisc'IO updates its models (the main grammar and the tables of access sizes, offset transformations and interarrival times). It then updates its predictors and builds the set of possible next context symbols (this set often consists of a single prediction). From these possible next symbols, a set of triplets (size, offset, date) is formed that can then be used by scheduling, prefetching, or caching systems. Although this kind of prediction can easily be extended to the series of N next I/O operations, our experiments will focus only on the capability of Omnisc'IO to predict the next one.

To use Omnisc'IO, any software aiming at optimizing I/O simply needs to be linked against the Omnisc'IO library and to call the following function: We first assess its capability to predict the next context symbols, and we show how the grammar grows in size as the application continues to run. We then evaluate its performance in predicting the spatial and temporal characteristics of the next operations.

A. Platform and applications

All our experiments are carried out at the Nancy site of the French Grid'5000 testbed [START_REF]Aladdin Grid[END_REF]. The applications run on a Linux cluster consisting of 92 Intel Xeon L5420 nodes (8 cores per node, 736 cores in total), using MPICH 3.0.4. The OrangeFS 2.8.7 parallel file system [START_REF] Carns | PVFS: a Parallel File System for Linux Clusters[END_REF] is deployed on a separate set of 12 Intel Xeon X3440 nodes. All nodes, including the file system's, are interconnected through a 20G InfiniBand network.

The list of applications used is presented in Table IV. These applications are real-world codes representative of applications running on current supercomputers. They have been used on NCSI's Kraken2 and NCSA's Blue Waters3 for CM1, ORNL's Titan 4 for GTC and LAMMPS, and ANL's Intrepid and Mira 5for Nek5000.

For the experiments in this paper, the applications are run on 512 cores of Grid5000, except for Nek5000, which runs on 32 cores. These applications are written in Fortran except for LAMMPS (C++). Most of them use a POSIX I/O interface. To show the generality of our approach with respect to higher-level I/O libraries, CM1 [START_REF] Bryan | CM1[END_REF], [START_REF] Bryan | A Benchmark Simulation for Moist Nonhydrostatic Numerical Models[END_REF] uses the HDF5 [22] I/O library over the default (POSIX) I/O driver, as well as the MPI-I/O driver offered by pHDF5, and Gzip compression over the default POSIX driver. CM1 writes one file per process per I/O phase. The domain decomposition in CM1 is such that the amount of data remains the same over time and across processes. The use of compression exemplifies the case of varying data size in a nonvarying domain decomposition. GTC [START_REF]UCIrvine[END_REF] writes one file per node per iteration, but the amount of data varies between files as particles move from one process to another. Like CM1, the domain decomposition in Nek5000 [START_REF] Fischer | Nek5000[END_REF] does not vary over time, but the I/O phase is executed only by the rank 0 after a reduce phase. LAMMPS [25], [START_REF] Plimpton | Fast Parallel Algorithms for Short-Range Molecular Dynamics[END_REF] also sends data to the rank Although all processes write data in CM1 and GTC, we consider the results of Omnisc'IO only on process rank 0 (for applications that issue I/O from all processes, these results are in fact identical in all processes since they exhibit the same behavior). We first evaluate how well our algorithm predicts future context symbols based on past observations. We then evaluate the ability of Omnisc'IO to predict the location (offset and size in the file) of the next I/O operations. We also evaluate its ability to predict when future accesses will happen.

B. Context prediction

To measure context prediction capabilities, we run each application, and at each I/O operation we use Omnisc'IO to predict the context symbol associated with the next one. We use a sliding window of ten operations and report the percentage of correct predictions. When Omnisc'IO predicts several possible next symbols, they are weighed as 1 # predicted symbols . For instance, if Omnisc'IO predicts that the next symbol will be either a or b and the real next symbol is b, then this prediction is weighed 1 2 . For CM1 and GTC, which run for long periods of time, we show only several iterations starting from the beginning of the run.

Results are shown in Figure 2. For all three configurations of CM1 as well as for LAMMPS and GTC, Omnisc'IO converges to a perfect (steady 100%) prediction of symbols after the first iteration. The variation observed during the first iteration corresponds to the moment the grammar starts detecting the innermost loops.

Omnisc'IO seems to learn GTC's behavior (Figure 2(e)) fast: the reason is that GTC's I/O phase consists of a loop over all particles, which is easily modeled in the grammar after the first two particles are written out. The prediction quality drops at the end of the first iteration when Omnisc'IO does not predict the end of this loop and the file being closed. This mistake is never repeated in later iterations. The same pattern appears in LAMMPS.

The case of Nek5000 is more interesting: although it writes periodically the exact same amount of data, the grammar model does not converge as fast and as perfectly as the other applications. Investigating the code of Nek5000, we found that this is due to code branches that process data in a different way depending on its content and then write it in an identical manner, leading to the creation of several symbols that are actually interchangeable in the grammar. Moving the write call outside the branches would help remove this indeterminism. Because we claimed our solution works with no prior knowledge of the application and without the involvement of the application developer, we did not apply this code modification.

We also observe a drop in prediction quality at the end of the LAMMPS and Nek5000 runs. This drop is due to the final results being output in a section of the code different from the one used for the periodic checkpoints. Thus these symbols, which appear the first time at the end of the execution could not have been predicted by any model.

Cost of a failed prediction: A failed prediction leads to searching new predictors within the grammar, instead of simply updating existing ones. This operation is linear in the size of the grammar (number of symbols). A failed prediction also has an effect on the system that leverages the prediction. For instance, a prefetching algorithm would read unnecessary data and/or fail to read the data that is actually needed by the program. The real cost would therefore depend on how much the incorrect operation consumes resources that could be used more productively.

C. Grammar size

Figure 3 shows the evolution of the size of the main grammar as a function of the number of operations. One can clearly distinguish a first learning phase during which Omnisc'IO discovers the behavior of the application. This phase corresponds to the first iteration (potentially preceded by an input phase). It is followed by a stationary regime during which the model is updated in a mostly logarithmic manner. All the applications considered here exhibit this logarithmic growth of the grammar size after the learning phase. GTC's grammar growth is logarithmic as well, but it exhibits a staircase pattern. This is due to a variable number of particles written at each checkpoint, which leads to a variable number of writes and thus prevents Omnisc'IO from grouping these writes into large rules. That said, after 100,000 accesses the grammar has only 450 symbols.

The memory footprint is directly linked to the size of the main grammar (a symbol in our implementation is a 100-byte C++ object, making the grammar consume 26 KB in the case of CM1+POSIX, for example), and the number of entries in the tables (one entry per symbol or per transition, accounting also for a few bytes. CM1+POSIX uses 198 symbols, for example). This part of the memory footprint does not increases after the learning phase. The memory footprint of Omnisc'IO is thus correlated mainly with the grammar size and does not exceed a few hundreds of kilobytes.

D. Spatial prediction

In this section, we first analyze how well our solution predicts the size and the offset of the next operation. We then combine these two predictions to compute a hit ratio.

1) Prediction of sizes: We analyzed how many different access sizes were associated with each context symbol. We found that the vast majority of symbols were associated with just one size, potentially different for each symbol (171 symbols out of 183 for CM1 using HDF5 are associated with one size, and similar numbers with GZIP and pHDF5, 12 out of 17 for GTC, and all 38 of them for Nek5000). LAMMPS had the most interesting distribution, with 123 symbols associated with a unique size (yet potentially different for each symbol), and one unique symbol associated with a different size at almost every appearance. This distribution is due to the fact that all n processes send their set of particles to the rank 0 process, which writes them into a file in n successive write calls. As the number of particles varies between processes and between checkpoints, this leads to the variation in observed sizes.

To evaluate the prediction of sizes, we use the following relative error as a metric:

E size = |size p -size o | size o , (2)
where size p is the predicted size and size o is the observed size. Intuitively, if the predictions are always such that E size ≤ ǫ, then allocating 1 + ǫ times the predicted size (in a caching system, for example) will always be enough to cover the need for the next operation. Figure 4 shows the relative error observed for all six cases. In all but Nek5000, the error goes to 0 or close to 0 after the learning phase. Errors observed in Nek5000 match the incorrect predictions of context symbols. In LAMMPS, the prediction is very close but not equal to 0. The reason is that the number of particles written (and thus the size of each write) varies slightly from one write to another. Thus, after trying to build a local size grammar out of those random sizes, Omnisc'IO falls back to keeping track of the average only.

Note that the graphs are cut down to a maximum relative error of 5, whereas the observed errors can be of up to several thousands. For instance, if Omnisc'IO predicts a write or 5,000 bytes while the application actually writes only 2, the relative error is 2,499.

To put these relative errors in perspective, Table V provides statistics on the sizes accessed by each operation. Note that the standard deviation is often close to or even larger than the average access size, making this average a poor estimator if we were to use it in a prediction.

2) Prediction of offsets: We consider that an offset prediction is either correct or incorrect. When our algorithm makes several predictions for the next context symbol (and therefore several predictions of offset), correct predictions are weighed accordingly. We compare our solution with the classical contiguous access estimation [START_REF] Wu | Sequential File Prefetching in Linux[END_REF], which consists of always predicting that the next offset will follow the previous access. Table VI shows the proportion of contiguous accesses in our set of applications as well as the proportion of correct predictions made by Omnisc'IO. In all cases, Omnisc'IO achieves a better prediction of offsets than does the naive approximation based on contiguous accesses. It is especially better suited when using a high-level I/O library such as HDF5 in CM1, since it manages to model and predict the portion of accesses that are noncontiguous. In particular, the prediction of offset in CM1 using HDF5 goes from 47.4%, when using a contiguous access estimation, to 92.2% with Omnisc'IO.

3) Hit ratio: We also combine the prediction of sizes and offsets to measure how accurately our solution can predict the location of the next access. This information forms a predicted segment S = x start , x end . The segment effectively accessed by the next I/O operation is denoted S 0 = y start , y end . The hit ratio of S with respect to S 0 , denoted H(S|S 0 ), is computed by

H(S|S 0 ) =    100 × |S ∩ S 0 | max(x end , y end ) -min(x start , y start ) 100 if S = S 0 = ∅ (3)
This metrics yields the percentage of overlap between the two segments with respect to the distance between their extrema: H(S|S 0 ) = 100 ⇐⇒ S = S 0 . Since our approach may propose several potential next locations, this formula is extended to multiple segments S 1 . . . S n by considering the average of H(S i |S 0 ) for i ∈ 1, n . Figure 5 shows the results obtained with our simulations, and Table VII presents the average hit ratio over the course of the entire run for each application. Note that for CM1+POSIX and CM1+MPI-I/O, Omnisc'IO holds a perfect hit ratio after the learning phase. Although the hit ratio in LAMMPS also seems to be perfect, it is actually slightly lower than 100% because of the small error made in the prediction of the size (see explanation in Section III-D1). The lowest hit ratio achieved in our experiments was that of CM1+Gzip (79.5%), which, since the study made on the prediction of offsets and sizes in earlier sections, is explained mainly by incorrect predictions of offsets. Our guess is that HDF5 writes compressed data by blocks of predictable size but jumps back and forth in a more unpredictable manner to update metadata.

E. Temporal prediction

Temporal prediction involves estimating the time between the end of an I/O operation and the beginning of the next one (interarrival time). For qualitative analysis, Figure 6 presents the series of observed interarrival times between consecutive operations, along with the predictions made by Omnisc'IO. We note that Omnisc'IO is efficient at discriminating immediate transitions (low transition times, which can be used as a hint that two consecutive operations belong to the same I/O phase) from distant transitions (corresponding to computation and communication phases that last much longer). Figure 7 presents the absolute difference between observed and predicted transition times on a logarithmic scale. For readability, we consider only the 1,000 last operations of each run, that is, during the stationary regime. Table VIII reports the average of absolute difference over the course of each run (in its entirety, and not restricted to the stationary regime). We also compare the performance of Omnisc'IO with the immediate reaccess estimation used by some I/O schedulers (e.g., [START_REF] Zhang | IOrchestrator: Improving the Performance of Multi-Node I/O Systems via Inter-Server Coordination[END_REF]), which consists of assuming that the next I/O operation is likely to immediately follow the current one (i.e., interarrival time are always estimated to 0) and use a time window during which a potential new operation is expected). In all situations, Omnisc'IO appears to be very good at predicting the interarrival time of I/O accesses. In particular, the average difference between the predicted and observed interarrival time is below a microsecond for LAMMPS, and at Note that by combining the prediction of interarrival times and context symbols, we can estimate how many accesses will happen within a given time window and how many consecutive operations will occur before the end of the I/O phase. Because of space constraints, these studies are not included in this paper.

F. Limitations of our approach

Like all systems, Omnisc'IO has limitations. As it leans on the repetitiveness of I/O patterns, any nonperiodic applications (e.g., applications that write their results only once at the end of their run) will make Omnisc'IO incapable of discovering repetitive structures in the I/O pattern. To deal with such applications, however, Omnisc'IO can save its model into files and reload it before the next run.

As noted in Section III-B, Omnisc'IO is sensitive to branches in the code that depend on the content of the data. Solving this problem is arguably more difficult, since it would

G. Run-time overhead

The run-time overhead on a commodity hardware is presented in Table IX. This overhead of a few microseconds is negligible compared with the time taken by the I/O operations themselves (a few milliseconds to several seconds). However, since Omnisc'IO works at the level of atomic, contiguous operations, these I/O operations can be made asynchronous to hide the overhead of Omnisc'IO behind the I/O time.

IV. RELATED WORK

This section presents the related work in the context of grammar-based modeling as well as spatial and temporal I/O prediction.

A. Grammar-based modeling

The first work related to ours is Sequitur [START_REF] Nevill-Manning | Identifying Hierarchical Structure in Sequences: A Linear-Time Algorithm[END_REF]. Sequitur is designed to build a grammar from a sequence of symbols and has been used mainly in the area of text compression [START_REF] Kieffer | Grammar-Based Codes: A New Class of Universal Lossless Source Codes[END_REF], but also natural language processing, music processing, and macromolecular sequence modeling [START_REF] Nevill-Manning | Inferring Sequential Structure[END_REF]. The repetitive periodic I/O behavior of HPC applications [START_REF] Oly | Markov Model Prediction of I/O Requests for Scientific Applications[END_REF] is a very good candidate application for Sequitur. To our knowledge, our approach is the first to take advantage of a grammar-based model not only for modeling but also for making real-time predictions (through improvements of the Sequitur algorithm) of the application's I/O pattern.

B. I/O patterns prediction

Spacial and temporal I/O access prediction is a challenge commonly addressed in the context of prefetching, caching, and scheduling. Prefetching and caching indeed require a prediction of the location of future accesses [START_REF] Wu | Sequential File Prefetching in Linux[END_REF], while I/O scheduling leverages estimations of I/O requests' interarrival time. Although these domains have been investigated for decades in the context of commodity computers [START_REF] Li | A New Method of Pefetching I/O Requests[END_REF], we restrict our study of related works mostly to their use in the HPC area, where applications have different (mostly more regular) I/O behavior.

1) Spatial predictions: Most of the work on spatial I/O patterns predication is done to assist I/O prefetching using various approaches, including Markov models [START_REF] Oly | Markov Model Prediction of I/O Requests for Scientific Applications[END_REF], speculative execution [START_REF] Chen | Exploring Parallel I/O Concurrency with Speculative Prefetching[END_REF], and knowledge accumulation [START_REF] He | KNOWAC: I/O Prefetch via Accumulated Knowledge[END_REF]. These studies predict the I/O behavior based on statistical methods, however, and therefore require either prior knowledge of the application or long runs before the model converges. Moreover, the predictions are evaluated by mean of performance improvements in a particular context such as prefetching. Our work focuses on providing a general approach that can predict both spatial and temporal I/O patterns of any HPC applications, at run time. Its evaluation focuses on its prediction capability, and our results can therefore be transferred to any of the aforementioned applications.

Kroeger and Long [START_REF] Kroeger | The Case for Efficient File Access Pattern Modeling[END_REF] study several spatial access pattern modelings techniques, some of which are inspired by text compression algorithms such as variants of PPM (prediction by partial matching). The contexts (or symbols) used in these models are parameters of system-level I/O calls (i.e., file name, offset, size, etc.). Our solution builds a model of the program's structure using backtraces and keeps statistics only on the access parameters. Moreover, it can predict when the next operations are going to happen.

Gniady et al. [START_REF] Gniady | Program-Counter-Based Pattern Classification in Buffer Caching[END_REF] also use stack frames to optimize the prediction of disk accesses, using existing pattern prediction techniques in the operating system. Their solution is used to improve caching.

Madhyastha and Reed [START_REF] Madhyastha | Learning to Classify Parallel Input/Output Access Patterns[END_REF] use artificial neural networks (ANNs) and hidden Markov models (HMMs) to classify access patterns in order to improve adaptive file systems. In their paper, the authors show that ANNs are incapable of predicting future access patterns, while HMMs need to be trained by using access patterns from several previous executions. The challenge of predicting when future accesses will occur is not addressed, however. Our solution based on grammar models is able to converge at run time without prior execution of the application and can predict both spatial and temporal access patterns.

Closer to our approach is the work by He et al. [START_REF] He | I/O Acceleration with Pattern Detection[END_REF], who propose an approach to spatial I/O pattern detection to improve metadata indexing in PLFS. Their approach consid-ers a sequence of (offset,size) access parameters and tries to find repetitive patterns in the differences (delta) between consecutive accesses, using a method inspired by the LZ77 sliding window algorithm. They also apply their algorithm to pattern-aware prefetching. While Omnisc'IO targets the same goal, it differs in the underlying algorithm used (Sequiturinspired versus LZ77-inspired). Our approach also leverages stack traces to build a model of the program's behavior, whereas the solution proposed by He et al. works on the sequence of (offset,size) pairs.

2) Temporal prediction and scheduling: Prediction of temporal access pattern has been investigated by Tran and Reed [START_REF] Tran | Automatic ARIMA Time Series Modeling for Adaptive I/O Prefetching[END_REF] using ARIMA time series to model interarrival time between I/O requests. While the authors propose a solution that builds the model at run time, such statistical models need a large number of observations in order to converge to a good representation and, thus, good predictions. While ARIMA-based methods are effective at file system level when no knowledge can be retrieved from the application, we have shown that accurate predictions of interarrival times are possible at the application level without the need for such stochastic methods.

Byna et al. [START_REF] Byna | Parallel I/O Prefetching using MPI File Caching and I/O Signatures[END_REF] propose a notation called I/O signatures to assist I/O prefetching. I/O signatures describe the historic access pattern including the spatiality, request size, repetitive behavior, temporal intervals, and type of I/O operation. I/O signatures are stored persistently and can be used only in later runs.

Zhang et al. [START_REF] Zhang | Opportunistic Data-driven Execution of Parallel Programs for Efficient I/O Services[END_REF] couple I/O schedulers with process schedulers on compute nodes. When an application enters an I/O phase, it spawns new processes that pre-execute the code in order to find future I/O accesses while the main processes are waiting for the first access to complete. The knowledge of future accesses is then leveraged by the main processes. Considering the trend toward smaller operating systems with only restricted features, this kind of approach is likely not to be applicable in future machines with no preemptive process scheduler.

Several schedulers have been proposed that leverage some knowledge from the applications. The network request scheduler from Qian et al. [START_REF] Qian | A Novel Network Request Scheduler for a Large Scale Storage System[END_REF], built in Lustre [START_REF] Donovan | Lustre: Building a File System for 1000-Node Clusters[END_REF], associates deadlines to requests. A similar design is proposed by Song et al. [START_REF] Song | Server-Side I/O Coordination for Parallel File Systems[END_REF]. These schedulers are not based on any prediction, however, and could be greatly improved by knowledge extracted by Omnisc'IO on future access patterns. This knowledge can indeed help decide which application should be given priority to access the file system given its future access pattern. The scheduler proposed by Lebre et al. [START_REF] Lebre | I/O Scheduling Service for Multi-Application Clusters[END_REF] aims at aggregating and reordering requests while trying to maintain fairness across applications, a task that would undoubtedly be easier with any kind of prediction of future incoming I/O requests.

In our previous work [START_REF] Dorier | CALCioM: Mitigating I/O Interference in HPC Systems through Cross-Application Coordination[END_REF] we advocated for cross-application coordination to mitigate I/O interference. While the application user was required to explicitly instrument an application to expose its I/O patterns to other applications, the spatial and temporal I/O predictions presented in the present work can be leveraged to remove the need for this instrumentation and thus offer transparent cross-application I/O scheduling.

V. CONCLUSION The unprecedented scale of tomorrow's supercomputers forces researchers to consider new approaches to data management. In particular, self-adaptive and intelligent I/O systems that are capable of runtime analysis, modeling, and prediction of applications I/O behavior with little overhead and memory footprint will be of utmost importance to optimize prefetching, caching, or scheduling techniques.

In this paper we have presented Omnisc'IO, an approach that builds a model of I/O behavior using formal grammars. Omnisc'IO is transparent to the application, has negligible overhead in time and memory, and converges at run time without prior knowledge of the application.

We have evaluated Omnisc'IO with four real applications in a total of six scenarios. Omnisc'IO converges quickly to a stable model capable of predicting both the date and location of future I/O accesses, achieving a near-perfect hit ratio (from 79.5% to 100% in our experiments) and interaccess time estimation (up to 0.199 sec of average absolute difference with the observed interaccess time).

As future work, we plan to integrate Omnisc'IO within our previous CALCioM framework [START_REF] Dorier | CALCioM: Mitigating I/O Interference in HPC Systems through Cross-Application Coordination[END_REF] for efficient I/O scheduling and to implement prefetching and caching systems that leverage the excellent prediction capabilities shown by Omnisc'IO. We also plan to explore this approach as a mechanism for representing I/O behavior for replay in parallel discrete event simulations of large-scale HPC storage systems.

For reproducibility and comparison with later works, traces of all our experiments are available along with the code of Omnisc'IO at http://omniscio.gforge.inria.fr.

Fig. 1 :

 1 Fig. 1: Overview of the Omnisc'IO approach.

  int omniscio_next( omniscio_req ** prediction, int * n) This function allocates the prediction array and fills it

Fig. 2 :

 2 Fig. 2: Context prediction capability of Omnisc'IO over the run of each application. Configurations (a), (b), (c), (e), and (f) exhibit a clear learning phase after which Omnisc'IO makes perfect predictions ((e) and (f) exhibit a drop of prediction at the end of the first iteration).

Fig. 3 :

 3 Fig. 3: Evolution of main grammar size (sum of the length of each rule, in number of symbols).

Fig. 4 :

 4 Fig. 4: Relative error in the prediction of access sizes in all simulations.

Fig. 5 :

 5 Fig.5: Measurement of the hit ratio using Omnisc'IO to predict the location of the next accessed segment, as a function of the number of the number of operations completed.

Fig. 6 :

 6 Fig. 6: Matching between observed and predicted interarrival times of I/O events.

Fig. 7 :

 7 Fig. 7: Difference between predicted and observed interarrival times of I/O events.

TABLE I :

 I Examples of context-free grammars. Lowercase letters represent terminal symbols, while uppercase letters represent rules and their instances. Example 1 is correct from a Sequitur perspective. Example 2 violates the rule utility (rule A is used only once; it should be deleted an its only instance should be replaced by its content). Example 3 violates the digram uniqueness (digram ab appears twice; a new rule B → ab can be created to replace it).

	Example 1	Example 2	Example 3
	S → abAAe	S → abAe	S → ababAAe
	A → cd	A → cd	A → cd
	complexity both in space and in time.

TABLE II :

 II Predictors incrementation matching a given input.

TABLE IV :

 IV List of applications used and their I/O backends.

	Application	Field	I/O Method(s)
			HDF5+POSIX
	CM1	Climate	HDF5+MPI-I/O
			HDF5+Gzip
	GTC	Fusion	POSIX
	Nek5000	Fluid Dynamics	POSIX
	LAMMPS	Molecular Dynamics	POSIX
	with a set of predicted request structures (including the size,
	offset, and date) representing the expected next I/O accesses.
		III. EVALUATION
	In this section, we evaluate Omnisc'IO on real applications.

TABLE V :

 V Statistics on access sizes by each application.

	Application	Min Max	Average	Std. dev.
	CM1 (POSIX)	4 B	562.5 KB 212.9 KB 268.2 KB
	CM1 (Gzip)	4 B	28.1 KB	5.5 KB	10.0 KB
	CM1 (MPI-I/O) 4 B	562.5 KB 109.5 KB 219.8 KB
	Nek5000	4 B	96.0 KB	20.1 KB	29.7 KB
	GTC	4 B	8.0 KB	7.8 KB	100.0 B
	LAMMPS	3 B	2.70 MB	851.1 KB 1.24 MB

TABLE VI :

 VI Proportion of correct offset prediction using a naive contiguous offsets approach, and using Omnisc'IO, rounded to closest 0.1%.

	Application	Contiguous Accesses	Omnisc'IO
	CM1 (POSIX)	47.4%	92.2%
	CM1 (Gzip)	53.2%	83.0%
	CM1 (MPI-I/O)	72.7%	98.0%
	Nek5000	99.4%	99.7%
	GTC	99.9%	100%
	LAMMPS	99.9%	100%

TABLE VII :

 VII Average hit ratio achieved by Omnisc'IO, rounded to closest 0.1%.

	Application	Hit Ratio
	CM1 (POSIX)	84.6%
	CM1 (Gzip)	79.5%
	CM1 (MPI-I/O)	96.0%
	Nek5000	98.6%
	GTC	100%
	LAMMPS	99.4%

TABLE VIII :

 VIII Average time difference between predicted and observed interarrival times (rounded to closest millisecond), and comparison with an immediate re-access estimation.

	Application	Time Difference Immediate Reaccess
	CM1 (POSIX)	0.197 sec	0.735 sec
	CM1 (Gzip)	0.199 sec	0.791 sec
	CM1 (MPI-I/O)	0.060 sec	0.406 sec
	Nek5000	0.012 sec	0.049 sec
	GTC	0.001 sec	0.006 sec
	LAMMPS	0.000 sec	0.003 sec
	worst 0.199 seconds for CM1+Gzip, as opposed to 0.003 and
	0.791 seconds, respectively, when considering an immediate
	reaccess estimation.

TABLE IX :

 IX Overhead of Omnisc'IO in the run time of each application (in microseconds per operation).

	Application	Average Overhead	Std. dev.
	CM1 (POSIX)	20.51 µsec	18.27 µsec
	CM1 (Gzip)	20.20 µsec	15.56 µsec
	CM1 (MPI-I/O)	19.95 µsec	14.50 µsec
	Nek5000	23.44 µsec	18.96 µsec
	GTC	19.03 µsec	27.79 µsec
	LAMMPS	22.10 µsec	14.72 µsec
	require Omnisc'IO to know on which specific part of the entire
	simulation's data the branch depends.

http://www.sequitur.info/sequitur simple.cc

www.nics.tennessee.edu

www.ncsa.illinois.edu

www.olcf.ornl.gov

www.alcf.anl.gov

ACKNOWLEDGMENTS

The present work benefited from the input of Gaëlle Garet, from Inria Rennes, who provided valuable references on grammar inference. The authors also thank Gene Cooperman (Northwestern U.) and Gail Pieper (ANL) for their feedback on the paper. This work was done in the framework of a collaboration between the KerData joint Inria -ENS Rennes -Insa Rennes team and Argonne National Laboratory within the Joint INRIA-UIUC-ANL Laboratory for Petascale Computing. Experiments presented in this paper were carried out using the Grid5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER, and several Universities as well as other organizations (see http: //www.grid5000.fr/). This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, under contract number DE-AC02-06CH11357.