Sejak 1990-an, saya takjub bahwa desain seluruh dunia mikroelektronika digital dikendalikan oleh dua kantor di California, yang berjarak 10 menit berkendara satu sama lain - Synopsys dan Cadence. Pada waktu itu, seperempat dunia desain dilakukan di Jepang (daratan Cina pada waktu itu masih dalam keadaan primitif), dan semua Sony, Hitachi, Fujitsu, dan raksasa lainnya membungkuk ke Amerika dan membayar jutaan dolar yang tak terhitung untuk program yang kemudian digunakan oleh perancang Jepang. Sekarang berlanjut dengan Samsung, Huawei dan bahkan dengan kantor Rusia yang mendesain microchip untuk ruang.
Tanah Rusia berhasil menumbuhkan Yandex versus Google, jadi mengapa tidak mencoba membuat beberapa program untuk merancang microchip? Anda dapat memulai dari yang kecil: untuk mempopulerkan kompetisi dan hackathon untuk pengembangan algoritma otomasi desain (Electronic Design Automation - EDA). Algoritma ini nyaman karena mereka memiliki banyak tingkat kesulitan: seorang siswa dapat menulis program Place & Route paling sederhana selama akhir pekan, tetapi sebuah program lanjutan akan membutuhkan puluhan tahun kerja untuk ratusan orang dan miliaran dolar dalam R&D.
Sekarang di Innopolis dekat Kazan mereka melakukan
acara untuk siswa dalam format "dua minggu pelatihan + hackathon .
" Salah satu topik adalah tugas EDA tradisional - menempatkan dan menelusuri grafik sirkuit elektronik ke dalam baris sel standar. Ini akan menarik untuk melihat apa yang tim kecil programmer dengan pemahaman dasar C ++ / Java / Python, metode untuk parsing teks, algoritma grafik dan keterampilan untuk memvisualisasikan struktur data menggunakan GUI dapat diimplementasikan dalam waktu singkat.
Jadi - pernyataan masalah:
Tugas ini terdiri dari tiga subtugas yang dapat ditangani oleh siswa yang berbeda:
- Parsing representasi teks dari grafik sirkuit digital.
- Menempatkan grafik pada barisan sel standar mikrosirkuit dan menghubungkan sel-sel ini dengan trek (tracing).
- Visualisasi hasil - tampilan pada layar trek sirkuit dan koneksi.
Input ke program adalah file teks dalam subset yang sangat terbatas dari bahasa deskripsi perangkat keras Verilog. File ini menjelaskan input dan output untuk rangkaian (input, output), koneksi internal (kawat) dan menyediakan daftar elemen logis dalam format "ketik instance-name (daftar koneksi)". File dapat diuraikan dalam C / C ++ menggunakan Lex + Yacc atau program serupa.
Hasil penguraian teks harus berupa representasi grafik dari elemen-elemen dalam memori. Tampilan ini akan digunakan oleh algoritma penempatan dan penelusuran, yang kemudian akan dibuat oleh struktur lain. Jika ada cukup banyak peserta dalam tim hackathon, hasil parsing awal dapat divisualisasikan selama hackathon sebagai tugas tambahan. Kira-kira dalam semangat ini, meskipun tidak begitu indah:
Jika tidak ada cukup banyak peserta selama hackathon, maka visualisasi grafik menengah, tidak diletakkan harus dibiarkan nanti, dan selama hackathon, hanya penempatan akhir harus ditampilkan di layar.
Secara umum, tugas parsing dapat diajukan dengan beberapa tingkat kompleksitas:
- Dalam kasus yang paling sederhana, semua node grafik adalah elemen logis dua-input AND dan OR, serta elemen-input tunggal TIDAK. Pada penempatan akhir, mereka direalisasikan oleh sel standar dengan lebar yang sama.
- Jika ada cukup waktu untuk hackathon, tugasnya bisa rumit:
- mengenalkan sel input tiga dan empat AND3, OR4, dll.
- perluas rangkaian jenis simpul dengan menambahkan NAND, XOR, D-flip-flop (D-Flip-Flop) dengan berbagai opsi (reset, aktifkan), dll.;
- membuat file teks tambahan untuk mengatur lebar dan parameter sel lainnya.
- Setelah hackathon, tugas dapat diikat ke dunia nyata, dan itu bukan parsing abstrak DAN dan ATAU yang diurai, tetapi file dalam format yang sama, tetapi dengan sel-sel dari perpustakaan nyata sel ASIC standar 28, 14 atau 7 nanometer, yang dipasok ke pengembang EDA dan perancang pabrik. tipe TSMC (Perusahaan Manufaktur Taiwan Semikonduktor).
Apa itu sel standar? Ini adalah sel tinggi standar untuk pustaka ASIC yang diberikan, yaitu pustaka primitif untuk membuat sirkuit mikro di pabrik menggunakan beberapa teknologi. ASIC - Sirkuit Terpadu Khusus Aplikasi. Sekarang kebanyakan chip, misalnya di smartphone, adalah ASIC. Sel-sel di pustaka ASIC memiliki tinggi standar sehingga mereka dapat dengan mudah diatur dalam baris untuk memasok daya kepada mereka dan memfasilitasi algoritma penelusuran. Sel-sel yang berbeda di perpustakaan dapat mengimplementasikan tidak hanya primitif seperti DAN dan OR, tetapi juga konstruksi yang lebih kompleks - multiplexer, kait, kombinasi dua atau tiga elemen logika (AND-OR), dll.
Sel-sel di
sirkuit mikro berbaris dalam baris (slide dari
kuliah Charles Danchek ):
Di antara baris ada saluran (saluran perutean) di mana koneksi lewat. Lebar saluran dapat diubah jika kemacetan terbentuk di koneksi. Di baris, Anda bisa membuat celah di antara sel:
Untuk hackathon, tugas dapat disederhanakan ke tingkat kuda bulat dalam ruang hampa:
- Batasi jenis sel. Sebagai permulaan, Anda biasanya dapat menempatkan hanya grafik dari dua input NAND.
- Pertimbangkan semua sel memiliki lebar yang sama.
- Abaikan semua aspek sifat fisik sel, termasuk penundaan sinyal dan konsumsi daya.
Di sini, "abaikan" berarti bahwa dalam latihan, Anda tidak dapat memperhitungkan fisika sel saat menilai kualitas penempatan dan penelusuran. Untuk memulainya, cukup hanya mempertimbangkan geometri, misalnya, untuk meminimalkan panjang total sambungan dan jumlah lapisan tempat sambungan dibuat. Kebutuhan akan lapisan baru muncul ketika tidak mungkin menempatkan dua konduktor tanpa melewatinya.
Di hackathon, cukup menganggap sel standar sebagai "kotak hitam" dan menampilkannya di layar seperti pada gambar di atas. Atau dengan gambar elemen logis, seperti pada slide dari
kuliah Igor Markov :
Meskipun jika Anda ditampilkan dengan bagian dalam sel, maka gambar lebih dekoratif. Slide dari
kuliah Charles Danchek :
Gambar lain dari internet dengan penempatan dan penelusuran + gambar bagian dalam sel:
Tetapi bagaimana cara menempatkan sel dalam baris, memperluas dan menyempit saluran di antara baris, membangun koneksi, memperkenalkan layer baru, mengevaluasi optimalitas hasil dan memilah-milah pilihan? Ya, ini murni tugas algoritmik dan pemrograman, di Innopolis mereka mungkin mengajarkan ini, karena itu saya tidak akan menyebarkan pemikiran atau pemikiran saya pada pohon. Sebagai inspirasi awal untuk penelusuran, Anda dapat menggunakan metode penelusuran gelombang kuno, yang dijelaskan
di bagian ketiga kursus untuk anak sekolah dari RUSNANO . Meskipun metode ini bukan untuk sel standar yang disusun dalam baris, tetapi untuk kasus yang kurang teratur dengan sejumlah kecil komponen:
2.10. Cara melakukannya: Algoritma penelusuran gelombang.
Salah satu algoritma klasik yang digunakan oleh program jejak awal adalah penelusuran gelombang, yang dijelaskan dalam artikel 1961 oleh Chester Lee, seorang peneliti di Bell Labs. Dalam bahasa Inggris, algoritma Lee disebut "maze routing," yang secara harfiah diterjemahkan sebagai "penelusuran labirin." Nama ini disebabkan oleh fakta bahwa selain program untuk mendesain elektronik, algoritma Lee digunakan dalam program game untuk menemukan jalur terpendek dalam labirin.
Algoritma Lee mewakili blok yang perlu dihubungkan, dalam bentuk angka pada bidang terbatas, yang ditandai "di dalam kotak". Untuk menemukan jalur terpendek dari output satu blok ke output blok lain, algoritma Lee menggunakan dua lintasan:
- Lulus pertama disebut propagasi gelombang. Kami menandai semua "sel" atau sel pada output pertama dengan unit. Setelah itu, untuk setiap sel yang berlabel angka N, kami menandai semua sel yang tidak berlabel bebas bersebelahan dengan angka N + 1. Ulangi markup tersebut hingga kami mencapai kesimpulan dari blok kedua atau tidak ada lagi kesempatan untuk menyebarkan "gelombang".
- Lintasan kedua disebut "pemulihan jalan." Jika sel di blok kedua ditandai, kami akan memilih di antara tetangganya sel yang ditandai 1 kurang dari jumlah di sel saat ini. Tambahkan sel tetangga ke jalan, masuk ke dalamnya dan mulai melihat tetangganya, yang ditandai 1 lebih sedikit. Kita ulangi ini sampai kita sampai pada kesimpulan dari blok pertama.
Pada awalnya, algoritma Lee digunakan dalam program untuk mendesain papan sirkuit cetak, kemudian mereka mulai menggunakannya untuk mendesain sirkuit mikro. Namun, ketika ukuran sirkuit mikro tumbuh, tidak mungkin untuk menerapkan algoritma Lee dalam bentuk aslinya, karena itu membutuhkan sejumlah besar memori untuk menyimpan array data, serta sejumlah besar waktu untuk banyak melewati array ini. Terlepas dari kenyataan bahwa program pelacakan otomatis modern menggunakan algoritma lain, algoritma Lee tetap menjadi latihan yang sangat baik bagi mereka yang baru saja menguasai pemrograman dan ingin menulis sendiri program pelacakan kecil.
Untuk algoritme yang lebih serius, Anda dapat mencari ide
di materi Igor Markov . Tetapi yang terbaik adalah berkreasi - bagaimana jika Anda menemukan sesuatu yang ribuan programmer algoritmik yang mengerti matematis belum menemukan kemacetan di jalan bebas hambatan 101, 880, dan 237 di jalan raya Synopsys dan Cadence setiap pagi di kota San Jose, Sunnyvale dan Mountain View, California.
Referensi (dari yang sederhana ke yang kompleks):
- Pengantar kuliah tentang dasar-dasar desain digital di Innopolis: 1 , 2 .
- Kursus pengantar elektronik digital dan EDA untuk anak sekolah lanjutan dari jenis olimpiade. Dari RUSNANO: 1 , 2 , 3 .
- Buku Teks Harris & Harris .
- Slide ceramah oleh Charles Danchek .
- Kursus oleh Igor Markov dari University of Michigan . Dia membaca kursus ini di Universitas Negeri Moskow.
Saya menyatakan harapan saya bahwa
inisiatif Innopolis dalam kompetisi algoritmik akan meluas. Area EDA secara matematis menarik dan dibayar dengan baik. Synopsys membuka cabang di Armenia dan menjadi salah satu perusahaan terkemuka di sana:
"Hari ini, Synopsys adalah salah satu perusahaan IT terbesar di Armenia dengan lebih dari 650 karyawan (termasuk lebih dari 600 insinyur)." Saya perhatikan bahwa Rusia lebih besar dari Armenia dan mungkin dapat membuat Sinopsisnya sendiri. Pada akhirnya, ada banyak programmer di Rusia, ahli matematika juga, dan kapitalisasi pasar saat ini Synopsys + Cadence kira-kira sama dengan biaya Olimpiade Sochi.