Eduardo C Campos
email: eccampos@ufu.br

Martin Monperrus
email: martin.monperrus@univ-lille1.fr

Marcelo A Maia
email: marcelo.maia@ufu.br

Searching Stack Overflow for API-usage-related Bug Fixes Using Snippet-based Queries

Keywords: Software and its engineering → Software libraries and repositories; API-usage-related bugs, crowd debugging, crowd knowledge

Project-specific bugs are related to the misunderstanding or incomplete implementation of functional requirements. API-usage-related bugs are independent of the functional requirements. Usually they cause an unexpected and wrong output or behavior because of an incorrect usage of an API (Application Programming Interface). We propose an approach to find fixes for API-usage-related bugs, which is based on matching snippets being debugged against related snippets in a Q&A website (Stack Overflow). We analyzed real code excerpts from OHLOH Code Search containing API method calls that may lead to API-usage-related bugs depending on how they are used by developers. We conducted a study with these excerpts to verify to what extent the proposed approach provides proper information from Stack Overflow to fix these potential API-usage-related bugs. The results are encouraging: 66.67% of Java excerpts with potential API-usage-related bugs had their fixes found in the top-10 query results. Considering JavaScript excerpts, fixes were found in the top-10 results for 40% of them. These results indicate that our approaches (i.e., lsab-java and lsab-js combined with the keyword filter) outperform Google and Stack Overflow in searching for API-usage-related bug fixes.

INTRODUCTION

Developers frequently need to use methods they are not familiar with or they do not remember how to use [START_REF] Moreno | How Can I Use This Method?[END_REF]. Unfortunately, some of the most severe obstacles faced by developers learning a new API are related to its documentation, in particular because of scarce information about API's design, usage scenarios, and code examples [START_REF] Souza | On the Extraction of Cookbooks for APIs from the Crowd Knowledge[END_REF] [START_REF] Robillard | A Field Study of API Learning Obstacles[END_REF]. As a result, developers may write code inconsistent with API documentation and thus introduce bugs [START_REF] Zhong | Inferring Resource Specifications from Natural Language API Documentation[END_REF].

The battle against software bugs exists since software existed. It requires much effort to fix bugs, e.g., Kim and Whitehead [START_REF] Kim | How Long Did It Take to Fix Bugs?[END_REF] report that the median time for fixing a single bug is about 200 days. The process of debugging is strongly related to the nature of the bug. For example, debugging a segmentation fault means focusing on allocation and deallocation of memory, while debugging an error of NullPointerException means finding which line of code is accessing some attribute or operation (API element) on a null variable.

In this paper, we claim that there exists a class of bugs that relates to the common misunderstanding of an API. Those bugs have a common characteristic: they occur repeatedly in different contexts and they are independent of the application domain. For instance, there are plenty of JavaScript programmers who experienced that parseInt("08") returns 0 whereas the expected result is 8. This class of bugs is called "API-usage-related bugs", because it is likely that this kind of bug has already occurred several times and there exists a description of the problem somewhere on the web, along with its explanation and fix. In other terms, the crowd has already identified the bug and its solution.

Generally speaking on debugging, one common limitation of research techniques that support automating or semiautomating debugging is their reliance on a set of strong assumptions on how developers behave when debugging (e.g., the approaches tend to assume perfect bug understanding) [START_REF] Parnin | Are Automated Debugging Techniques Actually Helping Programmers?[END_REF]. A more flexible solution would allow developers to inform a suspicious code snippet and get extra knowledge that would help understanding what would be possibly wrong with that pattern of code. In fact a common behavior of developers is to post pieces of code that contain bugs in question-answer (Q&A) sites, in order to obtain a diagnosis of correction for that particular bug. Treude et al. [START_REF] Treude | How do programmers ask and answer questions on the web?[END_REF] pointed out that Stack Overflow (SO) is particularly effective for code reviews, for conceptual questions and for novices.

So, for programmers who experience an API-usage-related bug, the SO crowd can be asked for a way to fix the bug using their own suspicious snippets. However, such approach would require an effective way to search the crowd knowledge using suspicious code snippets.

General purpose search engines were not designed to receive snippets as queries: typically these engines do not work well with large queries. Alternatively, different code mining techniques and tools have been proposed to retrieve rele-vant software components from different repositories with the aim of assisting developers during the software reuse process (e.g., Sourceforge 1 , Google Code Search 2 , Exemplar [START_REF] Mcmillan | Exemplar: A Source Code Search Engine for Finding Highly Relevant Applications[END_REF]). However, these customized code search engines were designed to index all information of software projects (e.g., help documentation, API calls used inside each application, textual descriptions of applications, etc.) instead of only code snippets. Moreover, code search engines were not designed to allow snippets being used as query. For instance, Google Code Search allows regular expressions and typical fields, such as, file/class/method names. Other engines like, Sourceforge and Exemplar allow keywords as input. In other words, these kind of engines are not suitable to match developers' snippets with crowd's snippets.

Therefore, our approach aims to recommend posts of SO whose code match developers' snippets. The motivation is that the answer's text provided by SO community members along with the code snippets could be helpful to assist developers during the debugging tasks at hand because they show how to use these code snippets, i.e., the whole post may help to overcome the cognitive distance [START_REF] Krueger | Software Reuse[END_REF] to understand problems in these code snippets.

To sum up, our contributions are as follows:

• An empirical analysis of code-snippet matching using code snippets of SO written in Java and JavaScript programming languages. This analysis showed that the built-in search engine of SO is not adequate when used with code snippets as input query;

• The construction of specific indexes for Apache Solr 3 containing lexical and syntactic information of source code snippets written in Java and JavaScript programming languages. Those indexes serve as core infrastructure for a recommendation system;

• The construction of a dataset containing 30 code excerpts (i.e., snippets) with potential API-usage-related bugs picked from OHLOH Code Search 4 (i.e., 15 excerpts in Java and 15 in JavaScript) and 30 posts of SO that fix the respective potential API-usage-related bug;

• Our recommendation strategies for code excerpts with potential API-usage-related bugs (i.e., lsab-java and lsab-js combined with the keyword filter) outperform Google and SO, and 66.67% of Java excerpts and 40% of JavaScript excerpts could have a proper recommendation in the top-10 results.

The remainder of this paper is organized as follows. Section 2 presents the concept of API-usage-related bugs and an empirical study of them. Section 3 presents the methodology of our work. Section 4 presents the experiments performed with code snippets of SO. Section 5 shows the experiment conducted with code excerpts that contain potential APIusage-related bugs. Related work is surveyed and shown in Section 6. In Section 7, we draw our conclusions.

API-USAGE-RELATED BUGS

API-usage-related bugs are not bugs in functions or methods of an API. In this paper, we suppose that the API does not contain bugs. API-usage-related bugs occur due to an incorrect usage of the functions or API methods by the developer. In opposition to API-usage-related bugs, project-specific bugs relate to misunderstanding or incorrect implementation of domain concepts.

Definition: An "API-usage-related bug" is a bug that causes an unexpected and wrong output or behavior resulting from an incorrect usage of an API.

Let us illustrate the definition with some examples. In Java, there is a method of "java.lang.Math" library called cos. The full signature of this method is "public static double cos(double)". The argument of this method is an angle, in radians. This method returns the trigonometric cosine of an angle. Despite this apparently simple description and self-described name, this method poses problems to many developers, as witnessed by the dozens of Q&As on this topic on Q&A websites5 . Many Q&As relate to the same issue: Why does Math.cos() give a wrong result?. One of the reasons is that if the argument of Math.cos is passed in degrees rather than radians, the method gives wrong result. Why is the question asked again and again? We hypothesize that the semantics of Math.cos is counterintuitive for many people (they erroneously assume that the angle must be passed in degrees), and consequently, the very same issue occurs in many development situations, independently of the domain. The fix for this problem is to use the method Math.toRadians to convert an angle to radians, i.e., "Math.cos(Math.toRadians(angle))".

Let's consider another example in JavaScript. There is a function called parseInt, which parses a string given as input and returns the corresponding integer value. This function also poses problems to many developers, as witnessed by the dozens of Q&As on this topic on Q&A websites 6 . Again, many Q&As relate to the same issue: Why does par-seInt("08") produce 0 and not 8?. The answer is that if the argument of parseInt begins with 0, it is parsed as octal (base 8). The fix for this problem is to specify the base. We hypothesize that the semantics of parseInt is counterintuitive for many people (they erroneously assume that the base is 10 rather than 8, perhaps because of the numerical decimal system is most frequently used in general operations involving numbers).

How to fix API-usage-related bugs? To fix APIusage-related bugs, we propose a system that relies on code snippet matching between the suspicious snippet under debug and the related pieces of code present in the SO questions. When facing an API-usage-related bug, the developer would ask our system to be pointed to relevant answer on SO. Our system is based on the fact that Q&As of SO often contain API-usage-related bug fixes. To sum up, to fix an API-usage-related bug, ask the crowd using your suspicious snippet [START_REF] Monperrus | Debugging with the Crowd: a Debug Recommendation System based on Stackoverflow[END_REF].

Why does our approach use code snippets as input query instead of terms? We claim that searching for bug fixes using snippets instead of terms is more suitable to fix API-usage-related bugs because understanding the root cause of a failure for developers typically involves complex activities such as navigating program dependencies and rerunning the program with different inputs [START_REF] Parnin | Are Automated Debugging Techniques Actually Helping Programmers?[END_REF]. Moreover, API-usagerelated bugs do not have exception stack traces that allow to locate the counter-intuitive API method.

Where do API-usage-related bugs come from? They appear when a developer of an API makes design decisions that go against the common sense, "common sense" being defined as the intuition and expectation being hold by many developers. In the parseInt example, most people expect that parseInt("08") returns 8. We see at least three main reasons behind API-usage-related bugs:

• First, the API under consideration may be poorly documented [3][31]. For example, the official documentation of the API can not contain code snippets that teach how to use a particular API method [START_REF] Moreno | How Can I Use This Method?[END_REF][24][29];

• Second, the API under consideration may seem comprehensible enough for some developers who do not read the documentation;

• Third, the API may assume something implicitly. For instance, parseInt implicitly assumes that prefixing the string with "0" means that an octal base is chosen.

A detailed study of why API-usage-related bugs appear is out of scope of this paper, it requires inter-disciplinary work between different fields such as software engineering and psychology.

Beyond the toy examples we have just discussed so far, there should be sufficient API-usage-related bug fixes on SO to motivate a recommendation system for this kind of bug. However, it is not possible to manually assess whether the millions of posts of SO refer to API-usage-related bugs or not. Hence, we need an automated technique to assess approximately the space of "API-usage-related bug fixes". This estimate has the only goal to know if there are sufficient occurrences of these kind of fixes to motivate a recommendation system.

We adopted the following criteria to identify SO threads (question + answers) as potentially containing an "API-usagerelated bug fix". First, it must contain one snippet in the question since our proposed approach consists of understanding the piece of code queried in our recommendation system. Second, they should be limited to a particular language. Third, they should have an accepted answer to be sure that the crowd was able to solve the bug. In order to select Java or JavaScript API-usage-related bugs, we use a filter on the tagging metadata of the question (i.e., we select questions if and only if they are tagged by "javascript" or "java"). The March 2013 dump of SO contains 3,389,743 posts. By applying the 3 filters aforementioned, we obtain 179,885 and 197,158 posts for Java and JavaScript, respectively. In our opinion, these values are sufficient numbers, supporting our intuition that there is a wealth of information in API-usage-related bug fixes on SO.

METHODOLOGY

In this section, we present four research questions about code snippet search and API-usage-related bugs (RQ1, RQ2, RQ3 and RQ4), the programming topics that will be subject of assessment, the preprocessing functions for code snippets and the local SO database used to conduct experiments with SO code snippets (i.e., Experiments I and II).

Before detailing the experiments, we will briefly explain what is indexing. The standard technique of indexing-based search consists of two transformation functions t index and tquery. The first function t index transforms the documents (i.e., posts of SO) into terms, and the second function tquery transforms the query into terms as well. The ranking consists of matching the document terms against the query terms. The functions t index and tquery are not necessarily identical, since the nature of documents (style, structure, etc.) is often different from the nature of queries.

In our proposed approach, the terms are preprocessed code snippets. Moreover, the result of a search on Apache Solr's index is a ranked list of documents (i.e., posts of SO), in which the first one is the more similar to the search query and the last one is the less similar. Each post in this ranking has a numeric value that we call Solr's score that represents its similarity to the query (i.e., it is done by Apache Solr in the current implementation). Thus, the first post of the ranking has the greater Solr's score and the last one has the smallest value.

Research Questions

This subsection presents the four research questions considered in the study.

RQ1: What is the accuracy of SO query mechanism when input queries are code snippets?

The research question RQ1 intends to investigate whether the search engine of SO can cope well with snippet-based queries. Experiment I will be conducted to answer this research question. Given a code snippet present in some post of SO and using this same code snippet as input to the built-in search engine of SO, we want to assess how well this search engine can find the post that contains the queried code snippet.

RQ2: Which indexing mechanism for code snippets is more effective for the topics considered in this study: the native index of SO site or a customized index using Apache Solr?

The research question RQ2 intends to investigate whether the construction of Apache Solr indexes containing information of code snippets improves the code-based queries. We compared the results obtained in the Experiment I with the results obtained in the Experiment II.

RQ3: Which preprocessing function for code snippets best improves the effectiveness of Solr indexes?

The research question RQ3 intends to investigate to what extent the use of preprocessing functions for code snippets during the phases of indexing and querying improves the efficacy of code-based query and which preprocessing function provides the best improvement. We conducted the Experiment II to answer this research question. In this experiment, we build different indexing alternatives for Apache Solr.

RQ4: How effective is the ranking produced by the proposed recommendation system to find fixes for potential API-usagerelated bugs?

The research question RQ4 intends to investigate how the proposed recommendation system copes with potential API-usage-related bugs present in the code excerpts of real software projects. We conducted the Experiment III to answer this research question. This experiment is dedicated for potential API-usage-related bugs and uses code excerpts picked from real software projects hosted on OHLOH Code Search website7 . These code excerpts contain some API method calls that can lead to API-usage-related bugs. We collected a sample of API method calls on SO site that have this behavior in order to build a dataset with potential API-usage-related bugs.

Considered Topics

We considered the following topics in our study: Java Android, Java non-Android and JavaScript. We decided to investigate Java Android separately because mobile application development is a trendy topic, with an upward-tendency that increments fast [START_REF] Linares-Vásquez | An exploratory analysis of mobile development issues using Stack Overflow[END_REF]. By also considering plain Java Q&As, we can investigate whether our preprocessing functions for code snippets behave according to specific software platforms (such as Android). The JavaScript related Q&As explore the domain of web development which is among the most active topics on SO.

Preprocessing functions for code snippets

Code snippets have a different nature compared to natural language texts. So, traditional information retrieval techniques for text preprocessing may not produce the desired terms for index construction. We define some preprocessing functions for code snippets and constructed specific indexes of Apache Solr using these functions in order to perform the Experiments I, II and III. We investigated six preprocessing functions listed below for the Java and JavaScript programming languages.

Function "raw"

This identity function does not modify the content of the piece of source code, i.e., does not perform any code preprocessing.

Term Extraction for Java and JavaScript (pp1)

This function returns all alphanumeric sequences present in the code snippet using the regular expression "[0-9a-zA-Z $]+". The main desired effect is to remove all punctuation characters.

Syntactic Function for Java (pp2)

This function considers elements of the context-free grammar of the language: it processes the Java code snippet and returns a set of compound terms corresponding to nodes of the abstract syntax tree of this code snippet. They are: type in variable declaration (e.g., int), method signature (e.g., void onAnimateMove[float, float, long]) and method invocation (e.g., onAnimateMove). We use the Eclipse JDT Core Component8 to generate the abstract syntax tree for the code snippet.

Lexical Function for JavaScript (pp3)

This function returns a list of lexical values (i.e., variable names and string literals) for the JavaScript code snippets using the Rhino API9 .

Lightweight Syntactic Analysis and Binding for Java (lsab-java)

This function processes the Java code snippet and extracts their API method calls. The characteristics of this parser are:

• Lightweight Syntactic Analysis: the parser processes the code snippet and identifies all variable declarations and all API method calls occurring in the code snippet (e.g., Calendar x; produces the term Calendar);

• Lightweight Binding: the parser resolves the bindings identified in the previous step, i.e., the syntactic analysis phase (e.g., Calendar x; x.getInstance() => the variable access "x" is replaced by the respective type, resulting in term Calendar.getInstance()). Moreover, this parser generates as output the terms: Calendar.getInstance and getInstance. We decided also to index the method name (i.e., the name that appears after the ".") to cover the cases where it is not possible to resolve the binding (i.e., some code snippets of SO do not have the variable declaration statement).

Lightweight Syntactic Analysis and Binding for JavaScript (lsab-js)

This function processes the JavaScript code snippet and extracts their API method calls. It performs the same steps made by the parser lsab-java, but contains parsing routines specific to the JavaScript language (e.g., the word "function" is a reserved word of the JavaScript language while this same word is not a reserved word of the Java language). When a developer declares a specific application domain function, the reserved word "function" is used (e.g., function functionName()). In this study, we decided not to index the names of application domain functions, since we are interested only in the API method calls. The project-specific texts (e.g., project method name) would not match the bug appearing in the Q&A web site [START_REF] Gao | Fixing Recurring Crash Bugs via Analyzing Q&A Sites[END_REF].

Table 1 shows the preprocessing functions for code snippets per type (i.e., No preprocessing, Lexical and Syntactic) and programming language (i.e., Java and JavaScript) considered in this study.

Local SO Database

We downloaded a release of SO public data dump 10 (the version of March 2013) and imported the data into a relational database in order to perform experiments with SO code snippets. The "posts" table of this database stores all questions posted by questioners in the website until the date the dump was built (3,389,743 questions). This table also stores all answers to each question, if any. docs/Mozilla/Projects/Rhino 10 http://blog.stackoverflow.com/category/cc-wiki-dump/ We used the Java library HTML Cleaner 11 in order to extract the code snippets of the questions and answers of SO. We have identified the presence of code snippets in the posts of SO through the use of HTML tags "<pre> <code>...". The next section shows the experiments with SO snippets conducted in this study.

EXPERIMENTS WITH CODE SNIPPETS FROM SO

We conducted some experiments with the search engine of SO and the search engine of Apache Solr to answer the research questions (RQ1, RQ2, and RQ3). Subsection 4.1 aims to answer the research question RQ1 and presents the experiments conducted with SO native site index.

Experiment I: Querying SO native site index

We investigate whether the search engine of SO is able to cope well with code-based queries. Our idea was to query the search engine of SO using code snippets that already exist in SO. We consider that SO handles code-based queries well if the post that contains such code snippet is rated in the top-10 positions of search engine results. This situation corresponds to the case where the developer queries our recommendation system with a snippet that contains some potential APIusage-related bug and gets the fix for his problem. In cases where SO does not find the posts that fix these potential APIusage-related bugs, we say that this site does not respond well to queries that are code snippets. This is an indication that a special indexing technique needs to be developed for better search results. We conducted the following experimental procedure in the following order:

• Step 1: We randomly selected 1000 code snippets from SO for each of the topics considered in this study (i.e., "Java Android", "Java non-Android" and "JavaScript");

• Step 2: For each selected code snippet, we save the SO identifier of the post that contains the snippet;

• Step 3: We perform two different queries in the SO site for each picked code snippet: a query considering the code snippet in its natural state (i.e., function "raw") and another query considering the result generated by the preprocessing function "pp1" in the code snippet;

• Step 4: For each queried code snippet, we calculate in which position in the top-10 the post of SO that contains the code snippet under study (i.e., saved in

Step 2) appears in the ranking.

Experiment I enabled us to answer the research question RQ1.

11 http://htmlcleaner.sourceforge.net/ Summary of RQ1. The results of Experiment I showed that SO does not have good efficacy when dealing with code-based queries. In addition, this experiment confirms the results obtained by Monperrus et al. [START_REF] Monperrus | Debugging with the Crowd: a Debug Recommendation System based on Stackoverflow[END_REF]. This leads to: 1) preprocessing the code snippets to improve the efficacy of API-usage-related bug matching; 2) build several dedicated indexes containing the information of SO's snippets to investigate whether these indexes would be more suitable for code-based queries, i.e., whether these indexes would yield better results than using the SO native site index. We constructed all these dedicated indexes using the Apache Solr search engine.

Table 2 shows the results obtained in Experiment I.

4.2 Experiment II: Building and Querying the indexes raw, pp1, pp2, pp3, lsab-java and lsab-js of Apache Solr

We built eight Apache Solr indexes to answer research questions RQ2 and RQ3. They are: Java-raw, Java-pp1, Java-pp2, Java-lsab, JavaScript-raw, JavaScript-pp1, JavaScript-pp3, and JavaScript-lsab. Each index consists of all Java or JavaScript code snippets from local database processed with the respective preprocessing function (e.g., Java-lsab index consists of all Java code snippets from local database processed with the preprocessing function lsab-java).

As previously stated in Experiment I, for each topic (i.e., Java Android, Java non-Android and JavaScript), we use 1000 code snippets. These snippets were also used to perform the Experiment II. For each Java code snippet, we perform a query on each of the four indexes of Apache Solr (i.e., Javaraw, Java-pp1, Java-pp2, and Java-lsab). In the case that the code snippet is written in JavaScript, we perform a query in each of the four remaining indexes of Apache Solr (i.e., JavaScript-raw, JavaScript-pp1, JavaScript-pp3 and JavaScript-lsab).

For example: given a Java code snippet (i.e., the snippet belongs to the Java Android or Java non-Android topics), it is processed using the following preprocessing functions for Java code: raw, pp1, pp2, and lsab-java. After preprocessing the code using one of the preprocessing functions, the generated output is searched in the respective index of Apache Solr. We define the following rule in order to make the index terms (i.e., t index ) become as similar as possible to the query terms (i.e., tquery): Code snippets preprocessed with the function X only consult the Apache Solr index that was constructed using the same preprocessing function X.

