Lionel Eyraud-Dubois
email: lionel.eyraud-dubois@inria.fr

Cristiana Bentes

Algorithms for Preemptive Co-scheduling of Kernels on GPUs

Modern GPUs allow concurrent kernel execution and preemption to improve hardware utilization and responsiveness. Currently, the decision on the simultaneous execution of kernels is performed by the hardware, which can lead to unreasonable use of resources. In this work, we tackle the problem of co-scheduling for GPUs in high competition scenarios. We propose a novel graphbased preemptive co-scheduling algorithm, with the focus on reducing the number of preemptions. We show that the optimal preemptive makespan can be computed by solving a Linear Program in polynomial time. Based on this solution we propose graph theoretical model and an algorithm to build preemptive schedules which minimizes the number of preemptions. We show, however, that finding the minimal amount of preemptions among all preemptive solutions of optimal makespan is a NP-hard problem. We performed experiments on real-world GPU applications and our approach can achieve optimal makespan by preempting 6 to 9% of the tasks.

I. INTRODUCTION

Graphics Processing Units (GPUs) are throughputoriented co-processors that are witnessing a rapid increase in the amount of computing resources. To avoid keeping these growing resources underutilized and improve performance, concurrent kernel execution (CKE) has been proposed and showed improved GPU throughput and resource utilization [START_REF] Adriaens | The case for GPGPU spatial multitasking[END_REF], [START_REF] Pai | Improving GPGPU concurrency with elastic kernels[END_REF], [START_REF] Zhao | Classification-driven search for effective sm partitioning in multitasking gpus[END_REF].

Recently, GPU architectures also provide hardware preemption. The preemption can occur at coarse and fine-grain granularity: thread level and instruction level. In thread level preemption, the threads that are executing on the SMs have to be completed before the preemption actually occurs. This type of preemption reduces the amount of context to be saved on the preemption event, since the threads finished their work. In NVIDIA GPUs, the switching of kernels in thread boundary can complete in less than 100 µs [START_REF]Nvidia gp100 pascal whitepaper[END_REF]. In instruction level preemption, however, all thread processing stops at the current instruction and the threads contexts have to be saved. This type of preemption involves substantially more state information, because all the registers of the executing threads must be saved, which takes significant memory bandwidth.

In this scenario, scheduling decisions are key to increase resource utilization and improve responsiveness. However, GPU resource allocation is performed by the hardware, that assigns as many resources as possible for one task and then assigns the remaining resources to the next task, if there are sufficient leftover resources [START_REF] Hu | Run-time performance estimation and fairness-oriented scheduling policy for concurrent GPGPU applications[END_REF]. This allocation policy has shown to lead to an unreasonable use of resources [START_REF] Pai | Improving GPGPU concurrency with elastic kernels[END_REF], and to be influenced by the order in which the kernels are launched [START_REF] Shekofteh | ccuda: Effective co-scheduling of concurrent kernels on gpus[END_REF], [START_REF] Cruz | Maximizing the gpu resource usage by reordering concurrent kernels submission[END_REF]. Therefore, the launching of kernels to the GPU has to be wisely performed in order to avoid an unbalanced occupation of the GPU resources and its consequent negative effect on the system performance.

In this work, we study the problem of co-scheduling kernels to the GPU for future scenarios that present high competition and the GPU will behave as multiprogrammed devices, such as CPUs are in the present. Although the problem of co-scheduling applications on CPU multicore nodes has been well studied in the past [START_REF] Shantharam | Speedup-aware coschedules for efficient workload management[END_REF], [START_REF] Aupy | Coscheduling algorithms for high-throughput workload execution[END_REF], [START_REF] Sun | Scheduling parallel tasks under multiple resources: List scheduling vs. pack scheduling[END_REF], they are not directly applicable to the GPU environment due to the GPU hardware allocation policies. We propose a novel graph-based preemptive coscheduling solution, that defines the kernels submission order focusing on reducing the number of preemptions. The idea is to exploit the kernels interference profile provided by previous works analysis of how the kernels resource usage impacts the interference in their co-execution [START_REF] Carvalho | Analysis and characterization of gpu benchmarks for kernel concurrency efficiency[END_REF], [START_REF] Ukidave | Mystic: Predictive scheduling for gpu based cloud servers using machine learning[END_REF]. More formally, we deal with the following problem: given a co-scheduling speedup matrix S, where S i,j is the speed at which kernel i makes progress when running with j, and the duration of each kernel, what is the best way to co-schedule them, in order to minimize their makespan. We first propose a Linear Programming model to generate an optimal preemptive schedule that minimizes the makespan of the kernels. The optimal solution then produces a coexecution graph G where each node i represents one kernel and an edge connecting i to j indicates that kernels i and j should co-execute. From G, we propose the algorithm CATERPILLARSPLIT to generate kernel submissions with the minimum number of preemptions. However, we show that the problem of minimizing the number of preemptions directly from the speedup matrix S is NP-hard.

We used 60 kernels from real-world applications obtained from the main benchmark suites for evaluating GPUs, Rodinia, Parboil and SHOC, and observed that our algorithms produce very efficient schedules. We obtain the optimal makespan by preempting between 5% and 10% of the kernels depending on the setting.

The rest of the paper is organised as follows. In Section II, we review related works. In Section III, we present the notations and the scheduling model used throughout the paper. Section IV shows how to obtain preemptive schedules with minimal makespan, and how to minimize the number of preemptions. Finally, Section V gives an experimental validation of our algorithms on realistic instances.

II. RELATED WORK

Enabling efficient multiprogramming on GPUs is receiving a lot of attention from the research community in recent years. Software techniques, such as reordering were proposed to find a good submission order to improve resource utilization [START_REF] Cruz | Maximizing the gpu resource usage by reordering concurrent kernels submission[END_REF], [START_REF] Wende | On improving the performance of multi-threaded CUDA applications with concurrent kernel execution by kernel reordering[END_REF], [START_REF] Li | A power-aware symbiotic scheduling algorithm for concurrent GPU kernels[END_REF]. Other software techniques propose modifying the granularity of the kernels to create more concurrency opportunities [START_REF] Pai | Improving GPGPU concurrency with elastic kernels[END_REF], [START_REF] Zhong | Kernelet: High-throughput GPU kernel executions with dynamic slicing and scheduling[END_REF], [START_REF] Ravi | Supporting GPU sharing in cloud environments with a transparent runtime consolidation framework[END_REF]. Hardware techniques were also proposed to divide the GPU resources among the concurrent kernels, called spatial multitasking [START_REF] Adriaens | The case for GPGPU spatial multitasking[END_REF], [START_REF] Liang | Efficient GPU spatial-temporal multitasking[END_REF].

The non-preemptive co-scheduling of kernels of different applications on the GPU have also been studied. The work of Margiolas and O'Boyle [START_REF] Margiolas | Portable and transparent software managed scheduling on accelerators for fair resource sharing[END_REF] transparently modifies the kernel code in terms of the thread blocks size in order to improve fairness in the assignment of the GPU resources among different kernels. Chen et al. [START_REF] Chen | Baymax: Qos awareness and increased utilization for non-preemptive accelerators in warehouse scale computers[END_REF] propose a task duration predictor and a task reordering mechanism based on the predictions to guarantee QoS. Ukidave et al. [START_REF] Ukidave | Mystic: Predictive scheduling for gpu based cloud servers using machine learning[END_REF] present an interferenceaware mechanism for co-scheduling on GPUs based on machine learning to predict whether kernels can share a GPU efficiently. Wen et al. [START_REF] Wen | Maxpair: Enhance opencl concurrent kernel execution by weighted maximum matching[END_REF] propose a graph-based algorithm to schedule kernels in pairs. The recent work of Shekofteh et al. [START_REF] Shekofteh | ccuda: Effective co-scheduling of concurrent kernels on gpus[END_REF] proposes the co-scheduling of pair of kernels with different execution behaviors. They use kernel slicing to improve the choice of kernels pairs for co-scheduling.

There are also some works in exploiting kernel preemption to provide fairness, responsiveness, and quality of service of applications running on GPUs. Xu et al. [START_REF] Xu | Warpedslicer: efficient intra-sm slicing through dynamic resource partitioning for gpu multiprogramming[END_REF] proposed a deadline-aware dynamic GPU partitioning to improve the responsiveness when a GPU is shared by tasks with strict and non-strict deadlines. Wang et al. [START_REF] Wang | Quality of service support for fine-grained sharing on gpus[END_REF] proposed QoS mechanisms for fine-grained GPU sharing, where kernels with QoS requirements receive enough resources to reach its goals, and the remaining resources are assigned to kernels without QoS requirements. Wang et al. [START_REF] Wang | Simultaneous multikernel gpu: Multi-tasking throughput processors via fine-grained sharing[END_REF] proposed Simultaneous Multikernel (SMK) that allows fine-grain sharing within each SM, kernels with complimentary resource usage are co-scheduled in the same SM to achieve resource fairness and better utilization. Chen et al. [START_REF] Chen | Effisha: A software framework for enabling effficient preemptive scheduling of gpu[END_REF] proposed a compiler-runtime software solution for priority-based preemptive scheduling on GPUs, that transforms the kernel for voluntary preemptions. Jin et al. [START_REF] Jin | Preemption-aware kernel scheduling for gpus[END_REF] proposed a preemption-aware scheduler that use cache miss behavior to classify the kernels into compute-intensive and memory intensive, and predict the performance of complementary execution of pairs of kernels based on their classification.

Compared to the other approaches, we propose a preemptive algorithm that use optimization strategies to find a global optimal solution rather than local or greedy solutions. In addition, we are the first to propose an algorithm to reduce the number of preemptions in coscheduling.

III. MODEL AND NOTATIONS

In this paper, we consider the problem of scheduling a set T of n independent tasks on a GPU with two streams. We assume that we know for each task i its execution time p i , and for each pair of task (i, j), we know the speed S i,j at which task i makes progress when running at the same time as task j. For ease of notation, we will assume that S i,i = 1.

Given this input data, we consider schedules σ defined as a succession of intervals I l , with duration d l , during which the set of running tasks is R l , where

1 ≤ |R l | ≤ 2. If i ∈ R l , its companion task in R l is either j if R l = {i, j} or i if R l = {i}, and is denoted c(R l , i).
A schedule is valid if all tasks have progressed to completion, i.e. ∀i ∈ T , l|i∈R l d l S i,c(R l ,i) = p i . The makespan of a schedule is its total duration, l d l . We are interested in the following problem: Problem 1 (MINMAKESPAN). Given input data p i and S i,j , find a valid schedule of minimal makespan.

In a preemptive schedule, we can define the number of preemptions of task i as P (σ, i), the number of intervals required to partition X i minus one. The total number of preemptions of a schedule σ is P (σ) = i∈T P (σ, i). a) Remark.: If for a pair a task (i, j), we have S i,j + S j,i ≤ 1, it is not worth it to schedule tasks i and j together. Indeed, it is never worse to replace a time interval of length d where they are together by a time of length dS i,j for task i alone followed by a time of length dS j,i for task j alone. Thus we can assume that ∀i, j, S i,j + S j,i is either 0 or more than 1.

IV. PREEMPTIVE SCHEDULES

A. Optimal Preemptive Schedule

The first remark from the previous definitions is that the makespan of a preemptive schedule σ does not depend on the ordering of its intervals, but only on their duration. It can thus be described with n(n-1) 2 variables x e for e ∈ {{i, j}|i, j ∈ T } describing the duration of the interval during which the set of running tasks is e. For this reason, given a speed matrix S, we introduce the graph G(S) = (T , E(S)) where the set of vertices is T , and there is an edge between i and j if S i,j + S j,i > 1.

Note that the graph G(S) also contains loops (edges from i to i).

This description means that we can express the MIN-MAKESPAN problem as the following Linear Program, called (PLP): In any optimal solution, at least |E(S)| constraints are saturated, thus at most n inequalities are strict. This implies that at most n x c variables are positive, and thus any optimal solution contains at most n different intervals. In the following, we denote by x * an optimal solution of this Linear Program. This solution yields the optimal makespan for problem MINMAKESPAN, and any ordering of the obtained intervals incurs at most n preemptions (the total number of task appearances is at most 2n, and the first appearance of each task does not count as a preemption).

In the remainder of this Section, we present how to compute an ordering of these intervals to minimize the number of preemptions. To this end, we introduce the graph G(x * ):

Definition 1 (Graph G(x) associated with a solution x). Given a solution x of the (PLP), we define G(x) as the graph with one vertex per task, in which there is an edge between tasks i and j if and only if x {i,j} > 0.

By definition, G(x) is a spanning subgraph of G(S). The above result ensures that G(x * ) has at most n edges. But we can actually prove a stronger statement:

Proposition 1. Any connected component of G(x * ) with k vertices has at most k edges.
Proof. If we rewrite (PLP) with only the variables x e such that x * e > 0, we obtain exactly the same solution x * . In this restricted (PLP), the connected components of G(x * ) produce independent problems, and for each of them the above analysis on the number of constraints and variables is still correct. Definition 2. A connected graph with at most as many edges as vertices is called a pseudo-tree, and can have at most one cycle. A pseudo-forest is a graph in which each connected component is a pseudo-tree.

Theorem 1. For any optimal solution x * , G(x * ) is a pseudo-forest.

B. Minimizing the number of preemptions

In this Section, we describe how to minimize the number of preemptions of a preemptive solution. We start by characterizing the graphs G(x * ) from which it is possible to build a non-preemptive schedule. As shown on Figure 1a, if the graph is a single path we can build a schedule without any preemption, just by following the path. Case 1b shows that this holds even if the graph is a caterpillar, i.e. has several nodes of degree 1 connected to a central path. In case 1b the path is A-B -E -G-H, with C, D and F (shown in lighter color) connected to it. Case 1c shows that this no longer holds true when nodes connected to the path have a more complicated structure. Here the path is A -B -C -F -G, with D -E connected to it, and it is necessary to have a preemption (here C is preempted). Case 1d shows that any cycle incurs at least one preemption.

This brings us to the following Lemma:

Lemma 1. The graph G of a preemptive solution can be ordered in a non preemptive way if and only if it is a vertex-disjoint collection of caterpillars.

3 A B C D E t R 1 R 2 A B C D E (a) Simple path A B E G H C D F t R 1 R 2 A B C D E F G H (b) Caterpillar graph A B C F G D E t R 1 R 2 A B C D E C F G (c) More complex tree A B C D t R 1 R 2 A B C D A (d) Cycle

Definition 3 (Caterpillar).

A graph G is a caterpillar if it contains a path P , such that all nodes of G that do not belong to P are incident to only one edge, directly connected to a node of P . We call the path P the internal path, and all nodes and edges of this path are called internal.

From the above discussion, it is natural to consider that preempting a task can be modeled by splitting the corresponding vertex of the graph, so that the task can appear at several places in the schedule. When a vertex is split, its neighbors are partitioned in two sets: the first set is attached to the first copy of the vertex, and the second set to the second copy.

The problem that we are interested in is:

Problem 2 (CATERPILLARSPLIT). Given a graph G, find a minimum number of node splitting operations to obtain a graph G which is a collection of vertex-disjoint caterpillars.

Of course, this problem can be solved separately on each connected component of G. We start by analyzing problem CATERPILLARSPLIT on trees, and will move to pseudo-trees later.

1) Solving the problem on trees: On trees, the problem CATERPILLARSPLIT can be formulated this way: Problem 3. Given a tree T , find a partition of the edges of T into a minimum number of edge-disjoint caterpillars.

Indeed, two different caterpillars in the result can share at most one node, and thus the number of caterpillars in a solution is exactly one plus the number of node splitting operations required.

To solve this problem, we make a number of observations in the following lemmas, illustrated on Figure 2. We assume that the tree T is rooted at some arbitrary root r, allowing to define the height of a vertex in T .

Definition 4 (height of a vertex). The height of a vertex v of a rooted tree T is the length of the longest downward path to a leaf from v.

By definition, leaves of T have height 0, and if the children of a vertex v are all leaves, then v has height 1. For any node v, we call leaves of v the children of v which are leaves in T .

Lemma 2 (Greedy for vertices of height 1). Assume that T contains a vertex t of height 2 connected to at least 3 vertices of height 1 u, v, w. There exists an optimal solution containing the caterpillar whose internal path is (u, t, v), with their leaves attached.

Proof. We first show that there exists an optimal solution in which nodes u, v and w are all internal nodes of their respective caterpillars in which they are connected to t. Indeed, if any of them (say node u) is a leaf node in the caterpillar C 1 containing edge (u, t), then the solution necessarily contains another caterpillar C 2 with the edges connecting u to its leaves. We can thus disconnect edge (u, t) from caterpillar C 1 and add it to caterpillar C 2 . Both C 1 and C 2 remain valid caterpillars, and both solutions contains the same number of caterpillars.

