Juri Luca

De Coi

Laurent Vercouter
email: laurent.vercouter@emse.fr

Reputation Put to the Test: a Testcase for a Cognitive Reputation Model

Keywords: Trust, Reputation, Agent technology

. However, Herzig et al. focus on describing a conceptual framework but do not provide any concrete instantiation of it, thereby not showing any evidence about the effectiveness of their approach. This paper fills the gap by presenting such an instantiation based on agent technologies. Although our instantiation targets a Wikipediarelated scenario and exploits the Jason [1] and CArtAgO [13],

[14] frameworks, the methodology we present is general and can be applied to different scenarios and agent technologies.

I. INTRODUCTION

The wide diffusion of open and decentralized environments like the Web makes it possible for actors to interact with previously unknown peers. As a consequence, trust has become a hot topic in the field of computer science. Many attempts to formalize concepts like trust and reputation have been carried out in the literature [START_REF] Castelfranchi | A non reductionist approach to trust[END_REF], [START_REF] Marsh | Computing with social trust, chapter Examining trust, forgiveness and regret as computational concepts[END_REF], [START_REF] Andrew | On the concept of trust[END_REF]. For the context of digital societies, the lately presented approach by Herzig et al. [START_REF] Herzig | A logic of trust and reputation[END_REF] appears to be especially promising, since it goes beyond previous work by proposing a formal model that complies with the cognitive theories of social trust [START_REF] Castelfranchi | A non reductionist approach to trust[END_REF] and reputation [START_REF] Conte | Reputation in Artificial Societies. Social Beliefs for Social Order[END_REF].

However, Herzig et al. focus on describing a conceptual framework but do not provide any concrete implementation nor integration into software agents, thereby not showing any evidence about the effectiveness of their approach. This paper fills the gap by presenting such an integration targeting a meaningful real-world scenario related to Wikipedia. 1 The conceptual framework by Herzig et al. nicely fits the Belief-Desire-Intention (BDI) model [START_REF] Michael | Intention, Plans, and Practical Reason[END_REF] commonly adopted in agent programming. For this reason, it was a natural choice resorting to agent technologies in order to implement the instantiation mentioned above. More specifically, we 1 http://www.wikipedia.org/ describe an implementation based on the Jason [START_REF] Rafael | Programming Multi-Agent Systems in AgentSpeak using Jason[END_REF] and CArtAgO [START_REF] Ricci | Environment programming in CArtAgO[END_REF], [START_REF] Ricci | CArtAgO: A framework for prototyping artifact-based environments in MAS[END_REF] frameworks, although it must be clear that the methodology we present is general and can be applied to different agent technologies as well as to different scenarios.

The contributions of this paper are as follows.

• We extend the conceptual framework presented in [START_REF] Herzig | A logic of trust and reputation[END_REF] by introducing the notion of reputation of an agent not to do an action • We present an instantiation of such conceptual framework targeting a meaningful real-world scenario related to Wikipedia • We describe an implementation of such instantiation on top of Jason and CArtAgO This paper is organized as follows: Section II describes the tackled scenario. Section III introduces the conceptual framework which will be used in the remaining of the paper. Section IV describes the instantiation of the conceptual framework targeting the scenario presented in Section II. Section V describes the implementation of the scenario. The outcome of an experimental evaluation is reported in Section VI. Section VII accounts for related work. Finally, Section VIII presents further work and draws some conclusions.

II. RUNNING SCENARIO

Because of the huge dimension of Wikipedia, "a number of Wikipedia community members have set up long-standing patrols [. . . ] to help editors maintain reasonable quality on an encyclopedia this size [. . . ] Patrols are used in Wikipedia to watch over a class of pages and take any appropriate actions". 2 Among Wikipedia patrols, the Recent changes patrol is responsible for checking "the recent changes to various articles for harmful edits" [START_REF]Recent changes patrol[END_REF]. After identifying problematic edits, Recent changes patrollers (from now on patrollers) improve or revert the edits and possibly warn the contributors responsible for them.

In order to simplify the activity of patrollers, a number of tools and resources are available (a brief account thereof is provided in Section V). However, such tools have been mainly designed to support the activity of patrollers who work independently from each other and do not allow for knowledge transfer among them. This approach has many drawbacks

