VHDL Synthesis: what happens when indexed arrays are overflowed?

[apblog]

Hi Everyone,

  I frequently end up writing code that needs to distribute data either into an array of std_logic_vectors or into an
array of submodules.

  Here are some fragments:

Code: [Select]

type tx_data_type is array (0 to 13) of std_logic_vector(7 downto 0);
signal tx_data   : tx_data_type;

signal dest : std_logic_vector(3 downto 0);
signal data : std_logic_vector(7 downto 0);

... (and later, in a process)...

tx_data( to_integer(unsigned(dest) ) ) <= data;


As you can see there are only 14 elements in my destination array.  What happens if "dest" takes on a value of 14 or 15?

Does the the destination index wrap around module 14?  Does the write simply go nowhere?  Is it "undefined behaviour"?
Implementation defined?

I am only concerned about synthesis here, for Xilinx and Lattice.

Typically I am able to control the entire system such that bad indexes will never be present.  In this case I can't be sure I won't ever end up with bad index data.  I could add checks to filter out bad indexes, but I'd rather not overcomplicate my code if it's not necessary.

Also, what about the reverse situation, where I am reading data from an indexed array, and exceed the index limits?

Thanks.

[nctnico]

It would be best to consider the behaviour undefined. But in this case I think 15 will be ignored because all bits are needed to decode the range of valid numbers. It may be different if you have more unused numbers.

By the way: if a signal is a number in VHDL then don't use std_logic_vector but the signed or unsigned types! They makes life much easier because you don't have to add casts everywhere..

[daveshah]

As I understand it, this will cause an error in simulation and undefined  behaviour in hardware.

In practice (assuming the read semantics are also compatible) that array will likely get mapped to a RAM primitive of a fixed size, so elements "14" and "15" will actually exist in hardware, so a write will go into those, and that value would be read out if an out of bounds read happened later.

[rstofer]

The problem is, the best answer we can provide starts with "I guess...".  I'm not about to try to decipher the IEEE standard (if I could even find it) because the answer will be buried deep in really long and obscure words.

I don't like the idea of 'undefined' in hardware.  I have enough trouble when things are defined.  I just wouldn't allow the situation to occur.  Either I would expand the array to cover all conditions of the index or I would work over the index until it was in range.  I could use a case statement around the array access.

[NorthGuy]

Either I would expand the array to cover all conditions of the index or I would work over the index until it was in range.  I could use a case statement around the array access.

I think these 2 approaches are completely different.

