Amine M Falek

Antoine Gallais

Cristel Pelsser

Sebastien Julien

Fabrice Theoleyre

To Re-Route, or not to Re-Route: Impact of Real-Time Re-Routing in Urban Road Networks

Keywords: road networks, route planning, real-time data, vehicle re-routing, traffic prediction

Route planning represents a major challenge with a substantial impact on safety, economy, and even climate. An ever-growing urban population caused a significant increase in commuting times, therefore, stressing the prominence of efficient realtime route planning. In essence, the goal is to compute the fastest route to reach the target location in a realistic environment where traffic conditions are time-evolving. Consequently, a large volume of traffic data is potentially required and the route continuously updated. We thereby address the re-routing problem to answer questions such as when, how often, and where is re-routing worthwhile. We base our study on a real dataset, comprising the travel times of the road segments of New York, London, and Chicago, collected over three months. By exploiting this dataset, we implement an optimal algorithm, able to mimic ideal predictions of road segment speeds in the network. Thereby, allowing us to compute the lower bound of traveltime to serve as a reference against other routing techniques. Mainly, we quantify the achieved travel-time gain of a static, no re-routing, and continuous re-routing strategies. Surprisingly, we find that traffic conditions are sufficiently stable for short time windows, and re-routing a vehicle is very seldom useful when exploiting accurate statistics at departure time. Typically, real-time re-routing should only be triggered during rush hours, for long routes, passing through well-identified road segments.

Introduction

Road network traffic congestion is a well known common cause of anger and frustration. From an economic point of view, congestion has an even more drastic impact. The 2015 urban mobility scorecard [START_REF] Schrank | Scorecard, urban mobility[END_REF] reports that urban Americans traveled an extra 6.9 billion hours and had to purchase an extra 3.1 billion gallons of fuel. To reliably arrive on time, travelers had to plan 48 minutes for a trip that should last only 20 minutes in light traffic. The estimated cost of congestion is steeply increasing since reported in 1982, with a cost of $42 billion against a total of $160 billion in 2015. While solutions exist to control traffic lights dynamically [START_REF] Li | Multi-objective optimal predictive control of signals in urban traffic network[END_REF], it is highly probable that congestion would still occur.

Route planning algorithms [START_REF] Bast | Algorithm engineering, chapter Route Planning in Transportation Networks[END_REF] compute a route, which consists of a sequence of road segments between a departure and arrival locations, and a traveltime, denoting its associated end-to-end cost. Historically, mobile navigation devices were used to guide the driver by autonomously computing a suitable route. With the wide adoption of smartphones, though, many applications nowadays benefit from the cloud where all computations are performed [START_REF] Li | Road disturbance estimation and cloud-aided comfort-based route planning[END_REF].

Route planning requires traffic information (estimated speed, vehicle counts) gathered from various sensors and probes within the network. Some mobile navigation devices rely on the median recorded travel-times of a set of monitored road segments to predict congestion. Smartphones and vehicles which usually embed GPS devices are also exploited by regularly relaying traffic measurements to the cloud so that a real-time model of the road network can be constructed [START_REF] Ahsani | Quantitative analysis of probe data characteristics: Coverage, speed bias and congestion detection precision[END_REF]. Realtime traffic information is particularly valuable to reduce the cost of urban freight transportation [START_REF] Flamini | The value of real-time traffic information in urban freight distribution[END_REF].

Prediction as a service aims at predicting the travel time of each road segment, based on past measurements [START_REF] Wu | Urban traffic flow prediction using a spatio-temporal random effects model[END_REF]. That way, a vehicle would use an alternative, faster route if congestion has been predicted along its primary route. Uncertainty may also be considered to compute a route with a given latest time of arrival [START_REF] Lee | A route guidance system considering travel time unreliability[END_REF]. While long-term prediction algorithms exist in the literature [START_REF] Chen | Long-term travel time prediction using gradient boosting[END_REF], short-term predictions are still challenging. Traffic jams are complicated to predict [START_REF] Hu | Real-time traffic jams prediction inspired by biham, middleton and levine (bml) model[END_REF], and their impact on travel time depends on various local factors (e.g., speed limit, type of street, neighboring local roads).

While vehicle re-routing may reduce the impact of congestion, relying on real-time data can be computationally expensive. Computing a route, directly on a small embedded device is inconvenient as traffic data must be downloaded first, which may correspond to a large volume of data when the target location is geographically far away. Practically, this means that hundreds of weights have to be collected periodically, even if the target is in the same urban area. This represents a massive amount of data when considering a large collection of users. Alternatively, the route computation can be executed directly in the cloud: centralized servers reply in real-time to queries. Thereby continuously re-evaluating the route of each vehicle until it reaches its destination. Consequently, the load in the cloud is roughly proportional to the sampling rate used to refresh the real-time data. In particular, it becomes challenging to exploit route planning algorithms that rely on pre-processed data because of the continuous traffic changes measured on the network.

In this paper, we quantify the benefit of using dynamic shortest path algorithms that re-route vehicles when congestion increases. Indeed, alternative paths may provide a faster route, but can only be identified when using real-time information. For this purpose, we exploit a real dataset comprising the travel times of the road segments of several cities (i.e., New-York, London, Chicago, and Cologne). To compare simulations with these real datasets, we also used the TAPAS (simulated) dataset [START_REF] Uppoor | Generation and analysis of a large-scale urban vehicular mobility dataset[END_REF]. The contributions of this paper are as follows:

(1) we quantify the travel-time gain when using real-time data to re-route vehicles, compared to a no re-routing approach that prohibits diverting from the path evaluated at the departure. Our dataset highlights that re-routing is very seldom required real conditions, even during rush hours;

(2) we provide an optimal algorithm to compute a lower bound for the travel time between any pair of locations. The algorithm replays the real dataset to mimic ideal predictions. The gain of using ideal predictions is below 10% compared with a continuous re-routing solution, even for the worst route;

(3) we compare the impact of re-routing based on two types of datasets (a real dataset vs. the simulated TAPAS dataset). Surprisingly, and contrary to current belief, we obtain very different behaviors when studying re-routing strategies. Simulations tend to exacerbate the randomness of travel time. Thus, simulations seem to not accurately capture the complexity of urban road network dynamics, proving the relevance of exploiting real datasets;

The remainder of this paper is organized as follows. Section 2 provides the related work. We then present the routing strategies used in our evaluation in section 3, and detail our models and assumptions. We explain our methodology in section 3.3, as well as the detailed description of our datasets. Section 4 presents our comparative analysis of the travel time gain of each routing strategy. We conclude and discuss future work in section 5.

Related Work

Road networks are usually abstracted through graph data structures where vertices and edges represent physical intersections and road segments, respectively. Edge weights are labeled with various metrics, such as distances or travel times required to join two vertices along a given edge.

Re-routing in road networks

The field of shortest path algorithms flourished in the last decade, with continuous improvement in execution times. Pre-processing consists of transforming the initial graph to reply efficiently to route queries [START_REF] Bast | Algorithm engineering, chapter Route Planning in Transportation Networks[END_REF]. However, using real-time information implies that the pre-processing phase has to be re-executed. [START_REF] Gmira | Managing in real-time a vehicle routing plan with time-dependent travel times on a road network[END_REF] propose to construct a delivery plan related to the Dynamic Vehicle Routing Problem. Their solution collects speed values in real-time, and update the path for a vehicle only if it becomes infeasible. However, they do not investigate the sub-optimality cost, i.e., a route is not updated if no constraint is violated, even if its travel time is not the smallest one.

