03 Introduction to Threads and Synchronization (Part I)

Lecture from: 26.02.2024 | Video: Video ETHZ

A Brief History of Computer Graphics - Ray Tracing

Ray tracing is a rendering technique that simulates the path of light rays to create realistic images.

Early Ray Tracing

The foundational idea of ray tracing dates back much earlier than computer graphics.

• 15th Century (Albrecht Dürer): Dürer’s “drawing machine” used a string to represent a light ray, tracing the path from an object to the viewer’s eye. This physical device embodied the core concept of ray tracing.
• 1968 (Appel): Arthur Appel first described the use of ray tracing in the context of computer graphics, specifically for calculating shadows.
• 1980 (Whitted): Turner Whitted extended the concept to include specular reflections and refractions, significantly enhancing realism.
• 1984 (Cook et al): Introduced stochastic ray tracing which includes effects like motion blur, and depth of field.
• 1997 First Realtime Raytracing: The first real-time ray tracing system was developed. This was a significant milestone, as it demonstrated the potential for interactive applications.

The Ray Tracing Algorithm (Simplified)

The basic ray tracing algorithm involves these steps:

1. For each pixel in the image:
   • Cast a ray: A ray is sent from the camera (viewpoint) through the pixel into the scene.
   • Find the closest intersection: Determine the closest object in the scene that the ray intersects.
   • Calculate shading: Calculate the color of the pixel based on the material properties of the intersected object, lighting conditions, and potentially reflections and refractions.

Inherent Parallelism

A crucial advantage of ray tracing is its embarrassingly parallel nature. Because the color of each pixel can be calculated independently of other pixels, the computation can be easily distributed across multiple processors or cores. This makes ray tracing well-suited for parallel processing, leading to significant speedups.

Modern Ray Tracing Techniques

Modern ray tracing methods often employ techniques that start with a lower-quality, “noisy” image and progressively refine it.

• Progressive Refinement: Instead of shooting many rays per pixel initially, modern methods might start with a small number of rays per pixel, producing a noisy but rapidly generated image.

• Monte Carlo Methods: Monte Carlo methods, which are used to model a variety of physical systems (like ray tracing), involve randomness. Instead of having a fixed number of samples, there’s an inherent randomness in the process that introduces noise.

• Denoising: Advanced denoising algorithms are used to remove the noise and produce a high-quality final image. This approach allows for faster initial rendering, making ray tracing more practical for interactive applications. Professor’s research group actively uses denoising methods.

Impact of Denoising

By incorporating denoising techniques, the number of rays required per pixel can be significantly reduced (potentially halved or more), leading to substantial performance improvements without sacrificing visual quality. This makes real-time ray tracing increasingly feasible, even for complex scenes.

Parallel Programming: Introduction to Threads and Synchronization

• Motivation: Why parallelism is both challenging and beneficial.
• Multiprocessing vs. Multithreading: The differences and trade-offs between these two approaches to concurrency.
• Java Threads: Creating, managing, and terminating threads in Java.
• Shared Resources and Thread Interleavings: The challenges of managing shared data and the potential for unexpected interactions between threads.
• Synchronization with synchronized Blocks: Using Java’s built-in mechanisms to control access to shared resources.
• Coordination/Communication: Producer-Consumer with wait & notify: Implementing classic coordination patterns using Java’s concurrency primitives.

Parallelism: An Analogy

Consider the steps involved in starting your day:

1. Wake up
2. Get out of bed
3. Brush teeth
4. Get dressed
5. Make coffee
6. Make toast

Some of these steps can be performed in parallel (e.g., making coffee and toast simultaneously), while others must be sequential (e.g., waking up before getting out of bed).

The Bad News: Parallelism is Tricky!

Humans are not inherently good at parallel thinking. Our attention is selective, and we can easily miss important details when focusing on multiple things simultaneously. Key takeaway: parallel thinking is not natural, and our attention can easily be diverted, leading to missed information.