Experiment II allowed us to answer the research questions RQ2 and RQ3. Summary of RQ2. The results of Experiment II show that searching in an index of Apache Solr previously constructed is much more effective than searching in the SO native site index. The column "Not Found" of Table 3 shows that in all indexes, the number of not found results was ≤ 26% (much less than those of Table 2, e.g., for JavaScript topic, we obtained 86% for t index = SO and tquery = pp1). Moreover, the column Rank ≤ 10 of Table 3 shows the high performance of all indexes in the code-based queries (≥ 61.8%). Summary of RQ3. In the Experiment II, the lexical function pp1 was better in all topics ("Java Android", "Java non-Android" and "JavaScript"), i.e., smaller amount of not found results than other preprocessing functions. The column "Not Found" of Table 3 showed that, in some cases, the functions pp2 and pp3 had a number of not found results greater than the raw function (i.e., for the topics "Java non-Android" and "JavaScript"). The lsab-java parser was much better on the topic "Java non-Android" than in the topic "Java Android". One possible explanation for this is that the topic "Java Android" not only uses the Java language for creating graphical user interfaces (GUIs), but also makes use of XML markup language. However, the parser lsab-java was not designed for processing XML.

Table 3 shows the results obtained in Experiment II. The column "Not Found" of Table 3 shows the amount of posts from SO not found in each index.

EXPERIMENT WITH POTENTIAL API-USAGE-RELATED BUGS

Now, we leverage the knowledge gained in the first three research questions (RQ1, RQ2 and RQ3) to study the efficacy of a recommendation system for API-usage-related bugs based on SO. To perform experiments with potential API-usage-related bugs present in different real-world software projects, it was necessary to build a dataset of potential API-usage-related bugs. The construction process of this dataset is a hard task. On SO, users ask different kind of questions. Nasehi et al. [START_REF] Nasehi | What makes a good code example? A study of programming Q&A in Stack Overflow[END_REF] identified four categories of questions related to the main concerns of the questioners and what they wanted to solve in SO: Debug-corrective, Howto-do-it, Need-to-know and Seeking-different-solution. The Debug-corrective category is very close to our work because the developer posts the buggy code in SO in order to glean the fix. But there is a number of bugs that are not related to API methods usage. The next subsection details the steps taken to build this dataset.

API-usage-related Bugs Dataset

The following steps were performed for the construction of such dataset:

• Step 1: We use the 3 filters (contains code in the question, tagged, answered) mentioned above in Section 2 to select candidate API-usage-related posts;

• Step 2: A manual analysis was performed with the first 50 returned posts for each programming language, resulting in the identification of 30 API-usage-related bugs, 15 for the Java language and 15 for the JavaScript language;

• Step 3: In order to obtain code from real-world software projects that contain potential API-usage-related bugs, we manually analyzed method calls found on snippets from SO posts, selecting the method name related to the respective API-usage-related bug (e.g., a counter-intuitive API method). The corresponding method name was queried in the OHLOH Code Search site 12 . We selected the first returned Java class and JavaScript function for being the representative code excerpt with potential API-usage-related bug. In order to produce the final excerpts of Java classes, we removed from the encountered classes the methods that did not call the method used in the query and instance variables.

• Step 4: The code excerpts with potential API-usagerelated bugs found on the OHLOH site were selected to compose the dataset. Then, we construct a pair of two Web addresses for each potential API-usage-related bug present in the dataset: the OHLOH address of the code with potential API-usage-related bug and the address of an arbitrary post of SO that fixes this potential API-usage-related bug.

The dataset of potential API-usage-related bugs used in this study is available online13 .

Experiment III: Excerpts from OHLOH with Potential API-usage-related Bugs

The impact of using real-world code snippets in Experiment III is to simulate a real software maintenance scenario. For each potential API-usage-related bug of the dataset (represented by an excerpt of real open-source code that can lead to API-usage-related bug and its respective correction in SO), we want to measure the position of the Q&A solution in the top-10 results after querying with the real code excerpt. So, for each code searched in our system, the position of the post of SO that solves the potential bug was calculated. It would be a possibility to evaluate the top-10 results for each queried snippet to obtain the quality of the overall recommendation because there may be more than one post of SO that discusses the fix of the potential API-usage-related bug. However, we decided to investigate the position of the APIusage-related bug fix in the ranking to obtain the accuracy of the recommendation. Before explaining how we performed the queries with potential API-usage-related bugs in the indexes of Apache Solr, it is necessary to understand about the keyword filter that was used for query construction. The next subsection presents the methodology used to construct the keyword filter.

Building the Keyword Filter

Table 4 shows the keyword filter used in the Apache Solr's query. The filter is added to the query of Apache Solr at the time which is performed the query in the index. These keywords were taken from a qualitative analysis involving 70 posts of SO containing API-usage-related bugs. These posts were also selected using the 3 filters (contains code in the question, tagged, answered) mentioned above in Section 2. A manual analysis was performed with the first 100 returned posts for each programming language.

Table 4 presents the most recurrent keywords in the titles of these selected posts (i.e., each keyword appeared at least 10 times in the title of these posts). The next subsection explains how to use the keyword filter to query a desired Apache Solr's index.

Table 4: Filter used in the Apache Solr's query.

Keywords considered in the filter unexpected, incorrect, wrong, output, return, returns, result, results, behavior, weird, strange, odd, problem, problems

Building Queries for Apache Solr using the Keyword Filter

Figure 1 shows the usage of the keyword filter in Apache Solr's query. The example in this figure is for a Java code excerpt #15 . Each document added to the index of Apache Solr has a set of fields, which store the information about document registration. Two fields are shown: "postTitle" and "codeText". The former refers to the title of SO's post, while the latter contains the output generated by the preprocessing function after processing the SO code snippet. In this figure, the snippet was preprocessed with the function lsab-java, which returns those terms denoting the names of invoked API methods.

The query related to Figure 1 has the following meaning: return the posts of SO (i.e., documents from the index) that have at least one of the keywords defined in Table 4 present in their title and whose code snippets have the API method calls present in the queried code excerpt. The query with no keyword filter would not have the fields "postTitle", but only the field "codeText". For each of the 15 potential API-usage-related bugs present in our dataset selected for the Java language, we performed 6 different queries using Apache Solr, with 2 queries by index (i.e., pp1 without filter, pp1 with filter, pp2 without filter, pp2 with filter, lsab-java without filter and lsabjava with filter).

For each of the 15 potential API-usage-related bugs present in our dataset selected for the JavaScript language, we performed 6 different queries using Apache Solr, with 2 queries by index (i.e., pp1 without filter, pp1 with filter, pp3 without filter, pp3 with filter, lsab-js without filter and lsab-js with filter). We can see that the first query of each index did not use the keyword filter, while the second query of each index used such filter.

We used the same preprocessing functions used in the Experiment II to conduct the Experiment III. Both the preprocessing functions pp1 and raw suffer from the problem of the presence of reserved words of the language (e.g., stop words as: "public", "class", etc.). Therefore, in Experiment III, the indexes Java-raw and JavaScript-raw were not considered.

We build new Apache Solr indexes to conduct the Experiment III because we are no longer interested in considering all Java and JavaScript code snippets present in our local database. Ideally, we would like to index only code snippets related to API-usage-related bugs to improve the search mechanism. To accomplish this, we use the 3 filters (contains code in the question, tagged, answered) mentioned above in Section 2 to select candidate API-usage-related posts. After this, all code snippets present in the post of SO (i.e., snippets present in the question along with snippets present in the answer(s)), after the completion of the preprocessing were indexed so that each post of SO was associated with exactly one document in the index of Apache Solr.

Comparing results with Google

Last but not least, we compared our results to searching in SO with Google, which is the most popular general purpose search engine, i.e., a general front-door to the crowd knowledge.

Other custom code search engines are not suitable for offthe-shelf comparison because they do not index SO content. They would require an adaptation to index snippets and link them to respective posts. In other words, they address a different problem scope.

For each of the 30 potential API-usage-related bugs in our dataset selected for the Java and JavaScript, we performed a Google search within SO aiming at understanding to what extent this search engine retrieves some post of SO mapped in our dataset.

We define a protocol for searching Google, based on the following rules:

• The search query should be restricted to SO site. For this, we specified Google to search within the SO site adding the search parameter "site:stackoverflow.com" to the query;

• Google is not good with long query. Thus, the search query should be limited to a maximum of 32 words (threshold adopted by Google itself).

We also investigate whether Google benefits from querying with preprocessed excerpts. The preprocessing functions pp1, lsab-java, and lsab-js were applied in Java and JavaScript excerpts present in our dataset. We also searched Google without preprocessing those excerpts, i.e., raw query.

Results and Discussion of Experiment III

This section presents and discusses the results obtained in the Experiment III. Table 5 has the following structure: the first column contains the id for each OHLOH code excerpt present in our dataset, the second column contains the Web address of the SO's post that fixes a particular potential APIusage-related bug written in Java language. The remaining columns refer to the positions occupied by these posts of SO in the top-10 ranking produced by the Apache Solr search engine and Google search engine. Concerning Apache Solr search engine, we considered the preprocessing functions pp1, pp2, and lsab-java without/with the use of the filter in the query of Apache Solr. Concerning Google, we considered the preprocessing functions raw, pp1, and lsab-java. Each row of the Table 5 corresponds to a potential API-usage-related bug written in Java mapped in our dataset.

Table 6 has similar structure as Table 5 but it is related to potential API-usage-related bugs written in JavaScript language. Concerning Apache Solr search engine, we considered the preprocessing functions pp1, pp3, and lsab-js without/with the use of the filter in the query of Apache Solr. Concerning Google, we considered the preprocessing functions raw, pp1, and lsab-js.

The colored cells of Tables 5 and6 indicate the positions in the top-10 search results found by Google or Apache Solr. We observed that Google does not cope well in searching for fixes to potential API-usage-related bugs, even with excerpts preprocessed by our parsers (i.e., lsab-java and lsab-js). These results indicate that these parsers combined with the keyword filter outperform Google in searching for fixes to potential API-usage-related bugs. Those tables show that the likelihood of finding a post of SO that fixes a potential API-usage-related bug written in Java or JavaScript programming languages increases when using the keyword filter in the Apache Solr's query (less "not found" --cells). Experiment III allowed us to answer the research question RQ4. Summary of RQ4. Experiment III revealed that the proposed approach performed better for Java than for JavaScript. For both languages, the proposed approach obtained the best (and promising) results using, respectively, the preprocessing functions lsab-java and lsab-js, combined with the keyword filter. Although in general, the proposed approach outperformed Google, the latter could find fixes in specific cases where the approach could not find (four out of thirty cases).

Threats to Validity

The main threat to external validity is that the dataset we use is small and may not be representative of real world datasets. However, all code excerpts we use are potential API-usage-related bugs present in real software projects. Note that many existing studies evaluate their approaches considering real world code snippets. Moreover, these studies have datasets whose sizes are similar to or much smaller than ours [START_REF] Gao | Fixing Recurring Crash Bugs via Analyzing Q&A Sites[END_REF][19] [START_REF] Le Goues | Genprog: A generic method for automatic software repair[END_REF].

Another threat to external validity is that our approach is as good as the database of SO. Currently, results are presented based on the data dump of March 2013. Although, the database of SO is growing rapidly. There are approximately 12M questions in the database today (June 2016), while in March 2013, the database had about 3M questions.

The main threat to internal validity is the size of code snippets with potential API-usage-related bugs queried in our system. Our intuition is that the larger the size of the code snippet queried in our system, the greater is the probability of introducing noise in the query results because a larger number of API methods could be considered (i.e., different API methods could confuse the proposed approach). On the other hand, our approach is a flexible solution because it allows developers to inform their own suspicious snippets of different sizes and get extra knowledge from SO discussions.

