O Acher

H Pages

F Enguehard

H Piombini

Desktop cutting of paper using a single emitter laser diode and inkjet printing

Keywords: Laser diode, paper, cutting

Laser cutting of paper is widely used in the paper conversion industry. CO 2 lasers are well suited for this type of applications. Desktop printing is a large market both for digital photography, document management and graphics applications, but it still lacks advanced cutting and scoring ability, and CO 2 lasers seem costly to be integrated in massmarket printers. For that reason, mass-scalable and low-cost semiconductor laser diodes would be very advantageous to add paper cutting and scoring features in desktop printers. However, common paper can not be cut properly using visible or Near Infrared (NIR) laser diode since it has a very poor absorption at these wavelengths. We report here an innovative solution to achieve paper cutting or scoring using a 1 W single emitter NIR laser diode, within an inkjet printer. A special ink that absorbs the NIR light, and that penetrates all through the paper, is first disposed on the lines to be cut. Then, the laser diode goes along the lines to be cut. We show that a cutting speed of 2m/min can be achieved on 80g/m 2 conventional paper. The influence of the optical properties of the ink on the cutting speed are discussed, as well as focussing issues. In particular, we show that invisible inks are suitable, and very clear-cut edges can be obtained. The perspective of this technique are discussed.

INTRODUCTION

1.1. An attractive opportunity in laser processing of materials : desktop cutting of paper using a diode laser Laser processing of materials has been recognized as a powerful technique in the industry for years [START_REF] Chrissolouris | Laser Machining Theory and Practice[END_REF] , and this technique is fast expanding. High Power Diode Lasers have attracted considerable interest in the field of material processing, they are very attractive in term of small size, reliability, and cost. However, it has been stated that the market of High power Laser diodes is a very small share of the overall laser diode market, and that the part of this market associated to material processing of material is also very small [START_REF] Bachmann | Industrial applications of high power diode lasers in materials processing[END_REF] . This is mainly because beam quality is still an issue with diode lasers when a large number of emitters are combined. In contrast, single emitter lasers are not affected by this limitation. Single emitter diodes with powers up to 10W have been reported [START_REF] Al-Muhanna | High-power (> 10 W) continuouswave operation from 100-µm-aperture 0.97-µm-emitting Al-free diode lasers[END_REF] , and are commercially available up to 5W. It is clear that a material processing applications that would be satisfied using a single emitter laser diode, and that would be driven by a mass market, would benefit from the tremendous downscaling of the costs that are observed for all integrated semiconductor components. In this paper, we show that such a material processing application exists : the material is paper, and the process is cutting or scoring the paper to the desired format and shape Though paper is a very old and common material, it is also a modern media with strong connections with digital applications [START_REF] Sellen | The myth of the paperless office[END_REF] . This fact is supported by figure 1, that gives some key figures on the paper consumption in different countries. It should be noted that 30 to 40 % of this consumption in the US and in Europe are dedicated to graphics uses. For the US only, the value of cut sheet paper is 10,8 billion dollars in 2002, and should grow to 12.2 billion dollars by 2006 5 . Digital printing can also be viewed as a form of material processing. Key revenue figures related to worldwide home and office inkjet printing market are given on Fig. 2. The 32.2 billion dollar revenue of 2003 is expected to increase steadily in the next years, with an anticipated revenue of 46.6 billion dollars in 2008. Special media, including photo paper, greeting card-boards, labels of all kinds, pre-cut paper with a variety of formats for applications ranging from name badges to CD-Rom jackets, represent more than 10% of this value. This illustrates the need for special format printer output, which is presently addressed by proposing a large variety of media consisting of pre-cut paper. This figures show that paper cutting using a laser diode may be the first mass-market desktop application of laser processing of materials. Of course semiconductor lasers are already widely used for desktop printing in laser printer, but in that case the laser is used to write on the photosensitive material, and it is not used in direct interaction with the paper. Though it may sound less fanciful than laser cutting and joining of high-tech aerospace alloys, or micro-machining electronic devices, it is clearly a desirable feature in our "Digital Era" that future printers shall be able to cut paper to any desired format, and expand creation possibilities concerning paper shape just like it did concerning the variety and quality of images it can create on paper.

Turning cost constrains into innovation opportunities

CO 2 lasers are widely used in the paper conversion industry, for paper cutting and scoring [START_REF] Chrissolouris | Laser Machining Theory and Practice[END_REF] . They are well suited for this application, since paper is absorbing at 10.6µm wavelength. Besides, they exhibit high powers, good beam quality, satisfactory price/power ratio, and they allow cutting speeds of several hundred meters per minutes or more that are well suited to industry. The requirements for high power voltage, thermal management, and maintenance, are easily dealt with in industrial environments. Recently, desktop "plug and play" laser cutting apparatus have been marketed 6 . These systems can cut light wood, plastics, cardboard and paper. However, their costs are still two orders of magnitudes higher than a digital inkjet printer. The requirement for a high voltage supply, the need for precision mechanical mounting of laser mirrors, the low wallplug efficiency of the laser and the subsequent requirements on thermal management, are strong barriers for cost reduction. In contrast, mass produced single emitter laser diodes with a few Watts of optical power have a very limited cost, and support very few mounting, power supply, and thermal management costs. As a consequence, they would be very attractive as sources for paper cutting. However, the problem is that conventional paper is white not only in the visible range, but also in the near infrared. As a consequence, conventional NIR emitting diodes do not interact with the paper and cannot cut it. We brought an innovative solution to this problem by using a proper ink that absorbs the radiation of the laser. The cutting of the paper is performed by first tracing the line to be cut on the paper with the absorbing ink, and then the ray of the NIR laser is used to cut the paper. We named it technology Trace and Ray Cut Technology, or TRACTechnology 7 . The inking operation with the absorbing ink can be done by inkjet printing. So if you start from a conventional printer as a basis for conception of a Print and Cut system, the integration of an additional printhead is not expensive, and all the displacement of the laser relatively to the paper can be handled with the paper management and tray management of the printer. As a consequence, extra costs of the Cut function are related to the Laser diode, which makes this system very affordable. This invention is described in more detail elsewhere [START_REF] Acher | Peripheral which can be used to print and cut sheets of paper using a low-power laser source[END_REF] . The aim of this paper is to give experimental evidences of the feasibility of paper cutting using a single emitter diode laser, and a proper ink. The integration of all these functions into an inkjet printer are an industrial issue that is not further discussed.

EXPERIMENTAL DETAIL

Our laser cutting demonstration system is based on a 1W single emitter diode at 810 nm. The emitter width is 100µm, and the focusing optics consists in two aspherical condensers (L 1 : F23 and L 2 : F8). The power available on the paper is determined using a bolometer. The maximum power available is 0.8W, as no special care was taken to minimize parasitic reflections on the lenses. A beam splitter and a camera can also be used to visualize the focused beam on the paper. The paper is put on an Aluminium drum with black coating. A "low thermal conductivity drum" consisting of a mat of glass fiber was also used. Conventional Microncontrôle mounts have been used to provide easy adjustment possibilities of the focusing and control of the drum speed, and no attempt has been made to achieve compactness in this laboratory apparatus. A sketch and a view of the optical bench are given on Figure 3.

Our experiments have been performed on plain white office paper, 80g/m 2 grade. Several types of inks have been used to investigate the laser cutting. Black and green office marker have been used. The marking process was slow enough, so that the ink penetrated in the paper and the color began to appear at the back of the paper. We formulated an "invisible ink" using a commercially available pigment from Aldrich, denominated IR820, that absorbs in the NIR and is nearly transparent in the visible range. The dye was dissolved in a mixture of water and propan-1-ol (20%). This solvent was chosen because it allowed a better penetration of the ink within the paper, due to a lower surface tension. Lines to be cut were drawn on the paper using a thin brush or a fountain pain. Care was taken that the ink penetrates deep enough in the paper. light is reflected and 20% is transmitted. The black marker ink allows 90% or more absorption. The invisible IR ink allows about 80% absorption at the wavelength of the laser, and leaves only a very light pale green appearance.

RESULTS

Fig. 5a shows the cut obtained with the laser on a paper inked with a black marker, at a laser speed of 1.2m/min. It should be underlined that when the laser moved outside the black inked area, it even not left a mark on the paper. It proves the necessity of a suitably absorbing ink. Experiments were also performed on paper inked using a desktop printer, either a laser printer or an inkjet printer. In contrast with inking made using a pen marker or our specially formulated ink, the ink of printers remains on the very surface of the paper, and does not penetrate within the paper. In all cases, it was stated that the laser ablation was limited to the very surface of the paper: only the superficial ink layer was removed. This observation is coherent with the use of laser in cleaning superficially stained paper [START_REF] Kautek | Laser interaction with coated collagen and cellulose fibre composites: fundamentals of laser cleaning of ancient parchment manuscripts and paper[END_REF] for art conservation, or for generating media with tactile characteristics through ink ablation [START_REF] Stewart | Multipass laser ablation of three coloured ink from a paper substrate[END_REF] .

