def generate_scheduling_plan(logged_times, gpu: int):
    global total_memory
    global global_tensors
    init(logged_times, gpu)
    tensor_nums = list(map((lambda x: len(x)), tensor_access_by_tensor))
    swap_out_number_limits = [int((weight * tensor_num)) for (weight, tensor_num) in zip(jobs_weights, tensor_nums)]
    swap_out_number = [0 for _ in tensor_nums]
    swapped_out_tensor = set()
    swapped_in_source_tensor = set()
    swap_out_dict = {}
    swapped_in_access = set()
    recomputations = []
    recomputation_tensor = set()
    swapped_flag = True
    recomputation_flag = True
    iter = 0
    original_memory_used = 0
    last_memory_used = 0
    job_id_ordered_by_weights = list(map((lambda x: x[0]), sorted([(job_id, weights) for (job_id, weights) in enumerate(jobs_weights)], key=(lambda x: x[1]), reverse=True)))
    max_memory_footprint = []
    while (swapped_flag or (recomputation_flag and enable_recomputation)):
        if (not debug_mod):
            total_memory = (nvmlDeviceGetMemoryInfo(handle).free / 1000000)
        else:
            total_memory = 6000
        (max_memory, max_tensors, last_input_accesses, max_time, time_axis) = run_global_memory_analysis(swap_scheduler, swapped_out_tensor)
        max_memory_footprint.append(max_memory)
        if ((len(max_memory_footprint) > 3) and (max([(max_memory_footprint[i] - max_memory_footprint[(i + 1)]) for i in range((len(max_memory_footprint) - 3), (len(max_memory_footprint) - 1))]) < (max_memory_footprint[(- 1)] * 0.0005)) and (iter > 100)):
            break
        if (iter == 0):
            original_memory_used = max_memory
            liveness_analysis(global_tensor_access)
        else:
            last_memory_used = max_memory
        max_tensors = sorted(max_tensors, key=(lambda x: x.size), reverse=True)
        if swapped_flag:
            swapped_flag = False
            for tensor in max_tensors:
                is_new_parameter = (tensor.is_parameter and (tensor_access_by_tensor[tensor.job_id][tensor][0].operation_name in optimizer_op) and (len(tensor_access_by_tensor[tensor.job_id][tensor]) == 1))
                if (not is_new_parameter):
                    if ((swap_out_number[tensor.job_id] <= swap_out_number_limits[tensor.job_id]) and (len(tensor_access_by_tensor[tensor.job_id][tensor]) > 1)):
                        if (tensor not in swapped_out_tensor):
                            all_access_of_tensor = tensor_access_by_tensor[tensor.job_id][tensor][1:]
                            output_access = tensor_access_by_tensor[tensor.job_id][tensor][0]
                            assert (output_access.access_type == AccessType.output)
                            if (last_input_accesses[tensor.job_id] is not None):
                                back_boundary = last_input_accesses[tensor.job_id].time
                            else:
                                last_time_access = tensor_access_by_tensor[tensor.job_id][tensor][(- 1)]
                                back_boundary = (last_time_access.time + tensor.swap_time)
                            succeed = False
                            front_boundary = output_access.time
                            swap_out_succeed = True
                            have_next_ITA = True
                            while ((not succeed) and (front_boundary < back_boundary) and swap_out_succeed and have_next_ITA):
                                swap_out_task = SwapTask(tensor, output_access.time, tensor.swap_time, TaskType.swap_out, front_boundary=front_boundary, back_boundary=back_boundary)
                                free_intervals = get_free_intervals(swap_out_task, swap_scheduler[swap_out_task.tensor.job_id], tensor_access_by_tensor[tensor.job_id][tensor])
                                selected_first_access_index = None
                                swap_out_succeed = False
                                have_next_ITA = False
                                for interval in free_intervals:
                                    if ((interval[1] - interval[0]) >= swap_out_task.time_cost):
                                        swap_out_succeed = True
                                        swap_out_task.start_time = interval[0]
                                        swap_out_task.end_time = (swap_out_task.start_time + swap_out_task.time_cost)
                                        swap_scheduler[swap_out_task.tensor.job_id].append(swap_out_task)
                                        for (i, access) in enumerate(all_access_of_tensor):
                                            if (access.start_time >= swap_out_task.end_time):
                                                have_next_ITA = True
                                                if can_next_input_access_swap_in(i, all_access_of_tensor, swap_out_task, swap_scheduler):
                                                    swapped_out_tensor.add(tensor)
                                                    swap_out_dict[tensor] = swap_out_task
                                                    swapped_in_access.add(access)
                                                    swap_out_number[tensor.job_id] += 1
                                                    selected_first_access_index = i
                                                    succeed = True
                                                    swapped_flag = True
                                                else:
                                                    swap_scheduler[swap_out_task.tensor.job_id].remove(swap_out_task)
                                                    front_boundary = access.end_time
                                                    assert (tensor not in swapped_out_tensor)
                                                break
                                        if (not succeed):
                                            if (swap_out_task in swap_scheduler[swap_out_task.tensor.job_id]):
                                                swap_scheduler[swap_out_task.tensor.job_id].remove(swap_out_task)
                                                break
                                        else:
                                            break
                            if (not succeed):
                                continue
                            if (not is_new_parameter):
                                for i in range((selected_first_access_index + 1), len(all_access_of_tensor)):
                                    access = all_access_of_tensor[i]
                                    if ((i == 0) or (access in swapped_in_access)):
                                        continue
                                    elif can_next_input_access_swap_in(i, all_access_of_tensor, swap_out_task, swap_scheduler):
                                        swapped_in_access.add(access)
                                        if (all_access_of_tensor[(i - 1)].start_time > swap_out_task.end_time):
                                            all_access_of_tensor[(i - 1)].release_flag = True
                            if swapped_flag:
                                break
                elif (tensor not in swapped_out_tensor):
                    output_access = tensor_access_by_tensor[tensor.job_id][tensor][0]
                    assert (output_access.access_type == AccessType.output)
                    swap_out_task = SwapTask(tensor, time=output_access.time, time_cost=tensor.swap_time, task_type=TaskType.swap_out, front_boundary=output_access.end_time, back_boundary=float('inf'))
                    free_intervals = get_free_intervals(swap_out_task, swap_scheduler[swap_out_task.tensor.job_id], tensor_access_by_tensor[tensor.job_id][tensor])
                    for interval in free_intervals:
                        if ((interval[1] - interval[0]) >= swap_out_task.time_cost):
                            swap_out_task.start_time = interval[0]
                            swap_out_task.end_time = (swap_out_task.start_time + swap_out_task.time_cost)
                            swap_scheduler[swap_out_task.tensor.job_id].append(swap_out_task)
                            for t in tensor.source_tensors:
                                if (t.is_parameter and (t not in swapped_in_source_tensor)):
                                    first_access = tensor_access_by_tensor[t.job_id][t][1]
                                    assert (first_access.access_type == AccessType.input)
                                    swap_in_task = SwapTask(t, first_access.time, first_access.tensor.swap_time, TaskType.swap_in, front_boundary=0, back_boundary=first_access.start_time)
                                    res = try_swap_in(swap_in_task, swap_scheduler, tensor_access_by_tensor[t.job_id][t])
                                    if res:
                                        swapped_in_source_tensor.add(t)
                                        swapped_out_tensor.add(tensor)
                                        swap_out_dict[tensor] = swap_out_task
                                        swapped_in_access.add(first_access)
                                        swap_out_number[tensor.job_id] += 1
                                        swapped_flag = True
                                    else:
                                        swap_scheduler[swap_out_task.tensor.job_id].remove(swap_out_task)
                                        assert (tensor not in swapped_out_tensor)
                                    break
                            break
        elif enable_recomputation:
            recomputation_flag = False
            if (max_memory >= total_memory):
                for job_id in job_id_ordered_by_weights:
                    max_tensors_filtered = []
                    for tensor in max_tensors:
                        if ((not tensor.is_parameter) and (tensor not in swapped_out_tensor) and (tensor.source_tensors is not None) and (len(tensor.source_tensors) > 0) and (False not in [(t not in swapped_out_tensor) for t in tensor.source_tensors]) and (False not in [(t not in recomputations) for t in tensor.source_tensors])):
                            max_tensors_filtered.append(tensor)
                    if (len(max_tensors_filtered) == 0):
                        continue
                    max_tensors_by_metric = sorted(max_tensors_filtered, key=(lambda x: x.recomputation_metric), reverse=True)
                    tensor = max_tensors_by_metric[0]
                    now_time = max_time[job_id]
                    all_access_of_tensor = tensor_access_by_tensor[tensor.job_id][tensor]
                    for (i, access) in enumerate(all_access_of_tensor):
                        if ((access.access_type == AccessType.input) and (access not in recomputations)):
                            if (access.start_time >= now_time):
                                for source_tensor in access.tensor.source_tensors:
                                    accesses = tensor_access_by_tensor[source_tensor.job_id][source_tensor]
                                    for temp_acc in accesses:
                                        if (temp_acc.release_flag and (temp_acc.end_time <= access.start_time)):
                                            break
                                    else:
                                        recomputations.append(access)
                                        all_access_of_tensor[(i - 1)].release_flag = True
                                        recomputation_flag = True
                                        recomputation_tensor.add(access.tensor)
                                    break
                            break
        iter += 1
    memory_saved_ratio = format(((1 - (last_memory_used / original_memory_used)) * 100), '.2f')
    print(f'memory_saved_ratio:{memory_saved_ratio}%')
    print(f'swap ratio:{(len(swap_scheduler[0]) / len(global_tensors))}')
    return generate_swap_recomputation_release_order(tensor_access_by_tensor, swap_scheduler, recomputations, job_num)
def generate_scheduling_plan(logged_times, gpu: int):
    global total_memory
    global global_tensors
    init(logged_times, gpu)
    tensor_nums = list(map((lambda x: len(x)), tensor_access_by_tensor))
    swap_out_number_limits = [int((weight * tensor_num)) for (weight, tensor_num) in zip(jobs_weights, tensor_nums)]
    swap_out_number = [0 for _ in tensor_nums]
    swapped_out_tensor = set()
    swapped_in_source_tensor = set()
    swap_out_dict = {}
    swapped_in_access = set()
    recomputations = []
    recomputation_tensor = set()
    swapped_flag = True
    recomputation_flag = True
    iter = 0
    original_memory_used = 0
    last_memory_used = 0
    job_id_ordered_by_weights = list(map((lambda x: x[0]), sorted([(job_id, weights) for (job_id, weights) in enumerate(jobs_weights)], key=(lambda x: x[1]), reverse=True)))
    max_memory_footprint = []
    while (swapped_flag or (recomputation_flag and enable_recomputation)):
        if (not debug_mod):
            total_memory = (nvmlDeviceGetMemoryInfo(handle).free / 1000000)
        else:
            total_memory = 6000
        (max_memory, max_tensors, last_input_accesses, max_time, time_axis) = run_global_memory_analysis(swap_scheduler, swapped_out_tensor)
        max_memory_footprint.append(max_memory)
        if ((len(max_memory_footprint) > 3) and (max([(max_memory_footprint[i] - max_memory_footprint[(i + 1)]) for i in range((len(max_memory_footprint) - 3), (len(max_memory_footprint) - 1))]) < (max_memory_footprint[(- 1)] * 0.0005)) and (iter > 100)):
            break
        if (iter == 0):
            original_memory_used = max_memory
            liveness_analysis(global_tensor_access)
        else:
            last_memory_used = max_memory
        max_tensors = sorted(max_tensors, key=(lambda x: x.size), reverse=True)
        if swapped_flag:
            swapped_flag = False
            for tensor in max_tensors:
                is_new_parameter = (tensor.is_parameter and (tensor_access_by_tensor[tensor.job_id][tensor][0].operation_name in optimizer_op) and (len(tensor_access_by_tensor[tensor.job_id][tensor]) == 1))
                if (not is_new_parameter):
                    if ((swap_out_number[tensor.job_id] <= swap_out_number_limits[tensor.job_id]) and (len(tensor_access_by_tensor[tensor.job_id][tensor]) > 1)):
                        if (tensor not in swapped_out_tensor):
                            all_access_of_tensor = tensor_access_by_tensor[tensor.job_id][tensor][1:]
                            output_access = tensor_access_by_tensor[tensor.job_id][tensor][0]
                            assert (output_access.access_type == AccessType.output)
                            if (last_input_accesses[tensor.job_id] is not None):
                                back_boundary = last_input_accesses[tensor.job_id].time
                            else:
                                last_time_access = tensor_access_by_tensor[tensor.job_id][tensor][(- 1)]
                                back_boundary = (last_time_access.time + tensor.swap_time)
                            succeed = False
                            front_boundary = output_access.time
                            swap_out_succeed = True
                            have_next_ITA = True
                            while ((not succeed) and (front_boundary < back_boundary) and swap_out_succeed and have_next_ITA):
                                swap_out_task = SwapTask(tensor, output_access.time, tensor.swap_time, TaskType.swap_out, front_boundary=front_boundary, back_boundary=back_boundary)
                                free_intervals = get_free_intervals(swap_out_task, swap_scheduler[swap_out_task.tensor.job_id], tensor_access_by_tensor[tensor.job_id][tensor])
                                selected_first_access_index = None
                                swap_out_succeed = False
                                have_next_ITA = False
                                for interval in free_intervals:
                                    if ((interval[1] - interval[0]) >= swap_out_task.time_cost):
                                        swap_out_succeed = True
                                        swap_out_task.start_time = interval[0]
                                        swap_out_task.end_time = (swap_out_task.start_time + swap_out_task.time_cost)
                                        swap_scheduler[swap_out_task.tensor.job_id].append(swap_out_task)
                                        for (i, access) in enumerate(all_access_of_tensor):
                                            if (access.start_time >= swap_out_task.end_time):
                                                have_next_ITA = True
                                                if can_next_input_access_swap_in(i, all_access_of_tensor, swap_out_task, swap_scheduler):
                                                    swapped_out_tensor.add(tensor)
                                                    swap_out_dict[tensor] = swap_out_task
                                                    swapped_in_access.add(access)
                                                    swap_out_number[tensor.job_id] += 1
                                                    selected_first_access_index = i
                                                    succeed = True
                                                    swapped_flag = True
                                                else:
                                                    swap_scheduler[swap_out_task.tensor.job_id].remove(swap_out_task)
                                                    front_boundary = access.end_time
                                                    assert (tensor not in swapped_out_tensor)
                                                break
                                        if (not succeed):
                                            if (swap_out_task in swap_scheduler[swap_out_task.tensor.job_id]):
                                                swap_scheduler[swap_out_task.tensor.job_id].remove(swap_out_task)
                                                break
                                        else:
                                            break
                            if (not succeed):
                                continue
                            if (not is_new_parameter):
                                for i in range((selected_first_access_index + 1), len(all_access_of_tensor)):
                                    access = all_access_of_tensor[i]
                                    if ((i == 0) or (access in swapped_in_access)):
                                        continue
                                    elif can_next_input_access_swap_in(i, all_access_of_tensor, swap_out_task, swap_scheduler):
                                        swapped_in_access.add(access)
                                        if (all_access_of_tensor[(i - 1)].start_time > swap_out_task.end_time):
                                            all_access_of_tensor[(i - 1)].release_flag = True
                            if swapped_flag:
                                break
                elif (tensor not in swapped_out_tensor):
                    output_access = tensor_access_by_tensor[tensor.job_id][tensor][0]
                    assert (output_access.access_type == AccessType.output)
                    swap_out_task = SwapTask(tensor, time=output_access.time, time_cost=tensor.swap_time, task_type=TaskType.swap_out, front_boundary=output_access.end_time, back_boundary=float('inf'))
                    free_intervals = get_free_intervals(swap_out_task, swap_scheduler[swap_out_task.tensor.job_id], tensor_access_by_tensor[tensor.job_id][tensor])
                    for interval in free_intervals:
                        if ((interval[1] - interval[0]) >= swap_out_task.time_cost):
                            swap_out_task.start_time = interval[0]
                            swap_out_task.end_time = (swap_out_task.start_time + swap_out_task.time_cost)
                            swap_scheduler[swap_out_task.tensor.job_id].append(swap_out_task)
                            for t in tensor.source_tensors:
                                if (t.is_parameter and (t not in swapped_in_source_tensor)):
                                    first_access = tensor_access_by_tensor[t.job_id][t][1]
                                    assert (first_access.access_type == AccessType.input)
                                    swap_in_task = SwapTask(t, first_access.time, first_access.tensor.swap_time, TaskType.swap_in, front_boundary=0, back_boundary=first_access.start_time)
                                    res = try_swap_in(swap_in_task, swap_scheduler, tensor_access_by_tensor[t.job_id][t])
                                    if res:
                                        swapped_in_source_tensor.add(t)
                                        swapped_out_tensor.add(tensor)
                                        swap_out_dict[tensor] = swap_out_task
                                        swapped_in_access.add(first_access)
                                        swap_out_number[tensor.job_id] += 1
                                        swapped_flag = True
                                    else:
                                        swap_scheduler[swap_out_task.tensor.job_id].remove(swap_out_task)
                                        assert (tensor not in swapped_out_tensor)
                                    break
                            break
        elif enable_recomputation:
            recomputation_flag = False
            if (max_memory >= total_memory):
                for job_id in job_id_ordered_by_weights:
                    max_tensors_filtered = []
                    for tensor in max_tensors:
                        if ((not tensor.is_parameter) and (tensor not in swapped_out_tensor) and (tensor.source_tensors is not None) and (len(tensor.source_tensors) > 0) and (False not in [(t not in swapped_out_tensor) for t in tensor.source_tensors]) and (False not in [(t not in recomputations) for t in tensor.source_tensors])):
                            max_tensors_filtered.append(tensor)
                    if (len(max_tensors_filtered) == 0):
                        continue
                    max_tensors_by_metric = sorted(max_tensors_filtered, key=(lambda x: x.recomputation_metric), reverse=True)
                    tensor = max_tensors_by_metric[0]
                    now_time = max_time[job_id]
                    all_access_of_tensor = tensor_access_by_tensor[tensor.job_id][tensor]
                    for (i, access) in enumerate(all_access_of_tensor):
                        if ((access.access_type == AccessType.input) and (access not in recomputations)):
                            if (access.start_time >= now_time):
                                for source_tensor in access.tensor.source_tensors:
                                    accesses = tensor_access_by_tensor[source_tensor.job_id][source_tensor]
                                    for temp_acc in accesses:
                                        if (temp_acc.release_flag and (temp_acc.end_time <= access.start_time)):
                                            break
                                    else:
                                        recomputations.append(access)
                                        all_access_of_tensor[(i - 1)].release_flag = True
                                        recomputation_flag = True
                                        recomputation_tensor.add(access.tensor)
                                    break
                            break
        iter += 1
    memory_saved_ratio = format(((1 - (last_memory_used / original_memory_used)) * 100), '.2f')
    print(f'memory_saved_ratio:{memory_saved_ratio}%')
    print(f'swap ratio:{(len(swap_scheduler[0]) / len(global_tensors))}')
    return generate_swap_recomputation_release_order(tensor_access_by_tensor, swap_scheduler, recomputations, job_num)