làm thế nào để bộ nhớ bản đồ một ma trận rất lớn?

Question

Giả sử bạn có một ma trận giá trị tính năng (40 điểm) lớn (40 điểm), các hàng là các tính năng và cột khác nhau là các mẫu/hình ảnh.

Bảng được precomputed cột khôn ngoan. Sau đó, nó hoàn toàn được truy cập hàng-khôn ngoan và đa luồng (mỗi thread tải toàn bộ một hàng) nhiều lần.

Cách tốt nhất để xử lý ma trận này là gì? Tôi đặc biệt cân nhắc hơn 5 điểm:

1. Vì nó chạy trên máy tính x64, tôi có thể ghi nhớ toàn bộ ma trận cùng một lúc nhưng điều đó có hợp lý không?
2. Còn ảnh hưởng của đa luồng (tính toán ban đầu đa luồng thì sao?)?
3. Cách bố trí ma trận: hàng hoặc cột chính?
4. Nó sẽ giúp đánh dấu ma trận là chỉ đọc sau khi kết thúc trước khi kết thúc?
5. Có thể sử dụng một số thứ như http://www.kernel.org/doc/man-pages/online/pages/man2/madvise.2.html để tăng tốc độ này?

Answer 1

Lập bản đồ bộ nhớ toàn bộ tệp có thể giúp quá trình này dễ dàng hơn nhiều.

Bạn muốn bố trí dữ liệu của mình để tối ưu hóa cho mẫu truy cập phổ biến nhất. Có vẻ như dữ liệu sẽ được viết một lần (cột khôn ngoan) và đọc nhiều lần (hàng khôn ngoan). Điều đó cho thấy dữ liệu nên được lưu trữ theo thứ tự hàng lớn.

Đánh dấu ma trận chỉ đọc khi tính toán trước có thể sẽ không giúp hiệu suất (có một số tối ưu hóa mức thấp nhất có thể, nhưng tôi không nghĩ bất cứ điều gì thực hiện), nhưng nó sẽ ngăn chặn lỗi vô tình ghi vào dữ liệu bạn không có ý định. Có thể là tốt.

madvise có thể sẽ hữu ích, khi bạn đã đăng ký và làm việc.

Lời khuyên chung của tôi: viết chương trình theo cách đơn giản nhất có thể, tuần tự lúc đầu, và sau đó đặt hẹn giờ xung quanh toàn bộ điều và các hoạt động chính khác nhau. Hãy chắc chắn rằng thời gian hoạt động chính tổng cộng cho thời gian tổng thể, vì vậy bạn có thể chắc chắn rằng bạn không bỏ lỡ bất cứ điều gì. Sau đó, nhắm mục tiêu nỗ lực cải thiện hiệu suất của bạn đối với các thành phần thực sự đang dùng nhiều thời gian nhất.

Mỗi lần JimR đề cập đến 4MB trang trong nhận xét của anh ấy, bạn có thể muốn xem xét đến hugetlbfs hoặc sử dụng bản phát hành hạt nhân Linux với hỗ trợ trang lớn trong suốt (được hợp nhất cho 2.6.38, có thể được vá vào phiên bản cũ hơn). Điều này có thể sẽ giúp bạn tiết kiệm rất nhiều TLB bỏ lỡ, và thuyết phục hạt nhân để làm đĩa IO trong khối đủ lớn để khấu hao bất kỳ tìm kiếm trên không.

Answer 2

1. Có thể, xem bên dưới.
2. Kích thước của tổng số bộ làm việc của tất cả các luồng không được vượt quá RAM có sẵn, nếu không chương trình sẽ chạy ở tốc độ ốc do hoán đổi.
3. Bố cục phải khớp với mẫu truy cập, miễn là điều kiện 2 được tôn trọng.
4. Bạn có ý nghĩa gì khi "đánh dấu là chỉ đọc"?
5. Đo lường.

