Carole Honoré-Chedozeau
email: carole.honore-chedozeau@vignevin.com

Maud Lelièvre-Desmas

Jordi Ballester

Sylvie Chollet

Bertrand Chatelet

Dominique Valentin

VINEYARDS AND GRAPE VARIETIES: WHAT IS GOING ON IN WINE PROFESSIONAL AND CONSUMER MINDS?

Keywords: vineyards, grape varieties, mental representation, wine labels, experts, consumers

Vineyard and grape variety are two popular ways of classifying wines. Vineyard designation is a traditional practice for European wine labels but is being increasingly replaced by grape variety designation, mainly used for New World and Swiss wine labels. In a context of wine categorization, we investigated on the relationship between those two dimensions. For this purpose, we selected a set of 56 wine labels to represent three red grape varieties (Gamay, Pinot Noir and Gamaret) and three vineyards (Beaujolais, Burgundy and Switzerland). Three panels were recruited: a panel of 30 wine professionals (experts) from the Beaujolais vineyard, a panel of 30 wine consumers from the Beaujolais vineyard and a panel of 30 wine consumers from Lille, a French region without wine production. We used a free hierarchical sorting task on labels coupled with a verbalization task and an interview. Data were first analyzed separately for each panel using a Hierarchical Multiple Factor Analysis and a Hierarchical Ascending Classification. Results showed that the three panels yielded very similar wine groups. With the exception of Gamaret wines, most French wines were separated by both vineyard and grape variety while Swiss wines were separated by grape varieties. Despite this similar categorization pattern, the interviews revealed different sorting criteria and strategies used to sort the labels for each panel. With the exception of a small part of experts, both experts and consumers from Beaujolais used their knowledge of grape varieties and vineyards to sort the wine labels while the consumers from Lille simply read the labels to find clues and deduce wine groups, because of a lack of knowledge. Overall, the results indicate an interaction between vineyard and grape variety dimensions for the wine categorization by experts and consumers. The methodology proposed seems to be a promising tool that could be helpful to improve the promotion of wines.

INTRODUCTION

