Vấn đề tốc độ với mảng C lớn sử dụng 64bit Visual C

Question

Tôi cần đọc một lượng lớn dữ liệu vào bộ đệm (khoảng 20gig). Tôi có 192gb DDram rất nhanh, vì vậy không có vấn đề với kích thước bộ nhớ. Tuy nhiên, tôi thấy rằng các mã sau chạy chậm hơn và chậm hơn nữa nó được vào bộ đệm. Trình lược tả Visual C cho tôi biết rằng 68% thời gian thực hiện 12 phút là trong 2 câu lệnh bên trong vòng lặp trong myFunc(). Tôi đang chạy win7, 64bit trên một dell rất nhanh với 2 cpu, 6 lõi vật lý mỗi (24 lõi logic), và tất cả 24 lõi là hoàn toàn maxed trong khi chạy này.

#define TREAM_COUNT 9000 
#define ARRAY_SIZE ONE_BILLION 

#define offSet(a,b,c,d) (((size_t) ARRAY_SIZE * (a)) + ((size_t) TREAM_COUNT * 800 * (b)) + ((size_t) 800 * (c)) + (d)) 

void myFunc(int dogex, int ptxIndex, int xtreamIndex, int carIndex) 
{ 
    short *ptx = (short *) calloc(ARRAY_SIZE * 20, sizeof(short)); 

    #pragma omp parallel for 
    for (int bIndex = 0; bIndex < 800; ++bIndex) 
      doWork(dogex, ptxIndex, carIndex); 
} 

void doWork(int dogex, int ptxIndex, int carIndex) 
{ 

    for (int treamIndex = 0; treamIndex < ONE_BILLION; ++treamIndex) 
    { 
     short ptxValue  = ptx[ offSet(dogex, ptxIndex, treamIndex, carIndex) ]; 
     short lastPtxValue = ptx[ offSet(dogex, ptxIndex-1, treamIndex, carIndex) ]; 

     // .... 
    } 

} 

Answer 1

Mã được phân bổ 20 khối của một tỷ ints ngắn. Trên hộp Windows 64 bit, một int ngắn là 2 byte. Vì vậy, phân bổ là ~ 40 gigabyte.

Bạn nói có 24 lõi và tất cả chúng đều được max. Các mã như nó không xuất hiện để hiển thị bất kỳ song song. Cách thức mã song song có thể có ảnh hưởng sâu sắc đến hiệu suất. Bạn có thể cần phải cung cấp thêm thông tin.

-

Vấn đề cơ bản của bạn, tôi nghi ngờ, xoay quanh hành vi bộ nhớ cache và giới hạn truy cập bộ nhớ.

Đầu tiên, với hai CPU vật lý gồm 6 lõi, bạn sẽ hoàn toàn bão hòa bus bộ nhớ của mình. Có thể bạn có kiến ​​trúc NUMA, nhưng không có kiểm soát trong mã về nơi mà calloc() của bạn phân bổ (ví dụ: bạn có thể có nhiều mã được lưu trữ trong bộ nhớ yêu cầu nhiều bước nhảy để tiếp cận).

Siêu phân luồng được bật. Điều này có hiệu quả một nửa kích thước bộ nhớ cache. Với mã là bus bộ nhớ bị ràng buộc, thay vì tính toán ràng buộc, siêu phân luồng có hại. (Có nói rằng, nếu tính toán là liên tục bên ngoài của giới hạn bộ nhớ cache anyway, điều này sẽ không thay đổi nhiều).

Mã không rõ ràng (vì một số/nhiều?) Bị xóa, cách truy cập mảng và mẫu truy cập và tối ưu hóa mẫu đó để tôn vinh tối ưu hóa bộ nhớ cache là chìa khóa để thực hiện.

Những gì tôi thấy trong cách bù đắp() được tính là mã liên tục yêu cầu tạo ra các tra cứu địa chỉ ảo mới đến vật lý - mỗi cái đòi hỏi phải có bốn hoặc năm truy cập bộ nhớ. Đây là hiệu suất kiling, của chính nó.

Lời khuyên cơ bản của tôi là chia mảng thành các khối có kích thước bộ nhớ cache cấp 2, cấp một khối cho mỗi CPU và để cho nó xử lý khối đó. Bạn có thể làm điều đó song song. Trên thực tế, bạn có thể sử dụng siêu phân luồng để tải trước bộ nhớ cache, nhưng đó là một kỹ thuật nâng cao hơn.

Answer 2

tối ưu hóa này sẽ thoát khỏi các phép nhân chậm:

... 
    int idx1 = offSet(dogex, ptxIndex, 0, carIndex); 
    int idx2 = offSet(dogex, ptxIndex-1, 0, carIndex); 

    for (int treamIndex = 0; treamIndex < ONE_BILLION; ++treamIndex) 
    {    
     short ptxValue  = ptx[ idx1 ]; 
     short lastPtxValue = ptx[ idx2 ]; 
     idx1+=800; 
     idx2+=800;    ... 

Answer 3

Bạn nên cố gắng truy cập vào mảng trong thời trang tuyến tính hơn nếu có thể. Điều này có thể gây ra số lượng bộ nhớ cache quá nhiều.

Answer 4

Tôi nghĩ, vấn đề của mã này là mẫu truy cập bộ nhớ của nó. Thực tế là mỗi chuỗi truy cập bộ nhớ với số gia tăng lớn (2 * 800 byte) có 2 hậu quả tiêu cực:

1. Khi bắt đầu, tất cả các chuỗi truy cập cùng một bộ nhớ, được tải sẵn vào bộ đệm L2/L3 và hiệu quả được sử dụng bởi mọi chuỗi. Sau đó, các chủ đề tiến hành với tốc độ hơi khác và truy cập các phần khác nhau của bộ nhớ, dẫn đến việc truy xuất bộ nhớ cache (một luồng tải dữ liệu vào bộ nhớ cache và truy vấn dữ liệu từ đó, mà chưa được đọc bởi các chủ đề khác, cần).Kết quả là, cùng một phần của bộ nhớ được đọc vào bộ nhớ cache nhiều lần (trong trường hợp xấu nhất, 12 lần, bởi số lượng các chủ đề trong một CPU). Vì bus bộ nhớ tương đối chậm nên điều này làm chậm toàn bộ chương trình.
2. Bộ nhớ cache L1 cũng được sử dụng không hiệu quả lắm: chỉ một phần nhỏ dữ liệu trong mỗi dòng bộ đệm được sử dụng bởi lõi CPU.

Giải pháp là để cho phép mỗi thread để truy cập tuần tự bộ nhớ (như trao đổi c và d lập luận của offSet(a,b,c,d) vĩ mô).