Design LCM single-purpose processor

The design uses the additive LCM method: keep two running multiples, X (of a) and Y (of b), and repeatedly add to the smaller one until they become equal. That common value is the LCM. (Inputs a and b are positive integers.)

Algorithm

 LCM(a, b):
   X = a; Y = b
   while (X != Y):
       if (X < Y) X = X + a
       else       Y = Y + b
   output X

Example a = 4, b = 6: (X, Y) = (4,6) -> (8,6) -> (8,12) -> (12,12). LCM = 12.

FSMD

Datapath (only)

  a -> [A]        [B] <- b
        |  X+A      |  Y+B
        v           v
  +--> [adder]   [adder] <--+
  |       |          |      |
  |   mux(a,X+A)  mux(b,Y+B)
  |       v          v      |
  +----- [X]        [Y] ----+
          |  \      /  |
          |   [comparator]--> eq, lt  (to controller)
          v
        out = X

Components: registers A, B, X, Y (X and Y are 16 bits, since the LCM of two 8-bit numbers can need up to 16 bits), two adders (or one shared adder with a mux), two 2:1 multiplexers (load the input or the add result), one comparator giving eq (X = Y) and lt (X < Y), and an output buffer. Control inputs to the datapath: loadA/B, X_sel, X_ld, Y_sel, Y_ld, out_en.

Controller (FSM)

Inputs: start, eq, lt. Outputs: X_ld, Y_ld, selects, done. Five states, 3-bit state register.

 start, status flags --> +-------------+   +-----------+
 (from datapath)         | Next-state  |-->| State     |
                         | logic       |   | register  |
                         +------^------+   +-----+-----+
                                |   current state |
                                +-----------------+
                                                  v
                                           +-------------+
                                           | Output logic|--> control
                                           +-------------+    signals