Gabriel Bathie

Loris Marchal

Yves Robert

Samuel Thibault

Revisiting dynamic DAG scheduling under memory constraints for shared-memory platforms

Keywords: task system, dynamic scheduler, memory constraint, resource limitation

This work focuses on dynamic DAG scheduling under memory constraints. We target a shared-memory platform equipped with p parallel processors. We aim at bounding the maximum amount of memory that may be needed by any schedule using p processors to execute the DAG. We refine the classical model that computes maximum cuts by introducing two types of memory edges in the DAG, black edges for regular precedence constraints and red edges for actual memory consumption during execution. A valid edge cut cannot include more than p red edges. This limitation had never been taken into account in previous works, and dramatically changes the complexity of the problem, which was polynomial and becomes NP-hard. We introduce an Integer Linear Program (ILP) to solve it, together with an efficient heuristic based on rounding the rational solution of the ILP. In addition, we propose an exact polynomial algorithm for series-parallel graphs. We provide an extensive set of experiments, both with randomly-generated graphs and with graphs arising form practical applications, which demonstrate the impact of resource constraints on peak memory usage..

Ordonnancement dynamique de graphes de tâches avec contrainte mémoire sur plate-forme à mémoire partagée

Résumé :

Nous étudions l'ordonnancement de graphes de tâches sous contrainte mémoire, et proposons un nouveau modèle qui prend en compte le caractère limité des ressources. Nous montrons que déterminer la ressource mémoire maximale nécessaire à tout ordonnancement dynamique devient un problème NP-complet,. Nous proposons un programme linéaire en nombres entiers et une heuristique pour le résoudre. Nous conduisons un ensemble de simulations sur des graphes aléatoires ou issus d'applications, et démontrons tout l'impact de la limitation de ressources sur la consommation mémoire maximale.

Mots-clés :

ordonnancement dynamique, graphe de tâches, contrainte mémoire, limitation de ressources [START_REF] Drozdowski | Scheduling multiprocessor tasks -an overview[END_REF]

Introduction

In the last decade, task systems have become ubiquitous to deploy scientific applications on large-scale parallel platforms. In such systems, the application is represented by a Directed Acyclic Graph (DAG) of tasks, where the nodes represent the tasks (a computational kernel composed of a sequential set of operations to be applied to the input data), and the edges represent the dependencies between the tasks. The set of dependencies defines a partial order of execution. The problem is to map the tasks onto a set of p computing processors. In this paper, we target shared-memory platforms, where available processors consist of dozens of cores that share a main memory. A traditional objective is to determine a scheduling that minimizes the total execution time, or makespan. The makespan minimization problem has received considerable attention in the scheduling literature. On the theoretical side, many complexity results establish NP-hardness and inapproximability results. On the more practical side, several list heuristics have been developed to achieve close-to-optimal makespans. These heuristics typically aim at minimizing the critical path of the schedule, and use estimations of task priorities such as bottom levels [START_REF] Drozdowski | Scheduling multiprocessor tasks -an overview[END_REF][START_REF] Topcuoglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF]. However, all these heuristics are designed statically, meaning that they assign tasks to processors in a predetermined ordering, before the beginning of the parallel execution. It turns out such static strategies are unlikely to reach their expected performance, and this for many reasons: (i) task duration estimates are known to be inaccurate and may be affected by unexpected preemptions by the system; (ii) data transfer costs on the platform are hard to correctly model and significantly vary from one execution to another, because they strongly depend upon link contention; and (iii) the resulting small estimation errors are likely to accumulate and to cause large delays. Altogether, static heuristics end up making wrong decisions! This explains why most runtime systems [START_REF] Grimshaw | The legion vision of a worldwide virtual computer[END_REF][START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF][START_REF] Mattson | The Open Community Runtime: A runtime system for extreme scale computing[END_REF][START_REF] Bosilca | PaRSEC: Exploiting Heterogeneity to Enhance Scalability[END_REF][START_REF] Gautier | KAAPI: A thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF][START_REF] Planas | Hierarchical taskbased programming with StarSs[END_REF] rely on dynamic scheduling, where task allocations and their execution ordering are decided at runtime, based on the system state and unexpected events. These runtime systems dynamically maintain the list of tasks that are ready for execution, and assign them on-the-fly to processors, thereby accurately balancing the workload. However, not all dynamic schedules are equally good, because of memory constraints. Intuitively, a dynamic scheduling can be seen as a parallel traversal of the task graph, with all processors progressing simultaneously on different paths. At any time-step in the execution, the amount of memory needed for the traversal depends upon the input and output data of the tasks that are active at that step (see Section 3 for a detailed description), and this memory amount should never exceed the maximum memory made available to the application. Otherwise, the traversal will require the use of swap mechanisms or out-of-core execution, which will dramatically (and negatively) impact the achieved makespan [START_REF] Ramakrishnan | Scheduling dataintensiveworkflows onto storage-constrained distributed resources[END_REF][START_REF] Agullo | Robust memory-aware mappings for parallel multifrontal factorizations[END_REF].

Consider a task graph whose internal nodes require a large volume of temporary data, such as graphs arising from multifrontal solvers [START_REF] Amestoy | A fully asynchronous multifrontal solver using distributed dynamic scheduling[END_REF]. Improper scheduling decisions may lead dynamic schedules to hit a memory wall at some step while everything was going fine in the previous steps; the dynamic schedule suddenly reaches a state where any further decision (any choice of the next task to execute) will exceed the amount of available memory. This unfortunate scenario arises because dynamic schedules usually consider only tasks that are ready for execution, and have thus a very limited insight into the fraction of the task graph that is yet to be discovered and processed. To avoid such a pitfall, some global information on the task graph is required to guide the dynamic schedule and enforce safe execution paths.

In summary, dynamic scheduling is needed for performance, but one should ensure that any dynamic schedule that can be produced by the runtime system will never exceed the total amount of memory available to the application. There are few existing studies that take dynamic memory footprint into account when scheduling task graphs, as detailed below in Section 2. In our previous work [START_REF] Marchal | Parallel scheduling of dags under memory constraints[END_REF][START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF], we have proposed an approach to ensure that any dynamic schedule never exceeds the available memory. In a nutshell, the idea is to introduce fictitious dependencies in the task graph to cope with memory constraints: these additional edges restrict the set of valid schedules and, in particular, forbid the concurrent execution of too many memory-intensive tasks. Formally, the additional edges are introduced to decrease the value of the maximal directed cut of the task graph, where the cut represents the total memory currently used after executing some tasks (those on one side of the cut) and before executing the rest of the tasks (those on the other side of the cut). There is a price to pay: each additional edge adds a fictitious dependence constraint, thereby limiting the degree of parallelism in the execution. We provide a detailed overview of this approach in Section 3.

However, this previous work [START_REF] Marchal | Parallel scheduling of dags under memory constraints[END_REF][START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF] does not account for resource limitation: there are only p processors, hence no more than p tasks can be processed concurrently. In terms of memory usage, ignoring resource limitation translates into considering too many potential cuts, thereby requiring too many fictitious edges, which unduly constraints the dynamic schedules. In this paper, we refine the standard model for memory-aware scheduling and introduce the first mechanism to take resource limitation into account. Our new model involves two types of memory edges in the DAG, black edges for regular precedence constraints, and red edges for actual memory consumption during execution. Then a valid edge cut cannot include more than p red edges. This limitation dramatically changes the complexity of the problem, which was polynomial with a single edge type and becomes NP-hard with two edge types. We provide an optimal solution for series-parallel graphs and an efficient heuristic for arbitrary graphs. The main contributions of this paper are the following:

• We introduce a new model with colored edges to account for resource constraints when computing peak memory; • We show that the optimization problem becomes NP-complete, but we introduce an Integer Linear Program (ILP) to solve it, together with an efficient heuristic based on rounding the rational solution of the ILP. We also propose an exact polynomial algorithm for series-parallel graphs (SPGs); • We provide an extensive set of experiments, both with randomlygenerated graphs and with graphs arising form practical applications, that demonstrate the impact of resource constraints on peak memory usage. The rest of the paper is organized as follows. We first briefly review the existing work on memory-aware task graph scheduling in Section 2. We provide background on memory-aware scheduling in Section 3. Then, Section 4 is the core of the paper: we introduce the new model, assess its complexity, provide an optimal algorithm for Series Parallel Graphs, and discuss extensions. Section 5 is devoted to simulations both with randomly-generated graphs and with graphs arising form practical applications; we compare the solution compute by an ILP solver together with the solution found by an efficient polynomial-time heuristic. Finally, we conclude and give hints for future work in Section 6.

Related work

Memory and storage have always been limiting parameters for large computations, as outlined by the pioneering work of Sethi and Ullman [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF] on register allocation for task trees, modeled as a pebble game. The problem of determining whether a directed acyclic graph can be pebbled with a given number of pebbles (i.e., executed with a given number of registers) has been shown NP-complete by Sethi [START_REF] Sethi | Complete register allocation problems[END_REF] if no vertex is pebbled more than once (the general problem allowing recomputation, that is, re-pebbling a vertex which have been pebbled before, has been proven Pspace complete [START_REF] Gilbert | The pebbling problem is complete in polynomial space[END_REF]).

This model was later translated to the problem of scheduling a task graph under memory or storage constraints for scientific workflows whose tasks require large I/O data. Such workflows arise in many scientific fields, such as image processing, genomics, and geophysical simulations. In several cases, the underlying task graph is a tree, with all dependences oriented towards the root, which notably simplifies the problem: this is the case for sparse direct solvers [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF] but also in quantum chemistry computations [START_REF] Lam | Memory-optimal evaluation of expression trees involving large objects[END_REF]. For such trees, memory-aware parallel schedulers have been proposed in [START_REF] Eyraud-Dubois | Parallel scheduling of task trees with limited memory[END_REF], and the impact of processor mapping on memory consumption has been studied in [START_REF] Agullo | Robust memory-aware mappings for parallel multifrontal factorizations[END_REF].

