Get best of the week

Model komputasi paralel

1. Perkenalan. Korutinisme kompetitif


Artikel sebelumnya tentang topik pemrograman otomatis hanya "bunga". "Berry" dari pemrograman otomatis, mis. untuk apa yang perlu Anda lakukan, adalah model komputasi paralel berdasarkan model mesin negara. Jadi, mari kita pergi ...

Standar C ++ termasuk dukungan yang telah lama ditunggu-tunggu untuk multithreading [1]. Tetapi kami tidak akan mengaguminya atau mengkritik fakta ini, karena bekerja dengan utas terbebani oleh begitu banyak kondisi, peringatan, dan fitur yang tanpa contoh nyata yang mengungkapkan masalah multithreading, diskusi tentang pemrograman multithread tidak hanya akan tergesa-gesa, tetapi juga cukup bias. Oleh karena itu, selanjutnya terutama bukan tentang arus, tetapi tentang automata, mengingat, tentu saja, yang pertama.

Bahasa C ++ jauh dari yang pertama, dilengkapi dengan konstruksi paralelisme. Kembali pada 60-an abad terakhir, N. Wirth mengusulkan perpanjangan paralel dari bahasa ALGOL [2]. Namun, 60 tahun ke depan belum menjelaskan apa yang harus dianggap sebagai algoritma paralel dan apa yang harus menjadi model komputasi paralel. Rupanya, ekstensi yang terlambat dari bahasa C ++ juga terhubung dengan ini.

Baik konstruksi lama dari bahasa ALGOL, dan analog mereka yang lebih modern dalam bahasa C ++, hanyalah metode paralelisasi struktural yang tidak memperkenalkan model algoritmik paralel. Untuk membenarkan hal ini, dapat dikatakan bahwa upaya yang dilakukan selama masa lalu untuk membuat model perhitungan formal telah gagal. Cukuplah untuk mengatakan bahwa jaring Petri yang sama tidak membenarkan harapan tinggi yang diberikan pada mereka.

Akibatnya, "spiral" perkembangan paralelisme tampaknya telah kembali ke sumbernya, hanya mengalami "perkembangan terminologis". Mantan coroutine sepele tiba-tiba menjadi maju "coroutine" (menelusuri kertas dari coroutine Inggris), dan kebingungan dengan konsep paralel dan bersamaan di segmen bahasa Inggris pemrograman paralel kadang-kadang menyebabkan hal-hal paradoks. Misalnya, edisi pertama buku [1] berbeda dari edisi kedua dengan mengganti istilah "paralel" dengan "kompetitif" dan "multithreaded" dengan "paralel". Jadi pikirkan ini dalam situasi “siapa adalah siapa”.

2. Model perhitungan otomat paralel


Mungkin tidak ada yang akan membantah bahwa langkah kualitatif berikutnya dalam pengembangan pemrograman dihubungkan dengan transisi ke model komputasi paralel. Tetapi apakah ini akan terjadi sebagai akibat dari perkembangan evolusioner dari model komputasi yang ada atau apakah itu akan menjadi model yang secara fundamental berbeda adalah masalah yang masih dibahas. Dan jika para teoretikus masih berdebat, maka bagian programmer yang termotivasi secara praktis sudah menggunakan metode struktural untuk memparalelkan program.

Pemisahan tugas dan peningkatan produktivitas dianggap sebagai satu-satunya alasan untuk menggunakan konkurensi. Setidaknya, bagi mereka atau kombinasinya pada akhirnya mengurangi atau mencoba mengurangi semua yang lain [1]. Tetapi ada alasan yang jarang dibicarakan, tetapi karena itu umumnya bermanfaat untuk terlibat dalam pemrograman paralel. Memang, kecepatan dapat ditingkatkan dengan metode perangkat keras murni, dan pemisahan tugas dengan paralelisme terhubung dengan cara yang sama seperti pekerjaan sehari-hari karyawan bank dengan daftar tugas resmi mereka. Dan hanya algoritma paralel yang merupakan strategi yang memungkinkan kita untuk mengalahkan kompleksitas tugas dan meningkatkan keandalan program. Dan semua ini bertentangan dengan pendapat yang berlaku tentang pemrograman multi-threaded, yang mengubah setiap program paralel menjadi produk perangkat lunak yang kompleks dan tidak dapat diandalkan.

