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

Чулан

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

Для определения простого числа использовался самый примитивный алгоритм поиска простых чисел. Для всех, кто учил программирование, обычно следует за 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.
Ставилось целью проверить как влияет кол-во нитей на скорость вычислений. Я не претендую на сравнение машин — это побочный результат, вывод я по ним не делал, каждый волен интерпретировать результаты как ему угодно.
Всем комментировавшим, спасибо — просветлило :) В будующем, буду стараться выражаться более четко и развернуто.

+22

6 января 2009, 21:17

unconnected 81,7

комментарии (55)

mace 6 января 2009, 21:44 #

берем кандидата (нечетного само собой), делим на все известные простые числа, меньшие чем половина кандидата.

А почему не корень кандидата?

НЛО прилетело и опубликовало эту надпись здесь

mace 6 января 2009, 21:54 # ↑

Зачем вычислять его каждый раз? Достаточно один раз запомнить его в переменной. А квадратный корень очень просто и быстро вычисляется бинарным поиском за логарифмическое время.

НЛО прилетело и опубликовало эту надпись здесь

unconnected 6 января 2009, 22:11 # ↑

Так и есть, выйгрышь значительный.
Знаца, 16 нитей, мой ноутбук:
умножаем (knownPrime*2<candidate): 58.101
делим (knownPrime<candidate/2): 107.577
корень (knownPrima<sqrt(candidate)): 0.825

на графиках использовалось умножение

НЛО прилетело и опубликовало эту надпись здесь

unconnected 6 января 2009, 22:21 # ↑

пример кода можно? я на С только лабораторные в институте делал, боевых навыков не имею

а так, сам в шоке, думал где выход из цикла несанкционированный — нет, все честно

НЛО прилетело и опубликовало эту надпись здесь

unconnected 6 января 2009, 22:39 # ↑

knownPrime<<1 < candidate: 47.925
knownPrime >1: 45.859

unconnected 6 января 2009, 22:40 # ↑

имелось в виду

unconnected 6 января 2009, 22:41 # ↑

имелось в виду:
knowPrime меньше candidate сдвиг в право на 1: 45.859

НЛО прилетело и опубликовало эту надпись здесь

xeon 7 января 2009, 01:18 # ↑

В C# операции вроде *2, 4, 8… и деление на степени двойки оптимизированы.
В IL-коде еще будут операции умножения, а вот уже в ассемблерном после JIT будут только сдвиги. Однако в результирующем ASM для деления и умножения будет больше mov-ов.

C#
var j = i / 2;
IL:
L_0004: ldloc.0
L_0005: ldc.i4.2
L_0006: div
L_0007: stloc.1
ASM:
0000003f mov eax,dword ptr [rsp+20h]
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax

C#:
var k = i >> 1;
IL:
L_0008: ldloc.0
L_0009: ldc.i4.1
L_000a: shr
L_000b: stloc.2
ASM:
00000054 mov eax,dword ptr [rsp+20h]
00000058 sar eax,1
0000005a mov dword ptr [rsp+28h],eax

7vies 7 января 2009, 10:47 # ↑

Судя по этому коду
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
у вас переменная — со знаком, поэтому возникает этот дополнительный код если сравнивать просто со сдвигом.
Но вот этой вот магии мне всё равно не понять:
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax
Кагбэ temp = eax; eax = temp; result = eax;

xeon 7 января 2009, 11:02 # ↑

Да, магия странная. Сейчас проверил на Int64 вместо Int32, т.к запускаю у себя под 64-битной ОС. Никуда эти странные mov-ы не исчезли. Можно еще на досуге посмотреть, как JIT от Mono себя ведет в подобной ситуации.

Int64 i = 10;
0000003a mov qword ptr [rsp+20h],0Ah

Int64 j = i / 2;
00000043 mov rax,qword ptr [rsp+20h]
00000048 cqo
0000004a sub rax,rdx
0000004d sar rax,1
00000050 mov qword ptr [rsp+38h],rax
00000055 mov rax,qword ptr [rsp+38h]
0000005a mov qword ptr [rsp+28h],rax

Int64 k = i >> 1;
0000005f mov rax,qword ptr [rsp+20h]
00000064 sar rax,1
00000067 mov qword ptr [rsp+30h],rax

middle 7 января 2009, 10:02 # ↑

Во-первых, если вычислять числа последовательно или почти последовательно (т.е. если количество чисел, обрабатываемых последовательно одним выч. узлом, сильно меньше, чем сами числа), то при переходе от n на n+m (где m сильно меньше n) корень легко пересчитывается: единичка либо прибавляется, либо нет :)

Во-вторых, в качестве альтернативы можно сравнивать p<=sqrt(n), а можно p*p<=n, и тут тоже можно придумать всякие оптимизации… ;)

middle 7 января 2009, 10:59 # ↑

Прошу прощения, неправильно написал. Должно быть «т.е. если разрывы между числами, обрабатываемыми одним выч. узлом, сильно меньше, чем сами числа».

unconnected 6 января 2009, 21:53 # ↑

с точки зрения правильности алгоритма — абсолютно верно, с точки зрения оценки вычислительных мощностей — не существенно
на самом деле, вспомнил о квадрате, после того, как результаты для первого графика получил, соответственно, пришлось оставить неоптимальный алгоритм поиска, чтобы сравнение было верно

mace 6 января 2009, 21:55 # ↑

Для больших чисел разница будет очень существенной.

YasonBy 6 января 2009, 22:01 #

Не думал, что мой ноутбук может серверную железяку переплюнуть.

Кто-то, Вы или я, неправильно понимает графики. ПО оси абсцисс — время, т.е. «меньше-лучше». Графики Opteron'а в обоих случаях выше других, т.е. при равном количестве нитей, оптерону требуется большее время. Где «переплюв»?

steck 6 января 2009, 22:01 # ↑

ноутбук на коре дуо. Оптерон серверная железка.

YasonBy 6 января 2009, 22:03 # ↑

Виноват, не знал… В таком случае, видимо, это означает (временный) конец холивора AMD vs. Intel…

savant 7 января 2009, 01:49 # ↑

оптерон не n-ядерный похоже был. в параллельных вычислениях это играет свою роль.

unconnected 7 января 2009, 10:58 # ↑

2-x ядерный, это то и удивительно

НЛО прилетело и опубликовало эту надпись здесь

YasonBy 6 января 2009, 22:02 # ↑

*По оси абсцисс…

steck 6 января 2009, 22:01 #

А сам код не выложите?

unconnected 6 января 2009, 22:14 # ↑

если общественность интересует — выложу, выкладывать быдло код не хочется, а приводить его в порядок просто так — лень

steck 6 января 2009, 22:17 # ↑

я бы погладел.
За былость не боитесь.

unconnected 6 января 2009, 22:32 # ↑

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

Yfka 7 января 2009, 01:01 # ↑

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

TheShade 7 января 2009, 01:12 #

Побойтесь железо «на коленке» друг с другом сравнивать :)
Компании целые комитеты устраивают, чтобы всё было честно.

+11

Yfka 7 января 2009, 01:37 #

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

в исследовательском отделе коммерческой компании во все дырки бы…)

1. Непонятно что именно исследовалось.
В первом абзаце написано «нити»:

в зависимости от количества нитей.

Тогда как в вариантах уже «процессы»:

Берем кандидата на простое число, отдаем его процессу, который его считает.

Берем кандидата,

кормим бездельничающему процессу

Т.е. нити или процессы? (Накладные расходы на создание процесса)
Рекомендация: писать об этом явно и недвусмысленно, всегда показывать исходники тестов.

2. Непонятно что именно исследовалось. И, кажись, сам автор этого не понял.
2.1. Исследовалась ли качество реализации .Net framework в зависимости от архитектуры процессора?
2.2. Исследовалась ли скорость переключения в различных версиях .Net framework? (На висте минимальная версия 3.0, а на сервере какая

стояла?)
Рекомендация: исследовать на одной версии виртуальной машины. (Сначала 3.0, например, потом 3.5)

3. Непонятно что именно исследовалось. Автор этого сам не знает, и отсюда непонятные результаты.

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

знатоки железа — поделитесь, в чем может быть дело?

А, по-моему, исследовалась как раз реализация механизма переключения

в различных ОС.
В висте и получилось быстрее.
Рекомендация: исследовать на одной версии ОС.
Т.е. всё кроме исследуемого параметра должно быть одинаковым.

Заключение:
Автор — молодец, рекомендую продолжать, но только более вдумчиво.

unconnected 7 января 2009, 11:11 # ↑

За развернутый комментарии спасибо.
исследовалось то, как кол-во нитей или процессов (т.к. нет устоявшегося перевода), которые Thread, влияют на скорость вычисления, если не изменять базовый алгоритм.
ВМ я указал — везде одинаковая .Net 3.5.
Сравнивалось два подхода, т.е. сравнивать нужно функции на первом и втором графике для каждой из машин.
Разные машины приведены в общем-то для расширения кругозора (все равно они в стойках стоят и на праздниках бездельничают)
В любом случае — сравнение не в пользу АМД — серверный процессор от Интела тоже участвовал :)

eschava 7 января 2009, 12:59 # ↑

Thread это уж точно не процесс

savant 7 января 2009, 14:43 # ↑

