ScheduleChainGraph.py

from math import gcd
from math import inf

# actors is a list of strings, the strings being the names of the actors
def ConvertSplits(actors, GCD, SplitPositions, L, R):
    if (L == R): return actors[L]

    s = int(SplitPositions[L][R])
    iL = GCD[L][L + s] // GCD[L][R]
    iR = GCD[L + s + 1][R] // GCD[L][R]
    
    leftSchedule = ConvertSplits(actors, GCD, SplitPositions, L, L + s)
    rightSchedule = ConvertSplits(actors, GCD, SplitPositions, L + s + 1, R)

    leftStr = f"{iL}({leftSchedule})" if iL > 1 else leftSchedule
    rightStr = f"{iL}({rightSchedule})" if iR > 1 else rightSchedule

    return f"{leftStr} {rightStr}"

# Sizes of produced and consumed are the same and equal to # of edges in SDFG
# q is the minimum-firing periodic flat SAS
def ScheduleChainGraph(actors, produced, consumed, q):
    size = len(actors)
    GCD = [[0 for i in range(size)] for j in range(size)]
    Subcosts = [[0 for i in range(size)] for j in range(size)]
    SplitPositions = [[0 for i in range(size)] for j in range(size)]

    # Compute GCD's of all subchains
    for i in range(size):
        GCD[i][i] = q[i]

        for j in range(i + 1, size):
            GCD[i][j] = gcd(GCD[i][j - 1], q[j])
    print(GCD)

    for chain_size in range(2, size + 1):
        for right in range(chain_size - 1, size):
            left = right - chain_size + 1
            min_cost = inf
            split = -1
            for i in range(chain_size - 1):
                split_cost = (q[left + i] / GCD[left][right]) * produced[left + i]
                total_cost = split_cost + Subcosts[left][left + i] + Subcosts[left + i + 1][right]
                if total_cost < min_cost:
                    split = i
                    min_cost = total_cost
            Subcosts[left][right] = min_cost
            SplitPositions[left][right] = split
    print(Subcosts)
    print(SplitPositions)
    print(ConvertSplits(actors, GCD, SplitPositions, 0, size - 1))

actors = ["A", "B", "C", "D", "E"]
produced = [3, 5, 6, 2]
consumed = [4, 3, 5, 3]
q = [4, 3, 5, 6, 4]

ScheduleChainGraph(actors, produced, consumed, q)