Chenxi Wang
email: wangchenxi@ict.ac.cn

Ting Cao
email: caoting@ict.ac.cn

John Zigman
email: john.zigman@sydney.edu.au

Fang Lv

Yunquan Zhang

Xiaobing Feng

Efficient Management for Hybrid Memory in Managed Language Runtime

Keywords: Hybrid memory, Managed runtime, JVM, Memory management

Hybrid memory, which leverages the benefits of traditional DRAM and emerging memory technologies, is a promising alternative for future main memory design. However popular management policies through memory-access recording and page migration may invoke non-trivial overhead in execution time and hardware space. Nowadays, managed language applications are increasingly dominant in every kind of platform. Managed runtimes provide services for automatic memory management. So it is important to adapt them for the underlying hybrid memory. This paper explores two opportunities, heap partition placement and object promotion, inside managed runtimes for allocating hot data in a fast memory space (fast-space) without any access recording or data migration overhead. For heap partition placement, we quantitatively analyze LLC miss density and performance effect for each partition. Results show that LLC misses especially store misses mostly hit nursery partitions. Placing nursery in fast-space, which is 20% total memory footprint of tested benchmarks on average, causes only 10% performance difference from all memory footprint in fast-space. During object promotion, hot objects will be directly allocated to fast-space. We develop a tool to analyze the LLC miss density for each method of workloads, since we have found that the LLC misses are mostly triggered by a small percentage of the total set of methods. The objects visited by the top-ranked methods are recognized as hot. Results show that hot objects do have higher access density, more than 3 times of random distribution for SPECjbb and pmd, and placing them in fast-space further reduces their execution time by 6% and 13% respectively.

Introduction

As processor cores, concurrent threads and data intensive workloads increase, memory systems must support the growth of simultaneous working sets. However, feature size and power scaling of DRAM is starting to hit a fundamental limit. Different memory technologies with better scaling, such as non-volatile memory (NVM), 3D-stacked and scratchpad memory, are emerging. To leverage the benefits of different technologies, with disparate access-cost modules into an integrated hybrid memory opens up a promising future for memory design. It has the potential to reduce power consumption and improve performance at the same time [START_REF] Xie | Modeling, architecture, and applications for emerging memory technologies[END_REF]. However, it exposes the complexity of distributing data to appropriate modules.

Many hybrid memory management policies are implemented in a memory controller with or without OS assistance [START_REF] Qureshi | Scalable high performance main memory system using phase-change memory technology[END_REF][START_REF] Ramos | Page placement in hybrid memory systems[END_REF][START_REF] Zhang | Exploring phase change memory and 3d die-stacking for power/thermal friendly, fast and durable memory architectures[END_REF][START_REF] Li | Managing hybrid main memories with a page-utility driven performance model[END_REF][START_REF] Dhiman | PDRAM: A hybrid PRAM and DRAM main memory system[END_REF][START_REF] Yoon | Row buffer locality aware caching policies for hybrid memories[END_REF][START_REF] Phadke | MLP aware heterogeneous memory system[END_REF][START_REF] Caulfield | Understanding the impact of emerging nonvolatile memories on high-performance, io-intensive computing[END_REF]. However, their page migrations can cause time and memory bandwidth overhead. There is also hardware space cost for recording memory access information which limits the size of management granularity too.

For portability, productivity, and simplicity, managed languages such as Java are increasingly dominant in mobiles, desktops, and big servers. For example, popular big data platforms, such as Hadoop and Spark, are all written in managed languages. Managed runtime provides services for performance optimization and automatic memory management. So it is important to adapt managed runtime for hybrid memory system.

This paper explores two opportunities: heap partition placement and object promotion, inside managed runtime for efficient hybrid memory management without additional data migration overhead. Hot objects (objects with high LLC miss density, i.e. LLC misses / object size) identification is conducted offline, thus no online profiling cost. We steal one bit from an object header as a flag to indicate hot object, so no impact on total space usage even at object grain. Our work is orthogonal to the management policies proposed inside an OS or hardware. They can work cooperatively but with reduced cost for managed applications. It can also work alone as a pure software portable hybrid-memory management.

For appropriate heap partition placement, we quantitatively analyze the LLC miss density for each partition of generational GC, including nursery, mature, metadata, and LOS (large object space). We demonstrate that the heap partitions according to object lifetime and characteristics also provide a natural partially classification of hot/cold objects. A 16 MB nursery covers 76% of total LLC misses, and most of them are store misses. Placing nursery in fast-space use 20% total memory footprint on average as fast-space, but only 10% performance difference from all heap in fast-space.

Besides the nursery, for workloads with relatively high LLC misses in mature partition, a small amount of the mature partition is allocated in fast-space to place hot objects during object promotion (which moves long-lived objects from nursery to mature partition). We develop an offline tool using the ASM bytecode manipulation framework [10] to record LLC miss density for each method. This information is used to direct JIT-generated machine-code to mark objects dereferenced by top-ranked methods as hot, so that they can later be moved to fast-space during object promotion. Results show that hot objects do have higher LLC miss density, more than 3 times of random distribution for SPECjbb and pmd, and placing them in fast-space further reduces their execution time by Mature …. ....

Nursery

Boot image

LOS Meta Other

Free Fig. 1: Virtual memory space partition of Jikes RVM 6% and 13% respectively, resulting in ultimately 27% and 31% faster using our policy compared to the default OS policy of interleaving page allocation. The structure of the paper is as follows. Section 2 and 3 are background for managed runtimes and related work. Section 4 is the management scheme we proposed. Section 5 introduces our hybrid memory emulation, and experimental settings. Finally, we discuss and conclude the results.

Managed runtime background

Managed runtime Managed-language applications require support services in order to run properly, such as Just-In-Time compilation (JIT) and Garbage collection (GC). Bytecode or only partially optimized code that are frequently executed are translated by the JIT into more optimized code. GC is used to automatically manage memory, including object allocation, and the identification and collection of unreachable objects. Among all types of GC, generational GC is the most popular one as it tends to reduce the overall burden of GC. It does this by partitioning the heap according to object lifetimes.

Generational GC and heap partition Since most objects have very short lifetimes, generational GC uses a low overhead space (called nursery space) for initial allocation and usage, and only moves objects that survive more frequent early collections to a longer lived space (called mature space). When a nursery is full, a minor GC is invoked to collect this space. When a minor GC fails due to a lack of space in mature space, a major GC will be performed. Nursery space is normally much smaller than mature space for efficient collection of short-lived objects. Jikes RVM also uses generational GC for its most efficient production configuration. This paper will use this configuration too. Under the production setting for the Jikes RVM, the heap uses a bump-allocation nursery and an Immix [START_REF] Blackburn | Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance[END_REF] mature space.

Other than nursery and mature spaces, Jikes RVM has spaces for large objects (LOS) including stacks, metadata (used by GC), as well as some small spaces for immortal (permanent), non-moving, and code objects, all of which share a discontiguous heap range with the mature space through a memory chunk free list. Figure 1 shows the virtual memory space partition of Jikes RVM. This paper will show how to distribute those partitions to appropriate memory space.

Related work

Different hybrid/heterogeneous main memory structures have been proposed, such as DRAM + NVM [START_REF] Bock | Concurrent page migration for mobile systems with os-managed hybrid memory[END_REF][START_REF] Dulloor | Data tiering in heterogeneous memory systems[END_REF][START_REF] Dhiman | PDRAM: A hybrid PRAM and DRAM main memory system[END_REF][START_REF] Li | Identifying opportunities for byte-addressable nonvolatile memory in extreme-scale scientific applications[END_REF][START_REF] Ramos | Page placement in hybrid memory systems[END_REF][START_REF] Wei | Exploiting program semantics to place data in hybrid memory[END_REF][START_REF] Zhang | Exploring phase change memory and 3d die-stacking for power/thermal friendly, fast and durable memory architectures[END_REF], on-chip memory + off-chip memory [START_REF] Dong | Simple but effective heterogeneous main memory with on-chip memory controller support[END_REF], and DRAMs with different feature values [START_REF] Chatterjee | Leveraging heterogeneity in DRAM main memories to accelerate critical word access[END_REF][START_REF] Phadke | MLP aware heterogeneous memory system[END_REF]. Though with different technologies, all of them share the common characteristic that different parts of the address space yield different access cost. Many technologies have been proposed to manage this heterogeneity.

Page access monitoring and migration Most of works use memory controllers to monitor page accesses [START_REF] Dong | Simple but effective heterogeneous main memory with on-chip memory controller support[END_REF][START_REF] Dhiman | PDRAM: A hybrid PRAM and DRAM main memory system[END_REF][START_REF] Ramos | Page placement in hybrid memory systems[END_REF][START_REF] Zhang | Exploring phase change memory and 3d die-stacking for power/thermal friendly, fast and durable memory architectures[END_REF]. The memory controller will then migrate top-ranked pages to fast-space, and OS will update the virtual address mapping table accordingly. However, these research all operate at a fixed grain, mostly on a page level. Besides, page migration invokes time and bandwidth overhead. Bock et al. [START_REF] Bock | Concurrent page migration for mobile systems with os-managed hybrid memory[END_REF] qualify that page migration can increase execution time by 25% on average. Our work utilize object promotion for object placement to suitable space, thus does not invoke extra data migration nor time overhead.

