'Cultural' and 'historical' perspectives have roots in classical and more particularly Weberian sociology [START_REF] Weber | Economy and Society[END_REF]). In the cultural perspective, institutions are 'wider cultural and symbolic patterns', increasingly with a 'global' or transnational scope, that shape and to a large extent determine organizations, structures or actors and script behaviours and interactions [START_REF] Scott | Institutional Environments and Organizations[END_REF]Jepperson 2000a). Institutions, from this perspective, are not producedthey are external 'realities', they are givens and determining constraints to which actors, structures, organizations or even nation-states conform give or take a degree of decoupling [START_REF] Meyer | World society and the nation-state[END_REF]). In the long run, those institutions are on an evolutionary path leading towards greater rationalization and this the world over, naturally with standardization and homogenizing effects (Scott, Meyer et al. 1994, pp. 2-4). The origins of this evolutionary path are to be found in cultural schemas provided by Christendom and in the structuration of the modern system of nation-states [START_REF] Jepperson | Political modernities : four main variants of the modern polity[END_REF]. From this type of perspective, action reflects normative patterns. The logic of 'action' can be described using March and Olsen's terms (1998) as a 'logic of appropriateness' -knowing, however, that 'action' here cannot be understood as 'free agency'.

From an historical perspective, institutions are frameworks essentially of a political, legal and societal nature. These frameworks are made up of organizations and formal rules and regulations often backed by coercive mechanisms and structures. This perspective insists on the particular significance of nation-states historically for the emergence and structuration of those frameworks. Those national institutional frameworks create powerful constraints at the national level and they lay out path dependencies that explain variations across countries in patterns of action, organization and interaction [START_REF] Fligstein | The Transformation of Corporate Control[END_REF][START_REF] Whitley | European Business Systems[END_REF][START_REF] Whitley | Divergent Capitalisms[END_REF]Hollingsworth and Boyer 1997;Hall and Soskice 2001). Those path dependencies also explain the robustness of national institutional frameworkseach of which is articulated in fact as a system [START_REF] Whitley | Divergent Capitalisms[END_REF]Maurice and Sorge 2000;Hall and Soskice 2001). From that perspective, the origins of institutional frames are external to actors for whom they essentially represent constraints and coercive mechanisms. And indeed action follows in that perspective what we call a 'logic of coercive constraint'.

Table 1 brings together in summary form and contrasts those three perspectives on institutions. For the purposes of this volume, we are moving towards our own type of institutional argument (see also [START_REF] Djelic | Exporting the American Model[END_REF]) that combines elements of all three perspectives and more particularly of the 'cultural' and 'historical' ones in an attempt at cross-fertilization [START_REF] Djelic | From a typology of neo-institutional arguments to their crossfertilization[END_REF].

Definition of Institutions

In this volume, we use an umbrella definition of institutions as consisting of both structures and formal systems on the one hand and normative and cognitive frames on the other that altogether provide stability and meaning to social behaviour [START_REF] Scott | Institutions and Organizations[END_REF]; see also Djelic and Quack in the conclusion to this volume). These sets of institutions owe their survival to self-activating social processes of reproduction [START_REF] Jepperson | Institutions, institutional effects, and institutionalism[END_REF]. In our view, institutions have both a structural dimension, including formal and informal rules and systems and an ideational dimension, including normative and cognitive patterns. Whereas these two dimensions have always been treated and approached separately and by different streams of the institutional argument, we believe that in order to understand processes of institutional change and emergence both dimensions should be brought together and investigated simultaneously (see also [START_REF] Campbell | Institutional analysis and the role of ideas in political economy[END_REF][START_REF] Djelic | Exporting the American Model[END_REF]).

We also combine the 'culture' and 'historical' perspectives in a different manner. We acknowledge the need to take into consideration together and at the same time the two levels of analysis that characterize each of these perspectives -'global' or transnational for the cultural perspective and national for the historical one. As we will see below, one way to reconcile institutional arguments with issues of change and emergence is precisely to look at the interplay and interface between these two spheres or levels of analysis.

Another way in which to bring in issues of change and emergence is to take some distance from descriptions of institutions as constraining or even deter-mining behaviours -which is predominantly what institutional analyses do both in the cultural and in the historical stream. We need to think also of the enabling functions of institutions. It is necessary to investigate, in other words the ways in which actors creatively recombine and extend the institutional principles at their disposal to devise new institutional solutions to their problems [START_REF] Sewell | A theory of structure: duality, agency, and transformation[END_REF][START_REF] Campbell | Mechanisms of evolutionary change in economic governance: interaction, interpretation and bricolage[END_REF][START_REF] Clemens | Politics and institutionalism: explaining durability and change[END_REF][START_REF] Caspar | Institutional adaptiveness, technology policy, and the diffusion of new business models: the case of German biotechnology[END_REF][START_REF] Kristensen | Unbundling battles over bounded rationalities[END_REF][START_REF] Lane | The emergence of German transnational companies: A theoretical analysis and empirical study of the globablization process[END_REF][START_REF] Sharpe | Globalization and change: orgnizational continuity and change within a Japanes multinational in he UK[END_REF]. It is necessary in other words to think of the conditions for 'institutional entrepreneurship' [START_REF] Fligstein | How to make a market: reflections on the attempt to create a single market in the European Union[END_REF]. Actors, here, are not the 'free agents' of the rational choice perspective but neither are they merely an aggregation of cultural scripts as suggested in the cultural perspective. We will show below that such recombination is much more likely in situations where different institutional frames enter into collision. One place, undeniably, where such collision is significant today is at the interface between national and transnational spheres.

In the following, we look more systematically into the treatment of change and emergence in the institutionalist literature. This naturally comes together with the correlative issues of institutional persistence and its conditions. We point, in the process, to the main building blocks of our own theoretical framework underscoring the ways in which it differs from existing perspectives.

Institutional Change and Persistence

A core insight behind institutional theory is that the patterning of social life is not produced solely by the aggregation of individual and organizational behaviours but also by institutions that structure actions through regulative instruments as well as normative and cognitive frames. Institutions and social actions are thus seen as being inextricably linked and as reciprocally and mutually constituting each other. Institutional accounts, particularly those fitting under the label 'historical' used above, have tended to emphasize the stability and durability of institutions. These accounts are based on an understanding of institutional arrangements where the latter are internally coherent and externally fitted. They tend to focus, furthermore, on the constraining or even determining effects of institutions on social behaviour rather than on potential converse and reciprocal effects.

Conditions of Institutional Persistence

There are two main ways in which institutions can constrain social behavioureither through external control and sanctioning or through persuasion, voluntary appropriation or socialization. Those institutional arguments that centre on states -their structures and constituent organizations -hence 'historical' institutionalism in our typology, tend to underscore the importance of control and sanctioning processes. In those arguments, the nation-state or state agencies have the capacity to establish rules, monitor conformity and exert sanctions if necessary. The power to sanction and control, however, does not have to be restricted to the nation-state and its agencies. Other societal bodies such as private firms and agencies or non-governmental organizations can exert authority based on their control over or access to resources and this may even extend beyond the borders of a particular nation-state with the potential risk of conflicting with or even undermining state authority [START_REF] Strange | The Retreat of the State. The Diffusion of Power in the World Economy[END_REF].

