Isabelle Roy

Elena Soare

Université Paris

CHAPTER SEVEN EVENT RELATED NOMINALS

published or not. The documents may come

1. Introduction 1,2 As has been widely argued for in the literature, deverbal nominals fall into two categories, depending on whether they retain the event from their verbal base or not. The original observation is due to [START_REF] Chomsky | Remarks on nominalization[END_REF]; see also [START_REF] Lees | The Grammar of English Nominalizations[END_REF], [START_REF] Marantz | No escape from syntax: don't try morphological analysis in the privacy of your own lexicon[END_REF], Borer (2003). For English -ation and -ing nominals (e.g., destruction, examination; forming, examining) and for zero-derived nominals (e.g., form, exam), this has led to distinguishing two classes of nominals: complex-event vs. result nominals (CENs/RNs [START_REF] Grimshaw | Argument Structure[END_REF] or Argument-Supporting nominals (AS-Ns, cf. (1)) vs. Referential nominals (R-Ns, cf. (2)-Borer 1999):

(1) a. the destruction of the city by the enemy b. the examination of the students by the teacher c. their building new quarters

(2) a. a complete destruction b. a difficult exam c. an impressive building

The nominals in (1) have an event interpretation (hence, Grimshaw's 1990 label of CENs). The eventive interpretation has been noted to correlate with various syntactic properties, as, for instance, the (possible) presence of temporal/aspectual modifiers.

(3) a. They destroyed the city in two hours. b. the destruction *(of the city) in two hours

The pattern in (3b) also has another important property, which is the obligatory realization of the arguments of the verbal base (hence the term Argument Supporting nominals; cf., [START_REF] Borer | The form, the forming and the formation of nominals[END_REF]Borer , 2003)). This property is compulsory when the event structure is activated in the presence of eventrelated modification (see [START_REF] Grimshaw | Argument Structure[END_REF][START_REF] Borer | The form, the forming and the formation of nominals[END_REF][START_REF]Exo-skeletal vs. endo-skeletal explanations[END_REF], Alexiadou 2001, among others). The correlation between the event interpretation and obligatory realization of argument structure has been an important point since [START_REF] Grimshaw | Argument Structure[END_REF]. The fact that both go hand in hand has been claimed in the literature to show that both are realized grammatically and that eventivity and arguments are inherited from the verbal and/or aspectual structure present with AS-Ns but are missing with R-Ns (the latter being simply derived from bare roots)-cf. Borer (2003); [START_REF] Alexiadou | Functional Structure in Nominals: nominalization and ergativity[END_REF]; van Hout and Roeper (1998). The syntactic approaches to word formation represented by these scholars take eventivity in AS-Ns to be correlated with the projection of syntactic functional layers detectable through argument structure projection and aspectual modifiers. The source of the eventive interpretation is the presence of a verbal base upon which AS-Ns are built. Nominalizations may thus inherit verbal properties, when (and only when) they involve a verbal / aspectual structure. The term 'event' (or 'eventive') nominals, however, is often the subject of some misunderstanding, or at least suffers from variable definitions depending on whether it is taken in the syntactic tradition where eventivity is correlated with particular structural properties, or from a (lexical-)semantic point of view where a much larger class of nominals would be considered as 'eventive'. 3 For instance, [START_REF] Grimshaw | Argument Structure[END_REF] Simple Event nominals (SENs) fall into this class when semantically defined. Such nouns (e.g., meeting, play) are 'semantically' associated to an event interpretation but do not exhibit the common event related properties of AS-Ns described above. SENs cannot take typical verbal / temporal modifiers otherwise found with AS-Ns (even in cases where there is a related verb, with the relevant temporal-aspectual modifiers):

(4) a. They met / played for two hours. b. the meeting / the play (*for two hours)

This suggests that SENs are not structurally derived from verbs, and hence if they involve an event, it cannot be inherited from a VP. Nevertheless, they do have an event interpretation which, it has been claimed in the literature, cf., [START_REF] Haas | Du verbe au nom: calques et décalages aspectuels[END_REF], can be tested in the context of, e.g. the take place predicate. Take place requires an eventive subject, and is compatible with both AS-Ns and SENs subjects, while rejecting R-Ns, as expected:

(5) a. The destruction took place at noon. (AS-Ns) b. The movie / meeting took place at noon.

(SENs) c. *The table / form took place at noon.

(R-Ns)

Another problematic group of nominalizations is also often associated with an event interpretation, namely -er nominals (see [START_REF] Hovav | -er nominals: Implications for a theory of argument structure[END_REF]Levin 1992, Alexiadou andSchäfer 2010, Roy andSoare (to appear)).

-Er nominals differ from AS-Ns in that they denote individuals (e.g., driver, teacher, scuba-diver). However, recent works by Alexiadou and Schäfer 2010 and Roy and Soare (to appear) have shown that some of them at least are interpreted in association with an actual eventuality. Independently of the typology one accepts (whether retaining three groups: episodic / dispositional / instruments, as in Roy and Soare (to appear) or just two groups based on the episodic / dispositional contrast alone, as in [START_REF] Alexiadou | On the syntax of episodic vs. dispositional -er nominals[END_REF]), there is a common agreement that some -er nominals at least relate to particular events, arguably inherited from their verbal base again. For instance, as commonly noted for English, phrasal -er nominals as in (6a), entail that the individual denoted by the N has taken part in the action expressed by the related verb (i.e., saved lives); whereas such entailment does not exist with the compound nominals as in (6b). One could hypothesize that the source of the event-related meaning for (6a) resides in the presence of an underlying event, plausibly derived from a full verbal phrase.