Vineyard and grape variety are two popular ways of classifying wines, widely transmitted via wine books, guides and websites, wine stores and restaurants. Vineyard designation is a traditional practice for European wine labels whereas grape variety designation is mainly used for New World and Swiss wine labels. The traditional vineyard designation is more and more often replaced by grape variety because of the New World wine market success. Understanding the large amount of information written on labels (producer's name, vintage, region, appellation, brand name, grape variety, legal mentions, etc...) is a daunting challenge for consumers. Aware of this challenge, many wine books, guide and websites tried to explain how to read wine label information. However, this is a difficult task as the information appearing on labels varies according to the country because of different law constrains. Many studies in marketing provide interesting results on the type of information used by consumers in a context of wine purchase decision and preferences (to name just a few: [START_REF] Atkin | Appellation as an indicator of quality[END_REF][START_REF] Charters | Consumer responses to wine bottle back labels[END_REF][START_REF] Gmuer | Does wine label processing fluency influence wine hedonics?[END_REF][START_REF] Tang | Perception of wine labels by Hong Kong Chinese consumers[END_REF][START_REF] Thomas | The Importance of Wine Label Information[END_REF]. In this study, we tried to understand the information wine professionals and consumers use to categorize wine labels. Do wine professionals and consumers rely on grape varieties and vineyards information? And if yes, what is the relationship between those dimensions?

MATERIAL AND METHODS

Wine labels

A set of 56 red wine labels was selected to represent six categories: three red grape varieties (Gamay, Pinot Noir and Gamaret) and three vineyards (Beaujolais, Burgundy and Switzerland). Each category was represented by 10 wine labels, with an exception for the Gamaret from Beaujolais vineyard category (six labels) because of a small production of these wines (Figure 1). Wine labels were collected in picture form from an Internet research by keywords for each wine category in order to represent as much as possible the diversity of wine labels.

Panels

Three panels of assessors with different expertise and familiarity with wines were recruited: a panel of 30 wine professionals from the Beaujolais vineyard (experts, 18 men, 12 women, mean-age = 45.13), a panel of 30 wine consumers from the Beaujolais vineyard (familiar consumers, 18 men, 12 women, mean-age = 46.40) and, a panel of 30 wine consumers from Lille, a French region without wine production (unfamiliar consumers, 13 men, 17 women, mean-age = 48.70). The wine consumers were recruited by means of an online questionnaire, in both Villefranche-sur-Saône and Lille, including socio-demographic questions as well as wine-tasting experience and drinking habits. The criteria used to select wine consumers were: not under the legal drinking age of 18, drinking wine at least once a year, no professional wine experience, not a member of a tasting club, and no formal training in wine-tasting or wine production.

Procedure

The experiment was conducted individually, with each assessor supervised by the same experimenter, in a quiet, private room. The 56 wine label cards were shuffled three times to ensure randomness before being presented simultaneously to the assessor on a white table. There was no time limit for either step. The procedure lasted from 20 minutes to one hour for each assessor.

The assessors were first asked to group the wine labels that belong to the same wine category: "You have in front of you a set of wine label pictures. Please group the wine labels that, in your opinion, belong to the same wine category. You can make as many groups as you like, with a minimum of two groups". They were free to make as many groups as they like. Depending on the number of groups obtained, the assessors were then asked to group together or to separate the groups initially formed as far as possible. After that, they were asked again to group together or to separate the groups formed in the two previous sorting. The goal of those sortings was to obtain a hierarchy at the end. After that, they were asked to describe with their own words and expressions the groups formed. Finally they were interviewed to indicate which criteria and strategies they used to sort the wine labels. Each interview was recorded with a dictaphone.

Data analysis

Data were first analyzed separately for each panel using a Hierarchical Multiple Factor Analysis (HMFA) coupled to a Hierarchical Ascending Classification (HAC), which was performed on the first HMFA dimensions explaining 85% of variance with Ward's criterion. The resulting clusters from the HAC are represented on the HFMA projections by dotted rectangles. The frequency of occurrence of words was computed for each cluster produced by HAC. An hypergeometric law was used to identify the words that best characterize each cluster [START_REF] Lebart | Statistique exploratoire multidimensionnelle : Visualisation et inférence en fouille de données[END_REF]. A Correspondence Analysis (CA) coupled to an HAC was then performed on the interview data in order to highlight the main criteria and strategies used to sort the wine labels by each panel, using a hypergeometric law. All statistical analyses were performed using the free software R, version 3.2.2 for Windows (R Core Team, 2015) with the additional R packages SensoMineR (Lê and Husson, 2008) and FactoMineR (Lê et al., 2008).

RESULTS AND DISCUSSION

3.1. Free hierarchical sorting 3.1.1. Expert panel A graphical projection of the assessors on the first two dimensions of the HMFA showed a division within the expert panel in two sub-groups: one with 22 experts and a second with the remaining eight experts (figures not shown). In order to better understand this division, separate HMFA coupled to HAC were conducted for each sub-group of experts (Figures 2a and2b). Figures 2a and2b show the projections of wine labels on the first two dimensions of the HMFA along with the 95% confidence interval around each label for each subgroup. The first and second dimensions explain 23% of the variance for the first sub-group of experts (Figure 2a) and 20.95% for the second sub-group of experts (Figure 2b). For the first sub-group of experts, the seven clusters obtained correspond to the expected taxonomy with few exceptions (Figure 2a) while those from the second sub-group of experts do not (Figure 2b). The Figure 2b shows an organization of the wine labels based on multi-criteria for the second sub-group of experts. Those results suggest two different categorization strategies within the panel: a categorization based on vineyards and grape varieties and another one on other criteria reflecting different strategies (marketing, aestheticism and design).

Familiar panel

Figure 3 shows the projections of wine labels on the first two dimensions of the HMFA, with a confidence interval of 95%.The first and second dimensions explain 22.10% of the variance. The first dimension opposes the Pinot Noir from Burgundy and Switzerland (PS and PB, on the right) to the Gamay from Beaujolais and the Gamaret from Beaujolais and Switzerland (GB, GtB and GtS on the left). The second dimension opposes the Gamay from Beaujolais and the Pinot Noir from Burgundy (at the top) to the Gamay, Gamaret, Pinot Noir from Switzerland and the Gamaret from Beaujolais (at the bottom). As was the case with the first sub-group of experts, the seven clusters correspond to the expected taxonomy with few exceptions. The clusters are named either by vineyards, appellations or grape varieties.

Unfamiliar panel

Figure 4 shows the projections of wine labels on the first two dimensions of the HMFA, with a confidence interval of 95%. The first and second dimensions explain 20.5% of the variance (Figure 4). The first dimension opposes the Gamay from Beaujolais (GB, on the right) to the Pinot Noir, the Gamay and the Gamaret from Switzerland and the Gamaret from Beaujolais (PS, GS, GtS and GtB, on the left). The second dimension opposes the Gamay from Beaujolais, the Pinot Noir from Burgundy and Switzerland (at the top) to the Gamay from Switzerland and the Gamaret from Switzerland and Beaujolais (at the bottom). As was the case with the first sub-group of experts, the five clusters obtained correspond to the expected taxonomy with few exceptions. The clusters are named either by vineyards, appellations or grape varieties. With the exception of the second subgroup of experts, results showed that the three panels yielded very similar wine groups. The clusters were named either by vineyard or grape variety (Figures 2a, 3 and4), but with some differences. Most French wines were separated by both vineyard and grape variety: the Pinot Noir from Burgundy and the Gamay from Beaujolais. Moreover, for all panels, Gamaret wines were clustered together regardless of their origin (Swiss or Beaujolais). With the exception of Gamaret, Swiss wines are separated from French wines and subdivided in two groups based on grape varieties (Pinot Noir and Gamay).

Interview analysis

Despite this similar categorization pattern, the interviews revealed different sorting criteria and strategies between panels (Figure 5). The first and second dimensions of CA shown in Figure 5 explain 90.02% of the variance. The first dimension opposes the unfamiliar consumers, the familiar consumers and the first sub-group of experts (on the left) to the second sub-group of experts (on the right), while the second dimension opposes the unfamiliar consumers (at the top) to the first sub-group of experts (at the bottom). The HAC performed on the CA dimensions yielded three clusters of criteria and strategies. The hypergeometric law showed that the first cluster, including name of the wine, cellaring potential, quality, search for salience, similarities and all possible clues and also lack of knowledge, was mostly used by the unfamiliar consumer panel. The second cluster, including crus, origin, bottling, appellation, grape variety, nouveau/primeur wine, quality of information and knowledge was mostly used by the first sub-group of the expert panel while the third cluster, including hedonism, visual appearance, desire, producer name, marketing and recall, was mostly used by the second subgroup of the expert panel. Both the majority of the experts and consumers from Beaujolais used mainly their knowledge of the grape varieties and vineyards (origin) to sort the labels the consumers from Lille simply read the labels to find clues and deduce wine groups because of a lack of knowledge for those wines.

CONCLUSION

Overall, the results indicate an interaction between the grape variety and the vineyard dimensions for the wine categorization by experts and consumers. Vineyard and grape variety designations have therefore the same weight in categorizing the wine labels. For the experts, two sub-groups were, however, identified: a first subgroup of experts that categorized the labels by vineyards, appellations and grape varieties thanks to their knowledge (like the familiar consumer panel) and a second one that categorized the labels with other goals in mind (marketing, distribution network, hedonism, recall). Because of a lack of knowledge, the unfamiliar consumers simply read the labels to find clues and deduce the wine groups, categorizing the labels by vineyards and grape varieties with some errors. So different expertise and familiarity levels lead to similar categorizations of wines from different vineyards and grape varieties but different criteria and strategies were used to reach these categorizations suggesting different mental wine representations. Label information provide access to the same wine categories and seem to be sufficient to allow consumers for deducing the same wine categories than the experts and the familiar consumers, with however some errors. The methodology proposed seems to be a promising tool that could be helpful to improve the promotion of wines.

Figure 1 :

 1 Figure 1: The wine taxonomy

Figure 2 :

 2 Figure 2: Projections of wine labels on the first two dimensions of the HMFA for (a) the first subgroup and, for (b) the second subgroup of experts. PB: Pinot noir from Burgundy; PS: Pinot noir from Switzerland; GB: Gamay from Beaujolais; GS: Gamay from Switzerland; GtB: Gamaret from Beaujolais; and GtS: Gamaret from Switzerland.

Figure 3 :

 3 Figure 3: Projections of wine labels on the first two dimensions of the HMFA for the familiar consumers. PB: Pinot noir from Burgundy; PS: Pinot noir from Switzerland; GB: Gamay from Beaujolais; GS: Gamay from Switzerland; GtB: Gamaret from Beaujolais; and GtS: Gamaret from Switzerland.

Figure 4 :

 4 Figure 4: Projections of wine labels on the first two dimensions of the HMFA for the unfamiliar consumers. PB: Pinot noir from Burgundy; PS: Pinot noir from Switzerland; GB: Gamay from Beaujolais; GS: Gamay from Switzerland; GtB: Gamaret from Beaujolais; and GtS: Gamaret from Switzerland.

Figure 5 :

 5 Figure 5: Projections of the main criteria and strategies used by the panels (Expert 1, Expert 2, Familiar consumers and Unfamiliar consumers) on the first dimensions of the CA.

Acknowledgments

This research was supported by CIFRE convention no.2013/1066 and Inter Beaujolais.


Ricardo Bispo Vieira
email: ricardo.bispo-vieira@exascale-computing.eu

Antoine Capra
email: antoine.capra@atos.net

Patrick Carribault
email: patrick.carribault@cea.fr

Julien Jaeger
email: julien.jaeger@cea.fr

Marc Pérache
email: marc.perache@cea.fr

Adrien Roussel
email: adrien.roussel@cea.fr

Detecting Non-Sibling Dependencies in OpenMP Task-Based Applications

Keywords: OpenMP task, Nested task, OMPT, Data dependency, Datarace > OMP_TOOL_LIBRARIES=Ompt_tool.so OMP_NUM_THREADS=2 mpcrun ./testCase3 * 0x2b7730422e70 < 1, 3, in >< 2, 6, out >

come   L'archive ouverte pluridisciplinaire

Introduction

The advent of multi-core processors occurred more than a decade ago, bringing processors scaling from a few cores to several hundreds. To exploit those functional units, the OpenMP programming model [START_REF]OpenMP Architecture Review Board: OpenMP Application Program Interface Version 5[END_REF] became the defacto standard leveraging the programmability and the performance of such systems. Based on compiler directives and the fork-join model, it spawns threads and implies a synchronization rendez-vous at the end of parallel regions. Mainly oriented to structured and regular parallelism first, it has been extended with a task programming model to enable efficient use of irregular and nested parallelism. Even if this tasking model has proven to provide good performance, global synchronizations are expensive and may prevent scheduling of upcoming tasks. Therefore, the notion of data dependency has been introduced, to provide a lighter local synchronization between successive dependent tasks. These dependencies can be expressed only between sibling tasks (i.e., created by the same parent task). The execution order of these tasks is given by the creation sequence (task directives order in the code) and the depend clauses. We call the sets of tasks spawned from the same parent a dependency domain.

Combining nested tasks with data dependencies may lead to some issues because of the parallel execution of tasks between dependency domains. Indeed, dependencies only apply between sibling tasks. However, these dependencies are not passed on the next generation of tasks. Hence, two dependency domains issued from sibling tasks with dependencies will not inherit their parent order. In this case, race conditions may occur even if the programmer thinks the dependencies are correctly expressed in the depend clauses. Correctly specifying a large number of dependencies across multiple dependency domains implies a non negligible burden to the developer and remains error prone.

In this paper, we aim at detecting such dependency declaration errors. The contribution of this paper is threefold: 1) we develop an algorithm to detect possible data races based on declared task dependencies, 2) we propose new extensions to the OMPT interface for keeping track of the memory scope of dependency variables and, 3) we implement the OMPT extensions in an OpenMP implementation and the algorithm in a tool to effectively detect data races.

