Rubens E A Moreira
email: rubens@dcc.ufmg.br

Caroline Collange
email: caroline.collange@inria.fr

Fernando Magno
email: fernando@dcc.ufmg.br

Quintão Pereira

Function Call Re-Vectorization

Keywords: D -Software [D.3 Programming Languages]: D.3.4 Processors -Compilers General Terms Languages, Performance SIMD, SIMT, Function, Programmability

Programming languages such as C for CUDA, OpenCL or ISPC have contributed to increase the programmability of SIMD accelerators and graphics processing units. However, these languages still lack the flexibility offered by lowlevel SIMD programming on explicit vectors. To close this expressiveness gap while preserving performance, this paper introduces the notion of Call Re-Vectorization (CREV). CREV allows changing the dimension of vectorization during the execution of a kernel, exposing it as a nested parallel kernel call. CREV affords programmability close to dynamic parallelism, a feature that allows the invocation of kernels from inside kernels, but at much lower cost. In this paper, we present a formal semantics of CREV, and an implementation of it on the ISPC compiler. We have used CREV to implement some classic algorithms, including string matching, depth first search and Bellman-Ford, with minimum effort. These algorithms, once compiled by ISPC to Intel-based vector instructions, are as fast as state-of-the-art implementations, yet much simpler. Thus, CREV gives developers the elegance of dynamic programming, and the performance of explicit SIMD programming.

Introduction

New hardware asks for new programming idioms. As an example, the appearance of general purpose Graphics Processing Units (GPUs) has led to a revolution in programming languages [START_REF] Garland | Understanding throughputoriented architectures[END_REF][START_REF] Nickolls | The GPU computing era[END_REF], which has culminated in the materialization of languages such as C for CUDA [START_REF] Sanders | CUDA by Example: An Introduction to General-Purpose GPU Programming[END_REF], OpenCL [START_REF] Munshi | OpenCL Programming Guide[END_REF], ISPC [START_REF] Pharr | ISPC: A SPMD compiler for highperformance CPU programming[END_REF] and PyCuda [START_REF] Klöckner | Pycuda and pyopencl: A scripting-based approach to gpu run-time code generation[END_REF]. These Multi-Threaded (MT) languages let programmers express computations as single kernels executed by many threads. They target architectures that combine SIMD and multi-threaded execution, like GPUs and multi-core CPUs with vector instructions.

However, such high-level abstractions come at a cost in flexibility and composability. Most programming languages that target hardware accelerators pack threads into SIMD vectors or GPU warps 1 for the whole duration of a kernel call. They also suspend and resume individual threads to simulate thread-dependent control flow. These constraints affect device-side library functions, which cannot assume any particular organization of parallelism nor thread activity. For instance, invoking full SIMD functions within divergent regions might lead to incorrect behavior. Consequently, library functions often contain two versions of each routine, and dynamically dispatch the proper version depending on whether threads diverge at the call site or not 2 .

On GPUs, developers circumvent the restrictions listed above in two ways: via warp-synchronous programming, or via dynamic parallelism. In the first case, programmers use the knowledge that threads are grouped in warps to achieve thread communication without synchronization or memory sharing. Yet, warp-synchronous programming is not easily composable with classic multi-thread programming. Programmers must ensure that every thread in a warp participates in each collective operation; e.g., the CUDA shfl function has undefined behavior when reading data from an inactive thread. However, multi-thread programming puts thread divergences out of the hands of programmers. Consequently, such warp-synchronous functions may not be called from multi-thread code that may have divergent control flow.

CUDA's dynamic parallelism (or OpenCL's device-side enqueue) lets threads already in flight create new groups of threads [START_REF] Yang | CUDA-NP: realizing nested threadlevel parallelism in GPGPU applications[END_REF]. This feature gives developers the opportunity to implement strikingly elegant algorithms [START_REF] Merrill | High performance and scalable radix sorting: A case study of implementing dynamic parallelism for GPU computing[END_REF]. However, this construct is too heavyweight for our simpler purpose of reactivating threads within a warp. For instance, invoking new threads from within a thread in CUDA involves the global scheduling of a new grid of threads [START_REF] Jones | Introduction to dynamic parallelism -Invited Talk[END_REF], a very expensive event. In short, currently, either we have the programmability and elegance of the multi-threaded model, or the efficiency of warp-synchronous programming, but not both.

The goal of this paper is to allow the composability of SIMD and MT through a programming construct syntactically similar to dynamic parallelism. To this end, we intro-duce the notion of Call Re-Vectorization (CREV). CREV is a programming idiom that modifies function calls. Functions marked with the crev tag, henceforth called r-functions, are executed by all the threads in a SIMD unit. This implies a context switch: to run a r-function, the runtime must change the state of all the threads, including those inactive due to divergent control flows. Upon completion, workers return to their previous state, in the same way that a function call is handled. Thus, we achieve a new level of recursion, in which threads can spawn new threads in a stack-based fashion. However, contrary to traditional dynamic parallelism, CREV uses only the accelerator's local memory (registers and call stack) to save thread states; hence, it is cheaper.

To validate our ideas, we have implemented them in ISPC [START_REF] Brodman | Writing scalable SIMD programs with ISPC[END_REF][START_REF] Pharr | ISPC: A SPMD compiler for highperformance CPU programming[END_REF] 3 . ISPC is a programming language, plus its compiler. This compiler produces industrial quality code for SIMD units such as Intel Streaming SIMD Extensions (SSE), Intel Advanced Vector Extensions (AVX) including AVX-512 for Xeon Phi accelerators [START_REF] Sodani | Knights Landing: Second-generation Intel Xeon Phi product[END_REF], or ARM NEON. We chose to implement CREV in ISPC because this framework supports the notion of unmasked or everywhere blocks [START_REF] Pharr | ISPC: A SPMD compiler for highperformance CPU programming[END_REF]: the ability to activate -in a new context -threads that are idle due to divergences. This feature is a requirement of CREV. We have used this new ISPC's extension to implement several classic algorithms using CREV. We show that these implementations are as efficient as warpsynchronous versions of them, and as clear and elegant as if they had been implemented using dynamic parallelism.

Summary of our Contributions.

The key contribution of this paper is the notion of Call Re-Vectorization, which comes out of the observation that it is possible to capitalize on divergent threads to help speedup the work of active threads. We explain the concept of CREV through examples, a formal semantics and an industrial quality implementation:

• Examples: Section 2 shows examples of algorithms that benefit from our notion of Call Re-Vectorization. Further examples are discussed in Section 4. • Semantics: Section 3.2 formalizes the semantics of µ-SIMD, a low-level instruction set sufficient to implement CREV. We have written a Prolog interpreter to validate that semantics. This interpreter made it easy to prototype different implementations of CREV, until we had a design that we could graft into a state-of-the-art compiler. • Translation: Section 3.3 describes the translation of the high-level "crev" keyword into the low-level representation. Core properties of the final, low-level code, as produced by the translator, are listed in Section 3.4. • Evaluation: Section 4 provides an empirical evaluation of our implementation. To perform this evaluation, we have implemented some algorithms, which are faster and cleaner than their original versions without CREV.

Overview

The goal of this section is to explain Warp-Synchronous Programming, Dynamic Parallelism (DP), and our notion of Call Re-Vectorization (CREV). To this end, we shall use Algorithm 1 as an example. This program receives a book b i , plus a pattern p. It then copies out all the lines l ∈ b i that match p. Pattern matching is performed by memcmp, and memory copying is done by memcpy. The book is represented as a matrix of characters; thus, each of its lines, and also the pattern p, is a vector of up to N characters. Algorithm 1 runs in parallel: t id is a thread identifier. Hence, each thread is in charge of matching a line l in b i against p. In case the match is positive, this thread must copy l to an output matrix b o . For clarity, we assume a single warp in this example, although the techniques we described can be applied independently to multiple warps. The number of threads that run simultaneously in Algorithm 1 is W , the warp width.

Algorithm 1: SIMD Book Filter

1 W ← warp size; t id ← thread index; 2 Function bFilter(mtx b i , mtx b o , vec p, int N ) 3 for k ← t id to num lines(b i ) -1 step W do 4 l ← b i [k]; 5 if memcmp(l, p, N ) == 0 then 6 memcpy(l, b o [k], N );
A naive multi-thread implementation of memcpy iterates sequentially over the arrays within each thread. This implementation is highly inefficient due to branch and memory divergence. Branch divergence occurs if the number of iterations N differs across threads. Threads with few iteration would finish the loop earlier and wait for threads with more iterations in order to restore convergence at the end of the loop. Memory divergence also happens as threads within a warp access data in unrelated locations. Such accesses, referred to as uncoalesced in the CUDA literature or as gather/scatter on SIMD platforms, are bandwidth-inefficient compared to accesses to consecutive elements.

Warp Synchronous Programming

It is possible to write function memcpy in a way that distributes operations on contiguous elements across consecutive threads. Algorithm 2 does it. Function memcpy shfl is aware of the SIMD nature of a warp. Variables are stored as vectors, having each position belonging to a specific thread. Instruction shfl(v, i) allows thread t id to read the value stored in variable v, but in the register space of thread i. This implementation give us an efficient way to copy data between arrays, as copies are distributed evenly between threads, removing most of the branch divergence. Memory divergence is also eliminated as threads of a warp access consecutive elements at each iteration of the loop on line 7.

Nevertheless, this function has an important limitation: it requires all threads in the warp to be active. It cannot safely be called from a point that has potential branch divergence. Indeed, the loop on line 7 would skip elements if some threads were inactive. To support calls to memcpy shfl within divergent regions, we need a way to re-activate threads and put them to work on the copy loop. In addition, the warp-synchronous programming construct is more complex and error-prone than the naive implementation. Nmy ← shfl(N, j);

7 for i ← t id to Nmy -1 step W do 8 dmy[i] ← smy[i];

Dynamic Parallelism in CUDA

In NVIDIA's CUDA and OpenCL 2.0, dynamic parallelism (DP) is the ability to invoke a new kernel K 2 from within a kernel K 1 [START_REF] Wang | Characterization and analysis of dynamic parallelism in unstructured GPU applications[END_REF]. In this case, programmers may request a large number of threads, i.e., multiple new warps in multiple thread blocks. As the inner K 2 is a new kernel, all its threads are active upon entry, regardless of branch divergence in K 1 . Algorithm 3 shows an implementation of memcpy that we could invoke from Algorithm 1 using dynamic parallelism. This algorithm splits, among all the threads in a warp, the work of copying vector s to vector d. Its main advantage is simplicity; its disadvantage is efficiency.

Algorithm 3: Implementation of memcpy that could be invoked dynamically from Algorithm 1.

1 W ← warp size; t id ← thread index; 2 Function memcpy dp(vec s, vec d, int N ) 3 for k ← t id to N -1 step W do 4 d[k] ← s[k];
Wang et al. demonstrate that the overhead of a new kernel launch can be as high as one millisecond [START_REF] Wang | Characterization and analysis of dynamic parallelism in unstructured GPU applications[END_REF]. The new kernel must be scheduled and wait until there are resources available for its execution. Then, the requested number of warps and memory blocks must be allocated before execution starts. For large workloads, the overhead of launching a nested kernel is paid off by the massive data parallelism available in the GPU [START_REF] Dimarco | Performance impact of dynamic parallelism on different clustering algorithms[END_REF]. However, for small tasks, this extra cost might degrade performance.

Call Re-Vectorization

Introducing an inner dimension of parallelism is desirable to implement irregular algorithms such as graph traversal and recursive sorting. Unfortunately, current abstractions based on warp-synchronous programming or Dynamic Parallelism either compromise efficiency or programmability. To solve this conundrum, we introduce Call Re-Vectorization (CREV), a new programming idiom. Syntactically, CREV is akin to CUDA's dynamic parallelism. Semantically, it avoids the cost of scheduling new kernels.

CREV revisits the concept of everywhere (also known as all or unmasked) blocks to temporarily re-enable inactive threads within divergent regions. Such construction was available in programming languages for SIMD machines, such as C* [START_REF] Rose | C*: An extended C language for data parallel programming[END_REF], MPL (MasPar Programming Language) [START_REF] Maspar | MasPar Programming Language (ANSI C compatible MPL) Reference Manual[END_REF] or POMPC [START_REF] Hoogvorst | POMP or how to design a massively parallel machine with small developments[END_REF] in the late 1980s and early 1990s, and has made a recent comeback in ISPC [START_REF] Pharr | ISPC: A SPMD compiler for highperformance CPU programming[END_REF]. In these languages, an everywhere block is executed by every processing element, regardless of its divergent state. At the end of that block, threads are sent back to their original state.

The everywhere block is a low-level construct to support the implementation of CREV; however, programmers do not deal with it directly -this is the task of the code generator. Algorithm 4 shows how Algorithm 1 looks like, once implemented using CREV. Programmers use the crev keyword at line 6 to re-vectorize functions. CREV maintains a stack of thread states to track execution contexts, thus supporting nested calls of r-functions. In terms of performance, a call to a function using the crev directive is equivalent to a regular function call -unlike the implementation of dynamic parallelism in CUDA, for instance. Thus, we favour the use of CREV for fine grain nested parallelism. Section 3 will explain the nitty-gritties behind the CREV directive.

Semantics of CREV

This section presents the semantics of Call Re-Vectorization. First, in Section 3.1, we state informally key features of CREV. In Section 3.2, we introduce µ-SIMD, a low-level programming language with a set of primitives that lets us Algorithm 4: SIMD Book Filter using CREV

1 W ← warp size; t id ← thread index; 2 Function bFilter(mtx b i , mtx b o , vec p, int N ) 3 for k ← t id to num lines(b i )-1 step W do 4 l ← b i [k]; 5 if memcmp(l, p, N ) = 0 then 6 crev memcpy crev(l, b o [k], N ); 7 Function memcpy crev(vec s, vec d, int N ) 8 for k ← t id to N -1 step W do 9 d[k] ← s[k];
implement CREV. In Section 3.3, we show how to implement the crev high-level construct using the building blocks available in µ-SIMD. Finally, in Section 3.4, we use our semantics to state some properties of CREV. Before we dive in these details, Example 3.1 arms the reader with some intuition on how CREV works.

Example 3.1 A function is called with the crev prefix to indicate that every thread, whether enabled or disabled, should execute the function. Every thread should execute the r-function multiple times if multiple enabled threads in the warp call it. For instance, if the warp size is 32 and 7 threads are enabled when the program flow hits line 6 in Algorithm 4, all 32 threads execute memcmp crev 7 times. In each case, the 32 threads temporarily take on the local state of the active thread that they are helping. Once done, these workers all get their local state restored.

The Cornerstones of CREV

CREV is defined as follows: for each active thread that reaches a call tagged with crev, we execute the target function once, forwarding global parameters (scalars) and extracting private ones per active thread (vectors). This principle of Call Re-Vectorization lays on three pillars: thread re-activation, SIMD function call and data distribution.

Thread Re-Activation. CREV does not lead to the creation of new threads. A function invoked via a CREV call is executed by every thread that is part of a warp, regardless of its threads' state. As mentioned in Section 2, a thread might be inactive due to divergences. However, dormant threads are re-activated to perform work. The former state of the thread is saved into the context stack, used for divergence management. On software context stack implementations such as used on AMD GPUs and Intel AVX-512 platforms, this operation is performed entirely in software. For platforms with hardware context stack implementations, like NVIDIA GPUs, it will require a new machine instruction. SIMD Function Call. Multi-thread and SIMD languages have different definitions of function calls. In MT, a function call is only performed by active threads. Only register lanes that correspond to active threads are saved. The other threads are guaranteed to stay inactive during execution of the function and need no context save. Although each thread conceptually has its own private call stack, the call stacks of a warp are typically synchronized for performance reasons and to allow the sharing of a single scalar stack pointer for a warp. Implementations of SIMD languages, on the other hand, save whole vector registers on function calls, keeping one stack pointer per warp. Unlike regular MT functions, rfunctions follow an SIMD application binary interface. This ensures that all registers in-use are saved before being overwritten inside the function, including lanes of threads that were inactive. Because no threads are created, context switch is similar to the cost of invoking a new function.

branch if zero

bz v, l unconditional branch jmp l branch if thread previously active jmp mask t id , l write to shared memory Data Distribution. Each formerly active warp thread is serialized to have a full warp operate on its data. As in the warp-synchronous memcpy example (Algorithm 2), this requires extracting and broadcasting each thread's register lane. Data distribution will be later detailed in Algorithm 5.

↑ v x = v read from shared memory v =↓ v x binary operations v 1 = o 1 ⊕ o 2 copy v = o shuffle data
::= l ∈ N Constants (C) ::= c ∈ N Variables (V ) ::= T id ∪ {v 1 , v 2 , . . . } Instructions (I) ::= Figure 1 Active Threads Θ ⊂ N Local Memory σ ⊂ V → Z Local Memory Bank β ⊂ T id → σ Shared Memory Σ ⊂ N → Z Synch Stack Π ⊂ (L × Θ × L × Θ × Π) Context Stack Λ ⊂ (Θ × Π × Λ) Program P ⊂ L → I Program Counter pc ∈ N

Low-Level Semantics

We formalize the notion of Call Re-Vectorization on top of a core language, µ-SIMD. This language provides the lowlevel constructs necessary to implement r-functions. Most of the syntax of µ-SIMD comes from Sampaio et al. [START_REF] Sampaio | Divergence analysis[END_REF], who, in turn, have reused ideas from Bougé et al. [START_REF] Bougé | Control structures for dataparallel SIMD languages: semantics and implementation[END_REF] and Farrell et al. [START_REF] Farrell | Formal specification of parallel SIMD execution[END_REF]. A µ-SIMD program is a sequence of instructions indexed by a pc. Figure 1 shows µ-SIMD's syntax. To formalize the semantics of µ-SIMD, we use the auxiliary functions shown in Figure 3. The semantics of µ-SIMD is given by Figures 4 and5. The former shows the behavior of instructions that change the program's control flow; the latter shows the behavior of logic and arithmetic instructions. The result of executing a control flow instruction is a triple (Θ, β, Σ). The interface between Figure 4 and Figure 5 is performed by Rules IT and TL. The result of executing an arithmetic or logic instruction is a pair (β, Σ), i.e., they only update the program memory. The semantics of control flow divergences. To simulate the effect of divergences, µ-SIMD has a stack Π. Each element in Π is a tuple (l id , Θ done , l next , Θ todo ), which indicates the point where divergent threads must re-converge. A new tuple is pushed onto Π due to a conditional branch, located at l id , that has caused a divergence, as described by Rules BT, BF and BD, in Figure 4. Θ done is the set of threads that have reached the synchronization point. Θ todo is the set of threads waiting to execute. These threads, once active, will resume execution at label l next . The stack is popped by instructions sync, whose behavior is given by Rules SS and SP. The Thread Stack. To implement CREV, we have added a thread stack Λ to µ-SIMD. This stack is fundamental to the implementation of everywhere blocks. Λ holds pairs (Θ, Π). Figure 4 shows that instructions everywhere (Rule EB) push elements onto Λ, and instructions end everywhere (Rule EE) pop it. The first element in this tuple is the set of threads active immediately before the execution of an everywhere block. The second element is the divergence stack, also in the state before the execution of the last everywhere block traversed by the program flow. In Rule EB (Fig. 4), Θ all represents all the threads available in a warp.

split(Θ, β, v) = (Θ 0 , Θ n ) where Θ 0 = {t | t ∈ Θ and β[t] = σ t and σ t [v] = 0} Θ n = {t | t ∈ Θ and β[t] = σ t and σ t [v] = 0} push([], Θ n , pc, l) = [(pc, [], l, Θ n )] push((pc , [], l , Θ n ) : Π, Θ n , pc, l) = Π if pc = pc where Π = (pc, [], l, Θ n ) : (pc , [], l , Θ n ) : Π push((pc, [], l, Θ n ) : Π, Θ n , pc, l) = (pc, [], l, Θ n ∪ Θ n ) : Π Figure 3.
(SP)

P [pc] = stop (Θ, β, Σ, ∅, Λ, P, pc) → (Θ, β, Σ) (JP) P [pc] = jmp l (Θ, β, Σ, Π, Λ, P, l) → (Θ , β , Σ ) (Θ, β, Σ, Π, Λ, P, pc) → (Θ , β , Σ ) (BT) P [pc] = bz v, l split(Θ, β, v) = (Θ, ∅) push(Π, ∅, pc, l) = Π (Θ, β, Σ, Π , Λ, P, l) → (Θ , β , Σ ) (Θ, β, Σ, Π, Λ, P, pc) → (Θ , β , Σ ) (BF) P [pc] = bz v, l split(Θ, β, v) = (∅, Θ) push(Π, ∅, pc, l) = Π (Θ, β, Σ, Π , Λ, P, pc + 1) → (Θ , β , Σ ) (Θ, β, Σ, Π, Λ, P, pc) → (Θ , β , Σ ) (BD) P [pc] = bz v, l split(Θ, β, v) = (Θ0, Θn) pc = pc + 1 push(Π, Θn, pc, l) = Π (Θ0, β, Σ, Π , Λ, P, pc ) → (Θ , β , Σ ) (Θ, β, Σ, Π, Λ, P, pc) → (Θ , β , Σ ) (BA) P [pc] = jmp mask T id , l T id ∈ Θ (Θ, β, Σ, Π, (Θ , Π ) : Λ, P, l) → (Θ , β , Σ ) (Θ, β, Σ, Π, (Θ , Π ) : Λ, P, pc) → (Θ , β , Σ ) (BI) P [pc] = jmp mask T id , l T id ∈ Θ (Θ, β, Σ, Π, (Θ , Π ) : Λ, P, pc + 1) → (Θ , β , Σ ) (Θ, β, Σ, Π, (Θ , Π ) : Λ, P, pc) → (Θ , β , Σ ) (SS) P [pc] = sync Θn = ∅ (Θn, β, Σ, (pc , Θ0, l, ∅) : Π, Λ, P, l) → (Θ , β , Σ ) (Θ, β, Σ, (pc , ∅, l, Θn) : Π, Λ, P, pc) → (Θ , β , Σ ) (SI) P [pc] = sync pc = pc + 1 (Θn, β, Σ, ( , ∅, , Θ0) : Π, Λ, P, pc ) → (Θ , β , Σ ) (Θ0 ∪ Θn, β, Σ, Π, Λ, P, pc) → (Θ , β , Σ ) (EB) P [pc] = everywhere (Θ all , β, Σ, ∅, (Θ, Π) : Λ, P, pc + 1) → (Θ , β , Σ ) (Θ, β, Σ, Π, Λ, P, pc) → (Θ , β , Σ ) (EE) P [pc] = end everywhere (Θ, β, Σ, Π, Λ, P, pc + 1) → (Θ , β , Σ ) ( , β, Σ, ∅, (Θ, Π) : Λ, P, pc) → (Θ , β , Σ ) (IT) P [pc] = ι ι = Control Flow Instruction (Θ, β, Σ, Θ mask , ι) → (β , Σ ) pc = pc + 1 (Θ, β , Σ , Π, (Θ mask , Π ) : Λ, pc ) → (Θ , β , Σ ) (Θ, β, Σ, Π, (Θ mask , Π ) : Λ, P, pc) → (Θ , β , Σ )
Σ(v) = c Σ v = c (TL) (t, β, Σ, Θ mask , ι) → (σt, Σ ) (Θ, β \ [β[t] → σt], Σ , Θ mask , ι) → (β", Σ") ({t} ∪ Θ, β, Σ, Θ mask , ι) → (β", Σ") (MT) t, β t id = t (BP) t, β v2 = c2 t, β v3 = c3 β[t] = σt c1 = c2 ⊕ c3 (t, β, Σ, , v1 = v2 ⊕ v3) → (σt \ [v1 → c1], Σ) (MV) β[t] = σt σt(v) = c t, β v = c (SI) t, β v1 = c1 t, β v lane = c lane β[t] = σt c lane ∈ Θ mask (t, β, Σ, Θ mask , shfl(v1, v lane )) → (σt \ [v1 → ], Σ) (SV) t, β v1 = c1 t, β v lane = c lane β[t] = σt c lane ∈ Θ mask β[c lane ] = σ lane σ lane (v1) = c2 (t, β, Σ, Θ mask , shfl(v1, v lane )) → (σt \ [v1 → c2], Σ) (CT) β[t] = σt (t, β, Σ, , v = c) → (σt \ [v → c], Σ) (AS) t, β v = c β[t] = σt (t, β, Σ, , v = v ) → (σt \ [v → c], Σ) (LD) t, β vx = cx β[t] = σt Σ cx = c (t, β, Σ, , v =↓ vx) → (σt \ [v → c], Σ) (ST) t, β vx = cx t, β v = cβ[t] = σt (t, β, Σ, , ↑ vx = v) → (σt, Σ \ [cx → c])
Figure 5. Semantics of arithmetic, logic and data-related instructions. Rule TL loops over every thread t ∈ Θ, and for each one of them, executes instruction ι.

No assumption can be made on the order in which instructions run. Figure 7 shows a trace of the execution of the program, given its initial state. Only threads t id = 0 and t id = 3 will enter the everywhere section, because

Instructions v0 = ↓tid Address 0 1 2 3 v1 = (v0 == 0) Contents 0 1 1 0 bz v1,
Σ[0] = Σ[3] = 0.
Nevertheless, all the four threads will execute the commands within that block. Instruction v3 = shfl(v2, v8) lets each thread read into v3 the value of v2 seen by thread v8.

High-Level Semantics

The µ-SIMD assembly gives us the primitive building blocks to implement CREV in higher-level languages. As a proof of concept, we have implemented CREV onto ISPC, using instructions of ISPC that are equivalent to those seen in µ-SIMD. By focusing on an abstract notation, µ-SIMD, instead of on a concrete language, such as ISPC, we claim generality: CREV can be implemented in any environment that supports our notions of everywhere and shuffle. In this section we show how to implement the crev modifier, which marks a function call as an r-function. For simplicity, our high-level language provides only syntax to declare and invoke functions. A function declaration consists of a name f , plus a list of formal parameters, e.g.: f (T p 1 , . . . , T p n ). We let T denote a type modifier, which can be either uniform or varying. We have borrowed this notation from ISPC. Other programming languages have different ways to express these modifiers. For instance, in CUDA we have shared and global allocation filling the role of ISPC's uniform variables.

Figure 8 shows the code that we produce for a r-function call f (a 1 , . . . , a n ), where each a i , 1 ≤ i ≤ n is an actual argument of f . Such an r-function call will trigger up to |Θ| executions of f , one for each active thread t ∈ Θ. The test in lines 3 or 8 in Figure 8 are used to single out the function

