CPU Utilization and Multicore Systems

CPU Utilization

• Low CPU utilization could be a result of single core/single thread processing.
• In single core/single thread, the CPU scheduler implements concurrency by rapidly switching between processes.
• This is achieved by running processes concurrently but not in parallel.
• CPU core can also be time-multiplexed with multiple threads to achieve concurrency, but not parallelism.

Multicore System and Multithreading

• A multicore system comprises multiple computing cores on a single processing chip, each appearing as a separate CPU to the operating system.
• Multithreading with a multicore system allows for parallelism by enabling threads to run on different processing cores concurrently.

Concurrency vs. Parallelism

• Concurrency is achieved on single core systems by quickly switching between multiple tasks using a scheduler.
• Parallelism is achieved on multi-core systems by executing tasks simultaneously.

Multicore Programming Challenges

• Application programmers and system designers must effectively utilize the multiple computing cores.
• Operating system designers must develop scheduling algorithms that utilize multiple processing cores for parallel execution.
• Application programmers have to modify or design new multithreaded programs.
• The challenges associated with multicore architectures include:
  • Dividing activities
  • Balancing workloads
  • Data splitting
  • Data dependency
  • Testing and debugging

Programming Challenges: Dividing Activities

• Finding parts of an application that can be split into separate, concurrent tasks is crucial for parallel execution.
• Tasks should be independent and can run concurrently on different cores.

Programming Challenges: Balance

• Ensure that the tasks contribute equally to the overall execution of the application for optimal efficiency.

What is a Thread?

• A thread is a basic unit for CPU utilization and comprises a thread ID, program counter, register set, and stack.
• Threads belonging to the same process share code, data, and OS resources like open files and signals.

Multithreaded Application

• A traditional process has a single thread of control.
• A multithreaded process has multiple threads of control and allows for concurrent execution of tasks.
• Many modern applications are implemented as a separate process with multiple threads of control.
• This helps perform multiple tasks, such as generating thumbnails, retrieving data from the network, or displaying content.

Amdahl’s Law

• Amdahl's Law determines the maximum speedup achievable by parallelizing a program considering its serial and parallel portions.
• The serial portion limits the achievable speedup, regardless of the number of available cores.
• For example, a program with 50% serial content has a maximum speedup of 2x, even with an infinite number of cores.

User Threads vs. Kernel Threads

• Two levels of thread support, user threads, and kernel threads.
• User threads are managed by user-level thread libraries, while kernel threads are managed by the operating system.
• Common thread libraries:
  • POSIX Pthreads
  • Windows threads
  • Java threads

Many-to-Many Model

• Provides flexibility by creating as many user threads as needed, which are mapped to kernel threads for parallel execution on a multiprocessor.
• Can schedule another thread when one is blocked, enhancing efficiency.
• However, implementing this model is more complex.

Two-level Model

• Similar to the many-to-many model but allows user threads to be bound to kernel threads.

Thread Libraries

• Provide an API for programmers to create and manage threads.
• Two main implementations:
  • User-level libraries with code and data structures residing in user space, involving local function calls for operations.
  • Kernel-level libraries with code and data structures residing in kernel space, requiring system calls for operations.

Three Types of Thread Libraries

• POSIX Pthreads: A POSIX standard API for thread creation and synchronization, implemented at either user or kernel level.
• Windows Thread: A kernel-level library provided for Windows systems.
• Java Thread: An API for creating and managing threads in Java programs. Implemented using the thread library of the underlying host OS.

Inter-thread Data Sharing

• Pthreads and Windows: Data declared globally (outside functions) are shared across threads belonging to the same process.
• Java: Shared data must be explicitly managed between threads, as there's no equivalent of global data.

Pthreads

• A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization.
• Can be implemented at both user and kernel levels.
• Global data is shared amongst threads of the same process.
• Two strategies for creating multiple threads:
  • Asynchronous threading: Parent thread creates a child and resumes execution concurrently and independently.
  • Synchronous threading: Parent thread creates child threads and waits for their termination before resuming.

Implicit Threading

• Gains popularity as managing explicit threads becomes more complex.
• Thread creation and management are handled by compilers and run-time libraries, relieving programmers from explicit thread management.
• Implicit threading techniques include:
  • Thread pools
  • Fork-Join
  • OpenMP
  • Grand Central Dispatch
  • Intel Threading Building Blocks

Fork-Join Parallelism

• Multiple threads (tasks) are forked, executed concurrently, and then joined after completion.

Multithreading Models

• Many-to-One Model

  • Maps multiple user threads to a single kernel thread.
  • Provides more efficient management and avoids overhead.
  • Limitation: if a thread performs a blocking system call, all threads within the process are blocked.
  • Example: Solaris Green Threads, GNU Portable Threads

