Mathieu Valette

When Humanities scientists are writers, their theories can be considered as text. Our purpose is to discuss the consequences of this claim, sketching out a methodology based on text semantics and corpora linguistics. In a certain way, we hope to continue European philological tradition. Our analysis is based on a 1,600,000-word corpus made up of conferences, books and articles written by French linguist Gustave Guillaume (1883-1960). After a brief epistemological introduction, the paper will focus on three topics: (i) the correlated evolution of lexicon and conceptual systems during the inception of theory (from philosophical speculation to scientific theory); (ii) linkage between lexicalisation and conceptualisation by means of morphemic variations and lexical creativity (concept of "act" and its derivations) ; (iii) recourse to trope analysis to characterise and define a concept regardless of the scientist's aim (concept of "mechanism").

1. Introduction 1.1. In the Humanities, theory is most of the time outlined with texts: papers, books, conference presentations, lectures etc. The scientist is first a reader and a text producer. But this imperative textuality is so ordinary that it is almost invisible, and so not problematised. Moreover, theories are generally read as synchronic systems, or even achronic systems, depending on their specific purposes (describing one fact, explaining one phenomenon...). Scientists appropriate models and concepts like tools; they have to know their function and how to manipulate them, but they do not care about knowing practical details of their enunciation. Actually, they ignore them, more or less. Moreover, they find such details embarrassing, because they make concept borders fuzzy. Lexicons, glossaries, and also handbooks, as they extract the concepts from their context, and standardise the definitions, give illusion of stability and tangibility. But concept textuality has necessarily an incidence, not only on interpretation, but also on theorisation. If the scientist is a text producer, then theorisation is the construction of meaning. Theorisation is forced by enunciation, and scientific works, beyond their materiality, can be considered as text. 1.2. The textual aspect of scientific works had been noticed by those in Europe looking at epistemological culture, and especially the French. In this respect, French philosopher Michel Foucault's works, in the 1960s, must be noted (see for instance Foucault 1969). Actually, he put in place a discourse philological analysis centred on the combination and evolution on specific discursive structures. His purpose is, first, to recognise discursive formations, i.e. stabilised relations, regularities between objects, types of enunciation, concepts and themes; then, to recognise breakpoints in idea system history.

Foucault followed famous predecessors' examples, as Georges Bachelard's, Georges Canguilhem's and Martial Gueroult's. Bachelard's notion of Epistemological break, or Canguilhem's notion of concept shifts shows, for instance, the history of one concept is not that of its increasing rationality and refinement, but that of the different fields in which they have been designed and validated. As for Martial Gueroult, he is maybe the first to take into consideration textual determination of scientific and philosophical works. 1.3. In a certain way, what we will call electronic epistemology is a linguistic approach of this French epistemology. Our purpose is the study of scientific texts using corpus linguistics tools which has been developed for the 30 last years and using also a powerful linguistic methodology: François Rastier's interpretative semantics (see Rastier et al. 2002). With linguistic engineering and interpretative semantics, we have tools and methodology Foucault did not have, among other things because some textual phenomena still are invisible with a classical philological analysis, like, for example, lexicon evolution, which depends on the reader's subjectivity. Concept emergence, concepts' individual and inter-related evolutions, the appropriation of a specific thematic, palinode etc.; all these pieces of information are very useful to understand scientific ideas' genesis, and they can rise from a computer-aided analysis much more easily than from a classical one. 1.4. Our purpose will be to study the development of theory on a defined corpus, of determined authors. Until now, we worked on the writings of French linguist Gustave Guillaume (1883-1960). They are actually typical: built during almost half a century (from 1919 to 1960), they came from a famous author, well-known for his theoretician's qualities all over the world, and among others philosophers like Merleau-Ponty, Deleuze or Ricoeur. Furthermore , the writings are very large and almost entirely digitised. Our electronic corpus is close to 1,600,000 words. It is compounded of 2 books (1919 and 1929), 20 papers (from 1933 to 1958), and written and complete texts from 22 years of weekly lessons, i.e. about 450 lectures (from 1938 to 1960). We have added to this a hand-written corpus consisting of drafts ands dissertations. Thus, it is possible to follow with a high precision the theoretician's train of thought, week after week. Through this author, we shall study below three conceptualisation phenomena . At first, we'll study the Guillaumian vocabulary's evolution between his 2 first books, that are 10 years apart (section 2), we'll tackle then a fundamental theoretical theme lexicon evolution (section 3), we'll finally analyse a particular theme through the tropes with which it is done (section 4).

Text genesis, concept genetics

2.1. From a practical point of view, one of the principal activities of scientists is to devise concepts, to modify them, to order and structure them. Conceptualisation goes with theorisation, and sometimes they are same 1 . To be aware of the fundamentally textual nature of concepts leads to think about their expression and the circumstances surrounding their development. Nowadays, one attaches more and more importance to discourse hiccups: autocorrection, slip of the tongue, anacoluthum etc. They were for a long time the victims of an homogeneity ideology (especially with the North-American generative theories). But now, these phenomena appear to be constituents of text, not only clues of the meaning construction, but even partners of this construction. As Bachelard said, in La formation de l'esprit scientifique, scientific concept is a clustering of "successive approximations" (Bachelard 1938: 61). Hesitations, renunciation, direction change, palinodes, all these hiccups of theorisation cannot be ignored, because they take part dynamically in conceptualisation and theorisation. Thus, discourse discontinuities have equivalents in the sometimes chaotic conditions of theoretical concept emergence. 2.2. Statistical analysis, called lexicon connection, which can be done on forms or on form occurrences , informs us on the breakdown of vocabulary in texts which make up the corpus. One can thus compare, in a macroscopic way, a set of texts. If 2 texts have a high number of common forms, one will say the lexicon connection is big, or on the contrary, that lexicon distance is small. Form dictionary analysis in Guillaume's corpus shows a diachronic organisation. In other words, overall lexicon evolution seems to be continuous, without major discrepancy 2 . However, one observes a very important distance between the first book, Le problème de l'article, written in 1917 (and published in 1919, henceforth PBA) and its closest neighbours, more particularly Temps et verbe (TV), published in 1929 and the first lectures read in 1938. Perhaps distance is the clue of a major revision of the author's idiolectal dictionary. Statistical lexicon methods allow to study the decreasing and increasing forms from one text to another. And yet it appears the lexicon structure is completely changed between the 2 first texts. First, Guillaume gives up philosophical concepts to promote scientific ones. Then, the change has unexpected consequences on structure and qualification marks of these concepts. 2.3. Among increasing forms, one can observe 5 semantic categories: (i) meta-linguistic vocabulary strongly increases. It is structured into 2 distinct lexicons: first, traditional meta-language (temps, aspect, mode, présent, passé, futur, aoriste, optatif etc.), then, idiolectal meta-language (chronogénèse, chronogénétique, chronothétique, chronotypes, aspect tensif, détensif etc.). (ii) the vocabulary is sustained with a theoretical lexicon which is organised around two morphological derivation patterns: -'constru'-(construire, construction) and 'systēm'-(système, systématique) which show that Guillaume wants to structure and set up concepts together in a new way; -'représent'-(représenter, représentation) and schēm'-(schéma, schématisation) which mean that Guillaume tries to show explicitly and concretely the phenomena he studies. This willingness to show, to represent and to schematise also appears when he frequently uses charts, indicated by the increasing use of the lexical item ("lexie") figure 3 .

1 Sometimes a single concept becomes a theory. 2 One will notice an amazing tendency of early and later texts to be close. In other words, it seems that Guillaume, in his earlier period, used vocabulary he had given up earlier. We will show examples of this U-turn below (see section 3.3 and 4.1) 3 Henceforth, we propose to adopt the French linguistic term lexie which is a stable set of morphemes, constituting a functional unit (see Rastier et al. 2002).

