Forum Discussion

Altera_Forum's avatar
Altera_Forum
Icon for Honored Contributor rankHonored Contributor
10 years ago

shift_left and shift_right for large vectors freeze Quartus

I am using Quartus 15.1.1 64 bit

I just found that shift_left and shift_right for large vectors freeze Quartus analysis and synthesis 

y <= std_logic_vector(shift_right( unsigned(x), i));

where x and y are std_logic_vector(1023 downto 0) and i is an integer range 0 to 1023

Using 512 instead of 1024 have compile time of 18 seconds, but with 1024 is more than 1 hour and seem in a forever loop..

Could anyone reproduce my problem?

Thanks

4 Replies

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    10 years ago

    Please file an SR if there's a bug. (I would also suggest adding a synthesizable HDL file rather than just a snippet, so user's don't have to do it and you're more likely to get someone to try it out)

    I think you're building a ton of 1024:1 muxes, which is going to be really large and slow(I'm sure there is common logic for a lot of it, but it's still not good).
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    10 years ago

    --- Quote Start ---

    Please file an SR if there's a bug. (I would also suggest adding a synthesizable HDL file rather than just a snippet, so user's don't have to do it and you're more likely to get someone to try it out)

    I think you're building a ton of 1024:1 muxes, which is going to be really large and slow(I'm sure there is common logic for a lot of it, but it's still not good).

    --- Quote End ---

    Quartus should implement multi-level logic with 2048:1024, 1024:512, 512:256 etc.. to get acceptable performance. I filled an SR.

    It seem that function right_shift isn't optimized to handle these large cases.

    Instantiating MUX manually with code like http://www.ece.ualberta.ca/~elliott/ee552/studentappnotes/2003_w/components/barrel_shifter/ works well and compile time is under 2 min with good performance (200 MHz on Stratix IV C2, 100 MHz on Cyclone V C8)
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    10 years ago

    --- Quote Start ---

    Quartus should implement multi-level logic with 2048:1024, 1024:512, 512:256 etc.. to get acceptable performance. I filled an SR.

    It seem that function right_shift isn't optimized to handle these large cases.

    Instantiating MUX manually with code like http://www.ece.ualberta.ca/~elliott/ee552/studentappnotes/2003_w/components/barrel_shifter/ works well and compile time is under 2 min with good performance (200 MHz on Stratix IV C2, 100 MHz on Cyclone V C8)

    --- Quote End ---

    Quartus implemented what is was told to ...

    The shift_right() function in ieee.numeric_std is rather naively 'straightforward' coded: 
    RESULT(ARG_L downto COUNT) := XARG(ARG_L-COUNT downto 0);

    This will probably expand in an exponential manner. For a 1024 shifter you will have 1024 * 1024 to 1' muxes, as Rysc hinted.

    If you want a barrel shifter, you will have to code one yourself. A 1024 barrel shifter will have 10 * 1024 * '2 to 1' muxes, which it evidently a lot less to handle by Quartus.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    10 years ago

    I tried a 765 bit shift_right:

    compilation time: 17 minutes

    fmax: 110 MHz on CycV

    There is Multiplexer Statistics report inside compilation:

    +------------------------------------------------------------------------------------------------------------------------------------------+

    ; Multiplexer Restructuring Statistics (No Restructuring Performed) ;

    +--------------------+-----------+---------------+----------------------+------------------------+------------+----------------------------+

    ; Multiplexer Inputs ; Bus Width ; Baseline Area ; Area if Restructured ; Saving if Restructured ; Registered ; Example Multiplexer Output ;

    +--------------------+-----------+---------------+----------------------+------------------------+------------+----------------------------+

    ; 4:1 ; 253 bits ; 506 LEs ; 0 LEs ; 506 LEs ; Yes ; |signed_adder|y[435]~reg0 ;

    ; 7:1 ; 3 bits ; 12 LEs ; 12 LEs ; 0 LEs ; Yes ; |signed_adder|y[253]~reg0 ;

    ; 7:1 ; 189 bits ; 756 LEs ; 756 LEs ; 0 LEs ; Yes ; |signed_adder|y[103]~reg0 ;

    ; 10:1 ; 48 bits ; 288 LEs ; 288 LEs ; 0 LEs ; Yes ; |signed_adder|y[36]~reg0 ;

    ; 13:1 ; 12 bits ; 96 LEs ; 96 LEs ; 0 LEs ; Yes ; |signed_adder|y[4]~reg0 ;

    ; 16:1 ; 4 bits ; 40 LEs ; 40 LEs ; 0 LEs ; Yes ; |signed_adder|y[3]~reg0 ;

    ; 4:1 ; 64 bits ; 128 LEs ; 128 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 64 bits ; 128 LEs ; 128 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 317 bits ; 634 LEs ; 634 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 16 bits ; 32 LEs ; 32 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 16 bits ; 32 LEs ; 32 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 653 bits ; 1306 LEs ; 1306 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 4 bits ; 8 LEs ; 8 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 4 bits ; 8 LEs ; 8 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 737 bits ; 1474 LEs ; 1474 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    ; 4:1 ; 758 bits ; 1516 LEs ; 1516 LEs ; 0 LEs ; No ; |signed_adder|ShiftRight0 ;

    +--------------------+-----------+---------------+----------------------+------------------------+------------+----------------------------+

    Quartus use multilevel mux or this report is another thing?