The remaining of the paper is organized as follows: Section 2 presents some motivating examples. Related work regarding nested tasks with data dependencies and their correctness is presented in Section 3. Then, Section 4 explains the main contribution through the dynamic detection of race conditions among data dependencies in non-sibling tasks. Section 5 describes the implementation of our approach while Section 6 illustrates our tool output and its overhead on some applications, before concluding in Section 7.

Motivating Examples

When considering nested tasks, each task in a dependency domain generates its own children tasks, hence its own dependency domain. By representing each task with a vertex, and linking each task to its children with an edge, it results a tree structure. We call such tree a spawn-tree. Since dependencies can only induce scheduling constraints inside a dependency domain (i.e., between sibling tasks), there is no ordering between tasks from different domains. Thus, these tasks can run concurrently in any order, even if they are at different levels in the spawn-tree. Indeed, specifying a dependency clause at a given level in the task nest does not propagate it to deeper levels (i.e., to children tasks). This might become tricky as, from the user point of view, dataflow information has been expressed. However, the resulting behavior and scheduling may not be the one expected. We present very simple test cases to illustrate such possible data races with misleading depend clauses.

Wrongly expressed dependencies. Listing 1.1 presents a test case based on nested tasks with data dependencies. The first task (single directive -task Fig. 1: An OpenMP code with nested tasks with dependencies and its corresponding spawn-subtree. Dotted ellipses in the tree are for dependency domains. 0 in the spawn-tree represented in Figure 1a) spawns two children tasks with dependencies (task constructs lines 5 and 9 with depend(in) and depend(out) clauses -tasks 1 and 2 in the spawn-tree). These tasks belong to the same dependency domain (dotted ellipse around task 1 and 2 in the spawn-tree). Each of these tasks spawns two other children tasks with dependencies (task constructs with depend(inout) clauses -tasks 3, 4, 5 and 6 in the spawn-tree).

The parents tasks 1 and 2 have serialized dependencies over a, ensuring an order. However, their children don't inherit this dependency. Without any taskwait directive at the end of task 1 to ensure that all its children tasks have finished before task 1 ends, all the tasks at the last level of the tree can run concurrently. Moreover, the children of task 1 can run concurrently with task 2. If the variable a is effectively written as suggested in the depend clauses, a race condition on a may happen. Listing 1.2: Unexpressed/Hidden dependencies Unexpressed/hidden dependencies. Listing 1.2 presents a similar test case, except that parent tasks don't express a data dependency over a. In this case, adding a taskwait directive is not enough to order all tasks. Since there is no inferred writing of a between the parent tasks, they can be executed in any order, and even concurrently. Hence, ensuring that all children tasks are finished does not enforce an order between other tasks at the same tree level, as the tasks from the two lower dependency domains can run concurrently, also causing data races. One possibility to solve this issue is to apply children dependency clauses to the parent tasks. Thus, these dependencies are said to be unexpressed (or hidden).

Listing 1.3 presents the same behavior: two tasks are spawned inside parallel construct. Even without nested tasks, the same problem occurs due to implicit tasks. Indeed, the parallel construct first spawns implicit tasks (one per OpenMP thread). Due to these implicit tasks, the explicit task creations (task constructs) represents the second level in the spawn-tree. For example, if one considers 2 OpenMP threads, thus two implicit tasks, this listing produces the same spawn-tree as depicted in Figure 1a. The implicit task level cannot accept depend clauses. Hence, the dependencies expressed on the explicit tasks are hidden to the implicit ones, causing the ordering issue as before. The same applies when creating explicit tasks with dependencies in a worksharing-Loop construct. v a r i a b l e a ; main ( void ) #pragma omp p a r a l l e l { #pragma omp t a s k depend ( i n : a ) {} #pragma omp t a s k depend ( i n o u t : a ) {} } Listing 1.3: Tasks with dependencies in implicit task

Related Work

The OpenMP support for tasks with dependencies has shown a growing interest from the community of developers and researchers, in various topics such as scheduling [START_REF] Rana | A Scalable Task Parallelism Approach for LU Decomposition With Multicore CPUs[END_REF], data locality [START_REF] Virouleau | Description, Implementation and Evaluation of an Affinity Clause for Task Directives[END_REF] and more generally performance optimization [START_REF] Ghane | False Sharing Detection in OpenMP Applications Using OMPT API[END_REF][START_REF] Agullo | Bridging the gap between OpenMP and task-based runtime systems for the fast multiple method[END_REF]. Thus, Perez et al. propose an extension of the OpenMP task directive to apply dependencies between different family lineage of domain dependencies [START_REF] Pérez | Improving the Integration of Task Nesting and Dependencies in OpenMP[END_REF]. The new clauses weakwait, weakin, weakout, weakinout and release refine the dependency relationship in a two-step process starting by applying inner-task dependencies directly to the outer-task successors at a weakwait synchronization point. Early processing is possible as the release clause indicates that no more dependencies will be expressed on the listed variables. Then, outer tasks with a weak dependency clause pass down predecessors dependencies to inner subtasks. The results obtained with these new extensions are coherent with the theoretical study conducted by Dinh et al. [START_REF] Dinh | Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers[END_REF]. In the nested dataflow model (ND), they showed that modified scheduling algorithms achieve better locality reuse and higher performance on large number of processors. ND is the extension of the nested parallel model (NP) with dependencies, where the fire construct completes the parallel and sequential constructs representing partial dependencies between two dependency domains. They introduced a methodology called DAG rewriting system (DRS) to translate from NP to ND and use it to revisit existing linear algebra algorithms, providing material for the modified scheduling proof. But these approaches do not enable debugging of current OpenMP task-based applications. For this purpose, data-race detection methods exist, based on either static, dynamic, or post-mortem approaches. Nonetheless, the majority only provides support for tasking model without data dependencies. Some tools support tasks with dependencies. Protze et al. [START_REF] Protze | Towards providing low-overhead data race detection for large OpenMP applications[END_REF] proposed an efficient and scalable OpenMP data-race detection tool called Archer based on a static-dynamic method for large HPC applications: relying on a LLVM compilation pass for static analysis and on ThreadSanitizer for dynamic analysis via code instrumentation and Happens-before relation. They annotated the OpenMP runtime to reduce false positives arising from synchronizations points and locking. They defined three detection states resulting from static analysis, race free, certainly racy and potentially racy regions. On top of that information, they extend ThreadSanitizer to take as input a blacklisted set of race-free regions, notably reducing amount of instrumentation at dynamic analysis. In [START_REF] Protze | OpenMP Tools Interface: Synchronization Information for Data Race Detection[END_REF], they detailed how they reported OpenMP runtime annotations into OMPT events callbacks, providing a portable data race detection tool with support for tasks with dependencies. Matar et al. [START_REF] Matar | Runtime Determinacy Race Detection for OpenMP Tasks[END_REF] conducted a similar study mainly oriented to tasking programming model, relying on ThreadSanitizer and the Happens-before relation for dynamic analysis. They proved that their tool, Tasksanitizer, is more efficient at task level to detect determinacy races. However, when combining nested tasks with dependencies, their respective solutions might be related to task scheduling, missing some possible race conditions. Our approach does not instrument every memory access, but it tracks dependency clauses and deals with the hierarchy of tasks, whatever the scheduling of those tasks. It is therefore complementary to methods like Archer and Tasksanitizer.

Detecting Dependencies Between Non-Sibling Tasks

Section 2 showed how unexpressed dependencies or the absence of taskwait directive in descendant tasks may lead to data races, despite the expression of dependencies on some tasks. In this Section, we present our approach to detect such wrong behavior. First, we will describe our approach with our main algorithm to detect potential data races based on the expressed dependencies. Then, since dependencies in OpenMP are passed through variables (i.e., logical memory addresses), we present in a second part how we detect that the depend clauses on the same address indeed concern the same variable.

Main Approach

Our main approach to detect potential data races in nested tasks is based on spawn-tree subgraph and their isolation. Each task t in a dependency domain will generate its own subtree in the spawn-tree. This subtree regroups all the tasks having the task t as an ancestor. All the tasks from the subtree of t should be compared with the subtree spawned from the siblings of t. However, these subtrees may not be compared in one case: if the t subtree is isolated.

A subtree is isolated if all the tasks in the subtree are enforced to be finished before any subtree from a subsequent sibling is started. Thus, the t subtree is isolated from another t subtree if, and only if, there is an ordering between t and t , and all tasks in t subtree are done before starting task t and its own subtree. This isolation can be achieved with several methods. The first method consists in putting a taskwait directive after the last task of each level in the t spawn-tree. The second method encapsulates task t in a taskgroup construct ending before task t . A third method inserts a if(0) clause on each task of the subtree.

If the subtree is isolated, no tasks from the t subtree may run concurrently with t subsequent sibling tasks. On the other hand, if the t subtree is not isolated from the subtrees of t subsequent siblings, tasks of multiple subtrees may run concurrently. In such case, it is necessary to test each task in all subtrees in a pairwise manner to detect depend clauses on same addresses. If this occurs, and the address in the multiple depend clauses refers to the same variable, then a data race may occur. Algorithm 1 presents these different steps. We will describe it on a small example. Listing 1.4 presents a task-based Fibonacci kernel extracted from the BOTS benchmarks [START_REF] Duran | Barcelona OpenMP Tasks Suite: A Set of Benchmarks Targeting the Exploitation of Task Parallelism in OpenMP[END_REF] and modified to express dependencies. In this new program, each invocation of the fib function creates three tasks: one for each new invocation of the fib function, and a third task to realize the sum of the f i b ( n ) i n t x , y , s ; i f ( n < 2 ) return n ; #pragma omp t a s k s h a r e d ( x ) depend ( o u t : x ) { x = f i b ( n -1 ) ; } #pragma omp t a s k s h a r e d ( y ) depend ( o u t : y ) { y = f i b ( n -2 ) ; } #pragma omp t a s k s h a r e d ( s , x , y ) depend ( i n : x , y ) { s = x + y ; } #pragma omp t a s k w a i t return s ;

Listing 1.4: Task-Based Fibonacci with dependencies two sub-results. The two fib invocations are independent (depend(out:x) and depend(out:y) clauses respectively), but the last task depends from the two previous tasks (depend(in:x,y) clause). The computation of fib(4) with this new algorithm produces the spawn-tree displayed in Figure 2a.

In our algorithm, we study each pair of tasks in each dependency domain, starting with the set of tasks generated by the root of the spawn-tree (l.3 and l.5 in the algorithm). Applied to the fib(4) example, we start by studying the tasks fib(3) and fib(2) at the first level. For each pair, we check if there is an isolation between their subtrees, hence if these tasks are ordered and all descendant tasks of the first task are enforced to be finished before starting the other task. We start by looking if the two tasks are ordered. To do so, for each dependency domain, we build a Directed Acyclic Graph (e.g., DAG) representing the complete ordering of tasks, thanks to depend and if clauses, taskwait and taskgroup directives. Then detecting if two tasks are ordered in a dependency graph is equivalent to find a path between the two tasks in the DAG (l.6). If there is a path, then the two tasks are ordered.

