Assignment #1 – Functional Programming for Parallel Processing Introduction
This assignment aims to consolidate your understanding of several topics taught in this course, such as applied functional programming and parallel /distributed processing. You are required to build and evaluate several versions of a simple but fundamental algorithm, Longest Common
Subsequence (LCS). This algorithm is very important, e.g. in bio-informatics, and efficient parallel versions are still sought and proposed.
For example, consider strings s1=”acba” and s2=”abcdad”. The LCS length is 3, given by the subsequence “aca” (or “aba”), as described by the following snapshots (s1 is the NS axis and s2 the WE axis):
For our purpose, we only require the LCS length, not the corresponding longest sunsequence(s). So, you won’t need any backtrace array like P above.
You are required to design and develop two command-line programs and write one evaluation report.
You will develop , A1F.EXE in F#, and A1C.EXE in C#. Each of these programs will run three different versions:
- Sequential implementation (SEQ), used as a baseline to evaluate the parallel speedup.
- Actor implementation (ACT), used to evaluate the parallel speedup for the Actor model. For F#, you will use its own MailboxProcessor, which provides unbounded queues. For C#, you will use the channel library with unbounded queues.
- CSP implementation (CSP), used to evaluate the parallel speedup for the CSP model.For F#, you will use the Hopac library, with size 0 buffers. For C#, you will use the channel library with size 1 buffers.
Your programs will be run and expected to show parallel speedups even on a single lab machine with several cores. However, your parallel Actors design should be amenable to run on a distributed cluster. You can read more about such topics in the Berkeley patterns for parallel computing, esp. the structured grid dwarf.
To ensure a fair playing field, you will base your design on the simple dynamic programming (DP) algorithm. However, some of the strings could be quite large. For space efficiency, you will need to consider replacing DP arrays by diagonal wave-fronts, instead of the textbook array approach. For parallel efficiency, you will need to consider a courser granularity, by splitting the virtual DP array into a grid of subarrays, defined by the intersection of horizontal and vertical bands. Finally, you will probably need to streamline your design by using sentinel values for the arrays/subarrays borders.
Figures 1, 2, and 3 schematically illustrate the progression of the diagonals wave-fronts, Fig. 1 for sequential processing, Figs. 2 and 3 for the parallel case with a courser granularity defined by horizontal and vertical bands. Green areas indicate active cells, currently on a diagonal wave-front. Yellow areas indicate already processed cells. White areas indicate unprocessed cells. Red lines indicate boundaries between bands.
Running the Programs
Figure 3: PAR (async evolution)
- Please strictly follow these conventions (for consistency with the marking tools)! 1. Invoking the F# program – one of the following command lines.
- Standard output: see appendix!
- Error output: may contain any additional traces which you want. However, these may affect the runtime, so you should disable these for the final submission.
- Invoking the C# program – as above, just replace A1F by A1C.
The report must contain a brief and of your own results. You will evaluate the relative performance of the versions vs. the message-based parallel versions, using tables and plots.
Your report should be structured and written like a research article, of (normally) up to 6 pages. It should contain: title, author, abstract, introduction, good and updated literature overview, brief descriptions of your algorithms, clear empirical evaluations of the runtimes of your implementations, conclusions, and bibliography.
As indicated by the highlights, the focus should be on the literature overview and your own empirical evaluation. Note that you can start working on your report from day one: only the empirical evaluation and conclusions need to wait for your results.
Suggestion to use a good and “standard” format for scientific publications, such as the LNCS article style, either in LaTeX (preferable) or Word.
Deliverables and Submission
Submit electronically, to the ADB web dropbox, an upi.7z archive containing an upi folder with: o your report as PDF; o your .FS F# source file(s); o a _COMPILE.FS.BAT batch file to compile your F# file(s) into an A1F.EXE executable.
o your .CS C# source file(s); o a _COMPILE.CS.BAT batch file to compile your C# file(s)
into an A1C.EXE executable.
Please do not submit anything else: no VS or VS Code solutions/projects, no copie of the neede
libraries, such as: Hopac.*.dll, System.Threading.Channels.dll, … (we already have copies of these)
Please keep your electronic dropbox receipt and follow the instructions given in our web pages, including our policy on plagiarism.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx