Korumalı alan

komik bıyık 25 Temmuz 2011, 00:59

Paralel matris çarpımı veya önbellek büyüsü. Küçük bir araştırma

giriiş

Bu makale tamamen meraktan yürütülen küçük bir çalışma hakkındadır. Ancak sonuçlar ilginç olduğundan yayınlamaya karar verdim. Paralel hesaplamanın temelleri basit ve kullanışlı bir görev kullanılarak tartışıldı: matris çarpımı.

Kesimin altında birkaç resim var!

Resmi olarak görev şu şekilde ifade edilir:
NxN boyutlu iki A ve B matrisi veriliyor. Ürünlerini hesaplamak gerekir: matris C.
C[i][j] = 1'den N'ye kadar k'nın toplamı A[i][k]*B[k][j].

Paralel bilgi işlem gerektirmeyen çözüm

Bu sorunu asimptotiklerle çözmek için en basit algoritma aşağıdaki gibidir:

for (int i = 0; i< n; ++i)
for (int j = 0; j< n; ++j){
c[i][j] = 0;
for (int k = 0; k< n; ++k)
c[i][j] = a[i][k]*b[k][j];
}

Yukarıdaki kodu 4-5 kat hızlandırmanıza olanak tanıyan iyi bilinen bir numara var. Bu, b dizisini, aktarılan B matrisini içeren bt dizisiyle değiştirmektir:

for (int i = 0; i< n; ++i)
for (int j = 0; j< n; ++j)
bt[i][j] = b[j][i];
for (int i = 0; i< n; ++i)
for (int j = 0; j< n; ++j){
c[i][j] = 0;
for (int k = 0; k< n; ++k)
c[i][j] = a[i][k]*bt[j][k];
}

* Bu kaynak kodu Kaynak Kodu İşaretleyici ile vurgulanmıştır .

Bu durumda hızlanma işlemci önbellek tasarımıyla ilgilidir. Bir bellek hücresine erişirken, yalnızca o değil, aynı zamanda birkaç komşu hücre de önbelleğe yazılır. İlk durumda, k aracılığıyla bir döngüde eriştiğimiz b dizisinin elemanları farklı satırlardadır, ancak aynı sütundadır ve dolayısıyla Veri deposu dizinin bir satırının boyutuna eşit bir mesafede bulunurlar. İkinci durumda, hafızada bulunan bt dizisinin bir satırının elemanlarına arka arkaya erişiyoruz.

Paralel Bilgi İşlem Çözümü

C matrisinin her bir elemanı diğerlerinden bağımsız olarak hesaplandığından ve A ve B matrisleri değişmediğinden, paralel çarpımı hesaplamak için C'nin hangi elemanlarının hangi ipliğe hesaplanacağını basitçe belirtmek yeterlidir.
Bu amaçla lf ve rg olmak üzere 2 sayı alan bir fonksiyon oluşturuldu. Fonksiyon, orijinal B matrisini kullanarak C matrisinin lf'den rg'ye kadar olan satırlarını hesaplar:

#define forn(i, n) for (int i = 0; i< int (n); ++i)

struct matrisMulParam(
int lf, rg;
matrisMulParam(int cLf = 0, int cRg = 0) : lf(cLf), rg(cRg)()
};

DWORD matrisMulNoHack(LPVOID p)(
for (int i = ((matrixMulParam*)p)->lf; i<= ((matrixMulParam*)p)->rg; ++i)
forn(j, n)(
c[i][j] = 0;
forn(k, n)
c[i][j] += a[i][k] * b[k][j];
}

Sil ((matrixMulParam*)p);
0 değerini döndür;
}

* Bu kaynak kodu Kaynak Kodu İşaretleyici ile vurgulanmıştır .

Benzer şekilde, transpoze edilmiş bir matris kullanılarak bir fonksiyon yazılmıştır.

Çalışma süresi verilerinin toplanması

Hesaplamalar 4'te yapıldı farklı bilgisayarlar farklı işlemcilerle:

1. Intel Atom N550
   • Saat frekansı: 1,5 GHz
   • Çekirdek sayısı: 2
   • Konu sayısı: 4
     Bu bir yazım hatası değil. İşte Intel web sitesine bir bağlantı ve burada netbook'umun Görev Yöneticisi ve Aygıt Yöneticisinin ekran görüntüleri var
   • L2 önbellek boyutu: 1 MB
2. Intel Core2Duo P8600
   • Saat frekansı: 2,4 GHz
   • Çekirdek sayısı: 2
   • Konu sayısı: 2
   • L2 önbellek boyutu: 3 MB
3. Intel Core2Quad Q6600
   • Saat frekansı: 2,4 GHz
   • Çekirdek sayısı: 4
   • Konu sayısı: 4
   • L2 önbellek boyutu: 8 MB
4. Amazon EC2 Yüksek CPU Ekstra Büyük Bulut Sunucusu,
   Güç açısından yaklaşık olarak 2. Intel Xeon E5410'a eşit
   • Saat frekansı: 2,33 GHz
   • Çekirdek sayısı: 4 (toplamda 8)
   • Akış sayısı: 4 (toplamda 8)
   • L2 önbellek boyutu: 12 (toplamda 24) MB

İstatistik elde etmek için aşağıdaki parametreler değiştirildi:

• Matris boyutu: 1000x1000 veya 2000x2000.
  Matrisler 1'den 1000'e kadar sözde rastgele tamsayılarla dolduruldu.
• 1'den 16'ya kadar iş parçacığı sayısı.
• Orijinal B matrisini veya aktarılmış olanı kullanma.

Belirtilen parametrelerin her kombinasyonu için en az 5 kez hesaplama yapıldı ve sonuç olarak program çalışma sürelerinin aritmetik ortalaması kullanıldı.

Sonuçlar

Farklı işlemcilere baktığım için farklı parametreler, karşılaştırma amacıyla programın milisaniye cinsinden mutlak çalışma süresini kullanamazsınız. Bunu yapmak için, göreceli çalışma süresini tanıtıyoruz: belirli parametrelerle matrislerin çarpımını hesaplama zamanının, aynı parametrelerle aynı matrislerin çarpımını tek bir iş parçacığında hesaplama zamanına yüzde olarak oranı.

Orijinal matrisi kullanan algoritma için göreceli çalışma süresinin iş parçacığı sayısına bağımlılığının grafiklerine bakalım:

Bu grafik tüm beklentileri karşılıyor: iş parçacığı sayısı çekirdek sayısına arttıkça çalışma süresi düşüyor ve ardından yaklaşık olarak sabit kalıyor. Bununla birlikte, Core2Quad ve Xeon için sonuçlar idealden %1'den daha az farklılık gösteriyorsa, Core2Duo ve Atom için sonuçlar daha kötüdür.

Veri boyutu 4 kat arttığında gecikme daha da güçleniyor. Özellikle Atom N550'de (netbook'lar açıkça 2000x2000 matrisleri çoğaltacak şekilde tasarlanmamıştır). Bu, aktarılmış bir matris kullanıldığında zamanın azalmasıyla tamamen aynı şekilde açıklanmaktadır. Belleğin farklı alanlarına erişen birden fazla iş parçacığı olduğunda, her iş parçacığı ayrı ayrı, belleği sırayla dolaşan bir iş parçacığından daha yavaş çalışacaktır. Ancak buna rağmen birden fazla iş parçacığı birden fazla iş parçacığından daha hızlı çalışacaktır.

Aşağıdaki grafikler, aktarılmış bir matris kullanan algoritma için iş parçacığı sayısına karşı göreceli çalışma süresini temsil eder:


Aktarılmış bir matris kullanıldığında hızlanma daha fazlası ile ilişkili olduğundan etkili kullanımönbellek, iş parçacığı sayısı artırılırsa ve bellek erişim sırası bozulursa daha kötü çalışmaya başlar. Atom ve Core2Quad ilginç bir şekilde davranıyor: Atom grafiği neredeyse hiç değişmeden kalırken Core2Quad performansı 1000x1000'den 2000x2000'e geçerken keskin bir şekilde kötüleşti.
Bu şu şekilde açıklanmaktadır: 1000x1000 matris boyutunda, 4 baytlık (int) 1000*1000 elemanlı 2 dizimiz (a ve b) var. Bu yaklaşık 8 megabayttır. Atom N550'nin 1 MB önbelleği, Core2Quad önbelleği tüm verilere uyduğunda tüm verilerin yalnızca 1/8'ini içeriyor. Dizileri 2000x2000'e genişlettiğimizde veri miktarını 4 kat arttırmış oluyoruz. Böylece artık verinin sadece 1/4'ü Core2Quad önbelleğine sığıyor ve aktarma hilesi daha az etkili oluyor ve Atom işlemcide çalışmadı ve çalışmaya devam ediyor.
Yukarıda açıklanan etkiyi göstermek için iki grafiği daha düşünün.
Transpoze matris kullanmanın verimliliğine, transpoze matrisi belirli parametreler altında kullanan algoritmanın çalışma süresinin, aynı parametreler altında orijinal matrisi kullanan algoritmanın çalışma süresine oranı adını verelim.