Suatu sistem paralel, yang terdiri dari banyak komponen paralel yang berfungsi dan secara aktif berinteraksi, objek, agen, dll., Mengimplementasikan suatu algoritma yang ditentukan dalam banyak hal bukan oleh algoritma dari masing-masing komponen (walaupun mereka, tentu saja), tetapi dengan jumlah komponen, jumlah dan jenis koneksi di antara mereka. Untuk mengendalikan kompleksitas ini dan memahami algoritma sistem paralel, Anda tidak hanya perlu model komputasi paralel, tetapi model yang, antara lain, dan bahkan di atas semua itu, memiliki teori yang tepat.

Tesis yang “sering merupakan program paralel lebih sulit untuk dipahami ..., dan, oleh karena itu, jumlah kesalahan meningkat,” secara sederhana, masih bisa diperdebatkan. Ya, algoritma program paralel bisa sangat sulit untuk dipahami, tetapi jika ada teori maka dapat "dihitung" secara formal menggunakan algoritma komponen. Dan dari sudut pandang mendesain, menerapkan dan memelihara komponen algoritma jauh lebih sederhana daripada algoritma sistem secara keseluruhan. Saat merancang komponen yang lebih sederhana, kami jelas akan membuat lebih sedikit kesalahan daripada mendesain sistem dalam satu bagian. Selain itu, komponen yang didebug dapat menjadi bagian dari sistem lain, mengurangi kompleksitas, meningkatkan keandalan dan meminimalkan biaya desain.

3. Konkurensi serial


Artikel [3] menggambarkan paralelisme dari model terpisah dari mesin keadaan terbatas. Salurannya di tingkat pelaksanaan transisi menentukan eksekusi paralel fungsi / metode yang terkait dengannya - predikat dan tindakan. Pada saat yang sama, tidak ada batasan pada predikat paralelisme. Ketika bekerja, mereka tidak saling bertentangan, karena tidak mempengaruhi isi memori. Tindakan, yang bekerja secara paralel, dapat memiliki input dan output data yang sama, serta mengubahnya secara independen satu sama lain. Dan semua ini bisa menjadi sumber ketidakpastian dalam nilai data output.

Pengoperasian tindakan yang benar dalam situasi yang dijelaskan di atas memberikan memori bayangan. Dengan menyimpan nilai-nilai baru di dalamnya, seseorang dapat menggunakan data yang sama bahkan dalam satu tindakan, baik sebagai input dan output. Contohnya adalah model generator pulsa persegi panjang, digambarkan sebagai y =! Y, di mana y adalah output dari generator. Kode C ++-nya di lingkungan VKPa ditunjukkan pada Listing 1, dan hasil program ditunjukkan pada Gambar. 1.

Daftar 1. Generator pulsa persegi panjang
#include "lfsaappl.h"

class FSWGenerator :
    public LFsaAppl
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FSWGenerator(pTAppCore, nameFsa, pCVarFsaLibrary); }
    bool FCreationOfLinksForVariables();
    FSWGenerator(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL);
    virtual ~FSWGenerator(void) {};
    CVar *pVarY;				//  
protected:
    void y1();
};

#include "stdafx.h"
#include "FSWGenerator.h"
// state machine transition table
static LArc TBL_SWGenerator[] = {
    LArc("s1",		"s1","--",	"y1"),			//
    LArc()
};

