Oliver Trachsel

Thomas R Gross

Supporting Application-Specific Speculation with Competitive Parallel Execution

Parallel systems allow sequential programs that demand the highest possible performance or output quality to execute different versions of program parts in parallel to dynamically select the best version (i.e., the fastest or the one that produces the highest quality). The close coupling of multi-core systems offers new opportunities to explore such speculation. We discuss here how competitive parallel execution (CPE) supports such applicationspecific programmatic speculation. The key insight is that variations of the same program compete against each other during application-specific phases. These competing variants execute in complete isolation, thereby changing localized program state-comparable to a very coarse-grained transactional model. The state modifications of exactly one of these variants are committed and made globally visible based on an application-specific quality metric.

The paper discusses operating system and architectural features to support and further extend the applicability and versatility of application-specific programmatic speculation. It also motivates the need for more research on how future systems can accommodate the diverse requirements of speculative approaches at different abstraction levels.

Introduction

A software developer usually has many options on how to solve a problem at hand. Different algorithms, parameters, data structures, and implementations come with their respective properties in terms of performance or output characteristics. Similarly, a user usually must configure a set of parameters when running a program. A good choice of parameters for both the programmer and the user (in terms of some situation-specific quality metric) often varies with the program's actual data input, and often cannot be determined without actually trying out different possibilities.

Application-specific programmatic speculation enables sequential programs to explore different execution paths simultaneously at run-time, taking advantage of the parallel processing power of modern multi-core and future many-core systems. The programs can thereby improve their performance or the quality of computed results. Suitable programming models and run-time support are required to enable many programmers to safely add such speculation to their programs. A central aspect to application-specific speculation models are isolation guarantees that relieve the programmer from worrying about possible side-effects between simultaneously explored execution paths. Such guarantees are especially important in the context of modern, highly complex programs, where a programmer is often not aware of the inner workings of the whole system, with all its components, underlying libraries, and the associated interactions. Due to this program complexity, manually modifying a program and using a traditional parallel programming approach to enable the exploration of alternative executions is a complex undertaking, that is often not considered worthwhile.

Competitive parallel execution (CPE) [START_REF] Trachsel | Variant-based competitive parallel execution of sequential programs[END_REF] is an instance in the design space of application-specific speculation models. In the CPE model, variations of the same program compete against each other during certain execution phases. Each execution path explored in parallel has a completely isolated view on the program state and all modifications are only visible locally to the specific execution path. At the end of each competitive execution phase, the resulting program state of one of the alternative execution paths is made globally visible and the program proceeds from this state. This effect isolation makes extending a program to use CPE particularly simple, as there is no need for complex reasoning on data sharing, mutual exclusion, data races, and other issues inherent to parallel programming.

We implemented a prototype CPE system to demonstrate that effective and efficient isolation guarantees can be provided by leveraging features of current operating systems. Additional features at the operating system and architecture level would enable even more powerful and versatile programming models and run-time systems, both in terms of performance and capabilities. CPE is a first step in the direction of supporting more general application-specific programmatic speculation, where programs can exploit idle processing power with minimal implementation complexity to pursue optional computations.

Depending on the underlying architecture and operating system, speculation may increase the energy consumption of a program. It needs to be decided on a case-by-case basis if the gain in terms of quality and performance outweighs this cost.

In earlier work [START_REF] Trachsel | Variant-based competitive parallel execution of sequential programs[END_REF] we have demonstrated how a subset of the competitive execution model and system can be leveraged to increase the performance of sequential programs. The present paper builds on top of that work and extends the CPE model to be applicable in a broader range of scenarios by giving the program more control over which of multiple speculative execution paths is committed and made globally visible. A similar concept, programmer-controlled competitive execution, has been described in [START_REF] Trachsel | A platform for competitive execution[END_REF] as an idea for future work. This idea has been adapted, implemented, and evaluated for the present paper.

Programmatic Speculation with CPE

The goal of application-specific programmatic speculation is to give programs a means to easily explore different alternate execution paths in scenarios where it is unclear which one of a set of algorithms, implementations, parameter sets, or heuristics is best suited to address a given problem. Application-specific speculation is not a general approach to parallelize applications, but rather fits for specific categories of applications, such as:

• Algorithmic variants -multiple algorithms or algorithm implementations exist and performance or quality characteristics depend on the input data. This group includes parametrized algorithms, heuristics-based algorithms, and randomized algorithms; • Transformation tasks -data must be transformed from one representation into another, and some properties of the output depend on the configuration of the transformation method; • Search problems -where the search space can be partitioned among different speculation units.

The CPE model needs strong isolation guarantees for speculative program variants to remove the need for an in-depth reasoning and understanding of issues that make traditional parallel programming intrinsically hard, such as data sharing, data races, and locking. Sections 2.1 and 2.2 describe the CPE programming and execution model in more depth, and Section 2.3 describes how features of modern operating systems and architectures can be leveraged to implement an efficient CPE runtime system. Modifying existing programs to enable application-specific speculation with CPE can be a very simple process, as illustrated by the video encoding example in Section 3.

CPE Programming Model

Our CPE API consists of three simple function calls to delimit the parts of a program where CPE is to take place: void* cpe_start(int variants, void *v1, ...); void cpe_finish(); void cpe_finish_wait(double quality);

These functions define the start end end points of competitive code sections. cpe start() forks program execution into multiple competing execution flows. The call returns in multiple program variants, each one receiving the corresponding variant descriptor (vN) as return value. The variant descriptor can be an arbitrary, application-specific value, e.g., a pointer to a configuration for a parametrized algorithm or a pointer to a function to be called in the program variant.

Competitive execution takes place until one program variant invokes the second function call, cpe finish(), or until all program variants invoke the third call, cpe finish wait(quality). In the first case, competing program variants are aborted and the program proceeds from the state of the program variant that called the cpe finish() function. In the second case, the completion of all competing program variants is awaited before the program proceeds from the state of the program variant with the highest quality value.

To enable CPE for an existing program it suffices to place these function calls at the appropriate places in the program and link the program with a CPE run-time library.

Execution Model

Upon forking program execution into multiple competing execution flows, the resulting program variants run in complete isolation from each other, and the effects and program state changes by one program variant are not visible in the other variants. These isolation semantics make reasoning about the behavior of variants particularly easy, as the program does not have to consider side effects of competitive execution versus sequential execution. If any of the program variants tries to perform an I/O operation that cannot be contained by the runtime system, competitive execution is prematurely aborted and program execution proceeds sequentially from the state of the program variant that performed the I/O operation.

A program can selectively relax these strict isolation semantics by allowing specific I/O operations (e.g., output to the console, reading or writing from/to specific files) and by explicitly sharing specific data among program variants. At the end of a competitive execution phase, only the program state and effects of a single program variant remain visible to the program, except modifications to explicitly shared data and effects of explicitly enabled I/O operations. The CPE programming paradigm thus defaults to complete isolation of parallel entities (program variants) and allows for selective relaxation of this isolation. This behavior is in contrast to programming models based on the shared memory principle, where any effects of parallel entities (threads) are globally visible per default and special measures have to be taken to contain some of these effects (e.g., through the usage of threadlocal variables or by protecting shared resources with locks). On the one hand, such a model where the default is complete isolation may have its restrictions and certainly has different applicability than a shared-memory model. On the other hand, the model makes it much easier to reason about the behavior and correctness of a program, because it requires explicit identification of resources that are not isolated from other speculative units and from the outside world.

Implementation

Our prototype CPE run-time system is a user-space library, but is closely bound to the operating system. (An earlier prototype of a system that in part provided similar functionality, and that was integrated into the operating system itself is presented in [START_REF] Trachsel | A platform for competitive execution[END_REF].) Program variants are represented as separate processes and the run-time system leverages the UNIX process model (where new processes are created as copies of existing processes) and the virtual memory management subsystem (which employs a copy-on-write approach to efficiently guarantee that memory modifications remain local to one program variant). The implementation thus uses processes rather than threads to obtain strongly isolated parallel entities. A similar path is taken, e.g., by the Grace system [START_REF] Berger | Grace: safe multithreaded programming for C/C++[END_REF] to obtain safe concurrent programs.

The run-time system monitors I/O operations of competitive program variants through a system call inter-positioning mechanism. System calls with side effects that are not explicitly enabled by the program are intercepted and the program resumes single-variant sequential execution. System call interception is currently realized through the operating system's process tracing facility, which results in a context switch upon each system call by a program variant. Basic support by the operating system to perform a pre-filtering step and avoid a context switch for uncritical and explicitly enabled system calls would lead to performance benefits for system call intense applications.

More details on the implementation of the prototype run-time system are provided in [START_REF] Trachsel | Variant-based competitive parallel execution of sequential programs (extended version)[END_REF].

Performance characteristics

This section gives a brief insight into the performance characteristics of the current run-time system prototype. The measurements presented in this section have been performed on an Intel Xeon system with two quad-core processors running at 2.26GHz. The processors (Intel E5520) are based on the Nehalem micro-architecture. Each core has a private L2 cache of 256 KB and the four cores on a processor share a L3 cache of 8 MB. The system has 12 GB of memory installed.

The left chart in Figure 1 shows the time it takes to create and terminate 1 to 8 CPE variants. This time varies between 55µs and 368µs, depending on the number of competing variants. These times corresponds to an overhead of approximately 50-80 µs per variant. The creation and termination overhead is constant and is therefore amortized over longer periods of competitive execution.

The right chart in Figure 1 shows the time required to intercept and inspect a system call invoked by a program variant. The time is measured by averaging the total time overhead to execute Figure 3. Execution time overhead due to copying of memory pages for 100 MB to 1000 MB write sets per variant, for 1-8 variants. 100,000 system calls per variant. The interception time varies between 5.7µs in the single-variant scenario and 1.9µs in the 8-variant scenario. The decrease in time overhead with increasing number of variants is a result of interleaving. This interleaving is possible because one part of the work to intercept a system call is performed on the CPU where the program variant is running, and another part on the CPU where the intercepting process is running.

Figures 2 and3 show the execution time overhead due to copying of memory pages. Pages or copied to maintain variant-private program states. A variant-local copy of a memory page is created upon the first write to the page. The chart in Fig-ure 2 shows the relative overhead if each of 1-8 variants writes to 1 MB or 10 MB worth of memory during a 1s period relative to a singlethreaded non-CPE program that writes to the same amount of memory pages. The chart in Figure 3 shows the same data for write sets between 100MB and 1000MB. The overheads for a 1 MB write are below 0.01% for any number of variants. In the 10 MB case the overhead is always below 0.9%. For the bigger write sets, the execution time overheads are approximately 6% (100 MB), 11-13% (200MB), 22-26% (400MB), and 55-76% (1000MB).

These performance properties aid in deciding for a given scenario if application-level speculation with a CPE-like approach is practicable in terms of performance. Especially the memory behavior of an application should be taken into consideration. A CPE-like systems is well suited for applications with good locality properties with regards to modified memory locations. For such applications, the presented CPE run-time system prototype provides a low-overhead means to simultaneously explore multiple alternative execution paths.

Application Example

We have modified x264 [START_REF]a free h264/avc encoder[END_REF], a modern H.264 video encoder, to illustrate the applicability and ease of use of a CPE-like approach for application-specific speculation, and to study the performance of the CPE run-time library. In this example, CPE is used to increase the picture quality of the encoded output video. Up to eight program variants, which use different encoding configurations, compete against each other for the encoding of each video frame. After encoding each frame, the program variant that produced the best picture quality relative to the original frame is selected and execution proceeds from this variant's program state.

Figure 4 shows how the original program is modified to obtain a CPE-enabled version. Program variants are spawned in line 3, before the the actual encoding routine is invoked in line 4. Each program variant employs a different encoding configuration. Line 5 computes the quality of the resulting video frame, which is passed to the CPE completion routine invoked in line 6. The example shows that very simple code modifications can suffice to introduce In x264, the encoding configuration is represented as an instance of type x264 param t. Each variant can use its own configuration object. Variantspecific configurations can differ, e.g., in the settings that determine how a frame being encoded is analyzed. Such settings include the algorithm and parameters related to motion detection and estimation, various parameters related to psychovisual optimizations, block partitioning settings, etc. These settings influence the quality and the bitrate of the resulting encoded frame. A suitable quality metric can then be used to select one of the resulting frames encoded by the different variants. Two examples of quality metrics that can be used are: i) to favor the encoded frame with the highest visual resemblance to the original image, computed in form of the peak signal-to-noise ratio (PSNR) or any other visual quality metric; or ii) to favor the frame with the smallest encoding size (i.e., the one minimizing the bitrate), but that fulfills some minimum visual quality requirements.

Speedup analysis

Figure 5 shows the speedup of the CPE-enabled program resulting from the modification shown in Figure 4 relative to a serial version. The serial version sequentially encodes each video frame multiple times in a row, once for each encoding configuration used by the CPE variants. An Nvariant CPE-enabled execution competitively encodes each frame using N encoding configurations. The performance of this N-variant execution is compared to a serial version where each frame is encoded N times, one after the other, and using the same encoding configurations as the CPE-enabled version.

We have the program encode 100 frames, and use two different base configurations: i) Low Quality, a lower quality encoding where the encoding of one frame takes approximately 90ms on average, and ii) High Quality, a higher quality encoding taking approximately 500ms per frame. We are mostly interested in the performance and scalability of the approach. All CPE-variants therefore use the same encoding configuration to ensure that the stand-alone execution time of all variants is identical. The time to compute the resulting frame qualities is not taken into account in the reported data.

Figure 5 shows the speedup of the CPE-enabled program with 1-8 variants relative to the corresponding serial versions. The fine dashed line corresponds to a linear speedup. As expected, due to the overhead induced by the CPE isolation mechanics, the speedup of the CPE-enabled program is sub-linear. A regression analysis reveals that the speedup corresponds to approximately 0.72 times the number of variants for the low quality configuration, and 0.85 times the number of variants for the high quality configuration.

Overhead analysis

We compare the execution time of the CPE-enabled program with the time it takes to execute multiple identical instances of the original program in parallel. The goal of this comparison is to understand to which extend the overhead is inherent to the CPE approach and the current run-time system, and which part is due to the increased system load in general, such as contention on the memory-bus and shared caches. We perform this comparison on two 8-core systems that are based on different processor micro-architectures. The first system is based on the Intel Nehalem micro-architecture. The second system is based on the older generation Intel Core 2 micro-architecture. The remaining setup, including the encoder configurations, corresponds to the setup described in Section 3.1.

Figure 6 shows the execution times for the Nehalem-based system. Figure 7 shows the same data for the Core-based system. The two charts show the execution times of the CPE-based version (CPE) using 1-8 variants, and the execution times of a non-CPE version, where the same number (1-8) of identical encoding processes is run in parallel (MP, for multi-process).

For the CPE-based configurations on the Corebased system (Figure 7), we observe an increase in execution time from 9.0s to 17.9s (+99%) in the low quality configuration when increasing the number of program variants from 1 to 8. For the high quality configuration, the execution time increases from 41.5s to 60.0s (+45%). The corresponding increases in execution time for the multi-process scenario are 21% (from 9.0s to 10.9s) and 29% (from 41.5s to 53.6s), respectively. These numbers illustrate well that the execution times of the multiprocess scenarios increase mainly with increasing contention on shared resources such as caches and the memory bus (the high quality encoding has a higher memory pressure than the low quality encoding, and lower spatial locality). The additional overhead for the CPE scenarios (which is mainly due to the process creation overhead and the copying of memory pages modified by program variants) decreases with an increasing computation/working set size ratio (higher quality encoding performs more computation, but does not access big- ger regions of memory than lower quality encoding).

The results for the Nehalem-based system in Figure 6 follow the same trends, but with a clearly lower relative increase in execution time for all scenarios. This better scaling behavior is due to the bigger caches and the higher memory bandwidth of this architecture. Execution time of the CPE-enabled program increases from 9.2s to 12.0s (+30%) for the low quality configuration, and from 43.4s to 50.4s (+16%) for the high quality configuration. In the multi-process scenarios the corresponding times increase by 3% (from 9.2s to 9.5s) and by 6% (from 43.4s to 46.2s).

