Subversion Repositories astron_adder

-------------------------------------------------------------------------------

--

-- Copyright (C) 2009

-- ASTRON (Netherlands Institute for Radio Astronomy) <http://www.astron.nl/>

-- P.O.Box 2, 7990 AA Dwingeloo, The Netherlands

--

-- This program is free software: you can redistribute it and/or modify

-- it under the terms of the GNU General Public License as published by

-- the Free Software Foundation, either version 3 of the License, or

-- (at your option) any later version.

--

-- This program is distributed in the hope that it will be useful,

-- but WITHOUT ANY WARRANTY; without even the implied warranty of

-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

-- GNU General Public License for more details.

--

-- You should have received a copy of the GNU General Public License

-- along with this program.  If not, see <http://www.gnu.org/licenses/>.

--

-------------------------------------------------------------------------------

LIBRARY IEEE, common_pkg_lib, common_components_lib;

USE IEEE.std_logic_1164.ALL;

USE common_pkg_lib.common_pkg.ALL;

ARCHITECTURE str OF common_adder_tree IS

  -- common_add_sub pipelining

  CONSTANT c_pipeline_in  : NATURAL := 0;

  CONSTANT c_pipeline_out : NATURAL := g_pipeline;

  -- There is no need to internally work with the adder tree sum width for

  -- worst case bit growth of c_sum_w = g_dat_w+ceil_log2(g_nof_inputs),

  -- because any MSbits that are not in the output sum do not need to be kept

  -- at the internal stages either. The worst case bit growth for

  -- g_nof_inputs = 1 still becomes ceil_log2(g_nof_inputs) = 1, which can be

  -- regarded as due to an adder stage that adds 0 to the single in_dat.

  -- However it also does not cause extra logic to internally account for bit

  -- growth at every stage, because synthesis will optimize unused MSbits away

  -- when g_sum_w < c_sum_w.

  CONSTANT c_w            : NATURAL := g_dat_w;                          -- input data width

  CONSTANT c_sum_w        : NATURAL := g_dat_w+ceil_log2(g_nof_inputs);  -- adder tree sum width

  CONSTANT c_N            : NATURAL := g_nof_inputs;            -- nof inputs to the adder tree

  CONSTANT c_nof_stages   : NATURAL := ceil_log2(c_N);          -- nof stages in the adder tree

  -- Allocate c_sum_w for each field and allocate c_N fields for the input

  -- stage and use this array for all stages. Hence the stage vectors

  -- are longer than necessary and wider than necessary, but that is OK, the

  -- important thing is that they are sufficiently long.

  TYPE t_stage_arr IS ARRAY (INTEGER RANGE <>) OF STD_LOGIC_VECTOR(c_N*c_sum_w-1 DOWNTO 0);

  SIGNAL adds    : t_stage_arr(-1 TO c_nof_stages-1);