A second way in which institutions constrain behaviour is through processes of persuasion that operate in the absence of formal and centralized sanctioning authorities. These processes reflect essentially normative and cognitive logics and we identified 'culture' institutionalists as focusing more particularly on these types of logics. Norms and values become appropriated and internalized by individuals, groups or organizations, which motivates them to respect and defend the status quo even in the absence of controls or sanctions. Educational and professional organizations are good examples of societal bodies relying on these types of logics to ensure homogeneity and stabilization of behaviours.

Naturally, in situations where diffused rule setting is effected apparently through persuasion, it is much more difficult to identify and/or recognize power and power relations. It seems reasonable, nevertheless, to differentiate between those situations where a number of actors have privileged access to some resources that allow them to promote and push their own normative and cognitive frames and those situations where actors have more equal access to resources and get to develop collectively shared understandings and frames out of mutual interaction and dialogue.

The constraining power and dimension of institutions can explain their persistence and robustness over time. The motives of social actors to support existing institutions and oppose change can reflect the articulation of two complementary rational logics -the fear of sanctions for subordinates and the desire to defend vested interests for dominant groups. These motives can also reveal successful socialization and internalization that led actors to believe that existing institutions are the best, the only or the most efficient solutions.

We propose that the stability, robustness and self-reproducing character of institutions will be all the more pronounced that regulative pressures and systems of control combine with normative and cognitive frames and reinforce each other. Legal institutions, for example, would hardly be as effective if they were not strengthened by actors' internalized beliefs of what is 'right' and 'wrong', of what is 'honesty' and 'fraud', and so on. The view that institutions articulate into systems -particularly at the national level -naturally makes stability and robustness even more likely. The homogeneity and coherence of the whole is assumed to have an impact on the preservation and reproduction of the parts [START_REF] Burns | The Shaping of Social Organization[END_REF][START_REF] Jepperson | Institutions, institutional effects, and institutionalism[END_REF][START_REF] Whitley | Divergent Capitalisms[END_REF]Maurice and Sorge 2000;Hall and Soskice 2001).

The Nature of Institutional Change

The extreme picture of a self-stabilizing, self-reproducing and tightly fitted system of constraints, characteristic in particular of historical institutionalism, leaves little place in this form to the idea of institutional system change or to the consideration of institutional emergence.

With respect to change of institutional systems, particularly those institutional systems of a national scope, institutional perspectives have tended to do one of three things. A number of these perspectives have de-emphasized change, pointing at the most to small, progressive or non-consequential steps. This has particularly been the case for the historical stream of institutional arguments. Instead of change, these perspectives have underscored the enduring stability and resilience of national institutional frameworks or systems even in the face of significant pressure for change, as stemming for example from processes of internationalization (D'Iribarne 1989[START_REF] Whitley | Divergent Capitalisms[END_REF]Maurice and Sorge 2000;[START_REF] Zeitlin | Americanization and its Limits[END_REF]Hall and Soskice 2001). Some of the resilience of national institutional systems has been related to what can be called their inherent 'flexibility for stability'. These are mechanisms and properties which enable societal systems to adapt and readjust to changes in their environment without breaking with the overall system logic [START_REF] Burns | The Shaping of Social Organization[END_REF][START_REF] Offe | Designing Institutions for East European Transition[END_REF][START_REF] Pempel | Regime Shift[END_REF]Quack and Morgen 2000).

Alternatively, some institutional arguments have acknowledged the possibility of a transformation of national institutional frameworks but essentially as a dramatic and rupture-like process, often implying a major crisis [START_REF] Westney | Imitation and Innovation[END_REF][START_REF] Djelic | Exporting the American Model[END_REF]). This suggests a picture of punctuated equilibria -a Kuhnian-type succession between periods of stability and moments of paradigm shift [START_REF] Kuhn | The Structure of Scientific Revolutions[END_REF][START_REF] Krasner | Approaches to the state: alternative conceptions and historical dynamics[END_REF].

A third approach has pointed to a long-term evolutionary process whereby a world-society carrying standardized and rationalized cultural and normative patterns was building up. In time, national institutional systems were coming to reflect those patterns becoming in the process increasingly homogeneous [START_REF] Meyer | World society and the nation-state[END_REF]Jepperson 2000a). This has defined the cultural stream of institutional arguments. Beyond the evolutionary trajectory, there is little specification in that approach of the concrete ways in which this world-society institutional frame is building up and being structured, or of the concrete mechanisms through which it is reverberating and translating into institutional system change at the national level.

From our perspective, a dichotomous opposition in the form of extreme alternative between radical and incremental change is not satisfying. Rupturelike change processes are assumed to have the potential to effect a radical transformation of the core institutional order of a society such 'that we can speak of a change in type of society' (Lockwood 1964, p. 244). Incremental institutional change, in contrast, is expected to be path dependent and rarely consequential by definition. Indeed, preexisting institutions constrain the ways in which actors perceive and choose alternative solutions when earlier arrangements become challenged and, as a consequence, the core institutional order of society remains in place, unchanged or, at the most, only slightly modified [START_REF] North | Institutions, Institutional Change and Economic Performance[END_REF]Campbell et al. 1991;Whitley and Kristensen 1997;[START_REF] Whitley | Divergent Capitalisms[END_REF]Maurice and Sorge 2000;Hall and Soskice 2001).

In fact, even in situations of rupture-like change, quite a number of institutional principles will carry over from one period to the next. Campbell (1997, p. 28), for example, concludes from his collaborative work on institutional transformation in Central and Eastern Europe that dichotomies 'such as these convey the impression that fundamental institutional change is a discontinuous process when even ostensibly revolutionary changes often embody significant evolutionary qualities'.

On the other hand, incremental models of change may be largely overestimating the continuity of institutional arrangements over the long run. In this book we suggest that, in certain circumstances, incremental change may be highly consequential -we call that the 'stalactite' model of change (for more see Djelic and Quack in the conclusion to this volume). This type of change may lead in time and progressively to a profound and qualitative transformation of the core institutional order or at least of some of its key dimensions. Our 'stalactite' model of change is one where change is seen as both incremental and consequential -where change is in fact the aggregation and crystallization through time of a multiplicity of smaller processes of transformation. We posi-tion this 'stalactite' model of change as complementing rather than displacing other perspectives.

Loci and Triggers of Institutional Change

