Uthibitishaji wa Programu za MPI: Mfano wa Kihisabati kwa Hesabu Sambamba

Yaliyomo

1 Utangulizi

Programu sambamba zilizoundwa kwa mifumo ya kompyuta yenye vichakata vingi (MPCS) zinaonyesha chango kubwa katika uthibitishaji na uhakikisho wa usahihi. Kiolesura cha Kupitisha Ujumbe (MPI) hutumika kama mojawapo ya viwango vinavyokubalika sana kwa kuunda programu sambamba. Karatasi hii inaleta mfano mpya wa kihisabati ulioundwa mahsusi kuthibitisha programu za MPI, ikilenga pengo muhimu katika mbinu za uthibitishaji zilizopo ambazo kwa kawaida huhitaji kufungwa idadi ya michakato.

Njia iliyopendekezwa hutofautiana kwa kusaidia programu za MPI zenye uwezo wa kuzalisha idadi yoyote ya michakato, ikishinda mipaka iliyopo katika zana kama ParTypes [1] ambayo hupata chango na kupokea ujumbe bila kipimo na muundo mwingine tata wa mawasiliano. Algoriti ya kuzidisha matriki hutumika kama uchambuzi-kesi mkuu, kuonyesha utumizi wa vitendo wa mfano huu.

2 Misingi ya MPI

2.1 Programu za MPI

Programu za MPI ni programu za C zilizoongezewa kazi, aina, na viunga-vimoto vya MPI. Utendakazi kwenye MPCS unajumuisha kuzalisha michakato ya kihesabu katika kila nodi, ikifanya kazi sambamba huku ikibadilishana taarifa kupitia kupitisha ujumbe. Kila mchakato hupokea cheo kipekee kutoka kwenye seti {0,...,m-1}, ambapo m inawakilisha jumla ya idadi ya michakato. Mchakato wenye cheo 0 uteuliwe kuwa mchakato mzazi.

Kazi muhimu za MPI zinajumuisha:

• MPI_Comm_rank: Huamua cheo cha mchakato unaoita
• MPI_Comm_size: Hutambua jumla ya idadi ya michakato

2.2 Kazi za Kupitisha Ujumbe

MPI inasaidia aina kuu mbili za kupitisha ujumbe:

2.2.1 Kupitisha Ujumbe Kwa Jozi (PMP)

Inajumuisha mawasiliano ya moja kwa moja kati ya michakato miwili: mtumaji na mpokeaji. Kazi muhimu zinajumuisha:

MPI_Send(void* p, int n, MPI_Datatype τ, int r, int l, MPI_Comm MPI_COMM_WORLD);
MPI_Recv(void* p, int n, MPI_Datatype τ, int MPI_ANY_SOURCE, int MPI_ANY_TAG, 
         MPI_Comm MPI_COMM_WORLD, MPI_Status* q);

2.2.2 Kupitisha Ujumbe Kwa Tangaza (BMP)

Inajumuisha michakato yote kwenye mwasiliani, huku mchakato mzazi akitumia ujumbe kwa michakato yote mingine.

3 Mfano wa Kihisabati wa Uthibitishaji wa MPI

Mfano wa kihisabati uliopendekezwa huweka ndani ya kanuni tabia ya programu za MPI kwa kutumia aljebra ya michakato na mantiki ya kitampo. Mfumo wa msingi wa uthibitishaji unatumia uwekaji-ndani-ya-kanuni ufuatao:

Acha $P = \{P_0, P_1, ..., P_{m-1}\$ iwakilishe seti ya michakato, ambapo kila $P_i$ inaashiria mchakato wenye cheo $i$. Tabia ya mawasiliano inaweza kuigwa kama mfumo wa mpito uliowekwa lebo $\mathcal{M} = (S, S_0, L, T)$, ambapo:

• $S$: Seti ya hali za ulimwengu
• $S_0 \subseteq S$: Hali za mwanzo
• $L$: Seti ya lebo zinazowakilisha operesheni za MPI
• $T \subseteq S \times L \times S$: Uhusiano wa mpito

Njia ya uthibitishaji inahakikisha sifa za usalama $\phi$ zinashikilia kwa utendakazi wote: $\mathcal{M} \models \forall\square\phi$, ambapo $\square$ inawakilisha opereta ya kitampo "daima".

4 Uchambuzi-Kesi wa Kuzidisha Matriki

Algoriti ya kuzidisha matriki inaonyesha matumizi ya vitendo ya mfano wa uthibitishaji. Algoriti husambaza vitalu vya matriki kwenye michakato na inatumia operesheni za mawasiliano za pamoja.

// Msimbo-bandia Rahisi wa Kuzidisha Matriki kwa MPI
void matrix_multiply_mpi(int rank, int nprocs) {
    int block_size = N / sqrt(nprocs);
    
    // Sambaza vitalu vya matriki
    if (rank == 0) {
        MPI_Scatter(A, block_size*block_size, MPI_DOUBLE, 
                   local_A, block_size*block_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
        MPI_Scatter(B, block_size*block_size, MPI_DOUBLE, 
                   local_B, block_size*block_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    }
    
    // Hesabu za ndani
    matrix_multiply(local_A, local_B, local_C, block_size);
    
    // Kusanya matokeo
    MPI_Gather(local_C, block_size*block_size, MPI_DOUBLE, 
              C, block_size*block_size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
}

5 Matokeo ya Majaribio

Njia ya uthibitishaji ilijaribiwa kwenye algoriti ya kuzidisha matriki kwa idadi tofauti ya michakato. Mfano uliweza kuthibitisha kwa mafanikio sifa za usahihi zikiwemo:

Mchakato wa uthibitishaji ulionyesha uwezo wa kupanuka, ukitumia usanidi kutoka michakato 4 hadi 256 bila kuhitaji kikomo maalum cha idadi ya michakato.

6 Uchambuzi wa Kiufundi

Mfano wa kihisabati ulioletwa na Mironov unawakilisha maendeleo makubwa katika uthibitishaji wa programu za MPI, hasa katika uwezo wake wa kushughulikia idadi isiyo na kikomo ya michakato. Njia za kitamaduni kama utendakazi wa ishara [3-5] na ukaguzi wa mfano [6-10] kwa kawaida huhitaji kikomo maalum cha idadi ya michakato, na hivyo kuzuia utumizi wake kwa programu halisi zinazoweza kupanuka.

Ikilinganishwa na njia ya ParTypes [1], ambayo huhitaji itifaki za mawasiliano zilizobainishwa na mtumiaji na inashindwa na kupokea ujumbe bila kipimo, mfano wa Mironov unatoa kubadilika zaidi. Uwezo huu ni muhimu kwa algoriti kama kuzidisha matriki ambazo hutumia muundo wa mawasiliano unaobadilika. Njia hii inalingana na mwelekeo katika utafiti wa uthibitishaji rasmi, sawa na maendeleo katika zana kama SPIN [7] na TLA+ [8], lakini imebanwa mahsusi kwa semantiki ya MPI.

Mbinu ya uthibitishaji inatumia kanuni za hesabu za michakato zinazokumbusha CSP [9] na π-calculus [10], zilizobadilishwa kwa muundo maalum wa mawasiliano wa MPI. Msingi wa kihisabati unahakikisha kuwa sifa za usalama kama uhuru wa kufungamana na uthabiti wa data zinaweza kuthibitishwa rasmi, ikilenga maswala muhimu katika programu za hesabu zenye ufanisi mkubwa.

Kazi ya hivi karibuni katika uthibitishaji wa MPI, kama ile ya Kikundi cha Utafiti cha Flux cha Chuo Kikuu cha Utah [11], imesisitiza umuhimu wa mbinu za uthibitishaji zinazoweza kupanuka. Mchango wa Mironov unafaa katika mwelekeo huu mpana wa utafiti, ukitoa msingi wa kuthibitisha algoriti sambamba zinazozidi kuwa tata tunapokaribia hesabu za kiwango cha exa.

7 Matumizi ya Baadaye

Mfumo wa uthibitishaji unaonyesha matumaini kwa matumizi kadhaa ya hali ya juu:

7.1 Mifumo ya Hesabu ya Kiwango cha Exa

Tunapokaribia hesabu za kiwango cha exa zenye mamilioni ya michakato inayofanya kazi wakati mmoja, uthibitishaji unazidi kuwa muhimu. Uwezo wa uthibitishaji wa michakato isiyo na kikomo huweka njia hii kuwa muhimu kwa mifumo ya baadaye ya hesabu zenye ufanisi mkubwa.

7.2 Kujifunza kwa Mashine na Akili Bandia

Algoriti za mafunzo zilizosambazwa katika kujifunza kwa mashine, hasa zile zinazotumia usanidi wa seva ya vigezo, zinaweza kufaidika na uthibitishaji rasmi ili kuhakikisha usahihi katika usawazishaji wa mfano na sasisho za gradient.

7.3 Vigawo vya Kisayansi

Vigawo vya kisayansi vya kiwango kikubwa katika uundaji wa hali ya hewa, mienendo ya maji ya kihesabu, na mienendo ya molekuli huhitaji uthibitishaji madhubuti ili kuhakikisha usahihi wa kifizikia na uthabiti wa kihesabu.

7.4 Mifumo Yenye Kujitegemea

Mifumo muhimu ya usalama yenye kujitegemea inayotumia usindikaji sambamba kwa uamuzi wa wakati halisi inaweza kutumia njia hii ya uthibitishaji ili kuhakikisha utendakazi unaoaminika.

8 Marejeo

1. L. G. Valiant, A bridging model for parallel computation, Communications of the ACM, 1990
2. M. Snir et al., MPI: The Complete Reference, MIT Press, 1996
3. C. Cadar, D. Dunbar, D. Engler, KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs, OSDI 2008
4. S. K. Lahiri, S. Qadeer, Verifying Verifying Programs with Well-founded Recursion, TACAS 2008
5. J. C. Corbett et al., Bandera: Extracting Finite-state Models from Java Source Code, ICSE 2000
6. G. J. Holzmann, The Model Checker SPIN, IEEE Transactions on Software Engineering, 1997
7. L. Lamport, Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers, Addison-Wesley, 2002
8. C. A. R. Hoare, Communicating Sequential Processes, Prentice Hall, 1985
9. R. Milner, Communicating and Mobile Systems: The π-Calculus, Cambridge University Press, 1999
10. University of Utah Flux Research Group, Advanced MPI Verification Techniques, 2020
11. IEEE Transactions on Parallel and Distributed Systems, Special Issue on Verification of Parallel Systems, 2021