Mengapa komputer tidak dilengkapi dengan perangkat keras khusus seperti menyortir jaringan?

10

Alih-alih pemrograman seperti yang kita lakukan, mengapa kita tidak membuat spesifikasi tugas umum seperti "menyortir", dan kemudian membiarkan lingkungan mengkompilasinya untuk memanfaatkan perangkat kerasnya dengan sebaik-baiknya? Dengan cara ini, kami dapat mengirimkan komputer dengan perangkat keras khusus baru seperti menyortir jaringan, dan itu akan bekerja secara otomatis dengan kode yang ada.

Viktor Maia
sumber
2
Beli papan PCI FPGA dan terapkan ekstensi apa pun yang Anda suka.
SK-logic
Perangkat keras bukanlah sihir. Banyak hal tidak dapat dipercepat banyak (atau sama sekali) oleh perangkat keras khusus, dan bahkan jika bisa, perangkat keras yang ada seringkali harus disesuaikan (atau setidaknya dikompilasi ulang). Lihat yosefk.com/blog/its-done-in-hardware-so-its-cheap.html
3
@ WorldEngineer Saya tidak melihat bagaimana itu masuk ke dalam gambar. Rata-rata pengguna Anda tidak tahu untuk apa 80% hal dalam CPU modern, mereka senang karena mereka diberi tahu itu membuat program mereka lebih cepat (dan ini memiliki kernel kebenaran). Jika penyortiran memang sama umum dengan anggapan OP dan dapat dioptimalkan dengan perangkat keras khusus, mereka akan meletakkannya di sebelah prediktor cabang ("apa itu, berkebun?"), Mengeluarkan siaran pers yang mengatakan mereka membuat aplikasi X dan Y 5% lebih cepat, dan jual.
1
Ini mengingatkan saya pada ide Conservation Cores , yang ditargetkan untuk efisiensi energi daripada kinerja puncak.
Paul A. Clayton

Jawaban:

19

Pertama-tama, komputer dilengkapi dengan perangkat keras khusus . Setiap laptop dan komputer desktop yang dijual selama beberapa tahun sekarang memiliki co-prosesor khusus, Graphics Processing Unit, yang menangani algoritma pemrosesan visual, seperti yang dibutuhkan oleh aplikasi video dan game. Komputer yang sangat besar ( misalnya , "superkomputer", keluarga System Z IBM) memiliki berbagai prosesor khusus untuk menangani pemrosesan numerik ("pemrosesan vektor"), dll .

Kedua, pengurutan adalah salah satu aspek komputasi yang paling banyak diteliti, dan ternyata terlalu rumit untuk dibangun menjadi perangkat keras untuk lebih dari sekadar kasus yang paling sederhana. Penyortiran adalah tentang kecepatan dan kebenaran. Kecepatan tergantung pada pilihan algoritma, jenis dan variasi dalam data, dan volume data. Kebenaran tergantung pada jenis dan konteks data. Sangat sepele untuk menyortir array integer berukuran sedang yang sesuai dengan ukuran kata asli CPU ( mis, 31 atau 63 bit plus tanda). Mengurutkan string karakter yang mengandung lebih dari sekadar nilai ASCII sangatlah kompleks - IBM menerbitkan buku 500+ halaman 20 tahun yang lalu hanya membahas masalah rangkaian karakter dalam konteks batasan nasional dan penggunaan umum. Dan kemudian ada pertanyaan tentang data yang tidak bersebelahan - pengurutan daftar yang ditautkan melibatkan pengejaran pointer di seluruh memori.

Ross Patterson
sumber
10

Masalah utama adalah bahwa algoritma pengurutan (1) membutuhkan banyak fleksibilitas, dan (2) akan sangat sulit untuk mempercepat menggunakan perangkat keras.

Satu hal adalah algoritma pengurutan sudah cukup cepat untuk berlari lebih cepat dari bandwidth memori prosesor - prosesor akan menghabiskan sebagian besar waktunya menunggu data bergerak mundur dan maju ke memori utama. Co-processor sorting yang dipercepat perangkat keras atau instruksi sortasi khusus akan memiliki masalah yang sama.

Cara bandwidth memori ini sedang ditangani adalah dengan menggunakan algoritma dan struktur data yang lebih baik yang memiliki "lokalitas" yang lebih baik, dan masih ada pekerjaan signifikan yang dilakukan di bidang ini, khususnya "algoritma cache cache lupa" (mereka tidak menyadari dalam arti bahwa mereka bekerja baik terlepas dari rincian caching, sedangkan algoritma "cache aware" disetel untuk ukuran halaman cache tertentu, dll).

