UNIT 4

ANTHOLOGY

Degree: Computer Systems Engineering

Subject: Computer Architecture

Master: Jorge Ontiveros

Alumno:Cristian Eduardo CavazosTorres
N° de Control:13480853

School Period: Jan-Jun/2016

Unit IV: Parallel Processing

4.1 Basic aspects of parallel computing
Parallel computing is a form of computation in which many instructions are executed.
simultaneously, operating on the principle that large problems can often be
divide into smaller ones, which are then solved simultaneously (in parallel). There are several
different forms of parallel computing: bit-level parallelism, instruction-level parallelism
instruction, data parallelism, and task parallelism. Parallelism has been employed during
many years, especially in high-performance computing, but interest in it has grown
lately due to the physical limitations that prevent the increase in frequency.
As the energy consumption —and consequently the generation of heat— of computers
has become a concern in recent years, parallel computing has become the
dominant paradigm in computer architecture, mainly in the form of processors
multicore. Parallel computers can be classified according to the level of parallelism that
It admits its hardware: equipment with multi-core and multi-processor processors that have multiple
processing elements within a single machine and the clusters, MPPS, and grids they use
various teams to work on the same task. Many times, to speed up specific tasks,
specialized parallel computing architectures are used alongside processors
traditional.
Parallel software programs are harder to write than sequential ones because the
concurrency introduces new types of software errors, with race conditions being the
more common. Communication and synchronization between different subtasks are some of the
largest obstacles to achieving good performance from the parallel program. The maximum
Possible acceleration of a program as a result of parallelization is known as Amdahl's law
Amdahl.

4.2 Types of parallel computing

