Viet Hai Ha

Éric Renault

Discontinuous Incremental: A new approach towards extremely lightweight checkpoints

. It is also the basic tool used in CAPE [1], [2], a paradigm which aims at distributing the execution of a program on a distributed-memory environment. This paper presents the new approach to checkpointer and the original optimization on checkpoint structure we have implemented and evaluated to make incremental checkpointing more efficient and more appropriate, especially for CAPE.

I. INTRODUCTION

As a critical component to ensure a program will terminate its execution even in case of system or hardware failure, many works have been done to develop checkpointing techniques and different approaches have been used. The first solution named complete checkpointing consists in saving all the information related to the running process [4]-[7], regardless these information have been modified from the beginning of the execution or they can be retrieved easily for example from a dynamic shared library. The alternative to complete checkpoints are incremental checkpoints. In this case, only the information that have been modified since the beginning of the execution are effectively saved [8], [START_REF] Yi | Ickpt: An Efficient Incremental Checkpointing Using Page Writing Fault -Focusing on the Implementation in Linux Kernel[END_REF]. The identification of the memory areas that have to be saved may either be provided by the developer of the application using pragma directives and/or dedicated functions, or automatically detected by the checkpointing tool itself. Both complete and incremental solutions have advantages and drawbacks. The main advantage of a complete checkpoint is the simplicity to generate it, while the main advantage of an incremental checkpoint is its size. An important drawback of incremental checkpointing technique, as a consequence of the regular monitoring of the process memory, is that the execution speed may significantly decrease. Overcoming this disadvantage is an important requirement to increase the performance of an incremental checkpointer.

OpenMP (for Open Multi-Processing) [15] is a very simple and powerful set of directives and functions to generate parallel programs from C, C++ or Fortran codes. The main limitation of OpenMP is that it is limited to shared-memory architectures. Some attempts have tried to port OpenMP on distributed memory architectures with various success. In order to achieve this goal, we have developed a new parallel computing paradigm called CAPE which aims at using checkpoints to distribute the execution of a program on a distributed-memory environment [START_REF] Renault | Parallelization of For Loops Using Checkpointing Techniques[END_REF], [START_REF] Renault | Distributed Implementation of OpenMP Based on Checkpointing Aided Parallel Execution[END_REF]. However, both existing checkpointing techniques cannot be used for an effective implementation. In case of complete checkpointing that was used in the first version of CAPE the very large generated checkpoints decreased the global performance. Although the incremental checkpointing technique can give smaller checkpoints, it has not enough services for the requirements of the discontinuously and alternatively checkpointing and recovering in CAPE.

As a result, in order to cope with both above requirements, this article presents the new approach and the original optimization we have developed and evaluated with very good first results.

The article is organized as follows: after the related works, Sec. III details our approach to generate discontinuous incremental checkpoints and also provides an evaluation of this approach; Sec. IV develops the data structure in checkpoint files, discussing memory granularity, the different storage format and arithmetics on checkpoints.

II. RELATED WORKS

A. Incremental checkpointing

An incremental checkpoint consists in a file that stores the parts of the memory3 that have been updated since the beginning of the execution of the program or the last checkpoint. From a high-level point of view, this is performed by setting access rights to read-only to all memory pages in order to force the system to deliver a SIGSEGV signal the next time a page is accessed for writing. Upon reception of the SIGSEGV signal, a copy of the content of the page is stored and access rights to the memory pages are restored to their initial values. When a checkpoint is required, the content of all modified pages are compared to their initial content and the difference is stored in the checkpoint file.

In order to perform these operations, each process that may be checkpointed has to be associated a monitor. Typically, this monitor is in charge of starting the process which checkpoints will be computed, catching the SIGSEGV signals, generating the checkpoint files and waiting for the termination of the process. However, this is not mandatory as a monitor may be attached to any already running process.

Clearly, the speed of the monitored process decreases due to the execution of the monitor. Even when writing a single byte to a read-only memory region, a set of operations both in the kernel and in the monitor is launched: the kernel issues SIGSEGV; the monitor catches SIGSEGV, sets the access write of the corresponding page to readwrite after reading and saving its initial values. These operations increase the total time to finish the initial writing operation. If parts of the program contain a series of such operations, for example in case of initializing a large memory area from a constant or from values read in a database, this increase may become very important. Column 5, row 3 of Table II on page 5 highlights a case where the execution time is increased to nearly 10 times. The main issue remains on how to avoid this decrease of speed while ensuring the recovering later.

B. CAPE

CAPE [START_REF] Renault | Parallelization of For Loops Using Checkpointing Techniques[END_REF], [START_REF] Renault | Distributed Implementation of OpenMP Based on Checkpointing Aided Parallel Execution[END_REF] stands for Checkpointing Aided Parallel Execution. It consists in modifying a sequential program so that instead of executing each part the one after the other on a single machine, parts are distributed over a set of machines to be executed in parallel. CAPE is not intended to automatically detect which parts of the original code have to be executed in parallel such parts are cited by programmers while using pragma directives of OpenMP. CAPE only aims at transforming a program so that it can be executed in parallel. A typical example is the distribution of a for loop. If the different iterations of a for loop are satisfying the Bernstein's conditions, i.e. any modified memory location is used only in the iteration loop where it is modified, it becomes possible to execute each loop iteration independently on different machines, compute the list of memory locations that have been modified in each iteration loop and include all these modifications inside a single process that will behave as if all iteration loops would have been executed locally.

While using ckpt [7], a complete checkpointer, CAPE has been proved its feasibility. Fig. 2 presents the general template for for loops in form for ( A; B; C ) D; when using the C programming language.

In this template, commands create ( beforei ) and diff ( beforei, afteri, deltai ) aim at extracting deltai, the memory areas that have been updated on hostx, after this host has finished its part of the loop. The use of a complete checkpointer requires an extra time for rendering this value and using an incremental checkpointer can avoid it. Another extra time is caused by the commands merge ( target, delta ) and restart ( target ) which serve to inject these delta into the memory of the initial host. Ability to directly execute this activity and then allow the process continue running can avoid this extra time. This leads to the requirement of the capacity to take and inject discontinuous incremental checkpoints in programs.

III. DISCONTINUOUS INCREMENTAL CHECKPOINTER IMPLEMENTATION

A. Principle

Based on the incremental checkpointing approach, the main idea for discontinuous incremental checkpointing is to add information to indicate which sections should be checkpointed by the monitor. This information is provided using pragma directives and may be implemented using different mechanisms like signals, breakpoints, etc. Three pragmas have been defined:

• pragma dickpt start • pragma dickpt stop • pragma dickpt save < f ilename >
Their behavior is described in Table I. In this table, pages refer to the pages of the virtual address space of the monitored process.

Assume a program consists of segments ( A, B, C, D ) in which, only B and D need to be checkpointed and two checkpoints are taken in B and one in D. Fig. 2 presents the prototype of the changed program, i.e the directives have been inserted to verify the above requirements.

B. Evaluation of performance

In order to highlight the impact of our new approach, we have developed a new checkpointer named Dickpt and measured its impact on a program computing the successive elements of a Markov Chain, see Fig. 3. Two cases were tested. The first one includes a directive to begin the checkpointing at location 0 (line 10) and takes a checkpoint at location 1 (line 23), while the second one avoids the checkpoint at location 1 and begins checkpointing at location 1. For both cases, one hundred state vectors are computed at location 3 (line 30) + set all pages to read-only status; + if it is the last checkpoint: change to checkpointing mode; -else: notice error; stop process. stop send "stop" back all pages to their original status. back all pages to their original status. to the monitor. save < f ilename > send "save" save the memory locations that have been modified notice error; stop process. to the monitor. to the current checkpoint;