Instructions Var 0 1 2 3 0 1 2 3 v0 = ↓tid v0 0 1 1 0 ✓ ✓ ✓ ✓ v1 = (v0 == 0) v1 1 0 0 1 ✓ ✓ ✓ ✓ bz v1, Done F T T F ✓ ✓ ✓ ✓ v2 = 4 * (tid + 1) v2 4 * * 16 ✓ • • ✓ everywhere ✓ • • ✓ v8 = 0 v8 0 0 0 0 ✓ ✓ ✓ ✓ Loop jmp_mask v8, Call T T T T ✓ ✓ ✓ ✓ jmp Next F F F F ✓ ✓ ✓ ✓ Call v3 = shfl(v2, v8) v3 4 4 4 4 ✓ ✓ ✓ ✓ v4 = v3 + tid v4 4 5 6 7 ✓ ✓ ✓ ✓ v5 = ↓v4 v5 2 1 3 4 ✓ ✓ ✓ ✓ v6 = v5 + 1 v6 3 2 4 5 ✓ ✓ ✓ ✓ ↑v4 = v6 ✓ ✓ ✓ ✓ Next v8 = v8 + 1 v8 1 1 1 1 ✓ ✓ ✓ ✓ v7 = (v8 == 4) v7 0 0 0 0 ✓ ✓ ✓ ✓ bz v7, Loop T T T T ✓ ✓ ✓ ✓ Loop jmp_mask v8, Call F F F F ✓ ✓ ✓ ✓ jmp Next T T T T ✓ ✓ ✓ ✓ Next v8 = v8 + 1 v8 2 2 2 2 ✓ ✓ ✓ ✓ v7 = (v8 == 4) v7 0 0 0 0 ✓ ✓ ✓ ✓ bz v7, Loop T T T T ✓ ✓ ✓ ✓ Loop jmp_mask v8, Call F F F F ✓ ✓ ✓ ✓ jmp Next T T T T ✓ ✓ ✓ ✓ Next v8 = v8 + 1 v8 3 3 3 3 ✓ ✓ ✓ ✓ v7 = (v8 == 4) v7 0 0 0 0 ✓ ✓ ✓ ✓ bz v7, Loop T T T T ✓ ✓ ✓ ✓ Loop jmp_mask v8, Call T T T T ✓ ✓ ✓ ✓ jmp Next F F F F ✓ ✓ ✓ ✓ Call v3 = shfl(v2,
✓ ✓ ✓ ✓ v5 = ↓v4 v5 1 3 4 0 ✓ ✓ ✓ ✓ v6 = v5 + 1 v6 2 4 5 1 ✓ ✓ ✓ ✓ ↑v4 = v6 ✓ ✓ ✓ ✓ Next v8 = v8 + 1 v8 4 4 4 4 ✓ ✓ ✓ ✓ v7 = (v8 == 4) v7 1 1 1 1 ✓ ✓ ✓ ✓ bz v7, Loop F F F F ✓ ✓ ✓ ✓ end_everywhere ✓ • • ✓ ↑tid = 1 ✓ • • ✓ Done sync ✓ ✓ ✓ ✓
Tid Tid Figure 7. Execution trace of the program in Figure 6.

Column Var shows contents of last variable assigned. T indicates branch taken; F indicates otherwise. The symbol • marks inactive threads. For the syntax of instructions, we refer the reader to Fig. 1; for their semantics, Figs. 4 and Algorithm 5 generates code that implements data distribution. Data distribution determines how actual parameters are bound to formal parameters, given that actual parameters can have one of two types: uniform or varying. By construction, r-functions have only uniform parameters. The loop in line 4 will go over all the function arguments, comparing formal (p) and actual (a) parameters. We let the type of a i be t i . If an actual argument is uniform, then parameter passing is trivially implemented as a copy between variables. Line 5 of Algorithm 5 generates code under such circumstance. If an actual parameter has type varying, then we generate code to perform a broadcast, as seen in line 7 of Algorithm 5.

Example 3.3

The program in Figure 9 shows three functions called via crev. We are assuming an architecture with four SIMD lanes, i.e., Θ all = {T 0 , T 1 , T 2 , T 3 }. When foo is invoked, the value of a, main's local variable, is broadcasted to foo's formal parameter. Thus, T 0 sees foo(0), T 1 sees foo(1), etc. When T 0 calls bar from foo, the same behavior is observed. However, when T 0 calls baz from bar, all the four threads activated into this context see baz(2), because baz receives a uniform argument. The fact that baz's local variable d is marked as varying is immaterial in this example, as this variable is initialized with uniform values.

Properties of CREV

The semantics of CREV, given by µ-SIMD's primitive building blocks, and the translator seen in Section 3.3, lets us establish a few properties that are true about this programming abstraction. In this section we go over a few of these properties. They are valid under the assumption that programs are well-formed. We define well-formed programs below: Definition 3.4 (Well-Formed Program) A µ-SIMD program is well-formed if any occurrence of an everywhere instruction at label l 1 is matched by an occurrence of an end everywhere instruction at label l 2 , and these two labels are control equivalent. Definition 3.4 borrows the concept of control equivalence from Ferrante et al. [START_REF] Ferrante | The program dependence graph and its use in optimization[END_REF]. Two points, l 1 and l 2 , in a program's control flow graph are said to be control equivalent if l 1 dominates l 2 , and l 2 post-dominates l 1 . We say that l 1 dominates l 2 if, and only if, any path from the root of the CFG to l 2 must cross l 1 . Dually, l 2 post-dominates l 1 if, and only if, any path from l 1 to the end of the CFG must cross l 2 . Our translator produces well-formed programs, as long as the program flow cannot leave a function through points other than its return address. Proof: This result follows trivially from the fact that an everywhere block surrounds only Algorithm 5 and the r-function. Well-formedness holds as long as none of these routines let the program flow escape the enclosing end everywhere instruction. This implies that the rfunction cannot throw exceptions, for instance.

Composability. CREV allows the nesting of everywhere blocks. Composition happens due to nested function calls. The thread stack Λ ensures that the last invoked r-function will be the first to remove pending computation. In what follows, we visit three consequences of this property. Composition is multiplicative. An crev call will put all the warp threads in active mode. By coupling this observation with composibility, we have that, in the absence of divergences, a sequence of n nested crev calls will create |Θ all | N tasks. Notice that CREV produces new tasks, but not new threads: we still have only |Θ all | threads to solve these tasks. Commutativity. The translator of Figure 8 calls an rfunction in a lexicographic order defined by thread identifiers. However, µ-SIMD's primitives do not impose any order on the threads pushed onto Λ. Therefore, the multiple SIMD calls of an r-function can be handled in any order. Synchronization parity. There is no distinction between the top level of parallelism and the inner level of parallelism with regards to the synchronization primitive. In other words, divergences are handled transparently by the synchronization stack Π, and, from a synchronization standpoint, it is not possible to tell if execution exists within the context of an r-function or not. To ensure this property, µ-SIMD's everywhere instruction pushes onto Λ, together with the set of active threads, the divergent state Π.

The interplay between CREV and nested function calls.

The implementation of CREV does not interfere with the implementation of function calls. Programming languages that support recursion use a structure known as activation stack to manage function calls. Entries in the activation stack are called activation records, and they store functions' local variables, return address, arguments, etc. Upon invocation, the activation record of a function is pushed onto the activation stack. For each thread pushed onto the thread stack there will exist one activation record on the activation stack. The multiplicative nature of CREV also implies on a multiplication of activation records. Therefore, n nested r-calls will generate |Θ all | n activation records; however, the maximum depth of the activation stack is still n + 1: activation records owned by different threads will not exist simultaneously.

Evaluation

To evaluate the ideas presented in this paper, we have implemented CREV on ISPC. We use this implementation to demonstrate that CREV allies the efficiency of warp synchronous programming with the clarity and elegance of dy-namic parallelism; hence, avoiding the complexity of the former, and the heavy scheduling cost of the latter.

Experimental Setup. Because CREV is a novel concept within ISPC, this compilation framework does not provide benchmarks that use it. Thus, we have re-implemented seven classic algorithms using the new keyword crev. Our seven benchmarks are: (bk) Book Filter (Algorithm 1); (sm) String Matching; (bf) Bellman-Ford [START_REF] Bellman | On a routing problem[END_REF]; (df) Depth-First Search;

(le) Leader Election; (qs) quick-sort; and (ms) merge-sort. Runtime Environment. We have implemented CREV onto ISPC v 1.9.1, and have used it to target a 6-core 2.00 GHz Intel Xeon E5-2620 CPU with 8-wide AVX vector units, running Linux Ubuntu 12.04 3.2.0. This running environment gives us warps with eight threads, e.g., |Θ all | = 8. The Competing Approaches. We compare four different ways to implement our benchmarks.

• Seq: serial implementation of each algorithm, as defined in Cormen's book [START_REF] Cormen | Introduction to Algorithms[END_REF]. String-matching was implemented after the Knuth-Morris-Pratt (KMP) [START_REF] Knuth | Fast pattern matching in strings[END_REF] algorithm. • Par: warp synchronous implementation using constructs available in the ISPC language, but without CREV. • Launch: dynamic parallelism, implemented via the launch keyword, which starts a new PThread per function call. • CREV: the implementation of the algorithms using the ideas introduced in this paper. The Seq version of each benchmark is implemented in C++, and is compiled with clang version 3.7.1, with the optimization flags -O2/-std=c++11. Benchmarks in the other three categories (Par, Launch and CREV) are compiled with ISPC. The Launch and CREV implementations look the same, except for the keyword that precedes function calls: launch in the first case, and crev in the second. The implementations in the Par group are different: they do not contain function calls within divergent regions, to ensure correctness.

Implementations are not available for all the programs. Even though it is trivial to implement quick-sort or mergesort with dynamic parallelism or with CREV, the craft of a warp synchronous implementation of them is not obvious; hence, we omit them. Additionally, we omit a sequential implementation of book filter, because this problem does not have a canonical, textbook-like, solution. Notice, however, that this algorithm reuses two r-functions: string match (sm), and memcpy (Algorithm 2). Thus, we show results for sequential string matching, but not for sequential book filter. How to read our results. Results are measured in millions of execution cycles, as reported by ISPC's testing environment. Numbers are the average of five, out of six samples. We have removed the first, to avoid cold-start discrepancies. The reader must bear four observations in mind, when analyzing our results: (i) speedups of CREV over pure ISPC (Par) are due to the better load distribution that CREV accomplishes by transporting work to inactive threads; (ii) the large slowdowns observed with Launch are due to the heavy cost of scheduling millions of new Posix threads to perform small chunks of work. (iii) CREV's slowdowns are due to the boilerplate code necessary to serialize threads, before invoking r-functions; (iv) we are comparing against an industrialstrength compiler; hence, speedups tend to be modest.

Results and Discussion

Figure 11 summarizes our results. The table shows runtime, measured as number of execution cycles (in millions), for all the implementations that we have of the seven different benchmarks. These numbers are produced with the largest inputs that we have for each benchmark:

• bk: 10K strings of 0s and 1s, each with 20K bits, and random target pattern with 16 bits. • sm: 256MB taken from books available in the Project Gutenberg, and a target pattern with 16 characters. • bf: random Erdös-Rényi [START_REF] Erdos | On random graphs[END_REF] graph with 2,048 nodes and 80% edge probability. • df,le: 8-ary complete tree, depth 5 (root + five full levels).

• qs,ms: 16K random integers in the range [0, 100000).

Figure 11 shows that ISPC, with or without CREV, is competitive against mainstream compilers: Seq is the best C implementation that we could produce of each algorithm; furthermore, these programs are compiled with clang -O2 (which was faster than clang -O3 in this experiment). Nevertheless, CREV and Par outperform these implementations in several cases, although they are not embarrassingly parallel. The table also reveals that Launch is sometimes orders of magnitude slower than the other approaches, being the fastest in only one case: bk. In bf and df, the excessive number of threads created by Launch forced earlier termination.

CREV usually outperforms Par by a small margin. However, the main benefit of the former over the latter is not performance. Rather, it is readability. The Launch and the CREV versions of each benchmark are exactly the same, except that whereas in one case we prepend the call of functions with the launch keywork, in the other we use crev. On the other hand, the Par implementations are very different, because they cannot call functions within potentially divergent regions. To circumvent this restriction, the five Par benchmarks forgo recursion. As an example, the ISPC ver-sion of depth-first search uses a stack of tasks, instead of performing recursive functions to traverse the graph. As another example, Algorithm 6 shows the CREVbased implementation of string matching. This is a warpsynchronous implementation of parallel matching: each thread t id tries to match P at positions

T [t id + n × W ],
where n ≤ |T |, and W is the warp size. Thus, in the best scenario, runtime is divided by W . This implementation is irregular: divergences might happen at lines 6 and 10. Each call to memcmp 4 will commence a CREV sequence of computations. Figure 12 compares our implementation, seen in Algorithm 6 (StringMatch) against the equivalent Par version, which does not perform any function call.

The Impact of Data on Runtime. The numbers seen in Figure 11 are input dependent. However, the overall conclusions remain the same, once we feed our benchmarks with inputs of different sizes. Figure 12 For this experiment, we searched for prefixes of the pattern "She had been watching him the la", of sizes 4, 8, . . . , 28, 32 in Jane Austen's book Pride and Prejudice, taken from Project Gutenberg 5 . CREV is always faster than ParStringMatch, and runs faster than KMP in more than half the cases. CREV beats plain parallelism because it distributes function memcmp among the eight available vector lanes. On the other hand, ParStringMatch has a potentially long divergent block in line 14. In our best result, observed for pat- 4 Function memcmp is also used at line 5 of Algorithm 1 5 https://www.gutenberg.org/ebooks/42671 Figure 12 (Bottom) shows a comparison between the four implementations of leader-election. Dynamic parallelism is still the slowest, overall; however, we notice that it tends to catch up with the other approaches for very large inputs, in this benchmark. This behavior is expected: if the amount of parallel work is large, then the greater flexibility and independence of pthreads start paying for the cost of creating them. Nevertheless, depending on how the algorithm is implemented, dynamic parallelism might lead to the creation of a very large number of threads, as the size of the input grows. Due to this observation, we have not been able to run the Launch versions of df and bf for the largest available inputs. On the other hand, in the case of leader-election (le), parallelism is coarser: each thread receives the task of finding strong components in a graph. Thus, even though the number of threads grows as the size of the input increases, this growth is less accentuated than in df and bf.

Related Work

GPUs' increasing programmability and decreasing costs have made them very popular for the development of general purpose high performance applications [START_REF] Nickolls | The GPU computing era[END_REF]. This popularity has attracted the interest of programming language researchers. Control flow divergences have been a particularly important source of attention. Therefore, the compiler-related literature contains a vast body of work describing analyses [START_REF] Coutinho | Divergence analysis and optimizations[END_REF][START_REF] Sampaio | Divergence analysis with affine constraints[END_REF][START_REF] Sampaio | Divergence analysis[END_REF][START_REF] Schaub | The impact of the simd width on control-flow and memory divergence[END_REF] and optimizations [START_REF] Coutinho | Divergence analysis and optimizations[END_REF][START_REF] Coutinho | Profiling divergences in GPU applications[END_REF][START_REF] Wu | Gpucc: An open-source gpgpu compiler[END_REF][START_REF] Zhang | On-thefly elimination of dynamic irregularities for GPU computing[END_REF] that reduce the effects of divergences in GPGPU code. CREV is not a competitor of these analyses and optimizations. On the contrary, Call Re-Vectorization complements such techniques, giving programmers a tool that lets them deal with divergences at the software level. In the rest of this section we touch work that is more closely related to ours. Everywhere Blocks. The problem of expressing nested SIMD loops in multi-thread style is not new. Some dataparallel programming languages for SIMD computers in the 80's and 90's allow to re-enable temporarily dormant threads. The C* language [START_REF] Rose | C*: An extended C language for data parallel programming[END_REF], the Maspar Programming Language [START_REF] Maspar | MasPar Programming Language (ANSI C compatible MPL) Reference Manual[END_REF] and the POMPC language [START_REF] Hoogvorst | POMP or how to design a massively parallel machine with small developments[END_REF] incorporate a control flow construct named either everywhere or all to this end. We have re-used these instructions to implement CREV. However, these are low-level primitives: they are not programmer-friendly, nor have any interface with function calls. Using everywhere directly is difficult, as this abstraction has no knowledge nor control over the state of dormant threads. CREV, on the contrary, is as easy to use as dynamic parallelism. It manages register saves and restores automatically, relieving the programmer from this task. Warp-level convergence guarantees. Previous work enforce guarantees on where threads converge after control divergences to make warp-synchronous programming safer. For instance, Pharr et al. have proposed the maximal convergence guarantee [START_REF] Pharr | ISPC: A SPMD compiler for highperformance CPU programming[END_REF], and Gaster has proposed a divergenceaware execution model for OpenCL [START_REF] Gaster | An execution model for OpenCL 2[END_REF]. CREV goes further by actually enforcing convergence at arbitrary program points, allowing warp-synchronous functions to be called from divergent sections. To the best of our knowledge, this is the first attempt to provide developers with such possibility. Grid-level Dynamic Parallelism. Much effort has been spent to reduce the overhead of dynamic parallelism. Alternatives to CUDA Dynamic Parallelism such as DTBL [START_REF] Wang | Dynamic thread block launch: A lightweight execution mechanism to support irregular applications on gpus[END_REF], Free Launch [START_REF] Chen | Free launch: optimizing GPU dynamic kernel launches through thread reuse[END_REF] and LaPerm [START_REF] Wang | LaPerm: Locality aware scheduler for dynamic parallelism on GPUs[END_REF] reduce sub-kernel launch overhead or improve cache locality. By relying on global schedulers, they allow load-balancing between GPU stream multiprocessors. We are not competing with these efforts, because CREV is not an alternative to dynamic parallelism. CREV is a static code transformation with no dynamic scheduling; hence, it does not create extra parallelism. In other words, we move work to threads that are already in flight, instead of spawning new threads. The main benefit of CREV, when compared to these previous work comes in terms of programmability and efficiency: by supporting composability of multi-thread and SIMD code, we give developers the chance to benefit from efficient warpsynchronous idioms without neither having to deal with primitives like shuffle, vote and population count, nor having to worry about saving the context of threads. Thread-level divergence aware optimizations. Compilers may reorder computations across loop iterations within each thread to mitigate branch divergence [START_REF] Coutinho | Divergence analysis and optimizations[END_REF][START_REF] Han | Reducing divergence in GPGPU programs with loop merging[END_REF][START_REF] Khorasani | Efficient warp execution in presence of divergence with collaborative context collection[END_REF][START_REF] Novak | Loop optimization for divergence reduction on GPUs with SIMT architecture[END_REF]. However, each thread performs the same set of tasks as in the original version, so divergences induced by load unbalance between threads of a warp remains an issue. CREV is a way to deal with irregular programs whose performance divergences hurt. However, CREV is not an optimization implemented by the compiler: programmers must adapt algorithms to use this construct. CREV deals well with divergences because it lets developers balance workload between threads in flight. In other words, it changes the loop structure by distributing iterations across different threads.

Final Thoughts

Primitives such as warp vote and shuffle have given experts the possibility of writing efficient SIMD code, by programming from the point of view of one warp. This coding style has been used in CUB and many other CUDA libraries 6 . However, warp-synchronous code does not play well with branch divergence. Most warp-synchronous algorithms require all threads in a warp to be active. This is a problem for the common usage scenario of a simple MT-style CUDA kernel that calls warp-synchronous library functions. It is our vision that the application developer writing the kernel should not be concerned with the internal implementation of library functions, and should be able to call any function inside divergent program regions. To meet the demands of this vision, this paper has introduced the notion of Call Re-Vectorization(CREV). We have described the building blocks necessary to implement CREV. Looking towards compatibility with future hardware, we have proposed lowlevel primitives with well-defined semantics and a high-level interface, the crev idiom, that makes programmer intent explicit. Thus, our notion of CREV does not rely implicitly on current hardware behavior, which might eventually change. We have implemented CREV into ISPC, using Intel instructions, and have shown how to code irregular algorithms in this environment. Our implementations are not only clearer than non-CREV based approaches, but also more efficient, as they balance work among inactive warp threads.

Algorithm 2 :

 2 Warp synchronous memcpy 1 W ← warp size; t id ← thread index; 2 Function memcpy shfl(vec s, vec d, int N ) 3 for j ← 0 to W -1 do 4 dmy ← shfl(d, j); 5 smy ← shfl(s, j);

6

 6

Figure 2 .

 2 Figure 2. The state of µ-SIMD machine is a septuple M (Θ, β, Σ, Π, Λ, P, pc). Θ is the set of active threads. A thread t ∈ Θ has a local memory σ, accessible through a memory bank β. Threads communicate through shared memory Σ. The stack Π tracks control flow divergences. A key component of Call Re-Vectorization is the thread stack Λ. The program counter, pc, keeps track of the next instruction ι ∈ P to be executed. The program P is a linear sequence of instructions. Although it never changes, we include it as state for convenience.

Figure 4 .

 4 Figure 4. Semantics of µ-SIMD's control flow instructions.

Figure 9 .

 9 Figure 9. A program written in ISPC, and the tree showing function calls for T 0 .

Theorem 3 . 5 (

 35 Well-Formed Translation) The translator of Figure8produces well-formed programs.

2 ProgramFigure 10 .

 210 Figure 10. Example of three nested calls to r-functions. Calls currently in the activation stack are highlighted.

Example 3 . 6

 36 Figure 10 reuse the program from Example 3.3 to illustrate these points. Again, we assume |Θ all | = 4. Thus, three non-divergent nested r-calls will create 4 × 4 × 4 × 4 = 256 tasks. At any time, the thread stack will contain at most 4+4+4+4 = 16 tasks waiting for execution. The activation stack will contain, at any given point, at most 4 activation records, corresponding to the activation of functions main, foo, bar and baz.

Algorithm 6 : 4 m

 64 Pattern matching: CREV vs. Naïve 1 P ← pattern; T ← target text; 2 W ← warp size; t id ← thread index; 3 Function memcmp(Offset k) ← True;5 for i ← t id to |P | do 6 if P [i] = T [i + k] then m ← False ;7 if all (m = True) then Found(k) ; 8 Function StringMatch 9 for i ← t id to (|T | -|P |) step W do 10 if P [0] = T [i] then crev memcmp(i) ; 11 Function ParStringMatch 12 for i ← t id to (|T | -|P |) step W do 13 j ← 0; k ← i; 14 while j < |P | and P [j] = T [k] do 15 j ← j + 1; k ← k + 1; 16 if j = |P | then Found(k) ;

  compares the runtime different implementations of string-matching and leader election. In string-matching, we omitted the Launch-based version, as it was too slow. Notice that KMP has lower asymptotic complexity than Algorithm 6. It runs in O(|T | + |P |), whereas Algorithm 6 runs in O(|T | × |P |/|W |).

Figure 12 .

 12 Figure 12. (Top) String-Matching. X-axis shows pattern sizes, in number of characters. Target text contains 256MB divided among 5,058,121 lines. (Bottom) Leader-Election. X-axis shows graph size, in number of edges. In both charts, Y-axis shows runtime, in millions of cycles. Boxes show percentage of speedup: white is CREV over Par; grey is CREV over Seq, and black is CREV over Launch.

  Auxiliar functions used to define µ-SIMD. split is a filter, dividing threads into two divergent sets (Θ 0 and Θ n ). Auxiliary function push updates the synchronization stack Π due to control flow divergences.

Operational Semantics. The state M of a program is a tuple (Θ, β, Σ, Π, Λ, P, pc), as described in Figure

2

. Threads are uniquely identified by a natural t id , having a local memory β[t id ], and sharing a global memory Σ. Memory is vectorized, thus, a local address v denotes a vector of variables v ∈ β[t id ]; hence, each thread sees its private version of v.

  Program written in µ-SIMD, plus its initial state. arbitrary number of nested everywhere blocks. After executing the instruction end everywhere, threads previously inactive will go back into sleeping mode. In other words, after end everywhere, the pair (Θ, Π) at the top of Λ is popped, and the diverging configuration Π becomes part of the current state of threads. If necessary to check if a thread is active due to an everywhere block, then µ-SIMD provides a conditinal jmp mask. The statement jmp mask(t id , l) will divert execution to l if t id is active in the mask at Λ's top. Example 3.2 illustrates the behavior of these instructions.

				Shared Memory
		Done	Address	4	5	6	7
		v2 = 4 * (tid + 1)	Contents	2	1	3	4
		everywhere	Address	8	9	10	11
		v8 = 0	Contents	1	5	6	1
	Loop jmp_mask v8, Call	Address	12	13	14	15
		jmp Next	Contents	2	3	1	7
	Call	v3 = shfl(v2, v8)	Address	16	17	18	19
		v4 = v3 + tid	Contents	1	3	4	0
		v5 = ↓v4
		v6 = v5 + 1
		↑v4 = v6		Private Memory
	Next v8 = v8 + 1	Address v0	v1	v2	v3
		v7 = (v8 == 4)	Contents *	*	*	*
		bz v7, Loop	Address v4	v5	v6	v7
		end_everywhere	Contents *	*	*	*
		↑tid = 1	Address v8
	Done sync	Contents *
	Figure 6.

Example 3.2 Figure 6 shows a program written in µ-SIMD. We assume |Θ all | = 4. This program increments a 4 × 4 matrix; however, line i is incremented only if Σ[t id ] = 0. The figure shows the initial state of the shared (Σ) and local memory of each thread (σ). The initial state of the variables in the local memory is immaterial for this example.

  5.

	1	everywhere	; ; begin CREV
	2	i = 0	; ; Loop counter
	3 loop : jmp mask i, call
	4	jmp next	; ; Skip idle threads
	5 call : extract(t n , p n , a n , i) ; ; Algorithm 5
	6	"call" f	; ; function call
	7 next : i = i + 1
	8	bnz(i = W ) loop
	9	end everywhere	; ; end CREV
	Figure 8. Low-level code produced to call r-function f .

invocation performed by each thread. A different call will happen due to each handle t label. In another dimension of parallelism, each function call will be executed by Θ all threads, due to the everywhere block at lines 10 and 13. Thus, we might have up to Θ 2 all computations.

Algorithm 5: Data distribution 1 Function declaration: f (p 1 , . . . , p n ); 2 Function call: f (t 1 a 1 , . . . , t n a n ); 3 Function extract(t n , p n , a n , i) 4 for k ∈ 1 . . . n do 5 if t k == uniform then 6 p k = a k ; 7 if t k == varying then 8 shfl(a k , i);

  Execution time, in millions of cycles. We use × to indicate that the implementation of a benchmark is not available, and • to indicate that the implementation of the benchmark does not run successfully until completion.

	Pg	Seq	Par	Launch	CREV
	bk	×	8,530.99	7,857.98	7,405.17
	sm	6,649.28	3,576.14 393,166.27	2,737.94
	bf	141,088.73 493,619.69	• 529,856.06
	df	3,754.10	3,786.26	•	3,790.44
	le	4,054.66	3,983.09	5,272.92	3,984.79
	qs	2.87	×	204.28	2.87
	ms	7.30	×	104.98	4.11
	Figure 11.

We shall call groups of threads that execute in lock-step a warp.

Ex.: see Trove at https://github.com/bryancatanzaro/trove.

The Intel SPMD Program Compiler (ISPC) is available at https:// github.com/ispc/

See https://nvlabs.github.io/cub/

Acknowledgement

This project is supported by the Inria-Fapemig Associate Team Prospiel and by CNPq. We thank the members of the Dragon Nest group and the PPoPP referees for their insightful comments and suggestions. Example 3.1 has been suggested by one of the referees. Finally, we thank Albert Cohen for shepherding this paper. Our implementation is publicly available at http://cuda.dcc.ufmg.br/swan/.


Romain Pinquié
email: romain.pinquie@ensam.eu

Philippe Véron
email: philippe.veron@ensam.eu

Frédéric Segonds
email: frederic.segonds@ensam.eu

Nicolas Croué
email: nicolas.croue@keonys.com

A Collaborative Requirement-Mining Framework to Support OEMs

Keywords: Requirements, exploration, cooperative engineering, collaborative decision making, visual analytics, framework

With the fastidiously ever-increasing complexity of systems, the relentless, massive customisation of products and the mushrooming accumulation of legal documents (standards, policies and laws), we observe a significant increase in requirements. We consider the tremendous volume of requirements as big data with which companies struggle to make strategic decisions early on. This paper suggests a collaborative requirement-mining framework to enable the decision-makers of an Original Equipment Manufacturer (OEM) to gain insight and discover opportunities in a massive set of requirements so as to make early effective strategic decisions. The framework supports OEMs willing to distil a subset of key requirements from large unstructured and semi-structured specifications.

Introduction

The development of complex systems prompts organisations to build partnerships to pool knowledge and resources and to share risks.

Within the supply chain, a stakeholder is either a system integrator 4 or an Original Equipment Manufacturer (OEM) 5 . Nonetheless, any stakeholder at tier N can, in turn, be an integrator of OEMs' subsystems developed at tier N-1, and an OEM that provides a subsystem to an integrator at tier N+1.

The development of a system-of-interest starts with the requirements development phase from the integrator's point of view. Requirements analysts elicit hundreds or thousands of requirements to specify the design, manufacturing, use, maintenance and disposal of a complex system-of-interest. For instance, at Mercedes-Benz, the size of a system-of-interest specification varies from 60 to 2000 pages and prescribes between 1000 and 50 000 requirements [START_REF] Houdek | Managing large scale specification projects[END_REF]. Once the system-of-interest is fully specified, systems architects develop functional and physical architectural alternatives. As soon as architects have committed themselves to one preferred architecture, requirements analysts apportion the performance requirements of the current hierarchical level to the functions of the next lower level. This recursive decomposition process, which aims at simplifying the problem to be solved, results in various Stakeholder Requirements Specifications (StRSs) 6 whose implementations require domain-specific knowledge from various OEMs. Therefore, an OEM is the one that takes over all the requirements of a given subsystem.

In its Chaos Manifesto report [START_REF] Standish | Chaos manifesto report[END_REF], the Standish Group points out that there is never enough time or money to do everything. Thus, the report argues that focusing on the 20% of the features and functions that give organisations 80% of the value will maximise the investment and improve overall user satisfaction. It is therefore strongly recommended to reduce the scope and spend more time focusing on high-value requirements rather than completing 100% of the requirements. Such a strategy is in the news since the report indicates that the features and functions developed went down, with 74% of the specified requirements completed in 2010, dropping to 69% in 2012. However, as [START_REF] Sawyer | REVERE: support for requirements synthesis from documents[END_REF] [START_REF] Sawyer | REVERE: support for requirements synthesis from documents[END_REF] state, there is no tool that supports the OEMs willing to adopt such a strategy. Hence, so far, when an OEM collects the StRS and the applicable documents the StRS refers to, it has no other alternative than go through the documents to identify and prioritise a subset of key requirements.

Literature review & Proposition

Related work

An up-to-date literature review of the existing visual requirements analytics 7frameworks can be found in Reddivari et al. [START_REF] Reddivari | Visual requirements analytics: a framework and case study[END_REF] and Cooper et al. [START_REF] Cooper | Requirements engineering visualization: a survey on the state-of-the-art[END_REF]. Coatanéa et al. [START_REF] Coatanéa | Requirements models for engineering, procurement and interoperability: a graph and power laws vision of requirements engineering[END_REF] and Lash [START_REF] Lash | Computational representation of linguistics semantics for requirements analysis in engineering design[END_REF] extract requirements and relationships from unstructured specifications. Zeni et al. [START_REF] Zeni | GaiusT: supporting the extraction of rights and obligations for regulatory compliance[END_REF] propose GaiuST, a framework that supports the extraction of legal requirements for regulatory compliance. Few articles broach the topic of contradictions in natural language [START_REF] Coatanéa | Requirements models for engineering, procurement and interoperability: a graph and power laws vision of requirements engineering[END_REF][START_REF] De Marneffe | Finding contradictions in text[END_REF]. However, much research attempt to diagnose quality defects by using NLP and text mining techniques [START_REF] Carlson | The NASA automated requirements measuring tool: a reconstruction[END_REF][START_REF] Christophe | A methodology supporting syntactic, lexical and semantic clarification of requirements in systems engineering[END_REF][START_REF] Génova | A framework to measure and improve the quality of textual requirements[END_REF][START_REF] Kiyavitskaya | Requirements for tools for ambiguity identification and measurement in natural language requirements specifications[END_REF][START_REF] Körner | Natural language specification improvement with ontologies[END_REF][START_REF] Lamar | Linguistic analysis of natural language engineering requirements[END_REF][START_REF] Yang | Analysing anaphoric ambiguity in natural language requirements[END_REF]. Recent work has been done to classify requirements thanks to machine learning [START_REF] Knauss | Semi-) automatic categorization of natural language requirements[END_REF] or linguistics analysis [START_REF] Lamar | Linguistic analysis of natural language engineering requirements[END_REF]. Zhang et al. [START_REF] Zhang | A prescriptive approach to qualify and quantify customer value for value-based requirements engineering[END_REF] suggest an approach to qualify and quantify customer value for value-based requirements engineering. Numerous requirements prioritisation techniques, which are reviewed in [START_REF] Achimugu | A systematic literature review of software requirements prioritization research[END_REF], have been developed to rank requirements. Finally, there is an stimulating interest to use recommendation systems in requirements engineering [START_REF] Felfernig | An overview of recommender systems in requirements engineering[END_REF].

