topic reformatting data using strides in Intel® Integrated Performance Primitives

reformatting data using strides

siddy — Tue, 31 Jan 2012 17:45:47 GMT

Hi,
Just wanted to clarify a methodological issue about data processing. I generally have prototypes im matlab, where I can change the sense of processing a data cube by reformatting the data: i.e for a [NxMxK] cube, it is easy to process either N MxK slices, or K NxM slices by re-permuting the dimensions, and iterating along the slowest varying index. Can this possibly be done by a smart choice of stride values in IPP? In other words, is it possible to enforce a specific data access pattern by a user defined stride (esp for a ippr malloc'ed data)?
Thanks,
Sid.

reformatting data using strides

Chao_Y_Intel — Wed, 01 Feb 2012 08:38:39 GMT

Sid,

Ippm domain (small matrix) has the parameters on the strides, which can used to select the data with some pattern.

But from the performance perspective, the consecutive data will provide the good performance, If the slowest index is varying, it is not friendly to achieve the performance. So for some image processing and some other function, it only provide the step parameter, which is the distance between consecutive lines. It supposes the data within one line is consecutive.

Thanks,
Chao

reformatting data using strides

siddy — Wed, 01 Feb 2012 16:59:58 GMT

Thanks Chao. I suspected that much.
Sid.

reformatting data using strides

igorastakhov — Wed, 01 Feb 2012 20:07:39 GMT

hi Sid,

what are N, M and K? if they are greater than 10 - you should not use IPP - in IPP small matrix domain is optimized for small sizes only 3x3 - 6x6, in some cases up to 10x10. For bigger sizes you should use MKL

Regards,
Igor

reformatting data using strides

siddy — Wed, 01 Feb 2012 21:36:24 GMT

N, M and K are the number of elements in each dimension (x- y- and z- ). Currently, I just
use M x K ippiMalloc'ed frame, iterated over 0 .. N-1 . Seems pretty fast for the processing
i do each frame.
I am still learing MKL call/usage syntax, and will probably shift to that for volume processing.
Sid.

Reformatting data using strides

SergeyKostrov — Thu, 02 Feb 2012 14:42:00 GMT

I think there is some confusion regarding yourterm "reformatting data". Maybe a processing with different
pattern, or something like this, would be better?

From my point of view, reformattingis a "special technique" that allows to change dimensions of a data
set, 2-D or 3-D, without reallocating an initial buffer for thedata set.

It means, ifthere isa data set with dimensions M x N (=T)it could be "reformatted" to a data set with
dimensions M/2 x N*2 (=T). It is a very important that an initial buffer is intact and M x N =T = M/2 x N*2 = T,
where T is a total number of elements in the data set.

Here is an example, if there is a 3 x 3matrix:

1 2 3
4 5 6
7 8 9

it could be "reformatted" to anarray ( 1 x 9 ):

1 2 3 4 5 6 7 8 9

or, to avector ( 9 x 1 ):

1
2
3
4
5
6
7
8
9

etc. I use that technique to "reformat" 2-D data sets and in my case it is called as "transform".

Best regards,
Sergey

Reformatting data using strides

siddy — Thu, 02 Feb 2012 18:33:37 GMT

Hi Sergey,
For want of a better term, I used "reformatting". In my example though, I would like to permute the dimensions, to MxNxK = KxMxN (=T), hence the constraints that you mentioned are satisfied. In fact, this is what I would like to do: Given M slices of NxK data, can I read them as K slices of MxN data? In neuroimaging for example, this would amount to acquiring data in axial orientation, and reading them in sagittal orientation, a transformation that is normally referred to as "reformatting" in this field at least.

So, In your examle above, do you reformat based on strides? would it work for a 3D arrangement?
Sid.

Reformatting data using strides

SergeyKostrov — Fri, 03 Feb 2012 04:35:50 GMT

Quoting siddy

...
So, In your examle above, do you reformat based on strides?

[SergeyK] No. It is a pure C/C++ template basedimplementation without IPP.

Would it work for a 3D arrangement?

[SergeyK] This is what I'd like to understand. You have a 3-D data set ( Volume ):

Volume = M x N x K

Is it a set ofM 2-D imageswith dimensions ofN x K?
or
Is it a set of M 2-D data sets ( not images / justnumbers) with dimensions of N x K?

Reformatting data using strides

siddy — Fri, 03 Feb 2012 20:06:11 GMT

M 2D images of size NxK .
Would I be at an advantage if it were a set on numbers MxNxK ?
Sid.

Reformatting data using strides

SergeyKostrov — Sat, 04 Feb 2012 01:54:54 GMT

Quoting siddy

M 2D images of size NxK .
Would I be at an advantage if it were a set on numbers MxNxK ?
Sid.

Hi Sid,

I tested my "transform" function and it doesn't work as expected in case of a3-D data set. It actually doesn't
matter if a 3-D data set is a set of 2-D images or 2-D sets of numbers. As soon asthe "transform" is applied
a data set becomes "invalid" in essense.

I'm going to look at it again some time later and here are three approaches I'm going to test for arranging
3-D data sets:

- A Structure of Arrays ( SOA )
or
- An Array of Structures ( AOS )
or
- A new version of my current "transform" function with strides

I remember that there is an article about SOA and AOS techniques on Intel's website. Please take a look.

Best regards,
Sergey

Reformatting data using strides

siddy — Tue, 07 Feb 2012 19:07:05 GMT

Hi Sergey,
Is you "transform" function something that I can have a look at? If it works like a "permute" function in matlab, this can be a good addition for the IPP suite. Just my thought, but I would be really interested in
having a look at it. In the meantime I am getting my head aroung AoS and SoA
Thanks,
Sid.

Reformatting data using strides - Source codes

SergeyKostrov — Thu, 09 Feb 2012 17:09:44 GMT

// Simple 2D Data Set class ( allows transforms )
//
// Notes:
// - This is a prototype I used for a template based 2Ddata set class ( it's avery different but idea is the same )
// - An underlying 1D array for a 2D array is a CONTIGUOUS
// - A Transform functionality assumes that the underlying 1D array is not reallocated
// - You could easily add methods like 'SetValue', 'Clear', 'LoadData', C++ operators, etc

class CDataSet2D
{
public:
CDataSet2D()
{
Init();
};

virtual ~CDataSet2D()
{
Free();
};

private:
void Init( void )
{
m_iRows = 0;
m_iCols = 0;

m_piData1D = NULL;
m_piData2D = NULL;
};

public:
int Allocate( int iRows, int iCols )
{
if( iRows <= 0 || iCols <= 0 )
return ( int )0;

m_iRows = iRows;
m_iCols = iCols;

m_piData1D = ( int * )malloc( ( m_iRows * m_iCols ) * sizeof( int ) );
if( m_piData1D == NULL )
return ( int )0;

memset( m_piData1D, 0x0, ( m_iRows * m_iCols ) * sizeof( int ) );

m_piData2D = ( int ** )malloc( m_iRows * sizeof( int * ) );
if( m_piData2D == NULL )
return ( int )0;

int *piData = m_piData1D;

for( int i = 0; i < m_iRows; i++ )
{
m_piData2D = piData;
piData += m_iCols;
}

return ( int )1;
};

void Free( void )
{
if( m_piData2D != NULL )
{
free( m_piData2D );
m_piData2D = NULL;
}

if( m_piData1D != NULL )
{
free( m_piData1D );
m_piData1D = NULL;
}
};

int Transform( int iRows, int iCols )
{
if( iRows <= 0 || iCols <= 0 )
return ( int )0;
if( m_iRows <= 0 || m_iCols <= 0 )
return ( int )0;

if( ( m_iRows * m_iCols ) != ( iRows * iCols ) )
return ( int )0;

if( m_piData1D == NULL )
return ( int )0;
if( m_piData2D == NULL )
return ( int )0;

m_iRows = iRows;
m_iCols = iCols;

if( m_piData2D != NULL )
{
free( m_piData2D );
m_piData2D = NULL;
}

m_piData2D = ( int ** )malloc( m_iRows * sizeof( int * ) );
if( m_piData2D == NULL )
return ( int )0;

int *piData = m_piData1D;

for( int i = 0; i < m_iRows; i++ )
{
m_piData2D = piData;
piData += m_iCols;
}

return ( int )1;
};

protected:
int m_iRows;
int m_iCols;

int *m_piData1D;
int **m_piData2D;
};

void main( void )
{
int iRetCode = -1;

CDataSet2D ds2D;

iRetCode = ds2D.Allocate( 5, 5 ); // Initialized as Matrix 5x5
iRetCode = ds2D.Transform( 1, 25 ); // Transformed to Array 1x25
iRetCode = ds2D.Transform( 25, 1 ); // Transformed to Vector 25x1
iRetCode = ds2D.Transform( 7, 7 ); // Attempt to Transform to Matrix 7x7 - Invalid input
}