Help: msb first bit-serial multiply reference needed

Help: msb first bit-serial multiply reference needed

Post by Shih-Lien » Fri, 10 Jun 1994 03:25:32



I am trying to find reference(s) on the design of a most-significant-bit-
first bit-serial (really parallel serial) multiplier. I was told
someone from Hughes or from TRW (or both) have published a design 10 years ago.
Could someone knowledgable help me ? Thanks in advance.

Shih-Lien

 
 
 

Help: msb first bit-serial multiply reference needed

Post by Steve Gols » Fri, 17 Jun 1994 12:19:19



> I am trying to find reference(s) on the design of a most-significant-bit-
> first bit-serial (really parallel serial) multiplier. I was told
> someone from Hughes or from TRW (or both) have published a design 10 years ago.

I don't know about them, but here's a reference that describes
MSB-first serial arithmetic elements including multipliers:

    Digit Pipelined Processors
    Mary Jane Irwin and Robert Michael Owens (Penn State Univ.)
    The Journal of Supercomputing, v1n1, 1987, pp. 61-86

In a related note, if anyone has an extra copy of Denyer and Renshaw's
book "VLSI Signal Processing: A Bit-Serial Approach" (Addison-Wesley
1985) I'd be very interested in buying it.


Consulting in: Verilog, VHDL, Synopsys, patent analysis, reverse engineering

 
 
 

Help: msb first bit-serial multiply reference needed

Post by Stanley B. Ki » Sun, 19 Jun 1994 14:23:29





>      (Shih-Lien Lu) writes:
>> I am trying to find reference(s) on the design of a most-significant-bit-
>> first bit-serial (really parallel serial) multiplier. I was told
>> someone from Hughes or from TRW (or both) have
>> published a design 10 years ago.

>I don't know about them, but here's a reference that describes
>MSB-first serial arithmetic elements including multipliers:

>    Digit Pipelined Processors
>    Mary Jane Irwin and Robert Michael Owens (Penn State Univ.)
>    The Journal of Supercomputing, v1n1, 1987, pp. 61-86

>In a related note, if anyone has an extra copy of Denyer and Renshaw's
>book "VLSI Signal Processing: A Bit-Serial Approach" (Addison-Wesley
>1985) I'd be very interested in buying it.


>Consulting in: Verilog, VHDL, Synopsys, patent analysis, reverse engineering

My master's thesis in 1982, under the direction of the late
James Robertson, was related to this topic.  I understood that
some people in Utah picked it up from there.  I don't know the
first published paper on this subject, but University of Illinois
Department of Computer Science might be able to supply copies
of technical reports and theses from the past.  Contact me if
you'd like more information.
--
Stan King


--
Stan King

 
 
 

1. Algorithm for finding set bits in a bit-string (and MSB).

Given a 'very sparse' integer having only one bit set in position 'p', this
C fragment detects 'very sparseness' and returns p. It is based on two entries
appearing in _Graphics Gems II_ (Academic Press, 1992, ed: Jim Arvo). These
describe integer operations combining bitwise-logic and arithmetic to perform
sparesness tests, bit tallying, etc. (The two entries are by Ken Shoemake and
Alan Paeth; I've forgotten their exact titles).

int sparsebit(i)
    long i;
    {
    int p;
    p = 0;
/* return position 'p' on range [0..31] of a "lone bit" integer (value 2^p) */
/* otherwise, return -1. This is "little-Endian form" as the lsb is at p=0. */
    if (i == 0) return(-1);             /* no bits set */
    if ((i & (-i)) != i) return(-1);        /* two or more bits set */
    if (i & 0xAAAAAAAA) p++;
    if (i & 0xCCCCCCCC) p += 2;
    if (i & 0xF0F0F0F0) p += 4;
    if (i & 0xFF00FF00) p += 8;
    if (i & 0xFFFF0000) p += 16;
    return(p);
    }

The msb of a sparse word having any number of bits set can be found by using:

int msbbit(i)
    long i;
    {
    long i2;
/* return the bit position of the msb as [0..31]; return -1 on arg of zero */
    while (i2 = (i & (-i)) i = i2;
    return(sparsebit(i));
    }

which removes the set bits (if any) having least weight until merely the msb
remains and then invokes the first subroutine. (This is described in the second
Gem). Note that the first algorithm has worse-case running time which grows
by log2(W) for world length W: 32-bit longs and especially 64-bit longs are big
wins. The bit-discard loop of the second procedure has run time proportional to
the number of 'on' bits in the input. Its worst-case running time occurs when
called with an input of -1 (W passes through the loop).

When non-sparse input is anticipated the stock shift-and-test or byte-table
methods give much better average-case performance. In these cases msbbit()
can be sped up significantly with simple heuristics. For instance, a prefacing

    if (i < 0) return(-1);

in msbbit() gives fast returns for 50% of its input, including the worst case.

   /Alan Paeth

2. queing mail

3. Bit Serial Multiply

4. When using visual traceroute (map) with @Home...

5. Need reference to use of "mediation and duplation" in integer multiply

6. FS: BJ-5 Bubblejet w/feeder

7. newbie needs help w/serial-to-serial...

8. Crystal Repors

9. Two serial inputs to one serial device

10. need "find first one" algorithm recently discussed here

11. Help!! Bit serial Baugh-Wooley multiplier

12. Help!!!! Bit serial Baugh-Wooley multiplier

13. : Pipelined Bit-serial multiplier with word-length delay?