Warping data

A system for warping data, comprising:

• a warping engine that includes an output generator that generates a plurality of target coordinates x ∈ N, a mapper that that calculates source coordinates x′ ∈ N for a plurality of target coordinates x ∈ N, and an interpolator that computes interpolated data values for each x in a neighborhood of x′ from the data values of the source coordinates;
• a cache that receives requests for data values of the source coordinates from the warping engine;
• and
• a main memory that provides data values of the source coordinates to the cache when there is a cache miss for those data values,
• wherein the plurality of source data points is a hyperrectangle of size p1 × . . . × pN, p1, . . . , pN≥1, N>1, centered at x′, and
• wherein the cache comprises a plurality of lines, and each line stores a hyperrectangle of size n1 × . . . × nN of D-dimensional data points, where D, n1, . . . , nN≥1, and the cache's is fully-set-associative where each cache line can be stored in any cache location.

A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executed by the computer to perform method steps for warping data, comprising the steps of:

• providing a set of target coordinates x ∈ N;
• calculating, by a warping engine, source coordinates x′ ∈ N for the target coordinates x ∈ N;
• requesting, by the warping engine, data values for a plurality of source coordinates from a cache, wherein the plurality of source data points is a hyperrectangle of size p1 × . . . ×pN, p1, . . . , pN≥1, N>1, centered at x′;
• and
• computing, by the warping engine, interpolated data values for each x in a neighborhood of x′ from the data values of the source coordinates returned from the cache,
• wherein requesting data values from the cache comprises calculating a number of cache lines K, wherein K depends on a maximal size of the group of source coordinates and a cache line size (n1 × . . . × nN), for a current request;
• calculating a tag for each cache line;
• comparing tags of missing cache lines to missing cache lines that have already been requested and are being retrieved, and keeping tags that correspond to lines that have already been requested in a queue, wherein the physical addresses of the missing cache-lines, for those of tags that are not in the queue, are sent to the main memory.