Frederic Giroudot
email: frederic.giroudot@isae.fr

Ahlem Mifdaoui
email: ahlem.mifdaoui@isae.fr

Tightness and Computation Assessment of Worst-Case Delay Bounds in Wormhole Networks-On-Chip

Keywords: Networks-on-chip, Network Calculus, wormhole routing, prioritysharing, VC-sharing, backpressure, flows serialization, Delay bounds, Tightness, Complexity

 for computing maximum delay bounds using Network Calculus, called the Buffer-Aware Worst-case Timing Analysis (BATA). The latter allows the computation of delay bounds for a large panel of wormhole NoCs, e.g., handling priority-sharing, Virtual Channel Sharing and buffer backpressure.

In this paper, we provide further insights into the tightness and computation issues of the worst-case delay bounds yielded by BATA. Our assessment shows that the gap between the computed delay bounds and the worst-case simulation results is reasonably small (70% tighness on average). Furthermore, BATA provides good delay bounds for medium-scale configurations within less than one hour. Finally, we evaluate the yielded improvements with BATA for a realistic use-case against a recent state-of-the-art approach. This evaluation shows the applicability of BATA under more general assumptions and the impact of such a feature on the tightness and computation time.

CONTEXT AND RELATED WORK

Networks-on-chip (NoCs) have become the standard interconnect for manycore architectures because of their high throughput and low latency capabilities. Most NoCs use wormhole routing [START_REF] Mohapatra | Wormhole routing techniques for directly connected multicomputer systems[END_REF][START_REF] Ni | A survey of wormhole routing techniques in direct networks[END_REF] to transmit packets over the network: the packet is split in constant length words called flits. Each flit is then forwarded from router to router, without having to wait for the remaining flits. This routing technique drastically reduces the storage buffer within routers, nevertheless it complicates the congestion patterns due to buffer backpressure. The latter is a flow control mechanism, which ensures a lossless transmission and avoids buffer overflow. Hence, when congestion occurs, a packet waiting for an input port to be freed can occupy several buffers of routers along its path; thus blocking in its turn other packets. This fact causes sophisticated blocking patterns between flows making the worst-case analysis of end-to-end delays a challenging issue.

Various timing approaches of NoCs have been proposed in the literature. The most relevant ones can broadly be categorized under several main classes: Scheduling Theory-based ( [START_REF] Liu | Tighter time analysis for real-time traffic in on-chip networks with shared priorities[END_REF][START_REF] Nikolić | Are virtual channels the bottleneck of priority-aware wormhole-switched nocbased many-cores?[END_REF][START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF][START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF][START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF][START_REF] Xiong | Extending real-time analysis for wormhole nocs[END_REF]), Compositional Performance Analysis (CPA)-based ( [START_REF] Rambo | Worst-case communication time analysis of networks-on-chip with shared virtual channels[END_REF][START_REF] Tobuschat | Real-time communication analysis for networks-on-chip with backpressure[END_REF]), Recursive Calculus (RC)-based ( [START_REF] Abdallah | Wormhole networks properties and their use for optimizing worst case delay analysis of many-cores[END_REF][START_REF] Ferrandiz | A method of computation for worst-case delay analysis on spacewire networks[END_REF]) and Network Calculus-based ( [START_REF] Jafari | Least upper delay bound for vbr flows in networks-on-chip with virtual channels[END_REF][START_REF] Mifdaoui | Buffer-aware worst case timing analysis of wormhole network on chip[END_REF][START_REF] Qian | Analysis of worst-case delay bounds for best-effort communication in wormhole networks on chip[END_REF]). However, these existing approaches suffer from some limitations, which are mainly due to:

• considering specific assumptions, such as: (i) distinct priorities and unique virtual channel assignment for each traffic flow in a router [START_REF] Shi | Real-time communication analysis for on-chip networks with wormhole switching[END_REF] [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF][START_REF] Xiong | Extending real-time analysis for wormhole nocs[END_REF]; (ii) a priority-share policy, but with a number of Virtual Channels (VC) at least equal to the number of traffic priority levels like in [START_REF] Shi | Real-time communication analysis with a priority share policy in on-chip networks[END_REF] [8][14] [START_REF] Tobuschat | Real-time communication analysis for networks-on-chip with backpressure[END_REF] or the maximum number of contentions along the NoC [START_REF] Nikolić | Are virtual channels the bottleneck of priority-aware wormhole-switched nocbased many-cores?[END_REF]; (iii) no support for Virtual Channels [START_REF] Abdallah | Wormhole networks properties and their use for optimizing worst case delay analysis of many-cores[END_REF][START_REF] Ferrandiz | A method of computation for worst-case delay analysis on spacewire networks[END_REF]; • ignoring the buffer backpressure phenomena, such as in [START_REF] Rambo | Worst-case communication time analysis of networks-on-chip with shared virtual channels[END_REF] [6] [START_REF] Mifdaoui | Buffer-aware worst case timing analysis of wormhole network on chip[END_REF]; • ignoring the flows serialization phenomena1 along the flow path by conducting an iterative response time computation, i.e. commonly used in Scheduling Theory and CPA, which generally leads to pessimistic delay bounds; An overview of these approaches has been presented in our previous work [START_REF] Giroudot | Buffer-aware worst-case timing analysis of wormhole nocs using network calculus[END_REF]. We have shown that there is no existing timing analysis approach covering all the technical characteristics of wormhole NoC routers while supporting the buffer size and flows serialization phenomena.

Hence, to cope with these identified limitations, we have proposed in [START_REF] Giroudot | Buffer-aware worst-case timing analysis of wormhole nocs using network calculus[END_REF] a timing analysis using Network Calculus [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] and referred as Buffer-Aware Worst-case Timing Analysis (BATA) from this point on. The main idea of BATA consists in enhancing the delay bounds accuracy in wormhole NoCs through considering: (i) the flows serialization phenomena along the path of a flow of interest ( foi), through considering the impact of interfering flows only at the first convergence point; (ii) refined interference patterns for the foi accounting for the limited buffer size, through quantifying the way a packet can spread on a NoC with small buffers.

Moreover, BATA is applicable for a large panel of wormhole NoCs: (i) routers implement a fixed priority arbitration of VCs; (ii) a VC can be assigned to an arbitrary number of traffic classes with different priority levels (VC sharing); (iii) each traffic class may contain an arbitrary number of flows (priority sharing).

There are currently some issues related to BATA, which are assessed in this paper:

• The first issue is the tightness: we have shown in [START_REF] Giroudot | Buffer-aware worst-case timing analysis of wormhole nocs using network calculus[END_REF] that BATA yields tighter bounds with respect to per-hop analysis used in CPA and Scheduling Theory for some use-cases, but it is still unknown in the general case how close the derived bounds are to the (unknown) exact worst-case delay. Thus, we are going to investigate this point through first conducting a sensitivity analysis of BATA when varying different configuration parameters, i.e., buffer size, flows packet length and flow rate. This sensitivity analysis enables the identification of the configuration parameters having the highest impact on the delay bounds. Afterwards, since there is no existing method for computing the exact worst-case delay in wormhole NoCs, we estimate the tightness of the delay bounds in comparison to simulation results, when varying the identified configuration parameters; • The second issue is the computation effort of BATA since it does not provide a closed-form solution for delay bounds but a recursive computation algorithm; thus we provide further insights into the impact of the number of flows on the computation time; • The third one is the efficiency of BATA for a realistic case study; thus we assess the tightness and computation time of our approach for a use-case of an autonomous driving vehicle application [START_REF] Burns | Schedulability analysis for real time on-chip communication with wormhole switching[END_REF] and we evaluate the yielded improvements against the most recent approach based on Scheduling theory [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF].

Contributions: In this paper, we provide further insights into the tightness and computation issues of the worst-case delay bounds yielded by BATA. Our assessment shows that the derived delay bounds are more sensitive to flow rate and buffer size, but increasing the buffer size does not yield further improvements after a certain point. This finding confirms that increasing buffer size is of limited efficiency for NoC performance. Moreover, BATA leads to tight delay bounds where the gap between the computed ones and the worstcase simulation results is reasonably small in general (70% of tightness on average). BATA provides also good delay bounds for medium-scale configurations within less than one hour. Finally, we highlight noticeable improvements with BATA for a realistic use-case, compared to the state-of-the-art approach [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF]. This evaluation shows particularly the applicability of BATA under more general assumptions, e.g. VC-sharing.

The rest of the paper is organized as follows. Section 2 introduces the system model and the main notations that are used throughout the paper. In Section 3, we describe BATA methodology and detail its main steps on a toy example. In Section 4, we conduct a sensitivity analysis of BATA and thereupon assess the tightness of the yielded delay bounds, with reference to worst-case simulation results. Section 5 describes the computation time of BATA for various configuration sizes and addresses the scalability issue of BATA. In Section 6, we assess the tightness and computation time of BATA for a realistic case study of an autonomous driving vehicle application [START_REF] Burns | Schedulability analysis for real time on-chip communication with wormhole switching[END_REF], in comparison to the state-of-theart approach [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF]. Finally, we report conclusions and give a glimpse of our future work in Section 7.

SYSTEM MODEL

Our model can apply to an arbitrary NoC topology as long as the flows are routed in a deterministic, deadlock-free way (see [START_REF] Ni | A survey of wormhole routing techniques in direct networks[END_REF]), and in such a way that flows that interfere on their path do not interfere again after they diverge. Nonetheless, we consider herein the widely used 2D-mesh topology with inputbuffered routers and XY-routing (e.g. [START_REF] Wentzlaff | On-chip interconnection architecture of the tile processor[END_REF]), known for their simplicity and high scalability. The common input-buffered 2D-mesh routers have 5 pairs of input-output, namely North (N), South (S), West (W), East (E) and Local (L), as shown on Figure 1 (top right). Each output of a router is connected to one input of another router. Moreover, as illustrated in Figure 1 (top left), the considered routers support Virtual Channels (VCs), i.e. separated channels with dedicated buffer space in the router that are multiplexed on the same interrouter links, and implement a Fixed Priority (FP) arbitration of VCs with flit-level preemption. Each VC may support many traffic classes, i.e., VCs sharing, and many traffic flows may be mapped on the same priority-level, i.e., priority sharing. Finally, we consider a blind (arbitrary) service policy to serve flows belonging to the same VC within the router. This assumption allows us to cover the worst-case behaviors of different service policies, such as FIFO and Round Robin (RR) policies.