Let us consider such an optimal solution, in which u, v and w are internal nodes. Since no path connects all three of them, they can not be in the same caterpillars in this solution. Consider the caterpillar C u which contains u, the caterpillar C v which contains v, and the caterpillar C w which contains w. If C u = C v , we can disconnect both caterpillars at node t and reconnect them pairwise, so that u and v belong to the same caterpillar, and the other parts are connected as well. If C u = C v we do not need to do this step. Leaves attached at t can be freely attached to this (u, t, v) caterpillar. Any other node connected to t as a leaf of either C u or C v can be attached to C w . The resulting solution has the same number of caterpillars, and contains the caterpillar (u, t, v) with their leaves attached, proving our lemma.

Lemma 3 (Special case for two vertices of height 1). Assume that T contains a vertex t of height 2 connected to exactly 2 vertices of height 1, u and v. Denote by s the father of t. There exists an optimal solution containing the caterpillar (u, t, v) with their leaves attached and with edge (t, s) also included.

Proof. By definition, u and v each have at least leaf, which we denote by u and v . Consider any optimal solution in which edges (u, u ) and (v, v ) are part of two different caterpillars C u and C v . One of these caterpillars contains edge (t, s) in its internal path, otherwise they can be merged together and the solution is not optimal. Assume without loss of generality that C u contains (t, s). It is possible to split C u at node s, and merge C v with the resulting part. This yields a solution with the same number of caterpillars as an optimal solution, thus it is optimal.

Consider now any optimal solution which contains the caterpillar (u, t, v) without edge (t, s). We can assume that all leaves of t are connected to this (u, t, v) caterpillar. Denote C the caterpillar of this solution which contains (t, s). By assumption, the only edges connected to t which do not lead to leaves are (t, u), (t, v) and (t, s). This implies that edge (t, s) is an external edge of caterpillar C. It is thus possible to remove it from caterpillar C and attach it to caterpillar (u, t, v): the solution produced is still optimal.

Lemma 4 (Contract lonely vertices of height 1). Assume T contains a vertex t of height 2 which has exactly child of height 1, u. Then in any optimal solution, node u belongs to only one caterpillar.

This implies that solving CATERPILLARSPLIT on T is equivalent to solving CATERPILLARSPLIT on T where edge (t, u) is contracted (i.e., nodes t and u are merged).

Proof. Consider any solution in which node u belongs to several caterpillars, and denote by C the caterpillar which contains edge (t, u). Since t has only one child of height 1, the internal path of this caterpillar is either empty or ends with the edge connecting t to its parent. In both cases, it is possible to add edge (t, u) to this path. All leaves of u can thus be added to caterpillar C, decreasing the total number of caterpillars of the solution, which implies that the considered solution is not optimal. These lemmas suggest an algorithm to solve CATER-PILLARSPLIT on trees, which is detailed in Algorithm 1. The optimality of this algorithm comes directly from the previous Lemmas: for each caterpillar added to S, we have a proof that there exists an optimal solution containing this caterpillar. Since a tree T that does not contain any vertex of height 2 is a caterpillar, the produced solution is valid and optimal.

2) Solving the problem on pseudo-trees: We now consider the general problem CATERPILLARSPLIT on pseudo-trees. Consider a pseudo-tree T which is not a tree: it either contains a self loop (an edge (i, i)) or one proper cycle C. If T contains a self loop (i, i), then an equivalent problem is obtained by replacing this loop with an edge connecting i to a new node i which represents the time during which task i must execute by itself. This replacement yields a tree, on which we can apply Algorithm 1.

If T contains a proper cycle C, it is easy to see with a similar argument as above that the number of caterpillars of any solution is equal to the number of split operations. We are thus again interested in minimizing the number of caterpillars used to partition the edges of T .