Figure 2b depicts the DAG generated for the dependency domain formed by the leaf tasks in subtree B. Since the two fib invocations are independent, there is no link between them. However, two links come from these tasks towards the third (sum) task, due to the depend(in) expressed dependencies. Hence, an order exists between fib(0) and (sum), and an order also exists between fib(1) and (sum).

We then check if the first subtree is isolated. If so, it is useless to detect potential conflicts between these subtrees (l.7-9). In the example, if the subtrees from fib(3) and fib(2) are isolated, no data race can happen between (sum) and the subtrees. However, it will not prevent data races between the subtrees, as they can be executed in any order, and even concurrently.

If no isolation is detected, we need to compare every pair of tasks in the tested subtrees (l.11-12). We check each depend clause from the two tasks to detect potential conflicting memory access (l.13). Once all the current sibling tasks are tested, we do the same procedure with the next level in the spawntree.

Tracking Memory Scope

The OpenMP runtime only uses the address of memory storage to express the dependencies. When detecting conflict with addresses, two cases arise. First, the address always identifies the same variable throughout the program execution. It is the case for global variables. On the other hand, some addresses can be reused throughout the program to store different variables. It is the case for heap and stack addresses, through function calls and return statements or memory allocation/deallocation. To ensure that the detected conflict on addresses passed to depend clauses can actually lead to a data race, we have to ensure that the same address relates to the same variable.

The fibonacci example can illustrate such behavior. With the dataflow based fibonacci algorithm, we can see that the same pattern of tasks may be replicated in the spawn-tree. It is the case for the subtrees B and C in Figure 2a.

When the program is running, the following behavior can happen. First, a thread runs the task which is the root node of subtree B. This task declares dependencies on stack addresses for variables x, y and s for the children task. Upon completion of the task, stack memory is recycled for the next instructions. If the root node of subtree C is then scheduled on this same thread, as it is the same task as the root of subtree B, it will map the same variables to the same stack addresses. The executing task will also declares dependencies for variables x, y and s, which happen to have the exact same stack addresses than the dependencies declared for the previous task. However, they are not related, and the reuse of addresses only relates to this specific scheduling. It is necessary to check if the use of the same addresses in multiple depend clauses are indeed related to the same variables.

Data scoping is a key element in OpenMP, and more generally in shared memory programming models. It describes if a specific data is shared among threads or is local to a thread. By default, scope attribute is set to shared for threads and implicit tasks, and to firstprivate for explicit tasks. OpenMP provides clauses to modify the scope attribute of data: shared exhibits data's memory address to all threads, and private, firstprivate or lastprivate create a thread's local data copy (different memory address). The firstprivate clause is a special case, the value of the variable is passed on to the local copy. By this way, if the variable value is an address, it violates the private attribute since all threads having the local data copy can simultaneously access the same memory storage. If the variable is used later in a depend clause, it may lead to a concurrent access.

To ensure that the same address in multiple depend clauses relates to the same variable, we record the data scoping attributes at task creation. We then study the data scoping path, i.e. the variable's scope attribute at each level between a task and a child task of its lineage. A color c is associated with each tested pair of tasks and each tested address. For the two tested tasks, we go up in the spawn-tree and check at each level if the address is a shared data, or if it was a value passed in a firstprivate clause. In both cases, the link to the checked level is colored with the color c. Once a common ancestor for the two tasks is found in the spawn tree, we obtain a direct path between the two tasks. If all the links in the path have the same color c, it means that the tested address was passed by the common ancestor down to the two tested tasks, and that the address relates to the same variable. Hence, the tested depend clauses may actually cause a data race, and the DetectConflicts phase in our algorithm raises an issue. To illustrate this coloring search, we focus on x variables from fib(1) invocations. To both tasks fib(1) from subtrees B and C for variable x, we use the color c 0 . Since the variable is in a shared clause for both tasks, the links between these tasks and their parents (respectively roots of subtrees B and C) are colored with c 0 . However, the variable passed in the shared clause is a newly created variable and does not come from a previous shared clause (or firstprivate clause). Hence, the upward links are colored with a new color c 1 (from root node of subtree B to fib(3) task, and from root node of subtree C to fib(4) task). For the same reason, the last link from fib(3) to fib(4) will have a new color c 2 . Once this link is colored, we obtain a colored path between the two tested tasks. However the path has multiple colors, hence the two addresses don't relate to the same variable. No potential data race will be raised, even if the depend clauses use the same memory address.

Method limitations

Our method uses the same information as the OpenMP dependencies mechanism, i.e, the memory address. We do not aim to detect nor instrument actual memory access, but only to check if the dependencies declared in the OpenMP task constructs are coherent. As we are based on the addresses passed in the dependency clauses, our method may miss some data races or report false positive.

The false positive arises when the task constructs declares dependencies on variables which are not used in the task, or in its descendant tasks. In these cases, our method returns a potential data race. However, since the variables are not used in the tasks, it is not a data race. These variables might just have been used to infer ordering between tasks with no actual read or write.

