Nicolas Auray

Folksonomy: the New Way to Serendipity

Keywords: taxonomy, indexation, innovation and user-created content

Folksonomy expands the collaborative process by allowing contributors to index content. It rests on three powerful properties: the absence of a prior taxonomy, multiindexation and the absence of thesaurus. It concerns a more exploratory search than an entry in a search engine. Its original relationship-based structure (the three-way relationship between users, content and tags) means that folksonomy allows various modalities of curious explorations: a cultural exploration and a social exploration. The paper has two goals. Firstly, it tries to draw a general picture of the various folksonomy websites. Secundly, since labelling lacks any standardisation, folksonomies are often under threat of invasion by noise. This paper consequently tries to explore the different possible ways of regulating the self-generated indexation process.

From one point of view the domains where the amateur productions begin to rival the level of the content of professional and institutional productions are on the increase: public corporations recognise that the blog and its anonymous aficionados contain more information than the 'official' medium produced by their distributors or agents, (BEAUDOIN & LICOPPE, 2002), or created by their political party [START_REF] Beauvallet | Parties de champagne. Militer en ligne au sein de Désirs d'avenir[END_REF]; while new artists are appearing who first earned reputations in the blogosphere (CARDON & DELAUNAY, 2006). This wealth of amateur content represents a generalisation throughout all cultural life of the phenomenon known as the 'democratisation of innovation ' (von HIPPEL, 2006); with amateurs injecting radical innovations into that realm undreamt of by engineers and whose existence specialists had previously primarily observed in cutting edge areas confined to IT, biotech or chemistry.

O

No. 65, 1 st Q. 2007

There are structural causes behind this massive and remarkable appearance of amateurs on the cultural stage by means of the internet. They include the significant increase in cultural capital on the part of internet uses, supported by upgraded education, the generalisation of intellectual work and the spread of the use of the internet among white-collar workers. Thus [START_REF] Leadbeater | The Pro-Am Revolution. How enthusiasts are changing our economy and society[END_REF] explain the development of the 'professionalized amateurs' (labelled as "pro-ams") by the generalised articulation we are now seeing of the vocational model of voluntary leisure and creative investment in paid work. This movement, backed by sustainable causes, seems to be further supported by the growing interest shown by the economic world in stimulating and organising this enormous business of the decentralised production of content. Apart from the sporadic attempts made by some companies to use amateur content (for the Netscape example, see AURAY, 2000; on crowdsourcing in general, see [START_REF] Howe | The rise of crowdsourcing[END_REF], what we observe is a continuous reprocessing of amateur content by the cultural industries [START_REF] Jenkins | Convergence Culture: Where Old and New Media Collide[END_REF] has shown in the sector on video games), or the development of a musical remix culture that endows objects, which have been paired with others or removed from their original environment, with greater fame than the original products. This huge inflow of amateur content has overturned the organisation of data on the internet. It multiplies referencing problems. The volatility and novelty of content is giving rise to congestion in search engines that are poorly suited to seeking non-textual data, blog commentaries or forum posts. But at a broader level, in line with a principle often observed by science sociologists, and which Merton has dubbed the "Saint Matthew effect", search engines depend on algorithms that favour content, which has already been massively quoted; they therefore focus all their attention on a limited number of sites that match the tastes of the majority. It turns out, however, that a major feature of the growing power of amateurs is the emergence of a new distribution model characterised by a 'long train' [START_REF] Anderson | The Long Trail[END_REF]. Demand is spread out over a large number of products. Products previously reserved for niche markets may see-saw into mass popularity, driven by word-of-mouth and web-user recommendations. Distribution circuits are pluralistic and horizontal, with growth in the number of cultural middle-men, where the judgment of the public and the commentary of web-user communities are added to the verdict of critical opinion and promotion appearing on the mass media. This gives rise to a requirement expressed by various web-users, ill-served by search engines, for a finer referencing of the complex space of cultural tastes based on the multiplication of subcultures and niches.

Definition of 'folksonomy'

To provide a remedy for this problem, users have come up with the idea of importing the spirit of collaboration by allowing the users themselves to create and share their key words. The term 'folksonomy' refers to these forms of self-generated references1 . It is usually attributed to Thomas van der Wal, an information architect and senior consultant at Infocloud. The basis of the word is 'folk', meaning people in general and taxonomy, from the Greek taxis (arrangement, name, law, used here in the sense of systematic classification). Leaving their differences aside, folksonomies display three marked characteristics: They depend on 'popular' self-indexation, in the sense that it is web users themselves, the contributors or readers of contents, who label them by allocating key words to them. Unlike classical classification systems, such as the Dewey universal classification, contributors to a folksonomy are not bound by a pre-defined terminology, but can adopt whatever terms they like to classify their resources. These terms are often known as key words or tags.

While in classical classification theory a taxonomy designates systems whereby categories are connected to each other by the inclusion of classes, the more inclusive a category is in a taxonomy, the higher its level of abstraction, folksonomies depend on multi-indexationthe same item may appear under a number of key words. This leads to a flexibility of the hierarchical relationship between the taxons: the same item may be placed in a subordinate category or terminal (which has no sub-category) and throughout the length of the category tree. The picture of a Siamese cat, for example, may be labelled under the key words Siamese and cat, but also under feline or animal, which is the generic category. But folksonomy also allows an object to be labelled by its characteristic attributes or features, and not by the categories to which it belongs. A photograph of a swallow is as likely to be labelled wings or feathers, as bird. Unlike, say, the Linnaean system for classifying animals, which is an exemplary system, folksonomies are more horizontal, labelling systems organised on a grid and open to characteristics that are known in linguistics as sememes.

Folksonomy is based on a relaxation of the relationships between the term and the index. [START_REF] Voss | Collaborative thesaurus tagging the Wikipedia way[END_REF] has also thrown light on the difference No. 65, 1 st Q. 2007 between this and the thesaurus categorisation system. The thesaurus, in the sense in which it was developed by Peter Luhn in 1957, is a tagging system 'controlled' by the fact that the a priori relationships between terms in the index are rendered explicit by the fact that they are connected by three types of relationshipsequivalence , hierarchy and association. Folksonomy releases this type of restriction between the indices of the items, by rendering them uncorrelated or non-connected. The first shared sites which used the principle of 'popular taxonomies' were del.icio.us , a shared site of web page bookmarks, set up in 2001, and FlickR, a shared photo site, created in 2000. Reaching a critical mass seems to have been the essential parameter for the success of these sites. They attracted their first users by offering them tools to help them store individual content. In other words, del.icio.us and FlickR were successful [START_REF] Tonkin | Folksonomies -Tidying up Tags?[END_REF] because it was easy to enter tags on them (APIs on the browsers allowed exportation onto the site), and particularly because they offered an easy way for users to check their photographs or bookmarks from anywhere. What attracted the first users was more like a raft of 'selfish' motivations [START_REF] Tonkin | Folksonomies -Tidying up Tags?[END_REF], such as simplified access to their own files2 . These taxonomy systems (in the broadest sense) then became applied, via self-generated indexation, to other types of content:

Blogs

Technorati, one the of the largest blog indexation engines has offered the provision in its pages of tags connected to content since January 2005. By August 2005, there were no less than 25 million labelled tags, and this figure has now risen to 34 million, with 12,000 new tags appearing every day.

Current events

Slashdot, a technical/scientific current events site, was the first to initiate the trend in this type of content. It produced a number of clones, of which the largest were Newsvine, offering current events in the form of a blend of professional sources (Associated Press) and web-user publications, and Ohmynews!, a current events site with 41,000 'citizen' contributors over six years, and where 30% of the site is edited by an editorial team.

Human skills

The Tagalag site allows for the tagging of individuals referenced by their names and geographical location or the terms that best characterise them. The service, which also exists in a beta version, would make it possible to find, for example, animated film fans in Manhattan. With the same type of content, the http://www.43things.com site, inspired by a local exchange system, makes it possible to establish relationships between people with an offer of 43 things to do, and people who either want to discover what the others want to do, or if they are in the same area, want some help on a reciprocal basis thanks to self-produced tags.

Image and sound

Music has been added to the sharing of videos (dailymotion and YouTube) and photographic images. In 2006, Yahoo launched a podcast directory, which also included tags, which tended to demonstrate that all new services had to include this browser principle from then on.

Folksonomy can therefore be seen as a fundamental movement that expands the collaborative process, by granting users the power to index content, hence returning a certain degree of control to users. It also represents a somewhat paradoxical phenomenon: on the one hand users, customers or end users are increasingly concerned with being located at the heart of the system as individuals, while striving to register themselves within a communal or network initiative on the other. Even so, as a means whereby co-operative tagging can be set up, folksonomy rests on very precise and No. 65, 1 st Q. 2007 specific methods. Three powerful properties can be discerned: the absence of a prior taxonomy, multi-indexation and the absence of thesaurus. These features are not, however, unique to the system. BEAUVISAGE (2005) showed that some internet directories had already opted for the structural choice of multi-indexation prior to the emergence of folksonomies.

