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

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

1. Compute sum-prefix of Q and store them in array PSUM
2. Compute sum-suffix of Q and store them in array SSUM
3. Compute max-suffix of PSUM and store them in array SMAX
4. Compute max-prefix of SSUM and store them in array PMAX
5. for 1 <= i <= n do in parallel
   1. Ms[i] = PMAX[i] - SSUM[i] + Q[i]
   2. Mp[i] = SMAX[i] - PSUM[i] + Q[i]
   3. M[i] = Ms[i] + Mp[i] - Q[i]
6. 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 !

Références

• Maximum subarray problem (wikipedia)
• Parallel Algorithms For Maximum Subsequence And Maximum Subarray (1995) by Kalyan Perumalla and Narsingh Deo (link)