In the low quality configuration (with its shorter speculative phases) the overhead that is due to the CPE-approach and run-time system themselves is thus approximately 27% (30%-3%). This overhead is significantly larger than the overhead observed for the high quality configuration (with the more than five times longer speculative phases) of approximately 10% (16%-6%). This difference is due to the fact that both configurations have comparable write set sizes for each encoded video frame and therefore a comparable amount of memory copying is required to maintain variant-local program states (approximately 3-10MB for most encoded frames). The time overheads due to this copying and due to the creation and termination of variants can be better amortized over the longer speculative phases of the higher quality configuration than over the shorter phases of the low quality configuration. As a consequence, we observe a lower relative overhead in execution time. An interesting artifact is the local peak at four variants in the CPE scenario for both the low and high quality cases. Further analysis has shown, that this behavior is partly influenced by the scheduling of variants to available cores. Different scheduling strategies lead to different trends. Additionally, the decrease in execution time for five and six program variants may also partly be due to synergetic effects. Similar effects have been observed and analyzed, e.g., by Zhuralev et al. [START_REF] Zhuravlev | Addressing shared resource contention in multicore processors via scheduling[END_REF].

Nehalem Turbo Boost

The measurements on the Nehalem-based system were performed with the processor's Turbo Boost feature [START_REF]Intel Turbo Boost technology in Intel Core microarchitecture (Nehalem) based processors[END_REF] enabled. This Turbo Boost technology allows processor cores to run at clock frequencies higher than the base operating frequency, and is activated and scaled depending on the number of active cores, estimated current and future power consumption, and processor temperature.

In theory, this boosting feature could lead to performance advantages for configurations with a lower number of CPE variants or concurrent processes, compared to configurations with a higher number of processes. In practice, we have not observed such a bias in favor of single-or low-variant configurations. Compared to an execution with Turbo Boost disabled, the boosting feature leads to a speed-up in the order of 3-5%, independent of the number of CPE variants or concurrent processes; with the exception for 2 out of 32 configurations, where a speed-up of 1-2% is observed. This observation correlates with a study of the Turbo Boost feature by Charles et al. [START_REF] Charles | Evaluation of the Intel Core i7 Turbo Boost feature[END_REF]. In their study, Turbo Boost leads to a reduction in execution time for all benchmarks and benchmark combinations. The benchmarks taken into account in the study represent a wide range of CPU-intensive and memoryintensive floating point and integer applications. Similar to our benchmarks, the authors did not observe a specific bias of Turbo Boost in favor of scenarios with a low number of used cores.

As a consequence, the availability of Turbo Boost on current processors needs not be taken into consideration upon deciding if a speculative model such as CPE should be employed or not for a concrete application scenario.

Beyond CPE

We see CPE and CPE-like programming models as a first step toward more general and versatile models of application-specific programmatic speculation. Such programming models could enable applications to easily pursue potentially beneficial computations alongside the main execution flow, without requiring sophisticated reasoning about possible side-effects.

The presented CPE run-time system can already offer acceptable performance for many application scenarios by leveraging features of modern operating systems and architectures. Additional features could enable CPE-like programmatic speculation models with even better performance characteristics and extended capabilities.

If, like in the presented CPE run-time system, the virtual memory system is leveraged to provide memory effect isolation among speculative program variants, the operating system's copy-onwrite implementation has a major impact on the overhead. This effect is also illustrated by the per-formance measurements presented in Section 3, that indicate that the computation/write set size ratio has an influence on the performance behavior of CPE-enabled applications. This impact could be better adapted to the actual program and its memory access pattern by supporting heterogeneous memory page sizes. The memory copying overhead could thereby be reduced by selecting smaller page sizes for memory regions that contain small individual objects, and larger page sizes for memory regions that contain large objects that are usually modified as a whole (such as the encoded output frame in the video encoding example). Such support of heterogeneous memory page sizes requires modifications at the operating system level (virtual memory management) and at the architecture level (translation lookaside buffer). Heterogenous memory page sizes could also benefit software transactional memory systems to implement cheaper and finer granular write barriers.

Transactional memory systems might in turn be leveraged for CPE-like execution models if they a) support a deferred update model and optimistic concurrency control with conflict detection and resolution taking place only at commit time; and b) provide a mechanism to disable automatic retry of aborted transactions. Transactions would be very long running in a CPE-based usage scenario, and a TM system would need to accommodate such characteristics in order to be applicable. CPE serves here as an example of applications of transactional memory systems that go beyond the original intention of such systems. We argue that such nontraditional usage scenarios should be taken into account when designing transactional memory systems.

To support application-specific speculation systems in managing speculative tasks, operating systems should offer more sophisticated interfaces to the scheduling subsystem than are currently available. As a minimum requirement, such interfaces would provide means to distinguish between compulsory and optional tasks and run optional (speculative) tasks only if and when resource and energy constraints allow to do so.

One major limitation of the current CPE system is that program variants cannot perform many types of I/O operations without either prematurely aborting competitive execution and returning to a sequential single-variant execution, or changing externally observable state (by I/O operations that are explicitly enabled by the program). This limitation is a side-effect of the strong isolation guarantees provided by the CPE model. A possible solution to alleviate this limitation are operating system transactions, e.g., like [START_REF] Porter | Operating systems transactions[END_REF]. Support for transactions in the OS would allow for more I/O operations inside speculatively executed program variants, by executing these operations in a transactional manner and committing only the operations of the finally selected program variant.

Related Work

Many other speculative techniques at different abstraction levels have been discussed in the literature. This section gives a brief overview on some of them and motivates that further research is required to address the question of how future computer systems can best accommodate and unify their diverse requirements.

One class of research investigates speculation at very fine granularities. Such low-level speculative techniques include (hardware, software, and hybrid) transactional memory systems, e.g., [START_REF] Dragojević | Stretching transactional memory[END_REF][START_REF] Koskinen | Coarse-grained transactions[END_REF], as well as hardware-supported thread-level speculation approaches, e.g., [START_REF] Hammond | Data speculation support for a chip multiprocessor[END_REF][START_REF] Liu | Posh: a tls compiler that exploits program structure[END_REF].

Other research employs speculative techniques at a coarser level, spanning a larger part of a program's execution flow. Such approaches include, e.g., the Galois system for optimistic parallelism [START_REF] Kulkarni | Optimistic parallelism requires abstractions[END_REF], the Fast Track system for speculative program optimization [START_REF] Kelsey | Fast track: A software system for speculative program optimization[END_REF], and Master/Slave Speculative Parallelization [START_REF] Zilles | Master/slave speculative parallelization[END_REF], a hardware-based approach to speculative parallelization.

Approaches at an even coarser level make use of speculative techniques at the language-level, where speculation is guided by the program and incorporates even larger parts of a program. In terms of the abstraction level and the speculation granularity, these approaches come closest to the CPE approach. Warth and Kay [START_REF] Warth | Worlds: Controlling the scope of side effects[END_REF] present a programming language construct that enables to fork computations of a program that operate on their own copy of the program state. The state modifications of such a world can later be committed back into the main execution flow. A prototype of the system is implemented as an extension to JavaScript. Moura et al. [START_REF] Moura | High level thread-based competitive or-parallelism in logtalk[END_REF] present an idea similar to CPE in the context of the logic programming language Logtalk. In their approach, the bodies of alternative clauses for the same goal are executed concurrently and compete to provide an answer. Cledat et al. [START_REF] Cledat | Opportunistic computing: A new paradigm for scalable realism on many-cores[END_REF] propose Opportunistic Computing, an approach to increase a program's performance or its realism under pre-defined responsiveness constraints by using spare computing cores to execute algorithm alternatives. In contrast to CPE, accesses to shared state need to be replaced by calls to an API to ensure that each algorithmic variant operates on a unique copy of all data.

Other research proposes frameworks, programming languages and language extensions to provide the means to specify algorithmic choice. Such systems can determine beneficial algorithm selection offline in some cases. For cases where offline selection is not possible, or where multiple algorithms or algorithm combination are potentially well suited, high level speculation support such as CPE can be used to simultaneously explore multiple possibilities at run-time. Examples of such systems are PetaBricks [START_REF] Ansel | PetaBricks: a language and compiler for algorithmic choice[END_REF], the work of Li et al. to optimize sorting with genetic algorithms [START_REF] Li | Optimizing sorting with genetic algorithms[END_REF], the Selector language construct [START_REF] Diniz | Selector: A language construct for developing dynamic applications[END_REF], and Du and Agrawal's system to support adaptive applications [START_REF] Du | Language and compiler support for adaptive applications[END_REF].

Generally, as the number of computing cores in systems continues to increase, it is to be expected that speculative approaches will become increasingly popular. Further research is needed to investigate how the diverse requirements of speculative techniques at various abstraction layers can best be unified and met by future computer systems. Another open research question that needs to be addressed is to what extend speculative and transactional approaches at different levels can co-exist or even be combined, and what kind of synergies and conflicts exist between the different techniques and their respective requirements.

Conclusions

The competitive parallel execution (CPE) model and run-time system show that application-specific multi-variant speculation is a viable possibility to leverage multi-core systems for different kinds of applications and they can be efficiently implemented on current architectures and operating systems. Future systems could enable even better performance characteristics and extended capabilities for CPE-like speculative models by providing adequate support at the architecture and operating system level. Also, future research needs to investigate how speculation approaches at different abstraction levels can co-exist, and how future system can accommodate their diverse needs in a unified manner.

Figure 1 .

 1 Figure 1. Left: Average time to start and terminate CPE variants. Right: Average time to intercept and inspect a system call.

Figure 2 .

 2 Figure 2. Execution time overhead due to copying of memory pages for 1 MB and 10 MB write sets per variant, for 1-8 variants.

Figure 4 .

 4 Figure 4. Program modification to enable CPE for the x.264 video encoder. Modified code is emphasized in bold.

Figure 5 .

 5 Figure 5. Speedup of the CPE-enabled version of x264 relative to a serial version that encodes each video frame multiple times in a row. The measurement were performed on an 8-core system based on the Nehalem micro-architecture.

Figure 6 .

 6 Figure 6. Performance of CPE-based video encoding on an 8-core system based on the Nehalem micro-architecture.

Figure 7 .

 7 Figure 7. Performance of CPE-based video encoding on an 8-core Xeon system based on the Core micro-architecture.


Mark Gebhart

Stephen W Keckler
email: skeckler@nvidia.com

ReFLEX: Block Atomic Execution on Conventional ISA Cores

Modern multicore chips target thread-level parallelism at the expense of increasing instruction-level parallelism from single threaded programs. While recent work has attempted to construct a wide-ILP machine from multiple simple cores, these approaches suffer from ISA overheads or scalability challenges. In this paper, we describe an architecture that is inspired by the scalability and flexibility of the TFLEX architecture, yet elides the unorthodox ISA and the overheads that stem from its dataflow execution model. Our results focus on the tradeoff between near out-of-order execution (small out-of-order window within a block of instructions) and far out-of-order execution across blocks. Experiments indicate that a small out-of-order window combined with block-level speculation enables our proposed ReFLEX architecture to achieve comparable performance and flexibility as TFLEX yet with simpler cores and a more conventional ISA.

Introduction

With the end of clock-rate scaling, current and future processors must rely on concurrency to provide continued performance scaling. Modern multicore processors target thread-level parallelism through a small number of simultaneous-multithreaded cores and data-level parallelism through short-vector extensions such as SSE. GPUs target both thread and data-level parallelism via a large number of massively multithreaded but (mostly) scalar cores. In either case, instruction-level parallelism for single-threaded programs or procedures is no longer the focus of multicore systems.

While emerging programs and workloads have a much greater focus on parallelism, many programs still have regions in which few or even one thread is operating. A common program paradigm is to alternate between serial and parallel phases, expanding thread count at the beginning of a parallel region and contracting back to a single thread which may process data prior to subsequent work creation. In such cases, Amdahl's law can dominate. We seek to harness the resources from multiple simple cores to exploit ILP when there are insufficient threads to saturate a multicore system.

Exploiting dynamic expansion and contraction of parallel threads in a manner that effectively utilizes the machine requires an agile system that can create work and synchronize quickly. Further, the capability to dynamically aggregate processing cores to form larger logical processors can enable the hardware to adapt to changing demands of parallel and sequential execution. Recent work on flexible core architectures that intend to exploit these capabilities include Core Fusion [START_REF] Ipek | Core Fusion: Accommodating Software Diversity in Chip Multiprocessors[END_REF], Federation [START_REF] Tarjan | Federation: Repurposing Scalar Cores for Out-of-order Instruction Issue[END_REF], and Composable Lightweight Processors (TFLEX) [START_REF] Kim | Composable Lightweight Processors[END_REF]. Of these, TFLEX is the most scalable enabling aggregation of up to 32 cores and performance scaling to 8 cores (SPEC-INT) and 32 cores (SPEC-FP).

However, TFLEX has several drawbacks. First, it requires a decomposition of a program into program regions (hyperblocks) of a fixed maximum size. Second, the dataflow oriented instruction set that was designed to scale ILP across many cores incurs substantial overheads for data movement and copying. Third, the microarchitecture requires sizable storage structures (reservation stations) to deploy the dataflow instruction set; because the reservation stations hold instructions that have both executed and are waiting to execute they can incur power overheads.

In this paper, we propose ReFLEX, a more conventional ISA architecture inspired by the advantages and capabilities of TFLEX. ReFLEX employs a conventional RISC-style architecture, augmented with block atomic semantics and full predication, and a microarchitecture that enables block-atomic execution without restricting blocks to a fixed minimum or maximum size. The ReFLEX microarchitecture consists of simple dualissue cores with a small out-of-order window to capture ILP from nearby instructions. Consecutive blocks can be mapped to different cores to exploit speculation and far-range ILP. The ReFLEX microarchitecture manages the register file and memory in a distributed fashion, enabling register and memory locality to be exploited within the cores.

We view ReFLEX as a step toward architectures that are amenable to modern compiler optimization algorithms and that can ultimately support dynamic expansion and contraction of threads spanning the cores and their aggregation into processors.

The remainder of this paper first provides an overview of the ReFLEX ISA, execution model, and microarchitecture.

It then compares the performance of ReFLEX to that of TFLEX, an architecture with greater complexity. Results show that with a small out-of-order window within a core, ReFLEX can attain comparable performance as the more complicated TFLEX processor.

Execution Model and Microarchitecture

ISA

The two fundamental changes to the ReFLEX ISA compared with a convention RISC ISA are support for block atomic execution and full predication. The ReFLEX ISA is similar to an EDGE ISA [START_REF] Burger | Scaling to the End of Silicon with EDGE Architectures[END_REF] except that instead of dataflow execution within a block, execution within a block has tradition RISC style in-order semantics. This avoids the overheads associated with dataflow execution, including fanout instructions, needed when a value is consumed by multiple instructions and nullification instructions, necessary to detect when a block has completed [START_REF] Gebhart | An Evaluation of the TRIPS Computer Systems[END_REF]. The results in Section 4 show that ReFLEX executes roughly 15% fewer instructions than TFLEX.

For the current version of this work, a block is defined as having up to 128 instructions with a single entry point and multiple exit points. There is no inherent reason that a ReFLEX block should have a fixed minimum or maximum size. At one extreme, atomic blocks could simply be basic blocks which would require little software support to form. However, larger block better amortize execution overheads. Register storage is partitioned into a global register file and block private data and predicate register files. Values in the private register files are valid only for the duration of a single dynamic instance of a block. Using this block atomic execution model has several benefits:

• Out of order local commit: Since the global machine state is only updated when blocks commit and blocks commit in-order, instructions within a block can be retired locally out-of-order. Only block outputs need to be buffered, rather than the speculative state of all instructions as done in a conventional reorder buffer. • Register hierarchy: Since each block has its own set of temporary register names, the need to perform register renaming is reduced compared with a conventional processor. Additionally, the block private values are not stored to the globally shared structures, reducing pressure on these structures. • Distributed execution: The execution overheads of distributed execution are amortized across the instructions in a block allowing for a more scalable system.

