|
Unit 5 |
||||||||||||||||||||||||||||||||||||||||||||||||||
A parallel
programming model is a concept that enables the expression of parallel
programs which can be compiled and executed. The value of a programming model
is usually judged on its generality: how well a range of different problems
can be expressed and how well they execute on a range of different
architectures. The implementation of a programming model can take several
forms such as libraries invoked from traditional sequential languages,
language extensions, or complete new execution models. Classifications of
parallel programming models can be divided broadly into two areas: process
interaction and problem decomposition. 1. Process interaction Process interaction
relates to the mechanisms by which parallel processes are able to communicate
with each other. The most common forms of interaction are shared memory and
message passing, but it can also be implicit. Shared memory In a shared memory
model, parallel tasks share a global address space which they read and write
to asynchronously. This requires protection mechanisms such as locks and
semaphores to control concurrent access. Shared memory can be emulated on
distributed-memory systems but non-uniform memory access (NUMA) times can
come in to play. Message passing In a
message passing model, parallel tasks exchange data through passing messages
to one another. These communications can be asynchronous or synchronous. The
Communicating Sequential Processes (CSP) formalisation of message-passing
employed communication channels to 'connect' processes, and led to a number
of important languages such as Joyce, occam and Erlang. Implicit In an implicit
model, no process interaction is visible to the programmer, instead the
compiler and/or runtime is responsible for performing it. This is most common
with domain-specific languages where the concurrency within a problem can be
more prescribed. 1. Problem
decomposition
Any parallel
program is composed of simultaneously executing processes, problem
decomposition relates to the way in which these processes are formulated.
This classification may also be referred to as algorithmic skeletons or parallel programming paradigms. Task
parallelism
A task-parallel
model focuses on processes, or threads of execution. These processes will
often be behaviorally distinct, which emphasizes the need for communication.
Task parallelism is a natural way to express message-passing communication.
It is usually classified as MIMD/MPMD or MISD. Data
parallelism
A data-parallel
model focuses on performing operations on a data set which is usually
regularly structured in an array. A set of tasks will operate on this data,
but independently on separate partitions. In a shared memory system, the data
will be accessible to all, but in a distributed-memory system it will divided
between memories and worked on locally. Data parallelism is usually
classified as SIMD/SPMD. In a shared
memory model, parallel tasks share a global address space which they read and
write to asynchronously. This requires protection mechanisms such as locks
and semaphores to control concurrent access. Shared memory can be emulated on
distributed-memory systems but non-uniform memory access (NUMA) times can
come in to play. Shared memory
model – read remote memory via an expression – write remote memory through assignment • Manipulating shared data may require synchronization • Does not allow locality exploitation [RGPV JUN 14 ,15(7)]
In a message passing model, parallel tasks exchange
data through passing messages to one another. These communications can be
asynchronous or synchronous. The Communicating Sequential Processes (CSP)
formalisation of message-passing employed communication channels to 'connect'
processes, and led to a number of important languages such as Joyce, occam
and Erlang. Detail: ·
Programmers control data and work
distribution ·
Explicit communication ·
Significant communication overhead
for small transactions These communications can be asynchronous or synchronous. The
Communicating Sequential Processes (CSP) formalization of message-passing
employed communication channels to 'connect' processes, and led to a number
of important languages such as Joyce, occam and Erlang. Example: MPI Data Parallel Model A data-parallel model focuses on performing operations on a data set
which is usually regularly structured in an array. A set of tasks will
operate on this data, but independently on separate partitions. In a shared
memory system, the data will be accessible to all, but in a
distributed-memory system it will divided between memories and worked on
locally. Data parallelism is usually classified as SIMD/SPMD. Data parallel model is:
In a shared memory system, the data will be accessible to all, but in
a distributed-memory system it will divided between memories and worked on
locally. Data parallelism is usually classified as SIMD/SPMD
References{Advance Computer Architecture,Kai Hwang}
Object
Oriented Model
[RGPV JUN 14(7)] The
object-oriented model is based on a collection of objects, like the E-R
model. ·
An object contains values stored in instance
variables within the object. ·
Unlike the record-oriented models, these values
are themselves objects. ·
Thus objects contain objects to an arbitrarily
deep level of nesting. ·
An object also contains bodies of code that
operate on the the object. ·
These bodies of code are called methods. ·
Objects that contain the same types of values and
the same methods are grouped into classes. The
object-oriented model is based on a collection of objects. o
An object contains values stored in instance
variables within the object. o
Unlike the record-oriented models, these values
are themselves objects. o
Thus objects contain objects to an arbitrarily
deep level of nesting. o
An object also contains bodies of code that
operate on the the object. o
These bodies of code are called methods. o
Objects that contain the same types of values and
the same methods are grouped into classes. o
A class may be viewed as a type definition for
objects. o
Analogy: the programming language concept of an
abstract data type. o
The only way in which one object can access the
data of another object is by invoking the method of that other object. o
This is called sending a message to
the object. o
Internal parts of the object, the instance
variables and method code, are not visible externally. o
Result is two levels of data abstraction. For
example, consider an object representing a bank account. o
The object contains instance
variables number and balance. o
The object contains a
method pay-interest which adds interest to the balance. o
Under most data models, changing the interest
rate entails changing code in application programs. o
In the object-oriented model, this only entails a
change within the pay-interest method. Unlike
entities in the E-R model, each object has its own unique identity, independent
of the values it contains: o
Two objects containing the same values are
distinct. o
Distinction is created and maintained in physical
level by assigning distinct object identifiers.
References{Advance Computer Architecture,Kai Hwang}
[RGPV DEC 14(7),JUN15(3)] A function
model or functional
model in systems
engineering and software
engineering is a structured representation of
the functions (activities, actions, processes, operations)
within the modeled system or
subject area. A logic model is a diagrammatic
representation of a program A logic model provides a graphic depiction of the
relationship between the main strategies of a program and associated goals,
objectives, population(s) of interest, indicators and resources. A function
model, also called an activity model or process
model, is a graphical representation of an enterprise's
function within a defined scope. The purposes of the function model are to
describe the functions and processes, assist with discovery of information
needs, help identify opportunities, and establish a basis for determining
product and service costs. Functional
perspective In systems
engineering and software
engineering a function model is created with a
functional modeling
perspective. The functional perspective is one of the
perspectives possible in business
process modeling, other perspecifives are for example behavioral,
organizational or informational. A functional
modeling perspective concentrates on describing the dynamic
process. The main concept in this modeling perspective is
the process, this could be a function, transformation, activity, action, task
etc. A well-known example of a modeling language employing this perspective is data flow diagrams. The perspective uses four symbols to describe a process, these being:
Now, with these symbols, a process can be represented as a network of
these symbols. This decomposed process is a DFD, data flow diagram. In Dynamic
Enterprise Modeling a division is made in
the Control model,
Function Model, Process model and Organizational model. Functional decomposition Functional
decomposition refers broadly to the process of resolving
a functional relationship
into its constituent parts in such a way that the original function can be
reconstructed from those parts by function
composition. In general, this process of decomposition is
undertaken either for the purpose of gaining insight into the identity of the constituent components, or for the
purpose of obtaining a compressed representation of the global function, a
task which is feasible only when the constituent processes possess a certain
level of modularity. Functional decomposition has
a prominent role in computer
programming, where a major goal is to modularize processes to the
greatest extent possible. For example, a library management system may be
broken up into an inventory module, a patron information module, and a fee
assessment module. In the early decades of computer programming, this was
manifested as the "art of subrouting," as it was called by some
prominent practitioners. Use of Logic Models Logic models are a useful way of helping stakeholders understand the
overall structure and function of a
program (i.e., the "big picture"). As such, logic models are a
useful resource for program planning and evaluation. A well-developed logic model is like a
useful road map: it defines boundaries, highlights important features, and
shows clearly marked "pathways". Logic Models Support Program Planning Logic models are a valuable resource for program planning.
Specifically, logic models contribute to effective program planning by:
Logic models also guide the development of program evaluations:
References{Advance Computer Architecture,Kai Hwang}
Concurrent programming is a computer
programming technique that provides for the execution of operations
concurrently - either within a single computer, or across a number of
systems. In the latter case, the term distributed computing is used.
Multiprocessor machines achieve better performance by taking advantage of
this kind of programming. In
parallel programming, single tasks are split into a number of subtasks that
can be computed relatively independently and then aggregated to form a single
coherent solution. Parallel programming is most effective for tasks that can
easily broken down into independent tasks such as purely mathematical
problems, e.g., factorization. Parallel
computing is a
form of computation in which many calculations are carried out
simultaneously, operating on the principle that large problems can often
be divided into smaller ones, which are then solved concurrently ("in parallel").
There are several different forms of parallel computing: bit-level,instruction
level, data, and task parallelism. Parallelism has been employed for many years,
mainly in high-performance computing, but interest in it has grown
lately due to the physical constraints preventing frequency scaling. As power consumption (and
consequently heat generation) by computers has become a concern in recent
years, parallel computing has become the dominant paradigm in computer architecture, mainly in the form of multicore processors. Parallel
computers can be roughly classified according to the level at which the
hardware supports parallelism, with multi-core and multi-processor computers having multiple
processing elements within a single machine, while clusters,MPPs, and grids use multiple computers to
work on the same task. Specialized parallel computer architectures are
sometimes used alongside traditional processors, for accelerating specific
tasks. Parallel computer programs are more difficult to write
than sequential ones, because concurrency introduces several new classes
of potential software bugs, of which race conditions are the most common. Communication and synchronization between the different
subtasks are typically some of the greatest obstacles to getting good
parallel program performance. Parallel
Compilers help accelerate the software development process by compiling code
quickly and efficiently. Take a closer look at the anatomy of a compiler and
the techniques used to 'parallel-ize' it. With the advent of multi-processor
machines researchers have tried to exploit parallelism in other wise serial
programs to obtain speed advantage. Various techniques have been developed
like vectorization and dependency graph analysis in order to extract
parallelizable segments in a piece of code written for a serial compiler. Computer software that translates (compiles) source code written
in a high-level language (e.g., C++) into a set of machine-language instructions that can be
understood by a digital computer's CPU. Compilers are very large programs, with error-checking and other
abilities. Some compilers translate high-level language into an
intermediate assembly language, which is then translated
(assembled) into machine code by an assembly program or assembler. Other
compilers generate machine language directly. .
[RGPV JUN 14,DEC
14(7)] To implement a parallel algorithm you need to construct a
parallel program. The environment within which parallel programs are
constructed is called the parallel
programming environment. Programming environments correspond roughly
to languages and libraries, as the examples below illustrate -- for example,
HPF is a set of extensions to Fortran 90 (a "parallel language", so
to speak), while MPI is a library of function calls There are hundreds of parallel programming environments.
To understand them and organize them in a meaningful way, we need to sort
them with regard to a classification scheme. In this note, we organize
programming environments in terms of their core programming models. This is a
complicated way to sort parallel programming environments, since a single
programming environment can be classified under more than one programming
model (for example, the Linda coordination language can be thought of in terms
of a distributed-data-structure model or a coordination model). Formal models Some programming environments are defined in terms of
detailed, formal theories. These programming environments provide guarantees
that less formal approaches can't make. For example, it is possible to build
programming environments that are deterministic and that strictly preserve a
program's sequential semantics. Unfortunately, formal programming
environments use language constructs that are unfamiliar to traditional
programmers, which makes for a barrier to their use. Logic programming models Programming environments based on logic programming use
declarative as opposed to imperative semantics. The most common approaches
are based on Prolog's first-order predicate calculus. Concurrency is included
in one of three ways: and-parallelism (execute multiple
predicates), or-parallelism (execute multiple guards), or through
explicit mapping of predicates linked together through single assignment
variables.
Functional programming models Functional programming languages use declarative semantics
and some form of lambda calculus to express the operation of a program. LISP
is perhaps the oldest and best known of the functional languages. With pure
functional languages, there are no side effects from a function. Hence,
executing functions as soon as the required data is available provides a
natural way to achieve concurrent execution.
Compositional models These models are based on explicitly distinguishing among
ways in which programs can be composed (put together to form larger
programs). In our context, the most pertinent forms of composition are
sequential (in which programs execute in sequence) and parallel (in which
programs execute "concurrently", where concurrent execution is
frequently modeled as interleaved execution of the elements of the
composition).
The demand for faster and more efficient computer systems
for both scientific and commercial applications has grown considerably in
recent times. Physical limitations and high costs make it impossible to
increase processor speed beyond certain limits. To overcome these
difficulties, new architectures emerged introducing parallelism in computing
systems. Currently, different types of high performance machines based on the
integration of many processors are available. Among these, some of the most
important are (Lau 1996): vector multiprocessors (a small number of high
performance vector processors); massively parallel processors (hundreds to
millions of processors connected together with shared or distributed memory);
and networked computers (workstations connected by a medium or high speed
network, working as a high performance virtual parallel machine). Parallel programming tools Many programming tools are available for the implementation
of parallel programs, each of them being more suitable for some specific
problem type. The choice of the parallel programming tool to be used depends
on the characteristics of each problem to be solved. Some tools are better
e.g. for numerical algorithms based on regular domain decomposition, while
others are more appropriate e.g. for applications that need dynamic spawning
of tasks and irregular data structures. Many parallel programming tools have
been proposed, and it would be impossible to survey all of them in this
paper. We have chosen a few tools which are currently in a stable state of
development and have been used in a number of applications, being
representative of different programming paradigms. PVM PVM (Parallel
Virtual Machine) is a widely used message passing library,
created to support the development of distributed and parallel programs
executed on a set of interconnected heterogeneous machines. A PVM program
consists of a set of tasks that communicate within a parallel virtual machine
by exchanging messages. A configuration file created by the user defines the
physical machines that comprise the virtual machine. A managing process
executes on each of these machines and controls the sending and receiving of
messages among them. There are subroutines for process initialization and
termination, for message sending and receiving, for group creation, for
coordinating communication among tasks of a group, for task synchronization,
and for querying and dynamically changing the configuration of the parallel
virtual machine. The application programmer writes a parallel program by
embedding these routines into a C, C++, or FORTRAN code. MPI MPI (Message
Passing Interface) is a proposal for the standardization of a message
passing interface for distributed memory parallel machines. The aim of this
standard is to enable program portability among different parallel machines.
It just defines a message passing programming interface, not a complete
parallel programming environment. For this reason, it does not handle issues
such as parallel program structuring, and debugging. It does not provide any
definition for fault tolerance support and assumes that the computing
environment is reliable.
These routines can be activated in two basic modes:
blocking or non-blocking. Three communication modes are available: ready (a
process can only send a message if there is a corresponding reception
operation initiated); standard (a message can be sent even if there is no
reception operation for it), and synchronous (similar to the standard mode,
but with a sending operation considered as completed only after its
destination processor initiates a reception operation). The selection of the
mode to be used depends on the type of communication needs of the application
and can have a great influence in the efficiency of the parallel program.
Group communication routines are defined to coordinate the communication
among tasks belonging to a predefined group of processors. |