Vektorizasyon (bilgisayar)

Vectorization (içinde paralel hesaplama ), özel bir durumu olan paralellik gerçekleştirir yazılım olup, varsayılan tek bir seferde bir işlem ipliği eş zamanlı olarak birden fazla işlevi yerine getirmek için modifiye edilir.

Vektörizasyon, bir bilgisayar programını bir seferde tek bir işlenen çiftini işleyen skaler bir uygulamadan , bir seferde birkaç işlenen çifti üzerinde bir işlemi işleyen bir vektör uygulamasına dönüştürme işlemidir. Terim, işlenenleri vektörlere veya matrislere koyma kuralından gelir .

Vektörü hesaplama konvansiyonel bilgisayar ve için önemli bir özelliktir süper eş zamanlı olarak, örneğin, aşağıdaki dört eklemenin örneğin işlemleri gerçekleştirmek vektör işlemleri gerçekleştirebilir modern:

Bununla birlikte, çoğu programlama dilinde genellikle büyük sayıların sıralı olarak eklenmesini gerçekleştiren döngüler yazarız. İşte C de böyle bir döngü örneği  :

for (i=0; i<n; i++) c[i] = a[i] + b[i];

Otomatik vektörleştirme, bilgisayar biliminde önemli bir araştırma konusudur; bir derleyicinin (insan yardımı olmadan) skaler programları vektörleştirilmiş programlara dönüştürmesine izin veren yöntemleri aramaktan ibarettir .

Bağlam

İlk bilgisayarlar genellikle bir seferde bir çift işlenen üzerinde bir talimatı sırayla yürüten mantıksal bir birime sahipti. Bilgisayar programları ve programlama dilleri bu nedenle komutları sıralı olarak yürütmek için tasarlanmıştır. Modern bilgisayarlar birçok şeyi aynı anda yapabilir. Çok sayıda iyileştirici derleyici, otomatik kod vektörleştirmesi gerçekleştirir: bu, bir vektör işlemci tarafından iyi kullanılacak kodu üretmek için sıralı programların parçalarının eşdeğer paralel programlara dönüştürülmesine izin veren bir derleyici özelliğidir.

Garantiler

Otomatik vektörleştirme, döngü optimizasyonu veya başka bir derleme optimizasyonu gibi, programın davranışını tam olarak korumalıdır.

Veri bağımlılıkları

Yanlış sonuçlardan kaçınmak için çalışma zamanında tüm bağımlılıklara uyulmalıdır.

Genel olarak, döngü değişmezleri ve sözcüksel kapsamı belirlenmiş bağımlılıklar kolaylıkla vektörleştirilebilir ve kapsamlı olmayan bağımlılıklar da daha zor olsa da vektörleştirilebilir. Ancak orijinal koda sadık kalarak tüm beyanlar arasında bağımlılığı sağlamak için bu dönüşümlerin güvenli bir şekilde yapılması gerekir.

Döngüsel bağımlılıklar, vektörleştirilmiş talimatlardan bağımsız olarak ele alınmalıdır.

Veri doğruluğu

Doğruluk ve bütün (ikili boyutu) vektörü talimat yürütme esnasında muhafaza edilmesi gerekmektedir. İkincisi, dahili tamsayıların boyutuna ve davranışına göre doğru seçilmelidir. Ayrıca, karışık tam sayı türlerinde, hassasiyet kaybı olmadan düzgün bir şekilde yükseltmek / indirgemek için ekstra özen gösterilmelidir. İşaret genişletme (aynı kayıtta birkaç tam sayı paketlenir) ve dönüştürme işlemleri sırasında veya hesaba katılmış olan bit işlemlerini taşırken özel dikkat gösterilmelidir.

IEEE-754 uyumluluğu etkin olmadığı sürece kayan nokta hassasiyeti de korunmalıdır; bu durumda işlemler daha hızlı olur ancak sonuçlar biraz farklılık gösterir. Büyük varyasyonlar, hatta IEEE-754'ü görmezden gelmek bile genellikle programlama hataları anlamına gelir. Programcı ayrıca tek duyarlıklı sabitleri ve döngü değişkenlerini (normalde varsayılan olarak iki) komut başına iki kat daha fazla işlem gerçekleştirmeye zorlayabilir.

Teori

Bir programı vektörleştirmek için, derleyici eniyileyici önce bildirimler arasındaki bağımlılıkları anlamalı ve gerekirse bunları yeniden hizalamalıdır. Bağımlılıklar haritalandıktan sonra, optimize edici, uygun adayların talimat uygulamalarını, çoklu veri öğeleri üzerinde çalışan talimat vektörlerine uygun şekilde organize etmelidir.

Bağımlılık grafiğini oluşturma

İlk adım, diğer bildirimlere bağlı olan bildirimleri tanımlayan bağımlılık grafiği oluşturmaktır. Bu, her bir ifadeyi incelemeyi ve ifadenin eriştiği her bir veri öğesinin birbirini tanımlamayı içerir. Diğer ad analizi , farklı değişkenlerin aynı bellek tahsisine eriştiğini doğrulamak için kullanılabilir.

Bağımlılık grafiği, vektörün boyutundan daha kısa bir mesafeye sahip tüm yerel bağımlılıkları içerir. Dolayısıyla, vektör kaydı 128 bit ise ve dizi türü 32 bit ise, vektörün boyutu 128/32 = 4'tür. Diğer tüm döngüsel olmayan bağımlılıklar vektörleştirmeyi geçersiz kılmamalıdır, çünkü eşzamanlı olmayacaktır. aynı vektör talimatına erişim.

Vektörün boyutunun 4 tamsayı (ints) ile aynı olduğunu varsayalım:

for (i = 0; i < 128; i++) { a[i] = a[i-16]; // 16 > 4, ignoré a[i] = a[i-1]; // 1 < 4, reste sur le graphe de dépendances }

Kümeleme

Optimize edici, grafiği kullanarak güçlü bir şekilde bağlı bileşenleri (SCC) ve vektörleştirilebilir ifadeleri diğerlerinden ayırarak gruplayabilir.

Örneğin, bir döngü içinde üç komut kümesini içeren bir program parçasını düşünün: (SCC1 + SCC2), SCC3 ve SCC4, bu sırayla, sadece ikinci kümenin (SCC3) vektörleştirilebilir. Son program, her küme için bir tane olmak üzere, yalnızca ortadaki vektörleştirilmiş üç döngü içerecektir. Optimize edici, talimatın yürütülme sırasını ihlal etmeden birinciden sonuncuyu birleştiremez, bu da gerekli garantileri geçersiz kılar.

Deyim algılama

Belirgin olmayan bazı bağımlılıklar, belirli deyimlere göre daha da optimize edilebilir.

Örneğin, sağdaki değerlerin değeri (RHS) alındığından ve ardından soldaki değerde saklandığından, aşağıdaki veri öz bağımlılıkları vektörleştirilebilir, böylece veriler atama içinde değişemez.

a[i] = a[i] + a[i+1];

Skalerlere göre kendine bağımlılık, değişkenler elimine edilerek vektörleştirilebilir.

Genel çerçeve

Döngü vektörleştirmenin genel çerçevesi dört aşamaya ayrılmıştır:

  • Başlangıç: Bağımsız döngü değişkenleri döngü içinde kullanılmaya hazır olduğunda. Bu normalde onları vektör komutlarında kullanılacak belirli desenlere sahip vektör yazmaçlarına taşımayı içerir. Bu aynı zamanda çalışma zamanı bağımlılık kontrolünün ekleneceği yerdir. Kontrol, vektörleştirmenin mümkün olmadığına karar verirse, temizleme adımına gidin.
  • Döngü (ler): orijinal kodda görünüm sırasına göre CSSC kümeleriyle ayrılmış tüm vektörleştirilmiş döngüler (veya değil).
  • Postlude: bağımsız döngülerin, indüksiyonların ve indirgemelerin tüm değişkenlerini döndürür.
  • Temizleme: Vektör boyutunun katı olmayan bir döngünün sonundaki yinelemeler için veya çalışma zamanı kontrollerinin vektör işlemeyi engellediği durumlarda döngüleri (vektörleştirilmemiş) basitçe uygular.

Çalışma zamanı vs derleme

Bazı vektörleştirmeler, derleme sırasında tam olarak doğrulanamaz. Derleme zamanı optimizasyonu, açık bir dizi indeksi gerektirir . Kütüphane fonksiyonları, işledikleri veriler harici parametreler tarafından sağlanmışsa optimizasyonu da ortadan kaldırabilir. Bu durumlarda bile, çalışma zamanı optimizasyonu çalışan döngüleri yine de vektörleştirebilir.

Bu yürütme kontrolü, başlangıç ​​aşamasında yapılır ve mümkünse akışı vektörleştirilmiş talimatlara yönlendirir, aksi takdirde kayıtlara veya skaler değişkenlere aktarılan değişkenlere bağlı olarak standart işlemeye geri döneriz.

Aşağıdaki kod, harici parametreleri çağıran veya bunlara bağlı herhangi bir işleve sahip olmadığından, derleme sırasında kolayca vektörleştirilebilir. Ek olarak, dil başka bir değişkenle aynı bellek tahsisini işgal etmeyeceğini, yerel değişkenler olmasını ve yalnızca yürütme yığınında yaşayacağını garanti eder .

int a[128]; int b[128]; // initialise b for (i = 0; i<128; i++) a[i] = b[i] + 5;

Öte yandan, aşağıdaki kodun bellek konumları hakkında hiçbir bilgisi yoktur çünkü referanslar işaretçilerdir ve tahsis edildikleri bellek dinamiktir.

int *a = malloc(128*sizeof(int)); int *b = malloc(128*sizeof(int)); // initialise b for (i = 0; i<128; i++, a++, b++) *a = *b + 5; // ... // ... // ... free(b); free(a);

A ve b adresinin yanı sıra yineleme döngü alanı (128) üzerinde hızlı bir çalışma süresi kontrolü, dizilerin örtüşüp örtüşmediğini söylemek için yeterlidir , böylece tüm bağımlılıkları ortaya çıkarır.

Derleyicinin evrimi ve / veya manuel kod değişiklikleri yoluyla yararlanılabilen SIMD paralelizminin doğasında bulunan gizli potansiyeli değerlendirmek için mevcut uygulamaları dinamik olarak analiz etmek için araçlar vardır .

Teknikler

Bir örnek, iki dijital veri vektörünü çarpan bir program olabilir. Skaler bir yaklaşım şöyle bir şey olabilir:

for (i = 0; i < 1024; i++) C[i] = A[i]*B[i];

Şöyle görünmesi için vektörleştirilebilir:

for (i = 0; i < 1024; i+=4) C[i:i+3] = A[i:i+3]*B[i:i+3];

Burada, C [i: i + 3], C [i] ila C [i + 3] arasındaki dört dizi indeksini temsil eder ve vektör işlemci, tek bir vektör talimatı için dört işlem gerçekleştirebilir. Dört vektör işleminin tümü bir skaler talimatla yaklaşık aynı anda tamamlandığından, vektör yaklaşımı orijinal koddan dört kata kadar daha hızlı çalışabilir.

Derleme için iki farklı yaklaşım vardır: biri klasik vektörleştirme tekniğine, diğeri ise döngü çözmeye dayanır .

Döngü seviyesinde otomatik vektörleştirme

Klasik vektör makineleri için kullanılan bu teknik, SIMD paralelizmini döngü düzeyinde bulmaya ve kullanmaya çalışır. Aşağıdaki gibi iki ana aşamadan oluşur.

  1. Vektörize edilebilen bir iç döngü bulun;
  2. Döngüyü dönüştürün ve vektör kodları oluşturun;

İlk adımda, derleyici vektörleştirmeyi engelleyebilecek engelleri arar. Vektörizasyonun önündeki en büyük engel, vektörün uzunluğundan daha kısa gerçek bir veri bağımlılığıdır. Diğer engeller arasında işlev çağrıları ve kısa yineleme sayıları bulunur.

Döngünün vektörleştirilebilir olduğu belirlendikten sonra, döngü vektörün uzunluğu kadar sıyrılır ve döngü gövdesindeki her bir skaler talimat karşılık gelen vektör talimatıyla değiştirilir. Aşağıda, bu adımdaki bileşen dönüşümleri yukarıdaki örnek kullanılarak gösterilmektedir.

for (i = 0; i < 1024; i+=4) for (ii = 0; ii < 4; ii++) C[i+ii] = A[i+ii]*B[i+ii];
  • Geçici Diziler Kullanarak Döngüler Dağıttıktan Sonra
for (i = 0; i < 1024; i+=4) { for (ii = 0; ii < 4; ii++) tA[ii] = A[i+ii]; for (ii = 0; ii < 4; ii++) tB[ii] = B[i+ii]; for (ii = 0; ii < 4; ii++) tC[ii] = tA[ii]*tB[ii]; for (ii = 0; ii < 4; ii++) C[i+ii] = tC[ii]; }
  • Vektör kodlarını kullanarak değiştirdikten sonra
for (i = 0; i < 1024; i+=4) { vA = vec_ld( &A[i] ); vB = vec_ld( &B[i] ); vC = vec_mul( vA, vB ); vec_st( vC, &C[i] ); }

Temel blok seviyesinde otomatik vektörleştirme

Bu nispeten yeni teknik, özellikle kısa vektör uzunluklarına sahip modern SIMD mimarilerini hedeflemektedir. Temel bloklarda SIMD paralelliğinin miktarını artırmak için döngüler açılabilse de, bu teknik döngülerden ziyade temel bloklar içindeki SIMD paralelliğinden yararlanır. İki ana aşama:

  1. En içteki döngü, büyük bir döngü gövdesi oluşturmak için vektörün uzunluğunun bir faktörü tarafından çözülür.
  2. İzomorfik skaler talimatlar (aynı işlemi gerçekleştiren), bağımlılıklar bunu yapmasını engellemiyorsa, bir vektör talimatında paketlenir.

Bu yaklaşımın adım adım dönüşümlerini göstermek için yukarıdaki ile aynı örnek tekrar kullanılmıştır.

  • Döngüleri çözdükten sonra (vektörün uzunluğuna göre, bu durumda 4 olduğu varsayılır)
for (i = 0; i < 1024; i+=4) { sA0 = ld( &A[i+0] ); sB0 = ld( &B[i+0] ); sC0 = sA0 * sB0; st( sC0, &C[i+0] ); ... sA3 = ld( &A[i+3] ); sB3 = ld( &B[i+3] ); sC3 = sA3 * sB3; st( sC3, &C[i+3] ); }
  • Paketlemeden sonra
for (i = 0; i < 1024; i+=4) { (sA0,sA1,sA2,sA3) = ld( &A[i+0:i+3] ); (sB0,sB1,sB2,sB3) = ld( &B[i+0:i+3] ); (sC0,sC1,sC2,sC3) = (sA0,sA1,sA2,sA3) * (sB0,sB1,sB2,sB3); st( (sC0,sC1,sC2,sC3), &C[i+0:i+3] ); }
  • Kod oluşturulduktan sonra
for (i = 0; i < 1024; i+=4) { vA = vec_ld( &A[i] ); vB = vec_ld( &B[i] ); vC = vec_mul( vA, vB ); vec_st( vC, &C[i] ); }

Burada, sA1, SB1, ... skaler değişkenleri temsil eder ve VA, VB ve Vc vektör değişkenlerini temsil eder.

Ticari otomatik vektör oluşturma derleyicileri, her ikisini de kullanan IBM XL derleyicisi dışında, çoğunlukla geleneksel döngü düzeyi yaklaşımını kullanır.

Kontrol akışının varlığında

Varlığı durumunda döngü gövdesinde bir değişkenin birden fazla değeri birleştirmek için her komut yolları ifadelerin yürütülmesini gerektirir. Genel bir yaklaşım, bir dizi kod dönüşümünden geçmektir: Tahmin → vektörleştirme (yukarıdaki yöntemlerden birini kullanarak) → vektörlerden tahminleri kaldırmak → skaler yüklemleri kaldırmak.

Aşağıdaki kod, bu dönüşümleri göstermek için bir örnek olarak kullanılmıştır:

for (i = 0; i < 1024; i++) if (A[i] > 0) C[i] = B[i]; else D[i] = D[i-1];
  • Vaaz ettikten sonra
for (i = 0; i < 1024; i++) { P = A[i] > 0; NP = !P; C[i] = B[i]; (P) D[i] = D[i-1]; (NP) }

(P) beyanı tutan bir yüklemi belirtir.

  • Vektörizasyondan sonra
for (i = 0; i < 1024; i+=4) { vP = A[i:i+3] > (0,0,0,0); vNP = vec_not(vP); C[i:i+3] = B[i:i+3]; (vP) (NP1,NP2,NP3,NP4) = vNP; D[i+3] = D[i+2]; (NP4) D[i+2] = D[i+1]; (NP3) D[i+1] = D[i]; (NP2) D[i] = D[i-1]; (NP1) }
  • Vektörlerden yüklemleri kaldırdıktan sonra
for (i = 0; i < 1024; i+=4) { vP = A[i:i+3] > (0,0,0,0); vNP = vec_not(vP); C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vP); (NP1,NP2,NP3,NP4) = vNP; D[i+3] = D[i+2]; (NP4) D[i+2] = D[i+1]; (NP3) D[i+1] = D[i]; (NP2) D[i] = D[i-1]; (NP1) }
  • Skaler yüklemleri kaldırdıktan sonra
for (i = 0; i < 1024; i+=4) { vP = A[i:i+3] > (0,0,0,0); vNP = vec_not(vP); C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vP); (NP1,NP2,NP3,NP4) = vNP; if (NP4) D[i+3] = D[i+2]; if (NP3) D[i+2] = D[i+1]; if (NP2) D[i+1] = D[i]; if (NP1) D[i] = D[i-1]; }

Kontrol akışı varlığında ek vektörleştirme maliyetinin azaltılması

Vektör kodundaki tüm kontrol yollarındaki talimatları yürütme zorunluluğu, skaler tabana göre vektör kodunu yavaşlatan ana faktörlerden biri olmuştur. Komut akışı ne kadar karmaşık hale gelirse ve skaler kodda ne kadar çok talimat sapılırsa, vektörleştirme o kadar zor olur. Ek yükünü azaltmak için, vektör dalları, skaler dalların skaler talimatları atlamasına benzer şekilde talimat vektörlerini atlamak için eklenebilir. Aşağıda, bunun nasıl elde edilebileceğini göstermek için AltiVec tahminleri kullanılmıştır.

  • Skaler taban (orijinal kod)
for (i = 0; i < 1024; i++) { if (A[i] > 0) { C[i] = B[i]; if (B[i] < 0) D[i] = E[i]; } }
  • Kontrol akışı varlığında vektörleştirmeden sonra
for (i = 0; i < 1024; i+=4) { vPA = A[i:i+3] > (0,0,0,0); C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vPA); vT = B[i:i+3] < (0,0,0,0); vPB = vec_sel((0,0,0,0), vT, vPA); D[i:i+3] = vec_sel(D[i:i+3],E[i:i+3],vPB); }
  • Vektör dallarına eklendikten sonra
for (i = 0; i < 1024; i+=4) if (vec_any_gt(A[i:i+3],(0,0,0,0))) { vPA = A[i:i+3] > (0,0,0,0); C[i:i+3] = vec_sel(C[i:i+3],B[i:i+3],vPA); vT = B[i:i+3] < (0,0,0,0); vPB = vec_sel((0,0,0,0), vT, vPA); if (vec_any_ne(vPB,(0,0,0,0))) D[i:i+3] = vec_sel(D[i:i+3],E[i:i+3],vPB); }

Vektör dallanma ile son kodda dikkat edilmesi gereken iki şey vardır. Bir yandan, vPA için talimatı tanımlayan yüklem de vec_any_gt kullanılarak harici vektör dalının gövdesine dahil edilir. Öte yandan, vPB'nin tüm bit alanlarında yanlış değerlere sahip olması nedeniyle, vPB için iç vektör dallanmasının karlılığı, vPB'nin tüm alanlarda yanlış değerlere sahip olmasının koşullu olasılığına bağlıdır.

Skaler tabandaki harici dallanmanın her zaman döngünün gövdesindeki talimatların çoğu atlanarak alındığı bir örnek düşünün. Vektör dallanmasız yukarıdaki ara durum, tüm vektör komutlarını çalıştırır. Vektör dallanma ile son kod, vektör kipinde hem karşılaştırmayı hem de dallanmayı gerçekleştirir ve potansiyel olarak skaler tabana göre performans kazanır.

Ayrıca görün

Referanslar

  1. http://dl.acm.org/citation.cfm?id=2254108
  2. S. Larsen ve S. Amarasinghe , "  Programlama dili tasarımı ve uygulaması üzerine ACM SIGPLAN konferansının bildirileri  ", ACM SIGPLAN Bildirimleri , cilt.  35, n o  5,2000, s.  145–156 ( DOI  10.1145 / 358438.349320 )
  3. "  IBM XL Derleyicileriyle Kod Optimizasyonu  " ,Haziran 2004(erişim tarihi Mayıs 2010 )
  4. J. Shin , MW Hall ve J. Chame , "  Kod oluşturma ve optimizasyon üzerine uluslararası sempozyum bildirileri  ", Kontrol Akışının Varlığında Süper Kelime Düzeyinde Paralellik ,2005, s.  165–175 ( ISBN  0-7695-2298-X , DOI  10.1109 / CGO.2005.33 )
  5. J. Shin , "  16. Uluslararası Paralel Mimari ve Derleme Teknikleri Konferansı Bildirileri  ", Vektorlu Koda Kontrol Akışı Tanıtımı ,2007, s.  280–291 ( DOI  10.1109 / PACT.2007.41 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">