Samaa M Shohieb
email: sm_shohieb@mans.edu.eg

Abd Elhady

Abdelrahman Mohsen

Abdelrahman Elbossaty

Eiad Rotab

Hajar Abdelmonem

Naira Elsaeed

Haidy Mostafa

Marwa Atef

Mai Tharwat

Abd Elghaffar

M Elhady

Aya Reda

Shaibou Abdoulai Haji
email: haji@korea.ac.kr

"Let's Play a Game!" Serious Games for Arabic Children with Dictation Difficulties

Keywords: Game-based Learning, Dictation Difficulty, Learning Disability, Technology in Learning, Human-Computer Interaction

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

Introduction and Motivation

Learning difficulties are neurological based processing problems. These processing problems can interfere with learning necessary skills such as reading, writing and mathematics. They can also interfere with higher level skills such as organization, time planning, long or short-term memory and attention. To handle learning difficulties, students need to practice a combination of their skills; information processing and motor skills. Some researchers studied the importance of a game-based approach for learning processes aiming at increasing engagement and motivation in general [START_REF] Venkatesh | Technology acceptance model 3 and a research agenda on interventions[END_REF][START_REF] Tan | Initial Perceptions of a Touch-Based Tablet Handwriting Serious Game[END_REF][START_REF] Shao | The effect of computer-assisted therapeutic practice for children with handwriting deficit: a comparison with the effect of the traditional sensorimotor approach[END_REF][START_REF] Giordano | Addressing dysgraphia with a mobile, webased software with interactive feedback[END_REF][START_REF] Maiorana | A Mobile Web Game Approach for Improving Dysgraphia[END_REF][START_REF] Borghese | Assessment of Exergames as Treatment and Prevention of Dysgraphia[END_REF][START_REF] Berningera | Computer instruction in handwriting, spelling, and composing for students with specific learning disabilities in grades 4 to 9[END_REF][START_REF] O'halloran | Using a tablet computer application to treat acquired dysgraphia and boost word output[END_REF]. Also, more specifically, attempts were made to handle learners with learning difficulties using game-based rehabilitation approach such as [START_REF] Tan | Initial Perceptions of a Touch-Based Tablet Handwriting Serious Game[END_REF] who presented a prototype of a tablet-based game for writing practice. The first evaluation was by adults (about 24 years) reporting a perception of an appreciation and usefulness of the gameplay. Researchers in [START_REF] Shao | The effect of computer-assisted therapeutic practice for children with handwriting deficit: a comparison with the effect of the traditional sensorimotor approach[END_REF] compared the sensorimotor approach with the effect of a computerassisted practice on handwriting problems reduction for children with learning difficulties and dictation difficulties. They performed their tests on 42 students divided into three groups; control group, sensorimotor approach group, and computer group. The computer group showed more significant development than the other groups.

Giordano and Maiorana [START_REF] Giordano | Addressing dysgraphia with a mobile, webased software with interactive feedback[END_REF] presented a practical web-based software system that can be used on tablets. Their system based on the Dynamic Time Warping algorithm to recognize the hand gestures through writing from merely connecting dots to complete writing a word that is compared with a reference trace that an expert has done. Also, [START_REF] Maiorana | A Mobile Web Game Approach for Improving Dysgraphia[END_REF] built a responsive web-based game to improve dysgraphia children' handwriting. The game helps students in writing words or letters to get a better score and make them practice in pre-graphism delete simple forms such as circles and straight lines, through many game motivations such as other rewards and more lives to advance in the game. They informally tested with children under the supervision of the developer. The students were engaged; the game has an impact on the students.

Moreover, Borghese et al. [START_REF] Borghese | Assessment of Exergames as Treatment and Prevention of Dysgraphia[END_REF] designed an early intervention game in collaboration with clinicians that was called "Exergames" for the dysgraphia disorder. The designed game focused on prewriting exercises. The Exergames were reliably tested on 16 kindergarten children. Berningera et al. [START_REF] Berningera | Computer instruction in handwriting, spelling, and composing for students with specific learning disabilities in grades 4 to 9[END_REF], as well, used iPad computer-assisted writing instruction to improve skills of students between 4 th and 9 th grade who suffer from dyslexia, dysgraphia or oral and written language learning disability (OWL LD) (impaired syntax composing). They proved that the customized computerized systems could be used for these grades successfully. O'Halloran [START_REF] O'halloran | Using a tablet computer application to treat acquired dysgraphia and boost word output[END_REF] designed an android based application based on the genetic algorithm that provides the participant with a series of cues (anagram, grapheme and semantic). The post-treatment attempts after applying their tests on real students showed that spelling moved closer to target words.

Most of the available works in handling students with dysgraphia difficulties target the English language except [START_REF] Salah | Super Alpha: Arabic Alphabet Learning Serious Game for Children with Learning Disabilities[END_REF] that presented and investigated the efficiency of an educational application that contained different games to handle some learning difficulties in the Arabic language especially reading difficulty. Therefore, there is a significant shortage of applications that handle students with dictation difficulties, a special type of dysgraphia, in the Arabic language. Consequently, this paper presents a design, implementation, and evaluation of an IOS games application [START_REF] Park | Development of gesture recognitionbased serious games[END_REF] that is dedicated to handling students with dictation difficulties at single word level and uti-lizes tablet computer or mobile devices as therapy tools. The implemented game focuses on students with dictation difficulties for the Arabic language. Our application helps students to learn how to write Arabic letters and words easily, how to differentiate between pronunciations of Arabic words, how to compare between similar Arabic (letters/word), how to know differences between directions and learning numbers more efficiently, as well. We called the gaming application "Mega Challenger" as it helps the student to challenge his/her difficulties so that he/she can achieve better learning performance.

The software user interface Mega Challenger design principles are presented in sections two and three respectively. Methodology and Experimental Design is discussed and proffered in section four. Section 5 presents the data analysis and results. Sections six and seven conclude and highlight future work respectively

Mega Challenger User Interface

Mega Challenger was implemented as ISO /IEC /IEEE 90003:2018 compatible software [START_REF]Software engineering -Guidelines for the application of ISO 9001:2015 to computer software Homepage[END_REF] and evaluated as ISO 25062:2006 (last reviewed and confirmed in 2019) [START_REF]Software engineering -Software product Quality Requirements and Evaluation (SQuaRE) -Common Industry Format (CIF) for usability test reports Homepage[END_REF]. It consists of three independent games that each game can be played independently from the other games. The games target enhancing a specific problem related to letter recognition and dictation difficulties. The first screen of the entire game is divided into three options; pronunciation of characters, learn how to spell words and write numbers, or the main directions as shown in figure 1, in the same order. The details of each game are described as following.

Pronunciation of Arabic letters

Students were presented with a list of the twenty-eight letters of the Arabic alphabet. When the student touches any letter from the list, he/she hear the pronunciation of the letter. This is considered a training level for the student. This is important to the students with dictation difficulties as it connects the hearing and sight senses with the learning process. Figure 2 shows a screenshot of the entire game. This was an extra feature added by the authors to add the efficiency and effectiveness of the game.

Learn How to Spell Words and Write Numbers

The second game is "Learning How to Spell Words". This helps the students with dictation difficulties on how to spell an Arabic word correctly. It advances in three subsequent levels. Words presented in the game were chosen sequenced systematically based on the "Nour Elbian" general guidelines to teach Arabic writing for children [START_REF] Elbian | [END_REF].

The first screen shows the word, picture to this word and a list of Arabic characters. The student must choose the correct letters of the shown word from the list. If the student chose the letter correctly would be shine, else nothing will happen to the letters, after student chooses all letters that included in the shown word and all of it became shine, he/she should write it correctly as shown in the reference word, figure 3.A. Mega Challenger will check the written word if it is true or false. If the written word is false, the student must repeat these steps. If the written word is correct student will go to the next level.

The second screen will show the same picture shown in the previous screen, but this time the picture is without a word. Instead, there are many choices of the related word but with wrong spelling. Only one of these words is correct, and the student must select the correct word from them. If the student's selection is correct, he/she will proceed to the third level, as shown in figure 3.B.

The third screen has a picture only, and the student writes the word that the picture represents without any help or reference word. If the student writes the correct word, he will proceed to another word. There are many words, and he must repeat these steps on each word, as shown in figure 3 Besides helping students in learning letters writing, they also learn in writing Indian numbers (the numbers technique used in the Arab world) correctly. Many levels from one to nine in which each screen has some fruits. The student is asked to count the number of appeared fruits and choose the correct number from the numbers given the list. If the selection is correct, the number will be put in the space and then disappear. The student repeats this step until he chooses the correct number. By this method, the student learns the correct way of writing numbers and the correct direction of numbers as shown in figures 4.

