Khung song song và tránh chia sẻ sai

Question

Gần đây, tôi đã trả lời một câu hỏi về việc tối ưu hóa một phương thức song song có khả năng để tạo ra mọi hoán vị của các số cơ số tùy ý. Tôi đã đăng một câu trả lời tương tự như song song, người nghèo thực hiện danh sách khối mã, và ai đó gần ngay lập tức chỉ ra điều này:

này được khá nhiều đảm bảo sẽ cung cấp cho bạn chia sẻ sai và có lẽ sẽ có nhiều thời gian chậm hơn. (Tín dụng để gjvdkamp)

và họ đã đúng, đó là chết chậm. Điều đó nói rằng, tôi đã nghiên cứu chủ đề, và tìm thấy một số interesting material and suggestions để chống lại nó. Nếu tôi hiểu nó một cách chính xác, khi các luồng truy cập bộ nhớ tiếp giáp (trong đó, mảng có khả năng sao lưu ConcurrentStack), khả năng chia sẻ sai có thể xảy ra.

---

Đối với mã dưới sự cai trị ngang, một Bytes là:

struct Bytes { 
    public byte A; public byte B; public byte C; public byte D; 
    public byte E; public byte F; public byte G; public byte H; 
} 

Đối với thử nghiệm của riêng tôi, tôi muốn để có được một phiên bản song song của chạy này và được thực sự nhanh hơn, vì vậy tôi đã tạo ra một đơn giản ví dụ dựa trên mã ban đầu. 6 là limits[0] là một lựa chọn lười biếng về phía tôi - máy tính của tôi có 6 lõi.

Độc chủ đề khốiTrung bình thời gian chạy: 10s0059ms

var data = new List<Bytes>(); 
    var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 }; 

    for (byte a = 0; a < limits[0]; a++) 
    for (byte b = 0; b < limits[1]; b++) 
    for (byte c = 0; c < limits[2]; c++) 
    for (byte d = 0; d < limits[3]; d++) 
    for (byte e = 0; e < limits[4]; e++) 
    for (byte f = 0; f < limits[5]; f++) 
    for (byte g = 0; g < limits[6]; g++) 
    for (byte h = 0; h < limits[7]; h++) 
    data.Add(new Bytes { 
     A = a, B = b, C = c, D = d, 
     E = e, F = f, G = g, H = h 
    }); 

song song, thực hiện kémRun thời gian trung bình: 81s729ms, ~ 8700 contentions

var data = new ConcurrentStack<Bytes>(); 
    var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 }; 

    Parallel.For(0, limits[0], (a) => { 
    for (byte b = 0; b < limits[1]; b++) 
    for (byte c = 0; c < limits[2]; c++) 
    for (byte d = 0; d < limits[3]; d++) 
    for (byte e = 0; e < limits[4]; e++) 
    for (byte f = 0; f < limits[5]; f++) 
    for (byte g = 0; g < limits[6]; g++) 
    for (byte h = 0; h < limits[7]; h++) 
     data.Push(new Bytes { 
     A = (byte)a,B = b,C = c,D = d, 
     E = e,F = f,G = g,H = h 
     }); 
    }); 

song song, ?? thực hiệnRun thời gian trung bình: 5s833ms, 92 luận điểm

var data = new ConcurrentStack<List<Bytes>>(); 
    var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 }; 

    Parallel.For (0, limits[0],() => new List<Bytes>(), 
    (a, loop, localList) => { 
     for (byte b = 0; b < limits[1]; b++) 
     for (byte c = 0; c < limits[2]; c++) 
     for (byte d = 0; d < limits[3]; d++) 
     for (byte e = 0; e < limits[4]; e++) 
     for (byte f = 0; f < limits[5]; f++) 
     for (byte g = 0; g < limits[6]; g++) 
     for (byte h = 0; h < limits[7]; h++) 
     localList.Add(new Bytes { 
      A = (byte)a, B = b, C = c, D = d, 
      E = e, F = f, G = g, H = h 
     }); 
     return localList; 
    }, x => { 
    data.Push(x); 
    }); 

Tôi rất vui vì tôi đã có một thực hiện đó là nhanh hơn so với phiên bản đơn luồng. Tôi mong đợi một kết quả gần với khoảng 10s/6, hoặc khoảng 1,6 giây, nhưng đó có lẽ là một kỳ vọng ngây thơ.

Câu hỏi của tôi là cho việc triển khai song song thực sự nhanh hơn phiên bản một luồng, có thêm tối ưu hóa nào có thể áp dụng cho hoạt động không? Tôi đang tự hỏi về tối ưu hóa liên quan đến song song, không cải tiến cho thuật toán được sử dụng để tính giá trị. Cụ thể là:

• tôi biết về việc tối ưu hóa để lưu trữ và cư như một struct thay vì byte[], nhưng nó không liên quan đến song song (hoặc là nó?)
• Tôi biết rằng một giá trị mong muốn có thể được lười biếng đánh giá với trình bổ sung mang theo gợn sóng, nhưng giống như tối ưu hóa struct.

Answer 1

Trước hết, giả định ban đầu của tôi về Parallel.For() và Parallel.ForEach() là sai.

Việc triển khai song song kém có khả năng có 6 luồng tất cả cố gắng ghi vào một đơn CouncurrentStack() cùng một lúc. Việc triển khai tốt sử dụng các địa phương luồng (được giải thích thêm bên dưới) chỉ truy cập biến chia sẻ một lần cho mỗi tác vụ, gần như loại bỏ bất kỳ tranh chấp nào.

Khi sử dụng Parallel.For() và Parallel.ForEach(), bạn có thể không chỉ đơn giản là in-line thay thế một for hoặc foreach vòng lặp với họ. Đó không phải để nói rằng nó không thể là một cải tiến mù, nhưng mà không kiểm tra vấn đề và dụng cụ nó, sử dụng chúng là ném đa luồng tại một vấn đề bởi vì nó có thể làm cho nó nhanh hơn.

** Parallel.For() và Parallel.ForEach() có tình trạng quá tải cho phép bạn tạo trạng thái cục bộ cho Task cuối cùng chúng tạo và chạy biểu thức trước và sau mỗi lần thực hiện lặp lại.

Nếu bạn có một hoạt động bạn parallelize với Parallel.For() hoặc Parallel.ForEach(), nó có khả năng là một ý tưởng tốt để sử dụng quá tải này:

public static ParallelLoopResult For<TLocal>(
    int fromInclusive, 
    int toExclusive, 
    Func<TLocal> localInit, 
    Func<int, ParallelLoopState, TLocal, TLocal> body, 
    Action<TLocal> localFinally 
) 

Ví dụ, gọi For() để tổng hợp tất cả các số nguyên từ 1 đến 100,

var total = 0; 

Parallel.For(0, 101,() => 0, // <-- localInit 
(i, state, localTotal) => { // <-- body 
    localTotal += i; 
    return localTotal; 
}, localTotal => { <-- localFinally 
    Interlocked.Add(ref total, localTotal); 
}); 

Console.WriteLine(total); 

localInit phải là một lambda khởi tạo loại trạng thái cục bộ, được chuyển đến các số body và localFinally lambdas. Xin lưu ý tôi không đề xuất thực hiện tổng hợp từ 1 đến 100 bằng cách sử dụng song song, nhưng chỉ có một ví dụ đơn giản để làm ví dụ ngắn.