Understanding when to re-route vehicles is critical to reducing the re-computation cost. [START_REF] Pan | Proactive vehicular traffic rerouting for lower travel time[END_REF] propose an infrastructure-based approach: when congestion is detected, the system asks nearby vehicles to re-compute their shortest route. Congestion threshold, as well as the set of vehicles to re-route, impact the efficiency of this proposal significantly.

In the Dynamic Shortest Path problem (DSP), a re-routing algorithm tries to update the shortest path to handle multiple edge weight updates [START_REF] Chan | Shortest path tree computation in dynamic graphs[END_REF]. Such an approach is much more efficient than re-executing the shortest path algorithm from scratch.

While these approaches aim to devise the most accurate strategy to trigger route computation, the objective of this paper is to instead quantify the gain in travel-time when authorizing redirections or exploiting ideal predictions.

Real-time data sources

Collecting travel-time measurements of each road segment in real-time is a challenging objective. We may use the GPS trajectories of a collection of vehicles to deduce the specific travel time of each road segment [START_REF] Duan | Improved deep hybrid networks for urban traffic flow prediction using trajectory data[END_REF][START_REF] Sanaullah | Developing travel time estimation methods using sparse gps data[END_REF]. For this purpose, each trajectory has to be mapped to a set of road segments while minimizing the mismatch ratio [START_REF] Falek | Unambiguous, real-time and accurate map matching for multiple sensing sources[END_REF]. [START_REF] Ladino | Travel time forecasting from clustered time series via optimal fusion strategy[END_REF] propose to merge heterogeneous data sources (e.g., cameras, induction loops), to create a combined, more accurate dataset. Imputation techniques [START_REF] Chen | Tripimputor: Real-time imputing taxi trip purpose leveraging multi-sourced urban data[END_REF] help to reconstruct missing data (e.g., a road segment is not crossed for short time-period).

Recent approaches propose to adopt a synthetic model. Typically, the SUMO simulator [START_REF] Behrisch | Sumo-simulation of urban mobility[END_REF] is used to generate the mobility pattern of a large number of devices, using realistic urban points of interest. Travel and Activity PAtterns Simulation (TAPAS) was used to generate the well-known TAPAS-Cologne dataset [START_REF] Uppoor | Generation and analysis of a large-scale urban vehicular mobility dataset[END_REF]. However, to the best of our knowledge, no study has been conducted to verify the accuracy of these simulations. In [START_REF] Kamga | A methodology to estimate travel time using dynamic traffic assignment (DTA) under incident conditions[END_REF], the authors, use simulated data from VISTA [START_REF] Ziliaskopoulos | VISTA, Visual Interactive System for Transportation Algorithms[END_REF] to determine the impact of incidents on travel times. Other traffic simulation software such as Dynameq (Dynameq, 2020) and TRANSIMS [START_REF] Barrett | Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the transims router[END_REF] provide simulated datasets of the travel times in a road network.

In this paper, we highlight in Sections 4 and 4.4 the differences obtained between the different approaches when using real (measurement-based) datasets vs. the TAPAS dataset.

Traffic prediction

Recently, traffic prediction has received much attention in order to provide prediction as a service [START_REF] Liebig | Dynamic route planning with real-time traffic predictions[END_REF]. These techniques try to consider the inherent characteristics of road networks (e.g., flow conservation) to predict future trends accurately. Predictions rely on computationally intensive techniques such as, e.g., bee colony optimization [START_REF] Dell'orco | Bee colony optimization for innovative travel time estimation, based on a mesoscopic traffic assignment model[END_REF], or spatiotemporal random field [START_REF] Liebig | Dynamic route planning with real-time traffic predictions[END_REF]. Alternatively, [START_REF] Wang | A simple baseline for travel time estimation using large-scale trip data[END_REF] propose to predict end-to-end travel times directly but limiting its practical interest for route computation.

However, congestion is highly variable: [START_REF] Coifman | Distributed surveillance on freeways emphasizing incident detection and verification[END_REF] highlight that 48% of the congestion is difficult to predict. [START_REF] Li | Limits of predictability for largescale urban vehicular mobility[END_REF] concludes that accidents are impossible to predict and even complicated to detect early.

Since existing prediction techniques are partly inaccurate and computationally intensive, we aim in this paper to quantify its gain: if individual travel times for each road segment can be ideally predicted, is the end-to-end travel time gain significant?

2.4. Evaluating routing performance on dynamic road networks [START_REF] Smith | A SUMO based evaluation of road incidents' impact on traffic congestion level in smart cities[END_REF] evaluate the impact of accidents on traffic congestion using a vehicular simulation and highlight the need for using actual traffic conditions to predict the travel time. [START_REF] Wang | Comprehensive Performance Analysis and Comparison of Vehicles Routing Algorithms in Smart Cities[END_REF] provide a performance analysis of different route planning algorithms (i.e., Dijkstra, static A * , dynamic Dijkstra, and dynamic A * ) in smart cities. Their experiments use the TAPAS-Cologne dataset [START_REF] Uppoor | Generation and analysis of a large-scale urban vehicular mobility dataset[END_REF], which was built by generating traffic demand using TAPAS and Gawron's algorithm for traffic assignment. They consider a rush hour during a weekday to evaluate the impact of traffic jams. [START_REF] Mcardle | City-scale traffic simulation from digital footprints[END_REF] attempt to simulate traffic in the Greater Dublin region. Typically, each vehicle selects its destination according to a radiation model, to model probabilities of interactions between different regions.

Unfortunately, all these performance comparisons use simulations with synthetic models. The objective of our paper is instead to use real datasets, with the actual travel time for each segment, at any instant, during very long periods (i.e., a few months).

Methodology

A route planning solution identifies a path to follow for a vehicle. Most solutions can be classified into:

(1) embedded devices help to compute a route, sometimes after having downloaded real-time data about the congestion of the road network [START_REF] Wang | An improved a* algorithm for traffic navigation in real-time environment[END_REF]; (2) cloud-based infrastructures receive a collection of queries from the vehicles that they have to handle in real-time [START_REF] Li | Road disturbance estimation and cloud-aided comfort-based route planning[END_REF]. Continuously reconsidering the route because of real-time data is also expensive in a cloud serving a large number of customers, where additional resources have to be provisioned.

Each route planning strategy has to solve individual queries, returning a route with minimal travel time. Formally, we define a query as q = (s, d, t s )|s, d ∈ V and t s ∈ T , where s, d and t s represent the departure location, the destination location and the departure time respectively. Likewise, a route is defined as an ordered list of vertices (road segments) in the graph.

In this paper, we consider the following strategies, ordered by the volume of resources (bandwidth and computation) they require:

(1) static: we do not have any knowledge of the actual traffic conditions (i.e., no data is exchanged); (2) no re-routing: we know the travel time of each road segment precisely just before the vehicle leaves its starting point. For the sake of limiting computational cost, the vehicle does not reconsider its decision after departure; (3) continuous re-routing: we have continuous access to the most recent real-time data.

A vehicle may be redirected to a different (shorter) route as soon as traffic conditions change; (4) prediction based routes: we are able to predict the traffic conditions perfectly.

Consequently, we can identify the shortest ideal route, which constitutes our lower bound;

Assumptions and Model

A road network is defined by a list of road segments. Each of them consists of a set of consecutive coordinates (latitude and longitude) that define its shape. We use a dynamic directed graph G T = (V, E, W T ) to represent the road network, where v ∈ V is a vertex representing a physical intersection of two or more road segments, e ij ∈ E a directed edge from vertex i to j, and w ij (t) ∈ W T the weight assigned to e ij , as a function of time t ∈ T .

