Matrix Multiplication using Tiling Method

Execution Time for Matrix multiplication can be improved by using a tile method which is based on dividing the matrix/2D array into smaller sub matrices/Tiles and then multiplying each of the tile in manner as shown below:
The 2D arrays must be Square Matrices of same size in order of power of 2.



Implementation in C++:

for(int i_=0;i_<N;i_+=tile) {
for(int j_=0;j_<N;j_+=tile) {
for(int k_=0;k_<N;k_+=tile) {
    for(i=i_; i<i_+tile; ++i){
               for(j=j_; j<j_+tile; ++j){
                          for(k=k_; k<k_+tile; ++k){
                      P[j][i] += A[j][k]*B[k][i];
                  }
              }
      }
      }
      }
}

tile: Tile size could be 2, 4, 8, 16...

Comments

Post a Comment

Popular posts from this blog

How to install GEM5 Simulator in ubuntu

Image
Hello Friends Today I would list the steps and Instructions to install GEM5 Simulator on ubuntu. GEM5 Simulator is one of the popular simulator for simulating Computer-Architecture and Experimenting some research stuff. STEPS: 1.  First of all you will need to install some dependencies such as git,scons.... you can install all in one go by using the below command: sudo apt install build-essential git m4 scons zlib1g zlib1g-dev libprotobuf-dev protobuf-compiler libprotoc-dev libgoogle-perftools-dev python-dev python 2. After that you need to clone/download the officaial GEM5 repository: git clone https://gem5.googlesource.com/public/gem5 3. After that you can build GEM5 using the below command by going into the downloaded/cloned directory. scons build/X86/gem5.opt -j9 4.  You are ready to run and experment with GEM5, you can find the results in the m5out Directory. and whenever you make any change in the code you need ot build GEM5 again with...
Read more

Shell Scripting is Fun

Shell Scripting Coding Problem Problem: Write a shell script that accepts a name from the user and creates a directory by that name, then creates a text file in that directory and stores the data accepted from user (till the singlecharacter Q is given), and displays the number of characters stored in the file. Solution:  #start #!/bin/bash echo -n "Enter a name to create a directory with: " read d mkdir $d cd $d echo -n "Enter a name to create a text-file with: " read f if [ -f $f ] then   rm $f fi touch $f count=0 echo "Enter data for text-file $f" read -n 1 a while [ "$a" != "Q" ] do   echo -n  -e "$a" >> $f   count=$(( $count + 1 ))   read -n 1 a done echo echo -n "Number of characters in $f is: $count" #end
Read more