Baffling interview question !!

[Bloodninja]

Hello everyone,

I have recently done an interview with an employer for Digital ASIC Designer where I did a written test.

I was doing well until I reached the last question which I couldn't understand and I don't think I've solved it correctly...

They were nice to give me a copy of the question, it goes as follows:

According to the diagram attached :

View attachment 63434

In this system, the source can generate one piece of data axy per clock cycle. A portion of this data ax goes straight into a FIFO. If the FIFO is full, the source is prevented from generating any data.

The rest of the data ay is used as an address to fetch data from the module EXT. For each request ay sent to EXT, a sequence of n words b1..n are returned. These are returned serially at the rate of one word per clock cycle with the first word b1 appearing d clock cycles after the original request was made. The EXT module is perfectly pipelined and can queue up an infinite amount of requests.

The sequence b1..n is put through a serial to parallel converter (not shown) to create a single piece of data b which is combined with one piece of data out of the FIFO to create axb.

The sink can accept one piece of data axb per clock cycle, but it cannot accept a word ax without a corresponding word b.

All interfaces in the system have flow control so need not run at maximum rate.

• What is the latency through the system?
My answer:

The latency would be (d) clock cycles + the time delay resulting from each stage.

• What is the maximum throughput of this system?
My answer:

The maximum throughput would be 2^n since the address size is from 1 to n.
• What is the minimum size that the FIFO can be to achieve this maximum throughput?
My answer:

Since the FIFO is going to produce an output as soon as an input comes in, and since it takes d clock cycles to fill the pipeline, the minimum would be d - n

• Draw a waveform diagram for the system above where n=2 and d=6 showing the output of the source, FIFO and EXT and the input to the sink.

I couldnt solve this one...

So what do you think ?

Cheers !

 

[misterT]

- For the sink to be able to accept data axb, the word b needs to be formed. This takes at least n+d clock cycles. I would say the latency is n+d. Assuming that you do not count the one clock cycle it takes to generate and receive data.
- You achieve max throughput when the source can generate data on every clock cycle. It takes n+d clock cycles to form the data b and combine it with ax from the fifo. So the min size for fifo is n+d. The max throughput would then be n+1 words every n+d clock cycles. Assuming the data ax is one word.

 

[Bloodninja]

hey misterT,

Thanks for replying, can you please tell me which subject is this question covering really so I can read more on it ?

thanks

 

[misterT]

hey misterT,

Thanks for replying, can you please tell me which subject is this question covering really so I can read more on it ?

thanks

I believe "Kahn Process Networks" could be good subject to start with. This is quite general subject in Digital Systems Design.