• no patroller can profit from other patrollers' experience and lessons learned. As a consequence, a new-entry patroller will need for instance to check n edits of a contributor c before realizing that c is a vandal, even if another patroller already checked enough edits of c to conclude that she indeed is • checking an edit's quality is not always trivial, since it often requires working knowledge about the topic of the edited article. Moreover-as confirmed by our investigation-simple and intuitive heuristics are not always effective (e.g., the use of a dirty or offensive word does not always indicate a vandalism, since it could be the only word known to a contributor not familiar with the article's language which has the intended meaning). The indication of the average quality of a contributor's edits as provided by other patrollers could save much time while evaluating upcoming edits of the same contributor • tools available to patrollers often allow to add contributors to black-or whitelists. However, since checking an edit's quality is not trivial, patrollers could mistakenly add contributors to such lists. Again, the possibility of comparing a patroller's evaluations with other patrollers' ones could prevent or reduce the effect of such wrong additions • a patroller might be a vandal herself. By sharing patrollers' evaluations and comparing them with each other, outlier behaviors (and hence vandal patrollers) can be easily identified The arguments listed above motivate the need of knowledge transfer among patrollers. At a low abstraction level, such knowledge can be thought of as a set of statistics about the quality of the edits of different contributors. At a high abstraction level, such knowledge can be interpreted as an expectation about the quality of upcoming edits performed by the contributors, i.e., a sort of confidence that the upcoming edits of the contributors will have a given quality.

In the following sections, we show how the conceptual framework presented in [START_REF] Herzig | A logic of trust and reputation[END_REF] allows to express and represent such knowledge.

III. CONCEPTUAL FRAMEWORK

The scenario described in Section II requires patrollers to exchange confidence estimates about the quality of contributors' upcoming edits. In other words, it requires to build a common belief within a patroller community about the future behavior of contributors. Within [START_REF] Herzig | A logic of trust and reputation[END_REF]'s conceptual framework, such a belief can be most naturally modeled by resorting to the concept of reputation.

This section recalls the conceptual framework presented in [START_REF] Herzig | A logic of trust and reputation[END_REF] and proposes an extension by introducing the notion of reputation of an agent not to do an action.

A. Dispositional trust and reputation

The concepts of trust and reputation have been formalized in [START_REF] Herzig | A logic of trust and reputation[END_REF] according to the socio-cognitive approach presented in [START_REF] Castelfranchi | A non reductionist approach to trust[END_REF]. In this theory, trust is defined as follows: "an agent i trusts an agent j for the action α in order to achieve a goal ϕ". Two concepts defined in the formalization are especially interesting for our work: dispositional trust and reputation.

Dispositional trust refers to a trust belief occuring whenever some conditions are satisfied. Agent i is disposed to trust agent j to do α w.r.t. ϕ in the circumstances κ iff

• i has the potential goal ϕ in the circumstances κ • i believes that from now on, if it has the goal ϕ and κ holds, then j will be capable to do α j, by doing α, will ensure ϕ to be true at some point j will intend to do α This definition describes dispositional trust in doing an action. A dual definition has been proposed to describe dispositional trust in inaction, i.e., a situation where the target is trusted not to do an action. Agent i is disposed to trust agent j not to do α w.r.t. ϕ in the circumstances κ iff

• i has the potential goal ϕ in the circumstances κ • i believes that from now on, if it has the goal ϕ and κ holds, then j will be capable to do α j, by doing α, will ensure ϕ to be always false j does not intend to do α

The concept of reputation has been addressed as a group belief: reputation refers to a dispositional trust belief of a group of agents instead of a single one. Agent j has reputation in group I to do α w.r.t. ϕ in the circumstances κ iff

• I has the potential group goal ϕ in the circumstances κ • it is public for the group I that from now on, if the group I has the goal ϕ and κ holds, then j will be capable to do α j, by doing α, will ensure ϕ to be true at some point j will intend to do α Because of space constraints, we point the interested reader to [START_REF] Herzig | A logic of trust and reputation[END_REF] for the formalization of such concepts as well as the definition of potential (group) goal and public belief.

B. Reputation not to do an action

Despite defining dispositional trust in a target doing and not doing an action, Herzig et al. only define reputation of a target doing an action. However, some scenarios require to represent the fact that a target is trusted within a group not to act in a way that would defeat a goal of the group. For this reason, we suggest to extend [START_REF] Herzig | A logic of trust and reputation[END_REF]'s framework with the concept of reputation of an agent not to do an action. More specifically, we propose that agent j has reputation in group I not to do α w.r.t. ϕ in the circumstances κ iff

• I has the potential group goal ϕ in the circumstances κ • it is public for the group I that from now on, if the group I has the goal ϕ and κ holds, then j will be capable to do α j, by doing α, will ensure ϕ to be always false j does not intend to do α For completeness, we formalize the concept of reputation not to do an action according to the formalism introduced in [START_REF] Herzig | A logic of trust and reputation[END_REF].

Reput(I, j, ∼ α, ϕ, κ) def = P otGoal ∀ I (ϕ, κ) ∧ P ublic I G * ( (κ ∧ i∈I Goal i (ϕ) ∧ Capable j (α) ∧ Af ter j:α G * ¬ϕ) ⇒ ¬Intends j (α))

IV. INSTANTIATION

In order to apply the conceptual framework described in Section III to the scenario introduced in Section II we have to

• identify the target agent j, the evaluating agent i or group of agents I, the action α of j, the goal ϕ of i or I and the context κ • find a way to estimate i's dispositional trust in j (resp. j's reputation in I) (not) to do α w.r.t. ϕ in the circumstances κ We will discuss the two issues in Sections IV-A and IV-B respectively.

A. Basic entities

It might be intuitive considering the target agent j as the Wikipedia contributor and the evaluating agent i as the patroller. After thinking a bit, it might be reasonable considering ϕ as the goal of preserving the integrity of Wikipedia articles which is independent from the circumstances κ. More debatable is which group(s) of agents I and which action(s) α we might want to consider. W.r.t. α, Krupa et al. [START_REF] Krupa | Trust based evaluation of wikipedia's contributors[END_REF] consider two possible actions: good and bad edits (which they call modification and vandalism respectively). This approach is consistent with Wikipedia's philosophy ("A bad edit is an edit that for one reason or another may need to be entirely removed. A needy edit requires maintenance or improvement in some manner" [START_REF]Recent changes patrol[END_REF]) and allows them to identify both bad and needy edits, as shown in Tab. I. Tab. I is supposed to be read as follows: rows (resp. columns) represent whether the contributor is trusted to provide a good edit (resp. to refrain from providing a bad edit). Notice that if an edit is trusted to be bad then it does not make sense checking whether it is trusted to be good. W.r.t. I, a trivial solution would be to consider as group of agents the set of all patrollers. However, it might be the case that most patrollers do not have any opinion about a given contributor, since it is unlikely that many patrollers checked many edits of the same contributor. Therefore, for each edit it might be meaningful considering I as the set of patrollers having a sufficiently well-founded opinion of the contributor who did such edit. Although this is the approach enforced in our implementation, we briefly mention a concurrent proposal (somehow suggested by [START_REF] Krupa | Trust based evaluation of wikipedia's contributors[END_REF]) which leverages articles' categories, i.e., "groups of articles on related topics". 3 According to this approach, when evaluating edits of articles belonging to a given category, I would be the set of patrollers who are expert for that category. We list below some issues which make the implementation of such approach a complex task.

• Not all articles are assigned to some category • Some articles are assigned to more than one single category • Category assignment varies with time • Retrieving patrollers' expertise is not trivial

B. Trust/Reputation estimate

As described in Section III, dispositional trust (resp. reputation) of a target agent j w.r.t. an action α and a goal ϕ can be computed based on the beliefs of an evaluating agent i (resp. a group of agents I) about: (i) j's capability and intention to do α; and (ii) which consequences j's execution of α has w.r.t. ϕ. W.r.t. the instantiation presented in Section IV-A, we hence have to estimate whether a given patroller believes (resp. whether it is public in the set of patrollers having a sufficiently well-founded opinion of the contributor) that 1) a given Wikipedia contributor is capable to do a good edit 2) by doing a good edit, the contributor will ensure the article to be consistent at some point 3) the contributor intends to do a good edit 4) the contributor is capable to do a bad edit 5) by doing a bad edit, the contributor will ensure the article to be always inconsistent 6) the contributor does not intend to do a bad edit By definition, a good edit preserves the consistency of an article. Moreover, every contributor is capable to do a bad edit. Finally, although a bad edit leaves an article in an inconsistent state, it is unlikely that the article will stay inconsistent forever. For these reasons, we can assume that every patroller believes (resp. that it is public in the set of patrollers having a sufficiently well-founded opinion of the contributor) that, for each Wikipedia contributor, items 2. and 4. in the list above are true and item 5. is false. 4Therefore, we only need to find a way to estimate whether the patroller believes (resp. whether it is public in the set of patrollers having a sufficiently well-founded opinion of the contributor) that: (i) the contributor is capable and intends to do a good edit; and (ii) she does not intend to do a bad edit.

Statistics about the previous activity of Wikipedia contributors can be adopted as a starting point. For instance, w.r.t. point (ii), since every Wikipedia contributor is capable to do a bad edit, whenever a given Wikipedia contributor j does a bad edit it holds that she intended to do a bad edit. For this reason, j can be assumed not to intend to do a bad edit whenever the number of bad edits she did is higher than a given (absolute or relative) threshold. Similarly, j can be assumed to be capable and to intend to do a good edit whenever the number of good edits she did is higher than a given threshold (not necessarily equal to the previous one).

