 # Data dependency

Hi,

I was wondering whether there is an academic/algorithm/whatever solution to the problem of data

dependency between threads. What i mean is whether there is some sort of way to convert, for example,

``````for ( int i = 0; i < 1000; i++ )

res[ i ] = res[ i - 1 ] + res[ i - 2 ];
``````

thanks

eyal

Hello, why just not fill the line with Fibonacci numbers ;-)

Hi,

This is just a sample, not the real code. The real code is a loop where each iteration depends on the previous result.

I was wondering whether it can be parallized.

thanks

eyal

I believe it can. If it is some kind of matematical iterative formula, there are (usually) ways to convert it into a standalone formula that would not depend on the previous result.
Otherwise, maybe some scans algorithm?

To tell you more I think we need to see your exact problem.

Hi,

I’ve posted it in the past and made some progress however I’m still not happy with the results, and therefore I decided to ask a more general question to see if there

is indeed some sort of a parallel algorithm to do such thing.

Anyway here is the code and some insights:

1. The above loop/code cant be parallelized either as the results need to be checked serially.

2. iTimePlusCeeWindow - iTimeMinusCeeWindow can be assumed (at the moment) to be between 0…40

3. iTimeEnd - iTimeBegin can be 1…4000

``````int ceeWindow  = ( int ) m_multifocParamSelectionWindow;

for( int iTime = iTimeBegin; iTime < iTimeEnd; iTime++ )

{

int		 iTimePlusCeeWindow  = __min( iTime + ceeWindow, iTimeEnd-1 );

int		 iTimeMinusCeeWindow = __max( iTime - ceeWindow, 0 );

bool  is_best					   = true;

double	  dCurrentCor			 = pCorTemp[ iTime ];

for ( int iSliceTime = iTimeMinusCeeWindow; iSliceTime <= iTimePlusCeeWindow; iSliceTime++ )

{

if ( m_ppCor_Temp_cre_angle_best[ i_rCre ][ iSliceTime ] > dCurrentCor )

{

is_best = false;

break;

}

}

if ( is_best )

{

for ( int iSliceTime = iTimeMinusCeeWindow; iSliceTime < iTimePlusCeeWindow; iSliceTime++ )

{

m_ppCor_Temp_cre_angle_best[ i_rCre ][ iSliceTime ]			   = pCorTemp[ iSliceTime ];

m_ppStack_Temp_cre_angle_best[ i_rCre ][ iSliceTime ]	   = pStack_Temp_cre_angle[ iSliceTime ];

}

}

}
``````

thanks

eyal