CSE-211_Part_6

Topics Covered: Vector Processors • Single Instruction Multiple Data (SIMD) Instruction Set Extensions • Graphics Processing Units (GPU)

Vector Processors:

Definition:
A vector processor is a type of CPU designed to handle vector operations. These processors are optimized for executing operations on vectors (arrays of data) rather than scalar operations on individual data points.

Key Features of Vector Processors:

• Vector Operations: Vector processors can perform the same operation on multiple data elements simultaneously. For example, adding two vectors element by element in one instruction.
• Wide Vector Registers: Vector processors use wide registers (e.g., 128 bits, 256 bits, or more) to hold multiple data elements, allowing parallel processing.
• Pipelining: Vector processors use pipelines to efficiently process large amounts of data, ensuring that data is processed as it becomes available without waiting for the previous data to be fully processed.

Example:

• A vector processor may perform operations such as:
  • Vector addition: A[i] = B[i] + C[i]
  • Matrix multiplication: Elements of a matrix are stored in vector registers for parallel processing.

Use Cases:

• Scientific computing, simulations, and tasks involving large datasets, like climate modeling, image processing, and numerical simulations.

---

Key Takeaways:

1. Scalar Processing:
   Each iteration processes one element, leading to higher loop overhead due to instruction fetching and control dependencies.

2. Vector Processing:
   If the same task were implemented on a vector processor, a single vector instruction could replace the loop, improving efficiency by operating on multiple elements simultaneously.

Vectorized Implementation (Conceptual):

c

// Vectorized instruction (hypothetical assembly) LOADV V1, A # Load vector A into V1 LOADV V2, B # Load vector B into V2 MULVV V3, V1, V2 # Multiply vectors V1 and V2, result in V3 STOREV V3, C # Store vector result to C




Basic Vector Execution Example

Scenario:

We are performing element-wise multiplication for V3 ← V1 × V2. The vector length register (VLR) is set to 4.

Vector Pipeline Timing:

Here’s how the pipeline works for this example:

1. Load Vectors:

   • LV V1, R1: Load vector V1 from memory at location R1.
   • LV V2, R2: Load vector V2 from memory at location R2.

2. Multiply Elements:

   • MULVV.D V3, V1, V2: Multiply elements of V1 and V2, storing the results in V3.

3. Store Results:

   • SV V3, R3: Store the result vector V3 into memory at location R3.

Pipeline Timing Chart:

Instruction	F	D	R	Y0	Y1	Y2	Y3	W
LV V1, R1	F	D	R	L0	L1			W
LV V2, R2	F	D	R	L0	L1			W
MULVV.D V3, V1, V2	F	D	D	D	D	D	D	W
SV V3, R3	F	F	F	F	F	F	D	W

C Code:

c
for (int i = 0; i < 4; i++) {
    C[i] = A[i] * B[i];
}

Vector Assembly Code:

asm
LI VLR, 4         # Set vector length to 4
LV V1, R1         # Load vector A from memory into V1
LV V2, R2         # Load vector B from memory into V2
MULVV.D V3, V1, V2 # Multiply V1 and V2, store results in V3
SV V3, R3         # Store result vector in memory

---

Vector Instruction Parallelism

Key Concept:

Vector processors achieve parallelism by:

• Breaking vector operations into smaller independent tasks that run simultaneously.
• Overlapping execution of multiple instructions, such as load, multiply, and add operations.

Example Scenario:

• The machine has 32 elements per vector register and 8 lanes for parallel computation.

Execution Units:

• Load Unit: Handles memory operations to load/store vectors.
• Multiply Unit: Performs vector multiplication.
• Add Unit: Performs vector addition.

Example Execution:

• Load two vectors into registers (V1 and V2).
• Multiply the elements of V1 and V2 (V3 ← V1 × V2).
• Add another vector V4 to V3 (V5 ← V3 + V4).

Timing Chart for Vector Instruction Parallelism (8 Lanes):

Cycle	Load Unit	Multiply Unit	Add Unit
1	Load V1[0:7]
2	Load V1[8:15]
3	Load V1[16:23]
4	Load V1[24:31]
5	Load V2[0:7]	Multiply V1[0:7] × V2[0:7]
6	Load V2[8:15]	Multiply V1[8:15] × V2[8:15]
7	Load V2[16:23]	Multiply V1[16:23] × V2[16:23]	Add V3[0:7] + V4[0:7]
8	Load V2[24:31]	Multiply V1[24:31] × V2[24:31]	Add V3[8:15] + V4[8:15]
9			Add V3[16:23] + V4[16:23]
10			Add V3[24:31] + V4[24:31]

Visualization of Parallelism:

• Load Unit operates in chunks of 8 elements at a time.
• Multiply Unit starts multiplying as soon as the first chunk is loaded.
• Add Unit starts addition while multiplication is ongoing.

Performance Interpretation:

With 8 lanes, the number of cycles is significantly reduced compared to scalar execution. The overlapping of operations maximizes throughput.

---

Vector Chaining

Definition:

Vector chaining is akin to register bypassing in scalar processors. It allows dependent vector instructions to begin execution as soon as the first result of the previous instruction is available.

Key Advantages:

• Reduced Latency: Dependent instructions don’t need to wait for the entire vector to be computed.
• Increased Throughput: Better parallelism utilization across vector functional units.

Chaining Flow:

• Load Vectors V1 and V2.
• Multiply V3 = V1 × V2.
• Add V5 = V3 + V4.

Timing Diagram: Without vs. With Chaining

Time	Load	Multiply	Add
Cycle 1	V1, V2
Cycle 2	V1, V2	V3 = V1 × V2
Cycle 3		V3 = V1 × V2	V5 = V3 + V4
Cycle 4		V3 = V1 × V2	V5 = V3 + V4
Cycle 5			V5 = V3 + V4

C Code for Chaining:

c
for (int i = 0; i < 4; i++) {
    C[i] = (A[i] * B[i]) + D[i];
}

Vector Assembly Code with Chaining:

asm
LI VLR, 4         # Set vector length to 4
LV V1, R1         # Load vector A into V1
LV V2, R2         # Load vector B into V2
MULVV.D V3, V1, V2 # Multiply V1 and V2, result in V3
LV V4, R4         # Load vector D into V4
ADDVV.D V5, V3, V4 # Add V3 and V4, result in V5
SV V5, R5         # Store result vector in memory

---

Vector Stripmining

Problem:

Vector registers have limited length (e.g., VLR = 64), and large datasets cannot fit entirely in these registers.

Solution:

Break the dataset into chunks that fit into vector registers. This is called stripmining.

Execution Flow:

1. Calculate the remainder (N mod 64).
2. Process the remainder first.
3. Process chunks of size 64 until all elements are processed.

Example Vector Assembly Code:

asm
# Calculate the initial remainder
ANDI R1, N, 63          # R1 = N % 64 (remainder elements)
MTC1 VLR, R1            # Set Vector Length Register (VLR) to remainder

loop:
    LV V1, RA           # Load vector from A into V1
    LV V2, RB           # Load vector from B into V2
    MULVV.D V3, V1, V2  # Multiply V1 and V2, store in V3
    SV V3, RC           # Store result vector into C

    # Update pointers
    DSLL R2, R1, 3      # R2 = R1 * 8 (calculate offset in bytes)
    DADDU RA, RA, R2    # Update pointer RA
    DADDU RB, RB, R2    # Update pointer RB
    DADDU RC, RC, R2    # Update pointer RC

    # Update counters
    DSUBU N, N, R1      # N = N - R1 (remaining elements)
    LI R1, 64           # Set R1 to maximum vector length
    MTC1 VLR, R1        # Reset VLR to full length (64)

    BGTZ N, loop        # Loop if more elements remain

---

Key Takeaways:

1. Vector Chaining allows dependent instructions to start as soon as the first result is available.
2. Stripmining handles large datasets by breaking them into chunks that fit into vector registers.
3. Vector Instruction Sets offer scalability and compactness for efficient execution of operations in parallel.
4. Automatic Code Vectorization helps in speeding up execution by grouping operations into vector instructions.
5. Vector Conditional Execution enables efficient handling of conditions within loops using vector mask registers.

SIMD Instruction Set Extensions

Single Instruction, Multiple Data (SIMD) extends the idea of vector processing, where a single instruction operates on multiple data points at the same time, typically leveraging hardware to execute parallel tasks efficiently.

SIMD Operations

• SIMD instructions allow one instruction to perform operations on multiple pieces of data simultaneously.
• This approach is commonly used in tasks such as multimedia processing, data mining, scientific simulations, and machine learning.

SIMD Execution Example:

• Vector Length: SIMD operations use vector registers, processing multiple data elements at once.
• Example: SIMD would multiply corresponding elements of two arrays in one instruction cycle.

Graphics Processing Units (GPUs)

GPUs are specialized processors designed to accelerate the rendering of graphics, typically by handling parallel tasks efficiently. They leverage SIMD-like operations to process multiple data elements in parallel, making them ideal for tasks that require high throughput.

Key GPU Features

1. Parallelism: GPUs contain hundreds to thousands of smaller cores that perform computations in parallel, particularly for vectorized operations.
2. Massive Throughput: Designed to handle large amounts of data simultaneously, GPUs excel in parallel tasks like rendering images and video.
3. SIMD-like Operations: GPUs implement SIMD in both hardware and software for highly efficient processing, such as in graphics rendering and scientific computations.

GPU Execution Model

• GPUs use a SIMD architecture to perform multiple calculations in parallel, efficiently processing graphics data or performing calculations like matrix multiplications in deep learning.

Advantages of Vector Processors, SIMD, and GPUs

1. Vector Processors improve computational efficiency by operating on multiple data elements in parallel, reducing loop overhead and increasing throughput.
2. SIMD Extensions provide hardware-level parallelism, boosting performance in tasks like multimedia, video processing, and scientific simulations.
3. GPUs offer massive parallel processing capabilities, making them ideal for rendering graphics and performing high-throughput computational tasks, including AI and machine learning.

Feature	Vector Processors	SIMD	GPUs
Definition	Processors designed to handle vector (array) operations efficiently by performing the same operation on multiple data elements simultaneously.	A type of parallel processing where multiple data elements are processed with a single instruction.	Specialized processors designed to handle large-scale parallel computations, especially in graphics and general-purpose computing tasks.
Execution Model	Vector processing works on long vectors of data using vector registers and execution units.	Executes the same instruction on multiple data points simultaneously, typically using vector registers.	Executes many operations concurrently across thousands of smaller processing units, handling many threads in parallel.
Data Handling	Focuses on long vectors, each containing multiple data points, and processes them in parallel.	Processes multiple data elements in a single instruction, but typically handles smaller data chunks than vector processors.	Handles large datasets in parallel with thousands of cores, making it highly efficient for tasks that can be massively parallelized.
Parallelism	Fine-grained parallelism on vectorized data.	Fine-grained data-level parallelism (processing multiple data elements with one instruction).	Coarse-grained parallelism, supporting massive thread-level parallelism (thousands of threads simultaneously).
Performance	Excellent for scientific and engineering applications requiring high throughput of vector operations.	High efficiency for tasks where the same operation is applied to large data sets (e.g., multimedia processing).	Extremely high throughput for parallelizable tasks like rendering graphics, deep learning, simulations, and scientific computations.
Hardware Design	Contains specialized vector registers and execution units.	Requires SIMD units in CPUs or accelerators, supporting vector instructions.	Contains a large number of small processing units (CUDA cores for NVIDIA, Stream processors for AMD).
Programming Model	Typically programmed in vectorized instructions using specialized compilers.	Typically programmed using vectorized operations in SIMD-aware instructions (e.g., SSE, AVX in CPUs).	Programmed using parallel programming models like CUDA or OpenCL, with support for both low-level and high-level abstraction.
Examples	Cray-1, NEC SX series.	Intel's AVX (Advanced Vector Extensions), SSE (Streaming SIMD Extensions).	NVIDIA GPUs (e.g., GeForce, Tesla), AMD Radeon GPUs.
Application Domains	Scientific computing, engineering simulations, large-scale data analysis.	Image processing, signal processing, audio/video encoding, cryptography.	Graphics rendering, deep learning, parallel computation, gaming, scientific simulations.
Cost	Expensive, as they are specialized processors designed for high-performance tasks.	Integrated into modern CPUs, typically lower cost compared to dedicated processors.	Expensive, particularly high-end GPUs used for scientific computation and deep learning.
Flexibility	Less flexible compared to SIMD and GPUs. Designed specifically for vector processing tasks.	More flexible than vector processors but still limited to tasks that can be parallelized over data.	Highly flexible, capable of handling a wide range of parallel tasks beyond graphics (e.g., AI, machine learning).
Power Efficiency	Generally low power consumption for the specific tasks they are designed for.	More power-efficient than GPUs but less efficient than vector processors in their specialized domain.	Power consumption can be high, especially in GPUs used for intensive computational tasks like deep learning.