01 Introduction & Course Overview

Lecture from: 19.02.2024 | Video: Video ETHZ

Course Administration

Why this Course?

1. Necessity: Parallel programming has become essential since the early 2000s due to limitations in single-core performance scaling.
2. Different Thinking: It introduces a new way of thinking about computation, challenging the assumption of total ordering in all tasks.
3. Engagement: It’s intellectually stimulating and can be enjoyable for those who like problem-solving.

Goals

Our goals are twofold:

1. Practical Skills: Learn how to write parallel programs practically, primarily using Java (with examples in C).
2. Fundamental Understanding: Grasp the underlying principles of parallel computing. Generic concepts outlive specific tools. There are alternative approaches beyond Java’s paradigms.

Overview

The course is divided into four main blocks:

1. (Parallel) Programming: Basic concepts and techniques.
2. Parallelism: Task and data parallelism, decomposition, and task graphs.
3. Concurrency: Shared memory, threads, locks, and mutual exclusion.
4. Parallel Algorithms: Common parallel algorithm patterns and their analysis.

Part 1 Schedule:

Part 2 Schedule:

Learning Objectives

By the course’s end, students should:

1. Master fundamental concepts in parallelism.
2. Know how to construct parallel algorithms using various paradigms (e.g., task parallelism, data parallelism) and mechanisms (e.g., threads, tasks, locks, communication channels).
3. Be qualified to reason about correctness (absence of race conditions, deadlocks, etc.) and performance (speedup, efficiency) of parallel algorithms.
4. Be ready to implement parallel programs for real-world applications (e.g., searching large datasets, image processing).

Parallelism and Concurrency

Parallelism is the idea of dividing a task into smaller, independent subtasks that can be executed simultaneously. This can significantly reduce the overall execution time.

Analogy: Searching for a needle in a haystack is faster if multiple people work on different parts of the haystack concurrently. Similarly, finding the maximum value in a large array can be parallelized.

Concurrency deals with managing access to shared resources by multiple processes or threads.

Analogy: Imagine a kitchen with a stove and oven shared by two chefs (processes). We need to ensure both chefs can use the resources fairly and without conflict.

Key Concepts:

• Starvation: A situation where a process is perpetually denied access to a needed resource. We aim for starvation-freedom.
• Mutual Exclusion: Ensuring that only one process can access a critical resource (like the stove) at any given time. This prevents data corruption and race conditions.
• Communication Protocol: A well-defined method for processes to exchange information, with minimal overhead.

Why Parallelism?

Moore’s Law (the observation that the number of transistors on a chip doubles approximately every two years) has historically driven performance improvements. This law also broadly applies to RAM size and pixel densities. Transistor counts continue to increase. However, clock speeds (single-core performance) have plateaued since around 2005.

Why the Plateau?

Heat and power consumption have become the primary limiting factors in modern computer architecture. As transistors become smaller and faster, they consume more power and generate more heat. Dissipating this heat becomes increasingly difficult and expensive.

The Solution: Multi-Core Processors

The industry’s response has been to shift from increasing clock speed to increasing the number of cores (processing units) per chip. We maintain efficient power usage (operations per watt) by keeping individual cores relatively small and simple, but we achieve higher overall performance by executing multiple tasks in parallel.

Mutual Exclusion

Ensuring that only one process/thread can access a shared resource at a time.

Example: Alice (Cat) and Bob (Dog)

Alice and Bob cannot be in the garden simultaneously.

Requirement 1: Mutual Exclusion: The garden is mutually exclusive to Alice and Bob.

Requirement 2: No Lockout When Free: If the garden is empty, a pet wanting to enter should not be indefinitely blocked.

How to Solve This?

Idea 1: Shared Signal (Alternating Turns)

A light signal indicates whose turn it is to be in the garden. When a pet leaves, it pulls a rope to switch the light, changing the signal.

Problem: Starvation: A pet could stay in the garden indefinitely, preventing the other from entering.

Idea 2: Notification (Flags)

Each pet has a flag to signal their intention to enter the garden.

Access Protocol 1

1. Alice checks if Bob’s flag is up.
2. If not, the cat raises its flag and enters the garden.

Problems:

• No Mutual Exclusion: Both pets could check simultaneously, see no flags, raise their own flags, and enter the garden together.
• Deadlock: Both pets see each other’s flags up and wait indefinitely.

Access Protocol 2

1. Cat raises its flag.
2. Cat checks if Bob’s flag is up.
3. If not, the cat enters the garden.

Problems:

• Livelock: Both pets repeatedly raise their flags, see the other’s flag, lower their flags, and repeat, never entering the garden. This is a specific kind of starvation.

Final Access Protocol (Combination)

Combine the binary light signal (for fairness and turn-taking) with the flag system (for intention signaling).

1. Both Want to Enter: Both pets raise their flags.
2. Check Signal: They check the light signal to determine priority.
3. Lower Flag: The pet without priority lowers its flag and waits.
4. Enter and Switch: The pet with priority enters the garden. When leaving, it switches the light signal.

Problem Resolution:

• Mutual Exclusion: The flag system, combined with the light signal, ensures only one pet enters at a time.
• Deadlock: The light signal breaks the symmetry, preventing indefinite waiting.
• Livelock: The light signal determines a definite order, avoiding the repeated raising and lowering of flags.
• Starvation The light takes a binary value, preventing one pet from waiting forever.

Remaining Issue (not fully solved):

One pet could still hog the garden by repeatedly entering and leaving quickly. The light signal prevents indefinite starvation, but not short-term unfairness. More sophisticated mechanisms (like ticket locks or semaphores) are needed to enforce stricter fairness in real-world systems.

Producer-Consumer

The Producer-Consumer problem is a classic concurrency problem where one or more producers generate data and one or more consumers process that data. The key is to synchronize access to a shared buffer (like a queue) where producers place data and consumers retrieve it.

Example: Tiger (Consumer) and Zookeeper (Producer)

• Alice (Tiger): The consumer. She eats food from plates.
• Bob (Zookeeper): The producer. He fills the plates with food.
• Alice cannot be in the garden when the plates are empty.
• Bob can only enter the garden to refill plates when Alice is not present.

In this scenario, unlike the mutual exclusion problem where two entities are competing for a single resource, we have a cooperative relationship. Both the producer (Bob) and the consumer (Alice) need to communicate. A single flag can be sufficient for synchronization.

Protocol

1. Flag Up: Indicates that the plates are empty.
2. Bob (Producer) Enters: Bob sees the flag up, enters the garden, and fills the plates.
3. Bob Leaves and Lowers Flag: Bob leaves the garden and takes the flag down, signaling that the plates are full.
4. Alice (Consumer) Enters: Alice sees the flag is down, enters the garden, and eats.
5. Alice Leaves and Raises Flag: After eating, Alice leaves the garden and raises the flag, indicating that the plates are now empty.

This protocol works well because both Alice and Bob actively participate in the communication and synchronization. The flag serves as a shared signal, indicating the state of the shared resource (the plates).

Readers-Writers

The Readers-Writers problem is another classic concurrency problem. It deals with multiple processes (or threads) accessing a shared resource (like a file or a database). Some processes (readers) only need to read the data, while others (writers) need to modify it.

The Challenge:

• Multiple readers can access the data concurrently without any issues.
• However, a writer must have exclusive access to the data. No other reader or writer can access the data while a writer is modifying it.

This scenario is common in database systems, where many users might be reading data, but updates (writes) require exclusive access to ensure data consistency.

Example: Writer (Alice) and Reader (Bob)

Alice (writer) is writing a message, and Bob (reader) is reading it.

Scenario:

1. Alice writes “Pet”. Bob reads “Pet”.
2. Alice writes “Loves”. Bob reads “Loves”.
3. Alice writes “Ham”. Bob goes into the house (is delayed) and doesn’t read “Ham”.
4. Alice writes “I”. Bob is still away.
5. Alice writes “Hate”. Bob is still away.
6. Alice writes “Salad”. Bob returns and reads “Salad”.

Result: Bob reads “Pet Loves Salad,” which is an inconsistent and incorrect message.

What went wrong? The reader (Bob) was interrupted during the writing process, leading to an inconsistent view of the data.

Why is this important?

This simple example highlights the complexities of parallel and concurrent programming. The core message is:

• Bad News:

  • Real-world parallel computing is far more complex than these simplified examples.
  • The effects of actions by one thread (e.g., setting a flag) may be delayed or even appear in a different order to other threads. This phenomenon is due to memory consistency models and hardware-level optimizations. This makes the simple protocols discussed earlier even more problematic.
  • The precise reasons for these complexities involve deep topics in computer architecture and operating systems, which will be covered in later studies.

• Good News:

  • Modern hardware provides specialized mechanisms (atomic operations, memory barriers) to help manage low-level concurrency issues.
  • High-level programming languages (like Java) offer abstractions (locks, semaphores, concurrent data structures) that simplify concurrent programming.
  • While we won’t always be dealing directly with these low-level details, understanding the underlying principles is crucial for writing correct and efficient parallel programs. This foundation is essential for using higher-level abstractions effectively.

Continue here: 02 Java Recap and JVM Overview