Xavier Hadoux
email: xavier.hadoux@irstea.fr

Nathalie Gorretta

Gilles Rabatel

Weeds-wheat discrimination using hyperspectral imagery

Keywords: hyperspectral imagery, classification, weed detection, PLS-LDA

The difficulties to efficiently discriminate between weeds and crop by computer vision remains today a major obstacle to the promotion of localized weeding practices. The objective of the present study was to evaluate the potential of hyperspectral imagery for the detection of dicotyledonous weeds in durum wheat during weeding period (end of winter). An acquisition device based on a push-broom camera mounted on a motorized rail has been used to acquire top-view images of crop at a distance of one meter. A reference surface set in each image, as well as specific spectral pre-processing, allow overcoming variable outdoor lighting conditions. Spectral discrimination between weeds and crop, obtained by PLS-LDA, appears quite efficient, with a 8% prediction error on an independent test set.

Introduction

Precision Agriculture concept relies on the spatial modulation of crop processing operations, for a better adaptation to heterogeneities inside the parcel. This concept, which was raised more than twenty years ago, is now currently applied in nitrogen input management, allowing a better control on yield and product saving.

However, for weeding operations, despite considerable environmental and economical issues, the common practice still consist in applying an assurance strategy: herbicides are uniformly spread over the entire parcel whatever is the actual level of infestation.

The reason is mainly technological. Currently some devices are proposed on the market to operate localized spraying of herbicides on bare soil (the vegetation being detected by photocells). However, no commercial setup addresses localized weeding operations after crop emergence, because it requires a perception system based on computer vision, able to discriminate weeds from crop. Indeed, the identification of species inside vegetation is today the main obstacle to localized weeding. Numerous scientific studies have addressed this problem, and can be classified in two main approaches [START_REF] Slaughter | Autonomous robotic weed control systems : A review[END_REF]:

-The spectral approach, which focuses on the plant reflectance, and involves multispectral or hyperspectral imagery [START_REF] Feyaerts | Multi-spectral vision system for weed detection[END_REF], [START_REF] Vrindts | Weed Detection Using Canopy Reflection[END_REF]. In this case, the difficulty consists in establishing spectral differences that are robust with respect to variable lighting conditions.

-The spatial approach, which relies on spatial criteria such as plant morphology [START_REF] Chi | Leaf shape modelling and analysis using geometric descriptors derived from Bezier curves[END_REF], [START_REF] Manh | Weed Leaf Image Segmentation by Deformable Templates[END_REF], texture analysis [START_REF] Burks | Classification of weed species using colour texture features and discriminant analysis[END_REF] or spatial organization [START_REF] Gée | Crop/weed discrimination in perspective agronomic images[END_REF]. In this case, the natural complexity and variability of vegetation scenes are the main difficulties for classification.

The study presented here follows the first approach, in the particular case of durum wheat crop. The objective was to evaluate, as a first step, if the leaf reflectance contains enough spectral information to make a reliable discrimination between crop and dicotyledonous weeds. For this purpose, hyperspectral images of crop scenes have been acquired during the weeding period. Then specific correction procedures have been applied to overcome the variability of lighting conditions and of spatial orientation of leaves in natural crop scenes.

Finally, a Partial Least Square Linear Discrimination Analysis (PLS-LDA) discrimination model has been calibrated and tested on the corrected hyperspectral images. The discrimination results are presented and discussed.

Material and methods

Image acquisition and correction

Hyperspectral images of durum wheat have been acquired in an experimental station near Montpellier, south of France, in March 2011 and 2012. Images were acquired using a device specially developed by Irstea for in-field short-range hyperspectral imagery. The device consists in a push-broom CCD camera (HySpex VNIR 1600-160, Norsk Elektro Optikk, Norway) fitted on a tractor-mounted motorised rail. The camera has a spectral range from 0.4 µm to 1µm with a spectral resolution of 3.7nm. The first dimension of the CCD matrix is the spatial dimension (1600 pixels across track) and the second dimension is the spectral dimension (160 bands).

Each image represents about 0.30m across track by 1.50m along track seen at 1m above the canopy, the lens, and the view angle being fixed. The spatial resolution across track is 0.2 mm. The spatial resolution along track, depending on the motion speed, has therefore been adjusted.

In Fig. 1, two hyperspectral images are shown with false colours, i.e. using 3 bands respectively at 615, 564 and 459 nm as R, G, and B channels. These images illustrate the difference in lightning conditions we have to face in the following. In order to be able to compare spectral data collected in different outdoor conditions, it is necessary to have hyperspectral images independent of illumination, i.e. reflectance images.

The reflectance of a given material is the ratio of reflected light to incident light. Therefore, we need to know solar lighting at each acquisition time. Hence, Spectralon (Labsphere, Inc., New Hampshire, USA.) is generally used because it is a lambertian surface and it reflects 99 % of received signal whatever the wavelength. Therefore, it provides a good approximation of solar incident light in outdoor conditions. However, in our case, we have chosen to use a commercial ceramic plate, which is more robust to damage or dirt due to field experiment conditions.