Re 3: Nếu bạn có, ví dụ:, 8 CPU nhưng không có đủ RAM để tải 8 hàng, bạn nên làm cho mỗi luồng xử lý hàng của nó liên tục trong các khối có thể quản lý được. Trong trường hợp này, khối bố trí của một ma trận sẽ có ý nghĩa. Nếu thread PHẢI có toàn bộ hàng trong bộ nhớ để xử lý nó, tôi sợ rằng bạn không thể sử dụng tất cả các CPU, vì quá trình sẽ bắt đầu đập, tức là, đá ra một số tập con của ma trận ra khỏi ram và tải lại một tập hợp con cần thiết khác. Điều này là hơi ít xấu hơn so với trao đổi đầy đủ như ma trận là không bao giờ sửa đổi, do đó, nội dung của các trang không cần phải được ghi vào tập tin trao đổi trước khi bị đuổi ra ngoài. Nhưng nó vẫn làm tổn thương hiệu suất tồi tệ.

Ngoài ra, làm truy cập ngẫu nhiên I/O từ nhiều chủ đề là một ý tưởng tồi, đó là những gì bạn sẽ kết thúc làm nếu bạn sử dụng mmap(). Bạn có (có lẽ) chỉ có một đĩa đơn, và I/O song song sẽ làm cho nó chậm hơn. Vì vậy, mmap() có thể không có ý nghĩa và bạn có thể đạt được hiệu suất I/O tốt hơn bằng cách đọc dữ liệu tuần tự vào ram.

Lưu ý rằng 40GB là khoảng 10,5 triệu trang trong 4096 byte. Bằng cách làm mmap(), bạn sẽ, trong trường hợp xấu nhất, làm chậm tính toán bởi nhiều đĩa cứng tìm kiếm. Với 8ms mỗi lần tìm kiếm (được lấy từ wikipedia), bạn sẽ mất 83666 giây, tức là gần một ngày!

Answer 3

Nếu bạn có thể phù hợp với toàn bộ điều vào bộ nhớ chính, thì có: bộ nhớ ánh xạ tất cả, và nó không quan trọng cho dù đó là cột chính hoặc hàng lớn. Tuy nhiên, ở 40+ Gb, tôi chắc chắn nó quá lớn đối với bộ nhớ chính. Trong trường hợp này:

1. Không, đừng lập bản đồ toàn bộ! Ít nhất, không mong đợi bộ nhớ để làm việc như bộ nhớ bình thường nếu bạn bản đồ tất cả. Chương trình của bạn sẽ mất vĩnh viễn nếu bạn không xử lý đúng các vấn đề về i/o.
2. Sự cố truy cập đa luồng được giải quyết nếu bạn lưu trữ hàng chính (có vẻ như bạn không viết cột đa luồng).
3. Bạn nên đặt nó ra hàng khôn ngoan, giả sử mỗi ô được viết một lần và sau đó đọc nhiều lần.
4. Có, tôi nghĩ rằng nó sẽ giúp đánh dấu ma trận là chỉ đọc sau khi nó được viết, nhưng hoàn toàn là một cách để ngăn chặn lỗi (tình cờ viết). Nó sẽ không ảnh hưởng đến hiệu suất.
5. Không, không có số lượng nhân thông minh đọc trước sẽ giải quyết vấn đề hiệu suất của bạn. Bạn cần phải giải quyết nó ở cấp độ thuật toán.

Tôi nghĩ bạn sẽ gặp phải vấn đề về hiệu suất với việc triển khai ngây thơ. Hoặc là máy tính với thrash trong khi viết (nếu bạn lưu trữ hàng chính) hoặc nó sẽ thrash trong khi truy vấn (nếu bạn lưu trữ cột chính). Sau này có lẽ là tồi tệ hơn, nhưng đó là một vấn đề cả hai cách.

Giải pháp đúng là sử dụng một biểu diễn trung gian không phải là hàng chính hay cột lớn mà là 'các ô vuông lớn'. Lấy 50.000 cột đầu tiên và lưu trữ chúng trong một tệp ánh xạ bộ nhớ (giai đoạn 1). Nó không quan trọng nếu đó là cột chính hoặc hàng lớn kể từ khi nó sẽ được hoàn toàn cư trú bộ nhớ. Sau đó, lấy từng hàng và viết nó vào tập tin ánh xạ bộ nhớ chính cuối cùng (giai đoạn 2). Sau đó lặp lại chu trình cho 50.000 cột tiếp theo, v.v.