Comment multi-threading ce scénario de problème?

Question

Je voudrais faire une simulation d'un système distribué, dans lequel, je devrais faire une recherche d'information (fournitures) d'une manière distribuée (parallèle si je pourrais !!), par exemple j'ai la classe suivante:

Il y a plusieurs groupes, chacun a un nom et se compose d'une liste de membres, de voisins et de fournitures, chaque membre a des informations et répertorie d'autres groupes pouvant contenir des informations et des fournitures pertinentes, etc. Je veux faire une recherche pour les fournitures, Premièrement: à l'intérieur d'un groupe, si je ne trouve pas l'offre requise, je devrais faire une recherche dans tous les groupes qui sont voisins de ce groupe, je pense faire en utilisant Multi-threading, je veux dire, si la recherche a échoué, je devrais faire une recherche dans tous les autres voisins en même temps en utilisant plusieurs threads, chacun prenant en considération un voisin, Si j'ai 10 voisins puis 10 threads devraient être 2- Maintenant, si je veux commencer la re-recherche avec plusieurs groupes, je veux commencer par 3 ou 4 groupes ou plus, chacun cherche un approvisionnement différent, ou le même .... + un groupe qui invoquent la recherche pourrait être un voisin pour un autre groupe ...

Donc, ma question est Comment réaliser ce scénario en utilisant des threads?

PS.I ont une machine avec un seul processeur avec un noyau, et je ne se soucient pas d'un temps d'exécution (les frais généraux), tout ce que je veux est de simuler ce problème ...

Merci pour chaque réponse, et meilleures salutations.

Answer 1

Étant donné que vous avez un problème lié à la CPU, le nombre optimal de threads à utiliser est probablement le nombre de cœurs que vous avez. Je voudrais m'assurer que chaque fil a environ 100 micro-secondes de travail ou vous pourriez trouver que vous avez plus de tête que de travail utile. par exemple. vous pourriez trouver que la recherche de nœuds 10K est d'environ 100 nous travail. Si vous ne faites pas attention, une application multithread peut être plusieurs fois plus lente qu'une seule thread.

Donc, je trouverais un moyen de diviser le travail de sorte que vous avez environ 1K à 100K nœuds pour chaque thread et limiter votre concurrence au nombre de core que vous avez.

Answer 2

Je ne pouvais pas comprendre la deuxième exigence, mais pour le premier, voici une approche possible. Avant cela cependant, techniquement, votre processus n'est pas complètement lié au CPU, il est également lié aux E/S (réseau). Donc, s'il vous plaît, ne supposez pas que le fait de le rendre muti-thread fournira l'accélération requise que vous recherchez. Je suppose que votre environnement de développement est monoprocesseur et monotone, mais votre environnement de déploiement peut ne pas l'être.

Retour à la suggestion. Je voudrais créer une classe GroupPool qui a un pool de threads qui peuvent aller chercher des informations. Le nombre de threads sera configurable via un paramètre de configuration d'exécution. Vous pouvez créer une classe de fabrique qui lit ce paramètre à partir d'un fichier de configuration et crée un pool d'objets exécutables.

Chacun de ces objets représente une connexion au noeud voisin. [TODO] Vous n'avez pas mentionné si vous souhaitez recurder sur les nœuds fournisseurs, c'est-à-dire si vous ne trouvez pas l'information dans un nœud fournisseur, voulez-vous rechercher le fournisseur, les fournisseurs du fournisseur, etc. Si oui, vous allez avoir le problème de la détection de cycle.Une fois que ces objets thread recherchent des informations et les trouvent, ils mettent à jour un sémaphore sur l'objet de fabrique (vous pouvez déplacer ce dernier vers un objet séparé car la conception sera meilleure), et envoient également l'identifiant du fournisseur (voir objet a du sens)

Vous pouvez avoir un écouteur pour ce sémaphore modifié et dès que la valeur change, vous savez que vous avez trouvé vos informations et que vous obtenez l'identifiant fournisseur de cet objet. Une fois que vous obtenez vos informations, vous pouvez envoyer une notification au pool d'unités d'exécution pour arrêter les objets exécutables lorsque vous avez déjà trouvé vos informations. En fonction de si vous recherchez une réponse binaire (trouver des données et tout fournisseur est ok) et si vous voulez recurse, la complexité de ce qui précède va augmenter.

Espérons que cela vous aide à essayer de concevoir la structure de votre problème.

Answer 3

Je ne vois aucun avantage de performance à multi-threader cela sur une seule machine CPU. C'est parce que seulement 1 thread sera capable de fonctionner à la fois et qu'il y aura du temps de commutation entre threads, donc il faudra probablement plus de temps pour trouver un groupe avec la ressource désirée. Personnellement, je voudrais simplement parcourir les voisins du premier groupe et vérifier les ressources. Ensuite, si les ressources n'étaient pas trouvées, j'appelais la recherche sur chacun des sous-groupes, en passant dans la liste des groupes déjà vérifiés, afin de pouvoir ignorer les groupes qui ont déjà été vérifiés. Quelque chose comme:

public Group searchForGroupWithResource(Resource resource){ 
    List<Group> groupsToCheck = new ArrayList<Group>(); 
    groupsToCheck.add(this); 
    int currentIndex = 0; 
    while(currentIndex < groupsToCheck.size()){ 
     Group currentGroup = groupsToCheck.get(currentIndex); 
     if(currentGroup.hasResource(resource)){ 
      return currentGroup; 
     } 
     groupsToCheck.addAll(currentGroup.getNeighbors(groupsToCheck)); 
     currentIndex++; 
    } 
    return null; 
} 

public List<Group> getNeighbors(List<Group> excludeGroups){ 
    //Get non-excluded neighbors 
    List<Group> returnNeighbors = new ArrayList<Group>(); 
    for(Group neighbor : neighbors){ 
     boolean includeGroup = true; 
     for(Group excludeGroup : excludeGroups){ 
      if(excludeGroup.equals(neighbor)){ 
       includeGroup = false; 
       break; 
      } 
     } 
     if(includeGroup){ 
      returnNeighbors.add(neighbor); 
     } 
    } 
    return returnNeighbors; 
} 

Note: Si vous décidez encore d'aller pour le multi-threading, je suggère un objet commun qui stocke des informations sur la recherche qui est accessible à tous les threads. Cela permet de spécifier les groupes qui ont été cochés (donc vous ne vérifiez pas deux fois le même groupe) et si les fournitures requises ont été trouvées (vous pouvez donc arrêter de vérifier les ressources).