Figure 6 provides closer views of the laser cut on a paper inked using the black marker ink.

Further cutting experiments were also performed on paper marked using the IR absorbing invisible ink. It was found that slightly slower paper displacement speeds were required to obtain a complete cut. Fig. 7a gives a view of a complete cut obtained at 0.8W laser power, and at 0.75m/min. The marking IR absorbing ink is not visible. The cutting width is coherent with the spot diameter which is estimated about 30µm. For higher displacement speeds of the laser on the inked paper, it is observed that the cut is not performed all through the paper. A view of such incomplete cut is given on fig. 7b.

A complete investigation as a function of laser power and laser speed was performed on paper both inked with black marker ink and invisible ink. Results are displayed on figure 8. It is observed that a minimum power of 0.2 W is required to cut the inked paper. For significantly higher laser power, the speed at which complete cut of the paper occurs increases linearly with the available power. Black marker ink is obviously more efficient, since the ratio of the power by the threshold cutting speed is about 0.28J/cm fusing black ink, while it is of 0.5J/cm using IR absorbing invisible ink. This is attributed to incomplete laser absorption of paper inked with the invisible dye, and possibly to a degradation of the optical characteristics of the dye during the interaction process with the laser. The processing of inked paper at laser speeds higher than the threshold cutting speed is useful, since it can produce easily tearable lines, and easy folding lines. For speed over power ratio that are comprised between 100% and 120% of the threshold, the laser produces easy separation lines. It is easy to tear apart the two pieces of paper separated by such a line. The result is very tidy. For power over speed ratio comprised between 120% and 200% of the cutting threshold, easy folding lines are obtained. Laser processing proves to be a convenient way to score the paper, that can then be folded into three-dimensional objects. The folding lines are very tidy.

Figure 7: laser cut of paper inked using an invisible absorbing ink; left: complete cut obtained with a cutting speed of 0.75m/min; right : incomplete cut obtained with a laser speed of 1.2m/min.

Figure 8 : cutting performance recorded at different laser powers and laser speeds, for black ink (squares) and "invisible ink" (triangles). Full marks correspond to complete cut, and hollow mark correspond to incomplete cut. The lines describe the asymptotic dependence of the maximum cutting speed with the laser power. The cutting of stronger paper, with surface weight up to 3 times that of conventional office paper, has also been achieved. It was found that for a given laser power, the cutting speed is nearly proportional to the inverse of the weight of the paper.

Experiments have also been conducted on photo paper. It has been found that the glossy surface to be printed is quite impermeable to the absorbing ink, which is detrimental to the quality of the cut. A solution was found by inking the paper on the back side with the invisible ink, and good quality results were then obtained. The influence of the quality of the beam focusing has also been investigated. As expected, it is observed that the higher cutting speeds are obtained when best focus is obtained. The influence of the thermal properties of the substrate supporting the paper has also been investigated. In particular, it has been shown that when the underlying support material has a low thermal conductivity, the combustion zone of the paper extends to a width significantly larger than the spot width, and a flame may be visible. The result is not tidy. A similar effect can be observed when the paper is not properly applied against its metallic support.

DISCUSSION

It is interesting to compare the lineic energy E l required to cut a unit of length in our experiments and in conventional CO 2 system. Reference 1 gives indications on high power CO 2 lasers used in the paper conversion industry. The cutting speed reported for a 250W laser on 75µm thick paper corresponds to E l =0.9J/cm energy, that of a 70kW laser is about 2.6J/cm. In our experiments, we achieved lineic energies E l =0.5J/cm using our invisible ink, and as low as E l =0.28J/cm using black ink. This shows that though industrial CO 2 paper cutting systems differ by several order of magnitudes from our system devised for desktop printing, lineic energies required for cutting are comparable. We achieve somewhat better efficiency in our system, possibly because of better focusing.

A very simple model can be proposed to account for E l . The paper is supposed to degrade at a temperature T d ; the radial profile of the laser beam is assumed to be uniform over a disk of radius R ; the deposition of heat within the paper is supposed to be uniform over a thickness δ (related to the features of optical absorption of the paper at the laser wavelength) ; and heat transfer between the paper and the environment is neglected. Under these circumstances, an order of magnitude of the energy per unit length E l can be expressed as :

p d l R C T P E v 2 ρ π δ ∆ = = (1)
where ρ and C p are the density and specific heat of paper, and ∆T d = T d -T a is the temperature elevation from the ambient temperature T a to the degradation temperature T d .

Applying formula (1) with the following numerical values : ρ = 800 kg/m 3 (corresponding to 80 g/m 2 paper grade), R = 30 µm (value representative of our experiments), δ = paper sheet thickness = 100 µm, C p = 1500 J/kg/K (measured by DSC) and ∆T d = 400K (temperature elevation at which the paper turns into flame), one obtains for E l the value of 0.02 J/cm, i. e. about one order of magnitude less than the E l values observed experimentally. The simplistic model described above must therefore be improved in order to better account for the different physical phenomena that occur in the laser paper cutting experiments. In particular, one may suspect that the energy required to degrade the paper is significantly larger than the evaluation introduced in this model. In addition, thermal diffusion of the heat produced by the laser should not be neglected. Though the presence of the substrate with a high thermal conductivity may increase the lineic energy required to obtain a complete cut, our experiments proved that it is absolutely essential that the substrates acts as a heatsink in order to avoid uncontrolled combustion of the paper. Though in our experiments the inking has been done with a fountain pain, the possibility of performing the inking using an inkjet printer is being demonstrated. Consideration on chemistry have been used to find proper solvent, in order to have a proper penetration of the ink in the paper, and a proper viscosity; results shall be reported elsewhere. Inkjet printers are now achieving much more challenging material deposition issues [START_REF] Sirringhaus | Inkjet printing of functional materials[END_REF] . Price quotations for 1W cw laser diodes are in the 30$ to 40$ for large quantities. Mass-produced focusing optics adapted to laser diodes have been developed for CD and DVD industry, and are expected to be cheap. As a consequence, the key components that should be added to inkjet printers to perform cutting and scoring operations are compatible with mass-market applications. The cutting speeds of 1.2m/min achieved for 1W optical power and invisible ink is compatible with a few pages per minutes throughputs common to personal printers. The speed can be increased by a factor of 5 using commercially available 5W cw laser diodes. This gives opportunities for market segmentation, with higher throughput and more expensive products on the one hand, and cheaper and slower products on the other hand. The expected decrease of the price per Watt of optical power may further drive replacement market for years. It should be mentioned that an already successful development of laser processing of material using an IR absorbing pigment transparent in the visible range has been reported. It consists in laser welding transparent polymer films using a NIR laser 12,[START_REF] Frieder | Welding with lasers[END_REF] .

APPLICATIONS AND MARKETS

Existing markets addressed through pre-formatted supports

The requirement for special format outputs in digital printing is presently addressed through a variety of special format media, or precut media. Special format photo-paper, CD labels, fancy Christmas greeting cards, are very commonly marketed media that address these needs. For business applications, a much larger variety of pre-cut media exist, from address labels to badge name cards, or from fancy stickers to thumbnail organizers 14 . Many other needs for special format support are addressed through conventional printing companies, that generally use dye cutting to make special shapes. The possibility of addressing the market of special format through a cutting and scoring ability in the printer is a very clear advantage, since it does not require to buy a special format media for each application, creation is easy, and format can be tailored to the precise needs of the user through proper software.

Print and Cut systems for the sign industry

A straightforward process to cut thin sheet media is to use knives and blades. The sign industry has been using successfully mechanical cutting on so-called "cutting plotter" for years 15 . These systems require special vinyl media, and they are not intended to cut paper. They are not able to cut any shape, since the curvature radius of the cutting that this systems can performed is limited. Recently, print-heads have been added to some of these systems. These "Print and Cut" systems are well suited for the sign industry, but they are not adapted to office paper media.

Perspectives for desktop cutting applications and markets

Laser cutting of light material has been investigated as a possible first step toward desktop personal fabrication devices, in particular by the MIT MediaLab. In particular, "Desktop Fabrication" and "LaserLogo" from the Grassroots Invention Group, or "Personal fabrication" Special Interest Group 16 , report possible future uses of laser cutting of material. But it does not seem that printing and laser cutting of paper has been envisioned in these works. The applications of this technique is not only in moving the value from special formats media to the desktop printing machine by addressing already existing applications. It clearly expands creation ability in the area of Digital Photography (see Fig. 9), office and small business organization (Fig. 10.), and graphics creation (Fig. 11). Of course, this makes sense only if software used for these applications assist the user in including cutting and scoring features. In turn, it opens significant opportunities for new softwares or updated version of existing softwares that would include this possibilities.