Direct data placement To avoid data migration overhead, there are works that place data in appropriate space directly according to their reference behaviours [START_REF] Chatterjee | Leveraging heterogeneity in DRAM main memories to accelerate critical word access[END_REF][START_REF] Li | Identifying opportunities for byte-addressable nonvolatile memory in extreme-scale scientific applications[END_REF][START_REF] Phadke | MLP aware heterogeneous memory system[END_REF][START_REF] Wei | Exploiting program semantics to place data in hybrid memory[END_REF]. Chatterjee et al. [START_REF] Chatterjee | Leveraging heterogeneity in DRAM main memories to accelerate critical word access[END_REF] organize a single cacheline across multiple memory channels. Critical word (normally the first word) in a cacheline will be placed in a low-latency channel. Wei et al. [START_REF] Wei | Exploiting program semantics to place data in hybrid memory[END_REF] show that for the groups of objects allocated at the same place in the source code, some of them exhibit similar behaviours, which can be used for static data placement. Li et al. [START_REF] Li | Identifying opportunities for byte-addressable nonvolatile memory in extreme-scale scientific applications[END_REF] develop a binary instrumentation tool to statistically report memory access patterns in stack, heap, and global data. Liu et al. [START_REF] Liu | Rethinking memory management in modern operating system: Horizontal, vertical or random?[END_REF] also implement a tool in OS to collect page access frequency, memory footprint, page re-use time, etc. which can be used to identify hot pages. Phadke and Narayanasamy [START_REF] Phadke | MLP aware heterogeneous memory system[END_REF] also profile applications' MLP and LLC misses offline to determine from which memory space each application would benefit the most. There are also works require programmers to help decide data placement [START_REF] Dulloor | Data tiering in heterogeneous memory systems[END_REF][START_REF] Hassan | Software-managed energy-efficient hybrid DRAM/NVM main memory[END_REF][START_REF] Malicevic | Exploiting NVM in large-scale graph analytics[END_REF]. Our paper uses offline profiling for data placement instead of online monitoring and migration, and does not invoke extra burden to programmers.

Adaption of managed runtime There are a few works related to the management of hybrid memory particularly for managed applications [START_REF] Nakagawa | Preliminary analysis of a write reduction method for non-volatile main memory on jikes rvm[END_REF][START_REF] Nakagawa | An analysis of the relationship between a write access reduction method for nvm/dram hybrid memory with programming language runtime support and execution policies of garbage collection[END_REF][START_REF] Nakagawa | Language runtime support for nvm/dram hybrid main memory[END_REF][START_REF] Nakagawa | NVM/DRAM hybrid memory management with language runtime support via MRW queue[END_REF][START_REF] Inoue | Identifying the sources of cache misses in java programs without relying on hardware counters[END_REF][START_REF] Schneider | Online optimizations driven by hardware performance monitoring[END_REF]. Shuichi Oikawa's group conduct some preliminary work [START_REF] Nakagawa | Preliminary analysis of a write reduction method for non-volatile main memory on jikes rvm[END_REF][START_REF] Nakagawa | An analysis of the relationship between a write access reduction method for nvm/dram hybrid memory with programming language runtime support and execution policies of garbage collection[END_REF][START_REF] Nakagawa | Language runtime support for nvm/dram hybrid main memory[END_REF][START_REF] Nakagawa | NVM/DRAM hybrid memory management with language runtime support via MRW queue[END_REF]. They state that nursery should be in the fast memory space, but without supporting data, nor for metadata, stacks or other partitions in the heap. They extend write barriers to record the writes to each object online to find hot objects. However that will include write hit to cache which can mislead the data placement. Besides, the process could result in a non-trivial execution overhead. Inoue et al. [START_REF] Inoue | Identifying the sources of cache misses in java programs without relying on hardware counters[END_REF] identify a code pattern in Java applications that can easily causing L1 and L2 cache misses. However, we find the number of memory accesses caused by this pattern is negligible. A series of papers [START_REF] Yang | Automatic heap sizing: taking real memory into account[END_REF][START_REF] Hertz | Garbage collection without paging[END_REF][START_REF] Yang | CRAMM: virtual memory support for garbage-collected applications[END_REF] describing managed runtime techniques focusing on avoiding page faulting to disk. Those techniques could be applied to vertical hybrid main memory, where fast-space (e.g. DRAM) acts as a cache for slow-space (e.g. NVM). However Dong et al. [START_REF] Dong | Simple but effective heterogeneous main memory with on-chip memory controller support[END_REF] show that if performance difference between fast-space and slow-space (typically seen in DRAM and NVM) is not obvious, it may not be adequate for vertical hybrid memory to be viable. Hertz et al. [START_REF] Hertz | Garbage collection without paging[END_REF] keep frequently used partitions such as nursery in memory, preventing them from being swapped, we show that this is still very significant for the nursery even in our context. This paper profiles LLC miss density for each partition and method offline to decide object placement during a GC process.

4 Hybrid memory management scheme

Overview

The goal of our management system is to enable a machine with a small proportion of fast-space to perform as well as a machine with the same amount of memory where all the memory is fast-space. Specifically, we want hot objects be allocated in fast-space. We exploit two opportunities in managed runtimes: partition placement and object promotion. Analysing the LLC miss density of the various partitions, we determine if all, none or part of a partition is placed in fast-space. Object promotion to the mature partition provides a decision point where an object must be moved, as such, a cheap opportunity for moving to either slow-space or fast-space. Selecting either fast-space or slow-space is driven by offline profiling to determine hot methods (highest LLC miss density) and online marking of objects accessed by those methods. Compared to work before, our scheme does not cause online monitoring or extra data migration, thus no relevant performance overhead.

Heap partition placement To profile each heap partition, we use numactl library to map virtual memory space to fast-space or slow-space, and use PMU counters to measure LLC load/store misses. As explained in Section 2, the nursery is a continuous space, and we map it as a whole. LOS, metadata, and mature partitions share a dis-contiguous memory range divided into chunks. Free chunks are maintained on a list and available for any partition to allocate. To support hybrid memory, we change to two freelists, one for slow-space and one for fastspace. Different partitions will be given the right to access a specific list or both lists. When no free chunks are available in the fast-space list, objects will be allocated from the slow-space list. The overhead of managing the additional list is negligible.

In Section 6, we will show that the LLC miss density of the nursery partition is much higher than other partitions, and as such it is mapped to fast-space. A small proportion of the mature partition is mapped to fast-space, and hot objects are moved to that portion when they are promoted.

Object promotion Minor GC promotes surviving objects from the nursery to the mature partition. During this process, our scheme promotes hot objects to fast-space, and all other surviving objects are promoted to slow-space. Section 3 discusses some related work for finding hot objects. However, our experiments show that they either have a large overhead in time and space, are not effective, or need a programmer to annotate the critical data. Dynamic optimization prevents popular instrumentation tools, such as VTune, from being effective for profiling hardware events.

We develop a tool called HMprof to profile LLC miss density in the mature partition for each method of an application. Since our experiments show that even though each application executes hundreds or thousands of methods, only a Fig. 2: Offline LLC miss per method profiling feeds into method footprint profiling which is then used to facilitate object promotion during normal execution.

dozen of them are responsible for most of the LLC misses, for example 0.4% and 1% of the methods in pmd and hsqldb covers 51% and 54.8% LLC respectively. This is a result of the particular access patterns and role of those methods. We will describe the implementation details next.

HMprof offline performance instrumentation

This instrumentation and profiling take place in two phases: first, collecting each method's performance counter statistics of any heap partition by instrumenting the application's java bytecode; and second, collecting the object visitation statistics for the candidate methods by altering the JIT. Figure 2, shows two offline profiling stages, and subsequence execution(s) of the application. These phases are described below.

LLC miss profiling Performance counter instrumentation is inserted into each method. Since methods may be compiled, and recompiled at runtime it is not possible to use the code location to identify the method, as such each method instrumented is given a unique numeric identifier as part of its instrumentation. The method code is transformed so that it has an additional local variable which is used to record a performance counter entry-value or re-entry value for the method, by invoking perf.readPerf(I)J, see Figure 3a. Upon exiting the method (either by return from the method, throwing an exception, or invoking a method), the entry-value, performance counter exit-value and the method identifier are logged.

The performance counters read and the values logged are maintained per thread. Logging a measurement is done by invoking perf.updatePerf(IIJ)V, see Figure 3b, which adds the performance counter delta for that thread to a thread specific array. Each element of the array corresponds to an instrumented thread identifier. Since there is no interaction between the threads, there is little impact overall, aside from a small perturbation of the cached data.

The statistics accumulated by a particular thread are finally added to the totals when that thread terminates. This imposes some cost on thread termination, but this does not have a significant performance impact. When all threads have terminated the final statistics values are written to a file. We can get a ranked list of methods according to their LLC misses in the mature partition.

Object footprint profiling Only LLC miss information is not enough to decide the hotness of a method, because the high LLC misses may be because it accesses a large amount of data. So LLC miss density is needed. Object visitation instrumentation is used to track the number of objects visited and their corresponding footprint for the top-ranked methods. An extra word is added to the object header to track which ones of those methods have visited a particular object. When a method visits an object, one corresponding bit will be marked. Because those methods are only a few, one extra word is enough. An extra phase is added to JIT to add marking code, and those methods are forcibly compiled with JIT. Thus, all objects dereferenced by any method that is being tracked are marked.

At the end of execution, the mature partition is scanned for marked objects, this excludes objects that do not survive a nursery collection. The number and footprint of the objects dereferences are accumulated per method. With the LLC miss information from the first step, we can work out the hot method list. Note that all the work above by HMprof is done offline. It will not add overhead to application run.

Hot Object Marking

After hot methods are found, we will mark the objects they visit as hot and move them to fast-space while an application runs. Similar as Section 4.2, we add a new phase in the HIR optimizations of JIT to mark the objects. This one flag bit is stolen from each object header. We target getfield, putfield, and call as three of the most common cases where objects are dereferenced / visited. Importantly a reference that is returned from a call or a getfield has the potential to be dereferenced, if such dereference is to occur then before the return value is dereferenced, the HIR inserts a null check. When a null check of this form is seen then that too is instrumented. In general, these will cover most of the operations that cause object and array dereferencing. Figure 4a shows the additional instructions that are inserted after the getfield, note, ObjRef reference will already have passed a null check or equivalent to get to this point, so it is safe to use. A similar pattern is used for putfiled and call (for virtual and interface calls). Similarly, we show in Figure 4b the additional code added after a null check. In both cases they will set (mark) the hot bit in the object header as true, and in later versions will only conditionally set the hot bit.

We used replay compile in our experiment, so the JIT cost will not be counted when the application runs. However, as Cao et al. [START_REF] Cao | The yin and yang of power and performance for asymmetric hardware and managed software[END_REF] shows that the JIT can run asynchronously with application threads, the application running time won't be sensitive to the JIT performance.

Experimental methodology

