370CT: Introductory lecture

Dr Carey Pridgeon

2016-08-06 Tue

Created: 2017-01-17 Tue 08:17

intro

Module Contents

This module will cover the following subjects:

  • Concurrent Programming Fundementals.
  • Parallel Programming with OpenMP
  • Distributed Programming with OpenMPI

By a mix of Lectures and weekly programming exercises.

  • Assessment is via:
    • A programming assignment (50%).
    • An exam (50%)

Module Delivery

  • The subjects are taught by a mix of lectures and weekly programming exercises.
  • These exercises are constructively aligned, which means they progress with the subjects, and if done, will make passing this module much easier.
  • The exercises are sequential. If you don't do them as you go along you will get stuck.
  • Support for the exercises will always be available in the classes.

Module Delivery

  • Not doing the exercises will make the assignment and exam extremely hard to pass, and a high module grade will be impossible.
  • All resits/fails in the past on this module can be attributed to ignoring this advice.
  • Failure to attend lectures and workshops will have the same effect.
  • Lateness is your problem not mine, if you miss material it is your responsibility to catch up.
  • This module is not especially easy, but since it employs industry standard methods and involves lots of programing, it is valuable.

Workplace Relevence

  • Everything you learn on this module will come up in your career as a programmer, usually sooner rather than later.
  • Job interviews involve technical questions and algorithm demonstrations. physical practice with techniques will help more than just reading about a given subject.

Module assesment scheme

  • The Assignment is due in towards the end of the module.
  • I will expect you to work on the assignment in the class during the modules run.
  • Part of your grade for the assignment will be me seeing you work on it and discussing it with you.
  • Faliure to do this will therefore impact your grade for the assignment significantly.

Facilities

Module Facilities

  • All programming on this module can be done on Nostromo, a Linux Cluster running Centos 7
  • To use it, you will need to have accounts created, since it is not part of the university user account system.
  • Username Allocation
  • Put your name and email next to a username and login. You will be asked to change your password, thereafter the account will be yours for the run of the module.
  • I am the admin of this machine, so if you have any problems, including forgetting your password, ask me.

External access

VPN (Virtual Private Network)

  • To access university resources used on this module externally you need to establish a VPN (Virtual Private Network) connection.
  • To install VPN go to this url:
  • https://connect.coventry.ac.uk
  • It will attempt a Java client install. If it fails it will give give you a downloadable client. I have never had the Java client successfully install, but the downloadable app is probably easier.
  • Login in to this program using the same url and your university credentials.

Subject

Multi-processor Computing

  • Modern processors have multiple cores because of the limitations described in Moore’s Law.
  • This leaves only multiple cores as the solution on a single machine, or multiple computers, themselves with multiple cores and shared memory for more power.
  • Because of this, serial programs are becoming increasingly irrelevant.

Why Bother?

  • Not all problems need multiple cores, but programs don’t just solve the problem they are aimed at.
  • If you wish to be a programmer, this is a subject you need to understand, even if only on the basic level this module will provide.

seperation.png

Definitions

Serial Programs

  • A serial program consists of a sequence of operations that get run in predictable order, always one at a time.
  • This sequence of operations is executed in a process.
  • A normal process contains one thread of execution (list of operations).

serial.png

Multi-Threaded Programs

  • A multi-threaded program contains one main thread and an arbritrary number of additional number of additional threads of execution.
  • There are several classes of multi-threaded program. In this module we will cover three of them.
    • Concurrent
    • Parallel
    • Distributed

Concurrency

  • Concurrent operations are those which may or may not happen simultaneously, but do not act on the same data.
  • Concurrency is obtained because one operation need not complete at any particular point because no other thread/operation is dependant on it.

concurrent.png

Parallelism

  • Parallel programs are those in which operations do happen simultaneously. They most often, but not always, involve operations on the same dataset.
  • In this class of programming timing of the various threads is important
  • Operations need to happen in a certain order and finish in a co-ordinated/controlled manner as some combination of results usually occurs.