(6) a. a saver of lives (has saved lives) b. a life-saver (hasn't necessarily saved lives)

However, as for SENs, 'eventive' -er nominals do not take event modifiers otherwise possible with AS-Ns (compare (7) with (3) above):

(7) a. He drove the truck (for two hours). b. the driver of the truck (*for two hours)

Evidently, while there is a strong sense in which both AS-Ns and episodic -er nominals refer to events or are related to an event interpretation, they do not do so in the same way, as the diagnostics for eventivity clearly indicate. These facts further illustrate why in the present-day literature on nominalizations there is no consensus on the definition of eventive nominals and their variable properties. The aim of this paper is to gain some understanding into the semantic relationship derived nominals entertain with their verbal base, and to provide a principled analysis of AS-Ns, SENs and (eventive) -er nominals that accounts for the different flavors in which the interpretation of a deverbal nominal is said to be 'event-related'. We offer an analysis that bears crucially on a difference between strong/grammatical eventuality and lexical/conceptual eventuality cast in terms of a semantic type difference between entity-denoting vs. event-denoting nominals.

This paper is organized as follows. Section 2 deals with 'event' nominals, i.e., AS-Ns and SENs, providing a summary of the literature that will serve as a starting base for our discussion, and argues for a first distinction between strong/grammatical events and lexical/conceptual events. Section 3 turns to a detailed discussion of the properties of eventive -er nominals, which manifest event properties in a different way from event-denoting nominals. We first show that these nominals are event-related in a strong/grammatical sense, and that a unified structural account is warranted, for event-denoting and for -er AS-Ns as well. We proceed in section 4 to a type semantic analysis of derived nominals that captures the differences between individual nominals and event nominals and the interaction of semantic types with the grammatical vs. conceptual events. In section 5, we extend our proposal to include SENs, and then conclude in section 6.

Event nominals

AS-nominals

The literature on deverbal nominalizations starting with [START_REF] Lees | The Grammar of English Nominalizations[END_REF]; [START_REF] Chomsky | Remarks on nominalization[END_REF]; [START_REF] Grimshaw | Argument Structure[END_REF] pays special attention to the question of their ambiguity. Taking, as an illustration, -ation nominals (e.g., examination, destruction, manifestation), they may denote either an event or an entity (i.e., object), which may but must not be the result of an event. As stated above, this is commonly expressed in the literature under the form of the CENs / RNs distinction (initially proposed by [START_REF] Grimshaw | Argument Structure[END_REF], and is implemented broadly in terms of a structural ambiguity, as we will see below.

An overview of the properties distinguishing CENs from RNs is summarized in Table 1. Given the observed correlation between argument structure and eventive interpretation, in recent works on nominalizations (cf. [START_REF] Borer | The form, the forming and the formation of nominals[END_REF]Borer , 2003;;[START_REF] Alexiadou | Functional Structure in Nominals: nominalization and ergativity[END_REF]Alexiadou , 2010a,b;,b;Kornfilt and Whitman 2011, among others) the distinction has been restated in terms of Argument Supporting (or AS)-nominals and Referential (or R)-nominals (terminology from [START_REF] Borer | The form, the forming and the formation of nominals[END_REF]Borer , 2003)). The properties in the left column, including obligatory realization of the (internal) arguments and modification with aspectual modifiers, are generally seen as a hallmark for eventivity inside nominals. The properties are exemplified in (8) for AS-Ns and (9) for R-Ns.

AS-Ns

R-Ns As illustrated above in (8), in presence of event-related modifiers like frequent, constant adjectives or in/for-PPs, AS-Ns obligatorily realize their argument structure. Removing the arguments in the presence of the modifiers would give rise to ungrammaticality. This is not the case with R-Ns, which are noneventive and do not have arguments (9b). Frequent/constant modification is possible with R-Ns but in the plural (9c), which gives rise to an iterative reading only ("frequently giving/taking exams"; compare with (8c)). In/for-PPs are impossible. Furthermore, R-Ns can be selected by predicates that require an entity noun and not an eventive noun: [START_REF]For the syntactic derivation of -er nominals we assume the results of Roy and Soare[END_REF] a. *The examination of the patients was on the table.

(i) (ii) (iii) (iv) (v)
b. The exam was on the table.

For ambiguous nominals, such as assignment, painting, building, manifestation, the compatibility with be on the table excludes the presence of arguments:

(11) a. *The assignment of the tasks to the participants was on the table. b. The assignment was on the table.

The literature offers different views on the AS-N / R-N ambiguity. Lexicalist approaches take the ambiguity as being stored in lexical entries, and consequently assume the existence of assignment-AS-N / assignment-R-N pairs. This direction has been developed since [START_REF] Halle | Prolegomena to a Theory of Word Formation[END_REF] lexical Word Formation Rules, and continued in [START_REF] Booij | Dutch Morphology : A Study of Word Formation in Generative Grammar[END_REF], [START_REF] Aronoff | Word Formation in Generative Grammar[END_REF], Di [START_REF] Sciullo | On the Definition of Word[END_REF], among many others. By opposition, structural/syntactic approaches reject the idea of rampant ambiguity in the lexicon, and see the AS-N/R-N contrast as corresponding to a systematic structural difference in the form of the nominalization. The latter position is argued for by [START_REF] Marantz | No escape from syntax: don't try morphological analysis in the privacy of your own lexicon[END_REF], [START_REF] Borer | The form, the forming and the formation of nominals[END_REF], [START_REF] Alexiadou | Functional Structure in Nominals: nominalization and ergativity[END_REF], among others, which endorse a syntactic approach to word formation. Building on Grimshaw's criteria, it has been argued in this tradition that AS-Ns are derived on the basis of a full structure including verbal / aspectual layers; while R-Ns are simple, root-derived nominals. Syntactic approaches to deverbal nominals formation thus assume that the correlation between the eventive interpretation and the obligatory argument structure must be implemented by assigning different structural representations to the two classes of nominals. The correlation with the argument realization is therefore not accidental but derives from the internal syntactic properties of the relevant nominal expressions. The projection of argument structure inside deverbal nominals is also to be taken as a property of the verbal layers. These different layers have received different labels throughout the literature, from "Event Phrase" (van Hout and Roeper 1998), to different flavors of AspP [START_REF] Borer | The form, the forming and the formation of nominals[END_REF](Borer , 2003(Borer , 2005;;Alexiadou et al. 2010); and different executions have been proposed. For instance, [START_REF] Borer | The form, the forming and the formation of nominals[END_REF]Borer ( , 2003Borer ( , 2005)), implements the correlation between event structure and argument structure by proposing that arguments are introduced by functional heads, one of which is also responsible for introducing the event variable. In the structure of AS-Ns in (12) below, Asp Ev (standing for Aspect of Event) thus introduces the external argument and Asp Q (standing for Aspect of Quantity) the internal one (which is likewise severed from the root). Asp Ev is also responsible for introducing the event variable ev. In this paper, we will by and large adopt Borer's framework; but see [START_REF] Alexiadou | Functional Structure in Nominals: nominalization and ergativity[END_REF]; Van Hout and Roeper (1998) among others for alternative implementations.

(12) DP/NP (AS-Ns) [START_REF]A phase-based approach to nominalization seems relevant to account for the domains of adjunction and interpretation[END_REF], in turn, are built directly from a root. They lack verbal structure and, therefore, the event variable introduced by Asp Ev .

3 N Asp Ev P 3 Asp Ev Asp Q P -ation 3 ev Asp Q XP 4 form- R-nominals in
(

) DP/NP (R-Ns) 3 N XP -ation 4 form- 13
Recent work on AS-Ns denoting processes have, thus, reached the conclusion that eventivity in these nominals is structurally built-in, and that the projection of argument structure is also a consequence of their functional structure. The syntactic approaches to deverbal nominals formation share the idea that eventivity is encoded in the syntax. Therefore, we will refer to these cases as cases of "grammatical eventivity", in which the presence of the event is structure-related and results from the presence of dedicated verbal functional projections in the structure of the nominal, identifiable by aspectual and manner modification. We will call this structurally built-up eventivity 'strong/grammatical' eventivity.

Simple Event nominals

In her original typology of deverbal nominals, [START_REF] Grimshaw | Argument Structure[END_REF] distinguished not two, but three classes of deverbal nominals. Besides CENs and RNs, (here replaced by AS-Ns and R-Ns, respectively), her taxonomy includes a third class of so-called Simple Event Nominals (SENs). Nominals in the SENs class also denote events as they can combine with predicates like take place, last x time and be interrupted that take an event as a subject (cf. Haas et al. 2008) (14). According to this test, they pattern with AS-Ns (15) rather than R-Ns ( 16), leading many current researchers to class them with 'event' nominals:

(14) a. The concert/ the movie/ the game took place at nine.

(SENs) b. The concert / the movie/ the game lasted three hours. c. The concert/ the movie/ the game has been interrupted. (R-Ns) However, while the class of SENs represented by concert, movie, game in ( 14) above, shares with AS-Ns the property of being eventive (in a way to be defined later), they clearly do not necessarily project argument structure. Incidentally, it turns out that, as opposed to AS-Ns (and R-Ns for that matter) SENs may, but need not to, be derived from a verbal base (with or without derivational morphology) (e.g. a movie, a concert, a game vs. a meeting, an attack). SENs are thus eventive by the semantic tests above 5 , but not in the way AS-Ns are; i.e., presumably not in the strong/grammatical sense defined in the previous section. Recall that standard syntactic views on AS-Ns assume that what we call a 'grammatical event' must be contributed by an underlying verbal base (or VP), and is identified by the standard tests summarized in Table 1. SENs, which do not require a verbal base, by assumption, cannot involve a grammatical event.

Crucially, and as expected, SENs are not compatible with aspectual PP modifiers (in/for PP), and in that respect pattern with R-Ns (20) rather than AS-Ns ( 19), independently of the existence of a related verb (18a) or not (18b). 6 (18) a. the meeting/attack (*for three hours) (SENs) b. the concert/movie/boycott (*for three hours/months) (19) a. The president met with the Prime Minister (for three hours).

b. the meeting of the president with the Prime Minister (for three hours) (AS-Ns) (20) the paper/table (*for three hours) (R-Ns)

Further properties distinguish SENs from AS-Ns. Recall from Table 1 that R-Ns are compatible with frequency modifiers when in the plural only, while AS-Ns accept frequency modifiers in the singular. As (21) shows, in that respect again, SENs pattern with R-Ns in (9c), and not with AS-Ns in (8c).

(21) the frequent concert*(s); the frequent movie*(s) (SENs)

In general there is no particular restriction on plurality and quantification with SENs (as for R-Ns and other nominals: three exams; many dogs); while certain restrictions on quantifiers, numerals and determiners, as illustrated in (22b), are commonly reported on AS-Ns (see [START_REF] Grimshaw | Argument Structure[END_REF][START_REF] Snyder | On the aspectual properties of English derived nominals[END_REF]). 7

(22) a. many concerts; three movies (SENs) b. *several/two/these elections of John by the department (AS-Ns)

The count properties of SENs can be seen as a result of their being event sortals (cf. [START_REF] Bennett | Events and their Names[END_REF][START_REF] Snyder | On the aspectual properties of English derived nominals[END_REF]. The fact that SENs can be counted is correlated to the fact that they can be individuated, unlike AS-Ns. The contrast is visible in existential constructions, which require an individuated N, and accept SENs but reject AS-Ns (cf. also [START_REF] Mourelatos | Events, Processes and States[END_REF]:

(23) a. There is a movie/ are three movies starting at 5. b. *There is a destruction/ are three destructions of the city by the enemy starting at 5.

In sum, SENs have heterogeneous properties, sometimes similar to those of AS-Ns and sometimes not (and hence making them similar to R-Ns and other non-derived nominals). In view of these apparently contradictory properties, SENs have always been rather problematic and left aside in many recent accounts. If we follow a structural approach, as discussed earlier, and if we assume that both the projection of argument structure and the event interpretation depends on the presence of a verbal(/aspectual) structure, SENs do not involve a 'grammatical event', structurally built up in the nominal, in the sense defined in the previous section. We must conclude that there is another possible source of eventivity inside nominals, which is not structure-related. Nominals can refer to events in the absence of verbal bases and therefore of any verbal layers. We will name this kind of eventivity, which is not inherited from a base predicate, a weak/conceptual(or lexical) eventivity.

Interim conclusion

In order to describe event-related nominals, a first distinction is needed between strong/grammatical eventivity and weak/conceptual eventivity. Among the tests commonly used to identify an underlying event, or eventuality more generally, inside derived nominals, some pertain to the grammatical event, others to the conceptual/lexical event. The tests are split as indicated in Table 2. This understanding of the tests turns crucial to apprehend the properties of SENs specifically, and how they differ from AS-Ns. (More on this in Section 5). -Er derived nominals (often called 'Agent'-nominals) present a further difficulty to an already complex notion of eventuality inside nominals. On the one hand, they denote individuals (rather than events); but on the other hand they have a strong/grammatical eventuality that can be linked to an AS-Ns structure [START_REF] Alexiadou | On the syntax of episodic vs. dispositional -er nominals[END_REF]; Roy and Soare (to appear)).

Tests for underlying eventuality

Nominals denoting participants in an eventuality have been characterized in the literature as being sensitive to a distinction between eventive and noneventive, on the basis of pairs like saver of lives / lifesaver and mower of the lawn / lawn-mower [START_REF] Hovav | -er nominals: Implications for a theory of argument structure[END_REF]Levin 1992, Van Hout andRoeper 1998, among others). Only in the first case is the participant denoted by the nominal entailed to be involved in an actual event; no such entailment arises with the compound forms. Animacy plays a role here, as instrument -er nominals (grinder, blender) never involve a participation in an event (cf., Rappaport Hovav and Levin 1992; Roy and Soare (to appear)).

As argued in Roy and Soare (to appear), when interpreted as eventive, animate -er nominals have properties of strong/grammatical events rather than weak/conceptual events. This can be shown by the tests (iv) and (v) in Table 2, which discriminate between the two types of eventualities. With respect to these two tests (and we will come back to test (vi) later), eventive -er Ns pattern with AS-Ns (and not SENs). As argued by Rappaport Hovav and Levin, the eventive interpretation, which is highlighted by the presence of frequency modifiers, correlates with the obligatory realization of arguments. -Er nominals can take frequency modifiers, but only when they realize their arguments. 8 In addition, frequency adjectives are possible with the singular (24b). Compare with AS-Ns in (8c) above.

(24) a. the constant defenders *(of human rights) b. this frequent consumer *(of tobacco)

On the basis of the similarities between ( 24) and (8c), a unified account for eventive -er Ns and AS-Ns, in terms of strong/grammatical eventuality, seems plausible. Recent works have argued for such an account, but assume further distinctions within the class of eventive -er Ns -cf.

[ VoiceP x [ vP ev [ RootP √ ]]]]]
For Roy and Soare (to appear), dispositional and episodic -er Ns involve a full verbal structure akin to the one found in AS-Ns, and differ by the type of quantification on the event variable, namely existential vs. generic:

(26) a. Dispositional -er Ns GEN [ NP N [ AspEvP -er [ AspEv' AspEv ev [ AspQP [ RootP √ ]]]]] b. Episodic -er Ns ∃ [ NP N [ AspEvP -er [ AspEv' AspEv ev [ AspQP [ RootP √ ]]]]]]
They show, on the basis of French data, that both episodic and dispositional Ns allow event-related adjectival modification, which can be of two types; frequency adjectives, allowed by episodic -eur Ns only, and big/happy adjectives with an event-related meaning (cf., [START_REF] Larson | Events and modification in nominals[END_REF], allowed by both dispositional and episodic -eur Ns. The interpretive contrast between episodic and dispositional Ns comes from their internal argument, either specific or nonspecific, leading to a particular vs. generic underlying eventuality. For further details regarding adjectival modification, and their event-related meanings in particular, as well as the correlation between event type and nominal meanings, we refer the reader to Roy and Soare (to appear).

( a big grinder us would.be useful "A big grinder would be useful to us."

Moreover, instruments never project true arguments. In particular, definite-specific objects are always ruled out, which we take to indicate that instruments do not take arguments (30) and that when they appear with a de-phrase, the latter is a mere modifier (31). The nonargumental status of de-phrases with instruments is further supported by the possibility of substituting them with a purpose à-phrase adjunct (never found with true arguments).

(30) a. L'aspirateur (*de la poussière) n'a pas bien fonctionné. the.aspirator of the dust neg.has not well functioned "The vacuum-cleaner (of the dust) didn't work well" b. Le photocopieur (*de l'article) a été très efficace.

the photocopier of the.paper has been very efficient "The copy-machine (of the paper) has been very efficient"

(31) a. broyeur de végétaux vs. dresseur de lions blender of vegetables tamer of lions "vegetable blender" "lion tamer" b. broyeur à végétaux vs. *dresseur à lions blender at/to vegetables tamer at/to lions "vegetable blender" Accordingly, instrument -er Ns must be treated on a par with R-Ns, as simple, root-derived nominals. A structurally built-in grammatical event must be assumed in the two classes of eventive (animate) -eur Ns, which must share the structure of AS-Ns in (12). Instrument Ns pattern with rootderived nominals with which they share the structure [START_REF]A phase-based approach to nominalization seems relevant to account for the domains of adjunction and interpretation[END_REF]. Accordingly, they have the following structure, respectively:

(32) NP (Eventive -er Ns) 3 N Asp Ev P -eur 3 -eur Asp Ev ' x 3 Asp Ev Asp Q P ev 3 DP Asp Q ' 3 Asp Q RootP 4 √ (33) NP (Instrument Ns) 3 N RootP -eur 4 √
However, if episodic/dispositional -er nominals are a form of AS-Ns, involving a case of strong/grammatical event, some differences between process-denoting AS-Ns and individual-denoting eventive -er Ns need to be addressed. We turn to this issue below.

Some unexplained differences

The presence of a grammatical event inside -er Ns has often been questioned and is the subject of some controversies. Proponents of the noneventive view, invoke two types of evidence that they take as arguing against a unified treatment of process As-Ns and individual -er Ns. [START_REF] Baker | On agent nominalizations and why they are not like event nominalizations[END_REF] argue on the basis of the grammaticality of adverbials in pairs like (34) for separating process As-Ns and -er Ns, assigning a 'purely nominal' status to the latter, which, according to them, are deprived of any internal verbal structure (even in languages in which they are able to assign Accusative case to their object, like Sakha). Absence of adverbial modification is not a reliable test for absence of grammatical events, however, as adverbs are also precluded with many process AS-Ns (even in cases where they are semantically compatible with the base verb) (35). This contrast was originally noted for Greek by [START_REF] Alexiadou | Deriving words and categories[END_REF] (and reported in Alexiadou 2001) and taken as an indication of a diminished verbal character for -er nominals, even in their eventive meaning.

(38) a. *i damastes ton fotonion mesa se/gia enan eona the tamers the-gen photons within for a century b. *o katharistis tu ktiriu epi ena mina telika apolithike the cleaner the-gen building for a month finally got.fired [START_REF] Alexiadou | Deriving words and categories[END_REF] suggested that an explanation for the ungrammaticality of aspectual PPs would rely on the fact that -er Ns lack an Asp(ectual) projection, which would rule out adverbial modification across the board-and manner modification can only be spelled out as an adjective. This in turn, as also suggested by [START_REF] Alexiadou | Functional Structure in Nominals: nominalization and ergativity[END_REF], relates to the semantics of -er nominals, which denote individuals, while process nominals denote events. The difference is, thus, expected to the extent that aspect is relevant for processes and not for individuals. However, a precise implementation of the difference has never been proposed. In our view, and since we accept a split between eventive and noneventive (i.e., instrument) -er Ns, the issue remains to understand the ban on aspectual PPs with individual Ns, as they involve a strong/grammatical event. The properties of eventive -er Ns are the combined result, as we shall argue below, of their involving both a grammatical/structurally built-in event and an individual variable. We will turn to this account in the next section.

Event nominals and semantic types

Event vs. individual argument

One fundamental difference between eventive -er Ns and process AS-Ns that, we will argue, has a major bearing on their contrastive properties, concerns their denotations. Evidently, on the one hand -er Ns denote individuals (the driver = the person who drives), whereas on the other hand process AS-Ns denote events properly speaking (the driving of the car = the event of driving the car). The difference is associated to the semantic properties of the nominal suffixes themselves (-er vs. -ation, -ing, etc.), and has structural consequences. As argued in Roy and Soare (to appear), the nominalizing suffix -er, which picks out an individual, is assumed to realize the external argument (i.e., occupies the specifier of Asp Ev P; cf., (32) above). 10 Following [START_REF] Borer | The form, the forming and the formation of nominals[END_REF]Borer ( , 2003)), the nominalizing suffix -ation, for instance, which picks out an event, is the realization of the aspectual head Asp Ev responsible for introducing an eventuality. Hence, even though eventive -er Ns and process AS-Ns share the same internal structural frame (that of AS-Ns rather than root derived R-Ns), the semantic difference in their denotation is expressed structurally as well. Cf. the representations in (32) vs. ( 12).

We propose that the two types of nominals correspond to a semantic difference between nouns of individuals and nouns of events. Assuming that nominalized constructs are NPs, and that NPs are predicative by nature (while referentiality would require a DP layer), we claim that the former take an individual argument, hence are of type <e,t> (39); whereas the latter take an event argument, hence are of type <v,t> (40 For process AS-Ns, type <v,t>, the outcome of the nominalization is a (nominal) predicate of events (40). The event semantics is introduced by the Asp Ev phrase complement of N°. As with AS-Ns, Asp Ev also introduces the event component in eventive -er Ns (39); however, both differ in the semantics of their nominalizing suffix and hence the interpretation of their resulting nominalization. The individual reading in (39) leads to the participant/agent interpretation as often characterized. Importantly, the source of the eventive interpretation in both (eventive) -er Ns and process AS-Ns is the presence of the event variable associated with Asp Ev . Both -ation and (eventive) -er suffixes take constituents of type <v,t> as argument. Other -er nominals, i.e. instruments (see Roy and Soare (to appear)), are noneventive and do not involve an event variable at all. In that case, we will assume a homophonous -er suffix that is noneventive and takes a bare root as complement; the resulting nominalization is consequently of type <e,t> only:

(41) NP <e,t> 3 N RootP -er 4 √
The important point here is that both process AS-Ns and eventive -er nominals involve an event variable, and hence share a strong/grammatical eventuality interpretation. They only differ in the type of the outcome nominal. We claim in the rest of this section that this difference alone plays a crucial role in explaining the compatibility / incompatibility of the two sorts of eventive nominals (<e,t> vs. <v,t>) with event-related modifiers, namely aspectual PPs. The relevant data have been presented above and will now be discussed.

Locality of Predicate Modification

The puzzling difference between AS-Ns and eventive -er nominals concerning temporal/aspectual adjunct modifiers, has sometimes been taken as evidence that -er Ns are never eventive. We argue instead that they mark the type difference between <e,t> and <v,t> nominals, rather than the absence of underlying eventuality itself.

Temporal and aspectual event modifiers are structurally adjuncts. We assume that they combine with the nominal they modify via the rule of Predicate Modification (PM) stated in Heim and Kratzer (1998: 65).

(42) Predicate Modification

If α is a branching node, {β, γ} is the set of α's daughters, and β and γ are both in D <e,t> , then

α = λx ∈ D e . β (x) = γ (x) = 1.
PM is a conjunction operation. PM amounts to 'intersective modification' (i.e., Conjunctive composition) and captures the intersective reading of predicate modifiers:

(43) city in Texas a. λx ∈ D e . city (x) = in Texas (x) = 1 b. λx ∈ D e . x is a city and x is in Texas PM predicts that the intersective reading of an adjunct modifier and the nominal is only possible at the level where they merge. Importantly, however, PM is only applicable when the two constituents β and γ are of the same semantic type. In their original proposal, both the β and γ elements are of type <e,t> (for predicates of individuals). Here, however, we extend the system to include a type difference between predicates of events, type <v,t> and predicates of individuals, type <e,t>. True to the basic principle, PM is only possible between two expressions of the same <v,t> or <e,t> type.

If modifiers are adjoined at the Asp Ev P level (i.e., associated to the underlying grammatical eventuality; cf. ( 39)-( 40)), PM should be applicable in both eventive -er Ns and AS-Ns alike, and both classes of nominals should be equally compatible with the relevant aspectual PPs. The event modifying PPs are possible with AS-Ns but not with -er nominals, however. This suggests that the nominal type plays a role in allowing PM, and consequently that PM takes place at a level where the distinction is expressed. Concretely, it means, we propose, that adjunction takes place at the NP level, i.e. "after" nominalization rather than before nominalization.

The ban on aspectual PPs can be explained solely on the basis of the type difference between eventive nominals that take individuals or events. The basic intuition is that driver (type <e,t>) is not compatible with for two hours modifiers (type <v,t>) simply because it is a predicate of individuals and not of events. With process AS-Ns, the type of the PP modifier matches the type of the nominal and the rule of compositionality can be applied as in (44b As already discussed, this is excluded with eventive -er Ns because of type mismatch. If we wanted to adjoin an aspectual PP in the frame in (44), adjunction (and PM) could only take place at the Asp Ev P level (due to the type constraints). This situation has, however, one important consequence for event nominals and for the understanding of how eventive -er Ns and process AS-Ns differ in their respective interpretation, even though both involve an underlying grammatical eventuality. Very clear predictions are made in terms of interpretation of the adjuncts: the aspectual PPs can only be interpreted intersectively with respect to Asp Ev P, and not to the NP. In other terms, PPs will be intersective with the embedded event and not with the (complex) NP. Cases of event modifiers inside the NP are possible with -er Ns and have been noted in the literature on French nominalizations (cf., in particular [START_REF] Kerleroux | Afterword: Nominalizations in syntactic theory[END_REF]. They behave in a systematic way: they are intersective with respect to the inner event, but non-intersective (and that may include a variety of interpretations; e.g., subsective) with respect to the N itself. Consider the following example:

(47) les pêcheurs sous la glace (=subset of fishers) the fishers under the ice "under-ice fishers" (due to [START_REF] Kerleroux | Afterword: Nominalizations in syntactic theory[END_REF] It has been noted that the nominal in (47) can under no circumstances describe individuals that are fishing and located under the ice. However, the important point is that the locative PP is interpreted intersectively with respect to the fishing (and not the fisher(s)): the fishing must take place under the ice, while no location is specified for the fishers. Modifiers at the VP /AspP level will always lead to a nonintersective reading for NP (i.e. a subset). Accordingly, going back to the original examples, (48) is possible but only when understood as subclasses of a (prototypical) class of nominals, and not in an event interpretation. Concretely, (48a) for instance, cannot be interpreted as the x such that x is a runner and x is in 9 seconds (because type mismatch prevents PM from applying at the NP level); but can be interpreted (with more or less pragmatic felicity; cf. (48) vs. ( 49)) as a subclass of runners (i.e. those than run in less than 9 seconds, with respect to a contextually determined run or running).

(48) les sprinters en moins de 9 secondes the runners in less than 9 seconds "the runners in less than 9 seconds" (49) a. le donneur de sang (*?en cinq minutes) the giver of blood in five minutes "the blood donor (*?in five minutes)" b. le dompteur des lions (*?pendant des années) the tamer of.the lions for many years "the lion tamer (*?for years)"

To conclude, adjunct PPs (including aspectual in/for-PP) are never allowed with -er Ns, as adjunction is precluded at the NP level. If adjunction takes place it can only be at the Asp Ev P level, leading systematically to a subsective interpretation with respect to NP (but intersective with respect to the lower Asp Ev P). The subsective reading, however, is constrained by pragmatic reasons. Nominalization forms a local domain where the meaning is computed first and then further modifiers are possible, provided that they are of the right semantic type for PM to apply. Adjunction at the Asp Ev P level is possible but is interpreted as intersective with respect to the event only (via PM); adjunction is, in this case, not visible/accessible for the individual. 13 Our results confirm what has been claimed in the literature since [START_REF] Grimshaw | Argument Structure[END_REF]; Van Hout and Roeper (1998); [START_REF] Borer | The form, the forming and the formation of nominals[END_REF], namely that aspectual modifiers signal the presence of an underlying aspectual/verbal structure. However, the underlying event is only visible to adjuncts if the nominalization expresses a predicate of events and not of individuals. For a nominal to be built on an underlying event (hence a verbal/aspectual structure) does not equate to express a predicate of events. In that sense, there is no incompatibility between the fact that -er Ns denote individuals and the fact they, nevertheless, involve a grammatical event.

Extension to Simple Event nominals (SENs)

This view of events inside nominals, forced by semantic compositionality, allows us in turn to gain some understanding of the Simple Event nominals (SENs) traditionally left aside as problematic cases. Recall that SENs are interpreted as related to an event (e.g., movie, meeting, concert), yet they do not pass the tests for a strong/grammatical eventuality, but only the tests for a weak/conceptual eventuality: while they do accept predicates like be interrupted, last x time, and enter in the during the N construction, they do not (i) project arguments, (ii) allow frequency adjectives in the singular, (iii) allow PP aspectual modifiers like in/for x time (cf., Table 2).

Since SENs lack a grammatical event, they are not syntactically derived from a verbal/aspectual structure and we assume that they are simply formed from a root (whether they are morphologically complex as in the case of meeting or not, as in concert, movie, attack). Accordingly, they pattern structurally with R-Ns (including instrument -er Ns) rather than AS-Ns. Cf. ( 41). If this is correct, then the difference between SENs and AS-Ns boils down to the same semantic type difference between <e,t> nominals on the one hand and <v,t> nominals on the other. What we have described as grammatical vs. conceptual eventuality interacts with the type difference: conceptual eventuality is found with nominals that are of the <e,t> type, whereas grammatical eventuality is found with event denoting nominals that are of type <v,t>. In other words, SENs differ from AS-Ns in that they take an individual as argument (rather than an event); it just happens that for SENs that individual variable is an abstract entity, conceptually an event (rather than a concrete object as with table, book, and so on). Accordingly, SENs share properties with other R-Ns that are associated with reference to individual entities (including abstract ones): they are count and allow discrete quantification (three movies, many concerts; cf. (22a)), they do not take frequency adjectives in the singular (*the frequent concert; cf. ( 21)) and do not take aspectual in/for PPs (52b). They differ, however, from other R-Ns in appearing with predicates like took place, last x time which seek for an event-denoting subject. However, this is only the result of their denoting abstract conceptual events (rather than concrete entities). In terms of the nominalization, for As-Ns, (51a) and (51b) are structurally and semantically related: the nominal form in (b) is derived from the verbal form in (a) and hence they share common semantic features. By contrast, for SENs, (52a) and (52b) are only conceptually related in the sense that their roots share the same conceptual/lexical content, but do not have internal grammatical structure.

(51) a. On a construit la cathédrale (en 100 ans). one has built the cathedral in 100 years b. La construction de la cathédrale (en 100 ans) the building of the cathedral in 100 years (52) a. Les membres du projet se sont réunis (pendant 3 heures). the members of.the project refl have met for 3 hours b. La/une réunion des membres du projet (*pendant 3 heures) the/a meeting of.the members of.the project for 3 hours

As earlier, the incompatibility of SENs with in/for PPs derives from a type mismatch between <e,t> nominals and <v,t> type adjuncts. Nothing special needs to be said of SENs in that respect; nor regarding frequency modification. As expected, SENs accept frequency adjectives when in the plural only, and thus pattern with R-Ns. The frequent modifier is adjoined at the NP level and forces pluralization of the individual with <e,t> type Ns. By contrast, recall that frequency adjectives do not force the plural on the nominal when they quantify over the inner event introduced by Asp Ev P in eventive -er Ns and AS-Ns.

In sum, SENs can be straightforwardly integrated in our type semantic account as <e,t> Ns and their apparently mixed properties can be derived from their semantic type and the special kind of abstract object they denote.

Conclusion

To conclude, event-related nominals (and nominalizations) form a rather heterogeneous group that is traditionally split into three coherent classes: AS-Ns, SENs, eventive -er Ns. They share event related properties that distinguish them from noneventive nominals altogether (R-Ns). The distinct properties of the three groups of event-related nominals can be accounted for on the basis of two interacting notions of event inside nominals. On the one hand, we have argued that a fundamental difference exists between grammatical eventuality, associated to the structural projection of VP/AspP and hence a verbal syntactic base, and conceptual eventuality that is expressed lexically on roots. On the other hand, the semantic type of the outcome of nominalization turns out crucial in distinguishing nominals that denote individuals (type <e,t>) and those that denote events (type <v,t>). The two notions interact in a very straightforward way, leading to the typology of nominals in Table 3.

Nominals of type <e,t> come in three flavours. They may not involve any event (and thus be interpreted as concrete entities); or involve an underlying eventuality, which can be a conceptual one only (SENs) or a grammatical one (eventive -er Ns). For nominals of type <v,t> the logically possible combinations are much more restricted, however. As <v,t> nominals are eventive in the strong/grammatical sense (i.e., they involve an event variable that is introduced, by assumption, structurally), they require a grammatical event: <v,t>. They cannot involve a conceptual event or no event at all. The attested classes of nominals are, thus, precisely the ones that we should expect in our system.

NP type

  examination of the students by the teachers b. the examination *(of the students) (by the teachers) (in three hours) c. the (frequent) examination of the students by the teachers (9) R-Ns a. the form; the exam b. the exam (*by the teachers) (*in three hours) c. the frequent exam*(s)

(

  15) a. The examination of the papers by the committee took place today at 5pm. (AS-Ns) b. The examination of the papers by the committee lasted three hours. c. The examination of the papers by the committee has been interrupted. (16) a. *The paper/ table took place yesterday. (R-Ns) b. *The paper/ table lasted three hours. 4 c. *The paper/ table has been interrupted. SENs also pattern with AS-Ns in being satisfactory in the during the N PP construction which calls for a temporal extension: (17) a. during the movie/concert/game (SENs) b. during the examination of the paper by the committee (AS-Ns) c. *during the paper/table

(

  34) a. finding the wallet quickly b. *the finder of the wallet quickly (35) a. the enemy found/destroyed the city quickly b. the finding/destruction of the city by the enemy (*quickly) Another piece of evidence taken to argue against a unified treatment of process As-Ns and -er Ns concerns the test (vi) in

( 46 )

 46 the destruction of the city by the enemy in 3 days a. λe ∈ D v . destruction of the city by the enemy (e) = in 3 days (e) =1 b. λe ∈ D v . e is a destruction of the city by the enemy and e is (completed) in 3 days. 12

Table 1 : properties of AS-nominals and R-nominals

 1

	event reading	no event reading
	obligatory arguments	arguments not obligatory
	compatible with aspectual	not compatible with aspectual
	modifiers like in three hours	modifiers
	constant, frequent with the	constant, frequent possible only
	singular	with the plural
	by-phrase is an argument	by-phrase is not an argument

Table 2 : Tests for strong/grammatical eventuality vs. weak/conceptual eventuality 3. Further issue: individual nominals 3.1. Eventive -er nominals

 2

		Strong/	Weak/
		Grammatical	Conceptual
		eventuality	eventuality
	(i) subject of be on the table	-	-
	(ii) subject of take place, be
	interrupted	+	+
	(iii) during the N	+	+
	(iv) obligatory arguments	+	-
	(v) constant, frequent possible
	with the singular	+	-
	(vi) compatible with aspectual	+	-
	modifiers like in/for three hours

  Crucially, no event-related properties can be observed in the case of instrument -eur nominals. Event-related meanings of adjectives are never allowed. Instruments differ in a clear way from dispositional Ns in (27).

	(29) Instruments 9
	a. *Un broyeur fréquent nous serait utile.
	a grinder frequent us would.be useful
	"A frequent grinder would be useful to us."
	b. *Un gros broyeur nous serait utile.
	27) Dispositional -er Ns
	a. *Nous avons interviewé un vendeur fréquent de voitures/ les
	we have interviewed a seller frequent of cars	the
	consommateurs fréquents de drogue.
	consumers	frequent of drug
	"We have interviewed a frequent car-dealer/ the frequent drug
	users."
	b. Nous avons interviewé un petit vendeur de voitures/ les
	we have interviewed a small dealer of cars	the
	gros consommateurs de drogue.
	big consumers	of drugs
	"We have interviewed a small car-dealer/ the big drug users."
	(28) Episodic -er Ns
	a. Un consommateur fréquent de plusieurs drogues douces/ de
	a consumer	frequent of several drugs soft	of
	LSD a témoigné au	procès.
	LSD has testified at.the trial
	"A frequent user of several soft drugs/ of LSD testified in
	court."
	b. Un heureux/ gros consommateur de plusieurs drogues douces/
	a happy big user	of several drugs soft
	de LSD a témoigné au procès.
	of LSD has testified	at.the trial
	"A happy/big user of several soft drugs/of LSD testified in
	court."

Table 2

 2

	: eventive -er Ns

  ).

	While for eventive -er Ns, the type of the event modifying PP mismatches
	that of the nominal, which prevents PM from deriving the compositional
	meaning of the nominal complex:
	(45) a. *the painter of the room in three days
	b.		*NP
		qp
		NP <e,t>	PP <v,t>
	3	4
	N	Asp Ev P	in three days
	-er	3
		-er	Asp Ev ' 3
		Asp Ev	Asp Q P 3
			DP	RootP
				4
				√
	By definition, PM is a local compositional rule. Aspectual PPs can only be
	interpreted intersectively with respect to the predicate they immediately
	modify. Since aspectual PPs can only be interpreted intersectively with
	respect to the eventuality (and only the eventuality) they are directly
	combined with, structurally, it must correspond to the eventuality
	introduced by the functional projection they are directly adjoined to. (44) a. the destruction of the city by the enemy in three days b. Hence, modifiers adjoined at the NP level are interpreted intersectively NP qp with NP. This is only possible with AS-Ns: aspectual PPs are intersective
	with the noun:	NP <v,t>	PP <v,t>
	3	4
	N	Asp Ev P	in three days
	-ation	3
		DP	Asp Ev ' 3
			Asp Ev	Asp Q P
			-ation	3
				DP	RootP
				4
				√

Table 3 : Typology of eventive and noneventive nominals

 3

		Underlying	Nominal form
		eventuality
	<e,t>	conceptual	SENs:
		eventuality	movie, play, concert
	<e,t>	grammatical	eventive -er Ns:
		eventuality:	driver, consumer
		AspEvP <v,t>	(e.g., the driver of the truck to Paris)
	<e,t>	no eventuality	R-Ns (concrete individual entities):
			table; exam; boy
	<v,t>	conceptual	**impossible
		eventuality
	<v,t>	grammatical	process AS-Ns:
		eventuality:	destruction, examination, forming
		AspEvP <v,t>	(e.g., the destruction of the city by the
			enemy)
	<v,t>	no eventuality	**impossible

We use the following abbreviations: ev-event; √-Root; gen-Genitive, reflreflexive pronoun. 3 We use the terms 'event' and 'eventivity' in a loose sense that does not discriminate between events properly speaking and states, and interchangeably with the term 'eventuality' introduced by Bach (1986). 4 There is an interpretation for (16b) in which lasted 3 hours applies to the lifetime of the subject (here a concrete entity) and not to an event duration per se. Nevertheless, the conclusion that R-Ns are different from both SENs and AS-Ns is supported by their respective behavior with the other predicates, namely take place, be interrupted, among others. 5 Similarly, the literature invokes the subject position of occur, start or finish (see e.g. Vendler 1967, Snyder 1998 among many others). We take all these tests as broadly indicating semantic eventivity in nominals, and do not broach on further semantic distinctions like the one between events and propositions, pointed at in the literature. 6 As pointed out to us by a reviewer, SENs are compatible with another type of apparently temporal modifiers, namely of x time. Structurally, this modifier is not a VP modifier, however, and involves clear nominal modification; e.g. a meeting/concert/movie of three hours in length; we leave it aside at it is not relevant to the question of an internal grammatical event.

7 Recent works on pluralization have shown that AS-Ns may sometimes accept plurals and discrete quantification when the nominals denote a bounded event; Borer (2005); Alexiadou et al. (2010). What is important here is that no such requirement is made for SENs. 8 As discussed in the literature, frequency adjectives are often ambiguous between (at least) three readings: internal, adverbial and generic interpretations (cf., in particular, [START_REF] Gehrke | Frequency adjectives as distributional modifiers[END_REF]. Typical cases of frequency adjective + N, that do not involve argument structure (e.g., an occasional sailor, an occasional beer) are generic or adverbial. We are not concerned with these cases here, and refer the reader to Roy and Soare (to appear) for further discussion.


Karel De Vogeleer

Gerard Memmi
email: gerard.memmi@telecom-paristech.fr

Pierre Jouvelot

Fabien Coelho
email: fabien.coelho@mines-paristech.fr

The Energy/Frequency Convexity Rule: Modeling and Experimental Validation on Mobile Devices

Keywords: DVFS, energy measurements, power measurements

This paper provides both theoretical and experimental evidence for the existence of an Energy/Frequency Convexity Rule, which relates energy consumption and CPU frequency on mobile devices. We monitored a typical smartphone running a specific computing-intensive kernel of multiple nested loops written in C using a high-resolution power gauge. Data gathered during a week-long acquisition campaign suggest that energy consumed per input element is strongly correlated with CPU frequency, and, more interestingly, the curve exhibits a clear minimum over a 0.2 GHz to 1.6 GHz window. We provide and motivate an analytical model for this behavior, which fits well with the data. Our work should be of clear interest to researchers focusing on energy usage and minimization for mobile devices, and provide new insights for optimization opportunities.

Introduction

The service uptime of battery-powered devices, e.g., smartphones, is a sensitive issue for nearly any user [START_REF] Ickin | Factors influencing quality of experience of commonly used mobile applications[END_REF]. Even though battery capacity and performance are hoped to increase steadily over time, improving the energy efficiency of current battery-powered systems is essential because users expect right now communication devices to provide data access every time, everywhere to everyone. Understanding the energy consumption of the different features of (battery-powered) computer systems is thus a key issue. Providing models for energy consumption can pave the way to energy optimization, by design and at run time.

The power consumption of Central Processing Units (CPUs) and external memory systems is application and user behavior dependent [START_REF] Carroll | An analysis of power consumption in a smartphone[END_REF]. Moreover, for cache-intensive and CPU-bound applications, or for specific Dynamic Voltage and Frequency Scaling (DVFS) settings, the CPU energy consumption may dominate the external memory consumption [START_REF] Snowdon | Power management and dynamic voltage scaling: Myths and facts[END_REF]. For example, Aaron and Carroll [START_REF] Carroll | An analysis of power consumption in a smartphone[END_REF] showed that, for an embedded system running equake, vpr, and gzip from the SPEC CPU2000 benchmark suite, the CPU energy consumption exceeds the RAM memory consumption, whereas crafty and mcf from the same suite showed to be straining more energy from the device RAM memory.

Providing an accurate model of energy consumption for embedded and, more generally, energy-limited devices such as mobile phones is of key import to both users and system designers. To reach that goal, our paper provides both theoretical and first experimental evidence for the existence of an Energy/Frequency Convexity Rule, that relates energy consumption and CPU frequency on mobile devices. This convexity property seems to ensure the existence of an optimal frequency where energy usage is minimal.

This existence claim is based on both theoretical and practical evidence. More specifically, we monitored a Samsung Galaxy SII smartphone running Gold-Rader's Bit Reverse algorithm [START_REF] Gold | Digital processing of signals[END_REF], a small kernel based on multiple nested loops written in C, with a high-resolution power gauge from Monsoon Solutions Inc. Data gathered during a week-long acquisition campaign suggest that energy consumed per input element is strongly correlated with CPU frequency and, more interestingly, that the corresponding curve exhibits a clear minimum over a 0.2 GHz to 1.6 GHz window. We also provide and motivate an analytical model of this behavior, which fits well with the data. Our work should be of clear interest to researchers focusing on energy usage and minimization on mobile devices, and provide new insights for optimization opportunities.

The paper is organized as follows. Section 2 introduces the notions of energy and power, and how these can be decomposed in different components on electronic devices. Section 3 describes the power measurement protocol and methodology driving our experiments, and the C benchmark we used. Section 4 introduces our CPU energy consumption model, and shows that it fits well with the data. Section 5 outlines the Energy/Frequency Rule derived from our experiment and modeling. Related work is surveyed in Section 6. We conclude and discuss future work in Section 7.

Power Usage in Computer Systems

The total power P total consumed by a computer system, including a CPU, may be separated into two components: P total = P system + P CPU , where P CPU is consumed by the CPU itself and P system by the rest of system. In a batterypowered hand-held computer device P system may include the power needed to light the LCD display, to enable and maintain I/O devices (including memory), to keep sensors online (GPS, gyro-sensors etc.), and others.

The power consumption P CPU of the CPU we focus on here can be divided into two parts: P CPU = P dynamic +P leak , where P dynamic is the power consumed by the CPU during the switching activities of transistors during computation. P leak is power originating from leakage effects inherent to silicon-based transistors, and is in essence not useful for the CPU's purposes. P dynamic may be split into the power P short lost when transistors briefly short-circuit during gate state changes and P charge , needed to charge the gates' capacitors: P dynamic = P short +P charge . In the literature P charge is usually [START_REF] Weste | Principles of CMOS VLSI design: a systems perspective[END_REF] defined as α Cf V 2 , where α is a proportional constant indicating the percentage of the system that is active or switching, C the capacitance of the system, f the frequency at which the system is switching and V the voltage swing across C. P short originates during the toggling of a logic gate. During this switching, the transistors inside the gate may conduct simultaneously for a very short time, creating a direct path between V CC and the ground. Even though this peak current happens over a very small time interval, given current high clock frequencies and large amount of logic gates, the short-circuit current may be non-negligible. Quantifying P short is gate specific but it may be approximated by deeming it proportional to P charge . Thus the power P dynamic stemming from the switching activities and the short-circuit currents in a CPU is thus P charge + (η -1)P charge , i.e., η •αC L f V 2 , where η is a scaling factor representing the effects of short-circuit power.

P leak originates from leakage currents that flow between differently doped parts of a metal-oxide semiconductor field-effect transistor (MOSFET), the basic building block of CPUs. The energy in these currents are lost and do not contribute to the information that is held by the transistor. Some leakage currents are induced during the on or off -state of the transistor, or both. Six distinct sources of leakage are identified [START_REF] Liu | BSIM 4.1.0 MOSFET model-user's manual[END_REF]. Despite the presence of multiple sources of leakage in MOSFET transistors, the sub-threshold leakage current, gate leakage, and band-to-band tunneling (BTBT) dominate the others for sub-100 nm technologies [START_REF] Agarwal | Leakage power analysis and reduction: models, estimation and tools[END_REF]. Leakage current models, e.g., as incorporated in the BSIM [START_REF] Liu | BSIM 4.1.0 MOSFET model-user's manual[END_REF] micro models, are accurate yet complex since they depend on multiple variables. Moreover, P leak fluctuates constantly as it also depends on the temperature of the system. Consequently P leak cannot be considered a static part of the system's power consumption. Given the different sources of power consumption in a MOSFET based CPU, the potal power can be rewritten as P total = P system +P leak +P dynamic .

The relationship between the power P (t) (Watts or Joules/s) and the energy E(∆t) (Joules) consumed by an electrical system over a time period ∆t is given by

E(∆t) = ∆t 0 P (t) dt = ∆t 0 I(t) • V (t) dt, (1)
where I(t) is the current supplied to the system, and V (t) the voltage drop over the system. Often V (t) is constant over time, hence P (t) only depends on I(t).

If both current and voltage are constant over time, the energy integral becomes the product of voltage, current and time, or alternatively power and time.

Power Measurement Protocol on Mobile Devices

A Samsung Galaxy S2 is used in our testbed sporting the Samsung Exynos 4 Systems-on-Chip (SoC) 45 nm dual-core. The Galaxy S2 has a 32 KB L1 data and instruction cache, and a 1 MB L2 cache. The mobile device runs Android 4.0.3 on the Siyah kernel adopting Linux 3.0.31. The frequency scaling governor in Linux was set to operate in ondemand mode to prevent frequency and voltage scaling on-the-fly. The second CPU core was disabled during measurements. The smartphone is booted in clockwork recovery mode to minimize noisy side-effects of the Operating System (OS) and other frameworks.

During the experiments, the phone's battery was replaced by a power supply (Monsoon Power Monitor) that measures the power consumption at 5 kHz with an accuracy of 1 mW. The power of the system and the temperature of the CPU were simultaneously logged. The kernel was patched to print a temperature sample to the kernel debug output at a rate of 2 Hz.

The bit-reverse algorithm is used as benchmark kernel. This is an important operation since it is part of the ubiquitous Fast Fourier Transformation (FFT) algorithm, and rearranges deterministically elements in an array. The bit-reversal kernel is CPU intensive, induces cache effects, and is economically pertinent. The Gold-Rader implementation of the bit-reverse algorithm, often considered the reference implementation [START_REF] Gold | Digital processing of signals[END_REF], is given below:

void bitreverse_gold_rader (int N, complex *data) { int n = N, nm1 = n-1; int i = 0, j = 0; for (; i < nm1; i++) { int k = n >> 1; if (i < j) { complex temp = data[i]; data[i] = data[j]; data[j] = temp; } while (k <= j) { j -= k; k >>= 1; } j += k; } }
The input of the bit-reversal algorithm is an array with a size of 2 N ; the elements are pairs of 32 bit integers, representing complex numbers. Note that array sizes up to 2 10 fit in the L1 cache, while sizes over 2 17 are too big to fit in the L2 cache.

During the measurements, N is set between 6 and 20 in steps of 2, while varying the CPU frequency from 0.2 GHz to 1.6 GHz in steps of 0.1.

To minimize overhead, 128 copies of the kernel are run sequentially. For time measurement purposes, this benchmark is repeated 32 times for at least 3 seconds each time (this may require multiple runs of the 128 copies). For the power and temperature measurements, the benchmark is repeated in an infinite loop until 32 samples can be gathered. The benchmark is compiled with GCC 4.6, included in Google's NDK, generating ARMv5 thumb code.

Modeling Energy Consumption

Energy is the product of time by power. We look at each of these factors in turn here.

Execution Time

Since applications run over an OS, we need to take account for it when estimating computing time. Indeed, an OS needs a specific amount of time, or clock cycles, to perform (periodical) tasks, e.g., interrupt handling, process scheduling, processing kernel events, managing memory etc. When the processor is not spending time in kernel mode, the processor is available for user-space programs, e.g., our benchmark. From a heuristic point of view, it can be assumed that the OS kernel needs a fixed amount of clock cycles cc k per time unit to complete its tasks. Thus, we propose to model the amount of clock cycles to complete a benchmark sequence of instructions cc b as t(f β -cc k ), where cc k are the number of clock cycles spent in the OS, t the total time needed to complete the program, f the system's clock frequency and β an architecture-dependent scaling constant, to be fitted later on with the data. The definition of cc b is rewritten to isolate the execution time:

t = cc b f β -cc k . ( 2
)
Note that t tends to zero for f → ∞ and there is a vertical asymptote at β √ cc k .

Table 1 shows the fitting errors of Equation 2 on the execution time measurement data, averaged over all tested input sizes. The fitting exhibits a vertical asymptote around 115 MHz. This may indicate the minimum amount of clock cycles required by the OS of the phone to operate. The measurement data for input sizes 2 6 up to 2 16 are well described by Equation 2. However, sizes 2 18 and 2 20 , too large to fit within cache L2, seem to operate under different laws. Therefore, from now on, the attention is focused on data that fit in the cache of the CPU.

Power Consumption

If dynamic power modeling is rather easy (see Section 2), the case for leakage is more involved, and warrant a longer presentation. In particular, leakage power is heavily temperature-dependent [START_REF] Liu | BSIM 4.1.0 MOSFET model-user's manual[END_REF]. For example, our CPU at 1.3 GHz shows an inflated power consumption of around 5% between a CPU temperature of 36 • C and 46 • C. You et al. [START_REF] You | Compiler analysis and supports for leakage power reduction on microprocessors[END_REF] shows similar results for a 0.1µm processor; a temperature increase from 30 • C to 40 • C leads to a 3% power increase. On the other Table 1. Average absolute execution time (t), power (P ), and energy (E) fitting errors (%) of Equation 2, Equation 4, and Equation 5 respectively, on the measured data given different CPU frequencies (f) at a 37 • C core temperature. f (GHz) 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1. [START_REF] Gold | Digital processing of signals[END_REF] hand, the power P charge required for a given computation does not change with regards to the CPU temperature. The Berkeley Short-channel IGFET Model (BSIM) [START_REF] Liu | BSIM 4.1.0 MOSFET model-user's manual[END_REF] shows that the leakage current micro models depend on a multitude of variables. The temperature itself appears several times in the sub-threshold and BTBT leakage models; the gate leakage however is not temperature dependent. Mukhopadhyay et al. [START_REF] Mukhopadhyay | Accurate estimation of total leakage current in scaled cmos logic circuits based on compact current modeling[END_REF] showed via simulation that for 25 nm technology the sub-threshold leakage current is dominant over the BTBT leakage current, but the latter cannot be neglected. Under normal conditions, the temperature of the CPU's silicon varies continuously depending on the load of the CPU and the system's ambient temperature. Therefore, to have a fair comparison of energy consumption between different code pieces one needs to compare the measurements at a reference temperature.

Finding a temperature scaling factor for the leakage current is however not a straightforward task. Nevertheless, approximative scaling factors have been analytically obtained or experimentally defined via simulations (mainly SPICE) [START_REF] Su | Full chip leakage estimation considering power supply and temperature variations[END_REF][START_REF] Liao | Temperature and supply voltage aware performance and power modeling at microarchitecture level[END_REF][START_REF] Ferre | Characterization of leakage power in cmos technologies[END_REF]. After analysis on our data, we discovered that none of the cited approximations would fit well. This is because the rationale on which these approximations are based assume conditions, which are not entirely realistic, to simplify the leakage current micro models. Most previous research works focus solely on the sub-threshold leakage effect, neglecting other leakage effects. This may be appropriate for technologies larger than the 45 nm technology we use.

Skadron et al. [START_REF] Skadron | Temperature-aware microarchitecture: Modeling and implementation[END_REF] studied the temperature dependence of I leak as well. Skadron et al. deducted a relationship between the leakage power P leak and dynamic power P dynamic based on International Technology Roadmap for Semiconductors (ITRS) measurement traces (variables indexed with 0 are reference values):

R T = P leak P dynamic = R 0 V 0 T 2 0 e B T 0 V T 2 e -B
T .

(

) 3
If the temperature T is stable across different operating voltages, then the value of R T is a function of V multiplied by a constant γ, which includes the temperature dependent variables and other constants. Total power P total is thus:

P total = P system + P leak + P dynamic = P system + γV P dynamic + P dynamic

= P system + (1 + γV ) • ηαCf V 2 . ( 4
)
This formulation of P total incorporates three parameters: P system , γ, and ηαC.

The values of these variables can be obtained via fitting power traces on Equation 4. V and f are linked via the DVFS process inherent to the Linux kernel and the hardware technicalities. Experimental values for our CPU are found inside the Siyah kernel; they are shown in Table 2. The power fitting errors are shown in Table 1 for a 37 • C CPU temperature. The fitting errors are on the average not larger than 3 % except for the measurement point at 1.5 GHz. This measurement point was obtained at different independent occasions but appears, for obscure reasons, to disobey persistently the model in Equation 4.

Energy Consumption

Typical compute-intensive programs incur approximately a constant load on the CPU and system, barring user interactions. Moreover, if the time to complete one program is also much smaller than the sampling rate of the power gauge, then P (t) in Equation 1is constant. Hence, it suffices to sample the power P bench of a benchmark at a given CPU temperature and multiply this value by the execution time of the benchmark t bench to get an energy estimate. As a result the definition of time in Equation 2, and power in Equation 4, can be used to model the energy of one benchmark kernel. The energy consumed by the CPU E CPU is given by

E CPU = E leak + E dynamic = P bench • t bench = (1 + γV ) • ηαCf V 2 • cc b f β -cc k . (5)
Constants γ, ηαC, cc b , and cc k in this formulation were evaluated before via fitting.

The Energy/Frequency Convexity Rule

Using the testbed and models described above, Figure 5 shows the measured and modeled energy E CPU for our benchmark kernel over the different frequencies; data have been normalized over the benchmark input size. Table 1 shows the average absolute energy error between our fitted model and the measured data.

The average fitting error stays below 6 % except for measurement points 1.5 GHz and 200 MHz. The large fitting error in the 200 MHz case stems from the large execution time that amplifies the power measurement fitting error (see Table 1). It can also be seen that, for larger benchmark input sizes, on the average more energy is required. This is the result of higher level cache utilization. Figure 5 exhibits a clear convex curve, with a minimum at Frequency f opt , suggesting the existence of an Energy/Frequency Convexity Rule for computeintensive programs. Why is the energy consumption curve convex? The energy consumption of the benchmark kernel scales approximately linearly with the number of instructions. The time ∆t it takes to execute an instruction sequence increases more than linearly with decreasing operating frequency. P leak is independent of the type of computation, and E leak builds up linearly with time: E leak = P leak ∆t. P leak becomes increasingly important in the part where the CPU frequency f is smaller than f opt . For the part where f > f opt , the inflated E CPU can be attributed to the increasing supply voltage V CC affecting P dynamic quadratically. Furthermore, had P system been incorporated in the picture, then f opt would have moved to a higher frequency because the additional consumed energy of the system could have been minimized by a faster completion of the computations on the CPU.

Our proposal for the existence of an Energy/Frequency Convexity Rule can be further supported using our previous models. Indeed, we can model the relationship in Table 2 between the frequency (GHz) and voltage (V) in the Linux kernel with a linear approximation: V = m 1 f + m 2 . Now the derivative of E CPU defined in Equation 5 over f or V can be computed. The energy curve shows a global minimum E CPU,min for f opt when its derivative is equal to zero (∂E CPU /∂f = 0) and its second derivative is positive.

Given that E CPU only shows one minimum, f opt is the global minimum if the following equality holds:

(1 + γV )V f β β f β -cc k = f m 1 (3γV + 2) + (1 + γV )V. (6)
Four parameters appear in this formulation that affect the optimal frequency f opt : β and cc k , which are related to the execution time of the benchmark, m 1 the slope between V and f , and γ related to the leakage current ratio. Simulations show that, if β or cc k decreases, E CPU,min will shift to a higher frequency, and, if m 1 or γ decreases, f opt will decrease as well. γ is temperature dependent; if the temperature increases, γ will increase accordingly. Hence, E CPU,min and f opt increase with temperature as well. For the presented measurements Equation 5shows a minimum on the average around 700 MHz. This holds for all input sizes of the benchmark between 2 6 and 2 16 . As a result, this implies that there exists an operating frequency, which is neither the maximum nor the minimum operating frequency, at which the CPU would execute a code sequence on the top of the OS in the most energy efficient way.

Related Work

The convex property of the energy consumption curve has been hinted at before in the literature. A series of papers, approaching the problem from an architectural point of view, have suggested a convex energy consumption curve with respect to DVFS [START_REF] Snowdon | Power management and dynamic voltage scaling: Myths and facts[END_REF][START_REF] Fan | The synergy between power-aware memory systems and processor voltage scaling[END_REF]. The authors put forward some motivation for the convexity of the curve, but do not provide an analytical framework. A detailed explanation or an analytical derivation, as presented here, is not given however.

In the Very-large-scale Integration (VLSI) design domain voltage scaling has also been discussed but usually for a fixed frequency [START_REF] Zhai | Theoretical and practical limits of dynamic voltage scaling[END_REF][START_REF] Calhoun | Sub-threshold design: The challenges of minimizing circuit energy[END_REF]. The aim of the voltage scaling is to find a minimum energy operation point where the digital circuit yields the correct output. The major trade-off is between increasing circuit latency and leakage power, and decreasing dynamic power. This trade-off yields also a convex energy consumption curve, but for a fixed frequency.

Conclusion

We provide an analytical model to describe the energy consumption of a code sequence running on top of the OS of a mobile device. The energy model is parametrized over five parameters abstracting the specifics of the Dynamic Voltage and Frequency Scaling (DVFS) process, the execution time related parameters, and the power specifications of the CPU. Measurement traces from a mobile device were used to validate the appropriately fitted model. It is shown that the model is on the average more than 6 % accurate. The importance of power samples obtained at a reference temperature is also pointed out.

It is also shown that the analytical energy model is convex (representing what we call the Energy/Frequency Convexity Rule) and yields a minimum energy consumption of a code sequence for a given CPU operation frequency. This minimum is a function of the temperature, execution time related parameters, and technical parameters related to the hardware. A more in depth analysis of the Energy/Frequency Convexity Rule can be found in our technical report [START_REF] Vogeleer | The energy/frequency convexity rule: Modeling and experimental validation on mobile devices[END_REF].

Future work includes checking the validity of our model and its parameters over a wide range of compute-intensive benchmarks. Also, extending the presented model to better handle memory access operations, in particular the impact of caches, is deserved. Finally a generalization of the model to encompass the impact of other programs running in parallel with benchmarks or system power effects would be useful.

Fig. 1 .

 1 Fig.1. Energy required by the CPU at 37 • C to complete our benchmark kernel given an input size. The dashed lines denote the theoretical curve as per Equation5.

Table 2 .

 2 Frequency and voltage relationship for the Dynamic Voltage and Frequency Scaling (DVFS) process in the default Siyah kernel.

	f (MHz) 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600
	V (mV) 920 950 950 950 975 1000 1025 1075 1125 1175 1225 1250 1275 1325 1350