1
edit
Changes
→Description of the project
For my project instead of picking a new method to learn to parallelise with, I decided to try to paralellise an algorithm that is fairly hard to write, to see if after following this course I could actually parallelise an algorithm. The thing is, in the workshops we have only been parallelising algorithms that have been specifically written to be parallelised. I wanted to change that and see if I could still do it. The algorithm I am parallelising is a Branch & Bound Algorithm by Little from 1966. A good explanation of the algorithm can be found here: https://www.youtube.com/watch?v=nN4K8xA8ShM, the explanation of the branch and bound I wrote starts at 34:30.
=== Assignment 2 =Description==First off because I am not a C / C++ programmer I had a lot of trouble learning C++ syntax and what I could and could not do in my program. I think as a result the program is also slower than it should be. Some difficulties and how I solved them:* After removing a row or column, the matrix would be skewed, we would have to keep track of the exact columns and rows we removed and calculate our current value based on that entire history along the way.The way I remedied that is that instead of removing the rows and columns, I put a sentinel value in them (UINT16_MAX), the rest of the algorithm just ignores that value. * Not all of the column minima need to be found, since if you have a row minimum in a column that automatically turns into a column minimum, due to the nature of the algorithm.When searching for row minima I kept a bool array of which columns I had already found a value for, so that I would not have to search those *columns in the findColMinima function. *Subtour eliminationStore the result as partial tours,If an assignment is the start of a tour and the end of a tour, place it in between and concatenate the tour.If an assignment is the start of a tour, place it before the tour.If an assignment is the end of a tour, place it behind the tour.If an assignment is not part of a tour, create a new tour with it.Find out which tour the assignment got added to and eliminate the subtour that goes from the end of that tour to the beginning. I wanted to parallelise certain sections of the algorithm, most notable :finding the row and column minimumsubtracting the row and column minimum With a cilk_for reducer and a vectorized cilk_for this should have been possible, the thing is, I wrote the algorithm in such a way that instead of searching for a minimum, it searches for the location of the minimum. This turned out to be a problem when trying to parallelise it.
==Source==