Thread — это всегда нить. Process обозначается словом «процесс». Путать эти понятия не стоит. Разницу я думаю вы и так знаете :)

underwater 7 января 2009, 02:06 #

Еще бы через CUDA прогнать

TheShade 7 января 2009, 02:06 #

Только перед тем, как продолжать, определитесь, что Вы планируете исследовать:

1. «Как сделать самый быстрый параллельный primality testing?». Тогда вам сюда.

2. «Какая платформа лучше для имплементации выбранного алгоритма?». Тогда начинать отсюда, хорошего учебника по параллельному программированию, плюс запастись хорошим профайлером.

3. «Какая железка лучше для выполнения параллельных задач?». Не надо этим вопросом непрофессионально заниматься :)

Недавно я настолько устал говорить одно и тоже, что написал Performance Tuning DOs/DON'Ts (ссылка в блог, извините).

JonyRock 7 января 2009, 02:10 #

Темой моей курсовой работы было «Реализация многопоточности в .Net». Хочу выложить на хабр, но не хватает кармы…

Sannis 7 января 2009, 15:06 # ↑

Для персонального блога хватает, а для коллективного вам ещё кто-нибудь подбросит плюс, я уверен :)

JonyRock 7 января 2009, 16:54 # ↑

Спасибо автору за статью, спасибо Вам за карму. Планирую заняться после сессии.

Gasoid 7 января 2009, 02:30 #

------простые числа на питоне--------------
#!/usr/bin/env python
import threading

thr = 100
sim = 10000
s = 3
S = [1,2]
def simple(n) :
    for d in range(2,n) :
        if n%d :
            if d == n-1: S.append(n)
        else : break

while s < sim :
    if threading.activeCount() <= thr:
        threading.Thread(target=simple, name="t%i" % s, args=[s]).start()
        s += 1

print S

выполняется буквально несколько секунд на интеле 4 в debian
рад и удивлен))

7vies 7 января 2009, 11:02 # ↑

Ну, несколько секунд для простых чисел до 10к — это как-то не очень быстро…

Stebanoid 7 января 2009, 11:52 # ↑

def good_prime©:
    """Возвращает список простых чисел, найденный
методом "решето Сундарама" """
    #c=time.clock()
    D=C/2
    B=C/6
    A=set(range(D))
    for i in xrange(1,B+1):
        for j in xrange(i,(D+i)/(1+2*i)+1):
            A.discard(i+j+2*i*j)
    A=[ 2*x+1 for x in A ]
    #print time.clock()-c
    return A

А так? :)

ptalus 7 января 2009, 12:51 # ↑

«Очень» оптимальная программа — много лишних итераций как в главном цикле, так и в функции.
1) в главном цикле можно перебирать только нечетные числа
2) в функции перебирать нечетные, от 3 до n/2 с шагом 2 ( d in range(3, n//2, 2) )

ptalus 7 января 2009, 12:52 # ↑

комментарий к первой программе

proxor 7 января 2009, 06:51 #

Интересно было бы на Erlang посмотреть в такой же ситуации :) Не займетесь?

middle 7 января 2009, 10:05 # ↑

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

–1

Halt 7 января 2009, 12:10 # ↑

А вот не скажите. Все зависит от реализации. К тому же «динамический язык» не значит «медленный язык». Скажем, меня жутко удивило, что Dolphin Smalltalk считал некоторые тесты (кажется простые числа там тоже были) сопоставимо а то и быстрее альтернатив.

Хотя сами разработчики Dolphin-а говорят (и я с ними согласен) что целочисленные тесты для таких дел это зло и не могут являться критерием скорости языка. В том смысле, что реальные данные появляются в реальных же, боевых задачах, где автоматическая оптимизация кода скажет свое слово.

middle 7 января 2009, 14:30 # ↑

Конечно. Но реализация Erlang пока одна и мы все её знаем :)

Halt 7 января 2009, 19:54 # ↑

Разумеется :) Я всего лишь попытался посмотреть с другой стороны

dust 7 января 2009, 10:08 #

На той же википедии (на заметку)

За нахождение простого числа из более чем 10⁸ десятичных цифр EFF назначила награду в 150000 долларов США.

Doggy 7 января 2009, 15:19 # ↑

Ушел искать :)

Dimchansky 7 января 2009, 10:34 #

Код в студию!

ExD 7 января 2009, 13:24 #

Код не выложили, Parallel Extensions навряд ли юзали, так что ядро вы использовали скорее всего одно. Хотелось бы видеть также результаты после использования NGen'а. Конфигурации серверов не указаны(интересует конкретные процессоры и оперативная память). На другие косяки вам тоже указали. В общем очень скользкий тест, который стоит провести более честно;)

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