Romain Leconte
email: romain.leconte@irt-saintexupery.com

Eric Jenn
email: eric.jenn@irt-saintexupery.com

Guy Bois
email: guy.bois@spacecodesign.com

Hubert Guérard
email: hubert.guerard@spacecodesign.com

Make Life Easier for Embedded Software Engineers Facing Complex Hardware Architectures

Keywords: OpenMP, FPGA, Design Space Exploration, Embedded systems

The increasingly parallel execution platforms -mixing multi-cores, GPUs, and programmable logic (namely, FPGA) -require new development techniques and technologies to be used efficiently. Software developers are hampered by the complexity of modern SoCs and MPSoCs. In particular, the complexity of the hardware design flow makes the exploitation of FPGAs difficult and expensive, especially in cases where the design space to be explored is large. Therefore, this paper proposes a design flow that offers joint support of both hardware and software flows making life easier for embedded software engineers. It is based on a HW/SW codesign approach where a sequential C code annotated with OpenMP offloading directives is progressively transformed into an FPGA implementation. OpenMP has been selected because it is a widely adopted solution in the high-performance computing domain, but also because work is currently going on to extend its scope to embedded real-time systems. This paper identifies the important properties required in such a flow, demonstrates how they are supported by our workflow, and, finally, presents results of our approach on an image processing function deployed on both Zynq and Cyclone platforms.

I. INTRODUCTION AND CONTRIBUTIONS

Optimizing the use of complex modern Multi-Processor System on Chip (MPSoC) require significant efforts for the software and hardware developers. They have to cope with an ever increasing number of homogeneous or heterogeneous cores, the presence of SIMD units, AI accelerators, GPGPUS, and now, FPGA.

On the software side, to fully exploit the high level of parallelism offered by the platform, software engineers have now to expose as much as possible the parallelism of their applications, at coarse (e.g., process or thread), and fine grain (e.g., loop). When the level of hardware parallelism is high, this activity definitely needs to be supported by appropriate abstractions and modeling or programming languages. OpenMP [START_REF] Guérard | OpenMP Application Programming Interface Version 4[END_REF] is one possible solution.

OpenMP is one of the most popular technologies to support the large scale parallelization of applications. OpenMP is an API specification maintained by the OpenMP workgroup 1 . It proposes a set of source-level annotations to expose the parallelism of applications at multiple levels: loops, tasks, data, etc., and manage communications between the parallel components on the basis of the shared memory communication paradigm. Since version 4.0 [START_REF] Guérard | OpenMP Application Programming Interface Version 4[END_REF], OpenMP also supports heterogeneous architectures. Using the target directive, parts of the code can be offloaded from the main CPU (or host) to one or several accelerators implemented using general purpose processors, GPGPUs, or FPGAs. Using these offloading annotations, the code running on the host can move data from its memory to the devices (or target) memory, execute logic on the target device and move data back to the host memory.

On the hardware side, software developers are hampered by the complexity of modern SoCs and MPSoCs. Although FPGAs are now competitive with respect to state-of-the-art processors -thanks to the latest technology breakthroughs, including low latency communication links between FPGAs and CPUs, and the relatively low power consumption of todays FPGAs -moving part of the code from software to hardware (FPGA) still requires a significant effort.

So, in order to deploy a complex application on those execution platforms, developers require an integrated design flow offering joint support of both hardware and software.

Towards that goal, our proposal has 3 main characteristics:

• It starts with a unique and "high-level" formalism to expose parallelism. This formalism allows parallelization and deployment decisions to be taken gradually during the design process, and with as few changes to the source code as possible.

• It provides the means to translate an OpenMP code into an hybrid CPU-FPGA virtual platform that can be validated, HW/SW partitioned and evaluated by software developers.

• It comes with an semi-automatic synthesis and bitstream generation process targeting Xilinx' or Intel's FPGAs. Note that even if the last point may require some manual interventions of hardware engineers, for instance to select appropriate constructs or add appropriate annotations to facilitate or guide the High-Level Synthesis process, we estimate that over 75% of effort can be achieved by software engineers.

II. OVERVIEW OF THE PROPOSED WORKFLOW

A. Overview

The complete workflow is depicted in Figure 1. The input is an OpenMP annotated code in which the developer has identified and annotated the code regions to be parallelized and offloaded. Before entering the process leading to the FPGA implementation (i.e., entering TOAST), the annotated code can be first compiled and functionally tested on devices easier to setup, such as a GPU (e.g., NVidia) or on an acceleration board (e.g., a Xeon Phi accelerator). This is achieved using an OpenMP-aware compiler (e.g., gcc or Clang) supporting the target.

During the first phase of the workflow, the source code is transformed into two components: the host code aimed at being executed on the host, and the target code aimed at being deployed on the accelerator (another general purpose processor or an FPGA-implemented hardware accelerator). Both components interact using services provided by a generic control and communication API. This first phase, implemented by the TOAST tool, is detailed in Section III.

During the second phase, the host code and the target code enter the design exploration process in which candidate solutions -including deployment and target technologies -are successively designed, evaluated, and refined. These evaluation steps are performed on a SystemC virtual platform during the early phases, and on the actual hardware implementation during the late phases. The parts of the application deployed on the CPU (the host) are compiled using a standard toolchain (gcc, Clang, etc.); the parts that are deployed to the FPGA go through High Level Synthesis (HLS). In our case, this phase is implemented by a System Design Environment (SDE) called SpaceStudio from Space Codesign Systems [2] and by FPGA vendors specific toolchains (e.g., Vivado from Xilinx [3], and Quartus Prime from Intel [4]).

B. System Design Environment and FPGA vendors specific toolchains

A System Design Environment facilitates the development and deployment of applications that target heterogeneous systems (CPU and FPGA). Xilinx proposes a SDE called SDSoC2 , but unfortunately it only targets the Xilinx Zync platform. We based our toolchain on Space Codesign's SDE called SpaceStudio [2], which presents the advantage to be platformindependent and allows the system architect to deploy on either Xilinx or Intel platforms.

Figure 2 summarizes the HW/SW codesign flow of SpaceStudio. A system architect creates a set of architectures representing different mappings of the application's components onto a specified platform and specifies the type of communication used between those components.

SpaceStudio supports virtual platform simulation for performance prediction and algorithm validation. It integrates moni-Fig. 3. TOAST Architecture toring and analysis capabilities for non-intrusive performance profiling of both hardware and software. Examples of collected metrics are bus performance (latency and throughput), queue and memory usage, processor load, task scheduling, context switching, as well as timing data. Using the collected information, the system designer can determine which architectures allow the application to exhibit the best performance. Those architectures can then be directly implemented on the target platform as SpaceStudio generates the code and project files for downstream HLS tools to synthesize application-tasks mapped as co-processor. The result of this process can be directly deployed on the target to be tested and to confirm the performance characteristics of the program.

The input of SpaceStudio is a SystemC code partitioned into several logical modules (called "Space Modules") that communicate using a dedicated communication API. Those modules are directly generated from the program source code. OpenMP annotations are used to designate the parts to be offloaded, and to capture the control and data dependencies. This generation process is implemented in the TOAST tool described hereafter.

III. FROM OPENMP TO SYSTEM LEVEL DESIGN WITH TOAST

Offloading directives have been introduced in OpenMP 4.0. They support the deployment of part of a program on one or several devices. A device may be another processor, a GPU, a FPGA coprocessor, etc. This allows to exploit the various forms of hardware-level parallelism using a unique technology and a consistent model of computation and communication, rather than using specialized languages or APIs to target directly these kind of accelerators. Using these offloading annotations, the code running on the main CPU (or host) can move data from its memory to the device's (or target) memory, execute logic on the target device and move data back to the host memory.

TOAST (Tool for OpenMP Annotations to System design Translation) is the bridge between OpenMP and the system level design. It interprets the OpenMP offloading directives (omp target) to generate a functionally equivalent architecture ready to be deployed on one or several device configurations.

The input of TOAST is a source file containing the host code as well as the target regions to offload (i.e., the code that will be ultimately run on the device).

The output of the tool is composed of several source files:

• One for the host, consisting of the input file with the modifications listed in the next section applied to it. • One file for every Space Module generated out of a target directive. Next, for each Space Module device specification, there are two possible refinements:

• The use of an HLS tool to produce a bitstream if the device is an FPGA. In that process, OpenMP constructs still in the device source file (such as parallel regions or tasks constructs) will be discarded. • The use of an appropriate compilation toolchain depending on the device the module is mapped to. For example, a version of gcc to compile code for soft cores such as the MicroBlaze or Nios. Note that TOAST keeps all OpenMP annotations of the initial OpenMP file, except those interpreted during the offloading process implementation. In practice, this means that those annotations can still be processed by the host or the target3 dedicated compilers (for example gcc for the Cortex-A9 or Cortex-A53), as long as they support OpenMP. For instance, if the OpenMP source file contains both offloading annotations (omp target) and loop or task parallelization annotations (i.e., omp parallel for, omp task), the latter may be exploited by the host compilation toolchain to generate multithreaded and multi-core implementations of the host part.

IV. TOAST IMPLEMENTATION DETAILS

TOAST is implemented using the Clang LibTooling framework [START_REF][END_REF]. This framework provides a set of services to access and modify the Abstract Syntax Tree (AST) of a C program.

Figure 3 presents the architecture of TOAST and how it integrates Clang LibTooling by implementing:

• AST Matchers, which are used to find the elements of the AST corresponding to the OpenMP offloading directives • Match Callback Functions, which are used to replace elements of the original source code and create the source files to be deployed on the devices. Figure 4 schematically describes the structure of the generated files for one OpenMP offloading directive (omp target). As shown on this figure, some code parts are simply "translocated" from the input file to the host or target files whereas other, "template code" and "communication code" are generated according to the OpenMP directives.

A. Subset of OpenMP currently covered by TOAST

The current implementation of TOAST supports the following OpenMP directives:

• pragma omp target • pragma omp target data • pragma omp target enter data • pragma omp target exit data • pragma omp target update It also fully supports the map clause that is the core of the OpenMP API to manage communications and avoid unnecessary transfers between the host and device memories.

It is worth noting that a omp target clause does not fork any treatment: it simply offloads some code block to some external device, in order to accelerate its computation. Accordingly, the host thread that initiates this computation is blocked until the computation is complete. Stated differently, the offloaded part is executed synchronously with the host thread. If one wants to parallelize computations, he has to add other clauses such as nowait and depend that allow to decouple the execution of the target region from the host control flow. Those clauses are also supported by TOAST. Their use is illustrated later in subsection V-B.

The following runtime library routines are also implemented:

• omp_target_alloc • omp_target_free • omp_target_is_present They are part of the runtime library and are used by the higher level memory management services that compose the runtime library. They are also available to the user as specified in the OpenMP standard.

B. Runtime library technical details

The runtime library is the part of the implementation that will be linked to the final host binary. As shown in Figure 5, the runtime library has the following roles:

• Manage the device memory • Trigger execution of computations on the device 1) Device Memory Management: Memory allocations on the device are done through the RunTime Library (RTL). Memory can be manually allocated by the user by calling the omp_target_alloc service. It can also be allocated automatically by the RTL when it encounters a target or target data directive that requires memory allocation on the device. The RTL uses three structures to keep track of the state of the device memory:

• Memory page containing the address of the memory page in the device memory, the number of memory blocks used, and whether it is allocated or not. • A hash table holding all references to memory pages created during the lifetime of the program, indexed by their address in memory. • A set of free memory page addresses. The RTL uses two structures to keep track of memory associations between the host and the device as well as the reference count associated with each memory block in the device:

• A hash table holding references to memory pages associated with a host pointer (which is the index). • A hash table holding the reference count of a given host pointer (therefore the reference count of the associated memory on the device).

These structures consume memory on the the host, but they also reduce the number of data copies between the host and the device at runtime. The interconnection between the host and the accelerators being a bottleneck, it is important to limit those copies as much as possible to get the benefits of offloading computations.

This constraint also applies to the choice of the memory used to implement communications. Device memory is allocated in the central SDRAM for it provides faster communications (and, also, larger storage) than the FPGA-located Block RAMs (BRAMs). This way the BRAM is only used for the scratchpad memory of the different accelerators that are generated. The memory transactions within this structure shown in Figure 6 are the following: 1) variables are copied from the Host memory into the Device memory by the Host, following the map clause if specified 2) variables are copied from the Device memory into the scratchpad memory by the accelerator 3) local scratchpad memory is modified by the accelerator execution. 4) variables are copied from the scratchpad memory into the Device memory by the accelerator 5) variables are copied from the Device memory into the Host memory by the Host, following the map clause if specified

2) Trigger Execution: As mentionned previously, the target device can be an FPGA or a CPU (e.g., a softcore). In both cases, the code to run on the device is extracted from the original source code, synthesized (or compiled), and loaded on the FPGA (or CPU) before execution. Note that, contrary to off-line offloading scheme implemented by TOAST, in the gcc implementation, the logic to be executed on the device when the device is a CPU is uploaded to the device at runtime. This scheme is extremely flexible but it can hardly be implemented on a FPGA. In addition, it makes temporal analysis (e.g., Worst-Case Execution Time estimation) much harder to achieve.

A typical OpenMP offloading implementation (such as the one from gcc or clang) can be summarized as follows:

1) The host asks the runtime library to run a target region 2) The runtime library updates the device memory state 3) The runtime library loads the associated binary on the target along with the device memory addresses of all variables accessed during the execution of the offloaded region 4) The runtime library launches the execution of the offloaded region 5) The runtime library updates the host memory state once the offloaded region has finished its execution In our implementation, the RTL does not need a dedicated "trigger device computation" service. Instead, control flow is transferred to/from the device using the SpaceStudio API. Therefore, our offloading implementation can be summarized as follows:

1) The host asks the runtime library to update the device memory state 2) The host gets the addresses of the variables required to execute the offloaded region (from the RTL) 3) The host sends these addresses to the device 4) The host sends the signal to start the device computation 5) The host waits for the signal indicating that the device has finished its execution 6) The host asks the runtime library to update the host memory state according to the device memory state

V. APPLICATION AND EVALUATION

A. Offloading with one accelerator

To validate our approach, we have applied it to the development of a line detection program. The initial program, written in C++, implements a sequence of three steps: filtering, edge detection, and line detection. After profiling this monothreaded program, the filtering step was found to be the most CPU-intensive, so we used TOAST to offload it to the FPGA. The resulting architecture is described in Figure 7. TOAST created the Filtering Space Module and added the communications to the host source code.

The original OpenMP code of the Filtering function is presented in Listing 1. The only difference from the original code is the pragma added on line 3 to offload the included computations. The map clause requires to copy the input Fig. 7. TOAST HW/SW partitioning results applied to a Line Detection example image to the FPGA before execution of the offloaded region. It is not copied back to the host after execution since the image is not changed by the algorithm. This clause also prevents to copy the initial result_array to the device memory, as the value of the result is only set by the device.

The code generated by TOAST for the host and target modules are given in Listing 2 and 3, respectively. The following elements are worth being commented (for an overview of the memory management, please refer to Section IV-B1).

On the host side (Listing 2):

• Lines 9-10: create the mappings to access the input and output images • Lines 11-12: get the addresses of the input and output images • Lines 13-17: send the addresses of the input and output images, and other parameters to the device • Line 19: trigger the processing • Line 20: wait until the processing is complete • Lines 21-22: deallocate the memory mappings used to access the input and output images On the target side (Listing 3):

• Lines 14-18: read the addresses of the input and output images, and other parameters • Lines 19-20: copy the input and output images to the local scratchpad memory • Line 22: wait for the execution trigger [START_REF] Guérard | OpenMP Application Programming Interface Version 4[END_REF]

v o i d l i n e d e t e c t i o n : : c o n v o l u t i o n f i l t e r ( i n t h e i g h t ,

i n t w i d t h , i n t k e r n e l s i z e , u n s i g n e d c h a r * s o u r c e i m a g e , u n s i g n e d c h a r * r e s u l t i m a g e ) {

v o i d f i f o w r i t e ( T * h o s t p t r , i n t d e v i c e n u m ) ; 2 v o i d f i f o r e a d ( T * h o s t p t r , i n t d e v i c e n u m ) ; 3 v o i d map ( T * h o s t p t r , i n t map type , i n t m a p m o d i f i e r

, i n t device num , i n t n b e l e m e n t s , u n s i g n e d l o n g o f f s e t ) ; 4 v o i d end map ( T * h o s t p t r , i n t map type , i n t m a p m o d i f i e r , i n t device num , i n t n b e l e m e n t s , u n s i g n e d l o n g o f f s e t ) ; 5 . . .

7 v o i d l i n e d e t e c t i o n : : c o n v o l u t i o n f i l t e r ( i n t h e i g h t ,

i n t w i d t h , i n t k e r n e l s i z e , u n s i g n e d c h a r * s o u r c e i m a g e , u n s i g n e d c h a r * r e s u l t i m a g e ) { After this phase, the complete design can be simulated, profiled, and evaluated at the functional level using SpaceStudio's own virtual platform. Coupled with OpenMP's flexibility to designate the code parts to be offloaded, this toolchain allows for a fast -hence large -architectural exploration process. Once the best architecture is identified on the basis of profiling figures, it takes around 15 minutes to generate the bitstream and test the complete application in its production environment on the target board.

The focus of this work was to obtain a functional validation of the application on the device. The example application has been successfully deployed on both a Xilinx XC7Z020 (ZedBoard from Digilent) and an Intel Cyclone V 5CSEMA5F31C6N (DE1-SoC from Terasic), both SoCs are fitted with a 667MHz dual-core ARM Cortex-A9 processor and an on-chip programmable logic area. At this phase of the experiment, no low-level optimizations have been applied (i.e., no increase of the clock frequency, no burst or DMA transfers, etc). Furthermore, the filter computation has only been offloaded, not parallelized. So, considering the performance of the host CPU (one dual-core ARM Cortex A9 at 667 MHz), performance increase can only be achieved by a better usage of the FPGA resource. This improvement is investigated in the next section.

B. Offloading to multiple accelerators

The example previously shown does a simple offloading, without parallelization. In order to improve performances, the initial program is slightly tweaked to dispatch the filter work on multiple accelerators, as shown in Listing 4.

This listing shows two target directives (starting line 15 and line 20, respectively), each one covering a call to the same function (sub_filter) but with specific map clauses designating the part of the initial image to be processed by each target. Each clause corresponding to one target, this implementation generates two accelerators, but it could easily 1 # pragma omp d e c l a r e t a r g e t 2 v o i d s u b f i l t e r ( i n t l i n e s t a r t , i n t l i n e e n d , i n t h e i g h t , i n t w i d t h , i n t k e r n e l s i z e , u n s i g n e d c h a r * s o u r c e i m a g e , u n s i g n e d c h a r * r e s u l t i m a g e ) { Using the workflow presented in Figure 1, we have generated variants with 2, 4, 8 and 10 accelerators and used the SpaceStudio environment to estimate the FPGA occupation of each variant and generate its implementation on the target board.

The performance characteristics of the generated variants on the board are presented in Table I. At this stage, we chose to use 8 accelerators as adding more accelerators does not improve the performance (as shown by the data collected). We parallelize the filtering process by dividing the computation of the filter on slices of the image. However, the algorithm needs the preceding and following lines of the current line being processed to produce a result, meaning that, as we increase the number of accelerators computing a slice of Fig. 9. Utilization of the generated FPGA configuration with 8 accelerators the image, the number of overlapping lines that needs to be transferred to several accelerators increases, hence the total number of communications happening between the host and the accelerators. This phenomenon leads to diminishing returns when adding accelerators as they increase the time of communication more than the time gained by having lines processed concurrently on the FPGA. The block representation of the generated design is shown in Figure 8, and its utilization of the target FPGA (ZedBoard) is shown in Figure 9.

Performance figures given in Table I show that at least 8 accelerators are needed to observe an acceleration with respect to the reference implementation. The performance vs. resource ratio is not as high as what would be achieved by manual VHDL or Verilog coding, but the performance vs. development cost is certainly much higher. Indeed, this result is obtained 1) with very few modifications of the source code 2) with very few manual operations, thanks to the automated tool chain, 3) using a high-level formalism (OpenMP) allowing a comprehensive and consistent expression and exploitation of application-level parallelism, 4) using a compilation chain and runtimes (OpenMP compliant compilers) allowing the deployment of the same application on diverse targets (GPU, acceleration boards, or FPGA), 5) with practically no knowledge of HDL programming. Moreover, performances can actually be significantly improved by simply adding HLS pragmas to the source code. For instance, with the addition of two HLS pragmas in our algorithm, we were able to obtain a total execution time of the filter of 16.7 ms, which correspond to a 3.7x speedup.

This example illustrates the feasibility of the workflow presented in Section II. However, this demonstration has been performed on a simple, integer code. Will our workflow be applicable to applications making an extensive use of floating point operations (FPOps)? Indeed, deploying FP-extensive code on a FPGA is very resource demanding. In some cases, it may be necessary to re-code the offloaded part so that it uses fixed-point operations instead of FPOps. In that case, accelerating the application does not simply consists to select the code to be offloaded using OpenMP annotations and to press a button: the offloaded part must be re-coded. If the developer relies on the HLS compiler to handle floating point operations, he must ensure that the computed results are always "identical" to those that would be obtained on the host. Finally, performances gains achieved by offloading FPintensive code may be limited due to the necessity to comply with the operation ordering in the C code in order to ensure identical results [START_REF] Hrica | Floating-PointDesign with Vivado HLS[END_REF].

VI. RELATED WORKS

Several academic works have addressed the problem of translating an OpenMP annotated code to an FPGA implementation. A comprehensive bibliography can be found in [7, Section B]).

