Matrix "multiplication"

• Deadline: 2024/04/18 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

The main goal is to implement matrix "multiplication"; however, the multiplication is done over the algebra (min,+), instead the usual (+,*). The element is a 16-bit unsigned integer.

Reference algorithm

    uint16_t a[L][N], b[N][M], c[L][M];
        
    for( i = 0; i < L; ++ i)
      for( j = 0; j < M; ++ j)
      {
        c[i][j] = 0xFFFF;
        for( k = 0; k < N; ++ k)
          c[i][j] = std::min( c[i][j], a[i][k] + b[k][j]);
      }
    

Notes

• Some memory overhead (< +100%) allowed
• You may align matrix dimensions to a multiply of 32/64/128/256 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 1000*1000 elements (this size will fit in 6 MB space (L2 cache) and about 0.5 s time).
• Optimize data layout
• Try SIMD

The required interface

    template< typename policy>
    class matrix {
    public:
        matrix(size_t m, size_t n);
        size_t vsize() const;
        size_t hsize() const;
        uint16_t get(size_t i, size_t j) const;
        void set(size_t i, size_t j, uint16_t e);
        void assign_mul(const matrix & a, const matrix & b);
    private: // ...
    };
    

assign_mul assigns to this object the result of the multiplication of a and b, according to the reference algorithm above.

Test parameters

size - the size of the three (square) matrices - 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 repeatedly calling assign_mul. 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).