Tidak diragukan lagi siapa pun yang telah mempelajari ilmu komputer dasar telah menghabiskan waktu merancang algoritma pengurutan – kode yang mengambil daftar item yang tidak diurutkan dan menempatkannya dalam urutan naik atau turun. Ini tantangan yang menarik karena ada begitu banyak cara untuk melakukan ini dan karena orang telah menghabiskan banyak waktu untuk mencari tahu bagaimana melakukan penyortiran ini seefisien mungkin.

Pengurutan sangat mendasar sehingga algoritme dibangun ke sebagian besar pustaka standar bahasa pemrograman. Dan dalam kasus pustaka C++ yang digunakan dengan kompiler LLVM, kode tersebut belum disentuh selama lebih dari satu dekade.

Tetapi grup AI DeepMind Google kini telah mengembangkan alat pembelajaran penguatan yang dapat mengembangkan algoritme yang sangat optimal tanpa terlebih dahulu dilatih tentang contoh kode manusia. Triknya adalah mempersiapkannya untuk memperlakukan pemrograman sebagai permainan.

Ini semua permainan

DeepMind, antara lain, dikenal karena mengembangkan perangkat lunak yang mengajari dirinya sendiri cara bermain game. Pendekatan ini terbukti sangat efektif, menaklukkan permainan yang beragam seperti catur, dia pergiDan StarCraft. Meskipun detailnya berbeda-beda tergantung pada game yang dihadapinya, program belajar dengan memainkannya sendiri dan menemukan opsi yang memungkinkannya memaksimalkan skor.

Karena belum dilatih tentang game yang dimainkan oleh manusia, sistem DeepMind dapat menemukan cara untuk memainkan game yang belum terpikirkan oleh manusia. Tentu saja, karena ia selalu bermain melawan dirinya sendiri, ada beberapa kejadian di mana ia mengembangkan titik buta yang dapat dieksploitasi oleh manusia.

Pendekatan ini sangat relevan dengan pemrograman. Paradigma bahasa yang hebat menulis kode yang efisien karena mereka telah melihat banyak contoh manusia. Tetapi karena itu, mereka sangat tidak mungkin mengembangkan sesuatu yang belum pernah dilakukan manusia sebelumnya. Jika kami ingin meningkatkan algoritme yang dipahami dengan baik, seperti fungsi pengurutan, mendasarkan sesuatu pada kode manusia yang ada, paling banter, akan memberi Anda kinerja yang setara. Tapi bagaimana Anda membuat AI benar-benar memilih pendekatan baru?

Orang-orang di DeepMind telah mengambil pendekatan yang sama dengan catur dan dia pergi: Mereka mengubah pengoptimalan kode menjadi sebuah game. Sistem AlphaDev mengembangkan algoritme kompilasi x86 yang memperlakukan latensi kode sebagai hit dan mencoba meminimalkan hit tersebut sambil memastikan bahwa kode berjalan hingga selesai tanpa kesalahan. Melalui pembelajaran penguatan, AlphaDev secara bertahap mengembangkan kemampuan untuk menulis kode yang sangat efisien dan kuat.

Di dalam AlphaDev

Mengatakan bahwa sistem meningkatkan latensi adalah masalah lain daripada menjelaskan cara kerjanya. Seperti kebanyakan sistem AI kompleks lainnya, AlphaDev terdiri dari beberapa komponen berbeda. Salah satunya adalah fungsi representasi, yang melacak keseluruhan kinerja kode saat sedang dikembangkan. Ini termasuk keseluruhan struktur algoritme, serta penggunaan register dan memori x86.

Sistem menambahkan instruksi perakitan satu per satu, dipilih oleh a Temukan pohon Monte Carlo– sekali lagi, pendekatan yang dipinjam dari sistem game. Aspek “pohon” dari pendekatan ini memungkinkan sistem untuk dengan cepat mempersempit ke area terbatas dari sejumlah besar kemungkinan instruksi, sementara Monte Carlo menambahkan tingkat keacakan pada instruksi yang tepat yang dipilih dari cabang itu. (Perhatikan bahwa “bantuan” dalam konteks ini mencakup hal-hal seperti rekaman khusus yang dipilih untuk membuat rakitan yang valid dan lengkap.)