RELATED WORK

API-usage-related bugs are not really studied in the literature.

Crowd Debugging. Gao et al. [START_REF] Gao | Fixing Recurring Crash Bugs via Analyzing Q&A Sites[END_REF] proposed a fully automatic approach to fixing recurring crash bugs via analyzing Q&A sites. Their approach extracts queries from crash traces and retrieves a list of Q&A pages. They investigated recurring bugs (i.e., bugs that occur often in different projects) and observed that many recurring bugs have already been Table 5: Results of queries performed in the Java indexes pp1, pp2, and lsab-java (without/with the use of the keyword filter in the Apache Solr's query; "-" = Post of SO not found in the ranking; "P" refer to the positions occupied by posts of SO in the ranking. discussed over the Q&A sites such as SO. Our approach is designed to handle a particular class of recurring bugs called API-usage-related bugs. The latter are related to incorrect usage of an API by a developer and do not generate exception stack traces. Moreover, we proposed to search SO using snippet-based queries instead of terms extracted from exception stack traces.

Monperrus et al. [START_REF] Monperrus | Debugging with the Crowd: a Debug Recommendation System based on Stackoverflow[END_REF] defined the concept of "crowd bugs" (i.e., synonym for "API-usage-related bugs") and proposed the idea of "debug with the crowd". Our approach was based on Monperrus et al. paper and present a complete new set of empirical results. Moreover, we investigated API-usagerelated bugs present in Java and JavaScript code snippets, while Monperrus et al. only handle JavaScript API-usagerelated bugs.

F. Chen and S. Kim [START_REF] Chen | Crowd debugging[END_REF] proposed to mine SO in order to help developers during debugging tasks. Their approach is aimed at detecting different types of bugs. Unlike them, our approach is designed to provide fixes and explanations from SO for a particular type of bug (i.e., API-usage-related bugs). Our approach differs in the sense that we suppose a scenario where developers already know the suspicious snippet and wants to find if there is a discussion on that pattern of snippet.

Hartmann et al. [START_REF] Hartmann | What Would Other Programmers Do: Suggesting Solutions to Error Messages[END_REF] presented HelpMeOut, a social recommender system that aids the debugging of compiler error messages by suggesting solutions that other programmers have applied in the past. HelpMeOut uses both error messages and source code context in the capture and search for relevant fixes. Unlike HelpMeOut, our approach uses only code snippets to search SO for API-usage-related bug fixes because API-usage-related bugs do not generate exception stack traces.

Semantic code search and code search engines. The main usage of code search engines is to retrieve code samples and reusable open source code from the Web. Different works tackled this problem [START_REF] Zagalsky | Example Overflow: Using social media for code recommendation[END_REF][20][25] [START_REF] Thummalapenta | Parseweb: A Programmer Assistant for Reusing Open Source Code on the Web[END_REF]. The mining of open source repositories has also been used to identify API and framework usage and to find highly relevant applications to be reused [START_REF] Mcmillan | Exemplar: A Source Code Search Engine for Finding Highly Relevant Applications[END_REF][14] [START_REF] Thummalapenta | SpotWeb: Detecting Framework Hotspots and Coldspots via Mining Open Source Code on the Web[END_REF]. Differently from the work done so far on code search, we do not target open source repositories to provide code samples and reusable code, or to understand the usage of APIs; instead, we target the crowd knowledge provided by discussions in SO as alternative source. This is because we want to provide developers with API-usagerelated bug fixes with explanations, rather than just with reusable code components/snippets.

Recommender Systems. Different typologies of recommender systems to suggest relevant project artifacts, support newcomers in a project, and assist developers by suggesting code examples on the Web relevant to their current task has been presented. Well-known examples are HIPIKAT [START_REF] Čubranić | Hipikat: Recommending Pertinent Software Development Artifacts[END_REF], DEEPINTELLISENCE [START_REF] Holmes | Deep Intellisense: A Tool for Rehydrating Evaporated Information[END_REF], and eROSE [START_REF] Zimmermann | Mining Version Histories to Guide Software Changes[END_REF]. Other work focused on suggesting relevant documents, discussions and code samples from the Web to fill the gap between the IDE and the Web browser. Examples are CODETRAIL [START_REF] Goldman | Codetrail: Connecting Source Code and Web Resources[END_REF], MICA [START_REF] Stylos | Mica: A Web-Search Tool for Finding API Components and Examples[END_REF], FISHTAIL [START_REF] Sawadsky | Fishtail: From task context to source code examples[END_REF], and DORA [START_REF] Kononenko | Automatically locating relevant programming help online[END_REF].

Among the various sources available on the Web, Q&A Websites and in particular SO, have been the target of many recommender systems. In a previous work [START_REF] Campos | Searching Crowd Knowledge to Recommend Solutions for API Usage Tasks[END_REF], we present an approach that makes use of "crowd knowledge" available in SO to recommend information that can assist developers in their development tasks with a given API. This strategy recommends a ranked list of question-answer pairs from SO based on a query. The criteria for ranking are based on three main aspects: the textual similarity of the pairs with respect to the query related to the developer's problem, the quality of the pairs, and a filtering mechanism that uses machine learning to consider only "how-to" posts. However, there are some differences between the work presented here and this previous work: (i) the previous approach is more general and it was not designed to deal with API-usagerelated bugs; (ii) the previous approach relies on searching Lucene indexes using a list of terms as input query, while the current approach uses suspicious code snippets as input query; (iii) the previous approach was designed to assist developers during development tasks while the current approach was designed to assist developers during debugging tasks.

Ponzanelli et al. [START_REF] Ponzanelli | Mining StackOverflow to Turn the IDE into a Self-confident Programming Prompter[END_REF] proposed Prompter, a recommender system designed to automatically capturing the code context in the IDE and suggesting documents from SO that have enough self-confidence to the developer. Our approach also takes into account the developer's code context with the aim of suggesting relevant SO discussions. However, there are some differences between the two works: (i) their approach is more general and addresses a different problem scope (i.e., they do not limit their scope to "API-usage-related bugs"); (ii) they do not use the Apache Solr as search engine. Instead, they use other search engines (i.e., Google, Bing, and Blekko); (iii) they implement a different code searching technique.

CONCLUSIONS

In this paper, we presented a new approach to find fixes for API-usage-related bugs using suspicious code snippets as input query. Typical general and source code search engines are not designed to handle this type of query. For all experiments, we considered preprocessing functions for code snippets written in Java or JavaScript languages. We built a dataset composed by 30 excerpts with potential API-usagerelated bugs extracted from OHLOH in order to evaluate our approach. The results showed a clear advantage in approximately 40% of the approach using the filter in relation to the approach without using the filter. Moreover, the results are encouraging: for 66.67% of Java excerpts with potential API-usage-related bugs picked from OHLOH, we found their fix in the top-10. Concerning JavaScript excerpts present in the dataset, for 40% of them, we found their fix in the top-10. These results suggest that our approaches (i.e., lsab-java and lsab-js combined with the keyword filter) outperform Google and SO in searching for fixes to potential API-usage-related bugs present in real software projects.

Figure 1 :

 1 Figure 1: Example of Apache Solr's query using the keyword filtering.

Table 1 :

 1 Preprocessing functions for code snippets per type and programming language.

	Type	Java	JavaScript
	No preprocessing raw	raw
	Lexical	pp1	pp1, pp3
	Syntactic	pp2, lsab-java lsab-js

Table 2 :

 2 Using SO Snippets as Code-based Queries (SO refers to Stack Overflow, hence t index =SO means that the indexing function is that of Stack Overflow, "raw" means that no preprocessing is used). "PP" refers to preprocessing.

	Topic	Index PP	Query PP	Not Found Rank #1 Rank ≤ 5 Rank ≤ 10
	Java Android	t index =SO tquery=raw	89.3%	8.9%	9.8%	9.9%
	Java Android	t index =SO tquery=pp1	94.7%	4.7%	4.9%	5.2%
	Java non-Android t index =SO tquery=raw	90.4%	8.7%	9.4%	9.4%
	Java non-Android t index =SO tquery=pp1	89.1%	10.5%	10.5%	10.6%
	JavaScript	t index =SO tquery=raw	95%	4.5%	4.9%	5%
	JavaScript	t index =SO tquery=pp1	86%	12.7%	13.8%	13.9%

Table 3 :

 3 Using SO Snippets as Code-based Queries (SOLR refers to Apache Solr, hence t index =SOLR means that the search index was constructed using Apache Solr, "raw" means that no preprocessing was used). "PP" refers to preprocessing.

	Topic	Index PP	Query PP	Not Found Rank #1 Rank ≤ 5 Rank ≤ 10
	Java Android	t index =SOLRraw,	tquery=raw	15.1%	61.9%	74%	78.5%
	Java Android	t index =SOLR pp1 ,	tquery=pp1	3.1%	85.7%	94.2%	95%
	Java Android	t index =SOLR pp2 ,	tquery=pp2	11.1%	71.3%	79%	81.7%
	Java Android	t index =SOLR lsab-java , tquery=lsab-java	26%	59.9%	68.2%	69.5%
	Java non-Android t index =SOLRraw,	tquery=raw	11.2%	70.1%	82.4%	85.4%
	Java non-Android t index =SOLR pp1 ,	tquery=pp1	3.5%	90%	95%	95.9%
	Java non-Android t index =SOLR pp2 ,	tquery=pp2	17%	63.8%	73.9%	76.5%
	Java non-Android t index =SOLR lsab-java , tquery=lsab-java	9.9%	79.8%	86.9%	88.7%
	JavaScript	t index =SOLRraw,	tquery=raw	7.3%	74.3%	88.7%	90.4%
	JavaScript	t index =SOLR pp1 ,	tquery=pp1	0.9%	90.5%	98.1%	98.8%
	JavaScript	t index =SOLR pp3 ,	tquery=pp3	11.9%	77.5%	85.6%	86.8%
	JavaScript	t index =SOLR lsab-js ,	tquery=lsab-js	23.9%	51.6%	58.3%	61.8%

http://stackoverflow.com/search?q=Math.cos+java

http://stackoverflow.com/search?q=%5Bjavascript %5D+title%3AparseInt

https://code.openhub.net/ (verified 05/02/2016)

http://www.eclipse.org/jdt/core/component

https://developer.mozilla.org/en-US/

https://code.ohloh.net/ (verified 05/02/2016)

https://github.com/eduardocunha11/API-usage-relatedbugs (verified 30/08/2016)

ACKNOWLEDGMENTS

We would like to thank the Brazilian agencies FAPEMIG, CAPES and CNPq for partially funding this research.


Santiago Iturriaga
email: siturria@fing.edu.uy

Sergio Nesmachnow
email: sergion@fing.edu.uy

Bernabé Dorronsoro
email: bernabe.dorronsoro@lifl.fr

Pascal Bouvry
email: pascal.bouvry@uni.lu

ENERGY EFFICIENT SCHEDULING IN HETEROGENEOUS SYSTEMS WITH A PARALLEL MULTIOBJECTIVE LOCAL SEARCH

Keywords: Scheduling, local search, multithreading, heterogeneous computing

This article introduces ME-MLS, an efficient multithreading local search algorithm for solving the multiobjective scheduling problem in heterogeneous computing systems. We consider the minimization of both the makespan and energy consumption objectives. The proposed method follows a fully multiobjective approach, applying a Pareto-based dominance search that is executed in parallel by using several threads. The experimental analysis demonstrates that the new multithreading algorithm outperforms a set of fast and accurate two-phases deterministic heuristics based on the traditional MinMin. The new ME-MLS method is able to achieve significant improvements in both makespan and energy consumption objectives in reduced execution times for a large set of testbed instances, while exhibiting a near linear speedup behavior when using up to 24 threads.

INTRODUCTION

Distributed computing platforms have grown at a fast pace. Nowadays, they gather many heterogeneous computing (HC) resources located worldwide. In the last decade, the novel grid computing systems emerged as useful providers for the computing power needed to tackle complex problems in many application domains [START_REF] Foster | The Grid: Blueprint Future Computing Infrastructure[END_REF].

In current distributed HC/grid systems, efficiently allocating tasks to be executed on available resources (scheduling) is a key problem to take full advantage of the computing power. The goal of the scheduling problem is to assign tasks to the computing resources by satisfying specific efficiency criteria, usually related to the total execution time of a bunch of tasks (makespan), but frequently also considering other relevant objectives such as resource utilization, quality of service, etc.

Traditional scheduling problems are NP-hard [START_REF] Garey | Computers and intractability[END_REF], thus classic exact methods are not useful in practice to solve large instances of the problem. Many deterministic scheduling heuristics have been proposed, but in general they do not scale appropriately when solving large dimension instances, also demanding long execution times. Thus, non-deterministic heuristics and metaheuristics have been used to tackle scheduling problems, and they are shown to compute efficient schedules in reasonable timespans for both small and large dimension instances [START_REF] Nesmachnow | Heterogeneous Computing Scheduling with Evolutionary Algorithms[END_REF][START_REF] Nesmachnow | Multiobjective Scheduling on Distributed Heterogeneous Computing and Grid Environments Using a Parallel Micro-CHC Evolutionary Algorithm[END_REF][START_REF] Pinel | Solving Very Large Instances of the Scheduling of Independent Tasks Problem on the GPU[END_REF][START_REF] Xhafa | Parallel Memetic Algorithms for Independent job Scheduling in Computational Grids[END_REF].

Recently, energy consumption has become a major concern in distributed/high performance computing. Processors are the main consumers of energy in such systems, and frequently they also offer the most flexible options for energy management, by applying dynamic voltage scaling (DVS), dynamic power management, slack sharing and reclamation, etc. [START_REF] Khan | A Cooperative Game Theoretical Technique for Joint Optimization of Energy Consumption and Response Time in Computational Grids[END_REF][START_REF] Kim | Power Aware Scheduling of Bag-of-Tasks Applications with Deadline Constraints on DVS-Enabled Clusters[END_REF][START_REF] Zhu | Scheduling with Dynamic Voltage/Speed Adjustment Using Slack Reclamation in Multiprocessor Real-Time Systems[END_REF]. Reducing processors consumption is a great challenge, and researchers currently focus on the development of energyaware scheduling algorithms for HC/grid systems [START_REF] Lee | Minimizing Energy Consumption for Precedence Constrained Applications Using Dynamic Voltage Scaling[END_REF].

In this article, we propose, implement, and evaluate ME-MLS, a highly efficient multiobjective local search metaheuristic to find accurate tradeoff solutions to the multiobjective scheduling problem of minimizing the makespan and the energy consumption in HC/grid systems. ME-MLS is a population-based method that follows a fully multiobjective approach; it does not optimize an aggregated function of the problem objectives, but uses a Pareto-based dominance analysis instead. The ME-MLS population is size bounded, thus, two different replacement policies are evaluated:

1. a fast greedy ad-hoc replacement algorithm, and 2. the Adaptive Grid Archiving (AGA) algorithm proposed by Knowles et al [START_REF] Knowles | Properties of an Adaptive Archiving Algorithm for Storing Nondominated Vectors[END_REF].

Both ME-MLS variants are compared versus well-known deterministic heuristics over a large set of instances. The experimental results show that ME-MLS is able to compute accurate tradeoff schedules in short execution times.

The manuscript is organized as follows. Section 2 introduces the multiobjective energy-aware scheduling problem in HC systems and a review of related work. The details about the design and implementation of the new multiobjective local search method is presented in Section 3. Experimental evaluation of the proposed method over a large set of problem instances is described in Section 4. Finally, Section 5 presents the conclusions and formulates the main lines for future work.

ENERGY-AWARE SCHEDULING IN HC SYSTEMS

This section introduces the makespan-energy heterogenous computing scheduling problem (ME-HCSP) and a review of related work.

Problem Formulation

An HC system is composed by a set of heterogeneous computers (usually called machines), having different computing power and energy consumption demand, depending on the hardware features.

In this work, we address the problem of scheduling a set of non-dependent tasks on an HC system. In this model, a task is considered as atomic workload unit, so it cannot be divided, nor interrupted after it is assigned to a machine (the scheduling problem follows a non-preemptive model). The execution times of any task and the energy consumption to perform it vary from one machine to another. Thus, those machines that are able to execute tasks quickly and with low energy consumption will have a strong demand in the system.

Scheduling problems usually target the minimization of the makespan, to reduce the time spent to execute a bunch of tasks. The makespan is defined as the time spent since the first task begins execution to the moment when the last task is completed [START_REF] Leung | Handbook of Scheduling: Algorithms, Models, and Performance Analysis[END_REF]. The ME-HCSP aims at minimizing the makespan together with the energy consumption in HC systems.

The mathematical model of ME-HCSP considers the following elements:

• An HC system composed of a set of heterogeneous machines P = {m 1 , . . . , m M }; each machine performing at a certain processing speed and energy consumption.

• A collection of tasks T = {t 1 , . . . , t N } to be executed on the system.

• An execution time function ET : T × P → R + , where ET (t i , m j ) is the time required to execute task t i on machine m j .

• An energy consumption function EC : T × P → R + , where EC(t i , m j ) is the energy required to execute task t i on machine m j , and EC IDLE : P → R + , being EC IDLE (m j ) the energy that machine m j consumes in idle state.

The ME-HCSP proposes to find a schedule f that simultaneously minimizes the makespan (defined in Equation ( 1)), and the energy consumption (defined in Equation ( 2)), which accounts for both the energy required for tasks execution and the energy that each machine spends in idle state until all tasks are finished; (CP (M j ) is the completion time of machine j, i.e., the time when it finishes all its assigned tasks). The energy for executing a given task depends on its execution time ET (t i , m j ), but the two objectives are in conflict in HC systems, since fast machines usually consume more energy than the slower ones. max

m j ∈P t i ∈T : (t i ,m j )∈f ET (t i , m j ) ( 1
)
t i ∈T : (t i ,m j )∈f EC(t i , m j ) + m j ∈P (makespan -CP (M j ))EC IDLE (m j ) (2)
In the previous ME-HCSP formulation, all tasks can be performed disregarding the execution order. This kind of programs are frequent in e-Science applications over HC/grid computing, such as Single-Program Multiple-Data applications used for multimedia processing, data mining, parallel domain decomposition of numerical models for physical phenomena, etc.

The independent tasks model also arises when different users submit their (independent) tasks to execute in grid and volunteer-based computing services, such as WLCG, Teragrid, Berkeley's BOINC, Xgrid [START_REF] Berman | Grid Computing: Making the Global Infrastructure a Reality[END_REF], where non-dependent domain decomposition applications are often submitted for execution. Thus, the ME-HCSP faced in this work is relevant in realistic distributed HC/grid environments.

Related Work

The main trend in energy-aware schedulers proposed in the related literature is to apply energy management methods within the computing elements. The most used strategies for energy management are dynamic voltage scaling (DVS), dynamic power management, and slack sharing/reclamation methods [START_REF] Khan | A Cooperative Game Theoretical Technique for Joint Optimization of Energy Consumption and Response Time in Computational Grids[END_REF][START_REF] Kim | Power Aware Scheduling of Bag-of-Tasks Applications with Deadline Constraints on DVS-Enabled Clusters[END_REF].

Kim et al. [START_REF] Kim | Dynamic Resource Management in Energy Constrained Heterogeneous Computing Systems Using Voltage Scaling[END_REF] introduced several online/batch dynamic heuristics for scheduling tasks with priorities and deadlines in an ad-hoc grid with limited battery capacity, using DVS for power management. The batch dynamic heuristics based on the classic MinMin scheduler [START_REF] Luo | A Revisit of Fast Greedy Heuristics for Mapping a Class of Independent Tasks Onto Heterogeneous Computing Systems[END_REF] performed best, but they required significantly longer time. Li et al. [20] also proposed an energy-aware scheduler based on the MinMin heuristic to reduce energy consumption using dynamic power management.

In 2009, Kahn and Ahmad [START_REF] Khan | A Cooperative Game Theoretical Technique for Joint Optimization of Energy Consumption and Response Time in Computational Grids[END_REF] developed an energy-aware grid scheduler based on the concept of Nash Bargaining Solution from cooperative game theory. The scheduler was applied for planning in infrastructures with DVS-enabled machines.

Another cooperative approach to solve the energy-aware scheduling problem was introduced by Mezmaz et al. [START_REF] Mezmaz | A Parallel Bi-Objective Hybrid Metaheuristic for Energy-Aware Scheduling for Cloud Computing Systems[END_REF], which applied a cooperative parallel bi-objective hybrid genetic algorithm (GA), improved with the energy-aware heuristics previously proposed by Lee and Zomaya [START_REF] Lee | Energy Conscious Scheduling for Distributed Computing Systems Under Different Operating Conditions[END_REF].

The work by Pecero et al. [START_REF] Pecero | A Multi-Objective GRASP Algorithm for Joint Optimization of Energy Consumption and Schedule Length of Precedence-Constrained Applications[END_REF] applied a bi-objective Greedy Randomized Adaptive Search Procedure (GRASP) scheduler. The proposed method builds a feasible solution using a greedy evaluation function, and uses a post-processing bi-objective local search method applying DVS to improve the solution quality and to generate a set of Pareto solutions.

A two-phase energy-aware heuristic for grid scheduling was proposed by Pinel et al. [START_REF] Pinel | A Two Phase Heuristic for the Energy-Efficient Scheduling of Independent Tasks on Computational Grids[END_REF], by first applying the MinMin heuristic to find schedules with good makespan, and a local search in the second phase. The method allowed to find schedules with similar quality to those computed by a cellular evolutionary algorithm (EA), while reducing the execution time, and significantly improving the MinMin schedules.

Kessaci et al. [START_REF] Kessaci | Parallel Evolutionary Algorithms for Energy Aware Scheduling[END_REF] proposed two multiobjective parallel evolutionary algorithms enhanced with energy-aware scheduling heuristics for tasks with dependencies, combining makespan and energy consumption in a unique function and using explicit DVS for energy management. Kolodziej et al. [START_REF] Kolodziej | Hierarchical genetic-based grid scheduling with energy optimization[END_REF] developed an EA framework for designing energy-aware schedulers, using DVS for energy reduction. The problem model in that work considered bag-of-tasks applications and a bi-objective scheduling problem minimizing makespan and energy consumption. The article by Lindberg et al. [START_REF] Lindberg | Comparison and Analysis of Eight Scheduling Heuristics for the Optimization of Energy Consumption and Makespan in Large-Scale Distributed Systems[END_REF] introduced a set of eight heuristics, including two EAs for the energy-aware grid scheduling problem subject to deadline and memory constraints.

The approach we describe in this article does not explicitly apply DVS or other energy management methods. Instead, we propose a scheduler that computes the energy consumption by considering the maximum and minimum energy consumption provided by the processor technology, which accounts for hardware-embedded energy saving features. The efficiency of these technologies is model dependent, since hardware-embedded energy saving features are proprietary technologies (e.g. AMD provides the Optimized Power Management technology in the Opteron processor family, Intel provides the SpeedStep technology in Xeon/i7 processor family, etc.). In our approach, a machine with assigned workload is assumed to operate at its peak performance, consuming the maximum specified energy. Conversely, a machine with no workload is assumed to be in idle state with the embedded energy saving technology keeping the energy consumption at its minimum specified value.

A MULTITHREADING ENERGY-AWARE HC SCHEDULER

This section describes the newly proposed multithreading local search algorithm to solve the energy-aware scheduling problem in HC systems.

ME-MLS Design

ME-MLS is a population-based local search algorithm, which maintains a population of non-dominated (elite) solutions in order to avoid biasing the search toward any of the two objectives of the energy-aware scheduling problem. A shared-memory parallel implementation is proposed for ME-MLS, by using a pool of threads. Each thread is a peer that performs a search, and no thread acts in a master role.

Algorithm 1 presents the logic of each ME-MLS thread. Schedules are initialized using a randomized version of the Minimum Completion Time (MCT) scheduling for i = 0 → max iterations do end while 24: end while heuristic [START_REF] Luo | A Revisit of Fast Greedy Heuristics for Mapping a Class of Independent Tasks Onto Heterogeneous Computing Systems[END_REF] (line 1). Each thread iteratively applies a local search (lines 11 to 13) on a clone s of a randomly selected schedule s (line 6). Newly found non-dominated schedules are inserted into the population (line 16). Since each thread has to exclusively lock the population to insert a new schedule (lines 14 to 18), they apply an additional number of operations (bounded by the REWORK FACTOR parametercomputed in line 20) waiting for the population lock to be released. After the new schedule is safely inserted into the population (line 16), the thread repeats the whole process (lines 3 to 23) to keep improving non-dominated schedules from the population. Figure 1 shows the steps performed by ME-MLS algorithm.

Replacement Algorithm

The elite population in ME-MLS is limited in size, so a replacement technique is applied when the maximum size is reached. We evaluated two replacement methods: a fast greedy ad hoc technique, and the Adaptive Grid Archiving technique.

Fast greedy ad hoc replacement. This technique makes use of heuristic knowledge regarding the makespan-energy metrics. It always inserts the newly found non-dominated schedules into the population, helping to prevent a stagnation When the population is full, a schedule currently in the population is selected to be replaced based on a distance function, defined as the sum of the relative improvements of each objective metric. Those schedules that compute the minimum value in at least one of the problem objectives are never replaced. When using the fast greedy ad hoc replacement technique in the ME-MLS algorithm we will refer to ME-MLS + ad hoc algorithm.

Adaptive Grid Archiving (AGA). The AGA technique was initially proposed as the crowding strategy applied in the Pareto Archived Evolution Strategy (PAES) algorithm [START_REF] Knowles | Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy[END_REF]. It consists in dividing up the objective space into hypercubes with the goal of balancing the density of non-dominated solutions in the hypercubes. Then, when inserting a non-dominated solution in the Pareto front, its grid location in the solution space is determined. If the Pareto front is already full and the grid location of the new solution does not match with the most crowded hypercube, a solution belonging to that most crowded hypercube is removed before inserting the new one. The AGA strategy guarantees three very desirable properties for multiobjective optimization (MO) algorithms:

1. it maintains solutions at the extremes of all objectives; 2. it maintains solutions in all of the Pareto occupied regions, and 3. it distributes the remaining solutions evenly among the Pareto regions.

When using the AGA replacement technique in the ME-MLS algorithm we will refer to ME-MLS + AGA algorithm.

Local Search

The The local search performed by each thread (Algorithm 2) applies one of the following strategies: makespan optimization, energy optimization, or random optimization (line 1). The method works with two machines m A and m B to perform the search (selected in lines 3-4). When the makespan optimization strategy is applied, it selects with high probability the machine defining the makespan as m A and the machine with the lowest computing time as m B . The energy optimization strategy selects with high probability the most energy consuming machine as m A and the less energy consuming machine as m B . The random optimization selects two random machines as m A and m B . Then, a random set of tasks tasks X from the ones assigned to m A is selected (line 5). For each task x ∈ tasks X , the method randomly selects an operation to perform (line 8):

1. a swap operation, or 2. a move operation.

When the swap operation is applied (lines 9 to 16), the method selects a random set of tasks tasks Y assigned to m B (line 6), computes the values for both objectives when swapping task x with each task y ∈ tasks Y (lines 11 and 12), and chooses the swap which improves most the schedule objectives (line 14). If the energy and makespan improvements of the computed swap are in conflict (i.e. the swap improves one metric but degrades the other), the best swap according to the selected search strategy is applied. When no swap is found to improve neither of the schedule objectives, no swap is applied.

If the move operation is applied, for task x (lines 17 to 26), the method selects a set of random machines M = {randommachines}∪{m B } (line 18), and computes the variation in the schedule objectives when moving task x to each machine m D ∈ M (lines 20-21). Then, the move operation which improves most the schedule objectives prioritizing the currently selected search strategy is selected to be applied (lines 22 to 24).

When no swap/move is found to improve neither of the schedule objectives, no operation is applied.

Implementation Details

Implementation language and libraries. ME-MLS is implemented in GNU C++ 4.6, avoiding heavy C++ constructs (classes, interfaces, polymorphism) to minimize the code execution overhead.

The multithreading support is provided by the GNU POSIX thread library 2.13. We do not use high level parallel multithreading libraries, such as OpenMP, in order to have fine grain control over the synchronization mechanisms. Finally, the Mersenne Twister (MT) method [START_REF] Matsumoto | Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator[END_REF] is used to generate pseudorandom numbers, since empirical evidence indicates that it is more efficient than standard generators [START_REF] Nesmachnow | Time Analysis of Standard Evolutionary Algorithms as Software Programs[END_REF]. We modified the original MT implementation to be thread-safe, allowing multithreading random numbers generation.

Problem encoding. ME-MLS maintains in memory a multi-structure comprising both a machine-based and a task-based encoding for schedules [START_REF] Nesmachnow | Heterogeneous Computing Scheduling with Evolutionary Algorithms[END_REF] (Figure 2). This multi-structure allows ME-MLS to efficiently access the tasks assigned to a given machine in O(1) via the machine-based encoding; and given a certain task, to locate the machine to which it is assigned also in O(1) via the task-based encoding.

Population initialization. The population is initialized using a randomized version of the MCT heuristic [START_REF] Luo | A Revisit of Fast Greedy Heuristics for Mapping a Class of Independent Tasks Onto Heterogeneous Computing Systems[END_REF], considering the tasks sorted in a random order. The tasks are scheduled following that random order to the machines that first accomplish them, providing diversity to the initial population.

EXPERIMENTAL ANALYSIS

This section introduces the ME-HCSP instances and the hardware platform used in the experimental analysis, as well as the MinMin based heuristics used as a reference baseline to compare the ME-MLS results. Finally, the experimental results are presented and analyzed, along with a speedup evaluation of the proposed method.

ME-HCSP Instances and Execution Platform

Instances. A set of 96 ME-HCSP instances was generated to evaluate the ME-MLS algorithm. Each instance describes the machines scenario and the set of tasks workloads. The scenarios were generated using realistic data, gathering for each machine the computational power, and the energy consumption in both idle state and processing state. The workloads were generated following the ETC methodology [START_REF] Ali | Task Execution Time Modeling for Heterogeneous Computing Systems[END_REF].

Three instance dimensions were used in the experimental analysis (number of tasks × number of machines): 512 × 16, 1 024 × 32, and 2 048 × 64. For each dimension, 12 different scenarios and 8 workloads (4 using parameters by Ali et al. [START_REF] Ali | Task Execution Time Modeling for Heterogeneous Computing Systems[END_REF] and 4 using parameters by Braun et al. [START_REF] Braun | A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks into Heterogeneous Distributed Computing Systems[END_REF]) were generated. Combining all these scenarios and workloads we obtain a set of 96 ME-HCSP instances that model realistic small-and medium-sized HC infrastructures.

Execution platform. The experimental analysis was performed on a 24-core Magny-Cours AMD Opteron Processor 6172, 2.1 GHz, 24 GB RAM, running 64-bits CentOS 5.1 Linux, from Cluster FING (http://www.fing.edu.uy/cluster).

MinMin Based Heuristics Used as Reference Baseline

In order to compare the ME-MLS results, we propose here a set of heuristics based on the MinMin list scheduling method [START_REF] Luo | A Revisit of Fast Greedy Heuristics for Mapping a Class of Independent Tasks Onto Heterogeneous Computing Systems[END_REF], which is considered to outperform other deterministic heuristics for minimizing the makespan objective [START_REF] Izakian | Comparison of Heuristics for Scheduling Independent Tasks on Heterogeneous Distributed Environments[END_REF]. The original MinMin heuristic greedily picks the task that can be completed the soonest, taking into account the current machine assignments. MinMin starts with a set U of all unmapped tasks, calculates the MCT for each task in U for each machine, and assigns the task with the minimum overall MCT to the machine that can complete it faster. The mapped task is removed from U , and the process is repeated until all tasks are mapped. A pseudocode of the MinMin heuristic is presented in Algorithm 3.

Algorithm 3 MinMin heuristic

1: U = T {set of unasigned tasks} 2: while U = ∅ do 3:
for each task t k ∈ U do 4:

for each machine m h ∈ P do remove t i from U 12: end while 13: return task assignment MinMin uses a two-phases optimization strategy (the double for cycle in Algorithm 3), thus we define four MinMin versions by alternating the minimization objective in each phase. The first version minimizes the completion time in both phases (it corresponds to the classic MinMin heuristic); the second version minimizes the energy objective in both phases; in the remaining versions the minimization objectives are alternated to be in the first phase or in the second phase. We use the lowercase Min notation when minimizing the completion time and the uppercase MIN notation when minimizing the energy. Thus, the four versions of the MinMin heuristics used in the comparison are: MinMin, MINMIN, MinMIN, and MINMin.

Multiobjective Optimization Metrics Used to Evaluate ME-MLS

Several metrics have been considered in this article to evaluate the two variants of the proposed ME-MLS algorithm, regarding the two main purposes of multiobjective optimization techniques:

1. converging to the Pareto front and 2. correctly sampling the set of non-dominated solutions [START_REF] Coello | Evolutionary Algorithms for Solving Multi-Objective Problems[END_REF][START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF].

The quality metrics evaluate the convergence towards the Pareto front. We consider in this work the number of (different) non-dominated solutions found for each algorithm (ND), and Inverted Generational Distance (IGD), defined as the (normalized) sum of the distances between the non-dominated solutions in the Pareto front found by the algorithm and a set of uniformly distributed points in the true Pareto front. Smaller values of IGD mean a better approximation to the Pareto front.

The diversity metrics measure the distribution of the computed non-dominated solutions, evaluating the capability of correctly sampling the Pareto front of the problem. In this work we consider the spread and Relative Hypervolume (RHV) metrics. Spread includes the information about the extreme points of the true Pareto front in order to compute a precise value of the distribution [START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF]. Smaller values of spread mean a better distribution of non-dominated solutions in the calculated Pareto front. RHV is the ratio of the volume (in the objective functions space) covered by the Pareto front computed by the algorithm and the volume covered by the real Pareto front.

In the experimental analysis, the true Pareto front -which is unknown for the ME-HCSP instances studied -was approximated by gathering the non-dominated solutions found using both ME-MLS variants in the 30 independent executions performed for each algorithm.

Parameter Setting Experiments

The goal of this work is to efficiently solve the ME-HCSP, thus a fixed 10 seconds execution time stopping criterion is used for the ME-MLS algorithm. This time stopping criterion is significantly lower than the execution time of the algorithms in the related literature, which ranges from 60s to 90s [START_REF] Nesmachnow | A Parallel Micro Evolutionary Algorithm for Heterogeneous Computing and Grid Scheduling[END_REF]. For the speedup evaluation of ME-MLS, the stopping criterion was set to 6 million iterations.

In order to provide statistical significance to the results and considering the stochastic nature of the proposed algorithm, 30 independent ME-MLS executions were performed on each instance. Each execution was performed using 24 threads, the maximum number of cores available in the computing platform.

A configuration analysis was performed using the 512 × 16 dimension instances in order to find the best values for the population size (POP SIZE), the number of local search per schedule (THREAD IT), the neighbourhood size used in the local search (SRC TASK NHOOD, DST TASK NHOOD, and DST MACH NHOOD), and the re-work factor (REWORK FACTOR).

The candidate values for the parameter settings study were: POP SIZE ∈ {30, 35, 40}, THREAD IT ∈ {500, 650, 800}, SRC TASK NHOOD ∈ {24, 28, 32}, DST TASK NHOOD ∈ {16, 20, 24}, DST MACH NHOOD ∈ {8, 12, 16}, and REWORK FACTOR ∈ {10, 14, 18}. The best results were obtained with the following configuration POP SIZE = 30, THREAD IT = 650, SRC TASK NHOOD = 28, DST TASK NHOOD = 16, DST MACH NHOOD = 16, and REWORK FACTOR = 14.

Results and Discussion

This subsection presents and discusses the experimental results obtained in the evaluation of the ME-MLS scheduling algorithm. The sample Pareto front approximations in Figure 4 show that the ME-MLS + AGA algorithm is able to compute accurate solutions, with good diversity and an appropriate covering.

Solution quality.

Summarizing, the study indicates that the AGA replacement strategy is a useful choice to improve the quality and diversity of the schedules found by the ME-MLS algorithm, significantly improving over the ad hoc replacement technique regarding the two main goals in MO.

Computational efficiency: speedup evaluation. A speedup analysis was performed for both ME-MLS + AGA and ME-MLS + ad hoc algorithms in order to study the reductions in the execution times when using different numbers of threads. The speedup evaluation was done over the 1 024 × 32 instances, and performing 30 independent executions of each version of the algorithm, using a stopping criterion of 6 million iterations.

Figure 5 graphically summarizes the results of the speedup analysis when using up to 24 threads executing on the 24 cores available in the Magny-Cours experimental computing platform used.

CONCLUSIONS

In this article, we have proposed, implemented, and evaluated a new fast parallel multiobjective local search algorithm to tackle the energy-aware scheduling problem in HC systems. The new scheduler, called ME-MLS, is based on Pareto dominance, and it works on a population of non-dominated schedules that are iteratively evolved in parallel by using multithreading programming techniques. In order to demonstrate the good performance of the algorithm, an efficient termination condition of only 10 seconds was set in the experimental evaluation, allowing to perform almost-online scheduling in HC systems. The experimental analysis compared the proposed method versus state-of-theart scheduling techniques. Two different versions of the multiobjective scheduling ME-MLS algorithm were evaluated, differing on the policy followed to discard nondominated solutions when the population is full: the ME-MLS + AGA and the ME-MLS + ad hoc algorithms.

The two proposed versions of the algorithm were evaluated on a testbed of 96 problem instances with dimensions of up to 2 048 tasks and 64 processors, and they were validated by comparing the obtained results versus those of four versions of the state-of-the-art MinMin scheduler: the classical one and three other energy-efficient ones. The Kruskal-Wallis non-parametric test was applied to look for statistical significance on the algorithms comparison, and we concluded that ME-MLS + AGA offers a better overall performance than ME-MLS + ad hoc. The experimental analysis shows that ME-MLS + AGA outperforms best Min-Min based heuristic for every instance, with improvements of up to 14.0 % for the makespan and up to 13.9 % in the energy consumption. The performance analysis shows that the two ME-MLS variants have a promising scalability behavior.

As future work, we are working on improving ME-MLS to make it quicker and more accurate, by designing new specialized operators for the problem. Additionally, we plan to integrate the proposed local search algorithms into well-known and accurate multiobjective EAs to look for higher quality solutions. We also plan to tackle dynamic versions of the scheduling problem in HC/grid environments.

Algorithm 1 9 :

 19 Peer threads in the ME-MLS algorithm 1: initialize solution(population, thread index) 2: initialization barrier() 3: while not stop criteria do search strategy ← select strategy(makespan, energy, or random) max iterations ← random(1, THREAD IT) 10: while not end search do 11:

else 20 :

 20 max iterations ← random(1,THREAD IT/REWORK FACTOR)

Fig. 1 .

 1 Fig. 1. Diagram of the ME-MLS algorithm

Fig. 2 .

 2 Fig. 2. Problem encodings: a) machine-oriented encoding, b) task-oriented encoding

)Fig. 4 .

 4 Fig. 4. Approximated Pareto fronts computed by the ME-MLS + AGA algorithm

Fig. 5 .

 5 Fig. 5. Speedup two variants of ME-MLS algorithm

  Local search applied by each ME-MLS thread on schedule s

	8:	operator ← random(move or swap)
	9:	if operator = swap then
	10:	for all y ∈ tasks Y do
	11:	delta x,y ← improvement(search strategy, s , swap x,y )
	12:	delta best ← improvement(search strategy, s , best operation)
	13:	if delta x,y > delta best then
	14:	best operation ← swap x,y
	15:	end if
	16:	end for
	17:
	23:	best operation ← move x,m D
	24:	end if
	25:	end for
	26:	end if
	27: end for
	28: apply operation(best operation)

energy-aware local search performed by each thread in ME-MLS is based on a randomized version of the Problem Aware Local Search (PALS) method [1]. Algorithm 2 1: search strategy ← current optimization strategy (makespan, energy, or random) 2: best operation ← none 3: m A ← random machine(search strategy, s ) 4: m B ← random machine(search strategy, s ) = m A 5: tasks x ← random task set(m A ) 6: tasks y ← random task set(m B ) 7: for x ∈ tasks X do else if operator = move then 18: M ← random machine set() ∪{m B } 19: for all m D ∈ M do 20: delta x,m D ← improvement(search strategy, s , move x,m D ) 21: delta best ← improvement(search strategy, s , best operation) 22:

if delta x,m D > delta best then

Table 1 .

 1 Table1reports the average and best makespan and energy improvements by the two studied variants of ME-MLS with respect to the MinMin based heuristic that performs the best for that instance and objective. The results show that ME-MLS outperforms the best MinMin based heuristic with makespan improvements of up to 14.0 % and energy consumption improvements of up to 13.9 %. Both ME-MLS + AGA and ME-MLS + ad hoc are able to compute schedules with similar average objective values for instances with dimension up to 1 024 × 32. ME-MLS + ad hoc computes slightly better average schedules than ME-MLS + AGA when solving instances with dimension 2 048 × 64. In the small ME-HCSP instances (512 × 16), the best improvements are obtained for the makespan objective, while in the largest ME-HCSP instances (2 048 × 64), the best improvements are obtained for the energy consumption. Figure3summarizes the average improvements by dimension when comparing ME-MLS to each MinMin based heuristic. ME-MLS improvements over the best MinMin heuristic Multiobjective optimization metrics. We compared ME-MLS + AGA and ME-MLS + ad hoc by studying the multiobjective optimization metrics on the Pareto front approximations computed by each algorithm. In order to determine the significance of the comparison, a statistical analysis was performed Average ME-MLS improvements over the MinMin based heuristics over the results for each algorithm, metric, and problem instance solved. First, the Kolmogorov-Smirnov (K-S) test was applied to check whether the metric values follow a normal distribution or not. The values for the D statistic by the K-S test indicated that the results for ME-MLS + AGA and ME-MLS + ad hoc are not normally distributed. As a consequence, the non-parametric Kruskal-Wallis statistical test was performed with a confidence level of 95 %, to compare the distributions for ME-MLS + AGA and ME-MLS + ad hoc.

			ME-MLS + AGA		ME-MLS + ad hoc
	dimension 512 × 16	model heter. Ali high high high low low high low low high high high low Braun low high	makespan best avg 12.9 % 9.4 % 14.0 % 9.5 % 10.9 % 8.3 % 10.9 % 4.1 % 10.7 % energy best avg 9.5 % 4.4 % 9.5 % 5.1 % 9.3 % 5.3 % 7.4 % 11.7 % 9.5 % 9.7 % 6.3 % 5.5 % 3.8 % 5.3 % 2.3 % 10.3 % 8.0 % 8.3 % 4.1 %	makespan best avg 12.3 % 9.1 % 13.5 % 9.2 % 10.9 % 8.4 % 11.2 % 4.0 % 10.7 % 7.4 % energy best avg 9.7 % 4.4 % 9.5 % 5.2 % 9.2 % 5.2 % 11.6 % 9.2 % 10.0 % 6.2 % 5.4 % 3.8 % 5.2 % 2.3 % 10.5 % 7.8 % 8.3 % 4.2 %
		low low	5.9 % 5.0 %	5.5 %	3.2 %	5.9 % 5.0 %	4.7 % 3.1 %
	dimension 1 024 × 32	model heter. Ali high high high low low high low low high high high low Braun low high	makespan best avg 9.7 % 7.3 % 8.7 % 7.2 % 10.8 % 8.7 % 6.8 % 2.3 % 11.4 % energy best avg 9.6 % 5.9 % 8.9 % 5.6 % 9.9 % 7.8 % 8.9 % 8.8 % 6.2 % 9.3 % 5.7 % 10.1 % 7.6 % 9.4 % 6.0 % 8.5 % 6.0 % 7.9 % 4.4 %	makespan best avg 10.5 % 7.1 % 10.0 % 6.2 % energy best avg 9.7 % 6.7 % 9.2 % 5.4 % 11.3 % 9.0 % 9.8 % 7.3 % 7.0 % 2.6 % 11.4 % 8.8 % 9.1 % 6.1 % 10.3 % 6.3 % 10.3 % 7.5 % 9.8 % 6.3 % 8.7 % 5.8 % 8.0 % 4.7 %
		low low	10.5 % 9.0 % 11.3 %	8.8 %	11.3 % 9.3 % 11.0 % 8.5 %
	dimension 2 048 × 64	model heter. Ali high high high low low high low low high high high low Braun low high	makespan best avg 7.2 % 5.0 % 6.2 % 4.2 % 6.8 % 4.5 % 12.7 % energy best avg 9.4 % 4.6 % 9.2 % 4.6 % 9.9 % 3.4 % 0.3 % 12.9 % 9.3 % 7.2 % 4.7 % 9.9 % 5.3 % 7.6 % 6.2 % 9.5 % 6.6 % 7.4 % 5.0 % 9.9 % 4.8 %	makespan best avg 8.5 % 5.7 % 11.1 % 6.8 % energy best avg 7.7 % 5.2 % 10.7 % 6.5 % 7.6 % 6.3 % 12.7 % 9.4 % 4.8 % 1.1 % 13.3 % 9.2 % 8.1 % 5.4 % 10.8 % 7.3 % 7.8 % 6.4 % 10.4 % 8.3 % 8.8 % 5.6 % 11.7 % 7.0 %
		low low	6.4 % 4.3 % 13.9 % 10.1 %	8.0 % 6.0 % 13.8 % 9.6 %

