Could we use a heap here ? instead of sorting on each iteration. for elements which are changed you can remove and reinsert

I actually thought about using a heap here but

• live_memory is updating from iteration to iteration,
• node.mpi_node.memory_to_free could be changing from iteration to iteration since how much memory can be freed after scheduling a node depends on what nodes have already scheduled.

So if we were to use a heap, elements in the heap would need to be updated from iteration to iteration and it is not efficient to do so.

I guess the reason this isn't as bad is because it's O(n) * O(max_concurrently_schedulable_nodes).

But, just to discuss - the live memory is the same for every node. If live_memory + node.mpi_node.size < max_memory, does it actually matter what we schedule ? I'm not sure we need the max here: max(live_memory + node.mpi_node.size, max_memory).

I think you could conceivably avoid updating the live memory and just update the memory_to_free ? anyways not needed but thinking aloud.

I guess the reason this isn't as bad is because it's O(n) * O(max_concurrently_schedulable_nodes).

But, just to discuss - the live memory is the same for every node. If live_memory + node.mpi_node.size < max_memory, does it actually matter what we schedule ? I'm not sure we need the max here: max(live_memory + node.mpi_node.size, max_memory).

I think you could conceivably avoid updating the live memory and just update the memory_to_free ? anyways not needed but thinking aloud.

Surprising to me that the greedy algorithm is not to order by net change in memory.. This will choose the largest node that is below max memory.. then net difference.. would assume it would just order by net difference.

I guess the reason this isn't as bad is because it's O(n) * O(max_concurrently_schedulable_nodes).

yes!!

If live_memory + node.mpi_node.size < max_memory, does it actually matter what we schedule?

In this case, whichever you schedule would not affect the peak memory immediately at the current step, but can have an effect on later steps.

I'm not sure we need the max here: max(live_memory + node.mpi_node.size, max_memory).

The algorithm (given in the paper) selects the next node to schedule based on two numbers for every node:

(1) memory after output allocation, call it mem1, which is live_memory + node.mpi_node.size;
(2) memory after the node is executed and its last used buffers are freed, call it mem2.

Among all nodes whose mem1 is below max_memory, it selects the node with the lowest mem2; and if such nodes do not exist, it selects the node with lowest mem1.

The first element in the tuple -- max(live_memory + node.mpi_node.size, max_memory) -- is evaluated to be max_memory for all nodes whose mem1 is below max_memory. For tiebreaking, we then use the second element in the tuple, which is effectively mem2:

mem2 is live_memory + node.mpi_node.size - node.mpi_node.memory_to_free. Since live_memory is the same for all nodes, we simply use node.mpi_node.size - node.mpi_node.memory_to_free for comparison.

Hope this makes sense.

I think you could conceivably avoid updating the live memory and just update the memory_to_free ? anyways not needed but thinking aloud.

Does the explanation above help with this?