Para peneliti dari EPFL, AMD, dan University of Novi Sad telah mengungkap inefisiensi lama dalam algoritma yang memprogram jutaan chip yang dapat dikonfigurasi ulang yang digunakan di seluruh dunia, sebuah penemuan yang dapat membentuk kembali bagaimana generasi masa depan ini dirancang dan diprogram.
Banyak industri, termasuk telekomunikasi, otomotif, kedirgantaraan dan fisika partikel bergantung pada jenis chip khusus yang disebut array gerbang yang dapat diprogram lapangan (FPGA). Tidak seperti chip tradisional, FPGA dapat dikonfigurasi ulang hampir tanpa henti, menjadikannya sangat berharga di bidang yang bergerak cepat di mana merancang chip khusus akan memakan waktu bertahun-tahun dan harganya harganya. Tetapi fleksibilitas ini hadir dengan tangkapan: efisiensi FPGA sangat tergantung pada perangkat lunak yang digunakan untuk memprogramnya.
Sejak akhir 1990 -an, sebuah algoritma yang dikenal sebagai Pathfinder telah menjadi tulang punggung routing FPGA. Tugasnya: Menghubungkan ribuan komponen sirkuit kecil tanpa membuat tumpang tindih. Selama beberapa dekade, itu bekerja dengan sangat baik sehingga menjadi standar. Namun, ketika sirkuit tumbuh lebih besar, para insinyur mulai menghadapi perlambatan yang membuat frustrasi dan sesekali kegagalan langsung. Desain yang seharusnya berhasil sering diberi label “tidak dapat keluar.”
Sekarang, dengan kolega dari University of Novi Sad dan perusahaan teknologi AMD, para peneliti dari Laboratorium Arsitektur Sistem Paralel (PARSA) di sekolah komputer dan komunikasi Ilmu Telah datang selangkah lebih dekat untuk melepaskan pekerjaan dalam algoritma klasik ini.
Dalam makalah baru -baru ini, yang menerima penghargaan kertas terbaik di IEEE ke -33 Simposium Internasional tentang Kustom yang Dapat Diprogram Lapangan Komputasi Mesin, Mereka mengungkapkan mengapa kegagalan ini terjadi dan bagaimana batas Pathfinder dapat diatasi.
Retak dalam algoritma
“Sebenarnya, tidak mengherankan bahwa Pathfinder terkadang gagal,” jelas Shashwat Shrivastava, kandidat PhD dengan Parsa dan penulis pertama makalah ini. “Sangat awal, para peneliti menunjukkan bahwa masalah di balik perutean FPGA sangat sulit. Kemudian, pencipta algoritma asli, bersama dengan beberapa kolaborator, menemukan kasus-kasus di mana Pathfinder tidak akan pernah berhasil-tetapi mereka mencatat kasus-kasus seperti itu tidak akan muncul dalam praktik.”
Selama beberapa dekade, tampaknya mereka benar – Pathfinder bekerja dengan sangat baik.
“Pathfinder bekerja dengan sangat baik, pada kenyataannya, bahwa ketika gagal, orang jarang mempertanyakan algoritma. Alih -alih bertualang di dalam untuk melihat apa yang sedang terjadi, mereka men -tweak parameternya, sirkuit yang dimodifikasi, atau beralih ke FPGA yang lebih besar,” tambah Stefan Nikolic, alumni EPFL dan sekarang seorang profesor di Universitas Novi Sedang. “Bagian dari alasan untuk ini adalah bahwa agak sulit untuk memahami apa yang sebenarnya dilakukan Pathfinder pada contoh-contoh penting praktis. Sirkuit modern sangat besar sehingga sinyal mereka membentuk hutan yang benar-benar di dalam chip.”
Masukkan hutan
“Jadi, kami benar-benar perlu melihat masing-masing pohon di hutan itu,” lanjut Shrivastava, “dan saya benar-benar bermaksud pohon. Setiap sinyal-koneksi yang membawa informasi antara komponen sirkuit harus mencapai beberapa tujuan tanpa tumpang tindih sinyal lain. Routing FPGA pada dasarnya adalah tentang membangun satu pohon untuk setiap sinyal pada chip.”
Saat mengerjakan proyek lain yang mengandalkan Pathfinder, tim terus melihat hasil yang menentang intuisi. Pada awalnya, mereka menyalahkan faktor -faktor eksternal, bukan algoritma itu sendiri. Akhirnya, mereka menyadari bahwa mereka membutuhkan contoh terkontrol: kasus kecil dan rumit di mana solusi pasti ada, dan di mana Pathfinder harus berhasil.
“Kami membutuhkan contoh nyata dan praktis, dan banyak dari mereka, untuk memahami apa yang sebenarnya terjadi,” Shrivastava menjelaskan. “Jadi, kami membangun kerangka kerja untuk secara otomatis mengekstrak masalah kecil dan sulit dari sirkuit nyata. Menyaksikan bagaimana Pathfinder berjuang dengan ini membantu kami mengungkap masalah yang tetap tersembunyi untuk waktu yang sangat lama.”
Kekuatan dalam kemitraan
“Terobosan ini akan jauh lebih sulit tanpa dukungan industri,” kata Mirjana Stojilovic, penasihat PhD Shrivastava. “Sejak awal, kami berkolaborasi dengan Chirag Ravishankar dan Dinesh Gaitonde dari AMD. Mereka membantu kami memodelkan FPGA sedekat mungkin dengan perangkat komersial, memastikan temuan kami memiliki dampak dunia nyata.”
Setelah kerangka kerja siap, segalanya bergerak dengan cepat. Tim menemukan bahwa Pathfinder sering membangun pohon perutean yang lebih besar dari yang diperlukan, meningkatkan risiko tumpang tindih. Masalahnya berasal dari urutan yang dibuat dan menambahkan cabang baru ke pohon.
“Dalam retrospeksi, ini intuitif, tetapi entah bagaimana itu sebagian besar tidak diketahui selama bertahun -tahun,” kata Shrivastava. “Solusi pertama kami sederhana: cobalah pesanan yang berbeda dan pilih yang menghasilkan pohon terkecil. Secara eksperimental, itu bekerja dengan sangat baik.”
Melihat ke depan
Tim sekarang sedang mengeksplorasi solusi yang lebih diskalakan. “Saya sangat bangga bahwa magang musim panas@EPFL telah berkontribusi secara signifikan. Salah satunya, Sun Tanaka, juga merupakan rekan penulis makalah ini,” tambah Stojilovic. “Penemuan kami dapat membentuk kembali bagaimana jutaan FPGA diprogram dan mempengaruhi desain generasi masa depan dari chip yang dapat dikonfigurasi ulang ini.”
