Rabih Amhaz

Sylvie Chambon

Jérôme Idier

Vincent Baltazart

A NEW MINIMAL PATH SELECTION ALGORITHM FOR AUTOMATIC CRACK DETECTION ON PAVEMENT IMAGES

Keywords: Crack detection, minimal path, Dijkstra algorithm, non destructive control, pavement

This paper proposes a new algorithm for crack detection based on the selection of minimal paths. It takes account of both photometric and geometric characteristics and requires few information a priori. It is validated on synthetic and real images.

INTRODUCTION

Monitoring road surface conditions is an important issue in many countries. The objective is to detect surface distresses, like raveling and cracking, in order to plan effective road maintenance and to afford a better sustainability of the pavement structure. Human visual inspection has been gradually replaced by automatic data collection with specific imaging devices [START_REF] Wang | Automated imaging technologies for pavement distress surveys[END_REF]. In consequence, processing techniques have been then developed (for monitoring surface conditions) as a support of human visual control [START_REF] Chambon | Automatic road pavement assessment with image processing: Review and comparison[END_REF]. In this paper, only image based techniques are discussed.

The main difficulty for image processing stems from the fact that cracks are particular image features that only appear as thin, irregular dark lines buried into textured noise. Within the scope of automatic crack detection, two kinds of methods can be discussed: unsupervised and supervised [START_REF] Oliveira | Supervised crack detection and classification in images of road pavement flexible surfaces[END_REF][START_REF] Li | Pavement crack classification via spatial distribution features[END_REF]. Using a learning machine step [START_REF] Oliveira | Automatic road crack detection and characterization[END_REF] provides interesting results but, in this paper, we will work on fully automatic unsupervised techniques.

The methods based only on the photometric information, e.g., threshold methods, are difficult to handle in practice owing to the observed mono modal grey level distribution on the whole images [START_REF] Chambon | Automatic road pavement assessment with image processing: Review and comparison[END_REF][START_REF] Tsai | Critical assessment of pavement distress segmentation methods[END_REF][START_REF] Elbehiery | Surface defects detection for ceramic tiles using image processing and morphological techniques[END_REF]. Conventional contrast enhancement and/or equalization techniques may improve the visual rendering of the image but may also enhance local discontinuities within the crack pattern at the same time, that results in false and incomplete detections. Better performance and robustness against the image texture can be achieved when both photometric and geometric characteristics of cracks are exploited. As an example, mathematical morphological approaches were adopted to reduce the discontinuities (by using dilation operators) within the crack pattern and to remove false detections (by using erosion operators) [START_REF] Tanaka | A crack detection method in road surface images using morphology[END_REF]. But, the automatic implementation of the latter methods is made difficult because of the large amount of parameters to tune. Using filtering methods is a common approach [START_REF] Medina | Automated visual inspection of road surface cracks[END_REF] but even when using multiresolution, it is still difficult to have good performance in some cases, e.g., the French pavement images [START_REF] Chambon | Automatic road pavement assessment with image processing: Review and comparison[END_REF][START_REF] Subirats | Automation of pavement surface crack detection with a matched filtering to define the mother wavelet function used[END_REF]. Some methods introduce local constraints like geometric constraint in a Markovian modeling [START_REF] Chambon | Automatic road pavement assessment with image processing: Review and comparison[END_REF], or both proximity and continuity constraints in a tensor voting approach [START_REF] Zou | Cracktree: Automatic crack detection from pavement images[END_REF]. However, the constraints at the local scale may counteract the result at the larger scale. Some post-processing, e.g., the minimum spanning tree in [START_REF] Zou | Cracktree: Automatic crack detection from pavement images[END_REF], is then required to afford the detection of the whole crack network. The most recent approaches introduce a more powerful geometric constraint than previous methods: minimal paths that are supposed to be significantly darker inside the crack than outside the crack.

Using minimal paths has both the advantage of introducing a global photometric constraint and a global geometric constraint. Estimating minimal paths in of each pixel of the image is expensive and, in consequence, the existing approaches have proposed a strategy to reduce this cost. The first possibility is to select small subsets of pixels, based on manual selection [START_REF] Kaul | Detecting curves with unknown endpoints and arbitrary topology using minimal paths[END_REF] or automatic selection of points of interest [START_REF] Chambon | Detection of points of interest for geodesic contours: Application on road images for crack detection[END_REF], whereas the second one reduces the estimation of the path by introducing orientation and length constraints [START_REF] Nguyen | Freeform anisotropy: A new method for crack detection on pavement surface images[END_REF]. The first approach is too selective and the points of interest detected do not cover all the crack whereas the second approach is not able to detect cracks with fast variations of orientation. For all these reasons, in our previous work [START_REF] Amhaz | Automatic road crack detection bu selection of minimal paths[END_REF], we introduced a minimal path approach without any constraints on the orientation nor the length of the paths.

The scope of the proposed algorithm is to select endpoints at the local scale and then to select minimal paths at the global scale. Moreover, the minimal paths are estimated between a subset of pixels that covers all the crack and that is larger than the subset of points of interest used in [START_REF] Chambon | Detection of points of interest for geodesic contours: Application on road images for crack detection[END_REF]. The result obtained is a skeleton, i.e. a path with one pixel width in the center of the crack, as illustrated in Fig. 1(d). These results were encouraging but there are still some imperfections, such as: false detections that are assimilating as loops. Moreover, in order to qualify the size of the disorder, it is necessary to detect the width of the crack and this approach can only provide the skeleton. In this paper, we propose an enhanced version in order to cope with such deficiencies and to obtain a result like in Fig. 1(f).