if < f ilename > contains previous checkpoint: + merge current checkpoint to < f ilename >; else:

+ save current checkpoint to < f ilename >; set all pages to read-only status. and one checkpoint is generated after each computation. The testbed was composed of an Intel Core2 Duo E8400 running at 3 GHz with 3 GB RAM and operated by Ubuntu 9.10 based on Linux kernel 2.6.31-21-generic. Table II presents the performance evaluation for four vector sizes (N equals to 3320, 6640, 9960 and 13280 elements respectively). For each vector size, performance are measured 30 times (mean values are provided in the table). In order to avoid the pollution of disk effects on measurements, all data (the virtual address space of processes, checkpoints, etc.) are resident in RAM.

A # pragma dickpt start B1 # pragma dickpt save <filename1> B2 # pragma dickpt save <filename1> # pragma dickpt stop C # pragma dickpt start D # pragma dickpt save <filename2> # pragma dickpt stop
The first section of Table II presents the size of checkpoints at location 1 (i.e. just after the initialization -as the case of normal incremental checkpointer) and at location 2 (i.e. just after the computation of a new vector). This difference is the size of the transition matrix which is initialized at the beginning of the program. These data show how much disk space can be saved while abandoning the checkpoint at location 1 and, in the same way, how faster the checkpoint can be transfered over the network if necessary.

The second section of the table shows the time required to run the program without saving checkpoints, while saving all checkpoints and while saving location 2 checkpoints only. It highlights the fact that the overhead involved by the generation of location 2 checkpoints is very light (between 1.5% and 3.3% for 100 checkpoints, i.e. between 0.01% and 0.03% per checkpoint) compared to the overhead involved by the generation of both location 1 and location 2 checkpoints (the total execution time is multiplied by 8.5).

The third section of table provides the execution time to run the process restarting from loop iteration number 50. Two cases are envisaged: the first one uses all checkpoints, i.e. the program is restarted, suspended at the beginning of function main, all checkpoints are injected in the process and the execution resumes at loop iteration 50; the second one uses location 2 checkpoints only, i.e. the program is restarted, suspended after the initialization step, all location 2 checkpoints are injected in the process and the execution resumes at loop iteration 50.

The performance measurements show that avoiding location 1 checkpoints is always beneficial.

C. Advantages and drawbacks

While comparing with the normal incremental checkpointing technique, our new approach has the strong and weak points below:

• Performance: increase the speed of the program in both periods of checkpointing and recovering; decrease strongly the size of checkpoints. • Flexibility: allows to select the segments to be checkpointed in programs. The case of normal incremental checkpointing is obtained by setting a pragma dickpt start and a pragma dickpt stop as the first and the last instruction respectively in the checkpointed program. • More specifically for the case of CAPE: it can directly extract and allows to inject the delta, thus increase the performance of this paradigm. can not be merged to an unique checkpoint. So, many files are needed to contain the checkpoints of different checkpointing blocks. This drawback is important when checkpoints reference the same memory area.

IV. CHECKPOINT STRUCTURE OPTIMIZATION

The structure of a complete checkpoint is usually quite straightforward. After some very specific data like the content of registers and the size of the memory, the rest of a complete checkpoint is usually composed of the content of all the memory pages the one after the other one.

In the case of an incremental checkpoint, several cases have to be envisaged. All solutions are storing the content of registers. However, regarding the memory updates, the best solution really depends upon the granularity of data, which ranges from one byte to one page with the most interesting case at one word.

Memory granularity

There are two main drawbacks when the granularity is the page. The first one is that a complete page must be saved even though a single byte in the page has been modified, which is not really memory efficient. Considering the size of today disks, this may not be a problem unless a very large number of checkpoints have to be generated. The problem may have a more important impact if for examples these checkpoints have to be sent over the network, especially with a limited bandwidth. The second main drawback is that it provides no information on which bytes in the page have been modified effectively. The latter drawback definitively forbids any merge operation of successive incremental checkpoints.

Setting the granularity of the checkpoint to a single byte solves the memory inefficiency problem of the page granularity. However, it leads to other subtle problems, like for example the reference to memory locations that do not exist in the virtual address space of the process. Let < a, b, c, d > be four bytes stored at a memory location and representing a pointer in memory. After a first checkpoint, this memory location may contain < a, b ′ , c, d >. After a second checkpoint, the same memory location may contain < a, b, c ′ , d >. If, for any reasons, it is required to merge the two checkpoints (and this is typically the case with CAPE), the result becomes < a, b ′ , c ′ , d > which may not be part of the virtual address space of the process.

Setting the granularity of the checkpoint to a word (i.e. four bytes) is the best compromise as it solves the problem of memory space efficiency and does not introduce any pointer problem as described above. This solution is not the perfect solution. However, problems involved by setting the granularity of the checkpoint to a word has no significant impact on the execution of the program.

Finally, one can note that setting the granularity of the checkpoint to the entire virtual address space turns an incremental checkpointer into a complete checkpointer.

Incremental checkpoint content

Apart from the specific values also stored in complete checkpoints, an incremental checkpoint should be composed of the list of memory locations that have been modified since the beginning of the execution of the program, or since the previous checkpoint, and the last value for each of these specific memory locations. The simplest structure to store such a list is to save the one after the other one both the addresses and their associated value. However, since the spatial locality of data in most programs implies that a modification at a memory location increases the probability for adjacent memory locations to be modified, this way of storing data is not necessarily efficient.

Thus, in order to take advantage of the spatial locality of updates and therefore reduce the size of checkpoints, several alternative methods for storing memory updates have been identified:

• Single data. This case occurs when a single memory location has been updated. In this case, the only information to store are the basic address of the memory location and the content at the memory location. Data to store all information into the checkpoint are: < addr, value >

• Several successive data. This case occurs when more than one consecutive memory locations have been updated. For example, this is encountered when the content of an array has been modified. The best way to store all the information in this case is: • Many data. This occurs when lots of non-successive memory locations have been updated on a single page. In this case, instead of storing a large number of Single data and Several successive data elements, it is more efficient to store the address of the page, the list of memory locations on the page that have been modified and for each modified memory location the associated value. The efficiency of this solution resides in the mapping, i.e. the list of memory locations on the page. As this is a binary information for each data in the page, it can be represented using a single bit per memory location. For example, for a 4-kB page, the size of the map is 1024 bits (or 128 bytes) with a granularity set a word. < addr, map, [value...] >

• Entire page. This occurs when all memory locations on a memory page have been modified. This case is quite common when a new page is added to the virtual address space of a process. The best way to store the complete content of a page is: < addr, [value...] >

No size need to be provided in this case as it is implicitly known.

Table III compares the amount of memory needed to store updated data for all cases presented above. The size of a memory page is assumed to be 4 kB. Let a chunk be a set of contiguous memory locations that have been updated. Let c be the number of chunks in a memory page, let s i be the number of elements in chunk i and let u be the number of updates in the memory page. By definition, c i=1 s i = u. Fig. 4 shows a comparison of the amount of memory needed to store all updates in a 4-kB page as a function of the number of updated memory locations in the page. SD, MD and EP only depend upon the number of updated memory locations while SSD also depends on the distribution of the updated memory locations. As a result, Fig. 4 shows both the best case (SSD min ) that is when all updated memory locations are in a single chunk, and the worst case (SSD max ) that is the case when updated memory locations are distributed in the configuration that requires the maximum number of chunks. For 4-kB memory pages and 4-byte words, this maximum is given by:

⌊u/2⌋ if 0 < u ≤ 682 1024 -u if 682 < u ≤ 1024
One can note that when two successive memory locations have to be stored, the amount of memory needed to store the information for both Single data and Several successive data cases is the same. The most efficient solution, i.e. the one that reduces the most the memory usage, is identified this way. For each page, first the Many data representation is built. It requires at most 4228 bytes; second, a combination of Single data and Several successive data methods is built, having Single data chosen for isolated data and Several successive data chosen when at least two consecutive memory locations have been updated; third, the shortest representation between both computed is stored. Note that the Entire page method is left to the storage of new pages. From the expressions provided in Table III one can demonstrate that the Several successive data method is always the most interesting solution when the number of updates is smaller than 34. Then, there is a trade-off between the Several successive data method and the Many data method that depends on the number of chunks. Fig. 5 is a magnification of Fig. 4 for a number of updates in the range from 0 to 50.

Identifying the method

Considering that more than one method is used to store memory updates, it is important to identify which one was used when restoring the content of the checkpoint. A simple solution would have consisted in adding an extra integer or even a character before any data description or set of data description. However, in order to keep the size of the checkpoint as small as possible, it has been decided to add no extra byte to the checkpoint.

Instead, considering that all methods require an address as the first field and that these addresses are necessarily aligned on a boundary of a word, i.e. these addresses are necessarily a multiple of 4 or the last two digits of their binary representation are necessarily 00, it is possible to use this "free" space to store which method was used to store the data. In our current implementation, 00 is associated to Single data, 01 to Several successive data, 10 to Many data and 11 to Entire page. When restoring the content of a checkpoint, these two bits are reset to 00 after the storage method has been identified and before the address is effectively used.

V. CONCLUSION AND FUTURE WORKS

For the development of our distributed implementation of OpenMP using the CAPE paradigm, an efficient incremental checkpointer is required. This article presented our new approach of discontinuous incremental checkpointer. The initial implementation of this approach, Dickpt, has proved its efficiency in terms of size -the decrease of amount of memory required to store the checkpoints -and time to generate the checkpoints, to restart from a checkpoint or to send the checkpoint over the network. This approach led to very lightweight checkpoints, the size being in the order of very few kB while the size of the virtual address space of the process is in the order of tens or hundreds of MB. However, by the significantly changes due to the possibility and the nature of the checkpointer, new paradigms may be developed for CAPE and we are investigating in this way.

Apart from processor registers, the current implementation of our incremental checkpointer does not save system information about the process, like open file descriptors, sockets, POSIX semaphore or shared memory, etc. Somehow, this is not a real drawback as if such declarations are set outside of checkpointed segments, they could be re-executed in case of restoration. However, in the near future, these system data will be included and the overhead involved by the inclusion of each of them will be studied. In fine, we would like this incremental checkpointer to be completely customizable so that users would be able to store only relevant information.

Fig. 1 .

 1 Fig. 1. Template of CAPE for for loops.

Fig. 2 .

 2 Fig. 2. Pseudo-code for discontinuous incremental checkpoints.

Fig. 3 .

 3 Fig. 3. Program computing the successive elements of a Markov Chain.

Fig. 4 .

 4 Fig. 4. Amount of memory to store updates.

Fig. 5 .

 5 Fig. 5. Trade-off between SSD and MD.

TABLE I PRAGMAS

 I OF DISCONTINUOUS INCREMENTAL CHECKPOINTING TECHNIQUE.

				Monitor
	Pragma	Process	Checkpointing mode	Recovering mode
	start	send "start"	set all pages to read-only status.	find the next checkpoint:
		to the monitor		-if found:
				+ inject checkpoint to the monitored process;

•

  Change of the source code: in the role of a checkpointer, it is the most important drawback. Users have to insert the directives to indicate the regions being checkpointed.

However, when used in CAPE, this insertion is done by the CAPE's compiler. As a result, this drawback has no impact for CAPE's users.

• Fragmentation of checkpoints: checkpoints which are not taken in a single block (surrounded by a pair of pragma dickpt start and pragma dickpt stop)

TABLE III AMOUNT

 III OF MEMORY TO STORE UPDATES.

		Amount of memory
	Method	for a single chunk	for a page
	Single data (SD)	8	8 × u
	Several successive data (SSD)	8 + 4 × s	8 × c + 4 × u
	Many data (MD)	132 + 4 × u	132 + 4 × u
	Entire page (EP)	4100	4100

viet hai.ha@it-sudparis.eu

eric.renault@it-sudparis.eu

References to the memory are, unless otherwise specified, references to the virtual memory and not the physical memory. In the same way, the paper refers to virtual pages and virtual address spaces and not physical pages and physical address spaces respectively.


Viet Hai Ha
email: viethai.ha@it-sudparis.eu

Éric Renault
email: eric.renault@it-sudparis.eu

Design and Performance Analysis of CAPE based on Discontinuous Incremental Checkpoints

Checkpointing Aided Parallel Execution (CAPE) is a paradigm using checkpointing technique to distribute sequential programs equipped with OpenMP directives in distributed systems. In its first prototype, the use of a complete checkpointer strongly decreased global performance. This paper shows how the performance of the CAPE paradigm have been improved using discontinuous incremental checkpointing and provide an in-depth analysis of this performance.

I. INTRODUCTION

The architecture of parallel machines has drastically changed over the past fifteen years, from mainframes that were the typical solution for parallel computing at the beginning of the 90's to the clusters [1] at the end of the 90's or more recently to grids [START_REF] Foster | The Anatomy of the Grid: Enabling Scalable Virtual Organizations[END_REF]. Available tools to develop applications on top of these platforms also have evolved but differently. As two main architectures have been identified for parallel machines, shared-memory architectures on the one hand and distributed-memory architecture on the other hand, specific tools have been developed to cope with their specificities. One is OpenMP [3], developed for shared-memory machines and PVM, and the other is MPI [4], for distributed-memory systems. If the programming paradigm associated with OpenMP is quite simple to handle by programmers for its similarities with the more traditional sequential paradigm, the messagepassing paradigm associated with distributed-memory system is more difficult to convince a large public to use it. As a result, there have been several attempts to develop a compiler that automatically generates a version of OpenMP programs that is capable of running on a distributed-memory architecture. They can be divided into two categories.

The first category consists in using a Single System Image (SSI) in order to hide the distributed nature of the underlying architecture to the parallel application [START_REF] Karlsson | A fully compliant OpenMP implementation on software distributed shared memory[END_REF]. An SSI aims at providing an abstraction layer on top of a distributed system so that users and applications can use resources as they were parts of a single monolithic machine. Typically, this means that the set of processors is seen as an SMP or a single multicore processor; the set of available RAMs in each node is seen as a single memory; and the set of file systems is accessible as a single one. Several SSI are now available and mature with different capabilities and targeting different architectures. Some solutions for clusters are Genesis [START_REF] Goscinski | GENESIS: an efficient, transparent and easy to use cluster operating system[END_REF], Millipede [START_REF] Friedman | MILLI-PEDE: Easy parallel programming in available distributed environments[END_REF], Nomad [START_REF] Pinheiro | Nomad: A scalable operating system for clusters of uni and multiprocessors[END_REF] and Kerrighed [START_REF] Morin | Kerrighed: A Single System Image Clustet Operating System for High Performance Computing[END_REF]. A newer solution for grids is XtreemOS [START_REF] Morin | XtreemOS: a Grid Operating System Making your Computer Ready for Participating in Virtual Organizations[END_REF], a derivative product from Kerrighed. XtreemOS is still an ongoing work and also targeting clouds [START_REF]Contrail: Open Computing Infrastructure for Elastic Services[END_REF]. The main advantage of using an SSI to run an OpenMP program is that the program can run as is, with no need to recompile if an executable file is already available.

