Fork-Join développement en Java ™ SE

Original: http://www.coopsoft.com/ar/ForkJoinArticle.html


Fork-inscrire tous les jours, multi-core des applications Java ™

Bifurquer ou de diviser la charge de travail en tâches multiples pour le traitement parallèle et de rejoindre les résultats ensemble est une technique utilisée dans d’innombrables calculs, le nombre des applications scientifiques. Beaucoup d’autres applications pourraient bénéficier d’un traitement de fourche rejoindre mais en utilisant l’approche scientifique peut-être pas dans leur meilleur intérêt.

Cet article présente une “embarrassante parallèle” fourche rejoindre approche qui fonctionne bien pour les applications de tous les jours, multi-core en Java ™ SE, ME, ainsi que Android. ™ (3000 mots)


Edward Harned (eh at coopsoft dot com)
Développeur Senior Software Systems coopératives, Inc.
Février 2010 [mise à jour Juin 2013]


Quel est Fork-Join?

Pensez à une bifurcation de la route où chaque chemin vient finalement de retour ensemble – jointures.

Fork-Join pauses une application en plusieurs parties pour le traitement parallèle et rejoint les résultats à la fin.


Figure 1: Fork-Join Structure

Fork-Join Structure

Disons que nous avons un tableau de mille numéros. Nous devons faire une procédure sur chacun de ces numéros et les additionner.

  Liste 1: Traitement Array


for (int i = 0; i < 1000; i++) {
total += doProcedure(array[i]);
}


Si la procédure prend une seconde (temps horloge murale) pour terminer, il va prendre un millier de secondes (plus de 16½ minutes) pour effectuer cette tâche.

Fork-Join pourrait

  •         séparée (fourchette) le grand tableau en dix tableaux de cent éléments chacun,
  •         traite chaque tableau sur une CPU séparée, et
  •         rejoindre les résultats lorsque vous avez terminé.


Ce serait prendre une centaine de secondes (un peu plus de 1½ minutes), un dixième du temps d’origine. Disponible, plus le résultat de la plus CPU.

Ceci est ce que le calcul scientifique est tout au sujet – traiter simultanément les montants faramineux de données en tant que de nombreux CPU disponibles. Cette abstraction ressemble étroitement au modèle scientifique norme de Divide-and-Conquer.

Diviser pour régner est un paradigme naturel pour algorithmes parallèles. Après avoir divisé un problème en deux ou plusieurs sous-problèmes, le procédé permet de résoudre les problèmes de sous-parallèle. Typiquement, les sous-problèmes sont résolus de manière récursive et donc l’étape suivante de fracture des rendements encore plus sous-problèmes pour résoudre en parallèle.


   
Figure 2: Divide-and-Conquer

Divide and Conquer

 


    
Problèmes d’utilisation de chariots Rejoignez modèle scientifique pour les applications quotidiennes

Création de tâches est pas le problème; ce ne sont que des objets. Le problème est un nombre élevé de threads de traitement des tâches lorsque ces tâches doivent:


     
Les liaisons
Accès à des services distants (SGBD, messagerie, et bien d’autres) nécessite une connexion au service distant. Généralement, les services à distance utilisent un thread pour gérer la connexion et qui exige que la mémoire, le changement de contexte, la synchronisation et la coordination. Les plus de connexions au service, plus les ressources du service a besoin, et les moins de connexions disponibles pour d’autres tâches dans la JVM. Cela affecte chaque utilisateur.

        Serrures
Les verrous sont un tueur à la haute performance. Serrures morts / vivants, l’inversion de priorité, la famine, convoyage et les frais généraux (qui monte de façon exponentielle avec la longueur de la liste des tâches en attente) sont quelques-uns des problèmes de l’utilisation de serrures.

 Sémaphores
Les plus de threads qui veulent un permis en même temps, plus les fils qui doivent attendre la disponibilité de permis. Cela nous ramène à tous les problèmes de l’utilisation de serrures.

   La cohérence du cache
Lorsque plusieurs processeurs accès / jour la même variable à l’intérieur d’une ligne de cache, (bloc de données copiées à partir de la mémoire principale contenant de nombreux domaines), l’unité de mémoire peut invalider la ligne de cache. Qui non seulement ralentit une application, il peut affecter d’autres applications ainsi.

  Mémoire étendue
Les plusieurs objets ou plus les objets, plus la mémoire. Les discussions les plus actifs de manutention des tâches, alors le plus de mémoire en cours d’utilisation. Naturellement, il en résulte que de grandes tâches de mémoire doivent étranglement.

   La nécessité de jouer gentil