Section 2 presents the proposed minimal path approach. The performance assessment in Section 3 includes a comparison with four other methods which have been processed on both synthetic and real images. Section 4 draws the conclusion and the perspectives.

MINIMAL PATH SELECTION

The most famous algorithm to calculate minimal path in graph theory is Dijkstra algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]. Assuming that the crack pattern can be detected by darker pixels than the image background, a path cost function is defined as the sum of grey levels along the path as follows:

C(s, d) = 1 card(C) d m=s I(m), (1)
where s is the source point, d the destination point, m is a pixel of the path and card(C) is the length of the path. The crack pattern is assumed to be a series of connected pixels with an arbitrary chaotic shape and length. The authors in [START_REF] Nguyen | Freeform anisotropy: A new method for crack detection on pavement surface images[END_REF][START_REF] Amhaz | Automatic road crack detection bu selection of minimal paths[END_REF] consider that the minimal path within a crack reaches a lower cost function than any other path within the image background. The strategy of using this information differs between the two papers. The authors of [START_REF] Nguyen | Freeform anisotropy: A new method for crack detection on pavement surface images[END_REF] estimate the minimal path from each pixel of the image with directional constraint (four orientations) and a fixed distance (30 pixels) in order to reduce time execution. The main feature of the approach is to consider that if one orientation gives different grey level distribution than the other orientations, the pixel is probably inside the crack. Consequently, authors select pixels instead of paths, and the connection information given by the estimated selected paths is lost.

As opposed to the latter, [START_REF] Amhaz | Automatic road crack detection bu selection of minimal paths[END_REF] proposes to use the information on both cost function and minimal paths throughout the process. Moreover, to reduce time execution, significant pixels are selected as endpoints of the minimal paths. Then, elementary minimal paths are computed at the local level without either direction or length constraints. The histogram of the costs of each path estimated between these endpoints presents a bimodal distribution which allows to choose an appropriate threshold for selecting the best minimal paths, i.e. paths really inside the crack. The first results show how approach manages to detect cracks with chaotic path and orientation changes compared to [START_REF] Nguyen | Freeform anisotropy: A new method for crack detection on pavement surface images[END_REF]. However, some defaults have been highlighted: the crack detection contains some loops, cf. gorithm used is able to attract a part of the path inside the crack while the other part is outside. This behavior causes some artifacts: that we call "spikes" and "loops". A spike is a part of path joining a crack to an outer endpoint. A loop is made of two spikes joining at the same endpoint.

4. Elimination of artifacts (spikes and loops), Fig. 1(e):

With the help of minimal paths estimated, we can detect the outer endpoints and select only the correct parts of the paths, i.e. inside the crack. Local analysis along the crack skeleton is performed to differentiate extremities, e i : red point, and sources of ramification, s i : green point. A spike is the path between e i and s i and a loop is the path between two s i . The cost function on each part of the path is studied and it is appropriate to apply the same threshold as step 3 to remove the outer parts of the paths.

Width detection, Fig. 1(f):

The crack skeleton at step 4 allows us to obtain reliable estimation of grey level distribution of the crack pixels. Local analysis is then performed along the crack skeleton which consists of iteratively aggregating the pixels with grey levels below the threshold S w = µ w + σ w where µ w is the mean and σ w the standard deviation of the grey levels of the skeleton pixels.

In practice, the proposed algorithm requires four parameters: the thresholds S a , S c and S w at steps 1, 3 and 5 respectively, and the size of the image subsets for local analysis, P at step 1. We choose P = 8 because it induces a reasonable computation time (few minutes). The thresholds S a , S w and S c are automatically matched to the statistics of the pixels from the image background (S a ), those from the skeleton cracks (S w ), and the statistics of the cost function (S c ).

PERFORMANCE ASSESSMENT

Data Set: To evaluate the performance of MPS we tested the algorithm on a data set of both synthetic and real images from the aigle-RN project : http://media.lcpc.fr/ext/pdf/sem/2008 jtr aigle.pdf

The 36 grey level images of size 1920 × 480 include most of the pavement types under various lightning configurations (with and without controlled lights) and different types of cracks (longitudinal, transverse, alligatoring) with some ramifications at some places.

We generate a new synthetic image which is an improvement compared to [START_REF] Chambon | Automatic road pavement assessment with image processing: Review and comparison[END_REF] where the synthesis of both the crack and the background (i.e., the road surface) is based on a bimodal histogram. Here to be more realistic, an artificial crack pattern is introduced within a real image. The pixels within the crack pattern are randomly generated and the associated grey level distribution obeys the pixel distribution of the real cracks that have been semi-automatically segmented. The width along the crack pattern has been fixed to either one or two pixels. Fig. 2 shows the resulting synthetic image with some ramifications and directional variations. Pseudo Ground Truth: The assessment of the algorithms can be established with a pseudo ground truth (PGT). In [START_REF] Chambon | Automatic road pavement assessment with image processing: Review and comparison[END_REF], the PGT consists of manually selecting the pixels which were believed to belong to the crack pattern, before merging the individual results from four different operators. We update this PGT by using semi-automatic detection: for each crack piece, two endpoints are manually selected and the crack pattern is estimated with Dijkstra path-finding algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]. Criterion: The quantitative assessment consists on computing the true positive (TP) (good detection), false positive (FP) (false alarm), and false negative (FN) and calculating the DICE index that is the harmonic mean of precision and sensitivity, which ranges between 0 (worst score) and 1 (best score):

DICE = 2T P 2T P + F P + F N (2)
Methods: As opposed to [START_REF] Chambon | Detection of points of interest for geodesic contours: Application on road images for crack detection[END_REF], the performance of the proposed minimal path selection method (MPS) has been compared to three other methods: a modeling approach (labelled (M) for Markovian modelling [START_REF] Chambon | Automatic road pavement assessment with image processing: Review and comparison[END_REF]), and two other minimal path approaches, namely the Free Form Anisotropy (FFA) by Nguyen [START_REF] Nguyen | Freeform anisotropy: A new method for crack detection on pavement surface images[END_REF], and the previous version of the proposed method, labelled (MPS0) [START_REF] Amhaz | Automatic road crack detection bu selection of minimal paths[END_REF]. Results and discussion: For both data sets, Markov-based method provides discontinuous crack segmentation owing to the sensitivity to the image texture, see Fig. 2(c) and 4(a). FFA method detects a continuous crack path, but the strategy with directional and length constraints clearly reveals the difficulty to detect the chaotic crack pattern and the fine structure of the crack, e.g., see the change directions and the width on the right of the image Fig. 2(d) and 4(b). MPS0 [START_REF] Chambon | Detection of points of interest for geodesic contours: Application on road images for crack detection[END_REF] provides a fair segmentation of the skeleton and the full-length crack, Fig. 2(e) and 4(c). Both loop and spike artifacts have been reduced. Moreover, we can appreciate the width refinement in Fig. 3(f) and 4(d) that is quite precise. In Table At this stage of the development, the drawback of the latter technique is mostly entailed by the computational time encountered by the use of the conventional Dijkstra algorithm. It can be found that the computer time increases a lot beyond P = 8, for step 2, and in consequence we choose this value. With this parameter, under Matlab programming, the MPS algorithm requires about 12 minutes for the processing of 1MPixels on a 2.7 GHz laptop computer with 8 GB RAM, presented in Fig. 4.

The general quantitative assessment is presented on Fig. 3 for the whole data set of field data. The MPS method gives the highest DICE rate compared to the three other methods; for example, it is twice the score of the markovian method.

CONCLUSION

This paper has presented a brief review of existing approaches for the automatic crack detection on pavement images. We introduce an improved version of an algorithm based on minimal path selection by reducing loop and spike artifacts in the crack detection and by adding the width estimation. Pixelbased assessment of the method has shown that the image segmentation is now more reliable than the compared methods. The method allows a very fine characterization of cracks which could be used for further monitoring refinement in the future. In consequence, MPS can detect cracks with variable widths along the skeleton of any form. The future work will focus firstly on testing this method on larger pavement images within the framework of Tomorrow's Road Infrastructure Monitoring & Management (TRIMM) European project Fig. 3. Mean DICE values versus computational cost (in minutes) obtained by the three methods presented in section 3 and applied on the 36 real images, as an example Fig. 4.

(http://trimm.fehrl.org/). Secondly, it is also expected to test the MPS approach on 3D data, which are collected with the latest generation of imaging systems, e.g., the LCMS device (www.pavemetrics.com) or the RoadScout device (www.radarportal.com.au). Thirdly, it is planned to improve the computational efficiency of the second step of MPS (section 2.2) by either GPU programming or using some newer versions of minimal path computation algorithms, e.g., [START_REF] Delling | Engineering route planning algorithms[END_REF].

  Fig. 1(e), and only the skeleton is detected.

Fig. 1 . 1 . 2 . 3 .

 1123 Fig. 1. The five steps from the original image (a) to the result (f) of the MPS method, wich are detailed in section 2.

Fig. 2 .

 2 Fig. 2. Results with a synthetic image (a) with ground truth presented in (b). (Green: True Positive, red: False Positive, blue: False Negative).

Fig. 4 .

 4 Fig. 4. Results with a real image (Green: True Positive, red: False Positive, blue: False Negative)

Table 1 .

 1 Results -DICE values for different methods applied to the synthetic image, see Fig.2.

	1, among


DVFS governor for HPC: Higher, Faster, Greener Georges Da Costa, Jean-Marc Pierson IRIT, University of Toulouse dacosta@irit.fr pierson@irit.fr Abstract-In High Performance Computing, being respectful of the environment is usually secondary compared to performance: The faster, the better. As Exascale computing is in the spotlight, electric power concerns arise as current exascale projects might need too much power to even boot. A recent incentive (Exascale at maximum 20MW) shows that reality is catching up with HPC center designers.

Beyond classical works on hardware infrastructure or at the middleware level, we do believe that system-level solutions have great potential for energy reduction. Moreover energy-reduction has often been neglected by the HPC community that focus mainly on raw computing performance.

In the literature, energy savings is achieved mainly by two means: Either processor load is the only metric taken into account to reduce processors frequency and to ensure no impact on raw performances; Or processor frequency is managed only at task level outside the critical path.

In this article we show that designing and implementing a DVFS (Dynamic Voltage and Frequency Scaling) mechanism based on instantaneous system values (here network activity) can save up to 25% of energy consumption while reducing marginally performance. In several cases, reducing energy consumption also leads to an increase in performances because of the thermal budget of recent processors. This work is validated with real experiments on a linux cluster using the NAS Parallel Benchmark (NPB).

Index Terms-HPC; Green; Energy; DVFS; Governor;

I. INTRODUCTION

Saving energy for High Performance Computing applications has gained interest since only a few years. Solutions widely accepted in other IT domains can not be directly transferred to HPC systems. In HPC, the key performance criteria is time-to-solution. Consolidation with virtualization and dynamic migration of virtual machines coupled with switching-off unused nodes, empowered in commodity clusters and cloud computing, are not acceptable because of their impact on performances and the high level of utilization of the HPC clusters. Applications are deployed on large scale infrastructure making solutions for embedded systems also not applicable.

Techniques for reducing the energy demand on HPC infrastructure are mainly based on hardware dynamic adaptation to the applications needs. For instance when an application is using the disk IO only for specific phases (usually initialization and loading phase, and finish phase and dumping results), disks can be switched into an energy efficient sleep mode for the rest of the time. The same applies for communication phases when the CPU can be slowed down without impacting the application makespan. Diverse techniques exist for detecting such possibilities, either before, during or after the execution of an HPC application.

In this article, we show the potential for energy savings using automatic adaptation to application behavior at runtime. We propose a simple algorithm (NetSched) for optimizing HPC energy-to-solution based on CPU frequency adaptation on the hosts of the infrastructure, and we validate our approach using well known HPC benchmarks. Our main contributions are the following:

• Development of system-level runtime monitoring of HPC applications enabling behavior detection for HPC applications;

• Development of an algorithm for automatic hardware adjustment aimed at reducing energy consumption without impacting time-to-solution. The rest of this article is organized as follows: Section II gives an overview of the different approaches for energy savings in the context of HPC applications. Section III details our methodology and our NetSched algorithm while Section IV describes our experiment setup and results. Section V discusses the impact of our results for HPC centers while Section VI concludes and gives perspectives to our work.

II. STATE OF THE ART

In HPC environments the main focus for reducing energy has long been to improve the power efficiency of the hardware [START_REF] Careglio | Hardware leverages for energy reduction in large scale distributed systems[END_REF], including the environment infrastructure (i.e. cooling efficiency). While incomplete, [START_REF] Liu | A survey of the research on power management techniques for high-performance systems[END_REF] gives a good overview of the literature on power management for high performance systems.

Another widely used solution for cloud computing is consolidation. But even with low-overhead virtualization techniques for HPC systems [START_REF] Huang | A case for high performance computing with virtual machines[END_REF], [START_REF] Tikotekar | An analysis of hpc benchmarks in virtual machine environments[END_REF], [START_REF] Verma | Power-aware dynamic placement of hpc applications[END_REF] consolidation is of no use on fully loaded systems.

In the literature, the method usually followed to reduce energy in HPC systems is to consider that HPC workload can be modeled as a graph of tasks. For tasks not on the critical path in terms of execution time, it is possible to reduce their processors' frequency. It leads to energy-savings and reduced performance for those tasks. However as they are not on the critical path, the makespan of the whole application is not affected. This technique used in Adagio [START_REF] Rountree | Adagio: Making dvs practical for complex hpc applications[END_REF] is more generally called slack reclamation [START_REF] Guérout | Energy-aware simulation with DVFS[END_REF], [START_REF] Aupy | Reclaiming the energy of a schedule: models and algorithms[END_REF], [START_REF] Wang | Energy-aware dynamic slack allocation for real-time multitasking systems[END_REF], [START_REF] Babaii Rizvandi | Some observations on optimal frequency selection in dvfs-based energy consumption minimization[END_REF], [START_REF] Wang | Towards energy aware scheduling for precedence constrained parallel tasks in a cluster with dvfs[END_REF], [START_REF] Kappiah | Just in time dynamic voltage scaling: Exploiting inter-node slack to save energy in mpi programs[END_REF], [START_REF] Etinski | Power-aware load balancing of large scale mpi applications[END_REF], [START_REF] Alonso | Dvfs-control techniques for dense linear algebra operations on multi-core processors[END_REF]. The main limits of this approach are two fold: the need for information on the applications structure, and the task granularity of the adaptation.

Other quite similar approaches consist in using information of running applications (beyond the graph of tasks) to set the hardware performances according to these. Most of them only consider that hardware is limited to processors and adaptation is limited to frequency scaling, while few consider network, memory and disk as well. The needed information can be given with the application in terms of communication patterns and resource needs [START_REF] Verma | Power-aware dynamic placement of hpc applications[END_REF], [START_REF] Pierson | On the Utility of DVFS for Power-Aware Job Placement in Clusters[END_REF]. They can also be retrieved for the whole applications or for phases of applications after a precharacterization process [START_REF] Freeh | Exploring the energy-time tradeoff in mpi programs on a power-scalable cluster[END_REF], [START_REF] Cappello | On communication determinism in parallel hpc applications[END_REF], or using a code instrumentation and/or analysis [START_REF] Hotta | Profile-based optimization of power performance by using dynamic voltage scaling on a pc cluster[END_REF], [START_REF] Freeh | Using multiple energy gears in mpi programs on a power-scalable cluster[END_REF], [START_REF] Panas | Tool support for inspecting the code quality of hpc applications[END_REF], [START_REF] Barthou | Performance tuning of x86 openmp codes with maqao[END_REF]. Application phases can be obtained and used at runtime within a modified code linked to an ad-hoc library [START_REF] Minartz | Managing hardware power saving modes for high performance computing[END_REF], [START_REF] Li | Hybrid mpi/openmp power-aware computing[END_REF] or without the need to adapt the application [START_REF] Da | Characterizing applications from power consumption: A case study for HPC benchmarks[END_REF], [START_REF] Landry | Harnessing Performance Counters for Predicting and Improving Energy Performance of HPC Systems[END_REF], [START_REF] Hsu | A power-aware run-time system for high-performance computing[END_REF]. In these approaches one setting is valid for the duration of one phase.

Classical DVFS (Dynamic Voltage and Frequency Scaling) at kernel level are usually based on CPU utilization. After each time-slot (100ms or less) processor frequency is adapted based on the recent CPU utilization. Frequency is chosen to optimize first performance then power consumption. They are not adapted for HPC workloads as CPU utilization stays most of the time at 100% for such workloads and thus processors are always at maximum frequency. Such approaches encompass classical linux governor (ondemand) or β-adaptation algorithm [START_REF] Hsu | A power-aware run-time system for high-performance computing[END_REF]. In these cases and more generally, sleep states are rarely used as they halt not only the processor but also other processing such as the interactions between the processor and the memory or the network.

A more generic but seldom-used approach is the one of Miser [START_REF] Ge | Cpu miser: A performance-directed, run-time system for power-aware clusters[END_REF] and Green Governor [START_REF] Spiliopoulos | Green governors: A framework for continuously adaptive dvfs[END_REF]. Authors propose to evaluate if memory or processor is the bottleneck resource at a particular time step (one second or less) and to change the processor frequency accordingly. If the bottleneck is the processor, its frequency is increased, if it is memory, it is decreased. This approach brings energy improvement with limited impact on performance for a large variety of workload without the need for internal information of the application. Our approach is a generalization of these as we propose a framework that consider not only memory but also any resource bottleneck with the same reactivity as the kernel approach. We will illustrate this flexibility by using network resource consumption in the experiment Section. One interesting point is that slack reclamation and bottleneck detection are compatible. Usually the latter can save energy based on a performance reduction budget given by the former.

III. DVFS FOR HPC, TIME-AND ENERGY-WISE

For the evaluation of this research work, applications come from NAS Parallel Benchmark (NPB) [START_REF] Bailey | The nas parallel benchmarks 2.0[END_REF]. This benchmark provides 7 applications (IS, FT, EP, BT, LU, CG and SP) with workloads being representatives of HPC applications. They exhibit a range of behaviors from an embarrassingly parallel code (EP) to LU decomposition of matrix (LU) with interleaved computations and communications phases. These applications are well studied in the literature and present well known communication and computing patterns. A. Task-level DVFS One of the goal of HPC programmers is to use at maximum the raw computing power of the hardware. For instance a classical goal is to overlap communications with computations. If this goal was perfectly achieved, it would mean that reducing raw computing power (by reducing CPU frequency) would increase the makespan (time-to-solution) of HPC applications so much that it would ultimately consume more energy globally.

Energy is computed as the product of makespan and mean power consumed. For instance, if a computer can run at either 1GHz (powersave kernel governor) or 2.6GHz (performance kernel governor), consuming respectively 150W and 250W, it leads to a computing power ratio of 2.6 and a power consuming ratio of 1.666. With such ratios, if an application is only limited by raw computing power, running at 1GHz would consume nearly 1.56 times more energy than at 2.6GHz.

But real applications are not that simple. To illustrate, Figure 1 shows the behavior of NPB with respect to change in processors' frequency. For instance, for IS benchmark, reducing frequency of all nodes from 2.6GHz to 1GHz leads to 35% increase in execution time only instead of the 160% expected if the limit was only raw computing power. In this scenario, the total energy is reduced by 19%: Indeed, mean power consumption is vastly reduced while time increases only slightly, making the product time-to-solution by mean power more interesting at low frequency than at high frequency for this application.

Those only interested in energy-to-solution metric (energy needed to finish a task) would run IS and FT applications at low frequency, leading to an energy decrease of nearly 20% at the cost of a time penalty of 35%. In HPC environment this time escalation is unacceptable. From these experiments, we understand that reducing frequency has a positive impact on energy-to-solution for IS and FT, while time increases do not correspond to the ratio of frequencies. We conclude that these two applications are not limited only by frequency nor are unrelated to frequency. But since a time increase is observed, raw computing power is, at least partially, a limitation.

B. Phase-level DVFS

Simply choosing for a whole application at which speed to run the processor is inefficient. At a finer grain, an application can be seen in a simplified modeling, in one of the following states:

• Computing • Communicating (network) • Disk or memory I/O • Idle Benchmark FT SP BT EP LU IS CG Time increase (%) 0 -3 -1 1 -2 2 0 Energy increase (%) 0 -3 -1 -1 -2 -1 -1 Fig. 2.
Comparing max frequency (reference, performance governor) and ondemand governor Fig. 3. Classical pattern of HPC application behavior. The length will be α + β seconds if using performance governor, and αλ + β seconds if using powersave, with λ > 1. λ is the ratio between maximum and minimum processor frequency.

The Idle case is already covered by classical approaches like the ondemand governor. This governor adapts the processor frequency as a function of the load in order to maximize efficiency. Usually HPC applications can not benefit from this governor since these applications' programmers tend to reduce idle times. Figure 2 shows that time and energy are roughly the same for ondemand and performance on classical HPC benchmarks: Nodes are rarely idle as time-to-solution and energy-to-solution are equals meaning that mean powers are equals. If mean powers are equals, we conclude that most of the time the ondemand governor is choosing the maximum frequency.

It is to be noted that most current MPI implementations are actively waiting for packets (polling) and thus applications stay only rarely in Idle state. As explained in the State of the Art, the only relevant case is when a distributed application can be described as a DAG. In this case it is efficient to change processor frequency to the lowest available or to sleep mode when a processor has no tasks. As previously discussed, this article focuses on the case where a task is currently running, in particular on the critical path where performance is of utmost importance.

Disk and memory I/O and network communications are symmetrical: In the following the article will focus on communication without loss of generality. Future work will consist in modeling in the same way other shared buses such as memory or disks.

C. NetSched

We build our approach on the weak hypothesis that during the execution of HPC applications, there is an oscillation between two behaviors, computing and communicating as shown on Figure 3.

This figure shows successive computing and communication phases cycles. If for one phase the time for computation is α and the time for communication is β while running at full speed, then the same execution at the slowest speed would last λα for the computation part (λ is the ratio between the two speeds) and would not change the communication part. If P 1 is the mean power consumption at full load at full speed, and P 2 is the one at slowest speed, the energies for a cycle are (α + β)P 1 and (λα + β)P 2 for respectively fastest and slowest processor speed.

To minimize energy consumption, it is more efficient to stay at maximum speed if

(α + β)P 1 < (λα + β)P 2 .
Obtaining α and β at runtime is difficult. We decided to use the application used bandwidth (which is easy to measure) to obtain the ratio α/β, using the relation (where B m is the maximum bandwidth of the link) :

B w = B m β α + β
Merging the two equations, we obtain

B w < B m λ -1 (λ - P 1 P 2 ) = B 1
Hence, when running at full speed, if the current bandwidth is lower than B 1 , from the energy consumption point of view it is more interesting to stay at this speed, otherwise it is more interesting to change to a lower speed.

The same reasoning gives B 2 as the threshold over which it is interesting to stay at low speed, and under which it is more interesting to switch to full speed.

B 2 = B m λ -1 (λ P 2 P 1 -1)
Figure 4 exhibits the incoming byte rate during the execution of each of the 7 applications from the NPB (values shown for one node and one run, horizontally scaled since each application has a different time-to-solution): Applications adapted to low frequency (IS and FT) communicate way more than others. This fits to the presented model: Lowering frequency while communicating decreases the energy.

D. NetSched implementation

In the following we tested our hypothesis that during communications phases frequency can be reduced without impacting computing performances. We designed and implemented NetSched, a program that adapts processor frequency during runtime based on monitored network load.

Based on the equations from Section III-C, we consider that if the communication bandwidth is over B 1 (resp. lower B 2 ) while the processor is at maximum (resp. minimum) speed, it is interesting to reduce (resp. increase) processor speed.

In order to avoid oscillating situations, levels will be respectively 10% over B 1 and 10% below B 2 . This creates an hysteresis to improve the stability of the system. The resulting NetSched algorithm is then (where IBR is Incoming Byte Rate):

• Every 10th of second, do:

-If processor at Slowest frequency and IBR ≤ .9×B 1 → Change frequency to Fastest -If processor at Fastest frequency and IBR ≥ 1.1×B 2 → Change frequency to Slowest At the moment NetSched is implemented as a Linux daemon using system calls to obtain network bandwidth values as well as changing the frequency. This daemon implementation follows the same philosophy of the Linux kernel governors (such as ondemand). A future step will be the integration of NetSched as a module in the Linux kernel itself.

Compared to the classical state of the art using whole tasks or detecting phases in the application, NetSched behaves like a kernel governor and takes decisions every 100ms.

IV. EXPERIMENTS A. Experimental environment

Experiments throughout this article were done on nodes from Toulouse Grid5000 site. Grid5000 [START_REF] Cappello | Grid'5000: a large scale and highly reconfigurable grid experimental testbed[END_REF] is a completely reconfigurable infrastructure where each node can be adjusted to the needs of the experiment.

Each node is connected to a powermeter able to measure power consumption every second. Those monitored nodes are bi Dual-Core AMD Opteron processors (2218) with 8GB of memory and Gigabyte Ethernet card. Processors are DVFSenabled and can run at frequencies between 1GHz and 2.6GHz.

Nodes run Debian, using 2.6.37 Linux kernel. Since the powermeter sampling frequency is at maximum 1Hz (one sample per second), the power measurement infrastructure for assessing our research work was set up to one second. MPI library is Mpich2. System-level measures are finer grained and by default collected every 100ms.

NPB class C problems are used. NPB classes are related to problem length. Class C problems are solved between half a minute to few minutes on selected nodes. These applications do not use disks during computation, as many HPC applications.

For this batch of experiments, 4 nodes were used, leading to 16 cores experiments. NAS Parallel Benchmark applications are configured to use 16 slots, one per core. Depending on the application, some limits are imposed on the number of slots: Some applications need a power of two, some need a square,... Therefore 16 cores have been used in order to have the same number of slots for the 7 applications.

In this infrastructure, λ = 2.6 as minimum frequency is 1GHz and maximum frequency is 2.6GHz. Bm = 1024 3 /8 as the network is Gigabit Ethernet, P 1 = 280 and P 2 = 152 (in Watts, as measured directly on the nodes).

Using these values, 1.1×B 1 ≃ 7.10 7 and 0.9×B 2 ≃ 3.10 7 .

Several policies have been tested on the infrastructure: For all the 7 applications, 4 settings of the governor for the CPU frequency (called DVFS policies in the following) were used, namely performance, powersave, ondemand, and NetSched. For each of these settings, the experiment was repeated 100 times, energy and makespan were monitored, the mean, standard deviation and slope deviation were computed. Therefore, for each application, 400 experiments were used to analyze the behavior of all 4 DVFS policies (including our proposed algorithm NetSched), leading to a total of 2800 experiments. In order to avoid bias the sequence of the 2800 experiments was randomly chosen.

For each block of 100 experiments (meaning for each application and DVFS policy, i.e. 28 blocks), the normalized standard deviation (standard deviation divided by mean value) was computed: 24 values are below 4%, and all 28 are below 7.5%, both for energy and makespan mean values (maximum are for SP and LU applications, shown in Table 5 for the performance policy). Despite the accuracy of the power monitoring infrastructure (sampling rate of our power measures is 1Hz), the standard deviation is still low, especially when considering that the duration of some applications is small in comparison (from 16s to 355s, see Table 5). For the IS application, finishing in 16s, a measure every 1s has an higher impact on accuracy than for SP finishing in 355s.

It can be noted that for some benchmarks like LU, the application consumes less energy with NetSched policy than performance policy and is also faster. Modern processors have fine-grain control of their thermal budget. When a processor heat exceeds a threshold, its internal frequency is reduced (at hardware level, whatever the operating system governor) in order to let it cool down below a temperature threshold. Using an energy-saving system such as NetSched allows the processor to go faster when needed because it cools down when possible. It results in overall faster runs on several benchmarks while still saving energy (LU, FT, SP) compared to the maximum frequency.

In the same way, we evaluated the normalized slope deviation of the energy and makespan values (computed using least square linear interpolation of values to obtain the slope, values shown are a percentage of the vertical change of this slope for 100 experiments to the mean value). This was done to check if these values were impacted by the sequence of jobs on the hosts (computing machines may heat up and their energy consumption might increase slightly due to this). The average slope of the measured values is almost zero (see Table 5), meaning that the impact of the sequence is negligible. Results are similar for the other DVFS policies than performance.

Performance governor sets the CPU frequency to the maximum for the whole duration of the experiment (2.6GHz on our infrastructure). Powersave governor sets the CPU frequency to the minimum for the whole duration of the experiment (1GHz on our infrastructure). Setting the governor to performance or powersave modes has no impact on the operating system since the frequency does not change over time.

The ondemand governor increases the CPU frequency to the maximum frequency when the CPU utilization overpass a threshold value. When CPU utilization decreases below this threshold, the governor decreases the frequency step by step: It sets the CPU to run at the next lowest frequency until reaching the lowest possible frequency. The CPU utilization is checked every time-step (100ms on our infrastructure) and the same algorithm is applied to dynamically adjust the CPU frequency to current process load. Like the two previous governors it runs inside the Linux kernel as a module.

NetSched governor has already been described in III-C. At a bird-eye-view it has the same behavior as ondemand, adjusting the CPU frequency to the actual behavior of the application. It adapts frequency up to 10 times per second.

The two governors ondemand and NetSched have an impact on the operating system since a monitoring of the load (for ondemand) or of the IBR (for NetSched) is done and changes in frequency performed. Despite this overhead we will see that results are promising.

B. Experimental results

Figure 6 shows the mean energy consumption on the left, and the makespan on the right. Graphs are normalized so that the reference (100) is set to be the performance policy.

Concerning the energy consumption, we observe that for IS and FT applications, energy consumption is decreased by about 20% with powersave and up to 25% for our NetSched algorithm while ondemand consumes the same energy than performance. For the remaining 5 applications (SP, CG, LU, BT and EP) powersave has higher energy cost (up to 50% increase for EP), while our NetSched has always better energy consumption than performance (except for EP with an increase of less than 1%) and is very close to ondemand (at maximum 3%). We conclude that from an energy point of view, our NetSched algorithm is almost always better than any other policy available. Compared to the ondemand that is also changing the CPU frequency at runtime, our strategy can save up to 25% of energy (see FT application).

Besides energy savings, it is important to check if the duration of the applications are impacted by the policies. For each application, not surprisingly, the powersave policy has a negative impact on the makespan: The frequency is lowered, the CPU takes more time to perform the computation. When the application is mainly composed of raw computation (like the EP application), the time is multiplied by 2.6. Comparing with other policies, we exhibit that our NetSched policy is always better (for 3 applications, and up to 4% for the LU application) or on the same level than the performance and ondemand governor. Only on the IS bench we observe a slight increase in the makespan (less than 5%).

Altogether, we conclude that on the studied applications, our algorithm is beneficial in almost all the cases, with a potential large impact on energy savings (up to 25%), a potential for better makespan on some cases (by a few %) while at worst increasing the energy of less than 1% and the makespan of less than 5%.

Using phase-level DVFS lets NetSched to be in most case more efficient than performance as it reduces processor frequency when processor is the less needed (during communication) while not reducing it when it would impact makespan. Makespan is then globally stable but mean power consumption is reduced, so energy-to-solution is reduced.

Compared to powersave, NetSched has smaller time-tosolution even if mean power is higher: While doing only communications their mean power consumptions are the same, but NetSched benefits from the fact that doing raw computations at maximum frequency is more energy-efficient than at minimum frequency.

Finally the comparison with ondemand has large similarity with performance as ondemand scarcely manages to reduce frequency for the applications at hand, as explained earlier.

C. Validation

Previous experiments show that for efficient HPC code (i.e. without idle time) using network bandwidth for adjusting the CPU frequency leads to improvements. In a more generic case, using at the same time load (ondemand-like), network (NetSched-like), and IO information would certainly lead to an energy efficiency improvement greater than the one obtained solely with NetSched. Currently most DVFS techniques take only load into account. Figure 7 shows energy consumption of NPB using performance as a reference. Without entering in the details of all governors tested, we notice that all of them (other than performance and powersave) are using only the load of the system to manage dynamically the CPU frequency. Most of Energy consumption (energy-to-task) for several schedulers that base their decision only on load. Reference is performance. Classical linux performance and conservative governors are present. them behave as performance as they do not detect any idle time (ondemand and conservative are present). Next HPC governors will need an holistic view in order to achieve maximal gains. Current implementation of NetSched uses only two processor frequencies, but the model can be applied to any number of frequency levels using the same methodology.

One particularly interesting point is that using the model designed in Section III-C, the reduction in energy consumption should be correlated with an increase in execution time as shown on Figure 8. In real cases, Figure 6 shows that most of Fig. 8. Theoretical slowdown of applications as a function of computation percentage using NetSched. Worst case is reached at about 45% of computation (using values of Section IV-A).

the time this increase is absent but for one case. The case of FT is particularly interesting as it shows the best improvement in energy consumption without performance penalty. This property is linked to the communication pattern. A significant slowdown would appear only if the application behavior is a mix of communication and computation close to the point NetSched changes the frequency from minimum to maximum (at about 45% using our environment, seen on Figure 8). This limit is actually when (α + β)P 1 = (λα + β)P 2 . In this case the slowdown would be P 1 /P 2 (i.e. 1.8 in our experimental environment, 1.6 taking into account the hysteresis). As seen Fig. 9.

Communication pattern during a run of FT using performance governor in Figure 9, FT does not follow any pattern and is rarely in this region, hence not suffering much from this slowdown.

Furthermore it must be noted that these results were obtained using 16 slots. A larger scale would increase the ratio communication over computation. In this case NetSched would exhibit even more savings, following this ratio.

V. IMPACT ON HPC CENTERS

System administrators of HPC centers are confronted with a dilemma: On the one hand their users require more and more computing power (and often obtain budgets for the hardware) and are not ready to trade any performance loss for energy concerns; On the other hand they have to handle two problems: (1) their operational cost is limited by external factors (like financial stress) where the operational cost includes costs for the electricity and costs for the staff. (2) their energy provider is capping their potential instantaneous power to the physical limits of the power plants or the electrical wires bringing the energy to the data center.

In this perspective, our proposal has several merits:

• Reducing the energy consumption of HPC applications leads to lower operational energy costs. Given a budget limit, this means that more computations can be done for the same price, especially when the machines are managed on a pay-per-use perspective.

• It allows to make more computations with the same physical limit on maximum power usage (power capping), this gain will depend on the particular application.

• The operating system is adjusting automatically to the actual applications on the machines, without the loss of performances from a user point of view, and without any additional staff commitment.

• It does not involve any change in the HPC application.

• It is fully complementary with other approaches at the hardware level (taking more energy efficient hardware and infrastructure) and at the middleware level: Indeed, acting at the machines operating system level allows our approach to be transparent from its environment. Also, every watt saved at the lower level of an infrastructure has an indirect impact on the other levels as well (including the cooling infrastructure). The goal of exascale computing for a 20 MW power budget is achievable only when all the leverages are used and combined together. This improvement is not sufficient, but is one of the pieces needed to achieve it. Many HPC centers are not prepared for higher power demands (on the energy provider point of view) and reducing every watt is a necessary step to be able to handle more and more complex applications and computing power. We do believe that our strategy is a stepping stone towards this goal.

ACKNOWLEDGMENTS

Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr)