BEGIN

  -- The tabel below lists how many two port adders (+) and one port pipes (.)

  -- to match the adder latency, there are at each stage of the adder tree.

  --

  --         nof +,.   nof +,.   nof +,.   nof +,.        nof +,.

  --         stage 0   stage 1   stage 2   stage 3   -->  total

  -- N =  2    1,0       -         -         -              1

  --      3    1,1       1,0       -         -              3

  --      4    2,0       1,0       -         -              3

  --      5    2,1       1,1       1,0       -              6

  --      6    3,0       1,1       1,0       -              6

  --      7    3,1       2,0       1,0       -              7

  --      8    4,0       2,0       1,0       -              7

  --      9    4,1       2,1       1,1       1,0           11  < N + nof stages

  --     10    5,0       2,1       1,1       1,0           11

  --     11    5,1       3,0       1,1       1,0           12

  --     12    6,0       3,0       1,1       1,0           12

  --     13    6,1       3,1       2,0       1,0           14

  --

  --                                                                   input     output   nof

  --  stage   nof +                     nof .                         width     width    input

  --    -     -                         -                              -         w+0     -

  --    0    (N+0)/2                  ((N+0)/1) MOD 2                  w+0       w+1     N

  --    1    (N+1)/4                  ((N+1)/2) MOD 2                  w+1       w+2    (N+0)/2  + ((N+0)/1) MOD 2

  --    2    (N+3)/8                  ((N+3)/4) MOD 2                  w+2       w+3    (N+3)/8  + ((N+3)/4) MOD 2

  --    3    (N+7)/16                 ((N+7)/8) MOD 2                  w+3       w+4    (N+7)/16 + ((N+7)/8) MOD 2

  --                                                                               

  --    j    (N+(2**j)-1)/(2**(j+1))  ((N+(2**j)-1)/(2**j)) MOD 2      w+j       w+j+1

  -- Keep in_dat in stage -1 of adds. Store each subsequent stage of the adder

  -- tree in into adds. Until finally the total sum in the last stage.

  gen_tree : IF g_nof_inputs > 1 GENERATE

    -- Input wires

    adds(-1)(in_dat'RANGE) <= in_dat;

    -- Adder tree

    gen_stage : FOR j IN 0 TO c_nof_stages-1 GENERATE

      gen_add : FOR i IN 0 TO (c_N+(2**j)-1)/(2**(j+1)) - 1 GENERATE

        u_addj : ENTITY work.common_add_sub

        GENERIC MAP (

          g_direction       => "ADD",

          g_representation  => g_representation,

          g_pipeline_input  => c_pipeline_in,

          g_pipeline_output => c_pipeline_out,

          g_in_dat_w        => c_w+j,

          g_out_dat_w       => c_w+j+1

        )

        PORT MAP (

          clk     => clk,

          clken   => clken,

          in_a    => adds(j-1)((2*i+1)*(c_w+j)-1 DOWNTO (2*i+0)*(c_w+j)),

          in_b    => adds(j-1)((2*i+2)*(c_w+j)-1 DOWNTO (2*i+1)*(c_w+j)),

          result  => adds(j)((i+1)*(c_w+j+1)-1 DOWNTO i*(c_w+j+1))

        );

      END GENERATE;

      gen_pipe : IF ((c_N+(2**j)-1)/(2**j)) MOD 2 /= 0 GENERATE

        u_pipej : ENTITY common_components_lib.common_pipeline

        GENERIC MAP (

          g_representation => g_representation,

          g_pipeline       => g_pipeline,

          g_in_dat_w       => c_w+j,

          g_out_dat_w      => c_w+j+1

        )

        PORT MAP (

          clk     => clk,

          clken   => clken,

          in_dat  => adds(j-1)((2*((c_N+(2**j)-1)/(2**(j+1)))+1)*(c_w+j)-1 DOWNTO

                               (2*((c_N+(2**j)-1)/(2**(j+1)))+0)*(c_w+j)),

          out_dat => adds(j)(((c_N+(2**j)-1)/(2**(j+1))+1)*(c_w+j+1)-1 DOWNTO

                             ((c_N+(2**j)-1)/(2**(j+1))  )*(c_w+j+1))

        );

      END GENERATE;

    END GENERATE;

    -- Map final sum to larger output vector using sign extension or to smaller width output vector preserving the LS part

    sum <= RESIZE_SVEC(adds(c_nof_stages-1)(c_sum_w-1 DOWNTO 0), g_sum_w) WHEN g_representation="SIGNED" ELSE

           RESIZE_UVEC(adds(c_nof_stages-1)(c_sum_w-1 DOWNTO 0), g_sum_w);

  END GENERATE;  -- gen_tree

  no_tree : IF g_nof_inputs = 1 GENERATE

    -- For g_nof_inputs = 1 gen_tree yields wires sum <= in_dat, therefore

    -- here use common_pipeline to support g_pipeline. Note c_sum_w =

    -- g_dat_w+1 also for g_nof_inputs = 1, because we assume an adder stage

    -- that adds 0 to the single in_dat.

    u_reg : ENTITY common_components_lib.common_pipeline

    GENERIC MAP (

      g_representation => g_representation,

      g_pipeline       => g_pipeline,

      g_in_dat_w       => g_dat_w,

      g_out_dat_w      => g_sum_w

    )

    PORT MAP (

      clk     => clk,

      clken   => clken,

      in_dat  => in_dat,

      out_dat => sum

    );

  END GENERATE;  -- no_tree

END str;