CSC2002S Notes
1. Parallel and Concurrent Programming ................................................................................. 2
2. Architecture ................................................................................................................................. 84
3. Mobile Development and Design ...................................................................................... 181
,1. Parallel and Concurrent Programming
Parallelism versus Concurrency
Parallel program:
• Use extra computational resources to solve a problem faster (increasing
throughput via simultaneous execution).
Parallel algorithm example:
• May get roughly 4x speedup – array sum
Concurrent program:
• Correctly and efficiently manage access to shared resources (from multiple
possibly-simultaneous clients).
• Uses synchronization to prevent multiple operations from interleaving in a
way that leads to incorrect results
,Concurrency algorithm example:
• Prevent bad interleaving (correctness).
• But allow some concurrent access (performance).
Checkpoint
Your Java web server needs to keep track of the number of accesses to particular
web pages. As defined in this course, this is a:
A. parallel programming problem
B. concurrent programming problem
C. Both A and B
D. neither A nor B
→C
Concurrency Problems – Race Conditions
• A race condition is an error in a program where the output and/or result of
the process is unexpectedly and critically dependent on the relative sequence
or timing of other events.
• The idea is that the events race each other to influence the output first.
NOTE: Unintended race conditions are incredibly common in concurrent programs.
Example:
Therac-25, a radiation therapy machine for cancer treatment used software safety
systems that had a race condition between operator text input and software
configuring the electron beam. Caused by users hitting the up arrow too quickly,
preventing the system from properly registering their edits.
→ Resulted in an occasional 100X radiation dose, that lead to several deaths.
, Nondeterminism
In sequential programs, instructions are executed in a fixed order determined by the
program and its input. The execution of one procedure does not overlap in time with
another.
→ Deterministic
In concurrent programs, computational activities may overlap in time and the
subprogram executions describing these activities proceed concurrently.
→ Non-deterministic
NOTE: It is not possible to tell, by looking at the program, what will happen when it
executes.
Parallel/Concurrent Complexity
Managing parallel complexity and the principles and techniques necessary for the
construction of well-behaved and efficient parallel and concurrent programs.
NOTE: General rule is to stay sequential if possible.
When parallel programming is necessary
High Performance Computing (HPC):
• Uses cutting-edge parallel computers to solve “grand-challenge” problems.
• Programmers write programs to solve such computationally large problems
that it would take years, or centuries, for one computer to finish it.
NOTE: Parallel programming is essential to use the computing power of multicore
architectures → Most current desktop and laptop computers have multiple cores.
When concurrent programming is necessary
Complex programs like:
• Operating systems, web browsers, real-time systems, event-based
implementations of graphical user interfaces, multiuser games, chats and
ecommerce.
• Handle multiple things happening at once and therefore are multithreaded.
• Many concurrent threads run simultaneously.
1. Parallel and Concurrent Programming ................................................................................. 2
2. Architecture ................................................................................................................................. 84
3. Mobile Development and Design ...................................................................................... 181
,1. Parallel and Concurrent Programming
Parallelism versus Concurrency
Parallel program:
• Use extra computational resources to solve a problem faster (increasing
throughput via simultaneous execution).
Parallel algorithm example:
• May get roughly 4x speedup – array sum
Concurrent program:
• Correctly and efficiently manage access to shared resources (from multiple
possibly-simultaneous clients).
• Uses synchronization to prevent multiple operations from interleaving in a
way that leads to incorrect results
,Concurrency algorithm example:
• Prevent bad interleaving (correctness).
• But allow some concurrent access (performance).
Checkpoint
Your Java web server needs to keep track of the number of accesses to particular
web pages. As defined in this course, this is a:
A. parallel programming problem
B. concurrent programming problem
C. Both A and B
D. neither A nor B
→C
Concurrency Problems – Race Conditions
• A race condition is an error in a program where the output and/or result of
the process is unexpectedly and critically dependent on the relative sequence
or timing of other events.
• The idea is that the events race each other to influence the output first.
NOTE: Unintended race conditions are incredibly common in concurrent programs.
Example:
Therac-25, a radiation therapy machine for cancer treatment used software safety
systems that had a race condition between operator text input and software
configuring the electron beam. Caused by users hitting the up arrow too quickly,
preventing the system from properly registering their edits.
→ Resulted in an occasional 100X radiation dose, that lead to several deaths.
, Nondeterminism
In sequential programs, instructions are executed in a fixed order determined by the
program and its input. The execution of one procedure does not overlap in time with
another.
→ Deterministic
In concurrent programs, computational activities may overlap in time and the
subprogram executions describing these activities proceed concurrently.
→ Non-deterministic
NOTE: It is not possible to tell, by looking at the program, what will happen when it
executes.
Parallel/Concurrent Complexity
Managing parallel complexity and the principles and techniques necessary for the
construction of well-behaved and efficient parallel and concurrent programs.
NOTE: General rule is to stay sequential if possible.
When parallel programming is necessary
High Performance Computing (HPC):
• Uses cutting-edge parallel computers to solve “grand-challenge” problems.
• Programmers write programs to solve such computationally large problems
that it would take years, or centuries, for one computer to finish it.
NOTE: Parallel programming is essential to use the computing power of multicore
architectures → Most current desktop and laptop computers have multiple cores.
When concurrent programming is necessary
Complex programs like:
• Operating systems, web browsers, real-time systems, event-based
implementations of graphical user interfaces, multiuser games, chats and
ecommerce.
• Handle multiple things happening at once and therefore are multithreaded.
• Many concurrent threads run simultaneously.
