COMS20001: Concurrent Computing

Welcome to the unit web page for Concurrent Computing. This second year unit is worth 20 credit points. The module introduces concurrent computing as a key computational concept and provides an introduction to practical use of concurrent programming and formal reasoning about concurrency. It will give an overview of how concurrency principles underpin the creation of parallel applications, operating systems and computer networks.

Overview: The Unit in a Nutshell

This unit gives an introduction to formalisations and implementation techniques that are relevant to building and utilizing computers that run more than one entity at once. Concurrency solutions are required both when applications are to be speeded up via parallel execution and when resources must be shared. We will show state-of-the art techniques for using multiple processors for one task, as well as how single processors can be used to handle multiple tasks. Particular topics covered will include an introduction to concurrency and how it can be reasoned about, how concurrency can be deployed on hardware, concurrent programming, how concurrency is handled by operating systems and how concurrent systems can be interconnected by networks. The course is structured in four distinct parts:

Core concurrency principles and reasoning
Concurrent programming
Operating systems
Interconnection networks

The components and their relationships are illustrated in the diagram below.

People: Staff, Teaching Assistants and Students

Weeks
01-12	Majid Mirmehdi	majid@cs.bris.ac.uk
	Tilo Burghardt	tilo@cs.bris.ac.uk
13-24	Daniel Page	daniel.page@bristol.ac.uk

Locations: Times and Rooms

Lecture: Mon 12noon, QB1.4 Pugsley
Lecture: Fri 10am, PRIORY CMPLX D BLK 2D3
Spare Slot: Fri 9am, PRIORY CMPLX D BLK 2D3 (slot may or may not be used)
Lab: Fri 2pm-4pm, MVB2.11 or Fri 4pm-6pm, MVB2.11

Materials: Lecture Notes, Worksheets, Courseworks

Wk		LECTURES		LABS
	PART 1: Core Concepts, Reasoning and Programming in Concurrent Computing
01		Mon 28.09.15, 12noon QB1.4 Pugsley Introduction and History (print version 6pp) (slides) -- TEAM SIGNUP -- signup as a pair for ONE lab slot with your TWO usernames in the participants field	Fri 02.10.15, 10am PRIORY CMPLX D BLK 2D3 Towards Concurrent Programming in xC (print version 6pp) (slides) Code: hello.xc, par.xc, hellotile.xc, partc.c, partxc.xc, interface.xc	SLOT: Fri 02.10.15, 2pm-4pm MVB 2.11 or SLOT: Fri 02.10.15, 4pm-6pm MVB 2.11 LAB 01: Warm-up & xC Threads Topic: Concurrent Code Execution (Parallelism and Non-Determinism) Part A: Getting Started Part B: Parallel Ants External: Get xTimeComposer External: XC Specification External: XC Documentation External: XC Programming Guide
02		Mon 05.10.15, 12noon QB1.4 Pugsley Deadlocks and Channel Communication (print version 6pp) (slides) Dining Philosophers	Fri 09.10.15, 10am PRIORY CMPLX D BLK 2D3 Data Exchange for Processes in xC (print version 6pp) (slides)	SLOT: Fri 09.10.15, 2pm-4pm MVB 2.11 or SLOT: Fri 09.10.15, 4pm-6pm MVB 2.11 LAB 02: xC Channels Topic: Communicating Threads (Runtime Interlinks and Deadlock) Queen & Worker Ants
03		Mon 12.10.14, 12noon and Mon 19.10.14, 12noon QB1.4 Pugsley Replication & Pipelining (print version 6pp) (slides)	Fri 16.10.15, 10am PRIORY CMPLX D BLK 2D3 CSP Abstraction: Events, Processes, Traces, Refinement (print version 6pp) (slides)	SLOTS: Fri 16.10.15, 2pm-4pm MVB 2.11 Fri 23.10.15, 2pm-4pm MVB 2.11 or SLOTS: Fri 16.10.15, 4pm-6pm MVB 2.11 Fri 23.10.15, 4pm-6pm MVB 2.11 ASSIGNMENT WEEKS 3-4 (pair programming, formative, 0%) (xCore-200 Explorer Kit required) Download Code Skeleton (xc)
04			Fri 23.10.15, 10am PRIORY CMPLX D BLK 2D3 Choice, Refusals, Failures (print version 6pp) (slides)
05		Mon 26.10.15, 12noon QB1.4 Pugsley Concurrent System Design (print version 6pp) (slides)	Fri 30.10.15, 10am Fri 06.11.15, 10am PRIORY CMPLX D BLK 2D3 Bridging the Gap: xC and CSP (print version 6pp) (slides)	LAB SLOTS WEEKS 5-10 Fri 2pm-4pm/4pm-6pm MVB 2.11 ASSIGNMENT WEEKS 5-10 (pair programming, summative, 25%) (xCore-200 Explorer Kit required) Download Skeleton Project (xTimeComposer) PGM Images: 16x16, 64x64, 128x128, 256x256, 512x512
06		Mon 02.11.15, 12noon QB1.4 Pugsley Paradigms of Parallelism (print version 6pp) (slides)
07		Mon 09.11.15, 12noon QB1.4 Pugsley Liveness and Deadlock (print version 6pp) (slides)	Fri 13.11.15, 10am PRIORY CMPLX D BLK 2D3 Introduction to Petri Nets (print version 6pp) (slides)
08		Mon 16.11.15, 12noon QB1.4 Pugsley Detailed Execution Control in xC (print version 6pp) (slides)	Fri 20.11.15, 10am PRIORY CMPLX D BLK 2D3 Race Conditions and Critical Sections (print version 6pp) (slides)
09		Mon 23.11.15, 12noon QB1.4 Pugsley (no Friday Lecture) Basics of Memory and Process Administration (print version 6pp) (slides)
10		Mon 30.11.15, 12noon QB1.4 Pugsley Advanced Data Access in xC (print version 6pp) (slides)	Fri 04.12.15, 10am PRIORY CMPLX D BLK 2D3 Case Study: Java Concurrency
11		Mon 07.12.15, 12noon QB1.4 Pugsley (no Friday lecture, presentations instead) Concurrency Challenges (Interactive Lecture)	--- COURSEWORK PRESENTATION SIGNUP --- Signup with your usernames of the team in the participant field. You need to signup for a slot and all team members need to turn up at MVB2.11 at the specified time, otherwise you may not get your mark and feedback for the coursework. ALSO, BRING ALONG YOUR SCOTLAND YARD BOARDGAME (if you were a keeper from PANDA2) AND YOUR 2 xCORE-200 Explorer Kits!
12		Mon 14.12.15, 12noon QB1.4 Pugsley Summary, Outlook, Exam Preparation

