Parallel Implementations of (sum-)Scan Operation and Its Applications

Instructions:

In this research project, students are asked to study the theory and implementations behind a very important parallel primitive -i.e. the scan primitive- and its numerous applications. There are two main approaches in implementing the scan primitive on a Parallel Random Access Machine (PRAM) for achieving efficient data parallelism.

The project involves reading the base articles and book chapters by Daniel Hillis and Guy Steele and by Guy Blelloch who introduced two implementations of the parallel scan primitive and writing a report on your understanding of the scan primitive and its applications.

Please read the instructions here carefully and start working on your project as soon as possible to give yourself time to critically think about and to write a successful report on this project.

Overview:

Scan operation is a very important operation in many computing applications. The idea is to work on a vector of elements and keep a running operation (per-element) of the input vector.

This operation has a very straightforward serial implementation, involving a loop to go through each element of the input vector. However, the serial scan operation suffers from a O(n) running time, where n is the number of input elements in the array.

Data Parallel scan operations have the potential to reduce this requirement to O(lg n), thereby speeding up the process drastically for a large number of input elements.

Applications of this operation include, radix sort, quick sort, line-of-sight, line drawing, and many more. Therefore, an efficient implementation of such an important primitive could potentially help improve the performance of many applications.

Reading Materials

There are two required reading documents that students are asked to read and comprehend. Student reports are to be based on student's complete understanding of these documents. However, please feel free to search online for additional documents or reference materials that help your understanding of the theoretical and application concepts for this research project.

The following are the references to the required reading materials. You may find the .pdf files of these documents as attachments to the assignment on your blackboard. [1] Daniel Hillis and Guy Steele, (1986). "Data Parallel Algorithms", in Communications of ACM, 29(12), pp. 1170-1182. [2] Guy E. Blelloch, (1991). "Prefix Sums and Their Applications", in Synthesis of Parallel Algorithms (ed:JohnReif), Morgan Kaufmann, pp. 35-60.

Tasks:

Student's tasks are to start working on the two papers (as presented in the Reading Materials section) and get a firm grasp of the theory behind, and applications of the Scan primitive. 1- After a solid understanding of the concepts, students are asked to write a report on the theoretical and algorithmic frameworks behind the concept of this research project. 2- The report will also include students working examples of the concepts presented in the paper(s). 3- Further, students are asked to search online (or by going on http://vcuhvlibrary.uhv.edu/ and clicking on Try OneSearch tab) to search for recent papers that utilize the concepts of this project in applications.

Reading Phase: Please download the required papers from the blackboard or from an online resource. Read the papers, and try to get a firm understanding of the concepts as well as the applications of these concepts. Once you are ready to proceed and are confident of your understanding of the concepts, you may start working on your report.

There are three parts for the report (as discussed above) and the format is described in the deliverable section.

Writing Phase: When you are ready to work on your report, please make sure that you include all the required deliverable materials. Please make sure that the report is structured in such a manner that the required items are easy to access and follow. There are not any restrictions on the number of pages, formatting style, or the structuring of your paper. As such, please make sure that your report follows a cohesive delivery and that by reading your paper the instructor can assess your evaluation of the concepts and understanding of the materials. Your report may also need you to present working examples or answer some specific questions.

A comprehensive report is required as the sole deliverable material for this research project. Each student is asked to write his/her own report on the required materials. However, you may use any other material in addition to the required reading contents to help your understanding of the concepts and applications as a part of this research project.

The following is a generic format that the report may follow and the contents that the report is required to include. However, the structuring of the report is left to the student to decide.

Introduction Please include an introduction section to your report. This section should include the following items at the minimum: 1- A brief introduction to the concepts of this research paper 2- A short presentation of the importance of the concepts to be presented (in theory and applications) 3- A brief overview of the structure of the rest of the report

Literature Review This section will include students' review of both the Hillis and Steele (1986) and Belloch (1991) papers. Include an overview of each paper, what concepts were covered in each paper and present a broad and high level description of major contributions of each paper.

Theoretical Concepts After the review of the papers, please write a section on the theoretical concepts that each paper covers. In this section, please write your own understanding of each method. You may use two subsections that cover the Hillis and Steele, and the Blelloch's algorithms separately. Use diagrams, tables, or figures to discuss each method and present your understanding of each method to the best of your ability. NOTE: (highly recommended) please show two examples for the method discussed each paper. These examples will help solidify your understanding as well as show case your grasp of the concepts.

Typical Applications Choose one application out of each paper and discuss an algorithm and show examples of how the algorithm works. You may also have subsections for each algorithm. Please present as many diagrams, or examples as needed to show your understanding of how each application works.

Recent Experiments For this section, students are asked to research the applications of the Scan primitive (either Hillis/Steele or Blelloch's implementation) in a real-life application. Please describe the application, the use of scan for accelerating the application as presented by the author(s) of the work you are citing, and discuss the results of their experiments.

Citation and References

Please include all of the references you used for this project. Make sure that you have proper citations to the work you are referencing in your report appropriately. Your citations may follow APA, MLA, Chicago, or IEEE styles.