10.10.2018 14:34
Nirec
 
Здравствуйте!!! Если кто разбирается opem mp, помогите пожалуйста, у меня задание такое: Распараллелить сортировку Шелла, но у меня как то корявенько оно работает
Код:
/*Параллельная сортировка Шелла*/
#include "stdafx.h" 
#include <iostream> 
#include <omp.h> 
#include <ctime>
#include <windows.h> 
using namespace std;
int main()
{
	setlocale(LC_ALL, "rus");
	int m;
	const int n = 199;
	int a[n];
	srand(time(NULL));
	cout << "\nИсходный массив: ";
	for (int i = 0; i < n; i++)
	{
		a[i] = rand()%n;
		//a[i] = n-i;
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	cout << endl;
	cout << "Этапы сортировки массива: \n";
	cout << "\n";
	//алгоритм сортировки Шелла
    int step = n / 2;//инициализируем шаг. 
    while (step > 0)//пока шаг не 0 
	{
	#pragma omp parallel for num_threads(2)  
	for (int i = 0; i < (n - step); i++)
	{
		int j = i;
		//будем идти начиная с i-го элемента 
		while (j >= 0 && a[j] > a[j + step]) 
		{
			Sleep(1);
			#pragma omp critical
			//пока не пришли к началу массива 
			//и пока рассматриваемый элемент больше 
			//чем элемент находящийся на расстоянии шага 
		{ 
					//меняем их местами 
					int temp = a[j];
					a[j] = a[j + step];
					a[j + step] = temp;
					m = omp_get_thread_num(); 
					cout << "Поток " << m << " меняет местами элементы с номерами " << j << " и " << j + step << "\n";
					j--;
				}
		}
  }
			step = step / 2;//уменьшаем шаг 
 }
	cout << "\nОтсортированный массив: ";
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	system("pause");
	return 0;
}
10.10.2018 17:53
Occul
 
Цитата:
Nirec #pragma omp parallel for num_threads(2)
Я не сталкивался с omp, могу ошибаться, но в данном случае, мне кажется, ты ссылаешься на потоки, при том, что их не создаешь? Может, использовать конструкцию вида
Код:
#pragma omp parallel for shared(n,step,a) private(i,j)
?
11.10.2018 00:00
Nirec
 
не помогает


(0,04Мб)
препод сказал, что такой алгоритм в принципе распараллелить вообще нельзя, нужна другая идея
11.10.2018 08:15
Occul
 
Непонятно, зачем он дает задание, которое выполнить нельзя и "нужна другая идея"? Сама сортировка Шелла в два потока вряд ли может идти... В любом случае транзакциями... Т.е. либо параллелить, либо Шелл.
11.10.2018 12:26
Nirec
 
Цитата:
void ShellSort(int n, int mass[])
{
int i, j, step;
int tmp;
for (step = n / 2; step > 0; step /= 2)
for (i = step; i < n; i++)
{
tmp = mass[i];
for (j = i; j >= step; j -= step)
{
if (tmp < mass[j - step])
mass[j] = mass[j - step];
else
break;
}
mass[j] = tmp;
}
}
если этот алгоритм распараллелить?
11.10.2018 16:07
OlegON
 
А как его параллелить, если при непрерывности массива его элементы должны сравниваться каждый между собой?

Форум на базе vBulletin®
Copyright © Jelsoft Enterprises Ltd.
В случае заимствования информации гипертекстовая индексируемая ссылка на Форум обязательна.