iir_ilp1.jl 8 KB
Newer Older
Rémi's avatar
Rémi committed
1
2
function iir_ilp1!(model::Model,
                   wordlength::Int,
Rémi's avatar
Rémi committed
3
                   specifications_init::Vector{Tuple{Float64, Float64, Float64}},
Rémi's avatar
Rémi committed
4
                   ;presolve_order::Int=1, # 1 => a,b | 2 => b,a
5
                   presolve_time_sec::Float64=Inf,
Rémi's avatar
Rémi committed
6
                   use_big_m::Bool=true,
Rémi's avatar
Rémi committed
7
                   nb_adders_lb::Int=0,
8
                   with_symmetry_breaking::Bool=true,
Rémi's avatar
Rémi committed
9
                   avoid_internal_shifts::Bool = false,
Rémi's avatar
Rémi committed
10
11
12
13
                   verbose::Bool = false,
                   debug::Bool = false,
    )
    solution = DesignSolution((0,0), (0,0,0), (0,0), AdderGraph(Vector{AdderNode}()), AdderGraph(Vector{AdderNode}()))
Rémi's avatar
Rémi committed
14
15
    # Call get_gb_secondorder_iir
    verbose && println("Finding bounds for b_k")
Rémi's avatar
Rémi committed
16
    gb = get_gb_secondorder_iir(model, specifications_init, verbose=verbose)
Rémi's avatar
Rémi committed
17
18
19
    if !model[:gb_obtained]
        return solution
    end
Rémi's avatar
Rémi committed
20
    infeasibility_proven = true
Rémi's avatar
Rémi committed
21
    scaling_init = (1, gb) # stability -- a_k in [-2,2]
Rémi's avatar
Rémi committed
22
    best_A = typemax(Int)
Rémi's avatar
Rémi committed
23
24
25
26

    scalings = union([(scaling_a, scaling_init[2]) for scaling_a in scaling_init[1]:-1:(scaling_init[1]-wordlength)], [(scaling_init[1], scaling_b) for scaling_b in (scaling_init[2]-1):-1:(scaling_init[2]-wordlength)])
    for scaling in scalings
        empty!(model)
Rémi's avatar
Rémi committed
27
28
29
30
31
        model[:presolve_done] = false
        model[:success_presolve] = false
        model[:scaling] = scaling
        presolve_done, success_presolve = model[:presolve_done], model[:success_presolve]
        current_AM = nb_adders_lb
Rémi's avatar
Rémi committed
32
33
34
        verbose && println("Scaling (a, b): $(scaling)")
        specifications = scale_specifications(specifications_init, scaling)

Rémi's avatar
Rémi committed
35
36
37
38
39
        while (!presolve_done || success_presolve) && current_AM < best_A
            if !presolve_done
                # Call iir_design!
                verbose && println("Generation of IIR design part")
                iir_design!(model, specifications, wordlength, use_big_m=use_big_m, with_symmetry_breaking=with_symmetry_breaking, verbose=verbose)
Rémi's avatar
Rémi committed
40

Rémi's avatar
Rémi committed
41
42
43
44
45
46
47
48
49
50
                presolve_done = true
                # Presolve? a_k? b_k?
                verbose && println("Presolving")
                first_presolve! = presolve_a!
                second_presolve! = presolve_b!
                if presolve_order == 2
                    first_presolve! = presolve_b!
                    second_presolve! = presolve_a!
                end
                presolve_time_sec_for_each_coef = presolve_time_sec/5
Rémi's avatar
Rémi committed
51

Rémi's avatar
Rémi committed
52
53
                timelimit = time_limit_sec(model)
                set_time_limit_sec(model, timelimit)
Rémi's avatar
Rémi committed
54

Rémi's avatar
Rémi committed
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
                first_presolve!(model, presolve_time_sec_for_each_coef=presolve_time_sec_for_each_coef, verbose=verbose)
                if !model[:success_presolve]
                    if !model[:infeasibility_proven]
                        infeasibility_proven = false
                    end
                    continue
                else
                    infeasibility_proven = false
                end
                second_presolve!(model, presolve_time_sec_for_each_coef=presolve_time_sec_for_each_coef, verbose=verbose)
                @assert model[:success_presolve]
                success_presolve = model[:success_presolve]
                verbose && println(model[:bounds_a])
                verbose && println(model[:bounds_b])
            end
            bounds_a, bounds_b = model[:bounds_a], model[:bounds_b]
Rémi's avatar
Rémi committed
71

Rémi's avatar
Rémi committed
72
73
74
75
76
77
78
            # Add MCM ILP1 to model
            verbose && println("Adding MCM to the model and solving...")
            mcm_ilp_odd_increment!(model, wordlength, specifications,
                                   model[:bounds_a], model[:bounds_b], nb_adders_lb=current_AM,
                                   use_big_m=use_big_m, avoid_internal_shifts=avoid_internal_shifts,
                                   verbose=verbose, only_positive=true, no_output_shifts=false,
                                   nb_total_adders_ub=best_A-1)
Rémi's avatar
Rémi committed
79

Rémi's avatar
Rémi committed
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
            current_AM = model[:NA]+1
            if termination_status(model) == MOI.OPTIMAL
                NA = model[:NA]
                best_A = NA+sum(1-round(Int, value(model[:azero][m])) for m in 1:2)+sum(1-round(Int, value(model[:bzero][m])) for m in 0:2)-1
                verbose && println("Current solution -- A: $(best_A)")
                solution.coefficients_a = (round(Int, value(model[:a][1])), round(Int, value(model[:a][2])))
                solution.coefficients_b = (round(Int, value(model[:b][0])), round(Int, value(model[:b][1])), round(Int, value(model[:b][2])))
                verbose && println("\tcoefficients b: ", solution.coefficients_b)
                verbose && println("\tcoefficients a: ", solution.coefficients_a)
                solution.shifts = (wordlength-1-model[:scaling][1]+round(Int, log2(value(model[:a0]))), wordlength-1-model[:scaling][2]+round(Int, log2(value(model[:a0]))))
                verbose && println("\tshifts (a,b): ", solution.shifts)
                solution.addergraph_a = AdderGraph(Vector{AdderNode}(), collect(solution.coefficients_a))
                for i in 1:NA
                    if round(Int, value(model[:mcma][i])) == 1
                        node_shift = 0
                        for s in -wordlength:0
                            if round(Int, value(model[:Psias][i,s])) == 1
                                node_shift = s
                                break
                            end
Rémi's avatar
Rémi committed
100
                        end
Rémi's avatar
Rémi committed
101
102
103
104
105
106
                        input_shift = 0
                        for s in 0:wordlength
                            if round(Int, value(model[:phias][i,s])) == 1
                                input_shift = s
                                break
                            end
Rémi's avatar
Rémi committed
107
                        end
Rémi's avatar
Rémi committed
108
109
                        subtraction = [value(model[:cai_right_shsg][i]) < 0, value(model[:cai_left_sg][i]) < 0]
                        push_node!(solution.addergraph_a,
Rémi's avatar
Rémi committed
110
111
112
                            AdderNode(round(Int, value(model[:ca][i])),
                                      [InputEdge(get_addernode_by_value(addergraph, round(Int, value(model[:cai][i,1]))), input_shift+node_shift, subtraction[1]),
                                      InputEdge(get_addernode_by_value(addergraph, round(Int, value(model[:cai][i,2]))), node_shift, subtraction[2])]
Rémi's avatar
Rémi committed
113
                            ))
Rémi's avatar
Rémi committed
114
115
                    end
                end
Rémi's avatar
Rémi committed
116
117
118
119
120
121
122
123
124
                solution.addergraph_b = AdderGraph(Vector{AdderNode}(), collect(solution.coefficients_b))
                for i in 1:NA
                    if round(Int, value(model[:mcmb][i])) == 1
                        node_shift = 0
                        for s in -wordlength:0
                            if round(Int, value(model[:Psias][i,s])) == 1
                                node_shift = s
                                break
                            end
Rémi's avatar
Rémi committed
125
                        end
Rémi's avatar
Rémi committed
126
127
128
129
130
131
                        input_shift = 0
                        for s in 0:wordlength
                            if round(Int, value(model[:phias][i,s])) == 1
                                input_shift = s
                                break
                            end
Rémi's avatar
Rémi committed
132
                        end
Rémi's avatar
Rémi committed
133
134
                        subtraction = [value(model[:cai_right_shsg][i]) < 0, value(model[:cai_left_sg][i]) < 0]
                        push_node!(solution.addergraph_b,
Rémi's avatar
Rémi committed
135
136
137
                            AdderNode(round(Int, value(model[:ca][i])),
                                      [InputEdge(get_addernode_by_value(addergraph, round(Int, value(model[:cai][i,1]))), input_shift+node_shift, subtraction[1]),
                                      InputEdge(get_addernode_by_value(addergraph, round(Int, value(model[:cai][i,2]))), node_shift, subtraction[2])]
Rémi's avatar
Rémi committed
138
                            ))
Rémi's avatar
Rémi committed
139
140
141
142
143
144
                    end
                end
            end
            empty!(model)
            model[:scaling] = scaling
            model[:bounds_a], model[:bounds_b] = bounds_a, bounds_b
Rémi's avatar
Rémi committed
145
            model[:presolve_done], model[:success_presolve] = presolve_done, success_presolve
Rémi's avatar
Rémi committed
146
147
        end
    end
Rémi's avatar
Rémi committed
148

Rémi's avatar
Rémi committed
149
150
151
152
    if infeasibility_proven
        @warn "No second-order IIR filter for these specifications"
    end

Rémi's avatar
Rémi committed
153
    return solution
Rémi's avatar
Rémi committed
154
end