LIHPC-Computational-Geometry / coupe

the concurrent partitioner
https://LIHPC-Computational-Geometry.github.io/coupe/
Apache License 2.0
12 stars 3 forks source link

Targetor: an algorithm for multi-criteria load balancing #297

Open SMoraisDev opened 1 year ago

SMoraisDev commented 1 year ago

This PR provides a new algorithm that can be used to optimize a partition where the instance has multiple criteria.

The idea of the algorithm is to optimize the partition by achieving the best possible movement or a movement close to it. To do this, the space of weights is discretised into boxes and each weight is associated with a box. The algorithm is iterative, and at each iteration it will determine the best move to make, search the associated box and, if there are no valid moves associated with the box's weight, it will explore nearby boxes, moving further and further away.

Currently, the space of weights is discretised in a regular manner according to values supplied by the user (cf. struct RegularBoxHandler). Other structures can be considered as long as they implement the BoxHandler trait.

The approach to exploring neighbor boxes is based on a progressively increasing neighborhood (see struct NeighborSearchStrat). Other structures can be considered as long as they implement the SearchStrat trait.

SMoraisDev commented 1 year ago

Btw, current struct name is TargetorWIP, i'll modify it into Targetor (or whatever other name) once this is no more a draft.

SebastienMorais commented 1 year ago

The current implementation does not handle constant weight (discretizing the weight space between val and val results in None values)