According to [START_REF] Tolbert | The institutionalization of institutional theory[END_REF] the emergence of institutions is a process in three stages. First, actors develop through recurrent and regular interactions patterned reactions to problems to which shared meanings and understandings become attached (see also [START_REF] Berger | The Social Construction of Reality[END_REF]. This is in fact a pre-institutionalization stage.

Then these particular meanings and understandings become generalized beyond the specific context in which they crystallized. This second stage can be called the objectification stage and goes together with the stabilization of a consensus among social actors about the value of the behavioural patterns and of their associated meanings and understandings. This consensus can translate into preliminary structures and rules that on the whole remain fragile at this semi-institutionalized stage and can still be revised or challenged.

The third and last stage of institutionalization is what [START_REF] Tolbert | The institutionalization of institutional theory[END_REF] call 'sedimentation'. It is characterized both by an even wider spread of patterned behaviours and meanings and by the solidification and perpetuation of structures. It is during this last stage that institutions can potentially acquire the 'quality of exteriority', that is, become taken for granted and develop a reality of their own.

The logical sequencing goes from habitualization to sedimentation. However, it is possible in a number of situations to skip the first stage -the habitualization stage. The diffusion of institutional rules preexisting in a different context represents such a short cut with a direct move into the objectification stage [START_REF] Tolbert | The institutionalization of institutional theory[END_REF]. Following [START_REF] Dimaggio | The iron cage revisited : institutionalized isomorphism and collective rationality in organizational fields[END_REF], there are three main channels for such a process of diffusion -the coercive, the mimetic and the normative. All three types of channels may be operative simultaneously thus reinforcing each other. They may also alternate or follow each otherthe coercive channel being supported over time or even replaced by mimetic and normative ones [START_REF] Djelic | Exporting the American Model[END_REF].

Moving from institutions to institutionalization and thinking about the latter as a set of sequential stages -habitualization, objectification and sedimentation -suggests that the level of embeddedness and robustness of institutional rules will vary. Certain patterns of social behaviour -those that are semi-institutionalized or still at stage one or two -will be more likely to become subject to critical evaluation, modification and elimination than others -those that are fully institutionalized. Or as [START_REF] Jepperson | Institutions, institutional effects, and institutionalism[END_REF] puts it, degrees of institutionalization are best conceived in terms of relative vulnerability to social intervention.

Within a given society, varying patterns of behaviours will coexist that situate themselves at different stages of institutionalization. Instead of considering the systemic nature of institutional arrangements, we should take in this internal diversity and differentiation and the contradictions that it may generate [START_REF] Sewell | A theory of structure: duality, agency, and transformation[END_REF][START_REF] Clemens | Politics and institutionalism: explaining durability and change[END_REF]. We should also look at border points or points of interface through which, we have suggested, alternatives may appear. In this volume, we focus in particular on those points of interface that put in contact the national and the transnational. Together, those are the cracks in the system -or at its boundaries -that are likely to make it more vulnerable. Those cracks or weaker points indicate the more obvious potential loci for change. We argue that external pressures can act as triggers. Major shifts in the environment, such as long-lasting alterations in markets or radical changes in technology may play a role. Internationalization, we add, is also in itself source of pressure (see also [START_REF] Westney | Imitation and Innovation[END_REF][START_REF] Campbell | Institutional theory and the influence of foreign actors on reform in capitalist and post-socialist societies[END_REF][START_REF] Djelic | Exporting the American Model[END_REF]Boyer et al. 1998;[START_REF] Lane | The emergence of German transnational companies: A theoretical analysis and empirical study of the globablization process[END_REF]. Our claim in this volume is that we should combine a focus on internal loci of disruptions and opportunities with an argument on external triggers of change. We point to institutional change as emerging where and when internal challenges and spaces of opportunity combine with and are being reinforced by external triggers and alternatives. Globalization is in part about the multiplication of configurations of that type.

Agents of Change: Foreign versus Domestic, Dominant versus Fringe Players

The understanding of institutions presented here as not only constraining but also enabling points to the role and significance of actors, sometimes characterized by the labels 'strategizing actors' or 'institutional entrepreneurs'. Institutional change comes about when certain groups or networks of actors develop new patterns of interaction, from scratch or through bricolage, when certain groups or networks seize upon patterns existing elsewhere and promote them as superior to existing arrangements, working to mobilize as large and significant a support as possible for that project.

The challenge to institutionalized rule systems can best be understood, we argue, when we have a clear picture of the impact different actors can have. From the perspective we develop here that the national/transnational interface is important to understand changes in national rules of the game, we differentiate between dominant and fringe actors but also between foreign and domestic actors. The following categorization, summarized in Table 2, is schematic and should be taken as identifying ideal types rather than as real life description. Dominant actors are those who hold a central position in terms of power and social status, based on privileged access to resources. Dominant foreign players will have the strength and resources to push along their own rules of the game well beyond their traditional boundaries of activity. They can become 'missionaries' of institutional change. Dominant local players will tend to do one of two things -either to resist change or else be its driving force.

In periods of relative stability, they will tend to resist institutional change. Dominant local players are likely then to have vested interests in existing institutions. Their perception of the world also has a tendency to remain structured by just these institutions. In periods of crisis, radical rupture or acute challenge, dominant local actors can turn however into active promoters of institutional change and in fact become its main driving force. The case of Nokia in Finland perfectly illustrates that (Tainio et al. in this volume). Other examples can be found in the Eastern part of the European continent.

One should add here the particular case of the transnational firm where a dominant actor is neither fully domestic nor entirely foreign but somewhere in between. There will be a tendency for these types of actors to be unsatisfied with the preexisting institutional conditions characteristic of their country of origin. These actors will then possibly turn into active promoters of institutional change -the case of Nokia once again illustrates that but one thinks also of Vivendi in France or Daimler Benz in Germany. Another possible reaction will be for those hybrid, a-national actors to flee their country of origin and set up their headquarters elsewhere -Swedish multinationals have tended to follow that path.

On the other side, one finds fringe players. Fringe players are located at the periphery of a particular institutionalized area. They tend to have little power, low social status and limited access to resources. Fringe players from foreign contexts will tend on the whole to be absent from the local scene. For the most part, local fringe players will also be relatively powerless and passive. The few that may take the initiative, however, may be quite innovative. In relatively stable periods, local fringe players can have more incentives than dominant players to experiment with new solutions since such experiments are less costly to them in terms of reputation. They are also less likely to be sanctioned by central players for violating rule systems, and if successful they will gain increased power and social status from institutional change. Fringe players have been identified as critical actors for developing alternative practices at the micro level which were in contradiction with existing institutions at the macro level. [START_REF] Leblebici | Institutional change and the tranformation of interorganizational fields: an organizational history of the U.S. radio broadcasting industry[END_REF] show how fringe players changed the governance structure of an inter-organizational field such as the US broadcasting industry (see also [START_REF] Jones | Co-evolution of entrepreneurial careers, institutional rules and competitive dynamics in american film, 1895-1920[END_REF]. [START_REF] Stearns | Economic behavior in institutional environments: the corporate merger wave of the 1980s[END_REF] refer to fringe players as successful challengers of existing practices in inter-firm coordination in the US whose innovation then became legitimized and institutionalized, through adoption and adaptation by dominant players, as a market for mergers and acquisitions.

Fringe players can challenge existing arrangements either at the level of discourse or at the level of practice -a combination of both being in fact quite likely. This challenge could remain localized and lead nowhere. In certain circumstances, it could also come to arouse wide support and it could possibly become appropriated, adopted and adapted, by dominant players. The new solution will thus be advocated as superior until it becomes taken for granted. Institutional innovation through fringe actors is therefore more likely to take the bottom-up road and to operate through mimetic and normative pressures since these actors usually do not have the means to institutionalize their solutions through coercion and sanction from above.

In the context of globalization, we see another path as being particularly operational. This is the direct or indirect alliance between foreign dominant actors pushing their own rules of the game and a few local fringe players that find an interest in sponsoring those alternative rules (all contributions in Part I, see also [START_REF] Djelic | Exporting the American Model[END_REF][START_REF] Djelic | The coevolution of new organizational forms in the fashion industry : a historical and comparative study of France, Italy and the United States[END_REF]. This kind of alliance appears to take the champions and partisans of status quo and stability through a pincer movement.

Institution Building in the Transnational Space

A central claim of this volume, we have seen, is that the transnational level is one important purveyor in today's world of alternative rule systems that may contribute to the transformation of subsocietal or societal institutional arrangements. Those alternatives may themselves be rules that are dominant in foreign subsocietal or societal institutional spheres. They may also be, and this is we believe another major claim of this volume, rule systems in the making with a transnational scope or dimension. This process of structuration of a space traditionally conceived as anomic translates into institution building and institutional emergence at the transnational level. It is a marker and defining characteristic, we propose, of the recent episode of globalization.

Institutional Emergence -the Transnational Dimension

Even though there may have been cases, historically, when actors created social institutions from scratch and in a 'vacuum', the genesis of institutions in contemporary societies unfolds in general in a form that is closer to 'bricolage' than to ex nihilo generation [START_REF] Offe | Designing Institutions for East European Transition[END_REF][START_REF] Hall | Political science and the three new institutionalisms[END_REF][START_REF] March | The institutional dynamics of international political orders[END_REF]. Actors build upon, work around, combine, reinvent and reinterpret logics and institutional arrangements that either function elsewhere or with which they are familiar. This goes, we propose here, for institution building in the transnational space.

Within the context of nation-states, the creation of new institutions is likely to be influenced by the existing institutional environment. Interests and identities of social actors that engage in institution building, coalitions and conflicts between groups with similar and competing interests as well as the cognitive templates that actors use are shaped by the preexisting sets of institutional arrangements in which those groups of actors inscribe themselves. The state, in the form of political actors or agencies, does play a particularly significant role in that process of institution building at the societal level [START_REF] Clemens | Politics and institutionalism: explaining durability and change[END_REF] but this should not blind us to the impact and significance of other actors.

A lot of these features translate, we argue, at the transnational level. Institution building in the transnational sphere brings in a multiplicity of actors or groups of actors. The interests and identities of those actors, their characteristic patterns for entering conflicts and coalitions as well as the cognitive templates that define them, reflect to a great extent the preexisting institutional arrangements in which they set themselves. Very often, those have a societal or national character (Morgan 2001a, b). Hence a number of national actors extend their national contextual rationalities into the international sphere and through their repeated interactions they become involved in institution building in a newly emerging transnational sphere (see for examples McNichol and Bensedrine or Ventresca et al. in this volume). Or they may become involved in reforming, renegotiating and changing existing international institutional arrangements as motivations, power relations and conditions change over time (see Lilja and Moen or Lehmkuhl in this volume).

Through time, repeated interactions and the building up of a transnational frame, actors are emerging that have transnational -in the sense of not purely national -identity and sense of selves. Hence the interplay between well known national structures and logics and more emergent transnational patterns and rationalities is a key direction for institutional analysis. This is a path on which we engage in this volume.

The Missing Links -Institutionalization as a Process in the Transnational Space

We have proposed above to talk about institutionalization as a process rather than about institutions. And building upon the work of [START_REF] Tolbert | The institutionalization of institutional theory[END_REF] we have differentiated between three moments -that fit in fact on a continuum and are not discrete or separate stages. This differentiation between moments of habitualization, objectification and sedimentation is particularly valuable, we believe, for looking at institution building in the transnational space. And a focus on institutionalization as a process rather than on institutional systems also makes particular sense when looking at the transnational space.

Such a perspective makes it possible to overcome the limits and shortcomings that are characteristic of existing debates. A first and quite significant advantage is that this perspective makes it possible to navigate between the Charybdis of under-determination and the Scylla of over-determination. The literature on and around the transnational arena has tended to cluster at two extremes.

On the one hand, the mainstream of the International Relations (IR) tradition pictures the transnational space as essentially anomic -a shapeless and structureless arena. Agents are essentially free and rational, maximizing their own interests with little burden being put on them by the space in which their action takes place. Krasner (1999, p. 72), for example, in his recent book on sovereignty still questions the impact of institutions in the international sphere and argues that in this sphere a logic of consequence usually will prevail over a logic of appropriateness (see also [START_REF] Gilpin | The Challenge of Global Capitalism[END_REF]. Other writers, such as Ruggie (1993[START_REF] Ruggie | Constructing the World Polity. Essays on International Institutionalization[END_REF], have given more weight to international organizations and drawn a more complex picture of the interdependencies between domestic and international power structures. Heterodox writers within the IR tradition go even further by directing attention to the structuration of social networks across borders. Neo-Gramscian scholars, in particular, focus on processes of transnational class formation and the emergence of 'historical blocks' of public and private authorities [START_REF] Cox | Gramsci, hegemony and international relations: an essay in method[END_REF][START_REF] Cox | Production, Power and World Order[END_REF]. Transnational social networks are regarded as central mechanisms through which ideologies and worldviews -and hence structures and institutions -enter in conflict and contradiction and hegemonies come and go (van der Pijl 1984[START_REF] Van Der Pijl | Transnational Classes and International Relations[END_REF].

On the other hand, cultural neoinstitutionalism -the one strand of institutional theory taking the transnational space seriously -has underscored the thickness and highly determining nature of the transnational institutional system. The transnational space is made up of a dense web of cultural rules and patterns, symbolic constraints that shape and determine organizations and structures but also social action and actors themselves. 'What actors do', in the words of key proponents of this theoretical perspective, 'is inherent in the social definition of the actor himself. The particular types of actors perceived by self and others and the specific forms their activity takes reflect institutionalized rules of great generality and scope' (Meyer et al. 1994, p.18). This volume will point to a path somewhere in between -where the web of institutional constraints is multilayered and in the making, malleable and changing. Actors are neither free, independent or discrete, nor fully and only rational in the classical sense. The idea of social networks is useful but what emerges once again is the multiplicity and multidirectionality of those networks as well as their undeniable embeddedness in multiple and more or less overlapping institutional frames.

Our perspective in this volume and our take in particular on institutionalization allows us to avoid another simplistic and extreme alternative. This alternative has to do with the type of 'rationality' that can be found within the transnational space. The clear opposition here is between the idea of a universal or global rationality -neutral and theoretical that would point in fact to something like the 'end of history' or to the 'best of all possible worlds' -and the conviction on the other hand that rationalities are plural and that when they express themselves in the transnational space they tend to reflect in fact national embedding institutional systems. National systems do emerge as important in shaping actors and organizations' rationalities, however we do not rule out the possibility for the emergence of transnational bases of rationalities, in the process of transnational institution building.

A number of heterodox writers situated between the two extremes of traditional International Relations and cultural neoinstitutionalism have identified elements of such processes of transnational institution building which can be integrated in our research agenda. What these authors find is an increasing blurring of border lines between political and private authority in the transnational sphere and increasingly overlapping 'spheres of authority' [START_REF] Rosenau | Along the Domestic-Foreign Frontier[END_REF] and 'webs of influence' [START_REF] Braithwaite | Global Business Regulation[END_REF]. These emerging transnational arenas of institution building are populated by increasingly multiple and heterogeneous groups of agents, ranging from multinational companies and other private corporate actors [START_REF] Stopford | Rival States, Rival Firms[END_REF][START_REF] Strange | The Retreat of the State. The Diffusion of Power in the World Economy[END_REF]Cutler et al. 1999) over representatives of social movements [START_REF] Held | Global Transformations[END_REF]Boli and Thomas 1999;[START_REF] O'brien | Contesting Global Governance. Multilateral Economic Institutions and Global Social Movements[END_REF] to the national political actors which prevail in traditional IR theory (for a critical review of the role of the latter actors in the project of building a European Union see Sandholtz and Stone Sweet 1998).

Finally, the perspective we propose makes it possible to avoid falling in the evolutionary trap. Institution building is not a simple and linear process. And this may be particularly true in the transnational space. The continuum of the three moments -habitualization, objectification and sedimentation -is analytically useful but only if it is not used and understood at face value. The fact that we can differentiate between those three moments does not (indeed, far from it) say that those three moments necessarily follow each other in a linear and systematic manner in real life. Nor does it say that there is an evolutionary and unavoidable path going from pre-institutionalization or habitualization to the full stabilization of institutional rules of the game. On the contrary, those three categories can allow us to think of circular paths, ruptures and discontinuities. Institution building in the transnational space proceeds at varied pace according to the 'layer' that we look at. Such institution building remains highly fragile, particularly during the first two moments, which makes ruptures, discontinuities or even backlashes highly possible. The kaleidoscope or multilayered nature of the institution building process in the transnational space also makes it possible and even likely that there will be shortcuts. Rather than starting from scratch and the progressive aggregation of and negotiation between behaviours, institution building in a particular layer can get inspiration from rules of the game and institutional patterns already stabilized in a neighbouring layer.

Trickle-up and Trickle-down Trajectories -Bridging Levels of Analysis

We have argued above that processes of de-institutionalization and re-institutionalization are particularly likely to emerge at the interface of national and transnational rule systems. We have made suggestions of how we could use this interface as a starting point for our exploration into globalization as a process of institutional building and institutional change, particularly looking at the confrontation between different national actors and between foreign and domestic, dominant and fringe players. But under which conditions do changes in actors' rule systems at the micro or subsocietal level become relevant for other areas and for higher order rules at the societal or even transnational level? And in which circumstances do changes in macro level rules -at the transnational or national level -diffuse to the micro level and become relevant for the behaviour of individual economic actors? Some of the debates and disagreements around the likelihood and degree of institutional emergence and change in relation to globalization can be explained by the fact that scholars place themselves at different levels of analysis without attempting to create a link. Whereas many studies of institutional change and institutional evolution are situated either at the organizational field level or at the transnational level, work that highlights stability and durability of institutions is predominantly focused on the nation-state level [START_REF] Knill | Seek and ye shall find!" linking different perspectives on institutional change', preprints of the Max-Planck-project team 'Recht der Gemeinschaftsgüter[END_REF]. In order to reconcile change with stability, we need a better understanding of how those different levels of institutionalization are linked together. We need to investigate the processes through which institutional change in particular subsocietal systems contributes to the transformation of higher level institutional orders -both at the national and transnational level -and vice versa.

With regard to institutional change within national societal spaces, two types of processes are important here. First, transnational institution building can effect upon national institutional systems directly, in a top-down way, leading dominant actors to redefine national regulations or other forms of institutionalized patterns of economic organization. The passing of a new European legislation relating to transport, for example, forced national governments, business corporations and trade associations within the different European member states to redefine their national rule systems and patterns of cooperation (see Plehwe with Vescovi in this volume). Secondly, transnational institution building can have also an indirect impact on national institutional systems if actors at the subsocietal level start to introduce new and challenging rules of the game. Cumulative changes of that type eventually lead to ambiguities and uncertainties that initiate bottom-up processes of change resulting in redefinitions of higher level rules and principles. Examples are initially 'minor' changes in the rules governing the French asset management industry (Kleiner in this volume) or in foreign investment in Finnish corporations (Tainio et al. in this volume) which in fact and together with other minor changes became a source of pressure on the wider national systems of corporate governance and elite production and reproduction.

These two forms of institutional change are what we will refer to as trickledown and trickle-up trajectories in the conclusion to this volume. Building on the empirical contributions that make up this volume, we will propose in this last chapter a more analytic and systematic description of those mechanisms linking changes in the international business environment to different forms of institutional change in national societal spaces. The focus here will be clearly on transnational institution building as trigger for national institutional change.

In turn, when analysing institution building in the transnational sphere, the national origins and components of this process should not be lost from sight. From this perspective, transnational institution building can be analysed as pro-cesses of reinterpretation, recombination and bricolage of institutional fragments from different contextual origins. We suggest that there are basically three different modes in which the rubbing, contestation and combination of different institutional fragments can take place at the transnational level.

In the dominant mode, the building of institutions at the transnational level simply reflects one dominant local or national model. This is illustrated by the diffusion of American economic rules such as the logic of 'shareholder value' through international financial market actors to other countries (see Tainio et al., Kleiner and McKenna et al. in this volume).

A second mode of transnational institution building is negotiation. In this case, institution building in the transnational sphere comes about as the result of confrontation, debate and bargaining between actors coming from different national rule systems. Examples are the negotiation of unified legal frameworks for specific sectors of economic activity within the European Union (see Plehwe with Vescovi and Midttun et al. in this volume) or the bargaining between the USA and the European Union leading to a multilateral agreement on labelling of genetically modified soy (see McNichol and Bensedrine in this volume).

A third form of transnational institution building is the emergent mode. It tends to involve actors with less clear, and often more transnational identities. It tends to take place at the borders of multiple rule systems and to be of a high complexity which makes outcomes rather unpredictable. These three modes will be, based on the empirical chapters of this volume, described in a more systematic manner in the conclusion.

Overall, we suggest that in order to understand the complexities involved in the link between globalization and institutions we should investigate more closely the interplay between transnational institution building and changes in national institutional systems. The interactions between these two types of processes over time can create a reinforcing cycle of institutional change and transnational institution building. With such an understanding of globalization, a lot of work still remains to be done. The contributions in this book represent attempts to study globalization from the conceptual viewpoint outlined above. They attempt to capture parts of the overall interplay between globalization as institutional change at the national level and globalization as institution building in the transnational sphere. They do this by focusing on specific sectors, countries, points and periods in time. Whereas contributions in Part I analyse how globalization has become a trigger for institutional change within the national space, contributions in Part II analyse processes of insitutionalization in the transnational sphere. Taken together, the contributions to this volume provide rich evidence for the repeated, and often mutually reinforcing, interactions between institutional change at the national and institution building at the transnational level.

Table 1 :

 1 Towards a Typology of Institutional Arguments

		'Rational choice'	'Cultural'	'Historical'
		institutionalism	institutionalism	institutionalism
	Definition of	Formal and structural	Wider cultural and	Formal and structural
	institutions	economic and	symbolic patterns	political, legal,
		political frames		societal frames
				backed up by
				coercive mechanisms
	Origins	Rational interest of	Long-term evolution	Nationally-shaped
		actors, calculus	-external reality	path dependencies -
				external reality
	Logic of action	Rational interest of	Appropriateness	Constraint
		actors, calculus

Table 2 :

 2 Actors of Change -Foreign or Domestic, Dominant or Fringe

		Domestic	Foreign
	Dominant	Resistant/Driving Force	Missionaries
	Fringe	Activists/Agitators	Absent


Changjiang Gou

Anne Benoit

Loris Marchal

Memory-aware tree partitioning on homogeneous platforms

I. INTRODUCTION

Parallel workloads are often modeled as directed acyclic graphs of tasks. In this paper, we aim at scheduling some of these graphs, namely rooted tree-shaped workflows, onto a set of homogeneous computing platforms, so as to minimize the makespan. Such tree-shaped workflows arise in several computational domains, such as the factorization of sparse matrices [START_REF] Davis | Direct Methods for Sparse Linear Systems[END_REF], in computational physics code modeling electronic properties [START_REF] Lam | Memory-optimal evaluation of expression trees involving large objects[END_REF], or in sparse linear algebra [START_REF] Liu | The role of elimination trees in sparse factorization[END_REF]. The nodes of the tree typically represent computation tasks and the edges between them represent dependencies, in the form of output and input files. In this paper, we consider out-trees, where there is a dependency from a node to each of its child nodes, but the case of in-trees is similar. For such out-trees, each node (except the root) has to receive an input file from its parent and produces a set of output files (except leaf nodes), each of them being used as an input by a different child node. All its input file, execution data and output files have to be stored in local memory during its execution. The input file is discarded after execution, while output files are kept for the later execution of the children.

The way the tree is traversed influences the memory behavior: different sequences of node execution demand different amounts of memory, and memory optimal traversals have been proposed [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF], [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. The problem of scheduling such a tree on a single processor with limited memory is also discussed in [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]: in case of memory shortage, some input files need to be moved to a secondary storage (such as a disk), which is larger but slower, and temporarily discarded from the main memory.

We focus here on a homogeneous multi-processor platform and aim at partitioning the tree and mapping different subtrees on different processors, each having its own private memory. Hence, we are able to both reduce memory requirement and to improve the processing time (or makespan) by doing some processing in parallel. However, this incurs communication costs, which may be non negligible.

II. MODEL

We consider a tree-shaped task graph τ , where the nodes of the tree, numbered from 1 to n, correspond to tasks, and the edges correspond to precedence constraints among the tasks. The tree is rooted (node r is the root, where 1 ≤ r ≤ n), and all precedence constraints are oriented towards the leaves of the tree. A precedence constraint i → j means that task j needs to receive a file (or data) from its parent i before it can start its execution. Each task i in the rooted tree is characterized by the size f i of its input file, and by the size m i of its temporary execution data (and for the root r, we assume that f r = 0). A task can be processed by a given processor only if all the task's data (input file, output files, and execution data) fit in the processor's currently available memory. The memory requirement of task i is thus MemReq(i) = f i +m i + j∈children(i) f j , where children(i) are the children nodes of task i in the tree.

Task i can be executed once its parent, denoted parent(i), has completed its execution, and the execution time for task i is w i , if it fits in memory. If the whole tree fits in memory and is executed sequentially, the execution time, or makespan, is n i=1 w i . In this case, the task schedule, i.e., the order in which tasks of τ are processed, plays a key role in determining how much memory is needed to execute the whole tree in main memory. When tasks are scheduled sequentially, such a schedule is a topological order of the tree, also called a traversal. One can figure out the minimum memory requirement of a task tree τ and the corresponding traversal using the work of Liu [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF] or some of the authors' previous work [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. We denote by MinMemory(τ ) the minimum amount of memory necessary to complete task tree τ .

The target platform consists of p identical processors, each equipped with a memory of size M . The aim is to benefit from this parallel platform both for memory, by allowing the execution of a tree that does not fit within the memory of a single processor, and also for makespan, since several parts of the tree could then be executed in parallel. The goal is therefore to partition the tree workflow τ into k ≤ p connected subtrees τ 1 , . . . , τ k , which can be each executed within the memory of a single processor, i.e., MinMemory(τ ) ≤ M , for 1 ≤ ≤ k. We are to execute such k subtrees on k processors. Let root(τ ) be the task at the root of subtree τ . If root(τ ) = r, the processor in charge of tree τ needs to receive some data from the processor in charge of the tree containing parent(root(τ )), and this data is a file of size f root(τ ) . This can be done within a time

f root(τ ) β
, where β is the available bandwidth between each couple of processors. We denote by alloc(i) the set of tasks included in subtree τ rooted in root(τ ) = i, and by desc(i) the set of tasks that have a parent in alloc(i): desc(i) = {j | parent(j) ∈ alloc(i)}. The makespan can then be expressed with a recursive formula. Let M S(i) denote the makespan required to execute the whole subtree rooted in i, given a partition into subtrees. Note that the whole subtree rooted in i may contain several subtrees of the partition (it is τ for i = r). The goal is hence to express M S(r), which is the makespan of τ . We have M S(i) = fi β + j∈alloc(i) w j + max k∈desc(i) M S(k). We assume that the whole subtree τ is computed before initiating communication with its children. The goal is to find a decomposition of the tree into k ≤ p subtrees that all fit in the available memory of a processor, so as to minimize the makespan M S(r): Definition 1 (MINMAKESPAN). Given a task tree τ with n nodes, a set of p processors each with a fixed amount of memory M , partition the tree into k ≤ p subtrees τ 1 , . . . , τ k such that MinMemory(τ i ) ≤ M for 1 ≤ i ≤ k, and the makespan is minimized.

In the companion research report [START_REF] Benoit | Memory-aware tree partitioning on homogeneous platforms[END_REF], we establish the problem complexity with the following theorem. Its proof relies on a sophisticated reduction from the Partition problem.

Theorem 1. The (decision version of) MINMAKESPAN problem is NP-complete.

III. HEURISTIC STRATEGIES

In this section, we design polynomial-time heuristics to solve the MINMAKESPAN problem. The pseudo-codes and more detailed descriptions are available in the companion research report [START_REF] Benoit | Memory-aware tree partitioning on homogeneous platforms[END_REF].

A. Tree partitioning without memory constraints

In this section, we focus on the case where MinMemory(τ ) ≤ M , i.e., it is possible to process the whole tree on a single processor without exceeding the memory constraint. The objective is to split the tree into a number of subtrees, each processed by a single processor, in order to minimize the makespan.

We first consider the case where the tree is a linear chain, and prove that its optimal solution uses a single processor.

Lemma 1. Given a tree τ such that all nodes have at most one child (i.e., it is a linear chain), the optimal makespan is obtained by executing τ on a single processor, and the optimal makespan is n i=1 w i . Proof. If more than one processor is used, all tasks are still executed sequentially because of dependencies, but we further need to account for communicating the f i 's between processors. Therefore, the makespan can only be increased.

More generally, if the decomposition into subtrees form a linear chain, then the subtrees must be executed one after the other and no parallelism is exploited, so that the makespan can only be increased compared to executing the whole tree on a single processor.

1) Two-level heuristic: The first heuristic, SplitSubtrees, builds upon Lemma 1 and creates a two-level partition with a set of nodes executed sequentially, and a set of subtrees that can all be executed in parallel, so that we do not have any linear chain of subtrees. A similar idea was proposed in [START_REF] Eyraud-Dubois | Parallel scheduling of task trees with limited memory[END_REF], where the goal was to reduce the makespan while limiting the memory in a shared-memory environment. SplitSubtrees adapts these ideas to the present model, which includes communications. 2) Improving the SplitSubtrees heuristic: There are two main limitations of SplitSubtrees. First, it produces only a "two-level" solution: in the provided decomposition, all subtrees except one are the children of the subtree containing the root. In some cases, it is beneficial to split the tree into more levels. We thus designed a variant ImprovedSplitV1, which builds a multi-level solution. From the solution of SplitSubtrees, it tries to split again each of the children subtrees. To do this, it either uses processors initially left idle, or processors devoted to small subtrees that are then put back into the sequential set. It then outputs the solution that decreases the most the makespan.

The second limitation is the possibly too large size of the first subtree, containing the sequential set. As its execution is sequential, it may lead to a large resource waste. ImprovedSplitV2 attempts to overcome this limitation by removing the largest subtree from the solution, and iteratively calling SplitSubtrees on the remaining trees. Thus, the initial sequential set can be split again into a number of subtrees.

3) ASAP heuristic (as soon as possible): The main idea of this heuristic is to parallelize the processing of tree τ as soon as possible, by cutting edges that are close to the root of the tree. ASAP uses a node priority queue P Q to store all the roots of subtrees produced. Nodes in P Q are sorted by nonincreasing W i , where W i is the total computation weight of the subtree rooted at node i. Iteratively, it cuts the largest subtree, until there are as many subtrees as processors. Therefore, it is able to create a multi-level partition of the tree.

We also introduce a variant of the ASAP heuristic, named ASAPc10, which puts in P Q not only the children of the node that was selected as the root of a subtree the latest, but also all its descendants up to a depth of 10. All these nodes are candidates to be selected as subtree's root, and are sorted by non-increasing values of W i -fi β . Here, we take into account the communication cost, as it corresponds to the gain of moving this subtree to another processor (we remove some computation from the tree, but add a communication cost). At each step, the best candidate in this set is selected to become the root of a new subtree. The value of 10 was selected as it seems a good tradeoff between performance and running time, but this heuristic can be generalized for any depths.

4) Avoiding chains of subtrees: The tree in Figure 1 provides an example in which ASAP cuts four edges (edges between red nodes) and maps each subtree to one processor. Node labels represent their subtree computational weight, all edges have weight 10, and p = 6. Compared to executing the tree on one processor, the parallel executing scheme from ASAP costs more due to the communication between processors. We are hence looking for chains in the quotient tree, where vertices from a same subtree are represented by a single vertex, and dependencies are added in the quotient tree if and only if there is a dependency between two of the original nodes.

We propose an algorithm to avoid this shortcoming, called AvoidChain. We first build the quotient tree and look for chains in it. The subtrees of a chain are then merged into a single subtree, which leaves some processors idle. These idle processors can then be used to improve the makespan thanks to Algorithm LarSav, as explained below.

5) Increasing the number of subtrees: If the number of subtrees is smaller than the number of processors, we can further reduce the makespan by repartitioning subtrees. Given a tree τ and a partition C, LarSav first builds the quotient tree, and finds its critical path, which defines the makespan of τ . All subtrees on the critical path, except leaves of the quotient tree, are candidates to be cut into two parts. For each subtree that is a leaf in the quotient tree, we try to cut its two largest children, which avoids producing a chain. We iteratively select the subtrees and the corresponding splittings that reduce the most the makespan. We repeat this process until no more idle processor is left, or when the makespan stops decreasing. We select the solution that gives the largest savings in makespan.

B. Tree partitioning with memory constraints

We now move to the general case where the memory needed to process the whole tree, MinMemory(τ ), is larger than the available memory M . Again, we want to partition the tree so as to minimize the makespan. We consider two-step heuristics: (Step 1) We first partition the tree into k subtrees so that each of these fits in the local memory; k should not be larger than the number of processors p, otherwise we fail to find a solution; (Step 2) Then, if k < p, we try to make use of the remaining (p -k) processors to reduce the makespan, by repartitioning some of the subtrees obtained in Step 1. We first present three heuristics for Step 1, and then move to Step 2.

1) Partitioning trees for the memory: We first note the proximity of this problem with the MINIO problem [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. In this problem, a similar tree has to be executed on a single processor with limited memory. When the memory shortage happens, some data have to be evicted from the main memory and written to disk. The goal is to minimize the total volume of the evicted data while processing the whole tree. In [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF], six heuristics are designed to decide which files should be evicted. In the corresponding simulations, the FirstFit heuristic demonstrated better results. It first computes the traversal (permutation σ of the nodes that specifies their execution sequence) that minimizes the peak memory, using the provided MINMEMORY algorithm [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. Given this traversal, if the next node to be processed, denoted as j, is not executable due to memory shortage, we have to evict some data from the memory to the disk. FirstFit orders the set S = {f i1 , f i2 , . . . , f ij } of the data already produced and still residing in main memory, so that f i1 is the data that will be used for processing the latest, and selects the first data from S until enough memory has been freed. We consider the simple adaptation of FirstFit to our problem: the final set of data F that are evicted from the memory defines the edges that are cut in the partition of the tree, thus resulting in |F | + 1 subtrees. This guarantees that each subtree can be processed without exceeding the available memory, but not that the number of subtrees is smaller than p.

It seems natural to minimize the number of subtrees in Step 1, as we deal with makespan minimization possibly by repartitioning subtrees, in Step 2. Thus, we propose a variant of the FirstFit strategy, which orders the set S of candidate data to be evicted by non-increasing sizes f i , and selects the largest data until their total size exceeds the required amount. This heuristic is called LargestFirst.

Finally, we propose a third and last heuristic to partition a tree into subtrees that fit into memory. As for the previous heuristic, we start from a minimum memory sequential traversal σ. We simulate the execution of σ, and each time we encounter a node that is not executable because of memory shortage, we cut the corresponding edge and this node becomes the root of a new subtree. We continue the process for the remaining nodes, and then recursively apply the same procedure on all created subtrees, until each of them fit in memory. This heuristic is called Immediately.

2) Optimizing a partition for makespan: When there are no more subtrees than processors, we first attempt to slightly modify this partition using heuristic Upper. The main idea is to reduce the workload of the sequential part, that is, the subtree that contains the root of the tree, since no other subtree can be executed simultaneously. For this purpose, we start by the subtree containing the root and look for its children in the quotient graph. We order these children by increasing makespan, so as to start with the less loaded subtrees, and try to grow the corresponding subtrees by including its parent. We iteratively repeat this process until the memory needed for the updated subtree is larger than the bound M , or until we create some dependency with another child. We then select the extension of the current subtree that reduces the most the makespan, before trying to grow other subtrees. All children subtrees are then put in the list of candidate subtrees to be later considered for optimization, so that the optimization propagates from the top to the bottom of the tree.

Finally, note that it is also possible to apply the LarSav heuristic described earlier if there are additional processors available. However, all heuristics will fail if the heuristic used in Step 1 returns a partition requiring too many processors.

IV. EXPERIMENTAL VALIDATION THROUGH SIMULATIONS

We generated ten groups of trees, each one with 3,000 trees, whose size ranges from 1,000 to 6,000. The maximum number of children of a node (called "maximum degree" in the following) is constant in a given group and ranges from 4 to 22. The trees with smaller maximum degree are thus generally deeper but narrower than the ones with larger maximum degree. The sizes of the nodes' input data (f i ) follow a truncated exponential distribution with mean value 100, where the values smaller than 10 are removed. The execution time (w i ) of each node is randomly generated in the same way. We then set the size of execution file (m i ) as three times its input data size. We only consider trees whose MinMem is larger than its MaxOutDeg, others are discarded. Recall that MaxOutDeg = max 1≤i≤n (MemReq(i)), where MemReq(i) denotes the memory requirement of task i.

To compare the performance of the proposed heuristics in different environments, we have selected three different options for the number p of processors: it is equal to 1%, 10%, or 40% of the tree size n. We also consider three scenarios for the relative cost of computations vs. communications. Given a tree, we select the communication bandwidth β such that the average communication to computation ratio (CCR), defined as the total time of the computations divided by the total time for communicating all data, is either 1/16(= 0.0625), 1 or 16.

Due to lack of space, we do not detail results for the case without memory constraint, and we refer to the companion research report [START_REF] Benoit | Memory-aware tree partitioning on homogeneous platforms[END_REF]. Note that ASAPc10 generally performs better than the reference heuristic SplitSubtrees, except in the case of a too small number of processors (n/p = 100). Using LarSav on the solution produced by ASAPc10 allows us to further reduce the makespan. BestImprovedSplit allows us to reduce the makespan of SplitSubtrees, but only by a small factor. When communication is expensive (CCR = 16), ASAPc10 and LarSav are worse than SplitSubtrees: benefits from parallel execution are cancelled by communication costs. In other cases, SplitSubtrees is worse on more than half of the instances. We also find that the structure of trees does not have an obvious influence on the relative performance of heuristics.

In the memory-constrained case, the memory bound for each processor is set to the minimum memory needed to process any single task. This is thus a very strict scenario. The tree first has to be decomposed into some subtrees by either FirstFit, LargestFirst or Immediately such that none of them exceeds the bound M . The sequential subtree traversal is given by MinMem as described in [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. Each subtree is then mapped onto a processor. First, we compare how many subtrees these algorithms produced, since using less subtrees in this first phase leaves more room for makespan improvement in the second phase. FirstFit produces less subtrees, as shown in Figure 2a, and LargestFirst behaves almost the same on trees with a small maximum degree. So, FirstFit is the best heuristic that gives us a feasible partition when processors are limited.

Upper is designed to reduce the makespan without using more processors. Figure 2b shows that on average, it achieves only small makespan reductions, while it performs better on trees with larger maximum degree, especially for the partition built by Immediately. After Upper, LarSav can further reduce the makespan by using idle processors: 90% of processors are idle on at least 75% of the cases. Figure 2c shows that the makespan returned by LarSav is much smaller. In conclusion, FirstFit is the best option for computing a first partition, Upper and LarSav are then very helpful to reduce its makespan.

V. CONCLUSION

We have studied how to minimize the time required to compute a tree of tasks on a distributed computing platform with memory constraints. After proving the problem NPcomplete, we designed several heuristics. Extensive simulations demonstrate the efficiency of these heuristics and provide guidelines about the heuristic that should be used. Without memory constraints, using a combination of ASAPc10 and LarSav is the best choice in most settings, even though BestImprovedSplit may be useful with a few processors or expensive communications. With memory constraints, the combination of FirstFit with Upper and LarSav is the best choice.

Figure 1 :

 1 Figure 1: Example of a chain with ASAP.

  Number of subtrees produced by the heuristics, compared to FirstFit. LarSav further reduces the makespan (n = 0.10p).

Figure 2 :

 2 Figure 2: Performance of the heuristics with memory constraint.


Chloé Ollivier
email: chloe.ollivier@alumni.univ-avignon.fr

Yoann Lecomte

Konstantinos Chalikakis

Charles Danquigny

Christophe Emblanch

Naomi Mazzilli

Vulnerability mapping of a vast karst hydrosystem. Application and adjustments of PaPRIKa method to the Fontaine-de-Vaucluse catchment (France)

Keywords: Vulnerability mapping, PaPRIKa method, karst protection, Fontaine de Vaucluse catchment area

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Vulnerability mapping of a vast karst hydrosystem. Application and adjustments of PaPRIKa method to the Fontaine-de-Vaucluse catchment (France)

Abstract

The Fontaine-de-Vaucluse spring (south-eastern France) is one of the largest karstic spring in Europe, with an average discharge rate of 20m 3 s -1 . This spring is the unique outlet of a vast catchment area of about 1100km 2 . Since human activities and global changes increase the pressure on fresh water resources, such a large reservoir needs to be protected for future exploitations. The vulnerability assessment is therefore necessary to sustainable groundwater management. Mapping the vulnerability of Fontaine-de-Vaucluse catchment can guide the evolution of Human activities in order to preserve the groundwater quality.

The intrinsic vulnerability analysis refers to specific hydrogeological settings and highlights the characteristics of the hydrosystem that may increase the vulnerability [START_REF] Margat | Vulnérabilité des nappes d'eau souterraine à la pollution[END_REF]. Therefore contaminant properties are not considered in this analysis. The intrinsic vulnerability property is a dimensionless quantity relative to the studied area [START_REF] Vrba | Guidebook on mapping groundwater vulnerability[END_REF]. The multi-criteria method PaPRIKa has been developed for mapping the intrinsic vulnerability of karst hydrosystem [START_REF] Dörfliger | Cartographie de la vulnérabilité intrinsèque des aquifères karstiques[END_REF]. This method is based on four criteria namely the Protection (P), the Reservoir (R), the Infiltration (I) and the Karst features (Ka). Each criterion is mapped independently and classified into five indexes from lowest to highest vulnerability. The final vulnerability map is then calculated by combining the four criteria according to a weighting relation. Consequently, the larger is the catchment area, the more time consuming is the task.

This study aims to produce a vulnerability map of the Fontaine-de-Vaucluse catchment with PaPRIKa. The main challenge of applying PaPRIKa to such a vast catchment was to report qualitative information of the vulnerability at the local scale with a consistent representativeness at the regional scale. The extension of the catchment area implies also a larger range of possibilities for each parameter and each criterion and a huge database. For instance we have to deal with a wide range of altitudes (from 89 m to 1912 m a.s.l), a large range of mountain slopes (0 -90 • ), various carbonate formations (from marlstone to limestone), the thickness of carbonate series (more than 1500m including an unsaturated zone 750 m thick) and numerous soil types. All these parameters cause a large spectrum of hydrogeological environments and could justify adjustments of PaPRIKa method. As a consequence, a second challenge of the vulnerability mapping was to automate all phases in order to test and improve these method's adaptations. It enables also searching for the most consistent criteria weighting relationship and is less time consuming.

The whole catchment vulnerability map has been carried out. It is made of 4 vulnerability classes. Thus different hydrological environments can lead to a same class. The most vulnerable zones cover 2% of the area, including sinkholes and major faults. Indeed such features can act as a direct transfer zone towards the saturated zone. 45% of the catchment area has a high vulnerability index. These zones correspond mainly to highlands where the infiltration rate is high. An intermediate vulnerability index is attributed to 48% of the area, mainly corresponding to mountainsides. Finally, the lowest vulnerability index is attributed to 5% of the area mainly characterised by very steep slopes where infiltration rate is the lowest.

In conclusion, the PaPRIKa method has been successfully programmed and applied on a vast kart hydrosystem. The obtained distribution of vulnerability classes seems realistic and consistent at both scales, regional and local. At large scale the vulnerability map is globally linked with main geomorphological units. On the other hand, at the local scale the vulnerability map is mostly influenced by karst features that drive hydrodynamics. The vulnerability map provides a relevant support for resource management.

  Chloé Ollivier * a , Yoann Lecomte b , Konstantinos Chalikakis a , Charles Danquigny a , Christophe Emblanch a and Naomi Mazzilli a a Université d'Avignon et des Pays de Vaucluse -INRA, UMR1114 EMMAH, F-84914 Avignon, France b Syndicat Mixte du Bassin des Sorgues, 1 chemin des Palermes, 84320Entraigues-sur-la-Sorgue, France

	Eurokarst 2016
	5-7 September 2016