This game can handle children with dictation difficulties such as; change the word spelling, using a wrong letter or use similar characters, or even ignore writing some letters.

Learning Directions

Most of the students with dictation difficulties are not able to differentiate between directions. This game helps the student to learn the name of each direction and match with a suitable arrow. The student is asked to choose a suitable arrow for every direction. These levels are shown in figure 5 A B C Fig. 4. A game to help students in recognition and writing of the Indian numbers Fig. 5. A game to help students in recognition the directions

"Mega Challenger" Game Design Principles

The user interface of Mega Challenger is designed in a manner to fit children who start reading and writing (between 7-9 years old). The design principles are stratified with the guidelines of game design [START_REF] Moreno-Ger | Educational game design for online education[END_REF] which are to:

1. Provide informative and immediate feedback. The feedback is visualized through making a comparison with a reference trace and combined with written text. 2. Reduce short-term memory load. This is gained, for instance, by clearly visible record and score for playing the game. 3. Presentation based on a feedforward technique. For example, we used bright colors for objects, and light colors for backgrounds, so that the student can easily concentrate on the targeted task. 4. The game is accessible, free, and easy to reach on the Apple store. It can easily be installed on an iPad or iPhone device. 5. Tracking of student performance should be allowed in the game by storing his/her advancement and score.

A set of writing exercises are hidden inside the game dynamics that are presented to the children in a way to avoid boredom. Also, the game motivates the writing process of the players with offering immediate encouraging audible feedback reward to go ahead in the game.

Methodology and Experimental Design

This experiment tests the effect of playing the game on students with dictation difficulties motivation and learning performance achievement. The work has been accomplished through implementing a mobile-based application and testing it with a sample of students with dictation difficulties. The null hypothesis states that there is no statistically significant difference in student's achievement when they receive a learning game. The first hypothesis (H1) claims that students with dictation difficulties achieve better academic results when they play the game. The second hypothesis (H2) claims that students with dictation difficulties are more motivated in serious games.

Sampling Procedure

Students with dictation difficulty who are between seven and nine years old in Mansoura city primary schools, in Egypt, in the academic year 2018-2019 were the targeted statistical population of our experiments. The selected population (including 42 students from 3 different primary schools) is selected with utilising volunteering sampling technique after obtaining consent from their parents and an approval of the children to participate. An ethical approval was obtained from the ethics committee of the faculty of Computers and Information, Mansoura University_ Egypt. The students differ in their demographic data. Fifteen of them were girls and twenty seven were boys. Twenty of students were 7 years, ten of them were 8 years, and eight of them were 9 years.

Clinical Interview

Three psychological and behavioral experts have clinically interviewed the selected students. They analyzed the students by criteria of the 4th edition of Diagnostic and Statistical Manual of Mental Disorders (DSM-V MD) [START_REF] Kupfer | A research agenda for DSM V. American Psychiatric Pub[END_REF] to detect any mental, visual or auditory disability. Therefore, the dictation difficulties could be specified whether they are generated because of mental disabilities or learning disabilities.

Dictation Achievement Assessment

A dictation test from the academic books of the first grade is performed for the students to detect ones who have dictation disabilities. The test was performed according to standard dictation tests regulation; the dictation achievement test consists of 60 words [START_REF] Malekian | The effects of educational multimedia in dictation improvement of exceptional students with dictation difficulty[END_REF]. For more reliability and accuracy of the test, psychological and behavioral experts were scrutinizing the students' performance during the assessment. After performing the pre-assessment, students without dictation difficulties are given 0, and students with learning difficulties are given 1. Also, students with dictation difficulties were assigned a score between 1 and 10 to detect the achievement record and consequently the severity of their problem based on the dictation pre-assessment.

Test Conduction and Evaluation (Data Collection)

Mega Challenger was offered to learning difficulties specialists for evaluation and the software was modified based on their comments. Then the final version of the software was used with the students over 16 weeks with 48 sessions (3 sessions every week). Each session was about 10-15 minutes; this time is recommended by learning difficulties specialists who helped us. Sessions were conducted under the supervision of both the tutors of the difficulties specialists and the researchers. Mega Challenger was presented on a touch-tablets and touching phones. In order to maximize the benefit from Mega Challenger, students were asked to play the game in its sequence that was designed based on the "Nour Elbian" general guidelines to teach Arabic writing for children [START_REF] Elbian | [END_REF]. Finally, we administered a post to the students with dictation difficulties assessment and compared the results with the pre-assessment to determine how the computer-based game improves the performance of the students with dictation difficulties.