The second category consists in using a parallel library and translating OpenMP directives and memory updates to call to the parallel library functions. Two solutions have emerged as of today, one developed on top of MPI [START_REF] Basumallik | Towards automatic translation of OpenMP to MPI[END_REF] and the other one on top of Global Arrays [START_REF] Huang | Towards a more efficient implementation of OpenMP for clusters via translation to global arrays[END_REF]. The main criticism towards solutions based on a parallel library is that they have lots of difficulties to take into account all memory accesses. Typically, when a memory location is accessed through a differentiation or a set of differentiation, it is sometimes very difficult for the compiler to identify the data type associated to the memory area.

Apart from the above two categories, we have been developing CAPE (which stands for Checkpointing Aided Parallel Execution) [START_REF] Éric | Distributed Implementation of OpenMP Based on Checkpointing Aided Parallel Execution[END_REF] [15], a method that uses checkpointing technique to execute OpenMP programs on distributed architectures. The first prototype of CAPE proved the feasibility of the approach but the use of a complete checkpointer as the base tool strongly decreased the global performance. This article aims at showing how the performance of the CAPE paradigm have been improved using the discontinuous incremental checkpointer we developed and at providing an in-depth analysis of this performance.

The article is organized as follows: section II presents the principles inherent to CAPE. The next one focusses on the discontinuous checkpointer and develops how these principles have been modified to cope with incremental checkpoints. The last section before the conclusion is dedicated to the in-depth analysis of the performance measurements.

II. CAPE PRINCIPLES

CAPE, which stands for Checkpointing Aided Parallel Execution, aims at automatically transforming a parallel sharedmemory program so that it can be executed on a distributedmemory architecture. In the current implementation that we developed, CAPE is able to handle OpenMP directives provided in a C programming language program. However, CAPE is not language dependent and could be extended to any programming language and/or parallel library or tool.

The basic idea of CAPE is that while many researches have been conducted in order to develop checkpointing applications to save the state of a program, CAPE makes use of checkpoints in order to allow programs to run on a distributed-memory architecture instead of a shared-memory architecture. The main difference between these two architectures remains in the fact that two segments out of three (both text and data segments vs. the stack) are shared by the different threads belonging to a single parallel process while the two processes belonging to a single parallel application are executing in two completely different memory address spaces. For both architectures, stacks belonging to different threads are stored at different locations. And as a thread should not access the private data of another directly, there should be no portability problem from a sharedmemory architecture to a distributed-memory architecture. As most programs executing on distributed-memory architectures are SPMD, the text segment which is read-only by definition is not changed during execution and is therefore consistent among all the nodes. Thus, this segment involves no problem either. The situation is different for the data segment which memory locations may be accessed by any thread at any time. In the scope of CAPE, the virtual address space is taken into account as a whole and no difference is made among the different segments.

# pragma omp parallel for for ( A ; B ; C ) D

↓ automatically translated into

↓ parent = create ( original ) if ( ! parent ) exit copy ( original, target ) for ( A ; B ; C ) parent = create ( before i ) if ( parent ) ssh host x restart ( before i ) else D parent = create ( after i ) if ( ! parent ) exit diff ( before i , after i , delta i ) merge ( target, delta i ) exit parent = create ( final ) if ( parent )
diff ( original, final, delta ) wait for ( target ) merge ( target, delta ) restart ( target ) Figure 1 presents the effective transformation that is performed on a code that specifies a parallel for that has all loop iterations D satisfy Bernstein's conditions using OpenMP directives. The parent, i.e. the master node, is in charge of managing the slaves only and does not execute any loop iteration in the parallel part. However, this is not mandatory and the master node could also take part in the execution of one or more loop iterations. The translation is based on the following functions:

• create creates a checkpoint and saves it in the file provided as a parameter. The value returned by the function is used to identify whether the function has just created the checkpoint and returned, or the process has been created after resuming the execution from the checkpoint. This function is very similar to the fork system call, except that create returns TRUE after generating the checkpoint and FALSE after resuming the execution from the checkpoint.

• copy copies a file into another one.

• diff saves into the last file provided as a parameter the list of modifications that should be applied on the first file to obtain the second one.

• merge applies the list of modifications saved in the second file provided as a parameter to the checkpoint file provided as the first parameter.

• wait_for returns after the file whose the name is provided as a parameter is available.

• restart resumes the execution of the current process from the checkpoint file provided as a parameter.

Note that the operation that consists in resuming the execution of the checkpoints generated for each loop iteration, the line in italic in Fig. 1, is executed on the master node but delegated to an external process in charge of managing the distribution of processes on a set of remote resources. BOINC [START_REF] Anderson | BOINC: A System for Public-Resource Computing and Storage[END_REF], used in the scope of the Seti@Home project, is probably one of the most famous tool aiming at distributing works among a set of computing resources. For an in-depth description of CAPE, refer to [START_REF] Éric | Distributed Implementation of OpenMP Based on Checkpointing Aided Parallel Execution[END_REF] and [START_REF] Éric | Parallelization of For Loops Using Checkpointing Techniques[END_REF].

III. DICKPT AND A NEW MODEL FOR CAPE

The performance analysis of the implementation of CAPE based on a complete checkpointer showed that an important part of the program execution is spent in creating checkpoints, sending checkpoints over the network, computing the difference between two checkpoints, and injecting the previously computed difference into a process [START_REF] Mereuta | Checkpointing Aided Parallel Execution Model and Analysis[END_REF]. An optimization had been introduced by distributing the computation of the differences between two checkpoints on the set of nodes and then return to the master node the difference only instead of the complete checkpoint, but performance results still remained quite poor as at least one complete checkpoint had to be sent over the network. It clearly appeared that the unique viable solution consists in using incremental checkpoints only.

The main idea behind using incremental checkpoints is twofold: first, this allows to transmit far less data over the network; second, the time needed to deal with incremental checkpoints is more interesting. For example, instead of creating a checkpoint and then compute the differences between this new checkpoint and another one that serves as a reference, it is now possible to directly generate the set of differences as it is the checkpoint itself. Moreover, the use of incremental checkpoints also allows to avoid the copy of complete checkpoints that is time consuming.

Despite the availability of several incremental checkpointers, we decided to implement our own one in order to make sure it perfectly matches our needs [START_REF] Viet | Discontinuous Incremental: A New Approach Towards Extremely Lightweight Checkpoints[END_REF]. In fact, the implementation of CAPE based on incremental checkpoints requires the ability to suspend and resume the checkpointer. Thus, we developed DICKPT [START_REF] Viet | Discontinuous Incremental: A New Approach Towards Extremely Lightweight Checkpoints[END_REF] (which stands for DIscontinuous ChecKPoinTing) that allows to start and stop checkpointing at any location in the program. It is based on a buffer and a set of three primitives. The buffer aims at storing all the modifications that occurred on the process since the last time the checkpointer started or resumed its execution. These three primitives behave as follows:

• start clears the buffer and then starts or resumes checkpointing. Any modifications occurring on the process after the call to start are reported in the buffer. A call to start while the checkpointer is active results in clearing the content of the buffer which is definitively lost.

• stop stops checkpointing, i.e. any modifications that occurs on the process after the call to stop is not reported in the buffer. A call to stop while the checkpointer is not active is just discarded.

• create saves the content of the buffer in the file provided as a parameter. Several calls to create may occur inside a start/stop pair. In this case, the buffer containing the modifications that have been performed on the process is reinitialized for each call. There are two sub cases depending on the name of created files. The first case occurs when the file name matches the one of previous call. In this case the new file will be merged with the existed file. In the other case, the new file will be independently created. Function create may be called while the checkpointer is active.

For the rest of the paper, the meaning of function create is the one above.

Figure 2 presents the new version of the piece of code that is substituted to an OpenMP parallel for construct. The semantic associated to functions merge on this figure are exactly the same as the one presented for Fig. 1. The other functions are defined as follows:

• master returns TRUE when executing on the master node and FALSE when executing on a slave.

• last_parallel returns TRUE when the current parallel block is the last one of the entire program and FALSE otherwise.

• send transfers the content of the file provided as the first parameter to the node provided as the second parameter.

# • broadcast sends a file to all the slaves. This function can only be executed on the master node.

• receive waits for the file provided as a parameter to be available.

• inject updates the current process with the information provided in the checkpoint file provided as a parameter. Note that this function does not update the instruction pointer.

• wait_for waits and merges all the components of the file provided as a parameter.

Two assumptions have been made to make the template works. The first one is that the platform for the master node and the slaves are homogeneous. This is easy to achieve, especially today with the rapid growth of virtualization. The second assumption states that no slave process has interactions with its environment. This second assumption can easily be handled by intercepting the calls to system calls and returning the result of the execution of the system call on the master node. In fact, if the master node is the only one to execute system calls, it becomes easy to detect whether a system call had already been executed and thus avoid its execution the second time.

Apart from the use of incremental checkpoints instead of complete checkpoints, one of the most noticeable improvements between the original template and the one in Fig. 2 is that the process is never restarted. Checkpoints, which are far lighter than in the previous case, can only be used to inject the differences into a process and cannot be used to restart the process directly. Also note that this new template can be applied several times one after another inside a single program, or can be nested.

IV. PERFORMANCE EVALUATION

In order to validate our approach, some performance measurements have been conducted on a Desktop Grid. This testbed is composed of nodes including Intel (R) Core (TM) 2 Duo E8400 CPUs running at 3 GHz and 2 GB RAM, operated by Linux kernel 2.6.35 with Ubuntu 10.10 flavour, and connected by a standard Ethernet. In order to avoid as much as possible external influences, the entire system was dedicated to the tests during performance measurements.

The program used for tests is a matrix-matrix product for which the size varies from 3,000×3,000 to 12,000×12,000. Matrices are supposed to be dense no specific algorithm has been implemented to take into account sparse matrices. Each experiment has been performed at least 10 times and a confidence interval of at least 90% has always been achieved for the measures. Data reported here are the means of the 10 measures. I. A single core was used for the sequential execution of the program, while the OpenMP program took benefits of the two cores. One can check that results in the Table I are consistent as the execution time for both sequential and OpenMP versions are directly proportional to the cube of the matrix size. Typically, this means that no important cache effects have polluted the performance measurements, probably because almost all data were fitting into memory. Moreover, the speed-up obtained by OpenMP is 1.8 for the first three matrix sizes and 1.65 for the fourth one, which are expected values.

The execution of both the sequential version and the OpenMP version of the program on one of the nodes gives the result provided in Table

Figure 3 and 4 present the execution time in seconds of the matrix-matrix program for various number of nodes and matrix sizes. Note that, despite the fact that processors are dual core, a single core was used during the experiments. Three measures are represented each time: the left one is associated with CAPE using complete checkpoints, the middle one is also associated with CAPE but with incremental checkpoints, and the right one is associated with MPI. The MPI program has been developed for reference as exchanges to keep all processes consistent between nodes are kept minimal.

For both figures, two series of graphs are provided. The upper series is related to the master node, while the lower series is associated with the slave nodes. Each series is composed of four graphs:

• Init is the elapsed time between the beginning of the program and the beginning of the parallel for loop in the matrix-matrix product. On Fig. 2, these are all lines before the first one.

• Before is the time spent to create and send the checkpoints (lines 2 to 5) on the master. On slave nodes, this includes receiving and updating the slave process using the checkpoint (lines 14 and 15). For the specific case of MPI, this is the time to send data to slave nodes.

• Final is the time to generate the last checkpoint on the master node (lines 6 and line 7) and the time to do the job on the slaves (line 16 and line 17).

• Update is the time to receive all updates from the slave nodes and inject them in the master node (lines 8 and line 9). On slave nodes, this is the time to generate the incremental checkpoints and send them to the master node (lines 18 to 20). For the specific case of MPI, this is the time to send data to the master node.

Figure 3 presents the execution time for different number of nodes. The size of matrices are 9,000×9,000. However, similar trends are observed for the other matrix sizes. One can remark that the 3-node case apart, the execution time when using incremental checkpoints is always better than the execution time when using complete checkpoints. The larger the number of nodes, the smaller the execution time for both CAPE using incremental checkpoints and MPI. Moreover, the execution time for CAPE using incremental checkpoints is getting closer and closer as the number of nodes is increasing. The case for CAPE using complete checkpoints is different. When few nodes are used for the computation (up to 11), the execution time is decreasing as the number of nodes is increasing and the value is quite similar to the other two cases (CAPE using incremental checkpoints and MPI). However, for larger number of nodes, the execution time for CAPE using complete checkpoints is directly proportional to the number of nodes. This is due to the time needed to generate the checkpoints to be sent and the time to send these checkpoints over the network (there is at least one complete checkpoint for each slave node). This clearly justifies the use of incremental checkpoints for CAPE.

At first, the performance for three nodes may look strange as the execution time of the program with CAPE using complete checkpoints is better than the execution time with CAPE using incremental checkpoints. In fact, for small number of nodes, the amount of data transmitted over the network between the different nodes is almost the same for both complete and incre-On the master node. On the master node. mental checkpoints as in the case of incremental checkpoints slave nodes receive a big part of matrices. However, in the case of incremental checkpoints, processes are monitored in order to capture the memory pages that are accessed for writing. The monitoring of the slave processes involves a computing overhead that is reduced proportionally with the amount of computation, and therefore with the number of nodes, when a large number of nodes is used. Fortunately, this is not a problem for CAPE. Processors with 4 and even 8 cores are available on the market and, as a result, CAPE is targeting architectures with a larger number of nodes.

Figure 4 presents the execution time for difference matrix sizes. The number of nodes involved in the parallel machine is 31. However, the remarks below would be the same with other number of nodes. The figure clearly shows that the execution time for CAPE using complete checkpoints is directly proportional to the square of the matrix size, while the execution time for both CAPE using incremental checkpoints and MPI is directly proportional to the matrix size. This is due to the fact that the virtual address space of the processes is mainly composed of the matrices, and that the complete virtual address space is transmitted over the network for complete checkpoints. However, for CAPE using incremental checkpoints and MPI, the complete virtual address spaces are not transmitted over the network and only the data that have been updated during the computation of the matrix-matrix product are considered. Moreover, one can remark that the execution time for CAPE using incremental checkpoints and MPI are usually very close. This in-depth analysis of the performance results shows that globally the execution time for CAPE using incremental checkpoints is only 10% higher than the execution time for MPI, excepts for 3,000×3,000 matrices where the ratio is 1.3. Note that graphs (c) on Fig. 3 and4 do not show any data for CAPE with incremental checkpoints and MPI as the execution time for both is too small to be represented. Figure 5 shows the speedup of CAPE using incremental checkpoints for various number of nodes and matrix sizes. The red line represents the theoretical maximum speedup. The figure clearly shows that the solution is efficient with an efficiency (the ratio of the speedup over the number of nodes) in the range from 75% to 90%. Also, it highlights that the larger the size of the matrices, the higher the speedup, which was not the case with the complete checkpoint implementation.

V. CONCLUSION AND FUTURE WORKS

This article presented CAPE and more specifically the modifications that have been applied on the template algorithm to translate automatically parallel programs with OpenMP directives into a parallel program targeted for distributedmemory architectures together with the discontinuous incremental checkpointer we developed. An in-depth performance analysis is also provided that shows the legitimation of the incremental checkpointing approach.

At present, CAPE has proven its efficiency for the generation of code satisfying the Bernstein's conditions for distributed-memory architecture. In the near future, we have planed to go further the Bernstein's conditions and take into account shared variables.

Fig. 1 .

 1 Fig. 1. Template for OpenMP with complete checkpoints.

Fig. 3 .

 3 Fig. 3. Execution time (in seconds) vs. number of nodes.

Fig. 4 .

 4 Fig. 4. Execution time (in seconds) vs. problem size.

Fig. 5 .

 5 Fig. 5. Speedup vs. number of nodes.


Viet Hai Ha
email: viethai.ha@it-sudparis.eu

Éric Renault
email: eric.renault@it-sudparis.eu

Improving Performance of CAPE using Discontinuous Incremental Checkpointing

Originally, OpenMP was designed to develop parallel applications on shared-memory architectures. One of the advantages that made the success of OpenMP is the simplicity of the associated programming model. Checkpointing Aided Parallel Execution (CAPE) is a paradigm that uses checkpointing techniques to run parallel programs on distributedmemory architectures. In order to show its effectiveness, it has been used to develop a compiler to run OpenMP programs on distributed-memory architectures. The first prototype we developed proved the feasibility of the paradigm but the use of complete checkpoints led to poor performance. This was mainly due to the large amount of data to transfer and process. This paper presents the new prototype we developed for CAPE based on the discontinuous incremental checkpointing technique and an analysis its performance.

I. INTRODUCTION

There has been an extensive developement of parallel architecture systems for the last three decades, with the appearance of new concepts like clusters, grids and more recently, multicore processors and clouds. Tools to develop applications on top of these platforms also have evolved but differently. Setting aside objects such as threads and processes, MPI which was designed for distributed-memory systems and OpenMP for shared-memory architectures are the most common standards for parallel programming today. From the programmer's point of view, OpenMP is simpler than MPI as only a set of OpenMP directives need to be inserted to convert a sequential program into a parallel one. OpenMP also provides efficient mechanisms for data sharing and thread synchronization. Its main weakness (from a distributed-memory programer's point of view) is the limitation to shared-memory infrastructures. As a result, OpenMP is convenient for multicore and multiprocessor machines, but for the other systems such as grids, clusters and clouds, a transformation is required. CAPE, our paradigm, may be used to implement this transformation.

This article aims at showing how the performance of the CAPE (Checkpointing Aided Parallel Excecution) paradigm has been improved using discontinuous incremental checkpointing and providing an analysis of these performances. The article is organized as follows: the next two sections present how OpenMP has been ported on different distributed architectures and the principles associated with checkpointing respectively. Sec. IV presents the principles inherent to CAPE and the next section develops how these principles have been modified to cope with discontinuous incremental checkpoints. The last section before the conclusion is dedicated to the analysis of some performance measurements.

II. OPENMP ON DISTRIBUTED MEMORY ARCHITECTURES

There have been several attemps to make OpenMP programs running on a distributed-memory architecture [START_REF] Merlin | Distributed OpenMP: extensions to OpenMP for SMP clusters[END_REF]. They can be divided into two categories.

The first category consists in using a Single System Image (SSI) in order to hide to the parallel application the distributed nature of the underlying architecture [START_REF] Karlsson | A fully compliant OpenMP implementation on software distributed shared memory[END_REF]. An SSI aims at providing an abstract layer on top of a distributed system so that users and applications can use resources as if they were parts of a single monolithical machine. Typically, this means that the set of processors is seen as an SMP or a single multicore processor; the set of RAMs available in each node is seen as a single memory; and the set of filesystems are accessible as a single one. Several SSIs are now available and mature with different capabilities and targetting different architectures. Some solutions for clusters are Genesis [START_REF] Goscinski | GENESIS: an efficient, transparent and easy to use cluster operating system[END_REF], Millipede [START_REF] Friedman | MILLI-PEDE: Easy parallel programming in available distributed environments[END_REF], Nomad [START_REF] Pinheiro | Nomad: A scalable operating system for clusters of uni and multiprocessors[END_REF] and Kerrighed [START_REF] Morin | Kerrighed: A Single System Image Clustet Operating System for High Performance Computing[END_REF]. More recently, XtreemOS [START_REF] Morin | XtreemOS: a Grid Operating System Making your Computer Ready for Participating in Virtual Organizations[END_REF], a solution for grid has been developped. XtreemOS is derivated from Kerrighed and still an ongoing work now also targetting clouds [START_REF]Contrail: Open Computing Infrastructure for Elastic Services[END_REF]. The main advantage of using an SSI to run an OpenMP program is that the program can run as is, with no need to recompile if an executable file is already available.

The second category consists in using a parallel library and translating OpenMP directives and memory updates to calls to the parallel library functions. Two solutions have emerged as of today, one developed on top of MPI [START_REF] Basumallik | Towards automatic translation of OpenMP to MPI[END_REF] and the other one on top of Global Arrays [START_REF] Huang | Towards a more efficient implementation of OpenMP for clusters via translation to global arrays[END_REF]. The main criticism towards solutions based on a parallel library is that they have lots of difficulties to take into account all memory accesses. Typically, when a memory location is accessed through a dereferentiation or a set of dereferentiations, it is sometimes very difficult for the compiler to identify the data type associated with the memory area.

III. CHECKPOINTING

A. Principles and tools

When running, a process may crash at two different levels: hardware or software. Software problems are usually due to a bad use of the language that had not been detected at compilation time. Hardware problems occur when one of the critical components of the machine fails. If software problems can be tracked using some tools and corrected before a large and long-time running program is started, it is more difficult to track and avoid potential hardware problems. As a result, in order to avoid loosing the result of several hours, days or even weeks of computations, i.e. to insert fault tolerance into computing systems, some systems include a mechanism to regularly save the state of processes, called a checkpoint, so as to be able to resume their execution from the last checkpoint in case of any problem instead of restarting from the beginning of the execution. Typically, a checkpoint consists in saving a snapshot containing the application state, i.e. all the data that will be necessary to restart the process from this state.

The checkpoint may be performed at different levels in the system. User-level checkpointing requires no support from the kernel and is usually performed by the process itself. Kernel-level checkpointing requires the kernel to extract all the information about the process so that they can be saved on the disk. Both methods have advantages and drawbacks. The main advantage for user-level checkpointing is that quite portable from one system to another without the need of intervention the kernel. The main advantage of kernel-level checkpointing is that all data related to all processes are accessible. Moreover, there exists some hybrid mechanisms where kernel data are accessible from user space. This is the case of checkpointing tools using the /proc pseudo-filesystem under Unix.

There are two main categories of checkpointing techniques. Complete checkpointing aims at storing all the information related to the process, including the virtual address space, state registers, and sometimes extra information from the kernel like the list of open file descriptor. Incremental checkpointing [START_REF] Yi | Ickpt: An Efficient Incremental Checkpointing Using Page Writing Fault -Focusing on the Implementation in Linux Kernel[END_REF] aims at only storing the parts of the memory1 that have been updated since the beginning of the execution of the program or the last checkpoint. From a high-level point of view, this is perfomed by setting access rights to read-only to all memory pages in order to force the system to deliver a SIGSEGV signal the first time a page is accessed for writing. Upon reception of the SIGSEGV signal, a copy of the content of the page is stored and access rights to the memory pages are restored to their initial values. When a checkpoint is required, the content of all modified pages are compared to their initial content and the difference is stored in the checkpoint file. In order to perform these operations, each process that may be checkpointed has to be associated a monitor. Typically, this monitor is in charge of starting the process which checkpoints will be computed, catching the SIGSEGV signales, generating the checkpoint files and waiting for the terminaison of the process.