The problem of general task graphs handling large data has been identified by Ramakrishnan et al. [START_REF] Ramakrishnan | Scheduling dataintensiveworkflows onto storage-constrained distributed resources[END_REF] who introduced clean-up jobs to reduce the memory footprint and propose some simple heuristics. Their work was continued by Bharathi et al. [START_REF] Bharathi | Scheduling data-intensive workflows on storage constrained resources[END_REF] who developed genetic algorithms to schedule such workflows. More recently, runtime schedulers have also been confronted to the problem: in the StarPU task-based runtime system, attempts have been made to reduce memory consumption by throttling the task submission rate [START_REF] Sergent | Controlling the memory subscription of distributed applications with a task-based runtime system[END_REF].

As explained in the introduction, we have previously proposed a way to restrict the potentially large memory needed for the traversal of a task graphs by adding fictitious edges [START_REF] Marchal | Parallel scheduling of dags under memory constraints[END_REF][START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF]. Our method consists in first computing the worst achievable memory of any parallel traversal, using either a linear program or a min-flow algorithm. Then if the previous computation detects a potential situation when the memory exceeds what is available on the platform, we add a fictitious edge in order to make this situation impossible to reach in the new graph. This study is inspired by the work of Sbîrlea et al. [START_REF] Sbîrlea | Bounded memory scheduling of dynamic task graphs[END_REF]. In that study, the authors focus on a different model, in which all data have the same size (as for register allocation). They target smallergrain tasks in the Concurrent Collections (CnC) programming model [START_REF] Budimlić | Concurrent collections[END_REF], a stream/dataflow programming language. Their objective is, just as ours, to schedule a DAG of tasks using a limited memory. To this purpose, they associate a color to each memory slot and then build a coloring of the data, in which two data items with the same color cannot coexist. If the number of colors is not sufficient, additional dependence edges are introduced to prevent too many data items to coexist. These additional edges respect a precomputed sequential schedule to ensure acyclicity. An extension to support data of different sizes is proposed, which conceptually allocates several colors to a single data, but is only suitable for a few distinct sizes.

While our previous study [START_REF] Marchal | Parallel scheduling of dags under memory constraints[END_REF][START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF] is a first step towards the design of efficient memory-bounded dynamic schedulers, it suffers from major shortcomings that prevents its use in actual runtime schedulers:

• First, the running time of the algorithm is too high: computing the worst possible memory, while done in polynomial time, is expensive (O(n 3 ) for a dense graph with n vertices), and it has to be called after each edge insertion, so potentially O(n 2 ) times. • Second, the algorithm assumes an unlimited number of processors, and thus the simultaneous execution of infinitely many tasks. Thus, it dramatically overestimates the amount of memory that may actually be needed by a parallel processing of the DAG. In the present work, we alleviate both problems, through a new model to finely take the number of processors into account, and a new algorithm with much reduced complexity for a special case of task graphs (series-parallel graphs).

Finally, a recent paper studies the problem of computing the maximum memory of a multithreaded computation [START_REF] Kaler | Cilkmem: Algorithms for analyzing the memory high-water mark of fork-join parallel programs[END_REF]. Their model is more complex and dedicated to Cilk programs, with the objective to derive low-complexity

RR n°9323

algorithms for this problem (typically linear-time algorithms).

Background

In Section 3.1, we introduce the SimpleDataFlowModel [START_REF] Marchal | Parallel scheduling of dags under memory constraints[END_REF][START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF] to study memory usage for general DAGs. This model is a natural extension of the original pebble game [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF], and of the model introduced by Liu for tree graphs [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF]. Then in Section 3.2, we discuss how to emulate more realistic models, and outline the limitations of the current approach.

The SimpleDataFlowModel

The target application is described by a workflow of tasks whose precedence constraints form a DAG G = (V, E). Each node i ∈ V represents a task and each edge e ∈ E represents a precedence constraint, expressed in the form of output and input data. The processing time necessary to complete a task i ∈ V is denoted by w i . The memory usage of the computation is modeled only by the size of the data produced by the tasks and represented by the edges. Specifically, for each edge e = (i, j), we denote by m e or m i,j the size of the data produced by task i for task j. We assume that G contains a single source node s and a single sink node t; otherwise, one can add such nodes along with appropriate edges of zero weight. An example of such a graph is illustrated in Figure 1. Memory consumption rules are remarkably simple in the SimpleDataFlow-Model. In the model, at the beginning of the execution of a task i, all input data of i are immediately deleted from the memory, while all its output data are allocated to the memory. We introduce the following definitions for the total input and output size of a node i ∈ V :

Inputs (i) = j|(j,i)∈E m j,i , Outputs (i) = j|(i,j)∈E m i,j .

RR n°9323

Now, the total amount of memory M used needed to store all necessary data is transformed as follows when task i is executed:

M used ← M used -Inputs (i) + Outputs (i) .
The SimpleDataFlowModel may seem unrealistic, because when we start executing a task, its inputs are immediately deleted and we only allocate memory for its outputs. In many scientific applications, it is required to store both the inputs and the outputs throughout the execution of the task, and maybe to allocate space for some temporary data internal to the task. Fortunately, many complex memory behaviors, including the latter one with input, output and temporary data co-existing in memory, can be emulated in the SimpleDataFlowModel, via some elementary transformations of the input DAG. Together with its simplicity, this versatility explains the appeal of the the SimpleDataFlowModel and its usage in the literature [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF][START_REF] Marchal | Parallel scheduling of dags under memory constraints[END_REF][START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF].

We detail elementary transformations to account for more complex memory consumption rules in Section 3.2. Beforehand, we explain how to estimate peak memory usage in the SimpleDataFlowModel. A schedule or parallel execution of a DAG with p processors is defined by:

• An allocation µ of the tasks onto the processors (task i is computed on processor µ(i)); • The starting times σ of the tasks (task i starts at time σ(i)). As usual, a valid schedule ensures that data dependences are satisfied (σ(j) ≥ σ(i) + w i whenever (i, j) ∈ E) and that processors compute a single task at each time step (if µ(i) = µ(j), then σ(j) ≥ σ(i) + w i or σ(i) ≥ σ(j) + w j ). When considering parallel executions, we assume that all processors use the same shared memory, whose size is limited. We say that the data associated to the edge (i, j) is active at a given time-step if the execution of i has started but not that of j. This means that the (output) data of i is present in memory.

We now compare parallel and sequential schedules. A sequential schedule S of a DAG G is defined by a total order σ of its tasks. Clearly, the memory used by a sequential schedule at a given time-step is the sum of the sizes of the active data. The peak memory of such a schedule is the maximum memory used during its execution, which is given by:

M peak (σ) = max i j s.t. σ(j)≤σ(i) Outputs (j) -Inputs (j) (1)
where the set {j s.t. σ(j) ≤ σ(i)} represents the set of tasks started before task i, including itself. Equation (1) demonstrates the simplicity of the SimpleDataFlowModel, where input data are replaced by output data as the execution progresses.

Furthermore, Equation (1) allows us to state a prominent feature of the SimpleDataFlowModel: there is no difference between sequential schedules and parallel executions as far as memory is concerned! More precisely, for each parallel execution (µ, σ), there exists a sequential schedule with equal peak memory: simply consider a sequential schedule that starts tasks in the same order as the parallel execution (see the detailed proof in [START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF]). A key consequence is that we can bound the maximum memory of any parallel execution: it is equivalent to computing the peak memory of a sequential schedule. Then, to compute the peak memory of a sequential schedule, we define a topological cut (S, T ) of a DAG G as a partition of G in two sets of nodes S and T such that s ∈ S, t ∈ T , and no edge is directed from a node of T to a node of S. An edge (i, j) belongs to the cut if i ∈ S and j ∈ T . The weight of a topological cut is the sum of the weights of the edges belonging to the cut. For instance, in the graph of Figure 1, the cut ({s, a, b}, {c, d, t}) is a topological cut of weight 11. Note that this cut would not be a topological cut if the edge (d, a) was present in the graph. In the SimpleDataFlow-Model, the memory used at a given time is equal to the sum of the sizes of the active output data, which depends solely on the set of nodes that have been executed or initiated. Therefore, the maximal peak memory of a DAG is equal to the maximum weight of a topological cut. It turns out that there exists an algorithm to compute a maximal topological cut with polynomial complexity O |V ||E| log |V | 2 /|E| [START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF]. As stated in the introduction, if the maximal topological cut exceeds the total memory available, we have proposed in our previous work to add fictitious edges that will go backwards (from T to S) and will decrease the weight of the cut. Unfortunately, the approach is very costly [START_REF] Marchal | Parallel scheduling of dags under memory constraints[END_REF][START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF]: we may need to insert

O(|V | 2 ) edges, each at a cost O(|V | 3 ) if the DAG is dense (with |E| = Θ(|V | 2 )).

Emulation of more realistic models

As explained above, the SimpleDataFlowModel does not account for the fact that inputs and outputs of a given task often reside in memory simultaneously. However, this is a common behavior for scientific applications, and some studies [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] further account for some temporary data m temp i that has to be in memory when processing task i (in addition to task inputs and outputs). The memory needed for processing task i becomes Inputs (i) + m temp i + Outputs (i). Such a behavior can be emulated in the SimpleDataFlowModel, as illustrated on Figure 2. Each task i is split into two nodes i 1 and i 2 . We transform all edges (i, j) in edges (i 2 , j), and edges (k, i) in edges (k, i 1 ). We also add an edge (i 1 , i 2 ) with an associated data of size Inputs (i)+m temp i +Outputs (i). Task i 1 represents the allocation of the data needed for the computation, as well as the computation itself, and its weight is thus w i 1 = w i . Task i 2 stands for the deallocation of the input and temporary data and has weight w i 2 = 0.

i w i = 10, m temp i = 1 2 3 i 1 10 i 2 0 2 6 3
Figure 2: Transformation of a task as in [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] (left) to the SimpleDataFlow-Model (right).

After this transformation, the graph includes two types of edges. The edges that were originally present in the graph and stand for regular dependencies between tasks are called the black edges. The edges that have been added to represent computations are called the red edges. Both edge types have different roles. In particular, there cannot be more than p red edges in a cut representing an actual state of a parallel computation of the graph with p processors. We now understand another limitation of the Simple-DataFlowModel: while it can emulate parallel executions with realistic memory rules, computing the maximum cut of the transformed graph will only provide a loose upper bound of the maximum memory needed by any dynamic schedule. In other words, we can still compute the maximum cut of the transformed graph, but it will overestimate the amount of memory that may actually be needed during a parallel execution of the DAG. One major contribution of this paper is to introduce a new framework which distinguishes between black and red edges to account for resource constraints.

Resource constraints

We formally state the optimization problem in Section 4.1 and assess its complexity in Section 4.2 for general graphs. We also formulate the problem as the solution of an Integer Linear Program (ILP) in Section 4.3, and we introduce an efficient heuristic. Finally, we give an efficient algorithm to solve the problem series-parallel graphs, or SPGs, in Section 4.4.

Optimization problem

As outlined in Section 3.2, when we transform an edge-weighted DAG G to the SimpleDataFlowModel, the resulting graph contains two different types of edges: those that correspond to edges of G, and those that correspond to computations (vertices of G). In terms of graph properties, this can be modeled as a 2-coloring of the edges. In what follows, computation edges are referred to as red edges, and communication edges as black edges. Recall that the memory weight of computation edges is the sum of the memory used by the input, the output and temporary data of the computation. Therefore, the weight of red edges will likely be larger than that of black edges, which only carry the weight of input or output data.

The max-cut of the graph may well go through an arbitrary number of red edges. However, if the program is scheduled on a platform with p processors, hence at most p computations can be executed in parallel. Therefore, the max-cut is an overestimation of maximum memory usage of the program, and the difference may be quite large especially because red edges have larger weights. Figure 3 In what follows, we will use the term "p-cut" to refer to a topological cut crossing at most p red edges, and "p-maxcut" for a topological cut with maximum weight among those crossing at most p red edges.

Complexity

As discussed in Section 3.1, computing the maximum-weight topological cut (without colored edges) of a graph can be done in polynomial time. We show that adding the constraint on colors of edges makes the problem very combinatorial:

Theorem 1. p-MaxTopCut is NP-Complete
Proof. The p-MaxTopCut problem is in N P : the set S of the cut (S, T ) is a polynomial certificate. One can check in polynomial time that the cut is topological, has weight at least W and includes at most p red edges. For the completeness, we use a reduction from the Max-k-SubsetIntersection (MSI) problem, which is NP-Complete [START_REF] Xavier | A note on a maximum k-subset intersection problem[END_REF]. The MSI problem is the following:

Definition 1. Given a set X, C = {S i } i∈[1,...,
l] a set of l subsets of X, two integers k ≤ l and q, find a subset I ⊆ [1, . . . , n] such that |I| = k and i∈I S i ≥ q. In other words, find k subsets S i such that the cardinality of their intersection is greater or equal to q.

Consider an instance I 1 of MSI: a set X, C a collection of l subsets of X, two integers k and q. Let n = |X|. We build the following instance of p-MaxTopCut: G = (V, E), where

V = {s, t} ∪ {u i |i = 1, . . . , l} ∪ {v j |j = 1, . . . , n} E = {(s, u i )|i = 1, . . . , l} ∪ {(v j , t)|j = 1, . . . , n} ∪ {(u i , v j )|x j / ∈ S i }
where the edges from s to the u i are red and have weight n + 1, the other are black. The edges from the v j to t have weight 1, and the edges from the u i to the v j have weight 0. Finally, let p = k and W = (n + 1)p + q. See figure 4. If a node v j has no predecessor (respectively a node u i has no successor), we can add a black edge (s, v j ) (respectively (u i , t)) with weight 0. This allows us to consider the case with only one source and target, but does not change the rest of the proof, hence we will omit these edges in the rest of the proof. Now, assume that I 1 has a solution, i.e. there are p subsets (S i ) i∈I of X whose intersection has cardinality at least q. Then consider the cut (S, T ) where

S = {s} ∪ {u i |i / ∈ I} ∪ {v j | no predecessor of v j is in S} RR n°9323 s t u 1 u i u l v 1 v j v n n + 1 n + 1 n + 1
(u i , v j ) ∈ E ⇔ x j / ∈ S i
and T = V \ S: it goes through the edges (s, u i ) for i ∈ I and through the edges (v j , t) for x j ∈ i∈I S i . It is a topological cut, has exactly p red edges and by construction of G, all the v j corresponding to the x j that are in the intersection of the S i are not linked to the corresponding u i . Therefore, we can put at least q of them in S, and the cut crosses at least q edges (v j , t) of weight 1. Hence, the cut has weight at least p • (n + 1) + q • 1 (the first term counts the weight of the red edges, the second term counts the weight of the (v j , t) edges), and therefore it is a solution to I 2 . Conversely, assume that I 2 has a solution, i.e. there exists a topological cut (S, T ) with at most p red edges and weight greater than (n + 1)p + q. It goes through exactly p red edges, otherwise if it goes through less that p red edges, it can have weight at most (p -1)(n + 1) + n • 1 as the other edges carrying weight are the edges of weight 1, and there are only n of them. As the weight is greater that (n + 1)p + q, we get that the cut crosses at least q edges (v j , t) of weight 1.

Let I = {i|u i ∈ T }, the set of the indices of the subsets corresponding to the (s, u i ) edges crossed by the cut. As remarked above, |I| = p = k, therefore we have selected exactly k subsets. To show that I is a solution to I 1 , we need to show that i∈I S i ≥ q.

Let Y = {x j |v j ∈ S} be the set of elements x j such that the edge (v j , t) is crossed by the cut. As mentioned above, the cut crosses at least q such edges, therefore |Y | ≥ q. For all y ∈ Y , as the cut is topological, we have that they are not linked to any if the C i , i ∈ I. Therefore, by construction of G, ∀i, y ∈ C i . Hence, y ∈ i∈I C i , and we get Y ⊆ i∈I C i , and therefore i∈I C i ≥ q, therefore I 1 has a solution.

Last, we show that this reduction is polynomial. The size of I 1 is n + l + log(q). We do not need to count log(k) as k ≤ l. The created instance I 2 has |V | = n + l + 2 nodes and |E| ≤ n + l + nl edges, and weight W = np + q, therefore log(W ) = O (log(n) + log(p) + log(q)). Therefore I 2 has size polynomial in the size of I 1 . Therefore, p-MaxTopCut is NPcomplete.

Integer Linear Program and Heuristic

The following Integer Linear Program (ILP) can be used to compute the p-maxcut:

max (i,j)∈E m i,j d i,j (2)
∀(i, j) ∈ E, d i,j = p i -p j (3)
∀(i, j) ∈ E, d i,j ≥ 0 (4)
p s = 1 (5)
p t = 0 ( 6
) (i,j)∈E isred i,j d i,j ≤ p (7) ∀i, p i ∈ {0, 1} (8)
The p variables are used to assign vertices to either S (p i = 1) or T (p i = 0). We consider that isred i,j = 1 if c(i, j) = red and isred i,j = 0 otherwise. This ILP is adapted from the one from [START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF] which computes the maximum topological cut of G. A single constraint has been added: Equation ( 7) limits the number of red edges from S to T to at most p.

In the case of the maximum topological cut without resource constraints, there is a simple way to solve this ILP by solving it over the rational numbers and rounding to integers. Unfortunately, due to the additional constraint (Equation ( 7)), the rounding procedure does not give a valid optimal value in the case of p-MaxTopCut. However, this gives the intuition for a heuristic. Starting from a fractional solution of the above linear program and a threshold value w ∈ [0, 1], we can derive an integer solution as follows: we take the p i s returned by the rational solution, and set p i to 0 in the integer solution if and only if we had p i ≤ w in the rational solution (and we let p 1 = 1 otherwise). This describes a topological cut, which might use more than p red edges. We propose to apply this rounding procedure to all possible values of w. In practice, we only have to consider all p i rational values for i = 1, . . . , |V | as well as w = 1. Among these |V | + 1 values of w, we return the topological cut with at most p red edges with maximum weight (if any). Note that this procedure may fail if no rounding produces a cut with less that p red edges. However, considering all the |V | + 1 rounding values makes this very unlikely. In particular, it never happened in all the simulations reported in Section 5: the heuristic always found a solution; furthermore,

RR n°9323

that solution was close to the optimal value in most cases (see Section 5 for details).

Series-Parallel Graphs

Series-Parallel Graphs, or SPGs, are widely used in the literature because they nicely model fork-join types of computations such as BSP (Bulk Synchronous Model) [START_REF] Cordasco | On scheduling series-parallel dags to maximize area[END_REF][START_REF] Finta | Scheduling uet-uct seriesparallel graphs on two processors[END_REF]. SPGs are defined inductively as follows: Definition 2. A series-parallel graph (SPG) is either:

• the "Edge" graph E(m, r) = ({s, t}, {(s, t)}): two nodes, the source and the target, linked by an edge. m is the weight of that edge, r ∈ {true, f alse} is true if and only if c(s, t) = red, • the series composition of two SPGs

G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 )
(with respective sources and targets (s 1 , t 1 ) and (s 2 , t 2 ):

Series(G 1 , G 2 ) = (V 1 ∪ V 2 , E 1 ∪ E 2 }) with source s = s 1 , target t = t 2 , with t 1 = s 2 in the resulting graph, • the parallel composition of two SPGs G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ): P ar(G 1 , G 2 ) = (V 1 ∪ V 2 , E 1 ∪ E 2 )
with source s = s 1 = s 2 and target t = t 1 = t 2 . Series and parallel composition are illustrated on Figure 5. Proof. A SPG is a binary tree of its constructors, called its decomposition tree (see Figure 6): leaves of the tree are the edges of the SPG, internal nodes are the series and parallel constructors. Note that every internal node has exactly two children, thus the tree is a full binary tree. Furthermore, given a series-parallel graph, its decomposition tree can be built in linear time [START_REF] Valdes | The recognition of series parallel digraphs[END_REF][START_REF] Bodlaender | Parallel algorithms for series parallel graphs and graphs with treewidth two 1[END_REF].

Furthermore, if G is the series composition of G 1 and G 2 , then a topological cut of G is either a topological cut of G 1 or of G 2 : the topological constraints forbid a cut that goes through both. Similarly, if G = P ar(G 1 , G 2 ), then any cut of G that goes through G 1 goes through G 2 as well. Therefore, a topological cut of G with p red edges will cross k red edges in G 1 and p -k red edges in G 2 , for some k, 0 ≤ k ≤ p. Finally, if G is a red edge (s, t), it has no topological cut with zero red edges, and one nonempty topological cut: ({s}, {t}). If G is a black edge, then its maxcut is ({s}, {t}).

Let M (G, k) denote the weight of the k-maxcut of a SPG G. The previous remarks lead to the following formulas:

s t a 1 b 1 c 1 G 1 s t a 2 b 2 c 2 G 2 s a 1 b 1 c 1 s t a 2 b 2 c 2 Serie(G 1 , G 2 ) : s a 1 b 1 c 1 a 2 b 2 c 2 t P ar(G 1 , G 2 ) :
M (Edge(m, T rue), 0) = -∞ (9)
M (Edge(m, F alse), 0) = m (10)
M (Serie(G 1 , G 2 ), k) = max {M (G 1 , k), M (G 2 , k)} (11)
M (P ar(G 1 , G 2 ), k) = max j=0...k {M (G 1 , j) + M (G 2 , k -j)} (12)
Using these formulas, one can compute M (G, k) using the values of M (G 1 , i), i = 1 . . . p and M (G 2 , j), j = 1 . . . p in time O(p) for each k = 1. . . p, hence in total time O(p 2 ). Using dynamic programming and storing the values of M (G , i), i = 1 . . . p for all G in the decomposition tree of G, one can compute the p-maxcut of G in time O(p 2 • N ), where N is the number of nodes in the decomposition tree of G. To conclude on the complexity, we need to show that N = O(|E|). It is well-known that for any l ≥ 1, a full binary tree (i.e. each node is either of leaf or has two children) with l leaves has exactly 2l -1 nodes1 . Using the fact that the leaves of the decomposition tree of G are exactly the edges of G, we obtain that N = 2|E| -1, and therefore the algorithm runs in time O(|E|p 2 ).

Simulation results

In this section, we perform simulations to assess the impact of resource constraints on the memory peak for dynamic schedulers. We also study whether the rounding heuristic described in Section 4.3 succeeds to compute a pmaxcut close to the optimal one.

Datasets

We used both synthetic task graphs and graphs from classical HPC applications. Specifically, we report experiments for five datasets. The first dataset is generated using the DAGGEN software [START_REF] Suter | Daggen: A synthetic task graph generator[END_REF]. We use the same parameters that were used to produce a dataset widely used in the scheduling literature [START_REF] Hunold | One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints[END_REF][START_REF] Desprez | A bi-criteria algorithm for scheduling parallel task graphs on clusters[END_REF][START_REF] Marchal | Limiting the memory footprint when dynamically scheduling dags on shared-memory platforms[END_REF]. These graphs count between 10 and 100 tasks.

Five parameters influence the generation of these DAGs. The number of nodes belongs to {10, 25, 50, 100}. The width, which controls how many tasks may run in parallel, belongs to {0.2, 0.5, 0.8}. The regularity, which controls the distribution of the tasks between the levels, belongs to {0.2, 0.8}. The density, which controls how many edges connect two consecutive levels, belongs to {0.2, 0.8}. The jump, which controls how many levels an edge may span, belongs to {1, 2, 4}. Combining all these parameters, we get a dataset of 144 DAGs.

The next three datasets represent actual workflow applications and have been generated with the Pegasus Workflow Generator [START_REF] Da Silva | Community resources for enabling research in distributed scientific workflows[END_REF]. We consider three different applications, named Ligo, Montage, and Genome, each containing 20 graphs of 50 nodes and 20 graphs of 100 nodes. We assumed that the memory needed during the execution of a node is negligible compared to the size of the input and output data, which must be kept in memory during this process.

The last dataset consists in the task graphs of the qr_mumps [START_REF] Agullo | Implementing multifrontal sparse solvers for multicore architectures with sequential task flow runtime systems[END_REF] application, when applied on matrices from the University of Florida Sparse Matrix Collection [START_REF] Davis | The university of florida sparse matrix collection[END_REF]. These matrices were ordered using either the colamd [START_REF] Davis | Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm[END_REF] or scotch [START_REF] Pellegrini | Sparse matrix ordering with scotch[END_REF] ordering. The 24 resulting task graphs are indeed trees of tasks whose size vary from 39 to 5900 nodes.

For all these graphs, we computed both the maximum topological cut (maxcut), the maximum topological cut with at most p red edges (p-maxcut) using the ILP Gurobi solver [START_REF]Gurobi optimizer reference manual[END_REF], and the solution returned by the heuristic. The C++ code used for the simulation is publicly available online at https: //github.com/GBathie/PMaxcut.

Results

The first set of simulations studies the impact of the number of processors (the value of p) when computing the p-maxcut, comparing it with to the maximum topological cut without any bound on resources (p = ∞). We plot in Figure 7 the ratios maxcut/p-maxcut obtained in all cases, using Tukey boxplots. The box presents the median, the first and third quartiles. The whiskers extend to up to 1.5 times the box height (interquartile range). While the results largely depend on the target, we observe globally that taking p into account when computing the maximum topological cut dramatically reduces its value in most cases. Note that in for better readability, we remove outliers from the plots, as they only concern special cases where the gain of using the p-maxcut instead of the maxcut was even higher. For the Pegasus datasets, the value of the cut is reduced at least by a factor 1.6 (LIGO with p = 10) and at most by a factor 17 (LIGO with p = 1). For QR-Mumps, the value of the cut is reduced at least by 5% (p = 10) and at most by a factor 1.38 (p = 1). For the DAGGEN datasets, this ratio goes from 1.10 tup o 5.5. In most cases, the ratio p-maxcut/maxcut decreases when the number of processors grows from 1 to 10, except for the MONTAGE graphs which exhibit a very large degree of parallelism.

Figure 8 presents the results of the heuristic for the MONTAGE and LIGO datasets, normalized to the optimal p-maxcut computed with the ILP. We use the same boxplots, except that outliers are drawn and appear separately as empty circles. We observe that the heuristic is able to find a cut with a weight very close to optimal only for small values of p. For all the other datasets, the heuristic finds a p-maxcut which is at most 2% smaller RR n°9323

Conclusion and Future Work

In this paper, we have revisited dynamic DAG scheduling under memory constraints. We have introduced a new model that takes resource limitation into account when computing peak memory needs. By coloring those edges that represent temporary memory requirements during task execution, we bound the memory actually needed during an execution with p processors as a function of p, while previous work assumed unlimited resources. The additional constraints due to resource limitation turn an otherwise polynomial problem into a NP-hard problem. We have introduced an Integer Linear Program (ILP) to solve it, together with an heuristic based on rounding the rational solution of the ILP. Furthermore, we provide an exact polynomial algorithm for the particular case of serial-parallel graphs. With an experimental study conducted over randomly-generated graphs and task graphs from actual applications, we show that our refined approach can significantly reduce the weight of the maximum topological cut.

Future work includes several promising directions. The first direction is to compare the ILP and the heuristic on task graphs of very large size, because we expect the ILP to fail providing a solution beyond a certain number of nodes. The second direction is to design efficient strategies to reduce peak memory in the refined model with colored edges, thereby extending previous approaches to the new model. The third direction is to study the behavior of a restricted class of dynamic schedulers which try and select low memory-consuming tasks. For instance, instead of progressing to execute any ready task, these restricted schedulers would only select ready-tasks whose memory requirements keeps total memory consumption below a given threshold. The algorithmic complexity of such approaches will however probably remain very high. In particular, it is not clear how to fix the global threshold so that the restricted schedulers have a good chance to execute the whole task graph without exceeding the memory constraint. Finally, the fourth direction would be to develop scheduling strategies that rely upon a coarse representation of the task graph instead of the complete graph, thereby allowing to deal with very large graphs while (hopefully) keeping a tight estimation of the total memory requirement. This would allow for an effective implementation of scientific application at scale within a task-based runtime system.

|V |), which is polynomial in the size of G. Therefore, BlockingTopCut ∈ N P .

To prove the hardness of BlockingTopCut, we use a reduction from the N P -complete problem 2-Partition [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]: Given a family of n ≥ 2 positive integers (a i ) i=1,...,n , ∀i, a i > 0, is there a subset I ⊆ {1, . . . , n} such that Let S = n i=1 a i , and set the weight of the edges as follows:

w(s, i) = 0, ∀i ∈ {1, . . . , n} w(i, t) = a i , ∀i ∈ {1, . . . , n} w(s, a) = S 2 w(a, b) = S 2 + 1 w(b, t) = 0
The resulting graph is shown on the Figure 9. First, if I 1 has a solution I ⊆ {1, . . . , n} such that i∈I a i = S 2 , then we define K = I ∪ {s}, and C = (K, V \ K). It is a topological cut: it contains vertices from 1, . . . , n and s, and the only edges entering these vertices are RR n°9323 from s. We then have

M (C) = u∈K v / ∈K w(u, v) = i∈I v / ∈K w(u, v) + v / ∈K w(s, v) = i∈I w(i, t) + v / ∈K w(s, v) = i∈I a i + 0 + w(s, a) = i∈I a i + 0 + S 2 = S 2 + S 2 = S ≤ M
Successors of C either contain one additional vertex from {1, . . . , n} or a. Adding j from {1, . . . , n} increases the value of the cut by a j > 0, it would then be strictly larger than S and therefore, strictly larger than M . Adding a increases the weight by 1, and the cut could have weight S + 1 > M . Hence, C is a solution to I 2 , the instance of BlockingTopCut.

Conversely, if I 2 has a solution, it is a cut C = (K, T = V \ K) with M (C) ≤ M , such that any successor C has weight M (C ) > M . We can then remark that the edge (a, b) cannot be in the cut (i.e. we cannot have a ∈ K and b / ∈ K). Otherwise, such a cut C would have a successor K ∪ {b} with value M ( C) -S 2 -1 ≤ M ( C) ≤ M , which would contradict the hypothesis that every successor must have value strictly greater than M .

Similarly, the edge (b, t) cannot be in the cut. Otherwise, either the cut contains all the vertices i ∈ {1, . . . , n}, or it doesn't have all of them. If it has all of them, then the cut is (V \ {t}), and it has a successor with value 0 ≤ M , the cut (V, ∅), which contradicts the hypothesis. On the other hand, if K contains only a set I {1, . . . , n} of the a i , then let j ∈ {1, . . . , n} \ I. The value of the cut is i∈I a i . The cut then has a successor where we add the vertex j, with value i∈I a i + a j ≤ n i=1 a i = S = M . This means that the cut K ∪ {j} (successor of K) has value lower than M , which contradicts the hypothesis.

Hence, if I 2 has a solution, K contains s but not a. It also contains some vertices i of {1, . . . , n}: let I = {1, . . . , n} ∩ K. By hypothesis, we know that M (K) ≤ M = S, and Because of this NP-hardness result, solving efficiently the Blocking-TopologicalCut problem seems out of reach. The optimization problem associated with the BlockingTopologicalCut and Topological-Traversability problems would be to find the highest k ≤ M such that there is no topological cut of weight lower than or equal to k, and such that all of its successors have weight greater than k. By using such a k to restrict the runtime (i.e., the rule is that it cannot schedule tasks that would make memory use to exceed k), it would be guaranteed that the computation would never use more than M memory -independently of the max cut of the task graph. Unfortunately, it turns out that an approximate value that is within a constant factor of the optimal value still might not be an acceptable solution. Figure 10 shows a task graph whose max cut is M = 2v (the graph can be traversed with maximum memory 2v), where v is also a solution (the graph can be traversed with maximum memory v), but where 3 2 v is not a solution (the graph cannot be traversed with maximum memory 3 2 v ). In other words, the set of solutions is not connected! This little example illustrates the difficulty of the optimization problem.

M (K) = i∈I a i + S 2 . Hence, i∈I a i + S 2 ≤ S ⇔ i∈I a i ≤ S 2 . K has a successor K = K ∪ {a}. By hypothesis, RR n°9323 M (K ) > M = S,

Other simulation results

See Table 1, Figure 11

Figure 1 :

 1 Figure 1: Example of a workflow, (red) edge labels represent the size m i,j of associated data, while (blue) node labels represent their computation weight w i .

Figure 3 :

 3 Figure 3: Example of DAG for which the maxcut is an overestimation of the maximum memory used. The weight of the maxcut (in blue) is 14. For p = 1, the max cut with at most 1 computation edge (red edges, green cut) has weight 10.

Figure 4 :

 4 Figure 4: DAG for the reduction:(u i , v j ) ∈ E ⇔ x j / ∈ S i

Theorem 2 .

 2 The p-MaxTopCut problem can be solved in time O(|E|p 2 ) for a SPG graph with |E| edges on a platform with p processors.

Figure 5 :

 5 Figure 5: Example of series and parallel composition of SPGs

Figure 6 :

 6 Figure 6: Example of SP Graph (left) and its decomposition tree (right). S = Series constructor, P = Parallel, E = Edge.

Figure 7 :Figure 8 :

 78 Figure 7: Influence of p when computing the p-maxcut for all datasets RR n°9323

i∈I a i = S 2 ?

 2 Let I 1 be an instance of 2-Partition. Consider the DAG G = (V, E), where V = {1, . . . , n} ∪ {s, a, b, t} and E = {(s, i), (i, t), i = 1, . . . , n} ∪ {(s, a), (a, b), (b, t)}

Figure 9 :

 9 Figure 9: DAG for the reduction

  Finally, we need to check that this reduction is indeed polynomial. The size of the graph G = (V, E) created is polynomial in n: |V | = n + 4 and |E| = 2n + 3. M = S = n i=1 a i has size polynomial in those of the a i . The construction of the graph can be done in time polynomial in |E| and |V |. This concludes the proof.

Figure 10 :

 10 Figure 10: Example of DAG for which the set of admissible solutions is not connected: both v and 2v are solutions, but not 3 2 v.

Figure 11 :Figure 12 :

 1112 Figure 11: Complete results (with outliers) for p-MaxTopCut/MaxTopCut.

  and M (K ) = i∈I a i + S 2 + 1. Therefore, we have Combining the last inequality with inequality above, we get that i∈I a i =

		i∈I	a i +	S 2	+ 1 > S
	⇔	i∈I	a i + 1 >	S 2
	⇔	i∈I	a i ≥	S 2	as the values are integers

S

2 . Hence, if I 1 has a solution: I.

Table 1 :

 1 Summary of the simulation results

	Dataset	p	average of	average of	cases with heuristic
			p-MaxTopCut/MaxTopCut p-MaxTopCut/Heuristic	= p-MaxTopCut
		1	14.654	1.000	0/40
	Genome	3	5.407	1.000	0/40
		5	3.318	1.000	0/40
		10	1.690	1.000	0/40
		1	16.926	1.306	4/40
	LIGO	3	10.001	1.836	13/40
		5	7.685	2.329	17/40
		10	6.691	4.001	29/40
		1	4.186	1.001	40/40
	MONTAGE 3	4.186	1.011	40/40
		5	4.186	1.038	40/40
		10	4.161	1.148	39/40
		1	1.385	1.000	0/29
	QR-Mumps	3	1.091	1.006	3/29
		5	1.052	1.000	0/29
		10	1.049	1.003	2/29
		1	4.611	1.000	0/144
	DAGGEN-1 3	2.004	1.031	8/144
		5	1.405	1.001	4/144
		10	1.095	1.001	3/144
		1	5.529	1.210	1/144
	DAGGEN-2 3	1.993	1.023	6/144
		5	1.430	1.005	3/144
		10	1.106	1.001	2/144
	RR n°9323

RR n°9323

See https://en.wikipedia.org/wiki/Binary_tree.RR n°9323

Appendix: Scheduling at runtime

In this section, we briefly discuss extensions of this work that go beyond bounding the maximum memory peak of a dynamic schedule by computing the p-maxcut of the colored DAG.

In practice, a dynamic scheduler that schedules tasks on the fly could be programmed to avoid scheduling tasks which would make the memory used by the parallel execution larger than the memory of the machine. Therefore, even if the p-MaxTopCut is larger than the memory of the machine, the runtime might still be able to find a scheduling of the graph that does not exceed the available memory. In this context, we would like to know whether the runtime will always be able to keep the memory of the computation under some threshold M , using the new rule of avoiding any task whose execution would exceed the memory currently available.. A sufficient condition that, for any stage of the computation that uses memory not greater than M , we can schedule another task such that the memory usage stays below M . If the opposite happens, then there exists a scheduling that reaches a situation where any choice leads the computation to use an amount of memory larger than M . We state the problem formally as follows: The TopologicalTraversability belongs to Co-N P , hence we considered its negation: Unfortunately, this latter problem is combinatorial:

