Karol Desnos
email: kdesnos@insa-rennes.fr

Maxime Pelcat
email: mpelcat@insa-rennes.fr

Jean-Francois François Nezan
email: jnezan@insa-rennes.fr

Slaheddine Aridhi
email: saridhi@ti.com

Memory Bounds for the Distributed Execution of a Hierarchical Synchronous Data-Flow Graph

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

I. INTRODUCTION

During the design of an embedded system, the treatment of memory issues strongly impact the final system quality and performance, as the area occupied by the memory can be as large as 80% of the chip and may be responsible for a major part of its power consumption [START_REF] De Greef | Array placement for storage size reduction in embedded multimedia systems[END_REF]. Prior work on memory issues for Multiprocessor System-on-Chip (MPSoC) mostly consists of optimization techniques that minimizes the amount of memory allocated to run an application, thus reducing the capacity and area of memory of the developed system [START_REF] Murthy | Shared memory implementations of synchronous dataflow specifications[END_REF], [START_REF] Fabri | Automatic storage optimization[END_REF], [START_REF] Raulet | Optimisations mémoire dans la méthodologie aaa pour code embarqué sur architectures parallèles[END_REF]. These techniques rely on a precise knowledge of system behavior, particularly scheduling and mapping the application tasks on the system processors, and so may only be applied during late stages of the system design process.

The purpose of the method presented in this paper is to derive the memory bound requirements of a system (Figure 1) in the early stages of its development when there is a complete abstraction of the system architecture. This method is based on an analysis of the system application, and allows the developer of a multi-core shared-memory system to adequately size the chip memory.

This paper focuses on memory characterization of applications described by a Dataflow Process Network (DPN) Model of Computation (MoC) [START_REF] Lee | Dataflow process networks[END_REF]. A MoC defines the semantics of an algorithm model: which components the model can contain, how they are interconnected and how they interact. A DPN MoC divides the application into computational entities named actors that exchange data via First-In First-Out (FIFO) channels. The algorithm model is specified as a directed application graph in which nodes represent actors and edges represent FIFO queues. Each actor is associated to firing rules specifying its behavior in terms of token consumption and production. Tokens are abstract representations of a data quantum, independent of its size. The actors themselves are "black boxes" of the model and may be implemented in any programming language. Firing an actor consists of starting its preemption free execution.

The Synchronous Data-Flow (SDF) MoC is certainly the most widely used DPN model. It consists of a static model in which all production and consumption token rates are fixed and known at compile time. This property makes the model analysis possible at compile time. Interface Based SDF (IBSDF) is a hierarchical DPN MoC based on SDF that can be analyzed hierarchically [START_REF] Piat | Multi-core code generation from interface based hierarchy[END_REF].

Insu cient memory

Possible allocated memory

Wasted memory

Available Memory

Maximum-Weight

Clique Problem

Heuristic for Maximum-Weight

Clique Problem The rapid prototyping context and the IBSDF model, which serves as an input to our method, are introduced in section II and the successive transformations applied to the application graph to reveal its memory characteristics are developed in section III. Then, section IV presents existing algorithms and a new heuristic approach to derive the memory bounds of an application. An overview of previous research on memory issues for multi-core systems is given in section V. Finally, after an evaluation of the performance of our method in section VI, we conclude this paper and propose possible directions for future work in section VII.

≤ ≤ Interval Coloring

Problem

Sum of vertices weights 0

Insu cient memory

Possible allocated memory

Wasted memory

II. CONTEXT

A. Interface-Based Synchronous Data-Flow Graph

IBSDF [START_REF] Piat | Multi-core code generation from interface based hierarchy[END_REF] is a static hierarchical dataflow MoC defined as an extension of SDF. Figure 2 shows an example of an IBSDF graph, where the top level comprises 3 actors A, B and h that respect the SDF semantics. Edges are labeled with their token production and consumption rates. An edge with a black dot signifies that initial tokens are present in the FIFO queue when the system starts to execute. The number of initial tokens is specified by the x100 label. Initial tokens are a semantic element of the SDF MoC that makes communication possible between successive iterations of the graph execution. h is an IBSDF hierarchical actor. Its behavior is given by a subgraph containing source and sink interfaces. These interfaces insulate the behavior of the top graph and subgraph. This property makes the algorithm description process simpler and less errorprone [START_REF] Piat | Multi-core code generation from interface based hierarchy[END_REF]. Like SDF, IBSDF is an untimed MoC. It specifies actor dependencies but does not take into account the time needed to execute the actors. The memory bounds presented in this paper are thus computed without actor timing consideration and, in that sense, characterize an application IBSDF graph independent of implementation. This is in contrast to the related work from the literature, which tends to focus on postscheduling and execution timing analysis (see Section V).

B. Hardware/Software Exploration Workflow

Rapid prototyping consists of extracting information from a system in the early stages of its development. It enables hardware/software co-design and favors early decisions that improve system architecture efficiency. The work presented in this paper aims to extract memory information from an application graph at an early stage of system design and independent of architecture details. It allows the system designer to discard architectures with insufficient memory and to evaluate the degree of memory optimization required to produce the final system with an optimal amount of memory.

Figure 3 illustrates the position of the memory bounds computation in the rapid prototyping process as proposed in [START_REF] Pelcat | An open framework for rapid prototyping of signal processing applications[END_REF]. Rapid prototyping inputs consist of an algorithm model respecting the IBSDF MoC, an architecture model respecting the System-Level Architecture Model (S-LAM) semantics

Rapid Prototyping

IBSDF Algo

S-LAM Archi

Scenario

Algo Transfos

Archi Transfos

Scheduling

Simulation

Code Generation

Exporting Results

Memory Bounds Computation

DAG

Fig. 3. Rapid Prototyping Process [START_REF] Pelcat | A System-Level architecture model for rapid prototyping of heterogeneous multicore embedded systems[END_REF] and a scenario providing constraints and prototyping parameters. The scenario ensures the complete separation of algorithm and architecture models. Algorithm and architecture models undergo transformations in preparation for the rapid prototyping steps. Static multi-core scheduling is then applied to dispatch the algorithm actors to the architecture processing elements and to schedule their executions [9] [10]. Finally, the scheduling information is used to simulate the system behavior and to generate compilable code for the targeted architecture. It can also be exported to an external SystemC based simulator. In this process, the memory bounds computation is executed on the transformed algorithm graph and has no dependency on the architecture graph. The next section explains the IBSDF graph properties and Section III-A details the algorithm transformations applied to IBSDF prior to the memory bounds computation.

III. PREPROCESSING TOWARD MEMORY ANALYSIS

A. Algorithm Transformations

The first step to characterize the memory bounds of an application consists of applying a set of transformations to its IBSDF Graph. The SDF model of the application is successively flattened, and first converted into a Single Rate SDF, then into a Directed Acyclic Graph (DAG). As presented in [START_REF] Piat | Multi-core code generation from interface based hierarchy[END_REF], these transformations are used to reveal the parallelism embedded in the IBSDF model, thus enabling a better mapping and scheduling of its actors on a multicore architecture. To illustrate these transformations, we successively apply them to the IBSDF graph of Figure 2. The first transformation consists of flattening the hierarchy of the graph by replacing all hierarchical nodes with their content. The IBSDF graph is thus transformed into a SDF graph presented in Figure 4.

The second transformation is the conversion into a Single-Rate SDF graph: a SDF where the production and consumption values on each edge are equal. In this model, each vertex corresponds to a single actor firing from the SDF graph. This conversion is performed by computing the topology matrix [START_REF] Lee | Synchronous data flow[END_REF], multiplying actors by the number of their firings and reorganizing edges, as shown in Figure 5, where actor B is split in two instances. An algorithm to perform this conversion can be found in [START_REF] Sriram | Embedded Multiprocessors: Scheduling and Synchronization[END_REF].

The last conversion consists of generating an acyclic precedence graph by isolating one iteration of the algorithm. This is achieved by ignoring the edges with initial tokens in the single-rate SDF. In our example, this transformation results in ignoring the feedback edge F→A which stores 100 initial tokens. In the context of memory analysis, these transformations are applied to fulfill the following objectives:

• Expose data parallelism: Concurrent analysis of data parallelism and data precedence gives information on the lifetime of memory objects prior to any scheduling step. Indeed, two FIFO queues belonging to parallel data-paths may contain data tokens simultaneously and consequently are forbidden from sharing a memory space. Conversely, two FIFOs linked with a precedence constraint, such as A→B and C→F FIFOs in Figure 4, will never store data tokens simultaneously, thus can share the same memory space.

