OpenMP tasks in a triple nested linked list

Vote count:

0

I'm new to OpenMP and I'm trying (without success so far) to implement a parallel version of a piece of code (written here in pseudo-code, as the specific language of implementation doesn't mater that much) that goes through a triple nested linked list.

I can't put the original code here because it's several thousand lines long.

The triple nested linked list has the following aspect:

• LIST A: composed of NA nodes of type A. Each type A is the pointer to the first element of a list with type B nodes.


• LIST B: composed of NB nodes of type B. Each type B is the pointer to the first element of a list with type C nodes, and it also stores information (lets call it xB) about a 3D position of each of the NB objects B.


• LIST C: composed of NC nodes of type C and it stores information (lets call it xC) about a 3D position of each of the NC objects C .

Now, here is what I want to parallelize using OpenMP:

ptr_A => head_A
DO WHILE(prt_A != NULL)
     ptr_B => head_B
     DO WHILE(prt_B != NULL)
          ptr_C => head_C
          DO WHILE(prt_C != NULL)
               dr = xB - xC ! Distance from object B to object C
               IF(dr < some value) *do stuff*
          ENDDO
     ENDDO
ENDDO

One easy way (using tasks) of parallelizing a linked list in OpenMP is the following (writne in C):

my_pointer = listhead;!
!
   #pragma omp parallel!
   {!
      #pragma omp single nowait!
      {!
         while(my_pointer) {!
           #pragma omp task firstprivate(my_pointer)!
           {!
             (void) do_independent_work (my_pointer);!
           }!
           my_pointer = my_pointer->next ;!
         }!
      } // End of single - no implied barrier (nowait)!
   } // End of parallel region - implied barrier! 

However, how does one proceed to the parallelization of the more complicated triple nested list?

1. Where does the parallel region stars (inner or outer lists)?


2. I need to use information from 2 different lists (list B and C). Does this causes problems?


3. What additional steps one has to take (when comparing with the simpler linked list example above) to make this work?

I've searched about this subject, but all examples I've seen are about a single list, not list of lists.

asked 42 secs ago

André Almeida

27

OpenMP tasks in a triple nested linked list