Project
Description
Given a series Q of N integers (positive or negative), the max subarray of Q is the largest contiguous subarray such that the sum of its element is maximum.
For example, given Q
The max subsequence is
6
-1
8
Remark : if the max subarray is not unique, the first one should be returned.
There are many solutions to this problem. One is Kadane's algorihm which solves it in O(N) but cannot be parallelized. We will consider a solution proposed by Perumalla et al.
Parallel Algorithm
This solution relies on 2 applications of the SCAN/PREFIX algorithm. The first one is sum-prefix and uses the sum operation on the array. The second is max-prefix and uses the max function. To implement it, simply start from the sum-prefix version and replace sum with max() and the initial 0 values with the neutral value for max.
It also uses a SUFFIX operation which works in reverse order on the array.
Max subarray :
Input : Q array of N integers
Output : Max subsequence
- Compute sum-prefix of Q and store them in array PSUM
- Compute sum-suffix of Q and store them in array SSUM
- Compute max-suffix of PSUM and store them in array SMAX
- Compute max-prefix of SSUM and store them in array PMAX
- for 1 <= i <= n do in parallel
- Ms[i] = PMAX[i] - SSUM[i] + Q[i]
- Mp[i] = SMAX[i] - PSUM[i] + Q[i]
- M[i] = Ms[i] + Mp[i] - Q[i]
- Find the subarray with the largest value in M. The indexes of this subarray are the indexes of the subarray of Q giving this sum.
Example
This example comes from the article in references. It is important to understand each step and verify the computation.
Implementation
The algorithm should be implemented in a single file yourSurname.c (family name) with the following constraints.
- The compilation should have no warning with gcc -Wall .... -fopenmp -lm
- The input file (array) will be given on the command line.
- ./yourSurname fichier1
- The output should be the maximum sum found, followed by the elements of the subarray. All elements should be separated by a space and the line will end with a '\n'. For example, with the Q array given in example, the output will be
- 28 11 10 -6 4 9
The input file is assumed to be well written, i.e. no errors, correct numbers...It will contain n =2ˆm elements.
Testing your solution
The following zip file contains a python script for testing your solution. Place your file yourSurname.c in the src directory and execute the following command :
~/>python3 evaluate.py yourName;True;True;False;Error
The first column is the compilation result (Trues). The second column is the first dataset, it's True so everything is fine. The second dataset have given an incorrect result (False) and the last one crashed or did not produce results after a 5s timeout.
Submission
The project should be submitted as a GitHub repository on https://classroom.github.com/a/uK9aYVM8 as 2 files before the 15th of January, 6.00pm with the final version in the master branch.
- A file yourSurname.c which can be compiled using only
gcc -o nom -Wall -std=c99 nom.c -lm -fopenmp - A readme.txt file stating which methods are parallel. For example, use the following format
- void prefixSum(....) : parallel
- void displayResult(...) : non parallel
- .....
Grading
The following points are evaluated
- Compiling without errors or warning
- Correct execution on multiple datasets
- Parallelism level (each of the 6 steps of the algorithm can be parallelized).
- The fastest parallel version will have a bonus point.
The evaluation of mostly done automatically so if the output format is incorrect, the program will be assumed to be incorrect !