Marc Tchiboukdjian
email: marc.tchiboukdjian@imag.fr

Vincent Danjean
email: vincent.danjean@imag.fr

Bruno Raffin
email: bruno.raffin@imag.fr

Thème

Binary Mesh Partitioning for Cache-Efficient Processing

Keywords: Cache-aware, cache-oblivious, mesh layouts, data locality, unstructured mesh, isosurface extraction

One important bottleneck when visualizing large data sets is the data transfer between processor and memory. Cache-aware (CA) and cache-oblivious (CO) algorithms take into consideration the memory hierarchy to design cache efficient algorithms. CO approaches have the advantage to adapt to unknown and varying memory hierarchies. Recent CA and CO algorithms developed for 3D mesh layouts significantly improve performance of previous approaches, but lack of theoretical performance guarantees. We present in this report a O(N log N) algorithm to compute CO layout for unstructured meshes. We prove that a coherent traversal of a N-size mesh in dimension d will induce less than N/B + O(N/M 1/d ) cache-misses where B and M are the block size and the cache size. Experiments show that our layout computation is faster and significantly less memory consuming than for the best known CO algorithm. Performance is comparable to this algorithm for classical visualization algorithm access patterns, or better if the access pattern is adapted to the binary mesh partitioning produced by the algorithm. We also show that cache oblivious approaches lead to significant performance increases on recent GPU architectures.

Partitionnement Binaire de Maillage pour un Traitement Efficace en Cache Résumé : Les transferts de données sont le principal goulot d'étranglement lors de la visualisation de gros jeux de données. Les techniques cache-aware (CA) et cacheoblivious (CO) modélisent la hiérarchie mémoire pour concevoir des algorithms efficaces en cache. De plus, le modèle CO permet de s'adapter à la hiérarchie mémoire sans en connaître les paramètres. Les algorithmes CA et CO développés récemment pour la réorganisation de maillage 3D améliorent significativement les performances des approches précédentes mais manquent de garanties théoriques. Nous présentons dans ce rapport un algorithme de réorganisation de maillages non structurés en temps O(N log N). Nous garantissons que la traversée cohérente d'un maillage de taille N en dimension d ne cause pas plus de N/B + O(N/M 1/d ) défauts de cache avec B la taille d'une ligne de cache et M la taille du cache. Les expériences montrent que notre algorithme de réorganisation de maillage est plus rapide et consomme beaucoup moins de mémoire que le meilleur algorithme CO connu. Les performances du maillage obtenu sont comparables pour les filtres de visualisation standards mais meilleures si les schémas d'accès sont adaptés à la découpe récursive produite par notre algorithme. Nous montrons également une importante amélioration des performances sur les architectures GPU récentes.

Mots-clés : localité des données, maillage non structuré, extraction d'isosurface.

Introduction

Combining adequately data layout and access patterns can significantly improve performance for many memory intensive applications. As classical processor architectures cache adjacent data blocks, data accessed consecutively should be stored nearby in memory to reduce cache-misses. Enforcing locality is also relevant for some SIMD or vector processing units where parallel accesses require fewer clock cycles when the target data are close in memory (nvidia GPUs [START_REF] Ryoo | Optimization principles and application performance evaluation of a multithreaded GPU using CUDA[END_REF] or Intel Larabee [START_REF] Seiler | Larrabee: a many-core x86 architecture for visual computing[END_REF] for instance). We can expect locality of data access to be even more critical for emerging manycore architectures that show complex memory hierarchies where cores share cache and memory bandwidth.

Many visualization applications rely on read-only and memory intensive algorithms with coherent access patterns usually based on spatial locality. Space filling curves, like the Z curve, are commonly used for regular data structures [START_REF] Pascucci | Global Static Indexing for Real-Time Exploration of Very Large Regular Grids[END_REF]. They provide a cacheefficient layout for access patterns showing a strong spatial locality. For irregular data structures, computing cache-efficient layouts is significantly more difficult.

We can distinguish two classes of cache-efficient algorithms: Cache-Aware (CA) and Cache-Oblivious (CO) algorithms. CA algorithms are based on the externalmemory (EM) model [START_REF] Aggarwal | The input/output complexity of sorting and related problems[END_REF]. The memory hierarchy consists of two levels, a main memory of size M called cache and an infinite size secondary memory. Data is transferred between these two levels in blocks of B consecutive elements. CA algorithms can be very efficient but require the layouts to be recomputed for each memory architecture. It makes it difficult to efficiently share the same layout between heterogeneous processing units mixing CPUs and GPUs for instance. CO approaches [START_REF] Frigo | Cache-Oblivious Algorithms[END_REF] intend to overcome this limitation by proposing layouts that are independent from the cache and block size M and B (Fig. 1). The Z curve is an example of a CO layout (Fig. 2). For irregular data structures, the most significant and recent work is probably the CO mesh layout proposed by Yoon et Al. [START_REF] Yoon | Cache-oblivious mesh layouts[END_REF] (OpenCCL algorithm). In comparaison to other layouts, experiments show speedups ranging from 2 for in-core computations, up to 20 for out-of-core computations. However this algorithm is based on heuristics, without theoretical performance guarantee, neither on the layout computation complexity nor the quality of the resulting layout.

In this report we introduce a new CO layout algorithm for irregular meshes with a theoretical performance guarantee. It relies on a recursive mesh partitioning using a specific BSP (Binary Space Partitioning) algorithm introduced by Miller et al. [START_REF] Miller | Geometric Separators for Finite-Element Meshes[END_REF].

Figure 2: Good layouts can significantly reduce the number of block transfers. On the left, 75% of the data must be loaded to access the queried slice (each line corresponds to a cache line), while the CO layout used on the right (Z curve) enables to reduce this amount to only 25% of the data (each block fits into a cache line). This algorithm cuts the mesh guaranteeing a good tradeoff between minimizing the number of cut elements and having two partitions of close size. When applied recursively it ensures that spatially close and strongly connected data tend to be partitioned deeper in the BSP tree. The CO layout is obtained by storing the data linearly in memory from the first leaf of the BSP tree to the last one. The data loaded in a cache block are thus contiguous leaves of the BSP tree. It is cache oblivious as to any block and cache size correspond a BSP tree depth level ensuring a strong locality and connectivity.

This CO layout algorithm shows several benefits. The layout computation has a O(N log N) complexity. It also guarantees that a coherent traversal of an N-size mesh in dimension d induces less than N/B + O(N/M 1/d ) cache-misses where B and M are the block and cache size. Experiments show the layout computation is about two to three times faster than for the OpenCCL algorithm while requiring significantly less memory (from 5 to 35 times measured in our experiments). We are comparable with the OpenCCL algorithm for classical visualization algorithm access patterns. But experiments reveal that adapting the access pattern to the BSP tree can bring significant additional performance improvements (about 12% for in-core computations).

We also show that CO layouts can lead to significant performance improvements on recent NVIDIA GPUs (1.2 to 2.7 speedups), even if no cache mechanism is involved. As our algorithm enforces data locality, access to the mesh are faster due to coalesced data access.

Related work is discussed in section 2. The algorithm is presented and analyzed in section 3 and its implementation discussed in section 4. Then we present experimental results in section 5.

INRIA Figure 3: Visual illustration of different layouts for the torso mesh. Successive cells in memory are colored from blue to red. From left to right, the original, geometric (sorted by x,y and z coordinates), OpenCCL (cache-coherent layout from [START_REF] Yoon | Cache-oblivious mesh layouts[END_REF]) and FastCOL (our approach) layouts. For spatially close triangles, color discrepancy decreases from the left to right layouts. It denotes an improved memory locality, less likely to generate cache-misses for spatially coherent access patterns.

2 Related Work

Cache-Efficient Algorithms

Today, many algorithms have their CA or CO versions [START_REF]Algorithms for Memory Hierarchies[END_REF] where computations and data are reordered for an efficient cache use. A widely used technique is blocking or tiling: elements are mapped in memory and accessed by blocks of size B to fit in a cache line. For instance, regular search trees are made CA by grouping B keys in a single node. Such tree is called a B-tree. Another example is matrix multiplication. Instead of rows or columns, the ATLAS library [START_REF] Whaley | Minimizing development and maintenance costs in supporting persistently optimized BLAS[END_REF] traverses the matrix by blocks such that all involved blocks for a partial computation fit in the cache. It is often possible to obtain the same result while being oblivious to the block size.

For example, by carefully storing a binary tree in memory with the vam Emde Boas layout [START_REF]Algorithms for Memory Hierarchies[END_REF], a search can match the I/O bound of the CA B-tree. In this layout, the tree is divided at the middle of its height into a top tree and several bottom trees. The same layout is recursively applied to each of these trees, which are then stored sequentially in memory. The same recursive blocking technique is applied within the divide and conquer matrix multiplication. Indeed, this is a CO algorithm [START_REF]Algorithms for Memory Hierarchies[END_REF] with the same theoretical complexity as its CA counterpart.

Another CO alternative to blocking is the use of space filling curves. For example, it works perfectly with matrix multiplication [START_REF] Bader | Cache oblivious matrix multiplication using an element ordering based on a Peano curve[END_REF] or regular meshes [START_REF] Pascucci | Global Static Indexing for Real-Time Exploration of Very Large Regular Grids[END_REF]. CO algorithms for regular structures are not always as efficient as their CA counterpart. The access pattern to the CO layout is more complex leading to a significant overhead impairing performance. For instance, CO matrix multiplication is not competitive with the CA version [START_REF] Yotov | An experimental comparison of cache-oblivious and cache-conscious programs[END_REF]. We do not face this problem here as an unstructured mesh has already a complex access pattern.

Mesh Layouts

The problem of reordering mesh elements for efficient cache use was first encountered when a vertex cache has been introduced in graphic cards. In order to maximize the efficiency of the hardware vertex cache, triangles needed to be reordered before being sent to the graphic card. The algorithm developed by [START_REF] Hoppe | Optimization of mesh locality for transparent vertex caching[END_REF] reorders triangles to form triangle strips. They assume the cache has a FIFO policy and the cache size is known to the algorithm. New algorithms that works for all cache sizes has been introduced in [START_REF] Bogomjakov | Universal rendering sequences for transparent vertex caching of progressive meshes[END_REF]. However, as they target graphic cards, they only reorder the mesh cells and not the points. Moreover, their consider the graphic card cache model (no cache line, independent vertices fetching, etc.) which is very different from the CPU cache models. To be efficient, the application must access the mesh in the exact order given by the cell layout (especially for triangle strips). Finally, work in this area mostly dealt with surface meshes.

Processing sequences [START_REF] Isenburg | Streaming meshes. Visualization[END_REF] reorder points and cells of the mesh, but this approach focuses on streaming computations. The goal is to minimize the maximum amount of memory used during the computation. The application should again follow the mesh layout.

OpenCCL [START_REF]OpenCCL: Cache-Coherent Layouts[END_REF] presented in [START_REF] Yoon | Cache-oblivious mesh layouts[END_REF] casts the mesh layout problem as a graph optimization problem. To describe the access pattern of the application using the mesh, the user must provide a graph where vertices represent data and edges link data that are likely to be accessed in sequence at runtime. A good mesh layout is a permutation of the graph vertices that results in a more efficient layout of the mesh in memory. They developed a local metric to decide if a swap of some vertices improves the layout. They optimize this measure thanks to a multilevel optimization scheme. However their algorithm is based on a heuristic that does not give the global optimum. They do not provide a bound on the quality of the layout, i.e. the resulting number of cache-misses. Our algorithm FastCOL gives an upper bound on the number of cache-misses incurred by the application at runtime. This bound is closely related to the CA and CO metrics introduced in [START_REF] Yoon | Mesh Layouts for Block-Based Caches[END_REF].

Aforementioned approaches mainly focused on optimizing mesh layouts when the application accesses the mesh without the help of any additional data structure. That is, the application only traverses the mesh with the help of the cells and points arrays or with the cell-to-points or point-to-cells pointers of the mesh. Another approach [START_REF] Yoon | Cache-Efficient Layouts of Bounding Volume Hierarchies[END_REF] optimizes the layout for applications accessing the mesh through bounding volume hierarchies (BVH) trees. To generate an efficient layout, they use the OpenCCL algorithm and provide two kind of links in the access graph: links representing spatial locality and links representing parent-child locality in the BVH to optimize. Our algorithm also handles these two kinds of locality. During the layout computation, we build a BSP tree that is used to reorder the mesh. This tree is tailored to efficiently use our mesh layout. In opposite to the approach in [START_REF] Yoon | Cache-Efficient Layouts of Bounding Volume Hierarchies[END_REF] where the layout algorithm takes a mesh and a BVH tree as input to produce a layout, we only take the mesh as input and produce both a layout and a BSP tree consistent with this layout. This BSP tree can be used as an acceleration structure, for isosurface extraction for instance.

Isosurface Extraction

The marching tetrahedron algorithm can be accelerated with various data structures allowing to efficiently search for the cells intersected by the isosurface. The first data structure was the min-max tree [START_REF] Wilhelms | Octrees for faster isosurface generation[END_REF]. An octree where each node stores the minimum and maximum values of its subtree permits to quickly discard parts of the mesh that do not contain any intersected cell. The search is thus improved from O(n) to O(k + k log n/k) where n is the number of cell and k the size of the isosurface (usually k ≪ n). If the scalar field is spatially coherent, the performance is actually improved over the theoretical bound.

INRIA

An optimal data structure for this problem is the interval tree storing for each cell c the interval whose extremes are the minimum and maximum value of the points of c [START_REF] Cignoni | Optimal isosurface extraction from irregular volume data[END_REF]. The query time is improved to O(log n + k) whatever the spatial repartition of the scalar field is. The interval tree has been made I/O-efficient allowing a query with complexity O(log B n + k/B), which is optimal [START_REF] Chiang | I/O optimal isosurface extraction[END_REF]. However this approach is not space-efficient since vertex information is duplicated many times. The 2-level indexing scheme based on the meta-cells technique introduced in [START_REF] Chiang | Interactive out-of-core isosurface extraction[END_REF][START_REF] Chiang | External memory techniques for isosurface extraction in scientific visualization[END_REF] is both practical and space-efficient as there is no duplicated information. Spatially close cells are grouped into meta-cells, which are then used in the I/O-efficient interval tree.

The approach we developed with the consistent BSP tree is a CO alternative to the meta-cells technique but we use the min-max tree instead of the interval tree which may not be as efficient on a scalar field with high spatial variations.

Binary Mesh Partitioning Recursive Layout

The goal is to define CO mesh layouts for spatially coherent access patterns, i.e. when elements accessed consecutively are spatially close. Such patterns encompass a large range of visualization algorithms.

These access patterns are modeled by a class of graphs called overlap graphs. There exists an optimal separator for overlap graphs, which, when applied recursively, provides a CO mesh layout.

Overlap Graphs

We model the mesh by a graph G = (V, E) where vertices represent elements of the mesh (points or cells), and edges link elements that are likely to be accessed consecutively. We also associate to each vertex v i a coordinate p i in R d , usually the coordinate of the corresponding element of the mesh. These graphs can model a large range of access patterns, even ones with a weak spatial coherency where edges connect distant elements. To be able to build efficient CO layouts with a provable quality, we restrict to the class of graphs modeling spatially coherent access patterns, i.e. where edges connect spatially close elements. Such graphs are called overlap graphs [START_REF] Miller | Geometric Separators for Finite-Element Meshes[END_REF].

A graph is α-overlap if it is possible to associate to each vertex v i a ball B i centered at p i such that each pair of balls intersect in at most one point. The radii of the balls can be freely adjusted allowing the modeling of meshes with non uniform cell sizes. Additionally edges can connect two vertices only if expanding the smaller of their two balls by a factor of α make them intersect.

Meshes are often composed of elements that are well shaped in some sense, such as having a bounded aspect ratio or angles that are not too small or too large. Such geometric features ensure that edges meet the overlap graph constraint. Every mesh with bounded aspect ratio elements in two or three dimensions is contained in some overlap graph (for a good choice of the parameter α).

Most of the spatially coherent access patterns on meshes are overlap graphs. For instance, the graph where vertices are points of the mesh and two vertices share an edge when they share an edge in a cell is an overlap graph. The one where vertices are cells of the mesh and two vertices share an edge when cells share a face is also an overlap graph.

Geometric Separator Algorithm

Given their geometrical properties, overlap graphs can be partitioned efficiently in two parts of approximately equal size, while minimizing the number of edges cut.

The following randomized algorithm introduced by Miller et al. [START_REF] Miller | Geometric Separators for Finite-Element Meshes[END_REF] computes in linear time and with a high probability an optimal geometric separator. It starts by randomly sampling a constant number of points from the input mesh and project them onto the surface of the unit sphere in R d+1 (Algo. 1). Then it finds a centerpoint of this random sample in linear time relative to the sample size. A point is a centerpoint if every hyperplane passing through it divides the sample set approximately evenly, at most in the ratio d + 1 : 1. With good probability, this centerpoint is a centerpoint of the original set of points [START_REF] Clarkson | Approximating center points with iterated radon points[END_REF]. Finally we randomly choose a hyperplane through the centerpoint. Repeating this process and selecting the separator cutting the smallest number of edges gives a small separator with high probability.

Algorithm 1: Geometric separator algorithm

Input: The most time consuming part of the algorithm is the quality evaluation of the separator (Alg. 1 line 8) as other operations involve only a small number of points.

