Christopher Sangwin
email: j.sangwin@ed.ac.uk

Developing and evaluating an online linear algebra examination for university mathematics

Keywords: Mathematics, undergraduate study, high stakes tests

In this paper I report development of an automatically marked online version of a current paperbased examination for a university mathematics course, and the extent to which the outcomes are equivalent to a paper-based exam. An online examination was implemented using the STACK online assessment tool which is built using computer algebra, and in which students' answers are normally typed expressions. The study group was 376 undergraduates taking a year 1 Introduction to Linear Algebra course. The results of this experiment are cautiously optimistic: a significant proportion of current examination questions can be automatically assessed, and the quantitative outcomes are moderately correlated with the paper examination.

Introduction

To what extent can we produce an automatically marked version of a paper-based examination for methods-based university mathematics courses using contemporary technology? To what extent are the outcomes of this exam equivalent to the outcomes of a paper-based exam? In this paper I report a pilot to develop, use, and evaluate an online examination for a university linear algebra course.

My work is based upon the epistemological position that to successfully automate a process it is necessary to understand it profoundly. It follows that automation of a process necessitates the development of a certain kind of understanding and we learn a lot about the underlying process through automation. Assessment provides students with challenge, interest and motivation: assessment is a key driver of students' activity in education. To many students mathematics is defined in a large part by what we expect students to do in examinations, [START_REF] Burkhardt | What you test is what you get[END_REF].

The STACK online assessment tool [START_REF] Sangwin | Computer aided assessment of mathematics[END_REF] is built using computer algebra and students' interactions move significantly beyond multiple choice questions with their well-known difficulties for mathematics, see [START_REF] Sangwin | Asymmetry in student achievement on multiple choice and constructed response items in reversible mathematics processes[END_REF]. In particular STACK uses the computer algebra system Maxima to generate random questions; interpret students' typed algebraic expressions; establish objective mathematical properties of students' answers; and assign outcomes such as feedback and marks. Online automatic assessment has for many years been used widely in formative settings, see [START_REF] Sangwin | Computer aided assessment of mathematics[END_REF]. Developing high-stakes final examinations is a natural extension of automation of formative assessment. Automation also has practical benefits, such as reducing the marking load, better test reliability, and potentially speeding up examination process. However, changing written examinations, with centuries of custom and practice, is a high-stakes and high-risk undertaking. When I examined school-level examinations [START_REF] Sangwin | Automation of mathematics examinations[END_REF] the results were cautiously optimistic: a significant proportion of current questions could be automatically assessed. In this paper I extend this work and create online examination questions and trial their use with a large group of university students.

Methodology

Changing examination processes is both high-stakes and high-risk. Furthermore, there are serious ethical problems with running an experiment in these circumstances without serious and authentic trial exams. Hence, for this study I added a mock online examination to an existing course: Introduction to Linear Algebra (ILA). This is a year 1, semester 1, mathematics course worth 20 credits taken by mathematics, computer science and other undergraduate students. Students normally take 120 credits per year, in two semesters. The course is defined by [START_REF] Poole | Linear algebra: a modern approach[END_REF] Chapters 1 to Chapter 6.2, with a selection of the applications included and selected topics omitted. ILA had over 600 students, of whom 578 took the final written examination and had a non-zero examination mark.

Students had requested exam practice, but it was impractical to administer and mark students' attempts in the short period between the end of teaching and the scheduled examination. Students would have expected more detailed formative feedback than provided by the genuine exam, and the genuine exam takes approximately 35 person-days to mark. In context, a mock examination was likely to be taken seriously by a significant proportion of the student cohort as a valuable practice and learning opportunity. Since the mock examination did not contribute to the overall course grade there was no incentive for students to cheat, or to be impersonated. Introduction to Linear Algebra, has an "open book" examination and so possible access to materials is less of a threat to this experiment than would be the case for a closed-book examination. The lack of certainty over who was sitting the online tests, the circumstances of participation, and the potential use of internet resources is certainly a compromise. Such uncertainty does not affect the extent to which I could produce questions at a technical level, or the effectiveness of the scoring mechanism in the face of students' attempts, which themselves constitute important results and generate key points for discussion. The results consist of a report on the extent to which current questions can be faithfully automated, and I give a report on students' attempts.

Results

The existing paper-based ILA examination takes 180 minutes and consists of Section A: compulsory questions worth 40 marks, and Section B: four questions each of 20 marks from which we take the student's best three marks. Students may use any standard scientific calculator but graphical calculators with matrix functions are not permitted.

The primary teaching goal was to provide students with an online examination which was as close as possible to the forthcoming paper-based summative course examination. The research goals were to evaluate the effectiveness of this, and to provide evidence for a discussion of equivalence with the genuine examination. ILA has been running for many years, with a stable (but not invariant) syllabus, and I had access to examinations going back to December 2011 (two per year: the main exam and an equivalent resit paper). I therefore decided to remove the oldest exam papers from easy access through the course website and base the online examination on those questions. Using as few papers as possible helps provide a representative online examination. Technically it is difficult to operate a "best 3 out of 4"' mark scheme in the STACK online system and in any case for a formative mock exam this makes little sense.

In deciding how to allocate marks I have taken a very strict interpretation. Specifically, where the original intention of the examiners included "with justification", I only awarded those marks which could be given for the answer only online. For example, Q5 on our online exam asked the following.

5. Is it possible for A and B to be 3*3 rank 2 matrices with AB = 0? True/False.

The original paper awarded 7 marks for the answer and justification, whereas only one mark was awarded for the correct answer. I did ask students to provide typed free-text justifications even though these would not be marked and no automatic feedback was provided. Ultimately I used two papers (120 marks each) to create the online exam. In this 59 marks of the online exam were from Dec-11 and 50 marks from Aug-12. I took one question from Dec-13 to add a mark to Section A to make the online exam total 110 marks.

Of the paper-based questions selected for the online exam, 44 marks are not awarded online. These missing marks are for justification which cannot, at this time, be automatically assessed. This resulted in Section A having fewer marks than would be the case with a paper based submission. Of the 240 marks available on the Dec-11 and Aug-12 papers, 109/240 marks 45% were automated in a way faithful to the original examinations. I think this is a remarkably high proportion, and discuss this in more detail below. However, the online versions as implemented for this study do lack some partial credit and do not (in this experiment) implement follow on-marking, which in some Section B questions is substantial. This is not a limitation of the system itself, but rather in the time available to implement more elaborate automatic marking schemes. Note that STACK requires students to type in an algebraic expression as their answer, and an example question is shown in figure 1. For ILA, online course work quizzes were already implemented using STACK. All students were expected to sit 30 online quizzes using the STACK system as part of the ILA course before the mock examination, and would be thoroughly familiar with how to enter answers into the system. The online examination was made available to students to do in their own time for a period of one week in December 2017, between the end of formal teaching and the scheduled paper-based exam. Students could choose when to sit the online examination, but were given one attempt of 180 minutes to do so to simulate examination practice. All data was downloaded from the online STACK system, and after ratification by the exam board, combined with overall achievement data. Students were assigned a unique number to ensure anonymity, and the data loaded into R-studio for analysis.