r i = {u, v, .., w} Defines a road segment R = q(s, d, t s )
Route in reply to the query from vertex s to d at timeslot

t s R = {u, v, w, .., z} A route is an ordered set of vertices T T ime[q or R]
Travel time of a query q (or a route R) algo

Designates one of four algorithms: static/no rerouting/continuous re-routing/ideal T T ime [q, algo] Travel time of q using algorithm algo

t ≥ 0 ∈ R Represents the time in seconds 0 ≤ t k ≤ T ∈ N
Timeslot index of a real-time data update symbols used throughout the paper.

For the sake of clarification, we use the term dynamic to refer to a graph whose structure remains the same (no edges are deleted or inserted), but edge weights change over the period T . We consider road networks with traffic congestion, but we neglect the new roads that may appear.

We exploit a dataset where the speed of each road segment is monitored periodically and synchronously. Thus, we denote by timeslot the discretized time, during which the speeds for all the road segments remain unchanged. An edge weight w ij (t) = d ij /s ij (t) represents the travel time in seconds required to join the vertices i and j, where d ij and s ij (t) represent the length of the edge e ij and its corresponding speed at time t respectively.

A road segment r i = {u, v, w, .., z} ∈ V consists of an ordered list of vertices in the graph. When the speed on the road segment r i changes, it affects the weights of all the edges associated with that road segment. Hence, in our implementation, every edge in the adjacency list points to a specific road segment in the road segments map.

Route Planning Strategies

We now describe in more detail the route computation algorithms we use in the rest of the paper to evaluate the importance of real-time speed data along with road segments. Real-time information implies that vehicles may change their route when congestion occurs. Practically, drivers may be progressively aware of current incidents because they use different data sources [START_REF] Kucharski | Simulation of rerouting phenomena in dynamic traffic assignment with the information comply model[END_REF]. We neglect here the mutual impact of their decisions, i.e., travel-time may increase if all the drivers take the same decision. We model in the rest of this section different families of routing algorithms, taking into consideration traffic information.

Each strategy corresponds to a given travel time formulation. The here presented route planning strategies (i.e., static, no re-routing, continuous re-routing, and ideal prediction based) respectively deal with travel times that are either time-independent (i.e., no knowledge of traffic conditions), evolution-independent (i.e., knowledge of traffic conditions at the initial computation time only), time-aware (i.e., knowledge of initial traffic conditions and regular updates throughout the journey) or ideal (perfect forecast of traffic conditions).

Static Route Planning

We assume here the system has no knowledge about traffic conditions (e.g., an embedded device disconnected from the Internet). It represents our worst but thrifty strategy and provides a baseline for comparison. Thus, it will use the maximum speed for each road segment to compute the fastest route. The weights are time-independent, and hence w ij represents the travel time from vertex i to j, where s ij is the speed limit in this particular case. For a given query q(s, d, t s ), the departure time t s is meaningless since the algorithm would always return the same route for a departure from s toward the destination d. We use Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF] to compute the route with the shortest travel time.

No re-Routing Route Planning

The system has here a complete knowledge of the travel times but never reconsiders its decision. It mimics an embedded navigation system that is disconnected after departure or cloud infrastructure that executes the query only once. Thus, we apply the same strategy as previously, just executing Dijkstra's algorithm, with the travel time of each road segment at departure. This way, we can quantify the gain of using up-to-date information before departure.

Continuous re-Routing Route Planning

We continuously reconsider the routing decision by trying to compute a better route with shorter travel time, modeling the approach proposed by [START_REF] Chen | Risk-averse autonomous route guidance by a constrained a* search[END_REF]. This strategy helps to bypass congested areas when they appear, but it also consumes more resources. If the computation is delocalized, the device has to retrieve all the travel times periodically for its area. In a cloud, this means that the query has to be re-executed continuously, consuming computational resources.

Let ∆t be the sampling rate of the real-time traffic data. The route planning algorithm will re-compute the optimal route toward the destination at each crossroad. We use a dynamic version of Dijkstra's algorithm as detailed in algorithm 1:

(1) we use a time-dependent graph model, where the weight of each edge is time-variant.

When executing Dijkstra's algorithm, we pick the most recent weights; (2) the route is reconsidered when a new data sample occurs, i.e., it corresponds to an update of speed data. In that case, the shortest route to the destination from the current position is computed (line 4);

(3) we traverse the graph, following the current route (lines 7-17). We have to verify if we can reach the next crossroad before the next speed sample occurs (line 11); (4) if we cannot, we have also to consider the upcoming speed updates to reflect the actual travel time (line 14). ( 5) when a new sample occurs, we set the upcoming crossroad as the new position (line 18) from which we re-evaluate the route (step 1). This version accommodates any sampling rate. This way, we can compare the impact of the data accuracy on the travel time.

Ideal Prediction Based Route Planning

As mentioned earlier, traffic congestion forecasting is a technique used by most advanced route planning algorithms. By incorporating predictions, one could predict recurrent traffic jams, and thus, plan the route accordingly at departure time.

We propose here to model such prediction-based routing algorithm [START_REF] Liu | Lstm network: a deep learning approach for short-term traffic forecast[END_REF]. More precisely, our goal is to quantify the maximal benefit attainable when using a perfect forecast. Thus, we use an ideal prediction algorithm to compute the maximum gain achieved by any prediction-based routing algorithm. To do so, we depart a vehicle in the past by replaying the recorded measurements a posteriori.

We propose to use Algorithm 2:

(1) we first insert the departure vertex into the set of settled vertices (line 1) as the triplet (vertex, parent, arrival time). We insert its neighboring vertices (i.e., head vertices of outgoing edges) into a priority queue keeping the vertex with earlier arrival time at the head;

(2) at each iteration, we poll a vertex v from the queue and insert it into the settled set (line 5);

Algorithm 2: Optimal Route with ideal predicion routing.

Data: departure vertex (s), destination vertex (d), departure time (ts) Result: shortest route as an ordered list of vertices (route) /* settled is a list containing all vertices for which the shortest route was found */ 1 settled ← {(s, s, ts)}; /* (the settled vertex, its parent, arrival time) */ /* priority queue holds vertices that we either did not visit yet (∞) or for which we did not find the shortest path */ (3) we compute the travel time required to reach each of its neighbors w (lines 7-18).

