A strategy for array management in local memory
Identifieur interne : 000C28 ( Istex/Corpus ); précédent : 000C27; suivant : 000C29A strategy for array management in local memory
Auteurs : Christine Eisenbeis ; William Jalby ; Daniel Windheiser ; François BodinSource :
- Mathematical Programming [ 0025-5610 ] ; 1994-01-01.
English descriptors
- Teeft :
- Algorithm, Analytical model, Approximate window, Approximate windows, Approximation, Approximation window, Arbitrary point, Array, Array element, Array elements, Array management, Atomic dependence graph, Basic idea, Best solution, Block sizes, Cache, Classical knapsack problem, Code generation process, Coherence, Coherence constraints, Complex behavior, Computation, Constant shape, Convex hull, Corresponding window, Corresponding windows, Data accesses, Data dependencies, Data locality, Data locality optimization, Data transfers, Dependence graph, Dependency, Different occurrences, Distinct elements, Dominant window, Eisenbeis, Exact reference windows, Execution order, Extreme points, First case, First problem, General results, General structure, Geometric properties, Geometrical framework, Global strategy, Hyperplane, Innermost, Innermost loop, Innermost loops, Input dependence, Integer, Integer coordinates, Integer points, International conference, Iteration, Iteration space, Iteration vector, Knapsack, Knapsack problem, Large number, Last iteration, Limited size, Linear function, Linear references, Loading strategy, Local memories, Local memory, Local memory management, Local memory management strategy, Local memory size, Local memory space, Locality, Locality properties, Loop, Loop body, Loop bounds, Loop execution, Loop interchange, Loop restructuring, Loop reversal, Loop transformations, Main memory, Main memory accesses, Main result, Management problem, Management strategy, Memory locations, Memory management, Memory references, Memory space, Multiple copies, Next section, Optimization, Optimized code, Other hand, Outer loop, Outermost loops, Parallelepiped, Parallelization, Previous example, Previous section, Previous studies, Program transformation, Rational interval, Reference window, Reference windows, Referenced, Rice university, Same memory location, Second case, Section details, Simple case, Small example, Spatial locality, Special cases, Spot contention, Standard polynomial algorithms, Submodule span, Subset, Such cases, Technical report, Temporary array, Theoretical point, Time step, Time steps, Timing function, Total number, Tradeoff, Uniprocessor case, Vector form, Vector length, Vectorization, Window approximation, Window approximations, Window characterization, Window computation, Window size, Window size computation, Window sizes.
Abstract
Abstract: One major point in loop restructuring for data locality optimization is the choice and the evaluation of data locality criteria. In this paper we show how to compute approximations of window sets defined by Gannon, Jalby, and Gallivan. The window associated with an iterationi describes the “active” portion of an array: elements that have already been referenced before iterationi and that will be referenced after iterationi. Such a notion is extremely useful for data localization because it identifies the portions of arrays that are worth keeping in local memory because they are going to be referenced later. The computation of these window approximations can be performed symbolically at compile time and generates a simple geometrical shape that simplifies the management of the data transfers. This strategy allows derivation of a global strategy of data management for local memories which may be combined efficiently with various parallelization and/or vectorization optimizations. Indeed, the effects of loop transformations fit naturally into the geometrical framework we use for the calculations. The determination of window approximations is studied both from a theoretical and a computational point of view, and examples of applications are given.
Url:
DOI: 10.1007/BF01582075
Links to Exploration step
ISTEX:4BE0B51D8EED8EFB43D01F7DAD47DF902805275DLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A strategy for array management in local memory</title><author><name sortKey="Eisenbeis, Christine" sort="Eisenbeis, Christine" uniqKey="Eisenbeis C" first="Christine" last="Eisenbeis">Christine Eisenbeis</name><affiliation><mods:affiliation>INRIA Rocquencourt, 78153, Le Chesnay, France</mods:affiliation></affiliation></author><author><name sortKey="Jalby, William" sort="Jalby, William" uniqKey="Jalby W" first="William" last="Jalby">William Jalby</name><affiliation><mods:affiliation>IRISA/INRIA Rennes, Rennes, France</mods:affiliation></affiliation></author><author><name sortKey="Windheiser, Daniel" sort="Windheiser, Daniel" uniqKey="Windheiser D" first="Daniel" last="Windheiser">Daniel Windheiser</name><affiliation><mods:affiliation>IRISA/INRIA Rennes, Rennes, France</mods:affiliation></affiliation></author><author><name sortKey="Bodin, Francois" sort="Bodin, Francois" uniqKey="Bodin F" first="François" last="Bodin">François Bodin</name><affiliation><mods:affiliation>IRISA/INRIA Rennes, Rennes, France</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:4BE0B51D8EED8EFB43D01F7DAD47DF902805275D</idno><date when="1994" year="1994">1994</date><idno type="doi">10.1007/BF01582075</idno><idno type="url">https://api.istex.fr/ark:/67375/1BB-8LHSZTFV-1/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000C28</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000C28</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A strategy for array management in local memory</title><author><name sortKey="Eisenbeis, Christine" sort="Eisenbeis, Christine" uniqKey="Eisenbeis C" first="Christine" last="Eisenbeis">Christine Eisenbeis</name><affiliation><mods:affiliation>INRIA Rocquencourt, 78153, Le Chesnay, France</mods:affiliation></affiliation></author><author><name sortKey="Jalby, William" sort="Jalby, William" uniqKey="Jalby W" first="William" last="Jalby">William Jalby</name><affiliation><mods:affiliation>IRISA/INRIA Rennes, Rennes, France</mods:affiliation></affiliation></author><author><name sortKey="Windheiser, Daniel" sort="Windheiser, Daniel" uniqKey="Windheiser D" first="Daniel" last="Windheiser">Daniel Windheiser</name><affiliation><mods:affiliation>IRISA/INRIA Rennes, Rennes, France</mods:affiliation></affiliation></author><author><name sortKey="Bodin, Francois" sort="Bodin, Francois" uniqKey="Bodin F" first="François" last="Bodin">François Bodin</name><affiliation><mods:affiliation>IRISA/INRIA Rennes, Rennes, France</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Mathematical Programming</title><title level="j" type="abbrev">Mathematical Programming</title><idno type="ISSN">0025-5610</idno><idno type="eISSN">1436-4646</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Berlin/Heidelberg</pubPlace><date type="published" when="1994-01-01">1994-01-01</date><biblScope unit="volume">63</biblScope><biblScope unit="issue">1-3</biblScope><biblScope unit="page" from="331">331</biblScope><biblScope unit="page" to="370">370</biblScope></imprint><idno type="ISSN">0025-5610</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0025-5610</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Analytical model</term><term>Approximate window</term><term>Approximate windows</term><term>Approximation</term><term>Approximation window</term><term>Arbitrary point</term><term>Array</term><term>Array element</term><term>Array elements</term><term>Array management</term><term>Atomic dependence graph</term><term>Basic idea</term><term>Best solution</term><term>Block sizes</term><term>Cache</term><term>Classical knapsack problem</term><term>Code generation process</term><term>Coherence</term><term>Coherence constraints</term><term>Complex behavior</term><term>Computation</term><term>Constant shape</term><term>Convex hull</term><term>Corresponding window</term><term>Corresponding windows</term><term>Data accesses</term><term>Data dependencies</term><term>Data locality</term><term>Data locality optimization</term><term>Data transfers</term><term>Dependence graph</term><term>Dependency</term><term>Different occurrences</term><term>Distinct elements</term><term>Dominant window</term><term>Eisenbeis</term><term>Exact reference windows</term><term>Execution order</term><term>Extreme points</term><term>First case</term><term>First problem</term><term>General results</term><term>General structure</term><term>Geometric properties</term><term>Geometrical framework</term><term>Global strategy</term><term>Hyperplane</term><term>Innermost</term><term>Innermost loop</term><term>Innermost loops</term><term>Input dependence</term><term>Integer</term><term>Integer coordinates</term><term>Integer points</term><term>International conference</term><term>Iteration</term><term>Iteration space</term><term>Iteration vector</term><term>Knapsack</term><term>Knapsack problem</term><term>Large number</term><term>Last iteration</term><term>Limited size</term><term>Linear function</term><term>Linear references</term><term>Loading strategy</term><term>Local memories</term><term>Local memory</term><term>Local memory management</term><term>Local memory management strategy</term><term>Local memory size</term><term>Local memory space</term><term>Locality</term><term>Locality properties</term><term>Loop</term><term>Loop body</term><term>Loop bounds</term><term>Loop execution</term><term>Loop interchange</term><term>Loop restructuring</term><term>Loop reversal</term><term>Loop transformations</term><term>Main memory</term><term>Main memory accesses</term><term>Main result</term><term>Management problem</term><term>Management strategy</term><term>Memory locations</term><term>Memory management</term><term>Memory references</term><term>Memory space</term><term>Multiple copies</term><term>Next section</term><term>Optimization</term><term>Optimized code</term><term>Other hand</term><term>Outer loop</term><term>Outermost loops</term><term>Parallelepiped</term><term>Parallelization</term><term>Previous example</term><term>Previous section</term><term>Previous studies</term><term>Program transformation</term><term>Rational interval</term><term>Reference window</term><term>Reference windows</term><term>Referenced</term><term>Rice university</term><term>Same memory location</term><term>Second case</term><term>Section details</term><term>Simple case</term><term>Small example</term><term>Spatial locality</term><term>Special cases</term><term>Spot contention</term><term>Standard polynomial algorithms</term><term>Submodule span</term><term>Subset</term><term>Such cases</term><term>Technical report</term><term>Temporary array</term><term>Theoretical point</term><term>Time step</term><term>Time steps</term><term>Timing function</term><term>Total number</term><term>Tradeoff</term><term>Uniprocessor case</term><term>Vector form</term><term>Vector length</term><term>Vectorization</term><term>Window approximation</term><term>Window approximations</term><term>Window characterization</term><term>Window computation</term><term>Window size</term><term>Window size computation</term><term>Window sizes</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: One major point in loop restructuring for data locality optimization is the choice and the evaluation of data locality criteria. In this paper we show how to compute approximations of window sets defined by Gannon, Jalby, and Gallivan. The window associated with an iterationi describes the “active” portion of an array: elements that have already been referenced before iterationi and that will be referenced after iterationi. Such a notion is extremely useful for data localization because it identifies the portions of arrays that are worth keeping in local memory because they are going to be referenced later. The computation of these window approximations can be performed symbolically at compile time and generates a simple geometrical shape that simplifies the management of the data transfers. This strategy allows derivation of a global strategy of data management for local memories which may be combined efficiently with various parallelization and/or vectorization optimizations. Indeed, the effects of loop transformations fit naturally into the geometrical framework we use for the calculations. The determination of window approximations is studied both from a theoretical and a computational point of view, and examples of applications are given.</div></front></TEI><istex><corpusName>springer-journals</corpusName><keywords><teeft><json:string>local memory</json:string><json:string>eisenbeis</json:string><json:string>iteration</json:string><json:string>reference window</json:string><json:string>array management</json:string><json:string>data locality</json:string><json:string>referenced</json:string><json:string>parallelepiped</json:string><json:string>approximate window</json:string><json:string>approximate windows</json:string><json:string>dominant window</json:string><json:string>tradeoff</json:string><json:string>parallelization</json:string><json:string>subset</json:string><json:string>hyperplane</json:string><json:string>iteration space</json:string><json:string>previous section</json:string><json:string>vectorization</json:string><json:string>timing function</json:string><json:string>innermost loop</json:string><json:string>array elements</json:string><json:string>knapsack</json:string><json:string>loop transformations</json:string><json:string>main memory</json:string><json:string>loop interchange</json:string><json:string>optimization</json:string><json:string>window approximations</json:string><json:string>knapsack problem</json:string><json:string>algorithm</json:string><json:string>locality</json:string><json:string>general results</json:string><json:string>loop bounds</json:string><json:string>local memory space</json:string><json:string>integer coordinates</json:string><json:string>memory references</json:string><json:string>innermost</json:string><json:string>coherence</json:string><json:string>cache</json:string><json:string>loop reversal</json:string><json:string>window size</json:string><json:string>local memory management</json:string><json:string>block sizes</json:string><json:string>local memories</json:string><json:string>reference windows</json:string><json:string>time step</json:string><json:string>iteration vector</json:string><json:string>data locality optimization</json:string><json:string>same memory location</json:string><json:string>loop body</json:string><json:string>array</json:string><json:string>dependency</json:string><json:string>outer loop</json:string><json:string>corresponding window</json:string><json:string>distinct elements</json:string><json:string>uniprocessor case</json:string><json:string>vector length</json:string><json:string>local memory size</json:string><json:string>extreme points</json:string><json:string>linear function</json:string><json:string>global strategy</json:string><json:string>last iteration</json:string><json:string>input dependence</json:string><json:string>loop execution</json:string><json:string>temporary array</json:string><json:string>time steps</json:string><json:string>first case</json:string><json:string>window sizes</json:string><json:string>local memory management strategy</json:string><json:string>window approximation</json:string><json:string>international conference</json:string><json:string>approximation</json:string><json:string>loop</json:string><json:string>computation</json:string><json:string>other hand</json:string><json:string>large number</json:string><json:string>total number</json:string><json:string>multiple copies</json:string><json:string>classical knapsack problem</json:string><json:string>atomic dependence graph</json:string><json:string>dependence graph</json:string><json:string>basic idea</json:string><json:string>standard polynomial algorithms</json:string><json:string>corresponding windows</json:string><json:string>coherence constraints</json:string><json:string>small example</json:string><json:string>such cases</json:string><json:string>memory locations</json:string><json:string>array element</json:string><json:string>locality properties</json:string><json:string>rice university</json:string><json:string>spatial locality</json:string><json:string>window characterization</json:string><json:string>data accesses</json:string><json:string>geometric properties</json:string><json:string>limited size</json:string><json:string>execution order</json:string><json:string>window size computation</json:string><json:string>submodule span</json:string><json:string>arbitrary point</json:string><json:string>special cases</json:string><json:string>convex hull</json:string><json:string>window computation</json:string><json:string>geometrical framework</json:string><json:string>first problem</json:string><json:string>main result</json:string><json:string>section details</json:string><json:string>simple case</json:string><json:string>integer points</json:string><json:string>management strategy</json:string><json:string>management problem</json:string><json:string>loading strategy</json:string><json:string>next section</json:string><json:string>best solution</json:string><json:string>different occurrences</json:string><json:string>data transfers</json:string><json:string>data dependencies</json:string><json:string>memory space</json:string><json:string>innermost loops</json:string><json:string>outermost loops</json:string><json:string>theoretical point</json:string><json:string>second case</json:string><json:string>previous example</json:string><json:string>vector form</json:string><json:string>main memory accesses</json:string><json:string>analytical model</json:string><json:string>exact reference windows</json:string><json:string>previous studies</json:string><json:string>memory management</json:string><json:string>code generation process</json:string><json:string>rational interval</json:string><json:string>loop restructuring</json:string><json:string>linear references</json:string><json:string>technical report</json:string><json:string>complex behavior</json:string><json:string>general structure</json:string><json:string>optimized code</json:string><json:string>approximation window</json:string><json:string>constant shape</json:string><json:string>program transformation</json:string><json:string>spot contention</json:string><json:string>integer</json:string></teeft></keywords><author><json:item><name>Christine Eisenbeis</name><affiliations><json:string>INRIA Rocquencourt, 78153, Le Chesnay, France</json:string></affiliations></json:item><json:item><name>William Jalby</name><affiliations><json:string>IRISA/INRIA Rennes, Rennes, France</json:string></affiliations></json:item><json:item><name>Daniel Windheiser</name><affiliations><json:string>IRISA/INRIA Rennes, Rennes, France</json:string></affiliations></json:item><json:item><name>François Bodin</name><affiliations><json:string>IRISA/INRIA Rennes, Rennes, France</json:string></affiliations></json:item></author><articleId><json:string>BF01582075</json:string><json:string>Art20</json:string></articleId><arkIstex>ark:/67375/1BB-8LHSZTFV-1</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: One major point in loop restructuring for data locality optimization is the choice and the evaluation of data locality criteria. In this paper we show how to compute approximations of window sets defined by Gannon, Jalby, and Gallivan. The window associated with an iterationi describes the “active” portion of an array: elements that have already been referenced before iterationi and that will be referenced after iterationi. Such a notion is extremely useful for data localization because it identifies the portions of arrays that are worth keeping in local memory because they are going to be referenced later. The computation of these window approximations can be performed symbolically at compile time and generates a simple geometrical shape that simplifies the management of the data transfers. This strategy allows derivation of a global strategy of data management for local memories which may be combined efficiently with various parallelization and/or vectorization optimizations. Indeed, the effects of loop transformations fit naturally into the geometrical framework we use for the calculations. The determination of window approximations is studied both from a theoretical and a computational point of view, and examples of applications are given.</abstract><qualityIndicators><score>9.28</score><pdfWordCount>13995</pdfWordCount><pdfCharCount>66741</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>40</pdfPageCount><pdfPageSize>432 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>190</abstractWordCount><abstractCharCount>1273</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>A strategy for array management in local memory</title><genre><json:string>research-article</json:string></genre><host><title>Mathematical Programming</title><language><json:string>unknown</json:string></language><publicationDate>1994</publicationDate><copyrightDate>1994</copyrightDate><issn><json:string>0025-5610</json:string></issn><eissn><json:string>1436-4646</json:string></eissn><journalId><json:string>10107</json:string></journalId><volume>63</volume><issue>1-3</issue><pages><first>331</first><last>370</last></pages><genre><json:string>journal</json:string></genre><subject><json:item><value>Mathematics of Computing</value></json:item><json:item><value>Numerical Analysis</value></json:item><json:item><value>Combinatorics</value></json:item><json:item><value>Calculus of Variations and Optimal Control</value></json:item><json:item><value>Optimization</value></json:item><json:item><value>Mathematical and Computational Physics</value></json:item><json:item><value>Mathematical Methods in Physics</value></json:item><json:item><value>Numerical and Computational Methods</value></json:item><json:item><value>Operation Research/Decision Theory</value></json:item></subject></host><namedEntities><unitex><date></date><geogName></geogName><orgName></orgName><orgName_funder></orgName_funder><orgName_provider></orgName_provider><persName></persName><placeName></placeName><ref_url></ref_url><ref_bibl></ref_bibl><bibl></bibl></unitex></namedEntities><ark><json:string>ark:/67375/1BB-8LHSZTFV-1</json:string></ark><categories><wos><json:string>1 - science</json:string><json:string>2 - operations research & management science</json:string><json:string>2 - mathematics, applied</json:string><json:string>2 - computer science, software engineering</json:string></wos><scienceMetrix><json:string>1 - applied sciences</json:string><json:string>2 - engineering</json:string><json:string>3 - operations research</json:string></scienceMetrix><scopus><json:string>1 - Physical Sciences</json:string><json:string>2 - Mathematics</json:string><json:string>3 - General Mathematics</json:string><json:string>1 - Physical Sciences</json:string><json:string>2 - Computer Science</json:string><json:string>3 - Software</json:string></scopus><inist><json:string>1 - sciences appliquees, technologies et medecines</json:string><json:string>2 - sciences exactes et technologie</json:string><json:string>3 - terre, ocean, espace</json:string><json:string>4 - geophysique externe</json:string></inist></categories><publicationDate>1994</publicationDate><copyrightDate>1994</copyrightDate><doi><json:string>10.1007/BF01582075</json:string></doi><id>4BE0B51D8EED8EFB43D01F7DAD47DF902805275D</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/1BB-8LHSZTFV-1/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/1BB-8LHSZTFV-1/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/1BB-8LHSZTFV-1/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">A strategy for array management in local memory</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher scheme="https://scientific-publisher.data.istex.fr">Springer-Verlag</publisher><pubPlace>Berlin/Heidelberg</pubPlace><availability><licence><p>The Mathematical Programming Society, Inc., 1994</p></licence><p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</p></availability><date>1991-10-14</date></publicationStmt><notesStmt><note type="research-article" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</note><note type="journal" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">A strategy for array management in local memory</title><author xml:id="author-0000" corresp="yes"><persName><forename type="first">Christine</forename><surname>Eisenbeis</surname></persName><affiliation>INRIA Rocquencourt, 78153, Le Chesnay, France</affiliation></author><author xml:id="author-0001"><persName><forename type="first">William</forename><surname>Jalby</surname></persName><affiliation>IRISA/INRIA Rennes, Rennes, France</affiliation></author><author xml:id="author-0002"><persName><forename type="first">Daniel</forename><surname>Windheiser</surname></persName><affiliation>IRISA/INRIA Rennes, Rennes, France</affiliation></author><author xml:id="author-0003"><persName><forename type="first">François</forename><surname>Bodin</surname></persName><affiliation>IRISA/INRIA Rennes, Rennes, France</affiliation></author><idno type="istex">4BE0B51D8EED8EFB43D01F7DAD47DF902805275D</idno><idno type="ark">ark:/67375/1BB-8LHSZTFV-1</idno><idno type="DOI">10.1007/BF01582075</idno><idno type="article-id">BF01582075</idno><idno type="article-id">Art20</idno></analytic><monogr><title level="j">Mathematical Programming</title><title level="j" type="abbrev">Mathematical Programming</title><idno type="pISSN">0025-5610</idno><idno type="eISSN">1436-4646</idno><idno type="journal-ID">true</idno><idno type="issue-article-count">21</idno><idno type="volume-issue-count">3</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Berlin/Heidelberg</pubPlace><date type="published" when="1994-01-01"></date><biblScope unit="volume">63</biblScope><biblScope unit="issue">1-3</biblScope><biblScope unit="page" from="331">331</biblScope><biblScope unit="page" to="370">370</biblScope></imprint></monogr></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1991-10-14</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: One major point in loop restructuring for data locality optimization is the choice and the evaluation of data locality criteria. In this paper we show how to compute approximations of window sets defined by Gannon, Jalby, and Gallivan. The window associated with an iterationi describes the “active” portion of an array: elements that have already been referenced before iterationi and that will be referenced after iterationi. Such a notion is extremely useful for data localization because it identifies the portions of arrays that are worth keeping in local memory because they are going to be referenced later. The computation of these window approximations can be performed symbolically at compile time and generates a simple geometrical shape that simplifies the management of the data transfers. This strategy allows derivation of a global strategy of data management for local memories which may be combined efficiently with various parallelization and/or vectorization optimizations. Indeed, the effects of loop transformations fit naturally into the geometrical framework we use for the calculations. The determination of window approximations is studied both from a theoretical and a computational point of view, and examples of applications are given.</p></abstract><textClass><keywords scheme="Journal Subject"><list><head>Mathematics</head><item><term>Mathematics of Computing</term></item><item><term>Numerical Analysis</term></item><item><term>Combinatorics</term></item><item><term>Calculus of Variations and Optimal Control</term></item><item><term>Optimization</term></item><item><term>Mathematical and Computational Physics</term></item><item><term>Mathematical Methods in Physics</term></item><item><term>Numerical and Computational Methods</term></item><item><term>Operation Research/Decision Theory</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1991-10-14">Created</change><change when="1994-01-01">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/1BB-8LHSZTFV-1/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-journals not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer-Verlag</PublisherName><PublisherLocation>Berlin/Heidelberg</PublisherLocation></PublisherInfo><Journal><JournalInfo JournalProductType="ArchiveJournal" NumberingStyle="Unnumbered"><JournalID>10107</JournalID><JournalPrintISSN>0025-5610</JournalPrintISSN><JournalElectronicISSN>1436-4646</JournalElectronicISSN><JournalTitle>Mathematical Programming</JournalTitle><JournalAbbreviatedTitle>Mathematical Programming</JournalAbbreviatedTitle><JournalSubjectGroup><JournalSubject Type="Primary">Mathematics</JournalSubject><JournalSubject Type="Secondary">Mathematics of Computing</JournalSubject><JournalSubject Type="Secondary">Numerical Analysis</JournalSubject><JournalSubject Type="Secondary">Combinatorics</JournalSubject><JournalSubject Type="Secondary">Calculus of Variations and Optimal Control</JournalSubject><JournalSubject Type="Secondary">Optimization</JournalSubject><JournalSubject Type="Secondary">Mathematical and Computational Physics</JournalSubject><JournalSubject Type="Secondary">Mathematical Methods in Physics</JournalSubject><JournalSubject Type="Secondary">Numerical and Computational Methods</JournalSubject><JournalSubject Type="Secondary">Operation Research/Decision Theory</JournalSubject></JournalSubjectGroup></JournalInfo><Volume><VolumeInfo VolumeType="Regular" TocLevels="0"><VolumeIDStart>63</VolumeIDStart><VolumeIDEnd>63</VolumeIDEnd><VolumeIssueCount>3</VolumeIssueCount></VolumeInfo><Issue IssueType="Combined"><IssueInfo TocLevels="0"><IssueIDStart>1</IssueIDStart><IssueIDEnd>3</IssueIDEnd><IssueArticleCount>21</IssueArticleCount><IssueHistory><CoverDate><DateString>7 January 1994</DateString><Year>1994</Year><Month>1</Month></CoverDate></IssueHistory><IssueCopyright><CopyrightHolderName>The Mathematical Programming Society, Inc.</CopyrightHolderName><CopyrightYear>1994</CopyrightYear></IssueCopyright></IssueInfo><Article ID="Art20"><ArticleInfo Language="En" ArticleType="OriginalPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ArticleID>BF01582075</ArticleID><ArticleDOI>10.1007/BF01582075</ArticleDOI><ArticleSequenceNumber>20</ArticleSequenceNumber><ArticleTitle Language="En">A strategy for array management in local memory</ArticleTitle><ArticleFirstPage>331</ArticleFirstPage><ArticleLastPage>370</ArticleLastPage><ArticleHistory><RegistrationDate><Year>2005</Year><Month>4</Month><Day>14</Day></RegistrationDate><Received><Year>1991</Year><Month>10</Month><Day>14</Day></Received><Revised><Year>1993</Year><Month>4</Month><Day>5</Day></Revised></ArticleHistory><ArticleCopyright><CopyrightHolderName>The Mathematical Programming Society, Inc.</CopyrightHolderName><CopyrightYear>1994</CopyrightYear></ArticleCopyright><ArticleGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ArticleGrants><ArticleContext><JournalID>10107</JournalID><VolumeIDStart>63</VolumeIDStart><VolumeIDEnd>63</VolumeIDEnd><IssueIDStart>1</IssueIDStart><IssueIDEnd>3</IssueIDEnd></ArticleContext></ArticleInfo><ArticleHeader><AuthorGroup><Author AffiliationIDS="Aff1" CorrespondingAffiliationID="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Christine</GivenName><FamilyName>Eisenbeis</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>William</GivenName><FamilyName>Jalby</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Daniel</GivenName><FamilyName>Windheiser</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>François</GivenName><FamilyName>Bodin</FamilyName></AuthorName></Author><Affiliation ID="Aff1"><OrgName>INRIA Rocquencourt</OrgName><OrgAddress><Postcode>78153</Postcode><City>Le Chesnay</City><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>IRISA/INRIA Rennes</OrgName><OrgAddress><City>Rennes</City><Country>France</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>One major point in loop restructuring for data locality optimization is the choice and the evaluation of data locality criteria. In this paper we show how to compute approximations of window sets defined by Gannon, Jalby, and Gallivan. The window associated with an iteration<Emphasis Type="Italic">i</Emphasis> describes the “active” portion of an array: elements that have already been referenced before iteration<Emphasis Type="Italic">i</Emphasis> and that will be referenced after iteration<Emphasis Type="Italic">i.</Emphasis> Such a notion is extremely useful for data localization because it identifies the portions of arrays that are worth keeping in local memory because they are going to be referenced later. The computation of these window approximations can be performed symbolically at compile time and generates a simple geometrical shape that simplifies the management of the data transfers. This strategy allows derivation of a global strategy of data management for local memories which may be combined efficiently with various parallelization and/or vectorization optimizations. Indeed, the effects of loop transformations fit naturally into the geometrical framework we use for the calculations.</Para><Para>The determination of window approximations is studied both from a theoretical and a computational point of view, and examples of applications are given.</Para></Abstract></ArticleHeader><NoBody></NoBody></Article></Issue></Volume></Journal></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>A strategy for array management in local memory</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>A strategy for array management in local memory</title></titleInfo><name type="personal" displayLabel="corresp"><namePart type="given">Christine</namePart><namePart type="family">Eisenbeis</namePart><affiliation>INRIA Rocquencourt, 78153, Le Chesnay, France</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">William</namePart><namePart type="family">Jalby</namePart><affiliation>IRISA/INRIA Rennes, Rennes, France</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Daniel</namePart><namePart type="family">Windheiser</namePart><affiliation>IRISA/INRIA Rennes, Rennes, France</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">François</namePart><namePart type="family">Bodin</namePart><affiliation>IRISA/INRIA Rennes, Rennes, France</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</genre><originInfo><publisher>Springer-Verlag</publisher><place><placeTerm type="text">Berlin/Heidelberg</placeTerm></place><dateCreated encoding="w3cdtf">1991-10-14</dateCreated><dateIssued encoding="w3cdtf">1994-01-01</dateIssued><copyrightDate encoding="w3cdtf">1994</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: One major point in loop restructuring for data locality optimization is the choice and the evaluation of data locality criteria. In this paper we show how to compute approximations of window sets defined by Gannon, Jalby, and Gallivan. The window associated with an iterationi describes the “active” portion of an array: elements that have already been referenced before iterationi and that will be referenced after iterationi. Such a notion is extremely useful for data localization because it identifies the portions of arrays that are worth keeping in local memory because they are going to be referenced later. The computation of these window approximations can be performed symbolically at compile time and generates a simple geometrical shape that simplifies the management of the data transfers. This strategy allows derivation of a global strategy of data management for local memories which may be combined efficiently with various parallelization and/or vectorization optimizations. Indeed, the effects of loop transformations fit naturally into the geometrical framework we use for the calculations. The determination of window approximations is studied both from a theoretical and a computational point of view, and examples of applications are given.</abstract><relatedItem type="host"><titleInfo><title>Mathematical Programming</title></titleInfo><titleInfo type="abbreviated"><title>Mathematical Programming</title></titleInfo><genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre><originInfo><publisher>Springer</publisher><dateIssued encoding="w3cdtf">1994-01-01</dateIssued><copyrightDate encoding="w3cdtf">1994</copyrightDate></originInfo><subject><genre>Mathematics</genre><topic>Mathematics of Computing</topic><topic>Numerical Analysis</topic><topic>Combinatorics</topic><topic>Calculus of Variations and Optimal Control</topic><topic>Optimization</topic><topic>Mathematical and Computational Physics</topic><topic>Mathematical Methods in Physics</topic><topic>Numerical and Computational Methods</topic><topic>Operation Research/Decision Theory</topic></subject><identifier type="ISSN">0025-5610</identifier><identifier type="eISSN">1436-4646</identifier><identifier type="JournalID">10107</identifier><identifier type="IssueArticleCount">21</identifier><identifier type="VolumeIssueCount">3</identifier><part><date>1994</date><detail type="volume"><number>63</number><caption>vol.</caption></detail><detail type="issue"><number>1-3</number><caption>no.</caption></detail><extent unit="pages"><start>331</start><end>370</end></extent></part><recordInfo><recordOrigin>The Mathematical Programming Society, Inc., 1994</recordOrigin></recordInfo></relatedItem><identifier type="istex">4BE0B51D8EED8EFB43D01F7DAD47DF902805275D</identifier><identifier type="ark">ark:/67375/1BB-8LHSZTFV-1</identifier><identifier type="DOI">10.1007/BF01582075</identifier><identifier type="ArticleID">BF01582075</identifier><identifier type="ArticleID">Art20</identifier><accessCondition type="use and reproduction" contentType="copyright">The Mathematical Programming Society, Inc., 1994</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</recordContentSource><recordOrigin>The Mathematical Programming Society, Inc., 1994</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/1BB-8LHSZTFV-1/record.json</uri></json:item></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/H2N2V1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C28 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000C28 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= H2N2V1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:4BE0B51D8EED8EFB43D01F7DAD47DF902805275D
|texte= A strategy for array management in local memory
}}
| This area was generated with Dilib version V0.6.33. |  |