Hence, we model such a wormhole NoC router as a set of independent hierarchical multiplexers, where each one represents an output port as shown in Figure 1 (bottom). The first arbitration level is based on a blind service policy to serve all the flows mapped on the same VC level and coming from different geographical inputs. The second level implements a preemptive FP policy to serve the flows mapped on different VCs levels and going out from the same output port. It is worth noticing that the independence of the different output ports is guaranteed in our model, due to the integration of the flows serialization phenomena. The latter induces ignoring the interference between the flows entering a router through the same input and exiting through different outputs, since these flows have necessarily arrived through the same output of the previous router, where we have already taken into account their interference. Consequently, each output port is modeled independently from the other output ports.

We use Network Calculus [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF] to model routers and traffic through service and arrival curves, respectively. Therefore, each router-output pair 𝑟, referred to as a node, is modeled as a rate-latency service curve:

𝛽 𝑟 (𝑡) = 𝑅 𝑟 (𝑡 -𝑇 𝑟 ) + ,
where 𝑅 𝑟 represents the processing capacity of the router in flits per cycle and 𝑇 𝑟 corresponds to the processing delay (the delay a flit experiences when it is processed).

Each flow 𝑓 is modeled with a leaky-bucket arrival curve:

𝛼 𝑓 (𝑡) = 𝜎 𝑓 + 𝜌 𝑓 𝑡 ,
where 𝜎 𝑓 and 𝜌 𝑓 are the maximum burst and rate of the flow 𝑓 , respectively. These parameters depend on the maximal packet length 𝐿 𝑓 (payload and header in flits), the period or minimal inter-arrival time 𝑃 𝑓 (in cycles), and the release jitter 𝐽 𝑓 (in cycles) in the following way :

𝜌 𝑓 = 𝐿 𝑓 𝑃 𝑓 𝜎 𝑓 = 𝐿 𝑓 + 𝐽 𝑓 • 𝜌 𝑓
For each flow 𝑓 , its path P 𝑓 is the list of nodes crossed by 𝑓 from source to destination. Moreover, for any 𝑘 in appropriate range, P 𝑓 [𝑘] denotes the 𝑘 𝑡ℎ node of flow 𝑓 path. Therefore, for any 𝑟 ∈ P 𝑓 , the input arrival curve of flow 𝑓 at node 𝑟 is denoted:

𝛼 𝑟 𝑓 (𝑡) = 𝜎 𝑟 𝑓 + 𝜌 𝑟 𝑓 • 𝑡

BUFFER-AWARE TIMING ANALYSIS

In this section, we describe briefly the main idea of BATA and illustrate it through an example. More details can be found in [START_REF] Giroudot | Buffer-aware worst-case timing analysis of wormhole nocs using network calculus[END_REF].

To compute end-to-end delay bounds for a foi 𝑓 along its path P 𝑓 , based on BATA, we follow three main steps.

1) Buffer-aware analysis of the indirect blocking set: To account for the impact of flows that do not physically share any resource with the foi 𝑓 , but can delay it because they impact at least one flow directly blocking 𝑓 , we introduce the Indirect Blocking set of 𝑓 , abbreviated IB set and denoted IB 𝑓 . It consists of a set of pairs {𝑘, S 𝑘 } where 𝑘 is the flow involved in indirect blocking and S 𝑘 is the subpath of 𝑘 where a packet of 𝑘 can cause blocking that can backpropagate to 𝑓 . This step takes into account the impact of the limited buffer size on the way a packet can spread on the NoC; thus on IB 𝑓 .

To better understand the impact of the buffer size on IB 𝑓 , we consider the illustrative example in Figure 2 assuming that: (i) each buffer can store only one flit; (ii) all flows have 3-flit-long packets; (iii) all flows are mapped to the same VC; (iv) the foi is flow 1; (v) all flows have an initial arrival curve 𝛼(𝑡) = 𝜎 + 𝜌𝑡 and all routers have a service curve 𝛽(𝑡) = 𝑅(𝑡 -𝑇 ) + . Consider a packet A of flow 3 that has just been injected into the NoC and granted the use of the North output port of R6. Simultaneously, a packet B of flow 2 is requesting the same output, but as A is already using it, so B has to wait. B is stored in input buffers of R6, R5 and R4. Finally, a packet C of flow 1 has reached R3 and now requests output port East of R3. However, the West input buffer of R4 is occupied by the tail flit of B. Hence, C has to wait. In that case, A indirectly blocks C, which means flow 3 can indirectly block flow 1 even though they do not share resources; Thus, IB1 = {{3, [𝑅7, 𝑅8, 𝑅9]}}.

2) End-to-end service curve computation to get a bound on the end-to-end delay for a foi 𝑓 , we need to compute its end-to-end service curve along its path P 𝑓 taking direct blocking and indirect blocking delays into account. This step integrates the flows serialization effects using the Pay Multiplex Only Once (PMOO) principle [START_REF] Schmitt | Improving performance bounds in feed-forward networks by paying multiplexing only once[END_REF]. This service curve is denoted :

𝛽 𝑓 (𝑡) = 𝑅 𝑓 (𝑡 -𝑇 𝑓 ) + ,
where 𝑅 𝑓 represents the bottleneck rate along the flow path, accounting for directly interfering flows of same and higher priority than 𝑓 , and latency 𝑇 𝑓 consists of several parts :

𝑅 𝑓 = min 𝑟∈P 𝑓 𝑅 𝑟 𝑓 𝑇 𝑓 = 𝑇𝐷𝐵 + 𝑇𝐼𝐵 + 𝑇 P 𝑓
where:

• 𝑇 P 𝑓 is the "base latency", that any flit of 𝑓 experiences along its path due only to the technological latencies of the crossed routers; • 𝑇𝐷𝐵 is the maximum direct latency, due to interference by flows sharing resources with the flow of interest (foi). We denote the set of such interfering flows 𝐷𝐵 𝑓 ; • 𝑇𝐼𝐵 is the maximum indirect blocking latency, due to flows that can indirectly block 𝑓 through the buffer backpressure phenomenon, IB 𝑓 .

To compute such a service curve, we proceed according to Algorithm 1 :

• We compute 𝑅 𝑓 . It is the minimum of the residual rates granted to 𝑓 along its path. The residual rate granted to 𝑓 at node 𝑟 is the left system capacity after taking into account the consumed one by flows of same and higher priority than 𝑓 at node 𝑟. • We compute 𝑇 P 𝑓 (line 2), then 𝑇𝐷𝐵 (lines 4 to 10); • We run our indirect blocking analysis and extract the IB set (line 11); • We compute 𝑇𝐼𝐵 (lines 12 to 18).

The detailed analytical expression of 𝑇 𝑓 is in [START_REF] Giroudot | Buffer-aware worst-case timing analysis of wormhole nocs using network calculus[END_REF]. Hence, we just point out here this computation for the same example in Fig. 2.

The only flow directly contending with foi 1 on its path is flow 2 at router R3 (East output); thus 𝐷𝐵1 = {2} and the rate of 𝛽1 is 𝑅 -𝜌. The arrival curve of flow 2 at this node is its initial arrival curve; thus:

𝑇 P 1 = 4𝑇 𝑇𝐷𝐵 = 𝜎 + 𝜌(𝑇 + 𝐿 𝑅 ) 𝑅 -𝜌 Algorithm 1
Computing the end-to-end service curve for a flow 𝑓 : endToEndServiceCurve(𝑓, P 𝑓 )

𝛽 𝑘 ← endToEndServiceCurve(𝑘, [P 𝑘 [0], • • • , 𝑟0]) 7:
𝛼 0 𝑘 ← initial arrival curve of 𝑘 8:

𝛼 𝑟 0 𝑘 ← computeArrivalCurve(𝛼 0 𝑘 , 𝛽 𝑘 ) 9:
𝑇𝐷𝐵 ← directBlocking(𝛼 𝑟 0 𝑘 ) Knowing that 𝐼𝐵1 = {{3, [𝑅7, 𝑅8, 𝑅9]}} and the burst of this flow at the input of R7; thus:

𝛽 𝑘 ← endToEndServiceCurve(𝑘, [P 𝑘 [0], • • • , 𝑆[0]]) 16: 𝛼 𝑆[0] 𝑘 ← computeArrivalCurve(𝛼 0 𝑘 , 𝛽 𝑘 ) // Now
𝑇𝐼𝐵 = 3𝑇 + 𝜎 𝑅7
3 𝑅 It's worth noticing that computing 𝜎 𝑅7 3 needs recursive calls to the function endToEndServiceCurve. We will discuss the impact of such calls on the computation time in Section 5.

3) End-to-end delay bound computation once the end-to-end service curve for the foi 𝑓 , 𝛽 𝑓 , is known, an upper bound on the end-to-end delay of 𝑓 , 𝐷 P 𝑓 𝑓 can be computed as the maximum horizontal distance between 𝛽 𝑓 and the initial arrival curve of 𝑓 :

𝐷 P 𝑓 𝑓 = 𝜎 𝑓 𝑅 𝑓 + 𝑇 P 𝑓 + 𝑇𝐷𝐵 + 𝑇𝐼𝐵 (1)
We can now compute the end-to-end delay bound of foi 1 of the example in Fig. 2 𝐷

P 1 1 = 𝜎 𝑅 -𝜌 + 4𝑇 + 𝜎 + 𝜌(𝑇 + 𝐿 𝑅 ) 𝑅 -𝜌 + 3𝑇 + 𝜎 𝑅7 3 𝑅

TIGHTNESS ANALYSIS

In this section, we assess the tightness of the delay bounds yielded by BATA. First, we conduct a sensitivity analysis of BATA to identify the configuration parameters that have the highest impact on the delay bounds. Then, we evaluate the tightness of the delay bounds using simulation, for different values of the identified parameters.