In [START_REF] Podobas | Empowering OpenMP with Automatically Generated Hardware[END_REF], Podobas et al propose a solution where an OpenMP code is transformed into custom FPGA hardware units orchestrated by a NiosII softcore. This approach differs from ours for three main reasons: (i) they translate OpenMP tasks (#pragma omp task), whereas we process OpenMP offloading directives (#pragma omp target); (ii) they provide a specific HLS chain that generates "hyper-tasks", whereas we use standard HLS chains provided by FPGA vendors (Xilinx or Intel) in order to leverage on the maturity of these products; (iii) they start HLS from the compiler's intermediate representation (IR) whereas we use a source-tosource transformation in order to maintain a direct traceability from the OpenMP code to the code provided as input to the HLS toolchain.

In [START_REF] Sommer | OpenMP device offloading to FPGA accelerators[END_REF], Sommer et al also process OpenMP target directives, and also uses commercial HLS tools to generate an FPGA implementation. The transformation relies on the ThreadPool-Composer (TPC) API (see [START_REF] Korinth | An Open-Source Tool Flow for the Composition of Reconfigurable Hardware Thread Pool Architectures[END_REF]), later improved in TaPaSCo4 , whereas our workflow relies on the communication API implemented in the SpaceStudio environment. Leveraging the capabilities of SpaceStudio, our workflow allows to evaluate the performance of different deployment solutions starting from a unique OpenMP source code. It also allows to deploy to either Intel or Xilinx platforms.

Finally, in [START_REF] Ceissler | Automatic Offloading of Cluster Accelerators[END_REF], Ceissler et al propose HardCloud5 , which extends OpenMP 4.x with clauses expressing the fact that the annotated software code will be replaced by either a presynthesized hardware implementation (mode 1) or an hardware implementation generated from source code (mode 2). Mode 2 seems to be similar to our solution, but as of the writing of this paper, only the first mode is described and supported.

VII. CONCLUSION

Software developers need appropriate programming paradigms and languages to expose the parallelism of their applications, and exploit efficiently the huge processing capabilities of the recent hardware platforms of the embedded market. OpenMP is a possible solution towards that goal thanks to the large scope of parallelization approaches supported, including the capability to offload parts of a software application to an external processing unit such as a GPU or an FPGA, to its very large user base, and its maturity. In domains where size, weight and power constraints are stringent, FPGA solutions are a promising alternative to general purpose CPUs or GPUs, as long as the transformation from software to hardware (i) does not mean re-coding manually the application in some low-level hardware description language such as VHDL or Verilog, and (ii) does not hinder the capability to explore various implementation solutions. To comply with conditions (i) and (ii), we have implemented a complete workflow based on two main components: TOAST, a new tool that extracts and "encapsulates" the OpenMP target code, and SpaceStudio, that provides Design Space Exploration and platform-independant implementation capabilities. Thanks to the independence of OpenMP with respect to the hardware platform, this solution can be used to deploy the same software first on a multi-core for early verification and functional validation activities, then on non-embeddable hardware accelerators (such as GPUs), and finally on FPGAs. We have presented the application of this workflow on a simple use case.

In the short term, we are completing TOAST to support the complete offloading capabilities of OpenMP and add optimizations to the generated code.

On the long term, several issues remain to be addressed. First, our workflow strongly relies on the capabilities of the HLS toolchain and of the target FPGA. If some significant part of code needs to be modified to be deployed on an FPGA, this means that some design choice must be done very early in the process, i.e., before the coding phase, and this would strongly affect the DSE capabilities of the approach. For instance, an application containing floating point operations may need to be rewritten using fixed point operations before being given to the HLS toolchain. Second, we strongly believe that OpenMP can make its way into the domain of safety critical embedded systems, but this is conditioned by the improvement of OpenMP determinism, which will require the application of specific implementation and usage constraints. Hopefully, several academic works have been carried out towards that goal (see e.g., [START_REF] Vargas | OpenMP and timing predictability: A possible union?[END_REF]).

Fig. 1 .

 1 Fig. 1. From OpenMP to SoC FPGA workflow (TOAST stands for Tool for OpenMP Annotations to System design Translation)

Fig. 4 .

 4 Fig. 4. TOAST Code generation

Fig. 5 .

 5 Fig. 5. Runtime library interaction with the host and the device at runtime

Fig. 6 .

 6 Fig. 6. TOAST Memory structure

2 3 # 5 / 8 }

 358 pragma omp t a r g e t map ( a l w a y s , t o : s o u r c e i m a g e [ 0 : IMAGE SIZE ] ) map ( from : r e s u l t i m a g e [ 0 : IMAGE SIZE ] ) 4 { / c o n v o l u t i o n a c c e s s i n g s o u r c e i m a g e and w r i t i n g r e s u l t s i n r e s u l t i m a g e 6 . . . 7 } Listing 1. Original OpenMP source code • Lines 23-26: do the filtering operation • Lines 27-28: copy the input and output image from the local scratchpad to the main memory • Line 29: signal the end of the computation For this simple example, TOAST generates the Space Module source files in less than a second thanks to the speed of the Clang Libtooling framework. The overhead of the transformation is negligible compared to the rest of the compilation process which takes around 15 seconds to compile the host 1

8 9 d

 9 e v i c e . map ( s o u r c e i m a g e , OMP MAP to , OMP MOD always , DEVICEMEMORY ID, IMAGE SIZE , 0 ) ; 10 d e v i c e . map ( r e s u l t i m a g e , OMP MAP from , OMP MOD none , DEVICEMEMORY ID, IMAGE SIZE , 0 ) ; 11 u n s i g n e d l o n g s o u r c e i m a g e a d d r 0 = d e v i c e . g e t a d d r i n d e v i c e m e m o r y ( s o u r c e i m a g e ) ; 12 u n s i g n e d l o n g r e s u l t i m a g e a d d r 0 = d e v i c e . g e t a d d r i n d e v i c e m e m o r y ( r e s u l t i m a g e ) ; 13 d e v i c e . f i f o w r i t e (& s o u r c e i m a g e a d d r 0 , 0 ) ; 14 d e v i c e . f i f o w r i t e (& r e s u l t i m a g e a d d r 0 , 0 ) ; 15 d e v i c e . f i f o w r i t e (& k e r n e l s i z e , 0 ) ; 16 d e v i c e . f i f o w r i t e (& h e i g h t , 0 ) ; 17 d e v i c e . f i f o w r i t e (& w i d t h , 0 ) ; 18 i n t go 0 ; 19 d e v i c e . f i f o w r i t e (&go 0 , 0 ) ; 20 d e v i c e . f i f o r e a d (&go 0 , 0 ) ; 21 d e v i c e . end map ( s o u r c e i m a g e , OMP MAP to , OMP MOD always , DEVICEMEMORY ID, IMAGE SIZE , 0 ) ; 22 d e v i c e . end map ( r e s u l t i m a g e , OMP MAP from , OMP MOD none , DEVICEMEMORY ID, IMAGE SIZE , 0 ) ; 23 } Listing 2. Host code after TOAST transformation 1 v o i d read from memory ( T * l o c a l p t r , u n s i g n e d l o n g memory address , i n t n b e l e m e n t s , i n t e l e m o f f s e t ) ; 2 v o i d w r i t e t o m e m o r y ( T * l o c a l p t r , u n s i g n e d l o n g memory address , i n t n b e l e m e n t s , i n t e l e m o f f s e i d T a r g e t 0 : : t h r e a d ( v o i d ) { 6 u n s i g n e d c h a r s o u r c e i m a g e [ IMAGE SIZE ] ; 7 u n s i g n e d c h a r r e s u l t i m a g e [ IMAGE SIZE ] ; i g n e d l o n g s o u r c e i m a g e a d d r ; 12 u n s i g n e d l o n g r e s u l t i m a g e a d d r ; 13 w h i l e ( t r u e ) { 14 ModuleRead ( HOST0 ID , SPACE BLOCKING , & s o u r c e i m a g e a d d r ) ; 15 ModuleRead ( HOST0 ID , SPACE BLOCKING , & r e s u l t i m a g e a d d r ) ; 16 ModuleRead ( HOST0 ID , SPACE BLOCKING , & k e r n e l s i z e ) ; 17 ModuleRead ( HOST0 ID , SPACE BLOCKING , &h e i g h t ) ; 18 ModuleRead ( HOST0 ID , SPACE BLOCKING , &w i d t h ) ; 19 read from memory ( s o u r c e i m a g e , s o u r c e i m a g e a d d r , IMAGE SIZE , 0 ) ; 20 read from memory ( r e s u l t i m a g e , r e s u l t i m a g e a d d r , IMAGE SIZE , 0 o n v o l u t i o n a c c e s s i n g s o u r c e i m a g e and w r i t i n g r e s u l t s i n r e s u l t i m a g t e t o m e m o r y ( s o u r c e i m a g e , s o u r c e i m a g e a d d r , IMAGE SIZE , 0 ) ; 28 w r i t e t o m e m o r y ( r e s u l t i m a g e , r e s u l t i m a g e a d d r , IMAGE SIZE , 0 ) ; 29 M o d u l e W r i t e ( HOST0 ID , SPACE BLOCKING , &go ) ; 30 } 31 } Listing 3. Target code after TOAST transformation binary and the SystemC simulation of the hardware modules.

3/ / c o n v o l u t i o n a c c e s s i n g s o u r c e i m a g e and w r i t i n g r e s u l t s i n r e s u l t i m a g 6 # 9 10 # pragma omp p a r a l l e l 11 {

 6911 pragma omp end d e c l a r e t a r g e t 7 8 v o i d l i n e d e t e c t i o n : : c o n v o l u t i o n f i l t e r ( i n t h e i g h t , i n t w i d t h , i n t k e r n e l s i z e , u n s i g n e d c h a r * s o u r c e i m a g e , u n s i g n e d c h a r * r e s u l t i m a g e ) { 12 # pragma omp m a s t e r 13 # pragma omp t a r g e t d a t a map ( a l w a y s , t o : s o u r c e i m a g e [ 0 : IMAGE SIZE ] ) map ( from : r e s u l t i m a g e [ 0 : IMAGE SIZE ] ) 14 { 15 # pragma omp t a r g e t map ( t o : s o u r c e i m a g e [ 0 : SLICE SIZE + OVERLAP SIZE ] ) map ( from : r e s u l t i m a g e [ 0 : SLICE SIZE ] ) n o w a i t 16 { 17 s u b f i l t e r ( 0 , h e i g h t / 2 , h e i g h t , w i d t h , k e r n e l s i z e , s o u r c e i m a g e , r e s u l t i m a g e ) ; 18 } 19 20 # pragma omp t a r g e t map ( t o : s o u r c e i m a g e [ SLICE SIZE -OVERLAP SIZE : SLICE SIZE + 2 * OVERLAP SIZE ] ) map ( from : r e s u l t i m a g e [ SLICE SIZE : SLICE SIZE ] f i l t e r ( h e i g h t / 2 , h e i g h t , h e i g h t , w i d t h , k e r n e l s i z e , s o u r c e i m a g e , r e s u l t i m a g e ) ; 23 } 24 } 25 } 26 } Listing 4. Parallelized OpenMP source code

Fig. 8 .

 8 Fig. 8. Block design of the generated FPGA configuration with 8 accelerators

See www.openmp.org.

See https://www.xilinx.com/sdsoc.html.Fig. 2. SpaceStudio workflow

If the target device is another processor, not a FPGA.

Available at git.esa.informatik.tu-darmstadt.de

See www.hardcloud.org.


Fabien Lauer
email: fabien.lauer@esstin.uhp-nancy.fr

Gérard Bloch
email: gerard.bloch@esstin.uhp-nancy.fr

A new hybrid system identification algorithm with automatic tuning

Keywords: hybrid system, system identification, bounded error, Support Vector Regression

Hybrid system identification is composed of two subproblems: estimate the discrete state or mode for each data point, and estimate the submodel governing the dynamics of the continuous state for each mode. For linear hybrid systems, the paper proposes to tackle these problems in a single step by simultaneously approximating each submodel while associating data points to each of these. The method borrows ideas from bounded-error approaches and Support Vector Regression to extend the algebraic procedure. The algorithm can easily deal with noise by fixing a predefined accuracy threshold. This bound on the error can be different for each mode when the noise level is considered to switch with the system. An extension of the algorithm to automatically tune itself in accordance with the noise level of each mode is also provided. The method can be seen as an an extension of the algebraic approach, but also as an alternative to the bounded error approach when a predefined or preferred model structure is given or when the noise level is unknown. An extension of the method to nonlinear submodels is provided in the companion paper (Lauer and Bloch, 2008).

INTRODUCTION

Context. A hybrid system is usually described by both a continuous state and a discrete state, where the vector field defining the evolution of the continuous state depends on the discrete state. In this framework, a system can be seen as switching between different subsystems, which are usually modeled by linear AutoRegressive with eXogenous inputs (ARX) models in the discrete-time case. Two types of identification problems may arise in this setting depending on whether the discrete state sequence that generated the data is known or not. If it is, then the problem can be simply recast as n common identification problems, each one using only the data for a given discrete state. However, in most cases this sequence is unknown and the problem becomes nontrivial as it amounts to both estimate the regions or the boundaries in the continuous state space (or regressor space) that define the discrete state and the parameters of the linear models in these regions.

Related work. Five main approaches have been devised for this problem: the clustering-based approach [START_REF] Ferrari-Trecate | A clustering technique for the identification of piecewise affine systems[END_REF], the mixed integer programming based approach [START_REF] Roll | Identification of piecewise affine systems via mixed-integer programming[END_REF], the Bayesian approach (Juloski et al., 2005a), the bounded error approach [START_REF] Bemporad | A bounded-error approach to piecewise affine system identification[END_REF] and the algebraic approach [START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF]. The first four focus on the problem of PieceWise Affine (PWA) system identification, where the discrete state depends on the continuous state. However, both the bounded error and Bayesian approaches can also be used to identify a broader class of systems, known as switched linear systems, where the discrete state evolves independently of the continuous state. The algebraic approach (Vi-dal et al., 2003) focuses on this latter problem, but without taking the noise into account in its development. This leads to an algorithm very sensitive to noise, compared to the clustering-based or bounded error methods, as shown by Juloski et al. (2005b). Besides, the bounded error method provides a convenient way of dealing with noisy data by looking for a model with a predefined accuracy. However, the hyperparameters of the method, such as the model accuracy that determines the number of modes, may be difficult to tune to get a prescribed structure, e.g. if prior knowledge on the number of modes is available (Juloski et al., 2005b).

Tools and proposed method. The paper focuses on linear hybrid system identification1 from noisy data with Switched ARX (SARX) models. PieceWise ARX (PWARX) models are considered as a special case of this problem. In this context, the paper proposes a bounded error approach to satisfy the hybrid decoupling constraint when working with noisy data in the algebraic identification framework. The new method uses tools and ideas from the fields of machine learning and optimization. In machine learning, Support Vector Machines (SVM) [START_REF] Vapnik | The nature of statistical learning theory[END_REF] can be used both for regression and system identification [START_REF] Drezet | Support vector machines for system identification[END_REF]Mattera and Haykin, 1999). In hybrid system identification, SVM classifiers are already used to estimate the switching boundaries between the modes [START_REF] Ferrari-Trecate | A clustering technique for the identification of piecewise affine systems[END_REF][START_REF] Bemporad | A bounded-error approach to piecewise affine system identification[END_REF]. For regression, this learning algorithm, known as Support Vector Regression (SVR), uses an ε-insensitive loss function which does not take into account errors that are less than ε [START_REF] Smola | A tutorial on support vector regression[END_REF]. This loss function allowing for errors below a predefined threshold is close in spirit to the bounded error approach. However, the origin is different. In learning theory, this effect is justified in order to minimize the generalization error of the model, whereas the bounded error approach was developed to allow the automatic determination of the number of linear submodels required to approximate a nonlinear function with a given accuracy.

Contribution. The paper proposes a new method for linear hybrid system identification from noisy data. This method allows to consider a noise model that also switches with the system by choosing different bounds on the error for different modes. To our knowledge, this problem has not yet been explored in the literature, though being realistic (most sensors have a constant relative precision rather than a constant absolute one). An extension of the algorithm to automatically tune itself in accordance with the noise level of each mode is also provided. In comparison to the the bounded error method [START_REF] Bemporad | A bounded-error approach to piecewise affine system identification[END_REF], which determines the number of modes for a fixed bound on the error, this alternative approach to the tuning of parameters may be useful when a predefined or preferred model structure is given. In this case, instead of testing various thresholds on the accuracy until a good model structure is found, a minimal bound on the error can be automatically determined for a given number of modes.

Paper organization. Starting from the setting of the problem in the algebraic framework (sect. 2.1), the paper then describes how to deal with noise in a bounded error approach (sect. 2.2). Then, the bounded error with soft constraints is discussed with the use of the ε-insensitive loss function (sect. 2.3) before exposing the algorithm itself (sect. 2.4). This alorithm is then extended to automatically tune the bounds on the error (sect. 2.5). Finally, two numerical examples are given (sect. 3) to show both the automatic tuning and the application to hybrid system identification.

Notations: all vectors are column vectors written in boldface and lowercase letters whereas matrices are written in boldface and uppercase.

HYBRID SYSTEM IDENTIFICATION

Consider modeling a linear hybrid system of output y i from N input-output samples (x i , y i ) by a model f ,

y i = f (x i ) + e i = f λi (x i ) + e i , (1)
composed of n ARX affine2 submodels f j of the form

f j (x i ) = w T j x i + b j , (2)
where w j ∈ R p and b j ∈ R are the p + 1 parameters, the regression vector

x i = [y i-1 . . . y i-na , u i-1 . . . u i-nc ] T
contains the delayed n a outputs y i-k and n c inputs u i-k of the system, while the discrete state λ i ∈ {1, 2, . . . , n} determines which mode (or which ARX submodel) is used to compute f (x i ). In a Switched ARX (SARX) model, the discrete state λ i evolves independently of x i , whereas in a PieceWise ARX (PWARX) model, the discrete state is a function of x i . This function is defined as

λ i = j, if x i ∈ S j = {x : H j x i 1 ≤ 0}, j = 1, . . . , n,
(3) in which the matrices H j define the regions S j partitioning the regressor space X ⊆ R (na+nc) .

2.1 Noiseless case: the algebraic approach [START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF] proposed an algebraic approach to simultaneously estimate the discrete and the continuous parts of a SARX model. It basically amounts to consider that the vector z i = [x T i , -y i ] T lies at least on one of the hyperplanes defined by3 [w T j 1]z i + b j = 0, i.e. that the product, n j=1 [w T j 1]z i + b j , of these terms, known as the hybrid "decoupling" polynomial, equals zero. The solution is then obtained by writing this constraint for all the N available data points (x i , y i ) and developing the polynomials to recover a linear system of equations involving new parameters h j built from products of the original parameters w j , b j . This method can be seen as forcing at least one submodel f j to approximate the point (x i , y i ) with zero error. Defining the submodel errors e ij = y if j (x i ) = y iw T j x ib j , and imposing this condition for the N points allows to write the hybrid "decoupling" polynomial constraints as

n j=1 e ij = 0, i = 1, . . . , N. (4)
However, in the case of noisy data, these constraints cannot be satisfied. In practice, [START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF] proposes to solve the linear system involving the products h j of the parameters in a least squares sense to approximate the solution. As detailed by [START_REF] Ma | Identification of deterministic switched ARX systems via identification of algebraic varieties[END_REF], this corresponds to the minimization of a sub-optimal approximation, suitable for a low noise level, of the objective function

N i=1 e 2 i : min hj N i=1 n j=1 (e ij ) 2 . ( 5
)
One drawback of this method is that the original parameters w j and b j are estimated through their products and not directly, which may lead to additional errors on their estimates.

Considering noise with a bounded error approach

The bounded error approach developed by [START_REF] Bemporad | A bounded-error approach to piecewise affine system identification[END_REF] aims at finding the minimal number n of submodels that allows the error e i on all the training points (x i , y i ) to be bounded by

|y i -f (x i )| = |e i | ≤ δ, i = 1, . . . , N. (6)
Considering this approach in the setting of section 2.1 results in rewriting the "decoupling" polynomials (4) as

n j=1 [|e ij | ≥ δ] = 0, i = 1, . . . , N, (7)
where [•] = 1, if the bracketed expression is true, and 0 otherwise. If the discrete state is estimated by λi = arg min j∈{1,...,n}

|e ij |, (8)
then the absolute value of the error of the hybrid model, |e i | = min j |e ij |, is bounded by the threshold δ, for all i for which constraint (7) holds. However, the problem thus posed is not easy to solve. The following proposes a relaxation of the bounded error constraint through the use of a particular loss function.

Bounded error with soft constraints

The ε-insensitive loss function, defined by [START_REF] Vapnik | The nature of statistical learning theory[END_REF] for Support Vector Regression (SVR) as

l(e ij ) = 0 if |e ij | ≤ ε, |e ij | -ε otherwise, (9)
builds a tube of insensitivity, in which the errors are meaningless. Absolute errors larger than the width of the tube ε are penalized linearly, which ensures a certain robustness to outliers compared to a quadratic loss function.

The bounded error constraints (7) can thus be approximated efficiently by the minimization of this loss function.

In this setting, the problem becomes

min wj ,bj N i=1 n j=1 l(e ij ). (10)
Remark 1: Compared to the approach of [START_REF] Bemporad | A bounded-error approach to piecewise affine system identification[END_REF], solving (10) does not ensure that the error is truly bounded for all points. However, this softening of the constraints can be desirable to deal with outliers.

Remark 2: Compared to the approach of [START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF], the objective function in ( 10) is minimized directly with respect to the model parameters w j and b j instead of their products. This may prevent additional errors on the parameter estimates.

An issue that has not been studied in the literature so far is the identification of hybrid systems under the assumption of a switching noise model. This framework extends the standard models in order to consider that the different submodels are corrupted by noise of different levels and or distributions.

An advantage of the proposed approach is the possibility to deal easily with a different noise level for each mode by using different bounds on the errors. Simply define n loss functions l j as

l j (e ij ) = 0 if |e ij | ≤ ε j , |e ij | -ε j otherwise, ( 11
)
where ε j can be set to different values for each j. Then these loss functions can be used in (10) to accomodate each mode. An example of application where this is useful is provided in section 3.

Algorithm

The minimization of the ε-insensitive loss function ( 9) can be implemented through the minimization of n × N positive slack variables ξ ij and n × N soft constraints of the type

-ξ ij -ε ≤ y i -f j (x i ) ≤ ε + ξ ij , (12) j = 1, . . . , n, i = 1, . . . , N,
where ξ ij ≥ 0. To deal with the switching noise variance assumption, multiple loss functions (11) with different thresholds ε set to δ j , j = 1, . . . , n, are implemented via the set of constraints

-ξ ij -δ j ≤ y i -w T j x i -b j ≤ δ j + ξ ij , (13)
j = 1, . . . , n, i = 1, . . . , N, where the submodels f j have been replaced by (2).

In addition, by following the SVR approach, the submodels f j are trained by minimizing the norms of the parameter vectors w j 2 . Minimizing these norms, which are also measures of the model complexity, is known to yield models with better generalization performance [START_REF] Smola | A tutorial on support vector regression[END_REF]. The problem of training n models under the decoupling constraints with bounded error ( 7) is thus approximated by the optimization program involving n(p+ 1 + N ) variables:

min wj ,bj ,ξij ≥0 n j=1 w j 2 2 + C N i=1 n j=1 ξ ij (14) -ξ ij -δ j ≤ y i -w T j x i -b j ≤ δ j + ξ ij , j = 1, . . . , n, i = 1, . . . , N.
Solving this problem with a sufficiently large constant C leads to solution functions f j in accordance with the original constraints (7). Moreover, the discrete state λ i is readily available for all i from the variables ξ ij vanishing to zero as λi = j, for ξ ij = 0, i.e. for the model f j approximating (x i , y i ) with an error less than δ. The cases where the bounded error constraint is not satisfied, i.e. no ξ ij is zero, can be further discriminated by letting λi = arg min j (ξ ij ).

In the case of PWA systems where the modes are linearly separable in the regressor space X , undetermined points can be reclassified after the training of separating hyperplanes (the boundaries between the domains S j ) based on the determined cases only. The classification issue is not discussed here due to size constraints and the reader is referred to [START_REF] Vapnik | The nature of statistical learning theory[END_REF] and [START_REF] Mangasarian | Generalized support vector machines[END_REF] for an introduction to state-of-the-art methods.

The hyperparameters of the method are the number n of modes, the bounds δ j , the regularization parameter C and the number of lagged inputs and outputs (dynamic order). They can be tuned on a subset of the data put aside for validation. When too few data are available, crossvalidation techniques can be used. Automatic tuning of the bounds δ j is discussed in the following.

Automatic tuning

Using the ν-Support Vector Regression (ν-SVR) formulation described in [START_REF] Schölkopf | New support vector algorithms[END_REF], one can tune automatically the width ε of an ε-insensitive loss function. Applying this trick to the algorithm ( 14) leads to min wj ,bj,ξij ≥0,δj≥0

n j=1 w j 2 2 + C N i=1 n j=1 ξ ij + νN C n j=1 δ 2 j (15) -ξ ij -δ j ≤ y i -w T j x i -b j ≤ δ j + ξ ij , j = 1, . . . , n, i = 1, . . . , N.
Notice that, in comparison to [START_REF] Schölkopf | New support vector algorithms[END_REF], actually the squares of the δ j are minimized instead of the δ j directly. Minimizing the δ j directly would produce a shrinkage effect due a constant influence function equal to one. This is not desirable when dealing with noisy data, since the method relies on the fact that some ξ ij , which satisfy ξ ij ≥ max(0, |e ij |δ j ), are zeros and thus that e ij ≤ δ j for a certain number of points. On the contrary, in the minimization of a quadratic criterion, the influence function is known to decrease around zero, which leads to non-zero solutions for the δ j .

As one hyperparameter ν has been added, the n hyperparameters δ j are now automatically tuned. The optimization program (15) thus involves n(p + 2 + N ) variables. This algorithm can be further improved by considering adaptive δ j as above but bounded by δ, simply by introducing the constraint δ ≥ δ j , for j = 1, . . . , n, in (15). Doing so, we impose a bound δ on the error as in the standard approach [START_REF] Bemporad | A bounded-error approach to piecewise affine system identification[END_REF], but also allow the algorithm to shrink this bound in order to produce better solutions.

Optimization issues

Problems ( 14) and ( 15) are nonlinear optimization programs involving respectively n(p + 1 + N ) and n(p + 2 + N ) variables, which may become a difficulty for a large number of data N . However, the proposed method benefits from the good properties of Support Vector Regression and is thus well adapted for the cases where few data are available. Problems minimizing a nonlinear objective function over a convex set, such as ( 14) and ( 15), can be solved by general purpose solvers such as the function fmincon found in MATLAB, but with no guarantee that the solution is a global minimum. The non-convexity of the objective functions is due to the product terms n j=1 ξ ij , which have however a global minimum equal to zero (due to ξ ij ≥ 0). For values of δ j so that the bounded error constraints can be satisfied, this optimum is feasible. Local optimization algorithms, such as sequential quadratic programming, are thus expected to converge towards a global minimum and can be used to solve the problems.

In practice, it has been observed that the optimization rarely leads to a local minimum corresponding to a bad solution of the initial system identification problem. Moreover, such bad solutions are easily detected, in which case the optimization can be restarted from another initial point and with a smaller tolerance on the termination criteria. For instance, in the algorithm 1, used in the experiments of section 3.1, bad solutions are detected from the resulting maximum absolute error, MAE = max i∈{1,...,N } |y if (x i )|. The optimization is restarted with a smaller tolerance Tol, used for the three termination tolerances (change in the variables, change in the objective function and constraint violation), until the MAE is lower than the maximal error allowed and specified by δ. However, when this overall bound is too small compared to the noise level, this condition cannot be satisfied and the algorithm is stopped when Tol reaches a predefined minimal value m.

Algorithm 1. Computing a solution to problem (15) that is acceptable with respect to the maximal absolute error (MAE).

(1) Initialize Tol and its minimal value m (2) Choose a random initial vector of n × (p + N + 2) variables with values in the interval [0, 1] (3) Call fmincon to solve (15) (4) If MAE > δ,

• if Tol > m,

• Tol ← 0.1×Tol

• go to step 2 • else

• output a warning "No solution with MAE < δ can be found, maybe the bound δ is too tight for this data set"

EXAMPLES

Two examples are provided to show the efficiency of the method both for the automatic tuning of the bounds while estimating two synthetic functions and for hybrid system identification.

Switching noise variance and automatic tuning

The first example shows the approximation of a onedimensional PWA map y = a 1 x + b 1 , for x < -2, and y = a 2 x + b 2 otherwise. It also emphasizes the need for different bounds on the errors for the different modes, in case of a switching noise model, and demonstrates the efficiency of the automatic tuning of these bounds.

30 points in the interval -5 ≤ x < -2 are generated for a 1 = 1 and b 1 = 0. In the first set of experiments, β 1 and β 2 are set to 0.8 and 0.2 respectively. All optimization programs are solved by the MATLAB function fmincon for C = 40. Figure 1 shows the approximation of the N = 71 data by algorithm ( 14) for δ 1 = δ 2 = 0.6 (top). When using the same bound on the error for the two models, the data are correctly approximated within the bounds, but the bound is clearly too large for the data corrupted by low level noise, leading to â2 = -0.34 and b2 = -0.14. In this case, using different bounds for each model, in accordance with the noise levels, may lead to a better approximation.

Algorithm ( 15) is then used with an overall bound δ = 1 and ν = 1 to estimate the linear models under the switching noise assumption. As shown at the bottom of Figure 1, this leads to a better fit for x ≥ 2 with â2 = -0.49 and b2 = -0.01, while the final bounds on the errors estimated in accordance with the noise levels are δ 1 = 0.54 and δ 2 = 0.18. As a comparison, a manual

-5 -4 -3 -2 -1 0 1 2 -5 -4 -3 -2 -1 0 1 2 3 -5 -4 -3 -2 -1 0 1 2 -6 -5 -4 -3 -2 -1 0 1 2 3
Fig. 1. Simultaneous estimation of 2 linear functions with different noise levels. Top: using the same bound on the error for the 2 models, the bound is clearly too large for x ≥ -2. Bottom: automatic tuning of the bounds leads to a better fit.

grid search of the optimal parameters δ 1 and δ 2 over 10 values in the range [0.1, 1.0] (requiring 100 runs of the algorithm) leads to values close to these: δ 1 = 0.6 and δ 2 = 0.2. Table 1 summarizes the results with respect to the parameter estimates and the Mean Square Error (MSE) given by

M SE = 1/N N i=1 (y i -f (x i )) 2 .
The results for the automatic tuning are identical in terms of MSE to the ones obtained by a manual grid search of the optimal values of δ 1 and δ 2 . The parameter estimated in these two settings are very close. For the three settings (fixed, manual and automatic tuning), a bias can be observed for the parameter b 1 , due to a high noise level β 1 = 0.8 and a low number of data (30 points generated with the parameters a 1 and b 1 ).

The automatic tuning is now tested with respect to the variation of the noise level. The noise level for x < -2 is set to β 1 = 0.5, while the one for x ≥ 2 varies from β 2 = 0.1 to β 2 = 1. Figure 2 shows the mean and standard deviations over 100 runs of the the estimated parameters. During the experiments, δ 1 and δ 2 given by the algorithm (15) evolve in accordance with the noise levels β 1 and β 2 . Thanks to this automatic tuning, the expectation of the parameter estimates is mostly insensitive to the noise level, while their standard deviations increases only slightly for high levels of noise.

Simulated hybrid system identification

Consider the hybrid system switching between mode 1: y t = y t-1 + u t-1 + e t , and mode 2: y t = -0.905y t-1 + 0.048u t-1 + e t , where e t is a zero-mean Gaussian noise of standard deviation 0.1. An output trajectory of 100 points of this system is generated with a random initial condition y 0 , a random input sequence u t ∼ N (0, 1) and random mode switches. The MATLAB function fmincon is then used to compute the solution of problem ( 14) for C = 100 and δ 1 = δ 2 = 0.1. The trajectory of the resulting model ŷt = f λt (ŷ t-1 , u t-1 ) is shown on Figure 3. The two estimated submodels are f 1 (ŷ t-1 , u t-1 ) = 0.989ŷ t-1 + 1.02u t-1 and f 2 (ŷ t-1 , u t-1 ) = -0.893ŷ t-1 + 0.043u t-1 , which shows the recovering of the original parameters. The discrete state is estimated by λt = arg min j (ξ tj ). As shown in Fig. 3, the algorithm recovers the true mode without requiring a settling time and only 5 classification errors occur on the whole trajectory. Moreover, the effect of these classification errors is limited and their origin can

  5 and are corrupted by a uniform noise in the interval [-β 1 , β 1 ]. 41 points in the interval -2 ≤ x ≤ 2 are generated for a 2 = -0.5 and b 2 = 0 and are corrupted by uniform noise in the interval [-β 2 , β 2 ].

Fig. 2 .

 2 Fig. 2. Average performance of the automatic tuning with respect to the noise level over 100 runs. Expectation of the estimated parameters a 1 , b 1 (top) and a 2 , b 2 (bottom) with their standard deviations versus the noise level β 2 . The true parameters are also represented (dash lines).

Table 1 .

 1 Parameter estimates and Mean Square Error (MSE) for example 1 of section 3.1 and figure 1.

						a 1		b 1	a 2	b 2		MSE
		true parameters		1		0.5	-0.5	0		0.073
		same bounds		0.83	-0.24	-0.34 -0.14	0.138
		(δ 1 = δ 2 = 0.6)
		automatic tuning	0.91	0.04	-0.49 -0.01	0.108
		(δ 1 = 0.54, δ 2 = 0.18)
		manual search		0.92	0.10	-0.51 -0.02	0.108
		(δ 1 = 0.6, δ 2 = 0.1)
	1
	0.5
	0
	-0.5
		0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
	0.2
	0
	-0.2
	-0.4
	-0.6
	-0.8	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1

Nonlinear hybrid system identification is discussed in the companion paper(Lauer and Bloch

, 2008).

Affine models are more general than linear ones and allow the piecewise function f to be continuous in PWARX models.

[START_REF] Vidal | An algebraic geometric approach to the identification of a class of linear hybrid systems[END_REF], only linear submodels without the term b j are considered.

be explained. They occur on ambiguous points for which

In case of a PWA system, these ambiguities could be removed by classifying the points with respect to a separating boundary in the regressor space.

CONCLUSION

In this paper, a new method for hybrid system identification has been proposed to bridge the gap between the bounded error approach and the algebraic procedure.

The method makes use of the ε-insensitive loss function proposed in the machine learning community for Support Vector Regression. Since no assumption on the discrete sequence that generates the data is required, arbitrarily switched ARX (SARX) as well as piecewise ARX (PWARX) models can be identified. Compared to the bounded error approach [START_REF] Bemporad | A bounded-error approach to piecewise affine system identification[END_REF], the resulting algorithm can deal with switching noise level and automatically tune the error bounds accordingly. It thus offers an alternative, which may be useful when a predefined or preferred model structure is given. Based on support vector regression, the proposed method is also very efficient when few data are available for identification.

Future work will focus on missing topics such as subsytems with different orders, estimation of the number of modes, more experiments including real-life applications, incorporation of prior knowledge and in-depth study of the optimization problems. Besides, extension of the proposed method to nonlinear submodels has been studied by Lauer and Bloch (2008).


Yann Saint-Georges

Patrice Hamel

Claire Lemaire

Geneviève Dujardin

Role of positively charged transmembrane segments in the insertion and assembly of mitochondrial innermembrane proteins

, EMBO J., 20, 1281-1288) recently have proposed that Oxa1p could act as part of a general membrane insertion machinery for mitochondrial respiratory complex subunits. We have previously shown that mutations in the TM domain of Cyt1p can partially compensate for the absence of Oxa1p. Here, we demonstrate that a single amino acid substitution in the TM domain of Qcr9p can bypass Oxa1p in yeast. Qcr9p and Cyt1p are two subunits of the respiratory complex bc1 and their relative roles in the assembly of other respiratory complexes have been investigated. The mutations we have isolated in Cyt1p or Qcr9p introduce positively charged amino acids, and we show that the mutant TM domain of Cyt1p mediates the restoration of complex assembly. We propose that the positive charges introduced in Cyt1p and Qcr9p TM domains promote interactions with negatively charged TM domains of other respiratory complex subunits, allowing the coinsertion of both domains into the membrane, in the absence of Oxa1p. This model argues in favor of a role of Oxa1p in the insertion and the lateral exit of less hydrophobic TM domains from the translocation site into the lipid bilayer.

The biogenesis of membrane oligomeric complexes is an intricate process that requires the membrane targeting of subunits, their insertion into the lipid bilayer, folding with cofactors, and the assembly into a functional structure. Numerous studies in bacterial or eukaryotic cells have demonstrated that most membrane proteins insert at the translocon site and that this process is driven by hydrophobic transmembrane (TM) domains (1,2). However, very little is known about the lateral exit of TM domains from the site of insertion into the lipid bilayer and about the mechanistic details of subunit assembly into functional complexes. The mitochondrial respiratory chain enzymes are complexes composed of numerous nonidentical subunits (Fig. (Fig. 1).1). Their biogenesis requires the participation of nucleus-encoded factors that are not intrinsic components of the complexes and are imported into mitochondria by using a sophisticated translocation machinery (3)(4)(5). Most of these proteins are conserved through evolution and it has been shown that mutations in the genes encoding subunits of the respiratory complexes or assembly assisting proteins are the direct cause of several human neurodegenerative pathologies (ref. 6, for review)

Schematic representation of the mitochondrial respiratory chain. Four respiratory complexes are embedded within the inner membrane of mitochondria: the complex I, III or the bc1 complex, IV or the cytochrome c oxidase complex (Cox) and the insoluble part of complex V or ATP synthase. c represents cytochrome c. bc1 and Cox complexes each contain about 10 subunits. Cyt1p and Qcr9p are nucleus-encoded subunits of bc1 complex and have one TM domain each. Cox2p is a mitochondria encoded subunit of Cox complex with two TM domains. The small arrows indicate the electron (e) flow.

Oxa1p, a membrane protein conserved from bacteria to eukaryotic organelles, is a key component of the insertion machinery of membrane proteins. The Escherichia coli homologue YidC interacts with the Sec translocase and mediates the insertion of a subset of proteins into the bacterial membrane (7,8). In yeast mitochondria, the absence of Oxa1p leads to a complete loss of respiration associated with severe defects in the insertion and assembly of subunits of the Cox and ATPase complexes and with minor defects in the assembly of the bc1 complex (9)(10)(11). The translocation and maturation of the Cox subunit, Cox2p, is almost completely blocked (12,13) and several other membrane subunits are degraded (14). Oxa1p interacts with nascent mitochondrial polypeptides and it has been proposed that it could act as part of a general membrane insertion machinery (15). Oxa1p is functionally conserved in fission yeast, human and plant mitochondria (16)(17)(18) and in chloroplasts, its homologue Alb3 plays a role in the insertion of the light harvesting chlorophyll-binding proteins into the thylakoid (19,20).

The functional conservation of Oxa1p through evolution suggests a crucial role in the mechanism of protein insertion into the membrane, but its precise function remains poorly understood. Interestingly, we found that its absence in yeast mitochondria can be partially compensated for by different mutations. First, ATP synthase assembly and activity is fully restored in a strain lacking the mitochondrial protease Yme1p (14). Second, we have isolated several suppressor mutations in the TM domain of cytochrome c1 (Cyt1p), an electron carrier of the respiratory complex bc1 (21). These mutations partially restore the Cox and ATP synthase assembly independently of the electron transfer activity of cytochrome c1, showing that the function of Cyt1p revealed by the suppressor mutations is quite distinct from its welldefined role as an electron carrier.

In this study, we discovered that a single mutation introducing a positive charge in the TM domain of Qcr9p can also partially restore the insertion and assembly of Cox and ATP synthase in the absence of Oxa1p. Qcr9p is a bc1 complex subunit and the relative roles of Qcr9p and Cyt1p in the assembly of other respiratory complexes have been investigated. Although Qcr9p appears dispensable, we found that cytochrome c1 is essential for Cox assembly and that its TM domain is essential for the suppression activity. We propose that the presence of a positive charge in the TM domain of Qcr9p or Cyt1p promotes interactions with a negatively charged TM domain of other respiratory complex subunit, allowing the coinsertion of these two TM domains into the lipid bilayer even in absence of Oxa1p. This model argues in favor of a role for Oxa1p in the lateral exit of less hydrophobic TM domains, e.g., negatively charged TM domains, from their site of translocation within the membrane.

MATERIALS AND METHODS

Strains, Media, Genetic Methods, and Plasmids.

All of the strains had the same nuclear background ade2-1 ura3-1 his3-11,-15 trp1-1 leu2-3, -112 can1-100. Yeast media, genetic methods, and the strains CW30, NBT2, and R101 were described in ref. 21. Ethanol/glycerol medium used was 1% yeast extract, 1% casamino acids, 0.05 M sodium potassium phosphate (pH 6.25), 3% ethanol, and 3% glycerol. YEpNB33 is a multicopy vector and pFL61 is a multicopy yeast expression vector; both carry the URA3 gene (21). The double or triple mutant strains were constructed either by transformations or genetic crosses between the various single mutants. Strain PHT28 was constructed by transforming R102 (see below) with a BstEII/KpnI fragment carrying the OXA1 gene and selecting for respiratory competent and uracil prototroph transformants.

Isolation and Cloning of Suppressor Mutations.

Genetic suppressors were isolated after UV mutagenesis of the oxa1∷LEU2 (NBT2) and oxa1∷URA3 (NBT3) strains (21). Molecular genetics enabled us to map seven of the suppressor mutations to the CYT1 gene and four to a distinct locus. To clone this gene, a genomic library was constructed from the suppressor strain R102. CsCl-purified nuclear DNA was partially digested with HinDIII and ligated with the HinDIII-digested YEpNB33. The ligated DNA was used to transform electrocompetent Escherichia coli cells to ampicillin and kanamycin resistance. About 380,000 independent transformants were recovered. The library DNA was CsCl-purified and used to transform the NBT2 strain. Of 400,000 uracil prototroph transformants, 21 were respiratory competent. Plasmids were isolated from these transformants and the inserts were characterized.

Inactivation of the QCR9 Gene: Cloning of the QCR9 cDNA.

For QCR9 inactivations, the NsiI-PstI fragment of QCR9 was replaced by a 1.5-kb NsiI fragment carrying the URA3 gene, or the PCR-amplified G418 R cassette (22) was cloned at the Klenow-filled NsiI site. The two constructions were used to transform the wild-type strain CW30 to give YST1 (qcr9∷URA3) and PHT21 (qcr9∷G418 R ). Plasmid YEpYS3 carries the QCR9 cDNA that was cloned by complementing the PHT21 strain with a yeast cDNA library constructed in pFL61.

Epitope Tagging of Qcr9p.

We have tagged Qcr9p at its C terminus with 13 c-myc epitopes by using the HIS5 marker gene as described (23). DNA was amplified and used to transform to histidine prototrophy two yeast strains CW30 and PHT28 carrying the QCR9 or the QCR9-1 allele, respectively. Strains YS18-5A, YS16-1B expressing the wild type, or mutant tagged Qcr9p are respiratory competent, showing that the tagged proteins are functional.

Construction of a Short Form of Cyt1p.

YEpPH225 and YEpYS7 are pFL61-based plasmids expressing either the wild-type CYT1 or the CYT1-1 cDNAs. First, a 450-bp AatII/AvaI internal fragment was deleted from YEpPH225 and YEpYS7. Then, PvuII-Acc65I-digested plasmids were Klenow-treated and self-ligated to give YEpYS12 and YEpYS9. These plasmids enable the expression of a short form of pre-Cyt1p protein in which the central hydrophilic region of Cyt1p (175 aa) is deleted whereas the first 63 aa are fused in-frame to the last 71 aa (see Fig.

Isolation of Mitochondria, Carbonate Extraction, and Respiratory Chain Activities.

Mitochondria were purified from cells grown in complete or minimal galactose medium and carbonate extractions were performed as in ref.

Electrophoresis and Immunoblotting.

They were performed as described (14). The anti-yeast Cox2p was purchased from Molecular Probes whereas the anti-Atp2p, anti-Atp4p, and anti-c-myc were generous gifts from J. Velours (Institut de Biochimie et Génétique Cellulaire, Bordeaux, France) and J. M. Galan (Institut J. Monod, Paris), respectively.

RESULTS

A Single Amino Acid Substitution Introducing a Positive Charge in the TM Domain of Qcr9p Partially Compensates for the Absence of Oxa1p.

Yeast is a facultative aerobe organism that can derive energy from fermentation. Yeast cells carrying an inactivated Δoxa1 gene are thus viable but respiratory deficient. In consequence, they grow on a fermentable substrate such as glucose but are unable to grow on a nonfermentable medium containing ethanol or glycerol as respiratory substrate. In the search for partners of Oxa1p, we have isolated genetic suppressors that restore the respiratory growth of cells in the absence of Oxa1p (Fig. (Fig. 22A and Materials and Methods). Among 11 independent dominant nuclear suppressor mutations, seven mapped to the CYT1 gene ( 21) and four to another gene. To identify this second gene, we constructed a genomic library from the strain R102 and used it to transform the Δoxa1 mutant. All of the respiratory-competent transformants recovered and harbored the QCR9 gene that encodes a noncatalytic subunit of the bc1 complex required for electron transfer activity (26,27). We have shown that all four independent suppressors carry the same single nucleotide substitution (GGT>CGT:QCR9-1) at codon 23 of the QCR9 ORF, replacing a glycine residue by an arginine. Qcr9p is a small protein composed of 65 aa with a short C-terminal domain located in the intermembrane space and a TM domain where the G23K suppressor is located. As a control, we showed that overexpression of the wild-type QCR9 gene does not compensate for the absence of Oxa1p, demonstrating that the mutation is required for the suppression (data not shown).

Figure 2 The QCR9-1 mutation partially compensates for the respiratory defect caused by the absence of Oxa1p. WT (CW30); Δoxa1 (NBT2); Δoxa1 CYT1-1 (R101); Δoxa1 QCR9-1 (R102). See Materials and Methods and Hamel et al. (21). (A) Strains were grown on glucose (G) and ethanol/glycerol (E) media (see Materials and Methods) and incubated for 7 days at 28°C. (B) The mitochondrial translation products were 35 S-labeled in vivo in the presence of cycloheximide as described (28). The proteins were separated on 16% SDS-polyacrylamide gels. Arrowheads indicate apocytochrome b (Cytbp) of bc1 complex, pre-Cox2p, and mature Cox2p of cytochrome c oxidase. (C) Mitochondria were purified from cells grown on complete galactose medium as described in Materials and Methods. One hundred micrograms of purified mitochondrial proteins was separated on 12% SDS-polyacrylamide gels, and the accumulation of Cox2p, Atp4p, and Atp2p subunits was analyzed with specific antibodies by Western blotting. Atp2p is used as an internal control as we have previously shown that the accumulation of Atp2p does not depend on Oxa1p (14).

In the absence of Oxa1p, the translocation and maturation of Cox2p is blocked, the assembly of Cox and ATP synthase is impaired, and several membrane subunits undergo degradation. As shown in Fig. Fig. 22 B andC, the QCR9-1 mutation partially restores Cox2p maturation and the accumulation of membrane subunits such as Cox2p and Atp4p. Twenty percent of the wild-type Cox activity is recovered, and the ATPase oligomycin-sensitive activity is fully restored (data not shown). These results indicate that the single glycine to arginine substitution in the TM domain of the bc1 complex subunit Qcr9p partially alleviates the respiratory complex assembly defects caused by the absence of Oxa1p. Interestingly, Qcr9p and Cyt1p are two subunits of the bc1 complex and the QCR9-1 (G23>K) mutation, like the CYT1-1 (L216>K) and CYT1-2 (L219>K) mutations, also introduce a positively charged amino acid within the TM domain of the protein.

Interactions Between the TM Domains of Cyt1p and Qcr9p in the Presence of Oxa1p.

According to the crystal structure of beef and Saccharomyces cerevisiae bc1 complexes (29)(30), the two TM domains of Cyt1p and Qcr9p are in close proximity. Thus, we have investigated whether functional interactions between the two TM domains could exist and their possible implication in respiratory complex assembly. We have compared the effects of each single mutation CYT1-1 or QCR9-1 and the combination of both mutations on the biogenesis of the bc1, Cox, and ATPase complexes. Although both single mutants show substantial respiratory growth, the respiratory growth of the double mutant is strongly impaired (Fig. (Fig. 33A): its duplication time is about 12 h as compared with 2.5 h for the wild type (data not shown). As shown by cytochrome spectra, the amount of assembled bc1 complex is decreased in the three strains (Fig. (Fig. 33B). The bc1 activity is further decreased in the CYT1-1 QCR9-1 double mutant (18% of the wild-type level) compared with each single mutant (Table (Table1).1). A slight diminution of Cox activity also is observed in the double mutant whereas the QCR9-1 and CYT1-1 mutations alone have no detectable effect on this complex. The ATP synthase activity is not affected in any of the strains (data not shown). Finally, the activities of the three respiratory complexes are nearly nil in the triple mutant Δoxa1 CYT1-1 QCR9-1, several subunits being degraded (data not shown).

Table 1

The enzymatic activities of the bc1 and Cox complexes are affected in the double mutant CYT1-1 QCR9-1 In conclusion, both the assembly and the enzymatic activities of the bc1 complex are affected in the CYT1-1 QCR9-1 double mutant. The two mutations together have a much more deleterious effect on the bc1 complex activity than each single mutation. Also a slight decrease in the Cox activity is only visible in the double mutant. Thus, the two TM domains of Cyt1p and Qcr9p seem to genetically interact and this interaction appears critical for the assembly and/or activity of bc1 and Cox complexes.

Cyt1p Is Required for the Restoration of Cox Assembly in Absence of Oxa1p.

Mutations in the TM domains of Cyt1p and Qcr9p partially restore the insertion and assembly of Cox and ATP synthase in the absence of Oxa1p. However, this restoration is always stronger with the CYT1-1 than with the QCR9-1 mutation (Fig. (Fig. 2).2). To establish the relative role of these two subunits in the restoration of respiratory complex assembly, we asked whether either of the suppressor mutations could function in the absence of the other subunit.

We constructed two Δoxa1 strains carrying either the CYT1-1 mutation and the Δqcr9 inactivation, or the QCR9-1 mutation and the Δcyt1 inactivation. As the two subunits Cyt1p and Qcr9p are required for the bc1 electron transfer activity, this activity is nil in the two strains and we found that the ATPase activity is still fully restored (data not shown). As shown in Fig. Moreover, carbonate extractions show that Qcr9p is found predominantly in the membrane fraction in both strains (data not shown). Thus, the lack of restoration of Cox assembly observed in the Δcyt1 QCR9-1 strain is not caused by the destabilization or mislocalization of Qcr9p but is more likely to be caused by the absence of Cyt1p. Hence, Cyt1p is required for the restoration of Cox assembly by the QCR9-1 mutation whereas Qcr9p is not necessary for this restoration by the CYT1-1 mutation. Thus, Cyt1p has a major role in the restoration of Cox assembly in the absence of Oxa1p. (C) Qcr9p was tagged with the c-myc epitope as described in Materials and Methods. Five hundred micrograms of total yeast proteins, extracted as described (31), was separated on 12% SDSpolyacrylamide gels and immunoblotted with anti-c-myc. WT (YS18-5A), QCR9-1 (YS16-1B), Δoxa1 QCR9-1 (YS16-18D), Δoxa1 Δcyt1 QCR9-1 (YS16-1C).

The Mutant TM Domain of Cyt1p Mediates the Restoration of Complex

Assembly.

Cyt1p has a bipartite structure. A large N-terminal hydrophilic domain, located in the intermembrane space and binding the heme moiety, is responsible for the electron transfer activity. A short C-terminal hydrophobic domain anchors the molecule to the mitochondrial inner membrane (refs. 32 and 33 for reviews). As shown in Fig. Fig. 5,5, Cyt1p is tightly bound to the membrane and resistant to carbonate extraction in wild-type cells. However, fastmigrating carbonate-extractable forms of cytochrome c1 are systematically observed in the Δoxa1 CYT1-1 strain, and we have previously proposed that they could be responsible for the restoration of complex assembly (21). In the Δoxa1 QCR9-1 strain, no carbonate extractable forms of cytochrome c1 are detected. This finding indicates that these forms do not play a major role in suppression but are likely to be a simple consequence of the CYT1-1 mutation. Indeed, this mutation introduces a positive charge in the TM and thus probably modifies the binding properties of Cyt1p to the membrane. Furthermore, the nature and position of all of the suppressor mutations in the TM domains of Cyt1p and Qcr9p suggests that the TM domain of Cyt1p is responsible for the restoration of complex assembly.

Carbonate-extractable forms of cytochrome c1 do not accumulate in the Δoxa1 QCR9-1 strain. Mitochondria (equivalent of 300 μg of proteins) were purified from cells grown on galactose complete medium and treated with sodium carbonate as described (14). The supernatants (S; soluble fractions) and pellets (P, membrane fractions) were separated on 12.5% SDS-polyacrylamide gels and transferred to nitrocellulose filters. Detection of cytochromes c and c1 was performed on the membrane as described (34). * indicates the fast-migrating extractable forms of cytochrome c1. WT (CW30); Δoxa1 QCR9-1 (R102); Δoxa1 CYT1-1 (R101).

To test this hypothesis, we constructed a shortened Cyt1p (see Materials and Methods) that no longer carries the hydrophilic domain of Cyt1p but only encodes the presequence essential for the correct mitochondrial import and the C-terminal part of the protein with the mutant TM domain (Fig. (Fig. 66A). Remarkably, the respiratory growth is restored by the short Cyt1p in cells carrying an inactivated Δoxa1 gene together with a wild-type CYT1 gene ensuring full electron transfer activity through the bc1 complex. We found that Cox2p accumulation and Cox activity are still partially recovered whereas the accumulation of Atp4p and ATPase activity are restored to wild-type level (Fig. (Fig. 66 B and C, and data not shown). However, the restoration mediated by the short Cyt1p does not take place in the absence of wild-type Cyt1p or Qcr9p (data not shown). This finding suggests that this short mutant Cyt1p requires the presence of some assembled bc1 complex, which may be necessary for the correct integration or orientation of the proteins in the membrane. In addition, a short form of Cyt1p with a wild-type TM domain is able to restore neither the respiratory growth nor the complex assembly, stressing the importance of the CYT1-1 mutation in the mechanism of suppression (data not shown). In conclusion, the mutant TM domain of cytochrome c1 restores the assembly of both Cox and ATPase complexes in the absence of Oxa1p.

DISCUSSION

The Oxa1p family plays a pivotal role in the insertion and assembly of membrane proteins into organelles and bacteria. In yeast mitochondria, the absence of Oxa1p leads to severe defects in the biogenesis of the Cox and ATPase complexes and to minor defects in the assembly of the bc1 complex. Unexpectedly, we have shown that single mutations in the TM domains of two subunits of the bc1 complex, Cyt1p and Qcr9p, can bypass the absence of Oxa1p and partially restore the biogenesis of Cox and ATPase assembly (ref. 21 and this study). This restoration is independent of the electron transfer activity of the bc1 complex because we have shown that it also occurs in strains deficient for the bc1 complex activity (see Fig. In most cases, the mutations in Cyt1p or Qcr9p that compensate for the absence of Oxa1p correspond to single amino acid substitutions. For Cyt1p, these mutations affect a number of amino acids all located in the TM domain, e.g., the CYT1-1 or CYT1-2 mutations that change the leucine 216 or 219 to a lysine residue (21). In this study, we show that the mutant TM domain of Cyt1p is sufficient on its own for the restoration of complex assembly. For Qcr9p, we have obtained in all four cases, the same substitution changing the glycine 23 to an arginine residue (mutation QCR9-1). This glycine, located in the middle of the TM domain, is conserved in the plant, chicken, and mammal homologues and may play an important role in complex assembly.

According to the crystal structure of the yeast bc1 complex (30,33), the TM domains of Cyt1p and Qcr9p are in close proximity and our studies on the double mutant CYT1-1 QCR9-1 show that these two domains interact genetically. Moreover, Cyt1p seems to be absolutely required for the restoration of Cox assembly by the mutant Qcr9p, this restoration being in any case weaker than with the mutant Cyt1p itself. Thus, the QCR9-1 mutation seems to act with Cyt1p, at least for restoration of Cox assembly, and glycine 23 appears critical for the interactions between Qcr9p and Cyt1p. The full restoration of ATPase assembly by the QCR9-1 mutation in the absence of Cyt1p is reminiscent of restoration observed in the protease-deficient mitochondria (14) and suggests that the need of Oxa1p for ATPase assembly is slight enough to be bypassed by a number of extragenic mutations.

Restoration of Complex Assembly Could Occur Through Lateral Interactions

Between TM Domains of Various Subunits.

It recently was shown that the yeast and mammalian respiratory complexes assemble into supramolecular structures (35,36). In particular, the bc1 and Cox complexes associate to form a supercomplex and the subunits Qcr9p and Cyt1p both appear important for its formation.

We have shown that the double mutation CYT1-1 QCR9-1 not only drastically reduces the bc1 complex activity but also noticeably affects Cox activity. This result together with the fact that the Cyt1p and Qcr9p TM domains are located at the periphery of the bc1 complex (30) suggest that these domains could interact with Cox subunits during the biogenesis of the complexes.

QCR9-1 and the mutations in the Cyt1p TM domain that compensate for the absence of Oxa1p introduce positively charged amino acids in the membrane region. Thus it is tempting to propose that this charge is responsible for the restoration of respiratory complex assembly. This positively charged amino acid could interact with a negatively charged amino acid of another TM domain. Such negatively charged amino acids occur in several TM domains of respiratory complex subunits. In particular, an analysis of the crystal structure of beef Cox complex (37) and sequence alignments between beef and yeast subunits indicates that the beginning of the first TM helix of Cox2p presents several acidic amino acids. Indeed, one of the main consequence of the absence of Oxa1p is a defect of Cox2p insertion and translocation (12,13). Thus, it is tempting to propose that the negatively charged residues of Cox2p could interact with the positive charge present in the mutant TM of Cyt1p or Qcr9p, this interaction leading to the restoration of Cox2p insertion.

Oxa1p Could Play a Role in the Insertion and Lateral Exit of Less Hydrophobic TM Domains.

How could such simple membrane interactions bypass the need for Oxa1p, which has been proposed to be essential for the insertion within the inner membrane of respiratory complex subunits? It has been recently shown that the insertion of some membrane subunits, such as Atp9p and Atp8p subunits, is completely Oxa1p-independent (14,38). Similarly, substantial assembly of the bc1 complex subunits can occur in the absence of Oxa1p (9). Several additional proteins might be also involved in the translocation/insertion machinery of mitochondrial membrane proteins (41)(42)(43)(44). In particular, Preuss et al. (44) have shown that the double mutant Δmba1 Δoxa1 exhibits a strong growth defect even on glucose, suggesting that Oxa1p and Mba1p have an important overlapping function. However, the fact that the CYT1-1 mutation does not suppress the double mutant Δmba1 Δoxa1 (data not shown) suggests that Mba1p acts at a different step of the translocation machinery. This work provides a genetic demonstration that the TM domain of subunits of different complexes interact during the biogenesis and reinforces the recent view that respiratory enzymes are assembled into supramolecular structures (35,36).

  Fig.66A).

Figure 6

 6 Figure 6 The mutant membrane domain of Cyt1p mediates suppression. (A) Schematic representation of the mutant pre-Cyt1p protein and the short form (see Materials and Methods for constructions). The black box represents the hydrophobic domain anchoring the protein to the membrane, and * indicates the position of the CYT1-1 mutation. The dashed box represents the 61-aa presequence that is cleaved to give the mature form Cyt1p and the four vertical lines indicate the positions of the heme ligands within the hydrophilic central domain. (B and C) The Δoxa1 mutant (NBT2) was transformed with three plasmids. YEpYS7 expresses the mutant Cyt1p protein (Δoxa1 CYT1-1), pFL61 is the control vector (Δoxa1), and YEpYS9 expresses the short form of the mutant Cyt1p (Δoxa1 CYT1-1,-S). (B) Transformants were grown on ethanol medium and incubated for a week at 28°C. (C) Mitochondria were purified from transformants grown on minimal medium to select for the presence of the plasmid. Cox2p, Atp4p, and Atp2p were immunodetected as described in Fig. Fig.22C.

  14. Cytochrome c oxidase activity was measured according to ref. 21, ATPase activity according to ref. 24, and ubiquinol cytochrome c oxidoreductase activity according to ref. 25.

Figure 3

 3 Figure 3 Respiratory growth is severely impaired in the double mutant CYT1-1 QCR9-1. WT (CW30); CYT1-1 (PHT2); QCR9-1 (PHT28); QCR9-1 CYT1-1 (CQ2-2B). (A) Strains were grown on glucose (G) and ethanol (E) media as a respiratory substrate and incubated for 3 days at 28°C. (B) Lowtemperature cytochrome absorption spectra of whole cells were recorded according to ref. 9. The arrows indicate the absorption maxima of the α bands of cytochromes c (546 nm), c1 (552 nm), b (558 nm), and a + a3 (602 nm).

  Fig. Fig.44B. The ubiquinol cytochrome c oxido-reductase activity (bc1 activity) is expressed in nmol of reduced cytochrome c/min per mg of protein.

Fig. 44 A

 44 and B, Cox2p maturation and Cox activity are still partially restored in the strain carrying the CYT1-1 mutation and the Δqcr9 inactivation, whereas no restoration is detected in the strain carrying the QCR9-1 mutation and the Δcyt1 inactivation. We have ruled out the possibility that the Cox deficiency in the latter strain is caused by the destabilization of Qcr9p in the absence of Cyt1p (Fig.(Fig.44C).

Figure 4 Cyt1p

 4 Figure 4 Cyt1p is essential for the restoration of Cox assembly in the absence of Oxa1p. (A) Mitochondrial translation products were labeled as described in Fig. Fig.22B. WT (CW30); Δoxa1 CYT1-1 Δqcr9 (YST3); Δoxa1 Δcyt1 QCR9-1 (YST4); Δcyt1 QCR9-1 (YSG9-3B). (B) Enzymatic activities were measured in mitochondria purified from galactose grown cells as described in Materials and Methods. The cytochrome c oxidase activity (Cox activity) is expressed in nmol of oxidized cytochrome c/min per mg of protein and percentages of wild-type activities are given in parenthesis.(C) Qcr9p was tagged with the c-myc epitope as described in Materials and Methods. Five hundred micrograms of total yeast proteins, extracted as described(31), was separated on 12% SDSpolyacrylamide gels and immunoblotted with anti-c-myc. WT (YS18-5A), QCR9-1 (YS16-1B), Δoxa1 QCR9-1 (YS16-18D), Δoxa1 Δcyt1 QCR9-1 (YS16-1C).

  Fig.44).Introduction of a Positive Charge in TM Domains of Either of the Two bc1 Subunits Restores the Insertion and Assembly of Cox and ATPaseComplexes.

  Samuelson et al.(7) and Scotti et al.(8) have proposed that the bacterial Oxa1p homologue, YidC, could act like the TRAM protein of the mammalian endoplasmic reticulum membrane. TRAM appears to be required for the insertion and lateral exit of TM segments that are not sufficiently hydrophobic to equilibrate by themselves into the lipid bilayer, these less hydrophobic sequences being sandwiched between the multispanning TRAM protein(39,40). Oxa1p has five predicted TM segments and may play a similar role in the inner membrane of mitochondria for the less hydrophobic TM segments, such as the first TM helix of Cox2p (see Fig. Fig.7).7). If this model is true, one can predict that the introduction of charged residue in a TM domain would render it more dependent on Oxa1p. This is the case for the TM domain of Cyt1p for which the presence of a positive charge (e.g., CYT1-1) leads to the accumulation of noninserted (carbonate extractable) forms of Cyt1p in the Δoxa1 mutant, the insertion of wild-type Cyt1p being Oxa1p-independent. In the absence of Oxa1p and in the presence of mutant TM domain of either Qcr9p or Cyt1p, we propose that the positively charged TM domains of the bc1 complex subunit can interact with the negatively charged TM domain of Cox2p or other Oxa1p-dependent subunits. This interaction could allow some lateral exit of the TM domain within the lipid bilayer from their site of insertion, leading to partial restoration of respiratory complex assembly even when Oxa1p is not present. The insertion of less hydrophobic TM domain might play an essential role for the formation of oligomeric membrane complexes because the charged residues located in the TM domain are likely to be important for the folding and stabilization of the complex structure.

Figure 7

 7 Figure 7 Mode of action of Oxa1p and positively charged TM domains. (A) Oxa1p could allow the membrane insertion of charged or less hydrophobic TM domains (e.g., first TM helix of Cox2p) by sandwiching them until they reach stable integration within the oligomeric complex (Cox complex). (B) Positively charged TM domain (e.g., Cyt1p) could be coinserted with a negatively charged one (e.g., first TM helix of Cox2p).

ACKNOWLEDGMENTS

We thank N. Lachacinsky for technical assistance. We thank Dr. J. Herrmann (Institute for Physiological Chemistry, Munich) for the mba1 mutant and Drs. J. Velours and J. M. Galan for the gift of antisera. We are grateful to Drs. N. Bonnefoy, O. Groudinsky, and C. J. Herbert for discussions and critical reading of the manuscript and C. J. Herbert for checking the English. This work was supported in part by a grant from the Association Française contre les Myopathies and by a fellowship from Ligue contre le Cancer de l'Essonne (to P.H.).