Dataflow Predication

ReFLEX uses predication to create large blocks which better amortize block execution overheads. All of the instructions, except for two constant generation instructions, support predication. Instructions use dataflow predication where an instruction can either be directly predicated or indirectly predicated when one of its operands is predicated [START_REF] Smith | Dataflow Predication[END_REF].

Alternatively, a traditional full predication model could be used [START_REF] Mahlke | A Comparison of Full and Partial Predicated Execution Support for ILP Processors[END_REF]. The advantage of dataflow predication is that the compiler is already targeted to TRIPS and TFLEX which use dataflow predication. Additionally, the encoding of dataflow predication is more compact since nested predication can be encoded with a single predicate. The disadvantage of dataflow predication is that more complex state must be tracked to ensure that only the intended instructions are executed. To implement dataflow predication, each block private register is augmented with a valid bit. When a block begins executing, all of the registers are invalid. When a value is written to a register, the valid bit is set.

Instructions only execute if their predicates match and the valid bits for all source operands are set. Since there are only 32 entries in the temporary register file (TRF) and up to 128 instructions in a block, the compiler must perform register allocation and reuse some of the entries in the TRF across multiple live ranges. Special care must be taken to update the valid bits after mispredicated instructions. Each instruction can be augmented with a specifier "C" which signals that the valid bit for the destination register should be cleared if the instruction does not execute. Figure 1 shows an example of how these modifiers are used. In this example, after register allocation R0 and R1 are used at both the top and bottom of the block. The predicated addi must be augmented with the "C" specifier because if P0 is false, P1 will not be produced. The predicated addi and subi will not execute, since the valid bit for P1 will not be set. If the predicated addi did not have the "C" specifier, the final addi in the block would read the value of R1 from the read of G1. The intended behavior is for the addi P P P P P P P P P P P P P P P P P P P P P P P P P P P P to not execute when P0 is false. The non-predicated addi must have the "C" specifier because if it does not execute, later consumers could read the value of R0 produced by the read instruction.

P P P P L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 P P P P P P P P L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 L2 P (a)
In general, all instructions that define a new live range should have the "C" specifier. The two exceptions to this rule are instructions that define the first use of a register in a block do not need the "C" specifier, since initially all registers are invalid. Second, when a register is defined by multiple predicated instructions, only the first instruction should have the "C" specifier. An example of this case is the lack of a "C" specifier on the predicated subi instructions in Figure 1.

Composability

Figure 2 shows some of the different ways a 32-core system can be configured. This ranges from using each core as a separate processor, allowing for 32 simple processors, aggregating all of the cores into a single processor, or some point in between. Each core has 128 registers; when multiple cores are composed, the program has access to a total of 128 registers which are partitioned across all composed cores. Each core has a 8KB L1 data cache and a 2KB L1 instruction cache. When multiple cores are composed, the caches are combined with address partitioning, giving the program access to 8KB times the number of cores of data cache and 2KB times the number of cores of instruction cache. Each block is assigned a home core which is responsible for performing branch prediction and detecting when a block completes. The full details can be found in the original TFLEX paper [START_REF] Kim | Composable Lightweight Processors[END_REF].

Microarchitecture

In this work we leverage the microarchitecture of TFLEX [START_REF] Kim | Composable Lightweight Processors[END_REF] with some changes to support the modified execution model. Figure 3 shows an overview of the microarchitecture of a 2 core ReFLEX system; the exact microarchitecture parameters used for this study are shown in Table Global out-of-order execution can be achieved in two ways. First, since multiple blocks are in-flight concurrently, instructions in different blocks are free to execute out of global program order. Second, the instructions within a block are locally executed out-of-order. Figure 3 shows a system configured with an out-of-order execution window of size 2. Section 4 illustrates the performance tradeoff between exploiting near versus far parallelism.

Along with the valid bits needed to implement dataflow predication, the pending reads and writes to a register must also be tracked. These pending operations come from the local out-of-order execution. Pending reads and writes are identified by their instruction number within the block. An instruction may only execute if there are no pending writes to its source registers from earlier instructions and no pending reads to its destination register from earlier instructions. When WAW and WAR hazards are encountered, the processor stalls until they are resolved, unless register renaming is being used.

In this version of the work, each block can have up to 32 memory operations. Each core has a 64entry LSQ which uses a NACK policy to stall memory operations when the LSQ is full [START_REF] Sethumadhavan | Late-binding: Enabling unordered load-store queues[END_REF]. The LSQs are addressed partitioned across the cores. Since the LSQ can reject a memory operation when it is full, each core has a 16-entry memory instruction skid buffer. Once issued, memory instructions are moved from the issue window to the skid buffer. Once an entry has been successfully allocated in the LSQ, the instruction is removed from the skid buffer. Since TFLEX has dedicated storage for all instructions in a block, a memory skid buffer is not needed.

Methodology

We use Simpoints [START_REF] Sherwood | Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications[END_REF] from the SPEC2K benchmarks to evaluate ReFLEX. Our current infrastructure supports a total of 14 of the C and Fortran benchmarks. Additionally, we evaluate ReFLEX on 28 of the EEMBC benchmarks [3]. We use the Scale compiler [START_REF] Mckinley | The Scale Compiler[END_REF] to produce block atomic RISC code. The instructions within a block are scheduled by a modified TRIPS scheduler [START_REF] Coons | A Spatial Path Scheduling Algorithm for EDGE Architectures[END_REF]. All of the simulations are done on a cycle level execution driven simulator.

Preliminary Results

In this section we present preliminary results, as we are still tuning the compiler for ReFLEX. The reduction in the number of instructions executed by ReFLEX compared with TFLEX is shown in Figure 4. These results are with an 8-core system with an execution window of 9 instructions without register renaming. The number of instructions executed across all of the different configurations for a given benchmark varies by less than 1%. Therefore, Fewer instructions are executed by ReFLEX compared with TFLEX on the integer benchmarks than the floating point benchmarks. This is due to the complex control of the integer benchmarks, which requires more dataflow overhead instructions. Some benchmarks, such as vpr and equake see no reduction in instruction count compared with TFLEX. In fact, equake actually executes 19% more instructions on ReFLEX. For this benchmark, the compiler has formed blocks differently than when compiling for TFLEX and the blocks produced are less efficient, requiring more instructions to be executed. Overall, there is a savings of roughly 15% in the number of instructions that must be executed.

Figure 5 shows the geometric mean across all of the benchmarks normalized to a 1-core configuration where the baseline core executes a block inorder. Each line shows results for increasing the amount of out-of-order execution performed locally within a core. An execution window of 128 allows for full out-of-order execution across a single block. With an execution window of 128 instructions, ReFLEX is equivalent to TFLEX except for the dataflow overhead instructions present in TFLEX. When compiling for ReFLEX, the compiler forms different blocks than when compiling for TFLEX since it does not need to allocate space in the block for these dataflow overhead instructions. Generally this results in better performance; however, in some cases the ReFLEX blocks are less efficient. On SPEC INT and EEMBC, where the amount of parallelism exploited is limited, the gains from performing register renaming are limited. For these benchmarks, the energy overhead of performing register renaming is not justified. On SPEC FP, register renaming increases the maximum speedup achieved from 4.5 to just under 5.5. In cases where absolute performance is critical, a large execution window coupled with register renaming provides the best performance. In other cases, energy can be saved by not performing register renaming and simply stalling when WAW and WAR hazards are encountered.

As the number of cores increases, the difference in performance between in-order and out-of-order cores increases. Out-of-order cores can better tolerate the increasing communication delays present in larger configurations. To achieve high performance, some degree of out-of-order execution is needed to exploit near parallelism, especially with a large number of cores. When only in-order cores are used, the performance is limited and 2 out-of-order cores with an execution window size of 17 can match the performance of 16 in-order Performance can be increased either by increasing the size of the local execution window or increasing the number of cores depending on area and power constraints. There is ongoing work to increase the scalability of TFLEX on benchmarks such as EEMBC and SPEC INT. Some of these mechanisms could also be applied to ReFLEX. Figure 6 compares the performance of ReFLEX to TFLEX [START_REF] Kim | Composable Lightweight Processors[END_REF] across the three sets of benchmarks. TFLEX has an advantage in that it can choose to execute any ready instruction within the block but its performance is limited by the overhead instructions needed to perform dataflow execution within a block. When the local execution window is 9 entries or larger, ReFLEX is competitive with TFLEX. On SPEC FP register renaming is needed to remain competitive with larger number of cores. ReFLEX performs better on SPEC INT and EEMBC compared to TFLEX since the scalability of these benchmarks is limited, thus ReFLEX's limitations have less of an impact on performance.

As the number of cores increases, generally, performance decreases relative to TFLEX. With a large number of cores, the scheduling of instructions within a block has the potential to degrade the performance of not only the current block but also consumers of the current block's outputs. The scheduler must deal with two competing interests. It must place instructions that produce values consumed by other blocks early in the block, to produces these outputs as soon as possible. At the same time, it must place instructions that consume values from other blocks later in the block so that these consumers do not delay the execution of independent instructions while waiting for remote values to be produced. Instructions can be both a consumer of a value from a prior block and a producer of a value needed by a subsequent block. We found that the best scheduling heuristic was to order instructions based on their transitive distance to the top of the dataflow graph, where instructions with large distances being placed later in the block. We look across the likely block predecessors to include the dataflow graphs for prior blocks. This heuristic places instructions that are less likely to stall execution while waiting on predecessors earlier in the block. Those instructions that are more likely to have to wait on predecessors are placed later in the block.

Figure 7 shows the individual benchmark performance compared with TFLEX with a local window size of 9. The EEMBC benchmarks are omitted for space constraints due to the large number of benchmarks in the suite. Performance ranges from 50% worse than TFLEX to 80% better than TFLEX. This wide range is a function of the amount of fanout in each benchmark, which ReFLEX eliminates, and the importance of a large local execution window, where TFLEX has the advantage. Register renaming is particularly important to mcf, providing roughly a 20% performance improvement for larger number of cores.

Related Work

Block structured ISAs: Multiscalar processors [START_REF] Sohi | Multiscalar Processors[END_REF] use software to divide a program into a collection of tasks where each task is similar to an atomic block. Predication is not used to grow the size of tasks but rather internal control flow is allowed. Most tasks have far fewer dynamic instructions than the number of static instructions in a Re-FLEX block. Each task is executed by a separate processor and a single register file is keep globally consistent by connecting the processors in a ring and forwarding register values around this ring. This ring structure requires that tasks be mapped in a round robin fashion. Blocks in ReFLEX can be mapped to arbitrary cores which can be exploited for locality advantages. Additionally, the ring structure establishes a static processor granularity where one of the main goals of ReFLEX is to enable composable execution.

Melvin and Patt proposed a block structured ISA to increase the fetch bandwidth [START_REF] Melvin | Enhancing Instruction Scheduling With a Block-Structured ISA[END_REF]. In their work, blocks are the atomic unit of work and instructions within a block execute in dataflow order. Their program structure is similar to an EDGE ISA without support for predication. They use both a global architectural register file and block local storage. Each block can have up to 256 instructions which requires a large amount of local storage. Since they perform dataflow execution within a block they face many of the challenges of TFLEX. Their main goal was to increase performance by exploiting ILP and a flexible microarchitecture that supported composability was not a focus.

Composable processors: There have been several projects that used traditional ISAs to construct composable processors. However, the perinstruction bookkeeping overheads associated with traditional ISAs limit scalability. Federation [START_REF] Tarjan | Federation: Repurposing Scalar Cores for Out-of-order Instruction Issue[END_REF] considers using tightly coupled in-order cores to achieve out-of-order execution. This is similar to how ReFLEX achieves out-of-order execution across blocks. They focus on enabling this small scale composability to avoid the area and power Core Fusion [START_REF] Ipek | Core Fusion: Accommodating Software Diversity in Chip Multiprocessors[END_REF] aims to use composable execution to exploit both ILP and TLP across an 8 core microarchitecture. One key advantage of this work is that it requires no changes to the ISA. When running a single sequential SPEC2K application Core Fusion is 30% and 50% faster than a single two-wide issue out-of-order core on SPEC INT and SPEC FP respectively. Section 4 shows that ReFLEX can achieve better scalability on SPEC2K due to its block structured ISA. TFLEX [START_REF] Kim | Composable Lightweight Processors[END_REF] leverages an EDGE ISA, which uses block atomic execution and dataflow within a block, to enable composability. However, the dataflow execution within a block has high overheads. Up to 20% of the instructions executed are dataflow overhead instructions which often are on the critical path. Additionally, these dataflow overhead instructions limit the amount of useful work that can be put into a given sized block. Using composability to support dynamic expansion and contraction of parallel work was not studied.

Conclusions

In this work, we have shown that a RISC ISA, augmented with block semantics and support for predication, can efficiently execute on a distributed composable microarchitecture. This approach does not rely on register renaming or a reorder buffer to perform out-of-order execution. A ReFLEX processor, with a nine entry local execution window, is competitive with the dataflow execution TFLEX processor. We are currently conducting a detailed power evaluation. Compared with TFLEX this model reduces the number of instructions executed by roughly 15% and replaces a 128-entry RAM based instruction window with a small (9 entry) CAM based execution window.

We are exploring the potential of internal control flow for reducing the number of fetches for blocks that are part of a tight loop. In order to take advantage of phase changes in the program we are exploring support for lightweight mechanisms to spawn and then contract parallel work when parallel sections are encountered. We believe that the block model is a good mechanism for supporting this requirement because spawning blocks is a lightweight operation. We also plan to study the algorithms that assign blocks to cores. Dependent blocks in serial sections should be scheduled on the same core while independent blocks in parallel sections need to be scheduled on different cores.

This model allows for more aspects of the processor to be dynamically tuned to adjust performance and rapidly adapt to the changing parallelism needs of a program. Further, the lightweight communication provided by this model can potentially exploit fine-grained parallelism that is not profitable to exploit on coarser grained designs. We view this work as a first step and future work will exploit the capabilities of ReFLEX to efficiently execute programs with varying degrees of parallelism.

Figure 1 :

 1 Figure 1: Example of dataflow predication, the addi instructions must clear their destination register if they are mispredicated to prevent consumers from seeing the values of R1 and R0 from previous live ranges (read instructions).

  32 2-wide CLP config. (b) 8-processor CLP config.(c) One 64-wide CLP config.

Figure 2 :

 2 Figure 2: Composability of a 32 core system.

Figure 4 :

 4 Figure 4: Number of Instructions Executed Normalized to TFLEX for SPEC INT and SPEC FP

  Tuning the compiler for ReFLEX is ongoing work. Results are shown for SPEC INT, SPEC FP, and EEMBC both with and without register renaming on the TRF and PRF. Increases in the size of the local execution window result in performance increases; however, a local window of 17 instructions captures nearly all of the performance of a maximally sized 128 entry execution window. The scalability varies greatly based on the benchmark suite. SPEC INT and EEMBC have limited scalability and performance generally peaks at 8 cores. SPEC FP sees performance increases up to 16 cores. When 32 cores are used, the performance degrades due to increases in communication costs and decreases in branch predictor accuracy at a large speculation depth.

Figure 5 :

 5 Figure 5: Scalability compared to 1 in-order core across SPEC INT, SPEC FP, and EEMBC both with and without register renaming on the PRF and the TRF

Figure 6 :

 6 Figure 6: Performance compared to TFLEX across SPEC INT, SPEC FP, and EEMBC both with and without register renaming on the PRF and the TRF

Figure 7 :

 7 Figure 7: Performance compared to TFLEX for SPEC INT and SPEC FP both with and without register renaming on the PRF and the TRF and a fixed window size of 9 instructions

Table 1 :

 1 1. To each Microarchitecture parameters.

	Parameter	Configuration
	Instruction	Partitioned 2KB (per core) I-cache (1-cycle hit)
	Supply	Local/GShare Tournament predictor(2K+256 bits, 3 cycle latency) speculative updates
		Num. entries: Local 128(L1) + 256(L2)
		Global: 1024, Choice: 1024, RAS: 16, CTB: 32, BTB: 256, BType: 512.
	Execution	In-order / Out-of-order execution, CAM structured variable entry execution window
		Limited dual-issue (1 FP and 1 INT or 2 INT)
	Data Supply Partitioned 8KB D-cache (per core) (2-cycle hit, 2-way set-associative, 1-read port and 1-write port)
		4MB decoupled S-NUCA L2 cache [6] (8-way set-associative, LRU-replacement)
		L2-hit latency varies from 5 cycles to 27 cycles depending on memory address
		Average (unloaded) main memory latency is 100 cycles; 64-entry LSQ / core

Figure 3: Microarchitecture of a 2 core system.

core, we added a 32-entry temporary register file (TRF), a 8-entry predicate register file (PRF), and a small execution window to allow for out-of-order execution within a block to improve performance. The 128-entry global register file is partitioned across all cores. Dedicated read and write instructions are used to access the global register file. The 128 reservation stations per core used by TFLEX to support dataflow execution within a block are no longer needed. Like TFLEX, multiple blocks can be executed concurrently but they commit their outputs (writes to the global register file and stores to the memory system) in program order. A memory dependence predictor is used to allow memory operations to optimistically execute out of program order.

Acknowledgments

This research is supported by NSF grant CCF-0936700. The authors thank Katherine Coons and Bertrand Maher for their help with the TRIPS tools.


Andreas Arnold-Bos

Jean-Philippe Malkasse

Gilles Kervern

A PREPROCESSING FRAMEWORK FOR AUTOMATIC UNDERWATER IMAGES DENOISING

Keywords: underwater vision, denoising, contrast equalization, adaptive smoothing

A major obstacle to underwater operations using cameras comes from the light absorption and scattering by the marine environment, which limits the visibility distance up to a few meters in coastal waters. Current preprocessing methods typically only concentrate on local contrast equalization in order to deal with the nonuniform lighting caused by the back scattering. We review these techniques, then go further and show that the additional use of adaptive smoothing helps to address the remaining sources of noise and can significantly improve edge detection in the images. Many results on real data are provided and discussed using a custom numerical criterion.

INTRODUCTION

In the recent few years, the increasing interest in remotely operated vehicles and autonomous underwater vehicles for submarine operations has called for the development of reliable sensors to ensure mission success. Optical cameras seem to be a good choice, as they have a good resolution and are readily available on the market. However, the main drawback to the use of cameras comes from the relatively limited visibility that can be attained: about twenty meters in clear water and less than a few meters in turbid, coastal waters such as in harbors [START_REF] Legris | Les capteurs d'imagerie en robotique sous-marine: tendances actuelles et futures[END_REF]. The propagation process can be divided into three additive components. The exponential decay of the light intensity with distance, called attenuation, leads to a hazy image background. Visibility may indeed be augmented with artificial lighting. Unfortunately, a significant fraction of the power will be reflected by the water towards the camera before actually reaching the objects. This process, known as backscattering, causes undesirable differences of contrast in the image, which mask the details of the scene. Finally, forward scattering, i.e. randomly deviated light on its way to the camera, causes blurring of the image features. Macroscopic floating particles (marine snow), can also be considered as unwanted signal. In orders of magnitude, backscattering and marine snow are the greatest degradation factors, forward scattering comes second and attenuation follows closely.

Deconvolution is theoretically possible as the received image can be expressed as the convolution of an ideal image with the modulation transfer function of the water [START_REF] Mcglamery | A computer model for underwater camera systems[END_REF]. However many model parameters are needed. First of all, the attenuation and diffusion coefficients that characterize the water turbidity are only scarcely known in tables and can be extremely variable. Next, the most crucial parameter to recover is the depth of a given object point in the scene, which is necessary to correctly estimate the distance traveled by the light. Therefore, to the best of our knowledge, deconvolution has only been used in rather controlled environments so far. Liu et al. [START_REF] Liu | Underwater image transmission and blurred image restoration[END_REF] expose the full deconvolution procedure on the image of a flat object taken in a water tank, which allows for the estimation of the depth. Trucco and Olmos [START_REF] Trucco | Self-tuning underwater image restoration[END_REF] tackle the problem in real-life conditions but assume a top-down point of view, with small variations of the bottom depth; moreover, they use a simplified model where only forward scattering is present. They estimate the medium parameters by using an iterative method on a dedicated quality criterion.

When no specific assumption can be made on the point of view or the turbidity parameters, as in our case, generic image enhancement methods are often employed in the underwater robotics literature. These methods make total abstraction of the image formation process and are usually very simple and fast. They are typically used to correct the contrast disparities caused by the attenuation and backscattering, but the remaining noise level remains high, thus impairing edge detection. In this paper, we explore the use of adaptive smoothing techniques in order to improve the edge detection. Furthermore, we present a simple criterion which allows for a comparison of the enhancement methods and the edge detection robustness.

ALGORITHM DESCRIPTION 2.1 Contrast equalization

Many well-known techniques are known to help correcting the lighting disparities in underwater images. As the contrast is non uniform, a global color histogram equalization of the image will not suffice and local methods must be considered. Among all the methods they reviewed, Garcia, Nicosevici and Cufi [START_REF] Garcia | On the way to solve lighting problems in underwater imaging[END_REF] constated the empirical best results of the illumination-reflectance model on underwater images: if I(i, j) is the original image, and I LP (i, j) its low-pass version, a scaled, contrast-equalized version of I is I eq (i, j) = I/I LP (i, j). The low-pass version of the image is typically computed with a Gaussian filter having a large standard deviation. After the scaling, pixel values of I eq will present a distribution centered around one, with a small dispersion (especially for poorly contrasted images) except for a few outliers. Therefore, contrast equalization is followed by histogram clipping to reject these outliers:

I clip (i, j) =    i 1 if I eq (i, j) < i 1 , i 2 if I eq (i, j) > i 2 , I eq (i, j) else. (1)
where [i 1 ..i 2 ] is the 90% percentile interval of the intensity distribution of I eq . Then the dynamic of the image may be expanded so that all available intensity levels [0..i max ] are occupied:

I exp (i, j) = I clip (i, j) -i 1 i 2 -i 1 .i max ( 2
)
This method is theoretically relevant because backscattering, which is responsible for most of the contrast disparities, is indeed a slowly varying spatial function. Backscattering is the predominant noise, hence it is sensible for it to be the first noise addressed in the algorithm. However, contrast equalization also corrects the effect of the exponential light attenuation with distance.

Noises present in the images after equalization

The contrast equalization will generally raise the noise level in poorly contrasted areas of the original image. Indeed, the local gain of the contrast equalization process is:

G(i, j) = 1 I LP (i, j) . i max i 2 -i 1 (3)
The standard deviation of the noise at location (i, j) will also be multiplied by G(i, j); consequently, the lower the intensity, the higher the noise level. Gain G affects all types of noises remaining in the image, as the additive Gaussian noise of the camera electronics, the quantification noise, which can all be considered as Gaussian white noise. However, these noises are often small in front of the noise produced by the water, of which we shall now give a brief summary. Apart from forward scattering, which has a blurring effect, macroscopic floating particles producing images of the size of a pixel can be present as well: it may be, for instance, sand raised by the motion of a diver, or small plankton particles. These particles are, per se, part of the scene, but cause generally unwanted signal. We see them as an additive noise, of distribution clearly not Gaussian yet still reasonably similar, because the particles will act as (secondary) sources of attenuated and diffused light. It is important to stress the local nature of this noise, and the problems it causes in edge detection, because it is likely to cause falsely detected edges.

Use of adaptive smoothing to increase edge detection robustness

Edge detectors such as the Canny-Deriche algorithm [START_REF] Deriche | Using Canny's criteria to derive a recursively implemented optimal edge detector[END_REF] use a linear filter of typical width α akin to the Gaussian filter to smooth the image in the orthogonal direction to the computed derivative. This helps to reduce noise and increases the edge detectability. In the underwater context, noise is generally important so large α values are needed; doing so results in badly localized and less precise object shapes. Indeed, the linear smoothing filter does not adapt itself to the local noise intensity or the presence of edges, so the filtering level is overevaluated on some parts of the image. This was our motivation for adding an adaptive image smoothing stage between the contrast equalization and the edge detection. The principle behind adaptive smoothing is that the image is filtered less where edges are present, hence preserving their good visibility. We have experimented anisotropic filtering and complex wavelets as possible means to reduce the influence of the aforementioned noises. Before providing the results, we shall briefly describe how these methods are used.

Anisotropic filtering

Anisotropic filtering was introduced in a seminal article by Perona and Malik [START_REF] Perona | Scale-space and edge detection using ansotropic diffusion[END_REF]. Basically, it consists in solving iteratively a modified version of the heat diffusion equation on the image, using a control function c of the gradient:

∂i ∂t = λ.div c(| --→ grad i| 2 ) --→ grad i i(t = 0, x, y) = i 0 (x, y) (4)
Smoothing increases with time t and the diffusion coefficient λ. In order to account for the local noise amplification caused by the contrast equalization, we write:

λ(i, j) = λ 0 .G(i, j) (5)
Control function c tends to one to allow diffusion when the gradient is small (i.e. in uniform areas of the image). When the gradient gets large (in the vicinity of edges), c tends towards zero.

Various forms have been proposed for c. We use the function proposed by Sochen, Kimmel and Mallardi [START_REF] Sochen | A geometrical framework for low-level vision[END_REF], because it optimizes the tradeoff between a small diffusion in the direction of the gradient, and a large tangential diffusion:

c(| --→ grad i|) = 1 1 + | --→ grad i| 2 (6)

Wavelet filtering

Time-frequency methods have also been widely used to denoise images, especially bi-orthogonal or "symlet" wavelet decomposition. Known problems of these methods are the following:

1. they are not translation independent and thus may corrupt the phase of the signal, which distorts edges;

2. an automatic thresholding method of the wavelets coefficients is not always available.

We followed Kovesi [START_REF] Kovesi | Phase preserving denoising of images[END_REF] who proposed to use complex-valued log-Gabor wavelets so as to have an approximation of the amplitude and the phase of the signal at various scales. Then, only the amplitude of the coefficients is shrunk by the estimated noise contribution at that scale, so as to preserve the phase of the signal. Noise is assumed to be Gaussian and white, so the distribution of the amplitude of the wavelets coefficients at each scale follows approximately a Rayleigh distribution. Of the ideal image, only edges (about 5 % of the pixels) contribute at the smallest scale and the majority of the coefficients correspond to noise; their mean and variance can therefore be easily computed. Then, because the noise is supposed to be white, its contribution at a given scale is proportional to the bandwidth of the wavelet corresponding to that scale. However, unlike Kovesi's original algorithm, we do not use a constant threshold over space, but instead correct it by factor G(i, j) so that heavier filtering is done where the initial image was dark. Note that the assumption of a Gaussian white noise is false in our case, but the noise distribution observed in uniform zones of our images were close enough. The principal advantage of Kovesi's method is that no constants tuning is necessary after initial setting. Note that other wavelet-based denoising schemes exist that behave well on edges, such as the curvelets [START_REF] Starck | The curvelet transform for image denoising[END_REF], which may be investigated in the future in our context.

EXPERIMENTS 3.1 Qualitative results

We performed our experiments on miscellaneous images with unknown turbidity characteristics. These images present typical noise levels for underwater conditions. Fig. 1 offers a visual comparison of the effect of the two stages of our preprocessing on the original image. Contrast equalization enhances visibility, yet it may create halos around strongly contrasted objects of size similar to the Gaussian kernel (visible on image c, around fishes). We found that a good tradeoff between equalization and small halos could be found by allowing the standard deviation of the kernel to be five to ten percent of the image diagonal length. Noise remaining after contrast equalization is visibly reduced after adaptive smoothing. Kovesi's method was used to perform the smoothing, but anisotropic diffusion gives slightly better solutions, with sharper edges, as seen in fig. 2. However, anisotropic filtering has two drawbacks: a lengthy computation time and the fact that diffusion constants must be manually tuned. Kovesi's method is faster and automatic. Fig. 3 displays the edges as found by the Canny-Deriche detector for the four previous images. In all cases, the thresholds and smoothing parameters of the Canny detector are the same. More edges are detected after contrast equalization, but they include false positives. Smoothing helps to cut down on edges corresponding to noise.

Quantitative results

Contrast is often suggested as a means to assess the gain in underwater image preprocessing algorithms. Various contrast criteria have been proposed in the literature [START_REF] Peli | Contrast in complex images[END_REF]. Global contrast criteria, the simplest of which is the variance of the image, is not usable because of the nonuniform lighting in raw images. Local criteria are generally very complicated and not very condensed, thus heavier to use.

To assess the quality of enhancement methods, we propose a new, synthetic criterion. We base it on a very general result by Pratt [START_REF] Pratt | Digital Image Processing[END_REF]: for most well-contrasted and noise-free images, the distribution of the gradient magnitude histogram is closely exponential, except for a small peak at low gradients corresponding to homogeneous zones. When images have such a gradient distribution, edges are generally easily discernible from noise by a simple thresholding of the gradient. On the contrary, for an image heavily corrupted by noise, or badly contrasted, the gradient magnitude distribution will be very different. For instance, if we consider the extreme case of an image consisting in pure Gaussian white noise, the two components of the gradient will be normally distributed (as differences of normally distributed random variables); and the magnitude of the gradient will follow a Rayleigh distribution. On the other hand, a badly contrasted image will have more low gradients than usual, so the distribution will not be exponential. We note i the gradient magnitude and h(i) the gradient magnitude histogram (computed on typically N = 128 bins and normalized by its sum), then we perform a linear regression on ln h(x), as shown in fig. 4:

ln h(i) = a -b.i (7)
In practice, not all the gradient magnitude range is used for the regression, because noise appears in ln h(i) at high gradients. This noise results from sampling effects for low histogram counts.

In our experiments, the magnitude range went from i = 1 to N = 2/3N . Our robustness criterion is linked to the variance of the linear regression, which measures the closeness of the histogram with an exponential distribution. The closer the robustness is to one, the better the enhancement:

R = exp - 1 N -1 i=N i=1 ln h(i) -ln h(i) 2 (8)
Robustness is indicated in fig. 3 for the images presented in this paper. The values taken by the criterion confirm our intuition concerning the image quality. R takes lower values for images where the sea bottom is not visible or made of sand, as the uniform background perturbs the gradient statistics; but generally speaking the robustness criterion is higher for smoothed images than for just contrast-equalized images, which in turn have a higher robustness than raw images.

CONCLUSION

In this paper, we showed that the standard method consisting in simply equalizing the contrast of the images is not sufficient enough in many cases to allow for a robust edge detection. To correct this, we benchmarked two classes of adaptive smoothing methods: anisotropic filtering and Kovesi's phase preserving wavelet filtering. This helps to address the remaining noise sources in the image (the captor and the macroscopic floating particles). We showed that the two methods give arguably similar visual results and both improve edge detection. However Kovesi's approach provides a self-thresholding mechanism, which allows for a fully automatic denoising. We also proposed a simple, condensed numerical criterion to assess the quality of the restoration procedure, which generally agrees with intuition.

Fig. 1 :

 1 Fig. 1: Benefits of adaptive smoothing. Left: original image. Middle: after contrast normalization and histogram clipping. Right: after Kovesi wavelet filtering.

Fig. 2 :Fig. 3 :Fig. 4 :

 234 Fig. 2: Close-up view of image c) for comparison between Kovesi's wavelet filtering (left) and anisotropic filtering (right).

ACKNOWLEDGMENTS

The first author wishes to thank Thales Underwater Systems for having welcomed him as a student intern during his Diplôme d'Etudes Approfondies in Signal and Image processing (Supaero, Toulouse) final project.