Matthieu Gallet

Mathias Jacquelin

Loris Marchal

Scheduling complex streaming applications on the Cell processor

In this paper, we consider the problem of scheduling streaming applications described by complex task graphs on a heterogeneous multicore processor, the STI Cell BE processor. We first present a theoretical model of the Cell processor. Then, we use this model to express the problem of maximizing the throughput of a streaming application on this processor. Although the problem is proven NP-complete, we present an optimal solution based on mixed linear programming. This allows us to compute the optimal mapping for a number of applications, ranging from a real audio encoder to complex random task graphs. These mappings are then tested on two platforms embedding Cell processors, and compared to simple heuristic solutions. We show that we are able to achieve a good speed-up, whereas the heuristic solutions generally fail to deal with the strong memory and communication constraints.

Introduction

The last decade has seen the arrival of multicore processors in every computer and electronic device, from the personal computer to the high-performance computing cluster. Nowadays, heterogeneous multicore processor are emerging. Future processors are likely to embed several specialpurpose cores -like networking or graphic cores-together with general cores, in order to tackle problems like heat dissipation, computing capacity or power consumption. Deploying an application on this kind of platform becomes a challenging task due to the increasing heterogeneity.

Heterogeneous computing platforms such as Grids have been available for a decade or two. However, the heterogeneity is now likely to exist at a much smaller scale, within a machine, or even a processor. Major actors of the CPU industry are already planning to include a GPU core 1 to their multicore processors [START_REF]AMD Fusion[END_REF]. Classical processors are also often provided with an accelerator (like GPUs, graphics processing units), or with processors dedicated to special computations (like ClearSpeed [START_REF]ClearSpeed technology[END_REF] or Mercury cards [START_REF]Mercury technology[END_REF]), thus resulting in a heterogeneous platform. The best example is probably the IBM RoadRunner, the current leader of the Top500 ranking [21], which is composed of an heterogeneous collection of classical AMD Opteron processors and Cell processors.

The STI Cell BE processor is an example of such an heterogeneous architecture, since it embeds both a PowerPC processing unit, and up to eight simpler cores dedicated to vectorial computing. Moreover, the Cell processor is widely available and affordable. This is why we focus our study on this heterogeneous multicore processor.

Deploying an application on such a heterogeneous platform is not an easy task, especially when the application is not purely data-parallel. In this work, we focus on applications which exhibit some regularity, so that we can design efficient static scheduling solutions. We thus concentrate our work on streaming applications. These applications usually concern multimedia stream processing, like video edition softwares, web radios or Video On Demand applications [START_REF] Wu | On optimal resource utilization for distributed remote visualization[END_REF][START_REF] Hary | Precedence-constrained task allocation onto point-to-point networks for pipelined execution[END_REF]. However, streaming applications also exist in other domains, like real time data encryption applications, or routing softwares, required by cell phones for example [START_REF] Thies | Language and Compiler Support for Stream Programs[END_REF]. A stream is a sequence of data that have to go through several processing tasks. The application is generally structured as a directed acyclic task graph; this can be a simple chain of tasks, or a more complex structure, as illustrated in the following.

To process a streaming application on a heterogeneous platform, we have to decide which tasks will be processed on which processing elements, that is, to find a mapping of the tasks onto the platform. This is a complex problem since we have to take platform heterogeneity, task computing requirements, and communication volume into account. The objective is to optimize the throughput of the application: for example in the case of a video stream, we are looking for a solution that maximizes the number of images processed per time-unit.

Several stream solutions have already been developed or adapted for the Cell processor. DataCutter-Lite [START_REF] Hartley | A component-based framework for the Cell broadband engine[END_REF] is an adaptation of the DataCutter framework for the Cell processor, but it is limited to simple streaming applications described as linear chains, so it cannot deal with complex task graphs. StreamIt [START_REF] Hang | A streaming computation framework for the Cell processor[END_REF][START_REF]Streamit project[END_REF] is a language developed to model streaming applications; a version of the Streamit compiler has been developed for the Cell processor, however it does not allow the user to specify the mapping of the application, and thus to precisely control the application. Some other frameworks allow to handle communications and are rather dedicated to matrix operations, like ALF [START_REF]Accelerated library framework[END_REF], Sequoia [START_REF] Fatahalian | Sequoia: Programming the memory hierarchy[END_REF], CellSs [START_REF] Bellens | CellSs: a programming model for the Cell BE architecture[END_REF] or BlockLib [START_REF] Ålind | BlockLib: a skeleton library for Cell broadband engine[END_REF].

In previous work, we have studied how to map complex workflows onto a set of heterogeneous resources, in the context of computing Grids. In particular, in [START_REF] Gallet | Efficient scheduling of task graph collections on heterogeneous resources[END_REF], we explain how to compute an optimal mapping, that is a mapping reaching the optimal throughput. This is achieved using steady-state scheduling [START_REF] Beaumont | Steady-state scheduling[END_REF]: the activity of each resource (processing element or communication links) is bounded using linear constraints, and a mixed linear program (with integer and rational variables) gathering these constraints has to be solved to derive the optimal mapping. In the present paper, we show that steady-state scheduling meets the needs of an efficient scheduler for streaming application on heterogeneous processors, although new issues have to be solved due to the completely different granularity of the tasks.

The rest of this paper is organized as follows: Section 2 presents in details the Cell processor together with a model of its operation, as well as our hypotheses for streaming applications. Then, we expose a theoretical complexity study of the problem in Section 3. Section 4 introduces some implementation choices that have an impact on the constraints for a good mapping. Section 5 then presents our optimal solution, obtained through the resolution of a mixed linear program. Finally, Section 6 presents the results of our experiments.

Platform and application model

In this section, we detail our view of the Cell processor, and introduce useful notations. In a second step, we also present the model of the streaming application.

Cell processor model

As said in the introduction, the Cell is a heterogeneous multicore processor. It has jointly been developed by Sony Computer Entertainment, Toshiba, and IBM [START_REF] Kahle | Introduction to the cell multiprocessor[END_REF], and embeds the following components:

• Power core. Also known as the PPE (standing for Power Processing Element) and respecting the Power ISA 2.03 standard. This core is two-way multithreaded and its main role is to control the other cores, and to be used by the OS due to its similarity with existing Power processors. We do not a priori limit our study to only one Cell processor, so we consider platforms which may include n P PPE cores PPE 0 , . . . , PPE n P .

• Synergistic Processing Elements (SPE) cores. These cores constitute the main innovation of the Cell processor and are small 128-bit RISC processors specialized in floating point, SIMD operations. These differences induce that some tasks are by far faster when processed on a SPE, while some other tasks can be slower • Main memory. Only PPEs have a transparent access to main memory. The dedicated memory controller is integrated in the Cell processor and allows a fast access to the requested data. Since this memory is by far larger than the SPE's local stores, we do not consider its limited size as a constraint for the mapping of the application.

• Element Interconnect Bus (EIB). This ring bus links all parts of the Cell processor to each other. The EIB has an aggregated bandwidth BW = 200 GB/s, and each component is connected to the EIB through a bidirectional interface, with a bandwidth bw = 25 GB/s in each direction.

All these components are displayed in a schematic view on Figure 1(a). To simplify formulas, we gather all processing elements under the same notation PE i , so that the set of PPEs is PPEs = {PE 0 , . . . , PE n P -1 }, while SPEs = {PE n P , . . . , PE n P +n S -1 } is the set of SPEs. Let n be the total number of processing elements, i.e., n = n P + n S . We have two classes of processing elements, which fall under to the unrelated computation model: a PPE can be fast for a given task T k and slow for another one T l , while a SPE can be slower for T k but faster for T l . Communication model. Since the aggregated bandwidth of the EIB bus is equal to the sum of the bandwidth of all the interfaces (when we have all 8 interfaces), we assume in the following that this bus is not a constraint and that no contention occurs between communications. This is optimistic, since the structure of the bus may prevent irregular communication patterns to fully use its bandwidth, but we keep this model as a starting point. We will see in the evaluation that this model is precise enough to accurately compute an optimal schedule. As all communication elements are fully bidirectional, we use a bidirectional bounded-multiport model, with linear communication cost: a data of size S is sent (or received) in time S/b, where b is the bandwidth used for this communication, and the sum of incoming (respectively outgoing communications) of any element does not exceed its bandwidth in that direction. Note that memory accesses have to be counted as communications since they use the same interfaces.

EIB

Due to the limited size of the DMA stack on each SPE, each SPE can issue at most 16 simultaneous DMA calls. Similarly, each SPE has a separate stack for communications between itself and a PPE, which can handle at most eight simultaneous DMA calls.

Each core owns a dedicated communication interface (a DMA engine for the SPEs and a memory controller for the PPEs), and communications can thus be overlapped with computations.

Summarized theoretical model for the complexity study. In the following theoretical study, the Cell processor is therefore modeled by a set of processing elements as described on Figure 1(b). Each processing elements is provided with two communications interfaces in charge of the incoming and outgoing communications, with limited bandwidth B in q = B out q = bw . As we have seen above, this is the only contention point for communications. Communications can be overlapped with computations. Moreover, computation costs are modeled using the unrelated-machine model.

Application model

In this work, we target streaming applications. A stream is a sequence of instances, such as images in the case of a video stream. Our objective is to maximize the throughput of the application, that is the number of instances processed per time-unit.

