# What is the lower bound of the following computation

I came across this question was I was browsing online

An operation OP has the following characteristics

    OP Latency = 7 clocks
OP cycles/issue =2


Derive the minimum number of cycles required for the following computation:

 X[0] OP X[1] OP X[2] OP ....... OP X[N-1]


The answer was written as 7 + 2(n-2). But I was not able to achieve the result. Can someone help me to solve this.

My try: As suggested by D.W. to check the value for n=3,4,5 For n=3, I am getting lower bound as 7+2(2)

For n=4, I am getting lower bound as 7+3(2)

For n=5, I am getting lower bound as 2(7)+4(2)

For n=6, I am getting lower bound as 2(7)+5(2)

Am I going correct. But it deviates from the answer given

• A lower bound is -23746590736972. Nov 21, 2013 at 20:07
• What have you tried? Where did you get stuck? Did you try some small examples for small values of $n$? For instance, what's the best you can do for $n=3$? for $n=4$? for $n=5$? Write out the optimal sequence for each of those. Does that suggest a generalizable pattern?
– D.W.
Nov 22, 2013 at 1:19
• @saikirangrandhi Time can't be negative, which means that the actual time taken must be more than the number I gave. Therefore, the number I gave is a lower bound, which is what you asked for. Your question was probably voted down because its vague (there are infinitely many lower bounds) and because, in the original version, you didn't give any indication of what you'd tried yourself before asking here. Nov 22, 2013 at 9:38
• @saikirangrandhi No, a lower bound is just anything that's guaranteed not to be bigger than the real quantity. If you mean to ask for the minimum number of clock cycles, you should edit the question to say that. I agree that none of the lower bounds I've given is actually the minimum number of clock cycles. Nov 22, 2013 at 10:05
• @saikirangrandhi The number of cycles cannot be negative or fractional: you understand that perfectly. What you're not understanding is the definition of a lower bound and how a lower bound on a quantity is not the same thing as the minimum value that quantity can have. For example, I do not know the height of anyone in your family but I know that the shortest person in your family is more than 10cm tall: 10cm is a lower bound, but it is not the actual height of anyone your family. Nov 22, 2013 at 10:15

Your edit changes the question. $7+2(n-2)$ is a lower bound on the number of cycles to get the answer, but it is not the minimum number of cycles. For some values of $n$, the minimum number of cycles is strictly larger than $7+2(n-2)$.

Example: if $n=3$, your goal is to compute $X[0] OP X[1] OP X[2]$.

The optimal sequence is $Y := X[0] OP X[1]; Z := Y OP X[2]$. This takes 14 cycles.

It's not 9 cycles as you wrote: the value of $Y$ is not ready until 7 cycles have finished, and the computation of $Y OP X[2]$ cannot start until the value of $Y$ is ready; once you start the computation of $Y OP X[2]$, it will take another 7 cycles to get the final answer.

Due to the dependencies, there is no way to do it in less than 14 cycles. So, 14 cycles in the minimum number of cycles possible.

What about the lower bound $7+2(n-2)$? For $n=3$, we have $7+2(n-2)=7+2\times 1=9$. So, the lower bound says 9. That is a correct bound: the minimum is indeed $\ge 9$. To say that something is a lower bound means that the true total time is always at least as large as the lower bound.

So, $7+2(n-2)=9$ is a correct lower bound on the time taken for $n=3$. It just isn't the best possible lower bound, but it is a lower bound.

For general $n$, something similar happens. $7+2(n-2)$ is a lower bound. It's not a very good lower bound, and the actual time taken will usually be larger than $7+2(n-2)$. But, it certainly won't be less -- and that's all that we mean when we say that $7+2(n-2)$ is a lower bound.

How do we know that $7+2(n-2)$ is a lower bound? Well, obviously, we have to perform at least $n-1$ OP operations. After issuing each one, we have to wait 2 cycles before issuing the next one. Also, there is a latency of 7 cycles to wait for the result from the last one. Thus, we need at least $7+2(n-2)$ cycles in total, as explained in David Richerby's answer.

That's why $7+2(n-2)$ is a valid lower bound, even though it isn't the minimum number of cycles.

The attempt in the edited question is almost there. When you issue the instruction OP, you get the answer back seven cycles later. When you issue an OP instruction, you must wait two more cycles before issuing another. You need to issue $N-1$ OP instructions, so they're issued at times $0, 2, 4, \dots, 2(N-2)$, and the last one completes seven cycles after it's issued, so we get the required answer.

Having said that, the example in the question seems bad. Since OP is an instruction taking two arguments, it's unclear what X[0] OP X[1] OP X[2] even means. If it's supposed to mean S := X[0] OP X[1]; S := S OP X[2]; then there are dependencies between the instructions. The second OP needs to know the value returned by the first, so it can't be issued until the first one has finished. If the instruction sequence is supposed to mean X[0] OP X[1]; X[1] OP X[2], then it should just be written that way, or even just OP; OP, since the arguments are irrelevant.

• can you please explain by taking a case of n=10 or higher. I didn't understand what are the corresponding operands at the issues 0,2,4......2(N-2) Nov 22, 2013 at 10:47
• @saikirangrandhi It's impossible to say what the operands are because the question you found is too vague. All we really know is that we have to issue $N-1$ OP instructions. The problem is that the expression in the question is written as if it was in a high-level language but then it asks about CPU instructions. In reality, given an expression such as X[0]+X[1]+...+X[N-1] in a language like C, the compiler would produce a sequence of LOAD and ADD instructions and would optimize their order to avoid conflicts. (E.g., it might compute X[0]+X[1] in parallel with X[2]+X[3].) Nov 22, 2013 at 11:09
• I think the minimum number of cycles internally mean getting the best optimization. Nov 22, 2013 at 11:15
• N-1 OP instructions are issued, I agree but the latency has something to do over here. Nov 22, 2013 at 11:29