This approach requires that, for each Wikipedia contributor j, the number of her (good/bad) edits is retrieved. The overall number of edits (starting from a given timestamp) can be easily retrieved by monitoring the edits occurring on Wikipedia and counting the ones done by j. More complex is to retrieve the number of good/bad edits, since patrollers do not explicitly tag edits as good, needy or bad. Krupa et al. rely on heuristics: they consider an edit to be good (resp. bad) if the time elapsed between j's edit and the following one related to the same article is above a given threshold (resp. the same article has been modified right after by some patroller who left a comment containing either of the words rv, revocation, révocation, vandalisme and annulation-notice that they focused on the French Wikipedia). Moreover, an article's category is taken into account when evaluating whether an edit done on such an article should be considered good.

Unfortunately, Krupa et al. do not provide evidences showing that their heuristics are not only reasonable but also effective. Indeed, beside the problems related to Wikipedia categories we mentioned at the end of Section IV-A, such heuristics could in principle be affected by the following issues: it might be the case that a given article is modified right after a good edit (resp. that a bad edit is discovered only after a while), moreover it might be the case that a patroller did not provide any comment when reverting a bad edit or that the comment does not contain the expected keywords. For this reason, at least two directions are feasible as further work: (i) performing a quantitative analysis in order to evaluate the effectiveness of such heuristics; and (ii) enabling patrollers to provide explicit feedback. Being the quantitative analysis still ongoing work (cf. Section VIII), Section V describes an implementation of the second approach based on the Jason [START_REF] Rafael | Programming Multi-Agent Systems in AgentSpeak using Jason[END_REF] and CArtAgO [START_REF] Ricci | Environment programming in CArtAgO[END_REF], [START_REF] Ricci | CArtAgO: A framework for prototyping artifact-based environments in MAS[END_REF] frameworks.

V. IMPLEMENTATION

In order to simplify the activity of patrollers, a number of tools and resources are available (a list thereof is provided in [START_REF]Recent changes patrol[END_REF]). Some of them filter the edits on Wikipedia articles according to some criterion (e.g., by focusing on the activity of contributors inside/outside the patroller's watch list), whereas most of them provide patrollers with all edits performed in some subset of Wikipedia (e.g., en.wikipedia). Some of them use as input Wikipedia's "Recent changes" special pages or RSS feed, but the favourite source of information about latest edits are by far Wikipedia's "Recent changes" IRC channels hosted on irc.wikimedia.org which communicate in real-time every operation performed on Wikipedia.

Tools currently available have been mainly designed to support the activity of patrollers who work independently from each other and do not allow for knowledge transfer among them. This section introduces MOUSQUE-TAIRE 5 , a collaborative tool enabling knowledge transfer among patrollers. Such a tool implements the approach described in Section IV and is freely available at http://labh-curien.univ-st-etienne.fr/ ∼ decoi/Mousquetaire. zip. Section V-A presents MOUSQUETAIRE's user interface, whereas Section V-B provides information about its implementation.

A. User interface MOUSQUETAIRE's GUI (depicted in Fig. 1) has been inspired by the one of Vandal Fighter6 . Both of them: (i) show edit notifications posted on Wikipedia's "Recent changes" IRC channels as rows in a table; (ii) allow to click on such rows in order to open the system browser at a page comparing the versions of the article immediately preceding and following the corresponding edit; and (iii) dynamically fill the table with new rows as soon as edits are notified through Wikipedia's IRC channels.

MOUSQUETAIRE's GUI also provides further functionalities: (i) table rows can be ascending/descending ordered according to the values appearing in a given column; (ii) rows can be filtered in order to show only the ones containing a given string in a given column; (iii) different perspectives are available which allow to group rows by article or contributor so that only the most recent edit per group is shown. In case such a perspective is selected, older edits of a given article (resp. by a given contributor) can be shown/hidden by clicking on the arrow at the left of the group's most recent edit.

Yet another perspective allows to only show further edits of articles edited by the patroller. This feature is especially useful to identify: (i) contributors who keep vandalizing articles even upon subsequent reverts of their edits; (ii) edit wars, which occur "when editors who disagree about the content of a page repeatedly override each other's contributions, rather than trying to resolve the disagreement by discussion". 7 However, the by far most important difference between MOUSQUETAIRE's GUI and Vandal Fighter's one is that the former allows patrollers to provide feedback for a given edit by selecting either of GOOD, NEEDY or BAD in the corresponding combo box and pressing the corresponding Submit button. Patroller feedback is then leveraged in order to automatically classify upcoming edits and show them in the corresponding tab.

B. Behind the scenes

Fig. 2 shows MOUSQUETAIRE's main components as well as the actors it interacts with: the front-end to the IRC channel and the IRC channel itself, the GUI, the knowledge bases containing trust/reputation estimates, the patroller and 7 http://en.wikipedia.org/wiki/Wikipedia:Edit warring In the first case (identified by letter a), the new edit intercepted by the IRC front-end (1a) and provided to the classifier (2a) is assigned by the latter an estimate based on the contributor's trust and/or reputation as available in the corresponding repositories. Both edit and estimate are then forwarded to the GUI (3a) with a request to update the table in the corresponding tab. If the tab is currently selected, the updated table is shown to the user (4a).

In the second case (identified by letter b), patroller feedback is communicated through the GUI (1b) to the classifier (2b), which will then use it in order to compute an updated trust/reputation estimate of the contributor whose edit has just been checked by the patroller. Such estimate is eventually stored into the corresponding repository and propagated to peer MOUSQUETAIRE engines (3b). Section V-B2 (resp. Section V-B3) is devoted to the description of the implementation of the control flow identified by letter a (resp. b). Since the classifier is implemented as a Jason agent, whereas both the IRC channel and the GUI are wrapped by a CArtAgO artifact, Section V-B1 briefly recalls such technologies.

1) Back-end technologies: The code of a Jason [START_REF] Rafael | Programming Multi-Agent Systems in AgentSpeak using Jason[END_REF] agent specifies its: (i) beliefs; (ii) proactive behavior (i.e., the tasks which the agent will perform sponte sua); and (iii) reactive behavior (i.e., the tasks which the agent will perform as a reaction to some event occurred in the outer world). Agent beliefs are represented as a Logic Programminglike [START_REF] Lloyd | Foundations of Logic Programming[END_REF] knowledge base. Agent behavior is specified as a set of plans, each of which consists of a list of activities to be performed if some condition holds. Examples of such activities are to query or modify the agent's knowledge base and to interact with other agents or the environment.

