Re: PDP-8: count number of set bits in a word
A general discussion of population count: https://stackoverflow.com/questions/8590432/when-to-use-parallel-counting-mit-hakmem-for-bitcount-when-memory-is-an-issue
Re: PDP-8: count number of set bits in a word
At 08:49 PM 5/04/2019 +, you wrote: >Hi Kyle, > >hat's a really interesting problem, and the government (NSA) wanted this badly >and done FAST. > >they asked Seymour Cray to create a specific instruction for this and they >called it 'population count' > >Anybody know the why and how it is useful? > >I am deep in matrix math books and 'classification algorithms' in statistics >math, looking into electronics reliability WCCA, so this is an interesting >topic. > >Randy If we're considering hardware solutions, then the best way is to build a simple I/O device, with a writeable latch for the data word, fed as address into some nonvolatile memory like a big EPROM or flash, the output of which can be read via a port. Fill the NV memory with the required lookup table (derived by some code written in anything. BASIC for lols.) So the required code is just one write and one read. See the size chart: https://en.wikipedia.org/wiki/EPROM The biggest EPROM made was ST M27C322, 32 Mbit, 2Mx16. 21 Address bits, 16 data bits, 80nS access time. http://pdf.datasheetcatalog.com/datasheet/stmicroelectronics/6184.pdf Wasteful though, since the result only needs 5 bits. For an 8 bit result, 27C4001, 512K x 8 bit, 19 Address bits. http://www-inst.eecs.berkeley.edu/~cs150/fa02/docs/M27C4001.pdf If the argument is only a 16bit word, then use a 27512. 64K x 8 bit Guy
Re: PDP-8: count number of set bits in a word
> On Apr 5, 2019, at 4:49 PM, Randy Dawson via cctalk > wrote: > > Hi Kyle, > > hat's a really interesting problem, and the government (NSA) wanted this > badly and done FAST. > > they asked Seymour Cray to create a specific instruction for this and they > called it 'population count' > > Anybody know the why and how it is useful? > > I am deep in matrix math books and 'classification algorithms' in statistics > math, looking into electronics reliability WCCA, so this is an interesting > topic. I don't know how it was used in crypto, but I know of another application: the PLATO system uses it for fuzzy matches of text input. The idea is to split the strings (user input and expected input) into tokens, then xor each token and do a population count on that. "close" is defined as count < some threshold. There may be more encoding in there, i.e., it's not necessarily an xor of the straight text, but that's the basic idea. The implementation matches the "lookup table" technique, but with a fair amount of hardware thrown at it. The 60-bit word is split into 15 4-bit pieces. Each 4-bit piece is run through a logic block to generate a 3 bit count, then those counts are summed by a tree of adders to yield the final 6 bit result. It's pretty compact, about 60 modules (where each module has about 30-50 transistors on it) and takes 800 ns (8 cycles, it's a 10 MHz machine) for the whole instruction, the actual count process is about half that. paul
Re: PDP-8: count number of set bits in a word
Hi Kyle, hat's a really interesting problem, and the government (NSA) wanted this badly and done FAST. they asked Seymour Cray to create a specific instruction for this and they called it 'population count' Anybody know the why and how it is useful? I am deep in matrix math books and 'classification algorithms' in statistics math, looking into electronics reliability WCCA, so this is an interesting topic. Randy From: cctalk on behalf of Vincent Slyngstad via cctalk Sent: Friday, April 5, 2019 12:08 PM To: Kyle Owen; General Discussion: On-Topic and Off-Topic Posts Subject: Re: PDP-8: count number of set bits in a word From: Kyle Owen via cctalk: Friday, April 05, 2019 8:59 AM > Just wondering if anyone has come up with a fast way to count the number of > 1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the > word through the link or sign bit, incrementing a count based on the value > of the link or sign. That's probably the shortest, but not the fastest. (I get 13 words.) You could use RTL and check two bits at a time, for a probably-faster version. (That one is 32 words with the loop unrolled.) > With a small lookup table, you can reduce the total number of loops by > counting multiple groups of bits at a time, but this of course comes with > the cost of using more memory. Any other suggestions? I know a hack to clear a single bit at a time. Here's my first attempt (14 words): / / Return the number of bits that were set in AC. CBITS, .-. DCA CBMASK / Save the value DCA CBCNT / No bits yet CBLP, TAD CBMASK / Get bits, or bits-1 AND CBMASK / Likely clear bottom bit SNA / Last one? JMP CBRET ISZ CBCNT/ One more bit DCA CBMASK / New mask CMA / Complement bottom bit JMP CBLP / ...and go again CBRET, TAD CBCNT / Get result JMP I CBITS / ...and return CBMASK, .-. CBCNT, .-. $ The run time is related to the number of bits set, and independent of their position. It feels like we did this a year or two ago? Or maybe in the PiDP group? Vince
Re: PDP-8: count number of set bits in a word
From: Kyle Owen via cctalk: Friday, April 05, 2019 8:59 AM Just wondering if anyone has come up with a fast way to count the number of 1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the word through the link or sign bit, incrementing a count based on the value of the link or sign. That's probably the shortest, but not the fastest. (I get 13 words.) You could use RTL and check two bits at a time, for a probably-faster version. (That one is 32 words with the loop unrolled.) With a small lookup table, you can reduce the total number of loops by counting multiple groups of bits at a time, but this of course comes with the cost of using more memory. Any other suggestions? I know a hack to clear a single bit at a time. Here's my first attempt (14 words): / / Return the number of bits that were set in AC. CBITS, .-. DCA CBMASK / Save the value DCA CBCNT / No bits yet CBLP, TAD CBMASK / Get bits, or bits-1 AND CBMASK / Likely clear bottom bit SNA / Last one? JMP CBRET ISZ CBCNT / One more bit DCA CBMASK / New mask CMA / Complement bottom bit JMP CBLP/ ...and go again CBRET, TAD CBCNT / Get result JMP I CBITS / ...and return CBMASK, .-. CBCNT, .-. $ The run time is related to the number of bits set, and independent of their position. It feels like we did this a year or two ago? Or maybe in the PiDP group? Vince
Re: PDP-8: count number of set bits in a word
I suppose you could test each nybble for zero, then equate a 16-element LUT on nybbles not zero? -- Anders Nelson +1 (517) 775-6129 www.erogear.com On Fri, Apr 5, 2019 at 11:59 AM Kyle Owen via cctalk wrote: > Just wondering if anyone has come up with a fast way to count the number of > 1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the > word through the link or sign bit, incrementing a count based on the value > of the link or sign. > > With a small lookup table, you can reduce the total number of loops by > counting multiple groups of bits at a time, but this of course comes with > the cost of using more memory. Any other suggestions? > > Much appreciated, > > Kyle >
PDP-8: count number of set bits in a word
Just wondering if anyone has come up with a fast way to count the number of 1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the word through the link or sign bit, incrementing a count based on the value of the link or sign. With a small lookup table, you can reduce the total number of loops by counting multiple groups of bits at a time, but this of course comes with the cost of using more memory. Any other suggestions? Much appreciated, Kyle