Hybrid memory emulator Because we do not have hybrid memory products and software simulators are very slow to run complex managed applications, we use a two-socket NUMA server (Intel Xeon X5650) with an interference program to mimic a hybrid memory structure. The interference program only runs on the remote CPUs, which regularly reads data from remote memory to increase the remote access latency and reduce its bandwidth for other applications. Tested benchmarks only run on the local ones.

Running the interference program and also using three channels for the local memory and a single channel for the remote memory, the latency of the mimic slow-space (remote memory) is 3.4 times that of the fast-space (local memory). The fast-space's read and write bandwidth is 5.3 times and 18.2 times those of the slow-space respectively, which is in keeping with current NVM characteristicsthe write bandwidth is much worse than read. Those numbers fall within the range of latency and bandwidth characteristics for current NVM technologies [START_REF] Caulfield | Understanding the impact of emerging nonvolatile memories on high-performance, io-intensive computing[END_REF][START_REF] Qureshi | Scalable high performance main memory system using phase-change memory technology[END_REF].

LLC size control The paper is about memory management policy design, and the memory footprint of the benchmarks is not large. To avoid the interference of LLC with the policy evaluation, we need to reduce the LLC size as much as possible. The method we used is mentioned in [START_REF] Ferdman | Clearing the clouds: a study of emerging scale-out workloads on modern hardware[END_REF] as cache polluting method to reduce the LLC cache size to 4 MB. Based on the settings above, Figure 5a shows our emulated experimental platform.

Virtual machine configurations We implemented our approach in the Jikes RVM. The mature space is set so that it is big enough to hold all objects that survive nursery GC eliminating the effects of major GC. We use replay compilation to remove the nondeterminism of the adaptive optimization system. It also means that in our experiments, we will not include any JIT processing time. We use DaCapo and SPECjbb benchmarks [START_REF] Blackburn | The dacapo benchmarks: java benchmarking development and analysis[END_REF] for our experiments. Figure 5b describes each benchmark and their working set size.

Default OS memory policy The default Linux memory policy interleaves allocation across all nodes in a NUMA system [START_REF]The Linux Kernel Organization: NUMA memory policy[END_REF]. This policy will compare with ours in the performance evaluation. In our experimental platform, we use mbind() system call to set a VMA (Virtual Memory Area) policy, and interleave page allocation in a task's virtual address to fast and slow memory modules.

6 Evaluation results

Heap partition placement

To decide how to place each partition in hybrid memory, we quantitatively evaluate the LLC misses associated with each partition, as well as the performance effect when it is placed in fast-space. Figure 6a shows the LLC miss distribution for each partition. It shows that though nursery is only 16 M, it covers the most LLC misses, 76% on average. This is primarily a result for all objects, except for large objects, being initially allocated in the nursery and causing a significant number of LLC misses during object initialization. We evaluate various nursery sizes from 4 M to 128 M. Results show that LLC misses due to nursery accesses increase with the nursery size. However, the curve flattens after 16 M for most applications, so we pick 16 M in the experiments. The mature partition covers 13% of the LLC misses on average. This percentage is relatively high for SPECjbb, pmd, and hsqldb, 44%, 27% and 22% respectively. The LLC misses hitting other partitions are small. Even though stacks are frequently accessed, they are mostly in cache, so will not cause many LLC misses. With the memory footprint result of total objects allocated in each partition, we compute the LLC miss density of the nursery to be 12.5 times that of the mature partition, 25 times that of LOS, and 33.3 times that of the metadata partition.

Some memory technology like NVM has a large write cost. Our hybrid memory emulator also sets the write bandwidth much smaller than that of the read bandwidth. Figure 6b shows the portion of store misses in total hitting the nursery and the mature partition when an application or GC executes. We can see that: a) for Java benchmarks, most LLC misses are store misses, 64% on average; b) almost all of these store misses hit in the nursery; c) in the nursery, nearly all store misses happen when application code executes, while in the mature partition, they happen during GC execution. Since the mature partition is set to be large enough that no major GC is triggered, all these store misses are a result of object promotion during minor GCs. So store misses are distributed evenly in the mature partition, which has been confirmed in our experiment results. This is undesirable for hybrid memory management especially for NVM, which expect the existence of write-hot data to put into fast-space.

Figure 7a is a stacked column chart showing the time effect of placing each partition in fast-space. The reference is the time when all heap is placed in fastspace. The total height of a bar shows the relative time when all heap is placed in slow-space. It reflects the LLC miss rate (LLC misses per instruction) of an application. lusearch has the highest LLC miss rate, 7.87 per 1K instructions. The second is xalan, 2.57 per 1K instructions. So when the heap is placed in slowspace, compared to being placed in fast-space, the running time is 4.57 and 2.22 times respectively. avrora has the lowest LLC miss rate, 1.03 per 1K instructions. So the time is basically the same when the heap is either in fast-space or slow- space. The figure also shows that corresponding to Figure 6a, placing a 16 M nursery into fast-space can greatly reduce the time, on average from 1.76 to 1.10, only a 10% difference from placing all the heap in fast-space. Placing the mature partition in fast-space can further reduce time from 1.08 to almost the same as all in fast-space (1.00) on average. For SPECjbb and pmd, the mature partition in fast-space reduces their normalized running time from 1.29 to 1.01, and 1.23 to 1.00. We then compare the execution time of the nursery in fast-space with the default page interleaving scheme of OS in Figure 7b. For the interleaving scheme, we compare both a 16 M and larger 64 M interleaved fast-space setting with our 16 M setting. However, in both instances as interleaving treats every partition evenly, the time is much more than only the 16 M nursery in fast-space, 1.38 and 1.35 respectively compared to 1.10 on average. All the results above suggest that the nursery should be placed directly into fast-space. It will get rid of the online monitoring and page migration costs. For mature space, we will allocate a small amount of fast-space for the hot objects found by our tool HMprof. The results will be analyzed in the next section.

Hot object allocation

Marked hot objects that are promoted to the mature partition are placed in fastspace, if available. In this subsection we show the effectiveness of our scheme, i.e. the objects moved to fast-space have high memory accesses but relatively small space cost. In particular SPECjbb, pmd and hsqldb are examined since they have more LLC misses in the mature partition than other benchmarks.

Figure 8a shows the correlation of fast-space usage and the LLC misses it covers when hot objects in mature partition are allocated in fast-space. pmd benefits most, with the hottest method only using 15% (12 M) of the mature partition objects (by volume) while covering 50% of the LLC misses. The hottest 12 methods of SPECjbb use 6% (18 M) of the mature partition objects (by volume) and cover 31% of the LLC misses. After the first 12 methods the thirteenth is proportionally less effective, resulting in a total use of 12% (36 M) of the mature partition objects (by volume) and 37% of the LLC misses being covered. The remaining methods are not considered hot or account for too few LLC misses. The hot methods for hsqldb are not obvious, and with the 12 hottest methods using 43% (42 M) of the mature partition objects (by volume) while covering 56% of the LLC misses, only a little better than random promotion. As noted in Section 6.1, the distribution of write LLC misses amongst objects in the mature partition is more even than that of read LLC misses, and given the cost difference between read and write, it is adversely affecting our performance improvements.

Figure 8b compares relative execution time of default OS page interleaving policy using 64 MB fast-space, only a 16 M nursery in fast-space, and both the 16 M nursery and hot objects of mature partition in fast-space. The policy proposed gets the best performance for the three benchmarks. For SPECjbb and pmd only 16% and 23% (respectively) of their working sets reside in fast-space (including the nursery partition), while only degrading performance by 23% and 12% respectively from that of all the heap in fast-space. Placing 51% of the working set for hsqldb in fast-space yields a performance degradation of 8% over than of all the heap in fast-space.

Conclusion

Hybrid memory is a promising alternative for future memory systems, however, its complexity challenges effective management. This paper explores unique opportunities inside managed runtimes for efficient and portable hybrid memory management with negligible online overhead. Our policy places the nursery and a small amount of the mature partition in fast-space. Compared to the default OS policy, for SPECjbb and pmd, our scheme is 27% and 31% faster. Compared to placing all the heap in fast-space, we place 16% and 23% heap in fast-space, but achieve only 23% and 12% performance difference respectively for the two benchmarks. In future work, we will target big data applications as test benchmarks.

Fig. 3 :

 3 Fig. 3: Example instrumentation in a method. g e t f i e l d R e s u l t ( RefType ) = ObjRef , O f f s e t , f i e l d b y t e l o a d t 0 (B) = ObjRef , HOT BIT OFFSET i n t o r t 1 (B) = t 0 (B) , HOT BIT MASK b y t e s t o r e t 1 (B) , ObjRef , HOT BIT OFFSET (a) getfield

Fig. 4 :

 4 Fig. 4: Example HIR after inserting hot object marking instructions.

Fig. 5 :

 5 Fig. 5: Experimental platform and benchmarks.

Fig. 6 :

 6 Fig. 6: (a) LLC misses distribution; (b) LLC store misses %.

Fig. 7 :

 7 Fig. 7: (a) Time effect of each partition, (b) Time comparison between nursery in fast-space and OS interleaving allocation.

Fig. 8 :

 8 Fig. 8: (a) The correlation of LLC misses hitting in fast-space and the fast-space used, (b) time comparison of interleaving, nursery in fast-space, and nursery plus hot objects of mature partition in fast-space.

Acknowledgement This work is supported by the National High Technology Research and Development Program of China (2015AA011505), the Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing (2016A03), the China Postdoctoral Science Foundation (2015T80139), the National Natural Science Foundation of China (61202055, 61221062, 61303053, 61432016, 61402445, 61432018, 61133005, 61272136, 61521092, 61502450).


Chao Tan

Luyu Li

Chentao Wu

Jie Li

DASM: A Dynamic Adaptive Forward Assembly Area Method to Accelerate Restore Speed for Deduplication-based Backup Systems

Keywords: Data Deduplication, Restore Speed, Reliability, Cache Policy, Performance Evaluation

