# examples/mpk/tgraph.py
"""CPU teaching model of MPK's SM-level task graph (tGraph) pipeline.

Standard library only. It decomposes tiny programs into tasks, derives events
from region overlap, fuses events, normalizes forks and joins, linearizes tasks
(Algorithm 1) and replays event-driven dispatch onto FIFO worker queues.

This is an independent teaching model, not MPK's code. It runs no GPU work, and
all counts and durations are for toy graphs, not for the paper's models.
"""

import argparse
import collections
import dataclasses
import heapq
import json
from typing import Callable

INDEX_BYTES = 4  # Assumed width of a task or event index in the toy encoding.


@dataclasses.dataclass(frozen=True)
class Operator:
    """One operator whose output is tiled along a single axis.

    Attributes:
      name: Operator and output tensor name; tasks are named name1, name2, ...
      extent: Length of the output axis.
      tiles: Number of equal tasks; each computes one disjoint output range.
      reads: Maps a task's output range (lo, hi) to the input regions it reads,
        each as (tensor, lo, hi). Inputs that no operator produces are external.
    """

    name: str
    extent: int
    tiles: int
    reads: Callable[[int, int], tuple]


@dataclasses.dataclass
class Event:
    """A synchronization point: it fires once every task in `ins` finishes."""

    ins: set
    outs: set