We presented a questionnaire to teachers of children with dictation difficulties. There were six teachers for 42 students in 3 primary schools. Questions were asked to the teachers after the user study (Table 1 that in turn concerned the perceptions of the teachers about utilizing Mega Challenger. All the presented questions were created based on usability measurements for game development standards [START_REF]Digital Game Development Standards Homepage[END_REF] and ISO 25062:2006 (last reviewed and confirmed in 2019) [START_REF]Software engineering -Software product Quality Requirements and Evaluation (SQuaRE) -Common Industry Format (CIF) for usability test reports Homepage[END_REF]. Questions were in Arabic language and translated into English after conducting the study for readability reasons. Authors conducted quantitative analyses on the collected interview content.

5

Results and Discussion

Usability test analysis

It was performed on questions that were asked to the teachers after the user study, which are formulated as seen in Table 1. This analysis was based on ISO 25062:2006 [START_REF]Software engineering -Software product Quality Requirements and Evaluation (SQuaRE) -Common Industry Format (CIF) for usability test reports Homepage[END_REF], which is a standard method for reporting the usability evaluation of an application.

Table 1. Questions Asked In the Interview after the User Study.

Q# Interview Questions 1.
Did your frequency of administering teaching sessions to your students increase after using Mega Challenger? Also, describe the time and place of using it most frequently.

2.

Describe any specific issues experienced while using Mega Challenger, and any notes you may have in that regard.

3.

Describe any noteworthy responses shown by your students while using Mega Challenger, and upon which feature/instance that response was given.

4.

Do you feel that Mega Challenger presented instructions and verbal communication clearly, i.e., was Mega Challenger clear enough to teach dictation through its instructions? 5.

Which one do you consider is the most suitable device size to utilize Mega Challenger: tablet or smartphone? 6.

Was your student able to use Mega Challenger alone (without assistance)? 7.

What would you recommend adding to Mega Challenger, and why? 8.

What do you consider the positive and negative aspects of "Mega Challenger" to be, and why?

These questions investigated teachers' experience with and feedback about using Mega Challenge. The usability measurements with each metric response are shown in Table 2.

Table 2. Usability Objective and Subjective Measurements.

Data analysis of student's performance in the pre-assessment and postassessment

The results show a significant difference between the student's performance in the pre-assessment and post-assessment . Consequently, the students were greatly motivated by playing a game. Base on the experiments we rejected the null hypothesis stating that there is no development in the student's performance when they receive a learning game. Results of each student for the pre and post-assessments are shown in figure 6.

Usability Attribute

The A paired-samples t-test was conducted to compare students' academic performance before and after using Mega Challenger. There was a significant difference in the scores of the students before (M=2.43, SD=1.06) and after (M=5.10, SD=1.32) using Mega Challenger; t (41) =-30.31, p = 0.000. These results suggest that the use of Mega Challenger does help students with dictation difficulties to perform better academically. Specifically, our results suggest that when academic games are incorporated into the teaching and learning process, it helps students with dictation difficulties.

Data were collected and analyzed to have an understanding of the effectiveness of the Mega Challenger. Post-assessment in combination with teacher's reports revealed that the Mega Challenge application was attractive to student. Also, the students were engaged by both the voiced pronunciation of the word. Teachers, additionally, mentioned that the application sounds provided uniformity in teaching dictation to students, which better accommodated the children's learning.

The majority of the participants gave positive responses to the questions, which revealed satisfactory user experience with the game. Figures 6 reveals that parents believed the application to fit students' needs, they can use the game almost every day at home. Teachers found it easy to use to calibrate the difficulty levels of teaching mate-rials, and to teach dictation via Mega Challenger. Teachers indicated that the application ran well on mobile phones, though they added that they may prefer tablets. They appreciated the accessibility of to the application as it could be used anywhere, how it could be used semi-independently or with simple guiding, and how smoothly the lessons went. They, consequently, recommended the inclusion of more vocabulary and ability to train of writing sentences.

Conclusions

Mega Challenger is a gaming application that has been built based on the teaching strategies applied for children with dictation difficulties. It was designed, implemented tested on 42 children who have different demographic data but all have dictation difficulties. According to the experimental results of the students, show a significant difference between the student's performance in the pre-assessment and postassessment. Usability evaluation of Mega Challenger, based on ISO 25062:2006 [START_REF]Software engineering -Software product Quality Requirements and Evaluation (SQuaRE) -Common Industry Format (CIF) for usability test reports Homepage[END_REF], on post-user study interviews with students' teachers concluded that Mega Challenger decreases the assessment loads of teachers. Mega Challenger is a promising tool for students who have dictation difficulty. We concluded that children with dictation difficulties achieve better academic results when they play the game and that children with dictation difficulties are more motivated in serious games.

7

Future Work

Improving the Interaction

Authors have observed that some children have weak finger muscle coordination or weak arms. Ex. While they try to touch the screen of the iPad, their touch finger sometimes crashed the surface, that the application incorrectly recognized that action as scrolling instead of touching. Therefore, the sensitivity of the application should be increased. Also, the author hopes to extend Mega Challenger to be feasible for much more learning difficulties, such as dyscalculia and dyslexia.

Enhancing the Interface

The next goal of this research is to enhance the Mega Challenger to teach complete sentences to the learning difficulty in the Arabic language. We can add acting verbs and the other sentence parts to the Mega Challenger.

Enhancing the User Centered Design

Enhancing the user-centred design by recruiting more volunteers as users is one of the most important issues in the future work. Mega Challenger needs to be tested on more children with dictation difficulties to take more feedbacks, consequently improving the game.

Fig. 1 .

 1 Fig. 1. The first screen of the entire game is divided into three options from top to down (Pronunciation of Arabic letters, Learn to write words and numbers, and Learning the main directions)

Fig. 2 .

 2 Fig. 2. A list of the twenty-eight letter of the Arabic alphabet embedded in the pronunciation of Arabic letters

Fig. 3 .

 3 Fig. 3. Learning how to write a specific word beginning from the easier to the harder

Fig. 6 .

 6 Fig. 6. Results of each student in the pre and post-assessment


Pisano G H E Periods

Duchamp

P Simonnet

Elementary remarks about

Keywords: Pisano periods, ring extensions, order

In this short note, we reprove in a very elementary way some known facts about Pisano periods as well as some considerations about the link between Pisano periods and the order of roots of the characteristic equation. The technics only requires a small background in ring theory (merely the definition of a commutative ring). The tools set here can be reused for all linear recurrences with quadratic non-constant characteristic equation.

Introduction

Let R be a commutative ring. The Fibonacci sequence within R is defined by the following recurrence.

F 0 = 0 R , F 1 = 1 R , F n+2 = F n + F n+1 (1)
It can be easily checked that this sequence is periodic iff the characteristic of the ring R is positive 1 . The period of F n (called Pisano period) is exactly the order of the invertible matrix 0 1

1 1 ∈ M(2, R) (2)
For introducing matters and results with respect to Pisano periods, see [2]. The aim of this short note is to write down some elementary facts about these periods and how, according to cases, it is exactly related to orders of some units in R. * gheduchamp@gmail.com † simonnet_p@univ-corse.fr 1 Although all the Fibonacci sequence lives in the subring Z.1 R (≃ Z / nZ where n is the characteritic of R), it be more compact (and a bit more elegant, due to the possible adjuntions) to consider the sequence as living in an arbitrary ring R. Some of the tools set here can be reused to cope with linear recurrences with quadratic non-constant (and invertible) characteristic equation.

Setting and results.

We discuss around the possiblity of solving the equation X 2 -X -1 = 0 within R.

Throughout the paper, we suppose that 1 R = 0 R (i.e. R is not the null ring) and that 5 = 5.1 R is a unit in R. We will call (E) the preceding equation i.e.

x 2 -x -1 = 0 (E)
and make use of

σ the automorphism of R[x] sending x → 1 -x.
First case: x 2 -x -1 = 0 has (at least) one root

We have the following lemma Lemma 2.1. We suppose that the equation (E) has at least one root in R (call it r and set s := 1 -r), then 1. s is a root of (E)

2. r and s are units in R 3. r -s is a square root of 5 and therefore also a unit in R 4. F n = r n -s n r-s (called Binet formula in ( [2], see also Max Alekseyev's answer in [START_REF]Complexity of a Fibonacci Numbers discrete[END_REF]).

The following matrix

1 1 r s (3)
is a unit in M(2, R) and 6. We have in M(2, R)

1 1 r s -1 0 1 1 1 1 1 r s = r 0 0 s (4) 7. Then the period of F n within R is infinite iff r or s is of infinite order. Proof. 1) Remarking that σ(x 2 -x -1) = x 2 -x -1 we get the result. 2) r(-s) = r(r -1) = r 2 -r = 1 then r -1 = -s and similarly s -1 = -r 3) (r -s) 2 = r 2 -2rs + s 2 = rs=-1 = r 2 + s 2 + 2 = r 2 =r+1 s 2 =s+1 r+s=1 = 5
Now, if y 2 = 5 and as 5 is a unit, we have y.(y/5) = y 2 .5 = 1 which proves that ±(r -s) are units in R. 4) (r n ) and (s n ) are sequences satisfying x n+2 = x n + x n+1 and the same holds for all their linear combinations in particular

t n = r n -s n r -s it suffices now to check that t i = F i for i = 0, 1. QED 5) One has 1 1 r s = s -r (5)
which is a unit from point (3). Therefore

1 1 r s -1 = 1 s -r s -1 -r 1 (6) 6) We have 0 1 1 1 1 1 r s = 1 1 r s r 0 0 s (7)
Hence (4). 7) Again, from equation ( 4), one has in M(2, R) × and R × ord( 0 1 1 1 ) = lcm(ord(r), ord(s)) (8)

We are now in the position to state Proposition 2.2. We suppose the hypotheses of Lemma 2.1. Then 1. The roots, r, s of (E) are both of finite or infinite order.

2. In the case when both roots are of finite order (a) Either 2.1 R = 0 R and ord(r) = ord(s) = 3.

(b) Or (2 = 0 and) one of the orders of r, s is odd (say ord(r) ≡ 1 mod 2) and the other one is the double of it (ord(s) = 2 ord(r)). In this case, the Pisano period is ord(s) = 2 ord(r) (c) Or (2 = 0 and) their orders are all even. In this case ord(s) = ord(r)

and the Pisano period is ord(s) = ord(r).

Proof. 1) Due to the fact that s = (-1/r) and r = (-1/s) (9) 2a) For g ∈ {r, s}, the group generated by g is {1, g, g + 1} hence g is of order 3. From now on we assume that 2 = 0. 2b) Let us now suppose that ord(r) ≡ 1 mod 2. Then, due to (9), we have 1 = s ord(s) ord(r) = (-1/r) ord(r) ord(s) = (-1) ord(s) (10) which, due to the fact that 2.1 R = 0 R , entails that s is of even order. But, in the same way, equation (9) shows that s 2. ord(r) = (-1) 2. ord(r) = 1 and then ord(s)|2. ord(r).

On the other hand r ord(s) = (-1/s) ord(s) = (-1) ord(s) = 1 this proves that ord(r)| ord(s). By Gauss lemma and taking into account that ord(r) is odd and ord(s) is even, we also have 2. ord(r)| ord(s). Finally ord(s)|2. ord(r)| ord(s) therefore ord(s) = 2. ord(r). 2c) Similar reasoning using (9).

Second case: x2 -x -1 = 0 has no roots in R.

We consider R 1 := R[x] (x 2 -x -1) and, with r = x (considering that 5 is still a unit in R 1 ), we are brought back to the preceding case. In this case, however, we remark that we have the automorphism σ sending x to (1 -x) which preserves the ideal (x 2 -x -1) and then passes to quotients (see Figure 1). this proves that r and σ(r) = 1 -r are of the same order 2 .

R[x] R[x] R[x] (x 2 -x -1) R[x] (x 2 -x -1)

Figure 1 :

 1 Figure 1: Involutive automorphism of R[x] (x 2 -x -1) without Galois theory.

This common order is necessarily even by the examination of the first case.


Zacharie Barrou Dumont

Pan-European snow cover products from Sentinel-2: algorithm and evaluation

The snow cover detection was evaluated over Europe using in situ snow depth observations at 1764 stations from 36 countries, totaling 26933 datapoints and covering a wide range of climate and topographic conditions. The evaluation database was prepared by merging two datasets of in situ snow depth (height of snow, HS) measurements : SYNOP data (WMO automatic weather station) and a compilation of measurements in the Alps (ALPS) from [Matiu et al., 2021]. The evaluation period spans a hydrological year from 1 September 2017 to 31 August 2018.

A sigmoid-shaped empirical function for estimating the top-of-canopy (TOC) FSC from the NDSI of the level 2A pixels was calibrated using snow maps classified from Pléiades very high resolution images.