Data deduplication yields an important role in modern backup systems for its demonstrated ability to improve storage efficiency. However, in deduplication-based backup systems, the consequent exhausting fragmentation problem has drawn ever-increasing attention over in terms of backup frequencies, which leads to the degradation of restoration speed. Various Methods are proposed to address this problem. However, most of them purchase restore speed at the expense of deduplication ratio reduction, which is not efficient. In this paper, we present a Dynamic Adaptive Forward Assembly Area Method, called DASM, to accelerate restore speed for deduplicationbased backup systems. DASM exploits the fragmentation information within the restored backup streams and dynamically trades off between chunk-level cache and container-level cache. DASM is a pure data restoration module which pursues optimal read performance without sacrificing deduplication ratio. Meanwhile, DASM is a resource independent and cache efficient scheme, which works well under different memory footprint restrictions. To demonstrate the effectiveness of DASM, we conduct several experiments under various backup workloads. The results show that, DASM is sensitive to fragmentation granularity and can accurately adapt to the changes of fragmentation size. Besides, experiments also show that DASM improves the restore speed of traditional LRU and ASM methods by up to 58.9% and 57.1%, respectively.

Introduction

Data deduplication is an effective technique used to improve storage efficiency in modern backup systems. [START_REF] Wallace | Characteristics of backup workloads in production systems[END_REF] [START_REF] Asaroand | Data de-duplication and disk-to-disk backup systems: Technical and business considerations[END_REF]. A typical deduplication-based backup system partitions backup streams into variable-size or fixed-size chunks. Each data chunk is identified by fingerprints calculated using cryptographic methods, such as SHA-1 [START_REF] Quinlan | Venti: A new approach to archival storage[END_REF]. Two chunks are considered to be duplicates if they have identical fingerprints. For each chunk, deduplication system employs Key-Value Store, also referred to fingerprint index, to identify possible duplicates. Only new fresh chunks are physically stored in containers while duplicates are eliminated.

However, in backup systems, the deviation between physical locality and logical locality increases when backup frequencies are improved, which leads to the physical dispersion of subsequent backup streams. The consequent exhausting fragmentation problem has drawn ever-increasing attention, which results in the degradation of restoration speed and expensive garbage collection operations [START_REF] Nam | Chunk fragmentation level: An effective indicator for read performance degradation in deduplication storage[END_REF] [10].

In the past decade, various methods are proposed to address this problem [START_REF] Mandagere | Demystifying data deduplication[END_REF] [START_REF] Paulo | A survey and classification of storage deduplication systems[END_REF]. Most of them purchase restore speed by sacrificing the deduplication ratio, which is costly [START_REF] Srinivasan | idedup: latency-aware, inline data deduplication for primary storage[END_REF] [START_REF] Lillibridge | Improving restore speed for backup systems that use inline chunk-based deduplication[END_REF]. Traditional restoration method employs LRU algorithm to cache chunk containers. In many scenarios, LRU buffers a large amount of unuseful chunks within containers. Besides, unlike some other applications, we have perfect pre-knowledge of future access informations during restoration, which cannot be well utilized by LRU. A few advanced approaches like ASM [START_REF] Lillibridge | Improving restore speed for backup systems that use inline chunk-based deduplication[END_REF] employs a forward assembly area to prefetch data chunks within a same container. Nevertheless, ASM is a chunk-level restoration method which limits its read performance due to the one-container cache regulation.

In this paper, we present a Dynamic Adaptive Forward Assembly Area Method, called DASM, to accelerate restore speed for deduplication-based backup systems. DASM exploits the fragmentation information within the restored backup streams and dynamically trades off between chunk-level cache and container-level cache. DASM is a pure data restoration module which pursues optimal read performance without sacrificing deduplication ratio. Meanwhile, DASM works well under different memory footprint restrictions.

The main contributions of this paper are summarized as follows,

• We propose a novel Dynamic Adaptive Forward Assembly Area method (DASM) for deduplication-based backup systems, which outperforms prior approaches in terms of restoration speed. DASM performs well in different scenarios, such as various memory restrictions and backup workloads. • We conduct several experiments to demonstrate the effectiveness of DASM.

The results show that DASM sharply improves the restore speed in various workloads.

The remainder of the paper is organized as follows. Section 2 reviews the background and the motivation of DASM. Section 3 illustrates the details of our DASM. Section 4 evaluates the performance of our scheme compared with other popular restoration cache algorithms. Finally we conclude our work in Section 5.

Background and Motivation

In this section, firstly, we introduce data deduplication briefly. Then we explore the fragmentation problem and how it impacts restoration speed. After that, an elaborate investigation of existing solutions and the motivation of our approach are exhibited. In backup systems, data deduplication can significantly improve storage efficiency [13] [2]. Figure 1 illustrates a typical data deduplication system architecture [START_REF] Fu | Design tradeoffs for data deduplication performance in backup workloads[END_REF].

Data Deduplication

Two chunks are considered to be duplicates if they have identical fingerprints. A typical deduplication system employs Key-Value Store, referred to fingerprint index as well, to identify possible duplicates. The key-value store maps each fingerprint to the corresponding physical location of data chunks. The recipe store is used to record logical fingerprint sequences according to the order of the original data stream, in case of future data restoration. And container store is a log-structured storage warehouse. After deduplication, data chunks are aggregated into fixed-sized containers(usually 4MB) and stored in a container store.

As shown in Figure 1, original backup streams are partitioned into several variable or fixed-size chunks. The hash engine calculates a fingerprint for each data chunk using cryptographic methods, such as SHA-1 [START_REF] Quinlan | Venti: A new approach to archival storage[END_REF].

Once a fingerprint is produced, the system takes following steps to eliminate duplicates: (1) Look up in the fingerprint cache. (2) If it is a cache hit, it means that a duplicate data chunk has already existed. In this situation, we can only record the fingerprint into recipe store and terminate the deduplication process.

(3) If cache misses, it looks up in the key-value store for further identification. (4) If there is a match, jump to step 5. Otherwise, the data chunk is considered to be a new fresh and stored into containers in the container store. (5) Record the fingerprint in the recipe store. [START_REF] Lillibridge | Improving restore speed for backup systems that use inline chunk-based deduplication[END_REF] Update fingerprint cache to explore data localities.

Fragmentation Problem and Restoration Speed

Fragmentation is one of the exhausting problems caused by typical deduplication scheme. As we can see in Figure 1, physical chunks are stored sequentially in order of their appearance. In the essence, the physical locality is similar to the logical locality for the first backup stream. However, this deviation increases as time goes because duplicate chunks are eliminated, which leads to the physical dispersion of subsequent backup streams.

Fragmentation problems is troublesome in many aspects. First, it degrades the restoration speed [START_REF] Nam | Chunk fragmentation level: An effective indicator for read performance degradation in deduplication storage[END_REF]. In deduplication systems, read and write operations are executes with basic granularity of container. Thus data restoration should be faster with consecutive physical distribution. Besides, chunks could become invalid because of data deletion operations. Physical dispersion results in holes within the containers, which leads to the emergence of inefficient garbage collection [START_REF] Preston | Restoring deduped data in deduplication systems[END_REF].

Various methods are proposed to address these problems. On one hand, several methods accelerate the restore speed via decreasing deduplication ratio. [START_REF] Fu | Accelerating restore and garbage collection in deduplicationbased backup systems via exploiting historical information[END_REF]. iDedup [START_REF] Lillibridge | Improving restore speed for backup systems that use inline chunk-based deduplication[END_REF] selectively deduplicates only sequences of disk blocks and replaces the expensive, on-disk, deduplication metadata with a smaller, in-memory cache. These techniques enable it to tradeoff deduplication ratio for performance. The context-based rewriting (CBR) minimizes drop in restore performance for latest backups by shifting fragmentation to older backups, which are rarely used for restore [START_REF] Kaczmarczyk | Reducing impact of data fragmentation caused by in-line deduplication[END_REF].

Traditional restoration method employs LRU algorithm to cache chunk containers. However, LRU is a container-level cache policy which buffers a large amount of unused chunks within containers. Besides, unlike other data access pattern, we have perfect pre-knowledge of future access information during restoration, which is not utilized by LRU. ASM [START_REF] Lillibridge | Improving restore speed for backup systems that use inline chunk-based deduplication[END_REF] employs a forward assembly area to prefetch data chunks within a same container. Nevertheless, ASM is a chunk-level restoration method which limits its read performance since the one-container cache regulation.

Forward Assembly Area

Forward Assembly Area (ASM) is a chunk-level restoration method which caches chunks rather than containers for better cache performance. Figure 2 ASM employs a large forward assembly area to assemble M bytes of the restored backup. Meanwhile, it utilizes two dedicated buffers, a recipe buffer to cache recipe streams and a chunk-container-sized buffer to cache proper containers that is being used.

In a simple case shown in Figure 2, firstly, ASM reads the recipes from their related recipe store preserved in disk into the recipe buffer. Then, ASM obtains the top n recipes which hold at most M bytes of the restored data. After that, ASM finds the earliest unrestored chunk and loads the corresponding container into its I/O buffer. For chunk1 with fingerprint f p1, the corresponding container container13 is loaded into the container buffer. Then, all the chunks belongs to container13 in the top n recipe items will be restored ,which are chunk1, chunk5,chunk7 in this case. ASM repeats this procedure until the M bytes are completely filled. Finally, ASM flushes these M bytes of restored data into disk.

ASM restores M bytes every time and only one container is loaded into memory during each recovery, which improves the cache performance. However, the one-container regulation may degrade the read performance since each container have to wait until the last one finishes restoration of all chunks.

Our Motivation

Many previous literatures attempt to figure out the fragmentation problem through deduplication procedures, such as rewriting. These methods purchase restore speed at the expense of deduplication ratio reduction, which is unworthy. From the restoration's perspective purely, traditional LRU cache policy ignores the perfect pre-knowledge of future access information during restoration and holds plenty of useless chunks in memory, which is a big resource waste. ASM is a chunk-level restoration method which limits its read performance since the one-container cache regulation.

To address this problem, we propose a novel Dynamic Adaptive Forward Assembly Area method (DASM) for deduplication-based backup systems, which arms ASM with a multiple-container-sized cache. DASM adaptively adjusts the size of the forward assembly area and the container cache according to the fragmentation level of the restored backup streams to pursue optimal restoration performance. DASM is resource independent and cache efficient, which outperforms prior approaches under different memory footprint restrictions and various backup workloads.

