Matthieu Wipliez
email: mwipliez@insa-rennes.fr

Mickael Raulet
email: mraulet@insa-rennes.fr

Mickaël Raulet

CLASSIFICATION AND TRANSFORMATION OF DYNAMIC DATAFLOW PROGRAMS

Keywords: Dataflow Programming, Classification, RVC-CAL, Abstract Interpretation

published or not. The documents may come

INTRODUCTION

The arrival of multi-core in the desktop computing market has renewed the interest in multi-processor programming. There are many different techniques to write multi-processing programs, depending on memory architecture (shared or distributed), architecture (uniprocessor or multiprocessor), number of cores (single core, multi-core, many-core), etc. Most of these techniques constrain program design in a way that make it difficult to use a different technique, should the program be ported to a different architecture than initially planned. Dataflow programming is a portable platform-agnostic alternative that allows an algorithm to be described so that parallelism is made explicit.

A dataflow description consists in a directed graph where vertices (or actors) process data and edges carry data, with the requirement that vertices cannot share data. Actors can only communicate with other actors through ports connected to edges. The semantics of a dataflow program are defined by a Model of Computation (MoC) that dictates conditions for existence of a valid schedule, bounded memory consumption, proof of termination, and other properties. MoCs go from Synchronous Dataflow (SDF) with total compile-time predictability with respect to scheduling, memory consumption, termination, to dynamic dataflow where those properties are not predictable in the general case, with increasing expressiveness, for instance see [START_REF] Lee | Synchronous data flow[END_REF][START_REF] Bilsen | Cyclo-static dataflow[END_REF][START_REF] Bhattacharya | Parameterized Dataflow Modeling for DSP Systems[END_REF][START_REF] Buck | Scheduling dynamic dataflow graphs with bounded memory using the token flow model[END_REF][START_REF] Buck | Static scheduling and code generation from dynamic dataflow graphs with integer-valued control streams[END_REF][START_REF] Lee | Dataflow Process Networks[END_REF].

The Reconfigurable Video Coding (RVC) [START_REF] Mattavelli | The Reconfigurable Video Coding Standard [Standards in a Nutshell[END_REF] standard defines existing MPEG video standards as dynamic dataflow programs in which actors are written in a language called RVC-CAL. These dataflow programs can be automatically translated and ported to a wide range of platforms and languages, from hardware to multi-core software [START_REF] Mattavelli | The Reconfigurable Video Coding Standard [Standards in a Nutshell[END_REF]. Contrary to SDF and a few other MoCs, RVC-CAL has a much greater expressive power, but this also means that runtime scheduling is mandatory in the general case, which severely impacts execution speed.

Fortunately, most signal processing applications are far from being entirely dynamic, and parts with static behavior need not be dynamically scheduled. The problem is to detect actors that behave statically or quasi-statically, since dynamic dataflow has an expressive power equivalent to a Turing machine [START_REF] Buck | Scheduling dynamic dataflow graphs with bounded memory using the token flow model[END_REF], which means it is not possible to prove the termination of a dynamic dataflow program in general. This paper makes the following contributions:

• we present a method to automatically classify an actor as static, cyclo-static, or quasi-static (section 3). As shown on Fig. 1, classification is the first step towards high-performance implementation of dataflow programs. It is mandatory to allow other optimizations to take place.

• we describe an algorithm to transform actors classified as "not dynamic" to reduce scheduling overhead when executing those actors (section 4). The transformation we describe may be used to transform actors into other actors that will not only execute faster, but will also fa-cilitate the application of later optimizations. Indeed, actor merging consists of creating composite actors from several actors, and our transformation changes actors so that they can be merged more easily. The last optimization that can be used to achieve the maximum throughput for a dataflow application is multiprocessor mapping and scheduling techniques for statically schedulable subsets (for an example see [START_REF] Pelcat | An open framework for rapid prototyping of signal processing applications[END_REF][START_REF] Boutellier | Quasi-static scheduling of CAL actor networks for reconfigurable video coding[END_REF][START_REF] Gu | Exploring the concurrency of an MPEG RVC decoder based on dataflow program analysis[END_REF]).

BACKGROUND

Dataflow Programming with RVC-CAL

This section presents the model of the programs that we classify and transform. Formally, the dataflow programs we are dealing with are Dataflow Process Networks (DPNs) [START_REF] Lee | Dataflow Process Networks[END_REF]. DPNs are related to Kahn Process Networks (KPNs) [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] as both models contain blocks (processes in a KPN, actors in a DPN) that communicate with each other through unidirectional, unlimited FIFO channels. Reading from a FIFO is blocking (if a process or an actor attempts to read data from a FIFO and no data is available, it must wait), whereas writing to a FIFO is non-blocking, i.e. the write returns immediately.

Programs that respect one model or the other must be scheduled dynamically [START_REF] Lee | Dataflow Process Networks[END_REF][START_REF] Thomas | Bounded Scheduling of Process Networks[END_REF]. Contrary to Kahn processes, actors can test an input port for the absence or presence of data ; an actor need not be suspended when it cannot read, which in turn means that scheduling a DPN does not require contextswitching nor concurrent processes. MPEG has recently defined a standard called Reconfigurable Video Coding (RVC) [START_REF] Mattavelli | The Reconfigurable Video Coding Standard [Standards in a Nutshell[END_REF] to describe existing and future video standards with dataflow programming. A dataflow program consists of a hierarchical DPN where actors are defined with the RVC-CAL language, a Domain-Specific Language (DSL) for signal processing. An RVC-CAL actor may have input and output ports connected to FIFOs, parameters, state variables, functions and procedures, actions that may be identified by a tag, a Finite State Machine (FSM) whose tran-sitions reference tagged actions, and a set of priorities that establish a partial order between action tags.

Contrary to most non-dataflow languages, dataflow programs do not admit a single entry point. A dataflow network has one entry point per actor, which means the program may start from any actor in the network. The only entry points of an actor are its actions; functions and procedures can only be called by an action. An action computes data by reading tokens from input ports and writing tokens to output ports. The patterns of tokens read and written by a single action are called input pattern and output pattern respectively. Additionally an action has guards that must be true for an action to be executed. Apart from these specific features, the body of an action is like a procedure in most imperative programming languages, with local variables and imperative statements.

An actor is executed (or fired) by selecting a fireable action and firing it. An action is fireable iff: (1) the current FSM state allows the action to fire (or there is no FSM and this condition is always true), (2) there are enough tokens for the action to fire, (3) the guards of the action evaluate to true. Figure 2 shows an actor named "Clip" that performs a clipping operation. This operation is traditionally done in video decoders after an inverse Discrete Cosinus Transform to clip the values of pixels to a given interval. The actor has the following behavior. When a boolean token arrives on the SIGNED port, the read signed action fires, reads the token and stores it in the sflag state variable, and initializes a counter named count. The sflag variable configures the clip as signed if true and unsigned otherwise. At this point only the limit action can fire, regardless of whether there are tokens on the SIGNED port, because count is non-negative. Each time this action fires, it reads a token on I, decrements the counter, clips the value read to [-255, 255] in signed mode or to [0, 255] in unsigned mode, and outputs the clipped value on O. When count reaches -1, the cycle can start again.

Classification of an RVC-CAL Actor: An Example

Figure 3 shows the behavior of the "Clip" actor expressed with Cyclo-Static Dataflow (CSDF) [START_REF] Bilsen | Cyclo-static dataflow[END_REF]. Within this model, the number of tokens produced and consumed by an actor changes periodically according to a production/consumption sequence. For instance, the consumption sequence on IN has a zero followed by 64 ones: On its first invocation, the actor will not consume any token on the port, and for the next 64 invocations, it will consume one token on the port each time. The advantage of expressing an actor as CSDF is that it can be statically scheduled because the number of tokens the actor will consume and produce is known at compile-time. The problem is then how to classify actors into Models of Computation (MoCs) more constrained than dynamic dataflow so that as many actors as possible can be statically or quasi-statically scheduled.

SIGNED

A Taxonomy of Dataflow Models of Computation

This section presents a taxonomy of Models of Computation (MoCs) (Fig. 4) that can model the different types of behavior that actors can exhibit. The actors in the Video Tool Library of the RVC standard can behave statically, cyclo-statically, quasi-statically, or dynamically. We present the MoCs in the literature that are suitable to model these types of behaviors. Dataflow MoCs are defined as subsets of a general model called Dataflow Process Networks (DPNs). The taxonomy shown on Fig. 4 reflects the fact that MoCs are progressively restricted from DPN towards SDF with respect to expressiveness, but at the same time they become more amenable to analysis. We first study the rules of DPN, and then present the models that can be used to model static, cyclo-static, quasistatic, and dynamic RVC-CAL actors.

Dataflow models respect the semantics of DPNs: A dataflow model is a directed graph whose vertices are actors and edges are unidirectional FIFO channels with unbounded capacity, connected between ports of actors. Each FIFO channel carries a sequence of tokens. Executing a DPN boils down to executing repeatedly the actors in the graph, possibly ad infinitum. An actor executes (or fires) when at least one of its firing rules is satisfied. Each firing may consume and produce tokens. An actor can have N firing rules, where each one represents an acceptable sequence of tokens. Additionally an actor has a firing function that takes a sequence of tokens and produce a sequence of tokens.

Synchronous Dataflow (SDF) [START_REF] Lee | Synchronous data flow[END_REF] is the least expressive DPN model, but it is also the model that can be analyzed more easily. Schedulability and memory consumption of SDF graphs can be determined at compile-time, and algorithms exist that can map and schedule SDF graphs onto multiprocessors in linear time with respect to the number of vertices and processors [START_REF] Pelcat | An open framework for rapid prototyping of signal processing applications[END_REF]. Any two firing rules of an SDF actor must consume the same amount of tokens, and all firings must produce the same amount of tokens on the output ports. This definition is actually included in Lee's denotational semantics for SDF [START_REF] Lee | Dataflow Process Networks[END_REF], which states that SDF actors have a single firing rule. Our definition simply allows SDF actors to have several firing rules as long as they have the same production/consumption rate, which in practice makes it easier to describe SDF actors that have data-dependent computations.

Cyclo-static Dataflow (CSDF) [START_REF] Bilsen | Cyclo-static dataflow[END_REF] extends SDF with the notion of state while retaining the same compile-time properties concerning scheduling and memory consumption. State can be represented as an additional argument to the firing rules and firing function, in other words it is modeled as a self-loop. Contrary to the RVC-CAL version of "Clip", the state of the CSDF version does not contain the sflag variable because it is not taken into account in firing rules, instead it only consists of the value of the count variable that holds the number of values processed so far.

Synchronous and cyclo-static dataflow allow signal processing algorithms to be modeled as graphs with fixed production/consumption rates. On the other hand, so-called "quasi-static" graphs can be used to describe data-dependent token production and consumption. Quasi-static dataflow differs from dynamic dataflow in that there are techniques that statically schedule as many operations as possible so that only data-dependent operations are scheduled at runtime [START_REF] Bhattacharya | Parameterized Dataflow Modeling for DSP Systems[END_REF][START_REF] Buck | Scheduling dynamic dataflow graphs with bounded memory using the token flow model[END_REF][START_REF] Boutellier | Quasi-static scheduling of CAL actor networks for reconfigurable video coding[END_REF]. We chose to use the PSDF [START_REF] Bhattacharya | Parameterized Dataflow Modeling for DSP Systems[END_REF] model as a target for our classification because it can be used to model static, cyclo-static and quasi-static behavior as a dataflow graph. RVC-CAL places no restrictions whatsoever about the firing rules nor firing function of an actor. An RVC-CAL actor can thus have a behavior that is data-independent and stateindependent, cyclo-static state-dependent, quasi-static datadependent, or data-dependent and state-dependent (dynamic). The RVC-CAL language extends the DPN MoC by adding a notion of guard to firing rules. Formally the guards of a firing rule are boolean predicates that may depend on the input patterns, the actor state, or both, and must be true for a firing rule to be satisfied.

AUTOMATIC CLASSIFICATION OF DYNAMIC DATAFLOW ACTORS

This section presents the first contribution of this paper: A method to automatically classify dynamic dataflow actors into more restricted dataflow Models of Computations. Classification is a prerequisite for the transformations presented in section 4 and actor merging. We first present how the classification method can detect actors that it cannot classify and discard them.

Detection of Unclassifiable Actors

DPN places no restrictions on the description of actors, and as such it is possible to describe a time-dependent actor in that its behavior depends on the time at which tokens are available. This happens in RVC-CAL when a given action reads tokens from input ports not read by a higher-priority action, and these actions have guards that are not mutually exclusive. The "Clip" actor presented section 2 has a time-dependent behavior. If you read the description carefully, you will notice that the limit action can fire as long as there tokens on IN and not on SIGNED, therefore potentially clipping pixels before clipping mode is set by read signed. In this particular case, this behavior is a flaw in the implementation of the actor itself, although it may never cause any problems if the actors connected to it always send a token on the SIGNED port first. In other cases, time-dependent behavior can be useful as a low-level optimization by allowing an actor to test for the absence of data and still do something useful when that is the case. Time-dependent behavior can be removed in some cases simply by making guards mutually-exclusive, which in our example translates to rewriting the limit action as presented in Fig. 5.

Classifying a time-dependent actor may be intractable or impossible depending on the kind of actor. This kind of actor cannot be classified as SDF by definition (because actions of an SDF actor have the same token production/consumption rate), but it could still be considered a valid cyclo-static or quasi-static actor, in which case we would need to record the sequences of tokens that lead to this cyclo-static or quasistatic behavior. The intractability of classifying such an actor lies just there, since an automatic classification algorithm limit: action I:[i] ==> O:[ if i > 255 then 255 else if i < min then min else i end end ] var int min = if sflag then -255 else 0 end guard count >= 0 // mutually exclusive with read_signed do count := count -1; end Fig. 5. The limit action rewritten in a time-independent way. would need to explore all the possible input patterns with no criterion as to when to stop the enumeration of possible tokens.

Therefore our classification method must detect and discard time-dependent actors to prevent enumerating the universe of possible token sequences. Detecting actions that read input ports not read by higher-priority actions is trivial. However, such actions may not render the actor time-dependent if their guards are exclusive, which must be mechanically verified. To this end we feed the guards to a constraint solving system, which either gives the values of tokens and state variables that satisfy both guards (guards not mutually exclusive), or else finds no solution (guards mutually exclusive).

Constraints are created from the guards of an action as follows. The guards of an action are boolean expressions that must be simultaneously true for the action to be fired, so we translate each guard of any two actions to a constraint. Suppose an action has a guard x > 0 and the other action has a guard x = 1, then the constraint solver will find values of x that satisfy the constraints, such as x = 2. If there is such a solution, this means the guards are not mutually exclusive.

Abstract Interpretation of Actors

Classifying an actor within a MoC is based on checking that a certain number of MoC-dependent rules hold true for any execution of this actor. Some of these rules are verified solely from the structural information of the actor, for instance the rules for a static actor only depends on the input and output patterns of actions. In more complicated cases, we need to be able to obtain information from an actual execution. The actor must be executed so that the information obtained is valid for any execution of the actor, whatever its environment (the values of the tokens and the manner in which they are available). As a consequence it is not possible to simply execute the actor with a particular environment supplied by the programmer. To circumvent this problem we use abstract interpretation [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF].

Abstract interpretation consists in doing the computations performed by a program in an abstract universe of objects rather than on concrete objects. Our abstract interpretation of an actor has the following properties:

• The set of values that can be assigned to a variable is

V alues = Z ∪ {true, false} ∪ {⊥}
The value ⊥ is used for variables whose value is unknown, e.g. for uninitialized variables.

• The environment is defined as an association of variables and their values:

Env : Idents → V alues
Env initially contains the state variables of the actor associated with their initial value if they have one, otherwise with ⊥.

• When the interpreter enters an action, the environment is augmented with bindings between the name of the tokens in the input pattern and ⊥. In other words, a token read has an unknown value by default.

The abstract interpreter interprets an actor by firing it repeatedly until either one of the conditions is met:

1. The interpreter is told to stop because analysis is complete as determined by the classification algorithm.

2. The interpreter cannot compute if an action may be fired because this information depends on a variable whose value is ⊥.

To fire the actor, the interpreter starts by selecting one fireable action, that is an action that meets the criteria defined section 2.1. The abstract interpretation of an RVC-CAL actor is the same as its concrete interpretation with the following exceptions. Any expression that references a variable v where Env(v) = ⊥ has the value ⊥. Conditional statements and loops that test an expression whose value is ⊥ are not executed. However, guards evaluated as ⊥ cause the abstract interpreter to stop as per condition 2.

Classification of a static actor

Classification tries to classify each actor within models that are increasingly expressive and complex. The rationale behind this is that the more powerful a model, the more difficult it is to analyze. If an actor cannot be classified as a static actor, the method will try to classify it as cyclo-static, and then as quasi-static. An actor is classified as static iff it conforms to the SDF MoC, which means that all its actions have the same input and output patterns. A one-action actor is by definition static.

Classification of a cyclo-static actor

The conditions an actor must meet to be a candidate for classification as cyclo-static are two-fold: (1) it must have a state, hereinafter noted S, and (2) there must be a fixed number of data-independent firings that depart from the initial state, modify the state, and return the actor to its original state S 0 . We consider two kinds of actor state:

1. S consists of a set of scalar state variables and their runtime value. A state variable belongs to S iff it has an initial value and is used in at least one guard expression. S 0 is the set of variables of S with their initial value. Non-scalar variables (arrays) are not taken into account because state is typically not implemented with them. A full cycle is found when at least one action has been executed, and S = S 0 is true.

2. In the case where S = ∅ and the actor does not have an FSM, it is considered to have no state and therefore cannot be classified as cyclo-static. Otherwise the state consists of the current FSM state, and S 0 is the initial state s 0 of the FSM: S 0 = s 0 . If there is no path that returns S to S 0 , the actor cannot be classified as cyclostatic.

Once the classification algorithm finds the actor to be a valid cyclo-static candidate, we use the abstract interpreter presented section 3.2 until we find that the actor has returned to its original state, or the abstract interpreter stops because of data-dependent behavior. When the actor has returned to its original state, the algorithm stores the sequence of actions that fired, as well as the production and consumption of tokens on each port of the actor.

Classification of a quasi-static actor

A quasi-static actor is informally described as an actor that may exhibit distinct static behaviors depending on a datadependent condition. Our classification method is restricted to classify the subset of quasi-static actors considered by Boutellier et al. [START_REF] Boutellier | Quasi-static scheduling of CAL actor networks for reconfigurable video coding[END_REF] and defined as follows. A quasi-static must have an FSM whose initial state s 0 has transitions to n branches (n ≥ 2), the i th branch starting with state s i .

Each transition from s 0 to s i must be solely dependent on a control token; s 0 may have a cycle, which simply consumes one control token and returns the actor to the initial FSM state. Self-loops and cycles more generally are allowed within a branch, and so are cross-branch transitions, as long as all branches go back to the initial state.

The first step of the classification of an actor as quasistatic is to assert it has an FSM that respects the aforementioned conditions. This is done simply by examining each successor s i of the initial state s 0 , and checking that there is a path from s i back to s 0 . This criterion alone does not qualify the actor as quasi-static, it merely discards candidates that cannot be quasi-static.

The second step of the classification consists in checking that each branch fires a fixed number of data-independent firings and returns to the initial state: 1. for each branch i, find a value that satisfies the condition to take branch i but not any branch before it. We use constraint solving to automatically find a satisfying value.

2. use the abstract interpreter by taking branch i and firing the actor until it goes back to the initial state, or the abstract interpreter stops because of data-dependent behavior.

Taking branch i is done by making the interpreter return the concrete value computed in step 1 instead of ⊥ when the control port is read. It is important that the abstract interpreter only provide the concrete value once. Indeed, in some FSMs there may be more than one conditional state, i.e. more than one state being conditioned by the control port. We could probably further narrow the subset of acceptable actors with this criterion, but this is not necessary since the abstract interpreter will identify the transitions departing from a conditional state different from s 0 as data-dependent.

TRANSFORMATION OF CLASSIFIED ACTORS

This section presents the second contribution of this paper: A method to automatically transform actors that were classified as static, cyclo-static, or quasi-static, to higher-level SDF and PSDF graphs. This transformation improves execution speed of the resulting actors, and makes merging actors of the same kind easier.

Transformation to SDF and PSDF

The classification of actors gives information about the sequence of actions that were fired:

• in the case of static behavior, there may only be one action by definition; actors that have several actions with similar input/output patterns must be transformed to single-action actors.

• in the case of cyclo-static behavior, the sequence is a list of actions with fixed production/consumption rates that start from an initial state and eventually return to this initial state.

• in the case of quasi-static behavior, there are several sequences of actions; each sequence is a concatenation of a first conditional action and a sequence of actions with fixed production/consumption rates.

To allow actors to be merged later, these sequences must be transformed to respect appropriate MoCs. They can be trivially transformed from cyclo-static to CSDF and from quasi-static to PSDF, by transforming an action invocation to a vertex and setting production and consumption to zero on every edge (since the actions do not consume the data of one another). However, this kind of graphs cannot be easily manipulated or optimized. The graphs do not represent the behavior of the actors; they are not suitable for merging, in particular merging SDF graphs together when each graph is composed of up to a few hundred vertices can quickly result in huge graphs, especially if the repetitions of vertices are not multiple of one another (see [START_REF] Lee | Synchronous data flow[END_REF] for additional explanations); the graphs cannot be efficiently mapped and scheduled because optimally scheduling a SDF graph is an NP-complete problem [START_REF] Pelcat | An open framework for rapid prototyping of signal processing applications[END_REF].

A better representation is a graph where a sequence of actions is transformed to a single higher-level action that fires all the actions in the sequence consecutively, this way edges can carry the proper production/consumption rates and the graph accurately represents the actor's behavior. The contents of higher-level actions can be factorized with loop rerolling.

Loop rerolling is the exact opposite of the well-known loop unrolling transformation. It has been used by Stitt and Vahid to recover loop structures from compiled code [START_REF] Stitt | New decompilation techniques for binary-level co-processor generation[END_REF]. In the context of this work, we used this transformation to find loops of actions within an initially flat sequence of actions. Loops are rerolled in two steps. First, we must recognize common sequences within an input sequence. Then, loops can be formed around consecutive repetitions of common sequences.

We used the Sequitur [START_REF] Nevill-Manning | Identifying hierarchical structure in sequences: A linear-time algorithm[END_REF] algorithm to recognize common sequences of actions from the initially flat list of actions. Sequitur works by deriving a hierarchical structure in the form of a Context-Free Grammar from a sequence of symbols. For instance the grammar G 1 derived from the sequence of symbols ababc is: S → A A c, A → a b.

To obtain loops from the hierarchical structure, we walk through the hierarchical structure by counting the number of rule invocations and developing the rules. For instance, suppose we have a sequence1 composed of four repetitions of a sub-sequence composed of five as followed by three bs, noted 4(5(a) 3(b)). The corresponding grammar is transformed so that we group consecutive actions together, which gives us 5(a) 3(3(b) 5(a)) 3(b). Sequitur works in linear time, so the hierarchical structure it derives is not optimal, which explains why the result is not minimal in terms of number of loops.

Optimization of Action Scheduler

Before classification, all actors are considered dynamic. This means that to fire an action an action scheduler must check that there are enough tokens in the input FIFOs and enough room in the output FIFOs, read tokens, compute data, and write tokens. After classification we know that some actors have a behavior that is static, cyclo-static, or quasi-static. As a consequence, we have information about the number of tokens and the room needed for several actions to fire, not just one.

A static actor is transformed to an actor with a single action, so it is not possible to reduce the number of read and write operations. Conversely, after loop rerolling cyclo-static actors have one high-level action, and quasi-static actors have n conditioned high-level actions. Those high-level actions act as static action schedulers: They fire sequences of actions, each action potentially reading and writing tokens. Since we know the number of firings that will occur, those reads and writes can be replaced by loads from/stores to arrays. For instance the limit action of "Clip" would be transformed as shown on Fig. 6. The A action is transformed as follows:

1. read data from each input port in a tokens port array 2. initialize each index port variable to zero

RESULTS

We have implemented the classification method and the transformation algorithm in the RVC-CAL compilation infrastructure supported by the Open RVC-CAL Compiler (Orcc) 2 . Orcc has a front-end that compiles RVC-CAL actors to an Intermediate Representation (IR) that retains structural information but lowers the RVC-CAL language to a simpler language in SSA form [START_REF] Cytron | Efficiently computing static single assignment form and the control dependence graph[END_REF]. The IR of actors can then be loaded and transformed to source code in any of the target languages supported by back-ends, namely C, C++, Java, LLVM, and VHDL.

We used the Cream [START_REF] Tamura | Cream: Class Library for Constraint Programming in Java[END_REF] constraint programming library to check mutually exclusive guards and to find values in the quasi-static classification method. Cream is capable of solving constraints defined on integers using different branch-andbound strategies. We extended the library to handle bitwise and constraints.

The classification method has been tested on 50 actors used by two dataflow descriptions of an MPEG-4 part 2 decoder present in Orcc. Table 1 shows the classification results with actors classified as static, cyclo-static, quasi-static, dynamic, time-dependent. The action scheduler optimization has been implemented for cyclo-static actors with mono-token reads and writes. This subset allowed us to test only one of the two dataflow descriptions, in which it resulted in a 20% increase of the number of frames decoded per second. Measurements on a particular actor responsible of the interpolation in motion compensation indicate that the transformed version of the actor is 2.4 times faster than the original version.

RELATED WORK

Zebelein et al. present a classification algorithm for dynamic dataflow models in [START_REF] Zebelein | Classification of General Data Flow Actors into Known Models of Computation[END_REF]. In their model, actors are defined as SystemC modules that receive and send data via SystemC FIFOs. Their classification method is based on the analysis of read and write patterns and FSMs of the different modules. Compared to ours, their approach is limited by the fact that they ignore any C++ code that does not contain a read or a write, and that they do not classify quasi-static actors.

In [START_REF] Boutellier | Quasi-static scheduling of CAL actor networks for reconfigurable video coding[END_REF], Boutellier et al. show how to express quasi-static RVC-CAL actors as PSDF graphs and how to derive a multiprocessor schedule from these graphs. However, they do not address the issues of automated classification and transformation: Quasi-static behavior is specified with parameters defined manually, and they do not explain how lowlevel Homogeneous SDF (HSDF) graphs created from quasistatic branches can be automatically transformed to high-level PSDF graphs. As a consequence, we believe that our work can serve as a preprocessing step for their approach by automatically classifying actors as quasi-static and transforming them to high-level PSDF graphs.

Gu et al. present a technique to recognize a set of Statically Schedulable Regions (SSRs) within a dynamic dataflow program [START_REF] Gu | Exploring the concurrency of an MPEG RVC decoder based on dataflow program analysis[END_REF]. SSRs are sets of ports that are statically coupled, which essentially means that the production of an output port matches the consumption of the input port(s) it is connected to (additional criteria are developed in [START_REF] Gu | Exploring the concurrency of an MPEG RVC decoder based on dataflow program analysis[END_REF]). On the one hand, SSR classification has potentially more knowledge about static behavior because it looks at connected actors rather than just inside actors. On the other hand, by considering an actor as a whole our classification can discover its behavior (cyclo-static and quasi-static) and transform it into a high-level SDF or PSDF graph that will make merging easier. Using SSRs to obtain additional information as an input to our classification algorithm is a possible direction for future work.

CONCLUSION

This paper presented a method to automatically classify dynamic dataflow actors into more restricted dataflow MoCs, along with a method to automatically transform classified actors to static dataflow and parameterized static dataflow graphs. The transformations presented allow more efficient code to be generated for those actors and improve execution speed by reducing the number of FIFO accesses. We used these methods on 50 actors from two dynamic dataflow descriptions of an MPEG-4 part 2 decoder, and studied how the actors that could be transformed following classification could improve execution speed by 20% on one of the descriptions.

The work described in this paper paves the way for future work concerning the merge of SDF and PSDF actors together. Merging actors would further reduce the overhead induced by FIFO accesses, and would also reduce the amount of dynamic scheduling currently needed. Actor merging is a necessary step towards efficient multi-processor mapping and scheduling by increasing the computation to communication ratio.

Fig. 1 .

 1 Fig. 1. Towards an efficient implementation of dynamic dataflow programs using classification and transformation.

Fig. 2 .

 2 Fig. 2. The Clip actor in RVC-CAL.

Fig. 3 .

 3 Fig. 3. Behavior of the "Clip" actor.

Fig. 4 .

 4 Fig. 4. Dataflow Models of Computation.

Fig. 6 .

 6 Fig. 6. The limit action transformed.

2

  Orcc is available at: http://orcc.sf.net

	Number of actors Classification
	6	static
	14	cyclo-static
	11	quasi-static
	13	dynamic
	6	time-dependent

Table 1 .

 1 Classification results on 50 actors.

The developed sequence is "aaaaabbbaaaaabbbaaaaabbbaaaaabbb".


Jean-François Caulier

Patrick Dumont

The Interpretation of the Laakso-Taagepera Effective Number of Parties *

Keywords: Fragmentation, effective number of parties, concentration index, size biased sampling, length biased sampling Résumé JEL classification: C65, D71, D72 Mot-clés : Fragmentation, nombre effectif de partis, indice de concentration, échantillonage biaisée par la taille

In this paper, we present a general statistical framework within which we can draw a new interpretation of the Laakso-Taagepera effective number of parties fragmentation index. With the particular method of sampling with probability proportional to the party sizes, we show that the Laakso-Taagepera effective number of parties is the inverse of the size biased version of the traditional expected party size in shares. Further, we provide an axiomatic definition of the Laakso-Taagepera effective number of parties.

Introduction

What do we mean by the fragmentation of a party-system ? What is the definition of such a widely used concept in the political science field ? Why is it important to assess the degree of fragmentation of party-systems ? More importantly why the concept receives hearty agreement for its use when there is no unanimous consensus in its meaning ? Our aim is to discover or understand the definition that has to be given to the notion of fragmentation on the basis of its most accepted operationalization : the Effective Number of Parties (ENP). Our task is motivated by the work of [START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF] that present an alternative way to compute the Effective Number of Parties in terms of well-known statistics (mean and variance). Their work used as a springboard for ours, we seek to dive more deeper in the mathematical properties of the ENP in order to understand exactly its exact meaning and interpretation.

An important aspect of classification of party-systems is the degree of competition among political parties which in turn, depends ceteris paribus on the number and sizes of the elected parties. A system is said to be fragmented if it is composed of many elected parties. Hence, at a first approximation we can think that a key feature for a definition of the notion of fragmentation refers to the number of elected parties (see [START_REF] Elkins | The measurement of party competition[END_REF],p.683). Of course the number of parties alone does not tell anything on the size distribution of seats and is of poor information. Some authors have proposed to enrich the concept of fragmentation in order to go beyond the only consideration of the number of parties and the distribution of seats, such as in [START_REF] Blau | The effective number of parties at four scales: Votes, seats, legislative power and cabinet power[END_REF] or [START_REF] Ricciuti | Political fragmentation and fiscal outcomes[END_REF]. Despite these efforts, the quantitative very aspect of fragmentation remains deeply rooted in the field. Since the first proposal for classification in term of two-party and multi-party proposed by Duverger [START_REF] Duverger | Political Parties: Their Organization and Activity in the Modern State[END_REF]), scholars have constantly tried to give more precise quantifications of the number of competing parties and distribution of sizes. One such measure has reached a high degree of consensus among scholars : the Laakso-Taagepera Effective Number of Parties (ENP) (see [START_REF] Lijphart | Electoral Systems and Party Systems: A Study of Twenty-Seven Democracies, 1945-1990[END_REF] p.68 and [START_REF] Laakso | Effective number of parties: A measure with application to west europe[END_REF]). Despite the drawbacks and flaws of the ENP, stressed by some authors suggesting new measures (see [START_REF] Dumont | The effective number of relevant parties : How voting power improves the Laakso-Taagepera's index[END_REF], [START_REF] Dunleavy | Constructing the number of parties[END_REF], [START_REF] Golosov | The effective number of parties: A new approach[END_REF], [START_REF] Kline | How we count counts: The empirical effects of using coalitional potential to measure the effective number of parties[END_REF], [START_REF] Molinar | Counting the Number of Parties: An Alternative Index[END_REF]), the ENP remains the most constant used, if not the only one, measure of party-system fragmentation. It thus seems that if we are in state to correctly and consistently give a correct interpretation to the ENP, we will directly get a definition for the concept of fragmentation, given that the ENP is "The" measure of fragmentation.

The ENP in a mean and variance framework

We introduce some notation in order to present the classical formula for the ENP and the proposed reformulation of [START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF] in terms of mean and variance.

Let N denote a party-system composed of n political parties, n a finite integer. Each party i owns x i ∈ R + seats in the party-system, with R + the set of nonnegative real numbers and x = n i=1 x i is the total number of seats in the system. We assume that x is known and fixed for a given party-system. We denote by s i = x i /x the shares of seats of party i, for each i in N . A party-system N consists either in a distribution of seats

x ∈ R n + or shares s ∈ [0, 1] n with R n
+ and [0, 1] n the n-fold cartesian product of R + and [0, 1] respectively. The Effective Number of Parties [START_REF] Laakso | Effective number of parties: A measure with application to west europe[END_REF]) of a party-system N is a function ENP : R n + → R + defined by

ENP(x) = 1 n i=1 (x i /x) 2 = n i=1 s 2 i -1
the inverse of the sum of squared shares. Some basic statistics : For a distribution of seats x, let

µ(x) = 1 n n i=1 x i (1)
the mean number of seats among parties,

σ 2 (x) = 1/n n i=1 (x i -µ(x)) (2)
the variance of x. Correspondingly we have µ(s) and σ2 (s) the mean and variance of s. Note that µ(s) = 1/n. Alternatively we can calculate the variance by

σ 2 (s) = µ(s 2 ) -µ 2 (s) = 1 n n i=1 s 2 i - 1 n 2 ,
that can be rewritten

n i=1 s 2 i = n σ 2 (s) + 1 n 2 = nσ 2 (s) + µ(s)
establishing the identity

ENP(x) = n/(1 + n 2 σ 2 (s)) = 1/(µ(s) + nσ 2 (s)) (3)
as in [START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF] (equation (10), p.105).1

If relation 3 is interesting as it allows the calculation of ENP using two well-known statistics, the mean and the variance, or even simpler only by knowing n and the variance (since the mean of n shares is always 1/n), it could then mislead to the conclusion that the ENP is merely a reformulation of the variance of a distribution of seat shares. Still, we must bare in mind that the reformulation of an expression is not always insignificant and indeed, this reformulation of ENP can shed the light on two possible paths of interpretations. The first concerns the relation between ENP and concentration indices and the second one concerns the statistical interpretation of the ENP. Both kinds of interpretations explain why the ENP can be expressed only as a function of n and the variance.

The ENP as number equivalent index

One of the reasons explaining the success story of the ENP can be found on its intuitive meaning : "The effective number of components is the easiest to visualize in concrete terms: [ENP]=2.28 directly tells us that there are more than two but definitely less than three major parties [. . . ] One can ask uninitiated students to estimate the effective number of parties and they respond with values approximating [ENP]" (in [START_REF] Taagepera | Seats and Votes: The Effects and Determinants of Electoral Systems[END_REF], p.80).

The ENP is a number equivalent index. This type of index requires that if all the parties in the party-system have the same number of seats, the value taken by the index is the actual number of parties (see [START_REF] Adelman | Comment on the" h" concentration measure as a numbersequivalent[END_REF]). The difficulty in assessing the fragmentation of a party-system lies in the variability among parties sizes. When all the parties have an equal number of seats, there is no inequality in the distribution of seats, the actual number of parties does convey some sense. If a number equivalent index evaluated for a party-system achieves a value of k, we can say that the party-system is as fragmented as if there were k parties of equal size. Of course a number equivalent index does not always achieve integer values but this must not create problems, first because it then tells us where the party-systems stands according to situations with clearcut meaning (if the index is 1.5, you can say that it is half fragmented than 3 or that it is just the halfway between 1 and 2 equal parties), secondly no one seems to be offended by an assertion stating that last year, each american woman has given birth to one and half children.

According to [START_REF] Blackorby | A normative approach to industrial-performance evaluation and concentration indices[END_REF], number equivalent indexes are inverse of concentration measures. Indeed, the link between the ENP and the Hirschman-Herfindahl concentration index is well known (see [START_REF] Laakso | Effective number of parties: A measure with application to west europe[END_REF] or [START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF]). The ENP is simply the inverse of the Hirschman-Herfindahl (HH). Applied to a party-system, the HH is calculated as HH(s) = 1/ENP(s) = n i=1 s 2 i . The HH index achieves (the-oretically) values between 0 and 1 indicating the degree of concentration. An increase in the value of a number equivalent corresponds to a reduction in the degree of concentration. A party-system highly concentrated (HH → 1) displays most probably a dominant party owning most of the available seats and is thus poorly fragmented, with a low ENP close to 1 (the lower bound for the ENP). Concentration indices are not inequality indices, even though both are related. Measures of concentration deal with the presence of dominant elements in term of sizes in the distribution under study. Inequality indices are concerned with the presence of small size elements by comparison of large size elements in the distribution. To stress the distinction between the aspects tackled by the measures, imagine a distribution with a giant size element. If some tiny size elements enter into the distribution, a concentration index won't be affected whereas the inequality will greatly increase. The variance of a distribution is not an adequate inequality index. If we double each entry in a given distribution such that the mean is double and the shape of the distribution remains unchanged, the variance would quadruple, while common sense would difficultly accept that inequality is aggravated. One way to transform the variance in an inequality index is to standardize it, obtaining the coefficient of variation :

c(x) = σ 2 (x) µ(x) or for s = x x , c(s) = n σ 2 (s),
a function of n and σ 2 (s). The coefficient of variation records the relative dispersion of distributions and is particularly adequate to compare distributions with different means.

The precise link between concentration and inequality indices has been demonstrated first in [START_REF] Davies | Choosing between concentration indices: The iso-concentration curve[END_REF] and then by [START_REF] Blackorby | A normative approach to industrial-performance evaluation and concentration indices[END_REF]. They show that the inverse of a concentration measure (a number equivalent index) can be written as a function of the number of elements n and a measure of inequality (the coefficient of variation for example). Accordingly, the ENP can be written as a function f (n, c(s)) where f is increasing in n and decreasing in c(s). Let us rewrite equation 3 as

ENP(s) = n 1 + c 2 (s) = n 1 + √ σ 2 (s) µ(s) 2 = n 1 + n 2 σ 2 (s)
the desired relationship. Holding c(s) fixed, we see that ENP is increasing in n and decreasing in c(s) for a fixed n. The ENP being a number equivalent index, given the existing results in the literature, it is not a surprise that the ENP can be expressed as a function of n and σ 2 .

The ENP as statistic

In this section we present the second line of interpretation of the ENP in term of statistic. We build on this interpretation on the story told by [START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF], the so-called "class-size paradox"2 , that we place in a more general context. As [START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF] state in footnote 3, p.103, this paradox is a well-known phenomenon in the statistics literature, which can be found under various names whose most frequent are "methods of ascertainment" [START_REF] Fischer | The effects of methods ascertainment upon the estimation of frequencies[END_REF]), "length-biased sampling" [START_REF] Cox | The statistical analysis of series of events[END_REF], [START_REF] Zelen | Length-biased sampling and biomedical problems[END_REF]), "the waiting time paradox" [START_REF] Feller | An introduction to probability theory and its applications[END_REF], p.12),, "sizebiased sampling" [START_REF] Scheaffer | Size-biased sampling[END_REF]), "the inspection paradox" [START_REF] Ross | Introduction to probability models[END_REF]), "weighted distributions" [START_REF] Patil | Encyclopedia of statistics, chapter Weigthed distributions[END_REF]), . . . All these papers deal with the same problem of sampling bias. In the class-size paradox, you want to estimate the average size of classes in a school by asking students the size of their class. This method introduces an estimation bias since you are sampling students and not classes. Suppose that you repeatedly go for a walk after dinner and meet ten people in your neighborhood out of which seven have a dog, you won't surely conclude that 70% of your neighbors have a dog. When you arrive randomly at a bus stop, due to the variation of circulation of buses, you will have to wait more than half the average time between two buses. You are more likely to arrive during longer intervals between two buses and must wait on average more than the average inter-arrival time. A radar fixed at an arbitrary location on a highway has more chances to record faster cars, slow-developing tumors have more chances to be detected in random medical screenings of a population, . . . In all these examples, the variation in sizes or length matters a lot, and the problem disappears as soon as there is no variation in size.

We have already seen that there is no difficulty to assess the fragmentation in a party-system with equal size parties, but the raw number of parties is a useless information as soon as there is variability in size. The intuitive explanation usually put forward for the ENP is that some weighting is necessary. Bigger parties receive more weight in the computation, and to avoid arbitrary weights, we use weight proportional to size [START_REF] Taagepera | Predicting party sizes: the logic of simple electoral systems[END_REF] p.58). This amounts to introducing a sampling bias. We now present the ENP formula in the context of sampling bias to show the logic of its weighting and to present the consequent interpretation.

We start with a finite party-system N with n parties. Let i = 1, . . . , n denote the labels of parties in N . The distribution of seats among parties in N is x = x 1 , . . . , x n with x i being the number of seats own by party i. We design a random experiment consisting in drawing a party i. The discrete random variable X is the number of seats own by party i. The probability function associated to X is p X (x i ) = P (X = x i ). The expected value of X, denoted by E[X], is defined by

E[X] = n i=1 x i p X (x i ).
This expression is the expected number of seats given the random selection process of parties. Note that E[X] corresponds to the mean number of seats µ in equation ( 1) if and only if p X (x i ) = 1 n for all i ∈ N , when all parties have the same probability to be selected. The variance of X, denoted by Var(X) is defined by

