Floyd-Warshall Algorithm

machineauthorcommitcommit dateplatformtimechecksumcheckrel timebonus
mpi-homobaibatca4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.018614894170730723645475OK17.4884-99.4199
mpi-homobaibatca4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.20644894170730723645475OK20.53-104.991
mpi-homobalekdac62f3c1"2025-04-08 23:49:56 +0200"avx512all(64,1024,2)640.04853064894170730723645475OK0.8258766.64681
mpi-homobalekdac62f3c1"2025-04-08 23:49:56 +0200"avxall(64,1024,2)640.05873714894170730723645475OK1.00845-0.292401
mpi-homobellusm1ae21b4"2025-04-07 16:23:17 +0200"avx512all(64,1024,2)640.0486344894170730723645475OK0.8276366.57285
mpi-homobellusm1ae21b4"2025-04-07 16:23:17 +0200"avxall(64,1024,2)640.05996994894170730723645475OK1.02962-1.01406
mpi-homoberkal9e10ce7"2025-04-17 11:41:35 +0200"avxall(64,1024,2)640.04204954894170730723645475OK0.72194411.3197
mpi-homoberkal9e10ce7"2025-04-17 11:41:35 +0200"avx512all(64,1024,2)640.04399594894170730723645475OK0.74870510.0551
mpi-homobodat8f05c6b"2025-04-09 11:09:13 +0200"avx512all(64,1024,2)640.06070584894170730723645475OK1.03307-1.13035
mpi-homobodat8f05c6b"2025-04-09 11:09:13 +0200"avxall(64,1024,2)640.07149174894170730723645475OK1.22743-7.11988
mpi-homoborovskv4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.025424894170730723645475OK17.6054-99.6517
mpi-homoborovskv4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.23064894170730723645475OK20.9419-105.681
mpi-homobubakf4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.035414894170730723645475OK17.7768-99.9883
mpi-homobubakf4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.206344894170730723645475OK20.5291-104.99
mpi-homobuiquo896a96f"2025-04-24 21:45:19 +0200"avx512all(64,1024,2)640.05584074894170730723645475OK0.9502771.77199
mpi-homobuiquo896a96f"2025-04-24 21:45:19 +0200"avxall(64,1024,2)640.08090194894170730723645475OK1.389-11.4161
mpi-homocarvasj77ccc92"2025-03-18 20:40:58 +0100"avx512all(64,1024,2)640.04699214894170730723645475OK0.7996957.76606
mpi-homocarvasj77ccc92"2025-03-18 20:40:58 +0100"avxall(64,1024,2)640.06413354894170730723645475OK1.1011-3.3462
mpi-homocelovskje74d108"2025-04-17 18:06:39 +0200"avxall(64,1024,2)640.06997264894170730723645475OK1.20135-6.37365
mpi-homocelovskje74d108"2025-04-17 18:06:39 +0200"avx512all(64,1024,2)640.07338154894170730723645475OK1.24878-7.71888
mpi-homocernohj3ceb11cb"2025-04-17 03:28:11 +0200"avx512all(64,1024,2)640.04153264894170730723645475OK0.70678612.057
mpi-homocernohj3ceb11cb"2025-04-17 03:28:11 +0200"avxall(64,1024,2)640.05579624894170730723645475OK0.957961.4922
mpi-homocimermmic15b97e"2025-04-14 20:18:49 +0200"avx512all(64,1024,2)640.05249064894170730723645475OK0.8932663.92152
mpi-homocimermmic15b97e"2025-04-14 20:18:49 +0200"avxall(64,1024,2)640.0574864894170730723645475OK0.9869710.455647
mpi-homodoskocj14dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.012594894170730723645475OK17.385-99.214
mpi-homodoskocj14dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.210774894170730723645475OK20.6045-105.117
mpi-homodvoraj484dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.012364894170730723645475OK17.3811-99.2062
mpi-homodvoraj484dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.206294894170730723645475OK20.5281-104.988
mpi-homofarkasau615e41d"2025-04-14 11:19:51 +0200"avx512all(64,1024,2)640.03777524894170730723645475OK0.64284515.3515
mpi-homofarkasau615e41d"2025-04-14 11:19:51 +0200"avxall(64,1024,2)640.03923744894170730723645475OK0.67366313.7246
mpi-homofarkasm24dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.126574894170730723645475OK19.3419-102.92
mpi-homofarkasm24dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.223184894170730723645475OK20.8156-105.471
mpi-homogutvaldv9adc5bf"2025-04-17 14:13:44 +0200"avx512all(64,1024,2)640.06492734894170730723645475OK1.10491-3.46614
mpi-homogutvaldv9adc5bf"2025-04-17 14:13:44 +0200"avxall(64,1024,2)640.08233854894170730723645475OK1.41366-12.0277
mpi-homohrdinap1439c5ad"2025-04-25 10:43:14 +0200"avx512all(64,1024,2)640.04272374894170730723645475OK0.72705611.0746
mpi-homohrdinap1439c5ad"2025-04-25 10:43:14 +0200"avxall(64,1024,2)640.05654554894170730723645475OK0.9708251.02873
mpi-homohrubyja26f5aa4c"2025-04-17 16:08:37 +0200"avx512all(64,1024,2)640.06389424894170730723645475OK1.08733-2.90883
mpi-homohrubyja26f5aa4c"2025-04-17 16:08:37 +0200"avxall(64,1024,2)640.0887194894170730723645475OK1.52321-14.6207
mpi-homojevcakj4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.03814894170730723645475OK17.823-100.078
mpi-homojevcakj4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.206744894170730723645475OK20.5358-105.001
mpi-homokapylouma4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.078424894170730723645475OK18.5153-101.402
mpi-homokapylouma4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.208384894170730723645475OK20.5637-105.048
mpi-homokoliandlde8133c"2025-04-12 13:25:14 +0200"avxall(64,1024,2)640.0291234894170730723645475OK0.5000124.0817
mpi-homokoliandlde8133c"2025-04-12 13:25:14 +0200"avx512all(64,1024,2)640.02955564894170730723645475OK0.50296723.8768
mpi-homokolnika4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.012824894170730723645475OK17.389-99.2219
mpi-homokolnika4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.236084894170730723645475OK21.0351-105.836
mpi-homokouckyj1eae3959"2025-04-05 11:49:50 +0200"avx512all(64,1024,2)640.05079934894170730723645475OK0.8644845.05944
mpi-homokouckyj1eae3959"2025-04-05 11:49:50 +0200"avxall(64,1024,2)640.05491674894170730723645475OK0.9428592.04426
mpi-homokraldav1084632d"2025-04-16 17:17:23 +0200"avx512all(64,1024,2)640.0505414894170730723645475OK0.8600895.23653
mpi-homokraldav1084632d"2025-04-16 17:17:23 +0200"avxall(64,1024,2)640.06042464894170730723645475OK1.03742-1.27651
mpi-homokrenmar4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.01954894170730723645475OK17.5037-99.4504
mpi-homokrenmar4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.20824894170730723645475OK20.5607-105.043
mpi-homokroupad14dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.084164894170730723645475OK18.6138-101.587
mpi-homokroupad14dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.204484894170730723645475OK20.4974-104.936
mpi-homolagood45ffd7"2025-04-12 22:37:42 +0200"avx512all(64,1024,2)640.05156544894170730723645475OK0.877524.53942
mpi-homolagood45ffd7"2025-04-12 22:37:42 +0200"avxall(64,1024,2)640.06030174894170730723645475OK1.03532-1.2058
mpi-homolejkom4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.040124894170730723645475OK17.8578-100.146
mpi-homolejkom4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.209744894170730723645475OK20.5868-105.087
mpi-homolopatad4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.016024894170730723645475OK17.444-99.3316
mpi-homolopatad4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.237874894170730723645475OK21.0655-105.886
mpi-homolovisekd4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.127654894170730723645475OK19.3605-102.953
mpi-homolovisekd4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.230644894170730723645475OK20.9425-105.682
mpi-homomaliarm4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.045724894170730723645475OK17.9539-100.333
mpi-homomaliarm4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.218454894170730723645475OK20.7351-105.337
mpi-homomojikm4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.128084894170730723645475OK19.3679-102.967
mpi-homomojikm4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.204954894170730723645475OK20.5054-104.95
mpi-homopajonkf4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.068634894170730723645475OK18.3472-101.086
mpi-homopajonkf4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.206234894170730723645475OK20.5272-104.986
mpi-homopelikam3c596ef4"2025-04-17 23:47:40 +0200"avx512all(64,1024,2)640.02815584894170730723645475OK0.47914425.5627
mpi-homopelikam3c596ef4"2025-04-17 23:47:40 +0200"avxall(64,1024,2)640.3853354894170730723645475OK6.61578-65.6465
mpi-homopernicke34e962"2025-04-22 15:31:05 +0200"avx512all(64,1024,2)640.05170984894170730723645475OK0.8799794.44223
mpi-homopernicke34e962"2025-04-22 15:31:05 +0200"avxall(64,1024,2)640.06687514894170730723645475OK1.14817-4.80057
mpi-homopetrunyoa8f78aa"2025-04-13 15:40:34 +0200"avx512all(64,1024,2)640.05213514894170730723645475OK0.8872164.15765
mpi-homopetrunyoa8f78aa"2025-04-13 15:40:34 +0200"avxall(64,1024,2)641.013234894170730723645475OK17.3961-99.2361
mpi-homopohljin949243e"2025-04-22 00:09:43 +0200"avx512all(64,1024,2)640.04715174894170730723645475OK0.8024117.64826
mpi-homopohljin949243e"2025-04-22 00:09:43 +0200"avxall(64,1024,2)640.07785084894170730723645475OK1.33661-10.0805
mpi-homorehorcc705343"2025-04-24 12:30:57 +0200"avx512all(64,1024,2)640.05164764894170730723645475OK0.878924.48405
mpi-homorehorcc705343"2025-04-24 12:30:57 +0200"avxall(64,1024,2)640.06776534894170730723645475OK1.16346-5.26001
mpi-homosevcikm8fc123f1"2025-04-11 19:37:24 +0200"avxall(64,1024,2)640.09035154894170730723645475OK1.55124-15.2542
mpi-homosezemskj4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.021124894170730723645475OK17.5315-99.5055
mpi-homosezemskj4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.223124894170730723645475OK20.8146-105.469
mpi-homosindelm6e22612e"2025-04-17 17:14:22 +0200"avx512all(64,1024,2)640.05659794894170730723645475OK0.9631631.30402
mpi-homosindelm6e22612e"2025-04-17 17:14:22 +0200"avxall(64,1024,2)640.06784044894170730723645475OK1.16475-5.29849
mpi-homosmykj3ff2224"2025-04-14 16:38:37 +0200"avxall(64,1024,2)640.05588414894170730723645475OK0.9594691.43752
mpi-homosmykj3ff2224"2025-04-14 16:38:37 +0200"avx512all(64,1024,2)641.206834894170730723645475OK20.5374-105.004
mpi-homostrecans4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.137894894170730723645475OK19.5363-103.267
mpi-homostrecans4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.234464894170730723645475OK21.0076-105.79
mpi-homosykorjos4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.082654894170730723645475OK18.5879-101.538
mpi-homosykorjos4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.208374894170730723645475OK20.5636-105.048
mpi-homotomiskat36b5493"2025-04-25 21:50:21 +0200"avxall(64,1024,2)641.07574894170730723645475OK18.4686-101.315
mpi-homotomiskat36b5493"2025-04-25 21:50:21 +0200"avx512all(64,1024,2)641.212484894170730723645475OK20.6336-105.166
mpi-homotomisz4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.103084894170730723645475OK18.9387-102.188
mpi-homotomisz4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.210714894170730723645475OK20.6034-105.115
mpi-homotothmatu5a47ecf"2025-04-07 20:06:00 +0200"avx512all(64,1024,2)640.05357554894170730723645475OK0.9117293.21074
mpi-homotothmatu5a47ecf"2025-04-07 20:06:00 +0200"avxall(64,1024,2)640.05532354894170730723645475OK0.9498441.78781
mpi-homotvrdekpb070818"2025-04-18 19:09:43 +0200"avx512all(64,1024,2)640.0733374894170730723645475OK1.24802-7.6978
mpi-homotvrdekpb070818"2025-04-18 19:09:43 +0200"avxall(64,1024,2)640.1097244894170730723645475OK1.88384-22.0035
mpi-homovaganove8e43f36"2025-04-16 11:12:26 +0200"avx512all(64,1024,2)640.04949784894170730723645475OK0.8423365.96119
mpi-homovaganove8e43f36"2025-04-16 11:12:26 +0200"avxall(64,1024,2)640.05022214894170730723645475OK0.8622595.149
mpi-homovermesad44b0e9"2025-04-15 00:54:34 +0200"avx512all(64,1024,2)640.05021544894170730723645475OK0.8545485.4611
mpi-homovermesad44b0e9"2025-04-15 00:54:34 +0200"avxall(64,1024,2)640.05606984894170730723645475OK0.9626571.32228
mpi-homovilimev71c9afa"2025-04-15 23:27:21 +0200"avxall(64,1024,2)640.08650034894170730723645475OK1.48512-13.7408
mpi-homovireakt4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.046254894170730723645475OK17.963-100.35
mpi-homovireakt4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.206054894170730723645475OK20.5242-104.981
mpi-homovomelolu4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.018324894170730723645475OK17.4835-99.4102
mpi-homovomelolu4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.21034894170730723645475OK20.5965-105.103
mpi-homozavodsv4dedfdb"2025-02-25 19:57:30 +0100"avxall(64,1024,2)641.040724894170730723645475OK17.8679-100.166
mpi-homozavodsv4dedfdb"2025-02-25 19:57:30 +0100"avx512all(64,1024,2)641.232644894170730723645475OK20.9766-105.739
mpi-homozellervbb34430"2025-04-15 17:59:08 +0200"avxall(64,1024,2)640.09930514894170730723645475OK1.70496-18.5372
mpi-homozellervbb34430"2025-04-15 17:59:08 +0200"avx512all(64,1024,2)640.105434894170730723645475OK1.79417-20.309

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

Hints

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).