Design of DASM

To overcome the shortages of the forward assembly area method, we present a Dynamic Adaptive Forward Assembly Area method (DASM) which arms ASM with a multiple-container-sized cache. Figure 3 pendencies and increase cache efficiencies, we impose restrictions on memory footprint by bounding the overall size of the ASM area and the container cache.

Besides the original ASM area and the new joint container cache, DASM involves other two main components as below,

• Dynamic Orthotics

Dynamic Orthotics is a calculation model which exploits future access information to pursue optimal restoration performance within the restriction of finite memory footprint. It regards the fragmentation rate as a major criterion and dynamically adjusts the proportion of the ASM area to the container cache. Details are discussed in Section 3.1.

• Cache Policy

Cache Policy module depicts the cache replacement policies carried out in the container cache. It works as a centralized scheduler which dispatches containers legitimately to reduce cache miss and minimize the bandwidth requirement.

DASM abides by the following steps, 1) Tradeoff the ASM area and the container cache according to the fragmentation rate, which are typically done by Dynamic Orthotics module. After Dynamic Orthotics completes the tradeoff, the top n chunks within C containers are restored at this time.

2) Load the required C containers into the container cache. If there is a cache miss, DASM selects appropriate cache policies for container replacement.

3) Execute the ASM restoration schemes policies repeatedly: find the earliest unrestored chunk and copy all the chunks pertains to its corresponding container to the forward assembly area.

4) Flush all the restored data to disks and restart from step 1.

Dynamic Orthotics

Restoration speed is strongly depended on the fragmentation granularity of the restored data stream. We consider two extreme situations, (1) Lowest fragmentation granularity for the first backup: as for the first backup. in this scenario, we can shrink container caches to a single container size since almost all consecutive chunks belong to a same container.

(2) Highest fragmentation granularity that almost all unique chunks are placed in different containers with each other: Under this circumstance, we have to shrink ASM area to acquire as large container cache area as possible.

Based on these observations, we propose a mathematical model called Dynamic Orthotics, which exploits future access information to pursue optimal restoration performance within the restriction of finite memory footprint. It regards fragmentation rate as the major criterion and dynamically adjusts the proportion of the ASM area to container cache.

For clarity, we define a few symbols as shown in Table 1. Suppose there are n chunks waiting to be restored in the forward assembly area and they belong to C n containers. To obtain optimal restoration performance, ASM area should hold exactly ∑ n i=1 chunksize i bytes while container cache has the ability to load accurately C n containers. The relationships between these notations can be formulated by the following equations:

|ASM | = n ∑ i=1 chunksize i (1) |CC| = C n * CS (2) |ASM | + |CC| ≤ |M F P | (3)
We define fragmentation rate by the following equation,

f ragmentation rate = |CC| |M F P | (4)
As shown in Algorithm 1, Dynamic Orthotics reads chunk information sequentially from the recipe buffer. For each chunk, dynamic orthotics calculates whether it can be pushed into ASM. If Equation 1

Near-optimal Cache Policy

To reduce container cache miss penalty as much as possible, we implement a variant of Belady's optimal replacement cache policy [START_REF] Belady | A study of replacement algorithms for a virtual-storage computer[END_REF].

Belady's policy evicts the cached container that will be accessed in the farthest future. With foreseeable container access information, it is oversimplified to achieve optimality. However, with fragmentation rate high enough, we may have to traverse along the recipe list for a long time to find a victim, which is expensive. Therefore we establish several cache policies which could achieve near-optimal performance under framework of DASM.

• If a container has already existed in the container cache and it will be reused during the next round, keep it in the cache. • If there exists no such containers, evict all containers in the container cache.

DASM dynamically adapts the size of container cache and reserve exactly C n containers' size for the containers required. Since containers which are not reused during the next round will be evicted no matter how, we just evict them without considering replacement order.

Performance Evaluation

To demonstrate the effectiveness of DASM, we conduct several experiments using various backup datasets to evaluate the performance of DASM and compare it with traditional restore methods such as LRU and ASM.

Evaluation Methodology 1) Evaluation Platform

We utilize an open-source deduplication platform called Deduplication Framework (DeFrame) [START_REF] Fu | Design tradeoffs for data deduplication performance in backup workloads[END_REF], for comprehensive data deduplication evaluation. DeFrame implements the entire parameter space discussed in a modular and extensible fashion; this enables apple-to-apple comparisons among both existing and potential solutions [START_REF] Fu | Design tradeoffs for data deduplication performance in backup workloads[END_REF].

We implement and evaluate a DASM prototype on DeFrame under the Ubuntu 14.10 operating system, with linux kernel version 3.13.0, running on a quad-core Intel i5-4430 processor at 3.00 GHz, with a 12GB RAM, a 1TB 7200RPM hard disk drive.

2) Traditional restoration methods for comparison

This evaluation employs LRU, ASM as the contrasts. As illustrates in Section 2, traditional restoration method employs LRU algorithm to cache chunk containers. ASM employs a forward assembly area to prefetch data chunks within a same container.

3) Evaluation Metrics

In this paper, we exploit restoration speed as our major evaluation metric. Restore speeds are measured in term of encoding time in seconds.Besides, we explores fragmentation rate to show that DASM is sensitive to fragmentation degree and can adapt to fragmentation change accurately. The fragmentation rate is defined in Section 3.1 as:

f ragmentation rate = |CC| |M F P | (5)

4) Evaluation Datasets

We choose three real-world files as our datasets: ubuntu-14.04.3, ubuntu-14.10 and ubuntu-15.04. These datasets are firstly stored as the 1st, 2nd and 3rd backup streams in the deduplication systems, respectively. After that, we evaluates performance of LRU, ASM and our DASM methods by restoring each original backup streams. Table 2 lists some detailed information about these datasets.

Experimental Results

In this section, we give the experimental results of DASM and compare it with LRU and ASM under three backup streams to illustrate its benefits.

1) Restore Speed Under Different Cache Size

Analysis

Traditional LRU cache policy ignores the perfect pre-knowledge of future access information during restoration and holds plenty of useless chunks in memory, which is a big resource waste. ASM is a chunk-level restoration method which limits its read performance since the one-container cache regulation.

From the results in the previous subsecitons, it is clear that DASM approach has many advantages on restore speed in backup systems compared to the previous restore methods: LRU and ASM. There are several reasons to achieve these gains. First, DASM integrates container cache which can effectively enhance the hit ratio of chunks and reduce read latency. Second, DASM can accurately capture current fragmentation granularit and dynamiclly adjust ASM area size and container cache size to achieve the best performance. Therefore, DASM outperforms LRU and ASM enormously.

Conclusions

In this paper, we present a Dynamic Adaptive Forward Assembly Area Method, called DASM, to accelerate restore speed for deduplication-based backup systems. Different from previous approaches, DASM is a pure data restoration module which pursue optimal read performance without sacrificing deduplication ratio. DASM exploits the fragmentation information within the restored backup streams and dynamically trades off between chunk-level cache and container-level cache which leverages both advantages of LRU and ASM. Experiments results show that DASM is sensitive to fragmentation degree and can adapt to fragmentation change accurately. Besides, experiments also show that DASM improves the restore speed of traditional LRU and ASM methods by up to 58.9% and 57.1%, respectively.

Fig. 1 .

 1 Fig. 1. Data Deduplication System Architecture.

Fig. 3 .

 3 Fig. 3. Overview of Dynamic Adaptive Forward Assembly Area Method(DASM).

Fig. 6 .

 6 Fig. 6. Fragmentation rate curves under different backup streams

  depicts the basic functions of ASM.

										Memory
	Recipe List				Forward Assembly Area			Container 13
	FP CID fp1 13 fp2 51 10609 Off 0 fp3 49 12708 fp4 22 14608 fp5 13 18807	Len 4093 6737 1972 2100 4099	2. Read a fingerprint	chunk1	chunk5	chunk1	chunk7	4. Copy all chunks in this container	chunk1 chunk19 chunk7 chunk5
	fp6 51 22844	4037
	fp1 13	0	4093
	fp7 13 12885	3741
			fpafpb	fph	A	E	I	M
	1. Read recipe from recipe store	fpafpi fpafpi	fph fpm	B C D	F G H	J K L	Blank	3. Read container from container store
	Disk		Recipe Store		Container Store
			Fig. 2. Forward Assembly Area(ASM) Method.

Table 1 .

 1 Notations of DASM Overall memory footprint whose size is donated by |M F P | chunksizei Chunk size of the ith chunk in the recipe stream CiThe overall number of containers required by the top i chunks nThe number of chunks waiting to be restored at a time rate Fragmentation Rate

	Notation Description
	ASM	Forward assembly area whose size is donated by |ASM |
	CC	Container cache whose size is donated by |CC|
	CS	Container Size
	M F P

  2 3 still holds, then add the chunk into ASM. Otherwise, terminate and adjust |ASM| and |CC| according to the returned value.

	Algorithm 1: Dynamic Orthotics
	Aim: Dynamically adjust the proportion of the ASM area to container cache
	according to the fragmentation rate.
	while (chunk ← RecipeBuffer.head)̸ = null do
	C ′ n = chunk.CID in CC? Cn : Cn + 1
	if (ASM.size+chunk.size)+C ′ n *CS ≤ MFP.size then
	ASM.size+=chunk.sie
	Cn=C ′ n
	else
	return ASM.size, Cn

Table 2 .

 2 Detailed Information about Datasets

	Backup data	Bytes	Chunks	Average Chunk Size	Containers
	ubuntu-14.04.3	1054867456 228791	4610	255
	ubuntu-14.10	1186529280 257945	4599	378
	ubuntu-15.04	1150844928 250609	4592	480

Table 3

 3

	and Figure 4 de-