Var(X) = E (X -E[X]) 2 = n i=1 p X (x i )(x i -E[X]) 2 = E[X 2 ] -E 2 [X].
Again, the variance of X corresponds to the variance of the distribution σ 2 in equation ( 2) if and only if p X (x i ) = 1 n for all i ∈ N . We now design another experiment that consists in drawing a seat s at random, with s the label of the seat, taking values from 1 to x, the total number of seats. To each seat corresponds one and only one party. The discrete random variable X * is the number of seats of the corresponding party owning s, i.e. if s belonging to party j has been chosen by the random experiment, then X * = x j . The probability function associated to X * is p X * (x i ) = P (X * = x i ). This experiment is an indirect way to choose a party.3 Correspondingly, the expected value of X * is defined by

E[X * ] = n i=1 x i p X * (x i ).
and its variance by

E (X * -E[X * ]) 2 = n i=1 p X * (x i ) (x i -E[X * ]) 2 = E[X * 2 ] -E 2 [X * ].
According to the random experiment chosen, there exist two different ways to estimate the mean number of seats by party. In the second experiment, selecting a seat is an indirect way of picking a party. Given the number of seats owned by parties, parties are selected with a probability proportional to the number of seats they have. The second experiment is a method of sampling with bias proportional to size. X * is called the size-biased version of X and the probability function of X * is called the size-biased probability function of X