For each u ∈ C, the subgraph of nodes reachable from u without going through C is a tree T u . By rooting T u at u, all the Lemmas proven above are still valid, with one exception: Lemma 3 cannot be applied if the vertex t of height 2 is u, since u has no father in T u . This implies that iteratively applying the Lemmas as in Algorithm 1 yields a cycle C in which the subtrees T u can have 4 possible shapes (see Figure 3 If T u is of shape C or D, we call the subtree corresponding to each vertex of height 1 in T u a leg of u. Each u ∈ C can thus have 0, 1 or 2 legs. Note that for shapes C and D, node u can have any number of leaves in T u .

If two legs are separated on the cycle by at least two nodes, or by one node of shape B, we can reduce the problem with the following lemmas: Lemma 5. Assume the cycle C contains three consecutive nodes u, v, w, where u and w have at least one leg, and node v has shape B. Then there exists an optimal solution which contains the caterpillar made of one leg of u, T v and one leg of w, with leaves of u and w attached. If u and/or w has only one leg, then this caterpillar also contains the next edge of the cycle in the corresponding direction, as an external edge.

Proof. This proof is very similar to the proofs of Lemma 2; in the interest of brevity we only present the main points. In the first part, we prove that there exists an optimal solution in which edges (u, v) and (v, w) are part of the same caterpillar: from any optimal solution in which this is not the case, a case analysis on whether edges (u, v) and (v, w) are internal edges in their respective caterpillar shows that we can always obtain another optimal solution with the required property. Then, we show that such a solution can always be transformed into an optimal solution which satisfies the conditions of this Lemma.

Lemma 6. Assume the cycle C contains at least four consecutive nodes (u, v 1 , . . . , v k , w) for k ≥ 2 where u and w have at least one leg, and nodes v i have no leg. Then there exists an optimal solution containing the caterpillar made of one leg of u, ∪ i T vi , and one leg of w, with the leaves of u and w attached. If u and/or w has only one leg, then this caterpillar also contains the next cycle edge in the corresponding direction, as an external edge.

Proof. This Lemma is proven in the same way as the previous one, where in the first part we state that there exists an optimal solution in which edges of the path (u, v 1 , . . . , v k , w) are part of the same caterpillar.

Node v in Lemma 5 and nodes v 1 , . . . , v k in Lemma 6 are called forcing nodes.

When two legs are close enough, the next Lemma shows that we can merge the corresponding nodes: Lemma 7. Assume that C contains three consecutive nodes (u, v, w) where u and w have at least one leg, and T v has shape A (i.e., v is connected to no other edge). Consider T obtained by contracting the edges (u, v) and (v, w): the three nodes are replaced by a node t, to which T u and T w are connected.

Then solving CATERPILLARSPLIT on T is equivalent to solving CATERPILLARSPLIT on T .

Proof. Consider any solution S for T . If one leg of u and one leg of w are part of the same caterpillar in S , the edges (u, v) and (v, w) can be added to this caterpillar in place of node t, and we obtain a solution for T . On the other hand, if there is no caterpillar with a leg of u and a leg of w, it means S contains at least two caterpillars with node t. We can attach edge (u, v) to the caterpillar which contains a leg of u, and (v, w) to the caterpillar which contains a leg of w (both as external edges). Since v has no other edge, this yields a solution for T .

If two caterpillars of S contain a leg of u and a leg of w, we can swap them to obtain a solution where one caterpillar has two legs of u and one caterpillar has two legs of w, and return to the second case mentioned above. Lemma 7 also holds if u and w are neighbors in the cycle: edge (u, w) can be contracted.

With these three lemmas, we can write algorithm 2 to solve CATERPILLARSPLIT on pseudo-trees. On line 12, Repeatedly merge two consecutive nodes on the cycle (Lemma 7) and apply Lemma 2;

16 return the resulting once C v has been removed from T , the resulting graph is a tree. We can thus use Algorithm 1 from the previous Section to solve CATERPILLARSPLIT in that case. On line 15, all legs of the cycle will be grouped by two, and we obtain l 2 caterpillars, where l is the number of legs.

C. Minimization of both makespan and preemptions

The algorithms presented above work in two steps: we first compute a preemptive solution x * with optimal makespan thanks to the Linear Program (PLP), and then we compute the optimal ordering for this particular solution which minimizes the number of preemptions. This does not guarantee that the resulting schedule has an optimal number of preemptions: there may exist another optimal solution of (PLP) which incurs fewer preemptions with a correct ordering.

In order to strengthen the guarantee on the number of preemptions, one may want to study the following problem (we denote it with MINPREEMPTIONS): given a speed matrix S i,j and processing times p i , output a schedule with the smallest number of preemptions among those schedules with optimal makespan. Unfortunately, we show in this Section that this problem is actually NP-complete.

Theorem 2. MINPREEMPTIONS is NP-complete.

Proof. The problem clearly belongs to NP: given a solution, it is easy to check in polynomial time that the solution is valid, and to compute its makespan and number of preemptions.

We prove its NP-hardness by reduction from the wellknown problem 3-PARTITION, whose input is a set of 3n integers a i , with i a i = nB, and whose output is a partition of [|1, 3n|] into n parts P j such that ∀j, i∈Pj a i = B.

From any 3-PARTITION instance with values a i , we build the following instance for our scheduling problem:

• There are n groups of tasks A j , B j , C j , X j , Y j with the following processing times:

A B C X Y p 2B 3B 2B B B
The co-scheduling matrix S for the tasks of group j is as follows: For any tasks u and v in different groups, S u,v = 0. • In addition, there are 3n V i tasks, with p Vi = a i from the 3-PARTITION instance. The co-scheduling coefficients of these tasks are 1 for all the B j tasks (S Vi,Bj = 1 for all i and j), and 0 for all other tasks of any group j. If the 3-PARTITION instance is positive, it is possible to schedule these tasks without preemption with makespan 5nB (see Figure 5, where each group j is associated with one part P j ).

A B C X Y A • 1 0 1 0 B 1 • 1 0 0 C 0 1 • 0 1 X 1 0 0 • 0 Y 0 0 1 0 • t R 1 R 2 B 2B 3B 4B 5B X j A j B j C j Y j V i1 V i2 V i3
assume there exists a non preemptive schedule for these tasks in time 5nB. Since the total execution time of all tasks is 9nB from tasks of all groups and nB from V i tasks, this schedule must have two tasks executing at all times. In each group j, task X j can only run together with task A j for a duration B. The remaining duration of task A j can only be together with task B j . Similarly, task Y j must execute with task C j , and the remaining duration has to be with task B j . The remaining duration of task B j (for B time units) has to be together with some tasks V i for some i. Let us denote by P j the set of indices i such that task B j runs with the tasks V i in this schedule. Since no preemption is allowed, the sum of execution times of these V i tasks is exactly B, and so we have a solution for the 3-PARTITION instance.

V. EXPERIMENTAL EVALUATION

In this section, we present an experimental validation on realistic data, in order to assess the practical performance of our algorithm.

A. Benchmarks

The data was obtained by benchmarking a number of GPU kernels from different well-known GPU benchmark suites (Rodinia, Parboil and SHOC) that reproduce reallife applications [START_REF] Carvalho | Analysis and characterization of gpu benchmarks for kernel concurrency efficiency[END_REF]. The experiments were performed on a GPU Tesla P100-SXM2 based on the Pascal architecture. The kernels were compiled with NVCC CUDA version 8.0 and the executions used a framework that support the submission of two given kernels at the same time. Measuring the resulting execution time of both kernels allows to obtain realistic values for the slowdown experienced by kernels when running together.

Consider a given measurement for kernels K and K , whose standalone execution times are respectively T 1 K and T 1 K . We measure the co-execution time O K,K : the time interval during which both kernels are running together. We also measure the execution times of kernel K when running with K : T K K , and respectively T K K is the execution time of K when running with K.

With similar ideas to those used in [START_REF] Carvalho | Analysis and characterization of gpu benchmarks for kernel concurrency efficiency[END_REF] to define the so-called concurrency index, we can use these measurements to compute the speed S K,K of kernel K when run with kernel K . If the co-execution interval is the whole duration of T K K , then S K,K =

T 1 K T K K
since the total work is T 1 K , and it was performed in time T K K . For shorter coexecution intervals, we will assume that outside of the co-execution interval, both kernels behaved as if they were in isolation. We can thus consider that all of the slowdown incurred by each kernel is due to this interval. Then the duration T K K -O K,K is common between both executions, and can be removed. Since the remaining duration was executed in time O K,K , the speed S K,K is thus:

S K,K = T 1 K -(T K K -O K,K ) O K,K = 1 - T K K -T 1 K O K,K
We have thus computed these values for each measurement for all kernels analyzed in [START_REF] Carvalho | Analysis and characterization of gpu benchmarks for kernel concurrency efficiency[END_REF], and assigned speed = 0 for all measurements that resulted in too short of an overlap. Each kernel pair was measured 5 times, and the maximum speed recorded for each pair was used as a measure of how fast these kernels may run together. The CDF of the resulting speed distribution is shown on the left of Figure 6, which shows that about half of kernel pairs can not run together at all, and the speeds of the remaining pairs is roughly uniformly distributed. This does not tell the whole story though, since we expect correlations between the speed of kernels relative to each other. The complete speed matrix is provide on the right of Figure 6.

B. Experimental setting

From the speed measurements, we construct random instances to our scheduling problem in the following way. We fix a number n of tasks, and each task computes one of the 60 kernels, picked at random. To assign task durations, we can use the measured standalone time of the kernels (modeling the fact that this task computes the kernel once). This is the actual case, and it results in large variety in task execution times because the kernels are very different from each other. This case comes in two flavors: either uniform where the kernels are picked with equal probability, or weighted where each kernel is picked with a probability inversely proportional to its duration. In the weighted case, if two kernels have duration d and d , the expected number of tasks of each type will be c • n/d and c • n/d for some constant c. Thus, the expected total workload corresponding to each type of task is equal to c • n, independently of the kernel duration. We have also analyzed the random duration case, in which the duration of a task is a uniform value between 0 and 10 (modeling the fact that each task computes one given kernel several times, and that tasks have relatively similar durations). In this last case, two tasks may represent the same kernel but have different durations.

For each case and each number of tasks, we have generated 15 different instances. We first compute the solution to the preemptive Linear Program (PLP), and then, for each instance, we evaluate the results of the preemptive solution obtained with the CATERPILLARSPLIT algorithm (Algorithm 2). For comparison, we also compute the sequential solution (where each task is executed alone) and the solution obtained from the graph-based algorithm MAXPAIR [START_REF] Wen | Maxpair: Enhance opencl concurrent kernel execution by weighted maximum matching[END_REF] which schedules tasks nonpreemptively by grouping them by best-assorted pairs.

All algorithms are implemented in Python 3.6.5. Linear Programs are solved with CPLEX 12.7.

C. Experimental results

Figure 7 shows the number of preemptions achieved by the CaterpillarSplit algorithm, on the solution returned by the Linear Program. The plot actually shows the average number of preemptions per task, i.e. the total number of preemptions divided by the number of tasks. This average reaches a constant value relatively q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q weighted randomDuration uniform quickly, showing that our solution requires to preempt at most 12% of tasks (9% in average) for the worst setting random duration.

Figure 8 shows the performance in terms of schedule length, compared to a sequential solution. In addition to the results of CATERPILLARSPLIT and MAXPAIR, this plot includes schedule durations for CATERPILLAR-SPLIT with the very conservative assumption that each preemption incurs an overhead of either 20 or 50% of the average task duration, during which the GPU can not process any task. We first see that using concurrent execution allows to reduce execution time by 20 to 30%. Using our preemptive solutions allows to reduce this time further, by 10-12% for the weighted case, by 5-7% for the uniform case, and by 3-5% for the random duration case. Furthemore, our solution is more efficient in all cases even with 20% overhead, and in both the weighted and uniform cases with the very conservative 50% overhead.

VI. CONCLUSIONS

In this paper, we address the problem of co-scheduling on a GPU. We propose a theoretical model and pro-vide a preemptive scheduling algorithm. We show that the optimal preemptive makespan can be computed in polynomial time, and that we can schedule any solution of optimal makespan with a minimal number of preemptions. However, computing the minimal amount of preemptions among all preemptive solutions of optimal makespan is an NP-hard problem.

We present an experimental evaluation of our algorithm on realistic instances, based on benchmarks of real applications. We show that our approach is able to achieve the optimal makespan by preempting 6 to 9% of all tasks depending on the experimental condition, which allows to obtain very good performance compared to the literature, even with a conservative overhead.

This work opens many challenging perspectives. One next step would be to design an algorithm to produce non-preemptive schedules which could be more efficient than MAXPAIR, or more generally to take a preemption cost into account. On the theoretical side, it would be valuable to provide worst-case estimates on the average number of preemptions (we conjecture that it can not be more than 1 3 ), and to consider the problem with concurrent execution of three kernels.

  Minimize e∈E(S) x e subject to ∀i ∈ T , e∈E(S)|i∈e x e S i,c(e,i) ≥ p i ∀c ∈ C, x c ≥ 0 This Linear Program has |E(S)| variables, and |E(S)| + n constraints.

Figure 1 :

 1 Figure 1: Possible cases to turn the graph G into a schedule.

Figure 2 :

 2 Figure 2: Illustrations of Lemmas 2, 3 and 4. Leaves are in grey, internal paths of the caterpillars have thick edges, and non connected edges show the splitting.

Algorithm 1 : 3 t 4 if t has one child of height 1 u then 5 Merge t with u ; 6 else if t has two children of height 1 u and v then 7 C 8 S ← S ∪ {C}; 9 Remove edges of C from T ; 10 else if t has at least 3 children of height 1 then 11 Pick u and v, two children of height 1 of t; 12 C 13 S

 1345678910111213 CaterpillarSplit(T , r)Input: A tree T , rooted at r Output: A partition of T in caterpillars 1 S ← ∅ ; 2 while T has vertices of height 2 do ← a vertex of height 2 of T ; ← caterpillar (u, t, v) with leaves attached, and the edge from t to its parent; ← the caterpillar (u, t, v) with leaves attached; ← S ∪ {C};14Remove edges of C from T ; 15 return S ∪ {T }

Figure 3 :

 3 Figure 3: Four possible shapes for a node on the cycle.

  ): (A) T u = {u}, i.e. u is a leaf in T u ; (B) u has height 1 in T u , with at least one leaf; (C) u has height 2 in T u , and exactly one child of height 1; (D) u has height 2 in T u , and exactly two children of height 1.

