SIMD có đáng giá không? Có lựa chọn nào tốt hơn không?

Question

Tôi có một số mã chạy khá tốt, nhưng tôi muốn làm cho nó chạy tốt hơn. Vấn đề chính tôi có với nó là nó cần phải có một vòng lặp lồng nhau. Cái bên ngoài là cho các phép lặp (mà phải xảy ra serially), và cái bên trong là cho từng hạt điểm được xem xét. Tôi biết không có nhiều tôi có thể làm gì về người ngoài, nhưng tôi đang tự hỏi nếu có một cách tối ưu hóa một cái gì đó như:

void collide(particle particles[], box boxes[], 
     double boxShiftX, double boxShiftY) {/*{{{*/ 
      int i; 
      double nX; 
      double nY; 
      int boxnum; 
      for(i=0;i<PART_COUNT;i++) { 
        boxnum = ((((int)(particles[i].sX+boxShiftX))/BOX_SIZE)%BWIDTH+ 
         BWIDTH*((((int)(particles[i].sY+boxShiftY))/BOX_SIZE)%BHEIGHT)); 
         //copied and pasted the macro which is why it's kinda odd looking 

        particles[i].vX -= boxes[boxnum].mX; 
        particles[i].vY -= boxes[boxnum].mY; 
        if(boxes[boxnum].rotDir == 1) { 
          nX = particles[i].vX*Wxx+particles[i].vY*Wxy; 
          nY = particles[i].vX*Wyx+particles[i].vY*Wyy; 
        } else { //to make it randomly pick a rot. direction 
          nX = particles[i].vX*Wxx-particles[i].vY*Wxy; 
          nY = -particles[i].vX*Wyx+particles[i].vY*Wyy; 
        } 
        particles[i].vX = nX + boxes[boxnum].mX; 
        particles[i].vY = nY + boxes[boxnum].mY; 
      } 
    }/*}}}*/ 

Tôi đã nhìn vào SIMD, mặc dù tôi không thể tìm thấy nhiều về nó, và tôi không hoàn toàn chắc chắn rằng việc xử lý cần thiết để trích xuất và đóng gói dữ liệu đúng sẽ đáng để đạt được một nửa như nhiều hướng dẫn, vì dường như chỉ có hai đôi có thể được sử dụng tại một thời điểm.

Tôi đã cố gắng chia nhỏ thành nhiều chuỗi với shm và pthread_barrier (để đồng bộ hóa các giai đoạn khác nhau, trong đó mã ở trên là một), nhưng nó chỉ làm cho nó chậm hơn.

Mã hiện tại của tôi không hoạt động khá nhanh; đó là thứ tự của một giây cho mỗi lần lặp 10 triệu hạt * và từ những gì tôi có thể nói từ gprof, 30% thời gian của tôi chỉ dành cho chức năng đó (5000 cuộc gọi; PART_COUNT = 8192 hạt mất 1,8 giây). Tôi không lo lắng về những thứ thời gian nhỏ, liên tục, nó chỉ là các hạt 512K * 50K lần lặp * 1000 thử nghiệm mất hơn một tuần thời gian qua.

Tôi đoán câu hỏi của tôi là nếu có bất kỳ cách nào để xử lý các vectơ dài này hiệu quả hơn là chỉ lặp qua chúng. Tôi cảm thấy như có nên, nhưng tôi không thể tìm thấy nó.

Answer 1

Tôi không chắc chắn SIMD sẽ hưởng lợi bao nhiêu; các vòng lặp bên trong là khá nhỏ và đơn giản, vì vậy tôi đoán (chỉ bằng cách tìm kiếm) rằng bạn có thể nhiều bộ nhớ ràng buộc hơn bất cứ điều gì khác. Với ý nghĩ đó, tôi muốn thử viết lại phần chính của vòng lặp để không chạm vào mảng hạt hơn cần thiết:

const double temp_vX = particles[i].vX - boxes[boxnum].mX; 
const double temp_vY = particles[i].vY - boxes[boxnum].mY; 

