Verbindungsnetzwerke - Operationsprinzipien MPI OS trap IP stack

Vorlesung Rechnerarchitektur 2
Seite 220
Verbindungsnetzwerke - Operationsprinzipien
Motivation: Standard Communication Methods
Levels of communication software which are traversed in standard communication systems
like Ethernet: application level, MPI, OS trap, IP stack, API, device driver, HW, network.
The same levels up on the receiving side.
Communication services: reliable message transfer, guaranteed delivery, no loss of packets,
ordered delivery, retain message sequence, flow control, fault handling, completion signalling.
Cost of Communication with COTS: 1GigEthernet
• Bandwidth not up-to-date
• End-to-End Latency poor: ~50 µs
There exists a large number of applications and algorithms which are latency tolerant or
where the latency can be hidden into computation, e.g. computer generated movies, calculation is done frame by frame, communication only for frame distribution and frame collection.
Application
1µs
MPI
OS trap
IP stack
25µs
24µs
Driver
I/O Bus
Device
Network
Sender
Receiver
Now: 10GigEthernet
• Solves bandwidth issue, not latency
• Only further optimizations (TCP offloading) reduce latency
End-to-end latency: ~11 µs
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 221
Verbindungsnetzwerke - Operationsprinzipien
I/O-Devices
An I/O-device is a resource of a computer system, which implements the function of a specific I/O-interface.
An I/O-interface is used to establish communication between a computer system and the outside world (may be another computer system or a peripheral device like a printer).
Common I/O-Devices:
•
•
•
•
Network
Storage (SCSI)
Peripherial (USB, Serial, Parallel)
Graphics
CPU
Cache
System
Bus
Addr
Data
I/O
bridge
I/O
device
Addr
Device Command Register
Data
I/O Bus
Device status Register
Device Data Register (read)
Device Data Register (write)
Generic I/O device block diagram
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 222
Verbindungsnetzwerke - Operationsprinzipien
I/O-Devices -PIO
Um auf ein I/O-Device zuzugreifen, wird im klassischen Fall der Programmed-I/O-Modus
angewandt (PIO). Hier ist es Aufgabe des Prozessors, die gewünschten Daten zu transportieren.
Mittels mmap wird der Adressraum des Devices in den Adressraum des Prozesses gemappt.
Dann kann mittels normalen load-/store-Befehlen auf das Device zugegriffen werden. Die
MMU sorgt dann dafür, daß diese Befehle nicht den Hauptspeicher, sondern die zuständige
Bridge addressieren.
CPU
virtual address
space of process
MMU
physical address space
of I/O-Device
load/store ops
System-Bus
MEM
I/O-Bridge
Device
Zugriffsschema für PIO
Nachteile:
• hohe Prozessorlast (vgl. busy-wait)
• Performance bzgl. Bandbreite nicht optimal
Vorteile:
• leicht zu implementieren
• minimale Latenz für einen Zugriff auf ein Device
Da in vielen Anwendungen die primäre Anforderung eine hohe Bandbreite ist und um den
Prozessor von den I/O-Operationen zu entlasten, wurde der Direct-Memory-Accesss-Modus
eingeführt (DMA). Hier können Daten zwischen Resourcen ohne Beteiligung des Prozessors
kopiert werden.
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 223
Verbindungsnetzwerke - Operationsprinzipien
DMA - Basics
Definition :
A direct memory access (DMA) is an operation in which data is copied
(transported) from one resource to another resource in a computer system without the involvement of the CPU.
The task of a DMA-controller (DMAC) is to execute the copy operation of data from one resource location to another. The copy of data can be performed from:
• I/O-device to memory
• memory to I/O-device
• memory to memory
• I/O-device to I/O-device
A DMAC is an independent (from CPU) resource of a computer system added for the concurrent execution of DMA-operations. The first two operation modes are ’read from’ and
’write to’ transfers of an I/O-device to the main memory, which are the common operation
of a DMA-controller. The other two operations are slightly more difficult to implement and
most DMA-controllers do not implement device to device transfers.
The DMAC replaces the CPU for the transfer task of data from the I/O-device to the main
memory (or vice versa) which otherwise would have been executed by the CPU using the
programmed input output (PIO) mode. PIO is realized by a small instruction sequence executed by the processor to copy data. The ’memcpy’ function supplied by the system is such
a PIO operation.
The DMAC is a master/slave resource on the system bus, because it must supply the addresses for the resources being involved in a DMA transfer. It requests the bus whenever a data
value is available for transport, which is signaled from the device by the REQ signal.
The functional unit DMAC may be integrated into other functional units in a computer system, e.g. the memory controller, the south bridge, or directly into an I/O-device.
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 224
Verbindungsnetzwerke - Operationsprinzipien
DMA - Operations
DMA
CPU
controller
Arbiter
Addr
Data
Memory
I/O
ACK
REQ
device
simplified logical structure of a system with DMA
A lot of different operating modes exist for DMACs. The simplest one ist the single block
transfer copying a block of data from a device to memory. For the more complex operations
please refer to the literature [Flik, Mot81]. Here, only a short list of operating modes is given:
• single block transfer
• chained block transfers
• linked block transfers
• fly-by transfers
All these operations normally access the block of data in a linear sequence. Nevertheless,
there are more usefull access functions possible, as there are:
•
•
•
•
constant stride
constant stride with offset
incremental stride
...
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 225
Verbindungsnetzwerke - Operationsprinzipien
DMA - Operations
DMAC
CPU
Memory
DMA Command Register
Device Base Register
2a.
1.
2b.
3.
Block Length Register
Mem Base Register
Temporary Data Register
1a.
Block
5. Length
Memory
Block
Mem Base Addr
6.
Descriptor
1b.
4.
I/O
device
Command
Area
Device Data Register
Execution of a DMA-operation (single block transfer)
The CPU prepares the DMA-operation by the construction of a descriptor (1), containing all
necessary information for the DMAC to independently perform the DMA-operation. It initalizes the operation by writing a command to a register in the DMAC (2a) or to a special
assigned memory area (command area), where the DMAC can poll for the command and/or
the descriptor (2b). Then the DMAC addresses the device data register (3) and read the data
into a temporary data register (4). In another bus transfer cycle, it addresses the memory
block (5) and writes the data from the temporary data register to the memory block (6).
1. CPU prepares the DMA-operation by the construction of a descriptor
2a. Initalization of the operation by writing a command to a register
2b. Initalization of the operation by writing a command to a special memory region
3. DMAC addresses the device data register
4. DMAC reads the data into a temporary data register
5. DMAC addresses Memory block
6. DMAC writes the data from the temporary data register to the memory block
[Mot81] MC68450 Direct Memory Access Controller, Product Data Sheet, Motorola Semiconductor Products Inc., 1981.
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 226
Verbindungsnetzwerke - Operationsprinzipien
DMA - Operations
The DMAC increments the memory block address and continue with this loop until the
block length is reached. The completion of the DMA operation is signaled to the processor
by sending an IRQ signal or by aserting a memory semaphore variable, which can be tested
by the CPU.
Two basic types of DMACs can be distinguished:
• register based DMAC
• descriptor based DMAC
A register based DMAC is controlled by programmed I/O-Cycles. The CPU writes the DMA
tasks with all needed information into the registers and starts the operation with a write to a
specific control bit ’DMA-start’. The completion of the operation can be tested at the status
register by ’spinning’ or by enabling the interrupt signaling.
The descriptor based DMAC can access the main memory to read and write the descriptor,
which contains the task description. Also the completion signaling is performed by a write
to a specific ’doorbell area’.
Both types of DMAC must be able to snoop the bus for cache coherency. This is difficult for
DMACs integrated into I/O-devices which are placed on an I/O-bus.
Further issues:
•
•
•
•
It is possible to replicate the register structure supporting multiple channels.
physical addressing, address translation required
DMA control signals
A DMAC is using bus bandwidth which may slow down processor execution
by bus conflicts (solution for high performance systems: use xbar as interconnect!)
[Flik] Mikroprozessortechnik, CISC, RISC Systemaufbau Assembler und C, Flik,Thomas, Springer Verlag, 6.Aufl. 2001.
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 227
Verbindungsnetzwerke - Operationsprinzipien
Anwendung von PIO und DMA auf Verbindungsnetzwerke
Send/Receive mittels PIO
Send:
• Prüfen ob ausreichend Speicher im NIC frei ist
• Schreibe Empfänger/Daten in Register (gemappt im Hauptspeicher), Speicher
auf dem NIC muss für ganze Nachricht ausreichen
• Informiere NIC über Sende-Operation
Receive:
• Prüfe ob Nachricht vorhanden
• Lese Daten aus Register aus, Speicher auf dem NIC muss für ganze Nachricht
ausreichen
• Informiere NIC über Receive-Operation (d.h. Speicher wird freigegeben)
Send/Receive mittels DMA
Send:
• Prüfe ob ausreichend Speicher im DMA-Bereich (Teil des Hauptspeichers, gepinnt und physikalisch fortlaufend) frei ist (für Daten UND Descriptor)
• Schreibe Daten in DMA-Bereich
• Setze Descriptor auf, der die Nachricht beschreibt (Adresse von Daten, Länge,
Empfänger, ...)
• Informiere NIC über neuen Descriptor
• NIC holt Daten aus Hauptspeicher in (kleinen) Zwischenspeicher auf dem NIC,
Versand erfolgt Paketweise
• NIC markiert Descriptor als konsumiert
Receive:
•
•
•
•
NIC überprüft, ob ausreichend Speicher im DMA-Bereich frei ist
NIC schreibt Daten in DMA-Bereich
NIC setzt Descriptor auf, der die empfangene Nachricht beschreibt
Alternativ: NIC informiert Prozess über Interrupt oder Prozess pollt auf Statusregister (-> Replication)
• Prozess kopiert Daten in privaten Bereich, markiert Descriptor als konsumiert
(beinhaltet Freigabe des DMA-Bereichs)
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 228
Verbindungsnetzwerke - Operationsprinzipien
Klassifizierung von Kommunikationsmethoden
Bisher bekannt: PIO und DMA-Methoden für Send/Receive-Kommunikation
Klassifizierbar nach:
• Two-sided and one-sided Communication
(processes involved in communication)
• Two-, one- and zero-copy (number
(number of copies done by processes)
• User-Level Communication
(bypassing of OS)
Für Synchronisation auf nachrichtenbasierten Systemen sind klassische Nachrichten erforderlich. Für die Kommunikation würden aber Lese-/Schreiboperation in den entfernten
Speicher ausreichen (dann eigentlich kein NORMA mehr!), ähnlich wie in speichergekoppelten Systemen. Diese entfernten Speicheroperationen bezeichnet man als Remote-Memory-Access (RMA) mit Put- und Get-Operationen.
Classification of Communication Schemes
User-Level
Communication
applies to all
Send/Receive
scheme
(asynchronous or
synchronous)
n-copy
(two-, one-, zero-)
1
0
2
Send/
Posted-Receive
scheme
Put/Get
(RMA)
scheme
Two-/one-sided
Communication
2
1
Synchronous
Put/Get
scheme
Klassifizierung von Kommunikationsmethoden
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 229
Verbindungsnetzwerke - Operationsprinzipien
User-level communication
virtual address space of process P
physical address space
I/O device
I/O mem
I/O mem
registers
Process P
VA base
phy. continuous
and pinned mem
data
desc
regular
working space
data
phy. continuous
and pinned mem
data
desc
DMAC
PA base
1. process copy data
2. process write desc
3. process trigger device
4. device fetches desc
5. device fetches data
Sending scheme for user-level communication with copying of data
User-level communication:
•
•
•
•
•
Direkter Zugriff vom Prozess auf das Device
Keine Involvierung des Betriebssystems
Exklusive Zuordnung des Devices für einen Prozess
Latenzarmer Zugriff durch Wegfall von OS-Traps
In Realität: Device wird nie ganz dem User überlassen, Konfiguration und
Überwachung muss priveligiert sein.
• Implementierung: Adressbereich für Datenaustausch für User-Prozess verfügbar, Adressbereich für Konfiguration/Überwachung nur für Daemon-Prozess.
• Physikalisch fortlaufender und gepinnter Speicherbereich notwendig, Addressumrechnung von VA <-> PA nur im Betriebssystem bekannt und bei User-level communication somit nicht mehr verfügbar.
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 230
Verbindungsnetzwerke - Operationsprinzipien
User-level communication
virtual address space of process P
physical address space
I/O device
I/O mem
I/O mem
registers
Process P
VA base
phy. continuous
and pinned mem
data
desc
phy. continuous
and pinned mem
data
desc
DMAC
PA base
5. process copy data
4. process reads desc
3. process polls status
2 device writes desc
1. device writes data
regular
working space
data
Receiving scheme for user-level communication with copying of data
Nachteil: Pollen des Prozesses auf dem Device Registern -> Verschwendung von I/O-Bandbreite.
Lösung: Replikation des Registers im Hauptspeicher, durch Cachekohärenz pollt der Prozess nur noch auf dem Cache.
virtual address space of process P
physical address space
I/O device
I/O mem
I/O mem
registers
Process P
VA base
phy. continuous
and pinned mem
phy. continuous
and pinned mem
status
status
data
desc
regular
working space
data
data
desc
DMAC
PA base
5. process copy data
4. process reads desc
3. device writes status, process polls
2 device writes desc
1. device writes data
Optimized receiving scheme for user-level communication with copying of data
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 231
Verbindungsnetzwerke - Operationsprinzipien
One-sided communication
Bisher mussten Nachrichten immer erst in einen Zwischenspeicher sowohl auf der Sendeals auch auf der Empfangsseite kopiert werden -> Two-copy.
Posted-Receives erlauben zumindest ein One-copy, da ein Kopiervorgang auf der Empfangsseite wegfällt.
Mittels RMA-Operationen ist es möglich, Zero-copy zu implementieren: Der ’Sender’
möchte beim ’Empfänger’ einen Speicherbereicht lesen oder schreiben. Der ’Sender’ teilt
dem NIC seine lokale Adresse mit den Daten sowie die entfernte Adresse mit. Der NIC wird
dann die Daten direkt vom Quellpuffer in den Zielpuffer schreiben.
Kombiniert man dies mit User-level communication, so sind nur virtuelle Adressen bekannt.
Die Hardware kann aber nur mit physikalischen Adressen umgehen, daher ist auf beiden Seiten eine Adressumsetzung von Nöten.
Speicherschutz auf dem entfernten Knoten wird mittels Windows implementiert.
Führt man die Zero-Copy operation ohne Benachrichtigung des Empfängers durch, so hat
man das Operationsprinzip der One-sided communication, da der Empfänger (jetzt: Target)
gar nicht mehr in die Kommunikation involiert ist.
virtual address space of process P
physical address space
I/O device
I/O mem
I/O mem
registers
Process P
VA base
phy. continuous
and pinned mem
desc
regular
working space
data
phy. continuous
and pinned mem
desc
DMAC with TLB
PA base
1. process write desc
2. process trigger device
3. device fetches desc
4. device fetches data
Origin side of RMA with user-level communication
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06
Vorlesung Rechnerarchitektur 2
Seite 232
Verbindungsnetzwerke - Operationsprinzipien
One-sided communication
virtual address space of process P
physical address space
I/O device
I/O mem
I/O mem
registers
phy. continuous
and pinned mem
Process P
VA base
phy. continuous
and pinned mem
DMAC with TLB
PA base
regular
working space
1. device writes data
data
Target side of RMA with user-level communication
Eigenschaften:
• Target bekommt von der Kommunikation nichts mit, keine Synchronisation
• Physikalisch fortlaufender und gepinnter Speicher beim Target nicht mehr notwendig
• ADRESSUMSETZUNG AUF DEM I/O-DEVICE NOTWENDIG
Lehrstuhl für Rechnerarchitektur - Universität Mannheim
WS05/06