As a simple example of a streaming application, we can think of a stream which must go through a simple chain of tasks, as depicted on Figure 2(a): in this application all instances of the stream must go through two tasks, such as two filters to apply to all images of a video stream. Streaming applications may be more complex, as described on Figure 2(b), and we model the structure of the application with a Directed Acyclic Graph G A = (V A , E A ). The set V A of nodes corresponds to tasks T 1 , . . . , T K . The set E A of edges models the dependencies between tasks, and the associated data: the edge from T k to T l is denoted by D k,l . A data D k,l , of size data k,l (in bytes), models a dependency between two task T k and T l , so that the processing of the ith instance of task T l requires the data corresponding to the ith instance of data D l,k produced by T k . Moreover, it may well be the case that T l also requires the results of a few instances following the ith instance. In other words, T l may need information on the near future (i.e., the next instances) before actually processing an instance. For example, this happens in video encoding softwares, when the program only encodes the difference between two images. We denote by peek k the number of such instances, that is, we need instances i, i + 1, . . . , i + peek k of D k,l to process the ith instance of T l . This number of following instances is important not only when constructing the actual schedule and synchronizing the processing elements, but also when computing the mapping, because of the limited size of local memories where temporary data are stored.

We also take into account communication between tasks and the main memory; we note read k the number of bytes read in memory by each instance of task T k , and write k the number of bytes task T k writes to memory.

Finally, since computing speeds of PPEs and SPEs are unrelated, w P P E (T k ) (respectively w SP E (T k )) denotes the time required for a PPE (resp. an SPE) to complete a single instance of T k . As all SPEs and all PPEs are identical, these two values totally describe the computation requirements. Note that the processing times of tasks (as well as the size of the data exchanged by tasks) are instance independent.

3 Problem definition and complexity analysis

Definitions: mapping and schedule

As explained above, our goal is to deploy a complex streaming application, described by a task graph, on a heterogeneous multicore architecture, under the objective of throughput maximization. To completely described the deployment of the application, we have to provide both a mapping and a schedule. The mapping describes where each task will be processed, whereas the schedule specifies when. such a mapping, all instances of a given task T k are thus processed on the same processing element. We could also use a more general scheme, with different instances of the same task processed on different processing elements. This could help improving the throughput, but it would require to described the mapping of each instance of each task. We have studied this problem earlier, and provided a polynomial-time algorithm to solve it under some constraints on the task graph [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF]. However, using a general mapping scheme has several drawbacks: it requires a complex flow control in order to route all messages, it induces larger buffers, and it involves a lot more communications when a task T k with peek k > 0 (i.e., a task which needs data from several instances to process a single instance) is replicated on several processing elements. Therefore, using a general mapping is not suited with the target architecture, which requires simple control and small communications, due to the limited size of the local memories. In this study, we thus concentrate on schedules describes by a simple mapping of tasks to processing elements.

1 T 4 T 3 T 7 T 6 T 5 T 2 T 9 T 8 (b) Other streaming application. PE 4 PE 2 PE 1 PE 3 T 1 T 4 T 3 T 7 T 6 T 5 T 2 T 9 T 8 (c) A possible mapping.
D 1,2 peek 3 =1 T 3 T 2 D 1,3 T 1 PE 2 PE 1
(a) Application and mapping. peek 1 = peek 2 = 0 and peek 3 = 1 Given a mapping, we can reconstruct a complete periodic schedule as illustrated on Figure 3.

T 2 T 1 D 1 ,2 D 1 ,3 T 3 T 2 T 1 D 1 ,2 D 1 ,3 T 3 T 2 T 1 D 1 ,2 D 1 ,3 T 1 T 2 T 1 D 1 ,2 D 1 ,3 T 1 D 1 ,2 D 1 ,3 0 1 2 3 4 PE 2 PE 1 T 5 period (b) Periodic schedule.
After a few periods for initialization, each processing element enters a steady state: a processing element in charge of a task T k simultaneously processes one instance of T k , sends the result D k,l of the previous instance to the processing element in charge of each successor task T l , and receives the data D j,k of the next instance from the processing element in charge of each predecessor task T j . The exact construction of this periodic schedule is detailed in [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF] for general mappings. In our case, the construction of the schedule is more straightforward: a processing element PE i in charge of a task T k simply processes it as soon as its input data is available, i.e., as soon as PE i has received the data for the current instance and potentially the peek k following ones. Note that since we use a bounded-multiport model for communication, we do not need to precisely schedule the communications inside a period. All communications can happen simultaneously as soon as the average bandwidth needed during the period does not exceed the bandwidth bound on each interface. We denote by T the duration of a period in the obtained schedule. In this schedule, a new instance is processed every T time-units, thus the throughput of this schedule is ρ = 1/T .

Complexity of the problem

In the previous section, we have seen that the mapping of an application onto the computing platform totally defines the schedule and its throughput ρ. In this section, we discuss the complexity of the problem of finding a mapping with optimal throughput. In this section, we forget about memory constraints, and constraints on the number of DMA transfers, as explained in Section 2.1: those constraints are not needed to prove that the problem is difficult. The associated decision problem is formally defined as follows.

Definition 1 (Cell-Mapping). Given a directed acyclic application graph G A , a Cell processor with n P PPE cores and n S SPE cores and a bound B, is there a mapping with throughput ρ ≥ B? Theorem 1. Cell-Mapping is NP-complete in the strong sense.

Proof. First note that we can check in polynomial time if a mapping has a given throughput: we simply have to make sure that the occupation time of each resource (processing element or communication interface) for processing one instance is not larger than 1/B. Thus, this problem belongs to the NP class.

