Saya mencoba untuk lebih memahami apa yang diperlukan untuk kompiler untuk dapat membuat pilihan cerdas tentang konkurensi atas nama programmer. Saya menyadari bahwa ada banyak aspek sulit dari masalah ini misalnya:
- Memastikan bahwa tidak ada kondisi balapan
Memastikan bahwa kode yang akan dijalankan secara bersamaan tidak akan memiliki efek samping yang berdampak pada makna semantik dari kode tersebut
Memutuskan apakah overhead dari pemintalan threads bermanfaat mengingat tingkat paralelisme yang tersedia dalam kode
Pemahaman saya adalah bahwa dua representasi perantara utama yang digunakan dalam kompiler modern adalah penugasan tunggal statis untuk bahasa berorientasi prosedural dan berorientasi objek dan kelanjutan lewat gaya untuk bahasa fungsional. Alasan tentang masalah apa pun yang tercantum di atas tampaknya sulit menggunakan bentuk peralihan ini. Bahkan bahasa yang seharusnya secara teori memiliki peluang terbaik pada paralelisasi otomatis (bahasa fungsional murni seperti Haskell dengan jaminan tidak ada efek samping) telah membuat kemajuan terbatas di bagian depan ini.
Jadi pertanyaan saya sebenarnya adalah representasi perantara apa yang telah digunakan untuk mencoba dan mengatasi masalah ini? Apakah ada representasi lain yang telah digunakan dalam penelitian akademik yang saya tidak sadari yang lebih cocok untuk tugas ini? Apakah masalah ini yang secara mendasar harus diselesaikan oleh ujung depan kompiler dengan memanipulasi pohon sintaksis abstrak sebelum kompilasi mencapai representasi perantara?
Jawaban:
Orang akan menganggap bahwa pemodelan konkurensi secara eksplisit dalam representasi perantara (IR) adalah persyaratan yang diperlukan. Jadi salah satu jawabannya adalah, "setiap IR yang digunakan untuk program berurutan dengan penambahan beberapa operasi konkurensi", misalnya, "bercabang dan bergabung", "paralel x y". Menambahkan ini memungkinkan untuk alasan tentang beberapa jenis konkurensi, tetapi tidak selalu mudah. Juga tidak jelas bagaimana memastikan properti tertentu (data-race freeness) tanpa pergi ke representasi yang berfungsi penuh (yang membuatnya sulit untuk memodelkan paralelisme dengan berguna).
Arguably Coloured Petri Nets (CPNs) adalah pilihan yang baik untuk mewakili program dengan konkurensi. (Token dalam CPN adalah "berwarna" [memiliki tipe] dan dapat membawa nilai; "transisi" ke negara dapat melakukan aritmatika sewenang-wenang pada token yang masuk untuk menghasilkan token yang mungkin berbeda warna dengan nilai yang dihitung di "tempat"). Jika Anda berpikir tentang tempat sebagai hasil yang dihitung dan transisi sebagai operator pemodelan (termasuk yang khusus untuk mengakses memori), ini memberi Anda berapa jumlah grafik aliran data yang digunakan untuk memodelkan program. Anda dapat dengan mudah menggunakan ini untuk memberikan interpretasi formal ke representasi kompiler klasik seperti tiga kali lipat [operator, input1, input2, output].
Ada banyak alat untuk menganalisis grafik CPN seperti itu, termasuk properti komputasi seperti kebuntuan-kebuntuan, batasan jumlah token di tempat, dll. CPN Heirarkis memungkinkan Anda memodelkan fungsi dan prosedur dan gagasan "panggilan".
Apa yang tidak jelas dilakukan oleh representasi ini, adalah memudahkan untuk mempertimbangkan di mana seseorang dapat memparalelkan suatu aplikasi. Sepele, dua subkomputasi dapat paralel jika efek sampingnya tidak ada operan bersama (itulah sebabnya beberapa orang menyukai program / representasi fungsional). Jika representasi program Anda memodelkan memori bersama, Anda dapat memodelkannya sebagai monolith dan mendapatkan serangkaian masalah yang biasa tentang alasan tentang interaksi pada memori bersama, termasuk pengalamatan alias, dll. Salah satu cara untuk menghindari ini adalah memperlakukan memori sebagai potongan terisolasi dengan status program yang lebih besar berupa kumpulan (seperti pohon) dari semuanya ini; Anda bisa meneruskan potongan ini di dalam representasi perantara Anda. Tidak ada interaksi antara dua komputasi paralel jika mereka tidak berbagi potongan (misalnya, subtree memori).
sumber