7 .

 7 Lemma 5, where u has two legs and w has one. Thick edges show the internal path of the caterpillar, and non-connected edges show where the splitting occurs. The original pseudo-tree T is on the left, T is on the right.

Figure 4 :

 4 Figure 4: Illustrations for Lemmas 5 and 7.

Algorithm 2 : 7 Split node u to obtain a path; 8 returnv then 11 Cv ← caterpillar forced by v (Lemma 5 or 6); 12 S

 2781112 CaterpillarSplit(T , C) Input: A pseudo-tree T , containing one cycle C Output: A partition of T in caterpillars 1 foreach u ∈ C do 2 Solve CATERPILLARSPLIT on Tu, stop when u has at most two children of height 1; 3 if no node of C has a leg then 4 Split any node of C to obtain a path; 5 return the caterpillar made of this path and all their leaves attached; 6 else if exactly one node u of C has one or two legs then the caterpillar made of this path and all their leaves attached; 9 else if there are at least two legs on cycle C then 10 if there exists two legs separated by a forcing node ← CATERPILLARSPLIT (T \ Cv) (Alg. 1);

Figure 5 :

 5 Figure 5: Valid schedule for group j with P j = {i 1 , i 2 , i 3 } if the 3-PARTITION instance is positive.

Figure 6 :

 6 Figure 6: Speeds obtained from measurement data. Cumulative distribution on the left, speed matrix on the right.

Figure 7 :

 7 Figure 7: Analysis of the number of preemptions achieved by the CATERPILLARSPLIT algorithm. Each dot is an experiment, the line represents a smoothed average with standard deviation shown in grey.

Figure 8 :

 8 Figure 8: Performance of CATERPILLARSPLIT (with and without preemption overhead) compared to MAXPAIR.


Maria Alice Brito

Ali Amad

Benjamin Rolland

Pierre A Geoffroy

Hugo Peyre

Jean-Luc Roelandt

Imane Benradia

Pierre Thomas

Guillaume Vaiva

Franck Schürhoff

Dr Baptiste Pignon
email: baptistepignon@yahoo.fr

Religiosity and prevalence of suicide, psychiatric disorders and psychotic symptoms in the French general population

Keywords: Religious beliefs, Religious observance, Mood disorders, Suicide attempts, Psychotic disorders

à 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

According to Emile Durkheim, religion provides rules of conduct for individuals and thus allows for social integration and regulation. His work, entitled « Le Suicide », published in 1897, was the first sociological study to examine the effect of religion on suicide risk [START_REF] Durkheim | Religion and the risk of suicide: longitudinal study of over 1 million people[END_REF]. Durkheim analyzed variations in suicide rates among different social groups in France, particularly religious groups, and found a protective effect of religion membership against suicide. Since then, a substantial amount of scientific studies have addressed the question of the protective effect of religion on suicidality. However, the results found were contradictory. For instance, in Ireland, religious affiliation was not associated with significant variations in the risk of death by suicide [2]; while in a representative sample of the general population of the United Kingdom, the prevalence of suicidal ideation and suicide attempts was significantly lower among religious groups, in comparison to non-religious groups [START_REF] Jacob | The association of religiosity with suicidal ideation and suicide attempts in the United Kingdom[END_REF]. In a 42-country study, Hsieh found significant variations in this association [START_REF] Hsieh | A Global Perspective on Religious Participation and Suicide[END_REF]. More precisely, religious involvement was associated with lower rates of death by suicide in Latin America, Eastern and Northern Europe, and English-speaking countries, but higher rates in East Asia, Western and Southern Europe. These results support the notion that the effect of religion on suicidality may not be the same in all regions of the world. Moreover, with regard to the relationship between suicide and religiosity, statistical adjustment on psychiatric disorders could bring significant insight. Finally, to our knowledge, no religiosity studies concerning suicide have focused on the French general population since Durkheim's work.

The effect of religious affiliation and participation on the rates of psychiatric disorders has also been studied.

Regarding depression, several studies and meta analyses have found protective effects of religion [START_REF] Braam | Religion as a cross-cultural determinant of depression in elderly Europeans: results from the EURODEP collaboration[END_REF][START_REF] Smith | Religiousness and depression: Evidence for a main effect and the moderating influence of stressful life events[END_REF][START_REF] Miller | Religiosity and Major Depression in Adults at High Risk: A Ten-Year Prospective Study[END_REF].

Religion also appears to be protective against addictive disorders [START_REF] Miller | Religiosity and Substance Use and Abuse Among Adolescents in the National Comorbidity Survey[END_REF][START_REF] Vance | A Multivariate Twin Study of the Dimensions of Religiosity and Common Psychiatric and Substance Use Disorders[END_REF]. Regarding anxiety disorders, studies have found non-significant differences, or slight associations between religion and lower rates of anxiety disorders [START_REF] Rasic | Longitudinal relationships of religious worship attendance and spirituality with major depression, anxiety disorders, and suicidal ideation and attempts: Findings from the Baltimore epidemiologic catchment area study[END_REF][START_REF] Khalaf | A Critical Comprehensive Review of Religiosity and Anxiety Disorders in Adults[END_REF]. Regarding psychotic disorders, the relationship between religion and prognosis and quality of life for patients has been extensively studied [START_REF] Bonelli | Mental Disorders, Religion and Spirituality 1990 to 2010: A Systematic Evidence-Based Review[END_REF][START_REF] Borras | Religious Beliefs in Schizophrenia: Their Relevance for Adherence to Treatment[END_REF][START_REF] Caqueo-Urízar | Religion involvement and quality of life in patients with schizophrenia in Latin America[END_REF], and the prevalence of psychotic symptoms has been shown to be associated with religion [START_REF] Oh | Psychotic experiences and religiosity: Findings from the collaborative psychiatric epidemiological surveys[END_REF]. However, to our knowledge, no studies have ever assessed the risk of psychotic disorders according to religious affiliation or participation. Overall, as for suicide outcomes, no studies about the relationship between religiosity and the prevalence of psychiatric disorders has been carried out in France, and it is of great importance to study these associations within a specific context, due to specific cultural aspects. Migration, which is associated with specific risks of psychiatric disorders [START_REF] Amad | Increased prevalence of psychotic disorders among thirdgeneration migrants: Results from the French Mental Health in General Population survey[END_REF][START_REF] Mindlis | Mood disorders in first-and second-generation immigrants: Systematic review and meta-analysis[END_REF][START_REF] Selten | Migration and psychosis: a meta-analysis of incidence studies[END_REF], may also influence this association [START_REF] Johns | Prevalence and correlates of self-reported psychotic symptoms in the British population[END_REF][START_REF] Jordanova | Religious discrimination and common mental disorders in England: a nationally representative population-based study[END_REF], and, to our knowledge, no studies have adjusted for this risk factor.

In this context, the objective of this study was to analyze the association between religious beliefs and practice and the prevalence of suicide attempts, psychiatric disorders, and psychotic symptoms in a large sample of the French general population while adjusting for several sociodemographic variables, including migration status. Our hypothesis is that religiosity remains negatively associated with suicide and is protective against most psychiatric disorders.

METHODS

Mental Health in the General Population (MHGP) survey

This study is an explorative secondary analysis of MHGP survey. This survey was conducted by the World Health Organization-Collaborating Centre (WHO-CC) between 1999 and 2003, and interviewed 38,694 subjects at 47 study sites. Approximately 900 participants were selected using the quota sampling method from each site [START_REF] Lunsford | The Research Sample, Part I: Sampling[END_REF]. This method provides a sample of a population with similar characteristics to the overall population, i.e., age, sex, and level of education. The initial objective of this survey was to describe the perceptions and representations of mental health in the general population. The inclusion criteria were as follows: the subject providing consent, being 18 years old or above, being francophone, and not being hospitalized or homeless.

Socio-demographic variables

The following socio-demographic values were collected: age, sex, education level, marital status, income level and migration status (native, first, second or third generation migration).

Religiosity

For each participant, religiosity was assessed on the basis of religious beliefs and religious practice. These were identified by means of two questions: "are you a believer?" and "are you religiously observant?". Participants answered with "Yes" or with "No" to these two questions.

Psychiatric disorders

The Mini International Neuropsychiatric Interview (MINI, French version 5.0.0) was used to screen for major psychiatric disorders as defined by the 10th version of the International Classification of Diseases (ICD-10). It has excellent validity, reliability (inter-rater and test-retest), sensitivity and specificity [22,[START_REF] Sheehan | The Mini-International Neuropsychiatric Interview (M.I.N.I.): the development and validation of a structured diagnostic psychiatric interview for DSM-IV and ICD-10[END_REF].

A three-day training course about MINI administration, organized by the WHO-CC, was given to the MHGP survey evaluators (i.e., nursing students and psychologists) [START_REF] Caria | Santé Mentale en Population Générale : Images et Réalités (Smpg) » : Présentation de La méthodologie d'enquête[END_REF]. The psychiatric disorders studied were: lifetime bipolar disorder (BD, F31), current unipolar depressive disorder (UDD, F32 and F33), current generalized anxiety disorder (GAD) (F41.1), current panic disorder (F41.0), current social anxiety disorder (SAD, F40.1), current post-traumatic stress disorder (PTSD) (F43.1), one-year alcohol use disorders (AUD) (F10) and one-year substance use disorders (SUD) (F19). Lifetime history of suicidal attempts was also assessed. With regard to psychotic disorders, 7 psychotic symptoms were assessed, including five items that assess the lifetime occurrence of delusional symptoms: delusions of persecution, thought broadcasting, delusions of control, delusions of reference, and other delusional ideas (e.g., somatic delusions or delusions of grandiosity); and two items that assess the lifetime occurrence of visual and auditory hallucinations. The diagnosis of a lifetime psychotic disorder was assessed by the presence of psychotic symptoms in the MINI and confirmed by a clinician who was familiar with transcultural psychiatry. Other details on the MHGP survey are available elsewhere [START_REF] Pignon | Prevalence and clinical severity of mood disorders among first-, second-and third-generation migrants[END_REF][START_REF] Pignon | Increased prevalence of anxiety disorders in thirdgeneration migrants in comparison to natives and to first-generation migrants[END_REF][START_REF] Pignon | A latent class analysis of psychotic symptoms in the general population[END_REF].

Statistical Analysis

To study the association between religious status and psychiatric disorders, the prevalence of psychiatric disorders, psychotic symptoms, and suicide attempts were assessed according to religious beliefs and religious observance. To analyze the role of religious observance specifically and separately from beliefs, the analyses concerning religious observance were repeated among believers. The statistical analyses used were chi-square tests for bivariate analyses, and binomial logistic regressions for the multivariable analyses.

Binomial logistic regressions were adjusted for the following factors: age, sex, education level, migration status, economic level and marital status. Concerning the history of suicide attempts, to exclude the influence of the different psychiatric disorders, analyses were repeated with additional adjustment for the different psychiatric disorders (i.e., mood, anxiety, addictive and psychotic). The statistical analyses were performed using R software [START_REF] Team | A language and environment for statistical computing[END_REF].

RESULTS

Religious beliefs and observance

Of the 38,694 subjects interviewed in the SMPG survey, 21,634 (59.0%) reported being religious believers, and 8,794 (22.7%) reported being religiously observant. Subjects who were not believers were considered as non-observant. Among believers, 12,793 (59.1%) were not observant. Among those who were religiously observant, 63 (0.7%) were not believers (see Table 1 for the details).

-TABLE 1 -

Sociodemographic variables

Sociodemographic characteristics of the study population are detailed in Table 2. Age was associated with religiosity, with higher rates of religiosity among people aged over 60 years-old (75.4% of beliefs in 60+ age-band vs. 60.7% and less in the other age-bands, 41.1% of observance vs. 22.2% and less). Women were more religious than men (beliefs: 64.4% vs. 52.8%, observance: 27.9% vs. 19.5%). Subjects with lower levels of education and income were also more religious. Finally, first-and second-generation migrants were more religious than natives and third-generation migrants (beliefs: 76.2% and 66.2% for first-and secondgeneration vs. 57.6% and less for native and third-generation; observance: 43.6% and 28.0% vs. 23.2% and less).

-TABLE 2 -

Religiosity and suicide

Religious beliefs (OR=0.90, 95% CI [0.82-0.99]) and, more importantly, religious observance (OR=0.79, 95% CI [0.70-0.89]) appeared to be associated with lower rates of history of suicide attempts. Contrary to the association with religious beliefs, the association with religious observance remained significant after Bonferroni correction. Additional analyses which were adjusted for other psychiatric disorders (i.e., mood, anxiety, addictive and psychotic disorders) found the same associations (beliefs: OR=0.88, 95% CI [0.80-0.97], observance: OR=0.80, 95% CI [0.70-0.90]).

Religiosity and mood disorders

Religious beliefs (OR=1.15, 95% CI [1.06-1.23]) were associated with a higher UDD rate (and remained significant after Bonferroni correction), contrary to religious observance (OR=0.99, 95% CI [0.91-1.08]) which was not significantly associated.

Religious beliefs (OR=0.83, 95% CI [0.69-0.98]) were associated with a lower rate of BD, contrary to religious observance (OR=0.88, 95% CI [0.70-1.09]) which was not significantly associated. This association did not remain significant after Bonferroni correction.

Religiosity and anxiety disorders

Religious beliefs (OR=1.13, 95% CI [1.06-1.21]) were associated with a higher rate of GAD (and remained significant after Bonferroni correction), but not religious observance (OR=0.98, 95% CI [0.90-1.06]).

Religious beliefs (OR=1.06, 95% CI [0.96-1.18]) were not associated with SAD rate, contrary to religious observance (OR=0.87, 95% CI [0.76-0.99]) which was significantly associated with a lower rate. This association did not remain significant after Bonferroni correction.

Religious beliefs and observance were not associated with panic disorder and PTSD rates (beliefs: OR=1.09, 95% CI [0.99-1.20] for panic disorder, and OR=0.90, 95% CI [0.69-1.18] for PTSD; observance: OR=1.00, 95% CI [0.89-1.11] for panic disorder, OR=1.10, 95% CI [0.81-1.47] for PTSD).

Religiosity and addictive disorders

Religiosity and psychosis

Psychotic symptoms were more frequent among subjects with religious beliefs (OR=1.37, 95% CI [1.30- Except for psychotic disorders and religious observance, theses associations did not remain significant after Bonferroni correction.

Details of prevalence and bivariate and multivariable comparisons according to religiosity are available in

Tables 3 and4.

-TABLES 3 AND 4 -

Analyses of religious observance among believers

Religious observance among believers was associated with the same effect as in the total sample for the following outcomes: history of suicide attempts (OR=0.83, 95% CI [0.72-0.94]), SAD (OR=0.81, 95% CI [0.70-0.94]), AUD (OR=0.70, 95% CI [0.58-0.83]), and SUD (OR=0.60, 95% CI [0.46-0.77]). The associations with the addictive disorders remained significant after Bonferroni correction. As in the total sample, religious observance was not associated with UDD (OR=0.92, 95% CI [0.84-1.00]), BD (OR=0.98, 95% CI [0.76-1.27]), panic disorder (OR=0.95, 95% CI [0.84-1.07]) or PTSD (OR=1.18, 95% CI [0.84-1.66]). In contrast to the total sample, psychotic disorders (OR=1.09, 95% CI [0.92-1.28]) and symptoms (OR=0.98, 95% CI [0.91-1.28]) were not associated with religious observance; and GAD (OR=0.90, 95% CI [0.82-0.98]) was slightly negatively associated with religious observance. See details of prevalence in Table 5.

-TABLE 5 -

DISCUSSION

Our study analyzed the association between the prevalence of suicide attempts, psychiatric disorders and psychotic symptoms, and religious beliefs and observance. The analyses were adjusted for migrant status, among other factors. Interestingly, religious beliefs and observance had different relationships with psychiatric disorders. Indeed, a positive association was found with psychotic disorders, UDD and GAD.

Conversely, a negative association was found between religiosity and history of suicide attempts, BD, SAD, and, to a greater degree, with addictive disorders. Moreover, religious observance had almost the same relationships with the outcomes when analyzed in the total sample and specifically among believers.

The relationships between religiosity and psychiatric outcomes are analyzed cross-sectionally in the present study. The major bias of such studies is the lack of information concerning whether religious characteristics were present in subjects before the onset of psychiatric disorders. Indeed, religiosity for subjects with psychiatric disorders could be considered as coping strategies (e.g., relief for psychological distress) and thus occur after the onset of psychiatric disorders. Thus, religiosity as either a protective or risk factor to psychiatric outcomes can only be hypothesized. However, some of the associations observed in this study have been found in longitudinal studies (see below); and both religious beliefs and observance may have psychopathological effects. On the one hand, the belief in God or any other spiritual belief should provide relief (and thus prevent psychiatric disorders) in addressing life adversities [START_REF] Korkeila | Childhood adversities, adulthood life events and depression[END_REF][START_REF] Beards | Life events and psychosis: a review and metaanalysis[END_REF]. Moreover, concerning observance, the religious community may bring social support to the observant individual which could be protective against loneliness, also a major risk factor for psychiatric disorders [START_REF] Beutel | Loneliness in the general population: prevalence, determinants and relations to mental health[END_REF][START_REF] Erzen | The effect of loneliness on depression: A meta-analysis[END_REF][START_REF] Da Rocha | Loneliness in Psychosis: A Metaanalytical Review[END_REF]. This social role of religiosity could also provide potential support for subjects with psychiatric patients, and thus prevent clinical worsening and encourage recovery [START_REF] Shahid | Religion/Spirituality: A Tool to Better Help Psychiatric Patients[END_REF]. On the other hand, religious beliefs may increase the feeling of responsibility, and thus the feeling of guilt; and religious observance is codified by rules that could be difficult to comply with. Furthermore, religiosity may increase proneness to delusional ideas and hallucinatory perceptions [START_REF] Steenhuis | Religiosity in young adolescents with auditory vocal hallucinations[END_REF]. Some authors describe religious beliefs as falling within a spectrum of belief from the norm to delusion [START_REF] Gawad | Religious Activity, Psychotic Features, and Suicidality in 688 Acute Psychiatric Inpatients[END_REF]. According to Pierre, a dimensional approach to delusion would be more relevant in differentiating the normal from the pathological, rather than assessing the context of the religious belief itself [START_REF] Pierre | Faith or Delusion? At the Crossroads of Religion and Psychosis[END_REF]. The different associations found in our study may be discussed in light of these different issues. Furthermore, comparisons with studies across countries are difficult. For instance, American studies may be influenced by the weight of religion in American society which is different from the weight of religion in French society [START_REF] Debray | God: An Itinerary[END_REF]. France is characterized by secular customs, and the place of religion belongs primarily to the private sphere. Thus, the impact of religion on socio-cultural codes is uneven compared to other less secularized societies.

The negative association between religiosity and suicide is consistent with Durkheim's work. Since then, several cross-sectional European studies have also studied this association. Using similar methodology in a representative sample of the general population of the United Kingdom, Jacob et al. found consistently lower prevalence of suicidal ideation and attempts among subjects with a religion (whole suicidality lifetime: OR=0.83, 95% CI [0.69-0.99]) [START_REF] Jacob | The association of religiosity with suicidal ideation and suicide attempts in the United Kingdom[END_REF]. The major strength of our study is to provide supplementary and consistent analysis of this association adjusted for the different psychiatric disorders. Thus, the statistical association of religiosity is the same after adjustment for psychiatric disorders, which is consistent with a negative association against suicide, even among patients with psychiatric disorders [START_REF] Rasic | Longitudinal relationships of religious worship attendance and spirituality with major depression, anxiety disorders, and suicidal ideation and attempts: Findings from the Baltimore epidemiologic catchment area study[END_REF]. As the survey was cross-sectional, no causal conclusions can be stated. However, prospective studies in the USA and a systematic review of 17 worldwide studies confirmed our cross-sectional findings [START_REF] Kleiman | Prospective prediction of suicide in a nationally representative sample: religious service attendance as a protective factor[END_REF][START_REF] Vanderweele | Association Between Religious Service Attendance and Lower Suicide Rates Among US Women[END_REF][START_REF] Lawrence | Religion and Suicide Risk: A Systematic Review[END_REF]. Moreover, a study based on 162 European regions found a "dose-effect" negative relationship between suicide rate and the strength of subjective religiosity [START_REF] Stack | Religiousness as a Predictor of Suicide: An Analysis of 162 European Regions[END_REF]. These negative associations may be explained by the moral judgment of suicide induced by religion. Indeed, suicide is explicitly forbidden in monotheistic religions such as Judaism, Christianity, and Islam [START_REF] Jacob | The association of religiosity with suicidal ideation and suicide attempts in the United Kingdom[END_REF]. However, Durkheim stated that the negative association found is not linked to any religious condemnation of suicide but rather to the influence of the society formed by the sharing of common beliefs and practices [START_REF] Durkheim | Religion and the risk of suicide: longitudinal study of over 1 million people[END_REF]. Comparing the suicide rates in different religious groups, he argued that the stronger the ties of the community were, the more protective the community was against suicide. The dogma of communication with a divine being or the immortality of the soul would therefore be secondary.

The negative association of religiosity with addictive disorders suggested a protective effect, which was stronger than that for suicide attempts, could also be related to religious doctrines against taking and/or abusing alcohol and/or drugs. The negative association found in our results is consistent with previous studies on this topic [START_REF] Vance | A Multivariate Twin Study of the Dimensions of Religiosity and Common Psychiatric and Substance Use Disorders[END_REF][START_REF] Heinz | Spiritual/Religious Experiences and In-Treatment Outcome in an Inner-City Program for Heroin and Cocaine Dependence[END_REF][START_REF] Dew | Religion/Spirituality and Adolescent Psychiatric Symptoms: A Review[END_REF][START_REF] Tuck | Religion, Alcohol Use and Risk Drinking Among Canadian Adults Living in Ontario[END_REF]. Of note, among all psychiatric disorders, the negative association of religiosity appeared to be the strongest for addictive disorders. Edlund et al. have analyzed the role of mental health status and social support in this negative association, and found significant but small associations [START_REF] Edlund | Religiosity and decreased risk of substance use disorders: is the effect mediated by social support or mental health status?[END_REF]. Other studies found an association linking factors relating to religiosity as a whole: social religiosity, fear of God's judgment, forgiveness, and/or thankfulness [START_REF] Vance | A Multivariate Twin Study of the Dimensions of Religiosity and Common Psychiatric and Substance Use Disorders[END_REF][START_REF] Kendler | Dimensions of religiosity and their relationship to lifetime psychiatric and substance use disorders[END_REF].

However, owing to the fact that depressive symptoms are strong predictive factors of suicidality across psychiatric disorders [START_REF] Cavanagh | Psychological autopsy studies of suicide: a systematic review[END_REF][START_REF] Arsenault-Lapierre | Psychiatric diagnoses in 3275 suicides: a meta-analysis[END_REF][START_REF] Roux | Mediation Analyses of Insight, Quality of Life, Depression, and Suicidality: Results From the FACE-SZ Cohort[END_REF][START_REF] Miller | Bipolar Disorder and Suicide: a Review[END_REF] and that negative associations have been found in most studies, the positive association of religious beliefs with UDD is surprising. In an international and prospective study, Leurent et al. found a higher prevalence of depression among religious compared to non-religious subjects [START_REF] Leurent | Spiritual and religious beliefs as risk factors for the onset of major depression: an international cohort study[END_REF]. An explanation of these conflicting results could be that findings in any specific population may not generalize to another. Furthermore, the association of the present study between depression and religious beliefs was weak, whereas religious observance was not associated with UDD in the total sample nor in the believer sample. Regarding BD, little evidence is found in previous studies. A clinical review based on 5 studies that used homogeneous samples of BD patients did not find significant differences [START_REF] De Fazio | Religiousness and spirituality in patients with bipolar disorder[END_REF]. Contrary to the results of our study, some authors suggested that a higher incidence of strong religious experiences was described in mania [START_REF] Gallemore | The religious life of patients with affective disorders[END_REF], as if religious activity could have an influence in hypomanic/manic phases for BD patients.

However, and also surprisingly regarding the positive association with UDD, our study found a slight negative association between BD and religious beliefs, and an absence of association with religious observance.

Regarding anxiety disorders, a mild positive association between religious beliefs and GAD was found in our study, whereas, surprisingly, a negative association with religious observance was found among believers, enhancing the fact that beliefs and observance may have different psychiatric consequences. SAD was also negatively associated with the observance in the total sample and among believers, without association with beliefs. In comparison to suicide, depression or addictive disorders, fewer studies analyzed the association between anxiety disorders and religion. These studies were in favor of a protective effect of religiosity on anxiety disorders rates. In a literature review in 2014, Khalaf et al. found 10 studies addressing the rates of anxiety disorders according to religiosity [START_REF] Khalaf | A Critical Comprehensive Review of Religiosity and Anxiety Disorders in Adults[END_REF]. Concerning GAD, studies found conflicting results (4 studies found a protective effect of religiosity, and 2 found an association between religiosity and GAD). The studies on SAD found insignificant associations. In a longitudinal study, Rasic et al. have followed more than 1000 subjects over a period of more than 10 years and did not find any association between any anxiety disorders and religiosity or spirituality [START_REF] Rasic | Longitudinal relationships of religious worship attendance and spirituality with major depression, anxiety disorders, and suicidal ideation and attempts: Findings from the Baltimore epidemiologic catchment area study[END_REF].

The results of our study concerning psychotic outcomes (association with beliefs and observance in the total sample, but no association with observance among believers) are in favor of a stronger association with religious beliefs rather than religious observance. To our knowledge, no studies to date have assessed the risk of psychotic disorders according to religious characteristics. Concerning psychotic symptoms, the results of previous studies were also conflicting. Several studies have looked at multiple ethnic groups and found variations in the association between religiosity and psychotic symptoms [START_REF] Oh | Psychotic experiences and religiosity: Findings from the collaborative psychiatric epidemiological surveys[END_REF][START_REF] Earl | An exploration of how psychotic-like symptoms are experienced, endorsed, and understood from the National Latino and Asian American Study and National Survey of American Life[END_REF]. In Kovess-Masfety et al. World Health organization study across 18 countries, including France, no associations were found between religious affiliation and psychotic symptoms [START_REF] Kovess-Masfety | Psychotic experiences and religiosity: data from the WHO World Mental Health Surveys[END_REF]. Focusing on specific subgroups in the same study, such as individuals with high religious investment, authors revealed higher rates of psychotic symptoms. Moreover, a Loch and al. study focused on the impact of organizational religious activity and perceptual abnormalities/hallucinations in individuals at ultra-high risk for psychosis and found a positive association [START_REF] Loch | Hearing spirits? Religiosity in individuals at risk for psychosis-Results from the Brazilian SSAPP cohort[END_REF]. The authors hypothesized that churches and religious organizations could be used to cope with hallucinations. Furthermore, such associations raise the question about the boundaries between religious beliefs and delusional symptoms [START_REF] Ventriglio | Delusion, possession and religion[END_REF]. Mystical themes are recurrent in delusions, e.g., megalomania and persecutory ideas that contain elements related to God or the devil. In addition, hallucinatory experiences could be integrated into a spiritual dimension, e.g., in communicative experiences with God. Furthermore, in our study, religiosity appeared negatively associated with suicide, and positively with psychotic symptoms. The link between suicide and psychotic symptoms has been extensively shown, including in MHGP survey [START_REF] Devylder | Suicidal Ideation and Suicide Attempts Among Adults With Psychotic Experiences: Data From the Collaborative Psychiatric Epidemiology Surveys[END_REF][START_REF] Pignon | Sociodemographic and clinical correlates of psychotic symptoms in the general population: Findings from the MHGP survey[END_REF]. Several clusters of psychotic symptoms could exist, with symptoms related to religiosity, and other to psychopathology. Further studies are necessary to disentangle the links between suicide, psychotic symptoms and religiosity.

A large number of participants were drawn from the general population, instead of subgroups, which provided a strong statistical base. Moreover, this is the first study conducted on the subject in the French population to our knowledge. However, the survey was conducted in the early 2000s, and thus the results need to be interpreted with caution, as religiosity is decreasing in the French society [START_REF] Todd | Lineages of Modernity: A History of Humanity from the Stone Age to Homo Americanus[END_REF]. Furthermore, some limitations of the study should be mentioned. First of all, the large-scale questionnaires involved retrospective data collection, as well as refusals to participate. Some refusals could be explained by the private and intimate nature of religiosity to certain people. Moreover, the quota method was used to select the subjects, and not a probabilistic one, which could affect the representativeness of the sample population.

Finally, the exclusion of homeless and institutionalized individuals induced a bias due to the high prevalence of psychiatric disorders in these populations. The multiple definitions of the criteria "religiosity" should also be highlighted [START_REF] Vance | A Multivariate Twin Study of the Dimensions of Religiosity and Common Psychiatric and Substance Use Disorders[END_REF][START_REF] Rasic | Longitudinal relationships of religious worship attendance and spirituality with major depression, anxiety disorders, and suicidal ideation and attempts: Findings from the Baltimore epidemiologic catchment area study[END_REF][START_REF] Kendler | Dimensions of religiosity and their relationship to lifetime psychiatric and substance use disorders[END_REF][START_REF] Leurent | Spiritual and religious beliefs as risk factors for the onset of major depression: an international cohort study[END_REF]. The strengths of participants' faith, the attendance at places of worship, the number of prayers, the belief in life after death or the belief in a supernatural force are religious criteria that would also have been interesting to study but were unavailable in MHGP survey. Therefore, religious beliefs and observance were assessed binarily, without assessment of the degree of religiosity or the timeframe of putative religiosity. Because of the cross-sectional nature of the study, no causal link can be determined. In addition, this study is prevalence-based, and thus could be influenced not only by religiosity, but also by different courses of the disease according to these risk factors. As discussed above, a possible bias is that religiosity could be secondary to the psychiatric disorder.

The present study shows positive and negative associations between religiosity and psychiatric disorders.

The paradox of both negative associations with suicide and positive associations with UDD needs to be addressed, e.g., studying the prognosis role of religiosity among patients with depression or other psychiatric disorders. Likewise, the association with psychotic symptoms, which are present in several psychiatric disorders, could be considered paradoxical as religiosity is negatively associated with some of these disorders (bipolar or addictive disorders). Finally, as it can be crucial for our patients, religious beliefs and observance should be considered when taking preliminary case histories. More studies are needed to shed light on the mechanisms of the association between religiosity as a clinical factor in psychiatry.

  AUD and SUD were less frequent among subjects with religious beliefs (OR=0.69, 95% CI [0.69-0.77] for AUD; OR=0.60, 95% CI [0.52-0.69] for SUD), and with religious observance (OR=0.60, 95% CI [0.51-0.70] for AUD; OR=0.48, 95% CI [0.38-0.60] for SUD). Theses associations did not remain significant after Bonferroni correction.

1. 45 ]

 45 ) and with observance (OR=1.14, 95% CI [1.08-1.21]). Regarding psychotic disorders, the associations were the same (beliefs: OR=1.38, 95% CI [1.20-1.58], and observance: OR=1.25, 95% CI [1.07-1.45]).

Acknowledgements:

None.

Financial support:

This research received no specific grant from any funding agency, commercial or not-for-profit sectors.

Availability of Data and Materials:

The data is not available in open access.

Conflict of Interest:

None.

Ethical Standards:

The authors assert that all procedures contributing to this work comply with the ethical standards of the relevant national and institutional committees on human experimentation and with the Helsinki Declaration of 1975, as revised in 2008.

Legal authorization was obtained by the "Commission Nationale Informatique et Liberté" (CNIL) and the "Comité consultatif sur le traitement de l'information en matière de recherche" (CCTIRS), with number 98.126.