7. Parallel programming

Parallel programming

Necessary for parallel machines

e.g. many-core CPU, distributed systems

Useful for 1-CPU machines

Various parallel programming languages proposed

Parallel programming around us

Multitask OS

Browser, Word, etc. run in parallel

Full-duplex communiction

Transmit and receive data at the same time

c.f. Half-duplex communication

Hardware interrupt

User interface events

Hardware interrupt

Send a hardware signal to CPU and interrupt current process

Run a special program and return

Infinite loop can't finish without hardware interrupt

Web and parallel programming

Many tasks work in parallel

User actions

System output

Search in the background

Communication between server and browser

Complicated because many actors work in parallel

Parallel vs concurrent

Parallel

Multiple machines run in parallel

Concurrent

Pseudo-parallelism

Time-sharing

Preemptive multitasking and non-preemptive multitasking

Preemptive multitasking

Switch processes by hardware interrupt

Available on popular OS

OS takes care of multiple processes

Non-preemptive multitasking

Each process voluntarily give control to another process

A process give control to next process

Sometimes used in games and old embedded systems

Non-preemptive systems

Old system on a car

No OS

Only one process running

One program checks sensors and control parts forever

Primitive games

Infinite loop syncing with vsync/hsync video signal

Old PC OS

AppleII, Windows3.x, MacOS

All programs stop when printing

Old PDAs

Zaurus, Palm, ...

Difficulty of parallel programming

Debugging is difficult because of nondeterministic behavior

No strict run order

Programs sometimes works fine, and sometimes not

Difficult to prove that the program is correct

Program logic is complicated

Syncronization is difficult

Locking, starvation, scheduling, ...

Advantages of parallel programming

Use multiple machines / CPUs

Sometimes logic becomes simple

e.g. Simulation of many agents

Simple parallel programming

Unix pipes

% cat slide | grep pipe | wc

8-Queen

http://gyazo.com/942a93103f9ead8908fb3a49800ce68b.png

Easy to show solutions sequentially

Difficult to show next solution based on user actions

Separation of solver and user action

8-Queen

code:queen1.js

function setup(){

col = [];

qpos = [];

up = {};

down = {};

nqueens = 8;

var i;

for(i=0;i<nqueens;i++){

}

for(i= -nqueens;i<nqueens;i++){

}

expand(0);

}

function output(){

var i;

var s = '';

for(i=0;i<nqueens;i++){

}

console.log(s);

alert(s);

}

function expand(n){

for(var c=0;c<nqueens;c++){

if(n+1 >= nqueens){

output();

}

else {

expand(n+1);

}

}

}

}

Running 8-Queen on console

code:node.txt

% node queen1.js

04752613

05726314

06357142

06471352

13572064

...

Getting the result with other UI

User interface and parallel programming

Parallel pogramming is ideal for UI programming

Simultaneous multiple input

Mouse, keyboard, speech, etc.

Should be handled by different processes

Sudden error handling

Dealing with multiple users

Replace a user with a test program

Treat a user as a external process

Half-duplex communication

Data transmission is one-directional

Send data and receive data alternatively

Like a phone / tranceiver

Old computer terminal for big computers

Typing impossible while the system is working

Reset key for interrupt

Very bad usability

Like a single-track line

Single-track line

https://gyazo.com/9ddc4c16d201c1ca16136e5249628e4f.png

A keyboard for big IBM computers

http://gyazo.com/b8ae4735ce94e8abdecc5f1364ef34a3.png

Modern terminal

Full-duplex communication

Always acceput input

Okay to type ahead

Commands are executed sequentially

Full-duplex communication

Double-track line

Parallel programming required

e.g. Terminal emulator

The system should watch system output ane user input simultaneously

Double-track line

https://gyazo.com/c5f906543e7d6ef7696daa95f4885d33.png

Process vs thread

Process

Independent programs

Thread

Light-weight processes in a single program

Process

Independent memory space

Separated from other processes

Process switching / interprocess communication takes time

Therad

Multiple threads in a single memory space

Fast synchronization and data sharing

Popular on modern lightweight languages

Thread libraries

cthread

Available on Mach OS

pthread

POSIX Standard

GNU Library

Coroutine

Explicitly give control to other thread

c.f. Subroutine

Available on Modula-2, JavaScript

Example of coroutine

Using coroutine for 8-Queen

http://gyazo.com/3c4cf41a04404b42078db80de9c76486.png

Generator

New feature in JavaScript (ES6)

function*(){ ... }

Simple generator example

code:gentest.js

function* gfn(from, to){ // Generator function

while(from <= to) yield from++;

}

var g = gfn(1, 20); // Generator

for(var num of g) alert(num);

Task switching between generators

code:tasks.js

function* task1(){ // Generator func for task1

while(true) yield "I am task1"

}

function* task2(){ // Generator func for task2

while(true) yield "I am task2"

}

var t1 = task1() // Generator 1

var t2 = task2() // Generator 2

while(true){

alert(t1.next().value)

alert(t2.next().value)

}

Importance of synchronization between processes

Processes should not be switched at wrong places

Some resources should be handled only by one process at one time

code:count1.rb

count = 0

t1 = Thread.new do

100000.times do

count += 1

end

end

t2 = Thread.new do

100000.times do

count += 1

end

end

t1.join; t2.join

puts count

Results

code:rubyout.txt

