0
$\begingroup$

I want to implement parallel Floyd-Warshall algorithm in assembler.

The FW algorithm is all about if and assign statements executed in an inner-most loop:

# D is an adjacency matrix of size n x n
for k : n
  for i : n
    for j : n
      if (D[i, j] > D[i, k] + D[k, j])
        D[i, j] := D[i, k] + D[k, j]

I want to achieve simple parallelization on the assembly level, by unrolling the inner-most (index with j) loop. For example, I can assume that the graph is of some size 4n and in the inner-most loop I can do j += 4 instead of j++.


My question: will this parallelization work?

In my opinion, this should work if all the assignments performed within one full inner-most loop cycle are independent. Full inner-most loop cycle means k = const, i = const, j = changes, whereas independent means that the order of iteration over j loop does not matter (and hence: order of assignment).


I have prepared a simple visualization of full middle loop cycle for an adjacency matrix of size 4 x 4, for k = 2.

Visualization

Before I start with the implementation I wanted to make sure that it will actually work. :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.