• One-to-One Model

  • Maps each user thread to a unique kernel thread.
  • Offers increased concurrency as each user thread can run independently.
  • Potential for overhead because creating kernel threads is resource-intensive.
  • Examples: Windows, Linux

• Many-to-Many Model

  • Multiplexes user threads to a smaller or equal number of kernel threads.
  • Provides flexibility and allows for parallel execution on multicore systems.
  • Allows for multiplexing of user threads to a smaller number of Kernel threads.
  • Improves concurrency and efficiency.
  • Example: Windows with the ThreadFiber package

Thread Libraries

• Thread Libraries

  • Provide a set of API for creating and managing threads.
  • Two main implementations:
    • User-level library: Code and data structures reside in user space. Function calls are local and don't involve system calls
    • Kernel-level library: Code and data structures exist in kernel space. Function calls require a system call to the kernel.

• Types of Thread Libraries:

  • POSIX Pthreads: A POSIX standard API for thread creation and synchronization. Can be implemented as user-level or kernel-level.
  • Windows Thread: A kernel-level library available on Windows systems.
  • Java Thread: Provides a thread API for creation and management. Implemented using the underlying host system's thread library.

Inter-thread Data Sharing

• Data Sharing
  • POSIX & Windows: Global variables declared outside functions are shared among all threads within the same process.
  • Java: No global data. Explicit mechanisms are needed for threads to share data.

Implicit Threading

• Growing in Popularity
  • Simplifies thread management, reducing complexity for programmers.
  • Implicit Threading is when the creation and management of threads is handled by compilers and runtime libraries instead of programmers.
• Five Implicit Threading Methods:
  • Thread Pools
  • Fork-Join
  • OpenMP (Open Multi-Processing)
  • Grand Central Dispatch
  • Intel Threading Building Blocks

Pthreads (POSIX Threads)

• POSIX Standard (IEEE 1003.1c)
  • Defines a standard API for thread creation and synchronization.
  • Implementation varies among operating systems.
• Common In UNIX Systems
  • Used in Linux and Mac OS X.
• Strategies for Thread Creation:
  • Asynchronous Threading: Parent thread creates a child thread and resumes execution. Parent and child threads operate independently.
  • Synchronous Threading: Parent thread creates child threads and waits for all children to terminate before resuming execution.

Fork-Join Parallelism

• Implicit Threading Approach
  • Threads (tasks) are forked (created) and then joined (synchronized) for coordination.
• Benefits:
  • Simplifies parallelism, as tasks can be split and recombined effectively.
  • Utilizes available resources more efficiently.
• Example: A task can be broken down into smaller subtasks that can be executed concurrently. The results are then combined to produce the final outcome.

Implicit vs Explicit Threading:

• Explicit Threading:
  • Programmer explicitly creates, manages and destroys threads.
  • Provides fine-grained control over thread behavior
  • Requires significant programming effort and knowledge.
• Implicit Threading:
  • Automated thread management by compilers and runtime libraries.
  • Easier for programmers to manage parallelism.
  • Less control over thread behavior.
• Examples:
  • Implicit: OpenMP, Grand Central Dispatch.
  • Explicit: POSIX Pthreads, Windows Threads.

Benefits of Multithreading

• Increased Responsiveness: Allows an application to keep responding to user input, even while other operations are being performed.
• Resource Utilization: Multiple threads can utilize the resources of a multi-core system more efficiently, leading to better performance.
• Simplified Programming: Can simplify the development of applications with complex operations.

Challenges of Multithreading

• Synchronization: Ensure that threads access shared resources in a coordinated manner, preventing race conditions.
  • Requires synchronization mechanisms like mutexes, semaphores, and condition variables.
• Deadlock: Situation where two or more threads are blocked, waiting for each other to release resources.
• Competition: Careful consideration is needed when multiple threads access shared resources (like memory, files or variables).

Linux Thread Management

• Kernel-level Threads: Linux uses the one-to-one model.
  • Each user thread maps to a kernel thread.
  • Threads share the same address space, which results in significant memory sharing.
• Kernel Threads:
  • Managed by the kernel.
  • Run and scheduled by the operating system.

Objectives

• Understanding Threads:
  • Threads are basic units of CPU utilization comprising thread ID, program counter, registers, and stack.
  • Threads share code, data, and resources like open files with other threads within the same process.
• Benefits of Multithreaded Applications:
  • Enhanced responsiveness, improved resource utilization, and simplified programming.
• Implicit Threading:
  • Different approaches - thread pools, fork-join, OpenMP, Grand Central Dispatch, and Intel Threading Building Blocks.
• Linux Thread Representation:
  • Linux utilizes the one-to-one model, mapping each user thread to a kernel thread.

This quiz explores the concepts of CPU utilization, concurrency, and parallelism in computing. It covers the differences between single-core and multi-core systems and the implications of multithreading. Test your understanding of how these systems achieve task management and performance optimization.