Graph G = (Vertices V, Edges E) Output: A separator φ repeat n c times 1 V s ← sample of (d + 3) 4 points of V 2 V p ← project V s to the unit sphere in R d+1 3 c ← centerpoint of V p 4 (u,
The quality of the obtained separator is guaranteed by the following theorem.

Theorem 1 (Geometric separator [START_REF] Miller | Geometric Separators for Finite-Element Meshes[END_REF]) Let G be an n-vertex α-overlap graph in d dimensions. With high probability, the previous algorithm (Alg.

1) partitions the vertices of G into two sets A and B such that |A|, |B| ≤ d+1 d+2 n and the number of edges between A and B is O αn

1-1/d .
Such a separator is asymptotically optimal for the class of overlap graphs. Indeed we cannot find a smaller separator for a regular d dimensional grid [START_REF] Miller | Geometric Separators for Finite-Element Meshes[END_REF].

Mesh Layout Algorithm

The recursive application of the separator gives a BSP tree where each node is a separator. Leaves of this tree correspond to small subparts of the mesh that are stored consecutively to provide the layout (Algo. 2). As the geometric separator has linear complexity, our layout algorithm has complexity

INRIA

W (N) = max 1/2≤λ ≤δ [W (λ N) +W ((1 -λ )N)] + O(N) = O (N log N)
where δ = d+1 d+2 . The only requirement to obtain the claimed complexity is to have a point sampler of linear complexity and an iterator on edges of linear complexity too.

Layout Quality

In the following theorem, we exhibit a bound on the quality of the layout generated by algorithm 2.

Theorem 2 (Layout quality) Let G be a N-vertex α-overlap graph in d dimensions representing the access pattern of a d-dimensional N-size mesh. The layout produced by algorithm 2 ensures that a traversal of the mesh respecting the access pattern of G induces less than N/B + O(N/M 1/d ) cache misses where B and M are the block and cache size.

Let T the BSP tree obtained by recursively applying the geometric separator. Let T m ⊂ T a subtree of the BSP tree with the same root but whose leaves are nodes x of T verifying size( f ather(x)) > m and size(x) ≤ m. We first compute k m , the number of edges cut by all the separators in T m . We show that k m = O N m 1/d . Let K(r) be the maximum number of cut edges in a subtree T ′ m of T m rooted at a subgraph of size r. If r ≤ m then T ′ m is just a leaf and K(r) = 0. If r ≥ m, we count the edges cut in the left and right children and the edges cut by the separator of the root of

T ′ m : K(r) ≤ max 1/2≤λ ≤δ [K(λ r) + K((1 -λ )r)] + cαr 1-1/d
where c is a constant and δ = d+1 d+2 (Th. 1). By induction, we can prove that

K(r) ≤ c ′ r m 1/d -r 1-1/d as long as c ′ ≥ αc 2 1/d -1 .
And thus

k m = K(N) = O N m 1/d
. We now model an application using the mesh as a function f to be applied to all elements of the mesh. The function f is in agreement with the access graph if, to process element i, only the neighbors of i in the graph need to be accessed. We also make the following assumptions:

• all elements in the mesh are processed exactly once;

(a)

• elements are accessed one leaf of T m after the other (with m ≤ M).

(b)

The order between leaves and the order inside each leaf can be freely chosen. As each element of the mesh is processed at least once, the number of compulsory cache misses is at least N B . This is a lower bound on the number of cache-misses of any application that need to process each element of the mesh. Following edges that link an element in a leaf l and an element outside leaf l causes O(1) extra cache-misses (bringing the corresponding block in cache can evicts a block corresponding to leaf l that might be needed later). These extra cache-misses for all leaves sum up to O(k m ) misses. After the whole mesh has been processed, the number of cache-misses is thus N B + O(k m ). Combining this result with the previous one we obtain N B + O N m 1/d . If elements are processed in the order given by the layout, we can take m = M and we obtain the claimed bound.

At this point we cannot directly compare this algorithm with OpenCCL. OpenCCL is based on a meta-heuristic and no upper bound on the quality of the resulting layout is given.

Discussion on the Access Graph Model

The access graph modeling the application access pattern is not exact. First, this graph just gives local information on which data is accessed but no global information on how the graph is traversed. Next, real life applications do not rely only on intrinsic mesh characteristics such as topology or geometry when accessing the mesh but sometimes on the layout itself. For example, the connectivity filter of VTK only uses the mesh topology, but a marching tetrahedron algorithm processes mesh cells in the order of the layout.

With our layout, an application still needs to respect some properties (assumptions (a) and (b) in the previous section) while traversing the access graph. We believe that we could obtain the same performance guarantee slackening these two assumptions to rely only on the characteristics of the mesh itself. We are however not able to prove it yet.

Implementation

Choosing the Access Graph

The algorithm described in section 3 can be applied to any access pattern as long as the corresponding graph is an overlap graph (actually the algorithm still works if it is not the case but the bound on cache-misses does not hold). However it is not practical to generate a new layout for each application. For instance to compute a volume rendering by ray casting of the mesh, one might want to optimize the mesh layout according to the rays direction. Both our algorithm and OpenCCL are two slow to generate a layout before each image generation. In practice it is better to compute only once a layout that will be efficient in general. We choose in the implementation to only consider the INRIA graph where vertices are points of the mesh and edges link two vertices sharing a cell. Following on our volume rendering example, this layout will be reasonably good for any rays direction. One ray traversing c cells of the mesh induces c/B 1/3 cache-misses while a layout optimized for this specific direction may induce only c/B cache-misses (but as bad as 1 cache-miss per cell for an orthogonal direction). In this specific case, packing rays should also improve performance of the more general layout to c/B.

Layout Computation

We implemented the geometric separator algorithm in C++. We first randomly generate all the n h n c separators. Half of them are hyperplanes and the other half are lines. We then traverse all the cells of the mesh and for each of them we check that its points are on the same side of the separator. If not, the cell is cut by the separator and we increment the cut size by 1. Using cells instead of edges to select the best separator produces a very close result and allows us not to compute the edges of the graph, which can be computationally expensive. All separators are checked against a cell before going to the next one. This allows us to dereference each cell index only once for the entire separator computation.

To keep the memory usage low, we do not project all the points before evaluating a separator but project them on the fly. This induces duplicate computation as a point is used in several cells but keep memory overhead close to zero. That way we do not need to store an entire copy of the points in memory.

Once we found the best separator, points of the mesh are reordered according to this separator. All points laying to the left of the separator are moved to the left part of the array and points laying to the right are moved to the right part of the array. The same partitioning is done on cells. When a cell is cut by the separator we choose a side according to the center of gravity of the cell. We then recurse on the left and right mesh generated. This algorithm is very similar to quicksort and could be efficiently parallelized.

We stop when a submesh has a size lower than 8. We choose n c = 2 and n h = 30 for the experiments (Alg. 1). As the randomized centerpoint algorithm is quite good we can keep n c low. During our experiments we noticed that substantial changes of all these parameters does not impact very much the quality of the generated layout. The expensive part of the quality evaluation is the rotation and scaling of each center point.

Cells Layout

A mesh layout tries to optimize both points and cells ordering. As points and cells are usually accessed in a similar way, a consistent ordering for points and cells is better (for instance, in an isosurface computation points defining each cell will often be accessed right after the cell itself). Our geometric approach is naturally good as the same geometric separator can be applied for both points and cells. A separator cutting few edges for the points graph also cut few edges for the cells graph. It is not possible to do the same with OpenCCL for example as their separators are combinatorial and not geometric. It is often less efficient to compute both points and cells layouts independently. In this case, computation time is longer and runtime efficiency lower. For OpenCCL, the cell layout takes 3.2 more time than the points layout on the bucky ball mesh. An usual trick is to compute the cells layout using the order given by the minimal index of points in the cell. Consistency of points and cells layout can futher improve performance. On large meshes the consistent layout for points and cells with the BSP tree is up to 10% faster than the min-vertex layout applied to FastCOL on isosurface extraction. Moreover min-vertex applied to OpenCCL is up to 20% faster than OpenCCL applied to both points and cells.

Consistent BSP Tree

We use the BSP tree defining the partitioning of the mesh as a min-max tree. At each node of the BSP tree is stored the minimum and maximum value of the scalar field in the corresponding region of the mesh. A region that do not contain any cell intersected by the isosurface can be quickly discarded.

A nice property of this BSP-tree is that each region corresponds to a small part of the mesh stored sequentially in memory (see fig. 4). When traversing the BSP-tree in prefix order and examining the mesh cells that might contain a part of the isosurface, mesh cells are accessed sequentially. The sequence of cells can jump part of the mesh but never goes back. This leads to a traversal of the mesh inducing less cache-misses (see section 5.2.2).

Experiments

In our experiments, we compared the initial layout, the geometric layout, the one computed with OpenCCL, and the one computed with our FastCOL algorithm by running ten classical filters and measuring the execution time and the cache-misses. In this part, we describe the experiments performed. For sake of conciseness, we present only some representative results. Full results are provided in appendix A. Eventually, we show that these results can be correlated with the property that our algorithm optimizes (the locality of the vertices and edges in the layout).

Description of the Experiments

The experiments were conduced on three kinds of configurations: two generic processors (AMD Opteron875 @ 2.2Ghz, cache L1 8KB, cache L2 1MB and Intel Core2 E6750 @ 2.66Ghz, cache L1 32KB, cache L2 4MB) and one graphical processor (NVIDIA GTX280 30MP 1GB programmed with cuda 1.3).

INRIA

We took 9 different meshes1 , processed to generate several instances of various sizes. For the original mesh, we subdivide some cells by adding a new vertex. It leads to a set of 50 meshes that can be divided by their size into 4 groups: 5 meshes of about 100 k cells, 10 meshes of about 1 M cells, 17 meshes of about 10 M cells, and 18 meshes of about 50 M cells.

Ten filters have been tested on each layout and are presented below. Six of them are algorithms implemented directly within VTK [START_REF] Schroeder | The Visualization Toolkit, An Object-Oriented Approach To 3D Graphics[END_REF], two have been manually developed on CPU, and the last two ones has been written with CUDA on GPU.

Gradient The VTK gradient filter computes at each point the gradient of the scalar field of the mesh. Each point p accesses the scalar data of points connected to p by an edge of the mesh. Points are processed in the order given by the point layout.

Connect The VTK connectivity filter applies a breadth first search on the mesh to compute the connected region each cell lies in. Each cell c accesses cells sharing a point with c. Cells are processed in an order depending only on the topology of the mesh.

RC The VTK Bunyk Ray Cast filter computes a volume rendering of the mesh following [START_REF] Bunyk | Simple, Fast, and Robust Ray Casting of Irregular Grids[END_REF]. Each ray traverses the mesh cell by cell.

PT The VTK Projected Tetrahedra filter computes a volume rendering of the mesh following [START_REF] Shirley | A polygonal approximation to direct scalar volume rendering[END_REF]. Tetrahedra are sorted by their centroid according to the viewing direction and then sent to the GPU for projection. Each tetrahedron accesses to its points. Tetrahedra are processed in the order given by the cell layout.

HAVS The VTK HAVS filter computes a volume rendering of the mesh following [START_REF] Callahan | Hardware-assisted visibility sorting for unstructured volume rendering[END_REF]. Data accesses are similar to PT.

VtkIso

The VTK isosurface extraction filter implements the marching tetrahedron algorithm. Each cell accesses to its points. Cells are processed in the order given by the cell layout.

CpuIso and GpuIso Home-made implementations of the marching tetrahedron algorithm. The GPU implementation is developed with CUDA.

CpuTree and GpuTree

The search for cells intersected by the isosurface is accelerated with a min-max tree where the tree is simply a kd-tree. Each cell accesses to its points, like with the regular marching tetrahedron, but cells are now processed in a different order than the one of the cell layout. Also, not all cells are processed. We only measure the time spend in processing the intersected cells and not the traversal of the tree.

The bigger meshes (50 M cells) have not been tested on the volume rendering filters due to the very large execution time of these filters. Moreover, they have not been tested on GPU, due to the insufficient amount of memory available.

Results

In our experiments, we considered two aspects: the computation of the layouts and the effect of the layout on the filter executions.

Layout Algorithms

All layouts have been prepared on a Opteron875 @ 2.2Ghz with 32 GB of memory and 64 GB of swap. The geometric layout is only a coordinate sort by the x, y and z axes, so it is very fast (less than 40 s for the biggest meshes) and not memory consuming. The results presented in the table 1 include the execution time and memory consumption for computing the OpenCCL and FastCOL layouts. Table 1 shows that our FastCOL program is about three times faster than the OpenCCL one. Our FastCOL program also requires far less memory to compute its layout. The bigger meshes with 50 M cells have not been processed with OpenCCL because their computation would have required more than 96 GB of memory.

Filters Performance with respect to Mesh Layouts

For each of the 50 meshes and for each filter, we measured the global time of the experiment. When using a filter on a generic processor, we also measured the number of L1 and L2 cache-misses with the PAPI software [START_REF] Browne | A portable programming interface for performance evaluation on modern processors[END_REF]. When using a filter on the GPU, we measured the number of uncoalesced parallel accesses. A parallel global memory access performed by all threads of a half-warp is coalesced into a single memory transaction as soon as the words accessed lie in the same segment of size equal to 128 bytes for 32-bit or 64-bit words.

For each experiment (architecture, graph and algorithm fixed), the measured time, the number of cache-misses and the number of uncoalesced accesses are very stable.

In tables 2 and 3, we use the initial layout as the reference and we compute the ratio with this one for the three other layouts. Then, we compute the means of these ratio for each group of 10 meshes. The "time" columns show the speed-up for the considered layout and the "L2" or "Unco." columns show the ratio of saved L2 cache-misses or uncoalesced memory accesses. In all cases, higher values are better.

Table 2 compares the initial layout versus the geometric, OpenCCL and FastCOL layouts. Table 3 compares the initial layout versus the OpenCCL layout and two variants of the FastCOL layout. The first one uses an external min-max tree while the second one reuses the BSP tree the layout is based on as described in 4.4.

Discussion and Interpretation

Our results clearly show that mesh layouts can significantly influence filter performance. Results are consistent: more variations between layouts can be observed with bigger meshes where cache effects are predictably more important. Indeed, with smaller meshes, a bigger part of the meshes can be loaded in the cache, whatever the layout is. We can observe that OpenCCL and FastCOL layout nearly always lead to a speedup greater than 1. This means that cache-oblivious layouts are an efficient approach to globally improve filter performance. Results for OpenCCL and FastCOL are similar. However, the layout computation time is about 3 times smaller for FastCOL and the memory footprint is far less important. OpenCCL is unable to compute a layout for a 50 M cells mesh with 96 GB of memory and swap, whereas this is where the biggest speed-up is observed with the FastCOL layout.

We can also observe that measured speed-ups are generally smaller with VTK filters than with home-made filters. This clearly appears for the iso-surface filter which is implemented with VTK (VtkIso) and with an home-made code (CpuIso). The VTK implementation shows a maximum speed-up of 1.44 whereas our implementation goes up to 4 (with a smaller global execution time). This is due to the VTK library that is not fully optimized and performs several other computations. For instance, in the VtkIso filter, after the extraction of the isosurface, same points are merged to give a mesh as a result.

As explained previously in this report, we think that speed-up improvements are due to better data locality in memory. We will present here some more evidence of this fact. We call "length of an edge" the memory gap between the two vertices of this edge in the vertex array loaded in memory. If a mesh has smaller edges, more of them will fit in cache and a better performance should be observed. Notice that other analysis can be conduced on similar metrics. For example, instead of considering the length of edges, we can consider the "size of a cell", which would be either the maximum memory gap between all vertices of the cell in the vertex array, or the maximum memory gap between all adjacent cells in the cell array. Figure 5 shows for the 10 M cell torso mesh3 the proportion of edges which length is smaller than the size reported in abscissa. The two graphics are zoomed around the L1 and L2 cache sizes of the tested architectures. We can clearly see on this figure how cache-oblivious layouts (OpenCCL and FastCOL) optimize smaller edge lengths. The original layout appears to be the worst with regards to the edge lengths.

The geometric layout does not particularly optimize smaller edge lengths as opposed to CO layouts, but it exhibits a size for which nearly 100% of the edges fit in cache. Once the size is big enough to contain two entire slices of the mesh in the x direction, all edges will have a size smaller than this one. This has important consequences: the geometric layout will lead to a good performance when this size is smaller than the L2 cache size. Indeed, results show clearly that the geometric layout performs well for small meshes while it is outperformed by the CO layouts for the bigger ones. The other consequence is that the geometric layout is not efficient with regard to the L1 cache. It has indeed been observed (results are detailed omitted). That is why speed-up are generally less important with the geometric layout than with OpenCCL or FastCOL layouts for small meshes.

We also compared our estimation of cache-misses and the number of cache-misses actually observed during our experiments. If we call N the size of a mesh G = (V, E) (in bytes), B the size of a cache line and M the cache size, we estimate the number of cache-misses by:

ExpectedCM ≈ N B + ∑ e∈E ✶ λ e >M
where λ e is the length of the edge e. That is, we count the number of cache-misses for a linear full read of the data arrays and we add one cache-miss per edge whose length is bigger than the cache size M. The theoretical upper bound N B + O (k M ) we give for our FastCOL algorithm in theorem 2 is larger because in our algorithm we count one for each edge that goes from one subtree (of size smaller than M) to another one. It is immediate that all edges within a subtree of size smaller than M have a length smaller than M. But some edges between different subtrees counted as bigger than M in our theoretical bound can in fact be smaller.

In figure 6, we display the correlation between the expected cache-misses for the considered mesh layout and the cache-misses observed with the PAPI software on the two architectures we used. Note that the factor N B has been subtracted for this measure. Otherwise, it would have been difficult to easily compare meshes of different N sizes. The correlation between expected cache-misses and real ones is very high with a calculated r 2 of 0.98. We want to highlight the effect of using the structure built by our algorithm. Indeed, the BSP tree computed by our algorithm can efficiently be reused by the filters that needs such BSP tree. Table 3 illustrates this fact. In this experiment (on CPU and GPU), we compute an isosurface using a min-max tree to quickly reject some parts of the meshes. The two first experiments use a kd-tree with the OpenCCL and FastCOL layouts. The CO layouts lead to a speed-up even if the tree does not partition the meshes like the layouts. However, if in the isosurface algorithm we use the BSP tree computed by our FastCOL algorithm, the efficiency is greatly improved.

Conclusion

We introduced FastCOL, an algorithm relying on the geometric separator from Miller et al. [START_REF] Miller | Geometric Separators for Finite-Element Meshes[END_REF] for computing CO mesh layouts. FastCOL is a O(N log N) algorithm computing layouts with a proven quality. This algorithm requires significantly less computation time and memory than OpenCCL, the best known CO mesh layout algorithm [START_REF] Yoon | Cache-oblivious mesh layouts[END_REF]. Without modifying the visualization algorithms, it can bring significant performance improvements on CPUs where it reduces the number of cache-misses, as well as on GPU architectures where it favors parallel coalesced data accesses. Performances are comparable to OpenCCL and better by more than 10% if the access pattern is adapted to FastCOL's BSP tree.

Developing efficient algorithms for multicore architectures is challenging regarding the complexity of their memory hierarchy and concurrent processing capabilities. Oblivious approaches are interesting as they bring extra performance while reducing the tuning efforts. Our future work will focus on evaluating the benefits of CO layouts on multicores with classical parallel and processor oblivious algorithms.

A Additional Measures

Figure 1 :

 1 Figure 1: The cache-oblivious memory model. Data is transfered by block of B consecutive elements into a cache of size M. Both parameters are unknown to the algorithm.

5 repeat n h times 6 n ← random normal vector 7 φ 8 compute the number of edges cut by φ 9 end 10 end 11 return the best φ 12

 56789101112 r) ← rotation and scaling factor to move c at the origin ← separator defined by (u, r, n)

