NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/programm/3386

Internet Message Format | 1993-01-01 | 2.8 KB

Path: sparky!uunet!spool.mu.edu!yale.edu!ira.uka.de!sbusol.rz.uni-sb.de!coli.uni-sb.de!coli-gate.coli.uni-sb.de!spackman
From: [e-mail] (Stephen Spackman)
Newsgroups: comp.programming
Subject: Re: Fast array rotation
Date: 1 Jan 1993 19:02:33 GMT
Organization: DFKI Saarbruecken GmbH, D-W 6600 Saarbruecken
Lines: 37
Message-ID: <[e-mail]>
References: <u895027.724990251@tasman> <[e-mail]>
Reply-To: [e-mail]
NNTP-Posting-Host: disco-sol.dfki.uni-sb.de
In-reply-to: Dave Dodson's message of Tue, 22 Dec 1992 15:43:38 GMT

In article <[e-mail]> Dave Dodson <[e-mail]> writes:
|In article <u895027.724990251@tasman> [e-mail] (Mark Mackey) writes:
|>
|>    I am currently writing a terrain display routine which utilises
|>a fast surface display algorithm based on scan-line processing. As
|>part of the algorith I need to rotate the raw data array. I have an
|>algorithm to do this using two 1d transforms, but in between these
|>transforms the data array needs to be transposed.
|>    Does anyone out there have any code for fast array transposition
|>on disk, minimising disk access time? Alternatively, if anyone out there
|>has ideas on how to rotate a large array (512*512 reals) efficiently
|>I would be most grateful.
|
|I assume you have the array stored on disk in row- or column-major order.
|There is a way to transpose the array by reading and writing the matrix
|twice.  For simplicity, assume you have row-major order, 4 byte reals,
|and a scratch array of length 64K bytes.  Read 65536/4/512 = 16 rows into
|the scratch array.  Write 16 x 16 square blocks onto a scratch file.  There
|will be 512/16 = 32 of them for every 16 rows.  Repeat for all rows of the
|matrix.  Now randomly read blocks 1, 33, 65, ... .  Transpose each 16 x 16
|block in memory, and write out the first 16 rows of the transposed matrix.
|Repeat with blocks 2, 34, 66, ... , 3, 35, 67, ... .

Or, under certain circumstances, you might consider doing nothing at
all. After all, it's only the indexing calculation that distinguishes
layouts; could you parameterise on it and be done? (That might entail
either multiple versions of the various operations or runtime code
generation, to get really good performance; in the latter case, be sure
you know how to explain things to any caches that might be kicking
around :-). In a sense this is no more than a generalisation of dodson's
suggestion, of course....

But hey, if by a "real" you mean a float, you've only got a meg or two
of data there. Where do disks come into it? :-).
------------------------------------------------------------------------
stephen p spackman                                       [e-mail]
------------------------------------------------------------------------