Về câu trả lời này
Câu trả lời này là Phần II của câu trả lời được chấp nhận ở trên .
7. Naive so với thuật toán Chunksize của Pool
Trước khi đi vào chi tiết, hãy xem xét hai gifs dưới đây. Đối với một phạm vi độ dài iterable khác nhau, chúng cho thấy hai thuật toán được so sánh đã xử lý iterable được thông qua như thế nào [sau đó sẽ là một chuỗi] và cách các tác vụ kết quả có thể được phân phối. Thứ tự của các công nhân là ngẫu nhiên và số lượng nhiệm vụ phân tán trên mỗi công nhân trong thực tế có thể khác với các hình ảnh này cho các nhiệm vụ nhẹ và các nhiệm vụ trong Kịch bản rộng. Như đã đề cập trước đó, chi phí cũng không được bao gồm ở đây. Đối với các nhiệm vụ đủ nặng trong Kịch bản dày đặc với kích thước dữ liệu được truyền không thể bỏ qua, các tính toán thực tế đã vẽ một bức tranh rất giống nhau.
Như được hiển thị trong chương "5. Thuật toán Chunksize của Pool", với thuật toán khối của Pool, số lượng khối sẽ ổn định ở n_chunks == n_workers * 4 cho các lần lặp đủ lớn, trong khi nó tiếp tục chuyển đổi giữa n_chunks == n_workers và n_chunks == n_workers + 1 với cách tiếp cận ngây thơ. Đối với thuật toán ngây thơ được áp dụng: Bởi vì n_chunks % n_workers == 1 là True cho n_chunks == n_workers + 1, một phần mới sẽ được tạo trong đó chỉ một công nhân sẽ được sử dụng.
Naive Chunksize-Thuật toán:
Bạn có thể nghĩ rằng bạn đã tạo các tác vụ trong cùng một số lượng công nhân, nhưng điều này sẽ chỉ đúng với các trường hợp không có phần còn lại cho len_iterable / n_workers. Nếu có là phần còn lại, sẽ có một phần mới chỉ có một nhiệm vụ cho một công nhân. Lúc đó tính toán của bạn sẽ không song song nữa.
Dưới đây bạn thấy một hình tương tự như trong hình 5, nhưng hiển thị số phần thay vì số phần. Đối với thuật toán chunkize đầy đủ của Pool [n_pool2], n_sections sẽ ổn định ở yếu tố khét tiếng, mã hóa cứng 4. Đối với thuật toán ngây thơ, n_sections sẽ xen kẽ giữa một và hai.
Đối với thuật toán khối của Pool, việc ổn định tại n_chunks = n_workers * 4 thông qua trước đó đã đề cập xử lý thêm, ngăn việc tạo một phần mới ở đây và giữ Chia sẻ không sử dụng giới hạn ở một công nhân cho các vòng lặp đủ dài. Không chỉ vậy, thuật toán sẽ tiếp tục thu nhỏ kích thước tương đối của Chia sẻ không hoạt động, dẫn đến giá trị RDE hội tụ 100%.
"Đủ lâu" cho n_workers=4 là len_iterable=210 chẳng hạn. Đối với các lần lặp bằng hoặc lớn hơn thế, Chia sẻ không hoạt động sẽ bị giới hạn ở một công nhân, một đặc điểm ban đầu bị mất do phép nhân 4- trong thuật toán chunkize ở vị trí đầu tiên.
Thuật toán chunkize ngây thơ cũng hội tụ 100%, nhưng nó chậm hơn. Hiệu ứng hội tụ chỉ phụ thuộc vào thực tế là phần tương đối của đuôi co lại trong trường hợp sẽ có hai phần. Đuôi này chỉ có một công nhân làm việc được giới hạn ở độ dài trục x n_workers - 1, phần còn lại tối đa có thể có cho len_iterable / n_workers.
Các giá trị RDE thực tế khác nhau như thế nào đối với thuật toán chunkize của Pool và thuật toán chunkize?
Dưới đây bạn tìm thấy hai bản đồ nhiệt hiển thị các giá trị RDE cho tất cả các độ dài có thể lặp lên tới 5000, cho tất cả số lượng công nhân từ 2 đến 100. Thang màu đi từ 0,5 đến 1 [50% - 100%]. Bạn sẽ nhận thấy nhiều vùng tối hơn [giá trị RDE thấp hơn] cho thuật toán ngây thơ trong sơ đồ nhiệt bên trái. Ngược lại, thuật toán khối của Pool ở bên phải vẽ ra một bức tranh che nắng hơn nhiều.
Độ dốc đường chéo của các góc tối phía dưới bên trái so với các góc sáng phía trên bên phải, một lần nữa cho thấy sự phụ thuộc vào số lượng công nhân đối với cái gọi là "lặp dài".
Làm thế nào xấu nó có thể nhận được với mỗi thuật toán?
Với thuật toán khối của Pool, RDE giá trị 81,25% là giá trị thấp nhất cho phạm vi công nhân và độ dài lặp được chỉ định ở trên:
Với thuật toán chunkize ngây thơ, mọi thứ có thể trở nên tồi tệ hơn nhiều. Tính toán thấp nhất RDE ở đây là 50,72%. Trong trường hợp này, gần một nửa thời gian tính toán chỉ có một công nhân duy nhất đang chạy! Vì vậy, coi chừng, chủ sở hữu tự hào của Hiệp sĩ hạ cánh . ;]
8. Kiểm tra thực tế
Trong các chương trước, chúng tôi đã xem xét một mô hình đơn giản hóa cho vấn đề phân phối toán học thuần túy, bị loại bỏ khỏi các chi tiết khó chịu, khiến cho việc xử lý đa chủ đề trở nên khó khăn như vậy ngay từ đầu. Để hiểu rõ hơn về Mô hình phân phối [DM] một mình có thể góp phần giải thích việc sử dụng nhân viên quan sát trong thực tế, bây giờ chúng ta sẽ xem xét Lịch biểu song song được vẽ bởi thực tính toán.
Thiết lập
Các sơ đồ sau đây đều xử lý các thực thi song song của một hàm giả đơn giản, bị ràng buộc bởi cpu, được gọi với nhiều đối số khác nhau để chúng ta có thể quan sát Lịch biểu song song được vẽ thay đổi như thế nào tùy thuộc vào các giá trị đầu vào. "Công việc" trong hàm này chỉ bao gồm phép lặp trên một đối tượng phạm vi. Điều này đã đủ để giữ cho lõi luôn bận rộn vì chúng ta chuyển số lượng lớn vào. Tùy chọn chức năng sẽ có thêm một số data duy nhất không có nhiệm vụ. Vì mỗi tác vụ bao gồm cùng một lượng công việc chính xác, chúng tôi vẫn đang xử lý một Kịch bản dày đặc ở đây.
Hàm này được trang trí với trình bao bọc lấy dấu thời gian với độ phân giải ns [Python 3.7+]. Dấu thời gian được sử dụng để tính toán thời gian của một nhiệm vụ và do đó cho phép vẽ Lịch biểu song song theo kinh nghiệm.@stamp_taskel def busy_foo[i, it, data=None]: """Dummy function for CPU-bound work.""" for _ in range[int[it]]: pass return i, data def stamp_taskel[func]: """Decorator for taking timestamps on start and end of decorated function execution. """ @wraps[func] def wrapper[*args, **kwargs]: start_time = time_ns[] result = func[*args, **kwargs] end_time = time_ns[] return [current_process[].name, [start_time, end_time]], result return wrapper
Phương pháp starmap của Pool cũng được trang trí theo cách mà chỉ bản thân cuộc gọi starmap được tính thời gian. "Bắt đầu" và "kết thúc" của cuộc gọi này xác định mức tối thiểu và tối đa trên trục x của Lịch biểu song song được sản xuất.
Chúng tôi sẽ quan sát tính toán của 40 nhiệm vụ trên bốn quy trình công nhân trên một máy với các thông số kỹ thuật sau: Python 3.7.1, Ubuntu 18.04.2, CPU Intel® Core i7-2600K @ 3.40GHz × 8
Các giá trị đầu vào sẽ được thay đổi là số lần lặp trong vòng lặp for [30k, 30M, 600M] và kích thước dữ liệu gửi thêm [mỗi tác vụ, numpy-ndarray: 0 MiB, 50 MiB].... N_WORKERS = 4 LEN_ITERABLE = 40 ITERATIONS = 30e3 # 30e6, 600e6 DATA_MiB = 0 # 50 iterable = [ # extra created data per taskel [i, ITERATIONS, np.arange[int[DATA_MiB * 2**20 / 8]]] # taskel args for i in range[LEN_ITERABLE] ] with Pool[N_WORKERS] as pool: results = pool.starmap[busy_foo, iterable]
Các lần chạy được hiển thị bên dưới được lựa chọn cẩn thận để có cùng thứ tự các khối để bạn có thể nhận ra sự khác biệt tốt hơn so với Lịch biểu song song từ Mô hình phân phối, nhưng đừng quên thứ tự mà công nhân nhận nhiệm vụ của họ là không xác định.
Dự đoán DM
Để nhắc lại, Mô hình phân phối "dự đoán" Lịch biểu song song như chúng ta đã thấy trước đó trong chương 6.2:
CHẠY 1: Lặp lại 30k và 0 dữ liệu MiB cho mỗi tác vụ
Cuộc chạy đầu tiên của chúng tôi ở đây rất ngắn, các nhiệm vụ rất "nhẹ". Toàn bộ cuộc gọi pool.starmap[]- chỉ mất 14,5 ms trong tổng số. Bạn sẽ nhận thấy, trái với DM, việc chạy không bị giới hạn ở phần đuôi, mà còn diễn ra giữa các nhiệm vụ và thậm chí giữa các nhiệm vụ. Đó là bởi vì lịch trình thực sự của chúng tôi ở đây tự nhiên bao gồm tất cả các loại chi phí. Ở đây không có nghĩa là tất cả mọi thứ bên ngoài của một nhiệm vụ. Có thể real idling trong thời gian một nhiệm vụ không được nắm bắt như thế nào đã được đề cập trước đó.
Hơn nữa bạn có thể thấy, không phải tất cả các công nhân đều nhận được nhiệm vụ của họ cùng một lúc. Điều đó là do thực tế là tất cả các công nhân được cho ăn inqueue được chia sẻ và mỗi lần chỉ có một công nhân có thể đọc được từ đó. Điều tương tự cũng áp dụng cho outqueue. Điều này có thể gây ra sự đảo lộn lớn hơn ngay khi bạn truyền các kích thước dữ liệu không biên cho cách chúng ta sẽ thấy sau này.
Hơn nữa, bạn có thể thấy rằng mặc dù thực tế là mọi nhiệm vụ đều bao gồm cùng một lượng công việc, nhưng khoảng thời gian đo thực tế cho một nhiệm vụ thay đổi rất lớn. Các nhiệm vụ được phân phối cho worker-3 và worker-4 cần nhiều thời gian hơn các task được xử lý bởi hai công nhân đầu tiên. Đối với lần chạy này, tôi nghi ngờ đó là do turbo boost không còn khả dụng trên lõi cho worker-3/4 tại thời điểm đó, vì vậy họ đã xử lý các tác vụ của mình với tốc độ xung nhịp thấp hơn.
Toàn bộ tính toán nhẹ đến mức các yếu tố hỗn loạn do phần cứng hoặc hệ điều hành giới thiệu có thể làm lệch PS một cách quyết liệt. Tính toán là một "chiếc lá trên gió" và DM - dự đoán có rất ít ý nghĩa, ngay cả đối với một kịch bản phù hợp về mặt lý thuyết.
CHẠY thứ 2: Lặp lại 30 triệu và 0 dữ liệu MiB cho mỗi tác vụ
Tăng số lần lặp trong vòng lặp for từ 30.000 lên 30 triệu, dẫn đến Lịch song song thực sự gần với một kết hợp hoàn hảo với dự đoán được cung cấp bởi dữ liệu được cung cấp bởi DM, Hurrah ! Tính toán trên mỗi tác vụ hiện đủ nặng để làm cho các phần không hoạt động ở đầu và ở giữa, chỉ cho phép Chia sẻ Idling lớn hiển thị mà DM dự đoán.
CHẠY thứ 3: Lặp lại 30 triệu và 50 dữ liệu MiB cho mỗi tác vụ
Giữ các vòng lặp 30M, nhưng cũng gửi 50 MiB cho mỗi tác vụ qua lại xiên hình ảnh một lần nữa. Ở đây hiệu ứng xếp hàng có thể nhìn thấy rõ. Worker-4 cần chờ đợi lâu hơn cho nhiệm vụ thứ hai so với Worker-1. Bây giờ hãy tưởng tượng lịch trình này với 70 công nhân!
Trong trường hợp các nhiệm vụ tính toán rất nhẹ, nhưng có thể cung cấp một lượng dữ liệu đáng chú ý là tải trọng, nút cổ chai của một hàng đợi chung có thể ngăn chặn bất kỳ lợi ích bổ sung nào của việc thêm nhiều công nhân vào Pool, ngay cả khi chúng được hỗ trợ bởi các lõi vật lý. Trong trường hợp như vậy, Worker-1 có thể được thực hiện với nhiệm vụ đầu tiên và chờ đợi một nhiệm vụ mới ngay cả trước khi Worker-40 hoàn thành nhiệm vụ đầu tiên.
Bây giờ nó trở nên rõ ràng tại sao thời gian tính toán trong một Pool không luôn luôn giảm tuyến tính với số lượng công nhân. Gửi một lượng dữ liệu tương đối lớn cùng có thể dẫn đến các tình huống trong đó phần lớn thời gian dành cho việc chờ dữ liệu được sao chép vào không gian địa chỉ của một công nhân và chỉ một công nhân có thể được cho ăn cùng một lúc.
RUN thứ 4: Lặp lại 600M và 50 dữ liệu MiB cho mỗi tác vụ
Ở đây chúng tôi gửi lại 50 MiB, nhưng tăng số lần lặp từ 30M lên 600M, đưa tổng thời gian tính toán tăng từ 10 giây lên 152 giây. Lịch biểu song song được vẽ lần nữa , gần với kết quả khớp hoàn hảo với dự đoán, chi phí thông qua sao chép dữ liệu bị gạt ra ngoài lề.
9. Kết luận
Phép nhân được thảo luận bởi 4 làm tăng tính linh hoạt lập lịch, nhưng cũng thúc đẩy sự không đồng đều trong phân phối nhiệm vụ. Nếu không có phép nhân này, Chia sẻ không sử dụng sẽ bị giới hạn ở một công nhân duy nhất ngay cả đối với các lần lặp ngắn [cho DM với Kịch bản dày đặc]. Thuật toán chunkize của Pool cần các biến lặp đầu vào có kích thước nhất định để lấy lại đặc điểm đó.
Như câu trả lời này đã được hy vọng cho thấy, thuật toán khối của Pool dẫn đến việc sử dụng lõi trung bình tốt hơn so với cách tiếp cận ngây thơ, ít nhất là đối với trường hợp trung bình và vì chi phí dài không được xem xét. Thuật toán ngây thơ ở đây có thể có Hiệu suất phân phối [DE] thấp tới ~ 51%, trong khi thuật toán khối của Pool có mức thấp ~ 81%. DE tuy nhiên không bao gồm Chi phí song song [PO] như IPC. Chương 8 đã chỉ ra rằng DE vẫn có thể có sức mạnh dự đoán tuyệt vời cho Kịch bản dày đặc với chi phí ngoài lề.
Mặc dù thực tế là thuật toán khối của Pool đạt được mức cao hơn DE so với cách tiếp cận ngây thơ, nó không cung cấp phân phối taskel tối ưu cho mọi chòm sao đầu vào. Trong khi một tĩnh đơn giản thuật toán chunking không thể tối ưu hóa [bao gồm cả chi phí] Hiệu quả song song [PE], không có lý do cố hữu tại sao nó không thể luôn cung cấp Hiệu suất phân phối tương đối [RDE] là 100% , điều đó có nghĩa là, giống nhau DE như với chunksize=1. Một thuật toán chunkize đơn giản chỉ bao gồm toán học cơ bản và có thể tự do "cắt bánh" theo bất kỳ cách nào.
Không giống như việc triển khai thuật toán "chunking kích thước bằng nhau" của Pool, thuật toán "chunking kích thước chẵn" sẽ cung cấp RDE 100% cho mỗi len_iterable/n_workers sự phối hợp. Thuật toán phân chia kích thước chẵn sẽ phức tạp hơn một chút khi triển khai trong nguồn của Pool, nhưng có thể được điều chỉnh trên đầu thuật toán hiện tại chỉ bằng cách đóng gói các tác vụ bên ngoài [Tôi sẽ liên kết từ đây trong trường hợp tôi thả Q/A làm thế nào để làm điều đó].
Tôi nghĩ rằng một phần của những gì bạn đang thiếu là ước tính ngây thơ của bạn cho rằng mỗi đơn vị công việc chiếm cùng một khoảng thời gian trong trường hợp chiến lược của bạn là tốt nhất. Nhưng nếu một số công việc hoàn thành sớm hơn những công việc khác thì một số lõi có thể trở nên nhàn rỗi chờ đợi các công việc chậm hoàn thành.
Do đó, bằng cách chia các đoạn thành 4 phần nhiều hơn, sau đó nếu một đoạn hoàn thành sớm, lõi đó có thể bắt đầu đoạn tiếp theo [trong khi các lõi khác tiếp tục hoạt động trên đoạn chậm hơn của chúng].
Tôi không biết lý do tại sao họ chọn chính xác yếu tố 4 nhưng đó sẽ là một sự đánh đổi giữa việc giảm thiểu chi phí của mã bản đồ [muốn có các khối lớn nhất có thể] và cân bằng các khối thời gian khác nhau [muốn có khối nhỏ nhất có thể ].