Algorithm 2 : 1 π 2 return π 3

 2123 Layout algorithmInput: Graph G Output: Permutation of the nodes π T ← complete BSP tree of the graph G ← left to right order of the leaves of T

Figure 4 :

 4 Figure 4: Illustration of the correspondance between mesh regions, BSP tree branches, and data arrays.

  Figure 5: Cumulative distribution function of edge lengths of the torso mesh (10M resolution).

Figure 6 :

 6 Figure 6: Correlation between edge lengths and measured L2 cache-misses on cpuiso. Each point corresponds to a mesh with geometric, OpenCCL or FastCOL layouts.

Table 1 :

 1 Layout computation

	Mesh size	OpenCCL	FastCOL
	#cells	Bytes	Time	Mem. space	Time	Mem. space
	100k 3.7 MB	4.5 s	123 MB	1.2 s	22 MB
	1M	43 MB	54 s	1.24 GB	17 s	81 MB
	10M 370 MB 9 min 24 s 9.96 GB	3 min 50 s 0.56 GB
	50M	1.8 GB	NA	> 96 GB 26 min 44 s 2.72 GB

Table 2 :

 2 Speed-up of Geometric, OpenCCL and FastCOL layouts over the original layout on various visualization algorithms on Core2 E6750 at 2.66Ghz, with 32 kB of L1 cache, and 4 MB of L2 cache.

		Mesh	Geometric	OpenCCL	FastCOL
		size	Time	L2	Time	L2	Time	L2
	Gradient	100k 1.02 1M 1.06 10M 1.07 50M 1.1	1.51 3.53 2.36 1.34	1.01 1.07 1.15	1.49 4.03 8.22	1.02 1.08 1.15 1.36	1.52 3.94 7.81 10.53
	Connect	100k 0.95 1M 0.97 10M 1.09 50M 0.89	0.94 0.95 1.08 0.87	1.12 1.16 1.45	1.17 1.19 1.49	1.11 1.19 1.46 1.66	1.21 1.19 1.49 1.9
	RC	100k 0.98 1M 1.01	1.08 1.07	1.05 1.2	1.4 1.8	1.06 1.2	1.36 1.79
		10M	0.76	0.72	3.28	5.02	3.2	4.89
	PT	100k 1.06 1M 0.91	0.82 0.64	0.93 1.09	1.18 1.51	1.15 1.1	1.18 1.52
		10M	0.97	0.9	1.37	2.66	1.37	2.65
	HAVS	100k 1.02 1M 1.14 10M 1.2	2.04 3.43 1.9	1.01 1.06 1.33	2 4.04 5.96	1.08 1.09 1.32	2 4.03 5.77
	VtkIso	100k 0.99 1M 1.1 10M 1.32	1.04 1.22 1.71	1.04 1.15 1.44	1.06 1.24 1.79	1.04 1.15 1.44	1.09 1.24 1.78
	CpuIso	100k 1.06 1M 1.71 10M 2.28 50M 0.97	1 2.85 5.4 0.79	1.16 2.34 4.08	1.02 2.8 5.78	1.17 2.35 3.99 4.87	1.02 2.78 5.68 6.84
			Time Unco. 2 Time Unco. 2 Time Unco. 2
	GpuIso	100k 0.96 1M 1.26 10M 1.83	1.18 1.04 1.25	1.56 2.2 4.09	3.08 2.59 3.85	1.52 2.11 3.8	2.97 2.38 3.39

2

Uncoalesced global memory access INRIA

Table 3 :

 3 Speed-up isosurface extraction with a kd-tree used as a min-max tree except for FastCOL (bsp) that uses the BSP tree of the mesh layout.

		Mesh	OpenCCL	FastCOL	FastCOL (bsp)
		size	Time	L2	Time	L2	Time	L2
	CpuTree	100k 1.23 1M 1.46 10M 2.37 50M	1.31 1.8 3.14	1.21 1.45 2.31 2.92	1.30 1.74 3.02 3.47	1.37 1.75 2.75 4.55	1.23 1.72 3.06 4.85
				Unco. 2		Unco. 2		Unco. 2
	GpuTree	100k 1.20 1M 1.63 10M 2.50	1.85 1.81 2.14	1.18 1.57 2.34	1.75 1.67 1.86	1.33 1.84 2.79	1.90 1.89 2.14

Table 4 :

 4

			Mesh sizes
	Meshes	#points	#cells	size (MB) size w/ scalar (MB)
	blunt	40,948	222,414	7.72	8.04
	fighter	13,832	70,125	2.46	2.56
	spxr1	18,845	99,593	3.47	3.61
	spxu1	17,431	100,236	3.46	3.59
	spx	2,896	12,936	0.46	0.48
	bucky2	262,144	1,250,235	44.15	46.15
	fighterr1	169,279	1,025,665	35.18	36.47
	fighteru1	174,471	1,057,557	36.27	37.60
	flamme2	246,668	1,429,237	49.26	51.14
	plasma	274,625	1,310,720	46.29	48.38
	post	108,300	616,050	21.28	22.11
	sf2	378,747	2,067,739	71.77	74.66
	spxr2	180,213	1,030,585	35.58	36.95
	spxu2	183,981	1,130,922	38.72	40.13
	torso	168,930	1,082,723	36.91	38.20
	bucky2r1	1,585,333 9,951,469	339.98	352.08
	bucky2u1	1,429,613 9,404,326	319.72	330.63
	fighterr2	1,649,525 10,259,164	350.84	363.42
	fighteru2	1,642,795 10,300,418	351.94	364.48
	flamme2r1 1,564,240 10,039,758	342.19	354.13
	flamme2u1 1,624,652 10,087,446	345.03	357.42
	plasmar1	1,742,157 10,840,277	370.69	383.99
	plasmau1	1,675,932 11,148,401	378.58	391.37
	postr1	1,785,085 10,262,122	354.03	367.65
	postu1	1,647,891 9,510,317	327.95	340.52
	sf1	2,461,694 13,980,162	482.98	501.77
	sf2r1	1,610,554 9,588,705	329.49	341.77
	sf2u1	1,772,252 10,997,790	376.19	389.71
	spxr3	1,671,580 10,126,742	347.30	360.06
	spxu3	1,702,853 10,666,566	364.49	377.48
	torsor1	1,567,838 10,072,449	343.27	355.23
	torsou1	1,547,928 9,822,806	335.20	347.01
	bucky2r2	7,493,319 48,070,324	1638.50	1695.67
	bucky2u2	7,761,809 49,494,141	1688.10	1747.31
	fighterr3	7,638,337 48,193,668	1645.58	1703.86
	fighteru3	8,158,153 51,706,388	1764.68	1826.92
	flamme2r2 8,009,055 51,703,067	1761.17	1822.27
	flamme2u2 8,265,998 52,268,733	1784.31	1847.37
	plasmar2	7,450,645 47,849,247	1630.77	1687.62
	plasmau2	7,792,881 49,661,879	1693.93	1753.38
	postr2	8,209,139 50,520,927	1729.67	1792.30
	postu2	8,088,952 50,293,710	1719.98	1781.70
	sf1r1	8,252,867 50,126,740	1718.64	1781.60
					INRIA

Table 6 :

 6 Build layouts sur Opteron

	Meshes	OpenCCL FastCOL FastCOL vs OpenCCL
	blunt	9.25	3.38	2.74
	fighter	3.37	0.77	4.38
	spxr1	5.17	1.01	5.12
	spxu1	4.40	1.10	4.00
	spx	0.49	0.11	4.45
	bucky2	66.26	17.42	3.80
	fighterr1	42.28	15.00	2.82
	fighteru1	41.75	17.04	2.45
	flamme2	65.13	18.96	3.44
	plasma	68.45	20.72	3.30
	post	26.53	9.24	2.87
	sf2	98.27	30.70	3.20
	spxr2	42.59	16.45	2.59
	spxu2	41.72	15.85	2.63
	torso	45.54	16.76	2.72
	bucky2r1	544.49	200.84	2.71
	bucky2u1	476.38	198.17	2.40
	fighterr2	580.75	238.67	2.43
	fighteru2	587.32	241.17	2.44
	flamme2r1	537.84	223.89	2.40
	flamme2u1	566.02	246.90	2.29
	plasmar1	569.11	236.63	2.41
	plasmau1	588.87	227.96	2.58
	postr1	564.06	259.20	2.18
	postu1	542.77	210.85	2.57
	sf1	636.16	230.23	2.76
	sf2r1	514.48	194.52	2.64
	sf2u1	543.82	190.55	2.85
	spxr3	563.27	221.67	2.54
	spxu3	587.70	267.79	2.19
	torsor1	603.92	297.79	2.03
	torsou1	585.91	238.83	2.45
	bucky2r2		1511.13
	bucky2u2		1519.59
	fighterr3		1757.53
	fighteru3		1918.77
	flamme2r2		1620.70
	flamme2u2		1716.28
	plasmar2		1488.51
	plasmau2		1572.15
	postr2		1983.04
	postu2		1786.25
	sf1r1		1452.39
	sf1u1		1136.74
	sf2r2		1404.00
				INRIA