(iii) Among structure items, one sees a lexical field we could relate to spatial patterns: situer ["to locate"], opposer ["to oppose"], différer ["to differ"], comprendre ["to include"] etc. This vocabulary links the two theoretical lexicon sets seen above. (iv) Forms used as reference-related lexicon are on the increase as well. For instance: nous nommerons ["we'll name"], identité ["identity"], propre ["own"], proprement dit ["strictly speaking"]. (v) Finally, Guillaume seems to introduce a critical dimension. He fits his works into linguistics history (using expression like: linguistique savante, historique, traditionnelle descriptive ["descriptive, traditional, historical, scholarly linguistics"]). 2.4. Let's study now the decreasing forms in TV; that is forms existing in PBA which will be given up 10 years later. (i) The most important remark we can make concerns the substantial fall in philosophical vocabulary: -verb: exister ["to be", "to exist"], -nouns: esprit ["mind"], raisonnement ["reasoning"], intelligent, êtres ["beings"], idéalité ["ideality"], idée ["idea"], matière ["matter"], objet ["object"], vue ["view"], fin ["purpose"], progrès ["progress"], force, causes, loi ["law"]; -adjectives: générale ["general"], pure, formelle ["formal"], logique ["logical"]. In comparison, meta-language vocabulary doesn't seem to decrease. Only traditional grammar terms as article or nom which are specific to the PBA problematic decrease. It doesn't mean that Guillaume gives up all the first book's meta-language: meta-language increases at the expense of non linguistic concepts, i.e. non scientific concepts.

(ii) May we also add that evaluation and qualifying lexies decrease too: plusieurs ["several"], guère ["hardly"], très ["very"], trop ["too much"], peu ["few"], assez ["enough"], tout ["all"], souvent ["often"], sortes de ["kind of"], diverses ["various"], véritable ["real"], forte ["strong"], facile ["easy"], petit ["small"] etc. (iii) Lastly, let's notice the decrease in the use of modal verbs falloir (il faut, il ne faut pas, ["it must", it mustn't"]) and impersonal pronominal verb s'agir (il s'agit, il ne s'agit pas, il ne s'agit plus) which indicate and point what is about. These two verbs' decrease may show Guillaume's abandonment of hypothetical or teleological stance. To sum up, in PBA one has data, but very few tool concepts to analyse them, and the lack is offset with philosophical notions (esprit, idée, loi etc.) qualified with modal verbs and evaluation lexies (sorte de, presque, peu, etc.). In TV, one has a wealth of tool concepts and very specific meta-concepts (thus one avoids evaluations). Tool concepts and meta-concepts are organised into a hierarchy, they form a system, and this system is, strictly speaking, a theory, in an etymological meaning which is "shown", or even "performed by mind". That's why charts and spatial location lexicon are required. Moreover, esprit ["mind"] is the largest decrease between PBA and TV. The number of occurrences of esprit in PBA is 337, that is 1/6 th of occurrences in the whole published corpus to date, which is made up of more than 20 books. Finally, one notices the 'constru'-lexeme, which is the largest increase between PBA and TV, is also the largest increase in the whole corpus, from 1919 to 19604 . It shows the crucial aspect of what has been done between the two books;: Guillaume gives up a philosophical approach of language in favour of a more rigorous, theoretical and scientific attitude. 2.5. For, us; Guillaume's palinode is typical of the hiatus existing between philosophy and science. At the same time, French writer Paul Valéry said something which wonderfully sums up Guillaume's realisation: La philosophie développe cette croyance qu'il y a, dans la profondeur que nous supposons au sens de certains mots, des choses, des objets qui pour être indéfinissables n'en ont pas moins une existence réelle. Et ces mots-là précisément font partie de cette croyance. Ainsi infini, parfait, temps, cause, âme et matière etc. sont idoles philosophiques -et non considérées [pour] ce qu'ils sont [c'est-à-dire] des instruments défectueux, désastreux en combinaison5

To our mind, Guillaume, between PBA and TV, freed himself from these croyance and from these idoles philosophiques, because they were inappropriate to describe language, and impossible to combine with each other.

Theme lexicalisation

3.1. To determine concepts, philosophical tradition gives pre-eminence to lexicon, and more particularly to noun phrases. And yet, Saussure asserted that the psychic side of sign, i.e. "signified", doesn't coincide with concept. Therefore, a concept is not systematically linked to a specific sign. It can be actualised in theme, that is a set of semantic units which aren't necessarily lexicalised. In other words, a concept is not bound to match lexie. A theme lexicalisation, which leads to form a concept, mustn't be thought exclusively as its start, not even as achievement of conceptualisation. It appears to be a state linked to a particular time. Before lexicalisation, concept can exist textually, in a more or less tenuous manner, in a state of theme(s) in the process of structuring. It is then semantically unstable and textually complex. It is embedded in a complex net of expressions and phraseologies. More, a theme can be divided in several sub-themes, which can coexist in same context or specialise according to different issues. Several genetically distinct themes can merge, become muddled, group together, to eventually separate. They can also coexist for a long time, without mixing up, while sometimes sharing a few semes. Themes and sub-themes can give rise to several lexicalisations: during the same time, that is in the same context, or at different times. Themes (and sub-themes) can also never be lexicalised (or lexicalised a posteriori, by other authors6 . Anyway, lexicalisation doesn't mean concept is defined. 3.2. Actualisation, i.e. the way linguistic item goes from language to discourse, is sometimes considered as Guillaume's emblematic concept. Though, the lexie is statically very infrequent in the corpus. One counts less than 40 occurrences. In fact, the concept of actualisation had several aspects, which did not correspond to the same reality. In 1919 (PBA), actualisation does not exist namely. But a complex theme built around substantives actuel ["actual"] and inactuel ["inactual"] dominates. The theme is aided by adjective or noun suffixes which mean states and not process (e.g. actuelle, inactuelle, actualité; inactualité etc.). Form inactuel is in competition with form virtuel ["virtual"]. Only morpheme 'virtu'-feeds a process lexie: virtualiser (["to virtualise"], 3 occurrences). A similar conceptual couple is also present, achieved with puissance ["powerful"] vs. effet ["effect"] and 'potent'-vs. 'effect'-(e.g. potentielles, effectives). But no form means process (like potentialiser, for instance). Actualisation doesn't come suddenly, but progressively, during TV. In Chapter 3, one has form actualisantes (["actualising"], 2 occurrences); in Chapter 4, actualisable (2 occurrences); and, in chapter 5, 8 different forms: two of which are past participle actualisés and eventually noun actualisation. Noun first appears with prefixed (sur-actualisation). Then, process morpheme -'is'-is added to lexeme 'potent '-(potentialiser). But process lexeme 'virtualis'-, invented 10 years before, remains marginal (3 occurrences). During the 30's, actualisation frequency falls drastically, and both associated sub-themes7 gradually decrease and become very rare. Concerning conceptual couple 'potent'-vs. 'effect'-, it leaves purely and simply from Guillaume's meta-language. On the other hand, morpheme 'effect'-is reused in couple puissance vs. effet which is more and more frequent, while first themes are abandoned. Puissance vs. effect are used in lexies like unité de puissance ["power unit"], unité d'effet ["effect unit"]. They go with a new theme structured around unifying concept acte. Lexies are then compounded: acte de langage ["speech act"], acte de discours ["discourse act"], acte de représentation ["representation act"]. Charts below shows how the morpheme 'act'-, which is used in 30 different ways, decreases while lexie acte de x increases. It is funny to see that Guillaume gives up, at first, philosophical rhetoric in favour of a scientific conceptual pattern, but then he turns away some famous philosophical concepts (puissance and acte) to use them as part of compounded lexies (unité de puissance, acte d'expression) and to integrate them in his scientific discourse. 3.3. Why does Guillaume give up morpheme 'act(u)'? and above all its combination actualiswhile it's going to become very famous in linguistics ? Several ways can explain it. The first one, which is more human than theoretical, involves expanding corpus. In 1922, Swiss linguist Charles Bally used for the first time actualisation to mean a very similar idea to the one described but untitled by Guillaume a while before. Linguists acknowledged Bally to be the inventor of the word. But word refers to concept, and then, concept authorship was granted to Bally, even if Guillaume was using it as theme before. That's why Guillaume avoids talking about actualisation after 1929, except for claiming credit for the invention! The other explanation is more theoretical. It's about the will of Guillaume to improve description of mechanisms that today we would call cognitive mechanisms. They are relation between thought and language. To Guillaume's mind, the first theme opposing actuel and inactuel should seem to be inadequate, because it wasn't enough constrained, or too hazy. Before its actualisation, language couldn't really be distinguished from thought. In the 40's, Guillaume places, between thought and language, an insurmountable ontological step. Language can't be thought. Moreover, it can't be considered as actualisation of thought (for more details, see Valette 2001).

