Considering localized food systems as 'niches'…

… not only because of their market position, … but first and foremost because they may pave the way to reconfigure hegemonic orderings or 'regimes' (Geels and Schot, 2007) à What about the biopolitical dimension of terroir products innovations ? (Barham, 2003 ;Giaccaria et.al., 2013) Looking at the relationship between agriculture and environment in its broad sense, including its agro-physical definition (1), as well as socio-economic dimensions (2). Beyond issues of biodiversity conservation, lie… 1) perspectives of enhancing plants' capacity of adaptation (Chiffoleau and Desclaux, 2006) 2) and challenges of re-framing power asymmetries within the supply chains (Bonneuil et al., 2006).

Potato as the core object of investigations:

-a plant particularly subject to exhaustion, -and hence liable to jeopardize the sustainability of local food systems.

Between alliance and self-reliance

Questioning the limits of terroir

Delineating Sustainable Food Systems as Local Networks ? Lucile Garçon

PhD student in Geography -LER, University of Lyon 2 lucile.garcon@gmail.com à Assessing the management of vegetal material as a critical nexus

The spatial life of potatoes • The comparison of our different cases shows that where stakeholders are able and ready to form alliances with parts of the conventional system, the durability of the local food networks seems better. • Nevertheless, sustainability remains at stake, as long as farmers are unable to become less dependent on external manufacturers of seeds. à The 3 rd type gives stakeholders a chance to explicitly address such a contradiction and to define their own transition path which appears to be as tortuous as social innovation

  SEND BACK AND RE-BUYTUBERS EVERY 5 YEARS.2.5. Potatoes come back as high-yield tubers, but it lasts only a few years. TYPE 3 -A BROAD DYNAMIC HAS BEEN SET IN MOTION, WHICH FOSTERS THE MANAGEMENT OF BIODIVERSITY. STILL, THE VIABILITY OF THE SYSTEM REMAINS AT STAKE, AS THE REPRODUCTION OF THE FLAGSHIP POTATO IS NOW IN PERIL.Durability vs sustainability ? 2 ≠ 3 : One of the consortia studied decides to break off this cycle, and venture a management of vegetal material at a territorial scale.


Adrien Barbaresi
email: adrien.barbaresi@oeaw.ac.at

Efficient construction of metadata-enhanced web corpora

Metadata extraction is known to be a problem in general-purpose Web corpora, and so is extensive crawling with little yield. The contributions of this paper are threefold: a method to find and download large numbers of WordPress pages; a targeted extraction of content featuring much needed metadata; and an analysis of the documents in the corpus with insights of actual blog uses.

The study focuses on a publishing software (WordPress), which allows for reliable extraction of structural elements such as metadata, posts, and comments. The download of about 9 million documents in the course of two experiments leads after processing to 2.7 billion tokens with usable metadata. This comparatively high yield is a step towards more efficiency with respect to machine power and "Hi-Fi" web corpora.

The resulting corpus complies with formal requirements on metadata-enhanced corpora and on weblogs considered as a series of dated entries. However, existing typologies on Web texts have to be revised in the light of this hybrid genre.

Introduction 1.Context

This article introduces work on focused web corpus construction with linguistic research in mind. The purpose of focused web corpora is to complement existing collections, as they allow for better coverage of specific written text types and genres, user-generated content, as well as latest language evolutions. However, it is quite rare to find readymade resources. Specific issues include first the discovery of relevant web documents, and second the extraction of text and metadata, e.g. because of exotic markup and text genres (Schäfer et al., 2013). Nonetheless, proper extraction is necessary for the corpora to be established as scientific objects, as science needs an agreed scheme for identifying and registering research data [START_REF] Sampson | The role of taxonomy in language engineering[END_REF]. Web corpus yield is another recurrent problem [START_REF] Suchomel | Efficient Webcrawling for large text corpora[END_REF][START_REF] Schäfer | Focused Web Corpus Crawling[END_REF]. The shift from web as corpus to web for corpus -mostly due to an expanding Web universe and the need for better text quality (Versley and Panchenko, 2012) -as well as the limited resources of research institutions make extensive downloads costly and prompt for handy solutions [START_REF] Barbaresi | Ad hoc and general-purpose corpus construction from web sources[END_REF].

The DWDS lexicography project1 at the Berlin-Brandenburg Academy of Sciences already features a good coverage of specific written text genres [START_REF] Geyken | The DWDS corpus: A reference corpus for the German language of the 20th century[END_REF]. Further experiments including internet-based text genres are currently conducted in joint work with the Austrian Academy of Sciences (Academy Corpora). The common absence of metadata known to the philological tradition such as authorship and publication date accounts for a certain defiance regarding Web resources, as linguistic evidence cannot be cited or identified properly in the sense of the tradition. Thus, missing or erroneous metadata in "one size fits all" web corpora may undermine the relevance of web texts for linguistic purposes and in the humanities in general. Additionally, nearly all existing text extraction and classification techniques have been developed in the field of information retrieval, that is not with linguistic objectives in mind.

The contributions of this paper are threefold:

(1) a method to find and download large amounts of WordPress pages;

(2) a targeted extraction of content featuring much needed metadata;

(3) an analysis of the documents in the corpus with insights of actual uses of the blog genre. My study focuses on a publishing software with two experiments, first on the official platform wordpress.com and second on the .at-domain. WordPress is used by about a quarter of the websites worldwide2 , the software has become so broadly used that its current deployments can be expected to differ from the original ones. A number of 158,719 blogs in German have previously been found on wordpress.com [START_REF] Barbaresi | For a fistful of blogs: Discovery and comparative benchmarking of republishable German content[END_REF]. The .at-domain (Austria) is in quantitative terms the 32th top-level domain with about 3,7 million hosts reported.3

Definitional and typological criteria

From the beginning of research on blogs/weblogs, the main definitional criterion has always been their form, a "reverse chronological sequences of dated entries" [START_REF] Kumar | On the Bursty Evolution of Blogspace[END_REF]. Another formal criterion is the use of dedicated software to articulate and publish the entries, a "weblog publishing software tool" [START_REF] Glance | Blogpulse: Automated Trend Discovery for Weblogs[END_REF], "publicdomain blog software" [START_REF] Kumar | On the Bursty Evolution of Blogspace[END_REF], or Content Management System (CMS). These tools largely impact the way blogs are created and run. 1996 seems to be the acknowledged beginning of the blog/weblog genre, with an exponential increase of their use starting in 1999 with the emergence of several user-friendly publishing tools [START_REF] Kumar | On the Bursty Evolution of Blogspace[END_REF][START_REF] Herring | Bridging the Gap: A Genre Analysis of Weblogs[END_REF].

Whether a blog is to be considered to be a web page in its whole [START_REF] Glance | Blogpulse: Automated Trend Discovery for Weblogs[END_REF] or a website containing a series of dated entries, or posts, (Kehoe and Gee, 2012) being each a web page, there are invariant elements, such as "a persistent sidebar containing profile information" as well as links to other blogs [START_REF] Kumar | On the Bursty Evolution of Blogspace[END_REF], or blogroll. For that matter, blogs are intricately intertwined in what has been called the blogosphere: "The crosslinking that takes place between blogs, through blogrolls, explicit linking, trackbacks, and referrals has helped create a strong sense of community in the weblogging world." [START_REF] Glance | Blogpulse: Automated Trend Discovery for Weblogs[END_REF]. This means that a comprehensive crawl could lead to better yields.

Regarding the classification of blogs, [START_REF] Blood | The Weblog Handbook: Practical Advice on Creating and Maintaining your Blog[END_REF] distinguishes three basic types: filters, personal journals, and notebooks, while [START_REF] Krishnamurthy | The Multidimensionality of Blog Conversations: The Virtual Enactment of September 11[END_REF] builds a typology based on function and intention of the blogs: online diaries, support group, enhanced column, collaborative content creation. More comprehensive typologies established on one hand several genres: online journal, self-declared expert, news filter, writer/artist, spam/advertisement; and on the other hand distinctive "variations": collaborative writing, comments from readers, means of publishing [START_REF] Glance | Blogpulse: Automated Trend Discovery for Weblogs[END_REF].

2 Related work

(Meta-)Data Extraction

Data extraction has first been based on "wrappers" (nowadays: "scrapers") which were mostly relying on manual design and tended to be brittle and hard to maintain [START_REF] Valter Crescenzi | Roadrunner: Towards Automatic Data Extraction From Large Web Sites[END_REF]. These extraction procedures have also been used early on by blogs search engines [START_REF] Glance | Blogpulse: Automated Trend Discovery for Weblogs[END_REF]. Since the genre of "web diaries" was established before the blogs in Japan, there have been attempts to target not only blog software but also regular pages [START_REF] Nanno | Automatically Collecting, Monitoring, and Mining Japanese Weblogs[END_REF], in which the extraction of metadata also allows for a distinction based on heuristics.