For the sensitivity analysis, we will analyze the end-to-end delay bounds when varying the following parameters: To achieve this aim, we consider the configuration described on Table 1 and Figure 3. This configuration remains quite simple but exhibits sophisticated indirect blocking patterns. We assume periodic flows with no jitter having the same period and packet length. We also assume each router can handle one flit per cycle and it takes one cycle for one flit to be forwarded from the input of a router to the input of the next router, i.e., for any node 𝑟, 𝑇 𝑟 = 1 cycle and 𝑅 𝑟 = 1 flit/cycle. Finally, to maximize indirect blocking, we consider that all the flows are mapped on the same VC. Our flow of interest is flow 1, because it is one of the flows that is most likely to undergo indirect blocking.

Figure 4 illustrates the end-to-end delay bounds of the foi when varying buffer size. For the top graph, we keep each flow rate constant at 4% of the total bandwidth; whereas for the bottom graph, we keep each flow payload at 16 flits.

We notice on both graphs that end-to-end delay bounds decrease with buffer size, with occasional stalling from one value to another. This is something we could expect because at a given packet length, the greater the buffer, the less a packet can spread in the network. Consequently, the IB set tends to be smaller, or to contain smaller subpaths. We notice that past a certain buffer size, the end-to-end delay bounds stay constant with larger buffers. This results from the fact that the IB set remains the same once buffers are big enough to hold an entire packet. Therefore, adding buffer space after a certain point does not improve end-to-end delay bounds. Hence, over-dimensioning the buffers within routers is not efficient to enhance NoC performance.

Next, we focus on the packet length impact on the end-toend delay bound, as illustrated in Figure 5. The top graph presents results when the buffer size is constant (4 flits) and The first observation we can make from both graphs is that the delay bounds evolve in an almost linear manner with the packet length. For instance, on the top graph, with 8 flits of buffer size and payload equal to 16, 64, 96 and 128 flits, the ratio of payload and end-to-end delay bound is 17.2, 19.9, 19.8, 19.7.

On the top graph, we observe further interesting aspects:

• At a given payload, the buffer size has a limited impact on the end-to-end delay bounds. For instance, for payload 64 flits, the delay bounds increase with less than 25% when the buffer size increases with 480%; • For payloads that are significantly larger than buffer size, the delay bound remains constant regardless of the buffer size, e.g., it is the case for payload 128 flits.

Finally, we study the impact of the flow rate on the end-toend delay bounds, as illustrated on Figure 6. The buffer size is fixed to 4 flits on the top graph and the payload to 16 flits on the bottom one. We can see on both graphs that the delay bounds increase with the rate. From the top graph, one can notice that at a constant rate, increasing the payload usually causes the end-to-end delay bound increase. On the other hand, from bottom graph, we confirm the conclusion drawn from Figure 4: increasing buffer size does not improve delay bounds after a certain value. Moreover, delay bounds seem more sensitive to the rate variation for small buffer sizes. For instance, for buffer size equal to 1 flit, delay bounds are 321 cycles and 1178 cycles (×3.7) for rates equal to 1% and 40% (×40), respectively. Whereas, for buffer size equal to 32 flits, the delay bounds are multiplied by only 1.6 when considering the same rate values.

The conducted sensitivity analysis reveals two main interesting conclusions:

• The configuration parameters having the highest impact on the derived delay bounds are the buffer size and the flow rate; Thus, both parameters will be considered for the tightness analysis; • Increasing the buffer size within routers after a certain point does not improve the NoC performance; Thus, over-dimensioning the buffers is not considered as an efficient solution to decrease the delay bounds.

To assess the tightness of the delay bounds yielded by BATA, we consider herein a simulation using Noxim simulator engine [START_REF] Catania | Cycle-accurate network on chip simulation with noxim[END_REF]. Knowing no method to compute the exact worstcase for wormhole NoCs, we derive an achievable worst-case delay through simulation, that we compare to the analytical end-to-end delay bounds.

In order to approach the worst-case scenario, we run each flow configuration many times while varying the flows offsets and we consider the maximum worst-case delay over all the simulated configurations. Afterwards, we compute the "tightness ratio" for each flow, that is the ratio of the achievable worst-case delay and the worst-case delay bound. A tightness ratio of 100% means the worst-case delay bound is the exact worst-case delay. However, it is worth noticing that a tightness ratio below 100% does not necessarily mean that the worst-case delay bound is inaccurate, but it can simply reveals that the worst-case scenario has not been reached by the simulation. Therefore, the determined tightness ratio is a lower bound on the exact tightness ratio.

To perform simulations, we have configured Noxim simulator engine [START_REF] Catania | Cycle-accurate network on chip simulation with noxim[END_REF] to control the traffic pattern using the provided traffic pattern file option. For each flow, we have specified:

• the source and destination cores;

• 𝑝𝑖𝑟, packet injection rate, i.e. the rate at which packets are sent when the flow is active; • 𝑝𝑜𝑟, probability of retransmission, i.e. the probability one packet will be retransmitted (in our context, this parameter is always 0); • 𝑡on, the time the flow wakes up, i.e. starts transmitting packets with the packet injection rate; • 𝑡 off , the time the flow goes to sleep, i.e. stops transmitting; • 𝑃 , the period of the flow. Moreover, since we want to simulate a deterministic flow behavior to approach the worst-case scenario, we use the following parameters for each flow:

• Maximal packet injection rate : 1.0;

• Minimal probability of retransmission : 0.0; To create different contention scenarios and try approaching the worst-case of end-to-end delays, we chose randomly the offset of each flow and perform simulations with uniformly distributed values of offsets for each flow. We generate 40000 different traffic configurations with random offsets for each set of parameters and simulate each of them for an amount of time allowing at least 5 packets to be transmitted.

We simulate the configuration of Figure 3, when varying buffer sizes in 4, 8 and 16 flits, and flow rates in 8% and 32% of the total available bandwidth. We extract the worstcase end-to-end delay found by the simulator and compute the tightness ratio for each flow. The obtained results are gathered in Table 2. As we can see, tightness ratio is always above 20%, while average tightness ratio is above roughly 50%. We also notice the average tightness ratio improves when the buffer size increases. For 8% rate, the average tightness ratio varies between 70.1% and 80.8%. For 32% rate, the average tightness ratio varies between 49.7% and 79.8%.

According to our sensitivity analysis, the indirect blocking patterns covered by our model tend to become simpler when the buffer size increases, making the IB latency smaller. Moreover, we can expect a correlation between the tightness ratio and the IB set size:

• first, for each {flow index, subpath} pair in the IB set, the analysis may introduce a slight pessimism in the IB latency computation; • second, the more complex the potential blocking scenarios are, the harder it is to reach or approach the worst-case delay by simulations: it requires a precise synchronization between flows to achieve those scenarios, and the greater the IB set, the less such a synchronization statistically happens over random offsets. Therefore, we can infer that the greater the buffer size, the easier it is to approach the worst-case delay by simulating the configuration. This is confirmed by the general trend of the average tightness ratio. It is also backed up by the following fact: in our analysis, flows 1 and 2 have the largest IB sets and are the most likely to undergo indirect blocking. We notice that at 8% rate (resp. 32% rate), their delay bounds tightness rises from 44% to 79% (resp. 44% to 87%) and 41% to 79% (resp. 24% to 97%) when the buffer size increases from 4 flits to 16 flits.

COMPUTATION ANALYSIS

We now assess how well BATA scales on larger configurations through evaluating the computation time. To achieve this aim, we consider a larger NoC than the one considered for tightness analysis, while varying the number of flows. We particularly consider a 8 × 8 NoC with 4, 8, 16, 32, 48, 64, 80, 96 and 128 flows and generate 20 configurations for each fixed number of flows 𝑁 . To do so, we randomly pick 2𝑁 (𝑥-coordinate, 𝑦-coordinate)-couples, where each coordinate is uniformly chosen in the specified range (here, from 0 to 7). We use 𝑁 of these couples for source cores and the other 𝑁 for destination cores. All other parameters (flow rate, packet length, buffer size, router latencies) are kept constant.

For each considered configuration, we focus on the following metrics:

• ∆𝑡, the total analysis runtime (computation time); • ∆𝑡𝐼𝐵, the duration of the IB set analysis; • ∆𝑡𝑒2𝑒, the duration of all end-to-end service curves computations.

The derived results are illustrated in Figure 7: the top graph for ∆𝑡, the middle one for ∆𝑡𝐼𝐵 and the bottom one for ∆𝑡𝑒2𝑒. For each flow number, we have plotted the average runtime for all the configurations with this number of flows, as well as the computed metric for each configuration (one dot per configuration). Only configurations with runtime up to 10 4 s have been considered, but the IB analysis, much faster, was performed for all configurations.

The top graph shows that the runtime grows rapidly with the number of flows (we are using a logarithmic scale on the Y-axis). Moreover, we notice that the runtimes may vary a lot for the same number of flows. For instance, for 32 flows, they range between 67ms and 110s. For 48 flows, they go from 1.5s to more than 1h10min.

To further assess what impacts the scalability of BATA, we plot the contributions to the total runtime of the IB set analysis and the end-to-end service curve computation. We notice that the IB set analysis alone (middle graph) runs in less than 8 seconds for all tested configurations. This shows that BATA approach complexity is mostly due to the end-toend service curve computation as shown in the bottom graph. This fact is mainly due to the recursive call to end-to-end service curve function in Algorithm 1.

Computing the end-to-end service curve actually needs the computation of other service curves in two cases:

(1) when computing 𝑇𝐷𝐵, we need to know the burst of the contending flow at the convergence point with the foi. Thus, we compute the service curve for the contending flow from its source to the convergence point with the foi (Algorithm 1, line 6); (2) when computing 𝑇𝐼𝐵, we need to know the arrival curve of each flow in the IB set at the beginning of its subpath. Thus, we compute the service curve of this To highlight this aspect, we measured the number of calls to the function computing a service curve during the analysis. The results displayed on Figure 8 and clearly show the expected trend. We can also notice that when all flows are mapped on different VCs (no VC-sharing), no indirect blocking is possible, i.e. IB 𝑓 = ∅ for any flow 𝑓 . Hence, there is no computation to be done for 𝑇𝐼𝐵, which drastically reduces the complexity of the approach in this case. In Algorithm 1, this means that lines 12 to 18 are not executed.

The derived results show that BATA gives good delay bounds for medium-scale configurations in less than one hour. However, the complexity of BATA increases with the number of flows due to the recursive calls to end-to-end service curve function. This fact is inherent to the large panel of NoCs, i.e., priority-sharing, VC-sharing and buffer backpressure, covered by BATA

AUTOMOTIVE CASE STUDY

In this section, we confront our model to a realistic automotive case study. This case study was used in several previous works to test NoC real-time analysis models, and recently in [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF]. It consists of 38 flows on a 4 × 4 manycore platform with a 2D-mesh NoC. The parameters of the flows can be found in [START_REF] Burns | Schedulability analysis for real time on-chip communication with wormhole switching[END_REF]. For convenience reasons, we reordered the flows as in [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF]. We also conducted a comparative analysis with the state-of-the-art method detailed in [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF] in terms of derived delay bounds tightness.

The NoC parameters used in [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF] are the following:

• The duration of a cycle is 0.5 ns;

• All routers have a technological latency of 3 cycles;

• The link capacity is one flit per cycle; Average tightness difference +0.07% +0.08% -0.03% Maximum tightness difference +3.70% +3.49% +0.01% Minimum tightness difference -0.10% -0.10% -0.10% • To compare our results to the ones in [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF], we performed the analysis for different buffer sizes (2, 100 and 1000000 flits, the latest being large enough to assume buffer size is infinite).

We then plotted comparative graphs on Figure 9 and we notice that our approach gives similar results to [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF]. To further quantify the similarity of the results, we introduce the "tightness difference" for a given flow:

∆𝜏 = 𝜏BATA -𝜏ST ,
where 𝜏𝐵𝐴𝑇 𝐴 is the tightness ratio of the bound yielded by BATA, and 𝜏𝑆𝑇 is the tightness ratio of the bound yielded by the method of [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF]. ∆𝜏 is positive when BATA gives the tighter bound and negative otherwise. We synthesized the differences in Table 3. We computed the minimum, maximum and average tightness difference.

As we can notice, both approaches give very close results, giving credit to both models.

Authors in [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF] have shown that only 4 VCs are sufficient to find a mapping of flows to VCs that ensures each flow has exclusive use of the VC within each router, which greatly simplifies the computation. However, having only one flow per VC at each node can raise scalability problems: with larger and/or less favorable configurations, ensuring each flow has the exclusive use of a VC within each router would require a number of different VCs that is not reasonable any more.

In that respect, we want to stress out that our model allows priority sharing and VC sharing (several flows sharing priority levels and VCs). Therefore, we have performed another analysis on the same configuration using only 2 VCs, with the following priority mapping:

• Flows 1 to 19 have the higher priority and are mapped to VC0; • Flows 20 to 38 have the lower priority and are mapped to VC1.

We also analyze a configuration with only 1 shared VC.

We have plotted the results with the different VC configurations on Figure 10. We only displayed the results for a buffer size of 2 flits, but the trend is similar with other sizes. To get an insight into the impact of reducing the number of VCs on delay bounds computed with BATA, we also computed, for each flow and for each 𝑛 VC configuration, the relative increase of the worst-case delay bounds compared to the delay bound with 4 VCs, as follows: 𝑖𝑛𝑐𝑛 = delay with 𝑛 VCs -delay with 4 VCs delay with 4VCs

The results are on Table 4. First, as we can notice from Fig. 10, all flows have delay bounds less than their periods (the shortest period is 40 ms); thus remain schedulable. More particularly, when we reduce the number of VCs, the computed delay bound for each flow increases (respectively 34 and 32 times out of 38) or remains the same (respectively 4 and 1 time out of 38). However, for 5 flows cases with one VC, the computed bound decreases compared to the original configuration with no shared VC (4 VCs). The concerned flows are among the flows that have the lowest priorities in the original configuration. Mapping all flows to the same priority allows more fairness. Consequently, it tends to increase the delay bounds of the flows that had the highest priorities in the original mapping, and conversely to decrease the waiting time of lower priority flows. 4, we compute the average increase of the worst-case delay bounds computed with BATA when we reduce the number of VCs, compared to the bound with 4 VCs. The average bound increase stays reasonable (up to 150 %) when the number of available VCs is divided by 2 or 4. In comparison to the state-of the-art method in [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF], BATA does not need the non-shared VCs assumption; thus, BATA enables the delay bounds computation with shared VCs. In this particular case study, we are able to show that decreasing the number of Virtual Channels (and consequently the platform complexity) can be done while maintaining the schedulability of all flows and complying with the timing constraints.

Finally, we provide some insights into the runtime of our method. For each buffer size and number of VCs, we measured the runtime of our analysis and summarized our results in Table 5. We notice that runtimes with non-shared VCs are in the order of 10 times lower than runtimes with 1 and 2 VCs. This confirms our conclusions in Section 5 concerning the inherent complexity of BATA to handle the priority-sharing and VC-sharing assumptions.

Actually, when no VC is shared between several flows, the IB latency is zero. However, when VCs are shared, there are additional recursive calls to end-to-end service curve function needed to compute the IB latency; thus we can expect an increase in the analysis duration.

CONCLUSION

In this paper, we proposed an extensive evaluation of the tightness and computation time of our previously published Table 5: Runtimes of BATA for different NoC configurations when sharing VCs buffer-aware worst-case timing analysis (BATA) for wormhole NoCs [START_REF] Giroudot | Buffer-aware worst-case timing analysis of wormhole nocs using network calculus[END_REF]. To evaluate the tightness, we first studied how the various system parameters impact the computed end-to-end delay bounds. We found our model to be most sensitive to rate and buffer size. Consequently, we proceeded the tightness analysis with a set of different buffer sizes and flow rates. We were able to achieve a tightness ratio up to 80% on average, with reference to simulation.

We then estimated the scalability of our approach in terms of computation time when increasing the number of flows. We found that the main complexity of the analysis lies in the indirect blocking latency computation, as it leads to additional recursive calls to the function computing the endto-end service curve. However, this complexity comes from the fact that the model is able to cover configurations with shared priority and shared VCs. If no VCs are shared, the analysis is much less complex.

Finally, we compared our results to those of [START_REF] Nikolic | Real-time analysis of priority-preemptive nocs with arbitrary buffer sizes and router delays[END_REF] on an automotive case study. We have shown that the results are very similar, with tightness ratios differing by less than 0.1% on average. Moreover, since our model is not limited by the assumptions of no priority-sharing and no VC-sharing, we have analyzed other configurations with reduced number of VCs (thus lower complexity) while maintaining the schedulability of all flows.

Our next focus will be to rethink the indirect blocking analysis in order to decrease the computational cost of BATA while covering a large panel of NoC configurations.

Figure 1 :

 1 Figure 1: Router architecture and output multiplexing

Figure 2 :

 2 Figure 2: Example configuration (left) and packet stalling (right)Consider a packet A of flow 3 that has just been injected into the NoC and granted the use of the North output port of R6. Simultaneously, a packet B of flow 2 is requesting the same output, but as A is already using it, so B has to wait. B is stored in input buffers of R6, R5 and R4. Finally, a

Figure 3 :

 3 Figure 3: Flow configuration on a 6×6 mesh NoCTo achieve this aim, we consider the configuration described on Table1and Figure3. This configuration remains quite simple but exhibits sophisticated indirect blocking patterns. We assume periodic flows with no jitter having the same period and packet length. We also assume each router can handle one flit per cycle and it takes one cycle for one flit to be forwarded from the input of a router to the input of the next router, i.e., for any node 𝑟, 𝑇 𝑟 = 1 cycle and 𝑅 𝑟 = 1 flit/cycle. Finally, to maximize indirect blocking, we consider that all the flows are mapped on the same VC. Our flow of interest is flow 1, because it is one of the flows that is most likely to undergo indirect blocking.Figure4illustrates the end-to-end delay bounds of the foi when varying buffer size. For the top graph, we keep each flow rate constant at 4% of the total bandwidth; whereas for the bottom graph, we keep each flow payload at 16 flits.We notice on both graphs that end-to-end delay bounds decrease with buffer size, with occasional stalling from one value to another. This is something we could expect because at a given packet length, the greater the buffer, the less a packet can spread in the network. Consequently, the IB set tends to be smaller, or to contain smaller subpaths. We notice that past a certain buffer size, the end-to-end delay bounds stay constant with larger buffers. This results from the fact that the IB set remains the same once buffers are big enough to hold an entire packet. Therefore, adding buffer space after a certain point does not improve end-to-end delay bounds. Hence, over-dimensioning the buffers within routers is not efficient to enhance NoC performance.Next, we focus on the packet length impact on the end-toend delay bound, as illustrated in Figure5. The top graph presents results when the buffer size is constant (4 flits) and

Figure 4 :

 4 Figure 4: Buffer size impact on end-to-end delay bounds the one when the rate of each flow is constant (4% of the link capacity).The first observation we can make from both graphs is that the delay bounds evolve in an almost linear manner with the packet length. For instance, on the top graph, with 8 flits of buffer size and payload equal to 16, 64, 96 and 128 flits, the ratio of payload and end-to-end delay bound is 17.2, 19.9, 19.8, 19.7.On the top graph, we observe further interesting aspects:

Figure 5 :

 5 Figure 5: Payload impact on end-to-end delay bounds

  0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0

Figure 6 :

 6 Figure 6: Rate impact on end-to-end delay bounds

Figure 7 :

 7 Figure 7: Results of the scalability analysis

Figure 8 :

 8 Figure 8: Number of calls to the function endToEnd-ServiceCurve()

Figure 9 :

 9 Figure 9: Worst-case end-to-end delay bounds comparison for different buffer sizes (2, 100 and ∞)

