Thuật toán băm nào có thể song song? Tối ưu hóa băm của các tệp lớn sử dụng trên các CPU đa lõi

Question

Tôi quan tâm đến việc tối ưu hóa băm của một số tệp lớn (tối ưu hóa thời gian đồng hồ treo tường). I/O đã được tối ưu hóa đủ tốt và thiết bị I/O (SSD cục bộ) chỉ được khai thác ở mức khoảng 25% công suất, trong khi một trong các lõi CPU hoàn toàn tối đa.

Tôi có nhiều lõi hơn, và trong tương lai có thể sẽ có nhiều lõi hơn. Cho đến nay tôi đã chỉ có thể gõ vào lõi nhiều hơn nếu tôi xảy ra cần nhiều băm của cùng một tập tin, nói một MD5 và một SHA256 cùng một lúc. Tôi có thể sử dụng cùng một luồng I/O để cấp hai hoặc nhiều thuật toán băm, và tôi nhận được các thuật toán nhanh hơn được thực hiện miễn phí (như xa như thời gian đồng hồ treo tường). Khi tôi hiểu hầu hết các thuật toán băm, mỗi bit mới thay đổi toàn bộ kết quả, và nó vốn dĩ là thử thách/không thể làm song song.

Có bất kỳ thuật toán băm chính thống nào song song không?
Có bất kỳ băm không chính thống nào có thể song song (và có ít nhất một triển khai mẫu có sẵn) không?

Khi các CPU trong tương lai sẽ hướng tới nhiều lõi hơn và giảm tốc độ đồng hồ, có cách nào để cải thiện hiệu suất của băm tệp không? (khác với nitơ lỏng làm mát bằng cách ép xung?) hoặc là nó vốn không song song?

Answer 1

Thực tế, có rất nhiều nghiên cứu đang diễn ra trong lĩnh vực này. Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ hiện đang tổ chức một cuộc thi để thiết kế thế hệ tiếp theo của hàm băm cấp chính phủ. Hầu hết các đề xuất cho đó là song song.

Một ví dụ: http://www.schneier.com/skein1.2.pdf

mô tả của Wikipedia về tình trạng hiện tại của cuộc thi: http://en.wikipedia.org/wiki/SHA-3

Answer 2

Những loại SSD nào bạn có? Việc triển khai MD5 của C của tôi chạy ở mức 400 MB/s trên một lõi Intel Core2 đơn (2,4 GHz, không phải là Intel mới nhất). Bạn có thực sự có SSD hỗ trợ băng thông 1,6 GB/s không? Tôi muốn như vậy !

Có thể áp dụng băm cây trên bất kỳ hàm băm nào. Có một vài sự tinh tế và đặc tả Skein cố gắng xử lý chúng, tích hợp một số siêu dữ liệu trong chính hàm đó (điều này không thay đổi nhiều thứ cho hiệu suất), nhưng "chế độ cây" của Skein không phải là "Skein" SHA-3. Ngay cả khi Skein được chọn là SHA-3, đầu ra của một băm chế độ cây sẽ không giống như đầu ra của "Skein đơn giản".

Hy vọng rằng, một tiêu chuẩn sẽ được xác định tại một thời điểm nào đó, để mô tả băm chung của cây. Ngay bây giờ không có gì cả. Tuy nhiên, một số giao thức đã được xác định với sự hỗ trợ cho một băm cây tùy chỉnh với hàm băm Tiger, dưới tên "TTH" (Tiger Tree Hash) hoặc "THEX" (Tree Hash Exchange Format). Đặc điểm kỹ thuật cho TTH có vẻ hơi khó nắm bắt; Tôi tìm thấy một số tham chiếu đến bản nháp đã di chuyển hoặc biến mất.

Tuy nhiên, tôi hơi mơ hồ về khái niệm. Đó là loại gọn gàng, nhưng chỉ cung cấp hiệu năng nếu bạn có thể đọc dữ liệu nhanh hơn những gì mà một lõi đơn có thể xử lý và được cung cấp chức năng phù hợp và thực hiện đúng, một lõi đơn có thể băm khá nhiều dữ liệu mỗi giây. Một hash cây lây lan qua một số lõi đòi hỏi phải có dữ liệu được gửi đến các lõi thích hợp, và 1,6 GB/s không phải là băng thông nhỏ nhất từ ​​trước tới nay.

SHA-256 và SHA-512 không phải là rất nhanh. Trong số các ứng cử viên SHA-3, giả sử một bộ vi xử lý x86 ở chế độ 64 bit, một số người trong số họ đạt được tốc độ cao (hơn 300 MB/s trên Intel Core2 Q6600 2,4 GHz của tôi, với một lõi đơn - đó là những gì tôi có thể nhận ra của SHA-1, quá), ví dụ BMW, SHABAL hoặc Skein.Về mặt mã hóa, các mẫu thiết kế này hơi mới, nhưng MD5 và SHA-1 đã được mã hóa "bị hỏng" (khá hiệu quả trong trường hợp MD5, thay vì theo lý thuyết cho SHA-1) nên bất kỳ ứng viên nào trong vòng 2 SHA-3 nên ổn thôi.

Khi tôi đặt nắp "seer", tôi thấy rằng bộ vi xử lý sẽ tiếp tục trở nên nhanh hơn RAM, đến mức chi phí băm sẽ bị lấn át bởi băng thông bộ nhớ: CPU sẽ có chu kỳ đồng hồ để rảnh trong khi chờ cho dữ liệu từ RAM chính. Tại một số điểm, toàn bộ mô hình luồng (một RAM lớn cho nhiều lõi) sẽ phải được sửa đổi.

Answer 3

Bạn không nói những gì bạn cần băm của mình. Nếu bạn không trao đổi với thế giới bên ngoài nhưng chỉ để sử dụng nội bộ, chỉ cần chia từng tập tin thành nhiều phần, tính toán và lưu trữ tất cả các tổng kiểm tra. Sau đó, bạn có thể sử dụng nhiều lõi chỉ bằng cách ném một đoạn cho mỗi cái. Hai giải pháp mà bạn nghĩ đến là chia các tệp theo các khối có kích thước cố định (đơn giản hơn, nhưng sẽ sử dụng ít lõi hơn cho các tệp nhỏ hơn mà bạn không cần tất cả sức mạnh đó) hoặc trong một số khối cố định (sẽ sử dụng tất cả các lõi cho mọi tệp). Thực sự phụ thuộc vào những gì bạn muốn đạt được và phân phối kích thước tệp của bạn trông như thế nào.

Nếu, mặt khác, bạn cần băm cho thế giới bên ngoài, vì bạn có thể đọc từ các thư trả lời khác không thể với băm "chuẩn" (ví dụ: nếu bạn muốn gửi băm SHA1 để người khác kiểm tra với các công cụ khác nhau) vì vậy bạn phải tìm một nơi khác. Giống như tính toán băm khi bạn lưu trữ tệp, để truy xuất sau này hoặc tính toán băm trong nền với lõi 'miễn phí' và lưu trữ để truy xuất sau này.

Giải pháp tốt hơn phụ thuộc vào những hạn chế của bạn là gì và bạn có thể đầu tư vào không gian, thời gian hoặc sức mạnh CPU.