The CArtAgO [START_REF] Ricci | Environment programming in CArtAgO[END_REF], [START_REF] Ricci | CArtAgO: A framework for prototyping artifact-based environments in MAS[END_REF] framework greatly simplifies the interaction between Jason agents and the environment. In particular, CArtAgO allows to populate the environment with artifacts whose functionalities can be invoked by Jason agents and which can themselves issue signals, possibly triggering the reactive behavior of Jason agents. CArtAgO artifacts are Java classes extending cartago.Artifact: they can issue signals by invoking the parent class's signal methods, whereas Jason agents can directly invoke methods of CArtAgO artifacts annotated with cartago.OPERATION.

2) New edit operation: The control flow identified by letter a in Fig. 2 has been implemented as follows: whenever the CArtAgO artifact wrapping the IRC channel is notified that a new edit occurred, it issues the signal handleNewEntry with two parameters: an object containing information about the occurred edit and the userId (or IP address) of the contributor. The Jason agent implementing the classifier reacts to such a signal as follows: first the agent's knowledge base is inspected in order to retrieve an estimate of the contributor. Afterwards, the method addEntry of the CArtAgO artifact wrapping the GUI is invoked with two parameters: the estimate and the object containing information about the occurred edit.

In MOUSQUETAIRE, estimates of Wikipedia contributors can be based either on dispositional trust or reputation. In the first case, a patroller believes a contributor to be unknown if the patroller has no information about her. Otherwise, the patroller believes the contributor to be: (i) good if the number of good edits she did is higher than the half of her overall number of edits; (ii) bad if the number of bad edits she did is higher than the half of her overall number of edits; (iii) needy otherwise.

In the second case, the reputation of a contributor is: (i) good if all patrollers who already evaluated some edit of hers believe her to be good; (ii) bad if all such patrollers believe her to be bad; (iii) needy otherwise. Notice that if a patroller never evaluated any edit of a contributor she does not belong to the group within which the contributor has a given reputation, therefore she will assume such a contributor to have an unknown reputation.

3) Patroller feedback: The control flow identified by letter b in Fig. 2 has been implemented as follows: whenever the CArtAgO artifact wrapping the GUI is notified that the patroller submitted her feedback about some edit, it issues the signal feedback with two parameters: the userId (or IP address) of the contributor and the feedback submitted by the patroller. Within the knowledge base of the Jason agent implementing the classifier, a history/4 fact is available for each evaluated contributor. Beside the contributor's userId (or IP address), such a fact contains the number of her edits which have been evaluated as good/bad along with her overall number of edits.

When reacting to a feedback signal, the agent first checks whether information about the contributor who did the evaluated edit is available in its knowledge base. If this is the case, the history/4 fact related to the contributor is updated in both the agent's knowledge base and the other agents' one. The second step requires to broadcast two messages, the first one retracting the outdated information and the second one asserting the updated one.

If information about the contributor who did the evaluated edit is not available in the agent's knowledge base, a new history/4 fact is added to both the agent's knowledge base and the other agents' one.

VI. EXPERIMENTAL EVALUATION

As described in Section V, MOUSQUETAIRE can work both in the dispositional trust and reputation modalities. This section describes an experimental evaluation of the dispositional trust modality, whereas an evaluation of the reputation one is regarded as further work.

The results provided in the following are based on data crawled from the IRC channel devoted to the English Wikipedia throughout 24 hours starting from Fri Oct 22 16:45:49 CEST 2010. The dataset contains information about 183386 edits performed on 103811 Wikipedia pages by 30806 contributors. In average, 2.12 edits per second occurred, each page was edited 1.77 times and each contributor edited 5.95 times. Most pages were edited no more than once and most contributors edited no more than once. On the other hand, most edits involved 19576 pages (i.e., 19% overall) and were performed by 660 contributors (i.e., 2% overall).

103146 edits (i.e., 56% overall) involved Wikipedia pages other than articles (namely, books, categories and other administrative pages, files, portals, templates and users as well as talks about each of them). 28528 edits (i.e., 16% overall) were performed by bots, i.e., "automated or semi-automated tools that carry out repetitive and mundane tasks in order to maintain the [. . . ] articles of the English Wikipedia". 8The statistics provided in the following only relate to edits performed by humans on articles. 3825 edits have been manually reviewed in order to assess their quality. Assessing the quality of an edit is not always trivial, since knowledge about the edited article's topic is required. For this reason, in order to provide for an assessment as uniform as possible we mainly focused on syntactical issues. As a consequence, we considered edits contradicting each other as good as long as they left the article in a grammatically consistent state.

As a result of the assessment, each edit has been assigned a label out of G, N, P, B or U. Labels G, N and B are supposed to identify good, needy and bad edits respectively. Label P (possibly bad) has been assigned to suspicious edits which did not seem to deserve the label B. Finally, label U (unknown) has been assigned to edits which could not be checked, since an attempt to retrieve them returned an error message from the Wikipedia database.

Our evaluation only considered edits of contributors who performed at least two edits not labeled as unknown (2944 edits by 398 contributors). Fig. 3(a) (resp. Fig. 3(b)) provides a report about the effectiveness of our approach where possibly bad edits are considered as good (resp. bad). Beside noticing that the two reports do not essentially differ, we observe that our approach has a remarkable precision (86-87% of estimates are correct), whereas 5% of the estimates are false negatives (i.e., good edits considered as bad) and 4-5% are false positives (i.e., bad edits considered as good).

We conclude this section by mentioning that the MOUS-QUETAIRE package described in Section V also contains: (i) a database storing the crawled Wikipedia edits as well as utilities to automatically create such a database; (ii) a database storing the filtered Wikipedia edits as well as utilities to automatically filter out edits performed by bots or on Wikipedia pages other than articles; (iii) a database storing the manually assessed edits as well as utilities enabling to reproduce the results shown in Fig. 3; and (iv) a readMe.txt file explaining how to use the abovementioned utilities.

VII. RELATED WORK

The freedom to contribute that governs Wikipedia is a major reason of its success. However, it also enables to damage the encyclopedia by vandalizing its articles. In such a case, reverting bad edits requires first of all to identify them. Some tools, such as VandalFighter, notify patrollers of new edits. However, because of Wikipedia's intense activity, they cannot check every modification but have to define their own heuristics to decide which one should (not) be checked.

Automatic assistance is hence desirable to identify bad or needy edits as accurately as possible. A competition on vandalism detection software has been organized and analyzed in [START_REF]Notebook Papers of CLEF 2010 LABs and Workshops[END_REF]. Most of the competing tools classify edits according to features like presence of given keywords, size of the modifications, capitalization of characters or topic of the article. However, only one [START_REF] Javanmardi | Submission to the 1st international competition on wikipedia vandalism detection[END_REF] of the nine participants to the competition exploits an estimate of the contributor's trustworthiness. This approach has shown promising results, despite the trust model being a simple one.

Indeed, the decision (not) to check an edit is essentially based on trust. However, such decision is subjective as different patrollers might take different decisions for the same edit. Trust management has been addressed in the field of multi-agent systems and some work has been proposed which takes the social aspect of trust into account. A survey of existing models in this very active field can be found in [START_REF] Sabater | Review on computational trust and reputation models[END_REF].

Most of the trust models for multi-agent systems rely on statistics to make automatic decisions. However, this approach shows its limits whenever a tight interaction with human users is required as the integration of human and software trust decision processes has proved to be difficult. To overcome this drawback, socio-cognitive models of trust and reputation have been proposed [START_REF] Castelfranchi | A non reductionist approach to trust[END_REF], [START_REF] Conte | Reputation in Artificial Societies. Social Beliefs for Social Order[END_REF]. The work described in this paper builds this late approach into a software agent assisting patrollers in their subjective trust decision and enabling them to collaboratively build reputations.

VIII. CONCLUSIONS AND FURTHER WORK

The wide diffusion of open and decentralized environments like the Web makes it possible for actors to interact with previously unknown peers. As a consequence, trust has become a hot topic in the field of computer science. Many attempts to formalize concepts like trust and reputation have been carried out in the literature, most remarkably the one by Herzig et al. [START_REF] Herzig | A logic of trust and reputation[END_REF].

However, Herzig et al. focus on describing a conceptual framework but do not provide any concrete instantiation of it, thereby not showing any evidence about the effectiveness of their approach. In this paper, we filled the gap by: (i) extending the conceptual framework described in [START_REF] Herzig | A logic of trust and reputation[END_REF]; (ii) presenting an instantiation of such conceptual framework; and (iii) describing an implementation of such instantiation based on agent technologies. Although our implementation targets a Wikipedia-related scenario and exploits the Jason [START_REF] Rafael | Programming Multi-Agent Systems in AgentSpeak using Jason[END_REF] and CArtAgO [START_REF] Ricci | Environment programming in CArtAgO[END_REF], [START_REF] Ricci | CArtAgO: A framework for prototyping artifact-based environments in MAS[END_REF] frameworks, the methodology we presented is general and can be applied to different scenarios and agent technologies.

Concerning current and further work, the first issue we are trying to address is the cold-start problem: new edits can be automatically classified as good, needy or bad only if information about their contributors is available to the patroller('s group), i.e., if the patroller or someone in her group already evaluated some edit of the contributors. Heuristics like the ones presented in [START_REF] Krupa | Trust based evaluation of wikipedia's contributors[END_REF] quality of edits in a manual way in order to collect statistics to be used for the definition of meaningful heuristics. As a second goal, we would like to make our implementation available to the Wikipedia community. If on the one hand real users would provide the ideal testing environment for our approach, on the other hand our implementation needs to undergo some technical improvements before being publicly released. First of all, the user-friendliness of the GUI should be improved: so far, patrollers are required to provide explicit feedback about the edits they check. A future version could inspect a patroller's edit and automatically consider the previous one related to the same article as: (i) good; (ii) needy; or (iii) bad; according to whether the patroller: (i) checked the edit and did not do anything else; (ii) improved the edit; or (iii) reverted it.

Figure 1 .

 1 Figure 1. MOUSQUETAIRE's GUI

Figure 2 .

 2 Figure 2. Control flow within a MOUSQUETAIRE engine

Figure 3 .

 3 Figure 3. Results of the evaluation of MOUSQUETAIRE's dispositional trust modality

  provide a possible way to overcome this problem. For this reason, we are currently assessing the

	actual expected	bad needy good	actual expected	bad needy good
	bad	9%	0%	4%	bad	11%	0%	5%
	needy	2%	0%	2%	needy	2%	0%	2%
	good	5%	0%	77%	good	5%	0%	76%
	(a) possibly bad edits are considered as good	(b) possibly bad edits are considered as bad

http://en.wikipedia.org/wiki/Wikipedia:Patrols

http://en.wikipedia.org/wiki/Wikipedia:FAQ/Categories

Notice that this is different than in[START_REF] Krupa | Trust based evaluation of wikipedia's contributors[END_REF], where items 1. and 3. (but not items 2. and 4.) are assumed to be true.

The name has been suggested by the musketeers' collaboration-oriented motto Un pour tous! Tous pour un! ("One for all, all for one") in Alexandre Dumas' novel Les Trois Mousquetaires ("The Three Musketeers").

http://en.wikipedia.org/wiki/Wikipedia:VF

http://en.wikipedia.org/wiki/Wikipedia:Bots

ACKNOWLEDGMENTS

The work described in this paper has been carried out within the scope of the ANR ForTrust 9 project ANR-06-SETI-006.


Junjie Lai

André Seznec

TEG: GPU Performance Estimation Using a Timing Model

Keywords: GPGPU, CUDA, Performance Estimation, Analytical Model TEG: GPU Performance Estimation Using a Timing Model GPGPU, CUDA, Performance Estimation, Analytical Model

Modern Graphic Processing Units (GPUs) offer significant performance speedup over conventional processors. Programming on GPU for general purpose applications has become an important research area. CUDA programming model provides a C-like interface and is widely accepted. However, since hardware vendors do not disclose enough underlying architecture details, programmers have to optimize their applications without fully understanding the performance characteristics.

In this paper we present a GPU timing model to provide more insights into the applications' performance on GPU. A GPU CUDA program timing estimation tool (TEG) is developed based on the GPU timing model. Especially, TEG illustrates how performance scales from one warp (CUDA thread group) to multiple concurrent warps on SM (Streaming Multiprocessor). Because TEG takes the native GPU assembly code as input, it allows to estimate the execution time with only a small error. TEG can help programmers to better understand the performance results and quantify bottlenecks' performance effects.

Introduction

In recent years, more and more HPC researchers begin to pay attention to the potential of GPUs since GPU can provide enormous computing power and memory bandwidth. Today, many applications have been ported to GPU platforms with programming interfaces like CUDA [START_REF][END_REF] or OpenCL [8]. Though little efforts are needed to functionally port applications on GPU, programmers still have to spend lot of time to optimize their applications to achieve better performance. However, because few architecture details are disclosed, it is hard to gain insight into the GPU performance result. Normally, programmers have to exhaustively explore the design space or rely on their programming experience [START_REF] Ryoo | Program optimization space pruning for a multithreaded gpu[END_REF]. To better understand the performance remains a challenge for GPGPU community.

We present a GPU timing model to analyze GT200 GPU performance and the tool TEG to estimate GPU kernel execution time. TEG takes the output of a NVIDIA disassembler tool called cuobjdump [START_REF][END_REF]. cuobjdump can process the CUDA binary file and generate assembly codes. TEG does not execute the codes, but only uses the information such as instruction type, operands, etc. With the instruction trace and some other necessary output of a functional simulator, TEG can give the timing estimation in cycle-approximate level. Thus it allows programmers to better understand the performance bottlenecks and how much penalty the bottlenecks can introduce. We just need to simply remove the bottlenecks' effects from TEG, and estimate the performance again to compare. In our study, we make the following contributions. First, we present a timing model based on micro benchmarks and a new approach to estimate GPU performance with instruction traces. Second, we present how the performance scales from one warp to multiple concurrent warps on SM, thus TEG can give good estimation for applications with very few concurrent warps on SM.

Several works on GPU analytical models have been presented to help developers to optimize GPU applications. Hong et al. [START_REF] Hong | An analytical model for a gpu architecture with memory-level and thread-level parallelism awareness[END_REF] proposed a simple GPU analytical model that takes PTX code as input and statically predict execution time based on analyzing memory warp parallelism and computation warp parallelism. Another GPU analytical model introduced by Baghsorkhi et al. [START_REF] Baghsorkhi | An adaptive performance modeling tool for gpu architectures[END_REF] uses abstract interpretation of a GPU kernel to predict general purpose applications on GPU architecture. Kim et al. [START_REF] Kim | Cumapz: a tool to analyze memory access patterns in cuda[END_REF] presented a tool called CuMAPz to estimate GPU memory performance. CuMAPz collects performance-critical effects, such as shared memory bank conflicts and calculates a memory utilization parameter based on all these factors. Recently, Zhang et al. [START_REF] Zhang | A quantitative performance analysis model for gpu architectures[END_REF] proposed a quantitative performance model for GPU, which is similar to our approach. The main difference is that in our study, we use instruction trace instead of instruction statistics as the tool input, and demonstrate finer grained performance scaling behavior.

The paper is organized as follows: Section 2 introduces our target GPU architecture and CUDA programming model. In Section 3 we present our timing model for GPU. Section 4 demonstrates TEG's workflow. In Section 5 we evaluate TEG with two cases. Section 6 concludes this study and presents future direction.

Background

2.1 GT200 GPU Architecture GPU represents a major trend in the recent advance on architecture for high performance computing. GPU processor includes large number of fairly simple cores. We use NVIDIA GT200 architecture (Figure 1) as a candidate for our research.

GT200 is composed of 10 TPCs (Thread ProcessingCluster), each of which includes 3 SMs (Streaming Multiprocessor). Each SM further includes 8 SPs (Streaming Processor) and 2 SFUs (Special Function Unit). If we consider SP as one core, then one GPU processor is comprised of 240 cores.

For Geforce GTX 280 model, with 1296MHz shader clock, the single precision peak performance can reach around 933GFlops. GT280 has 8 64-bit wide GDDR3 memory controllers. With 2214MHz memory clock on GTX 280, the memory bandwidth can reach around 140GB/s. Besides, within each TPC there is a 24KB L1 texture cache and 256KB L2 Texture cache is shared among TPCs. NVIDIA has announced the new generation GPU with code name Fermi. There are a few differences from GT200 generation. First of all, the TPC is removed from the architecture and each SM contains 32 SPs, much more than 8 of GT200. Fermi provides real L1 and L2 cache hierarchy. Double precision computation power increases dramatically for Tesla version Fermi. Since in our present research step, cache effects are ignored, Fermi will be our next research target.

Inria

CUDA Programming Model

The Compute Unified Device Architecture (CUDA) [START_REF][END_REF] is a C-like abstraction for NVIDIA GPU, and has very good programmability. A CUDA program is composed of host code, which runs on the host CPU, and device code or kernel, which runs on the GPU processor. The device code is first compiled into PTX code, and then into native GPU binary code. In the PTX code, register resource is assumed to be unlimited. The resource allocation and some optimization techniques, such as instruction reordering, are applied when compiling PTX code into binary code.

A typical CUDA program normally creates thousands of threads to hide latency with very light-weight context switch mechanism. These threads are grouped into 1D to 3D blocks, and blocks are grouped into 1D or 2D grids. Threads within one block can share data in shared memory. Programmers need to provide enough number of threads to get good occupancy, so as to hide arithmetic pipeline latency and memory access latency.

Each block is distributed to one SM at execution time. A barrier synchronization operation can only be applied to threads in the same block. The basic execution and scheduling units are warps. For GT200 GPU, each warp contains 32 threads. Because processor resources, such as registers and shared memory, are limited, only a limited set of warps can run concurrently on SM, called active warps. We only need to model a few warps running concurrently on each SM to estimate GPU's performance. Thus, good approximation can be obtained while the problem size is limited.

There are three levels of memory space in CUDA abstraction. Each thread has its own local memory. Each block has a private shared memory partition. All threads can access the global memory , the constant memory space and the texture memory space. Local memory, global memory, constant memory and texture memory are mapped to off-chip DRAM. Both constant memory and texture memory are cached through read-only caches. The per-block shared memory is mapped to on-chip SRAM.

Model Setup

In this part, we present an analytical model for GPU GT200 and the key parameters of the model. Then we discuss some performance effects that TEG can demonstrate.

GPU Analytical Model

Our model for GT200 GPU is illustrated in Figure 2. In our model, each SM is taken as one processor core. SM is fed with warp instructions. Inside one SM, there are issue engine, shared memory, register file and functional units like SP, DPU, SFU and LD/ST unit. Global memory load/store instructions are issued to LD/ST unit.

Every 2 cycles, the issue engine selects one ready warp instruction from active warps and issues the instruction to the ready functional units according to instruction type. A warp instruction can be be issued when all the source operands are ready. GPU uses a scoreboard mechanism to select the warp with a ready warp instruction. In our model, different scoreboard policies are implemented. For each warp, since instructions are issued in program order, if one instruction's source operands are not ready, all the successive instructions have to wait.

Every three SMs share the same memory pipeline in one TPC, and thus share 1/10 of peak global memory bandwidth. 8 channels connect the device memory chips with the GPU processor and each channel bandwidth cannot exceed 1/8 of peak global memory bandwidth. We do not model the on-die routing of memory requests, since the hardware details have not been disclosed.

TPC x10

Model Parameters

To use the analytical model in TEG, we need to estimate model parameters. In this section, some main parameters are introduced. Much work has been done to understand GPU architecture through benchmarking [START_REF] Wong | Demystifying gpu microarchitecture through microbenchmarking[END_REF]. Many results and ideas are borrowed from this work.

Instruction Latency

Two types of instruction latency are of interest. One is the execution latency, or cycles that an instruction needs to execute in a functional unit. The other is the issue latency, or cycles that the scheduler has to wait to issue another instruction after issuing one warp instruction. A warp instruction launches 32 operations.

Inria

The issue latency is calculated using instruction throughput information. For example, the throughput for integer add is 8 ops/clock. So the issue latency is 32/8 = 4 cycles. When there are enough active warps, the scheduler can issue another warp instruction from another warp in 4 cycles after issuing one integer add instruction. However, when only one single warp is active on SM, the instruction throughput cannot reach the peak performance. According to the instruction throughput of one warp, we can calculate the issue latency of the instruction in one warp. More details are in Section 3.2.2. We illustrate below the methodology that we use to measure instruction execution latency and issue latency.

The typical technique to measure instruction latency is to use the clock() function. The clock() function returns the value of a per-TPC counter. To measure instruction execution latency, we can just put dependent instructions between two clock() function calls. For example, the CUDA code in Listing Some arithmetic instructions' execution latency and issue latency are listed in Table 1. Since float MUL operation can be issued into both SP and SFU. The instruction has higher throughput and shorter issue latency. In the table we only present the latency for 16 bit integer MUL and MAD, since 32-bit integer MUL and MAD operations are translated into the native 16-bit integer instructions and a few other instructions. In each SM, there is only one SFU which can process double precision arithmetic instructions. Thus, the issue latency is much longer for double precision arithmetic instructions.

Performance Scaling on One SM

In the previous section, the issue latency is calculated assuming several warps are running concurrently. For example, float MAD instruction's issue latency for multiple warps is 4. But if we run only one warp, then the measured issue latency is 8. And for a global memory load instruction GLD.U32, the issue latency in the same warp is around 60 cycles while the issue latency for multiple warps is a much smaller value and we use 4 cycles in TEG. Similar results are obtained for other arithmetic instructions and memory instructions, which suggests that a warp is occupied to issue one instruction while the scheduler can continue to issue instructions from other warps and the occupied period is normally longer than the waiting time of the scheduler to issue a new instruction from another warp. Thus it is not possible to achieve peak performance with only one active warp on SM even if most nearby instructions in one warp are independent.

After one warp instruction is issued, the scheduler can switch to another warp to execute another instruction without much waiting. However, if the scheduler still issue instructions from the same warp, the longer issue latency is needed. This undocumented behavior may affect performance when there are very few active warps on SM.

Inria

Masked instruction

All 32 threads within a warp execute the same warp instruction at a time. When threads of a warp diverge due to a data-dependent branch, they may have different execution path. GPU executes each path in a serial manner. Thus, the warp instruction is masked by a condition dependent on thread index. For masked arithmetic instructions, we find that all behavior remains similar as the un masked behavior. That is to say, all the issue latency and execution latency are the same as those of unmasked arithmetic instructions. For memory operations, since less data needs to be transfered, the latency is shorter and less memory bandwidth is occupied.

Memory Access

We consider the memory access separately from the other instructions because of 3 reasons. First, other functional units belong to one SM only, but each 3 SMs within one TPC share the same memory pipeline and all SMs share the same 8 global memory channels. Second, the scheduler needs to wait around 60 cycles after issuing one global memory instruction to issue another instruction in the same warp, but it can issue another instruction very quickly if it switches to another warp (Refer to Section 3.2.2). Third, memory access has much more complex behavior. For shared memory access, there might be bank conflicts (Section 3.3.3), and then all memory accesses of one half-warp are serialized. For global memory access, there might be coalesced and uncoalesced accesses (Section 3.3.4).

The typical shared memory latency is about 38 cycles and the global memory latency without TLB miss is about 436 to 443 cycles [START_REF] Wong | Demystifying gpu microarchitecture through microbenchmarking[END_REF].

Let C mem represent the maximum number of concurrent memory transactions per TPC and it is calculated as follows:

N T P C * N W arp * ele_size * C mem mem_latency * 1 Clk = B peak C mem = B peak * mem_latency N T P C * N W arp * ele_size * Clk
where N T P C , N W arp , ele_size, mem_latency, Clk, and B peak denote the number of TPCs, the number of threads per warp, the accessed data type size, the global memory latency, processor clock frequency, and the peak global memory bandwidth, respectively. For double precision memory transactions, C mem ≈ 18. Thus the number of unfinished double precision memory transactions through the memory pipeline of a TPC cannot exceed 18.

Performance Effects

Branch Divergence

Masked instructions (Section 3.2.3) are warp instructions with a warp size mask. Each bit of the mask indicates whether the corresponding thread is active to execute the instruction. Threads of the same warp may have different execution path. Since SM has to finish each path in serial and then rejoin, extra execution time is introduced.

Instruction Dependence and Memory Access Latency

One of the motivations or advantages of GPU processor is that it can hide latency due to instruction dependence or memory access by forking large number of threads. However, when there are very few active warps, it is possible that at some point, all warps are occupied in issuing instructions. The scheduler is available but none of the active warps can be released. Thus the latency cannot be perfectly hidden and may become an important factor to performance degradation.

Bank Conflicts in Shared Memory

The shared memory is divided in 16 memory modules, or banks, with the bank width of 4 bytes. The bank is interleaved so that successive 4 bytes words in shared memory space are in successive banks. Threads in a half-warp should access different banks to achieve maximum shared memory bandwidth. Otherwise the access is serialized [START_REF] Ruetsch | Optimizing matrix transpose in cuda[END_REF], except all threads in a half-warp read the same shared memory address.

For example, the float ADD instruction FADD32 R2, g[A1+0xb], R2; has a operand g[A1+0xb] located in shared memory. The execution latency is around 74 cycles without bank conflict. If all threads within a half-warp access the same bank, the execution latency becomes about 266 cycles.

Uncoalesced Memory Access in Global Memory

The global memory of GPU has very high access latency comparing to shared memory latency. For global memory accesses of a half-warp, if certain conditions are satisfied, the memory transactions an be coalesced into one or two transactions. The required conditions depend on GPU hardware and CUDA compute capabilities. The general guideline is that threads of one half-warp should access adjacent memory elements. If the coalesced conditions cannot be met, more memory transactions are needed, introducing much performance loss. For example, if every thread loads 4 bytes from global memory, in the worst case, to serve each thread in the half-warp, 16 separate 32-byte transactions are issued. Thus 87.5% of the global memory bandwidth is wasted.

Chanel Skew in Global Memory

The global memory of GT200 GPU is divided into 8 partitions. The global memory thus can be accessed through 8 channels. The channel width is 256Btyes (32*8B) [START_REF] Ruetsch | Optimizing matrix transpose in cuda[END_REF]. Similar as accessing to shared memory, concurrent accesses to global memory should be distributed evenly among all the partitions to achieve high global memory bandwidth. Load imbalance on the memory channels may significantly impair performance. If the application's memory access pattern has significant imbalance over different channels, much performance degradation will be introduced.

Inria

C(i, j) = k A(i, k) * B(j, k)
In the implementation, the three matrices A, B and C, are partitioned into 16x16 sub-matrix. The computation for a C sub-matrix is assigned to a CUDA block. A block is composed of 256 (16x16) threads and each thread computes one element in the C sub-matrix. In the CUDA kernel, at each step, a block of threads load the A and B sub-matrices first into shared memory. After a barrier synchronization of the block, each thread loads A(i, k) and B(j, k) from shared memory, and accumulates the multiplication result to C(i, j).

However, since a half-warp of threads, load B(j, k), B(j + 1, k), . . . , B(j + 15, k), for a shared memory allocation like B[16][16], all the 16 elements will reside in the same bank and there would be bank conflicts in the shared memory.

In the following experiment, we assign each warp with the same amount of workload and run 1 to 16 warps concurrently on one SM. We use clock() function to measure the execution time on device of one block, since the barrier synchronization is only applicable within one block. And for multiple blocks' total execution time, we use the measured host time to calculate the device Then we compare the host time for the two configurations and calculate the cycles for 2 blocks (16 warps) to finish on the SM. The measured and predicted execution time of 1 to 16 concurrent warps on one SM is illustrated in Table 2. Then we normalize the execution time with the workload and show the speed up from 1 to 16 active warps on each SM in Figure 4. For GPU performance optimization, programmers often come to the question that how much performance loss due to one performance degradation factor. With TEG, it is fairly easy to answer the question. We just need to change the configuration. In this case, in the tool, we just assume all shared memory accesses are conflict-free. Thus we can estimate the performance without shared memory bank conflict, which is illustrated in Figure 5 and Table 3.

We then modified the CUDA code to eliminate bank conflicts and compare the result with TEG's output. The comparison shows very good approximation.

Lattice QCD

Quantum chromodynamics (QCD) is the physical theory for strong interactions and lattice QCD is a numerical approach to QCD theory. Lattice QCD simulation is one of the challenging problems for high performance computing community. We select one kernel in Hopping_Matrix routine [START_REF] Ibrahim | Efficient simdization and data management of the lattice qcd computation on the cell broadband engine[END_REF] as our example. The input of the Hopping_Matrix kernel include the spinor field, the gauge field, the output is the result spinor field. The spinor field resides on the 4D space-time site and is represented by a 3x4 complex matrix data structure. The gauge field on the link connecting neighbor sites is implemented as a 3x3 complex matrix. The half spinor filed is represented by a 3x2 complex matrix, which is the temporary data generated on each of 8 space-time directions for one full spinor.

The functionality of the kernel is not important to our discussion. Instead, the memory layout is of interest. In the first version of our implementation, all the data is organized in array of structures. This is typical data layout for conventional processors to obtain good cache hit rate. However, GPU has much more concurrent threads. Normally different threads are assigned with different data structures. So the accesses of the threads in a warp have a long stride of the size of the data structure. Thus, accesses to global memory cannot be coalesced. The predicted and measured execution results are illustrated in Table 4 and Figure 6. Since each thread occupies much register resource, the active warp number is limited. If we reorganize the data layout into structure of arrays, the memory accesses of threads in a warp would be adjacent. Thus they can be coalesced. The result is shown in Table 5 and Figure 7. This case also shows that TEG can easily demonstrate the performance loss due to performance bottlenecks, such as uncoalesced memory accesses.

Conclusion

In our paper, we present our timing model for GT200 GPU a timing estimation tool TEG. With the timing model and the assembly code as input, TEG can estimate GPU cycle-approximate performance. Evaluation cases show that TEG can get very close performance approximation. Especially, TEG has good approximation for applications with very few active warps on SM. Thus we could better understand GPU's performance result and quantify bottlenecks' performance effects. Present profiling tools can only provide programmers with bottleneck statistics, like number of shared memory bank conflict, etc. TEG allows programmers to understand how much performance one bottleneck can impair and forsee the benefit of eliminating the bottleneck. The main limitation is that TEG cannot handle the situation when there is much memory traffic and a lot of memory contention occurs because we lack the knowledge of detailed on-die memory controller organization and the analysis is far too complicated for our analysis method. Our future plan includes studying the new Fermi architecture and introducing cache effects into our model.

Figure 1 :

 1 Figure 1: Block Diagram of GT200 GPU

Figure 2 :

 2 Figure 2: GPU Analytical Model

Figure 4 :

 4 Figure 4: C = AB T with Bank Conflict

Figure 5 :

 5 Figure 5: C = AB T Modified

Figure 6 :

 6 Figure 6: Hopping_Matrix kernel with Uncoalesced Accesses

Figure 7 :

 7 Figure 7: Hopping_Matrix kernel with Coalesced Accesses

Table 1 :

 1 The assembly code after compiling PTX code to binary code is in Listing 3. S2R instruction move the clock register to a general purpose register. A dependent shift operation after S2R suggests that the clock counter is incremented at half of the shader clock frequency. An extra 28 cycles is introduced because of the dependence between SHL and S2R (24 cycles), and the issue latency of SHL (4cycles). Arithmetic Instruction LatencyFor 21 FADD32 instructions between the two clock measurements, the measured cycles are 514. So the execution latency of FADD32 is (514 -28 -8)/20 ≈ 24.8 cycles are the issue latency of FADD32 in one warp (Please refer to 3.2.2 for more details).

	1

Table 3 :

 3 C = AB T Modified execution time. For example, when there are 30 blocks, each SM can be assigned one block and when there are 60 blocks, each SM has two blocks to execute.

	Inria

Table 4 :

 4 Hopping_Matrix kernel with Uncoalesced Accesses

	WarpNum	1	2	4
	Measured (cycles)	51053	68383	122430
	Predicted (cycles)	46034	66674	110162
	Error	-10.90% -2.56% -11.14%

RR n°7804

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Source Code

Binary Code Nvidia

The binary code includes the native kernel code that runs on GPU device. Second, the binary code is disassembled using tool cuobjdump provided by NVIDIA [START_REF][END_REF]. Third, TEG analyzes the generated assembly code and obtains information such as instruction type, and operands' type, etc.

We need the actual instruction traces in many cases. The instruction trace can be obtained with detailed GPU simulators, such as Barra [START_REF] Collange | Barra: A parallel functional simulator for gpgpu[END_REF] or GPGPU-Sim [START_REF] Bakhoda | Analyzing cuda workloads using a detailed gpu simulator[END_REF]. In our study, the instruction trace is provided by Barra simulator.

So after the third step, the assembly code information and instruction trace are served to issue engine model (see Figure 3). The issue engine model issues all the warp instructions to corresponding functional units model according to the instruction trace and our GPU timing model. At this stage, all runtime timing information can be collected by our information collector.

We can vary the configuration of TEG, such as the active warp number on SM to observe how performance scales from one warp to multiple concurrent warps. We can also compare the performance with or without one bottleneck by choosing whether or not to apply the bottleneck's effects in TEG. Thus we can quantify how much performance gain we may get by eliminating the bottleneck and programmers can decide whether it is worth the optimization efforts.