Parallel chạy mã vợt

Question

Tôi đang sử dụng mã đơn giản sau đây để giải quyết vấn đề n-queens:

#lang racket 

; following returns true if queens are on diagonals: 
(define (check-diagonals bd) 
    (for/or ((r1 (length bd))) 
    (for/or ((r2 (range (add1 r1) (length bd)))) 
     (= (abs (- r1 r2)) 
     (abs(- (list-ref bd r1) 
       (list-ref bd r2))))))) 

; set board size: 
(define N 8) 
; start searching: 
(for ((brd (in-permutations (range N)))) 
    (when (not (check-diagonals brd)) 
    (displayln brd))) 

Nó đang làm việc tốt nhưng phải mất một thời gian dài cho các giá trị lớn hơn của N. Nó sử dụng in-permutations chức năng để có được một dòng hoán vị. Tôi cũng thấy rằng nó chỉ sử dụng 25% công suất CPU (1 trong 4 lõi đang được sử dụng). Làm thế nào tôi có thể sửa đổi mã này để nó sử dụng thử nghiệm song song của hoán vị từ dòng hoán vị trong và sử dụng tất cả 4 lõi CPU? Cảm ơn bạn đã giúp đỡ.

Chỉnh sửa: Đã sửa đổi check-diagonals chức năng như được đề xuất trong nhận xét. Mã cũ hơn là:

(define (check-diagonals bd) 
    (define res #f) 
    (for ((r1 (length bd)) 
     #:break res) 
    (for ((r2 (range (add1 r1) (length bd))) 
      #:break res) 
     (when (= (abs (- r1 r2)) 
       (abs(- (list-ref bd r1) 
         (list-ref bd r2)))) 
     (set! res #t)))) 
    res) 

Answer 1

Để bắt đầu, trước khi đồng bộ hóa bất kỳ thứ gì, bạn có thể cải thiện chương trình gốc của mình một chút. Dưới đây là một số thay đổi bạn có thể thực hiện:

1. Sử dụng for/or thay vì ngắt kết nối và sử dụng #:break.
2. Sử dụng for*/or thay vì lồng nhau for/or các vòng lặp trong nhau.
3. Sử dụng in-range nếu có thể đảm bảo các vòng lặp for chuyên về các vòng lặp đơn giản khi mở rộng.
4. Sử dụng dấu ngoặc vuông thay vì dấu ngoặc đơn ở các vị trí có liên quan để làm cho mã của bạn dễ đọc hơn đối với Racketeers (đặc biệt vì mã này không phải là lược đồ di động từ xa).

Với những thay đổi đó, các mã trông như thế này:

#lang racket 

; following returns true if queens are on diagonals: 
(define (check-diagonals bd) 
    (for*/or ([r1 (in-range (length bd))] 
      [r2 (in-range (add1 r1) (length bd))]) 
    (= (abs (- r1 r2)) 
     (abs (- (list-ref bd r1) 
       (list-ref bd r2)))))) 

; set board size: 
(define N 8) 
; start searching: 
(for ([brd (in-permutations (range N))]) 
    (unless (check-diagonals brd) 
    (displayln brd))) 

Bây giờ chúng ta có thể chuyển sang parallelizing. Đây là điều: song song mọi thứ có xu hướng phức tạp. Lập kế hoạch làm việc song song có xu hướng có phí, và chi phí trên có thể lớn hơn những lợi ích thường xuyên hơn bạn nghĩ. Tôi đã dành một thời gian dài cố gắng song song mã này, và cuối cùng, tôi là không phải có thể tạo ra một chương trình chạy nhanh hơn chương trình tuần tự, ban đầu.

Tuy nhiên, bạn có thể quan tâm đến những gì tôi đã làm. Có thể bạn (hoặc một người nào khác) sẽ có thể nghĩ ra điều gì đó tốt hơn tôi có thể. Công cụ liên quan cho công việc ở đây là futures của Racket, được thiết kế cho tính song song hạt mịn. Tương lai là khá hạn chế do thời gian chạy của Racket được thiết kế (mà về bản chất là vì lý do lịch sử), vì vậy không chỉ bất cứ thứ gì có thể được song song, và một số lượng hoạt động khá lớn có thể khiến cho tương lai bị chặn. May mắn thay, Racket cũng giao hàng với Future Visualizer, một công cụ đồ họa để hiểu hành vi thời gian chạy của tương lai.

Trước khi chúng tôi có thể bắt đầu, tôi chạy phiên bản tuần tự của chương trình với N = 11 và ghi lại kết quả.

$ time racket n-queens.rkt 
[program output elided] 
     14.44 real  13.92 user   0.32 sys 

Tôi sẽ sử dụng những con số này làm điểm so sánh cho phần còn lại của câu trả lời này.

Để bắt đầu, chúng tôi có thể thử thay thế vòng lặp chính for bằng for/asnyc, chạy toàn bộ thân của nó song song.Đây là một phép biến đổi cực kỳ đơn giản và nó để lại cho chúng tôi vòng lặp sau:

(for/async ([brd (in-permutations (range N))]) 
    (unless (check-diagonals brd) 
    (displayln brd))) 

Tuy nhiên, làm cho thay đổi đó không cải thiện hiệu suất; trong thực tế, nó làm giảm đáng kể nó. Chỉ chạy phiên bản này với N = 9 mất ~ 6,5 giây; với N = 10, phải mất ~ 55.

Tuy nhiên, điều này không quá bất ngờ. Việc chạy mã với trình hiển thị tương lai (sử dụng N = 7) cho biết rằng displayln không hợp pháp trong vòng một tương lai, ngăn không cho bất kỳ thực thi song song nào thực sự xảy ra. Có lẽ, chúng ta có thể khắc phục điều này bằng cách tạo ra tương lai mà chỉ tính toán kết quả, sau đó in chúng serially:

(define results-futures 
    (for/list ([brd (in-permutations (range N))]) 
    (future (λ() (cons (check-diagonals brd) brd))))) 

(for ([result-future (in-list results-futures)]) 
    (let ([result (touch result-future)]) 
    (unless (car result) 
     (displayln (cdr result))))) 

Với sự thay đổi này, chúng ta có được một tốc độ tăng nhỏ trong nỗ lực ngây thơ với for/async, nhưng chúng tôi vẫn xa chậm hơn so với phiên bản tuần tự. Bây giờ, với N = 9, phải mất ~ 4,58 giây, và với N = 10, phải mất ~ 44.

Xem xét trình hiển thị tương lai cho chương trình này (lần nữa, với N = 7), hiện không có khối, nhưng có một số đồng bộ (trên jit_on_demand và cấp phát bộ nhớ). Tuy nhiên, sau một thời gian đã bỏ đi, việc thực hiện dường như đang diễn ra, và nó thực sự chạy rất nhiều tương lai song song!

Sau một chút về điều đó, tuy nhiên, việc thực hiện song song dường như chạy ra khỏi hơi nước, và mọi thứ dường như bắt đầu chạy tương đối liên tục một lần nữa.

Tôi đã không thực sự chắc chắn những gì đã xảy ra ở đây, nhưng tôi nghĩ có lẽ đó là vì một số các kỳ hạn chỉ là quá nhỏ. Có vẻ như chi phí lên kế hoạch cho hàng ngàn tương lai (hoặc, trong trường hợp N = 10, hàng triệu) đã vượt xa thời gian thực tế của công việc đang được thực hiện trong tương lai. May mắn thay, điều này có vẻ như một cái gì đó mà có thể được giải quyết bằng cách chỉ nhóm công việc thành những phần, một cái gì đó tương đối doable sử dụng in-slice:

(define results-futures 
    (for/list ([brds (in-slice 10000 (in-permutations (range N)))]) 
    (future 
    (λ() 
     (for/list ([brd (in-list brds)]) 
     (cons (check-diagonals brd) brd)))))) 

(for* ([results-future (in-list results-futures)] 
     [result (in-list (touch results-future))]) 
    (unless (car result) 
    (displayln (cdr result)))) 

Dường như sự nghi ngờ của tôi là đúng, bởi vì sự thay đổi đó sẽ giúp rất nhiều thứ. Bây giờ, chạy phiên bản song song của chương trình chỉ mất 3,9 giây cho N = 10, tăng tốc hơn 10 lần so với phiên bản trước bằng cách sử dụng tương lai. Tuy nhiên, thật không may, vẫn còn chậm hơn so với phiên bản hoàn toàn tuần tự, chỉ mất khoảng 1,4 giây. Tăng N lên 11 làm cho phiên bản song song mất ~ 44 giây, và nếu kích thước chunk được cung cấp cho in-slice được tăng lên 100.000, nó mất nhiều thời gian hơn, ~ 55 giây.

Xem xét trình hiển thị trong tương lai cho phiên bản đó của chương trình, với N = 11 và kích thước chunk 1.000.000, tôi thấy rằng dường như có một số giai đoạn song song mở rộng, nhưng tương lai bị chặn rất nhiều cấp phát bộ nhớ:

này có ý nghĩa, kể từ bây giờ mỗi tương lai là xử lý công việc nhiều hơn nữa, nhưng nó có nghĩa là tương lai được đồng bộ hóa liên tục, có khả năng dẫn đến chi phí hiệu suất đáng kể tôi nhìn thấy.

Tại thời điểm này, tôi không chắc có nhiều thứ khác mà tôi biết cách tinh chỉnh để cải thiện hiệu suất trong tương lai.Tôi đã cố gắng cắt giảm phân bổ bằng cách sử dụng các vectơ thay vì danh sách và các hoạt động sửa lỗi chuyên ngành, nhưng vì lý do gì đó, dường như hoàn toàn hủy diệt tính song song. Tôi nghĩ rằng có lẽ đó là vì tương lai không bao giờ bắt đầu song song, vì vậy tôi đã thay thế tương lai bằng tương lai, nhưng kết quả đã gây nhầm lẫn cho tôi, và tôi thực sự không hiểu ý của họ.

Kết luận của tôi là tương lai của Racket chỉ đơn giản là quá mong manh để làm việc với vấn đề này, đơn giản như nó có thể được. Tôi từ bỏ.

---

Bây giờ, như một phần thưởng nhỏ, tôi quyết định thử và bắt chước những điều tương tự trong Haskell, vì Haskell có một câu chuyện đặc biệt mạnh mẽ để đánh giá song song hạt mịn. Nếu tôi không thể tăng hiệu suất trong Haskell, tôi cũng sẽ không thể có được một trong Racket.

tôi sẽ bỏ qua tất cả các chi tiết về những điều khác nhau tôi đã cố gắng, nhưng cuối cùng, tôi đã kết thúc với chương trình sau đây:

import Data.List (permutations) 
import Data.Maybe (catMaybes) 

checkDiagonals :: [Int] -> Bool 
checkDiagonals bd = 
    or $ flip map [0 .. length bd - 1] $ \r1 -> 
    or $ flip map [r1 + 1 .. length bd - 1] $ \r2 -> 
     abs (r1 - r2) == abs ((bd !! r1) - (bd !! r2)) 

n :: Int 
n = 11 

main :: IO() 
main = 
    let results = flip map (permutations [0 .. n-1]) $ \brd -> 
     if checkDiagonals brd then Nothing else Just brd 
    in mapM_ print (catMaybes results) 

tôi đã có thể dễ dàng thêm một số xử lý song song sử dụng thư viện Control.Parallel.Strategies. Tôi đã thêm một dòng vào chức năng chính mà giới thiệu một số đánh giá song song:

import Control.Parallel.Strategies 
import Data.List.Split (chunksOf) 

main :: IO() 
main = 
    let results = 
     concat . withStrategy (parBuffer 10 rdeepseq) . chunksOf 100 $ 
     flip map (permutations [0 .. n-1]) $ \brd -> 
      if checkDiagonals brd then Nothing else Just brd 
    in mapM_ print (catMaybes results) 

Phải mất một thời gian để tìm ra các đoạn phải và lăn kích thước bộ đệm, nhưng những giá trị này đã cho tôi một 30-40% tăng tốc phù hợp hơn ban đầu, chương trình tuần tự.

Bây giờ, rõ ràng, thời gian chạy của Haskell là phù hợp hơn cho lập trình song song so với Racket, vì vậy so sánh này hầu như không công bằng. Nhưng nó đã giúp tôi tự mình thấy rằng, mặc dù có 4 lõi (8 với siêu phân luồng) theo ý của tôi, tôi thậm chí không thể tăng tốc 50%. Ghi nhớ nó trong tâm trí.

Như Matthias noted in a mailing list thread I wrote on this subject:

Một lời cảnh báo về xử lý song song nói chung. Cách đây không lâu, một người trong CS tại một trường Ivy League đã nghiên cứu việc sử dụng tính song song trong các ứng dụng và ứng dụng khác nhau. Mục đích là để tìm hiểu xem ‘cường điệu’ về sự song đối ảnh hưởng đến con người như thế nào. Hồi ức của tôi là họ tìm thấy gần 20 dự án, nơi các giáo sư (trong CE, EE, CS, Bio, Econ, vv) nói với sinh viên tốt nghiệp của họ/PhD để sử dụng song song để chạy các chương trình nhanh hơn. Họ đã kiểm tra tất cả chúng và cho N - 1 hoặc 2, các dự án chạy nhanh hơn một khi đã loại bỏ tính song song. Nhanh hơn đáng kể.

Mọi người thường đánh giá thấp chi phí truyền thông mà chủ nghĩa song song đưa ra.

Cẩn thận để không phạm sai lầm tương tự.