• Break FIFOs into buffers shared between actors: In the SDF model, the channels carrying data tokens between actors behave like FIFO queues. The memory needed to allocate each FIFO corresponds to the maximum number of tokens stored during an execution of the graph. As this number of tokens depends on the schedule of the actors, methods exist to derive a schedule that minimizes the memory needed to allocate the FIFOs [START_REF] Sung | Memory efficient software synthesis with mixed coding style from dataflow graphs[END_REF]. However, in our method, the memory analysis is not dependent on scheduling considerations. It is for this reason that FIFOs of undefined sizes before the scheduling step are replaced with buffers of fixed sizes during the transformation of the graph into a single-rate SDF. In Figure 5, buffers linking two actors will be written and read only once with a data token of fixed size, which simplifies the memory analysis.

• Derive an acyclic model: Cyclic data-paths in an IBSDF graph are an efficient way to model iterative or recursive calls to a subset of actors. In order to use efficient static scheduling algorithms [START_REF] Kwok | High-performance algorithms of compile-time scheduling of parallel processors[END_REF], SDF models are often converted into DAGs before being scheduled. Besides revealing data-parallelism, this transformation makes it easier to schedule an application, as each actor is fired only once per execution of the resulting DAG. Similarly, in the absence of a schedule, deriving a DAG permits the use of memory objects (communication buffers) that will be written and read only once per execution of the DAG. Consequently, before a memory object is written and after it is read, its memory space will be reusable to store another object.

B. Memory objects

The DAG resulting from the transformations of an IBSDF graph, contains three types of memory objects

• Communication buffers: The first type memory object corresponds to the directed edges of the DAG and are the buffers used to transfer data between consecutive actors.

In our approach, we consider that the memory allocated to these buffers is reserved from the execution start of the edge producer actor until the completion of the edge consumer actor. This choice is made to enable custom token consumption throughout actor firing time. As a consequence, the memory used to store an input buffer of an actor should not be reused to store an output buffer of the same actor. In Figure 5, the 150 units of memory used to carry data between actors C and D can not be reused, even partially, to transfer data from D to F. Working memory of actors: This second type of memory object is the maximum amount of memory allocated by an actor during its execution. This working memory represents the memory needed to store the data used during the computations of the actor but does not include the input nor the output buffers memory. In our method, we assume that an actor keeps an exclusive access to its working memory during its execution. In Figures 2 to 5, the size of the working memory associated with each actor is given by the number below the actor name. This memory is equivalent to a task stack space in an operating system. • Feedback FIFOs: The final type of memory object corresponds to the memory needed to store edges ignored as a result of the transformation of a Single-Rate SDF into a DAG. These edges which are ignored to break cycles, can still carry data between successive executions of the DAG and behave like FIFO queues. These feedback edges may not share memory space with any other memory object of the application.

C. Memory Exclusion Graph

Once an application has been transformed into a DAG, and all its memory objects have been identified, the last preprocessing step of our method consists of deriving the memory exclusion graph which will serve as a basis to our analysis.

A memory exclusion graph is an undirected weighted graph denoted by G =< V, E, w > where:

• V is the set of vertices. Each vertex represents an indivisible memory object. • E is the set of edges representing the memory exclusions.

• w : V → N is a function with w(v) the weight of a vertex v. The weight of a vertex corresponds to the size of the associated memory object. We also denote: Two memory objects of any type exclude each other (i.e. they can not share the same memory space) if a schedule can be derived from the DAG where both these memory objects store data simultaneously. Some exclusions are directly caused by the properties of the memory objects, such as exclusions between input and output buffers of an actor. Other exclusions result from the parallelism of an application, as is the case with the working memory of actors from parallel data-paths that might be executed concurrently.

• N (v) the neighborhood of v, i.
The memory exclusion graph presented in Figure 6 is derived from the IBSDF graph of Figure 2. The complete graph contains 17 memory objects and 66 exclusions but, for clarity, only the vertices corresponding to the buffers between actors (type 1) are presented.

Building a memory exclusion graph based on a DAG consists of scanning its actors and data-transfers in order of precedence, so as to identify its parallel branches. As part of this scan, the memory objects and the exclusions caused by a precedence relationship are added to the memory exclusion graph. The, exclusions are then inserted between all memory objects which have been identified in the DAG as belonging to parallel branches. An alternative way of building an exclusion graph is to first build its complement graph, within which two vertices are linked if the corresponding memory objects can share a memory space. Then, the exclusion graph is simply obtained by considering that two of its vertices are linked if they are not connected by an edge in the complement graph.

In our method, the memory exclusion graph is built based on a non-scheduled DAG allowing the characterization of the application independent of architecture constraint. However, a subsequent update of this graph to incorporate the changes resulting from a schedule is possible. Indeed, a static schedule introduces an execution order of the graph actors, which can be seen as a new precedence relationship between actors. The addition of this new precedence link to a DAG, results in the possible disappearance of a certain amount of parallelism and the resulting exclusions. For example in Figure 5, if actor D is scheduled before actor E, then the exclusion disappears between the working memory of D and the E→F communication buffer.

IV. MEMORY ALLOCATION BOUNDS

The upper and lower bounds of the static memory allocation of an application are respectively a maximum and a minimum limit to the amount of memory needed to run an application, as presented in Figure 1. These bounds are crucial information in the co-design process, as they allow the developer to adjust the size of the memory available accordingly to the application requirements. Furthermore, as these bounds can be computed during the early development of a MPSoC, they might prevent the developer from mapping an insufficient or an unnecessarily large memory chip.

A. Least upper bound

The least upper memory allocation bound of an application corresponds to the size of the memory needed to allocate each memory object in a dedicated memory space. Such an allocation would be a waste of memory, as a memory space used to store an object would never be reused to store another. However, this allocation scheme must be used for exclusion graphs where an exclusion exists for every pair of vertices.

Given an exclusion graph G, its upper memory allocation bound is thus the sum of the weight of its vertices:

Bound M ax (G) = v∈V w(v) (1)
The upper bound for the exclusion graph of Figure 6 is 850 units, and the upper bound for the complete exclusion graph derived from the IBSDF of Figure 2 is 1020 units.

B. Greatest lower bound

The greatest lower memory allocation bound of an application is the least amount of memory required to execute it. Finding this optimal allocation based on an exclusion graph can be done by solving the equivalent Interval Coloring Problem [START_REF] Bouchard | About equivalent interval colorings of weighted graphs[END_REF], [START_REF] Fabri | Automatic storage optimization[END_REF].

A k-coloring of an exclusion graph is the association of each vertex v i of the graph with an interval

I i = {a, a + 1, • • • , b -1} of consecutive integers -called colors -, such that b -a = w(v).
Two distinct vertices v i and v j linked by an edge must be associated to non-overlapping intervals. Assigning an interval to a weighted vertex is equivalent to allocating a range of memory address to a memory object. Consequently, a k-coloring of an exclusion graph corresponds to an allocation of its memory objects.

The Interval Coloring Problem consists of finding a kcoloring of the exclusion graph with the fewest integers used in the I i intervals. This objective is equivalent to finding the allocation of memory objects that uses the least memory possible, thus giving the greatest lower bound of the memory allocation.

Unfortunately, as presented in [START_REF] Bouchard | About equivalent interval colorings of weighted graphs[END_REF], this problem is known to be NP-Hard, therefore it would be prohibitively long to solve in the rapid prototyping context which involves applications with hundreds or thousands of buffers. Moreover, a suboptimal solution to the Interval Coloring problem corresponds to an allocation that uses more memory than the minimum possible: more memory than the greatest lower bound. Consequently, a sub-optimal solution fails to achieve our objective which is to find a lower bound to the size of the memory allocated for a given application.

Insu cient memory

Possible allocated memory

Wasted memory

C. Lower bound using exact solution to the Maximum-Weight Clique Problem

Since the greatest lower bound can not be found in reasonable time, we focus our attention on finding a lower bound close to the size of the optimal allocation. In [START_REF] Fabri | Automatic storage optimization[END_REF], Fabri introduces another lower bound derived from an exclusion graph: the weight of the Maximum-Weight Clique (MWC).

