Formulas

Local minimas

Some partitioning algorithms accounts for escaping local minimas, which are called hill-climbing. Their counterpart are called greedy, meaning they only accept moves that immediately improve cost or closeness.

Both types of algorithms can be combined to optimize solving the partitioning problem.

Designer interaction

Both human designers and synthesizers benefit from interaction with the partitioning methods through the following selections:

• Object granularity
• Allocation of system components
• Quality metrics
• Objective and closeness functions
• Algorithm choice(s)

Algorithms

A system with $n$ objects and $m$ system components have $m^n$ possible mappings.

Divided into constructive and iterative algorithms depending on if they create partitions from the ground up or need to be based on an existing partition.

temp = initial temperature
cost = Objfct(P)
while not Frozen loop
    while not Equilibrium loop
        P_tentative = RandomMove(P)
        cost_tentative = Objfct(P_tentative)
        Δcost = cost_tentative - cost
        if (Accept(Δcost,temp) > Random(0,1)) then
            P = P_tentative
            cost = cost_tentative
        end if
    end loop
    temp = DecreaseTemp(temp)
end loop

Quality

There are three main factors considered when determining the quality of an estimator, namely speed, accuracy and fidelity.

Simulated annealing

Simulated annealing is a partition algorithm that models the annealing process in physics, where a material is melted and its minimal energy state is achieved by lowering the temperature slowly enough that equilibrium is reached at each temperature.

– Solution example for 2014 exam

temp = Initial temperature
cost = Objfct(P)
while not Frozen loop
    while not Equilibrium loop
        P_tentative = RandomMove(P)
        cost_tentative = Objfct(P_tentative)
        Δcost = cost_tentative - cost
        if (Accept(Δcost,temp) > Random(0,1)) then
            P = P_tentative
            cost = cost_tentative
        end if
    end loop
    temp = DecreaseTemp(temp)
end loop

ISEGEN

ISEGEN is an instruction set extension generator. ISEGEN will allow the user to optimise a system where an application is running on a CPU by identifying chunks of the program that can be beneficial to replace with a custom instruction, i.e. an instruction set extension, implemented in hardware.

– Solution example for 2014 exam

SetInitialConditions()
last_best_C ⇐ C
loop (until exit condition)
    best_C ⇐ last_best_C
    while (there exists unmarked node in DFG)
        foreach (unmarked node n)
            Calculate M_toggle(n,best_C)
        endfor
        best_node ⇐ Node with maximum Gain
        Toggle and Mark best_node
        CalcImpactOfToggle(best_node,best_C)
        if (toggling best_node satisfies constraints)
            Update best_C from toggling best_node
            Calculate M(best_C)
        endif
    endwhile
    if (M(best_C) > M(last_best_C))
        last_best_C ⇐ best_C
        Unmark all nodes
    endif
endloop
C ⇐ last_best_C

Time Division Multiple Access (TDMA)

Time Division Multiple Access (TDMA) arbitration assigns a bus access time slot to each master. The length of the slots assigned to each master can vary, depending on its transfer requirements. If a master has nothing to send in its time slot, the time slot is wasted, with reduced band width utilization as result.

Round Robin (RR)

Round Robin (RR) arbitration gives the masters access to the bus in a circular manner. It is simple to implement and every master will get access to the bus but with unpredictable delay. Critical data may have to wait a long time.

TDMA/RR

A two-level TDMA/RR first divides the bus band width into a set of time slots for each master. If a master has nothing to send in its time slot, it is given to the other masters in a circular manner. This increases the band width utilization compared with pure TDMA. The cost is an increase in the arbiter implementation complexity.

– Solution example for 2012 exam

Loop permutation

Primarily intended for optimizing address locality and cache hit rate.

Simplified code example:

for k in range(M):
    for j in range(N):
        foo(p[j][k])

would likely be optimized for cache by swapping iteration order of the indexes like in the following counter-example

for j in range(N):
    for i in range(M):
        foo(p[j][k])

Loop fusion

Very simply illustrated with the following example transformation. May be useful for cache optimization.

for j in range(N):
    foo(p[j])

for j in range(N):
    bar(p[j])

$$ \implies $$

for j in range(N):
    foo(p[j])
    bar(p[j])

Loop fission

Loop fission is basically doing the above transformation in reverse. Likely favourable for multi-core processors for concurrent processing.

Loop unrolling

Illustrated in the following example transformation.

$N=16$ loop iterations

for (i = 0; i < 15; i++)
{
    p[j] = foo(j);
}

$$ \implies $$

for (i = 0; i < 15; i+=3)
{
    p[j] = foo(j);
    p[j+1] = foo(j+1);
    p[j+2] = foo(j+2);
}

With a loop factor $f=3$

Note that loops with $N \mod f \neq 0$ must include additional lines of code for operations that do not fit in the new loop.

Loop splitting

for j in range(N):
    if j<K:
        foo()
    else:
        bar()

$$ \implies $$

for j in range(K):
    foo()

for j in range(K, N):
    bar()