Как распараллелить алгоритм Гаусса через библиотеку thread?

@SalavatGood · Регистрация: 18.12.2018

Студворк — интернет-сервис помощи студентам

Всем привет. Для зачета дали задачу распараллелить на потоки алгоритм Гаусса, но только без MPI. Сам более менее пользовался уже библиотекой thread, однако куда не зайду везде параллелят Гаусса только по MPI, а подробной информации по алгоритму Гаусса по другой библиотеки нет. Хотелось бы у вас узнать, как можно решить данную задачу, может кто-либо уже сталкивался с подобным? Хотя мне уже два человека говорили что алгоритм Гаусса параллелить невозможно

@Annemesski · 29.02.2020, 04:31

Гаусс нашел весьма наглядный метод решения СЛАУ, но таки да, параллелить его - слабо представимо, разве что прямой проход можно распараллелить по строкам, но выглядит это, по крайней мере в первом приближении, чудовищно...
1. Создать потоки в количестве n - 1, где n количество уравнений системы
2. каждому потоку выделить по строке основной матрицы начиная со второй и передать первую строку и множитель
3. параллельно выполнить в потоках вычитание произведения переданной строки и множителя из строки соответствующей потоку
4. убить поток для самой верхней строки (из тех что еще живут в потоках), саму строку и соответствующий ей множитель передать оставшимся живым потокам.
5. повторять пп. 3 и 4 пока не умрут все потоки.

Ну а далее - обратный ход и тут уж как не крути мы не можем решать (если, конечно, система имеет решения) уравнение k - 1 пока не решим уравнение k - зависимость по данным. Как-то так.

@XLAT · 29.02.2020, 19:22

Сообщение от Annemesski

убить поток

интересно, как это сделать в <thread>?
можно общий пример некасаемый задачи?

C++
1
2
3
4
5
6
7
8
9
int main()
{
     std::thread thr(threadFunction);
     thr.detach();
 
/// здесь мне надо thr убить. КАК?
 
     return 0;
}

@Annemesski · 29.02.2020, 22:49

интересно, как это сделать в <thread>?

Тут общего идеального решения нет, но вариантов масса, Ваш thr завершиться сам по завершению threadFunction само собой его придется подождать в майне или придется заставить threadFunction реагировать на: глобальную переменную, флаг в общедоступной памяти, количество итераций известное до запуска потока и т.д. ну и да, по хорошему подождать в майне пока он завершиться.

Если Вы намекаете на то что ТСу придется дирижировать потоками, а это MPI, так это горе не беда, множители считаются заранее для всех строк, потоку передается счетчик итераций соответствующий номеру строки, main ждет завершение потоков по очереди, а потоки имеют задержку перед выполнением итерации гарантирующую что они не будут мешать друг другу читать освободившуюся строку. Тут я возможно что-то еще не учел и понимаю что это все в принципе довольно уродливо, но как говориться: "каков привет", раз такое задание придется крутиться.

@XLAT · 29.02.2020, 23:28

Сообщение от Annemesski

Если Вы намекаете

неа, нету намёков,
в бусте можно завершить отстёгнутый поток, а в в std::thread по ходу нет.

@Annemesski · 01.03.2020, 00:04

Сообщение от XLAT

в бусте можно завершить отстёгнутый поток, а в в std::thread по ходу нет.

Так и есть, чтобы рулить stl-овскими тредами придется что-то самому придумывать либо с шармэмори, либо с умными указателями, либо... варианты на выбор.

@SalavatGood · 01.03.2020, 00:44 **[ТС]**

Сообщение от Annemesski

1. Создать потоки в количестве n - 1, где n количество уравнений системы

У меня 8-мипоточный процессор, у меня программа только до 9 уравнений будет?

@S_el · 01.03.2020, 01:00

Сообщение от SalavatGood

Хотя мне уже два человека говорили что алгоритм Гаусса параллелить невозможно

Ради интереса, эти 2 человека реальны?
Linear Algebra: Gaussian Elimination

@Annemesski · 01.03.2020, 01:05

Сообщение от SalavatGood

У меня 8-мипоточный процессор, у меня программа только до 9 уравнений будет?

Нет, вы же не на ParallelC или фортране пишете, в С++ понятие параллелизма несколько условное, то есть, на самом деле, инструкции в потоках будут как бы вперемешку выполняться, что внешне выглядит как параллельное выполнение, реальное распараллеливание по ядрам будет выполняться на уровне ОС.

@S_el · 01.03.2020, 01:08

Сообщение от XLAT

в бусте можно завершить отстёгнутый поток, а в в std::thread по ходу нет.

Поэтому в стандарт был добавлен std::jthread. Пока можно юзать библиотеку на основе которой они появились - https://github.com/josuttis/jthread

@SalavatGood · 01.03.2020, 01:32 **[ТС]**

Преподаватель запретил по mpi делать. Хотя куда ни глянь в интернете особенно любят mpi, как будто других библиотек не существует...

Новые блоги и статьи Все статьи Все блоги /
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@SalavatGood 14 / 13 / 1 Регистрация: 18.12.2018 Сообщений: 422

	Как распараллелить алгоритм Гаусса через библиотеку thread? 28.02.2020, 22:51. Показов 2157. Ответов 10 Метки cpp, thread, вопрос, задача (Все метки) Всем привет. Для зачета дали задачу распараллелить на потоки алгоритм Гаусса, но только без MPI. Сам более менее пользовался уже библиотекой thread, однако куда не зайду везде параллелят Гаусса только по MPI, а подробной информации по алгоритму Гаусса по другой библиотеки нет. Хотелось бы у вас узнать, как можно решить данную задачу, может кто-либо уже сталкивался с подобным? Хотя мне уже два человека говорили что алгоритм Гаусса параллелить невозможно 0

@Annemesski 2673 / 1335 / 480 Регистрация: 08.11.2016 Сообщений: 3,688
	29.02.2020, 04:31
	Гаусс нашел весьма наглядный метод решения СЛАУ, но таки да, параллелить его - слабо представимо, разве что прямой проход можно распараллелить по строкам, но выглядит это, по крайней мере в первом приближении, чудовищно... 1. Создать потоки в количестве `n - 1, где n количество уравнений системы` 2. каждому потоку выделить по строке основной матрицы начиная со второй и передать первую строку и множитель 3. параллельно выполнить в потоках вычитание произведения переданной строки и множителя из строки соответствующей потоку 4. убить поток для самой верхней строки (из тех что еще живут в потоках), саму строку и соответствующий ей множитель передать оставшимся живым потокам. 5. повторять пп. 3 и 4 пока не умрут все потоки. Ну а далее - обратный ход и тут уж как не крути мы не можем решать (если, конечно, система имеет решения) уравнение `k - 1` пока не решим уравнение `k` - зависимость по данным. Как-то так. 0

@SalavatGood 14 / 13 / 1 Регистрация: 18.12.2018 Сообщений: 422
	01.03.2020, 01:32 [ТС]
	Преподаватель запретил по mpi делать. Хотя куда ни глянь в интернете особенно любят mpi, как будто других библиотек не существует... 0