Proof. We first prove that the problem is in N P . The certificate is simply the list of all the vertices in one set of the cut C. One can check in time O(|E|) that the cut is topological and that its value is lower than M . Furthermore, the cut has at most |V |-1 successors, as a successor has one vertex more than C. Hence, computing the values of all the successors can be done in O(|E| •


Véronique Lemoine

Stephanie Lerat

Marie-José Gremmo

Preservice

Veronique Lemoine-Bresson

Preservice Teacher Training for Diversity: A Research Project Based on an Intercultural Course

Keywords: Preservice teacher education, diversity, interculturality, reflexive practitioner

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

Introduction

Cultural diversity has been a prevailing theme in discussions about education over the past decade in Western Europe [START_REF] Meunier | Un rapport difficile à la diversité dans l'école de la République[END_REF][START_REF] Zimenkova | Diversity: Future Project of Current Challenge? Construction of the Term Diversity within Citizenship Education in Europe[END_REF]. Educators are concerned about how to adequately address needs among learners from different backgrounds, such as those who speak languages other than the school language at home. In addition to active educational practitioners who are in constant contact with a wide variety of learners, preservice educators are apprehensive about their ability to successfully navigate diversity in an educational context.

This paper discusses a research project, DiPerLang, Diversités des personnes et des langues (Diversity of Persons and Languages), whose aim is to provide French preservice Master of Education (M.Ed.) students with the opportunity to develop theoretical knowledge surrounding issues related to diversity through an intercultural course, and to apply this theoretical knowledge by developing pedagogical resources and carrying out workshops with school children. More specifically, this project seeks to address the following questions:

1. How do M.Ed students understand "diversity of languages and people"? How is this understanding (re)shaped in the context of an intercultural course? 2. How do these students apply this understanding a. to the development of pedagogical resources targeting school children, and b. when carrying out workshops based on these resources? c. How is such understanding (re)shaped during transmission? The main purposes of DiPerLang are threefold: To expose students through an intercultural course to the theoretical background necessary to address diversity in their future role as educators, including the opportunity to practically apply these concepts to a real-life teaching situation; to observe and analyze how students appropriate concepts related to diversity and how this understanding is transmitted to school children; and to contribute to the discussion about what teacher training should look like in the early 21 st century. This commitment to quality teacher training is reflected in the interventional research paradigm adopted, where "the researcher is not only the observer of a phenomenon, but intervenes in the action, in the research and the training of the participants" (Duchesne & Leurebourg, 2012, p.3).

This paper focuses on the exploratory stage of DiPerLang, beginning with an outline of the theoretical framework adopted, followed by a brief description of the participants. The two-phase methodology consisting of an intercultural course and the development of pedagogical resources is then described, followed by a preliminary analysis of a short written production by the participants. The paper closes with a discussion of the advantages of the adopted approach to diversity education, future developments of the DiPerLang project, and diversity education in teacher training in general.

Diversities and Interculturality: Theoretical Framework

As noted by [START_REF] Carton | Des usages du mot culture dans la recherche CECA[END_REF], most understandings of interculturality center around two major conceptions of culture. In the first set of approaches, culture is seen as that which is common to a group of people. This is what is generally understood when someone refers to "French culture" or "American Culture". This type of approach effectively reduces a person to a handful of characteristics, related to their supposed culture, and neglects the processes of person-to-person negotiation of meaning and understanding inherent to human interaction. Culture and language frequently go hand in hand in visions of culture stemming from this type of approach.

In the second set of approaches, the vision of culture moves beyond labels and considers an "individual as involved in a network of relationships which are in constant evolution and specific to that person" (Carton 2011, p.14). This is reflected in Abdallah-Pretceille (2004)'s foregrounding of the inter-part of interculturality as opposed to culture. By rejecting a static notion of culture, these approaches take into consideration the constant evolution of personal identities and pluralities through encounters and interactions in a variety of contexts. The resulting vision is that of an individual as diverse.

The approach to diversity adopted by the DiPerLang project opposes views of culture which overlook a basic fact about human interaction, succinctly captured by [START_REF] Wikan | Generous Betrayal: Politics of Culture in the New Europe[END_REF]: "Cultures don't meet. People do". Identity is seen as complex, fluid and constantly shifting. Every individual participates in a variety of "discourse systems" [START_REF] Scollon | Intercultural Communication: A Discourse Approach, 3rd Edition[END_REF] and is constantly navigating and managing diversity, even if using only one language. The way a linguistic message is delivered in an academic setting and a social setting can differ drastically, just as the way persons identify themselves in diverse situations can also differ.

Language and what is said about language plays an active role in the construction and perpetuation of social realities, and contributes to the symbolic power of a language variety (Bourdieu, 1992). Qualifying a given way of using a linguistic code, such as an accent, as desirable attributes more symbolic power to that language variety and, by extension, to the speakers who use it. At the same time, such recognition reinforces negative beliefs, or what Blanchet (2016) calls glottophobia -negative discrimination of people based on the use of linguistic forms deemed as inferior -towards speakers of other varieties. In short, attitudes surrounding language diversity in a social situation can contribute to the development and perpetuation of unjustified treatment of people based on the way they use language in a given context.

The omnipresence of language norms in the classroom context makes judgements regarding language frequent. One way for educators to take into account the diversity present in schools, is by developing an understanding of the various factors at play. With an adequate theoretical framework, they will be able to identify and question insidious ideologies and consider the universality of diversity and the diversities of each individual. The DiPerLang project, in addition to exposing M.Ed students to the theoretical background which can assist them in understanding diversity as interaction, evolution, shifting and change, also offers them the opportunity to transmit a more accurate understanding of these notions to school children.

Methodology Context and Participants

All of the participants were enrolled in the second-year of an M. Ed. at the École Supérieure d'Enseignement et d'Éducation (Lorraine Institute of Education), in France, in one of two programs: The Teaching and Accompanied Practice program (TAP) preparing them for a teaching career in the public primary school system, or the Instructional Design program (ID), for students pursuing a career in education outside the school system.

The exploratory phase of the Diperlang project (2016-2017 academic year) involved 24 TAP students and 21 ID students. All participants took an intercultural course given by one of the researchers (Lemoine-Bresson), a one semester mandatory course (27 hours) for the ID students, and a full-year optional course (64 hours) for the TAP group.

The exploratory stage of this project took place in two phases, the first one consisting of the Intercultural course and the second one the creation of pedagogical material. All of the participants took part in the first phase, and only 29 took part in the second phase.

The Intercultural course contents for Phase 1 were derived from three main bodies of work: The instructor's doctoral thesis [START_REF] Lemoine | Diversités franco-allemandes : pratiques interculturelles et autonomisantes en didactique des langues étrangères[END_REF] 1. The evolution and shifting of identities: the role of attribution of characteristics, the myth of homogeneity, essentialism (culturalism, differentialism, etc.); 2. The use of culture as an excuse, as an argument in favor of, as a fortress, as a strategy, as power (focusing on the notions of difference and diversity); 3. The multifaceted role of Inter-: interactions with self and others, intersubjective, interrelations, negotiations, agreement, disagreement.

During Phase 2, the students created pedagogical material to run workshops with schoolchildren dealing with diversity of people and languages. Throughout the stages of conception, preparation and running of the activities, they provided written feedback on their experience by critically reflecting on their teaching practice. In this paper, only the results of the first analysis of the personal texts from phase one will be considered.

Preliminary Results: Personal Experience Descriptions

In the Personal Experience Description (PED) activity, participants were asked to describe a personal experience with the Other and to interpret the experience using theoretical notions from the Intercultural course and formulating questions that arise from the situation. Through the PEDs it is possible to gain an appreciation of how the students' understanding of diversity of persons and languages is shaped and reshaped through interaction with the course in mind.

Criteria retained for analysis

As the activity was part of a summative evaluation, students' responses reflected this situation, in particular with respect to appealing to the instructor's expectations. Nevertheless, the PEDs ranged greatly in terms of context and the vision of interculturality depicted. The choice of the encounter and its description and interpretation provided insights into the students' understanding of the Other and what qualifies as an intercultural experience.

Description

One of the first elements analyzed was the students' position as either encountering the Other, in the role as the Other, or as an observer [START_REF] Rabatel | Les enjeux des postures énonciatives et de leur utilisation en didactique[END_REF]. The elements used to contextualize the experience, including the physical location, as well as the criteria used to construct and differentiate between the self and the Other were considered, especially since the importance of context for apprehending interactions was emphasized during the intercultural course. Another key element was the identification of the intercultural issue at stake, which demonstrates an understanding of how such issues arise. Special attention was paid to whether or not the student referred to a specific vision of the norm present in the situation described. Voices external to the experience but which contributed to the creation of attitudes, such as "I had been told that..." [START_REF] Deronne | Postures énonciatives du scripteur : le cas du mémoire d'IUFM[END_REF] were also taken into account.

Not all PEDs contained elements corresponding to all these criteria, nor to the criteria retained concerning the analytical part of the writing activity. Just as the use of various elements to construct the PED was taken into account in the analysis of these texts, the absence of elements was also considered.

Interpretation

In the second part of the activity the students were asked to interpret their PED. The reshaping of student understanding through interaction with the course material was considered through the use of terms for the theoretical notions covered in class. Contradictions in the text or the misuse of terms were also taken into account in the analysis. By deconstructing their experience through naming and questioning the obvious and beliefs taken for granted, factors contributing to the intercultural issue at stake can be accounted for. A potential influence of the course can also be observed through the questioning of various attitudes, experiences and visions. The table below summarizes the criteria retained for the analysis of the interpretation part of the activity:

1. Interpretation present: yes/no 2. Use of terms covered in class used 3. Naming and questioning the obvious 4. Theoretical notions present 5. Questions asked

Relationship between the description and interpretation

The third dimension taken into account was the presence or absence of a link between the description and the interpretation to establish the coherence between these two parts. The taking of a moral stance was also considered.

Sample PED and analysis

In order to demonstrate the applicability and the interest of the three-part analysis of the PEDs, the following sample PED, translated from French, will be considered:

My personal experience goes back to when I was still a psychology student (in the last year of my bachelor's degree), and we had a Polish or Russian (from a Slavic country) student in our class. She was a little bit older than I was and was already a nurse in her home country. What I am questioning are the thoughts, the representations that I had towards this foreign student.

First of all, I positioned myself in a hierarchical and folkloric manner: indeed, I differentiated between "her" and "us" (French psychology students), and as well, her accent seemed very "exotic".

I focused on her difficulties in written French: she didn't write very well in French and so she wasn't integrated and wouldn't succeed in her studies, according to me. I didn't try to find out if she was a critical thinker or if what she wrote was relevant, especially seeing as how she had made it to the 3 rd year of the degree program just like me. There was no real sharing between her and I. I didn't try to get to know her more. I literally excluded her from our group, whereas her nursing experience would have most likely enriched my "cultural and intellectual background.

As can be seen, the student's encounter with the Other takes place in the context of a university class in a recent past. The student describes herself and the Other using the criteria of nationality, profession, and age: a French psychology student, and an older Slavic nurse. The intercultural issue is that of inclusion/exclusion, attributed to a vision of a norm -the Other's lack of mastery of the French language.

Terms used in the intercultural course are present, notably "folkloric," "hierarchical," "us and them", and "positioning oneself." The obvious is named, the fact that "she didn't write well" and "had an exotic accent" were equated with a perceived inability to achieve success or to be a full-fledged member of the student group. The theoretical notions present include those from the course used, moving beyond a homogenous vision of a group (in this case, foreign students not completely mastering French) to understanding individuals in their own personal complexity (a trained nurse with experience and a 3 rd year psychology student, etc.).

The description of the experience serves the interpretation leading to the realization that the student allowed the vision of the linguistic norms to obstruct her view of the Other as a person, as a critical thinker, as a nurse with experience. Through the deconstruction and reconstruction of the situation, the student is able to question herself. The intercultural course has given the student the theoretical background and words necessary to reframe this past experience and to glean insight from it.

Discussion

The preliminary analysis of these PEDs gives insight into students' understanding of the Other and how they define an intercultural experience. Developing the ability to identify an intercultural issue and to account for the contributing factors allow students a means to reframe a past experience, as well as the tools necessary to frame future encounters. Some of the PEDs show that students are still negotiating their understanding of the relevant theoretical concepts, underlining the need to allocate sufficient course hours to intercultural courses and promoting the relevance of these courses to pre-service educators. Some students, in their interpretation of their experience, also indicate their desire to transfer this type of critical thinking to their own pupils. This reinforces the applicability of future educators developing a theoretical background in notions concerning diversity.

The analysis of the processes of creating pedagogical resources developed in the second phase of the exploratory stage of this project, and of transferring knowledge to school children, will provide additional insight into the (re)shaping of students' understanding of issues surrounding diversity and will aid in the preparation of the main phase of the project.

The latter, scheduled to take place during the 2017-2018 academic year, will enable the development of a more thorough analysis of the transformation of notions, by taking into account personal factors potentially influencing this process, such as past teaching, volunteer or educational experiences.

  /www.coe.int/t/dg4/linguistic/LangEduc/LE_PlatformIntro_en.asp). Theoretical references included, among others, Abdallah-Pretceille, Dervin, Wikan, Machart, Leyens, and Liddicoat. The course was divided into three modules, each dealing with different aspects of interculturality:

						, Dervin (2016)'s
	"methodological	toolbox"	and	European	Council	resources	(see
	http:/


Stanislaw FISZER Université de Lorraine

During the post-Stalinism "Thaw", in the 1960 Polish philosophers and historians of ideas, such as Adam Schaff, Leszek Kołakowski, Krzysztof Pomian offered a rereading of Marxism, challenging one of the last grand narratives of history. They all were branded "revisionists" and gradually forced into silence; while those officials who resented their loss of totalitarian controls were labeled "dogmatists" and were checked in their ambitions by the new First Secretary of the Party Władysław Gomułka who pledged a "Polish road to socialism". In general, the decade 1956-1966 was characterized by moderate reforms, an uneasy truce between divergent Party factions combating each other behind the scene, between the Party and the Roman Catholic Church, and between the government and public opinion.

Very orthodox and rigid in his early writings, in 1955 Kołakowski joined the editorial staff of Po prostu (Straigt Talk), a rebellious weekly of young Communist intellectuals. The paper was to become a major force preparing the "Polish October" of 1956. This year, he published Responsibility and History, four part critique of Soviet-Marxist dogmas, in the Polish periodical Nowa Kultura (New Culture). Some of his philosophical essays were translated into Western languages 1 , often to his uneasiness, for as a member of Polish United Worker's Party, he had no wish to add fuel to the non-Marxist or anti-Marxist opposition. In these years Kołakowski won the acclaim of the young generation as the sharpest mind among the "revisionists" and became close to Adam Schaff, considered the official ideologue of the Party. In 1965, the latter published Marxism and the Human Individual (Marksizm a jadnostka ludzka)2 , placing this one in the center of his reflection influenced by Sartre's Reason (1960). The same year Kołakowski and Pomian published an anthology of The Existentialist Philosophy which shows how increasingly fascinated they were by different currents of this thought.

Critique of Dialectical

The Polish revisionists pursued three principal objectives. In the first place they rejected Stalinist's dogmas, principally the doctrine of the sharpening class struggle under socialism and the idea that the class enemy must be stamped out by terror. Kołakowski identifies Stalinism with a sect which "surrounded itself with an impenetrable ideological and ritualistic fence" and "peopled its world with a thousand new deities, each demanding worship under threat of excommunication on grounds of atheism."3 With the rejection of the dogma, Marxism was reappraised and the stress was laid on the thought of the young Karl Marx4 and the theory of alienation. In Schaff's opinion "when Marxism lost sight of the problems of the individual and emphasis was shifted to the study of mass movement, neglect of everything connected with the individual was a natural result."5 But, over and above that, the revisionism was an attempt to enrich the Marx's philosophy and to transcend it because, as Schaff says, "it is foolish […] to remain blind to the fact that [the] course of [history] has been different and has taken place in conditions other than those originally envisaged, and to cling to old formulas that were suited to other conditions." 6 In other words, the Polish revisionists subscribed to Marx's conception of communism as a movement changing reality and not as a steady state of affairs.

Shifting emphasis from masses to individuals, the revisionists reconsidered the role of intellectuals in the modernization of the Marxist's theory. Kołakowski asserts that "the spiritual dominion of any ruling class over the people […] depends on its bonds with the intelligentsia."7 By these words he identifies himself with a long Polish tradition which regarded the intelligentsia as an elite of the nation, aspiring to preserve and shape its constantly threatened identity and trying to place itself above all partisan interests. Furthermore, Kołakowski evokes the figure of a priest and a jester, deep-rooted in the Polish and Central European literature and culture:

The priest is the guardian of the absolute; he sustains the cult of the final and the obvious as acknowledged by and contained in tradition. The jester is he who […] doubts all that appears self-evident […] reveals contradictions in what appears obvious […] derides common sense and reads a sense into the absurd. 8 It is obvious that in the context of the 60 the priest symbolizes all dogmatists, whereas the jester embodies a handful of revisionists. Although Kołakowski recognizes a dialectical interdependence of priest's and jester's philosophies, he declares himself in favor of the second one for which the Stalinist doctrine became a subject of derision. By the way, Kołakowski, apparently inspired by Witold Gombrowicz, sees in the conflict between the jester and the priest the clash between the traits of adolescence and senility. Besides derision, he recommends adopting "inconsistency" as a philosophical method and an "individual attitude […] which is merely a consciously sustained reserve of uncertainty, a permanent feeling of possible personal error."9 Thus Kołakowski revives the old philosophical skepticism which was incompatible with unquestionable optimism and faith in a steady progress.

The revisionists focused on individual, reinterpreting the Marx's theory of alienation adapted from Feuerbach's The Essence of Christianity (1841). They disagree in particular with Engels's opinion that the transition to socialism is a leap from the realm of necessity to the realm of freedom. In fact, the abolition of private property, as the appropriation of human life, didn't eliminate alienation and the dehumanization of life. In socialist countries there are various forms of alienation, principally resulting from the existence of the State which is an alienated force. During the Stalinist's period, the State was a coercive machine that began to crush and annihilate its makers. The Polish October Revolution was a natural reaction against the "cult of personality" and the dictatorship of the Communist Party. Nevertheless, according to Adam Schaff, in the post-Stalinist socialist countries the State is an indispensable administrative and bureaucratic machine whose existence results from the technological complication of the modern world, unimaginable in Marx's epoch. If the vast and complicated State machinery of administration has to remain, a social division based on the exercise of power can't be eliminated. In this situation, the struggle for democratization of social life and against bureaucracy, often identified with "red bourgeoisie" or a "new class", should be conceived in Schaff's opinion "as a struggle against bureaucracy that is bad, unreasonable, incompetent […] but not against […] bureaucracy in general". In any case, given the transformations of the modern civilization, the State, under capitalism as well as under and socialism, would remain what it is: a Moloch compared with which the individual is a very atom.

The second major aspect of alienation in socialist societies is the alienation of labor which results from its division and specialization. Marx analyzed the nature of this alienation under capitalism. But Schaff claims that "the technical aspects of the problem cut across all systemsfor example, work on an assembly line is inherently the same regardless of government." 10 The only way to overcome it would be by reducing working time. On the other hand, independently of the character of government and political system, a world in which man has attained the power of self destruction and could be unable to control the forces he has himself released, is an alienated world. As we see, Shaff regards as utopian the Marxist's theory of the elimination of alienation in socialist societies. Proposing to soften its effects, he doesn't believe in the possibility to eradicate it entirely in the modern world of ever more universal relations linked with modern techniques of production and means of communication. From this point of view, he differs from both dogmatists and radical revisionists who under the influence of the utopian socialism hoped to create a society of selfgoverning associations of free producers. Moreover, this idea was still very much alive in the ranks of Solidarity in the 80.

The problem of national and social freedom was a central issue of the Polish October.

The slogans like "We want a free Poland", "Down with the Russians" were chanted along with "Down with the Communist dictatorship", "We want free elections" at thousands of meetings. Gomułka himself, enthusiastically supported by the great majority of society, in his public speeches, criticized the hardships of Stalinism and promised reforms to democratize the country and liberalize the State's policy. Thus, Polish communists found themselves unexpectedly at the head of a nation liberation movement. These circumstances combined with openness to existential philosophy urged the revisionists to re-examine the question of the freedom and individual's relationship to history. Working on the principle that man is not only a product of history but also its maker, they tried in particular to answer how to solve the conflict between the objective Marxist laws of historical development and the individual's free will, necessity and freedom. In chapter "The individual and history" of his book Marxism and the human Individual, Adam Schaff attempts to reconcile Marxist historical determinism with Sartre's existential indeterminism, arguing that man could only become free and able to shape his own life and history as he became conscious of the determinisms to which he is subject. He asserts that freedom is a recognized necessity:

For what matters is not that the choice made by man should be unconditioned, but that it should be made of his own free will and not the result of coercion by some external force.

Man's freedom is not measured by the degree of his […] detachment from social determinants (which in any case is a fiction) but by the extent to which he understands his purposes and the ways of achieving them through choice of the proper action. 11 In other words, freedom is to be found wherever the individual can choose, without being forced, between a number of courses of action, even though his choice is determined by some social or individual factors and can be explained in terms of them.

Kołakowski goes even further reasserting the personal, or "subjective", factor in history. In his essay Responsibility and History, he questions historical determinism which is "by nature vague" 12 . In obedience to Stalinist doctrine, socialism was historical inevitability and individuals were subordinated to it as its tools. Morals had to conform to the necessary process of progress whose nature was arbitrary defined by the Communist party.

Consequently, all the crimes perpetuated in the name of this historical necessity, described as the demiurge of history, were regarded as morally good actions. Kołakowski claims the "ethical individualism" according to which it is impossible to evaluate morally the good or bad results of an anonymous historical process, of a group or social class. Only human beings and their deeds are subject to moral judgment 13 . 11 Ibid.

12 Toward a Marxist Humanism, p. 124. 13 Kołakowski asserts that "Real social involvement is moral involvement […] each individual's participation in any specific form of political life is a moral act for which that individual is wholly responsible. No one is relieved of either positive or negative responsibility on the grounds that this actions formed only a fraction of a given historical process […] A soldier is morally responsible for a crime committed on the orders of his superior; an individual is all the more responsible for acts performedsupposedly or in facton the orders of an anonymous history", ibid., p. 140.

In his approach to the dilemmas facing the individual and his relationship to history Kołakowski is undoubtedly closer than Schaff to the existentialist conception of man as an autonomous monad of consciousness, "lonely" and "doomed to freedom". But both of them take a very similar position claiming the freedom of scientific and artistic expression, subjected to a strict control under Stalinism. According to Schaff, " it must be an axiom that scientific work can only be reached through the investigations of scientists, and artistic truth through the explorations of artists." 14 It can be noted in passing that a relative normality of development that art, literature and science had recovered during the Polish October, has been maintained until the collapse of socialist regime, in spite of the existence of censorship. In the 1960 a flow of translations from English and French brought to Polish readers Albert Camus, Jean-Paul Sartre, Faulkner, Beckett, Ionesco. Several forerunners of existentialism, such as Witkacy and Gombrowicz, whose names had been forbidden, came to the surface. A multitude of writers whose debuts had been delayed during the preceding period could publish their works. In their poems, Herbert and Szymborska conjured large existentialist puzzles, while the Polish Film School underlined the role of individual as opposed to collectivity.

We can observe that by focusing on the individual, the revisionist Marxists express the Polish society's aspirations in the post-Stalinist period. In this manner they convey Marxism humanism closely connected with the concept of happiness. As a matter of fact, the young Marx wanted to make man happy by eliminating the existing social causes of human unhappiness and by liberating the individual from alienation. Communism was regarded as the best means to realize this ideal: having eradicated the roots of human misery as a mass phenomenon it should give each person free play in the pursuit of happiness and let him be happy in his own way. From this point of view, Stalinism was the opposite of Marxism because, by abolishing individual identity, it tried to impose the same stereotype of happiness on everybody. Quoting Zamiatin's We and Orwell's 1984, Schaff asserts that "a society that, to achieve a fusion of individual and public interests, strives to enforce a generally binding model of human happiness must inevitably end with a horrifying tyranny that stifles the individual with a totally dehumanized life." 15 However, let us not forget that, according to the revisionists, the pursuit of individual happiness in socialist countries should go hand with hand with the development of a social 14 Marxism and the Human Individual, p. 157. Kołakowski says on this subject: "There exists now a clearly recognized need to attack the degenerate, cancerous growth of the ideology which led to the belief that Party must profess certain dicta on the laws of biological heredity or the best forms of musical expression, in Toward a Marxist Humanism, p. 168. 15 Marxism and the Human Individual, p. 179. attitude. This one is the reverse of a narrow egoism which results from the market competition and the idolatrous worship of money raised to the status of supreme value. For the aim of communism is, in the words of Schaff, "to make men regard not only such things as stealing as dishonest and indecent, but also any kind of selfish behavior which, by the standards of capitalist society, is perfectly compatible with honesty and respectability." 16 As for the young Kolakowski, his defense of human and humanistic socialism is accompanied by his criticism of the "lure of capitalism" which, in his opinion, "is very great in Poland."

The revisionists wanted to democratize Polish society and to involve its members in public affairs through activity in social organizations and by a devolution of certain kinds of power, above all in the economic and administrative field, to civic and workers' organizations. Nevertheless, some of them tried to justify by international situation the dictatorship of the proletariat which, according to Marx, was to be a relatively brief postrevolutionary phase. In 1965, Schaff puts the question: "can the socialist countries permit themselves as broad a development of democracy as they would like? Can they solve the problem of the personal liberties of the citizen as they would like?"; and he answers: "No, they cannot." 17 In order to shorten the transition stage from dictatorship to democracy, the revisionists advocate the formation and cultivation of libertarian attitudes and habits, stamped out by the Stalinist terror. Schaff encourages to "cultivate a new human personality that would be distinguished equally by commitment to social concerns and responsibility for them as by independence of mind and intelligent disobedience if this is required by the social good." 18 We might reasonably assume that these words show social hopes for progressive democratization after Gomulka's "thaw". It is undoubtedly true that the era of Stalinization of Poland had forever ended and that society became more liberal in the late 1950 and in the early 1960. There was some normalcy, life looked a little more comfortable. Tadeusz Różewicz, one of the best known Polish postwar writer, eludes to this in his play Witnesses, published in 1962 and subtitled Our little stabilization. Already in the play's first hundred words, the author remarks on the change in climate, stating: "we again have something resembling poetry", and follows it immediately with what will be a recurring refrain: "we cross our legs"for the first time in years, one can sit back and relax. But eventually, aspirations for full liberalization were proven false, as Gomulka's regime became more conservative. In the second half of the 1960 one could observe a growing disparity between 16 Ibid.,p. 202. 17 Ibid.,p. 214. 18 Ibid,p. 216. intellectual and political life in the country. The revisionists' hopes for progressive political change in Poland were replaced with disillusionment which is one of the principal causes of their breaking off with the Party and, as for some of them, their progressive rejection of the concept of Marxism as a separate school of thought. But, as Kołakowski asserts in Permanent and Transitory Aspects of Marxism, the most significant division is not between orthodox Marxists on one hand and everyone else on the other. It is between the Right and the Left in the humanities. And by the intellectual Left he means: "radical rationalism in thinking […] an entirely secular view of the world; criticism pushed to its utmost limits, distrust of all closed doctrines and systems; striving for open-mindedness, that is, readiness to revise accepted theses, theories, and methods." 19 This attitude is one that, in my opinion, constitutes a permanent aspect of revisionist thought and an interesting proposition for the intellectual Left even today. 19 Toward a Marxist Humanism, p. 185.

Leszek Kołakowski, Toward a Marxist Humanism. Essays on the Left Today(New York, 1968).

The book was translated in English under the title of Marxism and the Human Individual(New York, 1970).

L. Kołakowski, "Responsibility and History", in Toward a Marxism Humanism, p. 99 and 100.

The Young Marx was considered part of humanist "bourgeois" philosophy, which Marx later criticized along with German Idealism, on behalf of "social relations" which primed over individual consciousness, a product of ideology according to him. Marxist revisionists stressed the humanistic philosophical foundations of Marx's thought by focusing on the Economic and Philosophical Manuscripts of 1844 (first published in 1932, and largely suppressed in the Soviet Union until the post-Stalinist "thaw"). Marx there expounds his theory of alienation adapted from Feuerbach's The Essence of Christianity (1841).

Marxism and the Human Individual, p. 98.

Marxism and the Human Individual, p. 193.

L. Kołakowski, "Intellectuals and the Communist Movement", in Toward a Marxism Humanism, p. 139.

L. Kołakowski, "The Priest and the Jester", ibidem, pp. 33 and 34.

L. Kołakowski," In Praise of Inconsistency", ibid. 214.

Marxism and the Human Individual, p. 148.