Bit-level parallelism
Since the advent of large-scale integration (VLSI) as a manufacturing technology
computer chips in the 1970s until around 1986, the acceleration in the
computer architecture was largely achieved by doubling the word size in the
computer, the amount of information that the processor can handle per cycle. The increase in
the size of the word reduces the number of instructions that the processor must execute to
perform an operation on variables whose sizes are greater than the length of the word. For
For example, when an 8-bit processor has to add two 16-bit integers, the processor first
must add the 8 least significant bits of each integer with the addition instruction, to
continuation, add the 8 higher order bits using the addition instruction with carry that
it takes into account the carry bit from the lower order addition, in this case an 8-bit processor
requires two instructions to complete a single operation, where a 16-bit processor
needs a single instruction to complete it.
Historically, 4-bit microprocessors were replaced by 8-bit ones, and then by 16-bit ones.
bits and 32 bits, this general trend came to an end with the introduction of 64-bit processors, which
which has been a standard in general-purpose computing for the last decade.
Instruction-level parallelism
A canonical five-stage pipeline in a RISC machine
(IF = Pedido de Instrucción, ID = Decodificación de instrucción, EX = Ejecutar, MEM = Acceso a la
memory, WB = Writing
A computer program is, essentially, a sequence of instructions executed by a
processor. These instructions can be reordered and combined into groups that are then
executed in parallel without changing the program's outcome. This is known as parallelism
level of education.
Advancements in instruction-level parallelism dominated computer architecture.
from the mid-1980s to the mid-1990s.
Modern processors have multi-stage instruction pipelines.
Each stage in the pipeline corresponds to a different action that the processor performs on the
instruction corresponding to the stage; a processor with a pipeline of N stages can have up to
in different instructions at different stages of completion. The canonical example of a processor
Segmented is a RISC processor, with five stages: fetch instruction, decode, execute,
access to memory and write. The Pentium 4 processor had a 35-stage pipeline.
A superscalar processor with a five-stage pipeline, capable of executing two instructions per
cycle. It can have two instructions in each stage of the pipeline, for a total of up to 10
instructions (shown in green) executed simultaneously.
In addition to instruction-level parallelism of pipelining, some processors can execute
more than one instruction at a time. These are known as superscalar processors.
Instructions can be grouped together only if there is no data dependency between them. The
scoreboarding and the Tomasulo algorithm —which is similar to scoreboarding but makes use of the
renaming records - are two of the most common techniques for implementing execution outside
of order and instruction-level parallelization.
4.2.1 Taxonomy of parallel architectures
The first step towards the parallelization of computer architectures occurs with the
appearance of vector processors or systems. Vector processors extend the
concept of parallelism through segmentation in the processing of large data strings.
Problems. Various definitions for parallel architectures have been proposed.
The difficulty in precisely defining the term is intertwined with the problem of specifying a
taxonomy of parallel architectures. The central problem in order to specify a definition and
consequently the taxonomy for modern parallel architectures is to meet the
next set of imperatives:
Exclude the architectures that incorporate only low-level parallelism mechanisms and that
they have become so popular as a typical feature of modern computers.
Maintain the useful elements of Flynn's classification such as data flows and
instructions.

4.2.2 Architecture of sequential computers

Unlike combinational systems, in sequential systems, the values of the
outputs, at a given moment, do not depend exclusively on the values of the inputs in that
moment, but also from the previous values. The simplest sequential system is the bistable.
Most sequential systems are governed by clock signals. They are
referred to as 'synchronous', as opposed to 'asynchronous' which are
those that are not controlled by clock signals. The main ones are listed below
sequential systems that can be found in the form of integrated circuits or as structures in
programmed systems:
Counter
Records
[Link] Flynn's taxonomy
Probably the most popular classification of computers is Flynn's classification. This
the taxonomy of architectures is based on classification according to the flow of data and
instructions in a system. A flow of instructions is the set of sequential instructions
which are executed by a single processor, and a data flow is the sequential flow of data
requeridos por el flujo de instrucciones.
[Link] Organization of the memory address space
Logical organization
Programs are often organized into modules, some of which may be
shared by different programs, some are read-only and others contain data that
they can modify. Memory management is responsible for handling this logical organization, which
contrasts with the linear physical address space. One way to achieve this is through the
memory segmentation.
Physical organization
Memory is usually divided into high-speed primary storage and secondary storage.
lower speed. The operating system's memory management is responsible for moving the information
between these two levels of memory
4.3 Shared Memory Systems: Multiprocessors
Each processor has its own control unit that executes its own code on its own
data, you can run any application (not just vector programs).
Centralized Shared Memory:
The memory shared by all processors and accessible from anyone.
Decomposed into several modules to allow concurrent access from multiple processors
Each processor must have an addressing space wide enough to
to be able to fully direct it.
Multiprocessor with a shared memory system in which access time varies
depending on the location of the memory word.
The shared memory is physically distributed across all processors (local memories).
set of local memories forms the global addressing space accessible by all
processors. In multiprocessors, each processor usually has an associated local cache and that
introduce the problem of coherence in cache: any local modification of a certain
The position of the shared memory will first be carried out on a local cache, and this can give
place to an incoherent global vision of memory. The elements that integrate a multiprocessor
can be connected to each other through a hierarchical structure of buses. Digital buses
they are the fundamental interconnection systems adopted in commercial systems since
workstations to minicomputers, mainframes, and multiprocessors.
4.3.1 Dynamic or indirect interconnection networks
Features:
Before defining the characteristics of interconnection networks, we will say that a node is called
any of the devices that you want to connect to the network, such as process elements,
memory modules, input/output processors, etc.
Degree of the nodes
Diameter of a net
Bisection width
Network latency
Productivity
Scalability
Symmetry
Connectivity
Classification of Interconnection Networks:
The most important criterion for classifying interconnection networks is based on rigidity.
the links between the nodes: in this regard, networks can be classified as static or
Dynamics. A static network is characterized by its topology being established definitively.
and stable when a system is installed; its only possibility of modification is to grow. For the
On the contrary, a dynamic network can vary in topology well during the course of execution or of the
processes or between the execution of them. On the other hand, networks can be hierarchical or
No, they are formed by a series of levels, with a different number of nodes, within
each of which has symmetry. Most hierarchical networks tend to be static, without
Embargo, there is some type of dynamic topology that can also be.
Dynamic interconnection networks
Dynamic interconnection networks are convenient in cases where one wants a network of
general purpose since they are easily reconfigurable. Also for that reason, this type of Networks
they greatly facilitate scalability. In general, dynamic networks require elements of
specific connections such as bus arbiters, switches, etc. The main
The dynamic network topologies are as follows:
Buses
Crossbar switching networks
Multistage Interconnection Networks or MIN
Omega Networks
baseline networks
Butterfly Networks
Delta Networks
Closs Networks
Benes Networks

[Link] Shared medium networks

Shared media environment
It occurs when multiple hosts have access to the same medium. For example, if several PCs are present
connected to the same physical cable, to the same optical fiber, it is said that they share the same
media environment.
Extended shared media environment
It is a special type of shared media environment in which networking devices
they can expand the environment so that it can include multiple accesses or greater distances of
Wiring. The basic vehicle we use to access our network is the connection of our
computer to the same. It is generally done through cables.
Depending on the cable and its physical characteristics, we can make different connections.
The physical connection between the computer and the network is always established through a port. A
connector allows linking the transmission medium with the network access circuitry. For each
a different port is used in the cabling system and sometimes an accessory device
The cable that has the most projection today is fiber optic, but right now it is expensive and difficult.
to install. However, its use is recommended to link distant networks and to create
very fast links between servers or interconnection of networks.
The three main transmission media used in local networks are:
braided
coaxial cable
fiber optic
[Link] Switched networks
It consists of a set of interconnected nodes, through transmission media,
usually forming a mesh topology, where information is transferred
routing it from the source node to the destination node through switching between intermediate nodes.
A transmission of this type has
3 phases:
. Establishing the connection
. Transfer of information
. Release of the connection
Switching at a node refers to the physical or logical connection of an input path to the node with a
exit path of the node in order to transfer the information that arrives through the first path to the
Second. The switched networks are the wide area networks.
Switched networks are divided into:
Packet switching
Circuit switching
Packet switching:
It is a method of sending data over a network of computers. A packet is a group of
information that consists of two parts: the data itself and the control information, which
indicates the route to follow along the network to the packet's destination. There is an upper limit for
the size of the packages; if it exceeds, it is necessary to divide the package into smaller ones.
Advantages:
The packets form a queue and are transmitted as fast as possible.
They allow the conversion of data speed.
The network can continue to accept data even if the transmission is slow.
Is there a possibility to manage priorities (if a group of information is more important
than the others, will be broadcast before those others.
Circuit switching:
It is a type of connection that different nodes of a network make to achieve an appropriate path.
to connect two users of a telecommunications network.
Unlike what happens in packet switching, in this type of switching it
establish a dedicated communication channel between two stations. Resources are reserved for
transmission and switching of the network for exclusive use in the circuit during the connection. This
it is transparent: once established it seems as if the devices were really
connected.
Advantages
The bandwidth is defined and remains constant during communication.
The circuit is fixed, no time is wasted in routing the information.
The transmission takes place in real time, being useful for voice and video communication.
Although there is a delay in establishing the call, the transmission delay
the posterior is negligible; if the traffic generally occurs between the same pair of
stations can be faster.
4.3.2 Cache coherence
Cache coherence refers to the integrity of the data stored in the caches.
locales of the shared resources. Cache coherence is a special case of coherence.
by heart.
Multiple caches with common resources.
When the clients of a system, particularly the CPUs in a multiprocessor, maintain caches.
de una memoria compartida, los conflictos crecen. Haciendo referencia al dibujo, si el cliente de
the top has a copy of a block of memory from a previous read and the client below changes
that block, the client above could be working with erroneous data, without being aware of it
of it. The coherence of the cache tries to manage these conflicts and maintain consistency between
the caches and the memory.
4.4 Distributed memory systems. Multicomputers:
Clusters
A cluster is a type of distributed parallel architecture that consists of a set of
independent (and initially low-cost) interconnected computers operating in a way
combined as a single computational resource
However, each computer can be used independently or separately.
4.4.1 Static interconnection networks
4.4.2 Cluster
The term cluster (from the English cluster, "group" or "bunch") applies to sets or conglomerates.
of computers built using common hardware and that behave
as if they were a single computer. Cluster technology has evolved in support of
activities ranging from supercomputing applications and critical mission software, servers
web and e-commerce, to high-performance databases, among other uses.
Cluster computing arises as a result of the convergence of several current trends.
which include the availability of high-performance economical microprocessors and high-speed networks
speed, the development of software tools for high-performance distributed computing,
as well as the growing need for computational power for applications that require it.
Simply put, a cluster is a group of multiple computers connected by a high-speed network.
speed, in such a way that the set is seen as a single computer, more powerful than the
common desk.
Clusters are usually used to improve performance and/or availability by
on top of that provided by a single computer typically being more economical than
individual computers with comparable speed and availability.
A cluster is expected to present combinations of the following services:
High performance
2. High availability
3. Load balancing
4. Scalability
4.4.3 Cluster Programming
Parallel programming: these clusters are designed and optimized to run programs
parallels. In this case, the programs must be made specifically to work in
parallel form.
Typically, these programs are models that require performing a large number of calculations.
numerical. The advantage of programming them this way and running them in a cluster is that they are reduced
drastically reducing processing times. In the case of weather models used to predict
The time is obviously the need to run them in minimal time.
When a model is programmed on a multiprocessor platform (a machine with more than one
processor), it is necessary to use parallel programming schemes. The libraries (MPI) are the
that allow task parallelization. In the case of SCALI clusters, porting programs made with
MPI libraries are straightforward thanks to the use of SCAMPI libraries.

The interconnection systems used between nodes in this type are extremely important.
clusters. SCI is an international standard (IEEE1596) for high-speed interconnections.
Dolphin Interconnect Solutions manufactures a variety of SCI products, among which are
they find the SCI-PCI adapter cards that SCALI uses in its clusters. The performance of
these cards are amazing: several hundred megabytes per second and latency times
lower than a microsecond in the SCI layer reaching the limits of the PCI bus (64bits/66Mhz).
Uses:
Structural Analysis
Fluid mechanics simulations
Genomic models
Weather forecast

And the study of any phenomenon that can be modeled mathematically.

4.4.4 Considerations on the performance of clusters
A high-performance cluster is a set of computers designed to provide high
performance in terms of computational power. The reasons for using a high cluster
performance are:
The size of the problem to be solved
The price of the machine needed to solve it.
Through a cluster, it is possible to achieve computational capabilities superior to those of a
computer more expensive than the total cost of the computers in the cluster.
An example of very cheap clusters are those being carried out in some universities with
personal computers discarded as 'outdated' that manage to compete in capability of
calculation with very expensive supercomputers.

To ensure this computing capability, problems need to be parallelizable, since the

the method by which clusters expedite processing is by dividing the problem into smaller problems
small ones and calculate them at the nodes, therefore, if the problem does not meet this characteristic,
the cluster cannot be used for its calculation.
For a problem to be parallelizable, special libraries such as this one must be used.
PVM (parallel virtual machine) or MPI (Message Passing Interface), where the former is used
especially in clusters with heterogeneous nodes (processor architecture, operating systems,
among others), and belonging to different network domains, the second library used for clustering
homogeneous
A type of software for creating high-performance clusters is OSCAR (Open Source Cluster)
Application Resources) distributed under GPL license. This software works on the system
Linux operation. In Windows, 'WCC 2003' (Windows Computer Cluster) could be used.