Efforts were made to generate wrappers automatically, with emphasis on three different approaches [START_REF] Guo | ECON: an Approach to Extract Content from Web News Page[END_REF]: wrapper induction (e.g. by building a grammar to parse a web page), sequence labeling (e.g. labeled examples or a schema of data in the page), and statistical analysis and series of resulting heuristics. This analysis combined to the inspection of DOM tree characteristics [START_REF] Wang | News Article Extraction with Template-Independent Wrapper[END_REF][START_REF] Guo | ECON: an Approach to Extract Content from Web News Page[END_REF] is a common ground to the information retrieval and web corpus linguistics communities, with the categorization of HTML elements and linguistic features [START_REF] Cai | Content Extraction from News Pages using Particle Swarm Optimization on Linguistic and Structural Features[END_REF] for the former, and markup and boilerplate removal operations known to the latter community (Schäfer and Bildhauer, 2013).

Regarding content-based wrappers for blogs in particular, targets include the title of the entry, the date, the author, the content, the number of comments, the archived link, and the trackback link [START_REF] Glance | Blogpulse: Automated Trend Discovery for Weblogs[END_REF]; they can also aim at com-ments specifically [START_REF] Mishne | Leave a Reply: An Analysis of Weblog Comments[END_REF].

Blog corpus construction

The first and foremost issue in blog corpus construction still holds true today: "there is no comprehensive directory of weblogs, although several small directories exist" [START_REF] Glance | Blogpulse: Automated Trend Discovery for Weblogs[END_REF]. Previous work established several modes of construction, from broad, opportunistic approaches, to the focus on a particular method or platform due to the convenience of retrieval processes. Corpus size and length of downloads are frequently mentioned as potential obstacles. [START_REF] Glance | Blogpulse: Automated Trend Discovery for Weblogs[END_REF] performed URL harvesting through specialized directories, and found a practical upper bound at about 100,000 active weblogs, which were used as a corpus in their study.

The first comprehensive studies used feeds to collect blog texts [START_REF] Gruhl | Information Diffusion through Blogspace[END_REF], since they are a convenient way to bypass extensive crawling and to harvest blog posts (and more rarely comments) without needing any boilerplate removal.

An approach based on RSS and Atom feeds is featured in the TREC-Blog collection4 (Macdonald and Ounis, 2006), a reference in Information Extraction which has been used in a number of evaluation tasks. 100,649 blogs were predetermined, they are top blogs in terms of popularity, but no further information is given. Spam blogs, and hand-picked relevant blogs (no information on the criteria either) are used to complement and to balance the corpus to make it more versatile. The corpus is built by fetching feeds describing recent postings, whose permalinks are used as a reference. From initial figures totaling 3,215,171 permalinks and 324,880 homepages, most recent ones from 2008 mention 1,303,520 feeds and 28,488,766 permalink documents. 5Another way to enhance the quality of data and the ease of retrieval is the focus on a particular platform. To study authorship attribution, [START_REF] Schler | Effects of Age and Gender on Blogging[END_REF] gathered a total of 71,000 blogs on the Google-owned Blogger platform, which allowed for easier extraction of content, although no comments are included in the corpus.

The Birmingham Blog Corpus (Kehoe and Gee, 2012) is a more recent approach to comprehensive corpus construction. Two platforms are taken into consideration: Blogger and wordpress.com, with the "freshly pressed" page on WordPress as well as a series of trending blogs used as seed for the crawls, leading to 222,245 blog posts and 2,253,855 comments from Blogger and WordPress combined, totaling about 95 million tokens (for the posts) and 86 million tokens (for the comments).

The YACIS Corpus [START_REF] Ptaszynski | YACIS: A five-billion-word corpus of Japanese blogs fully annotated with syntactic and affective information[END_REF]) is a Japanese corpus consisting of blogs collected from a single blog platform, which features mostly users in the target language as well as a clear HTML structure. Its creators were able to gather about 13 million webpages from 60,000 bloggers for a total of 5.6 billion tokens.

Last, focused crawl on the German version of the platform wordpress.com led to the construction of a corpus of 100 million tokens under Creative Commons licenses [START_REF] Barbaresi | For a fistful of blogs: Discovery and comparative benchmarking of republishable German content[END_REF], albeit with a much lower proportion of comments (present on 12.7% of the posts). In fact, comments have been shown to be strongly related to the popularity of a blog [START_REF] Mishne | Leave a Reply: An Analysis of Weblog Comments[END_REF], so that the number of comments is much lower when blogs are taken at random.

The sharp decrease in publication of work documenting blog corpus construction after 2008 signalizes a shift of focus, not only because web corpus construction does not often get the attention it deserves, but also because of the growing popularity of short message services like Twitter, which allow for comprehensive studies on social networks and internet-based communication, with a larger number of users and messages as well as clear data on network range (e.g. followers).

Method

Discovery

A detection phase is needed to be able to observe bloggers "in the wild" without needing to resort to large-scale crawling. In fact, guessing if a website uses WordPress by analyzing HTML code is straightforward if nothing was been done to hide it, which is almost always the case. However, downloading even a reasonable number of web pages may take a lot of time. That is why I chose to perform massive scans in order to find websites using WordPress, which to my best knowledge has not yet been tried in the literature. The detection process is twofold, the first filter is URL-based whereas the final selection uses shallow HTTP requests.

The permalinks settings6 in WordPress define five common URL structures: default (?p= or ?page id= or ?paged=), date (/year/ and/or /month/ and/or /day/ and so on), post number (/keyword/number -where keyword is for example "archives"), tag or category (/tag/, /category/, or cross-language equivalents), and finally post name (long URLs containing a lot of hyphens). Patterns derived from those structures can serve as a first filter, although the patterns are not always reliable: news websites tend to use dates very frequently in URLs, in that case the accuracy of the prediction is poor.

The most accurate method would be a scan of fully-rendered HTML documents with clear heuristics such as the "generator" meta tag in the header, which by default points to WordPress. In this study, HTTP HEAD7 requests are used to spare bandwidth and get cleaner, faster results. HEAD requests are part of the HTTP protocol. Like the most frequent request, GET, which fetches the content, they are supposed to be implemented by every web server. A request fetches the meta-information written in response headers without downloading the actual content, which makes it much faster, but also more resource-friendly, as according to my method less than three requests per domain name are sufficient.

The following rules come from from the official documentation and have been field-tested:

(1) A request sent to the homepage is bound to yield pingback information to use via the XML-RPC protocol in the X-Pingback header. Note that if there is a redirect, this header usually points to the "real" domain name and/or path, ending in xmlrpc.php. What is more, frequently used Word-Press modules may leave a trace in the header as well, e.g. WP-Super-Cache, which identifies a WordPress-run website with certainty.

(2) A request sent to /login or /wp-login.php should yield a HTTP status corresponding to an existing page (2XX, 3XX, more rarely 401).

(3) A request sent to /feed or /wp-feed.php should yield the header Location.

The criteria can be used separately or in combination. I chose to use a simple decision tree. The information provided is rarely tampered on or misleading, since almost all WordPress installations stick to the defaults. Sending more than one request makes the guess more precise, it also acts like a redirection check which provides the effectively used domain name behind a URL. Thus, since the requests help deduplicating a URL list, they are doubly valuable.

Sources and crawls

This study falls doubly into the category of focused or scoped crawling [START_REF] Olston | Web Crawling[END_REF]: the emphasis lies on German or on the .atdomain, and a certain type of websites are examined based on structural characteristics.

I have previously shown that the diversity of sources has a positive impact on yield and quality [START_REF] Barbaresi | Finding Viable Seed URLs for Web Corpora: A Scouting Approach and Comparative Study of Available Sources[END_REF]. Aside from URL lists from this and other previous experiments [START_REF] Barbaresi | Crawling microblogging services to gather language-classified URLs. Workflow and case study[END_REF] and URLs extracted from each batch of downloaded web documents (proper crawls), several sources were queried, not in the orthodox BootCat way with randomized tuples [START_REF] Baroni | BootCaT: Bootstrapping Corpora and Terms from the Web[END_REF]) but based on formal URL characteristics as described above:

(1) URLs from the CommonCrawl8 , a repository already used in web corpus construction [START_REF] Habernal | C4corpus: Multilingual web-size corpus with free license[END_REF][START_REF] Schäfer | CommonCOW: massively huge web corpora from CommonCrawl data and a method to distribute them freely under restrictive EU copyright laws[END_REF];

