Có tìm thấy song song trong Haskell không?

Question

Tôi có một số loại vấn đề bạo lực tôi muốn giải quyết trong Haskell. Máy của tôi có 16 lõi nên tôi muốn tăng tốc thuật toán hiện tại của mình một chút.

Tôi có phương thức "tryCombination" trả về một chuỗi Chỉ (Chuỗi) hoặc Không có gì. Vòng lặp của tôi trông giống như sau:

findSolution = find (isJust) [tryCombination a1 a2 a3 n z p | 
           a1 <- [600..700], 
           a2 <- [600..700], 
           a3 <- [600..700], 
           n <- [1..100], 
           .... 

Tôi biết có một parMap đặc biệt để song song chức năng bản đồ. Một mapFind có thể phức tạp vì nó không thể dự đoán được, nếu một luồng thực sự tìm thấy sự xuất hiện đầu tiên. Nhưng có một cái gì đó giống như một mapAny để tăng tốc độ tìm kiếm?

EDIT:

Tôi viết lại mã sử dụng "withStrategy (parList rseq)" đoạn. Báo cáo trạng thái giống như sau:

38,929,334,968 bytes allocated in the heap 
2,215,280,048 bytes copied during GC 
    3,505,624 bytes maximum residency (795 sample(s)) 
     202,696 bytes maximum slop 
      15 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
Gen 0  44922 colls, 44922 par 37.33s 8.34s  0.0002s 0.0470s 
Gen 1  795 colls, 794 par 7.58s 1.43s  0.0018s 0.0466s 

Parallel GC work balance: 4.36% (serial 0%, perfect 100%) 

TASKS: 10 (1 bound, 9 peak workers (9 total), using -N8) 

SPARKS: 17576 (8198 converted, 9378 overflowed, 0 dud, 0 GC'd, 0 fizzled) 

INIT time 0.00s ( 0.00s elapsed) 
MUT  time 81.79s (36.37s elapsed) 
GC  time 44.91s ( 9.77s elapsed) 
EXIT time 0.00s ( 0.00s elapsed) 
Total time 126.72s (46.14s elapsed) 

Alloc rate 475,959,220 bytes per MUT second 

Productivity 64.6% of total user, 177.3% of total elapsed 

gc_alloc_block_sync: 834851 
whitehole_spin: 0 
gen[0].sync: 10 
gen[1].sync: 3724 

Như tôi đã đề cập (xem nhận xét của tôi), tất cả các lõi đều hoạt động chỉ trong ba giây (wenn tất cả các tia lửa được xử lý). 30 sau tất cả công việc được thực hiện bởi một lõi đơn. Làm thế nào tôi có thể tối ưu hóa nhiều hơn?

Một số EDIT hơn:

bây giờ tôi đã "withStrategy (parBuffer 10 rdeepseq)" thử và fiddled xung quanh với kích thước bộ đệm khác nhau:

Buffersize GC work Balance  MUT  GC 
     10    50%  11,69s 0,94s 
     100    47%  12,31s 1,67s 
     500    40%  11,5 s 1,35s 
    5000    21%  11,47s 2,25s 

Trước hết tôi có thể nói, đó đây là một cải tiến lớn so với những năm 59 mà không có bất kỳ đa luồng nào. Kết luận thứ hai là, kích thước bộ đệm nên càng nhỏ càng tốt nhưng lớn hơn số lõi. Nhưng tốt nhất là, tôi không bị tràn ra ngoài và cũng không bị xì xì nữa. Tất cả đã được chuyển đổi thành công.

Answer 1

Tùy thuộc vào lazyness của tryCombination và song song mong muốn, một trong những có thể làm những gì bạn muốn:

import Control.Parallel.Strategies 
findSolution = 
    find (isJust) $ 
    withStrategy (parList rseq) $ 
    [ tryCombination a1 a2 a3 n z p 
    | a1 <- [600..700] 
    , a2 <- [600..700] 
    , a3 <- [600..700] 
    , n <- [1..100]] 

này paralleizes công việc được thực hiện bởi tryCombination để tìm ra cho dù đó là một Just hoặc một Nothing, nhưng không phải kết quả thực tế trong số Just.

Nếu không có lazyness như được khai thác và các loại quả rất đơn giản, nó có thể làm việc tốt hơn để viết

findSolution = 
    find (isJust) $ 
    withStrategy (parList rdeepseq) $ 
    [ tryCombination a1 a2 a3 n z p 
    | a1 <- [600..700] 
    , a2 <- [600..700] 
    , a3 <- [600..700] 
    , n <- [1..100]]