Table 8 :

 8 Gradient sur Opteron

		Meshes		Original		Geometric			OpenCCL			FastCOL	FastCOL vs
			time (s)	L1	L2	time	L1	L2	time	L1	L2	time	L1	L2	OpenCCL
		spx	0.10	2.75E+05 2.07E+04 1.00 1.50 0.53 1.02 2.63 0.31 1.00 2.62 1.02	1.02
		fighter	0.56	1.80E+06 4.56E+05 1.07 1.51 1.22 1.03 1.32 3.14 1.09 2.29 2.78	0.94
		spxr1	0.77	3.43E+06 3.53E+05 1.03 1.55 1.35 1.03 1.08 1.72 1.03 2.11 1.60	1.00
		spxu1	0.77	5.39E+06 6.92E+05 0.99 2.43 2.78 1.03 2.58 1.28 1.02 5.89 3.35	1.01
		blunt	1.82	7.03E+06 1.99E+06 1.08 2.04 3.10 1.15 1.67 3.90 1.10 3.47 3.64	1.04
		post	4.79	1.33E+07 1.56E+06 1.02 1.71 0.79 1.05 2.36 1.10 1.03 2.33 1.09	1.02
		bucky2	9.22	1.70E+07 4.04E+06 0.95 0.30 0.82 0.97 0.86 1.36 0.99 1.51 1.35	0.98
		fighterr1	9.86	5.81E+07 2.43E+07 1.17 0.92 2.98 1.28 1.42 11.67 1.30 6.66 11.31	0.98
		fighteru1	9.58	3.05E+07 1.90E+07 1.16 1.01 4.63 1.19 0.85 8.42 1.22 3.32 8.21	0.98
		flamme2	11.62	3.37E+07 5.44E+06 0.93 0.54 0.33 1.05 1.44 1.56 1.05 1.38 1.78	1.00
		plasma	9.49	4.04E+07 3.54E+06 0.97 1.09 0.81 1.02 1.57 1.19 1.02 2.24 1.28	1.00
		spxr2	8.74	3.36E+07 1.03E+07 1.05 1.00 1.41 1.12 3.86 3.95 1.13 3.64 4.74	0.99
		spxu2	9.38	4.14E+07 1.13E+07 1.04 1.17 1.32 1.13 4.99 5.15 1.11 5.06 4.65	1.02
		torso	10.48	3.70E+07 2.78E+07 1.17 0.71 3.08 1.29 1.79 12.08 1.28 3.77 10.97	1.01
		sf2	15.99	5.15E+07 7.72E+06 1.03 1.33 1.32 1.03 0.61 1.86 1.04 3.12 1.81	0.99
		bucky2r1	86.59	5.49E+08 1.46E+08 1.02 1.20 1.78 1.17 7.30 7.08 1.18 6.04 6.59	0.99
		bucky2u1	75.22	3.34E+08 6.64E+07 1.01 2.36 1.27 1.05 4.53 3.45 1.09 4.14 3.13	0.97
		fighterr2	103.27 4.29E+08 2.33E+08 1.16 0.95 1.84 1.29 2.09 10.96 1.36 4.77 9.94	0.95
		fighteru2	100.64 4.52E+08 2.06E+08 1.12 0.71 1.50 1.29 2.72 9.57 1.30 4.57 8.89	0.99
		flamme2r1	90.76	5.63E+08 1.54E+08 0.96 1.14 0.77 1.17 5.71 7.17 1.20 5.69 6.54	0.97
		flamme2u1	93.60	4.76E+08 1.67E+08 1.01 1.01 0.92 1.22 5.98 7.12 1.22 4.96 6.71	1.00
	INRIA	plasmar1	89.63	2.72E+08 1.05E+08 1.01 0.79 1.35 1.14 2.66 4.71 1.12 2.75 4.34	1.01

Table 24 :

 24 GpuTree sur GTX280

	Meshes		Original		Geometric		OpenCCL		FastCOL	FastCOL (bsp)	FastCOL (bsp)
		time (ms) uncoalesced time uncoalesced time uncoalesced time uncoalesced time uncoalesced	vs OpenCCL
	spx	0.50	1.37E+04	0.94	0.58	1.01	1.28	1.01	1.18	1.06	1.42	1.04
	fighter	3.43	1.33E+05	1.14	0.92	1.44	1.99	1.45	1.99	1.67	2.08	1.16
	spxr1	1.77	7.20E+04	0.90	0.86	1.19	2.03	1.16	1.84	1.34	2.11	1.12
	spxu1	1.10	4.61E+04	0.90	0.86	1.18	1.98	1.13	1.77	1.28	2.03	1.09
	blunt	1.38	5.75E+04	0.98	1.02	1.16	1.95	1.16	1.95	1.3	1.99	1.12
	post	2.05	6.90E+04	0.91	0.86	1.08	1.39	1.14	1.71	1.32	2.02	1.21
	bucky2	9.91	2.85E+05	0.81	0.74	1.20	1.44	1.18	1.37	1.34	1.42	1.11
	fighterr1	37.29	6.30E+05	1.98	1.00	3.08	2.20	2.96	1.96	3.58	2.30	1.16
	fighteru1	20.48	5.14E+05	1.29	0.95	2.08	2.17	2.02	1.90	2.45	2.29	1.18
	flamme2	5.79	1.71E+05	0.55	0.60	1.17	1.42	1.13	1.31	1.31	1.46	1.12
	plasma	4.68	1.35E+05	0.76	0.81	1.16	1.50	1.14	1.42	1.26	1.49	1.08
	spxr2	9.25	3.38E+05	0.64	0.90	1.33	2.08	1.27	1.87	1.5	2.13	1.12
	spxu2	5.18	1.86E+05	0.58	0.92	1.33	2.13	1.28	1.89	1.5	2.18	1.13
	torso	11.08	6.84E+05	1.41	0.98	2.63	2.39	2.38	2.05	2.81	2.40	1.07
	sf2	20.50	5.47E+05	1.01	1.06	1.24	1.37	1.23	1.24	1.4	1.33	1.13
	bucky2r1	115.87	3.70E+06	0.75	0.93	1.77	1.99	1.69	1.75	2	1.99	1.13
	bucky2u1	89.89	2.55E+06	1.07	0.97	1.98	2.03	1.88	1.78	2.24	2.05	1.13
	fighterr2	327.00	7.57E+06	1.17	0.93	2.74	2.18	2.59	1.89	3.13	2.18	1.14
	fighteru2	162.22	4.00E+06	1.02	0.95	2.67	2.25	2.51	1.95	3.02	2.25	1.13
	flamme2r1	66.26	2.06E+06	0.57	0.89	1.82	2.08	1.73	1.82	2.03	2.08	1.12
	INRIA

Table 26 :

 26 GpuTree sur 8800GTX

	Meshes		Original		Geometric		OpenCCL		FastCOL	FastCOL (bsp)	FastCOL (bsp)
		time (ms) uncoalesced time uncoalesced time uncoalesced time uncoalesced time uncoalesced	vs OpenCCL
	spx	0.63	1.78E+02	1.00	1.00	1.00	1.00	1.01	1.00	1	0.98	1
	fighter	4.22	9.08E+02	1.24	1.00	1.31	1.00	1.32	1.00	1.4	0.96	1.06
	spxr1	2.14	5.44E+02	0.92	1.00	1.05	1.00	1.05	1.00	1.1	0.99	1.05
	spxu1	1.29	3.20E+02	0.91	1.00	1.04	1.00	1.05	1.00	1.09	1.00	1.05
	blunt	1.65	3.84E+02	1.00	1.00	1.07	1.00	1.07	1.00	1.14	0.97	1.06
	post	2.42	5.71E+02	0.86	1.00	1.00	0.99	1.02	1.00	1.08	0.99	1.08
	bucky2	10.87	2.98E+03	0.86	1.00	1.01	1.00	1.02	1.00	1.07	0.99	1.06
	fighterr1	56.32	4.06E+03	1.88	1.00	3.69	1.00	3.67	1.00	3.98	0.99	1.08
	fighteru1	34.00	3.39E+03	1.25	1.00	2.71	1.00	2.71	1.00	2.92	0.99	1.08
	flamme2	7.05	1.60E+03	0.39	1.00	1.09	1.00	1.08	1.00	1.16	1.00	1.06
	plasma	6.08	1.33E+03	0.70	1.00	1.10	1.00	1.11	1.00	1.16	0.99	1.05
	spxr2	10.28	2.36E+03	0.40	1.00	1.12	1.00	1.11	1.00	1.19	1.00	1.06
	spxu2	5.95	1.24E+03	0.38	1.00	1.12	1.00	1.13	1.00	1.21	1.00	1.08
	torso	16.79	4.16E+03	1.65	1.00	1.98	1.00	2.02	1.00	2	0.91	1.01
	sf2	25.29	6.02E+03	1.01	1.00	1.15	1.00	1.14	1.00	1.2	0.97	1.04
	mean 100K	1.98	4.67E+02	1.01	1.00	1.09	1.00	1.10	1.00	1.15	0.98	1.05
	median 100K	1.65	3.84E+02	1.00	1.00	1.05	1.00	1.05	1.00	1.10	0.98	1.05
	min 100K	0.63	1.78E+02	0.91	1.00	1.00	1.00	1.01	1.00	1.00	0.96	1.00
	max 100K	4.22	9.08E+02	1.24	1.00	1.31	1.00	1.32	1.00	1.40	1.00	1.06
	mean 1M	17.51	2.77E+03	0.94	1.00	1.60	1.00	1.60	1.00	1.69	0.98	1.06
	median 1M	10.58	2.67E+03	0.86	1.00	1.12	1.00	1.12	1.00	1.19	0.99	1.06
	min 1M	2.42	5.71E+02	0.38	1.00	1.00	0.99	1.02	1.00	1.07	0.91	1.01
	max 1M	56.32	6.02E+03	1.88	1.00	3.69	1.00	3.67	1.00	3.98	1.00	1.08

RR n°7118