(2) the CDX index query frontend of the internet Archive;9 (3) public instances of the metasearch engine Searx. 10A further restriction resides in the downloads of sitemaps for document retrieval. A majority of websites are optimized in this respect, and experiments showed that crawls otherwise depend on unclear directory structures such as posts classified by categories or month, as well as on variables (e.g. page) in URL structures, which leads to numerous duplicates and an inefficient crawl. Another advantage is that websites offering sitemaps are almost systematically robot-friendly, which solves ethical robots.txt-related issues such as the crawl delay, which is frequently mentioned as an obstacle in the literature.

Extraction

I designed a text extraction targeting specifically

WordPress pages, which is transferable to a whole range of self-hosted websites using WordPress, allowing to reach various blogger profiles thanks to a comparable if not identical content structure. The extractor acts like a state-of-the-art wrapper: after parsing the HTML page, XPATHexpressions select subtrees and operate on them through pruning and tag conversion to (1) write the data with the desired amount of markup and (2) convert the desired HTML tags into the output XML format in strict compliance to the guidelines of the Text Encoding Initiative 11 , in order to allow for a greater interoperability within the research community.

The extraction of metadata targets the following fields, if available: title of post, title of blog, date of publication, canonical URL, author, categories, and tags. The multiple plugins cause strong divergences in the rendered HTML code, additionally not all websites use all the fields at their disposal. Thus, titles and canonical URL are the most often extracted data, followed by date, categories, tags, and author.

Content extraction allows for a distinction between post and comments, the latter being listed as a series of paragraphs with text formatting. The main difference with extractors used in information retrieval is that structural boundaries are kept (titles, paragraphs), whereas links are discarded for corpus use. A special attention is given to dates. Documents with non-existent or missed date or entry content are discarded during processing and are not part of the corpus, which through the dated entries is a corpus of "blogs" in a formal sense. Removal of duplicates is performed on entry basis.

Content analysis

In the first experiment, language detection is performed with langid.py [START_REF] Lui | langid.py: An Off-the-shelf Language Identification Tool[END_REF] and sources are evaluated using the Filtering and Language identification for URL Crawling Seeds 12 toolchain [START_REF] Barbaresi | Finding Viable Seed URLs for Web Corpora: A Scouting Approach and Comparative Study of Available Sources[END_REF], which includes obvious spam and non-text documents filtering, redirection checks, collection of host-and markup-based data, HTML code stripping, document validity check, and language identification. No language detection is undertaken is the second experiment since no such filtering is intended. That being said, a large majority of webpages are expected to be in German, as has been shown for another German-speaking country in the .de-TLD 11 http://www.tei-c.org/ 12 https://github.com/adbar/flux-toolchain (Schäfer et al., 2013).

The token counts below are produced by the WASTE tokenizer [START_REF] Jurish | Word and Sentence Tokenization with Hidden Markov Models[END_REF].

4 Experiment 1: Retrieving German blogs

General figures on harvested content

In a previous experiment, the largest platform for WordPress-hosted websites, wordpress.com, blogs under CC license were targeted [START_REF] Barbaresi | For a fistful of blogs: Discovery and comparative benchmarking of republishable German content[END_REF]. In the summer of 2015, sitemaps were retrieved for all known home pages, which lead to the integral download of 145,507 different websites for a total number of 6,605,078 documents (390 Gb), leaving 6,095,630 files after processing (36 Gb). There are 6,024,187 "valid" files (with usable date and content) from 141,648 websites, whose text amounts to about 2.11 billion tokens.

The distribution of harvested documents in the course of years is documented in table 6, there are 6,095,206 documents with at least a reliable indication of publication year, i.e. 92.3% of all documents. Contrarily to dates in the literature, these results are not from reported permalinks dates from feeds, but directly from page metadata; nonetheless, there is also a fair share of implausible dates, comparable to the 3% of the TREC blog corpus [START_REF] Macdonald | The TREC Blogs06 Collection: Creating and Analysing a Blog Test Collection[END_REF]. This indicates that these dates are not an extraction problem but rather a creative license on the side of the authors. All in all, the observed metadata are in line with the expectations, even if the high proportion of photoblogs is not ideal for text collection. Comments were extracted for 1,454,752 files (24%), this proportion confirms the hypothesis that the wordpress.com-platform leads primarily to the publication of blogs in a traditional fashion. On the contrary, the typology has to be more detailed in the second experiment due to the absence of previous knowledge about the collection. 5 Experiment 2: Targeting the .at-domain

General figures on harvested content

The iterations summed up in table 5 took place during the 2nd half of 2015. Each time, all links in the .at top level domain were extracted, and analyzed as to their potential to be using Word-Press. If so, potential sitemaps were retrieved and the URLs added to the queue if they were new.

When necessary (e.g. after stages 5 and 6), the crawls have been refreshed with new material described in sources. After 11 iterations, seed exhaustion was nearing as new WordPress websites with sitemaps were hard to come by, and the experiment was stopped. Table 5: Iterations and yields in the second experiment A total of 3,053,974 different URLs have been downloaded (159 Gb), which left after processing and canonicalization 2,589,674 files (14 Gb). There are about 2 million "valid" files (with usable date and content), whose text amounts to about 550 million tokens. There are 5,664 different domain names before processing, and 7,275 after (due to the resolution of canonical URLs).

Typology

Of all canonical domain names, only 240 contain the word blog. Comments were extracted for 181,246 files (7%), which is explained mainly by the actual absence of comments and partly by difficulty of extraction in the case of third-party comment systems.

The distribution of harvested documents in the course of years is documented in table 6. There are 2,083,535 documents with at least a reliable indication of publication year, i.e. 80.5% of all documents. The relative amount of "creative" dates is slightly higher than in experiment 1, which hints at a larger diversity of form and content.

The increase in the number of documents exceeds by far the increase of domains registered in the .at-TLD13 , which seems to hint at the growing popularity of WordPress and maybe also at the ephemeral character of blogs.

Table 6: Distribution of documents among plausible years in the second experiment An analysis of the top-50 domains names in canonical URLs extracted from the documents, by total number of documents in the corpus (see table 7) gives the following typology: informational for general news websites (9), promotional/commercial for websites which list ads, deals, jobs or products (12), specialized for focused news and community websites (16), entertainment (3), political (3), personal for websites dedicated to a person or an organization (3), adult (2), forum (1).

There are 260,468 pages with categories, 834,284 uses and 11,813 different categories in total, the top-15 results are displayed in table 8. The Table 7: Most frequent domains names in URL queue in the second experiment fact that "blog" is used as a category shows that it is not taken for granted.

There are 279,083 pages with tags, 5,093,088 uses in total, and 192,352 different tags, the top-15 results are displayed in table 9. The tags reflect a number of different preoccupations, including family, holidays, sex, job and labor legislation. "Homemade" and "amateur" can be used in German, albeit rarely, these words give more insights on the genre (most probably adult entertainment) All in all, the distribution of categories and tags indicates that the majority of texts target as expected German-speaking users.

Discussion

Although the definition of blogs as a hybrid genre neither fundamentally new nor unique [START_REF] Herring | Bridging the Gap: A Genre Analysis of Weblogs[END_REF] holds true, several assumptions about weblogs cannot be considered to be accurate anymore in the light of frequencies in the corpus. Blogs are not always "authored by a single individual" [START_REF] Kumar | On the Bursty Evolution of Blogspace[END_REF], nor does the frequency criterion given by the Oxford English Dictionary (Kehoe and Gee, 2012) -"frequently updated web site" -necessarily correspond to the reality. Even if both experiments gathered blogs in a formal sense, there are differences between the websites on the platform wordpress.com and freely hosted websites. The former are cleaner in form and content, they are in line with a certain tradition. The "local community interactions between a small number of bloggers" [START_REF] Kumar | On the Bursty Evolution of Blogspace[END_REF] of the beginnings have been relegated by websites corresponding to the original criteria of a blog but whose finality is to sell information, entertainment, or concrete products and services.

Consequently, the expectation that "blog software makes Web pages truly interactive, even if that interactive potential has yet to be fully exploited" [START_REF] Herring | Bridging the Gap: A Genre Analysis of Weblogs[END_REF] is either outdated or yet to come. Beside these transformations and the emergence of other social networks, the whole range from top to barely known websites shows that the number of comments per post and per website is largely inferior to the "bursting" phase of webblogging, where comments were "a substantial part of the blogosphere" [START_REF] Mishne | Leave a Reply: An Analysis of Weblog Comments[END_REF]. The evolution of the Web as well as the scope of this study cast the typical profile of a passive internet consumer, a "prosumer" at best, which should be taken in consideration in web corpus construction and computer-mediated communication studies. If blogs still bridge a technological gap between HTML-enhanced CMC and CMC-enhanced Web pages [START_REF] Herring | Bridging the Gap: A Genre Analysis of Weblogs[END_REF], a typological gap exists between original and current studies as well as between users of a platform and users of a content management system.

