5
\$\begingroup\$

The following is a c++ source code to get a matrix (std::vector<std::vector<T>>) transpose in parallel.

The span is \$\Theta(\lg^2(n))\$ while the work is \$\Theta(n^2)\$

Any suggestion to improve will be appreciated.

#include<vector>
#include<iostream>
#include<future>
#include<iomanip>
template <typename T>
void parallelForColsTrans(std::vector<std::vector<T>>& A, size_t fCol, size_t lCol, size_t i, size_t n)
{
    if (fCol == lCol)
    {
        T temp = A[i][fCol+n];
        A[i][fCol+n] = A[i+n][fCol];
        A[i+n][fCol] = temp;

        return;
    }

    std::async(parallelForColsTrans<T>, std::ref(A), fCol, (fCol + lCol) / 2, i, n);
    std::async(parallelForColsTrans<T>, std::ref(A), (fCol + lCol) / 2 + 1, lCol, i, n);

}


template <typename T>
void parallelForRowsTrans(std::vector<std::vector<T>>& A, size_t fRow, size_t lRow, size_t fCol, size_t lCol, size_t n)
{
    if (fRow == lRow) {
        parallelForColsTrans(A, fCol, lCol, fRow, n);
        return;
    }

    std::async(parallelForRowsTrans<T>, std::ref(A), fRow, (fRow+lRow) / 2, fCol, lCol, n);
    std::async(parallelForRowsTrans<T>, std::ref(A), (fRow + lRow) / 2 + 1, lRow, fCol, lCol, n);
}

template <typename T>
void pMatTransposeRecursive(std::vector<std::vector<T>>& A, size_t firstRow, size_t lastRow, size_t firstColumn, size_t lastColumn)
{
    if (firstRow == lastRow)    return;

    auto t1 =std::async(pMatTransposeRecursive<T>, std::ref(A), firstRow, (firstRow +lastRow)/2, firstColumn, (firstColumn+lastColumn)/2);
    auto t2 =std::async(pMatTransposeRecursive<T>, std::ref(A), (firstRow +lastRow)/2+1, lastRow, firstColumn, (firstColumn+lastColumn)/2);
    auto t3 =std::async(pMatTransposeRecursive<T>, std::ref(A), firstRow, (firstRow +lastRow)/2, (firstColumn+lastColumn)/2+1, lastColumn);
    pMatTransposeRecursive<T>(std::ref(A), (firstRow +lastRow)/2+1, lastRow, (firstColumn+lastColumn)/2+1, lastColumn);
    t1.get();
    t2.get();
    t3.get();
    size_t n = (lastColumn-firstColumn+1)/2;
    parallelForRowsTrans<T>(std::ref(A), firstRow, firstRow+n-1, firstColumn, firstColumn+n-1, n);

}

template <typename T>
void transpose(std::vector<std::vector<T>>& A){
    pMatTransposeRecursive( A, 0, A.size()-1, 0, A[0].size()-1);
}
int main(){

    std::vector<std::vector<int>> A = {{1,2,3,4,7,7,7,8}, {5,6,7,8,4,5,1,1}, {9,10,5,5,11,12,4,79}, {7,8,13,14,15,16,44,6}, {13,-14,7,-7,15,-16,-44,6}, {13,-14,105,106,404,6,9,9}, {13,-14,7,-7,15,-16,-44,6}, {13,-14,105,106,404,6,9,9}};
    transpose(A);
    for(auto & el:A){
        for(auto& ele:el) std::cout << ele << std::setw(4) ;
        std::cout << "\n";

    }
}
\$\endgroup\$
  • \$\begingroup\$ I think recursion is realy not required for calculating the transpose of a matrix. I don't think it's worth to use multithreading for that either. If you are just doing it for learning and want to keep the recursion and multithreading, please clarify that in the question. \$\endgroup\$ – akuzminykh Mar 23 at 6:45
  • \$\begingroup\$ @akuzminykh the multithreading saves the time doesn't it. \$\endgroup\$ – asmmo Mar 23 at 6:47
  • \$\begingroup\$ Calculating the transpose of a matrix is rather simple. So it can be calculated by a single thread pretty fast. Now you have to know that a thread has to be created before it can execute, which takes time. It could happen that your current code is actually slower because of the multithreading, just because of the overhead of creating additional threads. Recursion has a similar problem, but this is more dependent on the compiler. I'd like to write a whole answer in detail but I don't know C++ well .. \$\endgroup\$ – akuzminykh Mar 23 at 6:54
  • \$\begingroup\$ @akuzminykh this is a general code. It's not specified for this small matrix but for huge 2d vectors \$\endgroup\$ – asmmo Mar 23 at 6:57
  • 1
    \$\begingroup\$ If your only constraint is to save time, don't roll this yourself; use a BLAS library. \$\endgroup\$ – Reinderien Mar 24 at 13:24
5
\$\begingroup\$

Is it worth parallelising?

When you are parallelizing code you have to ask yourself if it's worth doing that. Parallel code doesn't magically give a speedup, because there are various things that can actually slow you down when using parallelism, for example:

  • Spawning and waiting for threads itself costs some time.
  • Threads might be fighting for resources, like locks, but even just memory access might cause contention.
  • Code that is not trivially parallelizable might require more computations when parallelized than when running single-threaded.

In the case of transposing matrices, there are almost no computations involved, the work is completely dominated by reading and writing to memory. A good single-threaded implementation, which reads sequentially as much as possible, will likely be able to saturate the memory bus on typical desktop machines.

In your implementation, you have a huge overhead just from starting all the async work items: you call async() more often than there are elements in the matrix. So that alone will make this horribly slow. Most good parallel algorithms try to limit the number of threads to the number of CPU cores or hardware threads that are available.

Even if you didn't parallelize, but kept the structure of the code the same (just not use async()), then the recursive divide-and-conquer approach will cause a non-sequential memory access pattern.

Code review

Nested std::vector<>s are not efficient containers for matrices

While it's convenient to declare a 2D matrix using std::vector<std::vector<T>>, it is not very efficient, since there is a lot of indirection. It is more efficient to declare a single std::vector<T> of size n * n, and index the vector using [row * n + col], or use a C++ library that provides proper matrix classes.

Use std::swap()

The standard library provides std::swap(), which swaps two variables for you.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ "A good single-threaded implementation, which reads sequentially as much as possible, will likely be able to saturate the memory bus." Only got to address this passage. It depends on the hardware. It is indeed true for typical computers - but it is not the case high peformance CPUs with tons of cores designed for work stations; e.g., Xeon or some AMD processors. They tend to have memory bus way wider than a single thread can populate. Aside from that - parallelizing transpose - definitely not worth parellezation regardless. \$\endgroup\$ – ALX23z Mar 24 at 22:34
  • \$\begingroup\$ Many normal desktop CPUs can't get full memory bandwidth from a single core either (for example a 4770K with 2400MHz memory gets about 35GB/s multi-threaded but 20GB/s single-threaded), but the problem is less bad than on server parts \$\endgroup\$ – harold Mar 25 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.