1 :

 1 Compute 𝑅 𝑓 2: Compute 𝑇 P 𝑓 // Compute 𝑇𝐷𝐵: 3: 𝑇𝐷𝐵 ← 0 4: for 𝑘 ∈ 𝐷𝐵 𝑓 do 𝑟0 ← cv(𝑘, 𝑓 ) // Get convergence point of 𝑓 and 𝑘

	5:
	6:

  10: end for // Compute 𝑇𝐼𝐵: 11: IB 𝑓 ← indirectBlockingSet(𝑓 ) 12: 𝑇𝐼𝐵 ← 0 13: for {𝑘, 𝑆} ∈ IB 𝑓 do ̃ 𝛽 𝑘 ← VC-service curve of 𝑘 on 𝑆 // Compute the service curve of 𝑘 from its first node to the beginning of 𝑆:

	14:
	15:

  add the delay over the subpath to 𝑇𝐼𝐵 :

	17:	𝑇𝐼𝐵 ← 𝑇𝐼𝐵+ delayBound(𝛼 𝑘 , ̃ 𝛽 𝑆[0] 𝑘	)
	18: end for

19: return 𝑅 𝑓 (𝑡 -(𝑇 P 𝑓 + 𝑇𝐷𝐵 + 𝑇𝐼𝐵)) +

Table 1 :

 1 Flow characteristics

	WC delay bound (cycles)	1000 1500 2000 2500	BUFFER_SIZE=1, BATA BUFFER_SIZE=8, BATA BUFFER_SIZE=16, BATA BUFFER_SIZE=32, BATA BUFFER_SIZE=48, BATA
		500
		0
		0	20	40	60 PAYLOAD	80	100	120

Table 2 :

 2 Tightness ratio results for the tested configuration

	Rate Buffer Tightness statistics		Per-flow tightness ratio
			Average	Max	Min	1	2	3	4	5	6	7	8	9	10	11	12
	8%	4	70.1% 91.7% 40.6% 44% 41% 64% 68% 77% 75% 89% 68% 47% 88% 92% 89%
		8	72.1% 92.0% 38.1% 46% 38% 69% 71% 80% 79% 90% 70% 49% 90% 92% 90%
		16	80.8% 88.3% 48.9% 79% 79% 85% 86% 85% 86% 87% 70% 49% 88% 88% 87%
	32%	4	49.7% 95.6% 20.8% 44% 24% 51% 64% 46% 21% 44% 46% 24% 70% 96% 66%
		8	64.2% 88.9% 33.3% 66% 47% 59% 81% 53% 46% 69% 65% 33% 88% 79% 85%
		16	79.8% 97.3% 43.8% 87% 97% 54% 87% 64% 86% 97% 71% 44% 88% 96% 88%

Table 3 :

 3 Tightness differences for various buffer sizes between BATA and state-of-the-art approach

	• Flows' priority assignment follows a rate monotonic
	policy;
	• Each router supports 4 Virtual Channels with no
	priority-sharing and no VC-sharing, i.e., one flow per
	VC;

Table 4 :

 4 Relative increase of the worst-case end-toend delay bounds for 𝐵 = 2 with BATA Moreover, in Table

		120 140	BATA, original 4 VCs configuration, B=2 BATA, 2 shared VCs BATA, single shared VC
	End-to-end delay (µs)	40 60 80 100
		20
		0
			1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 Flow index
	Figure 10: Delay bounds with 4, 2 and 1 VC with
	buffer size = 2 flits for BATA
				2 VCs	1 VC
	Average bound increase 101.11%	145.13%
	Minimal bound increase	0.00%	-95.05%
	Maximal bound increase 464.16% 2293.01%

The pipelined behavior of networks infers that the interference between flows along their shared subpaths should be counted only once, i.e., at their first convergence point.


VRT: Exploration and Filtering of Trajectories in an Immersive Environment using 3D Shapes

Keywords:

: VRT enables dynamic filtering of large trajectory datasets using 3D shapes. From left to right: (a) A cylinder used as a saber to select and filter particles from a numerical simulation dataset, (b) a sphere used to select and animate vehicles at a road junction in a car traffic dataset. Such shapes can become (c) persistent to refine queries and extract complex vortex, and trajectories can be (d) animated to re-create turbulent flows of particles.

INTRODUCTION

Many fields generate large trajectory datasets: GPS trackers on aircrafts are used for real-time monitoring of thousands of moving objects; road traffic simulations give insights on how to prevent traffic jams in a city; particle simulations of turbulent flows make it possible to identify phenomenons normally invisible due to their small scale in space and time. Those domains usually involve domain-expert users who need to explore their dataset to assess the structure and quality of collected or generated data [START_REF] Tukey | Exploratory data analysis[END_REF].

Interaction is key during the exploration process, in particular to isolate elements of interest. For instance, when interacting with aircraft datasets, a frequent exploratory task is to filter by take offs and landings, for a given specific airport area. Assuming the planes' positions are displayed in 3D with coordinates (x, y, z), and their trajectories result from their tracking over time (t), selecting planes is achieved by having constraints on both 1) the 2D position on the ground (a circle centered on the airport), and 2) maximal altitude. Performing such a selection is difficult with standard 2D dynamic queries [START_REF] Shneiderman | Dynamic Queries for Visual Information seeking[END_REF] as they only operate on a plane.

Immersive environments demonstrate great promise to explore and interact with 3D datasets [START_REF] Chandler | Immersive Analytics[END_REF]. Recent work includes Fiberclay [START_REF] Hurter | FiberClay: Sculpting Three Dimensional Trajectories to Reveal Structural Insights[END_REF], which provides a tilted 3D view, direct brushing and selection interactions. However, those selections are not localized and also select fly-overs; the process requires deselecting trajectories from another point of view.

This paper seeks to introduce a simple yet general-purpose interaction technique that operates simultaneously on the three spatial dimensions. The technique uses 3D geometric shapes (spheres, cuboids and cylinders) that encode a 3D query which the user manipulates to probe a highly cluttered environment [START_REF] Elmqvist | A Taxonomy of 3d Occlusion Management for Visualization[END_REF]. Our research hypothesis is that such 3D geometric queries are not only expressive enough for open-ended exploration tasks, but also to single out specific elements. To validate this hypothesis, we present VRT [name changed for peer review], a VR trajectory data visualizer in which we implemented the technique and tested it against different application domains and datasets. Our paper has three main contributions:

• The first contribution is to present a visualization toolkit that allows non-experts in Virtual Reality to intuitively create and use simple 3D geometric shapes as selection tools, and to filter the dataset through the use of custom Boolean operations.

• The second contribution of this paper is the implementation of persistent selectors that allow the reuse of specific queries.

• The third contribution is the mapping choice of all the interactions possible in VRT on the limited inputs available with the VR controllers.

RELATED WORK

Visualization in Immersive Environments

Immersive environments (e. g., VR, augmented reality, interactive walls) have demonstrated great promise for the exploration of abstract datasets [START_REF] Chandler | Immersive Analytics[END_REF]. In particular, recent years have seen a fast democratization of Virtual Reality (VR) technology: newer headsets with much more resolution and precise user's movements, VR support in consumer-grade graphics card and the emergence of high-level development software such as Unity 1 , along with standardized libraries like Valve's OpenVR2 , have made standardized VR technology accessible.

In the meantime, the task of exploring large datasets has become pervasive in all research and engineering domains. We found that while extremely powerful visualization tools, such as Kitware's ParaView 3 and its plugins like the Topology Toolkit [START_REF] Tierny | The Topology ToolKit[END_REF] exist, they lack the ease of use and intuitiveness that VR shines in. This is why we started work on VRT, a lightweight open-source tool aimed at science and engineering domain-experts specialized in quickly visualizing and filtering trajectory datasets in VR.

Indeed, when compared to traditional 3D visualizers, VR shows high potential. Users can immerse themselves in the dataset with many more degrees of freedom than through a traditional mouse and keyboard interface, both for the control of their point of view and of their interactions with the data. However, these benefits come at a cost; depth perception and comfortable viewing are only possible on dual high resolution screens, which greatly impact the rendering performance. Meanwhile, a high frame rate (traditionally, a minimum of 30 fps) is essential in VR to reduce risks of inducing nausea.

Exploration in Immersive Environments

Exploration techniques in those settings often rely on displaying large amounts of data for the user to navigate within, with no previous assumptions (e. g., filtering, aggregation) made. Fiberclay [START_REF] Hurter | FiberClay: Sculpting Three Dimensional Trajectories to Reveal Structural Insights[END_REF] is a flagship example that displays thousands of trajectories and lets user build queries using beams. ImAxes [START_REF] Cordeil | ImAxes: Immersive Axes As Embodied Affordances for Interactive Multivariate Data Visualisation[END_REF] and IATK [START_REF] Cordeil | IATK: An Immersive Analytics Toolkit[END_REF] permit the creation of axes to map data attributes to spatial locations and create standard charts (e. g., parallel coordinates, scatterplots) based on logical rules. Those techniques have in common that they require no user interface to switch between interaction modes: only the users' VR controllers are visible in the virtual environment. VRT is heavily inspired by this approach and augments the controllers to display current possible queries as 3D shapes called selectors, as well as operation menus used to filter the dataset by combining multiple selections.

Dynamic Queries and Brushing

Dynamic queries [START_REF] Shneiderman | Dynamic Queries for Visual Information seeking[END_REF] set the foundation for interactive exploration of large datasets. They enable the selection of value ranges in an iterative and safe way and are informative as they are coordinated to visual feedback. Such queries enable users to grasp the structure and distribution of the datasets through transient selections, which are key for exploratory data analysis [START_REF] Tukey | Exploratory data analysis[END_REF]. Our work is built on this paradigm, and in particular brushing, which complies with the direct manipulation paradigm to let users manipulate regions of interest on the screen in a natural way. Brushing has been extended beyond 2D environments such as in 3D [START_REF] Sherbondy | Exploring connectivity of the brain's white matter with dynamic queries[END_REF] and immersive environments, e. g., for Cave interactions [START_REF] Symanzik | Dynamic Statistical Graphics in the CAVE Virtual Reality Environment[END_REF], in Virtual Reality [START_REF] Hurter | FiberClay: Sculpting Three Dimensional Trajectories to Reveal Structural Insights[END_REF][START_REF] Prouzeau | Scaptics and Highlight-Planes: Immersive Interaction Techniques for Finding Occluded Features in 3d Scatterplots[END_REF], or with tangible interactions [START_REF] Besanc ¸on | Hybrid Touch/Tangible Spatial 3d Data Selection[END_REF][START_REF] Jackson | A Lightweight Tangible 3d Interface for Interactive Visualization of Thin Fiber Structures[END_REF]. However, brushing specific areas or volumes remains challenging especially with large datasets due to occlusions.

3D Occlusions and Selection Tools

3D environments require occlusion management [START_REF] Elmqvist | A Taxonomy of 3d Occlusion Management for Visualization[END_REF], as objects in a scene can mask each other, especially when their density is important. To facilitate large selections, different techniques have been used in VR such as hand avatars, bimanual selection, 3D cursors and raycasting [START_REF] Argelaguet | A survey of 3d object selection techniques for virtual environments[END_REF]. While ray casting allow ease of interaction and selection in Virtual Reality and seems to have become a default technique [START_REF] Argelaguet | A survey of 3d object selection techniques for virtual environments[END_REF], it does not allow for distinguishing between objects that are both on the infinite ray. In this case, other techniques such as shapes (e. g., squares, circles) can be used to select all items within them [START_REF] Chen | LassoNet: Deep Lasso-Selection of 3d Point Clouds[END_REF][START_REF] Yu | CAST: Effective and Efficient User Interaction for Context-Aware Selection in 3d Particle Clouds[END_REF]. In a 2D space, rectangle shapes are standard as they can easily be built using mouse selection [START_REF] Shneiderman | Dynamic Queries for Visual Information seeking[END_REF], but if more attributes are being used, complex shapes can emerge [START_REF] Heer | Generalized Selection via Interactive Query Relaxation[END_REF], e. g., by using a non-visual attribute. In 3D worlds, 3D shapes (e. g., cuboid, sphere) enable the manipulation of spatial regions in an efficient way to select groups of objects and so progressively refine the selection [START_REF] Jackson | Force Brushes: Progressive Data-Driven Haptic Selection and Filtering for Multi-Variate Flow Visualizations[END_REF][START_REF] Kopper | Rapid and accurate 3d selection by progressive refinement[END_REF] . BalloonProbe [START_REF] Elmqvist | BalloonProbe: Reducing occlusion in 3d using interactive space distortion[END_REF] uses spherical shapes to let users separate objects based on their attributes in a 3D scene. Bounding boxes of groups of points in a 3D space [START_REF] Hentschel | Virtual Reality-Based Multi-View Visualization of Time-Dependent Simulation Data[END_REF] can become interactive to select items. Balloon Selection [START_REF] Benko | Balloon Selection: A Multi-Finger Technique for Accurate Low-Fatigue 3d Selection[END_REF] also lets users create and translate spheres in a 3D space for target selections, with a combination of 2 DOF interactions. Flat 2D planes can be used for spatial structure projection, e. g., in brain imagery [START_REF] Akers | CINCH: a cooperatively designed marking interface for 3d pathway selection[END_REF][START_REF] Chen | Human Brain Functional MRI and DTI Visualization With Virtual Reality[END_REF][START_REF] Coffey | Interactive Slice WIM: Navigating and Interrogating Volume Data Sets Using a Multisurface, Multitouch VR Interface[END_REF]. To manage this problem, already lessened by the small footprint of the trajectories, our work capitalizes on using a variety of probes both in shapes and sizes, as well as by providing an ease of navigation to make better points of view quickly available to the user.

FEATURES DESIGN

The design approach of VRT is based on three core features illustrated Fig. 2: 1. Visualization: VRT allows the user to see a 3D rendering of the raw dataset and easily change their point of view through intuitive game-like movement controls.

2. Selection: intuitive arm motions allow the user to select the parts of the dataset they want to filter by touching them with configurable 3D shapes called selectors.

3. Filtering: the user can create custom Boolean operations to control the visibility of the trajectories they selected.

This section details the design of those three features.

Immersive Visualization of Trajectory Data