$ ruby count1.rb

142012

$ ruby count

142597

$ ruby count

124374

$

Success example

http://gyazo.com/cbad66d3f8e1cd3837111c78ddc43352.png

Failure example

http://gyazo.com/2eaec9c77a7c9c36ecbb4b2baffa3aba.png

Critical Section

Problem caused if executed by multiple processes at the same time

count += 1

Should be executed atomically

Corrected version

Only one process can access "count"

code:count2.rb

require 'Monitor'

lock = Monitor.new

count = 0;

t1 = Thread.new do

100000.times do

lock.synchronize do

count += 1

end

end

end

t2 = Thread.new do

100000.times do

lock.synchronize do

count += 1

end

end

end

t1.join; t2.join

puts count

Executing the corrected version

code:runcount.txt

$ ruby count2.rb

200000

$ ruby count2.rb

200000

$

Whe do we need synchronization?

In the OS

In the application

e.g. Wiki

Conflict if edited simultaneously

Interesting synchronization problems

Dining philosophers problem

http://gyazo.com/c1099adbf7a3d668e444a29afd772594.png

Possible problems

Deadlock

Resource starvation

e.g. Someone cannot eat anything forever

Primitives for supporting synchronization

Atomic operation without hardware support

http://gyazo.com/345ca496d5efc523a8bfe62a84d59f32.png

Hardware-based synchronization support

Set a bit if test succeeds

Only one CPU succeeds the test

Lock instruction

Disable hardware interrupt at next instruction

68000, 80486, etc.

Fetch and add

The Art of Multiprocessor Programming

https://www.amazon.co.jp/dp/0123705916 https://gyazo.com/031fb9eecd436f8249c1076e57cd5227.png

How to wait for a resource

Busy-wait

Check the condition forever

Wait for input, condition, etc.

Very inefficient

Should be switched to another proess

Synchronization primitives}

mutex

Semaphore

Monitor

mutex

"mutual exclusion"

Wrap a critical region

Synchronization primitive (Dijkstra)

Control entrance/exit of critical region

http://gyazo.com/c565aed30ead1e39bb5d8c1f012a9bc2.png

Semaphore structure

Integer "s" and a list of processes

P instruction

code:p.txt

(initialize s)

if(s==0){ put the process into 'waiting' queue }

else s = s-1

V instruction

code:v.txt

if(waiting) make one process running

else s = s+1

P and V are atomic

Binary semaphore / counting semaphore

Semaphore features

Various synchronization possible

Programming is complicated

Treat critical region as a block

Introduced by Concurrent Pascal

Available on Java

Monitor example (Ruby)

code:monitor.rb

require 'Monitor'

lock = Monitor.new

count = 0;

t1 = Thread.new do

100000.times do

lock.synchronize do

count += 1

end

end

end

t2 = Thread.new do

100000.times do

lock.synchronize do

count += 1

end

end

end

t1.join; t2.join

puts count

CSP (Communicating Sequential Processes)

Synchronization by message transfer

Communication between sequential processes via communication channel

No shared memories

Parallel languages

Occam

CSP

Concurrent Pascal, Edison

Monitor

Modula-2

Coroutine

Erlang

Asynchronous message

Standard language + parallelism

cthread / pthread

Ruby thread

Java thread

Generator

Linda

Interprocess communication

Shared memory

Message communication

Synchronization and communication

Synchronization itself doesn't mean anything

Some data should be exchanged

Integration of synchronization and data sharing desired

Linda

Share tuples (data) in a shared space

4 primitive operations for data exchange and synchronization

Linda

http://masui.org/5c79a78e3de1dcec20999cedfc5ddfad.png

8-Queen on Linda?

Input / output / calculation can communicate via TS

node-linda

Linda server running on standard HTTP

Getting sensor info

code:sensor.js

setup = () => {

createCanvas(400,1000)

// connect to node-linda server and create a tuple space

server = "//linda-server.herokuapp.com"

socket = io.connect(server)

linda = new Linda().connect(socket)

ts = linda.tuplespace("masuilab")

y = 0

linda.io.on("connect", () => { // connected to Linda server

ts.watch({where: "delta"}, (err, tuple) => { // wait for tuples

if(y > 600){

clear()

y = 0

}

y += 20

})

})

}

Rinda

Linda implemented in Ruby

by Seki-san

Easy to use on Ruby

Other languages not supported

Programming in Rinda

code:rinda.rb

require 'rinda/rinda'

require 'delicious'

TS_URI = 'druby://localhost:12345'

USER = 'masui'

ts = DRbObject.new(nil,TS_URI) # connect to TS

while true

register(USER) if val > 4.0

Linda implementation on a Web server

RocketIO

Ruby library similar to Socket.io

Socket.io = communication library on Node.js

Flexible communication between server and client

Server

Client

var io = new RocketIO().connect()

Use an instance

io.on(“eventname”, callback)

Receive data

io.push(“eventname”, data)

Send data to server

Example: Controlling browser from a special device

Process 1

Read the input device and send to TS

Process 2

Read the data in TS and control the browser

Parallel programming and other paradigms

Distributed programming

Object-oriented programming

Parallel OO programming

State transition programming

Extended state transition diagram, Petri nets

Visual programming

Diagram and schematics imply parallelism

Summary

People tend to avoid using parallel programming

Modern languages support simple parallel programming

Generators, etc.

References