Vous êtes l’application peut ne pas être la seule application en cours d’exécution sur l’ordinateur. Quand on demande monopolise les ressources, tout le monde ressent la douleur. Jouer agréable avec d’autres revient à ce que nous avons tous appris dans l’enfance. La même chose est vraie quand le développement de logiciels qui ne fonctionne pas comme une application autonome.


Le thème du développement multi-core est de garder contention, les tâches en compétition pour les mêmes ressources, à un minimum.

Si le paradigme de décomposition dynamique de Divide-and-Conquer convient à vos besoins, alors lisez cet article sur la version du DSE haute performance de Tymeac. Sinon, un cadre Bifurquer fonctionnelle peut mieux répondre à vos besoins.

    Fonctionnelle cadre Bifurquer

Java ™ SE / ME applications multi-core ainsi que les applications Android ™ qui ne peuvent pas utiliser le modèle Divide-and-Conquer, ne pas traiter les grands tableaux de nombres, ou ne pas avoir une structure de calcul intensif besoin d’un cadre de bifurcation fonctionnelle pour les applications de parallélisation . Plus précisément, ils doivent débourser le travail en ses composants fonctionnels plutôt que de décomposer un tableau en sous-tâches identiques.

    Figure 3: fonctionnelle cadre Bifurquer

Functional Forking Framework

 

Un cadre de bifurcation fonctionnelle possède deux attributs essentiels. Il doit:

  •         Limitez affirmation.
  •         Être simple à utiliser ou embarrassante parallèle.


        
Limite Contention

Garder le nombre de threads actifs, en compétition à un minimum absolu est primordiale. La meilleure façon de limiter conflit de thread est d’utiliser des seuils pour chaque pool de threads entretien une file d’attente de tâches. Voir cet article sur la haute performance files d’attente prioritaires dans Java SE pour un exemple de la façon dont l’aide de listes d’attente peuvent conserver les ressources de filetage.

Réutilisation des ressources plutôt que d’acquérir de nouvelles copies des ressources est un gagnant tout autour. Nous devons tenir compte non seulement le code de la tâche, mais le code de gestion des ressources ainsi.

Prenons l’exemple d’une tâche besoin d’accéder à une base qui nécessite une [java.sql.] Déclaration. En utilisant une file d’attente de demandes, le code de tâche peut partager la même déclaration pour de nombreux accès plutôt que l’acquisition d’une nouvelle déclaration pour chaque accès. Partage d’une déclaration est une économie énorme en lice frais généraux et les limites dans le code de gestion.

        Ce qui est embarrassant parallèle?

Embarrassant algorithmes parallèles sont ceux qui peuvent résoudre de nombreuses tâches similaires mais indépendants simultanément avec peu ou pas de nécessité d’une coordination entre les tâches. Ces types de problèmes ont une telle parallélisation facile que l’on est presque “gêné” de parler de comment il est simple d’obtenir de nombreux processeurs travaillant efficacement.

Une solution embarrassante parallèle peut facilement fourchette dans un certain nombre de composants totalement indépendants, chacun exécutant sur un processeur séparé.

            Figure 4: Embarrassant parallèle

Embarrassingly Parallel

     
     
Par example:
Une entreprise peut avoir besoin d’un système de prix de devis automatisé. Pour développer un devis, le système a besoin de prix de l’article de base (base de données de prix), la réduction de la clientèle pour les articles et les frais d’expédition (base de données du client), et les coûts d’expédition de base (base de données de l’expéditeur.)

Traditionnellement, le programme accède à chaque base de données en série, en attendant que chaque accès à terminer avant de passer à la prochaine visite.

Dans un système parallèle, les fourchettes de programme () la demande en trois files d’attente, chacune desservie par un pool de threads, attend jusqu’à ce que les dernières finitions d’accès et rejoint () les résultats ensemble.

            Figure 5: Demande de prix


Le prix citation ci-dessus est un exemple d’une requête synchrone, où l’appelant attend pour l’achèvement. Il ya seulement un petit pas en avant pour ajouter le support pour la demande asynchrone ou autonome, où l’appelant ne pas attendre l’achèvement.

Il ya beaucoup, beaucoup de situations où bifurquer le travail en ses composants est souhaitable:

  •         Prenez une application de jeu où nous pouvons débourser un événement en composants séparés. L’avantage ici est l’excitation; les segments plus d’événements qui se déroulent en même temps, le plus intéressant du jeu.
  •         Prenez une application avec de multiples animations où nous pouvons Fork chaque animation pour fonctionner sur son propre processeur.
  •         Prenez une opération de traitement d’image où chaque pixel d’une image doit avoir sa couleur inversée. Le cadre peut facilement distribuer des données d’image à des tâches multiples qui peuvent fonctionner indépendamment l’un de l’autre.
  •         Prenez une institution financière où re-valorisation d’un portefeuille implique composants qui communiquent avec les différents marchés à travers le monde.
  •         Prenez une demande de soins de santé où les différents tests sont des composants à un diagnostic.


Il est un effort pour voir à ce que l’application ne peut pas utiliser la parallélisation d’un cadre de bifurcation fonctionnelle.

    Comment ce cadre serait regarder dans une application Java ™?

Un cadre pour bifurquer la demande en ses composants fonctionnels doit:

Connaître les composants (files d’attente) pour chaque opération de demande (Fonction). Une classe simple contenant un nom de fonction de chaîne et une liste des files d’attente est associée base Java ™ programmation.

     Liste 2: Fonction Classe

public class Function {

      private String    name; // Function name
      private Queue[] que;   // Queues for this Function
}

Placez la demande (contenant les objets d’entrée) dans chacun des files d’attente de renvoyer un tableau de l’objet à l’appelant ou en ignorant les objets retournés.

    Liste 3: Mettre en file d’attente

public Object[] fork(Queue[] que, Object request) {

      Object[] return_obj = new Object[] {null, null, null};

      for (int i = 0; i < que.length; i++) {
putInQueue(que[i], return_obj [i], request);
}

       return return_obj;
}


Attendre la fin / timeout ou ne pas attendre.

     Listing 4: Attendre / Nowait


public boolean join(Object[] obj) {

    /* when all elements are non-null, return true
* wait for a while
* after an interval, return false
*/

}


Renvoyer les résultats à l’appelant ou d’ignorer les objets

        Figure 6: Retour à l’appelant

Return Object[]

    Pour construire ce cadre nous ferions:

  1.         Besoin de maintenir le code de tâche réelle qui fait le travail
  2.         Besoin de maintenir une liste de files d’attente et fonctions
  3.         Besoin de maintenir une classe “start up” qui charge les files d’attente et des fonctions en mémoire


(1) Le code qui fait le travail devrait ressembler à ceci:

            Liste 5: Code du Travail


public static Object main(Object obj) {}

Un principale méthode () qui accepte un objet (l’entrée de l’appelant) et retourne un objet (le résultat du travail.)

(2) Nous pourrions maintenir les files d’attente et des fonctions comme des objets dans une liste simple classe.

(3) Lancez pourrait simplement charger les classes de listes dans la mémoire avec un nouveau (liste des classes) et commencer les discussions pour chaque file d’attente.

Comment un simple appel pourrait ressembler:

      Listing 6: Appel Simple

    Framework fw = new Framework();

    // For each call:
Function
func = fw.getFunction(name);
Object[] back =
func.fork(request};

Ce cadre est simple à utiliser, embarrassant simple.

    Récapitulatif

Jusqu’à présent, nous avons vu comment bifurquer une demande en ses composants fonctionnels peut fonctionner comme une partie intégrée d’une seule application (dans la même JVM.) Pour être pratique, nous avons aussi besoin de rendre le cadre accessible à partir de la JVM de l’autre. Simplement, il doit prendre en charge de nombreux appels d’utilisateurs simultanément comme un serveur.

    Ce qui en fait un serveur

Quels changements faut-il faire pour forger ce cadre simple en un serveur?

  1.         Nous devons séparer l’appelant du travail.
  2.         Nous devons fournir une récupération d’erreur.
  3.         Nous devons soutenir le cadre comme un objet distant.
  4.         Nous devons assurer la sécurité.
  5.         Nous devons fournir des fonctionnalités d’administration pour contrôler le serveur.

        Séparation
Le premier changement est de séparer la demande courtage (ce qui est la méthode la fourchette ci-dessus ()) de la transformation réelle. Nous devons séparer, mais garder une trace de chaque demande dans un objet unique.

    Liste 7: Objet Requête