Limitations of existing solutions

In current commercial requirements engineering software can be divided into four main categories: (1) the everlasting document-based specifications (e.g. Word, Excel, PDF) that are easy to use and cheap; (2) the centralised database-based specifications (e.g. Rational DOORS8 , ENOVIA V6 Requirements Central9 ) that ease collaboration and configuration management; the model-based systems engineering specifications (e.g. SysML) that offer new elements such as relationships between requirements; and (4) the requirements editors and analysers that assist analysts with ensuring the quality of requirements (e.g. The Requirements Quality Suite10 ).

Feedback from industrialists reveals that these technologies benefit the systems integrators whose main tasks are requirements writing and management, but they do not help the OEMs willing to distil a large set of requirements. Such requirements management tools require the definition of an inflexible, welldefined data model before starting a new project. Moreover, they do not offer any contextual view of the requirements and their interdependencies, but only offer a graphical table that imitates the form of a spreadsheet. We can also notice that requirements analysis tools mainly focus on the processing task, but provide very limited visual analytics capabilities. Conversely, visual analytics solutions concentrate on the depiction of requirements' features without including advanced processing capabilities. Finally, current solutions do not provide any statistical capabilities that may help identify patterns in a large set of requirements.

This literature review prompts us to claim that there is an urgent need to imagine a framework that supports OEMs willing to distil a large set of requirements by integrating advanced computational capabilities with visual analytics.

