How do you understand Systolic Arrays?

Question

I'm working on a problem from the Digital Design and Computer Architecture course on Systolic arrays.

The question set up is as follows:

The following diagram is a systolic array that performs the multiplication of two 4-bit binary numbers (a and b). For example, if a=1110 and b=1011, the result of the multiplication is c=10011010:

The input to the systolic arrays is through the AND gates. The figure shows which bits of the two numbers a and b are inserted into each AND gate. However, the figure does not indicate in which cycle each input is issued. Make the folowing assumptions:

• The latency of each adder is one cycle.
• Vertical arrows propagate the sum to the next adder.
• Diagonal arrows propagate the carry to the next adder.
• Horizontal arrows propagate the output of the AND gates in each row.
• An adder adds the value of its three inputs (vertical, diagonal and horizontal inputs)
• An adder can hold a value for only one cycle.

The question is the following:

How many cycles does it take to perform one multiplication of two 4-bit binary numbers in this systolic array? Indicate 1) in which cycle each bit is inputted in the systolic array and 2) in which cycle each bit of the result is produced.

It's probably worth also pointing out that the subscripts are apparently little endian.

I've been trying to wrap my head around the order of inputs to the Systolic array, but I can't figure out how I'm supposed to think about it.

How are you supposed to think about a problem like this when a lot is happening in parallel?

Answer 1

The behavior of sequential (logic) circuits has temporal order.

Combinational (logic) circuits have no temporal order. It operates concurrently/simultaneously, and uses all logic gates at the same time.

Hence, the bits of the input numbers are loaded together at the same time, from the least significant bit (LSB) to the most significant bit (MSB).

Systolic arrays are subsystems in a datapath, and are created with combinational circuits.

They are homogeneous networks of data processing units, such as simple 1-bit adders in this case.

They matter for VLSI deep learning, since deep learning architectures have lots of repetitive steps of computation to be performed. This can be implemented with systolic arrays.

With graphics processing, or signal processing, it is harder to mathematically formulate data processing as a 2-D mesh/network that can be realized as a systolic array.

Think of it like functional programming with Erlang, or even Haskell, Scala, and OCaml. With immutable variables, it is hard/harder to model finite state machines or temporal behavior. Hence, a lot of stuff happens concurrently/simultaneously.

Hence, the common argument of using functional programming to model dataflow computing/architectures/processing. For better parallel or distributed computing, being able to model concurrent/simultaneous operations make functional programming languages, like Haskell, more amenable to modeling combinational logic circuits. We avoid using sequential circuits, which have states and need mutable variables to model, and can lead to resource contention (e.g., just like mutable variables in shared-memory parallel programming). This is the motivation of using Haskell as a platform to create Clash as an embedded domain-specific language, or hardware construction language (HCL) in this case.

Chisel HDL, which is based on Scala, and Hardcaml, which is based on OCaml, are a compromise between purely functional programming and procedural programming (also based on object-oriented programming, in these cases). Hence, they can model sequential and combinational circuits well.

Reference: What are some good books for vlsi cmos design? Or some good educational software? Or, https://cs.stackexchange.com/a/170071/115652