Bu grafik yukarıdakilerin tümünü iyi bir şekilde göstermektedir. Core2Quad ve Xeon'un verimliliği, belleğin farklı alanlarına erişen ve önbelleği parçalayan çok sayıda eşzamanlı iş parçacığı nedeniyle azalır. Core2Duo'nun verimliliği, aynı anda yalnızca 2 iş parçacığının çalışması ve önbellek boyutunun önceki işlemcilerdeki kadar büyük olmaması nedeniyle neredeyse hiç değişmedi.
Aşağıdaki şekil aynı grafiği yalnızca Atom N550 göstergelerinin eklenmesiyle içermektedir.


Önbellek ve transpoze hilesinin verimliliğindeki bu artışı hiçbir zaman anlayamadım. Umarım yorumlarda gerçeğin derinliklerine inebiliriz.

Çözüm

İlk önce,İşlemci önbelleği, programın yürütme hızını önemli ölçüde etkiler, ancak çoğu durumda bunu düşünmüyoruz bile.
İkincisi, kaynak kodu ve genel olarak bu makalede kullandığım her şey tek arşivdeki bağlantıdan indirilebilir.
Üçüncüsü, derleyici g++ 4.5.2 kullandı, derleme satırı g++ -Duvar -O,
Amazon'da Windows 7 ve Windows Server 2008 R2.
İlginiz için teşekkür ederiz.
Saygılarımla Ivan.

Not: Veri toplama süreci böyle görünüyordu

Etiketler: paralel hesaplama, çarpma, matris, c artı artı

Bu makale yoruma tabi değildir çünkü yazarı henüz topluluğun tam üyesi değildir. Yazarla ancak topluluktaki birinden davet aldıktan sonra iletişime geçebileceksiniz. Bu ana kadar kullanıcı adı bir takma adla gizlenecek.

Bu makale tartışılacak POSIX standartları Konular ve OpenMP. Yani NxN matrislerinin bu standartlar kullanılarak paralel çarpımı ve karşılaştırılması.

1) OpenMP kullanarak matris çarpım kodu.

#katmak #katmak #katmak #katmak #katmak #katmak #katmak #katmak #katmak #katmak #katmak #katmak int *alloc_matrix(int ​​size)( int *matrix = (int*)malloc(size * size * sizeof(int)); printf("matrix %dx%d tahsis edildi\n", size, size); dönüş matrisi ; ) void del_matrix(int ​​*matrix)( free(matrix); ) double dtime())( struct timeval tv; struct timezone tz; double t; gettimeofday(&tv, &tz); t = (double)tv.tv_sec + (double)tv .tv_usec*1e-6; return(t); int main() ( int N = 50; int THR = 2; int i, j, k; printf("İş parçacığı sayısını girin\n" ); scanf("% i",&THR); omp_set_dynamic(0); omp_set_num_threads(THR); printf("Matris boyutunu girin\n"); int *alloc_matrix(N); ); int *B = tahsis_matrix(N); int *C = tahsis_matrix(N); int rand_num(zaman(NULL));

2) Pthread kullanarak matris çarpımı kodu.