Sistem kemudian mengevaluasi status kode rakitan untuk latensi dan validitas dan memberinya skor, dan membandingkannya dengan skor skor sebelumnya. Dan melalui pembelajaran penguatan, ini menghubungkan informasi tentang cara kerja berbagai cabang pohon, mengingat keadaan program. Seiring waktu, Anda “belajar” bagaimana mencapai kondisi permainan yang menang – seperti selesai – dengan skor maksimum, yang berarti latensi minimum.

Manfaat utama dari sistem ini adalah pelatihannya tidak harus menyertakan contoh kode apa pun. Sebagai gantinya, sistem menghasilkan contoh kodenya sendiri dan kemudian mengevaluasinya. Dalam prosesnya, tergantung pada informasi tentang set instruksi mana yang efektif dalam penyortiran.

Kode yang berguna

Pengurutan dalam program yang kompleks dapat menangani kelompok item yang besar dan sewenang-wenang. Tetapi pada tingkat perpustakaan standar, mereka dibangun dari sekumpulan besar fungsi yang sangat spesifik yang hanya menangani satu situasi atau beberapa kasus. Misalnya, ada algoritma terpisah untuk menyortir tiga item, empat item, dan lima item. Dan ada sekumpulan fungsi lain yang dapat menangani jumlah item yang berubah-ubah hingga maksimum – artinya Anda dapat memanggil satu yang menyortir hingga empat item, tetapi tidak lebih.

DeepMind telah menetapkan AlphaDev pada masing-masing fungsi ini, tetapi fungsinya sangat berbeda. Untuk fungsi yang menangani sejumlah elemen tertentu, dimungkinkan untuk menulis kode tanpa cabang mana pun yang mengeksekusi kode berbeda berdasarkan keadaan variabel. Akibatnya, kinerja kode ini umumnya sebanding dengan jumlah instruksi yang diperlukan. AlphaDev mampu mencukur semua instruksi Sort-3, Sort-5, dan Sort-8, dan bahkan lebih banyak lagi instruksi Sort-6 dan Sort-7. Hanya ada satu (peringkat 4) di mana dia tidak dapat menemukan cara untuk memperbaiki kode manusia. Berulang kali menjalankan kode pada sistem sebenarnya menunjukkan bahwa lebih sedikit instruksi menghasilkan kinerja yang lebih baik.

Menyortir sejumlah variabel entri melibatkan percabangan dalam kode, dan prosesor yang berbeda memiliki jumlah perangkat keras yang berbeda yang didedikasikan untuk menangani cabang-cabang ini. Oleh karena itu, kode tersebut dievaluasi berdasarkan kinerjanya pada 100 perangkat berbeda. Di sini sekali lagi, AlphaDev telah menemukan cara untuk mendapatkan kinerja ekstra, dan kita akan melihat cara melakukannya dalam satu situasi: fungsi yang menyortir hingga empat item.

Dalam implementasi saat ini di pustaka C++, kode menjalankan serangkaian pengujian untuk melihat berapa banyak elemen yang diperlukan untuk mengurutkan dan memanggil fungsi pengurutan khusus untuk jumlah elemen tersebut. Kode yang direvisi melakukan sesuatu yang bahkan lebih aneh. Menguji apakah ada dua elemen dan memanggil fungsi terpisah untuk mengurutkannya jika perlu. Jika hitungannya lebih besar dari dua, kode memanggil untuk menyortir tiga yang pertama. Jika ada tiga elemen, hasil semacam ini akan dikembalikan.

Namun, jika ada empat item untuk disortir, ia akan menjalankan kode khusus yang sangat efisien dalam memasukkan item keempat ke tempat yang sesuai dalam larik tiga item yang diurutkan. Ini sepertinya pendekatan yang aneh, tetapi secara konsisten mengungguli kode saya yang ada.

dalam produksi

Karena AlphaDev menghasilkan kode yang lebih efisien, tim ingin mengintegrasikannya kembali ke pustaka C++ standar LLVM. Masalahnya di sini adalah bahwa kode tersebut ada di rakitan dan bukan di C++. Jadi, mereka harus bekerja mundur dan mencari tahu kode C++ mana yang akan menghasilkan rakitan yang sama. Setelah ini selesai, kode tersebut digabungkan ke dalam rantai alat LLVM – pertama kali beberapa kode telah dimodifikasi selama lebih dari satu dekade.

Akibatnya, para peneliti memperkirakan bahwa kode AlphaDev sekarang dieksekusi triliunan kali sehari.

Alam, 2023. DOI: 10.1038 / s41586-023-06004-9 (tentang DOI).