Parallel Processing Fundamentals

Parallel Processing

• Execution of concurrent events in the computing process to achieve faster computational speed
• Purpose is to increase throughput, i.e., the amount of processing that can be accomplished in a given interval of time
• Levels of parallel processing:
  • Bit-level
  • Instruction-level
  • Procedure-level
  • Program-level
• Examples: shift register, register with parallel load, multiplicity of functional units performing identical or different operations

Flynn's Classification of Parallel Computers

• Based on the multiplicity of instruction streams and data streams
• Instruction stream: sequence of instructions read from memory
• Data stream: operations performed on data in the processor
• Classification:
  • SISD (Single Instruction Stream, Single Data Stream)
  • SIMD (Single Instruction Stream, Multiple Data Streams)
  • MISD (Multiple Instruction Streams, Single Data Stream)
  • MIMD (Multiple Instruction Streams, Multiple Data Streams)

SISD

• Single computer containing control unit, processor, and memory unit
• Instructions and data stored in memory, executed sequentially
• May or may not have parallel processing
• Parallel processing can be achieved by pipelining

SIMD

• Only one copy of the program exists
• A single controller executes one instruction at a time
• Data bus, control unit, and multiple processor units
• Alignment network and multiple memory modules

MISD

• No computer classified as MISD currently exists

MIMD

• Multiple processing units
• Execution of multiple instructions on multiple data
• Types:
  • Shared memory multiprocessors
  • Message-passing multi-computers

Pipelining

• Technique to decompose a sequential process into sub-operations
• Each sub-process is executed in a dedicated segment, operating concurrently
• Result of each segment is transferred to the next segment
• Final result obtained after data passes through all segments

Design of a Basic Pipeline

• In a pipelined processor, a pipeline has two ends: input and output
• Multiple stages/segments between ends, with output of one stage connected to input of next stage
• Interface registers (latch or buffer) hold intermediate output between stages
• All stages controlled by a common clock
• Example of a 5-stage RISC pipeline:
  • Stage 1: Instruction Fetch
  • Stage 2: Instruction Decode
  • Stage 3: Instruction Execute
  • Stage 4: Memory Access
  • Stage 5: Write Back

Overview of Central Processing Unit (CPU)

• Introduction to CPU architecture
• Components: General Register Organization, Stack Organization, Instruction Formats, Addressing Modes, Data Transfer and Manipulation, Program Control and Program Interrupt, and Reduced Instruction Set Computer

Major Components of CPU

• Storage Components: Registers, Flags
• Execution (Processing) Components: Arithmetic Logic Unit (ALU)
  • Performs arithmetic calculations, logical computations, and shifts/rotates
• Transfer Components: Bus
• Control Components: Control Unit

Registers

• In basic computers, there is only one general-purpose register, the Accumulator (AC)
• In modern CPUs, there are many general-purpose registers
• Advantages of having many registers include:
  • Fast transfer between registers within the processor
  • Slower access to memory

General Register Organization

• Registers: R1-R7
• Clock and Input components
• Load component connected to MUX (SELA and SELB)
• Decoder and ALU components

Operation of Control Unit

• Directs information flow through ALU by selecting components and functions
• Example: R1 <- R2 + R3
  • MUX A selector (SELA): BUS A <- R2
  • MUX B selector (SELB): BUS B <- R3
  • ALU operation selector (OPR): ALU to ADD
  • Decoder destination selector (SELD): R1 <- Out Bus

Control Word Encoding

• 3 bits for SELA, SELB, and SELD
• 5 bits for OPR
• Encoding of register selection fields and ALU operations

ALU Control

• Encoding of ALU operations (OPR)
  • Transfer A (TSFA), Increment A (INCA), ADD A + B (ADD), Subtract A - B (SUB), Decrement A (DECA), AND A and B (AND), OR A and B (OR), XOR A and B (XOR), Complement A (COMA), Shift Right A (SHRA), and Shift Left A (SHLA)
• Examples of ALU microoperations:
  • R1 <- R2 - R3
  • R4 <- R4 OR R5
  • R6 <- R6 + 1
  • R7 <- R1
  • Output <- R2
  • Output <- Input
  • R4 <- shl R4

This quiz covers the basics of parallel processing, including pipelining, multiprocessors, interconnection structures, and interprocessor communication and synchronization.