in our lecture on numerical methods
today I'd like to do a small coding
session and we discussed the Monte Carlo
methods and somewhere in the middle
there was this little experiment
described how you can use a Monte Carlo
approximation to approximate P okay so
you find this in the script the thing is
that four times the moniker integral of
the indicator function on a two
dimensional random vector ax so
eggs and why
uniform on zero one gives you an
integral and this integral is actually
equal to P so we can approximate P by
calculating this on the counter in
sequence and the idea behind this was
also in the script
just to have you this if you sample
random points in the unit hypercube then
the probability to be inside the circle
is the ratio of the area of the circle
with respect to the area of the unit
hypercube okay and so then we do the
transformation to just the upper
secretary of the quarter from 0 to 1 and
then we get four times where this
integral okay this gives us P okay so
and then later in the script we have the
remark that Monte Carlo
is a very good technique if you like to
perform parallelization so why is that
okay so there was the experiment here
that we should use this algorithm of
approximating P and parallelize it say
for example to make use of multiple
processor cores so I would like to do a
small excursion on parallelization so
teach you a little bit about this and
actually you will see that with some
frameworks some Java frameworks it's
actually very easy it's just writing one
additional board and you are done
okay so the point here is that the Monte
Carlo method uses a sequence of iid so
it uses a sequence of independent
identically distributed random variables
and the important aspect here is the
independent so if the random variables
are independent actually this directly
implies that the calculations we have to
perform on these samples are independent
so each individual calculation
can be performed independently so we can
very easily split the vac into say
smaller parts and then distribute these
smaller parts to their own processor
core or like on the GPU - or to a GPU
set okay so the idea is that we use a
random sequence and we just split it in
two blocks so say we have blocks of size
M so then we have J times M plus I
from i from 0 to m minus 1 so each
subsequence has m elements and then we
have K such sucks subsequence such that
K times M is the total number so we have
K sub sequences J from 0 to K minus 1
okay and then we can perform a Monte
Carlo integral on each of these sub
sequences calculate the sum and then the
total sum is just the sum of the
individuals okay so to implement this
parallelization actually sometimes there
are frameworks that help us in splitting
up things so actually we don't even have
to do this splitting so how do we get
these sub sequences so we have several
options of generating such sub sequences
so first of all if you get back to this
slide you see here that
this sequence here starts at XJ times M
plus zero and
hence at XJ times M plus n minus 1 so if
we would like to do Monte Carlo we would
like to start all the sub tasks at the
same time so actually we like to have a
sequence where we can cut out a sub
sequence and perform Monte Carlo on this
sub sequence so if you have for example
1,000 Monte Carlo samples so n is 1,000
and you would like to have 10 sub
sequences each with 100 Monte Carlo
samples you would like to have a
sequence that can start at X 100 X 200 X
300 and so on so in order to do this a
sequence where you can calculate the
number at a certain index directly from
that index has a certain advantage
recall that for linear congruential
generator
we generated the next point from the
previous point okay and so if we would
like to start at X 100 maybe we have to
run from X 0 to X 99 to actually get the
starting point which is a bit useless
because it means that we have to
generate all other random numbers in in
a sequence so we cannot paralyze the
general generation of the random numbers
so sometimes this is not an issue
because the generation of the random
numbers is fast so you first generate
all the random numbers and then you
calculate your function f of X when you
do the Montecarlo integral so sometimes
you only paralyze the evaluation of the
function but you do not paralyze the
generation of the random numbers if you
are sold by going from the bottom
through the top if you are in the
special situation that your secrets
calculates an element X I explicitly
from the index so like for example in
the funda coreboot and Horton sequence
so then you can very easily paralyze
this because you just say start at a
certain index if this is not possible
sometimes there are certain random
number generators that have some kind of
skip ahead possibility so you can find a
formula that generates element 100 from
say element 0 so you can find a formula
that generates an archer step so you
first have to do
this step and if this is not possible
say for example you have a pseudo-random
number generator for example like math
and twister and you do not find a
formula that allows you to do this skip
ahead then there is a dirty trick you
can do yeah but it's maybe not
recommended so if the sequence is
generated from a seed
yes so there is some initial value then
you can consider to generate different
sequences with different random seeds so
this works there
you know it's but it's maybe not an
accurate solution because if you just
consider that your sequence is like that
okay these are now your numbers you
generated and you are Montecarlo seed of
the sequence is here this initial value
this is the seed the starting point and
it's generating the next point from the
previous point and then you choose a
random lis other seat and here you
generate now a different Monte Carlo
sequence then it may happen by chance
that actually your Monte Carlo seed is
identically to some number that appeared
early in the other sequence which then
means that actually the other sequence
already contains
these numbers and you see that the
second sequence only has three
additional points so the gain in
accuracy is a little bit lower okay
but still this technique of using random
seats different seats to generate a
sequence
yeah so this is the seat
and it may happen that the seed appears
in the other sequence so it might happen
there two sequences
overlap overlap eloped okay so these are
some options on how we can parallel eyes
and now before I discuss something here
on the coding let's do a code session on
this so today I like to do coding with
you and I will use two to api's two
frameworks this Java stream API and the
execute offender
okay so let's go here and create a new
[Music]
experiment a new class so let's call
this Monte Carlo integration experiment
or Monte Carlo integration then
experiment I would like to have a main
method and I just implement some ways of
paralyzing this approximation of P here
okay so first as a benchmark maybe I
would like to know the analytic value so
let's define this as a constant here
so this is our analytic value okay and
later I will try to compare this absurd
has to go here compare our numerical
solution with this so
the first one is to use a heart and
sequence and let's define the number of
Montecarlo samples let's be a little bit
bold I would like to be twenty million
one two three one two three this is 10
to the power of seven well let's use 10
to the power of eight 200 million so
this is two times ten to the power of
eight and with 20 to 200 million samples
I would like to approximate P so let's
test with the Horten sequence and I
would like to test this with the Java
stream API and it may be first I do an
example where we are not using the
parallelization so let's call this
sequential okay I create dedicated
masses to do this okay so we have a
little bit more nicer overview in our
kochiya
okay so approximation of P using Monte
Carlo with the Horton sequence so the
Horton sequence we had it in our course
before so in random numbers we had the
funder corporate sequence and the Horton
sequence so Horton sequence is just a
funder corporate sequence where each
dimension has a different base and the
funder corporate sequence was this
algorithm here that
performed the calculation of the old
number of under corporate number by form
directly from the index okay so we have
a sequence of indices and we can
directly calculate the number from the
index so I create a stream so a stream
is just a sequence in in this framework
I create a stream of numbers from 0 to
number of samples so if you look here
this first one is included the last one
is not included so this is just 0 to n
minus 1 ok then this stream I would like
to apply a function that map's each
index on a floating point double number
so I use here map to double and the
argument should be a function that map's
an integer an integer to a floating
point double number ok so how do we
calculate this floating for double
number so first we calculate our hand
and vector so we calculate x and y so X
is 2 times the port number so
Horten sequence George let's part this
that's yours
a heart in sequence from here no obvious
wasn't any missing that's what's the
reason we cannot find it okay and this
this function get heart and number four
given base and I pass the index I and
then the base so we was base - for the
first time ention and we was base 3 for
the second dimension so horton sequence
is between 0 & 1
i subtract 1/2 then it's between minus
1/2 and plus 1/2
i multiplied with 2 then it is between
minus 1 and plus 1 so x is 2 okay so
next number is the horton sequence for
base 3 so we generate a two dimensional
horton sequences with base two and three
for the two dimensions next thing is
that we have to check the indicator
function so we integrate from 0 from
minus 1 to 1 in both dimensions and the
next thing is that we have to calculate
F which is the indicator function are we
in the unit circle or not so if x
squared plus y squared is smaller than 1
we are in the unit circle so we return 1
otherwise we return 0
okay so this maps the sequence of
integers to a sequence of indicator
function values which we then just sum
up okay so this is now on our Monte
Carlo some so we have to divide by the
number of symbols so divided by the
number of samples and actually the
integral is just as we just transformed
here two times so that the new DX is two
times the old DX so we have to multiply
by four okay so that was our little
integration problem and let's print out
the result so we are using here a
sequential and the Java stream RP and
what is the error the error is P orchard
minus P analytic is Tierra okay so let's
try if this box so I run this little
program okay so now this takes a while
you see here processors are working a
little bit now but not too much you are
not not everyone is here busy
hmm maybe I should have got used here
the number of samples okay so we get a
10 to the minus 6 and it took a few
seconds
at reasons we like to do paralyzation i
would like to know how long it takes so
if we like to have a half measure for
time we can ask here the system for the
current time in milliseconds before we
do the calculation and after we do the
calculation okay and then we calculate
the time in seconds as the time and -
the time start converted to a double
divided by 1000 okay and we can prevent
in addition here maybe the time that it
took to calculate this
Monte Carlo integral okay so maybe add
it to use here a little bit
the numbers 2f the result a little bit
faster okay so you see this took here
five seconds so if I go back to 20 it
will take maybe 20 seconds to calculate
this okay so wait while it's running
let's do this now in parallel okay so I
just copy this code here I rename this
with stream say parallel and here on the
top I also call this other test which
performs the calculation in panel okay
so now it's actually in the same code I
haven't done the parallelization yet so
and I would like to show you how easy it
is to colonize this because you can tell
the stream API that he should perform
calculations in parallel and actually
you can also decide when he should do
this so here he is generating a stream
of integer numbers and I would like to
tell him after you have generated this
everything that comes after this can be
done in parallel and you can do this by
just adding here the Verte parallel okay
actually that's it yeah so this code is
now performing this calculation here in
parallel okay so let's print this using
stream so this is parallel
oops so let's check how long it takes if
we perform it in parallel so I run the
program
okay and while it's running you see the
reason why he can easily paralyze this
is that the stuff which is inside here
is completely independent yeah so for
every eye he's doing something but the
other eye doesn't need to know what he's
doing okay so maybe I add a few more
dots here and so on to to have the
output a bit nicer and you see that if
you now look here in the lower left on
the processors the first run is
currently running sequential so it does
not use up a lot of my processors
actually this conference here takes
takes up consumes up some time and then
it just consumes say in in in some one
processor it took 24 seconds now every
processor is in use you see
and it took five seconds okay so we get
a performance increase of say a factor
of five No roughly four point something
reason is that he does not have all
eight process was and this may be a
small overhead and doing this
colonization okay
so there was a good question in the chat
how does he know how to split up the
stream so how many numbers of compute
tasks is he using and this is actually a
very good question so um he can check
how many course
how many parallel CPUs or how many CPUs
the machine has and he uses
as many worker threats as I have cause
okay so and then he is cutting the
problem into smaller packages but in
this cutting there is maybe an issue
remember the code of the Harton sequence
or the funder corporate sequence if you
look at the code of the front Accord
sequence then you see that he is
calculating the number from the index
and actually this algorithm takes longer
for larger indices so if you now cut
your sequence into smaller packages it
may happen that one package takes a lot
longer than another package which means
that for example if you have eight
packages of work and seven of them just
need one second but the last one needs
10 second then in some if you do it
sequentially you have maybe 17 seconds 7
plus 10 but if you paralyze it you have
10 seconds because it takes the time of
the slowest package and you just have a
factor of 1.7 performance and increase
in this engine example which is a bit
disappointing if you had eight cores
so the question how he is actually
splitting this up is important and this
may be a reason to use another framework
where you have more control on splitting
this up you can of course use more
threads which which somehow also will
[Music]
increase this parallelism you know but I
have another example where we need more
control on how to split these tasks
so actually internally he has some some
logic to split this up I can send you
maybe some some reference where you can
read about this I would like to make
another example let's do the same with
smears and twister for Mersenne twister
I do not have skipped ahead at hand yeah
so for example I would like to do this
technique of starting Mason twister with
different seats with different
multicolored seats
but actually I have a small question why
not just use one Mason twister for all
the parallel calculations and everybody
just picks from the sequence a number
and performs the calculation and then
another one picks a number and performs
the calculation so actually all the
parallel calculations could share the
same method twister and this is actually
OK for Monte Carlo because the order in
which we actually sum these sequences up
does not matter so actually this example
here of splitting a sequence in these
packages it's just one possibility we
could also just have a sequence which is
index 0 1 2 3 4 5 6 7 and then we have
index 8 9 10 and the first thread takes
index 0 and 8 and so on here are 16 and
the next one takes index 1 and even
sometimes they skip one and they just
consume the whole sequence that's sir
possibility which is actually not on
this slide you know just try and use the
sequence in parallel now so maybe I
write here one more alternative if the
sequence allows this
we can make a single sequence generator
so you was a singular sequence generator
from parallel slits
okay so in order to be able to do this
to generator has to be some kind has to
have some kind of property yeah that
allows this this is sometimes called
thread safety so generator has to be
thread safe
you
okay and this is a nice example which I
would like to show you next so next
example is test this integration of P
with the Mezen Twista okay so uh let's
you are quite a new test here let's call
it test Mills end with stream maybe I
also do first the sequential version
okay so the P medicine the approximation
with the Mason twister okay I have some
generator maybe I'd like to use here the
same code as here above so with the
integer stream just to make it more
similar you can also directly generate a
Babel stream with some generator
but to make it more similar let's just
copy this code here so you really see
that it's a fair comparison because we
are doing the same thing again so let's
call this here P MSN and okay and I
remove the parallel so it is sequential
and here inside I would like to create
this random number from a Mersenne
twister and the Mayerson twister
implementation which i would like to use
is that of Apache Commons math so there
is a library that has a Mersenne twister
implementation
so let me write to see explicitly it so
that you see which kind of
implementation I use okay and the
argument here is some seed of the
Mersenne twister so let's use some
number as an initial value of the
generator and we have here a random
number generator and you know that the
Mersenne twister is a soy de vendor
number generator so in order to generate
a two dimensional sequence from a one
dimensional sequence we can make the
click to populate the random vector one
by the other now so the first element is
here the random number from the sequence
generator and then we just pick another
independent so iid simple number for the
second component so very easy this is
the medicine twister implementation okay
you see here the index is actually I is
not used huh
so it's maybe a bit strange to use here
this integer sequence and then transform
it to the dab and never use the I but
that's just to keep the example similar
to the previous one so this here is an
SN it is sequential and as is using the
stream API okay so let's check how this
performs so I have to do this test here
I call this test here with our twenty
million twenty two hundred million 200
million sample points okay so let's try
so maybe I should cut out the first one
because it is always taking twenty
seconds but again you see now the first
approximation is running sequentially
the computer cause are not very busy
yeah you will print out the result and
after that the second simulation run
starts in parallel and the computer core
we'll become very busy now for a few
seconds now and he has the result after
five seconds okay now it's not busy
enough the computer of course are not
busy we are in the example of methane
okay and it takes seven seconds so maybe
I move here a few points away one two or
three okay and you see that mess then I
actually took seven seconds without
paralyzation yeah so it is a factor of
three faster then using the heart in
sequence and this difference will
actually increase because the Horten
sequence becomes slower and slower for
higher indices and also the Horten
sequence is now two dimensional if you
use a three dimensional the difference
will also be even more prominent yeah so
you see now it is not parallel this is
the methane calculation currently
running and it takes seven seconds you
also see here that the pseudo-random
number generator is a bit
less accurate no so if you go back here
you see this is 10 to the minus 6 for
Holton 10 to the minus 4 for the math
and Trista yeah so if we go back here
and I'll make a small remark here so we
perform this simulation with n equal to
2 times 10 to the 8th which means that
Monte Carlo now so Monte Carlo is 1
divided by square root of n which is
approximately one point four so one
divided by one point four which is
approximately 10 to the minus four which
is actually what we see here 10 to the
minus four
so for pseudo-random number generator
and for the Horten sequence we had log n
to the power of T divided by n so
which is approximately 10 to the minus 6
for Alton okay that's nice now so we see
that actually the mathematical result is
coming out exactly from from this so you
see there's a factor of 100 between the
two in accuracy but there's also some
kind of a factor of 3 something in the
performance and this ratio will change
if you have higher dimensional problems
and some at a certain level monitor car
was with pseudo pseudo-random number
generator this is better okay but look
that this is Mayor Zen with our
parallelization so we can become even
faster so let's do mayor send with a
parallel stream okay so I just do a new
test here called it's parallel I call
this test here true
perform the calculation okay and I do
this tiny little change that I call here
please perform all the calculations in
parallel on your computer on your
threads on your course okay so let's run
this little program so in order to save
a little bit time yeah we know by now
that the sequential Halton takes about
20 seconds let's comment this out so I
only run the other examples so he will
start with parallel Halton okay so he's
getting fast
okay so parallel Horton and I get some
kind of ever okay so that's strange
so where does this arrow come from so it
must come from our new part of code and
so let's comment all the others out and
run again so I run again
you
oops I
I made a mistake I did the parallel here
in the sequential and not here and the
parallel okay so here here it should be
this is our court where we want to do
the power because that was just a
sequential okay so if I now run this
part of code here just messin streamers
parallel we get an error
so if I remove the word parallel the
error is gone it's calculating the mess
n sampling in sequential so 6 seconds 10
to the minus 4 if I add the word
parallel
I get some stranger
so let's investigate this error so you
see there is some index out of bounds
exception here a strange number 624
actually this number reminds us of the
dimension in which Mersenne twister is
uniform distributed at most so the
highest dimension we can we can we can
use or we should use and we get this
index out of bounds exception if we run
in parallel and this problem is due to
the fact that actually the Mersenne
twister application implemented is not
set safe so there is an issue called
sketch safety which is important so if
you have multiple threads yeah so
multiple parallel worker threads which
access say a common variable so some
counter was the Montecarlo seed or
whatever and they access this variable
in parallel then this may lead to
inconsistent States for example you have
say some variable where you count
something one sweat is counting up then
the sweat is assuming that this variable
is one larger than the previous value
he's performing some calculations which
used his variable but then another
parallel set is also counting up then it
may happen that the first part of the
first set has used in our I plus 1 and
the second part uses I plus 2 but he or
he assumed that nobody had changed this
variable so there are some basic rules
how you can avoid this but before we can
discuss this I would like to actually
show you what has happened here so you
see there's this index out of town
exception here in the implementation of
the Apache common math math and Twista
and he tells us that this is in unison
twister in line 252 if I click this he
will jump to the court where this
happens okay so this is ugly code that
performs the messin twister calculation
okay and you see that there is some kind
of array this array empty here which
generates the next value and actually
Mason twister works in the following way
that he will generate 624 values in a
single block so he's not generating one
random number from the previous one he's
generating 624 random numbers from the
previous 624 random numbers so actually
it's like linear congruential random
number generator with a very big number
okay so he's storing these 624 numbers
in this array so whenever you ask him
he's checking is your current index
larger than this number so if you over
here over this number you see that this
is 624 yeah so if this number is
actually larger or equal so the he's
beyond the 624 numbers
yes then he will generate the new
numbers and at the end he sets the index
to zero and you can ask for the next
numbers so if you are below this number
you will just get the next number okay
and now you immediately see maybe what
happened here we have parallel threads
in parallel asking for the next number
okay so the first set was here and the
number was may be smaller than the end
now so he was not asking for the next
one so the next thread was here and the
number was also smaller than the end so
he does not generate a new one and he
would like to ask for the next one so
now assume that your index is 606
hundred twenty three and two thread walk
along this in parallel so they will skip
this part here and there are two threads
asking for this number but there's only
one number left now so the next set is
actually seeing here the increment from
the previous thread and he is requesting
a number which did not exist so to avoid
this problem you have to actually allow
only one threat to enter this piece of
code here okay so this can be done with
a verge called synchronize so this is
maybe in a most potent way of fixing
this issue so you can
denies the excess to a threat then the
exit access to to available by using the
word synchronized so this is that only
one thread is allowed to actually
perform this modification and then when
it's done the other set is allowed to
enter this code so if the threads need
to modify a common shared field or
object so in our case this is the
counter inside the SN Twista then the
access has to be synchronized there are
other tips how you can avoid such
problems for example the good thing is
that to use only read-only access if
possible then if you do not modify a
variable it should if you just read it
this problem does not occur or if you
have some kind of counter and it is
possible that every thread has its
individual encounter so the variable
exists in every thread on its own so say
this me this is sometimes called that
the variable is thread-local now then
this problem also does not occur because
every set has its own counter and they
do not interfere I will show you the two
solutions of introducing a thread local
and of synchronization let's try it with
synchronization okay so
maybe I'm a bit reporter and I add here
a synchronized around this block so this
means that actually only one thread is
allowed to enter this block here this
solution is actually a bit stupid but I
just want to show you then it works so
we have a parallel execution but I do
not allow that this critical part here
is calculated by two threads
simultaneously because inside the messin
here next double so there is this
function next called and two threads
modify the counter at the same time not
checking that we are very close to the
bound now because we have already passed
this point here and which then results
that one thread is beyond the size of
this array okay so if I now run this
experiment yeah so maybe I can also
enable all the others here so we maybe
not all xxii Horten sequence sequential
can be may be skipped but the other ones
are may be fast enough so we have fought
in parallel with five point second five
point seven seconds we have may ascend
with seven seconds ten to the minus four
using sequential and now comes to
parallel and what you see here that is
the process was a little bit more busy
but actually he is not using up all the
processors and the reason is that
actually this verge here blocks the
parallelism because this plot here can
be only entered by one thread at a time
and you see that now the time is almost
s verse as sequential halt
it's not only that we blocked the
parallelism so we have became sequential
it's that we have now so much overhead
in parallelizing and then we are
removing the parallelism that it is
actually slower so maybe you say that we
only need to block the generation of the
random numbers so let's pluck only the
generation of the random numbers and the
rest of the calculation can be performed
in parallel which would look like this
so you have a random vector ax the
generation of the random vector is not
allowed to be parallel okay
but each butBut the calculation then if
you are inside the unit cube is allowed
to prepare there so in our example this
doesn't cure a lot because actually the
calculation of are we inside the unit
cube or not is so fast so it does not
matter in other problems this is maybe a
good solution to have a synchronized
around generation of the random numbers
but still it is here not a very good
solution because it takes much longer
you know
then actually the sequential version
this the sequential version is five
seconds here it is still 1970 seconds so
maybe next idea is just to synchronize
each individual s XS which would be like
this okay does this help
so I synchronize the access to the
Mersenne twister yeah but okay
I can I can tell you it does not help
okay so you see that actually with this
implementation of Mayerson
using the stream API it's very difficult
to perform a parallelization
I wouldn't say it is impossible with the
same API the following trick can be also
done with the stream API but I would
like to show you now an alternative
where I perform a parallel execution
make sure there should be parallel here
okay so let's let's go to the cleaner
version of the code here where the
synchronize was around this looks like
bit a bit nicer okay so I would like to
show you an alternative framework so
here on our list
there was distress Java stream API so it
is very easy to parent an eyes with a
stream parallelize the stream by just
adding the word parallel but the code
inside has to be independent of each
other
and has to be set safe okay so the next
thing is an execute the execute of
framework and Java futures so let's
write this so I would like to test my
sin with the so called executor
framework for a given number of samples
okay so in the executor framework you
can get something which is called the
executor and you can submit tasks to the
executor and the executor is performing
all the tasks in parallel okay so I
would like to split now the number of
tasks by hand so let's define some
number of tasks so let's say I have 100
tasks
I would like to split my samples in 100
packages so I have some number of
samples per task so the number of
samples per task is just the number of
samples divided by the number of
samples divided by the number of actually at this point you have to be a
actually at this point you have to be a
bit careful yeah that this integer
division has no remainder
otherwise you have to increase one
package by this size of the remainder or
have a specific package but in our case
I don't care about this now because I
know the integer division is is this is
fine so there is something called an
executor service
and they are different
such executors sorry executors well I
see not liking my my ass okay III need
executors I don't know maybe I write it
by hand anomaly drugs okay so there are
different such as to execute just and
that's for example here the fixed sled
pool executors yeah
and you can specify how many parallel
because how many parallels lets you use
for this calculation you know so let's
have here some number of threats and how
many threats would I like to use maybe a
good value as guidance it's the number
of processors just use as many parallel
workers as you have processors you can
ask for the number of processors by
using runtime get one time available
processors so this is our value of the
number of threads so now you can submit
a working task to this executors so what
do I like to do as a task I would like
to calculate the approximation of P with
Amazon twister but each melon twister
for the task should use a different seat
so actually on our list I used the first
trick which was on our list use
sequences with different seat wasn't
recommended but it is here may be a way
to paralyze the pseudo-random number
generator
so for this let's write a small function
get approximation of P with methane
which uses a given seat and uses a
number of samples okay
and then I submit this function with
different seats to the parallel skirts
so let's first generate the Mersenne
twister so let's use this non set safe
implementation from cut party common
math and let's use this seat which is
here our argument is the seed of this
random number generator okay so now we
have this random number generator let's
calculate P from this maybe I just
copied the cord which we had here and so
it is just fair yeah
okay I generate an in-stream with number
of samples not parallel maybe to double
and I do not need to synchronize here
because every thread has its own local
version of the lesson so they are
independent okay and I returned this
number okay so now I have here a
sequential calculation of the lesson
okay
maybe also you you you can do the
traditional one without the street if
you like to see the court without the
street you would right here Montecarlo
some then you have an integer loop
okay or instead of some I can just count
the number of samples in unit circle
okay then you have an integer loop which
generates the random number and counts
the number of so distance yet zero sorry
that starts at zero and counts up if we
are inside the unit circle this would be
the version without stream and the value
which should be returned is four times
the number of samples in the unit circle
divided by the number of total centers
okay so either way he works
yeah so this is now the approximation of
P using a melon twister pseudo-random
number generator with a given seat so
now I continue here and I would like to
have different such jobs with different
seats so actually I use a random number
generator to generate the seat this
random number generator needs also some
Montecarlo seat some seat and I use the
Java random for this okay so and now
let's submit to the executor our drop
so you write executors dot submit and
then you can just submit some tasks yeah
so this task takes no argument but
returns a value okay so the value is the
value of P approximated so let's get the
seat here see it is random seed dot next
long okay so now it works and for this
seed I would like to submit now a task
ok the task is just a function with no
argument so you do this break it open
pack it close and it returns a value
namely it returns the approximation of P
with methane using this seat and here it
uses number of samples per task ok this
submits one such task to the executor so
actually we would like to submit many
tasks so how many tasks would we like to
submit number of tasks is the number and
I created loop around this which submits
many different tasks to the executor so
now the executor takes these tasks and
works on parallel ok so you see this
doing this parallelism by hand without
the stream is a little bit more work
yeah but actually we have much more
control because we can explicitly
specify how many tasks he should use and
you can also specify how the tasks
should be split now this is like
advantage ok so where do we get the
result ok the result is actually coming
back here so I need some list
of results where I collect all my result
okay so the result from this function is
a double okay
but actually this cannot work because if
I would like write this line he would
have to wait for the executor to finish
to get the result so I cannot get the
result immediately but I can get
something which gets me the result in
the future so I get a handle to it and
later I can ask for the result and
actually this object which I get is
called
a future so a future is a value which
you will get at a future point in time
now so you get a handle on this value
and you can specify what kind of future
is it is a future value being a double
okay so this is what this executor
returns and I create here now a list of
such future values which are in the
future a double okay
and let's put this result here in this
list okay so this is
the first step distribute the vodka task
so we distribute all the tasks so now
all the tasks ran in parallel and we can
ask for the results so the next step is
collect the results so we can collect
the results in some so we do a loop over
all tasks again know and collect the
results so this is some is some plus
result besides I would like to have the
result corresponding to the first second
third and so on tasks this object here
is the so-called future and from this
future I can now get the double value
okay and here an exception can happen
yeah so I have to declare that an
exception can happen if the skate was
interrupted okay but let's don't care
about this so then our approximation is
a sum of different P approximations and
we just take the average of this so this
is sum divided by actually now divided
by the number of tasks so I take the
average of say 100 approximations each
approximations being the average of 2
million simulations
okay so that was a little bit lengthy
but it's now an example of calculating
this approximation in parallel using the
executor okay let's also calculate the
time yeah so the time in seconds is the
start time the end time minus the start
time so let's calculate here time end is
the current time in milliseconds and
also time start before we do all this
stuff here is
the current time in milliseconds No so
let's do it here so we can measure the
time how long this takes
so I hope I wrote everything correctly
maybe again the code is not so long yeah
it's just these lines and it has two
parts first we distribute all the
calculations second we collect all the
results these calls here run as in
Chronos Li in parallel so i can submit
more tasks and again and he's just
collecting the tasks and working on it
this call here is synchronizing so this
call is waiting for the task to finish
but at this point we can wait for the
first task to finish because all the
other tasks are already running and it
also does not matter if the second task
ends before the first task before or if
because he will then wait for the first
task and then he immediately jumps to
the second one and sees the result is
already there now so this loops here
they it's as long as the slowest task
which is what we need because we need
all the values so let's add our last
test here test messin with executor to
our list and let's keep fingers crossed
and run this program
so now we do a test of the Horten
sequence approximation of pea
sequential in parallel using the star
chalice stream API we do this
same with absurdo random number
generation later with Zen twister
sequential and parallel and then we use
the executor framework you see the first
sequential one did not use all the
processors now we are going in parallel
we were faster we using all the
processors now we are going sequential
we are not using all the processors
partners and was quite fast now we have
this buggy implementation of using the
screen stream API where we synchronize
inside and we lose all the performance
okay and the last one is messing with
executor so now he should maybe use all
processors and it is very fast okay it's
actually the fastest one 1.6 second you
know okay so this one is even faster
then the Horten parallelization yeah so
you see again the factor of 4 or 5
between Mason and Orton so Mason is
factor of 3 or 4 faster and now the
fastest thing we have is the power
they're messing you see that the result
here is different from this result here
why is that okay so maybe I add here on
two more digits to two more dots to be
bit nicer
so why is the result of methane using
the executor framework different from
the stream API the reason is that we are
using completely different sequences so
here we used one sequence with a single
seat okay here we are using many
different sequences with different seeds
the seeds are generated from another
sequence but actually the methane
sequences have different Montecarlo
seeds so they are completely different
sequences and you see I believe the
result was 7 times 10 to the minus 5 so
actually this sequence was by chance a
little bit better but you know that
Monte Carlo is actually just in
probability oh no it's a little bit
worse I see it's a little bit worse ok
so it was by chance a little bit worse
you can use a different number here and
maybe you get another you can also use
the executor framework to parallelize
the horton sequence and maybe I like to
do this because it's just copy and paste
it's not so much work yeah so get
approximation of P with me then I copy
this get approximation of P with Horton
and now I do not want to split using the
seed I want to split using the start
index of the secrets of the start index
of the sequence so this loop here goes
from start index to start index plus
number of samples and inside it uses a
horton sequence so I can get rid of this
mess in here
and inside are you is a heart in
sequence so Halton sequence dot get halt
a number four given base I and true for
the first component and I and three for
the second component okay so now I have
an approximation of P using the Horton
sequence with a different start index
and I would like to know now create as
we did here wisdom as n different
batches you know using the Horton
sequence okay so I copied this here test
Carlton and this is my last test now
Horton with executors so I'd like to run
this test also here test
Alton all this executors maybe we maybe
move it here so we have Horton and
messin tests okay and I need to modify
this code here so in this code we have
here 100 different tasks we create the
executor service this was needed to
generate random seats now this is not
needed because we do not use the gate
approximation business and we used to
get approximation with Halton for a
given start index so and what is the
start index the start index is just
which task am i working on
multiplied with number of samples per
task and also the first task goes from
zero to two million minus one and the
next one goes from two million to four
million minus one and so on
okay so you see this will be for the
first one two million but the two
million is not included in the loop now
because we start in zero okay so I have
created now a parallelization using the
execute of framework based e hot
sequence and let's scan this experiment
okay
so unfortunately running all the guys
takes so long yeah we have 20 seconds
for the first one you see processors are
not used up yeah it's sequential so I
hope I did everything all right then
what's the next one the next one is the
parallel Horton no which gives us the
same number much faster the next one is
hot and with executors which gives us
the same member almost there's a small
difference maybe you can think about
where the difference comes from and it
is faster it's actually one second
faster which is 20% you have faster
you're almost 20% then comes me as n in
sequential order which is similar to the
parallel yeah
the parallel Mezen using three was buggy
was slow no and we have here the very
fast messin with the executor framework
okay there is a surprising thing
parallelization usually the executor is
faster than using the stream and the
reason here is that actually very much
related to the question which we had in
the chat which we had from you how does
he know how to split the task so
actually he doesn't know a lot of our
problem so he uses some reasonable split
but the Horton sequence has the
unpleasant effect that later blocks take
longer than earlier blocks so actually
we should split it up into many small
blocks but I still would like to use
eights heads because if I use more
threads he will switch the threads
between the processors which takes time
actually I would like to use once that
pair processor and every thread works on
some task and the task should be small
enough such that he can distribute it
more evenly so if you just have here
actually the example is here eight
blocks he has a very large number of
blocks and one block is much slower than
the other one and the calculation takes
as long as the slowest block if you have
two small blocks it may be that the
overhead to schedule the task is too
large so here in this executor framework
you have much more control about the
size of this block and you can choose a
number which gives you then an even
faster
calculation now so if I have here an
eight it's maybe worse so let's let's
stop the calculation and just remove
this first one because it takes so long
okay so Alton parallel using stream so
now the difference is a little bit
smaller yeah it's only it's it's it's
not one second it's a little bit smaller
because we used a small number of blocks
to summarize I let it run all together
and we have seen many aspects in this
little experiment yeah for example
you've seen that you cannot paralyze
every code because it's not sweat safe
if you have code which is not set safe
you need to synchronize things but if
you use the stream API and just
synchronize the whole block you you you
you lose all the advantages okay this is
maybe trivia but maybe you should have
seen it once and if you'd like to have
finer control on splitting the worker
tasks then you can do this with this
executor framework I will commit this
code to our repo so you can use it maybe
as a blueprint for your examples or when
you read you like to do something in
parallel either use the stream API or
just use the executor brush and you see
in this two dimension Halton is actually
still better yeah it takes here a little
bit longer but it is a factor of 100
better but in higher dimension this
difference is shrinking and having a
fast pseudo-random number generator
parallelized is maybe then still the
best way to go okay so actually this was
quite exhaustive code session you know
and maybe there were many details inside
yeah that you do not need for the theory
for the next sections on theoretical
sections but I believe it's may be nice
to have seen this at least once and you
have also seen that the code you need to
pile and I something you know there's a
stream API or using the executor API
it's not so long and also executor is a
little bit longer you define your
executor you distribute your tasks you
collect the result yeah so maybe it's
bit longer but still fits on one page
okay so thanks for today
yeah so you have seen already the script
we will continue with generation of
random numbers with other distributions
so so far we have just looked at uniform
distributed random numbers so next
session will be on random number
sequences which have other distributions
like normal distribution exponential
distribution and so on for this we need
to prove some some small results and
have their nice applications in
mathematical finance