Matrice paralelă - Parallel array

În calcul , un grup de matrice paralele (cunoscut și ca structură de matrice sau SoA) este o formă de structură de date implicită care folosește mai multe matrice pentru a reprezenta o matrice singulară de înregistrări . Păstrează o matrice de date separată, omogenă pentru fiecare câmp al înregistrării, fiecare având același număr de elemente. Apoi, obiectele situate la același index în fiecare matrice sunt implicit câmpurile unei singure înregistrări. Pointerii de la un obiect la altul sunt înlocuiți cu indicii matrice. Acest lucru contrastează cu abordarea normală a stocării tuturor câmpurilor fiecărei înregistrări împreună în memorie (cunoscută și sub numele de matrice de structuri sau AoS). De exemplu, s-ar putea declara o matrice de 100 de nume, fiecare un șir și 100 de vârste, fiecare un număr întreg, asociind fiecare nume cu vârsta care are același indice.

Exemple

Un exemplu în C folosind tablouri paralele: 

int  ages[]   = {0,          17,        2,          52,         25};
char *names[] = {"None",     "Mike",    "Billy",    "Tom",      "Stan"};
int  parent[] = {0 /*None*/, 3 /*Tom*/, 1 /*Mike*/, 0 /*None*/, 3 /*Tom*/};

for (i = 1; i <= 4; i++) {
    printf("Name: %s, Age: %d, Parent: %s \n",
           names[i], ages[i], names[parent[i]]);
}

în Perl (folosind un hash de matrice pentru a păstra referințe la fiecare matrice): 

my %data = (
    first_name   => ['Joe',  'Bob',  'Frank',  'Hans'    ],
    last_name    => ['Smith','Seger','Sinatra','Schultze'],
    height_in_cm => [169,     158,    201,      199      ]);

for $i (0..$#{$data{first_name}}) {
    printf "Name: %s %s\n", $data{first_name}[$i], $data{last_name}[$i];
    printf "Height in CM: %i\n", $data{height_in_cm}[$i];
}

Sau, în Python : 

first_names   = ["Joe",  "Bob",  "Frank",  "Hans"    ]
last_names    = ["Smith","Seger","Sinatra","Schultze"]
heights_in_cm = [169,     158,    201,      199      ]

for i in range(len(first_names)):
    print("Name: %s %s" % (first_names[i], last_names[i]))
    print("Height in cm: %s" % heights_in_cm[i])

# Using zip:
for first_name, last_name, height_in_cm in zip(first_names, last_names, heights_in_cm):
    print(f"Name: {first_name} {last_name}")
    print(f"Height in cm: {height_in_cm}")

Argumente pro şi contra

Tablourile paralele au o serie de avantaje practice față de abordarea normală:

  • În unele cazuri, pot economisi o cantitate substanțială de spațiu evitând probleme de aliniere. De exemplu, unele arhitecturi funcționează cel mai bine dacă numerele întregi de 4 octeți sunt întotdeauna stocate începând cu locațiile de memorie care sunt multiple de 4. Dacă câmpul anterior a fost un singur octet, s-ar putea pierde 3 octeți. Multe compilatoare moderne pot evita automat astfel de probleme, deși în trecut unii programatori declarau în mod explicit câmpurile în ordinea reducerii restricțiilor de aliniere.
  • Dacă numărul de articole este mic, indicii matricii pot ocupa mult mai puțin spațiu decât indicii plini, în special pe unele arhitecturi.
  • Examinarea secvențială a unui singur câmp al fiecărei înregistrări din matrice este foarte rapidă pe mașinile moderne, deoarece aceasta echivalează cu o traversare liniară a unui singur tablou, prezentând o localitate ideală de referință și un comportament cache.
  • Acestea pot permite procesarea eficientă cu instrucțiuni SIMD în anumite arhitecturi ale setului de instrucțiuni

Unele dintre aceste avantaje depind în mare măsură de limbajul de programare particular și de implementarea în utilizare.

Cu toate acestea, matricele paralele au, de asemenea, mai multe dezavantaje puternice, ceea ce servește pentru a explica de ce nu sunt, în general, preferate:

  • Au o localitate de referință semnificativ mai slabă atunci când vizitează înregistrările non-secvențial și examinează mai multe câmpuri ale fiecărei înregistrări, deoarece diversele tablouri pot fi stocate în mod arbitrar la distanță.
  • Ele ascund relația dintre câmpurile unei singure înregistrări (de exemplu, nicio informație de tip nu are legătură cu indexul dintre ele, un index poate fi utilizat în mod eronat).
  • Au puțină limbă directă (limbajul și sintaxa acestuia nu exprimă de obicei nicio relație între tablourile din matricea paralelă și nu pot detecta erori).
  • Întrucât pachetul de câmpuri nu este un „lucru”, trecându-l în jurul lui obositor și predispus la erori. De exemplu, în loc să apeleze o funcție pentru a face ceva unei înregistrări (sau structură sau obiect), funcția trebuie să ia câmpurile ca argumente separate. Când se adaugă sau se modifică un câmp nou, multe liste de parametri trebuie să se schimbe, unde trecerea obiectelor ca întreg ar evita astfel de modificări în întregime.
  • Sunt scumpe de crescut sau micșorate, deoarece fiecare dintre mai multe tablouri trebuie să fie realocate. Tablourile pe mai multe niveluri pot ameliora această problemă, dar afectează performanța din cauza indirectării suplimentare necesare pentru a găsi elementele dorite.
  • Poate cel mai rău dintre toate, acestea ridică foarte mult posibilitatea de erori. Orice inserare, ștergere sau mutare trebuie aplicată întotdeauna în mod consecvent tuturor matricelor, sau matricele nu vor mai fi sincronizate între ele, ducând la rezultate bizare.

Localitatea defectuoasă de referință poate fi atenuată în unele cazuri: dacă o structură poate fi împărțită în grupuri de câmpuri care sunt în general accesate împreună, se poate construi o matrice pentru fiecare grup, iar elementele sale sunt înregistrări care conțin doar aceste subseturi ale structurii mai mari câmpuri. (a se vedea proiectarea orientată spre date ). Acesta este un mod valoros de a accelera accesul la structuri foarte mari, cu mulți membri, păstrând în același timp porțiunile structurii legate între ele. O alternativă la legarea lor împreună utilizând indexuri matrice este utilizarea de referințe pentru a lega porțiunile, dar acest lucru poate fi mai puțin eficient în timp și spațiu.

O altă alternativă este de a utiliza o singură matrice, în care fiecare intrare este o structură de înregistrare. Multe limbi oferă o modalitate de a declara înregistrări reale și matrici ale acestora. În alte limbi, poate fi fezabil să simulați acest lucru declarând o matrice de dimensiuni n * m, unde m este dimensiunea tuturor câmpurilor împreună, împachetarea câmpurilor în ceea ce este efectiv o înregistrare, chiar dacă limbajul particular nu are suport direct pentru înregistrări. Unele optimizări ale compilatorului , în special pentru procesoarele vectoriale , sunt capabile să efectueze automat această transformare atunci când sunt create matrici de structuri în program.

Vezi si

Referințe

  • Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein . Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN  0-262-03293-7 . Pagina 209 a secțiunii 10.3: Implementarea indicatoarelor și a obiectelor.
  • Skeet, Jon (3 iunie 2014). „Anti-model: colecții paralele” . Accesat la 28 octombrie 2014 .