Alexandre Honorat

Karol Desnos

Mickaël Dardaillon

Jean-François Nezan

A Fast Heuristic to Pipeline SDF Graphs

Keywords: SDF, pipeline, parallelism, throughput

A common optimization of signal and image processing applications is the pipelining on multiple Processing Elements (PE) available on multicore or manycore architectures. Pipelining an application often increases the throughput at the price of a higher memory footprint. Evaluating different pipeline configurations to select the best one is time consuming: for some applications, there are billions of different possible pipelines. This paper proposes a fast heuristic to pipeline signal and image processing applications modelled with the Synchronous DataFlow (SDF) Model of Computation (MoC). The heuristic automatically adds pipeline stages in the SDF graph in the form of delays, given the Execution Time (ET) of the actors and the number of PEs. The heuristic decreases the time spent by the developer to pipeline its application from hours to seconds. The efficiency of the approach is illustrated with the optimisation of a set of signal and image processing applications executed on multiple PEs. On average, when adding one pipeline stage, our heuristic selects a stage resulting in a better throughput than 90% of all possible stage emplacements.

Introduction

Synchronous DataFlow (SDF) [START_REF] Lee | Synchronous data flow[END_REF] is widely used to model signal and image processing applications and to optimize them on multicore embedded systems. Pipelining is made possible in SDF by adding delays. Delays represent initial data in buffers, which break data dependencies. This method has already been proved to be efficient on SDF applications [START_REF] Lee | Pipeline interleaved programmable dsp's: Synchronous data flow programming[END_REF] but usually requires to add the delays manually in the SDF graph or to call heuristics [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF]. Indeed, computing the optimal throughput of an application is a problem of high complexity that also requires computing the scheduling, the mapping and the pipelining.

In this paper we propose a fast heuristic to automatically pipeline an application modelled with an SDF graph. This heuristic is performed before mapping and scheduling the application, and is thus suboptimal but fast and scalable. It automatically adds delays in the SDF graph, given the number of Processing Elements (PEs) and application profiling information. The heuristic is parametric: the user can choose the number of pipeline stages that he wants to add. Various experiments demonstrate that our heuristic increases the throughput of the majority of the tested applications. When adding one pipeline, the heuristic finds the solution ensuring optimal throughput for 19 applications out of 24 tested.

The paper is organized as follows. Section 2 presents the main properties of the SDF Model of Computation (MoC). Section 3 specifies the notion of pipeline for SDF graphs and outlines necessary conditions for their validity. The main contribution, automatic pipelining of SDF graphs, is developed in Section 4. Extensive experiments follow in Section 5 with both theoretical evaluation of the throughput gain and real measurements on hardware. The main drawback of pipelining, memory footprint increase, is also quantified. Related work is presented in Section 6. Finally, Section 7 concludes this paper.

Background

SDF [START_REF] Lee | Synchronous data flow[END_REF] graphs are directed multi-graphs annotated with data communication rates. The vertices are called actors, and the edges are called buffers. Actors correspond to the processing of the application, while buffers contain the data sent from an actor to another. Data stored in a buffer are called tokens. Two rates are specified per buffer b: a production rate prod(b) ∈ N * on the sending side of b, and a consumption rate cons(b) ∈ N * on the receiving side. Hence, each time an actor is fired, which means its computations are executed, it consumes and produces a fixed number of tokens on each input and output buffers, respectively.

Only consistent SDF graphs are considered in this paper. An SDF graph is consistent when there exists a finite number of firings of each actor bringing back all buffers with the exact same number of tokens as initially. Such minimal number of firings is called a repetition vector and denoted r. It is computed from the buffers production and consumption rates.

To avoid deadlocks, cycles of the graph need initial tokens in at least one of their buffers. These initial tokens are called delays. The size of a delay on a buffer b, that is the number of initial tokens that b contains, is denoted d 0 (b). In this paper, it is assumed that the user already set delays in cycles, ensuring no deadlock. Delays are not restricted to cycles though; when placed correctly and outside cycles, delays cut some data dependencies and create pipeline stages. This point will be discussed and illustrated in the next section.

The contribution of this paper is a heuristic for automating the placement of pipeline delays in any SDF graph. Following the semantics introduced in [START_REF] Arrestier | Delays and States in Dataflow Models of Computation[END_REF], we assume all delays being permanent, which means that their token values are transmitted from one graph iteration to the next.

Admissible graph cuts for pipelining

Admissible graph cuts for pipelining correspond to feed-forward graph cuts as defined for the design of integrated circuits [START_REF] Parhi | VLSI digital signal processing systems : design and implementation[END_REF]. A graph cut is a set of edges which, if removed, disconnects the graph in two or more components. In a feedforward graph cut, all edges of the cut are going in the same direction. Hence, such cut cannot contain an edge from a cycle. The direction of an edge is deduced from the topological ranks of the actors. An example of actor ranks of As Soon As Possible (ASAP) and As Late As Possible (ALAP) topological orderings is presented in Figure 1a. Lowest actor rank 1 correspond to actors without input buffers, and the highest actor rank correspond to actors without output buffers.

A pipeline is created by adding delays on all buffers of a feed-forward graph cut, in order to break the data dependencies. For example, the feed-forward graph cut (dashed line) between topological ranks 1 and 2 of the graph in Figure 1a breaks the data dependencies between actors A and B, and A and ∆. The pipeline increases the throughput of the graph, as depicted in Figure 1b. In Figure 1a as in all SDF graphs presented in this section, rates are all equal to 1 for simplification. The throughput is defined by the inverse of the Initiation Interval (II) duration, that is the duration to periodically execute a graph iteration. A graph iteration contains as many firings as in the repetition vector r. We assume that there is a synchronization barrier at the end of each graph iteration. On the left part of Figure 1b, without pipeline, the II duration is 3, whereas on the right part, the II duration is only 2 with the pipeline. Note that, depending on the topological ordering, the graph cuts may not be identical.

To create a pipeline on an SDF graph, the size of a delay on a buffer b must be equal to If multiple feed-forward graph cuts contains the same buffer, the delay sizes are summed. In this paper, the number of pipelines n correspond to n different feed-forward graph cuts, dividing the execution of the application in n+1 stages.

A 1 B 2 Γ 3 ∆ 2/3 T (a)
Graph example annotated with ASAP and ALAP topological orderings. ALAP ordering is specified with T , only if different from ASAP.

1 2 3 PE 1 A ∆ PE 2 B Γ 1 2 PE 1 A ∆ PE 2 B Γ (b)
Two schedule examples of graph 1a on two PEs: on the left without pipeline, on the right with one pipeline between ranks 1 and 2.

Fig. 1: Topological ordering and schedule example without and with pipeline.

Unfortunately, the number of admissible graph cuts may be large. An example is given with a commonly used split-join graph topology [START_REF] Tendulkar | Symmetry breaking for multi-criteria mapping and scheduling on multicores[END_REF], which is a subcategory of SDF graph. Although the graph represented in Figure 2 only contains 4 parallel paths with 3 buffers each, 3 4 = 81 cuts are admissible. Indeed, if l paths connect a split actor to a join actor, each path having m buffers, the total number of feed-forward graph cuts is equal to m l . Because the number of admissible graph cuts may grow exponentially with the number of edges of the graph, exploring them all is not feasible. For this reason, our heuristic algorithm will only explore a subset of the admissible cuts. For example, our heuristic considers at most 3 admissible cuts for the graph in Figure 2. Those admissible cuts are detailed in the next section.

Automatic pipelining of SDF graphs

The automatic pipelining heuristic has two main steps: (1) generation of topological graph cuts, (2) selection of topological graph cuts. The first step, described in Section 4.1, computes a subset of admissible cuts. The second step, detailed in Section 4.2, selects a few cuts among the cuts computed in step (1).

Computing topological graph cuts

The heuristic selects a subset of admissible graph cuts: topological graph cuts according to the ASAP and ALAP topological orderings. A topological graph cut of rank c contains all buffers coming from an actor of rank lower than c and going to an actor of rank higher than or equal to c. Such topological cut is admissible if none of its buffers is part of a directed cycle of the graph.

The number of admissible topological graph cuts is upper bounded by the diameter of the graph, that is the number of buffers on the longest path. For example, the graph depicted in Figure 2 admits only 3 topological cuts according to ASAP graph ordering, whereas this graph admits 81 admissible cuts in total. Moreover, in the case of Figure 2, ASAP and ALAP graph orderings are identical so the same 3 graph cuts are considered for both topological orderings.

In order to build the ASAP and ALAP topological orderings, a cycle analysis of the graph is run first: the Johnson's algorithm [START_REF] Johnson | Finding all the elementary circuits of a directed graph[END_REF] computes all simple cycles of a directed graph. Johnson's algorithm upper bounds the complexity of the whole heuristic. The buffers being part of cycles are recorded to later filter the admissible cuts. For example, the topological cut of rank 3 in the SDF graph depicted in Figure 1a is invalid since there is a cycle between actors B and Γ .

Note that it is assumed that the user sets enough delays on at least one buffer of any cycle, so that this buffer breaks the data dependency of the cycle. Thanks to this assumption, ASAP and ALAP orderings are computed by a mere breadth first search on the graph, not visiting the buffer breaking each cycle.

The number of admissible topological graph cuts is small and upper bounded by the graph diameter, enabling our heuristic to be fast. The admissible topological graph cuts naturally include all cuts located at sequential bottlenecks of the application, so they are the best candidates to increase the application performances by pipelining. Formally, sequential bottlenecks are located on single paths of the graph: when two successive actors of ranks c -1 and c are the only actors having these ranks. Selecting such cuts particularly benefits the applications having single paths and their repetition vector equal to 1.

Selecting best topological graph cuts

To select the best topological graph cuts, the presented heuristic relies on a map linking topological ranks to an estimate of the Execution Time (ET) of all their actors. By definition, all actors having the same topological rank can be executed in parallel. We introduce a few notations to formalize the computation of this map. T (a) denotes the Execution Time (ET) of an actor a. The number of firings of a is r[a]. The rank of a is rank(a). The number of PEs is #PE. The ET estimate of rank c, denoted rankLoad(c), is computed as follows in Equation [START_REF] Allan | Software pipelining[END_REF].

rankLoad(c) = rank(a)=c r[a] #PE × T (a) #{a| rank(a) = c} (1)
The main purpose of Equation ( 1) is to provide a metric indicating if cutting before actors of rank c improves the throughput, that is to balance the computation before and after the cut. To do so, we actually compare the estimated ET of all ranks before the cut of rank c, 1≤i<c rankLoad(i), with the estimated ET of all ranks after the cut of rank c, c≤i rankLoad(i). However, it is needed to weight the ranks according to the amount of parallelism that they contain, so that the graph is cut where it matters most: on single paths for example. Thus, Equation (1) contains two divisions in order to reduce the weight of already parallel ranks: the repetition factor is divided by #PE, and the whole sum is divided by the number or actors in the considered rank. The rankLoad is averaged for both ASAP and ALAP topological orderings.