2 queue ← {(v, -1, ∞)|v = s ∈ V }; 3 route ← {d}; /*
In particular, we traverse each edge vw , and we update its speed when a new sample occurs before reaching the next crossroad (lines 15-17); (4) we re-insert w into the queue with its corresponding parent vertex v and the updated arrival time t w (line 18); (5) when the destination vertex is settled, we construct the route by browsing backward all the parent vertices starting at the destination until we reach the departure vertex (lines 20-23).

Evaluation Workflow

To fairly compare different route planning strategies, we need to compute enough routes using each strategy to cover most roads in the road network. To do so, we generate a massive number of queries and solve each of them with our four routing strategies. Hence, for a given route R = q(s, d, t s ), by varying the departure time t s , we can track the changes of R as a vehicle experiences congestion along the route from s to d, at different times of the day.

Figure 1.: Workflow for the stretch factor quantification of not using real-time data.

We insist on the fact that we do not simulate the deployment of multiple vehicles on the road network at once. Indeed, we do not have any means to incorporate the added congestion due to those vehicles, as one might expect in a mobility simulation tool. Instead, we consider each query as representing a probe vehicle, to measure the impact of the measured traffic (from our datasets) on its route (and not the inverse).

We apply here the following workflow to quantify the interest in exploiting real-time data (Figure 1):

(1) we use real vs. simulated (TAPAS) datasets, and emulate different sampling rates (from 1 to 30 min) by subsampling the datasets;

(2) we randomly select 1000 pairs of source and destination vertices in each road network;

(3) for every (source, destination) pair, we generate a broad set of queries at different timestamps (every 1 min for the simulation and every 10 min on the real dataset); (4) for each query, we execute each route planning strategy to extract the route to follow;

(5) we then emulate a vehicle moving along the route returned by the algorithm in the previous step. This way, we can accurately evaluate the actual end-to-end travel time for each strategy at different times of the day.

Finally, we use the previous results to compare the static, no re-routing, continuous re-routing and ideal prediction strategies, detailed in sections 3.2.1, 3.2.2, 3.2.3 and 3.2.4 respectively.

We ran all our experiments on the High-Performance Computing (HPC) at the University of Strasbourg. We generated thousands of jobs that were executed on Intel Xeon Sandy-Bridge nodes with 16 cores and 64GO of RAM. The combined computation effort required approximately 50,000 CPU-hours.

Datasets

To evaluate the impact of the different route planning strategies, we use real travel times for a broad set of road segments. Additionally, we also use a simulated dataset for comparison purposes. We rely upon:

s1 d1 s2 d2 s3 d3 0/1 1/1 2/3 1/2 1/1 2/3 0/1 1/1 1/1 1/1 1/2 0/1 1/1 Diverging vertex Route using ideal prediction 0/1 0/1 0/1 0/1 0/1 1/1 1/1 1/1 1/1 0/1 1/1 1/1 1/1 1/1 1/1 0/1 0/1 div. routes total routes = 2/3
Route using continuous re-routing Diverging route segments (1) the simulated TAPAS dataset: [START_REF] Uppoor | Generation and analysis of a large-scale urban vehicular mobility dataset[END_REF] focuses on a small German City (Cologne), during a weekday (24 hours). It relies on the simulator SUMO to simulate the traffic from a large set of emulated vehicles, pseudorandomly selecting pairs of sources and destinations (e.g., home, office). We run the simulation using SUMO to generate a dump file specifying the speed along every road segment at 1-sec intervals. We subsample the dataset to get the same sampling rate used in the real dataset.

(2) a real dataset: we use the dataset of three major cities (New York, London, and Chicago) for which HERE (HERE Technologies, 2018) provides a fine-grain estimation of the speeds for the most important road segments. We collected three months (i.e., from September 21 st to December 18 th 2017) worth of data at a sampling rate of 1 min, which allows an accurate estimation of the actual travel time experienced by users. Additionally, we also use the city of Cologne, for the same geographical area and during the same time window as the TAPAS dataset for a fair comparison.

Metrics for the Performance Evaluation

We now detail the metrics we used to compare the different routing strategies.

Identification of congestion

To identify the rush hour period, we compute the Congestion Factor (CF ) of each query as the ratio of the optimal travel time (using the ideal routing strategy) to the free-flow travel time. In the TAPAS dataset, the free-flow speed of a road segment corresponds to its speed limit. In the real dataset, the free-flow speed was provided as the average measured speed during low-volume periods and depends on the road characteristics such as lane width.

Hence, given a query R = q(s, d, t s ), the congestion factor of the end-to-end route R is defined as:

CF [R] = T T ime[R, ideal] T T ime[R, f reef low] (1)
To analyze more clearly the behavior of each routing strategy, we need to classify the routes according to their congestion level. For this purpose, we define for each route its traffic flow (TF) metric, which represents the congestion of its most congested road segment. For each route R = q(s, d, t s ), we measure the level of congestion of each road segment r i ∈ R. More precisely, the congestion level corresponds to the relative speed decrease compared with free-flow conditions:

T F [r] = max speed(r i , t) speed f f (r i ) ri∈R (2)
where speed(r i , t) corresponds to the speed at time t for the road segment r i , and speed f f (r i ) to its speed in ideal conditions (i.e., free flow). T F = 1 corresponds to free-flow conditions, and T F = 0 corresponds to a complete halt of all vehicles on one of its road segments.

Travel Time Stretch and Gain Factors

We will use the stretch factor in travel time to compare the different strategies. The ideal strategy provides, by definition, the lowest end-to-end travel time and represents our lower bound. The stretch factor for a query q(s, d, t s ) is defined as:

SF [q] = T T ime[q, algo] T T ime[q, ideal]) (3)
where T T ime[q, algo] represents the end-to-end travel time for the route returned by the algorithm algo (static/no re-routing/continuous re-routing/ideal) for the query q. Notice that SF [q] ≥ 1, and hence, the higher the stretch factor gets, the worse is the performance of algorithm algo compared to the ideal.

To specifically focus on the gain achieved by re-routing vehicles after their departure, we also compute the gain factor. It corresponds to the relative gain in travel time through the path selected by the prediction-based and the redirecting strategies compared with the static one (i.e., without redirection after the departure).

Identification of divergences

We focus on the continuous re-routing strategy to precisely determine where a vehicle is practically re-routed because the congestion has changed. Practically, we identify the divergence vertices, i.e., geographical locations where the next edge is different with or without rerouting. Formally, given two routes R 1 and R 2 that share at least the same first and last vertices, we define their diverging vertices as the set {j ∈

V | ∃i, k, w ∈ V | (e ij , e jk ) ∈ R 1 ∧ (e ij , e jw ) ∈ R 2 ∧ k = w}.
We construct a grid overlay where each cell is a 10 × 10 square meters. We consider a large number of route queries (pairs of sources/destinations). We execute the route computation for each query at different instants covering to cover the whole dataset. For each cell cell i , we consider all the routes that cross this cell. We compute its divergence ratio (0 ≤ div[cell i ] ≤ 1) as the ratio of the number of diverging routes to the number of total routes. A route is diverging if the routes with and without the re-routing strategy are different for at least one instant of the dataset. Hence, a cell with a high divergence ratio means that more vehicles are re-routed when crossing this cell. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Some cells may be traversed by only a few routes, leading to statistically meaningless results. Thus, we only consider cells traversed by a significant number of routes (300 in this case).

Results

In a road network with no congestion, all routing strategies should return optimal routes. Hence, our first goal is to distinguish the critical parts of the dataset by identifying the rush hours in each city. The remainder of the paper will solely focus on evaluating the presented routing strategies during rush hours only.

We also provide a visual, interactive interface to showcase a sample of the NYC dataset and obtained results at http://its-icube.com/. Each query is represented individually, to visually represent the temporal characteristics of each route all along the week. In particular, we can identify the diverging vertices, as well as the evolution of the congestion.

Absolute Travel Time and Rush Hours

Figure 3 illustrates the CF in the Cologne TAPAS dataset. As expected, we identify the rush hours in the morning (6:00-9:00) and afternoon (15:00-19:00) of the working day. The optimal travel time is almost six times longer than the free-flow travel time during these two periods.

Figure 4 illustrates the congestion factor for the experimental datasets. We focused uniquely on Thursday, Friday, Saturday, and Sunday to provide readable charts (the remaining weekdays display similar characteristics to Thursday). We can derive the following observations:

(1) some queries benefit from travel times smaller than the free-flow. They correspond to very short distances (a few hundred meters) when streets are empty;

(2) we observe the rise in congestion starting at 6:00 and intensifying in the afternoon with a peak at 17:00.

(3) we can easily make a distinction between working days and weekends, which are much less congested.

Similar observations hold for London and Chicago.

Travel Time Stretch and Gain Factors

We now compare the achieved travel time for each routing strategy. In particular, Fig. 5 illustrates the stretch factor for the TAPAS dataset (left) vs. the real datasets (right). The stretch factor denotes the travel time increase compared with the shortest path, with an ideal dataset (i.e., with ideal predictions). We clipped the plot at SF = 3, as it reaches ≈ 6 in the simulation.

The static routing strategy provides, as expected, the longest travel time. However, the distribution is significantly different between the simulation and the real dataset. With TAPAS, 28% of the queries have an SF greater than 1.5. In contrast, we only report 1.6% of the queries in Cologne and approximately 4% in New York, London, and Chicago. In Cologne, the SF using either the no re-routing or continuous re-routing strategies yields optimal travel times most of the time. Only ≈ 12% of the queries are characterized with a stretch factor greater than 1. In TAPAS, though, more than 75% of the queries have a SF > 1 even when using continuous re-routing. Moreover, for several queries in the simulation, travel time is worse when using continuous rerouting rather than no re-routing. The high variability of congestion profoundly affects re-routing in the simulation as a vehicle might engage in a seemingly faster alternative route only to become more congested than the initial route. In New York, London, and Chicago, approximately 75% of the queries benefit from ideal travel times when using continuous re-routing.

To further comprehend when continuous re-routing is advantageous, we pinpoint the travel time gain it offers (compared to no re-routing) based on the congestion level (Fig. 6). We normalize the travel time difference of using continuous re-routing (and ideal routing for reference) over the no re-routing strategy.

As expected, re-routing is relevant only when congestion occurs. The gain is, however, often negligible when the actual speed is close to 50% the speed limit. For very congested routes (T F ≤ 10%), we reduce the travel time significantly by re-routing the vehicle. Exploiting ideal predictions allows the gain to be even higher, to choose a better route: the best route is selected, before the congestion's increase.

Conclusion: continuous re-routing significantly reduces travel time for most queries. In New York City, we can reduce by 15% (1st quartile), which seems to justify the usage of a smart route planning strategy. However, predictions only marginally decrease the travel time for all the measured datasets. The traffic conditions seem to evolve smoothly, and redirecting the vehicle when the congestion occurs appears as a sufficient strategy. Clearly, continuous re-routing is essential to re-route around highly congested road segments. When the road network is less congested (T F ≥ 40%), the gain factor quickly converges to zero.

Impact of Sampling Rate on Travel Time

For the continuous re-routing algorithm, the sampling rate ∆t impacts both travel and execution times. For fine-grained values, the algorithm is aware of the latest changes in traffic congestion and can re-route accordingly. However, it may also re-compute unnecessarily the routes, increasing execution time significantly. Our goal is thus to determine the right sampling rate for a good travel/execution time trade-off.

By varying the sampling rate ∆t from 1 to 30 minutes, we re-compute the queries we generated using continuous re-routing. We only consider queries with a travel time T T ime[q] ≥ 60min to make sure re-routing has potentially occurred for the largest sampling rate ∆t = 30.

Figure 7a illustrates the distribution of the stretch factor as a function of the sampling rate. Obviously, a higher sampling rate means inaccurate speed values. Thus, the route planning strategy will take sub-optimal decisions. However, the re-routing strategy performs well, even for average sampling rates. Surprisingly, in New York, for instance, the road network variations can be efficiently handled even if measurements are reported every 10 minutes. Figure 7c illustrates the execution time for New York. At ∆t = 10min, the execution time drops from ≈ 500ms to less than 50ms, which provides a good trade-off between travel time and execution time. Of course, there exists a myriad of algorithmic techniques in the literature, capable of significantly reducing the execution time. Considering that ∆t dictates the number of times we have to re-compute the route, we are only interested here in the rate of the change of execution time as ∆t increases.

Figure 7b represents the execution time for the TAPAS dataset. In complete contradiction with the real dataset results, the stretch factor distribution is almost the same regardless of the sampling rate value. Again, we observe that congestion changes too fast throughout the whole road network (even at ∆t = 1min), causing the algorithm to inevitably re-route through highly congested road segments.

Conclusion: we can accommodate average sampling rates when using real-time data. Five minutes provide enough accuracy (for all our road networks) to identify the best routes while reducing the computational or bandwidth cost.

Route Divergence Patterns

Figure 8 illustrates the distribution of the diverging vertices in each road network, as defined in section 3.5.3. A divergence vertex corresponds to a crossroad where at least one vehicle has been re-routed to reduce travel time (i.e., traffic congestion has changed since its departure). The divergence ratio counts the ratio of routes (source/destination) for which the path diverges when crossing the cell, with and without the re-routing strategy.

The road networks in the real dataset exhibit a small set of diverging vertices with The yellow dots depict diverging vertices with a divergence ratio ≥ 0.5. a high divergence ratio, typically almost all diverging vertices have a divergence ratio ≤ 0.5. This means that only 50% of the routes that cross these cells are re-routed at least once during the whole duration of the dataset. Inversely, the simulated dataset (with TAPAS) exhibits a significant number of diverging vertices. TAPAS generates pseudorandomly the traffic and estimates the level of congestion, and the speed for each road segment. It seems that TAPAS exhibits a very different pattern compared with the real datasets.

Figure 9 summarizes the obtained divergence patterns for both the TAPAS and real datasets. We only represent here New-York City since other real datasets behave similarly. Each graph corresponds to a heat map (a red cell corresponds to a cell with a high divergence ratio). We also highlighted the divergence vertices with a divergence ratio ≥ 0.5 (yellow dots).

Remark: while we identify many cells with a high divergence ratio for all the graphs, we can, however, still make a distinction between the TAPAS and the real datasets. In the TAPAS dataset of Cologne, the divergence seems present everywhere. We assume that this behavior comes from the fact that the source/destination of each vehicle is picked pseudorandomly, and the shortest route is used. Individual routing strategies seem more complex, and the trips seem to follow a uniform distribution.

Conclusion: many cells exhibit a large divergence ratio, and we cannot directly use this metric to trigger the route re-computation efficiently. However, we identified only a small number of diverging vertices. Thus, we would be able to execute the computation only when the route crosses these specific points, making the computation much more efficient. We would reduce the processing load without increasing the end-to-end travel time.

Conclusion & Perspectives

Modern intelligent systems guide vehicles through the fastest routes to avoid congested areas. However, they need to exploit real-time data, where the speed of each road segment has to be known precisely. Even worse, this real-time feature has a cost, in bandwidth (data collection), and computation (re-computation of the route to the destination). Interestingly, the no re-routing strategy provides close to ideal travel times most of the time. Using the continuous re-routing strategy can further improve travel time by avoiding very congested areas when they appear.

We also used a simulated dataset (TAPAS) that leads to very different results concerning the travel time and the re-rerouting gain. TAPAS seems not able to capture the road network characteristics accurately, and particularly its dynamics. This observation speaks in favor of working with real datasets to model realistic environments.

In future work, we plan to enhance the use of real-time data in our route planning strategies. We considered here that each vehicle triggers a route computation after reaching each crossroad (if the speed has changed). We may improve the re-routing strategy by triggering a computation only when the routes may diverge. We identified specific crossroads where vehicles have a higher probability of being re-routed. We only considered selfish decisions in this study, i.e., each vehicle decides by itself when it should re-compute its route to the destination. To reduce the congestion, we may consider a more collective objective, redirecting some of the vehicles . Thus, we expect to propose a strategy that could also consider the gain in travel time, depending on the characteristics of the route and of the local area.

Figure 2 .

 2 Figure 2.: Diagram illustrating the process of computing the divergence ratio of a cell.

  Figure 3.: Congestion Factor distribution in Cologne simulation, Germany, over a period of 24 hours.

Figure 5 .

 5 Figure 4.: Congestion Factor distribution in New York, based on weekday and daytime over a period of 3 months.

Figure 6 .

 6 Figure 6.: Travel time gain of continuous re-routing and ideal routing algorithms over the no re-routing algorithm as function of traffic flow in New York

  Figure 7.: Impact of sampling rate on travel time in Cologne simulation, New York and London (a, c and d) and execution time in Cologne simulation (b) using the continuous re-routing algorithm.

  Figure 8.: Diverging vertices divergence ratio distribution.

  Table 1 contains definitions of the recurring keywords and Table 1.: Keywords & symbols definitions.

	Keywords	&	Definition
	symbols
	e ij		Directed edge from vertex i to j
	d ij		Length [m] of e ij
	s ij (t)		Speed [m/s] of e ij at time t
	w ij (t)		Travel time [s] of e ij at time t
	T		Number of timeslots in a given dataset
	δt = 60 sec		Sampling rate of the datasets
	∆t ≥ δt		Variable sampling rate

  Algorithm 1: Fastest Route with continuous re-Routing.Data: departure vertex (s), destination vertex (d), departure time (ts), sampling rate (∆t) Result: shortest route as an ordered list of vertices (route) /* Set current position to vertex s and current time to ts */ 1 here ← s; 2 tnow ← ts;

	3 do
		/* updates the route, from here to the destination	*/
	4	route ← dijkstra(here, d, tnow) ;
		/* true if a new data sample occurs		*/
	5	isN ewSample ← f alse;
		/* traverse the route until a new data sample occurs	*/
	6	while !isN ewSample do
		/* next edge in shortest route		*/
	7	evw ← getN extEdge(route) ;
	8	lg ← getLength(evw)	/* get length of edge evw */
	9	while lg > 0 do
		/* maximum distance that can be covered by next speed change	*/
	10	lgmax ← speed(evw, tnow) * (∆t -tnow mod ∆t);
	11	if lg < lgmax then	/* crossroad reached before next sample */
	12	lg ← 0 ;