Folksonomies are polarized and focus on two social objectives

An original aspect of the relationship structure of folksonomy site is the fact that it is three-way: there are the resources (the content), tags and users.

Fig.2 -A model of tagging system

The specific nature of this structure as resting on a number of bases has given rise to the drawing of two-way graphics to code the data. Kleinberg, for example, has grasped the way in which the social graphic of writers and the social graphic of content are connected (via links). CHAKRABARTI et al. (1998) have also tacked this process, by making a distinction between writers, content and anchor text.

The opposition between broad and narrow folksonomies

Thomas van der WAL (2005) distinguishes two types of folksonomies, the broad and the narrow. This distinction is important. The first category, of which del.icio.us is an example, is characterised by the breadth of the number of tags authorised to reference an item, and the fact that the user may re-allocate an already issued tag to existing content. The second category, of which FlickR is an example, is characterised by a limitation in the number of tags used to reference an item. This limitation starts from a restriction in the number of users who have the right to apply a label, and moves to a quota system for the number of tags that can be entered. Each system has its advantages and disadvantages. 'Broad' folksonomy, for example, has the plus that it is possible to view the various ways in which people describe a collection of shared content, and thus of identifying emerging vocabularies and trends. An indirect consequence of this advantage is that 'broad' folksonomy allows a population to be broken down into affinity groups according to the descriptive vocabulary they use; this is a convenient tool for matching similar individuals, that is, people who have similar systems for perceiving and categorising the world. But the downside of 'broad' folksonomy is the dispersal of the description of the object into a large number of different key words; it becomes harder to find a specific piece of content. 'Narrow' folksonomy, however, because it is less casual as regards the attachment of a key word to a piece of content, reveals its strength in finding precise content from a key word search. It is particularly useful when it comes to building databases on content, which cannot be easily found by text-based searches using the standard tools. An indirect advantage is that it allows for the grouping of content on a basis of the cooccurrence of key words within the groups by ascending classification methods 3 . A high level of importance is attributed to grouping by FlickR, for example, allowing photographs with a similar content to be tracked down by ascending classification 4 . This central opposition suggests that there is a distinction between social usages. Vander Wal emphasises the fact that broad folksonomy systems are based, above all, on the placing of importance on social grouping properties, where connections between individuals are achieved on a basis of breaking No. 65, 1 st Q. 2007

down the population into groups with similar perception concepts. These types of folksonomy, resting as they do on social networks, can only classify information and share it; they put together users who share the same centres of interest. The indexer-user becomes in turn himself indexed to a certain degree and placed in relationship with other key words. Narrow folksonomy systems, on the other hand, are above all focussed on the development of the properties of the exploration of the corpus, little by little, thanks to the relevance of the descriptors used5 .

More generally, the opposition between the two systems of folksonomy emphasises, in an underlying way, a feature common to boththe reevaluation of exploratory usages. This opposition therefore reveals two different modalities of these curious usages: the first corresponding to cultural curiosity, the second to social curiosity.

The assumption of cultural curiosity

The folksonomy would be a solution for a more exploratory web search than that using a search engine: the little by little quest. It is a more random way of exploring the blackboard. This gives rise to the theory behind Adam MATHERS' work (2004): "Browsing versus Finding," namely that there is a fundamental difference between direct searching with a query and browsing to find interesting content. The primary virtue of folksonomy is 'serendipity' (in the sense of lucky chance). This is a solution that encourages browsing, and, via a collection of interlinked tags, constitutes a fantastic source for identifying unexpected finds, which would never have been revealed without it. It is the same difference between exploring a problem space to formulate questions and seeking effective answers to precisely formulated questions. On this point it is not obvious whether the use of folksonomy sites is a response to an explicit prior preference for exploration, or if, on the contrary, folksonomy has provided the occasion and influenced the development of exploratory uses of the web without it having been planned in advance (lucky chance). What is certain, however, is that folksonomy sites allow a more open, more random, exploration of content than the use of a search engine. In this way, folksonomy music sites will show you the playlists of those people who like the music you listen to, which leads us to constantly vary our music. The Pandora site boasts that it allows web users to "create a random radio", by discovering artists by making use of the users' playlists. Similarly, del.icio.us mentions the importance of assistance in exploration, in curious sifting. Visual aids make it possible to browse from tag to tag by navigating around the graphic of co-occurring tags such as "Revealicious", a tool developed by Sébastien Pierre de Ivy (software architecture and design); hublog, a tool developed by Alf Eaton (see EATON, 2005). More sophisticated plug-ins make it possible to browse from a tag to all the people who tagged the tag6 . In order for this to be possible, all folksonomy sites depend on mechanisms, which reinforce the relevance of this cultural browsing: the uniqueness of the tagging process and collaborative filtering (MALTZ, 2005).

On the one hand, in order not to crush the diversity of content under a small number of dominant categories used to index them, folksonomy sites strive to maintain diversity in labelling as an objective. All categorisation rests on deciding between two limitations: (see ROSS, 1978 for a more detailed presentation): providing the maximum of information with the No. 65, 1 st Q. 2007 smallest cognitive effort; and staying as close as possible to the perceived world so that the categories represent (map) the structure of the actual world as accurately as possible. It would appear that in navigating between these two limitations, folksonomy sites place the cursor closer to the second limitation, by increasing the number of categories. This is made clear on del.icio.us.

What makes del.icio.us powerful is the uniqueness of the tagging process: to retain the contextual specificity of the tagging, the tagger is not offered all the tags available for tagging the same context, but only the intersection between the tags already issued and his own collection of tags (the term used to designate this intersection is "Recommended Tags"). This encourages the tagger to reuse his own tags; this favours a large number of categories. It has also been deemed fundamental by del.icio.us that the possibility of personalised and potentially idiosyncratic tagging behaviour be allowed for and encouraged. The Recommended Tags in del.icio.us thus replace the traditional compromise in classification theory between the need for simplifying harmonisations and truth to reality. By retaining a contextual and idiosyncratic anchorage for the tagging activity, the somewhat mysterious process of "emergence" has been relegated: as the site's founder noted, "classification will emerge from the totality of the tags, which have been imposed by the users."

The second characteristic is collaborative filtering (MALTZ, 2005). Instead of receiving a random guide to pages by simple co-occurrences calculated on the whole of the panel, the user receives first the content contributed by other users with a similar cultural profile. Thus, on the bookmark sharing site del.icio.us, the problem of tag distribution has been taken into account in accordance with a law of power. A user, Kiddphunk, has therefore set up a plug-in called "delicious discover"7 , which is designed to facilitate the connecting of the user with users who favour the same content, i.e., who share with him not popular links (links which many users have), but rare links. At the outer limit, his tool allows connection to be made with elective affinities, that is, the totality of the users who are the only ones who share precisely this link with him. In order to achieve this, a weighting system is used, according to rarity, for the content which each user has in common with him. His method aims to highlight, for each user, the type of content, known as the 'sweet spot', which is both widely unpopular yet really matter to him.

Social exploration: the discovery of the other and the meeting

Collaborative sharing does not have a lucid acceptation of cultural curiosity as its only interest. It sometimes spills over into a number of functions leading to connection with other individuals. This is sometimes explicit on certain folksonomy sites dedicated to meeting up. Hence, http://www.43things.com offers, on the basis of keywords entered in turn by skills seekers and suppliers (see above), to create a list of 43 things to do in your life, to discover what others want to do, to be in the same geographical area and to help each other. From this point of view taxonomy is an icebreaker (Brown), a support in social exploration, in the sense that it provides a filter, so that users can be sure of finding themselves in a relationship pre-defined on the basis of a reliable cultural profile. However, this possibility of meeting exists in more or less extensive ways on all the sites: on FlickR, users can associate themselves with interest groups; they can thus invite friends to see their private photographs. The link is not reciprocal: inviting a friend to view your photos that does not mean you can, in turn, access their private photographs.

The possibility of mutual contact is thus favoured by the alert device. We have just seen how, with FlickR, it is possible to subscribe to the updated collections of other users (only by invitation): this means that a user can keep up to speed with someone else's photographic activity. This is also the model used by Pandora, the music listening site: "As you listen (with iTunes, Winamp, Windows Media Player, or others), your tracks automatically appear in your online musical profile we call this 'scrobbling'. Explore custom recommendations and personalised radio, find your musical soulmates, discuss your favourite bands, and share your musical insights with friends, family, and the world!" These devices for making social exploration easier sometimes take on a comical appearance. For example, the creation of "Chinese portraits" of users has been implemented on del.icio.us, where they are identified by means of a mosaic of images. Extisp.icio.us8 (from the Latin word for divination by the inspection of entrails) allows you to view a mosaic of images drawn from Yahoo images on the basis of tag words used several times by a del.icio.us user.

No. 65, 1 st Q. 2007

