Interview Question 47: Multi Clock Sync Pulse

 Design a module as shown below. The input sync_A gets asserted for some (say 3) clocks in the clk_A domain. The output sync_B should also assert for exactly the same number of clocks but in the clk_B domain.

The timing diagram is shown below.

Followup questions:

- Is fA/fB ratio fixed or it is unknown?

  .The answer to this question will decide which CDC approach you should take.

- Is the number of clocks fixed or variable or it can vary on the fly or is it configurable?

  . The answer to this question will decide which approach you take?

Interview Question 46: What is wrong with this design?

 Study the provided block diagram of a chip-level design. Each square has one clock delay associated with it. What can go wrong with this type of design? How will you fix it? How it will affect the overall design?

Interview Question 45: Find faster clock

 Design a module that finds the faster clock between two different clocks. The output A_faster_than_B asserts "1" when fA > fB and asserts "0" when fB > fA along with valid. 

Followup questions:

- How will you handle when clocks are almost the same or the same? How will you indicate the output in this case?

- How will update the design if asked to find and indicate the frequency of the clocks?

Interview Question 41: Design a circuit to calculate square of a number

Create micro-architecture and write an RTL code for a design that calculates the square of a given number.

Caveat: It should not use any multiplier operation. It does not have to be done in one clock cycle.

Interview Question 39: Compute Sum of Differences.

 You need to compute the Sum of Differences for the given two matrices.

Output = ABS(A00-B00) + .... + ABS(A03-B03) + ........+ ABS(A30-B30) + .... + ABS(A33-B33)

Each entry is an 8-bit unsigned integer. 

Questions you should be asking:

- Are all the values are available immediately or they arrive at different times?

- How many clocks are allowed to compute? (1/2/4/16)

    . The answer will change your micro-architecture of design

Hints:

- Design a simple SOD design for just two 8-bit inputs. This can become a building block.

- Give attention to the widths of outputs of each block.

- What will change if the design can not fit in the required number of clocks? (pipelining)

Interview Question 23: Micro Architect a Counters Block

Micro-architect a counters module as shown in above picture.

This module contains a large number of counters using an SRAM. This memory takes two clocks to write and three clocks to read data. You need to read counter value based on provided Address_In, perform increment or decrement operation, and then write it back to the same location to update the value. The output ports provide updated counter values.

This may seem like a simple read-modify-write operation but account for corner cases like consecutive operations performed on the same address.

Interview Question 21: Find more than two 1s in the input vector

- Try to solve the problem using 2-3 different ways with different complexities. 

The articles I read - 2: Moving data across asynchronous clock boundaries

What strategy best addresses a situation where parallel data must pass across a clock domain boundary? The traditional method is to generate a flag and to use a handshake sequence.

When the transmitter has parallel data ready for transfer,it creates a rising edge on the READY line, which in turn sets flag F telling the receiver that data is available. The receiver scans F continuously and, after finding it high, accepts the stable parallel data and then creates a rising edge of ACK, which sets flip-flop A. This resets F, which in turn resets A. This particular design makes no assumptions about any phase or frequency relationship between the transmit and receive clocks. Such generality dictates a design using a benign
controlled race condition between the two flip-flops. A reasonable loop delay can conveniently be inserted between F and the reset of A. In a less generic design, this delay might be implemented as one period of either the transmit or receive clock.

This traditional handshake requires both sides to poll the flag F. The transmitter must change parallel data only when F is low, and the receiver must accept data only when F is high. This requirement results in a safe but slow data transfer. However, speedier ways to transfer data across an asynchronous clock boundary exist.

Peter Alfke's article was originally published in Integrated System Design magazine in 2000. A pdf of this article is available here. An html version of original article is archived here.

Interview Question 16: Fibonacci number generator

Design a hardware block to generate Fibonacci numbers.
You have freedom to decide the architecture of this block.


In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence:



or, alternatively,



By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation


with seed values

Interview Question 15: Create a compact data structure

A tree based data structure of distribution of post offices in a county is shown above. 
- How do you store this data structure efficiently in a memory?
- Create a hardware (algorithm based) to find out whether given post office exists. For example if input to design is PO21 the module should traverse the data structure and show whether it exists or not.

Interview Question 14: Continuous Memory Read Writes

This is a high performance design question. Create a block which is an event counter as shown below. 

This module is implemented using a single port memory as it has large number (millions) of counters. Every clock a valid signal indicates an increment or decrement operation of a counter indicated by an address. This block also produces output of the selected counter after a fixed latency.

Essentially you need to design a “Read-Modify-Write” operation. Assume that the chosen memory requires 2 clocks to complete the write and 2 clocks to read the data. The command and address combination can happen in any sequence. For example you may receive increment/decrement command for the same address on 10 consecutive clock cycles.

Interview Question 12: Design a Garage door opener

Just like the previous question this one also deals with finding out a person's problem solving approach. 

A garage door opener is a controller which responds to multiple switch/sensor inputs and produces output for a motor to pull garage door up or down or stop in the middle. 

Half the fun in solving this design problem is in understanding the functionality and creating a list of conditions/specifications.

Interview Question 11: Design a beverage dispenser machine

This is a common question in many interviews for design positions. The expected answers vary based on experience of the person. A fresh college graduate may focus on just a state machine diagram design. An experienced person's answer will be very different. State machine diagram is just a small part of it. In any case this open ended question tests how a person thinks and approaches problem solving.

The articles I read - 1: Xcell Journals from Xilinx

I read my first XCell Journal in 1996 when I started working with XC4000 family of devices. It is a wonderful archive of tips on FPGA/CPLD devices. All the past issues since 1988 are archived online here.
http://www.xilinx.com/publications/xcellonline/ 

Click on "Past Issues" tab to access old issues. Let me know if you find any interesting read.

Interview Question 10: Trouble-Free Switching Between Clocks

How do you gracefully switch between 2 asynchronous clocks?

Here is an answer from http://www.xilinx.com/publications/archives/xcell/Xcell24.pdf

Asynchronously selecting between two clock sources can easily produce glitches that cause unreliable system behavior. The circuit diagrammed here avoids these problems.

While the SELECT input is stable (either High or Low), the two control flip-flops are in opposite states and one of the two clock inputs drives the clock output. When the SELECT input changes, there is no immediate impact until after the next falling edge of the originally-selected clock source, which also resets its control flip-flop. The Output Clock signal will then stay Low until the next falling edge of the newly-selected clock. This edge will set its control flip-flop, causing this clock to drive the Output Clock. Thus, with this circuit, any switching between clock sources is delayed by holding the output Low from the time the first clock goes Low until the time the second clock is Low.

Interview Question 9: Logic to find out number of data chunks

In one of my past back-plane design I implemented a store and forward logic. The packet data was sent in chunks of 64 bytes. One chunks consisted of 62 byte of payload and 2 bytes of data which contained other useful information like pointers to other chunks, actual payload bytes in that chunk, and QOS related tags.

Can you design a smallest logic to find out the number of chunks needed for supplied packet payload?

Interview Question 8: Sneaking CPU read/writes when continuous Memory Read Writes are going on

With the advent of increased performance needs new design challenges arise. This questions deals with one of such problem. A single port memory is continuously accessed by surrounding data plane blocks. They are accessing memory in continuous fashion. For example W-R-W-R.... There is no empty clock cycle to waste. 

The software wants to access this memory through CPU read/writes intermittently. Usually a simple mechanism using a state machine can be used to sneak in CPU access when no data plane access is going on. The problem arises when when this request gets timed out as every clock is being used by data planes accesses. How does one resolve this problem?

Changing single port memory to dual port memory seems to be easy solution but what if it is prohibitively expensive and not allowed. As design geometries are also stretched to the limit, increasing/doubling clock rate of memory is also ruled out.

How will you approach this practical problem?

Interview Question 7: Enhance the memory

You are given a one port memory block as shown below.

In past you used this memory to design an application where you performed one read or write operation every clock. Now in next generation product you are asked to double the performance. How will you accomplish it? Brainstorm multiple scenarios.
For example:

1. How will you modify the design if you could double the clock at which memory can run?

2. What if you can not double the clock speed? How will you modify the design if you are asked to use memory at the same clock period as the surrounding logic.

I know, it is difficult to take out juice from the memory like this. What if you are asked just to allow (WRx + RDy) or (RD0 + RD1) combinations only? You may also use more than one memory to solve this problem.

Interview Question 6: 7 bit 1’s counter using 1 bit adders.

You are given a basic 1 bit adder block as shown below. 

How can you use this building block to create a module which finds out number of 1s in a 7 bit input?

Interview Question 5: Design / Architect a solution

Design a solution (state machine, timing diagrams etc) for following problem.

Followup question: What are the possible error conditions. How to  find and recover from them?