Floyd-Warshall Algorithm

• Deadline: 2025/04/27 23:59
• Points:
  • 120 pts for solution working at nominal speed (i.e. as fast as an unpublished reference solution)
  • +/-80 pts per ten-fold speed-up/slow-down, logarithmically

Reference algorithm

Floyd-Warshall Algorithm computes a matrix of shortest-path lengths in a directed graph. In our case, we assume non-negative edge lengths. In addition, any acyclic path in the graph is guaranteed to be shorter than 0x7FFF. This assumption allows to use 0x7FFF to indicate absence of an edge, including the guarantee that 2*0x7FFF fits in std::uint16_t.

    uint16_t inf = 0x7FFF;
    uint16_t c[N][N];

    for (std::size_t i = 0; i < N; ++i)
    {
        for (std::size_t j = 0; j < N; ++j)
        {
            c[i][j] = inf;
        }
        c[i][i] = 0;
    }

    for ([i, j] : /*edges*/)
        c[i][j] = /*edge length*/;
        
    for (std::size_t k = 0; k < N; ++k)
        for (std::size_t i = 0; i < N; ++i)
            for (std::size_t j = 0; j < N; ++j)
                c[i][j] = std::min( c[i][j], c[i][k] + c[k][j]);
   

Observation

• If i==k then the innermost loop body is equivalent to

          c[k][j] = std::min( c[k][j], c[k][k] + c[k][j]);
      

• Because c[k][k]>=0, c[k][j] is never changed by this code.
• Similarly, for j==k, c[i][k] is never changed.
• Consequently, in the k-th iteration of the outermost loop, the row c[k][_] and the column c[_][k] are not altered.
• As a result, there is no loop-carried dependence in the two innermost loops.

Hints

• Use vector instructions for min and +.
• Some memory overhead (< +100%) allowed
• You may align matrix dimensions to a multiply of 32/64 elements
• Expected number of columns >= 64
• Matrix size determined in advance (by constructor arguments)
• The class does not have to be complete wrt. C++ programming guidelines (copy/move-support may me missing etc.)
• Tune for square matrixes about 1024*1024 elements (this size will fit in 2 MB space and about 0.5 s time).
• Optimize data layout

The required interface

    template< typename policy>
    class matrix {
    public:
        using matrix_element = std::uint16_t;
        static constexpr matrix_element inf = 0x7FFF;
        matrix(size_t n);
        void clear();
        size_t size() const;
        void set(size_t i, size_t j, matrix_element e);
        matrix_element get(size_t i, size_t j) const;
        void floyd_warshall();
    private: // ...
    };
    

The constructor allocates space for a n*n matrix and calls clear(). clear() sets the diagonal elements to zeros and the rest to inf.

floyd_warshall() performs the main loop of the algorithm.

The measured part consists of calling clear(), repeatedly calling set(), and floyd_warshall(). The time printed by the program is the wall time for the measured part divided by n*n*n, in nanoseconds.

For relevant performance measurement at parlab, the program shall be run as:

            srun -p mpi-homo-short -n 1 -c 16 <build-folder>/fw --direct-print=no --threads=8
        

Test parameters

size - the size of the matrix - iterated through the set { 64, 128, 256, 512, 1024 }; { 64 } in Debug mode.

repeats is an auto-adjusted parameter, used to increase running time by invoking the measured part repeatedly. The range of the parameter is set so that the expected run time ranges from fractions of a second to seconds (stopped by the auto-adjustment mechanism after exceeding a second).