Click here to Skip to main content
Click here to Skip to main content

Matrix/Vector Multiplication Optimization

, 14 Sep 2005
Rate this:
Please Sign up or sign in to vote.
This article describes a way to make matrix vector multiplication faster.

Sample Image

Introduction

The purpose of this article is to show how to speed up some matrix operations. This improvement is obtained by using assembly language with SSE (Streaming SIMD Extension) technology.

Background

In this article, we are going to see how to improve the speed of the mathematical operation: Matrix Vector multiplication. I have chosen this operation because it is often used in programming (image processing, 2D, 3D etc.).

Since the Pentium III Processor, Intel encloses the SSE technology. This technology was included in order to improve image, video, audio processing. The SSE technology uses SIMD (Single Instruction Multiple Data) instructions. For example, this allows to perform four multiplications (on single precision float) with only one instruction. By using these characteristics, I tried to speed up the matrix/vector multiplication.

Requirement

In order to use the SSE instruction set, you need a computer with a Pentium III processor or newer. Next, Visual C++ can't compile the SSE instructions without the Processor Pack. (Instructions to install it in the Zip file.)

Using the code

The program provided by the link on the top performs a matrix/vector multiplication. It displays the time spent in the C++ function and the time spent in the assembly function. It also displays the matrix and the two vectors (multiplication and result).

You can find two ways to proceed this operation (one in C++ and another in assembler). The code shows you the time (in CPU clock cycles) spent in each function.

First in the C++ function, the code is optimized when you compile in Release mode. So the matching must be done in the Release mode.

Here is the main of the project:

//
// The main contain the call to the functions,
// declarations, and time measurement

int main(int argc, char* argv[])
{
    //Enter the size of the matrix

    int size;

    int i;

    printf("Enter the size of the matrix:\n");
    scanf("%d",&size);
    
    // Allocate memory
    float* matrix=(float*) malloc (size*size*sizeof(float));
    float* vector=(float*) malloc (size*sizeof(float));
    float* result=(float*) malloc (size*sizeof(float));
    float* matrix1=(float*) malloc (size*size*sizeof(float));
    for(i=0; i<size*size; i++)
        matrix1[i]=(float)i;

    // Writting values in the matrix and vector
    MatrixVectorWritting(matrix, vector, size);

     // Benchmark the two fonctions
     __int64 t1=GetTime();
     for(i=0; i<100; i++)
         result=MatrixVector_C(matrix,vector, size);
     __int64 t2=GetTime();
     __int64 time_C=t2-t1;
     printf("Time spend en C++ fonction: %d clock cycles.\n", 
                                                     time_C);

     __int64 t3=GetTime();
     for(i=0; i<100; i++)
         result=MatrixVector_SSE(matrix1, vector, size);
     __int64 t4=GetTime();
     __int64 time_SSE=t4-t3;
     printf("Time spend en Asm SSE fonction:" 
            " %d clock cycles.\n",time_SSE);       

     // Display the matrix and the two vectors
     MatrixVectorDisplay(matrix, vector, result, size);

     // Display the time improvement in percent

     TimeImprove(time_C,time_SSE);  
     return 0;
}

We can see in the main function that we make a "for" loop (100 times) on each function we compare. At the beginning of each loop we read the CPU clock. And at the end of each loop we read again the CPU timer clock. Then we take the difference between the two times read. And we obtain the number of clock cycles spent in each function (independent of the CPU used for the test).

Here is the code used to read the CPU timer called RDTSC:

/// Read the computer's timer RDTSC
__int64 GetTime()
{
    __int64 clock;
    __asm
    {
        rdtsc                        // Resad the RDTSC Timer
        mov    dword ptr[clock], eax // Store the value in EAX and EDX Registers
        mov    dword ptr[clock+4], edx
    }
    return clock;
}

Points of Interest

As you can see with the program, there are some matrix dimensions where the assembly function is not very efficient. This happens when the size of the matrix is lower than 3x3. For very low sizes of the matrix the code is not very optimized. But it's possible to make a specific function for the matrix/vector multiplication of 3x3 or 2x2 matrixes. You can find a white paper on the Intel web site.

History

Some sections of the code can be improved. So if I find anything else I'll update the code. If you have some ideas, you can propose.

Links

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

aurelien400

France France
No Biography provided

Comments and Discussions

 
GeneralAbout using SSE in managed C++ Pinmembermalei200328-May-06 22:09 
Generaltime measurement Pinmembermanoelaudaz11-May-06 7:28 
Generalnice article but... PinmemberSaurabh.Garg15-Sep-05 0:54 
Hi its a nice article but I think it would be better it you can describe code that do matrix multiplication rather then simple timing stuff.
 
It would be very nice to learn how to optimize code in assembly.
 
-Saurabh

QuestionWhat about BLAS? PinmemberNeWi14-Sep-05 12:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140814.1 | Last Updated 14 Sep 2005
Article Copyright 2005 by aurelien400
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid