Nicolas Reul

Hubert Branger

Jean-Paul Air Giovanangeli

Flow

M Banner

Air Flow separation above unsteady breaking waves

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


N Melab

J Gmys
email: jan.gmys@umons.ac.be

M Mezmaz

D Tuyttens
email: daniel.tuyttens@umons.ac.be

Multi-core versus Many-core Computing for Many-task Branch-and-Bound applied to Big Optimization Problems

Keywords: Muti-core, Coprocessor/Many-core, Intel Xeon Phi, Parallel Branch-and-Bound, permutation Flow-Shop

On the road to exascale, coprocessors are increasingly becoming key building blocks of High Performance Computing platforms. In addition to their energy efficiency, these many-core devices boost the performance of multi-core processors. In this paper, we revisit the design and implementation of Branch-and-Bound (B&B) algorithms for multi-core processors and Intel Xeon Phi coprocessors considering the offload mode as well as the native one. In addition, two major parallel models are considered: the master-worker and the work pool models. We address several parallel computing issues including processor-coprocessor data transfer optimization and vectorization. The proposed approaches have been experimented using the Flow-Shop scheduling problem (FSP) and two hardware configurations equivalent in terms of energy consumption: Intel Xeon E5-2670 processor and Intel Xeon Phi 5110P coprocessor. The reported results show that:

(1) the proposed vectorization mechanism reduces the execution time by 55.4% (resp. 30.1%) in the many-core (resp. multi-core) approach ; (2) the offload mode allows a faster execution on MIC than the native mode for most FSP problem instances ; (3) the many-core approach (offload or native) is in average twice faster than the multi-core approach ; (4) the work pool parallel model is more suited for many/multi-core B&B applied to FSP than the master-worker model because of its irregular nature.

Introduction

In addition to multi-core processors, coprocessors are increasingly becoming key building blocks of High Performance Computing platforms. Besides their energy efficiency, they boost the performance of traditional multi-core processors through the combination of a larger number of processing cores, vector-SIMD processing and multi-threading. Currently, the most used coprocessors (Top500 ranking of November 2015) [START_REF]Top500 HPC international ranking[END_REF] are Nvidia GPU accelerators and Intel MIC 1 coprocessors. The former are composed of a large number of slim cores while the latter, the focus of this paper, integrate a relatively smaller number of streamlined largish cores relying on SIMD processing. From now on, for brevity "MIC" is used to designate Intel Xeon Phi and "MC" to represent multi-core. Today, MIC coprocessors allow to achieve peak performance of the order of one TeraFlops. Nevertheless, it is often difficult to extract the largest portion of the theoretically available performance. Indeed, the specific features of these coprocessors raise several issues including the optimization of data transfer between the processor and its coprocessor, vectorization, data placement optimization, etc. Several research works have recently addressed these issues in different application areas including supervised deep learning [START_REF] Viebke | The Potential of the Intel (R) Xeon Phi for Supervised Deep Learning[END_REF], DNA sequence analysis [START_REF] Memeti | Accelerating DNA Sequence Analysis Using Intel(R) Xeon Phi(TM)[END_REF], astrophysics (dynamics of astrophysical objects) [START_REF] Kulikov | Astrophi: A code for complex simulation of the dynamics of astrophysical objects using hybrid supercomputers[END_REF], hydrodynamics (smoothed particle hydrodynamics simulation of a nebula) [START_REF] Dokulil | High-level Support for Hybrid Parallel Execution of C++ Applications Targeting Intel R Xeon Phi TM Coprocessors[END_REF], etc. However, in combinatorial optimization the parallelization for Xeon Phi coprocessors is rarely addressed. The overall objective of this paper is to revisit the parallel design and implementation of Branch-and-Bound (B&B) algorithms for MIC coprocessors. For comparison (MC versus MIC), a multi-core implementation is also considered using the same parallelization approach.

B&B algorithms are well-known methods for solving to optimality NP-hard optimization problems 2 . They are based on an implicit enumeration of the solutions composing the search space associated with the problem to be tackled. The search space is explored by dynamically building a tree whose root node designates the original problem. Each internal or intermediate node represents a subproblem obtained by the decomposition of the subproblem associated with its parent node. The leaf nodes designate potential solutions or subproblems that cannot be decomposed. The construction of the B&B tree and its exploration are performed using four operators: branching, bounding, selection and elimination. The algorithm proceeds in several iterations to progressively improve the best solution found so far. The generated and not yet examined subproblems are kept in a pool, that is initialized with the original problem. At each iteration, the selection operator is used to select a subproblem from this pool, according to some strategy (depth-first, best-first,...). The branching operator performs its decomposition into smaller subproblems. The bounding operator calculates a lower bound of each generated subproblem. Each subproblem having a lower bound higher than the current upper bound (best solution found so far) is discarded by the elimination operator. It means that this subproblem will not be decomposed.

Recently, the parallelization of B&B algorithms has been revisited for multi-core (clusters of) processors [START_REF] Barreto | Parallel branch and bound algorithm-a comparison between serial, openmp and mpi implementations[END_REF] and GPU [START_REF] Melab | A gpu-accelerated branch-and-bound algorithm for the flow-shop scheduling problem[END_REF][START_REF] Lalami | Contribution à la résolution de problèms d'optimisation combinatoire: méthodes séquentielles et parallèles[END_REF][START_REF] Chakroun | Reducing thread divergence in a gpu-accelerated branchand-bound algorithm[END_REF] and their combination [START_REF] Chakroun | Combining multi-core and gpu computing for solving combinatorial optimization problems[END_REF][START_REF] Vu | Heterogeneity and locality-aware work stealing for large scale branch-and-bound irregular algorithms[END_REF]. In [START_REF] Chakroun | Reducing thread divergence in a gpu-accelerated branchand-bound algorithm[END_REF], it is shown that the bounding operator represents on average between 98 % and 99 % of B&B applied to the Flow-Shop problem (considered as a case study in this paper). Such result demonstrates that the bounding operator needs massively parallel computing. The GPU-accelerated bounding has been investigated in [START_REF] Melab | Graphics processing unit-accelerated bounding for branch-and-bound applied to a permutation problem using data access optimization[END_REF]. The reported results show that the CPU-GPU data transfer is costly. Therefore, it is recommended to perform also the branching operator on GPU in order to generate locally the subproblems and evaluate their lower bounds. In this paper, we reuse this idea within the context of MIC coprocessors using the offload (GPU-like) mode. Regarding the parallelization of B&B on MIC coprocessors, it has only been previously addressed in our work [START_REF] Mezmaz | Parallel branch-and-bound using private ivm-based work stealing on xeon phi mic coprocessor[END_REF] using the native mode without vectorization. The parallelization of the algorithm is based on the work stealing model. In the native mode, the coprocessor is standalone and executes the whole B&B algorithm. To the best of our knowledge, the parallelization of B&B on MIC coprocessors has not been previously addressed using the offload mode. The major contributions of this paper are the following:

• Revisiting the parallelization of B&B and its implementation on MC processors and MIC coprocessors. The objective is to investigate the parallel bounding model combined with the parallel tree exploration model of B&B algorithms to allow highly efficient solving of large instances of the Flow-Shop problem on MC processors and MIC coprocessors. Two parallel models are considered: master-worker and work-pool [START_REF] Kumar | Introduction to Parallel Computing[END_REF]. Unlike in the masterworker model, in the work pool model the work distribution is initiated by the workers (not the master) which makes this model more suited for irregular applications such as B&B.

• For the parallelization on MIC, investigating the offload-based approach as well as the native-oriented one.

• Proposing a vectorization mechanism for multi-core processors as well as for MIC coprocessors. Vectorization has not been considered in our previous work [START_REF] Mezmaz | Parallel branch-and-bound using private ivm-based work stealing on xeon phi mic coprocessor[END_REF].

• Finally, evaluating and discussing the performance of the proposed approaches considering different criteria: multi-core vs. many-core, offload vs. native, vectorized vs. nonvectorized, and master-worker vs. work pool. The experiments have been performed using the Flow-Shop scheduling problem and two hardware configurations equivalent in terms of energy consumption: Intel Xeon E5-2670 and Intel Xeon Phi 5110P.

The rest of the paper is organized as the following. In Section 2, we first present the IVMbased serial B&B algorithm. IVM is a new data structure dedicated to permutation problems and presented in the next section. In Section 3, we detail the multi-core and many-core parallelization approaches. In Section 4, we report some experimental results comparing the different approaches. Finally, some conclusions are drawn in Section 5.

IVM-based serial B&B

As quoted in the introduction, B&B is a tree-based exploration algorithm using four operators: selection, bounding, elimination and branching. At implementation, these four operators act on the data structure that stores the generated subproblems. Therefore, the design of the data structure has a great impact on the efficiency of these operators. A stack implemented as a linked-list is often used in existing works related to B&B algorithms using depth-first selection. In [START_REF] Mezmaz | Parallel branch-and-bound using private ivm-based work stealing on xeon phi mic coprocessor[END_REF], it is shown that the IVM data structure, which stands for Integer-Vector-Matrix, allows to speed up the exploration using a smaller memory footprint than its linked-list counterpart. Therefore, IVM is reused in this paper to deal with permutation optimization problems. A permutation optimization problem consists in finding a permutation of n objects which optimizes an objective function. For instance, for the Flow-Shop problem, considered as a case study in this paper, it consists in finding the schedule of n jobs on m machines that minimizes the makespan. In other words, the objective is to find a permutation of n jobs that minimizes the due date of the last job on the last machine. The IVM data structure for the Flow-Shop problem is illustrated in Figure 1 where the left side (Figure 1.(a)) is the tree-based representation using top-down gray rows and the Linked-list-based representation using horizontal and vertical solid lines. In the tree-based representation, each node designates a partial (subproblem) permutation or a full (solution) permutation. The jobs before the "/" symbol are scheduled while the following ones are to be scheduled.

On the other hand, IVM illustrated in Figure 1.(b) indicates the next subproblem to be solved. The integer I of IVM gives the level (position of "/" + 1) of this subproblem. In this example, the level of the next subproblem is 1. The vector V indicates the jobs that are already scheduled (jobs 2 and 3 in the example) and thus the position of the subproblem among its sibling nodes in the tree. The matrix M, which is triangular, contains the jobs to be scheduled at each level: all the n jobs (for a problem with n jobs) for the first row, n -1 jobs for the second row, and so on.

To use the IVM data structure in the B&B algorithm, some of its operators are revisited as the following:

• The bounding operator just associates a lower bound to a subproblem, so it is not changed.

The three other operators act on the data structure, so they have to be redefined.

• The selection operator indicates the next subproblem (23/14 in the example) to be solved using the integer and the vector.

• The bounding operator associates a lower bound to the selected subproblem. If the lower bound is smaller than the cost of the best solution found so far, the subproblem is decomposed.

• The branching (decomposition) operator is performed by modifying the IVM data structure. The modification of IVM consists in increasing the level, meaning the value of I, and copying in the matrix M the next jobs to be scheduled to the next row.

• The elimination operator withdraws a subproblem if its lower bound is greater than the cost of the best solution found so far. Its implementation consists in incrementing the index in V if possible. Otherwise, the value of the integer I is decremented and the value of V is incremented.

Many-core and Multi-core B&B

In this section, we first briefly describe the MIC-based hardware architecture and its associated parallel programming model. Then, we detail the offload-based and native-oriented parallelization approaches for MIC coprocessors. The parallelization approach for multi-core processors is the same as the native-based one for MIC coprocessors.

MIC-based architecture and parallelization

The market of accelerators has been dominated by Nvidia during several years. Since recently, they are faced to the competition of Intel with its Many Integrated Cores (MIC)-based Xeon Phi. This latter is a coprocessor coupled to the processor through a PCI Express bus. As illustrated in Figure 2, a typical platform consists of one to two Intel Xeon processor(s) (CPUs) and one to eight (two in this figure) Intel Xeon Phi coprocessors per host. Multiple such platforms may be interconnected to form a cluster or supercomputer [START_REF] Chrysos | Intel Xeon Phi X100 Family Coprocessor -the Architecture[END_REF].

From the hardware point of view, the Xeon Phi board has one Knights Corner (KNC) processor, the first production chip based on the MIC architecture, and 8 GB of GDDR5 RAM. As illustrated in Figure 3, KNC integrates up to 60 CPU-cores interconnected by a high-speed bi-directional ring, and runs at over 1 GHz. It connects to its private external memory with a peak bandwidth of over 320 Gbps. The cores are based on the Intel Pentium architecture. Each core has 32 KB of L1 data and instruction cache, 512 KB of L2 data cache kept coherent by a global-distributed tag directory (TD), and a 512-bit vector Floating Point Unit (FPU). This latter performs fused-multiply-add (FMA) operations. Therefore, the peak performance is about 32 (resp. 16) GFlops in single (resp. double) precision. Consequently, the KNC delivers a peak performance of about 2 (resp. 1) TFlops in single (resp. double) precision.

From a programming standpoint, the key is to treat the Intel Xeon Phi coprocessor as an x86-based SMP-on-a-chip with over 50 cores, with multiple threads per core and 512-bit SIMD instructions. From programming language point of view, Intel Xeon Phi is more accessible than Nvidia GPU because it can be programmed using standard programming environments such as OpenMP, MPI, Cilk Plus and Posix Threads. However, to achieve higher performance one should consider three fundamental features: scaling through locality, Simultaneous Multi-Threading (SMT) and vectorization. These last two are often combined as it is done in this paper and other papers such as [START_REF] Memeti | Accelerating DNA Sequence Analysis Using Intel(R) Xeon Phi(TM)[END_REF] and [START_REF] Viebke | The Potential of the Intel (R) Xeon Phi for Supervised Deep Learning[END_REF]. In [START_REF] Memeti | Accelerating DNA Sequence Analysis Using Intel(R) Xeon Phi(TM)[END_REF], thread-level parallelism is used in splitting the DNA sequence into chunks, and vectorization is applied to the transition function of finite automata (loop vectorization). In [START_REF] Viebke | The Potential of the Intel (R) Xeon Phi for Supervised Deep Learning[END_REF], thread parallelism is used to divide the input over the available threads, allowing threads to process samples concurrently. Vectorization is applied in convolutional layers to the computations of partial derivatives and weight gradients. On the other hand, as an Intel Xeon Phi coprocessor runs an operating system (Linux) and has its own IP address, there are two ways to involve it in a parallel program: a processor-centric "offload" mode and a "native" mode. In the next sections, we investigate the two approaches.

Offload-based parallelization of B&B for MIC coprocessors

The parallelization approach of the B&B algorithm uses the thread-based Master-Worker parallel model. The master thread performs the selection and pruning operators of the B&B while the worker threads execute the branching and bounding operators. To take maximum advantage of the computational power provided by the massively parallel MIC coprocessors these latter should be fed by a large number of computations (many-task computing). To achieve that as illustrated in Figure 4, the master thread maintains multiple IVM-based pools of tree nodes generated and evaluated by the worker threads. On the processor side, at each iteration of the exploration process a set of tree nodes (whose size is a user-parameter) is selected. The selected set of nodes is offloaded to the coprocessor to be processed.

On the coprocessor side, as illustrated in Algorithm 1 (Line 10-23), each thread generates and evaluates one or more children subproblems. Each child subproblem is uniquely identified by the corresponding parent subproblem and an index indicating its position among sibling nodes (Line 13-15). After mapping a thread onto a parent node and a child index, the thread generates Algorithm 1 Pseudo-code for the offload-based Branch-and-Bound algorithm. #pragma offload(mic:0) in(poolOfParentNodes) out(poolOfLowerBounds) end while 31: end procedure the child subproblem. For children that are leaves the cost of the solution is evaluated. The children which are internal nodes are evaluated (bounded) using Algorithm 2 and their associated lower bounds are returned to the CPU. In order to avoid transferring the resulting children nodes the branching operator is also performed on the CPU (this operation can be overlapped with the computation of lower bounds using the signal and wait specifiers). Every child having a lower bound greater than the cost of the best solution found so far is pruned on CPU. The selection and pruning operators (Lines 5 and 26) are performed in parallel using all the processing cores of the CPU. The process is iterated until the exploration is completed and the optimal solution is found.

The implementation on Intel Xeon Phi of the coprocessor-based B&B requires to address the challenging issues quoted in previous section. First, to deal with the processor-coprocessor data transfer optimization the branching operator, which generates tree nodes or subproblems, is moved to the coprocessor. The execution of the branching operator on the coprocessor allows one to avoid the transfer of the branched parent nodes from CPU to Xeon Phi which is costly. However, this raises other issues related to thread granularity and mapping. Indeed, if a parent node is processed entirely (branching and bounding) by a single thread there will be a load imbalance. In fact, the parent nodes may have different numbers of children as they are located at different levels in the B&B tree. To deal with this problem the tasks assigned to threads are child nodes instead of parent nodes.

The semantics of the algorithm and its data structures is not the focus of this paper. For more details on these ones and on the lower bound please refer to the Ph.D thesis of I. Chakroun [START_REF] Chakroun | Parallel heterogeneous branch and bound algorithms for multi-core and multi-gpu environments[END_REF].

for (k = 0 → n(n-1)
2 ) do 6:

tmp0, tmp1, ma0, ma1 ← InitFun(k, nbFixed, MM, RM)

for

(j = 0 → n) do 8: job←JM[k][j] 9: if (SM[job]==0) then 10: tmp0 += PTM[ma0][job] 11: tmp1 = max(tmp1, tmp0 + LM[k][job]) + PTM[ma1][job] 12:
end if return LB 18: end procedure

Vectorization

One of the major mechanisms allowing performance improvement on Intel Xeon Phi is vectorization [START_REF] Stanic | Evaluation of Vectorization Potential of Graph500 on Intel Xeon Phi[END_REF]. Different levels are provided ranging from compiler-based automatic easy-to-use vectorization to manual and programmer control vectorization. In our work, as quoted previously, the most consuming part of the B&B algorithm is the calculation of the lower bound function (Algorithm 2). In the rest of this section, we first present FSP then we propose a method for the vectorization of its associated lower bound function.

Flow-Shop Problem (FSP). The Flow-Shop scheduling problem is a permutation problem which consists in scheduling n jobs on m machines [START_REF] Garey | The complexity of flow-shop and job-shop scheduling[END_REF]. For instance, in Figure 5, we have 4 jobs designated by different colors to be scheduled on 3 machines.

The scheduling must be done with respect to two constraints: each machine cannot be simultaneously assigned to more than one job (to more than one color), and the execution order of the jobs (the colors) is the same on all the machines. The objective is to minimize the makespan, i.e. the termination date of the last job on the last machine. In this example, the solution consists in scheduling first the red job, then the blue job and orange one, and finally the green job. The solution can be coded as a permutation (3, 4, 2, 1) and its cost is the termination date of the green job on the machine M3. In this work, the lower bound function proposed by Lageweg et al. [START_REF] Lenstra | A General bounding scheme for the permutation flow-shop problem[END_REF] is used in our bounding operator (Algorithm 2). This lower bound is mainly based on Johnson's theorem [START_REF] Johnson | Optimal two and three-stage production schedules with setup times included[END_REF] which provides a procedure for finding an optimal solution for Flow-Shop scheduling problem with 2 machines. This bound is known for its good results and has a computational complexity of O(m 2 nlog(n)), where n is the number of jobs and m the number of machines. For large values of the parameters m and n, the problem is time-intensive. More details on the lower bound and its computational complexity can be found in [START_REF] Melab | Graphics processing unit-accelerated bounding for branch-and-bound applied to a permutation problem using data access optimization[END_REF].

Vectorization of the lower bound of FSP. The focus is put on the most compute-intensive portion of the lower bound function and its main data-dependencies. This portion of code is the inner for-loop (Lines 7-13) which consumes about 70% of the bounding time. The body of this inner loop is executed n 2 × (n -1)/2 times, n being the number of jobs. Regarding data dependencies, the statement in Line 11, including a dependency of current tmp1 on tmp1 from previous iteration prevents vectorization (icc do not auto-vectorize it). In addition, except for Line 15 the iterations of the outer loop are independent (private variables: tmp0, tmp1, ind0, ind1 and current). However, only the inner loop may be vectorized 3 .

In order to allow more vectorization than provided by the compiler, the order of the nested loops must be inverted as illustrated in the vectorized lower bound function (Algorithm 3).

for (k = 0 → n(n-1)
2 ) do 6:

Tmp0[k], Tmp1[k], Ma0[k], Ma1[k] ← InitFun(k, nbFixed, MM, RM) 7:
end for

8:

for (j = 0 → J) do permute loop-order 9:

#pragma ivdep 10:

for (k = 0 → n(n-1)
2 ) do inner loop vectorizable 11:

job←JM[j][k] transpose JM 12: if (SM[job]==0) then 13: Tmp0[k] += PTM[Ma0[k]][job]
14:

Tmp1[k] ← max(Tmp1[k], Tmp0[k] + LM[k][job]) + PTM[Ma1[k]][job]
15:

end if

16:

end for

17:

end for

18:

for

(k = 0 → n(n-1)
2 ) do 19:

Tmp1[k]←EndFun(Tmp0[k], Tmp1[k], k, nbFixed, QM) 20:
end for

21:

LB←max-reduce(Tmp1[])

22:

return LB

23: end procedure

For auto-vectorization by the compiler it is preferable to write small separate loops, rather than merging into a single loop. The outer loop is thus split into 3 separate serial loops and a max-reduce operation (Line 20) in order to isolate the k-dependent instructions from the innerloop. The cost to pay for this is to declare the scalars tmp0, tmp1, ma0 and ma1 as arrays (resp. T mp0, T mp1, Ma0 and Ma1) of size n(n-1)

2 . The same strategy on GPU severely breaks down performance due to the memory problem (these intermediate variables are no longer stored into registers). In order to improve performance and assist the compiler in vectorizing the loops all arrays are aligned at 64 byte boundaries. For static arrays this is achieved by using attribute ((aligned(64))). For dynamically allocations the mm malloc function is used and the statement assume aligned(arr, 64) informs the compiler immediately before the concerned loop that the starting address of array arr is a multiple of 64 bytes. Even with the highest optimization level activated (-O3) the Intel compiler (icc) still needs the hint "#pragma ivdep" to vectorize the inner loop (Line 10) successfully. The two other for-loops are auto-vectorized.

Multi-core and native-based many-core parallelization of B&B

As pointed out in Section 3.1, in the native mode the Xeon Phi coprocessor is used as an independent many-core device. Therefore, the parallel B&B algorithm can be executed entirely on the coprocessor. For a fair comparison between MC and MIC, the same parallelization approach is used for the two architectures. We have considered the two parallelization models: master-worker and work pool. In the master-worker approach illustrated in Figure 6, as for the offload-based parallelization approach (for a fair comparison), the master thread maintains a set of IVM-based pools of subproblems and performs an iterative exploration process until the optimal solution is found. At each iteration, it selects a subset of parent subproblems from those pools to be sent to the worker threads which perform their decomposition and the evaluation of the generated children. These later are sent back to the master thread together with their associated lower bounds. The selection and pruning operators are performed in parallel using all the processing cores of the CPU. In the work pool-oriented parallelization approach, the master thread plays the same role. However, the parent subproblems are distributed to the worker threads on their request. As pointed out in the introduction this approach is well-suited in our case because the calculation function of the lower bounds is irregular. The master thread stops the exploration process when all the pools of subproblems are empty.

The implementations of the master-worker and work pool approaches using OpenMP are quite similar. The major difference between them is the parameter of the "schedule" clause in the work sharing parallel loop, which is "static" (resp. "dynamic") for the master-worker (resp. work pool) implementation. Finally, the two implementations are vectorized using the same method as for the offload-based many-core approach, presented in Section 3.2.1.

Experimentation

In this section, we propose an experimental study of the proposed many-core approaches for Intel Xeon Phi (offload and native) and compare them to their multi-core counterpart. We first describe the hardware and software testbeds and give some parameter settings used for our experiments. Then, we report and discuss some experimental results.

Hardware and software testbeds and parameter setting

For the multi-core implementation, we have used OpenMP version 4.0. All the experiments are run on hardware described in Table 1. The compiler used for the CPU and MIC implementations is Intel icc version 15.0 for Intel devices. For all experiments the compilation level 3 (-O3) is used. On the other hand, the UNIX time command is used to measure the elapsed execution time for each Flow-Shop instance. Finally, the GFLOPS(DP) row is obtained using the following computations:

• MIC: 16( f lops/Ghz) × 60(cores) × 1.053(GHz/core) = 1010.88GF/s

• CPU: 8( f lops/Ghz) × 8(cores) × 2.6(GHz/core) = 166GF/s
The last row indicates that the two hardware configurations (considering a two-socket multi-core processor) are equivalent in terms of energy consumption. For Intel Xeon E5-2670, as the server includes two sockets its power (in Watt) value is equal to 115 × 2 = 230.

As quoted in Section 3.1, the coprocessors are many-core devices dedicated to massively parallel computing. Therefore, they need to be fed by a large number of computations. To do that, many B&B trees must be explored simultaneously in order to generate multiple (IVM-based) pools maximizing the use of the coprocessor cores. Before the experiments are performed, the number M of IVM-based pools to be created is calibrated through a series of experiments on the problem instance T a028 for the MIC (offload and native) and MC approaches. The experimental results are reported in Figure 7. Based on the figure, the number of IVMs is fixed to 2500 (resp. 240 and 32) for the offload-based MIC approach (resp. native-based MIC approach and multicore approach). In addition, in our experiments multithreading (2 threads per physical core) is used for the MICbased approach. This parameter is determined experimentally as shown in Figure 8. The problem instance Ta028 (8.1 millions of decomposed subproblems) is considered for this calibration.

Experimental results

The performance analysis consists in comparing the performance of the parallel multi-core approach and the two many-core MIC-based approaches. The objective is to evaluate the impact on performance of the hardware architecture (multi-core vs. many-core), the programming mode of MIC (offload vs. native), the vectorization mechanism (vectorized vs. non-vectorized), and the parallelization model (master-worker vs. work pool). The different approaches have been experimented using the 10 instances (T a021 -T a030) of the Taillard's problem 20 jobs on 20 machines. The best solution found so far is initialized to the optimal solution to guarantee that the amount of work (explored nodes) is the same for each of the experimented approaches. This allows to prevent from the well-known speed up anomalies investigated for instance in [START_REF] Mans | Performances of parallel branch and bound algorithms with best-first search[END_REF].

Impact of hardware architecture, programming mode and vectorization

We first investigate three performance factors: the hardware architecture (MC vs. MIC), the programming mode of MIC (offload vs. native), and the vectorization mechanism (with vs. without). Table 2 reports the experimental results obtained on the T a021 -T a030 Taillard's instances. During the exploration of these instances on average 43.1 millions of subproblems are decomposed. The largest instance is T a023 with 140.8 millions of decomposed subproblems. The experimental results shown in Table 2 are obtained using a static task assignment in the parallel bounding phase. The first two columns of the table contain respectively the numbers of the 10 solved problem instances and their associated search space sizes in millions of nodes. The following doublecolumns designate the exploration times in seconds obtained using respectively the MIC-accelerated offload-based approach, the MIC-accelerated native-based approach, and the multi-core approach. Each double-column designates the exploration times obtained without (NoVect) and with vectorization (Vect). The MIC offload-based (resp. native-based) approach uses 236 ((resp. 240) threads while the multi-core hyperthreading-based approach uses 32 threads. In [START_REF] Saini | Early Multi-node Performance Evaluation of a Knights Corner (KNC) based NASA supercomputer[END_REF], the authors report some experimental results demonstrating the impact on data transfer overhead of the Coprocessor Offload Infrastructure (COI) daemon in the offload mode. The COI daemon runs the services required to support data transfer for offload on a dedicated core. The reported results show that it is beneficial to avoid using this core for user code, i.e., one should use only 59 cores. Following this recommendation, we have used 236 threads (corresponding to 59 cores) in our experiments for the offload-based MIC approach.

From the last row of the table, three major observations can be made. First, the proposed vectorization mechanism allows one to speed up the MIC-based (resp. multi-core) approach by about 55.4% (resp. 30.1%) in average. The improvement ratio is computed as follows:

NoVect-Vect NoVect . One can notice that the improvement is close to double on MIC than on MC because the size of the registers on Xeon Phi 5110P (512 bits) is double than the size of registers on Xeon E5-2670 (256 bits). Second, the offload-based MIC-accelerated approach is on average faster than its native-based counterpart whatever is the tackled problem instance.

Using the offload-based approach there is, on the one hand, the additional cost induced by processor-coprocessor data transfer. On the other hand, the partially sequential IVM-management is performed on the CPU and thus with a higher clock rate. The following subsection investigate this issue more closely. Finally, the MIC-accelerated approaches outperform their energyequivalent multi-core counterpart for all problem instances in their non-vectorized as well as vectorized versions. For instance, considering their vectorized versions the offload-based (resp. native-based) MIC approach is 2.16× (resp. 1.84×) faster than its multi-core counterpart.

Impact of the parallelization model

Another series of experiments has been performed using the work pool parallel model with vectorization considering the MC and MIC architectures. The obtained results are reported in Table 3. The two first columns are the same as those of Table 2. The three following double-columns designate the exploration times (in seconds) obtained using respectively the MIC offload-based vectorized approach, the MIC native-based vectorized approach and the multi-core vectorized approach. Each double column comprises the time obtained using the master-worker (schedule=static) model and the time obtained using the work pool (schedule=dynamic). From the last row of the table, two major observations can be made. First, for the two architectures the work pool model allows a faster resolution for all the tackled problem instances. This can be explained by the irregular nature of the lower bound calculation function illustrated in Figure 9. Subproblems with smaller lower bound calculation cost do not penalize the subproblems with a greater lower bound evaluation cost. Second, the benefit of using dynamic instead of static task assignment varies according to the target architecture and model. Using a dynamic instead of a static task assignment in the offload mode allows to decrease the average execution time by 6% while it allows an improvement of 17% (resp. 22%) in the native (resp. MC) case. These numbers correlate to the size of the task-pools evaluated in parallel. Because of averaging, when a very large pool is used a static task repartition is indeed likely to lead to smaller relative differences between per-thread workloads than the repartition of a small task-pool.

Considering the work pool model, the average resolution time for the offload and native models are nearly equivalent. The native-based algorithm outperforms its offload-based counterpart for the three smallest instances T a028 -T a030, while the latter is faster for all other instances. Considering the work pool model, the offload-based (resp. native-based) MIC approach is 1.78× (resp. 1.72×) faster than its multi-core counterpart.

Breakdown of execution time

In Figure 10 the average execution time (for instances T a021 -T a030) is decomposed into three parts: bounding, IVM-management and overhead induced by the parallelization of the bounding phase. The IVM-management time includes the selection of parent nodes and node elimination. The overhead is measured as follows. The parallel node evaluation is invoked twice: a first time without computing the lower bounds and a second time actually carrying out the evaluation of subproblems. The purpose of the first operation is to isolate the transferring and marshaling of data, thread creation and the scheduling of the node evaluation loop from the computation of lower bounds. The time labeled as "overhead" in Figure 10 is obtained by measuring the time required for this first operation. The bounding time is obtained by subtracting the measured overhead from the time required to perform the actual evaluation of the lower bounds.

Compared to a master-worker model the work pool approach allows to reduce the time required to perform the parallel bounding operation, which reduces the overall execution time. On the other hand, Figure 10 clearly shows that the work pool model is costlier to manage than its static master-worker counterpart. However, for both the MC and MIC-based approaches the benefits resulting from a better workload repartition outweigh this increased overhead.

Unsurprisingly, the offload-based approach incurs the highest overhead among the three considered approaches. Compared to the native execution model, the offload model spends less time managing the pool of subproblems, as this part is performed with a higher clock rate on the CPU. This allows the offload-based approach to use a higher number of IVMs without being penalized by a high IVM-management cost. As mentioned, especially in the case of a static task assignment, a larger pool-size may also improve the performance of the bounding phase, reducing the load imbalance between threads. Indeed, comparing the results obtained for the statically scheduled offload and native models, one can notice that the offload-based algorithm spends less time in the bounding phase than its native-based counterpart. This difference disappears when switching to the dynamic task assignment. This indicates that the relative penalty induced by load imbalance is lower for larger overall work loads, i.e. a larger number of IVMs.

Conclusion

According to the recent Top500 ranking (November 2015) [START_REF]Top500 HPC international ranking[END_REF], it is confirmed that hybrid HPC platforms including coprocessors is the trend towards the exascale era. On the other hand, it appears that the market of hybrid HPC is dominated by Nvidia followed by Intel with its Xeon Phi. In this paper, we have revisited the parallelization of B&B algorithms for many-core coprocessors, more exactly Intel Xeon Phi which emerged recently as a strong concurrent to Nvidia GPU. From the design point of view, we have combined two hierarchical parallel models: the parallel tree exploration model and the parallel bounding. The bounding operator is performed on the coprocessor because, on the one hand, it is the most time-consuming part of the B&B algorithm. On the other hand, it is massively data parallel and thus well-suited for coprocessors. In addition, the branching operator, which generates tree nodes during the exploration process, is also performed on the coprocessor to minimize the cost of their offloading from the processor to the coprocessor. Such coprocessor-based design of B&B algorithms gives rise to other issues including processorcoprocessor data transfer optimization and vectorization on Intel Xeon Phi. To deal with the first issue we have reused some recommendations proposed in [START_REF] Chakroun | Parallel heterogeneous branch and bound algorithms for multi-core and multi-gpu environments[END_REF] as quoted above. For the second issue, we have proposed a vectorization mechanism for the lower bound function. The different implementations have been experimented on the 10 instances of the 20 jobs on 20 machines problem using equivalent hardware configurations in terms of energy consumption: Xeon Xeon E5-2670 and Xeon Phi 5110P. The reported results show that first, the vectorization mechanism allows in average an improvement of 55.4% (resp. 30.1%) on Xeon Phi 5110P (resp. Xeon E5-2670). Second, the offload mode allows a faster execution than the native mode due the processing of sequential and weakly parallel parts on the higher-clocked CPU. Hyper-threading (2 threads per physical core) is used to speed up the execution on Xeon Phi. Third, the MIC-based parallelization is up to twice faster than its multi-core counterpart whatever is the used mode on MIC: offload or native. Finally, the work pool parallel model is more suited than the masterworker model for B&B applied to the Flow-Shop problem because of its irregular nature.

In the near future, we plan to extend our work to deal with parallel exact optimization on hybrid architectures combining multi-core processors, Xeon Phi coprocessors and GPU accelerators. Work partitioning between the three devices will be a particular challenging issue [START_REF] Dokulil | High-level Support for Hybrid Parallel Execution of C++ Applications Targeting Intel R Xeon Phi TM Coprocessors[END_REF]. Then, we will extend the resulting hybrid approach with a cluster-level parallelism. This will allow us to solve efficiently the hardest unsolved Taillard's instances of the Flow-Shop problem. Finally, we believe that the conclusions drawn from the experiments reported in this paper will be useful for the parallelization of other tree-based applications. Therefore, in the long term, we will try to generalize the approach to other tree-based exploration algorithms such as B&X (X=cut, price, ...).

Figure 1 :

 1 Figure 1: LL and IVM-based representations

Figure 2 :

 2 Figure 2: Hardware view: Intel Xeon Phi = coprocessor of CPU.

Figure 3 :

 3 Figure 3: Hardware view: Knights Corner core.

Figure 4 :

 4 Figure 4: Offload-oriented many-core B&B.

Algorithm 2

 2 Computation of lower bound (un-vectorized) input: subproblem = {permutation, nbFixed (#jobs fixed)}, constant data (MM, JM, PTM, LM) output: lower bound (LB) of subproblem 1: n := #jobs 2: procedure compute LB 3: RM, QM, SM ← InitTabs(permutation, nbFixed)

Figure 5 :

 5 Figure 5: Illustration of the Flow-Shop problem.

Algorithm 3

 3 Computation of lower bound (vectorized) input: subproblem = {permutation, nbFixed (#jobs fixed)}, constant data (MM, JM, PTM, LM) output: lower bound (LB) of subproblem 1: n := #jobs 2: procedure compute LB vectorized 3: RM, QM, SM ← InitTabs(permutation, nbFixed)

Figure 6 :

 6 Figure 6: Native-oriented many-core or multi-core B&B.

Figure 7 :

 7 Figure 7: Elapsed time vs. Number of IVMs for MIC-B&B in offload and native mode.

Figure 8 :

 8 Figure 8: Impact of multithreading on the performance of MIC-based approach

Figure 9 :

 9 Figure 9: Illustration of the irregular nature of the bounding function. Average elapsed time (1000000 evaluations) required for computing the lower bound for a subproblems according to its depth in the tree.

Figure 10 :

 10 Figure 10: Time spend in bounding, IVM-management and overhead.

Table 1 :

 1 Hardware execution platform

		Intel Xeon E5-2670 Intel Xeon-Phi 5110P
	#Physical cores	8	60
	#Logical cores	16	240
	clock(Ghz)	2.6	1.053
	GFLOPS(DP)	166	1011
	SIMD	256-bit	512-bit
	Cache(MB)	20	30
	Mem BW(GB/s)	51.2	320
	Watt	115	225

Table 2 :

 2 Exploration time (in seconds) obtained using the multi-core and MIC master-worker approach.

		Nodes	Xeon Phi offload	Xeon Phi native	Multi-core
	Inst.	(×10 6 )	No-Vect Vect	No-Vect Vect	No-Vect Vect
	21	41.4	1,137	535	1,410	629	1,599	1,103
	22	22.1	566	269	700	306	785	562
	23	140.8	3,756	1,705	4,643	2,007	5,307	3,709
	24	40.1	938	431	1,200	517	1,391	971
	25	41.4	1,144	570	1,400	641	1,603	1,069
	26	71.4	1,651	766	2,120	929	2,371	1,714
	27	57.1	1,342	559	1,699	668	1,982	1,372
	28	8.1	228	108	276	118	296	209
	29	6.8	183	84	218	91	241	173
	30	1.6	51	25	55	24	60	44
	AVG	43.1	1,100	505	1,372	593	1,564	1,092

Table 3 :

 3 Exploration time (in seconds) obtained using the vectorized multi-core and MIC master-worker and work pool approaches.

		Nodes Xeon Phi offload Vect Xeon Phi native Vect	Multi-core Vect
	Inst.	(×10 6 )	static	dynamic	static	dynamic	static dynamic
	21	41.4	535	501	629	520	1,103	843
	22	22.1	269	254	306	259	562	434
	23	140.8	1,705	1,608	2,007	1,673	3,709	2,862
	24	40.1	431	396	517	411	971	749
	25	41.4	570	540	641	559	1,069	834
	26	71.4	766	714	929	747	1,714	1,320
	27	57.1	559	524	668	545	1,372	1,083
	28	8.1	108	102	118	99	209	163
	29	6.8	84	80	91	78	173	133
	30	1.6	25	24	24	20	44	34
	AVG	43.1	505	474	593	491	1,092	845

MIC stands for Many Integrated CoresPreprint submitted to Future Generation Computer Systems December

[START_REF] Stanic | Evaluation of Vectorization Potential of Graph500 on Intel Xeon Phi[END_REF] 2016

An optimization problem consists of minimizing or maximizing a cost function. Without loss of generality, in this paper the minimization case and the permutation Flow-Shop scheduling problem are considered.

http://d3f8ykwhia686p.cloudfront.net/1live/intel/CompilerAutovectorizationGuide.pdf


Alok Arun

Susana M Coelho

Akira F Peters

Simon Bourdareau

Laurent Peres

Delphine Scornet

Martina Strittmatter

Agnieszka P Lipinska

Haiqin Yao

Olivier Godfroy

Gabriel J Montecinos

Komlan Avia

Nicolas Macaisne

Christelle Troadec

Abdelhafid Bendahmane

J Mark Cock
email: cock@sb-roscoff.fr

Convergent recruitment of life cycle regulators to direct sporophyte development in two eukaryotic supergroups

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Developmental processes need to be precisely coordinated with life cycle progression. This is particularly important in multicellular organisms with haploid-diploid life cycles, where two different developmental programs, corresponding to the sporophyte and gametophyte, need to be deployed appropriately at different time points within a single life cycle. In the unicellular green alga Chlamydomonas, plus and minus gametes express two different HD TFs of the three amino acid loop extension (TALE) family called Gsm1 and Gsp1 [START_REF] Lee | Early sexual origins of homeoprotein heterodimerization and evolution of the plant KNOX/BELL family[END_REF]. When two gametes fuse to form a zygote, these two proteins heterodimerise and move to the nucleus, where they orchestrate the diploid phase of the life cycle. Gsm1 and Gsp1 belong to the knottedlike homeobox (KNOX) and BEL TALE HD TF classes, respectively. In the multicellular moss Physcomitrella patens, deletion of two KNOX genes, MKN1 and MKN6, blocks initiation of the sporophyte program leading to conversion of this generation of the life cycle into a diploid gametophyte [START_REF] Sakakibara | KNOX2 genes regulate the haploid-to-diploid morphological transition in land plants[END_REF]. Similarly, the moss BEL class gene BELL1 is required for induction of the sporophyte developmental program and ectopic expression of BELL1 in gametophytic tissues induces the development of apogametic sporophytes during the gametophyte generation of the life cycle [START_REF] Horst | A single homeobox gene triggers phase transition, embryogenesis and asexual reproduction[END_REF]. In mosses, therefore, the KNOX and BEL class life cycle regulators have been recruited to act as master regulators of the sporophyte developmental program, coupling the deployment of this program with life cycle progression. P. patens KNOX and BEL proteins have been shown to form heterodimers [START_REF] Horst | A single homeobox gene triggers phase transition, embryogenesis and asexual reproduction[END_REF] and it is therefore possible that life cycle regulation also involves KNOX/BEL heterodimers in this species.

The filamentous alga Ectocarpus has emerged as a model system for the brown algae [START_REF] Cock | Emergence of Ectocarpus as a model system to study the evolution of complex multicellularity in the brown algae In[END_REF][START_REF] Coelho | Ectocarpus: A model organism for the brown algae[END_REF]. This alga has a haploid-diploid life cycle that involves alternation between multicellular sporophyte and gametophyte generations (Figure 1A). A mutation at the OUROBOROS (ORO) locus has been shown to cause the sporophyte generation to be converted into a fully functional (gamete-producing) gametophyte (Figure 1B) [START_REF] Coelho | OUROBOROS is a master regulator of the gametophyte to sporophyte life cycle transition in the brown alga Ectocarpus[END_REF]. This mutation therefore induces a phenotype that is essentially identical to that observed with the P. patens mkn1 mkn6 double mutant, but in an organism from a distinct eukaryotic supergroup (the stramenopiles), which diverged from the green lineage over a billion years ago [START_REF] Eme | On the age of eukaryotes: evaluating evidence from fossils and molecular clocks[END_REF].

Here we identify mutations at a second locus, SAMSARA, that also result in conversion of the sporophyte generation into a gametophyte. Remarkably, both OUROBOROS and SAMSARA encode TALE HD TFs and the two proteins associate to form a heterodimer. These observations indicate that TALE-HD-TF-based life cycle regulatory systems have very deep evolutionary origins and that they have been independently recruited in at least two eukaryotic supergroups to act as master regulators of sporophyte developmental programs.

Results

Two TALE homeodomain transcription factors direct sporophyte development

The ORO gene was mapped to a 34.5 kbp (0.45 cM) interval on chromosome 14 using a segregating family of 2000 siblings derived from an ORO x oro cross and a combination of amplified fragment length polymorphism (AFLP) [START_REF] Vos | AFLP: a new technique for DNA fingerprinting[END_REF] and microsatellite markers.

Resequencing of the 34.5 kbp interval in the oro mutant showed that it contained only one mutation: an 11 bp deletion in exon six of the gene with the LocusID Ec-14_005920, which encodes a TALE homeodomain transcription factor. (Figure 1C). A visual screen of about 14,000 UV-mutagenised germlings identified three additional life cycle mutants (designated samsara-1, samsara-2 and samsara-3, abbreviated as sam-1, sam-2 and sam-3). The sam mutants closely resembled the oro mutant in that gamete-derived parthenotes did not adopt the normal sporophyte pattern of development but rather resembled gametophytes. Young, germinating individuals exhibited the wavy pattern of filament growth typical of the gametophyte and, at maturity, never produced unilocular sporangia (the reproductive structures where meiosis occurs; Figure 1A), a structure that is uniquely observed during the sporophyte generation (Figure 2A-C-figure supplement 1). Moreover, the sam mutants exhibited a stronger negative phototrophic response to unilateral light than wild type sporophytes (Figure 2D), a feature typical of gametophytes [START_REF] Peters | Life-cycle-generation-specific developmental processes are modified in the immediate upright mutant of the brown alga Ectocarpus siliculosus[END_REF] that was also observed for the oro mutant [START_REF] Coelho | OUROBOROS is a master regulator of the gametophyte to sporophyte life cycle transition in the brown alga Ectocarpus[END_REF].

Genetic crosses confirmed that the sam mutants were fully functional (i.e. gamete-producing) gametophytes and complementation analysis indicated that they were not located at the same genetic locus as the oro mutation (Table supplement 1). Interestingly, hybrid sporophytes that were heterozygous for the sam mutations failed to produce functional unilocular sporangia.

Wild type unilocular sporangia contain about a hundred haploid meio-spores produced by a single meiotic division followed by several rounds of mitotic divisions, whereas unilocular sporangia of SAM/sam heterozygotes never contained more than four nuclei indicating that abortion was either concomitant with or closely followed meiosis (Figure 2F). This indicated either a dominant effect of the sam mutations in the fertile sporophyte or abortion of the sporangia due to arrested development of the two (haploid) meiotic daughter cells that carried the mutant sam allele. Ectocarpus sporophytes produce a diffusible factor that induces gametophyte initial cells or protoplasts of mature gametophyte cells to switch to the sporophyte developmental program [START_REF] Arun | Non-cell autonomous regulation of life cycle transitions in the model brown alga Ectocarpus[END_REF]. The oro mutant is not susceptible to this diffusible factor (oro protoplasts regenerate as gametophytes in sporophyte-conditioned medium) indicating that ORO is required for the diffusible factor to direct deployment of the sporophyte developmental pathway [START_REF] Arun | Non-cell autonomous regulation of life cycle transitions in the model brown alga Ectocarpus[END_REF]. We show here that the sam-1 mutant is also resistant to the action of the diffusible factor. Congo red staining of individuals regenerated from sam-1 protoplasts that had been treated with the diffusible factor detected no sporophytes, whereas control treatment of wild type gametophyte-derived protoplasts resulted in the conversion of 7.5% of individuals into sporophytes (Figure 2E-table supplement 2). Therefore, in order to respond to the diffusible factor, cells must possess functional alleles of both ORO and SAM.

The Ectocarpus genome contains two TALE HD TFs in addition to the ORO gene.

Resequencing of these genes in the three sam mutants identified three genetic mutations, all of which were predicted to severely affect the function of Ec-27_006660 (Figure 2G). The identification of three disruptive mutations in the same gene in the three independent sam mutants strongly indicates that these are the causative lesions. Ec-27_006660 was therefore given the gene name SAMSARA (SAM). ORO and SAM transcripts were most abundant in gametes (Figure 3A), consistent with a role in initiating sporophyte development following gamete fusion. Quantitative PCR experiments demonstrated that sporophyte and gametophyte marker genes [START_REF] Peters | Life-cycle-generation-specific developmental processes are modified in the immediate upright mutant of the brown alga Ectocarpus siliculosus[END_REF] were down-and up-regulated, respectively, in sam mutant lines (Figure 3B), as was previously demonstrated for the oro mutant [START_REF] Coelho | OUROBOROS is a master regulator of the gametophyte to sporophyte life cycle transition in the brown alga Ectocarpus[END_REF].

ORO and SAM regulate the expression of sporophyte generation genes

To investigate the genetic mechanisms underlying the switch from the gametophyte to the sporophyte program directed by the ORO and SAM genes, we characterised the gene expression networks associated with the two generations of the Ectocarpus life cycle. Comparative analysis of sporophyte and gametophyte RNA-seq data identified 1167 genes that were differentially regulated between the two generations (465 upregulated in the sporophyte and 702 upregulated in the gametophyte; Table supplement 3). The predicted functions of these generation-biased genes was analysed using a system of manually-assigned functional categories, together with analyses based on GO terms and KEGG pathways. The set of generation-biased genes was significantly enriched in genes belonging to two of the manuallyassigned categories: "Cell wall and extracellular" and "Cellular regulation and signalling" and for genes of unknown function (Figure 3C-table supplement 3). Enriched GO terms also included several signalling-and cell wall-associated terms and terms associated with membrane transport (Figure 3D-table supplement 4). The gametophyte-biased gene set was enriched for several cell signalling KEGG pathways whereas the sporophyte-biased gene set was enriched for metabolic pathways (Figure 3E-table supplement 5). We also noted that the generationbiased genes included 23 predicted transcription factors and ten members of the EsV-1-7 domain family (Table supplement 3) [START_REF] Macaisne | The Ectocarpus IMMEDIATE UPRIGHT gene encodes a member of a novel family of cysteine-rich proteins with an unusual distribution across the eukaryotes[END_REF]. The latter were significantly enriched in the sporophyte-biased gene set (c2 test p=0.001).

Both the sporophyte-biased and the gametophyte-biased datasets were enriched in genes that were predicted to encode secreted proteins (Fisher's Exact Test p=2.02e -8 and p=4.14e -6 , respectively; Table supplement 3). Analysis of GO terms associated with the secreted proteins indicated a similar pattern of enrichment to that observed for the complete set of generationbiased genes (terms associated with signalling, cell wall and membrane transport; Table supplement 4). Figure 3C illustrates the relative abundances of manually-assigned functional categories represented in the generation-biased genes predicted to encode secreted proteins.

The lists of differentially expressed genes identified by the above analysis were used to select 200 genes that showed strong differential expression between the sporophyte and gametophyte generations. The pattern of expression of the 200 genes was then analysed in the oro and sam mutants and a third mutant, immediate upright (imm), which does not cause switching between life cycle generations [START_REF] Macaisne | The Ectocarpus IMMEDIATE UPRIGHT gene encodes a member of a novel family of cysteine-rich proteins with an unusual distribution across the eukaryotes[END_REF], as a control. Figure 3F shows that mutation of either ORO or SAM leads to upregulation of gametophyte generation genes and downregulation of sporophyte generation genes, consistent with the switch from sporophyte to gametophyte phenotypic function. Moreover, oro and sam mutants exhibited similar patterns of expression but the patterns were markedly different to that of the imm mutant. Taken together with the morphological and reproductive phenotypes of the oro and sam mutants, this analysis supports the conclusion that ORO and SAM are master regulators of the gametophyte-tosporophyte transition.

The ORO and SAM proteins interact in vitro

HD TFs that act as life cycle regulators or mating type determinants often form heterodimeric complexes [START_REF] Banham | An N-Terminal Dimerization Domain Permits Homeodomain Proteins To Choose Compatible Partners and Initiate Sexual Development in the Mushroom Coprinus cinereus[END_REF][START_REF] Horst | A single homeobox gene triggers phase transition, embryogenesis and asexual reproduction[END_REF][START_REF] Hull | Sex-specific homeodomain proteins Sxi1alpha and Sxi2a coordinately regulate sexual development in Cryptococcus neoformans[END_REF][START_REF] Kämper | Multiallelic recognition: nonself-dependent dimerization of the bE and bW homeodomain proteins in Ustilago maydis[END_REF][START_REF] Lee | Early sexual origins of homeoprotein heterodimerization and evolution of the plant KNOX/BELL family[END_REF]. The ORO and SAM proteins were also shown to be capable of forming a stable heterodimer using an in vitro pull-down approach (Figure 4). Deletion analysis indicated that the interaction between the two proteins was mediated by their homeodomains.

Evolutionary origins and domain structure of the ORO and SAM genes

Analysis of sequence databases indicated that all brown algae possess three HD TFs, all of the TALE class, including orthologues of ORO and SAM (Figure 5A-table supplement 6).

Comparison of brown algal ORO and SAM orthologues identified conserved domains both upstream and downstream of the HDs in both ORO and SAM (Figure 5B,C-figure supplement 5). These domains do not correspond to any known domains in public domain databases and were not found in any other proteins in the public sequence databases. The HD was the only domain found in both the ORO and SAM proteins (Figure 5). To identify more distantly-related orthologues of ORO and SAM, we searched a broad range of stramenopile TALE HD TFs for the presence of characteristic ORO and SAM protein domains. Only one non-brown-algal protein, from the raphidophyte Heterosigma akashiwo, possessed similarity to these domains, allowing it to be classed tentatively as an ORO orthologue (gene identifier 231575mod; Figure 5A,C-table supplement 6). The transcriptome of this strain also included a truncated TALE HD TF transcript similar to SAM but more complete sequence data will be required to confirm orthology with SAM (gene identifier 296151; Figure 5A-table supplement 6). This analysis allowed the origin of ORO to be traced back to the common ancestor with the raphidophytes (about 360 Mya; [START_REF] Brown | A molecular genetic timescale for the diversification of autotrophic stramenopiles (Ochrophyta): substantive underestimation of putative fossil ages[END_REF] but the rate of divergence of the non-HD regions of ORO and SAM precluded the detection of more distantly related orthologues. An additional search based on looking for TALE HD TF genes with intron positions corresponding to those of ORO and SAM did not detect any further orthologues (Figure supplement 3).

Discussion

The analysis presented here demonstrates that two TALE HD TFs, which are capable of forming a heterodimer, are required for the deployment of the sporophyte program during the life cycle of the brown alga Ectocarpus. The parallels with life cycle regulation in the green lineage, where TALE HD TFs have also been shown to regulate deployment of the sporophyte program [START_REF] Horst | A single homeobox gene triggers phase transition, embryogenesis and asexual reproduction[END_REF][START_REF] Sakakibara | KNOX2 genes regulate the haploid-to-diploid morphological transition in land plants[END_REF], are striking. Knockout of the KNOX class TALE HD TF genes MKN1 and MKN6 in Physcomitrella patens result in conversion of the sporophyte generation into a functional gametophyte [START_REF] Sakakibara | KNOX2 genes regulate the haploid-to-diploid morphological transition in land plants[END_REF], essentially the same phenotype as that observed with Ectocarpus oro or sam mutants despite the fact that more than a billion years of evolution separate the two lineages [START_REF] Eme | On the age of eukaryotes: evaluating evidence from fossils and molecular clocks[END_REF] and that the two lineages independently evolved complex multicellularity. The similarities between life cycle regulators in the two eukaryotic supergroups suggests that they are derived from a common ancestral system that would therefore date back to early eukaryotic evolution. The ancient origin of this life cycle regulatory system is supported by the fact that distantly-related homeodomain or homeodomain-like proteins act as mating type factors in both fungi and social amoebae [START_REF] Hedgethorne | Homeodomain-like DNA binding proteins control the haploid-to-diploid transition in Dictyostelium[END_REF][START_REF] Hull | Sex-specific homeodomain proteins Sxi1alpha and Sxi2a coordinately regulate sexual development in Cryptococcus neoformans[END_REF][START_REF] Nasmyth | Transcriptional regulation in the yeast life cycle[END_REF][START_REF] Van Heeckeren | The mating-type proteins of fission yeast induce meiosis by directly activating mei3 transcription[END_REF]. It has been proposed that the ancestral function of this homeodomain-based life cycle regulators was to detect syngamy and to implement processes specific to the diploid phase of the life cycle such as repressing gamete formation and initiating meiosis (Perrin, 2012 and references therein). With the emergence of complex, multicellular organisms, it would not have been surprising if additional processes such as developmental networks had come under the control of these regulators as this would have ensured that those developmental processes were deployed at the appropriate stage of the life cycle [START_REF] Cock | Evolution and regulation of complex life cycles: a brown algal perspective[END_REF]. Indeed, it has been suggested that modifications to homeodomain-based regulatory circuits may have played an important role in the emergence of sporophyte complexity in the green lineage [START_REF] Bowman | Evolution in the Cycles of Life[END_REF][START_REF] Lee | Early sexual origins of homeoprotein heterodimerization and evolution of the plant KNOX/BELL family[END_REF]. Key events may have included the replacement of the Gsp1-like class of BELL-related1 genes with alternative (true BEL-class) proteins and diversification of both the true BELL-class and the KNOX-class TALE HD TFs. In particular, the emergence and subfunctionalisation of two KNOX subfamilies early in streptophyte evolution is thought to have facilitated the evolution of more complex sporophyte transcriptional networks [START_REF] Furumizu | Antagonistic roles for KNOX1 and KNOX2 genes in patterning the land plant body plan following an ancient gene duplication[END_REF][START_REF] Sakakibara | KNOX2 genes regulate the haploid-to-diploid morphological transition in land plants[END_REF]. In the brown algae, ORO and SAM also function as major developmental regulators but, in this lineage, the emergence of a multicellular sporophyte has not been associated with a marked expansion of the TALE HD TF family. However, there does appear to have been considerable divergence of the ORO and SAM protein sequences during brown algal evolution, perhaps reflecting the evolution of new functions associated with multicellular development and divergence of the sporophyte and gametophyte developmental programs. Heterodimerisation appears to be a conserved feature of brown algal and green lineage TALE HD TFs (Figure 4 and [START_REF] Lee | Early sexual origins of homeoprotein heterodimerization and evolution of the plant KNOX/BELL family[END_REF] despite the lack of domain conservation.

However, in Ectocarpus heterodimerisation involves the ORO and SAM HDs whereas in

Chlamydomonas, it is the KNOX1 and KNOX2 domains of Gsm1 that interact with the Cterminal region of Gsp1 (which includes the HD, Ala and DE domains).

Interestingly, diploid sporophytes heterozygous for sam mutations exhibited abortive development of unilocular sporangia at a stage corresponding to the meiotic division of the mother cell. At first sight it might seem surprising that a gene should play an important role both directly following the haploid to diploid transition (initiation of sporophyte development) and at the opposite end of the life cycle, during the diploid to haploid transition (meiosis).

However, these phenotypes make more sense when viewed from an evolutionary perspective, if the ORO SAM system originally evolved as a global regulator of diploid phase processes.

There is now accumulating evidence for an ancient role for HD TFs in life cycle regulation in both the bikont and unikont branches of the eukaryotic tree of life [START_REF] Hedgethorne | Homeodomain-like DNA binding proteins control the haploid-to-diploid transition in Dictyostelium[END_REF][START_REF] Horst | A single homeobox gene triggers phase transition, embryogenesis and asexual reproduction[END_REF][START_REF] Hull | Sex-specific homeodomain proteins Sxi1alpha and Sxi2a coordinately regulate sexual development in Cryptococcus neoformans[END_REF][START_REF] Lee | Early sexual origins of homeoprotein heterodimerization and evolution of the plant KNOX/BELL family[END_REF]Sakakibara et al., 2013 and this study). We show here that these systems have been adapted to coordinate life cycle progression and development in at least two multicellular eukaryotic lineages (land plants and brown algae).

The recruitment of TALE HD TFs as sporophyte program master regulators in both the brown and green lineages represents a particularly interesting example of latent homology, where the shared ancestral genetic toolkit constrains the evolutionary process in two diverging lineages leading to convergent evolution of similar regulatory systems [START_REF] Nagy | Latent homology and convergent regulatory evolution underlies the repeated emergence of yeasts[END_REF]. The identification of such constraints through comparative analysis of independent complex multicellular lineages provides important insights into the evolutionary processes underlying the emergence of complex multicellularity. One particularly interesting outstanding question is whether HD TFs also play a role in coordinating life cycle progression and development in animals? Analysis of the functions of TALE HD TFs in unicellular relatives of animals may help provide some insights into this question.

Materials and Methods

Treatment with the sporophyte-produced diffusible factor

Sporophyte-conditioned medium, gametophyte-conditioned medium and protoplasts were produced as previously described [START_REF] Arun | Non-cell autonomous regulation of life cycle transitions in the model brown alga Ectocarpus[END_REF]. Protoplasts were allowed to regenerate either in sporophyte-conditioned medium supplemented with osmoticum or in gametophyteconditioned supplemented with osmoticum as a control. Congo red staining was used to distinguish sporophytes from gametophytes [START_REF] Arun | Non-cell autonomous regulation of life cycle transitions in the model brown alga Ectocarpus[END_REF]. At least 60 individuals were scored per treatment per experiment. Results are representative of three independent experiments.

Mapping of genetic loci

The oro mutation has been shown to behave as a single-locus, recessive, Mendelian factor [START_REF] Coelho | OUROBOROS is a master regulator of the gametophyte to sporophyte life cycle transition in the brown alga Ectocarpus[END_REF]. AFLP analysis was carried out essentially as described by [START_REF] Vos | AFLP: a new technique for DNA fingerprinting[END_REF]. DNA was extracted from 50 wild type and 50 oro individuals derived from a cross between the outcrossing line Ec568 [START_REF] Heesch | A sequence-tagged genetic map for the brown alga Ectocarpus siliculosus provides large-scale assembly of the genome sequence[END_REF] and the oro mutant Ec494 [START_REF] Coelho | OUROBOROS is a master regulator of the gametophyte to sporophyte life cycle transition in the brown alga Ectocarpus[END_REF]Table supplement 1). Equal amounts of DNA were combined into two pools, for bulk segregant analysis. Pre-selective amplification was carried out with an EcoRI-anchored primer and an MseI-anchored primer, each with one selective nucleotide, in five different combinations (EcoRI+T / MseI+G; EcoRI+T / MseI+A; EcoRI+C / MseI+G; EcoRI+C / MseI+A; EcoRI+A / MseI+C). These reactions were diluted 1:150 for the selective amplifications. The selective amplifications used an EcoRI-anchored primer and an MseI-anchored primer, each with three selective nucleotides, in various different combinations. The PCR conditions for both steps were 94°C for 30 sec, followed by 20 cycles of DNA amplification (30 sec at 94°C, 1 min at 56°C and 1 min at 72°C) and a 5 min incubation at 72°C except that this protocol was preceded by 13 touchdown cycles involving a decrease of 0.7°C per cycle for the selective amplifications.

PCR products were analysed on a LI-COR apparatus. This analysis identified two flanking AFLP markers located at 20.3 cM and 21.1 cM on either side of the ORO locus. For 23 (12 oro and 11 wild type) of the 100 individuals, no recombination events were detected within the 41.4 cM interval between the two markers. Screening of these 23 individuals (11 wild type and 12 oro) with the microsatellite markers previously developed for a sequence-anchored genetic map [START_REF] Heesch | A sequence-tagged genetic map for the brown alga Ectocarpus siliculosus provides large-scale assembly of the genome sequence[END_REF] identified one marker within the 41.4 cM interval (M_512) and located the ORO locus to near the bottom of chromosome 14 [START_REF] Cormier | Re-annotation, improved large-scale assembly and establishment of a catalogue of noncoding loci for the genome of the model brown alga Ectocarpus[END_REF].

Fine mapping employed a segregating population of 2,000 individuals derived from the cross between the oro mutant line (Ec494) and the outcrossing line Ec568 and an additional 11 microsatellite markers within the mapping interval (Table supplement 7) designed based on the Ectocarpus genome sequence [START_REF] Cock | The Ectocarpus genome and the independent evolution of multicellularity in brown algae[END_REF]. PCR reactions contained 5 ng of template DNA, 1.5 µl of 5xGoTaq reaction buffer, 0.25 units of GoTaq-polymerase (Promega), 10 nmol MgCl 2 , 0.25 µl of dimethyl sulphoxide, 0.5 nmol of each dNTP, 2 pmol of the reverse primer, 0.2 pmol of the forward primer (which included a 19-base tail that corresponded to a nucleotide sequence of the M13 bacteriophage) and 1.8 pmol of the fluorescence marked M13 primer. The PCR conditions were 94°C for 4 min followed by 13 touch-down cycles (94°C for 30 sec, 65-54°C for 1 min and 72°C for 30 sec) and 25 cycles at 94°C for 30 sec, 53°C for 1 min and 72°C for 30 sec. Samples were genotyped by electrophoresis on an ABI3130xl Genetic Analyser (Applied Biosystems) and analysis with Genemapper version 4.0 (Applied Biosystems). Using the microsatellite markers, the oro mutation was mapped to a 34.5 kbp (0.45 cM) interval, which contained five genes. Analysis of an assembled, complete genome sequence for a strain carrying the oro mutation (strain Ec597; European Nucleotide Archive PRJEB1869; [START_REF] Ahmed | A Haploid System of Sex Determination in the Brown Alga Ectocarpus sp[END_REF] together with Sanger method resequencing of ambiguous regions demonstrated that there was only one mutation within the mapped interval: an 11 bp deletion in the gene with the LocusID Ec-14_005920. Comparison of the reference genome (strain Ec32) supercontig that contains the SAM gene (sctg_251) with homologous supercontigs from several independently assembled draft genome sequences corresponding to closely related Ectocarpus sp. strains [START_REF] Ahmed | A Haploid System of Sex Determination in the Brown Alga Ectocarpus sp[END_REF][START_REF] Cormier | Re-annotation, improved large-scale assembly and establishment of a catalogue of noncoding loci for the genome of the model brown alga Ectocarpus[END_REF] indicated that sctg_251 was chimeric and that the first three exons of the SAM gene were missing. The complete SAM gene was therefore assembled and has been submitted to Genbank under the accession number KU746823.

Quantitative reverse transcriptase polymerase chain reaction analysis of mRNA abundance

Total RNA was extracted from wild-type gametophytes and partheno-sporophytes (Ec32) and from sam-1 (Ec374) and sam-2 (Ec364) partheno-gametophytes using the Qiagen RNeasy Plant mini kit and any contaminating DNA was removed by digestion with Ambion Turbo DNase (Life Technologies). The generation marker genes analysed were Ec-20_001150 and Ec-26_000310 (sporophyte markers), and Ec-23_004240 and Ec-21_006530 (gametophyte markers), which are referred to as IDW6, IDW7, IUP2 and IUP7 respectively, in [START_REF] Peters | Life-cycle-generation-specific developmental processes are modified in the immediate upright mutant of the brown alga Ectocarpus siliculosus[END_REF]. Following reverse transcription of 50-350 ng total RNA with the ImPro II TM Reverse Transcription System (Promega), quantitative RT-PCR was performed on LightCycler® 480 II instrument (Roche). Reactions were run in 10 µl containing 5 ng cDNA, 500nM of each oligo and 1x LightCycler® 480 DNA SYBR Green I mix (Roche). The sequences of the oligonucleotides used are listed in Table supplement 8. Pre-amplification was performed at 95°C for 5 min, followed by the amplification reaction consisting of 45 cycles of 95°C for 10 sec, 60°C for 30 sec and 72°C for 15 sec with recording of the fluorescent signal after each cycle. Amplification specificity and efficiency were checked using a melting curve and a genomic DNA dilution series, respectively, and efficiency was always between 90% and 110%. Data were analysed using the LightCycler® 480 software (release 1.5.0). A pair of primers that amplified a fragment which spanned intron 2 of the SAM gene was used to verify that there was no contaminating DNA (Table supplement 8). Standard curves generated from serial dilutions of genomic DNA allowed quantification for each gene. Gene expression was normalized against the reference gene EEF1A2. Three technical replicates were performed for the standard curves and for each sample. Statistical analysis (Kruskal-Wallis test and Dunn's Multiple Comparison Post Test) was performed using the software GraphPadPrism5.

RNA-seq analysis

RNA for RNA-seq analysis was extracted from duplicate samples (two biological replicates) of approximately 300 mg (wet weight) of tissue either using the Qiagen RNeasy plant mini kit with an on-column Deoxyribonuclease I treatment or following a modified version [START_REF] Peters | Life-cycle-generation-specific developmental processes are modified in the immediate upright mutant of the brown alga Ectocarpus siliculosus[END_REF] of the protocol described by [START_REF] Apt | The gene family encoding the fucoxanthin chlorophyll proteins from the brown alga Macrocystis pyrifera[END_REF]. Briefly, this second protocol involved extraction with a cetyltrimethylammonium bromide (CTAB)-based buffer and subsequent phenol-chloroform purification, LiCl-precipitation, and DNAse digestion (Turbo DNAse, Ambion, Austin, TX, USA) steps. RNA quality and concentration was then analysed on 1.5% agarose gel stained with ethidium bromide and a NanoDrop ND-1000 spectrophotometer (NanoDrop products, Wilmington, DE, USA). Between 21 and 93 million sequence reads were generated for each sample on an Illumina Hi-seq2000 platform (Table supplement 9). Raw reads were quality trimmed with Trimmomatic (leading and trailing bases with quality below 3 and the first 12 bases were removed, minimum read length 50 bp) [START_REF] Bolger | Trimmomatic: a flexible trimmer for Illumina sequence data[END_REF]. High score reads were aligned to the Ectocarpus reference genome [START_REF] Cock | The Ectocarpus genome and the independent evolution of multicellularity in brown algae[END_REF]available at Orcae;[START_REF] Sterck | ORCAE: online resource for community annotation of eukaryotes[END_REF] using Tophat2 with the Bowtie2 aligner [START_REF] Kim | TopHat2: accurate alignment of transcriptomes in the presence of insertions, deletions and gene fusions[END_REF]. The mapped sequencing data was then processed with HTSeq [START_REF] Anders | HTSeq -A Python framework to work with highthroughput sequencing data[END_REF] to obtain counts for sequencing reads mapped to exons. Expression values were represented as TPM and TPM>1 was applied as a filter to remove noise. Differential expression was detected using the DESeq2 package (Bioconductor; [START_REF] Love | Moderated estimation of fold change and dispersion for RNA-seq data with DESeq2[END_REF] using an adjusted p-value cut-off of 0.05 and a minimal fold-change of two. Heatmaps were generated using the Heatplus package for R [START_REF] Ploner | Heatplus: Heatmaps with row and/or column covariates and colored clusters[END_REF] and colour schemes selected from the ColorBrewer project (http://colorbrewer.org).

The entire set of 16,724 protein-coding genes in the Ectocarpus Ec32 genome were manually assigned to one of 22 functional categories (Table supplement 10) and this information was used to determine whether sets of differentially expressed genes were enriched in particular functional categories compared to the entire nuclear genome (c 2 test). Blast2GO [START_REF] Conesa | Blast2GO: A comprehensive suite for functional analysis in plant genomics[END_REF] was used to detect enrichment of GO-terms associated with the genes that were consistently up-or downregulated in pairwise comparisons of the wild type gametophyte, the sam mutant and the oro mutant with the wild type sporophyte. Significance was determined using a Fisher exact test with an FDR corrected p-value cutoff of 0.05. Sub-cellular localisations of proteins were predicted using Hectar [START_REF] Gschloessl | HECTAR: a method to predict subcellular targeting in heterokonts[END_REF]. Sets of secreted proteins corresponded to those predicted to possess a signal peptide or a signal anchor.

Detection of protein-protein interactions

Pull-down assays were carried out using the MagneGST TM Pull-Down System (Promega, Madison, WI) by combining human influenza hemagglutinin (HA)-tagged and glutathione Stransferase (GST) fusion proteins. In vitro transcription/translation of HA-tagged ORO proteins was carried out using the TNT Ò Coupled Wheat Germ Extract System (Promega, Madison, WI). GST-tagged SAM proteins were expressed in Escherichia coli. Protein production was induced by adding IPTG to a final concentration of 2mM and shaking for 20 h at 16°C. After the capture phase, beads were washed four times with 400 µL of washing buffer (0.5% IGEPAL, 290 mM NaCl, 10 mM KCl, 4.2 mM Na 2 HPO 4 , 2 mM KH 2 PO 4 , at pH 7.2) at room temperature. Beads were then recovered in SDS-PAGE loading buffer, and proteins analysed by SDS-PAGE followed by Clarity TM chemiluminescent detection (Biorad, Hercules, CA). The anti-HA antibody (3F10) was purchased from Roche, and the anti-GST antibody (91G1) from Ozyme.

Searches for HD proteins from other stramenopile species

Searches for homeodomain proteins from additional brown algal or stramenopile species were carried out against the NCBI, Uniprot, oneKP [START_REF] Matasci | Data access for the 1,000 Plants (1KP) project[END_REF] and iMicrobe databases and against sequence databases for individual brown algal (Saccharina japonica, [START_REF] Ye | Saccharina genomes provide novel insight into kelp biology[END_REF]Cladosiphon okamuranus, Nishitsuji et al., 2016) and stramenopile genomes (Nannochloropsis oceanica, Aureococcus anophagefferens, Phaeodactylum tricornutum, Thalassiosira pseudonana, Pseudo-nitzschia multiseries) and transcriptomes (Vaucheria litorea, Heterosigma akashiwo) using both Blast (Blastp or tBlastn) and HMMsearch with a number of different alignments of brown algal TALE HD TF proteins. As the homeodomain alone does not provide enough information to construct well-supported phylogenetic trees, searches for ORO and SAM orthologues were based on screening for the presence of the additional protein domains conserved in brown algal ORO and SAM proteins.

As intron position and phase was strongly conserved between the homeoboxes of ORO and SAM orthologues within the brown algae, this information was also used to search for ORO and SAM orthologues in other stramenopile lineages. However, this analysis failed to detect any additional candidate ORO or SAM orthologues. These observations are consistent with a similar analysis of plant homeobox introns, which showed that intron positions were strongly conserved in recently diverged classes of homeobox gene but concluded that homeobox introns were of limited utility to deduce ancient evolutionary relationships [START_REF] Mukherjee | A comprehensive classification and evolutionary analysis of plant homeobox genes[END_REF].

GenomeView [START_REF] Abeel | GenomeView: a nextgeneration genome browser[END_REF] was used together with publically available genome and RNA-seq sequence data [START_REF] Nishitsuji | A draft genome of the brown alga, Cladosiphon okamuranus, S-strain: a platform for future studies of "mozuku" biology[END_REF][START_REF] Ye | Saccharina genomes provide novel insight into kelp biology[END_REF] to improve the gene models for some of the brown algal TALE HD TFs (indicated in Table supplement 6 by adding the suffix "mod" for modified to the protein identifier).

Phylogenetic analysis and protein analysis and comparisons

Multiple alignments were generated with Muscle in MEGA7 [START_REF] Tamura | MEGA5: molecular evolutionary genetics analysis using maximum likelihood, evolutionary distance, and maximum parsimony methods[END_REF].

Phylogenetic trees were then generated with RAxML [START_REF] Stamatakis | Using RAxML to Infer Phylogenies[END_REF] using 1000 bootstrap replicates and the most appropriate model based on an analysis in MEGA7. Domain alignments were constructed in Jalview (http://www.jalview.org/) and consensus sequence logos were generated with WebLogo (http://weblogo.berkeley.edu/logo.cgi). Intrinsic disorder in protein folding was predicted using SPINE-D [START_REF] Zhang | SPINE-D: accurate prediction of short and long disordered regions by a single neural-network based method[END_REF], low complexity regions with SEG (default parameters, 12 amino acid window; [START_REF] Wootton | Non-globular domains in protein sequences: automated segmentation using complexity measures[END_REF] and secondary structure with PSIPRED [START_REF] Buchan | Scalable web services for the PSIPRED Protein Analysis Workbench[END_REF].

Figure 1 .

 1 Figure 1. The oro life cycle mutation corresponds to a TALE homeodomain transcription factor gene. (A) Life cycle of wild type and oro mutant Ectocarpus. The wild type sexual cycle (upper panel) involves production of meio-spores by the diploid sporophyte via meiosis in unilocular (single-chambered) sporangia (US). The meio-spores develop as haploid, dioecious (male and female) gametophytes. The gametophytes produce gametes in plurilocular gametangia (PG), which fuse to produce a diploid sporophyte. Gametes that fail to fuse can develop parthenogenetically to produce a partheno-sporophyte, which can produce spores by apomeiosis or following endoreduplication to engender a new

Figure 2 .

 2 Figure 2. Phenotypic and genetic characterisation of sam life cycle mutants. (A-C) The sam-1 mutant exhibits gametophyte-like morphological characteristics. Different stages of (A) wild type gametophyte (strain Ec32), (B) wild type partheno-sporophyte (strain Ec32) and (C) sam-1 mutant (strain Ec374). PG, plurilocular gametangia; PS, plurilocular sporangium; US, unilocular sporangium. (D) sam mutants exhibit a gametophyte-like photopolarisation response to unidirectional light. Letters above the boxplot indicate

Figure 3 .

 3 Figure 3. Gene expression analysis. (A) Abundance of ORO and SAM transcripts during different stages of the life cycle. Error bars, standard error of the mean (SEM); TPM: transcripts per million. (B) Quantitative reverse transcription PCR analysis of generation marker genes. The graphs indicate mean values ± standard error of transcript abundances for two gametophyte marker genes, Ec-23_004240 and Ec-21_006530, and two sporophyte marker genes, Ec-20_001150 and Ec-26_000310. Data from five independent

Figure 4 .Figure 5 .

 45 Figure 4. Detection of ORO-SAM heterodimerisation in vitro using a pull-down assay. (A) ORO and SAM constructs used for the pull-down experiments. (B) Pull-down assay between SAM and different versions of the ORO protein. (C) Pull-down assay between different versions of the SAM protein and full-length ORO protein. Note that all ORO proteins were fused with the HA epitope. FL, full-length; HD, homeodomain.

  Reconstruction and sequence correction of the ORO and SAM loci The sequence of the 34.5 kbp mapped interval containing the ORO gene (chromosome 27, 5463270-5497776) in the wild type Ectocarpus reference strain Ec32 included one short region of uncertain sequence 1026 bp downstream of the end of the ORO open reading frame. The sequence of this region was completed by PCR amplification and Sanger sequencing and confirmed by mapping Illumina read data to the corrected region. The corrected ORO gene region has been submitted to Genbank under the accession number KU746822.

Acknowledgements

We thank the ABiMS platform (Roscoff Marine Station) for providing computing facilities and support.

Funding

This work was supported by the Centre National de la Recherche Scientifique; Agence Nationale de la Recherche (project Bi-cycle ANR-10-BLAN-1727, project Idealg ANR-10-BTBR-04-01 and project Saclay Plant Sciences (SPS), ANR-10-LABX-40); Interreg Program France (Channel)-England (project Marinexus); the University Pierre et Marie Curie and the European Research Council (SexSea grant agreement 638240 and ERC-SEXYPARTH). A.A. and H.Y. were supported by a fellowship from the European Erasmus Mundus program and the China Scholarship Council, respectively.

Additional information

Competing interests

The authors have no competing interests.

Additional files

Supplementary files

Supplementary notes

Supplementary Figure 1. Morphological characteristics and response to unidirectional light of sam mutants. Supplementary Figure 2. Evidence for the production of full-length ORO and SAM transcripts during the gametophyte generation. [START_REF] Sakakibara | KNOX2 genes regulate the haploid-to-diploid morphological transition in land plants[END_REF]Sakakibara et al., , 2008)). However, no phenotypes were detected during the haploid protonema or gametophore stages in KNOX mutant lines [START_REF] Sakakibara | KNOX2 genes regulate the haploid-to-diploid morphological transition in land plants[END_REF](Sakakibara et al., , 2008;;Singer and Ashton, 2007) and the RT-PCR only amplified certain regions of the transcripts.

Consequently, these results have been interpreted as evidence for the presence of partial transcripts during the gametophyte generation. To determine whether the ORO and SAM transcripts produced in Ectocarpus were incomplete, RNA-seq data from male and female, immature and mature gametophytes was mapped onto the ORO and SAM gene sequences. This analysis indicated that full-length transcripts of both the ORO and SAM genes are produced during the gametophyte generation (Figure supplement 2).

ORO and SAM domain structure

The conserved domains that flank the homeodomains in the ORO and SAM proteins share no detectable similarity with domains that are associated with TALE HDs in the green (Viridiplantae) lineage, such as the KNOX, ELK and BEL domains. Interestingly, both the ORO and SAM proteins possess regions that are predicted to be highly disordered (Figure supplement 5B). Intrinsically disordered region are a common feature in transcription factors and the flexibility conferred by these regions is thought to allow them to interact with a broad range of partners (Niklas et al., 2015), a factor that may be important for master developmental regulators such as the ORO and SAM proteins.

Stramenopile TALE HD TFs

All the stramenopile species analysed in this study possessed at least two TALE HD TFs, with some species possessing as many as 14 (Table supplement 6). Note that genomes of several diverse stramenopile lineages outside the brown algae were predicted to encode proteins with more than one HD (Table supplement 6

Supplementary tables

See separate Excel file.

Supplementary references