Priority Queues

[krosenfeld-IDM]

From Open Design Questions

Jonathan did an investigation as to whether priority queues made sense for things like vaccination. He concluded that the perf didn't pencil out. Chris still interested in doing his own investigation.

from @jonathanhhb

[krosenfeld-IDM]

From @KevinMcCarthyAtIDM

I don't have a strong opinion - this seems to me to be more of a "specific model" question rather than a "core framework" question. That is, they may be the most performant/interpretable option for simulations with a certain population or time scale, or for certain processes within a simulation. They make a lot of intuitive sense. But it may be that a different implementation may be necessary at other scales or for other processes in a model. So I think worth looking at "what does this look like for a northern Nigeria model, does it perform well for that?" and if so, we implement it within the "demographic step" functions for that model, in a way that could be replaced for a different model with different needs.

[krosenfeld-IDM]

@clorton 's implementation (fixed length, array-based priority queue) was quite different than earlier implementations I had seen. I did some comparisons in different languages and implementations here.

Referencing @jonathanhhb 's implementation of RI using a priority queue/task sorter here using heapq.push()

https://github.com/jonathanhhb/laser/blob/55514eb93501b4970c816c8b3a15cc25a01037ad/sql_modeling/src/sir_sql.py#L152-L168

[jonathanhhb]

Given some of the progress we've seen in how fast we just iterate over large arrays quickly with parallelization and/or C, I'm less interested in priority queues or specialized containers for accessing (sorted) subsets of the population. That said, there could still be some valid use cases where they perform better. The 2 that I've heard proposed are:

1. Natural Mortality
2. RI

On mortality, which has its own discussion, I'm of the view that everyone should have a predetermined 'dod' or expected_life_span and we use that to filter "dead people" out of transmission operations, and that we don't need to do much more than that. Which leaves us with...

For RI, if we need high fidelity in terms of who and when folks are getting "intervened", it could make sense to stuff newborns in a queue by age and then process them in order, and stuff them in a "second dose RI queue", etc.

I should add that it's my understanding that we've coalesced around keeping all agents sorted in age order (where we have ages) so it can be pretty easy to find people of the right age or even keep an index to the "oldest agent considered for RI". But when keeping track of "once vaxxed" it might be easier and faster to use a queue rather than a flag and a second index.

It might all come down to how fast we can enque and deque vs for-loop.

[KevinMcCarthyAtIDM]

@jonathanhhb - if we are actually migrating people from node to node, does that mess with keeping them in age order? I guess not if we don't care about being in "node order". But I guess stated another way - it's easy to keep an array sorted by one property, especially one like age that only goes one direction; seems it could get trickier if we want to keep two things ordered, e.g., order by node for easy within-node operations; then within node, keep ordered by age for easy targeting. Are there any situations where we might want to do that? Or where might need to explore tradeoffs - "node order" enables this performance improvement, "age order" enables that one, ...
That's a more general question - for a specific implementation of a model, I think enforcing age order to enable highly performing RI makes sense.

[krosenfeld-IDM]

I think priority queues could also be helpful in general for adding complexity to interventions. RI with age distribution was one example but maybe also other interventions like multi-day SIAs, etc...

[krosenfeld-IDM]

@jonathanhhb - just to make sure I understand could you clarify (or point me to notes) about where the progress for iterating over arrays quickly 🚀 is coming from? Is this OpenMP (using shared memory + lots of cores) or something else? Thanks!