p X * (X * ) = Xp X (X) E[X]
and thus

E[X * ] = n i=1 x i p X * (x i ) = n i=1 x 2 i p X (x i ) E[X] = Var(X) + E 2 [X] E[X]
that can further be simplified

E[X] + Var(X) E[X] = E[X * ]. (4)
The difference

E[X * ] -E[X] = Var(X) E[X] is the bias involved estimating E[X] by E[X * ].
Using this general setting, we are in state to give the interpretation of the ENP in terms of the two random processes we have just designed.

We recall that the population of x seats is distributed across n parties and we denote x i the number of seats of party i, i = 1, . . . , n. Note that n i=1 x i = x. Then the expected number of seats in a equally randomly selected party , i.e. the average party size, is given by equation ( 1)

µ(x) = 1 n n i=1 x i = x n
with the corresponding variance σ 2 (x) (equation ( 2)). Now if x = 1 we get by equation ( 1)

µ(s) = 1 n .
With the second random process consisting in drawing a seat at random, we get the expected size (in number of seats) of a party containing an equally randomly selected seat and it is given by

µ * (x) = n i=1 x i x x i = n i=1 x 2 i x = x 2 1 + • • • + x 2 n x 1 + • • • + x n (5)
that comes from the reasoning of choosing a seat with probability 1 x and recording the size of the party owning the seat, so that if you record the score for all seats, out of x seats, you will record x i times the size x i for each possible i = 1, . . . , n. For each value x i in the first distribution, you get x 2 i entries in the second distribution. If x = 1 we get by equation ( 5)

µ * (s) = n i=1 s 2 i = 1 ENP(x) . (6)
Using equation (4) we have

µ * (s) = µ(s) + σ 2 (s) µ(s) = µ(s) + nσ 2 (s). (7)
Combining equations ( 6) and ( 7), we get the identity in equation (3) of [START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF] (equation (10), p.105). For example, suppose two parties with s 1 = 0.6 and s 2 = 0.4, draw a seat at random and record the size of its party, with 60% of chances you will record 0.6 and with 40% of chances you will record 0.4, making the expected size of the party for the average seat 60%(0.6)+40%(0.4) = 0.52, contrasting with the average size of parties of 0.6+0.4 2 = 0.5. The expected size from drawing a party at random is 0.5 whereas the expected size of a party from drawing at random a seat is 0.52. Both means can be obtained by direct calculation using equations ( 1) and ( 5) or by equation ( 7) : µ * (0.6, 0.4) = 0.5 + 0.01 0.5 = 0.52 In term of interpretation, µ(x) is the average size for a party, or the size of the average party, whereas µ * (x) is the size of the party owning the average seat. Correspondingly, µ(s) are the seat shares of the average party and µ * (s) are the seat shares of the party owning the average seat. The difference between µ(s) and µ * (s) is the selection bias due to the method of sampling. Here, we consider that the population elements are the seats whereas the sampling or observational units are the parties, considered as groups of seats. Hence, µ(s) is the group mean and µ * (s) is the element mean. By equation ( 7) we see that the element mean is always greater than the group mean unless there is no variability (measured by σ 2 (s)) in the distribution of seat shares. And this is exactly the rationale behind the ENP : we want to attach more importance to bigger parties. If you select a party indirectly by picking a seat, you have more chances to choose a bigger party. The bigger the party, the more chances the seat chosen at random belongs to the party. On the contrary, the probability that the randomly chosen seat belongs to a smaller party is smaller. This process of random group selection is known in the literature as selection of groups with probability proportional to size (see [START_REF] Kish | Sampling organizations and groups of unequal sizes[END_REF]).

This leads to a new interpretation of the ENP. The inverse of the ENP is the average size (in seat shares) of the party to which belongs a randomly chosen seat denoted µ * (s). Pick at random a seat, it will belong to a party with 1/ENP seat shares. Generally speaking, an average is simply a total number of units divided by the number of elements. Normalizing units in seat shares, we get 1 as the total number of seat shares. The number of elements in this line of interpretation is measured by an effective number of parties. Hence we can call 1/ENP= µ * (s) the effective average size in seat shares. 4 Again, if there is no variability in size among parties, the ENP is the actual number of parties n, in that case, the effective average size µ * (s) is simply 1/n, the average size in seat shares µ(s). In a given assembly, we tautologically always have n i=1 s i = 1, then

1 ENP = µ * (s) ⇔ ENP = 1 µ * (s)
the effective number of parties is the total number of seat shares divided by the effective average size.

Definition. Let x = x 1 , . . . , x n a distribution of seats among the n political parties in a finite party-system N and x = n i=1 x i the total number of seats in N . The corresponding distribution of seat shares is denoted s = s 1 , . . . , s n with s i = x i

x for i =, 1 . . . , n.

• Draw a seat at random with probability 1 x and record the size of the corresponding party, then µ * (x) =

x 2 1 +•••+x 2 n x 1 +•••+xn
is the expected size of the party owning the seat, or the effective average size.

• Correspondingly, µ * (s) = s 2 1 +• • •+s 2 n is the expected shares of the party owning the seat, or the Hirschman-Herfindahl effective average seat shares.

• With the same random process, the Laakso-Taagepera effective number of parties EN P (x) =

1 µ * (s)
is the expected number of parties having the same size of the party owning the randomly selected seat.

In light of this framework, the new interpretation of the ENP is quite interesting. If you repeatedly draw a seat at random, then you know that in average, there will be ENP(x) parties of the same size of the party from which the chosen seat has been drawn, including this party. We also provide a new interpretation of the classical concentration Hirschman-Herfindahl index as the effective average size in seat shares, that contrasts with the usual interpretation as the probability that two deputies picked at random from among the parties will be of the same party (see [START_REF] Golosov | The effective number of parties: A new approach[END_REF], [START_REF] Dalton | The quantity and the quality of party systems[END_REF]).5

The contraharmonic mean

In this section we briefly comment another occurrence of µ * (x) =

x 2 1 +•••+x 2 n x 1 +•••+xn
in the literature as contraharmonic mean or antiharmonic mean. the first reason we can put forward in order to explain the given name can be found for n = 2 (see [START_REF] Lann | A closer look at a relatively neglected mean[END_REF]), where its relationship with respect to the harmonic mean is plain. The arithmetic mean of two numbers a and b is

A = a + b 2 .
The harmonic mean of two numbers a and b is

H = 2ab a + b .
The contraharmonic mean of two numbers a and b is

C = a 2 + b 2 a + b .
In these particular cases, C and H are equally distant from A, i.e.

C -A = A -H = (a -b) 2 2(a + b) .
Relationship that can be verified with C = 2A-H. The distance between C and A being the same as the one between A and H but on the other way can be considered as a good justification for the name contra or antiharmonic. Alas, this relationship only holds for n = 2. Nevertheless, there still exists a relationship between the contraharmonic and harmonic means. Let X be a random variable and X * its size-biased version (see previous section or appendix). Then it can be shown that (see [START_REF] Stein | Sampling bias and the inspection paradox[END_REF]) :

E 1 X * = 1 E[X]
.

Hence, in calculating the expectation of the inverse of the random variables X * , i.e. the harmonic mean of X * , we get the inverse of the expectation of X. Hence, in order to estimate the expectation of X, it is sufficient to take the inverse of the harmonic mean of X * . This reason can constitute another argument for the given name of contraharmonic.

Axiomatic characterization of the ENP

In this section, we present a set of independent postulates or axioms that, if combined, fully characterize the ENP and its inverse, the HH. Note that another axiomatization of the Hirschman-Herfindahl index already exists in the literature (see [START_REF] Chakravarty | An axiomatic characterization of a generalized index of concentration[END_REF]) that completely differs from ours. 6 We adopt the usual notation : x ∈ R n + is the distribution of seats among the n parties, for any n ∈ N. The corresponding shares is denoted s ∈

[0, 1] n , s i = x i /x with x = n i=1 x i . The Laakso-Taagepera Effective Number of Parties is a function EN P : n∈N R n + → R + such that ENP(x) = n i=1 s 2 i -1
and the Hirschman-Herfindahl concentration index is a function HH

: n∈N R n + → R + such that HH(x) = 1/ENP(x) = n i=1 s 2 i .
We first provide the characterization of HH as measure of concentration.

Axiom 1 (Homogeneity of degree zero). For all n ∈ N, for all x ∈ R n + , for all scalars k > 0, a function

C : n∈N R n + → R + is homogeneous of degree zero if and only if C(x) = C(kx)
All what matters in the measurement of concentration are shares and not absolute levels. An index of concentration is independent of the unit in which the components of x are measured. In particular, measuring the concentration on a given distribution or on the distribution expressed in percentages should not change the degree of concentration, making concentration a relative index. We can thus state the axiom in a weaker form :

Axiom 2 (Relative index). For all n ∈ N, for all x ∈ R n + , C : n∈N R n + → R + is a relative index if and only if

C(x) = C x x .
Thus, if an index C is homogeneous of degree zero, C can be expressed as a relative index.

Axiom 3 (Reflexivity). For all n ∈ N, for all a ∈ R + , a function C :

n∈N R n + → R + is reflexive if and only if C(1a) = 1/n with 1 ∈ R n + = 1, . . . , 1.
That is, if the n quantities are equal, then the value taken by function C as effective average size is simply 1/n. In particular, if there is only one quantity in a distribution x ∈ R + = {x}, then C(x) = 1.

Axiom 4 (Recursivity). For all n ∈ N, for all x ∈ R n + , a function

C : n∈N R n + → R + is recursive if and only if C(x 1 , x 2 , x 3 , . . . , x n ) = C(x 1 + x 2 , x 3 , . . . , x n ) -2 x 1 x 2 x2 .
This axiom belongs to the general class of recursivity properties

C(x 1 , x 2 , x 3 , . . . , x n ) = C(x 1 + x 2 , x 3 , . . . , x n ) + G(x 1 , x 2 )
for functions C : n∈N R n + → R + and G : R 2 + → R + where different generating functions G have been given in the literature in order to characterize information measures such as entropy (see [START_REF] Ebanks | Characterizations of information measures[END_REF], chap. 3 or [START_REF] Aczel | On measures of information and their characterizations[END_REF]). The motivation for this recursivity axiom is to compare the concentration of two distributions with the same aggregate quantities and one distribution has been obtained from the other by merging in one entry the first two entries of the original distribution. In that case, by how much the concentration increases ? The difference in term of concentration when x 1 and x 2 from a distribution x ∈ R n + merge in

x 1 + x 2 in a distribution x ∈ R n-1 + is given by C(x ) -C(x) = G(x 1 , x 2 ) = - 2 x2 x 1 x 2 that can be rewritten C(x ) -C(x) x 2 x = -2 x 1 x (8)
that is, the average concentration increase in term of the shares of x 2 is a linear function g(x 1 /x) = 2x 1 /x. Since we can write equation 8 as

C(x ) -C(x) x 1 x = -2 x 2 x
we have G(x 1 , x 2 ) = g(x 1 /x)x 2 = g(x 2 /x)x 1 ⇒ g(x) = kx with x ∈ R + and k an arbitrary constant, in particular in this case k = -2/x. The interpretation of the recursivity is now plain : the average increase of concentration resulting from a merging of two entries is linear, the simplest form of increase we can find.

Theorem 1. For all n ∈ N, for all x ∈ R n + , a function C : n∈N R n + → R + satisfies axioms 2-4 if and only if C(x) = HH(x).

Proof. (⇒)

Note that we can rewrite for any scalar k > 0, so that HH satisfies axiom 1, and thus axiom 2. Let x = 1a with a ∈ R + . Then we have

HH(x) = n i=1 (x i ) 2 ( n i=1 x i ) 2 to see directly that HH(kx) = n i=1 (kx i ) 2 ( n i=1 kx i ) 2 = k 2 n i=1 x 2 i k 2 ( n i=1 x i ) 2 = n i=1 x 2 i ( n i=1 x i ) 2 13
HH(x) = n i=1 a 2 ( n i=1 a) 2 = na 2 n 2 a 2 = 1 n ,
satisfying the axiom 3. Now, for any

x ∈ R n + , HH(x) = n i=1 s 2 i = s 2 1 + s 2 2 + s 2 3 + • • • + s 2 n = (s 1 + s 2 ) 2 + s 2 3 + • • • + s 2 n -2s 1 s 2 ,
satisfying the axiom 4. (⇐) For any x ∈ R n + , by axiom 2,

C(x) = C(s).
By axioms 3, for x ∈ R + ,

C(x) = 1.
Let S i = i j=1 s j and Ṡi = S i-1 s i for all i = 1, . . . , n -1. By successive applications of axiom 4,

C(s 1 , . . . , s n ) = C(s 1 + s 2 , s 3 , . . . , s n ) -2s 1 s 2 = C(S 2 , s 3 , . . . , s n ) -2 Ṡ2 = C(S 2 + s 3 , s 4 , . . . , s n ) -2 Ṡ2 -2S 2 s 3 = C(S 3 , s 4 , . . . , s n ) -2 Ṡ2 -2 Ṡ3 . . . = C(S n-1 , s n ) -2 n-1 i=2 Ṡi = C(S n-1 , 1 -S n-1 ) -2 n-1 i=2 Ṡi = C(S n-1 + 1 -S n-1 ) -2 n i=2 Ṡi = 1 -2 n i=2 Ṡi = n i=1 s 2 i = HH(x) by noting that s n = 1 -n-1 i=1 s i = 1 -S n-1 .
The axiomatization of the ENP can be done straightforward by some simple adaptation of the axioms, since the ENP can be expressed as the inverse of HH.

Axiom 5 (Reflexivity*). For all n ∈ N, for all a ∈ R + , a function C :

n∈N R n + → R + is reflexive if and only if C(1a) = n with 1 ∈ R n + = 1, . . . , 1. Axiom 6 (Recursivity*). For all n ∈ N, for all x ∈ R n + , a function C : n∈N R n + → R + is recursive if and only if C(x 1 , x 2 , x 3 , . . . , x n ) = C(x 1 + x 2 , x 3 , . . . , x n ) - 2x 2 x 1 x 2 .
Theorem 2. For all n ∈ N, for all x ∈ R n + , a function C : n∈N R n + → R + satisfies axioms 2,5 and 6 if and only if C(x) = ENP(x).

Other desirable properties have been proposed in the literature for the effective number of parties or HH, but they appear to be logically deducible from the conjunction of the ones elevated to the rank of axioms. One of them is zero shares independence : if a party has zero shares in a party-system, it should not influence the fragmentation/concentration. Definition (Zero shares independence). For all n ∈ N, for all x ∈ R n + a function C : R n + → R + is independent of zero entries in x, if and only if

C(x, 0) = C(x).
This property can be deduced from homogeneity and recursivity :

C(x 1 , x 2 , x 3 , . . . , x n , 0) = C(x 1 + x 2 , x 3 , . . . , x n , 0) - 2x 1 x 2 x2 = C(x 1 + x 2 + x 3 , . . . , x n , 0) -2 x 1 x 2 -(x 1 + x 2 )x 3 x2 = . . . = 1 -2 n i=2 Ṡi -2 n i=1 x i 0 = n i=1 s 2 i = C(x 1 , x 2 , x 3 , . . . , x n ).
Another desirable property also states that merging of two entries should not reduce concentration. This can also been to be satisfied thanks to the recursivity axiom. To deepen our intuitive understanding of the functioning and interpretation of the recursivity axiom, we present the next corollary of Theorem 1.

Corrollary 1. For all n ∈ N, for all x ∈ R n + such that x 1 = x 2 , let C : n∈N R n + → R + be a concentration index satisfying axioms 2,5 and 6, then C(x 1 + x 2 , x 3 , . . . , x n ) -C(x 1 , x 2 , x 3 , . . . , x n ) = s 2 that is the increase in concentration resulting from the merging of x 1 and x 2 is exactly s 2 = x 2 x .

Let s ∈ [0, 1] n be a seat shares distribution such that s 1 = 50%, then, by the recursivity axiom we know that HH(0.5 + s 2 , s 3 , . . . , s n ) -HH(s) = s 2 . In particular, if s = (0.5, 0.5), by the reflexivity axiom HH(s) = 1/2. By the reflexivity axiom we also have HH(s 1 + s 2 = 1) = 1, and thus HH(1) -HH(s) = 1/2, as desired.

Conclusion

Various authors have proposed amelioration of the Laakso-Taagepera effective number of parties in order to measure the fragmentation without taking the time to address the fundamental question of defining what is the fragmentation of a party-system? Since the measurement of fragmentation is now intimately linked to the ENP, even exclusively, we propose a statistical interpretation of the ENP as consistent definition of party-system fragmentation. By putting the class-size paradox of [START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF] in a more general statistical framework, we can tell a nice story in which fits perfectly the measurement of fragmentation and draw thereby a new interpretation by analogy. This new interpretation is the following. For a given partysystem, the ENP is in expectation, the number of parties having the same size as the party owning a seat drawn at random with probability equals to 1 over the total number of seats. The inverse of the ENP, known as the Hirschman-Herfindahl concentration index, is the expected size of the party owning a seat drawn at random with the same probability. We then show how the ENP is fully characterized by the properties of zero-homogeneity, reflexivity and a particular recursion equation.

X * is equal to the mean of the original random variable X when it is positive, i.e., E[1/X * ] = 1/µ. Another way of expressing these results is that E[X * ]E[1/X * ] = 1 + σ 2 /µ 2 . 20 Documents de Travail du Centre d'Economie de la Sorbonne -2011.06

  Documents de Travail du Centre d'Economie de la Sorbonne -2011.06

The same derivation can be obtained from the relation ENP -1 = 1 n + nσ

(s) in[START_REF] Golosov | The effective number of parties: A new approach[END_REF] (equation (1) p.2).

Documents de Travail du Centre d'Economie de la Sorbonne -2011.06

Documents de Travail du Centre d'Economie de la Sorbonne -2011.06

(see also[START_REF] Feld | Why your friends have more friends than you do[END_REF],[START_REF] Feld | Variation in class size, the class size paradox, and some consequences for students[END_REF], Feld and Grofman [2010]) 6 Documents de Travail du Centre d'Economie de la Sorbonne -2011.06

Note how our constructions mimic the procedure of computing the averages of class size in[START_REF] Feld | The laakso-taagepera index in a mean and variance framework[END_REF].

See Hannah and Kay [1977]. 9 Documents de Travail du Centre d'Economie de laSorbonne -2011.06

Draw a deputy at random, with probability 1/si he will belong to party i, draw another deputy, with the same probability he will belong to party i, so that with probability 1/s 2 i both will belong to the same party.

[START_REF] Chakravarty | An axiomatic characterization of a generalized index of concentration[END_REF], the authors characterize a general class of concentration indices, known as the Hannah-Kay class (see[START_REF] Hannah | Concentration in modern industries: Theory, measurement and the U.K. experience[END_REF]) to which the Hirschman-Herfindahl index is a particular case. They show that among the self-weighted quasi-linear means, the Hannah-Kay family is the only one to satisfy a replication axiom. 11 Documents de Travail du Centre d'Economie de la Sorbonne -2011.06

Appendix

In this appendix, we reproduce some entries that can be found in [START_REF] Patil | Encyclopedia of statistics, chapter Weigthed distributions[END_REF]. Suppose X is a nonnegative observable random variable with PDF f (x). Suppose a realization x of X under f (x) enters the investigator's record with probability proportional to w(x, β), so that P r(Recording|X = x) = w(x, β).

Here the recording (weight) function w(x, β) is a nonnegative function with parameter β representing the recording (sighting) mechanism. Clearly, the recorded x is not an observation on X, but on the random variable X w having PDF

where ω = E[w(X, β)] is the normalizing factor, making the total probability equal to unity. The random variable X w is called the weighted version of X, and its distribution in relation to that of X is called the weighted distribution with weight function w. An important weighted distribution corresponds to w(x, β) = x, in which case, X w = X * is called the size-biased version of X . The distribution of X * is called the size-biased distribution of PDF

where µ = E[X]. The PDF f * is called the length-biased or size-biased version of f , and the corresponding observational mechanism is called lengthor size-biased sampling. Some interesting results concerning size-biased sampling : [START_REF] Zelen | Length-biased sampling and biomedical problems[END_REF]). The expected value of the size-biased version X * is E[X * ] = µ[1 + σ 2 /µ 2 ], where E[X] = µ and V (X) = σ 2 . Furthermore, the harmonic mean of