In the same way, if variables are used in a task but do not appear in a depend clause, our method will not consider the variable. The same also happens if a variable a variable is used in the task spawning a dependency domain, with tasks declaring dependencies on the same variable. In these cases, out method will not detect the potential data race. #pragma omp t a s k depend ( i n : a )

#pragma omp t a s k depend ( o u t : a ) { a = s o m e v a l u e ; } l o c a l = a ; Listing 1.5: Nested tasks with potential race conditions The test case in listing 1.5 presents such scenario. Based only on the dependency declarations, there is no way to detect when the actual memory access is performed in the parent task, i.e, before or after the child task.

Tool Implementation

Our detection method is based on the task spawn-tree and the DAG built from dependency clauses information. Building and maintaining such structures requires accessing information from the OpenMP directives and internals in addition to those provided by its API: e.g., when a parallel region starts and ends, when synchronizations occur at multiple levels, be informed of tasks creation and retrieve their dependencies set if any. These information are tightly linked to the OpenMP API and runtime implementation.

The OMPT [START_REF] Eichenberger | OMPT: An OpenMP Tools Application Programming Interface for Performance Analysis[END_REF] interface aimed at developing portable performance and analysis tools for OpenMP. Recently released as part of the OpenMP specification, it provides an instrumentation-like portable interface for tool callbacks. A callback is a function that is registered during the tool initialization to be triggered at corresponding events. In addition, OMPT specifies a collection of inquiry functions to probe the OpenMP runtime for internal information.

Our tool can either be used at runtime or post-mortem through the generation of a trace. Both versions use the same information that can be gathered through the set of OMPT callbacks listed below. Implementation has been done inside the MPC framework [START_REF] Carribault | Enabling Low-Overhead Hybrid MPI/OpenMP Parallelism with MPC[END_REF], a hybrid MPI/OpenMP runtime which support the OMPT interface. During the initialization phase, we create the internal structures and the root task of the spawn tree. Then, to instrument all OpenMP tasks in the application, the tool registers the following OMPT callbacks to the OpenMP runtime:

-ompt callback parallel {begin/end} t: callbacks to register the entry and exit points of parallel regions. We use the begin event to retrieve the number of threads inside the parallel team. During the end event, we deallocate all nodes of the spawn tree, if any, and its related dependencies. Only the root task remains as the code returns to the initial task.

-ompt callback implicit task t: callback triggered during the creation of implicit tasks. We use it to add nodes representing the implicit tasks of the parallel region into the spawn tree.

-ompt callback sync region t: callback to register region synchronization. Its parameters contain the synchronization type (i.e. a barrier, a taskgroup or a taskwait) and the endpoint scope (i.e. the beginning or the end of the synchronization). We use it for partitioning the dependency domain at the explicit task level. In the runtime version, the main algorithm 1 for data race detection is trigerred. This allows to reduce memory consumption by only keeping and applying resolution on one instance of the spawn-tree at the time. In post-mortem version, trace generation is performed by dumping local buffers to output files.

-ompt callback task create t: callback to register the creation of an explicit task. We use this callback to add a task node to our internal spawn tree representation at the creation of an explicit task. Such informations are stored in local buffers in the post-mortem version.

-ompt callback dependences t: callback to register all dependencies specified on a new task. We retrieve the dependencies of the newly created task, and update the dependency DAG of the parent task node. Such informations are stored in local buffers in the post-mortem version.

OMPT extensions. Section 4 highlights that it is necessary to know the data sharing attribute of a dependence to detect data races in the context of nested tasks with dependencies. The current OMPT interface exposes the scope of a parallel region, the spawning sequence of tasks and the dependencies between these tasks. But it lacks a way to provide information about data-sharing attributes at constructs, needed in our method to detect false positives. To do so, we propose the following extensions to the OMPT interfaces. The data sharing attributes of each variable are retrieved at task creation. We extend the callback to also store an array with the data collection inherited from outer scope to the new task (see Listing 1.6). This array contains values for each variable: if a variable is shared, the array contains its address. If a variable is firstprivate, the array contains the variable value. The location of the address variable used in the depend clause is required to eliminate false positive in our data race detection method. We extended the structure exposed in Listing 1.7 to include an int value to store this location.

Experimental Results

An enumeration of available applications using nested tasks with dependencies lead to a small set of candidates. Upon ad hoc test cases based on those presented throughout the whole paper and the modified Fibonacci, the Kastors benchmarks suite [START_REF] Virouleau | Evaluation of OpenMP dependent tasks with the KASTORS benchmark suite[END_REF] provided a suitable candidate. The Strassen benchmark is a wellknown algorithm for matrix multiplication that achieves lower execution bound than the regular method O(n 3 ). It recursively splits the matrices and applies the Strassen method in a divide and conquer manner, until a specified cutoff is reached where the regular method turns back to be more efficient. We present the output format of our tool and its associated overhead on these benchmarks.

Output description. The generated output goes along with the approach described as follows: the nodes of the spawn tree are numbered in a breadth-first search manner, therefore, the root has the number 0, each implicit task has the number between [1,...,N] where N is the number of threads participating to the parallel region, and the explicit tasks have a number between ]N,...,M] where M is the total number of nodes in the spawn tree. Two conflicting nodes n and n respectively belonging to the subtree where nodes rn and rn are the roots and with dependencies d and d on a variable address addr generate the following output: * addr < rn, n, d >< rn , n , d >

