Africa-Press – Cameroun. En informatique, on décerne des prix à des articles fondateurs. Ainsi en 2024, un article daté de 1994 a été primé. Il était intitulé « Balanced allocations » (répartition de charges). Le problème consiste à répartir des balles entre des boîtes pour éviter que certaines ne soient surchargées tandis que d’autres sont presque vides.
Approche classique: si vous placez n boules dans n boîtes au hasard une par une, en moyenne chaque boîte contient une boule, mais le hasard peut faire que certaines en aient davantage. La plus remplie en a environ ln(n)/ln(ln(n)) (ce qui fait entre 6 et 7, si n vaut 1 milliard). Si les boules sont des tâches et les boîtes des processeurs pour les exécuter, il faut donc prévoir des « salles d’attente » suffisamment grandes.
Des « salles d’attente » plus petites
Nouveauté de l’article primé: chaque boule, à son arrivée dans le système, examine le contenu de deux boîtes choisies au hasard et va se mettre dans la moins remplie des deux. Là encore, en moyenne chaque boîte contient une boule, mais cette fois-ci la plus remplie n’en a qu’environ ln(ln(n))/ln(2): entre 4 et 5, si n vaut 1 milliard. Cela permet donc de construire des « salles d’attente » plus petites.
Asymptotiquement, la différence est énorme et l’article a également surpris par la simplicité de la méthode algorithmique. C’est en étant prêt à penser en dehors des clous qu’on fait de la recherche non incrémentale !
Par Claire Mathieu, directrice de recherche au CNRS, Institut de recherche en informatique fondamentale (CNRS/université Paris Cité).
Algorithme
Pour plus d’informations et d’analyses sur la Cameroun, suivez Africa-Press
