CSE41CON Assignment 1998

Due Date 11/6/98 (9am)

Problem Overview

This assignment asks you to design two programs to process a black and white image to identify the size of the largest connected object in the image.

You should assume that,

• the image is 512 by 512 pixels,
• pixel values are 0 (white) or 255 (black),
• there may be more than one object in the image,
• the objects are black on a white background.

Objectives

The overall assignment tests the ability to devise and implement a parallel program for a parallel computer using a shared memory programming model.

Stage 1

This section of the assignment tests the ability of the student to devise a sequential and parallel algorithm to solve the set problem. These algorithms are to be presented as structured pseudocode. The data allocation scheme used by the parallel algorithm should be explained with the aid of a diagram.

The specific objectives are,

• (5 Marks) To analyse the problem and devise;
  • (2 marks) a sequential algorithm,
  • (3 marks) and a parallel algorithm, including a workload allocation diagram.
• (2.5 Marks) Perform a time and storage complexity analysis of both algorithms and using these measures predict the performance improvement that you expect from the parallel code.

Stage 2

Implement the algorithms you have designed and evaluate the performance of the parallel algorithm in comparison to the sequential. Use speedup graphs for a range of machine sizes from 2 to 32 in steps of 2 to show how your parallel algorithm compares to the sequential.

The specific objectives are,

• (5 marks) To implement and debug a parallel program using DiST and Modula-P.
• (1 marks) To evaluate the performance of a parallel algorithm using empirical execution time data.
• (1 marks) To compare the empirical performance and predicted performance and discuss the relationship between them.

The remaining [0.5 marks] are allocated to optimising the performance of your parallel program, and showing how re-writing sections of the algorithm can improve performance. You should discuss the reasons for your optimisations, and why they improve the performance of the parallel program.

Submission

Submission will be electronically managed via the commands submit and verify. To submit your assignment create a directory called "CON". Copy into that directory the following files.

• A Modula-P source code file with procedures that implement the sequential and parallel solutions to the problem.
• A text file giving your algorithm structure, storage and time complexity analysis and speedup results, The report should use those results to discuss how well the actual performance matches your predictions. You should also comment on the correctness of your program, including identifying any known bugs.

Execute the command "submit CON<CR>" to send the contents of the directory to the submission site. You can check that the submission has been successful by issuing a "verify" command. If you make an incorrect submission resubmit using the "submit" command again. This will overwrite your previous submission.

Due Date 11/6/98, at 9am

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -link 0 question.tex.

The translation was initiated by Arnold N. Pears on Tue Jun 2 17:51:39 AEST 1998