As an extension, to facilitate meetings between users, certain folksonomy sites have set up a fun modalisation of their functions. Certain folksonomy sites are explicitly based on "modalisation" (in the sense used by [START_REF] Goffman | Les Cadres de l'expérience[END_REF] in the form of riddles of the labelling experience: the idea is not to apply tags to a resource, but to guess the tags which have been applied by someone else. For instance, Luis von Ahn developed a game 9 in which two people are simultaneously given an image of the same picture, with no way to communicate. The game has been licensed by Google in the form of the Google Image Labeler. When the user's label matches the partner's label, both will earn points and move on to the next image until the 90-second period runs out. The game keeps the high scores of registered users and these are displayed both for the day and for "all time"; Google is betting on users' competitiveness to rack up high scores to swell the number of images ranked. It is a clever way for Google to build an accurate database used when using the image search. Sometimes more sophisticated forms of fun framing of the relationship exist: on a site like Odeo, a podcast site, users face each other in the framework of a competition in which they try to build sentences in a cloud of tags, by shifting the tags and adding others and by changing the general order.

The articulation between social connections and semantic proximity

A number of studies have striven towards a better understanding of the articulation between social affiliations and the creation of a new vocabulary. For example, Marlow and Naarman chose at random 2,500 of the most intensive users on FlickR (those who had sent a number of over 100 tags). Using this sample of users, they tried to test out whether the fact of having contacts (they worked on contacts and not on membership of a group) influences the process of the formation of a vocabulary. In order to do this, they attempted to calculate the rate of shared tags (the number of common tags/the sum of their two groups of tags) between two users, a rate which could be called "overlap". They compared the overlap between two users chosen at random from this list, and the overlap between two users in contact. The overlap between two users in contact is higher than between two users chosen at random. Other observations can be made: the frequency of considerable overlap is significantly higher for users in contact 9 http://www.espgame.org/ than for two users chosen at random. There is therefore a relationship between social affiliation and the formation of the vocabulary of the tags. This type of study leads to the question of whether membership of a group of contacts is correlated to the existence of a common "sociolect". It again throws doubt on drawing too clear-cut a distinction between cultural exploration and social exploration. It would appear that cultural proximity is an important factor in social affiliation. Some additional studies would be appreciated, particularly to test whether it is pure resemblance which is a socially connective factor, or if, on the contrary, a small degree of dissimilarity helps guarantee a relationship. What would be a satisfactory level of dissimilarity supporting the best possibility of a sustainable relationship? From a broader viewpoint, diachronic studies would be needed to provide a better understanding of the direction of the influence between social relationship-establishing phenomena and cultural exploration phenomena: is it merely the case that an overlap between semantic proximity and social affiliation simply bears out the fact that it is easier to connect up with people who share your tastes? Would it be impossible to reveal a connection between a sustainable relationship and the diversification of the partners' semantic fields?

No. 65, 1 st Q. 2007

Even if they remain focussed on the provision of a variety of cultural and social exploration functions, folksonomies have more recently witnessed the development of unexpected functions. Aside from the diversity of their exploratory uses, a third type of unforeseen use appears to have established itself, deriving from users: the opinion poll. Thus Technorati displays as a matter of course the 250 most popular tags of the moment. Tag aggregators like Guten Tag 10 reveal the popularity of the words used as descriptors on other services. Using them, it is possible to calculate statistics on the popularity of tags deriving from a range of different sites. Del.icio.us displays the most popular sites of the day, or, via connected services (LiveMarks), the list of novelties published on del.icio.us. From a broader viewpoint, with viewing tools such as cloud of tags, the majority of these sites make it possible to show in a flash what a given grouping is thinking about at a given moment. The larger the tag, the more it is likely to mean that a large number of users have entered the tag. The folksonomy sites are therefore also indicators of opinion. However, there is a lack of reflexion on the amount of past time to consider so as to include an item in "dominant cultural climate." The difference between a transitory mode and a value is unclear in this counting of tags, so that we disagree with the aim of some folksonomies websites to qualify their results as a genius seculi, or to label their "cloud of most popular tags in the last week" with the hegelian word "Zeitgeist".

The governance of self-generated taxonomies

The folksonomy is often described in the literature as 'feral', that is, uncontrolled: WALKER, 2004;MARLOW et al., 2005. The main characteristic of these works is to highlight the emergency of taxonomies on the basis of the unique and unchecked entry of each user. A number of studies, which have often given rise to implementation in websites, have striven towards remedies with a view to the governance of self-generated taxonomies. They begin by identifying the main problems, then move on to the solutions intended to solve them.

Folksonomy suffers first and foremost from basic problems of polysemy and homonym management 11 : does a page indexed by 'java' refer to a style 10 http://gutentag.viabloga.com/ 11 It is not possible to talk about spelling problems or a lack of coherence in the choice made by users in the use of concatenations (some use a dash, others a slash, others nothing at all) as it of music, a programming language, or a town in Wyoming? Is a page bearing the tag 'glass' talking about the material, an object, or the expression 'to have a glass'? These homonymy problems are aggravated by the fact that the key words are often mixed up, as on Technorati. Folksonomy also suffers from the problem of synonymy. Multilingualism makes both problems worse: if a folksonomy site sees itself as international, not only does the number of tags explode because of the different translations, but at the same time very puzzling homonyms appearthe word pain means 'bread' in French! Does the key word 'cap', a cape in French, refer to the most beautiful geographical capes in the world, or to the English headgear? Language mixing, practised by Technorati, FlickR or del.icio.us, gives rise to a major problem, which can be regulated by adaptive behaviour on the part of the users. Moreover, will French web users, faced with the predominance of English terms in their indexes, be tempted to use English-language markers to avoid the problems of multilingualism, thus reinforcing the predominance of descriptors in English? But leaving aside these basic problems, folksonomy also suffers from a crucial problem: the lack of standardisation in the tagging process. What should one think of the tag 'music'? Does this refer to content of a professional nature (a studio, a label, a music vendor, etc), the lyrics of a song, a historic site, or just a music fan's site? And more generally, folksonomy says as much about people's ways of seeing and classification as it does about the content thus classified. There is no universality in the definition of 'basic terms', which would allow content to be labelled: two different people will have different opinions about the 'basic terms' of a piece of information 12 . A history of cats, for example, could be tagged differently by the participants according to their expertise: as cat, or as Persian or as Felis silvestris catus longhair Persian. Sub-populations of experts can operate at a more specific level than the basic level in their area of expertise. Another problem is that, depending on the organising principles for categories that people have in their heads, some will choose different markers to designate an object: thus, a photograph of a piano could have a tag 'grand' for an individual classifying the piano as a musical instrument, while it will be different for a person classifying it as furniture. The position of the user in the social space of taste leads to perception and categorisation would appear that standardisation faults can easily be rectified by a careful reading of the instructions. 12 For further light on the term universalist used to distinguish Rosch and Lloyd's theory of categorisation (1978), which postulates the existence of a 'basic level', see RASTIER (1991).

No. 65, 1 st Q. 2007

systems [START_REF] Bourdieu | La Distinction. Critique sociale du jugement[END_REF], which therefore transforms labelling. A final problem is that some users will want to apply a large number of tags, others few. [START_REF] Golder | Usage Patterns of Collaborative Tagging Systems[END_REF] revealed a sharp contrast between two sub-populations, one of which labels with on average very few bookmarks, while the other is more lax. It revealed a very high level of dissimilarity of practice. However, these governance problems should not be overestimated. The folksonomy sites are betting on emergence. They are counting on the fact that by self-organised aggregation, taxonomies will naturally emerge on the basis of these decentralised contributions. Some studies have revealed empirical evidence in this sense. [START_REF] Golder | Usage Patterns of Collaborative Tagging Systems[END_REF], for example, have shown how swiftly a tag system can stabilise itself, with the frequency of appearance of a tag increasing when a piece of content is frequently referred to a fixed value. This is a very important phenomenon: consensus is tacitly formed without the direct wish of a higher authority. Tag convergence takes place when a reference becomes increasingly popular. [START_REF] Golder | Usage Patterns of Collaborative Tagging Systems[END_REF] observe that, on the basis of a relatively low number of citations for the same URL (100 bookmarks), the relative proportion of the different tags used to describe it stabilises, and becomes very stable. This is a very interesting result, which means that the reliability of labelling obtained via folksonomy is rather more optimistic. In actual fact, in the case of URLs cited more than 100 times, which is a low number, relative objectivity and labelling soundness already exists. Attempts at governance have been driven by the need to domesticate these feral taxonomies without throwing more doubt on what makes these folksonomies interesting: the principle of faithfulness to the real world and to systems of perception. How are the significance of a bottom-up (selforganising) model and the need for homogeneity to be reconciled? As long as folksonomy sites still retained community homogeneity they could do without such rules since the existence of the community was posited on the existence of similar thought and systems and hence the use of identical terms to designate identical things: the problem of the explosion in the number of tags, for a programmer community, means that the different meanings of the term 'java' have little importance when practically all requests for this tag relate to IT. And the negative 'meta noise' elements for the conoscenti are less to be found within communities, and where they are negative are easily identified and excluded.

No. 65, 1 st Q. 2007

A governance requirement

As these sites have become more popular, however, attempts at governance have been developed. MARLOWE et al. have identified a classification in the types of governance existing. Three can be distinguished:

 Opening up labelling rights: 'self tagging' and 'free-for-all tagging' are opposed. In the first case, the tags are made by the posters of content themselves (readers have no right to write: this is the case with FlickR). In the second case, the tags are open to the totality of the readers (readers have the right to write: this is the case with del.icio.us). Between these two extremes a variety of levels of compromise exist. Some systems, for example, may select the resources which the users are permitted to tag (the images in ESP Game, for example), while other systems grant permission according to category (friends, family or contacts). There are also systems that authorise certain sub-populations to remove a tag. The management of tagging rights may explain the large differences between these systems.

 Support for tag writing: 'Blind tagging' is opposed (users are unable to see the tags assigned to the same resource by other users, as in del.icio.us) and 'viewable tagging' (users are able to see the tags already associated with a resource). Between these extreme positions lies 'suggestive tagging' (possible tags are suggested to a user). The creation of suggestions is a powerful convergence factor [START_REF] Golder | Usage Patterns of Collaborative Tagging Systems[END_REF]. FlickR assists the user when he enters his second tag on the same photograph, by informing him of the tags occurring along with the first tag he entered Del.icio.us offers an intersection between others' tags and the tags already placed by the tagger.

 A third important characteristic is the aggregation of tags for a given resource. Naturally, the two models can be placed in opposition, the bag model in which users are authorised to place a large number of tags for one resource; and the set (type FlickR) model, in which syntactic constraints and number limitations exist. These types of practice make for a clear distinction from the selfmanaged taxonomy sites. Thus it can be seen that del.icio.us is a free-for-all system, suggestive, and resting on the model of the bag. Conversely, FlickR is a self-tagging system, blind to the first tags and viewable for the second tags, and above all based on the overall restriction model. What heuristics can be suggested to introduce greater objectivity into tagging practices? Three classes of heuristic can be distinguished.

An initial category of studies seeks to allow the users to operate at their liberty and to organise the viewing of their results by clustering by displaying the hierarchies between the tags. For this reason FlickR has recently introduced the idea of 'tag clusters', a first step towards a way of hierarchically arranging key words. For example, the term 'jaguar' brings up a page offering several groups, one a collection of cats, another of British cars and a third of French fighter aircraft. In the same vein is the site fac.etio.us, a search tool which offers an alternative presentation of the content of del.icio.us, organised in line with a more structured classification system. Fac.etio.us is a plug-in whereby it is possible to add some degree of organisation into the 'flat' system of collaborative tags; it introduces facets according to the genre of the tag: fac.etio.us is a reworking of the del.icio.us database, which makes use of faceted classification, grouping tags under headings such as 'by place' (Iraq, USA, Australia), 'by technology' (blog, wiki, website) and 'by attribute' (red, cool, retro). HEARST ( 2006) is working on faceted taxonomy systems (which blend hierarchical categorisation with clustering).

Other studies emphasize the need to train users. This work concentrates on the need to orient them in the direction of a syntax. One result from Ulises Ali MEJIAS (a student who undertook an interview-based study, although based on too small a panel) is that the mixing of ultra-specific tags and general tags is an effective means of retaining the uniqueness, which lies at the heart of the richness of del.icio.us and ensures that the taggings remain comprehensible. To improve the pertinence of the emission of tags, most websites let their users to pass through funny helps, which let them integrate the minimal rules of tagging.

Algorithms for quality recommendation and convergence

A third modality for regulating the self-generated taxonomies exists. This is by the design of the recommendations (viewed by the writer of a tag before he enters its own) that the system should be led towards the production of more relevant tags. [START_REF] Shen | Tagging, communities, vocabulary, evolution[END_REF] have undertaken a study on a folksonomy site dedicated to cinema, which indexes movies 13 . In order to fully appreciate the results of their work, we must understand that they were provided in advance with a quality criterion of a folksonomy

Conclusion

Folksonomy is a fundamental movement that expands the collaborative process, by allowing contributors to index content. It rests on three powerful properties: the absence of a prior taxonomy, multi-indexation and the absence of thesaurus. It concerns a more exploratory search than an entry in a search engine. Its original relationship-based structure (the three-way relationship between users, content and tags) means that two forms of results can be used that relate back to different social usages: cultural exploration and social exploration. Since labelling lacks any standardisation, folksonomies are often under threat of invasion by noise. Systems of governance have been set up to combat this threat based on three different formats. Firstly, systems of visualisation have attempted to reinstate a form of hierarchy-driven labelling by ascending breakdown. Secondly, user training, sometimes by way of a game, has aimed to lead users towards greater objectivity. However, it would appear that the most advanced forms of governance are by way of controlling recommendation algorithms. A judicious choice of these algorithms allows for great objectivity, or at least greater stability, in the self-organised aggregation of the individual labels.

Fig. 1 -

 1 Fig. 1 -"Structure of indexing systems" (from VOSS, 2006)

Figure 3 -

 3 Figure 3 -the Pandora Music website

Figure 4 -

 4 Figure 4 -Vocabulary overlap distribution for random users and contacts (n=2500)

Fig. 5 -

 5 Fig. 5 -Two extreme users (#565, #635) tag growth (*)

Figure 6 -

 6 Figure 6 -The stabilization of tag's relative proportions (from GOLDER & HUBERMAN, 2006)

Some writers also use the terms "potonomy" and popular "taxonomy".

As evidence of their success, clones of each of these sites developed, shown by the numerous offspring spawned by delicious, of which the most well-known, del.irio.us, an open source version of del.icio.us, has not survived. But others have, such as BlogMarks, a similar service but restricted to French language content, or Connotea, dedicated to a precise subject area, in this case, that of science.

It is, of course, possible to proceed in the same way in 'broad' folksonomy systems, but the results do not have the same level of relevance.

The grouping would in particular appear to be the attraction of the killer interactive environment which Ludicorp has created for FlickR.

By way of an extension of Vander Wal's argument, certain interpreters have forced the opposition: thus, LE DEUFF (2006) infers from Vander Wal's dichotomy a different distinction, namely that narrow folksonomies, focused on content, would be primarily used in an individual objective (to describe them he uses the term personomy), while the broad, focused on other users, would favour the collective and collaborative aspect. This extremist dichotomy is open to doubt.

http://www.hyperorg.com/blogger/mtarchive/003702.html#comments

http://www.mandalabrot.net/delicious/

http://kevan.org/extispicious

The website is stored on the server of their original institution, the University of Michigan: http://movielens.umn.edu

No. 65, 1 st Q. 2007

website. This criterion has the following definition. Following the classification made by MARLOW et al. (2006), they arrange the tags in three classes: factual tags (item topics, kinds of item, category refinements), subjective tags (express user opinions, evaluations), and personal tags (which have an intended audience of the tag applier himself: task organisations, self-reference, item ownership). On the basis of this categorisation system, they construct quality criterions for a folksonomy system. A first quality criterionwhich we could name a "substantial" criterion-relates to the proportion of factual tags on the whole: the factual tags are more easily understood and indicate a respect of objectivity criterions; the higher the proportion of them, the better the system is able to generate common knowledge. A second quality criterion, which could be called procedural, concerns the stability over time of the distribution between the three classes of tags: when the proportion stabilizes over time, the authors consider that this indicates a system reaching quality.

The interest of the study of [START_REF] Shen | Tagging, communities, vocabulary, evolution[END_REF] is related to the fact that the authors are also the conceptors of the movie indexation website, which led them to program different recommandations vizualisation systems. They presented four different experimental panels: the unshared group (no tags are shared between members), the shared group (saw tags applied by other members of their group to a given movie), the shared-pop group (saw only most popular tags, i.e. those applied to the item by the greatest number of persons) and the shared-rec group (saw only tags applied to both the target item and to the most similar items to the target item; similarity between a pair of items was defined by the cosine similarity of the ratings provided by the users). The final tag class distributions between those four experimental groups were very different. The shared-pop and the shared-rec groups were dominated by factual tags, the shared group by subjective tags while the unshared group was divided more evenly. The most interesting result is that the tag selection algorithms have a major impact on tag class distribution.

Moreover, the authors looked at whether tag class distributions converged quickly or slowly: again, the shared-pop and the shared-rec converged, when the shared and unshared had less visual evidence of convergence: they were drifting. As a matter of fact, the shared-rec and shared-pop displayed algorithms that favoured tags applied by many different people, and those tend to be factual in nature (80% of tags applied by five or more people are factual). The third result was that the shared-pop and shared-rec groups had the greater number of tags. It can thus be seen that the choice of a precise selection algorithm for proximity criteria and popularity criteria is better if the group is oriented towards quality.


Pierre Michaud
email: pierre.michaud@inria.fr

Replacement policies for shared caches on symmetric multicores : a programmer-centric point of view

Keywords: C.1.2 [Processor Architectures]: Miscellaneous Symmetric multicore processor, quality of service, self-performance, shared cache, replacement policy, memory bandwidth

The presence of shared caches in current multicore processors may generate a lot of performance variability in multiprogrammed environments. For applications with qualityof-service requirements, this performance variability may lead the programmer to be overly pessimistic about performance and reduce the application features and/or spend a lot of effort optimizing the algorithms. To solve this problem, there must be a way for the programmer to define a reasonable performance target and a guarantee that the actual performance is very unlikely to be below the targeted performance. We propose that the performance target be defined as the performance measured when each core runs a copy of the application, which we call self-performance. This study characterizes self-performance and explains how the shared-cache replacement policy can be modified for selfperformance to be meaningful.

INTRODUCTION

There exists an implicit contract between the programmer and the processor. When a programmer writes a program for which performance matters and evaluates performance by running the program, he often assumes that performance is deterministic, hence reproducible. Actually, there can be some performance variability, some due to the operating system, some due to the runtime system. But this performance variability can generally be tackled in software (e.g., by minimizing the number of system calls, by choosing the appropriate programming language, etc.). With multicore processors able to execute several applications simultaneously, performance variability may stem from the sharing of microarchitectural resources by several applications running concurrently. Shared caches, for instance, are among the microarchitectural resources that incur the most performance variability. But the programmer has little control on this performance variability. Moreover, the microarchitecture of today's processors is not always documented and it is difficult for the programmer to understand what is happening.

Depending on workload characteristics, the actual performance of a particular application may be much smaller than the performance measured at programming time. For applications with quality-of-service requirements (e.g., a video decompressor), this may lead the programmer to be overly pessimistic about performance and reduce the application features and/or spend a lot of effort optimizing the algorithms.

Previously proposed solutions to this problem involve the use of programmable priorities or quotas [START_REF] Kim | Fair cache sharing and partitioning in a chip multiprocessor architecture[END_REF][START_REF] Iyer | CQoS : a framework for enabling QoS in shared caches of CMP platforms[END_REF][START_REF] Rafique | Architectural support for operating system-driven CMP cache management[END_REF][START_REF] Guo | From chaos to QoS : case studies in CMP resource management[END_REF][START_REF] Nesbit | Virtual private caches[END_REF][START_REF] Guo | A framework for providing quality of service in chip multiprocessors[END_REF][START_REF] Iyer | QoS policies and architecture for cache/memory in CMP platforms[END_REF]. With these solutions, programmers who want a performance guarantee must ask for resources they are sure to obtain. In practice, this requires either to partition shared resources evenly between cores or to keep some cores unused.

We propose a new solution to this problem, which is to have an explicit contract between the programmer and the microarchitecture. The programmer measures the application performance by running simultaneously a copy of the application on each core. This defines what we call selfperformance. This study characterizes self-performance and shows that, for self-performance to be meaningful, the microarchitecture must manage shared resources carefully. In particular, we show that conventional cache replacement policies are not compatible with the self-performance contract. We propose some replacement policies that are compatible with self-performance.

The paper is organized as follows. Section 2 explains the concept of self-performance and the motivations behind it. We show in Section 3 that conventional cache replacement policies are not compatible with self-performance and we provide insights as to why this is so. We also show that, even without considering the self-performance contract, conventional cache replacement policies lead to the paradoxical situation that increasing the memory bandwidth may decrease the performance of some applications. In Section 4, we propose sharing-aware replacement policies that solve the problems emphasized in the previous section. Section 5 discusses some implications of our proposition. Finally, Section 6 concludes this work.

Simulations.

The simulation results presented in this study correspond to a simulated multicore with 4 identical cores, depicted in Figure 1. The 4 cores share a 4 MB 16-way set-associative level-2 (L2) cache. The main characteristics of the simulated 1. Our simulator is trace-driven, using traces generated with Pin [START_REF] Luk | Pin : building customized program analysis tools with dynamic instrumentation[END_REF]. We obtain one trace for each CPU 2006 benchmark 1 . To obtain each trace, we run the application without any instrumentation for 30 seconds, then we send a signal that triggers instrumentation. More details about our approximate simulation methodology can be found in [START_REF] Michaud | Replacement policies for shared caches on symmetric multicores: a programmer-centric point of view[END_REF]. We denote each SPEC CPU2006 benchmark by its SPEC number. Unless stated otherwise, each simulated IPC (instructions retired per cycle) reported in this study corresponds to the IPC of the thread running on core #1 for 10 million CPU cycles while other threads run on cores #2,#3 and #4.

SELF-PERFORMANCE

In this study, we consider independent sequential tasks. Though it is hoped that more and more parallel applica-1 Except 481.wrf, that we could not compile.

tions will be developed, sequential programming is still very important. We explain in Section 5.3 what are the implications of our proposition for multi-threaded programs.

The problem

For applications with quality-of-service (QoS) requirements, it is important that performance measured at programming time be deterministic, or close to deterministic. In a multicore, several resources are shared : physical memory, caches, buses, power supply, etc. Because of resource sharing, when several independent applications run concurrently on different cores, the performance of each application depends on the characteristics of the other applications. On a single CPU, the operating system (OS) can control the amount of physical memory and CPU time allotted to each task, in particular tasks with QoS requirements. On a multicore, the operating system can decide which applications to run simultaneously and for how long, but it has no control on microarchitectural resource sharing. The notion of CPU time is not accurate, as the quantity of work done during a fixed period of time may vary drastically depending on resource sharing. What we need is a way for the programmer to specify a performance target and a microarchitecture that minimizes the possibility for the actual performance to fall significantly below the performance target. An obvious solution would be to assume that the application runs alone on the multicore. But the multicore would be underused.

The solution that has been proposed so far is to let the OS have a fine control of shared microarchitectural resources [START_REF] Kim | Fair cache sharing and partitioning in a chip multiprocessor architecture[END_REF][START_REF] Iyer | CQoS : a framework for enabling QoS in shared caches of CMP platforms[END_REF][START_REF] Rafique | Architectural support for operating system-driven CMP cache management[END_REF][START_REF] Guo | From chaos to QoS : case studies in CMP resource management[END_REF][START_REF] Nesbit | Virtual private caches[END_REF][START_REF] Guo | A framework for providing quality of service in chip multiprocessors[END_REF][START_REF] Iyer | QoS policies and architecture for cache/memory in CMP platforms[END_REF]. Each shared resource is associated with priorities or quotas that are programmable. For example, the programmer defines his microarchitectural needs, i.e., the resources he wants (cache size, bus bandwidth, etc.), and the OS tries to give to each application the requested resources. However, this raises a question : what if the sum of resources requested by applications running concurrently exceeds the processor's resources ? With programmable quotas, each application is given a share of resources that is a function of, but is not necessarily equal to, what the application requests [START_REF] Rafique | Architectural support for operating system-driven CMP cache management[END_REF]. This implies that the applications for which it is important to obtain a performance guarantee must ask for quotas that they are sure to obtain. In practice, this means that when a resource is shared by up to N threads, the programmer must ask for 1/N (or less) of the resource in order to obtain a performance guarantee.

Based on this observation, we propose a viable alternative to programmable quotas2 . We call it self-performance. Self-performance is less flexible than programmable quotas but we believe it is simpler for the programmer and more practical.

Self-performance

Obtaining a performance guarantee is a two-stage problem :

• We need a way to define a performance target.

• We must minimize the possibility for the actual performance to fall below the targeted performance.

On the one hand, we do not want the performance target to be too pessimistic. On the other hand, the performance target must be a value that is possible to enforce. If it is too optimistic, it may be impossible to reach the performance targets of all the applications running simultaneously. If we measure the application performance when it runs concurrently with some random applications, we may obtain a performance target that is too optimistic. If we choose misbehaving applications to stress shared resources, we may obtain a performance target that is too pessimistic. Instead, we propose to define the performance target of an application by running copies of this application on all cores. More precisely, we define the self-performance contract as follows :

The self-performance of a sequential program on a symmetric multicore processor is the performance measured for one instance of the application on a symmetric run, i.e., when running simultaneously and synchronously copies of that program on all cores, using the same inputs. The actual performance must be greater than or close to the self-performance, whatever the applications running on the other cores.

The rationale is as follows. If the application uses few resources, its self-performance is very close to the performance when it runs alone. But if the application asks for a lot of resources, it competes with copies of itself and gets a share that is equal to the resource size divide by the number of cores. The performance target defined this way is neither too optimistic nor too pessimistic. Self-performance can be measured by the programmer without requiring any knowledge of the internal microarchitecture details (e.g., which resources are shared, how the resource arbitration works, etc.). The programmer does not even need to know the number of cores. The only thing that the programmer must be aware of is the self-performance contract. For the convenience of the programmer, the OS should provide a selfperf utility for launching symmetric runs. Programmers who do not need a performance guarantee can measure performance as usual, without using the selfperf utility. But it is an optimistic performance in this case.

System resources.

In this study we focus on shared microarchitectural resources, and more particularly shared caches. We do not address the problem of system resources, like physical memory. For example, if the programmer has QoS constraints and wants a high self-performance, he should prevent the application memory demand from exceeding the memory size divided by the number of cores. We assume that the OS is always able to give this amount of memory to the application.

SHARED CACHES AND SELF-PERFOR-MANCE

Unlike for system resources, the operating system has little control on shared microarchitectural resources. It is possible to have some control by carefully choosing which application to run simultaneously (provided such choice exists). But, to our knowledge, existing processors do not allow the OS to control microarchitectural resources more finely.

Among shared microarchitectural resources, caches exhibit the most chaotic and hard-to-predict behavior. For example, on a set-associative cache with least-recently-used (LRU) replacement, a small decrease of the number of cache entries allotted to a thread may result in the miss ratio suddenly going from 0 to 100%. The most obvious way to avoid the erratic behaviors due to shared caches is to avoid shared caches. Nevertheless, shared caches have some advantages. On a multicore with private caches, whenever a single thread is running, the cache capacity of idle cores is generally wasted. When a cache is shared between several cores, the whole cache capacity is accessible to a single running thread. This is particularly interesting for the last on-chip cache level, as off-chip accesses are costly in performance and energy. There are other advantages when several threads from the same application communicate with each other. With private caches, several copies of the same data may be replicated. Not only does this decrease the effective cache capacity, but this means potentially a cache miss for each copy. For these reasons, several recent multicores have shared level-2 (L2) or level-3 (L3) caches. However, to our knowledge, there is no mechanism in these multicores to control the way the cache capacity is partitioned between different threads running concurrently. The partitioning is simply the result of the cache replacement policy, that is why we call it natural partitioning in this study.

Under natural cache partitioning, self-performance can exceed actual performance

The model of cache partitioning proposed in [START_REF] Stone | Optimal partitioning of cache memory[END_REF], though inaccurate in practice, is useful for understanding some qualitative aspects of natural cache partitioning. We present a simplified version of the model, which we will use to help understand our simulation results.

Let us consider n threads numbered from 1 to n running simultaneously, and a fully-associative shared cache with a capacity of C blocks. The number of cached blocks belonging to thread i is wi. It is assumed that the cache capacity is saturated, i.e., C = P n i=1 wi. The miss rate of thread i, in misses per cycle, is mi. The total miss rate is m = P n i=1 mi. The model assumes that, on a miss from any thread, the probability that the victim block belongs to thread i is proportional to the total number of cached blocks belonging to thread i, i.e., it is wi/C. During T cycles, miT blocks from thread i are inserted in the cache and mT × wi/C blocks from thread i are evicted from the cache. It is assumed that an equilibrium is eventually reached, such that wi is stable. It means that, for each thread, the number of block insertions equals the number of block evictions. Hence we have miT = mT × wi/C, that is,

mi wi = m C (1)
This quantity, mi/wi, was not identified in [START_REF] Stone | Optimal partitioning of cache memory[END_REF]. We call it the cache pressure of thread i. Equation (1) means that the equilibrium partitioning is such that all threads have equal cache pressure. Figure 2 shows on an example how the concept of cache pressure is useful for finding the equilibrium cache partition from the threads miss rate curves (misses per cycle as a function of the number of cached blocks). On this example, the cache is shared between 2 threads. Thread 1 needs less than half the cache capacity to have a null miss rate. However, because it shares the cache with thread 2, thread 1 has a non-null miss rate. The example of Figure 2 explains why natural cache partitioning cannot guarantee that the actual performance will reach the self-performance target. In particular, the performance of a thread may be severely decreased when the other threads have high miss rates.

Experiment on a real multicore.

We did a simple experiment on a MacBook Pro featuring an Intel Core 2 Duo processor and 2 GB of memory. This processor has 2 cores and a 4 MB shared L2 cache. We ran benchmark vpr from the SPEC CPU2000. The measured execution time was approximately 51 seconds. Then we measured the self-performance of vpr by running simultaneously two instances of vpr. The execution time of vpr was 53 seconds, which means that the self-performance of vpr is close to its performance when it runs alone. Then we ran vpr simultaneously with benchmark mcf from the SPEC CPU2000. The execution time of vpr was 73 seconds, i.e., 38% worse than the self-performance. Then we ran vpr simultaneously with a microbenchmark that we wrote and which we denote 999. Microbenchmark 999 is provided in Figure 3. It has a very high miss rate (1 miss every 4 instructions) and evicts cache blocks very aggressively. The execution time of vpr was 101 seconds, i.e., 90% worse than the self-performance. We used the Apple tool shark to access the performance counters of the Core 2 Duo and we checked that the decrease of performance comes from an increase of L2 cache misses. This experiment shows that, under natural cache partitioning, the actual performance may be significantly smaller than the self-performance.

Self-performance is not always defined under natural cache partitioning

In our definition of self-performance, we made the implicit assumption that, on a symmetric run, performance is the same on all cores. With identical cores, this is indeed the case most of the time. According to the cache pressure model (cf. Figure 2), if threads have the same miss rate curve, they should get the same share of the cache capacity. Therefore, a symmetric run on 4 cores should result in each thread getting one fourth of the cache capacity. However, the cache pressure model is only an approximation of reality. It is useful for explaining certain qualitative phenomena, but it makes no assumption on the replacement policy and therefore cannot model policy-dependent behaviors.

i n t a [ SIZE ] ; main ( ) { i n t i , n ; i n t x = 0 ; f o r ( n=0; n < 1 0 0 0 0 0 0 ; n++) { f o r ( i =0; i <SIZE ; i+=STEP) { x += a [ i ] ; } } p r i n t f ( "%d\n " , x ) ; }
Empirically, from our experiments and simulations, we believe that LRU is unlikely to generate strange performance variations on symmetric runs. But this is not necessarily the case with other replacement policies. Though we present results only for LRU in this study, we also did simulations with a variant of the DIP replacement policy where each core has a distinct PSEL counter.

DIP was recently proposed as an improvement over LRU for L2 and L3 caches [START_REF] Qureshi | Adaptive insertion policies for high performance caching[END_REF]. DIP (or DIP-inspired policies [START_REF] Jaleel | High performance cache replacement using re-reference interval prediction (RRIP)[END_REF][START_REF] Michaud | The 3P and 4P cache replacement policies[END_REF]), is likely to be implemented in future processors. All our observations and conclusions with LRU are the same with DIP, except that natural cache partitioning under DIP may lead to strong performance asymmetry on symmetric runs. We found that natural cache partitioning does not always guarantee that a symmetric run leads to a balanced cache partitioning.

Figure 4 shows the result of running 4 instances of microbenchmark 999 compiled with SIZE = 2 19 (cf. Figure 3) when the L2 replacement policy is DIP and the memory bandwidth is 4 bytes per cycle. The plot shows the number of retired instruction on each core as a function of time. Despite cores being identical, this example exhibits a strong performance asymmetry, the performance of core #3 being higher than the other cores. Our simulator uses a pseudorandom number generator (RNG), which is used in the DIP policy and in the bus arbitration policy. Actually, the leading core varies with the RNG seed. This phenomenon can be explained as follows. From the cache pressure model, we expect threads with identical miss rate curves (in particular identical threads) to converge to a state where the shared cache is equally partitioned. The reason is that there is a negative feedback at work : the more cached blocks belong to a given thread, the higher the probability for that thread to have its blocks evicted. Though we have no formal proof, a negative feedback seems to be at work with the LRU policy. Under LRU, we did not encounter a single example of a symmetric run leading to significant performance asymmetry. DIP may have a completely different behavior. DIP is based on a Bimodal Insertion Policy (BIP). With BIP, a block inserted in the cache recently has a high probability to be the next victim. It will be the next victim if it is not re-referenced before the next cache miss (from any thread). 3). Memory bandwidth is 4 bytes/cycle and the L2 replacement policy is a variant of DIP (one PSEL counter per thread). The plot shows the number of retired instructions on each core as a function of time.

In such case, BIP has a tendency to evict blocks belonging to the thread with the highest miss i.e., on a symmetric run, the thread with the smallest number of cached blocks. Hence we have a positive feedback where small divergences get amplified with time. This is a case of sensitivity to initial conditions. Such chaotic behavior is a priori incompatible with providing a performance guarantee. The SAR policies proposed in Section 4 solve this potential problem.

A symmetric run is not equivalent to a static partitioning of shared resources

One of our counter-intuitive findings is that self-performance is not exactly the performance one would measure with programmable quotas by partitioning each resource statically and equally between cores. Actually, when memory bandwidth limits performance, self-performance exceeds the performance of a single run with statically partitioned resources.

Figure 5 shows the IPC (instructions retired per cycle) for a subset of our benchmarks whose performance is limited by memory bandwidth. For each benchmark we show results for 4 configurations, where SGL denotes isolated runs (i.e., there are 3 idle cores) and SYM denotes symmetric runs. SGL-1 is for a memory bandwidth of 1 byte per CPU cycle and a 1 MB shared cache. SYM-4 is for a bandwidth of 4 bytes/cycle and a 4 MB cache. SGL-2 is for a memory bandwidth of 2 byte per CPU cycle and a 1 MB shared cache. SYM-8 is for a bandwidth of 8 bytes/cycle and a 4 MB cache. The shared-cache associativity remains constant and equal to 16. As can be seen the performance of SYM-4 is higher than the performance of SGL-1, and the difference is not negligible (23% for 429.mcf). A similar conclusions holds for SYM-8 versus SGL-2, but the difference is less pronounced. The explanation of these counterintuitive results lies in memory bandwidth sharing. This is illustrated in Figure 6 with an artificial example. With our definition of a symmetric run, copies of the same program are run synchronously, meaning that they are launched at the same time. However in practice, the execution on the different cores is not exactly synchronous. In fact, perfect synchronization would be very difficult to obtain and would actually decrease self-performance. Perfect synchronization implies that if we launch the program copies exactly at the same cycle, they should finish exactly at the same cycle. But even when all cores have exactly the same microarchitectural state at the beginning of the symmetric run, and assuming the microarchitecture behavior is deterministic, the program copies do not finish exactly at the same time because certain shared resources cannot be accessed by all threads simultaneously. Consequently, there is a slight desynchronization of cores on a symmetric run. Because cache misses are often bursty, a slight desynchronization permits obtaining a more uniform utilization of the bus bandwidth. This is what Figure 6 illustrates.

Increasing memory bandwidth may decrease performance.

Once there is an agreement between the programmer and the microarchitect that self-performance represents the minimum performance, the microarchitect must try to minimize the possibility of this not being the case. For the microarchitect, this means a special attention to each shared resource. In our simulations, only two resources are shared : the L2 cache and the bus bandwidth. The focus of this study is the cache replacement policy. But for our results to be meaningful we had to be careful with the cache indexing and with the bus arbitration policy.

L2 and L3 caches are generally indexed with physical addresses. On a symmetric run, physical indexing utilizes cache sets more uniformly than virtual indexing, so selfperformance is likely to be higher than what would be measured by partitioning the cache statically and equally between cores. We already observed an analogue phenomenon with memory bandwidth in Section 3.3. However, it is difficult to exploit this phenomenon in the cache without sacrificing the performance guarantee. The self-performance would be too optimistic. Instead, the OS should implement a page coloring scheme such that the cache indexing is equivalent to using the virtual address3 . Our simulations in this study assume a virtual indexing.

As for the bus arbitration policy, we initially implemented a simple least-recently-selected (LRS) scheme, which we thought would be sufficient. The LRS arbiter selects, among nonempty request queues, the least recently selected one. LRS arbitration is commonly used for arbitrating resource conflicts between threads in some multi-threaded processors like the Sun UltraSPARC T1 [START_REF] Kongetira | Niagara: a 32-way multithreaded Sparc processor[END_REF]. But we found that, when LRS is used for the bus, we cannot guarantee self-performance. To see why, consider the case of an application with a low average miss rate but whose misses occur in bursts. On a symmetric run, the desynchronization of cores permits avoiding most bus conflicts (cf. Figure 6). But when the application is run simultaneously with threads having a high average miss rate, it is granted bus access again only after each of the competing threads has accessed the bus once. Thus the application suffers from bandwidth saturation despite having a low average miss rate. To solve this problem, we have implemented a different bus arbitration policy. We associate a 4-bit up-down saturating counter with each request queue. This counter represents a score. To select which queue should access the bus, the arbiter chooses, among non-empty queues, the one with the lowest score. If a selection occurs (at least one queue is not empty), the score of the selected queue is incremented by X, where X is the number of running threads minus one (X = 3 in this study), and the score of each non-selected queue is decremented by 1. With this arbitration policy, an application with a low average miss rate has a low score and its requests can access the bus quickly even if the other threads have a high miss rate.

Figure 7 shows the IPC on core #1 when the 3 other cores run a copy of the benchmark (symmetric run) and when Figure 7: IPC for a subset of our benchmarks. The benchmark is run on core #1. Two workloads are considered for the 3 remaining cores : workload SYM runs a copy of the benchmark on each core (symmetric run) and workload 999 runs a copy of microbenchmark 999 on each core. For both workloads, we show the IPC when memory bandwidth is 4 bytes/cycle (SYM-4 and 999-4) and when it is 8 bytes/cycle (SYM-8 and 999-8).

they run instances of microbenchmark 999. In both cases, we show the IPC when memory bandwidth is 4 bytes/cycle (SYM-4 and 999-4) and when it is 8 bytes/cycle (SYM-8 and 999-8). We show results only for benchmarks whose performance suffers from running simultaneously with microbenchmark 999. As can be seen, the actual performance can be much smaller than the self-performance. This is particularly striking for 403.gcc and 435.gromacs. For 403.gcc, the actual performance can be 6 times worse than the selfperformance.

Another striking observation is that increasing the memory bandwidth can decrease the performance of an application. For example, when running with microbenchmark 999, 435.gromacs experiences a 16% performance drop when memory bandwidth goes from 4 to 8 bytes/cycle. By limiting the rate at which blocks can be evicted from the cache, a smaller bandwidth offers a better protection against aggressive cache evictions, but only to a certain extent. The cache pressure model confirms this observation. On Figure 8, we consider a thread #1 with a working set of W1 blocks and a miss rate curve that drops suddenly when W1 blocks are cached. The bandwidth is B (maximum number of misses per cycle). If the other threads are able to saturate bandwidth, the cache pressure is B/C (cf. equation ( 1)) and the miss rate of threads #1 is m1 = W 1 C B . If we increase bandwidth B, we increase cache pressure and the miss rate of thread #1, hence we decrease thread #1 performance.

This situation where an obvious structural improvement (making the bus wider or faster) may decrease the performance of an application is not a healthy situation. The microarchitect does not expect an application to experience a slowdown when memory bandwidth is increased.

SHARING-AWARE REPLACEMENT PO-LICIES

Sharing-aware replacement (SAR) is intended to solve the problems highlighted in Section 3.

The basic idea of SAR is to take into account the cache space occupied by each thread. This requires that a thread identifier (TID) be stored along with each block in the cache. For instance, with 4 logical cores, each TID is 2-bit wide. We say that a TID is inactive if there are fewer running threads than logical cores and the TID does not correspond to a thread currently running (an inactive TID typically corresponds to a thread that has finished execution of that is waiting for an event or a system resource). A SAR policy selects a victim block as follows :

• Each TID proposes a potential victim block in the cache set.

• The SAR policy selects a victim TID and the actual victim block is the victim block proposed by the victim TID.

• If the cache set contains some blocks belonging to an inactive TID, such inactive TID is chosen as the victim TID.

The last point is for being able to exploit the full cache capacity when there are fewer running threads than cores The implementation of the first point (having each thread proposing a potential victim block) is very dependent of the underlying replacement policy. A SAR policy requires little storage overhead compared to a conventional policy. For instance, SAR policies based on a LRU stack, like DIP [START_REF] Qureshi | Adaptive insertion policies for high performance caching[END_REF], or those based on the Not-Recently-Used (NRU) policy, like DRRIP [START_REF] Jaleel | High performance cache replacement using re-reference interval prediction (RRIP)[END_REF], do not require any extra storage apart from perblock TIDs. The victim selection logic, though, is slightly more complex. SAR policies based on CLOCK [START_REF] Zebchuk | Re-examining cache replacement policies[END_REF][START_REF] Michaud | The 3P and 4P cache replacement policies[END_REF] require one clock hand per thread and incur some storage overhead.

In this study, we assume LRU SAR policies : the potential victim block for a thread is the least-recently used among blocks belonging to that thread. The SB policy makes the worst-case performance (999) close to self-performance (SYM). The B2 policy, simpler than SB, is almost as effective.

The SAR SB policy

A possible solution for ensuring that a thread gets the cache space it would get on a symmetric run is to give the same amount of cache space to each thread. This can be done by choosing as victim TID the TID with the largest number of cached blocks. In case of equality, we choose the TID whose proposed victim is closest to the LRU position. Such policy should progressively converge to an equilibrium partition where all threads get an equal share. There are two possible options. The number of blocks may be computed either for the whole cache or just for the cache set. We denote the first policy global-biggest (GB), and the second one set-biggest (SB). The GB policy chooses as victim TID the TID with the largest number of blocks in the whole cache, while the SB policy chooses as victim TID the TID with the largest number of blocks in the cache set where the missing block goes. The GB policy can be implemented by maintaining 4 counters giving the total number of blocks belonging to each thread. On a miss, one or two counters are updated. The SB policy can be implemented by counting blocks on-the-fly while the miss request is being processed 4 .

Simulation results for the SB policy are shown in Figure 9. The SB policy is successful in making worst-case performance close to self-performance. This was expected, as the SB policy converges relentlessly to a state where each cache set is evenly divided between competing threads. Actually, we found that the GB policy is not safe and we do not show results for it. We have mentioned it just to emphasize the necessity of working at the set level. The main reason why the GB policy is not safe is that it does not guarantee that each cache set is evenly divided between threads. Indeed, some applications do not use cache sets uniformly. For example, we simulated benchmark 429.mcf with 3 instances of microbenchmark 999 compiled with ST EP = 32, i.e., using only even cache sets. With a GB policy, the performance of 429.mcf is 22% lower than the self-performance. The fact that one must work at the set level to obtain a performance guarantee has already been observed in [START_REF] Rafique | Architectural support for operating system-driven CMP cache management[END_REF].

The SAR B2 policy

The SB policy requires to find the TID that has the most blocks in a set. With 4 cores, this requires 3 comparisons. We propose a simpler SAR policy, that we call biggest-of-two, or B2 for short. Like the SB policy, the B2 policy counts how many blocks belong to each thread among the 17 blocks (16 blocks in the cache set, plus the missing block).

While processing the cache miss, the B2 policy chooses a random block in the cache set. The TID of this block is denoted the random TID. The TID of the missing block is denoted the missing TID. The B2 policy chooses the victim TID between the missing TID and the random TID, choosing the one that has the largest number of blocks among the 17 blocks. In case of equality, the random TID is chosen as victim TID. In other words, the victim is the random TID unless the missing TID has more blocks in the sets. Unlike the SB policy, on a 4-core processor, the B2 policy requires a single comparison. Counting blocks may not be necessary if we have a circuit that compares two 17-bit vectors and tells which one contains the most 1's.

As can be seen in Figure 9, the B2 policy is practically as effective as the SB policy.

IMPLICATIONS

Programmable TIDs

Although our proposition is less flexible than programmable quotas, it is still possible to have some control on the shared cache (and more generally on shared microarchitectural resources), though this is not the spirit of our proposition.

So far, we have assumed that threads running simultaneously had different TIDs. But if TIDs are programmable, we are not constrained to using different TIDs. If applications running have no QoS requirements and if we want the cache to behave like a conventional shared cache (for whatever reason), we can give the same TID to all threads. Also, it is possible to favor a thread. For instance, if we have 4 threads and if we want to give half of the shared cache capacity to one of the threads (for whatever reason), we can use one TID for the thread we want to favor, and a second TID that is shared by the 3 other threads.

Impact on throughput

When several applications run simultaneously, and compared with conventional LRU, the LRU SAR policies should increase the performance of some applications and decrease the performance of some others. To measure the average IPC, we ran each benchmark on core #1 and obtained its IPC when the 3 other cores run the 28 different workloads given in Table 2. The average IPC of each benchmark is the arithmetic mean of the 28 different IPCs measured for this benchmark on the 28 workloads. Results are given in Figure 10. As expected, the SAR SB and B2 policies decrease the average IPC on a few benchmarks (401,429,450) and increase it on a few others (434,435,456). On average, SAR LRU policies have little impact on total throughput.

Of course, it may be possible to devise replacement policies specifically aiming at maximizing total throughput, like some recently proposed policies [START_REF]JILP Workshop on Computer Architecture Competitions, Cache Replacement Championship[END_REF]. But in general, maximizing throughput is incompatible with providing performance guarantees.

Multi-threaded programs

So far we have considered sequential applications only. Obtaining a performance guarantee for a sequential application is not so easy, but obtaining a performance guarantee for a parallel application is even more difficult.

A possibility would be to reserve all the cores for one application. But if the number of threads in the application is less than the number of logical cores, processing resources are wasted.

Another possibility would be to let the programmer define a maximum number of threads nt for the application. Self-performance can be measured with the selfperf utility running ⌊nc/nt⌋ copies of the application simultaneously, with nc the number of logical cores. Then, enforcing selfperformance for that application requires to limit the number of applications running simultaneously to ⌊nc/nt⌋. If we try to run simultaneously several applications requiring a performance guarantee, it is the application with the largest nt that determines how many applications can run.

Of course, this would address only one of the many problems one would need to solve to provide a performance guarantee to parallel applications. The non-determinism inherent to some parallel programs seems a priori incompatible with obtaining a performance guarantee in the general case.

CONCLUSION

We introduced the concept of self-performance, which is a contract between the programmer and the microarchitecture. The programmer measures performance by running a copy of the application on each core, and the microarchitecture guarantees this level of performance independently of the characteristics of the applications running on the other cores. For the programmer, the advantage of selfperformance is that it is conceptually simple and does not require any knowledge of internal microarchitectural details. For the microarchitect, respecting the self-performance contract means paying attention to each microarchitectural resource that is shared between threads. In this context, shared caches are critical. We have shown that unmanaged sharing is incompatible with the self-performance contract. We have proposed sharing-aware cache replacement (SAR) policies that are compatible with self-performance.

The performance guarantee offered by SAR policies is not strict, in the sense that it is very difficult to prove the guarantee mathematically without getting rid of resource sharing (this is the case also for quota-based solutions). Nevertheless, our experiments and simulations have shown that the situation is better with our proposition than without it.

Yet, as the number of on-chip core increases, we believe that it will be more and more difficult to exploit the computing power of multicores without introducing significant performance variability. Increasing the number of on-chip cores without increasing (or worse, decreasing) the guaranteed performance of existing applications may limit the applicability of future multicores. Moreover, will programmers accept to spend some effort parallelizing their applications if they cannot have a performance guarantee ? We believe microarchitects should pay attention to these questions.

Figure 1 :

 1 Figure 1: Symmetric multicore simulated in this study.

Figure 3 :

 3 Figure 3: Microbenchmark 999 (compiled with gcc -O3 -DSIZE=160000000 -DSTEP=16)

Figure 4 :

 4 Figure 4: Symmetric run of microbenchmark 999 with SIZE = 2 19 (Figure3). Memory bandwidth is 4 bytes/cycle and the L2 replacement policy is a variant of DIP (one PSEL counter per thread). The plot shows the number of retired instructions on each core as a function of time.

Figure 6 :

 6 Figure 6: Example for explaining why self-performance can exceed the performance of an isolated run with memory bandwidth statically partitioned. This example assumes 2 cores.

Figure 8 :

 8 Figure 8: Cache pressure model. Cache capacity is C and bandwidth (maximum number of misses per cycle) is B. On this example, thread #1 has a working set of size W 1 and a miss rate curve that drops suddenly when W 1 blocks are cached. If the other threads are able to saturate bandwidth, the cache pressure is B/C and the miss rate m 1 of thread #1 is W 1 C B. Thus increasing bandwidth increases cache pressure and decreases thread #1 performance.

Figure 9 :

 9 Figure 9:The SB policy makes the worst-case perfor-

Table 1 :

 1 Simulated microarchitecture : default configu-

	multicore	4 dynamically-scheduled cores
	core fetch	2 instructions per cycle (x86)
	core retire	2 instructions per cycle (x86)
	reorder buffer	64 instructions (x86)
	branch predictor	YAGS, 12 KB, 25-bit global
		history, 8-bit tags
	branches	10-cycle minimum misprediction
		penalty, solved at retirement
	IL1 cache	private, 32 KB, 4-way SA LRU,
		64-byte block, 1 cycle lat,
		1 block refill & 2 instructions
		read per cycle
	DL1 cache	private, 32 KB, 4-way SA LRU,
		64-byte block, write-back
		write-alloc, 2 cycles lat,
		1 block refill & 1 ld-st/cycle
	L2 cache	shared, 4 MB, 16-way SA LRU,
		64-byte block, write-back
		write-alloc, 15 cycles lat,
		bandwidth 1 block/cycle
	MRQ	20 pending L2 misses
	memory bus	8 bytes per CPU cycle
	memory latency	300 CPU cycles
	hardware prefetch disabled

ration microarchitecture are summarized in Table

  Example with 2 threads. The miss rate m i of thread i is assumed to be a function of the number w i of cached blocks. The equilibrium partition (w 1 , w 2 ) is such that the two threads have equal cache pressure p = m 1 /w 1 = m 2 /w 2 , hence the points (w 1 , m 1 ) and (w 2 , m 2 ) lie on the same isobar (straight line whose slope is the pressure p). The equilibrium partition is obtained by rotating the isobar around the origin till w 1 + w 2 = C.

	misses / cycle
					isobar p
	m2
	m1
	0	w1	C/2	w2	C	cached blocks
	Figure 2:

To our knowledge, programmable quotas have not been adopted by the industry yet.

For avoiding having too many constraints on page allocation, page coloring may be active only when measuring performance with the selfperf utility. But for a stronger performance guarantee, page coloring should be the default behavior (some operating-systems like FreeBSD already use page coloring).

Actually, when counting blocks, we consider the 17 blocks consisting of the 16 blocks in the cache set plus the missing block.