Blunt fin, buckyball, langley fighter, liquid oxygen post, plasma64, san fernando and spx models are provided by the AIM@SHAPE Shape Repository (http://shapes.aim-at-shape.net/). Torso is courtesy of SCI and the last one is not published.RR n°7118

The other meshes produce similar graphs.INRIA

Tchiboukdjian & Danjean & Raffin

Tchiboukdjian & Danjean & Raffin


Hiba Yousef
email: hiba.yousef@telecom-paristech.fr

Jean Le

Feuvre Ltci

Giuseppe Valenzise
email: giuseppe.valenzise@l2s.centralesupelec.fr

Vedad Hulusic
email: vhulusic@bournemouth.ac.uk

Video Quality Evaluation for Tile-Based Spatial Adaptation

Keywords: Spatial-Based adaptation, HTTP adaptive streaming, Video quality evaluation, HEVC tiling

The demand for very high-resolution video content in entertainment services (4K, 8K, panoramic, 360 VR) puts an increasing load on the distribution network. In order to reduce the network usage in existing delivery infrastructure for such services while keeping a good quality of experience, dynamic spatial video adaptation at the client side is seen as a key feature, and is actively investigated by academics and industrials. However, the impact of spatial adaptation on quality perception is not clear. In this paper, we propose a methodology for the evaluation of such adapted content, conduct a series of perceived quality measurements and discuss results showing potential benefits and drawbacks of the technique. Based on our results, we also propose a signaling mechanism in MPEG-DASH to assist the client in its spatial adaptation logic.

I. Introduction

Super high resolution and immersive video are expected to significantly increase the bandwidth consumption in video streaming services. In some cases, such as for 360 and panoramic video, only portions (viewports) of the video are displayed to the user at a given time. In those applications, spatially adapting the quality of the video, e.g., reducing the quality of those parts of the content which are outside the region of interest (ROI), is a key tool to achieve a more efficient use of network resources.

In video coding, spatial quality adaptation is typically implemented by bit allocation algorithms. They can operate at different levels of granularity, from group-ofpictures to the coding unit or macroblock level. While this flexibility enables to achieve good coding gains, it might be too complex and even impractical in the context of adaptive video streaming targeting a large number of viewers. Indeed, in order to address all the users and their viewing conditions, the provider should encode a very large number of versions of the content, one per possible active combination of viewing criteria, resulting in overloading the server and/or CDN capacity. Another approach for spatial quality adaptation, discussed in this work and, currently, in MPEG-DASH, is to divide the video into a grid of N×M videos (either independent or using schemes such as HEVC tiles [START_REF] Sullivan | Overview of the high efficiency video coding (hevc) standard[END_REF]), encoded at different qualities, and let the client decide which video to pick based on its current viewing conditions.

When mixing tiles at different qualities, an important question is how the quality difference between tiles may affect the overall visual quality. In fact, boosting the quality of the tile containing the ROI might introduce artificial horizontal or vertical edges, due to the quality gap with neighboring tiles. This might in turn distract the visual attention and affect quality judgment [START_REF] Itti | Computational modelling of visual attention[END_REF]. In this paper, we study how overall video quality is affected by spatial quality adaptation in tiled video, by means of a subjective study on five 4K video contents. Specifically, for each content we encode tiles at two different bitrates: a higher bitrate for the ROI (identified in a preliminary visual attention test), and a lower one for the background. We then compare the visual quality of the video, measured through Mean Opinion Score (MOS), to a uniform tiling scheme (i.e., where all tiles have the same bitrate), for the same total bitrate. Our results show that non-uniform allocation might lead to important quality gains, mostly at low-to-medium bitrates. However, the gains highly depend on the semantic and perceptual masking properties of the content. Based on these results, we propose a new MPEG-DASH descriptor to signal which quality differences between ROI/non-ROI tiles are acceptable for a given content.

The rest of this paper is organized as follows. Section II presents related work in the domain. Section III presents the methodology used in video quality evaluation and describes the conducted experiment. Section IV presents the results of the experiments and discusses their impact on the adaptive streaming client and related options proposed for MPEG-DASH. Finally, Section V concludes this paper and proposes future work.

II. Related Work

Coding video with spatially varying quality has been largely studied in the past decades. Examples include sprite coding [START_REF] Hepper | Efficiency analysis and application of uncovered background prediction in a low bit rate image coder[END_REF], MPEG-4 Visual Objects [START_REF] Vetro | Mpeg-4 rate control for multiple video objects[END_REF], [START_REF] Vetro | Object-based coding for long-term archive of surveillance[END_REF] and other more recent ROI-based bit allocation schemes for H.264/AVC and H.265/HEVC [START_REF] Liu | Region-of-interest based resource allocation for conversational video communication of h. 264/avc[END_REF], [START_REF] Li | Visual attention guided bit allocation in video compression[END_REF], [START_REF] Meddeb | Regionof-interest-based rate control scheme for high efficiency video coding[END_REF], [START_REF] Himawan | Impact of automatic region-of-interest coding on perceived quality in mobile video[END_REF], [START_REF] Xu | Region-of-interest based conversational hevc coding with hierarchical perception model of face[END_REF], [START_REF] Bai | Saliency based rate control scheme for high efficiency video coding[END_REF]. In most cases, ROI-based allocation targets specific applications scenarios, e.g., assigning higher quality to faces in teleconferencing [START_REF] Meddeb | Regionof-interest-based rate control scheme for high efficiency video coding[END_REF], [START_REF] Xu | Region-of-interest based conversational hevc coding with hierarchical perception model of face[END_REF]. Previous work demonstrates that a proper rate allocation strategy might lead to substantial (albeit content-dependent [START_REF] Lai | A contentbased bit allocation model for video streaming[END_REF]) gains in terms of perceived visual quality. In [START_REF] Himawan | Impact of automatic region-of-interest coding on perceived quality in mobile video[END_REF] these gains were shown to be more important at low bitrates; however, their results were found on mobile video, and it is not clear how this conclusion extends to high-resolution content.

Our work relies on this previous art, but considers a different perspective: we consider the more general case of content with ROI bringing any semantics, and in the particular case of streamed tiled video [START_REF] Concolato | Adaptive streaming of HEVC tiled videos using MPEG-DASH[END_REF]. Instead of defining at the encoding time the ROI and adjust its quality, we focus on using uniform quality at the encoder side, unaware of any ROI/spatial quality adaptation, and mix the qualities at the receiver side, using the HEVC tiles mechanism which enables parallel processing of different parts (Tiles) within the same picture [START_REF] Misra | An overview of tiles in hevc[END_REF]. We chose the HEVC Tiling approach for simplicity and interoperability reasons, since all the existing HEVC profiles include Tiles. For the same reason, tile-based streaming has been recently studied for 360 • video [START_REF] Graf | Towards bandwidth efficient adaptive streaming of omnidirectional video over http: Design, implementation, and evaluation[END_REF] and panoramic streaming [START_REF] Sãąnchez | Compressed domain video processing for tile based panoramic streaming using hevc[END_REF]. Tiling approach, on the other hand, imposes a number of constraints, e.g., the tiling scheme is much simpler and has coarser-granularity compared to previously proposed methods; in addition, quality adaptation is not a part of the rate-distortion optimization such as previously proposed ROI-based coding schemes, which implies that only a small set of different representations of the video can be stored and streamed to the user. Finally, the large spatial extent of tiles introduces stronger, more detectable visual artifacts (horizontal and vertical tile edges) compared to a fine-granularity bit allocation approach. The purpose of this work is to evaluate the impact of such artifacts and to understand to which extent and under which conditions adaptive bit allocation in tiling is advantageous.

III. Video Quality Evaluation Experiment

In this section, we describe the subjective experiment we conducted in order to assess the impact of spatial adaptation in tiled video streaming.

1) Material Selection: For the study, six 4K sequences from the Joint Video Exploration Team (JVET) dataset 1 were used. Example frames for each sequence are reported in Figure 1. The sequences were selected based on their temporal and spatial information [START_REF] Itu-T | Subjective video quality assessment methods for multimedia applications[END_REF], see Figure 2. To span the largest possible range of the spatio-temporal plane, ToddleFountain, Tango, Drums and CatRobot were chosen. DaylightRoad and TrafficFlow were close on SI-TI plane, so TrafficFlow was chosen as the fifth test

A. Identification of Regions of Interest

In order to spatially adapt the bitrate across tiles, we first need to detect the region(s) of interest for each scene. To this end, we employed an eye tracker and recorded eye fixations using the GazeRecorder2 software. The visual attention (VA) experiment was conducted with 10 participants (5F/5M) with normal or corrected-to-normal vision. They were asked to watch the sequences naturally, i.e., without a specific task. Based on the the VA results, the test sequences can be classified into three types: a) content with a nearly static ROI: Drums, CatRobot, DaylightRoad, b) content with a dynamic ROI: Tango, ToddlerFountain and c) content without a clearly identifiable ROI: Traf-ficFlow.

B. Design

We used the double stimulus impairment scale (DSIS) methodology for the test [START_REF] Itu-T | Subjective video quality assessment methods for multimedia applications[END_REF], [START_REF] Simone | Selected contributions on multimedia quality evaluation[END_REF], [START_REF] Itu-T | Methodology for the subjective assessment of the quality of television pictures[END_REF]. The subjects were presented once with a pair of stimuli, and had to evaluate the impairment of the test stimulus with respect to the reference, using a 5-grades continuous degradation scale. The associated terms "Imperceptible", "Perceptible but not annoying", "Slightly annoying", "Annoying" and "Very annoying" are included for general guidance. Hereafter we will refer to these qualities on the impairment scale as

Q m = {Q 1 , Q 2 , Q 3 , Q 4 , Q 5 }, Q 1 being "Imperceptible".
We performed a selection between more than 1500 encoded sequences including uniform and non-uniform tiling grid, mixing tiles with the same and different qualities for the 6 input sequences. Overall, 130 video scenes in a random sequence order, all lasting for 8 seconds, were evaluated in the study by each participant.

1) Participants: 15 participants (7F/8M), naive to the purpose of the experiment, aged between 20 and 50, volunteered for the experiment. All of them reported normal or corrected-to-normal visual acuity.

2) Apparatus: The subjective test was performed in a dark and quiet test room dedicated to subjective visual tests [START_REF] Itu-R | The present state of ultra-high definition television[END_REF]. The display used in the subjective test was a commercial 64.5" 4K TV screen (TV SONY KD-65XD7505) at 3840×2160 pixels resolution, with the peak luminance of 350 cd/m 2 . The distance from the screen was fixed to 1.5 height of the display, with the eyes located at the center of the display.

3) Stimuli: In the main study, the same video sequences as for the VA test were used. In total, for each video content, 26 test stimuli were used for the test (5 without tiling, 5 with uniform tiling, and 16 tiled videos with spatial adaptation), as explained below.

