Bassem Ben

Halima -Mohamed Ali

Ben Halima
email: bbenhalima@gate.cnrs.fr.

Ben Bassem

Halima

Mohamed Ali

Time Preferences and Job Search: Evidence from France

Keywords: Time preference, Hyperbolic discounting, job search. Classification JEL : D90, J64, C41 ____________

Increasing impatience reduces search efforts of unemployed job seekers and therefore decreases the exit rate from unemployment. Also, impatience reduces reservation wage and increases the exit rate. To determine the overall effect of impatience on the exit rate from unemployment, we distinguish between exponential and hyperbolic time preferences. Search effort dominates the reservation wage and decreases the exit rate from unemployment if individuals have hyperbolic, rather than exponential, preferences. Using the French sample of the European Household Panel Survey, we found that search effort has a strong effect on the duration of unemployment, whereas the reservation wage is not significant. This result shows that the job seekers have hyperbolic preferences. Hyperbolic preferences affect problems associated with job search and policies aimed at reducing unemployment.

Introduction

Sequential models of job search make it possible to make predictions about the equilibrium of the influence of observable and unobservable individual characteristics on the exit rate from unemployment. In this literature, time preference is a significant factor, because it defines the level of the reservation wage as well as the intensity of the job search. We are interested in the observation, reported in many studies, of a great acceleration of the exit rate from unemployment near the completion date of unemployment benefits. This phenomenon may be taken an indication that unemployed workers have modified the conditions of their intertemporal trade-offs. However, in the literature on the modelling of time preference [START_REF] Gary | The endogenous determination of time preference[END_REF][START_REF] Harris | Dynamic Choices of Hyperbolic Consumers[END_REF], the effect of impatience on job seeking has attracted little attention in recent years, even though it is closely related to the theory of job search.

The investigation of the influence of time discounting on the equilibrium properties of models of job search, which view search effort as endogenous [START_REF] Mortensen | Job Search and Labor Market Analysis[END_REF], generally does not reveal a determinate effect on the exit rate from unemployment. On the one hand, increased time discounting (impatience) 1 leads an unemployed worker to attach little importance to the advantages of job search. Thus, the unemployed worker exerts little effort on job search. This behaviour tends to result in fewer job offers being received and to increase the duration of unemployment. On the other hand, increased time discounting also leads to a lower reservation wage and hence shortens the duration of unemployment. Impatient unemployed worker prefers to accept an offer of employment immediately, rather than wait for an additional period to receive a better offer. This effect tends to reduce the duration of unemployment and it is opposed to the effect of a fall of the intensity of search. This standard result, often cited in the specific literature, is due to the relatively simple modelling of the time consistency that is retained in the majority of the models. At the same time, an increasing number of researchers have been interested in testing the time consistency of agents, generally by conducting experiments in the laboratory, starting from exponential or hyperbolic discounting function [START_REF] Laibson | Golden Eggs and Hyperbolic Discounting[END_REF][START_REF] O"donoghue | Doing it Now or Later[END_REF][START_REF] Cox | Regression models and life tables[END_REF]Oaxaca, 1989, 1992).

The Discounted Utility (DU) model [START_REF] Samuelson | A note on measurement of utility[END_REF], which is often used by economists, has received a modicum of support from empirical research. Empirical research on intertemporal choice has revealed that the DU model is inadequate as a descriptive model of behaviour in a number of respects. This model shows that an individual who has intertemporal preferences represented by an exponential discounting function makes consistent choices and that his preferences are never reversed, which implies a constant discount rate through time. However, the studies of [START_REF] Pender | Discount rates and credit markets: Theory and evidence from rural India[END_REF] and [START_REF] Chapman | Temporal discounting and utility for health and money[END_REF] show that discount rates are not constant over time, but appear to decline. This pattern often referred to as hyperbolic discounting. The term "hyperbolic discounting" is often used to denote a decrease in impatience over time, with a high discount rate in the short run and a low one in the long run. The existence of this phenomenon has been confirmed by the studies of [START_REF] Myerson | Discounting of delayed rewards : Models of individual choice[END_REF] and [START_REF] Kirby | Bidding on the future: Evidence against normative discounting of delayed rewards[END_REF] 2 . The hyperbolic discounting function contradicts the assumption of the time consistency of preferences [START_REF] Fang | Measuring Time Inconsistency: Evidence from Work-Welfare Decisions in the NLSY[END_REF] and supports the decrease of impatience over time.

Hyperbolic time preferences have enormous implications for labour market policies.

Hyperbolic worker is particularly sensitive to the immediate costs of the job search and seeks to reap the benefits of search quickly by accepting a job offer in the near future.

Consequently, job-search programmes can help hyperbolic workers by finding a way to reduce the short-term costs of job search. It may also be possible to use interactive kiosks, where potential job applicants can submit their curriculum vitae and also schedule an interview at low cost to themselves. The interactive kiosks could coordinate between the various actors who help the applicant to gain employment. If costs represent a barrier for the search of hyperbolic job seekers, the availability of such interactive kiosks will encourage them to keep looking. This paper reports on an empirical study of the effects of impatience on job search outcomes. The originality of this paper is to compare our results obtained from the French data with the results of Della- [START_REF] Vigna | Job Search and Impatience[END_REF] on U.S. data. More impatient workers search less intensively and set a lower reservation wage. The effect of these tactics on the exit rate from unemployment is unclear. In their study, Della [START_REF] Vigna | Job Search and Impatience[END_REF] distinguish between different types of time preference: exponential and hyperbolic. They also distinguish between short-run and long-run impatience. The search decision involves a tradeoff between immediate search costs and the future benefits of accepting an offer made within a few weeks. Over this limited time frame, variation in short-run impatience matters more than variation in long-run impatience. In contrast, the decision concerning the reservation wage involves comparing the long-term consequences of obtaining a certain wage or waiting to receive an even better offer. In this case, variation in long-term discounting is more significant than variation in short-term discounting. According to the exponential discounting model, job seekers are concerned more with long-run impatience than short-run impatience.

In this case, the effect of the reservation wage will dominate the level of the search effort, because the decision on the reservation wage depends only on long-run impatience.

Accordingly, job seekers who become more impatient tend to exit from unemployment more quickly, because they lower their reservation wage. On the other hand, according to the hyperbolic discounting model, job seekers are more prone to be impatient in the short run than in the long run. In this case, the effect of the search effort will dominate the level of the reservation wage, because the search decision depends only on short-run impatience.

Therefore, job seekers who become more impatient tend to exit from unemployment more slowly, because they expend less effort on search.

Using the French sample of the European Household Panel Survey, we test these theoretical predictions empirically. We find that various measures of impatience are correlated negatively with search effort and the reservation wage. This result shows that when job seekers become more impatient, they tend to expend less effort on search and to lower the reservation wage. We also show that search effort has a strong effect on the exit rate from unemployment, whereas the effect of reservation wage is not significant. This result shows that individuals have hyperbolic preferences. Consequently, when they become more impatient, they exit from unemployment more slowly because they reduce the amount of effort on job search.

The remainder of the paper is organized as follows. Section 2 outlines the various assumptions made by the model of Della [START_REF] Vigna | Job Search and Impatience[END_REF]. In Section 3, we provide a descriptive analysis of the data, the choice of the impatience measures, and a nonparametric analysis of the effects of these measures on survival function in unemployment. In Section 4, we demonstrate the estimation and principal results. Section 5 concludes by summarizing the main results.

The search model of Della Vigna and Paserman (2005)

