|
| Home | People | Curriculum | Projects | Resources | Media |
Time skewing is an optimization that can be used to optimize certain
regular scientific codes (including stencils and a variety of other
calculations) for machines in which the processor vastly outperforms
the memory system.
The overhead is small enough to make it useful as a cache optimization
on machines as slow as the 200MHz Pentium system used to generate the
timing graph shown here.
Note that this graph shows the total run time for a constant number of
floating point operations,
so variations in timing are due to loop overhead
(at the left side of the graph)
and memory system delays
(at the right side - don't miss the week-long run using virtual memory
shown at the top right).
We believe this is the first locality optimization suitable for use
for both caches and "out-of-core" data sets,
Time Skewing in its most general form makes extensive use of Pugh & Rosser's iteration space slicing, but for simple cases it can be viewed as a combination of loop skewing and tiling with a new form of data transformation. Loop skewing has generally been overlooked in other work on compile-time optimization for locality (such as that by McKinley, Carr, and Tseng), largely due to the fact that empirical studies by Wolf and Lam found that it was not useful in practice. A noteable exception to this trend is the work by Song and Li on loop transformation (and recently, with Xu, and Wang, on memory reduction).
For the most complete description of time skewing, see pages 181-221 of the June 2002 issue of the International Journal of Parallel Programming. Rutgers DCS TR 449 records a preliminary version of this paper. Earlier work by Dave and John on defining time skewing and extending it to work on more realistic codes are also available as Rutgers Computer Science Department Tech. Reports.
Dave developed a version of the time skewing transformation for multiprocessors, which was presented in a poster session at LCPC '99 and a full paper at IPDPS '00. An earlier version of the IPDPS paper is available as Rutgers DCS TR 388.
Jaime and Tina presented a poster session at SC'97.
Tina has extended the code generation system in the Omega Library to perform automatic code generation involving memory mapping as well as iteration space remapping. We have written a short article (gzipped) describing this system, which was presented at MASPLAS '98. The source code for the examples in Figures 3, 4, 5, and 6 is available here. You can also get a gnuzipped tar file of the source or a gnuzipped linux executable. We had to patch Version 1.10 of the Omega Library to make this work (diffs). These have been integrated into the current version of the library.
People involved with Time Skewing (listed alphabetically):
|
|