Proposition

We propose a collaborative requirement-mining framework that addresses the problem of an OEM receiving a request for proposal consisting in a StRS and the referenced applicable documents, all of them prescribing a massive set of requirements that cannot be implemented within cost and schedule constraints.

The mission of the framework is to support the business analysts willing to distil a large set of requirements, that is, to create an optimised Sytem Requirements Specification (SyRS) that is ready to be managed in configuration thanks to requirements management tools. By using the "distil" we mean to get and show only the most important part of a large set of requirements. We qualify the SyRS as optimised because it is the result of the distilling process that only retains a subset of key requirements including:

-legal requirements: non negotiable requirements that are required for regulatory compliance.

-basic requirements: non negotiable requirements without which no one would buy the product. -added-value requirements: negotiable requirements corresponding to key product differentiators. Fig. 1 illustrates the operational scenario that we propose to answer the question "What is the subset of key requirements to be implemented?". First of all, for a given project, the project manager places the unstructured and semistructured documents corresponding to the StRS and the applicable documents into a common repository. Then, the operational scenario is as follows:

1. Extract explicitly stated attributes (e.g. original author, version, statement, original document source title, etc.) that make up each requirement and relationship from unstructured and semi-structured specifications. We use an attribute scheme to structure each requirement as a set of attributes so as to be compliant with the meta-model of the standardised Requirements Interchange Format (ReqIF) 11 . 2. Infer implicit requirements attributes, such as the business category (e.g. mechanics, electronics, I&T, marketing, safety, etc.), the functional vs. nonfunctional category, the textual cross-references to the referenced applicable prescriptive documents (e.g. The system shall comply with standard CS.25 ). Implicit relationships such as the linguistic interdependencies (e.g. synonymy, hypernymy, hyponymy, etc.) among the requirements keywords, the potential redundancies and contradictions, and the occurrence of proscribed terms can also be created.

3. Model the requirements and the relationships as a property graph data model into a graph database. 4. Visualise the requirements and the relationships from different perspectives enabling contextual and multidimensional exploration of the attributes through interactive functionalities. Users can interact with visualisation thanks to the classic CRUD 12 operations, and save changes to the database. When the data set is updated by saving changes in the database, the processing tasks have to be restarted to update the data model and the visualisations. So far we have identified five interactive visualisations:

-Quality view: highlights the quality defects that are not only inherent to a requirement statement (e.g. ambiguities, incompleteness, etc.), but also among a set of requirements (e.g. redundancies and contradictions). -Cross-references view: illustrates the interdependencies among the StRS and the referenced applicable documents. -Survey view: helps the domain-experts to retrieve the requirements that are relevant to their profile so as to estimate various decision-making criteria (e.g. cost, time, risks, quality, etc.). -Decision making view: supports analysts for uncovering unanticipated patterns in the dataset resulting from a statistical analysis of the decision-making criteria estimated by domain-experts in the survey view. -Configuration management view: depicts the history of changes (created, modified and deleted requirements and relations). 5. Capitalise the information and the strategic decisions made by the business analysts by keeping an historical record of subsequent projects. 6. Export into a ReqIF compliant XML data file the subset of key requirements that will be managed in configuration throughout the downstream system's life cycle phases thanks to requirements management tools. 7. Reuse the capitalised information throughout the entire synthesis process whenever a new specification is added in the repository or whenever a new set of specifications corresponding to a new request for proposal is received.

In the next sections we introduce the framework according to two perspectives: functional -WHAT functions need to be performed to fulfil the mission? -, and software -HOW shall the framework accomplish the required functions?

3 The collaborative requirement-mining framework

Functions of the framework -"WHAT"

In this section we present a Functional Flow Block Diagram (see Fig. 2) that not only defines the functions that the framework must perform to fulfil its mission, but also depicts their logical, sequential relationship, as well as what flow goes in and out of each function. It is the definition of "what" the framework must do without assuming a particular answer to how the functions will be performed. The first step consists in extracting the explicit attributes that make up each requirement (F1 and F2). For unstructured specifications (F1), attributes include a unique identifier for each requirement, the metadata corresponding to the author and version of each specification, as well as the statement of each requirement. For semi-structured specifications (F2) such as SysML requirements diagrams saved as an XML file, we only extract the statement attribute and the "derive" relationship elements. Then, the requirement statements are processed to extract the textual cross-references that refer to applicable documents (F3) from which the software extracts additional requirements. Legal requirements have to be highlighted (F5) in a visualisation because they are non-negotiable key requirements. It is therefore necessary to find a solution to distinguish legal requirements from non-legal requirements. Once all requirements have been extracted, a diagnosis (F6, F7 and F8) is launched to identify quality defects (e.g. contradictions and redundancies, ambiguities, etc.) to avoid over-specification with unnecessary requirements and misinterpretations during the survey phase. The cleaning of requirements defects requires another visualisation, the quality view, to illustrate contextual potential redundancies and contradictions. Once cleaned, the requirements are used to infer implicit attributes such as the business (e.g. mechanics, IT, etc.) and functional vs. non functional categories (F12). Such classes ease the retrieval of requirements (F12) whose value needs to be estimated from the OEM (F14) and the integrator (F15) perspectives. The estimation of decision-making criteria results in either a basic requirement that is non negotiable from the integrator's point of view or a requirement that needs to be negotiated (F15). The negotiation phase can be approached as a constrained optimisation problem where integrator's constraints need to be weakened to find a solution belonging to the OEM's feasibility space that is maximum in value but that was originally outside of the scale of constraints [START_REF] Cheung | Application of value-driven design to commercial aero-engine systems[END_REF].

Implementation of the framework -"HOW"

In the previous section we detailed what functions the framework must perform to fulfil its mission. Now we shall explain how the functions can be implemented.

To extract the textual content and the metadata we use a specific parser according to the extension of the uploaded StRS. The parser Apache Tika 13for .doc (Word), .odf (OpenOffice) and .pdf; the parser Apache POI 14 for .xls (Excel) and to extract figures that potentially are graphical requirements; and a simple XML parser (JDOM 15 ) for SysML requirement diagrams.

