Memisahkan langkah Baca / Komputasi / Tulis secara efisien untuk pemrosesan bersamaan entitas dalam sistem Entitas / Komponen

Mempersiapkan

Saya memiliki arsitektur entitas-komponen di mana Entitas dapat memiliki sekumpulan atribut (yang merupakan data murni tanpa perilaku) dan terdapat sistem yang menjalankan logika entitas yang bertindak atas data tersebut. Pada dasarnya, dalam kode yang agak pseudo:

Entity
{
    id;
    map<id_type, Attribute> attributes;
}

System
{
    update();
    vector<Entity> entities;
}

Suatu sistem yang hanya bergerak sepanjang semua entitas dengan laju yang konstan mungkin

MovementSystem extends System
{
   update()
   {
      for each entity in entities
        position = entity.attributes["position"];
        position += vec3(1,1,1);
   }
}

Pada dasarnya, saya mencoba memparalelkan pembaruan () seefisien mungkin. Ini dapat dilakukan dengan menjalankan seluruh sistem secara paralel, atau dengan memberikan setiap pembaruan () dari satu sistem beberapa komponen sehingga utas yang berbeda dapat menjalankan pembaruan dari sistem yang sama, tetapi untuk subset entitas yang berbeda yang terdaftar dengan sistem itu.

Masalah

Dalam kasus MotionSystem yang ditampilkan, paralelisasi adalah sepele. Karena entitas tidak saling bergantung, dan tidak mengubah data yang dibagikan, kami bisa memindahkan semua entitas secara paralel.

Namun, sistem ini kadang-kadang mengharuskan entitas berinteraksi (membaca / menulis data dari / ke) satu sama lain, kadang-kadang dalam sistem yang sama, tetapi sering antara sistem yang berbeda yang saling bergantung.

Sebagai contoh, dalam sistem fisika terkadang entitas dapat berinteraksi satu sama lain. Dua objek bertabrakan, posisi mereka, kecepatan dan atribut lainnya dibaca dari mereka, diperbarui, dan kemudian atribut yang diperbarui ditulis kembali ke kedua entitas.

Dan sebelum sistem rendering di engine dapat memulai rendering entitas, ia harus menunggu sistem lain untuk menyelesaikan eksekusi untuk memastikan bahwa semua atribut yang relevan adalah yang mereka butuhkan.

Jika kita mencoba untuk memaralelkan ini secara membabi buta, itu akan mengarah pada kondisi balapan klasik di mana sistem yang berbeda dapat membaca dan memodifikasi data pada saat yang sama.

Idealnya, akan ada solusi di mana semua sistem dapat membaca data dari entitas apa pun yang diinginkannya, tanpa harus khawatir tentang sistem lain yang memodifikasi data yang sama pada saat yang sama, dan tanpa memiliki programmer yang peduli dengan benar memesan eksekusi dan paralelisasi dari sistem ini secara manual (yang kadang-kadang bahkan tidak mungkin).

Dalam implementasi dasar, ini dapat dicapai dengan hanya menempatkan semua data membaca dan menulis di bagian-bagian penting (menjaganya dengan mutex). Tapi ini menginduksi sejumlah besar overhead runtime dan mungkin tidak cocok untuk aplikasi yang sensitif terhadap kinerja.

Larutan?

Dalam pemikiran saya, solusi yang mungkin adalah sistem di mana membaca / memperbarui dan menulis data dipisahkan, sehingga dalam satu fase mahal, sistem hanya membaca data dan menghitung apa yang mereka butuhkan untuk menghitung, entah bagaimana menyimpan hasil, dan kemudian menulis semua data yang diubah kembali ke entitas target dalam tulisan yang terpisah. Semua sistem akan bertindak pada data di negara bagian itu berada di awal frame, dan kemudian sebelum akhir frame, ketika semua sistem telah selesai memperbarui, pass tulisan serial terjadi di mana hasil cache dari semua yang berbeda sistem diulangi dan ditulis kembali ke entitas target.

Ini didasarkan pada (mungkin salah?) Gagasan bahwa kemenangan paralelisasi mudah bisa cukup besar untuk mengalahkan biaya (baik dalam hal kinerja runtime serta overhead kode) dari hasil caching dan pass penulisan.

Pertanyaan

Bagaimana sistem seperti itu diimplementasikan untuk mencapai kinerja yang optimal? Apa rincian implementasi sistem seperti itu dan apa prasyarat untuk sistem Entity-Component yang ingin menggunakan solusi ini?

