Introduzione 2
L’elaborazione della grande mole di dati forniti dal sistema multisensoriale a bordo
del robot (sensori ultrasonici, ottici, laser, GPS) che deve portare a decisioni in tempo
reale, giustifica l’implementazione da parte di Nergàl S.r.l. della scheda PCI
4
PCPR1
5
:
sistema di tipo MIMD
6
a multi-DSP a memoria distribuita (3.1) che associa i benefici
dovuti all’utilizzo di processori orientati ad applicazioni in tempo reale (DSP) , ai
vantaggi delle architetture parallele.
La scheda è composta da quattro Digital Signal Processor
7
connessi fisicamente in
una sorta di pipeline percorribile in entrambi i sensi (figura 3.4).
Le schede PCPR1 (il progetto prevede di utilizzarne fino a quattro nello stesso host),
attraverso uno slot PCI, vengono inserite in un computer il quale le utilizzerà come una
sorta di operai specializzati per determinate operazioni; ad esse saranno forniti dei dati
da elaborare e successivamente prelevati i risultati.
Ogni scheda è utilizzata come una unità hardware parallela allo host, dedicata ad
elaborazioni time-consuming, ed a sua volta, ogni scheda è composta da quattro unità
parallele (i DSP), su cui opereranno quattro processi distinti.
L’utente programmatore
8
può parallelizzare il suo algoritmo (5.1) in quattro processi
allocati sui quattro DSP (in questa fase del progetto si utilizza un’unica scheda), ma per
farlo necessita di una API
9
che gli permetta di attivare comunicazioni inter-DSP per lo
scambio di risultati parziali, finali e segnali di sincronismo.
Se da un lato le architetture parallele aggirano il limite fisico della frequenza di
funzionamento ed ottimizzano il rapporto prezzo/prestazioni, d’altra parte introducono
un overhead di comunicazione interprocesso che riduce le performance previste
teoricamente dalla legge di Amdahl (5.1).
Sfortunatamente processi che collaborano, anche se in modo indipendente, alla
realizzazione di un comune scopo, hanno la necessità di potersi parlare tra di loro. Lo
overhead di comunicazione è quindi un male necessario che può essere soltanto
controllato e ridotto, ma non eliminato.
4
PCI: Peripheral Component Interconnect, standard per la connessione di schede esterne alla CPU;
5
PCPR: Piattaforma di Calcolo Parallelo per la Robotica;
6
secondo la tassonomia di Flynn i MIMD sono sistemi che si basano sui flussi multipli di istruzioni e
flussi multipli di dati;
7
di tipo Analog Sharc 21065L;
8
la programmazione dei DSP 21065L è realizzata ad alto livello in C/C++, in ambiente VisualDSP++;
9
API: Application Program Interface, funzioni richiamabili dal programmatore all’interno del proprio
algoritmo che svolgono determinate operazioni;
Introduzione 3
Gli obiettivi che la presente tesi si pone sono:
1. la implementazione di un sistema che fornisca al programmatore della scheda
PCPR1 in ambiente C/C++, delle funzioni di base per la comunicazione di
generici messaggi tra i processori; MPI
10
(capitolo 2) è lo standard a cui ci si
è ispirati per la realizzazione del sistema; è basato fondamentalmente sul
concetto di messaggio che costituisce l’unità di informazioni che i processi
possono scambiarsi; tutto quello che i DSP possono trasmettersi è contenuto
nella struttura messaggio;
2. la realizzazione di un modello teorico di funzionamento del sistema MPI-
PCPR
11
, che preveda le performance del sistema di comunicazione al variare
della dimensione dei messaggi e del numero di hop
12
(5.3), in modo da
rilevare gli effetti dello overhead di comunicazione;
3. le misure sperimentali delle prestazioni del sistema di comunicazione (5.4) in
modo da evidenziare, al variare di parametri tunabili, come il sistema
reagisce ;
L’obiettivo 1 è stato realizzato con la ideazione e implementazione di MPI-PCPR,
sistema MPI-like, che realizza le funzioni di Send e Receive, bloccanti e non bloccanti,
attraverso un sistema costruito a strati (capitolo 4). Tali funzioni sono la base comune su
cui tutte le altre procedure MPI sono costruite.
La scrittura ex novo di una implementazione MPI si è resa necessaria, nonostante
l’esistenza di software open-source
13
(LAM, MPI-CH), vista l’impossibilità di una
operazione di porting dei sorgenti già scritti, sulla scheda PCPR1.
Le implementazioni già esistenti sono orientate a cluster di PC interconnessi
attraverso LAN
14
, tecnologia completamente diversa da quella presente sulla scheda
PCPR1 (2.5.3, 2.5.4).
10
Message Passing Interface
11
MPI-PCPR è il nome che è stato dato alla applicazione MPI-like per scheda PCPR1;
12
numero di DSP fisicamente frapposti tra i due processori comunicanti;
13
sorgente disponibile gratuitamente, su cui è possibile effettuare variazioni ed adattamenti;
14
Local Area Network, rete locale;
Introduzione 4
Ogni livello di MPI-PCPR fornisce a quello superiore dei servizi; i servizi
comprendono un determinato numero di funzioni, non accessibili direttamente
dall’utente (eccetto le API), sfruttabili dal livello superiore, il quale non ne conosce il
funzionamento, ma ne utilizza solamente gli effetti. L’implementazione dei servizi è
invece realizzata dalla strato che li mette a disposizione, il quale a sua volta sfrutta le
funzioni dello strato inferiore per soddisfare le proprie necessità.
La information hiding
15
, il nome dato a questa filosofia di progettazione, semplifica
sia la fase di ideazione e di scrittura del sorgente, che la fase di debugging e di eventuali
cambiamenti (capitolo 5). E’ possibile riscrivere completamente uno strato, l’importante
è il mantenimento delle stesse specifiche delle funzioni fornite all’esterno.
Nel sistema MPI-PCPR, un messaggio di alto livello, quello che l’utente richiede di
trasferire, verrà scomposto ed impacchettato in messaggi elementari (chiamati Sporti
Block) il cui trasferimento sarà demandato ai livelli inferiori.
In ricezione avverrà l’operazione contraria: gli SB forniti dai livelli inferiori saranno
ricomposti nel buffer utente in modo da ricostruire un messaggio di alto livello.
La prima parola di uno SB è lo header che realizza un mini protocollo di
comunicazione utilizzato dal Nastro Trasportatore, per il suo instradamento al DSP di
destinazione.
Il Nastro Trasportatore è il livello più hardware-dependent (scritto in Assembler)
della struttura a strati; è quel meccanismo sincrono, in esecuzione su ogni DSP, che
gestisce la consegna e l’instradamento dei blocchetti elementari, sfruttando i controllori
di DMA messi a disposizione dallo hardware delle seriali.
Tutto quello che l’utente deve fare, in accordo con la sintassi delle funzioni API, è
inserire il proprio messaggio in un buffer, richiamare la funzione Send o Receive
(bloccanti o non bloccanti) indicando il puntatore a tale buffer e l’identificativo del
processore destinatario o mittente.
15
nascondere le informazioni; ogni livello fornisce al superiore dei servizi ma ne nasconde il
funzionamento;
Introduzione 5
Il progetto PCPR-PRASSI non pone rigidi vincoli progettuali per la realizzazione
della interfaccia MPI-like; è stato quindi indispensabile rendere il progetto il più
flessibile possibile, mettendo a disposizione dell’utente parametri tunabili
16
, in modo da
tarare il sistema a seconda delle proprie necessità e facilitare il successivo apporto di
modifiche al sorgente (la struttura a strati è la risposta ottimale a quest’ultimo vincolo).
E’ possibile, per l’utilizzatore, agire sulla dimensione delle code di bufferizzazione
in ricezione e trasmissione dei messaggi elementari, intimamente legate al variare della
banda passante del sistema di comunicazione. L’utente, conoscendo le dimensioni
tipiche dei messaggi che intende utilizzare, potrà agire su tale parametro, adattando il
sistema alle proprie necessità (4.4).
E’ possibile orientare MPI-PCPR verso algoritmi che utilizzano con alta frequenza
le comunicazioni e verso quelli che raramente comunicano. Si agisce rallentando o
aumentando la frequenza di esecuzione del gestore dei messaggi (SPORTI), il che porta
ad un minore o maggiore utilizzo della CPU a scapito del programma utente (5.4.3).
Se il sistema è tarato in modo da risultare più orientato verso le comunicazioni,
impiegherà più CPU-time per la loro gestione, tempo che sarà sottratto a quello di
elaborazione utente.
Se invece il sistema viene tarato in modo da far sfruttare al massimo il DSP al
programma utente, si rallenterà la gestione delle comunicazioni, con relativo
peggioramento delle performance.
Scopo di questa tesi è la implementazione, l’ideazione di un modello teorico e lo
studio sperimentale, di una interfaccia ispirata allo standard MPI per la comunicazione
tra processi eseguiti in parallelo, su una scheda proprietaria multi-DSP
Innanzitutto nel capitolo 1, vengono descritte le finalità del progetto PRASSI,
diventato progetto PCPR all’interno della Nergàl S.r.l.
Nel capitolo 2 viene introdotto lo standard della comunicazione di messaggi tra
processi paralleli, MPI; se ne illustrano i concetti fondamentali, soffermandosi sulle
diverse modalità di comunicazione; si introducono brevemente alcune realizzazioni già
esistenti di MPI (LAM e MPI-CH) evidenziandone l’impossibilità di porting sulla
scheda PCPR1.
16
regolabili in base all’esigenza dell’utente;
Introduzione 6
Lo hardware ed il software utilizzati vengono descritti nel capitolo 3, dove viene
analizzata la scheda PCPR1 ma anche il VDSP++ utilizzato per la realizzazione del
progetto.
MPI-PCPR, ossia la nuova realizzazione MPI-like su scheda PCPR1, è descritta nel
capitolo 4, attraverso i suoi concetti fondamentali. Vengono spiegati i diversi strati che
compongono il sistema implementato, il loro funzionamento, le funzioni realizzate, il
protocollo di comunicazione, il funzionamento del sistema Nastro Trasportatore, il
problema e la risoluzione della gestione di risorse comuni (critiche), l’algoritmo ed il
funzionamento del gestore dei messaggi a basso livello (SPORTI), l’interfacciamento tra
il sistema utente (asincrono) e quello SPORTI (sincrono), l’utilizzo di code cicliche ed i
parametri tunabili del sistema.
Una volta esauriti gli aspetti implementativi del progetto si passa, con il capitolo 5,
ad illustrare le tecniche utilizzate per la fase di testing e debugging. Inoltre viene
spiegata la procedura adottata per il rilevamento delle performance del sistema di
comunicazione, gli echo test; le misure vengono elaborate e poi visualizzate in modo
grafico al variare di alcune grandezze tunabili del sistema. Tipici diagrammi sono:
l’andamento della banda passante in funzione della lunghezza del messaggio, al variare
del numero di hop
17
, al variare della capacità massima delle code di bufferizzazione e
della frequenza di esecuzione del gestore dei messaggi (SPORTI). Inoltre, nel capitolo
5, ci si sofferma anche sugli aspetti di consumo di CPU-time dell’intero sistema MPI-
like al variare della frequenza di esecuzione dello SPORTI; in particolare si mette in
evidenza un diagramma attraverso il quale è possibile ricavare quanta CPU è destinata
al programma utente, in base alla massima banda passante selezionata.
Infine con il capitolo 6 si indicano le conclusioni finali sul progetto realizzato e gli
aspetti su cui focalizzare l’attenzione per eventuali miglioramenti ed evoluzione del
sistema MPI-PCPR.
In appendice è descritto il funzionamento del DSP su cui la scheda PCPR1 è basata,
lo Sharc 21065L. Dopo aver brevemente analizzato il passaggio dalla classica
architettura di Von Neumann a quella Harvard e successivamente alla SHARC
18
, si
passano in rassegna tutti i sottosistemi che costituiscono il DSP, in particolare le Serial
Port (Sport).
17
saltelli, numero di DSP che un messaggio deve attraversare prima di arrivare a destinazione;
18
SHARC: Super Harvard Architecture, evoluzione della architettura Harvard;
CAPITOLO 1. Il progetto PRASSI - PCPR 7
CAPITOLO 1
IL PROGETTO PRASSI – PCPR
1.1 Il progetto PRASSI
Il progetto PRASSI (Sistemi di calcolo ad elevato parallelismo per l’elaborazione in
tempo reale di dati multisensoriali per sistemi robotici autonomi adibiti a mansioni di
sorveglianza e sicurezza) è stato finanziato dal Ministero per l’Università e la Ricerca
Scientifica e Tecnologica (MURST) nel 1995.
Il progetto PRASSI rientra nell’iniziativa “Calcolo Parallelo con Applicazioni alla
Robotica”, coinvolge università e centri di ricerca ed è coordinato dall’ENEA (Ente per
le Nuove tecnologie, l’Energia e l’Ambiente).
Obiettivo finale del progetto è la realizzazione di un robot destinato alla
sorveglianza di aree industriali molto ampie o di ambienti ostili all’uomo, in cui il robot
possa autonomamente muoversi, senza controllo umano.
Il problema di maggior interesse riguarda proprio la capacità del sistema di
ricostruire ed analizzare la struttura tridimensionale di un nuovo ambiente, sfruttando le
informazioni derivate da vari sensori, quali quelli ultrasonici, ottici e laser, in modo da
garantirgli sufficiente autonomia.
Normalmente i robot commerciali riescono a seguire un percorso ben definito,
abitualmente un ambiente interno dove hanno imparato o gli è stato insegnato a
muoversi.
La difficoltà invece riguarda nuovi ambienti esterni; il sistema deve essere in grado,
in tempo reale, di prendere decisioni sul percorso da seguire, utilizzando
prevalentemente i sensori di cui è dotato.
Il robot è basato sul modulo commerciale ATRV, della Real World Interface, una
divisione della iRobot
1
.
1
Per ulteriori informazioni consultare il sito: www.irobot.com
CAPITOLO 1. Il progetto PRASSI - PCPR 8
L’aver deciso per un prodotto commerciale già esistente, anziché dedicarsi alla
progettazione ex novo di un proprio sistema hardware-software, è stato fatto allo scopo
di concentrare gli sforzi del progetto sulle funzionalità d’alto livello, disponendo degli
attuatori e dei controlli di basso livello forniti già dal veicolo ATRV.
Il robot oltre numerosi sensori (12 sonar, uno scanner laser, un ricevitore GPS ed un
sistema di visione stereoscopica) comprende anche un sistema di elaborazione basato su
una scheda madre dual-processor
2
, due processori Pentium ed il sistema operativo
LINUX.
2
scheda madre ad alte prestazioni che può alloggiare fino a due processori funzionanti in parallelo;
Figura 1.1 Il robot ATRV prodotto dalla iRobot.
CAPITOLO 1. Il progetto PRASSI - PCPR 9
1.2 Il progetto Nergàl PCPR
La Nergàl S.r.l. nell’ambito del progetto PRASSI, si occupa fondamentalmente della
progettazione hardware e software di una piattaforma di calcolo parallelo di bordo, per
applicazioni in grado di gestire la moltitudine di dati provenienti dai sensori e fornire al
robot un sistema per la visione artificiale.
Quest’area di progetto è denominata PCPR (Piattaforma di Calcolo Parallelo per la
Robotica), il cui logo è mostrato in seguito.
L’utilizzo del calcolo parallelo nell’ambito del progetto PRASSI è necessario per
l’esigenza di ottenere prestazioni in tempo reale.
Una migliore ricostruzione dell’ambiente, infatti, può essere ottenuta mediante
l’impiego di una più vasta quantità di dati provenienti dai sensori e il calcolo parallelo
può soddisfare la richiesta computazionale dell’elaborazione in tempo reale.
Il progetto PCPR è finalizzato alla ideazione e attuazione di un sottosistema
hardware e software, che possa affiancare il sistema host nel processare i segnali
provenienti dai sensori.
Il sistema hardware PCPR consta di una scheda (descritta nel capitolo 3)
equipaggiata con DSP commerciali, gli SHARC 21065L, processori della Analog
(descritto in appendice A).
La scheda è utilizzata come una unità hardware parallela allo host, dedicata ad
elaborazioni time-consuming, molto più performante della CPU host (in realtà le CPU
sono due), a cui lo host invia dati e successivamente riceve dati processati.
PCPR
Piattaforma
Calcolo Parallelo
per la Robotica
NERGÀL
Figura 1.2 Logo del progetto PCPR
CAPITOLO 1. Il progetto PRASSI - PCPR 10
Le schede (si prevede l’utilizzo fino a 4 schede collegate allo host) vengono
utilizzate come operai specializzati solo in determinate operazioni, a cui lo host
demanda uno specificato compito, distribuendo loro il carico di lavoro e raccogliendo
successivamente i risultati.
1.2.1 L’interfaccia MPI-LIKE
Ogni scheda comprende 4 DSP 21065L
3
che costituiscono anche essi 4 unità
hardware indipendenti e connesse attraverso porte seriali (come descritto nel capitolo 3).
Ogni processore è in grado di eseguire un diverso algoritmo parallelamente agli altri e di
instaurare comunicazione inter-DSP.
Ogni processore, nella fase di inizializzazione dell’intero sistema, riceve dallo host il
proprio eseguibile. Tale compito è svolto dal loader (3.3), programma in esecuzione
sullo host che si occupa del caricamento del firmware
4
e della successiva trasmissione
da host verso scheda e viceversa, dei dati.
Ad ogni scheda sarà affidato un determinato algoritmo opportunamente
parallelizzato tra i quattro DSP e scritto in C, utilizzando l’ambiente di sviluppo
VDSP++ fornito dalla Analog (3.2).
Un algoritmo parallelo necessita, oltre che di essere eseguito da più unità di calcolo
contemporaneamente (per incrementare le performance), anche che i processi paralleli
siano in grado di cooperare fra loro, per scambiarsi i dati da elaborare, alcune
informazioni o risultati parziali.
MPI (2.1) è un’interfaccia che supporta il message passing tra processi, fornendo al
programmatore, a tale scopo, una serie di funzioni di alto livello.
3
www.analog.com
4
per firmware intenderemo l’intero codice che ogni DSP dovrà eseguire, composto dalla
implementazione MPI-PCPR e dalla applicazione utente
CAPITOLO 1. Il progetto PRASSI - PCPR 11
Uno dei compiti di Nergàl S.r.l. e scopo della presente tesi, è stato quello di scrivere
una interfaccia MPI-LIKE
5
, in modo da fornire all’utente programmatore
6
un semplice
strumento per attivare la intercomunicazione tra DSP; questo permette di riadattare
facilmente gli algoritmi paralleli già esistenti e scritti rispettando lo standard MPI o
scriverne di nuovi.
Includendo semplicemente il file header mpi.h, l’utente programmatore potrà
sfruttare quattro fondamentali chiamate per trasmettere e ricevere buffer di dati. La Send
(in versione bloccante e non bloccante) è utilizzata per trasferire dati verso un
determinato DSP. La Receive (in versione bloccante e non bloccante) è utilizzata per
ricevere dati da un determinato DSP.
Il progetto PCPR-PRASSI non pone dei rigidi vincoli progettuali per quanto riguarda
la ideazione della nostra interfaccia MPI-LIKE, chiamata MPI-PCPR.
MPI-PCPR è stata quindi pensata e sviluppata in modo da essere in futuro
eventualmente modificata e adeguata a successive varianti progettuali.
Infatti MPI-PCPR è innanzitutto scritta a strati indipendenti, in modo che possa
essere completamente ripensato uno strato, rispettandone il funzionamento all’esterno,
senza modificare l’intero progetto.
MPI-PCPR fornisce le primitive fondamentali di basso livello (Send_SB,
Receive_SB, Send_SB_nb e Receive_SB_nb, vedi capitolo 4) su cui è possibile costruire
in futuro tutte le altre funzioni MPI più complesse.
Il progetto PRASSI-PCPR non pone dei limiti neanche per quanto riguarda
l’intensità del traffico di messaggi che il sistema dovrà gestire.
MPI-PCPR è quindi stata sviluppata in modo da essere tunabile
7
a seconda delle
necessità dell’utente (4.4.3).
5
interfaccia che si ispira alla MPI standard, conservandone similitudini;
6
colui che scriverà l’applicazione parallela per la scheda, sfruttando l’interfaccia MPI;
7
tarare opportunamente delle variabili di un sistema, in modo da adattarne il funzionamento alle proprie
esigenze;
CAPITOLO 1. Il progetto PRASSI - PCPR 12
E’ infatti possibile modificare la dimensione di alcune delle strutture di
bufferizzazione interne al sistema, in modo da gestire lo stoccaggio di messaggi di una
maggiore o minore grandezza; una maggiore memoria per l’immagazzinamento dei
messaggi comporta un aumento delle performance (5.4.2) e la possibilità di gestire più
messaggi pendenti
8
, ma anche un maggior consumo di memoria.
E’ anche possibile rendere il sistema più orientato verso comunicazioni frequenti o
verso comunicazioni meno frequenti, adeguandolo alla intensità del traffico, variando la
frequenza di esecuzione del meccanismo di gestione dei messaggi elementari (SPORTI,
capitolo 4).
Per ottenere questa versatilità è stato pensato un sistema di comunicazioni a basso
livello di tipo sincrono, quello che in seguito sarà descritto e chiamato Nastro
Trasportatore (4.2), che trasferisce attraverso il proprio nastro pacchetti elementari di
dati in cui un messaggio complesso sarà scomposto.
La velocità del Nastro Trasportatore è tarabile dall’utente che la regolerà in modo
da fornire alla propria applicazione più CPU-time
9
per l’esecuzione, sottraendolo alla
gestione e smistamento dei messaggi, sistema che invece subirà un rallentamento.
Viceversa è possibile accelerare la gestione e smistamento dei messaggi a scapito
del tempo di CPU fornito alla applicazione utente, orientando MPI-PCPR verso sistemi
a comunicazione più frequente.
8
messaggi inviati ma non ancora ricevuti, cioè il processo ricevente non ha avviato ancora la procedura
Receive;
9
tempo che la CPU impiega per la esecuzione di una serie di operazioni;
CAPITOLO 2. Introduzione allo standard MPI ed implementazioni esistenti 13
CAPITOLO 2
INTRODUZIONE ALLO STANDARD MPI
ED IMPLEMENTAZIONI ESISTENTI
2.1 Dal Paradigma della Programmazione Sequenziale a quello del Message Passing
Il paradigma della programmazione sequenziale prevede che il programmatore
abbia una visione semplificata della macchina che prescinda dalla sua reale maggiore o
minore complessità [10].
Tutto quello che il programmatore deve considerare nella scrittura di un programma,
è una macchina avente un singolo processore che può accedere, in modo esclusivo, ad
una propria memoria con una certa capacità.
In realtà il paradigma potrà essere implementato in vari modi a seconda della vera
struttura della macchina. Per esempio ci può essere un sistema di tipo time sharing, in
cui lo stesso processore è condiviso a divisione di tempo da più processi che utilizzano
la stessa memoria.
Il programmatore vuole restare al di sopra della dipendenza dal diverso tipo di
implementazione, nel senso che, il suo programma, dovrà essere scritto e potrà essere
eseguito come se realmente girasse su un unico processore con memoria ad accesso
esclusivo.
Il paradigma message-passing è una naturale evoluzione di questa idea applicata
però alla programmazione parallela.
Il programmatore immagina di avere diversi processori ognuno con un proprio spazio
di memoria e scrive diversi programmi ognuno dei quali girerà su una diversa CPU con
la possibilità di instaurare comunicazioni tra i diversi processi.
Infatti la programmazione parallela, per definizione, necessita di cooperazione tra i
diversi processi affinché possa essere portato al termine un determinato lavoro, tale
cooperazione, richiede un qualche tipo di comunicazione.
CAPITOLO 2. Introduzione allo standard MPI ed implementazioni esistenti 14
Quindi se da un lato si sfrutta il parallelismo hardware per incrementare le
performance di un sistema, d’altra parte è necessario implementare un meccanismo per
la intercomunicazione tra i processi.
Le modalità hardware e software attraverso le quali si realizza la connessione di un
sistema multi-processore, restano trasparenti al programmatore che potrà così
concentrarsi sulla scrittura dell’algoritmo parallelo, sfruttando le chiamate per le
comunicazioni tra processi.
I programmi scritti seguendo il paradigma message-passing possono essere eseguiti
su sistemi multi processori a memoria condivisa o distribuita, oppure su reti di
workstation o anche su semplici sistemi a singolo processore
1
, oppure, come nel nostro
caso, su schede PCI multi-DSP; l’importante è che il sistema, comunque esso sia fatto,
abbia una implementazione del paradigma del message-passing.
1
in realtà questa è solo una applicazione didattica, non comporta un reale incremento delle prestazioni,
non essendoci unità hardware parallele ed indipendenti;
Figura 2.1 Programmazione strutturale - Message Passing
paradigma di programmazione
M
P
M
P
M
P
M
P
rete di interconnessione
paradigma message-passing
CAPITOLO 2. Introduzione allo standard MPI ed implementazioni esistenti 15
La possibilità, messa a disposizione del message-passing, di scrivere diversi
programmi che possano essere eseguiti uno su ogni singolo processore, è raramente
sfruttata dai programmatori.
Il caso più frequente è invece quello descritto dall’acronimo SPMD (Single Program
Multiple Data) [4] che è una restrizione del paradigma message-passing; esso prevede
che ogni processore esegua lo stesso algoritmo, ma su dati diversi.
Ci si riferisce ad una tipologia di problemi scomponibili in sotto-problemi ognuno
dei quali è risolvibile allo stesso modo.
Nell’elaborazione delle immagini è possibile, per esempio, dividere un frame in più
parti e far elaborare ogni parte da un diverso processo che implementi uno stesso
algoritmo (SPMD) anziché elaborare una immagine intera.
La convenienza, in termini di tempo di elaborazione, è maggiormente evidente se si
avesse a disposizione un processore dedicato per ogni singola parte, in cui il frame è
stato scomposto.
Un tipico algoritmo parallelo divide una generica griglia in più frammenti ed ogni
ritaglio è elaborato allo stesso modo, con la possibilità di scambio di risultati parziali tra
i processi durante l’esecuzione.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
