Mengatur sel standar (catatan orang luar)

Setelah menemukan artikel " Menghancurkan monopoli ... ", penulis, sebagai pribadi, meskipun sangat jauh dari EDA , tetapi secara alami ingin tahu, tidak terlalu malas untuk mengikuti tautan dan tanpa sadar menangkap dirinya berpikir bahwa salah satu solusi teknis utama adalah penggunaan deretan sel standar ( sel standar) tata letak) - terlihat sangat kontroversial.

Ya, pengaturan ini intuitif, karena kami menulis dan membaca dengan cara yang serupa, di samping itu, secara teknologi sederhana untuk mengatur sel dalam baris, sangat mudah untuk menghubungkan bus VDD dan GND. Di sisi lain, masalah kombinatorial yang sulit muncul, perlu untuk memotong sirkuit menjadi potongan-potongan linier dan mengatur potongan-potongan ini sedemikian rupa untuk (secara kasar) meminimalkan total panjang sendi.

Dan tentu saja, muncul pertanyaan apakah ada solusi alternatif ... itu bagaimana jika ...


Gambar 1 baris khas sel standar ( dari sini )

Bagaimana jika

Dari sudut pandang pengurangan panjang ikatan total, akan berguna untuk mengatur sel-sel standar di sepanjang salah satu kurva ex sweeping : Peano atau Hilbert.

Kurva ini terdiri dari massa berbagai "sudut dan celah", pasti ada konfigurasi di mana sel standar yang terhubung rata-rata berdekatan satu sama lain.
Atau dapat berfungsi sebagai iterasi nol untuk pengoptimalan lebih lanjut.


Gambar 2 Kurva Hilbert, bidang 8X8 dan 64X64

1. Kurva yang menyapu mirip dengan diri sendiri, yang cocok dengan konsep keseluruhan.
2. Mereka memiliki lokalitas yang tinggi yaitu titik yang terletak di suatu tempat di dekat kurva kemungkinan besar berada di dekat dan di luar angkasa.
3. Berisi jaringan saluran yang terorganisir secara hierarkis.
4. Untuk rangkaian logis, Anda dapat memilih kuadrat atau persegi panjang yang cocok 1x2,2x1 di mana ia ditempatkan secara berlebihan dan "memindahkan" sepanjang kurva sapuan (lihat Gambar 3) untuk memilih geometri yang optimal, karena ini hanya satu derajat kebebasan dengan fungsi biaya yang agak murah .
   
5. Kenyamanan koneksi ban (VDD / GND) akan tetap ada.
6. ...

Gambar 3 Tiga buah kurva Hilbert dengan shift yang berbeda.

Jadi:

• kami akan bereksperimen dengan kurva Hilbert
• kami akan bereksperimen dalam kotak 64X64 (Gambar 3)
• pada langkah dasar kurva dapat ada beberapa sel dan ruang standar - berapa banyak tepatnya dan dalam urutan apa - parameter percobaan
• semua langkah dasar diatur secara identik
• langkah-langkah dasar berjalan dengan tumpang tindih yaitu jika langkah dimulai dengan sel standar, harus ada ruang di ujungnya, dan sebaliknya
• semua spasi dan sel standar berukuran sama - 1X1
• semua sel diserialisasi dalam urutan tertentu, urutan ini juga merupakan parameter
• satu parameter lagi adalah pergeseran dari awal kurva (titik (0,0)), mulai dari mana kita akan mengatur sel standar dalam urutan tertentu
  
• panjang ikatan antara sel standar dihitung menurut L1 (jarak Manhattan)
• jumlah panjang semua obligasi adalah nilai yang diinginkan, setelah menentukan jumlah minimum, kita akan menemukan lokasi yang optimal

Dan sebagai kelinci percobaan, mari kita ambil penambah 8-bit. Ini cukup sederhana, tetapi tidak sepele. Ada banyak elemen dan koneksi di dalamnya untuk merasakan potensi pro dan kontra. Pada saat yang sama, tidak ada cukup dari mereka untuk dapat bereksperimen "di lutut".

Penghancur

4 adalah diagram skematis dari penambah bit tunggal penuh


Gambar 5 Jadi lihat utilitas grafik ini Neato dari graphwiz


6 penambah yang ditandatangani 8-bit, diambil di sini

Tapi kami hanya akan bekerja dengan bilangan bulat, tanpa flag kesalahan W.


Gbr. 7 Jadi penambah 8-bit melihat utilitas titik graphwiz.

Itu terlihat seperti tarian angsa kecil.


Gambar. 8 adalah grafik yang sama setelah optimasi menggunakan neato.

Eksperimen 1

• langkah dasar dari kurva Hilbert - (pass, cell, cell, pass)
• simpul grafik (sel satuan) diurutkan berdasarkan abjad

Gbr.9 pada X - bergeser dari awal, pada Y - panjang semua jalur

Jarak minimum (yang pertama) pada pergeseran 207 (Total panjang semua ikatan adalah 1968), mari kita lihat seperti apa pengaturan optimal ini.


Gambar 10 adalah grafik optimal untuk shift 207, itu tidak terlihat sangat bagus.

Eksperimen 2

• langkah dasar dari kurva Hilbert - (pass, cell, cell, pass)
• simpul grafik (sel satuan) dalam urutan alami (seperti yang muncul dalam deskripsi grafik, lihat deskripsi grafik di atas) -

11 pada X - pergeseran dari awal, pada Y - panjang semua jalur


Gambar. 12 grafik optimal untuk geser 11 panjang 750

Eksperimen 3

• langkah dasar dari kurva Hilbert - (pass, cell, cell, pass)
• urutan simpul ditentukan dengan melintasi lebar grafik, simpul tanpa tautan di awal daftar, akhir pekan di akhir

Gbr.13 pada X - bergeser dari awal, pada Y - panjang semua jalur


Gbr. 14 Pengaturan optimal - shift 3, panjang total 1451
Letakkan semua simpul input di awal dan output di akhir tidak terlalu bagus
sebuah ide.

Eksperimen 4

• langkah dasar dari kurva Hilbert - (lulus, sel, sel) Sic!
• urutan vertex adalah alami, seperti dalam percobaan 2

Gbr.15 pada X - bergeser dari awal, pada Y - panjang semua jalur


Gbr. 16 Pengaturan optimal - shift 10, total panjang 503

Eksperimen 5

Kita perlu melakukan sesuatu dengan IO, kita mendefinisikannya di post-processing, yaitu untuk setiap shift
membangun susunan tanpa simpul IO, lalu buat kerangka tingkat absorben di sekitar grafik, terapkan simpul IO ke titik terdekat yang tidak diduduki bingkai dan hitung panjang akhir

• langkah dasar kurva Hilbert - (lewati, sel, sel)
• urutan simpul ditentukan dengan melihat lebar, tetapi tanpa simpul IO

Gbr.17 pada X adalah pergeseran dari awal, pada Y adalah panjang dari semua jalur


Gambar. 18 Lokasi optimal adalah pergeseran 607, panjang total 484, rata-rata 3,33793

Kelihatannya bagus, tetapi bagaimana jika kita mengoptimalkan bukan total panjang jalan, tetapi jumlahnya dengan luas persegi panjang yang diduduki. Dimensinya berbeda, jadi kami akan berasumsi bahwa kami menghitung bukan panjang lintasan, tetapi area di bawah lintasan.

Eksperimen 6

Parameternya sama seperti pada percobaan 5, kami mengoptimalkan area.


Gbr.19 pada X - bergeser dari awal, pada Y - panjang semua jalur


Gbr. 20 Pengaturan optimal - shift 966, panjang total 639, rata-rata 3,30345

Persegi panjang itu ternyata cukup panjang. Tetapi bagaimana jika kita menganggap bukan bidang persegi panjang, tetapi kuadrat dari sisi miring, mendorong kita ke bentuk yang lebih persegi?

Eksperimen 7

Parameternya sama seperti pada percobaan 5, kami mengoptimalkan kuadrat dari sisi miring.


Gbr.21 pada X adalah pergeseran dari awal, pada Y adalah panjang dari semua jalur


Gbr. 22 Pengaturan optimal - shift 70, panjang total 702, rata-rata 3,46207

Eksperimen 8

• langkah dasar dari kurva Hilbert - (sel, lewati) Sic!
• urutan simpul ditentukan dengan melihat lebar, tetapi tanpa simpul IO

Kami berasumsi bahwa biaya berjalan di Y adalah dua kali lipat dari pada X, ini lebih dekat dengan kenyataan.

Gbr.23 pada X adalah pergeseran dari awal, pada Y adalah panjang dari semua jalur


Gbr. 24 Pengaturan optimal - shift 344, total panjang 650, rata-rata 3,8

Kesimpulan

Pendahuluan "Pilihan Editor" - Eksperimen 6.

Akan menyenangkan untuk mengatur simpul IO, tetapi ini membutuhkan petunjuk dari samping,
di mana tepatnya (arah) kelas simpul ini harus ditempatkan.

Tapi pertama-tama saya ingin mendengar pendapat para ahli.

PS : terima kasih kepada YuriPanchul dan andy_p untuk kurangnya reaksi negatif refleks.

UPD (11/02/2019): menambahkan “percobaan 8”, di mana sel standar terletak di simpul kurva Hilbert, mis. ketat pada kisi persegi. Selain itu, di satu sisi, mereka digabungkan menjadi baris tradisional, dan di sisi lain, mereka berada di sepanjang kurva Hilbert.