Problem $3$ :

The inner loop of a linear$-$equation solver executes the following operation:

${\displaystyle \underset{i+1}{\overset{?}{}}}$:$={\displaystyle \underset{i}{\overset{?}{}}}-ap(i)+bq(i)$

Suppose that $a,b,$ are constants and $p(i),q(i)$ are array variables preloaded in Memory. All these data

items can be streamed from Memory into an arithmetic pipeline, with one cycle delay between accesses to

each data item, to avoid computation bottlenecks. We assume integer pipeline stages operating on integer

data types. The objective is to perform $N$ iterations, $i=1,2,$dots,$N$ of the above operation and to produce

the final sum in minimal time.

a$.$ Design the block diagram and functional behavior of a three$-$function pipeline whose operations are

Multiply, Add, and Subtract. Find the collision vectors for controlling the system and find the fastest

possible cycle for the sequence of operations $,+,$ and $-,$ when operating on independent operands.

Here, this does not account for the interlocking necessary to make sure that the value of sum used

as an input is derived from the most recent value of sum used as an output. This means Memory

Read and Write are considered functionally separate in their interactions with the pipe.

b$.$ Now consider the maximum speed attainable when the input to the Adder is interlocked $($meaning

Registered$)$ to the output of the Subtractor. What is this maximum speed in your design? Note, a

separate register is needed to achieve this task.

c$.$ If we want to produce one update of sum per cycle on the average, how can we modify the pipeline to

achieve this rate? Show a pipeline architecture that achieves this rate and describe how you propose

to control the pipeline. Discuss the timing issues without the actual hardware implementation.