In conclusion, one can observe that Guillaume, when he gives his very last lectures, reuses themes he had abandoned since his first book 8 : theme potentiel vs. effectif is replaced by theme puissanciel vs. effectif. And in a stunning way, a few weeks before he dies, Guillaume invents a new concept, effection, that some people have assimilated to actualisation. This late lexie might be a revenge on the omnipresent actualisation. 4. Textual construction of concept: the example of mechanism 4.1. Concept never boils down, far from it, to one or several definitions or even to a set of glosses, added examples or not. Concept depends of its realisation in text. Each one modifies its nature in such a way that autonymy is only a particular case 9 . If two concepts are linked only one time, then the link is part of the concept's nature, even though the link is not defining strictly speaking.

To illustrate our claim, I'll focus on the theme of mechanics, firstly because it is a complex theme, in the area between philosophy, science and technology, and, consequently, it can be part of various conceptual constructions; lastly because it is a very important concept in Guillaume's theory. But as it is complex, it hasn't been very stable in the way Guillaume used it, and it gave rise to several senses which were sometimes contradictory. What is mechanical? (i) what concerns machines, or is explained by means of machines, or by analogy to manmade machines (mechanical explanation) (ii) what concerns a representation, or what supplies a concrete and intuitive explanation, like that which gives the knowledge of a mechanism (mechanical explanation), (iii) what excludes any occult power, any inner or immanent purpose, any notion of force 10 .

Guillaume uses almost all these senses of mechanical. In PBA, his 1919 book, which is written with a philosophical tone, metaphysical concepts are very often used. "Mechanical" explanation is mentioned many times, but it competes with "intelligent" explanation which includes a teleological meaning incompatible with the third sense of mechanical. After that, Guillaume will try to exclude this "intelligent" explanation. Besides, let me take the example of force, opposite to mechanism. In section 2.4, we saw it decreases sharply. One observes indeed several anti mechanism lexies: force occulte, force aveugle, force sans but ni finalité, force conservatrice, force vitale, force d'innovation, force novatrice, force de l'élan initial, force de résistance, force expressive, force agissante etc. 11 . In short; to study mechanic in Guillaume's writings is to measure the evolution from philosophy to science, and even technology. 4.2. Cybernetics is quite rightly considered as the ancestor of cognitive science and, more generally, as the first effort to let thought become a science object. Guillaume, as inventor of a theory of mind, was necessarily sensible to cybernetics. The positive traces of his interest are an easily identifiable corpus: 2 paragraphs in two lectures told in 1955 and a set of texts in different genres (essay, report, lecture) written during the 1956 spring. 1956 corpus analysis shows a very precise idea of what Guillaume thinks about cybernetics. Concerning favourable remarks, Guillaume seems to subsume his theory and cybernetics to a similar project: understanding the mechanism of thought. For him, the linguistic purpose of cybernetics is to isolate mechanisms used by language activity, i.e. to extract formal and mechanical parts of language from the human being (as material substratum) which force him to obey. Guillaume hastens to say the project is unrealistic, for phenomenological reasons: in a few words, he claims language exists only if it is located, embodied, and it cannot be 9 Besides, this case can be suspect: definition can tell what you would like the concept to be, and not what it really is when it is used. Moreover, quality of definition (accuracy, comprehensiveness) doesn't mean theoretical interest 10 Based on Vocabulaire technique et critique de la philosophie, Lalande, PUF, 1962. installed in a non body machine. But analysing some textual elements, one can think that Guillaume's positions were and still are much more moderate and subtle. In sections 4.3 and 4.4, we will study 2 textual phenomena, the first lexical, the second trope rhetorical. Both bring new information about the way Guillaume deals with the language embodiment. 4.3. In a 1956 conference, Guillaume called cybernetic mechanism endo-mécanisme du langage ("endo-mechanism of language") and assured many times it is an attested synonym for cybernetics. But endo-mechanism is not part of cybernetics terminology 12 . Though, one notices 17 occurrences of endo-mécanisme in the sub-corpus. It can't be a lapsus calami; and although Guillaume perhaps mistakes with the quite similar servomechanism, the use of prefix endo-is extremely interesting. Both elements forming the lexie endo-mécanisme are parts of Guillaume's idiolectal dictionary. One counts more than 1,500 occurrences of lexeme 'meca(n)'-(mécanique, mécanisme). It is used to construct the key-concept psychomécanisme (["psychomechanism"], i.e. mechanism of thought concerning language) which will be chosen by Guillaume's heirs to name the theory (psychomécanique du langage). Prefix endo-is also part of Guillaume's morphemic dictionary. One counts about 10 lexies using it (endo-sémantique, endo-statique, endo-morphologique, endo-systématique, endochronogénétique, endo-phrastie, endo-synthèse, endo-psychique, endo-génèse etc.) and about 200 occurrences in the whole corpus 13 . Prefix endo-is attested since 1938. It is contemporary of prefix psycho-. It's also in 1938 that appeared for the first time psycho-systématique, which is the name Guillaume chooses for his theory. Psychomécanisme, chosen by heirs, appears in 1945. A few months later (January 1946), one comes across a first occurrence of endo-systématique. The second one will appear in 1957, just after the conference devoted to cybernetic endo-mécanisme. Thus, it seems that morphemes endo-and psycho-are used in very similar constructions, -not to say interchangeable. Moreover, 6 months before he presents cybernetics with the wrong name endo-mécanisme, Guillaume writes: "Dans 'psychosystématique', il y a psychisme et système. 'Psychisme' emporte avec soi l'idée essentielle et cinétique d'intériorité. Le psychisme (humain), c'est le dedans de l'homme pensant." (Guillaume [12, 1 st 1955], leaf 2, unpublished) 14 . Finally, the two morphemes have the same seme /inside/. It is inherent in endo-and afferent in psycho-. 15 One is surprised by the morphological similitude between key concept psychomécanisme and pseudo-cybernetics concept endo-mécanisme. The first could be the etymon of the second. For us, this is a typical example of textual construction of concept. Term psychomécanique, forced by its realisations in the text, is here enriched with a cybernetic sense. This sense is extraordinary because, first, the cooccurrent realised lexie is a hapax (in textual construction 11 That is "occult force", "blind force", "purposeless force", "conservation force", "vital force", "innovation force", "novation force", "initial momentum force", "expressive force", "acting force" etc. At one stage, before he died, Guillaume talked about the forces vives du langage. 12 As historian of cognitive science Jean-Pierre Dupuy told us. 13 Concerning the inside morpheme 'intéri', we counted almost 1,000 occurrences. , intérieur(e), intérieurement, and interne are part of the peculiarities of Guillaume's style, compared to the TLF dictionary. 14 In short: "The (human) psyche is the inside of thinking man". 15 is the inside of thinking human" 4.4. the continuation of our investigation in Guillaume's text bring up the question of tropes, which are far from being absent in scientific discourse. Metaphor is particularly used. Let's study below some aspects of the rhetoric of Guillaume's scientific discourse. Guillaume is used to opposing language as mechanical and determined, and mind, as free and undetermined. Mechanics comes from Greek mekhane "machine". As we saw above, what is mechanical is explained by means of machines, or by analogy to man-made machines, and mechanical explanation is an avatar of the analogy. Guillaume uses frequently mechanical explanations, and he compared language to machine in but very few significant occasions. 4 times he draws the comparison, and twice he takes care to moderate the strength of the comparison. For us, this caution is an antiphrasis: rather than weaken the comparison, it emphasises its interest. In the first comparison, dated 1946, Guillaume opposes the order with which the component parts of the machine run and the order with which the worker built the machine; this to explain that synchronic order is not diachronic order. In the second one, dated 1947, he compares the relation between the speaker and the mechanic who drives his machine ignoring its architecture and its working: La construction achevée d'un système repose sur un certain ordre dans le rapport des parties constitutives . Elle n'a rien à voir avec l'ordre dans lequel les parties rapportées ont été apportées à l'ouvrier -qui est ici l'esprit afin qu'il en construise […]. J'évite autant que possible, parlant des choses de la langue, qui ont une rigoureuse spécificité, de faire appel à des comparaisons. Pour une fois cependant, je crois pouvoir, sans dommage appréciable, montrer exceptionnellement un peu moins de scrupule. Je dirai donc que l'ordre de rapport -l'ordre systématique -est dans une machine celui qui en assure le fonctionnement, celui sans lequel la machine ne marcherait pas. Il emporte avec lui une juste mise en place des pièces constitutives. Quant à l'ordre d'apport -l'ordre historique -il est celui, en général assez inconditionné, qu'on a suivi pour le montage des pièces […]. Je veux me persuader que cette comparaison n'a pas d'inconvénients cachés (Guillaume [5, 17 1946c] 1985: 196-197) 16 La situation du sujet parlant est, en l'espèce -j'ai peu de goût pour les comparaisons, généralement fausses sans qu'on s'en aperçoive bien à première vue -la situation est à peu près celle du mécanicien qui sait conduire une machine, mais qui peut n'avoir qu'une idée tout à fait vague du dispositif intérieur de la machine qu'il conduit et une idée encore plus vague des problèmes de toute sorte mis en cause par et pour sa construction. La difficulté, qui est grande, de s'introduire à la connaissance de la langue et de sa systématisation propre n'empêche nullement que cette connaissance soit indispensable à qui veut avoir une connaissance véritable de ce qu'est le langage. (Guillaume [12, 28 1947c] The methodology of scientific texts' semantic analysis we have tried to explain, lets us consider bivalence as a positive element of conceptualisation phenomenon, and not as a vacuity clue. Guillaume's warning reinforces the link between both comparisons and invites 16 "The completed development of a system is based on some sort of order of its constituent parts. It is unrelated to the order in which the constituent parts have been brought to the worker -who stands here for the mind […]. When it comes to analysing language, which is rigorously specific, I try to avoid using comparisons. For once, however, I feel I can be a little less unscrupulous without doing too much damage. I would therefore argue that the synchronic order -the system's order-is what allows the machine to run, the pre-requisite to making the machine work. It involves a fair implementation of the component parts. As for the diachronic order -the historical order-, it is the usually relatively independent order one has followed to assemble components […]. I want to convince myself that such a comparison does not hold any hidden flaws."

17 "The situation of the speaker is -although I don't like comparisons, which are usually flawed without anyone realising it at first-a bit like that of a mechanic who knows how to operate a machine but has only a vague idea of the inner parts of the machine he uses and an even vaguer idea of the varied issues involved in its assembly. The great difficulty of getting to know language and the system upon which it is based does not rule out the fact that such knowledge is vital if one wants genuinely to know what is language" us to compare topics actors. One can say briefly that this double comparison is part of a complex motif where enunciation (the mechanic) and cognition (the worker) are the same thing. Thus, one can understand the argument of language embodiment Guillaume claims to criticise cybernetics (see section 4.2). However, Guillaume will never express explicitly this equivalence. It's an absolutely rhetorical hesitation, written in 1958, which is the closest formulation we found:

Le langage est dans l'homme pensant, dans la pensée humaine, un ouvrage par elle construit, qui lui sert -c'en est le finalisme principal -à reconnaître en elle-même où elle en est de sa propre construction (Guillaume [12, 4 1958] 1995: 13) 18

Let's note that during the conference, Guillaume alludes, for the last time, to the cybernetic machine. Thus, it appears the nagging question of language embodiment is for the first time linked to a machine topic, by means of an "exceptionally not so bad" comparison, but it is finally mixed up with the cybernetic machine topic, which is not comparison but real scientific modelling. Let's make it clear this text is not part of our electronic corpus. Its epistemological status is problematic because it is extracted from Guillaume's draft. Drafts are writing and 18 "Language is, in thinking human, in human thought, a piece of work it constructs, which is used -here is its main purposeto know in itself what stage of its own construction it is". 19 See, for instance Guillaume [3, 14 1957Guillaume [3, 14 ] 1982:155, 164. 20 :155, 164. 20 "We haven't noticed yet natural is better than manufactured, as sparrowhawk is better than plane ; it is thousands of times less potential, but it is alive. What a crude mechanism the other is, [compared] with the value of this being which has cogs and circulation down to its countless molecules, which builds and repairs itself. It's blindingly obvious: the live thing, which is born, which builds itself from the inside, cell after cell, is infinitely more advanced than the manufactured thing from the outside. The wonder is not the plane but the bird". conceptualisation workshops. They don't only deal with language. In the present case, language is absent, textually speaking. But we draw the reader's attention to the use of substantive merveille ["wonder"], at the end of paragraph. 'Merveill'-is not a common word. In Guillaume's idiolect, the lexeme includes a feature /linguistics/ absent of its ordinary meaning. Thus, thanks to the lexie, the text is about linguistics. Let's see in which terms. Guillaume usually uses lexeme 'merveill'-realised in adjective merveilleuse ['wonderful'], alluding to a frequently quoted Meillet thought: "chaque langue forme un système où tout se tient, et a un plan général d'une merveilleuse rigueur" (Meillet [1903] 1964: 463) 21 . And yet, the clockwork metaphor is also linked to Meillet's name (as it is a lexie). Several times Guillaume happens to quote his mentor's comments about him: "Vous faites de l'horlogerieune horlogerie que vous aurez de la peine à faire voir aux linguistes" (Meillet, quoted by Guillaume [3, 14 1957] It means lexeme 'merveil'-, in this text, conjures up the clockwork metaphor applied to language. But as there are two concrete entities, one supposes Guillaume interprets metaphor literally. A qualitative step is taken. The clockwork metaphor is indeed harmless, firstly because it keeps the ideal feature of language (language is abstract, a clock is concrete), lastly because anyway, except in special cases, language doesn't give the time, no more than a clock speaks! But a plane is as concrete as a bird, and above all, they have the same function: if its mechanics is crude, its purpose, to fly, is identical to a bird's one (in this case). Eventually, the theme industriel vs. naturel built with the matched features /concrete/ and /fly/ is propagated to language, via 'merveill'-. And yet, they are two characteristic features of scientific modelling as it takes place during the 20 th century, thanks to cybernetics. To conclude, one can say that the concept language as manufactured mechanics (vs. language as natural mechanics) is not lexicalised, but it textually exists, even if it isn't the wonder we could expect.

Conclusion

Applied to scientific text, semantic analysis shows how theories aren't constructed with ideas, notions, and concepts, but as a mix between linguistic creativity and highly constrained 21 "Each language is a system where everything is connected and has a wonderfully rigorous plan". 22 "You are a clockwork designer -which clockwork you won't easily show to linguists". rhetoric. One can see how major conceptual themes, like equivalence between thinking human and human thought in Guillaume's works, can never be explicitly written but nevertheless exist with several textual forms (e.g. rhetoric palinode, comparison etc.) linked with other themes (e.g. machine). Issues of our methodology in progress are many. They are linked to the epistemological specificity of corpus linguistics. The question of the border of the corpus, for example, which was raised after our lecture at the KIAP conference, appears to be crucial. By way of conclusion, we will answer now our interlocutor. Our claim is text is a priori self-sufficient, and one needn't call other scientific productions to explain data. One could retort that we turned to Bally, Meillet and cybernetics in our exposé. Admittedly, nevertheless extra-elements were in fact present in the corpus (quotation of Meillet, criticism against Bally, even description of cybernetics). Even if we well know Guillaume, his intellectual environment, his readings etc., we think the refocusing on text, that is the real and tangible object of linguistics, is absolutely necessary to rank it to the level of science. Historical or sociological context can weaken linguistic analyses. Eventually, we prefer a poor but fair study on a few semantic elements, as those we talked about here, rather than a pan-scientific wandering.

  See Rastier et al. 2002 for conceptual system.of concept, rarity is value), second, it is an idiolectal word. In brief, in this text, psychomechanics is cybernetics. The synoptic table below shows this convergence:

		psycho-systématique
	1938
	endo-sémantique endo-génèse	1945	psycho-mécanique
	endo-morphologique
	endo-systématique	1946
	endo-phrastie
	endo-synthèse		1955
	endo-psychique...
			" (human) psyche
	1956		psycho-systématique
	cybernetics =		psycho-mécanique
	endo-mécanisme	/intériorité/ /inside/
	/mécanique/
	/mechanism/
		/système/
		/system/
	cybernetics = psychomécanique

  4.4. Comparisons seen above and other meditations on machines, except cybernetics one, are metaphoric, i.e. its descriptive value is nil. They are only evocative. The main mechanical metaphor we can observe in Guillaume's writings is the famous clockwork, the epitome of every artificial mechanism19 . Because it is very commonplace, it has no incidence on theory. But the clockwork metaphor has a representative value. It contains a specific seme in Guillaume's talk, and this seme can propagate and feed a comparison, for instance. Let's see a thought about artefact, a priori without linked to language:Nous n'avons pas encore bien vu que le naturel passe l'industriel, comme l'épervier passe l'avion ; il est des milliers de fois moins potentiel, mais il est vivant. Quelle mécanique grossière que l'autre, [comparé] au prix de cet organisme qui a rouage et circulation jusqu'en ses infinies molécules, qui s'est construit lui-même et se répare lui-même. Cela devrait crever les yeux comme une évidence : la chose vivante, qui est née, qui s'est bâtie du dedans, cellule par cellule, est infiniment plus perfectionnée que la chose fabriquée du dehors. La merveille, ce n'est pas l'avion, c'est l'oiseau.(Guillaume, draft) 20

  1982: 155)22 . Thus, lexie language, when it collocates lexie Meillet, consists of 3 semantic features /wonder/, /clockwork/ and /system/:

	Meillet collocation with
	LANGUAGE
	/merveill/
	/wonder/
	/horloge/
	/clockwork/
	/système/
	/system/

Mathieu VALETTE -Conceptualisation and Evolution of Concepts

One counts 3,254 occurrences, with 40 forms and 12 lexies: construire, reconstruire, construction, reconstruction, constructivité, construit, préconstruit, inconstruit, constructeur, constructif, reconstructif, constructivement (all lemmatised).

Paul Valéry, 1924, δέλτα, X, 237, quoted from Cahiers, Bibliothèque de la Pléiade, Gallimard, vol. II, 597. We slightly modified text for a better understanding. "Philosophy develops the belief there exist in the supposed depth of certain words, things, objects, which are undefinable but real. And those words are precisely part of this belief. Thus, 'infinity', 'perfection', 'time', 'cause', 'soul', 'matter', etc. are philosophical idols -and not considered as they are: faulty instruments, disastrous when combined".

A lexicalised concept can more easily be manipulated (relation with other concepts, migration to other issues or other thematics etc.).

That is the first sub-theme, without process ('act'-vs. 'inact'-/'virt'-); and the last sub-theme, with lexicalised process (actualiser).

It's a strong trend which isn't restricted to the theme talk about here.


Guillaume Rosinosky
email: guillaume.rosinosky@bonitasoft.com

Samir Youcef

François Charoy

Efficient migration-aware algorithms for elastic BPMaaS

Keywords: BPM, cloud, elasticity, BPM as a service

As for all kind of software, customers expect to find business process execution provided as a service (BPMaaS). They expect it to be provided at the best cost with guaranteed SLA. From the BPMaaS provider point of view it can be done thanks to the provision of an elastic cloud infrastructure. The provider still have to provide the service at the lowest possible cost while meeting customers expectation. We propose a customer-centric service model that link the BPM execution requirement to cloud resources, and that optimize the deployment of customer's (or tenants) processes in the cloud to adjust constantly the provision to the needs. However, migrations between cloud configurations can be costly in terms of quality of service and a provider should reduce the number of migration. We propose a model for BPMaaS cost optimization that take into account a maximum number of migrations for each tenants. We designed a heuristic algorithm and experimented using various customer load configurations based on customer data, and on an actual estimation of the capacity of cloud resources.

Introduction

During the last decade, we witnessed a major change in the way companies are delivering software. It is more often distributed as a service, operated by software producers, hosted in public clouds instead of as a package and installed install on premises. BPM systems vendors and operators start to propose this distribution modality. It removes the burden for customers to operate the BPMS and the corresponding infrastructure. They pay for process instances they execute or on a fixed monthly rate per user [START_REF] Le | A Study on BPaaS with TCO Model[END_REF]. The service provider aims at providing the required service quality at the lowest possible cost. Thanks to the public cloud and the elasticity it supports, providers can deliver that quality while minimizing resource consumption, and thus the operational cost. Public cloud providers allow to add and remove dynamically computing resources. However, it does not fit well with the deployment stack of a BPMS that include web servers and databases. In this paper, we propose a method that allows to distribute process execution on a set of cloud computing resources, and to adjust the resources based on the load that the customers require. We call a customer a tenant, and we ensure that all the processes of a tenant are executed on a BPMS installation. We consider that resources are paid by discrete time units. We assume that we know for each tenant what will be its maximal resource consumption time unit per time unit. More precisely, we want to take into account the knowledge we can get from the business dimension, i.e. the number of task execution per hour. In our previous work [START_REF] Rosinosky | An Efficient Approach for Multi-tenant Elastic Business Processes Management in Cloud Computing Environment[END_REF], we proposed to optimize resource consumption from a timeslot to the next. In this paper, we extend the method to optimize resource consumption on an arbitrary number of timeslots. We also limit tenant migrations from an installation to another to avoid unwanted service disruption. Migrations generally occurs when the resource on which a tenant is deployed is not sufficient to support its required load for the coming period of time. For each studied duration, based on the knowledge of the resource consumption profile that we can get from all the tenants, we compute a deployment plan that minimize resource consumption while maintaining the number of migrations for each tenant at an acceptable level. This is the contribution of this paper. We propose a linear optimization model and then an heuristic in two parts. A first that computes good times for each tenant to migrate using time series segmentation methods. Then we show how this method coupled to the a restricted version of the timeslot heuristic from the previous paper provides substantial gains compared to more simple or naive ones. We validate it with an experimentation using realistic values for the size customers and the size and price of cloud resources. In the next section, we present the state of art regarding BPM elasticity in cloud computing field. In section 3 we describe the model that we want to optimise. In the following section (4), we explain the condition of the experimentation. Then in section 5 we describe and discuss our results. In the last section, we conclude and present possible extensions to this work.

2 Elasticity in BPM Some attempts have already been done at managing BPMaaS elasticity in the cloud. Schulte et al. [START_REF] Schulte | Elastic Business Process Management: State of the art and open challenges for BPM in the cloud[END_REF] made a review on the current status on BPM elasticity, and the different important criteria. We focus here on the scheduling and resource allocation parts, with an emphasis on the multitenancy functionality.

Hoenisch et al. [START_REF] Hoenisch | Optimization of Complex Elastic Processes[END_REF] proposes an interesting approach : the Service Instance Placement Problem, a cost optimization model concerning the assignment of process instances to VM, scheduling of service invocations, and the provisioning of VM. The authors consider the underline structure of the BPM processes and propose to optimize the cost while taking into account penalties for violated deadlines. However, they consider only the BPM engine's CPU and RAM capacity in their model -and not the database tier-and do not consider multitenancy or migrations. Other previous attempts have the same drawbacks such as [START_REF] Hoenisch | Self-Adaptive Resource Allocation for Elastic Process Execution[END_REF], [START_REF] Janiesch | Optimizing the Performance of Automated Business Processes Executed on Virtualized Infrastructure[END_REF], [START_REF] Euting | Scalable Business Process Execution in the Cloud[END_REF].

Hachicha et al. [START_REF] Hachicha | A configurable resource allocation for multi-tenant process development in the cloud[END_REF] addresses multi-tenant BPMaaS with the concept of configurable resource assignment operator. It consists of an enrichment of the process with meta informations on the required resources for the tasks execution. However, it needs to add informations in the BPM schema, thus needing to alter BPM engine and the processes of the customers and do not propose a resource allocation and scheduling method. Another attempts to tackle the multi-tenant problem is done in [START_REF] Sellami | Elastic Multi-tenant Business Process Based Service Pattern in Cloud Computing[END_REF] by Sellami et al. They propose a multi tenant approach based on customizable thresholds, however, it does not take into account migration cost or the database tier.

There are many papers on Virtual Machine assignment or reassignment in data centers such as [START_REF] Wolke | More than bin packing: Dynamic resource allocation strategies in cloud data centers[END_REF], [START_REF] Li | On dynamic bin packing for resource allocation in the cloud[END_REF], [START_REF] Jaśkowski | A hybrid MIP-based large neighborhood search heuristic for solving the machine reassignment problem[END_REF], [START_REF] Brandt | Constraint-based large neighborhood search for machine reassignment: A solution approach to the ROADEF/EURO challenge[END_REF], however as in datacenters the physical machines are already reserved, only the scheduling part is studied and for the reassignment papers, the migrations are usually counted as part of the objective function instead of a separated entity.

Our work is an evolution of our precedent paper [START_REF] Rosinosky | An Efficient Approach for Multi-tenant Elastic Business Processes Management in Cloud Computing Environment[END_REF] where we proposed an bi-objective optimization model for cost and migrations quantity for all tenants scrambled from a timeslot to the next, and a corresponding efficient heuristic. Simply repeating this heuristic on multiple timeslots could provoke the migration of the same tenants, thus provoking breaks of quality of service. We propose here to harness the problematic of optimization on multiple consecutive timeslots, with a limitation on the number of migrations for each tenant.

The BPM execution model

In this section we introduce the model for the BPMS execution we want to optimize. Our model relies on a few assumptions regarding the BPM system. First, it must be multi-tenant, i.e. several customers (or tenants) can share the same BPMS installation. Second, it is possible to migrate a tenant from one installation to another with minimal disruption. The main issue here is the data migration from a database to another [START_REF] Das | ElasTraS: An elastic, scalable, and selfmanaging transactional database for the cloud[END_REF][START_REF] Barker | ShuttleDB: Database-Aware Elasticity in the Cloud[END_REF]. We also only consider that IaaS providers bill the computing resources per studied timeslot (for instance per hour). Main public cloud providers like AWS, and IBM Bluemix, follow this pattern per hour, while Google Compute Engine or Azure propose also a per minute billing.

The operation of a BPMS requires a complex production software stack. It may combine a BPM engine, load balancers and relational databases. They are often deployed on distinct hardware instances or virtual machines from the BPM engine, mostly for performance reasons. We call "cloud configuration" the set of resources that we use to execute process instances for a group of tenants. Last, we assume that we know the usage requirement for each tenant timeslot by timeslot in term of the maximum task throughput per second. This metric has the advantages of being representative of the system usage of both the database tier and the application server tier. We must also know the capability of each cloud configuration type in term of BPM task throughput.

We aim at minimizing the cloud resource cost while ensuring that the throughput for each tenant is at the required level. Migrations count for each tenant should not exceed a fixed number in order to avoid disruptions. We propose here a linear model where we wish to optimize the cost of placement.

Let the following variables :

-T , the set of cloud configuration types, with t its cardinality.

-I, the set of tenants with n its cardinality -J , is T × I the set of all possible cloud configurations associated with each tenant. its cardinality is m = t × n -C j , and W j , respectively the cost and the capacity for the configuration j, with j in J w i (k), the required capacity for the tenant i during time slot k -K defines all the time slots, from 0 to D, where D + 1 is the number of time slots. x j i (k), the assignment of tenant i to configuration instance j during time slot k y j (k), the activation of configuration j during time slot k -M is the defined maximum number of migrations for each tenant

min j∈J j k∈K k C j y j (k) (1)
We have the following constraints :

∀i ∈ I, ∀k ∈ K j∈J j x j i (k) = 1 (2) ∀j ∈ J , ∀k ∈ K i∈I i w i (k)x j i (k) ≤ W j y j (k) (3) ∀i ∈ I j∈J j k∈K\{D} k x j i (k)x j i (k + 1) ≥ |K| -M (4) ∀i ∈ I, ∀j ∈ J , ∀k ∈ K, x i j (k) ∈ {0, 1}, y j (k) ∈ {0, 1} (5)
Equation 1 is our optimization objective. We want to minimize the total cost of cloud configurations for all the time slots (a day for instance). The constraint described in equation 2 means that, for each timeslot, each tenant must be located on one and only cloud configuration. The constraint described in equation 3 means that, for each timeslot, the sum of required throughput of the tenants co-located on a cloud resource do not exceed the capacity of this resource.

The constraint described in equation 4 means that we want to limit the number of migrations per tenant to M . If x j i (k) and x j i (k + 1) are both equal to 1 for the resource j and the tenant i on two consecutive timeslots k and k + 1, their product will be equal to 1, the tenant did not migrate. In the other cases, the product will be equal to 0. They occur when tenant i migrated from or to another resource from timeslot k to timeslot k + 1 or when tenant i remained on a different resource on both timeslots. We sum these products resource per resource, on each timeslot pair for each tenant. We obtain the number of timeslot where a tenant remained on the same configuration. The difference between the total number of timeslots and this number is the number of migration. Limiting the number of migrations is then straightforward.

Since we have multiplication between two variables, we obtain a quadratic optimization problem. As can become is very slow to compute, we linearized the equation 4, following the usual method. The result for this linearization is described in equation 6 :

∀i ∈ I j∈J j k∈K\{D} k w j i (k + 1) ≥ |K| -M ∀i ∈ I j∈J j k∈K\{D} k x j i (k) + x j i (k + 1) -2w j i (k + 1) ≤ 1 ∀i ∈ I j∈J j k∈K\{D} k w j i (k + 1) ≤ x j i (k) ∀i ∈ I j∈J j k∈K\{D} k w j i (k + 1) ≤ x j i (k + 1) ∀i ∈ I, ∀j ∈ J , ∀k ∈ K, w i j (k) ∈ {0, 1} (6)
Even with the linearization, the resolution of this problem can be very time consuming. The number of variables will be of tn(D + 1) + tn 2 (D + 1), and the number of constraints will be of tn(D +1)+tn 2 (D +1)+4n. For 7 cloud resource types(t), 100 tenants (n), and 24 time-slots (D + 1), it makes 1696800 variables, and 1697200 constraints. It is not reasonable to try to compute the optimal solution when the number of tenants grows, as we will see in the experiment part. In the next section, we propose a heuristic that provide solutions to the problem with reasonable computation time even with large number of tenants.

Heuristic optimization proposition

Iterative timeslot algorithm

This algorithm is based on our previous timeslot heuristic [START_REF] Rosinosky | An Efficient Approach for Multi-tenant Elastic Business Processes Management in Cloud Computing Environment[END_REF]. Its principle is to consider that, regarding an initial distribution, we search the best distribution for the next timeslot, knowing that the required capacity of each tenant can change. With the timeslot algorithm, we search for a Pareto front of the lowest global number of migrations and resources cost. As the number of migrations is discrete and limited by the number of tenants, we can compute the lowest cost for each number. First, we look at overloading and overloaded tenants as shown in figure 1. It depicts the distribution of tenants on different cloud configurations. The initial state is at time T . At time T + 1, the requirement for each tenant changes. Some of them have to migrate (orange and red). The heuristic principle is, that for each possible number of migrations we consider the combination of resources containing the corresponding number of tenants, added to the number of tenants that we must migrate. As we consider the total quantity of tenants, there are several possibilities for each number of migrations. This is a classic subset sum problem. For instance, in figure 1, in order to compute the results for 5 migrations, we should move the tenants t8, t6, and remove the combinations of resources with 3 remaining tenants (R1 or R2 and R3). Once we have selected the tenants, we first repack the possible tenants in existing resources, and then use a Variable Cost and Size Bin Packing [START_REF] Kang | Algorithms for the variable sized bin packing problem[END_REF] algorithm for the remaining ones. The last step consists by iteratively try to replace by cheaper ones the resources with only moved tenants.

This approach provides good results timeslot by timeslot. Still, we must adapt it to ensure the number of migrations per tenant described by constraint 4 that limit the number of migration for a given duration per tenant. In the next section we propose an adaptation of this algorithm to enforce this constraint.

A migration aware optimization strategy

For this new strategy, we add the list of tenants allowed to migrate as an additional parameter to the previous method. For instance if, for a timeslot, we allow to migrate every tenant but T 5 and T 2 because they have reached their maximum number of migration (M ), the new timeslot algorithm must ignore them and maintain them on their resources. We cannot delete resources with tenants.

Let a migration strategy the set of h i (k) with 0 ≤ k ≤ D -1 where each tenant i is allowed to be migrated. h i (k) is equal to 0 if the tenant is not allowed to move between timeslot k and k + 1, and equal to 1, if it is allowed. The equation 7 describe the maximum number of migrations.

∀i ∈ I k∈K\{D} k h i (k) = M (7)
We need to find the optimal values for each h i (k) respecting the maximum number of migrations to obtain the best cost.

Once we have determined the different migrations timeslots, we choose the required capacity level. As our algorithm does not consider multiple timeslots simultaneously, we assign a fixed capacity for each tenant for each period where it does not migrate. We call C i (m) the capacity during the period between migrations m 1 and m 2 . In order to avoid overloads, we consider the maximum capacity required for the corresponding timeslots, as in equation 8. An example of a maximum load strategy is presented in figure 2. These capacities are used instead of the initial capacities of the tenants in the timeslot algorithm.

∀i As testing every migration strategy possibilities would be require too much time, we need an efficient way to evaluate which one we should use. It should give better results than a naive approach, and respect the constraint on the number of migrations for each tenant.

∈ I∀m 1 ≤ k < m 2 , C i (m 2 ) = max m1≤k<m2 (w i (k)) (8)

Time series segmentation

We propose a method to identify good migrations strategies. We consider first that the variations in load will produce the need for migrations. If for instance a tenant needs a throughput of 10 tasks per seconds between 12pm and 6am, and then a throughput of 50 tasks per second between 6am and 12am, the best time to migrate is at 6am. Our approach here is, for k migrations, to find a way to fragment the load time series in k + 1 consecutive fragments, in a way where they have the minimum load. Time series segmentation techniques address this kind of problems.

As Lovric [START_REF] Lovrić | Algoritmic methods for segmentation of time series: An overview[END_REF] explains, we can see time series segmentation as a processing step and core task for variety of data mining tasks, as a trend analysis technique, as a discretization problem in function of dimensionality reduction, etc. . . The latter point interests us as we want to find a way to discretize the load time series, with discrete periods of remaining tenants, separated by migrations. The main common algorithms based on Piecewise Linear Representation are originally reported by Keogh et al. [START_REF] Keogh | An online algorithm for segmenting time series[END_REF] : top-down, bottom-up and sliding window. As our approach is offline (we know the future load), we focus only top-down and bottom-up.

The principle is to iteratively separate (top-down) or merge (bottom-up) consecutive sets of observations in the time series, so they keep a minimal error related to real observations. As it can be seen in [START_REF] Keogh | An online algorithm for segmenting time series[END_REF] and [START_REF] Lovrić | Algoritmic methods for segmentation of time series: An overview[END_REF], the main version of the algorithm segments the time series using Piecewise Linear Approximation (PLA), fitting each segment with an affine function found by linear regression of the values for each segment. This approach is interesting for our needs. Indeed, as we explained earlier, we want to segment the time series considering the maximum load instead of the mean of segment (we consider for each segment its maximum load as described in equation 8). As we will see in the experiment section, we also tested a mean constant piecewise approximation, that consider a fixed mean for the segmentation.

Once we obtain the segments, we compute the corresponding migration strategy. We initialize the matrix to zero, except for the timeslots where there is a change of segments, that we initialize to one. We then use this migration strategy with the restricted iterative timeslot algorithm as we can see in the next part.

The optimization algorithm

Here is a synthesis of our timeslot algorithm :

-First, compute the desired migration strategy using a time series segmentation algorithm. -Second, initialize the initial timeslot (zero) with the initial distribution.

-Then, for each timeslot from k = 1 to k = D :

• Launch a timeslot algorithm, using the distribution of the previous timeslot. Only the tenants able to move in the migration strategy for this timeslot migrate. Thus we ensure constraint 4 of the model • Keep the less expensive distribution with the least number of migrations. This is the distribution we choose for the current timeslot.

This algorithm provides a solution that enforces the constraints. In the next section we describe our experimentation that shows how it provides better results than a naive solution and with a reasonable computation time even for an hundred of tenants.

To test our solution we made a few assumptions and relied as much as possible on datasets that gives us realistic foundations for the resolution of the model. As we can see in the model part, we needed to have a good estimation of the customer loads, timeslot by timeslot on one side, and of the price and capability in task throughput per timeslot of a cloud configuration on the other side. We have then compared several segmentation methods on the same datasets of customer loads and cloud configurations to find the best ones. In the next part we describe the datasets.

Datasets

In order to get meaningful cost and task throughput for our cloud configurations, we have used the data obtained in our test framework experimentation [START_REF] Rosinosky | A Framework for BPMS Performance and Cost Evaluation on the Cloud[END_REF]. In this paper, we have set up an experiment on AWS with a BPMN process composed of 20 consecutive automated tasks launching a Fibonacci script. We launched tests on several r3 (storage-oriented) family instance types for the database, and c4 (CPU-oriented) family instance types for the application server. We used the BPM system BonitaBPM 7.3.23 in its Open Source version. We compared the obtained throughput with the price of each cloud configuration. Results are described in table 1 For the customer load part, we wanted to test multiple tenant quantities (5, 10, 25, 50 and 100), having different throughputs based on real data from BonitaBPM customers. More precisely, we used minimum and maximum throughput per second found in the anonymized execution history tables. The used thresholds are described in table 2. We have then generated each tenants initial timeslot load randomly following an uniform distribution between the two thresholds. Table 2. For each customer, the observed interval in days, the minimum and the maximum task throughput per second for each hour.

To avoid too much variation between timeslots, we also used another parameter we name tenant gap, a percentage of the gap between a tenant's minimum and maximum throughput. Using a totally random behaviour makes tenants throughput very chaotic. In general, the required load is relatively stable, as we have noticed in customers data. For each timeslot, we compute randomly the percentage of the gap, and we add it to the previous timeslot's load. If we obtain a load lower than the minimum, we cap it to the minimum (respectively capped to the maximum for loads superior to the maximum). For instance, for customer E and a gap of 0.25, the change between hours would follow an uniform distribution between -0.25(120 -5) = -28.75 and 0.25(120 -5) = 28.75, capped on the minimum and maximum for the customer, here respectively 5 and 120. We have experimented with various values for the gap. A gap percentage of 1 will correspond to a complete random behavior between the minimum and maximum loads. A gap percentage of 0 will correspond to a load who stays fixed at the initial timeslot load. For each number of tenants, we wanted to test multiple tenant gaps as it shows multiple levels of variability. More precisely, we have tested the tenant gaps 0.25, 0.5, 0.75 and 1. We have not tested the 0 tenant gap, because it provokes a stable load, and the algorithm would converge to a stable distribution and then stop moving tenants.

As we said, the main parameters we varied are the tenant quantity, and the tenant gap. Nonetheless, given the random nature of the obtained load, we ran the tests multiple times with different random distributions for each couple tenant gap and tenant quantity. In order to keep repeatable configurations and be able to test multiple algorithms, we have used twenty different random seeds for each tenant parameter couple. Using the same random seed on a same couple tenant gap/tenant quantity gives every time the same load distribution.

For each generated set (the cartesian product between twenty seeds, the 4 tenant gaps, and the 5 different tenant quantities), we tested several migration plan algorithms that we describe in the next part.

Software and methods

Our goal here is to determine between the different methods and for different number of migrations, which one gives the better migration strategies i.e. which one between top-down and bottom-up algorithms, grouped and individual strategies, and ConstantMaxPieceWise, ConstantPieceWise and Linear Regression fitters gives the best results.

As our metrics are hourly based on the different configurations and tenant loads, we used hourly timeslots, more precisely 48 timeslots. The initial setting is the following : for each tenant, we select the least expensive resource that is suited for the maximum required throughput on the study time. We name this method adapted heuristic.

For the segmentation part we implemented a fixed and updated version of the Alchemyst library4 . This library implements top-down and bottom-up algorithms, with mean constant and linear regression fitters. We added max constant fitter as described in section 4.3. We also tested the algorithms for several number of migrations, more precisely 2, 3 and 4 per day, so 4, 6 and 8 for the 48 hours studied. Last, we tested two grouping strategies : considering each tenant in a separated manner (individual strategy), or executing the segmentation on the sum of the loads, and moving every tenant simultaneously at the obtained migration timeslots (grouped strategy) .

We also enhanced our previous timeslot algorithm implementation [START_REF] Rosinosky | An Efficient Approach for Multi-tenant Elastic Business Processes Management in Cloud Computing Environment[END_REF] with the restriction on the tenant list. For performance reasons we don't consider here the subset sum for each number of migrations but only all the tenants.

To obtain reference values, we used a naive method to compute the cost. This gives us a reference cost that we can obtain without calculation. We also compared a subset of our test dataset with the solving of the linear model described in chapter 3 during a limited time, for the lowest number of tenants. For this we used the solver Gurobi [START_REF] Optimization | Gurobi Optimizer Reference Manual[END_REF].

Table 3 summarize the different parameters we used in this experiment. Experiments have been executed on c4.xlarge (CPU optimized) instances on Amazon Web Services. In the next part, we discuss our results. Table 3. Synthesis of the experiment dataset and algorithm used values.

Results and discussion

As we explained in the previous part, we compare our results with the adapted heuristic cost we obtained (in figure 3). The mean cost is between 370.15 $ for 5 tenants and a tenant gap of 0.25 and 18853.56 $ for 200 tenants and a tenant gap of 1. We can see here that the higher the gap, the higher the cost. Since the variation of the load is less restricted, the maximum load can be higher, and the strategy principle is to consider each tenant's higher load for each cloud resource. We see in figure 4 the results we obtained for a tenant gap of 0.25 and 4 migrations a day with the heuristic. We compute the gain percentage by observing for each experiment run (one seed, one tenant gap percent, on tenant quantity, one number of migrations) the ratio of the difference of the result related to the corresponding adapted cost. We can see that the different strategies give different level of results. Top-down algorithms give better results than top-down, except for top-down individual with linear regression fitter. Grouped strategies give almost every time the best results, except for the top-down algorithm on individual strategy with a constant maximum piecewise fitter, who gives results near to the two bests, (top-down grouped constant strategies), and is even more efficient for 200 tenants. For top-down algorithms, constant maximum piecewise is the best algorithm, followed by constant mean piecewise. It is more difficult to compare for bottom-up strategies.

Figure 5 shows a global overview of the results. Most of the time, the topdown algorithm gives better results than the bottom-up. The best global approach are usually more efficient on small number of tenants or with less varia-tion (low tenant gap). The best fitters here are top-down grouped constant max piecewise, top-down individual constant max piecewise and top-down constant piecewise. As expected, we obtain better results when we allow more migrations (from 5 to 10 percent for 2 migrations to 15 to 25 percent for 4 migrations). A higher gap percentage generates worse results. The top-down individual Constant Max Piecewise strategy gives the best results for more than 5 tenants almost every time. It stays relatively stable, for a defined strategy and number of tenants, mainly for grouped strategies. Individual strategies are always longer, and the duration seems to be multiplied by 3 to 4 each time the number of tenants doubles.

On the other side, computing the results with the exact model using a solver is very time consuming and does not give very good results for more than 5 tenants and a defined time of 30 minutes as we can see in the table 4. We have not tried to do the complete tests for more tenants. Even for 10 tenants, 24 hours of computing time does not give the optimal results : we have obtained a MIP gap of 7 % at best with the solver, while with our heuristic we obtained gains of 20% with a mean duration of at most 0.4 seconds of running time. For 100 tenants, our heuristic duration is 100 seconds for a grouped strategy.

We can see the correlation between the number of migrations and the gain. The results show us that the top-down algorithm works much better than the bottom-up, and that constant maximum piecewise fitter give almost every time better results than the other fitters. The constant mean piecewise fitter gives also interesting results. Good results for global strategies can be explained by the resource-oriented approach of our algorithm (except for overloading and overloaded tenants, it considers only resource removal for tenant displacement). The very good performance of individual maximum constant piecewise, especially for large number of tenants shows that this fitter is very efficient, but needs a minimum number of tenants to become more efficient.

We have shown that our heuristic is fast, even when the number of tenants grows, and permits substantial savings for the BPMaaS providers. A gain of 20 % on the adapted strategy for 100 tenants corresponds to a mean of 1373.48 $ for two days. Moreover, it is possible to test multiple strategies, as the computing time stays low (for 200 tenants an individual strategy lasts a mean of 11.75 seconds, and 5.02 seconds for a grouped one). The longer duration for the individual strategy can be explained by the mechanics of the heuristic. Indeed, in this case we segment every tenant instead of all at once in the grouped strategy. Individual strategies could be more interesting to use in production environment. Indeed, even if we have not considered this constraint, migrating all the tenants together could have some side effects on QoS because all the data of the customers will migrate simultaneously, having negative effects on the available network bandwidth. Of course an individual strategy could give the same results if the tenants have identical workload patterns.

In this paper, we have proposed a new linear model for resource allocation and scheduling of BPM execution in the cloud, and a quick, simple and straightforward heuristic giving good results compared to naive approaches and solving of the model. This model relies on assumptions that makes it applicable in an operational setting. First, we consider customers as a whole (tenants) and not a distribution process instance by process instance. This reduces the scope of the calculation and avoids security issues regarding access to the business data. Second we assume that we can migrate a BPMS deployment from one installation to another in a reasonable time. This is not available in current systems but it is possible with very little service interruption.

We have tested it with data from an existing BPMS with a task metric. Of course, we could also use it with other metrics such as the number of processes and even for other services than BPMS. For instance, we could consider web servers and the throughput of HTTP queries as soon as they have a strong data management component. We can also use the algorithm with different temporal dimensions, hours as in the experimentation, but also minutes or seconds. We also plan to use it in an online manner, coupled with a predictive component that computes dynamically the expected load for the following time slots. This is our next step. We also think that can still improve our results using metaheuristics. Even if they are much better than with a naive approach, there is room for improvement as shown by our experiments with a solver for 5 tenants. Last, we want to test this heuristic with customer data, where the results should be better considering the load patterns we can identify (day/night cycle, working hours, lunch time, etc.).

The authors would like to thank Gurobi for the usage of their optimizer, and Amazon Web Services for the EC2 instances credits (this paper is supported by an AWS in Education Research Grant Award). The data and the results are available at : http://doi.org/10.5281/zenodo.401374 . The source code of the framework is not free for now, except for the segmentation library, available at https://github.com/guillaumerosinosky/Segmentation/.

Fig. 1 .

 1 Fig. 1. Example of distribution of tenants on cloud resources at T and T+1

Fig. 2 .

 2 Fig. 2. Migration strategy of 6 tenants on 24 hours

Fig. 3 .Fig. 4 .

 34 Fig. 3. Distribution of experimentation adapted heuristic costs in dollars

Fig. 5 .

 5 Fig. 5. Gain in percentage of the algorithm regarding the naive approach in y axis, compared to the number of tenants in the x axis. The legend of figure 4 applies here.

Figure 6

 6 Figure 6 show the running time of the algorithm with different parameters. It stays relatively stable, for a defined strategy and number of tenants, mainly for grouped strategies. Individual strategies are always longer, and the duration seems to be multiplied by 3 to 4 each time the number of tenants doubles.On the other side, computing the results with the exact model using a solver is very time consuming and does not give very good results for more than 5 tenants and a defined time of 30 minutes as we can see in the table 4. We have not tried to do the complete tests for more tenants. Even for 10 tenants, 24 hours of computing time does not give the optimal results : we have obtained a MIP gap of 7 % at best with the solver, while with our heuristic we obtained gains of 20% with a mean duration of at most 0.4 seconds of running time. For 100 tenants, our heuristic duration is 100 seconds for a grouped strategy.We can see the correlation between the number of migrations and the gain. The results show us that the top-down algorithm works much better than the bottom-up, and that constant maximum piecewise fitter give almost every time better results than the other fitters. The constant mean piecewise fitter gives

Fig. 6 .

 6 Fig. 6. Mean duration in seconds for individual and grouped approaches, for each studied number of tenants. The standard deviation is represented on each bar, with the mean number of seconds.

Table 1 .

 1 . It provides the number of tasks for one $ for each configuration type. Price, mean task throughput, and mean task throughput by dollar of used cloud configurations.

	DB inst. type AS inst. type price task TP task TP per $
	db.m3.medium m3.medium	0.177	16.400	92.656
	db.m3.medium c4.large	0.223	23.157	103.845
	db.r3.large	c4.large	0.399	55.164	138.255
	db.r3.large	c4.xlarge	0.518	58.067	112.100
	db.r3.xlarge	c4.large	0.674	65.113	96.607
	db.r3.large	c4.2xlarge	0.757	61.474	81.208
	db.r3.xlarge	c4.xlarge	0.793	83.236	104.963
	db.r3.xlarge	c4.2xlarge	1.032	89.149	86.384
	db.r3.2xlarge	c4.2xlarge	1.587 105.794	66.663
	db.r3.2xlarge	c4.4xlarge	2.063 107.585	52.150
	db.r3.4xlarge	c4.4xlarge	3.173 115.283	36.332
	db.r3.4xlarge	c4.8xlarge	4.126 129.279	31.332

  Tenant qty Tenant gap Mean adapted Nb migr. Solver duration Solver gain Mean MIP gap

	5	0.25	419.99	2	1800	41.05%	3.57%
	5	0.25	421.91	3	1800	48.28%	3.45%
	5	0.25	421.91	4	1800	51.64%	3.91%
	10	0.25	685.82	2	1800	3.18%	48.33%
	10	0.25	685.82	3	1800	1.28 %	52.68%
	10	0.25	685.82	4	1800	1.28 %	55.33 %

Table 4 .

 4 Solver results for the 10 first seeds. Mean MIP gap is the gap between the solution and the inferior bound found.

http://www.bonitasoft.com/

https://github.com/alchemyst/Segmentation developed by Carl Sandrock for his paper[START_REF] Sandrock | Identification and Generation of Realistic Input Sequences for Stochastic Simulation with Markov Processes[END_REF]