Sebaliknya, aplikasi media (audio dan grafik, khususnya grafik 3D) memanfaatkan beberapa struktur yang sangat berulang - tentu saja ada fleksibilitas, tetapi itu dibangun di atas fondasi yang besar dan sangat terstruktur dengan baik. Itu memungkinkan akselerasi grafik untuk memulai dengan hal-hal seperti Blitting (operasi blok copy yang dapat dikonfigurasi tetapi masih sangat terstruktur) dan gambar garis / poligon. Ini berarti bahwa ketika pemrosesan grafis dan suara semakin canggih, operasi vektor menjadi target yang jelas untuk optimasi - MMX pertama (vektor bilangan bulat) kemudian SSE (vektor pelampung). Itu berarti ada struktur yang didefinisikan dengan cukup baik untuk bagaimana mesin grafis 3D bekerja ketika pipa grafis 3D fungsi lama dipindahkan ke perangkat keras grafis 3D.

Namun dengan grafik 3D, apa yang pernah dilakukan dalam perangkat keras sekarang dilakukan dalam perangkat lunak untuk fleksibilitas - shaders adalah perangkat lunak, misalnya, yang merupakan cara kami mendapatkan sejumlah besar shader yang berbeda memberikan tampilan bahan yang berbeda. Namun, perangkat lunak itu masih bekerja dengan cara yang jauh lebih terstruktur daripada perangkat lunak umum, dan karena itu masih dapat menggunakan platform perangkat keras yang jauh lebih khusus. Itulah sebabnya kartu grafis Anda sekarang dapat mempercepat segalanya mulai dari fisika hingga cracking passwords - aplikasi yang juga sesuai dengan model yang sama dan dapat diimplementasikan secara efisien menggunakan set instruksi yang disediakan prosesor grafis modern.

Prosesor grafis sekarang adalah keturunan spiritual atau aktual dari prosesor sinyal digital, yang (dan mungkin masih) semacam prosesor khusus untuk menangani sinyal digital (misalnya audio).

Yang mengarah ke titik akhir - algoritma pengurutan dapat dipercepat oleh perangkat keras. Bergantung pada data Anda, pengurutan dapat ditangani menggunakan instruksi MMX atau SSE (single-instruction-multiple-data) pada prosesor Anda, tetapi mungkin tidak banyak gunanya karena masalah bandwidth memori - mungkin Anda bisa sedikit lebih hemat daya meskipun begitu. Namun, Anda juga bisa menggunakan perangkat keras grafis Anda. Dengan begitu, Anda dapat memanfaatkan bandwidth memori yang jauh lebih baik untuk kartu grafis. Anda tidak akan bisa mengganti segala macam cara ini, tapi itu pasti mungkin dan mungkin dilakukan jika perlu.

TKI karena berbagai masalah ekonomi dan praktis, merancang perangkat keras khusus untuk mempercepat tugas yang relatif sempit seperti menyortir tidak masuk akal. Sebuah fitur yang mempercepat berbagai tugas, atau yang membuat perangkat keras akselerasi yang ada berlaku untuk berbagai tugas yang lebih luas seringkali jauh lebih masuk akal.

Steve314
sumber
3

Tetapi mereka melakukannya! Mereka disebut ekstensi set instruksi. (Hal-hal seperti SSE dan sejenisnya)

Tugas-tugas tertentu memiliki implementasi yang sangat bagus dalam perangkat lunak. Biasanya implementasi tersebut cukup baik untuk melakukan pekerjaan, sehingga tidak ada perangkat keras khusus yang diperlukan. Jika Anda membuat beberapa jenis perangkat keras khusus, Anda harus memiliki beragam aplikasi untuk membuatnya berharga.

Jika Anda melihat perangkat keras yang dapat membuat ini berfungsi, tebakan saya adalah Anda akan melihat sesuatu seperti FPGA. Seperti yang Anda lihat dengan FPGA, chip akan menjadi jauh lebih mahal sementara itu tidak berlaku untuk banyak aplikasi.

Onno
sumber
Saya harus google untuk SSE, tetapi, sebelumnya, penyortiran mungkin universal. Apakah ini diterapkan pada tingkat perangkat keras?
MaiaVictor
Eh juga, saat kami di sana, maukah Anda merekomendasikan buku?
MaiaVictor
Saya hanya berbicara tentang optimasi spesifik pekerjaan yang diterapkan pada prosesor gaya CPU secara umum, karena jaringan penyortiran digunakan sebagai contoh. Saya tidak tahu apakah SSE atau set instruksi lain termasuk pengurutan optimasi spesifik. Saya melakukan penyortiran jaringan google, dan karena ada implementasi umum yang dioptimalkan, saya pikir implementasi perangkat lunak dapat melakukan pekerjaan dengan baik jika implementasi dilakukan dengan benar.
Onno
Saya harus menunjukkan bahwa sebagian besar ekstensi set instruksi beroperasi pada tingkat yang lebih rendah daripada jaringan penyortiran yang Anda gunakan sebagai contoh, tetapi bukan tidak mungkin untuk merancang optimasi multi register yang dapat melakukan penyortiran dengan cara ini. Tetapi pertanyaan bagi para pembuat CPU adalah: "apakah akan membayar cukup untuk membenarkan biaya?".
Onno