Pull to refresh

Параллельные вычисления при поиске простых чисел.

Lumber room
Небольшая лабораторная работа по распараллеливанию.
На входе лобовой алгоритм поиска простых чисел, на выходе изменение скорости вычислений в зависимости от количества нитей.


Для определения простого числа использовался самый примитивный алгоритм поиска простых чисел. Для всех, кто учил программирование, обычно следует за Hello world!
Суть алгоритма: берем кандидата (нечетного само собой), делим на все известные простые числа, меньшие чем половина кандидата. Если ни разу не поделили без остатка — число простое.
Все цифры взяты на поиске первых 10000 простых чисел во втором миллионе. Т.е. нужно найти простые числа с порядковыми номерами от 1000001-1010000. Первый миллион простых чисел был уже посчитан до. На самом деле все посчитано и много после, но цель (пока) была сравнить подходы, а не победить проект GIMPS.

Первый заход:
Берем кандидата на простое число, отдаем его ните, которая его считает. Повторяем операцию по кол-ву нитей. Ждем пока все нити посчитают, собираем результаты, кормим нити следующей партией кандидатов.

Что получилось:

Ось абсцисс — кол-во одновременных нитей. Ординат — время в секундах.

Второй заход:
Берем кандидата, кормим бездельничающей ните, когда нить посчитала, забираем результат и кормим ните следующего кандидата. Повторяем постоянно для всех нитей.

Что получилось:

Опять же, по абсцисс — нити, по ординат — секунды.

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

Очень обескуражили результаты на AMD. Не думал, что мой ноутбук может серверную железяку переплюнуть. Может, есть тут знатоки железа — поделитесь, в чем может быть дело?

Код на С#. RE — .Net 3.5.
В забеге принимали участие следующие машины:
2х XeonDC — hp dl140 g3 Windows 2003 Server
Opteron — FSC RX330 S1 Windows 2003 Server
Core 2 Duo — Lenovo T60 (UD0PSRT). Vista Business.

Определение простого числа — тут.

P.S. Спасибо sannis и barauswald за то, что натолкнули на мысль провести такое мини исследование. Благодаря ему, я теперь четко понимаю как параллельно программить на C#.

UPD
Поменял по тексту процессы на нити (thread), чтобы исключить разночтения.
Модели процессоров: 2x Xeon DC = 2шт Intel Xeon 5110; Opteron = Dual-Core AMD Opteron 2216; Core2Duo = Intel Core 2 T5600.
Ставилось целью проверить как влияет кол-во нитей на скорость вычислений. Я не претендую на сравнение машин — это побочный результат, вывод я по ним не делал, каждый волен интерпретировать результаты как ему угодно.
Всем комментировавшим, спасибо — просветлило :) В будующем, буду стараться выражаться более четко и развернуто.
Tags:
Hubs:
Total votes 40: ↑31 and ↓9 +22
Views 1.1K
Comments Comments 55