private long              unique_id; // unique identification of this request
  private Object           input; // input reference, if any
  private boolean         type; // type of request true=sync false=async
  private Object[]         output // the output objects from the tasks
  private AtomicInteger next_output; // subscript to add an element to above
  private Queue[]         que_names; // list of all the queues in this function
  private Queue            agent; // future queue, if used
  private AtomicInteger nbr_remaining; // queues remaining to be processed
  private int                wait_time; // max wait time for sync request

Quel est le champ «agent?”

       Agent
Une requête synchrone retourne le tableau de l’objet de la transformation à l’appelant. Qu’est-ce que le cadre devrait faire avec le tableau d’objets de rentrer d’une demande asynchrone? Le cadre peut éventuellement mettre le tableau d’objets (comme une entrée) dans une nouvelle file d’attente pour le traitement par une tâche de l’agent. De cette façon, la tâche de l’agent peut prendre des mesures sur la base de l’état d’achèvement de l’opération de transformation préalable.

  Par example:
Une fonction est de générer un devis et l’envoyer à un utilisateur comme une demande asynchrone.

  1.                     L’appelant utilise la méthode de fourche asynchrone ().
  2.                     Les cadres fourches la demande dans ses files d’attente respectives.
  3.                     Lorsque la dernière file d’attente se termine, le cadre passe l’objet tableau retourné à la tâche de l’agent en mettant la demande dans la file d’attente spécifiée comme «agent».
  4.                     La tâche de l’agent envoie l’e-mail ne rien renvoyer.


       
Reprise sur erreur
Le deuxième changement est l’ajout de reprise sur erreur, la marque de professionnalisme.

Qu’est-ce qui peut aller mal ici? “Tout ce qui peut aller mal ira mal.” Murphy’s Law.

         Retour sur
Nous pourrions avoir une erreur de bifurquer. Une file d’attente bornée pourrait être plein ou la file d’attente peut être désactivé (voir ci-après.) La récupération d’erreur doit sauvegarder toutes les files d’attente que fourchue succès et d’informer l’appelant de la problème. Par example:

  •                 Nous avons trois files d’attente (A, B, C) dans la fonction.
  •                 Files d’attente A et B reçoivent avec succès la demande.
  •                 Queue C ne reçoit pas la demande parce que la file d’attente est pleine.
  •                 Maintenant nous revenir en arrière essayant de tirer la demande de toutes les files d’attente que fourchue avec succès afin que nous puissions gagner du temps de traitement pour les demandes défectueuses.


            
Exception / Erreur
Nous pourrions avoir une exception / erreur dans le code de la tâche réelle qui fait le travail. Si elle a échoué une fois, il ne sera probablement échouer à nouveau. Par conséquent, il est souhaitable de désactiver la file d’attente jusqu’à ce qu’un développeur résout le problème. Lorsque le code de la tâche est propre, nous ne voulons pas prendre le serveur. Nous voulons informer le serveur que nous avons une nouvelle copie du code de la tâche qui est propre et nous voulons que la file d’attente activée.

Stalle
Nous pourrions avoir le dessus de se produire dans une requête asynchrone, appelé un décrochage (requêtes synchrones temps et peut purger du système.) Depuis fonctions ne peuvent pas complète jusqu’à ce que toutes les files d’attente finir, nous devons placer les demandes bloquées dans une liste Bloqué. Lorsque la file d’attente est à nouveau utilisable, nous pouvons re-lancer le traitement de la liste de l’impasse.

.
Radiant est un sujet en soi et nécessite fil confinement. Cet article introduit le sujet: Gestion des discussions en Java SE

    Dilemme de filetage
Nous pourrions avoir un bloc de filetage à jamais sur une ressource externe ou aller dans une boucle sans fin. De toute façon, en chronométrant les événements dans la vie d’un fil, le cadre peut reconnaître cette situation et pourra radier le fil en le remplaçant par un nouveau thread.

Annulation
Nous pourrions avoir un appelant veut annuler une demande déjà présentée. Le annuler est similaire à une erreur de délai d’attente, mais il est applicable à la fois aux demandes synchrones et asynchrones. Bien que l’annulation d’une demande est la plus souhaitable, la logique de traitement d’une annulation dans une requête multi-composant est pas pour les faibles de cœur.

Suivi
Le timing est inutile, sauf si un thread démon surveille les épreuves chronométrées à la recherche de problèmes réels ou potentiels.

Notification
Pas de cadre peut gérer toutes les situations; l’intervention humaine est parfois nécessaire. Nous devons avertir les administrateurs en envoyant un message par tous les moyens les utilisations d’organisation (messagerie instantanée, e-mail, ou toute autre méthode de chez nous.)

  Objet distant
