4x4 dot product code

[IainNZ]

4 .* 4 Dot Product

[a,b,c,d] .* [e,f,g,h]
=
a*e  b*f  c*g   d*h
    +         +
         +

Assume multiply is two operations
Assume can do two multiplies at a time
Assume add is two operations
Assume can do two additions at a time

[IainNZ]

T = 30  # Time horizon
L = 4   # Instruction length
R = 3   # Max registers
C = 2   # Max simultaneous multiplies and adds

using JuMP, Gurobi
m = Model(solver=GurobiSolver())
@defVar(m, x[i=1:7,t=1:T], Bin)
@defVar(m, y[i=1:7,t=1:T], Bin)
@defVar(m, r[i=1:7,t=1:T], Bin)

# Link state y to start x
for i in 1:7
    for t in 1:T-L+1
        for s in t:t+L-1
            @addConstraint(m, y[i,s] >= x[i,t])
        end
    end
end

# Must run each instruction
for i in 1:7
    @addConstraint(m, sum(x[i,1:T-L]) == 1)
end

# Manually implement precedence
for t in 1:T-L
    # Add 1 after Mult 1 and Mult 2
    @addConstraint(m, x[5,t] <= sum{x[1,s],s=1:t-L})
    @addConstraint(m, x[5,t] <= sum{x[2,s],s=1:t-L})
    # Add 2 after Mult 3 and Mult 4
    @addConstraint(m, x[6,t] <= sum{x[3,s],s=1:t-L})
    @addConstraint(m, x[6,t] <= sum{x[4,s],s=1:t-L})
    # Add 3 afer Add 1 and Add 2
    @addConstraint(m, x[7,t] <= sum{x[5,s],s=1:t-L})
    @addConstraint(m, x[7,t] <= sum{x[6,s],s=1:t-L})
end

# Can't start more than one at a time
for t in 1:T
    @addConstraint(m, sum(x[:,t]) <= 1)
end

# Can't more than a certain number of ops at a time
for t in 1:T
    # Multiplies
    @addConstraint(m, sum{y[i,t],i=1:4} <= C)
    # Adds
    @addConstraint(m, sum{y[i,t],i=5:7} <= C)
end

# Register occupation
for t in 1:T
    @addConstraint(m, r[1,t] >= sum{x[1,s],s=1:t} - sum{x[5,s],s=1:t} )
    @addConstraint(m, r[2,t] >= sum{x[2,s],s=1:t} - sum{x[5,s],s=1:t} )
    @addConstraint(m, r[3,t] >= sum{x[3,s],s=1:t} - sum{x[6,s],s=1:t} )
    @addConstraint(m, r[4,t] >= sum{x[4,s],s=1:t} - sum{x[6,s],s=1:t} )
    @addConstraint(m, r[5,t] >= sum{x[5,s],s=1:t} - sum{x[7,s],s=1:t} )
    @addConstraint(m, r[6,t] >= sum{x[6,s],s=1:t} - sum{x[7,s],s=1:t} )
    @addConstraint(m, r[7,t] >= sum{x[7,s],s=1:t} )
    @addConstraint(m, sum(r[:,t]) <= R)
end

# Force 1 to start at time 1
@addConstraint(m, x[1,1] == 1)

# Finish ASAP
@setObjective(m, Min, sum{t*sum(y[:,t]),t=1:T})

solve(m)

for i in 1:7
    println(i)
    println(iround(getValue(x[i,:])))
    println(iround(getValue(y[i,:])))
    println(iround(getValue(r[i,:])))
end

[IainNZ]

1
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
2
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
3
[0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
4
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
5
[0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1]
6
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1]
7
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]