We prove the NP-completeness using a straightforward reduction from the Minimum Multiprocessor Scheduling problem restricted to two machines, which is known to be NP-complete even with a fixed number of machines [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. An instance I 1 of Minimum Multiprocessor Scheduling with two machines consists in n tasks T 1 , . . . , T n provided with a length l(k, i) for each task T k and each processor i = 1, 2, and a bound B ′ . The goal is to find an allocation f of the tasks on the processors such that k,f (k)=i l(k, i) ≤ B for each processor i = 1, 2.

We construct an instance I 2 of our problem with one PPE (corresponding to processor 1) and one SPE (corresponding to processor 2). The streaming application consists in a simple chain of n tasks: V A = {T 1 , . . . , T n } and there is a dependency D k,k+1 for all k = 1, . . . n -1. The computation times are w P P E (T t ) = l(t, 1) and w SP E (T t ) = l(t, 2), and communication costs are neglected: data k,k+1 = 0 for all k = 1, . . . n -1. Finally, we set B = 1/B ′ . The construction of I 2 is obviously polynomial.

Assume that I 1 has a solution f . Then, f defines a mapping of the tasks onto the processing elements. Using this mapping, the maximum occupation time of each processing element is at most B. Therefore, the throughput of this mapping is at least 1/B = B ′ . f is thus a solution for instance I 1 . Similarly, a solution for I 2 is to a solution for I 1 .

The proof does not make use of communications:the problem is NP-complete even without any communication costs. Note that the restriction of Minimum Multiprocessor Scheduling with a fixed number of machines admits a fully polynomial approximation scheme (FPTAS) [START_REF] Horowitz | Exact and approximate algorithms for scheduling nonidentical processors[END_REF]. However, when considering a general application, communications have to be mapped together with computations, and the previous FPTAS cannot be applied. In spite of the NP-completeness of the problem, and thanks to the limited number of processing elements, we will show in Section 5 that a solution using Mixed Integer Programing allows to compute the optimal solution in a reasonable time.

Implementation choices

In this section, we relate the implementation choices made when designing our scheduler that impacts the optimization problem: we need to clarify these choices before we can express the constraints on memory, and the constraints on the number of communications from and to SPEs. There are two main issues: how to handle asynchronous communications and how to compute a bound on the buffer sizes.

Communications and DMA calls

The Cell processor has very specific constraints, especially on communications between cores. Even if SPEs are able to receive and send data while they are doing some computation, they are not multi-threaded and the computation must be interrupted to initiate a communication (but the computation is resumed immediately after the initialization of the communication). There are two ways to transfer data from a core to another:

1. The sender writes data into the destination local store; 2. The receiver reads data from the source local store. This method is a bit faster, so it is preferred to the former. Due to the absence of auto-interruption mechanism, the thread running on each SPE has regularly to suspend its computation and check the status of current DMA calls. Moreover, as presented in Section 2.1, the DMA stack on each SPE has a limited size. A SPE can issue at most 16 simultaneous DMA calls, and can handle at most 8 simultaneous DMA calls issued by the PPEs. Furthermore, when building a steady-state schedule, we do not want to precisely order communications among processing elements, since it would require a lot of synchronizations. On the contrary, we assume that all the communications of a given period may happen simultaneously. These communications correspond to edges D k,l of the task graph when tasks T k and T l are not mapped on the same processing element. With the previous limitation on concurrent DMA calls, this induces a strong limitation on the mapping: each SPE is able to receive at most 16 different data, and to send at most 8 data to PPEs per period.

Determining buffer sizes

Since SPEs have only 256 kB of local store, memory constraints on the mapping are tight. We need to precisely model them by computing the exact buffer sizes required by the application.

Mainly for technical reasons, the code of the whole application is replicated in the local stores of SPEs (of limited size LS) and in the memory shared by PPEs. We denote by code the size of the code which is deployed on each SPE, so that the available memory for buffers is LS -code. A SPE processing a task T k has to devote a part of its memory to the buffers for incoming data D j,k , as well as for outgoing data D k,l . Note that both buffers have to be allocated into the SPE's memory even if one of the neighbor tasks T j or T l is mapped on the same SPE. In a future optimization, we could save memory by avoiding the duplication of buffers for neighbor tasks mapped on the same SPE.

As we have seen in Section 3.1, before computing an instance of a task T k , a processing element has to receive all the corresponding data, that is the data D j,k produced by each predecessor task T j , both for the current instance and for the peek k following instances. Thus, the results of several instances need to be stored during the execution, because processing elements are not synchronized on the same instance. In order to compute the number of stored data, we first compute the index of the period in the schedule when the first instance of T k is processed. The index of this period is denoted by firstPeriod (T k ), and is expressed by:

firstPeriod (T k ) = 0 if T k has no predecessor, max D j,k firstPeriod (T j ) + peek k + 2 otherwise.
All predecessors of an instance of task T k are processed after max D j,k firstPeriod (T j ) + 1 periods. We have also to wait for peek k additional periods if some following instances are needed, plus one period for the communication from the processing element handling the data, hence the result. By induction on the structure of the task graph, this allows to compute firstPeriod for all tasks. For example, with the task graph and mapping described on Figure 3, we have firstPeriod (1) = 0, firstPeriod (2) = 2, and firstPeriod (3) = 4. Again, we could have avoided the additional period dedicated for communication when tasks are mapped on the same processor (e.g., we could have firstPeriod (3) = 3), but we let this optimization for future work to keep our scheduling framework simple.

Once the firstPeriod (T k ) value of a task T k is known, buffer sizes can be computed. For a given data D k,l , the number of temporary instances of this data that have to be stored in the system if firstPeriod (T l ) -firstPeriod (T k ). Thus, the size of the buffer needed to store this data is buff k,l = data k,l × (firstPeriod (T l ) -firstPeriod (T k )).

Optimal mapping through mixed linear programming

In this section, we present a mixed linear programming approach that allows to compute a mapping with optimal throughput. This study is adapted from [START_REF] Gallet | Efficient scheduling of task graph collections on heterogeneous resources[END_REF], but takes into account the specific constraints of the Cell processor. The problem is expressed as a linear program where integer and rational variables coexist. Although the problem remains NP-complete, in practice, some softwares are able to solve such linear programs [START_REF]ILOG CPLEX: High-performance software for mathematical programming and optimization[END_REF]. Indeed, thanks to the limited number of processing elements in the Cell processor, we are able to compute the optimal solution for task graphs of reasonable size (up to a few hundreds of tasks).

Our linear programming formulation makes use of both integer and rational variables. The integer variables are described below. They can only take values 0 or 1.

• α's variables which characterize where each task is processed: α k i = 1 if and only if task T k is mapped on processing element PE i . • β's variables which characterize the mapping of data transfers: β k,l i,j = 1 if and only if data D k,l is transfered from PE i to PE j (note that the same processing element may well handle both task if i = j). Obviously, these variables are related. In particular, β k,l i,j = α k i × α l j , but this redundancy allows us to express the problem as a set of linear constraints. The objective of the linear program is to minimize the duration T of a period, which corresponds to maximizing the throughput ρ = 1/T . The intuition behind the linear program is detailed below. Remember that processing elements PE 0 ,. . . ,PE n P -1 are PPEs whereasPE n P ,. . . ,PE n are SPEs.

• Constraints (1a) define the domain of each variable: α and β lie in {0, 1}, while T is rational.

• Constraint (1b) states that each task is mapped on exactly one processing element.

• Constraint (1c) asserts that the processing element computing a task holds all necessary input data. • Constraint (1d) asserts that a processing element can send the output data of a task only if it processes the corresponding task. • Constraint (1e) ensures that the computing time of each PPE is no larger that T , and Constraint (1f) does the same for each SPE. • Constraint (1g) states that all incoming communication have to be completed within time T , and Constraint (1h) does the same for outgoing communications. • Constraint (1i) ensures that all temporary buffers allocated on the SPEs fit into their local stores. • Constraint (1j) states that a SPE can perform at most 16 simultaneous incoming DMA calls, and Constraint (1k) makes sure that at most eight simultaneous DMA calls are issued by PPEs on each SPE.

                                                       MINIMIZE T UNDER THE CONSTRAINTS (1a) ∀D k,l , ∀PE i and PE j , α k i ∈ {0, 1}, β k,l i,j ∈ {0, 1} (1b) ∀T k , n-1 i=0 α k i = 1 (1c) ∀D k,l , ∀j, 0 ≤ j ≤ n -1, n-1 i=0 (β k,l i,j ) ≥ α l j (1d) ∀D k,l , ∀i, 0 ≤ i ≤ n -1, n-1 j=0 (β k,l i,j ) ≤ α k i (1e) ∀i, 0 ≤ i < n P , T k (α k i w P P E (T k )) ≤ T (1f) ∀i, n P ≤ i < n, T k (α k i w SP E (T k )) ≤ T (1g) ∀i, 0 ≤ i < n, α k i read k + D k,l 0≤j<n,j =i (β k,l j,i data k,l ) ≤ T × bw (1h) ∀i, 0 ≤ i < n, α k i write k + D k,l 0≤j<n,j =i (β k,l i,j data k,l ) ≤ T × bw (1i) ∀i, n P ≤ i < n, T k α k i D k,l buff k,l + D l,k buff l,k ≤ LS -code (1j) ∀j, n P ≤ j < n, 0≤i<n,i =j D k,l β k,l i,j ≤ 16 (1k) ∀i, n P ≤ i < n, 0≤j<n P D k,l β k,l i,j ≤ 8 (1)
We denote ρ opt = 1/T opt , where T opt is the value of T in any optimal solution of Linear Program (1), with O(n 2 ) variables and O(n 2 ) constraints. The following theorem states that ρ opt is the maximum achievable throughput. Theorem 2. An optimal solution of Linear Program (1) describes a mapping with maximal throughput.

Proof. Consider an optimal solution of Linear Program (1), with throughput ρ opt = 1/T opt . Thanks to the constraints of the linear program, this solution defines a valid mapping with period T opt . As we have seen before, this corresponds to a schedule with throughput ρ opt .

We now consider any possible mapping of the application onto the processing elements, and the associated schedule. We define α k i = 1 if task T k is mapped on processing element PE i in this mapping, and 0 otherwise. We also define β k,l i,j = α k i × α l j . We finally consider the period T achieved by the schedule associated with this mapping. Since T is a valid period for this mapping, these variables satisfies all constraints of Linear Program (1). α, β and T are then a solution of the linear program. Thus, T ≤ T opt and this mapping has a throughput 1/T which is not larger than the ρ opt .

Experimental validation

To assess the quality of both our model and our scheduling strategy, we conduct several experiments. We used two hardware platforms: a Sony PlayStation 3, and an IBM QS22. The Sony PlayStation 3 is a video game console built around a single Cell processor, with only 6 usable SPEs and a single Power core. The IBM QS22 is a high performance computing server built on top of two Cell processors connected through a high performance interface and sharing main memory. Using both Cell processors generates many new difficulties, both for software development (moving threads on particular PPEs) and platform modeling (especially for communication contention between both Cell processors). Therefore, we first focus on optimizing the performance for a single Cell processor, and we will adapt our study to several processors in a future work. Thus, in the experiments, the number of PPE is n P = 1 and the number of SPEs n S may vary from zero to eight (or six on the PlayStation 3). For our experiments, we use ILOG CPLEX [START_REF]ILOG CPLEX: High-performance software for mathematical programming and optimization[END_REF] to solve the linear program introduced in the previous section. In order to reduce the computation time for solving the linear program, we used the ability of CPLEX to stop its computation as soon as its solution is within 5% of the optimal solution. While this significantly reduces the average resolution time, it still offers a very good solution. Using this feature, the time for solving a linear program was always kept below one minute (mostly around 20 seconds), which is negligible in front of the duration of a stream application.

Scheduling software

Together with these hardware platforms, we also need a software framework to execute our schedules while handling communications. If there already exist some frameworks dedicated to streaming applications [START_REF] Hang | A streaming computation framework for the Cell processor[END_REF][START_REF] Hartley | A component-based framework for the Cell broadband engine[END_REF], none of them is able to deal with complex task graphs while allowing to statically select the mapping. Thus, we have decided to develop one1 . Our scheduler only requires as input parameters the description of the task graph, its mapping on the platform, and the code of each task. Even if it was designed to use the mapping returned by the linear program, it can also use any other mapping, such as the heuristic strategies described below.

We now briefly describe our scheduler, which is mainly divided into two main phases: the computation phase, during which the scheduler selects a task and processes it, and the communication phase, during which the scheduler performs asynchronous communications. These steps, depicted on Figure 4, are executed by every processing element. Moreover, since communications have to be overlapped with computations, our scheduler cyclically alternates between those two phases.

The computation phase, which is shown on Figure 4(a), begins with the selection of a runnable task according to the provided schedule, then it waits for the required resources (input data and output buffers) to be available. If all required resources are available, the selected task is processed, otherwise, it moves to the communication phase. Whenever new data is produced, the scheduler signals it to every dependent processing elements.

The communication phase, depicted in Figure 4(b), aims at performing every incoming communication, most often by issuing DMA calls. Therefore, the scheduler begins by watching every previously issued DMA call in order to unlock the output buffer of the sender when data had been received. Then, the scheduler checks whether there is new incoming data. In that case, and if enough input buffers are available, it issues the proper "Get" command.

To obtain a valid and efficient implementation of this scheduler, we had to overcome several issues due to the very particular nature of the Cell processor. First, the main issue is heterogeneity: Mappings generated through linear programming achieves the best speed-up, and they also offer the best scalability among every mappings. For these task graphs, we reach a speed-up between 2 and 3 using 8 SPEs, while the heuristics reaches a maximum speed-up of 1.3. This shows that it is crucial to take data transfers into account when designing mapping strategies. However, our complex strategy based on linear programming and using a better model of the platform is able to get good performance out of this complex architecture.

Influence of the communication-to-computation ratio

We now test the performance of the mapping computed with the mixed linear program, for different values of the communication-to-computation (CCR). The speed-up when using the 8 SPEs of the QS22 are presented on Figure 8. We see that the larger the CCR, the more difficult to get a good speed-up. Indeed, when communications are predominant, it is hard to distribute tasks among SPEs and to reach a decent throughput. Eventually, the best policy is to map all tasks to the PPE. In conclusion, our experiments demonstrate the usefulness of our approach on the Cell. High are obtained whenever the CCR of the application is sufficiently low, and our mappings offer better performance and scalability compare to the heuristics we have implemented.

Conclusion

In this paper, we have studied the scheduling of streaming applications on a heterogeneous multicore processor: the STI Cell processor. The first challenge was to come up with a realistic and yet tractable model of the Cell processor. We have designed such a model, and we have used it to express the optimization problem of finding a mapping with maximal throughput. This problem has been proven NP-complete, and we have designed a formulation of the problem as a mixed linear program. By solving this linear program with appropriate tools, we can compute a mapping with optimal throughput. In a second step, we have implemented a complete scheduling framework to deploy streaming applications on the Cell processor. This framework allows the user to deploy any streaming application, described by a potentially complex task graph, on a Cell processor, given any mapping of the application to the platform. Thanks to this scheduling framework, we have been able to test our scheduling strategy, and to compare it to simpler heuristic strategies. We have shown that our strategy reaches 95% of the throughput predicted by the linear program, that our approach has a good and scalable speed-up when using up to 8 SPEs, and that our strategy clearly outperforms the simple heuristics, which are unable to deal with the complex mapping problem. Overall, this demonstrates that scheduling a complex application on a heterogeneous multicore processor is a challenging task, but that scheduling tools can help to achieve good performance.

This work has several natural extensions, and we have already started to study some of them. First, several optimizations of the scheduling framework could be implemented to achieve even better performance, such as limiting buffer sizes for neighbors tasks mapped on the same processing elements. Then, we need to extend and refine the model we have presented in this paper to more complex platforms. For example, we would like to be able to use both Cell processors of the QS22, or even a cluster of QS22 machines. On the long view, we would like to adapt our model and framework to other heterogeneous multicore platforms. Finally, we have seen that simple heuristics fail to efficiently map the application on the platforms; thus it would be interesting to design involved mapping heuristics which approach the optimal throughput.

Figure 1 :

 1 Figure 1: Cell processor.

Figure 2 ( 1 T 2 (

 212 c) shows one possible mapping for the task graph depicted on Figure 2(b) on four processing elements PE 1 , PE 2 , PE 3 , and PE 4 . Using this mapping, all instances of task T 1 are processed by PE 1 , all instances of tasks T 2 , T 5 , and T 6 are processed by PE 2 , etc. With input stream output stream T a) Simple streaming application.

T

Figure 2 :

 2 Figure 2: Applications and mapping.

Figure 3 :

 3 Figure 3: Mapping and schedule

Figure 5 :Figure 6 :

 56 Figure 5: Two random task graphs used in the experiments

Figure 7 :

 7 Figure 7: Speed-up obtained on the QS22 depending on the number of SPEs used.

Figure 8 :

 8 Figure 8: Speed-up of random task graphs according to the CCR, for the mapping computed through linear programming using 8 SPEs on an QS22.

An experimental version of our scheduling framework is available online, at http://graal.ens-lyon. fr/~mjacquel/cell_ss.html

the Cell processor is made of two different types of cores, which induces additional challenges for the programmer:

• SPE are 32-bit processors whereas the PPE is a 64-bit architecture;

• Different communication mechanisms have to be used depending on which types of processing elements are implied in the communication. To properly issue our "Get" operations, we made use of three different intrinsics: mfc_get for SPE to SPE communications, spe_mfcio_put for SPE to PPE communication, and memcpy for communication between PPE and main memory. Another difficulty lies in the large number of variables that we need to statically initialize in each local store before starting the processing of the stream: the information on the mapping, the buffer for data transfer, and some control variables such as addresses of all memory blocks used for communications. This initialization phase is again complicated by the different data sizes between 32-bit and 64-bit architectures, and the runtime memory allocation.

All these issues show that the Cell processor is not designed for such a complex and decentralized usage. However, our success in designing a complex scheduling framework proves that it is possible to use such a heterogeneous processor for something else than pure data-parallelism.

Applications

We test our scheduling framework on three random task graphs, obtained with the DagGen generator [START_REF] Suter | Dag generation program[END_REF]. This allows us to test our strategy against task graphs with different depths, widths, and branching factors. Two of the three generated task graphs are described on Figures 5(a) and 5(b), and the last one is a simple chain graph with 50 tasks. For these graphs, we generated 6 variants of different communication-to-computation ratio (CCR), resulting in 24 different random applications. We compute the CCR of a scenario as the total number of transfered elements divided by the number of operations on these elements. In the experiments, the CCR goes from 0.775 (computation-intensive scenario) to 4.6 (communication-intensive scenario).

Reference heuristics

Here, we present two simple heuristic strategies that we have designed in order to assess the performance of our schedule based on linear programming. These strategies are designed for the particular hardware platforms used in our tests; therefore, they can handle a Cell processor with several SPEs and one PPE. Since we noticed that memory limitation of the SPEs is one of the most significant factor for performance, these strategies focus on a reasonable usage of this limited memory. The second one also takes the computation amount into account when mapping tasks to processing elements. Both strategies are greedy strategies: they map the tasks one after the other, and never go back on a previous decision.

The first heuristic, called GREEDYMEM, process the tasks in a topological order. Given a task, it select the SPEs which have enough free memory to host the tasks and its buffers. Among those SPEs, the one with the least loaded memory is chosen. If no SPE can host the task, it is allocated on the PPE.

The second heuristic is called GREEDYCPU and is very similar to GREEDYMEM: among the processing elements (SPEs and PPE) with enough memory to host a task, it selects the one with the smallest computation load.

Experimental results

The results presented here are obtained on the QS22, using up to eight SPEs. We have also performed the same experiments on the PlayStation 3, and the results are exactly the same as the one on the QS22 (using six SPEs). Thus, we show only the results on the QS22.

Entering steady-state

First, we show that our scheduling framework succeeds in reaching steady-state, and that the throughput is then similar to the one predicted by the linear program. Figure 6 shows the experiments done with the task graph described in Figure 5(a), with a CCR of 0.775, on the QS22 using all eight SPEs. We notice that a steady-state operation is obtained after approximately 1000 instances. Note that one instance consists only of a few bytes, so the steady-state throughput is obtained quickly compared to the total length of the stream. In steady state, the experimental throughput achieves 95% of the throughput predicted by the linear program. The small gap is explained by the overhead of our framework, and the synchronizations induced when communications are performed.

Comparing heuristics with linear program

Then, we compare the throughput of the mapping obtained through mixed linear programming with the mappings computed by the heuristics. We compute the speed-up obtained by each mapping, that is the achieved throughput normalized to the throughput when using only the PPE. Figure 7 shows the results for the three random task graphs, with CCR 0.775, for different numbers of SPEs used.


D M Basko
email: denis.basko@grenoble.cnrs.fr

Calculation of the Raman G peak intensity in monolayer graphene: role of Ward identities

The absolute integrated intensity of the single-phonon Raman peak at 1580cm -1 is calculated for a clean graphene monolayer. The resulting intensity is determined by the trigonal warping of the electronic bands and the anisotropy of the electron-phonon coupling, and is proportional to the second power of the excitation frequency. The main contribution to the process comes from the intermediate electron-hole states with typical energies of the order of the excitation frequency, contrary to what has been reported earlier. This occurs because of strong cancellations between different terms of the perturbation theory, analogous to Ward identities in quantum electrodynamics.

Introduction

In the past decades, Raman spectroscopy [1] techniques were successfully applied to carbon compounds, such as graphite [2] and carbon nanotubes [3]. Upon the discovery of graphene [4], Raman spectroscopy has proven to be a powerful and non-destructive tool to identify the number of layers, doping, disorder, strain, and to characterize the phonons and electron-phonon coupling [5,6,7,8,9,10,11].

The most robust feature in the Raman spectra of all conjugate carbon compounds is the so-called G peak, corresponding to the in-plane bond-stretching optical vibration of sp 2 -hybridized carbon atoms. In graphene this vibration has the E 2g symmetry, it is doubly degenerate, and its frequency ω ph ≈ 1580 cm -1 . While the G peak frequency is sensitive to external factors, such as doping level [6,7,8] or strain [12,10,11], its total frequency-integrated intensity I G is often assumed to remain constant under the change of many external parameters, depending only on the excitation frequency. Thanks to this robustness, I G is often used as a reference to which intensities of other peaks are compared [13,14,15], since measurement of absolute peak intensities represents a hard experimental task (the first use of I G as a reference for other Raman peak intensities in graphite probably dates back to 1970 [16]).

Given this popular role of I G as a reference, it is clear that having at hand a theoretical expression of the absolute intensity in terms of the basic parameters of the material (such as the electronic dispersion, the electron-phonon coupling, etc.), would be useful. Nevertheless, to the best of the author's knowledge, no such expression is available at present. I G was discussed in a recent paper by the author [17], where the conclusion was reached that even in the limit when the excitation frequency ω in is small compared to the energy scale t 0 characterizing the electronic dispersion (several eV), the intensity I G is contributed by the whole conduction and valence bands, not just by low-energy states in the vicinities of the Dirac points. As will be shown below, this conclusion is wrong, since Ref. [17] missed strong cancellations occurring as a consequence of a Ward identity. This affects the dependence of I G on ω in .

In the present work I G is calculated for a clean graphene monolayer suspended in vacuum. When ω in ≪ t 0 , the intensity is indeed determined only by electronic states with energies ∼ ω in , not the whole conduction and valence bands (however, these energies do not have to be close to ω in /2). In this limit I G can be expressed in terms of a few parameters, characterizing these low-energy states. As correctly mentioned in Ref. [17], trigonal warping of the electronic bands and the anisotropy of the electronhole coupling turn out to be crucial for the G peak. In the limit ω ph ≪ ω in ≪ t 0 the frequency dependence is I G ∝ ω 2 in . At higher frequencies, the calculation is performed using the nearest-neighbor tight-binding model. The main feature found is a strong enhancement of I G when the frequency matches the energy of electron-hole separation at the M point of the electronic first Brillouin zone, where a van Hove singularity in the electronic density of states occurs.

Calculation

The Bloch form of the electronic wave function in the tight-binding model is where ψ a (r) is the atomic wave function localized near the origin, α = A, B labels the sublattices, and the two-dimensional integer vector n labels the unit cells, each containing two atoms from the two sublattices. The wave vector k runs over the first Brillouin zone. The Bloch amplitudes U αk satisfy the Shrödinger equation (we neglect the non-orthogonality of the atomic orbitals)

Ψ k (r) = e ikr α=A,B U αk n ψ a (r -r α,n ), (1)
d 1 d 3 d 2 A A A B B B A A B B B A A A
ǫ - Ĥ(0) k U Ak U Bk = 0, (2)
where the Hamiltonian matrix is given by

Ĥ(0) k = 0 H k H * k 0 , H k = -t 0 i=1,2,3 e ikdi = H * -k . ( 3a
)
Here t 0 ≈ 3 eV is the nearest-neighbor coupling matrix element, and d 1,2,3 are the vectors connecting an A atom to its three nearest neighbors, as shown on Fig. 1. Their length is |d 1,2,3 | = a ≈ 1.42 Å. The energy eigenvalues are ǫ = ±ǫ k , where

ǫ k ≡ |H k |.
Note that H k is not a periodic function in the first Brillouin zone; its values on the boundaries related by a reciprocal lattice vector differ by a constant phase factor e ±2πi/3 . Suppose that all atoms belonging to the sublattice α are displaced by u α , and u A = -u B . Such a uniform displacement corresponds to optical phonons with the wave vector q = 0. These are the phonons responsible for the G peak, as fixed by the momentum conservation (the wave vectors of both incident and scattered photons are negligibly small). In the tight-binding model the mechanism of the electron-phonon coupling is the change of the nearest-neighbor electronic matrix element t 0 due to the change in the bond length a, ∂t 0 /∂a ≈ -6 eV/ Å. Then, to linear order in the atomic displacements, the electron-phonon interaction Hamiltonian is given by

V (0) k = u A -u B 2 • 0 F k F * k 0 , F k = 2i t 0 a ∂t 0 ∂a ∂H k ∂k . (3b)
The electromagnetic field of the incident and scattered light is described by the vector potential A. The Hamiltonian describing interaction of the electrons with the field can be obtained by the Peierls substitution k → k -(e/c)A in the electronic Hamiltonian. Since we are interested in a two-photon process, we should expand the Hamiltonian to the second order in A:

Ĥ(1) k = - e c A • 0 v k v * k 0 , (3c)
Ĥ(2) k = e 2 c 2 A i A j 0 w ij k (w ij k ) * 0 , (3d)
V

k = - e c A i (u Aj -u Bj ) 0 g ij k (g ij k ) * 0 , (1)
V (2) k = e 2 c 2 A i A j (u Al -u Bl ) 0 h ijl k (h ijl k ) * 0 , (3e)
v k = ∂H k ∂k , w ij k = ∂ 2 H k ∂k i ∂k j , g ij k = ∂F i k ∂k j , h ijl k = ∂ 2 F i k ∂k j ∂k l . ( (3f)
) 3g
Here i, j, l = x, y label the in-plane Cartesian components, and the summation over repeated indices is assumed. Note that for the description of resonant multiphoton processes it is sufficient to keep Ĥ(1) k term only, as it was done in [17], since the contribution of other terms is (i) off-resonant and (ii) smaller by a factor ∼ ω in /t 0 . However, for the one-phonon process studied here the contributions from all terms turn out to be of the same order; in fact, they almost cancel each other.

To calculate the Raman scattering probability, we follow the general steps of Ref. [17]: pass to the second quantization, calculate the scattering matrix element, and substitute it into the Fermi Golden Rule. The zero-temperature electronic Green's function is a 2 × 2 matrix, Ĝk (ǫ) = (ǫ

-Ĥk + i0 + sgn ǫ) -1 . ( 4
)
Upon quantization of the phonon field the atomic displacements corresponding to the optical phonons are expressed in terms of the phonon creation and annihilation operators b † q,µ , bq,µ as

ûA,n = -û B,n = q,µ e (µ) 2N M ω ph bqµ e iqrn + h. c. . (5)
Here µ = x, y labels the two degenerate phonon modes, e (µ) is the unit vector in the corresponding direction, M is the mass of the carbon atom, N is the total number of the carbon atoms in the crystal, and "h.c." stands for the hermitian conjugate. A small finite wave vector q has to be introduced in order to treat the in-plane momentum conservation properly; only the q = 0 modes will contribute to the final result. The transverse electromagnetic field is quantized inside the large volume L x L y L z in the Coulomb gauge:

Â(r) = Q,ℓ 2πc L x L y L z Q e (Q,ℓ) âQ,ℓ e iQr + h. c. . ( 6
)
Here Q is the three-dimensional wave vector, ℓ = 1, 2 labels the two transverse polarizations along the two unit vectors e (Q,ℓ) ⊥ Q.

The probability for an incident photon with the polarization e in and frequency ω in to be scattered into an element of the solid angle do out with the polarization e out , and with the frequency ω out = ω in -ω ph fixed by the energy conservation, is given by

dI G do out = ω 2 out (2π) 2 c 4 µ 2M ijl e in i (e out j ) * e (µ) l 2 . ( 7
)
Here M ijl is the transition matrix element (the factor of 2 explicitly takes care of the two spin projections of the electron). It is given by the sum of the following contributions:

M ijl = 2πe 2 √ ω in ω out L x L y 2N M ω ph d 2 k (2π) 2 dǫ 2π e iǫ0 + × Tr{D ijl 1 + Dijl 1 + D ijl 2 + Dijl 2 + Dijl 2 + D ijl 3 }, (8)
D ijl 1 = Ĝk (ǫ)v i k Ĝk (ǫ -ω in ) F l k Ĝk (ǫ -ω out )v j k , (9a) Dijl 1 = Ĝk (ǫ)v j k Ĝk (ǫ + ω out ) F l k Ĝk (ǫ + ω in )v i k , (9b)
D ijl 2 = Ĝk (ǫ)ĝ li k Ĝk (ǫ -ω out )v j k , (9c) Dijl 2 = Ĝk (ǫ)v i k Ĝk (ǫ -ω in )ĝ lj k , (9d) Dijl 2 = Ĝ(ǫ) ŵij k Ĝk (ǫ -ω ph ) F l k , (9e)
D ijl 3 = ĥlij k Ĝk (ǫ). (9f)
The factor e iǫ0 + prescribes closing of the ǫ-integration contour in the upper halfplane. In fact, it is important only for the last term, Eq. (9f) which corresponds to the sum over the filled valence band. Upon integration over ǫ, Eq. ( 8) reduces to the standard perturbation theory expression for the Raman amplitude as the sum over intermediate states. Each intermediate state contains an electron with the wave vector k in the conduction band and a hole in the valence band with the wave vector -k. The k integration is performed over the first Brillouin zone. The six terms given by Eqs. (9a)-(9f) can be represented pictorially by the diagrams shown in Fig. 2.

In fact, D 1k = D1k because the Green's function and all the vertex matrices satisfy ĜT k (ǫ) = σx Ĝk (ǫ)σ x and Ĝk (-ǫ) = -σ z Ĝk (ǫ)σ z (the T superscript denotes the matrix transpose, and σx,z are the Pauli matrices).

If one integrates each of the terms in Eqs. (9a)-(9f) separately, the main contribution to the k-integral comes from the "bulk" of the first Brillouin zone, rather than the vicinities of the Dirac points (as it was pointed out in Ref. [17]). Let us formally consider, however, the whole expression for M ijl at ω in = ω out = 0. Then the sum of the terms (9a)-(9f) is a total derivative, ∂ 2 [ F l k Ĝk (ǫ)]/(∂k i ∂k j ). Thus, the k-integral vanishes, i. e., at ω in = ω out = 0 all terms contributing to the matrix element, cancel. This cancellation is far more general than the tight-binding model, used here. Indeed, consider linear response of the electronic current j to a static homogeneous vector potential A. The corresponding response function χ ij must vanish, since an observable (current) cannot respond to a pure gauge ‡. This holds for any configuration of the atomic positions, hence its derivative with respect to ‡ Strictly speaking, it is the limit lim q→0 lim ω→0 χ ij (q, ω) which vanishes, while the calculation done in this work corresponds to the opposite order of limits. The two limits commute for undoped graphene, when the Fermi surface has zero length. At finite doping, the contribution of the filled valence band states far below the Fermi energy still cancels out. the displacements, ∂χ ij /∂u l , must also vanish. As follows from the Kubo formula, the matrix element M ijl at ω in = ω out = 0 is equal just to this derivative, up to a constant factor. This fact is analogous to the Ward identity in the quantum electrodynamics. The cancellation of different terms contributing to M ijl was overlooked in Ref. [17], and it was wrongly concluded that M ijl is determined by the whole of the first Brillouin zone. In fact, for ω in ≪ t 0 it is sufficient to focus on the vicinities of the two Dirac points, as will be seen below.