In forest regions, the FSC is adjusted to subcanopy "on-ground" FSC using the Copernicus Sentinel-2-derived tree cover density (TCD). In particular, this service provides a canopy-adjusted fractional snow cover (FSC) at 20 m resolution along with a cloud and cloud shadow mask and quality flags. The products are derived from Sentinel-2 observations, resulting in a revisit time less than or equal to 5 days (except during low illumination periods in winter at high latitude).

The products are generated using the MAJA-LIS pipeline :

MAJA is a level 2A processor which provides slope corrected surface reflectance images including a coarse resolution cloud and cloud shadow mask. We found a good agreement between both datasets with an accuracy (proportion of correct classifications) of 94 % and kappa of 0.81.

Let

More accurate (+6 % kappa) retrievals were obtained by excluding low-quality pixels at the cost of a reduced coverage (-13 % data). Performances decreased at sites with higher tree cover density due to the obstruction of the ground surface by the tree canopy.

The FSC in open terrain was evaluated using SPOT 6/7 satellite images, time lapse camera photographs, terrestrial lidar scans and crowd-sourced in situ measurements

The root mean square error (RMSE) on the retrieved FSC is consistently estimated close to 25% Snow detection evaluation FSC evaluation [Muhuri et al., 2021] showed that the algorithm yielded similar performances (25-30% RMSE) as a computationally intensive spectral unmixing approach while retrieving the subcanopy ground FSC over a forested site in Sierra Nevada (USA).

••

  -It-Snow (LIS) provides the fractional snow cover (FSC) of every pixel identified as containing snow and a refined cloud mask : Threshold parameters : • Normalized Difference Snow Index (NDSI) pass: n 1 , n 2 • NDSI = f(green, swir) • Red band reflectance pass: r 1 , r 2 Pass 1 step: First snow detection • Snow if > n 1 and > r 1 and not in cloud mask • Used to calculate snowline • Snowline elevation step: calculate lowest elevation with significant snow amount z s . • Pass 2 step: final snow/cloud discrimination • Refine cloud + shadow mask • Snow if > n 2 , > r 2 and > z s DEM Sentinel-2 L2A products (MAJA software): • Green, red and swir reflectance bands • Coarse cloud +

•1

  Barrou Dumont et al. (2021) Brief communication: Evaluation of the snow cover detection in the Copernicus High Resolution Snow & Ice Monitoring Service, The Cryosphere • Muhuri et al. (2021) Performance Assessment of Optical Satellite Based Operational Snow Cover Monitoring Algorithms in Forested Landscapes, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing • Gascoin et al. (2020) Estimating fractional snow cover in open terrain from Sentinel-2 using the Normalized Difference Snow Index, Remote Sensing • Matiu, M. et al.: Observed snow depth trends in the European Alps: 1971 to 2019, The Cryosphere, 15, 1343-1382, https://doi.org/10.5194/tc-15-1343-2021, 2021. Centre d'Etudes Spatiales de la Biosphère (CESBIO), Université de Toulouse, CNRS/CNES/IRD/INRAE/UPS 2 Université de Sherbrooke 3 Magellium 4 Centre National d'Etudes Spatiales (CNES) FSC = 0.5 tanh(a NDSI + b) + 0.5 a = 2.65 ; b = -1.42 FSC (TOC)

Zacharie Barrou Dumont 1 , Simon Gascoin 1 , Arnab Muhuri 2 , Michaël Ablain 3 , Rémi Jugier 3 , Germain Salgues 3 , Florence Marti 3 , Aurore Dupuis 4 , Olivier Hagolle 1

	On behalf of the European Commission, the European Environment Agency has
	commissioned the development and real-time production of the Copernicus
	High Resolution Snow & Ice products (HRSI), including a snow cover component to address these needs.


Mohamed Benazouz
email: mohamed.benazouz@lip6.fr

Olivier Marchetti
email: olivier.marchetti@lip6.fr

Alix Munier-Kordon

Pascal Urard
email: pascal.urard@st.com

A new Approach for Minimizing Buffer Capacities with Throughput Constraint for Embedded System Design

Keywords: Timed Weighted Event Graphs, Synchronous Dataflow, Buffer minimization, Streaming applications

The design of streaming (e.g. multimedia or network packet processing) applications must consider several optimizations such as the mimimization of the whole surface of the memory needed on a Chip. The minimum throughput of the output is usually fixed. In this paper, we present an original methodology to solve this problem.

The application is modelled using a Marked Timed Weighted Event Graphs (in short MTWEG), which is a subclass of Petri nets. Transitions correspond to specific treatments and the places model buffers for data transfers. It is assumed that transitions are periodically fired with a fixed throughput.

The problem is first mathematically modelled using an Integer Linear Program. We then study for a unique buffer the optimum throughput according to the capacity. A first polynomial simple algorithm computing the minimum surface for a fixed throughput is derived when there is no circuit in the initial MTWEG, which corresponds to a wide class of applications. We prove in this case that the capacities of every buffer may be optimized independently.

For general MTWEG, the problem is NP-Hard and an original polynomial 2-approximation algorithm is presented. For practical applications, the solution computed is very close to the optimum.

I. INTRODUCTION AND RELATED WORK

Due to consumers expectations, embedded systems are becoming increasingly complex. For instance, many of mobile phones available on the market can take and display photos, download and play multimedia contents, and naturally allow to hold a telephone conversation. Most of these applications consist in data stream processing and can be splitted into a set of components or tasks performing specific treatments infinitely often and a set of buffers for data exchanges. Currently, the synchronous dataflow paradigm [START_REF] Lee | Synchronous data flow[END_REF] remains the most widely used in this specific area. In this model, an application is modelled by a directed graph where each node (resp. arc), called actor, models a component (resp. a buffer). In this producer/consumer paradigm, each actor activation requires to consume data in its input buffers. After a deterministic time, the actor will write data in its output buffers. In the Synchronous DataFlow model (in short SDF), the actors production/consumption rates are known at compile time. As the whole application has to be integrated on a single chip and satisfies high quality requirements, the buffer minimization problem with throughput constraints is crucial for the design of embedded system.

Nevertheless, in this paper, we consider Marked Timed Weighted Event Graph (in short MTWEG) which is a subclass of Petri net. In this model, transitions correspond to treatments of fixed processing times. Each place p models a buffer and has exactly one input arc and one output arc weighted respectively by u(p) and v(p). These values denote the number of tokens that has to be added to (resp. removed from) place p. If u(p) = v(p) = 1 for every place, we get a Marked Time (non Weighted) Event Graph (in short MTEG).

MTWEG and SDF are clearly equivalent formalisms. However, the Petri net model has been considerably expanded with many theoretical results from various scientific communities, providing a unified model with many results and algorithmic tools.

The determination of the liveness and the computation of the optimal throughput of a MTEG are two fundamental questions which are polynomially solved from a long time [START_REF] Commoner | Marked directed graphs[END_REF], [START_REF] Chrétienne | Les réseaux de petri temporisés[END_REF], [START_REF] Ramamoorthy | Performance evaluation of asynchronous concurrent systems using petri nets[END_REF]. The minimization of a weighted sum of the initial markings for a minimum given throughput of a MTEG is in N P , and many authors developed efficient heuristics and exact methods to solve it (see. as example [START_REF] Gaubert | An algebraic method for optimizing resources in timed event graphs[END_REF], [START_REF] Giua | Firing rate optimization of cyclic timed event graphs[END_REF], [START_REF] Laftit | Optimization of invariant criteria for event graphs[END_REF]). The N P -completeness of this problem was proved recently in [START_REF] Marchetti | Dimensionnement des mémoires pour systèmes embarqués[END_REF].