Conclusion

The trade-off to gain metadata using focused downloads following strict rules seems to get enough traction to build larger web corpora, since a total of 550 Gb of actually downloaded material allows after processing for the construction of a corpus of about 2.7 billion tokens with rich metadata. This comparatively high yield is a step towards more efficiency with respect to machine power and "Hi-Fi" web corpora, which could help promoting the cause of web sources and modernization of research methodology.

The resulting corpus complies with formal requirements on metadata-enhanced corpora and on weblogs considered as a series of dated entries. The interlinking of blogs and their rising popularity certainly don't stay in the way. However, addressing the tricky question of web genres seems inevitable in order to be able to properly qualify my findings and subsequent linguistic inquiries. More than ever, blogs are a hybrid genre, and their ecology tends to mimic existing text types, audiences, and motivations, with a focus on information (general, specialized, or community-based) as well as on promotional goals.

Table 1 :

 1 Distribution of documents among plausible years in the first experiment4.2 TypologyAn analysis of the top domain names in canonical URLs extracted from the documents, by total number of documents in the corpus (see table 2) yields a typology clearly oriented towards community blogging mostly centered on creative activities or hobbies.

	Domain name	URLs
	mariusebertsblog.com	2,954
	allesnaehbar.de	1,730
	zuckerzimtundliebe.de	1,194
	lyrikzeitung.com	1,104
	der-retrosalon.com	1,092
	rhein-main-startups.com	1,046
	sciencefiles.org	1,042
	des-belles-choses.com	1,014
	twinklinstar.com	1,013
	wirsindeins.org	1,007

Table 2 :

 2 Most frequent domains names in URL queue in the first experiment There are 4,777,546 pages with categories, 10,288,861 uses and 312,055 different categories in total, the top-15 results are displayed in table 3.

	Name	Freq. Translation
	1 Uncategorized 588,638 (defaut category)
	2 Allgemein	239,796 general
	3 Politik	71,534 politics
	4 Allgemeines	60,178 general
	5 News	58,281 (also German)
	6 Musik	46,238 music
	7 Gesellschaft	35,675 society
	8 Fotografie	35,042 photography
	9 Deutschland	33,841 Germany
	10 Aktuelles	33,117 current topics
	11 Medien	30,914 media
	12 Alltag	29,839 everyday life
	13 Leben	27,897 life
	14 Fotos	26,107 pictures
	15 Sonstiges	24,431 misc.

Table 3 :

 3 Most frequent categories in the first experimentThere are 2,312,843 pages with tags, 15,856,481 uses in total, and 2,431,920 different tags, the top-15 results are displayed in table 4. They are as general as the top categories but slightly more informative.

Table 4 :

 4 Most frequent tags in the first experiment

Table 8 :

 8 Most frequent categories in the second experiment

	Name	Freq. Translation
	1 Wien	18,973 Vienna
	2 Deutschland	18,895 Germany
	3 Usermeldungen	14,409 user reports
	4 sterreich	10,886 Austria
	5 Angebot aus DE 10,155 offer from Germany
	6 sex	10,112
	7 Frauen	9,541 women
	8 Kinder	8,968 children
	9 USA	8,013
	10 Urlaub	7,767 holiday
	11 homemade	7,666
	12 amateur	7,660
	13 mydirtyhobby	7,635
	14 Recht	7,611 law
	15 Arbeitsrecht	7,294 labor legislation

Table 9 :

 9 Most frequent tags in the second experiment than on content language.

Digital Dictionary of German, http://zwei.dwds.de

http://w3techs.com/technologies/details/cmwordpress/all/all

3 http://ftp.isc.org/www/survey/reports/2016/01/bynum.txt

http://ir.dcs.gla.ac.uk/wiki/TREC-BLOG

https://web.archive.org/web/20160313020503/ http://ir.dcs.gla.ac.uk/test collections/blogs08info.html

http://codex.wordpress.org/Using Permalinks

http://www.w3.org/Protocols/rfc2616/rfc2616

http://commoncrawl.org

https://github.com/internetarchive/wayback/ tree/master/wayback-cdx-server

https://github.com/asciimoo/searx/wiki/Searx-instances

YearDocs. 2003 1,746 2004 4,993 2005 13,916 2006 62,901 2007 191,898 2008 377,271 2009 575,923 2010 733,397 2011 871,108 2012 1,066,996 2013 1,108,495 2014 717,861 2015 362,633 rest 6,068

Year Docs. 2003 17,263 2004 30,009 2005 28,177 2006 35,853 2007 47,934 2008 78,895 2009 104,604 2010 152,422 2011 176,231 2012 197,819 2013 297,143 2014 371,605 2015 517,073 rest 28,507

1,594,059 in January 2005; 3,112,683 in January 2010; 3,630,078 in January 2015 Source: http://ftp.isc.org/www/survey/reports/ Domain name URLs Genre vol.at 333,690 informational triple-s.at 312,714 informational salzburg24.at 134,230 informational vienna.at 96,654 informational vorarlbergernachrichten.at 49,816 informational dealdoktor.de 25,445 promotional sportreport.biz 24,796 informational cba.fro.at 21,895 informational juve-verlag.at 21,548 promotional eventfotos24.at 17,805 entertainment unibrennt.at 16,497 political dolomitenstadt.at 16,484 informational sparhamster.at 13,997 promotional freizeitalpin.com 12,440 specialized webdeals.at 11,472 promotional hans-wurst.net 10,717 entertainment autorevue.at 9,840 specialized katja.at 9,833 political spielweb.at 9,541 promotional medmedia.at 9,125 specialized adiweiss.at 8,741 personal sciam-online.at 8,058 specialized electronicbeats.net 7,255 specialized antiquariat-getau.at 7,205 promotional greenpeace.org 7,031 political photoboerse.at 6,945 promotional salzburgresearch.at 6,802 professional mittelstand-nachrichten.at 6,694 informational sturm12.at 6,672 specialized raketa.at 6,170 entertainment platzpirsch.at 6,127 promotional sexyinsider.at 6,024 adult rebell.at 5,782 specialized jusportal.at 5,739 specialized aktuelle-veranstaltungen.at 5,733 specialized ffmoedling.at 5,633 personal zddk.eu 5,386 forum kosmetik-transparent.at 5,381 specialized sportwetteninfo.at 5,366 specialized autoguru.at 5,142 specialized ps4news.at 5,102 specialized gastronomiejobs.wien 5,035 promotional psychohelp.at 4,836 promotional porno-austria.at 4,822 adult christianmari.at 4,709 promotional blog.sprachreisen.at 4,493 personal w6-tabletop.at 4,488 specialized ellert.at 4,381 promotional demonic-nights.at 4,353 specialized todesanzeigen.vol.at 4,296 specialized


Liang Wang
email: lwang@cse.cuhk.edu.hk

Xiaohang Wang
email: xh.wang@giat.ac.cn

Terrence Mak

Dynamic Programming-Based Lifetime Reliability Optimization in Networks-on-Chip

Keywords: Reliability, Networks-on-Chip, Routing algorithm, Dynamic programming

Technology scaling leads to the reliability issue as a primary concern in Networks-on-Chip (NoC) design. Due to routing algorithms, some routers may age much faster than others, which become a bottleneck for system lifetime. In this chapter, lifetime is modeled as a resource consumed over time. A metric lifetime budget is associated with each router, indicating the maximum allowed workload for current period. Since the heterogeneity in router lifetime reliability has strong correlation with the routing algorithm, we define a problem to optimize the lifetime by routing packets along the path with maximum lifetime budgets. A dynamic programming-based lifetime-aware routing algorithm is proposed to optimize the lifetime distribution of routers. The dynamic programming network approach is employed to solve this problem with linear complexity. The experimental results show that the lifetime-aware routing has around 20%, 45%, 55% minimal MTTF improvement than XY routing, NoP routing, and Oddeven routing, respectively.

Introduction

Networks-on-Chip (NoC) is emerging as an efficient communication infrastructure for connecting resources in many core system. NoC is composed of routers interconnected through a network. NoC provides communication fabrics for data transmission among cores. The data transmission is in the form of packets, which is divided into flits and routed by routers. In NoC, routing algorithm provides a protocol for routing the packets. In other words, the pathways of the packets are determines by a routing algorithm. Generally, routing algorithms are classified into deterministic routing and adaptive routing. Deterministic routing algorithm provides a fixed path given source and destination. Compared to deterministic routing algorithm, adaptive routing algorithm is more flexible. The pathway of a packet can dynamically adapt to NoC traffic or other conditions. In this chapter, we exploit an adaptive routing algorithm to optimize the lifetime reliability of NoC.

