Mendeteksi overflow dalam penjumlahan

Misalkan saya diberi array integer lebar tetap (yaitu mereka cocok dengan register lebar ), . Saya ingin menghitung jumlah pada mesin dengan aritmatika komplemen 2's, yang melakukan penambahan modulo dengan semantik sampul. Itu mudah - tetapi jumlahnya mungkin melebihi ukuran register, dan jika ya, hasilnya akan salah. $n$ $w$ $a_1, a_2, \dots a_n$ $S = a_1 + \ldots + a_n$ $2^w$

Jika jumlahnya tidak melimpah, saya ingin menghitungnya, dan untuk memverifikasi bahwa tidak ada kelebihan, secepat mungkin. Jika jumlahnya melimpah, saya hanya ingin tahu itu terjadi, saya tidak peduli dengan nilai apa pun.

Menambahkan angka secara naif tidak berfungsi, karena jumlah parsial mungkin meluap. Misalnya, dengan register 8-bit, adalah valid dan memiliki jumlah , meskipun jumlah parsial kisaran register . $(120, 120, -115)$ $125$ $120+120$ $[-128,127]$

Jelas saya bisa menggunakan register yang lebih besar sebagai akumulator, tapi mari kita asumsikan kasus yang menarik di mana saya sudah menggunakan ukuran register terbesar.

Ada teknik terkenal untuk menambahkan angka dengan tanda kebalikannya sebagai jumlah parsial saat ini . Teknik ini menghindari luapan pada setiap langkah, dengan biaya tidak ramah-cache dan tidak mengambil banyak keuntungan dari prediksi cabang dan eksekusi spekulatif.

Apakah ada teknik yang lebih cepat yang mungkin mengambil keuntungan dari izin untuk melimpah jumlah parsial, dan lebih cepat pada mesin khas dengan bendera melimpah, cache, prediktor cabang, dan eksekusi serta pemuatan spekulatif?

(Ini adalah tindak lanjut dari penjumlahan aman Overflow )

algorithms arrays integers numerical-analysis Gilles 'SANGAT berhenti menjadi jahat'
sumber

Mengapa solusi Dave tidak bekerja dengan baik dengan cache dan pipa menurut Anda? Jika Anda melakukan sesuatu yang mirip dengan partisi Quicksort di tempat dengan pivot virtual , Anda memperlakukan cache dengan baik selama partisi dan penjumlahan berikut. Saya tidak tahu tentang mispredictions cabang selama mempartisi, tetapi fase penjumlahan harus dilakukan dengan baik dalam hal itu juga.

0

$0$

Raphael

@ Raphael Dalam aplikasi saya, overflow adalah kasus luar biasa. Persyaratan yang sesuai dengan "apakah ini meluap?" dengan demikian dilayani dengan baik oleh prediksi cabang. Persyaratan terkait dengan "Apakah angka ini positif?" tidak bisa diprediksi. Efek cache memang sedikit karena Anda memiliki dua kursor, bukan satu.

Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

Anda dapat menambahkan jumlah ukuran tanpa meluap jika Anda menggunakan bit aritmatika. Saran saya adalah melakukan hal itu dan kemudian memeriksa apakah hasilnya ada dalam kisaran. Algoritma untuk aritmatika multiprecision terkenal (lihat TAOCP bagian 4.3 jika Anda memerlukan referensi), seringkali ada dukungan perangkat keras untuk penambahan ( membawa bendera dan menambahkan dengan membawa instruksi), bahkan tanpa dukungan seperti itu Anda dapat menerapkannya tanpa lompatan bergantung pada data ( yang bagus untuk lompat prediktor) dan Anda hanya perlu satu pass pada data dan Anda dapat mengunjungi data dalam urutan yang paling nyaman (yang bagus untuk cache). $n$ $w$ $\lceil \log n\rceil + w$

Jika data tidak sesuai dengan memori, faktor pembatasnya adalah IO dan seberapa baik Anda berhasil dalam tumpang tindih IO dengan perhitungan.

Jika data sesuai dengan memori, Anda mungkin akan memiliki (satu-satunya pengecualian yang dapat saya pikirkan adalah mikroprosesor 8-bit yang biasanya memiliki 64K memori) yang berarti Anda melakukan aritmatika presisi ganda . Overhead atas loop melakukan $\lceil \log n\rceil \leq w$ $w$ bit aritmatika bisa hanya dua instruksi (satu untuk menandatangani memperpanjang, yang lain untuk menambah dengan membawa) dan sedikit peningkatan tekanan register (tapi jika saya benar, bahkan register x86 yang kelaparan memiliki cukup register bahwa satu-satunya akses memori di loop batin dapat mengambil data). Saya pikir itu mungkin bahwa prosesor OO akan dapat menjadwalkan operasi tambahan selama latensi beban memori sehingga loop batin akan dieksekusi pada kecepatan memori dan dengan demikian latihan akan menjadi salah satu dari memaksimalkan penggunaan bandwidth yang tersedia (prefetch). atau teknik interleaving dapat membantu tergantung pada arsitektur memori).

