next up previous
Next: 3.3.2 Gather-Scatter-Operationen Up: 3.3 Grundlegende globale Operationen Previous: 3.3 Grundlegende globale Operationen

   
3.3.1 EXCHANGE

EXCHANGE($LinkNo$, $nWords$, $SendData$, $RecvData$)

Austausch von Daten zwischen den Prozessoren $p$ und $q$ über das Link $LinkNo$.

Variante a)
 
Abbildung 3.12: EXCHANGE non-blocking
\begin{figure} \unitlength0.05\textwidth \begin{center} \begin{picture} (9,5)... ...(6,3.5){\vector(-3,-2){3}} \thinlines \end{picture} \end{center} \end{figure}

Variante b)

Verklemmungsfreies EXCHANGE zwischen $p$ und $q$ bei blockierender Kommunikation erfordert eine eindeutige Vorschrift, welcher von beiden Prozessen zuerst senden bzw. empfangen darf. Die Funktion BTEST($k,link$)$\,=\,$ XOR( $k,2^{link-1}$) testet, ob das $link-1$-te Bit gesetzt ist oder ob nicht. Durch die Festlegung, daß der Prozeß, dessen entsprechendes Bit gesetzt ist zuerst senden und dann empfangen darf (beim anderen umgekehrt), ist ein deadlock-freies EXCHANGE realisierbar.
 
Abbildung 3.13: EXCHANGE blockierend
\begin{figure} \unitlength0.05\textwidth \begin{picture} (19,9.5) % \savebox{... ...(1,0){3}} \put(11,4){\vector(-1,0){3}} \thinlines \end{picture} \end{figure}



Gundolf Haase
1998-12-22