Tiago Carneiro
email: tiago.carneiro@ppgcc.ifce.edu.br

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

Nouredine Melab
email: nouredine.melab@univ-lille1.fr

Francisco Heron De Carvalho Junior

P P Rebouças Filho

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

Dynamic Configuration of CUDA Runtime Variables for CDP-based Divide-and-Conquer Algorithms

Keywords: CUDA dynamic parallelism, Backtracking, Divide-and-conquer

CUDA Dynamic Parallelism (CDP) is an extension of the GPGPU programming model proposed to better address irregular applications and recursive patterns of computation. However, processing memory demanding problems by using CDP is not straightforward, because of its particular memory organization. This work presents an algorithm to deal with such an issue. It dynamically calculates and configures the CDP runtime variables and the GPU heap on the basis of an analysis of the partial backtracking tree. The proposed algorithm was implemented for solving permutation combinatorial problems and experimented on two test-cases: N-Queens and the Asymmetric Travelling Salesman Problem. The proposed algorithm allows different CDP-based backtracking from the literature to solve memory demanding problems, adaptively with respect to the number of recursive kernel generations and the presence of dynamic allocations on GPU.

Introduction

Irregular applications are present in different research fields, such as combinatorial optimization, data mining, and simulations [START_REF] Wang | Characterization and analysis of dynamic parallelism in unstructured GPU applications[END_REF]. The difficulty of parallelizing an application is closely related to its degree of irregularity [START_REF] Mukherjee | Efficient support for irregular applications on distributed-memory machines[END_REF]. Applications that present irregular control structure, irregular data structures, and irregular pattern of communication are notably difficult to parallelize [START_REF] Yelick | Programming models for irregular applications[END_REF]. Unstructured tree search methods for solving combinatorial problems, such as backtracking and branch-and-bound, are examples of such applications. These problem solver paradigms are present in many different areas, e.g., combinatorial optimization, artificial intelligence, and operations research [START_REF] Gendron | Parallel branch-and-bound algorithms: Survey and synthesis[END_REF]. The program model usually applied to parallelize backtracking algorithms for GPUs, allied to characteristics of the problems commonly solved, results in fine-grained and irregular workloads, which is detrimental to the performance of the GPU.

Although GPUs suffer from performance degradation while processing irregular applications, they are still attractive accelerators. They are ubiquitous, energy efficient, and deliver a high price/GFLOP rate [START_REF] Brodtkorb | State-of-the-art in heterogeneous computing[END_REF]. Furthermore, GPU programming interfaces and tools have become more flexible and expressive. Recent extensions to the general-purpose graphics processing unit (GPGPU) programming model, such as CUDA dynamic parallelism (CDP), can raise the expressiveness of the GPGPU programming model, making it possible to better address irregular applications and recursive patterns of computation [START_REF] Adinetz | CUDA dynamic parallelism: API and principles[END_REF], such as divide-and-conquer, used by backtracking algorithms. Despite CDP's purpose of better coping with recursive computations, it is not straightforward to use this technology for processing memory demanding problems [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF]. CDP presents several hardware limitations and a different memory organization [START_REF] Adinetz | CUDA dynamic parallelism: API and principles[END_REF][START_REF][END_REF]: it is required to configure the CUDA runtime to reserve memory for synchronization between kernel generations. Moreover, in case of dynamic allocations on GPU, it is also necessary to configure the GPU heap size. Both GPU heap and memory for synchronization are not available for use. The related work on CDP does not address these issues.

This work presents an algorithm that dynamically calculates and configures the CDP runtime requirements and the GPU heap size. This calculus is based on an analysis of the partial backtracking tree. The proposed algorithm was implemented for solving permutation combinatorial problems, experimented on two test-cases: N-Queens and the Asymmetric Travelling Salesman Problem. The proposed algorithm allows different CDP-based backtracking from the literature to solve memory demanding problems, autonomously with respect to the number of recursive kernel generations and the presence of dynamic allocations on GPU.

The remainder of this paper is structured as follows. Section 2 brings background information and related works. Section 3 presents the proposed algorithm, and Section 4 brings the performance evaluation. Finally, conclusions and directions for further investigations are outlined in Section 5.

Background and Related Works

N-Queens and ATSP

The Traveling Salesman Problem (TSP) consists in finding the shortest Hamiltonian cycle(s) through a given number of cities in such a way that each city is visited exactly once. For each pair of cities (i, j) a cost c ij is given by a cost matrix C N ×N . The TSP is called symmetric if the cost matrix is symmetric (∀i, j : c ij = c ji ), and asymmetric otherwise (ATSP). Due to its relevance, the TSP is often used as a benchmark for novel problem-solving strategies [START_REF] Cook | In pursuit of the traveling salesman: mathematics at the limits of computation[END_REF].

The ATSP instances used in this work come from a generator that creates instances based on real-world situations [START_REF] Cirasella | The asymmetric traveling salesman problem: Algorithms, instance generators, and tests[END_REF]. Three classes of instances have been selected: crane, modeling stacker crane operations; coin, modeling a person collecting money from pay phones in a grid-like city; and tsmat, consisting of asymmetric instances where the triangle inequality holds. Each class of instances has its own characteristics. Hence, two instances of the same size N may result in a different behavior for the same algorithm.

The N-Queens problem consists in placing N non-attacking queens on a N × N chessboard. It is also often used as a benchmark for new GPU-based backtracking strategies [START_REF] Plauth | A performance evaluation of dynamic parallelism for fine-grained, irregular workloads[END_REF][START_REF] Zhang | Optimization of N-Queens solvers on graphics processors[END_REF]. We consider the version of N-Queens that consists in finding all feasible board configurations. N-Queens can be modeled as a permutation problem: position r of a permutation of size N designates the column in which a queen is placed in row r.

CUDA Dynamic Parallelism Programming Model

In the CDP terminology, the thread that launches a new kernel is called parent. The grid, kernel, and block to which this thread belongs are also called parents. The launched grid is called child. The launch of a child grid is non-blocking, but the parent grid only finishes its execution after the termination of all child grids. Inside a block, different kernel launches are serialized. To avoid serialization of kernel launches, the programmer must link each kernel launch to a different stream [START_REF][END_REF]. Concerning the memory model, blocks of a child grid also have shared memory, and child threads also have local and register memories. A Child grid is not aware of its parent context data, and a parent thread should not pass to child threads pointers to its local or shared memories. Thus, the communication between parent and child is performed through global memory.

Related Works on CUDA Dynamic Parallelism

The parallelization of irregular applications using CDP has received little attention in the literature. Particularly, CDP has been used for processing graphs, clustering, simulations, and backtracking algorithms [START_REF] Wang | Characterization and analysis of dynamic parallelism in unstructured GPU applications[END_REF][START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF][START_REF] Plauth | A performance evaluation of dynamic parallelism for fine-grained, irregular workloads[END_REF][START_REF] Zhang | Dynamic parallelism for simple and efficient GPU graph algorithms[END_REF][START_REF] Dimarco | Performance impact of dynamic parallelism on different clustering algorithms and the new GPU architecture[END_REF]. According to related works, CDP is beneficial for processing applications whose data are hierarchically arranged. In such situations, the use of CDP results in performance gains and a code closer to the high-level description of the algorithm [START_REF] Zhang | Dynamic parallelism for simple and efficient GPU graph algorithms[END_REF][START_REF] Dimarco | Performance impact of dynamic parallelism on different clustering algorithms and the new GPU architecture[END_REF]. However, when these requirements are not met, using CDP may result in significant overheads and makes the code much more complex [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF][START_REF] Plauth | A performance evaluation of dynamic parallelism for fine-grained, irregular workloads[END_REF].

GPU-accelerated Backtracking

Backtracking algorithms explore the solution space by dynamically building a tree in a depth-first order [START_REF] Zhang | Branch-and-bound search algorithms and their computational complexity[END_REF]. The algorithm iteratively generates and evaluates new nodes, where each child node is more restricted than its father node. If a child node leads to a feasible and valid solution, it is branched, and its child nodes are stored in the Active Set. Otherwise, the node in question is discarded, and the algorithm backtracks to an unbranched node in the Active Set. The search generates and evaluates nodes until the Active Set is empty.

GPU-based backtracking algorithms usually consist of two stages: backtracking on CPU until a cutoff depth d cpu and parallel backtracking on GPU [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF][START_REF] Plauth | A performance evaluation of dynamic parallelism for fine-grained, irregular workloads[END_REF][START_REF] Zhang | Optimization of N-Queens solvers on graphics processors[END_REF][START_REF] Feinbube | NQueens on CUDA: Optimization issues[END_REF][START_REF] Carneiro | A new parallel schema for branch-and-bound algorithms using GPGPU[END_REF]. Algorithm 1 presents a pseudocode for the GPU-accelerated backtracking in question.

Initially, the algorithm gets the problem to be solved (line 1) and the properties of the GPU (line 2). Next, the variable d cpu receives the initial cutoff depth (line 3). The cutoff depth d cpu is a problem-dependent parameter, usually determined by manual tuning. For the ATSP, the cutoff depth d cpu corresponds to all feasible and valid permutations with d cpu cities. The initial backtracking on CPU (line 4) fills the active set A cpu with all objective nodes found at d cpu , as illustrated in Figure 1. In the present context, an objective node is a valid, feasible and incomplete solution (permutation) at d cpu .

Before launching the backtracking on GPU, a subset S ⊆ A cpu of size chunk ≤ |A cpu | is chosen (line 7). Next, the CPU updates A cpu and transfers S to GPU's global memory (lines 8 -11). Then, the host configures and launches the kernel (lines 12 -14). In the kernel, each node in S represents a concurrent backtracking root R i , i ∈ {0, ..., chunk -1}. Therefore, each thread T h i explores a subset S i of the solution space S concurrently. The kernel ends when all threads have finished the exploration of S. The kernel may be called several times until A cpu is empty (lines 6 -16).

Algorithm 1: CPU-GPU parallel backtracking algorithm.

CDP-based Backtracking Algorithms

Plaut et al. [START_REF] Plauth | A performance evaluation of dynamic parallelism for fine-grained, irregular workloads[END_REF] propose two CDP-based backtracking for enumerating all feasible and unique solutions of the N-Queens, called DP2 and DP3. Both approaches launch recursively Algorithm 1 by using CDP. The strategy called DP2 is based on two depths: d cpu and d gpu . Each node in A cpu (at depth d cpu ) is a root of a backtracking that searches for objective nodes at depth d gpu . To store the objective nodes, the first thread of block b that finds an objective node allocates memory for the maximum number of objective nodes block b can find. This block-based active set will be further referred to as A b gpu . Then, a recursive new generation of kernels is launched by using CDP, searching from d gpu to N , as Results show that the overhead caused by dynamic allocations and dynamic kernel launches outweighs the benefits of the improved load balance yielded by CDP. Moreover, the performance of both algorithms strongly depends on the tuning of several parameters, such as block size and cutoff depth.

Applications that perform dynamic allocations on GPU and/or launch more than two kernel generations that synchronize require the configuration of the CUDA runtime, which is not straightforward [START_REF] Adinetz | CUDA dynamic parallelism: API and principles[END_REF][START_REF][END_REF]. Under this scope, Carneiro Pessoa et al. [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF] propose CDP-BP: a CDP-based backtracking that performs no dynamic allocations on GPU and avoids the need for dynamic setup of CUDA runtime variables. CDP-BP is also based on two depths, like DP2. The memory requirements of the application are dynamically calculated on the host, taking into account an analysis of the partial backtracking tree. The host allocates memory for further kernel generations and launches the search on GPU. Each GPU thread identifies its portion of the device-side active set based on thread-to-data mappings. Results show that CDP-BP has much better worst-case execution times and smaller dependence on parameters tuning than its non-CDP counterpart. Additionally, the authors also reported a difficulty in comparing CDP-BP to DP2 and DP3 using memory demanding instances, due to the complexity of dynamically calculating the upper bound on the required CUDA heap size.

The Proposed Algorithm

As previously pointed out, it is not straightforward to calculate an upper bound on the GPU heap size a CDP-based application needs. It is necessary to take into account the memory requirements of several CDP kernel generation until the search reaches the base depth. If the programmer does not configure the CUDA heap size before launching the first kernel generation, the GPU reserves a default memory space of 8 MB, which may be insufficient to store the objective nodes found by several kernel generations. However, it is not possible to configure the GPU heap size equal to the GPU's global memory size, as the CDP runtime reserves memory for other purposes.

Up to 150 MB of global memory is reserved for each kernel generation that performs parent-child synchronization. This memory is used to keep track of the state of the parent grid and cannot be used by the programmer. Additionally, in case the application launches more than two kernel generations that perform synchronization, a CUDA runtime variable must be explicitly configured with such a number of generations to avoid runtime errors [START_REF][END_REF].

This section presents a new algorithm to calculate the memory requirements of the search, independently of the number of launched kernel generations. The proposed algorithm works on the host. The upper bound on the GPU heap size is dynamically calculated according to an analysis of the partial backtracking tree, by applying for different kernel generations the memory requirement analysis of [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF]. Additionally, the proposed algorithm also configures the CUDA runtime accordingly, before the first kernel generation is launched.

The following sections provide a detailed description of the proposed algorithm. It consists of two main parts: memory requirement analysis and launching the first kernel generation. For the sake of greater simplicity, only the algorithm for solving instances of the ATSP to optimality is presented, which can be adapted for solving other permutation combinatorial problems with straightforward modifications.

Memory Requirement Analysis

As pointed out in Section 2.3, GPU-based backtracking performs an initial search on CPU to generate A h cpu . Before launching the first kernel generation, it is necessary to find a subset S ⊆ A h cpu of size chunk for which its memory requirement fits the device limitations. The Device (GPU) and Host (CPU) data structures will be further distinguished by the superscripts d and h, respectively.

Backtracking algorithms that dynamically allocate memory on GPU's heap, such as DP3, need to store in global memory A d cpu , the cost matrix C N ×N , and control data for the subsequent kernel generations. Moreover, it is necessary to reserve memory for parent-child synchronization and the heap. The memory requirement analysis consists of three steps: getting the number of kernel generations, heap size calculation, and calculation of the required global memory. These steps are detailed in the following sections.

Calculating the Number of Kernel Generations

It is necessary to know the number of kernel generations before launching the first one. This value is used to configure the runtime and to calculate the memory reserved by the GPU to keep track of context data of the parent grid.

One can see in Algorithm 2 the function that returns the number of kernel generations. Initially, the function receives the intial depth of the search and the size N of the problem. Next, it gets the base of the recursion (line 1). Then, the number of generations that perform parent-child synchronization is calculated in lines 4 -6. The programmer must provide two functions: get base depth() and get next depth(). The first one is responsible for calculating the base of the recursion (line 1). In turn, the second one is responsible for returning the next depth of the recursion (line 5), which works like an iterator.

Upper Bound on the Required GPU Heap Size

The heap size calculation is the main step of the memory requirement analysis. The strategy employed in this step takes into account the maximum number of children nodes that a node at current depth can have at next depth, which is:

expected childrennext = maxnext maxcurrent
where the maximum number of nodes of a given depth d is:

max d = (N -1)! (N -d)!
Algorithm 3 presents a function that estimates an upper bound on the required GPU heap size. This function receives as parameters chunk, which is the size of a subset S ⊆ A h cpu , and the size N of the problem. Then, it calculates, for each recursive kernel call until the search reaches the base depth, the memory required to store the upper bound on the number of objective nodes at depth next (lines 4 -11). After getting the heap requirements for chunk nodes, it is possible to determine the amount of global memory required by the application.

Global Memory Required by the Application

Algorithm 4 returns the amount of global memory required by the application based on a subset S ⊆ A h cpu of size chunk. Initially, the memory reserved for synchronization is calculated in line 1. As previously pointed out, a memory space of 150 MB is reserved for each kernel generation that performs parentchild synchronization. The amount of global memory required to store the control data, A d cpu , and the heap is calculated in lines 3 -4. Finally, in line 6, the required global memory is calculated by adding the values got in lines 2 -5.

Algorithm 3: Upper bound on the GPU heap size.

Input: The size chunk of S ⊆ A h cpu , and the size N of the problem. Output: Upper bound on the requested GPU heap size (in bytes). All algorithms presented in this section take into consideration a subset S ⊆ A h cpu of size chunk. The next section shows how to choose S, to set up the CUDA runtime variables, and to launch the first kernel generation.

Launching the First Kernel Generation

Before launching the first kernel generation from the host, the application must find a subset S ⊆ A h cpu of size chunk such that an upper bound on its requirements fit into the global memory. Algorithm 5 shows how to get such a subset. Initially, the upper bound on the requirements of S is calculated in line 1, using Algorithm 4. If the memory required by S is bigger than the available global memory, chunk is decreased until its requirements fit into the available global memory (lines 3 -5). If there is no S such that its requirement fits into the available global memory, the program returns an error (lines 6 -8).

Algorithm 6 presents the launching of the first kernel generation on GPU. After determining a suitable S (line 1), the CUDA runtime variables of heap size and number of kernel generations are set in line 2. All allocations on device memory are performed in line 3. There is no host allocation for other active sets than A d cpu because threads on device dynamically allocate memory on GPU's Algorithm 4: Global memory required by the application.

Input: The size chunk of S ⊆ A h cpu , the size N of the problem, and the number k of kernel generations that perform parent-child synchronization. Output: The total of global memory required by the application (in bytes).

1 required memory ← 0 2 nesting memory ← k × 150M B 3 activeSet memory ← chunk × sizeof (N ode) 4 control memory ← chunk × sizeof (ControlData)

Performance Evaluation

The proposed algorithm was implemented to manage three recursive CDP-based backtracking from the literature:

-DP2 and DP3: CDP-based algorithms introduced in Section 2.3.1.

-CDP-DP3: hybridization between CDP-BP and DP3 proposed by [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF]. Compared to DP3, CDP-DP3 also doubles d cpu until the search reaches the base depth. However, CDP-DP3 launches less CDP kernels than DP3, and dynamic allocations start on the second CDP kernel generation.

These GPU-based searches are launched in line 11 of Algorithm 6. For comparison, the following backtracking strategies are also considered.

-BP-DFS: non-CDP implementation of Algorithm 1 proposed by [START_REF] Carneiro | A new parallel schema for branch-and-bound algorithms using GPGPU[END_REF].

-CDP-BP: CDP-based algorithm introduced in Section 2.3.1 that makes no dynamic allocations on GPU and launches two kernel generations. -Multicore: multi-threaded version of BP-DFS that applies a pool scheme for load balancing. -Serial: serial control implementation optimized for single-core execution.

All implementations (but the serial one) use the data structures, the algorithm for consistency of the incumbent solution, and the kernel code of BP-DFS. For more details, refer to [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF].

Experimental Protocol and Parameters Settings

All CUDA programs were parallelized using CUDA C 8.0 and compiled with GCC 5.4. The testbed, operating under CentOS 7.1 64 bits, is composed of two Intel Xeon E5-2650v3 @ 2.30 GHz with 20 cores, 40 threads, and 32 GB RAM. It is equipped with an NVIDIA Tesla K40m (GK110B), 12 GB RAM, and 2880 CUDA cores @ 745 MHz.

In the experiments, ATSP instances of sizes (N) ranging from 10 to 19 are solved to optimality. In turn, N-Queens problems of sizes (N) ranging from 10 to 18 are also considered. The memory requirement of the test-cases ranges from few KB to several GB.

To compare the performance of two parallel backtracking algorithms, both should explore the same search space [START_REF] Karypis | Unstructured tree search on SIMD parallel computers[END_REF]. Therefore, for all ATSP instances, the initial upper bound is set to the optimal value. This initialization ensures that all implementations above outlined explore the same feasible region, which is always the case for the N-Queens problem.

The performance of GPU-accelerated backtracking algorithms strongly depends on the tuning of several parameters [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF][START_REF] Plauth | A performance evaluation of dynamic parallelism for fine-grained, irregular workloads[END_REF]. Preliminary experiments were carried out to find out a suitable block size, d cpu and d gpu for all GPU-based implementations. Table 1 summarizes the best parameter configurations of all parallel implementations. The chosen parameters are the best for most of the instances, but not for all of them.

Both DP3 and CDP-DP3 have no cutoff depth tuning because they follow the strategy proposed by [START_REF] Plauth | A performance evaluation of dynamic parallelism for fine-grained, irregular workloads[END_REF], which doubles d cpu . For the N-Queens, there are N possibilities of starting node at depth d cpu . This way, four kernel generations can be launched: at d cpu = 1, d gpu = 2, 4 and 8 (base). For the ATSP, there is only one possible starting city. This way, three kernel generations are launched.

Results

First of all, it is important to point out that the proposed algorithm is necessary to make DP2, DP3, and CDP-DP3 solve all test-cases without runtime Table 1: List of best parameters found experimentally for all parallel implementations. The superscript Q and A indicate that the settings are for the N-Queens or, respectively, the ATSP implementation. errors. According to preliminary experiments, these implementations that make dynamic allocations on GPU cannot solve instances of size N > 12 using the default GPU heap size of 8 MB. The CUDA runtime returns an "illegal memory access" error in situations where the GPU heap requirement of the application is bigger than the configured one.

Table 2 reports the average speedup achieved by all parallel implementations for different ranges of problem sizes compared to the serial baseline. In turn, Figure 2 presents the average speedup reached by all parallel implementations compared to the serial baseline.

The lowest values of average speedup in Table 2 are observed for DP2, DP3, and CDP-DP3. These applications perform dynamic allocations/deallocations on GPU and launch a new kernel per GPU thread. The overhead of dynamic allocations, multiple streams creation/destruction, and several kernel launches amount negatively for small sizes. However, as the solution space grows, this overhead becomes less significant, and the benefits of a more regular load yielded by the DP3 algorithm are observed: as can be seen in Figure 2, CDP-DP3 is the CDP-based implementation with the best overall results for the ATSP.

The benefits of using the DP3 strategy would not be realized without the proposed algorithm. As previously said, DP2, DP3, and CDP-DP3 can only solve instances of size up to N = 12 without GPU heap configuration. According to for sizes ranging from 10 to 12. These values change considerably for bigger problems, and CDP-DP3 becomes superior to CDP-BP for solving the ATSP, as previously pointed out. However, it is not the case for the N-Queens, as one can see in Figure 2.

Launching one new kernel for each GPU thread is not a good strategy for the N-Queens problem. The load processed by a child kernel is much smaller than the one launched when solving the ATSP [START_REF] Carneiro Pessoa | GPU-accelerated backtracking using CUDA dynamic parallelism[END_REF]. This way, DP2, DP3, CDP-DP3 produce a significant overhead for processing small loads. In turn, CDP-BP launches a new kernel generation based on the load of the whole block, instead of the load of a single thread. According to NVIDIA Visual Profiler, by using the block-based kernel launch, CDP-BP can archive twice more occupancy and three times more eligible warps per active cycle than all other CDP-based implementations while enumerating all feasible configurations of the N-Queens. Thus, CDP-BP is much faster than its CDP-based counterparts and as faster as the multi-threaded implementation. The results of CDP-BP for the N-Queens and instances of sizes ranging from 10-12 justifies its better values than the ones of CDP-DP3 in Table 2.

BP-DFS is the fastest implementation when using its best configuration since it is highly optimized and does not suffer from CDP's intrinsic performance penalties. Moreover, BP-DFS is also superior to the multi-threaded implementation that applies load balance and runs on two CPUs, 20 cores / 40 threads.

Discussion

One of CDP's purposes is to better cope with divide-and-conquer applications. This is in part true for our implementations of both CDP-DP3 and DP3. The use of dynamic allocations removes the need for complex thread-to-data mapping. Furthermore, the strategy of doubling d gpu makes almost the whole search to be executed on GPU, which avoids d cpu /d gpu tuning. However, solving memory demanding problems requires extra programming efforts.

Using a different value than the default one makes it necessary to configure the CUDA heap beforehand, which brings complexity to the code. The heap size calculation takes into account a subtree rooted at d cpu that goes down to the base depth. Moreover, the definition of a recursion base is also challenging: for an ATSP instance of size N = 18, 4 generations of kernels would be launched. Furthermore, it would require an enormous amount of memory to store the possible children nodes at d cpu = 16 (refer to Section 3.1.2). However, the last kernel generation would perform no all. example, consider instance tsmat18. The fourth kernel generation of DP3 would evaluate less than 3% of the solution space.

Moreover, the initial d cpu for both DP3 and CDP-DP3 is 2. Taking into account the ATSP, it is unlikely that pruning of unfeasible nodes happens in such a shallow depth. As a consequence, the memory requirement analysis of both DP3 and CDP-DP3 would return a heap requirement close to the maximum possible size, which wastes memory. This is not the case for DP2: both d cpu and d gpu need tuning, and the number of objective nodes at deeper depths is much smaller than the maximum one. This way, DP2 can solve instance crane15 in a configuration with the default heap and a deep d cpu . However, this configuration is slower than the one of Table 1 that needs GPU heap setup.

Finally, the memory for parent-child synchronization cannot be ignored, and it can be a limitation for more modest hardware: there may be a situation where the memory reserved for depth synchronization takes almost the whole global memory, leaving nearly no memory space for the search procedure on GPU.

Conclusion and Future Works

This work has presented an algorithm to calculate the memory requirements of CDP-based divide-and-conquer algorithms and configure the CUDA runtime accordingly. The proposed algorithm was implemented to manage different CDPbased backtracking from the literature and experimented on two test-cases: N-Queens and ATSP.

Using CDP may be a good choice for programmers that intent to parallelize recursive divide-and-conquer application for solving nondemanding problems. The use of recursion removes much of the complexity in programming and parameters tuning. Moreover, despite the intrinsic overhead of CDP, speedups are observed for all CDP-based implementations. However, using CDP for processing memory demanding recursive applications brings extra complexity on configuring the runtime before launching the first kernel generation.

A future research direction is on investigating different ways of calculating the next d gpu and a rule for determining the base depth. Another future work is to investigate limitations of modest gamer hardware while processing memory demanding CDP-based recursive applications.

Fig. 1 :

 1 Fig. 1: Illustration of the DP2 strategy.

Algorithm 2 :

 2 Calculating the number of kernel generations. Input: The size N of the problem, and the initial cutoff depth initial depth. Output: Number of kernel generations that perform synchronization. Also including the one launched by the host. 1 base ← get base depth(N ) 2 current depth ← initial depth 3 kernel gen ← 1 4 while current depth ≤ base depth do 5 current depth ← get next depth(current depth, N ) 6 kernel gen ← kernel gen + 1 7 end

1 9 ub

 9 ub requested heap ← sizeof (N ode) × chunk 2 base ← get base depth(N ) 3 current depth ← get initial depth() 4 while current < base do 5 next depth ← get next depth(current depth) requested heap ← ub requested heap × expected childrennext 10 current depth ← next depth 11 end

Fig. 2 :

 2 Fig. 2: Average speedup reached by all parallel implementations compared to the serial baseline.

  [START_REF] Brodtkorb | State-of-the-art in heterogeneous computing[END_REF] required heap ← get heap(chunk, N ) chunk, the size N of the problem, and the number k of kernel generations. Output: A suitable chunk size. Finally, lines 7 -18 process S ⊆ A h cpu of size chunk until A h cpu is empty. After each kernel call, control data is retrieved (line 12) and the variables counter and remaining are updated (lines[START_REF] Zhang | Dynamic parallelism for simple and efficient GPU graph algorithms[END_REF][START_REF] Dimarco | Performance impact of dynamic parallelism on different clustering algorithms and the new GPU architecture[END_REF][START_REF] Zhang | Branch-and-bound search algorithms and their computational complexity[END_REF][START_REF] Feinbube | NQueens on CUDA: Optimization issues[END_REF][START_REF] Carneiro | A new parallel schema for branch-and-bound algorithms using GPGPU[END_REF]. The variable counter is used to make A d cpu point to unexplored nodes (line 10) and as termination criteria (line 7). Launching the first kernel generation on GPU.

	Algorithm 5: Calculating a suitable chunk size.
	1 total required ← required memory(chunk, N, k)
	2 available memory ← get GP U properties(global memory)
	3 while total required > available memory do
	4	chunk ← decrease chunk(chunk)
	5	total required ← required memory(chunk, N, k)
	6	if chunk < 1 then
	7	return error
	8	end
	9 end
	heap. Algorithm 6:
	6 required memory ←
	required heap + nesting memory + activeSet memory + control memory

Input:

Input: Cost matrix C d N ×N ,A h cpu , the global upper bound, and the size N of the problem. 1 chunk ← get suitable chunk(survivors dcpu, N ) 2 set CDP variables(get heap(chunk, N ), get num gen(N, dcpu)) 3 device memory allocation(A d cpu , chunk, sizeof (N ode), control data d ) 4 survivors dcpu ← |A h cpu | 5 counter ← 0 6 remaining ← survivors dcpu 7 while counter < survivors dcpu do 8 nt ← get block size() 9 nb ← chunk/nt 10 cudaM emCpy(A d cpu , (A h cpu + counter), chunk × sizeof (N ode), H2D) 11 GP U search <<< nb, nt >>> (C d , chunk, A d cpu , control data d , upper bound, N ) 12 syncDataD2H(control data h , control data d , chunk) 13 counter ← counter + chunk 14 remaining ← remaining -chunk 15 if remaining < chunk then 16 chunk ← remaining 17 end 18 end

Table 2 :

 2 Average speedup reached by all parallel implementations for different ranges of sizes compared to the serial baseline.

		Average Speedup
	Implementation 10 -12 13 -15 16 -19(18) All sizes
	DP2	1.3× 3.26×	5.11×	2.99×
	DP3	1.08× 5.20×	6.68×	4.20×
	CDP-DP3	2.10× 7.89×	7.12×	5.72×
	CDP-BP	5.24× 8.38×	7.72×	7.10×
	BP-DFS	5.82× 15.86×	15.70×	12.37×
	Multicore	4.63× 14.71×	16.00×	11.41×

Table CDP -

 CDP BP is 2.5× faster than CDP-DP3 and 4.8× faster than DP3

[START_REF] Wang | Characterization and analysis of dynamic parallelism in unstructured GPU applications[END_REF] Parameter are the same for ATSP and N-Queens.


Audrey Marescaux

Vincent Thieu

Josette Garnier

Carbon dioxide, methane and nitrous oxide emissions from the human-impacted Seine watershed in France

Keywords: Seine Basin, CO2, CH4, N2O, direct/indirect emissions, human impacts

Carbon dioxide, methane and nitrous oxide emissions from the human-impacted Seine watershed in France

Introduction

Carbon dioxide (CO 2 ), methane (CH 4 ) and nitrous oxide (N 2 O) have been shown to dominate the well-mixed greenhouse gases (GHGs), contributing 80% of the positive radiative forcing driving climate change (Myhre et al., 2013). Between 1750, the beginning of the Western industrial revolution, and 2011, atmospheric concentrations of CO 2 , CH 4 and N 2 O increased by 40%, 150% and 20%, respectively, reaching values of 390.5 ppm (± 0.2 ppm), 1803.2 ppm (± 0.2 ppm) and 324.2 ppb (± 0.2 ppb) (Hartmann et al., 2013).

For the 1750-2011 period, anthropogenic CO 2 emissions at the global scale reached 555,000 ± 85 teragrams of carbon (TgC). Fossil fuel combustion and cement production were responsible for 67.5% of it while land use change accounted for 32.4% (Almajhdi et al., 2013). For the 2000-2009 period, anthropogenic CH 4 global emissions were estimated at 248 (228-276368) TgC-CH 4 yr -1 (bottom-up approach) (Almajhdi et al., 2013). The Intergovernmental Panel on Climate Change (IPCC) report ( 2013), attributed 60.4% of CH 4 sources to agriculture and waste, 10.6% to biomass and biofuel burning and 29% to fossil fuel combustion. N 2 O atmospheric concentrations have also increased considerably since the preindustrial era, due to intensification of agriculture and the use of synthetic nitrogen (N) fertilizers and manure applications that increased the production of N 2 O in soils, sediments and aquatic ecosystems. In addition to fertilization, industrial processes (e.g., manufacture of nylon), effluents from wastewater treatment, cattle feedlots and excrement, biomass burning and land emissions due to atmospheric nitrogen deposition (from agriculture, fossil fuel combustion, burning biomass and industrial activities) also contributed to an increase in N 2 O emissions of 6.9 (2.7-11.1) TgN (N 2 O) yr -1 over the last two decades (Seitzinger et al. 2000;Khalil et al. 2002;Ciais et al., 2013).

Global emissions of these three GHGs from streams and rivers have been reported in the literature as important fluxes in the continental GHG budgets. CO 2 emissions from rivers and streams have been quantified at between 230 (150-300) TgC yr -1 and 1,800 ± 250 TgC yr -1 or 840-6,600 Tg CO 2 equivalent yr -1 (Tg CO 2 eq), (Cole et al., 2007;Battin et al., 2009b;Aufdenkampe et al., 2011;Lauerwald et al., 2015;Regnier et al., 2013;Raymond et al., 2013a ;Sawakuchi et al., 2017;Drake et al., 2017). CH 4 global inland water emissions have been estimated at 1.5-26.8 Tg CH 4 yr -1 or 42.0-750.4 Tg CO 2 eq (Bastviken et al., 2011;Sawakuchi et al. 2014;Borges et al. 2015;Stanley et al. 2016) while N 2 O riverine emissions have been reported to range between 50.6 (46.5-55.5) Gg N 2 O yr -1 and 1,980 Gg N 2 O yr -1 or 13.4 Tg CO 2 eq and 524.7 Tg CO 2 eq (Kroeze et al., 2010;Beaulieu et al., 2011;Hu et al., 2016). In CO 2 eq, global CO 2 emissions are about ten times higher than CH 4 and N 2 O emissions. Many regional studies on inland waters have proposed a specific focus on CO 2 emissions (Butman and Raymond 2011;Denfeld et al. 2013;Abril et al. 2014;Ran et al., 2017, van Geldern et al., 2015, among others), CH 4 emissions (e.g., Bastviken et al. 2004;Garnier et al., 2013;Sawakuchi et al., 2014;Spawn et al. 2015;McGinnis et al. 2016) or N 2 O emissions (e.g., Seitzinger et al. 2000;Garnier et al., 2009;Yu et al., 2013;Turner et al., 2015). However, only a few studies have assessed the three GHG concentrations together or emissions from lentic ecosystems (reservoirs and lakes) (e.g., Huttunen et al., 2003;Zhao et al., 2013;Miettinen et al., 2015;Huang et al. 2015;Wang et al. 2017) or from streams and rivers (e.g., Harrison et al., 2005;Hlaváčová et al., 2006;Borges et al., 2015;Teodoru et al., 2015;Schade et al., 2016;Borges et al., 2018). Anthropogenic activities are known to have marked impacts on biogeochemical cycles and on CO 2 , CH 4 and N 2 O emissions (e.g., Kempe, 1982 and1984;Seitzinger et al., 2000;Garnier et al., 2007;Rajkumar et al., 2008;Barros et al., 2011;Baulch et al., 2011;Regnier et al., 2013;Alshboul et al., 2016b;Deemer et al., 2016;Martinez-Cruz et al., 2017;Prairie et al., 2017).

N 2 O emissions from the highly urbanized Seine drainage network have been estimated at 0.10-0.20 gigagrams (Gg) N-N 2 O yr -1 or 42-83 Gg CO 2 eq yr -1 (Garnier et al. 2009), while CH 4 emissions have been estimated at 0.30 GgC-CH4 yr -1 or 11.2 Gg CO 2 eq yr -1 (Garnier et al., 2013b). CO 2 emissions from the Seine basin have not yet been investigated, apart from occasional values of pCO 2 calculated in the Seine at Paris (annual mean for 1975Paris (annual mean for -1979Paris (annual mean for : 1997 ppmv; ppmv;Kempe, 1982). Nevertheless, comparison of the three GHG budgets at the global scale (with a factor of 10 between CO 2 and N 2 O or CH 4 emissions expressed in CO 2 eq), supports the hypothesis that CO 2 emissions could also account for a large proportion of the GHG emissions at the regional scale of a single watershed. This paper compares GHG behaviors (CO 2 , CH 4 , N 2 O) in the Seine River, a temperate hydrosystem subjected to strong anthropogenic pressures and quantifies the emissions from the drainage network. Earlier papers by our team already examined water concentrations and emissions of N 2 O (Garnier et al., 2009) and CH 4 (Garnier et al., 2013). Here we report on new field investigations to examine pCO 2 and CO 2 emissions together with CH 4 and N 2 O. Spacetime analyses at the scale of the Seine River basin using this unique GHG data set were expected to provide new insights into GHG riverine emissions, particularly the impact of wastewater effluents from the Parisian conurbation (12 M inhabitants). The second aim of this study was to compare the indirect emissions from the drainage network with estimated direct emissions from land under different uses (croplands, grasslands and forests, and livestock farming) and due to other activities (energy transformation, industry, residential and tertiary sectors, as well as transport) using existing data, in order to identify the main sources of emissions.

Material and methods

Study site

The Seine River is located in the north of France with a catchment of approximately 71,730 km 2 at Poses, where a weir separates the river from its estuary, and flows into the English Channel. Its average annual discharge over the past 10 years at the outlet is 500 m 3 s -1 (French water authorities Agence de l'Eau Seine Normandie -French acronym AESN, http://www.eau-seine-normandie.fr/, last accessed 2018/11/05). The Seine basin is densely populated (> 200 inhabitants (inhab.) km -2 for the basin as a whole but reaching more than 20,000 inhab. km -2 in inner Paris and around 5,000-7,000 inhab. km -² in the Paris conurbation) (Fig. 1) (INSEE 2013). Heavily urbanized and industrialized in its downstream sector, the upstream basin is dominated by croplands.

The Seine River watershed can be represented by the Strahler stream order (SOs) (Strahler, 1952;1957) a concept describing any hydrological network from its source (SO 1) to its estuary by a regular pattern of confluence of tributaries with increasing stream order. The Seine hydrological network is represented by more than 3,000 first SOs to one SO 7 (the lower Seine river) (Annex 1-1). The main stem studied here is the downstream Marne River (SO 6) and the lower Seine (SO 7). The Marne River basin is intensively cropped and densely populated in its downstream sector and used to be one of the most eutrophic rivers of the drainage network (Garnier et al., 2005) (Fig. 1). The Marne joins the Seine River at the entrance of Paris. Downstream from Paris, the Seine River receives the treated effluents of 12 million inhabitants, strongly impacting the lower Seine River, downstream from the confluence with the Oise River (SO 6). The main land use classes in the basin are croplands (56.8% of the basin), forests (25.8%) and grasslands (9.7%), urbanized areas represent 7.0% (CLC database, IFEN, 2006) and wetlands (between 10.9%-15.6%;Curie et al., 2007). The lithology of the sedimentary basin of the Seine River is dominated by chalk, limestone and carbonates (Annex 1-1).

Sampling strategies

Eleven field campaigns were conducted at 23 sampling locations over a distance of 700 km (exact locations in Annex 1-6). Sampling sites were selected to account for the spatial variability of the upstream basin along the Marne River, upstream and downstream from the main WWTPs, including Paris, and along the lower Seine. The 11 field campaigns at low water were conducted in 2010 (May 3-4 May; July 5-7; October 2-6 2010), in 2011 (May 17-19; August 23-28), in 2012 (April 4-10; August 28 to September 3), in 2013 (February 13-18;June 17-23 2013), andin 2014 (May 13-17;September 9-12). In addition to these longitudinal profiles, smaller SOs were sampled during two snap-shot campaigns in 2016 (February 22 to March 10, and September 7-14) and one in 2017 (March 14-23). A total of 14 campaigns are therefore analyzed here. Sampling locations covered all important land use classes in the basin.

In the field, 100 ml borosilicate serum bottles were filled with water without air to determine N 2 O and CH 4 levels. To stop biological processes and gas exchange, 50 µl of HgCl 2 (2%) was added to the bottles that were then sealed with a rubber septum. In addition, 2-l water chemistry sampling bottles (high-density polyethylene) were filled and pH (NBS scale), water temperature, turbidity, dissolved oxygen and conductivity variables were measured using a multiparameter instrument (YSI® 6600 V2). Buffers (pH 4 and 7) were used for pH calibration, potassium chloride electrolyte solution for dissolved oxygen, and 10 mS cm -1 standard for conductivity.

In the laboratory, total alkalinity (TA) (µmol kg -1 ) was analyzed using three replicates of 20 ml of filtered water (GF/F: 0.7 μm) with an automatic titrator (TitroLine® 5000) and HCl 0.1M. Dissolved nitrate and ammonium were determined on filtered water (GF/F, 0.7 μm) with an automated analyzer (Gallery TM Automated Photometric Analyzer) according to Jones (1984) and Slawyk and MacIsaac (1972), respectively.

For dissolved organic carbon (DOC), analyses were collected in glass flasks after filtration on GF/F Whatman grilled filters (GF/F, 0.7 μm porosity, at 500°C for 4 h) and acidified (0.1 ml H 2 SO 4 4 M in 30 ml of water). DOC was analyzed with a TOC analyzer (Aurora 1030 TOC Analyzer, O-I-Analytical).

Gas analyses

Dissolved carbon dioxide.

Partial pressure of CO 2 (pCO 2 ) (ppmv) was measured in small SOs (1-3) and along the main stem (SOs 6-7), using a syringe headspace technique coupled with a non-dispersive infrared (NDIR) gas analyzer (Licor LI-820 or LI-840, USA) (Abril et al., 2015). In four syringes, 30 ml of stream water and 30ml of air were equilibrated in CO 2 by shaking them continuously for 10 minutes. The first syringe was used to purge the system and measurements were made using the other three. Dry pCO 2 was converted into CO 2 water concentrations (µgC l -1 ) (Weiss, 1974;Weiss and Price, 1980). We completed our data set of field measurements with existing datasets of pH, total alkalinity and water temperature measurements from which we calculated pCO 2 values (ppmv) with CO2SYS software algorithms (Pierrot et al., 2006) using water temperature, alkalinity and pH measurements for the period 2007 -2017 (22,142 of these three variables, i.e., around 1,400 stations distributed throughout the Seine Basin at a monthly to bimonthly frequency ) collected by the French water authorities -AESN). The carbonate dissociation constants (K1 and K2) applied were from (Millero, 1979) Atmospheric wet pCO 2 and pCO 2 was used to calculate CO 2 concentrations (µgC l -1 ) at equilibrium in the water with CO 2 solubility (Weiss, 1974).

Dissolved nitrous oxide (N2O) and methane (CH4).

N 2 O concentrations were determined with a gas chromatograph (Perichrom ST 200)

combined² with an electron capture detector (GC-ECD) (Garnier et al. 2007 and2009). CH 4 concentrations were also measured using a gas chromatograph coupled to a flame ionization detector (GC-FID) (Garnier et al., 2013). Only the three 2010 campaigns were already included in Garnier et al. (2013) for CH 4 . For N 2 O and CH 4 determination, we used the same sampling and laboratory procedures as in the studies cited just above.

Calculation of indirect and direct emissions

Calculation of indirect emissions from hydrosystems

The diffuse flux (f(GHG), mgC-CO 2 , mgC-CH 4 or mgN-N 2 O m -2 day -1 ) of GHG at the interface of the river and the atmosphere can be calculated as:

𝑓(𝐺𝐻𝐺) = 𝑘 𝐺𝐻𝐺 ([𝐺𝐻𝐺] -[𝐺𝐻𝐺] 𝑒𝑞 ) Eq. 1
where [𝐺𝐻𝐺] is the concentration of greenhouse gases in the water (mgC-CO 2 m -3 , mgC-CH 4 m -3 , mgN-N 2 O m -3 ), and [𝐺𝐻𝐺] 𝑒𝑞 is the concentration of greenhouse gas at equilibrium with respect to atmospheric concentrations (mgC-CO 2 m -3 , mgC-CH 4 m -3 , mgN-N 2 O m -3 ).

According to Wanninkhof (1992), Wilke and Chang (1955) and Raymond et al., (2012a), the gas transfer velocity 𝑘 𝐺𝐻𝐺 (m day -1 ) under negligible wind conditions in rivers can be calculated as:

𝑘 𝐺𝐻𝐺 = 𝑘 600 . √ 600 𝑆𝑐 𝐺𝐻𝐺 (𝑇)
Eq. 2

The k 600 (Eq. 3) in Raymond et al., (2012a) was selected as being appropriate to compare GHG emissions at large spatial scales, and for analyses of bulk biogeochemical budgets (Raymond et al., 2012a).

𝑘 600 = 𝑣. 𝑆. 2841 ± 𝑎 + 2.02 ± 𝑏 Eq. 3

where 𝑣 is the water velocity (m s -1 ) and S the slope (-); 𝑘 600 is the gas transfer velocity for a Schmidt number of 600 (m day -1 ). Coefficients a and b are standard deviations of 107 and 0.209, respectively. The French water authority database -AESN, enabled estimation of the water velocity from water discharge records in the basin for the period 2012-2014, and also provided measured slopes. Slopes and water velocity were then averaged by SO and by season.

Schmidt numbers (𝑆𝑐 𝐺𝐻𝐺 (𝑇), dimensionless) of the calculated GHG (-) depend on water temperature 𝑇 in degree Celsius (°C) as described in Wanninkhof (1992)

𝑆𝑐 𝐶𝑂 2 (𝑇) = 1911.1 -118.11𝑇 + 3.4527𝑇 2 -0.041320𝑇 3 𝑆𝑐 𝐶𝐻 4 (𝑇) = 1897.8 + 114.28𝑇 + 3.2902𝑇 2 -0.039061𝑇 3 𝑆𝑐 𝑁 2 𝑂 (𝑇) = 2055.6 -137.11𝑇 + 4.3173𝑇 2 -0.054350𝑇 3
Eq. 4

Eq. 5

Eq. 6

Each flux was calculated for each SO and day. The total emission of the hydrosystem (E) (mgC-CO 2 day -1 , mgC-CH 4 day -1 or mgN-N 2 O day -1 ) corresponds (see Eq.7) to the sum of GHG fluxes calculated for each SO (F SO ) multiplied by the number of rivers per SO (n SO ) and the average water surface of these SOs (A SO , m 2 ). The number of rivers per SO (n SO ) and the water surface (A SO ) were extracted from the drainage network based on the topological records of the French water authorities -AESN.

𝐸 = ∑ F SO n SO A SO 8 𝑆𝑂=1 Eq. 7
These values were averaged per period (summer -April to October-and winter -November to March-) and per SO (1-7). Finally, the annual estimate was assumed to have the combination of values calculated using average summer and winter characteristics (see Garnier et al., 2009 and2013).

While humans have increased direct emissions through agricultural and industrial activities, emissions have also increased indirectly in aquatic and semi-aquatic (lake, river, riparian zone) and terrestrial (e.g., forest) ecosystems (Jurado et al., 2017).

Direct greenhouse gas emissions from agricultural and nonagricultural activities in the

Seine basin

We used the estimations of N 2 O and CH 4 emissions caused by agricultural activities in the Seine basin reported in previous studies (Garnier et al., 2009 and2013). The total amount of CH 4 emitted from agricultural sources, i.e., essentially by livestock (enteric fermentation and manure degradation) was calculated based on the number of animals per species and per age in the Seine Basin, and the specific emission factors for each species (kg-CH 4 head -1 year -1 ) (Garnier et al., 2013). Again, according to Garnier et al. ( 2013), we estimated CO 2 emissions from agricultural sources considering the use of 180 kgN ha -1 yr -1 nitrogen fertilizers on agricultural land and the emission of 0.52 tC-CO 2 per ton of N fertilizers produced. We also assumed that 100 l ha -1 yr -1 of fossil energy is required for farm work. Taking into account the cropped area, these emissions amounted to 622 Gg C-CO 2 yr -1 (Garnier et al., 2013). As a first approximation, we disregarded the effect of possible sequestration by soils and emissions linked to changes in land use. All nonagricultural GHG emissions were collected with spatially explicit references and processed using GIS technology (QGIS Development Team, 2016) to be scaled to the limits of the Seine River basin. Total GHG emissions were estimated by summing riverine, agricultural and nonagricultural GHG emissions.

Statistical analyses

The GHG concentrations and associated water temperatures were bootstrapped with 10,000 iterations, using the R package "boot.ci" (R Core team, 2015) in order to obtain mean, standard deviation and 95% confident intervals for each season and each SO. This procedure allows estimating the distribution of a sample from a limited dataset. For each bootstrap, the consistency between the generated mean value and that of the original dataset was checked.

The uncertainty of the GHG flux (expressed as 95% confidence interval) was quantified with Monte Carlo simulations using equation (1) consisting of 10,000 runs (Beck, 1987). The required distributions of the input parameters were either provided by the bootstrapping (for GHG concentrations and water temperatures) or equation ( 3) for the gas exchange velocities assuming a Gaussian distribution of coefficient a and b. For these calculations, we also assume that each of these parameters varies independently from one another.

The variability of GHG concentrations and gas transfer velocity between orders and seasons was tested using Kruskal-Wallis and Wilcoxon signed-rank tests, respectively. Coefficients of determination (R 2 ) were used to check for correlations between GHG concentrations, nutrients and environmental parameters. Significant correlations are designated by an asterisk, taking into account the number of data.

Results

Greenhouse gas concentrations in the hydrological network

The annual mean CO 2 concentrations in the water were spatially significantly higher for the first and last SOs (> 2,000 µgC-CO 2 l -1 ), similar to N 2 O (> 1 µgN-N 2 O l -1 ). The annual mean CH 4, concentrations were only significantly higher in the 7 th SO, especially in summer (> 3 µgC-CH 4 l -1 ) (Fig. 2) (Annex 1-5). The mean annual concentrations in medium river SOs (3-5) were generally lower(< 2000 µgC l -1 for CO 2 , < 1.5 µgC l -1 for CH 4 , and ~ 0.6 µgN l -1 for two seasons selected (winter and summer). CO 2 concentrations were only significantly higher in summer than in winter in the 1 st SO whereas summer CH 4 concentrations were higher in the majority of SOs (Fig. 2, Table Annex 1-4). mean CH 4 saturation value: 43 ngC l -1 with a range of 27-61 ngC l -1 ).

Our data set enabled us to focus on the three GHG concentrations along the main streams of the Marne River (Fig. 3, from -365 to 0 km, SO 6) and the lower Seine River (Fig. 3, km from 0 to ± 350 km, SO 7) where the concentrations were the highest (Fig. 3; see also Fig. 2). The 11 longitudinal profile campaigns (from April to October i.e., in the summer period) were averaged for each GHG concentration for 2010-2014, and for each station (10 on the Marne branch and 13 on the lower Seine, Fig. 3). Despite wide variability, the longitudinal profiles of three GHG gases (CO 2 , CH 4 , N 2 O) shared similar spatial trends of their concentrations (Fig. 3). Indeed, the concentrations were highest downstream from the effluent outlets in the Paris conurbation and from the city of Rouen. These patterns mirrored NO 2 -, NH 4 + and DOC concentrations that are typically high in wastewater effluents. As nitrification and organic matter degradation consume oxygen, the opposite trend was observed for oxygen concentrations (Fig. 3). concentrations and other variables of interest (e.g., O 2 , dissolved organic carbon). The slopes of the relationships varied greatly (by a factor of 100), depending on the discharge and the temperature during the campaigns (Fig. 4; Table 1-1).

Greenhouse gas emissions from the hydrological network

The difference in GHG concentrations between the atmosphere and the surfaces of the water, and gas transfer velocities, control emissions of GHGs. Gas transfer velocity depended on k 600 (Eq. 3) and on the Schmidt number (Eq. 4-6). k 600 decreased with SOs due to the decreasing slope, and increased with water velocity as a result of turbulence. Schmidt numbers depend on 20 temperature sensitivities of the specific solubility of the different gases, resulting in different k patterns (Annex 1-3).

Greenhouse gas emission fluxes showed that the Seine hydrological network is a source of three gases (CO 2 , CH 4 and N 2 O) to the atmosphere. In particular, budgets showed that CO 2 summer emissions (1,440 10 3 kgC-CO 2 day -1 ) were lower than winter emissions (1,800 10 3 kgC-CO 2 day -1 ) (annual amount 592 GgC-CO 2 yr -1 on average, Fig. 7). Seasonal CH 4 emissions were 554 kgC-CH 4 day -1 and 433 kgC-CH 4 day -1 in summer and winter, respectively (i.e., an average annual diffusive emission of 0.180 GgC-CH 4 yr -1 ). N 2 O emissions amounted to 708 kgN-N 2 O day -1 in summer and 601 kgN-N 2 O day -1 in winter (i.e., an annual average of 0.240 GgN-N 2 O yr -1 ) (Fig. 7). In addition, the annual budget shows that 44% of the CO 2 emissions were emitted from the first and second SOs of the Seine basin, while the 6 th and 7 th SOs contributed the most nitrous oxide, more than 50% of the emissions.

CH 4 emissions were more evenly distributed among upstream (SOs 1, 2), intermediate (SOs 3, 4, 5) and downstream reaches (SOs 6, 7).

Considering global warming potential (GWP) for the last 100 years, i.e. 28 for CH 4 and 265

for N 2 O, the hydrosystem's annual N 2 O budget (99 Gg CO 2 eq yr -1 ) was 14 times higher than CH 4 diffusive emissions (7 Gg CO 2 eq yr -1 ), an N 2 O budget that itself was around 22 times lower than the CO 2 budget (2,170 Gg CO 2 eq yr -1 ) (Fig. 7, Table 1-2). Interestingly, CO 2 emissions accounted for 95.3% of the three GHG emissions from the hydrosystem (indirect emissions), while N 2 O and CH 4 emissions accounted for 4.4% and 0.3%, respectively.

Emissions from agricultural and nonagricultural sectors

Total GHG emissions from the agricultural basin were estimated at 14,295 Gg CO 2 eq yr -1 .

CH 4 , N 2 O and CO 2 emissions contributed 51%, 33% and 16% of agricultural emissions, respectively (Table 1-2).

Total direct GHG emissions from the nonagricultural basin were estimated at 44,713 Gg CO 2 eq yr -1 , the majority from the Ile-de-France region (92%). Nonagricultural emissions of CO 2 were more than 100 times higher than those of CH 4 and N 2 O (Table 1-2). Whereas CO 2 emissions were rather well distributed among the categories, CH 4 and N 2 O emissions occurred mainly in the energy & manufacturing sector. These emissions were approximately three times higher than the sum of those from the residential & tertiary and transport sectors (Fig. 5).

Total GHG emissions from the Seine basin

Total GHG emissions from the basin were estimated at 61,284 Gg CO 2 eq yr -1 . When both direct emissions (including agricultural and nonagricultural activities) and indirect emissions (from the hydrosystem) were summed, the value was much higher for CO 2 (48,528 Gg CO 2 eq yr -1 ), while CH 4 and N 2 O were estimated at 7,634 Gg CO2eq yr -1 and 5,122 Gg CO 2 eq yr -1 , respectively (Fig. 6). While agricultural activities were responsible for a quarter of the total GHG emissions in the Seine basin (14,295 vs. 61,284 Gg CO 2 eq yr -1 , Table 1-2), the hydrosystem only accounted for a small proportion of the total emissions of each of the three gases 4.5% for CO 2 , 0.1% for CH 4, and 1.9% for N 2 O (Fig. 6, Table 1-2).

Discussion

Limits to our calculations of the emission

To calculate gas emissions from the drainage network, k was computed according to Raymond et al. (2012), which validated the equation on small streams. The equation selected for k is linearly dependent on the slope and the water velocity averaged per SO and per season. Although the Seine catchment is relatively flat as the Seine source is located around under-or overestimation of GHG fluxes. Similarly, exceptional flood events resulting in high turbulence (and water velocity) were not taken into account in this study, which could bias our estimations. However, comparing our results with those previously published for N 2 O and CH 4 using a different equation (Garnier et al., 2009 and2013), did not change the numbers much. We thus consider that our results provide robust estimates, although there is a need for k measurements in the Seine hydrosystem, which could increase the accuracy of GHG emissions. Although uncertainties persist in the estimates of GHG direct emissions in the Ilede-France region and the rest of the basin, we believe that the order of magnitude is also correct.

Patterns of indirect CO 2 , CH 4 , N 2 O emissions from rivers in the drainage network: differences and similarities

Surprisingly, 95.3% of the indirect GHG emissions of the Seine drainage network were mainly linked to CO 2, compared to CH 4 (0.3%) and N 2 O (4.4%) emissions. Considering the higher stream orders (SOs) of the Seine River as productive systems (Garnier et al., 2005(Garnier et al., , 2007) ) and despite the recent decrease in algal bloom (Aissa-Grouz et al., 2016), we had expected uptakes of CO 2 in the river network. Studying pCO 2 at the scale of the whole Seine drainage network revealed oversaturation in CO 2 at all locations and in both seasons, which we interpreted as being caused by soil leaching as well as inputs from aquifers where concentrations were up to ten times higher than those in the surface water (20,000-60,000 ppm in the Brie aquifer, data not shown), and releases of effluents from WWTPs.

Oversaturation of the GHGs with respect to atmospheric concentrations was not only observed in the Seine River (see also Garnier et al., 2009 and2013), but also in the other temperate river, the Meuse (Borges et al., 2018), where groundwater has also been reported to be a source of CO 2 oversaturation. Contributions from groundwaters, quickly degassed at the head of the basin, were experimentally demonstrated by Garnier et al. (2009) for N 2 O.

Further, the higher GHG emissions in small SOs can be linked not only with higher concentrations but also with higher gas exchange rates (k and k 600 ) (see Eq. 2, 3), k being linked with the slope of the basin, on average higher for lower SOs.

In headwaters, allochthonous organic matter inputs and nitrate fertilizer leaching are also possible sources of GHG emissions from mineralization of organic carbon in the soil and groundwaters, along with denitrification in riparian zones (see Fig. 8;and Richey et al., 2002;Venkiteswaran et al., 2014). Denitrification in soils or sediments (i.e., nitrate reduction) is known to produce more N 2 O in anoxic or suboxic conditions (Garnier et al., 2010;Vilain et al., 2014;Benoit et al., 2015) than nitrification. Regarding CH 4 , anoxic organic-enriched locations of the river banks or in-stream sediment may enhance methanogenesis. While high CO 2 and CH 4 concentrations have been reported to be related to the extent and connectivity with wetlands in a tropical river system (Borges et al., 2015a;Teodoru et al., 2015), the (intensively cropped) Seine River basin only contains a small proportion of wetlands. We identified CO 2 emissions from headwaters (1 st and 2 nd SOs) dominating the GHG source of the hydrosystem at 44%, like Marx et al. ( 2017), who estimated that 36% of CO 2 global riverine emissions originate from headwaters. In comparison to CO 2 emissions for the Seine basin, N 2 O emissions from headwaters represented 34% and CH 4 emissions only 25% of their respective total emissions (see Fig. 7). However in three US headwater streams draining land under mixed uses, Schade et al. ( 2016) found lower CO 2 emissions in these mainly sandy streambeds, than in the carbonated streambeds in the Seine River, but potentially high CH 4

and N 2 O emissions, probably due to organic-enriched streams where these authors reported a close relationship between total GHG emissions and concentrations of dissolved organic carbon (DOC).

In medium sectors of the Seine River, the decreasing contribution of groundwater as well as a decreasing ratio of terrestrial and riparian surface areas compared to the water volume could explain the lower emissions (Fig. 8). Higher emissions of the three GHGs in the higher SOs (6-7) can be interpreted as a response to WWTP effluents discharged downstream from the Paris conurbation (Fig. 8). As the water column was not fully anoxic even in the sector of effluent outlet, CH 4 may be linked to methanogenesis in the sediment that is rich in settled organic matter, while CO 2 is expected to result from organic matter respiration in both the water column and sediment (Battin et al. 2009;Vilmin et al. 2015;Garnier et al., 2009 and2013). For N 2 O emissions, in addition to denitrification in suboxic zones (at the scale of the bottom sediment-water interface, but also at the particle level (Garnier et al., 2007(Garnier et al., , 2009;;Jia et al., 2016;Xia et al., 2017), nitrification of the ammonium massively supplied by effluents was also a source of N 2 O emissions (Garnier et al., 2007(Garnier et al., , 2009;;Burgos et al., 2017). With lower gaseous exchange rates calculated in these higher SOs, the emissions of the three GHGs accounted for 26%, 52% and 38% of the total drainage network flux for CO 2 , CH 4 and N 2 O, respectively in the 6 th and 7 th SOs (see Fig. 7). Physiological processes enhanced by higher temperature did not systematically lead to higher GHG emissions in the summer, pointing to complex interactions between in-stream microbial processes (mineralization) and the contribution of groundwater (diffuse sources) and discharge of effluents (point sources). Upstream-downstream patterns of the three GHG concentrations, which were further detailed in 11 longitudinal profiles along the main stem of the Marne River and the lower Seine stem, showed "background" concentrations along the main stem of the Marne compared to the peaks observed downstream. The impact of the Parisian WWTPs was quite clear immediately downstream from their outlets and decreased within the 30 km downstream, partly due to dilution by the Oise River and in-stream processes. Farther downstream, GHG concentrations again increased, reflecting the major impact of the treated effluent from the Rouen conurbation. Although the number of inhabitant equivalents treated is 12 times higher in the Paris WWTPs than in Rouen's, the carbon load was only six times higher (i.e., a lower carbon abatement in the Rouen WWTP, with its smaller capacity), explaining the high impact. Such an impact of point source pollution, i.e., a discharge of labile organic matter into rivers, has already been reported to increase pCO 2 (Kempe, 1984). The significant relationships between (i) N 2 O, NH 4 + and NO 2 -and (ii) CO 2 , oxygen and DOC we found in our study corroborated the importance of in-stream processes that are mainly supported by anthropogenic inputs via urban effluents (i.e., mineralization of organic matter, denitrification, nitrification and lower oxygen concentration in the lower Seine River). In African rivers, Borges et al. (2015b) reported similar net heterotrophic dynamics for these aquatic ecosystems based on the relationships between pCO 2 , CH 4 and dissolved oxygen (O 2 ), despite lower domestic wastewater inputs in tropical systems, but with forested riparian zones and wetlands that also enriched the river in organic matter.

It is worth mentioning that only diffusive emissions of CH4 were taken into account, although 40% ebullition of indirect emissions could be added (Garnier et al., 2013). However taking the high contribution of CO 2 emissions in the drainage network into account would not affect the overall results. et al., 2013).

Among the 23.3% of agricultural emissions, the highest proportion (51%) was related to CH 4 although since the late 1970s, livestock has been confined to the periphery of the Seine basin (Mignolet et al., 2007). N 2 O emissions accounted for 33% and CO 2 for 16% of agricultural emissions. Whereas intensive cereal cropping contributed to N 2 O direct emissions though fertilization (Bouwman, 1996b;Cayuela et al., 2017), it also contributes to CO 2 emissions linked to the manufacture of fertilizers and direct fuel consumption for the cultivation of the 35,000 km 2 basin (Garnier et al., 2013).

Finally, for a highly human-populated basin such as the Seine, the riverine emissions accounted for only a small fraction (3.7%) of total emissions. However, cities have mitigation options, such as green technologies, and changes in lifestyle (drastic reduction in fossil energy consumption for individual vehicles, better insulation of buildings, etc.) as well as structural changes in agricultural production (e.g., more organic agriculture without mineral fertilizers,

Conclusion

In this study, we estimated emissions of greenhouse gases from the Seine hydrosystem characterized by a high population rate and intensive agriculture. At the regional scale of the Seine basin, CO 2 emissions (in CO 2 eq.) accounted for 6.4 and 9.5 times the amount of CH 4

and N 2 O emissions, respectively, in good agreement with the ~10 times found at the global scale.

We showed that the hydrological drainage network of the Seine River was oversaturated in GHGs (CO 2 , CH 4 , and N 2 O) with respect to their atmospheric concentrations. GHG emissions from the Seine hydrosystem accounted for only 3.7% of the total GHGs emitted from the basin as a whole. GHG emissions from the hydrosystem were also dominated by CO 2 emissions (95.3% of the 3.7%) and were interpreted as controlled by soil leaching and groundwater discharges in small SOs and by wastewater effluents along the main stem of the Seine River. Of the 73% of the GHG emissions originating from the nonagricultural sector, CO 2 emissions contributed 98%, and most came from the Ile-de-France region. For the agricultural sector, the 23.3% of GHG emissions mainly comprised CH 4 and N 2 O -51% and 33%, respectivelywhile CO 2 emissions accounted for only 16%.

In the future, modeling different scenarios for climate change or changes in anthropic pressure in the Seine basin (including agricultural practices and energy consumption) could enable us to propose actions to minimize the emissions of these greenhouse gases. , 1967) and stream orders (Strahler, 1952;1957) in the Seine basin.

Annex 1-2. Relationships between direct and indirect pCO2.

A relationships was established between direct and indirect pCO 2 measurements (n=108) for

Annex 1-3 Spatial and seasonal variations in gas transfer velocities (k) of CO2, CH4 and N2O

The difference in GHG concentrations between the atmosphere and water surfaces, and gas transfer velocities, control GHG emissions. Values of gas transfer velocities (k) were higher for all GHGs for small Strahler order (SOs) than for high SOs (Fig. 2). Our k calculations (Eq.

3) are directly related to slope, water velocity and water temperature. Consequently, k trends according to Strahler order were in more in agreement with the steeper slopes of the small headwater streams than with those of the main streams. Seasonal patterns and gas transfer velocity values were similar for CO 2 and N 2 O, with higher k in winter for small SOs than in summer, while the opposite patterns were observed for SOs 5-7. This resulted from the increase in water flow and water velocity in winter that affected k values more strongly in small SOs than in main streams, whereas in summer, higher water temperatures led to higher k in higher SOs than upstream. However, the k of CH 4 showed a different pattern with lower k in summer whatever the SO. Indeed, k depends on water temperature sensitivities of the Schmidt number of the different gases.

Fig. 1

 1 Fig. 1 Population density and main wastewater treatment plant capacities of the Seine River watershed (France) (INSEE, 2013 and the French water authorities -AESN 2005). In yellow, measurement stations located along the main stem of the Seine River (Marne River and the lower Seine) were sampled in 2010 (May 3-4; July 5-7; October 2-6 2010) in 2011 (May 17-19; August 23-28), in 2012 (April 4-10; August 28 to September 3), in 2013 (February 13-18; June 17-23 2013) and 2014 (May 13-17; September 9-12). One of the main stems of the Seine River is shown at the top of the figure with sampling stations and distance from Paris in kilometers (km=0).

N 2 O

 2 agricultural emissions were calculated from a review of emission coefficients for the major land use classes (croplands, grasslands and forests). An ongoing study aiming at refining N 2 O emissions by accounting for a relation between N 2 O emissions and mineral nitrogen fertilizers applied under different classes of rainfall would approximately amount 9 GgN-N 2 O yr -1 close to the 11.4 GgN-N 2 O yr -1 previously reported in Garnier et al. (2009), established from a different approach, and used here.

  We estimated nonagricultural GHG emissions based on data inWu et al. (2016) andStaufer et al., (2016) for the Ile-de-France Region, while data at the scale of the French administrative Departments were used for the rest of the Seine basin, excluding Ile-de-France (available at https://www.citepa.org/fr/, 2018/01/05, from CITEPA, French Interprofessional Technical Center for Studies on Air Pollution, last accessed 2018/11/05). CITEPA provides accurate census data on urban GHG emissions including energy transformation, manufacturing, the service sector and transport using the CORe Inventory AIR emissions methodology (CORINAIR, https://www.eea.europa.eu/publications/EMEPCORINAIR, last accessed 2018/11/05) from the European Environment Agency with a NUTS 3 resolution (French Departments). To analyze the nonagricultural emissions separately, we grouped the different sectors in three major classes:

Fig. 2

 2 Fig. 2 Greenhouse gas (CO 2 , CH 4 , N 2 O) concentrations in water (µgC-CO 2 .l -1 , µgC-CH 4 l -1 and µgN-N 2 O l -1 ) as a function of the stream order in the Seine drainage network in winter and summer averaged from the 14 campaigns conducted between 2010 and 2017. Whiskers are standard deviations between observed GHG concentrations.

Fig. 3

 3 Fig. 3 Greenhouse gas (CO 2 , CH 4 and N 2 O) and oxygen concentrations along the main stem of the Marne River (km -400 to 0) and the lower Seine River (km 40-400). Averaged concentrations for (left) nitrous oxide (N 2 O), ammonium (NH 4 + ) and nitrite (NO 2 -) in mgN l -1 ; (right) carbon dioxide (CO 2 ) and methane (CH 4 ) in µgC l -1 ,

Fig. 4

 4 Fig. 4 Relationships between (a) concentrations of N 2 O (µgN l -1 ) and NO 2 -(mgN l -1 ), (b) concentrations of N 2 O (µgN l -1 ) and NH 4 + (mgN l -1 ), (c) CO 2 (µgC l -1 ) and oxygen (mgO 2 l -1 ), and (d) CO 2 (µgC l -1 ) and dissolved organic carbon (DOC: mgC l -1 ). From top to bottom, example from the campaigns in May 2010, September 2012, September 2013 and September 2014.

  of CO 2 as a function of oxygen (O 2 ) and dissolved organic carbon (DOC) for each of the 11 campaigns. Corresponding values of mean discharges and temperatures (temp) for the duration of the campaign are indicated. *Slope significantly different from 0 for R 2 > 0.16 (n > 20).

  CH 4 and N 2 O) emissions from the hydrographic network (measurements made in this study), from the agricultural basin (including croplands, grasslands and forests according to Garnier et al. (2009 and 2013) and from nonagricultural sectors (data from CITEPA 2005 and from Wu et al. (2016) for the Ile-de-France region).∑ GHG: sum of the three GHGs by compartment and by gas.

Fig. 5

 5 Fig. 5 Greenhouse gas emissions (CO 2, CH 4 and N 2 O) from nonagricultural sectors (Gg CO 2 eq yr -1 ) in the Seine watershed including energy transformation-manufacturing, service sector, and transport (GIS treatments applied to CITEPA data; https://www.citepa.org/fr/, 2018/01/05)

Fig. 6

 6 Fig. 6 Greenhouse gas emissions (CO 2, CH 4 and N 2 O in Gg CO 2 eq yr -1 ) from the Seine hydrographic network and those from the watershed, divided into agricultural and nonagricultural (GIS treatments applied to CITEPA data; https://www.citepa.org/fr/, last accessed 2018/11/05); Data for Ile-de-France are from Wu et al. (2016) and Staufer et al. (2016).

Fig. 7

 7 Fig. 7 Greenhouse gas (CO 2 , CH 4 and N 2 O) emissions from the Seine hydrographic network (yearly average of 14 campaigns (2010-2017). The pie charts represent the proportion of GHG emissions expressed in GWP. Percentage contributions are given for small (1 st to 2 nd SO), intermediate (3 rd to 5 th SO) and large (6 th to 7 th SO) rivers in the Seine watershed.

Fig. 8

 8 Fig. 8 Schematic representation of the sources of CO 2 , CH 4 and N 2 O emissions from the Seine hydrosystem. OM: organic matter; NH 4 + : ammonium

Fig. 9

 9 Fig.9Map of the lithology (Albinet, 1967) and stream orders(Strahler, 1952; 1957) in the Seine basin.

Fig. 10

 10 Fig. 10 Gas transfer velocity for CO2, CH4, N2O calculated according to the fifth equation in table 2 in Raymond et al. (2012) as a function of stream order (SO) in the Seine basin in winter (blue) and in summer (red). Whiskers are standard deviations between observed GHG concentrations

  Table 1-1).

	No relationship was found between N 2 O and NO 3	-. CO 2 was positively and significantly
	correlated with DOC (six out of 11 campaigns, R 2 > 0.27; n = 23) and negatively correlated
	with oxygen (five out of 11 campaigns, R 2 > 0.35), but no correlation was found between CH 4

Table 1 -

 1

1 Parameters of the linear relationships (slope and R²) of N 2 O as a function of nitrite (NO 2 -

Table 1 -

 1

2 Comparative greenhouse gas (Gg CO 2 eq yr -1 of CO 2,

1.4.3. Direct CO 2 , CH 4 , N 2 O emissions from the Seine basin: agricultural and nonagricultural emissions

  France with 12 M inhab. vs. 16 M inhab. for the entire Seine basin) is not surprising, and is in line with results reported for other large cities(Pataki et al., 2006). Although human respiration, which accounts for 10% of the total (1 kg CO 2 inhab .-1 yr -1 , Prairie and Duarte, 2007), was included in the estimates as the measurements came from tower fluxes and atmospheric inversion(Breón et al., 2015; Wu et al., 2016), we did not subtract this flux. Urban agriculture and many other small sectors (See Table1-1A, Wu et al., 2016), reported to account for 2.7%, were not taken into account either. On the whole, according toBréon et al. (2015), we can consider that in megacities such as Paris and it conurbation, net CO 2 fluxes are dominated by fossil fuel emissions. These Ile-de-France fuel emissions are hypothesized to account for 12% of those from France as a whole (Boden

	Indirect GHG emissions from the hydrographic network accounted for 3.7% of the total
	emissions, 23.3% being linked to agricultural activities and land use, 73.0% to nonagricultural
	uses (dominated by the urban sources in the Ile-de-France region).
	Such a high proportion of nonagricultural GHG (heating, transport, energy and industry) from
	a very highly populated area (Ile-de-

  the Seine River basin(Marescaux et al., 2018) to reduce pCO 2 indirect calculation bias (seeAbril et al., 2015b).

	𝒄𝒐𝒓𝒓𝒆𝒄𝒕𝒆𝒅 𝒑 𝑪𝑶 𝟐 = 𝟏𝟎	( 𝒍𝒐𝒈(𝒄𝒂𝒍𝒄𝒖𝒍𝒂𝒕𝒆𝒅 𝒑 𝑪𝑶 𝟐 𝟎.𝟖𝟓	)-𝟎.𝟓𝟏	)	(Marescaux et al., 2018a)
	where calculated pCO 2 is partial pressure of carbon dioxide (ppmv) calculated from pH, total
	alkalinity, and water temperature using the CO2SYS software (Pierrot et al., 2006). The
	carbonate dissociation constants (K1 and K2) applied are from Millero, (1979) with zero
	salinity. CO 2 solubility is from Weiss, (1974).

Annex 1-5 Results of the statistical differences between mean of greenhouse gas concentrations by stream order.

				1.6.6.	5 6	1689 2001	47 55	94 111	93 110			131 154	10 14	110 126	241 280
						7	2362	59	118	118			240	19	203	443
				1.6.5. Stream orders
					CO 2		1		2	3		4	5	6	7
					1		[GHG]	sd	p < 0.05*	95% C.I. p < 0.05*	p < 0.05*	fGHG p < 0.05*	sd p < 0.05*	95% C.I. p < 0.05*
					2				<	> p < 0.05*	p < 0.05*	p < 0.05*	p < 0.05*	< p > 0.05	>
					3	1 2	0.63 1.74	0.15 0.34	0.32 1.07	0.94 2.42	p < 0.05*	34 78 p < 0.05*	9 16 p > 0.05	16 45 p < 0.05*	52 111
				summer	4 5 6	3 4 5	1.47 2.25 1.20	0.37 0.20 0.17	0.74 1.85 0.87	2.21 2.65 1.53			64 p > 0.05 102 49	17 p < 0.05* 12 p < 0.05* 8	29 p < 0.05* 78 p < 0.05* 32 p < 0.05*	98 126 66
	-1	l			7	6	1.43	0.13	1.17	1.69	-1	d	56	8	40	73
		CH 4 , µgC	orders Stream	winter	CH 4 1 2 3 4 5	7 1 2 3 4 5 6	3.47 0.60 1 0.81 0.75 1.03 0.45 0.88	0.36 0.09 0.15 0.08 0.22 0.09 0.09	2.76 0.43 p > 0.05 2 0.51 0.59 0.60 0.26 0.71	4.18 0.78 3 p < 0.05* 1.12 0.90 p > 0.05 1.46 0.64 1.06	, kgC p < 0.05* 4 CH 4 p > 0.05 p < 0.05*	171 65 5 p < 0.05* 68 55 p > 0.05 77 22 45 p > 0.05 p > 0.05	25 11 p < 0.05* 6 14 7 p > 0.05 18 6 7 p > 0.05 p > 0.05 p > 0.05	121 44 p < 0.05* 7 40 41 p < 0.05* 41 11 32 p < 0.05* p < 0.05* p < 0.05*	221 87 97 69 113 34 59
					6	7	1.51	0.34	0.82	2.18			100	26	48 p < 0.05*	152
					7	1	1.22	0.18	0.86	1.58			117	26	66	168
				summer	N 2 O 1 2	2 3 4 5	0.79 0.55 1 0.54 0.50	0.12 0.05 0.06 0.04	0.55 0.45 p < 0.05* 2 0.41 0.42	1.03 0.64 3 p < 0.05* 0.66 0.57 p > 0.05	4 p < 0.05* p > 0.05	51 27 p < 0.05* 5 30 27 p > 0.05	13 7 p < 0.05* 6 9 7 p > 0.05	24 13 p < 0.05* 7 12 12 p < 0.05*	78 41 48 41
	-1	µgN l			3 4	6 7	0.75 3.10	0.11 0.26	0.52 2.57	0.98 3.63	-1	d p > 0.05 kgN	56 p > 0.05 400 p > 0.05	16 p > 0.05 61 p < 0.05*	24 p < 0.05* 279 p < 0.05*	89 521
		O, N-N 2			5 6	1 2	1.65 0.59	0.29 0.05	1.08 0.49	2.23 0.69		O, N-N 2	250 31	59 p > 0.05 9	131 p < 0.05* 13 p < 0.05*	368 49
				winter		3 4 5	0.61 0.53 0.96	0.06 0.04 0.46	0.48 0.44 0.05	0.73 0.62 1.87			29 20 53	9 7 42	11 5 -32	48 35 138
						6	0.56	0.13	0.31	0.81			16	12	-8	40
						7	2.07	0.27	1.53	2.62			202	43	116	287
						1	3449	112	225	225			351	21	310	661
						2	2114	53	107	106			191	11	168	360
	-1	µgC l , CO 2		summer		3 4 5 6 7 1	1959 1548 1465 1731 2292 2168	51 39 37 52 57 72	101 79 73 104 114 144	102 79 73 103 114 144	-1	d MgC , CO 2	175 145 130 162 287 545	11 9 11 16 24 29	152 127 108 130 238 487	327 272 238 293 525 1032
				Winter		2 3	2410 2095	67 56	134 112	134 110			321 236	16 13	288 211	609 447
						4	1633	43	86	86			173	10	154	328
															33 34

Annex 1-6 Exact locations, mean and standard deviations of water quality parameters (chlorophyll a (Chl. a), total alkalinity, pH, dissolved oxygen (O2), and dissolved silica (DSi)) of the sampling stations located along the main stem of the basin.

		Coordinates (EPSG 3857)	(Paris = 0) km	Chl. a (µg/l)	Water temperature (°C)	Alkalinity (mmole l -1 )	pH (-)		O2 (mg l -1 )	DSi (mg l -1 )
	Name of the sampling station			mean	SD	mean	SD	mean	SD	mean	SD	mean	SD	mean	SD
	Tancarville	49°28'21.2"N 0°27'51.5"E	337.00	33.20	22.18	17.05	2.4	4.17	0.42	8.09	0.18	7.41	0.74	3.31	0.90
	Caudebec	49°31'13.0"N 0°44'50.1"E	310.50	14.22	10.05	17.73	2.0	4.14	0.41	8.05	0.21	7.48	0.71	3.07	1.10
	Duclair	49°28'47.3"N 0°52'34.0"E	278.00	11.63	12.30	17.61	2.5	4.05	0.51	7.96	0.21	7.22	1.09	3.06	1.24
	Bouille	49°21'07.8"N 0°56'03.6"E	259.70	12.20	14.17	17.88	2.3	3.99	0.66	7.94	0.18	7.14	0.80	2.97	1.32
	Bas Dock	49°26'36.9"N 1°03'51.9"E	251.30	28.06	64.35	17.75	2.4	4.06	0.65	8.11	0.40	7.75	0.93	3.23	1.27
	Oissel	49°20'13.8"N 1°05'36.4"E	229.40	24.53	50.89	18.00	2.3	4.01	0.61	8.02	0.23	8.20	0.83	2.83	1.39
	Elbeuf	49°17'36.9"N 1°00'35.0"E	218.97	26.59	51.02	18.00	2.4	3.95	0.65	8.03	0.24	8.56	1.09	2.88	1.33
	Poses	49°18'35.9"N 1°14'10.9"E	202.00	21.57	42.48	18.26	2.5	3.99	0.52	7.98	0.23	8.44	1.40	2.78	1.34
	Vernon	49°05'44.9"N 1°29'15.9"E	150.00	15.76	31.64	17.99	2.9	3.90	0.66	7.93	0.24	8.13	0.57	2.78	1.29
	Porcheville	48°57'59.4"N 1°46'35.3"E	101.00	8.39	10.53	17.96	2.8	4.05	0.47	7.88	0.26	7.23	0.87	2.80	1.24
	Poissy	48°56'12.3"N 2°02'19.6"E	76.00	6.14	6.54	17.85	2.9	4.06	0.45	7.84	0.19	7.72	0.99	2.86	1.32
	Conflans	48°59'19.2"N 2°04'55.2"E	70.00	3.51	3.33	18.24	2.9	3.68	0.42	7.85	0.21	7.12	1.28	2.52	1.16
	Maison Laffite	48°56'41.1"N 2°09'30.7"E	48.00	4.57	3.72	18.12	3.0	3.72	0.46	8.05	0.39	7.43	1.01	2.25	1.11
	Saint Maurice	48°49'00.4"N 2°25'11.9"E	0.00	19.58	52.80	17.50	3.2	4.18	0.39	8.17	0.26	9.52	2.16	2.25	1.11
	Neuilly sur Marne	48°51'13.0"N 2°31'57.9"E	-30.00	10.15	19.12	17.43	2.9	4.29	0.39	8.17	0.21	8.94	1.50	2.32	1.19
	Annet	48°54'59.0"N 2°43'08.1"E	-50.00	9.19	16.06	17.18	2.8	4.31	0.38	8.17	0.17	8.97	1.11	2.22	1.10
	Sammeron	48°58'10.8"N 3°19'15.0"E -120.00	6.80	8.53	17.16	3.1	3.97	0.39	8.16	0.17	8.89	0.84	1.82	0.85
	Saulchery (Nogent l'Artaud) 49°04'31.7"N 3°38'12.5"E -150.00	4.76	4.49	17.17	3.0	3.93	0.35	8.12	0.30	8.64	0.97	1.65	0.76
	Dormans	48°59'43.0"N 4°14'38.1"E -180.00	4.68	3.48	17.16	3.3	3.69	0.45	8.11	0.26	8.58	0.74	1.44	0.59
	Matougues	48°37'20.9"N 4°42'01.9"E -260.00	3.12	1.53	16.49	3.3	3.62	0.53	8.04	0.17	8.60	0.97	1.28	0.62
	Moncetz l'Abbaye	48°38'49.0"N 4°39'12.7"E -335.00	5.06	3.36	16.23	3.7	3.47	0.59	8.12	0.18	8.95	1.22	0.98	0.56
	Arrigny	48°37'20.9"N 4°42'01.9"E -337.00	7.15	6.95	16.30	4.0	3.34	0.79	8.03	0.52	8.63	1.70	1.08	0.59
	Larzicourt	48°37'47.2"N 4°42'34.0"E -340.00	5.83	3.96	15.11	2.7	4.17	0.43	8.15	0.39	8.69	1.46	1.21	0.81

dissolved organic carbon (DOC) in mgC l -1 , and dissolved oxygen in mgO 2 l -1 . The pCO 2 values were calculated from pH, temperature and alkalinity using CO2SYS software(Pierrot et al., 2006). These data are partly described inGarnier et al. (2009 and 2013).

Acknowledgements

The C-CASCADES (https://c-cascades.ulb.ac.be/) project of which this study was a part, received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 643052. Audrey Marescaux benefitted from a PhD grant. The PIREN-Seine programme and the HydroGES project are also greatly acknowledged for their support. Many thanks are due to Abdelkader Azougui, Sébastien Bosc, Anunciacion Martinez Serrano, and Benjamin Mercier for their kind participation in the fieldwork and for their assistance with chemical analyses in the lab.

Goulven Laruelle is also acknowledged for his help with statistical analyses. Vincent Thieu (assistant-professor at the University Pierre and Marie Curie, Paris) and Josette Garnier (Research Director at the CNRS, Centre National de la Recherche Scientifique, France) are co-supervisors of the PhD candidate. We thank the four anonymous reviewers for their constructive comments.

The datasets generated during the current study are available from the corresponding author on reasonable request (Audrey.marescaux@sorbonne-universite.fr)

Affiliations

Sorbonne Universités, Université Pierre et Marie Curie, Centre National de la Recherche Scientifique, Institut Pierre Simon Laplace, UMR 7619 METIS, Paris, France

Data availability

Author contribution statement

All the authors contributed to the design of the study. JG and VT are co-supervisors of the PhD. AM participated as a PhD student in the field campaigns and chemical analyses in the laboratory. AM wrote the first draft of the manuscript, and all co-authors helped interpret the data and write the article.

Corresponding authors : Audrey Marescaux, Audrey.maresaux@sorbonne-universite.fr

Competing interests :

The authors declare no competing personal or financial interests.

The datasets generated during the current study are available from the corresponding author on reasonable request