13 tnow ← tnow + lg getSpeed(evw ,tnow ) ; 14 else /* crossroad not reached before next sample */ 15 isN ewSample ← true; 16 lg ← lg -lgmax; 17 tnow ← tnow + lgmax getSpeed(evw ,tnow ) ; 18 here ← getHeadV ertex(evw); 19 while here = d; /* we reached d */ 20 return (route)

Amine M. Falek. Email: a.falek@technologyandstrategy.com -falek@unistra.fr This work has been done when A. Gallais was employed by the University of Strasbourg


Satyajit Das
email: satyajitdas@iitkpd.ac.in

Rohit Prasad

Kevin J M Martin

Philippe Coussy

Energy Efficient Acceleration of Floating Point Applications onto CGRA

In this paper, we propose a novel CGRA architecture and associated compilation flow supporting both integer and floating-point computations for energy efficient acceleration of DSP applications. Experimental results show that the proposed accelerator achieves a maximum of 4.61× speed-up compared to a DSP optimized, ultra low power RISC-V based CPU while executing seizure detection, a representative of wide range of EEG signal processing applications with an area overhead of 1.9×. The proposed CGRA achieves a maximum of 6.5× energy efficiency compared to the CPU.

I. INTRODUCTION

The simplicity of Coarse Grained Reconfigurable Architectures (CGRA) with regular organization of Processing Elements (PE) helps to exploit the instruction level parallelism making them serious candidate for energy efficient accelerators [START_REF] Sutter | Coarse-grained reconfigurable array architectures[END_REF]. Modern applications rely on many floating point operations, which are performed in several cycles to not penalize the frequency of the whole architecture. Hence, supporting only integer operations does not cover all the computational needs of an advanced and subsequent applications.

Due to the area overhead induced by floating point capability, typical CGRAs become less attractive if all the PEs contain floating point computational units, which is stressed by the results shown in this paper. The heterogeneity in the PEs often fails to transport data synchronously to the PEs containing floating point units, disturbing parallel float computations resulting in a performance bottleneck. Transporting data synchronously to the processing elements can be guaranteed by decoupling address generation of the data structures from the computation flow. In this context, the contributions of this paper are: noitemsep

• a novel CGRA architecture employing IEEE 754 compliant floating point operations units. The PEs of the CGRA contain a Flexible Address Generation Unit (FAGU) which decouples addresses generation from the computation flow for increasing effective parallelism between the floating point operations at instruction level.

• the associated compilation flow to efficiently exploit parallelism between the floating point operations at instruction level leveraging static scheduling. • study on EEG application running in the proposed CGRA. Results are compared with the execution in DSP optimized, ultra low-power RISC-V CPU [START_REF] Gautschi | Near-threshold risc-v core with dsp extensions for scalable iot endpoint devices[END_REF] for performance and energy efficiency.

The rest of this paper is organized as follows. Section II discusses the state of the art in the context of floating point acceleration in CGRAs. It also motivates the need of new architecture and compilation flow to support energy efficient floating point application acceleration leveraging CGRA based architecture. Section III presents the proposed architecture and associated compilation flow. The experimental results are presented in the Section IV. Finally, the paper is concluded in Section V.

II. BACKGROUND AND MOTIVATION

Due to significant area overhead for the floating point computations (≈ 25% of a PE area in our case), employing floating point unit (FPU) in every PE of a CGRA loses its interest. While employing dedicated floating point computational units, CGRAs like [START_REF] Voitsechov | Inter-thread communication in multithreaded, reconfigurable coarse-grain arrays[END_REF] use heterogeneous PEs. However, heterogeneity in the PEs results increasing the minimum schedule length where multi-cycle operations like FP computations are involved. This limitation of floating point execution is incurred by address generation in the computation flow. Inconsistency in address generations penalizes the effective spatial parallelism in multiple floating-point computations when temporal parallelism (pipelining) cannot be exploited. Typical CGRAs like ADRES [START_REF] Bouwens | Architectural exploration of the adres coarse-grained reconfigurable array[END_REF], Morphosys [START_REF] Lee | Design and implementation of the morphosys reconfigurable computing processor[END_REF], IMAGINE [START_REF] Khailany | Imagine: Media processing with streams[END_REF] which support integer-based applications only do not possess dedicated address generation unit (AGU). In these cases, the addresses are part of the instruction and they are stored into the instruction memory as look up tables. This scheme results in increased number of instructions which adds to the energy consumption. For better area and energy efficiency, CGRA like IPA [START_REF] Das | A 142mops/mw integrated programmable array accelerator for smart visual processing[END_REF] performs address calculation in software (i.e. address generation is a part of the computation flow). Operations for address generation are mapped onto the PEs. For integer and fixed point based compute and control intensive applications, such approach has been proven to be quite efficient. However, for applications with multi-cycle floating point operations, the software based address calculation causes serious performance bottleneck due to asynchronous data-arrival to the PEs with FPU. Asynchronous data access increases the minimum schedule length of a DFG resulting in longer execution time.

Fig. 1 elaborates the minimum schedule length problem due to asynchronous data arrival. In the Data Flow Graphs (DF Gs) operations and data dependencies are represented by nodes and edges respectively. Weights of the edges correspond to the execution latency of source operation nodes. Two Scheduling of load nodes determines the data arrival to the computational units. To assure synchronous data arrival to the PEs, we propose to decouple address calculation from the computation flow as shown in the Fig. 1 (c) & (f), which achieves the best schedule length.

Hardware address generation is a well defined problem in modern DSP processors. Shami et al [START_REF] Shami | Address generation scheme for a coarse grain reconfigurable architecture[END_REF] propose a versatile address generation scheme for stream data processing in CGRAs. In this paper, we propose to use a flexible address generation unit to complement the decoupling of address generation from the computation flow to increase effective parallelism in FP computations.

III. PROPOSED ARCHITECTURE AND COMPILATION FLOW A. Architecture

The proposed CGRA is loosely coupled with a host CPU (see Fig. 2). The CGRA subsystem consists of a Heterogeneous Processing Element Array (HPEA), a context memory and a DMA controller. The CGRA shares data with the CPU through a tightly coupled data memory (TCDM) with multiple banks and a logarithmic interconnect.

The Context Memory stores configuration data (instruction and constants) for each PE in the PE Array which are broadcast

B. Compilation flow

In the compilation flow, the CGRA is modeled by a bipartite directed graph with two types of nodes: operator and register, in which temporal aspect is implicitly represented by connections from registers to operators. Applications are modeled as CDFGs. CDFG is composed of a Control Flow Graph (CFG) and a set of basic blocks (BB) represented by DFGs. The compilation flow finds the mapping of DFGs onto the CGRA graph. Steps involved in the proposed compilation flow are discussed chronologically below.

1) BB selection and multi-cycle operation serialization: This step selects one basic block from the CDFG using forward traversal-Breadth First Search (BFS) [START_REF] Das | An energyefficient integrated programmable array accelerator and compilation flow for near-sensor ultralow power processing[END_REF], and identifies multi-cycle operations (floating point computations). The operation nodes are then transformed by adding dummy nodes equal to the number of the total cycles needed to perform the operation. As an example, in the sample DFG of the Fig. 3 (a) node 4 is a float operation that takes 3 cycles to compute. This step transforms the DFG according to the Fig. 3 (b) (adding 4 and 4 sequentially). The transformed DFG is then passed to the scheduling and binding step.

2) Scheduling and binding: The proposed approach uses a backward traversal list scheduling algorithm to schedule the Priority of the nodes depends on their weight followed by mobility and number of fan-outs. The weight of any node is the execution latency in number of cycles.

The binding algorithm follows an incremental version of the Levi's [START_REF] Levi | A note on the derivation of maximal common subgraphs of two directed or undirected graphs[END_REF] subgraph matching algorithm. Since this step is exact in nature, the algorithm we propose adds the newly scheduled operation node except the float operations and its associated data node to the sub-graph composed of already scheduled and bound nodes. Only the previous set of solutions that have been kept are used to find every possibility to add this couple of nodes without considering the non-yet scheduled nodes.

For the floating point operation binding, the algorithm finds the binding solution only for the first operation node among all the dummy nodes (i.e. node 4 in Fig. 3 (b)). The tool assigns same solution to rest of the transformed nodes (node 4 , 4 in Fig. 3 (b)). This way, the binding of the floating point operation satisfies multi-cycle operations onto the CGRA with static scheduling.

3) Dynamic Transformation: If binding step does not find any solution for the current node, the graph is transformed on the fly. The transformation either reroutes the operation (Fig. 3 (c)) or distributes the fan-outs (Fig. 3 (d)) to satisfy available connectivity constraints of the CGRA node.

4) Stochastic Pruning: Exactness of the placement approach leads to very large number of partial mappings. It grows exponentially if not pruned. Hence, we use the stochastic pruning approach described in [START_REF] Das | A scalable design approach to efficiently map applications on cgras[END_REF].

After mapping all the nodes in the current basic block, the flow selects another basic block for DFG transformation and mapping, and apply the flow described in this section. Once, all the basic blocks are mapped, the compiler generates an assembly containing a single mapping for the entire CDFG.

IV. EXPERIMENTS AND RESULTS

This section analyzes the implementation results of the proposed CGRA, providing an estimation of the performance, area, and energy efficiency when running dimensionality reduction of seizure detection algorithm. The dimensionality reduction is based on principal component analysis (PCA) and composed of five kernels where Singular Value Decomposition (SVD) is performed by three of these kernels. SVD is a wellknown algorithm that computes eigenvalues and eigenvectors of a co-variance matrix. The method transforms the starting matrix into a bi-diagonal form through successive Householder matrices followed by diagonalizing the matrix through Givens matrices [START_REF] Wilkinson | Handbook for Automatic Computation: Volume II: Linear Algebra[END_REF]. The output of this procedure is the eigenvectors' matrix, used to find the Principal Components (PCs).

A. Implementation Results

This section describes the implementation results of the proposed CGRA accelerator, providing a comparison with a low power RISC-V based processor [START_REF] Gautschi | Near-threshold risc-v core with dsp extensions for scalable iot endpoint devices[END_REF]. This core is highly optimized for DSP benchmarks and features SIMD extensions, including dot-product and shuffle instructions, and misaligned load support that greatly reduce the load-store traffic to data memory while maximizing computational efficiency.

Both the CGRA and CPU RTL implementations were synthesized with Synopsys design compiler 2014.09-SP4 in STMicroelectronics 28nm UTBB FD-SOI technology. Synopsys PrimePower 2013.12-SP3 was used for timing and power analysis at the supply voltage of 0.6V, 125 • C temperature, in typical process conditions. In this operating condition the CGRA and the RISC-V CPU operates at 50 MHz. The Context Memory of the CGRA was sized at 4 KB, to fit both instructions and constants of the HPEA. The TCDM is sized at 32 KB with 4 memory banks. The implementation considers an HPEA consisting of a 4x2 PE array, each PE including 20x64-bit IRF, a 32x8-bit RRF and 32x16-bit CRF. The PE array is sized to support DSP and bio-signal processing applications. We do not focus on design space exploration, since this is out of the scope of this paper. Each of the PEs in the top row consists of Floating point multiplier and adder/subtractor. To perform the very few divide and square root operations that are present in the targeted EEG kernels, one floating point divider/square-root unit is employed in the HPEA. For area comparison, the RISC-V CPU includes 32 KB of data memory and 1 KB of instruction cache, which is equivalent to the design parameters of the proposed CGRA.

Table I shows the area breakdown of the CGRA and comparison with a RISC-V CPU. A complete area breakdown (Fig. 4) of the PE containing floating point multiplier, adder/subtractor depicts FPU almost acquires 25% area of the PE, whereas the memory components RRF, CRF, IRF takes around 7%, 13% and 28% respectively. ALU and FAGU together covers 21% of the PE area. In this paper for fair comparison and to achieve similar accuracy, we employed the same IEEE compliant FPU that is used by the RISC-V core.

B. Performance Results

This section provides performance comparison between the proposed CGRA and the RISC-V running PCA kernels. Additionally, we have presented performance results for the CGRA version where address is computed in software. Table II presents latency (in cycles) information executing the kernels computing PCA in the EEG analysis. The CGRA execution achieves a speed-up up to 4.64× with an average of 2.3×. It is to be noted that the performance gain in the kernels like accumulate, householder and diagonalize is less than the gain in the kernels like PC computation and mean-covariance. Due to heavy control intensive nature of these kernels (accumulate, householder and diagonalize), the compiler is unable to exploit instruction level parallelism efficiently. The table also indicates that due to long schedule performance degradation for floating point computations, CGRA without FAGU did not achieve any performance gain.