At the core of VRT is its ability to display trajectory data in VR. The VRT engine renders a visualization as an ensemble of independent paths, each made of many small 2D segments called ribbons. Each ribbon serves to link two adjacent points of the path. We name each of these points atoms, as they can hold more attributes than spatial coordinates (e. g., a time value, the current kinetic energy of a particle, etc.). Examples of visualizations can be seen Fig. 1. Additionally, VRT enables time-based animation of trajectories using small spheres that follow each path from its start to its end (optionally using its atoms' time values for reference if applicable). The position, radius, and animation speed of these spheres can be configured in real time, making them a good tool to expose invisible implicit attributes such as speed.

Trajectories can also be animated from a shared starting position, i. e. a given spatial selection from which a playback starts, ignoring the context of the actual starting time of each path. We call this technique "dropping" spheres on a selection.

Selection using 3D Geometric Queries: Selectors

A selector is a tool for selecting trajectories; it takes the form of a colored 3D shape attached to the hand of the user. It functions as a 3D brushing tool, allowing the user to make 3D geometric queries on the dataset. There are six colors available for selectors (red, green, blue, yellow, cyan and magenta). Thus, the user has six stored selectors that they can use by switching from one color to the other.

When the user presses a physical selection trigger (Fig. 3), the selector becomes active, and all visible ribbons touching the selector takes the color of the selector. This notifies the user that the paths those ribbons belong to have been selected and put in that selector's color group (used afterwards through operations). The selector then stays active until the user lets the trigger go, allowing for selection through painting-like strokes. It is important to note that while only a part of the path is colored, the entire path is considered selected in that color. This partial coloration does not hide too much of the original color of the path, which can be configured to relay information.

We include three selector shapes in VRT: cuboids, spheres and cylinders (see Table 1). These shapes can be manipulated through parameters which define their size as well as their position and rotation relative to the hand of the user. Controllable parameters, listed Table 1, are intentionally restrictive. This is necessary in order to not confuse the user with too many possible operations on the restricted number of buttons available on the VR controllers. Cuboids have the additional limitation of being rotation-locked on both horizontal axes; this way, their bottom side is always parallel to the ground of the visualization, making axis-aligned queries easier to perform.

The three selector shapes were chosen for their utility in different use cases. Spheres are mostly useful for selecting all trajectories passing through a specific point of interest, or used as a detached pointer to select specific trajectories at a medium distance from the user. Cylinders are often used as a kind of sword, slicing through a bundle of similarly-oriented trajectories to select them all. Cuboids, thanks to their rotation lock, are more useful as walls, ceilings or floors delimiting certain regions of space, e. g., for selecting all trajectories going above a certain height.

Persistent selectors

It can often be interesting to perform the same query multiple times -for example, when redoing a selection after having hidden a subset of ribbons. In this case, using hand-held shapes to try to make the exact same query is cumbersome. To solve this problem, we introduce persistent selectors: by pressing a button, the user can clone the currently hand-held selector in the 3D space as a persistent selector, which won't move with the user and can be activated at a distance when necessary.

Persistent selectors also give the user the opportunity to seed multiple points of interest ahead of time, to use later in combined queries -this is especially interesting in fields focused on such points of interest, e. g., with traffic data.

Using Selections to Filter Data: Operations

Once selections have been done, the user can utilize the color groups they populated to filter the currently displayed trajectories. This process of filtering is done through the use of operations that the An OR-type operation will, out of all currently displayed paths, hide all but those that are selected in at least one of the operation's color groups; as an example, the "Blue, Green, OR" operation will only keep displayed the trajectories that are either selected in blue or green.

An AND-type operation will only keep previously-displayed trajectories that are selected in all of the operation's color groups. Thus, the "Blue, Green, AND" operation would this time only keep displayed the trajectories that are selected in blue and green.

Of importance is the fact that operations and selections only affect currently displayed trajectories. This adds another level of flexibility to VRT's filtering system, as consecutive filtering operations will be able to complement each other.

CONTROLLER MAPPING AND USER EXPERIENCE

Apart from animation controls, all previously introduced features of VRT are accessible directly on the controllers. We did not implement any large menu on the screen, to let the user explore the visualization with their vision unobstructed.

The control scheme in VRT was designed to give intuitive access to the previously described features, despite being restrained by the limited set of controls offered by VR controllers. Since standardized controls for VR devices are not yet available, this section is largely specific to the Samsung HMD Odyssey4 controllers we used during the development of the project, however, most if not all of these controls could be adapted to different devices. The nomenclature of the different inputs and all of VRT's controls are respectively illustrated in Fig. 3 (a), (b) and (c).

Control Modes

In order to limit the complexity of the controls, two separate control layouts are accessible and toggled at the press of a button: selection mode and creation mode. In selection mode, the user can select trajectories using the selectors, switch between different selector colors, place and remove persistent selectors, and create and execute filtering operations. Creation mode is exclusive to selector modification, allowing the user to position the current selector relative to their hand and to change its dimensions; configurable parameters for each type of selector are summarized in Table 1.

To broaden the range of possible inputs, an "inverse" trigger is used: while the left controller's trigger is pressed, some controls are modified (usually to have the opposite of their normal effect).

Operation Controls

Displayed on the left controller's pad are six initially blank squares, representing the six colors groups previously mentioned (Fig. 3,c). Those squares encircle a symbol which shows the operation's type: either "&" (AND-type) or "||" (OR-type).

By clicking the right controller's pad, which displays the current selector's color (Fig. 3,c), this color's presence in the operation will be toggled. When a color is to be used in the operation, its corresponding square will be filled. This way, the left pad provides a complete overview of what the operation will do. A pull-down menu on the left controller's pad can be clicked to toggle the operation's type. All changes to the operation are also signaled through vibrations in the left controller, such that an experienced user will not have to look at it to know the operation's state.

Finally, the created operation can be applied to the visualization by pressing the left controller's pad (Fig. 3,c). Resetting the effects of operations requires pulling up from the bottom part of the left pad to bring up the "RESET" button, then pressing it. Finally, while the "Inverse" trigger is pressed, the left pad changes to display the word "Invert"; pressing the left pad at this moment will execute the "Invert" selection, toggling the visibility of all the paths in the dataset. This special operation is not influenced by the color groups or type of the standard operation.

IMPLEMENTATION NOTES AND OPTIMIZATIONS

VRT is implemented in C# using Unity5 , a popular 3D real-time rendering engine traditionally used for video game development. We used Samsung's HMD Odyssey as VR equipment, with Alienware laptops to help achieve real-time rendering. Our implementation uses Valve's SteamVR library to interface with our VR equipment. VRT's algorithms could however be re-implemented using other software and hardware solutions.

VRT is released as an open source project with permissive licence. Code and documentation are available on GitHub [Left blank for peer review] .

While we relied on a well established stack of software and devices, an important development effort was required to achieve solid rendering performance and fast collision detection. The following sections provide a high-level overview of those algorithms and discuss the impact they had on the design of VRT.

Trajectories Rendering

A crucial constraint in exploratory data analysis is to build techniques with as little latency as possible; and in VR software, maintaining a solid framerate is critical. Indeed, bad performance will cause poor synchronisation of the video feedback to the user's movements, quickly inducing nausea; thus, VRT has to be able to render the trajectories of a dataset at least 30 times per second.

To alleviate the load on the graphics card used, we chose to render paths with a minimal amount of triangles through procedural mesh creation. Each ribbon (individual segment of a path) is made of two triangles forming a rectangle; an additional triangle is rendered between each two consecutive ribbons to soften the junction between the two rectangles. Individual meshes are procedurally created for each path by linking all of the path's ribbons. This vertex configuration is shown Fig. 4.

Compared to an approach where actual 3D cylinders are rendered, this method produces cleaner results and uses fewer triangles and memory, however, it requires the ribbons to be rotated towards the camera at all time. This was done through the use of a custom HLSL (High Level Shading Language) shader.

This system allows us, on our computers equipped with Nvidia's 1080Ti (Max-Q design), to sustain an acceptable framerate up to around 20 million on-screen atoms (constitutive points of the trajectories).

Collision Detection

Whenever the user presses the selection trigger, the selector in their right hand becomes active, selecting and painting all the ribbons it touches in its color. Unity provides efficient methods for checking if two individual 3D shapes collide. However, a naive implementation would need to apply this check to all the ribbons in the scene and repeat this intensive operation each frame that the selector is active, making for unacceptable performance.

To alleviate this problem, space in VRT is divided in small cuboid sections we call districts. Each district keeps track of all the ribbons inside it. This partitioning allows the program to quickly get a gross approximation of which ribbons are in a specific spatial zone and to restrain the computationally expensive accurate collision detection algorithm to only those ribbons.

In order to know which districts to check for collisions, we implemented a shell-filling algorithm, particularly efficient for selections with large selectors.

1. First, the center of the selector is used to determine a district necessarily touched by the selector, which we call the "center district".

2.

A line of districts stemming from the center district in an arbitrary direction is progressively checked until a district at the edge of the selector is found (which we call a "border district").

3. A flooding algorithm starting from the found border district finds all the border districts around the selector, creating an hermetic "shell" of border districts.

4. Starting again from the center district, a flooding algorithm finds all the districts enclosed by the shell; those districts, fully comprised within the selector, are called "inside districts". Once this has been done, the algorithm can safely assume that all ribbons pertaining to "inside" districts are touched by the selector without need for further calculations. Afterwards, only ribbons exclusive to "border" districts will be fully tested to determine if they touch the selector or not.

This algorithm, summarized Fig. 5, essentially reduced the complexity of collision detection from O(N 3 ) to O(N 2 ) on very large selectors, as only the surface of the selector gets "deeply" checked.

USER EVALUATION

During the design of VRT, we followed the Munzner [START_REF] Munzner | A nested model for visualization design and validation. Visualization and Computer Graphics[END_REF] nested model design methodology by constantly engaging with many potential end-users from various domains, involving both human behavior trajectory recordings as well as simulations. This phase spanned over 9 months in total and helped us to validate the problem, data abstraction and encoding steps of the model. This process remained highly informal, with multiple exchanges of sample datasets, questions, and screenshots of the prototype. We validated the algorithm part of the nested model by achieving real-time frame-rate for the datasets we used in our experiments.

We conducted a user evaluation for the interactions encoding part of the nested model during formal sessions with domain-expert participants who were not involved in the design process. We sought for experts who needed to visualize large amounts of data, but with a lack of expertise in building interactive systems. In total we contacted 6 experts, either from our local university or from professional networks who submitted a dataset to load into VRT to us (as a technical procedure was needed to clean, format and scale the dataset). We also added static 3D models and background elements useful for context (e. g., rugby pitch, map of a city/country) (see details Table 2). We invited them to one or two evaluation sessions (depending on their availability or for follow-ups related to adding more or different datasets). Due to limited space, we report only on 4 case studies we selected based on the diversity of datasets and tasks.

Each session started with a training procedure. After briefly presenting the tool, the HMD, and the controllers, the participants used the HMD for 30 minutes in a guided tutorial visualization of aircraft trajectories over a country over a day. This dataset allowed participants to use VRT with a realistic exploration task in a reasonablysized dataset with low trajectory density. The training ended with an evaluation process requiring the use of selectors and operations to solve a specific task with this dataset: selecting trajectories between two given airports. Following the tutorial, participants were able to explore their visualization and use all the capabilities of VRT to filter their datasets. Each session lasted on average 60 minutes; the participants' behavior was recorded through a webcam, a screen-cast from the headset, and an automated log of their positions and interactions within the 3D environment. Those logs are illustrated in Fig. 6, 7, 8 and 9) with the position of the user (top-left 3D chart) and a timeline of its interactions (from top to bottom: choice of selector, creation of a persistent selector, operation on selectors, reset, change of speed and selectors edition mode activated/deactivated). Such logs enable to grasp the user activity over space and time. It also enabled us to efficiently browse video recordings to sequences of interest, e. g., when multiple persistent selectors have been created.

Case study RUGBY: Players Performance Analysis

Sports tracking data is becoming increasingly available due to advances in wearable GPS sensor technologies. Such data provides fine-grained position of players on a pitch. We collaborated with a Rugby Team (consistently ranked in the top 5 teams of one of the major European Leagues) which constantly collects GPS data of its players and substitutes during training and games (warm-ups included). We contacted a researcher expert in rugby, with experiences as a player and trainer. He was also familiar with the tactics of the team we collaborated with and mainly used dashboards, datasheets, and video streaming to identify weaknesses in the team, which zone of the pitch was occupied the most, as well as the team behavior during an action. Individual behaviors are also important to identify exhausted players needing to be substituted. We loaded the GPS dataset of a single game from the team in VRT. As the dataset was very accurate, we only loaded 1/10 of the dataset with uniform spatial sampling. We added 3D models of goalposts and a rugby pitch map to give spatial context and references to the expert.

The first step of our domain expert was to grasp the distribution of the dataset as a standard 2D map (Fig. 6 left). While this map generates an important visual clutter (due to over-plotting), the expert positioned himself in a tilted position similar to one of a spectator or a TV camera. He animated players using the playback feature and configured the paths color to reflect the players' speed. The cylinder interaction was used to explore the dataset and pick a particular player (# 14). This player's behavior was isolated, though with no particular findings. After resetting the selection, he inspected the team's collective behavior and was able to infer the positions of the forward players by looking at group placements during waves of attack or defence. He constantly changed his position around the game to adjust his point of view. For this scenario, he did not find useful to select a spatial region in particular. The second step was to encode player load (which is an attribute related to effort) as the vertical axis (z) and to animate all the players. The resulting vertical visualization allowed him to quickly identify the top 3 most active players on the field. Here, cylindrical selectors were often used as pointing rods to explain parts of the game or point to particular players without using their selecting ability.

Case study PROPELLER: Flow Simulation Exploration

Our colleagues from the Engineering department of our local university provided us with a numerical simulation of turbulence phenomena around a propeller over time. After discussions, we selected a data subset from a numerical simulation of 9, 440 streamlines over a maximum of 150 instants, resulting in a total of 738, 096 atoms. Those streamlines were localized around a propeller currently studied by these experts. Such a structure generates regions of interest such as a vortex and separated flow regions. They typically wanted to know if the streamlines involved in the vortex were from the same departure areas or not, and to study their time evolution. They also sought to identify supersonic regions in the flow. Experts knew interesting areas in advance and were seeking for a quick way to explore and visualize their dataset, as well as the possibility of communicating their research to either students or the general public in intuitive video format. They currently use Mathwork's Matlab6 and Kitware's ParaView to run their simulation and visualize the results. As streamlines are already by nature 3D data, their representation is straightforward. We tested two color strategies: coloring by Mach number to highlight the supersonic area, or using random colors to study the streamlines separately. 3D models of the propeller and of the supersonic layers completed the visualization.

The expert started his exploration with an overview of the trajectories and then selected streamlines from departure locations he knew would hold streamlines involved in vortex. Then, he changed his point of view to refine the selection using the cylinder shape (due also to a preference for what he called "a lightsaber"). By using another color, he could see the newly selected trajectories as a subset of previous selections. Fig. 7 illustrates this step-by-step process up to the final selection. The expert then spent some time explaining the physics foundations behind this phenomena using the cylinder to point to and describe the behavior of the selected streamlines. ) or mapping of a non-spatial attribute was used (RUGBY, TRAFFIC). We highlighted in bold the most interesting attributes during the case studies. Finally, some case studies required to add a 2D background (often a map) and a 3D model for context.

Case study PARTICLES: 3D Particles in a Turbulent Flow

