Vi presenterar en ny metod för att beräkna cache-oblivious layouter av stora maskor som förbättrar prestandan av interaktiv visualisering och geometriska bearbetningsalgoritmer. Med tanke på att maskan är åtkomlig på ett någorlunda enhetligt sätt utgår vi från att det inte finns några särskilda dataåtkomstmönster eller cacheparametrar i den minneshierarki som ingår i beräkningen. Dessutom sträcker sig vår formulering direkt till datorlayouter av multi-upplösning och avgränsande volymhierarkier av stora maskor. Vi utvecklar en enkel och praktisk cache-oblivious metriska för att uppskatta cache missar. Att beräkna en sammanhängande meshlayout är reducerat till ett kombinatoriellt optimeringsproblem. Vi designade och implementerade en out-of-core multilevel minimization algoritm och testade dess prestanda på ostrukturerade maskor som består av tiotals till hundratals miljoner trianglar. Våra layouter kan avsevärt minska antalet cache missar. Vi har observerat 2-20 gånger speedups i view-beroende rendering, kollisionsdetektering, och isocontour extraktion utan någon ändring av algoritmer eller runtime program.
Problemet med cache-oblivious mesh layouts beskrivs först i REF.
Cache-oblivious mesh layouts