C. Energy Consumption & Efficiency

Following the considerations of the Section 4.1, here we present energy efficiency of the CGRA compared with the RISC-V CPU. Executions with high number of active PEs/cycle achieve large MOPS. Fig. 5 shows due to highly control intensive nature of the accumulate and diagonalize, the CGRA achieved efficiency of 90 and 99 MOPS/mW respectively. CGRA achieves a maximum of 156 MOPS/mW energy efficiency for the meancovariance which is 6.5× higher compared to the RISC-V CPU which has the efficiency of 24 MOPS/mW. For the householder and PC, CGRA achieves an efficiency of 115 and 138 MOPS/mW respectively.

V. CONCLUSION

This paper presents an energy efficient CGRA and associated compilation flow to perform floating point application acceleration. Supporting floating point (or more generally multicycle operations) must go along with hardware based address generation unit which decouples the address generation from the execution flow to leverage parallel arbitrary data accesses. The novel architectural approach proposed in this paper reduces the complexity and size of the instruction memory in the traditional CGRAs which do not possess a dedicated address generation unit. Thanks to the efficient compilation flow, the architecture exploits instruction level parallelism efficiently while running floating-point computations compared to the software based address calculation scheme. Case study on the EEG application shows that the proposed CGRA achieves an average of 120 MOPS/mW energy efficiency which is around 5× higher than the RISC-V CPU with an area overhead of 1.9× only.

Fig. 1 :

 1 Fig. 1: (a) Sample DFG with software based address generation; (b) The same DFG with different schedule length; (c) DFG with decoupled address generation reducing the schedule length; (d), (e), (f) ASAP schedule of the DFGs (a), (b), (c) respectively different scenarios of software based address calculation are presented in the first two sub-figures. As Soon As Possible (ASAP) scheduling of the two DFGs in Fig. 1 (a) and (b) reveals that the address calculations are fully part of the critical path of the DFGs. Two different minimum schedule length suggests that software based address generation may take different numbers of cycles depending on the location of the index variable. For instance, early scheduling of the node load2 in the critical path helps to achieve better minimum schedule length of 15 in Fig. 1 (e) compared to 17 in (d).Scheduling of load nodes determines the data arrival to the computational units. To assure synchronous data arrival to the PEs, we propose to decouple address calculation from the computation flow as shown in the Fig.1 (c) & (f), which achieves the best schedule length.Hardware address generation is a well defined problem in modern DSP processors. Shami et al[START_REF] Shami | Address generation scheme for a coarse grain reconfigurable architecture[END_REF] propose a versatile address generation scheme for stream data processing in CGRAs. In this paper, we propose to use a flexible address generation unit to complement the decoupling of address generation from the computation flow to increase effective parallelism in FP computations.

Fig. 2 :

 2 Fig.2: CGRA integrated System and PE architecture by the DMA controller. The configuration data is stored in the respective memory segments of the PE prior to starting of the execution. The HPEA consists of heterogeneous PEs, connected with a mesh torus network for data sharing and a bus network for context broadcast. To support floating point operations, we have employed floating point multiplier, adder/subtractor and divider/square-root units inside the PEs as shown in the Fig.2. In addition to the 32-bit ALU and a Load-Store Unit (LSU), each PE consists of a Constant Register File (CRF) which stores the immediate values of the instructions, a Regular Register File (RRF) and Output Register (OPR) to store temporary variables. The Controller in the PE fetches instructions from the Instruction Register File (IRF). A Flexible Address Generation Unit (FAGU) is implemented in each PE, which facilitates random access to the tightly coupled data memory for the LSUs.

Fig. 3 :

 3 Fig.3: Graph transformations used in the compilation flow DFG nodes of each basic block. It relies on a heuristic in which the schedulable operations are listed by priority order. Priority of the nodes depends on their weight followed by mobility and number of fan-outs. The weight of any node is the execution latency in number of cycles.The binding algorithm follows an incremental version of the Levi's[START_REF] Levi | A note on the derivation of maximal common subgraphs of two directed or undirected graphs[END_REF] subgraph matching algorithm. Since this step is exact in nature, the algorithm we propose adds the newly scheduled operation node except the float operations and its associated data node to the sub-graph composed of already scheduled and bound nodes. Only the previous set of solutions that have been kept are used to find every possibility to add this couple of nodes without considering the non-yet scheduled nodes.For the floating point operation binding, the algorithm finds the binding solution only for the first operation node among all the dummy nodes (i.e. node 4 in Fig.3 (b)). The tool assigns same solution to rest of the transformed nodes (node 4 , 4 in Fig.3 (b)). This way, the binding of the floating point operation satisfies multi-cycle operations onto the CGRA with static scheduling.3) Dynamic Transformation: If binding step does not find any solution for the current node, the graph is transformed on the fly. The transformation either reroutes the operation (Fig.3 (c)) or distributes the fan-outs (Fig.3 (d)) to satisfy available connectivity constraints of the CGRA node.4) Stochastic Pruning: Exactness of the placement approach leads to very large number of partial mappings. It grows exponentially if not pruned. Hence, we use the stochastic pruning approach described in[START_REF] Das | A scalable design approach to efficiently map applications on cgras[END_REF].After mapping all the nodes in the current basic block, the flow selects another basic block for DFG transformation and mapping, and apply the flow described in this section. Once, all the basic blocks are mapped, the compiler generates an assembly containing a single mapping for the entire CDFG.

Fig. 4 :

 4 Fig. 4: Area break down of a PE with FPU

Fig. 5 :

 5 Fig. 5: Energy efficiency compared to the RISC-V CPU For the execution in CGRA, Million Operations Per Second (MOPS) only considers the active PEs during execution, since a PE may be idle due to TCDM bank access conflicts, consecutive NOPs or unused in the application execution.Executions with high number of active PEs/cycle achieve large MOPS. Fig.5shows due to highly control intensive nature of the accumulate and diagonalize, the CGRA achieved efficiency of 90 and 99 MOPS/mW respectively. CGRA achieves a maximum of 156 MOPS/mW energy efficiency for the meancovariance which is 6.5× higher compared to the RISC-V CPU which has the efficiency of 24 MOPS/mW. For the householder and PC, CGRA achieves an efficiency of 115 and 138 MOPS/mW respectively.

TABLE I :

 I Area in µm 2

		CGRA	RISC-V CPU
	DMA controller	593
	interconnect	6,273
	Context memory	9,345
	TCDM	65,164
	HPEA	122,692
	Total Area	204,067	106,759

TABLE II :

 II Performance comparison in cycles

		CGRA	CGRA		Gain in
	Kernels	without	with	RISC-V	CGRA
		FAGU	FAGU		with FAGU
	mean covariance	734,934 300,050	732,377	2.44x
	accumulate	94,018	48,877	66,334	1.36x
	householder 211,113 125,375	132,870	1.06x
	diagonalize	257,488	84,186	175,092	2.08x
	PC	268,809 105,993	488,252	4.61x

  Table III compares the energy consumption in µJoule while running different kernels in the CGRA and CPU. The table shows that the CPU energy consumption surpasses the CGRA by up to 3.3× with an average of 1.86×.

TABLE III :

 III Energy consumption comparison in µJoule

	Kernels	CGRA RISC-V Energy gain
	mean-covariance	3.24	5.71	1.8x
	accumulate	0.38	0.52	1.4x
	house holder	1.02	1.04	1x
	diagonalize	0.8	1.4	1.8x
	PC	1.14	3.8	3.3x