SAUCE
Home
Events
Listing
Future
Previous
Accelerated Computing with GPUs 2020
Data Mining - Winter 20/21
High Performance Computing 2019
Einführung in die Bioinformatik WS19/20
Computational Logic
Parallel Algorithms and Architectures 2019
DSEA Praktikum 2018/19
Deep Learning 2018
High Performance Computing 2018
Parallel Algorithms and Architectures 2018
Datenstrukturen und effiziente Algorithmen Ws 18/19
EiP SoSe 18
bio-st-18
EiP WS 2017/18
High Performance Computing 2017
Datenstrukturen und effiziente Algorithmen WiSe 17/18
PS SS 2017
Einfuehrung in die Programmierung SS17
Parallel Algorithms and Architectures 2017
High Performance Computing 2016
DSEA 2016/17
EiP WS2016/17
Parallel Algorithms and Architectures 2016
PS SS 2016
Krypto SS 2016
EiP SS 2016
DSEA Praktikum WS 2015/16
DSEA WS 2015/16
News
Documentation
About
Changelog
Roadmap
Deutsche Dokumentation
Tips and Tricks
Test configuration
Language information
Contact
Login
Parallel Algorithms and Architectures 2017
Sheet 7 (Sparse Matrices, Page Rank)
Pair Programming
Sheet 3 (Quaternion Normalization, Matrix Transposition)
Sheet 4 (Array Reversal, Determinants)
Sheet 5 (Prefix Scan, Knapsack)
Sheet 6 (Piecewise constant kernels, FFT-Convolution)
Sheet 7 (Sparse Matrices, Page Rank)
Sheet 8 (Streams, Multi-GPU)
Sheet 9 (Jacobi Iteration)
Task 1 (COO, CSR, ELL)
Task 1 (COO, CSR, ELL)
Task 2 (Markov Chain Equilibrium)
Task 1 (COO, CSR, ELL)
Assignment
Scaffold Head
#include <iostream> #include <algorithm> #include <vector> #include <random> #include <assert.h> using namespace std; template <class value_t> struct dense_matrix{ vector<value_t> data; // dense matrix entries size_t m; // number of rows size_t n; // number of cols }; template <class value_t> struct csr_matrix{ vector<value_t> data; // non-zero data vector vector<size_t> col_index; // col indices vector<size_t> row_ptr; // starting indices of each row size_t m; // number of rows size_t n; // number of cols }; template <class value_t> struct coo_matrix{ vector<value_t> data; // non-zero data vector vector<size_t> row; // row indices vector<size_t> col; // col indices size_t m; // number of rows size_t n; // number of cols }; template <class value_t> struct ell_matrix{ vector<value_t> data; // non-zero and padded data vector vector<size_t> index; // index array size_t num_max; // maximum non-zeros of all rows size_t m; // number of rows size_t n; // number of cols }; template <class value_t> void generate_sparse_matrix(dense_matrix<value_t>& dm, size_t m, size_t n, double eps=1e-1) { dm.m = m; dm.n = n; mt19937 engine(42); uniform_real_distribution<double> dist(0, 1); dm.data = vector<value_t>(m*n, 0); for (size_t i = 0; i < m; i++) for (size_t j = 0; j < n; j++) if (dist(engine) < eps) dm.data[i*n+j] = i*n+j; } template <class value_t> void print_matrix(const dense_matrix<value_t>& dm) { for (size_t i = 0; i < dm.m; i++) for (size_t j = 0; j < dm.n; j++) cout << dm.data[i*dm.n+j] << (j+1 == dm.n ? "\n" : "\t"); cout << endl; } template <class value_t> bool equals(const dense_matrix<value_t>& lhs, const dense_matrix<value_t>& rhs){ assert(lhs.m == rhs.m && lhs.n == rhs.n); for (size_t i = 0; i < lhs.m*lhs.n; i++) if (lhs.data[i] != rhs.data[i]) return false; return true; }
Scaffold Foot
template <class value_t> void coo2dense(const coo_matrix<value_t>& coo, dense_matrix<value_t>& dm) { assert(coo.data.size() == coo.row.size() && coo.row.size() == coo.col.size()); dm.m = coo.m; dm.n = coo.n; dm.data = vector<value_t>(coo.m*coo.n, 0); for (size_t i = 0; i < coo.data.size(); i++) dm.data[coo.row[i]*coo.n+coo.col[i]] = coo.data[i]; } template <class value_t> void csr2dense(const csr_matrix<value_t>& csr, dense_matrix<value_t>& dm) { assert(csr.data.size() == csr.col_index.size() && csr.row_ptr.size() == csr.m+1); dm.m = csr.m; dm.n = csr.n; dm.data = vector<value_t>(csr.m*csr.n, 0); size_t count = 0; for (size_t i = 0; i < csr.m; i++) { const size_t range = csr.row_ptr[i+1]-csr.row_ptr[i]; for (size_t j = 0; j < range; j++) { dm.data[i*csr.n+csr.col_index[count]] = csr.data[count]; count++; } } } template <class value_t> void ell2dense(const ell_matrix<value_t>& ell, dense_matrix<value_t>& dm) { assert(ell.data.size() == ell.index.size() && ell.data.size() == ell.m*ell.num_max); dm.m = ell.m; dm.n = ell.n; dm.data = vector<value_t>(ell.m*ell.n, 0); size_t count = 0; for (size_t i = 0; i < ell.num_max; i++) for (size_t j = 0; j < ell.m; j++) { dm.data[j*ell.n+ell.index[count]] += ell.data[count]; count++; } } int main() { size_t m = 1024, n = 2048; dense_matrix<size_t> dm, tmp; generate_sparse_matrix(dm, m, n); coo_matrix<size_t> coo; dense2coo(dm, coo); coo2dense(coo, tmp); cout << equals(dm, tmp) << endl; csr_matrix<size_t> csr; dense2csr(dm, csr); csr2dense(csr, tmp); cout << equals(dm, tmp) << endl; ell_matrix<size_t> ell; dense2ell(dm, ell); ell2dense(ell, tmp); cout << equals(dm, tmp) << endl; }
Start time:
Mo 24 Apr 2017 11:59:00
End time:
So 01 Okt 2017 00:00:00
General test timeout:
10.0 seconds
Tests
Comment prefix
#
Given input
Expected output
1 1 1