Mempertimbangkan poin terbaru, sulit untuk memikirkan algoritma lain dengan kinerja yang lebih baik. Ketergantungan data (dan dengan demikian tidak dapat diprediksi) melompat keluar dari pertanyaan seperti beberapa melewati pada data. Bahkan mencoba menggunakan beberapa inti prosesor saat ini akan sulit karena bandwidth memori mungkin akan jenuh, tetapi itu bisa menjadi cara mudah untuk mengimplementasikan akses yang disisipkan.

Pemrogram
sumber

Saya tidak dapat menambah ukuran register di mesin saya. Asumsikan saya sudah menggunakan ukuran register sebesar mungkin.

Gilles 'SO- berhenti menjadi jahat'

@ Gilles, prosesor yang saya tahu memiliki flag melimpah yang Anda ingin kami manfaatkan juga bawa carry dan tambahkan dengan carry carry . Bahkan pada mereka yang tidak (selain MIPS?), Aritmatika multiprecision akan menjadi kandidat yang serius (hanya memiliki satu akses data - baik untuk cache -, mengaksesnya secara berurutan - baik untuk pra-pengisi cache - -, dan dapat diimplementasikan tanpa lompatan bergantung data - bagus untuk prediktor lompat).

Pemrogram

Apa yang Anda maksud dengan “aritmatika multiprecision”? Saya pikir maksudmu floating point. Tetapi banyak arsitektur tidak memiliki register floating point yang cukup besar, jika ada. Katakan saya menambahkan bilangan bulat 64-bit pada amd64, atau bilangan bulat 32-bit pada ARM tanpa VFP.

Gilles 'SO- berhenti menjadi jahat'

@Gilles, saya maksudkan apa yang dijelaskan dalam bagian 4.3 dari TAOCP: penggunaan beberapa kata untuk mewakili nilai yang tidak dapat disimpan dalam satu kata. Bignum adalah varian di mana jumlah kata disesuaikan secara dinamis, tebakan saya adalah bahwa di sini Anda dapat menentukan batas maksimal untuk jumlah kata yang diperlukan (yaitu 2 jika data Anda ada dalam memori; jika tidak, bekerja untuk menumpukkan IO dengan perhitungan akan menjadi titik tindakan pertama, Anda akan terikat IO) dan cukup gunakan, itu akan cukup rendah sehingga menangani sejumlah kata yang bervariasi akan lebih mahal.

Pemrogram

Ah, baiklah. Bisakah Anda menjelaskan hal ini dalam jawaban Anda? Apakah Anda memiliki referensi dengan pengaturan waktu dan perbandingan dengan metode lain?

Gilles 'SANGAT berhenti menjadi jahat'

Pada mesin di mana tipe integer berperilaku sebagai cincin aljabar abstrak [pada dasarnya berarti bahwa mereka membungkus], seseorang dapat menghitung jumlah item [i] dan (item [i] >> 16) hingga sekitar 32767 item. Nilai pertama akan memberikan 32 bit yang lebih rendah dari jumlah yang benar. Nilai terakhir akan menghasilkan bit 16-47 dari sesuatu yang dekat dengan jumlah yang benar, dan menggunakan nilai sebelumnya itu dapat dengan mudah disesuaikan untuk menghasilkan bit 16-47 dari jumlah yang benar tepat.

Pseudocode akan menjadi seperti:

Sum1=0 : Sum2 = 0
For up to 32768 items L[i] in list
  Sum1 = Sum1 +L[i]
  Sum2 = Sum2 +(L[i] >> 16) ' Use sign-extending shift
Loop
Sum1MSB = Sum1 >> 16 ' Cannot use division of numbers can be negative--see below
Sum2Mid = Sum2 and 65535
Sum2Adj = Sum1MSB - Sum2Mid
If Sum2Adj >= 32768 then Sum2Adj = Sum2Adj - 65536
Sum2 += Sum2Adj

Setelah kode di atas, Sum2 dan Sum1 bersama-sama harus menghasilkan jumlah yang benar, terlepas dari intervensi overflow. Jika perlu untuk total lebih dari 32768 angka, mereka dapat dibagi menjadi kelompok-kelompok 32768, dan setelah menghitung Sum2 untuk setiap kelompok, seseorang dapat menambahkannya ke "variabel besar" dua variabel untuk semua kelompok secara keseluruhan.

Dalam beberapa bahasa, operator shift kanan dapat digantikan oleh divisi dengan 65536. Itu umumnya bekerja saat menghitung Sum2, tetapi tidak saat mengekstraksi Sum1MSB. Masalahnya adalah bahwa beberapa bahasa membulatkan pembagian ke nol sementara di sini diperlukan untuk melakukan pembulatan pembagian ke angka yang lebih rendah berikutnya (menuju infinity negatif). Kesalahan menghitung Sum2 akan diperbaiki nanti, tetapi kesalahan menghitung Sum2LSB akan mempengaruhi hasil akhir.

Perhatikan bahwa tidak ada dalam hasil akhir akan menunjukkan apakah salah satu perhitungan yang melibatkan Sum1 telah "meluap", tetapi jika nilai dijamin untuk membungkus kode dengan bersih tidak perlu peduli tentang apakah ada overflow telah terjadi.

supercat
sumber