Table 3 .

 3 Comparison among LRU, ASM and DASM under different cache size in terms of restore speed.

						128M		256M			1G
				1st	2nd	3rd	1st	2nd 3rd	1st	2nd	3rd
		DASM	4.733 6.047 5.982 4.552 5.689 5.329 4.34 5.937 4.947
		LRU	11.507 12.233 12.311 8.173 8.245 7.874 9.081 9.461 10.114
		Improvement 58.9% 50.6% 51.4% 44.3% 31.0% 32.3% 52.2% 57.2% 51.1%
		ASM	8.341 9.491 9.623 8.453 8.127 6.693 9.572 10.692 11.544
		Improvement 43.3% 36.3% 37.8% 46.1% 30.0% 20.3% 54.7% 44.5% 57.1%
	6 8 10 12 14	11.507 8.341 4.733	8.173 8.453 4.552	7.081 7.572 4.34	6 8 10 12 14	12.233 9.491 6.047	8.245 8.127 5.689	9.461 10.692 5.937	6 8 10 12 14	5.982 9.623 12.311	6.693 5.329 7.874	4.947 11.544 10.114
	4						4				4
	2						2				2
	0						0				0
		MFP=128M MFP=256M MFP=1G		MFP=128M MFP=256M MFP=1G		MFP=128M MFP=256M MFP=1G
		LRU ASM DASM			LRU ASM DASM		LRU ASM DASM
		(a)

Restore speed for the 1 st backup (b) Restore speed for the 2 nd backup (c) Restore speed for the 3 rd backup Fig. 4.

  Comparison among LRU, ASM and DASM under different cache size in terms of restore speed.

	6 8 10 12 14	8.341 4.733 11.507	9.491 6.047 12.233	9.623 5.982 12.311	4 6 8 10	4.552 8.453 8.173	5.689 8.127 8.245	6.693 5.329 7.874	6 8 10 12 14	4.34 7.572 7.081	5.937 10.692 9.461	4.947 11.544 10.114
	2 4				2				2 4
	0				0				0
		1st	2nd	3rd		1st	2nd	3rd		1st	2nd	3rd
		LRU ASM DASM		LRU ASM DASM		LRU ASM DASM
		(a) Restore speed for 128M MFP		(b) Restore speed for 256M MFP		(c) Restore speed for 1G MFP
	Fig. 5. Comparison among LRU, ASM and DASM under different backup streams in
	terms of restore speed.

2)

Restore Speed Under Different backup streams Figure

  5 illustrates the comparison between restore speed among LRU, ASM and DASM under different backup streams. Since the first backup is stored sequentially among the containers, which means that it carries the lowest fragmentation problem, it is restored fastest under arbitrary circumstances. As shown in the Figure, DASM outperforms LRU and ASM under any backup streams.3) Fragmentation Rate Figure6depicts the fragmentation rate changing curves under different backup streams. As we can see in the figure, regardless of the size of memory footprint, as backup time increases, the average fragmentation rate rises with amplitude aggrandizament (3rd > 2nd > 1st). This phenomenon implies that our DASM can effectively and accurately detect fragmentation changes and adjust accordingly.

Acknowledgement

We thank anonymous reviewers for their insightful comments. This work is partially sponsored by the National 863 Program of China (No. 2015AA015302), the National 973 Program of China No.2015CB352403), the National Natural Science Foundation of China (NSFC) (No. 61332001, No. 61303012, and No. 61572323), the Scientific Research Foundation for the Returned Overseas Chinese Scholars, and the CCF-Tencent Open Fund.


Canqun Yang
email: canqun@nudt.edu.cn

Zhaokui Li
email: zhaokuili@yeah.net

Jianbin Fang

Tao Tang

Xuhao Chen

Streaming Applications on Heterogeneous Platforms

Keywords: Multiple Streams, Heterogeneous Platforms, Performance

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Heterogeneous platforms are increasingly popular in many application domains [START_REF] Owens | GPU Computing[END_REF]. The combination of using a host CPU combined with a specialized processing unit (e.g., GPGPUs or Intel Xeon Phi) has been shown in many cases to improve the performance of an application by significant amounts. Typically, the host part of a heterogeneous platform manages the execution context while the timeconsuming code piece is offloaded to the coprocessor. Leveraging such platforms can not only enable the achievement of high peak performance, but increase the performance per Watt ratio.

Given a heterogeneous platform, how to realize its performance potentials remains a challenging issue. In particular, programmers need to explicitly move data between host and device over PCIe before and/or after running kernels. The overhead counts when data transferring takes a decent amount of time, and determines whether to perform offloading is worthwhile [START_REF] Boyer | Improving GPU performance prediction with data transfer modeling[END_REF][START_REF] Shuai | Rodinia: A benchmark suite for heterogeneous computing[END_REF][START_REF] Gregg | Where is the data? why you cannot debate CPU vs. GPU performance without the answer[END_REF]. To hide this overhead, overlapping kernel executions with data movements is required. To this end, multiple streams (or streaming mechanism) has been introduced, e.g., CUDA Streams [START_REF]CUDA C Best Practices Guide Version 7[END_REF], OpenCL Command Queues [START_REF]OpenCL -The open standard for parallel programming of heterogeneous systems[END_REF], and Intel's hStreams [START_REF]hStreams Architecture document for Intel MPSS 3[END_REF]. These implementations of multiple streams spawn more than one streams/pipelines so that the data movement stage of one pipeline overlaps the kernel execution stage of another 1 .

Prior works on multiple streams mainly focus on GPUs and the potential of using multiple streams on GPUs is shown to be significant [START_REF] Gómez-Luna | Performance models for asynchronous data transfers on consumer graphics processing units[END_REF][START_REF] Ino | Gpu-chariot: A programming framework for stream applications running on multi-gpu systems[END_REF][START_REF] Liu | Software pipelining for graphic processing unit acceleration: Partition, scheduling and granularity[END_REF][START_REF] Van Werkhoven | Performance models for CPU-GPU data transfers[END_REF]. Liu et al. give a detailed study into how to achieve optimal task partition within an analytical framework for AMD GPUs and NVIDIA GPUs [START_REF] Liu | Software pipelining for graphic processing unit acceleration: Partition, scheduling and granularity[END_REF]. In [START_REF] Gómez-Luna | Performance models for asynchronous data transfers on consumer graphics processing units[END_REF], the authors model the performance of asynchronous data transfers of CUDA streams to determine the optimal number of streams. However, these studies have shown very limited number of cases, which leaves two questions unanswered: (1) whether each application is required and worthwhile to use multiple streams on a given heterogeneous platform?, [START_REF] Boyer | Improving GPU performance prediction with data transfer modeling[END_REF] whether each potential application is streamable or overlappable? If so, how can we stream the code?

To systematically answer these questions, we (1) build a statistical view of the data transfer (H2D and D2H) fraction for a large number of test cases, and (2) present our approach to stream different applications. Specifically, we statistically show that more than 50% test cases (among 223) are not worthwhile to use multiple streams. The fraction of H2D varies over platforms, applications, code variants, and input configurations. Further, we identify two types of nonstreamable codes (Iterative and SYNC) and three categories of streamable code based on task dependency ( embarrassingly independent, false dependent, and true dependent). Different approaches are proposed to either eliminate or respect the data dependency. As case studies, we stream 13 benchmarks of different categories and show their streaming performance impact. Our experimental results show that using multiple streams gives a performance improvement ranging from 8% to 90%. To the best of our knowledge, this is the first comprehensive and systematic study of multiple streams in terms of both streaming necessity and how-to. To summarize, we make the following contributions:

-We build a statistical view of the data transfer fraction (R) with a large number of test cases and analyze its impacting factors (Section 3). -We categorize the heterogeneous codes based on task dependency and present our approach to stream three types of applications (Section 4). -We show a generic flow of using multiple streams for a given application: calculating R and performing code streaming (Section 3, 4). -We demonstrate the performance impact of using multiple streams on the CPU-MIC platform with 13 streamed benchmarks (Section 5).

Related Work

In this section, we list the related work on pipelining, multi-tasking, workload partitioning, multi-stream modeling, and offloading necessity.

Pipelinining is widely used in modern computer architectures [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF]. Specifically, the pipeline stages of an instruction run on different functional units, e.g., arithmetic units or data loading units. In this way, the stages from different instructions can occupy the same functional unit in different time steps, thus improving the overall system throughput. Likewise, the execution of a heterogeneous application is divided into stages (H2D, KEX, D2H), and can exploit the idea of software pipelining on the heterogeneous platforms.

Multi-tasking provides concurrent execution of multiple applications on a single device. In [START_REF] Adriaens | The case for GPGPU spatial multitasking[END_REF], the authors propose and make the case for a GPU multitasking technique called spatial multitasking. The experimental results show that the proposed spatial multitasking can obtain a higher performance over cooperative multitasking. In [START_REF] Wende | Multi-threaded kernel offloading to GPGPU using Hyper-Q on kepler architecture[END_REF], Wende et al. investigate the concurrent kernel execution mechanism that enables multiple small kernels to run concurrently on the Kepler GPUs. Also, the authors evaluate the Xeon Phi offload models with multi-threaded and multi-process host applications with concurrent coprocessor offloading [START_REF] Wende | Concurrent kernel execution on xeon phi within parallel heterogeneous workloads[END_REF]. Both multitasking and multiple streams share the idea of spatial resource sharing. Different from multi-tasking, using multiple streams needs to partition the workload of a single application (rather than multiple applications) into many tasks.

Workload Partitioning: There is a large body of workload partitioning techniques, which intelligently partition the workload between a CPU and a coprocessor at the level of algorithm [START_REF] Yang | Adaptive optimization for petascale heterogeneous CPU/GPU computing[END_REF] [START_REF] Yang | A peta-scalable CPU-GPU algorithm for global atmospheric simulations[END_REF] or during program execution [START_REF] Takizawa | SPRAT: Runtime processor selection for energy-aware computing[END_REF] [START_REF] Pienaar | MDR: Performance model driven runtime for heterogeneous parallel platforms[END_REF]. Partitioning workloads aims to use unique architectural strength of processing units and improve resource utilization [START_REF] Mittal | A survey of CPU-GPU heterogeneous computing techniques[END_REF]. In this work, we focus on how to efficiently utilize the coprocessing device with multiple streams. Ultimately, we need to leverage both workload partitioning and multiple streams to minimize the end-to-end execution time.