FSWGenerator::FSWGenerator(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
    LFsaAppl(TBL_SWGenerator, strNam, nullptr, pCVFL)
{
    pTAppCore = pInfo;
}
// creating local variables and initialization of pointers
bool FSWGenerator::FCreationOfLinksForVariables() {
// creating local variables
    pVarY = CreateLocVar("y", CLocVar::vtBool, " ");
    return true;
}
// setting output signals
void FSWGenerator::y1() {
    pVarY->SetDataSrc(nullptr, !bool(pVarY->GetDataSrc()));
}


gambar
Ara. 1. Simulasi pengoperasian generator pulsa persegi panjang di VKPA.

Dalam kasus ini, mesin memiliki satu keadaan dengan transisi tanpa syarat (transisi dengan tanda hubung di tempat kondisi input) dalam bentuk loop yang ditandai oleh aksi y1, yang mengimplementasikan inversi dari variabel output, yang membentuk pulsa persegi dalam dinamika. Dalam kerangka model otomat, frekuensi sinyal pulsa dapat dikontrol dengan menetapkan nilai kebijaksanaan waktu diskrit ruang otomat ke mana otomat dimuat.

1. , . . . .


Kemampuan untuk mengontrol waktu diskrit dari otomat dan keberadaan banyak ruang otomat bukan satu-satunya, tetapi penting, sifat khas dari lingkungan VKPa. Dengan menggunakannya, Anda dapat mengoptimalkan kinerja program paralel. Misalnya, mesin yang menerapkan visualisasi data dan dialog pengguna harus ditempatkan di ruang otomat lambat, dan proses aplikasi harus didistribusikan di antara ruang otomat sesuai dengan prioritas dan kecepatan yang diinginkan, dll. dll.

Dalam kerangka model otomat, nilai output generator mudah terkait dengan keadaan model saat ini. Kode untuk model generator, yang sudah memiliki dua status, yang masing-masing mencerminkan keadaan output generator, ditunjukkan pada Listing 2.

Listing 2. Generator gelombang persegi pada status
#include "lfsaappl.h"

extern LArc TBL_SWGenState[];
class FSWGenState :
    public LFsaAppl
{
public:
    FSWGenState(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
    LFsaAppl(TBL_SWGenState, strNam, nullptr, pCVFL) {};
};

#include "stdafx.h"
#include "FSWGenState.h"
// state machine transition table
LArc TBL_SWGenState[] = {
    LArc("s0",		"s1","--",	"--"),			//
    LArc("s1",		"s0","--",	"--"),			//
    LArc()
};


Dalam model baru, status menggantikan variabel output, dan ini, seperti dapat dilihat, secara dramatis menyederhanakan model generator. Akibatnya, kami mendapat mesin "telanjang", yang hanya diwakili oleh tabel konversi. Untuk memantau status saat ini "s1" di VKPa, variabel dari tipe fsa (status) dengan nama SWGenState. (S1) dibuat untuk mesin dengan nama SWGenState. Dibutuhkan nilai true dalam status s1, dan false ketika mesin dalam kondisi berbeda. Selanjutnya, variabel ini sudah digunakan dengan cara menampilkan data lingkungan VKPA (lihat tren sinyal pada Gambar. 2).

gambar
Ara. 2. Memodelkan generator keadaan

4. Model kontrol komputasi paralel


Lebih lanjut, bergerak menuju penciptaan model proses paralel, adalah logis untuk menggunakan banyak mesin negara yang berfungsi dan berinteraksi secara simultan, yaitu. jaringan automata. Dalam kasus ini, masalah memilih model waktu jaringan muncul, yang bisa sama untuk semua mesin atau, dalam batasnya, masing-masing untuk masing-masing. Dalam VKPa, pilihan dibuat untuk satu kali (untuk detail lebih lanjut tentang jaringan sinkron automata, lihat [5]).

Pilihan waktu tunggal memungkinkan Anda untuk membuat aljabar automata yang memiliki operasi komposisi dan penguraian automata. Menggunakan yang pertama, Anda dapat menemukan otomat yang dihasilkan, yang memberikan ide yang akurat tentang pengoperasian sistem paralel. Dan di sini ada baiknya mengingat tesis di atas tentang "kompleksitas pemahaman" dari program paralel. Kehadiran operasi komposisi memungkinkan kita untuk memecahkan "masalah pemahaman" dari program paralel.

Tentu saja, otomat yang dihasilkan untuk jaringan sejumlah besar komponen bisa sangat produktif. Tetapi, untungnya, pemahaman tentang operasi subsistem atau jaringan dari sejumlah kecil komponen lebih sering diperlukan, di mana menemukan otomat yang dihasilkan tidak menyebabkan masalah besar. Contoh model RS-flip-flop berikut menunjukkan ini.

Model pemicu RS adalah contoh sistem paralel sederhana. Ini sangat menarik dengan adanya umpan balik silang. Masukan, atau, dengan cara lain, rantai siklik, loop, loop aljabar, dll. saat ini merupakan masalah serius untuk model struktural sistem paralel. Dalam kasus umum, itu diizinkan dengan memasukkan ke dalam celah celah elemen memori. Ini adalah solusi standar yang diusulkan oleh teori automata [4]. Output yang sama direkomendasikan pada orang MATLAB. Lingkungan VKPa berbeda karena tidak memerlukan pengenalan elemen tambahan untuk implementasi loop. Catatan, dan ini sangat penting, sirkuit nyata juga tidak membutuhkannya (lihat sirkuit RS-flip-flop).

Dalam gbr. Gambar 3 menyajikan model paling sederhana dari elemen AND-NOT, yang terdiri dari rangkaian pemicu RS. Itu tidak memperhitungkan penundaan elemen akun, serta tipenya (keterlambatan transportasi atau inersia). Namun, itu masih mengandung setidaknya satu beat beat. Ini adalah waktu transisi dari satu negara ke negara lain. Listing 3 menunjukkan kode model

gambar
. 3. Model elemen DAN TIDAK

Daftar 3. Model elemen DAN TIDAK
#include "lfsaappl.h"

class FIne :
    public LFsaAppl
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FIne(pTAppCore, nameFsa, pCVarFsaLibrary); }
    bool FCreationOfLinksForVariables();
    FIne(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL);
    virtual ~FIne(void) {};
    CVar *pVarX1;				//  
    CVar *pVarX2;				//  
    CVar *pVarY;				//  
    CVar *pVarStrNameX1;		//    
    CVar *pVarStrNameX2;		//    
    CVar *pVarStrNameY;         //   
protected:
    int x1(); int x2(); int x12();
    void y1(); void y2(); void y12();
    bool bX1, bX2, bY;
};


#include "stdafx.h"
#include "FIne.h"
// state machine transition table
static LArc TBL_Ine[] = {
    LArc("st",		"st","^x12","y12"), 		//
    LArc("st",		"s1","x12^x1",	"y1"),		//
    LArc("st",		"s1","x12^x2",	"y1"),		//
    LArc("st",		"s0","x12x1x2",	"y2"),		//
    LArc("s1",		"s0","x1x2",   "y2"),		//
    LArc("s0",		"s1","^x1",    "y1"),		//
    LArc("s0",		"s1","^x2",    "y1"),		//
    LArc()
};

FIne::FIne(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
    LFsaAppl(TBL_Ine, strNam, nullptr, pCVFL)
{ }

// creating local variables and initialization of pointers
bool FIne::FCreationOfLinksForVariables() {
// creating local variables
    pVarX1 = CreateLocVar("x1", CLocVar::vtBool, " 1- ");
    pVarX2 = CreateLocVar("x2", CLocVar::vtBool, " 2- ");
    pVarY = CreateLocVar("y", CLocVar::vtBool, " ");
    pVarStrNameX1 = CreateLocVar("strNameX1", CLocVar::vtString, "name of external input variable(x1)");			//   
    pVarStrNameX2 = CreateLocVar("strNameX2", CLocVar::vtString, "name of external input variable(x2)");			//   
    pVarStrNameY = CreateLocVar("strNameY", CLocVar::vtString, "name of external output variable(y)");		//   
// initialization of pointers
    string str;
    if (pVarStrNameX1) {
        str = pVarStrNameX1->strGetDataSrc();
        if (str != "") { pVarX1 = pTAppCore->GetAddressVar(str.c_str(), this);	}
    }
    if (pVarStrNameX2) {
        str = pVarStrNameX2->strGetDataSrc();
        if (str != "") { pVarX2 = pTAppCore->GetAddressVar(str.c_str(), this); }
    }
    if (pVarStrNameY) {
        str = pVarStrNameY->strGetDataSrc();
        if (str != ""){pVarY = pTAppCore->GetAddressVar(str.c_str(), this);}
    }
    return true;
}

int FIne::x1() { return bool(pVarX1->GetDataSrc()); }
int FIne::x2() { return bool(pVarX2->GetDataSrc()); }
int FIne::x12() { return pVarX1 != nullptr && pVarX2 && pVarY; }

void FIne::y1() { pVarY->SetDataSrc(nullptr, 1); }
void FIne::y2() { pVarY->SetDataSrc(nullptr, 0.0); }
void FIne::y12() { FInit(); }


Dalam gbr. Gambar 4 memperlihatkan diagram flip-flop RS dan modelnya dalam bentuk mesin keadaan terbatas. Panah pada model menunjukkan koneksi antara automata jaringan. Di sini, di satu sisi, keadaan model mencerminkan keadaan keluaran elemen, dan, di sisi lain, mereka juga digunakan sebagai sinyal untuk mengatur hubungan informasi antara proses paralel. Bentuk model ini (dengan sinkronisasi melalui status) yang membuatnya cukup mudah untuk menemukan otomat yang dihasilkan dari jaringan. Itu ditunjukkan dalam gambar. 5 (untuk prosedur menemukan otomat yang dihasilkan, lihat [6] untuk lebih jelasnya).

Bandingkan algoritma [yang dihasilkan] dari program paralel RS-flip-flop dan algoritma operasi elemen AND-NOT yang terpisah. Perbedaannya mencolok. Dalam hal ini, algoritma komponen dibuat oleh "handle", dan algoritma sistem paralel dibuat secara implisit - oleh "kecerdasan buatan" dari jaringan. Ini adalah perbedaan kualitatif antara program paralel dan yang berurutan: mengubah hanya komunikasi (setidaknya satu), kita akan mendapatkan algoritma kerja yang sama sekali berbeda. Dan itu pasti tidak akan menjadi pemicu RS lagi. Dan, omong-omong, robot lain yang dihasilkan.

gambar
Ara. 4. Skema RS-FF dan model jaringan

gambar
Gambar. 5. Model jaringan mesin yang dihasilkan RS-trigger

Analisis otomat yang dihasilkan pada Gambar. 5 memberikan "pemahaman" berikut tentang program paralel (dan pemicu sebenarnya, tentu saja). Pertama, ketika beralih dari satu negara ke negara lain, pemicunya tentu akan melalui keadaan "terlarang" dari output (dan apa yang buku teks katakan tentang ini?). Kedua, jika pemicu didorong ke dalam satu keadaan keluaran (dalam keadaan "s1w1"), dan kemudian dua unit diumpankan ke input, itu akan memasuki mode pembangkitan, mis. pergantian siklik antara status “s1w1” dan “s0w0” dan (dan apakah Anda pernah mendengar tentang pemicu generasi?).

Transisi melalui keadaan terlarang juga terjadi pada pemicu nyata, tetapi mode pembuatan tidak mungkin karena perbedaan keterlambatan elemen nyata. Ara. Gambar 6 menunjukkan mode pembuatan model pemicu pemicu, yang ada selama unit pada input disimpan.

Catatan 2. Deskripsi khas operasi pemicu RS diberikan dalam sebagian besar kasus dalam bentuk tabel kebenaran. Tetapi untuk melakukannya, memahami bahwa pemicu adalah skema berurutan, itu, pada kenyataannya, sengaja menyesatkan mereka yang mempelajari topik ini. Yah, tidak ada pemicu yang tidak dapat memiliki "negara terlarang"! Tetapi untuk beberapa alasan hanya sedikit yang memutuskan untuk menemukan kebenaran ini dan, terutama, membahas masalah generasinya (lihat, misalnya, [7]).


Ara. Gambar 7 menunjukkan pergantian model pemicu antara kondisi stabilnya. Di sini, satu keadaan input pemicu mempertahankan keadaan saat ini dari output pemicu, dan ketika input ini atau itu diatur ke nol, ia beralih ke status berlawanan. Pada saat yang sama, ketika pelatuk diaktifkan, outputnya pada saat yang sama dengan satu ukuran terpisah pada saat yang sama mengambil status tunggal (dilarang oleh siapa?).

gambar
Ara. 6. Mode pembuatan RS-trigger

gambar
Gambar. 7. Mengganti RS-trigger antar state

Pertimbangkan model pemicu RS lainnya, yang terdiri dari satu keadaan dan satu tindakan, yaitu. mirip dengan model pada Listing 1. Kodenya ditunjukkan pada Listing 4. Model ini, seperti model generator, tidak memiliki predikat dan nilai sinyal tanpa transformasi menengah apa pun merupakan input untuk tindakan y1. Apakah ini baik atau buruk? Di satu sisi, sepertinya itu bagus, karena kode menjadi lebih sederhana, tetapi di sisi lain ... tidak juga. Dan kita akan mengerti alasannya sekarang.

Listing 4. Model elemen NAND dari satu tindakan
#include "lfsaappl.h"

class FTwoOperators :
    public LFsaAppl
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTwoOperators(pTAppCore, nameFsa, pCVarFsaLibrary); }
    bool FCreationOfLinksForVariables();
    FTwoOperators(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL);
    virtual ~FTwoOperators(void) {};
    CVar *pVarX1;				//  
    CVar *pVarX2;				//  
    CVar *pVarY;				//  
    CVar *pVarStrNameX1;		//    
    CVar *pVarStrNameX2;		//    
    CVar *pVarStrNameY;         //   
protected:
    int x12();
    void y1(); void y12();
    bool bX1, bX2, bY;
};

#include "stdafx.h"
#include "FTwoOperators.h"
// state machine transition table
static LArc TBL_TwoOperators[] = {
    LArc("st",		"st","^x12","y12"), 		//
    LArc("st",		"s1","x12", "--"),		//
    LArc("s1",		"s1","--",  "y1"),		//
    LArc()
};

FTwoOperators::FTwoOperators(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
    LFsaAppl(TBL_TwoOperators, strNam, nullptr, pCVFL)
{ }
// creating local variables and initialization of pointers
bool FTwoOperators::FCreationOfLinksForVariables() {
// creating local variables
    pVarX1 = CreateLocVar("x1", CLocVar::vtBool, " 1- ");
    pVarX2 = CreateLocVar("x2", CLocVar::vtBool, " 2- ");
    pVarY = CreateLocVar("y", CLocVar::vtBool, " ");
    pVarStrNameX1 = CreateLocVar("strNameX1", CLocVar::vtString, "name of external input variable(x1)");			//   
    pVarStrNameX2 = CreateLocVar("strNameX2", CLocVar::vtString, "name of external input variable(x2)");			//   
    pVarStrNameY = CreateLocVar("strNameY", CLocVar::vtString, "name of external output variable(y)");		//   
// initialization of pointers
    string str;
    if (pVarStrNameX1) {
        str = pVarStrNameX1->strGetDataSrc();
        if (str != "") { pVarX1 = pTAppCore->GetAddressVar(str.c_str(), this);	}
    }
    if (pVarStrNameX2) {
        str = pVarStrNameX2->strGetDataSrc();
        if (str != "") { pVarX2 = pTAppCore->GetAddressVar(str.c_str(), this); }
    }
    if (pVarStrNameY) {
        str = pVarStrNameY->strGetDataSrc();
        if (str != "") { pVarY = pTAppCore->GetAddressVar(str.c_str(), this);	}
    }
    return true;
}

int FTwoOperators::x12() { return pVarX1 != nullptr && pVarX2 && pVarY; }

void FTwoOperators::y1() {
// reading input signals
    bX1 = bool(pVarX1->GetDataSrc());
    bX2 = bool(pVarX2->GetDataSrc());
// setting output signals
    bY = !(bX1&&bX2);
    pVarY->SetDataSrc(nullptr, bY);
}
// initialization of pointers
void FTwoOperators::y12() { FInit(); }


Jika kita menguji model baru dalam mode "memori bayangan", maka kita tidak akan melihat perbedaan dalam operasinya dari yang sebelumnya, yaitu, dan, beralih, itu akan melalui negara terlarang dan secara teratur memasuki mode generasi. Jika kita mengatur pekerjaan dengan data dalam mode biasa, kita akan mendapatkan hasil yang ditunjukkan pada Gambar. 8 dan ara. 9.

gambar
Gambar. 8. Kegagalan mode pembuatan model pemicu RS

gambar
. 9. Melewati status terlarang oleh

model pemicu RS Mengapa model pertama, terlepas dari mode bekerja dengan memori, menunjukkan hasil yang stabil, dan yang kedua - mengubah perilaku? Alasannya adalah predikat. Model kedua tidak memiliki predikat, dan ini sangat penting untuk perilakunya. Tetapi bagaimana dan mengapa ada / tidaknya predikat mempengaruhi algoritma operasi program paralel?

Model program elemen AND-NOT, seperti program otomat, memiliki dua saluran input dan satu saluran output. Mereka harus mencocokkan dua predikat dan satu aksi. Program pertama sepenuhnya konsisten dengan ini. Kernel VKPa, yang menginterpretasikan deskripsi otomat, pertama-tama mengeksekusi semua predikat tidak hanya otomat tertentu, tetapi juga seluruh ruang otomat, dan baru kemudian memulai semua tindakan. Dalam hal ini, dalam urutan apa pun tindakan dijalankan, mensimulasikan paralelisme, dan dalam mode apa pun mereka bekerja dengan memori, hasil predikat pada siklus jam saat ini dari otomat tidak bergantung pada mereka (tindakan). Karena itu, program pertama menghasilkan hasil yang sama.

Program kedua, meskipun bekerja langsung dengan saluran input mesin, membaca sinyal input sebagai bagian dari tindakan. Tindakan, bekerja dengan input data dalam mode memori bayangan, menulis nilai baru ke memori bayangan dan dengan demikian bekerja dengan data yang valid pada awal siklus clock diskrit. Dalam mode biasa, mereka "mengambil" nilai-nilai instan yang ditetapkan pada saat perubahan mereka, dan dengan demikian algoritma menjadi tergantung pada saat-saat perubahan memori. Ketergantungan serupa ditunjukkan oleh program kedua. Dan bahkan jika metode predikat diperkenalkan ke dalam model kedua, ini tidak akan berpengaruh pada hasil kerjanya. Yang penting di sini bukan fakta keberadaan metode predikat, tetapi fitur pekerjaan mereka dalam kerangka model pemrograman otomat.

5. Kesimpulan


Menggunakan program paralel RS-trigger sebagai contoh, kami memeriksa beberapa properti yang melekat dalam program paralel mana pun. Kami akan terus mempertimbangkan aspek umum tertentu dari fungsi program paralel sebagai contoh sirkuit logis (digital). Pilihan topik pemodelan sirkuit digital di sini tidak disengaja. Bahkan, dalam "bentuk halus" mereka mewakili karya proses paralel. Ini membuat analisis nuansa konkurensi, ras, sinkronisasi, jalan buntu, dll. dll. transparan, jelas dan sederhana.

Pada saat yang sama, tidak peduli bagaimana Anda menyebut pemrograman - "kompetitif" atau paralel, apakah Anda menggunakan "coroutine", coroutine, utas atau mesin untuk pemrograman, hasil dari program [paralel] harus sama di semua implementasi. Model otomatis program paralel dalam kerangka CPSU mengejar ini dan hanya tujuan ini.
Apapun asumsi yang akan dibuat mengenai implementasi inti dari interpretasi automata lingkungan VKPa, semua ini akan menjadi "spekulasi", karena hasil kerja program otomatis tidak boleh dikaitkan dengan penerapan model komputasi. Ini bisa berupa perangkat lunak (seperti sekarang) atau perangkat keras (seperti yang saya harapkan di masa depan), diimplementasikan pada satu inti atau pada perangkat mereka, dalam versi single-threaded atau multi-threaded, dll. dll. semua ini tidak akan mempengaruhi hasil program otomatis paralel.

Dan, sepertinya, tujuannya tercapai. Model pemicu RS, sebagai salah satu tes yang mungkin dari sistem paralelisme [8], meyakinkan kami akan hal ini ... Seperti yang telah ditunjukkan kehidupan, semua program paralel lainnya, asalkan lingkungan telah berhasil melewati implementasi paralelisme uji pemicu RS, bekerja dengan benar, andal, dan stabil. . Omong-omong, MATLAB yang sama "RS-trigger test" tidak lulus, dan ini sudah mengatakan banyak ...

literatur
1. . ++ . . . . .. – .: , 2012. – 672 .
2. . : . . – .: , 1981. – 360 .
3. . [ ], : habr.com/ru/post/484588 . . . ( 07.01.2020).
4. .. . .: , 1962.
5. .., - .. . – 2- ., . . – .: , 1988. – 480 .
6. .. . [ ], : cloud.mail.ru/public/HwsK/T95PMM8Ed . . . ( 01.02.2020).
7. . . 2- . – .: , 2004. – 432.
8. .. ? “ ”, №10/97, .116-119. [ ], : www.osp.ru/pcworld/1997/10/158015 . . . ( 01.02.2020).

Source: https://habr.com/ru/post/undefined/

More articles:


All Articles