3.1 HWLU

The HWLU architecture can be configured for any number of loop nesting levels to eliminate branch instruction overhead for loop increments. The user can regenerate the corresponding files for the top-level module (hwlu) and the priority encoder used internally (prenc) for a different number of supported loops.

The following figure shows the block diagram of the hardware looping architecture.

Block diagram of the HWLU.

Loop index values are produced every clock cycle based on the corresponding loop bound and stride values for each level of nesting. The initial value for the loop indices is provided by a reset mechanism, and the maximum value is equal to the loop bound minus one. In the following cycle of a last iteration for a specific loop, the loop index is reset to its initial value.

The priority encoder performs the actual control logic in context of the hwlu and operates asynchronously by detecting the magnitude comparator (cmpge) outputs (bitwise flag signals) and an external signal preassumably from the datapath (innerloop_end). This signal is produced by the corresponding hardware module that performs the inner loop operations, which may be a dedicated accelerator engine.

If a specific loop is terminating, this loop as well as all its inner loops are reset during the subsequent cycle. For a non-outermost loop, its immediate parent loop index is incremented. In case that none of the loops is terminating, then the inner loop is incremented. Signal innerloop_end guards this increment operation.

Finally, signal done designates that processing in the entire loop structure has terminated.

3.2 IXGENB

The ixgenb architecture variant is based on a hardware algorithm for zero-overhead looping on perfect nests. This algorithm automates the design of compact and efficient hardware looping units that can be implemented as fully synchronous hardware. The looping units of this type are hereafter termed as index generators', and abbreviated to i{IXGEN} which is also used when referring to the algorithm. These units can be also viewed as tuple generators, covering the entire space of ``d`-tuples for d-dimensional data processing.

The first form of the algorithm, named IXGENB, is directly applicable in context of a behavioral HDL model for any number of loops. The pseudocode semantics for implementing these mechanisms can be found below.

local     temp_index: temporary copy of index.
parameter NLP: number of supported loops.
begin
  if innerloop_end == 1 then
    for i in 1 to NLP loop
      if temp_index[i] + stride[i] < loop_count[i] then
        if i greater than 1 then
          for j in 0 to i-1 loop
            temp_index[j] = zero;
          endfor;
        endif
        temp_index[i] = temp_index[i] + stride[i];
        break;
      endif;
      if temp_index[] + stride[] >= loop_count[] then
        temp_index = zero;
        done       = 1;
      endif;
    endfor;
  endif;
  index = temp_index;
 end;

When the data processing in the inner loop is completed, innerloop_end is asserted and a cascaded set of comparisons between index registers to their corresponding loop bound values is activated. The flow of comparisons is directed from outermost to their immediately innermost loops. If the index value is less than the loop bound for a given loop i, the index is incremented by a stride value, while all its outer loops are set to the initial index values. After the first successful comparison, the cascaded structure is prematurely exited in a form similar to the break statement of the C programming language. Given that the cascaded comparisons fail, an index value which is lexicographically larger or equal to loop_count signifies the end of processing in the loop nest.

3.3 IXGENR

The second form of the algorithm, named IXGENR, describes an HDL code generator of an equivalent index generation unit. Its main difference lies in the fact that it uses a priority encoded scheme that cannot be specified in a parameterized manner using natural HDL semantics. The pseudocode semantics of algorithm IXGENR can be found below.

Here, the temporary signals temp<n>_index and loop_count<n> are used where n is the current loop enumeration. In the generated HDL code, these signals are defined as aliased names of elements of the index and loop_count vectors, respectively. It should be noted than all lines featuring a call to the PRINT() routine illustrate emitted code.

local     temp_index: temporary copy of index.
alias     temp_index[i]: i-th segment of temp_index.
alias     loop_count[i]: i-th segment of loop_count.
parameter NLP: number of supported loops.
begin
  PRINT(if innerloop_end = 1 then);
  for i in n downto 1 loop
    if i == n then
      PRINT(if temp_index[i] + stride[i] < loop_count[i] then)
    else
      PRINT(elsif temp_index[i] + stride[i] < loop_count[i] then)
    endif;
    for j in n downto i+1 loop
      PRINT(temp_index[i] = zero;)
    endfor;
    PRINT(temp_index[i] = temp_index[i] + stride[i];)
  endfor;
  PRINT(else)
  for i in 1 to NLP loop
    PRINT(temp_index[i] = zero;)
  endfor;
  done = 1;
  PRINT(endif)
  PRINT(endif)
  PRINT(endif)
  PRINT(index = temp_index;)
end

5.1. GHDL

For running the GHDL simulation, change directory to the /sim/rtl_sim/run subdirectory:

assuming LOOPGEN_HOME is the directory where the top-level /loopgen is found.

Then, the sim.sh shell script is executed, with appropriate command-line arguments for e.g. the hwlu architecture:

The simulation produces a VCD (waveform) dump named hwlu.vcd (correspondingly ixgenb.vcd or ixgenr.vcd for the other two architectural variants) which is automatically copied to the /sim/rtl_sim/out subdirectory. In order to distinguished between different values for generic parameters, the VCD files are renamed to reflect the corresponding settings, e.g. hwlu_3_8.vcd for NLP=3 and DW=8.

The ixgenb and ixgenr designs can be simulated in the same way, if you replace appropriately hwlu in the instructions above.

5.2. Modelsim

For running the Modelsim simulation, e.g. for the hwlu case the corresponding shell script is executed from the /sim/rtl_sim/run subdirectory:

As in the GHDL case, the VCD dump is produced.

Again, the ixgenb and ixgenr designs can be simulated in the same way, if you replace appropriately hwlu in the aforementioned instructions.

5.3 Example operation

The operation of the core is rather simple. Input signal clk is the system clock for the design. Input signal innerloop_end is the termination status flag from the computation unit that performs the operations devoted to the inner loop.

The core performs one loop increment per cycle and when a final iteration for a specific loop is reached, this loop as well as its inner loops are reset in the same cycle.

The operation of the core can be halted in case the signal innerloop_end is deasserted. Then, the contents of the index registers of the hardware looping unit are not changed and any activity beyond the comparator modules is ceased.

The following figure illustrates the timing diagram of a loopgen unit, for loop_bound values equal to X"4", X"7", ``X"4" and stride values equal to X"3", X"1", X"2" for each loop (NLP=3, DW=4).

Timing diagram from sample operation of the loopgen unit.

6.1. Running the synthesis script

For running the Xilinx ISE synthesis tool, change directory to the /syn/xise/run subdirectory:

and execute the corresponding script (for synthesizing hwlu):

The synthesis procedure invokes several Xilinx ISE command-line tools for logic synthesis as described in the corresponding Makefile, found in the the /syn/xise/bin subdirectory.

Typically, this process includes the following:

• Generation of the *.xst synthesis script file.
• Generation of the *.ngc gate-level netlist file in NGC format.
• Building the corresponding *.ngd file.
• Performing mapping using map which generates the corresponding *.ncd file.
• Place-and-routing using par which updates the corresponding *.ncd file.
• Tracing critical paths using trce for reoptimizing the *.ncd file.
• Bitstream generation (*.bit) using bitgen, however with unused pins.

Finally, the hwlu.bit bitstream file is produced.

The same process can be applied for synthesizing the ixgenb and ixgenr designs as well. Notably, ixgenb albeit written in behavioral VHDL is well-accepted and supported for synthesis by the Xilinx XST/ISE logic synthesis tool.