OpenMP параллельная производительность - PullRequest
Новая
       20

OpenMP параллельная производительность

1 голос
/ 27 января 2012

Я пытаюсь реализовать матрицу расстояний параллельно, используя openmp, в котором я вычисляю расстояние между каждой точкой и всеми остальными точками, поэтому лучший алгоритм, который я до сих пор придумывал, стоит O (n ^ 2) и производительность мой алгоритм, использующий openmp с использованием 10 потоков на 8-процессорной машине, не лучше последовательного подхода с точки зрения времени выполнения, поэтому мне интересно, есть ли какая-либо ошибка в моей реализации на подходе openmp, так как я впервые использую openmp, поэтому, пожалуйста, если в моем заявлении есть какая-либо ошибка или какой-либо более быстрый подход, пожалуйста, дайте мне знать. Ниже приведен мой код, где «dat» - это вектор, содержащий точки данных. 

map <int, map< int, double> > dist;   //construct the distance matrix 

int c=count(dat.at(0).begin(),dat.at(0).end(),delm)+1;

#pragma omp parallel for shared (c,dist)

for(int p=0;p<dat.size();p++)
{

    for(int j=p+1;j<dat.size();j++)
    {
        double ecl=0;

        string line1=dat.at(p);
        string line2=dat.at(j);

        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);

#pragma omp critical
        {
            dist[p][j]=ecl;
            dist[j][p]=ecl;
        }
    }
}

Ответы [ 2 ]

2 голосов
/ 08 февраля 2012

Как уже указывалось, использование критических разделов замедлит работу, поскольку в этом разделе одновременно разрешен только 1 поток. Абсолютно нет необходимости использовать критические разделы, поскольку каждый поток записывает во взаимоисключающие разделы данных, при этом чтение неизмененных данных, очевидно, не нуждается в защите.

Мое подозрение относительно медлительности кода сводится к неравномерному распределению работы по потокам. По умолчанию я думаю, что openmp делит итерации поровну между потоками. В качестве примера рассмотрим, когда у вас есть 8 потоков и 8 баллов:

- нить 0 получит 7 расчетов расстояния

-притаска 1 получит 6 расчетов расстояния

...

-приточка 7 получит 0 вычислений расстояния

Даже при большем количестве итераций подобное неравенство все еще существует. Если вам нужно убедить себя, создайте частный счетчик потока, чтобы отслеживать, сколько вычислений фактически выполняется каждым потоком.

С такими конструкциями разделения работы, как параллель, вы можете указать различные стратегии распределения работы. В вашем случае, вероятно, лучше пойти с 

#pragma omp for schedule(guided)

Когда каждый поток запрашивает несколько итераций цикла for, он получает количество оставшихся циклов (еще не переданных потоку), деленное на количество потоков. Итак, изначально вы получаете большие блоки, позже вы получаете меньшие блоки. Это форма автоматического распределения нагрузки, учтите, что есть некоторые (возможно, небольшие) издержки при динамическом распределении итераций между потоками.

Чтобы не допустить, чтобы первый поток получил неоправданно большой объем работы, ваша структура циклов должна быть изменена таким образом, чтобы на более низких итерациях было меньше вычислений, например измените внутренний цикл for на 

for (j=0; j<p-1; j++)

Еще одна вещь, которую следует учитывать, - при работе с большим количеством ядер память может стать узким местом. У вас есть 8 процессоров, борющихся за, вероятно, 2 или 3 канала DRAM (отдельные карты памяти на одном и том же канале все еще конкурируют за пропускную способность). Кэш-память ЦП на кристалле в лучшем случае распределяется между всеми процессорами, поэтому кэш-память у вас по-прежнему не больше, чем серийная версия этой программы.

2 голосов
/ 28 января 2012

#pragma omp critical имеет эффект сериализации вашего цикла, поэтому избавление от него должно стать вашей первой целью. Это должен быть шаг в правильном направлении: 

ptrdiff_t const c = count(dat[0].begin(), dat[0].end(), delm) + 1;
vector<vector<double> > dist(dat.size(), vector<double>(dat.size()));

#pragma omp parallel for
for (size_t p = 0; p != dat.size(); ++p)
{
  for (size_t j = p + 1; j != dat.size(); ++j)
  {
    double ecl = 0.0;
    string line1 = dat[p];
    string line2 = dat[j];
    for (ptrdiff_t i = 0; i != c; ++i)
    {
      double const num1 = atof(line1.substr(0, line1.find_first_of(delm)).c_str());
      double const num2 = atof(line2.substr(0, line2.find_first_of(delm)).c_str());

      line1 = line1.substr(line1.find_first_of(delm) + 1);
      line2 = line2.substr(line2.find_first_of(delm) + 1);
      ecl += (num1 - num2) * (num1 - num2);
    }

    ecl = sqrt(ecl);
    dist[p][j] = ecl;
    dist[j][p] = ecl;
  }
}

Есть несколько других очевидных вещей, которые можно сделать, чтобы сделать это быстрее в целом, но исправление параллелизации - самая важная вещь.

...