Thư viện tam giác an toàn chủ đề

Question

Tôi đang viết một phần mềm C++ cần tính toán tổng Minkowski nhanh. Một triển khai dựa trên các hậu tố kép.

tôi đánh giá một số thư viện hình học như

• CGAL
• LEDA
• boost::geometry (không có việc thực hiện tổng Minkowski, nhưng có một tutorial giải thích làm thế nào để thực hiện nó)

nhưng tôi đã sử dụng thư viện của bên thứ ba khác rất nhanh so với thư viện trước đó s và sử dụng thư viện FIST cho triangulation.

Mã của tôi làm việc nhiều hơn hoặc ít hơn trong các cách sau:

• tôi đọc đa giác của tôi
• tôi tính toán Minkowski tổng Tôi cần
• Đối với lần n
  • tôi quyết định đa giác để sử dụng trong tính toán sau đây
  • Tôi làm một số nội dung dựa trên khoản tiền Minkowski
  • Tôi cung cấp cho một val ue đến kết quả
• Tôi lấy kết quả với giá trị tốt nhất là kết quả cuối cùng

Kể từ khi tính toán trong vòng lặp được độc lập từ vòng tròn, tôi song song vòng lặp và tất cả mọi thứ làm việc tốt.

Sau đó, tôi quyết định chuyển số tiền tính toán Minkowski trong mỗi vòng song song:

• tôi đọc đa giác của tôi
• Đối number_of_threads (= n) lần
  • tôi quyết định đa giác để sử dụng trong các sau tính toán
  • Tôi tính toán khoản tiền Minkowski tôi cần trong vòng này
  • Tôi làm một số nội dung dựa trên khoản tiền Minkowski
  • tôi đưa ra một giá trị cho kết quả

• Tôi lấy kết quả với giá trị tốt nhất là kết quả cuối cùng

  nhưng thư viện của bên thứ ba làm việc không còn nữa.

tôi nhận được thông báo lỗi number_of_threads - 1 nói

Assertion Failed.

Các tệp gây ra lỗi xác nhận thay đổi từ chạy đến chạy và từ chuỗi này sang luồng khác, nhưng tất cả đều là tệp c có cùng tên với tiêu đề FIST (trong khi tôi có mã nguồn của thư viện bên thứ ba , Tôi chỉ có một .lib và tiêu đề của thư viện FIST)

Như đã nêu trước đây, tôi đã cố tính toán tất cả các khoản tiền Minkowski mà tôi cần bên ngoài mã song song và sử dụng kết quả bên trong nó. Điều này là ok. Vì vậy, tôi gần như chắc chắn rằng các vấn đề đến từ FIST.

Tôi có hai câu hỏi:

• Bạn có biết nếu thư viện FIST là chủ đề an toàn không?

• Nếu không, bạn có thể gợi ý cho tôi thư viện tam giác C++ (C hoặc, tốt hơn) để thay thế FIST (có thể với các buổi biểu diễn tương đương) không?

chỉnh sửa:

Thực ra, tôi không biết nếu "thread-safe" là chính xác những gì tôi muốn: Tôi chỉ cần một thư viện tringulation thể tính toán nhiều triangulations độc lập cùng một lúc .

Tôi nghĩ rằng nếu thư viện đã biến không toàn cầu và nếu nó có một lớp học mà không static biến

class triangulation 
{ 
    // no static variables 

    void execute_triangulation(); 
} 

nó có thể là đủ. Vì vậy, tôi có thể sử dụng các phiên bản khác nhau của lớp đó và chạy song song với phương thức của chúng.

Answer 1

Bạn có thể sử dụng 2D triangulation package of CGAL để thay thế FIST và sau đó sử dụng nó làm đầu vào của thư viện bên thứ ba có tổng số tiền Minskowski. Hình tam giác CGAL rất nhanh và đáng tin cậy. Bạn có thể triangulate đa giác và hình dạng phức tạp bằng cách sử dụng triangulation Delaunay hạn chế.

Nhân tiện, bạn sử dụng thư viện Minkowsky nào?

Answer 2

Nó phụ thuộc rất nhiều vào những gì bạn có nghĩa là bằng cách này:

Kể từ mã của tôi là parallelizable tôi giới thiệu đa luồng

Bạn cần phải cụ thể hơn để có được sự giúp đỡ. Nó có nghĩa là "bạn đã giới thiệu đa luồng"? Ví dụ, không có thư viện nào bạn đề cập đến có tính toán song song các khoản tiền Minkowski (hoặc bất kỳ thứ gì khác) được tích hợp sẵn - bạn sẽ cần phải tự mình song song nó.

Đối với khoản tiền Minkowski, có thể sử dụng phương pháp giảm bản đồ: chia bộ dữ liệu đầu vào thành các phần nhỏ hơn, tính tổng Minkowski cho mỗi phần song song (bản đồ) và kết hợp trung gian khi chúng đến từ công nhân độc lập (giảm). Các yêu cầu cho việc này là đảm bảo an toàn chủ đề cơ bản (ví dụ: CGAL cung cấp cho bạn) quyền truy cập chỉ đọc vào các thông số của tính toán.

Answer 3

Một giải pháp khả thi và có thể kiểm tra ngay lập tức là đặt một mutex xung quanh mã gọi các phép tính Minkowski.Nếu điều đó nghe có vẻ thú vị và bạn không biết cách thực hiện, hãy thêm nhận xét chi tiết nền tảng bạn đang sử dụng và tôi hoặc người khác sẽ phác thảo cách thực hiện.

Ít nhất, điều đó sẽ cho bạn biết liệu bạn đã xác định chính xác sự cố chưa. Nếu các tính toán tạo thành một phần nhỏ trong tổng số băng thông của bạn, thì nó có thể trở thành một giải pháp tốt - nếu không chỉ là một bước trên đường.