The rest of the calculation is tedious, but straightforward. Let us focus on the limit ω in ≪ t 0 first. In the vicinity of the K point we write k = K + p and expand:

H k = v(p x -ip y ) -α 3 (p x + ip y ) 2 + O(p 3 ), ( 10a
)
iF k = F 0 (e x -ie y ) + F 1 (p x + ip y )(e x + ie y ) + O(p 2 ). ( 10b
)
The expansion around the K ′ point can be obtained by flipping e x → -e x , p x → -p x . Note that going one order beyond the Dirac approximation is necessary, since the leading contribution to M ijl vanishes. (Indeed, the Dirac Hamiltonian has a continuous rotation symmetry, so any third-rank tensor must vanish; the continuous rotation symmetry is lifted by the trigonal warping term.) In the nearest-neighbor tight-binding model one has

v = 3 2 t 0 a, α 3 = 3 8 t 0 a 2 , F 0 = -3 ∂t 0 ∂a , F 1 = - 3a 2
∂t 0 ∂a . (11)
Still, in Eqs. (10a), (10b) we prefer to keep all four parameters v, α 3 , F 0 , F 1 independent, since going beyond the nearest-neighbor tight-binding model would invalidate Eq. ( 11), while the form of Eqs. (10a), (10b) is fixed by the symmetry §.

It is instructive to write down explicitly the expression for the matrix element after the integration over the directions of p (we change the integration variable from p § In fact, the C 6v crystal symmetry allows a term α 0 (p 2

x + p 2 y ) in the expansion of H k (electron-hole asymmetry), which appears already in the second-nearest-neighbor approximation. However, it does not contribute to the matrix element calculated here because of its full rotational symmetry.

to ǫ k and denote by A C = L x L y /N = √ 27a 4 /4 the area per carbon atom):

M xxy = ie 2 √ ω in ω out A C 2M ω ph ∞ 0 dǫ k × C in ω 2 in 4ǫ 2 k -ω 2 in + C out ω 2 out 4ǫ 2 k -ω 2 out + C ph ω 2 ph 4ǫ 2 k -ω 2 ph = - πe 2 4 A C 2M ω ph C in ω in + C out ω out + C ph ω ph √ ω in ω out , (12a)
C in = 2 F 0 α 3 v 2 ω in ω ph + F 1 v ω in 2ω ph - ω in 2ω out + 1 , (12b)
C out = -2 F 0 α 3 v 2 ω out ω ph - F 1 v ω out 2ω ph + ω out 2ω in -1 , (12c)
C ph = -2 F 0 α 3 v 2 + F 1 v ω 2 ph 2ω in ω out . ( 12d
)
The integral over ǫ k corresponds to the sum over the intermediate states whose energies are 2ǫ k (an electron with the energy -ǫ k in the valence band is promoted to the conduction band where its energy is ǫ k ). The poles are bypassed by adding an infinitesimal imaginary part ǫ k → ǫ k -i0 + , as follows from Eq. ( 4). At frequencies ω in not small compared to t 0 the k integral in M xxy should be evaluated numerically. We focus in the limit ω ph ≪ ω in . In this limit the overall Raman efficiency, i. e., the absolute probability for an incident photon with the polarization e in and frequency ω in to be scattered in the full solid angle 4π with any polarization, accompanied by the emission of a 1580 cm -1 optical phonon, is given by

I G = 2πλ Γ 3 e 2 c 2 ω in a c 2 f (ω in /t 0 ). ( 13
)
The dimensionless electron-phonon coupling constant is defined as λ Γ = ( √ 27/M ω ph )(t -1 0 ∂t 0 /∂a) 2 , which coincides with the definition of Ref. [17] in the tightbinding model. The dimensionless function f (ω in /t 0 ) is plotted in Fig. 3. In the low-energy limit, ω in ≪ t 0 , its value is f (0) = 1, as follows from Eq. (12a). When the frequency matches the van Hove singularity at the M point of the first Brillouin zone, ω in ≈ 2t 0 , the intensity diverges, f (ω in /t 0 ) ∝ 1/(ω in /t 0 -2) 2 . This divergence is cut off at the scale |ω in -2t 0 | ∼ max{ω ph , γ}. However, in the absence of a reliable information on electronic relaxation processes in this region of the spectrum, we prefer not to study this issue in detail, leaving the divergence as it is.

Discussion

First, let us see which electron-hole states contribute the most to the G peak intensity. In principle, for ω in ≪ t 0 one can imagine three situations. They are illustrated Fig. 4 where the π electron dispersion is shown schematically, together with the contributing states. In the situation (a) these are the states whose energies are close to the half of the excitation frequency, the difference ǫ k -ω in /2 being small by some parameter. This was shown to be the case for the 2D peak, the second-order overtone of the D peak at 2700 cm -1 , which is fully resonant and |ǫ k -ω in /2| ∼ γ, where 2γ ≪ ω in is the

0 0.5 1 1.5 2 ω in /t 0 0 5 10 f(ω in /t 0 ) Figure 3.
The dimensionless function f (ω in /t 0 ) appearing in Eq. ( 13).

electron inelastic scattering rate [18,17]. This is also the case for the doubly-resonant D peak at 1350 cm -1 , where |ǫ k -ω in /2| ∼ ω ph ≪ ω in [19,20]. In the situation (b) the difference |ǫ k -ω in /2| ∼ ω in itself, and no small parameter enters. Finally, in the situation (c) the Raman process is contributed by the whole Brillouin zone, ǫ k ∼ t 0 .

A natural guess for the G peak would be the option (a): indeed, there is a contribution from intermediate states that violate energy conservation by the energy ∼ ω ph . However, in Ref. [17] it was found that the main contribution to the integral in Eq. ( 8) with only two terms (9a), (9b) came from the states ǫ k ∼ t 0 [option (c)]. In the present work we have seen that this contribution, in fact, is canceled by other terms, missed in Ref. [17], due to the Ward identity. To see that the correct picture for the G peak in fact corresponds to Fig. 4(c), let us consider doped sample, i. e., with the Fermi energy ǫ F detuned from the Dirac point. Then transitions involving states with ǫ k < |ǫ F | are simply blocked by the Pauli principle, so the lower limit of the integral in Eq. (12a) must be set to |ǫ F |. Let us analyze the first term in Eq. (12a) (the second term is almost equal to the first, the third one is smaller by a factor ∼ ω 2 ph /ω 2 in ):

∞ |ǫF | C in ω 2 in dǫ k 4ǫ 2 k -ω 2 in = C in ω in 4 iπθ(ω in -2|ǫ F |) + ln 2|ǫ F | + ω in 2|ǫ F | -ω in . (14)
The value of the integral is determined entirely by the ratio |ǫ F |/ω in , and no other energy scales enter, whether small (ω ph ) or large (t 0 ). That is, the value of the integral in Eq. (12a) is determined not just by the vicinity of the pole, but by the whole range of energies from ǫ k = 0 to ǫ k ∼ ω in . Numerically, when ǫ F is raised from zero to ω in /4 (half of the distance to the pole), |M xxy | 2 is changed by about 12%.

In other words, the uncertainty in the energy of the electron-hole states, contributing to the process, is of the order of their energy itself (∼ ω in ). By virtue of the energy-time uncertainty principle, the duration of the process (the typical lifetime of the virtual electron-hole pair) is ∼ 1/ω in . The relevant length scale is thus v/ω in ∼ 3 Å for v = 10 8 cm/s ≈ 7 eV • Å and ω in = 2 eV. The Raman process giving rise to the G peak is thus extremely local in space, involving just a few carbon atoms, as it was noted earlier [21]. Its locality can be also understood from the quasiclassical

K Γ M in ω K Γ M in ω (a) (b) (c) K Γ M in ω Figure 4
. Schematic view of the π electron band structure (solid curves), with the states effectively contributing to a Raman process (pink areas)for ω in ≪ t 0 : (a) states within the narrow region

|ǫ k -ω in /2| ≪ ω in ; (b) a broad region of states with |ǫ k -ω in /2| ∼ ω in , but still ǫ k ≪ t 0 ; (c) the whole Brillouin zone, ǫ k ∼ t 0 .
real-space picture of Raman scattering in graphene [20]. This short length scale should be contrasted to much longer scales responsible for Raman peaks produced according to Fig. 4 (a), for example, the doubly-resonant D peak at 1350 cm -1 [23,24,22,20].