The Good News: Parallelism is Useful!

Despite the challenges, parallelism is essential for modern computing.

I suggest watching this video, it gives a really good intuition. If you like that video, watch the whole playlist suggested here :D

Multitasking/Multiprocessing

Multitasking is the concurrent (= single execution thread, but switching program context to give illusion of multitasking) execution of multiple tasks or processes.

• Time Multiplexing: The CPU rapidly switches between tasks, creating the illusion of parallelism even on a single-core system.
• Asynchronous I/O: Allows the CPU to continue processing while I/O operations (which are truly parallel) are in progress. For example, waiting 10ms for a hard drive allows other processes to execute a significant number of instructions.

Process Context

A process is a program executing within an operating system. Each running instance of a program (e.g., multiple browser windows) is a separate process. Each process has its own context, including:

• Instruction counter
• Values in registers, stack, and heap
• Resource handles (file access, devices)

Process Lifecycle States

Processes transition through various states:

1. Created: The process is being initialized.
2. Running: The process is currently executing instructions.
3. Waiting: The process is waiting for an event (e.g., I/O completion).
4. Blocked: The process is waiting for a resource (e.g., a lock).
5. Terminated: The process has finished execution.

Process Management

The operating system manages processes:

• Starts and terminates processes.
• Controls resource usage (CPU time, memory).
• Schedules CPU time.
• Synchronizes processes (if needed).
• Enables inter-process communication.

Process Control Blocks (PCB)

The OS uses Process Control Blocks (PCBs) to store information about each process. Switching between processes involves saving and restoring the PCB, which can be complex and expensive.

Context switching between processes:

Problem of having many processes:

Multithreading

Multithreading provides concurrency within a single process.

Threads are independent sequences of execution running within the same OS process. Crucially, threads share the same address space.

• Shared Resources: Threads share resources and can communicate more easily than separate processes.
• Efficiency: Context switching between threads is generally more efficient than between processes (no address space change, no OS scheduling).
• Vulnerability Threads are not isolated and it’s easy to make programming mistakes.

Usage of Multithreading

• Reactive Systems: Continuously monitoring and responding to events.
• GUI Responsiveness: Allowing user interaction while performing background tasks.
• Servers: Handling multiple clients concurrently.
• Parallel Computation: Taking advantage of multiple CPU cores.

Multithreading: 1 vs. Many CPUs

Multiple threads sharing a single CPU (time-slicing):

Multiple threads running on multiple CPUs (true parallelism):

Big Picture of multithreaded Java application:

Java Threads

A thread in Java is a sequence of instructions executed sequentially. The java.lang.Thread class is a core part of the Java language. Key methods:

• start(): Creates a new thread of execution and calls the run() method on the associated object.
• interrupt(): Freezes a thread and throws an exception.

Creating Java Threads: Option 1 (Oldest)

Subclass java.lang.Thread and override the run() method.

• The run() method contains the code that will be executed by the thread.
• Calling start() invokes run().
• Crucially, creating a Thread object does not start the thread; you must explicitly call start().

Creating Java Threads: Option 2 (Better)

Implement the java.lang.Runnable interface.

• The Runnable interface has a single method: public void run().
• Create a Thread object, passing an instance of your Runnable class to the constructor.
• Call start() on the Thread object.

Thread State Model in Java

Threads transition through various states:

• NEW: The thread has been created but not yet started.
• RUNNABLE: The thread is eligible to be run by the scheduler.
• BLOCKED/WAITING/TIMED_WAITING: The thread is waiting for a resource or event (e.g., I/O, a lock, wait(), sleep()).
• TERMINATED: The thread has completed execution.

java.lang.Thread (Under the Hood)

The Thread class implements Runnable. It contains native methods (implemented in C/C++) that interact with the operating system to manage threads.

Native C implementation:

Continue here: 04 Introduction to Threads and Synchronization (Part II)