2

I'm building a distance matrix on which each row represent a point and each column is the distance between this point and all the other points in the data and my algorithm works very fine in the sequentially. However, when I try to parallelize it I get segmentation fault error.The following is my code for parallel where dat is a map that contain all my data. Any help here will be highly appreciated.

map< int,string >::iterator datIt; map< int,string >::iterator datIt2; map <int, map< int, double> > dist; int mycont=0; datIt=dat.begin(); int size=dat.size(); #pragma omp parallel //construct the distance matrix { #pragma omp for for(int i=0;i<size;i++) { datIt2=dat.find((*datIt).first); datIt2++; while(datIt2!=dat.end()) { double ecl=0; int c=count((*datIt).second.begin(),(*datIt).second.end(),delm)+1; string line1=(*datIt).second; string line2=(*datIt2).second; for (int i=0;i<c;i++) { double num1=atof(line1.substr(0,line1.find_first_of(delm)).c_str()); line1=line1.substr(line1.find_first_of(delm)+1).c_str(); double num2=atof(line2.substr(0,line2.find_first_of(delm)).c_str()); line2=line2.substr(line2.find_first_of(delm)+1).c_str(); ecl += (num1-num2)*(num1-num2); } ecl=sqrt(ecl); dist[(*datIt).first][(*datIt2).first]=ecl; dist[(*datIt2).first][(*datIt).first]=ecl; datIt2++; } datIt++; } }
Improve this question
2
  • 2
    With respect, if you're expecting us to debug that code, you could at least provide the stack trace at the point of the crash. Commented Jan 17, 2012 at 14:27
  • Please, at least indent your code before posting it. Commented Jan 17, 2012 at 14:27

2 Answers 2

Reset to default
3

I'm not sure if it is the only problem with your code, but standard containers (such as std::map) are not threadsafe, at least if you write to them. So if you have any write access to your maps, such as dist[(*datIt).first][(*datIt2).first]=ecl; you need to wrap any access to the maps in some sort of synchronization structure, either using #pragm omp critical or mutexes (omp mutex or, if you use boost or C++11 boost::mutex or std::mutex are options too): 

//before the parallel: omp_lock_t lock; omp_init_lock(&lock); ... omp_set_lock(&lock); dist[(*datIt).first][(*datIt2).first]=ecl; dist[(*datIt2).first][(*datIt).first]=ecl; omp_unset_lock(&lock); ... //after the parallel: omp_destroy_lock(&lock);

Since you only read from dat it should be fine without syncronization (in C++11 at least, C++03 has no guarantees about threadsafety whatsoever (since it has no concept of threads). It should typically be fine to use it without synchronization still, but technically its implementation dependent behaviour.

Furthermore since you didn't specify the data sharing all variables declared outside the parallel region are shared by default. Therefore your write access to datIt and datIt2 also present race conditions. For datIt2 this can be avoided by either specifying it as private, or even better declaring it at the point of first use:

map< int,string >::iterator datIt2=dat.find((*datIt).first);

Solving this for datIt is a bit more problematic, since it seems you want to iterate over the whole length of the map. The easiest way (which is not overly costly by using O(n) advance each iteration) seems to operate on a private copy of datIt, which is advanced accordingly (not guaranteeing 100% correctness, just a quick outline):

#pragma omp parallel //construct the distance matrix { map< int,string >::iterator datItLocal=datIt; int lastIdx = 0; for(int i=0;i<size;i++) { std::advance(datItLocal, i - lastIdx); lastIdx = i; //use datItLocal instead of datIt everytime you reference datIt in the parallel //remove ++datIt } }

This way the map is iterated omp_get_num_threads() times, but it should work. If that is an unacceptable overhead for you, look at this answer of mine for alternative solutions for looping on a bidirectional iterator in openmp.

As a sidenote: Maybe I missed something, but to me it seems that considering datIt is an iterator into dat, dat.find(datIt->first) is a bit redunant. There should be only one element in the map with the given key, and datIt points to it, so this seems like an expensive way of saying datIt2=datIt (correct me if I'm wrong).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

In addition to Girzzly's answer, you do not specify anything private or shared. This usually means you do not controll the access of your memory. You have to define datIt firstprivate and datIt2 private when you enter the parallel region otherwise everythread overwrites their shared value, which leads to segfaults.

Instead of using locks I would use a critical section, which is more openmpish.

Improve this answer

4 Comments

I general prefer locks to critical section, because I might want to add accesses to the shared datastructure at other points of the code, which can easily made to work with locks, but not so with critical sections, where you can't easily have different critical sections synchronize against each other (to my knowledge). However I would alsways wrap the lock code in a RAII class, which I didn't do in my sample for brevity. I hope you don't mind if I add the point about datIt to my answer
That's fine. I haven't used openmp in a OOC code extensively. I am not sure what you mean by synchronize against each other since, the code is executed one thread at a time. Additionally, before and after the critical section an implicit flush is called so everyone is up to date anyways.
I'm not 100% sure myself, but the way I see it I can't protect accesses to shared constructs with critical sections if I access it from different parts of the sourcecode, since while only one thread can be in a given critical section at the same time, there is no prohibition against threads beeing in different critical sections at the same time (I think, if there is it seems really wasteful). So critical sections protect a certain position in the code, instead of a certain datastructure. That doesn't really seem like a good idea to me.
also note that specifying datIt as fristprivate is not enough, since the loop won't iterate over the whole map in that case

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.