cdocutils.nodes
document
q)q}q(U nametypesq}q(Xgoing scala!qNXtestingqNX$initial experiments with performanceqNXrunningq NX
previous workq
NXbasic parallelism using parqNXdownload the codeqNX(example: trapezoidal numeric integrationq
NXgoing parallelqNuUsubstitution_defsq}q(X bitbucketqcdocutils.nodes
substitution_definition
q)q}q(U rawsourceqXf.. |bitbucket| image:: figures/bitbucket.png
:alt: Bitbucket
:align: middle
UparentqhUsourceqcdocutils.nodes
reprunicode
qX(/home/gkt/Work/notes/source/parallel.rstqq}qbUtagnameqUsubstitution_definitionqU
attributesq}q(Udupnamesq ]Uclassesq!]Ubackrefsq"]Uidsq#]Unamesq$]q%hauUlineq&KUdocumentq'hUchildrenq(]q)cdocutils.nodes
image
q*)q+}q,(hXVimage:: figures/bitbucket.png
:alt: Bitbucket
:align: middleq-h}q.(UalignXmiddleq/UuriXfigures/bitbucket.pngq0h#]h"]h ]h!]U
candidatesq1}q2U*h0sh$]UalthX Bitbucketq3q4}q5buhhh(]hUimageq6ubaubXdo-whileq7h)q8}q9(hX,.. |do-while| replace:: ``do``\ -``while``
hcdocutils.nodes
section
q:)q;}q<(hUhh:)q=}q>(hUhhhhhUsectionq?h}q@(h ]h!]h"]h#]qAUbasic-parallelism-using-parqBah$]qChauh&Kh'hh(]qD(cdocutils.nodes
title
qE)qF}qG(hXBasic Parallelism using ParqHhh=hhhUtitleqIh}qJ(h ]h!]h"]h#]h$]uh&Kh'hh(]qKcdocutils.nodes
Text
qLXBasic Parallelism using ParqMqN}qO(hhHhhFubaubcdocutils.nodes
paragraph
qP)qQ}qR(hX%Using parallelism solves problems more quickly than using a
single-processor machine, as is the case where groups of people solve
problems larger than one person can solve. But just as with groups of
people, there are additional costs and problems involved in coordinating
parallel processors:qShh=hhhU paragraphqTh}qU(h ]h!]h"]h#]h$]uh&Kh'hh(]qVhLX%Using parallelism solves problems more quickly than using a
single-processor machine, as is the case where groups of people solve
problems larger than one person can solve. But just as with groups of
people, there are additional costs and problems involved in coordinating
parallel processors:qWqX}qY(hhShhQubaubcdocutils.nodes
bullet_list
qZ)q[}q\(hUhh=hhhUbullet_listq]h}q^(Ubulletq_X-h#]h"]h ]h!]h$]uh&K$h'hh(]q`(cdocutils.nodes
list_item
qa)qb}qc(hXWe need to have more than one processor work on the problem at the same
time. Our machine must have more than one processor, and the operating
system must be able to give more than one processor to our program at the
same time. Kernel threads allow this in Java. An alternative approach is to
have several networked computers work on parts of the problem; this is
discussed in Chapters 11 and 12, “Networking” and “Coordination.” of the
HPJPC book by Christopher and Thiruvathukal.
hh[hhhU list_itemqdh}qe(h ]h!]h"]h#]h$]uh&Nh'hh(]qfhP)qg}qh(hXWe need to have more than one processor work on the problem at the same
time. Our machine must have more than one processor, and the operating
system must be able to give more than one processor to our program at the
same time. Kernel threads allow this in Java. An alternative approach is to
have several networked computers work on parts of the problem; this is
discussed in Chapters 11 and 12, “Networking” and “Coordination.” of the
HPJPC book by Christopher and Thiruvathukal.qihhbhhhhTh}qj(h ]h!]h"]h#]h$]uh&K$h(]qkhLXWe need to have more than one processor work on the problem at the same
time. Our machine must have more than one processor, and the operating
system must be able to give more than one processor to our program at the
same time. Kernel threads allow this in Java. An alternative approach is to
have several networked computers work on parts of the problem; this is
discussed in Chapters 11 and 12, “Networking” and “Coordination.” of the
HPJPC book by Christopher and Thiruvathukal.qlqm}qn(hhihhgubaubaubha)qo}qp(hXWe need to assign parts of the problem to threads. This at least requires
rewriting a sequential program. It usually requires rethinking the
algorithm as well.
hh[hhhhdh}qq(h ]h!]h"]h#]h$]uh&Nh'hh(]qrhP)qs}qt(hXWe need to assign parts of the problem to threads. This at least requires
rewriting a sequential program. It usually requires rethinking the
algorithm as well.quhhohhhhTh}qv(h ]h!]h"]h#]h$]uh&K,h(]qwhLXWe need to assign parts of the problem to threads. This at least requires
rewriting a sequential program. It usually requires rethinking the
algorithm as well.qxqy}qz(hhuhhsubaubaubha)q{}q|(hXWe need to coordinate the threads so they perform their operations in the
proper order, as well as avoid race conditions and deadlocks. A number of
useful facilities are not provided by the standard Java language package.
We provide a good collection for your use in our thread package.
hh[hhhhdh}q}(h ]h!]h"]h#]h$]uh&Nh'hh(]q~hP)q}q(hXWe need to coordinate the threads so they perform their operations in the
proper order, as well as avoid race conditions and deadlocks. A number of
useful facilities are not provided by the standard Java language package.
We provide a good collection for your use in our thread package.qhh{hhhhTh}q(h ]h!]h"]h#]h$]uh&K0h(]qhLXWe need to coordinate the threads so they perform their operations in the
proper order, as well as avoid race conditions and deadlocks. A number of
useful facilities are not provided by the standard Java language package.
We provide a good collection for your use in our thread package.qq}q(hhhhubaubaubha)q}q(hXWe need to maintain a reasonable grain size. Grain size refers to the
amount of work a thread does between communications or synchronizations.
Fine grain uses very few instructions between synchronizations; coarse
grain uses a large amount of work. Too fine a grain wastes too much
overhead creating and synchronizing threads. Too coarse a grain results in
load imbalance and the underutilization of processors.
hh[hhhhdh}q(h ]h!]h"]h#]h$]uh&Nh'hh(]qhP)q}q(hXWe need to maintain a reasonable grain size. Grain size refers to the
amount of work a thread does between communications or synchronizations.
Fine grain uses very few instructions between synchronizations; coarse
grain uses a large amount of work. Too fine a grain wastes too much
overhead creating and synchronizing threads. Too coarse a grain results in
load imbalance and the underutilization of processors.qhhhhhhTh}q(h ]h!]h"]h#]h$]uh&K5h(]qhLXWe need to maintain a reasonable grain size. Grain size refers to the
amount of work a thread does between communications or synchronizations.
Fine grain uses very few instructions between synchronizations; coarse
grain uses a large amount of work. Too fine a grain wastes too much
overhead creating and synchronizing threads. Too coarse a grain results in
load imbalance and the underutilization of processors.qq}q(hhhhubaubaubeubhP)q}q(hXTwo easy, practical approaches to dividing the work among several
processors are executing functions in parallel and executing
iterations of loops in parallel. Parallelizing loops will be presented
in the next chapter. In this chapter we will discuss running subroutines
in parallel.qhh=hhhhTh}q(h ]h!]h"]h#]h$]uh&KTwo kinds of algorithms particularly adaptable to parallel execution of
functions are the divide-and-conquer and branch-and-bound algorithms.
Divide-and-conquer algorithms break large problems into parts and solve
the parts independently. Parts that are small enough are solved simply
as special cases. You must know how to break a large problem into parts
that can be solved independently and whose solutions can be reassembled
into a solution of the overall problem. The algorithm may undergo some
cost in breaking the problem into subparts or in assembling the
solutions.qhh=hhhhTh}q(h ]h!]h"]h#]h$]uh&KOh'hh(]qhLX>Two kinds of algorithms particularly adaptable to parallel execution of
functions are the divide-and-conquer and branch-and-bound algorithms.
Divide-and-conquer algorithms break large problems into parts and solve
the parts independently. Parts that are small enough are solved simply
as special cases. You must know how to break a large problem into parts
that can be solved independently and whose solutions can be reassembled
into a solution of the overall problem. The algorithm may undergo some
cost in breaking the problem into subparts or in assembling the
solutions.qąq}q(hhhhubaubh:)q}q(hUhh=hhhh?h}q(h ]h!]h"]h#]qU'example-trapezoidal-numeric-integrationqah$]qh
auh&KZh'hh(]q(hE)q}q(hX(Example: Trapezoidal Numeric IntegrationqhhhhhhIh}q(h ]h!]h"]h#]h$]uh&KZh'hh(]qhLX(Example: Trapezoidal Numeric IntegrationqӅq}q(hhhhubaubhP)q}q(hXPSometimes, a program needs to integrate a function (i.e., calculate the
area under a curve). It might be able to use a formula for the integral,
but doing so isn’t always convenient, or even possible. An easy
alternative approach is to approximate the curve with straight line
segments and calculate an estimate of the area from them.qhhhhhhTh}q(h ]h!]h"]h#]h$]uh&K\h'hh(]qhLXPSometimes, a program needs to integrate a function (i.e., calculate the
area under a curve). It might be able to use a formula for the integral,
but doing so isn’t always convenient, or even possible. An easy
alternative approach is to approximate the curve with straight line
segments and calculate an estimate of the area from them.qۅq}q(hhhhubaubhP)q}q(hX=This visual (courtesy of HPJPC) shows the trapezoidal method:qhhhhhhTh}q(h ]h!]h"]h#]h$]uh&Kbh'hh(]qhLX=This visual (courtesy of HPJPC) shows the trapezoidal method:qㅁq}q(hhhhubaubh*)q}q(hX].. image:: figures/trapezoids.png
:alt: Trapezoidal Integration Method
:align: center
hhhhhh6h}q(UalignXcenterUuriXfigures/trapezoids.pngqh#]h"]h ]h!]h1}qU*hsh$]UalthXTrapezoidal Integration Methodq녁q}qbuh&Nh'hh(]ubhP)q}q(hX.This equation shows how to calculate the area.qhhhhhhTh}q(h ]h!]h"]h#]h$]uh&Kih'hh(]qhLX.This equation shows how to calculate the area.qq}q(hhhhubaubhP)q}q(hXWe wish to find the area under the curve from :math:`a` to :math:`b`. We
approximate the function by dividing the domain from :math:`a` to :math:`b`
into :math:`g` equally sized segments. Each segment is :math:`(b - a) / g`
long. Let the boundaries of these segments be :math:`x_0 = a`, :math:`x_1`,
:math:`x_1`, ... , :math:`x_g = b`. The polyline approximating the curve will
have coordinates :math:`(x_0, f(x_0))`, :math:`(x_1, f(x_1))`, :math:`(x_2,
f(x_2))`, ..., :math:`(x_g, f(x_g))`.hhhhhhTh}q(h ]h!]h"]h#]h$]uh&Kkh'hh(]q(hLX.We wish to find the area under the curve from qq}q(hX.We wish to find the area under the curve from hhubcsphinx.ext.mathbase
math
q)q}q(hUh}r(UlatexXah#]h"]h ]h!]h$]uhhh(]hUmathrubhLX to rr}r(hX to hhubh)r}r(hUh}r(UlatexXbh#]h"]h ]h!]h$]uhhh(]hjubhLX:. We
approximate the function by dividing the domain from rr }r
(hX:. We
approximate the function by dividing the domain from hhubh)r}r(hUh}r
(UlatexXah#]h"]h ]h!]h$]uhhh(]hjubhLX to rr}r(hX to hhubh)r}r(hUh}r(UlatexXbh#]h"]h ]h!]h$]uhhh(]hjubhLX
into rr}r(hX
into hhubh)r}r(hUh}r(UlatexXgh#]h"]h ]h!]h$]uhhh(]hjubhLX) equally sized segments. Each segment is rr}r(hX) equally sized segments. Each segment is hhubh)r}r(hUh}r(UlatexX(b - a) / gh#]h"]h ]h!]h$]uhhh(]hjubhLX/
long. Let the boundaries of these segments be r r!}r"(hX/
long. Let the boundaries of these segments be hhubh)r#}r$(hUh}r%(UlatexXx_0 = ah#]h"]h ]h!]h$]uhhh(]hjubhLX, r&r'}r((hX, hhubh)r)}r*(hUh}r+(UlatexXx_1h#]h"]h ]h!]h$]uhhh(]hjubhLX,
r,r-}r.(hX,
hhubh)r/}r0(hUh}r1(UlatexXx_1h#]h"]h ]h!]h$]uhhh(]hjubhLX, ... , r2r3}r4(hX, ... , hhubh)r5}r6(hUh}r7(UlatexXx_g = bh#]h"]h ]h!]h$]uhhh(]hjubhLX=. The polyline approximating the curve will
have coordinates r8r9}r:(hX=. The polyline approximating the curve will
have coordinates hhubh)r;}r<(hUh}r=(UlatexX
(x_0, f(x_0))h#]h"]h ]h!]h$]uhhh(]hjubhLX, r>r?}r@(hX, hhubh)rA}rB(hUh}rC(UlatexX
(x_1, f(x_1))h#]h"]h ]h!]h$]uhhh(]hjubhLX, rDrE}rF(hX, hhubh)rG}rH(hUh}rI(UlatexX
(x_2,
f(x_2))h#]h"]h ]h!]h$]uhhh(]hjubhLX, ..., rJrK}rL(hX, ..., hhubh)rM}rN(hUh}rO(UlatexX
(x_g, f(x_g))h#]h"]h ]h!]h$]uhhh(]hjubhLX.rP}rQ(hX.hhubeubhP)rR}rS(hXNThe area is then given by this formula, which sums the area of all trapezoids:rThhhhhhTh}rU(h ]h!]h"]h#]h$]uh&Ksh'hh(]rVhLXNThe area is then given by this formula, which sums the area of all trapezoids:rWrX}rY(hjThjRubaubh*)rZ}r[(hXF.. image:: figures/math1.png
:alt: Basic Formula
:align: center
hhhhhh6h}r\(UalignXcenterUuriXfigures/math1.pngr]h#]h"]h ]h!]h1}r^U*j]sh$]UalthX
Basic Formular_r`}rabuh&Nh'hh(]ubhP)rb}rc(hX$If we apply that formula unthinkingly, we will evaluate the function twice for
each value of x, except the first and the last values. While the correct
result would be obtained, it is inefficient and kind of defeats the purpose of
going parallel. A little manipulation gives us the following:rdhhhhhhTh}re(h ]h!]h"]h#]h$]uh&Kyh'hh(]rfhLX$If we apply that formula unthinkingly, we will evaluate the function twice for
each value of x, except the first and the last values. While the correct
result would be obtained, it is inefficient and kind of defeats the purpose of
going parallel. A little manipulation gives us the following:rgrh}ri(hjdhjbubaubh*)rj}rk(hXT.. image:: figures/math2.png
:alt: Parallel "Friendly" Formula
:align: center
hhhhhh6h}rl(UalignXcenterUuriXfigures/math2.pngrmh#]h"]h ]h!]h1}rnU*jmsh$]UalthXParallel "Friendly" Formularorp}rqbuh&Nh'hh(]ubhP)rr}rs(hXgWe've now reduced the problem to computing the parallel sum term, which is
represented nicely in Scala.rthhhhhhTh}ru(h ]h!]h"]h#]h$]uh&Kh'hh(]rvhLXgWe've now reduced the problem to computing the parallel sum term, which is
represented nicely in Scala.rwrx}ry(hjthjrubaubhP)rz}r{(hX$We present three solutions in Scala:r|hhhhhhTh}r}(h ]h!]h"]h#]h$]uh&Kh'hh(]r~hLX$We present three solutions in Scala:rr}r(hj|hjzubaubhZ)r}r(hUhhhhhh]h}r(h_X-h#]h"]h ]h!]h$]uh&Kh'hh(]r(ha)r}r(hXG``integrateSequential()``: The sequential (i.e. not parallel) solution is aimed at showcasing one of
the key benefits of functional programming in general. In many cases, the code closely follows the mathematics
you write. Because the code is clear in terms of its intentions, we can adapt the solution for parallel
execution.
hjhhhhdh}r(h ]h!]h"]h#]h$]uh&Nh'hh(]rhP)r}r(hXF``integrateSequential()``: The sequential (i.e. not parallel) solution is aimed at showcasing one of
the key benefits of functional programming in general. In many cases, the code closely follows the mathematics
you write. Because the code is clear in terms of its intentions, we can adapt the solution for parallel
execution.hjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh(]r(cdocutils.nodes
literal
r)r}r(hX``integrateSequential()``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXintegrateSequential()rr}r(hUhjubahUliteralrubhLX-: The sequential (i.e. not parallel) solution is aimed at showcasing one of
the key benefits of functional programming in general. In many cases, the code closely follows the mathematics
you write. Because the code is clear in terms of its intentions, we can adapt the solution for parallel
execution.rr}r(hX-: The sequential (i.e. not parallel) solution is aimed at showcasing one of
the key benefits of functional programming in general. In many cases, the code closely follows the mathematics
you write. Because the code is clear in terms of its intentions, we can adapt the solution for parallel
execution.hjubeubaubha)r}r(hX``integrateParallel()``: The parallel version shows how to get parallel speedup in Scala from the
sequential one, simply by adding ``par``.
hjhhhhdh}r(h ]h!]h"]h#]h$]uh&Nh'hh(]rhP)r}r(hX``integrateParallel()``: The parallel version shows how to get parallel speedup in Scala from the
sequential one, simply by adding ``par``.hjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh(]r(j)r}r(hX``integrateParallel()``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXintegrateParallel()rr}r(hUhjubahjubhLXl: The parallel version shows how to get parallel speedup in Scala from the
sequential one, simply by adding rr}r(hXl: The parallel version shows how to get parallel speedup in Scala from the
sequential one, simply by adding hjubj)r}r(hX``par``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXparrr}r(hUhjubahjubhLX.r}r(hX.hjubeubaubha)r}r(hX<``integrateParallelGranular()``: This version shows how to combine parallel and serial execution. By
allowing the user to specify the grain size (number of retangles to do sequentially at a time),
it is possible to determine how Scala itself might be chunking the work in the ``integrateParallel()``
solution.
hjhNhhdh}r(h ]h!]h"]h#]h$]uh&Nh'hh(]rcdocutils.nodes
definition_list
r)r}r(hUh}r(h ]h!]h"]h#]h$]uhjh(]rcdocutils.nodes
definition_list_item
r)r}r(hX6``integrateParallelGranular()``: This version shows how to combine parallel and serial execution. By
allowing the user to specify the grain size (number of retangles to do sequentially at a time),
it is possible to determine how Scala itself might be chunking the work in the ``integrateParallel()``
solution.
hjhhhUdefinition_list_itemrh}r(h ]h!]h"]h#]h$]uh&Kh(]r(cdocutils.nodes
term
r)r}r(hXd``integrateParallelGranular()``: This version shows how to combine parallel and serial execution. ByrhjhhhUtermrh}r(h ]h!]h"]h#]h$]uh&Kh(]r(j)r}r(hX``integrateParallelGranular()``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXintegrateParallelGranular()rr}r(hUhjubahjubhLXE: This version shows how to combine parallel and serial execution. Byrr}r(hXE: This version shows how to combine parallel and serial execution. Byhjubeubcdocutils.nodes
definition
r)r}r(hUh}r(h ]h!]h"]h#]h$]uhjh(]rhP)r}r(hXallowing the user to specify the grain size (number of retangles to do sequentially at a time),
it is possible to determine how Scala itself might be chunking the work in the ``integrateParallel()``
solution.hjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh(]r(hLXallowing the user to specify the grain size (number of retangles to do sequentially at a time),
it is possible to determine how Scala itself might be chunking the work in the rr}r(hXallowing the user to specify the grain size (number of retangles to do sequentially at a time),
it is possible to determine how Scala itself might be chunking the work in the hjubj)r}r(hX``integrateParallel()``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXintegrateParallel()rr}r(hUhjubahjubhLX
solution.rr}r(hX
solution.hjubeubahU
definitionrubeubahUdefinition_listrubaubeubeubh:)r}r(hUhh=hhhh?h}r(h ]h!]h"]h#]rUdownload-the-coderah$]rhauh&Kh'hh(]r(hE)r}r(hXDownload the CoderhjhhhhIh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]rhLXDownload the Coderr}r(hjhjubaubj)r}r(hUhjhhhjh}r(h ]h!]h"]h#]h$]uh&Nh'hh(]r(j)r}r(hXg|bitbucket| ZIP File
https://bitbucket.org/loyolachicagocs_plsystems/integration-scala/get/default.zip
hjhhhjh}r(h ]h!]h"]h#]h$]uh&Kh(]r(j)r}r(hX|bitbucket| ZIP Filerhjhhhjh}r(h ]h!]h"]h#]h$]uh&Kh(]r(h*)r }r
(hh-h}r(Ualignh/Uurih0h#]h"]h ]h!]h1}rU*h0sh$]Ualth4uhjh(]hh6ubhLX ZIP Filer
r}r(hX ZIP Filehjubeubj)r}r(hUh}r(h ]h!]h"]h#]h$]uhjh(]rhP)r}r(hXQhttps://bitbucket.org/loyolachicagocs_plsystems/integration-scala/get/default.ziprhjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh(]rcdocutils.nodes
reference
r)r}r(hjh}r(Urefurijh#]h"]h ]h!]h$]uhjh(]rhLXQhttps://bitbucket.org/loyolachicagocs_plsystems/integration-scala/get/default.ziprr}r (hUhjubahU referencer!ubaubahjubeubj)r"}r#(hXe|bitbucket| via Mercurial
hg clone https://bitbucket.org/loyolachicagocs_plsystems/integration-scala
hjhhhjh}r$(h ]h!]h"]h#]h$]uh&Kh'hh(]r%(j)r&}r'(hX|bitbucket| via Mercurialr(hj"hhhjh}r)(h ]h!]h"]h#]h$]uh&Kh(]r*(h*)r+}r,(hh-h}r-(Ualignh/Uurih0h#]h"]h ]h!]h1}r.U*h0sh$]Ualth4uhj&h(]hh6ubhLX via Mercurialr/r0}r1(hX via Mercurialhj&ubeubj)r2}r3(hUh}r4(h ]h!]h"]h#]h$]uhj"h(]r5hP)r6}r7(hXJhg clone https://bitbucket.org/loyolachicagocs_plsystems/integration-scalahj2hhhhTh}r8(h ]h!]h"]h#]h$]uh&Kh(]r9(hLX hg clone r:r;}r<(hX hg clone hj6ubj)r=}r>(hXAhttps://bitbucket.org/loyolachicagocs_plsystems/integration-scalar?h}r@(Urefurij?h#]h"]h ]h!]h$]uhj6h(]rAhLXAhttps://bitbucket.org/loyolachicagocs_plsystems/integration-scalarBrC}rD(hUhj=ubahj!ubeubahjubeubj)rE}rF(hXu|instructions| Build and Run Instructions
https://bitbucket.org/loyolachicagocs_plsystems/integration-scala/overview
hjhhhjh}rG(h ]h!]h"]h#]h$]uh&Kh'hh(]rH(j)rI}rJ(hX)|instructions| Build and Run InstructionsrKhjEhhhjh}rL(h ]h!]h"]h#]h$]uh&Kh(]rM(h*)rN}rO(hX\image:: figures/instructions.png
:alt: Instructions
:align: middlerPh}rQ(UalignXmiddlerRUuriXfigures/instructions.pngrSh#]h"]h ]h!]h1}rTU*jSsh$]UalthXInstructionsrUrV}rWbuhjIh(]hh6ubhLX Build and Run InstructionsrXrY}rZ(hX Build and Run InstructionshjIubeubj)r[}r\(hUh}r](h ]h!]h"]h#]h$]uhjEh(]r^hP)r_}r`(hXJhttps://bitbucket.org/loyolachicagocs_plsystems/integration-scala/overviewrahj[hhhhTh}rb(h ]h!]h"]h#]h$]uh&Kh(]rcj)rd}re(hjah}rf(Urefurijah#]h"]h ]h!]h$]uhj_h(]rghLXJhttps://bitbucket.org/loyolachicagocs_plsystems/integration-scala/overviewrhri}rj(hUhjdubahj!ubaubahjubeubeubeubh:)rk}rl(hUhh=hhhh?h}rm(h ]h!]h"]h#]rnUgoing-scalaroah$]rphauh&Kh'hh(]rq(hE)rr}rs(hXGoing Scala!rthjkhhhhIh}ru(h ]h!]h"]h#]h$]uh&Kh'hh(]rvhLXGoing Scala!rwrx}ry(hjthjrubaubhP)rz}r{(hX4Let's start by looking at ``integrateSequential()``.r|hjkhhhhTh}r}(h ]h!]h"]h#]h$]uh&Kh'hh(]r~(hLXLet's start by looking at rr}r(hXLet's start by looking at hjzubj)r}r(hX``integrateSequential()``h}r(h ]h!]h"]h#]h$]uhjzh(]rhLXintegrateSequential()rr}r(hUhjubahjubhLX.r}r(hX.hjzubeubcdocutils.nodes
literal_block
r)r}r(hX def integrateSequential(a: Double, b: Double, rectangles: Int, f: Fx): Double = {
val interval = (b - a) / rectangles
val fxValues = (1 until rectangles).view map { n => f(a + n * interval) }
interval * (f(a) / 2 + f(b) / 2 + fxValues.sum)
}
hjkhhhU
literal_blockrh}r(Ulinenosrh ]U xml:spacerUpreserverh#]h"]UsourceXq/home/gkt/Work/notes/examples/integration/src/main/scala/edu/luc/etl/sigcse13/scala/integration/Integration.scalah!]h$]uh&Kh'hh(]rhLX def integrateSequential(a: Double, b: Double, rectangles: Int, f: Fx): Double = {
val interval = (b - a) / rectangles
val fxValues = (1 until rectangles).view map { n => f(a + n * interval) }
interval * (f(a) / 2 + f(b) / 2 + fxValues.sum)
}
rr}r(hUhjubaubhP)r}r(hX]As would be expected, we should be write this the way we think of the problem mathematically:rhjkhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]rhLX]As would be expected, we should be write this the way we think of the problem mathematically:rr}r(hjhjubaubhZ)r}r(hUhjkhhhh]h}r(h_X-h#]h"]h ]h!]h$]uh&Kh'hh(]r(ha)r}r(hX:``a`` and ``b``: The endpoints of the integration intervalrhjhhhhdh}r(h ]h!]h"]h#]h$]uh&Nh'hh(]rhP)r}r(hjhjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh(]r(j)r}r(hX``a``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXar}r(hUhjubahjubhLX and rr}r(hX and hjubj)r}r(hX``b``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXbr}r(hUhjubahjubhLX+: The endpoints of the integration intervalrr}r(hX+: The endpoints of the integration intervalhjubeubaubha)r}r(hXK``rectangles``: The number of rectangles to use to approximate the integralrhjhhhhdh}r(h ]h!]h"]h#]h$]uh&Nh'hh(]rhP)r}r(hjhjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh(]r(j)r}r(hX``rectangles``h}r(h ]h!]h"]h#]h$]uhjh(]rhLX
rectanglesrr}r(hUhjubahjubhLX=: The number of rectangles to use to approximate the integralrr}r(hX=: The number of rectangles to use to approximate the integralhjubeubaubha)r}r(hX&``f``: The function to be integrated.
hjhhhhdh}r(h ]h!]h"]h#]h$]uh&Nh'hh(]rhP)r}r(hX%``f``: The function to be integrated.hjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh(]r(j)r}r(hX``f``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXfr}r(hUhjubahjubhLX : The function to be integrated.rr}r(hX : The function to be integrated.hjubeubaubeubhP)r}r(hXIn the last case, this is where Scala makes our work particularly easy by allowing us to
define a proper function type as shown below:rhjkhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]rhLXIn the last case, this is where Scala makes our work particularly easy by allowing us to
define a proper function type as shown below:rr}r(hjhjubaubj)r}r(hX type Fx = Double => Double
hjkhhhjh}r(jh ]jjh#]h"]UsourceXq/home/gkt/Work/notes/examples/integration/src/main/scala/edu/luc/etl/sigcse13/scala/integration/Integration.scalah!]h$]uh&Kh'hh(]rhLX type Fx = Double => Double
rr}r(hUhjubaubhP)r}r(hXIn our previous Java work (in the book), we had to use Java *interfaces* for
this same task. While seemingly just *syntactic sugar*, Java's boilerplate is
offputting to computational scientists, who would rather use C and FORTRAN
where function parameters are possible. Unlike those choices, however, Scala
gives us the compelling aspect of *full type checking*, which means that we
can be assured of excellent performance without the complexity--and sometimes
unsafe behavior--that is found in other languages.hjkhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]r(hLX<In our previous Java work (in the book), we had to use Java rr}r(hX<In our previous Java work (in the book), we had to use Java hjubcdocutils.nodes
emphasis
r)r}r(hX*interfaces*h}r(h ]h!]h"]h#]h$]uhjh(]rhLX
interfacesrr}r(hUhjubahUemphasisrubhLX* for
this same task. While seemingly just rr}r(hX* for
this same task. While seemingly just hjubj)r}r(hX*syntactic sugar*h}r(h ]h!]h"]h#]h$]uhjh(]rhLXsyntactic sugarrr }r
(hUhjubahjubhLX, Java's boilerplate is
offputting to computational scientists, who would rather use C and FORTRAN
where function parameters are possible. Unlike those choices, however, Scala
gives us the compelling aspect of rr}r
(hX, Java's boilerplate is
offputting to computational scientists, who would rather use C and FORTRAN
where function parameters are possible. Unlike those choices, however, Scala
gives us the compelling aspect of hjubj)r}r(hX*full type checking*h}r(h ]h!]h"]h#]h$]uhjh(]rhLXfull type checkingrr}r(hUhjubahjubhLX, which means that we
can be assured of excellent performance without the complexity--and sometimes
unsafe behavior--that is found in other languages.rr}r(hX, which means that we
can be assured of excellent performance without the complexity--and sometimes
unsafe behavior--that is found in other languages.hjubeubhP)r}r(hXBecause it is essential to understand the sequential version (the core
algorithm) before proceeding, we offer a brief explanation of each line of
code, even when obvious, and how we are taking advantage of Scala (when less
obvious!)rhjkhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]rhLXBecause it is essential to understand the sequential version (the core
algorithm) before proceeding, we offer a brief explanation of each line of
code, even when obvious, and how we are taking advantage of Scala (when less
obvious!)rr}r(hjhjubaubhZ)r }r!(hUhjkhhhh]h}r"(h_X-h#]h"]h ]h!]h$]uh&Kh'hh(]r#(ha)r$}r%(hXIn line 2, we calculate ``interval`` using the formula that was presented
earlier. Scala, being pragmatic, is able to do the right thing and treat the
entire expression as Double, resulting in a Double value. Scala really shines
here by not requiring us to declare every val type, owing to its innate type
inferencing mechanism. This results in code that is much easier to comprehend
(at least we like to think so).
hj hhhhdh}r&(h ]h!]h"]h#]h$]uh&Nh'hh(]r'hP)r(}r)(hXIn line 2, we calculate ``interval`` using the formula that was presented
earlier. Scala, being pragmatic, is able to do the right thing and treat the
entire expression as Double, resulting in a Double value. Scala really shines
here by not requiring us to declare every val type, owing to its innate type
inferencing mechanism. This results in code that is much easier to comprehend
(at least we like to think so).hj$hhhhTh}r*(h ]h!]h"]h#]h$]uh&Kh(]r+(hLXIn line 2, we calculate r,r-}r.(hXIn line 2, we calculate hj(ubj)r/}r0(hX``interval``h}r1(h ]h!]h"]h#]h$]uhj(h(]r2hLXintervalr3r4}r5(hUhj/ubahjubhLX{ using the formula that was presented
earlier. Scala, being pragmatic, is able to do the right thing and treat the
entire expression as Double, resulting in a Double value. Scala really shines
here by not requiring us to declare every val type, owing to its innate type
inferencing mechanism. This results in code that is much easier to comprehend
(at least we like to think so).r6r7}r8(hX{ using the formula that was presented
earlier. Scala, being pragmatic, is able to do the right thing and treat the
entire expression as Double, resulting in a Double value. Scala really shines
here by not requiring us to declare every val type, owing to its innate type
inferencing mechanism. This results in code that is much easier to comprehend
(at least we like to think so).hj(ubeubaubha)r9}r:(hXTIn line 3, this requires a bit more explanation. Working from our equation,
recall that our summation term goes from 1 to the number of rectangles minus
0. We use Scala's until to get the indices. When ``rectangles`` is small, this
is fine. What happens when it is large? The answer depends on whether we are
using eager or lazy evaluation. In mathematical/scientific computing, we often
need to do a large number of iterations to get a better answer. This is where
the ``view`` comes in. It gives us a lazy sequence that can then be mapped
(also lazily) using the user-supplied function, ``f``.
hj hhhhdh}r;(h ]h!]h"]h#]h$]uh&Nh'hh(]r<hP)r=}r>(hXSIn line 3, this requires a bit more explanation. Working from our equation,
recall that our summation term goes from 1 to the number of rectangles minus
0. We use Scala's until to get the indices. When ``rectangles`` is small, this
is fine. What happens when it is large? The answer depends on whether we are
using eager or lazy evaluation. In mathematical/scientific computing, we often
need to do a large number of iterations to get a better answer. This is where
the ``view`` comes in. It gives us a lazy sequence that can then be mapped
(also lazily) using the user-supplied function, ``f``.hj9hhhhTh}r?(h ]h!]h"]h#]h$]uh&Kh(]r@(hLXIn line 3, this requires a bit more explanation. Working from our equation,
recall that our summation term goes from 1 to the number of rectangles minus
0. We use Scala's until to get the indices. When rArB}rC(hXIn line 3, this requires a bit more explanation. Working from our equation,
recall that our summation term goes from 1 to the number of rectangles minus
0. We use Scala's until to get the indices. When hj=ubj)rD}rE(hX``rectangles``h}rF(h ]h!]h"]h#]h$]uhj=h(]rGhLX
rectanglesrHrI}rJ(hUhjDubahjubhLX is small, this
is fine. What happens when it is large? The answer depends on whether we are
using eager or lazy evaluation. In mathematical/scientific computing, we often
need to do a large number of iterations to get a better answer. This is where
the rKrL}rM(hX is small, this
is fine. What happens when it is large? The answer depends on whether we are
using eager or lazy evaluation. In mathematical/scientific computing, we often
need to do a large number of iterations to get a better answer. This is where
the hj=ubj)rN}rO(hX``view``h}rP(h ]h!]h"]h#]h$]uhj=h(]rQhLXviewrRrS}rT(hUhjNubahjubhLXo comes in. It gives us a lazy sequence that can then be mapped
(also lazily) using the user-supplied function, rUrV}rW(hXo comes in. It gives us a lazy sequence that can then be mapped
(also lazily) using the user-supplied function, hj=ubj)rX}rY(hX``f``h}rZ(h ]h!]h"]h#]h$]uhj=h(]r[hLXfr\}r](hUhjXubahjubhLX.r^}r_(hX.hj=ubeubaubha)r`}ra(hXtIn line 4, we are able to plug everything into the derived formular for
calculating the trapezoidal integration. Technically, we could have put the
``fxValues`` val definition in the same line of code, but having it separate
makes it easier to understand for new Scala users (one of the goals for our
SIGCSE workshop). More importantly, you should be able to write the code this
way and not have to worry about losing performance. By setting up this lazy
computation, we're able to compute the sum *on demand*. Aside from this split,
the code here exactly matches the formula we derived for performing
trapezoidal integration.
hj hhhhdh}rb(h ]h!]h"]h#]h$]uh&Nh'hh(]rchP)rd}re(hXsIn line 4, we are able to plug everything into the derived formular for
calculating the trapezoidal integration. Technically, we could have put the
``fxValues`` val definition in the same line of code, but having it separate
makes it easier to understand for new Scala users (one of the goals for our
SIGCSE workshop). More importantly, you should be able to write the code this
way and not have to worry about losing performance. By setting up this lazy
computation, we're able to compute the sum *on demand*. Aside from this split,
the code here exactly matches the formula we derived for performing
trapezoidal integration.hj`hhhhTh}rf(h ]h!]h"]h#]h$]uh&Kh(]rg(hLXIn line 4, we are able to plug everything into the derived formular for
calculating the trapezoidal integration. Technically, we could have put the
rhri}rj(hXIn line 4, we are able to plug everything into the derived formular for
calculating the trapezoidal integration. Technically, we could have put the
hjdubj)rk}rl(hX``fxValues``h}rm(h ]h!]h"]h#]h$]uhjdh(]rnhLXfxValuesrorp}rq(hUhjkubahjubhLXS val definition in the same line of code, but having it separate
makes it easier to understand for new Scala users (one of the goals for our
SIGCSE workshop). More importantly, you should be able to write the code this
way and not have to worry about losing performance. By setting up this lazy
computation, we're able to compute the sum rrrs}rt(hXS val definition in the same line of code, but having it separate
makes it easier to understand for new Scala users (one of the goals for our
SIGCSE workshop). More importantly, you should be able to write the code this
way and not have to worry about losing performance. By setting up this lazy
computation, we're able to compute the sum hjdubj)ru}rv(hX*on demand*h}rw(h ]h!]h"]h#]h$]uhjdh(]rxhLX on demandryrz}r{(hUhjuubahjubhLXu. Aside from this split,
the code here exactly matches the formula we derived for performing
trapezoidal integration.r|r}}r~(hXu. Aside from this split,
the code here exactly matches the formula we derived for performing
trapezoidal integration.hjdubeubaubeubhP)r}r(hX:The sequential version of integration presented here is completely side-effect
free. That is, all of the work is being done without mutating state. This
means that it can immmediately be turned into something parallel in Scala,
provided we know where the actual work is being done. Let's continue this
exploration!rhjkhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]rhLX:The sequential version of integration presented here is completely side-effect
free. That is, all of the work is being done without mutating state. This
means that it can immmediately be turned into something parallel in Scala,
provided we know where the actual work is being done. Let's continue this
exploration!rr}r(hjhjubaubeubh:)r}r(hUhh=hhhh?h}r(h ]h!]h"]h#]rUgoing-parallelrah$]rhauh&Kh'hh(]r(hE)r}r(hXGoing ParallelrhjhhhhIh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]rhLXGoing Parallelrr}r(hjhjubaubhP)r}r(hXThe immediately preceding discussion was presented with great care, because
what we are about to demonstrate illustrates how one needs to do very little
work to take what is sometimes known as an *embarrassingly parallel* algorithm
and make it run in parallel. The term *embarrassing* is a tad misleading. As
we'll see, the results don't always follow your intuition. Furthermore, while
the results can be gotten quickly, it doesn't always mean that you are getting
the best results possible. For example, as well as Scala does, it still
doesn't do nearly as well as our hand-coded multithreaded Java example from
HPJPC. We'll say more about this later.hjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]r(hLXThe immediately preceding discussion was presented with great care, because
what we are about to demonstrate illustrates how one needs to do very little
work to take what is sometimes known as an rr}r(hXThe immediately preceding discussion was presented with great care, because
what we are about to demonstrate illustrates how one needs to do very little
work to take what is sometimes known as an hjubj)r}r(hX*embarrassingly parallel*h}r(h ]h!]h"]h#]h$]uhjh(]rhLXembarrassingly parallelrr}r(hUhjubahjubhLX1 algorithm
and make it run in parallel. The term rr}r(hX1 algorithm
and make it run in parallel. The term hjubj)r}r(hX*embarrassing*h}r(h ]h!]h"]h#]h$]uhjh(]rhLXembarrassingrr}r(hUhjubahjubhLXq is a tad misleading. As
we'll see, the results don't always follow your intuition. Furthermore, while
the results can be gotten quickly, it doesn't always mean that you are getting
the best results possible. For example, as well as Scala does, it still
doesn't do nearly as well as our hand-coded multithreaded Java example from
HPJPC. We'll say more about this later.rr}r(hXq is a tad misleading. As
we'll see, the results don't always follow your intuition. Furthermore, while
the results can be gotten quickly, it doesn't always mean that you are getting
the best results possible. For example, as well as Scala does, it still
doesn't do nearly as well as our hand-coded multithreaded Java example from
HPJPC. We'll say more about this later.hjubeubhP)r}r(hX#Let's look at the parallel version.rhjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]rhLX#Let's look at the parallel version.rr}r(hjhjubaubj)r}r(hX def integrateParallel(a: Double, b: Double, rectangles: Int, f: Fx): Double = {
val interval = (b - a) / rectangles
val fxValues = (1 until rectangles).par.view map { n => f(a + n * interval) }
interval * (f(a) / 2 + f(b) / 2 + fxValues.sum)
}
hjhhhjh}r(jh ]jjh#]h"]UsourceXq/home/gkt/Work/notes/examples/integration/src/main/scala/edu/luc/etl/sigcse13/scala/integration/Integration.scalah!]h$]uh&Kh'hh(]rhLX def integrateParallel(a: Double, b: Double, rectangles: Int, f: Fx): Double = {
val interval = (b - a) / rectangles
val fxValues = (1 until rectangles).par.view map { n => f(a + n * interval) }
interval * (f(a) / 2 + f(b) / 2 + fxValues.sum)
}
rr}r(hUhjubaubhP)r}r(hXIn this version, observe that we have added the ``par`` method call just
before generating the lazy ``view``. This is the only sensible place to add
``par``, because in mathematical/scientific computing, we know that most of
the parallel potential is found *where the loops are*. The ``1 until
rectangles`` is where the actual workload is being generated, so it is a
natural place to suggest ``par``.hjhhhhTh}r(h ]h!]h"]h#]h$]uh&Kh'hh(]r(hLX0In this version, observe that we have added the rr}r(hX0In this version, observe that we have added the hjubj)r}r(hX``par``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXparrr}r(hUhjubahjubhLX- method call just
before generating the lazy rr}r(hX- method call just
before generating the lazy hjubj)r}r(hX``view``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXviewrr}r(hUhjubahjubhLX). This is the only sensible place to add
rr}r(hX). This is the only sensible place to add
hjubj)r}r(hX``par``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXparrr}r(hUhjubahjubhLXe, because in mathematical/scientific computing, we know that most of
the parallel potential is found rr}r(hXe, because in mathematical/scientific computing, we know that most of
the parallel potential is found hjubj)r}r(hX*where the loops are*h}r(h ]h!]h"]h#]h$]uhjh(]rhLXwhere the loops arerr}r(hUhjubahjubhLX. The rr}r(hX. The hjubj)r}r(hX``1 until
rectangles``h}r(h ]h!]h"]h#]h$]uhjh(]rhLX1 until
rectanglesrr}r(hUhjubahjubhLXV is where the actual workload is being generated, so it is a
natural place to suggest rr}r(hXV is where the actual workload is being generated, so it is a
natural place to suggest hjubj)r}r(hX``par``h}r(h ]h!]h"]h#]h$]uhjh(]rhLXparrr}r(hUhjubahjubhLX.r}r(hX.hjubeubeubh:)r}r(hUhh=hhhh?h}r(h ]h!]h"]h#]rUtestingrah$]rhauh&Mh'hh(]r(hE)r }r
(hXTestingrhjhhhhIh}r(h ]h!]h"]h#]h$]uh&Mh'hh(]r
hLXTestingrr}r(hjhj ubaubhP)r}r(hXOThe following code shows the unit tests for our various *integration* examples.rhjhhhhTh}r(h ]h!]h"]h#]h$]uh&Mh'hh(]r(hLX8The following code shows the unit tests for our various rr}r(hX8The following code shows the unit tests for our various hjubj)r}r(hX
*integration*h}r(h ]h!]h"]h#]h$]uhjh(]rhLXintegrationrr}r(hUhjubahjubhLX
examples.r r!}r"(hX
examples.hjubeubj)r#}r$(hXpackage edu.luc.etl.sigcse13.scala.integration
import org.junit.Test
import org.junit.Assert._
import Integration._
import Fixtures._
/**
* Simple JUnit-based tests.
*/
class Tests {
@Test def testSequential() {
assertEquals(333.3, integrateSequential(0, 10, 1000, sqr), 0.1)
}
@Test def testParallel() {
assertEquals(333.3, integrateParallel(0, 10, 1000, sqr), 0.1)
}
@Test def testParallelGranular() {
assertEquals(333.3, integrateParallelGranular(10)(0, 10, 1000, sqr), 0.1)
}
}
hjhhhjh}r%(jh ]jjh#]h"]UsourceXk/home/gkt/Work/notes/examples/integration/src/test/scala/edu/luc/etl/sigcse13/scala/integration/Tests.scalah!]h$]uh&Mh'hh(]r&hLXpackage edu.luc.etl.sigcse13.scala.integration
import org.junit.Test
import org.junit.Assert._
import Integration._
import Fixtures._
/**
* Simple JUnit-based tests.
*/
class Tests {
@Test def testSequential() {
assertEquals(333.3, integrateSequential(0, 10, 1000, sqr), 0.1)
}
@Test def testParallel() {
assertEquals(333.3, integrateParallel(0, 10, 1000, sqr), 0.1)
}
@Test def testParallelGranular() {
assertEquals(333.3, integrateParallelGranular(10)(0, 10, 1000, sqr), 0.1)
}
}
r'r(}r)(hUhj#ubaubhP)r*}r+(hXFor the purpose of testing, we set up :math:`f(x) = x^2` and integrated it
from 0 to 10. The value of this integral should be 333.333333333....hjhhhhTh}r,(h ]h!]h"]h#]h$]uh&M h'hh(]r-(hLX&For the purpose of testing, we set up r.r/}r0(hX&For the purpose of testing, we set up hj*ubh)r1}r2(hUh}r3(UlatexX
f(x) = x^2h#]h"]h ]h!]h$]uhj*h(]hjubhLXW and integrated it
from 0 to 10. The value of this integral should be 333.333333333....r4r5}r6(hXW and integrated it
from 0 to 10. The value of this integral should be 333.333333333....hj*ubeubhP)r7}r8(hXWe can't stress enough the importance of unit tests, especially when working a
sequential algorithm into a parallel one. While you are less likely to make
mistakes in Scala, it is very easy when trying certain strategies to get the
wrong answer. (In fact, one of them, the third, gave an incorrect answer
during testing, simply because of a division error I made when computing the
number of workers!)r9hjhhhhTh}r:(h ]h!]h"]h#]h$]uh&Mh'hh(]r;hLXWe can't stress enough the importance of unit tests, especially when working a
sequential algorithm into a parallel one. While you are less likely to make
mistakes in Scala, it is very easy when trying certain strategies to get the
wrong answer. (In fact, one of them, the third, gave an incorrect answer
during testing, simply because of a division error I made when computing the
number of workers!)r<r=}r>(hj9hj7ubaubhP)r?}r@(hXUsing the notion of a test fixture, it is possible to specify what function we
wish to test without contaminating the general-purpose code we wrote with a
specific function to be integrated. See below.rAhjhhhhTh}rB(h ]h!]h"]h#]h$]uh&Mh'hh(]rChLXUsing the notion of a test fixture, it is possible to specify what function we
wish to test without contaminating the general-purpose code we wrote with a
specific function to be integrated. See below.rDrE}rF(hjAhj?ubaubj)rG}rH(hXpackage edu.luc.etl.sigcse13.scala.integration
// begin-object-Fixtures
object Fixtures {
def sqr(x: Double): Double = x * x
}
// end-object-Fixtures
hjhhhjh}rI(jh ]jjh#]h"]UsourceXn/home/gkt/Work/notes/examples/integration/src/main/scala/edu/luc/etl/sigcse13/scala/integration/Fixtures.scalah!]h$]uh&Mh'hh(]rJhLXpackage edu.luc.etl.sigcse13.scala.integration
// begin-object-Fixtures
object Fixtures {
def sqr(x: Double): Double = x * x
}
// end-object-Fixtures
rKrL}rM(hUhjGubaubeubh:)rN}rO(hUhh=hhhh?h}rP(h ]h!]h"]h#]rQUrunningrRah$]rSh auh&Mh'hh(]rT(hE)rU}rV(hXRunningrWhjNhhhhIh}rX(h ]h!]h"]h#]h$]uh&Mh'hh(]rYhLXRunningrZr[}r\(hjWhjUubaubhP)r]}r^(hXSThe tradition of scientific computing is one where users *want* and *need* to
be able to run it from the command-line, often in an unattended fashion (say,
on a computing cluster or network of workstations or cloud resources). The
following is the main program we put together to run the integration of
:math:`f(x) = x^2` manually. You can specify the number of rectangles, the
number of times to run each of the experiments, and a grain size for testing
the combined parallel/sequential version, ``integrateParallelGranular()``.
We'll say more about this function in our performance discussion.hjNhhhhTh}r_(h ]h!]h"]h#]h$]uh&Mh'hh(]r`(hLX9The tradition of scientific computing is one where users rarb}rc(hX9The tradition of scientific computing is one where users hj]ubj)rd}re(hX*want*h}rf(h ]h!]h"]h#]h$]uhj]h(]rghLXwantrhri}rj(hUhjdubahjubhLX and rkrl}rm(hX and hj]ubj)rn}ro(hX*need*h}rp(h ]h!]h"]h#]h$]uhj]h(]rqhLXneedrrrs}rt(hUhjnubahjubhLX to
be able to run it from the command-line, often in an unattended fashion (say,
on a computing cluster or network of workstations or cloud resources). The
following is the main program we put together to run the integration of
rurv}rw(hX to
be able to run it from the command-line, often in an unattended fashion (say,
on a computing cluster or network of workstations or cloud resources). The
following is the main program we put together to run the integration of
hj]ubh)rx}ry(hUh}rz(UlatexX
f(x) = x^2h#]h"]h ]h!]h$]uhj]h(]hjubhLX manually. You can specify the number of rectangles, the
number of times to run each of the experiments, and a grain size for testing
the combined parallel/sequential version, r{r|}r}(hX manually. You can specify the number of rectangles, the
number of times to run each of the experiments, and a grain size for testing
the combined parallel/sequential version, hj]ubj)r~}r(hX``integrateParallelGranular()``h}r(h ]h!]h"]h#]h$]uhj]h(]rhLXintegrateParallelGranular()rr}r(hUhj~ubahjubhLXC.
We'll say more about this function in our performance discussion.rr}r(hXC.
We'll say more about this function in our performance discussion.hj]ubeubj)r}r(hXpackage edu.luc.etl.sigcse13.scala.integration
import Integration._
import Fixtures.sqr
object Main extends {
def main(args: Array[String]) {
try {
require { 2 <= args.length }
val rectangles = math.max(args(0).toInt, 1000)
val n = math.max(args(1).toInt, 1)
val grainSize = if (args.length == 3) math.min(args(2).toInt, rectangles) else rectangles
timedRun(rectangles, n, "sequentially", integrateSequential)
timedRun(rectangles, n, "in parallel", integrateParallel)
timedRun(rectangles, n, "in parallel with " + grainSize +
" rectangles per serial worker", integrateParallelGranular(grainSize))
} catch {
case _: NumberFormatException => usage()
case _: IllegalArgumentException => usage()
}
}
def usage() {
Console.err.println("usage: rectangles (>= 1000) " +
"numberOfRuns (>= 1) [ grainSize (rectangles % grainSize == 0) ]")
}
def timeThis[A](s: String)(block: => A): A = {
val time0 = System.currentTimeMillis
val b = block
val time1 = System.currentTimeMillis - time0
println("Timing " + s + " = " + time1)
b
}
// begin-timedRun
def timedRun(rectangles: Int, n: Int, how: String,
integrationStrategy: (Double, Double, Int, Fx) => Double) {
timeThis(how) {
print("Computing area " + how + "; now timing " + n + " iterations")
val area: Double = (1 to n).map { _ => integrationStrategy(0, 10, rectangles, sqr) }.head
println("; area = " + area)
}
}
// end-timedRun
}hjNhhhjh}r(jh ]jjh#]h"]UsourceXj/home/gkt/Work/notes/examples/integration/src/main/scala/edu/luc/etl/sigcse13/scala/integration/Main.scalah!]h$]uh&M&h'hh(]rhLXpackage edu.luc.etl.sigcse13.scala.integration
import Integration._
import Fixtures.sqr
object Main extends {
def main(args: Array[String]) {
try {
require { 2 <= args.length }
val rectangles = math.max(args(0).toInt, 1000)
val n = math.max(args(1).toInt, 1)
val grainSize = if (args.length == 3) math.min(args(2).toInt, rectangles) else rectangles
timedRun(rectangles, n, "sequentially", integrateSequential)
timedRun(rectangles, n, "in parallel", integrateParallel)
timedRun(rectangles, n, "in parallel with " + grainSize +
" rectangles per serial worker", integrateParallelGranular(grainSize))
} catch {
case _: NumberFormatException => usage()
case _: IllegalArgumentException => usage()
}
}
def usage() {
Console.err.println("usage: rectangles (>= 1000) " +
"numberOfRuns (>= 1) [ grainSize (rectangles % grainSize == 0) ]")
}
def timeThis[A](s: String)(block: => A): A = {
val time0 = System.currentTimeMillis
val b = block
val time1 = System.currentTimeMillis - time0
println("Timing " + s + " = " + time1)
b
}
// begin-timedRun
def timedRun(rectangles: Int, n: Int, how: String,
integrationStrategy: (Double, Double, Int, Fx) => Double) {
timeThis(how) {
print("Computing area " + how + "; now timing " + n + " iterations")
val area: Double = (1 to n).map { _ => integrationStrategy(0, 10, rectangles, sqr) }.head
println("; area = " + area)
}
}
// end-timedRun
}rr}r(hUhjubaubeubh:)r}r(hUhh=hhhh?h}r(h ]h!]h"]h#]rU$initial-experiments-with-performancerah$]rhauh&M+h'hh(]r(hE)r}r(hX$Initial Experiments with PerformancerhjhhhhIh}r(h ]h!]h"]h#]h$]uh&M+h'hh(]rhLX$Initial Experiments with Performancerr}r(hjhjubaubhP)r}r(hX=This is still being written up but will be demonstrated live.rhjhhhhTh}r(h ]h!]h"]h#]h$]uh&M-h'hh(]rhLX=This is still being written up but will be demonstrated live.rr}r(hjhjubaubj)r}r(hX def integrateParallelGranular(grainSize: Int)(a: Double, b: Double, rectangles: Int, f: Fx): Double = {
require { rectangles % grainSize == 0 } // can relax this later
val workers = rectangles / grainSize
val interval = (b - a) / workers
val fullIntegration = (0 until workers).par.view map { n =>
val c = a + n * interval
integrateSequential(c, c + interval, grainSize, f)
}
fullIntegration.sum
}
hjhhhjh}r(jh ]jjh#]h"]UsourceXq/home/gkt/Work/notes/examples/integration/src/main/scala/edu/luc/etl/sigcse13/scala/integration/Integration.scalah!]h$]uh&M/h'hh(]rhLX def integrateParallelGranular(grainSize: Int)(a: Double, b: Double, rectangles: Int, f: Fx): Double = {
require { rectangles % grainSize == 0 } // can relax this later
val workers = rectangles / grainSize
val interval = (b - a) / workers
val fullIntegration = (0 until workers).par.view map { n =>
val c = a + n * interval
integrateSequential(c, c + interval, grainSize, f)
}
fullIntegration.sum
}
rr}r(hUhjubaubeubh;eubhhhh?h}r(h ]h!]h"]h#]rU
previous-workrah$]rh
auh&M5h'hh(]r(hE)r}r(hX
Previous Workrhh;hhhhIh}r(h ]h!]h"]h#]h$]uh&M5h'hh(]rhLX
Previous Workrr}r(hjhjubaubhP)r}r(hXThis example was developed as part of High-Performance Java Platform Computing
by Thomas W. Christopher and George K. Thiruvathukal.rhh;hhhhTh}r(h ]h!]h"]h#]h$]uh&M7h'hh(]rhLXThis example was developed as part of High-Performance Java Platform Computing
by Thomas W. Christopher and George K. Thiruvathukal.rr}r(hjhjubaubj)r}r(hUhh;hhhjh}r(h ]h!]h"]h#]h$]uh&Nh'hh(]r(j)r}r(hXc|pdf| PDF of Book
https://hpjpc.googlecode.com/files/HPJPC%20Christopher%20and%20Thiruvathukal.pdf
hjhhhjh}r(h ]h!]h"]h#]h$]uh&M;h(]r(j)r}r(hX|pdf| PDF of Bookrhjhhhjh}r(h ]h!]h"]h#]h$]uh&M;h(]r(h*)r}r(hXJimage:: figures/pdf.png
:alt: PDF
:align: middlerh}r(UalignXmiddlerUuriXfigures/pdf.pngrh#]h"]h ]h!]h1}rU*jsh$]UalthXPDFrr}rbuhjh(]hh6ubhLX PDF of Bookrr}r(hX PDF of Bookhjubeubj)r}r(hUh}r(h ]h!]h"]h#]h$]uhjh(]rhP)r}r(hXPhttps://hpjpc.googlecode.com/files/HPJPC%20Christopher%20and%20Thiruvathukal.pdfrhjhhhhTh}r(h ]h!]h"]h#]h$]uh&M;h(]rj)r}r(hjh}r(Urefurijh#]h"]h ]h!]h$]uhjh(]rhLXPhttps://hpjpc.googlecode.com/files/HPJPC%20Christopher%20and%20Thiruvathukal.pdfrr}r(hUhjubahj!ubaubahjubeubj)r}r(hXc|bitbucket| ZIP File
https://bitbucket.org/loyolachicagocs_books/hpjpc-source-java/get/default.zip
hjhhhjh}r(h ]h!]h"]h#]h$]uh&M>h'hh(]r(j)r}r(hX|bitbucket| ZIP Filerhjhhhjh}r(h ]h!]h"]h#]h$]uh&M>h(]r(h*)r}r(hh-h}r(Ualignh/Uurih0h#]h"]h ]h!]h1}rU*h0sh$]Ualth4uhjh(]hh6ubhLX ZIP Filerr}r(hX ZIP Filehjubeubj)r}r(hUh}r(h ]h!]h"]h#]h$]uhjh(]rhP)r}r(hXMhttps://bitbucket.org/loyolachicagocs_books/hpjpc-source-java/get/default.ziprhjhhhhTh}r(h ]h!]h"]h#]h$]uh&M>h(]rj)r}r(hjh}r(Urefurijh#]h"]h ]h!]h$]uhjh(]rhLXMhttps://bitbucket.org/loyolachicagocs_books/hpjpc-source-java/get/default.zipr r
}r(hUhjubahj!ubaubahjubeubj)r}r
(hXa|bitbucket| via Mercurial
hg clone https://bitbucket.org/loyolachicagocs_books/hpjpc-source-java
hjhhhjh}r(h ]h!]h"]h#]h$]uh&MAh'hh(]r(j)r}r(hX|bitbucket| via Mercurialrhjhhhjh}r(h ]h!]h"]h#]h$]uh&MAh(]r(h*)r}r(hh-h}r(Ualignh/Uurih0h#]h"]h ]h!]h1}rU*h0sh$]Ualth4uhjh(]hh6ubhLX via Mercurialrr}r(hX via Mercurialhjubeubj)r}r(hUh}r(h ]h!]h"]h#]h$]uhjh(]rhP)r }r!(hXFhg clone https://bitbucket.org/loyolachicagocs_books/hpjpc-source-javahjhhhhTh}r"(h ]h!]h"]h#]h$]uh&MAh(]r#(hLX hg clone r$r%}r&(hX hg clone hj ubj)r'}r((hX=https://bitbucket.org/loyolachicagocs_books/hpjpc-source-javar)h}r*(Urefurij)h#]h"]h ]h!]h$]uhj h(]r+hLX=https://bitbucket.org/loyolachicagocs_books/hpjpc-source-javar,r-}r.(hUhj'ubahj!ubeubahjubeubj)r/}r0(hXx|instructions| Build and Run Instructions
https://bitbucket.org/loyolachicagocs_plsystems/integration-scala/overview
hjhhhjh}r1(h ]h!]h"]h#]h$]uh&MGh'hh(]r2(j)r3}r4(hX)|instructions| Build and Run Instructionsr5hj/hhhjh}r6(h ]h!]h"]h#]h$]uh&MGh(]r7(h*)r8}r9(hjPh}r:(UalignjRUurijSh#]h"]h ]h!]h1}r;U*jSsh$]UaltjVuhj3h(]hh6ubhLX Build and Run Instructionsr<r=}r>(hX Build and Run Instructionshj3ubeubj)r?}r@(hUh}rA(h ]h!]h"]h#]h$]uhj/h(]rBhP)rC}rD(hXJhttps://bitbucket.org/loyolachicagocs_plsystems/integration-scala/overviewrEhj?hhhhTh}rF(h ]h!]h"]h#]h$]uh&MDh(]rGj)rH}rI(hjEh}rJ(UrefurijEh#]h"]h ]h!]h$]uhjCh(]rKhLXJhttps://bitbucket.org/loyolachicagocs_plsystems/integration-scala/overviewrLrM}rN(hUhjHubahj!ubaubahjubeubeubh)rO}rP(hX).. |if-else| replace:: ``if``\ -``else``
hh;hhhhh}rQ(h ]h!]h"]h#]h$]rRXif-elserSauh&MIh'hh(]rT(j)rU}rV(hX``if``h}rW(h ]h!]h"]h#]h$]uhjOh(]rXhLXifrYrZ}r[(hUhjUubahjubhLX-r\}r](hX\ -hjOubj)r^}r_(hX``else``h}r`(h ]h!]h"]h#]h$]uhjOh(]rahLXelserbrc}rd(hUhj^ubahjubeubh)re}rf(hX5.. |if-else-if| replace:: ``if``\ -``else``\ -``if``
hh;hhhhh}rg(h ]h!]h"]h#]h$]rhX
if-else-ifriauh&MKh'hh(]rj(j)rk}rl(hX``if``h}rm(h ]h!]h"]h#]h$]uhjeh(]rnhLXifrorp}rq(hUhjkubahjubhLX-rr}rs(hX\ -hjeubj)rt}ru(hX``else``h}rv(h ]h!]h"]h#]h$]uhjeh(]rwhLXelserxry}rz(hUhjtubahjubhLX-r{}r|(hX\ -hjeubj)r}}r~(hX``if``h}r(h ]h!]h"]h#]h$]uhjeh(]rhLXifrr}r(hUhj}ubahjubeubh8eubhhhhh}r(h ]h!]h"]h#]h$]rh7auh&MMh'hh(]r(j)r}r(hX``do``h}r(h ]h!]h"]h#]h$]uhh8h(]rhLXdorr}r(hUhjubahjubhLX-r}r(hX\ -hh8ubj)r}r(hX ``while``h}r(h ]h!]h"]h#]h$]uhh8h(]rhLXwhilerr}r(hUhjubahjubeubXhtmlrh)r}r(hXX.. |html| image:: figures/html.png
:alt: HTML
:align: middle
hhhhhhh}r(h ]h!]h"]h#]h$]rjauh&Kh'hh(]rh*)r}r(hXLimage:: figures/html.png
:alt: HTML
:align: middleh}r(UalignXmiddleUuriXfigures/html.pngrh#]h"]h ]h!]h1}rU*jsh$]UalthXHTMLrr}rbuhjh(]hh6ubaubXepubrh)r}r(hXW.. |epub| image:: figures/epub.png
:alt: ePub
:align: middle
hhhhhhh}r(h ]h!]h"]h#]h$]rjauh&Kh'hh(]rh*)r}r(hXLimage:: figures/epub.png
:alt: ePub
:align: middleh}r(UalignXmiddleUuriXfigures/epub.pngrh#]h"]h ]h!]h1}rU*jsh$]UalthXePubrr}rbuhjh(]hh6ubaubXpdfrh)r}r(hXT.. |pdf| image:: figures/pdf.png
:alt: PDF
:align: middle
hhhhhhh}r(h ]h!]h"]h#]h$]rjauh&Kh'hh(]rh*)r}r(hjh}r(UalignjUurijh#]h"]h ]h!]h1}rU*jsh$]Ualtjuhjh(]hh6ubaubjijejSjOXinstructionsrh)r}r(hXo.. |instructions| image:: figures/instructions.png
:alt: Instructions
:align: middle
hhhhhhh}r(h ]h!]h"]h#]h$]rjauh&Kh'hh(]rh*)r}r(hjPh}r(UalignjRUurijSh#]h"]h ]h!]h1}rU*jSsh$]UaltjVuhjh(]hh6ubaubuUparse_messagesr]rUcurrent_sourcerNU
decorationrNUautofootnote_startrKUnameidsr}r(hjohjhjh jRh
jhhBhjh
hhjuh(]r(hjjjjcsphinx.addnodes
highlightlang
r)r}r(hUhhhhhU
highlightlangrh}r(UlangXscalaUlinenothresholdI9223372036854775807
h#]h"]h ]h!]h$]uh&Kh'hh(]ubh=ehUUtransformerrNU
footnote_refsr}rUrefnamesr}rUsymbol_footnotesr]rUautofootnote_refsr]rUsymbol_footnote_refsr]rU citationsr]rh'hUcurrent_linerNUtransform_messagesr]rUreporterrNUid_startrKU
autofootnotesr]rU
citation_refsr}rUindirect_targetsr]rUsettingsr(cdocutils.frontend
Values
ror}r(Ufootnote_backlinksrKUrecord_dependenciesrNUrfc_base_urlrUhttp://tools.ietf.org/html/rU tracebackrUpep_referencesrNUstrip_commentsrNU
toc_backlinksrUentryrU
language_coderUenrU datestamprNUreport_levelrKU_destinationrNU
halt_levelrKU
strip_classesrNhINUerror_encoding_error_handlerrUbackslashreplacerUdebugrNUembed_stylesheetrUoutput_encoding_error_handlerrUstrictrU
sectnum_xformrKUdump_transformsrNU
docinfo_xformrKUwarning_streamr NUpep_file_url_templater
Upep-%04drUexit_status_levelrKUconfigr
NUstrict_visitorrNUcloak_email_addressesrUtrim_footnote_reference_spacerUenvrNUdump_pseudo_xmlrNUexpose_internalsrNUsectsubtitle_xformrUsource_linkrNUrfc_referencesrNUoutput_encodingrUutf-8rU
source_urlrNUinput_encodingrU utf-8-sigrU_disable_configrNU id_prefixrUU tab_widthrKUerror_encodingrUUTF-8r U_sourcer!U(/home/gkt/Work/notes/source/parallel.rstr"Ugettext_compactr#U generatorr$NUdump_internalsr%NUsmart_quotesr&Upep_base_urlr'Uhttp://www.python.org/dev/peps/r(Usyntax_highlightr)Ulongr*Uinput_encoding_error_handlerr+jUauto_id_prefixr,Uidr-Udoctitle_xformr.Ustrip_elements_with_classesr/NU
_config_filesr0]Ufile_insertion_enabledr1Uraw_enabledr2KU
dump_settingsr3NubUsymbol_footnote_startr4KUidsr5}r6(jjhhjjhBh=jjjjjRjNjh;jojkuUsubstitution_namesr7}r8(hhh7h7jjjjjjjijijSjSjjuhh'h}r9(h ]h#]h"]Usourcehh!]h$]uU footnotesr:]r;Urefidsr<}r=ub.