Madalina Olteanu

Fabrice Rossi

Florian Yger

Challenges in anomaly and change point detection

Introduction

Real world data intensive applications are subject to the adverse effects of noise, outliers and anomalies that are common in large scale data. In addition, while shortly lived models can be built under a stationary assumption, many applications are long lived and face some form of drift in the data which can manifest as change points when the evolution is not smooth. The introduction of this paper gives a brief overview of the vast scientific literature dedicated to anomaly and change-point detection, with a focus on surveys and books. We introduce the main vocabulary and concepts needed to navigate further this literature and summarise some of the main challenges faced by practitioners.

Anomalies and outliers are generally defined as observations that deviate in an important way from other observations. While they have been studied since the very early stages of modern statistics (see e.g. [START_REF] Edgeworth | On discordant observations[END_REF]), dealing with them remains challenging. Thousands of research papers have been published on those topics, as well as numerous surveys, review papers and textbooks. An early standard text on outlier detection from the statistical community is for instance [START_REF] Barnett | Outliers in Statistical Data[END_REF], originally published in 1978. Numerous problems surrounding anomaly detection were already identified (and somewhat addressed) by the first edition of this book: the unavoidable presence of outliers in large data sets, the need for multivariate outlier detection, differences between individual outliers and groups of outliers, the need to take into account the dependency structure of the data (for instance to find outliers in time series), etc.

The need to "live with outliers" lead to the design of robust estimation methods and to the field of robust statistics (see for instance [START_REF] Rousseeuw | Robust Regression and Outlier Detection[END_REF], originally published in 1987). The main justification for robust statistics is that non robust estimators (e.g. the mean as an estimator of the expectation) can be corrupted by a very small number of outlier observations, leading to a biased estimation bounded only by the severity of the outliers (and the sample size). This is "solved" by replacing robust variants of those estimators (e.g. the median instead of the mean). See [START_REF] Rousseeuw | Anomaly detection by robust statistics[END_REF] for a recent survey on robust statistics applied to anomaly detection.

The robust statistics approach provides a very good illustration of the core dilemma of anomaly detection which is summarised by C. C. Aggarwal [START_REF] Aggarwal | Outlier analysis[END_REF] with the sentence "The data model is everything". Indeed, almost all anomaly detection methods proceed by first building a model of "normal" data and then by using it to score observations in such a way that anomalies have a high score. In statistics, models are probabilistic and the scores are inversely proportional to the likelihood of observations. More generally, scores are derived from prediction quality of the data model: a poorly predicted observation has a high score and vice versa. Unfortunately, the presence of outliers in the data set used to build the model will generally bias it in such a way that those outliers will be considered more "normal" than they should (normal observations may also be assigned too large scores). In other words, in order to build a good anomaly detection model, one should use outlier free data! From its early statistical roots, the field of anomaly detection has evolved to encompass more ad hoc methods from all the sub-fields of data science (e.g. deep learning, see [START_REF] Pang | Deep learning for anomaly detection: A review[END_REF]) and to broaden it application fields, as illustrated by the data mining oriented survey from Chandola et al. [START_REF] Chandola | Anomaly detection: A survey[END_REF] and Aggarwal's book [START_REF] Aggarwal | Outlier analysis[END_REF]. While numerous challenges were already identified in the statistical community, others have emerged. For instance, older statistical methods were originally focused on numerical data, while discrete data oriented methods are more recent (see [START_REF] Taha | Anomaly detection methods for categorical data: A review[END_REF] for a recent survey). Earlier works focusing on taking into account the dependency structure of the data were dedicated mainly to the regression case (under the Gaussian noise hypothesis) and to time series [START_REF] Blázquez-García | A review on outlier/anomaly detection in time series data[END_REF]. This has been extended to more general structures, for instance to the classification case (especially for methods addressing label noise, see e.g. [START_REF] Frenay | Classification in the presence of label noise: A survey[END_REF]) and to spatial structures (see for instance [START_REF] Shekhar | A unified approach to detecting spatial outliers[END_REF]). Arbitrary dependencies between observations can be represented via graphs, an approach that gave birth to Graph Signal Processing (GSP) methods (see [START_REF] Ortega | Graph signal processing: Overview, challenges, and applications[END_REF][START_REF] Dong | Graph signal processing for machine learning: A review and new perspectives[END_REF] for surveys). Graph filters can be used to remove (and therefore detect) noisy observations under arbitrary dependencies, generalising techniques developed for time series.

More generally, recent trends include handling data with intrinsic complex structure (rather that classical data with complex dependency structure), for instance whole time series, i.e. data in which each observation is a time series, see [START_REF] Blázquez-García | A review on outlier/anomaly detection in time series data[END_REF]. A popular case is the one of graph valued data where each observation is a graph or where the full data set is represented by a single observed graph (i.e., when the links are measured and not expert based dependency hypotheses). See [START_REF] Akoglu | Graph based anomaly detection and description: a survey[END_REF][START_REF] Ma | A comprehensive survey on graph anomaly detection with deep learning[END_REF] for surveys.

Change point and drift detection is a related problem that has also received a significant attention. Following the same pattern, early methods were developed by statisticians, for instance the well known CUsUM technique proposed by Page in 1954 [START_REF] Page | Continuous inspection schemes[END_REF]. Since then, numerous papers, surveys and books have been dedicated to change point detection (see for instance [START_REF] Basseville | Detection of abrupt changes: theory and application[END_REF][START_REF] Tartakovsky | Sequential Analysis: Hypothesis Testing and Changepoint Detection[END_REF] for online techniques, [START_REF] Truong | Selective review of offline change point detection methods[END_REF] for offline ones and [START_REF] Aminikhanghahi | A survey of methods for time series change point detection[END_REF] for a general survey).

The main difference between anomaly detection in a temporal context and change point detection is that the latter is generally leveraging three data models rather than one. In essence, one compares the quality of a single model for the whole time series (or a sub-sequence) with the quality of two models, one before the tentative change point and one after. As the change point is unknown, model estimation is potentially biased: one model can be estimated using a mixture of data before the true change point and data after the true change point. This phenomenon is closely related to the one faced by anomaly detection technique, with the additional aspect that the "anomalies" are here somewhat structured (as they are produced by another model).

In the scientific literature, the terms drift detection are generally specific to change detection in a supervised context, especially in the classification setting. This amounts essentially to detecting when a predictive model is not adapted anymore to new data. Unsupervised methods, i.e. methods that do not assume the true labels will be known without too much delay after a prediction is made, are the closest to change point and anomaly detection ones (see [START_REF] Gemaque | An overview of unsupervised drift detection methods[END_REF] for a specific survey on those unsupervised methods and [START_REF] Lu | Learning under concept drift: A review[END_REF][START_REF] Agrahari | Concept drift detection in data stream mining : A literature review[END_REF] for more general ones).

The rest of the paper is organised as follows. We introduce the vocabulary and core concepts needed to understand the challenges of anomaly and change point detection in Section 2. Section 3 discusses C. C. Aggarwal's summary of the main difficulty faced by all techniques: "The data model is everything". Section 4 concludes the paper by presenting two of the main current challenges in the field.

2 Core concepts

Anomaly, noise and outlier

Anomalies and outliers are generally defined in plain English using arguably vague sentences such as

• an anomaly "appears to deviate markedly from other members of the sample in which it occurs" [START_REF] Grubbs | Procedures for detecting outlying observations in samples[END_REF];

• an outlier is "an observation which deviates so much from the other observations as to arouse suspicions that it was generated by a different mechanism" [START_REF] Hawkins | Identification of Outliers[END_REF];

• an outlier is "an observation (or subset of observations) which appears to be inconsistent with the remainder of that set of data" [START_REF] Barnett | Outliers in Statistical Data[END_REF].

Those informal definitions should be considered as guiding principle to define mathematically sound and operational definitions, as we will see below. In particular, Chandola et al. write in [START_REF] Chandola | Anomaly detection: A survey[END_REF] "Anomalies are patterns in data that do not conform to a well defined notion of normal behavior." which constitutes already a step towards more formal definitions. Notice that we do not distinguish between anomaly and outlier, but there is some value in being more precise in some contexts. Aggarwal proposes in [START_REF] Aggarwal | Outlier analysis[END_REF] to distinguish noise from anomaly by the intensity of the deviation from normality: noisy data are more normal than anomalies. Then he proposes to call outliers noisy data as well as anomalies (possibly distinguishing weak outliers from strong outliers).

This distinction can be illustrated in probabilistic terms with the classical Gaussian distribution. Let us assume that a quantity is measured with an additive measurement noise distributed according to a standard normal distribution and that the true quantity should be 100 (in some adapted measurement unit). Then any measurement between 98 and 102 will be considered normal because roughly 95% of measurements made on a true quantity of 100 will fall in this interval. A measurement of 103 could be considered as noisy, as a true quantity of 100 shall lead to a measurement larger or equal to 103 only in 0.13% of the observations. Then a measurement of 105 could be considered as anomalous because observing values larger or equal to 105 should happen only once for more than 3 millions measurements on average.

This basic example illustrates the main difficulties of anomaly detection: we need to chose a data model (here the standard normal distribution and the fact that the true quantity is 100) as well as decision thresholds.

Type of anomalies

Chandola et al. [START_REF] Chandola | Anomaly detection: A survey[END_REF] sort anomalies into three categories or types. The simplest case is the one of point anomalies where a single observation can be classified in isolation as an anomaly. This type of anomaly is the main focus of most of the methods. In statistical and machine learning terms, it is associated to the classical independence hypothesis between observations. When the observations are statistically dependent, the notion of anomaly should be revised. Indeed, the expected value of an observation is in this case dependent from the values of other observations. Then the status of an observation (normal or anomalous) cannot be decided in isolation. Such anomalies are called contextual anomalies or conditional anomalies.

The most well known case of contextual anomalies is the one of time series [9] but numerous extensions have been considered, some recently. It should be first noted that the terms time series generally refer to temporal data with numerical values, while there is also an important literature on discrete sequences, i.e. time series with categorical values (see [START_REF] Chandola | Anomaly detection for discrete sequences: A survey[END_REF] for a survey). Spatial data have also been studied, for instance in [START_REF] Shekhar | A unified approach to detecting spatial outliers[END_REF].

As pointed out in the introduction, graphs can be used to represented fully arbitrary dependencies between observations and denoising filters from signal processing can be generalised from the time domain to the graphical one, leading to the field of graph signal processing (GSP) [START_REF] Ortega | Graph signal processing: Overview, challenges, and applications[END_REF][START_REF] Dong | Graph signal processing for machine learning: A review and new perspectives[END_REF]. When the graph is observed, one can use it as a dependency hypothesis, leveraging GSP or other approach, or, on the contrary, one can question it, considering edges as potential outliers. This leads to a generalised notion of contextual anomaly specific to graph anomaly detection [START_REF] Akoglu | Graph based anomaly detection and description: a survey[END_REF][START_REF] Ma | A comprehensive survey on graph anomaly detection with deep learning[END_REF].

The third category of anomalies is the one that concerns groups of observations. In point or contextual anomalies, a single observation is considered anomalous when confronted to a subset of related observations (which are themselves normal). In collective anomalies, a subset of observations is considered as a whole to be anomalous even if each observation is normal considered in isolation (or within its natural context). A typical example is a faulty sensor that stops updating for a short time period and then resumes normal operation: the fact that the sensor reports several identical values while possible might be a hint that something is not working as expected, even if the value is perfectly valid. In addition to the temporal context, collective anomalies are frequently searched for in spatial data and in graphs (see e.g. [START_REF] Larroche | Percolation-based detection of anomalous subgraphs in complex networks[END_REF]).

In practical applications, such as computer intrusion detection (see e.g. [START_REF] Ahmed | A survey of network anomaly detection techniques[END_REF]), it is common to look for several types of anomalies, depending on the hypotheses on data generation. In addition, data tend to be collected more and more thoroughly leading to complex data sets such as temporal network data, which combine naturally a complex structure and non trivial dependencies.

Change and drift detection

Change-point detection relates to anomaly detection, in particular to contextual and collective anomalies. The main conceptual difference between both is that data are "normal" on both sides of a change point, and are only considered anomalous from the point of view of the other model. Change-point analysis implies the data to be available in a sequential manner, and is therefore more common for temporal or streaming data, or more generally for ordered data (see the following section).

Generally designed in an unsupervised context, change-point detection builds upon the idea that the underlying distribution of the data is abruptly changing at some unknown instants. While the first historical methods focused on detecting changes in the mean value (as in CUsUM [START_REF] Page | Continuous inspection schemes[END_REF] discussed in the introduction), subsequent developments proposed numerous modelling frameworks, both parametric and nonparametric.

In the supervised learning context, an abrupt change in the data distribution is generally called a concept shift. Because of the asymmetric nature of the data, with "inputs" X t and "outputs" (a.k.a. predictions) Y t , research on concept shift distinguishes different types of change, namely in marginal distributions (P(X) or P(Y )) or in conditional distributions (P(X|Y ) and P(Y |X)). Covariate shift [START_REF] Sugiyama | Machine learning in non-stationary environments: Introduction to covariate shift adaptation[END_REF] and prior probability shift are the terms used to refer to changes in the marginal of X or Y respectively. The main focus of research is generally true concept shift, i.e. changes over time in P(Y |X), including the difficult case of handling new values for Y in the classification setting. The term data set shift [START_REF] Quinonero-Candela | Dataset shift in machine learning[END_REF] is also used in the literature and can encompass many diverse situations ranging from the aforementioned concept drift to sample selection and domain shift.

While there is not a perfect consensus on the vocabulary, it is generally admitted to use shift for abrupt changes and drift for smoother change in the data distribution (see e.g. the discussion in [START_REF] Agrahari | Concept drift detection in data stream mining : A literature review[END_REF]). Notice however, that in the data mining community, especially in data stream literature, the dominant term is concept drift, in a way that encompass both abrupt and gradual changes, and that even extends to the unsupervised context (see [START_REF] Gemaque | An overview of unsupervised drift detection methods[END_REF]).

Operational hypotheses

The conditions under which anomaly or change detection is performed can have a significant impact on the design and the performances of the detection methods.

While very uncommon, the case of supervised learning should be mentioned for anomaly detection. Indeed in some application contexts such as fraud or computer intrusion detection, it may be possible to collect a data set with labelled examples combining (a lot of) normal examples and (a small set of) anomalous examples. In this case, the problem is a standard but difficult supervised learning one. The difficulties come from the unbalanced nature of the data (collecting examples of anomalous behaviour is generally difficult) and from the ill-posed nature of the classification: while the normal data class is well defined, the anomalous data form a collection of unrelated examples that can exhibit vastly different characteristics (in contrast to change point or drift detection settings where both data distribution are supposed to be somewhat consistent). In addition, the normal data set can be contaminated by undetected anomalies. Variations over the fully supervised learning context include the also classical semi-supervised one, with a specific variant where only one class (the anomalous one) is labelled. We refer the reader to Chapter 7 of [START_REF] Aggarwal | Outlier analysis[END_REF] for further details.

In practice, anomaly and change point detection will therefore be mostly conducted under the unsupervised learning paradigm (to the point where most surveys discuss only unsupervised techniques). On the contrary, concept drift detection will be mostly conducted under the supervised learning paradigm.

Another important aspect is specific to temporal (or ordered) data and applies to both change and anomaly detection. Models can be applied in an on-line way or in an off-line way. In the former, the data appear as a stream and the goal is to take a decision on the last observation using only the past observations. This can be slightly relaxed by allowing some delay between the observation and the decision, which enables the method to see some observations that occurred after the one under analysis. In the off-line mode, the data is fully observed before applying the method. A classical trade-off between the modes are accuracy versus delay: on-line methods are generally less accurate than off-line ones, but the latter cannot be used in a streaming context or to react quickly to new observations.

3 "The data model is everything"

A unifying view

As pointed out in [START_REF] Aggarwal | Outlier analysis[END_REF] one can summarise the whole field of anomaly detection as follows: "Virtually all outlier detection algorithms create a model of the normal patterns in the data, and then compute an outlier score of a given data point on the basis of the deviations from these patterns." As discussed above, this generalises to some extent to change point detection and to concept drift detection. In those cases, we have a "current" data model which is confronted either to some new observations or directly to another data model. In these settings, models are compared via observations, by assessing which model is better at describing one or several observations. Thus anomaly and change detection methods differ by the assumptions they make on the data as translated into the model building strategy, and by the aggregation level at which they compare entities of interest (a single observation versus a model, a collection of observations versus a model, two models).

Consequences

As already discussed in the Introduction, this "model and score" view emphasises the core difficulty of anomaly and change detection: in general, the data model will be adjusted to the observations blindly, that is without knowing in advance whether a given observation is normal or not. Thus model fitting must be somehow "robust" to the presence of outliers (not necessarily in the robust statistics sense). This is surprisingly difficult as even "simple" tasks such as computing a mean or a covariance matrix are biased in presence of anomalies [START_REF] Rousseeuw | Robust Regression and Outlier Detection[END_REF].

In addition, owing to the unsupervised nature of the problem (in most of the cases), model choice is difficult. In essence, we are in a typical case of a ill-posed model. If we come back to the very basic example of a Gaussian noise described above, results would be quite different using another noise distribution such as a Laplace one. For instance using a Laplace distribution with unitary variance, centred on 100, the probability of observing 105 or more is larger than 1/2500, compared to 1/(3.5 × 10 6 ) for the standard normal distribution. In a sense the Laplace noise model is more tolerant to extreme values than the Gaussian one. More generally, the nature of some observations is very likely to depend on expert hypotheses on the data generation process and it seems a bit naive to hope for fully automated generic models.

Moreover, the vast majority of the methods output an anomaly score or a comparable quantity in change detection approaches (e.g. model dissimilarities). In a decision oriented setting, this continuous quantity must be turned into a binary one: is this observation an anomaly? is there a shift in the data distribution? While researchers tend to focus on score evaluation, using for instance the area under the ROC curve (AUC) as an integrated quality metric, practitioners generally need decisions. It is common to read that ranking the observations based on their score allows one to avoid setting a decision threshold. However ranking is putting the weight of the decision on the analyst shoulders, as he/she will have to decide where to stop in the list of ranked observations. Even worse, the stopping decision could be driven in this case by operational considerations (such as human resources available to investigate the anomalies). While those are valid considerations, they should be explicitly stated. In summary, thresholding scores into decisions is part of the model fitting process and should not be ignored. Notice that the discussion applies almost as is to change point detection: fixing the decision threshold is equivalent to fixing a number of anomalies (on a static data set), whose counterpart in change detection is the number of change points.

Challenges and opportunities

As summarised above, anomaly detection and change detection are somewhat ill-posed problems (as e.g. clustering [START_REF] Luxburg | Clustering: Science or art?[END_REF]) and expert input and monitoring is necessary to obtain meaningful results. Evaluating objectively the proposed methods remains also a difficult problem for the same reasons.

Interpretability and visualisation

On the best way to engage users in machine learning algorithm monitoring and steering is via information visualisation techniques [START_REF] Endert | The state of the art in integrating machine learning into visual analytics[END_REF], especially when the goal is explicitly to enhance the trust of the user into the results provided by the algorithm [START_REF] Chatzimparmpas | The state of the art in enhancing trust in machine learning models with the use of visualizations[END_REF]. As far as we known there is unfortunately no general survey on visualisation techniques directly targeting anomaly or change detection, but two specific application contexts have been reviewed: network monitoring [START_REF] Zhang | A survey of network anomaly visualization[END_REF] and user behaviour [START_REF] Shi | Visual analytics of anomalous user behaviors: A survey[END_REF].

More generally, there is a strong need for interpretable detection. A recent survey [START_REF] Panjei | A survey on outlier explanations[END_REF] presents the state-of-the-art in this direction. It outlines several strategies to provide anomaly explanations, mainly score unification (that brings comparability between detection methods), outlying attribute identification and causal interaction among anomalies (x is an anomaly because y appeared before in the data set).

Both visualisation and interpretability remain relatively new in the literature but are also considered as very important for the applicability of detection methods in real world application, as argued by e.g. this position paper [START_REF] Riveiro | The importance of visualization and interaction in the anomaly detection process[END_REF] and this survey [START_REF] Ma | A comprehensive survey on graph anomaly detection with deep learning[END_REF]. These topics are actively researched as exemplified by Hinder et al. paper [START_REF] Hinder | Contrasting explanation of concept drift[END_REF] is the present volume.

Benchmarking

Unsupervised models are notoriously difficult to evaluate [START_REF] Luxburg | Clustering: Science or art?[END_REF] as a consequence of their ill-posed nature: each model uses generally different hypotheses about the data generation process, with an associated quality metric for which it is optimal (but of course not for other metrics). The gold standard is to refer to a collection of labelled data sets where the ground truth is known with reasonable certainty (and representative of the task at hand). This is surprisingly difficult to achieve in anomaly and change detection settings, generally for cost reasons as, by definition, expert based labelling is needed to build the ground truth. This is particularly costly because the anomalies are by essence rare: in order to label enough anomalies, very large data sets are needed. An example of evaluation under this gold standard is included in Coussirou et aL. paper [START_REF] Coussirou | Anomaly detections on the oil system of a turbofan engine by a neural autoencoder[END_REF] in this volume. In some situations, it is possible to generate anomalies or changes using artificial models or human intervention. This is illustrated by Bel-Hadj et al. paper [START_REF] Bel-Hadj | Anomaly detection and representation learning in an instrumented railway bridge[END_REF] in the present volume. But this is generally not the case, as discussed for instance by [START_REF] Ahmed | A survey of network anomaly detection techniques[END_REF] in the case of classical network intrusion benchmarks.


Antoine Fraboulet
email: antoine.fraboulet@insa-lyon.fr

Tanguy

Tanguy Risset
email: tanguy.risset@ens-lyon.fr

Master Interface For On-Chip Hardware Accelerator Burst Communications

Keywords: system on chip, SoC simulation, high level synthesis, interface generation

published or not. The documents may come

Introduction

Large scale systems on chip (SoC) design is faced with many problems among which efficient communication managing is one of the most important. In the past, communication efficiency has already been one of the major burden in parallel machine development but in addition, today's on-chip communications are limited by the power consumption problem. Network on chip based SoC architectures are not arriving as fast as envisaged because of the power consumption problem. In addition, shorter design time is required to meet the ever increasing time-to-market constraints. IP re-use and platform based design are pointed out as solution to faster design but they are still confronted with important limitations and are not really used in today's industrial design flows. Examples of these problems are: IP standardisation, system on chip cycle accurate simulation time [START_REF] Pétrot | A simulation environment for core based embedded systems[END_REF][START_REF] Gracia Pérez | A new optimized implementation of the systemC engine using acyclic scheduling[END_REF], and fast integration of special purpose hardware in a design environment.

We address the problem of providing a rapid and efficient integration of a special purpose hardware accelerator into a complex system on chip possibly integrating many processor cores and important software applications. More precisely, we will focus on the category of stream processing hardware accelerators. Stream processing performs on-the-fly costly computations on streams of data. The amount of control in these computations is reduced, but the complexity lies in the quantity of computations usually submitted to soft real time constraints (as for audio or video processing). Hardware accelerators containing parallel computation usually presented in the form of arrays of processors are mandatory to meet these constraints. we refer to these accelerators as data-flow ips. Systolic arrays are examples of such data-flow ips but they are not the only ones. In this paper we only target linear array of processor which have a small number of input/output ports, the problem of interfacing 2D array of processors has been studied in [START_REF] Darte | Hardware/software interface for multidimensional processor arrays[END_REF], but the problems encountered are quite different and many ip integrated to SoC are 1D arrays because of the high bandwidth required by 2D arrays.

The hardware accelerators used in SoC for portable communication systems (cell-phones, pda,. . . ) are originally designed by hardware designers in collaboration with signal processing engineers. For these ips, the performance bottleneck lies in the communication of the data between memory and the ip. The paradigm used for specifying and designing these circuits is called the data-flow model: designers manipulates streams of data which input and output the circuits without any information about the external storage of these data. The interface protocol is data synchronised which means that the behaviour is regulated by the consumption and production of data at the boundaries of the architecture. In this protocol, if the data is not present the computations are stopped, usually with a clock enable mechanism.

Until recently, these ips where designed by hand with a precise methodology, knowing in advance the target SoC architecture. Hence the design of the interface was more or less performed together with the architecture. New trends in SoC design require the use of tools to accelerate the design phase of specific hardware accelerators. These tools are called high level design, behavioural synthesis tools or hardware compilers [START_REF] Guillou | High level design of digital filters in mobile communications[END_REF][START_REF] Casseau | Architectural synthesis of digital processing applications dedicated to submicron technologies[END_REF][START_REF] Schreiber | High-Level Synthesis of Non Programmable Hardware Accelerators[END_REF]. Most of the time, because of the huge design space they propose to the user a toolbox for tuning parameters of the resulting architecture. However, even if these tools greatly accelerate and secure the design of the ip itself, the time needed to write the interface may render the tool simply useless. Today, these tools produce some configuration information that helps in the design of the interface, but this part has not been standardised. In this paper, based on the experience of MMAlpha [START_REF] Derrien | Automatic synthesis of efficient interfaces for compiled regular architectures[END_REF][START_REF] Fraboulet | Cycle accurate simulation model generation for SoC prototyping[END_REF] and Gaut [START_REF] Casseau | Architectural synthesis of digital processing applications dedicated to submicron technologies[END_REF], we identify the common concepts that are used by data-flow ip designers to propose a generic interface mechanism. This generic interface mechanism will be parameterised by the configuration information output from data-flow ip generators. We also hope to bring a standard way of describing data-flow ip input/output behaviour so as to facilitate ip reuse.

We introduce in this paper some theoretical foundations for the automatic generation of data-flow ips interface. As a reference to data-flow model of computation used to build ips, we introduce the data flow model of interface which basically rely on a data synchronised protocol. We highlight the various parameters that must be taken into account to adapt the data-flow ip to various SoC platform and we validate this high level interface design concept by a complete cycle accurate SoC simulation using the SocLib simulation environment and a high level designed hardware accelerator synthesised with the MMAlpha tool [START_REF] Guillou | High level design of digital filters in mobile communications[END_REF]. We provide many experimental results concerning communication performances for various architecture of the interface. The major conclusion of this work is that optimal communication scheme can be reached only if the interface of the hardware accelerator is master, i.e. contains a dma, and moreover this dma has to have a small degree of programmability: it must be able to execute repeatedly a small sequence of transfers.

Hardware/Software Interface Of Data-Flow IPs

In this section, we precisely identify the context of the work, it implies precise definition of what we call data-flow ip, the schematic architecture of the system on chip we target and the overall principles of the hardware/software interface that we wish to generate.

Data flow IP and SoC environment

In recent SoC design, many processors ips are to be connected on a communication medium which can be a bus, a hierarchical bus or a network. We will refer to this communication medium as the bus even if this work can be applied to network on chip based SoC architectures. The processors are usually initiators, in the sense that they initiates communications. In addition, several other ips are connected on the bus: memory, hardware accelerators, external communication systems, bridge to other buses and so on. In most recent SoC architectures the only hardware to be designed specifically will be some hardware accelerator dedicated to a particular algorithm to be executed on the SoC.

From the external communications point of view, a data flow ip is a black box controlled by data arrival which receives and sends data possibly at each clock cycle. It has a number of input ports and output ports each of which having a certain bit-width. We assume that, in addition to the clock, the ip has a clock enable pin that can freeze the execution of the ip. Hence, if the clock enable is not set, everything behave in the ip as if the clock was not changing. This allow us to define the notion of virtual clock, the virtual clock is the one seen inside the ip, it does not take into account the clock changes that are not validated by the clock enable. Then, we assume that the ip is data synchronised, i.e. at each clock cycle, data are presented on the input port and at the raise of the clock (provided that the clock enable is set), the data is read by the ip. If all the required data are present and the clock enable is set then the ip can run for a cycle which increments the virtual clock counter. We do not assume that there is a hand shake protocol at this level of abstraction. In practice there is a hand shake protocol at a lower level, but it can be abstracted thanks to the virtual clock mechanism.

The target SoC platform is represented on Fig. 1, ips are connected to the bus via the vci interface protocole. vci [START_REF] Risset | Virtual component interface standard (OCB specification 2[END_REF] is a low level point to point protocol standardised by the vsi Alliance and permits to interconnect ips independently of the protocol used by the bus. A mips processor executes a stream-processing like application and uses a hardware ip to accelerate computations. The ip has been generated with mmalpha high level synthesis tool [START_REF] Guillou | High level design of digital filters in mobile communications[END_REF], hence it is named MMAlpha accelerator in Fig. 1.

Hardware/Software Interface Global Scheme

In general we assume that the hardware accelerator will be controlled by a processor (that we call the host processor). Hence the interface of the ip is composed of a software part and a hardware part. The software part will command the data communication between memory and the ip, we call this part the driver. From our experience [START_REF] Derrien | Automatic synthesis of efficient interfaces for compiled regular architectures[END_REF][START_REF] Fraboulet | Cycle accurate simulation model generation for SoC prototyping[END_REF], the communication scheme used to feed the hardware accelerator must respect important constraints so as to obtain acceptable performances: (i) it should try to use a Direct Memory Access module (dma) to perform communication in burst mode, but only when it increases performances; (ii) the designer can set the burst size to balance between hardware cost, communication latency and bus contention. Also, the architecture of the hardware/software interface must be re-usable for many different data-flow ip. It can be envisaged in three main modes depicted in Fig. 1: either the driver on the host processor directly executes all the communications or it simply controls a dma which himself performs the communications between the memory and the ip. The use of this dma can be made much more efficient if the dma is designed specifically to this generic interface control mechanism and is directly connected to the ip as shown on 1-c and demonstrated in section 4. The proposed interface mechanism must be used in various SoC architectures, hence we think that an interface generator tool must be used to generate various versions of the interface depending on targeted SoC parameters, this is detailed in next section.

Generic Interface Generation Principles

In this section we identify the concept that are useful to build an interface generator for data-flow ips.

Communication Activity Abstraction

The crucial point is to abstract the ip communication activity in such a way that it is (i) platform independent and (ii) compact. To be platform independent, one has to identify the communication activity that depends only of the ip. To be compact one must use loop like formalism to express a large number of communication in a very small space. The use of parameters not known at compile time in these loop is mandatory. The theoretical background of our work is based on the polyhedral model which uses polyhedra to abstract loop iteration domains. However, interface synthesis for linear arrays does not need a important knowledge on polyhedra as the only polyhedra manipulated are 1-dimensional.

Figure 2. Graphical representation of input/output on a simple data-flow IP

Consider a very simple example: a hardware module that processes two streams a 1 , a 2 ,. . . and b 1 , b 2 ,. . . (only the input interface is detailed here). The a stream is 16 bits wide while the b stream is 8 bits wide. This ip inputs the first a sample at t = 1 and then one a sample every three clock cycle until N samples have been processed. The t counter corresponds to a counter on the virtual clock of the ip hence we are currently observing the behaviour from inside the module, it is initialised with the reset of the ip. The b stream is input at the same rate (one sample every 3 clock cycles) but starts at t = 5. The ip is represented on the left of Fig. 2, many signal processing filters have the same kind of input/output behaviour: each stream is composed of a sequence of samples arriving at a regular rate. The schedule of the inputs can be graphically represented by the right of Fig. 2, for N = 6. The input interface behaviour has three phases. During the first phase, only a is input, then a and b are input, and finally there is a phase where only b is input. Because of the stream processing behaviour of the application, we can divide each of these phases into the repetitive execution of a motif which corresponds to the consumption of one sample of each stream (right of Fig. 2). We define a motif as a small sequence of steps (here 3 steps) where I/O performed by each port are precisely defined. Here, each sample of stream a is input every 3 clock cycles. Hence, the I/O behaviour on port a can be described as a repetitive execution of a simple motif: one step with input and two steps without input. The motif of stream b has the same length, hence the I/O behaviour during phase φ 2 can be expressed as N -1 execution of a simple motif which is illustrated on the right of Fig. 2. In general the length of the motif of a phase is the least common multiple of the length of the motifs of all the streams involved.

// phase φ 1 for m = 1 to 1 read(a[m]) wait(3) // phase φ 2 for m = 2 to N read(a[m]) wait(1) read(b[m-1]) wait(2) // phase φ 3 for m = N + 1 to N + 1 wait(1) read(b[m-1]) wait(2)
To specify functional behaviour of the ip, the motif index m can be used rather than the virtual clock t. Of course, as we are in the data flow model, there will always be a relation between the motif index m and the virtual clock counter t. For our example, this relation can be expressed as: in phase φ 2 the motif m start its execution at t = 3m -2, this relation can be easily established once the motif has been defined. In addition we need a way to identify which data is concerned with a particular motif m. For that we assume that data input on a particular port are successive elements of a linear array. Any other indexing is possible, however, it should be as close as possible as the memory layout of the corresponding variable in a target SoC.

We gather the phase and motif information into the data-flow interface format presented in Fig. 3 which permits to represent the input behaviour of the architecture of Fig. 2 without assigning a value to N . In these loops, the m index is the motif index or equivalently the number of the sample treated. The virtual clock counter t can be reconstructed using the wait instructions. The instructions have a 0 cycle execution time except the wait() statement whose execution time is the argument. The phases and motifs completely define the communication behaviour of the ip. Any ip whose input/output behaviour cannot be expressed with these concepts cannot be interfaced by our mechanism. Note that it strictly implies data-independent communications, the communication scheme must be statically defined before the computation starts. This data-flow interface format should be parsed by the interface generator. During this process, the polyhedral model can be used to store the internal representation of the phase and motif information. For instance, the virtual clock cycles at which the ip should read on port a are the integers of the following set:

{ 3m -2 | 2 ≤ m ≤ N }. This set is called a Z-polyhedron.
Researches on the polyhedral model [START_REF] Quinton | On manipulating Z-polyhedra using a canonical representation[END_REF] have shown how to store and manipulate these sets without knowing the value of N . Building this set during the parsing of the data-flow interface program of Fig. 3 is easy.

The scheme of the interface mechanism is depicted in Fig. 4, it will be explained in next section. Just note that FIFOs are placed between the bus and the IP to buffer the data. In order to integrate the ip into a SoC, we need some more information, in particular the size of the bus and the size available for the FIFOs used to buffer data before the ip. we define the communication scheme by a succession of communication pattern inside each phase: a communication pattern is the set of data that will be sent to the architecture to feed the architecture during a particular phase. A pattern can gather several motifs in order to take advantage of the bus burst mode. Input pattern and output pattern must be carefully merged taking into account buffering available to avoid deadlocks. On our example, during phase φ 2 , if we have FIFOs containing 20 data of a and b before ip input ports, and assuming that the bus width is 32 bits, we can use the following pattern: send 10 bus-words of a, then send 5 bus-words of data b (remember that b has a twice smaller bit width).

To sum up the important concepts that we have introduced in this section:

• The input/output behaviour of the ip is divided into a finite number of phases. A phase is a period during which communication occurs only on (possibly many) fixed ports. • A phase repeats from one to a very large number of time (possibly fixed at run time) a motif.

A motif has a fixed number of virtual clock cycle. It describes the repeated behaviour of the input and output of the interface for each sample during a particular phase. • A pattern (or communication pattern) is the set of data that will be sent to the architecture to feed the architecture during a particular phase. We are now able to introduce the basic architecture of our interface mechanism. It is represented on Fig. 4 with a maximum burst size of 10 bus words. The hardware part is on the left. The proposed architecture has two target interfaces on the interconnect. These two ports can be reduced to one if simultaneous input and output are not feasible as it is the case when the interconnect is a bus. Data received from the host processor through the bus are de-multiplexed according to the communication pattern of the current phase. The hardware performing this control is a simple automaton parameterised by phases, motifs and communication patterns, we call it the controller. The software driver executed on the host processor is represented on the right. One can see how the patterns are used to write the driver (only input instructions are detailed). The compatibility between the controller configuration and the driver is essential, both should be generated by the same tool. This is the major argument for an interface generator.

Generic Interface Description

The interface generator reads input/output behaviour of the ip expressed in a particular format such as the data-flow interface format presented in Fig. 3 and produces the corresponding hardware controller and software driver. This generator should be able to include many parameters in addition to the ip parameters. For instance, the designer should be able to specify the maximum size of burst allowed, as well as the size of the FIFOs present in the interface generated. A good interface generator should be insensitive to a change of master processor, i.e. it should be easily retargeted to a new assembly langage or interruption handling strategy.

Finally the interface generator should be adaptable to different memory layout of the streams. The difficult part is to make the phase/motif information and the memory layout organisation compatible. In our version, we have assumed that successive data that enters a particular input port of the ip are stored contiguously in the memory. If this is not the case, as for instance for interleaved data in stereo signal processing, and if we still want to use burst access to memory, the interface must merge the memory layout organisation with the pattern information to program the controller. We think that this is very difficult to do in a generic way, hence we propose to generate a communication pattern mechanism interface for a fixed memory layout organisation of each stream, the most common case being the in-order data layout organisation.

Experiments: Cycle Accurate SoC Simulation

Performance results for this particular kind of experiments are very dependent on some target architecture characteristics as for instance the behaviour of the caches. It is now well known that cache behaviour and network congestion are very difficult to predict, hence the only way to validate our interface mechanism is to perform a cycle accurate simulation of the whole system. We have performed these simulations with the SocLib (http://soclib.lip6.fr/) environment and measured the performances obtained with the three main interface modes presented in figure 1, we have also measured the impact of the burst size on the communication performances. The description of the experimental setting is performed in section 4.1, the results are analysed in section 4.2.

Target Platform And Design Methodology

We have chosen to execute a classical audio signal processing application that processes stereo audio files and proposes various simple filters like lp's tick removal. As we mentioned before, we are interested in non-interleaved streams. Writing an interleaved version of the interface would not be very difficult and would only require a modification of the input and output controllers used within the interface. We have added an 8 tap fir filter, a simple convolution with 8 multiplication and 8 additions. We have provided a SystemC module implementing a data flow hardware accelerator for this filter. The target platform that we want to simulate is composed of a processor, a memory, the hardware accelerator connected on a communication medium (see right of Fig. 6).

Simulation of the SoC platform was done in SystemC using the SocLib environment. The main component of SocLib is currently a set of SystemC simulation models for common ips (mips processor, ram, NoC, busses, dma). All these simulation models use vci interconnection standard [START_REF] Risset | Virtual component interface standard (OCB specification 2[END_REF]. These simulation models are publicly available and there exists synthesizable rtl versions of the ips that can be used for the final design. The hardware accelerator was synthesised with mmalpha [START_REF] Guillou | High level design of digital filters in mobile communications[END_REF]. mmalpha is a toolbox for designing regular parallel architectures (systolic like) from recurrence equation specifications expressed in the Alpha language. It is one of the only existing tools that really automates the refinement of a software specification downto rtl description within the same language: Alpha. We have developed a translator from AlpHard (hardware description language, subset of Alpha) to SystemC [START_REF] Fraboulet | Cycle accurate simulation model generation for SoC prototyping[END_REF]. We wrote by hand a SystemC version of the generic interface presented in this paper and we generated from mmalpha the configuration of the controller and the software driver for different parameters of the experiments (size of the burst, different types of interface) etc.

Providing a complete refinement methodology using high level synthesis from a bulk software specification is not easy, we explain here precisely what we did from the original C-code, it is illustrated in Fig. 6. We have extracted from the C-code a function (referred as filter.c) performing the filter, and translated it in Alpha by hand (filter.alpha). Driven by the user, mmalpha will refine this specification downto a hardware description specification in the Alpha language (referred as AlpHard format). At any step of the refinement, mmalpha can generate C-code for simulation. The filter manually translated in Alpha was validated by replacing the original filter.c function by the C code generated from the filter.alpha by mmalpha and testing resulting execution against original program. Then mmalpha generated a systolic version of the filter from which we generated a SystemC simulation model (filter.cpp), and a SystemC file for configuring the hardware interface and the software driver (driver.c). The software driver replaced the original filter.c in the program before its compilation to the mips processor. In the particular instance of the SoC represented in figure 6, there is no dma, this driver explicitly performed all the communications between the memory and the hardware accelerator as did the driver represented on the right of Fig. 4. Hence, on Fig. 6, the box labelled Filter is composed of the generic interface plus the SystemC files generated by mmalpha: interface configuration and filter.cpp.

The hardware components of the platform are: a mips R3000 processor (with its associated data and instruction cache) also referred as the cpu, a standard memory, a component used for displaying output (referred as tty) and the a specific hardware accelerator generated with mmalpha including the interface. All these components are connected via vci ports to a simple network (internal architecture of this network is not precisely simulated, only the latency and bandwidth can be parameterised). All these components are memory mapped, i.e. the mips has access to the input and output ports of the hardware accelerator as two particular memory locations. The software running on the mips, in addition to bootstrapping information, is composed of the C program cross-compiled with gcc to a mips target.

We have written three SoC platforms to simulate the three types of interface illustrated in Fig. 1. In the first platform (Fig. 1-a), the cpu drives all communications: in order to send a data to the accelerator, the software driver running on the mips must read the data in the memory and write it at the memory location of the accelerator I/O ports, this is illustrated by arrows 1 and 2 on Fig. 1-a, this is also what performs the SEND macro of Fig. 4. In this version, the accelerator contains two slave ports: one for input, one for output.

The second platform uses an external dma that can outperform the cpu by using longer communication burst on the interconnect, it is represented on Fig. 1-b. If the dma is parameterised to perform one burst, the behaviour of a SEND is the following: the mips configures the dma, then the dma reads the data in memory and writes it to the hardware accelerator (in burst mode, arrow 1, 2 and 3 of Fig. 1-b), then it raises an interruption to indicate to the mips that the communication occurred. This interruption is a major problem because it takes approximately 380 cycles to be handled by the mips. In order to minimise the impact of the interruption, we have authorised the scatter-gather scheme for the dma: the dma can store more than one burst communication configuration, the number of configuration stored is a parameter of our experiment, this is a classical improvement of dma engines. We are promoting another modification of the dma: because of the very regular nature of our communications (transmitting continuous streams), the configuration of the dma is always the same up to the starting address of the data which is incremented regularly. If we could, for instance implement the loop present on the driver of Fig. 4 inside the dma, we would gain a lot of interruption handling (N/20 in the example of Fig. 4). This can be easily done by providing an additional register in the dma which indicates how many times the configuration stored on the dma must be executed before waking up the cpu. We have implemented this improvement in the simulation model of our dma.

The third platform is simply obtained by putting the dma inside the hardware accelerator. This is a natural improvement, as shown in Fig. 5, it immediately divides the number of communications by two. In this version, the hardware accelerator contains one slave port for configuration by the mips and one master port for initiating communications with the memory (Fig. 1-c).

Experimental Results

In this section we only measured the portion of code composed of the original filter.c. Some performance results are presented in table 1, in this table and in the rest of the section, the term cpu refers to the first platform (Fig 1-a), the term external dma refers to the second platform (Fig 1-b) and the the term internal dma refers to the third platform (Fig 1-c). This table shows an average simulation speed of 50 000 cycles per second, there is no major difference in simulation speed between the three platforms, the only difference is for the loop enable dma platform that is slightly slower due to the activity increase that has to be simulated. We can immediately see the improvement of the internal loop enable dma platform: a throughput of 254 000 samples for 600 000 cycles is obtained. The theoretical maximum throughput that can be obtained is 300 000 samples For the cpu driven platform the cache size has a strong effect on performance. For instance, in Fig. 7, we have shown the influence of cache line size on the frequency at which data could arrive to the ip. The use of cache line of 16 bus word increases the throughput and the effect of a cache miss can be clearly visualised. With cache line reduced to one bus word, the data arrive regularly but slower. On the other hand it can be shown that cache size does not influence performances on this application as cache are direct-mapped. The behavior shown in Fig. 7 clearly indicate that efficient handling of burst mode through a dma module is a crucial issue to obtain an efficient use of the hardware accelerator. However, as it can be seen in table 1, performance for the dma engine are counterbalanced by the interrupt acknowledge mechanism that reduces the gain obtained with burst communications for small burst sizes. This tradeoff quickly turns in favour of the dma platform for burst sizes larger than 70 bus words on our architecture. As soon as the burst sizes counterbalance the interrupt latency the dma platform is more efficient than cpu driven I/O as it can be seen on figure Fig. 8 (ext. dma).

Using an external dma module allows more efficient burst communications over the interconnect but still requires 4 transfers for each samples. The third architecture uses an internal dma that has been implemented directly in the interface. This dma engine allows the interface to directly access the memory to fetch its input samples and to write the results back to the memory in only 2 accesses to the interconnect, reducing the number of data transfers by a factor 2 compared to the external dma platform. Hardware accelerator throughput is not changed by using an internal dma for small burst sizes as the main bottleneck is still the transfer of dma configurations and interrupt handling. Hardware throughput for internal dma is shown on figure Fig. 8 (int. dma(1)).

The next architecture modification we have made is to use a scatter/gather enabled dma engine that can store several successive transfer configurations. This list reduces the number of interrupt that are generated by the dma. For instance, a list size of n configurations allows to reduce by a factor n the number of interrupt acknowledge handled by the cpu. Performance improvements can be seen on figure Fig. 8 for several list size varying between 1 and 1024 configurations (int. dma(1 --1024)). Even when using big list sizes, performances ares still not at the maximum throughput, the cpu still has to perform configuration transfers using the bus. The more configuration the dma can store, the more transfers have to be done between two successive run of the accelerator. These inactivity periods occurring between burst mode computation phases introduce some extra latency that freezes the hardware pipeline during reconfiguration and have to be taken into account for realtime processing that have strict timing or jitter constraints on the data streams. Furthermore, the performance improvement is limited by the configuration transfers and we can observe a maximum performance between 256 and 512 configuration list sizes followed by a performance decrease for bigger lists. This performance decrease comes from the latency introduced by long configurations that cannot be fully completed during the 600 000 cycles of the simulation.

The last architecture we simulated overcomes the configuration problem by storing and transferring the complete configuration to the internal dma using a compact representation. This configuration represents the phases and motifs discussed in section 3. The loop enable dma that we use in the architecture can perform the complete processing transfer without requiring interrupt for configuration transfers. This communication mode is close to the maximum theoretical throughput even for small burst sizes and is thus limited only by the interconnect bandwidth and memory performances. Furthermore, this high throughput is obtained for small burst sizes and allows to keep latency and jitter to a minimum compared to similar performances obtained with other solutions using big configuration lists. The performance results of Fig. 8 clearly demonstrates that the loop enable dma is mandatory to reach interesting performances with a data-flow ips on a SoC.

Related work

Many recent works present SoC simulation environments [START_REF] Loghiy | Analyzing on-chip communication in a MPSoC environment[END_REF][START_REF] Bolado | Platform based on open-source cores for industrial applications[END_REF][START_REF] Jang | High-level system modeling and architecture exploration with systemc on a network SoC: S3C2510 case study[END_REF]. These approaches do not have an Open Source policy as the one of SocLib, their main concern is the acceleration of the simulation at various level of precision: transaction level or cycle accurate level. These works do not propose generic interface mechanism for ips. Some attempt have been made to abstract communication behaviour at high level [START_REF] Chandras | An interconnect channel design methodology for high performance integrated circuits[END_REF] or at low level [START_REF] Silva | Synchronous protocol automata: A framework for modelling and verification of SoC communication architectures[END_REF][START_REF] Shin | Fast exploration of parameterized bus architecture for communication-centric SoC design[END_REF][START_REF] Banerjee | A power and performance model for networkon-chip architectures[END_REF], but none of these approaches use the assumption that the ip are in the data-flow model hence they propose solutions which are not optimised for stream processing.

Many of the interesting results in this field are based on the work of the Ptolemy project [START_REF] Lee | Overview of the Ptolemy project[END_REF] and especially the introduction of various computation models for data-flow ips: process network [START_REF] Kienhuis | Compaan: Deriving process networks from matlab for embedded signal processing architectures[END_REF] or sdf [START_REF] Williamson | Synthesis of parallel hardware implementations from synchronous dataflow graph specifications[END_REF][START_REF] Jung | Efficient hardware controller synthesis for synchronous dataflow graph in system level design[END_REF]. An interesting theory has been developed for multi-rate ip-based systems [START_REF] Horstmannshoff | Mapping multirate dataflow to complex RT level hardware models[END_REF], but the problem solved is the interconnection between several data-flow ip while we specifically target a single data-flow ip controlled by a host. The work presented here has its roots in the research on the mmalpha system [START_REF] Derrien | Automatic synthesis of efficient interfaces for compiled regular architectures[END_REF][START_REF] Derrien | Interfacing compiled FPGA programs: the MMAlpha approach[END_REF], a very similar problem was studied by Park and Diniz [START_REF] Park | Synthesis of pipelined memory access controllers for streamed data applications on FPGA-based computing engines[END_REF][START_REF] Park | Synthesis and estimation of memory interfaces for FPGAbased reconfigurable computing engines[END_REF] leading to the design of a generic interface that can be parameterised to connect to different data-flow ip with some constraints on the ips. This approach does not assume that communications are known statically and propose a run-time resolution to solve conflicting access to the bus.

Several high level design tools are now clearly identified either as research prototypes or industrial products [START_REF] Guillou | High level design of digital filters in mobile communications[END_REF][START_REF] Casseau | Architectural synthesis of digital processing applications dedicated to submicron technologies[END_REF][START_REF] Schreiber | High-Level Synthesis of Non Programmable Hardware Accelerators[END_REF][START_REF] Hounsell | Co-processor synthesis a new methodology for embedded software acceleration[END_REF][START_REF] Kienhuis | Compaan: Deriving process networks from matlab for embedded signal processing architectures[END_REF][START_REF] Bednara | Automatic synthesis of FPGA processor arrays from loop algorithms[END_REF], each of these tools have implemented ad-hoc communication protocol between the generated data-flow ip and the host. The Pico [START_REF] Schreiber | High-Level Synthesis of Non Programmable Hardware Accelerators[END_REF] tool and the Paro tool [START_REF] Bednara | Automatic synthesis of FPGA processor arrays from loop algorithms[END_REF] have in house interface mechanisms with dedicated solution for the problem exposed here. We expect our model to be usable at least by mmalpha and Gaut [START_REF] Casseau | Architectural synthesis of digital processing applications dedicated to submicron technologies[END_REF].

Conclusion

In this paper we have delimited a class of architecture that is subject to high throughput requirement and restricted enough to allow an interface mechanism which is generic and efficient. The notion of phase, motif and pattern can be defined for many data flow ip and are particularly useful for high level design tools that can use them to generate hardware and software interfaces together with the ip.

The cycle accurate simulation environment that we use is much more accurate than theoretical estimation of throughput because cache behaviour and interruption handling are very difficult to predict. We have highlighted an important issue: a very important improvement in the throughput between the memory and the ip can be obtained with a slightly optimised version of scatter-gather dma that we called loop-enable dma. We have shown that the hardware/software of the interface can be generated automatically together with the ip and quasi-optimal communication throughput can be reached.

Figure 1 .

 1 Figure 1. The three main interface modes: (a) CPU driven, (b) external dma and (c) internal dma engine

Figure 3 .

 3 Figure 3. Data flow interface format used for specifying input/output behaviour of the IP of Fig. 2

Figure 4 .

 4 Figure 4. Hardware and Software interfaces for the Data-flow hardware accelerator of Fig. 3. Controllers must be configured according to communication patterns used in the software driver on the right hand side.

Figure 5 .

 5 Figure 5. Hardware DMA interface implementation using a single data port for the Data-flow hardware accelerator of Fig. 3.

Figure 6 .

 6 Figure 6. The SoC simulated and the global design methodology. Square boxes represent SystemC models of ips.

Effect of different size of data cache lines (1 bus word and 16 bus word) on the arrival of data to the ip

  .for 600 000 cycles, indeed each sample is 16 bits wide, there are two sample stream which must be at least read once from the memory and write once to the memory, hence with a memory answering in one clock cycle and a bus width of 32 bits we cannot compute more than 300 000 samples for 600 000 cycles. The internal loop enable dma version is nearly optimal. There is no major difference between the cpu version and the dma version because the improvement provided by the burst of the dma is counter-balanced by the overhead of the dma interruptions.

	SystemC.CLK
	SystemC.CACHE_1_WORD.DATA	308	310	312		314	316	318
	SystemC.CACHE_1_WORD.WRITEOK
	SystemC.CLK
	SystemC.CACHE_16_WORD.DATA	316 318 320		322	324 326 328 330 332 334 336 338 340 342
	SystemC.CACHE_16_WORD.WRITEOK
	Figure 7. cpu	ext. dma int. dma int. dma w/ loop
	complete simulation time (seconds)		10.91	12.82	10.91	18.26
	complete simulation cycles		600000	600000	600000	600000
	simulation speed (cycles/seconds)		54995.5	46802	54995.5	32858.8
	hardware pipeline throughput (samples)	16861	10561	9601	254041

Table 1 . Performances obtained from the complete SoC simulation for burst size of 30 samples and different hardware configuration

 1

Hardware accelerator throughput according to different burst length and cpu or dma communication mechanism

		300000
	samples processed during simulation (600 Kcycles)	50000 100000 150000 200000 250000						cpu ext. dma int. dma (1) int. dma (2) int. dma (256) int. dma (512) int. dma (1024) int. dma (loop)
		0	0	50	100	150	200	250
					software driver communication granularity (burst size)
	Figure 8.


Mena B Lafkioui

Postposed topic specification across the Sahara. An areal phenomenon

Keywords: Areality, Contact, Contrast, Grammaticalisation, Sahara, Topicalisation

In the present study, I argue that post-posed topic specification (PTS) across the Sahara is an areal phenomenon and that in the case of Southern Tamazight (i.e., Tuareg and Zenaga) it is an innovation generated by pattern replication. On the other hand, the required matter for PTS formation in Southern Tamazight is generally provided by Tamazight itself by means of system-internal developments involving the following predominant grammaticalisation track, that is, [*modality markers > topic specifiers]. I also show that full convergence has taken place in these Southern Tamazight languages, which has affected their linguistic typology on the morphological, syntactic, and pragmatic level. Moreover, the study accounts for the significance of the functional parameter of contrast in the development of these topic specifiers and hence confirms the importance of system-based factors in language change.

Introduction

Although quite some languages distinguish specific topic markers, their study has been largely overlooked in linguistics, despite their pragmatic significance, as they facilitate discursive coherence and dynamics. Indo-European examples of such markers are for instance the English "as regards", "as for", "concerning", the French quant à, pour ce qui est de, concernant, and the Spanish, en cuanto a, respecto a, por lo que toca a, which generally occur in sentence-initial or clauseinitial position. These markers add semantic and pragmatic values to the topic's referent by specifying its general content or by creating more contrast between its properties and that of the previously instantiated topic. Combined with a proper intonation pattern -generally engaging prosodic prominence -they clearly demarcate the topic from its relating comment. They may also serve to introduce new topics into the discourse or to reintroduce previously mentioned ones.

These markers are coined as "topic specifiers" in [START_REF] Mena | Preposed topic specification in Berber: An innovation induced by contact with Arabic[END_REF], where they are investigated in detail for the major languages of North Africa, i.e., Tamazight (language family and branch of Afroasiatic, also called Berber) and Arabic (Semitic). The latter study shows that Northern Tamazight distinguishes "preposed topic specifiers", which were engendered by contact with Arabic, from which Tamazight replicated the grammatical pattern and borrowed certain material, with or without processing it. In certain Northern Tamazight languages, such as Taqbaylit (North Algeria), this contact phenomenon has led to full convergence through the systematic usage of dedicated preposed topic specifiers based on Tamazight material, such as in example (1) with ma-d as the topic specifier. Furthermore, Lafkioui's study on preposed topic specifiers shows that the functional factor of contrast is predominant in the creation of these pragmatic markers and so confirms the significance of system-based factors in language change.

(1)

[ma d aqcic,]T tebbwi-t yid-es 1 'As for the boy, she took him with her.' (Dallet 1982: 476) Even if preposed topic specification markers are observed in Tamazight, they are not widespread and they are mostly optional. In fact, topicalisation in Tamazight is primarily marked by an intonation dislocation, which generally involves an intonation break [START_REF] Lafkioui | L'intonation et ses fonctions syntaxiques en rifain[END_REF][START_REF] Lafkioui | Intonation et topicalisation en berbère. In Parcours berbères[END_REF]. Other -subsidiary -parameters that de-termine the marked noun phrase topic are the independent noun state and fronting, with a left periphery predilection. Prosody also perfectly meets the needs of contrast demarcation in Tamazight. Even more so, prosodic prominence is required when topics are contrasted [START_REF] Lafkioui | La topicalisation en berbère: formes et structures[END_REF][START_REF] Lafkioui | Topicalization in Berber: A Typological Perspective[END_REF][START_REF] Mena | Preposed topic specification in Berber: An innovation induced by contact with Arabic[END_REF].

In Tuareg (Southern Tamazight), preposed topic specification markers are quite rare and often based on the conditional marker ku 'if' and its grammaticalised counterpart ku-d (and variants). Written proof of these markers goes back to the 19 th century [START_REF] Hanoteau | Essai de Grammaire de La Langue Tamachekʹ[END_REF], where ku-d is categorized as a conjunction meaning 'as for', like in (2).

(2) ku terham eg'let [ku-d nek]T ad ek'k'imer' 'Go if you like, as for me, I will stay.' (Hanoteau 1896: 123) As is displayed in (2), it is the composite and grammaticalised form ku-d (compared to ku) that plays the role of topic specifier, which highlights the contrastive semantic load of the topical referent it precedes. The same formal-functional logic attested in Taqbaylit (North Algeria) for ma as a conditional marker (among other functions) compared to ma-d as a topic specifier is attested in Tuareg, where ku, as a conditional marker (mainly), is in complementary distribution with ku-d as a preposed topic specifier.

Postposed topic specification markers (henceforth PTS) also occur in the world's languages but again are barely studied. They are commonly employed in African languages, including in the languages of the Sahara (North and Northwest Sahel included), where they are profusely developed. The following are examples of PTS markers expressed in two Afroasiatic languages of this region; example (3) stems from Tuareg (Southern Tamazight), while (4) stems from Hausa (Chadic).

(3)

[tagăyt-za,]T ḳannăn dăɣ-ăs ăṛătăn ăggôtnen 'As for the Doum palm, they make a lot of things out of it.' (Prasse & al. 2003: 871) (4)

[Kànde fa (…),]T mun fi sôntà 'As for Kande, we like her the most.' (Newman 2000: 616) From a comparative Tamazight perspective, the Southern Tamazight languages -i.e., Tuareg mainly (Sahara, North, and Northwest Sahel) but also Zenaga (Mauritania) -are quite exceptional, as they provide evidence of the systematic use of PTS markers. These latter markers are generally absent elsewhere in Tamazight or not developed into "dedicated" pragmatic markers. The present study aims at explaining where PTS in Southern Tamazight originates from by means of the following diachronic scenario; that is, Southern Tamazight (predominantly Tuareg and Zenaga) would have been subject to innovation triggered by system-external factors (i.e., areality) that are not only responsible for the introduction of new distributional variants for topic specification but also for the success of their diffusion in the contact area (i.e., the Sahara), where PTS is commonly attested. The morphological material of the Tamazight PTS variants, however, is in certain cases of Tamazight origin. In other words, the study will account for the areal nature of the phenomenon of PTS by showing how Southern Tamazight, and especially the Tuareg languages, which are important lingua franca's in the Sahara, have replicated the distributional template of PTS common in this linguistic area, yet without necessarily borrowing the specific morphological material, for which it is also contingent upon its internal system. PTS in Southern Tamazight has reached full convergence due to the systematic use of certain Tamazight-based variants.

In the following section 2, I will show how PTS works in Southern Tamazight. Section 3 will account for the syntactic replication of post-placing topic specifiers in Tuareg and Zenaga, as the borrowing languages, from those languages with which they are in close contact in the Sahara (mainly in Niger, Mali, Northern Burkina-Faso, and Mauritania) and for their various pragmatic purposes relating to topic and contrast marking. Section 4 will discuss cases based on Tamazight morphological material, which chiefly pertain to modality. The article will end with a number of areal linguistic conclusions.

Postposed topic specification in Southern Tamazight

Postposed topic marking is a specificity of Southern Tamazight, and particularly of Tuareg and of Zenaga, where it is commonly attested. Tuareg accounts for za and dăɣ/da (and variants, including suffixes) as the main PTS markers, like in ( 5) to (7) from Tamajeq (Tuareg of the Ayer region, Niger).2

(5)

[năk-za]T wər-əleɣ măwta 'As for me, I do not have a car.' [START_REF] Prasse | Dictionnaire touareg-français (Niger): tămăžəq-tăfrănsist (Niger)[END_REF] All PTS markers of these examples serve the purpose of contrast, even though the topics vary in terms of morphosyntax, e.g., a pronominal subject-topic ( 5), a NP subject-topic ( 6), and an adverbial clause as circumstantial-topic ( 7), respectively. PTS markers usually combine with all sorts of topics. Yet, Tamasheq (Mali) has also developed the particular PTS ǝ ntɑ, which corresponds to the invariable 3SG independent pronoun, and which only combines with independent personal pronouns as topics (except for the 3SG). Example (8) testifies to this: nae kk (1SG independent pronoun) is the topic, which is marked by ǝ ntɑ (PTS < *3SG independent pronoun).

_________________________

[nae kk ǝ ntɑ]T ǝqqǐm-aeγ-ǝ dd 'As for me, I stayed' (Heath 2005: 615) In Zenaga, regular dedicated PTS markers are for instance ha, exemplified in (9), and (i)ṣṣa, exemplified in (10). The latter PTS fulfils varying and complex discursive functions in Zenaga, as well as in Hassaniyya Arabic (Mauritania and Sahara), where it is also commonly attested as a PTS, like in ( 11 Just as in Tuareg, the Zenaga and Hassaniyya PTS markers are typically employed to create more contrast between the semantic and pragmatic properties of the topic at hand and those of the previous topic as well as to emphasize them. PTS is also recorded in coordinated NP sentences, as in (12) from Tamajeq (Tuareg, Niger). Here, strong contrast is marked by using two different PTSs, respectively za and da.

(12) [Mokhamməd za]T eggur [Fatimata da]T tamarwalt 'So Mohammed, he was the jackal. As for Fatimata, she was the hare' (Petites soeurs 1974: 47/3) Emphasis or other pragmatic purposes such as inter-subjective (inter-personal) investment or distance, as well as narrative purposes like enhancing the dynamics of the described actions may also be prominent, such as in (13) from Tamajeq.

(13) [ash isla ǝmnokal ǝnki]T1 [arwada da]T2 isshot-as ehǝre wa yogǝlǝn ǝnki 'When the king heard this saying, even more, he gave him even more herd.' (Petites soeurs 1974: 153/63) This sentence contains two topics. The first one, ash isla ǝmnokal ǝnki 'when the king heard this saying', is a circumstantial topic and is not marked by a PTS. On the other hand, the second circumstantial topic, arwada, and more particularly its semantic notion of "even more", referring to the previously mentioned discursive object of "wealth" as well as to the currently mentioned "herd", is stressed by the PTS da, so as to render the idea of "unbelievable and unconceivable amounts of wealth".

The marker da as well as its allomorph de also function as pragmatic sequence markers in Tuareg, mostly to indicate the boundary of an information/intonation minimal unit or the end of the whole sentence or discursive paragraph, to which testifies (14) from Tamajeq (Niger). The first da in ( 14) marks the circumstantial topic and so foregrounds the setting wherein in the ensuing comment takes place. The second da, on the other hand, is not a PTS but marks the end of the complex sentence and that of the event it describes. ( 14) [as d-yosa iga afus-net da]T wǝr t-illa ar goro iyǝn da 'When the young man arrived, he put his hand (in it), and there was just one cola.' (Petites soeurs 1974: 157/16)

The pragmatic markers da and de may also be combined, like in (15) from Tamajeq, where de closes up the sentence, while da creates contrast between the topic ǝnta 'he' and the topic amnokal 'king' of the preceding clause.

(15) [amnokal]T ikk-e-du [ǝnta da]T issǝlkǝḍ i ǝmnokal ad d-ǝmmǝnǝyǝn de 'The king, he went to him. And he, he (also) went to meet the king, until they met.' (Petites soeurs 1974: 149/51)

Remarkably, Tuareg also allows to insert a PTS into a propositional and thus composite topic, such as the determinative clause barar wa n arigullan 'this child of Arigullan' in the following example (16). The PTS not only underlines here certain referential properties of the speech part it follows, i.e., the properties of being barar 'child', but also puts these properties in contrast with those of the subsequent topic adǝlâsǝgh (proper noun), which bears no PTS. In example ( 16), it is not only the properties of the two boys that are contrasted and highlighted -those of Arigullan's son compared to Adelasegh -but also the fact that Arigullan's son is still a little child (barar). A similar pragmatic strategy is observed in next extract (17) from Tamajeq (Niger), but here the items put in contrast are part of one sole composite topic, i.e., amǝddǝrghǝl ǝnten ǝnǝbdǝn 'the blind and the cripple'. In the following section 3, the areal nature of the PTS constructions discussed above will be accounted for.

It is always challenging to distinguish the phenomena that are the result of shared genetic archaisms from those that result from convergence due to an extended period of geographical proximity. Although this challenge also applies to the phenomenon of PTS, there is much evidence that points to its areal nature, regarding its syntactic at least. As is shown in section 2, only Southern Tamazight distinguishes PTS. Therefore, PTS' geolinguistic distribution does not corroborate an ancient genetic origin of the phenomenon. If it were a proto-Amazigh feature, one would expect to find at least some remnants in certain peripheral zones of Amazigh-speaking North Africa, which is not the case.

Moreover, Afroasiatic, the language phylum to which Tamazight belongs, does not provide conclusive proof of common genetic reflexes. Afroasiatic displays all kinds of devices for topic specification, including preposed, interposed, and postposed markers. Much variation in topic specification is also observed within the different language families. For instance, in Semitic, topic specifiers are preposed in (Moroccan) Arabic ( 18) and postposed in Amharic ( 19).

(18) [hiyya(,)]T gǝlsǝt, [ǝmma huwwa(,)]T ma ṣbǝr š.

'She, she sat down, as for him, he could not bear to be patient' [START_REF] Mena | Preposed topic specification in Berber: An innovation induced by contact with Arabic[END_REF])

(19) [lïjj-u-nï-mma]T yï-wädd-äw-al.
'(There is no question) as for his child, he likes him.' (Demeke and Meyer 2007: 27) Consequently, the areal origin of PTS in Southern Tamazight is the likeliest, also because the Tuareg languages are important lingua franca's of the Sahara. Tuareg is in regular contact with languages of different families belonging to the following three African phyla: Chadic of Afroasiatic (the same as Tamazight), Songhay of Nilo-Saharan, and Fula of Niger-Congo. Among these languages, Hausa (Chadic) is the main contact language of many Tuaregs, as it is another important lingua franca of this region, alongside Arabic. Wolof (Niger-Congo, Atlantic) is an important contact language for Zenaga-speaking people (Mauritania).

Hausa makes extensive use of PTS for various pragmatic purposes. As a matter of fact, the topic in Hausa is set off by a PTS and/or an intonation marker, except in interrogative and exclamative sentences. PTS markers in Hausa generally relate to modal particles without vowel lengthening, such as for instance dai 'indeed', fa 'well', kàm 'really', kùwa or kò 'moreover', but also to all kind of expressive material (Newman 2000: 615-621). Evidence that accounts for this is given in ( 20) and (21). The latter example contains different PTS markers at once to put emphasis on the topicalised item.

So, the languages of the Sahara (including the North and North-West Sahel) with which Southern Tamazight (Tuareg and Zenaga mainly) interacts on a regular basis -that is, Hausa, Songhay, and Fula -clearly account for PTS, which is often combined with fronting. Even Hassaniyya Arabic attests to PTS in this area, which is remarkable, as the Arabic varieties typically use "preposed" topic specifiers, if at all [START_REF] Mena | Preposed topic specification in Berber: An innovation induced by contact with Arabic[END_REF]. It is also worth reminding that Southern Songhay follows the areal PTS line, whereas Northern Songhay prefers fronting and preposed topic specification, which is in line with Northern Tamazight.

Taking into consideration all these findings and those discussed in previous section 2, it is more than reasonable to regard PTS as an areal phenomenon that triggered the replication of a grammatical pattern in Southern Tamazight (mainly Tuareg ad Zenaga), which is absent elsewhere in Tamazight. The fact that there is no evidence pointing to a system-internal development or to genetic inheritance, on the Tamazight or Afroasiatic level, only adds to the likelihood of the areal basis of PTS. Language contact due to areality has most probably triggered PTS in Hassaniyya Arabic, too.

Another reasonable inference is that areality may have impeded the further development of preposed topic specification in Southern Tamazight (especially in Tuareg), where it is marginal compared to PTS. Indeed, the attested material for preposed topic specification in Tuareg is not only scarce and outdated but also not quite developed into dedicated markers. Areal pressure, engaging the management and development of multilingual repertoires fitting the area of contact, may thus explain Southern Tamazight's shift from preposed to postposed specification. Interestingly, the opposite contact scenario, involving a shift from postposed to preposed topic specification, with or without material borrowing from Tamazight (or Arabic), is recorded in Northern Songhay, such as in Kwarandzyey (Algerian Sahara), which is under strong influence of Northern Tamazight. Tadaksahak (Northern Songhay), on the other hand, which is used more Southwards in the Sahara (Mali), accounts for an in-between scenario. Tadaksahak would have maintained the areal postposed pattern but borrowed some of its material from Tamazight; a potential borrow from Tamazight is the marker dá, which will be addressed in next section about the morphological origin of the primary PTS markers in Southern Tamazight.

Most "dedicated" PTS markers in Southern Tamazight relate to modality, often to conditional markers (see e.g., Prasse et al. 2003: 357;[START_REF] Sudlow | The Tamasheq of North-East Burkina Faso: Notes on Grammar and Syntax. Including a Key Vocabulary[END_REF]Sudlow : 33, 2009: 185): 185). This is in line with the findings concerning preposed topic specification in both Southern Tamazight and elsewhere in this language family [START_REF] Mena | Preposed topic specification in Berber: An innovation induced by contact with Arabic[END_REF].

The primary PTS markers attested in Tuareg are da/dă/dăɣ and their variants, which may occur as adverbs or may be amalgamated as clitics to the topic they follow and often emphasize. Emphasis is an important discursive function of these markers, which is clearly observable with dăɣ and its variants. For instance, in Tamasheq (Tuareg from North-East Burkina Faso), the conjunction kud 'if' and its composite variant kud ... dăɣ 'even if', which contains the emphasis marker dăɣ, are used for hypothetical purposes (Sudlow 2001: 331). The same findings are attested for Tamajeq (Tawellemmet and Tayert) from Niger, which distinguishes the conjunctions ku, kud 'if' and their composite variants kud-dăɣ, kuddă and kudda 'even if' (Prasse et al. 2003: 357). Tuareg also employs the anaphoric clitic -dăɣ (and variants), which in Mali is usually associated with a demonstrative and serves as an intensifier, e.g., w-a-dăɣ 'this same one we were talking about' (Heath 2005: 240).

Taking into consideration these findings and the fact that the markers dăɣ and its variants occur in similar forms with similar modal functions all over the Tamazight language family, even in languages that are geographically distant and typologically different from Tuareg (see examples 29 to 30), one can confidently infer that they have a morphological Amazigh origin. Consequently, PTS markers like dăɣ would be the outcome of system-based developments out of modality markers. The latter markers would have been developed into specific referentialmarking devices, which would have led to PTS following the diachronic path displayed in (28). A Tamazight origin probably also applies to za, another primary PTS marker, whose variants (e.g., sa, zi, si) are recorded in various Tamazight languages. Instances of it as a modality marker are even retrieved in Tamazight's ancient texts, such as those of old Tashelhiyt (South Morocco). For example, the modality marker za is attested in the text of M. Awzal (d. 1749, Ocean of Tears, Islamic Verse; dogma & practices) as an adverb (za/a), which may occur as a clitic -just like with the PTS -in the conglomerate forms iγ-za 'if… nevertheless' and iniza 'if… nevertheless', where it adds modal values (e.g., still, nevertheless) to the conditional 'if '. Next example (31) Concerning Zenaga Tamazight, the regular PTS ha is most likely of Amazigh origin, in terms of morphology, and relates to the presentational. It occurs in Northern Tamazight as well, but as a "preposed" topic specifier (see Lafkioui 2018 for more detail); example (32) from Mzab (Algeria) illustrates this. The fact that Zenaga postposes the marker ha corroborates PTS as an areal phenomenon, as far as its syntactic pattern is concerned. It also testifies to the great areal pressure to which the languages are subject in the Sahara. So, areality would have caused the change in word order in Zenaga by substituting the typical preplacement of ha by its postplacement, as is shown in (33).

(32) [ha nəšš,]T w-a yi tərgibəm na?

'And as form me, you haven't seen me, have you?' (Delheure 1984: 73) (36) [bāba ha,]T war-t uθ̣ ra-g d-aṣṣ-að̣ 'As for Bāba, I didn't see him today.

(Baba Horma, Zenaga)

Another common PTS in Zenaga -as well as in Hassaniyya Arabic -is (i)ṣṣa (see example 10), which reveals divergent and complex discursive functions. Its origin is unclear, although it is recorded elsewhere in Tamazight (e.g., Tarifit, North, Northeast, and Northwest Morocco). A thorough study of this marker within its variable discursive contexts in Zenaga and in Hassaniyya -and compared to other Tamazight languages -is needed but out of the scope of this study.

Conclusion

In view of the findings presented in previous sections, one can positively conclude that PTS across the Sahara is an areal phenomenon, which triggered a specific pattern replication in Southern Tamazight (i.e., Tuareg, Zenaga) that marks the topic by means of postplaced devices. The morphological material of the PTS markers, on the other hand, is usually of Tamazight origin. In other words, PTS in Southern Tamazight is an innovation generated by contact through pattern replication. The necessary matter commonly stems from Tamazight, as it is also retrieved in geolinguistically and typologically diverse languages of this family. Moreover, the development of PTS markers primarily follows a parallel grammaticalisation path, i.e. [*modality markers > topic specifiers]. Remarkably, this same modal diachronic path is also attested for preposed topic specification in Northern Tamazight [START_REF] Mena | Preposed topic specification in Berber: An innovation induced by contact with Arabic[END_REF]. Consequently, full convergence has come about in Southern Tamazight. A set of dedicated PTS markers based on Tamazight material are commonly used for various discursive purposes engaging topic, contrast, and emphasis marking. Most PTS instances strongly involve the expression of contrast, as was shown in previous sections. Contrast is also the leading factor in the development of preposed topic specification in Northern Tamazight [START_REF] Mena | Preposed topic specification in Berber: An innovation induced by contact with Arabic[END_REF]. Accordingly, contrast marking seems to facilitate borrowing [START_REF] Matras | Utterance Modifiers and Universals of Grammatical Borrowing[END_REF]. Note that the requirement for denoting increased contrastive semantic loads in Tamazight generally goes together with other func-

(

  16) [barar za wa n arigullan]T ifrag tekle, amǝr [adǝlâsǝgh]T abǝbbi a tu-tǝga tǝklit. 'As for the child of Arigullan, he, he could walk, whereas Adelasegh, he was worn by the servant astride her back.'(Aghali & Drouin 1979: 52/15)

(

  17) [amǝddǝrghǝl da ǝnten ǝnǝbdǝn]T ǝglǝn [...] 'The blind and the cripple, meanwhile, they left.' (Petites soeurs 1974: 169/27)

(

  28) modality adverb > modality clitic > emphasis clitic > PTSCases in point attesting to the occurrence of dăɣ and its variants with similar functions in different Tamazight languages are presented in (29) and (30).(29) idda-d diγ 'He came again' (Amaniss n.d.: 43; Tamazight of Central Morocco) (30) daγ keçç… 'You again...'(Dallet 1982: 148; Kabylia, North Algeria)

  ), for instance.

	(9)	[niˀk ha]T uɣjay-ak away in uθ̣ nagan.
		'As for me, I forget the language of Zenaga.'
		(Baba Horma, Zenaga)
	(10) [niˀk iṣṣa]T ma kint að̣ mag.
		'As for me, I didn't think.'
		(Baba Horma, Zenaga)
	(11) [minattu ṣṣa]T naˁrafha 'āna
		As for Minattu, I know her.
		(Baba Horma, Hassaniyya)

  accounts for this.

	(31) iġ-za yusy ajmil [...]
	'If one is nevertheless grateful to [...]'
	(Van den Boogert 1996: 294)

Alongside the PTS marker za, Tuareg of Burkina Faso (i.e., Tamasheq) also has iš as a morpheme expressing the same notions(Sudlow 2009: 185). Unfortunately, no examples of both morphemes are provided by Sudlow. Evidence of the suffix -dăɣ is also attested in this area, where it functions as an emphatic marker meaning 'this very, this same'(Sudlow 2001: 112).