We now examine the various assumptions made by the model of Della [START_REF] Vigna | Job Search and Impatience[END_REF] 3 . In their model, search effort is endogenous 4 and determines the probability of receiving a wage offer in any period. Hence, the job seeker expends search effort s, parameterized as the probability of obtaining a job offer. Therefore, . The job offer is characterized by a wage w . The structure of time preferences of [START_REF] Laibson | Golden Eggs and Hyperbolic Discounting[END_REF], [START_REF] Strotz | Myopia and inconsistency in dynamic utility maximization[END_REF], [START_REF] Phelps | On Second-Best National Saving and Game-Equilibrium Growth[END_REF], is used as a simplification of hyperbolic time preferences. Let

) ( t c u
denote the stream of per period utility that is derived from consumption. The present value of a flow of future utilities at time t is

t T t t u u    1 0   . ) 1 , 0 (  
is a parameter that reflects short-run patience and  is the discount factor that captures long-run patience. When 1   , the rate of time preferences is constant and preferences are time-consistent, which is the standard exponential discounting case. When The job seeker chooses a level of search effort and a wage acceptance policy to solve the optimisation programme:

            U t t U t E t F t t s V s V w V E s s c b t 1 1 1 ] 1 , 0 [ 1 , max max          [1]
where :

b is the benefits of unemployment,   :  is long-run patience, :

t s is the probability of receiving an employment offer in period t ,   :

1 w V E t 
is the continuation payoff of employment if the job seeker accepts a wage offer, and

: 1 V U t 
is the continuation payoff of unemployment if the job seeker rejects a wage offer or does not receive a wage offer.

Let us now study the various assumptions that can be derived from the resolution of this model. These assumptions are used to determine the nature of the correlation between impatience and the search effort, between impatience and the reservation wage, and between impatience and the exit rate from unemployment. These assumptions will be tested empirically using French data from the European Household Panel Survey.

-Hypothesis 1. At equilibrium, there is a negative correlation between impatience and the search effort. Search effort is strictly decreasing with short-run impatience -Hypothesis 3. The exit rate from unemployment is strictly decreasing with short-run impatience for naive job seekers. For sophisticated job seekers, the exit rate is also strictly decreasing with short-run impatience if

      1 1 ] / [ x x W W E at * w x  [2]
Given that short-run impatience affects the search effort directly, increasing     1 tends to decrease the exit rate from unemployment through the decrease in search effort.

-Hypothesis 4. Taking into account that there is a probability that a job seeker who finds work will be laid off, the exit rate from unemployment is increasing with long-run

impatience     1 if  is quite high (close

Data and non-parametric analysis

The data used comes from the French sample of the European Household Panel Survey conducted by Eurostat, and covers eight waves of study from 1994 to 2001 (Table 1). This longitudinal survey can be used to trace the history of job seekers on the labour market retrospectively. It provides complete information on the characteristics of individual job seekers and household structures. We now explain our choice of impatience measures. In the past, time preferences were often measured by experimental studies, in which people are asked to evaluate stylized intertemporal prospects that involve choice tasks 8 [START_REF] Cox | Regression models and life tables[END_REF]Oaxaca 1989, 1990). Impatient individuals prefer to receive immediate rewards and to avoid immediate costs in a way that our "long-run selves" do not appreciate (O"Donoghue and Rabin, 1999). Conversely, patient individuals prefer activities that have immediate costs and delayed benefits. Does behaviour that privileges a present or shorter-term solution constitute proof that people have a preference for the present (impatience) or that they simply have an aversion to risk? It may prove difficult to differentiate between impatience and risk aversion completely, because the correlation between these two factors cannot be denied. Individuals who are strongly riskaverse are also very impatient [START_REF] Anderhub | On the Interaction of Risk and Time Preferences: An Experimental Study[END_REF]. We collected information on the French data of the European Household Panel Survey in order to construct measures of impatience. Three assumptions were used in our empirical study: (i) impatience measures do not distinguish between short-run and long-run impatience; (ii) the discount rate does not change between the activities; and (iii) the level of impatience does not vary over time. Our measures may be imperfect proxies for impatience and they may pick out a number of other individual traits (e.g., tastes for leisure, or risk preferences) in addition to time preferences.

An explanation of why individuals prefer to consume today rather than tomorrow must appeal to a more specific phenomenon, one"s psychological nature. To improve the quality of our study, we attempted to control for these various factors in our choice of impatience measures.

The proxies that we selected are as follows:

Having a bank account: A simple model of saving behaviour predicts that individuals who are more patient delay consumption and accumulate more wealth. Therefore, they are more likely to have some type of bank account. 51.15% of individuals in the sample had a bank account.

Contribution to humanitarian associations: This type of behaviour characterizes patient individuals. Contributing to associations for the benefit of society, rather than for personal gain, indicates patience. This type of individual has long-term vision and seeks to prepare better conditions for future generations. Individuals who do not contribute to humanitarian associations are strongly represented in the sample (76%).

Smoking 9 : This activity is pleasurable at the time of consumption but detrimental to health in the long term. An impatient individual (smoker) will be satisfied with the short-term benefit without assigning importance to the long-term disadvantage. Daily smokers represent 21.45% of the sample.

Consuming one's income and incurring debt:

Having difficulty in keeping to one"s budget and incurring debt due to consumption can be related to impatience. An impatient person thinks less at the moment of purchase, and exposes him-or herself to exceeding the limits of his or her budget. Such individuals represent only 7% of the sample.

Life insurance:

The individuals who subscribe to a life insurance policy have a preference for the long term and show a weak preference for the present. Individuals who do not have life insurance represent 65% of the sample.

In order to homogenize impatience measures, we transformed them into reduced centred values. This process of standardizing data has the advantage of homogenizing data without changing the results of various statistical analyses. The analysis of correlation between the impatience measures shows that among 10 pairwise correlations, nine have a positive sign and are statistically different from zero (Table 2). To measure the quality of the measure, we used Cronbach"s alpha coefficient. A statistical index varies between 0 and 1, which is used to evaluate the homogeneity or consistency of an instrument. The value of Cronbach"s alpha coefficient was 0.536, which reflects an average correlation between the measures of 0.06. Both measures are very similar to those of [START_REF] Drago | Career Consequences of Hyperbolic Time Preferences[END_REF] and Della [START_REF] Vigna | Job Search and Impatience[END_REF] 10 . We determined an aggregate measure of impatience with factor analysis by using the five standardized proxies describe above. Factor analysis aims at reducing a significant amount of information to a few large dimensions. It is a statistical method that is used to describe variability among observed variables (

, ... , 2 , 1 ( ... 2 1 2 1 N n Y u F a F a F a X n n Q n n n p Q       [3]
We estimated a factor model via maximum likelihood [START_REF] Harman | Modern factor analysis[END_REF], ch.10) using the measures of impatience. The results are presented in Table 3. We retained only one factor. For this factor, all factor loadings have positive signs. Our conjecture was that this factor is impatience. The score coefficient was used to create the aggregate measure of impatience, which is a weighted average of the individual variables. The measures that received the most weight are consuming one"s income and incurring debt, and life insurance.

Given that the data set does not contain information on search intensity per se, we used the following search methods used by the job seeker to define a measure of search intensity:

(1) registration at the public employment agency, (2) personal steps taken to find a job (searching through newspapers, word of mouth from friends and relatives, direct contact with possible employers, etc.), and (3) contact with the public employment agency and following a programme of individual support. The average number of methods used by each unemployed person is 2.36.

The reservation wage is defined as the minimum wage below which an unemployed person refuses a job offer. The reservation wage is an important determinant of the probability that an unemployed person will exit unemployment. Nevertheless, direct information about the reservation wage is scarce 11 . However, having the reservation wage determined by the unemployed person him-or herself opens other possibilities. The way in which the French data of the European Household Panel Survey is collected includes asking the unemployed about the minimum hourly wage for which they would go to work. The unemployed are asked initially about the number of hours that they would like to work per week, then about the minimum wages that they would accept for the number of hours that they have just declared.

The direct use of the answers to these questions raises difficulties about the sincerity of the statements [START_REF] Feldstein | Unemployment Insurance and Reservation Wage[END_REF]. However, a majority of previous studies have agreed to consider this type of response as relevant information on the behaviour of labour supply [START_REF] Ridder | Unemployment Benefits and Search Behaviour: an Empirical Investigation[END_REF][START_REF] Jones | The Relationship between Unemployment Spells and Reservation Wages as a Test of Search Theory[END_REF]. Indeed, the distribution of the reservation wage seems to be consistent with the mean and variance observed in wages in France (Table 1). To supplement the descriptive analysis of the sample, survival rates in unemployment were estimated by means of a Kaplan-Meier estimation (Figure 1).

Figure 1. Kaplan-Meier estimator of the survival function in unemployment

The aggregate impatience measure is continuous variable. We distinguished between job seekers with low impatience, characterized as unemployed patient (1st quartile), and job seekers with high impatience, characterized as unemployed impatient (bottom quartile). The results of this estimation enable us to compare the survival function in unemployment between patient (impatience =0) and impatient job seekers (impatience =1). We show that the survival curve for a patient job seeker is below that of an impatient job seeker. The non-parametric estimation (Kaplan-Meier) gives us an idea of the effect of impatience on survival function in unemployment: patient job seekers stay less in unemployment than impatient.

Estimation

At each period, the job seeker chooses his search effort and his reservation wages. These two variables determine the probability of exiting unemployment. As we saw in the theoretical model of Della [START_REF] Vigna | Job Search and Impatience[END_REF], there is a correlation between job seekers" impatience and (a) their search effort, and (b) their reservation wages. The global effect of impatience on the exit rate from unemployment is unclear. The estimation results will enable us to determine the nature of the correlation between impatience and search effort, impatience and reservation wages, and impatience and exit rate from unemployment.

Impatience and search effort

We now determine the nature of the correlation between impatience and search intensity.

The equation for search effort is as follows: (columns 1 and 2, for the impatience measures and the aggregate impatience measure, respectively).

i i i IMP Intensity         ) ( X ' 1 i ' 1 1 [4]
Not having a bank account, not having life insurance, and smoking have a significant and negative effect on search effort. Most of the impatience measures show a strong negative correlation between impatience and search effort. This result is confirmed by the second estimation using the aggregate impatience measure. These results confirm theoretical predictions; there is a negative correlation between impatience and search effort. The US data used by Della [START_REF] Vigna | Job Search and Impatience[END_REF] shows that search effort is correlated negatively with impatience. For the other explanatory variables, age has a significant negative effect on search effort. Men tend to expend more effort on search than women. Receiving unemployment benefit has a significant and negative effect on search effort. Compensated individuals expend less effort on search than those who are not.

Impatience and reservation wage

The determination of the reservation wage requires comparing the long-term consequences of obtaining a certain wage with the wait to receive a better offer. In this case, contrary to the decision on the level of search effort, the variation of long-run impatience dominates the variation of short-run impatience. The equation for the reservation wage is as follows:

i i i IMP W Log         ) ( X ) ( ' 2 i ' 2 2 , [5]
where

) ( i W Log
is the log of reservation wage, i X is the vector of explanatory variables, and i IMP is the impatience measures. Using the Ordinary Least Square method (OLS), we determine, on the one hand, the effect of impatience on the reservation wage and, on the other hand, the effect of other variables on the reservation wage.

The results of this estimation (Table 4, columns 3 and 4) help to test the correlation between impatience and the reservation wage 13 . The first estimate (column 3) uses the impatience measures, while the second estimate (column 4) uses the aggregate impatience measure. Not having a bank account, not having life insurance, or not subscribing to humanitarian associations has a significant and negative effect on the reservation wage. Most of the impatience measures show a strong negative correlation between impatience and the reservation wage. This result is confirmed by the sign and the significance of the coefficient of the aggregate impatience measure (column 4). This confirms previous results and shows that workers who are more impatient set a lower reservation wage. We can now confirm the theoretical predictions; there is a negative correlation between impatience and the reservation wage. Data from the US used by Della [START_REF] Vigna | Job Search and Impatience[END_REF], in an analysis that does not include the control variables (age, education, marital status, etc.), shows that the reservation wage is correlated negatively with impatience. This correlation was not significant after including the control variables. Our result is different and could be due to the possibility that the measures of impatience are reflecting other dimensions of unobserved heterogeneity (for example, heterogeneity in human capital).

The income per household member and age, independently, had a significant and positive effect on the reservation wage. The effect on the reservation wage increases as the age of the individual increases. Men specify a higher reservation wage than women. When they are married, both men and women lower their reservation wage. It is also noted that the reservation wage grows steadily with the level of education. Individuals who had higher education specified a higher reservation wage than individuals with a lower standard of education (taken as a reference). Individuals who live in rural areas or cities that have fewer than 100,000 inhabitants tend to specify a lower reservation wage than those who live in the Paris region.

Search effort, reservation wage, and exit rate from unemployment

To determine the nature of the correlation between (a) search effort and the exit rate from unemployment, and (b) between reservation wage and the exit rate, a semi-parametric Cox proportional hazard model was used [START_REF] Cox | Regression models and life tables[END_REF]. This type of model allows all the standard determinants to be controlled for. It also allows duration dependence, which is the pure effect of the duration of unemployment on the probability of moving to employment, to be controlled for. The hazard model utilizes data on the sequence, timing, and the state that an individual is in; the probability of the type of exit is a function of time. This is referred to as the hazard rate or function. The hazard rate is the dependent variable, and the relationship between this rate and a variety of observed and unobserved variables is modelled. The hazard model has been widely used in biomedical and social science research, by [START_REF] Cox | Regression models and life tables[END_REF], Kalbfleish and Prentice (1980), and [START_REF] Heckman | A Method of Minimizing the Distributional Impact in Econometric Models for Duration Data[END_REF]. As before, let Ti be a nonnegative random variable that denoted the duration of unemployment for individual i. We now define   t h i , the hazard at time t for individual i, as follows:

    t t T t t T t t h i i t i          / Pr lim 0 [6]
Thus, this equation gives the probability that a job seeker will exit from unemployment between t and t t   , under the condition that the job seeker had not already died by time t.

In order to estimate the exit rate from unemployment and the effects of independent variables on this, we need to specify the functional form of the hazard model. The most widely used specifications are the accelerated time model and the Cox proportional hazard model.

According to the Cox proportional hazard model [START_REF] Cox | Regression models and life tables[END_REF], covariates have a multiplicative relationship with the hazard function (the proportionality assumption), which causes them to shift the hazard function up or downward. Therefore, covariates do not affect the duration of an activity directly 14 . Given that we are studying the effect of explanatory variables on the exit from unemployment, a Cox proportional hazard model is used. It is specified by

     i i i x t h X t h   exp ) ( 0 [7] where i t is the elapsed duration of unemployment for individual i;   X t h i /
denotes the hazard rate conditional on a vector of covariates X; The results of the determinants of the exit rate of unemployment are given in Table 4 (column 5 and 6). The first estimate (column 5) presents the correlation between the reservation wage and the exit rate, while the second estimate (column 6) identifies the correlation between search effort and the exit rate, using a Cox proportional hazard model.

The search effort has a significant effect on the exit rate from unemployment. Individuals who expend more search effort exit from unemployment after a shorter time (Result 1). The reservation wage does not have a significant effect on the exit rate from unemployment (Result 2). Taken together, Results 1 and 2 show us that the effect of the search effort dominates the effect of the reservation wage: this implies that individuals who are more impatient expend less effort on search and so may exit from unemployment more slowly.

Given that the effect of search effort dominates the level of reservation wage, we may conclude that the job seekers in our sample exhibit hyperbolic, rather than exponential, preferences. This last result shows that job seekers are more concerned by short-term impatience rather than by long-term impatience. Given this result, job-search programmes should reduce the short-term costs of research, which are immediately supported. Job seekers who belong to age group 2 [25-35 years] and group 5 [55; +] remain unemployed for longer than job seekers who belong to age group 1 [<25 years] (taken as a reference). The probability of men exiting unemployment is higher than that of women. We also note that job seekers who are married exit unemployment more slowly. Job seekers who have a university degree exit unemployment more quickly than individuals who are uneducated (taken as a reference).

Job seekers who live in areas with a population of 20,000 to 100,000 are unemployed for shorter periods than those who live in the Paris region.

Conclusion

This paper contributes to the literature on hyperbolic discounting. A second contribution of this paper is to compare our results on French data with the results of Della Vigna and Paserman on U.S. data. This comparison gave us an idea about the time preferences type of unemployed in both countries and policies that can be applied to reduce unemployment. Within a model that views search effort as endogenous, increasing impatience implies a reduction in search efforts and therefore reduces the exit rate from unemployment. At the same time, impatience increases the reservation wage and it reduces the exit rate from unemployment. The overall effect of impatience on the exit rate is unclear and requires a comparison of the relative strengths of effects. The effect of search effort dominates the reservation wage if job seekers have hyperbolic preferences, while the reservation wage dominates search effort if job seekers have exponential preferences. Put differently, the exit rate increases if the job seekers have hyperbolic preferences and decreases if they have exponential preferences. In the empirical test, we found that impatience measures are correlated negatively with the reservation wage and search effort. The results of the Cox proportional hazard model show that search effort has a positive effect on the exit rate from unemployment, whereas the reservation wage does not have a significant effect. This final result informs us about the nature of job seekers" time preferences. Given that the effect of search effort dominates the effect of reservation wages, we may conclude that the job seekers exhibit hyperbolic, rather than exponential discount.

The effectiveness of policies whose objective is to reduce unemployment depends on the nature of the time preferences of the unemployed. Hyperbolic preferences affect problems associated with job search and policies aimed at reducing unemployment. Hyperbolic agents are particularly sensitive to the immediate costs of job search (including contacting employers to obtain an interview, calling relatives, etc.). To reduce the immediate costs of the search to the job seeker, public employment services in France should follow up the unemployed more efficiently so that they may obtain information that will help them to reduce the costs of job search. France is exceptional because there are many heterogeneous actors and authorities of different status, which the job seeker must consult several times to stay informed. The creation of "houses of employment" could provide an opportunity to establish some basic principles for active policies to allow fluidity between unemployment and reemployment. This can be achieved by the effective reduction of the costs borne by the unemployed.

Interactive kiosks could also be set up, where job seekers can submit their curriculum vitae and schedule interviews at low cost. This administrative simplification for job seekers is now available in nearly all Western countries. However, such simplification is exceptionally slow in France. Note. Standard errors in parentheses, *: significant at the 0.1 level, **: significant at the 0.5 level, ***: significant at the 0.01 level.

Notes 1 An individual with high time discounting is assumed to be impatient, while an individual with low time discounting is assumed to be patient. 2 This inconsistency is presented by the following situation. When confronted with the choice between two payments that are close in time, for example, $10 today or $11 tomorrow, many agents prefer $10 today and thus demonstrate a remarkably high discount rate. However, given a longer time scale, most agents choose to take $11 in 101 days instead of $10 in 100 days, even though the period between the payments is still just one day. 3 For more details, see Della [START_REF] Vigna | Job Search and Impatience[END_REF] pp. 531-544. 4 It is common in the literature to view search effort as endogenous (Burdett and Mortensen, 1978; Mortensen 1986; Albrecht, Holmlund, and Lang 1991) 5 Quasi-hyperbolic discounting is an approximation of hyperbolic time preferences (Phelps and Pollack, 1968;[START_REF] Laibson | Golden Eggs and Hyperbolic Discounting[END_REF]. Such preferences imply a lower discount factor when the delay horizon is short (short-run impatience) than when the delay horizon is long (long-run impatience) and generate problems of self-control and time-inconsistency in a simple fashion. 6 Many empirical regularities regarding consumption [START_REF] Angeletos | The Hyperbolic Consumption Model: Calibration, Simulation, and Empirical Evaluation[END_REF][START_REF] Laibson | Golden Eggs and Hyperbolic Discounting[END_REF], drug addiction [START_REF] Gruber | Is Addition "Rational"? Theory and Evidence[END_REF], and unemployed worker behaviour [START_REF] Paserman | Job Search and Hyperbolic Discounting: Structural Estimation and Policy Evaluation[END_REF], among others, are explained better in terms of quasi-hyperbolic preferences than in terms of time-consistent preferences. 7 For more details, see Della [START_REF] Vigna | Job Search and Impatience[END_REF] pp.538-540 8 Respondents" answers to the question "Which would you prefer: $100 today or $150 one year from today? 9 An individual was treated as a smoker if he declared himself to be a daily smoker and not a casual smoker. 10 Glaeser, Laibson, Scheinkman and Soutter (2000) show that there is a low correlation between measures of an individual trait. The correlation can be reduced by a measurement error in the choice of impatience measures, but this should not alter the sign. 11 There is little empirical data to confirm or disconfirm this theoretical concept. In the absence of direct observation, study that seeks to evaluate the effect of the reservation wage on the duration of unemployment supposes that the relation, predicted by the theory of job search, which relates it to the level of the unemployment benefits, the arrival rate of offers, and the distribution of the wages offered, is well checked. The reservation wage can then be estimated by using information available on these variables. 12 We estimated the equation of search effort using the binomial negative model. According to the coefficient of sur-dispersion (alpha), we retain the Poisson model. 13 We use the same list of the variables used in the estimation in the equation for search effort. 14 In contrast, the accelerated time model (Cox and Oakes, 1984) assumes that covariates act multiplicatively on time rather than on the hazard function. Covariates, therefore, increase or decrease the time spent on an activity.

  of receiving a job offer during a sequence of searches is an increasing function of the intensity of search effort, but an increase in the search effort also augments the cost of the search. In each period, the job seeker incurs a cost of searching  

.

  are quasi-hyperbolic 5 . The discount factor between the current period t and the next one1  tis  , while the discount factor between any two periods in the future is  . With the structure of quasi-hyperbolic discounting, In the current period t , a reward of 10 that starts to materialize in time preferences involve problems of self control 6 . Following O"Donoghue and Rabin (1999), we distinguish between sophisticated and naive individuals, where the former are aware of their self-control problems and the latter are not. A naive hyperbolic individual believes incorrectly that in the future she will behave as an exponential individual with 1   . Sophisticated individuals predict the behaviour of their future selves perfectly.

-

  Hypothesis 2. For exponential and hyperbolic agent, the reservation wage is strictly decreasing with long-run impatience

  to 1) and for plausible values of the layoff probability7 . Given that long-run impatience affects the reservation wage directly, the exit rate from unemployment through the decrease in the reservation wage.The main objective of the empirical study reported in this paper is to test the predictions of this model using French longitudinal data. The results of this empirical part will help us to identify the nature of the time preferences of the job seekers in the sample and to remove the uncertainty of the effect of impatience on exit rate from unemployment. If job seekers the exit rate from unemployment. Knowing the type of time preferences that job seekers have can help to guide the formulation of labour market policies to reduce unemployment.

  fewer unobserved variables called factors. The observed variables are modelled as linear combinations of a set of common factors (

)

  , i X is the vector of explanatory variables, and i IMP is impatience measures. The econometric model that best fits this situation is the Poisson model as the dependent variable; the number of search methods is a non-negative integer 12 . For this estimation, we use socio-demographic variables: level of education, number of inhabitants in the region, household income per person, the reception of unemployment benefits, and impatience measures. For the search effort equation (4), we conduct two separate estimates. In the first estimation, we use impatience measures and in the second we use the aggregate impatience measure. Both estimates allow us to compare the results of the effect of impatience. The estimation results of the equation of search effort are reported in Table4

  of the time that has passed since becoming unemployed on the probability of moving to another state; and  i x denotes the covariates and parameter estimates for the exit rate.

Table 1 .

 1 Descriptive Statistics Job seekers who received unemployment benefits represent 65% of the sample. Women accounted for 54% of the sample. The average age for the whole sample is 34 years. While the share of graduates from higher education is close to 20%, there is still a higher proportion of graduates from short-term technical education, such as the Certificate of Professional Aptitude or the Diploma of Professional Studies. The average hourly reservation wage is around 6.56 euros. Thirty-one percent of the sample live in a region with more than 100,000 inhabitants.

	Variables	Mean	Standard Errors	Observations
	Age
	Age	34.280	11.5328
	Class 1 [<25]	0.2693	0.4437
	Class 2 [25-35]	0.2915	0.4545
	Class 3 [35-45]	0.2008	0.4007
	Class 4 [45-55]	0.1864	0.3895
	Class 5 [55 +]	0.0518	0.2217
	Gender
	Men	0.4595	0.4984
	Marital Status
	Married	0.3937	0.4887
	Skill Level
	No education	0.1170	0.3215
	General education	0.1591	0.3659
	Short Technical education	0.3012	0.4589
	Long Technical education	0.0814	0.2735
	University degree	0.1962	0.3972
	Region
	Rural Town	0.2697	0.4439
	< 20,000 inhabitants	0.1522	0.3593
	20,000-100,000 inhabitants	0.1485	0.3557
	> 100,000 inhabitants	0.3109	0.4629
	Paris	0.1184	0.3232
	Impatience measures
	No Bank account	0.4885	0.5000
	No Life insurance	0.6500	0.4771
	Smoking	0.2145	0.4106
	Consuming one"s income and incurring debt	0.0693	0.2541
	No Contribution to humanitarian associations	0.7659	0.4236
	Other variables
	Reservation wage	6.5598	2.6742
	Number of search methods	2.3678	0.7985
	Unemployed compensated (unemployment benefits)	0.6598	0.4738
	Log (income per household member)	8.0718	0.6204

The panel monitors, for each individual, the timing of unemployment spells in each wave.

It provides complete information on the characteristics of individual job seekers and household structures. The incidence of unemployment spells by individuals and by observation creates a sample of 2161 observations. The analysis of individual spells of unemployment shows 68.84% complete spells. The number of individual spells of unemployment registered varies between one and 12; the average is 1.96 with the average length being 7.35 months.

Table 2 .

 2 Correlation of impatience measures

					Consuming one"s	No Contribution to
		No Bank account	No Life insurance	Smoking	income and incurring debt	humanitarian associations
	No Bank account	1.000
	No Life insurance	0.2032 (0.0000)	1.000
	Smoking	0.5853 (0.0000)	0.1677 (0.0000)	1.000
	Consuming one"s income and incurring debt	0.1450 (0.0000)	0.0849 (0.0001)	0.1060 (0.0000)	1.000
	No Contribution to humanitarian associations	0.1214 (0.0000)	0.0685 (0.0015)	0.0854 (0.0001)	0.0414 (0.0541)	1.000

Table 3 .

 3 Factor Analysis, Aggregate Measure of Impatience

	Impatience measures	Factor Loadings	Uniqueness	Score
	No Bank account	0.1461	0.9786	0.0906
	No Life insurance	0.4151	0.7757	0.1502
	Smoking	0.2060	0.9401	0.0920
	Consuming one"s income and incurring debt	0.1371	0.7179	0.3451
	No Contribution to humanitarian associations	0.1552	0.9425	0.1083

Appendix


François Broquedis
email: broquedi@labri.fr

Olivier Aumage
email: aumage@labri.fr

Brice Goglin
email: goglin@labri.fr

Samuel Thibault
email: thibault@labri.fr

Pierre-André Wacrenier

Raymond Namyst
email: namyst@labri.fr

Franc ¸ois Broquedis

Structuring the execution of OpenMP applications for multicore architectures

come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

Typical nowadays computer architectures are based on a non uniform memory access (NUMA) interconnect of processing units based on multicores and simultaneous multithreading technologies. They can be seen as nested sets of resources with varying degrees, tightness and complexity of relationships, from a general point of view. The nature of these relationships being the sharing (or not) of some memory bank, cache, or even internal processing circuitry in the case of SMT.

Sharing has potentials for efficiency as a source of rationalization, but the other side of the coin is that sharing also has potentials for inefficiency as well, as a source of contention. Exploiting these machines efficiently is therefore a real challenge and dilemmas come when trying to take into account the memory hierarchy and the CPU utilization simultaneously. On NUMA machines for instance, threads should generally be scheduled as close to their data as possible, but bandwidth-consuming threads should rather be distributed over different chips.

As a consequence of their hierarchical nature, nowadays architectures feature numerous degrees of freedom. The layout, the number and the respective size of the nested sets of resources may considerably differ from one machine to another one. Therefore, the efficient programming of multicore and NUMA architectures requires an in-depth knowledge of both the target computer architecture and the application behavior like data sharing, synchronizations, memory access patterns, affinity and inter-thread relationship. As a consequence, the programmer should be given means to hint and guide the execution of his application. Nevertheless, even if experienced programmers are able to develop efficient applications for a specific hardware configuration, most of them rely on the operating system to get performance out of their parallel programs. Thus, the application programmer should be able to decide how much effort he wants to invest in his application parallelization process, and how much control he is willing to leave to the operating system. However, while the core scheduler of operating systems can often be influenced, it misses the ability to get accurate information about application behavior: for instance, adaptively-refined meshes entail very irregular and unpredictable behavior. This is why we claim that we can only reach the portability of performance by letting the runtime system be in charge of controlling thread scheduling and data placement layouts with the help of the application programmer. The runtime system can in turn cooperate with the operating system and gather hardware counters in the name of the application programmer, thus adapting the programmer requests to the current system state and the available resources.

The runtime system plays central role here. Its job is to adapt the execution of the application to the resources allocated by the operating system. Now, while the scheduling decisions should be left to the runtime, the whole software stack, from the application to the operating system, should be involved in the parallelizing and locality adaptation by providing useful information to the other components. In particular, it is important for the application to expose a structured view of its parallelism so that the runtime can later map it onto the allocated resources. For instance, in OpenMP frameworks, the information extracted by the compiler about memory affinity and adherence to the same parallel section can benefit in the guidance of task/thread scheduling. Such an information may also help in selecting a suitable memory bank location for pieces of data, or moving data to a new location to follow the evolution of the application state and behavior.

Our approach builds on these ideas to provide an OpenMP runtime system tightly integrated with a hardware-aware scheduler for structured execution of applications on nowadays hierarchical shared-memory computers. It combines the principles of a tree-like application parallelism structuring extracted with the help of the OpenMP compiler front-end and a tree-like modeling of the underlying architecture. It then dynamically maps the continuously evolving application parallelism tree onto the architecture tree, migrating threads and/or data when needed so as to maintain a good balancing of threads when events arise (task termination, new parallel sections, etc.).

This paper is organized as follows. Section 2 presents our FORESTGOMP OpenMP runtime system to exploit multicore and NUMA architectures through high level guided parallel execution. FORESTGOMP cooperates with our BUBBLESCHED programmable thread scheduling framework. Section 3 and Section 4 respectively introduce and evaluate the BUBBLESCHED policy we designed to schedule OpenMP programs onto multicore architectures and the complementary policy we designed for the NUMA case. Section 6 discusses relationships with other works from the community and Section 7 concludes the paper.

II. FORESTGOMP: A HIGH LEVEL WAY TO GUIDE PARALLEL EXECUTION

To fully tap into the potential of multicore machines, we have designed a platform for experimenting with and tuning scheduling policies of threads and tasks generated by OpenMP programs.

A. Rationale

Up to now, the OpenMP specification [START_REF]OpenMP: The OpenMP API specification for parallel programming[END_REF] has been built on the assumption that the underlying target architecture is a set of identical, independent computing units with a flat, isochronic shared memory space. For many years, this assumption was reasonable, but it is not anymore. Multicore and NUMA architectures break the assumption and offer new challenges to the application programmer that the OpenMP specification is not yet ready to take up.

Parallel programming approaches on such architectures have to deal with thread and data placement which OpenMP ignores. This is why the OpenMP ARB is currently discussing possible evolutions providing ways to group related threads together, place them according to their affinities, and distribute the data they access. These evolutions are promising but are mostly designed for the experienced programmers. The application programmer still has to make assumptions on parameters he cannot guess that directly depends on the underlying system state, like the amount of free memory or memory contention. This may lead to developing non-portable applications by defining the number of threads devoted to a parallel section and explicitly pinning threads onto the cores. Explicit binding and extended scheduling controls are desirable for advanced users to experiment with accurate low-level placement and understanding performance, but for the regular scientific application programmer there is a need for a more abstract, higher level approach.

The OpenMP specification was designed keeping in mind that the more accurate an OpenMP application is, the better performance it obtains. The OpenMP language implements this philosophy by providing high level clauses and keywords that help the programmer with parallelizing his application. For example, the user can define the minimal length of a chunk of the iteration space a parallel loop. Additional parameters and keywords helps the programmer defining the loop scheduling behavior or his parallelism grain.

Our approach extends the OpenMP philosophy of an incremental parallelization work from the application programmer. It advocates the idea that the programmer can help in the mapping of his application on the multicore or NUMA underlying architecture by progressively providing the runtime system with the additional information it needs to get a global view of thread and data relationship. The task of the runtime system is then to structure that parallelism to make an efficient use of hierarchical architectures.

B. The ForestGOMP runtime system

We developed the FORESTGOMP runtime to meet all these needs. FORESTGOMP is an extension of the GNU OpenMP library (LIBGOMP) that automatically structures the parallelism of OpenMP applications relying on the BUBBLESCHED platform. BUBBLESCHED provides a way to group related threads together into structures called Bubbles [START_REF] Thibault | Building Portable Thread Schedulers for Hierarchical Multiprocessors: the BubbleSched Framework[END_REF]. This way, the scheduler has a persistent view of the threads relationship that can be defined by sharing data or synchronizing a lot for example. As bubbles can contain nested bubbles, nested parallelism ends up with generating a tree of threads.

OpenMP parallel regions create threads to parallelize a sequential job. These threads usually share data and often needs to synchronize with each other. Thus the FOREST-GOMP runtime groups these threads into the same bubble structure. More generally, a bubble is created every time the application creates parallelism. As nested parallel regions generate nested bubbles, FORESTGOMP automatically builds a tree of OpenMP thread teams out of any OpenMP applications. This gives the FORESTGOMP scheduler a persistent and global view of threads likely to work together.

The runtime then needs to efficiently map this structured parallelism onto any hierarchical architecture. To do so, we believe that the operating system should not completely hide the computer architecture. Therefore, our runtime builds a To sum it up, FORESTGOMP structures the parallelism by generating a tree of threads and bubbles out of OpenMP applications and models hierarchical architectures with a tree of runqueues. So the problem of scheduling boils down to mapping a tree of threads onto a tree of runqueues. Many ways exist to implement this mapping, depending on the application nature and needs. The FORESTGOMP runtime provides several mapping policies called bubble schedulers. One may even design his own specific bubble scheduler thanks to a programming interface that helps with the details of bubbles and runqueues management.

The FORESTGOMP runtime system is implemented as a shared library that is binary compatible with LIBGOMP and extends it by adding a specialized affinity hint interface. As depicted on Figure 1, applications create OpenMP thread teams and let FORESTGOMP transparently schedule them using custom thread schedulers that are for instance invoked when an imbalance or locality issue appears. FOREST-GOMP relies on the BUBBLESCHED framework of the MARCEL multithreading library [START_REF] Thibault | Building Portable Thread Schedulers for Hierarchical Multiprocessors: the BubbleSched Framework[END_REF] to actually execute these threads according to its scheduling decision.

The knowledge of the underlying hardware is gathered from the HWLOC and MAMI libraries. HWLOC1 [START_REF] Broquedis | hwloc: a Generic Framework for Managing Hardware Affinities in HPC Applications[END_REF] was initially developed internally in BUBBLESCHED to gather portable information about the underlying hardware at startup. It is now available as a standalone library that builds a hierarchical architecture tree composed of objects describing the hardware (Node, Socket, Cache, Core, and more) and various attributes such as the cache type and size, or the socket number. It provides MPI and OpenMP libraries with a portable programming interface that abstracts the machine hierarchy, offering both hardware information gathering and process and thread binding facilities. MAMI2 is a memory interface that was designed to manage memory allocation and placement with regard to NUMA nodes within our user-level thread library in a portable manner. Aside from usual memory allocation policies such as binding or interleaving, it also offers synchronous and next-touch memory migration strategies. FORESTGOMP relies on these features to implement its memory affinity directives.

C. An open scheduling framework

The FORESTGOMP platform allows programmers to easily write, experiment with and tune thread scheduling policies. It provides a high-level API for writing powerful and portable schedulers that manipulate threads grouped into bubbles, as well as tracing tools to help analyzing the dynamic behavior of these schedulers. Programmers can hence focus on algorithmic issues rather than on nasty technical details.

Our programming interface is centered around primitives for manipulating bubbles and threads among a hierarchy of runqueues reflecting the underlying topology. Threads and bubbles are equally considered as entities, while bubbles and runqueues are equally considered as scheduling holders, so that we end up with entities (threads or bubbles) that we can schedule on holders (bubbles or runqueues). Primitives are then provided for manipulating entities in holders. Runqueues can be accessed through vectors, and can be walked thanks to "father" and "son" pointers. Some functions permit to gather statistics about bubbles so as to take appropriate decisions. This includes for instance the total number of threads and the number of running threads, but also various information such as the accumulated expected and current CPU computation time or memory usage, or the cache miss rates. To handle concurrency, one can use either fine-grain locking functions or coarse-grain functions which lock a whole sub-part of the machine (runqueues and bubbles).

Writing a high-level scheduler actually reduces to writing some hook functions. For instance, one of these hooks is called when the ground Self-Scheduler encounters a bubble during its search for the next thread to execute. The default implementation just looks for a thread in the bubble (or one of its sub-bubbles) and switches to it. Another hook is called when some time-slice for a bubble expires, and hence permits periodic operations on bubbles with a perbubble notion of time. Of course, mere "daemon" threads can also be started for performing background operations. As a result, programmers may manipulate threads with a high level of abstraction by deciding the placement of bubbles on runqueues, or even temporarily putting some bubbles aside (by defining their own runqueues that the basic Self-Scheduler will not look at).

D. Raw performance

As preliminary experiments, we tested the LIBGOMP library that comes with GCC 4.4, the INTEL compiler 11.1 and the FORESTGOMP runtime on the EPCC microbenchmark and the NAS OpenMP parallel benchmark suite. We executed these benchmarks on a quad-socket quad-core Opteron computer while setting the OMP_NUM_THREADS environment variable to 16 to get one thread per core. In that case, and more generally when dealing with flat parallelism, the FORESTGOMP runtime binds one thread per core. Figure II shows the overhead of each runtime system for each OpenMP construct obtained with the EPCC micro-benchmark. Figure I shows the speed-up of the B class of each application from the NAS OpenMP parallel benchmark suite. The calculated speed-ups refer to the sequential execution time of each application compiled with the INTEL compiler. The FORESTGOMP runtime behaves better on both BT and MG applications thanks to a more stable thread distribution. The INTEL runtime obtains better speed-ups on EP and SP thanks to better compiler optimizations. Indeed, the last two lines of table I show that serial execution times compiled with ICC and GCC (without OpenMP directives) differ a lot for these applications. INTEL locks are more efficient than the ones provided by the LIBGOMP and FORESTGOMP runtimes, so the INTEL runtime behaves better on the UA application which generates more than 300000 locks. The performance obtained with the CG, FT and LU applications (exceeding 16 of speed-up thanks to cache effects) is very similar. FORESTGOMP only adds a small overhead induced by the management of the bubble structures.

III. DESIGNING MULTICORE-AWARE SCHEDULING POLICIES

OpenMP developers are used to explicitly drive the parallel behavior of their code but the increasing complexity of computer architectures now renders this process difficult. Multicore architectures expose many processing units often organized in a hierarchical way, sharing multiple levels of cache memory. This explains why parallel languages generating flat parallelism often fail to exploit these architectures at their full potential (benefit from cache memory reuse, fast synchronizations, locality commodities).

Nested parallelism seems to be a natural way to fit the hierarchical structure of parallel computers. However, considering two running nested teams for instance, the first team to finish its work will make a whole set of cores idle, waiting for the other one to complete. Thus, to exploit this paradigm efficiently, it is necessary to create more OpenMP threads than cores or to dynamically allocate new cores to teams. This comes with a price that needs to be mitigated by the runtime system. For instance, Table III shows how the FORESTGOMP barrier was tailored in this aim.

A. A scheduling strategy to deal with multiple levels of cache memory

We previously presented a scheduler named Affinity [START_REF] Broquedis | Scheduling Dynamic OpenMP Applications over Multicore Architectures[END_REF] and showed that FORESTGOMP was able to schedule a very irregular application, called MPU, computing an implicit surface reconstruction which produces more than 30 000 threads per second on a 16-core computer. We present here the Cache scheduler, an evolution of Affinity, which differs in its initial distribution and by the fact Cache is able to take the thread workload into account. The Cache bubble scheduler main goal is to maximize cache memory reuse by scheduling related threads together onto cachesharing cores. In the context of OpenMP, this means to keep the OpenMP teammates together as long as possible. FORESTGOMP structures OpenMP parallelism by grouping threads created from a parallel region into the same bubble. Taking cache affinity into account reduces to preventing the scheduler from breaking these bubbles. The Cache distribution algorithm first sorts the teams to schedule depending on their workload. This way, when there are more teams than cores to occupy, a greedy distribution guarantees that the scheduler will not have to burst any bubble. Otherwise, Cache decides to burst the bubble containing the greatest number of threads first. The scheduler maintains statistics about where the threads were scheduled the last time the Cache algorithm was called, to be able to place them back at their previous location and maximize cache memory reuse. The Cache scheduler also implements a work stealing algorithm, inspired from existing programming models like Cilk or TBB, with the exception that the Cache scheduler starts to look for threads to steal locally first, in accordance with cache affinities expressed by bubbles. The way the Cache work stealing algorithm browses the architecture topology has a direct impact on the overall application performance.

B. Evaluation with the BT-MZ application

We also experimented with the BT-MZ application. It is one of the 3D Fluid-Dynamics simulation applications of the Multi-Zone OpenMP version of the NAS Parallel Benchmark 3.3. In this version, the mesh is split in the x and y directions into zones. Parallelization is then performed twice: simulation can be performed rather independently on the different zones with periodic face data exchange (coarse grain outer parallelization), and simulation itself can be parallelized among the z axis (fine grain inner parallelization). As opposed to other Multi-Zone NAS Parallel Benchmarks, the BT-MZ case is interesting because zones have very irregular sizes: the size of the biggest zone can be as big as 25 times the size of This application differs from MPU in the way the application programmer knows the workload associated with each zone. Transmitting this information to the runtime system can help guiding the scheduling to favor load balancing. The Cache distribution algorithm takes workload information into account when there are more groups of threads to distribute than cores to occupy. In that case, the scheduler performs a greedy distribution considering the workload of each team.

Table IV shows the speed-ups obtained by the LIB-GOMP and INTEL runtime systems, and different versions of the Cache scheduler that comes with FORESTGOMP, depending on the number of threads created from outer and inner parallel regions. We tested the C class of the BT-MZ application on a quad-socket quad-core computer. First, the performance confirms the FORESTGOMP runtime was designed for nested parallelism as it behaves better, for any combination of outer and inner number of threads, than the LIBGOMP and INTEL libraries. The Cache scheduler behaves best with 32 teams of 8 threads. Creating more threads than processors in this application offers the Cache scheduler ways to steal work when a processor idles, reaching this way a speed-up of 14.48. The column Cache + load info shows the performance obtained when the application programmer provides the workload associated to each zone to compute. This way, the Cache scheduler distribution algorithm takes the load into account when distributing the teams thus minimizing the need to call the work stealing algorithm. Such a distribution obtains a speed-up of 15.05. Alternatively, we slightly modified the Cache distribution algorithm to improve the load balance. In this version, instead of distributing all the teams over the core-level runqueues, we pick the most-loaded runqueue of each NUMA node and put its workload on the NUMA-level runqueue. This way, when a core completes the jobs associated to its runqueue, it starts helping out the most-loaded core associated to its NUMA node without having to call the work stealing algorithm. This strategy leads to a speed-up of 15.25, the best performance we obtained on the BT-MZ application, thanks to the fact that Cache distributes the OpenMP teams in a deterministic way that always leads to the same distribution, thus improving locality. This strategy also guarantees that teams with the highest workload will be executed first reducing the ending idle time.

Several OpenMP language extensions have been proposed to control the allocation of work to the participating threads. In order to favor affinities in a portable manner the NANOS compiler [START_REF] Ayguade | Employing Nested OpenMP for the Parallelization of Multi-Zone Computational Fluid Dynamics Applications[END_REF] allows to associate groups of threads with parallel regions in a static way in order to always execute the same thread on the same core. The OpenUH Compiler [START_REF] Chapman | Extending OpenMP Worksharing Directives for Multithreading[END_REF] proposes a mechanism to accurately select the threads of a subteam to define the thread-core mapping for better data locality, although this proposition does not involve nested parallelism.

Both mechanisms can lead to the performance FOREST-GOMP obtains on the BT-MZ benchmark. Indeed, the regular application scheme makes the best thread distribution feasible by explicit thread binding. However, the next section presents experiments in which the thread distribution needs to be reviewed dynamically to achieve the best performance.

IV. DESIGNING MEMORY-AWARE SCHEDULING POLICIES

FORESTGOMP achieves interesting speedups on previous examples thanks to regular memory access patterns. However, in the general case, the application may exhibit irregular access patterns that must be taken into account when load-balancing threads. Thread teams must be able to migrate together with their datasets in memory so as to maintain good locality and load balance.

A. Dealing with NUMA constraints at runtime

To keep designing larger scale configurations, computer architects propose ways to connect multicore chips together relying on technologies like AMD HYPERTRANSPORT or INTEL QPI. The resulting computers burden the application programmer with NUMA penalties and memory contention, making him concerned by memory affinity and thread/memory locality. Some software support already exists to help with limiting the amount of remote memory accesses in parallel applications, like the first-touch and next-touch allocation policies. first-touch makes the operating system allocate the considered pages next to the first thread to access them. It helps with improving thread/data locality, but assumes the memory access patterns will not change during the entire execution. next-touch asks the operating system to migrate the considered pages next to the next thread to access them. It helps with improving the performance of irregular applications, but is not widely available. More generally, both policies suffers from the same issues. First, they assume the first thread to touch the page will be the one that will work on them later. They also ignore the underlying system state while migration may suffer from out-of-memory situations or contention on the bus. These issues vary during the execution, forcing the thread and data distribution to adapt dynamically. That is why our approach is to let the runtime system in charge of threads and data placement. It is easier to achieve a sharper jointed distribution of threads and data with the precious hints the application programmer (or compiler) can provide : programmers (or compilers) may have a global view of threads and data relationship while a runtime can only discover them on the fly.

When it comes to designing applications for NUMA architectures, the application programmer has no other option than relying on the operating system. From our point of view, the runtime system is more likely to communicate efficiently with the operating system. Expressing his needs to the runtime system keeps the application programmer from designing non-portable applications. That is why, in a NUMA context, FORESTGOMP provides a programming interface for the programmer to express memory affinity from his application [START_REF] Broquedis | Dynamic Task and Data Placement over NUMA Architectures: an OpenMP Runtime Perspective[END_REF]. He no longer needs to be concerned about the underlying system state. All he has to do is to express his application patterns in a generic way. FOREST-GOMP provides two functions to do so: the first one sets the memory affinity for an OpenMP team to be born, and the second one sets the affinity for the caller thread from inside a parallel region. While the first one allows the runtime to perform early optimizations like directly creating the threads on the right runqueues, the second one is also needed when the memory access pattern changes inside a parallel region.

B. The Memory bubble scheduler

Now that the application programmer is able to transmit the memory affinities from his application to the runtime system, we need a scheduling strategy to perform a sound distribution of threads and data regarding the gathered information. This section introduces the Memory bubble scheduler.

Scheduling while preserving memory affinities: Every FORESTGOMP threads and teams now have some attached memory areas the runtime system can see. The Memory scheduler main goal is to distribute the threads and migrate the attached data to make every OpenMP team access local memory. To do so, it implements a three-phases distribution algorithm. The first algorithm phase consists in attracting the threads to the NUMA node holding the higher amount of their data. This information can be summarized onto bubbles. A bubble will explode if it contains threads attracted to different runqueues for the scheduler to be able to satisfy every expressed affinity. The phase one can lead to an unbalanced distribution. Indeed, some applications may allocate the accessed data on a small group of nodes, which means some nodes would not have any threads to execute at the end of phase one. To make sure every core will be occupied at the end of the distribution, the second algorithm phase stretches some memory affinities to balance the load on the computer. We move the threads with the smallest amount of attached memory first to do so (including threads with untouched memory). The last phase of the distribution algorithm is a matter of migrating the remotely-located data to the new threads location. As threads were driven to the node holding the bigger amount of their data during phase one, the Memory scheduler is guaranteed to migrate as less data as possible. This aspect has a real impact on performance, as migrating data is far more expensive than moving FORESTGOMP threads. When the distribution over the node level runqueues is over, an instance of the Cache scheduler is called inside each NUMA node to perform a cache-aware threads distribution.

Updating the threads and data distribution at the right time: Updating the threads and data distribution is a sensitive mechanism that influences the overall application performance. Calling the bubble scheduler too often will slow down the execution, as the bubble scheduler will browse the architecture topology to figure out the updates to perform on the current distribution. On the other hand, you will not get the best performance if the scheduler do not react soon enough in case of a major access pattern change. FORESTGOMP adopts a two-ways mechanism to decide how often the distribution needs to be updated. First, every time the application programmer updates the memory affinities, the bubble scheduler is called to check the current distribution. This approach may not be sufficient for irregular applications, so FORESTGOMP also provides a more dynamic mechanism based on hardware counters inspecting. The runtime checks the counters on a regular basis and infers the amount of remote memory accesses initiated from the current processor while defining a threshold from which FORESTGOMP will call the scheduler for checking the current distribution. These two approaches are complementary. Indeed, in some cases updates from the application programmer will not need the scheduler to rethink the current distribution. In other cases the programmer is able to roughly define which part of his application will work on which data, but cannot tell precisely when and how. Hardware counters can help reacting at the right time for these situations.

C. Evaluation

We evaluate our approach on the Twisted-STREAM and LU matrix factorization benchmarks.

Twisted-STREAM: STREAM3 is a synthetic benchmark parallelized using OpenMP that measures sustainable memory bandwidth and the corresponding computation rate for simple vectors. The three input vectors are wide enough to limit the cache memory benefits (20 millions double precision floats) and are initialized in parallel using a firsttouch allocation policy to get the corresponding memory pages close to the thread that will access them.

To complicate the STREAM memory access pattern, we designed the Twisted-STREAM benchmark in which we use nested OpenMP parallel regions. The benchmark now creates one team per NUMA node of the computer that works on its own set of STREAM vectors initialized in parallel, as in the original version of STREAM. To fit the target computer, a quad-socket quad-core OPTERON computer, the benchmark creates four teams of four threads.

Twisted-STREAM contains two distinct phases. During the second phase, each team works on a different data set than the one it was given in the first phase. We also modified the original benchmark so as to make the threads workload vary. The user can so specify how many STREAM iterations each team will have to compute.

The first-touch allocation policy only gives good results for the first phase as shown in table V. FORESTGOMP achieves the best and most stable performance on phase 1. The underlying bubble scheduler distributes the threads by the time the outer parallel region is reached. Each thread is permanently placed on one NUMA node of the computer. Furthermore, FORESTGOMP creates the teammates threads where the master thread of the team is currently located. As the vectors accessed by the teammates have been touched by the master thread, this guarantees the threads and the memory are located on the same NUMA node, and thus explains the good performance we obtain during phase one.

A typical solution to the lack of performance observed during phase two seems to rely on a next-touch page migration between the two phases of the application. However we show in the remaining of this section that next-touch is not always the best answer to the memory locality problem. We tested two different versions of the Twisted-STREAM benchmark: Twisted-100, in which all of the three vectors are 2 ± 1 GB/s 3 ± 0.5 GB/s 3.6 ± 0.2 GB/s Phase 2 1.3 ± 1 GB/s 2 ± 0.5 GB/s 1.7 ± 0.2 GB/s remotely-located during phase 2, and Twisted-66 in which only two of the three vectors are located on a remote NUMA node. It is worth noticing that we obtained performance shown in table V with Twisted-100.

Table VI shows the normalized execution times of the Twisted-100 benchmark compared to the performance obtained by the LIBGOMP runtime. In this case, all data is remotely located during phase 2. next-touch migrates the data to the location of the threads, which helps improving the performance when the threads workload is big enough. The Memory bubble scheduler prefers to move the threads to the location of the data. Indeed, the STREAM benchmark works on three 160MB-vectors. As migrating 480MB of memory is far more expensive than moving 16 FORESTGOMP threads, FORESTGOMP obtains the best performance here, whatever threads workload we set.

In the case of the Twisted-66 benchmark, only two of the three STREAM vectors are located on a remote NUMA node during phase 2. This time, the Memory bubble scheduler will first attract to threads to the location of the two remote vectors, and then migrate the remaining one. This way, FORESTGOMP only migrates one vector, instead of migrating two of them with a next-touch approach. Table VII shows the Memory scheduler algorithm offers performance gain sooner, and still behaves better than next-touch when the workload increases.

LU Matrix Factorization: We now look at a threaded LU matrix factorization. As usual, the implementation splits the matrix into smaller data blocks that are actually manipulated by a BLAS library (ATLAS). During each step, a new pivot block is computed on the diagonal. Then, the values for the corresponding column and row are updated as well as the ones for the remaining bottom-right blocks. This is done using for loops that we parallelized thanks to OpenMP parallel for pragmas. Data is initially distributed across all memory nodes in a interleaved manner so as to maximize the memory throughput. We measure a 388.9s factorization time (60.3 Gflop/s) for a 32k-wide matrix divided in 64 blocks per dimension.

This program is actually a good example of application where the developer cannot easily give useful hints about memory access patterns. Indeed, the number of blocks involved in each computation step decreases quadratically, causing threads to work on highly different blocks at each step. Therefore, instead of trying to understand these patterns and place threads and data jointly, we use a lazy next-touch approach. The whole matrix is marked as next-touch when the hardware counters overcome the FORESTGOMP remote accesses threshold so that the data is redistributed among the NUMA nodes when needed, depending on OpenMP thread access patterns. The factorization time decreases by 30% down to 298.2s (80.78 Gflop/s) thanks to this strategy that requires a moderate amount of work from the developer. Other matrix sizes show similar behavior but the block size must be carefully chosen so that the next-touch strategy is not disturbed by single pages being shared between multiple blocks/threads.

If migrating pages on next-write only, another 2.7% improvement is even obtained. We understand this result as the fact that Writers should be privileged in this algorithm since placing pages near them improves performance over placing pages near the first reader or writer.

V. RELATED WORK

Memory placement has been studied in the context ofOpenMP through some proposals towards data distribution directives la HPF [START_REF] Benkner | Efficient parallel programming on scalable shared memory systems with High Performance Fortran[END_REF], [START_REF] Chapman | Achieving performance under OpenMP on ccNUMA and software distributed shared memory systems[END_REF]. Such directives are useful to organize data the right way to maximize page locality, and, in our research context, a way to transmit affinity information to our runtime system without heavy modifications of the user application. Automatic page migration [START_REF] Nikolopoulos | User-Level Dynamic Page Migration for Multiprogrammed Shared-Memory Multiprocessors[END_REF] was also proposed as an innovative way to maintain locality in applications with regular memory access pattern. The convenient next-touch policy was studied as a way to tackle irregular algorithms which suffer from the lack of cooperation between the scheduler and the allocation library [START_REF] Lf | affinity-on-next-touch: increasing the performance of an industrial PDE solver on a cc-NUMA system[END_REF], [START_REF] Terboven | Data and Thread Affinity in OpenMP Programs[END_REF].

Multilevel and nested parallelism has long been emphasized as a promising path toward scalability with OpenMP [START_REF] Martorell | Thread Fork/Join Techniques for Multi-Level Parallelism Exploitation in NUMA Multiprocessors[END_REF], [START_REF] Tanaka | Performance evaluation of openmp applications with nested parallelism[END_REF], gradually brought compiler researchers and vendors to put more of their efforts on OpenMP nested parallelism. Extensions to control the binding of OpenMP threads were also proposed [START_REF] Ayguade | Employing Nested OpenMP for the Parallelization of Multi-Zone Computational Fluid Dynamics Applications[END_REF], [START_REF] Chapman | Extending OpenMP Worksharing Directives for Multithreading[END_REF]. Beyond the specific context of OpenMP, user-level multithreading was also the target of the INTEL Many-Core RunTime [START_REF] Saha | Runtime Environment for Tera-scale Platforms[END_REF] environment.

McRT extends the task queue mechanism to support scheduling domains that allows an application to select different hardware units where its different parts to be scheduled on. It however doesn't provide any framework for developing dedicated schedulers, and thus can only provide a limited range of scheduling abilities. Several operating systems provide facilities for distributing kernel threads along the machine by grouping them into sets: liblgroup on SolarisNSG on Tru64 and libnuma on Linux. These look very much like single level bubbles, but no possibility of nested sets is provided, which limits the affinity expressivity. Moreover, none of them provides the degree of control that we provide: with BUBBLESCHED, the application has hooks at the very heart of the scheduler to react to events like thread wake up or processor idleness.

In the context of high productivity computing systems, PGAS languages (Chapel, UPC, X10,...) and Fortress provide programmers with ways to control where particular threads run and how large objects are laid out in memory. For instance, Fortress proposes a tree of regions to describe the structure of the machine on which a program is run and provides means to place a thread at a given region. It may be interesting to associate a region with a bubble and have our threading library schedule Fortress threads: the Fortress programmer could therefore express affinities and could benefit from dynamic scheduling mechanisms we propose.

VI. CONCLUSION AND FUTURE WORK

FORESTGOMP is a platform for executing and tuning OpenMP programs over hierarchical multicore architectures. Its main component is an efficient runtime system capable of scheduling trees of threads generated by an OpenMP compiler. These trees both capture application parallelism and serve as a vehicle for carrying thread relationship and memory affinity information. Because this information is maintained by the runtime system during the whole application run, it can be used to perform appropriate redistributions of threads or data whenever it is necessary.

We have shown the benefits of designing and tuning specific scheduling policies, according to the general behavior of the application. We have presented the Cache and Memory bubble schedulers that achieve very high performance on several applications. These schedulers are written in a portable way, independently from the target architecture, which demonstrates the relevance of our approach.

There are several research directions we intend to address in the near future. We plan to provide the application programmer with tools to mark memory areas that should be attached to a thread upon the next read or write touch. This mechanism would help the runtime system to better infer the memory affinities, especially when the memory access patterns become too complex to be defined a priori by the programmer.

Our proposal is in line with the recent efforts of the OpenMP Architecture Review Board which is currently working on the next evolution of the specification towards a satisfying support of hierarchical, multicore architectures. In particular, the next release will feature new directives for specifying affinity between threads and data. Our proposal of a runtime system able to handle this information is complementary.

In the longer run, we plan to explore ways to compose our scheduling strategies with other schedulers and paradigms. For instance, parallel languages like Cilk or TBB rely on runtime systems able to efficiently schedule finegrain parallelism on SMP architectures. The idea here is for instance to assign instances of TBB schedulers to each NUMA node, while letting our Memory scheduler distribute the work across the nodes, thus widening the spectrum of flat parallelism approaches to NUMA computers in a portable way.

ForestGOMP Runtime Library ForestGOMP hints libgomp interface topology discovery scheduling thread management NUMA Application BubbleSched Marcel hwloc MaMI

	Cache Scheduler	Scheduler Memory
	Figure 1. Description of the FORESTGOMP runtime system, its schedulers
	that are combined to tackle cache and memory affinity, and its interaction
	with the application and low-level libraries.
	generic representation of the architecture with the help of
	the OS as hierarchical runqueues. A runqueue is a list
	containing threads and bubbles to be executed. We associate
	a runqueue to any level of the architecture: we define
	core-level runqueues, processor-level runqueues, NUMA
	node-level runqueues that define scheduling domains. For
	instance, scheduling a thread on a node-level runqueue
	means this thread can only be executed by one of the core
	this NUMA node contains. This way, one may constrain
	the execution of OpenMP teams to a specific part of the
	computer architecture.

Table I

 I SPEED-UP OF THE NAS OPENMP PARALLEL BENCHMARK SUITE, COMPARED TO THE ICC AND GCC SERIAL TIME, ON A QUAD-SOCKET QUAD-CORE OPTERON COMPUTER.

	Runtime	BT	CG	EP	FT	LU	MG	SP	UA
	LIBGOMP3 vs. GCC serial	12.4	14.0	15.8	12.2	19.8	5.8	4.3	7.0
	FORESTGOMP vs. GCC serial 13.1	14.0	15.6	12.0	19.8	6.4	4.8	3.3
	LIBGOMP3 vs. ICC serial	11.5	12.4	9.1	10.1	17.0	5.1	3.2	6.6
	FORESTGOMP vs. ICC serial	12.1	12.4	9.0	9.9	17.0	5.6	3.6	3.1
	INTEL ICC vs. ICC serial	11.2	12.3	14.9	10.1	17.9	4.7	5.3	4.4
	GCC serial (s)	693	369	152	120	913	22.7	655	420
	INTEL ICC serial (s)	642	327	87.8	99.1	782	20.0	493	397

Table II RUNTIME

 II OVERHEAD (US) OBTAINED WITH THE EPCC MICRO-BENCHMARK ON A QUAD-SOCKET QUAD-CORE OPTERON COMPUTER.

	Runtime	atomic barrier	critical	for	lock	parallel parallel for reduction single
	LIBGOMP3	0.30	2.91	4.01	2.91	3.95	7.15	8.15	8.74	3.74
	INTEL ICC	0.39	5.12	2.20	5.07	2.21	8.15	8.18	15.66	19.50
	FORESTGOMP	0.29	3.31	4.03	3.34	3.88	7.02	7.46	7.58	2.56

Table III EPCC

 III BENCHMARK: OVERHEAD (US) OF THE BARRIER CONSTRUCT DEPENDING ON THE NUMBER OF THREADS ON A QUAD-SOCKET QUAD-CORE OPTERON COMPUTER.

	Runtime	16 threads	32 threads	64 threads
	LIBGOMP3	2.91	187.9 (×64)	371.1 (×128)
	INTEL ICC	4.93	17.98 (×3.64)	63.29 (×12.84)
	FORESTGOMP	3.31	3.87 (×1.17)	5.15 (×1.56)

the smallest one. In the original SMP source code, outer parallelization is achieved by using Unix processes while the inner parallelization is achieved through an OpenMP static parallel section. Similarly to Ayguade et al.

[START_REF] Ayguade | Employing Nested OpenMP for the Parallelization of Multi-Zone Computational Fluid Dynamics Applications[END_REF]

and Jin et al.

[START_REF] Jin | Performance evaluation of a multi-zone application in different OpenMP approaches[END_REF]

, we modified this to use two nested OpenMP static parallel sections instead, using n o * n i threads.

Table IV SPEED

 IV -UPS OBTAINED WITH THE BT-MZ (CLASS C) APPLICATION, COMPARED TO THE ICC SERIAL TIME, ON A QUAD-SOCKET QUAD-CORE OPTERON COMPUTER DEPENDING ON THE NUMBER OF THREADS CREATED FROM OUTER AND INNER PARALLEL REGIONS.

	Outer × Inner	LIBGOMP3	INTEL	Cache Cache + load info Tuned Cache + load info
	4×4	9.4	13.8	14.1	14.1	14.1
	16×1	14.1	13.9	14.1	14.1	14.1
	16×2	11.8	9.2	14.1	14.2	14.3
	16×4	11.6	6.1	14.1	14.9	14.9
	16×8	11.5	4.0	14.4	15.0	15.2
	32×1	12.6	10.3	13.5	13.8	13.8
	32×2	11.6	5.9	14.2	14.2	14.3
	32×4	11.2	3.4	14.3	14.8	14.8
	32×8	10.9	2.8	14.5	14.7	14.7

Table V AVERAGE

 V RATES PER NODE OBSERVED WITH THE TWISTED-STREAM BENCHMARK USING A first-touch ALLOCATION POLICY. DURING PHASE 2, THREADS ACCESS DATA ON A DIFFERENT NUMA NODE.

	LIBGOMP	INTEL	FORESTGOMP
	Phase 1

Table VI NORMALIZED

 VI EXECUTION TIMES OF THE TWISTED-100 BENCHMARK (1.00 IS LIBGOMP) DEPENDING ON THE NUMBER OF STREAM ITERATIONS.

		1	2	4	8	16	32	64	128
	next-touch	5.92	3.28 2.06	1.36	1.07	0.99	0.97	0.95
	FORESTGOMP	0.75	0.74 0.74	0.74	0.74	0.74	0.74	0.74

Table VII NORMALIZED

 VII EXECUTION TIMES OF THE TWISTED-66 BENCHMARK (1.00 IS LIBGOMP) DEPENDING ON THE NUMBER OF STREAM ITERATIONS.

		1	2	4	8	...	128	256	512	1024
	next-touch	1.72	1.3	1.1	1	...	0.96	0.94	0.93	0.93
	FORESTGOMP	1.29	1.08	0.99	0.94 ...	0.90	0.88	0.86	0.85

http://runtime.bordeaux.inria.fr/hwloc

http://runtime.bordeaux.inria.fr/MaMI

http://www.cs.virginia.edu/stream/