Examples of Parallel Program tasks:

  • Parallel search on an array.
  • Parallel search in games: e.g chess, pathfinding.

Distributed

  • Computers can be grouped together to collectively work on the same task.
  • These collections of computers are called Clusters.
  • Programming using such systems is called HPC, or High Performance Computing.
    • Google.
    • Simulation.

SMPD

  • Parallel programs most often involve SPMD (Single Program Multiple Data).
  • SMPD programs run the same code/program, but do so on some form of shared data.
  • These can be data passed from one thread to another, or small portions of a larger dataset on which some operation needs to be performed.
  • Thus the Multiple Data comes from these portioned up data from the same dataset.

Shared Memory

  • This is memory which is shared between multiple cores on the same machine.
  • Memory is shared above the cache level. Some libraries make caches shared too.
  • The data from a parallel program usually needs recombination/synchronisation, so shared memory is required.
  • Shared Memory is always available on any multi-core machine.

Threading Model

  • Why threads over Processes?
  • Threads can be thought of as Lightweight processes.

    A process A thread needs
    Kernel manages: Programmer handles:
    - Virtual address Space - Scheduling
    - Scheduling - Resouce Access
    - Resource access  
  • Threads can be spawned faster than processes and need less memory. They also share any resource available to their parent process.

Programming

Python Threading

  • Most languages have their own equivalent threading library.
  • We will use threading in Python for Concurrency.
  • Threads are more efficient for performing operations required by a program then spawning a new process.
  • Using multiple processes to do tasks within a single program requires IPC (InterProcess Synchronisation).

Exercises for this week

  • Download the exercise sheet for week one (exercise_c1).
  • This exercise will cover creating threads that run functions you will write to print numbers and text.
  • Once you launch your threads, you will join them.
  • Joining them attaches to the main thread (the parent program), causing it to suspend until any attached thread has completed.
  • The exercises will demonstrate some issues with concurrency that we will learn to solve in the coming weeks.

Subsumption Architecture

What is Subsumption Architecture

  • Reactive robotic architecture.
  • No map of the external environment, no memory of past actions.
  • Ideally suited to a real time concurrent system, fairly populer in AI.
  • Essentially you have a robot with the reactive abilities of a cockroach.

Process 1

  • Each possible action has its own thread.
  • All threads run all the time, each has control when that control is handed to it.
  • In the case of our assignment task:
  • The robot has a heirarchy of action handling threads that pass control up and down.
  • Robot vectors by default, till it meets an obstacle/encounters a problem it has a handler for.
  • The relevent handler is given control.
  • Error type, solution selected and frequency must be recorded.

Process 2

  • It should be something like this, with control passing between threads according to outcomes.

subsumption.png

  • No record is kept of past actions, and no lookahead to future events/outcomes occurs.
  • There must be a path from every action to every possible follow on action.

Example Scenario for assignment - 1

  • Move forward. If a wheel behaves differently, is it an obstacle or a change in surface density?
  • Simulate sensors by just randomly selecting a rock or surface change.
  • If obstacle, reverse x cm, turn some amount, vector again.
  • If change in surface density, test surface under all wheel, how big a change?. Is it big enough to be a risk?

Example Scenario for assignment - 2

  • Again, randomly select outcome for this choice, but weigh that randomness so you can demonstrate call home or not in several runs.
  • If too big a change, radio home and stop. If not, raise wheel, vector, lower wheel, repeat.
  • This scenario is simplified, since all you are actually simulating is the robot equivilent of pulling your finger back from a heat source to avoid damage.

Example Scenario for assignment - 3

  • Smarter control, such as whether or not to stop trying altogether and just ask for help, would be higher up the decision loop. So ignore that.
  • For preference your robot should be able to complete the vectoring often enough to demonstrate that your program works.