VI. CONCLUSION AND PERSPECTIVES

The main contributions of this article are two-fold. First it shows that having an holistic view of the system instead of relying only on load leads to improve energy efficiency without sacrificing performances for HPC applications. Second it provides the model and algorithm of a decision process reducing energy consumption based on network utilization. Experiments on NAS Parallel Benchmarks show that large energy savings can be achieved (up to 25%) without impacting the performances of the applications in most of the cases (even increasing them on 3 cases, up to 4%) with only one case where the performance is decreased (less than 5%).

The proposed method is complementary and compatible with other methods proposed for HPC applications based on global applications characteristics (using expected slacks in DAG, synchronizing different tasks,...) since it runs at the lower level of the operating system.

The validation of our approach exhibited in this article must be confronted with several other benchmarks and real applications, in order to pass from an application to a behavioral perspective. The NetSched algorithm is very simple at the moment while achieving already good results. We want to check several directions to extend its scope and to limit the rare situations when slight increases in energy or time are witnessed. Among those, we will first merge it with the ondemand governor in order to be able to manage idle time and network usage. We will also increase the number of possible frequencies, from the two currently used in our proof of concept to an arbitrary number. The resulting governor will be able to manage larger use-cases, not only limited to wellwritten HPC applications. The goal of future experiments is to run large scale applications. Then, other components will be included, first one being an IO module and a memory module following the same idea than the network one.

The NetSched algorithm is currently implemented in userspace and will benefit from being in kernel-space. It would reduce its footprint by reducing the number of system calls. Also, constants B 1 and B 2 are easy to compute but work is still to be done to evaluate them automatically or to adjust them on the fly.

Finally merging NetSched with a slack reclamation algorithm is the next step. Depending on the constants B 1 and B 2 it is possible to model the slowdown and thus to optimize even more energy consumption outside of the critical path.

An interesting perspective will also be to experiment on heterogeneous architecture such as big.LITTLE in order to generalize our concept of running platform. It will done by considering a parallel between different architectures and different frequencies in our current model.

Fig. 4 .

 4 Fig. 4. One example of values of netRECVbyte for each application (left performance, right powersave)

Fig. 5 .Fig. 6 .

 56 Fig. 5. Mean energy consumption, makespan, standard deviation, slope deviation for performance policy.