Que signifient les termes "CPU bound" et "I / O bound"? [optimization]


Answers

CPU Bound signifie que la vitesse à laquelle le processus progresse est limitée par la vitesse de la CPU. Une tâche qui effectue des calculs sur un petit ensemble de nombres, par exemple en multipliant de petites matrices, est susceptible d'être liée au processeur.

I / O Bound signifie que la vitesse à laquelle un processus progresse est limitée par la vitesse du sous-système d'E / S. Une tâche qui traite des données à partir d'un disque, par exemple, en comptant le nombre de lignes dans un fichier est susceptible d'être liée aux E / S.

La mémoire liée signifie que la vitesse à laquelle un processus progresse est limitée par la quantité de mémoire disponible et la vitesse de cet accès à la mémoire. Une tâche qui traite de grandes quantités de données en mémoire, par exemple en multipliant de grandes matrices, est susceptible d'être liée à la mémoire.

La limite du cache signifie la vitesse à laquelle la progression d'un processus est limitée par la quantité et la vitesse du cache disponible. Une tâche qui traite simplement plus de données qu'il n'en faut dans le cache sera liée au cache.

Le paramètre I / O Bound serait plus lent que le paramètre Memory Bound serait plus lent que Cache Bound serait plus lent que CPU Bound.

La solution pour être lié aux E / S n'est pas nécessairement d'avoir plus de mémoire. Dans certaines situations, l'algorithme d'accès pourrait être conçu autour des limites d'E / S, de mémoire ou de cache. Voir Cachez les algorithmes inconscients .

Question

Que signifient les termes "CPU bound" et "I / O bound"?




le multithreading est un cas où la distinction est importante comme expliqué sur les exemples ci-dessous.

Exemple lié d'E / S de RAM: Somme vectorielle

Considérons un programme qui résume toutes les valeurs d'un seul vecteur:

#define SIZE 1000000
unsigned int is[SIZE];
unsigned int sum = 0;
size_t i = 0;
for (i = 0; i < SIZE; i++)
    /* Each one of those requires a RAM access! */
    sum += is[i]

Paralléliser cela en divisant le tableau de manière égale pour chacun de vos noyaux est d'une utilité limitée sur les bureaux modernes courants. C ++ benchmark sur: https://github.com/cirosantilli/algorithm-cheat/blob/ea16f6bba12e7dcc32c0cbbbcdc74bcc2fd2d05b/src/cpp/interactive/sum_array_parallel.cpp

Testé sur GCC 5.2.1, Ubuntu 15.10 avec un processeur Intel Core i5-3210M, Lenovo T430. Exemple de résultats typiques (variable depuis multi-thread):

Time        N Threads   Comment
---------   ----------  --------
0.045962    none
0.0487619   1           Worse than 0 threads because of startup overhead.
0.0329526   2
0.0302511   3
0.0232993   4           Best time. Only about 2x as fast.
0.0281021   5           Worse than 4 threads because we don't have
                        that many cores, which generate overhead. 

Le calcul n'a pas été 4x plus rapide que prévu avec 4 threads!

La raison pour laquelle tous les processeurs partagent un seul bus de mémoire reliant la RAM:

CPU 1 --\     Bus   +-----+
CPU 2 ---\__________| RAM |
CPU 3 ---/          +-----+
CPU 4 --/

donc le bus mémoire devient rapidement le goulot d'étranglement, pas le CPU.

Cela se produit parce que l'ajout de deux nombres prend un cycle de processeur unique , les lectures de mémoire prennent environ 100 cycles de processeur dans le matériel 2016.

Ainsi, le travail du processeur effectué par octet de données d'entrée est trop petit, et nous appelons cela un processus lié à l'E / S.

La seule façon d'accélérer davantage ce calcul consisterait à accélérer les accès mémoire individuels avec un nouveau matériel de mémoire, par exemple la mémoire multicanaux .

Passer à une horloge CPU plus rapide par exemple ne serait pas très utile.

D'autres exemples

  • La multiplication matricielle est liée à la CPU sur la RAM et les GPU. L'entrée contient:

    2 * N**2
    

    chiffres, mais:

    N ** 3
    

    les multiplications sont faites, et cela suffit pour que la parallélisation en vaille la peine pour le grand N. pratique.

    C'est pourquoi les bibliothèques aiment:

    exister.

    L'utilisation du cache fait une grande différence pour la vitesse des implémentations. Voir par exemple cet exemple de comparaison GPU didactique .

  • Les GPU ont un goulot d'étranglement pour les E / S lors du transfert des données à la CPU.

    Ils sont conçus pour que la sortie de rendu (un rectangle de pixels) puisse être sortie directement dans la mémoire vidéo, pour éviter l'aller-retour du processeur.

  • Le réseautage est l'exemple prototypique lié aux entrées-sorties.

    Même lorsque nous envoyons un seul octet de données, il faut encore beaucoup de temps pour atteindre sa destination.

    La mise en parallèle de petites requêtes réseau comme les requêtes HTTP peut offrir d'énormes gains de performance.

    Si le réseau est déjà à pleine capacité (par exemple en téléchargeant un torrent), la parallélisation peut encore augmenter améliorer la latence (par exemple, vous pouvez charger une page Web "en même temps").

  • Une opération factice CPU C ++ factice qui prend un nombre et le croque beaucoup:

Comment savoir si vous êtes lié au CPU ou aux E / S

Non-RAM IO lié comme disque, réseau: ps aux , puis theck si CPU% / 100 < n threads . Si oui, vous êtes lié à l'E / S, par exemple, le blocage des read n'attend que les données et le planificateur ignore ce processus. Ensuite, utilisez d'autres outils comme sudo iotop pour décider quel IO est le problème exactement.

Limite RAM-IO: difficile à dire, en tant que temps d'attente de la RAM, il est inclus dans CPU% mesures du CPU% . Peut-être que le mieux que vous pouvez faire est d'estimer les échecs de cache.

Voir également:




Lorsque votre programme attend des E / S (c'est-à-dire une lecture / écriture de disque ou une lecture / écriture réseau, etc.), le CPU est libre d'effectuer d'autres tâches même si votre programme est arrêté. La vitesse de votre programme dépendra en grande partie de la vitesse à laquelle les E / S peuvent se produire, et si vous voulez l'accélérer, vous devrez accélérer les E / S.

Si votre programme exécute beaucoup d'instructions de programme et n'attend pas d'E / S, alors il est dit être lié à l'UC. L'accélération du processeur accélérera le fonctionnement du programme.

Dans les deux cas, la clé pour accélérer le programme pourrait ne pas être d'accélérer le matériel, mais d'optimiser le programme pour réduire la quantité d'IO ou de CPU dont il a besoin, ou de faire des E / S tout en intensifiant le CPU des trucs.




Processus liés à l'E / S: passez plus de temps à effectuer des opérations d'E / S que des calculs, vous avez de nombreuses rafales d'UC courtes. Processus liés à la CPU: passez plus de temps à faire des calculs, quelques rafales d'UC très longues