Mengapa pembagian jauh lebih kompleks daripada operasi aritmatika lainnya?

39

Saya baru-baru ini menemukan sebuah kasus di mana saya membutuhkan operasi divisi integer pada chip yang tidak memiliki satu (ARM Cortex-A8). Ketika mencoba meneliti mengapa itu harus terjadi, saya menemukan bahwa secara umum pembagian membutuhkan lebih banyak siklus daripada penambahan, pengurangan atau penggandaan pada hampir semua arsitektur integer (atau fixed-point). Mengapa demikian? Apakah tidak dapat diwakili dengan logika dua-lapisan AND-OR seperti yang lainnya?

Phonon
sumber

Jawaban:

34

Division adalah algoritma iteratif di mana hasil dari hasil bagi harus digeser ke sisanya menggunakan ukuran Euclidean, lihat 2 ; sedangkan multiplikasi dapat direduksi menjadi serangkaian trik manipulasi bit (tetap).

aterrel
sumber
2
Dulu bahwa perkalian dan pembagian adalah operasi lambat. Multiplikasi saat ini sedikit lebih cepat (tetapi sedikit lebih lambat dari penambahan / pengurangan), tetapi pembagian masih lebih lambat dari yang lain. Saya percaya Newton-Raphson masih digunakan secara internal oleh sebagian besar untuk membalas nomor.
JM
12
(Di luar topik: "Operasi terbalik biasanya sulit. Lihat saja integrasi versus diferensiasi." - tergantung pada apakah yang Anda lakukan simbolis atau numerik. Diferensiasi mudah secara simbolis, tetapi secara numerik sulit; integrasi simbolis sulit, tetapi secara numerik mudah.)
JM
1
Oke, saya akan mengatasinya dengan mengatakan bahwa cubature adalah kaleng cacing yang berbeda; tetapi setidaknya dalam kasus satu dimensi, quadrature lebih mudah daripada diferensiasi.
JM
1
Bagaimanapun, invers selalu datang berpasangan. Mengapa Anda menyebut satu "operasi" dan yang lainnya "terbalik"?
David Ketcheson
2
Baik iterasi maupun invers membuatnya lebih sulit. Kekerasan pembagian berasal dari kenyataan bahwa Anda harus mengubah hasil dari hasil bagi menjadi sisa menggunakan ukuran Euclidean. Lihat teorema algoritma pembagian .
20

Sementara semua CPU saat ini tampaknya menggunakan pendekatan iteratif seperti yang disarankan aterrel , ada beberapa pekerjaan yang dilakukan pada pendekatan non-iteratif. Divisi Poin Floating Precision Variabel dan Root Square berbicara tentang implementasi non-iteratif divisi floating point dan kuadrat dalam FPGA , menggunakan tabel pencarian dan ekspansi seri taylor.

Saya menduga bahwa teknik yang sama memungkinkan untuk menjalankan operasi ini ke satu siklus (throughput, jika bukan latensi), tetapi Anda cenderung membutuhkan tabel pencarian yang besar , dan dengan demikian sangat luas area real-estate silikon untuk melakukannya .

Mengapa itu tidak layak?

Dalam mendesain CPU ada banyak trade-off yang harus dilakukan. Fungsionalitas, kompleksitas (jumlah transistor), kecepatan dan konsumsi daya semuanya saling terkait dan keputusan yang dibuat selama desain dapat membuat dampak besar pada kinerja.

Sebuah prosesor modern mungkin dapat memiliki unit floating point utama yang mendedikasikan transistor cukup pada silikon untuk melakukan divisi floating point dalam satu siklus , tetapi tidak mungkin menjadi penggunaan yang efisien dari transistor tersebut.

Multiply floating point membuat transisi ini dari iteratif ke non-iteratif satu dekade lalu. Saat ini, siklus tunggal bertambah dan bahkan bertambah banyak adalah hal yang biasa, bahkan dalam prosesor seluler.

Sebelum menjadi penggunaan anggaran transistor yang efisien, penggandaan, seperti pembagian, sering dilakukan dengan metode berulang. Saat itu, prosesor DSP yang berdedikasi dapat mendedikasikan sebagian besar silikon mereka untuk unit cepat multiplikasi terakumulasi (MAC) . Core2duo CPU memiliki floating point multiply latency 3 (nilainya keluar dari pipeline 3 cycle setelah masuk), tetapi dapat memiliki 3 multiply dalam penerbangan sekaligus, menghasilkan throughput satu siklus, sedangkan unit SSE2 dapat memompa banyak multiplikasi FP dalam satu siklus tunggal.

Alih-alih mendedikasikan area besar silikon ke unit pembagian satu siklus, CPU modern memiliki banyak unit, masing-masing dapat melakukan operasi secara paralel, tetapi dioptimalkan untuk situasi spesifik mereka sendiri. Faktanya, begitu Anda mempertimbangkan instruksi SIMD seperti SSE atau grafis terintegrasi CPU dari Sandy Bridge atau yang lebih baru dari CPU, mungkin ada banyak unit pembagian titik apung pada CPU Anda.

Jika pembagian floating point generik lebih penting bagi CPU modern maka mungkin masuk akal untuk mendedikasikan area silikon yang cukup untuk membuatnya menjadi siklus tunggal, namun sebagian besar pembuat chip jelas memutuskan bahwa mereka dapat menggunakan silikon dengan lebih baik dengan menggunakan gerbang itu untuk hal-hal lain . Jadi satu operasi lebih lambat, tetapi secara keseluruhan (untuk skenario penggunaan khas) CPU lebih cepat dan / atau mengkonsumsi daya lebih sedikit.

Mark Booth
sumber
Sepengetahuan saya, tidak ada chip yang memiliki latensi pembagian siklus tunggal untuk floating point. Misalnya, tabel instruksi Agner Fog untuk Intel, AMD, dan VIA CPU mencantumkan DIVPS (SSE packed floating-point divide) sebagai 10-14 siklus. Saya tidak dapat menemukan perangkat keras dengan instruksi pembagian siklus tunggal, tetapi saya bersedia terbukti salah. Itu tidak umum sejauh yang saya tahu.
Bill Barth
@ Bill - Terima kasih, kamu benar. Saya yakin saya telah melihat operasi divisi satu-siklus dalam chip DSP sebelumnya, jadi anggap itu akan membuat itu jalan ke desktop, seperti halnya siklus-tunggal, tetapi saya tidak dapat menemukan referensi sekarang. Saya telah memperbarui jawaban saya dan menambahkan beberapa informasi yang relevan tentang metode yang tidak berulang yang mungkin memungkinkannya di masa depan. Sungguh menakjubkan untuk berpikir bahwa pembagian tidak lebih efisien per siklus sekarang daripada kembali ketika saya menggunakan transputer.
Mark Booth
1
Saya pikir DSP melakukannya dengan membatasi rentang di mana mereka akurat. Ini adalah strategi yang sama yang digunakan untuk pencarian + interpolasi untuk root kuadrat.
Matt Knepley
1
Saya tidak yakin apa latensi pembagian seperti itu. Pada 4 GHz, melakukan perjalanan bolak-balik ke tabel pencarian dalam siklus N sangat membatasi ukuran potensial dari tabel tersebut (misalnya, cache L1 stagnan pada masing-masing 32K). Pergi 3D akan membantu meningkatkan ini (tetapi menantang wrt. Pendinginan). Apakah Anda tahu latensi apa yang dapat dicapai untuk CPU 4GHz / 5GHz modern?
Matthieu M.
1
Untuk divps / divpd vs mulp / mulpd nomor latensi dan throughput, lihat Divisi titik mengambang vs perkalian titik mengambang . Saya mengambil data dari tabel instruksi Agner Fog dan memformatnya ke dalam ringkasan lintas u dan div throughput dan latency, untuk single vs double dan untuk lebar vektor SIMD yang berbeda. (Chip Intel biasanya memiliki pembagi SIMD yang hanya setengah lebar dari vektor ALU lainnya.)
Peter Cordes