Transcript 256x256 512x512 1024x1024 - California State University, Long

Multicore Computing
Using Erlang
Art Gittleman
California State University Long Beach
[email protected]
Motivation



David Patterson – 2006 article
The number of processors per chip is expected
to double every two years
Educating faculty to train students in
concurrency is not a trivial problem
Using Multiple Processors


Most languages
Shared memory – must protect against
simultaneous modification


Erlang

Asynchronous message passing

Create processes

Scheduler uses available processors
Erlang
Functional programming language
Developed at Ericsson -1993
Open Source, runs on Windows, Linux, Mac
Applications
Amazon SimpleDB
Facebook chat (70 million+ users)
Teaching Erlang

Survey of Programming Languages

Five week module on functional programming

Used machines with two cores

Basic Erlang and some concurrency

Advanced Programming Languages

Ten-week unit

Used Beowulf cluster, 30 processors
Erlang Intro

Binding variables

Uses pattern matching

X = 4.
binds X to 4

Y = X + 2.
binds Y to 6

X = 3.
error – X bound to 4

Z + 1 = Y.
binds Z to 5
Data Structures

Tuples – fixed size

X = {hat, cat, fat}.

{A, cat, fat} = X.

binds A to hat
Lists – variable size

L = [3, 4, 5, 6].

[X | Y] = L.
binds X to 3, Y to [4,5,6]
Functions

Recursive definition

-module(append).

-export([append/2]).

append([ ] , L) → L;

append([H | T], L) → [H | append(T, L).

Concurrency Primitives


Create a process
Pid = spawn(Fun)
% in new process





% Fun executes
Send a process a message
Pid ! Message
Receive a message
receive … end
-module(times2).
-export([run/1]).
times2() ->
% executed in a process
receive
{From, X} -> From ! 2*X, % send back ans
times2()
end.
run(Num) →
% run(10) returns 20
Pid = spawn(fun times2/0), % create
Pid ! {self(), Num},
% send
receive
Result -> Result
end.
Three Assignments
1. Write three recursive functions
Generate a list of squares of random numbers
Sum two lists, element by element
Count the number of items < 1 in a list
2. Estimate pi. Send number of random trials to a
process that computes pi and returns result.
3. Estimate pi using four processes. Speedup
shown with two-core machines
Higher-Order Functions
•
Map
•
L = [1,2,3,4].
•
lists:map(fun(X) → 2*X end, L).
•
% returns [2,4,6,8]
•
List-comprehension
•
[2*X || X ← L].
Ten most frequent words
From Adam Turoff, Haskell article
•
Used text of Emma by Jane Austen
•
Develop simple functions to find the ten most
frequent words
•
Read text as list, split into sublists of equal
words, create sublists of [freq, word] pairs,
reverse sort, return top ten.
•
Many functions such as 'sort' are provided.
Strassen Matrix Multiplication
•
Recursive, more efficient than standard
method
•
NxN matrix requires 7 N/2xN/2 multiplications
•
Used seven machines on a Beowulf cluster.
Compare 14 processors to 1. Time in seconds
•
256x256
14 |
1.5
•
1 |
14.4
512x512
10.0
1024x1024
65.7
102.5
720.1
Conclusions
•
Erlang was easy to use for concurrency.
•
The programmer spawns processes and the
scheduler uses available processors either on
the same machine or distributed.
•
Erlang fits well in a programing languages
course.