Get best of the week

NPS, conveyor, komputasi otomatis dan lagi ... coroutine

1. Lagi tentang coroutine


Dalam artikel saya sebelumnya, Habr sayang, saya hanya menyentuh pada masalah pengetahuan tentang pemrograman modern. Diskusi berikutnya hanya mengkonfirmasi ketakutan spontan yang muncul: "landasan teoretis" yang terkenal itu segera menjadi sumber pertentangan. Fakta bahwa mereka (ketidaksetujuan) mungkin tidak ada atau mereka akan memiliki sifat yang berbeda tampaknya tidak mengganggu sebagian besar programmer "nyata". Terlebih lagi, mungkin itu tidak terlalu menarik, karena pemrogram dirangsang terutama oleh satu minat - kode, kode, dan hanya kode. Yah, hampir "sesuai resep dokter" [1] ...

Menyinggung masalah corutin dalam artikel dan komentar saya, saya sama sekali tidak bermimpi tentang seberapa banyak mereka dalam tren "saat ini". Namun kagum dengan "backing track" dari komentar saya dengan atau tanpa. Untuk apa, kata mereka, programmer? Namun, bagi saya semuanya menjadi jelas setelah membaca artikel tentang C ++ 20 yang baru disetujui dan prospek untuk pengembangan lebih lanjut [2]. Yang mengejutkan saya, ternyata coroutine berada di garis depan dari inovasi C ++ saat ini dan masa depan (lihat juga perpustakaan CppCoro ).

Nah, katakan padaku, apakah mungkin untuk menganggap serius dan / atau dengan tenang alis yang, tampaknya, membayangkan dirinya sebagai orang lain? Hit apa yang disebut! :(

Latar belakang kenalan saya dengan coroutine (saya akan menyebutnya sama dengan cara lama) adalah sebagai berikut. Ada kebutuhan untuk memparalelkan, tetapi sesuatu yang cocok tidak. Saya harus menciptakan, mempelajari literatur yang tersedia. Akibatnya, coroutine ditolak segera, dan utas kemudian. Alasannya adalah bahwa keduanya adalah metode struktural dari program paralelisasi, dan bukan model komputasi. Tetapi saya tidak menginginkan itu.

Deskripsi tentang apa yang akhirnya saya ketahui diberikan dalam artikel saya sebelumnya tentang Habré. Pembicaraan ini masih jauh dari selesai, tetapi untuk sekarang, bagaimana koroutin diingat, karena mereka telah menjadi subjek diskusi yang begitu panas? Satu-satunya hal adalah "poin" dari proses berhenti / beralih. Tidak seperti utas, mereka memungkinkan untuk memprediksi perilaku proses yang mensimulasikan operasi paralel. Secara teori, ini juga mengurangi kerugian sistem untuk implementasi paralelisme. Tetapi, bagaimanapun, semua ini pada dasarnya tidak berubah. Dan karena "titik-titik" hanya ditiru oleh keadaan model pemrograman otomat (AP), kenalan saya dengan coroutine selesai selama tujuh.

Tetapi saya tidak dapat berasumsi bahwa inkarnasi coroutine, yang sekarang disebut coroutine, akan menyalip saya. Dari sini, dan saya, mungkin "serangan" yang tidak dapat dibenarkan atas mereka, yang untuk itu saya dengan tulus meminta maaf kepada para pembela Corutin. Mungkin terburu-buru. Namun demikian, keadaan yang baru ditemukan tidak mempengaruhi sikap saya terhadap coroutine. Untuk kode baru, untuk alasan yang menguntungkan mereka, saya tidak pernah melihat sesuatu yang pada dasarnya baru. Namun, saya ingin mencatat bahwa coroutine lebih dekat dan lebih jelas bagi saya daripada utas, karena mengandung, seperti yang saya katakan di atas, analog dari set keadaan internal hingga automata (CA).

Namun, berhentilah bertobat. Mari kita kembali ke automata yang sepenuhnya menutupi "tema coroutine". Selanjutnya, saya akan menyajikan kemampuan AP yang terkait dengan pemodelan model paralel yang cukup terkenal dalam teori dan praktik - model algoritma paralel dan pipeline berjenjang. Solusi otomatis mereka, menurut saya, terlihat lebih visual, alami dan sederhana daripada yang didasarkan pada coroutine yang sama.

2. Bentuk algoritma Tier-parallel dan pipeline


Misalkan Anda perlu menghitung ekspresi:

y = (((a + b) * (c + d)) + ((e * f) + (q + h)))).

Juga, biarkan waktu pelaksanaan operasi ditentukan, didefinisikan dalam unit acak waktu terpisah - langkah-langkah di mana penambahan mengambil 1 langkah, dan perkalian mengambil 5 langkah.
Berdasarkan logika penghitungan ekspresi, waktu pelaksanaan operasi, dan jumlah variabel perantara, dalam satu perwujudan, distribusi operasi dengan tingkatan dan jumlah tingkatan itu sendiri dapat terlihat, misalnya, sebagai berikut:

t1 = a + b; t2 = c + d; t3 = e * f; t4 = q + h;
Tingkat0: t1; t2; t3; t4;
Tingkat1: t5 = t1 * t2; t6 = t3 + t4;
Tier2: t7 = t5 + t6;

