How did multiply instructions work in the various 68ks?

Wilson 09/19/2018. 2 answers, 310 views
m68k

pndc says about the 68000:

the [...] MULU/MULS instructions are very slow, taking about 70 cycles. The exact number of cycles is data-dependent because the microcode uses an iterative algorithm.)

So, (assuming that pndc is correct and the 68000 is microcoded). What "iterative algorithm" is this? I can imagine something naive like

(let (mulu_impl (lambda (ct x y)
    (if (eq? ct 0) 
        y
        (mulu_impl (decrement ct) x (add x y))))))
(mulu (lambda (x y) (mulu_impl x x y))
(* untested; could be full of brainfarts *)

which basically counts x downward, adding the old x to y each time. But this would be naive and slow for large values of x. They probably had a better trick up their sleeves.

the comp.sys.m68k faq says about the 68060:

The chip is all hardwired - there is no microcode in it.

I find this quote rather hard to believe, since I think that if you implement something so complex without microcode you end up decreasing the clock speed to allow for signal propagation delays; I could be wrong though. But if it is the case, then my guess is that MULU/MULS now need to be implemented differently from what I did in Lisp up there.

How was the multiplier(s) implemented in the 68000 and the 68060?

2 Answers


Dr Sheldon 09/20/2018.

Although none of my databooks directly state how multiplication is done, we can infer several things from what they do say.

My copy of M68000 8-/16-/32-bit Microprocessor User's Manual shows the execution times of the MC68000 multiply instructions on page 8-4:

MULS    70(1/0)+*
MULU    70(1/0)+*

where 70 is the number of processor cycles, 1 means one read cycle, 0 means no write cycles, + means additional cycles to fetch the effective address should be added, and * means that the number 70 is the maximum number of cycles. Below this is exactly the text that @DroidW quotes in his answer.

On page 10-5 of the same databook, the execution times for the MC68010 are listed:

MULS    42(1/0)+*
MULU    40(1/0)*

Note how fewer clock cycles are needed for this processor. I'm not sure why this MULU instruction is missing the + for effective address calculation (perhaps a typo). Also, this table is missing the text that @DroidW quotes in his answer.

The MC68000 indeed uses microcode (and in some cases nanocode). The processor simply doesn't have enough combinational logic to perform a complete multiplication calculation in one cycle. Instead, it repeats some basic operations, with a loop controlled by the microcode. There are no barrel shifters, just single-bit shifts.

Let's call the multiplicand D, the multiplier R, and the product P.


To multiply unsigned numbers (MULU), we perform a long multiplication algorithm:

(1) Clear the product P = 0.

(2) Shift P one bit left.

(3) Shift D one bit left, and check the bit shifted out (the MSB). If it is zero, skip to step 5.

(4) Add R to the product P.

(5) Repeat steps 2 to 4 for each bit of D.

Because the branch in step 3 jumps ahead to step 5, it makes sense that the number of cycles will be based on 2x(number of ones in the multiplicand). This is confirmed in @DroidW's quote.

In later chips such as the 68010, we can add more logic to accomplish steps 2 to 4 in parallel. Also, instead of the branch in step 3, we can mask R with the bit from step 3, and then always add that result to P. These measures reduce the number of machine cycles.

In later processors, you can unroll the loop and use a large number of adders. It uses a lot more hardware and is harder to design, but is much faster. For example, to multiply binary numbers 1101 and 0101:

   1101  value of R
  1101   value of R
 0000    R is masked
0000     R is masked
=======
0100111

To multiply signed numbers (MULS), we use Booth's algorithm.

(1) Set P to D. An additional bit is added to the right (a new LSB), which is initialized to zero.

(2) Examine the two least significant bits of P. If 01, continue to step 3. If 10, skip to step 4. Otherwise, skip to step 5.

(3) Add R to the upper word of P. Jump to step 5.

(4) Subtract R from the upper word of P.

(5) Arithmetically shift P one bit right.

(6) Repeat steps 2 to 5 for all bits of D.

As you can see, there is more work to be done when bit patterns 01 and 10 are seen. This is confirmed by @DroidW's quote.

In advanced processors, you can also unroll this algorithm using hardware.


DroidW 09/19/2018.

Not an answer, but my contribution (found here, credit to witbrock@cs.cmu.edu):

DIVS,DIVU - The divide algorithm used by the MC68000 provides less
        than 10% difference between the best and the worst case
        timings.    
MULS,MULU - The multiply algorithm requires 38+2n clocks where
        n is defined as:        
    MULU: n = the number of ones in the <ea>         
    MULS: n = concatanate the <ea> with a zero as the LSB;
          n is the resultant number of 10 or 01 patterns
          in the 17-bit source; i.e., worst case happens
          when the source is $5555

Kind regards.


HighResolutionMusic.com - Download Hi-Res Songs

1 Ariana Grande

7 Rings flac

Ariana Grande. 2019. Writer: Ariana Grande;Richard Rodgers;TBHits;Njomza;Michael "Mikey" Foster;Kaydence;Tayla Parx;Scootie;Oscar Hammerstein II;Victoria Monét.
2 Alan Walker

Lily flac

Alan Walker. 2018. Writer: Alan Walker;Lars Kristian Rosness;Magnus Bertelsen;K-391;Didrik Handlykken;Marcus Arnbekk.
3 Alec Benjamin

Let Me Down Slowly flac

Alec Benjamin. 2019. Writer: Alec Benjamin;Sir Nolan;Michael Pollack.
4 Alan Walker

Lost Control flac

Alan Walker. 2018. Writer: Alan Walker;Thomas Troelsen;Mood Melodies;Sorana;Fredrik Borch Olsen;Magnus "Magnify" Martinsen.
5 Skylar Grey

Everything I Need flac

Skylar Grey. 2018. Writer: Elliott Taylor;Rupert Gregson-Williams;Skylar Grey.
6 Post Malone

Sunflower flac

Post Malone. 2018. Writer: Carl Rosen;Louis Bell;Billy Walsh;Carter Lang;Swae Lee;Post Malone.
7 Westlife

Hello My Love flac

Westlife. 2019. Writer: Steve Mac;Ed Sheeran.
8 Alan Walker

Different World flac

Alan Walker. 2018. Writer: Shy Nodi;Alan Walker;Fredrik Borch Olsen;James Njie;Marcus Arnbekk;Gunnar Greve Pettersen;K-391;Corsak;Shy Martin;Magnus Bertelsen.
9 Sam Smith

Fire On Fire flac

Sam Smith. 2018. Writer: Steve Mac;Sam Smith.
10 Conor Maynard

Way Back Home (Sam Feldt Edit) flac

Conor Maynard. 2018. Writer: Ji Hye Lee;Shaun.
11 Normani

Dancing With A Stranger flac

Normani. 2019. Writer: Mikkel S. Eriksen;Tor Hermansen;Jimmy Napes;Normani;Sam Smith.
12 Slushii

Never Let You Go flac

Slushii. 2019. Writer: Sofía Reyes;Slushii;Aviella Winder.
13 Skrillex

Face My Fears flac

Skrillex. 2019. Writer: Poo Bear;Skrillex;Utada Hikaru.
14 Alora & Senii

Love U So flac

Alora & Senii. 2019. Writer: Alora & Senii.
15 The Chainsmokers

Hope flac

The Chainsmokers. 2018. Writer: Kate Morgan;Chris Lyon;Alex Pall;Andrew Taggart.
16 Imagine Dragons

Believer flac

Imagine Dragons. 2019. Writer: Dan Reynolds;Lil Wayne;Wayne Sermon;Ben McKee;Daniel Platzman;Robin Fredriksson;Mattias Larsson;Justin Tranter.
17 Alan Walker

I Don't Wanna Go flac

Alan Walker. 2018.
18 Mike Perry

Runaway flac

Mike Perry. 2019. Writer: Andreas Wiman;Dimitri Vangelis;Richard Müller;Sasha Rangas;Stefan Van Leijsen;Mike Perry.
19 Gesaffelstein

Lost In The Fire flac

Gesaffelstein. 2019. Writer: Ahmad Balshe;Nate Donmoyer;Gesaffelstein;DaHeala;The Weeknd.
20 Hozier

Almost (Sweet Music) flac

Hozier. 2019. Writer: Hozier.

Related questions

Hot questions

Language

Popular Tags