Exact finite checks and a schedule explorer

choices = [] if k < len(arrivals): tail, path = solve(k + 1, tuple(sorted(done))) choices.append((max(len(live) + 1, tail), ("receive " + arrivals[k],) + path))

for name, m in by_name.items(): if name in done: continue if not m.depends <= done or not m.inputs <= live: continue next_done = tuple(sorted(done | name)) tail, path = solve(k, next_done) local_peak = len(live) - len(m.inputs) + m.peak choices.append((max(local_peak, tail), (name,) + path))

need(bool(choices), "decomposition is stuck") return min(choices, key=lambda x: (x[0], x[1]))

start = len(arrivals) if batch else 0 value, path = solve(start, ()) return max(start, value), path

def stream_modules_one(): return ( Module("early", frozenset(("q1", "q2")), frozenset(), frozenset(), 2), Module("late", frozenset(("q3",)), frozenset(("out",)), frozenset(("early",)), 1), )

def stream_modules_two(): modules = [] arrivals = [] for j in (1, 2, 3): q = tuple(f"qjk" for k in (1, 2, 3)) arrivals.extend(q) early = f"earlyj" late = f"latej" modules.append(Module( early, frozenset(q[:2]), frozenset(), frozenset(), 2 )) modules.append(Module( late, frozenset((q[2],)), frozenset((f"tj",)), frozenset((early,)), 1 )) modules.append(Module( "root_early", frozenset(("t1", "t2")), frozenset(), frozenset(("late1", "late2")), 2 )) modules.append(Module( "root_late", frozenset(("t3",)), frozenset(("out",)), frozenset(("root_early", "late3")), 1 )) return tuple(arrivals), tuple(modules)

def batch_modules_two(): modules = [] arrivals = [] for j in (1, 2, 3): q = tuple(f"qjk" for k in (1, 2, 3)) arrivals.extend(q) modules.append(Module( f"decodej", frozenset(q), frozenset((f"tj",)), frozenset(), 3 )) modules.append(Module( "root", frozenset(("t1", "t2", "t3")), frozenset(("out",)), frozenset(("decode1", "decode2", "decode3")), 3 )) return tuple(arrivals), tuple(modules)

def check_schedules(): q1, p1 = optimize_schedule( ("q1", "q2", "q3"), stream_modules_one() ) need(q1 == 2, "wrong single-block module optimum")

arrivals, modules = stream_modules_two() q2, p2 = optimize_schedule(arrivals, modules) need(q2 == 3, "wrong two-level streaming module optimum")

arrivals_b, modules_b = batch_modules_two() qb, pb = optimize_schedule(arrivals_b, modules_b, batch=True) need(qb == 9, "batch input accounting was omitted")