Chapter 2 – Parallel and Distributed
Computing
ParallelApplications
Parallel Programming Environments
Sequential Applications
Compilers, PVM, MPI, ….
Cluster Middleware:
Single System Image and Availability Infrastructure
PC
PC // Workstation
Workstation PC
PC // Workstation
Workstation PC
PC // Workstation
Workstation PC
PC // Workstation
Workstation
CCoommmm
Common CCoommmm
Common CCoommmm
Common CCoommmm
Common
SW oonn
& SW oonn
& SW oonn
& SW oonn
&
SSWW &&
Applications SSWW &&
Applications SSWW &&
Applications SSWW &&
Applications
AApppplliicc AApppplliicc AApppplliicc AApppplliicc
aattiioonnss aattiioonnss aattiioonnss aattiioonnss
Operating System Operating System Operating System Operating System
OOppeer OOppeer OOppeer OOppeer
Network Interface HW Network Interface HW Network Interface HW Network Interface HW
raattiinngg raattiinngg raattiinngg raattiinngg
High speed network connection
SSyysstteem SSyysstteem SSyysstteem SSyysstteem
m m m m
Applications
User interface for presentation
Middleware
Distributed System Stack
Support for heterogeneous resource sharing, communication, and
programming environments for application development
Operative System
Execution platform including network connectivity services
Hardware
Computer and network hardware
MPI Programming, JMS,
MSMQ, MQS
Message Based
Communication
Paradigms /
Architectural
Models
Architectures
Sequential Era Compilers
Applications
Problem Solving Environments
Architectures
Compilers
Parallel Era Applications
Problem Solving Environments
1940 1950 1960 1970 1980 1990 2000 2010 2020 2030
Eras ofcomputing,1940s2030s.
Elements of parallel computing
• What is parallel processing?
• Hardware architectures for parallel processing
– Single-instruction, single-data (SISD) systems
– Single-instruction, multiple-data (SIMD) systems
– Multiple-instruction, single-data (MISD) systems
– Multiple-instruction, multiple-data (MIMD)
systems
• Approaches to parallel programming
– Data parallelism[SIMD]
– Process parallelism(Subtasks)
– Farmer-and-worker model[Master/Slave]
• Levels of parallelism
• Laws of caution
Instruction Stream
Data Input Data Output
Processor
Single-instruction, single-data (SISD)
architecture.
Single Instruction Stream
Data Input 1 Data Output 1
Processor 1
Data Input 2 Data Output 2
Processor 2
Data Input N Data Output N
Processor N
Single-instruction, multiple-data (SIMD)
architecture.
Instruction Instruction Instruction
Stream 1 Stream 2 Stream N
Single Data Output Stream
Single Data Input Stream
Processor 1
Processor 2
Processor N
Multiple-instruction, single-data (MISD)
architecture
Instruction Instruction Instruction
Stream 1 Stream 2 Stream N
Data Input 1 Data Output 1
Processor 1
Data Input 2 Data Output 2
Processor 2
Data Input N Data Output 3
Processor N
Multiple-instructions, multiple-data (MIMD)
architecture.
Cache L1 Cache L1
Core 2
IPC Channel IPC Channel
Processor 1 Processor 2 Processor N Processor 1 Processor 2 Processor 2
Memory
Bus Memory Memory Memory
Bus Bus Bus
Global System Memory Local Local Local
Memory Memory Memory
Shared (left) and distributed (right) memory MIMD
architecture
Messages Messages
IPC IPC Large Level
(Processes, Tasks)
Task 1 Task 2 Task N
Shared Shared
function f1() Memory function f2() function fJ()
{…} {…}
Memory {…} Medium Level
Function 1 Function 2 Function J (Threads, Functions)
a[0] = … a[1] = … a[k] = … Fine Level
b[0] = … b[1] = … b[k] = …
(Processor,
Statements Statements Statements Instructions)
Very Fine Level
(Cores, Pipeline,
+ x load Instructions)
Levels of parallelism in an
application
Elements of distributed computing
• General concepts and definitions
Tanenbaumet.al:
A distributed system is a collection of independent
computers that appears to its users as a single coherent
system.
Coulouris et al.:
A distributed system is one in which components
located at networked computers communicate and
coordinate their actions only by passing messages
Elements of distributed computing Contd(1)
• Components of a distributed system
• Architectural styles for distributed computing
– Component (Eg. objects, processes, pipes, and filters) and
connectors (Communication mechanism:
cooperation and coordination among components)
– Software architectural styles
• Data centered architectures
• Data-flow architectures
• Virtual machine architectures
• Call & return architectures
• Architectural styles based on independent components
– System architectural styles
• Client/server
• Peer-to-peer
Frameworks for Applications
distributed
programming
Middleware
IPC primitives for
control and data.
Operating System
Networking and
Parallel Hardware
Hardware
A layered view of a distributed
system.
Social Networks,
Scientific Computing,
Enterprise Applications
Applications (SaaS)
Frameworks for
Cloud Application
Development
Middleware (PaaS)
Virtual hardware,
networking, OS images,
and storage. Hardware and OS (IaaS)
A cloud computing distributed
system.
Client-server
request
Two Tier
(Classic Model)
client response server
Three Tier
client Server/client server
N Tier
server
client Server/client Server/client
server
P2P
peer
peer
peer
peer
peer
peer
peer
Elements of distributed computing Contd(2)
– Models for interprocess communication
• Message-based communication
• Models for message-based communication
– Point-to-point message model(direct
communication and queue-based
communication)
– Publish-and-subscribe message
model
» Push strategy- Publisher NOTIFY
all Subscribers
» Pull strategy- Publisher makes available
the message and Subscriber to check
– Request-reply message model (for each message
sent by a process, there is a reply)
Elements of distributed computing Contd(3)
• Technologies for distributed computing
– Remote procedure call
– Distributed object frameworks
• Object activation and lifetime
• Examples of distributed object frameworks
– Common object request broker architecture (CORBA)
– Distributed component object model(DCOM/COM1)
– Java remote method invocation (RMI)
– .NET remoting
• Service-oriented computing
– What is a service? encapsulates a software component
– Service-oriented architecture (SOA)
– Web services
– Service orientation and cloud computing
Elements of distributed computing Contd(4)
• Service-oriented computing
– What is a service? encapsulates a software component
» 4 Major characteristics
• Boundaries are explicit
• Services are autonomous
• Services share schema and contracts, not class or interface
definitions
• Services compatibility is determined based on policy
– Service-oriented architecture (SOA)
» Standardized service contract
» Loose coupling
» Abstraction
» Reusability
» Autonomy
» Lack of state
» Discoverability.
» Composability.
– Web services
– Service orientation and cloud computing (Web service & Web 2.0
technologies)
RPC
Node A Node B
Main Procedure Procedure Registry
Procedure A Procedure C:Node B
Procedure C
Procedure B RPC Library RPC Service
Program A (RPC Client) Program C (RPC Server)
Parameters Marshaling Return Value Parameters Unmarshaling Return Value
and Procedure Name Unmarshaling and Procedure Name Marshaling
Network
The distributed object programming
model
Node A Node B
Application B
21
10 16
Instance Remote
15
Instance
5: Object
1: Ask for Object Proxy Object Skeleton Activation
Reference
9 11 20 4
17 14 6
Remote Reference Module Remote Reference Module
Applica
tion A 12 7
8 13
19 18 3
2
Network
Web WSDL(s) Web Service
Server
WS Client UDDI Registry
Web WSDL
Server
Application
Web Service
WSDL
WS Client
Application
Application
WSDL- Web Service Definition Language
UDDI- Universal Description Discovery and
Integration
WS technology Stack
WSFL Web Service Flow
Static UDDI Service Discovery
Quality of Service
Direct UDDI Service Publication
Management
WSDL Service Description
Security
SOAP XML-based Messaging
HTTP, FTP,e-mail, MQ, IIOP, …. Network
WSDL- Web Service Definition Language
UDDI- Universal Description Discovery and Integration
SOAP- Simple Object Access Protocol (XML-based protocol for accessing web
services)
SOAP Messages
POST /InStock HTTP/1.1
Host: www.stocks.com
Content-Type: application/soap+xml; charset=utf-8
Content-Length: <Size>
<?xml version=“1.0”>
Envelope
<soap:Envelope xmlns:soap=“http//www.w3.org/2001/12/soap-envelope”
soap:encondingStyle=“http//www.w3.org/2001/12/soap-encoding”>
Header: Metadata & Assertions
<soap:Header></soap:Header>
<soap:Body xmlns:m=http://www.stocks.org/stock>
<m:GetStockPrice>
<m:StockName>IBM<m:StockName>
</m:GetStockPrice>
</soap:Body>
Body: Method Call
</soap:Envelope>
SOAP Messages
POST /InStock HTTP/1.1
Host: www.stocks.com
Content-Type: application/soap+xml; charset=utf-8
Content-Length: <Size>
<?xml version=“1.0”>
Envelope
<soap:Envelope xmlns:soap=“http//www.w3.org/2001/12/soap-envelope”
soap:encondingStyle=“http//www.w3.org/2001/12/soap-encoding”>
Header: Metadata & Assertions
<soap:Header></soap:Header>
<soap:Body xmlns:m=http://www.stocks.org/stock>
<m:GetStockPriceResponse>
<m:Price>34.5<m:Price>
</m:GetStockPriceResponse>
</soap:Body>
Body: Execution Result
</soap:Envelope>