#dahil #dahil #dahil #dahil #dahil #katmak #katmak #katmak #include #include #define SIZE 50 int *alloc_matrix(int ​​size)( int *matrix = (int*)malloc(size * size * sizeof(int)); printf("matrix %dx%d tahsis edildi\n" , size , size); dönüş matrisi; ) void del_matrix(int ​​*matrix)( free(matrix); ) double dtime())( struct timeval tv; struct timezone tz; double t; gettimeofday(&tv, &tz); t = (çift) tv.tv_sec + (double)tv.tv_usec*1e-6; return(t); struct matris_args( int *m1; int *m2; int *ans; int boyut; int başlangıç; int bitiş; ) ARG; void *multiply_matrix(void *pargs)( struct matris_args *args = (struct matris_args *) pargs; int i, j, k, l, m, tmp = 0; double t0 = dtime(); int *m1 = args-> m1; int *m2 = args->ans; int boyut = args->boyut; int end = args->end;< end; i++){ m = i * size; for(j = 0; j < size; j++){ l = 0; for(k = 0; k < size; k++){ tmp += m1 * m2; l += size; } ans = tmp; tmp = 0; } } printf("thread works %fs\n", dtime() - t0); pthread_exit(NULL); } main(int argc, char** argv){ int i, j, size, k, step, pos, res; int THR_NUM,THR,N; printf("Введите число потоков\n"); scanf("%i",&THR); printf("Введите размер матрици\n"); scanf("%i",&N); THR_NUM = THR; size = N; pthread_t threads; pthread_attr_t attr; printf("allocating\n"); int *m1 = alloc_matrix(size); int *m2 = alloc_matrix(size); int *ans = alloc_matrix(size); srand(time(NULL)); for(int i=0; i

3) Test etme

Intel Atom işlemcide 1000x1000 öğeli matrislerin çarpılması

Elde edilen verilere göre işlemcinin desteklediği hyper threading teknolojisinden dolayı 2 thread üzerinde bir miktar performans artışı meydana geldiği açıkça görülmektedir. İş parçacığı sayısının daha sonra artması performansta bir artışa yol açmadı, aksine yavaşlattı. Ayrıca Pthread kullanarak manuel paralelleştirmenin OpenMP kullanarak otomatik paralelleştirmeden daha etkili olduğu da açıktır.

Intel Xeon işlemcide 1000x1000 öğeli matrislerin çarpılması

Elde edilen verilere göre işlemcinin her iş parçacığı için ayrı bir çekirdek ayırabilmesi nedeniyle 2 ve 4 iş parçacığında performansın arttığı açıktır. Ancak 10 iş parçacıklı bir programı çalıştırmayı denediğimizde performans düşmeye başlar, bu aynı zamanda iş parçacıkları arasında nicemleme için harcanan süre nedeniyle de olur. Bu tablodan çekirdek başına bir iş parçacığı çalıştırmanın en verimli yöntem olduğunu varsayabiliriz (uygulama en iyi performansı 4 iş parçacığında gösterdi). Ayrıca Pthread aracılığıyla manuel paralelleştirmenin OpenMP aracılığıyla otomatik paralelleştirmeden daha etkili olduğu da açıktır.

Sorununuz j iç döngü değişkenindeki bir yarış koşulundan kaynaklanıyor. Özel hale getirilmesi gerekiyor.

C89'da şöyle bir şey yapardım:

#pragma omp paralel ( int i, j, k; #pragma omp for for(i=0; ...

C++ veya C99 için karışık bildirimler kullanın

#pragma omp paralel for(int i=0; ...

Bunu yaparak, kamuya açık veya özel herhangi bir şeyi açıkça beyan etmeniz gerekmez.

Kodunuza bazı ek yorumlar. B[k][j] kullanırken tek iş parçacıklı kodunuz önbelleğe alınmaz. Bu, kajuyu okur, ardından bir sonraki önbellek satırına geçer ve nokta çarpımı yürütülene kadar bu şekilde devam eder; bu sırada diğer pinler çıkarılmış olur. Bunun yerine devrik ilk olarak BT[j][k] olarak aktarılmalı ve erişilmelidir. Ayrıca, tek bir bitişik 2B dizi değil, dizi dizileri ayırdınız. Kodunuzu devrik ve bitişik bir 2B dizi kullanacak şekilde düzelttim.

İşte boyut = 512 için elde ettiğim süre.

Transpoze yok openmp 0,94s transpoze yok, openmp 0,23s transpoze, openmp yok 0,27s transpoze, openmp 0,08s #include #katmak #katmak void transpose(double *A, double *B, int n) ( int i,j; for(i=0; i