fw.h 2.92 KB
Newer Older
Ernst Naschenweng's avatar
Ernst Naschenweng committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
/*
 * Author: Ernst Naschenweng
 * Bachelor's Thesis in Scientific Computing
 * University of Vienna
 */

#ifndef BACHELOR_THESIS_FW_H
#define BACHELOR_THESIS_FW_H

#include <chrono>

// starts timer on object creation, stops it and returns time with end()
struct Timer {
private:
    std::string message;
    std::chrono::time_point<std::chrono::system_clock> start;

public:
    explicit Timer(std::string message);
    std::string end();
};

// contains distance matrix and Floyd-Warshall methods as well as reference implementation in Boost
// read from and write to distance matrix with at(x, y)
// result of shortest paths overwrites the original distance matrix
// "FUR" refers to the Hilbert curve, "ZUR" to the Z-curve
struct Matrix {
private:
    int size_;
    double* data_;

public:
    explicit Matrix(int size);
    ~Matrix();

    inline double& at(int x, int y);    // read and write to x/y coordinate in matrix
    void copyData(double boost[]);
    bool verifyAgainstBoost(const double data[]);
    void generateData(double minWeight, double maxWeight, unsigned short density, unsigned int seed);
    bool isReachable(int x, int y);

    std::string simple_FW();
    std::string simple_FW_FUR();    // hilbert
    std::string simple_FW_ZUR();    // z-curve
    std::string simple_FW_AVX(bool avx512); // if false, regular AVX is used (256 bit)

    std::string boost_FW();

    // based on research by Venkataraman et al. (source: https://www.cise.ufl.edu/~sahni/papers/shortc.pdf)
    std::string blocked_FW(int blockFactor);
    void blocked_FW_phase1(int blocksize, int currentBlock);
    void blocked_FW_phase2_horizontal(int blocksize, int currentBlock, int pivotBlock);
    void blocked_FW_phase2_vertical(int blocksize, int currentBlock, int pivotBlock);
    void blocked_FW_phase3(int blocksize, int currentCol, int currentRow, int pivotBlock);

    std::string blocked_FW_FUR(int blockFactor);
    void blocked_FW_FUR_phase1(int blocksize, int currentBlock, int i_[], int j_[]);
    void blocked_FW_FUR_phase2_horizontal(int blocksize, int currentBlock, int pivotBlock, int i_[], int j_[]);
    void blocked_FW_FUR_phase2_vertical(int blocksize, int currentBlock, int pivotBlock, int i_[], int j_[]);
    void blocked_FW_FUR_phase3(int blocksize, int currentCol, int currentRow, int pivotBlock, int i_[], int j_[]);

    std::string blocked_FW_ZUR(int blockFactor);

    std::string blocked_FW_AVX(int blockFactor, bool use_avx512);
    void blocked_FW_AVX_phase1(int blocksize, int currentBlock, bool use_avx512);
    void blocked_FW_AVX_phase2_horizontal(int blocksize, int currentBlock, int pivotBlock, bool use_avx512);
    void blocked_FW_AVX_phase2_vertical(int blocksize, int currentBlock, int pivotBlock, bool use_avx512);
    void blocked_FW_AVX_phase3(int blocksize, int currentCol, int currentRow, int pivotBlock, bool use_avx512);

    std::string blocked_FW_AVX_OMP(int blockFactor, int threads, bool use_avx512);
};

#endif //BACHELOR_THESIS_FW_H