----- (berdasarkan pertanyaan yang direvisi)

Poin pertama: karena Anda tidak menyebutkan profil runtime build versi Anda dan menemukan kebutuhan spesifik, saya sarankan Anda melakukannya secepat mungkin. Seperti apa profil Anda, apakah Anda meremukkan cache dengan tata letak memori yang buruk, adalah satu inti yang dipatok pada 100%, berapa banyak waktu relatif yang dihabiskan memproses ECS Anda dibandingkan dengan sisa mesin Anda, dll ...

Baca dari entitas dan hitung sesuatu ... dan pertahankan hasil di suatu tempat di area penyimpanan perantara hingga nanti? Saya tidak berpikir bahwa Anda dapat memisahkan read + compute + store dengan cara Anda berpikir dan mengharapkan toko perantara ini menjadi apa pun selain overhead murni.

Plus, karena Anda melakukan pemrosesan berkelanjutan, aturan utama yang ingin Anda ikuti adalah memiliki satu utas per inti CPU. Saya pikir Anda melihat ini pada lapisan yang salah , coba lihat seluruh sistem dan bukan entitas individu.

Buat grafik ketergantungan antara sistem Anda, bagan dari apa yang dibutuhkan sistem hasil dari pekerjaan sistem sebelumnya. Setelah Anda memiliki pohon dependensi maka Anda dapat dengan mudah mengirim seluruh sistem penuh entitas untuk diproses pada utas.

Jadi misalkan pohon ketergantungan Anda adalah tumpukan semak belukar dan beruang, masalah desain tapi kami harus bekerja dengan apa yang kami miliki. Kasus terbaik di sini adalah bahwa di dalam setiap sistem setiap entitas tidak bergantung pada hasil lain di dalam sistem itu. Di sini Anda dengan mudah membagi pemrosesan di seluruh utas, 0-99 dan 100-199 pada dua utas misalnya dengan dua inti dan 200 entitas yang dimiliki sistem ini.

Dalam kedua kasus, pada setiap tahap Anda harus menunggu hasil yang tergantung pada tahap selanjutnya. Tapi ini tidak apa-apa karena menunggu hasil dari sepuluh blok besar data yang sedang diproses dalam jumlah besar jauh lebih baik daripada menyinkronkan seribu kali untuk blok kecil.

Gagasan di balik pembuatan grafik dependensi adalah untuk menyepelekan tugas yang tampaknya mustahil yaitu "Menemukan dan merakit sistem lain untuk berjalan secara paralel" dengan mengotomatiskannya. Jika grafik seperti itu menunjukkan tanda-tanda diblokir oleh menunggu konstan untuk hasil sebelumnya maka membuat baca + modifikasi dan penulisan tertunda hanya memindahkan penyumbatan dan tidak menghilangkan sifat serial dari pemrosesan.

Dan pemrosesan serial hanya dapat dibalik paralel antara setiap titik urutan, tetapi tidak secara keseluruhan. Tetapi Anda menyadari ini karena itu adalah inti dari masalah Anda. Bahkan jika cache dibaca dari data yang belum ditulis, Anda masih harus menunggu cache itu tersedia.

Jika membuat arsitektur paralel itu mudah atau bahkan mungkin dengan kendala semacam ini maka ilmu komputer tidak akan berjuang dengan masalah sejak Bletchley Park.

Satu-satunya solusi nyata adalah dengan meminimalkan semua dependensi ini untuk membuat titik-titik sekuensial sesering mungkin diperlukan. Ini mungkin melibatkan pengelompokan sistem ke dalam langkah-langkah pemrosesan berurutan di mana, di dalam setiap subsistem, berjalan sejajar dengan benang menjadi sepele.

Terbaik yang saya dapat untuk masalah ini dan itu benar-benar tidak lebih dari merekomendasikan bahwa jika memukul kepala Anda di dinding bata sakit maka pecahkan menjadi dinding bata yang lebih kecil sehingga Anda hanya memukul tulang kering Anda.

