Sort Agents to improve message memory access pattern

[ptheywood]

Other than brute-force messaging, messages are sorted during post-processing (i.e. PBM construction for spatial, but this applies to bucket and array messaging too).

When agents access these messages, performance is greatly improved if neighbouring agents (in terms of thread / memory) access the same / neighbouring messages to one another. This can be achieved by sorting agents to suit their message access pattern.

Sorting has a cost, but at least in some cases this is far outweighed by the benefits from message access pattern.

Doing this automatically may be a challenge, as in non-trivial models there may be excessive sorting of agents which may harm performance rather than help.

There are a large number of things to consider

• Should / could this be automatic without harming performance?
  • Otherwise can we make it simple to opt in / out?
  • Or will we have to leave it up to the user (and potentially just provide a simple way for users to achieve this)
• Can we find a heuristic to track which will inform the simulation on how frequently to perform the sort?
  • In the spatial case, if agents do not move then sorting once will be all that is required. If agents move between bins quickly then more frequent sorting will be worthwhile.
• In models where agents output several types of message, we might not want agents to be sorted several times per iteration, flip-flopping between two orderings
• Can we leverage an existing sort to make this efficient? Can we leverage an existing sort to provide heuristics?
• ...

[ptheywood]

Short term solution: Sort on output every N iterations, where N is a parameter somewhere.

Longer term: more thoroguh investigation, fancier decision.