ATTENTION_BLOCK = (  # The Q/K/V example of Figure 5.
    Operator("Q", 8, 4, lambda lo, hi: ()),
    Operator("K", 4, 2, lambda lo, hi: ()),
    Operator("V", 4, 2, lambda lo, hi: ()),
    Operator("A", 8, 2, lambda lo, hi: (
        ("Q", lo, hi), ("K", lo // 2, hi // 2), ("V", lo // 2, hi // 2))),
    Operator("O", 4, 4, lambda lo, hi: (("A", 0, 8),)),
    Operator("R", 8, 2, lambda lo, hi: (("A", lo, hi),)),
)
MATMUL_ALLREDUCE = (  # Authored: element-wise tiles, as in Figures 3 and 4.
    Operator("M", 8, 4, lambda lo, hi: ()),
    Operator("AR", 8, 4, lambda lo, hi: (("M", lo, hi),)),
)


# region: dependencies
def decompose(operators):
    """Split operator outputs into disjoint tasks: (name, op, out, reads)."""
    tasks = []
    for op in operators:
        if op.extent % op.tiles:
            raise ValueError(f"{op.name}: extent must divide into equal tiles")
        width = op.extent // op.tiles
        for tile in range(op.tiles):
            lo, hi = tile * width, (tile + 1) * width
            tasks.append((f"{op.name}{tile + 1}", op.name, (op.name, lo, hi),
                          op.reads(lo, hi)))
    return tasks


def analyze_dependencies(tasks, granularity="task"):
    """One event per overlapping (producer, consumer) pair, after a start."""
    pairs = []
    for name, _, _, reads in tasks:
        for tensor, lo, hi in reads:
            for other, _, (written, w_lo, w_hi), _ in tasks:
                if written == tensor and w_lo < hi and lo < w_hi:
                    pairs.append((other, name))
    if granularity == "operator":  # A kernel barrier: all tasks to all tasks.
        by_op = collections.defaultdict(list)
        for name, op, _, _ in tasks:
            by_op[op].append(name)
        op_of = {name: op for name, op, _, _ in tasks}
        pairs = [(p, c) for p0, c0 in pairs
                 for p in by_op[op_of[p0]] for c in by_op[op_of[c0]]]
    pairs = list(dict.fromkeys(pairs))
    consumers = {c for _, c in pairs}
    start = Event(set(), {n for n, _, _, _ in tasks if n not in consumers})
    return [start] + [Event({p}, {c}) for p, c in pairs]
# endregion: dependencies


# region: fusion
def _fuse(events, key, merge):
    """Group events by `key`, keeping the start event (empty ins) untouched."""
    fused = {}
    for event in events:
        slot = key(event) if event.ins else id(event)
        if slot in fused:
            merge(fused[slot], event)
        else:
            fused[slot] = Event(set(event.ins), set(event.outs))
    return list(fused.values())


def fuse_successor_sets(events):
    """Definition 4.1: events with equal OutTasks merge; InTasks are unioned."""
    return _fuse(events, lambda e: frozenset(e.outs),
                 lambda keep, e: keep.ins.update(e.ins))


def fuse_predecessor_sets(events):
    """Definition 4.2: events with equal InTasks merge; OutTasks are unioned."""
    return _fuse(events, lambda e: frozenset(e.ins),
                 lambda keep, e: keep.outs.update(e.outs))
# endregion: fusion


def normalize(names, events):
    """Give every task one dependent event and at most one triggering event.

    Section 4.1 adds a fresh event and k empty tasks per fork or join.
    Figure 5(e) draws one fewer: an event whose only trigger (fork) or only
    consumer (join) is the task itself is reused. This model reuses it when
    it exists, and otherwise applies the general rewrite of Figure 6.
    """
    names = list(names)
    events = [Event(set(e.ins), set(e.outs)) for e in events]
    used, count = set(names), 0

    def new_dummy():
        """Return the next unused empty-task name: D1, D2, ..."""
        nonlocal count
        count += 1
        while f"D{count}" in used:
            count += 1
        used.add(f"D{count}")
        names.append(f"D{count}")
        return f"D{count}"

    for task in list(names):  # Forks: a task that triggers several events.
        triggered = [e for e in events if task in e.ins]
        if len(triggered) > 1:
            keep = next((e for e in triggered if e.ins == {task}), None)
            if keep is None:
                keep = Event({task}, set())
                events.append(keep)
            for event in triggered:
                if event is keep:
                    continue
                dummy = new_dummy()
                event.ins.discard(task)
                event.ins.add(dummy)
                keep.outs.add(dummy)
    for task in list(names):  # Joins: a task that waits on several events.
        awaited = [e for e in events if task in e.outs]
        if len(awaited) > 1:
            keep = next((e for e in awaited if e.outs == {task}), None)
            if keep is None:
                keep = Event(set(), {task})
                events.append(keep)
            for event in awaited:
                if event is keep:
                    continue
                dummy = new_dummy()
                event.outs.discard(task)
                event.outs.add(dummy)
                keep.ins.add(dummy)
    return names, events


# region: linearize
def linearize(names, events):
    """Algorithm 1: breadth-first order; each event gets a contiguous range."""
    dependent = {t: i for i, e in enumerate(events) for t in e.outs}
    trigger = {t: i for i, e in enumerate(events) for t in e.ins}
    queue = collections.deque(i for i, e in enumerate(events) if not e.ins)
    order, placed, dequeued = [], set(), []
    while queue:
        current = queue.popleft()
        dequeued.append(current)
        for task in names:
            if dependent[task] == current:
                order.append(task)
                placed.add(task)
                after = trigger.get(task)
                if after is not None and events[after].ins <= placed:
                    queue.append(after)
    if len(order) != len(names):
        raise ValueError("Tasks are unreachable from the start event")
    position = {task: index + 1 for index, task in enumerate(order)}
    table = []
    for number, index in enumerate(dequeued):
        spots = [position[t] for t in events[index].outs]
        first, last = min(spots), max(spots)
        if last - first + 1 != len(spots):
            raise ValueError("Successors are not contiguous")
        table.append({"id": number, "counts": len(events[index].ins),
                      "first": first, "last": last})
    number = {index: n for n, index in enumerate(dequeued)}
    links = {t: [number[dependent[t]], number.get(trigger.get(t))]
             for t in order}
    return order, table, links
# endregion: linearize


def contiguous_events(names, events):
    """Count events whose successors are already adjacent in `names`."""
    where = {task: index for index, task in enumerate(names)}
    count = 0
    for event in events:
        spots = [where[t] for t in event.outs]
        count += max(spots) - min(spots) + 1 == len(spots)
    return count


def encoding_bytes(table):
    """Toy successor storage: explicit lists versus (first, last) ranges.

    Assumption of this model: 4-byte indices; a list stores one index per
    successor plus one length word per event; a range stores two indices.
    """
    successors = sum(row["last"] - row["first"] + 1 for row in table)
    return {"listBytes": INDEX_BYTES * (successors + len(table)),
            "rangeBytes": 2 * INDEX_BYTES * len(table)}


def pairs_of(events):
    """Producer-consumer task pairs implied by events (the start excluded)."""
    return {(p, c) for e in events for p in e.ins for c in e.outs}


def compile_program(operators, granularity="task"):
    """Run decomposition, analysis, fusion, normalization and linearization."""
    tasks = decompose(operators)
    names = [t[0] for t in tasks]
    events = analyze_dependencies(tasks, granularity)
    after_successor = fuse_successor_sets(events)
    fused = fuse_predecessor_sets(after_successor)
    all_names, normal = normalize(names, fused)
    order, table, links = linearize(all_names, normal)
    return {
        "tasks": names,
        "pairEvents": len(events) - 1,
        "successorFused": len(after_successor) - 1,
        "predecessorFused": len(fused) - 1,
        "dummies": len(all_names) - len(names),
        "order": order,
        "events": table,
        "links": links,
        "contiguousBefore": contiguous_events(all_names, normal),
        "encoding": encoding_bytes(table),
        "pairs": sorted(pairs_of(events)),
    }


# region: schedule
def simulate(plan, durations, workers):
    """Replay event-driven dispatch: schedulers enqueue, workers run FIFO."""
    table, order, links = plan["events"], plan["order"], plan["links"]
    remaining = {row["id"]: row["counts"] for row in table}
    queues = [collections.deque() for _ in range(workers)]
    running, finishing, schedule = [None] * workers, [], []

    def start_idle(now):
        for worker in range(workers):
            if running[worker] is None and queues[worker]:
                task = queues[worker].popleft()
                end = now + durations.get(task, 0)
                running[worker] = task
                schedule.append({"task": task, "worker": worker,
                                 "start": now, "end": end})
                heapq.heappush(finishing, (end, worker, task))

    def activate(event, now):
        for index in range(table[event]["first"], table[event]["last"] + 1):
            load = [len(q) + (running[k] is not None)
                    for k, q in enumerate(queues)]
            queues[load.index(min(load))].append(order[index - 1])
        start_idle(now)

    activate(0, 0)  # The start event has no prerequisites.
    while finishing:
        now, worker, task = heapq.heappop(finishing)
        running[worker] = None
        after = links[task][1]
        if after is not None:
            remaining[after] -= 1
            if remaining[after] == 0:
                activate(after, now)
        start_idle(now)
    return schedule
# endregion: schedule


def early_starts(schedule, upstream, downstream):
    """Downstream tasks that begin before the last upstream task ends."""
    last = max(s["end"] for s in schedule if s["task"] in upstream)
    return sum(s["start"] < last for s in schedule if s["task"] in downstream)


def overlap_example(slow_duration=6, workers=4):
    """Operator-level versus task-level events for MatMul then AllReduce."""
    durations = {"M1": 2, "M2": 2, "M3": 2, "M4": slow_duration,
                 "AR1": 4, "AR2": 4, "AR3": 4, "AR4": 1}
    result = {"durations": durations, "workers": workers}
    for granularity in ("operator", "task"):
        plan = compile_program(MATMUL_ALLREDUCE, granularity)
        schedule = simulate(plan, durations, workers)
        result[granularity] = {
            "events": plan["events"],
            "schedule": schedule,
            "makespan": max(s["end"] for s in schedule),
            "earlyStarts": early_starts(
                schedule, {"M1", "M2", "M3", "M4"},
                {"AR1", "AR2", "AR3", "AR4"}),
        }
    return result


def pipeline_timeline(tasks, total_pages, overlap):
    """Authored one-SM timeline of (load, compute, pages) tasks.

    Without overlap, a task preloads only after the previous task finishes. With
    overlap, it may preload once the previous task has issued all its loads and
    enough shared-memory pages are free. Tasks hold pages until compute ends.
    Durations are illustrative units, not measurements.
    """
    holds, segments = [], []
    previous_load_end = previous_compute_end = 0
    for load, compute, pages in tasks:
        if pages > total_pages:
            raise ValueError("A task needs more pages than the SM has")
        start = previous_load_end if overlap else previous_compute_end
        while sum(n for end, n in holds if end > start) + pages > total_pages:
            start = min(end for end, _ in holds if end > start)
        load_end = start + load
        compute_start = max(load_end, previous_compute_end)
        compute_end = compute_start + compute
        holds.append((compute_end, pages))
        segments.append({"loadStart": start, "loadEnd": load_end,
                         "computeStart": compute_start,
                         "computeEnd": compute_end})
        previous_load_end, previous_compute_end = load_end, compute_end
    return segments


def self_check():
    """Check Figure 5, set equivalence, dispatch order and input contracts."""
    plan = compile_program(ATTENTION_BLOCK)
    assert (plan["pairEvents"], plan["successorFused"],
            plan["predecessorFused"], plan["dummies"]) == (18, 8, 5, 2)
    assert plan["order"] == ["Q1", "Q2", "Q3", "Q4", "K1", "K2", "V1", "V2",
                             "A1", "A2", "R1", "D1", "R2", "D2",
                             "O1", "O2", "O3", "O4"]
    # Figure 5(f), by its task rows: e4 has one trigger (A2), e5 has two (D1,
    # D2). The printed Counts row swaps those two values.
    assert [(r["counts"], r["first"], r["last"]) for r in plan["events"]] == [
        (0, 1, 8), (4, 9, 9), (4, 10, 10), (1, 11, 12), (1, 13, 14),
        (2, 15, 18)]
    assert plan["encoding"] == {"listBytes": 96, "rangeBytes": 48}
    assert plan["contiguousBefore"] == 4 and len(plan["events"]) == 6
    tasks = decompose(ATTENTION_BLOCK)
    raw = analyze_dependencies(tasks)
    one = fuse_successor_sets(raw)
    two = fuse_predecessor_sets(one)
    assert pairs_of(raw) == pairs_of(one) == pairs_of(two)
    assert len(fuse_predecessor_sets(fuse_successor_sets(two))) == len(two)
    swapped = fuse_successor_sets(fuse_predecessor_sets(raw))  # Order matters.
    assert pairs_of(swapped) == pairs_of(raw)
    assert sorted(map(sorted, (e.outs for e in swapped))) != sorted(
        map(sorted, (e.outs for e in two)))
    joined, rewired = normalize([t[0] for t in tasks], swapped)
    for task in joined:  # Joins in the swapped graph are rewritten too.
        assert sum(task in e.outs for e in rewired) == 1
        assert sum(task in e.ins for e in rewired) <= 1
    barrier = compile_program(MATMUL_ALLREDUCE, "operator")
    assert [(r["counts"], r["first"], r["last"]) for r in barrier["events"]] \
        == [(0, 1, 4), (4, 5, 8)]
    assert len(compile_program(MATMUL_ALLREDUCE)["events"]) == 5
    example = overlap_example()
    assert (example["operator"]["makespan"], example["task"]["makespan"]) \
        == (10, 7)
    assert (example["operator"]["earlyStarts"],
            example["task"]["earlyStarts"]) == (0, 3)
    for granularity in ("operator", "task"):  # Every run respects every pair.
        rows = example[granularity]["schedule"]
        ends = {s["task"]: s["end"] for s in rows}
        starts = {s["task"]: s["start"] for s in rows}
        assert len(ends) == 8
        for producer, consumer in compile_program(MATMUL_ALLREDUCE)["pairs"]:
            assert starts[consumer] >= ends[producer]
    assert overlap_example(2)["task"]["makespan"] == 6 == \
        overlap_example(2)["operator"]["makespan"]
    forks = compile_program((  # Fork and join around a shared tensor.
        Operator("P", 2, 2, lambda lo, hi: ()),
        Operator("S", 2, 2, lambda lo, hi: (("P", 0, 2),)),
        Operator("T", 2, 1, lambda lo, hi: (("S", 0, 2), ("P", 0, 2)))))
    assert forks["dummies"] > 0 and len(forks["order"]) == 5 + forks["dummies"]
    batch = [(2, 3, 3)] * 4
    assert [s["computeEnd"] for s in pipeline_timeline(batch, 7, True)] \
        == [5, 8, 11, 14]
    assert [s["computeEnd"] for s in pipeline_timeline(batch, 5, True)] \
        == [5, 10, 15, 20]
    assert pipeline_timeline(batch, 7, False)[-1]["computeEnd"] == 20
    for invalid in (lambda: decompose((Operator("X", 5, 2, lambda a, b: ()),)),
                    lambda: pipeline_timeline([(1, 1, 9)], 8, True)):
        try:
            invalid()
        except ValueError:
            pass
        else:
            raise AssertionError("Invalid input was accepted")
    return {
        "attention": plan,
        "overlap": example,
        "overlapEqual": overlap_example(2),
        "pipeline": {str(pages): {mode: pipeline_timeline(batch, pages,
                                                          mode == "overlap")
                                  for mode in ("barrier", "overlap")}
                     for pages in (5, 7)},
    }


def main():
    """Print deterministic results after running the correctness checks."""
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("--json", action="store_true")
    args = parser.parse_args()
    result = self_check()
    if args.json:
        print(json.dumps(result))
    else:
        print("tGraph checks passed: Figure 5 pipeline, fusion, dispatch.")
        attention = result["attention"]
        print(f"  pair events {attention['pairEvents']} -> "
              f"{attention['successorFused']} -> "
              f"{attention['predecessorFused']} events after fusion")
        print(f"  linearized task order: {' '.join(attention['order'])}")
        print(f"  successor storage (toy): {attention['encoding']}")
        print(f"  MatMul+AllReduce makespan (units): operator "
              f"{result['overlap']['operator']['makespan']}, task "
              f"{result['overlap']['task']['makespan']}")


if __name__ == "__main__":
    main()