With shrinking feature size and increasing transistor density, reliability issue is becoming a primary concern for chip design. The failure rate of electronic components increases 316% as the features size decreases 64% [START_REF] Srinivasan | The impact of technology scaling on lifetime reliability[END_REF]. Along with shrinking feature size, power density of chips increases exponentially, leading to overheat. High temperature also greatly reduces the lifetime of a chip. Dynamic thermal management (DTM) techniques such as dynamic voltage and frequency scaling (DVFS) [START_REF] Hanumaiah | Temperature-aware dvfs for hard real-time applications on multicore processors[END_REF], adaptive routing [START_REF] Al-Dujaily | Dynamic on-chip thermal optimization for three-dimensional networks-on-chip[END_REF] are employed to address the temperature issues. The temperature is maintained below a limit to ensure the reliability of a chip. Dynamic reliability management (DRM) is first proposed in [START_REF] Srinivasan | The case for lifetime reliabilityaware microprocessors[END_REF], aiming at ensuring a target lifetime reliability at better performance.

The reliability of NoC depends on the routers. The lifetime reliability of a router has strong correlation with the routing algorithm because the lifetime reliability is relevant to operating conditions and temperature, which are affected by the routing algorithm. We conduct a case study to show the distribution of routers reliability under two different routing algorithms, XY and Oddeven. The case study is evaluated in 8 × 8 2D mesh NoC. The detailed description of simulation setup is referred to Section 5. The lifetime, measured in MTTF metric (mean time to failure), is normalized to the maximum one. The results are presented in Figure 1, which shows the number of occurrences in different MTTF ranges. For both routing algorithms, there is a heterogeneity observed among the routers. Especially for Oddeven routing, the minimum MTTF of router is even less than 20% of the maximum one. It suggests that the minimum MTTF router is aging more than 5 times faster than the maximum MTTF router. The unbalanced lifetime distribution would become a bottleneck for the lifetime of system. Furthermore, the two distribution functions differ in slop for XY and Oddeven, indicating the correlation of router reliability and routing algorithms.

The above example indicates routing paths can be a control knob to optimize the router reliability. In this chapter, we apply dynamic reliability management to NoC and propose a lifetime-aware routing to optimize the lifetime reliability of NoC routers. Lifetime is modeled as a resource consumed over time. A lifetime budget is defined for each router, indicating the maximum allowed workload for current time. We define a longest path problem to optimize the router lifetime by routing packets along the path with maximum lifetime budgets. The problem is solved by dynamic programming approach with linear time complexity. The key idea is to use lifetime budget as the cost for dynamic programming. Moreover, a low cost hardware unit is implemented to accelerate the lifetime budget computation at runtime. This chapter is an extension of previous work [START_REF] Wang | Dynamic programming-based lifetime aware adaptive routing algorithm for network-on-chip[END_REF] by adding more detail descriptions, substantial analysis and modified experiments. The main contributions of this chapter include:

(1) Define a lifetime budget for each router, indicating the maximum allowed workload for current period. (2) Define a problem to optimize the lifetime by routing packets along the path with maximum lifetime budgets.

(3) Propose a lifetime-aware routing algorithm, which solves the problem through a dynamic programming approach with linear time complexity.

The remainder of the chapter is organized as follows. Section 2 briefly introduces the related work. Section 3 discusses the DRM and defines the lifetime budget for a router. Section 4 presents the adaptive routing, including problem formulation and routing algorithm. Section 5 analyzes the experimental results and Section 6 concludes this chapter.

Related Work

There are two kinds of failures in ICs: extrinsic failures and intrinsic failures. Extrinsic failures are caused by manufacturing defects and occur with a decreasing rate over time. Intrinsic failures are related with wear-out and are caused due to operation conditions within the specified conditions, e.g. temperature, current density, etc. In this chapter, we focus on long-term reliability management of routers, and only consider intrinsic failures. The failure mechanisms for intrinsic failures include electro migration (EM), time-dependent dielectric breakdown (TDDB), stress migration (SM), Negative Bias temperature instability (NBTI) and thermal cycling (TC). A reliability model named RAMP is proposed in [START_REF] Srinivasan | The case for lifetime reliabilityaware microprocessors[END_REF], which combines various failure mechanism models using Sum-of-failure method.

In the failure mechanism models, lifetime reliability is highly related to temperature. Most prior studies consider thermal issues, with the objectives to balance the temperature or to take temperature as a constraint [START_REF] Mulas | Thermal balancing policy for multiprocessor stream computing platforms[END_REF][13] [START_REF] Al-Dujaily | Dynamic on-chip thermal optimization for three-dimensional networks-on-chip[END_REF]. Mulas et al. [START_REF] Mulas | Thermal balancing policy for multiprocessor stream computing platforms[END_REF] employed a task migration approach to redistribute power dissipation such that the temperature of multiprocessor system is balanced. Hanumaiah et al. [START_REF] Hanumaiah | Temperature-aware dvfs for hard real-time applications on multicore processors[END_REF] adopted DVFS to maintain the temperature of multiprocessor system under a constraint. Al-Dujaily et al. [START_REF] Al-Dujaily | Dynamic on-chip thermal optimization for three-dimensional networks-on-chip[END_REF] proposed to balance the temperature of NoC by a thermal-aware routing algorithm. However, the thermal techniques neglect other factors on reliability, such as switch activity, operating frequency, etc. The lifetime could not be effectively balanced.

Dynamic reliability management (DRM), proposed in [START_REF] Srinivasan | The case for lifetime reliabilityaware microprocessors[END_REF], [START_REF] Lu | Interconnect lifetime prediction for reliability-aware systems[END_REF], regards the lifetime as a source that could be consumed. Reliability management is mainly studied for single-core processor or multi-core processors through various solutions, such as task mapping [START_REF] Hartman | Lifetime improvement through runtime wear-based task mapping[END_REF], frequency control [START_REF] Shi | Dynamic thermal management under soft thermal constraints[END_REF], reliability monitoring and adaptation [START_REF] Mercati | Workload and user experience-aware dynamic reliability management in multicore processors[END_REF], etc. Hartman [START_REF] Hartman | Lifetime improvement through runtime wear-based task mapping[END_REF] proposed to dynamically manage the lifetime of chip multiprocessors through run-time task mapping. The task mapping obtains data from on-chip reliability sensors and adapts to changing lifetime distribution in the system at run-time. Shi et al. [START_REF] Shi | Dynamic thermal management under soft thermal constraints[END_REF] explored DRM for both single-core and multi-core processors. The overall performance expressed as frequency policies is maximized under soft thermal constraint. Mercati et al. [START_REF] Mercati | Workload and user experience-aware dynamic reliability management in multicore processors[END_REF] proposed a DRM policy based on a two level controller. The controller monitors system reliability on a long time scale and adapts operating conditions on a short time scale. The multi-core system adapts operating conditions with DVFS such that a predefined target lifetime is satisfied.

Since NoC is becoming more important for multi-core system interconnection, reliability management in NoC domain is attracting increasing attentions. Some studies make attempt to improve the NoC reliability through microarchitecture design. A wear-resistant router microarchitecture is designed in [START_REF] Kim | Use it or lose it: wear-out and lifetime in future chip multiprocessors[END_REF] to improve reliability of routers. However, they did not consider the routing algorithm impacts on the router lifetime. Task mapping is another solution to improve NoC reliability. A compile-time task mapping algorithm is proposed in [START_REF] Das | Reliability-driven task mapping for lifetime extension of networks-on-chip based multiprocessor systems[END_REF] to balance the MTTF of NoC. However, at runtime the tasks are mapped on NoC-based MPSoC without considering the variation of runtime operating conditions. The reliability of NoC can also be improved through routing algorithms. Bhardwaj et al. proposed an aging-aware adaptive routing algorithm for NoC [START_REF] Bhardwaj | Towards graceful aging degradation in nocs through an adaptive routing algorithm[END_REF] [START_REF] Bhardwaj | An milp-based aging-aware routing algorithm for nocs[END_REF]. They introduced an aging model that defines stressed links and routers, in which the traffic of a router or link exceeds the upper limit called Traffic Threshold per Epoch (TTpE). However, the routing algorithm actually reduces the workloads of routers with high utilization, which may not exhibit the most aging effects. Different from their works, we directly apply reliability management to NoC, and propose a lifetime-aware routing algorithm to balance the lifetime distribution of NoC routers at runtime. The routing algorithm is based on the dynamic programming (DP) approach, which is proposed by Mak et al. [START_REF] Mak | A dp-network for optimal dynamic routing in network-on-chip[END_REF]. The dynamic programming approach is proposed for adaptive routing, in which the shortest path problem is solved optimally. The dynamic programming based adaptive routing has already been applied in congestion avoidance [START_REF] Mak | A dp-network for optimal dynamic routing in network-on-chip[END_REF], fault tolerance [START_REF] Zong | On multicast for dynamic and irregular on-chip networks using dynamic programming method[END_REF], thermal management [START_REF] Al-Dujaily | Dynamic on-chip thermal optimization for three-dimensional networks-on-chip[END_REF], etc.

