Amira Derradji
email: amira.derradji@imag.framira.derradji@arcan.fr

Agnès Front
email: agnes.front@imag.fr

Christine Verdier
email: christine.verdier@imag.fr

Vincent Bouzon
email: vincent.bouzon@arcan.fr

An Ontology for Unexpected Events and Actions in Chronic Patient Home Care Protocol

Keywords: p-health, health care protocol, chronic expert patient, ontology

An ontology for unexpected events and actions in chronic patient home care protocol

I. INTRODUCTION

A chronic disease requires long life treatments, which need the integration of patient's care in his own environment outside the hospital (or other institutions) and under continuous supervision by the healthcare team.

Home care for chronic diseases needs to apply continuously a set of actions, called "care protocol", defined by healthcare professionals, related to the disease follow-up, treatment, medication, etc. and indicating the patient (or his caregivers) how to treat and follow the disease.

One problem is the fact that this care protocol is not personalized to patient who often carries out alone several protocol's actions such as the control of vital parameters or some parts of the treatment. Doing that, he develops an important expertise on his chronic disease and can be considered as an "expert patient".

The patient's expertise in daily care offers important benefits to both patient and healthcare professionals, such as the knowledge of the concrete execution of the care protocol, the fact that some actions are not realized or correctly realized or are modified by the patient, and what happens to him as consequences. Designing and implementing these elements are our major challenges.

Moreover, more than continuously assisting the patient, our goal is also to provide healthcare professionals with detailed information about the patient's disease progression. This information can be very useful to discover prejudicial situations that require an intervention of the healthcare team. Indeed, during the disease follow-up, the patient's expertise in daily care can result in (i) actions not correctly made or modified and (ii) events undefined in the initial protocol that may happen. Both of them (unexpected actions and unexpected events) reported by the patient should be sent to the healthcare team who will analyze them and decide which one may be of benefit for the patient's care.

For that purpose, we propose in this paper to use the ontological paradigm that is widely used in healthcare domain. Indeed, ontologies have proved to be powerful in expressing expertise knowledge and represent it from human understandable into machine-readable format. The ontology will allow formalize a chronic patient expertise terminology (particularly chronic disease parameters, unexpected actions and unexpected events) that can be reused in other ontologies in the same domain. We propose to use traditional reasoning techniques and rules that define concepts values and relations between them.

We propose to do the traditional reasoning techniques on ontologies with rules defined on concepts values and on the relations between them. Thus, we propose to model relationships between the ontology concepts and to reason from patient's expertise.

The paper is organized as follows. Section II presents the case study on the chronic disease "type 1 diabetes". Section III presents our general approach. Section IV describes the ontology proposed. Section V presents a survey of related works applying ontologies in medicine and in home care. The conclusion is drawn in the last section.

II. CASE STUDY

This section presents a use case underlying our research. This use case is relative to the diabetes. The diabetes disease is a metabolic disorder characterized by the presence of high blood sugar (glucose) level due to defective insulin secretion, defective insulin action or both. There are two major types of diabetes, called type 1 and type 2. In type 1, the beta cells of the pancreas do not produce insulin. In type 2, the beta cells of the pancreas do not produce enough insulin for proper function. The patients with diabetes should know particularly how to control the level of blood sugar, how to inject insulin, how to recognize and treat hyperglycemia (high blood sugar level) and how to recognize and treat hypoglycemia (low blood sugar level).

To answer these questions, healthcare professionals defined a set of actions (the care protocol) that need to be achieved by the patient (or possibly caregivers). For example, the hypoglycemia care protocol for type 1 diabetes can be summarized as follow:

1) The patient recognizes the symptoms (e.g., weakness, headache, hunger, rapid heartbeat, etc.).

2) The patient makes himself safe (e.g., pull over if he is driving, sit down if he is walking, etc.).

3) The patient tests his blood sugar level using blood glucose meter to make sure that he is under an hypoglycemic episode. 4) The patient gets some carbs quickly into his body in order to avoid the side effects of this episode. For that, it is recommended to take 15 or 20 grams of sugar. Some foods can also quickly raise the blood sugar level such as 1 cup of fruit juice, 1 tablespoon of honey, etc. 5) The patient waits 20 to 30 minutes, then he checks his blood sugar level again with blood glucose meter. If it is still low, he eats again 15 or 20 grams of sugar. The patient repeats this action until his blood sugar level is higher than or equal to 70 mg/dl. It is also recommended, once the level is fixed, to eat more carbohydrate such as bread. Sometimes, the hypoglycemic episode is severe and causes the patient's unconsciousness. In this case, the caregiver (or the helper) should give him an emergency glucagon injection that quickly raises blood sugar levels. 6) The patient should look for the causes of hypoglycemic episode and discuss with the doctor about the severe case of hypoglycemia, the inscription of glucagon injection, and the adaptation of his diabetes management plan. Sometimes, the patient doesn't strictly follow the care protocol. He may skip, modify or replace an action. For example the patient may skip the action (3) and immediately perform the action [START_REF] Brickley | Rdf vocabulary description language 1.0: Rdf schema[END_REF]. He may also modify action (4) for example by "taking more sugar than 15 or 20 grams, until the disappearance of hypoglycemia symptoms" or replace this action by another such as "taking emergency glucagon injection". The ontology proposed (cf. section IV) aims to detect these different cases of unexpected events and actions.

III. THE GENERAL APPROACH

In previous works [START_REF] Derradji | Un méta-modèle et un langage orientés patient pour la représentation de protocoles de soins auto-adaptatifs[END_REF], we proposed to represent the home care protocol as a set of actions proposed to the patient in a web interface. This protocol is built by a medical team through their own web interface. The "healthcare professionals access" allows healthcare professionals to design, consult and adapt the care protocol.

In this paper, we illustrate the "chronic patient access" that allows a chronic patient (or his caregivers) to consult and follow the care protocol, and to monitor it by recording parameters or reporting unexpected events and actions. The web application interfaces showed in figure 1 present the implementation on a mobile device (e.g., a tablet) of the care protocol to be followed by the patient.

The construction of the care protocol relies on a Domain Specific Language (DSL) for the construction of care protocols Fig. 1: Patient interaction interface for following the care protocol that we defined in [START_REF] Derradji | Un méta-modèle et un langage orientés patient pour la représentation de protocoles de soins auto-adaptatifs[END_REF]. This DSL is based on an abstract syntax (meta-model) and a concrete syntax (graphical notation). On one hand, the meta-model describes and formalizes the main concepts of care protocol, which were extracted from a thorough study of various chronic diseases care protocols such as (1) expected actions: treatment action (e.g., inject insulin), measuring and monitoring action (e.g., control the blood sugar level), education action (e.g., wash hands before the blood sugar control) and preventive action (e.g., take the influenza vaccine), ( 2) actors: patient, healthcare professionals (e.g., diabetologist, nurse) and caregivers (e.g., family, friends), ( 3) diseases (e.g., type 1 diabetes), ( 4) drugs (e.g., insulin), medical devices (e.g., blood glucose meter), medical consultation (e.g., consultation with diabetologist), exam/act (e.g., glycated hemoglobin exam), ( 5) parameters (e.g., blood sugar), ( 6) good practices (e.g., insulin pen needle are disposable), ( 7) parts of body (e.g., abdomen) and (8) expected events (e.g., presence of lipodystrophy on the abdomen). On the other hand, a graphical notation is associated with each concept of the meta-model and is represented by clickable information, which provides more information about the concept. For example, in figure 1 (left side), the actor "Patient" should execute the measuring and monitoring action "Test blood sugar" which allows to test the parameter "Blood sugar" with medical device "Blood sugar meter" on the part of body "Finger" and respect the good practice "Avoid the thumb and index finger". Thus, in figure 1 (right side), the actor "Patient" should execute the treatment action "Eat carbs" and respect the good practice "Take 1 cup of fruit juice".

Moreover, a special interface is dedicated to report unexpected event with three main areas: emergency, pain and a dialogue box to express the problem (figure 2). Both, "emergency" and "pain" areas represent respectively the emergency and pain levels estimated by the patient. The emergency level is represented by a six-valued scale, from 0-not urgent to 5extremely urgent. For the pain level, the scale also offers six values, but with different meanings: 0-very moderate and 5very important. Finally, the patient describes the unexpected event in natural language in the corresponding text box.

The general approach of the treatment of the patient interaction is shown in the figure 3. We propose an ontology to exploit the report of all the unexpected events and actions and Fig. 2: Patient interaction interface for unexpected event Fig. 3: Treatment of patient interaction to infer important medical information that could be transferred to healthcare professionals. In particular, a comparison between the "expected action" as defined in the protocol and the "unexpected action" as realized and reported by the patient, needs to be done and analyzed. A report including detailed results will be generated and sent to healthcare professionals who could analyze the result and check the consequences of this action on the patient's health and life's quality.

All unexpected action that could have negative consequences will be filtered. The other unexpected actions will be retained and added to the initial care protocol in order to adapt and adjust the protocol to this new deal. If some events or actions are recurrent and "medically" interesting, it can become a new medical knowledge to be disseminated.

IV. THE KNOWLEDGE LAYER

This section presents the ECPO (Event Chronic Patient health care Ontology) that we designed for unexpected event and action in home care protocols.

A. Ontology and ontology engineering

An ontology is defined as a "formal explicit specification of a shared conceptualization" [START_REF] Studer | Knowledge engineering: principles and methods[END_REF]. Four notions are important in this definition. First, conceptualization refers to an abstract model of the world that we wish to represent. Secondly, explicit means that the type of concepts identified, and the constraints of their use, are explicitly defined. Thirdly, formal refers to the fact that the ontology should be machine-readable. Finally, shared means that a ontology captures consensual knowledge, that is not a personal view of the target phenomenon of some particular individual, but one accepted by a group.

An ontology is composed of sets of concepts, relations, attributes and data types. Concepts (or classes) are sets of real world entities with common features (e.g., drug).

Relations are binary associations between concepts. There exists inter-concept relations, which are common to any domain, and domain-dependent associations (e.g., care protocol is composedOf expected action). Attributes represent quantitative and qualitative features of particular concepts (e.g., code of drug), which take values in a given scale defined by the data type (e.g., integer, string, etc.).

Additionally, an ontology can contain instances (or individuals) (e.g., insulin is an instance of the concept drug)

Binary relations can be defined between concepts. In those cases, the concept at the origin of the relation represents the domain and those at the destination, the range. For example the relationship "hasDuration" has the concept "Unexpected event" as domain and the concept "Duration" as range. The relationships may fulfill properties such as symetry or transitivity.

In addition, concepts may represent overlapping sets of real entities (i.e. an individual may be an instance of several concepts simultaneously). In this case, ontology languages allow specify that two or more concepts are disjoint (i.e. individuals can only be instances of one of those concepts). Some standard languages have been developed to construct ontologies. They are usually based on first-order logic or on description logic. The most used are OWL (Ontology Web Language) [START_REF]Owl 2 web ontology language document overview[END_REF] and RDF (Resource Description Framework) [START_REF] Brickley | Rdf vocabulary description language 1.0: Rdf schema[END_REF].

B. The ECPO

In our research, ECPO has been designed with a synthesis of different methodological approaches [START_REF] Gómez-Pérez | Ontological engineering and the semantic web[END_REF] [6] [START_REF] Noy | Ontology development 101: A guide to creating your first ontology: Knowldege systems laboratory[END_REF] existing in the literature. This consists in the following steps:

• Specification: consists in identifying the domain covered by the proposed ontology, the purpose, the users and the data sources used to create it. The result of this step is the informal specification requirements document. • Conceptualization: consists in defining the concepts and relationships between them. The result of this step is the conceptual model of the ontology. • Implementation: once the conceptual model is defined, it will be encoded using an ontology language and an ontology editor. The result of this step is the ontology.

Fig. 4: Main concepts and relationships of ECPO

• Evaluation: after the development of the ontology, an evaluation will be done using an ontology reasoner in order to detect pitfalls.

1) Specification: This subsection details the first step of the ontology development which identifies:

• Domain of the ontology: chronic patient care protocol.

• Purpose of the ontology: allow healthcare professionals to interpret concretely the unexpected events or the unexpected actions done by chronic patient during the protocol application. • Users of the ontology: the healthcare professionals, the helpers and the patient. • Data sources: medical data about chronic diseases and care protocol.

2) Conceptualization: This step is the most important step in an ontology development. It consists in the definition of the content of the ontology. The proposed ontology ECPO includes the necessary concepts related to unexpected events and actions in a care protocol.

Figure 4 illustrates the main concepts and relationships of the proposed ontology ECPO. Boxes represent concept and lines represent relationships.

The main concepts composing this ontology are:

1) CareProtocol: is the chronic disease care protocol defined by the healthcare team which describes what the patient needs for monitoring his disease outside the hospital (cf. section III). The following relationships are defined for a CareProtocol:

• composedOf: CareProtocol!Disease, represents the disease associated with the care protocol. • composedOf: CareProtocol!Drugs, represents the drug associated with the care protocol. • composedOf: CareProtocol!Parameter, represents the parameter associated with the care protocol.

2) ExpectedAction: is a care protocol's action defined by the healthcare team which describes how the patient should treat his disease outside the hospital. The following relationship is defined for an ExpectedAction:

• composedOf: CareProtocol!ExpectedAction, represents actions to be executed in care protocol. 3) ExpectedEvent: represents a known occurrence defined in the initial care protocol. An expected event describes what may happen to the patient. The following relationships are defined for an ExpectedEvent:

• composedOf: CareProtocol!ExpectedEvent, represents the expected event that may occur in a care protocol. • hasConsequenceUnexpected: ExpectedEvent! Unex-pectedAction, associates an excepted event to an undefined action performed by the patient. 4) UnexpectedEvent: represents an undefined occurrence for the patient that may happen during his daily life. The following relationships are defined for an UnexpectedEvent:

• hasCause: UnexpectedEvent!Cause, is the reason why the unexpected event happens. The cause is given according to the patient's point of view, it may be correct or incorrect. • hasDuration: UnexpectedEvent!Duration, is the period during which the unexpected event occurred. • hasFrequency: UnexpectedEvent!Frequency, is the number of times that the unexpected event happens during daily care protocol. • hasConsequenceUnexpected:

UnexpectedEvent!UnexpectedAction, indicates that the patient may perform an unexpected action as consequence of an unexpected event.

• hasConsequenceExpected:

UnexpectedEvent!ExpectedAction, indicates that the patient may perform an excepted action as consequence of an unexpected event.

• supports: CareProtocol!UnexpectedEvent, represent the integration of all unexpected events in the initial care protocol. This integration is possible after the decision of healthcare professionals. 5) UnexpectedAction: an action performed by the patient that is undefined in the care protocol. The following relationships are defined for the UnexpectedAction:

• hasIntention:UnexpectedAction!Intention, describes the patient's determination to perform the unexpected action.

• supports: CareProtocol!UnexpectedAction, represents the integration of all unexpected actions in the initial care protocol after their analysis and validation by the healthcare professionals. The relationship between ExpectedEvent and ExpectedAction is not considered by ECPO because this relationship is defined in the initial care protocol and our proposed ontology is interested in cases of unexpected event or unexpected action or both.

In addition to these concepts and relationships between them, we defined some instances of the concepts in the ontology, for example:

• Unexpected event: have vomiting.

• Cause: overdose of a drug (Metformin 850 mg).

• Frequency: two times.

• Duration: two hours.

• Unexpected action: take anti-vomiting (Métopimazine 7,5 mg). • Intention: avoid further vomiting.

3) Implementation: This section describes the ECPO implementation. For that, we used the ontology language OWL-DL [START_REF] Pulido | Ontology languages for the semantic web: A never completely updated review[END_REF] and the open source ontology editor Protégé [START_REF] Noy | The knowledge model of protege-2000: Combining interoperability and flexibility[END_REF].

OWL-DL allows high level of expressiveness based on description logic and checks the inconsistency of the ontology using automatic reasoning. On the other hand, the open-source ontology editor Protégé is the most widely used tool for ontology development. Protégé allows the construction of ontologies in a simple and intuitive way and the generation of OWL code.

The ECPO is displayed in figure 5 using OWLViz plugin by Protégé. Fig. 5: ECPO in Protégé 4) Evaluation: After the development of the ECPO, the final step is conducted in two parts. On the one hand, the ontology consistency was evaluated via a reasoner in order to test the modelled knowledge of our proposed ontology. For that, we used Pellet 1 as a reasoner during the ontology development 1 http://clarkparsia.com/pellet process. On the other hand, the ontology will be tested by using SPARQL rules to identify the unexpected events and the unexpected actions. In order to validate this second part of the evaluation, we proposed some concrete scenarios related with the patient's expertise.

• Scenario 1: the patient forgets to take a dose of a drug at lunch (unexpected event), so he decides to take two doses of this drug at dinner (unexpected action). • Scenario 2: the patient is under an hypoglycemic episode (expected event), he eats sugar until the disappearance of hypoglycemia symptoms (and not 15 or 20 grams of sugar as indicated by the medical team (unexpected action) in order to avoid repetitive hypoglycemia episodes (intention). He thinks that an intense physical exercise is the cause of this episode (cause). • Scenario 3: the patient has vomiting (unexpected event)

during two hours (duration) when he takes too much a drug (cause), so he decides to take an anti-vomiting (expected action). • Scenario 4: the patient has headache (unexpected event)

for which he thinks the injection of insulin is the cause (cause). • Scenario 5: the patient takes two fruits before exercise (unexpected action) to avoid a malaise during exercise (intention). The formalization of SPARQL rules and the test of these five scenarios are part of our future works.

V. RELATED WORKS

This section presents the related works employing ontologies in medecine and home care.

A. Ontologies in medecine

The use of ontologies in medicine has been widely adopted. Some ontologies are implemented to represent taxonomies of medical concepts: for example, the taxonomy for health information technology terms [START_REF] Dixon | Development of a taxonomy for health information technology[END_REF], the taxonomy for the treatment of hypertension [START_REF] Mabotuwana | An ontology-based approach to enhance querying capabilities of general practice medicine for better management of hypertension[END_REF] or the Health Terminology/Ontology Portal (HeTOP) [START_REF] Grosjean | Teaching medicine with a terminology/ontology portal[END_REF]. Some ontologies are proposed in order to manage clinical guidelines. For example, in [START_REF] Kumar | Modular representation of the guideline text: An approach for maintaining and updating the content of medical education[END_REF], the authors design with OWL, concepts and relationships involved in a clinical guideline. In the same context, [START_REF] Ye | An ontology-based hierarchical semantic modeling approach to clinical pathway workflows[END_REF] proposes Context-Task Ontology (CTO) that contains the knowledge needed in the development of clinical guidelines.

There are other ontologies focus on the management of pathologies, for example, the ontology for the management of hypertension [START_REF] Steichen | Construction d'une ontologie pour la prise en charge de l'hypertension artérielle[END_REF] and the ontology for pneumology [START_REF] Baneyx | Construire une ontologie de la pneumologie aspects théoriques, modèles et expérimentations[END_REF].

B. Ontologies in home care

Ontologies have also been used in home care domain in order to represent and share a structured and well-defined terminology between different actors involved in health care. Some examples of ontologies focused on home care domain are Case Profile Ontology (CPO) and Actor Profile Ontology (APO) resulting from the K4Care project [START_REF] Valls | Using ontologies for structuring organizational knowledge in home care assistance[END_REF]. This project aimed to develop a web platform that delivers a set of home care services to all actors involved in home care for elderly patients. In this work, both ontologies are encoded in OWL-DL with Protégé and are built following the method On-To-Knowledge. CPO [START_REF] Riaño | An ontology for the care of the elder at home[END_REF] describes home care medical concepts integrating diseases, symptoms, syndromes, clinical intervention, assessment tests, laboratory analysis and social issues. On the other hand, APO [START_REF] Gibert | Enlarging a medical actor profile ontology with new care units[END_REF] is based on actors and includes the necessary knowledge related to the home care of elderly patients such as actors roles, actions, services, documents. Related with the same context, another ontology called OntoPAD [START_REF] Khalfi | Construction d'une ontologie pour la prise en charge des patients à domicile[END_REF] is proposed in the ABAH (Agent-Based Architecture for a Cooperative Information System) project. OntoPAD describes actors, actions and documents used in home care. In [START_REF] Paganelli | An ontology-based context model for home health monitoring and alerting in chronic patient care networks[END_REF], authors propose an ontology to represent health monitoring and alerting in chronic patient home care systems.

C. Discussion

Several researchers show the successful use of ontologies in the medical domain. Ontologies are used to structure the medical terminology about diseases or medical procedures, the home care for the representation of actors and interventions and the monitoring of chronic patients. More relative to our research, a few ontologies are related with home care domain and some of these ontologies are considered as a standard. Additionally, those ontologies represent and share medical knowledge about diseases, actors, organisation of medical intervention, etc. but neither consider the knowledge related with the daily realization of chronic patient care protocol at home, such as unexpected event (e.g., allergic reaction, missing drugs) or unexpected action (e.g., a diabetic patient eats 20g of sugar before sports while the quantity recommended by his doctor is 10g). In our research, we consider the patient as a mine of knowledge insufficiently exploited until now in home care. So, there is a need to exploit this patient's expertise in order to improve his care protocol and this is one of our challenges. Compared to these ontologies, the ECPO ontology aims to:

• Define and formalize knowledge about patient's expertise.

• Access to this knowledge.

• Store and reuse this knowledge.

• Get reasonning about patient's expertise and infer new expertise using properties and rules. In the next section, we present our findings and conclude with future works.

VI. CONCLUSIONS

In order to integrate the chronic patient's expertise acquired during the daily care protocol application, we propose an approach based on an ontology to represent the expertise's knowledge. The proposed ontology ECPO allows to identify in a concrete way the unexpected events and the unexpected actions done by the patient and helps the healthcare professionals to take decisions about the patient care protocol according to the ontology results.

As future works, the use of SPARQL rules will be considered, in order to determine prejudicial situations or good practices. In addition, we will focus on combine ontology with the patient's interface to provide expertise reports based on text or speech processing.


Artur Mariano
email: artur.mariano@sc.tu-darmstadt.de

Dongwook Lee
email: dongwook.lee@mail

Andreas Gerstlauer

Derek Chiou

Hardware and Software Implementations of Prim's Algorithm for Efficient Minimum Spanning Tree Computation

Keywords: Prim's algorithm, FPGA, Hardware acceleration, MST

Minimum spanning tree (MST) problems play an important role in many networking applications, such as routing and network planning. In many cases, such as wireless ad-hoc networks, this requires efficient high-performance and low-power implementations that can run at regular intervals in real time on embedded platforms. In this paper, we study custom software and hardware realizations of one common algorithm for MST computations, Prim's algorithm. We specifically investigate a performance-optimized realization of this algorithm on reconfigurable hardware, which is increasingly present in such platforms. Prim's algorithm is based on graph traversals, which are inherently hard to parallelize. We study two algorithmic variants and compare their performance against implementations on desktop-class and embedded CPUs. Results show that the raw execution time of an optimized implementation of Prim's algorithm on a Spartan-class Xilinx FPGA running at 24 MHz and utilizing less than 2.5% of its logic resources is 20% faster than an embedded ARM9 processor. When scaled to moderate clock frequencies of 150 and 250 MHz in more advanced FPGA technology, speedups of 7x and 12x are possible (at 56% and 94% of the ARM9 clock frequency, respectively).

Introduction

The minimum spanning tree (MST) problem is as an important application within the class of combinatorial optimizations. It has important applications in computer and communication networks, playing a major role in network reliability, classification and routing [START_REF] Graham | On the history of the minimum spanning tree problem[END_REF]. In many application domains, such as This work was performed while Artur Mariano was at UT Austin.

wireless and mobile ad-hoc networks (WANETS and MANETS), MST solvers have to be run online, demanding efficient, low-power, real-time implementations on embedded platforms.

In this paper, we focus on hardware implementation of one particular, common MST solver: Prim's algorithm [START_REF] Prim | Shortest connection networks and some generalizations[END_REF], which is used in several ad-hoc networks [START_REF] Benkic | Custom wireless sensor network based on zigbee. 49 th Elmar[END_REF] for topology calculation and other maintenance tasks, such as broadcasts, at both initialization and run time. In particular, several maximum broadcast lifetime (MBL) algorithms have been proposed in the past, all as derivatives of Prim's algorithm, running on a general directed graph [START_REF] Song | Energy-aware multicasting in wireless ad hoc networks: A survey and discussion[END_REF]. In such applications, Prim's algorithm is typically applied to medium to large network models with significant complexity, e.g. in terms of the number of nodes. In order to adapt to changing network conditions, the algorithm has to be executed in a distributed fashion at regular intervals on each node. In mobile and battery-operated nodes, cost, computational power and energy consumption are often critical resources, and high performance and low power realizations are required. For this purpose, platforms increasingly include reconfigurable logic to support hardware acceleration of (dynamically varying) tasks. This motivates an FPGA implementation of Prim's algorithm, where our primary focus is initially on improved real-time performance. To the best of our knowledge, there are currently no other studies of custom hardware realizations of this algorithm.

The rest of the paper is organized as follows: Section 2 provides a brief review of the theory behind Prim's algorithm including related work. Section 3 discusses the FPGA realization of the algorithm, and Sections 4 and 5 present the experimental setup and results. Finally, the paper concludes with a summary and outlook in Section 6.

Prim's Algorithm

Prim is a greedy algorithm that solves the MST problem for a connected and weighted undirected graph. A minimum spanning tree is a set of edges that connect every vertex contained in the original graph, such that the total weight of the edges in the tree is minimized.

The algorithm starts at a random node of the graph and, in each iteration, examines all available edges from visited to non-visited nodes in order to choose the one with the lowest cost. The destination of the chosen edge is then added to the visited nodes set and the edge added to the MST. The pseudo-code of the algorithm is presented as Algorithm 1.

Performance analysis

As with a majority of graph traversals, Prim's algorithm has irregular memory access patterns. In CPUs, this limits cache use and thus overall performance. As such, the algorithm is memory-bound with low computational requirements, and its performance is highly dependent on the organization of memory storage and memory access patterns. Depending on the used data structures, Prim's algorithm can have different asymptotic complexities. For common implementations using an adjacency matrix, Prim's complexity is O(V 2 ). For other implementations using adjacency lists with binary or Fibonacci heaps, the complexity reduces down to O((V + E) log V ) = O(E log V )) and O(E + V log V ), respectively. This comes at a higher fixed complexity per step with reduced regularity and exploitable parallelism. Hence, we focus in our work on the most common form using adjacency matrix based realizations.

Parallelism Analysis

Depending on the implementation of Prim's algorithm, it can exhibit some parallelism. For realizations that use an adjacency matrix to represent the graph, an improved implementation has been reported in [START_REF] Grama | Introduction to parallel computing: design and analysis of algorithms[END_REF], which is shown in Algorithm 2. This second version uses a supplemental array d to cache every value if it represents a cheaper solution than the ones seen so far, which allows lookups for minimum paths to be done in parallel.

In [START_REF] Grama | Introduction to parallel computing: design and analysis of algorithms[END_REF], the authors have pointed out that the outer while loop in this second implementation is hard to parallelize due to its inherent dependencies. However, the other operations in the body of the loop, namely minimum edge cost lookups (i.e. min-reduction steps) and updates of the candidate set can be processed in parallel over different elements of the supplementary array d. However, minreduction operations have to take into account that values representing edges E(s, d) in which s ∈ V T and d ∈ V T can not be considered.

for v ∈ (V-VT ) do if E(r,v) then d[v] ← W eight(E); else d[v] ← ∞ while VT = VG do Find a vertex u such that: | d[u] =min{d(v) | v ∈ (V -VT )} VT ← VT ∪ {u}; for all v ∈ (V -VT ) do d[v] ←min{d[v], W eight(u, v)};

Related Work

There are a number of implementations of Prim's method on CPUs. Some work has been done on parallel realizations targeting SMP architectures with shared address space, growing multiple trees in parallel and achieving a reported speedup of 2.64x for dense graphs [START_REF] Setia | A new parallel algorithm for minimum spanning tree problem[END_REF]. Additionally, in [START_REF] Gonina | Parallel Prim's Algorithm with a novel extension[END_REF] a distributed memory implementation, which supports adding multiple vertexes per iteration was demonstrated using MPI. Next to CPU implementations, GPUs were also used to compute Prim's algorithm [START_REF] Wang | Design and Implementation of GPU-Based Prims Algorithm[END_REF]. Such GPU implementations achieve only limited speedups of around 3x, highlighting the difficulties in implementing Prim's algorithm in an efficient and real-time manner. In [START_REF] Wang | Design and Implementation of GPU-Based Prims Algorithm[END_REF], the authors argued that the difficulty in parallelizing Prim's algorithm is very similar to other SSSP (single source shortest path) problems, like Dijkstra's algorithm.

FPGA Implementation

We used high-level synthesis (HLS) to synthesize C code for the different Prim variants down to RTL. We employed Calypto Catapult-C [START_REF] Bollaert | Catapult Synthesis: A Practical Introduction to Interactive C Synthesis High-Level Synthesis[END_REF] to generate RTL, which was further synthesized using Mentor Precision (for logic synthesis) and Xilinx ISE (for place & route). CPUs, for which we did not realize manually optimized implementations. Exploited optimizations of the outer loops did not provide us with substantial performance gains, while unrolling of loops did increase total area. Area increases by 3 times for a 8x unrolling degree. We were not able to pipeline the loops due to dependencies. The middle inner loop in Algorithm 1 has shown some small performance improvements when unrolled, with no significant difference between unrolling by 2, 4 or 8 times. Overall, the code did not exhibit significant benefits when applying loop optimizations.

Experimental Setup

We tested the performance of Prim's algorithm on 3 devices: a desktop-class CPU, an embedded processor and a Xilinx FPGA. Characteristics of tested platforms are summarized in Table 2. We evaluated algorithm performance on all platforms in order to measure possible speedups when moving to the FPGA.

For FPGA prototyping, we utilized a development board that includes a Freescale i.MX21 applications processor (MCU), which communicates with a Xilinx Spartan 3 FPGA over Freescale's proprietary EIM bus. The MCU contains an integrated ARM9 processor running at 266 MHz, an AMBA AHB bus and an EIM module that bridges between the AHB and the EIM bus. The ARM9 runs an embedded Linux distribution with kernel version 2.6.16 on top of which we implemented a testbench that feeds the FPGA with data and reads its output. We utilized both polling and interrupt-based synchronization between the ARM9 and the FPGA. On the FPGA side, we manually integrated Catapult-generated RTL with a bus slave interface connection to the EIM bus, using a custom developed EIM slave RTL IP module to receive and send data from/to the CPU. Designs were synthesized to run at 24 MHz on the FPGA. The bus interface clock, on the other hand, was set to run at 65 MHz.

Measurements of FPGA execution times have been made both including and excluding communication overhead. To obtain total FPGA execution times, we measured the time stamps between sending the first data item and receiving the last result on the CPU side. This includes overhead for OS calls, interrupt handling and EIM bus communication. In addition, we developed a VHDL/Verilog testbench and performed simulations to determine the raw FPGA computation time without any such communication overhead.

For our experiments, the algorithm ran on all platforms with fully-connected3 random graphs with orders (sizes) of up to 160 nodes (as determined by FPGA memory limitations). When compiling the code for the CPUs, we did not perform any manual tuning, solely relying on standard compiler optimizations using GCC 4.2.3 and GCC 4.5.2 for ARM9 and Pentium processors, respectively.

Results

Figure 1(a) shows total execution times of running Algorithm 1 for graphs with up to 160 nodes on the Intel Pentium, the ARM9 and the FPGA. We report execution times as the median of 5 measurements.

The Intel CPU clearly outperforms other devices. While a Pentium CPU is neither common in embedded domains nor comparable to other platforms in terms of price, we include its results as a baseline for reference.

Compared to the ARM9 processor, execution times on the FPGA are slightly larger across all graph orders. However, in this setup, measured execution times include communication overhead, which may limit overall FPGA performance. On the other hand, computation and communication are overlapped in the FPGA and computational complexities grow with the square of the graph size whereas communication overhead only grows linearly. Coupled with the fact that execution time differences between the ARM and the FPGA increase with growing graph sizes, this indicates that communication latencies are effectively hidden and clock frequency and/or hardware resources are limiting performance. FPGA-internal storage sizes limit possible graph sizes to 160 nodes in our case. This limitation could be overcome by taking advantage of matrix symmetries: the same matrix could be represented with half of the data, enabling the study of bigger inputs, e.g. to see if FPGAs could overcome the ARM9. However, as previously mentioned, execution times are computation bound and relative differences of both devices are growing for larger inputs. As such, extrapolating would indicate that the FPGA will not be able to outperform the ARM9 even for larger inputs.

To take advantage of FPGA strengths with increasing benefits for any additional parallelism available in the algorithm [START_REF] Singleterry | Field-Programmable Gate Array Computer in Structural Analysis: An Initial Exploration[END_REF][START_REF] Ornl | Performance Evaluation of FPGA-Based Biological Applications Olaf[END_REF], we have tested the second implementation of Prim's algorithm on dedicated hardware. Figure 1(b) shows the results of these experiments as measured on the FPGA and on the ARM9, where FPGA performance is reported both with and without communication overhead.

Algorithm 2 clearly performs better on both devices, with speedups of around 37.5x and 68.5x compared to Algorithm 1 for the ARM9 and FPGA, respectively. Even though the FPGA can take more advantage of the second implementation's parallelism than the single-core ARM9, the ARM9 still outperforms the FPGA in total execution time. However, when considering raw execution times without communication overhead, the FPGA performs better.

In addition, overall FPGA performance of designs on our board is limited to a maximum frequency of 24 MHz. To extrapolate possible performance, we scaled raw execution times for a graph with 160 nodes (requiring around 8.8 million clock cycles) to other clock frequencies, as shown in Figure 1(c). Assuming the bus interface is not a limiting factor, running the developed design on an ASIC or better FPGA in a more advanced technology would result in theoretical speedups of 5x and 10x for moderate clock frequencies of 100 MHz and 200 MHz, respectively, as also shown by Figure 1(c). However, this would most likely also come at increased cost, i.e. decreased price/efficiency ratios.

Summary and Conclusions

In this paper, we presented an FPGA implementation of Prim's algorithm for minimum spanning tree computation. To the best of our knowledge, this represents the first study of realizing this algorithm on reconfigurable hardware. Prim's algorithm plays a major role in embedded and mobile computing, such as wireless ad hoc networks, where FPGAs may be present to support hardware acceleration of performance-critical tasks. We followed a state-of-the-art C-to-RTL methodology using HLS tools to synthesize a high-level C description of two algorithmic variants down to the FPGA, with high performance being the primary goal. On our Spartan 3 FPGA with 66,560 LUTs, 33,280 CLB slices and 68,027 DFFs, our designs utilizes less than 2.5% of each type of logic resource.

Our results show that, considering total wall-time for any of the tried implementations, our unoptimized FPGA implementation running at a low clock frequency dictated by the bus interface reaches about the same performance as an implementation running on an embedded ARM core. However, in terms of raw computation cycles without any communication or OS overhead, the FPGA design achieves a speedup of ≈1.21. Using more advanced FPGA technology, with a different device, running at a moderate frequency of 150 MHz (55% of the ARM9's 266 MHz frequency), speedups of around 7.5x should be achievable. Compared to gains of 2.5-3x achieved on multi-core CPUs or GPUs, such an FPGA implementation can achieve better performance at lower cost and power consumption.

Prim's algorithm in its default implementations is limited in the available parallelism. In future work, we plan to investigate opportunities for further algorithmic enhancements specifically targeted at FPGA and hardware implementation, e.g. by speculative execution or by sacrificing optimality of results for better performance.

Algorithm 2 :

 2 Second implementation of Prim's algorithm. Input: A non-empty connected weighted graph G composed of vertexes VG and edges EG, possibly with null weights; Result: The minimal spanning tree in the d array; Initialization: VT = {r} and d[r] = 0, where r is a random node from V ;

2 Fig. 1 .

 21 Fig. 1. Total runtime and speedup of algorithms for graphs with up to 160 nodes.

Algorithm 1 :

 1 Standard Prim's algorithm.

	Input: A non-empty connected weighted graph G composed of vertexes VG and
	edges EG, possibly with null weights;
	Result: The minimal spanning tree in the f inalP ath array;
	Initialization: VT = {r}, where r is a random starting node from V ;
	while VT = VG do
	minimum ← ∞;
	for Visited nodes s ∈ VT do
	for all edges E(s,v) and v / ∈ VT do
	if Weight(E) ≤ minimum then
	minimum ← W eight(E);
	edge ← E;
	newV isited ← v;
	f inalP ath ← f inalP ath ∪ {edge};
	VT ← VT ∪ {newV isited};

Table 1 .

 1 Table1summarizes LUT, CLB, DFF and BRAM utilizations over different graph sizes for both implementations. We have realized the algorithm for graph sizes up to N = 160 nodes, where graphs are stored as adjacency matrices with N × N float values representing edge weights (and with negative values indicating edge absence).Within Catapult-C, we exploited loop unrolling and chaining only at a coarse granularity, i.e. for the bigger outer loops. This allows a fair comparison with FGPA synthesis results.

	Graphs size 40	70 100 130 160
		Algorithm 1
	LUTs	1047 1044 1109 1425 1448
	CLBs	523 522 554 712 724
	DFFs	563 623 628 635 624
	BRAMs	6	12	21	33	48
		Algorithm 2
	LUTs	1029 1145 1198 1368 1425
	CLBs	514 572 599 684 712
	DFFs	592 622 635 658 653
	BRAMs	7	13	22	34	49

Table 2 .

 2 Test platform specifications.

	Device	CPUs	FPGA
	Manufacturer	Intel	ARM	Xilinx
	Brand	Pentium M ARM 9 Spartan
	Model	T2080	926EJ-S	3
	Max clock	1.73 GHz 266 MHz 400 MHz
	Cores	2	1	-
	System mem 2 Gbytes 32 Mbytes 1.8 Mbit
	L1 Cache	32kB	16kB	-
	L2 Cache	4MB	-	-
	Pipeline	12 stage	5 stage	-
	Year	2006	2001	2003
	Launch price	$134	$15.5	$3.5

Graphs with (k -1)-connectivity with k = order.

Acknowledgments. Authors want to thank UT Austin|Portugal 2011 for enabling this research collaboration (www.utaustinportugal.org).


Simon Gansel

Stephan Schnitzer

Frank Dürr

Kurt Rothermel

Christian Maihöfer

Towards Virtualization Concepts for Novel Automotive HMI Systems

Many innovations in the automotive industry are based on electronics and software, which has led to a steady increase of electronic control units (ECU) in cars. This brought up serious scalability and complexity issues in terms of cost, installation space, and energy consumption. In order to tackle these problems, there is a strong interest to consolidate ECUs using virtualization technologies. However, current efforts largely neglect legal constraints and certification issues and the resulting technical requirements. In this paper, we focus on the consolidation of graphics hardware through virtualization, which received a lot of interest in the car industry due to the growing relevance of HMI systems such as head unit and instrument cluster in modern cars. First, we investigate relevant ISO standards and legal requirements and derive seven technical requirements for a virtualized automotive HMI system. Based on these requirements, we present the concept for a Virtualized Automotive Graphics System (VAGS ) that allows for the consolidation of mixed-criticality graphics ECUs.

Introduction

Over the years, the automotive industry, which was mainly driven by hardware and mechanics in the past, has changed to an industry where about 90 % of all innovations are driven by electronics and software [START_REF] Ebert | Embedded software: Facts, figures, and future[END_REF]. In current high-end cars, the IT hardware and software architecture is represented by more than 70 physically separated electronic control units (ECU), which are partitioned into different domains and connected via a network of different communication bus systems. To deploy new functionalities, the OEMs often add further ECUs to the vehicle. This trend of "new function, new ECU" has lead to serious scalability issues in terms of cost, installation space, and energy consumption. In order to deal with these problems and to stop this trend of adding further ECUs, there is a strong interest in the car industry to consolidate ECUs using virtualization technologies to share the same hardware between different components.

In this paper, we focus on the consolidation of graphics hardware since it is of high relevance in modern cars. An increasing number of automotive functionalities and applications require highly sophisticated graphical representations in 2D or 3D based on hardware acceleration. For instance, the Head Unit (HU) uses displays integrated into the backside of the front seats and center console to display multimedia content; and displays connected to the Instrument Cluster (IC) show car specific information like current vehicle speed or warnings. Therefore, HU and IC are good candidates for hardware consolidation. Each virtualized ECU runs in a dedicated virtual machine (VM), and a virtual machine monitor (VMM) acts as middleware between VMs and hardware. Besides the already mentioned general benefits, the virtualization of IC and HU provides advantages such as the flexible placement of graphical output on previously separated displays, which is a matter of software implementation only. Moreover, virtualization enables OEMs to deploy custom applications inside a dedicated VM that is isolated from HU and IC.

This paper makes the following two contributions to enable the consolidation of graphics hardware in vehicular systems. First, we thoroughly analyze relevant ISO standards and legal requirements and derive seven technical requirements for a virtualized automotive HMI system. Such requirements have been largely neglected by current virtualization efforts, which did not target automotive systems with their specific requirements, in particular, with respect to safety. For OEMs, the certifiability of automotive system functionalities is highly relevant. According to [16, ISO 26262], for each functionality safety-criticality shall be identified and mapped to criticality-classes3 . To fulfill the criticality-level, the severity and likelihood of failures must be determined using, for instance, failure mode and effects analysis (FMEA) [START_REF] Stamatis | Failure Mode and Effect Analysis: FMEA from Theory to Execution[END_REF]. Moreover, certifiability also applies to custom third-party applications. For instance, [12, ISO 15005] prohibits displaying movies to the driver while the vehicle is in motion. These specific regulations impose challenging technical requirements to virtualization.

As second contribution, we present a concept for a Virtualized Automotive Graphics System (VAGS ). We elaborate on the challenges that are due to the identified requirements to consolidate mixed-criticality graphics ECUs as used, in particular, by the HU and IC. Although virtualization is a mature technology for general resources like CPU or main memory, existing concepts do neither provide sufficient isolation for accessing shared graphics hardware (GPU) and input devices (e.g., steering wheel buttons), nor do they provide sufficient isolation for implementing the flexible presentation of application windows. Our proposed architecture can be used as starting point for the future implementation of the specified components.

The rest of this paper is structured as follows. In the next section, we analyze automotive standards and guidelines and derive technical requirements. In Section 3, we present the concept for a VAGS. In Section 4, we briefly describe a first proof-of-concept implementation of our concepts. Finally, we discuss related work in Section 5 and conclude this paper with a summary and outlook onto future work in Section 6.

Requirements

In this section, we discuss requirements that are relevant for automotive HMI systems. Automotive application development is constrained by ISO standards, automotive design guidelines, legal requirements, and OEM specific demands. The design guidelines (e.g., [1, AAM 2006], [5, ESoP 2008], [18, JAMA 2004]) in the automotive domain are almost completely derived from the following ISO standards.

- [11, ISO 11428 R6 -Certifiability For an OEM, certifiability is an essential part of the software development process, e.g., by using methods like FMEA [START_REF] Stamatis | Failure Mode and Effect Analysis: FMEA from Theory to Execution[END_REF]. The development process for certified software, in particular, for high criticality levels, is quite complex and expensive. A key indicator for complexity is the number of function points that correlates with the approximated number of software defects [START_REF] Ebert | Embedded software: Facts, figures, and future[END_REF]. Hence, a system shall be developed with respect to an easy certification according to [16, ISO 26262].

R7 -System Monitoring

System Monitoring puts the focus on logging, detecting, and reacting to events that possibly are relevant to provide safety.

R7.1 -Secure Boot: Derived from [13, ISO 15408-2], the system shall provide secure boot to ensure the integrity of the system. Compromising the system (14.6.9.1) or system devices or elements (14.6.9.2) by physical tampering shall be unambiguously detected. R7.2 -Auditing: The auditing of all safety-critical related events shall be guaranteed to ensure traceability of system activities in an automotive HMI system that potentially violate safety or security. Therefore, direct hardware access must not be permitted to ensure that auditing cannot be bypassed. For a potential violation analysis, a fixed set of rules shall be defined for a basic threshold detection, [13, ISO 15408-2] (7.3.2). To indicate any potential violation of the system-defined rules, the monitoring of audited events shall also be based on a set of rules (7.3.8.1) that must be enforced by the system either as an accumulation or a combination of a subset of defined auditable events which are known to threat the system security (7.3.8.2). Similarly, all changes to policies initiated by applications shall be monitored and verified. R7. [START_REF] Ebert | Embedded software: Facts, figures, and future[END_REF] A list of potential failures and service discontinuities have to be supervised by a watchdog to detect entering of failure states. Furthermore, for a de-fined subset of functions that are required to complete successfully, failure scenarios shall be specified that ensure recovery (14.7.11.1). R7.7 -System Integrity: In case of unrecoverable failures, the system shall be able to switch to degraded operation mode to preserve system integrity. A list of failure types shall be defined for which no disturbance of the operation of the system can take place [13, ISO 15408-2] (15.1.7.1). Moreover, the system shall ensure the operation of a set of capabilities for predefined failure types (15.1.6.1). This includes the handling of DoS attacks and detection of illegitimate policy changes. Some events have to be maintained in an internal representation to indicate if any violations take or took place. This includes the behavior of system activities for the identification of potential violations (7.3.10.2-3) like state changes (7.3.10.1).

Architecture

In this section, we briefly describe the architecture of a Virtualized Automotive Graphics System (VAGS ) (cf. Fig. 1) that addresses the identified requirements. Certifiability (R6) applies to the complete development process, all other requirements are represented by the functionalities of the components of our architecture. With respect to certifiability, we follow the approach of a microkernelbased VMM where drivers run in user space rather than kernel space. Therefore, the kernel code size is very small and easier to certify [START_REF] Ebert | Embedded software: Facts, figures, and future[END_REF]. If driver code crashes, this does not affect the VMM. The Virtualization Manager runs in a dedicated VM and exclusively manages shared resources. It contains relevant drivers, e.g., for GPU and input devices. This ensures that access to all shared resources is controlled by a single trustworthy VM. Indirect hardware access by VMs facilitates Virtualized Graphics Rendering (R4) and System Monitoring (R7). Additionally, the Virtualization Manager contains multiple software components ensuring that every hardware access by VMs is in compliance with our requirements. Note that our architecture only shows four exemplarily VMs. However, we do not restrict the number of VMs. Therefore, it is possible to deploy additional VMs if needed. In order to access hardware, the HU and IC VMs communicate with the Virtualization Manager VM. For this bidirectional communication, a Trusted Channel (R3) is required to support secure communication between the different virtual machines. A trusted channel is provided by the cooperation of the Isolated Communication Channel and the Authentication Manager. The Isolated Communication Channel provides integrity and isolation for communication (R3.1) between applications and the Virtualization Manager. To initiate a connection, applications first have to provide valid credentials to the Authentication Manager, to guarantee non-repudiation of origin and receipt (R3.2). In particular, this is required for the communication between the graphical applications located on HU or IC and the virtualization manager, which needs to be trustworthy to ensure that the active policy is never violated.

Permission and Policy Management (R5) ensures that applications are getting their defined permissions to use functionalities or resources provided by the Input Manager, Window Manager, or GPU Scheduler. Permissions are represented by the active policy, which depends on the current state (R5.1), e.g., "vehicle is parking" or "vehicle is in motion". The policy management is configured by rules that define transitions between policies performed whenever state changes (R5.2) in defined time constraints (R5.3). The Input Manager performs Input Event Handling (R1) and is responsible for dispatching user input events to the intended applications (R1.1). Since the processing of user input is subject to time restrictions, a minimal delivery time for input events to the applications must be ensured (R1.2).

The GPU Scheduler is responsible for Virtualized Graphics Rendering (R4) according to drawing requirements and permissions of graphical applications. To this end, applications are assigned priorities that define the amount of dedicated GPU resources (R4.1). Besides priorities, according to (R4.2), deadlines apply to the graphical rendering of certain applications like the tachometer. The GPU scheduler, therefore, has to sequence graphics commands, schedule application requests and provide isolation between different contexts (R4.3).

The Window Manager provides the functionality for creating, positioning, and displaying windows of graphical applications. This represents a paradigm shift from fully user-defined window management to restricted window creation and positioning (R2). Applications with sufficient permissions interact with the Window Manager to create windows and to modify properties like size and position (R2.1). Moreover the Window Manager is responsible for correct window stacking (R2.2) and meeting rendering time requirements (R2.3).

In order to guarantee Secure Boot (R7.1), the integrity of code that is loaded must be verified, using, for instance, approaches described in [START_REF] Gallery | Trusted computing: Security and applications[END_REF]. The Auditing component (R7.2) traces all relevant system activities and interactions. The gathered traces can be used by the Watchdog and System Monitor components to detect inconsistencies (for R7.3 to R7.7). The Watchdog supervises relevant system functionalities and emits signals in case of system malfunctioning as required for R7.3 to R7.6. The System Monitor receives signals of detected system malfunctions from the Watchdog. Rules are used to configure its reaction on these signals.

Implementation

We have created a proof-of-concept implementation for the main parts of our proposed VAGS architecture. The implementation consists of a Window Manager using an hierarchical access control management for display areas and input events. It supports permission negotiation between different virtual machines and applications. The applications create, destroy and move their windows using a dedicated Window Manager API. Based on their permissions, applications are allowed to display their windows in dedicated display areas. Furthermore, each display area is mapped to a depth level representing the priority of the application. This prevents that application windows are overlapped by windows of applications with lower priority. The Window Manager has a dedicated compositing backend which is currently (as an intermediate step) based on X11 compositing.

Linux was used as operating system for the Virtualization Manager and the graphical applications. As a first step we used an x86 standard PC platform and created a set of automotive applications like speedometer and navigation software to demonstrate the feasibility of the concept.

For communication between applications located on different VMs, a transport layer has been implemented. The channels use a custom ring buffer implementation and shared memory to establish data transfer channels. These channels are used for forwarding graphics data like EGL, OpenGL ES 2.0, and API commands of the Window Manager, from the graphics applications to the Virtualization Manager. The management of shared memory is performed by a dedicated component in the Virtualization Manager. To allow applications on different VMs for initiating new connections, in each VM a management process performs the mapping of shared memory segments to applications. The Virtualization Manager performs simple scheduling using synchronization mechanisms of OpenGL ES 2.0.

Related Work

The concept of microkernel-based VMMs in virtualization is well known for many years. The focus on safety increased during the last few years, e.g., the NOVA microkernel [START_REF] Steinberg | Nova: a microhypervisor-based secure virtualization architecture[END_REF]. Moreover, certifiability became more important, at least in case of the VMM [START_REF] Klein | seL4: Formal verification of an OS kernel[END_REF].

A large number of work related to virtualization and graphics applications has been described in the literature. Due to space constraints, we only focus on windowing systems, GPU scheduling, and graphics forwarding in the following. According to [START_REF] Epstein | Trusting x: Issues in building trusted x window systems -or -what's not trusted about x[END_REF], the X11 Windowing System does not provide security. Trusted X [START_REF] Epstein | A prototype b3 trusted x window system[END_REF] has been proposed to provide security for the X Windowing System targeting the requirements in TCSEC B3 (superseded by [13, ISO 15408-2]) but has not been certified. To provide isolation, an untrusted X server and a window manager is deployed for each security level which impacts scalability. Therefore, mutual isolation of applications is practically impossible due to scalability issues. Nitpicker [START_REF] Feske | A nitpicker's guide to a minimal-complexity secure gui[END_REF] is a GUI server with security mechanisms and protocols to provide secure and isolated user interaction using different operating systems. To achieve isolation between these OSes, Nitpicker uses the VMM L4/Fiasco [START_REF] Hohmuth | The Fiasco kernel: System Architecure[END_REF]. The EROS Window System (EWS) [START_REF] Shapiro | Design of the eros trusted window system[END_REF] targets the protection of sensitive information and the enforcement of security policies by providing access control mechanisms and enforcing the user volition. A common denominator of Trusted X, Nitpicker, and EWS is that they only focus on security and thus do not comply with Input Event Handling (R1), Restricted Window Creation and Positioning (R2), and System Monitoring (R5). DOpE [START_REF] Feske | Dope -a window server for real-time and embedded systems[END_REF] is a window server that assures redrawing rates windows of real-time applications and provides a best-effort service for non-real-time applications. DOpE is based on L4/Fiasco [START_REF] Hohmuth | The Fiasco kernel: System Architecure[END_REF] for isolation and IPC. However, policies are not enforced. Common to all these windowing systems is the fact that they do not support graphics hardware acceleration and do not provide any timing guarantees for rendering and displaying.

GERM [START_REF] Bautin | Graphic engine resource management[END_REF] provides GPU resource management targeting fairness without addressing isolation or prioritization. Timegraph [START_REF] Kato | Timegraph: Gpu scheduling for real-time multi-tasking environments[END_REF] enhances these concepts and provides priority-based scheduling of GPU command groups for DRI2. However, for the execution time of an GPU command group no upper bound can be guaranteed and the performance is heavily degraded. Additionally, due to latency induced by synchronous GPU operations, applications using the X Server and double buffering encounter additional problems addressed in [START_REF] Kato | Resource sharing in gpu-accelerated windowing systems[END_REF]. However, the X Server itself does not provide sufficient isolation mechanisms and therefore cannot be used for an automotive HMI system.

VMGL [START_REF] Lagar-Cavilla | VMMindependent graphics acceleration[END_REF] is an approach to transfer OpenGL commands from an OpenGL client to an OpenGL server using a TCP/IP connection. However, using TCP/IP causes significant latency and overhead. Blink [START_REF] Hansen | Blink: Advanced Display Multiplexing for Virtualized Applications[END_REF] is a display system which focuses on the safe multiplexing of OpenGL programs in different VMs. Blink uses an OpenGL Client/Server to transmit the OpenGL commands and data via shared memory to a "Driver VM". The "Driver VM" is responsible for the execution of the OpenGL commands on the GPU. Blink proposes "BlinkGL" which increases performance, but requires applications to be modified.

Summary and Future Work

In this paper, we presented requirements for novel automotive HMI systems. From relevant ISO standards, we derived seven technical requirements for the physical consolidation of mixed-criticality graphical ECUs such as head unit and instrument cluster. Additionally we presented VAGS (Virtualized Automotive Graphics System), a novel automotive HMI concept which provides isolation between custom graphics applications running in dedicated VMs. Although these applications are not certified, a VAGS can guarantee that no unintended interference with certified OEM software can take place. We presented a suitable architecture and created a proof-of-concept implementation. In future work we are going to improve graphics scheduling by using execution time prediction of graphics commands and by using a more suitable scheduling algorithm. Furthermore, we implement system monitoring, auditing, a watchdog, and integrate authentication concepts. Since the current implementation is based on X11, which has a couple of drawbacks, we plan to switch to a native implementation tailored to embedded hardware. Finally, we evaluate and optimize the performance of our implementation depending on different application scenarios.

Fig. 1 .

 1 Fig. 1. Architecture

  Furthermore, country-specific legal requirements constrain the definition of the priorities, e.g., German law requires the constant visibility of the speedometer while the vehicle is in motion (StVZO §57[START_REF] Janker | Straßenverkehrsrecht: StVG, StVO, StVZO, Fahrzeug-Zulas-sungsVO, Fahrerlaubnis-VO, Verkehrszeichen[END_REF]). Additionally, visual information must be presented in a consistent way[12, ISO 15005] (5.3.2.2.1). R2.3 -Timing Constraints: An automotive HMI system shall enable applications to provide important information to the driver within given time The GPU is a controlled resource according to [13, ISO 15408-2]. To prevent unintended interference, it must be possible to provide guarantees to certain applications that they are provided sufficient GPU resources such as processing time. Therefore, it must be possible to control which GPU resources individual windows, graphical applications, or VMs are allowed to use (15.3.6.1 and 15.3.7.1-2). R5.2 -Dynamic Policy Changes: Authorized software components shall be able to apply changes to policies during runtime. This includes granting and revoking permissions on both, currently active and currently inactive policies. As for R5.1, deadlines apply to dynamic policy changes. Where applicable and allowed, the driver shall be able to change the active policy to manipulate the flow of information (5.3.3.2.3). R5.3 -Presentation Enforcement: The system-defined rules shall enforce the presentation of legally required messages and traffic-situation-relevant messages. Presentation requires that those messages are visible and perceivable, in particular, if state changes require driver attention [12, ISO 15005] (5.3.2.2.2). Furthermore, state-related information shall be displayed either continuously or upon request by the driver.

	R2.2 -Priority-based Displaying of Windows: If multiple windows shall R4.2 -Rendering Time Constraints: Not only comparative requirements
	be displayed, the importance of each of them must be defined. Importance (like priorities) but also absolute timing requirements have to be fulfilled. A
	is represented by priorities, which can depend on safety requirements and response to a drivers tactile input shall not exceed 250 ms [12, ISO 15005]
	software ergonomic aspects (5.2.4.2.4) that must be met by the system (5.2.4.2.3). Similarly, emergency signals may require constant redraw rates
	(5.2.4.3.3). Moreover, they can depend on urgency and criticality which to represent flashing lights [11, ISO 11428] (4.2.2). This requires appropri-
	have to be defined [14, ISO 16951] (3.5). Additionally, appropriate reac-ate CPU and GPU resources and imposes a minimum frame rate since the
	tions (e.g., behavior in case of conflicts) shall be enforced [14, ISO 16951] delay between two consecutive frames is constraint by an upper bound. The
	] Ergonomic requirements for the perception of visual danger -[12, ISO 15005] Requirements to prevent impairment of the safe and effective signals. operation of the moving vehicle. -[14, ISO 16951] Priority-based presentation of messages. -[15, ISO 2575] Symbols for controls and indicators. -[13, ISO 15408-2] Security in IT systems. -[16, ISO 26262] Risk-based assessment of potentially hazardous operational situations and of safety measures. In the following, we propose seven technical requirements for automotive HMI system. For each of them we added references to relevant sections of the men-tioned ISO standards. R1 -Input Event Handling R1.1 -Restricted Access Control: For user input events access control is required and it shall not violate any of the following constraints [12, ISO 15005]. Applications using dialogues shall not require to use input devices in a way that demands removal of both hands from the steering wheel while driving (5.2.2.2.2). Additionally, exiting a dialog or an application shall always be possible (5.3.3.2.1) unless legally required or traffic-situation-relevant (5.3.3.2.3). R1.2 -Restricted Processing Time: A maximum processing time for input event handling shall be met. For instance, response to tactile user inputs shall not exceed 250 ms (5.2.4.2.3). R2 -Restricted Window Creation and Positioning R2.1 -Restricted Visibility of Windows: Usually, graphical applications use API functions to change the visibility of windows, e.g., to create, hide, or position them. This functionality must be restricted, and functions not in-upper bound must be known to determine the effectiveness of safety-critical messages [14, ISO 16951] (Annex F) and also to allow for the definition of delays after which messages are displayed (Annex B). (Annex B). R4.1 -Priority Handling: Application windows must be assigned a prior-R4.3 -GPU Resource Isolation:
	tended to be used by the driver must be inaccessible for him [12, ISO 15005] ity which determines how GPU commands are processed [12, ISO 15005]
	(5.2.2.2.4). (5.2.4.2.4 and 5.2.4.3.3), [13, ISO 15408-2] (15.2.5.1-2 and 15.2.6.1-2).

constraints. This means that windows showing information shall be visible within given time constraints

[12, ISO 15005]

(5.2.4.3.4)

. If applications require user interaction, e.g., if a user selects a radio channel, the flow of information must not adversely affect driving (5.2.4.2.1). Concretely, according to [1, AAM 2006] Section 2.1, each glance shall not exceed 2 seconds. Hence, any kind of animation shall not run longer than 2 seconds. R3 -Trusted Channel R3.1 -Integrity and Confidentiality: In environments where applications run inside VMs, communication is inevitable. This holds for communication that previously used dedicated communication hardware and is now replaced by software-based inter-VM communication. According to [13, ISO 15408-2], communication between applications and hardware must provide integrity and confidentiality, for both user data (14.5.8.2) and software components providing relevant functionality (17.1.5.3). All applications that need trusted communication shall be able to use it (17.1.5.2). R3.2 -Authentication and Non-Repudiation: Identification shall be assured even between distinct systems (17.1.5.1), which also applies to inter-VM communication. A trusted channel also requires non-repudiation of origin (8.1.1 and 8.1.6.1-3) and receipt (8.2.1 and 8.2.6.1-3). This requires authentication and may also involve cryptographic key management (9.1.1) and key access (9.1.7.1).

R4 -Virtualized Graphics Rendering

In our system, multiple VMs have shared access to a single GPU, and therefore the VMM has to provide isolation. That is, unintended interference between applications must not occur.

R5 -Reconfiguration of Policies

A set of permissions that apply to user input events, application windows, and the related scheduling and isolation is called a policy. At each point in time, exactly one policy is active, though policies are dynamically switched during runtime depending on the system state.

R5.1 -Dynamic State Changes:

In accordance to

[12, ISO 15005

], a state change happens either on user request or automatically by system-defined rules. A state can depend on a current vehicle condition like "vehicle is in motion" which could require the deactivation of applications that are not intended to be used by the driver while the vehicle is in motion (5.2.2.2.4).

Otherwise, an automotive HMI system shall provide sufficient information and warnings to provide the driver with the intended purpose in a current state. For every state change, specified deadlines apply to determine a consistent and accurate transition between different states. The definition of states and system behavior is explained in more detail in

[14, ISO 16951]

(3.3 and Annex E).

[16, ISO 26262] specifies five safety requirement levels: Four ASIL (Automotive Safety Integrity Level) ranging from ASIL-A (low criticality) to ASIL-D (high criticality), and one no-criticality level QM (Quality Management)

Acknowledgement

This paper has been supported in part by the ARAMiS (Automotive, Railway and Avionics Multicore Systems) project of the German Federal Ministry for Education and Research (BMBF) with funding ID 01IS11035.