There were 395 attempts at the mock online exam in December 2017. One student who was granted a second attempt for technical reasons had their first attempt disregarded, giving 394 attempts. There were no other significant technical problems affecting the conduct of the online examination. For the online exam (including those who scored zero) the mean grade was 47.9% with standard deviation of 23.2%. The coefficient of internal consistency (Cronbach Alpha) for the online exam was 0.87. There was a moderate positive correlation between time taken (M=132 mins, SD=48.6 mins) and the online exam result (M=47.9%, SD=23.2) r(392)=0.517, p<10 -16 , as might be expected. Despite a small number of outlier questions, the mock online exam appears to have operated successfully in its own right as a test.

The final mark for ILA is made up of coursework (20%) and a final paper-based exam (80%). There were 394 attempts at the online mock examination, and all but one of these students also sat the paper-based examination. Note that 17 students scored 0 for the online exam, perhaps indicating students who looked at the online questions but made no serious attempt at them. Technically there is a difference between students who never sat the online exam, and those who opened the exam and scored 0. For the analysis I excluded the 17 students who scored 0 in the online exam: this leaves the study group of N=376 students with paper and mock exam information.

For the study group, the online exam results had (M=50.2, SD=21.3) and paper exam (M=68.0, SD=17.3). For all students who sat the ILA paper exam (M=63.1, SD=21.6). Histograms of achievement are shown in figure 2. The "online exam" refers to scores on the online mock. The "study group paper" is the achievement of the study group on the genuine paper examination. "Paper examination" refers to the whole cohort of ILA in the genuine paper exam. There is a significantly larger failure rate (score less than 40%) in the online examination, and a significantly lower mean. These differences could be explained by the level of engagement: the online exam carried no credit, and students may have lost motivation when tired. A scatter plot of the online mock exam grades vs paper exam grades is shown in figure 3, together with a linear regression model. The blue dashed line shows the (ideal) linear relationship in which the online mock examination has identical outcomes with the paper-based exam. The mock exam grades and paper exam grades were moderately correlated, r(374)=0.593, p<10 -15 . Notice the online exam scores are clearly below those of the paper exam, supporting the hypothesis that students may have lost motivation when tired and not performed to their full potential in the online mock exam. Indeed, students scoring less than 40% in the online exam and more that 70% in the genuine exam are very likely not to have taken the online test seriously, perhaps confident (with good reason) abou t their abilit y.

Figure 3: Online mock exam grades vs paper exam grades for the study group

The number of non-empty free text responses to each of the "justify" questions is worthy of mention here. While no planned evaluation of the responses was part of this study, it is clear reading through the free-text responses that over 200 students took the exercise seriously, providing sensible (and often correct) justifications in good English. For the Section A questions included in this study there were 59 marks available in the paper format, whereas in the online exam only 24 marks were awarded. I did not expect students to make serious use of the free-text entry. The fact students entered sensible justification to many of these questions, and received no marks or feedback, could easily account for the difference in mean scores between the paper-based and online exam. There were a large number of empty responses (as there are on paper as well), together with some incoherent utterances, and some plaintive messages. I did not assess these freetext responses, or subject them to comprehensive analysis for the purposes of this paper. However, in a genuine online examination such responses could be assessed (1) manually in the traditional way on-screen, (2) using automatic assessment technology such as described in [START_REF] Butcher | A comparison of human and computer marking of short free-text student responses[END_REF][START_REF] Jordan | Student engagement with assessment and feedback: Some lessons from short answer free-text e-assessment questions[END_REF], or (3) using comparative judgment for longer passages, see [START_REF] Jones | Assessing mathematical problem solving using comparative judgement[END_REF][START_REF] Pollitt | The method of adaptive comparative judgement[END_REF].

Discussion

The implementation of the mock online examination for linear algebra was a modest success. There were no serious technical problems during the conduct, and no students complained of inaccurate or unfair marking. The results of the online examination were broadly comparable with a paper-based exam, with the consistently lower online performance explained by a combination of (1) potential disengagement in a low-stakes setting, (2) lack of assessment of students' justification (which is typically rather generous), and (3) lack of partial credit and follow through marking.