Le troisième changement est en soutenant le cadre comme un objet à distance avec l’option activation / désactivation de préserver les ressources.

Remote Method Invocation vient en plusieurs saveurs:
De base
Socket personnalisée en usine
IIOP
Portable Object Adapter
Jini
Inter Process Communication

Votre environnement peut être constitué d’un nuage avec processeurs séparés à de nombreux endroits différents. Rendre le cadre souple est parfaitement logique.

Sécurité
Le quatrième changement est l’ajout de la sécurité.

La technologie de sécurité Java ™ fait partie de la SE / Me plates-formes, il faut avant fin le serveur avec des classes de sécurité pour plus de flexibilité.

    Fonctions de l’administrateur
Le cinquième changement est l’ajout de fonctions d’administrateur.

L’exploitation forestière est ennuyeux et surtout inutile, jusqu’à ce que quelque chose va mal.

Les statistiques sont à la base de l’analyse des performances et tuning.

Nous devons fournir des interfaces vers les structures internes afin que les utilisateurs peuvent surveiller et contrôler les fonctionnalités. Il est pas beaucoup de bon si personne ne sait ce qu’il fait. Une fois que les gens savent ce qu’il fait, ils vont probablement vouloir le changer.

Rédaction d’un cadre Fork-Join qui est simple à utiliser et efficace pour les appels locaux est difficile. Faire la même chose pour l’accès réseau est une entreprise majeure.

    Combien de temps faudrait-il pour construire un tel serveur?

Environ 5-6 secondes. Juste assez longtemps pour décompresser un fichier.

Heureusement, il ya des fins générales, fourche rejoindre cadres soutenant les propriétés mentionnées ci-dessus pour les applications de tous les jours, multi-core en Java ™ SE, ME et Android ™ disponibles aujourd’hui. Et puisque le cadre peut fonctionner comme un serveur RMI (standard / activable, IIOP et le POA), il est disponible pour les applications Java EE ™.
Tymeac ™ pour Java ™ SE / ME / plates-formes Android ™ sont des projets de logiciels Open Source maintenus surSourceForge.net
et vous pouvez télécharger les dernières éditions il.

Conclusion

Avec une fourchette Rejoignez-cadre élaboré pour les communautés de calcul intensif ne fonctionne pas bien pour les applications quotidiennes.

La majeure partie des applications Java ™ multi-core besoin de débourser le travail en ses composants fonctionnels avec un cadre de qualité professionnelle qui est facile à utiliser, efficace, et open-source.
Les références

Téléchargements:

Télécharger la dernière édition SE de Tymeac ici. Avec toute la documentation, des scripts, des classes et de la source.

Télécharger la dernière édition de ME de Tymeac ici. Avec toute la documentation et de la source.

Téléchargez la dernière édition de ET Tymeac ici. Avec toute la documentation et des projets complets d’éclipse.

Télécharger la dernière édition de DSE de Tymeac ici. La version Divide-and-Conquer.

Articles:

La version Divide-and-Conquer haute performance de Tymeac – A Java Fork-Join Conquérant

La haute performance version d’Android ™ de Tymeac – Gestion Discussions dans Android

Utilisation des listes d’attente pour l’efficacité – High Performance files d’attente prioritaires dans Java SE

Le fil de conteneurs Java ™ SE – Gestion des discussions en Java SE

Autre:

Fourche rejoindre la file d’attente wiki – http://en.wikipedia.org/wiki/Fork-join_queue

La loi de Murphy – http://en.wikipedia.org/wiki/Murphy%27s_law

CPU cache wiki – http://en.wikipedia.org/wiki/CPU_cache

Cache cohérence wiki – http://en.wikipedia.org/wiki/Cache_coherence

Wiki embarrassante parallèle – http://en.wikipedia.org/wiki/Embarrassingly_parallel

   A propos de l’auteur

Edward Harned est un développeur de logiciels avec une expérience plus de trente ans de l’industrie. Il a d’abord conduit des projets en tant que salarié dans les grandes industries et a ensuite travaillé comme consultant indépendant. Aujourd’hui, Ed est un développeur senior chez Cooperative Software Systems, Inc., où, pendant les douze dernières années, il a utilisé la programmation Java ™ pour donner fourche rejoindre des solutions à un large éventail de tâches.

© 2010 – 2011 E.P. Harned Tous droits réservés

Comments are closed.