The existence of a polynomial algorithm for the liveness and the computation of the throughput of a MTWEG is a difficult question. Up to now, the time complexity of all the algorithms developed to answer these two fundamental questions is exponential in the worst case [START_REF] Teruel | On weighted T-systems[END_REF], [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problème d'assemblage[END_REF]. The consequence is that the optimization problems on MTWEG are possibly not in N P : the evaluation of the feasible solutions is not possible in polynomial time, which limits dramatically the existence of efficient algorithms. For example, Sauer [START_REF] Sauer | Marking optimization of weighted marked graph[END_REF] developed an algorithm to minimize the sum of the initial markings for a given throughput which evaluate a feasible solution using an exponential algorithm. The evaluation step of this algorithm limits significantly the size of the instances.

Another way to circumvent this problem is to reduce the set of feasible solutions. Benabid et al. [START_REF] Benabid | Periodic schedules for unitary timed weighted event graphs[END_REF] developed a polynomial time algorithm for the computation of a periodic firing of the transitions. This result can be regarded as a generalization of Reiter's result for MTEG [START_REF] Reiter | Scheduling parallel computations[END_REF]. In the case of MTWEG, the existence of a periodic firing of the transitions is clearly more restrictive than the liveness. On the same way, the throughput of a periodic firing is obtained by firing the transitions as soon as possible. However, optimization problems, such as the minimization of the initial markings are now in N P and efficient algorithms may be developed (even if the problem in N P -complete).

The minimization of the buffer capacities under a throughput constraint was also investigated by several authors using SDF model. The main drawback of all these approaches is that their complexity times depend on the numerical values of the instance, and leads, in the worst case, to exponentialtime algorithms. Adé et al. [START_REF] Adé | Buffer memory requirements in dsp applications[END_REF] and Murthy [START_REF] Murthy | Scheduling techniques for synchronous and multidimensional synchronous dataflow[END_REF] have both characterized the lowest capacity of a given buffer. Murthy has also showed that the minimization problem of buffer capacity of dataflow graph with a given initial buffers state is NP-Complete. To cope with this problem, Adé et al. [START_REF] Adé | Implementing dsp applications on heterogeneous targets using minimal size data buffers[END_REF], [START_REF] Adé | Data memory minimisation for synchronous data flow graphs emulated on dsp-fpga targets[END_REF] devise interesting heuristics to minimize the buffers sizes of a SDF graph such that there exists a valid schedule. In [START_REF] Govindarajan | Rate-optimal shcedule for multi-rate dsp computations[END_REF], [START_REF] Govindarajan | Minimizing memory requirements in rate-optimal schedule in regular dataflow networks[END_REF], several buffer minimization problems with throughput constraint are modelled using an Integer Linear Program. However, the number of constraints relies on the numerical values of consumption/production rates of the instance. More recently, in [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF], [START_REF] Ghamarian | Parametric throughput analysis of synchronous data flow graphs[END_REF] authors have dealed with this problem with throughput constraint based on a state space exploration with model checking techniques. Lastly, Wiggers et al. [START_REF] Wiggers | Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure[END_REF] developed a heuristic that aims to build a periodic firings of the transitions that minimizes the buffer capacities of a SDF.

The aim of this paper is to develop simple and efficient algorithms to solve the minimization of the overall number of initial tokens in a Timed Weighted Event Graph for a periodic firing with a given period. Section 2 is dedicated to basic definitions and the description of our problem. In Section 3, we show the modelling of a car radio using a MTWEG. In Section 4, we show that our problem can be formulated using an Integer Linear Program. The single buffer case is fully studied in Section 5 and a polynomial time algorithm is derived for an important sub-case of MTWEG. Section 6 is devoted to the presentation of a simple 2-approximation algorithm. Section 7 presents the resolution of the example using our algorithm. Section 8 is our conclusion.

II. MODEL AND NOTATIONS

A Marked Timed Weighted Event Graph G = (T, P, l, M 0 ) is defined by a set of places P = {p 1 , . . . , p m } and a set of transitions T = {t 1 , . . . , t n }. Every place p ∈ P is defined between two transitions t i and t j and is denoted by p = (t i , t j ). Each place p ∈ P is initially marked by M 0 (p) ∈ N tokens and is associated with two strictly positive integers u(p) and v(p) called the marking functions (see. figure 1).

For any transition t i ∈ T , we set P + (t i ) = {p = (t i , t j ) ∈ P, t j ∈ T } and P -(t i ) = {p = (t j , t i ) ∈ P, t j ∈ T }.

It is assumed that two successive firings of the same transition cannot overlap: this is modeled by a self-loop place p = (t i , t i ),

∀t i ∈ T with u(p) = v(p) = 1 and M 0 (p) = 1.
For a sake of simplicity, these loops are not pictured.

t i t j p M0(p) u(p) v(p)
Fig. 1. A place p = (t i , t j ) of a MTWEG.

We also suppose that a processing time ℓ(t i ) is associated to every transition t i . If t i is fired at time τ , v(p) tokens are removed from every place p ∈ P -(t i ). At time τ + ℓ(t i ), u(p) tokens are added to every place p ∈ P + (t i ). The instantaneaous marking of a place p ∈ P at time τ ≥ 0 is denoted by M (τ, p). Clearly, M (0, p) = M 0 (p).

A place p = (t i , t j ) has a bounded capacity F (p) > 0 if the number of tokens stored in p can not exceed F (p): ∀τ ≥ 0, M (τ, p) ≤ F (p). A MTWEG G = (T, P, M 0 , l, F ) is said to be a bounded capacity graph if the capacity of every place p ∈ P is bounded by F (p). It is proved in [START_REF] Marchetti | Minimizing place capacities of weighted event graphs for enforcing liveness[END_REF] that every place p = (t i , t j ) with bounded capacity may be replaced by a couple of places (p 1 = (t i , t j ), p 2 = (t j , t i )) denoted by (p 1 , p 2 ) c with the initial marking M 0 (p 1 ) = M 0 (p) and M 0 (p 2 ) = F (p) -M 0 (p). So, in this paper, we only consider symmetric MTWEG: every place p = (t i , t j ) is associated with a backward place p ′ = (t j , t i ) modelling the limited capacity. Note that a symmetric MTWEG is strongly connected: for every couple of vertices (x, y) ∈ (P ∪T ) 2 , there exists a path in G from x to y. In addition, to every couple of places (p, p ′ ) c modelling a buffer is associated a non negative cost by unit of capacity denoted by θ(p) = θ(p ′ ).

For any couple of integers (a, b) ∈ N 2 , gcd(a, b) denotes the greatest common divisor of a and b.

A. Schedules

Let G be a MTWEG. A schedule is a function s : T ×N ⋆ → Q + which associates, with any tuple (t i , q) ∈ T × N ⋆ , the starting time of the qth firing of t i . There is a strong relationship between a schedule and the corresponding instantaneous marking. Indeed, a schedule is feasible if the number of tokens of every place p = (t i , t j ) remains non negative at each time instant.

It has been proved in [START_REF]A sufficient condition for the liveness of weighted event graphs[END_REF] that the initial marking M 0 (p) of any place p = (t i , t j ) may be replaced by

M 0 (p) gcd(u(p), v(p))
gcd(u(p), v(p)) without any influence on s. Thus, we assume that the initial marking M 0 (p) of every place p = (t i , t j ) ∈ P is a multiple of gcd(u(p), v(p)).

The throughput of a transition t i for a schedule s is defined as

λ s (t i ) = lim q→∞ q s(t i , q) .
A schedule s is periodic if there exists a vector w = (w 1 , . . . , w n ) ∈ Q + n such that, for any couple (t i , q) ∈ T × N ⋆ , s(t i , q) = s(t i , 1) + (q -1)w i . w i is then the period of the transition t i and λ s (t i ) = 1 w i its throughput.

III. EXAMPLE

A. Description

Let us consider a car-radio application described in [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static real-time systems with back-pressure[END_REF]. The inputs of such systems are basically a MP3-reader and a cell phone. The output is a mixed sound from these two streams. Without any additional treatment, the output is reintroduced in the system through the cell phone, causing an echo effect. In order to obtain a pure speech in the cell phone, an additional input stream, corresponding to a microphone is added.

Figure 2 presents the streams and the main treatments. The first stream entrance, modelled by t 7 is the MP3 reader. t 10 corresponds to the entrance of the additional microphone. t 9 is the output. t 3 is the audio echo cancellation task. t 1 mixes the two input streams. t 5 produces a pure speech from the streams t 3 and the cell phone. The cost in such signal processing application may be interpreted by the size of samples exchanged between processes. Since in our case they exchange samples of the same size, we set θ(p) = 1 for every places p ∈ P .

t

B. The normalization step

A MTWEG is said to be normalized if all adjacent marking functions of every transition t i ∈ T are equal to a single value denoted by Z i , i.e. ∀p ∈ P + (t i ), u(p) = Z i and ∀p ∈ P -(t i ), v(p) = Z i . Note that the number of tokens remains constant in every circuit of a normalized graph. This simple important property eases the study of the liveness and the computation of periodic schedules (see. as example Theorem 1 below). We briefly recall here how every live symmetric MTWEG may be transformed into a normalized graph.

Let us first define the weight (or gain [START_REF] Karp | Properties of a model for parallel computations: Determinacy, termination, queueing[END_REF]) of every path µ of a MTWEG G by Rougthly speaking, for any circuit c of a MTWEG, W (c) can be viewed as the production rate of tokens on c. So, if W (c) < 1 for a given circuit, the number of tokens on this circuit decreases after a finite firing sequence and therefore it leads to a deadlock situation [START_REF] Teruel | On weighted T-systems[END_REF], [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problème d'assemblage[END_REF].

W (µ) = p∈P ∩µ u(p) v(p
In the sequel, a MTWEG G is said to be unitary if every circuit of G has a weight exactly equal to 1.

Every symmetric MTWEG G considered in our study is unitary: if it is not, there exists at least one circuit c of G such that W (c) > 1. So, the reverse circuit c ′ of c verifies

W (c ′ ) = 1 W (c) < 1
and thus, G is not live and no feasible schedule exists.

It is stated in [START_REF]A sufficient condition for the liveness of weighted event graphs[END_REF] that any unitary MTWEG can be polynomially transformed into an equivalent normalized MTWEG, i.e. with the same feasible schedules. It is firstly proved that, for any value α ∈ Q +⋆ , the markings functions and the initial markings of any place p ∈ P may be replaced simultaneously by respectively αu(p), αv(p) and αM 0 (p) without any influence on the schedules. Then, it is shown that positive integer values α(p), p ∈ P such that, ∀t i ∈ T , there exists an integer Z i with, ∀p ∈ P + (t i ), α(p)u(p) = Z i and ∀p ∈ P -(t i ), α(p)v(p) = Z i may be computed in polynomial time. Values Z i , t i ∈ T replace marking functions as said before.

The MTWEG depicted by Figure 3 is clearly not normalized. Moreover, since it is symmetric, we may have, for every couple of places (p i , p ′ i ) c with i ∈ {1, . . . , 10}, α(p i ) = α(p ′ i ). For our example, this yields to define the following system of equations:

                               Z 1 = α(p 1 ) = α(p 6 ) = α(p 8 ) = α(p 9 ) Z 2 = 441α(p 1 ) = 80α(p 2 ) Z 3 = 80α(p 2 ) = 80α(p 3 ) = 80α(p 10 ) Z 4 = α(p 3 ) = α(p 4 ) Z 5 = α(p 4 ) = α(p 5 ) Z 6 = 80α(p 5 ) = 441α(p 6 ) Z 7 = 1152α(p 7 ) Z 8 = 480α(p 7 ) = 441α(p 8 ) Z 9 = α(p 9 ) Z 10 = α(p 10 )
The minimal solution is given by (α(p 1 ), . .

C. Evaluation of the processing times

For our example, the throughput for the output transition t 9 must be equal to 44.1kHz that is to say ℓ(t 9 ) = w 9 = 1 44.1 ms. The following theorem, proved by [START_REF] Benabid | Periodic schedules for unitary timed weighted event graphs[END_REF], will provide an upper bound on the processing times of the other transitions.

Theorem 1. Let G be a normalized MTWEG. For any feasible periodic schedule s of G, there exists K ∈ Q ⋆+ such that, for any couple of transitions

(t i , t j ) ∈ T 2 , w i Z i = w j Z j = K.
Moreover, s is feasible iff, for any place p = (t i , t j ) ∈ P ,

s(t j , 1) -s(t i , 1) ≥ ℓ(t i ) + K(Z j -M 0 (p) -gcd i,j ).
where gcd i,j = gcd(Z i , Z j ).

By Theorem 1, we derive that K = w 9 Z 9 = 2.83 × 10 -4 ms.

The processing time of transition t 3 is fixed for physical considerations to ℓ(t 3 ) = 9.091ms. Fo the other transitions, the processing time must be at most equal to w i , thus we set ℓ(t i ) = w i . These values are reported in Table I.

IV. FORMULATION USING AN INTEGER LINEAR PROGRAM

Let G be a normalized symmetric MTWEG and K ∈ Q + a fixed value for the period. As seen before, a couple of places (p, p ′ ) c models a buffer of (unknown) minimum capacity F (p, p ′ ) = M 0 (p) + M 0 (p ′ ). Moreover, data stored in a buffer have all the same size depending on the buffer and denoted by θ(p). The general problem considered is to find an initial marking M 0 (p), p ∈ P such that:

1) The weighted capacity, proportional to the whole surface of the buffers p∈P θ(p)F (p, p ′ ) = p∈P θ(p)M 0 (p) is minimum.

2) There exists a periodic schedule with a period at most equal to K. The problem may be formulated by the following Integer Linear Program Π(K):

min p∈P θ(p)M 0 (p) subject to            ∀p = (t i , t j ) ∈ P, s(t j , 1) -s(t i , 1) ≥ ℓ(t i )+ K (Z j -M 0 (p) -gcd i,j ) ∀p = (t i , t j ) ∈ P, M 0 (p) = k i,j • gcd i,j ∀p = (t i , t j ) ∈ P k i,j ∈ N ∀t i ∈ T, s(t i , 1) ≥ 0
The first inequality expresses the necessary and sufficient condition associated with a place p on the first starting times of a feasible periodic schedule following Theorem 1. The second equality comes from the restriction of M 0 (p), p = (t i , t j ) ∈ P to multiples of gcd i,j = gcd(Z i , Z j ).

Let us note that, if the initial marking M 0 (p), p ∈ P is fixed, the corresponding optimum period may be easily computed: for any place p = (t i , t j ) ∈ P , let us denote by

H(p) = M 0 (p) + gcd i,j -Z j and L(p) = ℓ(t i ).
For a circuit c, H(c) = p∈c H(p) and L(c) = p∈c L(p). Theorem 2 expresses necessary and sufficient condition for the existence of a periodic schedule deduced easily from Bellman-Ford algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF].

Theorem 2 ([12]

). There exists a periodic schedule iff, for every circuit c of G, H(c) > 0.

The minimum feasible value K opt of K is then:

K opt = max c∈C(G) L(c) H(c) (1)
where C(G) denotes the set of circuits of G.

V. STUDY OF A BUFFER

A. Relationship between the optimum period and the capacity of a buffer

Let us consider a buffer modelled by a MTWEG G with a couple of transitions (t 1 , t 2 ) and a couple of places (p 1 , p 2 ) ∈ P 2 with p 1 = (t 1 , t 2 ) and p 2 = (t 2 , t 1 ). We study here the relationship between the minimum period K of a periodic schedule and the capacity F (p 1 , p 2 ) = M 0 (p 1 ) + M 0 (p 2 ) of the corresponding buffer.

First lemma expresses a lower bound on the capacity:

Lemma 1. The minimum capacity for the existence of a periodic schedule is

F min (p 1 , p 1 ) = Z 1 + Z 2 -gcd 1,2 .
Proof: G has three elementary circuits c 1 = (t 1 , t 1 ), c 2 = (t 2 , t 2 ) and c 3 = (t 1 , t 2 , t 1 ). By Theorem 2, there exists a periodic schedule if is also equal to the lowest capacity of a given buffer ( [START_REF] Adé | Buffer memory requirements in dsp applications[END_REF], [START_REF] Murthy | Scheduling techniques for synchronous and multidimensional synchronous dataflow[END_REF]).

H(c 1 ) = Z 1 > 0, H(c 1 ) = Z 2 > 0 and H(c 3 ) = F (p 1 , p 2 ) + 2gcd 1,2 -(Z 1 + Z 2 ) > 0. The last inequality is equivalent to F (p 1 , p 2 ) ≥ (Z 1 +Z 2 )-gcd
Let us suppose now that F (p 1 , p 2 ) ≥ F min (p 1 , p 2 ). From equation 1 in the previous section, the optimum value of the period for a fixed capacity F (p 1 , p 2 ) is

K opt = max ℓ(t 1 ) Z 1 , ℓ(t 2 ) Z 2 , ℓ(t 1 ) + ℓ(t 2 ) F (p 1 , p 2 ) + 2gcd 1,2 -(Z 1 + Z 2 )
Without loss of generality, we may assume that ℓ(t 1 )

Z 1 ≥ ℓ(t 2 ) Z 2
and thus

K opt = max ℓ(t 1 ) Z 1 , ℓ(t 1 ) + ℓ(t 2 ) F (p 1 , p 2 ) + 2gcd 1,2 -(Z 1 + Z 2 )
.

From a certain value of F (p 1 , p 2 ), K opt remains equal to ℓ(t 1 ) Z 1

. The following lemma characterizes this bound:

Lemma 2. The maximum value of capacity is F max (p 1 , p 2 ) = ℓ(t2) ℓ(t1) • Z1 gcd1,2 gcd 1,2 + 2Z 1 + Z 2 -2gcd 1,2 . Proof: F max (p 1 , p 2 ) is the minimum value for F (p 1 , p 2 ) such as ℓ(t 1 ) Z 1 ≥ ℓ(t 1 ) + ℓ(t 2 ) F (p 1 , p 2 ) + 2gcd 1,2 -(Z 1 + Z 2 )
Thus, we get

F (p 1 , p 2 ) ≥ ℓ(t 2 ) ℓ(t 1 ) + 2 Z 1 + Z 2 -2gcd 1,2 . Now, since F max (p 1 , p 2 ) is divisible by gcd 1,2 , F max (p 1 , p 2 ) = ℓ(t 2 ) ℓ(t 1 ) • Z 1 gcd 1,2 gcd 1,2 +2Z 1 +Z 2 -2gcd 1,2 .
Hence, the lemma.

The following theorem studies the determination of the optimum period for F (p 1 , p 2 ) between these two bounds:

Theorem 3. The function F (p 1 , p 2 ) -→ K opt is strictly decreasing and strictly convex for F (p 1 , p 2 ) ∈ {F min (p 1 , p 2 ), F min (p 1 , p 2 ) + gcd 1,2 , . . . , F max (p 1 , p 2 ) - gcd 1,2 , F max (p 1 , p 2 )}.
Proof: M 0 (p 1 ) and M 0 (p 2 ) are divisible by gcd 1,2 , so

F (p 1 , p 2 ) = M 0 (p 1 ) + M 0 (p 2 ) is. Now, for F (p 1 , p 2 ) ∈ {F min (p 1 , p 2 ), F min p1p2 + gcd 1,2 , . . . , F max (p 1 , p 2 ) - gcd 1,2 , F max (p 1 , p 2 )}, the corresponding value of K opt is ℓ(t 1 ) + ℓ(t 2 ) F (p 1 , p 2 ) + 2gcd 1,2 -(Z 1 + Z 2 )
which is strictly decreasing and strictly convex. Hence the result. This last theorem provides a good rule of thumb for the designer: "The more you increase buffer capacity, the less it increases the throughput." Let K min (p 1 , p 2 ) (resp. K max (p 1 , p 2 ) ) denotes the value of K opt for a buffer capacity equal to F min (p 1 , p 2 ) (resp.

F max (p 1 , p 2 ) ).
For example, let us consider the couple of places (p 7 , p 7 ) c from Figure 3. As seen before, normalized values for the adjacent transitions t 7 and t 8 are respectively Z 7 = 84672 and Z 8 = 35280 and gcd 7,8 = 7056. We get the bounds F min (p 7 , p ′ 7 ) = 16gcd 7,8 , K min (p 7 , p ′ 7 ) = 4.82 × 10 -3 ms, F max (p 7 , p ′ 7 ) = 32gcd 7,8 and K max (p 7 , p ′ 7 ) = 2.83 × 10 -4 ms. Figure 4 presents the variation of K opt according to F (p 7 , p ′ 7 ).

K opt (p 7 , p ′ 7 ) F (p 7 p ′ 7 ) × × × × × × × × × × × × × × × × × × × × 4.82×10 -3 2.41×10 -3 1.61×10 -3 2.83×10 -4 1 6 g c d 7 , 8 1 7 g c d 7 , 8 1 8 g c d 7 , 8 1 9 g c d 7 , 8 3 1 g c d 7 , 8 3 2 g c d 7 , 8
Fig. 4.

K opt according to F (p 7 , p ′ 7 ) = M 0 (p 7 ) + M 0 (p ′ 7 ). F min (p 7 , p ′ 7 ) = 16gcd 7,8 , K min (p 7 , p ′ 7 ) = 4.82 × 10 -3 ms, F max (p 7 , p ′ 7 ) = 32gcd 7,8 and K max (p 7 , p ′ 7 ) = 2.83 × 10 -4 ms.
Conversely, for any fixed value

K ∈ [K min (p 1 , p 2 ), K max (p 1 , p 2 )], the optimum value of capacity is F K (p 1 , p 2 ) = ℓ(t1)+ℓ(t2) K•gcd1,2 -2 gcd 1,2 + (Z 1 + Z 2 )
. Thus, the complexity to obtain the optimum capacity for a unique buffer is the computation of gcd 1,2 which is O(log(max{Z i , Z j })).

B. Consequence for a symmetric MWTEG without circuits of more than two transitions

Let us suppose that G is a symmetric MWTEG without any circuit of more than two transitions, i.e. the only circuits come from the buffer limitation. The undirected graph G = (T, E), for which every couple of places (p, p ′ ) c ∈ P 2 with p = (t i , t j ) and p ′ = (t j , t i ) is replaced by a unique edge (t i , t j ) ∈ E, is a tree. This limitation on the structure of G was extensively studied by many authors and corresponds to most of the applications (see. as example [START_REF] Wiggers | Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure[END_REF], [START_REF] Stuijk | Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs[END_REF], [START_REF] Ghamarian | Parametric throughput analysis of synchronous data flow graphs[END_REF]).

Starting from the Integer Linear Program Π(K) defined previously, we observe that there exists a periodic schedule of period

K iff 1) K ≥ max ti∈T ℓ(ti)
Zi and, 2) for every circuit c = (t i , t j , t i ) corresponding to a buffer, L(c) -KH(c) ≤ 0. The important point is that an optimum initial marking may be obtained by minimizing separately the capacity of each buffer.

For any fixed period K ≥ max ti∈T ℓ(ti)

Zi , an optimum marking of places p ∈ P is defined as follows. Let (p, p ′ ) c be a couple of places corresponding to a buffer:

1) If K ≤ K max (p, p ′ ), then the capacity of the corresponding buffer must be equal to F K (p, p ′ ). So, we set M 0 (p) = F K (p, p ′ ) and M 0 (p ′ ) = 0; 2) Else, K > K max (p, p ′ ) and this period may be achieved by the minimum capacity F min (p, p ′ ). We set then M 0 (p) = F min (p, p ′ ) and M 0 (p ′ ) = 0. This solution is clearly minimum for every buffer. So, it minimizes the overall weighted capacity of G. The complexity time of this algorithm is O(m log( max i∈{1,...,n} Z i )).

C. Example

The example depicted by Figure 3 does not verify the previous assumption. However, we may consider as example the subgraph G ′ limited to the transitions T ′ = {t 1 , t 5 , t 6 , t 7 , t 8 , t 9 } corresponding to the mixing of the sounds coming from the MP3 reader and the cell phone to the output. The corresponding undirected graph defined as G ′ = (T ′ , {{t 7 , t 8 }, {t 5 , t 6 }, {t 6 , t 1 }, {t 8 , t 1 }, {t 1 , t 9 }}) is clearly a tree.