For each original video, we used the Kvazaar 3 open source HEVC codec to encode 200 frames into 40 different qualities. The encoder was set to produce a uniform tile grid of T = 3 × 3 tiles. Motion vectors constraints are taken into account as suggested in [START_REF] Concolato | Adaptive streaming of HEVC tiled videos using MPEG-DASH[END_REF]. Five different qualities Q m , m = 1, . . . , 5, with Q 5 being the highest quality level, corresponding to a uniform bitrate allocation across tiles BR m,c (where c denotes video content), were chosen visually by 5 expert viewers to match the 5-grades of the continuous impairment scale. Then, we adapted each quality {Q 1 , Q 2 , Q 3 , Q 4 } with 4 different adaptations (Q 5 was not considered since the quality of all tiles was already high enough and the artifacts were imperceptible).

To this end, we first identify the N roi tiles that contain the ROI. For each video, these tiles are coded at the same bitrate, BR roi k , where k = 1, . . . , 4, denotes the adaptation level, in order to avoid quality discontinuities across the ROI. Conversely, the N roi = T -N roi tiles that do not contain the ROI are coded with a bitrate BR roi k . The bitrate for the ROI tiles is found by increasing the bitrate of uniform allocation at a given quality level, i.e.,

BR roi k = δ k • BR m,c , with δ k > 1.
The bitrate for non-ROI tiles, BR roi k , is then found by ensuring that the total 3 http://ultravideo.cs.tut.fi/# encoder bitrate for each adaptation setting equals the bitrate of uniform allocation, by solving the following equation:

N roi • BR roi k + N roi • BR roi k = T • BR m,c . (1)
The division between ROI and non-ROI tiles might create artificial edges, that we name Quality-Switch Edges (QSE). The number of ROI tiles, ROI tile indices (in raster-scan order, starting at index 1 for top-left tile) and QSEs for each content are given in Table I. It remains to find the values of δ k to determine the four adaptations for each content. We adopted the following strategy. A panel of 4 expert viewers inspected videos coded with different tiles mixed at different bitrates, in order to determine the maximum bitrate increment factor, δ 4 = δ max , for each content and quality level. δ max was chosen in such a way to avoid having different tiles in a frame clearly corresponding to different attributes on the impairement scale, as this might hinder the use of the scale in the test. In practice, we found that δ max is the largest value past which QSE visibility becomes the dominant artifact in the quality assessment procedure. Once δ 4 has been found, the remaining values of δ k , k = 1, . . . , 3, are set to δ k = δ max -1 4 . 4) Procedure: All videos were evaluated by each participant. The test was divided into three sessions to keep the duration of each session below 20 minutes. The test started with a training phase using the DaylightRoad sequence. The reference stimulus was the sequence encoded in a high bitrate without tiling; the test stimuli were the tiled and the non-tiled version with 5 different qualities of the sequence. Each subject observed the reference and then the test stimuli once for 8 seconds each and had 5 seconds to evaluate the overall quality through quality-rating forms.

IV. Results and Discussion

To analyze the results, we first computed the mean opinion scores (MOS) with the corresponding 95% confidence intervals. The values of MOS for the different spatial adaptation bitrate mixing (indicated by δ k ), as well as the MOS of uniform tiling and no-tiling configurations, are

reported in Figure 3, for different bitrates corresponding to quality levels Q 1 to Q 4 . Figure 4 aggregates these results by picking the best bitrate mix (i.e., the δ k yielding the highest MOS) across bitrates.

A. Effect of bitrate

At lower bitrates, we can see that the spatial adaptation gives better result than the uniform tiling grid for content with ROI, confirming that our approach can be used in adaptive streaming to provide better quality at the client side. Furthermore, it seems that configurations with higher QSE (CatRobot, Traffic) have a lesser perceived quality than configurations with lower QSE (Drums, Tango, Toddler). We plan on further looking at that possible correlation in future work. From the results, we can see that higher potential gains for spatial adaptations are found at low-to-medium bitrates, the artifact introduced by QSE being more visible than other at such rates. It is important to note that no post-processing other than HEVC standard one was applied on the content after decoding, in order to remain compatible with existing HEVC deployments. This implies that no deblocking filter was applied on QSE, making these more visible at higher rates. This shows the major complexity of HEVC tiling spatial adaptation: encoders have to ensure that tiles borders are not more visible than other coding artifacts, to avoid degrading the perceived quality of the (uniform tiled) content.

B. Presence of ROI

As expected, we also found out that the sequence without ROI (Traffic) did not benefit much from the spatial adaptation. We can derive the recommendation that spatial adaptation in sequences without a clear ROI should be used carefully, as it is in general not advantageous and can actually be detrimental to quality due to the presence of QSE's.

C. Effect of δ

We can observe that the choice of δ, i.e., quality difference between tiles, impacts the average quality gains, due to the trade-off between higher ROI quality vs. more QSE. It also makes the evaluation more difficult as distortion is spatially localized and overall quality is more difficult to judge. The choice of δ is very important and affects significantly the overall quality: by running factorial ANOVA we found a significant effect of the tiling scheme for all contents. Most importantly, the best δ is both content and rate dependent.

D. Applicability to HTTP Adaptive Streaming

We can see from this study that the benefit of spatial adaptation can be important at low bitrates, but most importantly that the quality variation δ across tiles has different impact based on the content. This implies that an adaptive streaming client cannot make the decision of selecting the quality using only bitrates/quality ranking of the media, but requires additional signaling derived from the content type. Based on this work, we have proposed in MPEG-DASH a mechanism to signal at the manifest level which tile quality combinations are acceptable for the given content. This is achieved by a DASH descriptor called QualityEquivalence, which allows specifying a target maximum quality difference between representations from different adaptation sets played together. This can apply to spatial HEVC adaptation, where each tile corresponds to one adaptation set. By carefully choosing the qualities of each tile, it is possible to instruct the client to perform tile adaptation on lower rates but not on higher rates for which the benefit is not obvious. This work is currently under standardization at MPEG [START_REF] Systems | w17213 -dash technologies under consideration[END_REF]. In order for the community to reproduce and extend this experiment, the test sequences and tools used are made available at http://gpac.io.

V. Conclusion

In this paper, we presented a subjective study to evaluate the impact on perceived video quality when doing spatial-based adaptation on HEVC content using tiles. We have shown that especially at lower bitrates one can benefit from spatial adaptation, in some cases achieving better quality than non-tiled version at the same overall bitrate. At the same time, we have shown that too high bitrate differences between tiles, producing visible artifacts at Quality-Switch-Edges (QSE), can negatively impact the overall perceived quality. We have also shown that the perceived quality depends on the nature of the content, and proposed a mechanism in MPEG-DASH to help the client in its adaptation logic for spatial adaptation. In future work, we plan to investigate QSE correlation to perceived quality, extending the experiment on video for 360 VR (cube maps or equi-rectangular projections), and designing a tiled-based rate adaptation logic leveraging the results of this study in order to conduct real-time experiments on spatial adaptation for 360 video live broadcast.

1

  https://mpeg.chiariglione.org/standardsexploration/futurevideo-coding/n16512-work-plan-assessment-test-material sequence since it is the only sequence that does not have a specific ROI according to the visual attention test. The DaylightRoad was kept as a training sequence.

Fig. 2 .

 2 Fig. 2. Spatial and Temporal Information for the test sequences

Fig. 1 .

 1 Fig. 1. Example frames of the selected sequences; (a) CatRobot, (b) DaylightRoad, (c) Drums, (d) Tango, (e) TrafficFlow, (f) Toddler-Fountain

Fig. 3 .

 3 Fig. 3. Comparison of mean opinion scores (MOS) across different scenes, bitrates and tiling conditions with the 95% confidence intervals. The MOS axis is adjusted on each graph for better precision

Fig. 4 .

 4 Fig. 4. Rate-MOS curves obtained through the subjective test. For the adaptive tiling curve, we selected for each bitrate δ the giving the best visual quality.

TABLE I

 I The number of ROI tiles, ROI tile indices and QSEs for the test sequences. The maximum number of QSE is 12, since we use a 3×3 tiling configuration.

	Scene	Nroi	ROI tile indices	QSEs
	CatRobot	4	4,5,7,9	7/12
	Drums	4	2,3,5,6	4/12
	Tango	6	1,2,4,5,7,8	3/12
	Toddler	2	4,5	5/12
	Traffic 4	3	4,5,6	6/12

TABLE II

 II Total bitrate per scene [Mbps] and ROI bitrate increment factors δ k .

	Scene	BR1	BR2	BR3	BR4
	CatRobot (S1)	1.5	2.3	3	4.5
	δ 1	1.05	1.1	1.125	1.1875
	δ 2	1.1	1.2	1.25	1.375
	δ 3	1.15	1.3	1.375	1.5625
	δ 4	1.2	1.4	1.5	1.75
	Drums (S2)	2.7	3.2	4.2	6
	δ 1	1.125	1.15	1.15	1.1875
	δ 2	1.25	1.3	1.3	1.375
	δ 3	1.375	1.45	1.45	1.5625
	δ 4	1.5	1.6	1.6	1.75
	Tango (S3)	2	2.5	3	4
	δ 1	1.1	1.075	1.1	1.15
	δ 2	1.2	1.15	1.2	1.3
	δ 3	1.3	1.225	1.3	1.45
	δ 4	1.4	1.3	1.4	1.6
	Toddler (S4)	10	20	30	35
	δ 1	1.5	1.65	1.6	1.6
	δ 2	2	2.3	2.2	2.2
	δ 3	2.5	2.95	2.8	2.8
	δ 4

https://sourceforge.net/projects/gazerecorder/

For the Traffic scene, no particular ROI was found in the VA test, so an horizontal tile line was selected to reduce intersections of tile borders with the content.

Acknowledgment

This work has been achieved within the Live360TV (http://www.live360tv.com/) collaborative research project, supported by three clusters (Images & Réseaux, Imaginove and Cap Digital) and partially funded by the French Government and three local councils (Région Bretagne, Région Rhône-Alpes and Région Ile-De-France).