Uygulama Cannon algoritması

Question

Arka Plan

I boyutta kare ve boyut işlemci sayısının kare kökü ile bölünebilir matris çarpma paralel bir algoritma Cannon's Algorithm uygulamak gerekir. Mükemmel bir şekilde çalışan bu kodu yazdım ama hayatımda çarpmadan koşmak sadece hikayenin yarısı. A x B'yi yeni bir matris C'ye doğru çarpmaz. İşte kod, lütfen bana yardım edin ve yanlış yaptığım şeyi çözmemde bana yardımcı ol. Açık olması gerektiği gibi bu ev ödevidir.

Kod yanlış neler oluyor inanıyorum

void shift_left(datatype** mat, int s, int row, int n, int amount) { 
    datatype* temp_buffer = malloc(sizeof(datatype) * n); 
    for(int col = 0; col < n; col++) { 
     datatype temp = mat[row][(col+amount)%s]; 
     temp_buffer[(col+amount)%s] = mat[row][col]; 
     temp_buffer[col] = temp; 
    } 
    memcpy(mat[row], temp_buffer, n); 
    free(temp_buffer); 
} 

void shift_up(datatype** mat, int s, int col, int n, int amount) { 
    datatype* temp_buffer = malloc(sizeof(datatype) * n); 
    for(int row = 0; row < n; row++) { 
     datatype temp = mat[(row+amount)%s][col]; 
     temp_buffer[(row+amount)%s] = mat[row][col]; 
     temp_buffer[row] = temp; 
    } 
    memcpy(&mat[0][col], temp_buffer, n); 
    free(temp_buffer); 
} 

void cannon_mul(int p_sqrt,datatype** a, datatype** b, datatype** c, int n) { 
    /* 2D matrices and n^2 sized only!*/ 
    int i = 0, j = 0, k = 0; 
    int s = p_sqrt; 
    for(i = 0; i < (s-1); i++) { 
     shift_left(a, s, i, s-1, i); // Skew matrix a 
    } 
    for (i = 0; i < (s-1); i++) { 
     shift_up(b, s, i, s-1, i); // Skew matrix b 
    } 
    for(k = 0; k < (s-1); k++) { 
     for(i = 0; i < (s-1); i++) { 
      for(j = 0; j < (s-1); j++) { 
       c[i][j] += a[i][j]*b[i][j]; 
       shift_left(a, s, i, s-1, 1); 
       shift_up(b, s, i, s-1, 1); 
      }      
     } 
    } 
} 

?

Önsezim yanlıştır ya da algoritmanın önemli bir bölümünü kaçırıyorum. Orijinal vardiya fonksiyonum geçici bir tampon kullanmıyordu, bu yüzden geçici bir tampon kullanmak istedim ama bu bir fark yaratmadı. Eğer yardımcı olursa bazı örnek çıktıları gösterebilirdim ama sonuç, istenen sonuca uzaktan bile yakın bir şekildedeğil. İyi haber hızlı :)

Sonuçları kendisiyle yukarıda benim koduyla ürettiği matrisi çarpılarak

1.48 0.14 9.47 8.99 8.06 0.06 6.68 1.04 4.44 7.50 
7.26 8.87 2.21 6.27 2.12 7.91 0.65 5.24 0.45 4.94 
0.47 4.13 1.87 2.25 6.83 1.52 6.41 9.14 9.22 8.91 
7.34 2.70 6.78 2.78 3.51 4.95 5.27 0.85 9.51 6.82 
0.28 6.73 0.70 8.88 7.14 9.09 2.36 5.38 6.43 9.00 
7.13 6.71 6.92 9.81 5.13 9.35 7.50 5.16 4.68 3.62 
1.30 6.26 4.55 4.27 0.51 2.23 3.19 8.75 6.57 9.07 
7.49 6.41 1.04 7.78 7.16 2.78 2.25 6.23 9.42 0.32 
3.21 3.60 2.04 2.93 4.29 3.88 2.78 8.01 4.57 6.47 
7.52 3.77 0.63 5.97 7.32 4.90 9.63 4.90 8.46 1.90 

çalışır bu:

163.41 212.17 144.32 227.10 251.03 205.60 245.63 277.33 368.99 334.11 
257.85 230.82 203.60 314.08 246.02 240.12 228.37 197.90 264.38 228.24 
234.13 272.10 110.75 294.84 263.16 242.07 209.54 316.13 339.23 260.51 
185.33 215.59 192.26 283.31 270.80 208.38 265.08 291.49 312.24 319.73 
313.23 301.95 182.04 348.11 283.20 337.49 266.54 284.57 355.28 281.07 
293.25 323.29 281.35 393.92 325.24 313.62 313.48 342.95 418.37 401.91 
255.88 238.25 122.17 254.52 243.58 204.49 217.69 273.03 314.89 214.45 
219.26 239.07 200.18 309.98 262.21 242.68 190.02 245.85 297.96 308.56 
209.03 213.11 126.24 266.48 233.88 199.33 193.28 228.92 277.50 202.27 
210.31 264.67 227.59 337.79 261.40 250.35 225.77 295.00 331.92 352.17 

