Thuật toán nào được hưởng lợi nhiều nhất từ ​​việc nhân lên hợp nhất?

Question

fma(a,b,c) tương đương với a*b+c ngoại trừ nó không làm tròn kết quả trung gian.

Bạn có thể cho tôi một số ví dụ về các thuật toán không có lợi cho việc tránh làm tròn này không?

Nó không rõ ràng, như làm tròn sau khi phép nhân mà chúng ta tránh có xu hướng ít vấn đề hơn làm tròn sau khi bổ sung mà chúng ta không.

Answer 1

taw nhấn vào một ví dụ quan trọng; nói chung, FMA cho phép các nhà văn thư viện thực hiện hiệu quả nhiều hoạt động điểm nổi khác với làm tròn chính xác.Ví dụ, một nền tảng có FMA có thể sử dụng nó để thực hiện phân chia tròn và căn bậc hai một cách chính xác (PPC và Itanium đã thực hiện phương pháp này), cho phép FPU về cơ bản là một máy FMA mục đích duy nhất. Peter Tang và John Harrison (Intel), và Peter Markstein (HP) có một số giấy tờ giải thích việc sử dụng này nếu bạn tò mò.

Ví dụ taw mang lại hữu ích hơn rất nhiều so với chỉ trong giới hạn lỗi theo dõi. Nó cho phép bạn đại diện cho sản phẩm của hai số dấu phẩy động như một tổng của hai số dấu chấm động mà không có bất kỳ lỗi làm tròn nào; điều này khá hữu ích trong việc triển khai các hàm thư viện dấu phẩy động được làm tròn chính xác. Sách của Jean-Michel Muller hoặc các giấy tờ trên crlibm sẽ là những nơi bắt đầu tốt để tìm hiểu thêm về những cách sử dụng này.

FMA cũng rất hữu ích trong việc giảm đối số trong các thường trình kiểu toán học-thư viện đối với một số loại đối số nhất định; khi một người đang làm giảm đối số, mục tiêu của việc tính toán thường là một từ có dạng (x - a*b), trong đó (a*b) gần như bằng x; đặc biệt, kết quả thường là theo thứ tự của lỗi làm tròn trong cụm từ (a*b), nếu điều này được tính mà không có FMA. Tôi tin rằng Muller cũng đã viết một số về điều này trong cuốn sách của ông.

Answer 2

Off đỉnh đầu của tôi - nhân Matrix, quy tắc của Newton, đánh giá đa thức, phương pháp số

Answer 3

Lợi ích chính của FMA là nó có thể nhanh gấp hai lần. Thay vì dùng 1 chu trình cho phép nhân và sau đó 1 chu kỳ cho phép cộng, FPU có thể phát hành cả hai thao tác trong cùng một chu kỳ. Rõ ràng, hầu hết các thuật toán sẽ được hưởng lợi từ các hoạt động nhanh hơn.

Answer 4

Một số ví dụ: Sản phẩm chấm vector. Biến đổi Fourier. Xử lý tín hiệu số. Đa thức. Tất cả mọi thứ.

Đó là câu hỏi tối ưu hóa và khai thác phần cứng nhiều hơn bất kỳ điều gì khác. Tổng sản phẩm là một yêu cầu rất phổ biến trong các phương pháp số, và cách này cho phép bạn đưa ra một chỉ dẫn rõ ràng cho trình biên dịch về cách làm một điều nhanh và có lẽ với độ chính xác cao hơn một chút. Trừ khi tôi bị nhầm lẫn, trình biên dịch được tự do thay thế a = b * c + d bằng lệnh FMA, nhưng nó cũng không miễn phí. (trừ khi các cuộc gọi chuẩn cho làm tròn, nhưng các trình biên dịch thực tế thường xuyên vi phạm các tiêu chuẩn theo những cách nhỏ).

Answer 5

Điều duy nhất tôi tìm thấy cho đến nay là "biến đổi không có lỗi". Đối với bất kỳ lỗi số dấu phẩy động nào từ a+b, a-b và a*b cũng là số dấu chấm động (trong vòng tới chế độ gần nhất, giả sử không có tràn/tràn, v.v.).

Lỗi bổ sung (và rõ ràng là trừ) rất dễ tính; nếu abs(a) >= abs(b), lỗi chính xác là b-((a+b)-a) (2 thất bại, hoặc 4-5 nếu chúng ta không biết cái nào lớn hơn). Lỗi nhân là tầm thường để tính toán với fma - nó chỉ đơn giản là fma(a,b,-a*b). Nếu không có fma đó là 16 flops của mã khá khó chịu. Và giả lập hoàn toàn chung của một cách chính xác làm tròn fma thậm chí còn chậm hơn thế.

Thêm 16 lần theo dõi lỗi cho mỗi lần thực hiện tính toán thực sự là quá mức cần thiết, nhưng chỉ với 1-5 lần thử nghiệm thân thiện với đường ống khá hợp lý và đối với nhiều thuật toán dựa trên 50% -200% chi phí và bù lại kết quả là lỗi nhỏ như thể tất cả các phép tính đã được thực hiện gấp đôi số bit chúng, tránh điều kiện bị lỗi trong nhiều trường hợp.

Điều thú vị là, fma không bao giờ được sử dụng trong các thuật toán này để tính toán kết quả, chỉ để tìm lỗi, vì tìm lỗi fma chậm như tìm lỗi nhân không có fma.

Từ khóa có liên quan để tìm kiếm sẽ là "giao thức Horner được đền bù" và "sản phẩm chấm được đền bù", với chương trình Horner mang lại lợi ích nhiều hơn nữa.

Answer 6

Nó đã được giải thích khá tốt trên Wikipedia entry for FMA rằng các thuật toán mà có cái gì để làm với tích lũy các sản phẩm hưởng lợi nhiều nhất từ ​​việc sử dụng FMA:

A fast FMA can speed up and improve the accuracy of 
many computations that involve the accumulation of products: 

* Dot product 
* Matrix multiplication 
* Polynomial evaluation (e.g., with Horner's rule) 
* Newton's method for evaluating functions.