Key Concurrency Terms (Covered in Unit PART 1)

Alphabet (CSP)
Alphabetised Parallel (CSP)
Amdahl's Law
Asynchronous Communication
Atomic Variables (Java)
Barrier (Synchronisation Point)
Bernstein's Criteria
Bipartite Graph (Petri Net)
Bottle Neck (Communication Properties)
Caching
Callable (Java)
Central Directory Server
Channel Communication
Channel Bandwidth
Channel Buffer
Channel End (XC)
Channel Latency
Circular Wait (Deadlock Condition)
Communication Overhead
Concurrency
Concurrent System Design
Critical Section
Communicating Sequential Processes (CSP)
Consumer-Producer Problem
CSPm
Data Dependency
Deadlock
Deadlock Resolution Strategies
Deadlock Conditions (Necessary & Sufficient)
Dekker's Algorithm
Deterministic Control Flow
Dining Philosophers Problem
Distributed Shared Memory
Divergence
Dynamic Analysis (Petri Net)
Event (CSP)
Executor (Java)
External Choice (CSP)
Failures (CSP)
Failure-Divergence-Refinement (CSP)
Failure-Refinement (CSP)
Fairness
Farming
Flynn's Taxonomy
Firing (Petri Net)
Front Side Bus
Future (Java)
Geometric Parallelism
Guarded Choice (CSP)
Granularity
Hiding (CSP)
Inhibitor Arc (Petri Net)
Internal Choice (CSP)
Labelled Transitions (CSP)
Liveness (Process Property)
Livelock
Livelock Freedom (Process Property)
Load Balancing
Local Memory
Locking (C)
Locking Conditions (Java)
Marking (Petri Net)
Memory Management Unit
Menu Choice (CSP)
Message Acknowledgement
Message Passing
MISD (Architecture)
MIMD (Architecture
Monitor
Multicore Processor
Multimemory System
Multithreading
Mutex (Java)
Mutual Exclusion
Mutual Independence (Threads)
Non-Determinism
OnChip Network
on stdcore (XC)
Orchestration
par (XC)
Parellelism
Peterson's Algorithm
Petri Nets
Prefixing (CSP)
Pipelining
Places (Petri Nets)
POSIX Threads
Preemption (Deadlock Resolution)
Prefix Closure (CSP)
Process (XC,CSP)
Process Networks
Process Algebra
Process Control Block
Process Table
Race Conditions
Reachability Graph (Petri Net)
Recursive Doubling Reduction
Reduction Graph
Refusals (CSP)
Trace-Refusals-Pair (CSP)
Replication (XC)
Runnable (Java)
Safety (Process Property)
Scalability (System Property)
select (XC)
Semaphore (Java)
Shared Memory
Silent Event (CSP)
SIMD (Architecture)
SISD (Architecture)
SKIP (CSP)
Sleeping Thread
Spinning (Active Waiting)
'Stale Data'
Starvation
State Space Cardinality (Process Properties)
Static Analysis (Petri Net)
STOP (CSP)
Synchronised Communication
'Tau' Event (CSP)
Test-And-Set Operation
Thread (Java)
Thread - Shared Environment
Thread Instantiation
threadsafe (Java)
Thread Termination
Thread Pool (Java)
Tokens (Petri Net)
Token Game (Petri Net)
Trace (CSP)
Trace Refinement (CSP)
Traces Set (CSP)
Transaction (XC)
Transition Diagram (Process)
Transitions (Petri Net)
Tree Reduction
Virtual Memory
volatile (Java)
Volatile Data
XC Language
XC/C Integration
XMOS XC-1A
XS1 Architecture
xTimeComposer

Acknowledgements

Many thanks to Kerstin Eder, Simon Hollis and other members of the Dept for signitficant contributions to teaching materials, Henk Muller and Ian Holyer for helpful discussions and input.

rossng/COMS20001--Concurrent-Computing