This research has done nothing to address serious practical problems associated with online examinations in general. Problems include the need for invigilation to reduce plagiarism and impersonation, and security to eliminate communication during the exam (such as answer sharing) or access to unauthorised resources. Indeed, while technology has the potential to support examination processes, there is technology specifically designed to undermine traditional examinations as well. For example the Ruby Calculator (https://rubydevices.com.au retrieved September 2018) is designed to aid unauthorized communication during exams. Either these examination conduct problems must be solved, or we need new models of assessing students. But these examination conduct problems have nothing to do with mathematics as a subject. I think it is remarkable that 109/240 (45%) of the marks available on paper were automated in a way faithful to the original examinations. Further, by selecting existing questions from two existing past papers I was able to create a fully online exam, with broadly similar syllabus coverage. However, this result can be interpreted as a comment on the mechanical nature of the subject, and of the assessments we use in the traditional examination. If the assessment of students' answers can be automated, then certainly the underlying processes can be automated by the computer algebra system. Why then are students still learning to perform these mechanical processes, e.g. in the context of ILA row reduction, and calculation of determinants and eigenvalues/vectors? Both partial credit and follow through marking are technically possible in STACK, but are expensive (in staff time) to implement. To take this work further we need tools which automate assessment of explanation, justification and reasoning. In particular "proof checking" software, as applied to students' understanding, is necessary to move beyond assessing only a final answer to a full mathematical answer. In this study, only students' final answers were subject to automatic assessment which is a serious limitation to the award of partial credit and method marks. However, progress is being made to assess working especially in the area of reasoning by equivalence as discussed briefly in [START_REF] Sangwin | Automation of mathematics examinations[END_REF]. The work on reasoning by equivalence is essential for assessing questions in calculus and algebra, two other pillars of pure mathematics. For this reason, I am confident the cautious optimism expressed here about linear algebra exams also extends to mathematics more broadly in year 1 and 2 university methods-based examinations and mathematics examinations at the school/university interface.

I was surprised at the extent to which existing questions could be automatically assessed. However, there is nothing sacrosanct about current examination questions. Why should the online examination be exactly the same as a paper-based examination? Current questions are written explicitly for the paper-based format, and it is sensible to seek to write questions which are tuned to, or indeed take advantage of, the online format as appropriate. For many true/false questions the justification requires appropriate examples. Computer algebra is ideally suited to assessing answers, such as counter-examples, which expect the teacher to perform some time-consuming and potentially error-prone calculation. For this research I did not rephrase such questions to "give me examples, such that ...", but this would be one option. Specifically we could certainly have 5. Give examples A and B of non-zero 3*3 matrices for which AB = 0. A computer algebra system is ideally a much better tool for assessing such answers than a human marker. Hence, it would be much more sensible to design an online examination with the format in mind. Indeed, often human examiners do not ask students to "give examples of", only because of the work entailed in marking these by hand. That said, to establish face-validity for the online examination it is useful to understand the extent to which we can assess existing questions and to establish that the technical assessment processes are equivalent.

The practical benefits of online automatic examinations include increased reliability, reduction in costs and in swifter marking times. This is very attractive to all stake holders in the process, including students, teachers and end-users of the results. It is highly likely that automatic examinations will become the norm in the near future. Online examinations will happen, but there is no need for them to be restricted to multiple choice formats. Indeed, as a community of educators we can do much better than that. However, there is a real danger that national examination boards, universities, and others with responsibilities for examinations will replicate traditional examinations online without a critical reassessment of the purpose of mathematics education. This analysis raises the question of whether we, as a mathematics community, believe current mathematics examinations are a valid test of mathematical achievement. Do current examinations actually represent valid mathematical practice, as undertaken by researchers, industrial mathematicians and for pure recreation as an intellectual pursuit? Construct validity is a central educational concern, but it is not relevant to the research question of whether we can actually automate current exams. My personal views about the nature of mathematics broadly align with those expressed in [START_REF] Polya | Mathematics and plausible reasoning[END_REF] and [START_REF] Lakatos | Proofs and refutations[END_REF]. That is, that setting up abstract problems and solving them lies at the heart of mathematics. [START_REF] Polya | Mathematical discovery: on understanding, learning, and teaching problem solving[END_REF] identified four patterns of thought to help structure thinking about solving mathematical problems. His "Cartesian" pattern is where a problem is translated into a system of equations, and solved using algebra. Note that the algebraic manipulation is the technical middle step in the process: setting up the equations and interpreting the solutions are essential parts to complete this pattern. My previous work [START_REF] Sangwin | Automation of mathematics examinations[END_REF] examined questions set in school-level examination papers and found that line-by-line algebraic reasoning, termed reasoning by equivalence, is the most important single form of reasoning in school mathematics. However, many examination questions do not relate to a problem at all, rather they instruct students to undertake a well-rehearsed set of techniques, isolated from any problem. Many questions in the ILA examinations also rely on predictable methods which can be well-rehearsed.

Informal discussions with colleagues, particularly during the thematic working group 21 during CERME, strongly suggest that online examinations are a concern for many working in mathematics education. The question of validity of all examinations, on paper and online, is central as is the difficult question of retaining validity if an examination format changes. Changing to online examinations provides some unique opportunities but it will be essential for stake-holders to retain confidence in any new assessment regimes, regardless of any significant merits the format brings.

Using sophisticated assessment tools such as STACK we can create a fully automatically marked examination, which is broadly equivalent to current paper-based examinations at the technical level and in terms of outcomes for students. With other tools, we can create a more rounded online examination, perhaps incorporating some human assessment of free-text justification. However, the attempt to automate assessment of students' answers reveals much about what we really ask students to do in examinations.

Figure 1 :

 1 Figure 1: Question 19d of the current study in STACK

Figure 2 :

 2 Figure 2: Histograms of achievement in the online mock and paper based examinations


Fiorenza Turiano
email: fiorenza.turiano@gmail.com

Paolo Boero
email: boero@dima.unige.it

Francesca Morselli
email: morselli@dima.unige.it

Teaching, learning and assessing in grade 10: an experimental pathway to the culture of theorems

Keywords: Formative and summative assessment, proving, secondary school

This report deals with the design of a teaching and learning pathway that encompasses an assessment method coherent with the educational long term goal chosen by the teacher. More specifically, it is aimed at contributing to promote high school learners' culture of theoremsi.e. mastery of conjecturing and proving supported by meta-mathematical knowledge. The assessment method, which combines formative assessment all during the teaching sequence and final assessment based on student's self-reflective report on her learning trajectory, has been implemented in 10th grade classes. A written essay, in form of letter written by the students to a fictitious schoolmate at the end of the pathway, is analysed in order to evaluate the potential of the implemented course.

Introduction

In this contribution, we address the following issue, as outlined in the call for papers of TWG21: "The assessment of specific mathematics domainssuch as for example algebra or geometry -or capabilities such as problem solving or mathematical modelling". More specifically, we refer to the teaching and learning of mathematical proof and proving, conceptualized as the development of a specific "culture of theorems" [START_REF] Boero | Theorems in school[END_REF]. In our research group, we have been working for many years in the development of specific constructs and related experimental activities concerning proof and proving. In particular, we designed methods to foster students' awareness of crucial aspects of proving concerning their inherent strategies, what warrants the truth of the statements, and the logic-linguistic features of proof [START_REF] Boero | Argumentation and proof: A contribution to theoretical perspectives and their classroom implementation[END_REF]). Here we focus on the design of a whole teaching and learning pathway that encompasses also formative assessment strategies and final assessment of the individual competencies. From one side, we believe in the efficacy of formative assessment strategies in promoting the development of a culture of theorems. From the other side, we recognize that promoting a culture of theorems, in order to be effective in the institution, requires a coherent method of final assessment. For this reason, we inserted an innovative method of summative assessment in the project. The aim of this report is to present the teaching-learning (and assessing) pathway as it was implemented in two 10th-grade classes, and to illustrate data that provide some initial evidence of its effectiveness.

The culture of theorems

We refer to [START_REF] Mariotti | Introduction to proof: The mediation of a dynamic software environment[END_REF]'s construct of theorem: the theorem is made up of the statement, together with its proof within a theory. For the same statement, it is possible to consider different ways of proving it, according to different methods of proof and different theories. In that perspective, competencies in conjecturing ad proving concern, in particular, the mastery of metamathematical knowledge regarding: the shape of statements (hypothesis, thesis); different methods to validate a statement; the distinct role of previously proved theorems (as synthesizers of deductive chains needed to build up the proof) and axioms (as founding stones of a theory); the distinction between the construction and plausibility of a conjecture (based on different processes: induction, abduction, analogy, etc.) and the construction of a proof (which aims at a deductive enchaining of propositions within a theory). The development of a culture of theorems requires: autonomy in acting as problem solvers in conjecturing and proving; awareness of meta-mathematical issues (like the epistemic constraints and logic-linguistic features of proof - [START_REF] Stylianides | Understanding and describing mathematical knowledge for teaching: Knowledge about proof for engaging students in activities of proving[END_REF], which play a crucial role both in understanding a proof produced by others, and in conjecturing and proving by themselves. Promoting a culture of theorems in classroom means to foster students' awareness of these aspects and to make students develop a meta-mathematical knowledge [START_REF] Boero | Argumentation and proof: A contribution to theoretical perspectives and their classroom implementation[END_REF]) that supports the self-regulation of the process of conjecturing and proving.

The crucial role of assessment

We believe that assessment must be consistent with teaching's aims and with task design. As a starting point, we refer to the known distinction between formative assessment and summative assessment. Summative assessment occurs at the end of the learning activity with the goal of estimating the individual student's achievement [START_REF] Mcintosh | Formative Assessment in Mathematics. The Clearing House: A Journal of Educational Strategies[END_REF], and is generally used as part of the grading process. Formative assessment is performed during the learning activity with the aim of improving learning. It is also called "assessment for learning" and may be considered a method of teaching where "evidence about student achievement is elicited, interpreted, and used by teachers, learners, or their peers, to make decisions about the next steps in instruction." (Black & Wiliam, 2009, p.7). Wiliam and Thompson (2007) describe five key strategies to promote formative assessment in classroom, involving three agents: the teacher, the students and the peers. The five strategies are: a) clarifying and sharing learning intentions and criteria for success; b) engineering effective classroom discussions and other learning tasks that elicit evidence of student understanding; c) providing feedback that moves learners forward; d) activating students as instructional resources for one another; e) activating students as the owners of their own learning. Moreover, [START_REF] Nicol | Formative assessment and self-regulated learning: a model and seven principles of good feedback practice[END_REF] argue that formative assessment may promote students' self regulated learning. Recognizing formative assessment as crucial for learning does not mean to deny the crucial role of summative assessment. At the same time, it is important to move beyond a summative assessment that confines itself to a mere "final test", that hardly provides reliable information on the competencies that are acquired. For instance, [START_REF] Taras | The Use of Tutor Feedback and Student Self-assessment in Summative Assessment Tasks: Towards transparency for students and for tutors[END_REF] describes a research where cycles of summative self-assessment, tutor feedback on self-assessment and final revised self-assessment are carried out. The issue of summative assessment in mathematics becomes crucial when it has to be set up after innovation teaching and learning sequences. Assessment methods based on individual problem solving and answering teacher's questions usually have a negative impact on the development of students' autonomy and responsibility as learners in the classroom social context. In the special case of the teaching and learning of proof, traditional individual assessment tasks (presenting learnt proofs, adapting learnt proofs to similar situations, only seldom producing and validating conjectures), result in students' focusing on the products and their features.

Assessment in a "culture of theorems" perspective

In our teaching and learning pathway, we aimed at creating a formative and summative assessment that is coherent with the whole educational plan, aimed at promoting a culture of theorems. In the culture of theorems, it is important to make students active and autonomous, willing to take the responsibility of creating their own proofs and critically analyse the proofs produced by others. Accordingly, we created activities where students give constructive feedback to their mates and take profit from mate's feedback, becoming at the same responsible of their own learning and resources for the mates; in this way, formative strategies d) and e) (Wiliam & Thompson, 2007) are promoted. The formative assessment activities are integrated with a summative assessment method based on the student's self-reflective report on the personal learning trajectory, so as to assess whether the student is able to exploit the previous formative assessment activities and act as an autonomous learner. We hypothesize that thanks to the sequence of activities students not only are more free to take intellectual risks in conjecturing and proving, but may be induced to use meta-mathematical aspects of conjecturing and proving as key tools to regulate their productive and reflective activities given their role (supported by the teacher) in analysing their fellows and their own conjecturing and proving performances. We also hypothesize that a final assessment method, based on their selfreflective reports on their learning trajectory, might offer them the opportunity to get acceptable results and at the same time would offer them (also thanks to the kind of work performed in the classroom) key tools to re-orient and improve their work. Such an assessment method might also be useful for another reason, related to the condition of so many students who enter high school in our country (and in others too) with low self-confidence and scarce willingness to take intellectual risks. Failures in traditional assessment tasks would confirm them in their disposition towards classroom work [START_REF] Boaler | Identity, agency and knowing in mathematics worlds[END_REF]. We note here that such a form of summative assessment may be considered as an integral part of the teaching and learning pathway and, then, the boundary between formative and summative assessment is not strict in the project. A more detailed description of the teaching and learning method, as well as of the assessment strategies, is provided in the subsequent paragraph.

An innovative teaching and learning (and assessing) project

The context Our teaching method and assessment choices was implemented in one 10th-grade class of 21 students in the year 2016/17 and in two 10th-grade parallel classes (of 31 and 19 students) in 2017-18. The classes belong to the scientific-oriented high school, which in our country prepares students for all academic courses, especially for the studies in STEM. We focused on the geometry course, that is taught 2 hours each week, from October to May, in parallel with 3 hours devoted to algebra (first and second degree equations and systems of equations, functions, etc.) and probability, taught by the same teacher. The course consists of 3 modules of about 16 hours each; it concerns some content of Euclidean plane geometry, typically taught in our country in the first two years of high school: (first module) to construct a tangent circle to two intersecting straight lines; to construct the tangent circle inside a given triangle; (second module) to study different cases of triangles inscribed in a circle (rectangle, isosceles, equilateral triangles), with related necessary and sufficient conditions; to study the relations between peripheral angle and central angle; (third module) given a circle, to study the relationships between its tangent and intersecting straight lines; and, given a circle, to deal with some problems concerning inscribed and circumscribed quadrilaterals. The geometry course in grade 10 follows a grade 9 course in Euclidean plane geometry of triangles and quadrilaterals, which, in our case, was taught by the same teacher. All the lessons were given by the teacher (author FT); one researcher (the author PB) was present and acted as participant observer.

The course: teaching and formative assessment

In our pathway, a sequence of classroom activities ("module") usually consists of some cycles, each of them starting with an individual work on a worksheet, which includes one task and some information and framing of it. The task is open, possibly with some general suggestions about how to deal with it; it involves one of the following activities: conjecturing, with the aim of getting a statement conforming to the requirement of Euclidean geometry; constructing a geometric figure (which corresponds to the "building-up" part of Euclid's constructions); proving of produced conjectures, or justifying produced constructions (after they have been shared and better formulated under the guide of the teacher in classroom discussions); analysing mates' productions of previous tasks; identifying salient meta-mathematical aspects of produced texts. We note again that peer review is an efficient way of carrying out formative strategies d) and e) (Wiliam & Thompson, 2007). Each initial individual task of the cycle may be followed by an individual (or small group) analysis of some representative students' solutions to the task, chosen by the teacher; and/or by a direct classroom discussion of those solutions, guided by the teacher. In this way, formative assessment strategies b), d) and e) are activated (Wiliam & Thompson, 2007). Discussion is addressed to identify gaps, mistakes, points of strength, differences of produced strategies, linguistic issues and meta-mathematical aspects. Students are particularly motivated to engage in these activities, because they will turn to be useful for the the preparation of the final personal report (the key material for their summative assessment-see below). Usually, the second phase of the cycle ends with a synthesis, guided by the teacher, about one (or some) different ways of solving the problemspecial care being devoted to the organization of the proof text (in the case of tasks asking for a proof of a given statement) according to meta-mathematical constraints. The synthesis is a key moment for clarifying and sharing learning intentions and criteria for success (strategy a), Wiliam and Thompson, 2007). For some crucial steps of the sequence, students are then requested to write the refined, shared solution for the same task; or to identify hypothesis, thesis, theorems or axioms used as warrants, etc. in a proof text written by the teacher. Table 1 summarizes the activities that were carried out, in reference to the activated formative assessment strategies (as described by Wiliam & Thompson, 2007).

Activity

Formative assessment strategy Class discussion on selected productions b) engineering effective classroom discussions that elicit evidence of student understanding; c) providing feedback that moves learners forward; d) activating students as instructional resources for one another; e) activating students as the owners of their own learning Peer review of selected productions d) activating students as instructional resources for one another; e) activating students as the owners of their own learning Class discussion to synthetize and organize the final product, with a focus on meta-mathematical aspects a) clarifying and sharing learning intentions and criteria for success; b) engineering effective classroom discussions and other learning tasks that elicit evidence of student understanding

The final assessment

Final assessment is made up of two parts: part A is performed at home, part B is done in classroom. In part A students are requested to prepare (at the end of each of the three modules of the geometry course) a written revision of each of the worksheets produced during the module, followed by a synthesis paper. Students' revision work of personal filled worksheets concerns: identification of gaps, mistakes, difficulties and lacking knowledge at the content and at the meta-level; remediating gaps and mistakes, but in strict agreement (when appropriate) with the personal line of thought. According to our hypothesis, students are engaged in using criteria of meta-mathematical type to identify their difficulties and mistakes, with an inner questioning: "Does my conjecture contain a hypothesis and a thesis? (...) Are there some gaps in my enchaining of propositions?". This questioning at the intra-personal level would echo what should have happened at the inter-personal level in the classroom interactions managed by the teacher, and would contribute to enter the culture of theorems. The synthesis paper concerns: difficulties met during the module, and when and how (and if) they have been overcome; and on relevant learning progresses, and how they occurred, taking the collective classroom work into account. In part B, performed in classroom, students are asked to do the written revision of three worksheets, chosen by the teacher (one of them produced by a schoolfellow, the others by the student herselfthus, a second revision for them). Its purpose is to avoid that the student merely relies on help provided by some more competent fellow (or another expert person). There is no other assessment task for the geometry course. The final grade is given to each student taking into account the involvement during all the pathway (participation to the individual and groupwork and to the discussions) and the final assessment (parts A and B). Criteria for assessing parts A and B concern students'ability in: revising mistakes; improving written productions in terms of completeness, correctness and clarity; reflecting on the personal learning pathway. Essential features of the assessing method are similar to those implemented at the university level as described in [START_REF] Guala | Cultural analysis of mathematical content in teacher education: The case of elementary arithmetic theorems[END_REF].

Evaluation of the project: preliminary results

Our evaluation of the educational project is aimed at understanding whether the pathway was efficient in promoting students' culture of theorems, with specific reference to autonomy and awareness of meta-mathematical issues. For the evaluation, as we'll detail hereunder, we rely on direct observation of the students' activities and fieldnotes, as well as on the qualitative analysis of a special reflective task that was carried out by the students at the end of the pathway.

From the direct observation of students' activities and the fieldnotes of the teacher and the observer, we got some preliminary evidences of the fruitfulness of the adopted method. First, students' relationships with their mistakes and pitfalls during the individual work on their worksheets gradually evolved (at the beginning, mistakes and wrong paths to the solution were carefully erased or whitened in order to hide them; gradually students realized that the memory of wrong paths and mistakes is useful to prepare their self-reflective report, but also to better take part in discussions). Second, there was a growth in the attention paid by students to meta-mathematical aspects: gradually, more and more teacher's (or peers') comments on those aspects are reported in students' notebooks. Third, there was an evolution on kind of students' requests and comments concerning meta-mathematical aspects addressed to the teacher (or their schoolfellows) during classroom discussions.

At the end of the three modules, the students were proposed a reflective task: they were asked to write a letter to a fictitious schoolmate, describing the way of working with theorems they lived during the year. The idea of asking students to narrate their experience to a fictitious schoolmate is coherent with the learning-teaching pathway, where students were encouraged to act as resources for the peers; moreover, the request to write a letter was aimed to promote an informal style, where each student could feel free to insert personal reflections on the pathway. Here is the text of the task:

Paolo, a student of your age, will move to our school and will attend the second year course. By now, he did not do any specific activity on theorems (maybe he has some idea of what is a theorem). Since he heard that your class worked a lot on the statement and the proof of theorems, he would like to contact you to get a clearer idea on the theme. Write a letter to Paolo, telling briefly your experience; explain in particular what is the statement of a theorem and what does "proving it" mean.

We analysed the written letters, looking for elements of meta-mathematical knowledge, as well as reflections on the way students lived the pathway. We realized a qualitative analysis of the texts (performed by the authors separately and after compared and discussed so as to reach an agreement), that we summarize in the subsequent part of the paragraph. Concerning mathematical and metamathematical knowledge related to theorems, most students are able to discuss the key features of a theorem. They point out relevant elements of the statement (hypothesis, thesis) and are able to discuss the issue of validity of the theorem.

Ema: the statement is made of two parts: hypothesis and thesis. The hypothesis is often introduced by "IF", and it is the sentence that you suppose to be true or it is necessary to start your proof. The thesis is often introduced by "THEN" and it is that sentence that you proved in your proof and that, thanks to your proof, is true.

Giu: In mathematics, the THEOREM is a statement that, starting from initial assumptions that are taken as true, draws some conclusions, by means of a precise proof. Proving a theorem means to affirm its validity, following precise properties or mathematical laws.

We note that students are also able to describe proving as a process aimed at producing a final product, which is a relevant metamathematical issue.

Lor: there are different ways to think of a proof, I'll propose you some of them. The most common is to see a theorem as a mathematical problem; in both cases [the theorem and the problem] there are starting points and final points, justified by calculations or known theorems, that is to say already proven. But the interpretation [of theorem] I like the most is another one: you must imagine the theorem as a travel. […] Before starting the travel, but also during the travel, you must keep in mind the final destination (the thesis) and avoid roads that may lead you to a wrong reasoning. Like in a travel, there can be different roads that lead to the same destination, the thesis.

Giu: a good proof must be organized into three parts: exploration, with the construction of the figure, and observation of all possible relations between the parts of the figure; search for relations that are useful for the proof, with the support of mathematical laws and theorems that allow to affirm that a given thing is true; synthesis of all the process with letters, so that it is precise, well formulated and synthetized.

The letters contain also many hints on efficient ways to perform the process. This is again an evidence of awareness of metamathematical issues; moreover, the fact of being able to descrive the process and "give advices" to the fictitious mate reveals that the students became responsible of their own learning, real protagonists of the pathway, and also ready to act as resources for the mates.

Giu: In general, during the proof you must observe the figure with careful and "wise" eyes, so as to reach a conclusion. […] I suggest you to pay attention to the text of the task and to the figure, to write down all your observations and, even if you think they are un-correct, because they will become useful for the subsequent auto-correction activity. I suggest you to carry out the activities with a lot of care, for me it was very useful.

Mar: I suggest you not to focus on a single aspect of the statement, but to have a wider view and try to think of known theorems that could be useful.

The letters contain a description of the learning pathway, often intertwined with personal reflections on the way the students lived such an experience.

Marco: I liked very much this pathway, because it made me appreciate more geometry, that I did not like very much until last year. This system of activities (proving, constructing, experimenting) made some arguments nicer and helped me to learn them in a better way.

Ser: before starting the pathway I felt unsecure and skeptical, but I changed my opinion. I started the pathway with a little knowledge (few theorems and laws), that I had to review and re-discuss. During the pathway I thought again to that period of time when children ask the reason for everything, because by means of the activities we questioned many things that we had always taken for granted. […] You can't imagine how many times I struggled with wrong ideas that did not lead me anywhere, or we had an idea that we could not develop. Some students even reveal a good awareness of the rationale of the educational pathway they experienced.

Giu: for me, the activity of correcting our mates' answers was very useful, because we had to understand his reasoning and possibly correct some imperfections.

Mat: do not worry if at the beginning you can't find the good proof or fill the worksheets, because this is a new method for you, as it was for us. Indeed, the teachers do not judge the mistakes but evaluate your ability to recognize and correct mistakes by yourself. Moreover, this pathway will help you to get into another mate's reasoning and complete or correct it.

Table 1 : Activities and related formative assessment strategies

 1

Discussion and further developments

The preliminary analysis of the letters provided some evidence for the effectiveness of our pathway, with particular reference to the students' development of meta-mathematical knowledge concerning the culture of theorems and growing assumption of responsibility as learners. The research is still ongoing and we are currently analysing the reflective reports provided by the students at the end of the three modules. Some issues need further reflection. One crucial issue is: how to grade selfreflective reports in an objective way? Sharing with students precise criteria might better orient their work and make more explicit the teacher's expectations, but it could lead students to conform their reflections to a model. Another aspect which needs careful consideration is the development of students' awareness about their growing up as learners in the classroom context. It was put into evidence in a few final letters, while it is relevant for the development of competencies.


Abdulqawi Saif

Lucas Nussbaum

Ye-Qiong Song

On the Impact of I/O Access Patterns on SSD Storage

Keywords: IO patterns, solid-state drives, random workaloads, performance issues

Nowadays, solid-state drives (SSDs) are increasingly used in storage infrastructures thanks to their promising performance compared with hard disk drives (HDDs). Their internal architecture consists of parallel storage units that do not use mechanical movements, so considerably fortified for random data access. However, in this report, we show that some SSD storage is sensitive to I/O patterns, achieving low I/O performance in case of running random workloads. The performance degradation occurs with workloads that have specific characteristics such as having only one I/O process and I/O requests with small block sizes. After many investigations on the I/O stack and inside the SSD storage, our results show that the internal readahead of SSDs is behind the performance gap between the sequential and random workloads. Indeed, activating the internal readahead incurs a performance increase in case of sequential access thanks to pre-reading the next amount of data into the cache. In contrast, this makes no sense for random workloads as the upcoming requests may not depend on what already stored in the cache.

I/O operations are centric for big data systems where an enormous quantity of data should be accessed regularly. Maintaining an acceptable I/O performance during data access means dealing with many challenges not only over the I/O stack but also including the storage devices themselves. Because hard disk drives (HDDs) still appear in today's infrastructure, many improvements are made in the I/O stack to strengthen their performance. Indeed, tuning some parameters on the I/O stack such as activating a different I/O scheduler can mitigate the performance impacts of HDDs to some extent, giving a small increase of IOPS. However, this is seen by the perspective of nowadays' I/O workloads as a minor achievement, which indirectly pushes towards having more robust storage devices. Certainly, having a new generation of storage devices that eliminate the mechanical movements of HDDs would be a sound solution. Solid-state drives (SSDs) achieve higher performance than HDDs thanks to their complete change in design and architecture. They use performant storage units such as NAND flash memories for storing data, decreasing the performance gap between accessing data stored on RAM and secondary storage. However, the variety of I/O workloads makes it challenging to leverage the potential of SSDs for all use cases. On the one hand, many I/O workloads still have features that were useful to improve accessing data on HDDs, e.g., having I/O block sizes around 4 KB which is the size of memory pages in Linux. Doing so on SSDs does not make sense as SSDs have an internal page size between 4 KB and 4 MB. Hence, accessing data with small block sizes may nevertheless incur performance issues. On the other hand, SSD controllers are still black boxes, so extracting their internal configurations to adjust the workload characteristics accordingly is not feasible. Of course, methods such as extracting information from SSD behaviors [START_REF] Kim | Parameteraware i/o management for solid state disks (ssds)[END_REF] might be useful, but trying to do so every time having a different workload is exhaustive. Moreover, systems such as big data storage do not provide support about choosing suitable SSDs for their workloads. Given that, performance issues will occur sooner or later if workloads do not take into account the particularities of underlying storage devices.

Delivering a comparable performance for sequential and random workloads is one of the promising claims of SSDs. Since the majority of SSD devices rely on memory-like storage units, storing data sequentially and randomly should not provoke any issues. Indeed, the storage units take almost the same time to store the data in adjacent or far-off storage cells as there is no meaning of adjacency or contiguous allocation on SSDs. However, in a recent study that evaluates the performance of a NoSQL database [START_REF] Saif | Ioscope: A flexible i/o tracer for workloads' i/o pattern characterization[END_REF], we observed that the SSD storage in use reports a delayed execution time in case of running random workloads. The experiments' workload has been initiated by only one I/O process that frequently accesses massive data using I/O requests with small size. Taking into account the fact that such a workload does not exploit the parallelism of the used SSD, reporting a degraded performance for random workloads is not logically expected. Hence, we are motivated to do further investigations to explain the leading causes behind this unusual behavior.

In this report, we perform a study over SSD storage to reveal the responses to I/O pattern changes. We perform several experiments that take into account the workload characteristics [START_REF] Agrawal | Design tradeoffs for ssd performance[END_REF] with minor adjustment to show the components of a NAND flash of the study described in [START_REF] Saif | Ioscope: A flexible i/o tracer for workloads' i/o pattern characterization[END_REF]. Several potential areas that may affect the I/O performance are investigated here, trying to understand what pushes the SSDs understudy to report moderate I/O performance for random workloads. These areas are either related to 1) the workload itself such as the size of I/O requests and the concurrency of I/O processes, 2) the I/O stack such as the impact of I/O schedulers, 3) or related to the internal parameters of the storage devices themselves such as the internal readahead.

The rest of this report is organized as follows. Section 2 briefly describes the internal structure of SSDs. Section 3 presents the initial benchmarks that reveal the impacts of I/O patterns on SSDs, while Section 4 describes the experiments performed to investigate that issue. Section 5 concludes.

SSD internal design

Figure 1 shows the essential components of a NAND SSD. It consists of an interface to communicate with hosts' I/O stack, a controller with a CPU, buffer manager and RAMs, and a set of NAND memories connected to the SSD controller via a multiplexer. When an I/O request arrives at the host interface, the controller processes that request, and then determine the target flash NAND for writing or reading data.

Three operations can be performed on an SSD (read, write and erase) with different granularities: erase operations can be done on blocks while reading or writing operations work on the page level. Updating the stored data results on using new memory pages and marking the previous copy of data as a stale to be erased in the next erase cycle. Generally, SSD controllers try to reduce the erase cycles by spreading the data into more NAND memories as possible.

Data is stored in memory cells. Three types of memory cells can be used in SSD design. Single level cell (SLC) where each cell only stores one bit of data. Multiple level cell (MLC) where each cell has four different states, so storing two bits, and triple level cells (TLC) for storing three bits per cell. Although having the possibility to store more data using MLC or TLC NAND flashes, their write/erase cycles are limited compared with SLC SSDs. Finally, SSDs controller sends one command per NAND flash [START_REF] Bjørling | Lightnvm: The linux openchannel ssd subsystem[END_REF] while planes in each NAND support parallel executions during data writing or data retrieval. Sending one command at a time indicates that if a file's data is allocated on the same NAND flash, the performance may be degraded since the data access will be done sequentially over that NAND.

Performance of Random Workload on SSDs

After analyzing the workload of the experiments presented in [START_REF] Saif | Ioscope: A flexible i/o tracer for workloads' i/o pattern characterization[END_REF], we found that only one process performs the I/O activities of the executed workload. That process sends near 93% of I/O requests with 28 KB as a block size. The requests are sent directly to the storage device (synchronous I/Os) via pread syscall.

Although the internal architecture of SSDs can be different from an SSD to another one, we expect to have different performance results accordingly. Hence, we perform our initial experiments to reproduce the experiments of [START_REF] Saif | Ioscope: A flexible i/o tracer for workloads' i/o pattern characterization[END_REF] on three SSD models located in the Grid'5000 testbed [START_REF] Bolze | Grid'5000: A large scale and highly reconfigurable experimental grid testbed[END_REF]. These models are described in table 1.

We use Fio benchmark (v 2.16) to reproduce a similar workload. We create one process to mutually perform reading or writing operations over a file of 40 GB of data. Our experimental factors include two block sizes (4 KB & 28 KB) and two access modes (sequential & random). The experiments are performed on a machine running debian9 with Linux 4.9.0

fio --name TEST1 --filename=test.img --rw=read --size=35G --ioengine=sync --iodepth=64 --blocksize=4k --direct=1 --numjobs=1 --group_reporting Tables 2 & 3
show the results of reading and writing experiments on the SSDs described in table 1. For both experiments, increasing the block size of I/Os from 4 KB to 28 KB leads to an increase in the performance according to the SSD model. However, changing the access mode from sequential to random has a significant effect on the reading experiments; the throughput is degraded by half for some studied SSD models (PX055MB040 and C400) for both block sizes. Similarly, the writing performance is affected by switching the access mode between sequential and random. However, the performance difference does not exceed 30 MB/s which is not comparable with reading experiments where the access mode influences more the performance.

The next section describes the experiments performed to understand why the studied SSDs show degraded performance for random workloads.

Experimentation

Determining the primary cause behind the sensibility of certain SSDs to the I/O patterns is not easy since it can be related to several hypotheses. The reason could be either related to 1) the characteristics of the used workload (e.g., small I/O block size), 2) the configuration of I/O stack since some layers such as I/O scheduler can merge, sort, and/or delay the I/O requests for optimizing the performance, 3) the fact of having only one I/O process, or 4) the internal behaviors of the SSDs in use as they are not all impacted by random workloads (e.g., PX02SSF020 model). That I/O pattern sensibility could also be related to all these points together. We narrow our investigation scope to experimenting only on the PX05SMB040 SSD model since it is the most affected SSD by random reading workloads (see table 2). Inria q q q q q q q q q q q q q q q q q q q q 100 200 300

I/O block size experiments

Experiments that vary the I/O block size between 4 KB and 1 MB are performed. Figure 2 shows the results of these experiments. One can see that the throughput of the writing workloads is not affected if the data is accessed sequentially or randomly. It just increases by increasing the block size because larger block size means a larger quantity of data written by each I/O request. However, the impact of random workloads is present during the reading experiments. The gap between the throughput of sequential read and random read is shown on the block size points from 4 KB to 512 KB included. Using larger block sizes than 256 KB eliminates the gap of reading data sequentially or randomly. However, these results do not bring answers to understand why that gap is still present with smaller block sizes.

I/O scheduler experiments

We perform experiments using several I/O schedulers to identify if some of them provoke the performance degradation for random workloads. Linux proposes several I/O schedulers that are basically invented to minimize the HDD's internal seeks as the schedulers are nothing but algorithms to organize and reorder I/O requests. These schedulers are noop, deadline, and complete fair queuing (CFQ) ordered by their level of complexity from the simple to the most complex scheduler that creates several I/O queues per process. Although these schedulers are still usable with SSDs despite their HDD-related goals, I/O frameworks such as block multi-queue (aka blk-mq) are developed to optimize the I/O for SSDs. blk-mq completely RR n°9319 q q q q q q q q q q 100 150 200 250 300 cfq none a) Read q q q q q q q q q q 100 200 300 Figure 3 only shows the result of using CFQ scheduler and blk-mq none. Indeed, the results of noop and deadline are completely comparable with CFQ results due to the usage of only one I/O process in workload execution. In that figure, one can see that varying the I/O schedulers do not have any impacts on the performance as the curves of CFQ and blkmq none go hand in hand on both sub-figures. Additionally, these results do not explain the gap between the sequential and random workloads for small block I/O sizes. For instance, the performance of reading data using a block size of 28 KB is different for sequential and random access. It is near 250 MB/s in case of sequential reading while its less than 50 MB/s in the case of random reading.

Concurrent I/Os

We narrow our investigation scope to include block sizes between 4 KB & 64 KB since previous experiments show that the issue of random workloads occurs while dealing with small data sizes. We perform experiments with a different number of concurrent jobs, trying to understand if the issue is persistent regardless of the simultaneous access to disks' data.

Figure 4 shows the results of varying the number of jobs that access the SSD at the same time. Every job consists of an I/O process that tries to read sequentially or randomly its own 4 GB file. From a, b, and c sub-figures, it is clearly shown that the performance gap between the sequential and random reading workloads occurs when having only one I/O process. Increasing the number of concurrent jobs means sending many I/O requests at a time, Inria q q q q q q q q q q q q 100 200 300 400 1 4 8 16 23 64

N° of jobs (each x 4 GB) Throughput (MB/s) Access mode q q read randread a) block size = 4 KB q q q q q q q q q q q q 200 400 600 800 1 4 8 16 23 64

N° of jobs (each x 4 GB) Throughput (MB/s) Access mode q q read randread b) block size = 28 KB q q q q q q q q q q q q 200 400 600 800 1000

1 4 8 16 23 64
N° of jobs (each x 4 GB)

Throughput (MB/s) Access mode q q read randread c) block size = 32 KB q q q q q q q q q q q q 500 700 900 exploiting the parallelism of the SSD and eliminating the impact of random access. Indeed, having a large number of jobs indicates that the SSD controller fetches more data each time it accesses the NAND flashes as several files are read simultaneously. Additionally, the larger the block size, the larger the throughput. For instance, the corresponding throughout of 16 jobs in the sub-figures a, b, and c are 432 MB/s, 950 MB/s, and 964 MB/s respectively. Figure 4-d shows that the block size is also behind the issue of random performance. Increasing the block size to 64 KB leads to eliminate the performance gap between the sequential and random access even in case of using only one I/O process.

The results recommend having larger blocks size in order to leverage the potential of the storage device. However, it indicates that the SSD behaves abnormally using smaller block size. We expect that the internal usage of buffers and internal page size of SSD is behind that behavior. To emphasize, let us suppose that the internal page size of the used SSD is 64 KB and that a file is allocated on multiple NAND flashes. Randomly accessing that file using a block size of 4 KB means that each read will return 64 KB into the internal buffer, but only the target 4 KB will be sent back to the host. Having millions of I/O requests means that the NAND flashes are always accessed to retrieve the data. In contrast, this always robust the performance of sequential workloads even in case of a single I/O process as the I/O requests often have chances to retrieve data from the buffer instead of reaching the NAND flashes.

In the next subsection, we tune internal parameters of the used SSD in order to understand the performance while having one I/O process and small I/O requests.

RR n°9319

q q q q q q q q q q q q q q q q 0 250 500 750 read randread a) SSD's readahead enabled q q q q q q q q q q q q q q q q 0 250 500 Despite having hints about how to eliminate the performance gap between the sequential and random workloads, we try to tune some internal parameters of the used SSD to understand why that SSD is sensible to random workload in case of having small block sizes and one individual I/O process. We expect that buffering behaviors are behind the distinction of performance between sequential and random workloads.

The sdparm1 tool is used to alter the state of some internal parameters of the SSD. The study includes several parameters among them (RCD: read cache disable, WCE: write cache enable, FSW: force sequential write, & DRA: disable read ahead ). Our experiments show that all parameters except the DRA do not affect our experiments. Figure 5 shows the results of enabling and disabling the SSD's internal readahead over several block sizes. Figure 5-a shows that the pre-read of consequent segments of data increases the performance of sequential workloads, especially for the small I/O block sizes as most of the requests will end up reading from the buffer. In contrast, submitting random IOs does not benefit from such a feature since the SSD could not predict what data will be read next. Disabling SSD's readahead prevents pre-fetching data for sequential reads, resulting by having comparable performance between sequential and random reads.

Discussion

Although the experiments of the previous section confirm that the internal readahead is behind the performance gap between sequential and random reading workloads, this finding only concerns the studied SSD model (PX055MB040). Hence, we need to confirm that via experimenting on other SSDs, in order to neutralize the hardware effects on results. Although the SSDs showed in table 4 report a performance gap between sequential and random workloads, we are not able to confirm that the internal readahead is behind that performance gap as we do with the PX055MB040 SSD. Unfortunately, manipulating internal parameters of SSDs like the readahead is not always possible. It depends on the ability of the target SSD to integrate changes. On the one hand, disabling the internal readahead using sdparm for Samsung MZ7KM240HMHQ0D3 is not feasible since the readahead parameter on that SSD does not have a changeable state, i.e., we can only read its value. On the other hand, in the case of both Intel SSDs (see table 4), the sdparm indicates that the parameter is changeable, but the desired value cannot be saved into the SSD. It seems like there is an interface mismatch where the sdparm considers our parameter as changeable but unfortunately when we try to alter its value, the SSD refuses to integrate the new value. Given that, finding the main reason for the issue of I/O pattern sensibility on such SSDs is not feasible without the ability to tune their internal parameters.

Conclusions

SSDs are capable of serving a large number of I/O requests simultaneously thanks to having their performant storage units arranged in parallel. However, many systems and applications still use only one I/O process to frequently accessing small chunks of data. In this report, we show that such a use case reports different performance between sequential and random workloads. On one side, our experiments confirm that the internal readahead of certain SSDs is behind that issue as it does not improve the performance of random workloads as it does with sequential ones. Disabling the readahead feature leads to having a similar, but also a moderate performance as there is no more anticipation in data access for sequential workloads. On the other side, eliminating the performance gap without performance degradation can be done via either increasing the I/O block sizes or increasing the number of concurrent I/O processes. The higher the number of concurrent I/O processes, the higher the obtained performance of SSDs no matter if workloads are accessing data sequentially or randomly.

Future work should consider reproducing that study on open-channel SSDs such as Light-NVM -compatible SSDs. Their accessible and programmable controllers permit to study the internal parameters in details, eliminating the existing restriction of running experiments on black box SSDs.

Figure 1 :

 1 Figure 1: SSDs design [1] with minor adjustment to show the components of a NAND flash

Figure 2 :

 2 Figure 2: Varying I/O block size over the PX05SMB040 SSD

Figure 3 :

 3 Figure 3: Results of using CFQ scheduler and blk-mq with no scheduler over the PX05SMB040 SSD

Figure

  Figure Results of using concurrent Fio's jobs over the PX05SMB040 SSD

Figure 5 :

 5 Figure 5: The effects of SSD's internal readahead on the experiments

  Une Étude sur l'impact des Patterns d'Accès d'Entrée/Sortie sur le Stockage SSD Résumé : De nos jours, les disques SSD sont de plus en plus utilisés dans les infrastructures de stockage grâce à leur performance prometteuse par rapport aux disques durs. Ils ont des unités de stockage parallèles qui n'utilisent pas de mouvements mécaniques, donc fortement immunisés contre les workloads aléatoires. Cependant, dans ce rapport, nous montrons que certains modèles de disques SSD atteignent des performances moyennes avec des workloads aléatoires. Nous réalisons une série d'expériences utilisant une workload émise par un seul processus et ayant des petites requêtes d'entrée/sortie afin d'étudier la sensibilité des disques SSD aux patterns d'accès d'E/S. Le résultat montre que le readahead interne des disques SSD est le responsable principal de l'écart de performance de SSD entre l'utilisation de workloads séquentielles et aléatoires. Il augmente seulement la performance des workloads séquentielles et il n'affecte pas la performance des workloads aléatoires puisque les données lues en anticipation ne sont pas utiles et sont probablement effacées à chaque arrivée d'une nouvelle requête d'entrée/sortie.

Mots-clés : Pattern d'Entrée/Sortie, Disque SSD, charge de travail aléatoire, problème de performance 1 Introduction

Table 1 :

 1 Description of three SSD models used in the initial experimentation phase

	SSD model	SSD Type Size	Optimized for	manufacturer Year
	PX02SSF020	MLC	200 GB	High-endurance & write-intensive	Toshiba	2017
	PX05SMB040	MLC	400 GB	High Endurance	Toshiba	2016
	C400-MTFDDAA064M MLC	64 GB	-	Micron	< 2008

Table 2 :

 2 Results of sequential and random reading workloads on three models of SSD

	SSD model	Workload	4 KB block size 28 KB block size
	PX02SSF020	Read Rand. Read	43.2 MB/s 31 MB/s	172 MB/s 148 MB/s
	PX05SMB040	Read Rand. Read	136 MB/s 40.1 MB/s	491 MB/s 220 MB/s
	C400-MTFDDAA064M	Read Rand. Read	61.9 MB/s 25 MB/s	143 MB/s 75 MB/s

Table 3 :

 3 Results of sequential and random writing workloads on three models of SSDs The experimental factors are added to the Fio command or script. For instance, a Fio command to specify one I/O process for performing a sequential reading over a file of 35 GB and an I/O block size of 4 KB is as follows:

	SSD model	Workload	4 KB block size 28 KB block size
	PX02SSF020	Write Rand. Write	88.2 MB/s 64 MB/s	312 MB/s 292 MB/s
	PX05SMB040	Write Rand. Write	123 MB/s 99.2 MB/s	496 MB/s 470 MB/s
	C400-MTFDDAA064M	Write Rand. Write	58 MB/s 38 MB/s	97 MB/s 86 MB/s
	and ext4 as a filesystem.

Table 4 :

 4 A serie of SSD models for investigating the impacts of internal readahead on

	random workload performance
	SSD model	SSD Type Size	Optimized for	manufacturer Year
	MZ7KM240HMHQ0D3 MLC	240 GB	Reliability & heavy demands	Samsung	2017
	SSDSC2BB300G4T	MLC	300 GB Read intensive	Intel	2013
	SSDSC2KG480G7R	MLC	480 GB Read intensive	Intel	2017
	We perform further experiments on three different models of SSDs which show different
	performance for sequential and random workloads. The characteristics of these SSDs are
	described in table 4.

RR n°9319

Inria

A tool that can be used to change several control parameters for most SCSI devices Inria

rue du Jardin Botanique CS20101 54603 Villers-lès-Nancy Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399