Parallel Processing

MEANING

Parallel processing (parallel processing) is the use of more than one CPU to execute a program simultaneously.

Ideally, parallel processing makes the program run faster as more CPUs are used.

GOAL

The main goal of parallel processing is to increase computing performance. The more things can be done simultaneously (in the same time), the more work that can be accomplished.

PARALLEL PROCESSING

parallel computing

Parallel computing is one technique to compute simultaneously using several computers simultaneously.

Normally required when the required capacity is very large, either because they have to process large amounts of data or due process demands a lot of computing.

To perform various types of parallel computing its necessary infrastructure parallel machine consisting of many computers connected to the network and able to work in parallel to solve a problem. It is necessary for various support software commonly referred to as middleware that acts to regulate the distribution of jobs among nodes in a single parallel machine. Furthermore, users must make parallel programming to realize the computation.

Parallel Programming itself is a computer programming technique that allows the execution of commands / operations concurrently. When computers are used simultaneously by separate computers connected in a network of computers, usually called distributed systems. A popular programming language used in parallel programming is MPI (Message Passing Interface) and PVM (Parallel Virtual Machine).

The thing to remember is parallel computing is different from multitasking. the meaning of multitasking is a computer with a single processor to execute multiple tasks simultaneously. While some people are struggling in the area of ​​operating systems assume that a single computer can not do multiple jobs at once, but the process of scheduling a pass off to the operating system make such computer tasks simultaneously. While parallel computing has been described previously, that parallel computing using multiple processors or computers. Besides not using parallel computing Von Neumann architecture.

To clarify more about the differences in a single computing (using one processor) and parallel computing (using multiple processors), then we must know in advance the understanding of the model of computation. There are 4 models of computing are used, namely:

1. SISD

2. SIMD

3. MISD

4. MIMD

1. SISD

Which stands for Single Instruction, Single Data is the only one to use the Von Neumann architecture. This is Because the models is only used one processor only. Therefore, this models can be regarded as a model for a single computation. While the other three models is parallel computing using multiple processors. Some examples of using computer models are SISD UNIVAC1, IBM 360, CDC 7600, Cray 1 and PDP 1.

2. SIMD

Which stands for Single Instruction, Multiple Data. SIMD processor to use many of the same instructions, but each processor to process different data. For example we want to find the number 27 in the series of numbers consists of 100 digits, and we use 5 processor. On each processor we use the same algorithm or command, but the data are processed differently. For example, processor 1 process data from sequence / order of the first to rank 20, second processor to process data from sequence 21 to sequence 40, so even for processor-processor to another. Several examples of SIMD computer model is ILLIAC IV, MasPar, Cray X-MP, Cray Y-MP, Thinking Machine CM-2 and the Cell processor (GPU).

3. MISD

Which stands for Multiple Instruction, Single Data. MISD uses many processors with each processor using different instructions, but to process the same data. This is the opposite of the model of SIMD. For example, we can use the same case on the SIMD model of example but a different way of settlement. At MISD when the computer first, second, third, fourth and fifth both process the data of the order of 1-100, but the algorithms used to search for different techniques on each processor. Until now there is no computer model of MISD.

4. MIMD

Which stands for Multiple Instruction, Multiple Data. MIMD uses many processors with each processor has different instructions and different data processing. But many computers using MIMD models also include components for SIMD models. Some models use MIMD computer is an IBM POWER5, HP / Compaq AlphaServer, Intel IA32, AMD Opteron, Cray XT3 and IBM BG / L.

In short for the difference between a single computing parallel computing, can be illustrated in the figure below:

Settlement Issues in Computing A Single

A Settlement Issues in Parallel Computing

From the difference between the two images above, we can conclude that the performance of parallel computing is more effective and can save time for data processing than a single computing.

From the explanations above, we can get the answers to why and when we need to use parallel computing. The answer is that parallel computing is much more time-saving and highly effective when we have to process large amounts of data. However, the effectiveness is lost when we only process small amounts of data, because the data with a small amount or a little more effective if we use a single computing.

Parallel computing requires:

· algorithms

· Programming language

· compiler

Parallel programming is a computer programming technique that allows the execution of commands / operations simultaneously in both the computer with one (single processor) or multiple (dual processors with parallel machines) CPU.

The main goal of parallel programming is to increase computing performance.

* Message Passing Interface (MPI)

MPI is a programming standard that allows programmers

to create an application that can run in parallel.

MPI provides functions for exchanging

between messages. Uses MPI else is

1. write parallel code is portable

2. get high performance in parallel programming, and

3. face problems involving irregular or dynamic data relationships that are not

so suited to parallel data model.

Relationship between Modern Computing with Parallel Processing

The relationship between modern computing and parallel processing are related, because the use of a computer or computing is now considered to be much faster than the settlement of the problem manually. With such improved computing performance or processes are increasingly applied, and one way is to increase the speed of the hardware. Where is the main component in the computer is the processor hardware. While parallel processing is the use of multiple processors (or multiprocessor computer architecture with many processors) for faster computer performance.

Computational performance by using parallel processing and utilize it using several computers or CPUs to find a solution to the problem of the problem. So it can be resolved quickly instead of using one computer. Computing with parallel processing will combine multiple CPUs, and divide the tasks for each of these CPUs. So, the problem is divided completion. But this is a big issue only, the problem of computing a smaller, cheaper one CPU only.

Memory Organization

Memory-Internal storage areas in the computer. The term memory identifies datastorage that comes in the form of chips, and the word storage is used for memory that exists on tapes or disks. Moreover, the term memory is usually used as a shorthand for physical memory, which refers to the actual chips capable of holding data. Some computers also use virtual memory, which expands physical memory onto a hard disk.
Every computer comes with a certain amount of physical memory, usually referred to as main memory or RAM. You can think of main memory as anarray of boxes, each of which can hold a single byte of information. A computer that has 1 megabyte of memory, therefore, can hold about 1 million bytes (orcharacters) of information.


1.0 Types of Memory

•  RAM (random-access memory): This is the same as main memory. When used by itself, the term RAM refers to read and writememory; that is, you can both write data into RAM and read data from RAM. This is in contrast to ROM, which permits you only to read data. Most RAM is volatile, which means that it requires a steady flow of electricity to maintain its contents. As soon as the power is turned off, whatever data was in RAM is lost.

•  ROM (read-only memory): Computers almost always contain a small amount of read-only memory that holds instructions for starting up the computer. Unlike RAM, ROM cannot be written to.

•  PROM (programmable read-only memory): A PROM is a memory chip on which you can store a program. But once the PROM has been used, you cannot wipe it clean and use it to store something else. Like ROMs, PROMs are non-volatile.

•  EPROM (erasable programmable read-only memory): An EPROM is a special type of PROM that can be erased by exposing it to ultraviolet light.

•  EEPROM (electrically erasable programmable read-only memory):An EEPROM is a special type of PROM that can be erased by exposing it to an electrical charge.

2.0 Cache Memories
 Cache memories are small, fast SRAM-­‐based Memories managed automatically in hardware.
 Hold Frequently accessed blocks of main memory
 CPU Looks first for data in caches.
 Typical system structure:

General Cache Organizationon (S,E,B)

Cache Read

Example:Direct Mapped Cache (E=1)

Direct mapped: One Line per set

Assume: Cache block size 8 bytes

Example:Direct Mapped Cache (E=1)

Direct mapped: One Line per set

Assume: Cache block size 8 bytes

3.0 Types of External Memory

• Magnetic Disk

— Floppy

— Winchester

— RAID

— Removable

• Optical

— CD-ROM

— CD-Writable (WORM)

— CD-R/W

— DVD

• Magnetic Tape

Magnetic Disk

• Disk substrate coated with magnetizable material (iron oxide…rust)

• Substrate used to be aluminium

• Now glass

— Improved surface uniformity

– Increases reliability

— Reduction in surface defects

– Reduced read/write errors

— Lower flight heights (See later)

— Better stiffness

— Better shock/damage resistance

• Range of packaging

— Floppy (PC’s A: drive, B: drive)

— Winchester hard disk (PC’s C: drive)

— Removable hard disk

Floppy Disk

• 8”, 5.25”, 3.5”

• Small capacity

— Up to 1.44Mbyte (2.88M never popular)

• Slow

• Universal

• Cheap

Optical Storage CD-ROM

• Originally for audio

• 650Mbytes giving over 70 minutes audio

• Polycarbonate coated with highly reflective coat, usually aluminium

• Data stored as pits

• Read by reflecting laser

• Constant packing density

• Constant linear velocity

Magnetic Tape

• First kind of secondary memory

• Serial access

• Slow

• Very cheap

• Backup and archive

4.0 Data Organization and Formating

Disk Geometry

Disk Geometry (Muliple-Platter View)

Disk Operation (Single-Platter View)

Disk Operation (Multi-Platter View)

Input/Output

INPUT and OUTPUT

Definition:

•A bus is a shared communication link, which uses one set of wires to connect multiple subsystems.

• I/O is very much architecture/system dependent

• I/O requires cooperation between

  – processor that issues I/O command (read, write etc.)

  -  buses that provide the interconnection between processor, memory      and I/O devices

  – I/O controllers that handle the specifics of control of each device and      interfacing

  – devices that store data or signal events


TYPE AND CHARACTERISTIC OF INPUT/OUTPUT:

Input devices

-Keyboard :  The data and instructions are input by typing on the keyboard. The          message typed on the keyboard reaches the memory unit of a computer.

-Mouse      :   It’s a pointing device. The mouse is rolled over the mouse pad, which in         turn controls the movement of the cursor in the screen.

• Output devices

-Speaker :    High definition, or low distortion, to create a dynamic impact.

-Printer :      Produces a representation of an electronic document on physical media


Example of Input/Output :

qInput devices              qOutput devices

keyboard:-                    Speaker:-

Mouse:-                     Printer:-

HANDLING I/O INTERRUPT:

• Interrupts: alternative to polling

  - I/O device generates interrupt when status changes, data   ready

  - OS handles interrupts just like exceptions (e.g., page faults)

  - Identity of interrupting I/O device recorded in ECR

• I/O interrupts are asynchronous

  - Not associated with any one

  - Don’t need to be handled immediately

• I/O interrupts are prioritized

  - Synchronous interrupts (e.g., page faults) have highest priority

  - High-bandwidth I/O devices have higher priority than low

INTERRUPT OVERHEAD:

• Parameters

  - 500 MHz CPU

  - Interrupt handler takes 400 cycles

  - Data transfer takes 100 cycles

  - 4 MB/s, 16 B interface disk transfers data only 5% of         time

• Data transfer (x) time

  0.05 * (4M B/s)/(16 B/xfer)*[(100 c/xfer)/(500M c/s)] =           0.25%

• Overhead for polling?

  (4M B/s)/(16 B/poll) * [(400 c/poll)/(500M c/s)] = 20%

• Overhead for interrupts?

  + 0.05 * (4M B/s)/(16 B/poll) * [(400 c/poll)/(500M c/s)] =    1%