CONCLUSION

We have addressed the question whether laser processing of materials may have mass-market applications in the next years. For simple price reasons, we found this is possible in the near future only if such application requires single emitter laser diodes emitting in the NIR. Such lasers have been demonstrated with powers up to 11W, they are commercially available with powers up to 5W, and the present cost is less than 40$ for 1W. These orders of magnitudes suggest that only thin materials can be processed, with a moderate speed. As a consequence, paper is a good material candidate for such mass market application. However, though laser cutting of paper is a well-proven industrial technique, laser diodes emitting in the NIR can not cut plain office paper because the optical properties of the paper are not suitable for that: white paper remains white, and therefore non absorbing, in the NIR. We have shown that using suitable inks that are absorbing at the wavelength of the laser, very tidy cut could be obtained, with cutting speeds ranging from 1.2m/min to 6m/min for powers ranging from 1 to 5 W. These speeds seem compatible with desktop digital printing applications. In addition, the digital printing environment provides easily solutions to dispose properly the absorbing ink, and to computer-assist the whole creation and realization process. While laser diodes have first reach mass market through storage applications (CD players), further extended trough digital printing and telecom applications (laser printers, fiber optics), high power laser diodes may reach mass market through a material processing application in close connection with digital printing. This innovation may be viewed as a first step into desktop laser-assisted personal fabrication devices.

Figure 1 :

 1 Figure 1: Key figures of the overall paper consumption in different countries.

Figure 2 :

 2 Figure 2: Key figures of inkjet digital printing.

Figure 3 :

 3 Figure 3: top: sketch of the experimental setup; bottom view of the experimental system (without the beam splitter, camera and bolometer).Optical properties of white paper inked with different dyes have been measured with a VARIAN spectrophotometer in the 300 to 1500 nm range. An integration sphere has been used to collect both specular rays and diffusion, to determine the total transmittance T and total reflectance R. The absorbency (A) is deduced from A=1-T-R. Results are presented on figure 4. It can be observed that the white paper absorbs less than 5% of the visible and NIR light. About 80% of the

Figure 4 :

 4 Figure 4 : Absorbency spectra of white paper and the same paper inked with black or infrared inks.

Figure 5 :

 5 Figure 5 : laser processing of inked paper : a) complete cut of the paper obtained on a mark made using a black marker b) superficial ablation of the ink deposited using a laser printer

  black ink, complete cut black ink, no cut NIR ink, complete cut NIR ink, no cut

Figure 9 :

 9 Figure 9: illustration of a possible use of paper cutting ability within a desktop printer, associated to Digital Imaging and Printing.

Figure 10 :

 10 Figure 10: illustration of a possible use of paper cutting ability within a desktop printer, associated to office and small business applications.

Figure 11 :

 11 Figure 11: illustration of a possible use of paper cutting ability within a desktop printer, associated professional graphics applications.

Proc. of SPIE Vol. 5711

Proc. of SPIE Vol. 5711 111

Proc. of SPIE Vol. 5711

Proc. of SPIE Vol. 5711 113

Proc. of SPIE Vol. 5711

Proc. of SPIE Vol. 5711 115

Proc. of SPIE Vol. 5711

Proc. of SPIE Vol. 5711 117

Proc. of SPIE Vol. 5711

Proc. of SPIE Vol. 5711 119

Proc. of SPIE Vol. 5711


Alain Darte

Alexandre Isoard

Tomofumi Yuki

Yuki Tomofumi

Compsys

Liveness Analysis in Explicitly-Parallel Programs

Keywords: Polyhedral analysis and optimizations, memory contraction, interference graphs, parallel languages

In this report, we revisit scalar and array element-wise liveness analysis for programs with parallel specifications. In earlier work on memory allocation/contraction (register allocation or intra-and inter-array reuse in the polyhedral model), a notion of "time" or a total order among the iteration points was used to compute the liveness of values. In general, the execution of parallel programs is not a total order, and hence the notion of time is not applicable. We first revise how conflicts are computed by using ideas from liveness analysis for register allocation, studying the structure of the corresponding conflict/interference graphs. Instead of considering the conflict between two live ranges, we only consider the conflict between a live range and a write. This simplifies the formulation from having four instances involved in the test down to three, and also improves the precision of the analysis in the general case. Then we extend the liveness analysis to work with partial orders so that it can be applied to many different parallel languages/specifications with different forms of parallelism. An important result is that the complement of the conflict graph with partial orders is directly connected to memory reuse, even in presence of races. However, programs with conditionals do not always define a partial order, and our next step will be to handle such cases with more accuracy.

Analyse de durées de vie dans les programmes explicitement parallèles

Résumé : Dans ce rapport, nous revisitons l'analyse de durée de vie (vivacité) des scalaires et des éléments de tableaux pour des programmes comportant des spécifications parallèles. Les précédents travaux sur l'allocation/contraction mémoire (allocation de registres ou réutilisation de tableaux dans le modèle polyédrique) utilisaient une notion de "temps" ou d'ordre total entre les itérations pour calculer la vivacité des valeurs. En général, l'exécution de programmes parallèles n'est pas un ordre total, et donc la notion de temps est mal définie. Nous révisons tout d'abord le calcul des conflits entre éléments mémoire en utilisant des idées provenant de l'analyse de durée de vie pour l'allocation de registres. Plutôt que de considérer le conflit entre deux intervalles de vie, nous considérons le conflit entre un intervalle de vie et une écriture. Ceci simplifie la formulation en n'impliquant plus, dans le test, que trois instances au lieu de quatre, et également améliore la précision de l'analyse dans le cas général.

Nous étendons ensuite l'analyse de vivacité pour prendre en compte des ordres partiels de sorte qu'elle puisse s'appliquer à différents langages ou spécifications parallèles, avec des formes différentes d'expression du parallélisme. Un résultat important est que le complémentaire du graphe de conflits, dans le cas des ordres partiels, est directement lié à la formulation de la réutilisation mémoire, même en cas d'accès concurrents (races). Néanmoins, les programmes comportant des conditionnelles ne définissent pas toujours d'ordre partiel, et l'étape suivante sera de traiter ces cas avec plus de précision.

Mots-clés :

Analyses et optimisations polyédriques, repliement mémoire, graphe d'interférence, langages parallèles

Introduction

Modern processors are equipped with several levels of memory hierarchy to keep the data as close as possible to the processing units. Because the locality of reference has significant impact on performance and energy consumption, efficiently utilizing storages at various levels-registers, caches, memories, and so on-has been a topic of many research.

One important analysis, common to many optimizations around storage, is liveness analysis. Live-ranges are used to determine if two values can share a same register and/or a memory location. It is also used to compute live-in/liveout sets, as well as to estimate memory footprint for predicting cache behaviors. Existing techniques [START_REF] Darte | Lattice-based memory allocation[END_REF][START_REF] Lefebvre | Automatic storage management for parallel programs[END_REF][START_REF] Quilleré | Optimizing memory usage in the polyhedral model[END_REF][START_REF] Wilde | Memory reuse analysis in the polyhedral model[END_REF] mostly assume sequential execution, or only simple forms of parallelism, when computing live-ranges. In this paper, we revisit RR n°8839 liveness analysis for parallel programs, with the ambition to have a common framework suitable for all parallel specifications.

Our contribution is twofold: by analyzing and exploiting the structure of interferences (conflicts between live-ranges), we provide a more efficient analysis for the sequential case, which can be extended to handle some structured forms of parallel specifications (such as nesting of parallel and sequential loops), namely series-parallel graphs. We then provide a generic approach to handle parallel specifications, in particular those based on an happens-before partial order.

We first motivate our work by illustrating the difficulties with liveness analysis in Section 1.1 and recall in Section 1.2 the notion of conflict that we use in formulating the liveness. We then present simplifications to the computation of liveness inspired by register allocation methods in Section 2 and extend these algorithms to general parallel specifications in Section 3. Finally, we discuss some links to other storage mapping techniques in Section 4 and conclude in Section 5.

Liveness, Conflicts, and Reuse

We first introduce the readers to liveness analysis and memory reuse, and the difficulties that arise when we add complications such as parallelism. Register allocation and array contraction through intra-array reuse are two similar forms of memory reuse, the latter being a symbolic version of the first. Liveness analysis is here to make sure resource sharing does not change the semantics of the code. The simplest example of register allocation is the following: x = ...; y = x + ...; ... = y ;

where the scalar y can reuse the memory element allocated to x, assuming x is never ever used later. The last condition is important, as it enforces that the lifetime of x ends right before the creation of y, thus allowing its reuse.

With loops and arrays, memory reuse becomes less straightforward. The same strategy applied on the following code

c [0] = 0; for ( i =0; i < n ; ++ i ) c [ i +1] = c [ i ] + .
..; can easily fold the c[] array into a single scalar c (thus simply removing the subscript). Again, this assumes that for all i (except potentially the last one) c[i] is never ever used later. Now, let us first consider nested loops and multidimensional arrays, then parallelism. For example, the following code requires a more precise analysis but with the same idea:

for ( i =0; i < n ; ++ i ) for ( j =0; j < n ; ++ j ) A [ i ][ j ] = A [i -1][ j -1] + A [i -1 , j ] + A [i -1 , j +1];
We cannot store a value (purple square in Figure 1a) in the same location as values that are still live (surrounded in orange). Those are said to be conflicting array elements. However, if we ignore live-in/live-out values, we can reuse any other ones. By reusing along the diagonal (see the mapping only n + 1 cells instead of n 2 is obtained. This is the idea used in standard array contraction techniques [START_REF] Darte | Lattice-based memory allocation[END_REF][START_REF] De Greef | Memory size reduction through storage order optimization for embedded parallel multimedia applications[END_REF][START_REF] Lefebvre | Automatic storage management for parallel programs[END_REF][START_REF] Quilleré | Optimizing memory usage in the polyhedral model[END_REF].

a[i][j] → a[(j-i)%(n+1)] below the figure), a minimal allocation requiring j i a[i][j] → a[(j-i)%(n+1)] (a) Sequential. j i a[i][j] → a[i%2][j] (b) Parallel on j.
When we try to handle parallelism, we have to consider all potential conflicts that may happen in one of all the possible parallel executions. On the previous example, if the j loop is parallelized, we end up with additional conflicts due to parallel iterations being potentially past or future. The new mapping a[i][j] → a[i%2][j] requires 2n cells, which is more than previously; as expected, increased parallelism comes at the cost of additional memory space.

All these examples can be handled by standard techniques, if the conflict analysis is computed with care. However, depending on the way the analysis is done (in the standard way, it implies 6 dimensions: 2 memory locations and 4 references, a write and a read accesses for each), it can be rather costly: we give in Section 2 two variants involving fewer dimensions. Moreover, there is a multitude of forms of parallelism-from software pipelining (see Figure 2a and Figure 2b, which will be detailed later on) to X10-like parallelism [START_REF] Saraswat | X10 language specification version 2[END_REF]-that are too complex to be modeled by such nested loops programs. They call for a more general framework based on a more general "happens-before" relation. Section 3 will extend this analysis to such a model. This will give us some new insights to re-interpret, with this new view, some previous works on memory reuse and possibly extend them (see Section 4).

Simultaneously Live Indices

Lattice-based memory allocation [START_REF] Darte | Lattice-based memory allocation[END_REF][START_REF] Darte | Lattice-based memory allocation[END_REF], as well as all prior work on intra-array reuse [START_REF] De Greef | Memory size reduction through storage order optimization for embedded parallel multimedia applications[END_REF][START_REF] Quilleré | Optimizing memory usage in the polyhedral model[END_REF][START_REF] Lefebvre | Automatic storage management for parallel programs[END_REF][START_REF] Darte | Lattice-based memory allocation[END_REF], is based on the concept of "conflicting" (array) elements. The set of pairs of elements that should not be mapped to the same location is expressed as a binary relation denoted as . It corresponds to the well-known interference graph in register allocation. It can also be used in other contexts such as for bank allocation or parallel accesses to memory [START_REF] Cilardo | Improving multibank memory access parallelism with lattice-based partitioning[END_REF][START_REF] Darte | Lattice-based memory allocation[END_REF], or more generally whenever renewable resources need to be shared. In register allocation, vertices correspond to the scalar variables of the program, edges denote the fact that two variables should not be mapped to the same register, so that graph coloring can be used to derive a valid register assignment. For intra-array reuse, the variables are the array elements (but expressed in a symbolic way, not in an extensive way) and the edges are the pairs defined by the relation. Actually, this view of register allocation is a bit simplistic and limited. In register allocation, instead of considering that a vertex corresponds to a variable name, variables can be renamed during their lifetime (what is called live-range splitting) and each live-range can be assigned a different register. The same is true when a variable is spilled (i.e., moved with a store operation from a register to memory) because it can come back from memory (with a load operation) in a different register. The situation is similar, although different, for and array elements. To reduce the complexity of the analysis and of the code rewriting necessary to express the allocation, we consider that an array element is live from its very first access until its very last access1 and that it is mapped, in this time period, to the same memory location. But we could also cut its live-range into pieces, for example (but not only) distinguishing each live-range starting at a given write and ending at its last corresponding read (as done in exact data-flow dependence analysis as opposed to memory-based dependence analysis), and then map an array element to different memory locations, depending on the program control point. However, this makes the analysis much more complicated and, unlike register allocation where the number of registers is more limited, it is maybe not worth it for allocation in memory. Also, we will consider that there is a single level of memory, i.e., no value is ever spilled during its whole lifetime (this could be useful however, in particular when offloading data to a distant platform, but here we assume that such data movements are explicit in the code, i.e., the spilling has already been taken care of).

According to Definition 1 by Darte et al. [START_REF] Darte | Lattice-based memory allocation[END_REF], two array elements identified by the vectors m 1 and m 2 conflict (denoted m 1 m 2 ) if they are simultaneously live under a schedule θ. In their work, a schedule is a function (which can express parallelism) that assigns to each operation u a "virtual" execution time as an element of a totally ordered set (T , ) [START_REF] Darte | Lattice-based memory allocation[END_REF]. This definition is kept quite general, as an input to the allocation problem: what an "operation" is, what "simultaneously live" means, and how the values of θ are interpreted is not precisely defined. These notions depend on the context of use and are mostly illustrated for the particular case of affine multi-dimensional schedules, as defined by Feautrier [START_REF] Feautrier | Some efficient solutions to the affine scheduling problem, part II: Multi-dimensional time[END_REF], i.e., functions from operations u = (S, i) (pair statement, iteration) into Z d (for some positive integer d) associated with the lexicographic order , that are affine with respect to i. This defines an execution with inner parallelism in the following sense: if θ(S, i) ≺ θ(T, j) then (S, i) is executed strictly before (T, j), while if θ(S, i) = θ(T, j) then both operations are done "in parallel". Again, what "in parallel" means depends on the implementation. In particular, one may need to define precisely how different accesses within a given operation are scheduled, for example reads and writes, as indicated by Darte et al. [START_REF] Darte | Lattice-based memory allocation[END_REF] (Footnote 2, Page 3). We will come back to this situation later.

W x R x W y R y (a) Butterfly. W x R x t W y R y (b) Crossproduct. W x R x t W y (c) Triangle.

Special Case Extensions

We now describe how to define the relation in more general situations than multi-dimensional affine schedules. It was previously illustrated for quadratic schedules with two instructions [START_REF] Darte | Lattice-based memory allocation[END_REF], but more situations are of interest today. We first describe the "simpler" cases with sequential schedule and loop parallelism at any level (not just inner parallelism) that can still be handled as natural and incremental extensions of the classical analysis using live-ranges.

In Section 3, we further extend to other forms of parallelism such as software pipelining and parallel specifications with partial orders (happens-before relations) where such natural extensions are not directly applicable. Although the resulting method is more general, it may nevertheless be less efficient or expressive for handling special cases. For instance, it is not clear how to compute the minimal size of an allocation, or a lower bound of it, using clique computations when there is no notion of global time. Thus, it is still interesting to explore the limits of classical approaches as we do here.

Fully Sequential Schedules

For a fully sequential schedule, affine or not, all operations are done in some particular order, with no parallelism. Bee [START_REF] Alias | Bee+Cl@k: An implementation of lattice-based array contraction in the source-to-source translator Rose[END_REF] uses this property to consider that x y iff the first write of x (respectively y) is before the last read of y (respectively x), thus creating a "butterfly" diagram shown in Figure 3a. Computing this relation was deemed rather costly as it required them to perform a crossproduct of QUASTs [START_REF] Feautrier | Parametric integer programming[END_REF].

We can, instead, rely on the notion of (sequential) time step. This consideration gives a specific way of computing conflicting elements, similar to the liveness used for register allocation, using live sets. For each time step t ∈ T , we can first identify the set Live(t) of all values considered live at t, i.e., to be stored in memory "during" t. Then, all values live at t are conflicting with each other as shown in Figure 3b (they form a clique using graph terminology), i.e., the set of conflicting pairs is t∈T (Live(t) × Live(t)). As for register allocation, one needs to carefully define the liveness2 with respect to θ. A memory location m is live at t if there are two operations3 , a write (S, i) and a read (T, j) of m with θ(S, i) t θ(T, j). The equality is necessary if one considers that a variable spanning a single time step requires storage. This depends on the granularity of the "operation". If one restricts the analysis to variables whose live-range spans at least two time steps, then one can define liveness with one strict inequality, e.g., with θ(S, i) ≺ t θ(T, j), or consider the "program points" between two time steps. In back-end optimization, to avoid confusions, one distinguishes live-in and live-out variables for each program instruction.

Let us illustrate these different points with the example corresponding to Figure 1a. The code has a single statement. The sequential order defines a 2-dimensional schedule with θ(S, i) = i and the lexicographic order. However, this schedule does not specify the order of accesses inside an operation. If all reads are performed before the write, then one can add a dimension to the schedule, distinguishing reads and writes, with θ (S, i, R) = ( i, 0) for a read and θ (S, i, W ) = ( i, 1) for a write, and then consider all 3-dimensional time steps. One can also proceed in an ad-hoc fashion, without this additional dimension, as follows. In general, to be always correct, one should consider all program points ("events") between any two accesses. This includes the program points between the reads and the writes of a given operation, in addition to those between operations. However, since reads precede writes in a given operation, it is sufficient to consider only the liveness at program points between operations (all conflicts are seen there). So, let us consider each time step t-here in 2D, a vector t = (t 1 , t 2 )-and let us interpret it as the program point just before the reads and writes scheduled at time step t. Then:

Live( t) = { m | i ∈ D S , i ≺ t, i = m} ∩ { m | j ∈ D S , t j, ( j -(1, 1) = m or j -(1, 0) = m or j -(1, -1) = m)}
where D S is the set of valid iterations for statement S, giving:

Live( t) = Live((t 1 , t 2 )) = {(t 1 , m 2 ) | 0 ≤ t 1 ≤ n -2, 0 ≤ m 2 ≤ n -1, m 2 ≤ t 2 -1}∪ {(t 1 -1, m 2 ) | 1 ≤ t 1 ≤ n -1, 0 ≤ m 2 ≤ n -1, t 2 -1 ≤ m 2 }
as depicted in Figure 1a. Such computations can be done with the iscc calculator [START_REF] Verdoolaege | Counting affine calculator and applications[END_REF], provided with the barvinok library [START_REF] Verdoolaege | Counting integer points in parametric polytopes using barvinok's rational functions[END_REF], with the following script: In this script, the set Live-a map from time indices t to array elements A[ m]-is built as previously described. The set Conflict is then defined as Live^-1.Live, which directly builds the union, for all time steps t, of the pairs of array elements live at the same time step. It corresponds to the composition (join) of the map A[ m ] → t with the map t → A[ m], i.e., with t = t. Note that, with this construction, an array element conflicts with itself, thus 0 is a conflicting difference. Then Delta gives the set of conflicting differences, which can be used for memory mapping:

# Inputs Domain := [n] -> { S[i,j] : 0 <= i, j < n }; Read := [n] -> { S[i,j] -> A[i-1,j-1]; S[i,j] -> A[i-1,j]; S[i,j] -> A[i-1,j+1] } * Domain; Write := [n] -> { S[i,j] -> A[i,j] } * Domain; Sched := [n] -> { S[i,j] -> [i,j] }; # Operators Prev := { [i,j]->[k,
Delta(n) = {(1, i 1 ) | i 1 ≤ 0, n ≥ 3, i 1 ≥ 1 -n}∪ {(0, i 1 ) | i 1 ≥ 1 -n, n ≥ 2, i 1 ≤ -1 + n}∪ {(-1, i 1 ) | i 1 ≥ 0, n ≥ 3, i 1 ≤ -1 + n}
From this set, one can infer, using modulo allocation techniques, that the mapping A[i, j] → A [j -i mod (n + 1)] of size n + 1 is correct. Computing the cardinal of the Live set at any time step (with the iscc operation card) gives a maximum size of n + 1 for n ≥ 3, which proves the optimality of this mapping, as claimed in Section 1.1.

If one wants to keep at all time the information on the time step t, an alternative method can be used as follows:

# Other solution, with liveness for each time step CLive := Live cross Live; EqualMap := domain_map identity domain Live; DeltaMap := deltas_map ((range Read)->(range Read)); TConflict := (EqualMap^-1).CLive; TDelta := TConflict.DeltaMap;

The set CLive has type [ t → t ] → [A[ m] → A[ m ]]. Then, the set TConflict has type t → [A[ m] → A[ m ]]
and gives, for a given time step t, the set of pairs of array elements A[ m] and A[ m ] live at t. Finally, the set TDelta gives the set of conflicting differences for a given time step t. Its range should give the same conflicting differences as Delta before.

Finally, to be complete, one should also consider live-in and live-out array elements. Unless they are stored in a different array, live-out array elements must be specified by the context and added to the previous analysis as reads after any time step. They can be computed as we now explain.

ReadAfterT := Preveq.(Sched^-1).Read + ((range Sched) -> LiveOut);

Similarly, unless all values defined by the kernel are stored in a fresh temporary array, live-in array elements must be computed and integrated in the set of values written before any time step. This can be done as follows:

SchedPrev := Sched.(Prev^-1).(Sched^-1); LiveIn := range(Read -SchedPrev.Write)); WriteBeforeT := (Prev^-1).(Sched^-1).Write + ((range Sched) -> LiveIn);

The cross-product of Live is the most expensive operation. In particular, if Live is composed of a union of polyhedra, the result will have many polyhedra due to the disjunctive expansion. To mitigate the problem, simplifying the expression using heuristics (provided by isl [START_REF] Verdoolaege | isl: An integer set library for the polyhedral model[END_REF] in our case) is particularly efficient but is, in itself, expensive too. A slightly different approach is to apply the same strategy than used for register allocation itself: two memory elements conflict if and only if one is live at the definition (write) of the other. This strategy, depicted in Figure 3c, can be implemented in the following way:

WriteBeforeT := (Preveq^-1).(Sched^-1).Write; ReadAfterT := Prev.(Sched^-1).Read; WriteAtT := (Sched^-1).Write; Live := WriteBeforeT * ReadAfterT; Conflict := (Live^-1).WriteAtT; AsymDelta := deltas Conflict;

Sym := { A[i,j] -> A[i,j]; A[i,j] -> A[-i,-j] }; Delta2 := Sym(AsymDelta);
Notice that time step consideration changed. We are interested in conflicts produced by a Write, i.e., conflicts that exist at the time step after the Write. Thus, compared to the previous script, we compute conflicts one step earlier by shifting the Live range into the future. This consists in swapping Prev and Preveq in the equations, with no computational overhead. However, the computed Conflict is now potentially asymmetric. We make it symmetric in the end to be consistent with the previous method. While this operation is purely syntactic, thus not costly by itself, it may lead the isl library to compute expensive disjoint unions, which it prefers. However, this did not have any significant impact on tested examples. Also, it is not required if the following uses of the analysis do not require symmetry. Furthermore, the switch to this method comes with an additional benefit in the case where we accept undetermined control flow. Indeed, as for register allocation, we might eliminate conflicts that were inconsistent. A standard example is what we call the "double diamond" case: if (...) then x = ...; else y = ...; if (...) then ... = x ; else ... = y ;

RR n°8839

Here, live-ranges of x and y technically interfere right in between the ifs. However, there is no valid execution where both are live at the same time (unless the program is incorrect on purpose), so they can share the same register. In fact, the only executions that make sense are the ones where the same branch is taken in both ifs, otherwise the variables are used without being defined. Our write-based analysis will consider that there is no conflict as, indeed, none of them is written while the other is live. Only one of them can ever be written (writes are in separate branch of the same if).

Undetermined control flow introduces many more problems [START_REF] Cohen | Program Analysis and Transformation: From the Polytope Model to Formal Languages[END_REF] and is not the focus of this paper. However, the framework developed in Section 3 must consider it may exist.

Affine Schedules and Parallel Loops

Now, consider the same example but with the innermost loop marked as parallel (see Figure 1b). This corresponds to the schedule (i, j) → i. In this code, all iterations of the j loop can run in parallel, however several semantics are possible. If the parallel loop is a Fortran-like FORALL loop, all reads of the j loop occur before any write. In this case, there is still a notion of "time step", actually, each iteration of the i loop corresponds to two time steps: a step with all reads for the different values of j and a step with all writes for the different values of j. The liveness can then be computed with the same principle as for a sequential code, with either the Live × Live approach or the Live × Write approach, exposed in Section 2.1. The only difference is the definition of the Prev and Preveq relations that depend on the schedule dimension:

Prev := { [i,j] -> [k,l]: i < k}; Preveq := { [i,j] -> [k,l]: i <= k};
With these definitions, we get that the set of live values at time step (k, l) is the full column A[k -1, * ] for 0 < k < n, and only one column of A is needed if array contraction is performed. However, with a more general parallel loop semantics, and without any information on the order of parallel accesses, reads and writes of different iterations of the j loop should be considered as possibly running concurrently. In other words, a safe definition of liveness is with Preveq instead of Prev in the definition of Live:

WriteBeforeT := (Preveq^-1).(Sched^-1).Write; ReadAfterT := Preveq.(Sched^-1).Read;

With this modification, we find that the live values are two successive columns of A, which is the expected set described in Figure 1b (and also the expected size of the contracted array). Indeed, when a value is written, all values of the preceding column may still need to be read. It is interesting to notice here the difference in memory size with the sequential execution. If the i and j loops are run sequentially, we saw that the array can be contracted into an array of size n + 1 with the mapping A[i, j] → A [j -i mod (n + 1)], which is nothing but the mapping A[i, j] → A [ni + j mod (n + 1)], a mapping that the methods of De Greef, Catthoor, De Man [START_REF] De Greef | Memory size reduction through storage order optimization for embedded parallel multimedia applications[END_REF] and of Quilleré-Rajopadhye [START_REF] Quilleré | Optimizing memory usage in the polyhedral model[END_REF] would find.

Of course, the previous computation is based on an over-approximation of the standard semantics. It ignores the fact that, in a parallel loop, there is still RR n°8839 some sequentiality, for each iteration, inside the body of the loop. As mentioned by Lefebvre and Feautrier [START_REF] Lefebvre | Automatic storage management for parallel programs[END_REF] (end of Page 656), taking this additional order into account may be needed to avoid considering that a read occurring before a write within a given statement instance induces a conflict. Note however that, in the previous example, such accuracy is not needed because a conflict still occurs due to other reads and writes on the same array element: each value defined in a parallel front is read in several iterations of the next parallel front. But such cases could arise (see the example later). To handle them in an exact manner, we could compute conflicts as before, with a Live × Live strategy, and then remove the pairs corresponding to live-ranges ending and starting at the same iteration. But set differences are likely to be more expensive, and also, the removal of conflicts needs to be done with care because the live-ranges can still be conflicting due to other accesses. Another possibility is to build directly the right conflicts, without computing set differences: The computation is done for each particular iteration (i, j), including the parallel counter j. The inequality l = j in the definition of PrevEqDiff is used to identify all live-ranges that fully "cross" this iteration, or that start or end at a parallel (but different) iteration. These live-ranges conflict with any live-range with a read or a write at iteration (i, j). This is not a Live×Live strategy (which would rather be hierarchical), but it is symmetric, because each pair of conflicting live-ranges is computed for one endpoint of each live-range. A Live×Write strategy would rather define the conflicts by: Conflict := (LiveCross^-1).(LiveStart); Delta := Sym(deltas (Conflict)); or even

# Operators PrevEqDiff := { [i,j] -> [k,l]: i < k; [i,j] -> [i,

Conflict := (LiveCross^-1).(WriteAtT);

The following code (whose iteration domain is depicted in Figure 4a) is an example where paying attention to the sequentiality in the loop body pays off. for ( i =0; i < n ; ++ i ) for parallel ( j =0; j < n ; ++ j ) Here, if care is not taken, two successive columns of the array seem to conflict. But with the previous exact method, the set of conflicting differences is as depicted in Figure 4b. Then, the mapping A[i, j] → A [i + j mod (n + 1)], which is not so easy to find automatically, is a suitable array contraction. The nesting of sequential and parallel loops can be handled in the very same way. For example, with a schedule (i, j, k, l) where j and l are parallel, we just need to define the relation PrevEqDiff as follows:

A [ i ][ j ] = A [i -1][ j -1] + 1 RR n°8839 j i (
PrevEqDiff := { [i,j,k,l] -> [i',j',k',l']: i < i'; [i,j,k,l] -> [i,j',k',l']: not (j = j'); [i,j,k,l] -> [i,j,k',l']: k < k'; [i,j,k,l] -> [i,j,k,l']: not (l = l') }
Then, again, one can compute the live-ranges that overlap with the time step (i, j, k, l) and make them conflict with the live-ranges with reads or writes at time (i, j, k, l). However, note that the corresponding "interference" graph (i.e., the conflicting pairs) may not be an interval graph anymore, because the underlying task graph is not a linear sequence of operations (here it is a series-parallel graph). It is not chordal either (unlike for SSA [START_REF] Bouchez | Register allocation: What does the NP-completeness proof of Chaitin et al. really prove?[END_REF]), i.e., a chordless cycle of length 4 is possible. This arises in this last example where

A[i, j], A[i, j + 1], A[i -1, j + 1], A[i -1, j + 2] form a conflicting cycle, but A[i, j] and A[i -1, j + 1]
do not conflict, and neither A[i, j + 1] and A[i -1, j + 2]. Nevertheless, the conflict graph has still some structure that will be explored later on.

Partial Orders and Beyond

The particular case of sequentiality in parallel loops, as exposed in Section 2.2, already shows the limit of reasoning with a concept of time step, where all variables "live" at this step are considered to be in conflict. Either such a notion of time step is difficult to extract from the description of the "schedule" or it simply does not exist and the conflict relation is not transitive. In this section,

RR n°8839

we extend the analysis to work with "happens-before" relations, and to partial orders, to handle parallel specifications.

The Need for Generalizations

Recall the two different software pipelines in Figure 2a and Figure 2b introduced in Section 1. The fact that these software pipelines were defined to organize a double-buffering execution of tiles (aggregation of loop iterations within boxes) and not simple iterations is not important. They can be summarized as partial orders specifying the execution of three types of statements: loads (L, i), computations (C, i), and stores (S, i), indexed by a single loop iterator i. Both define a "schedule" expressing some form of parallelism: computation tasks are organized as a sequence of tasks, communication tasks are also organized as a sequence of tasks, but with possibly some overlap between the two sequences (at "distance" at most 2).

The two different (periodic) schedules are implemented with synchronization mechanisms (arrows in the figures), imposing some precedence order. There is no explicit time step but, in these two particular cases, one can identify layers of parallel computations, fully sequentialized by a complete precedence graph between two successive layers (dotted horizontal lines in the figures). They can be used to define semantically-equivalent (in terms of liveness) schedules. For example, the software pipeline of Figure 2a behaves as the following schedule:

θ(L, 2i) = (i, 0), θ(C, 2i) = θ(L, 2i + 1) = (i, 1), θ(S, 2i) = θ(C, 2i + 1) = (i, 2
), θ(S, 2i + 1) = (i, 3). This representation assumes that statements scheduled at the same time step-such as (C, 2i) and (L, 2i+1)-behave as parallel statements (or statements in two different parallel iterations). Hence, it is equivalent to the following pseudo-code and can be analyzed as discussed in Section 2.2:

for ( i =...; i <...; ++ i ) { (L , 2 i ) ; do in parallel { (C , 2 i ) || (L , 2 i +1) }; do in parallel { (S , 2 i ) || (C , 2 i +1) }; (S , 2 i +1) ; }
The second software pipeline is a bit more tricky. It behaves as a schedule with a sequence of two parallel blocks, one performing (C, i), the other performing in sequence (S, i -1) then (L, i + 1). This is why a live-range ending in (S, i -1) and a live-range starting in (L, i + 1) can both overlap with any live-range live in (C, i), but do not overlap with each other. This time, the software pipeline behaves as the following code (excluding epilogue and prologue):

for ( i =...; i <... , ++ i ) { do in parallel { (C , i ) || { (S , i -1) ; (L , i +1) } }; }
To summarize, both software pipelines can be described and analyzed as described in Section 2.2. However, finding the right "layers" from the specification based on precedences among tasks is not obvious, and also it is not always possible. We now show how we can analyze the liveness directly from the description of a partial order among tasks: this is more general, easier when the notion of time step is not explicit, although the complexity may be higher as it depends on the number of statements more than on the number of time steps. It may also compute conflicting pairs in a redundant way (this is why the approaches of Section 2 may still be useful, for the cases where they can be applied, even if this should be supported by experimental evidence). The mechanism presented hereafter resembles the technique developed by Cohen and Lefebvre [START_REF] Cohen | Program Analysis and Transformation: From the Polytope Model to Formal Languages[END_REF][START_REF] Cohen | Storage mapping optimization for parallel programs[END_REF], but for slightly different purposes (partial memory expansion given a parallel specification).

Traces and Conflicts

We seek a method that, given a specification that may correspond to several executions, indicates that two memory locations conflict if there is an execution where they conflict.

An execution can be represented by a trace t, i.e., a sequence (a total order) of the operations executed. For each execution, we assume a canonical embedding (injective map) of its operations into a set of generic operations O. This embedding usually follows the syntax of the language and the structure of the AST. For example, in the parametric code for(k=n; k<2n; k++) S; the i-th operation a i,n for a given value of n, which corresponds to the execution of S for iteration k = n + i (when i < n), is in general abstracted by its code S and its "position vector" k. See also how operations are encoded for X10 analysis [START_REF] Yuki | Array dataflow analysis for polyhedral X10 programs[END_REF].

A given trace t may contain only a subset of these generic operations: we write a ∈ t if a is executed in t and a < t b if a ∈ t, b ∈ t and a is executed before b in t. By definition, < t is a total order for the operations executed in t. We define the relation S ∃ on O×O by: S ∃ (a, b) iff there is a trace t such that a < t b.

(

Then, two memory locations x and y conflict if their live-ranges (intervals) overlap for some trace. There are multiple ways of expressing this overlap. One can use a "butterfly" set of constraints [START_REF] Alias | Bee+Cl@k: An implementation of lattice-based array contraction in the source-to-source translator Rose[END_REF][START_REF] Darte | Lattice-based memory allocation[END_REF], involving 4 operations: W x (write of x), R x (read of x), W y (write of y), and R y (read of y), with the following order (see dotted arrows in Figure 5a):

W x < t R x , W x < t R y , W y < t R y , W y < t R x .
This symmetric method corresponds to the Live × Live approach of Section 2.1, given in Figure 3a. One can also reason, in an asymmetric manner, "at the time where y is defined" (as in the Live × Write approach of Figure 3c), with a set of constraints involving 3 operations, a write and a read of x (W x and R x ), and a write W y for y:

W x < t R x , W x < t W y , W y < t R x . (2)
Although equivalent for a given trace, the "triangle" approach (Figure 5b) is, for the same reason as for register allocation, more accurate when generalized to a case where not all operations are executed. We thus now focus on this one (Eq. 2)). We first replace the relation < t by the relation S ∃ :

S ∃ (W x , R x ), S ∃ (W x , W y ), S ∃ (W y , R x ). (3)
Note that this formulation is, in the worse case, an over-approximation. Indeed, it may be the case that there is no trace t where the 3 operations occur in this order while there are different traces where each two-by-two order is possible. However, in our context, this is most of the time equivalent, e.g., if all operations occur in all traces and if their scheduling freedom does not depend on their execution. 4Hereafter, we write ¬R the complement of a relation R. We can now define the relation R ∀ , generalization of the "happens-before" relations that we mentioned before, with R ∀ (a, a) for all a ∈ O, and, for a = b, with:

W x R x W y R y (a) Butterfly. W x R x W y (b) Triangle.
R ∀ (a, b) iff, for all traces t, a, b ∈ t implies a < t b. (4)
Since ¬R ∀ (a, b) iff S ∃ (b, a), Eq. ( 3) becomes (see Figure 5b):

¬R ∀ (R x , W x ), ¬R ∀ (W y , W x ), ¬R ∀ (R x , y ). (5)
Note that, in general, the relation R ∀ may be neither anti-symmetric, nor transitive, although Eq. ( 5) can still be used to compute conflicts. Consider all possible situations: (two branches of an if for example). The first two cases induce local asymmetry (but not necessarily transitivity) as in order relations. The third one corresponds to parallelism, as non-comparable operations in partial orders. In the last case, the relation is not asymmetric, and a and b will never contribute to conflicts because Eq. ( 5) cannot be true (they are never executed together). Note however that R ∀ defines a partial order if all operations are executed in any trace, e.g., for codes with no if conditions.

• If R ∀ (
If R ∀ is an under-approximation of R ∀ (i.e., R ∀ ⊆ R ∀ ), the relation R ∀ (and the corresponding S ∃ ) exhibits more traces, Eqs. (3) and ( 5) are more likely to be satisfied, and the resulting conflicts are thus conservative. One way to get a partial order (if needed) as an under-approximation of R ∀ is to make a consistent asymmetric choice between R ∀ (a, b) and R ∀ (b, a), for example by defining, for a = b: R ∀ (a, b) iff, for all traces t, a < t b or b / ∈ t (

(or the symmetric version with a / ∈ t). In this case, R ∀ (a, b) implies that if b is executed, a is always executed too, and interpreted as "the execution of a is always visible to b". Assuming that all operations execute at least once, one can easily prove that R ∀ is anti-symmetric and transitive, thus a (strict) partial order. Now let us focus on partial orders.

When R ∀ is a partial order , Eq. ( 5) becomes:

R ≺ W x , W y ≺ W x , R x ≺ W y . ( 7
)
This situation, where the freedom of parallelism (the set of all possible executions, and even more) is described through some representation (scheduling function or language constructs) expressing a partial order , is very common. This is the case in all previous examples (sequential code, nested loop parallelism as in OpenMP, software pipelining). The X10 "happens-before" relation (at least in the setting of affine control loops with async/finish keywords [START_REF] Yuki | Array dataflow analysis for polyhedral X10 programs[END_REF]) is also a partial order. Darte and Isoard [START_REF] Darte | Exact and approximated data-reuse optimizations for tiling with parametric sizes[END_REF] have also used an under-approximation of R ∀ to get a partial order and make liveness analysis for parametric tiling feasible, in a more accurate way than with Eq. ( 6) (see also the discussion in Section 4). Note that R x ≺ W y means that either W y ≺ R x or W y and R x are not comparable, i.e., can be executed in parallel (W y || R x ). When can be expressed in a (piece-wise) affine way, the conflicts can be computed similarly. Eq. ( 7) has some similarity with the Live × Write method (Section 2.1). There is no absolute time, but we can reason relative to the "time" when W y is being computed to see if W x may happen before W y and, similarly, if R x may happen after W y .

Partial Orders and Structure of Conflicts

We have shown how to compute conflicts given an extended concept of happensbefore relations and partial orders. In this section, we prove the following important structure theorem on conflicts for partial orders: Theorem 1 For a partial order , with no dead code, no undefined read, but possibly data races, the complement of the conflict graph is a comparability graph (i.e., defines a strict partial order ), from which one can define an optimal polynomially-computable static reuse of memory locations.

Intuitively, this is because if x and y do not conflict then only two cases arise. Either all reads and writes of x occur before (following ) any write of y, in which case we write x y, or the converse and we write y x. This clearly defines a strict partial order, which is an orientation of the complement of the conflict graph. Furthermore, when x y, then y can be mapped safely at the same location as x, in a form of memory reuse. The full proof is as follows. Proof. Assume that, for any memory location x and for any read R x of x, there is no execution (according to ) where x is not defined (but races are possible), i.e., there always exists a write W x of x such that W x ≺ R x . Assume also that for any write W x of x, there always exists a read R x of x such that W x ≺ R x . 5 Now, consider two memory locations x and y that do not conflict, according to Eq. ( 7), and two writes W x and W y of x and y respectively. First, W x and W y are always comparable for ≺. Indeed, if W x ≺ W y and W y ≺ W x , then with R x such that W x ≺ R x , we get R x ≺ W x (as ≺ is asymmetric) and R x ≺ W y (otherwise W x ≺ W y by transitivity of ≺), and thus x and y would conflict. Now, if W , W x , and W y are such that W x ≺ W y ≺ W x , then since we consider that a value is live from its very first write to its very last read (without considering lifetime "holes"), then with R x such that W andR x ≺ W y , thus x and y conflict.

x ≺ R x , we get W x ≺ W y ≺ R x , which implies R x ≺ W x , W y ≺ W x ,
We just proved that all writes of x are before (for the partial order) all writes of y (or the converse). Assume the first (W x ≺ W y for any writes of x and y), then for any read

R x of x, R x ≺ W y . Indeed, if R x ≺ W y , then R x ≺ W x (otherwise R x ≺ W y
by transitivity). And since W y ≺ W x , the memory locations x and y would conflict.

This result has a lot of similarities with the work of Berson et al. [START_REF] Berson | URSA: A unified resource allocator for registers and functional units in VLIW architectures[END_REF] and Touati [START_REF] Ahmed | Register saturation in instruction level parallelism[END_REF]. The difference is that, instead of looking for the minimal number of memory locations sufficient for any schedule, which is shown to be NP-complete, we look for an allocation with minimal number of memory locations valid for any schedule (a possibly slightly larger number). Since the conflict graph is the complement of a perfect graph (the reuse graph), its chromatic number can be computed in polynomial time, and an allocation of same size, based on static reuse, can be defined by a maximal number of independent chains in the reuse graph. When these graphs are not given by extension but through conflicting relations, it is not clear how this can be exploited to find better memory allocations. However, the formulation of the reuse graph gives some conceptual insight on previous work based on memory reuse and occupancy vectors, as we now discuss.

Links with Previous Work

The procedures described in Sections 2 and 3 are generalizations of previous approaches to compute conflicts between memory locations (registers and array elements), a necessary step to enable memory reuse. The case of sequential codes [START_REF] Alias | Bee+Cl@k: An implementation of lattice-based array contraction in the source-to-source translator Rose[END_REF], of parallelization through multi-dimensional affine scheduling [START_REF] Feautrier | Some efficient solutions to the affine scheduling problem, part II: Multi-dimensional time[END_REF] resulting in inner parallel loops, were well-known. The fact that the sequentiality within a statement of such inner parallel loops needs to be taken into account as a particular case was a folk theorem. We do not recall such previous work here. All other situations we covered, either to derive special techniques (Section 2), or to handle more general parallelism description (Section 3), were not proved correct or even handled before. We now discuss some other related work to which our study brings some new insight.

The first and (unexpectedly) closest work is the study of Cohen and Lefevbre [START_REF] Cohen | Program Analysis and Transformation: From the Polytope Model to Formal Languages[END_REF][START_REF] Cohen | Storage mapping optimization for parallel programs[END_REF], not in the context of memory contraction (reuse) but in the context of memory expansion: find the minimal expansion needed to correct a parallelization based on flow dependences only (thus ignoring anti-dependences). It is comforting to see that, when x and y are different, the conditions for minimal memory expansion given by Eq. (5.21) in Cohen's Ph.D. thesis [START_REF] Cohen | Program Analysis and Transformation: From the Polytope Model to Formal Languages[END_REF] (Page 193) are the same, but with different arguments and setting. The additional complication in their work comes from the will to avoid expansion by exploiting some knowledge, from the sequential execution, on conditionals [START_REF] Cohen | Program Analysis and Transformation: From the Polytope Model to Formal Languages[END_REF]. This is not our case: we start directly from a given parallel specification, but revisiting their work may give good insight to represent conditionals and deal with them in a more accurate way than with the under-approximation of Eq. ( 6).

Even if it was not stated in these terms, the work by Darte and Isoard [START_REF] Darte | Exact and approximated data-reuse optimizations for tiling with parametric sizes[END_REF] on parametric tiling also uses a special partial order to under-approximate R ∀ .

To make the problem piece-wise affine, "unaligned" tiles are introduced (tiles in shifted tilings), which are, by definition, never executed with the tile corresponding to W y in Eq. [START_REF] Cilardo | Improving multibank memory access parallelism with lattice-based partitioning[END_REF]. A partial order among all tiles is then defined (T ≺ T if every point in T is executed before any point in T ) to define the conflicts. This method is much more accurate for liveness analysis than defining, as suggested in Eq. ( 6), R ∀ (a, b) iff, for all traces t, a < t b or b / ∈ t. The latter assumes that tiles in different tilings (i.e., unaligned) can execute in parallel, making all array elements conflict with each other, which is of course not satisfactory.

Finally, Theorem 1 gives new insight on the concept of occupancy vectors. An occupancy vector o for an array A is such that A[ i + o] can reuse the memory location of A[ i] for all i. Lattice-based memory allocation [START_REF] Darte | Lattice-based memory allocation[END_REF] is based on the set DS of conflicting differences, computed from the conflict graph ( d ∈ DS if d = i -j such that A[ i] and A[ j] conflicts). Occupancy vectors (or reuse vectors) give the dual view, in the complement (the reuse graph): o is such that it is never a conflicting difference, i.e., it is in the complement of DS. This duality was partly exploited in lattice-based memory allocation [START_REF] Darte | Lattice-based memory allocation[END_REF] for the design of heuristics.

It also gives new insight for the concept of universal occupancy vectors (UOV) [START_REF] Strout | Schedule-independent storage mapping for loops[END_REF], an occupancy vector valid for all possible schedules, constrained by memory dependences only. The theory developed here could be used to address this problem: what we need is the relation defined by a b if there is a dependence path from a to b, i.e., the transitive closure of dependences. The problem is that, if an over-approximation can be built in the context of Presburger arithmetic, here we need an under-approximation. In the work of UOVs [START_REF] Strout | Schedule-independent storage mapping for loops[END_REF], the problem can be solved because it is restricted to uniform dependences and assuming large-enough iteration domains. So, transitivity of dependences is obtained by addition of dependence vectors.

Similarly, QUOV (quasi UOV) [START_REF] Yuki | Memory allocations for tiled uniform dependence programs[END_REF], designed to handle occupancy vectors valid for all possible tilings of a code, makes an assumption on the dependence cone that enables to capture the transitive closure. Finally, Thies et al. [START_REF] Thies | A step towards unifying schedule and storage optimization[END_REF] proposed a method to build occupancy vectors valid for all possible one-dimensional affine schedules (AUOV). The set of all such schedules θ can be expressed with Farkas lemma. Then, imposing θ(b) < θ(a) when b depends on a through a direct dependence captures the transitivity of ≺ through the transitivity of <. However, building a true UOV (i.e., for all schedules), even for affine dependences, remains open, unless the transitive closure of dependences can be expressed.

Conclusion

We have presented extensions to liveness analysis for parallel specifications. The most generic "happens-before" relation we considered (R ∀ -Eq. 4) is not even a partial order but we may still compute conflicts. We also focused on cases when the happens-before relation is a partial order (or can be approximated as one), which arises in many parallel programming models such as OpenMP, X10, and so on.

In extending the liveness analysis, we have described several ways to compute the conflicting relation, depending on the situation. They differ in their computational complexity (e.g., number of dimensions, or of unions involved), what they can express, and if they can be used for intermediate simplifications (coalescing of unions, approximations). It is not clear yet which solution will be, in practice, the most efficient one for real programs, either programs with complex accesses or large programs involving many different accesses. Also, even if Theorem 1 states that the minimal size of an allocation can be computed when the conflict graph is described in extension, it is not clear how it can be done in a symbolic (polyhedral) way. Lower bounds can be derived by clique computations, and it is more likely that exploiting the structure of the conflict graphs for special cases, as done in Section 2, will lead to more accurate lower bounds.

Finally, we hope that the analysis presented in this paper to serve as a stepping stone to the analysis of data reuse on any parallel language. We are currently working on applying Theorem 1, which explicits the link between memory conflicts (or interferences) and memory reuse, to improve element-wise array memory allocations.

Figure 1 :

 1 Figure 1: Conflicts on jacobi-1d.

Figure 2 :

 2 Figure 2: Two software pipelines for kernel offloading, borrowed from Alias et al. [2] and Darte et al. [8] respectively.

Figure 3 :

 3 Figure 3: Sequential strategies.

  l]: i<k or (i=k and j<l) }; Preveq := { [i,j]->[k,l]: i<k or (i=k and j<=l) }; WriteBeforeT := (Prev^-1).(Sched^-1).Write; ReadAfterT := Preveq.(Sched^-1).Read; # Liveness and conflicts Live := WriteBeforeT * ReadAfterT; Conflict := (Live^-1).Live; Delta := deltas Conflict;

  l]: not (l = j) }; WriteBeforeT := (PrevEqDiff^-1).(Sched^-1).Write; ReadAfterT := PrevEqDiff.(Sched^-1).Read; WriteAtT := (Sched^-1).Write; ReadAtT := (Sched^-1).Read; # Liveness and conflicts LiveCross := WriteBeforeT * ReadAfterT; LiveEnd := WriteBeforeT * ReadAtT; LiveStart := WriteAtT * ReadAfterT; Conflict := (LiveCross^-1).(LiveEnd + LiveStart); Delta := deltas (Conflict);

  a) Liveness set. δj δi (b) Conflicting differences.

Figure 4 :

 4 Figure 4: Example with non-chordal interferences.

Figure 5 :

 5 Figure 5: Parallel strategies.

  a, b) and ¬R ∀ (b, a), there is a trace t with a < t b and the same for all traces that contain a and b. • If ¬R ∀ (a, b) and R ∀ (b, a), this is the converse situation. • If ¬R ∀ (a, b) and ¬R ∀ (b, a), a and b are parallel, i.e., there is a trace with a before b, and the converse. • If R ∀ (a, b) and R ∀ (b, a) then a and b are never executed in the same trace

RR n°8839

In a correct code, the first access is a write. Otherwise, the value is live-in from the region being analyzed, so there is an implicit earlier write to bring it to its memory location. Similarly, the last access is a read otherwise it generates dead code or the value is actually live-out, which means there is an implicit read afterwards, to save it somewhere else.RR n°8839

In back-end code optimizations, liveness is usually defined on control-flow graphs, with the notion of "program point", and live-in and live-out variables at these points. This should be kept in mind when defining liveness with "time steps". Whatever the formalization, what is important is to be able to specify when memory locations are booked or released.

Again, following previous remarks/assumptions, one can just check the cases where (S, i) is a write and (T, j) a read.RR n°8839

However, for critical sections (or the atomic construct), the analysis is more accurate with Eq. (2) than with Eq. (3).RR n°8839

This "read" can be artificially added, just to code the fact that even if Wx may be useless for a given execution, unless we do dead code elimination, it stores some value and can destroy a live value. It thus counts for conflicts.RR n°8839