Various tools have been developed to checkpoint applications. Some examples are : Libckpt [START_REF] Plank | Libckpt: Transparent Checkpointing under Unix[END_REF], a transparent incremental checkpointing tool running at the user-level; TICK [START_REF] Gioiosa | Transparent, Incremental Checkpointing at Kernel Level: a Foundation for Fault Tolerance for Parallel Computers[END_REF], a transparent incremental checkpointing tool too but running at the kernel-level; DMTCP [START_REF] Ansel | DMTCP: Transparent Checkpointing for Cluster Computations and the Desktop[END_REF] takes into account the specificities of parallel applications including multithreaded ones and is running at the user level; and CLIP [START_REF] Chen | CLIP: a checkpointing tool for message-passing parallel programs[END_REF] have been designed to take into account the specific case of message-passing libraries.

IV. CAPE PRINCIPLES CAPE, which stands for Checkpointing Aided Parallel Execution, aims at automatically transforming a parallel sharedmemory program so that it can be executed on a distributedmemory architecure. In the current implementation we developed, CAPE is able to handle OpenMP directives provided in a C programming language program. However, CAPE is not language dependent and could be extended to any programming language and/or parallel library or tool.

The basic idea of CAPE is that while many researches have been conducted in order to develop checkpointing applications to save the state of a parallel program, CAPE makes use of checkpoints in order to allow programs to run on a distributed-memory architecture instead of a sharedmemory architecture. The main difference between these two architectures remains in the fact that two segments out of three (both text and data segments vs. the stack) are shared by the different threads belonging to a single parallel process while the two processes belonging to a single parallel application are executing in two completely different memory address spaces. For both architectures, stacks belonging to different threads are stored at different locations. And as a thread should not access the private data of another directly, there should be no portability problem from a shared-memory architecture to a distributed-memory architecture. As most programs executing on distributed-memory architectures are SPMD, the text segment which is read-only by definition is not changed during execution and is therefore consistent among all the nodes. Thus, this segment involves no problem either. The situation is different for the data segment which memory locations may be accessed by any thread at any time. In the scope of CAPE, the virtual address space is taken into account as a whole and no difference is made among the different segments. Figure 1 presents the main steps that are involved during the execution of a program using CAPE. Assume a program is composed of three parts. The first and the last parts are composed of a single thread, i.e. they are to be executed sequentially. However, the second part is a parallel part that shall be executed using three threads. The execution is as follows:

1) The program starts using a single thread. Let the node on which this part is executed be the master node. 2) After the execution of the sequential part, a checkpoint is generated and sent to three slave nodes. 3) On each slave node, one thread of the parallel part is executed. 4) After threads have finished their execution on slave nodes, each slave node generates a new checkpoint and computes the difference from the original checkpoint that was previously received on the node, i.e. any memory locations that have been updated is reported. 5) Each slave node sends back the difference to the master node. 6) After all differences from all slave nodes have been received, they are injected in the target process, i.e. the original process that executed the first sequential part. Figure 2 presents the effective transformation that is per-formed on a code that specifies parallel regions using OpenMP directives. This transformation uses two parallel sections for the example. However, it can be generalized to an as-large-aspossible set of sections [START_REF] Éric | Distributed Implementation of OpenMP Based on Checkpointing Aided Parallel Execution[END_REF] and to loops [START_REF] Éric | Parallelization of For Loops Using Checkpointing Techniques[END_REF]. In the present example, the parent, i.e. the master node, is in charge of both managing the slave and executing one thread in the parallel part. However, this is not mandatory. Assumes that P 1 and P 2 satify Bernstein's conditions. The translation is based on the following functions:

• create create a checkpoint and saves it in the file provided as a parameter. The value returned by the function is used to identify whether the function has just created the checkpoint and returned, or the process has been created after resuming the execution from the checkpoint. This function is very similar to the fork system call, except that create returns TRUE after generating the checkpoint and FALSE after resuming the execution from the checkpoint.

• copy copies a file into another one.

• diff saves into the last file provided as a parameter the list of modifications that should be applied on the first file to obtain the second one.

• merge applies the list of modifications saved in the second file provided as a parameter to the checkpoint file provided as the first parameter.

• wait_for returns after the file which name is provided as a parameter is available.

• restart resumes the execution of the current process from the checkpoint file provided as a parameter. Note that the operation that consists in resuming the execution of the first checkpoint generated in this example, the line in italic in Fig. 2, is executed on the master node but delegated to an external process in charge of managing the distribution of processes on a set of remote resources. BOINC [START_REF] Anderson | BOINC: A System for Public-Resource Computing and Storage[END_REF], used in the scope of the Seti@Home project, is probably one of the most famous tool aiming at distributing works among a set of computing resources. For an in-depth description of CAPE, refer to [START_REF] Éric | Distributed Implementation of OpenMP Based on Checkpointing Aided Parallel Execution[END_REF] and [START_REF] Éric | Parallelization of For Loops Using Checkpointing Techniques[END_REF].

V. NEW MODEL OF CAPE BASED ON DISCONTINUOUS INCREMENTAL CHECKPOINTS

The performance analysis of the implementation of CAPE based on a complete checkpointer showed that the larger part of the program execution is spent in creating checkpoints, sending checkpoints over the network, computing the difference between two checkpoints, and injecting the previously computed difference into a process [START_REF] Mereuta | Checkpointing Aided Parallel Execution Model and Analysis[END_REF]. An optimization had been introduced by distributing the computation of the differences between two checkpoints on the set of nodes and then return to the master node the difference only instead of the complete checkpoint, but performance results still remained quite poor as at least one complete checkpoint had to be sent over the network. It clearly appeared that the unique viable solution consists in using incremental checkpoints only.

The main idea behind using incremental checkpoints is twofold: first, this allows to transmit far less data over the network; second, the time needed to deal with incremental checkpoints is more interesting. For example, instead of creating a checkpoint and then compute the differences between this new checkpoint and another one that serves as a reference, it is now possible to directly generate the set of differences as it is the checkpoint itself. Moreover, the use of incremental checkpoints also allows to avoid the copy of complete checkpoints that was time consuming. Beside it, to avoid as much as possible the effect of checkpointer on the execution's speed of process [START_REF] Viet | Discontinuous Incremental: A New Approach Towards Extremely Lightweight Checkpoints[END_REF], only some sections of program have to be checkpoited. This is the reason for the developping our discontinuous incremental checkpointing technique with the two additional functions are start and stop. In this technique, the checkpointing is not continuously executed from the begin of program but only in the scope of pairs start and stop. In each such as pair, many demands of creating incremental checkpoints can be made by using create function. However, we believe it might be possible to implement CAPE using incremental checkpoints on top of any checkpointing tool. Figure 3 presents the new version of the piece of code that is substituted to an OpenMP parallel-sections construct. Beside the start, stop and create functions of checkpointer, the other new and changed functions are:

# pragma omp parallel sections

• master returns TRUE when executing on the master node and FALSE when executing on a slave.

• last_parallel returns TRUE is the current parallel block is the last one of the entire program and FALSE otherwise.

• send transfers the content of the file provided as the first parameter to the node provided as the second parameter.

• receive waits for the file provided as a parameter to be available.

• inject updates the current process with the information provided in the checkpoint file provided as a parameter.

Note that this function does not update the instruction pointer.

In this prototype, the first change is the execution sequential sections of program on all nodes of systems. This change aim for avoiding the sending large size complete checkpoints to resum program on slave nodes. The resume of program on master node is also removed by using the inject function. Finally, the deltas now can be created directly by using the new create function, that comsumes less time and memory space than by using the complete checkpoint version of both create and diff functions.

It is important to note that the template presented in Fig. 3 can be applied several times the one after the other one inside a single program, or can be nested. Also note that the same mechanism may be applied to for loops to generate a distributed-memory version of the program.

VI. PERFORMANCE EVALUATION

In order to validate our approach, some performance measurements have been conducted on a Desktop Grid. This testbed is composed of nodes including Intel (R) Core (TM) 2 Duo E8400 CPUs running at 3 GHz and 2 GB RAM, and operated by Linux kernel 2.6.35 with Ubuntu 10.10 flavor and connected by a standard Ethernet network.

The program used for tests is a matrix-matrix product for which the size varies from 3,000×3,000 to 12,000×12,000. Matrices are supposed to be dense with integers and no specific algorithm has been implemented to take into account sparse matrices. Each experiment has been performed at least 10 times and a confidence interval of at least 90% has always been achieved for the measures. Data reported here are the means of the 10 measures. The execution of both the sequential version and the OpenMP version of the program on one of the nodes gives the result provided in Table I. A single core was used for the sequential execution of the program, while the OpenMP program took benefits of the two cores. One can check that results in the Table I are consistent as the execution time for both sequential and OpenMP versions are directly proportional to the cube of the matrix size. Typically, this means that no important cache effects have polluted the performance measurements, probably because almost all data were fitting into memory. Moreover, the speedup obtained by OpenMP is 1.8 for the first three matrix sizes and 1.65 for the fourth one, which are expected values.

Figure 4 and 5 present the execution time in seconds of the matrix-matrix program for various number of nodes and matrix sizes. Note that, despite the fact that processors are dual core, a single core was used during the experiments. Three measures are represented each time: the left one is associated with CAPE using complete checkpoints, the middle one is also associated with CAPE but with incremental checkpoints, and the right one is associated with MPI. The MPI program has been developed for reference as exchanges to keep all processes consistent between nodes are kept minimal. Figure 4 presents the execution time for different number of nodes. The size of matrices are 12,000×12,000. However, similar trends are observed for the other matrix sizes. One can remark that the 3-node case apart, the execution time when using incremental checkpoints is always better than the execution time using complete checkpoints. The larger the number of nodes, the smaller the execution time for both CAPE using incremental checkpoints and MPI. Moreover, the execution time for CAPE using incremental checkpoints is getting closer and closer as the number of nodes is increasing. The case for CAPE using complete checkpoints is different. When few nodes are used for the computation (up to 11), the execution time is decreasing as the number of nodes is increasing and the value is quite similar to the other two cases (CAPE using incremental checkpoints and MPI). However, for larger number of nodes, the execution time for CAPE using complete checkpoints is directly proportional to the number of nodes. This is due to the amount of data that is transmitted over the network which is getting very important (there is at least one complete checkpoint for each slave node) even though the amount of data that are effectively interesting for each slave node is reduced. This clearly justifies the use of incremental checkpoints for CAPE.

At first, the performance for three nodes may look strange as the execution time of the program with CAPE using complete checkpoints is better than the execution time with CAPE using incremental checkpoints. In fact, for small number of nodes, the amount of data transmitted over the network between the different nodes is almost the same for both complete and incremental checkpoints as in the case of incremental checkpoints slave nodes receive a big part of matrices. However, in the case of incremental checkpoints, processes are monitored in order to capture the memory pages that are accessed for writing. The monitoring of the slave processes involves a computing overhead that is reduced proportionally with the amount of compution, and therefore with the number of nodes, when a large number of nodes is used. Fortunately, this is not a problem for CAPE. Processors with 4 and even 8 cores are available on the market and, as a result, CAPE is targeting architectures with a larger number of nodes. Figure 5 presents the execution time for difference matrix sizes. The number of nodes involved in the parallel machine is 31. However, the remarks below would be the same with other number of nodes. The figure clearly shows that the execution time for CAPE using complete checkpoints is directly proportional to the square of the matrix size, while the execution time for both CAPE using incremental checkpoints and MPI is directly proportional to the matrix size. This is due to the fact that the virtual address space of the processes is mainly composed of the matrices, and that the complete virtual address space is transmitted over the network for complete checkpoints. However, for CAPE using incremental checkpoints and MPI, the complete virtual address spaces are not transmitted over the network and only the data that have been updated during the computation of the matrix-matric product are considered. Moreover, one can remark that the execution time for CAPE using incremental checkpoints and MPI are very close. An in-depth analysis of the performance results shows that the execution time for CAPE using incremental checkpoints is only 10% higher than the execution time for MPI, except for 3,000×3,000 matrices where the ratio is 1.3 . Figure 6 shows the speedup of CAPE using incremental checkpoints for various number of nodes and matrix sizes. The red line represents the theoretical maximum speedup. The figure clearly shows that the solution is efficient with an efficiency (the ratio of the speedup over the number of nodes) in the range from 75% to 90%. Also, it highlights that the larger the size of the matrices, the higher the speedup, which was not the case with the complete checkpoint implementation.

VII. CONCLUSION AND FUTURE WORKS

This article presented CAPE and more specifically the modifications that have been applied on the template algorithm to translate automatically parallel programs with OpenMP directives into a parallel program targeted for distributedmemory architectures. Some performance analysis are also provided, proving the legitimity of the incremental checkpointing approach.

At present, CAPE has proven its efficiency for the generation of code satisfying the Bernstein's conditions for distributed-memory architecture. In the near future, we have planed to go further the Bernstein's conditions and take into account shared variables.

Fig. 1 .

 1 Fig. 1. The basic steps when execution OpenMP programs with CAPE.

Fig. 2 .

 2 Fig. 2. Template for OpenMP with complete checkpoints.

Fig. 4 .

 4 Fig. 4. Execution time (in seconds) vs. number of nodes.

Fig. 5 .

 5 Fig. 5. Execution time (in seconds) vs. problem size.

Fig. 6 .

 6 Fig. 6. Speedup vs. number of nodes.

  [START_REF] Morin | XtreemOS: a Grid Operating System Making your Computer Ready for Participating in Virtual Organizations[END_REF] The target process can resume the second sequential part of the program as if the part that have been executed remotely in parallel had been executed locally.

	# pragma omp parallel sections
	{
	# pragma omp section
	P 1
	# pragma omp section
	P 2
	}
	↓ automatically translated into ↓
	parent = create ( original )
	if ( parent )
	copy ( original, target )
	ssh host 1 restart ( original )
	P 1
	parent = create ( after 1 )
	if ( parent )
	diff ( original, after 1 , delta 1 )
	wait for ( delta 2 )
	merge ( target, delta 2 )
	merge ( target, delta 1 )
	restart ( target )
	else
	P 2
	parent = create ( after 2 )
	if ( parent )
	diff ( original, after 2 , delta 2 )
	exit

TABLE I EXECUTION

 I TIME (IN SECONDS) ON A SINGLE NODE.

References to the memory are, unless otherwise specified, references to the virtual memory and not the physical memory. In the same way, the paper refers to virtual pages and virtual address spaces and not physical pages and physical address spaces respectively.