:

2.20 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
50.81 0.00 0.00 0.00 0.00 87.51 0.00 0.00 0.00 0.00 
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 
0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 

sıralı program bu sonuç üretir

İlgili portioyu gösterdiğimi not etmek önemlidir Programımı ns daha fazla göstermem gerektiğini düşünüyorsanız lütfen bunu yapın ve daha fazla kod sağlayacağım. Son olarak Ödev etiketi neden eksik?

Düzenleme

Bir kişi tampon küçük oldu ve aptalca hata sizeof eksikti ve şimdi düzeltilmiş olduğunu kaydetti. Denedim ve aynı sonucu elde ettim, görünüşe göre sorun bununla ilgili bir şey değil. İnşallah 2 gün içinde, bir kişinin en azından sorunun nerede olduğu hakkında bir ipucu vermesi için ikna etmek için bir ödül açabilirim. Bu hata ayıklamak için görünmüyor bir hata, ve benim bu algoritma kabul etmek benim anlayışım sıfır sıfırdır. Anlayışımı arttırmak için çok az şey yapan web kaynaklarına güveniyorum.

Düzenleme 2

tampon tahsis sıfır calloc kullanarak çalıştı ancak sonuç değişmez. Çok garip ama bunu önerdiğiniz için teşekkürler; Hafızanın sıfırlandığını unuttum.

void shift_left(datatype** mat, int s, int row, int n, int amount) { 

    datatype* temp_buffer = calloc(n, sizeof(datatype) * n); 
    for(int col = 0; col < n; col++) { 
     /* temp_buffer[(col+amount)%s] = mat[row][col]; 
     temp_buffer[col] = mat[row][(col+amount)%s]; */ 
     temp_buffer[(col+amount)%s] = 0; 
     temp_buffer[col] = 0; 
    } 
    memcpy(mat[row], temp_buffer, sizeof(datatype) * n); 
    //free(temp_buffer); 

} 

void shift_up(datatype** mat, int s, int col, int n, int amount) { 
    datatype* temp_buffer = calloc(n, sizeof(datatype) * n); 
    for(int row = 0; row < n; row++) { 
     /* temp_buffer[(row+amount)%s] = mat[row][col]; 
     temp_buffer[row] = mat[(row+amount)%s][col]; */ 
     temp_buffer[(row+amount)%s] = 0; 
     temp_buffer[row] = 0; 
    } 
    memcpy(&mat[0][col], temp_buffer, sizeof(datatype) * n); 
    free(temp_buffer); 
} 

Ve şaşırtıcı aynı sonucu: 3

Düzenleme Bu çalıştı. Kodu sıfırladığım ve sıfır ile değiştirdiğim zaman sıfır yazılması gerektiğinde. Benim tahminim memcpy çalışmıyor.

Düzenleme 4

Ben memcpy suçlu olduğunu doğruladı.Ama neden bilemediğimi bilemiyorum, eğer veri tipine yardımcı olsaydı, sadece bir takma addır, profesör, kodun daha okunaklı olmasına yardımcı olmadığından bazı garip nedenlerden dolayı yazdı.

Ama eğer bunu kendi başıma çözersem, sorunumun çözümünü göstermekten memnun olurum.

Answer 1

Kopyalama çok küçük. memcpy(&mat[0][col], temp_buffer, n);

Answer 2

Kapsam dışı bir by-one hata gibi bana benzediğini var için aynı

// memcpy(mat[row], temp_buffer, n); 
memcpy(mat[row], temp_buffer, n * sizeof(datatype)); 

. Sizin cannon_mul

bu döngüler vardır:

for(i = 0; i < (s-1); i++) 

for (i = 0; i < (s-1); i++) 

for(k = 0; k < (s-1); k++) 
    for(i = 0; i < (s-1); i++) 
     for(j = 0; j < (s-1); j++) 

Ancak http://www.cs.berkeley.edu/~demmel/cs267/lecture11/lecture11.html#link_5 de ilgili kaynak malzeme ne inanıyorum içinde, yalancı kod diyor ki:

for all (i=0 to s-1) 

for all (i=0 to s-1) 

for k=0 to s-1 
    for all (i=0 to s-1, j=0 to s-1) 

Ben oldukça emin araçları değilim olanı Döngü değişkenleri , döngünün son yinelemesinde s-1 değerini almalıdır. Döngü değişkenleriniz hiçbir zamans-1 değerini almaz.

Döngülerinizi <= (s-1) olarak değiştirmeyi deneyin ve bunun yardımcı olup olmadığını görün.