.. index:: double: parallelism; actors .. _actors: Parallelism using Actors ============================= In this section, we're going to take a look at the Java vs. Scala way of doing things. We'll look at a guiding example that is focused on concurrent/parallel computing. This example appeared in *High Performance Java Platform Computing* by Thomas W. Christopher and George K. Thiruvathukal. We'll show how to organize a previously worked out solution that uses more explicit concurrency mechanisms from Java and how it can be reworked into a side-effect free Scala version by taking advantage of Scala's innate support for basic actor-style parallelism. .. index:: double: algorithm; Longest Common Subsequence .. _lcs: Guiding Example: Longest Common Subsequence ---------------------------------------------- A longest common subsequence (LCS) of two strings is a longest sequence of characters that occurs in order in the two strings. It differs from the *longest common* substring in that the characters in the longest common subsequence need not be contiguous. There may, of course, be more than one LCS, since there may be several subsequences with the same length. There is a folk algorithm to find the *length* of the LCS of two strings. The algorithm uses a form of dynamic programming. In divide-and-conquer algorithms, recall that the overall problem is broken into parts, the parts are solved individually, and the solutions are assembled into a solution to the overall problem. Dynamic programming is similar, except that the best way to divide the overall problem into parts is not known before the subproblems are solved, so dynamic programming solves all subproblems and then finds the best way to assemble them. The algorithm works as follows: Let the two strings be ``c0`` and ``c1``. Create a two-dimensional array ``a``:: int [][] a=new int[c0.length()+1] [c1.length()+1] Initialize ``a[i][0]`` to 0 for all ``i`` and ``a[0][j]`` to 0 for all ``j``, since there are no characters in an empty substring. The other elements, ``a[i][j]`` , are filled in as follows:: for (int i=0; i <= c0.length(); i++) a[i][0] = 0; for (int j=0; j <= c1.length(); j++) a[0][j] = 0; We will fill in the array so that ``a[i][j]`` is the length of the LCS of ``c0.substring(0,i)`` and ``c1.substring(0,j)``. Recall that ``s.substring(m,n)`` is the substring of ``s`` from position ``m`` up to, but not including, position ``n``.:: for (i=1; i <= c0.length(); i++) for (j=1; j <= c1.length(); j++) if (c0.charAt(i-1) == c1.charAt(j-1)) a[i][j]=a[i-1][j-1]+1; else a[i][j]=Math.max(a[i][j-1],a[i-1][j]); The above shows a *traditional* imperative solution that constructs a result matrix comprising the results of the LCS. So how exactly does this method work? Element ``a[i-1][j-1]`` has the length of the LCS of string ``c0.substring(0,i-1)`` and ``c1.substring(0,j-1)``. If elements c0.charAt(i-1) and c1.charAt(j-1) are found to be equal, then the LCS can be extended by one to length ``a[i-1] [j-1]+1``. If these characters don’t match, then what? In that case, we ignore the last character in one or the other of the strings. The LCS is either ``a[i][j-1]`` or ``a[i-1][j]``, representing the maximum length of the LCS for all but the last character of ``c1.substring(0,j-1)`` or ``c0.substring(0,i-1)``, respectively. The chore graph from [HPJPC]_ for calculation of the LCS is shown in the following figure. .. image:: figures/lcs-systolic.png :alt: Systolic Array :width: 500 px :align: center Any order of calculation that is consistent with the dependencies is permissible. Two are fairly obvious: (1) by rows, top to bottom, and (2) by columns, left to right. Another possibility is along diagonals. All ``a[i][j]``, where ``i+j==m`` can be calculated at the same time, for ``m`` stepping from 2 to ``c0.length()+c1.length()``. . Visualizing waves of computation passing across arrays is a good technique for designing parallel array algorithms. It has been researched under the names systolic arrays and wavefront arrays [Wavefront]_. The following figure shows how a wavefront computation progresses. .. image:: figures/lcs-wavefront.png :alt: Wavefront Illustration :width: 500 px :align: center .. [Wavefront] H. T. Kung, C. E. Leiserson: Algorithms for VLSI processor arrays; in: C. Mead, L. Conway (eds.): Introduction to VLSI Systems; Addison-Wesley, 1979 .. [HPJPC] Thomas W. Christopher and George K. Thiruvathukal, *High Performance Java Platform Computing*, Prentice Hall PTR and Sun Microsystems Press, 2000. .. index:: double: concurrency; explicit double: parallelism; explicit Java Threads Implementation ---------------------------------- |bitbucket| ZIP File https://bitbucket.org/loyolachicagocs_books/hpjpc-source-java/get/default.zip |bitbucket| via Mercurial hg clone https://bitbucket.org/loyolachicagocs_books/hpjpc-source-java |instructions| Build and Run Instructions https://bitbucket.org/loyolachicagocs_books/hpjpc-source-java Our Java implementation (see `LCS.java `_) of the LCS algorithm divides the array into vertical bands and is pictured in Each band is filled in row by row from top to bottom. Each band (except the leftmost) must wait for the band to its left to fill in the last element of a row before it can start can start filling in that row. This is an instance of the producer-consumer releationship. The following figure shows how our Java solution organizes the work in bands: .. image:: figures/lcs-bands.png :alt: Systolic Array/Wavefront Illustration :width: 500 px :align: center LCS class .. highlight:: java .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-LCS-vars :end-before: end-LCS-vars :linenos: .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-LCS-constructor1 :end-before: end-LCS-constructor1 :linenos: .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-LCS-constructor2 :end-before: end-LCS-constructor2 :linenos: .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-LCS-startOfBand :end-before: end-LCS-startOfBand :linenos: .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-LCS-getLength :end-before: end-LCS-getLength :linenos: Band internal class (does the work) .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-Band-vars :end-before: end-Band-vars :linenos: .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-Band-constructor :end-before: end-Band-constructor :linenos: Actual Runnable body .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-Band-run :end-before: end-Band-run :linenos: Main .. literalinclude:: ../examples/hpjpc/src/info/jhpc/textbook/chapter06/LCS.java :start-after: begin-LCS-main :end-before: end-LCS-main :linenos: .. index:: single: systolic arrays single: Actors single: dataflow double: parallelism; implicit Scala Actors Implementation ------------------------------------ .. highlight:: scala |bitbucket| ZIP File https://bitbucket.org/loyolachicagocs_plsystems/lcs-systolicarray-scala/get/default.zip |bitbucket| via Mercurial hg clone https://bitbucket.org/loyolachicagocs_plsystems/lcs-systolicarray-scala |instructions| Build and Run Instructions https://bitbucket.org/loyolachicagocs_plsystems/lcs-systolicarray-scala Trait .. literalinclude:: ../examples/lcs-systolicarray/src/main/scala/edu/luc/etl/sigcse13/scala/lcs/SystolicArray.scala :start-after: begin-trait-SystolicArray :end-before: end-trait-SystolicArray :linenos: The entire SystolicArray implementation is here: .. literalinclude:: ../examples/lcs-systolicarray/src/main/scala/edu/luc/etl/sigcse13/scala/lcs/SystolicArray.scala :start-after: begin-trait-SystolicArray :end-before: end-trait-SystolicArray :linenos: .. index:: double: technique; logging .. _logging: Logging // begin-object-logger .. literalinclude:: ../examples/lcs-systolicarray/src/main/scala/edu/luc/etl/sigcse13/scala/lcs/SystolicArray.scala :start-after: begin-object-logger :end-before: end-object-logger :linenos: Apply .. literalinclude:: ../examples/lcs-systolicarray/src/main/scala/edu/luc/etl/sigcse13/scala/lcs/SystolicArray.scala :start-after: begin-object-apply :end-before: end-object-apply :linenos: The internal Cell class, used to represent the cells of the Systolic Array (generally). .. literalinclude:: ../examples/lcs-systolicarray/src/main/scala/edu/luc/etl/sigcse13/scala/lcs/SystolicArray.scala :start-after: begin-class-Cell :end-before: end-class-Cell :linenos: This is used for autowiring the quadrant from where messages are being fired (from). It is an example of how Scala can help us avoid making mistakes. In scientific computations, subscript problems are common. .. literalinclude:: ../examples/lcs-systolicarray/src/main/scala/edu/luc/etl/sigcse13/scala/lcs/SystolicArray.scala :start-after: begin-mapToHelper :end-before: end-mapToHelper :linenos: This is used to autowire the left and top edges of the array. Although easy enough to check, it can be difficult to remember which subscript is row or column. Scala again makes this very easy for us. As we'll see, it also helps to make the user function self-documenting (literate). .. literalinclude:: ../examples/lcs-systolicarray/src/main/scala/edu/luc/etl/sigcse13/scala/lcs/SystolicArray.scala :start-after: begin-posToHelper :end-before: end-posToHelper :linenos: Wrapping it up with object lcs... .. literalinclude:: ../examples/lcs-systolicarray/src/main/scala/edu/luc/etl/sigcse13/scala/lcs/lcs.scala :start-after: begin-object-lcs :end-before: end-object-lcs :linenos: Setting up the text fixtures... .. literalinclude:: ../examples/lcs-systolicarray/src/test/scala/edu/luc/etl/sigcse13/scala/lcs/Fixtures.scala :start-after: begin-lcs-Fixtures :end-before: end-lcs-Fixtures :linenos: Testing... .. literalinclude:: ../examples/lcs-systolicarray/src/test/scala/edu/luc/etl/sigcse13/scala/lcs/Tests.scala :start-after: begin-lcs-Tests :end-before: end-lcs-Tests :linenos: