## Description

The knapsack problem is a classic NP-hard resource allocation

problem, which is used in the management of parallel systems.

You are given a knapsack that is capable of holding up to a xed

weight called its capacity, C.

You are also given a collection of items, each of which has a weight wi

and a value vi

.

The task is to choose which items to put into the knapsack to

maximize the value of its contents.

Being NP-hard means that there is (probably) no algorithm that can

solve the problem time polynomial in the number of bits of its input.

However, there is a pseudo-polynomial time solution: one that is

polynomial in the largest value in the input, namely the capacity.

This algorithm is based on dynamic programming.

It sequentially nds the best solution for C

0 = 1, for C

0 = 2 etc., up to

C

0 = C.

Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 2 / 7

Code Summary and Input Format

A sequential algorithm for solving the integer knapsack problem has

been provided on LMS. The program reads an instance from standard

input (stdin) and outputs the maximum value that the knapsack can

carry.

The rst line of input is a single integer (long int) giving the

capacity of the knapsack.

The second line is a single integer (int) giving the number of items

that may be placed into the knapsack.

Each subsequent line of the input le, one per item, provides a pair of

positive integers:

value weight

Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 3 / 7

(Tiny) Example Input

The following example can be solved sequentially in microseconds.

Your submission will be tested on examples that take minutes to solve

sequentially.

100

5

83 83

62 62

43 43

20 20

5 5

Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 4 / 7

Tasks

You can either work individually, or with the same partner as for

Part A. If there is a compelling reason to change partners, please

contact Lachlan Andrew.

Write an MPI program that computes and outputs the maximum

value that can be carried in the knapsack, in the same format as done

by the sequential program.

Aim to have your program run as fast as possible. In doing so, you

may alter the calculations of the program, so long as the nal output is

correct. You can use algorithms that you nd in the literature (parallel

or sequential), but please do not directly copy code from elsewhere.

Use the sequential code as a base. Do not change the le before the

end of main(). If you need to include additional headers, they can be

included after main(). In particular, do not alter the timing

statements or add any of your own timing statements.

Write at most 750 words that outlines how you achieved

parallelism/high performance. Include tables and/or charts of your

own measurements that support your discussion.

Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 5 / 7

Assessment

Project 1 B is worth 13% of your total assessment. It is group work in

size of 2 at most.

Assessment of the report (5/13) is based on the level of details and

presentation.

Assessment of the program (8/13) is based on correctness and

performance. Incorrect programs (i.e. that give incorrect outputs or

that fail to compile/run) will attract few if any marks. The top 5

fastest running programs, when given a mystery work load (you will

not be told the work load in advance), will be given a bonus mark; i.e.

the maximum mark for this project part is 14/13.

At most ve people will get the bonus mark. If a sixth person is tied

with anyone in the top ve, then anyone tied with that sixth person

will not receive a bonus mark.

Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 6 / 7

Submission

Submit a PDF of your report (use PDF only, no other format will be

assessed) via LMS on or before Saturday 14th September. As well

you will need to submit your program directly on Spartan. The process

will be similar to that for Project 1a, but instructions for doing this

will be given closer to the deadline.

Optimal code often requires specic compiler options. As a comment

in the last line of your C code, put the exact command line used to

compile your code. Do not put anything else on that line

Use 10pt font, single line spacing, 25 mm margins all around and

double column formatting. Use appropriate headings and clearly label

and refer to tables, gures and references.

Clearly put your name and login name and those of your partner at the

top of the report.

Aaron Harwood and Lachlan Andrew (School of Computing and Information Systems The University of Melbourne) COMP90025 Parallel and Multicore Computing 2019 Semester II 7 / 7