0
\$\begingroup\$

I have an issue with a module I use for rotation of a vector. I have two operations one uses 2 rotLeft modules and the other uses 2 rotRights. Originally I had occupied Slices overmapping issues which led me to combine the modules which helped a lot however now I am having issues with timing constraints in Xilinx, which results in incorrect output when programmed to an FPGA dev board. I've realized the issue is the rotation modules, when commenting out the four rotation modules port map the designs max speed is around 111Mhz and when in use 1.66Mhz, when only 2 are used it is around 44Mhz max which is fine since operating is 25Mhz. Their are 4 rotation modules in use; however, only 2 are needed at a time, depending on if a button is pressed on the board or not. I attempted to turn two off at a time by switching the with/select clause with a process gaurd and a case statement; however, I end up with LUT Overmapped issues (158%, usually 71%).

Does anyone have any advice for dealing with timing constraints and overmapping issues in Xilinx, or a way to improve the below module?

LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;

ENTITY rotLeft IS
    PORT (
    din     : IN STD_LOGIC_VECTOR(31 DOWNTO 0);  -- Input to be rotated
    amnt    : IN STD_LOGIC_VECTOR(4 DOWNTO 0);   --Amount to Rotate by
    dout    : OUT STD_LOGIC_VECTOR(31 DOWNTO 0) -- Rotated Input
     );
END rotLeft;

ARCHITECTURE rtl OF rotLeft IS
    SIGNAL rot  : STD_LOGIC_VECTOR(31 DOWNTO 0);
BEGIN
    WITH amnt SELECT -- din <<< amnt
        rot<= 
            din(30 DOWNTO 0) & din(31)           WHEN "00001", --01
            din(29 DOWNTO 0) & din(31 DOWNTO 30) WHEN "00010", --02
            din(28 DOWNTO 0) & din(31 DOWNTO 29) WHEN "00011", --03
            din(27 DOWNTO 0) & din(31 DOWNTO 28) WHEN "00100", --04
            din(26 DOWNTO 0) & din(31 DOWNTO 27) WHEN "00101", --05
            din(25 DOWNTO 0) & din(31 DOWNTO 26) WHEN "00110", --06
            din(24 DOWNTO 0) & din(31 DOWNTO 25) WHEN "00111", --07
            din(23 DOWNTO 0) & din(31 DOWNTO 24) WHEN "01000", --08
            din(22 DOWNTO 0) & din(31 DOWNTO 23) WHEN "01001", --09
            din(21 DOWNTO 0) & din(31 DOWNTO 22) WHEN "01010", --10
            din(20 DOWNTO 0) & din(31 DOWNTO 21) WHEN "01011", --11
            din(19 DOWNTO 0) & din(31 DOWNTO 20) WHEN "01100", --12
            din(18 DOWNTO 0) & din(31 DOWNTO 19) WHEN "01101", --13
            din(17 DOWNTO 0) & din(31 DOWNTO 18) WHEN "01110", --14
            din(16 DOWNTO 0) & din(31 DOWNTO 17) WHEN "01111", --15
            din(15 DOWNTO 0) & din(31 DOWNTO 16) WHEN "10000", --16
            din(14 DOWNTO 0) & din(31 DOWNTO 15) WHEN "10001", --17
            din(13 DOWNTO 0) & din(31 DOWNTO 14) WHEN "10010", --18
            din(12 DOWNTO 0) & din(31 DOWNTO 13) WHEN "10011", --19
            din(11 DOWNTO 0) & din(31 DOWNTO 12) WHEN "10100", --20
            din(10 DOWNTO 0) & din(31 DOWNTO 11) WHEN "10101", --21
            din(09 DOWNTO 0) & din(31 DOWNTO 10) WHEN "10110", --22
            din(08 DOWNTO 0) & din(31 DOWNTO 09) WHEN "10111", --23
            din(07 DOWNTO 0) & din(31 DOWNTO 08) WHEN "11000", --24
            din(06 DOWNTO 0) & din(31 DOWNTO 07) WHEN "11001", --25
            din(05 DOWNTO 0) & din(31 DOWNTO 06) WHEN "11010", --26
            din(04 DOWNTO 0) & din(31 DOWNTO 05) WHEN "11011", --27
            din(03 DOWNTO 0) & din(31 DOWNTO 04) WHEN "11100", --28
            din(02 DOWNTO 0) & din(31 DOWNTO 03) WHEN "11101", --29  
            din(01 DOWNTO 0) & din(31 DOWNTO 02) WHEN "11110", --30
            din(0)           & din(31 DOWNTO 01) WHEN "11111", --31
            din                                  WHEN OTHERS;

        dout <= rot;
END rtl;

EDIT: This is the code for the encryption/decryption https://gist.github.com/anonymous/cd91224afa3192cd2cf2

\$\endgroup\$
  • \$\begingroup\$ What fpga generation are you using? What is your critical path from the timing report? That rotation should be fine by itself if you pipeline properly. \$\endgroup\$ – Jonathan Drolet Apr 6 '15 at 17:03
  • \$\begingroup\$ Spartan 3E, 415ns after using SmartExplorer, It is for an encryption type module, and I implemented both encryption and decryption on the same board. \$\endgroup\$ – kdgwill Apr 6 '15 at 17:47
  • \$\begingroup\$ Can you give the critical path, not just its length. \$\endgroup\$ – Jonathan Drolet Apr 6 '15 at 17:58
  • \$\begingroup\$ I actually thought that was the critical path. I was unsure so i generated a Post Place & Route Timing Analysis gist.github.com/anonymous/1b5bcb6aa3b06251d66d \$\endgroup\$ – kdgwill Apr 6 '15 at 18:12
  • \$\begingroup\$ Also if it helps the design is to be implemented on a Basys2 board \$\endgroup\$ – kdgwill Apr 6 '15 at 18:34
3
\$\begingroup\$

From the timing report you attached, the critical path has 378 levels of logic in it. I can't emphasize enough how much 378 levels is, from the project I'm working on (video compression), my critical path is only 8 levels deep.

This is part of your problem, not only the propagation delays are enormous from going trough so many LUTs, ISE has a lot of problem routing the design in an efficient way. You need to add registers to pipeline your design, it is much easier to route a pipelined design and you will get faster speed and smaller area. Beside, registers are virtually free in FPGAs.

For instance, your rotLeft entity should have registered inputs and outputs, and it will then easily run at 100MHz, even in a spartan-3E. In my design, I always register my output, and assumes the inputs are registered (since they come from the output of another module).

Another part of your problem is these combinational loops that ISE report. Those are likely to change or even disappear once you redesign to add pipeline registers, but you shouldn't even try a bitstream with these in it.

\$\endgroup\$
  • \$\begingroup\$ So it is more beneficial to use process guards and additional buffer signals for each signal in I/O? This is the code for the encryption/decryption gist.github.com/anonymous/cd91224afa3192cd2cf2 \$\endgroup\$ – kdgwill Apr 6 '15 at 18:45
  • \$\begingroup\$ Yes, the complexity for the design tool is exponential with logic depth (I don't know the actual relationship, but you get the idea). It is much better to divide a 95 ns operation into 10 10ns operations. Looking at your code, there is no reason why most signals wouldn't be registered, it will change the control logic though. \$\endgroup\$ – Jonathan Drolet Apr 6 '15 at 19:00
  • \$\begingroup\$ Is it better to break up the with/select statements which repurpose the register depending on if the module is in encryption or decryption mode such as "WITH enc SELECT a_round <= din(63 DOWNTO 32) + skey(0) WHEN '0',--A = A + S[0] a_reg - skey(0) WHEN OTHERS; --A = A - S[0]" Into say 3 separate statement one for the encryption=addition, the other for decryption=subtraction and the third a with select statement ie "WITH enc SELECT a_round <= enc_data WHEN '0',--A = A + S[0] dec_data WHEN OTHERS; --A = A - S[0]"other than that from my limited experience think everything register \$\endgroup\$ – kdgwill Apr 6 '15 at 20:19
  • \$\begingroup\$ In this case, you have a 32-bits mux (din/a_reg) followed by an adder-subtractor (s[0]). I definitely expect a 32 bits adder-subtractor to be registered. If I'm looking for high performances, I would also register the result of the mux. \$\endgroup\$ – Jonathan Drolet Apr 6 '15 at 20:36
2
\$\begingroup\$

The right/left rotate operator is simply a mux tree, so the real reasons for this could be unrelated to the ror/rol:

  • you may be connecting the modules in a wrong or partially recursive way, with not enough registers to cut combinational paths. If you are using a modern FPGA, there's no way such a mux tree could hinder frequency so much if it is properly connected to the rest of the design.
  • you may have no registers at all in the design, not even for inputs and outputs. This could easily result in very slow paths.
  • your device may be too full, making it very hard for placement & routing to converge to a good solution.

It may also be none of the things I suggested. You should definitely check warnings in synthesis and P&R and perhaps also check that the synthesized netlist is the same as what you would expect.

\$\endgroup\$
  • 1
    \$\begingroup\$ Missing signals from sensitivity list is the main reason why implementation doesn't match simulation. Fix your sensitivity lists and simulate again. \$\endgroup\$ – Jonathan Drolet Apr 6 '15 at 18:06
  • 1
    \$\begingroup\$ I suggest you carefully check the way you connected those modules and/or investigate the combinational loop path in ISE. The LUTs in an FPGA are not meant to be used in feedback loops and that's the reason for your huge timing problems. \$\endgroup\$ – Francesco Conti Apr 6 '15 at 18:06
  • 2
    \$\begingroup\$ 1) of course, your "correct" results need a feedback path so if you simply cut it with flops it will be synthesizable but produce wrong results. Your logic is simply faulty and you should change that not inside the ror/rol modules but on the upper level of hierarchy, I.e where you instantiate them. 2) 9ns is no increase of the critical path with respect to the version where you had no ror/rol modules. Tclk=9ns means fclk=111 MHz. This is yet another proof that that combinational loop is responsible for your poor timing. But again, you must solve this by removing it - it is logically wrong. \$\endgroup\$ – Francesco Conti Apr 6 '15 at 19:50
  • 1
    \$\begingroup\$ A suggestion coming from experience: don't even bother synthesizing until you get a correct behavior in simulation. In any case, the warnings indicate that b_round_enc is never used / is always 0. This indicates a probable logic error (but you already know this, if this doesn't work in simulation). \$\endgroup\$ – Francesco Conti Apr 6 '15 at 21:44
  • 1
    \$\begingroup\$ One thing I can see in a quick look at your RTL is that there's some confusion in the way you are scheduling your operations in time. For example, you still "update" a using at least in one case a_rot_left, a value that is computed combinationally using a. You must clearly rethink the way you implement the algorithm commented above. One suggestion is that RTL design is nothing like coding high level software: you must have a clear idea of the structure of your RTL even if you code it behaviorally, to avoid loops such as the one I see here. \$\endgroup\$ – Francesco Conti Apr 7 '15 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.