Lifetime Budget Definition

For lifetime-aware routing algorithm, the lifetime reliability of routers should be provided for the algorithm to update routing decisions. There are mainly two methods to estimate lifetime reliability:

(1) Reliability is estimated through operating conditions history [START_REF] Zhuo | Process variation and temperature-aware reliability management[END_REF]. Using existing mathematical failure models, aging is periodically computed. At runtime, the operating conditions are monitored and provided for lifetime estimation.

(2) Aging sensors are used to monitor the aging effects of transistors [START_REF] Kim | Silicon odometer: An on-chip reliability monitor for measuring frequency degradation of digital circuits[END_REF]. For example, NBTI sensors are exploited to monitor the variation of threshold voltage, as the NBTI causes an increase on the threshold voltage of PMOS transistors. However, besides NBTI, the wear-outs of transistors are also incurred by other failure mechanisms such as EM, which could not be monitored by sensors explicitly.

In fact, both methods can be used for our lifetime-aware routing algorithm because the lifetime-aware routing is independent of lifetime estimation. The primary objective of this chapter is on lifetime-aware routing for lifetime optimization. We adopt the first method for lifetime estimation, i.e, the lifetime of routers are estimated from temperature and workload stresses history. We also present a hardware implementation for lifetime estimation in Section 4.5.

For long term reliability management of routers, we only consider wear-out related faults. The failure rate, a metric for lifetime reliability, keeps almost constant if the operating conditions (e.g. constant current, temperature, frequency and voltage) keep unchanged. The mean time to failure (MTTF) is inverse of failure rate when the operating conditions are constant. The MTTF due to EM is based on Black's equation [START_REF]Failure mechanisms and models for semiconductor devices[END_REF] as follows

M T T F ∝ (J -J crit ) -n exp (E a /kT ) ( 1
)
where J is the current density; J cris is the critical current density; E a is the activation energy; k is the Boltzmann's constant; T is temperature. n is a constant depend on interconnect metal used. However, this equation only assumes steady operating conditions, which is not realistic. The operating conditions (temperature, current density) are usually varying due to workload variation. Lu. et al. [START_REF] Lu | Interconnect lifetime prediction for reliability-aware systems[END_REF] derived MTTF under time-varying current density and temperature stresses as

T f = A E [ j(t) ( exp( -Q kT (t) ) kT (t) )] (2)
where A is a constant related to the structure. j(t) is current, and T (t) is temperature. The varying failure rate, also called lifetime consumption rate, is denoted

as λ(t) = j(t) ( exp( -Q kT (t) ) kT (t)
)

. The MTTF is the inverse of failure rate expectation value. Eq. 2 is based on the assumption of Electromigration (EM) failure mechanism. We only consider EM because EM is the primary aging factor for interconnection, and the reliability of both routers and links are closely related to interconnection. Based on Eq. 2, we also derive an equation as an approximation relationship between λ(t) and the routers workload. The current is j

(t) = CV dd W H × f × p [26]
, where p is switch activity. The voltage and frequency are assumed constant. In a router, switch activity is proportional to the incoming rate of a router because the incoming flits are assumed the only stimuli to the allocator. The failure rate can be represented as follows:

λ(t) ∝ d(t) ( exp( -Q kT (t) ) kT (t) ) (3)
where d(t) is the flits incoming rate at time t. The flits incoming rate is the number of flits passing through the router per unit time. The incoming rate also stands for the workload of a router. It is assumed that the ports of the incoming flits are not considered. The equation provides an approximated relationship between the lifetime and routers workloads.

Another equation derived in [START_REF] Lu | Interconnect lifetime prediction for reliability-aware systems[END_REF] is

∫ T f 0 r(t)dt = C,
where C is a constant. In the equation, lifetime is modeled as a resource consumed over time. As suggested by [START_REF] Lu | Interconnect lifetime prediction for reliability-aware systems[END_REF], we define a lifetime budget for each router, denoted as

LB(t) = ∫ t 0 (λ nominal -λ(t))dt (4)
where λ nominal is derived from the specified expected lifetime, indicating the constant lifetime consumption rate under nominal conditions. λ nominal is the inverse of expected MTTF, i.e., λ nominal • T f = C. If LB(t) > 0, the expected lifetime could satisfy the predefined constraint, and vice versa. The failure rate is related to operating conditions, i.e., temperature and workload, which are monitored periodically. Under discrete monitored conditions, the lifetime budget is represented as

