Histogramme des occurences

Objectif

Le but de ce TP est de mettre en œuvre un algorithme parallèle de calcul d’histogramme pour un tableau donné de caractères. Il y a 128 caractères dans l’antique table ASCII mais nous ne considérerons que ceux dont les codes entiers sont compris entre 32 et 126. Chaque caractère, à l’exception des n°36 et n°42, sera associé à un emplacement particulier, pour un total fixe de 68 emplacements (nous ne faisons pas de distinction entre les minuscules et les majuscules). Les classes de l’histogramme seront des compteurs 32 bits non signés dont on supposera qu’ils ne déborderont pas. On utilisera pour cela l’approche consistant à créer un histogramme en mémoire partagée pour chaque bloc de threads, puis à modifier l’histogramme global de manière atomique.

Instructions

Vous pouvez soit réutiliser le modèle Nvidia dans le dossier samples-etu/0_Simple, soit écrire votre propre code source à partir de zéro. Quelle que soit la solution que vous choisissez, n’oubliez pas que votre code doit effectuer les opérations suivantes :

  • allouer la mémoire du GPU

  • copier les données depuis la mémoire du CPU vers la mémoire du GPU

  • initialiser les dimensions de la grille et des blocs de threads

  • lancer le(s) noyau(x) CUDA

  • copier le(s) résultat(s) du GPU vers l’hôte

  • libérer la mémoire GPU

Le fichier exécutable, généré à la suite de la compilation de votre projet avec la commande make et le fichier Makefile fourni par Nvidia, devra être exécuté en utilisant la commande suivante :

perrot@cluster2:~$ ./histoText -i <inputText.txt> -o <outputHisto.csv>

où <outputHisto.csv> est le fichier de sortie au format csv contenant sur chaque ligne : <ASCII char c>:<c count>. Le fichier d’entrée est <inputText.txt> et contient l’ensemble des données à traiter.

Note

  • Comme référence, vous pouvez traiter ceci Dictionnaire anglais et le fichier de sortie résultant devrait être comme ceci.

  • Evidemment, ce dictionnaire ne contient pas tous les caractères ASCII. Vous êtes donc fortement invités à générer ou à trouver d’autres fichiers de test pour vous assurer que votre programme fonctionne correctement.

  • Mes propres tests incluront divers fichiers.

  • Vos travaux seront notés selon plusieurs critères :

    • la qualité du code CUDA

    • les réponses aux questions suivantes

    • la performance de votre programme

Questions

En plus du code lui-même, vous êtes invité à répondre aux questions suivantes, ce qui vous aidera éventuellement à mieux cerner la conception du code demandé.

  • Avez-vous eu des difficultés à réaliser correctement l’optimisation ?

  • Quelles sont les optimisations les plus bénéfiques ?

  • Combien de lectures de la mémoire globale sont-elles effectuées par votre kernel calculant l’histogramme ? expliquez.

  • Combien d’opérations atomiques sont effectuées par votre kernel calculant l’histogramme ? expliquez.

  • La plupart des fichiers texte se composent uniquement de lettres, de chiffres et de caractères d’espacement. Que pouvons-nous dire sur les conflits d’accès concernant le nombre de threads qui essaient simultanément d’incrémenter atomiquement un histogramme privé ?

Avertissement

Deadline

  • Comme je n’ai pas accès à la plateforme Moodle de l’ECM, vous êtes invités à m’envoyer votre code source par e-mail en pièce jointe.

  • Je dois recevoir vos codes avant le 31 mars. Tout code qui sera envoyé après cette date recevra une note de 0/20.