A clique is a subset of vertices that forms a subgraph within which each pair of vertices is linked with an edge. As memory objects of a clique can not share memory space, their allocation requires a memory as large as the sum of the weights of the clique elements, also called the clique weight. The subsets {CD,CE,CF,DF,EF} or {AB 1 ,AB 2 ,B 2 C} are examples of cliques in the exclusion graph of Figure 8. Their respective weights are 550 and 250. By definition, a single vertex can also be considered as a clique, and a clique is called maximal if no vertex can be added to it to form a larger clique. In Figure 8, clique {CD,CE,CF,DF,EF} is maximal, but {AB 1 ,AB 2 ,B 2 C} is not as B 1 C is linked to all the clique vertices and can therefore be added to the clique.

The Maximum-Weight Clique (MWC) of a graph is the clique whose weight is the largest of all cliques in the graph. Although this problem is also known to be NP-Hard, several branch-and-bound algorithms have been proposed to solve it efficiently. In [START_REF] Östergård | A new algorithm for the maximum-weight clique problem[END_REF], Östergård proposes an exact algorithm which is, to our knowledge, the fastest algorithm for exclusion graphs with an edge density under 0.80. For graphs with an edge density above 0.80, a more efficient algorithm was proposed by Yamaguchi et al in [START_REF] Yamaguchi | A new exact algorithm for the maximum weight clique problem[END_REF]. Both algorithms are recursive and use a similar approach: beginning with a single vertex, they search for the MWC C i in a subset of the graph, then add a vertex to the considered subset and use the weight of C i to bound the search for a larger clique C i+1 in the new subgraph. The two algorithms were implemented in order to compare their performances on exclusion graphs derived from different applications (cf. section VI).

In the exclusion graph of Figure 8, the MWC is {CD,CE,CF,DF,EF} with a weight of 550 units.

The weight of the MWC corresponds to the amount of memory needed to allocate the memory objects belonging to this subset of the graph. By extension, the allocation of the whole graph will never use less memory than the weight of its MWC. Therefore, this weight is a lower bound to the memory allocation and is less than or equal to the greatest lower bound, as shown in Figure 7.

D. Lower bound using approximate solution to the Maximum-Weight Clique Problem

Östergård's and Yamaguchi's algorithms are exact algorithms and not heuristics. As the MWC problem is an NP-Hard problem, and even using these fast algorithms, an exact solution in polynomial time can not be guaraneed. In the rapid prototyping context, all methods and algorithms used must have a short and predictable runtime; that is why we developed a heuristic algorithm for the MWC problem.

The proposed heuristic approach, presented in Figure 9, is an iterative algorithm whose basic principle is to remove a judiciously selected vertex at each iteration, until the remaining vertices form a clique.

Our algorithm can be divided into 3 parts:

• Initializations (lines 1-5): For each vertex of the graph, the cost function is initialized with the weight of the vertex summed with the weights of its neighbors. In order to keep the input graph unaltered through the algorithm execution, its set of vertices V and its number of edges |E| are copied in local variables C and nb edges . • Algorithm core loop (lines 6-13): During each iteration of this loop, the vertex with the minimum cost v * is removed from C (line 8). In few cases where several vertices have the same cost, the lowest number of neighbor |N (v)| then the smallest weight w(v) are used to determine the vertex to remove. By doing so, less edges are removed from the graph and the edge density of remaining vertices will be

Input: a memory exclusion graph G =< V, E, w > Output: a maximal clique C 1: C ← V 2: nb edges ← |E| 3: for each v ∈ C do 4: cost(v) ← w(v) + v ∈N (v) w(v ) 5: end for 6: while |C| > 1 and 2•nb edges |C|•(|C|-1) < 1.0 do 7: Select v * from V that minimizes cost(•) 8: C ← C \ {v * } 9: nb edges ← nb edges -|N (v * ) ∩ C| 10: for each v ∈ N (v * ) ∩ C do 11: cost(v) ← cost(v) -w(v * ) 12:
end for 13: end while

14: Select a vertex v random ∈ C 15: for each v ∈ N (v random ) \ C do 16: if C ⊂ N (v) then 17: C ← C ∪ {v} 18:
end if 19: end for Fig. 9. Maximum-Weight Clique Heuristic Algorithm higher, which is desirable when looking for a clique. If there still are multiple vertices with equal properties, a random vertex is selected among them. This loop is iterated until the vertices in subset C become a clique. This condition is checked line 6, by comparing 1.0 -the edge density of a clique -with the edge density of the subgraph of G formed by the remaining vertices in C. To this purpose nb edge , the number of edges of this subgraph, is decremented line 9 by the number of edges in E linking the removed vertex v * to vertices in C. Lines 10 to 12, the costs of the remaining vertices are updated for the next iteration.

• Clique maximization (lines [START_REF] Kwok | High-performance algorithms of compile-time scheduling of parallel processors[END_REF][START_REF] Bouchard | About equivalent interval colorings of weighted graphs[END_REF][START_REF] Östergård | A new algorithm for the maximum-weight clique problem[END_REF][START_REF] Yamaguchi | A new exact algorithm for the maximum weight clique problem[END_REF][START_REF] Kim | New efficient clique partitioning algorithms for register-transfer synthesis of data paths[END_REF][START_REF] Szymanek | A constructive algorithm for memoryaware task assignment and scheduling[END_REF]: This last part of the algorithm ensures that the clique C is maximal by adding neighbor vertices to it. To become a member of the clique, a vertex must be adjacent to all its members. Consequently, the candidates to join the clique are the neighbors of a vertex randomly selected in C. If a vertex among these candidates is linked to all vertices in C, it is added to the clique.

The complexity of this heuristic algorithm is of the order of

O(|N | 2 )
, where |N | is the number of vertices of the exclusion graph.

For example, in Table I, the algorithm is applied to the exclusion graph of Figure 6. For each iteration, the costs of the remaining vertices are given, and the vertex removed during the iteration is crossed out. The column Density corresponds to the edge density of the subgraph formed by the remaining vertices.

In this simple example, the clique found by the heuristic algorithm and the exact algorithm are the same, and their 6 weight also corresponds to the size of the optimal allocation. This example proves that, as shown in Figure 7, the result of the heuristic can be equal to the exact solution of the MWC problem, whose size can also equal the size of the optimal allocation.

V. RELATED WORKS

To the extent of our knowledge, memory optimization for multi-core systems has generally been studied in the literature as a post-scheduling process. Using the scheduling information, the lifetimes of the different memory objects of an application are derived. Minimization is then achieved by allocating several memory objects whose lifetimes do not overlap in the same memory space.

Once the lifetimes of the memory objects are obtained, the memory allocation is performed using one of these different approaches:

• Running static -or offline -allocation algorithms inspired by dynamic allocators, such as those proposed in [START_REF] De Greef | Array placement for storage size reduction in embedded multimedia systems[END_REF], [START_REF] Raulet | Optimisations mémoire dans la méthodologie aaa pour code embarqué sur architectures parallèles[END_REF], [START_REF] Murthy | Shared memory implementations of synchronous dataflow specifications[END_REF]. As opposed to dynamic allocators which allocate memory objects in order they are brought to them, static allocators have a global knowledge of all memory objects at compile time, thus making further optimizations possible.

• Coloring an exclusion graph that models the conflicting memory objects [START_REF] Bouchard | About equivalent interval colorings of weighted graphs[END_REF], [START_REF] Raulet | Optimisations mémoire dans la méthodologie aaa pour code embarqué sur architectures parallèles[END_REF]. An equivalent approach is to use the complement graph, where memory objects are linked if they have non-overlapping lifetime, and perform a clique partitioning of its vertices [START_REF] Kim | New efficient clique partitioning algorithms for register-transfer synthesis of data paths[END_REF]. • Using constraint programming, as is the case in [START_REF] Szymanek | A constructive algorithm for memoryaware task assignment and scheduling[END_REF] where memory constraints are used together with cost, resource usage and execution time constraints. Besides the post-scheduling techniques, a few publications also consider the memory optimizations during the scheduling process. In [START_REF] Murthy | Shared memory implementations of synchronous dataflow specifications[END_REF], [START_REF] Sung | Memory efficient software synthesis with mixed coding style from dataflow graphs[END_REF], algorithms are presented to derive a schedule from a SDF graph so that the size of the FIFOs between actors is minimized. Another technique proposed in [START_REF] Orsila | Automated memory-aware application distribution for multi-processor system-on-chips[END_REF], consists of iterating the scheduling and the memory allocation steps and keeping only the schedule whose corresponding memory allocation uses the least memory.

Finally, certain optimization techniques can be applied before the scheduling step. These techniques mostly consist of modifying the description of the application behavior so as to maximize the impact of later optimizations. Variable renaming, instruction re-ordering, loop merging and splitting are examples of modifications for imperative languages that can reduce the memory needs of an application [START_REF] Fabri | Automatic storage optimization[END_REF]. Similar modifications can be applied to SDF graphs, as was done in [START_REF] Piat | Multi-core code generation from interface based hierarchy[END_REF] where a technique used to extract parallelism from nested loops in imperative languages is adapted to reveal data parallelism embedded in an IBSDF graph.

As explained in [START_REF] Balasa | Storage estimation and design space exploration methodologies for the memory management of signal processing applications[END_REF], the former optimization techniques often require a partial system synthesis and the execution of time-consuming algorithms. Although these techniques provide an exact or highly optimized memory requirement, they may be too slow to be used in the rapid prototyping context. In [START_REF] Balasa | Storage estimation and design space exploration methodologies for the memory management of signal processing applications[END_REF], Balasa et al. survey existing estimation techniques that provide a reliable memory size approximation in a reasonable computation time. The main difference between these estimation techniques and our bounding method is the abstraction level considered. Indeed, these techniques are mostly based on the analysis of imperative code while our method deals with applications modeled with SDF graphs.

VI. RESULTS

The memory bounds are computed in the PREESM1 rapid prototyping framework [START_REF] Pelcat | An open framework for rapid prototyping of signal processing applications[END_REF]. PREESM is an open-source Eclipse-based tool providing graph transformation algorithms, multi-core scheduling and C code generation from IBSDF graphs. Algorithms for memory bound computation have been implemented in Java in this framework. All results presented in this section are obtained by running the algorithms on a 3.1GHz CPU. Table II shows the performance of different algorithms for the MWC problem. Each entry presents the mean performance obtained from 400 randomly generated exclusion graphs with a fixed number of vertices (|V |) and a fixed density of edges (δ(G)). For each exclusion graph, the weights of its vertices are uniformly distributed in a predefined range. The 400 graphs are generated with ranges varying from [1000; 1010] to [1000; 11000]. Columns Östergård's, Yamaguchi's and Time respectively give the mean runtime of each of the three algorithms, and the Efficiency column gives the average ratio of the clique size found by the heuristic algorithm over the size of the MWC.

It should be noted that the clique maximization part of the heuristic algorithm was deactivated in all tests of this section. Indeed, several tests showed that this maximization improved the mean efficiency by only 2%, while multiplying the runtime of the heuristic by a factor 1,6.

Table II shows that the runtime of exact algorithms grows exponentially with the number of nodes of the exclusion graphs, and is highly dependent on the edge density of the graphs. Conversely, the runtime of the heuristic algorithm is roughly proportional to |V | 2 and is not strongly influenced by the edge density of the graphs. The results in table II also reveal that the mean efficiency of the heuristic algorithm for random exclusion graphs is of the order of 90%, and decreases slightly as the number of vertices increases. Finally, these results additionally confirm that Yamaguchi's algorithm has better performance than Östergård's algorithm for graphs with more than 80 vertices and an edge density higher than 0,80. The performance of each of the three algorithms was also tested using exclusion graphs derived from IBSDF graphs of functional applications. Table III shows the characteristics of the tested graphs. The first three entries of this table, namely RACH, LTE 1 and LTE 2 , correspond to application graphs describing parts of the Long Term Evolution (LTE) wireless communication standard. The last two entries, MP4P2 and Diff, respectively, are a description of the MPEG-4 (Moving Picture Experts Group) Part2 video encoder, and a dummy application that computes the difference between successive video frames. The values given for Actors and FIFOs are those of the flattened IBSDF graph, before its conversion into a DAG. It may also be noted that the lower memory bound indicated in Table III corresponds to the size of the MWC. In this section, only the memory objects corresponding to the communication buffers (type 1) were considered to generate the exclusion graphs.

To take advantage of a multi-core architecture, an application modeled with an SDF graph must present a high degree of parallelism. Exclusion graphs derived from such applications will therefore have a high edge density, as is the case with the graphs of Table III. The performance of each of the three algorithms on these graphs are related in Table IV.

As shown in Table IV, the efficiency of the heuristic algorithm for exclusion graphs derived from real applications is much higher than for randomly generated exclusion graphs. In- deed, the heuristic algorithm always finds a clique with weight almost equal to the weight of the MWC and has a runtime at least 4 times faster. Moreover, contrary to the exact algorithms which sometimes fail to find a solution within 12 hours (as denoted by ∞), the runtime of the heuristic algorithm is highly predictable as it is solely dependent on the number of memory objects |V |. In the case of LTE 1 , because of the large number of vertices in the exclusion graph, exact algorithms never ran to completion, thus we are unable to give the MWC exact size nor the efficiency of our heuristic algorithm for this graph. However, this example shows that our heuristic algorithm may succeed in finding a lower bound to memory requirements in cases where exact approaches fail. Additionally, it can also be noted that Yamaguchi's algorithm presents a slightly better performance than Östergård's algorithms for exclusion graphs derived from SDF graphs.

Finally, the algorithms were tested against 120 exclusion graphs derived from randomly generated SDF graphs. The resulting exclusion graphs presented edge densities from 0.49 to 0.93 and possessed between 50 and 500 vertices. These tests confirmed that Yamaguchi's algorithm is faster than Östergård's for exclusion graphs derived from SDF graphs. These tests also showed that our heuristic approach finds the optimal solution 81% of the time, and that when the optimal solution is not found, the average efficiency is 96.5%.

VII. CONCLUSION AND FUTURE WORKS

This paper outlines a complete method for deriving the memory allocation bounds (Figure 1) of an application modeled with a hierarchical SDF graph. The bounds are derived as a part of a rapid prototyping process for MPSoC and are independent of mapping/scheduling considerations. Our method is based on a weighted graph, derived from an application graph, which models the ability of memory objects to share a memory space. In addition to presenting existing algorithms to derive optimal bounds, we propose a new heuristic approach for determining a lower bound to the memory requirement. Our experiments indicate good performances for this approach, both in terms of speed and efficiency. Future work on this subject is likely to include further testing of our method with exclusion graphs incorporating the working memory of actors. Other potential directions for future research are the design of an allocation algorithm using an exclusion graph as input and the iterative computation of memory bounds to influence a scheduling process.

  Fig. 1. Memory Bounds

Fig. 2 .

 2 Fig. 2. Interface Based SDF (IBSDF) graph

Fig. 4 .

 4 Fig. 4. Flattened Synchronous Data-Flow

Fig. 5 .

 5 Fig. 5. Single-Rate SDF or Directed Acyclic Graph if dotpoint edge ignored

  e. the set of vertices linked to v by an edge. Vertices of this set are said to be adjacent to v. • |S| the cardinality of a set S. |V | and |E| are thus respectively the number of vertices and edges of the graph. • δ(G) = 2•|E| |V |•(|V |-1) the edge density of the graph corresponding to the ratio of existing edges to all possible edges.

Fig. 6 .

 6 Fig. 6. Memory Exclusion Graph

Fig. 8 .

 8 Fig. 8. Clique examples

TABLE III PROPERTIES

 III OF THE TEST GRAPHS

TABLE IV PERFORMANCE

 IV OF MAXIMUM-WEIGHT CLIQUE ALGORITHMS ON EXCLUSION GRAPHS DERIVED FROM THE TEST GRAPHS

PREESM project: http://sourceforge.net/projects/preesm/

ACKNOWLEDGMENTS

The authors would like to thank Renaud Keller for creating LTE applications that were used to evaluate the heuristic approach performance.


Dominique Guégan
email: dominique.guegan@univ-paris1.fr

Wayne Tarrant
email: w.tarrant@wingate.edu

On the Necessity of Five Risk Measures

Keywords:

The banking systems that deal with risk management depend on underlying risk measures. Following the recommendation of the Basel II accord, most banks have developed internal models to determine their capital requirement. The Value at Risk measure plays an important role in computing this capital. In this paper we analyze in detail the errors produced by the use of this measure. We then discuss other measures, pointing out their strengths and shortcomings. We give detailed examples, showing the need for five risk measures in order to compute a capital in relation to the risk to which the bank is exposed. In the end we suggest using five different risk measures for computing capital requirements.

Introduction

In the middle of 2008, the worldwide banking system seemed to start unraveling. Some consumers failed to pay the payments on their mortgages or other loans. This led to default on several collateralized debt obligations (CDOs), triggering the need for payment of the default leg of many credit default swaps (CDSs). A fear of counterparty risk seized the banking industry, not knowing if the parties who had sold the insurance against the default on the CDOs would be able to make the contracted payments. This led to a "credit seizure" whereby banks stopped lending money as freely as they once had, both to consumers and to other banking entities.

Many people have asked the question of how such a series of events took place. Although the reasons are complicated and a political hot button topic, some citizens have come to learn more about worldwide banking systems and their regulators. Many are calling for renewed regulation of banks and similar enterprises. But in order to craft meaningful banking laws, we must first understand what laws have been in place and why we have had problems such as those described above in spite of the laws that were in effect.

The banking laws that deal with risk management are based upon underlying risk measures that are used in order to determine the capital requirement for banks. In the following, we consider the strengths and weaknesses of the most used risk measure and then consider other risk measures. We will discuss the limitations of each of these individual risk measures and then show that at least five risk measures are necessary for distinguishing among different types of risk profiles when determining capital requirements for banks.

We note that this approach is a new one because, in general, researchers and practitioners limit themselves to the study or use of a single measure or sometimes two measures. (See, for example, [START_REF] Artzner | Thinking Coherently[END_REF], [START_REF] Yamai | Comparative Analyses of Expected Shortfall and Value-at-Risk : Their Validity under Market Stress[END_REF], and [START_REF] Caillault | Forecasting VaR and Expected shortfall using dynamical Systems : a risk Management[END_REF], among others.) Here we insist upon the use of a larger number of measures of risk, which are easy enough to compute in practice. We show that this information gives a better understanding of the risk incurred and more insight into deciding the best risk management strategy for banks.

The paper is organized as follows. In Section two we have recalled the notion of risk measures. Section three is devoted to a discussion on the regulation in the banking industry. Section four focuses on the problems related to the use of Value at Risk and discusses the notion of coherent risk measures. Section five presents different scenarios using more than one risk measure, finally proposing at least five measures. Section 6 discusses the applicability of the method.

Some definitions

To understand international capital requirement regulations without interrupting the flow, it is necessary to specify the notion of risks with which we work or that we wish to measure. There is little wonder that people are confused by what the term "risk" ought to mean. For instance, the website businessdictionary.com defines risk in seventeen different "general categories". For an illustration of the complexity of the problem, we now recall this definition: " Risk is the probability that an actual return on an investment will be lower than the expected return. Financial risk is divided into the following general categories: [START_REF] Artzner | Thinking Coherently[END_REF] Basis risk: Changes in interest rates will cause interest-bearing liabilities (deposits) to reprice at a rate higher than that of the interest-bearing assets (loans). ( 2) Capital risk: Losses from un-recovered loans will affect the financial institution's capital base and may necessitate floating of a new stock (share) issue. (3) Country risk: Economic and political changes in a foreign country will affect loan-repayments from debtors. (4) Default risk: Borrowers will not be able to repay principal and interest as arranged (also called credit risk). ( 5) Delivery risk: Buyer or seller of a financial instrument or foreign currency will not be able to meet associated delivery obligations on their maturity. (6) Economic risk: Changes in the state of economy will impair the debtors' ability to pay or the potential borrower's ability to borrow. [START_REF] Embrechts | Modelling Extremal Events for Insurance and Finance[END_REF] Exchange rate risk: Appreciation or depreciation of a currency will result in a loss or a naked-position. [START_REF] Fama | The Behavior of Stock Markets[END_REF] Interest rate risk: Decline in net interest income will result from changes in relationship between interest income and interest expense. (9) Liquidity risk: There will not be enough cash and/or cash-equivalents to meet the needs of depositors and borrowers. [START_REF] Hogg | Loss Distributions[END_REF] Operations risk: Failure of data processing equipment will prevent the bank from maintaining its critical operations to the customers' satisfaction. [START_REF] Mandelbrot | The Variation of Speculative Prices[END_REF] Payment system risk: Payment system of a major bank will malfunction and will hinder its payments. [START_REF] Markowitz | Portfolio selection[END_REF] Political risk: Political changes in a debtor's country will jeopardize debt-service payments. [START_REF] Rockafellar | Conditional Value-at-Risk for General Loss Distributions[END_REF] Refinancing risk: It will not be possible to refinance maturing liabilities (deposits) when they fall due, at economic cost and terms. ( 14) Reinvestment risk: It will not be possible to reinvest interest-earning assets (loans) at current market rates. [START_REF] Yamai | Comparative Analyses of Expected Shortfall and Value-at-Risk : Their Validity under Market Stress[END_REF] Settlement risk: Failure of a major bank will result in a chain-reaction reducing other banks' ability to honor payment commitments. (16) Sovereign risk: Local or foreign debtor-government will refuse to honor its debt obligations on their due date. (17) Underwriting risk: New issue of securities underwritten by the institution will not be sold or its market price will drop."

Each of these seventeen definitions are relevant to the situations of banks and securities firms. The unifying theme for each of the above definitions is that the situation of risk requires both uncertainty and exposure. If a company already knows that a loan will default, there is no uncertainty and thus no risk. And if the bank decides not to loan to a business that is considered likely to default, there is also no risk for that bank as the bank has no exposure to the possibility of loss. Thus, Merriam Webster defines risk as the possibility of loss or injury. This is certainly consistent with the concepts we have set forth.

So now one goal could be to have a single risk measure that will account for all the risk that a bank or securities firm might encounter. Some have objected to the risk measure being a single number, but there is some support for this idea. Investing is always a binary decision-either one invests or one chooses not to invest. Thus the argument is that, given a single number, one should have enough information to decide whether to invest or not. There have been some general agreements about the kinds of properties that such a risk measure ought to possess. These agreements must be acknowledged as being assumptions, but they have provided the definition that is now universal.

We recall the universally accepted definition of a risk measure [START_REF] Artzner | Thinking Coherently[END_REF]. Let X be a random variable. Then ρ is a risk measure if it satisfies the following properties:

• (Monotonicity) if X ≥ 0, then ρ(X) ≤ 0 • (Positive Homogeneity) ρ(αX) = αρ(X) ∀ α ≥ 0 • (Translation Invariance) ρ(X + a) = ρ(X) -a ∀ a ∈ R.
The idea behind this definition is that a positive number implies that one is at risk for losing capital and should have that positive number of a cash balance on hand to offset this potential loss. A negative number would say that the company has enough capital to take on more risk or to return some of its cash to other operations or to its shareholders. The monotonicity property states that an investment that always has positive payoff gives the company the ability to take on more risk. Positive homogeneity implies that multiplying your investment by k times gives you a risk of a loss that is k times larger. Translation invariance implies that a company holding a in cash lowers its measure of risk by a.

The most well-known measure seems to be the Value at Risk (VaR). In order to define VaR, we must first recall some basic concepts. Let X be a random variable and α ∈ [0, 1].

• q is called an α-quantile if Pr[X < q] ≤ α ≤ Pr[X ≤ q],
• the largest α-quantile is q α (X) = in f {x|Pr[X ≤ x] > α}, and

• the smallest α-quantile is q - α = in f {x|Pr[X ≤ x] ≥ α}.
It is easy to show that q α ≥ q - α and that q is an α-quantile if and only if q - α ≤ q ≤ q α . Given a position X and a number α ∈ [0, 1], we define the α-Value at Risk, VaR α (X), by VaR α (X) = -q α (X). We call X α-VaR acceptable if VaR α (X) ≤ 0 or, equivalently, if q α (X) ≥ 0. The α-VaR can be seen as the amount of cash that a firm needs in order to make the probability of that firm going bankrupt to be equal to α. This leads to the following property of VaR: VaR α (X +VaR α (X)) = 0. This states that one may offset the risk of an investment by having an amount of cash on hand equal to the value at risk inherent in holding the asset.

The Value at Risk has historically been the most important of the risk measures, as it is the one used by the Basel Committee on Banking Supervision in order to determine capital requirements for banks. Now, we briefly discuss the history of the Basel Committee, and then we will delineate issues with the Value at Risk.

The Basel Committee on Banking Supervision

The Basel Committee has its origins in the Bank Herstatt issue of 1974. On 26 June 1974 German regulators closed Bank Herstatt and forced its liquidation. That morning several banks had made payment in Deutsche Marks in Frankfurt in exchange for United States Dollars that were to be delivered in New York later in the day and not simultaneously only due to time zone differences. Bank Herstatt was closed between the times of the two payments, meaning that the counterparty banks did not receive their US dollars in New York.

Because of this debacle, and due to the issue of jurisdictions for such a situation, the G-10 countries formed a committee under the Bank of International Settlements, (BCBS, 1988). This Basel Committee on Banking Supervision consists of representatives from central banks and from regulatory agencies. The focus of this committee continues to grow and change, but it has historically tried to accomplish the following goals: to define roles of regulators in cross-jurisdictional situations; to ensure that international banks or bank holding companies do not escape comprehensive supervision by a native regulatory authority; to promote uniform capital requirements so that banks from different countries may compete with one another on a "level playing field".

It is the third goal that we will address at length. It is important to note, though, that the Basel Committee has no legislative authority, but the participating countries are honor bound to use its recommendations in their own regulations. However, the committee seems to understand and tolerate some difference in how each country implements recommendations due to historical or cultural differences in each country's banking community.

In trying to address the goal of a "level playing field," the Basel Committee proposed minimal capital requirements for banks in 1988. In 1992 these requirements became law in the G-10 countries, with the notable exception of Japan, which took a longer period of transition to these requirements due to the nature of the banking culture in that country. These regulations have come to be called the 1988 Basel Accord, BCBS (1988).

This 1988 Basel Accord involved banking in the sense of taking deposits and lending (which is known as commercial banking under US law), and the 1988 Basel Accord's thrust was at credit risk. Under these requirements, a bank would calculate its capital and its credit risk and then have to meet the stipulation that

capital credit risk ≥ 8%
This is often called an 8% capital requirement. In addition, the 1988 Basel Accord distinguished two different types, or tiers, of capital. Tier 1 capital is comprised of the book value of common stock, non-cumulative perpetual preferred stock, and published reserves from post-tax retained earnings. Tier 2 capital is assumed to be of lower quality and includes general loan loss reserves, long-term subordinated debt, and cumulative and/or redeemable preferred stock. Under the 1988 Basel Accord, up to 50% of a bank's stated capital (for the 8% capital requirement) could be tier 2 capital.

The credit risk was calculated in a somewhat more complicated manner as a sum of risk-weighted asset values. Although the Basel Committee wanted to make a simple system and only used five different weights, there are still many asset classes to delineate. The Committee also left some of the supervision up to local authorities in that the class of claims similar to municipal bonds was given one of four weights at the discretion of the country's regulatory agency.

In the early 1990s, the Basel Committee decided that it needed to account for market risk. In April of 1993 the Basel Committee put forth a series of amendments to the 1988 Accord. These amendments were basically intended to give capital requirements for banks' market risk. Banks would be required to identify their trading book and hold capital to offset the risk associated with this trading book. Capital charges for offsetting the market risk of the trading book would be based upon a 10-day 95% VaR measure. The Committee also added a category of Tier 3 capital, which was short-term subordinated debt. However, this Tier 3 capital could only be used to cover market risk. Now, the inequality that banks had to satisfy was:

capital credit risk + market risk ≥ 8%
After a number of comments on these revisions, the Basel Committee released a revised proposal in April 1995. There were a number of changes to the 1993 amendments, most notably that the Basel Committee would now allow banks to use either the previously announced VaR-based measures or individual proprietary VaR measures for computing capital requirements. The proposals were adopted in 1996 and quickly became known as the 1996 amendment, BCBS (1996). This went into effect in 1998.

Later, it was recognized that the Accord's treatment of credit risk had problems. The weights provided an incentive for banks to hold the debt of the G-10 governments, which paid very small dividends to the banks. This fact posed a glaring conflict of interest because the G-10 governments were the ones with regulatory oversight of the banks. Corporate debt was much more profitable, but the banks were charged at the 100% rate for holding this debt. Banks quickly realized that all corporate debt was weighted equally, while some corporate debt was much more risky and thus supplied a larger reward. Banks came to hold a lot of risky corporate debt and less high quality corporate debt.

The 1988 Accord's system of risk weights also failed to address a burgeoning market. Banks used both credit derivatives and securitizations to take advantage of the Accord. In addition there was outright fraud being perpetrated in banks, either internally or by borrowers from the banks. The original Basel Accord and its amendments failed to speak to these issues of risk. A new accord would have to address such operational risk.

In 1999 the Basel Committee proposed a new Accord, now known as Basel II.

Basel II professes to be based on three pillars: minimum capital requirements, supervisory review, and market discipline. Basel II (BCBS, 2005) replaces the original treatment of credit risk and requires capital to offset operational risk, thus making the new inequality:

capital credit risk + market risk + operational risk ≥ 8%
However, there is no change to the computation of bank capital (the three tiered system) or to defining market risk. The banks are still allowed to use proprietary VaR-based measures or opt to use the standardized measure. They also now have three choices for computing credit risk and three more choices for computing operational risk. Basel II went into effect in December 2006, but it has not been followed as widely as the previous accords. For instance only ten of the largest banks in the US are subject to Basel II (as the US believes its own Securities and Exchange Commission has more stringent rules that Basel II), while another ten have the option to opt-in to such regulation.

What is most notable about all the changes is that the VaR-based measures remain. Central to understanding why banks have struggled so much lately is understanding their risk management, and in order to understand risk management, we must understand Value at Risk.

Value-at-risk and coherent measures 4.1 Problems with Value at Risk

There are two major problems cited with Value at Risk as a risk measure.

The issue that is easier to describe is the fact that Value at Risk does not address how large of a bankruptcy a firm will experience. This risk measure only tells that a business will be bankrupt with a 5% chance if it doesn't have on account a sum of money equal to the 95%-VaR. As an example, say that a firm holds an asset that initially had no cost. That asset has a 95% chance of paying the company US$1 million and a 5% chance of giving the company a loss of US$1 million. By the above definition, we find that the 95%-VaR is US$1 million. Now assume that the firm holds another asset, again without initial cost. This asset again has a 95% chance of giving the company a profit of US$1 million, with a 1% chance of a loss of US$1million and a 4% chance of a loss of US$1 billion. This asset also has a 95%-VaR of US$1 million, but it is very clear that the second asset is much more risky for the firm to hold.

One can claim that such an example is contrived or that a different value of α might eradicate this problem. First, this problem has already appeared in the problems with paying off credit default swaps. Second, the mathematics can be easily shifted to account for a 99%-VaR or a 99.9%-VaR or whatever level one might choose. Considering that returns on stocks have been shown to have the fatter tailed Pareto distributions [START_REF] Mandelbrot | The Variation of Speculative Prices[END_REF], [START_REF] Fama | The Behavior of Stock Markets[END_REF]), very large losses are possible with small probability. This example of Pareto distributions could be used to address both the objections of contrivance and of scaling of α with the same class of examples.

The second problem critics cite is that VaR does not account for diversification effects. It is widely held that owning different types of investment vehicles will help to alleviate some of the risk that holding only one investment would produce. [START_REF] Markowitz | Portfolio selection[END_REF] discusses diversifying away specific risk, that risk that is unique to a given holding. He acknowledges that one cannot alleviate the market risk that is common to all holdings. Markowitz's calculations show that holding any number of assets more than 30, chosen with appropriate covariance, diversifies away specific risk.

As an example of this problem, consider the case where a bank has made two $1 million loans and one $2 million loan, each with a 0.04 probability of default and all pairwise independent. Then the 95%-VaR for each loan is $0. Thus, if we construct a portfolio consisting solely of the $2 million loan, we must have a 95%-VaR of $0. If we instead choose diversification and make our portfolio out of the two independent $1 million loans, something paradoxical happens. The probability of both loans defaulting is 0.0016, but the probability of exactly one loan defaulting is 0.0768. This implies that the 95%-VaR of our diversified portfolio is $1 million. Thus, VaR does not favor diversification in some instances.

This should lead us to question whether we ought to favor diversification or whether diversification is a property that is not meaningful to us. For instance, at www.glynhylton.com, the following scenario is proposed: Imagine you are stranded on a desert island. For fresh water, there are three natural springs, but it is possible one or more have been poisoned. To minimize your risk, what is your optimal strategy for drinking from the springs? You might: select one of the three springs at random and drink exclusively from it or select two of the springs at random and drink exclusively from them, or drink from all three springs. Diversification would say that we would reduce our risk by drinking from each of the three streams. Yet common sense says that if one spring is poisoned, we should not take a single drink from it for fear of being killed by ingesting any of the poison. So, if we determine from the first drink from one spring that it is not poisoned, we have no incentive to diversify away our risk by drinking from the others. Instead, this would only add to our risk of being poisoned. One can easily see this analogy applied to the area of risky assets.

So, is diversification always the best policy? If each of our assets has some probability of default, is it better to spread the risk of loss over several loans, choosing a larger probability of taking a small loss? Or does it make more sense to hold only one asset, taking a small probability of losing everything? These are questions of risk aversion that each bank and each individual investor will need to answer depending on his or her or its own risk preferences. Investment professionals have decided that the former is preferable to the potential of losing their entire investment. And some regulating agencies have agreed with this judgment, though the Basel Committee has implicitly disagreed, whether intentionally or not. Thus, we will pursue ways in which we might reconcile these differences and determine if there is some risk measure that might respect the desirability of diversification.

Coherent Risk Measures

In 1997 Artzner, Delbaen, Eber, and Heath (ADEH) proposed four desirable properties that measures of risk should have. In addition to the properties of translation invariance, positive homogeneity, and monotonicity, these authors added the property of subadditivity, i.e., using the notation from before, if X 1 , X 2 are random variables, then ρ(

X 1 + X 2 ) ≤ ρ(X 1 ) + ρ(X 2 ).
This is an attempt to respect the perceived value of portfolio diversification. They chose to call any measure that satisfied all four of the properties by the name "coherent risk measure". Of course this was an intelligent choice of names for their class of measures, as nobody would want to be accused of using a measure that is incoherent.