Optimum values of capacity for this subgraph were calculated for K = 2.83 × 10 -4 ms and different processing time of t 8 . Values of the other transitions are fixed following Table I to ℓ(t 1 ) = l(t 9 ) = 2.3 × 10 -2 ms, ℓ(t 6 ) = 10ms and ℓ(t 7 ) = 24ms. Table II summarizes minimum capacities for different values of ℓ(t 8 ).

Note that the processing time of ℓ(t 8 ) only influences adjacent buffers corresponding to couples of places (p 7 , p ′ 7 ) c and (p 8 , p ′ 8 ) c . Their capacity decreases when ℓ(t 8 ) decreases. This point can be proved easily from the Integer Linear System Π(K). It was also noticed experimentally by [START_REF] Wiggers | Efficient computation of buffer capacities for multi-rate real-time systems with back-pressure[END_REF].

i,j ∈ N by k i,j ∈ Q + .
The idea of our approximation algorithm for the general case is to compute first polynomially an optimum solution M ⋆ 0 (p) ∈ Q, p ∈ P of Π ⋆ (K). A feasible solution M 0 (p) of Π(K) is then deduced using a rounding algorithm. Lemma 3. Let (p, p ′ ) c be a couple of place with p = (t i , t j ) and p ′ = (t j , t i ). Let also the value

F ⋆ K (p, p ′ ) = ℓ(t i ) + ℓ(t j ) K -2gcd i,j + (Z i + Z j ). Every feasible solution M ⋆ 0 of Π ⋆ (K) verifies M ⋆ 0 (p) + M ⋆ 0 (p ′ ) ≥ F ⋆ K (p, p ′ ). Proof: Let the circuit c = (t i , p, t j , p ′ , t i ) corresponding to a buffer. Then, L(c)-KH(c) = ℓ(t i )+ℓ(t j )-K(Z i +Z j - M ⋆ 0 (p) -M ⋆ 0 (p ′ ) -2gcd i,j ). Since M ⋆ 0 is feasible for Π ⋆ (K), we get L(c) -KH(c) ≤ 0 and thus M ⋆ 0 (p) + M ⋆ 0 (p ′ ) ≥ ℓ(t i ) + ℓ(t j ) K -2gcd i,j + (Z i + Z j
), the result. The following theorem characterizes an optimum feasible solution of Π ⋆ (K):