Saya telah mendengar solusi menarik untuk masalah ini: Idenya adalah bahwa akan ada 2 salinan data entitas (boros, saya tahu). Satu salinan akan menjadi salinan saat ini, dan yang lainnya akan menjadi salinan sebelumnya. Salinan ini hanya ditulis, dan salinan yang lalu hanya dibaca dengan ketat. Saya berasumsi bahwa sistem tidak ingin menulis ke elemen data yang sama, tetapi jika itu tidak terjadi, sistem tersebut harus berada di utas yang sama. Setiap utas akan memiliki akses tulis ke salinan saat ini dari bagian data yang saling eksklusif, dan setiap utas memiliki akses baca ke semua salinan data yang lalu, dan dengan demikian dapat memperbarui salinan ini menggunakan data dari salinan sebelumnya tanpa mengunci. Di antara setiap bingkai, salinan saat ini menjadi salinan masa lalu, namun Anda ingin menangani pertukaran peran.

Metode ini juga menghilangkan kondisi balapan karena semua sistem akan bekerja dengan status basi yang tidak akan berubah sebelum / setelah sistem memprosesnya.

Saya tahu 3 desain perangkat lunak menangani pemrosesan data secara paralel:

1. Memproses data secara berurutan : Ini mungkin terdengar aneh karena kami ingin memproses data menggunakan beberapa utas. Namun, sebagian besar skenario membutuhkan beberapa utas agar pekerjaan dapat diselesaikan sementara utas lainnya menunggu atau melakukan operasi yang berjalan lama. Sebagian besar penggunaan adalah utas UI yang memperbarui antarmuka pengguna dalam satu utas, sedangkan utas lain dapat berjalan di latar belakang, tetapi tidak diizinkan untuk secara langsung mengakses elemen UI. Untuk melewati hasil dari utas latar belakang, antrian pekerjaan digunakan yang akan diproses oleh utas tunggal pada kesempatan yang masuk akal berikutnya.
2. Sinkronisasi akses data: ini adalah cara paling umum untuk menangani beberapa utas yang mengakses data yang sama. Sebagian besar bahasa pemrograman telah dibangun di kelas dan alat untuk mengunci bagian di mana data dibaca dan / atau ditulis oleh banyak utas secara bersamaan. Namun, harus berhati-hati untuk tidak memblokir operasi. Di sisi lain, pendekatan ini menghabiskan banyak biaya dalam aplikasi waktu nyata.
3. Tangani modifikasi bersamaan hanya ketika terjadi: pendekatan optimis ini dapat dilakukan jika tabrakan jarang terjadi. Data akan dibaca dan dimodifikasi jika tidak ada akses ganda sama sekali, tetapi ada mekanisme yang mendeteksi kapan data diperbarui secara bersamaan. Jika itu terjadi, perhitungan tunggal hanya akan dieksekusi lagi sampai sukses.

Berikut beberapa contoh untuk setiap pendekatan yang dapat digunakan dalam sistem entitas:

1. Mari kita pikirkan CollisionSystemyang membaca Positiondan RigidBodykomponen dan harus memperbarui Velocity. Alih-alih memanipulasi Velocitysecara langsung, CollisionSystemmalah akan menempatkan CollisionEventdalam antrian kerja dari sebuah EventSystem. Acara ini kemudian akan diproses secara berurutan dengan pembaruan lainnya ke Velocity.
2. Suatu EntitySystemmendefinisikan seperangkat komponen yang perlu dibaca dan ditulis. Untuk masing-masing Entityakan memperoleh kunci baca untuk setiap komponen yang ingin dibaca, dan kunci tulis untuk setiap komponen yang ingin diperbarui. Seperti ini, setiap orang EntitySystemakan dapat membaca komponen secara bersamaan saat operasi pembaruan disinkronkan.
3. Mengambil contoh dari MovementSystem, Positionkomponen tidak dapat diubah dan berisi nomor revisi . The MovementSystemsavely membaca Positiondan Velocitykomponen dan menghitung baru Position, incrementing membaca revisi jumlah dan mencoba memperbarui Positionkomponen. Dalam hal modifikasi bersamaan, kerangka kerja menunjukkan ini pada pembaruan dan Entityakan dimasukkan kembali dalam daftar entitas yang harus diperbarui oleh MovementSystem.

Bergantung pada sistem, entitas, dan interval pembaruan, setiap pendekatan mungkin baik atau buruk. Kerangka kerja sistem entitas memungkinkan pengguna untuk memilih di antara opsi-opsi itu untuk mengubah kinerja.

Saya harap saya dapat menambahkan beberapa ide ke dalam diskusi dan beri tahu saya jika ada berita tentangnya.