Saturday, July 7, 2012

Combinational Loop

Introduction

Combinational loops are logical structures that contain no synchronous feedback element. This kind of loops cause stability and reliability problemas,  as we will see in this article, violating the synchronous principles by making feedback with no register in the loop.

Why? How? is generated a combinational loop? 

Basically, a combinational loop es implemented in hardware (gates) when in the written VHDL code describing combinational logic a signal that is in the left side of an assignment statement (that is, to the left of the <= symbol) it also is on the expression at the right side of the signal assignment statement (right of <=). For example the following lines of code generate a combinational loop, as long as they are written in a combinational process or in a concurrent signal assignment statement.

1 acc <= acc + data;
2
3 Z <= Z nand B;
4
5 cnt <= cnt + 1;


However, it's important to point out that if these same statements are written in a clocked process, each of them will generate the respective sequential logic. This is due to the fact that the signal assignment statement in clocked process will generate a register for the assigned signal, therefore the loop will be registered in this case, therefore no combinational loop is generated.

Hardware

The following figure shows a diagram of a combinational loop. 



As it is shown in the figure, the combinational logic output is fedbacked to the same combinational logic without any register in the loop. The logic between the first input an the last output can be made up of one or several levels of combinational logic. It can also have different signals coming in and coming out of that piece of logic, but at least one of the signal is going back (feedback) to the first logic level, as it can be seen in the following figure.


This kind of logic circuit usually is not desired, no wanted to be implemented. Hence, when the synthesis tool finds out about this combinational loop generates a warning message. 
Here is an example of VHDL code that generate a combinational loop when is implemented.

 1 library ieee;
 2 use ieee.std_logic_1164.all;
 3
 4 entity lazo_comb is
 5   port(
 6     a: in  std_logic;
 7     z: out std_logic);
 8 end lazo_comb;
 9
10 architecture beh of lazo_comb is
11
12  signal y: std_logic;

 
13
14 begin
15     z <= y;
16
17 process(a,y)
18  begin
19     y <= y nand a;
20 end process;
21
22 end beh;


The synthesis tool, Synplify in this case, generates the following warning regarding the combinational loop. 



The warning message "found combinational loop at 'y'" means that the signal 'y' is feed-backed to the input of the combinational logic without any register in the loop. This loop can be easily found when seeing the RTL view of the synthesized system, as it can be seen in the following figure. 


Simulation

The simulation of the system (very simple system) is shown in the following figure. 



The ModelSim windows details a lot of information that deserve a detailed analysis. First of all, the top window plots the waveforms of the signals from the described system, whose main expression is in the line 24 of the middle window. The bottom window, Transcript window, generates an error message, saying that the limit of iterations has been reached at 50ns and no stable value has been gotten. In other words, this mean that the system has began to oscillated and remained oscillating. The maximum number of iterations is configurable in ModelSim (Simulate->Runtime Options); as it's in most simulators. By default this value is set to 5000. Another important piece of information can be found in the bottom of the waveform window. There you can read that the number of Delta reached 5000, which is exactly the number maximum of iterations set in the runtime options, and even after that amount of deltas the system is not stable.
Why this simple logic is oscillating? Well, analyzing the true table of the nand gate, while one of the input is stuck at '0', the output will be always '1'. That is happening in the simulation shown above. Whereas, when the input (signal a in the simulation) tries to change to '1', due to the fact the other input is still at '1' the output change to '0', then since the feedback input is '0', the output should go to '1', then that '1' is going back with the other input at '1', the output will go to '0' again, and so on...This is what is called an "unstable combinational loop". This kind of loop should NEVER be used in a real design.
Other point to bring out on this example is the importance of simulating a system. Assuming that we configured the FPGA without any simulation, based on the fact that the synthesis tool just gave us a 'warning'), we'd see an no stable output, spending some time (maybe a lot of time) trying to find out why the output is not stable. Conversely, by doing the simulation the problem would appear at first shot. 

 Code Style

In designs with a large, very large, amount of code lines it is very easy to make mistakes and generate a combinational loop with no intention (as it can be seen in the example above). So, follow certain order when writting the code, trying to maintain a certain flow of data. Also, take a close look at the warnings generated by the synthesis tool. 
In case you deliberately want to implement a combinational loop, write a detailed description of the reason for doing that, and also write a comment in the constraint file. The reason for this last point is due to the fact that the Static Timing Analysis tool (STA) usually increase the minimum period of the system when it founds a combinational loop. Therefore, in this case you should tell to the STA tool to 'ignore' that particular path. The syntax for ignoring a path is 'set_false_path' for the Quartus (Altera) software, and for the ISE (Xilinx) you should use TIG with its resepctivs syntax in both cases.