Làm thế nào để song song chức năng tinh khiết nhỏ?

Question

Tôi có chương trình D2, ở dạng hiện tại của nó, là đơn luồng, và gọi hàm thuần túy tương tự khoảng 10 đến 100 lần trong vòng lặp bên trong cho mỗi lần lặp của vòng lặp ngoài của chương trình này. Không có sự phụ thuộc dữ liệu giữa các cuộc gọi, tức là không có cuộc gọi nào sử dụng kết quả từ bất kỳ cuộc gọi nào khác. Nhìn chung, chức năng này được gọi là hàng triệu lần, và là nút cổ chai chính trong chương trình của tôi. Các thông số là duy nhất gần như mọi thời gian, do đó, bộ nhớ đệm sẽ không giúp đỡ.

Thoạt nhìn, điều này có vẻ giống như ứng cử viên hoàn hảo để song song. Vấn đề duy nhất là hàm chỉ mất khoảng 3 micro giây cho mỗi cuộc gọi, thấp hơn độ trễ của việc tạo một luồng mới, và không vượt quá mức trên của việc thêm công việc vào một nhóm nhiệm vụ (nghĩa là, có được một mutex, cấp phát bộ nhớ cho giữ thông tin về nhiệm vụ, đối phó với tranh chấp có thể cho hàng đợi của nhóm nhiệm vụ, v.v.). Có cách nào tốt để tận dụng lợi thế của tính song song đó là hạt mịn này?

Answer 1

Điều gì về việc tạo nhiều chuỗi có hàng đợi riêng để hoạt động? Bởi vì không có chồng chéo của các hàng đợi bạn không cần phải tạo khóa.

Answer 2

Tùy thuộc vào cấu trúc chương trình của bạn, bạn luôn có thể kết hợp một nhóm các cuộc gọi thành một nhiệm vụ. Nếu mỗi nhiệm vụ thực hiện 50 cuộc gọi hàm, thì chi phí cho việc quản lý tác vụ không phải là một yếu tố lớn nữa.

Answer 3

Không bắt đầu từng chuỗi để chạy một tác vụ duy nhất, sau đó tắt nó ngay.

Khi bắt đầu chương trình, hãy tạo chuỗi cho mỗi lõi chỉ cần ngồi chờ dữ liệu từ hàng đợi (đường ống hoặc một số cơ chế tạo của riêng bạn). Nếu bạn có thể đưa ra một cơ chế mà tất cả các chủ đề chờ đợi trên cùng một hàng đợi, thậm chí tốt hơn, nhưng sau đó phương thức lấy của hàng đợi sẽ phải được đồng bộ hóa ...

Bất cứ khi nào bạn có một khối hàng trăm hoặc hàng nghìn các quy trình của bạn được tính toán, thả toàn bộ khối vào hàng đợi trống tiếp theo.

Bạn sẽ thực sự kết thúc với một hoặc nhiều luồng cho hàng đợi, một chuỗi các luồng xử lý dữ liệu từ hàng đợi và một hoặc nhiều lần đọc và xử lý kết quả.

Bạn có thể cần phải đặt đủ dữ liệu trong "mục" bạn đang xử lý để có thể biết phải làm gì với chúng sau khi bạn đã hoàn tất. Chúng hầu như chắc chắn là một đối tượng và bạn có thể muốn chúng chứa thông tin trạng thái.

Có thể bạn không muốn nhiều chuỗi xử lý hơn là bạn có lõi.

Chỉnh sửa: Đồng thời xem một số thư viện đồng thời, như ThreadPoolExecutor. Thật dễ dàng để quên thư viện đồng thời (như tôi vừa làm), đó có thể là chính xác những gì bạn đang tìm kiếm (do đó nhấn mạnh)

Answer 4

Điều này nghe giống như hướng dẫn SIMD có thể hữu ích. Nếu bạn đã có một trình biên dịch tự động vector hóa, bạn sẽ có thể viết lại hàm để hoạt động trên 4 giá trị đồng thời, và trình biên dịch có thể ngưng tụ nó thành các lệnh SSE thích hợp. Điều này có thể giúp giảm chi phí cuộc gọi chức năng. Nếu trình biên dịch của bạn không tốt ở mã tự động-vector hóa, thì bạn có thể sử dụng nội tại SSE để giảm gần đến mức lắp ráp để lập trình phần thân của hàm.

Answer 5

Như đã đề xuất ở trên, không khởi động chuỗi mỗi khi bạn nhập hàm này, và hơn thế nữa có độ chi tiết "công việc" lớn hơn một thao tác của hàm bên trong sao cho chi phí tạo việc làm được phân bổ tốt.Mô tả thói quen ban đầu của bạn là một cái gì đó như:

void OuterFunction(Thingy inputData[N]) 
{ 
    for (int i = 0 ; i < N ; ++i) 
    InnerFunction(inputData[i]); 
} 

Chúng tôi muốn giải quyết vấn đề của bạn bằng cách (giả sử một hệ thống hàng đợi công việc hiện tại):

void JobFunc(Thingy inputData[], int start, int stop) 
{ 
    for (int i = start ; i < stop ; ++i) 
    InnerFunction(inputData[i]); 
} 
void OuterFunction(Thingy inputData[N], int numCores) 
{ 
    int perCore = N/numCores; // assuming N%numCores=0 
           // (omitting edge case for clarity) 
    for (int c = 0 ; c < numCores ; ++c) 
    QueueJob(JobFunc, inputData, c * perCore, (c + 1) * perCore); 
} 

Vì vậy, miễn là dữ liệu đầu vào của bạn là hoàn toàn độc lập, như bạn nói trong câu hỏi ban đầu của mình, bạn không cần khóa nó; sự đồng bộ hóa chỉ cần thiết khi có sự phụ thuộc giữa các luồng và ở đây không có gì.

Ngoài ra, ở cấp độ vi mô hiệu suất này bắt đầu trở nên có liên quan: quan trọng nhất, địa phương bộ nhớ cache. Tìm nạp trước có thể giúp bạn có được một chặng đường dài đáng ngạc nhiên.

Sau đó xem xét khả năng của SIMD bạn có thể vector hóa nó để chạy bốn điểm đầu vào thông qua một thanh ghi đơn cùng một lúc. Với bốn lõi và SIMD 4 rộng, bạn có thể về mặt lý thuyết nhận được tốc độ 16x, nhưng điều này giả định rằng công việc InnerFunction đang làm chủ yếu là một hàm toán học cố định, vì phân nhánh có xu hướng xóa bỏ hiệu suất SSE/VMX.

Answer 6

Thật là một câu hỏi thú vị ... như bạn đã lưu ý, bạn sẽ không thể đủ khả năng chi phí liên quan đến khóa truyền thống cho hàng đợi công việc cho việc này. Tôi muốn khuyến khích bạn cố gắng sử dụng một trong những nhiệm vụ dựa trên môi trường lập trình hạt mịn hiện tại nếu bạn có thể ... Tôi nghĩ về điều này trong ba nhóm công việc:

Các đoạn đầu tiên của vấn đề là để đảm bảo an toàn , tính đúng đắn và tính song song, và có vẻ như bạn đã được bảo vệ bởi vì hàm của bạn là thuần khiết.

Tôi nghĩ phần khó khăn nhất tiếp theo là mô tả đồng thời, cụ thể là bạn đề cập đến hàm này được gọi nhiều lần. Bạn có thể đường ống dẫn này và lập lịch biểu riêng biệt chức năng từ công việc của nó không? Nếu bạn không thể làm đường ống này, nó trông giống như một vòng lặp song song, một cây traversal hoặc là nó không có cấu trúc hơn này. Cụ thể, obeying Amdahl nếu bạn không thể chồng chéo công việc và đảm bảo rằng có một số trường hợp của nó hoặc một cái gì đó khác đang chạy cùng một lúc, bạn có hiệu quả nối tiếp ngay cả khi bạn là tinh khiết. Bất cứ điều gì bạn có thể làm để tái cấu trúc công việc thành một đường ống, một cây chuyển tiếp đệ quy (hoặc vòng lặp song song) hoặc nếu bạn phải làm việc không có cấu trúc với phụ thuộc explicity giữa các tác vụ sẽ giúp ở đây bất kể thư viện được sử dụng.

Khu vực cuối cùng tôi nghĩ đến là đảm bảo thực hiện hiệu quả trên nền tảng của bạn và điều này liên quan đến việc giảm chi phí và tranh chấp trong cả mã và mã lập lịch và đảm bảo rằng mã nối tiếp hoàn toàn hiệu quả nhất có thể. Nếu bạn không thể sử dụng một trong các thư viện hiện có và phải xây dựng thư viện của riêng mình, tôi khuyên bạn nên xem một số thuật toán lập lịch tự định hướng work-stealing queue, như bạn đã lưu ý, bạn sẽ không thể thấy lợi ích từ việc sử dụng ổ khóa truyền thống vì chi phí của chúng cao hơn chi phí chức năng của bạn và rất có thể bạn sẽ cần phải xem xét kỹ thuật không có khóa để giảm chi phí lên lịch và xóa nhiệm vụ vào bất kỳ hàng đợi nào bạn sử dụng. Bạn cũng sẽ cần phải chú ý nhiều đến việc chia sẻ và tranh chấp cả trong thuật toán lập lịch và trong chức năng của bạn, bởi vì ở mức độ chi tiết này ngoài các vấn đề thông thường và thông báo hướng dẫn chi tiết thông thường, bạn cũng cần phải xem xét tại shared state and contention even on reads because they can be sources of contention too.

Tôi xin lỗi nếu điều này không quá cụ thể, nhưng tôi hy vọng nó hữu ích.

Answer 7

bạn có thể có thể xoay vòng trong ra ngoài sử dụng so sánh-and-Swap để có được một khóa nguyên tử tăng miễn phí:

void OuterFunction() 
{ 
    for(int i = 0; i < N; i++) 
    InnerFunction(i); 
} 

đi:

void OuterFunction() 
{ 
    int i = 0, j = 0; 

    void Go() 
    { 
     int k; 
     while((k = atomicInc(*i)) < N) 
     { 
     InnerFunction(k); 

     atomicInc(*j); 
     } 
    } 

    for(int t = 0; t < ThreadCount - 1; t++) Thread.Start(&Go); 

    Go(); // join in 

    while(j < N) Wait(); // let everyone else catch up. 
} 

---

Sửa : luồng của tôi bị gỉ nên không biên dịch được vì tất cả các tên đều sai.

Answer 8

Không có sự phụ thuộc dữ liệu giữa các cuộc gọi, tức là không có cuộc gọi nào sử dụng kết quả từ bất kỳ cuộc gọi nào khác.

Điều đó sẽ giúp song song, nhưng hoàn toàn chắc chắn rằng chức năng không có tác dụng phụ nào cả. Nếu chức năng đang cập nhật cấu trúc dữ liệu, nó có an toàn không? Nếu nó làm IO, IO sẽ chỉ kết thúc là một nút cổ chai nếu bạn quản lý để thực hiện song song chức năng?

Nếu câu trả lời là "có" cho các câu hỏi này thì các đề xuất trước đó là tốt, chỉ cần cố gắng tối đa hóa mức độ chi tiết của ứng dụng bằng cách gán các hàm thực thi cho càng nhiều càng tốt cho mỗi chuỗi.

Tuy nhiên, có thể bạn sẽ không nhận được bất kỳ lợi ích nào từ tính song song khổng lồ, nhưng có thể có một số tăng tốc khiêm tốn hơn có thể có ...