ADEH (1997) start by defining a set of acceptable positions. These are positions that some sort of supervisor, such as a regulator or an exchange's clearing firm, decides have an appropriate level of risk for the firm. They then propose that a firm may make different choices when faced with an unacceptable position. Either the firm may alter the position or decide to offset the unacceptable position by having cash on hand to account for the possibility of a loss. Should the firm decide to hold the unacceptable position, a risk measure will be the "distance" away from acceptable that their position measures.

ADEH (1997) then go about showing links between acceptance sets and measures of risk. Their acceptance sets are those for which the risk measure ρ takes a negative value on the set. Thus, acceptance sets are those for which no additional capital is needed to offset the risk that is being taken by holding the given position.

They next demonstrate that VaR is incoherent and also that VaR fails to recognize when there is a concentration of risks. This is just as we have shown above, although their examples are slightly more complicated and less transparent. The main conclusions of these authors to reject Value at Risk as a good risk measure lies on the following two reasons:

• Value at Risk does not behave nicely with respect to addition of risks, even independent ones, creating severe aggregation problems.

• the use of value at risk does not encourage and, indeed, sometimes prohibits diversification, because Value at Risk does not take into account the economic consequences of the events the probabilities of which it controls.

The authors (ADEH, 1997) then give the above definition of a coherent risk measure. They prove that any coherent risk measure arises as the supremum of the expected negative of final net worth for some collection of "generalized scenarios" or probability measures on states of the world. They point out that "Casualty actuaries have been working long at computing pure premium for policies with deductible, using the conditional average of claim size, given that the claim exceeds the deductible, [START_REF] Hogg | Loss Distributions[END_REF]. In the same manner, reinsurance treaties have involved the conditional distribution of a claim for a policy (or of the total claim for a portfolio of policies), given that it is above the ceding insurer's retention level. In order to tackle the question of how bad is bad, which is not addressed by the value at risk measurement, some actuaries (Bassi, Embrechts and Kafetzaki, 1996) have first identified the deductible (or retention level) with the quantile used in the field of financial risk measurement."

We now introduce the notion of tail conditional expectation. Given a base probability measure P on a probability space Ω, a total return r on a reference instrument and a level α, the tail conditional expectation is the measure of risk defined by

TCE α (X) = -E P [ X r | X r ≤ -VaR α (X)] (4.1)
This concept is variously called the expected shortfall, expected tail loss, conditional value at risk, mean excess loss or mean shortfall by several authors in the literature, [START_REF] Rockafellar | Conditional Value-at-Risk for General Loss Distributions[END_REF]. (ADEH) are able to show that coherent risk measures in general (and so their tail conditional expectation in particular) correspond to convex closed sets which include the positive orthant and are in fact homogeneous cones. They give several classifications, showing that coherent risk measures are in correspondence with the measures that arise from looking at the "generalized" scenarios that banks may face in order to construct and maintain acceptable positions. In mathematical terms, these are measures on probability spaces.

Finally, we can remark that for each risk X one has the equality

VaR α (X) = in f {ρ(X)|ρ coherent, ρ ≥ VaR α (X)}.
Thus, knowing that more restrictive measures are available to them, the question is why regulators would use the Value at Risk, noting that no known organized exchanges use VaR as the basis of risk measurement for margin requirements.

(ADEH) immediately answer their own question, with a quote from [START_REF] Stulz | Rethinking Risk Management[END_REF], "Regulators like Value at Risk because they can regulate it."

We will look at the problems that will arise from such an attitude.

5 How many measures do we need for a robust risk management strategy?

Insufficiency of a single measure

Here, we discuss the weakness of any single measure of risk for risk management strategy.

We start by noting that each of the graphs that are shown in this and the following sections represent the final 5% of the probability density function, i.e. if f (x) is the pdf of a distribution X that we are considering, then we must have that d c f (x)dx = 0.05. In this case [c, d] is the region of the graph that we have shown.

There is an understood assumption that f (x) = 0 for all x > d. Under this notation, the 95%-VaR(X) = c and the 95%-TCE(X) = 1

.05

d c x f (x)dx.
Although Value at Risk is used by the Basel Committee for determining the capitalization that a bank needs, it turns out that VaR is insufficient for distinguishing between some kinds of different risk characteristics. The following two situations have exactly the same VaR. In each case, the 95%-Value at Risk is 0. This is a great misnomer, as there are probabilities of a loss in each case. However, if we consider the notion of Maximum Loss (ML) that is the measure of risk ML(X) that is defined to be the largest loss that a firm could experience with nonzero probability when that firm holds the position X (in the notation of the previous paragraph, we have that ML(X) = d), then we can observe that this measure would distinguish between the two situations, as ML(X 1 ) = 5, while ML(X 2 ) = 10. (In this and in each of the following figures, we will adopt the notation that the first graph represents a distribution X 1 , while the second represents a distribution X 2 .) We also note that the 95%-TCE will identify that the two risk profiles are different, as 95%-TCE(X 1 ) = 5 2 , while 95%-TCE(X 2 ) = 10 0 x(1 -1 10 x)dx = 10 3 .

Since VaR turned out to be insufficient for our risk measuring purposes, maybe one of the two other measures is a better choice. We will start with the Tail Conditional Expectation at the 95% level. Here we look at two different situations having the same 95%-Tail Conditional Expectation. Both of these have the same 95%-Tail Conditional Expectation, as 95%-TCE(X 1 ) = 95%-TCE(X 2 ) = 10 3 , yet there are obviously different risk patterns associated with the two loss distributions. In the first situation, there is uniform probability of loss. In the second case, the probability of loss increases as losses increase. However, there is the potential for larger loss with the second situation. Each scenario might be preferable to certain institutions for specific situations, but the 95%-TCE does not alert the institution to any difference in the two different loss patterns. It is notable that both the Maximum Loss and the 95%-VaR will distinguish between the two situations. 95%-VaR(X 1 ) = 7 3 , while 95%-VaR(X 2 ) = 0. Likewise, ML(X 1 ) = 13 3 and ML(X 2 ) = 5.

Because the TCE has not been able to distinguish among different risk situations, we turn to the other measure we have previously introduced -the Maximum Loss. We will again look at the last 5% of the probability distribution. As we see in Figure 3, the two risk models have the same Maximum Loss as both distributions have no probability occurring after the value of 5. However, there are vastly different risks involved in choosing one situation over the other. In the first case, there is a simple uniform probability of loss across all the loss levels. In the second case there is zero probability of smaller losses but a larger probability of larger losses, tapering off toward the maximum loss. Here both the 95%-VaR and the 95%-TCE will determine the difference in the two positions. We first note that 95%-VaR(X 1 ) = 0 and that the 95%-VaR(X 2 ) = 3. Also, the 95%-TCE(X 1 ) = 5 2 , while the 95%-TCE(X 2 ) = 5 3 x(-

3 2 x + 17 2 ) = 19 5 .
From these examples, we should begin to see what each of these risk measures is actually measuring. The 95% Value at Risk gives the starting point of the worst 5% of returns under the given model. The 95% Tail Conditional Expectation tells the weighted average of that worst 5% interval. And the Maximum Loss shows the worst possible loss for the given risk profile.

