{'fraction_non_alphanumeric': 0.020571516956034184, 'fraction_numerical': 0.0065736050423417505, 'mean_word_length': 4.83528880866426, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Autonomous driving systems hardware and software architecture exploration: optimizing latency and cost under safety constraints

With the recent progress of techniques in computer vision and processor design, vehicles are able to perform a greater number of functions, and are reaching higher levels of autonomy. As the list of autonomous tasks that the car is supposed to perform grows, two design questions arise: how to group these tasks into modules and which processors and data buses should instantiate these modules and their links in the physical architecture. Both questions are linked, as the processing capacity of the processors influences how centralized the architecture can be, and the modularization influences the overall system latency as well. Furthermore, our interest lies in designing architectures that perform the tasks rapidly, while minimizing cost. This multiobjective problem is intractable without architecture exploration and an analysis tool. This paper presents a linear optimization formulation to capture these tradeoffs, and to systematically find relevant architectures with optimal latency and cost. The results show that enforcing all safety constraints on the architecture leads to a worst case increase of 17% in latency and 18% component cost per vehicle. The increase in latency is significant at the scale of human driver reaction times.


INTRODUCTION
Advances in autonomous vehicle technologies are rapid. Whether autonomous vehicles (AV) will only result in various technical demonstrators or in viable products for end users will depend on not only the advance of component technologies, but also on their organization into functional systems that possess attractive life cycle properties such as safety, reliability, producibility, and affordability. While much of the current focus of AV technology development is on demonstrating functional capabilities, an important next step is to begin to determine which tradeoffs among the elements of AV system architectures will yield superior overall system performance. Several prototypes were presented during the 2007 DARPA Urban challenge, giving the first insights on which architectures were promising. 1 For instance, advances in the performance of computer vision algorithms and the ability for some algorithms to successfully perform object recognition at sufficiently high rates is a key enabler in the cre-ation of fully autonomous vehicles. The performance of deep learning algorithms increases with the size of the training data set and the depth of the neural networks, resulting in these algorithms performing more and more operations. 2 The physical architecture of the components supporting these algorithms therefore contains processors with more computing power, in order to perform the same tasks more effectively within the time required for vehicles to be considered autonomous.
This implies some important tradeoffs in system design. Distributing computational tasks on different processors allows for parallelizing the computation, but the transfer of data between processors increases latency 3 (time taken to complete all required computations). If all the computational tasks are carried out on a single processor, processors with high computing capabilities (and cost) will be required. As prototypes of functioning autonomous vehicles turn into viable products going into mass production, quantifying this tradeoff between cost and latency becomes critical. Our work aims to develop an approach for identifying architectures that can perform at acceptable levels of latency, but are cost-effective for development and manufacturing. In the work presented here, cost is viewed as the addition of individual component costs, which allows a linear formulation of the system cost. This work aims to extend existing methods from embedded systems design to a higher level, at the early phases of design. Unlike most of the existing work in the area, cost considerations are introduced, in addition to the latency calculation, and the performance impact of allowing a largely distributed system, as well as safety constraints, are evaluated. This allows the designer to quantitatively assess the benefits of specific safety measures and weigh them against potential negative impacts on latency, which is another safety relevant metric.

FUNCTIONAL AND PHYSICAL ARCHITECTURES
As future cars are meant to take over an increasing number of tasks from the driver, the embedded systems and the network they form in the car are becoming a complex system. It is no longer the case that each subsystem performed its own task in isolation from the others (e.g., locking the doors after the car started driving). Autonomous cars have to be able to perform a long list of tasks, in various environments, 4 and the output of one task can be useful information for the next. The list of potential hardware to perform these tasks is also long. 5 This paper presents a method to formally design the architecture of embedded self-driving systems for autonomous cars.
The first step is to build a functional architecture of the car, and to understand how tasks interconnect. Several functional architectures have already been proposed. 6,7 Our functional model is not limited to an abstract model, but it assumes execution times and gives performance constraints on the algorithms that will be used to instantiate the tasks listed in the functional architecture. 8 The specific data reflect a realistic functional architecture used in industry for an autonomous vehicle. The functional architecture is defined as a network of tasks, that communicate to one another via messages, whereas processors and data buses are components of the physical architecture. The functional architecture is the equivalent of a graph, where tasks are the nodes, messages are the edges, and the adjacency matrix of the graph would be the problem's design structure matrix (DSM). 9 The design of such a functional architecture can be informed by recent methods in network analysis such as functional dependency network analysis (FDNA), 10 in order to identify the effects of a functional failure in a highly connected architecture such as the one presented here.
For example, Figure 1 shows that the Cognition 2 task cannot receive the latest information until seven other tasks finish their calculations. It is worth noting that a part of the system, as described by this functional architecture, is examined here, and that the control devices are not included in the selection process, for example. In order to create redundancy in the system and increase safety, some tasks are replicated into a degeneracy task; both tasks require the same input and outputs, but they might be carried out by different algorithms or hardware solutions. Identifying the most capability-carrying functions through a network analysis 11 informs the design of a redundancy network of tasks to improve performance and safety in the first stages of the design. For example, the task "Recognition 4," has the degeneracy equivalent "Recognition 4 Degeneracy." The purpose of redundant tasks is to have a function that takes over if the original function fails, whether because of a hardware or a software failure. Each task has an ASIL (automotive safety integrity level), corresponding to how critical it is. A task and its degeneracy equivalent might have different ASILs.
In order to transfer the safety considerations from the functional architecture to the physical ones, two safety constraints are defined: a task and its degeneracy equivalent should not be allocated to the same processor and all tasks should be matched to a processor that has at least the same ASIL. 12 The ASIL metric captures the robustness of a component of the physical architecture in this model. Further robustness analyses, such as the system operational dependency analysis (SODA) 13 can be employed to extend safety considerations, but are not considered in this work.
Latency is defined as the maximum path length in the functional network. In this asynchronous system, it can represent the time between the recognition of an obstacle and a braking action, for example. It is a function of the tasks themselves, the processors they are being computed on, and the messages they need to exchange, and whether these communications are interchip. 3 As an example of the cost-latency tradeoff, one could design a system where all tasks are on the same chip, reducing the latency due to interchip communication but this would require a processor with very high capacities, and which would therefore be very expensive (the architecture would also be nonrobust to hardware failures). Using several processors linked to each other, the designer needs to specify which tasks should be processed in parallel, while respecting the capacity constraints given by data buses, on the messages that the chips need to exchange. The difference with a network flow problem is that, here, the capacity of the nodes and edges of the network are not set initially.
An assumption of this work is that tasks can be freely assigned to a list of provided processors, in order to, in a first instance, remove constraints to reach new, creative designs. A first avenue to explore the design space of physical and functional allocations is to simply enumerate all possible architectures, evaluate the cost and latency of them, and plot their performance to obtain a Pareto front. 14 However, this approach becomes rapidly computationally intractable due to the dimension of the design space in this type of problems.
The functional allocation problem is equivalent to partitioning the set of functions into an unknown number of subsets. 15 The size of the design space for k functions is therefore the Bell number In this paper, we describe a multiobjective discrete optimization model that minimizes cost and latency. We propose that this approach can serve as an initial step in exploring and identifying feasible and optimal architectures for latency and cost metrics-two of the important attributes for autonomous driving systems. The rest of this paper is organized as follows: In Section 3, previous and related work is reviewed; In Section 4, the details of the optimization formulation are presented, and the results obtained through this formulation are shown in Section 5.

RELATED WORK
Architecture principles and models for embedded systems are common in the software and electrical engineering fields, but literature is starting to emerge about how to use these principles at a higher level of the system, and more generally to optimize the architecture of embedded systems specifically for autonomous vehicles.
From an optimization perspective, Ma et al. (1982) give a general algorithm to allocate tasks on a distributed system 16  tributed system architecture to this system, and go into the details of the algorithms behind the tasks themselves. 22 Davare et al. (2007) try to minimize latency as a single objective, but they use different design variables.
Practical experiences of building autonomous vehicles, spurred by the DARPA urban challenge, have led to different articulations of requirements to improve safety in autonomous vehicles. 23 It seems that the current approach from the robotics field is to increase safety by improving each of the tasks or sensors individually, 24 for example, including pedestrian intent prediction in path planning, 25,26 whereas experts from the automotive industry have a functional pointof-view on safety. 27,28 Increased safety can also take the form of enhanced communication between the car and the driver, to increase transparency on the reasons why the car makes certain decisions, adding functions to the list of tasks the car has to perform. 29 More elaborate validation methods for safety include probabilistic modeling of the egocar and other agents on the road. 30 In our work, the optimization problem is formulated with assignment variables, and task attributes, such as activation periods, are assumed to be fixed, in order to reduce the size of the design Our work tries to link the performance of the system (proxied by end-to-end latency) and the cost of individual components, to create pareto-optimal, yet realistic, functional, and physical architectures. This is therefore a multiobjective problem, in addition to being multidisciplinary.

LATENCY AND COST OPTIMIZATION
The design problem contains two steps; identifying which tasks need to be grouped together without exceeding the computing power pro-  In order to quantify the cost-latency tradeoff, the optimization problem is formulated as a linear, mixed integer programming (MIP), multiobjective optimization problem, with constraints on the computational capacity of the processors. Constraints related to safety requirements (of redundancy) are also included in our formulation. This also allows us to investigate and quantify the impact of safety constraints.
The linear formulation allows for using branch-and-bound methods that are implemented through widely used solvers. The design space Example of latency calculations for two different architectures. The latency is calculated for the path between Sensor 1 and Actuator 1 in both cases. Adding a bus adds latency to the message going from task 1 to 3 . To ease the notation in the figure, messages are here designated with their own index, as opposed to the tasks they are linking, in the equations above; m 3 would be designated as 1 3 in the provided latency formula can hence be explored, and different pareto-optimal architectures can be found for minimizing latency and cost objectives.
As is shown in Figure 2, a module is a theoretical entity that regroups different tasks and that needs to be assigned to a type of

System latency model
The end-to-end latency is the time elapsed between any of the tasks that start at time t = 0 and the last task to be finished. The relevant scheduling theory results are detailed in. 34 It can be seen as the longest path between any of the tasks in the left column of Figure 1 and the tasks in the right column. It is composed of the time needed to perform each task on the path, as well as the time to transfer a message from one task to the next one, should they be on two different processors. 35 The following equation is therefore used for latency (see also Figure 3): where  is a possible path in the network, r i (resp. r i j ) the worst case response time for task i (resp. for message i j ), and T i (resp. T i j ) the activation period of task i (resp. of message i j ). Throughout the model, indices referring to messages are composed of the two tasks that the message is linking. For example, T i j is the period of the message linking i and j .
Although this formulation does not capture all the details of the processes taking place in the transmission of messages and the execution of tasks, it linearly links the hardware and logical attributes.
It quantifies the tradeoffs presented earlier between centralized and distributed architectures at the functional and physical levels. 22 As the primary goal here is to relatively compare architectures, rather than to determine latency behavior of a single design at high fidelity, we consider this worst case simplifying formulation to be adequate.
A closed-form analytical expression to represent latency in a system composed of tasks and messages that can preempt one another, with potentially buses with different protocols, is not possible. 36 As our purpose is to generate early designs rapidly, the preference is given toward a formulation that leads to a solution of the optimization problem in a reasonable amount of time, to be able to generate a Pareto front. The priorities of the different tasks are neglected in our formulation, as this is usually done at a later stage of the design. 3

Design variables
As encountered in the cited previous work, as well as in the topology of systems architecture problems detailed by Selva, 37 the model uses assignment variables that are binary; the variable is equal to 1 when the two items it represents are associated. Latency is modeled as a continuous dependent variable. The formulation is an MIP problem, that can be solved relatively fast with solvers.
i represents task i, m k represents the kth module, and r represents the rth choice in the list of potential processors.
 represents the space of existing messages. Messages are designated by the name of the sender task followed by the name of the receiver task. For example, if Task 1 sends a message to Task 3, the message will be denoted as 1 3 .
• x i m k represents the assignment of a task to a module • z m k r assignment of a module to a processor

Optimization model and constraints
The cost model C takes into account the cost of the physical components present in a given architecture. The cost expression is made up of two terms; the first one refers to the cost of processors,and the second one to the cost of buses. The index k refers to the choice of physical processor.
The factor 1000 in (3) meaning that each task is assigned to exactly one module, and each module to exactly one processor.

Processor capacity constraints
For each module, the computation amount, which is the clock cycle of the task (Cy ) divided by its activation period (T ) (in MHz), the RAM usage and the ROM usage should not exceed the clock rate available, the RAM capacity and the ROM capacity, respectively, of the assigned processor. RAM k (respectively, ROM k ) designates the RAM (respectively, ROM) usage or capacity of component k in KB.

Bus capacity constraints
This constraint ensures that the bus used to transmit the message between task i and task j can fit the number of bytes in the message.

Task precedence constraint
This equation states that, in the worst case, a task j downstream of task i can only start once the following has happened: • Task i can start.
• Time worth one period of task i has passed, therefore guaranteeing the task has started at least once.
• Task i has been processed on the processor it is being allocated to, and this processing time depends on the task's clock cycle and the processor's clock rate.
• The message going from task i to task j has been transmitted. The formula for this message induced latency comes from bit-stuffing, 39 as is done with CAN buses, using 11-bit identifiers for the messages.
The numbers 55 and 10 come from counting the bits in the CAN protocol.
• The period of the message has passed, therefore guaranteeing it has been transmitted at least once.
T m k m l , i j * y m k m l , i j ∀ i j ∈ .

Linearization constraints
∀m k ≠ m l and i j ∈  y m k m l , i j ≤ x i m k (12) ∀b, ∀m k ≠ m l and i j ∈ 

Safety constraints
Defining safety in autonomous vehicles is a challenging task. For the purpose of retaining a computationally tractable model, the safety notions are reduced here to two constraints on the functional and physical allocations. Through these constraints, the scope of safety is limited to the intrinsic system reliability, rather than examining uncertainty in the environment of the vehicle. 40 This assumes that the system only fails when the physical instantiation of a function (the processor to which it is assigned) fails itself. This reflects the usual literature in fault-tolerant architectures analysis, 41 however, an avenue of future work is to analyze reasons for which the functions would fail to perform correctly, even with functioning processor support. An example of such a failure would be the incapacity to recognize a pedestrian in front of the car, without any hardware failure.
The recommendations from the ISO26262 are leveraged to generate constraints on the optimization problem to represent safety. 28 Therefore, a task and its degeneracy equivalent are forced to be in different modules, and the processor choice has to respect the ASIL of the most critical task in the module. This allows the architecture to be resilient to physical component failure. For two specific tasks i and j that are meant to be on different processors (and therefore in different modules), this constraint materializes in Equation (21). In Equation (22), the ASIL of processor k needs to be at least as high as the ASIL of task i.

Single architecture example
The functional architecture used in this problem represents the entire set of functions needed to drive a car, all the way from sensing to controls. A Level 4 or 5 of autonomy corresponds to all functions successfully carried out in most or all situations. 27 The architecture contains 24 tasks, linked together by 32 messages. Depending on the context the car is driving in, city center with many pedestrian or highway without many traffic signs to read, some of the functions in the architecture will be more solicited than others. For example, if a task is to read traffic signs correctly, it will be activated more often in cities than on highways. However, the architecture considered here is valid for many different environments, and does not assume a specific scenario-the context only influences how much these functions need to be performed. Even though the latency equations are simplified, and the cost model only takes into account component price, this framework represents the steps that can be taken in the autonomous vehicle industry to plan the future compute power needed.
To generate all the following result, the Julia optimization package JuMP is used as a wrapper around the CPLEX solver, usually well suited for mixed-integer programs. Table 2 shows the list of available processors-and their attributes-used in this optimization. These data have been provided by industry stakeholders and are meant to represent the potential tradeoffs that can occur in processor choice.
This table illustrates that the cost is usually proportional to computing capabilities of the processors. Indeed, for the same cost, having a higher ASIL means having a lower capacity and clock rate. A first preprocessing step to reduce computation times is to identify processors that are dominated in all categories, and remove them from the list. For example, processors 10 and 14 have the same capacity attributes, an ASIL of 4, and processor 10 is more than twice as expensive as processor 14, and will therefore never be used. This exercise prompts the designer to make this type of decision, which might not have been made in a systematic manner otherwise.
In one of the nondominated architectures appearing on Figure 4, the degeneracy functions are assigned together to a processor, which is separate from the rest of the physical architecture; this is the most natural solution to respect the constraint expressed in Equation (21).

TA B L E 2
Available processors and their clock rate, RAM capacity, ROM capacity, and cost

F I G U R E 4
Results for different centralization levels-Safety constraints included. The results are calculated within 7% of optimality, meaning that there was a 7% gap between the mixed integer programming solution and the relaxed continuous linear programming solution used for the branch-and-bound. As increases, the performance moves to the right Many recognition functions are allocated individually, as they are heavier and may use a processor on their own.

Pareto fronts
The optimization is then run several times by weighing the two objec-   42 This share is likely to increase in the future, 43 meaning that the reduction in cost for this subsystem will have an impact at the system level.

Impact of task distribution
The architecture yielding the lowest end-to-end latency is also more than 10% faster than the architecture with the longest path, and lower cost. Although these numbers are much below average human reaction times for braking, about 1.5 s, 44 a 0.03 s difference in latency represents about 1 m when driving at 100 km/h. Depending on the scenario the car would need to be certified to drive in, this latency reduction might reduce the probability of crashing enough to demonstrate safety. In terms of time metrics for the system, this represents about three times the control period of an assisted driving system, meaning that the latency computed in this work is the main driver of reaction delay, and that a reduction in processing latency is significant and affects the behavior of the autonomous driving system. An avenue for future work would be to test these different architectures in simulations representing different driving scenarios, to quantify the impact of a latency reduction over time, in different settings.
As this work is meant for early design exploration, the gain in latency might not be significant enough to justify the use of a more expensive architecture as a base design, and more effort might be deployed in later design stages to reduce the parameters of each function, such as clock cycle. Figure 5 shows the performance of a four-module architecture with and without each safety constraint. The worst performing architectures with regard to both latency and cost are the ones with all safety constraints enforced (blue points in the upper right corner). Relaxing the ASIL constraints, given the state of our input list of components and their ASIL capabilities, improves cost by more than 15%, and latency by about 7%. However, relaxing the redundancy constraints might reduce the cost to a lesser extent, but not if the ASIL constraint is already relaxed. In terms of safety, reducing the end-to-end latency of the vehicle is crucial, however the designer has to weigh whether the current decrease in latency justifies a higher risk of failure due to hardware malfunction.

CONCLUSION
This work, linked with broader approaches of architecture and design for system-level properties, 45