Song song trình tạo chuỗi Fibonacci

Tôi đang học về sự song song và trong một bài tập tôi đã đưa ra một vài thuật toán mà tôi nên cải thiện về hiệu năng. Một trong số đó là một máy phát điện dãy Fibonacci:Song song trình tạo chuỗi Fibonacci

array[0] = 0; 
array[1] = 1; 
for (q = 2; q < MAX; q++) { 
    array[q] = array[q−1] + array[q−2]; 
}

nghi ngờ của tôi là, điều này không thể được tối ưu hóa (bằng cách song song), vì mỗi số phụ thuộc vào hai con số trước đó (và do đó gián tiếp trên tất cả các số trước). Làm thế nào điều này có thể được song song?

Nguồn

2013-05-09 Jawap

được bạn đang làm gì trong lớp học của bạn vậy, đến nay? – devnull

Fibonacci là một sự lựa chọn nghèo nàn cho sự song song, tôi tin tưởng. Kiểm tra điều này: http://trigonakis.com/blog/2011/02/27/parallelizing-simple-algorithms-fibonacci/ –

Trừ khi bạn có thể xác định các số Fibonacci liền kề trước thời hạn, có khả năng bạn sẽ không thể song song nó . – devnull

Chuỗi Fibonacci được xác định chỉ bằng hai phần tử đầu tiên của nó; trên thực tế, bạn bằng cách nào đó có thể parallelize nó, mặc dù xấu xí:

F(n + 2) = F(n + 1) + F(n) 
F(n + 3) = F(n + 1) + F(n + 2) = F(n + 1) * 2 + F(n) 
F(n + 4) = F(n + 2) + F(n + 3) = F(n + 1) * 3 + F(n) * 2 
F(n + 5) = F(n + 3) + F(n + 4) = F(n + 1) * 5 + F(n) * 3 
F(n + 6) = F(n + 4) + F(n + 5) = F(n + 1) * 8 + F(n) * 5

Hy vọng bởi bây giờ, bạn có thể thấy rằng:

F(n + k) = F(n + 1) * F(K) + F(n) * F(k - 1)

Vì vậy, sau khi tính toán các con số k đầu tiên, bạn có thể sử dụng mối quan hệ này để tính toán k mục tiếp theo trong chuỗi, đồng thời, song song.

Bạn cũng có thể sử dụng công thức trực tiếp cho số Fibonacci để tính toán song song, nhưng đó là loại quá uncool (cũng có thể quá đơn giản cho mục đích học tập mà nó có thể phục vụ).

Nguồn

2013-05-09 14:58:18