def synthesize_alltoall_subproblem(subproblem_algo, num_copies, logging=False):
    if subproblem_algo.is_pipelined():
        raise ValueError('Pipelining is not supported.')
    local_topology = subproblem_algo.topology
    chunks = subproblem_algo.instance.chunks
    local_nodes = (local_topology.num_nodes() - 1)
    remote_node = local_nodes
    nodes = (local_nodes * num_copies)
    collective = alltoall(nodes).chunk_up(chunks)
    links = [[0 for _ in range(nodes)] for _ in range(nodes)]
    for dst in range(nodes):
        for src in range(nodes):
            local_src = (src % local_nodes)
            local_dst = (dst % local_nodes)
            if ((src // local_nodes) != (dst // local_nodes)):
                bw = min(local_topology.link(local_src, remote_node), local_topology.link(remote_node, local_dst))
                links[dst][src] = bw
            else:
                links[dst][src] = local_topology.link(local_src, local_dst)
    switches = []
    for (srcs, dsts, bw, name) in local_topology.switches:
        for i in range(num_copies):

            def to_dist(ranks):
                for rank in ranks:
                    if (rank < remote_node):
                        (yield (rank + (i * local_nodes)))
                    else:
                        for r in range(nodes):
                            if ((r // local_nodes) != i):
                                (yield r)
            dist_srcs = list(to_dist(srcs))
            dist_dsts = list(to_dist(dsts))
            switches.append((dist_srcs, dist_dsts, bw, f'copy_{i}_{name}_local'))
    topology = Topology(f'Stiched(sub={local_topology.name},copies={num_copies})', links, switches)

    def nth_chunk_for_pair(src, dst, idx):
        return (((src + (dst * collective.num_nodes)) * chunks) + idx)
    steps = []
    local_end = (local_nodes * local_nodes)
    num_remote_pairs = (((num_copies - 1) * local_nodes) * local_nodes)
    remote_out_end = (local_end + num_remote_pairs)
    num_chunks = (remote_out_end + num_remote_pairs)
    for local_step in subproblem_algo.steps:
        sends = []
        unmatched_sends = {}
        unmatched_recvs = {}
        for (chunk, src, dst) in local_step.sends:
            for i in range(num_copies):

                def to_dist(rank):
                    return (rank + (i * local_nodes))

                def other_start(c):
                    other_i = (c % (num_copies - 1))
                    if (other_i >= i):
                        other_i += 1
                    return (other_i * local_nodes)
                if (chunk < local_end):
                    assert ((src != remote_node) and (dst != remote_node))
                    origin = to_dist(((chunk // chunks) % local_nodes))
                    target = to_dist(((chunk // chunks) // local_nodes))
                    assert subproblem_algo.collective.precondition((origin % local_nodes), chunk)
                    assert subproblem_algo.collective.postcondition((target % local_nodes), chunk)
                elif (chunk < remote_out_end):
                    c = (chunk - local_end)
                    local_origin = (((c // chunks) // (num_copies - 1)) % local_nodes)
                    origin = to_dist(local_origin)
                    target = (other_start(c) + ((c // (num_copies - 1)) // local_nodes))
                    assert subproblem_algo.collective.precondition(local_origin, chunk)
                    assert subproblem_algo.collective.postcondition((target % local_nodes), (chunk + num_remote_pairs))
                else:
                    assert (chunk < num_chunks)
                    c = (chunk - remote_out_end)
                    local_target = (((c // chunks) // (num_copies - 1)) // local_nodes)
                    target = to_dist(local_target)
                    origin = (other_start(c) + ((c // (num_copies - 1)) % local_nodes))
                    assert subproblem_algo.collective.precondition((origin % local_nodes), (chunk - num_remote_pairs))
                    assert subproblem_algo.collective.postcondition(local_target, chunk)
                chunk_idx = (chunk % chunks)
                dist_chunk = nth_chunk_for_pair(origin, target, chunk_idx)
                if (dst == remote_node):
                    assert (chunk < remote_out_end)
                    if (dist_chunk in unmatched_recvs):
                        dist_dst = unmatched_recvs.pop(dist_chunk)
                        sends.append((dist_chunk, to_dist(src), dist_dst))
                    else:
                        unmatched_sends[dist_chunk] = to_dist(src)
                elif (src == remote_node):
                    assert (chunk < num_chunks)
                    if (dist_chunk in unmatched_sends):
                        dist_src = unmatched_sends.pop(dist_chunk)
                        sends.append((dist_chunk, dist_src, to_dist(dst)))
                    else:
                        unmatched_recvs[dist_chunk] = to_dist(dst)
                else:
                    sends.append((dist_chunk, to_dist(src), to_dist(dst)))
        if ((len(unmatched_sends) > 0) or (len(unmatched_recvs) > 0)):
            raise ValueError('Subproblem algorithm has unpaired sends/recvs.')
        steps.append(Step(local_step.rounds, sends))
    instance = Instance(steps=len(steps), extra_rounds=sum(((step.rounds - 1) for step in steps)), chunks=chunks)
    return Algorithm.make_implementation(collective, topology, instance, steps)
def synthesize_alltoall_subproblem(subproblem_algo, num_copies, logging=False):
    if subproblem_algo.is_pipelined():
        raise ValueError('Pipelining is not supported.')
    local_topology = subproblem_algo.topology
    chunks = subproblem_algo.instance.chunks
    local_nodes = (local_topology.num_nodes() - 1)
    remote_node = local_nodes
    nodes = (local_nodes * num_copies)
    collective = alltoall(nodes).chunk_up(chunks)
    links = [[0 for _ in range(nodes)] for _ in range(nodes)]
    for dst in range(nodes):
        for src in range(nodes):
            local_src = (src % local_nodes)
            local_dst = (dst % local_nodes)
            if ((src // local_nodes) != (dst // local_nodes)):
                bw = min(local_topology.link(local_src, remote_node), local_topology.link(remote_node, local_dst))
                links[dst][src] = bw
            else:
                links[dst][src] = local_topology.link(local_src, local_dst)
    switches = []
    for (srcs, dsts, bw, name) in local_topology.switches:
        for i in range(num_copies):

            def to_dist(ranks):
                for rank in ranks:
                    if (rank < remote_node):
                        (yield (rank + (i * local_nodes)))
                    else:
                        for r in range(nodes):
                            if ((r // local_nodes) != i):
                                (yield r)
            dist_srcs = list(to_dist(srcs))
            dist_dsts = list(to_dist(dsts))
            switches.append((dist_srcs, dist_dsts, bw, f'copy_{i}_{name}_local'))
    topology = Topology(f'Stiched(sub={local_topology.name},copies={num_copies})', links, switches)

    def nth_chunk_for_pair(src, dst, idx):
        return (((src + (dst * collective.num_nodes)) * chunks) + idx)
    steps = []
    local_end = (local_nodes * local_nodes)
    num_remote_pairs = (((num_copies - 1) * local_nodes) * local_nodes)
    remote_out_end = (local_end + num_remote_pairs)
    num_chunks = (remote_out_end + num_remote_pairs)
    for local_step in subproblem_algo.steps:
        sends = []
        unmatched_sends = {}
        unmatched_recvs = {}
        for (chunk, src, dst) in local_step.sends:
            for i in range(num_copies):

                def to_dist(rank):
                    return (rank + (i * local_nodes))

                def other_start(c):
                    other_i = (c % (num_copies - 1))
                    if (other_i >= i):
                        other_i += 1
                    return (other_i * local_nodes)
                if (chunk < local_end):
                    assert ((src != remote_node) and (dst != remote_node))
                    origin = to_dist(((chunk // chunks) % local_nodes))
                    target = to_dist(((chunk // chunks) // local_nodes))
                    assert subproblem_algo.collective.precondition((origin % local_nodes), chunk)
                    assert subproblem_algo.collective.postcondition((target % local_nodes), chunk)
                elif (chunk < remote_out_end):
                    c = (chunk - local_end)
                    local_origin = (((c // chunks) // (num_copies - 1)) % local_nodes)
                    origin = to_dist(local_origin)
                    target = (other_start(c) + ((c // (num_copies - 1)) // local_nodes))
                    assert subproblem_algo.collective.precondition(local_origin, chunk)
                    assert subproblem_algo.collective.postcondition((target % local_nodes), (chunk + num_remote_pairs))
                else:
                    assert (chunk < num_chunks)
                    c = (chunk - remote_out_end)
                    local_target = (((c // chunks) // (num_copies - 1)) // local_nodes)
                    target = to_dist(local_target)
                    origin = (other_start(c) + ((c // (num_copies - 1)) % local_nodes))
                    assert subproblem_algo.collective.precondition((origin % local_nodes), (chunk - num_remote_pairs))
                    assert subproblem_algo.collective.postcondition(local_target, chunk)
                chunk_idx = (chunk % chunks)
                dist_chunk = nth_chunk_for_pair(origin, target, chunk_idx)
                if (dst == remote_node):
                    assert (chunk < remote_out_end)
                    if (dist_chunk in unmatched_recvs):
                        dist_dst = unmatched_recvs.pop(dist_chunk)
                        sends.append((dist_chunk, to_dist(src), dist_dst))
                    else:
                        unmatched_sends[dist_chunk] = to_dist(src)
                elif (src == remote_node):
                    assert (chunk < num_chunks)
                    if (dist_chunk in unmatched_sends):
                        dist_src = unmatched_sends.pop(dist_chunk)
                        sends.append((dist_chunk, dist_src, to_dist(dst)))
                    else:
                        unmatched_recvs[dist_chunk] = to_dist(dst)
                else:
                    sends.append((dist_chunk, to_dist(src), to_dist(dst)))
        if ((len(unmatched_sends) > 0) or (len(unmatched_recvs) > 0)):
            raise ValueError('Subproblem algorithm has unpaired sends/recvs.')
        steps.append(Step(local_step.rounds, sends))
    instance = Instance(steps=len(steps), extra_rounds=sum(((step.rounds - 1) for step in steps)), chunks=chunks)
    return Algorithm.make_implementation(collective, topology, instance, steps)