In order for us to obtain two distributions with the same 95%-Value at Risk, we only have to begin our figures at the same value, making sure that we have 5% of the probability after that common point. For two distributions to have the same 95%-Tail Conditional Expectation, we must have two geometric figures that have the same weighted center of mass. And for two figures to have the same Maximum Loss, we only need both to have a common point as the maximum value for which both distributions have a nonzero probability.

Insufficiency of any two risk measures

Since individual measures failed to give a thorough picture of the risk characteristics of a given risk model, maybe the situation will be better if we try using two different risk measures. Having just stated what each risk measure assesses about the risk situation, we will attempt to use measures in pairs to see if they give us a full description of the risk characteristics of a model.

We will start by using both the 95%-VaR and the 95%-TCE. Again we are left with a problem. Indeed, the two circumstances shown in Figure 4 have equal 95%-Values at Risk of 0 and equal 95%-Tail Conditional Expectations of 10 3 , yet there are obviously different risk profiles. Again, the first model has uniform loss characteristics. The second has increasing probability of a larger loss, yet it does not allow for as severe of a loss as the first distribution.

Because we wanted both the 95%-VaR and the 95%-TCE to be equal, we had to meet two conditions. For the VaR condition, we needed both figures to have the same "starting point" for the greatest 5% of losses. Since the first figure is a uniform distribution, it is easy to determine that its weighted center of mass is 10 3 . So our second figure would have to have a weighted center of mass at 10 3 also, which can be computed by looking at the integral calculation. One just has to choose a pdf f (x) so that (in the notation previously described) 1 .05 d c x f (x) = 10 3 . Note that ML(X 1 ) = 20 3 , while ML(X 2 ) = 5, so that the measure of Maximum Loss distinguishes between these two distributions. Now we look at the pair of 95%-VaR and Maximum Loss, as shown in Figure 5.

Once again, we are in the situation where both examples have equality of 95%-VaR, each of which is 0. And, for both distributions the Maximum Loss is 5. Yet, the risk characteristics are once again different. In the second example, there is a larger probability of larger losses, while the first example has uniform probabilities across the entire loss interval. It is notable that the 95%-TCE here will alert us to the difference in the two situations, as 95%-TCE(X 1 ) = 5 2 , while 95%-TCE(X 2 ) = In order to produce more examples, all we would need is that both have the same starting point of the greatest 5% of losses and the same ending point of nonzero probabilities. That is, for both distributions we would need a common c and a common d in the notation of the previous section. Above are two such examples that meet these criteria. Now we will consider the circumstance of using the 95%-TCE and the ML as our risk measure pair (Figure 6). Here, the 95%-TCEs are equal, as are the MLs. Again, the risk models give different risk characteristics to those who would need to make a choice between the two. We have the uniform loss probability on a smaller interval, should we choose the first example. In the second example, the losses increase in probability as the size of losses increases. Here, we again have two criteria that have to be met. In order for the 95%-TCEs to be equal, we need to have the same weighted centers of mass. Again, these can be determined by doing the integral calculations that were previously described. For the MLs to be equal, we again need both distributions to have the same "ending point."

For both of the distributions we have that the 95%-TCEs are 10 3 , while the MLs are both 5. Thus, it appears from these examples that using two risk measures is not sufficient. We notice that 95%-VaR(X 1 ) = 5 3 , while 95%-VaR(X 2 ) = 0, so that the third measure differentiates between the two risk profiles.

Insufficiency of all three measures

With each pair of risk measures proving insufficient to determine the entire risk loss pattern, we look to the potential that three measures might work. Our four examples in Figure 7 have equal 95%-VaRs, equal 95%-TCEs, and equal MLs, yet the risk patterns are clearly different. The first is once again a uniform loss pattern. The second example shows increasing probabilities of losses and then decreasing, while the third example does just the opposite. The fourth example shows that this pattern of increasing and then decreasing probabilities (or likewise decreasing and then increasing probabilities) could be appropriately extended to get an infinite family of examples which have equality of all three of our measures. In order for our examples to have equivalence of all three measures, we have to meet three criteria. We need the same "starting points" of the worst 5% of retruns in order to make the VaRs equal. We require identical "ending points" for the MLs to be equal. Since the uniform distribution has symmetry, it will have a 95%-TCE of 5 2 . Thus, any distribution with an equivalent 95%-TCE (and the same starting and ending points) must also be symmetric in the greatest 5% of its losses. So our three measures do not distinguish among the potential scenarios that we might face. Obviously, something more is needed.

Extending to different probability levels

We have chosen to use the 95% level for our risk measures, but there is nothing special about the 95% level. Our examples would be just as valid if we substituted 90% or 99% or any other number in all of our measures and then scaled identically in all of the corresponding diagrams. However, this concept of considering different risk levels might also lead us to enough risk measures so that we can determine the risk profile from information about the different risk measures.

So now we will try using a vector of measures consisting of the 95%-VaR, the 99%-VaR, the 95%-TCE, 99%-TCE, and the ML. The different risk profiles demonstrated in Figure 8 are quite odd-looking, but they all have identical 95%-VaRs, 99%-VaRs, 95%-TCEs, 99%-TCEs, and MLs. The three distributions all have the necessary geometric properties for equality of all five measures. If we wanted to form a larger family of examples with the same values for all five measures, we would need our new distributions to have the same "ending points" in order to match up the MLs. We would need them to have the same "starting points" for both the greatest 5% of losses and the greatest 1% of losses in order to have equal 95%-VaRs and equal 99%-VaRs, respectively. And we would need symmetry in the greatest 5% of losses and in the greatest 1% of losses in order to have 95%-TCEs and 99%-TCEs, respectively, equal to the 95%-TCE and the 99%-TCE of the uniform distribution. Any figure meeting all these criteria would also be indistinguishable from the first five when viewed purely by looking at the values in our vector of five measures. Clearly several different profiles can share all five measures.

Discussions and Extensions

The first question that occurs to us is: how surprising should we consider these results to be? If we think of the 1 -α tail as a probability distribution in and of itself (of course appropriately scaling so that we have an area of 1 rather than an area of 1 -α) then we can apply theorems and facts from statistics to our situation. What seems to be the most relevant to our situation is the prospect of unique determination of a probability distribution from data we know about the probability distribution. It is a standard result that a probability distribution cannot be uniquely determined from the knowledge of less than all its finite moments (i.e. from knowledge of its mean, standard deviation, skewness, kurtosis, etc. This is shown by looking at Taylor expansions for each of the moments). Thus we should expect that we cannot determine the exact risk profile for a given portfolio, even if we allow that each of the risk measures tell us something different about the risk distribution. Thus, there is reason why this result should not be completely surprising to us.

We did see that it required some strange risk profiles in order for five risk measures to fail to distinguish among the risk profiles. Although our diagrams are jagged, it is an easy exercise to smooth out the corners by approximations, making sure to respect the necessary arithmetic and calculus so as not to disturb the equalities that we have honored. Using three measures tended to miss some important distinctions. Although the five measure vector will miss some different risk profiles, what it misses are situations that will very rarely occur naturally. Thus, we suggest that the use of five risk measures would be appropriate for regulatory and reporting purposes.

Although it is difficult for a single risk measure to efficiently account for all the risks a bank must consider in determining its proper capital requirement, this paper has shown a feasible way to get a better view of these risks. In practice many different ideas have to be considered. If the five measures of risk seem unwieldy, we might consider one risk measure that is some sort of aggregation of these five measures. We also feel the need to engage in a discussion of the function(s) of risk measures. One approach might be to consider one measure for market risks and another for operational risks (see, for example, Embrechts, Klüppelberg and Mikosch (2007), and [START_REF] Guégan | A modified Panjer algorithm for operational risk capital calculations[END_REF]). We plan to investigate the suggestions

Figure 1 :

 1 Figure 1: Two loss distributions with equal 95%-VaRs

Figure 2 :

 2 Figure 2: Two loss distributions with equal 95%-TCEs

Figure 3 :

 3 Figure 3: Two loss distributions with equal MLs

Figure 4 :

 4 Figure 4: Two loss distributions with equal 95%-VaRs and equal 95%-TCEs

Figure 5 :

 5 Figure 5: Two loss distributions with equal 95%-VaRs and equal MLs

Figure 6 :

 6 Figure 6: Two loss distributions with equal 95%-TCEs and equal MLs

Figure 7 :

 7 Figure 7: Four loss distributions with equal 95%-VaRs, 95%-TCEs and MLs

Figure 8 :

 8 Figure 8: Using five risk measures

from this paper on different data sets and present the results in a companion paper.