Another consequence of the cancellation of the contribution from ǫ k ∼ t 0 is the frequency dependence of I G . The standard textbook dependence I ∝ ω 4 (for simplicity we assume ω in ≈ ω out ) is obtained for systems whose excited states have energies much higher than ω in [START_REF] Long | Raman Spectroscopy[END_REF]. The ω 4 dependence, suggested in Ref. [17], was essentially of the same origin: it was assumed that the main contribution to the process came from states in the bulk of the Brillouin zone, and thus with high energies. As we have seen, this conclusion is wrong, and the relevant states have energies ǫ k ∼ ω in . This remains true even at low frequencies, as the electronic spectrum in graphene has no (or almost no) gap. As a result, at low frequencies the dependence is ∝ ω 2 in , as seen from Eq. ( 13). Nevertheless, a recent measurement of Raman peak intensities performed on graphite nanocrystallites gives a ω 4 in dependence [15,[START_REF] Cançado | [END_REF]. For comparison, we plot I G from Eq. ( 13) together with two curves ∝ ω 4 in with two different coefficients in Fig. 5. Let us compare I G to the intensities of other peaks which have been calculated theoretically and measured experimentally. The D peak at 1350 cm -1 is due to emission of the scalar A 1 phonons with wave vectors near the K point. Due to momentum conservation, the D peak is activated by defects or edges. For a defect-free graphene flake of the size L a its intensity is given by [20]

I D = Cλ K e 2 c 2 v 2 c 2 ω in ω 2 D vL a L x L y ln ω 2 D + (4γ) 2 (4γ) 2 . ( 15
)
Here ω D ≈ 0.17 eV and λ K are the frequency and the dimensionless electron-phonon coupling constant for the corresponding phonons, v ≈ 7 eV • Å is the electron velocity (the slope of the Dirac cones), 2γ is the electron inelastic scattering rate, L x L y is the area of the excitation laser spot, and C is a numerical coefficient which depends on the shape of the flake and the character of the edges. We take λ Γ = 0.03, as obtained from the doping dependence of the G peak frequency [6,7], and λ K /λ Γ = 3 as extracted from the ratio of intensities of the intensities of the 2D peak at 2700 cm -1 and the 2D ′ peak at 3250 cm -1 [17]. Let us assume the inelastic scattering rate to be dominated by electron-phonon scattering (which is a lower bound), then it can be 0 0,5 estimated as γ = (λ Γ + λ K )ω in /8 [18]. For a small flake, Eq. ( 13) should be weighted by the ratio of the area of the flake to the excitation spot area. If we take an ideal hexagonal flake with armchair edges (which definitely represents an upper bound for I D ), then its area is L 2 a √ 27/8 and C = 4. For a round flake of the diameter L a with atomically rough edges the area is πL 2 a /4 and C = π 2 /18, i. e., I D is about 10 times smaller than for the ideal flake. Taking ω in = 2eV and using the low-frequency limit of Eq. ( 13), f (ω in /t 0 ) = 1, we obtain I D /I G ≈ (300 -3000 nm)/L a . The experimentally found intensity is I D /I G = (560 nm • eV 4 )/(L a ω 4 in ) [15,[START_REF] Cançado | [END_REF], which at ω in = 2 eV gives an almost 10 times smaller value than the calculated one for a flake with rough edges.

We can also consider 2D peak at 2700 cm -1 , whose intensity was calculated to be [18,17]

I 2D = λ 2 K 24 e 2 c 2 v 2 c 2 ω 2 in γ 2 . ( 16
)
For the same values as above we obtain I 2D /I G ≈ 150. The experimental value for graphene samples on a substrate is typically I 2D /I G ≈ 5 [5,12]. For suspended samples the ratio can be I 2D /I G ≈ 9 [27] and even I 2D /I G ≈ 17 [28]. Still, the experimental ratio is about 10 times smaller than the calculated one. Thus, the theory overestimates both I 2D /I G and I D /I G by about an order of magnitude. It seems more reasonable to assume that Eq. ( 13) for I G should be blamed for this discrepancy, rather than expressions for I D and I 2D . Indeed, as discussed above, I D and I 2D are determined by just a few material parameters (electron-phonon coupling constants, electronic velocity, etc.) which have been calculated by different methods and measured in many independent experiments. Moreover, corrections to Eq. ( 16) due to the trigonal warping and electron-hole asymmetry have been estimated in Ref. [17] and turned out to be small. At the same time, the parameters determining I G (electronic trigonal warping, electron-phonon coupling anisotropy) are not really known, the validity of the tight-binding model at sufficiently high energies is questionable, and even the calculated frequency dependence of I G does not seem to agree with the experiment.

Still, what is the main source of such a strong discrepancy? Is it possible that ω in = 2 eV is already sufficiently close to the singularity at ω in = 2t 0 , so that the dependence of I G on ω in is noticeably steeper than ω 2 , and the value of I G is higher than that predicted by the low-frequency asymptotics? On the one hand, the nearestneighbor tight-binding model with t 0 ≈ 3 eV seems to describe the band structure reasonably well in the energy range of interest, as is seen from its comparison with the results obtained by angle-resolved photoemission spectroscopy [29]. Then the energy of electron-hole separation at the M point is 2t 0 ≈ 6 eV and ω in /t 0 = 0.6 is quite close to the low-energy limit, as seen from Fig. 3. On the other hand, a recent ab initio calculation of the band structure of graphite gives the electron-hole separation at the M point about 4 eV [30]. Also, the anisotropy of the electron-phonon coupling may be stronger than that obtained from the nearest-neighbor tight-binding model [31]. In addition, the spectrum of electron-hole excitations can be modified by excitonic effects: the Coulomb attraction between the electron and the hole lowers the energy of the excitation with respect to its non-interacting value, so that the singularity in I D should be at a lower frequency. The author is aware of only one study of excitonic effects in the optical response of monolayer graphene; within the Dirac model it was shown that excitonic effects result in a weak feature at the border of the electron-hole continuum [32]. Their importance for optical excitation of electrons near the M point of the first Brillouin zone remains to be studied. Also, a direct measurement of the energy corresponding to the singularity by an excitation in the ultraviolet frequency range would shed light on this issue.

Conclusions

We have calculated the frequency-integrated intensity of the Raman G peak in monolayer graphene using the nearest-neighbor tight-binding model for electrons. The resulting intensity is determined by the trigonal warping of the electronic bands and the anisotropy of the electron-phonon coupling, and is proportional to the second power of the excitation frequency. Comparison to the intensities of other peaks, which have been measured experimentally and calculated theoretically, suggests that the present calculation underestimates I G by about an order of magnitude.

Figure 1 .

 1 Figure 1. Honeycomb lattice with the two sublattices A and B and the three nearest-neighbor bond vectors d 1 , d 2 , d 3 .

Figure 2 .

 2 Figure 2. (Color on line.) Diagrams corresponding to Eqs. (9a)-(9f). Solid arrows correspond to the electronic Green's functions, the dashed arrow represents the phonon emission vertex, the zigzag arrows represent the photon absorption and emission vertices.

Figure 5 .

 5 Figure 5. The intensity of the G peak as a function of ω in /t 0 from Eq. (13) for λ Γ = 0.03, t 0 a/c = 0.0023 (corresponding to t 0 ≈ 3.3 eV) (solid curve). Dashed and dotted curves correspond to 3 • 10 -11 (ω in /t 0 ) 4 and 4 • 10 -11 (ω in /t 0 ) 4 , respectively.


O Goubet

L Molinet

GLOBAL ATTRACTOR FOR WEAKLY DAMPED NONLINEAR SCHR ÖDINGER EQUATIONS IN L 2 (R)

We prove that the weakly damped nonlinear Schrödinger flow in L 2 (R) provides a dynamical system which possesses a global attractor. The proof relies on the continuity of the Schrödinger flow for the weak topology in L 2 (R).

Introduction

Nonlinear Schrödinger (NLS) and Korteweg-de Vries equations are asymptotical models for the waterwave propagation. These models supplemented with a damping and an external force provide examples of infinite-dimensional dynamical systems, in the framework described in [START_REF] Temam | Infinite Dimensional Dynamical Systems in Mechanics and Physics[END_REF], [START_REF] Hale | Asymptotic behavior of Dissipative Systems[END_REF], [START_REF] Raugel | Global attractors in partial differential equations[END_REF], [START_REF] Miranville | Attractors for dissipative partial differential equations in bounded and unbounded domains[END_REF]. We focus here on the cubic NLS equation ( 1)

u t + γu + iu xx + i|u| 2 u = f,
where γ > 0 is the damping parameter and where the external forcing f (x), that is independent of t, belongs to L 2 (R).

To define an infinite-dimensional dynamical system from this evolution equation, we supplement [START_REF] Akroune | Regularity of the attractor for a weakly damped Schrödinger equation on IR[END_REF] with an initial data u 0 in some Sobolev space X (or in some complete metric space) such that the corresponding initial value problem is well posed (in the Hadamard sense: existence and uniqueness of trajectories u(t) = S(t)u 0 in X, continuity of S(t) : u 0 → u(t) in X). This short article is concerned with the existence of a global attractor of the NLS flow with low regular initial data in L 2 (R). Recall that a global attractor is a compact set, invariant by the flow, that attracts all trajectories uniformly on bounded sets. Note that the existence of a such set for the NLS equations in more regular function spaces, as for instance H 1 (R), is well known (see [START_REF] Akroune | Regularity of the attractor for a weakly damped Schrödinger equation on IR[END_REF] and the references therein).

Our main result states as follows Theorem 1.1. The semi-group S(t) provides an infinite-dimensional dynamical system in L 2 (R) that has a global attractor A.

Let us describe the strategy of the proof. As in [START_REF] Ghidaglia | Finite dimensional behavior for the weakly damped driven Schrödinger equations[END_REF], we first prove that the NLS flow features a weak global attractor in L 2 (R), that is a global attractor for the weak topology of L 2 (R). For that purpose, we need to establish the following result that is interesting on its own : Theorem 1.2. The semi-group S(t) is a continuous mapping for the weak topology of L 2 (R).

The usual arguments to prove this kind of result in a function space X make use of the fact that the initial value problem is well-posed in a function space where X is locally compactly embedded (cf. [START_REF] Ghidaglia | Finite dimensional behavior for the weakly damped driven Schrödinger equations[END_REF]). Here such an argument can not be invoked since there is no available result on the well-posedness of the (1) in a space where L 2 (R) is locally compactly embedded (cf. [START_REF] Kenig | On the ill-posedness of some canonical dispersive equations[END_REF]). Note that the situation for KdV equations is easier according to this last point (see [START_REF] Goubet | Asymptotic smoothing and the global attractor for a weakly damped kdv equation on the real line[END_REF], [START_REF] Tsugawa | Existence of the global attractor for weakly damped, forced KdV equation on Sobolev spaces of negative index[END_REF]).

Therefore this result is new and can be outlined as follows. Calling U (t)u 0 the solution of ( 2)

u t + iu xx = 0; u(0) = u 0 ,
it is well-known that the linear Schrödinger equation features the so-called Kato's smoothing effect that reads:

(3)

||D 1/2 x U (t)u 0 || L ∞ x L 2 t ≤ c||u 0 || L 2 x . Above, D x =
√ -∆ stand for the operator with Fourier symbol |ξ|. Using the Christ-Kiselev theorem [START_REF] Christ | Maximal functions associated to filtrations[END_REF] (as in [START_REF] Molinet | Well-posedness results for the generalized Benjamin-Ono equation with small initial data[END_REF] in another context), we are able to prove that this smoothing effect is also valid for the nonlinear Schrödinger equation. Then the weak continuity is valid due to some compactness argument that allow us to pass to the limit in the nonlinear term. These arguments are developed in Section 1 below. In Section 2 we complete the proof of Theorem 1.1. First we prove the existence of a weak attractor. Then, using the famous J. Ball's argument (see [START_REF] Ball | Global attractors for damped semilinear wave equations. Partial differential equations and applications[END_REF], [START_REF] Wang | An energy equation for the weakly damped driven nonlinear Schrödinger equations and its applications to their attractors[END_REF], [START_REF] Moise | Attractors for non-compact semigroups via energy equations[END_REF]), we establish that the weak attractor is actually a global attractor in the usual sense.

Continuity of the flow for the weak topology

To begin with, we observe that for finite time results the damping parameter and the external forcing do not play a role. Then in this section we may assume for the sake of simplicity that γ = 0 and f = 0.

The usual way to solve the IVP problem associated to (4)

u t + iu xx + i|u| 2 u = 0,
supplemented with initial data u 0 is to perform a fixed point argument for the Duhamel's form of (4) that reads

(5)

u(t) = U (t)u 0 -i t 0 U (t -s)|u(s)| 2 u(s)ds.
Thanks to well-known Strichartz inequalities, we usually perform a fixed point into the space C([0, T ], L 2 (R)) ∩ L 6 T,x , where L 6 T,x = L 6 ([0, T ] × R x ). We first state and prove Proposition 2.1. There exists a numerical constant c such that for a solution to (5)

(6) ||D 1/2 x u|| L ∞ x L 2 T ≤ c(||u 0 || L 2 x + ||u 0 || 3 L 2
x ). Proof of the Proposition: the key point is to estimate the nonlinear term in [START_REF] Goubet | Regularity of the attractor for the weakly damped nonlinear Schrödinger equations[END_REF]. For that purpose, we first recall the dual estimate to (3) that reads [START_REF] Hale | Asymptotic behavior of Dissipative Systems[END_REF] ||

R U (-s)D 1/2 x Gds|| L 2 x ≤ c||G|| L 1 x L 2
t . We now prove [START_REF] Kenig | On the ill-posedness of some canonical dispersive equations[END_REF] ||

Rs U (t -s)D 1/2 x f ds|| L ∞ x L 2 t ≤ c||f || L 6 5 t,x
.

Actually, following P. Tomas duality argument, it is equivalent to prove that for any smooth function G that satisfies

||G|| L 1 x L 2 t ≤ 1, it holds (9)
R 3 U (t -s)D 1/2 x f (s, x)G(t, x)dtdxds ≤ c||f || L 6 5 t,x
.

Note that the left-hand side member of the above estimate can be rewritten as

(10) R R U (-s)D 1/2 x f (s, x) ds R U (-t)G(t, x)dt dx ,
Hence, applying Cauchy-Schwarz in x and using [START_REF] Hale | Asymptotic behavior of Dissipative Systems[END_REF], it finally suffices to check that

(11) || R U (-s)f ds|| L 2 x ≤ c||f || L 6 5 t,x
, Since this is nothing else but the dual form of the classical Strichartz estimate for the Schrödinger group on R:

(12) U (t)u 0 L 6 t,x ≤ c u 0 L 2
x , we are done. Recall now from [START_REF] Molinet | Well-posedness results for the generalized Benjamin-Ono equation with small initial data[END_REF] Lemma 2.2. (Christ-Kiselev) Consider a linear operator defined on spacetime functions f (t, x) by

(13) T f (t) = Rs K(t, s)f (s)ds. Assume (14) ||T f || L ∞ x L 2 t ≤ c||f || L 6 5 t,x , then (15)
|| t 0 K(t, s)f (s)ds|| L ∞ x L 2 t ≤ c||f || L 6 5 t,x
.

According to [START_REF] Molinet | Well-posedness results for the generalized Benjamin-Ono equation with small initial data[END_REF], this is valid since min(+∞, 2) > max( 6 5 , 6 5 ). We then apply this argument to the nonlinear term in ( 5), for t ∈ [0, T ]. This leads to

|| t 0 D 1/2 x U (t -s)ū 2 uds|| L ∞ x L 2 T ≤ c||u 3 || L 6 5 T,x ≤ c||u|| 3 L 18 5 T,x ≤ c||u|| L 2 T,x ||u|| 2 L 6 T,x . (16)
We conclude the proof of the proposition using that u is bounded in

C([0, T ], L 2 (R))∩ L 6 T,x .
At this stage we complete the proof of Theorem 1.2. Consider u 0,ε ⇀ u 0 in L 2

x . Due to the previous proposition, we know that, for any

K compact subset of R x , the sequence u ε remains in a bounded set of C([0, T ], L 2 (R)) ∩ L 6 T,x ∩ L 2 T H 1 2
x (K). Going back to the equation, we observe that ∂ t u ε remains in a bounded set of L 2 T H -2

x . Hence, due to a standard compactness argument, the sequence u ε , up to a subsequence extraction, converges towards some function v strongly in L 2 T L 2 (K). By interpolation, the strong convergence is also valid in L 4 T L 4 (K). This allows us to pass to the limit in the equation and to conclude that the limit v is a solution of (4) belonging to the class of uniqueness L 6 T,x . Set (., .) for the L 2 x scalar product. By (4) and the bounds above, it is easy to check that, for any smooth space function φ with compact support, the family {t → (u ε (t), φ)} is uniformly equi-continuous on [0, T ]. Ascoli's theorem then ensures that (u ε (•), φ) converges to (v(•), φ) uniformly on [0, T ] and thus v(0) = u 0 . By uniqueness, it follows that v ≡ u and from the above convergence result, it results that u ε (t) ⇀ u(t) in L 2

x for all t ∈ [0, T ].

Proof of the main Theorem

To begin with, we prove the existence of an absorbing ball for the semigroup; multiplying (1) by ū and integrating in x the real part of the resulting equation

(17) 1 2 d dt ||u|| 2 L 2 x + γ||u|| 2 L 2 x = Re f ūdx ≤ 1 2 γ||u|| 2 L 2 x + 1 2γ ||f || 2 L 2
x .

This implies

(18) ||u(t)|| 2 L 2 x ≤ e -γt ||u 0 || 2 L 2 x + 1 -e -γt γ 2 ||f || 2 L 2 x . Proposition 3.1. The ball X of radius M 0 = 2 ||f || L 2 x
γ is an absorbing set for the dynamical system under consideration.

We endow then this absorbing ball with the weak topology of L 2

x . X is then a compact metric space and S(t) acts continuously on X according to Theorem 1.2. Therefore, using Theorem I.1.1 in [START_REF] Temam | Infinite Dimensional Dynamical Systems in Mechanics and Physics[END_REF] the ω-limit set A = ∪ s>0 ∩ t>s S(t)X is a global attractor. In fact

(19) A = {a ∈ X; ∃b n ∈ X, t n → +∞, S(t n )b n ⇀ a.}
We plan to transform this weak convergence into a strong convergence. We use the famous J. Ball's argument. We begin with the energy equation that asserts that for any τ > 0, due to (17),

||S(t n )b n || 2 L 2 x = e -2γτ ||S(t n -τ )b n || 2 L 2 (20)
x -2Re τ 0 Rx e -2γs f (x)S(t n -s)b n dsdx.

According to the weak convergence, we have x + 2e -2γτ M 2 0 , since for n > τ S(t nτ )b n is in X and S(-τ )a, that belongs to the weak attractor, remains trapped in X. Letting τ → +∞ implies that A attracts the bounded sets for the L 2 x strong topology. To prove that A is compact is very similar and then omitted.

0 2 L 2 x 2 L 2 x -2Re τ 0 ||S(t n )b n || 2 L 2 x ≤ ||a|| 2 L 2

 0222202222 Rx e -2γs f (x)S(t n -s)b n dsdx = 2Re τ Rx e -2γs f (x)S(-s)adsdx . Using once again the energy equality (17) we also have that (22) ||a|| = e -2γτ ||S(-τ )a|| Rx e -2γs f (x)S(-s)adsdx.