Table 3

 3 reports the average and standard deviation values for spread and RHV diversity metrics for each instance model, heterogeneity class, and problem dimension. For each metric and heterogeneity class, the best algorithm and the number of problem instances in which it is the best with 95 % confidence (i.e. the computed pairwise p-value is below 5 × 10 -2 ) is also reported in the best 95 % column. The result is emphasized in bold font when a given algorithm variant is always better than the other one in the twelve problem instances solved for each instance model, heterogeneity class, and problem dimension.

Table 2

 2 demonstrates that ME-MLS + AGA outperforms ME-MLS + ad hoc in terms of the quality metrics, specially in the largest ME-HCSP instances. Regarding the diversity metrics, Table3shows that both algorithms compute similar results for spread and RHV for dimension 512 × 16, but ME-MLS + AGA was able to find Pareto fronts with better diversity and covering properties for dimension 1 024 × 32 and 2 048 × 64, as it is demonstrated by the values of the spread and RHV metrics.

	dimension 512 × 16	model heter. Ali high high high low low high low low high high high low Braun low high	ND ad hoc 8.33 ± 2.47 4.11 ± 1.43 AGA 10/12 1.00 ± 0.39 1.57 ± 0.76 AGA 6/12 IGD (normalized) AGA best 95 % AGA ad hoc best 95 % 8.02 ± 2.65 4.20 ± 1.39 AGA 8/12 1.00 ± 0.44 1.51 ± 0.73 AGA 5/12 6.67 ± 2.42 3.82 ± 1.20 AGA 10/12 1.00 ± 0.34 1.56 ± 0.64 AGA 8/12 2.84 ± 1.54 2.49 ± 1.12 ad hoc 3/12 1.00 ± 0.40 1.04 ± 0.40 ad hoc 1/12 6.63 ± 3.06 3.75 ± 1.50 AGA 7/12 1.00 ± 0.43 1.53 ± 0.64 AGA 5/12 6.18 ± 3.30 3.36 ± 1.50 AGA 8/12 1.00 ± 0.33 1.65 ± 0.67 AGA 6/12 6.64 ± 3.03 3.84 ± 1.56 AGA 7/12 1.00 ± 0.45 1.31 ± 0.61 AGA 5/12
			low low	6.02 ± 3.10 3.21 ± 1.21 AGA 7/12	1.00 ± 0.36 1.59 ± 0.63 AGA 7/12
	dimension 1 024 × 32	Ali Braun	high high high low low high low low high high high low low high low low	AGA 9.98 ± 0.22 4.44 ± 1.31 AGA 12/12 1.00 ± 0.32 2.38 ± 0.68 AGA 12/12 ad hoc best 95 % AGA ad hoc best 95 % 9.99 ± 0.09 4.16 ± 1.38 AGA 12/12 1.00 ± 0.32 2.62 ± 0.87 AGA 10/12 8.67 ± 1.48 3.63 ± 1.01 AGA 12/12 1.00 ± 0.23 3.35 ± 1.01 AGA 12/12 5.90 ± 1.90 2.92 ± 0.84 AGA 10/12 1.00 ± 0.43 1.57 ± 0.62 AGA 5/12 9.98 ± 0.16 4.14 ± 1.23 AGA 12/12 1.00 ± 0.28 2.29 ± 0.63 AGA 12/12 9.95 ± 0.43 4.72 ± 1.35 AGA 12/12 1.00 ± 0.29 2.48 ± 0.80 AGA 10/12 9.96 ± 0.42 4.75 ± 1.30 AGA 12/12 1.00 ± 0.32 2.38 ± 0.83 AGA 12/12 8.56 ± 1.49 3.63 ± 0.99 AGA 12/12 1.00 ± 0.24 3.06 ± 0.97 AGA 12/12
	dimension 2 048 × 64	Ali	AGA high high 10.00 ± 0.00 5.25 ± 0.92 AGA 12/12 1.00 ± 0.26 2.04 ± 0.62 AGA 12/12 ad hoc best 95 % AGA ad hoc best 95 % high low 10.00 ± 0.05 5.20 ± 0.99 AGA 12/12 1.00 ± 0.25 2.13 ± 0.67 AGA 10/12 low high 9.09 ± 1.19 3.72 ± 1.10 AGA 12/12 1.00 ± 0.20 3.19 ± 0.92 AGA 12/12 low low 8.02 ± 1.63 3.66 ± 1.18 AGA 12/12 1.00 ± 0.26 1.47 ± 0.53 AGA 6/12

Braun high high 10.00 ± 0.00 5.19 ± 0.93 AGA 12/12 1.00 ± 0.26 2.13 ± 0.65 AGA 12/12 high low 10.00 ± 0.00 5.18 ± 0.92 AGA 12/12 1.00 ± 0.26 2.19 ± 0.77 AGA 12/12 low high 10.00 ± 0.00 5.23 ± 0.87 AGA 12/12 1.00 ± 0.29 2.00 ± 0.65 AGA 12/12 low low 9.49 ± 0.86 4.03 ± 1.16 AGA 12/12 1.00 ± 0.19 2.92 ± 1.00 AGA 12/12

Table 2 .

 2 ME-MLS multiobjective quality metrics

  The study indicates that both ME-MLS + AGA and ME-MLS + ad hoc algorithms have a near linear speedup behavior. ME-MLS + AGA is the most efficient and scalable algorithm: it achieves a speedup of 22.4 when using 24 threads, while ME-MLS + ad hoc obtains a speedup of 20.2. Ali high high 1.00 ± 0.14 1.47 ± 0.37 AGA 10/12 0.82 ± 0.04 0.76 ± 0.08 AGA 9/12 high low 1.00 ± 0.14 1.45 ± 0.38 AGA 10/12 0.83 ± 0.04 0.77 ± 0.07 AGA 8/12 low high 1.00 ± 0.15 1.35 ± 0.43 AGA 10/12 0.88 ± 0.03 0.81 ± 0.06 AGA 11/12 low low 1.00 ± 0.14 1.17 ± 0.36 AGA 5/12 0.82 ± 0.06 0.84 ± 0.04 ad hoc 6/12 Braun high high 1.00 ± 0.14 1.46 ± 0.37 AGA 10/12 0.83 ± 0.04 0.76 ± 0.07 AGA 11/12 high low 1.00 ± 0.13 1.44 ± 0.33 AGA 8/12 0.86 ± 0.03 0.78 ± 0.07 AGA 11/12 low high 1.00 ± 0.15 1.49 ± 0.34 AGA 10/12 0.83 ± 0.04 0.76 ± 0.07 AGA 10/12 low low 1.00 ± 0.15 1.43 ± 0.37 AGA 10/12 0.88 ± 0.02 0.81 ± 0.05 AGA 11/12

	dimension 512 × 16	spread ad hoc high high 1.00 ± 0.12 1.07 ± 0.28 AGA 5/12 model heter. AGA best 95 % Ali high low 1.00 ± 0.10 1.05 ± 0.26 ad hoc 4/12 0.82 ± 0.08 0.78 ± 0.08 AGA 6/12 RHV AGA ad hoc best 95 % 0.85 ± 0.06 0.79 ± 0.07 AGA 6/12 low high 1.00 ± 0.15 1.20 ± 0.32 AGA 6/12 0.89 ± 0.05 0.85 ± 0.06 AGA 8/12 low low 1.01 ± 0.15 1.00 ± 0.17 ad hoc 2/12 0.82 ± 0.09 0.81 ± 0.08 none high high 1.00 ± 0.13 1.02 ± 0.29 none 0.84 ± 0.07 0.79 ± 0.08 AGA 7/12 high low 1.00 ± 0.14 1.08 ± 0.33 AGA 5/12 0.91 ± 0.04 0.88 ± 0.04 AGA 6/12 Braun low high 1.00 ± 0.11 1.05 ± 0.25 AGA 3/12 0.80 ± 0.09 0.77 ± 0.09 AGA 6/12
			low low	1.00 ± 0.14 1.12 ± 0.30 AGA 7/12	0.92 ± 0.03 0.91 ± 0.03 AGA 5/12
	dimension 1 024 × 32	Ali Braun	AGA high high 1.00 ± 0.15 1.30 ± 0.40 AGA 9/12 ad hoc best 95 % high low 1.00 ± 0.13 1.17 ± 0.39 AGA 7/12 low high 1.00 ± 0.15 1.39 ± 0.46 AGA 10/12 0.92 ± 0.03 0.81 ± 0.05 AGA 11/12 AGA ad hoc best 95 % 0.86 ± 0.05 0.75 ± 0.07 AGA 11/12 0.84 ± 0.05 0.72 ± 0.08 AGA 11/12 low low 1.00 ± 0.17 1.00 ± 0.34 AGA 2/12 0.90 ± 0.04 0.89 ± 0.04 AGA 5/12 high high 1.00 ± 0.15 1.21 ± 0.42 AGA 7/12 0.86 ± 0.05 0.77 ± 0.06 AGA 11/12 high low 1.00 ± 0.13 1.32 ± 0.36 AGA 8/12 0.85 ± 0.05 0.74 ± 0.07 AGA 11/12 low high 1.00 ± 0.15 1.37 ± 0.39 AGA 10/12 0.86 ± 0.05 0.76 ± 0.06 AGA 11/12 low low 1.00 ± 0.14 1.40 ± 0.43 AGA 10/12 0.91 ± 0.03 0.82 ± 0.05 AGA 11/12
	dimension 2 048 × 64			AGA	ad hoc	best 95 %	AGA	ad hoc	best 95 %

Table 3 .

 3 ME-MLS multiobjective diversity metrics

Acknowledgments

The work of S. Nesmachnow and S. Iturriaga is partly supported by Agencia Nacional de Investigación e Innovación (ANII) and Programa de Desarrollo de las Ciencias Básicas (PEDECIBA), Uruguay. B. Dorronsoro acknowledges that he present work is partially supported by the National Research Fund, Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND). P. Bouvry would like to acknowledge that this work was partly supported by Luxembourg FNR GreenIT project (C09/IS/05).

Pascal Bouvry has a Ph. D. in computer science at University of Grenoble, France. He is now Professor at the Faculty of Sciences, Technology and Communication, University of Luxembourg and head of the Computer Science and Communication research unit (http://csc.uni.lu). He is specialized in parallel and evolutionary computing and his current interest concerns the application of nature-inspired computing for solving reliability, security, and energy-efficiency problems in clouds, grids and ad-hoc networks.