I want to implement parallel Floyd-Warshall algorithm in assembler.
The FW algorithm is all about
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
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.
Before I start with the implementation I wanted to make sure that it will actually work. :)