Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!ukma!asuvax!noao!ncar!gatech!hubcap!fpst From: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) Newsgroups: comp.parallel Subject: Re: Name this primitive Message-ID: <1991Apr17.190457.8395@hubcap.clemson.edu> Date: 17 Apr 91 14:48:08 GMT References: <1991Apr16.164534.1530@hubcap.clemson.edu> Sender: fpst@hubcap.clemson.edu (Steve Stevenson) Reply-To: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) Organization: Snakd Island Research Inc, Toronto Lines: 69 Approved: parallel@hubcap.clemson.edu To: uunet!comp-parallel@uunet.UU.NET Apparently-To: uunet!comp-parallel In article <1991Apr16.164534.1530@hubcap.clemson.edu> Andrew Chin writes: > >multiplication, for example.) Even if an instruction is "fair," Pardon my ignorance, but what is ACO? >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. > >(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.) (1) Yes, it does have a name. If I were being pedantic, I'd stop there. In APL and J, we call it "transpose". (2) Yes, see any of many books on APL, or see Hui, Iverson, et al , "APL\?", in ACM SIGAPL Quote Quad, VOl 20, no 4, July 1990 - APL90 COnference proceedings for an early paper on J. (3) Is it practical? You betcha! Suppose you only have a reduction primitive for summing rows of an array, and want to sum the columns. Merely do "sum reduce tranpose x". Very handy. Why, I'll bet it would even have applications with non-Boolean arguments 8^}. With tongue removed from cheek: Boolean operations are an area which have made APL knock the socks off other languages in terms of performance. Having architectural support for transpose and other operations (indexing in and out of bit arrays with vector arguments comes to mind - contiguous row/column stuff -- would help) would help even more. J and older dialects of APL do not have the Flatlander prejudices that seem rife in other languages: Transpose (denoted |:) of an array x of shape (denoted $), results in an array in which the ordering of axes is reversed. That is, $x 3 4 5 (3 planes, 4 rows, 5 columns) $|:x (shape of the transpose of x) 5 4 3 If you want to transpose each plane, use "rank" (denoted ") to apply it to the rank-2 objects: $|:"2 x 3 5 4 There's a thread on this going on in comp.lang.apl. J, by the way, is a new dialect of APL, in which we have abandoned the APL character set, and adopted ASCII, and also rationalized 25 years of design, in which there some inevitable warts. So, yes, Boolean transpose is important. But, be sure that you allow for non-square arrays! I often transpose funny-shaped Boolean arrays. Robert Bernecky rbe@yrloc.ipsa.reuter.com bernecky@itrchq.itrc.on.ca Snake Island Research Inc (416) 368-6944 FAX: (416) 360-4694 18 Fifth Street, Ward's Island Toronto, Ontario M5J 2B9 Canada -- =========================== MODERATOR ============================== Steve Stevenson {steve,fpst}@hubcap.clemson.edu Department of Computer Science, comp.parallel Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell