Parallel processing, the method of having many small tasks
solve one large problem, has emerged as a key enabling technology in modern
computing. The past several years have witnessed an ever-increasing acceptance
and adoption of parallel processing, both for high-performance scientific
computing and for more “general-purpose" applications, was a result of the
demand for higher performance, lower cost, and sustained productivity. The
acceptance has been facilitated by two major developments: massively parallel
processors (MPPs) and the widespread use of distributed computing.
MPPs are now
the most powerful computers in the world. These machines combine a few hundred
to a few thousand CPUs in a single large cabinet connected to hundreds of
gigabytes of memory. MPPs offer enormous computational power and are used to
solve computational Grand Challenge problems such as global climate modeling
and drug design. As simulations become more realistic, the computational power
required to produce them grows rapidly. Thus, researchers on the cutting edge
turn to MPPs and parallel processing in order to get the most computational
power possible.
The second
major development affecting scientific problem solving is distributed
computing. Distributed computing is a process whereby a set of computers
connected by a network are used collectively to solve a single large problem.
As more and more organizations have high-speed local area networks
interconnecting many general-purpose workstations, the combined computational
resources may exceed the power of a single high-performance computer. In some cases,
several MPPs have been combined using distributed computing to produce
unequaled computational power. The most important factor in distributed
computing is cost. Large MPPs typically cost more than $10 million. In
contrast, users see very little cost in running their problems on a local set
of existing computers. It is uncommon for distributed-computing users to
realize the raw computational power of a large MPP, but they are able to solve
problems several times larger than they could use one of their local computers.
Common between
distributed computing and MPP is the notion of message passing. In all parallel
processing, data must be exchanged between cooperating tasks. Several paradigms
have been tried including shared memory, parallelizing compilers, and message
passing. The message-passing model has become the paradigm of choice, from the
perspective of the number and variety of multiprocessors that support it, as
well as in terms of applications, languages, and software systems that use it.
The Parallel
Virtual Machine (PVM) system described in this book uses the message passing
model to allow programmers to exploit distributed computing across a wide
variety of computer types, including MPPs. A key concept in PVM is that it
makes a collection of computers appear as one large virtual machine, hence its
name. The empirical investigations revealed that our parallel implementation
scales sufficiently well on Parix and PVM for moderate systems sizes (<256
processors). This is because few communication occurs in this specific
application, and many requests are answered in the direct neighborship of the
requester. For the larger system sizes, Parix clearly outperforms PVM. We
expect the gap between Parix and PVM to become more pronounced in applications
with a higher communication demand.
The performance
loss for larger systems is mainly caused by the implementation of PVM for the
transputer system. Especially the restriction that only one task on each
processor is possible yields to slower communication because each message could
not be processed immediately after receivement. Further it is not possible to
do efficient work-load balancing if PVM does not provide any information about
the MPP, i.e. the position of a task in the network or information about the
tasks in the direct neighborship.
PROTOCOLS
PVM
communication is based on TCP, UDP, and Unix-domain sockets. While more
appropriate protocols exist, they aren't as generally available. VMTP is one
example of a protocol built for this purpose. Although intended for RPC-style
interaction (request-response), it could support PVM messages. It is packet
oriented and efficiently sends short blocks of data (such as most pvmd-pvmd
management messages) but also handles streaming (necessary for task-task
communication). It supports multicasting and priority data. Connections don't
need to be established before use; the first communication initializes the
protocol drivers at each end. VMTP was rejected, however because it is not
widely available.
1 Pvmd-Pvmd
PVM daemons
communicate with one another through UDP sockets. UDP is an unreliable delivery
service which can lose, duplicate or reorder packets, so an acknowledgment and
retry mechanism is used. UDP also limits packet length, so PVM fragments long
messages.
We considered
TCP, but three factors make it inappropriate. First is scalability. In a
virtual machine of N hosts, each pvmd must have connections to the other N-1.
Each open TCP connection consumes a _le descriptor in the pvmd, and some operating systems limit the number of open _les to as few as 32,
whereas a single UDP socket can communicate with any number of remote UDP
sockets. Second is overhead. N pvmds need N(N -1)/2 TCP connections, which
would be expensive to set up. The PVM/UDP protocol is initialized with no
communication. Third is fault tolerance. The communication system detects when
foreign pvmds have crashed or the network has gone down, so we need to set
timeouts in the protocol layer.
2 Pvmd-Task and
Task-Task
A task talks to
its pvmd and other tasks through TCP sockets. TCP is used because it delivers
data reliably. UDP can lose packets even within a host. Unreliable delivery
requires retry (with timers) at both ends: since tasks can't be interrupted
while computing to perform I/O, we can't use UDP.
0 comments: