Song song OpenMP trên chức năng đệ quy

Question

Tôi đang cố gắng sử dụng song song để cải thiện tốc độ làm mới để vẽ cảnh 3D với các đối tượng được sắp xếp theo kiểu thừa kế. Thuật toán vẽ cảnh đầu tiên đệ quy đi qua cây của các đối tượng, và từ đó, xây dựng một mảng dữ liệu cần thiết được sắp xếp cần thiết để vẽ cảnh. Sau đó, nó vượt qua mảng đó nhiều lần để vẽ các đối tượng/lớp phủ, v.v ... Vì những gì tôi đã đọc OpenGL không phải là một API an toàn thread, tôi giả sử mảng mảng/mã vẽ phải được thực hiện trên luồng chính, nhưng tôi Tôi nghĩ rằng tôi có thể có thể song song chức năng đệ quy lấp đầy mảng. Điều quan trọng là mảng phải được điền theo thứ tự các đối tượng xuất hiện trong cảnh, vì vậy tất cả các chức năng liên kết một đối tượng đã cho với chỉ mục mảng phải được thực hiện theo thứ tự đúng, nhưng khi chỉ mục mảng đã được gán, Tôi có thể điền dữ liệu của phần tử mảng đó (không nhất thiết là một hoạt động tầm thường) bằng cách sử dụng các chuỗi công nhân. Vì vậy, đây là mã giả mà tôi đang cố gắng để có được. Tôi hy vọng bạn sẽ có được ý tưởng về cú pháp chuỗi xml-ish.

recursivepopulatearray(theobject) 
{ 
    <main thread> 
    for each child of theobject 
    { 
    assign array index 
    <child thread(s)> 
     populate array element for child object 
    </child thread(s)> 
    recursivepopulatearray(childobject) 
    } 
    </main thread> 
} 

Vì vậy, có thể thực hiện điều này bằng cách sử dụng OpenMP và nếu có thì làm cách nào? Có các thư viện song song khác có thể xử lý tốt hơn không?

Hợp đồng bổ sung: Để trả lời Davide's request for more clarification, hãy để tôi giải thích chi tiết hơn một chút. Hãy nói rằng cảnh được ra lệnh như thế này:

-Bicycle Frame 
    - Handle Bars 
    - Front Wheel 
    - Back Wheel 
-Car Frame 
    - Front Left Wheel 
    - Front Right Wheel 
    - Back Left Wheel 
    - Back Right Wheel 

Bây giờ, mỗi người trong số các đối tượng này có rất nhiều dữ liệu liên kết với nó, tức là các thông số vị trí, luân chuyển, kích thước, bản vẽ khác nhau, vv Ngoài ra, tôi cần phải thực hiện nhiều lần vượt qua cảnh này để vẽ nó đúng cách. Một đường chuyền vẽ các hình dạng của các đối tượng, một đường khác vẽ văn bản mô tả các đối tượng, một đường khác vẽ các kết nối/liên kết giữa các đối tượng nếu có. Dù sao, việc lấy tất cả dữ liệu vẽ ra khỏi các đối tượng khác này khá chậm nếu tôi phải truy cập nhiều lần, vì vậy tôi đã quyết định sử dụng một lần để lưu tất cả dữ liệu đó vào mảng một chiều, và sau đó tất cả thực tế bản vẽ chỉ nhìn vào mảng. Việc bắt được là bởi vì tôi cần phải làm OpenGL pushes/pops theo thứ tự đúng, mảng phải nằm trong thứ tự tìm kiếm theo chiều sâu thích hợp đầu tiên đại diện cho chế độ heirarchy cây. Trong ví dụ trên, mảng phải được đặt hàng như sau:

index 0: Bicycle Frame 
index 1: Handle Bars 
index 2: Front Wheel 
index 3: Back Wheel 
index 4: Car Frame 
index 5: Front Left Wheel 
index 6: Front Right Wheel 
index 7: Back Left Wheel 
index 8: Back Right Wheel 

Vì vậy, thứ tự của mảng phải được đăng đúng, nhưng một khi tôi đã gán mà ra lệnh cho đúng, tôi có thể parallelize điền của mảng. Ví dụ khi tôi đã gán Khung xe đạp để lập chỉ mục 0 và Xử lý các thanh để lập chỉ mục 1, một chuỗi có thể lấy phần tử mảng cho Khung xe đạp trong khi một chuỗi khác lấy phần tử mảng cho Thanh điều khiển.

OK, tôi nghĩ rằng trong việc làm rõ điều này, tôi đã trả lời câu hỏi của riêng tôi, vì vậy cảm ơn Davide. Vì vậy, tôi đã đăng answer của riêng mình.

Answer 1

Đây là một đoạn mã giả sửa đổi sẽ hoạt động.

populatearray(thescene) 
{ 
    recursivepopulatearray(thescene) 

    #pragma omp parallel for 
    for each element in array 
    populate array element based on associated object 
} 

recursivepopulatearray(theobject) 
{ 
    for each childobject in theobject 
    { 
    assign array index and associate element with childobject 
    recursivepopulatearray(childobject) 
    } 
} 

Answer 2

để parallelise thread con, chỉ cần đặt một pragma trước khi vòng lặp:

#pragma omp parallel for 
for (i=0; i < elements; i++) 
{ 
} 

việc làm.

Bây giờ, bạn hoàn toàn đúng, bạn không thể nhận được bất kỳ thư viện luồng nào để làm một bit trước một cách khác theo cách hoàn toàn song song (rõ ràng!) Và openMP không có tính năng 'khóa' hoặc 'chờ' (nó không có từ khóa 'chờ tất cả để kết thúc' - Barrier), nó không được thiết kế để mô phỏng thư viện chuỗi, nhưng nó cho phép bạn lưu trữ các giá trị "bên ngoài" phần song song và đánh dấu các phần nhất định là 'chỉ luồng duy nhất' (Từ khóa được đặt hàng) do đó, điều này có thể giúp bạn chỉ định các chỉ mục trong một vòng lặp song song trong khi các chủ đề khác chỉ định các phần tử.

Hãy xem getting started guide.

Nếu bạn đang sử dụng Visual C++, bạn cũng sẽ cần đặt cờ/omp trong cài đặt trình biên dịch của bạn.

Answer 3

Tôi nghĩ rằng bạn nên làm rõ hơn câu hỏi của bạn (ví dụ chính xác những gì phải được thực hiện nối tiếp và tại sao)

OpenMP (như nhiều thư viện song song khác) không không bảo đảm trật tự, trong đó các phần song song khác nhau sẽ thực hiện, và vì chúng thực sự song song (trên một máy đa lõi) có thể có các điều kiện chủng tộc nếu các phần khác nhau ghi cùng một dữ liệu. Nếu đó là ok cho vấn đề của bạn, chắc chắn bạn có thể sử dụng nó.

Answer 4

Là gbjbaanb mentioned, bạn có thể thực hiện việc này dễ dàng - nó chỉ yêu cầu một tuyên bố pragma để song song điều này.

Tuy nhiên, có một vài điều cần lưu ý:

Trước tiên, bạn đề cập đến trật tự đó là mâu thuẫn ở đây. Nếu bạn cần bảo tồn trật tự trong việc làm phẳng cấu trúc phân cấp, việc song song (ở mức này) sẽ có vấn đề. Bạn có thể sẽ mất hoàn toàn đặt hàng của bạn.

Ngoài ra, song song các hàm đệ quy có nhiều vấn đề. Thực hiện một trường hợp cực đoan - giả sử bạn có một máy tính lõi kép và bạn có một cây nơi mỗi nút "cha mẹ" có 4 con. Nếu cây là sâu, bạn rất, rất nhanh chóng "quá song song" vấn đề, thường làm cho mọi thứ tồi tệ hơn, không tốt hơn, hiệu suất khôn ngoan.

Nếu bạn định thực hiện việc này, có thể bạn nên đặt thông số cấp và chỉ song song với một vài cấp đầu tiên. Lấy ví dụ 4 con/mẹ của chúng ta, nếu bạn song song với 2 mức đầu tiên, bạn đã phá vỡ nó thành 16 đoạn song song (được gọi là từ 4 đoạn song song).

Từ những gì bạn đã đề cập, tôi muốn rời khỏi phần nối tiếp này, và tập trung thay vì thứ hai mà bạn đề cập đến:

"Sau đó, nó đi qua mà mảng nhiều lần để vẽ đối tượng/lớp phủ, vv"

Điều đó nghe như một nơi lý tưởng để song song.