Main Content

High-Level Synthesis Code Generation for Bisection Algorithm

Open Script

You can generate High-Level Synthesis (HLS) code from a MATLAB® design that implements a bisection algorithm to calculate the square root of a number in fixed-point notation.

MATLAB Design

First, set up the sqrt model.

mlhdlc_demo_setup('sqrt');

% Design Sqrt
design_name = 'mlhdlc_sqrt';

% Test Bench for Sqrt
testbench_name = 'mlhdlc_sqrt_tb';

Successfully copied: mlhdlc_sqrt
Successfully copied: mlhdlc_sqrt_runme
Successfully copied: mlhdlc_sqrt_tb
Successfully copied: mlhdlc_tutorial_sqrt
Successfully copied: mlhdlc_msysobj_nonrestsqrt
Successfully copied: mlhdlc_sysobj_nonrestsqrt
Successfully copied: mlhdlc_sysobj_nonrestsqrt_runme
Successfully copied: mlhdlc_sysobj_nonrestsqrt_tb
Successfully copied: mlhdlc_tutorial_sysobj_nonrestsqrt

Review the sqrt design

dbtype(design_name)

1     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2     % MATLAB design: Pipelined Bisection Square root algorithm
3     % 
4     % Introduction:
5     % 
6     % Implement SQRT by the bisection algorithm in a pipeline, for unsigned fixed
7     % point numbers (also why you don't need to run fixed-point conversion for this design).
8     % The demo illustrates the usage of a pipelined implementation for numerical algorithms.
9     %
10    % Key Design pattern covered in this example: 
11    % (1) State of the bisection algorithm is maintained with persistent variables
12    % (2) Stages of the bisection algorithm are implemented in a pipeline 
13    % (3) Code is written in a parameterized fashion, i.e. word-length independent, to work for any size fi-type
14    % 
15    % Ref. 1. R. W. Hamming, "Numerical Methods for Scientists and Engineers," 2nd, Ed, pp 67-69. ISBN-13: 978-0486652412.
16    %      2. Bisection method, http://en.wikipedia.org/wiki/Bisection_method, (accessed 02/18/13).
17    %      
18    
19    %   Copyright 2013-2015 The MathWorks, Inc.
20    
21    %#codegen
22    function [y,z] = mlhdlc_sqrt( x )
23        persistent sqrt_pipe
24        persistent in_pipe
25       if isempty(sqrt_pipe)
26           sqrt_pipe = fi(zeros(1,x.WordLength),numerictype(x));
27           in_pipe = fi(zeros(1,x.WordLength),numerictype(x));
28       end
29       
30       % Extract the outputs from pipeline
31       y = sqrt_pipe(x.WordLength);
32       z = in_pipe(x.WordLength); 
33       
34       % for analysis purposes you can calculate the error between the fixed-point bisection routine and the floating point result.
35       %Q = [double(y).^2, double(z)];
36       %[Q, diff(Q)]
37       
38       % work the pipeline
39       for itr = x.WordLength-1:-1:1       
40           % move pipeline forward
41           in_pipe(itr+1) = in_pipe(itr);
42           % guess the bits of the square-root solution from MSB to the LSB of word length
43           sqrt_pipe(itr+1) = guess_and_update( sqrt_pipe(itr), in_pipe(itr+1), itr );
44       end
45       
46       %% Prime the pipeline
47       % with new input and the guess
48       in_pipe(1) = x;
49       sqrt_pipe(1) = guess_and_update( fi(0,numerictype(x)), x, 1 );
50       
51       %% optionally print state of the pipeline
52       %disp('************** State of Pipeline **********************')
53       %double([in_pipe; sqrt_pipe])
54       
55       return
56    end
57    
58    % Guess the bits of the square-root solution from MSB to the LSB in
59    % a binary search-fashion.
60    function update = guess_and_update( prev_guess, x, stage )    
61        % Key step of the bisection algorithm is to set the bits
62        guess = bitset( prev_guess, x.WordLength - stage + 1);
63        % compare if the set bit is a candidate solution to retain or clear it
64        if ( guess*guess <= x )        
65            update = guess;
66        else        
67            update = prev_guess;
68        end
69        return
70    end

Simulate the Design

It is a best practice to simulate the design with the test bench prior to code generation to check for run-time errors.

mlhdlc_sqrt_tb

Iter = 01| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 02| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 03| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 04| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 05| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 06| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 07| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 08| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 09| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 10| Input = 0.000| Output = 0000000000 (0.00) | actual = 0.000000 | abserror = 0.000000
Iter = 11| Input = 4.625| Output = 0000010000 (2.00) | actual = 2.150581 | abserror = 0.150581
Iter = 12| Input = 12.500| Output = 0000011100 (3.50) | actual = 3.535534 | abserror = 0.035534
Iter = 13| Input = 16.250| Output = 0000100000 (4.00) | actual = 4.031129 | abserror = 0.031129
Iter = 14| Input = 18.125| Output = 0000100010 (4.25) | actual = 4.257347 | abserror = 0.007347
Iter = 15| Input = 20.125| Output = 0000100010 (4.25) | actual = 4.486090 | abserror = 0.236090
Iter = 16| Input = 21.875| Output = 0000100100 (4.50) | actual = 4.677072 | abserror = 0.177072
Iter = 17| Input = 35.625| Output = 0000101110 (5.75) | actual = 5.968668 | abserror = 0.218668
Iter = 18| Input = 50.250| Output = 0000111000 (7.00) | actual = 7.088723 | abserror = 0.088723
Iter = 19| Input = 54.000| Output = 0000111010 (7.25) | actual = 7.348469 | abserror = 0.098469
Iter = 20| Input = 62.125| Output = 0000111110 (7.75) | actual = 7.881941 | abserror = 0.131941
Iter = 21| Input = 70.000| Output = 0001000010 (8.25) | actual = 8.366600 | abserror = 0.116600
Iter = 22| Input = 81.000| Output = 0001001000 (9.00) | actual = 9.000000 | abserror = 0.000000
Iter = 23| Input = 83.875| Output = 0001001000 (9.00) | actual = 9.158330 | abserror = 0.158330
Iter = 24| Input = 83.875| Output = 0001001000 (9.00) | actual = 9.158330 | abserror = 0.158330
Iter = 25| Input = 86.875| Output = 0001001010 (9.25) | actual = 9.320676 | abserror = 0.070676
Iter = 26| Input = 95.125| Output = 0001001110 (9.75) | actual = 9.753205 | abserror = 0.003205
Iter = 27| Input = 97.000| Output = 0001001110 (9.75) | actual = 9.848858 | abserror = 0.098858
Iter = 28| Input = 101.375| Output = 0001010000 (10.00) | actual = 10.068515 | abserror = 0.068515
Iter = 29| Input = 102.375| Output = 0001010000 (10.00) | actual = 10.118053 | abserror = 0.118053
Iter = 30| Input = 104.250| Output = 0001010000 (10.00) | actual = 10.210289 | abserror = 0.210289

Create HDL Coder™ Project

Create an HDL Coder project.

coder -hdlcoder -new mlhdlc_sqrt_prj

Add the file mlhdlc_sqrt.m to the project as the MATLAB Function. Add the file mlhdlc_sqrt_tb.m as the MATLAB Test Bench.

For more information, see Get Started with MATLAB to High-Level Synthesis Workflow Using the Command Line Interface or Get Started with MATLAB to High-Level Synthesis Workflow Using HDL Coder App.

HLS Code Generation

This design is already in fixed point and suitable for HLS code generation. You do not need to run floating point to fixed point conversion on this design.

To generate HLS code from the MATLAB design:

1. At the MATLAB command line, set up the path for HLS code generation by using the function hdlsetuphlstoolpath.

2. Start the Workflow Advisor by clicking the Workflow Advisor button.

3. In the HDL Workflow Advisor, select Code Generation Workflow as MATLAB to HLS.

4. In the Select Code Generation Target step, from the Synthesis tool list, select Cadence Stratus.

5. Right-click the HLS Code Generation task and select Run to selected task to run all the steps from the beginning through the HLS code generation.

Examine the generated HLS code by clicking the hyperlinks in the HLS Code Generation log window.

See Also