Secara grafis ini ditunjukkan dalam gambar. 1, yang menunjukkan dua opsi untuk distribusi kalkulasi dalam tingkatan dan waktu kalkulasi yang ditambahkan dalam kutu. Perbandingan mereka menunjukkan bahwa dalam kasus umum, penurunan jumlah tingkatan tidak secara otomatis berarti pengurangan waktu perhitungan.

gambar
Ara. 1. Bentuk paralel-paralel dari penghitungan ekspresi,

tetapi satu opsi lagi dapat dipertimbangkan, yang sudah diwakili oleh banyak bentuk paralel-tier yang memecahkan satu masalah. Dalam gbr. Gambar 2 menunjukkan solusi seperti itu. Waktu perhitungan telah berkurang. Paralelisasi NPS juga dapat menarik dengan mempertimbangkan pelaksanaannya pada sistem multiprosesor.

gambar
Ara. 2. NPS paralel

Jika Anda memutar grafik JPF, maka Anda bisa mendapatkan skema komputasi pipa. Di dalamnya, elemen-elemen conveyor akan menjadi tingkatan, yang waktu operasinya dikurangi menjadi tingkat paling lambat. Dalam gbr. Gambar 3 menunjukkan skema pipelining dari ekspresi asli.

gambar
Ara. 3. Model

saluran pipa Karena untuk contoh ini waktu konveyor diskrit adalah 5 siklus jam, waktu perhitungan akan lebih buruk daripada versi terburuk dari NPS. Keuntungan dari pipa hanya dalam kontinuitas perhitungan.

3. Model otomat untuk menghitung ekspresi


Jika Anda menghapus batasan pada sinkronisasi operasi, maka NPS dapat diubah menjadi sirkuit yang akan menghasilkan hasil sebagai saluran pipa, tetapi tanpa batasan terkait dengan urutan dan waktu operasi. Diagram jaringan logis seperti itu dengan demonstrasi operasi penjumlahan (implementasi multiplikasi serupa) dalam bentuk model jaringan pesawat ruang angkasa ditunjukkan pada Gambar. 4.

gambar
Gbr. 4. Perhitungan ekspresi berdasarkan pada jaringan mesin negara hingga

Anda dapat melihat bahwa jaringan akan terus-menerus menghasilkan hasil dengan penundaan 7 siklus clock, mis. serta model NPS tercepat (Gbr. 7). Kerugiannya termasuk ketidakstabilan keluaran yang terkait dengan ras data. Sebagai contoh, perubahan simultan dalam nilai variabel dalam pasangan variabel g, h dan e, f akan menyebabkan perubahan t4 pada siklus clock berikutnya, setelah satu siklus clock ke perubahan dalam variabel t6 dan siklus clock lain ke variabel output t7 (lihat Gambar. 1 dan Gambar. 4) . Pada saat yang sama, setelah 5 siklus clock, variabel t3 akan berubah, yang akan mengarah pada perubahan dan output dari nilai-nilai yang akhirnya ditetapkan dari variabel t6, t7.

gambar
Ara. 5. Pemodelan NPS dengan jaringan automata

Dalam gbr. Gambar 5 menunjukkan bagaimana pengenalan blok tambahan memungkinkan untuk mensimulasikan perhitungan NPS. Demikian pula, Anda dapat mensimulasikan model komputasi pipelined, serta memblokir perubahan dalam output yang terkait dengan ras data.

3. Kesimpulan


Akan aneh untuk meragukan bahwa "gambar" di atas tidak dapat diwujudkan dengan menggunakan coroutine. Jujur saja, saya tidak ingin melakukan ini. Bagi saya, jauh lebih mudah untuk membuat automata yang mengimplementasikan operasi yang diperlukan, dan kemudian, hanya mengubah jumlah mereka dan hubungan di antara mereka, menerapkan perhitungan ekspresi apa pun.

Saya tidak akan bosan mengulangi bahwa saya tertarik pada konsep pemrograman visual yang diimplementasikan dalam paket Stateflow di MATLAB. Di sini Anda juga dapat membuat operasi otomat yang diperlukan, dan kemudian, menggunakannya, seperti blok standar, "menggambar" skema perhitungan untuk ekspresi apa pun, yang setelah dikompilasi akan berubah menjadi program kerja (misalnya, dalam C ++ yang sama). Pada saat yang sama, selama proses desain, alat visualisasi dan debugging akan tersedia yang khusus untuk teknologi pemrograman otomatis.

Benar, pertanyaan mungkin muncul - mengapa tautan permanen ke lingkungan CPSU tertentu yang tidak diketahui, jika ada Stateflow? Tetapi kita akan membicarakan hal ini secara terpisah ...

Ini adalah hal yang tidak bersyukur untuk membuat prediksi, tetapi meskipun demikian, berdasarkan pengalaman saya, saya akan mengungkapkan pemikiran yang menghasut: karena bahasa tingkat tinggi digunakan untuk meniadakan pemrograman bahasa assembly, jadi pemrograman visual cepat atau lambat dan tidak mengurangi kerumitan pemrograman dalam bahasa tingkat tinggi.

Sastra

1. Programer, mari kita pelajari sumber program klasik. [Sumber daya elektronik], mode akses: habr.com/en/post/488808 gratis. Yaz. Rusia (tanggal perawatan 02.22.2020).
2. C ++ 20 disetujui! Apa yang diharapkan dan apa yang harus disiapkan untuk pengembang C ++ 23. [Sumber daya elektronik], mode akses:habr.com/en/company/yandex/blog/488588 gratis. Yaz. Rusia (tanggal perawatan 02.20.2020).

More articles:


All Articles