Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!ox-prg!prg.ox.ac.uk!chin
From: chin@prg.ox.ac.uk (Andrew Chin)
Newsgroups: comp.theory
Subject: Name this primitive
Message-ID: <1580@culhua.prg.ox.ac.uk>
Date: 16 Apr 91 15:45:18 GMT
Sender: news@prg.ox.ac.uk
Reply-To: chin@prg.ox.ac.uk (Andrew Chin)
Organization: Oxford University Computing Laboratory, UK
Lines: 28

I am working on realistic PRAM models.  The PRAM is usually defined
without specifying what basic instruction set is used.  Two criteria for
deciding whether an instruction is "fair" to use are linear (sequential)
bit complexity and membership in AC0.  (These criteria exclude
multiplication, for example.)  Even if an instruction is "fair,"
however, it is best to justify supporting it in hardware or low-level
code.

It will help me greatly if I can have a basic instruction which takes
n n-bit words and produces n n-bit words such that the first word 
consists of the highest-order bits, the second word consists of the
second-highest-order bits, etc.  The effect is that of transposing
an n-by-n 0-1-valued matrix.

Clearly this can be done with linear bit complexity and in AC0.
What I want to know is:

(1)  Does this instruction have a name?
(2)  Are there references to it in the literature?
(3)  Is it practical?  (Both research results and hunches are invited.)

______________________________________________________________________
Andrew Chin                                chin@prg.oxford.ac.uk
Oxford University Computing Laboratory
8-11 Keble Road                            +44 865 513661
Oxford  OX1 3QD                            (0865) 513661
England                                    at Texas A&M 1991-93
______________________________________________________________________