The small example above is the output of our tool for Listing 1.3. The corresponding spawn-tree is depicted in Figure 1a. Our tool returns three potential data races: task 3 with task 6, task 4 with task 5 and task 4 with task 6. Theses pairs of tasks have dependencies on the same variable, with at least one being a write, so the analysis is true. A data race is possible as implicit tasks may run concurrently. Task 3 and task 5 have both read dependencies on the same variable, hence no order is required. Hence no issue is raised for this pair.

We also applied the Archer and the Tasksanitizer tools on this example. Tasksanitizer correctly unveils a data race, whereas for Archer, the analysis being applied on the current execution scheduling, the data race is not detected on every run. Both tools, upon detection of a race condition, only retrieve a subset of possible cases/scheduling leading to the race condition. In our ad-hoc cases, Tasksanitizer did find many false positives, mainly arising from poorly support of taskwait and dependencies in nested tasks with dependencies context. Study of overhead. We evaluated our tool overhead on the Fibonacci and the Strassen benchmarks. The tests were conducted on an Intel XEON node with 28 physical cores and 186GB of memory ram. In our results, we illustrate the slowdown factor (i.e. execution time with a tool divided by the time of the standard version of the code) for different tools: Archer, our tool with both online and post-mortem analysis. Tasksanitizer exhibited very high overhead for Fibonnacci (from one hundred to several thousands) and was segfaulting on Strassen, hence its results are not displayed.

Archer is more complete and performs more analyses than our tool. We use this time as an upper bound overhead to not overcome.

The evaluation of the modified Fibonacci was conduct on the Fibonacci values f ib(x), where x ∈ {4, 13, 23, 30}, representing respectively the creation of 12, 1128, 139101 and 4038804 tasks at runtime (see Figure 3). For a small number of tasks, the online version is efficient, whereas the trace-based version is slower than Archer. This is due to our tracing mechanism which is very basic (no I/O delegation or asynchronism), and the cost of waiting to write the trace is too high regarding the benchmark execution time. For a large number of tasks the online version spends to much time checking each pair of tasks, and has prohibitive overhead. On the other hand, tracing becomes very competitive. The evaluation of the Strassen benchmark was conducted on square matrices with power of two sizes from 512 to 8192. Two cutoffs were set for the switching value to regular method and for the max depth, controlling the task nesting up to four levels. On Strassen (Figure 4), overheads of both online and trace-based methods are lower than Archer. The slowdown is up to 7.7 for online resolution and a maximum of 4.6 for trace generation. With online resolution, only size 4096 provides high overheads. Further investigation is needed to understand these results.

Conclusion

Since version 4.0, the OpenMP standard includes the notion of data dependencies between tasks created by the same parent (either another task or a thread). But combining nested tasks with data dependencies may lead to race conditions, some uncovering unexpressed/hidden dependencies. This paper proposed an algorithm to detect such problems based on the depend clauses exposed by the programmer. We implemented this method in a tool providing both dynamic and post mortem approaches, based on the recently released OMPT interface and our extensions for data sharing attributes. We demonstrated that this method can effectively detect race conditions with a reasonable slowdown compared to existing tools. The proposed OMPT extension for data sharing attributes can be useful for any tools relying on addresses passed in clauses. For future work, we plan to study a restricted use of code instrumentation to detect data accesses inside OpenMP tasks, and then be able to detect any data races between depend clauses and actual variable accesses.

  main ( void ) v a r i a b l e a , b ; #pragma omp p a r a l l e l { #pragma omp s i n g l e { #pragma omp t a s k depend ( i n : a ) { #pragma omp t a s k depend ( i n o u t : a ) {} #pragma omp t a s k depend ( i n o u t : a ) {} } #pragma omp t a s k depend ( o u t : a ) { #pragma omp t a s k depend ( i n o u t : a ) {} #pragma omp t a s k depend ( i n o u t : a ) {} } } } Listing (1.1) Nested tasks with dependencies (a) Single spawn-subtree

Algorithm 1 : 4 DoDectectionConf licts = true 5 for v ∈ root.children {v} do 6 if 7 Synched = CheckSynch(v) 8 if Synched = true then 9 DoDectectionConf licts = f alse 10 if

 145678910 Resolve Non Sibling Dependencies 1 ResolveNonSiblingDependencies inputs: vertex root of the spawn-tree 2 if root.children = ∅ then 3 for v ∈ root.children do DependencyPath(v, v ) = true then DoDectectionConf licts = true then 11 for w ∈ subtree(v)∪v do 12 for w ∈ subtree(v )∪v do 13 DetectConflicts(w, w ) 14 ResolveNonSiblingDependencies(v)

  (a) Spawn-tree instance of fibonacci(4) (b) DAG generated from the dependency domain formed by the leaf tasks in subtree B.

Fig. 2 :

 2 Fig. 2: Data structures related to the task-based Fibonacci example

  typedef s t r u c t o m p t d e p e n d e n c e s o m p t d a t a t v a r i a b l e ; o m p t d e p e n d e n c e t y p e t d e p e n d e n c e t y p e ; i n t a d d r e s s l o c a t i o n ; ) o m p t d e p e n d e n c e t ; Listing 1.7: Extension to ompt task dependence t

Fig. 3 :

 3 Fig. 3: Overhead for multiple fibonacci values and number of threads.

Fig. 4 :

 4 Fig. 4: Overhead for multiple Strassen matrix sizes and number of threads.

Acknowledgments: This work was performed under the Exascale Computing Research collaboration, with the support of CEA, Intel and UVSQ.