Det skjedde slik at jeg måtte forholde meg tett til studiet av parallell databehandling og spesielt MPI. Kanskje denne retningen for i dag er veldig lovende, så jeg vil gjerne vise habraybrukerne det grunnleggende om denne prosessen.

Grunnleggende prinsipper og eksempel

Beregningen av eksponenten (e) vil bli brukt som eksempel. Et av alternativene for å finne den er Taylor-serien:
e ^ x = ∑ ((x ^ n) / n!), hvor summeringen skjer fra n = 0 til uendelig.

Denne formelen kan lett parallelliseres, siden det nødvendige antallet er summen av individuelle ledd, og på grunn av dette kan hver enkelt prosessor beregne de individuelle leddene.

Antall termer som vil bli beregnet i hver enkelt prosessor avhenger både av lengden på intervallet n og av tilgjengelig antall prosessorer k som kan delta i beregningsprosessen. Så, for eksempel, hvis lengden på intervallet er n = 4, og fem prosessorer (k = 5) er involvert i beregningene, vil fra den første til den fjerde prosessoren motta en term, og den femte vil ikke være involvert . Hvis n = 10, og k = 5, vil hver prosessor få to ledd å beregne.

Til å begynne med bruker den første prosessoren kringkastingsfunksjonen MPI_Bcast for å sende de andre verdien til den brukerspesifiserte variabelen n. Generelt har MPI_Bcast-funksjonen følgende format:
int MPI_Bcast (void * buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm), der buffer er adressen til bufferen med elementet, count er antall elementer, datatype er den tilsvarende datatypen i MPI, root er rangeringen av hovedprosessorforsendelsen, og comm er navnet på kommunikatoren.
I mitt tilfelle, som allerede nevnt, vil den første prosessoren med rangering 0 fungere som hovedprosessor.

Etter det vil tallet n bli sendt, hver prosessor vil begynne å beregne betingelsene. For dette, ved hvert trinn i sløyfen, vil tallet i, som i utgangspunktet er lik prosessorens rangering, suppleres med et tall som er lik antallet prosessorer som deltar i beregningene. Hvis tallet i de følgende trinnene overskrider tallet n spesifisert av brukeren, vil løkkekjøringen for denne prosessoren stoppe.

Under utførelsen av syklusen vil vilkårene bli lagt til en separat variabel, og etter fullføringen vil den resulterende summen bli sendt til hovedprosessoren. For dette vil MPI_Reduce-funksjonen til cast-operasjonen bli brukt. Generelt ser det slik ut:
int MPI_Reduce (void * buf, void * resultat, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)

Den kobler sammen elementene i inngangsbufferen til hver prosess i gruppen ved å bruke operasjonsoperasjonen, og returnerer den sammenkoblede verdien til utgangsbufferen til den prosessnummererte roten. Resultatet av en slik operasjon vil være en enkelt verdi, og det er grunnen til at cast-funksjonen har fått navnet sitt.

Etter å ha kjørt programmet på alle prosessorer, vil den første prosessoren motta den totale summen av leddene, som vil være eksponentverdien vi trenger.

Det skal bemerkes at både i parallelle og sekvensielle metoder for å beregne eksponenten, brukes en rekursiv funksjon for å finne faktoren. I løpet av å ta en beslutning om metoden for å parallellisere den utførte oppgaven, vurderte jeg muligheten for å finne faktorial også på forskjellige prosessorer, men til slutt ble dette alternativet adoptert av meg som irrasjonelt.

Den primære oppgaven er fortsatt å finne verdien av eksponenten, og hvis prosessorene begynner å beregne hver faktorial av hvert ledd separat, kan dette føre til motsatt effekt, nemlig et betydelig tap i ytelse og beregningshastighet.
Dette forklares med det faktum at i dette tilfellet vil en veldig stor belastning på kommunikasjonsmiljøet begynne, som allerede ofte er et svakt ledd i parallelle datasystemer. Hvis beregningen av faktoren foregår på hver prosessor på en privat måte, vil belastningen på kommunikasjonslinjene være minimal. Denne saken kan kalles et godt eksempel på at parallelliseringsproblemet også noen ganger må ha sine grenser.

Algoritme for kjøring av kode

1. Verdien av tallet n overføres fra det visuelle skallet til programmet, som deretter sendes til alle prosessorer ved hjelp av kringkastingsfunksjonen.
2. Når den første hovedprosessoren er initialisert, startes en timer.
3. Hver prosessor utfører en syklus, hvor inkrementet er antall prosessorer i systemet. I hver iterasjon av løkken beregnes en term og summen av slike termer lagres i variabelen drobSum.
4. Etter slutten av loopen legger hver prosessor sin drobSum-verdi til resultatvariabelen ved å bruke MPI_Reduce cast-funksjonen.
5. Etter å ha fullført beregninger på alle prosessorer, stopper den første hovedprosessoren timeren og sender den resulterende verdien av resultatvariabelen til utgangsstrømmen.
6. Tidsverdien målt av timeren vår i millisekunder sendes også til utgangsstrømmen.

Kodeoppføring

Programmet er skrevet i C ++, vi vil anta at argumentene for utførelse sendes fra det ytre skallet. Koden ser slik ut:

#inkludere "mpi.h"
#inkludere
#inkludere
bruker navneområde std;

dobbelt faktum (int n)
{
hvis (n == 0)
retur 1;
ellers
return n * Fakta (n-1);
}

int main (int argc, char * argv)
{
SetConsoleOutputCP (1251);
int n;
int myid;
int numprocs;
int i;
int rc;
lang dobbel drob, drobSum = 0, Resultat, sum;
dobbel startwtime = 0,0;
dobbel endwtime;

N = atoi (argv);

if (rc = MPI_Init (& argc, & argv))
{
cout<< "Oppstartsfeil, utførelse stoppet" << endl;
MPI_Abort (MPI_COMM_WORLD, rc);
}

MPI_Comm_size (MPI_COMM_WORLD, & numprocs);
MPI_Comm_rank (MPI_COMM_WORLD, & myid);

if (myid == 0)
{

Startwtime = MPI_Wtime ();
}
MPI_Bcast (& n, 1, MPI_INT, 0, MPI_COMM_WORLD);

for (i = myid; i<= n; i += numprocs)
{
dråpe = 1 / Fakta (i);
drobSum + = drob;
}

MPI_Reduce (& drobSum, & Result, 1, MPI_LONG_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
cout.presisjon (20);
if (myid == 0)
{
cout<< Result << endl;
endwtime = MPI_Wtime ();
cout<< (endwtime-startwtime)*1000 << endl;
}

MPI_Finalize ();
returner 0;
}

* Denne kildekoden ble uthevet med Source Code Highlighter.

Produksjon

Dermed fikk vi et enkelt program for å beregne eksponenten ved hjelp av flere prosessorer samtidig. Sannsynligvis er flaskehalsen lagringen av selve resultatet, for med økningen i antall sifre vil det ikke være trivielt å inneholde verdien ved hjelp av standardtyper, og dette stedet krever utdypning. Kanskje en ganske rasjonell løsning er å skrive resultatet til en fil, selv om du ikke kan fokusere på dette spesielt i lys av den rene pedagogiske funksjonen til dette eksemplet.

Merknad: Forelesningen er viet betraktningen av MPI-teknologi som en parallell programmeringsstandard for distribuerte minnesystemer. De viktigste modusene for dataoverføring vurderes. Begreper som prosessgrupper og kommunikatører introduseres. Grunnleggende datatyper, punkt-til-punkt operasjoner, kollektive operasjoner, synkronisering og tidsmålingsoperasjoner er dekket.

Hensikten med foredraget: Forelesningen tar sikte på å studere generell metodikk for utvikling av parallelle algoritmer.

Videoopptak av forelesningen - (volum - 134 MB).

5.1. MPI: grunnleggende begreper og definisjoner

La oss vurdere en rekke konsepter og definisjoner som er grunnleggende for MPI-standarden.

5.1.1. Parallelt programkonsept

Under parallelt program innenfor rammen av MPI, et sett med samtidig utført prosesser... Prosesser kan utføres på forskjellige prosessorer, men flere prosesser kan være plassert på samme prosessor (i dette tilfellet utføres deres utførelse i en tidsdelingsmodus). I det ekstreme tilfellet kan én prosessor brukes til å utføre et parallelt program - som regel brukes denne metoden til å innledningsvis kontrollere riktigheten til et parallellprogram.

Hver prosess i et parallelt program genereres basert på en kopi av den samme programkoden ( SPMP-modell). Denne programkoden, presentert i form av et kjørbart program, må være tilgjengelig på tidspunktet for lansering av et parallellprogram på alle prosessorer som brukes. Kildeprogramkoden for det kjørbare programmet er utviklet i algoritmiske språk C eller Fortran ved å bruke en eller annen implementering av MPI-biblioteket.

Antall prosesser og antall prosessorer som brukes bestemmes i det øyeblikket et parallelt program startes ved hjelp av utførelsesmiljøet til MPI-programmer og kan ikke endres i løpet av beregninger (MPI-2-standarden gir mulighet for dynamisk endring antall prosesser). Alle prosesser i programmet er sekvensielt nummerert fra 0 til p-1, hvor s det er et totalt antall prosesser. Prosessnummeret er navngitt rang prosess.

5.1.2. Dataoverføringsoperasjoner

MPI er basert på meldingsoverføringsoperasjoner. Blant funksjonene som tilbys i MPI er forskjellige paret (punkt til punkt) operasjoner mellom to prosesser og kollektiv (kollektiv) kommunikasjonshandlinger for samtidig interaksjon av flere prosesser.

For å utføre parede operasjoner kan forskjellige overføringsmoduser brukes, inkludert synkron, blokkering osv. - en full vurdering av ev. overføringsmoduser vil bli utført i underkapittel 5.3.

Som nevnt tidligere, gir MPI-standarden behovet for å implementere de fleste grunnleggende kollektive dataoverføringsoperasjoner - se underavsnitt 5.2 og 5.4.

5.1.3. Konseptet med kommunikatører

Prosessene til det parallelle programmet kombineres til gruppe... Under kommunikator MPI betyr et spesiallaget tjenesteobjekt som kombinerer en gruppe prosesser og en rekke tilleggsparametere ( kontekst) brukes når du utfører dataoverføringsoperasjoner.

Som regel utføres parede dataoverføringsoperasjoner for prosesser som tilhører samme kommunikator. Kollektive operasjoner brukes samtidig på alle kommunikasjonsprosesser. Som et resultat er indikasjonen av kommunikatoren som brukes, obligatorisk for dataoverføringsoperasjoner i MPI.

Beregninger kan opprette nye og slette eksisterende prosessgrupper og kommunikatører. Den samme prosessen kan tilhøre ulike grupper og kommunikatører. Alle prosesser i det parallelle programmet er en del av kommunikatoren som er opprettet som standard med MPI_COMM_WORLD-identifikatoren.

Hvis det er nødvendig å overføre data mellom prosesser fra forskjellige grupper, er det nødvendig å lage en global kommunikator ( kommunikator).

En detaljert vurdering av MPIs evner til å arbeide med grupper og kommunikatører vil bli utført i underkapittel 5.6.

5.1.4. Datatyper

Når du utfører meldingsoverføringsoperasjoner, for å indikere de overførte eller mottatte dataene i MPI-funksjonene, er det nødvendig å spesifisere type sendte data. MPI inneholder et stort sett grunnleggende typer data som i stor grad sammenfaller med datatypene i algoritmespråkene C og Fortran. I tillegg har MPI muligheten til å lage nye avledede typer data for en mer nøyaktig og kortfattet beskrivelse av innholdet i de videresendte meldingene.

En detaljert diskusjon av MPIs muligheter for å arbeide med avledede datatyper vil bli utført i avsnitt 5.5.

5.1.5. Virtuelle topologier

Som nevnt tidligere, kan parede dataoverføringsoperasjoner utføres mellom alle prosesser til samme kommunikator, og alle prosesser til kommunikatoren deltar i den kollektive operasjonen. I denne forbindelse har den logiske topologien til kommunikasjonslinjer mellom prosesser strukturen til en komplett graf (uavhengig av tilstedeværelsen av ekte fysiske kommunikasjonskanaler mellom prosessorene).

Samtidig (og dette ble allerede bemerket i avsnitt 3), for presentasjon og påfølgende analyse av en rekke parallelle algoritmer, er det tilrådelig å logisk representere det eksisterende kommunikasjonsnettverket i form av visse topologier.

MPI har evnen til å representere en rekke prosesser i skjemaet gitter vilkårlig dimensjon (se underkapittel 5.7). I dette tilfellet kan grenseprosessene til gitterne erklæres tilstøtende og dermed, basert på gitterne, strukturer av typen torus.

Dessuten har MPI også fasiliteter for å danne logiske (virtuelle) topologier av enhver nødvendig type. En detaljert vurdering av MPIs evner for å jobbe med topologier vil bli utført i avsnitt 5.7.

Og til slutt, et siste sett med bemerkninger før du begynner å vurdere MPI:

• Beskrivelse av funksjoner og alle eksempler på programmer gitt vil bli presentert på algoritmespråket C; spesifikasjonene for bruk av MPI for Fortran algoritmiske språk vil bli gitt i avsnitt 5.8.1,
• En kort beskrivelse av de tilgjengelige implementeringene av MPI-bibliotekene og en generell beskrivelse av utførelsesmiljøet for MPI-programmer vil bli vurdert i klausul 5.8.2,
• Hovedpresentasjonen av MPI-funksjoner vil være fokusert på versjon 1.2-standarden ( MPI-1); tilleggsfunksjoner i 2.0-standarden vil bli presentert i 5.8.3.

Når du begynner å studere MPI, kan det bemerkes at MPI på den ene siden er ganske komplisert - MPI-standarden sørger for tilstedeværelsen av mer enn 125 funksjoner. På den annen side er MPI-strukturen gjennomtenkt – utviklingen av parallelle programmer kan startes etter å ha vurdert kun 6 MPI-funksjoner. Alle tilleggsfunksjonene til MPI kan mestres etter hvert som kompleksiteten til de utviklede algoritmene og programmene vokser. Oppkalt i denne stilen - fra enkel til kompleks - og vil videre presentere alt opplæringsmaterialet på MPI.

5.2. Introduksjon til parallell programutvikling ved bruk av MPI

5.2.1. Grunnleggende om MPI

Her er det minste nødvendige settet med MPI-funksjoner, tilstrekkelig for utvikling av ganske enkle parallelle programmer.

5.2.1.1 Initialisering og avslutning av MPI-programmer

Den første funksjonen å ringe MPI skal være en funksjon:

int MPI_Init (int * agrc, char *** argv);

for å initialisere MPI-programmets kjøretid. Funksjonsparametrene er antall argumenter på kommandolinjen og teksten til selve kommandolinjen.

Siste funksjon kalt MPI må være en funksjon:

int MPI_Finalize (ugyldig);

Som et resultat kan det bemerkes at strukturen til et parallelt program utviklet ved hjelp av MPI bør være som følger:

#include "mpi.h" int main (int argc, char * argv) (<программный код без использования MPI функций>MPI_Init (& agrc, & argv);<программный код с использованием MPI функций>MPI_Finalize ();<программный код без использования MPI функций>returner 0; )

Det bør merkes:

1. Fil mpi.h inneholder definisjoner av navngitte konstanter, funksjonsprototyper og datatyper for MPI-biblioteket,
2. Funksjoner MPI_Init og MPI_Finalize er obligatoriske og må utføres (og bare én gang) av hver prosess i det parallelle programmet,
3. Før du ringer MPI_Init funksjonen kan brukes MPI_Initialisert for å finne ut om et anrop har blitt foretatt tidligere MPI_Init.

Eksemplene på funksjoner diskutert ovenfor gir en ide om syntaksen for å navngi funksjoner i MPI. Funksjonsnavnet innledes med MPI-prefikset, etterfulgt av ett eller flere ord i navnet, det første ordet i funksjonsnavnet begynner med en stor bokstav, ordene er atskilt med en understrek. Navnene på MPI-funksjoner forklarer som regel formålet med handlingene som utføres av funksjonen.

Det bør merkes:

• Kommunikator MPI_COMM_WORLD, som nevnt tidligere, opprettes som standard og representerer alle prosesser i det parallelle programmet som kjøres,
• Rangeringen oppnådd ved hjelp av funksjonen MPI_Comm_rank, er rangeringen av prosessen som gjorde kallet til denne funksjonen, dvs. variabel ProcRank vil anta ulike verdier i ulike prosesser.

Hovedfunksjonene til MPI

Den vanligste programmeringsteknologien for parallelldistribuerte minnesystemer er for tiden MPI (Message Passing Interface). Hovedmåten parallelle prosesser samhandler med hverandre i slike systemer er Message Passing. I hovedsak er MPI et bibliotek og kjøretid for parallelle programmer i C eller Fortran. Denne opplæringen vil beskrive eksempler på C-programmer.

I utgangspunktet tillater MPI bruk av MIMD-programmeringsmodellen (Multiple Instruction Multiple Data) - mange strømmer av instruksjoner og data, dvs. kombinere ulike programmer med ulike data. Men programmering for en slik modell viser seg å være for komplisert i praksis, så SIMD-modellen (Single Program Multiple Data) brukes vanligvis – ett program og mange datastrømmer. Her er et parallelt program skrevet slik at ulike deler av det samtidig kan utføre sin del av oppgaven, dermed oppnås parallellitet. Siden alle MPI-funksjoner finnes i biblioteket, vil det være nødvendig å koble sammen de tilsvarende modulene ved kompilering av et parallelt program.

I rammeverket til MPI forstås et parallelt program som et sett med prosesser som utføres samtidig. Prosesser kan utføres på forskjellige prosessorer, men flere prosesser kan være plassert på samme prosessor (i dette tilfellet utføres deres utførelse i en tidsdelingsmodus). Når et MPI-program startes på en klynge, vil hver av nodene utføre sin egen kopi av programmet, utføre sin egen del av oppgaven, det følger av dette at et parallelt program er et sett med interagerende prosesser, som hver fungerer i sitt eget adresseområde. I det ekstreme tilfellet kan én prosessor brukes til å utføre et parallelt program - som regel brukes denne metoden til å innledningsvis kontrollere riktigheten til et parallellprogram.

Antall prosesser og antall prosessorer som brukes bestemmes på tidspunktet for lansering av et parallelt program ved hjelp av utførelsesmiljøet til MPI-programmer og kan ikke endres i løpet av beregningene. Alle prosesser i programmet er sekvensielt nummerert fra 0 til np-1, hvor np er det totale antallet prosesser. Prosessnummeret kalles prosessens rangering.

Parallelle prosesser samhandler med hverandre ved å sende meldinger. Det finnes to typer sendingsmetoder (de kalles kommunikasjon) - kollektive og punkt-til-punkt. I kollektiv kommunikasjon sender en prosess den nødvendige informasjonen samtidig til en hel gruppe prosesser; det er også et mer generelt tilfelle når det innen en gruppe prosesser overføres informasjon fra hver prosess til hver. Enklere kommunikasjon er punkt-til-punkt-kommunikasjon, når en prosess sender informasjon til den andre, eller begge utveksler informasjon. Kommunikasjonsfunksjoner er hovedfunksjonene til MPI-biblioteket. I tillegg er de obligatoriske funksjonene MPI-initialiserings- og termineringsfunksjonene - MPI_Init og MPI_Finalize. MPI_Init skal kalles helt i begynnelsen av programmer, og MPI_Finalize skal kalles helt på slutten. Alle andre MPI-funksjoner må kalles mellom disse to funksjonene.

Hvordan vet en prosess hvilken del av beregningen den skal gjøre? Hver prosess som kjører på en klynge har sitt eget unike nummer - rangering. Når en prosess kjenner sin rangering og det totale antallet prosesser, kan den bestemme sin del av arbeidet. For dette har MPI spesielle funksjoner - MPI_Comm_rank og MPI_Comm_size. MPI_Comm_rank returnerer et heltall - rangeringen til prosessen som kalte den, og MPI_Comm_size returnerer det totale antallet kjørende prosesser.

Prosessene til det parallelle brukerprogrammet som feilsøkes er gruppert. I MPI er en kommunikator et spesiallaget tjenesteobjekt som kombinerer en gruppe prosesser og en rekke tilleggsparametere (kontekst) som brukes når man utfører dataoverføringsoperasjoner. Kommunikatoren som automatisk opprettes når programmet starter og inkluderer alle prosesser på klyngen kalles MPI_COMM_WORLD. Beregninger kan opprette nye og slette eksisterende prosessgrupper og kommunikatører. Den samme prosessen kan tilhøre ulike grupper og kommunikatører. Kollektive operasjoner brukes samtidig for alle prosesser i kommunikatoren, så kommunikatoren vil alltid være en av parametrene for dem.

Når du utfører meldingsoverføringsoperasjoner i MPI-funksjoner, er det nødvendig å angi typen data som skal overføres. MPI inneholder et stort sett med grunnleggende datatyper basert på standard datatyper i C-språket. I tillegg kan programmereren konstruere sine datatyper ved hjelp av spesielle MPI-funksjoner. Nedenfor er en tabell over samsvar for de grunnleggende datatypene.

MPI-konstanter	C språk datatype
MPI_INT	signert int
MPI_UNSIGNED	usignert int
MPI_SHORT	signert int
MPI_LONG	signert lang int
MPI_UNSIGNED_SHORT	usignert int
MPI_UNSIGNED_LONG	usignert lang int
MPI_FLOAT	flyte
MPI_DOUBLE	dobbelt
MPI_LONG_DOUBLE	lang dobbel
MPI_UNSIGNED_CHAR	usignert røye
MPI_CHAR	signert røye

Et eksempel på å starte MPI-biblioteket: studentpålogging, passord s304.

#inkludere

#inkludere

int main (int argc, char * argv)

/ * Initialiser MPI * /

MPI_Init (& argc, & argv);

/ * få rangeringen av prosessen * /

MPI_Comm_rank (MPI_COMM_WORLD, & rangering);

/ * få det totale antallet prosesser * /

MPI_Comm_size (MPI_COMM_WORLD, & størrelse);

printf ("Hei verden fra prosess% d av% ​​d \ n", rangering, størrelse);

/ * avslutte MPI * /

Kompilator og linker brukes til kompilering. Kommandolinje mpicc. (se mpicc ... .- hjelp)

Hver av de kjørende prosessene skal vise sin rangering og det totale antallet prosesser. La oss prøve å kompilere og kjøre dette programmet.

$ mpicc hello.c –o hello.o

$ mpicc hello.o –o hallo

Hello-filen vil være den kjørbare filen i eksemplet. Du kan kjøre den på én maskin og se at antall prosessorer er 1, og rangeringen av prosessen er 0:

$ ./hei

Hei verden fra prosess 0 av 1

Når du arbeider på serveren, brukes kommandoen til å kjøre mpirun ... Den har to hovedargumenter - navnet på filen som inneholder adressene til nodene og antall noder programmet skal kjøre på.

$ mpirun n0-6 –v hosts hei

Hei verden fra prosess 0 av 7

Hei verden fra prosess 3 av 7

Hei verden fra prosess 5 av 7

Hei verden fra prosess 4 av 7

Hei verden fra prosess 2 av 7

Hei verden fra prosess 6 av 7

Hei verden fra prosess 1 av 7

Programmet vil kjøre på 7 noder (inkludert serveren), og adressene til disse nodene er inne hosts-fil. Utskrift på skjermen ble utført av prosesser som ikke var i rekkefølgen til deres rekker. Dette skyldes at starten av prosesser ikke er synkronisert, men det er spesielle funksjoner i MPI for synkronisering av prosesser.

Det enkleste programmet inneholder ingen meldingsfunksjoner. I oppgaver i den virkelige verden må prosesser samhandle med hverandre. Naturligvis tar overføring av meldinger tid, noe som reduserer oppgavens parallelliseringsfaktor. Jo høyere hastighet på meldingsgrensesnittet (f.eks. Ethernet 10Mb/sek og Gigabit Ethernet), desto lavere blir dataoverføringskostnadene. Fordi tiden for datautveksling mellom prosesser er mye (i størrelsesordener) lengre enn tiden for tilgang til eget minne, arbeidsfordelingen mellom prosesser bør være «grov», og unødvendige dataoverføringer må unngås.

Blant problemene med numerisk analyse er det mange problemer, hvor parallelliseringen er åpenbar. For eksempel reduseres numerisk integrasjon faktisk til (mange) beregning av integranden (som er naturlig å overlate til separate prosesser), mens hovedprosessen kontrollerer beregningsprosessen (bestemmer strategien for fordeling av integrasjonspunkter over prosessene og samler inn delvis summer). Problemer med å søke og sortere i en lineær liste, finne røttene til funksjoner numerisk, søke etter ekstrema av en funksjon av mange variabler, beregne serier og andre har lignende parallellisering. I denne laboratoriet skal vi se på to parallelle algoritmer for å beregne π.

Beregning av tallet π ved metoden for numerisk integrasjon

Det er kjent at

Vi har erstattet beregningen av integralet med endelig summering , hvor n er antall summeringsseksjoner i numerisk integrasjon. Arealet til hver seksjon beregnes som produktet av bredden på 'stripen' med verdien av funksjonen i midten av 'stripen', deretter summeres arealene av hovedprosessen (et enhetlig rutenett er brukt).

Åpenbart er det enkelt å parallellisere denne oppgaven hvis hver prosess beregner sin delsum og deretter overfører beregningsresultatet til hovedprosessen. Hvordan unngå repeterende beregninger her? Prosessen må kjenne sin rangering, det totale antallet prosesser og antall intervaller segmentet skal deles inn i (jo flere intervaller, jo høyere nøyaktighet). Deretter, i en syklus fra 1 til antall intervaller, vil prosessen beregne arealet av stripen på det i-te intervallet, og deretter gå ikke til neste i + 1-intervall, men til intervallet i + m , hvor m er antall prosesser. Som vi allerede vet, er det funksjoner for å få rangeringen og det totale antallet prosesser MPI_Comm_rank og MPI_Comm_size ... Før du starter beregningene, må hovedprosessen overføre antall intervaller til resten, og etter beregningene samle de mottatte delsummene fra dem og summere dem, i MPI implementeres dette ved å sende meldinger. Det er praktisk å bruke den kollektive interaksjonsfunksjonen for å overføre meldinger her. MPI_Bcast som sender de samme dataene fra én prosess til alle andre. Det er 2 alternativer for å samle inn delbeløp - du kan bruke MPI_Samle , som samler inn data fra alle prosesser og gir dem til én (det oppnås en rekke m elementer, der m er antall prosesser) eller MPI_Reduser . MPI_Reduser fungerer på samme måte MPI_Samle - samler inn data fra alle prosesser og gir det til en, men ikke i form av en matrise, men utfører foreløpig en viss operasjon mellom elementene i matrisen, for eksempel summering og gir så ett element. For denne oppgaven ser det mer praktisk ut å bruke MPI_Reduser ... Teksten til programmet er gitt nedenfor

#include "mpi.h"

#inkludere

#inkludere

dobbel f ​​(dobbel a)

retur (4,0 / (1,0 + a * a));

int main (int argc, char * argv)

int n, myid, numprocs, i;

dobbel PI25DT = 3,141592653589793238462643;

dobbel mypi, pi, h, sum, x;

dobbel startwtime, endwtime;

MPI_Init (& argc, & argv);

MPI_Comm_size (MPI_COMM_WORLD, & numprocs);

MPI_Comm_rank (MPI_COMM_WORLD, & myid);

startwtime = MPI_Wtime ();

MPI_Bcast (& n, 1, MPI_INT, 0, MPI_COMM_WORLD);

h = 1,0 / (dobbel) n;

for (i = myid + 1; i<= n; i += numprocs)

x = h * ((dobbel) i - 0,5);

MPI_Reduce (& mypi, & pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

printf ("pi er omtrentlig % .16f, feilen er % .16f \ n",

pi, fabs (pi - PI25DT));

endwtime = MPI_Wtime ();

printf ("veggklokketid =% f \ n",

endwtime-startwtime);

La oss se nærmere på funksjonskallene MPI_Bcast og MPI_Reduser :

MPI_Bcast (& n, 1, MPI_INT, 0, MPI_COMM_WORLD) - innholdet i variabel n og ett element av typen MPI_INT fra en prosess med rangering 0 sendes til alle andre prosesser (MPI_COMM_WORLD - alle prosesser i kommunikatoren) til samme variabel n. Etter denne samtalen vil hver prosess vite det totale antallet spor. På slutten av beregningene summerer MPI_Reduce (& mypi, & pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD) opp (MPI_SUM parameter) verdiene fra MPI_DOUBLE mypi-variablene for hver prosess og skriver resultatet til prosessen pi-variabel med rangering 0. For å måle beregningstidsfunksjonen MPI_Wtime.

dobbel MPI_Wtime ();

MPI_Wtime returnerer antall sekunder, i flyttallformat, som representerer tiden som har gått siden starten av programmet.

Beregning av π ved Monte Carlo-metoden

"Skyting"-metoden kan brukes til å beregne verdien av π. Som anvendt i dette tilfellet består metoden i å generere punkter jevnt fordelt over et todimensjonalt område og bestemme.

Verdien av π beregnet på denne måten er omtrentlig; i det generelle tilfellet øker nøyaktigheten av å beregne den ønskede verdien med en økning i antall 'skudd' og kvaliteten på tilfeldig tallgeneratoren; lignende metoder brukes i tilfelle problemer med nøyaktig numerisk estimering.

Den parallelle algoritmen for å beregne tallet π ved denne metoden er på mange måter lik den forrige algoritmen vi vurderte. For å generere tilfeldige tall, må du bruke srand-funksjonen, som setter rangeringen av prosessen som et argument (frøet til sekvensen), så hver prosess vil ha sin egen sekvens.

#inkludere

void srand (usignert frø);

srand ()-funksjonen setter startnummeret for sekvensen generert av rand ()-funksjonen.

#inkludere

int rand (tomt);

Rand ()-funksjonen genererer en sekvens av pseudo-tilfeldige tall. Hvert kall til funksjonen returnerer et heltall mellom null og RAND_MAX-verdien.

For å samle resultatet er det også praktisk å bruke MPI_Reduce med spesifikasjonen for summeringsoperasjonen (MPI_SUM), og deretter dele den resulterende summen med antall prosessorer, og få det aritmetiske gjennomsnittet.

int MPI_Reduce (void * sendbuf, void * recvbuf, int count,

MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm);

Alternativer:

sendbuf-adressen til sendebufferen

recvbuf mottak buffer adresse

opreduksjonsoperasjon

kommunikator

int MPI_Bcast (void * buffer, int count, MPI_Datatype datatype, int root,

MPI_Comm comm);

Alternativer:

bufferadressen til sende/mottaksbufferen

telle antall elementer i sendebufferen (heltall)

datatype datatype for elementene i sendebufferen

rot hovedprosessnummer (heltall)

kommunikator

Trening: i samsvar med variantnummeret, kompiler og kjør det parallelle programmet som beregner tallet π i henhold til den gitte algoritmen.

Kjør oppgaven på én node og fra en klynge, på et spesifisert antall noder. Estimere beregningstiden, nøyaktigheten og parallelliseringsfaktoren til Amdahl, ta hensyn til nettverkslatens teoretisk og basert på resultatene av arbeidet.

Jobbalternativer

Alternativ nr.	Algoritme	Antall prosessorer	Antall iterasjoner på hver prosessor
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo
	Numerisk integrasjon
	Monte Carlo

· Redegjørelse av problemet, alternativ.

· Teksten til parallellprogrammet på C-språket i henhold til oppgaven.

· Resultater av å kjøre programmet på én node, utførelsestid t i, beregningsresultat, feil.

· Resultater av å kjøre programmet på serveren, utførelsestid, beregningsresultat, feil.

· Beskriv den parallelle algoritmen, informasjonsflyt under programkjøring og lasting av cache-minnet til noder. Beregn Amdahl-koeffisienten - K j basert på resultatene av programmet.

· Ta i betraktning resultatene av arbeidet til en gruppe studenter, bygg et histogram over avhengigheten av K j, t i på antall prosessorer som er involvert i beregningene.

• Opplæringen

I dette innlegget vil vi snakke om å organisere datautveksling ved hjelp av MPI ved å bruke eksemplet med Intel MPI Library. Vi tror at denne informasjonen vil være av interesse for alle som ønsker å bli kjent med feltet parallell høyytelses databehandling i praksis.

Vi vil gi en kort beskrivelse av hvordan datautveksling er organisert i parallelle applikasjoner basert på MPI, samt lenker til eksterne kilder med en mer detaljert beskrivelse. I den praktiske delen finner du en beskrivelse av alle stadier av utviklingen av "Hello World" demo MPI-applikasjonen, fra å sette opp det nødvendige miljøet og avslutte med å starte selve programmet.

MPI (Message Passing Interface)

MPI er et grensesnitt for å sende meldinger mellom prosesser som utfører samme oppgave. Den er først og fremst ment for distribuerte minnesystemer (MPP) i motsetning til for eksempel OpenMP. Et distribuert (klynge) system er som regel et sett med beregningsnoder forbundet med kommunikasjonskanaler med høy ytelse (for eksempel InfiniBand).

MPI er den vanligste grensesnittstandarden for dataoverføring i parallell programmering. MPI er standardisert av MPI Forum. Det finnes MPI-implementeringer for de fleste moderne plattformer, operativsystemer og språk. MPI er mye brukt for å løse ulike problemer innen beregningsfysikk, farmasøytiske produkter, materialvitenskap, genetikk og andre kunnskapsfelt.

Et parallelt program fra MPIs synspunkt er et sett med prosesser som kjører på forskjellige beregningsnoder. Hver prosess er avledet fra den samme programkoden.

Hovedoperasjonen i MPI er meldingsoverføring. Nesten alle de grunnleggende kommunikasjonsmønstrene er implementert i MPI: punkt-til-punkt, kollektiv og ensidig.

Jobber med MPI

La oss se på et levende eksempel på hvordan et typisk MPI-program fungerer. Som en demoapplikasjon tar vi kildekoden til eksemplet som følger med Intel MPI Library. Før vi kjører vårt første MPI-program, må vi forberede og sette opp et arbeidsmiljø for eksperimenter.

Sette opp et klynget miljø

For eksperimenter trenger vi et par beregningsnoder (helst med lignende egenskaper). Hvis du ikke har to servere for hånden, kan du alltid bruke skytjenester.

For denne demonstrasjonen valgte jeg Amazon Elastic Compute Cloud (Amazon EC2). For nye brukere tilbyr Amazon et gratis prøveår for servere på startnivå.

Å jobbe med Amazon EC2 er intuitivt. Hvis du har spørsmål, kan du se den detaljerte dokumentasjonen (på engelsk). Hvis du ønsker det, kan du bruke en hvilken som helst annen lignende tjeneste.

Vi lager to fungerende virtuelle servere. Velg i kontrollkonsollen EC2 virtuelle servere i skyen, deretter Start forekomst("Forekomst" betyr en virtuell serverforekomst).

Det neste trinnet er å velge operativsystem. Intel MPI Library støtter både Linux og Windows. For det første bekjentskapet med MPI vil vi velge OS Linux. Vi velger Red Hat Enterprise Linux 6.6 64-bit eller SLES11.3 / 12.0.
Vi velger Forekomsttype(servertype). For eksperimenter er t2.micro egnet for oss (1 vCPUer, 2,5 GHz, Intel Xeon-prosessorfamilie, 1 GiB RAM). Som nyregistrert bruker kunne jeg bruke denne typen gratis - merket "Gratis nivå kvalifisert". Vi setter Antall forekomster: 2 (antall virtuelle servere).

Etter at tjenesten ber oss om å kjøre Start Forekomster(konfigurerte virtuelle servere), lagre SSH-nøklene som vil være nødvendig for å kommunisere med virtuelle servere fra utsiden. Statusen til virtuelle servere og IP-adresser for kommunikasjon med serverne til den lokale datamaskinen kan overvåkes i administrasjonskonsollen.

Et viktig poeng: i innstillingene Nettverk og sikkerhet / Sikkerhetsgrupper det er nødvendig å lage en regel som vi åpner porter for TCP-tilkoblinger med - dette er nødvendig for MPI-prosessbehandlingen. Regelen kan se slik ut:

Type: Egendefinert TCP-regel
Protokoll: TCP
Portområde: 1024-65535
Kilde: 0.0.0.0/0

Av sikkerhetsgrunner kan en strengere regel settes, men for vår demo er dette tilstrekkelig.

Og til slutt, en liten undersøkelse om mulige emner for fremtidige publikasjoner om databehandling med høy ytelse.

Kun registrerte brukere kan delta i undersøkelsen. , vær så snill.