Forum Discussion

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

A sorter design issue

I want to design a sorter, which is used to allocate the new coming data to its proper loacation after comparing with all data inside the sorter. My algorithm is as below(pls check attachment:dengchang.jpg):

1. Compare the new data with all data inside the sorter (implemenmted with registers, just like data buffers).

2. Place the new data to proper position after comparing.

3. Shift all data behind the new data positon one step, and there is one data shifted out of the sorter.

There is negative setup slack issue after compilation. Each path between the new data and every regitser of the sorter has this timing issue. As the attached file:timing issue.jpg.

4 Replies

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

    Unroll the Data Path. That's the interesting part. Your constraint looks correct, there's minimal clock skew, just too much logic or route on the data path.

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

    Hi Rysc:

    Yes, there is a too long "if elsif". So the tool sythnsesize it to many mux. The "if elsif"'s lenth is desided by the sorter's depth. However, i must need the sorter's depth not short than 30.
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    --- Quote Start ---

    Hi Rysc:

    Yes, there is a too long "if elsif". So the tool sythnsesize it to many mux. The "if elsif"'s lenth is desided by the sorter's depth. However, i must need the sorter's depth not short than 30.

    --- Quote End --- 

    
process(clkin,reset)
begin
    if reset='0' then
       sorter_empty <= '1';dum_push <= '0';dum_cnt <= (others => '0');
       reg1_sort <= (others => '0');reg2_sort <= (others => '0');reg3_sort <= (others => '0');reg4_sort <= (others => '0');
       reg5_sort <= (others => '0');reg6_sort <= (others => '0');reg7_sort <= (others => '0');reg8_sort <= (others => '0');reg9_sort <= (others => '0');
       reg10_sort <= (others => '0');reg11_sort <= (others => '0');reg12_sort <= (others => '0');reg13_sort <= (others => '0');reg14_sort <= (others => '0');
       reg15_sort <= (others => '0');reg16_sort <= (others => '0');reg17_sort <= (others => '0');reg18_sort <= (others => '0');reg19_sort <= (others => '0');
       reg20_sort <= (others => '0');reg21_sort <= (others => '0');reg22_sort <= (others => '0');reg23_sort <= (others => '0');reg24_sort <= (others => '0');
       reg25_sort <= (others => '0');reg26_sort <= (others => '0');reg27_sort <= (others => '0');reg28_sort <= (others => '0');reg29_sort <= (others => '0');
       reg30_sort <= (others => '0');reg31_sort <= (others => '0');reg32_sort <= (others => '0');reg33_sort <= (others => '0');
    elsif clkin'event and clkin='1' then
       if d_valid='1' then
          dum_cnt <= (others => '0');
          if sorter_empty='1' then
             reg1_sort <= reg0_sort;
             sorter_empty <= '0';
          else--sorter_empty=0
             if reg0_sort(46 downto 0)<reg32_sort(46 downto 0) then
                reg33_sort <= reg0_sort;                
             elsif reg0_sort(46 downto 0)<reg31_sort(46 downto 0) then
                reg32_sort <= reg0_sort;reg33_sort <= reg32_sort;
             elsif reg0_sort(46 downto 0)<reg30_sort(46 downto 0) then
                reg31_sort <= reg0_sort;reg32_sort <= reg31_sort;reg33_sort <= reg32_sort;
             elsif reg0_sort(46 downto 0)<reg29_sort(46 downto 0) then
                reg30_sort <= reg0_sort;
                reg31_sort <= reg30_sort;reg32_sort <= reg31_sort;reg33_sort <= reg32_sort;
             elsif reg0_sort(46 downto 0)<reg28_sort(46 downto 0) then
                reg29_sort <= reg0_sort;reg30_sort <= reg29_sort;
                reg31_sort <= reg30_sort;reg32_sort <= reg31_sort;reg33_sort <= reg32_sort;
             elsif reg0_sort(46 downto 0)<reg27_sort(46 downto 0) then
                reg28_sort <= reg0_sort;reg29_sort <= reg28_sort;reg30_sort <= reg29_sort;
                reg31_sort <= reg30_sort;reg32_sort <= reg31_sort;reg33_sort <= reg32_sort;
             elsif reg0_sort(46 downto 0)<reg26_sort(46 downto 0) then
                reg27_sort <= reg0_sort;reg28_sort <= reg27_sort;reg29_sort <= reg28_sort;
                reg30_sort <= reg29_sort;reg31_sort <= reg30_sort;reg32_sort <= reg31_sort;reg33_sort <= reg32_sort;
             elsif reg0_sort(46 downto 0)<reg25_sort(46 downto 0) then
.........
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    14 years ago

    The problem is that you try to accomplish all the algorithm in one clock cycle. If you know that you won't have a valid data on each clock cycle, you can try and divide your code in two or more blocks and only execute one of the blocks on each clock cycle.

    If you can have new data on each cycle, then you will need to use pipelining and will need a major rewrite of the code. A way to do this would be to "propagate" an incoming data through your registers, pushing it one level on each clock cycle until it reaches the correct place, and then propagate the existing data, pushing the values one level down on each clock cycle. I'm not sure what I'm laying is very clear. If you don't see what I mean, tell me and I'll do a schematic of what I'm thinking.