The Stanford CoreNLP16 toolkit offers a variety of natural language processing (NLP) functions such as tokenisation, sentence splitting, POS-tagging and lemmatisation allowing the identification of sentences. A binary knowledge engineering classifier classifies the sentences as requirements or non-requirements based on prescriptive word matching (shall, must, should, require, have to, need, want, desire, etc.) [START_REF] Sawyer | REVERE: support for requirements synthesis from documents[END_REF]. As previously explained, any XML parser can do the job for a semi-structured SysML specification. The extraction of textual cross-references to applicable documents is an information extraction problem. This challenge can be solved with a probabilistic sequence model that is either discriminative such as Conditional Random Fields (CRF) and Maximum Entropy Markov Models (MEMM), or discriminative such as Hidden Markov Models (HMM). Stanford CoreNLP and the Java library Mallet 17 embed the CRF algorithm. A feature function that takes in as input a requirement statement, the position i of a term in the current statement, the class of the current token, and the class of the previous token can be used to build a linear-chain CRF. By defining two classes, class A corresponding to strings consisting in a blend of a few capital letters and digits such as "ISO900" or "CS25" standing for prescriptive document titles, and class B corresponding to chunks usually used to refer to content in external documents such as "in accordance with", "as specified in", "as set out in", it is likely that a term belonging to class A in the sequence model will be a cross-reference given the fact that the previous term belongs to class B. In other words, if we find a chunk such as "as specified in" followed by a term that mixes a few capital letters and digits such as "CS25', then we infer that the second term is a reference to an external document. Once extracted, cross-references are displayed to require the user to upload the referred applicable documents which, in their turn, will be processed to extract the requirements they prescribe. While uploading the required applicable documents, the user can manually set a binary (legal vs. non-legal ) switch so as to specify whether it is a legal document. If it is set as a legal document, then the extracted requirements are classified as key legal requirements.

To diagnose quality defects (e.g. redundancies, contradictions, ambiguities) that pollute specifications and often lead to wrong decisions we use natural language processing techniques. To identify redundancies and contradictions we, at first, carry out a thesaurus-based lexical semantic disambiguation of keywords (nouns, verbs, adjectives and adverbs). The identification of the meaning of keywords enables us to reliably select a subset of similar requirements thanks to a sentence-level similarity function. Then, we use the POS-tagger of Stanford CoreNLP to find negations (e.g. no, not, not, 't, etc.) and numerical values (e.g. 40, 50) in the statements, and we look for the antonyms of each keyword by querying the thesaurus WordNet 18 . An analysis of the numerical dependencies in each requirement with the Stanford CoreNLP dependency analyser 19 enables us to only keep the statements that include digital values related to a physical dimension (e.g. 40 N or 50 K). With ad-hoc algorithms we build: (1) pairs of requirements that contain physical numerical values, (2) pairs of requirements with a negation and requirements without a negation, and (3) pairs of requirements whose keywords are antonyms. Finally, we combine the similarity function with these numerical, negation and antonymy pairs. If a pair of requirements has a similarity score that is higher than the threshold (e.g. 0.8), then there is potentially a contradiction or a redundancy. Such an approach boosts recall rather than accuracy. Interactive visualisation representing clusters of similar and potentially contradictory requirements facilitates the cleaning of quality defects. This interactive quality view also depicts all the defects due to the infringement of best practices (e.g. ambiguities, incompleteness, etc.) in requirement writing.

Well-defined requirements are the basis for inferring new implicit attributes that help a domain-expert to retrieve requirements that belong to his domain of expertise. One attribute is the business category (mechanical, IT, etc.) a given requirement belongs to. This attribute can be inferred with supervised statistical learning text categorisation algorithms. The Support Vector Machine (SVM) algorithm is usually recognised as the best algorithm for text categorisation. Furthermore, Knauss and Ott (2014) demonstrated that a semi-supervised SVM model outperforms a supervised approach [START_REF] Knauss | Semi-) automatic categorization of natural language requirements[END_REF]. However, instead of building a time-consuming training set with annotated requirements as was done in [START_REF] Knauss | Semi-) automatic categorization of natural language requirements[END_REF], we propose to train a multi-class SVM model with sentences from domain-specific (mechanics, electronics, etc.) dictionaries and handbooks. In addition, either a formal linguistic analysis implemented with the syntactic meta-language Backus-Naur Form (BNF) [START_REF] Lamar | Linguistic analysis of natural language engineering requirements[END_REF] or a supervised machine learning decision tree [START_REF] Hussain | Using linguistic knowledge to classify non-functional requirements in SRS documents[END_REF] can be implemented to infer another implicit attribute that categorises the statements as functional or non-functional. These attributes coupled with the Apache Lucene 20 search engine, and the visualisation of semantic relationships (synonyms, hypernyms, hyponyms, etc.) among requirements are functionalities of the survey view that enable domain experts to retrieve the most relevant requirements according to their profile during the estimation phase.

Once assessed, quantitative decision-making criteria can be analysed with principal component analysis, whereas qualitative variables can be analysed with multiple correspondence analysis. A decision-making view communicates the results of the statistical multivariate analysis by uncovering unanticipated interesting patterns in the data set. These patterns ease the identification of a subset of added-value requirements that motivate business analysts' decisions.

Conclusion and future work

In this paper, we have presented a collaborative requirement-mining framework that supports OEMs willing to distil a large set of requirements. Its computational capabilities and interactive visualisations should help analysts to gain insight and discover opportunities in a massive set of requirements. Computational capabilities include the automated extraction of requirements and relationships, the inference of implicit attributes, the analysis of requirements' quality, a statistical multivariate analysis, and the capitalisation and reuse of information and decisions made. On the other hand, five interactive means of visualisation should improve exploration through contextual views illustrating requirements and their interdependencies and multidimensional views depicting the numerous attributes that make up each requirement and relationship. Furthermore, the originality of this framework is to focus on the contractual phase that brings a system integrator and OEM(s) in one single collaborative digital environment.

The prototyping of a web application is under development. The MVC design pattern JSF 2 21 has been selected. The graph database Neo4j 22 has been chosen to store requirements and relationships in a property graph data model. The Object-Graph Mapping Spring Data Neo4j 23 makes it possible to work with annotated POJO entities. Finally, the JavaScript library D3.js 24 has been adopted to create the web-based interactive visualisations.

Fig. 1 .

 1 Fig. 1. An over-simplified operational scenario of the collaborative framework.

Fig. 2 .

 2 Fig. 2. A FFBD depicting the lowest abstraction level of the functional architecture.

An integrators is sometimes known an acquirer, a customer, a contractor or a contracting authority.

[START_REF] Reddivari | Visual requirements analytics: a framework and case study[END_REF] An OEMs are sometimes known as a subsystem provider, a subsystem supplier or a subcontractor.

One StRS for each system element.

Reddivari al.[START_REF] Reddivari | Visual requirements analytics: a framework and case study[END_REF] coined the term visual requirements analytics that is the use of visual analytics applied to requirements engineering. Visual analytics is "the science of analytical reasoning facilitated by interactive visual interfaces"[START_REF] Thomas | Illuminating the path: research and development agenda for visual analytics[END_REF]. .

http://www-03.ibm.com/software/products/fr/ratidoor

http://www.3ds.com/products-services/enovia/products/v6/portfolio/d/collaborativeinnovation/s/governance-user/p/requirements-central/

[START_REF] De Marneffe | Finding contradictions in text[END_REF] http://www.reusecompany.com/requirements-quality-suite

http://www.omg.org/spec/ReqIF/

Create, Read, Update and Delete.

https://tika.apache.org/

https://poi.apache.org/

http://www.jdom.org/

http://nlp.stanford.edu/software/corenlp.shtml

http://mallet.cs.umass.edu/

https://wordnet.princeton.edu/

http://nlp.stanford.edu/software/stanford-dependencies.shtml

https://lucene.apache.org/core/


Keywords: mobility, falls, virtual reality training, psychomotor consequences

est destinée au dépôt

Rehabilitation of the psychomotor consequences of elderly fallers: A pilot study to evaluate the feasibility and tolerability of virtual reality training using a user-centered designed serious game.

Pierre Wargnier, Paul-Emile Fauquet, Samuel Benveniste, Pierre Jouvelot, Anne-Sophie Rigaud, Gilles Kemoun, Frédéric Bloch

To cite this version: Virtual reality training (VRT) could be seen as a worthwhile therapeutic approach for this syndrome since it has been shown to be useful to improve combat-related PTSD 2 . Our aim was to test the feasibility and acceptability of our VRT system, Virtual Promenade, developed to treat elderly adults showing arguments for post-fall PTSD. Method: We built a prototype VRT system in which subjects navigate through a non-immersive virtual environment while seated on a chair with a moving seat that reproduces the movement of the hips during walking [START_REF] Marivan | Rehabilitation of the psychomotor consequences of falling in an elderly population: A pilot study to evaluate feasibility and tolerability of virtual reality training[END_REF] . For this study, elderly subjects were selected among inpatients of our university hospital, hospitalised for specific rehabilitation work. Patients over 75 years old with a high score at the Fall Efficacy Scale (FES 4 ) were included. Each patient benefited from pre-and post-test assessments and 2 to 3 sessions of Virtual Promenade using the virtual environment associated to the moving seat. Results and Discussion: 8 subjects participated to the study, with mean age of 88.9±5.9 years and mean FES of 36.5±13.8 at pre-test time. Our system achieved good usability and acceptance for our participants, who all had mild or moderate cognitive impairment (mean MMSE=20.9±3.7), and we did not find any particular obstacle to the feasibility of our intervention. We also found that FES was not a reliable measure of fear of falling for this type of subjects. We therefore cannot conclude on the therapeutic effects of the system. In our future work, we plan on experimenting with immersive VRT, using a headmounted display, to enrich the virtual environments to offer more stressful situations. VRT offers potential as rehabilitation technique for elderly subjects with post-fall PTSD. The next step will be to design a randomized controlled trial in order to compare the efficacy of our Virtual Promenade versus standard rehabilitation techniques in this population.

Rehabilitation of the psychomotor consequences of elderly fallers: A pilot study to evaluate the feasibility and tolerability of virtual reality training using a user-centered designed serious game. Gerontechnology

	15(suppl):….s; doi:10.4017/gt.2016.15.s.714.00
	Purpose: A fall can lead to serious psychological consequences 1 . These symptoms can de-
	velop into Fear of Falling (FoF) with behavioural disorders comparable to Post Traumatic
	Stress Disorder (PTSD).

P. WARGNIER, P.E. FAUQUET, S. BENVENISTE, P. JOUVELOT, A.S. RIGAUD, G. KEMOUN, F. BLOCH.