CAB401: High Performance and Parallel Computing Assignment Due: 19/10/2020 (with proposal due by 04/09/2020) Worth: 50% Individual Overview You are to select a real world software application and manually parallelize it. That is, take any application that is not written in an explicitly parallel fashion and transform it so that it executes as efficiently as possible on a particular parallel computer. The software application can be whatever you like but you will obviously need access to its source code. It can for example be an open source application or an application that you have developed yourself, or perhaps one from your workplace. To be amenable to parallelization it will need to be relatively computationally intensive, i.e. it will need to perform sufficient computation so that parallelizing that computation will potentially produce a noticeable difference in perceived execution time. For example, a word processing application would probably not be a good candidate as such applications are already normally adequately responsive to user interaction. Note, that some applications are more amenable to parallelization than others. It is not expected that a perfect linear speedup will be achieved for all applications – simply that your parallelization achieves as much performance improvement as is available. Hardware You can use any parallel hardware that you have access to. You can make use of parallel computers provided by QUT or any other parallel computers you personally you have access to. It can be any form of parallel computer, e.g. multi-core, cluster, SMP, shared memory, distributed memory, GPU, etc. See criteria below regarding scalable parallelism. Software Again you can use whatever software that you have access to. This includes compilers, profilers, debuggers, libraries, etc. Some such software is available through QUT. You may use whatever programming language you wish and whatever parallel frameworks and libraries that you have access to. Submission Project Proposal, due 04/09/2019: Submit online form, describing: 1. A brief description of the sequential application that you have selected to parallelize. What does it do? Where did you find it? (1 paragraph max) 2. Discuss whether you think the proposed application performs sufficient computation so that parallelizing it will potentially produce a noticeable difference in perceived execution time. (1 paragraph max). 3. What parallel hardware and parallelization language/framework are you considering? E.g. targeting NVidia GPU programmed using CUDA. (1 paragraph max). The project proposal is designed to give you constructive feedback and to ensure you are on a productive path prior to final submission. Final Submission, due 19/10/2020, a zip file including both: 1. A report of 10-15 pages (not including appendices) describing your outcomes. The report should address the following criteria: a. An explanation of the original sequential application being parallelized, what it does (black box) and how it works (a high level description of software’s design/architecture). This might include call graphs, class diagrams, etc – whatever you find useful to describe the structure of the original sequential application. b. Your analysis of potential parallelism within the application. This might include identification of existing loops or control flow constructs where parallelism might be found. Explanation of the data and control dependences that you analysed to determine which sections of code were safe to parallelize. Which of these is likely to be of sufficient granularity to be worth exploiting? Is it scalable parallelism? A discussion of changes required to expose parallelism, such as replacing algorithms or code restructuring transformations. c. How did you map computation and/or data to processors? Which parallelism abstractions or programming language constructs did you use to perform synchronization? d. Timing and profiling results, both before and after parallelization and a speedup graph. e. How did you test that the parallel version produced the exact same results as the original sequential version? f. A description of the compilers, software, tools, and techniques you used to parallelize the application. g. The story of how you overcame performance problems/barriers (e.g. load imbalance, memory contention, granularity, data dependencies, etc) to improving parallel performance. h. An explanation of the code that you added or modified to parallelize the application (including source code line count). i. Reflect on your outcome – What have you learnt? How successful was your attempt? Do you think you’ve done as well as is possible? What might you have done differently? 2. Your source code (both before and after versions) together with instructions for compiling, running, hardware requirements and realistic input data sets. Assessment Criteria Criteria Standards Unsatisfactory Satisfactory (50%) Good Excellent (100%) Analysis of original application (10 marks) Demonstrates a deep understanding of the original application, its structure and performance issues/bottlenecks. (Must include identification and discussion of data and control dependencies and detailed before and after detailed profiling results). Use of tools and techniques (10 marks) Demonstrates advanced use of a wide variety of parallel programming software, tools and technologies. Optimal Speedup (10 marks) Obtained very close to the best possible performance improvement for the application (must be more than 4 cores for excellent). (Must include a correctly constructed speed-up graph). Overcoming Barriers (10 marks) Demonstrated great skill and effort to achieve this outcome and overcome significant barriers to improved performance. (Include interesting before and after code snippets) Report (10 marks) Report is well structured, easy to read, reflective and insightful.
