Thuật toán heuristic để cân bằng tải giữa các chủ đề

Question

Tôi đang làm việc trên một chương trình đa luồng, trong đó tôi có một số chuỗi công việc thực hiện các tác vụ có độ dài không bằng nhau. Tôi muốn cân bằng tải các tác vụ để đảm bảo rằng chúng hoạt động gần như giống nhau. Đối với mỗi công việc T _i Tôi có một số c _i cung cấp một xấp xỉ gần đúng với số lượng công việc cần thiết cho nhiệm vụ đó.

Tôi đang tìm một thuật toán hiệu quả (O (N) N = số nhiệm vụ hoặc tốt hơn) sẽ cho tôi "gần" một số dư tải tốt cho các giá trị của c _i. Nó không phải là tối ưu, nhưng tôi muốn có thể có một số giới hạn lý thuyết về cách phân bổ kết quả xấu như thế nào.

Bất kỳ ý tưởng nào?

Answer 1

Bạn muốn triển khai thuật toán đánh cắp công việc. Mỗi luồng công nhân có một hàng đợi đã kết thúc gấp đôi, các tác vụ mới được thêm vào cuối hàng đợi nhỏ nhất. Người lao động loại bỏ các nhiệm vụ từ đầu hàng đợi của riêng họ (tách trên cùng/dưới làm giảm tranh chấp), khi một công nhân không có nhiều việc phải làm, nó đánh cắp công việc ở dưới cùng của hàng đợi lớn nhất. Nó đơn giản, và hoạt động tốt, đây là thuật toán mà hệ thống song song của Microsoft đi kèm với .net4.0 dựa trên tôi tin tưởng.

Phân bổ kết quả là khá tốt, các chuỗi công việc sẽ chỉ được để lại mà không cần phải làm gì nếu không có thêm công việc nào có sẵn trong toàn bộ hệ thống.

Nb. Nếu bạn muốn một số mã ví dụ xé toạc, người bạn của tôi đã viết một hệ thống trộm cắp công việc cho C#, bạn có thể tìm thấy here

Answer 2

Trong O (N) điều này có vẻ dễ dàng.

Cung cấp cho mỗi chuỗi một số "điểm". Để p_i các điểm được phân bổ cho luồng T_i. Đối với mỗi tác vụ, chọn chủ đề có số cao nhất p_i và trừ chi phí nhiệm vụ từ p_i. Sau đó bạn chỉ cần theo dõi các chủ đề được sắp xếp theo điểm số, điều này là không đáng kể trong thời gian O (N), và có thể dễ dàng được thực hiện trong O (log N) với một cây cân bằng.

Để hoạt động liên tục, không có tối thiểu trong p_i. Nếu bạn muốn tránh điểm số đi rogue theo hướng-inf, chỉ cần thường xuyên thêm một số tiền tùy ý P cho tất cả các điểm (cùng một số tiền cho tất cả các điểm).

Chỉnh sửa: Tôi nhận sai N. Trên, N là số lượng chủ đề, trái với câu hỏi được yêu cầu. Với N = số nhiệm vụ, và T = số chủ đề, điều này dẫn đến chi phí O (N * log T). Nếu T là "nhỏ", thì nó gần với O (N).

Chỉnh sửa 2: Nếu tất cả các nhiệm vụ được biết trước, cũng như số lượng các chủ đề, sau đó tôi nghĩ rằng tính toán lập lịch trình tối ưu là giống như các knapsack problem và nó là, trong tất cả các tính tổng quát, NP-đầy đủ (vì vậy bạn sẽ nhận được hàm mũ ở đâu đó). Một phân tích dựa trên chi phí đơn giản như tôi đã mô tả ở trên sẽ cung cấp cho bạn một xấp xỉ tương đối tốt miễn là tất cả các nhiệm vụ riêng lẻ đều có chi phí nhỏ liên quan đến tổng chi phí được phân bổ cho mỗi luồng.

Answer 3

Tôi sẽ xem xét các thuật toán để cân bằng tải, ví dụ:

http://www.ieee802.org/3/trunk_study/february98/congdon.pdf

http://publib.boulder.ibm.com/infocenter/cicstg/v6r0m0/index.jsp?topic=/com.ibm.cicstg600.doc/ccllal0292.htm

Answer 4

Cách đơn giản nhất là để sắp xếp việc làm giảm dần bởi p_i (nhưng điều này là O (n log n)) và thực hiện điều này:

1. Đối với mỗi chủ đề, chúng tôi đã est Thời gian chạy e_n = 0.
2. Đối với mỗi tác vụ, tôi tìm thấy chuỗi có nhiệm vụ e_n enque tối thiểu trên đó và e_n = e_n + p_i.

Thuật toán này sẽ cho bạn kết quả tốt nhất nhưng với thời gian O (N M) trong đó N là số lượng công việc và số lượng chủ đề M. Tổng chi phí của giải pháp là O (N log N + N M), vì vậy đối với M < < N là O (N log N) và cho M gần N là O (n^2).

Answer 5

Độ nghiêng của tôi không phải là cố gắng tìm hiểu trước về cách gán nhiệm vụ, nhưng để ném tất cả vào hàng đợi công việc chung. Bất kỳ chuỗi công nhân nào không có gì khác để thực hiện nhiệm vụ tiếp theo từ hàng đợi sẽ thực hiện công việc và kiểm tra hàng đợi cho tác vụ tiếp theo.

Answer 6

Mặc dù đề xuất liên quan đến vấn đề ba lô là hữu ích, bạn nói rằng bạn đang cố gắng giảm thiểu thời gian thực thi ròng. Sử dụng cách tiếp cận ba lô sẽ yêu cầu bạn tiếp tục tăng kích thước của chiếc ba lô cho đến khi bạn nhận được giải pháp khả thi - không hiệu quả lắm.

Nếu thời gian thực thi bị giới hạn bởi thời gian hoàn thành dài nhất trong tất cả các luồng làm việc song song, tôi muốn gán nhiệm vụ sao cho tôi tối thiểu thời gian làm việc tối đa trên tất cả các chuỗi. Làm điều này có thể dẫn đến một hoặc nhiều chủ đề không thực hiện nhiều công việc, vì vậy chúng tôi không thực sự "cân bằng" công việc. Nếu bạn muốn cân bằng công việc, thì đó là một chức năng khách quan khác. Ví dụ, bạn có thể muốn giảm thiểu phương sai trong công việc giữa các luồng.

Tìm trong khu vực lập kế hoạch cửa hàng việc làm. Nếu bạn chỉ làm điều này thường xuyên, tôi khuyên bạn nên sử dụng thuật toán di truyền - nếu bạn phải thực hiện nó thường xuyên và theo cách tự động hơn, tôi khuyên bạn nên tìm kiếm một số tài liệu để tìm các thuật toán xác định. Hi vọng điêu nay co ich.