Multiple Streams Modeling: In [START_REF] Gómez-Luna | Performance models for asynchronous data transfers on consumer graphics processing units[END_REF], Gomez-Luna et al. present performance models for asynchronous data transfers on different GPU architectures. The models permit programmers to estimate the optimal number of streams in which the computation on the GPU should be broken up. In [START_REF] Van Werkhoven | Performance models for CPU-GPU data transfers[END_REF], Werkhoven et al. present an analytical performance model to indicate when to apply which overlapping method on GPUs. The evaluation results show that the performance model are capable of correctly classifying the relative performance of the different implementations. In [START_REF] Liu | Software pipelining for graphic processing unit acceleration: Partition, scheduling and granularity[END_REF], Liu et al. carry out a systematic investigation into task partitioning to achieve maximum performance gain for AMD and NVIDIA GPUs. Unlike these works, we aim to evaluate the necessity of using multiple streams and investigate how to use streams systematically. Using a model on Phi to determine the number of streams will be investigated as our future work.

Offloading Necessity: Meswani et al. have developed a framework for predicting the performance of applications executing on accelerators [START_REF] Mitesh | Modeling and predicting performance of high performance computing applications on hardware accelerators[END_REF]. Using automatically extracted application signatures and a machine profile based on benchmarks, they aim to predict the application running time before the application is ported. Evaluating offloading necessity is a former step of applying multiple streams. In this work, we evaluate the necessity of using multiple streams with a statistical approach.

A Statistical View

In this section, we give a statistical view of how many applications are worthwhile to be streamed on heterogeneous platforms, and analyze the factors that impact the streaming necessity.

Benchmarks and Datasets

As shown in Table 1, we use a large number of benchmarks that cover a broad range of interesting applications domains for heterogeneous computing. These benchmarks are from the Rodinia Benchmark Suite, the Parboil Benchmark Suite, the NVIDIA SDK, and the AMD APP SDK. In total, we employ 56 benchmarks and 223 configurations. The details about how applications are configured are summarized in Table 1. Note that we remove the redundant applications among the four benchmark suites when necessary.

Experimental Platforms

The heterogeneous platform used in this work includes a dual-socket Intel Xeon CPU (12 cores for each socket) and an Intel Xeon 31SP Phi (57 cores for each card). The host CPUs and the cards are connected by a PCIe connection. As for the software, the host CPU runs Redhat Linux v7.0 (the kernel version is 3.10.0-123.el7.x86 64), while the coprocessor runs a customized uOS (v2.6.38.8).

Intel's MPSS (v3.6) is used as the driver and the communication backbone between the host and the coprocessor. Also, we use Intel's multi-stream implementation hStreams (v3.5.2) and Intel's OpenCL SDK (v14.2). Note that the applications in Table 1 are in OpenCL, while the pipelined versions are in hStreams.

Measurement Methodology

A typical heterogeneous code has three parts: [START_REF] Adriaens | The case for GPGPU spatial multitasking[END_REF] transferring data from host to device (H2D), (2) kernel execution (KEX), and (3) moving data from device back (D2H). To measure the percentage of each stage, we run the codes in a strictly stage-by-stage manner. Moreover, we perform 11 runs and calculate the median value. Before uploading datasets, buffer allocation on the device side is required. Due to the usage of the lazy allocation policy, the allocation overhead is often counted into H2D. Thus, we argue that H2D might be larger than the actual host-to-device data transferring time.

Results and Analysis

We define data transfer ratio (R) as the fraction of the data transfer time to the total execution time, and take this metric (R) as an indicator of whether it is necessary to use multiple streams. Figure 1 shows the CDF distribution of the H2D and D2H duration versus the overall execution time (R H2D and R D2H ). We observe that the CDF is over 50% when R H2D = 0.1. That is, the H2D transfer time takes less than 10% for more than 50% configurations. Meanwhile, the number is even larger (around 70%) for the D2H part. In the remaining contents, we will focus on R H2D and use R (instead of R H2D ) for clarity. The Impact of Input Datasets Typically, the H2D ratio will remain when changing the input datasets. This is because the computation often changes linearly over the data amount. But this is not necessarily the case. Figure 2 shows how R changes with the input datasets for lbm and FDTD3d, respectively. We note that, for lbm, using the short configuration takes a decent amount of time to move data from host to device, while the data amount takes a much smaller proportion for the long configuration. For FDTD3d, users have to specify the number of time steps according to their needs. We note that the kernel execution time increases over time steps. When streaming such applications, it is necessary to focus on the commonly used datasets. The Impact of Platform Divergence Figure 4 shows how R changes on MIC and a K80 GPU2 . We see that the kernel execution time (of nn) on the MIC occupies 33% on average while the number is only around 2% on the GPU. This is due to the huge processing power from NVIDIA K80, which reduces the KEX fraction significantly. Ideally, using the streaming mechanism can improve the overall performance by 2% on the GPU. In this case, we argue that it is unnecessary to use multiple streams on GPU. (b) on GPU. To summarize, we observe that R varies over platforms, benchmarks, code variants, and input configurations. Each benchmark has a unique balance between computation and memory accesses. Different code variants lead to the differences in transferred data amounts and kernel execution time. Also, input configurations can incur changes in transferred data amounts and/or kernel execution time. Furthermore, R depends on hardware capabilities (e.g., the PCIe interconnect and the accelerator).

We use R as an indicator of deciding whether the target application is worthwhile to be streamed. Figure 1 shows that H2D takes only 10% of the total execution time for over 50% test cases. We argue that, on the one hand, the applications are not worthwhile to be streamed when R is small. This is due to two factors: (1) code streaming introduces overheads for filling and emptying the pipeline, and ( 2) streaming an application requires extra programming efforts from reconstructing data structures and managing streams. Thus, streaming such applications might lead to a performance degradation compared with the non-streamed code. On the other hand, when R is too large (e.g., 90%), it is equally not worthwhile to apply streams. When the fraction of H2D is too large, using accelerators may lead to a performance drop (when comparing to the case of only using CPUs), not to mention using streams. In real-world cases, users need make the streaming decision based on the value of R and the coding effort.

Our Streaming Approach

Categorization

After determining the necessity to apply the pipelining/streaming mechanism, we further investigate how-to. Generally, we divide applications into tasks which are mapped onto different processing cores. As we have mentioned above, each task includes the subtasks of data transfers and kernel execution. To pipeline codes, we should guarantee that there exist independent tasks running concurrently. Once discovering independent tasks, we are able to overlap the execution of H2D from one task and KEX from another (Figure 5(a)). For a single task, H2D is dependent on KEX.

In practice, more than one H2D may depend on a single kernel execution (Figure 5(b)). Thus, we need to analyze each H2D-KEX dependency to determine whether each pair can be overlapped. Moreover, an application often has more than one kernel. Implicitly, each kernel is synchronized at the end of its execution. Therefore, the kernel execution order is strictly respected within a single task. Figure 5(c) shows that H2D( 1) is depended by KEX( 1), but the data is not used til the execution of KEX( 2). Thus, this data transfer can be delayed right before KEX(2) when analyzing dependency and/or streaming the code. Based on the dependency analysis, we categorize the codes listed in Table 1 as streamable codes (Section 4.2) and non-streamable codes. The first pattern (SYNC) of non-streamed codes is when the H2D data is shared by all the tasks of an application. In this case, the whole data transfer has to be finished before kernel execution. The second non-streamable pattern is characterized as Iterative, for which KEX will be invoked in an iterative manner once the data is located on device. Although such cases can be streamed by overlapping the data transfer and the first iteration of kernel execution, we argue that the overlapping brings no performance benefit for a large number of iterations.

We analyze the heterogeneous codes listed in Table 1 and categorize them in Table 2. Each nonstreamable code is labeled with SYNC or Iterative. We note that the kernel of hearwall has such a large number of lines of codes and complex structures that its execution takes a major proportion of the end-to-end execution time. It is unnecessary to stream such code on any platform. Due to the multiple H2D-KEX dependency pairs, an application might fall into more than one category (e.g., streamcluster). Also, the kernel of myocyte runs sequentially and thus there are no concurrent tasks for the purpose of pipelining. For the streamable codes, we group them into three categories, which are detailed in Section 4.2.

Code Streaming

We divide the streamable/overlappable applications into three categories based on task dependency: (1) embarrassingly independent, (2) false dependent, and (3) true dependent. Tasks are generated based on input or output data partitioning, and thus task dependency shows as a form of data dependency. We will explain them one by one.

Embarrassingly Independent Tasks from such overlappable applications are completely independent. Thus, there is no data dependency between tasks. Taking nn (nearest neighbor) for example, it finds the k-nearest neighbors from an unstructured data set. The sequential nn algorithm reads in one record at a time, calculates the Euclidean distance from the target latitude and longitude, and evaluates the k nearest neighbors. By analyzing its code, we notice no dependency between the input data. Figure 6 shows how to partition the input data. Assuming 16 elements in the set, we divide them into 4 groups, which represent 4 tasks. Then we spawn streams to run the tasks. Due to no dependency, data transferring from one task can overlap kernel execution from another. More Embarrassingly Independent applications are shown in Table 2.

False Dependent There exist data dependencies in such overlappable applications, but the dependencies come from read-only data (i.e., RAR dependency). In this case, two tasks will share common data elements. A straightforward solution to this issue is that each task moves the shared data elements separately. For example, FWT (fast walsh transform) is a class of generalized Fourier transformations. By analyzing the code, we find that there are dependencies between the input data elements: As shown in Figure 7(a), calculating element x is related to the 4 neighbors which are marked in red. The input elements are read-only, so we can eliminate the relationship by redundantly transferring boundary elements (Figure 7(b)). We first divide the total elements into four blocks, corresponding to four tasks (in blue). Then, we additionally transfer the related boundary elements (in red) when dealing with each data block. More False Dependent applications are shown in Table 2. True Dependent The third category of overlappable applications is similar to the second one in that there exist data dependencies between tasks. The difference is that the dependency is true (i.e., RAW ). This is complicated for programmers not only because there is a dependence between the input data elements, but because they need to update input data in the process of calculation. Thus, the output elements depend on the updated input data, and we must control the order of calculation. The key for this pattern is to discover concurrency while respecting the dependency.

