Считаем Пи параллельно. Часть 1
В этой серии постов мы попробуем решить одну простую задачу с помощью более-менее актуальных технологий параллельного программирования (Нативные потоки, OpenMP, TBB, MPI, CUDA, OpenCL, OpenACC, Chapel может быть еще что-нить экзотическое. Как бы сравнительно и в hands-on ключе.
Чтобы все влезло в один пост (в нескольких частях) и вообще могло быть совокупно охвачено вниманием проблема была выбрана умышленно тривиальная. Поэтому многие аспекты упомянутых технологий и главное трудности которые возникают при реальном прграммировании современных массивно-параллельных систем останутся за кадром. Также не стоит пользоваться приведённым и примерами в качестве бенчмарка «GPU против CPU» или что-то в этом духе. Единственная цель — показать «как оно работает». Пост рассчитан на людей с параллельным программированием не очень знакомых. Под катом будет много кода. Собственно считать мы будем число Пи путем численного интегрирования
Исходные коды также доступны на github.com/undertherain/pi (будут пополнятся по мере написания следующих частей поста).
Последовательная версия.
Давайте для начала сделаем последовательную версию. Т.е. такую, которая использует одно ядро обычного центрального процессора. Возьмем самый простой из методов численного инетгрирования — метод прямоугольников и закодим его на языке Си (вообще дальше будем пользоваться Си\С++-ным суржиком в виду ряда причин.
Объявим некоторое количество cntSteps прямоугольников на которые мы разобъем нашу площадь под интегралом, посчитаем основание:
и всю площадь, посчитав значение функии в каждом прямоугольнике и домножив на основание.
Впрочем, домножим на основание step мы лучше «за скобками», т.е. за циклом — вот в принципе и все.
Вот полный код программы:
Native Threads
Самая, пожалуй, доступная простым пользователям параллельная архитектура — это обычный многоядерный процессор (кажется сейчас уже трудно найти процессор с одним ядром) или несколько процессоров на одной материнской плате. В принципе и одно ядро способно исполнять параллельно несоколько потоков — такой режим называется псевдо-параллельным или конкурентным. Ядро переключается между процессами (процесс — это грубо говоря находящаяся в памяти программа), выделяя каждому квант времени. В принципе такой режим выполнения уже может привести к росту производительности за счет сокрытия латентности памяти, если не на обычных «домашних» процессорах, то на специализированных многопоточных, но об этом позже. В нашем случае избыточное количество потоков привело бы к замедлению из-за накладных расходов на переключение между потоками.
Самый «исторический» способ исползьовать сразу несколько ядер на процессоре — это механизм потоков операционной системы, который сущесвовал задолго до истинно-параллельных процессоров для конкуренности хотя бы ради более удобного написания программ. С точки зрения программиста важно то, что параллельные потоки, исполняемые на разных ядрах или процессорах видят одно и то же адресное пространство, т.е нет нужды явно передавать данные между потоками. Зато если вдруг разные потоки пишут\читают одну и ту же переменную — то придётся озаботиться синхронизацией.
Ладно, давайти ближе к коду: с точки зрения языка Си поток — это обычная функция или метод класса, удовлетворяющая определённому прототипу. Давайте назовём ее static void * worker ( void * ptrArgs ) , аргументом она получает указатель на структуру, в которой можно сделать полей сколько нужно чтобы передать потоку его аргументы. В нашем случае мы скажем потоковой функии в каком диапазоне считать наш интеграл. В теле потоковой функции — уже известный нам цикл, собсно и считающий по диапазону который мы ему передали в параметрах.
Интервал интегрирования для каждого потока мы заранее вычислим изходя из его порядкового номера. Если один из потоков посчитает свою часть раньше — то соответсвующее ядро будет простаивать, т.е. мы потеряем производительность. Идеально было бы разделить интервал на много маленьих участков и раздавать потокам по мере того как они справляются со своей работой. Но пока оставим как есть.
На исполнение отдельным потоком функция запускается через системный вызов pthread_create в случае POSIX (в линуксе, например) или в случае windows этто будет аналогичный вызов из Win32 API, вуглядеть будет немного по-другому, но в целом похоже.
Результат будем из каждого потока прибавлять к общем перменной pi += sum * step ; (помним что мы находимся в общем адресном пространстве).
Чтобы память не испортилась в случае если два потока будут одновременно изменять одну ячейко нам надо как-то гарантировать что в один момент времени только один поток получает доступ к переменной pi, т.е. создать так называемую «критическую секцию». Для это можно воспользовться специальным механизмом операционной системы под названием мьютекс (от слова mutual exclusion) — если один поток заблокировал мьютекс, другой поток будет ждать (на попытке получить мьютекс самому) пока первый поток его не «освободит».
Итого выходит как-то так:
Копия на http://dumpz.org/195404/ на случай если у кото-то моё адово форматироваие неровно отображается.
На самом деле конкретно в этом примере (но так везти будет не всегда) можно было обойтись без мьютексов вообще если сохранять в каждом потоке результат в отдельную переменную (элемент массива ArgsThread arrArgsThread [ cntThreads ];
) а потом, дождавшись завершения всех потоков — просуммировать что получилось.
Вот код без мьютексов:
Как видите, код получилася довольно громоздкий и некросплатформенный. Если последнее решается отчасти с помощью boost::threads(но не все хотят ставить boost) или в новом C++11 потоки вообще стали частью языка (очень здорово вышло на самом деле) — но большая часть софта пока еще использует старый C++. Но проблема громоздкости кода всё равно остается.
OpenMP
OpenMP — это расширение языка (C/C++/Fortran) позволяющее делать примерно то же самое что мы делали с помощью API потоков операционной системы — но гораздо проще и лаконичней с помощью так называемых прагм. Прагма как бы говорит компилатору «взять вот этот код и исполнять параллельно» — и копмилятор делает все остальное.
Для распараллеливания цикла for в нашем первом последовательном примере достаточно добавить туда одну строчку:
эта прагма говорит, что нужно распараллелить витки цикла, переменную x сделать приватной для каждого потока, по переменной sum потом провести редукцию (или как это по-русски?) по суммированию. Т.е. сначала создать для каждого потока по копии — а потом их сложить. Примерно то же самое, что мы сделали в прошлом примере без мьютекосв. Также OpenMP предоставляет небольшой API для сервисных нужд.
Вычисление числа пи
Короче, я полный ноль в СИ, и нужно решить такую задачку:
Написать программу, которая вычисляет число «Пи» с заданной точностью (воспользоваться тем, что значение частичной суммы ряда 1-1/3+1/5-1/7+. при суммировании достаточно большого количества членов приближается к значению π/4). Программа должна проверять корректность исходных данных. Мне нужно сделать проверку на корректность данных, как это сделать? я вот код написал, но чушь полная. типо засунул if перед while и если не выоплняется то некорректные данные. Запускаю эту программу, ввожу точность и у меня просто командная строка летит и повторяет ответ бесконечно, при этом ответ неверный, всего выводит ответ 1 и после #INF 00.
Вычисление числа Пи
Составить на языке C программу, которая по введённому N возвращает N-ю после запятой десятичную.
Вычисление числа П
Нужна программа на C, вычисляющая число "ПИ" ну или хотя бы карказ ( с объяснением построчно, если.
Вычисление числа ПИ
Помогите разобраться с заданием на языке C. http://dencom.nsknet.ru/_mod_files/ce_images/2009.png
Вычисление числа пи
Всем доброго времени суток, подскажите как в моей программе получить более тысячи знаков после.
Overview
π is a mathematical constant number, approximately equal to 3.14159. It represents the ratio of a circle’s circumference to its diameter. So, how they calculated this magical number ��. Actually, there are a lot of methods to calculate it; one of the most famous methods is monte carlo. In this post I’ll try to explain how this can be done mathematically then programmatically using C#.
Finding the π formula
We know that the area of the circle is:
A = π(R^2) Where R is the radius of the circle.
After isolating π the formula should be:
π = A / (R^2) . (1)
The area of the circle quarter is:
Q = A / 4
Then the area should be:
A = 4 * Q . (2)
Let’s change A in (1) formula to (4 * Q) in (2) formula, the result should be:
π = (4 * Q) / (R^2)
Check the figure below, and read the following lines:
Q here can be denoted as number of points taken in the circle area (only red area). while R^2 is the number of points on the whole square area (red and blue areas).
Thus, the the final equation is:
π = (4 * M) / (N)
Where:
M is the number of points on the circle.
N is the number of points on the square.
Implementing the result with CSharp:
Let’s create a new CSharp console application to get started.
First, I created a simple class to help storing point structure (X, Y) as following:
How do I calculate PI in C#?
I was thinking it would be through a recursive function, if so, what would it look like and are there any math equations to back it up?
I’m not too fussy about performance, mainly how to go about it from a learning point of view.
20 Answers 20
If you want recursion:
This would become, after some rewriting:
Isaac Newton (you may have heard of him before 😉 ) came up with this trick. Note that I left out the end condition, to keep it simple. In real life, you kind of need one.
How about using:
If you want better precision than that, you will need to use an algorithmic system and the Decimal type.
If you take a close look into this really good guide:
You’ll find at Page 70 this cute implementation (with minor changes from my side):
There are a couple of really, really old tricks I’m surprised to not see here.
atan(1) == PI/4, so an old chestnut when a trustworthy arc-tangent function is present is 4*atan(1).
A very cute, fixed-ratio estimate that makes the old Western 22/7 look like dirt is 355/113, which is good to several decimal places (at least three or four, I think). In some cases, this is even good enough for integer arithmetic: multiply by 355 then divide by 113.
355/113 is also easy to commit to memory (for some people anyway): count one, one, three, three, five, five and remember that you’re naming the digits in the denominator and numerator (if you forget which triplet goes on top, a microsecond’s thought is usually going to straighten it out).
Note that 22/7 gives you: 3.14285714, which is wrong at the thousandths.
355/113 gives you 3.14159292 which isn’t wrong until the ten-millionths.
Acc. to /usr/include/math.h on my box, M_PI is #define’d as: 3.14159265358979323846 which is probably good out as far as it goes.
The lesson you get from estimating PI is that there are lots of ways of doing it, none will ever be perfect, and you have to sort them out by intended use.
355/113 is an old Chinese estimate, and I believe it pre-dates 22/7 by many years. It was taught me by a physics professor when I was an undergrad.