if(boxes[boxnum].rotDir == 1) 
{ 
    nX = temp_vX*Wxx+temp_vY*Wxy; 
    nY = temp_vX*Wyx+temp_vY*Wyy; 
} 
else 
{ 
    //to make it randomly pick a rot. direction 
    nX = temp_vX*Wxx-temp_vY*Wxy; 
    nY = -temp_vX*Wyx+temp_vY*Wyy; 
} 
particles[i].vX = nX; 
particles[i].vY = nY; 

này có tác dụng phụ tiềm năng nhỏ không làm việc bổ sung thêm vào cuối.

---

Một tăng tốc tiềm năng sẽ được sử dụng __restrict trên mảng hạt, do đó trình biên dịch có thể tối ưu hóa tốt hơn ghi vào vận tốc. Ngoài ra, nếu Wxx vv là các biến toàn cầu, chúng có thể phải tải lại mỗi lần thông qua vòng lặp thay vì có thể được lưu trong sổ đăng ký; sử dụng __restrict cũng sẽ giúp ích với điều đó.

---

Vì bạn đang truy cập vào các hạt theo thứ tự, bạn có thể thử tìm nạp trước (ví dụ __builtin_prefetch trên GCC) một vài hạt về phía trước để giảm bỏ lỡ bộ nhớ cache. Tìm nạp trước trên các hộp khó khăn hơn một chút vì bạn đang truy cập chúng theo thứ tự không thể đoán trước; bạn có thể thử một cái gì đó giống như

int nextBoxnum = ((((int)(particles[i+1].sX+boxShiftX) /// etc... 
// prefetch boxes[nextBoxnum] 

---

Một người cuối cùng mà tôi chỉ chú ý - nếu hộp :: rotDir luôn +/- 1.0, sau đó bạn có thể loại bỏ sự so sánh và chi nhánh trong vòng lặp bên trong như thế này:

const double rot = boxes[boxnum].rotDir; // always +/- 1.0 
nX =  particles[i].vX*Wxx + rot*particles[i].vY*Wxy; 
nY = rot*particles[i].vX*Wyx +  particles[i].vY*Wyy; 

---

Đương nhiên, hãy cẩn thận thông thường của hồ sơ trước và sau khi áp dụng. Nhưng tôi nghĩ rằng tất cả những điều này có thể hữu ích, và có thể được thực hiện bất kể bạn có chuyển sang SIMD hay không.

Answer 2

Bạn có đủ hồ sơ để cho bạn biết thời gian được sử dụng trong hàm đó không? Ví dụ:

Ví dụ: bạn có chắc chắn đó không phải là div và mod của bạn trong tính toán số hộp khi thời gian đang được sử dụng? Đôi khi các trình biên dịch không phát hiện ra các lựa chọn thay thế/thay thế có thể, ngay cả khi một con người (hoặc ít nhất, một người biết BOX_SIZE và BWIDTH/BHEIGHT, mà tôi không) có thể có khả năng.

Nó sẽ là một điều đáng tiếc phải tốn nhiều thời gian trên SIMDifying bit sai của mã ...

Một điều khác mà có thể là giá trị xem xét là nếu công việc có thể bị cưỡng chế vào một cái gì đó mà có thể làm việc với một thư viện như IPP, sẽ đưa ra quyết định sáng suốt về cách tốt nhất để sử dụng bộ xử lý.

Answer 3

((int)(particles[i].sX+boxShiftX))/BOX_SIZE 

Điều đó đắt nếu sX là int (không thể biết). Truncate boxShiftX/Y thành int trước khi vào vòng lặp.

Answer 4

Chỉ để lưu nội dung, cũng có libSIMDx86!

http://simdx86.sourceforge.net/Modules.html

(On biên dịch bạn cũng có thể thử: gcc-O3 -msse2 hoặc tương tự).

Answer 5

Thuật toán của bạn có quá nhiều hướng dẫn về bộ nhớ, số nguyên và nhánh để có đủ số lần gỡ bỏ độc lập để thu lợi nhuận từ SIMD. Các đường ống sẽ liên tục bị đình trệ.

Tìm một cách hiệu quả hơn để ngẫu nhiên hóa sẽ là đầu danh sách. Sau đó, cố gắng làm việc trong float hoặc int, nhưng không phải cả hai. Tái xử lý các điều kiện dưới dạng số học, hoặc ít nhất là một phép toán chọn lọc. Chỉ sau đó SIMD mới trở thành đề xuất thực tế