The selection of cuts is parameterized by two integers: the number of cuts wanted by the user x, selected among the number of balanced cuts to consider y (denoted D x, y in Section 5). We always have x lower than or equal to y, and y lower than the highest actor rank. y helps to define a first set of equally distributed topological graph cuts. To do so, the sum of all rankLoad(i) is divided by y, giving an average stage load avgStageLoad. Then we enumerate ASAP cuts by increasing order of their rank, and select the closest ones to a multiple of avgStageLoad. The same operation is performed on ALAP cuts sorted by decreasing order of their rank. At most, 2×y balanced cuts are selected, since cuts selected with ASAP and ALAP orderings may not be identical. Both orderings are considered in order to avoid selecting 0 cuts because of unbalanced ETs.

The last step of the heuristic is to select x cuts among the 2×y balanced cuts. This is done by two means: removing cuts that are too close from each other, and then selecting the one using less delays. Two topological cuts of rank c 1 and c 2 are considered too close from each other if the sum of their intermediate estimated ET is lower than avgStageLoad, as formalized in Equation [START_REF] Arrestier | Delays and States in Dataflow Models of Computation[END_REF].

avgStageLoad > c1≤i<c2 rankLoad(i) (2)

Evaluation

The presented heuristic is evaluated on various applications coming from the StreamIt [START_REF] Thies | Streamit: A language for streaming applications[END_REF] benchmark, the examples provided with the SDF3 [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF] tool, and the applications provided with the Preesm [START_REF] Pelcat | PREESM: A Dataflow-Based Rapid Prototyping Framework for Simplifying Multicore DSP Programming[END_REF] tool. These applications represent a panel of basic state of the art signal and image processing algorithms, as well as more complex telecommunications, video coding and computer vision applications. The heuristic results are compared by gain in throughput, relative to the sequential non-pipelined throughput on a single Processing Element (PE). Three different evaluations are performed. In Section 5.1, the theoretical throughput gain is computed based on the schedule length obtained after adding the pipelines selected by the heuristic. A comparison is made with the optimal throughput gain among all admissible cuts, for applications amenable to an exhaustive exploration, while large applications are detailed in Section 5.2. Finally in Section 5.3, the throughput and memory increases are measured on real executions of applications running on hardware.

All experiments have been run with the open-source Preesm tool (https: //preesm.github.io/), on a laptop with an Intel processor i7-7820HQ. For all selected applications, the execution time of the proposed heuristic is between 1 and 18 ms (maximum reached for SIFT). Note that the StreamIt/SDF3 applications are all stateless, except h263decoder (noAC) having self-loops. Self-loops disable auto-concurrency of an actor: multiple firings are serialized.

Main characteristics of the applications are presented in the results tables. In the second column, MAP is the Maximum number of Actors in Parallel in the SDF graph; MAP equals the maximum number of parallel paths in the graph. When known, the total number of admissible graph cuts is specified in the column labeled #Cuts. Note that multiple versions of SIFT and sobel-morpho applications are considered: their graph is identical but they do not have the same amount of firings. Some of their actors are fired a number of times equal to a multiple of a parameter p. Only SIFT and stereo contain directed cycles in their SDF graph. In all results tables, the columns labeled by D x, y contain the throughput gain obtained by the heuristic selecting x pipelines among y balanced pipelines. Columns labeled by C x contain the optimal throughput gain, over all admissible cuts, for x pipelines. Lines of results tables without any value printed in bold means that the throughput gain is similar for all setups; otherwise, the value in bold corresponds to the best gain among the line.

Theoretical throughput gain: regular applications

Theoretical throughput gain obtained with the heuristic is presented in Table 1, for three setups: no pipeline, one pipeline among one, three pipelines among three. Most applications have a repetition vector r equal to 1, except Chain4.2noAC (which contains self-loops), cd2dat, h263decoder, modem, mp3decoder, samplerate and satellite. Chain4.2noAC and Chain4.1 are toy examples made to fit the best cases of the heuristic; they correspond to the graph depicted in Figure 2, with only one path instead of four.

In Table 1, the best throughput gain is obtained by the heuristic with 3 cuts (D 3,3) for 11 of the 17 applications. More importantly, the heuristic finds a close to the optimal throughput with 1 cut for all applications except mp3decoder. The number of admissible cuts generating a throughput gain lower than or equal to D 1,1 is reported as a percentage of the total number of admissible cuts, in column %. In average, D 1,1 reaches a better throughput gain than 91% of the admissible cuts. Note that two applications are not compared with the optimal gain, FMRadio and Vocoder, because they admit too many cuts. These applications, and three others, are discussed in section 5.2.

On DCT and h263decoder, the throughput gain is less than 2.0, even with 3 pipelines: this comes from too few actors in the original graphs (respectively 8 and 4), having unbalanced ETs. This configuration leads the heuristic to find only 2 graph cuts for DCT and h263decoder, even if 3 pipelines were asked by the user. The number of effectively selected cuts is specified as an exponent. The same behavior happens for modem and mp3decoder applications: only 2 cuts are selected whereas 3 pipelines were asked. To avoid this problem, only 2 pipelines among 3 are requested for the Preesm applications, see Table 2 Indeed, in these applications the ETs are greatly unbalanced and the ET of the longest actor represents up to 47% of the sequential ET of sobel-morpho (p1).

For the Preesm applications evaluated in table 2, the heuristic reaches the best throughput in 7 cases out of 9. SIFT application is a difficult case: its SDF graph is widely parallel (up to 30 parallel paths) and contains multiple cycles. Moreover, its parallel paths have unbalanced ET. In this situation, selecting topological cuts is not the best option and 1 optimal cut (C 1) even reaches a better throughput than 2 cuts from the heuristic (D 2,3): for SIFT (p1) and SIFT (p2). However, when more balanced parallelism is expressed, for SIFT (p4), the heuristic configuration D 2,3 once again is better than the other setups.

Theoretical throughput gain: widely parallel applications

This subsection evaluates the applications revealing the main advantage of the presented heuristic: no explosion of the number of cuts to test when the SDF graph is already parallel. Indeed, all evaluated applications in Table 3 Table 2: Throughput gain with delays (D) of SDF benchmark applications, on four PEs. D 0 corresponds to no pipeline. D 1,1 corresponds to one pipeline selected among one. C 1 corresponds to the optimal single stage pipeline. % is the percentage of cuts worst than or equal to the heuristic. D 2,3 corresponds to two pipelines selected among three possibilities.

each cut by performing scheduling and mapping. Moreover, the number of possibilities also explodes with the number of pipelines asked: it is equal to the number of cut combinations without repetition (binomial coefficient):

#Cuts #Stages-1 . Table 3 presents results for the applications already having parallelism expressed in their graph: MAP is between 12 and 17 for all of them. In this experiment, the throughput is evaluated on 64 PEs for the heuristic setup D 3,3 selecting 3 pipelines. Having 64 PEs ensures to observe the effect of the pipelines instead of the inherent task parallelism. Indeed, the maximum number of actors in parallel MAP ( 17) is almost 4 times smaller than the number of PEs. The maximum theoretical throughput gain with unlimited PEs, Max Θ, is given as a reference. All applications in Table 3 are acyclic, so Max Θ is computed by dividing the sequential ET of the application by the ET of its longest actor, as if each buffer had a pipeline delay. Adding 3 pipelines increases the throughput gain from a factor 2 (for FMRadio) to 3 (for ChannelVocoder). Table 3: Throughput gain with delays (D) of SDF benchmark applications, on sixty-four PEs. D 0 corresponds to no pipeline. D 3,3 corresponds to three pipelines selected among three possibilities. Max Θ corresponds to the maximum possible throughput gain, with unlimited PEs.

Practical experimentation

In this subsection, the throughput and memory measurements come from real executions on hardware, on the same laptop used for all experiments, having 4 PEs. Note that the scheduler used in this practical experimentation differs from the one used in the theoretical experimentation. Both schedulers are a variant of list scheduling [START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF]. Memory is allocated after the scheduling process, with buffer merging [START_REF] Desnos | On Memory Reuse Between Inputs and Outputs of Dataflow Actors[END_REF] optimizations activated. The memory needed is computed by Preesm, and compared with the sequential version on 1 PE for reference. Results are provided in Table 4, for an average of 100 executions for SIFT and stereo, and 10000 executions for sobel-morpho and lane-detection. The heuristic especially improves the throughput of SIFT and sobel-morpho with p = 1 and p = 2, that is, when the application is not parallel enough. Yet, for lane-detection which has r = 1, the heuristic only slightly increases the throughput, while increasing the memory by a factor 1.9. The theoretical throughput gain of lanedetection is 2.5, that is two times higher than reality. We explain this gap by the variability of the ET of the display actor, representing 28% of the application sequential execution time. Also, synchronization points added by Preesm may be non-negligible. None of the applications reaches the throughput expected in the theoretical evaluation.

An interesting point is that selecting 1 cut among 2 (D 1,2) gives better results than 1 among 1 for half of the cases. Such heuristic setups may compensate the case of unbalanced ETs or cycles, especially for SIFT (p2). Moreover for SIFT (p2) the D 1,2 setup greatly reduces the memory footprint compared to D 1,1: from a factor 3.0 to 1.1. Finally, the heuristic offers a trade-off between memory footprint and throughput. This trade-off is especially needed for memory bounded application as SIFT requiring 197 MBytes (reference). At worst, for sobel-morpho (p4), adding one pipeline decreases the throughput while greatly increasing the memory (3.3 times). The memory increase is due to the graph cut location: between buffers transmitting numerous data, and thus it causes additional time for memory copies and synchronizations.

Name D 0 D 1,1 D 1,2 D 2,3 Sp. Mem. Sp. Mem. Sp. Mem. Sp. Mem. SIFT (p1) 1.2 1.1 1.6 2.1 1.4 1.3 1.3 1.8 SIFT (p2) 1.8 1.1 1.9 3.0 2.4 1.2 2.2 2.3 SIFT (p4) 2.5 1.2 2.2 1.1 2.2 1.1 2.5 1.8 sobel-morpho (p1) 0.9 1.0 1.3 2

Related work

Pipelining and more generally retiming has been extensively studied in the context of VLSI circuit design [START_REF] Leiserson | Retiming synchronous circuitry[END_REF][START_REF] Parhi | VLSI digital signal processing systems : design and implementation[END_REF]. Pipelining legality was formally defined by Parhi [START_REF] Parhi | VLSI digital signal processing systems : design and implementation[END_REF] for a subset of SDF graphs: Homogeneous Synchronous DataFlow (HSDF) graphs, which always have their repetition vector equal to 1. It was also studied for software pipelining [START_REF] Allan | Software pipelining[END_REF], with retiming methods used in this context [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF]. Our work focus on pipelining SDF graphs, avoiding the costly conversion to HSDF and thus reducing the analysis complexity.

Pipelining of SDF graphs was originally proposed by Lee [START_REF] Lee | Pipeline interleaved programmable dsp's: Synchronous data flow programming[END_REF] as an optimization. Gordon et al. [START_REF] Gordon | Exploiting coarse-grained task, data, and pipeline parallelism in stream programs[END_REF] proposed an heuristic to pipeline a partially unfolded SDF graph, as well as Kudlur et al. [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF]. The heuristic presented by Kudlur et al. requires the Initiation Interval (II) length as an input of their algorithm; on the contrary, our heuristic requires a maximum number of pipelines as an input, and tries to minimize the II accordingly. Also, the heuristic presented by Gordon et al. relies on a first transformation of the original actors, in order to balance the ETs and to adapt the amount of Multiple works [START_REF] Zhu | Multiconstraint static scheduling of synchronous dataflow graphs via retiming and unfolding[END_REF][START_REF] Liveris | Retiming for synchronous data flow graphs[END_REF] addressed the optimal finding of a retiming to reduce the makespan of a graph. Additionally, [START_REF] Zhu | Multiconstraint static scheduling of synchronous dataflow graphs via retiming and unfolding[END_REF] accepts a constraint on the maximum number of processors, at the cost of non-optimality. Both use symbolic execution of a partially unfolded SDF graph to find a retiming. In this paper we focus on the pipelining of an SDF graph in its reduced original form to provide a fast heuristic. We do not perform any execution, symbolic or not.

Scheduling has been largely explored in optimal and heuristic forms [START_REF] Kwok | Static scheduling algorithms for allocating directed task graphs to multiprocessors[END_REF][START_REF] Malik | Orchestrating Stream Graphs Using Model Checking[END_REF]. A few works look at combining pipelining with scheduling, restricted to HSDF graphs [START_REF] Yang | Pipelined data parallel task mapping/scheduling technique for mpsoc[END_REF] or acyclic SDF graphs [START_REF] Chen | Buffer minimization in pipelined sdf scheduling on multicore platforms[END_REF]. Our work separates pipelining from scheduling. Scheduling is computed afterwards on the pipelined graph, taking advantage of original data and task parallelism, as well as temporal parallelism.

Conclusion

A fast heuristic to automatically pipeline SDF applications at coarse grain has been presented and actually improves the throughput of the evaluated applications. The heuristic is able to quickly pipeline applications containing up to billions of admissible cuts. Our algorithm limits its exploration to a few cuts to reduce analysis time, and experiments show this method is close to the optimal solution. The last experiment have shown a gap between the theoretical throughput gain and the practical gain, always lower than expected. This gap is observed for both our heuristic and the theoretical optimal solution.

The presented heuristic is especially useful when considering a large amount of PEs. However, our method can still be improved for complex applications, especially if containing cycles, for examples by adding smaller delays to break the dependencies between only a certain amount of firings instead of all.

Finally, this heuristic is only one optimization method among various others, as the most related to this work: retiming. Combination of our pipelining heuristic and classic retiming techniques is kept for future work.

Addendum

This addendum is not part of the original accepted paper: it has been added by A. Honorat after publication and has not been reviewed. It focuses on:

linear equation to find all admissible graph cuts; details on ALAP ordering; example for selection of balanced cuts.

Equation to find all admissible graph cuts

Thanks to Michael Masin and his team, we were able to formulate the admissible feed-forward cut constraint as the following recursive Equation (3). The equality must be respected for every actor α ∈ V , the set of actors of the SDF graph. It introduces the notion of actor delay, denoted . An actor delay corresponds to a shift of data on all its input. The unit of the actor delay function is the number of pipeline stages: if (α) = 2, there are two pipeline stages until actor α. In the equation, E is the set of edges of the SDF graph.

∀e ∈ {b ∈ E| dst(b) = α}, (α) = (src(e)) + d 0 (e) cons(e) × r [α] (3)
The recursion stops on actors having no incoming buffer, where the actor delay is set to 1 by default: such actors are executed during the first pipeline stage. It is assumed that the user sets enough delays on at least one buffer of any cycle; these buffers are ignored for the computation of , otherwise the formula Equation (3) would imply an indefinite recursion.

As the placement validity is defined recursively from the actors having no outgoing buffers, delays may be distributed over the whole paths going to an actor, and not only on its direct incoming buffers. Figure 3 illustrates this possibility. Removing one of its two delays makes the cut not admissible anymore.

Details on ALAP ordering

It is important to note that we actually use a modified version of ALAP topological ordering, otherwise Equation (3) might not always be respected. The modified ALAP version enforces that all actors having no incoming buffers (or only incoming buffers breaking cycles) have the lowest topological rank. A counter-example and a valid example are given in Figure 4.

Example for selection of balanced cuts

An example of preselection and final selection of cuts is depicted in Figure 5. 4 cuts are preselected by the heuristic with configuration D 2, 3 on the given input graph having 9 actors in line. Each actor is executed only once and its ET is equal to 10. The two cuts with a dashed line correspond to the cuts found during the first enumeration of ASAP cuts. The two cuts with a dotted line correspond to the cuts found during the second enumeration of ALAP cuts. Note that there are less than 3 cuts preselected by each traversal because an extra condition stops the traversal when the sum of remaining rankLoad is higher than avgStageLoad = 22. The current value of the sum of rankLoad and the closest multiple of avgStageLoad when a cut is preselected is recalled below the cut in Figure 5. The ranks of the preselected cuts are: 4, 6, 7, 5, in order of appearance. Except between cuts 4 and 7, none of the other pair of ranks respects Equation [START_REF] Arrestier | Delays and States in Dataflow Models of Computation[END_REF]. The removal procedure first sorts the cuts by the size of their pipeline delays, and then starts in the reverse order of appearance to remove the largest cuts in delay size. In this case, all cuts imply the same delay size, and the first two cuts to compare are the cuts 5 and 7. As cuts 5 and 7 are too close to each other and imply the same delay size, the highest rank is removed by default: 7. Then only three preselected cuts remain: cuts 4, 6, 7 and the removal procedure stops since three is the number of preselected cuts asked by the configuration D 2, 3. Finally, the heuristic selects the first two of the remaining cuts: 4 and 6.

  d 0 (b) = prod(b) × r[src(b)] = cons(b) × r[dst(b)]. Thus, dependencies between all firings of producer actor src(b) and receiver actor dst(b) are broken.

Fig. 2 :

 2 Fig. 2: Split-join graph with four parallel branches. 2 admissible cuts are represented with a dashed line, among 81 possible.

Fig. 3 :

 3 Fig. 3: Graph with valid delay placement distributed on the paths. There are two pipeline stages: (∆) = (E) = (B) = 1 and (A) = (Γ ) = 2.

  Modified ALAP topological ordering to have valid (i.e. feed-forward) graph cuts.

Fig. 4 :

 4 Fig. 4: Graph cut examples for regular and modified ALAP topological ordering.

Fig. 5 :

 5 Fig. 5: Preselected and final cuts computed by the delay placement heuristic with configuration D 2, 3 on a sample chain graph. Dotted cuts correspond to the preselected cuts while the dashed cuts correspond to the 2 final cuts. Each actor is fired once and has an ET equal to 10.

Table 1 :

 1 admit between 10 5 and 10 10 cuts, which makes it impossible to evaluate the throughput of Characteristics and throughput gain with delays (D) of SDF benchmark applications, on four PEs. D 0 corresponds to no pipeline. D 1,1 corresponds to one pipeline selected among one. C 1 corresponds to the optimal single stage pipeline. % is the percentage of cuts worst than or equal to the heuristic. D 3,3 corresponds to three pipelines selected among three.

	Name	MAP #Actors #Cuts D 0 D 1,1 C 1 %	D 3,3
	Chain4.1	1	4	3	1.0	2.0	2.0 100	3.9
	Chain4.2noAC	1	4	3	1.4	2.3	2.3 100	3.4
	BitonicSort	4	40	141	1.6	2.9	2.9 100	3.6
	cd2dat	1	6	5	4.0	4.0	4.0 80	4.0
	DCT	1	8	7	1.0	1.8	1.8 100	1.8 2
	DES	3	53	128	1.2	2.2	2.2 96	2.4
	FFT	1	17	16	1.0	2.0	2.0 100	3.7
	FMRadio	12	43	-	3.1	3.3	-	-	3.3
	h263decoder (noAC)	1	4	3	1.8	1.8	1.9 100 2.0 2
	modem	1	6	5	2.0	3.3	3.3 100	3.3 2
	mp3decoder	2	14	33	3.7	3.7	3.8 66	3.7 2
	MPEG2noparser	3	23	140	1.1	2.2	2.2 100	2.7
	samplerate 4.0
	TDE	1	29	28	1.0	1.9	1.9 100	3.4
	Vocoder	17	114	-	1.2	2.1	-	-	2.6
	Name	MAP #Actors #Cuts D 0 D 1,1 C 1 %	D 2,3
	SIFT (p1)	30	54	868	1.2	1.6	2.2 92	1.6
	SIFT (p2)	30	54	868	2.3	2.8	3.7 91	3.0
	SIFT (p4)	30	54	868	3.5	3.5	3.6 80	3.7
	sobel-morpho (p1)	1	6	5	1.0	2.0	2.0 100	2.0
	sobel-morpho (p2) *	1	6	5	1.7	2.4	2.4 100	2.6
	sobel-morpho (p3) *	1	6	5	2.3	3.5	3.5 100	3.4
	sobel-morpho (p4)	1	6	5	2.3	2.8	3.3 40	3.3
	stereo	3	28	3631	3.3	3.9	3.9 99	3.9
	lane-detection *	3	11	24	1.0	1.7	1.7 100	2.5

Table 4 :

 4 Throughput and memory increases with delays (D), on four PEs, for different parallelism parameters (p). Specific mapping constraints are enforced for applications marked with *: read and display actors are alone on their core if there is a pipeline.

This project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement №732105 (project CERBERO) and from the Région Bretagne (France) under grant ARED 2017 ADAMS. We would like to thank Michael Masin for his help to generate all admissible graph cuts.


Marie-Hélène Moncel
email: marie-helene.moncel@mnhn.fr

Carmen Santagata

Alison Pereira

Sébastien Nomade

Pierre Voinchet

Jean-Jacques Bahain

Camille Daujeard

Antonio Curci

Cristina Lemorini

Bruce Hardy

Giacomo Eramo

Claudio Berto

Jean-Paul Raynal

Marta Arzarello

Beniamino Mecozzi

Alessio Iannucci

Raffaele Sardella

Ignazio Allegretta

Emanuela Delluniversit

Roberto Terzano

Pauline Dugas

Gwenolé Jouanic

Alain Queffelec

Andrea D'andrea

Rosario Valentini

Eleonora Minucci

Laura Carpentiero

Marcello Piperno

The origin of early Acheulean expansion in Europe 700 ka ago: new findings at Notarchirico (Italy)

R e v i s e d P r o o f

to the adaptability and migration of early human populations. These biological and environmental conditions need to be considered further in the light of much older than previously recognized cultural innovations in the European human evolution scheme.

The earliest Western European settlement, related to Homo sp., is now thought to be older than 1.2 Ma 1 . Homo antecessor, the earliest remains of Homo sp. in Western Europe, discovered in Spain at Atapuerca (1.2-0.8 Ma), could be a side branch of the Homo sp. clade located at the westernmost area of the Eurasian continent [START_REF] Bermúdez-De-Castro | Homo antecessor: the state of the art eighteen years later[END_REF] , as recently confirmed by paleoproteomics [START_REF] Welker | The dental proteome of Homo antecessor[END_REF] . This hominin would have no link with the subsequent hominin species. Homo heidelbergensis (defined from the Mauer mandible) [START_REF] Wagner | Radiometric dating of the type-site for Homo heidelbergensis at Mauer, Germany[END_REF] is considered to be at the origin of significant behavioral changes, such as the onset of biface production (technological Mode 2, Acheulean culture) [START_REF] Moncel | Early evidence of Acheulean settlement in north-western Europe -la Noira site, a 700 000 year-old occupation in the Center of France[END_REF][START_REF] Buck | Homo heidelbergensis[END_REF][START_REF] Gallotti | The lower/early middle pleistocene small debitage productions in Western Europe: new data from Isernia La Pineta t3c (Upper Volturno Basin, Italy)[END_REF] . The emergence of the Acheulean in Western Europe is very late compared to initial occurrences in Africa (1.75 Ma) [START_REF] Texier | Du seuil de l'hominisation aux premières cultures: potentialité et apports de la taille expérimentale[END_REF][START_REF] Beyene | The characteristics and chronology of the earliest Acheulean at Konso, Ethipia[END_REF][START_REF] De La Torre | Special issue on the early Acheulean of EF-HR (Olduvai Gorge, Tanzania)[END_REF] and the Levant (1.4-1.2 Ma). Rare manifestations indicate the emergence of such technologies earlier than 700 ka ago in the Mediterranean Basin (e.g., Barranc de la Boella, Spain) [START_REF] Vallverdù | Age and date for early arrival of the Acheulean in Europe (Barranc de la Boella, la Canonja, Spain)[END_REF] . Over the past decade, fieldwork has shown that elaborate biface production appeared suddenly around 700 ka ago in the Northwest of Europe [START_REF] Moncel | Early evidence of Acheulean settlement in north-western Europe -la Noira site, a 700 000 year-old occupation in the Center of France[END_REF][START_REF] Voinchet | New chronological data (ESR and ESR/U-series) for the earliest Acheulian sites of north-western Europe[END_REF][START_REF] Antoine | The earliest record of Acheulean human occupation in North-West Europe[END_REF] . Despite this new information, the timing and characteristics of the earliest evidence of Acheulean groups in Western Europe are still poorly known.

Various scenarios have been proposed to explain the onset of Acheulean diffusion in Western Europe without accounting for this late emergence: (1) a local origin stemming from previous core-and-flake traditions, or (2) the introduction of new populations or the diffusion of new ideas [START_REF] Moncel | Early evidence of Acheulean settlement in north-western Europe -la Noira site, a 700 000 year-old occupation in the Center of France[END_REF][START_REF] Martínez | On the origin of the European Acheulian[END_REF] . These new populations would have adapted to new environments and biomasses during the Mid-Pleistocene revolution.

The Basilicata region in Italy is characterized by the preservation of long archaeological sequences in volcanosedimentary complexes linked to the eruptive activity of the Vulture stratovolcano [START_REF]Notarchirico (Un sito del Pleistocene medio iniziale nel bacino di Venosa[END_REF][START_REF] Lefèvre | Tephro-stratigraphy and the age of ancient Southern Italian Acheulean settlements: The sites of Loreto and Notarchirico (Venosa, Basilicata, Italy)[END_REF] . Among these sites, the Notarchirico site (Venosa Basin), discovered in 1979, has yielded a 7 m-thick sequence of fluvial sediments including eleven archaeological levels, five of which contain bifaces (Fig. 1). A hominin femur fragment was found in the upper part of the sequence (level α) [START_REF] Mallegni | Découverte d'un femur acheuléeen à Notarchirico (Venosa, Basilicate)[END_REF] . [START_REF] Schreve | Editorial: the early Acheulean occupation of western Europe: chronology, environment and subsistence behaviour[END_REF] Ar/ [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF] Ar ages and ESR dates have revised the chronology of the sedimentary sequence excavated by Piperno and constrained the archaeological levels alpha to F between ca. 610 and 675 ka [START_REF] Pereira | The earliest securely dated hominin fossil in Italy and evidence of Acheulian occupation during glacial MIS 16 at Notarchirico (Venosa, Basilicata, Italy)[END_REF] , i.e., coeval with a glacial stage. The faunal assemblages from the upper levels A and α, described by Cassoli et al. can be attributed to Isernia faunal unit [START_REF] Cassoli | I vertebrati dei livelli superiori (A ed ALFA) della serie stratigrafica di Notarchirico, In Notarchirico; Un sito del Pleistocene medio-iniziale nel bacino di Venosa (Basilicata), Vol. I edizione Osanna (a cura di M. Piperno)[END_REF][START_REF] Sardella | The early Middle Pleistocene large mammal faunas of Italy: an overview[END_REF] . The archaeological material is found on pebbles andcobbles lags that represent shallow paleochannels. We present here new archaeological, chronological and environmental results for Notarchirico, which greatly enhance our understanding of the cognition of these hominins in Southern Italy earlier than 675 ka. These results fuel discussions concerning the timing of the earliest European Acheulean settlements in Western Europe, a behavioral shift by hominins in the region, and the possible routes used by hominins to access Southern Italy.

Results

A 30-m-long trench was opened on the side of Notarchirico hill, at the base of the previously studied sequence. Excavations were conducted over a surface of 8 to 26 m 2 depending on the stratigraphical unit investigated (Tables 1 andS1). Since 2016, excavation campaigns focusing on the base of the sequence have identified four units, including four archeosurfaces (I and J in addition to G and H).

Lithostratigraphy and dynamics.

The studied deposits lie on top of the Piano Region sedimentary formation of the Venosa Basin 21 (see Supplementary Tables S2, S3 and Figs. S1-S6). The sedimentary succession is described in detail in Supplementary Table S1 and Fig. 2 from the base upwards. The basal units (units 8 to 6) are characterized by low energy fluvial sedimentation and regular inputs of volcanic material. In the upper units (5 to 3), sedimentation progressively indicates somewhat higher energy currents and mainly volcano-derived remains. The main archaeological horizons are layers G (bottom of sub-unit 4.2), H (bottom of sub-unit 5.3), I1 (sub-unit 6.1), I2 (sub-unit 6.2) and J (sub-unit 7.4). The different facies correspond mainly to fills of meandering paleo-channels, crossed in places by the action of low energy currents. The fine components of these deposits derive from the alteration of volcanic fallout. The layers incorporating cobbles and gravels correspond to slope destabilization processes, which intervened after the arrival of masses of tephra and the release of lateral contributions from older conglomeratic deposits.

Geochronology.

Four sedimentary layers, some of which contain archaeological horizons, were dated by 40 Ar/ [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF] Ar on single grains and ESR on bleached quartz. The stratigraphic positions of the geochronological sam- ples are displayed in Fig. 2. Horizons H1b and H1c from sedimentary sub-unit 5.2 and 5.3 were dated by the ESR palaeodosimetric method, while the archaeological horizons I1 (sub-unit 6.1) and J (sub-unit 7.3) were analyzed using the [START_REF] Schreve | Editorial: the early Acheulean occupation of western Europe: chronology, environment and subsistence behaviour[END_REF] Ar/ [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF] Ar technique (Supplementary Table S4). [START_REF] Schreve | Editorial: the early Acheulean occupation of western Europe: chronology, environment and subsistence behaviour[END_REF] Ar/ [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF] Ar and ESR ages are reported at 2σ analytical uncertainties hereafter. Fifteen sanidine crystals were hence individually dated by [START_REF] Schreve | Editorial: the early Acheulean occupation of western Europe: chronology, environment and subsistence behaviour[END_REF] Ar/ [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF] Ar for sub-unit 6.1 and thirteen for sub-unit 7.3. In both cases, the probability diagrams are multimodal (Supplementary Fig. S7), characterized by populations of several crystals. At least six populations are evidenced for the youngest sub-unit 6. The ESR study was conducted with the multi-center approach advocated by Toyoda et al. [START_REF] Toyoda | Bleaching of ESR signal by the sunlight: a laboratory experiment for establishing the ESR dating of sediments[END_REF] . Aluminum (Al) and Titanium (Ti-Li and Ti-H) ESR centers of quartz were measured in the present study. The ages derived from Ti-Li and Al centers are consistent with each other (Supplementary Table S4), whereas Ti-H ages are significantly younger. Mean ESR Al/Ti-Li ages of 743 ± 67 ka (2σ, MSWD = 0.024 and P = 0.88) and 736 ± 70 ka (2σ, MSWD = 0.013 and P = 0.91) were obtained for Notarchirico H1b (sub-unit 5.2) and Notarchirico H1c (sub-unit 5.3) samples respectively. We also note that the results of the H1 levels are much older than the [START_REF] Schreve | Editorial: the early Acheulean occupation of western Europe: chronology, environment and subsistence behaviour[END_REF] Ar/ [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF] Ar ages of the over-and under-lying levels. However, these ages are still consistent, considering the associated error range.

Palaeontology and taphonomy. The lithic and bone material is dispersed on and included into the 10-30 cm-thick beds of pebbles-cobbles, remains of lakeshores or water channels (Fig. 3). There are no specific orientation patterns of the pieces and the pebbles. Fossil remains (NRT = 4,081 and NISPa = 289) are fragmented but can be attributed to several mammalian taxa (Supplementary Table S5). The straight-tusked elephant, Palaeoloxodon antiquus, was found in all stratigraphic levels, and is prevalent in levels F, G and I2. Cervids dominate the spectrum in levels H and I1, while large bovids are frequent in levels F and I2. Two species are newly reported: Hippopotamus antiquus in levels G and I1, and Macaca sylvanus spp. in level G. This occurrence of Macaca sylvanus spp. is documented by the proximal half of a right ulna (Supplementary Fig. S9). The fragmentary nature of the fossils complicates the detailed taxonomic attribution of cervids and bovids. Most of the remains consist of limb bone shafts, possibly related to slender bovids or megacerine deer. The occurrence of bison and/or aurochs is documented whereas Bos primigenius remains have not been confirmed [START_REF] Sardella | The early Middle Pleistocene large mammal faunas of Italy: an overview[END_REF][START_REF] Sala | Late Pliocene and Pleistocene small mammal chronology in the Italian peninsula[END_REF] . Praemegaceros sp. is relatively abundant among cervids, alongside middle-sized cervids including Dama cf. clactoniana and Cervus elaphus. . No carnivores have been found. This faunal list is almost similar to that of the youngest levels α and A of Notarchirico [START_REF]Notarchirico (Un sito del Pleistocene medio iniziale nel bacino di Venosa[END_REF] .

Scarce small mammal remains were recovered in layer I and identified as Arvicola mosbachensis, Microtus (Terricola) cf. M. (T.) arvalidens, and Microtus cf. M. nivaloides. Arvicola mosbachensis is the most represented species and should be one of its earliest occurrences. The small micromammal assemblage is closely related to the previously published material, attributed to the beginning of the Early Toringian (Arvicola-Microtus zone, Arvicola mosbachensis subzone 3) (Supplementary Fig. S9).

Cervids are represented by all skeletal parts, but isolated teeth, ribs and small articular bones dominate. Cervids are mostly juveniles and subadults (Supplementary Tables S6-S9). Large-sized bovid remains consist mainly of teeth and metapodials. Prime-aged and old adults predominate. Elephants are mostly represented by tusk fragments, teeth and indeterminate bone fragments and the hippopotamus by four fragments of teeth, one of which belongs to a young individual from layer I1. Concerning the Voorhies groups, the relative scarcity of long bones and cranial remains and the abundance of short elements for all species and levels is consistent with a shore deposit or a low-energy deltaic and lacustrine environment, with some possible more violent hydraulic transport episodes (Supplementary Tables S10 andS11). Post-depositional dry bone fractures are the most recurrent type of fragmentation, but some green bone fractures associated with notches have been recorded. The anthropic or natural origin of the latter is difficult to determine, and they may possibly have been caused by natural violent impacts (trampling or strong water flow). Bone surfaces are badly preserved and practically no elements present carnivore marks (layer I1). No cut marks could be identified (Supplementary Tables S12-S14, Figs. S10-S12). The bone assemblages from the outside trench represent a mixture of multiple deposits of animal carcasses, the majority of which may have died naturally in the vicinity of this water channel/lacustrine context, and then secondarily transported, sorted and modified. As of yet, there is no evidence to support any clear human or carnivore contribution to the accumulation of the bone assemblage, but we cannot rule out the possibility that some animals may have been accumulated and/or consumed in situ by both types of predators and scavengers.

Lithic assemblages.

Artefacts are mainly on nodules of chert and various types of silicified limestone pebbles and cobbles, which are abundantly available along the paleochannels (Supplementary Fig. S13). Most of the nodules are cubic or slightly rounded, 10 mm to 35 mm long, with some larger exceptions (70-90 mm). Four main lithotypes were identified (Supplementary Figs. S14-S16): silicified litharenites (flysch chert), nodular chert, vitreous chert and radiolarite. The partial presence of a neocortex demonstrates the secondary origin of the raw materials, associated with the Flysch Rosso Fm primary source (Synthem of Palazzo San Gervasio). Silicified litharenites constitute 80% of the samples from layer F, and the rest consist of nodular chert. This distribution is different in layer G, where 50% of the samples are silicified litharenites, 25% nodular cherts and 25% radiolarites. In layers I1 and I2, silicified litharenites and nodular cherts are represented in similar proportions and some radiolarites and vitreous cherts were also used.

More than 900 lithic objects were recorded, always associated with faunal material (Supplementary Tables S15-S20, Figs. 3,4,5). The richest layers are F, G, I2 and I1 (Tables 1,2). Layer H is poor, only composed of small flakes and flake-tools in chert. The new excavations have enriched the lithic series of layer F, previously comprised of relatively few artifacts, nine bifaces, and LCTs. Layer J has only yielded five flakes (including four retouched) and one chert core fragment. The material can be divided into two groups: flakes and cores on small chert nodules and a heavy-duty component mainly on limestone cobbles. Core technology consists of unifacial, unifacial discoid-type, multifacial and semi-rotating cores for layers F, G and I1. Less diversity is recorded in layer I2, which is only characterized by unifacial cores. Debitage utilizes the natural shape of nodules (except two flakes in layer G), with limited preparation of the striking platform, knapped by freehand percussion. The cores (typically 20-50 mm long) in chert produced low quantities of small 10-20 mm-long backed flakes (Supplementary Tables S15-S19 and Figs. S17-S25, Fig. 4). Cores sizes are similar between layers, but include some larger cores (Supplementary Figs. S26,S27). Flake platforms are cortical or flat, sometimes dihedral, punctiform or facetted (one in layer I2 to four in layer G), with an angle varying from 47 to 89°. Flake fragmentation is high. Flakes in chert range between 10 and 30 mm long (Supplementary Figs. S17, S21, S22, S23, Table S20). In layers Figure 5. Layer F. Bifaces and bifacial tools on limestone pebbles (1-6). Bifacial tool on a large chert nodule. Four bifaces on limestone and large chert nodules were found among the ten Large Cutting Tools (LCTs). The shaping of the bifaces covers a large part of the periphery and surface of the tool by one or several series of removals with retouches sometimes regularizing the cutting edges. The cross-sections are symmetrical or plano-convex. The base is frequently cortical. The support is a cobble or a large flake in limestone (n°1, 2, 5). The only exception is a tool on a large chert nodule available in situ (n°7). Some evidence of recycling is observed on the cutting edges (second series of small removals or retouches). Crushing marks on edges, due perhaps to percussion, are sometimes visible. Detailed descriptions are given in the Supplementary data. (Photos M-H. Moncel, C. Santagata).

F and G, there are some larger flakes (40-120 mm) coming from an in situ debitage (outside the excavated area) or brought to the site. Flakes, flake fragments and small nodules are retouched (between 5 and 20% of the corpus) on one or several edges by marginal, abrupt or denticulate retouch (Table 3). Some convergent tools exist (Supplementary Fig. S18). Flake-tools of layer G show the highest intensity of retouch on a large part of the periphery of flakes or nodules. The angle of the cutting edge is higher (75°-90°) for retouched nodules than for retouched flakes (25°-80°). The retouch on nodules is often abrupt and denticulate. We note that retouch substantially modifies initial blank shape in many cases. Retouched nodules in chert measure between 20 and 40 mm. In layers I2 and I1, most of the flakes are very small (10-20 mm) and retouched nodules are longer and wider (20-40 mm). Nodules in layer I2 are smaller than in layer I1. Nodules are generally thin (around 10 mm thick), but thicker than the flakes (around 2-5 mm for the most). Flakes and quadrangular nodules in chert could be considered as complementary tool kit in size.

Evidence of debitage on limestone pebbles is rare. The flakes in limestone (50-100 mm) are cortical and could come from the shaping process. The heavy-duty component is characterized by diversified and poorlystandardized artefacts. It includes unifacial round and thin pebble tools with limited shaping, some of which are pointed. Some tools are trifacial or quadrangular and extend over a large portion of the pebble. For layer I1, the rare bifacial pebble tools are small, and seldom pointed, while in layer I2, pebble tools are mostly unifacial.

The lack of bifaces in some layers of the upper part of the sequence and in layers I1 and I2 at Notarchirico, as the highest number of bifaces in layer F, could be due to the activities or the size of the excavation. It cannot be ruled out that future excavations will provide bifaces in layers I1 and I2 at Notarchirico, further postponing the age of this technology already elaborated. Bifaces demonstrating overall volume management were observed in layer F, confirming discoveries made by M. Piperno's excavations (Figs. 5,6, Supplementary Table S21, Fig. 4, 5) [START_REF] Moncel | Biface production at Notarchirico (Southern Italy) before 600 ka Contribution to the earliest evidence of the European Acheuleans[END_REF] . In layer F, four bifaces on limestone and large chert nodules were found among the ten Large Cutting Tools (LCTs). The shaping of the bifaces covers a large part of the periphery and surface of the tool by one or several series of removals, with retouch sometimes regularizing the cutting edges. The cross-sections are symmetrical or plano-convex with the base frequently cortical. The support is a cobble or a large flake in limestone (Fig. 5, n°1, 2, 5). The only exception is a tool on a large chert nodule available in situ (Fig. 5,n°7). Some evidence of recycling is observed on the cutting edges (second series of small removals or retouches). Crushing marks on edges, due perhaps to percussion, are sometimes visible.

Two limestone bifaces were also discovered in layer G, including one recycled specimen. As with the bifaces of layer F, they demonstrate bifacial volume management and equilibrium of the two faces of the tool (Fig. 6). Figure 6, n°1 shows a triface/biface on a pebble. This is a recycled tool with centripetal smooth removals on one flat face (lower face) The second phase of shaping used the piece as a preform to shape the opposite face by abrupt The second phase of shaping used the piece as a preform to shape the opposite face by abrupt and more or less invasive removals on both lateral edges and the proximal extremity. There are crushing marks on the round tip, which is slightly shaped.

The second biface is also on a pebble (n° 3). Shaping is alternate managing the whole volume by invasive and small removals to create a symmetrical tool. The shape is symmetrical. There is also one bifacial tool on a large chert nodule (n° 2). Using the natural shape of the nodule, the shaping is made by bifacial invasive convergent removals on one side and the proximal part form a tool that is asymmetrical in shape and cross-section, preserving a back on the opposite side. A back is preserved on the opposite side. There is with a notch related to a bec at the tool extremity. Detailed descriptions are given in the Supplementary data. (Photos M-H. Moncel, C. Santagata).

and invasive removals on both lateral edges and the proximal extremity. There are crushing marks on the round tip, which is slightly shaped. The second biface is also on a pebble (Fig. 6, n°3). Shaping is alternate, managing the whole volume by invasive and small removals, to create a symmetrical tool. . There is also one bifacial tool on a large chert nodule (Fig. 6,n°2). Using the natural shape of the nodule, bifacial invasive convergent removals on one side and the proximal part form a tool that is asymmetrical in shape and cross-section, preserving a back on the opposite side, with a notch related to a bec at the tool extremity. Additional detailed descriptions of the LCTs and bifaces of Figs. 5 and6 are given in the Supplementary data. Layers I1 and I2 did not yield bifaces, despite the fact that they were excavated over large surfaces (26 m 2 ). The chipped stone tools are affected by post-depositional processes (Supplementary Figs. S28,S29). However, use-related edge removals and edges are well preserved and clearly visible. A total of 42 active areas were detected on the lithic industry analyzed so far, including 32 from layer F (Fig. 3). Various soft to hard consistency materials were worked, but the best represented are soft and soft-medium materials, worked by cutting and scraping. In addition to these two actions, artefacts were also used for mixed actions, with a combination of transversal and longitudinal motions on the same tool. One example of engraving and one example of thrusting percussion were also recorded. The rare preserved micro-wear (only three cases) attests to processing fleshy tissue with mixed actions, scraping wood and cutting soft abrasive matter. Preliminary results of microscopic residue analysis support these conclusions with plant tissue and possible feather barbules co-occurring with wear patterns. Further analysis is underway to confirm these results (Supplementary Figs. S30 to S33). These data are consistent with the overall usewear data, which suggest that the chipped stone tools were used for different purposes, probably not only related to food processing. In fact, the scraping actions, mixed actions and engraving related to soft to hard materials may also represent activities to produce objects. Marked variations in the thickness of the active edges of these chipped stone tools (30°-80°) suggest that they were used for different activities requiring different active edge strengths.

Discussion

New fieldwork at Notarchirico has yielded four archaeological layers in unit 3, dated to 668 ± 6 ka [START_REF] Pereira | The earliest securely dated hominin fossil in Italy and evidence of Acheulian occupation during glacial MIS 16 at Notarchirico (Venosa, Basilicata, Italy)[END_REF][START_REF] Moncel | Biface production at Notarchirico (Southern Italy) before 600 ka Contribution to the earliest evidence of the European Acheuleans[END_REF] . The 40 Ar/ [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF] Ar ages calculated for sub-unit 6.1 and 7.3 are indistinguishable and point to the rapid deposition of the mainly fluvial sediment complex during the MIS 17 to the MIS 16 transition. The youngest eruptions identified in these levels correspond chronologically to the Toppo San Paolo sub-synthem of the Vulture stratovolcano (Barile synthem) dated in the literature to 679.6 ± 19 ka (Piano Regio Formation in the Venosa Basin), or to the Spinoritola sub-synthem (Foggianello synthem), dated to 693.8 ± 19 ka (Fonte del Comune Formation in the Venosa Basin) (ages recalculated from Villa and Buettner, 2009 with FCs standard at 28.294 Ma [START_REF] Renne | Joint determination of 40K decay constants and 40Ar*/40K for the Fish Canyon sanidine standard, and improved accuracy for 40Ar/39Ar geochronology. Response to the comment[END_REF] . The chronological data are in keeping with lithostratigraphic and sedimentological analyses suggesting that unit 7 in particular is very similar to other localities in the Venosa Basin belonging to the Piano Regio sedimentary formation [START_REF] Lefèvre | Tephro-stratigraphy and the age of ancient Southern Italian Acheulean settlements: The sites of Loreto and Notarchirico (Venosa, Basilicata, Italy)[END_REF] .

Hominins took advantage of these paleo-channels to avail of local small nodules of chert and limestone cobbles, as well as large mammal carcasses. The latter appear to have died of natural causes as no clear cut marks or anthropic bone breakages were identified. Usewear on small flakes and nodules indicate (mixed actions (scraping wood and cutting soft material). Based on data from the usewear analysis, the chipped stone tools do not seem to have been "cutting oriented", in contrast to other later small-sized Acheulean lithic industries [START_REF] Venditti | Animal residues found on tiny lower paleolithic tools reveal their use in butchery[END_REF] . Bifaces and bifacial tools present macro-traces on the edges resulting from working undetermined hard materials. Evidence of varied activities attests to diversified behavior and spatial exploitation. Some evidence of recycling of lithic materials is observed on one biface and some cores, suggesting recurrent hominin presence on the site. The gathering of small chert nodules and the production of very small flakes indicate adaptation to local raw materials or cultural traditions aiming to voluntary produce small end-products [START_REF] Venditti | Animal residues found on tiny lower paleolithic tools reveal their use in butchery[END_REF] .

Bifaces were also found lower in layer G, dated between 675 and 695 ka. Notarchirico thus yields the earliest bifaces in Italy and pushes back the age of the emergence of the Acheulean in Western Europe. Our study shows that hominins managed bifacial volumes, at least at the transition between MIS 17 and 16 in Italy, and that repeated human occupations occurred in both glacial and interglacial climatic conditions. The technological shift evidenced between layers G and I is not reflected by core technology, which is similar to core-and-flake assemblages (Mode 1) and some early Acheulean records (TD6 Atapuerca in Spain, prior to 780 ka, or Moulin-Quignon at 650 ka in the North of France) [START_REF] Antoine | The earliest record of Acheulean human occupation in North-West Europe[END_REF][START_REF] Ollé | The early and middle pleistocene technological record from Sierra de Atapuerca (Burgos, Spain)[END_REF][START_REF] Mosquera | From Atapuerca to Europe: tracing the earliest peopling of Europe[END_REF][START_REF] Moncel | The Acheulean workshop of la Noira (France, 700 ka) in the European technological context[END_REF][START_REF] Iovita | High handaxe symmetry at the beginning of the European Acheulian: the data from la Noira (France) in context[END_REF] , unlike other penecontemporaneous and younger sites, which show evidence of knapping innovation (e.g., la Noira 700 ka) [START_REF] Moncel | Early evidence of Acheulean settlement in north-western Europe -la Noira site, a 700 000 year-old occupation in the Center of France[END_REF][START_REF] Pereira | Apport de la datation 40Ar/39Ar à la compréhension de l'évolution culturelle des pré-néandertaliens en Italie centrale et méridionale entre 750 et 250 ka[END_REF][START_REF] Moncel | La Noira site (Centre, France) and the technological behaviours and skills of the earliest Acheulean in Western Europe between 700 and 600 kyrs[END_REF][START_REF] Hardy | Middle Pleistocene hominin behavior at the 700ka Acheulean site of la Noira (France)[END_REF] . The core technology on the whole sequence at Notarchirico, from level alpha to level F (excavations of M. Piperno) [START_REF] Antoine | The earliest record of Acheulean human occupation in North-West Europe[END_REF] , does not indicate differences over time and is similar to the technology applied in layers G and I at the bottom of the sequence. Small nodules of chert are used as cores which show mainly unifacial flaking and no preparation of the striking platform. Rare quartzite and quartz flakes and punctual knapping on limestone cobbles are present and may have been used for producing large flakes for shaping bifaces. Layers A, A1, B, D, F and G in the upper part of the sequence of the site yielded LCTs including some bifaces [START_REF] Moncel | Biface production at Notarchirico (Southern Italy) before 600 ka Contribution to the earliest evidence of the European Acheuleans[END_REF] . Layer F is the richest layer in quantity of bifaces and the new excavations confirm this richness. The bifaces found in the lowest level (layer G) are similar to those found in the layers of the upper part of the sequence. The management and reduction of the bifaces indicates a shaping process far from the simple and opportunistic process of the pebble-tools.

This ability to manage bifacial and bilateral symmetry, as well as the diversity of the morphological results, is also observed in penecontemporaneous Acheulean sites in North-western Europe between 700 and 600 ka at la Noira and Moulin-Quignon 5,35-41 (Fig. 1). These sites yield bifaces and a mixture of diversified crudely-made bifacial tools, suggesting flexibility in the knapping processes of Middle Pleistocene populations. The combined use of small natural fragments of chert at Notarchirico suggests similar opportunism and adaptability to raw material constraints. Unlike Notrachirico, however, both soft and hard hammers were used for shaping siliceous rocks at la Noira and Moulin Quignon.

Vol:.( 1234567890)

Scientific RepoRtS | _#####################_ | https://doi.org/10.1038/s41598-020-68617-8
www.nature.com/scientificreports/

The new finds at Notarchirico contribute to the debate on the two current hypothesis for the origins of the Acheulean in Europe: (1) local evolution and innovation/invention 42 or (2) arrivals of new populations/traditions (Acheulean) on the western side of Europe and limited to the area west of the Rhine River. For the first hypothesis, a local evolution, the site of Barranc de la Boella in Spain could represent an early attempt of bifacial shaping and local onset of crudely made bifacial tools (as in East Africa for the Early Acheulean) [START_REF] Mosquera | Barranc de la Boella (Catalonia, Spain): an Acheulean elephant butchering site from the European late Early Pleistocene[END_REF][START_REF] Santagata | Operating systems in units B and E of the Notarchirico (Basilicata, Italy) ancient Acheulean open-air site and the role of raw materials[END_REF] . Partial bifacial shaping and the production of large flakes is rare in Western Europe and do not appear to represent a "transition" between simple pebble tools and Acheulean bifaces [START_REF] Schreve | Editorial: the early Acheulean occupation of western Europe: chronology, environment and subsistence behaviour[END_REF][START_REF] Moncel | From 800 to 500 ka in Europe. The oldest evidence of Acheuleans in their technological, chronological and geographical framework[END_REF] . In contrast, Barranc de la Boella could also represent the arrival of a non-local hominin group and technology.

At la Noira, Moulin Quignon and Isernia-la-Pineta, we observe some innovations and complexity with some cores exhibiting a debitage independent of the stone shape. This behavior is not observed in Mode 1 series older than 700 ka. Raw material is mostly local but with little evidence of fragmentation of the reduction processes as in Acheulean sites in East Africa [START_REF] De La Torre | Special issue on the early Acheulean of EF-HR (Olduvai Gorge, Tanzania)[END_REF] . Some Pebble-tools at Notarchirico, both in layers with and without bifaces, are pointed and bifacial. However, the shaping of these pebble-tools is always limited to a small part of the pebble and conforms to the stone shape. At la Noira, Moulin Quignon and Notarchirico, there are crudely-made bifacial tools with limited shaping, diversified and numerous heavy-duty components and a low ratio of bifaces. At Notachirico, as at Moulin Quignon and la Noira, the mode of shaping of the bifaces and LCTs indicates a technological shift and turning point at 700 ka, suggesting populations with different cognition and skills. Thus, a biface production appears by its complexity and specificity as an abrupt "invention" among the Western European series.

Notarchirico is located in the South of Italy and no early Acheulean sites are currently known in Northern/ central Italy, except perhaps Isernia-la-Pineta that did not deliver bifaces [START_REF] Gallotti | The lower/early middle pleistocene small debitage productions in Western Europe: new data from Isernia La Pineta t3c (Upper Volturno Basin, Italy)[END_REF] . Moreover, there is a chronological and behavioral gap between the "cores-and-flakes" series of Pirro Nord and Ca'Belvedere di Monte-Poggiolo, dated to around 1.4-1.0 Ma, and the bifacial technology at Notachircio [START_REF] Mosquera | From Atapuerca to Europe: tracing the earliest peopling of Europe[END_REF][START_REF] Arzarello | Evidence of an early Pleistocene hominin presence at Pirro Nord (Apricena, Foggia, southern Italy): P13 site[END_REF][START_REF] Peretto | L'industrie lithique de Ca'Belvedere di Monte Poggiolo: stratigraphie, matière première, typologie, remontages et traces d'utilisation[END_REF] . The sites of la Noira, Moulin-Quignon and Notarchirico are key sites for attempting to resolve the timing of the onset of the European Acheulean. All three sites show evidence of elaborate early biface production in a short window of time, between 700 and 650 ka. They demonstrate shared technological traditions over a wide area of Western Europe, from southern Italy to northwestern France during both interglacial and glacial conditions [START_REF] Ashton | Mapping the human record: Population change in britain during the early palaeolithic[END_REF][START_REF] Carrión | Early human evolution in the western Palaearctic: ecological scenarios[END_REF][START_REF] Macdonald | Discontinuity in the record for hominin occupation in south-western Europe: implications for occupation of the middle latitudes of Europe[END_REF][START_REF]Crossing the human threshold: dynamic transformation and persistent places during the middle Pleistocene[END_REF][START_REF] Hosfield | Early hominins in north-west Europe: a punctuated long chronology?[END_REF][START_REF] Dennell | Hominin variability, climatic instability and population demography in Middle Pleistocene Europe[END_REF][START_REF] Fiedler | Several lower palaeolithic sites along the rhine rift valley, dated from 1.3 to 0.6 Million Years[END_REF] . Geochronological data available for Notarchirico indicate that the site was occupied by hominins between 690 and 600 ka, over a period covering the end of MIS 17, the entire MIS 16 and the beginning of MIS 15. No major changes were observed in the large mammals palaeontological record, except the presence of the hippopotamus, indicating a temperate humid climate, in levels G and I1, both chronologically attributed to the late MIS 17. On the other hand, the microfauna assemblage of layers or archaeosurfaces E and F, geochronogically coeval of the glacial MIS 16, indicates cold environments, in agreement with the few available palynological data dominated by grasses and Pinus [START_REF] Cassoli | I vertebrati dei livelli superiori (A ed ALFA) della serie stratigrafica di Notarchirico, In Notarchirico; Un sito del Pleistocene medio-iniziale nel bacino di Venosa (Basilicata), Vol. I edizione Osanna (a cura di M. Piperno)[END_REF] . It should be underlined that the available regional palaeoenvironmental data (as the Ohrid record in Albania) [START_REF] Dennell | Hominin variability, climatic instability and population demography in Middle Pleistocene Europe[END_REF] show in Mediterranean area the permanent presence of deciduous trees even during the glacial stages at the beginning of the Middle Pleistocene, which corresponded more to arid than very cold periods.

At Notarchirico, Acheulean assemblages are associated both with interglacial (MIS17) and glacial (MIS16) contextes, while at La Noira and Moulin Quignon, the human occupations seems both contemporaneous to early glacial stages [START_REF] Moncel | Early evidence of Acheulean settlement in north-western Europe -la Noira site, a 700 000 year-old occupation in the Center of France[END_REF][START_REF] Voinchet | New chronological data (ESR and ESR/U-series) for the earliest Acheulian sites of north-western Europe[END_REF][START_REF] Antoine | The earliest record of Acheulean human occupation in North-West Europe[END_REF][START_REF] Moncel | The Acheulean workshop of la Noira (France, 700 ka) in the European technological context[END_REF][START_REF] Iovita | High handaxe symmetry at the beginning of the European Acheulian: the data from la Noira (France) in context[END_REF] . These sites also show the adaptability of hominins not only to climatic variability, but to widely varying geography and types of raw materials [START_REF] Moncel | La Noira site (Centre, France) and the technological behaviours and skills of the earliest Acheulean in Western Europe between 700 and 600 kyrs[END_REF][START_REF] Hardy | Middle Pleistocene hominin behavior at the 700ka Acheulean site of la Noira (France)[END_REF][START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF][START_REF] Schreve | Editorial: the early Acheulean occupation of western Europe: chronology, environment and subsistence behaviour[END_REF][START_REF] Lugli | Suspected limited mobility of a Middle Pleistocene woman from Southern Italy: strontium isotopes of a human deciduous tooth[END_REF][START_REF] Goren-Inbar | The Acheuliean site of Gesher Benot Ya'aqov[END_REF] . New cognitive skills, along with a new and diversified tool kit, could have helped hominins to extend their territories when the climatic conditions were more favorable. Furthermore, hominins were able to occupy northern territories despite the lack of the fire use, even as conditions became colder [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF][START_REF] Ashton | Mapping the human record: Population change in britain during the early palaeolithic[END_REF][START_REF] Carrión | Early human evolution in the western Palaearctic: ecological scenarios[END_REF][START_REF] Macdonald | Discontinuity in the record for hominin occupation in south-western Europe: implications for occupation of the middle latitudes of Europe[END_REF][START_REF]Crossing the human threshold: dynamic transformation and persistent places during the middle Pleistocene[END_REF][START_REF] Hosfield | Early hominins in north-west Europe: a punctuated long chronology?[END_REF][START_REF] Dennell | Hominin variability, climatic instability and population demography in Middle Pleistocene Europe[END_REF][START_REF] Fiedler | Several lower palaeolithic sites along the rhine rift valley, dated from 1.3 to 0.6 Million Years[END_REF] . The presence of hominins with similar bifacial technology over such a wide area of Western Europe could signal an increase in hominin populations or a high degree of mobility of hominin groups [START_REF] Derex | Partial connectivity increases cultural accumulation within groups[END_REF][START_REF] Derex | Divide and conquer: intermediate levels of population fragmentation maximize cultural accumulation[END_REF][START_REF] Fogarty | The niche construction of cultural complexity: interactions between innovations, population size and the environment[END_REF][START_REF] Vaesen | Complexity and technological evolution: what everybody knows?[END_REF][START_REF] Grove | Population density, mobility, and cultural transmission[END_REF][START_REF] Bocquet-Appel | Neanderthal demographic estimates[END_REF][START_REF] Howitt-Marshall | Middle Pleistocene sea-crossings in the eastern Mediterranean?[END_REF] .

At this point, the known Acheulean sites just after 700 ka in Western Europe suggests that southern areas did not just serve as refugia during glacial times even if milder than in North Western areas [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF][START_REF] Moncel | From 800 to 500 ka in Europe. The oldest evidence of Acheuleans in their technological, chronological and geographical framework[END_REF] .

In contrast to the penecontemporaneous Acheulean sites of La Noira and Moulin Quignon, Notarchirico is located far to the south. If we consider the possible pathways for the arrival of the Acheulean in this region, the location of Notarchirico in southern Italy suggests two possible paleogeography-dependent routes: (1) following the northern coasts of the Mediterranean Sea from the Levant during low sea levels in glacial phases, or (2) crossing the Sicily channel between Tunisia and Sicily, also during glacial periods with low sea levels. Given the evidence of probable hominin occupation of insular land masses in the Mediterranean during the Lower Paleolithic (Crete, Gavdos, and Naxos) [START_REF] Howitt-Marshall | Middle Pleistocene sea-crossings in the eastern Mediterranean?[END_REF] , along withrecent discoveries of evidence of settlement on Indonesian and Philippine Islands east of the Wallace line in Southeast Asia as early as 700 ka [START_REF] Derricourt | Out of Africa": sea crossings, land crossings and culture in the hominin migrations[END_REF][START_REF] Abbate | Early to middle pleistocene homo dispersals from Africa to Eurasia: geological, climatic and environmental constraints[END_REF][START_REF] Brumm | Age and context of the oldest known hominin fossils from Flores[END_REF][START_REF] Ingicco | Earliest known hominin activity in the Philippines by 709 thousand years ago[END_REF][START_REF] Leppard | Maritime hominin dispersals in the Pleistocene: advancing the debate[END_REF] , the Sicilian route deserves consideration, in spite of the absence of solid evidence of a land bridge.

Methods

Lithostratigraphy. Classical field and laboratory methods were used for this study. The names of formations and the definition of units follow international stratigraphic rules (Supplementary Raynal et al.). The sedimentological samples were mostly loose samples for grain-size analysis and some blocks for thin section investigation (J.-P. R.). They were processed for particle size analysis, geochemical analysis and thin section preparation at the PACEA laboratory (University of Bordeaux) (P.D. and A.Q.). A Horiba LA-950 laser particle size analyzer was used for the twenty samples for grain size analysis. Sample pretreatment included suspension in sodium hexametaphosphate (5 g/l) and hydrogen peroxide (35%), at room temperature for 12 h. The suspension was then subjected to 60 s ultrasounds to achieve optimal dispersion. The Mie solution to Maxwell's equation provided the basis for calculating particle size using a refractive index of 1.333 for water and 1.55i-0.01i for the particles. Grain size distribution expressed in ɸ units was decomposed into different Gaussian populations (parametric curve fitting method) to identify and quantify the main modes. Results are presented in Supplementary Tables S2 andS3 and in several diagrams). X-Ray fluorescence was used to characterize one sample after grinding and transformation into 300 mg pellets. X-ray fluorescence (ED-XRF) analysis was carried out using a portable SPECTRO X-SORT (40 kV, 50 μA). Measurements were recorded in an air path with an acquisition time of 300 s. The device was calibrated beforehand using ICP-AES/ICP-MS compositions from 26 samples of Neogene and Quaternary sediments obtained by the SARM-CRPG laboratory in Nancy. Only elements for which a correlation coefficient (R2) greater than 0.9 between ED-XRF and ICP-AES/ICP-MS values were taken into account. Elements lighter than Si are not detected with this device. Thin sections from three undisturbed sediment blocks were vacuum impregnated with polyester resin. The mineralogical content of thin sections was studied under the microscope in natural and polarized-analyzed light and minerals were identified by their optical characteristics (G. J.).

Geochronology. Methodological protocols including preparation and analytical processes can be found in Supplementary Tables S4 andS5 for both methods. The 40 Ar/ [START_REF] Moncel | Linking environmental changes with human occupations between 900 and 400 ka in Western Europe[END_REF] Ar weighted mean ages include all sources of uncertainties (neutron fluence gradient (J), as well as the total K decay constant [START_REF] Renne | Joint determination of 40K decay constants and 40Ar*/40K for the Fish Canyon sanidine standard, and improved accuracy for 40Ar/39Ar geochronology. Response to the comment[END_REF] . Samples were co-irradiated with the monitor standard ACs-2 associated with an age of 1.1891 Ma [START_REF] Niespolo | Intercalibration and age of the Alder Creek sanidine 40Ar/39Ar standard[END_REF] . Corrections for initial argon are based on an atmospheric composition of 298.56 [START_REF] Lee | A redetermination of the isotopic abundances of atmospheric Ar[END_REF] .

Faunal and lithic remains. The early Middle Pleistocene is characterized by major reorganizations of terrestrial ecosystems, occurring in successive phases during paleoenvironmental changes, and strongly influenced by the onset of 100 ka climate cyclicity. Dispersal phases, mainly related to the progressive diffusion in Italy of taxa from Eastern and Central Europe, led to mammal faunal renewal. The biochronology of the early Middle Pleistocene vertebrate faunas are related to the Galerian Mammal Age, which includes Ponte Galeria, Isernia and Fontana Ranuccio Faunal Units (Mecozzi et al., Supplementary).

Methods for taphonomic analysis are explained in detail in Supplementary Daujeard and Curci. We report the total number of skeletal remains (NRT), the number of identified specimens (NISP), the minimum number of elements (MNE) and the minimum number of individuals present (MNI). We recorded the dimensions (length, breadth and thickness) and anatomical, taxonomic, and modification data for all the recorded and identified specimens. Non-coordinated indeterminate fragments were only used for fragmentation studies (tissue types and size classes). Ontogenic age-at-death of prey specimens was based on dental eruption/replacement patterns and wear. We observed bone surfaces with the naked eye and we examined and photographed some elements to distinguish the various surface alterations using two Dino-Lite Digital Microscopes (AD7013MZT and AM7915MZT, magnification 20-220 ×).

Lithic analysis aimed to identify technological behaviors and reduction processes i.e. [START_REF] Boëda | Identification de chaînes opératoires lithiques du Paléolithique ancien et moyen[END_REF][START_REF] Geneste | Systèmes techniques de production lithique: Variations technoéconomiques dans les processus de réalisation des outillages paléolithiques[END_REF] according to raw materials. Petrographic descriptions were carried out using a non-destructive multi-parametric protocol for chert investigations (NM-PCI), with a formalized mixed-data matrix (Supplementary Eramo et al.). The NM-PCI uses a formalized description of macroscopic and mesoscopic characteristics (e.g., structure, texture, fracture), expressed in binary or ordinal variables, as well as colorimetric (i.e., CIEL*a*b*) and geochemical (i.e., K, Ca, Ti, Mn, Fe, Ni, As, Sr, Ba) continuous variables of the chert matrix, acquired with portable devices (Konica-Minolta CM-2600d spectrophotocolorimeter and a Thermo-NITON XL3t ED-XRF spectrometer). A selection of the transformed mixed data variables [START_REF] Gower | A general coefficient of similarity and some of its properties[END_REF] was statistically processed and visualized (i.e., PAM, t-SNE) in R software environment [START_REF] Core | R: a language and environment for statistical computing[END_REF] with the following packages: cluster [START_REF] Maechler | Cluster Analysis Basics and Extensions[END_REF] for data transformation, PAM algorithm and silhouette width; ggplot2 [START_REF] Wickham | ggplot2: Elegant Graphics for Data Analysis[END_REF] and Rtsne 75 for output visualization; and fpc [START_REF] Hennig | fpc: Flexible procedures for clustering[END_REF] for internal and external clustering validation.

Use-wear analysis [START_REF] Renne | Joint determination of 40K decay constants and 40Ar*/40K for the Fish Canyon sanidine standard, and improved accuracy for 40Ar/39Ar geochronology. Response to the comment[END_REF] included the Low-Power (LPA) and the High-Power Approaches (HPA) in order to obtain a detailed interpretation of the function of chipped stone tools (Supplementary Figs. S26,S27). The LPA analyses traces of use observable at low magnification (generally up to 70-80 ×), defined in the literature as macro-traces, which for flint artefacts consist of: edge removals (scars resulting from use) and edge rounding. The HPA analyses traces of use observable at high magnifications (at least 100 ×), defined in the literature as micro-traces, which for flint artefacts consist of micro edge rounding, polish and striations. The LPA was applied to the chipped stone tools of Notarchirico using a Nikon SMZ stereomicroscope with a magnification range of 0.75 to 7.5 × equipped with a 10 × ocular, a 1 × objective, a reflected light system and a ToupView CMOS. The LPA enabled us to obtain a first evaluation of the degree of preservation of the lithic industry, to sample the tools with macro-wear and to infer the activities carried out and the hardness of the processed materials. The HPA was applied with a Nikon Eclipse metallographic microscope, with 10 ×, 20 ×, 50 × oculars equipped with a ToupView CMOS Camera. Helicon Focus software was used for picture focus stacking. A digital microscope Hirox RH-2000 was also used to observe highly reflective surfaces and to obtain images with ultra-fine detail. Micro-wear observation was carried out at the LTFAPA laboratory on lithic surface molds made with an ultra-fine dual-component silicone Provil Novo Light Fast, Heraeus (licence paid by C. Lemorini). Use-wear was interpreted with reference to the comparative reference collection of flint replicas of the LTFAPA laboratory of the Sapienza University (Supplementary Lemorini).

Figure 1 .

 1 Figure 1. Notarchirico, the penecontemporaneous Acheulean sites of la Noira and Moulin Quignon, and other Western European sites dated between 1.4 Ma and 590 ka with or without bifaces. The sites are attributed to cores-and-flakes type sites (Mode 1), Acheulean sites or Lower Palaeiolithic sites (Mode 2). (Map drawn and created by P. Voinchet and M-H. Moncel).

Figure 2 .

 2 Figure 2. Stratigraphic log of the Notarchirico sequence (Modified from Raynal et al., 1999) with the 40Ar/39Ar and ESR dates on bleached quartz and the location of the phases of human occupation (with or without bifaces). The new fieldwork concerns the base of the sequence from layers F to J2. (Modified after J-P. Raynal and A. Pereira, by P. Voinchet and M-H. Moncel).

Figure 3 .

 3 Figure 3. Illustrations of the new fieldwork at Notarchirico. (1) The 30 m-trench opened outside the building with the excavations of M. Piperno. (2) Layer F. Elephant tooth among the bed of pebbles. (3) Layer F. Fragment of elephant tusk and limestone pebble tools. (4) Layer G. Fragment of ungulate bone and pebble. (5) Layer F. Biface on a limestone pebble. (6) Aspect of layer I2, bed of pebbles. (7) Layer I2. Fragment of ungulate bone. (8) Layer I1. Fragment of bone. (9) (a) flake 2017 A18 F2: edge removals with feather/step terminations, diagonal unidirectional traces interpreted as resulting from cutting soft materials; (b) flake 2017 B19 F9: edge-removals with feather/step terminations, perpendicular direction interpreted as scraping soft/medium material. (Photos M-H. Moncel, C. Santagata n°1-8, n°9 C. Lemorini).

Figure 4 .

 4 Figure 4. Artefacts on chert nodules. (1-4) small retouched nodules from layers G and I.Hominins selected small quadrangular nodules for a direct, abrupt and denticulate retouch. (5-6) unifacial discoid-type cores (layer I2). Removals are centripetal. The preparation of the striking platform is limited or absent. (Photos M-H. Moncel, C. Santagata).

Figure 6 .

 6 Figure 6. Layer G. (1) Recycled bifacial or trifacial tool on a limestone pebble. (2) Bifacial tool on a large chert nodule.(3) Biface on limestone pebble. Two limestone bifaces were also discovered in layer G, including one recycled specimen. As with the bifaces of layer F, they demonstrate a bifacial volume management and equilibrium of the two faces of the tool, as for the tools of layer F. The n°1 shows a triface/biface on a pebble. It is a recycled tool with centripetal smooth removals on one flat face (lower face). The second phase of shaping used the piece as a preform to shape the opposite face by abrupt and more or less invasive removals on both lateral edges and the proximal extremity. There are crushing marks on the round tip, which is slightly shaped. The second biface is also on a pebble (n° 3). Shaping is alternate managing the whole volume by invasive and small removals to create a symmetrical tool. The shape is symmetrical. There is also one bifacial tool on a large chert nodule (n° 2). Using the natural shape of the nodule, the shaping is made by bifacial invasive convergent removals on one side and the proximal part form a tool that is asymmetrical in shape and cross-section, preserving a back on the opposite side. A back is preserved on the opposite side. There is with a notch related to a bec at the tool extremity. Detailed descriptions are given in the Supplementary data. (Photos M-H. Moncel, C. Santagata).

Table 1 .

 1 Synthesis of the sequence with location of archaeological layers, human behaviors and sampling.

						Samples (sedimentology NOT and
	Lithostratigraphic unit	Archeo unit Sub-unit Human behaviors	Characteristics	geochronology Ar, ESR)
					Bed of cobbles-pebbles
	3	F (8 m 2 )		Bifaces, cores and flakes	Cross-bedded volcano-derived and non-volcanic sands 20 cm
					Archaeological layer
	3		F1		Black volcanic sands 20 cm	NOT 17 01 Sample Ar
	4.1				Brown with small gravel 1 m	NOT 17 02 NOT 17 03
	4.2	G (10 m 2 )	G1	Bifaces, cores and flakes	Dark-grey volcanic sands 30 cm Archaeological layer	ESR sample
	4.3				Coarse sandy sub-unit with cobbles and sub-angulous gravels 30 cm	NOT 17 04 NOT 17 05
	5.1		H1a	Dispersed flakes	Silty-sandy deposit 10 cm Dispersed archeological material	NOT 17 06
	5.2		H1b		Silty-sandy deposit 10 cm Dispersed archeological material	NOT 17 08 ESR sample
	5.3	H (6 m 2 )	H1c	Dispersed flakes	Silty-sandy deposit. Sandier and oxidized with a few micro-beds of dark minerals 30 cm Dispersed archeological material	NOT 17 07 NOT 17 09 NOT 17 22 ESR sample
					Local lenses of small pebbles 15-30 cm	NOT 17 10
	6.1	I (26 m 2 )	I1a-b-c	Cores and flakes	Coarse sands and beds of more or less dense gravels with pluri-millimetric anastomosed	NOT 17 11 NOT 17 12
					crusts 40-45 cm	NOT 17 13
					Dispersed archeological material	Sample Ar
					Dense accumulation of cobbles and smaller
	6.2	I (26 m 2 )	I2	Cores and flakes	elements with limestones pebbles and a few fine-grained sandstone cobbles and flint nod-	NOT 17 14
					ules 10-15 cm
					Archaeological layer
	7.1				Tuffaceous sub-unit 3 cm	NOT 17 15
	7.2				Coarse yellow sands with a few cobbles 15 cm	NOT 17 16 Sample Ar
	7.3	J (4 m 2 )	J1	Cores and flakes	Tephra-derived coarse sands with some cobbles 10 cm	NOT 17 17 Sample Ar
	7.4	J (4 m 2 )	J2		Cobbles in a clayish volcano-derived matrix 30 cm	NOT 17 18 NOT 17 19
	8.1				Light-grey sand and micro-breccia	NOT 17 20
	8.2				Coarse yellow sands	NOT 17 21

Table 2 .

 2 Heavy-duty component on limestone pebbles per archaeological layer (number) and flakes in other stones.

	Layer	J	I2	I1	H	G	F
	Unifacial convergent LCT tools		2			6	5
	Bifaces					2	4
	Unifacial pebble tools	2	5	9	1	15	34
	Bifacial pebble tools		1	2		2	6
	Pointed unifacial pebble tools			2		6	10
	Pointed bifacial pebble tools/LCTs			1			4
	Trifacial pebble tools			1		1
	Rabots on pebbles		1			2	5
	Quadrangular unifacial tools						2
	Broken pebbles with impacts + isolated removals			1		31	52
	Flakes		2	2		7	46
	Other stone products		1	5	1		4

Table 3 .

 3 The tool kit on chert: number of flakes, fragments of flakes, retouched nodules and heavy-duty tools per archaeological layer.

	Layer	J	I2	I1	H	G	F
	Unretouched flake 5 (4 retouched) 40 (18 retouched) 98 (9 retouched)	21 (7 retouched) 78 (33 retouched) 177 (29 retouched)
	Broken flakes-debris		9 (3 retouched)	95 (10 retouched) 19 (6 retouched) 78 (23 retouched) 66 (7 retouched)
	Retouched nodules		4	21	1	50	12
	Cores	1	6	10		25	10
	Bifacial tools					1	1
	Bifaces						1

Vol:.(1234567890)Scientific RepoRtS | _#####################_ | https://doi.org/10.1038/s41598-020-68617-8

Scientific RepoRtS | _#####################_ | https://doi.org/10.1038/s41598-020-68617-8

Acknowledgements

Fieldwork was carried out with the financial and scientific support of the Leakey Foundation ("Early Evidence of Acheulean bifacial technology in Europe" grant, 2015-2016 and 2019-2020) and the National Museum of Natural History, Paris, France (ATM Action Transversale du Muséum, 2016-2018). We thank the Soprintendenza of Basilicata (Italy) for their scientific support, especially Dr. T.E. Cinquantaquattro, Dr. F. Canestrini, Dr. R. Pirraglia, and Dr. S. Mutino. We also thank the Venosa Museum and Dr. A. Mantrisi for their assistance. We also thank Rosalia Gallotti for useful remarks on the lithic assemblages. The paper was edited by Louise Byrne, official translator and native English speaker. We would like to thank the two reviewers for their useful remarks that deeply helped us to enhance the paper.

Author contributions

Competing interests

The authors declare no competing interests.

Additional information

Supplementary information is available for this paper at https ://doi.org/10.1038/s4159 8-020-68617 -8.

Correspondence and requests for materials should be addressed to M.-H.M.