Vi härleder snäva gränser på cache missar för utvärdering av explicita stencil operatörer på strukturerade nät. Vår nedre gräns är baserad på den isoperimetriska egenskapen hos den diskreta oktaedern. Vår övre gräns är baserad på ett bra förhållande mellan yta och volym av en parallellepiped som spänns av en reducerad bas av interferens lattice av ett rutnät. Mätningar visar att vår algoritm normalt minskar antalet cache missar med en faktor på tre, i förhållande till en kompilator optimerad kod. Vi visar att stencil beräkningar på rutnät vars interferens lattice har en kort vektor funktion onormalt högt antal cache missar. Vi kallar sådana rutnät ogynnsamma och föreslår att undvika dessa i beräkningar genom lämplig stoppning. Genom direkta mätningar på en MIPS R10000-processor visar vi ett bra samband mellan onormalt högt antal cachemissar och ogynnsamma tredimensionella rutnät.
Vissa snäva nedre och övre gränser för beräkning av lokala operatörer med fast radie på strukturerade rutnät erhölls i REF, där en tiling med en reducerad grundläggande parallellepiped av interferens lattice användes för att minska cache missar.
Efficient cache use for stencil operations on structured discretization grids
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}