Theorem 4. Let M ⋆ 0 (p), p ∈ P defined as, for every couple of place (p, p ′ ) c , M ⋆ 0 (p) = M ⋆ 0 (p ′ ) = 1 2 F ⋆ K (p, p ′ ). Then, M ⋆ 0 (p), p ∈ P is an optimum solution of Π ⋆ (K). Proof: M ⋆ 0 is a feasible solution if, for every cir- cuit c = (t 1 , p 1 , t 2 , p 2 , . . . , t k , p k , t k+1 ) with t 1 = t k+1 , L(c) -KH(c) = k i=1 ℓ(t i ) + K( k i=1 Z i - k i=1 M ⋆ 0 (p i ) - k i=1 gcd i,i+1 ) ≤ 0. By definition of M ⋆ 0 (p i ), we have -M ⋆ 0 (p i )+ 1 2 ℓ(t i ) + ℓ(t i+1 ) K -2gcd i,i+1 + Z i + Z i+1 = 0
By summing these equalities for all places of the circuit, we get

- k i=1 M ⋆ 0 (p i ) + k i=1 ℓ(t i ) K - k i=1 gcd i,i+1 + k i=1 Z i = 0 ×K -K k i=1 M ⋆ 0 (p i ) + k i=1 ℓ(t i ) -K k i=1 gcd i,i+1 + K k i=1 Z i = 0 and thus L(c) -KH(c) = 0. So, M ⋆ 0 is a feasible solution. Now, from Lemma 3, M ⋆ 0 (p) + M ⋆ 0 (p ′
) is exactly the lower bound of the capacity of the buffer (p, p ′ ) and thus p∈P θ(p)M ⋆ 0 (p) is optimum. So, theorem holds.

Our approximation algorithm consists in setting, for every couple of places (p, p ′ ) c corresponding to a buffer with p = (t i , t j ) and p

′ = (t j , t i ), M ⋆ 0 (p) = M ⋆ 0 (p ′ ) = 1 2 F ⋆ K (p, p ′ ) and M App 0 (p) = M App 0 (p ′ ) = M ⋆ 0 (p) gcd i,j gcd i,j .
M App 0 (p), p ∈ P is clearly a feasible solution of Π(K). The following lemma provides a lower bound of the overall capacity: Lemma 4. Let (p, p ′ ) c be a couple of place with p = (t i , t j ) and p ′ = (t j , t i ) and let a K (p, p ′ ) =

F ⋆ K (p,p ′ ) gcdi,j gcd i,j . Then A K = 1 2 (p,p ′ )c∈P 2 θ(p)a K (p, p ′
) is a lower bound of the minimum overall weighted capacity for a fixed period K. and theorem holds.

Proof: Any feasible solution M 0 (p), p ∈ P of Π(K) verifies M 0 (p) + M 0 (p ′ ) ≥ M ⋆ 0 (p) + M ⋆ 0 (p ′ ). From Lemma 3, M ⋆ 0 (p)+M ⋆ 0 (p ′ ) ≥ F ⋆ K (p, p ′ ), so M 0 (p)+ M 0 (p ′ ) ≥ F ⋆ K (p, p ′ ). Since M 0 (p) + M 0 (p ′ )
A K and p=(ti,tj)∈P θ(p)gcd i,j are both lower bounds of the overall weighted capacity, and thus, we get a 2approximation algorithm. This worse performance may be easily achieved for a symmetric Timed (non weighted) Event Graph.

VII. APPLICATION TO THE CAR-RADIO

Table III summarizes the values obtained for our example by the previous approximation algorithm.

We get the lower bound A K = 6348 and the overall capacity of our solution is equal to 6350. It is thus at less than 0.04 percent from the optimum. Note that the capacity of most of the buffers equals the minimum value, thus it is optimum.

In [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static real-time systems with back-pressure[END_REF], the whole circuit is not considered. However, the computed capacities for buffer (p 3 , p ′

3 ) c is 158, which is not minimum.

VIII. CONCLUSION

We presented in this paper an original approach to solve efficiently the minimization of the buffer capacities with throughput constraints for a class of streaming applications. A simple mathematical modelization using an Integer Linear Program was first introduced. An exact polynomial simple algorithm was deduced from the theoretical study of the influence of the capacity on the throughput for an important special case of the MTWEG. A general polynomial approximation algorithm was also developed for the general case. The solutions obtained for simple practical examples are very close to the optimum and beats previous works. This new approach can be easily implemented to automatized the design of such systems.

Remark 1 .

 1 . . , α(p 10 )) = (80 441 441 441 441 80 73.5 80 80 441) and corresponds to the new marking functions Z = (80 35280 35280 441 441 35280 84672 35280 80 441). Normalization affects the cost of places. Indeed, for every couple of places (p, p ′ ) c in the initial graph, initial markings were multiplied by α(p) during the normalization step. So, to get the real overall capacity cost for this new normalized graph we have to divide the cost θ(p) by α(p).For our example, we get (θ(p 1 ), . . . , θ(p 10 ))

  Transitions t 2 , t 4 , t 6 and t 8 are simple rate converters. Places model intermediate buffers of limited capacity between the components.

	MP3 Reader	7	t 1	t 9	Out To Speaker
	Cell	t 5
	Phone
		t 3
	Micro-phone	t 10
			Signal to eliminate

Fig. 2. Block diagram of a car-radio application

Figure

3

shows the modelling of the whole application by a MTWEG G.

  1,2 since initial marking M 0 (p 1 ) and M 0 (p 2 ) are multiples of gcd 1,2 .

One can note that F min (p 1 , p 2 ) does not depend on the computation times of transitions (t 1 , t 2 ). Moreover, this value

TABLE I PROCESSING

 I TIMES ℓ(t i ), t i ∈ T IN MILLISECONDS

	t 1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10
	ℓ 2.3×10 -2	10	9.091	0.125	0.125	10	24	10	2.3×10 -2	0.125

TABLE II OPTIMAL

 II INITIAL MARKINGS OF THE SUBGRAPH G ′ FOR DIFFERENT PROCESSING TIME OF t 8 .

	ℓ(t 8 ) =	10	7.5		5	2.5
	θ(p 6 )F (p 6 , p ′ 6 )	882	882		882	882
	θ(p 7 )F (p 7 , p ′ 7 ) 3072	2976	2880	2784
	θ(p 8 )F (p 8 , p ′ 8 )	882	772		662	552
	θ(p 9 )F (p 9 , p ′ 9 )	2	2		2	2
	Sum	4838	4632	4426	4220
	VI. AN APPROXIMATION ALGORITHM FOR THE GENERAL
		CASE
	We suppose here that K ≥ max ti∈T us consider the Linear Program Π	ℓ(t i ) Z i	is a fixed value. Let

⋆ (K) obtained from Π(K)

by replacing the condition k

  is divisible by gcd i,j ,M 0 (p) + M 0 (p ′ ) ≥ a K (p ′ , p)and lemma is proved.This last theorem bounds the overall capacity obtained by our algoritm:Proof: For every couple of places (p, p ′ ) c ∈ P 2 with p = (t i , t j ),

	Theorem 5.
	p∈P	θ(p)M App 0	(p) ≤ A K +	1 2	(p,p ′ )c∈P 2 ,	θ(p)gcd i,j
							p=(ti,tj)
		M App 0	(p) + M App 0	(p ′ ) = 2	F ⋆ K (p, p ′ ) 2gcd i,j	gcd i,j .
	Now, since
	2	F ⋆ K (p, p ′ ) 2gcd i,j	gcd i,j ≤	F ⋆ K (p, p ′ ) gcd i,j	gcd i,j + gcd i,j
	then
	θ(p)M App 0	(p) ≤
	p∈P

= a K (p, p ′ ) + gcd i,j , p∈P θ(p)a K (p, p ′ )+ 1 2 (p,p ′ )c∈P 2 , p=(ti,tj) θ(p)gcd i,j

TABLE III OPTIMAL

 III BUFFERS CAPACITIES FOR THE MTWEG PICTURED BY FIGURE 3 Buffers θ(p i )a K (p i , p ′ i ) θ(p i )F App K (p i , p ′

	(p 1 , p ′ 1 )c	882	882	i )
	(p 2 , p ′ 2 )c	160	160
	(p 3 , p ′ 3 )c	153	154
	(p 4 , p ′ 4 )c	2	2
	(p 5 , p ′ 5 )c	160	160
	(p 6 , p ′ 6 )c	882	882
	(p 7 , p ′ 7 )c	3072	3072
	(p 8 , p ′ 8 )c	882	882
	(p 9 , p ′ 9 )c	2	2
	(p 10 , p ′ 10 )c	153	154
	Sum	6348	6350