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.
programming-languages
hardware
sorting
Viktor Maia
sumber
sumber
Jawaban:
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.
sumber
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.
sumber
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.
sumber