LB(n) = { 0, if n is 0 LB(n -1) + λ nominal -λ(n), Otherwise (5)
where LB(n) and λ(n) are the lifetime budget and failure rate respectively at the n-th time interval. The lifetime budget indicates the maximum allowed failure rate for current the period. Therefore, the lifetime is modeled as a source of routers to be consumed over time. The router with higher workloads consumes the lifetime source at a faster speed.

From the perspective of packets, the selected path determines the workloads of the routers along the path. Therefore the routing algorithm, which determines the routing paths, plays an important role in the lifetime distribution of routers. In following sections, we propose a lifetime-aware routing algorithm to balance the lifetime distribution of routers.

Lifetime-Aware Adaptive Routing

Since MTTF or failure rate of a router is relevant to the flits incoming rate and temperature. We propose to balance the MTTF of routers through an adaptive routing algorithm. In this section, we first define a problem for lifetime reliability optimization and present the dynamic programming formulation for the problem. Then we propose an adaptive routing algorithm for lifetime reliability optimization. Table 1 summarizes all notations in this section. The optimal cost from s to d in LP form

V * (s, d)
The optimal cost from s to d in DP form

V (k) (s,
Cost(p) = ∑ k-1 i=0 C i,i+1
. We aim to find the path with the maximum cost of the path, denoted as V (s, d). The problem can be formally formulated as a linear optimization problem. Let u be a neighbor node of s, and on the one of the minimal distance paths. We have a constraint

V (s, d) ≥ V (s, u) + C u,d .
We can obtain the following linear programming: maximize

∑ ∀s∈V V (s, d) subject to V (s, d) ≥ V (u, d) + C s,u V (d, d) = 0 (6)
The above formation yields the optimal path from any nodes s to the destination node d, known as multiple-source single-destination longest path problem. With the nodes corresponding to the routers, the key idea of the adaptive routing is to use lifetime budget as the cost for the path, denoted as

C ri,ri+1 = LB i ( 7
)
LB i is the lifetime budget of the i-th router r i . The total lifetime budgets along the path p = ⟨r 0 = s, ..., r k-1 = d⟩ is

C s,d = k-1 ∑ i=0 LB i ( 8
)
Taking lifetime budget as the cost, the problem is to find a path with maximum lifetime budgets.

Dynamic Programming-based Formulation

Background of Dynamic Programming Dynamic programming (DP) is an optimization technique which was first introduced by Richard Bellman in the 1940s [START_REF] Bellman | Dynamic Programming[END_REF]. DP has been applied in a variety practical problems, in which the main complex problem can be broken into simpler subproblems. It provides a systematic procedure for determining the optimal combination of decisions which takes much less time than naive methods. In contrast to other optimization techniques, such as linear programming (LP), DP does not provide a standard mathematical formulation of the algorithm. Rather, DP is a general type of approach to problem solving, and it restates an optimization problem in recursive form, which is known as Bellman equation. The optimization or decision-making problems can be expressed in a recursive form as follows:

V i (t) = max ∀k {R i,k (t) + V k (t)}, ∀i (9)
where V i (t) is the expected reward of the i-th state and R i,k (t) is the reward of transition from state i to state k.

DP Formulation

The problem to find a path with maximum cost can also be stated in the form of dynamic programming, which defines a recursive process in step k. To obtain the optimal cost from node s to d, the process requires the notion of cost-to-go function, which is expect cost from node s to d. Based on the Bellman equation, the expected cost is updated recursively until the optimality criteria is reached. The Bellman equation can be expressed as

V (k) (s, d) = max ∀u∈V { V (k-1) (u, d) + C s,u } (10)
V (k) (s, d) is the cost from s to d at the k-th iteration. The cost C s,u is associated with lifetime budget. Initially, u = d and V (0) (d, d) = 0. Then Eq. 10 is solved recursively and the recursion is expanded from s to d. After k iterations, the optimal cost from s to d is V * (s, d), which is maximum among all minimal distance paths P s,d . The optimal cost is represented as following equation:

V * (s, d) = max {r0=s,...,r k-1 =d}∈P s,d { k-1 ∑ i=0 LB i } (11)
At each node s, the optimal decision that leads to the optimal path to d can be obtained from the argument of the maximum operator at the Bellman equation as follows:

µ(d) = arg max ∀j {V * (N (j), d) + LB s } ( 12
)
where j is the optimal decision, which represents the optimal output port or output direction. N (j) is the neighbor node in the direction j. LB s is the lifetime budget of node s.

Compared with linear programming, the dynamic programming presents an opportunity for solving the problem using parallel architecture and can greatly improve the computation speed.

Lifetime-Aware Adaptive Routing Algorithm

We propose a dynamic programming-based lifetime-aware adaptive routing algorithm, which is outlined in Algorithm 1. This algorithm outputs the direction to be taken for current node s. First, according to the positions of local node and destination node, the available directions D s are restricted to the minimal distance paths to destination (line 1). If the local node is the destination, the optimal cost is 0 and the routing direction is local port. Given an available direction j ∈ D s , the expected cost is computed by adding up the local cost LB s and the optimal cost from neighbor node N (j) to d (lines 6-8). The maximum cost is obtained by taking the maximum value from all V j (s, d), which are the costs of the paths that local node s takes direction j (line 9). Finally, the optimal direction µ(d) is obtained from the argument of the maximum operator (line 10). The dynamic programming-based adaptive algorithm outputs an optimal direction for each router. In the algorithm, the loop is realized in dynamic programming network. The optimal value for local node is propagated to the all neighbor nodes through dynamic programming network. The computational-delay complexity can be reduced to linear. In this chapter, the routers are assumed wormhole flow control without virtual channel. Deadlock can effectively be avoided by adopting one of the deadlock-free turn model. We adopt west-first turn model for deadlock avoidance [START_REF] Dally | Deadlock-free message routing in multiprocessor interconnection networks[END_REF].

Dynamic Programming Network

The dynamic programming network, introduced by Mak et al. [START_REF] Mak | A dp-network for optimal dynamic routing in network-on-chip[END_REF], is composed of distributed computation units and links. Figure 2 presents an example of 3×3 dynamic programming network. The dynamic programming network is coupled with NoC. Each computation unit implements the DP unit equations e.g. longest path calculations, and propagates the numerical solution to neighbor units. In addition, routing tables are implemented in routers. Algorithm 1 presents the operations required for updating the routing directions using the DP unit. The routing table will be updated periodically by the DP unit. For each router, the temperature and flits incoming rate are also monitored periodically. Failure rate is computed through the lifetime budget computation unit, which is presented in Section 4.5. According to the computed failure rate and nominal failure rate, the lifetime budget is updated. The lifetime budget values also propagated to the DP units as the DP costs. The dynamic programming network quickly resolves the optimal solution and passes the control decisions to routers, then the routing tables are updated.

The DP network presents several features to NoC: (1) The distributed units enable a scalable monitoring functionality for NoC. Each unit monitors local information and communicates with neighbor units, achieving a global optimization.

R R R R R R R R R V(i)
(2) The DP network can provide a real-time response without consuming data-flow network bandwidth due to the simplicity of the the computational unit.

(3) The DP network provides an effective solution to the optimal routing. To converge to the optimal solution, the delay of DP network depends on the network topology. Mak et al. have concluded that the network convergence time is proportional to the network diameter, which is the longest path in the network [START_REF] Mak | Adaptive routing in network-on-chips using a dynamic-programming network[END_REF].

Lifetime Budget Runtime Computation

The failure rate computation is an exponential function, not applicable for runtime computation. Similar to the methods proposed in [START_REF] Zhu | Reliable multiprocessor system-on-chip synthesis[END_REF], we use lookup tables that fit with Eq. 3 to pre-calculate failure rate. The runtime computation process is accelerated. To compute the lifetime budget at runtime, we design a hardware unit called lifetime budget computation unit (LBCU). The architecture of LBCU is presented in Figure 3. The temperature related part

( exp( -Q kT (t) ) kT (t)
) is pre-computed and kept in a lookup table. Each entry is corresponding to a temperature range. Another potential problem is that it may require much area to multiply with the incoming flit rate. Instead of computing the multiplication at the end of each time interval, we compute the failure rate per cycle. As shown in Figure 3, E, S, W, N, L are from 5 ports of a router, indicating whether there is a flit in current cycle. The failure rate per cycle is computed by multiplying the lookup table result with the sum of the ports. Because the maximum number to be multiplied is 5, the multiplication is only achieved by shifting and addition in stead of a multiplier. A counter is used to judge if it reaches the end of the time interval. At the end of the time interval, the lifetime budget is attained through addition. Despite of a little accuracy loss, the lifetime budget computation is accelerated at runtime while only some basic logic units are used. The implementation of LBCU will be evaluated in terms of area in Section 5.7.

Experimental Setup

Experiments are performed using Noxim simulator, which is an open source Sys-temC simulator for mesh-based NoC. In Noxim, the power of routers are modeled using ORION 2.0 NoC power simulator [START_REF] Kahng | Orion 2.0: A power-area simulator for interconnection networks[END_REF]. To model the temperature, we adopt HotSpot thermal model [START_REF] Huang | Hotspot: a compact thermal modeling methodology for early-stage vlsi design[END_REF]. The thermal configuration is the default configuration of HotSpot. To be more accurate, we adopt the floorplan of Tilera64 processor [START_REF] Bell | Tile64 -processor: A 64-core soc with mesh interconnect[END_REF] as the input of HotSpot. The frequency of NoC is configured 1 GHz. The simulation runs for 10 7 cycles. The time interval for temperature monitoring is 5000 clock cycles. And the routing tables and lifetime budgets are only updated at the end of each time interval. We employ Electromigration as the failure mechanism. The buffer depth is 10 flits and the packet size is 5 flits. In the experiments, we compare the lifetime-aware routing algorithm with XY routing, NoP routing and Oddeven routing, respectively. The NoP routing algorithm, a congestion-aware routing, is the west-first turn model with neighbors-on-path (NoP) selection scheme; the Oddeven routing is the oddeven turn model [START_REF] Chiu | The odd-even turn model for adaptive routing[END_REF] with random selection scheme. Besides, the evaluations are also performed over a suite of benchmarks: 9 benchmarks in PARSEC [START_REF] Bienia | The parsec benchmark suite: Characterization and architectural implications[END_REF] and 2 benchmarks in SPLASH-2 [START_REF] Woo | The splash-2 programs: characterization and methodological considerations[END_REF]. The benchmarks are listed in Table 2. This experiments are performed in an in-house developed simulator [START_REF] Wang | On selftuning networks-on-chip for dynamic network-flow dominance adaptation[END_REF]. The configurations for the simulator are listed in Table 3.

MTTF Distribution

As comparisons with the case study mentioned in Section 1, we evaluate the MTTF distribution of the lifetime-aware routing and NoP routing. The injection rate is also 0.005 flits/cycle; the NoC size is 8×8. Figure 4 presents the histogram of lifetime distribution. For the lifetime-aware routing, the MTTF distribution is more concentrated than others, namely, the MTTF is more evenly distributed.

Minimal MTTF Evaluation

The minimal MTTF router is the router with the highest probability to wear out. Because the minimal MTTF is critical for the system lifetime, we evaluate the minimal MTTF of routers, expressed in min{M T T F i }. The evaluation is under synthetic traffic. The traffic pattern is set random and the injection rate is set 0.005 flits/cycle. The routing algorithms are also compared in different NoC size, 8 × 8,10 × 10, 12 × 12. The results are shown in Table 4. In the table, the minimal MTTF value is evaluated. The evaluation metric is hour. It can be observed that the lifetime-aware routing has around 20%, 45%, 55% minimal MTTF improvement than XY routing, NoP routing, Oddeven routing, respectively. Additionally, the minimal MTTF also decreases dramatically with NoC size, because the workloads of routers increase with the area of NoC. The MTTF improvement against XY routing is relatively smaller as the XY routing also brings relatively less traffic for the routers in the central region.

We also evaluate the minimal MTTF with real benchmarks. The experimental results are demonstrated in Figure 5. Here all the minimal MTTF values are normalized to the values under lifetime-aware routing. The minimal MTTF under lifetime-aware routing is highest, which is consistent with previous results. In addition, the minimal MTTF under different benchmarks varies a lot because the workloads are inherently unbalanced.

NoC Overall MTTF Evaluation

We take NoC as a whole and evaluate the overall MTTF of NoC. This based on the assumption that NoC fails when a router fails. Therefore, the failure rate of NoC is the sum of all routers, denoted as λ N oC = ∑ N i=1 λ i . The MTTF of NoC is calculated according to Eq. 2. We evaluate the MTTF of NoC under real benchmarks with 4 different routing algorithms. The results are presented in Figure 6. From the results, we found that the lifetime-aware routing leads to around 5% NoC MTTF improvement due to its better lifetime distribution. Normalized NoC MTTF Fig. 6. NoC MTTF evaluation with real benchmarks However, the overall MTTF cannot effectively reflect the reliability of routers. The unbalanced lifetime distribution would make some routers age much faster despite of the small differences of overall MTTF. An example is illustrated in [START_REF] Ramachandran | Metrics for architecture-level lifetime reliability analysis[END_REF], showing that overall MTTF metric is not adequate for overall reliability specification.

Variance of MTTF

Besides overall MTTF, we also use the MTTF variance metric to show that the lifetime-aware routing distributes the lifetime more evenly. The results are shown in Figure 7. In the figure, the MTTF variance is normalized for comparisons. The lifetime-aware routing algorithm exhibits the less variance, showing that the lifetime distribution is more balanced.

Average Packets Delay Comparison

To evaluate the impacts on the global average delay, the lifetime-aware routing is also compared with the other three routing algorithms. The global average delay is evaluated with random traffic pattern. The buffer size is configured 10 flits.

The comparisons under flits injection rate from 0.01 to 0.17 flits/cycle. The experimental results are shown in Figure 8. The delay is measured in cycles. It can be observed that the saturated flit injection rate of the lifetime-aware routing is around 0.10 flits/cycle, which is 0.02 less than oddeven routing, 0.03 less than NoP routing, and 0.04 less than XY routing. Therefore, when the injection rate is less than 0.10 flits/cycle, these routing algorithms have similar performance in terms of average packet delay. However, the lifetime-aware routing achieves longer life while has smaller saturation point. It is concluded there is a trade-off between lifetime and performance (average packet delay).

Hardware Evaluation

We implement lifetime budget computation unit (LBCU) with Verilog HDL and compare LBCU with router in terms of area. The lookup table of LBCU contains 64 entris to keep pre-computed values, which corresponds to different temperature ranges. The size of each entry is 32 bits. The registers for lifetime budget and failure rate value are 32 bits. The router is open-source and developed by Becker [START_REF] Becker | Efficient microarchitecture for network-on-chip routers[END_REF]. The frequency is 1 GHz. The router is 5-ports input-buffered with wormhole flow control. The buffer size is 4 flits; the flit size is 75 bits. It can be concluded that LBCU leads to around 5.13% increase in terms of area. In other words, LBCU can be integrated with NoC with low overhead. In addition, the cost of dynamic programming network is not evaluated in this work. The detail evaluation for dynamic programming network can refer to [START_REF] Mak | A dp-network for optimal dynamic routing in network-on-chip[END_REF].

Conclusions and Future work

In this chapter, we propose a dynamic programming-based lifetime-aware routing algorithm for NoC reliability management. First, we define a lifetime budget metric for each router. With this metric, a problem is defined to optimize the lifetime by routing packets along the path with maximum lifetime budgets. We propose a lifetime-aware routing algorithm using dynamic programming approach. Finally, the lifetime-aware routing algorithms are evaluated in synthetic traffic and real benchmarks. The experimental results show that the lifetime-aware routing can distribute the lifetime of routers more evenly. The lifetime-aware routing has around 20%, 45%, 55% minimal MTTF improvement than XY routing, NoP routing, Oddeven routing, respectively.

In the future, we plan to optimize both the lifetime distribution of routers and the average packet latency. This is because we observe that the lifetime-aware routing algorithm lowers the performance in terms of average packet delay. A hybrid routing algorithm will probably be proposed taking consideration of both packet delay and lifetime of routers. Similar to [START_REF] Mercati | Workload and user experience-aware dynamic reliability management in multicore processors[END_REF], the lifetime is optimized in long-term scale while the performance is optimized in shor-term scale. Thus the lifetime can be improved without having much impact the performance. Another possible future work is to exploit the traffic throttling [START_REF] Chang | Hat: Heterogeneous adaptive throttling for on-chip networks[END_REF] or DVFS in NoC to maintain the MTTF of NoC above an expected value. This is because the lifetime reliability depends on the voltage, frequency and switching activity. The problem can be defined as maximizing performance given fixed lifetime budget. This is similar to the power budgeting problem [START_REF] Wang | Fine-grained runtime power budgeting for networks-on-chip[END_REF] [29] which maximizes performance under limited power budget. However, the lifetime budgeting is different as the aging process is in a long-term scale. Therefore, the strategies for lifetime budgeting is possibly quite different from power budgeting. In the future work, we will exploit novel strategies for lifetime budgeting problem.

Fig. 1 .

 1 Fig. 1. A case study for motivation. In 8 × 8 NoC, the Normalized MTTF of routers is evaluated under different routing algorithms

4 . 1

 41 d) The expected cost for s after k steps P s,d Available paths from s to d ri The i-th router along a path from s to d µ(d) The optimal routing direction to node d N (j) The neighbor node in the direction j Problem Definition To balance the lifetime distribution, the lifetime-aware adaptive routing aims to find a path with maximum lifetime budget from designated path sets for each packet. Therefore we formulate a longest path problem as follows. Given a directed graph G = (V, A) with n = |V| nodes, m = |A| edges, and a cost associated with each edge u → v ∈ A, which is donated as C u,v . Given two nodes s, d ∈ V, P s,d is the set of minimal distance paths from s to d. The cost of a path p = ⟨s = v 0 , ..., d = v k ⟩ ∈ P s,d , from s to d, is the sum of the costs of its constituent edges:

Fig. 2 .

 2 Fig. 2. An example of 3 × 3 dynamic programming network coupled with NoC

Fig. 3 .

 3 Fig. 3. Lifetime Budget Computation Unit

Fig. 4 .

 4 Fig. 4. MTTF distribution of NoP routing and lifetime-aware routing

Fig. 5 .

 5 Fig. 5. Minimal MTTF evaluation with real benchmarks

Fig. 7 .

 7 Fig. 7. Variance of MTTF comparison with real benchmarks

Fig. 8 .

 8 Fig. 8. Global average delay comparison

Table 1 .

 1 Notations

	Symbols Semantics
	V	A set of nodes in network G
	A	A set of edges in network G
	LBi	Lifetime budget of the router i
	C u,d	Cost of edge u → d
	V (s, d)

Algorithm 1

 1 Lifetime-Aware Adaptive Routing

	Definitions s: local node;
		Ds: set of directions to minimal distance paths;
		N (j): the neighbor node in the direction j;
		Vj(s, d): the cost of the path taking direction j for s;
	Input d: destination node;
		V * (N (j), d): the optimal cost from N (j) to d;
		LBs: lifetime budget of node s,
	Output µ(d): the optimal routing direction to d;
		V * (s, d): the optimal cost from s to d.
	1: Calculate available direction Ds according to positions of s and d
	2: if s = d then
	3:	V * (s, d) = 0
	4:	µ(d) = LOCAL
	5: else
	6:	for all directions j ∈ Ds do
	7:	Vj(s, d) = V * (N (j), d) + LBs
	8:	end for
	9:	V

* (s, d) = max ∀j Vj(s, d) 10: µ(d) = arg max ∀j Vj(s, d) ◃ Update optimal routing directions 11: end if

Table 2 .

 2 Benchmarks

	PARSEC streamcluster, swaptions, ferret, fluidani-
	mate, blackscholes, freqmine, dedup, can-
	neal, vips
	SPLASH-2 barnes, raytrace

Table 3 .

 3 Simulator setup

	Number of cores	64 (MIPS ISA 32 compatible)
	L1 D cache	16KB, 2-way, 32B line, 2 cycles,
		2 ports, dual tags
	L1 I cache	32KB, 2-way, 64B line, 2 cycles
	L2 cache (shared)	64KB slice/node, 64B, 6 cycles,
	MESI protocol	2 ports
	Main memory	2GB
	Data packet size	5 flits
	Meta packet size	1 flit
	NoC flit size	72-bit
	NoC VC number	4
	NoC buffer	5 × 10 flits

Table 4 .

 4 Minimal MTTF comparisons under different routing algorithms (hours).

	NoC size XY	NoP	Oddeven Lifetime	MTTF improvement (Lifetime vs.) XY NoP Oddeven
	8x8	577490 453085 435682 683209	18.3%	50.8%	56.9%
	10x10	321487 264756 253358 393711	22.4%	48.7%	55.4%
	12x12	173618 144960 133637 203117	16.9%	40.1%	52.0%

Acknowledgment

This research program is supported by the Natural Science Foundation of China No. 61376024 and 61306024, Natural Science Foundation of Guangdong Province No. S2013040014366, and Basic Research Programme of Shenzhen No. JCYJ20140417113430642 and JCYJ20140901003939020.