Other colleagues from the Engineering department provided us with a simulation of 3D particles in an isotropic and turbulent flow. Due to the large number of particles, they face visualization and exploration problems with this dataset. Surprisingly, they had never been able to simultaneously visualize a correct amount of particles even though it is an important aspect of their research work. Indeed, they wanted to explore their turbulent flow to develop an intuition on data and results and confirm predictions on the evolution of attributes according to the shape of the trajectory. They currently use Mathwork's Matlab to visualize these particle trajectories, but this tool only allows them to extract and visualize some parts of the dataset. We met these colleagues to discuss their dataset and visualization problems. This allowed us to identify an interesting subset of data that we enriched by computing the speed, acceleration, and power attributes for all the particles. We ended up with a dataset describing the evolution of a million particles in a turbulent flow over 2, 500 instants, which means 2, 500, 000, 000 records in total.

The expert started exploring from within (Fig. 8, left) the particles' trajectories. The speed, acceleration, and power attributes were used to color the trajectories along with random colors for each particle depending on the focus of the expert. As VRT could not display all the points available in the dataset, we had to sample the dataset. A standard sampling example, used several times, was a visualization of 20, 000 particles chosen randomly in the dataset between the instants 500 and 1, 500. No context elements such as 3D models or 2D background were added to this visualization. The expert was primarily interested in identifying changes in the power received by the particle from the surrounding flow.

Case study TRAFFIC: Traffic Flow Simulation

Understanding flows and movements of vehicles in large cities is important to understand the mobility of the residents. This data can lead to reductions in contamination and improvements to the traffic and living conditions. However, such data is usually difficult to collect as not all cars share their coordinates in real time. We collaborated with a Research laboratory specialized in simulation traffic data, in particular with one of their latest dataset over a European city. It contained 6, 121 trajectories of vehicles simulated over 3, 600 instants (1 hour of traffic simulation), making a total of 6, 641, 944 records. Such a dataset enables following individual cars with a very high (simulated) spatial resolution. The experts were interested in identifying congestion areas and sources of traffic that can create it. They also needed a visualization tool for their results to quickly validate the parameters of the simulation. They currently use Ifsttar's Symuvia7 , a specialized simulation tool for traffic with 2D visualizations of the results to generate this dataset, as well as Mathworks' Matlab for all the post-processing and analysis of data.

The expert started exploring the dataset and first used a cylindrical, saber-like selector to extract the vehicles passing through a critical junction of the city and study their global trajectory (Fig. 9). The second step was to reset the selected trajectories and use persistent spheres, strategically placed on main junctions of a district of the city, to extract only these trajectories. He then used the spheredrop functionality to only animate the vehicles on this selection and study the congested junctions. This simulation traffic dataset was intrinsically made of 2D trajectories on a plane, so we chose the speed of the vehicles as a third dimension. During the evaluation session, the coloration of the trajectories was either unique for each trajectory or representative of the speed of the vehicle. Despite the density of points, VRT was able to handle the full visualization and all the vehicle trajectories were displayed. We added the map of the city as a background to give spatial references to the expert.

DISCUSSION

We collected post-study feedback from users regarding the intuitiveness of the tool. Participants filled a questionnaire with a Likert scale ranging from 1 to 5 (with 1 corresponding to the less intuitive command mappings). The most intuitive commands were the movement in space using the Joystick, change of selector / color, and creation of Boolean operands. Change of speed, use of persistent selectors, and manual selection/deselection of queries were found quite intuitive. The reset command and creation mode were also found quite useful by participants, but one was not able either to use nor remember those commands. Performance was rated very good, but it could be improved to load larger datasets, mainly by refactoring the code to use a Data-Oriented Programming (DOP) approach to facilitate multi-threading, as well as moving collision detection computation to the graphics card.

The expert of the case study RUGBY raised some concerns about the additional value of VR in the exploration of the dataset. Indeed, most of the operations that he had done, could have been done in a desktop environment. Playback of the players could be achieved through video streaming of the game, and the identification of the most exhausted players through a dashboard or the use of datasheets. Nevertheless, the expert told us that VRT and VR might bring something new to the field if other attributes (e. g., heart rate) or automatic recognition of similar trajectory patterns were available. This would for instance allow for comparison of data between similar players, as well as a visualization of the players' effort during specific actions (e. g., rucks).

Further exchange with the experts allowed us to find two other flaws of VRT in its current state. First, even though VRT supports very early exploratory analysis, preliminary work is still needed to prepare the datasets. During our user evaluation, we pre-processed datasets to either filter or extract simulation samples as the entire dataset was too detailed. We also added domain-knowledge (e. g., 3D models, 2D background) to contextualize the exploration process. Those steps were purely technical and were achieved after multiple exchanges with domain experts. This was, however, partially addressed in later development stages, as the latest version of VRT facilitates this process by letting experts load their own trajectory datasets through a .json configuration file.

Secondly, exploration of 3D structures requires easy access to hidden, additional attributes, which VRT can for now only show after a reload of the entire visualization. During the case studies, an operator assisted the user to switch z-axis mapping and get details on the datasets information (e. g., names of moving entities) as those features are inaccessible in real-time in VRT. Adding those features has a design implication that requires further research. Such features are needed to fully support analytical processes [START_REF] Chandler | Immersive Analytics[END_REF], along with additional standard interactions such as sorting, deriving, or aggregating values.

One of our main research perspectives is to investigate more diverse shapes for selectors, beyond the three basic shapes we implemented. According to [START_REF] Wills | Selection: 524,288 ways to say "this is interesting[END_REF], two directions could be explored: custom shapes and data-dependent shapes. Custom shapes operate on the geometry of the shape, independently from the data. CAD (Computer Aided Design) tools (e. g., Autocad8 ) already support building such shapes, along with operations such as extrusion (subtraction of a shape by another). Extrusion could be a promising operation to build custom shapes using the 3D models of the scenes, as we have seen those greatly influence selections. For instance, experts of the PROPELLER case study could create a contour of the propeller, by subtracting a cube from the propeller shape instead of adding small spheres together to re-construct this contour. Gestures could be used to create such shapes, and an extensive body of work is already investigated this area (e. g., [START_REF] Vinayak | Shape-It-Up: Hand gesture based creative expression of 3d shapes using intelligent generalized cylinders[END_REF]).

Data-dependent shapes are driven by the data distribution, so that the shape selects groups of data points optimally using the density of the surrounding region [START_REF] Yu | Efficient Structure-Aware Selection Techniques for 3d Point Cloud Visualizations with 2dof Input[END_REF] or non-spatial attributes [START_REF] Jackson | Force Brushes: Progressive Data-Driven Haptic Selection and Filtering for Multi-Variate Flow Visualizations[END_REF]. Combining shapes with data beyond selections has a very high potential. For example, remote selection of trajectories could be facilitated by encoding the density as a visual property of the shape. Similarly, density can be encoded in haptic feedback [START_REF] Prouzeau | Scaptics and Highlight-Planes: Immersive Interaction Techniques for Finding Occluded Features in 3d Scatterplots[END_REF]) to access cluttered trajectories.

Figure 2 :

 2 Figure 2: Overview of a standard session of exploration using VRT. From left to right: (a) SteamVR environment seen while configuring and loading the session; (b) Hand-held selection using a sphere; (c) Persistent selectors used for repeated selections; (d) Filtering trajectories based on previous selections.

  Parameters relative to the hand of the user Shape

  user can create on the fly. Operations are characterized by their type (OR or AND) and the color groups they hold (which can be any combination of the six selector colors).

Figure 3 :

 3 Figure 3: Description of the input of the controllers. Left: (a) Input buttons names, (b) Input mapping of "creation" mode. The controls for "creation" mode slightly differ for different selector shapes. Right (c): Input mapping of "selection" mode.

Figure 4 :

 4 Figure 4: Structure of the procedural mesh used to render trajectories. In green and blue, ribbons; in red, junction triangles at the intersection of ribbons.

Figure 5 :

 5 Figure5: Four phases of the collision detection algorithm. In green, the selector; in blue, "inside"-type districts; in red, "border"-type districts.

Figure 6 :

 6 Figure 6: Case study RUGBY: the expert primarily used VRT to visualize data from a familiar point of view and used queries to single out interesting players. He also used the animation feature to playback players position over space (x, y), and their effort over time (z).

Figure 7 :

 7 Figure 7: Case study PROPELLER: the expert manged to quickly select streamlines of interest around a propeller. He refined his selection to single out streamlines involved in the creation of the vortex and separated flow areas.

Figure 8 :

 8 Figure 8: Case study PARTICLES: the expert studied the changes in power of the particles relative to the shape of the trajectories.

Figure 9 :

 9 Figure 9: Case study TRAFFIC: the expert studied the vehicle trajectories likely to create congestion through the main critical junctions of the city.

Table 1 :

 1 Selector shapes implemented in VRT and their parameters

Table 2 :

 2 Summary of the case studies by datasets properties, by count of unique trajectories, atoms (records) and instants (temporal time points) used for playback. Attributes are the ones available in the dataset for spatial mapping, for which dataset either already have a 3D structure (PROPELLER, PARTICLES

https://unity.com/

https://github.com/ValveSoftware/openvr

https://www.paraview.org/

https://www.samsung.com/us/computing/hmd/ windows-mixed-reality/

https://unity.com/

https://www.mathworks.com/products/matlab.html

https://www.licit.ifsttar.fr/linstitut/cosys/ laboratoires/licit-ifsttar/plateformes/symuvia/

https://www.autodesk.com/products/autocad/overview

CONCLUSION

We presented VRT, a tool for exploring and filtering large trajectorybased datasets using virtual reality. It extends the design space of volumetric probes by introducing a set of configurable 3D shapes and logical operations for use in intuitive selection. We evaluated its use case with domain-experts who sought to quickly grasp an overview of their dataset, as well as to extract particular regions or trajectories of interest. Our results show the ease of use and expressiveness of the 3D geometric shapes implemented in VRT as selectors. VRT was found to be particularly useful for progressively refining selections from extensive trajectory datasets to small subsets of outlying behavior. It also demonstrated its use as a powerful tool for conveying the structure of normally abstract datasets for communication purposes.