For example, in Xilinx-7, the smallest RAM you can get for this array is 32x8 (which takes 4 LUTs if it's single port). If you want 14x8, you'll get 32x8 anyway. It won't harm you if you extend the array to 16 (or 32 for that matter). It actually will not change anything.

If, instead, you decide to mingle with the index and bind it to the 14-element range, you will have to use 2 extra LUTs for this, and it'll also add an extra logic level. As a result, you will end up with using 50% more LUTs and working 2 times slower. Therefore my concern here would be to avoid any index manipulations.

I try not to clutter my mind with inconsequential, so I don't know if VHDL standard requires some boundary checking here. I don't know if the tool that I use may decide to include the boundary check or not. Neither do I know if the tool may decide to implement boundary checking in the future versions. But, I know how CLBs work. Thus I would extend the array to 16 (most likely even to 32) because by doing so I solve two problems:

- I prevent possible boundary checking by the tools
- I don't need to worry about cases with odd RAM sizes, which do not exist in the real world

[SiliconWizard]

Well, it is undefined behavior. If you get an out-of-bounds access during simulation, it will get caught. But after synthesis, anything could happen.

There are several ways of dealing with that. One would be not to care at all. If you are 100% certain that it never happens, just don't do anything about it. Extensive simulation and test cases may help getting confident that it never happens. I don't really like this approach.

On the other hand, if you want to be on the safe side (because, well, we all know that anything we are too certain about in a design is bound to prove false eventually), you can do that in a few ways.

The one I would use in such situation is to keep indices as ranged integers as much as you can in your code, and do the actual conversion from an std_logic_vector (say, 'dest') at only one place (or as few places as possible). Then the conversion would include a safety guard such as:

Code: [Select]

if unsigned(dest) <= tx_data'high then
    index := to_integer(unsigned(dest));
else
    (...)
end if;
The advantage is that ranged integers can be checked in most cases statically at compile stage, and the guarding section can be written in just one place. It won't cost much and will keep things safe. You may even raise some internal flag in case the index gets out of bounds to signal some internal error. On top of that, if it can be infered at the synthesis stage that the overflow actually never happens in your design, the guarding section will get pruned during optimization.

[apblog]

The problem is, the best answer we can provide starts with "I guess...". 

I don't like the idea of 'undefined' in hardware. 

Agreed that "undefined" bad and scary.

If, instead, you decide to mingle with the index and bind it to the 14-element range, you will have to use 2 extra LUTs for this, and it'll also add an extra logic level. As a result, you will end up with using 50% more LUTs and working 2 times slower. Therefore my concern here would be to avoid any index manipulations.

Thus I would extend the array to 16 (most likely even to 32) because by doing so I solve two problems:

- I prevent possible boundary checking by the tools
- I don't need to worry about cases with odd RAM sizes, which do not exist in the real world

Yes, excessive error check can be a real problem with adding additional logic levels.  Large fanouts and excessive combinational paths are an ongoing annoyance for me, which is why I try to keep things as simple as possible.

Declaring the  array to be larger is a very reasonable approach especially if it is commented well.

But you seem to be making the assumption that the construct above will be implemented as RAM (which is a reasonable assumption based on my simple example).  It could be that multiple processes are reading multiple registers in the array simultaneously, in which case it would have to be implemented as a bunch of discrete registers.

In other cases, it's not an array of registers I am targeting but an array of submodules, in this case, serial transmitters.   It's not logical to add unused serial transmitters.  Although I suppose they would be optimized out if their outputs weren't connected...

It would be best to consider the behaviour undefined. But in this case I think 15 will be ignored because all bits are needed to decode the range of valid numbers. It may be different if you have more unused numbers.

By the way: if a signal is a number in VHDL then don't use std_logic_vector but the signed or unsigned types! They makes life much easier because you don't have to add casts everywhere..

If the selection logic is implemented as a 1 of  N decoder then the extra select lines would just be unconnected and the write would do nothing in the case of a write.   In the case of a read, you would probably get whatever was the last valid value read from the array.

Good advice on the use of unsigned.

As I understand it, this will cause an error in simulation and undefined  behaviour in hardware.

In practice (assuming the read semantics are also compatible) that array will likely get mapped to a RAM primitive of a fixed size, so elements "14" and "15" will actually exist in hardware, so a write will go into those, and that value would be read out if an out of bounds read happened later.

Again, this is assuming that it implemented as a RAM, which I think it might not be depending on the read accesses.

[SiliconWizard]

Declaring the  array to be larger is a very reasonable approach especially if it is commented well.

It is simple enough, but it could get pretty expensive. In the simple example you provided, it would just be a matter of two 8-bit registers. Probably no big deal. But the larger the index range and the more area you would waste since it's in powers of 2.

Additionally, dealing with an abnormal condition is, IMO, often better than just making sure it will do nothing. Having no effect is not necessarily safe when things go wrong. It all depends on the application of course.

[xygor]

Do not use unconstrained integers for synthesis.
Specify a range:

signal dest_int : integer range 0 to 7 13;

The result, in general, is still undefined if the index is out of range, but synthesis has a better opportunity to minimize the hardware.

In your example though, dest(3) will not even connect to the synthesized circuit that produces tx_data.

Edit: or better:
signal dest_int : integer range 0 to tx_data'length-1;
Same circuit, but the intent is clearer to a human reader.
Edit edit: Dammit, I missed that tx_data'length is not 13!

[NorthGuy]

In other cases, it's not an array of registers I am targeting but an array of submodules, in this case, serial transmitters.   It's not logical to add unused serial transmitters.  Although I suppose they would be optimized out if their outputs weren't connected...

This is different. I guess, in this case, it would synthesise to the following: each transmitter would have its own register. The register's CE would be controlled by a LUT which would write to the register when "dest" matches. Of course, in this case wrong "dest" would just do nothing.

In this case, I wouldn't push the data into the array. Rather, I would describe this situation differently. I would simply fan out "dest" to all transmitters. This way the transmitter would detect if the data is his by comparing "dest" to the transmitter's number and acting accordingly. Detecting equality is just one LUT per transmitter (or even one LUT shared between two transmitters). The transmitter then could write the data to its register by itself, or perhaps get by without register at all - IMHO this functionality belongs to the transmitter and it doesn't make much sense to create a separate central entity to fork the data to transmitters. Thus there would be no array and no doubts of whether VHDL will bite you or not.

[apblog]

Rather, I would describe this situation differently. I would simply fan out "dest" to all transmitters. This way the transmitter would detect if the data is his by comparing "dest" to the transmitter's number and acting accordingly.

That's definitely turning the problem on it's head.  I really like that solution, and embarrassed that I didn't think of it!   

Thanks!

[Scrts]

My understanding is that synthesizer (at least Quartus) will not allow an overflow of a vector. So if you pass value 10000 into 4 bits vector, then that vector will be 0000. It seems like you overflow, but it should just start from the beginning overwriting old data.

[AndyC_772]

Yes, in practice the index simply wraps, but that's only the case if the size of the array is a power of two, and the 'extra' top bit can be simply discarded during synthesis. The risk of odd behaviour is when, say, you have a 14 element array with a 4 bit index, in which case the index can take invalid values.

IMHO the best way to deal with the "what if?" scenario is to specify explicitly what you want to happen in the code.

If your checking code really cannot ever have any effect, it'll get optimised away during synthesis anyway, and if it does get used, chances are the amount of logic required is minimal.

I tend to write quite a bit of code along the lines of:

Code: [Select]

CONSTANT number_channels : INTEGER := 6; // this can be changed when the code is re-used, or brought in as a GENERIC

SIGNAL index : INTEGER RANGE 0 TO number_channels - 1;

TYPE my_type IS ARRAY (NATURAL RANGE <>) OF STD_LOGIC_VECTOR (data_width - 1 DOWNTO 0);
SIGNAL my_data : my_type (number_channels - 1 DOWNTO 0);

...

IF index >= number_channels THEN
  ...do something sane...
ELSE
  ...do something referencing my_data(index)...
END IF;


[apblog]

In this case, I wouldn't push the data into the array. Rather, I would describe this situation differently. I would simply fan out "dest" to all transmitters. This way the transmitter would detect if the data is his by comparing "dest" to the transmitter's number and acting accordingly.

Once again, great idea.  I actually sat down to implement this and then I realized a complication.

The serial transmitters take a lot of time to send a byte, there needs to be a way to stall the FIFO when it has a byte for a port that is busy.

The solution I see to this involves 2 composite (or'd) signals back from the serial transmitters.

One signal, valid_addr,  indicates that a transmitter has recognized it's address .  If no transmitter sets this high, then the distributor process should discard the byte and move on.   

If valid_addr goes is high (1 cycle later than the addr is put on the bus), then the distributor process will wait for the second composite signal, ack, to go high, meaning that the transmitter has finished transmitting it's last byte and accepted the new one.

Individual transmitter fifos don't fundamentally alter the situation.

This scheme makes the fifo run at half speed, best case.  In most situations, with few and slow transmitters, this will not be a practical issue.

I'm curious if anyone has any thoughts on my proposed method for handling busy transmitters

But for now I have gone back to my original concept of having the distributor process choose the recipient, but with range checking on the index.

[NorthGuy]

The solution I see to this involves 2 composite (or'd) signals back from the serial transmitters.

One signal should be enough. If a tramsmitter sees new data, but it's busy, it sends back the "hold" signal which holds the process until the transmitter finishes with the old byte and snatches the new data. Such "hold" signal could possibly disable CE on the entity which produces data, so that the distribution system stalls until the transmitter is done. And the distribution unit wouldn't even "see" any disruptions because you cannot see anything when your clock stops.

In the absence of the "hold" signal, you assume that either the transmitter took the data or there were no transmitter for the data.

Individual transmitter fifos don't fundamentally alter the situation.

If there are cases where two or more sequential bytes go to the same transmitter, then having shallow FIFOs on every transmitter would make things faster. Xilinx-7 has some IO related FIFOs which are used mostly by their DDR3 memory IPs, but otherwise go unused - they're rather slow and shallow, but there are lots of them.