The bidirectional reflectance distribution function (BRDF) of the ceramic has been measured in laboratory. As for many ordinary materials, it is the summation of a lambertian term and a specular term, the latter depending on the incident and viewing angles. However, because the specular term is directive enough, it can be totally neglected in our field operating conditions (horizontal plate observed with a zenithal view under non-zenithal solar lighting incidence, according to the latitude and season). We can thus consider the ceramic plate as a lambertian material with a known hemispheric reflectance

) ( Rc
Finally, for a given luminance image, the average luminance

) (

Lc

measured on the ceramic plate can be used to compute the horizontal irradiance

) ( E on the scene ) ( / ) ( ) (    Rc Lc E 
.This allows applying the following reflectance correction to every pixel in the image:

) ( ) ( ). , , ( ) ( / ) , , ( ) , , (       Lc Rc y x L E y x L y x R   (1)
Where ) , ( y x are the pixel coordinates and  the wavelength.

The reflectance correction specified in (1) takes into account the irradiance

) ( E
measured by means of a horizontal ceramic plate. However, leaf surfaces in the vegetation scene are not horizontal. Therefore, their irradiance can be higher or lower than the ceramic plate's one, according to the cosine of the angle between their surface normal and the lighting incidence. This introduces an unknown multiplicative factor 1 k on the pixel spectrum collected in the reflectance image, with respect to the real leaf reflectance. Also, the BRDF of leaves includes a specular term [START_REF] Bousquet | Leaf BRDF measurement and model for specular and diffuse component differentiation[END_REF]. Due to a random spatial orientation, this specular reflection may be directed toward the image sensor. The corresponding specular light is not spectrally modified by the material and only contributes to the apparent reflectance as an additive term 2 k .

As a summary, the leaf pixel values in the reflectance image do not correspond to the actual leaf lambertian reflectance

) , , (  y x R f
but to an apparent reflectance:

2 1 ) , , (
k k y x R R f app     (2)
Where 1 k and 2 k are unknown terms.

In order to remove these unknown terms, a Standard Normal Variate (SNV) transformation will be applied consistently to all spectra before any further processing. It consists in centring the spectrum and setting its standard deviation equal to one.

Modelling procedure (experiment's design)

Since we have an important amount of spectra, we choose to build the model which gives the most reliable error estimation using an independant test set. In order to create this proper discrimination model, a calibration set, a validation set and a test set have to be built. A major sampling condition we took into consideration while designing the experiment is the independence between each set. For this purpose, we first split our images into three groups. Then, in each of these groups, we have manually selected some spectra according to three classes: durum wheat, dicotyledonous weeds and soil. By this way, in each set, both X-values (spectrum) and Y-values (classes) are known. Y is coded using a disjunctive binary coding (0 or 1). Table 1 details the number of selected spectra in each class for each set.

PLS-LDA

Because they contain accurate information about the chemical content of materials, spectra are often used for quantitative evaluation of component concentration, or for material discrimination. However, due to the high dimension of spectral data (hundreds of variables), classical multivariate regression or discrimination tools are not directly usable, and a first step of dimension reduction is generally required. In this context, the Partial-Least-Square (PLS) has become a very commonly used tool, thanks to its ability to determinate a pertinent subspace, called scores subspace, for a given regression problem. Unlike other dimension reduction methods, the PLS takes into account the covariance of both inputs and outputs to determine this scores subspace. To find the score subspace, PLS iteratively find the Latent Variables (LV) that produce the best trade-off between the explanation of the input, the explanation of the output, and the relation between the input and the output.

Then, both input and output are projected onto the formerly found LV and a new iteration begins. The number of iterations (the number of latent variables) is determined empirically using the V-shape of the Root Mean Square Error of Validation (RMSEV) described below.

Finally, a LDA is performed on the LV. This LDA consist in finding the linear subspace that allow the easiest discrimination. The well known solution to this problem is the subspace that maximise the variance between the classes and minimise the variance within the classes.

Calibration/Validation phase

During this phase, we want to figure out how many LV we need to keep for the model. To this purpose, we create a model using the variables in the calibration set. This procedure consists in creating models, with an increasing number of LV, using the calibration set. Applying these models on the validation set allows a computation of the RMSEV. The RMSEV is calculated by comparing the real val Y of the validation set with the estimated where the latter represent the results testing the calibration model directly on the calibration data.

Test phase

Applying this model on the independent test set allows the calculation of the Root Mean Square Error of Prediction (RMSEP). This RMSEP is the most reliable measure of prediction for this kind of model.

Results and discussion

Model calibration/validation

In order to illustrate the classification procedure, the RMSEC and the RMSEV curves are plotted in Fig. 2, for 1 to 20 LV. According to this plot, 7 LV are chosen for the PLS-LDA model.

In Table 2 the resulting confusion matrix of the validation. As it could be expected, the best membership estimation is obtained for the soil, which is spectrally very different from vegetation. The classification performances are good, with a global error rate of 8.4% and a maximal error of 11%. the results presented on Table 3. From these results, the global error of prediction is 7.9% which correspond to the global error during the validation. However, the maximal error is slightly superior with 14.6% of misclassified weed pixels. This test set validation confirms the robustness of the model created with a totally independent calibration test. Also, since images have been taken with a high difference of illumination, at different times and over two different years, we have a good chance that the model we produced will still be robust for the next season.

Conclusion

The results obtained above show the potential of detailed spectral information to discriminate vegetation species, provided the influence of lighting variability has been overcome using a reference material, and provided efficient chemometric tools such are PLS-LDA are utilised. However, despite the robustness, the classification errors are still important, due to the variability of the images taken at different time, different parcels and over two different years.

Moreover, the high number of required latent variables indicates that very tiny differences in the spectral shapes are taken into account to achieve an accurate discrimination.

The following step will be to evaluate the possibility of introducing spatial constraints to help the discrimination stage. Also, reducing the number of required bands, e.g. through a detailed study of the latent variable shapes would open the door to an operational device based on multispectral image acquisition.

FIGURE 1 :

 1 FIGURE 1: Two reflectance images in false RGB colours with different lighting conditions without shadow (up), with shadows (down). On the left : the ceramique plate.

  model. Plotting this error for an increasing number of LV gives the commonly used V-shaped curve RMSEV. The lowest RMSEV gives an estimation for the number of LV to keep. Another interesting plot present in Fig.2is the Root Mean Square Error of Calibration (RMSEC). This RMSEC is calculated by comparing cal Y and cal Y ˆ,

FIGURE 2 :

 2 FIGURE 2: Red : Root Mean Square Error of Validation, Blue : Root Mean Square Error of Calibration, for 1 to 20 Latent Variables

TABLE 1 :

 1 Experiment's design (number of spectrum samples per set)In the following, the calibration set and the validation set are used only to create the classification model and to find the best number of Latent Variable (LV). The test set is used only to estimate the prediction error.

		Calibration	Validation	Test
	Wheat	200	200	320
	Weed	150	150	240
	Soil	150	150	240

TABLE 2 :

 2 Confusion matrix of validation

		Classified as wheat	Classified as weed	Classified as soil
	Wheat	177 (88.5%)	22 (11%)	1 (0.5%)
	Weed	16 (10.7%)	132 (88%)	2 (1.3%)
	Soil	1 (0.6%)	0	149 (99.3%)
	3.2. Model test
	Then, applying this model onto the test set test X and calculating the confusion matrix gives

TABLE 3 :

 3 Confusion matrix of prediction

	Classified as \ real	Classified as wheat	Classified as weed	Classified as soil
	Wheat	293 (91.6%)	26 (8.1%)	1 (0.3%)
	Weed	35 (14.6%)	205 (85.4%)	0
	Soil	0	1 (0.4%)	239 (99.6%)

CIGR-Ageng 2012. International Conference on Agricultural Engineering, 8-12 Juillet 2012, Valence, Espagne


Ph.D Séverine Arsène

The collaborative development of specific norms for individual expression

The numerous conversations and debates that take place on the Chinese Web confirm the Internet as a legitimate platform for public expression. Through their participation, Internet users collectively elaborate a specific normative framework that partly differs from the theoretical model of deliberation. Some interviews with users clarify the role they attribute to online expression.

March 2008. The world's eyes are focused on China, while Tibetan riots break out in Lhasa.

Press agencies compete with different versions of the story and Youtube is blocked again. In the context of a severe censorship, thousands of Internet users express various kinds of reactions online, most of which follow the official line, sometimes with a virulent tone, 1 making it doubtful whether it is possible to merely discuss the Tibetan question in China. 2 The Chinese Internet is very dynamic and prolific. Even though the organization of political movements through the Web is forbidden, more and more mobilizations have occurred since the Sun Zhigang case in 2003, when thousands of Internet users expressed their indignation with the arbitrary treatment of migrants. 3 These mobilizations are neither strictly political nor totally distinct from entertainment. Indeed, the Internet provides a powerful mobilization tool for politically engaged people, 4 but the most influential movements occur when massive numbers of people feel touched by one particular case or scandal, and when they express their opinions on diverse conversation tools, like forums, blogs or even instant messaging. These informal exchanges about social issues are focused upon by several international observers 5 because they do have political consequences. 6 For example, Internet exchanges play an important role in the new models of agenda setting 7 and the authorities cannot but pretend that they take into account the opinion of the people. 8 Consequently, the question of popular deliberation has become an important stake in China. It is extensively researched as a modern technique of government. 9 Indeed, deliberation is often considered as a way to obtain more popular support in the process of decision making, be it a real development of popular participation or a mere camouflage of top-down policies.

Nevertheless researchers already underline some specificities of popular participation in China, which in some regards can hardly be called deliberation anymore. [START_REF] Xiang | Is an online public sphere emerging in China? A comparative study of deliberativeness of Chinese online discussion forums[END_REF] In fact, years of development of the Internet in Western countries have proved that it offers a very diverse environment which, far from fulfilling old democratic dreams, leads to new questions on the issue of public discussion. [START_REF] Flichy | Internet, un outil de la démocratie?[END_REF] As Peter Dahlgren [START_REF] Dahlgren | L'espace public et Internet[END_REF] argues, the Internet offers a "myriad of communicative spaces" that are both distinct and interlaced. Considering such questions as digital divide, commercialization, and the fact that the users are still dependent on their socio-cultural background, these spaces are not always perfect for deliberation. Are Internet users really better informed? Do they accept to be confronted to antagonistic opinions? What kind of public opinion can emerge from online discussions? The development of the Internet forces researchers to explore old questions again with fresh eyes.

Deliberative discussion can be defined as "a situation in which 1) at least one of the interlocutors tries to produce a change in the opinion of the other, 2) by the means of impersonal propositions", and "it requires that each of the interlocutors uses the faculty that allows to detach oneself from the singular and the immediate to reach the general and the durable, that is to say reason. [START_REF] Manin | Principes du gouvernement représentatif[END_REF] According to this definition, an exchange of arguments is possible only if the participants believe that they can convince each other, and reciprocally be convinced by each other. This means that they consider that they share some interests in common, despite their respective social belongings (it is also what Boltanski calls distanciation). [START_REF] Boltanski | La souffrance à distance[END_REF] They need to accept contradiction and to be able to articulate arguments to make their point understood by other participants. This ideal-type may not exist anywhere on the global Internet, [START_REF] Manin | Happy accidents: Deliberation and online exposure to opposing views[END_REF] but it serves as a comparison reference to question popular participation on the Internet. I argue that average Internet users do not praise the theoretical model of deliberation, if defined as a rationalized exchange of contradictory arguments between peers, resulting in the elaboration of a public opinion. Instead, the collective definition of online rules and values both confirms the Internet as a legitimate platform for individual expression and contributes to elaborate a specific normative framework that partly differs from the values adopted in Europe. This is not a denial of the real revolution brought by the development of the Internet in China, but rather a call for a more careful observation of the specific logics that drive people's involvement in this complex space. I intend to approach this issue through the study of some Internet users' perceptions of online conversations on IM, e-mail, forums, and blogs, which are the spaces where most online social interactions happen. They have been asked about their usage of these services, their opinion on the rules of each kind of Internet service, and the values that they find important to respect online.

Published contents of forums do reveal some online deliberation, but it is difficult to evaluate their representativity. A large part of the Internet users' activity is in fact not visible to the public. For instance, it is impossible to reach the majority of the Internet users, who only read comments online and never publish their own points of view. Discussions start with the decision to get involved or not, so we can not settle for online contents, but we should instead focus on the users themselves and their motivations. Some interesting surveys provide information on Internet users' "value orientations". 16 For example, more than 80% of the Chinese Internet users approve of Internet control. 17 between social categories in China, especially between rural and urban China, it is important to keep in mind that my observations are limited to this specific group.

By choosing the criteria of Internet usage only, I hope that this sample incorporates most of the various attitudes of "average" users in this group, though any representativity is illusory in qualitative research. This approach sheds more light on passive users who are seldom observed in Internet inquiries. The results are inevitably different from interviews of active users, whose patterns of communication logically include more involvement into the public space. One should not be surprised to find more political indifference in this sample than in some Internet forums, and this angle will inevitably have consequences on the overall analysis of the dynamics of the Chinese Internet.

A horizontal regulation under constraints.

"Very yellow, very violent"

As I did not particularly target politics, but wanted to explore the interviewees' personal opinions about online discussions, I opted to use the word "social issues" in the questions.

Social issues potentially cover parochial questions such as neighborhood disputes as well as large economic or social problems like education policy reform. I thought that this was broad enough to let the interviewees react on topics that have some general dimensions, without bothering them with so-called "sensitive" topics.

Quite surprisingly, the interviewees identify as "social issues" such cases as murders, adultery, all kinds of scandals involving some physical or moral violence. Such a proliferation of sinister details and sexual scandals was unexpected, but a significant number of the interviewees mentioned tabloid-like cases first, when asked for examples of recent "social issues" they had paid attention to, like this young lady:

I read comments, only if it really interests me, if it particularly calls my attention, like a few

years ago in Harbin, more than twenty kids were killed and I was very touched because I found that very sinister. Then there were reports on it, the police intervened, actually this case was discussed for about a year. If they had solved the problem quicker it would have been different, but at that time there were lots of forums that talked about it, and we expressed our opinion.

-Did many people express their opinion? -Yes, a lot, because it shocked everybody (gongfen). It was a Web café manager, his girlfriend had gone and he went crazy, so he took children to his place, and cut their limbs.

Then one of them was cleverer, he managed to escape and the case was published, but by that time there were already twenty children dead at least. 19 There are countless cases like this one on the Chinese Web and the interviewees are obviously very sensitive to them. The violent nature of some parts of the Internet is largely denounced in the national media. The Internet is described as a wild place where one can easily be confronted to pornography, coarseness, verbal and visual violence. It is not a place for children, because it is "very yellow, very violent",20 as a middle-school student said last January, when she was interviewed for a CCTV broadcast.

There is room for scandals on the Chinese Internet indeed. Some are of moral nature, dealing with cases of animal cruelty, such as the famous story of a woman crushing the head of a baby cat with her high heels. 21 She became the victim of a real manhunt online and offline.

Other cases underline class struggle, like the "BMW case", in which a massive quarrel happened after peasants damaged a luxurious car. 22 Of course, the most violent reactions occur when patriotism is involved, as witnessed in some anti-Japan campaigns. 23 Any topic involving Japan on mainstream Web portals attracts violent comments and insults directed at "Japanese pigs" or worse. In the same category, the recent riots in Lhasa also witnessed "a vitriolic outpouring of anger and nationalism directed against Tibetans and the West" on the Chinese blogs. 24 The existence of a rather high level of violence online, including rude vocabulary, intolerant opinions, and pornography is not a Chinese specificity. The Internet is not easier to control than the average communication channels and it is host to a variety of extreme situations almost everywhere in the world. In the Chinese context, Internet users have specific reactions toward this phenomenon though, and their own perceptions of the possibilities and limits of the Internet can give us some clues about their vision of the do's and don'ts in Chinese society.

Collective need for regulation

As an example of the difficulty to find the right tone for discussions, let us read a few sentences from a forum, written right after a celebrity named Sun Haiying had declared that "homosexuality is a crime":

Even though Sun Haiying's speech was a little exaggerated, he is right to disapprove of the idea that one can be gay. Homosexuals are unhealthy, both psychologically and physically.

They would like to be accepted by the society, which is understandable and deserves compassion. But one can not throw torrents of insults at people who disapprove of homosexuality. […] We must tolerate, learn and understand more and we need less insults, ignorance and attacks. Opinions should not be so extreme and we need to keep respectful towards other people. 25 The juxtaposition of a very radical opinion about homosexuality on the one side and the vocabulary about compassion, understanding and tolerance on the other side is interesting.

Obviously it is difficult for that person to deal with his own feelings, and express his opinions respectfully. He acknowledges the necessity of being tolerant with each other, whatever the intensity of the feelings, and his own degree of disagreement, for the sake of keeping the Internet peaceful.

The simultaneous presence of many people within a common space requires some selfregulation from each of the participants, according to implicit rules that are progressively and collectively elaborated. In other words, the constraints of sustainability of the forums and blogs make a minimum level of tolerance compulsory. Therefore the users are forced to learn the techniques of co-existence, to measure the subtle limits within which one does not harm each other's ego. This means that they need to decide whether they agree or not with what other people express on the Web, and with the fact and manner of publishing it. They must also decide what reaction to adopt and they need to learn moderation and politeness. They can ignore other people's opinions if they dislike them, and visit other kinds of websites, but they can not prevent the others from expressing themselves. They can express their own agreement or disagreement with their own words, and find the right balance between emotions and rationalization. Otherwise they can also make their own comments about the very tone of the forum (or other platform) and give some advice to the other users about the right online behavior.

A rather unified normative lexical field emerges in the interviews. One case after the other, a whole framework of norms is established by trial and error. The central values of this framework are moderation and responsibility, which are the attributes of a certain kind of modernity or "civilization".

People insult him with very dirty words, they don't even look at the nature of this person, you see? The only impression people give me is to let go their violent anger, they cannot really manage to discuss the case. Why do I say that I don't have new friends on the Web, it's because I believe that if you have emotions to let go, it is not the right way to do it, you need to be more civilized.

-So what should you do then? -You can express your own opinion on this topic, but you should not attack the personality or the body of this person. So people who post on these forums today are of a rather bad quality'. 26 Personal attacks are one of the biggest concerns of the interviewees, together with crude vocabulary. It is notable here that H.J. criticizes the "quality" of the people who make personal attacks, which is somewhat contradictory. It is a common pattern that the interviewees classify people into good and bad, and have the very behavior that they are Criticizing, that is to say attacking people instead of criticizing their ideas.

The most obvious particularity of the Internet as a publication space is that it is shared between lots of users who do not necessarily have the same opinions and behaviors.

According to the interviewees, one should try not to have any influence on the others, for fear of hurting them or creating a conflict:

There is no precise rule, for example something, one should express it according to one's most truthful opinion (zui zhenshi de xiangfa), treat this thing with the most correct attitude (zhengque de taidu). If this thing is not accurate, it can be attacked with bad intentions. One should treat this thing with moderation (pinghe), think over questions from this kind of correct attitude (zhengque de taidu), one should not be too violent. Because when you publish it, there is an influence on other people who read it for sure, so if you speak up there you must be responsible (fuzeren), especially responsible towards society, towards the Web, you mustn't believe that there is no sense of reality on the Web, that it's fake (xujia). The Web has two faces, one is real and one is fake, so when you discuss a question online it is the same, serious things must be taken seriously (renzhen) . 27 In this quite representative quote from a young mother, truth, moderation, and responsibility are keywords, as opposed to violence and falsehood. Entering a public space like an Internet forum provides opportunities and also implies that one must act as an adult, a responsible person who needs to pay attention to the others and to the society in general. Notably, her rather vague description of "the society" and "the Web" not only refers to other people and their feelings, but also to the nature of the topic, the kind of space, and -probably -the level of surveillance in this space. The Web is not only virtual. One should be aware that the same rules apply online as offline and that speaking out online can have real consequences.

"Responsible", in this case, has a multiple meaning and refers to a vast quantity of codes that cover both expression forms and conversations contents. Indeed, the majority of Internet users agree that some things should not be mentioned online, especially political contents. They often remind it to each other, and even exclude some participants from discussions when they have inappropriate opinions or behaviors. One of the interviewees said that he had stopped publishing dissenting opinions when some other users started to insult him and said that he was a bad citizen. This means that the collective rule-setting, which is supposed to play a regulation role and set the framework for peaceful collective exchanges, is also likely to result in collectively censoring some people's opinions. Only by watching the Web discussions, Internet users can guess all or part of the informal rules that are elaborated and respected by the majority of other users.

Self regulation and censorship

Many interviewees say that they lack self-confidence when it comes to writing their opinions online. For them it is important to have enough knowledge, to master the language and to take time to organize arguments. Unfortunately the fast rhythm of postings on some popular forum threads prevents them from achieving the required quality of expression, so they just give up.

In fact, these interviewees perceive the necessity of having certain particular skills to get legitimacy and be heard on the Web, like what Gaxie calls "compétence". 28 I don't like sending too much information in too public sites like discussions on forums.

-Why? 27 G. J., 32, clerk in a car-decorating company. 28 Daniel Gaxie, Le cens caché : inégalités culturelles et ségrégation politique, Paris, Seuil, 1978.

-On the one hand because I don't have time. Because if it is public and you see an interesting

comment, it is often too late, you need some time to write your answer, to think about it, the topic has already passed, and er… It seems that generally speaking I don't have interesting comments to make. But blogs, or that kind of discussions, you can talk, you can take your time… It's more interesting. 29 Other platforms can provide better conditions for expressing views, like smaller forums or blogs, where the relationship between the main author and the visitors is more personal, and the format of the comments is less interlaced. That makes them feel more comfortable with opinion sharing, but at the same time, the mainstream platforms are progressively reserved for those who feel confident enough to express themselves. This favors the emergence of educated people and experts as important figures on the Chinese Web.

When people enter the Web, they are not totally anonymous and they need a certain status to be taken more seriously. This is why some experts, considered as more objective or impartial, gain more authority in the public forums:

And one can read comments from different kinds of people, among which experts, members of a [soccer] team, coaches, Internet users. And then for instance when I watch sports, I pay attention to important meetings, related news, there are a lot. The contents are far more numerous than those of traditional media. 30 This extract shows that one does not write comments totally anonymously. The status of the participants is important and other users pay attention to their opinions according to their level of recognition. In that interviewee's mind, one speaks as an expert or as a player, and there is no neutral status in the exchange:

Because this sort of things does not relate to us, our level of interest isn't high, and if you haven't experienced it yourself, when you express opinions on it you always bring a subjective

bias. After all if you're not an expert who has researched the topic, it's not necessary to say anything about it.

-So you think that only experts should publish their opinions? -At least it should be experts or people who have experienced it in person before, who have really endured it personally. 31 Interestingly, this interviewee does not make any difference between witnesses and experts.

Both are presented as more "objective" than average people in the sense that they have more information on a case, they understand better the protagonists' motivations and interests. In fact, the word "objective" is almost an equivalent of "close to the case" in the mouth of L.G., whereas it would suppose "taking distance" in Western theory. 32 Consequently, the very demand for objectivity is presented here as an obstacle to public participation. Here, speech can have a different value depending on the speaker's status, though his or her authority can come from different sources. One can put himself as a specialist or at least a privileged witness of some situation, as someone who has experienced something interesting from a specific point of view, be it as an actor or as a privileged observer. Every writer and reader weighs other users' ideas according to his or her own perception. The conversation is not necessarily closed because of this selection, but it can be organized, subjectively arranged by the users, instinctively and collectively, so that some participants have more weight in the discussion and their ideas are put on top of the agenda. This collaborative process is done within the limits of the spaces' written rules and under the guidance of the moderators who are responsible of the published contents in any case. There is a real demand for regulation on the users' side, so moderators play a very important role on the forums, just as they do in Western countries. 33 They can censor all kinds of excessive postings. They can give more visibility to some comments that they find relevant by putting them at the top of the page. They can also remind the users of the explicit and implicit rules of the space.

The moderators have the power to delete messages and they often do so. This role is often described as crude censorship by Western Internet observers who tend to forget that this function is also crucial on the Western Web platforms. Indeed, the Chinese moderators' role is quite ambiguous, as they also do a necessary work to guarantee that the space stays peaceful and allows good exchanges:

About that, I have set up my own forum before, I mean my personal forum, so I have some understandings of the backstage processes, because I need to protect myself from being attacked. There are some malicious comments, and there are some people who maliciously leave messages on your forum, and then they denounce you, this situation happens very often.

So if you want to avoid this situation, you have to talk to the managers of some other big

forums like that, discuss with them. Of course we have some discussion topics that are quite 32 Luc Boltanski, La souffrance à distance, Paris, Métailié, 1993. 33 Stéphanie Wojcik, "The Three key roles of moderator in municipal online forums", paper presented at Politics: Web 2.0: An international conference, Royal Holloway, University of London, April 17-18, 2008.

specialized, like how to avoid this situation, how to find methods of control when I want to control something. 34

Sometimes, moderators also end up deleting opinions that are not in line with the national positions. Understandably, they do so to protect themselves and the sustainability of their forum, even more than to annoy the author of the comment. There is no better example than Japan on this point:

Every website that has a comment page has a manager, the manager's task is to clear up the garbage, the rubbish comments. So for them being a little against Japan, criticizing Japan, […] basically, what they want to express is to propagate this aspect, to propagate the fact that Japan is bad. If you say something else on the website they will delete it, it is useless. 35 This obvious censorship must not lead us to condemn Internet regulation as a whole. It is demanded and justified by the users themselves because it also protects them from some virtual conflicts, and it promotes a politically and socially secure atmosphere for them to participate. Thanks to the filtering process, they feel that whatever they write, it will be published only if it is checked and positively appreciated by the moderator.

Paradoxically, limited as it is, the framework of the Internet still offers an important platform for expression. This is already a huge step in the Chinese context where expression has long been a monopoly of the Chinese Communist Party (CCP). Publication, which has long been the privilege of propaganda, is being vested by individuals. The resulting profusion of contents, among which some are poorly "civilized", creates new kinds of anxieties for Internet users, therefore they are contributing to the elaboration of a framework of formal and informal rules. The users are learning how to behave in this sphere, how to co-exist with each other without shocking each other or feel shocked by the others. In that sense, the Internet in China offers some space for a constantly evolving user-based construction of a set of rules that is negotiated, obeyed and checked by the users themselves.

They take into account the constraints of the regime, and the collaborative dimension of rulesetting is very ambiguous. It both enables Internet users to validate a framework of discursive values that they find appropriate, and contributes to maintain a kind of collective surveillance or even censorship. Individuals prove to be subjects of the norms as well as their objects. 36 Therefore these norms should be observed at the grassroots level of individuals themselves, in their practices and representations. The way they legitimate norms enlightens some aspects of 34 C.L., designer, 26. 35 F.RT, student, 21. 36 Michel Foucault. Histoire de la sexualité. 1 La volonté de savoir, Paris, Gallimard, 1976. the social order, and therefore clarifies the conditions and particularities of popular participation online.

Internet users are promoting such values as politeness, objectivity, moderation, that seem to echo the Western discursive tradition. This should not lead one to conclude to the advent of deliberation, but only that of some aspects of it. These aspects have a specific significance in the Chinese context and deserve to be explored more precisely.

Personal expression vs. collective deliberation.

Despite the strict control on critical expression, the tone of the comments often crosses the most basic lines of politeness, 37 which leads me to wonder once again: "is discussion possible?" 38 and more precisely: what discussion is possible?

The values enhanced in online discussions in China enlighten Internet users' position towards the function of public expression. The very fact that one can discuss the rules, and assess the existence of some censorship proves that the Internet is already taken for granted as a popular expression platform. All the normative vocabulary used by the Internet users to qualify the legitimate online behavior can be analyzed as the manifestation of the role they attribute to this platform of expression.

Assertion of individual expression

The excesses allowed by anonymity are not always disapproved of. According to several interviewees, almost everyone needs some space to relax from a stressful daily life, and very few spaces allow the people to express their feelings, so Internet violence is just natural and even necessary. Most of the interviewees believe that the Internet is the right place for bursting out with anger, frustration, excitement, and all kinds of extreme emotions that can not be expressed openly elsewhere. An above quoted young lady expresses that indignation (gongfen) 39 is her main motive for participation on the Chinese Web. Another interviewee has the same feeling: 37 See this video that aims at proving the inalienable Chinese identity of Tibet. The comments, in English, are addressed to Westerners and half of the sentences contain the word "f***": "Tibet WAS, IS, and ALWAYS WILL BE a part of China", http://www.youtube.com/watch?v=x9QNKB34cJo&feature=related (consulted 06/06/2008). 38 Rebecca Mckinnon, "Tibet… Is discussion possible?", op.cit. 39 X.YH, piano teacher, 27.

Most people want to relieve themselves from what dissatisfies them in the society, or what dissatisfies them in other things. Most of them just want to let off steam (faxie). 40

All in all, it seems that the Internet has immediately been adopted by its users as a good space for popular expression and they find that it is worth coping with the drawbacks so that the population can use this opportunity for expression. Here is one typical example of the conclusion which almost all the interviewees draw about the role of the Internet.

What can the Internet bring to China? It can accelerate society's progress and technological development. But I think that it is also a platform for everyone to exchange, it is a place to express their own points of view. In fact I think it's quite good. [START_REF] Yh | [END_REF] Some avatars of Internet violence can reveal a form of mobilization. For example, a specific category of young Internet users is called "angry young" (feng qing) because of their excessive positions online. 42 Some describe them as disrespectful and violent, whereas others say that these young are just desperately trying to express their critical vision of the current society, that is becoming too competitive and amoral. Many scandals that cause widespread impulsive reactions undoubtedly reveal great popular concern for such questions as safety, [START_REF] Thireau | De l'épreuve publique à la reconnaissance d'un public: le scandale Sun Zhigang[END_REF] equity, value of human life, class struggle, or national pride, and they can be analysed as the affirmation of these new social norms, [START_REF] Boltanski | Affaires, scandales, grandes causes[END_REF] but I do not want to develop this aspect here. Instead, I want to concentrate on the very modalities of the debates, and on Internet users' perception of the online exchanges of opinions and the rules that organize them.

The anger of these youth challenges the tolerance of other Internet users and it reveals the limits of online expression in their mind. Freedom of speech is acknowledged under conditions.

Debate and polemic

First of all, according to most of the interviewees, freedom of speech supposes that one should not contradict each other's opinion: So I think that other people have their opinion, and I have mine, and it is not worth struggling about it, when you have seen it, it's over. It is useless to start analyzing if things should be like this or like that, everyone is free, right? So we can watch a little, but when it's over, I'm not the kind of guy that makes comments or judges the quality. 45 H.J. does not like to contradict other Internet users because he feels that it would result in refusing their own freedom. Moreover he feels that contradicting someone on the Internet equals to judging the quality of the person and his or her speech. As a result, the very respect of other people, of free online expression and the principle of tolerance lead this person to refuse contradictory debates and to choose the "exit" option.

Having opposed points of view, highlighting the opposition and exchanging arguments is often perceived as attacking other Internet users. It is seen as something uselessly aggressive, when one should just ignore the opinions of the others and leave them alone.

Of course, one can not underestimate the role of censorship in the defiance towards debate.

Having a different opinion is taking a risk at some point. The interviewees express the necessity to be careful, and speak in the terms allowed by the authorities, that is to say in accordance with the tone of official media like the People's Daily. It is necessary to "play the melody of harmony".

For sure, you must not speak about the leaders of the country, you can not say anything about national leaders, and in your dissertation you shouldn't mention things about the country's leaders. I think that in China it's impossible, every point that you want to criticize, when you are in China you can not say it. It is not like abroad, if you want to go against the tide, it is not possible. It's like you, you're writing a dissertation, you must follow the tone, write articles in accordance with the theme, you must not leave the theme. China is trying to reach the harmonious society, you must be careful to know if this is the harmony of the Internet, the harmony of China, you must write with the colors of harmony, this is Chinese culture, you can not change it, everybody is like that. 46 "Chinese culture" serves as a justification for what is first something forbidden by the communist system and censored by the authorities. It is far easier for Internet users to publish conformist opinions than to test original ideas, otherwise they would take the risk to "sing another tune". The musical metaphor is obviously an attempt to make the limits of expression look natural. They are part of Chinese culture and they are not questionable in the eyes of the interviewee. This effort to legitimize the situation reflects the personal appropriation of the national rules by this user.

It also reflects his position towards the foreign interviewer, in front of whom it is important not to criticize the country. Once again, this supports the idea that unanimity definitely looks better than discord, especially on a space that serves as China's showcase in front of the rest of the world. Internet is not considered here as a place for public discussion, but as a tool for displaying the most modern image of the country. 47 In that context, being exposed to diverse opinions most often lead the interviewees to avoid getting involved into a debate. Arguing with people who belong to other groups and who do not have the same point of view is most often perceived as a bad behavior. The interviewees were often asked what their reaction would be if they came across an opinion on the Web, with which they did not agree at all. Their answers almost invariably contained pejorative vocabulary like "polemic", "argue", "quarrel", that were not inferred by the tone of the question.

By contrast, the meaning of tolerance becomes slightly different from what it would be in another context. It is more than an attitude of respect towards other people's opinions. It implies not to contradict their opinions and to stay indifferent to them. It is thus associated to a list of other values, some of which are picked in the Chinese philosophy.

"Zhongyong" [happy medium] means something like letting go, not doing polemic, it sounds a little like that, it sounds a little like Buddhist or Christian thinking, it means that I am not going to quarrel with you about issues, like power or money, even if I must have desires, but my behavior or my character will not be like that. 48 For P.Y., the Chinese way of proceeding in discussions is the most subtle, and it is more efficient to manage relationships. Let us read further his interview.

One must have an amenable behavior (suihe), like this it facilitates relationships, it is easier to cooperate (gongshi), in fact I think that it is easier to succeed in all domains. In China we often come upon that sort of situations, for example you don't agree with someone, with your boss, or you don't agree with your client, if you quarrel violently, even if you're right, maybe he won't agree. It is different abroad, if you have an opinion you can say it directly, you can tell everybody we need to do like this, and then they do like this, but not in China. We speak in a more subtle way (weiwan), we express our point of view in a more subtle way, if it's my colleague, or if it's my friend, I must use this sentence, we think more about how to say things to settle issues. You can not expect from the Chinese to settle issues the same way as Westerners do, it would confuse things. If I start to argue violently on some questions with people, I don't believe that after that we could still solve issues together and in peace. So I think that it is understandable that when I read on the Internet that the Chinese should take inspiration from Western thinking, I don't agree. We need to learn some things, but on other things we need to respect ourselves, the context is different. 49 It seems that it is impossible to solve a disagreement in the eyes of P.Y. Discussion neither has the power to settle questions, nor to overcome them, it can only underline discord and make it even more insuperable. The reference to a commercial situation implies that the reference to tradition is mainly used for strategic purposes. Indeed, the strategic context is the ultimate reference to decide what elements can be kept or not within the various elements of the Chinese traditions.

Chinese Internet users mobilize various justifications for feeling uncomfortable with debate.

Whatever the justifications, the function of online expression is obviously not to exchange arguments and convince each other. It is a space available to put one's testimony, record one's diary, drop off some emotions, separately from the other users.

In this context, what dialogue is possible between the different Internet users?

Diversity, pluralism, and public opinion

In an article about a French radio broadcast, in which telephone operators had to select listeners for speaking on-air, Dominique Cardon 50 studies into details the sometimes arbitrary criteria that determine the legitimate participation in that kind of public space. Apart from the basic requirements of politeness and level of language, the persons in charge of the selection privileged listeners who were able to highlight a certain level of general interest through their personal testimony. They needed to find the general dimension that can have an interest for the whole society, in their particular situation. Under that condition, they could be selected to participate in the radio broadcast.

In this sample this detachment pattern is almost never referred to, and even sometimes criticized. One belongs to a group and he is representative of that group, be it regional, professional, national, by income or else. Paradoxically social belongings are taken for granted by the interviewees, and they do not consider the idea that each individual's various 49 P.Y., manager in a medicine company, 25. 50 Dominique Cardon, "Comment se faire entendre? La prise de parole publique des auditeurs de RTL", Politix, vol.8 n°31, 1995, p 145-186. belongings (sexual, educational, professional and so on) could be contradictory. When they describe their social belongings, the interviewees portrait a highly stereotyped and segmented society.

For example, M.N. tells us that the population's mentality depends on the geographic origins of the people. One of the pleasures derived from the Internet is to compare the habits of the North and the South, which incites people from each region to play the assigned roles:

There can be topics like this, there are Beijingers and Shanghainese, Beijingers can represent typical Northern people, and Shanghai represents a typical city of the South, and people from these two cities compare their characters. 51 This interviewee was quite enthusiastic about this experience. For him it represented the pleasure of sharing a common space and enjoying co-presence on a same virtual platform. Indeed, such a comparison encourages tolerance and diversity, but in this kind of conversations, you can only speak for yourself and never be representative of the others.

There is no common point between people from different social categories, therefore they can not speak for one another, let alone criticize one another's opinion. Apparently, different people's interests are necessarily antagonistic: I think perhaps some people can represent an association, that is to say he can represent a fixed crowd, for instance a profession, perhaps some people can represent the workers, some people can represent the farmers, some people can represent the white collar workers, but the person who speaks on behalf of the white collar workers benefits definitely cannot represent the lowest level social citizens, this is certain, then let's say the lowest level of the society definitely cannot represent such a high level social stratum as white collar workers, they definitely cannot represent each other. 52 Given that everyone has different points of view on each problem, and that everybody has his own life style, different educational levels, we don't understand things the same way, so it is difficult to say that we are going to make comments, maybe sometimes you find something is wrong, it is not correct, and someone else finds it's right, everything is possible, I think that everything has two faces, there can not be only one opinion on something. 53 In this vision every citizen's opinion can only be considered as corporatist, selfish, and partial.

Every category is seen as having contradictory points of view, and the multiple faces of the 51 M.N., chef, 26. 52 C.H., designer, 26. 53 X.YH., piano teacher, 27 .

individuals that result from their personal backgrounds are neglected. It seems difficult to imagine that these people could find a common position together.

The tolerance that is valued in this model is that of diversity, not that of pluralism. In the ideal type of pluralism, several points of view can emerge in one single group, and be shared in order to be discussed. There is a natural paradox in the concept of pluralism. There must be a basic agreement between everyone on the very fact that disagreement is possible and even fruitful. 54 On the contrary, in the model of a segmented and stereotyped society, the diversity of opinions can only be the result of diverse social situations. Consequently, they are not arguable and relativism is the only possibility to deal with divergent opinions.

Given this description of the society, a "public opinion" that would be the result of exchanges of views between the different social categories, seems unlikely to emerge. The word "public opinion" is used by the interviewees though, with a quite unexpected definition, and it reflects their perception of a segmented society:

In Harbin, it was also in the North-East, there was a nurse in Harbin who crushed the head of a kitty with her high heels, we call that the "cat case". When it broke out, when the photo was published, it was already on TV, people found where she worked, they called the hospital, her home, they prevented her from living normally, that's how it happened. After that the hospital fired her, they had to, otherwise it was impossible to work normally, this is the pressure of public opinion. 55 Here, public opinion is not the result of a diversity of opinions, or that of a debate. Instead, the Internet users are unanimous and they collectively condemn the actions of the woman. There is no collective exchange of opinions nor any organized reaction, but only a massive, arbitrary and excessive personal harassment that resulted in the punishment of one particular person and her entourage. The general dimension of public opinion is replaced by a singular example which has almost no impact for the rest of the society. Public opinion represents here a large number of people who have the same opinion, and who have always had that opinion, even without exchanging with one another whatsoever. In other terms, this kind of massive mobilization results in the enforcement of shared moral norms, rather than the elaboration of a public opinion, conceived as the result of public discussion, and opposed to a simple aggregation of multiple individual opinions. This does definitely not fit the ideal-type of deliberation, but some ideas are still exchanged, and they can spread very quickly without necessarily being discussed online. 54 Jean Leca, "La démocratie à l'épreuve des pluralismes", RFSP, Vol. 46, n° 2, 1996, p 225-279. 55 L.JJ., tourism, 23. 20 Expression on the Chinese Internet is not separated from social and political constraints. It is inextricably embedded in Chinese society. Nevertheless the rules are debated, commented on, reappropriated by the users, within the limits of what is permitted by the authorities. This very appropriation process reveals that Internet users are coming to grips with public expression platforms. The values defended by the Chinese Internet users, like diversity, tolerance and free opinion, have specific meanings in their minds and they must be understood in the light of the local context. Now, popular expression is legitimate within some limits that constantly evolve, even though it is most often devoted to testimonies and anonymous psychological release. For lots of Internet users, online expression is more an individual opportunity to release emotions than a collective tool to debate divergent opinions.

  These figures are useful to get a large picture of the Internet population, but they put together very diverse situations. It is doubtful whether the declarations of urban and rural users, youngsters and adults, can be aggregated together, so we need further qualitative exploration, to better understand the meaning of such declarations in smaller groups of users. During a fieldwork in Beijing in 2006-2007 for a PhD research project, fifty persons between 18 and 40, both men and women, were interviewed; they use the Internet for personal purposes at least one hour per day. Their profiles are randomly diversified in terms of profession, income, living area in Beijing. As my research initially focuses on Internet usage in the post-reform generation, I have chosen to interview mainly young adults between 20 and 30. That generation happens to be the main group of Internet users in the Chinese statistics, as the emergence of the Internet phenomenon still concerns in majority the very specific category of urban, young, educated Chinese people.

  18 Considering the huge differences

	16	Chinese	Internet	Research	Conference,	"Session	3:	Roland	Soong",

http://jmsc.hku.hk/blogs/circ/2008/06/13/session-3-roland-soong. 17 Guo Liang (dir.), The CASS China Internet Project Survey Report 2007, http://www.markle.org/. 18 CNNIC, Statistical survey report on the Internet development in China, 2007, www.cnnic.net.cn.

XYH, piano teacher, 27.

Joel Martinsen, "The yellow, violent mob culture of a Chinese BBS", www.danwei.org, 16/01/2008. The yellow colour metaphorically represents pornography in China.

Joel Martinsen, "Animal cruelty in the mainland press", www.danwei.org, 02/03/2006.

Raymond Zhou, "BMW drives wedge between rich, poor", China Daily, 18/01/2004, http://www.chinadaily.com.cn/en/doc/2004-01/18/content_300105.htm .

WangJing, "Tangchao yamen beijing shi "taiyangqi"" (Chinese). http://epaper.bjd.com.cn/wb/20060707/200607/t20060707_45533.htm .

Sophie Taylor, "Chinese seethe on Web over rare riots in Tibet", Reuters, 15/03/2008, via http://www.washingtonpost.com/wp-dyn/content/article/2008/03/15/AR2008031500633.html.

translated from byron730319, http://bbs.news.tom.com/i_741_83477.html (in Chinese), 15/08/2007, via http://blogenchine.com/2007/08/ (in French).

H.J, salesman, 28.

Z.L., marketing, 25.

Z.L., marketing, 25.

L.G., store manager, 24.

H.J., salesman, 28.

M.N., chef, 26.

The Internet plays dozens of interlaced, paradoxical and complementary functions. We do not mean that the Internet is only a showcase, but that when asked about the specific question of disagreement, the interviewees tend to privilege this aspect.

P.Y., manager in a medicine company, 25.


Manar Qamhieh
email: manar.qamhieh@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Laurent George
email: lgeorge@ece.fr

Dynamic Scheduling Algorithm for Parallel Real-time Graph Tasks

In this paper, we propose a dynamic global scheduling algorithm for a previously-presented specific model of real-time tasks called "Parallel Graphs" [1], based on the Least Laxity First priority assignment policy "LLF", we apply LLF policy on each subtask in the graphs individually, taking in consideration their precedence constraints. This model of tasks is a combination of graphs and parallelism, in which each subtask in the graph can execute sequentially or parallel according to its number of processors defined by the model. So we study parallelism possibilities in order to find the best structure of the tasks according to the practical specifications of the system.

I. INTRODUCTION

Physical constraints such as chip size and continuous heating forced processors' manufacturers to produce multi-processor systems, and as they are constantly growing, software parallelism has been widely studied and applied in practice.

However, parallelism in real-time embedded systems is still a rising challenge with many open questions to be studied. There are parallel task models exist in practice, such as the fork-join model used in OpenMP [START_REF]Openmp[END_REF] and has been studied in [START_REF] Lakshmanan | Scheduling Parallel Real-Time Tasks on Multi-core Processors[END_REF], and a more general model of parallel tasks has been proposed recently in [START_REF] Saifullah | Multi-core Real-time Scheduling for Generalized Parallel Task Models[END_REF] which overcomes the restrictions of the fork-join model. Those models consider the tasks as a sequence of parallel and sequential tasks.

The graph model of real-time tasks is a general representation of the models described previously. In our previous work [START_REF] Qamhieh | A Parallelizing Algorithm for Real-Time Tasks of Directed Acyclic Graphs Model[END_REF], we proposed a new model of real-time tasks called "Parallel Graphs", which is a combination of graphs and parallel tasks. By this we added an inner parallelism level to the graph as will be described in II. In this paper, we will extend our previous work by proposing parallelizing options a dynamic scheduling algorithm for the parallel graphs.

In this paper, firstly we will describe our task model in section II. In section III we will discuss the various parallelizing possibilities for parallel graphs. Section IV will present our dynamic scheduling algorithm. Finally in section V, we will finish the paper by concluding and giving perspectives.

II. TASK MODEL

In [START_REF] Qamhieh | A Parallelizing Algorithm for Real-Time Tasks of Directed Acyclic Graphs Model[END_REF] we presented previously a new model of real-time tasks called "parallel graphs". In this model, Each parallel real-time task is represented by a directed acyclic graph (DAG), which is a collection of subtasks and directed edges representing the execution flow of the subtasks and the precedence constraints between them. Each parallel graph task τ i consists of a set of q i subtasks and it is denoted as:

τ i = ({τ i,1 , τ i,2 , ..., τ i,qi }, D i , P i )
, where D i is the deadline of the graph and P i is its period. Each subtask τ i,k is represented as the following:

τ i,k = {c i,k , m i,k },
where c i,k is the total worst execution time of the subtask, and m i,k is the maximum degree of parallelism of τ i,k , which means that τ i,k can be scheduled on m i,k parallel processors at the most. Figure 1 shows an example of parallel graph task.

Precedence constraint means that each subtask can start its execution when all of its predecessors have finished theirs. If there is an edge from subtask τ i,u to τ i,v , then we can say that τ i,u is a predecessor of τ i,v , and τ i,v has to wait for τ i,u to finish its execution before it can start its own. Each subtask in the graph may have multiple predecessors, and multiple successors as well, but each graph should have a single source and a single sink vertex. In this work, we study the global scheduling of n synchronous periodic parallel real-time graphs with implicit deadlines on m identical processor system. A task set is denoted as Γ = {τ 1 , τ 2 , ..., τ n }, where each graph has period equals to its deadline. The schedulability is studied on the hyper period of each taskset.

A. Notation

Definition 1: Critical path [START_REF] Qamhieh | A Parallelizing Algorithm for Real-Time Tasks of Directed Acyclic Graphs Model[END_REF] of a graph τ i is the longest path in the graph through its subtasks when respecting their dependencies.

CP i = j∈critical subtasks c i,j
The critical path of the graph τ 1 from Figure 1 is

(τ 1,1 , τ 1,2 , τ 1,6 ) and CP 1 = 8.
Definition 2: The worst case execution time of a graph C i is the total execution time of all the subtasks in the graph τ i when executed sequentially.

C i = qi j=1 c i,j
Definition 3: Laxity of a parallel graph L i is the difference between its deadline and its critical path execution time.

L i = D i -CP i III. DIFFERENT PARALLELIZING ALGORITHMS In our previous paper [START_REF] Qamhieh | A Parallelizing Algorithm for Real-Time Tasks of Directed Acyclic Graphs Model[END_REF], we described a parallelizing algorithm which finds the best structure of the parallel graph according to the response time of the graph, by maximizing the number of parallelized subtasks in the graph. This algorithm does not consider the number of processors in the system, so there might be better structures of the parallel graphs when considering the actual specifications of the system like the number of processors, the scheduling policy, etc.

In this section we will discuss 2 possible parallelizing algorithms, a maximizing and minimizing algorithms according to the level of parallelism.

A. Maximizing parallelism

The parallelizing algorithm proposed in [START_REF] Qamhieh | A Parallelizing Algorithm for Real-Time Tasks of Directed Acyclic Graphs Model[END_REF] is an iterative algorithm whose aim is to parallelize the maximum number of necessary subtasks in the graph up to their maximum level of parallelism, on the basis of the following algorithm:

• Find the critical path of the graph using the depth-first search algorithm. • Parallelize all the subtasks in the critical path up to their maximum level of parallelism. • Repeat the 2 previous steps until there is a critical path with no parallelizable critical subtasks.

B. Minimizing parallelism

Another approach can be considered for this type of graph which is the reverse of the one in III-A. We can find the best structure of the graph according to the number of processors in the system, by trying to stretch the graph as long as possible in order to execute on a minimum number of processors without missing their deadline, and by filling the laxity of the graph with a maximum number of subtasks.

According to the following equation, a parallel graph τ i can execute sequentially on 1 processor if:

D i C i ≥ 1 (1)
Where D i is the deadline of the graph task, and C i is defined in II-A.

If this test fails, then we have to reduce the sequential execution time of the graph by parallelizing some of its subtasks using the following algorithm:

• Apply equation 1 on the parallel graph τ i .

• If the test succeeds, then τ i can execute on a minimum number of processors without missing its deadline.

• If the test fails, we calculate the critical path of τ i , parallelize the critical subtasks in order to reduce its sequential worst case execution time C i . • Repeat the first step on the newly parallelized graph τ i until the test succeeds.

C. Other possibilities

Choosing the best structure of the parallel graph is not an easy process. It is controlled by a lot of restrictions and limitations of the system, for example, using the maximizing parallelism algorithm will reduce the response time of the graph if executed on a system with a large number of processors, and theoretically, it will increase the number of preemptions and job migrations while scheduling (depends on the used priority assignment algorithms).

The minimizing algorithm will increase the response time of the graph while reducing the number of processors needed, which will decrease the energy consumption as a result.

There is a large number of parallelizing structures for the parallel graph task, which affects the schedulability of the tasks, the migration and preemption costs. In the future we aim to study those various possibilities and their effects by comparing them using a real-time simulation tool, and taking into account the different characteristics of embedded systems, such as the number of processors, energy consumption, etc.

IV. SCHEDULING PARALLEL GRAPHS

In this section, we propose a global preemptive scheduling algorithm on an implicit-deadline parallel graph task set Γ i of n graphs, on the hyper period of the taskset:

hyper(Γ i ) = LCM (τ j ), ∀j : 1 ≤ j ≤ q i 1
Since the active subtasks of each graph share the same period and deadline, we decided to use a dynamic priority assignment policy based on the least laxity first technique (LLF), which gives higher priority to tasks with lower laxity (slack time). Scheduling algorithms based on this priority assignment are optimal on mono-processor systems but not on multiprocessor systems, unless laxity priorities are verified all the time during the scheduling process to make sure delayed tasks gain higher priorities in time.

A. Scheduling algorithm

After applying a parallelizing algorithm on each graph τ i in Γ i , the generated graph task contains both sequential and parallel subtasks. A sequential subtask needs one processor to execute on, while parallel subtasks execute on multiple processors at the same time. Here we should say that we are interested in input-data parallelism, in which the same code is repeated on multiple processors while only the input data are changed.

As described in Section II, each graph task τ i consists of q i real-time subtask each has a WCET of c i,j , and due to the precedence constraint on the subtasks of the same graph, a subtask τ i,j cannot be activated unless all of its predecessor subtasks finish their execution. Because of that not all of the subtasks in the graph are activated at the same time or at the very instant of activating the graph.

There are 2 types of laxity in τ i , a general laxity of the graph as whole, denoted as L i and described in II-A, and a subtask laxity for each subtask τ i,j ∈ τ i .

As explained in our previous work in [START_REF] Qamhieh | A Parallelizing Algorithm for Real-Time Tasks of Directed Acyclic Graphs Model[END_REF], when a parallelizing algorithm is applied on a graph task τ i , we can also calculate the laxity of each subtask in τ i , by calculating the earliest and the latest finishing time of the execution time of each of them, the difference between those 2 time values is the laxity of the subtask. A subtask with laxity equaling to 0 is a critical subtask in the graph.

In order to organize the scheduling process of the graph set, we will consider 3 types of subtasks: active jobs, executing jobs and completed jobs. The active list contains the jobs that are activated either by the activation of the original graph (jobs of the starting subtask in the graph), or when the predecessors of a subtask complete their execution. When a job starts its execution, it will be moved to the executing list until its execution is over when it will be moved to the completed list. If an executing job is interrupted by a higher priority job, it will be moved back to the active list.

For each instant in time t where

0 ≤ t ≤ hyper(Γ i ),
we calculate the dynamic priority P r i,j (t) for each active job of subtask τ i,j of each graph task in Γ i , where:

P r i,j (t) = L i + L i,j -(t -A i,j ) (2)
where A i,j is the activation time of τ i,j , subtasks with lower P r(t) values have higher priorities.

The scheduling algorithm:

• At t = 0:
Each graph task τ i ∈ Γ is activated (since we consider synchronous activation), which means all the starting subtasks τ i,1 are activated as well and added to the active list. Then we calculate P r(0) for all of the subtasks in the active list using Equation 2.

According to the number of processors in the system, we start executing the subtasks with the highest priority which are moved to the executing list at the same time. If an executing subtask τ i,j is a parallel subtask according to the parallelizing algorithm, then it will need m i,j available processors in order to enable all of its parallel parts to execute concurrently. • ∀t where 0 < t ≤ hyper(Γ i ):

If an executing job finishes its execution at this instant of time, it will be moved to the completed list. And if all the predecessors of a subtask are in the completed list, then its job will be activated at this instant of time and added to the active list.

Since we use dynamic priority assignment, at each instant of time we re-calculate P r i,j (t) for all subtasks τ i,j in the active list. By this, the priority of delayed active subtasks will be increased in time since their laxity decreased.

According to the newly assigned priorities of the active subtasks, we fill the processors available in the system, and if there are active subtasks with higher priority than the ones already executing, they are allowed to interrupt their execution. • The scheduling algorithm of the graph set Γ will fail if -at any instance of time ta job in the active list reaches a P r(t) = 0 without having an available processor to execute on, since at t + 1 this job will have a negative laxity and miss its deadline. In the case of equal priorities between 2 active jobs, we choose the executing one randomly, but if an active job and an executing job have the same priority, we give the priority to the executing job to continue its execution without allowing the active one to interrupt the execution of the other. In that way we reduce the number of unnecessary cost of preemptions and migration.

Using this dynamic global scheduling algorithm, we scheduled each subtask in the graphs individually, by assigning priorities as shown in the previous algorithm. Precedence constraints between the subtasks due to the structure of the graph were visible only in the activation process. However, this scheduling algorithm was different from the previous scheduling techniques applied on the real-time tasks of the graph model seen in the literature. For example in [START_REF] Saifullah | Multi-core Real-time Scheduling for Generalized Parallel Task Models[END_REF], the authors propose to use a decomposition algorithm in order to assign local deadlines to the subtasks in the task, and to schedule each segment of tasks as independent tasks on multi-processor systems.

B. Scheduling example

In this section, we will apply the above-mentioned scheduling algorithm described in IV-A on a graph task set consisting of 2 graphs on a 2-processor system.

graph task set

Γ = {τ 1 , τ 2 } τ 1 = ({τ 1,1 (1, 1), τ 1,2 (3, 1), τ 1,3 (2, 2), τ 1,4 (1, 1)}, 10, 10) τ 1 = ({τ 2,1 (1, 1), τ 2,2 (1, 1), τ 2,3 (1, 1), τ 2,4 (1, 1)}, 5, 5)
The graphs in the task set have implicit deadlines, and all subtasks of the same graph share the same period and deadline. The scheduling algorithm is studied on the hyper period of the task set:

hyper(Γ) = LCM (10, 5) = 10
Figure 2 shows the graphs of the task set with the precedence constraints.

Graph τ 1 has a parallel subtask τ 1,3 which needs 2 processors available at the same time in order fo it to execute, or its execution will be delayed otherwise. All the other subtasks in this example are sequential.

By applying the critical path calculations described previously in [START_REF] Qamhieh | A Parallelizing Algorithm for Real-Time Tasks of Directed Acyclic Graphs Model[END_REF], we find that the laxity of the graph τ 1 equals to 5, and 2 for τ 2 , and all the subtasks of both graphs don't have local laxities (they are critical subtasks), except for subtask τ 1,3 which has a laxity L 1,3 = 1. At t = 0, the first subtasks of the each graph are activated (τ 1,1 & τ 2,1 ), according to the mentioned-above equation 2, we can calculate the priority of the subtasks as the following:

P r 1,1 = 5 + 0 -(0 -0) = 5 P r 2,1 = 2 + 0 -(0 -0) = 2
According to the results, τ 2,1 has higher priority than τ 1,1 , but since we have 2 processors available, both subtasks will be scheduled. Those calculations will be repeated at each instant of time in the hyper period of the task set, unless a deadline miss occurs before the end of the period. Table IV-B shows the priorities of the active subtasks of both graphs over the hyper period of the task set, while Figure 3 shows the final scheduling of the subtasks on the 2 processors of the system. We can notice that our proposed global preemptive scheduling algorithm based on LLF has succeeded in scheduling the taskset without any subtask misses its deadline.

V. PERSPECTIVE AND CONCLUSION

In this paper, we have introduced a dynamic global scheduling algorithm on multi-processor systems, for a specific real-time task set of parallel graph models, based on the Least Laxity First "LLF" job priority assignment in order to schedule each subtask in the graphs according to their laxity while considering the global deadline and period of the original graph with no need to assign a local deadline for them, we have also shown by an example the schedulability of this algorithm on a task set of the graph model.

! 1,1 (1,1) 1,2 (6,2) 1,3 (2,2) 1,4 (3,3) 1,5 (2,1) 1,6 (1,1) D1 =T1 1,1 (1,1) 1,2 (3,1) 1,3 (2,2) 1,4 (1,1) D1 = T1 =10 C1 = 9 CP1 = 5 2,1 (1,1) 2,2 (1,1) 2,4 (1,1) 2,3 (1,1) D2 = T2 =5 C2 = 4 CP2 = 3 1,1 1,2 1,3 1,3 1,4 2,1 2,2 2,3 2,4 1
The graph model of tasks has been studied recently in the literature, but adding the parallelism constraint to this model has raised a schedulability challenge and made it more complicated. That is why we presented 2 parallelizing algorithms in this paper, both algorithms depending on the constraints of the embedded systems which we aim to study in more details in the future.

In order to provide valid results to show the performance of our proposed scheduling algorithm, we started implementing it on a simulation tool called "YARTISS" [START_REF] Chandarli | YARTISS: A Tool to Visualize, Test, Compare and Evaluate Real-time Scheduling Algorithms[END_REF], developed by a real-time team in the research laboratory of Universit Paris-Est. By using this simulator we will be able to compare the performance of our own scheduling algorithm with other techniques and algorithms used in the literature, which will allow us to enhance its performance with respect to the practical issues of real embedded systems such as a limited number of processors, optimizing the schedulability in order to reduce the energy consumption by reducing the number of migrations and preemptions.

In parallel, we would like to study real-time scheduling anomalies and provide real-time feasibility tests for the proposed algorithm, in order to support the simulation results.

Finally, we hope to apply our model of tasks on real embedded systems, and propose adjustable techniques in order to enhance their performance such as schedulability and energy consumption.

Figure 1 .

 1 Figure 1. Example of the parallel graph model.

Figure 2 .

 2 Figure 2. Graph taskset example.

2 Figure 3 .

 23 Figure 3. Graph taskset scheduled using LLF.

LCM is the Least Common Multiple