.PAGE SIZE 58, 85 .NONUMBER .LEFT MARGIN 10 .RIGHT MARGIN 75 .NO FILL .NO JUSTIFY # .SKIP 5 .CENTER The RSX Multi-Tasker .SKIP .CENTER June, 1988 .SKIP .CENTER "All We Get, We Print" .SKIP .CENTER Fine Realtime Commentary Since 1975 .SKIP 6 .CENTER ^&Table of Contents\& .SKIP 2 .TAB STOPS 65 Food for Thought RSX-1 The Editor's Corner RSX-1 Mass Deception RSX-2 Submitting Articles to the Multi-Tasker RSX-3 And That's The Way Things Are RSX-3 Bulletin Board Notes RSX-4 Reading a VMS BACKUP tape via RSX RSX-4 Update on Bit Counting RSX-6 Performance Notes on Bit Counting RSX-8 .JUSTIFY .FILL .SKIP 14 .LM +5 .RM -5 Opinions expressed in the editorial section of the Multi-Tasker are those of the Editor. They do not represent the official position of the RSX SIG or that of DECUS leadership in general. .LM -5 .RM +5 .PAGE .COMMENT .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT Food for Thought .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT # .SKIP 7 .AUTOPARAGRAPH .CENTER Food for Thought .SKIP "Money is the barometer of a society's virtue. When you see that trading is done, not by consent, but by compulsion - when you see that in order to produce, you need to obtain permission from men who produce nothing - when you see that money is flowing to those who deal, not in goods, but in favors - when you see that men get richer by graft and by pull than by work, and your laws don't protect you against them, but protect them against you - when you see corruption being rewarded and honesty becoming a self-sacrifice - you may know that your society is doomed." .SKIP 2 .INDENT 30 - Ayn Rand .INDENT 30 ##Atlas Shrugged .COMMENT .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT The Editor's Corner .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT .SKIP 9 .CENTER The Editor's Corner .SKIP .CENTER Bruce R. Mitchell .SKIP Ever wonder how the Multi-Tasker gets printed? Or why it doesn't sometimes? Well, it's like this. The last week of the month, the Editor collects all the stuff sent in during the month, and anything left over from the previous month. Stuff inappropriate for the Multi-Tasker goes to other editors. Then everything remaining is collated into the boilerplate format for a Multi-Tasker issue, and test-run through Runoff. If there's less than 8 pages, no issue goes out for that month. Hint, hint. A little bird flew in the window the other day (25 April) and dropped a copy of a note from Digital on my desk. It concerned field testing for the KXJ11 and the VAX/CPR RSX coprocessor project. The note said that the long-delayed field test kit would be coming out by mid-April. The postmark was charitably past mid-April. The little bird jumped up and down on my desk, chattered angrily, dropped physical evidence of his opinion of field test on the envelope, and flew back out the window. What can I say? "Faire de la bonne cuisine demande un certain temps." (Good cooking requires time.)## Certainly we'll see it one of these days. I believe in DEC (and the tooth fairy, and the Easter bunny, and true love, and the Fast Taskbuilder.) The SIG chair has been passing good reading material along to the Editor recently. After reading a book on WWII propaganda techniques, I wondered about such massive attempts to deceive the populace of three continents. Scary stuff. It could never happen today, though. The public is too well informed ... .TEST PAGE 5 .SKIP 2 .CENTER ----- Mass Deception ----- Those of you who read "commercial" DEC newsletters, viz. all of you, are no doubt interested to see that DEC is "aggressively" targeting the mass storage market with the RA482, the RA70 and the RA90 series disk drives. Well, just how aggressive is aggressive? Digital sells the RA482 4-pack for the close range of $80,000. If memory serves me, the total capacity of the RA482 runs about 1.5 - 1.8 Gb (1,500 - 1,800 Mb). Doesn't matter much. Let's be generous, and say it's 2 GB (2,000 Mb) - easier to calculate with. The cost per Mb lies in spitting range of $40.00. On the secondary market, one can buy a brand-new Brand C 1.3 Gb (1,300 Mb) disk for about $14,000. Formatted, it should go about 1 Gb or 1,000 Mb - a convenient number. Take 2 of them, add on $2,500 for a controller, and the cost per Mb runs about $15.00. Huh! Disregarding the facts that Brand C disks occupy one quarter the space of DEC disks, that they are excellent disks made by a company whose reputation rides on good disks, that they are screaming fast, and that they're widely available ^&now\& at good discounts ... It's an interesting sidelight to note that DEC used to buy disks from Brand C. The RM02/RM03 and RM05 series - good, reliable disks - are all repackaged Brand C drives. They were successful, and priced well. You'd think that DEC would stick with something that works, so they could both make money while Brand C makes excellent disks and DEC makes excellent computers. But, y'know, DEC can do ^&anything\& better if they put their mind to it. Witness the cost-effectiveness, availability and widespread customer acceptance of the RA70s. Boy, is that ever aggressive, DEC! .TEST PAGE 5 .SKIP 2 .CENTER ----- Submitting Articles to the Multi-Tasker ----- Please submit machine readable media. RX01/2 is much preferred, as that's the only loadable medium on site. RX50 should be available by July, and 9 channel 800/1600 BPI magtape is the next easiest to get converted. But almost any medium I can't read can be converted by someone around here. All RSX volume formats are acceptable, but please don't send VMS ODS-2 format media. You can also submit articles through the RSX bulletin board system at (612) 777-7664. The Editor loves you if you do so. Kermit the file in and send it via MAIL to username MULTITASKER. Submissions which aren't machine readable may take longer to get into print. If you format your submission in RUNOFF, please set page size 58,80; left margin 10; right margin 75; and, when changing margins, use incremental changes rather than absolute. The editor thanks you for the consideration. Send your articles and other submissions to the luxurious Multi-Tasker offices: .SKIP .NO FILL .NO JUSTIFY Bruce R. Mitchell Machine Intelligence and Industrial Magic PO Box 77 Minnesota City, MN###55959 .JUSTIFY .FILL .TEST PAGE 5 .SKIP 2 .CENTER ----- And That's The Way Things Are ----- _... this month in Pool Lowbegone, where the Editor is massively confused, stuff is strewn all over the place, and his presentations for Cincinnati ^&still\& aren't ready. .COMMENT .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT Bulletin Board Notes .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT .TEST PAGE 15 .SKIP 4 .CENTER Bulletin Board Notes .SKIP The BBS management recently upgraded 2 MS11-LBs (64K word) to MS11-LDs (128K word) for a net addition of 128K words of extra main memory. That brings the memory up to 512 big K. We're caching more now and performance is improved. Software availability: RSX MAIL, Kermit, old issues of The Multi-Tasker and various other items. Free advice from everybody who logs in too. The system still needs hardware. Anything. Send us your old dead junk if nothing else. Pack up all that stuff in the spares cabinet and ship it off to the BBS management c/o your friendly Multi-Tasker editor at the address above. The BBS number: 1-612-SPR-PONG / 1-612-777-7664. This line is autobaud 110 - 1200 baud. To request an account, log in with account name ACCOUNT, password REQUEST. .COMMENT .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT Reading a VMS BACKUP tape via RSX .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT .TEST PAGE 15 .SKIP 4 .CENTER Reading a VMS BACKUP tape via RSX .SKIP 2 .CENTER Dr. Adrian Bottoms .CENTER RSX SIG Chair - UK, Ireland, and Middle East Chapter .CENTER XDT Computer Systems Ltd. ,9 The Square .CENTER Keyworth, Notts NG12 5JT, Great Britain .SKIP 2 In spite of being a long standing PDP-11/RSX shop we have recently purchased a VAXstation 2000 for playing with VMS. The VAX2000 has an RD53 and a RX33 floppy drive. I was recently faced with a problem of installing a software product under VMS for which I had the distribution only on half inch magtape written with VMS BACKUP. The software developers have structured their release kit to use the VMSINSTAL procedure. Since our half inch drive lives on the RSX machine I had no way of reading the tape directly. Although the RSX world has a utility called BRU which serves a similar function to VMS BACKUP there is no utility which will read VMS BACKUP tapes under RSX. Unwilling to be beaten by such a minor incovenience and knowing a little about BRU tape formats I did some investigation and found that BRU and BACKUP have one thing in common (apart from incompatible tape formats!): They both write tapes structured as ANSI Format D with each save set appearing as a FILE on the tape. This gave me some room to maneuver. The following sequence of actions allowed me, some 15 minutes later, to have the software product installed and running on the VAX. .SKIP 2 .lm +9 .INDENT -4 1.##On the RSX machine mount the VMS BACKUP tape under MTAACP as a Files-11 volume and do a directory listing using PIP. This showed the presence of 'files' PAKM010.A and SQZ021.A. I was interested only in PAKM010.A. Each of these 'files' corresponds to a BACKUP saveset. .SKIP .INDENT -4 2.##Initialize an RX33 floppy under RSX and mount it. Copy with PIP PAKM010.A to the floppy. Since VMS BACKUP places its savesets in [000000] when writing them to a disc, rename PAKM010.A to place it into the RSX directory [000,000]. Dismount the floppy. Carry floppy across to the VAX. (Remember, this is a Files-11 ODS-1 floppy). .SKIP .INDENT -4 3.##Load the floppy into the VAX and tell VMSINSTAL to get on with the installation. Everything goes OK for a while, then VMSINSTAL starts griping and moaning, and finally fails. .SKIP .INDENT -4 4.##Mount the ODS-1 floppy under VMS and then copy PAKM010.A to the RD53. INIT/DENS=DOUBLE $FLOPPY1 to make the floppy FILES-11 ODS-2. Copy PAKM010.A 'file' to $FLOPPY1:[000000]. .SKIP .INDENT -4 5.##Turn VMSINSTAL loose on the floppy to install PAKMANAGER. This time the product is installed without problems and passes the IVP. .SKIP .INDENT -4 6.##Pat self on back. .LM -9 There are a few other points that need mentioning. First, PIP must be installed with a very large increment to cope with the block size of the VMS BACKUP tape. Second, this procedure works only if the saveset fits on a single floppy - although a bit of programming to split a file into pieces and then re-assemble it could get around this. I was only able to achieve this bit of trickery becuse whoever designed the tape format for BRU and BACKUP decided to use ANSI format. I don't really understand why this decision was taken, but I am very grateful that it was. This structure opens up some interesting possibilities for creative BRU/BACKUP save set manipulation and recovery from problems with tape errors, since the backup sets on a tape may be manipulated with standard system utilities. .COMMENT .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT Update on Bit Counting .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT .TEST PAGE 15 .SKIP 4 .CENTER Update on Bit Counting .SKIP 2 .CENTER Richard Neitzel .CENTER 312 Laveta Pass .CENTER Golden, CO###80401 .SKIP 2 Recently I sent in a brief Macro routine to count the number of bits set in a word. Yes, it didn't work and I admit I headspaced the example - I suppose you never forget that BIT does not change the destination. However, a new algorithm that is faster in most cases is presented here, and this one does work! And for you quibblers, it handles the zero case, but my quibble is that you should test for zero before the call to avoid the overhead of a subroutine call. (Editor's note: I disagree here; let the subroutine check and return 0. Saves unnecessary repetition of code in the mainline.) This algorithm relies on a form of parallel addition, adding first one, then two, then three and finally four bit pairs to determine the number of set bits. The code is a bit longer then the earlier algorithm, but since it executes once instead of looping, it is faster for cases where several bits are set. Based on testing, this is faster at about 4 bits set. The earlier form is much faster for 1-2 bits and about the same for 3-4 bits. In the 11-16 bit range the new algorithm is almost two times faster. The following examples are in Macro-11 and C. The Macro routine gives examples of both the Fortran (delineated by {}) and DECUS C (delineated by []) calling conventions. C code is also shown but Fortran users wishing to code directly in Fortran are left to adapt the algorithm on their own. .SKIP 2 .NO FILL .NO JUSTIFY .SBTTL BITCNT Count Bits in a Word .GLOBL BITCNT # Fortran call: Call BITCNT (WORD, COUNT) # C call: count = bitcnt(word); # # BITCNT: {MOV @2(R5), R0 ; Get word to test. } [MOV SP, R0 ; Grab stack frame MOV R1, -(SP) ; Push R1 on stack MOV 2(R0), R0 ; Get word to test. ] # BEQ DONE ; If zero, don't bother # MOV R0, R1 ; Copy it into R1 BIC _#125252, R1 ; Clear every odd bit ASR R0 ; Shift right BIC _#125252, R0 ; Clear odd bits again ADD R1, R0 ; Now add 1 bit pairs # MOV R0, R1 ; Copy result into R1 BIC _#146314, R1 ; Clear alt. 2 bit pairs ASH _#-2, R0 ; Shift right 2 bits BIC _#146314, R0 ; Clear again ADD R1, R0 ; Add 2 bit pairs # MOV R0, R1 ; Copy result into R1 BIC _#377, R1 ; Clear low byte BIC _#177400, R0 ; Clear high byte SWAB R1 ; Swap bytes ADD R1, R0 ; Add 3 bit pairs # MOV R0, R1 ; Copy result into R1 BIC _#177760, R0 ; Save only lower 4 bits ASH _#-4, R1 ; Shift right 4 bits ADD R1, R0 ; Add 4 bit pairs # DONE: {MOV R0, @4(R5) ; Done, return result. } [MOV (SP)+, R1 ; Done, restore R1. ] # RETURN ; Return to the caller .JUSTIFY .FILL .SKIP Here is the same bit couting routine coded in DECUS C: .SKIP 2 .NO FILL .NO JUSTIFY int bitcnt(word) int word; { register int j,k; # if (word == 0) return(0); # j = word; # k = j _& 0x5555; j >>= 1; j _&= 0x5555; j += k; # k = j _& 0x3333; j >>= 2; j _&= 0x3333; j += k; # k = j _& 0377; j _&= 0177400; j = swabi(j); j += k; # k = j _& 0xf; j >>= 4; j += k; # return(j); } # .JUSTIFY .FILL .SKIP If you code in DECUS C, you can avoid the overhead of the function call and eliminate three lines of code by modifying the assembler output. Replace the push of the integer on the stack with "SWAB variable", and take out the subroutine call and the two lines after it that return the swapped value. It's not a lot, but sometimes every little bit helps. .COMMENT .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT Performance Notes on Bit Counting .COMMENT +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .COMMENT .TEST PAGE 15 .SKIP 4 .CENTER Performance Notes on Bit Counting .SKIP 2 .CENTER Bruce R. Mitchell .CENTER Machine Intelligence and Industrial Magic .CENTER PO Box 77 .CENTER Minnesota City, MN###55959 .SKIP 2 As Multi-Tasker editor I look at a lot of code. You only see what I consider to be the best of it in these pages. The bit-counting routine above is an interesting problem - one I was sure I could do better with. For amusement, I coded the "classical" shift and count routine and a nibble-counting table-lookup routine to see what the relative performance was of each as opposed to Neitzel's bit pair method. Here is the classical shift and count routine used for the in the performance test: .SKIP 2 .NO FILL .NO JUSTIFY BITCNT: CLR R2 ; Zero the result MOV @2(R5), R0 ; Load argument into R0 BEQ 20$ ; If zero, exit now # MOV _#16., R1 ; We shift 16 times # 10$: BIT _#1, R0 ; Bottom bit set? BEQ 11$ ; If not, don't increment # INC R2 ; Increment result # 11$: ASR R0 ; Bump down next bit SOB R1, 10$ ; And loop for next bit # MOV R2, @4(R5) ; Return the result # 20$: RETURN ; Return to the caller .JUSTIFY .FILL .SKIP And here is a routine which looks up the number of bits set in the current lowest nibble in a table. I got the idea for this from the CRC-16 code used in RSX DECnet. Note that it can be made to go even faster by processing bytes rather than nibbles and making BITTBL 256 entries in size (viz, 2**8 rather than 2**4). Then no looping is necessary, just a SWAB and BIC. I was too lazy to figure out the values for the byte table. .SKIP 2 .NO FILL .NO JUSTIFY BITTBL: .WORD 0, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 # BITCNT: CLR @4(R5) ; Zero the result MOV @2(R5), R0 ; Load argument into R0 BEQ 20$ ; If zero, exit now # MOV _#4, R1 ; We shift 4 times # 10$: MOV R0, R2 ; Copy value into R2 BIC _#177760, R2 ; Leave only bottom nibble ASL R2 ; For word offset ADD BITTBL(R2), @4(R5) ; Add bit count to result ASH _#-4, R0 ; Shift down next nibble SOB R1, 10$ ; And loop for next nibble # 20$: RETURN ; Return to the caller .JUSTIFY .FILL .SKIP The test program was run on an unloaded PDP-11/34A without cache, running RSX-11M-Plus V1.0 Update A. The results are thus indicative of the true performance of these routines. For classical shift and count, 65K test iterations: 12.3 seconds. For nibble counting, 65K test iterations: 7.4 seconds. For Neitzel's bit pair algorithm, 65K test iterations: 4.6 seconds. Some ya win, some ya lose.