NW, Needleman-Wunsch is a nonlinear global optimization method for DNA sequence alignments. The potential pairs of sequences are organized in a 2D matrix. In the first step, the algorithm fills the matrix from top left to bottom right, step-by-step. The optimum alignment is the pathway through the array with maximum score, where the score is the value of the maximum weighted path ending at that cell. Thus, the value of each data element depends on the values of its northwest-, north-and west-adjacent elements. In the second step, the maximum path is traced backward to deduce the optimal alignment. As shown in Figure 8(a), calculating element x is related with three elements: 'n' (northelement), 'w' (west-element), and 'nw' (northwest-element). We must calculate output elements diagonal by diagonal (in the same color), and the elements on the same diagonal can be executed concurrently. Figure 8(b) shows how we divide the data: we number all blocks from the top-left diagonal to the bottom-right one (the first row and first column are the two DNA sequences, marked in number 0), and then change the storage location to let elements from the same block stored contiguously. Figure 8(c) shows the storage pattern, and the numbers represent the relative location. By controlling the execution in the order of diagonal from top-left to bottom-right, we can respect the dependencies between tasks. Further, the tasks on the same diagonal can run concurrently with multiple streams. Note that the number of streams changes on different diagonals. More True Dependent applications can be found in Table 2.

Experimental Results

In this section, we discuss the performance impact of using multiple streams. We use the CPU-MIC heterogeneous platform detailed in Section 3.2. Due to the limitation in time and space, we port 13 applications from Table 1 with hStreams. As shown in Table 2, these 13 benchmarks are characterized as different categories and thus we use the corresponding approach to stream them. Figure 9 shows the overall performance comparison. We see that using multiple streams outperforms using a single stream, with a performance improvement of 8%-90%. In particular, for nn, FastWalshTransform, ConvolutionFFT2D, and nw, the improvement is around 85%, 39%, 38%, and 52%, respectively. However, for applications such as lavaMD, we cannot obtain the expected performance improvement with multiple streams, which will be discussed in the following. Also, we notice that the performance increase of using multiple streams varies over benchmarks and datasets. This is due to the differences in data transfer ratio (R): a larger R leads to a greater performance improvement. For example, for ConvolutionSeparable and Transpose, the average performance improvement is 45% and 11%, with R being 19% and 14%, respectively. Further, when selecting two datasets (400M and 64M) for Transpose, we can achieve a performance increase of 14% and 8%, with R being 20% and 10%, respectively.

For the False Dependent applications, if the extra overhead of transferring boundary elements is nonnegligible, code streaming is not beneficial. For FWT, one element is related to 254 elements which is far less than the subtask data size of 1048576. Therefore, although having to transfer extra boundary values, the overall streaming performance impact is positive. However, when the boundary elements are almost equal to the subtask size, the overhead introduced by boundary transmission can not be ignored. LavaMD calculates particle potential and relocation due to mutual forces between particles within a large 3D space. In the experiment, one element for lavaMD depends on 222 elements, in which 111 elements are lying before the target element and the other half behind. The task data size is 250, which is close to the boundary element number. Thus, we cannot get the expected performance improvement, and the experimental results confirm our conclusion. Specifically, when the task is of 250 and remains unchanged, for single stream, the H2D and KEX time is 0.3476s and 0.3380s, respectively. When using multiple streams, the overall execution time is 0.7242s. Therefore, it is not beneficial to stream the overlappable applications like lavaMD.

Conclusion

In this paper, we summarize a systematic approach to facilitate programmers to determine whether the application is required and worthwhile to use streaming mechanism, and how to stream the code. (1) obtaining the ratio R: run the codes in stage-by-stage manner, record the H2D and KEX time, and calculate R;

(2) judging whether the application is overlappable; (3) streaming the codes by either eliminating or respecting data dependency. Our experimental results on 13 streamed benchmarks show a performance improvement of upto 90%.

The process of analyzing whether a code is streamable and transforming the code is manually performed. Thus, we plan to develop a compiler analysis and tuning framework to automate this effort. Based on the streamed code, we will further investigate how to get optimal performance by setting a proper task and/or resource granularity. Ultimately, we plan to autotune these parameters leveraging machine learning techniques. Also, we want to investigate the streaming mechanism on more heterogeneous platforms, other than the CPU-MIC one.

Fig. 1 .

 1 Fig. 1. The CDF curve for data transfers between the host and the accelerator.

Fig. 2 .

 2 Fig. 2. R changes over datasets for lbm and FDTD3d.

Fig. 3 .

 3 Fig. 3. R changes over code variants of NVIDIA Reduction.

Fig. 4 .

 4 Fig. 4. R changes over platforms of Rodinia nn.

Fig. 5 .

 5 Fig. 5. The dependent relationship between H2D and KEX (The number in the parenthesis represents stages from different tasks).

Fig. 6 .

 6 Fig. 6. Nearest Neighbor Data Partition (16 elements and 4 groups).

  (a) Input elements dependencies. (b) Data Partition

Fig. 7 .

 7 Fig. 7. Task dependency and data partition for FWT

Fig. 8 .

 8 Fig. 8. NW input elements dependencies and how to partition.

Fig. 9 .

 9 Fig. 9. A performance comparison between single stream and multiple streams. For each application, we employ different configuration, corresponding to different data size. Note that ps, hg, cFFT and fwt represents PrefixSum, Histogram, ConvolutionFFT2D and FastWalshTransform, respectively.

Table 1 .

 1 Applications, Inputs and Configurations

	Suite	Applications		Input			Applications	Input
		backprop	10 × {2 16	, 2 17	, 2 18	, 2 19	, 2 20 }	bfs	graph{512K, 1M, 2M, 4M, 8M}
		b+tree	Kernel1, Kernel2	cfd	0.97K, 193K, 0.2M
	Rodinia (18)	dwt2d,gaussian, lud hearwall, lavaMD, leukocyte	2 10 10, 20, 30, 40, 50 , 2 11 , 2 12 , 2 13 , 2 14	myocyte, srad hotspot	100, 200, 300, 400, 500 2 9 , 2 10 , 2 11 , 2 12 , 2 13
		kmeans	{1, 3, 10, 30, 100} × 100000	nn, nw	2 10	, 2 11	, 2 12	, 2 13	, 2 14
		pathfinder	({1, 2, 4} × 10 5	, {100, 200, 400})	streamcluster	100 × {2 10	, 2 11	, 2 12	, 2 13	, 2 14 }
	Parboil (9)	spmv mri-gridding tpacf sgemm lbm	small, medium, large small small, medium, large small, medium short, long	stencil cutcp bfs mri-q	small, default small, large 1M, NY, SF, UT small, large
	NVIDIA SDK (17)	BlackScholes DCT8x8 DXTCompression Histogram MatVecMul Reduction Transpose VectorAdd	10 6 × {4, 8, 12, 16, 20} 2 10 × {1, 2, 3, 4, 8} lena 1, 2, 3, 4, 5 256, 128, 64, 32, 16 2 10 × 10 3 × {1, 2, 3, 4, 8} 2 10 × {1, 2, 3, 4, 8} 2 10 × {1, 2, 4, 8, 16}	ConvolutionSeparable DotProduct FDTD3d MatrixMul QuansiRandomGenerator Reduction-2 Tridiagonal FastWalshTransform ConvolutionFFT2D	2 10 × {1, 2, 3, 4, 8} 2 10 × 10 3 × {1, 2, 3, 4, 8} 10, 20,30, 40, 50 6, 7, 8, 9, 10 2 10 × 10 3 × {1, 2, 3, 4, 8} 2 10 × 10 3 × {1, 2, 3, 4, 8} 32, 64, 128, 256, 512 8M 62500k
		BinomialOption	2 10 × {1, 2, 4, 8, 16}	BitonicSort	2 20 × {1, 2, 4, 8, 16}
		BoxFilter	BoxFilter Input		DwtHaar1D	2 10 × 10 3 × {1, 2, 3, 4, 8}
	AMD SDK (12)	FloydWarshall RadixSort	2 10 × {1, 2, 3, 4, 5} 2 12 × {12, 13, 14, 15, 16}	MonteCarloAsian RecursiveGaussian	2 10 × {1, 2, 3, 4, 5} default
		ScanLargeArrays	2 10 × {1, 2, 4, 8, 16}	StringSearch	1, 2, 3, 4, 5
		URNG	1, 2, 3, 4, 5		PrefixSum	1024k

Table 2 .

 2 Application Categorization.

		Nonstreamable		Streamable
		SYNC	Iterative	Independent	False-dependent True-dependent
	Rodinia	backprop, bfs, b+tree, Kmeans, streamcluster	hotspot, pathfinder	backprop, dwt2d, nn, srad, streamcluster	lavaMD, leukocyte	gaussian, lud nw
		spmv,
	Parboil	tpacf, bfs,	mri-gridding, cutcp	sgemm	stencil, lbm
		mri-q
				BlackScholes, DCT8x8,
	NVIDIA SDK Reduction-2,	FDTD3d, DXTCompression	DotProduct, Histogram, MatrixMul, MatVecMul, QuansirandomGenerator, Reduction, Transpose,	ConvolutionSeparable FastWalshTransform ConvolutionFFT2D
				Tridiagonal, VectorAdd
				BinomialOption,
			BitonicSort,	MonteCarloAsian,	BoxFilter,
	AMD SDK		FloydWarshall,	RecursiveGaussian,	DwtHaar1D,
			RadixSort	ScanLargeArrays,	StringSearch
				URNG, PrefixSum

In the context, the streaming mechanism is synonymous with multiple streams, and thus we refer the streamed code as code with multiple streams.

Note that the only difference lies in devices (Intel Xeon

31SP Phi versus NVIDIA K80 GPU) and all the other configurations are the same.

Acknowledgment

We would like to thank the reviewers for their constructive comments. This work was partially funded by the National Natural Science Foundation of China under Grant No.61402488, No.61502514 and No.61602501, the National High-tech R&D Program of China (863 Program) under Grant No. 2015AA01A301, the National Research Fundation for the Doctoral Program of Higher Education of China (RFDP) under Grant No. 20134307120035 and No. 20134307120031.