tag:blogger.com,1999:blog-19730900031485797722024-03-21T16:58:34.683+11:00Yasir Arsanukaev | tech blogUnknownnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-1973090003148579772.post-62379822624388605802011-02-07T15:47:00.009+11:002011-02-08T21:26:38.623+11:00Code-golf: Поиск в ширину и – в глубину с помощью HaskellНаписал короткий код на Haskell для <a href="http://en.wikipedia.org/wiki/Breadth-first_search">поиска в ширину</a> и <a href="http://en.wikipedia.org/wiki/Depth-first_search">поиска в глубину</a>.<br /><a name='more'></a><br />Для обоих видов поиска используется рекурсивная структура, которая в читабельном виде выглядит следующим образом:<br /><br /><pre class="prettyprint lang-hs"><br />data Node a = Node {value::a, children::[Node a]}<br /></pre><br /><br />Сами тексты соответственно выглядят:<br /><br /><pre class="prettyprint lang-hs"><br />bfs :: Node a -> [a]<br />bfs (Node a b) = bfs' [a] b<br /> where bfs' res [] = res<br /> bfs' res n = bfs' (res ++ (map value n)) $ concatMap children n<br /><br />dfs :: Node a -> [a]<br />dfs node = dfs' [node] []<br /> where dfs' [] result = result<br /> dfs' (x:xs) result = dfs' (children x ++ xs) (result ++ [value x])<br /></pre><br /><br />Ну, и в сжатом виде:<br /><br /><pre class="prettyprint lang-hs"><br />data N a=N{v::a,c::[N a]}<br /><br />b(N a b)=d[a]b<br />d r[]=r<br />d r n=d(r++(map v n))$concatMap c n<br /><br />d n=f[n][]<br />f(x:y)=f(c x++y).(++[v x])<br />f _=id<br /></pre><br /><br />Где функция <code>b</code> – поиск в ширину, а функция <code>d</code> – в глубину.<br /><br />Поиск в глубину пытался сократить по-разному, в т. ч., как видно, с помощью <a href="http://en.wikipedia.org/wiki/Function_composition">композиции функций</a> (HaskellWiki – <a href="http://www.haskell.org/haskellwiki/Pointfree">Point-free Style</a>). Хотя, если развернуть композицию, вернув назад аргумент, объем кода будет идентичным:<br /><br /><pre class="prettyprint lang-hs"><br />d n=f[n][]<br />f(x:y)r=f(c x++y)$r++[v x]<br />f[]r=r<br /></pre><br /><br />Если у кого-то есть идеи по дальнейшему возможному сокращению кода, либо вы хотите попробовать реализовать сжатые алгоритмы на вашем любимом языке, прошу предлагать свои варианты на новом сайте для любителей программирования и программных головоломок Code Golf – Stack Exchange:<br /><br /><ul><br /> <li><a href="http://codegolf.stackexchange.com/q/118/112">Tree traversal: Breadth-first search</a></li><br /> <li><a href="http://codegolf.stackexchange.com/q/596/112">Tree traversal: Depth-first search</a></li><br /></ul><br /><br />Have <code>fun()</code>! ;-)Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-1973090003148579772.post-9063456678325979972010-04-15T00:38:00.028+10:002011-02-07T16:25:51.784+11:00Haskell и параллелизм: Триангуляция сферы параллельным рекуррентным разбиением тетраэдра с применением плоского затененияНадеюсь, вас не испугал заголовок статьи. Под катом приводится описание одного из методов распараллеливания вычислений в Haskell на примере изображения затененной сферы, имеются скриншоты результатов работы программы (трафика мало).<br /><a name='more'></a><br /><span style="font-weight: bold;">Введение</span><br /><br />Сначала нужно решить задачу построения сферы. Для этого обычно применяют аппроксимацию.<br /><br />Чтобы аппроксимировать сферическую поверхность, можно воспользоваться методом <span style="font-style: italic;">рекурсивного разбиения</span>, а в качестве <a href="http://ru.wikipedia.org/wiki/Правильный_многогранник">правильного многогранника</a> выберем тетраэдр, 4 грани которого являются равносторонними треугольниками. Можно было бы использовать любой другой правильный многоугольник; например, <a href="http://ru.wikipedia.org/wiki/Икосаэдр">икосаэдр</a> отлично подходит для аппроксимации сферы.<br /><br /><br /><span style="font-weight: bold;">Вершины тетраэдра</span><br /><br />Для определения координат вершин тетраэдра можно воспользоваться <a href="http://www.mathematische-basteleien.de/tetrahedron.htm">данными</a> выкладками. Предположим, что после соответствующих вычислений мы имеем следующие координаты четырех вершин тетраэдра:<br />(0.0, 0.0, 1.0),<br />(0.0, 0.942809, -0.333333),<br />(-0.816497, -0.471405, -0.333333),<br />(0.816497, -0.471405, -0.333333)<br /><br /><br /><span style="font-weight: bold;">Каркас приложения</span><br /><br />Для визуализации используем OpenGL; Haskell имеет к ней соответствующую <a href="http://www.haskell.org/haskellwiki/Opengl">привязку</a>. Теперь начнем создавать каркас приложения на Haskell с ее помощью:<br /><pre class="prettyprint lang-hs"><br />main = do<br /> (progname, _) <- getArgsAndInitialize <br /> initialDisplayMode $= [DoubleBuffered, WithDepthBuffer]<br /> initialWindowSize $= (Size 640 640)<br /> createWindow "Sphere approximation" <br /> myInit<br /> displayCallback $= display<br /> reshapeCallback $= Just reshape<br /> mainLoop<br /><br />myInit = do <br /> ortho (-2.0) 2.0 (-2.0) 2.0 (-10.0) 10.0 <br /> depthFunc $= Just Less<br /><br />display = do <br /> clear [ColorBuffer, DepthBuffer]<br /> -- put your drawing code here<br /> swapBuffers <br /><br />reshape s@(Size w h) = do<br /> viewport $= (Position 0 0, s)<br /> postRedisplay NothingNothing<br /></pre><br /><br />В этом наброске в функции <code class="prettyprint lang-hs">main</code> производится инициализация приложения, установка глобальных переменных состояния, и создается окно. В <code class="prettyprint lang-hs">myInit</code> устанавливается матрица ортогональности. В <code class="prettyprint lang-hs">initialDisplayMode</code> мы помещаем настройки, в данном случае мы указали, что хотим использовать двойную буферизацию, а также включить буфер глубины (Z-buffer); если этого не сделать, то едва ли изображение будет выглядеть так, как мы этого ожидаем. Пока ничего отображаться в окне не должно. В функции <code class="prettyprint lang-hs">display</code> перед началом рисования нужно очистить буферы цвета и глубины с помощью вызова <code class="prettyprint lang-hs">clear</code>, а после этого, поскольку мы использовали двойную буферизацию, переключить буфер с помощью <code class="prettyprint lang-hs">swapBuffers</code>. <br /><br /><br /><span style="font-weight: bold;">Отображение тетраэдра </span><br /><br />Теперь, после того, как у нас имеется каркас, мы попробуем что-нибудь изобразить. Изобразим тетраэдр. Для этого добавим к коду следующие строки:<br /><pre class="prettyprint lang-hs"><br />type Gf3 = (GLfloat, GLfloat, GLfloat)<br /><br />figCoords :: [Gf3]<br />figCoords = [ (0.0, 0.0, 1.0),<br /> (0.0, 0.942809, -0.333333),<br /> (-0.816497, -0.471405, -0.333333),<br /> (0.816497, -0.471405, -0.333333)<br /> ]<br /><br />tetrahedron coords = do<br /> triangle (coords !! 0) (coords !! 1) (coords !! 2)<br /> triangle (coords !! 3) (coords !! 2) (coords !! 1)<br /> triangle (coords !! 0) (coords !! 3) (coords !! 1)<br /> triangle (coords !! 0) (coords !! 2) (coords !! 3)<br /><br />triangle (x1, y1, z1) (x2, y2, z2) (x3, y3, z3) = do<br /> renderPrimitive Triangles $ do<br /> vertex $ Vertex3 x1 y1 z1<br /> vertex $ Vertex3 x2 y2 z2<br /> vertex $ Vertex3 x3 y3 z3<br /></pre><br /><br />а функцию <code class="prettyprint lang-hs">display</code> приведем к следующему виду:<br /><pre class="prettyprint lang-hs"><br />display = do<br /> clear [ColorBuffer, DepthBuffer]<br /> tetrahedron figCoords<br /> swapBuffers<br /></pre>Поскольку никакого затенения сейчас не используется, и все изображается с применением белой заливки, то вы должны увидеть белый равносторонний треугольник. Эти три вершины формируют основание тетраэдра:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuR0e8stxnxB6QMnfI73uf1cwLgkKNC7vj8dIrLLmI5rIl6wW0RHKNi-ob27gP2yg21fbL_MwLxVwt070IyU2JA9UWSNA4P0_pRF_tScf1Y8gqMNqChrTUt4KEOannfTUR1MkLMxQ7mAs/s1600/haskell_lit_sphere_00.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 223px; height: 201px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuR0e8stxnxB6QMnfI73uf1cwLgkKNC7vj8dIrLLmI5rIl6wW0RHKNi-ob27gP2yg21fbL_MwLxVwt070IyU2JA9UWSNA4P0_pRF_tScf1Y8gqMNqChrTUt4KEOannfTUR1MkLMxQ7mAs/s320/haskell_lit_sphere_00.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5465159288437759746" /></a><br /><br /><br /><span style="font-weight: bold;">Разбиение тетраэдра</span><br /><br />Имеющийся объект — тетраэдр — не очень-то пока похож на сферу. Поэтому попробуем сделать его чуть более похожим, произведя разбивку его граней.<br />Идея состоит в делении каждой грани тетраэдра на 4 равных треугольника:<br /><pre><br /> /\ /\<br /> / \ / \<br /> / \ /----\<br /> / \ / \ / \<br /> /________\ /___\/___\<br /></pre><br />Т. е. три новые точки делят каждую сторону треугольника, на которой они лежат, пополам. Три новых треугольника лежат в плоскости той же грани, которая была разбита. Поэтому необходимо сдвинуть новые вершины на поверхность аппроксимируемой сферы, выполнив нормализацию — не путать с нормалью, к ней мы вернемся чуть позже — их координат. Добавим к программе функцию рекуррентного разбиения треугольника:<br /><pre class="prettyprint lang-hs"><br />divideTriangle :: Gf3 -> Gf3 -> Gf3 -> Int -> IO ()<br />divideTriangle p1 p2 p3 0 = triangle p1 p2 p3<br />divideTriangle a@(x1, y1, z1) b@(x2, y2, z2) c@(x3, y3, z3) ndivisions = do<br /> divideTriangle a v1 v2 (ndivisions - 1)<br /> divideTriangle c v2 v3 (ndivisions - 1)<br /> divideTriangle b v3 v1 (ndivisions - 1)<br /> divideTriangle v1 v3 v2 (ndivisions - 1)<br /> where v1 = normalizeCoords ((x1 + x2)/2, (y1 + y2)/2, (z1 + z2)/2)<br /> v2 = normalizeCoords ((x1 + x3)/2, (y1 + y3)/2, (z1 + z3)/2)<br /> v3 = normalizeCoords ((x2 + x3)/2, (y2 + y3)/2, (z2 + z3)/2)<br /><br />normalizeCoords :: Gf3 -> Gf3<br />normalizeCoords c@(x, y, z)<br /> | len > 0 = (x/len, y/len, z/len)<br /> | otherwise = c<br /> where len = sqrt (x*x + y*y + z*z)<br /></pre><br /><br />а также модифицируем функции <code class="prettyprint lang-hs">tetrahedron</code>, <code class="prettyprint lang-hs">display</code> и <code class="prettyprint lang-hs">main</code> для учета количества рекуррентных разбиений следующим образом:<br /><pre class="prettyprint lang-hs"><br />tetrahedron coords ndivisions = do<br /> divideTriangle (coords !! 0) (coords !! 1) (coords !! 2) ndivisions<br /> divideTriangle (coords !! 3) (coords !! 2) (coords !! 1) ndivisions<br /> divideTriangle (coords !! 0) (coords !! 3) (coords !! 1) ndivisions<br /> divideTriangle (coords !! 0) (coords !! 2) (coords !! 3) ndivisions<br /><br />display nDivisions = do<br /> clear [ColorBuffer, DepthBuffer]<br /> tetrahedron figCoords nDivisions<br /> swapBuffers<br /><br />main = do<br /> (progname, _) <- getArgsAndInitialize<br /> initialDisplayMode $= [DoubleBuffered, WithDepthBuffer]<br /> initialWindowSize $= (Size 640 640)<br /> createWindow "Sphere approximation"<br /> myInit<br /> let nDivisions = 3<br /> displayCallback $= (display nDivisions)<br /> reshapeCallback $= Just reshape<br /> mainLoop<br /></pre><br />После компиляции и запуска такой программы изображается что-то наподобие этого:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiAbGIjGyu8ciV4kU-UFi2xPavVNJTA-XyIMg1IAG8wcOWPG-BSy7teIbq86WZ_SJVNWO50MTBcpCMJeRx8KVk4WaD05NOji1fPdYs6LElC7KONgDXINg2KDec6pXVeD817inqXEzERuBU/"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 222px; height: 206px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiAbGIjGyu8ciV4kU-UFi2xPavVNJTA-XyIMg1IAG8wcOWPG-BSy7teIbq86WZ_SJVNWO50MTBcpCMJeRx8KVk4WaD05NOji1fPdYs6LElC7KONgDXINg2KDec6pXVeD817inqXEzERuBU/" alt="" border="0" /></a><br />Держу пари, когда мы увеличим число разбиений и применим затенение, то наш рекуррентно разбитый тетраэдр уже будет не отличить от сферы.<br /><br /><br /><span style="font-weight:bold;">Затенение</span><br /><br />Существует <a href="http://www.compgraphics.info/3D/lighting/shading_model.php">множество</a> способов затенения. Одним из самых первых и распространенных был метод плоского затенения, где освещенность производится для полигона (треугольника) целиком. Этот метод хорошо подходит для затенения каких-либо объектов с прямыми гранями, но не совсем хорошо — для неровных поверхностей, поскольку при таком затенении на неровном объекте отчетливо становятся видны грани (<a href="http://en.wikipedia.org/wiki/Mach_bands">Mach bands</a>, <a href="http://www.fcenter.ru/online.shtml?articles/hardware/videos/8749">статья "Как компьютер рисует изображения"</a>). Тем не менее, нам не важна в данном случае фотореалистичность. Поэтому применим плоское затенение.<br /><br />Для определения степени освещенности точки — в нашем случае освещается треугольник — нужно определить косинус угла между нормалью, идущей из этой точки, и вектором идущим из этой точки к точечному источнику света (<a href="http://www.xakep.ru/post/14208/default.asp">статья в журнале Xakep "Освещение в играх"</a>)<br /><br />Чтобы найти нормаль, можно воспользоваться векторным произведением:<br /><pre class="prettyprint lang-hs"><br />crossProd :: (Num a) => (a, a, a) -> (a, a, a) -> (a, a, a) -> (a, a, a)<br />crossProd (x1, y1, z1) (x2, y2, z2) (x3, y3, z3) = (x, y, z)<br /> where x = (y2 - y1) * (z3 - z1) - (z2 - z1) * (y3 - y1)<br /> y = (z2 - z1) * (x3 - x1) - (x2 - x1) * (z3 - z1)<br /> z = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)<br /></pre><br />Нахождение косинуса угла между полученной нормалью и вектором к источнику света может замедлить вычисления, поэтому можно воспользоваться свойством скалярного произведения векторов:<br /><pre class="prettyprint lang-hs"><br />dotProd :: (Num a) => (a, a, a) -> (a, a, a) -> a<br />dotProd (x1, y1, z1) (x2, y2, z2) = x1*x2 + y1*y2 + z1*z2<br /></pre><br />Функцию <code class="prettyprint lang-hs">triangle</code> изменим следующим образом:<br /><pre class="prettyprint lang-hs"><br />triangle :: Gf3 -> Gf3 -> Gf3 -> IO ()<br />triangle a@(x1, y1, z1) b@(x2, y2, z2) c@(x3, y3, z3) = do<br /> -- Detrmine a triangle normal<br /> -- (it's just a direction, not a vector)<br /> -- Normalized normals are happy normals ;)<br /> let normal = normalizeCoords $ crossProd a b c<br /> let lightPos = (1.0, 1.0, 1.0::GLfloat)<br /> let intensity = 1.0 * dotProd normal lightPos<br /><br /> renderPrimitive Triangles $ do<br /> color $ Color3 intensity intensity intensity<br /> vertex $ Vertex3 x1 y1 z1<br /> vertex $ Vertex3 x2 y2 z2<br /> vertex $ Vertex3 x3 y3 z3<br /></pre><br />Здесь координаты источника света (1.0, 1.0, 1.0), коэффициент отражающей способности установлен в 1.0, интенсивность отражения изменяется для всех цветовых каналов одинаково. Теперь, если вы запустите программу, то можно будет увидеть следующее изображение (48 треугольников):<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9rye-DtiXBQRspZA8OYNnq-2MejnBePF6syt5jKTgo_AZGkuAQuJcV2P4Z92iAg0FsiwIr04YXGKBeWqkvhQqQEb7MUt92r1mH_jL2vpdvaQS4piojs741IuTnyPC2oN1nBMukkls6Hs/s1600/haskell_lit_sphere_02.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 230px; height: 216px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9rye-DtiXBQRspZA8OYNnq-2MejnBePF6syt5jKTgo_AZGkuAQuJcV2P4Z92iAg0FsiwIr04YXGKBeWqkvhQqQEb7MUt92r1mH_jL2vpdvaQS4piojs741IuTnyPC2oN1nBMukkls6Hs/s320/haskell_lit_sphere_02.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5465163127703589586" /></a><br />По-моему, оно походит чем-то на подсвеченную сферу. А если увеличить число разбиений до 8-1, то получится очень реалистичная сфера (49 152 треугольника):<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKogEMVY0HOhFAc0aSpZDnai82J5YccQaKOjMWZfC-OFuDueCQaRnYe9CKt9-SRqhqhBNJE8LQbVgk4rXEVuYXYq02cu7o1HqfABRxVVDsYvEHfwTcrC1lExBwsBI3rTPnqQKKn682gQI/s1600/haskell_lit_sphere_03.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 230px; height: 216px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgKogEMVY0HOhFAc0aSpZDnai82J5YccQaKOjMWZfC-OFuDueCQaRnYe9CKt9-SRqhqhBNJE8LQbVgk4rXEVuYXYq02cu7o1HqfABRxVVDsYvEHfwTcrC1lExBwsBI3rTPnqQKKn682gQI/s320/haskell_lit_sphere_03.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5465162085476455634" /></a><br /><a href="http://bitbucket.org/yasir/haskell/src/tip/sphere_approx/lit_sphere.hs">Полный код</a> приложения на данном этапе.<br /><br /><span style="font-weight:bold;">Параллелизм</span><br /><br />Все действия, приведенные выше, были сделаны, преследуя основную цель — сделать полученный код пригодным для распараллеливания. В противном случае можно было бы просто предоставить все операции по формированию изображения, его затенению и т. д. OpenGL, она это сделала бы гораздо эффективнее, поскольку эти алгоритмы реализованы аппаратно.<br /><br />Для Haskell <a href="http://www.haskell.org/haskellwiki/Applications_and_libraries/Concurrency_and_parallelism">имеются разнообразные библиотеки</a>, позволяющие сделать приложение многопоточным. Мы воспользуемся вызовом forkIO, и синхронизирующей переменной MVar, которые достаточно давно доступны в <a href="http://ru.wikipedia.org/wiki/GHC">Glasgow Haskell Compiler</a>. Импортируем их, добавив следующие строки в начало исходного кода:<br /><pre class="prettyprint lang-hs"><br />import Control.Concurrent<br />import Control.Concurrent.MVar<br />import Control.Monad<br /></pre><br />К текущему моменту в нашей программе можно распараллелить вызовы функции <code class="prettyprint lang-hs">divideTriangle</code>, осуществляемые в функции <code class="prettyprint lang-hs">tetrahedron</code>:<br /><pre class="prettyprint lang-hs"><br />tetrahedron :: [Gf3] -> Int -> IO ()<br />tetrahedron coords ndivisions = do<br /> child0 <- thread (coords !! 0) (coords !! 1) (coords !! 2) ndivisions<br /> child1 <- thread (coords !! 3) (coords !! 2) (coords !! 1) ndivisions<br /> child2 <- thread (coords !! 0) (coords !! 3) (coords !! 1) ndivisions<br /> child3 <- thread (coords !! 0) (coords !! 2) (coords !! 3) ndivisions<br /> ret <- mapM takeMVar [child0, child1, child2, child3]<br /> return ()<br /><br />thread :: Gf3 -> Gf3 -> Gf3 -> Int -> IO (MVar (IO ()))<br />thread p1 p2 p3 ndivisions = do<br /> mvar <- newEmptyMVar<br /> forkIO $ do <br /> let r = divideTriangle p1 p2 p3 ndivisions<br /> putMVar mvar r<br /> return mvar<br /></pre><br />Здесь создаются 4 нити, работающие параллельно. В функции <code class="prettyprint lang-hs">thread</code> перед созданием нити инициализируется синхронизирующая переменная с помощью вызова <code class="prettyprint lang-hs">newEmptyMVar</code>. Потом создается сама нить, которая осуществляет вызов <code class="prettyprint lang-hs">divideTriangle</code> и помещает в <code class="prettyprint lang-hs">MVar</code> результат, который был возвращен функцией <code class="prettyprint lang-hs">divideTriangle</code>.<br /><br />Само по себе содержимое <code class="prettyprint lang-hs">MVar</code> нас не интересуит, оно лишь служит сигналом нити, выполняющей вызов функции <code class="prettyprint lang-hs">takeMVar</code>, к тому, что можно продолжать дальнейшие вычисления, т. е. функция <code class="prettyprint lang-hs">takeMVar</code> не вернет управление, пока в <code class="prettyprint lang-hs">MVar</code> не будет помещено какое-либо значение. Таким образом, в списке <code class="prettyprint lang-hs">ret</code> будут находиться значения, которые нити поместили с помощью вызова <code class="prettyprint lang-hs">putMVar</code>, и программа не продолжит работу, пока все нити не поместят эти значения. Вызов <code class="prettyprint lang-hs">return ()</code> позволяет вернуть значение, которое соответствует типу функции <code class="prettyprint lang-hs">tetrahedron :: [Gf3] -> Int -> IO ()</code>, т. е. пустой кортеж.<br /><br />Но если вы скомпилируете и запустите эту программу, то прежней сферы вы не увидите! Предлагаю вам подумать, почему так происходит (вспомните свойства языка Haskell). <a href="http://bitbucket.org/yasir/haskell/src/tip/sphere_approx/lit_sphere_thr.hs">Полный код</a> программы на данном этапе.<br /><br />Если вы не догадались, почему ничего не изображается, и что нужно сделать, чтобы это исправить, то можете прочитать <a href="http://bitbucket.org/yasir/haskell/src/tip/sphere_approx/lit_sphere_thr_final.hs">этот код</a>. В нем я установил постоянную интенсивность по зеленому каналу, чтобы можно было наблюдать также и неосвещенную сторону сферы, и изменил последнюю строчку в функции <code class="prettyprint lang-hs">tetrahedron</code>.<br /><br /><span style="font-weight:bold;">Заключение</span><br /><br />В статье была рассмотрена техника распараллеливания вычислений на языке Haskell, продемонстрировано использование привязки к OpenGL. Как говорит <a href="http://www.haskell.org/haskellwiki/Applications_and_libraries/Concurrency_and_parallelism#Concurrency">эта статья</a>, Haskell производит паралельные вычисления <a href="http://shootout.alioth.debian.org/gp4/benchmark.php?test=threadring&lang=all">очень быстро</a>.<br /><br />Надеюсь, вам понравилось.<br /><br /><span style="font-weight:bold;">Литература</span><br /><br />Эйнджел, Эдвард. Интерактивная компьютерная графика. Вводный курс на базе OpenGL, 2 изд.: Пер. с англ. — М.: Издательский дом "Вильямс", 2001. — 592 с.: ил. — Парал. тит. англ. ISBN 5-8459-0209-6 (рус.)<br /><br />P. S. Возможно, кто-то посоветует способ сокрытия под кат текста так, чтобы это действительно работало в т. ч. и на <a href="http://fprog.ru/planet/">Russian Lambda Planet</a>.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-1973090003148579772.post-5659114710002143052010-03-27T23:11:00.010+11:002010-03-28T04:06:38.871+11:00Распределенные математические вычисления на языке ErlangВ статье иллюстрируется пример настройки окружения и серверов для возможности проведения распределенных вычислений на языке Erlang, а также их осуществление. В качестве примера предлагается перемножение матрицы на вектор с использованием пула <a href="http://www.erlang.org/doc/man/pool.html">pool(3)</a> серверов Erlang. В данном случае пул состоит из 3 машин под управлением ОС FreeBSD.<br /><a name='more'></a><br /><br /><span style="font-weight: bold;">Введение</span><br />Многие из вас, наверняка, уже использовали вызов spawn[_link] в своих приложениях, но немногие, как я заметил, знают о более лаконичном -- но также и более функциональном -- его аналоге pspawn[_link]. Попробуем заполнить этот пробел, решив простую математическую задачу.<br /><br /><br /><span style="font-weight: bold;">Подготовка</span><br />Настройки серверов для хоста с двумя тюрьмами, расположенными на нем:<br /><pre style="background-color: black; color: rgb(255, 255, 255); font-weight: bold;">[root@conductor ~/crunching]# uname -prs<br />FreeBSD 7.1-RELEASE i386<br />[root@conductor ~/crunching]# grep '\.loc' /etc/hosts<br />192.168.32.40<br />192.168.32.201<br />192.168.32.202<br />[root@conductor ~/crunching]# jls<br />JID IP Address Hostname<br /> 1 192.168.32.201 j1.loc<br /> 2 192.168.32.202 j2.loc<br />[root@conductor ~/crunching]# ifconfig em0 | grep inet<br />inet 192.168.32.40 netmask 0xffffff00 broadcast 192.168.32.255<br />inet 192.168.32.201 netmask 0xffffff00 broadcast 192.168.32.201<br />inet 192.168.32.202 netmask 0xffffff00 broadcast 192.168.32.202<br />[root@conductor ~/crunching]# cat ~/.hosts.erlang<br />'j1.loc'<br />'j2.loc'<br />[root@conductor ~/crunching]# pkg_info -E erlang*<br />[root@conductor ~/crunching]#<br /></pre><br /><br />Запуск мастер-ноды poolmaster@conductor Erlang на хосте, затем запуск пула ведомых нод (slaves) в тюрьмах. Возвращение списка адресов машин, составляющих пул:<br /><pre style="background-color: black; color: rgb(255, 255, 255); font-weight: bold;">[root@conductor ~/crunching]# erl -sname poolmaster -rsh ssh<br />Erlang R13B01 (erts-5.7.2) [source] [rq:1] [async-threads:0] [hipe] [kernel-poll:false]<br /><br />Eshell V5.7.2 (abort with ^G)<br />(poolmaster@conductor)1> c(pwnd).<br />{ok,pwnd}<br />(poolmaster@conductor)2> pool:start(crunchpool).<br />[crunchpool@j1,crunchpool@j2]<br />(poolmaster@conductor)3> pool:get_nodes().<br />[poolmaster@conductor,crunchpool@j1,crunchpool@j2]<br />(poolmaster@conductor)4><br /></pre><br /><br />Удаленное подключение к shell Erlang-ноды, находящейся на другой машине (в данном случае -- в тюрьме), и исполнение произвольного кода:<br /><pre style="background-color: black; color: rgb(255, 255, 255); font-weight: bold;">[root@conductor ~/crunching]# erl -sname client -remsh crunchpool@j1<br />Erlang R13B01 (erts-5.7.2) [source] [rq:1] [async-threads:0] [hipe] [kernel-poll:false]<br /><br />Eshell V5.7.2 (abort with ^G)<br />(crunchpool@j1)1> os:cmd("hostname").<br />"j1.loc\n"<br />(crunchpool@j1)2><br /></pre><br /><br />На всех узлах пула (в т. ч. на ведущем (master)) запускаются Erlang Port Mapper Daemon (epmd(1)) и beam(1):<br /><pre style="background-color: black; color: rgb(255, 255, 255); font-weight: bold;"><br />[root@conductor ~] jexec 1 sockstat -4<br />USER COMMAND PID FD PROTO LOCAL ADDRESS FOREIGN ADDRESS<br />root beam 2863 7 tcp4 192.168.32.201:63037 *:*<br />root beam 2863 8 tcp4 192.168.32.201:50707 192.168.32.201:4369<br />root beam 2863 10 tcp4 192.168.32.201:54136 192.168.32.40:61473<br />root beam 2863 13 tcp4 192.168.32.201:63037 192.168.32.202:61991<br />root epmd 1143 3 tcp4 192.168.32.201:4369 *:*<br />root epmd 1143 4 tcp4 192.168.32.201:4369 192.168.32.201:50707<br />root inetd 861 5 tcp4 192.168.32.201:22 *:*<br />root sendmail 837 5 tcp4 192.168.32.201:25 *:*<br />root syslogd 777 6 udp4 192.168.32.201:514 *:*<br />[root@conductor ~] jexec 2 sockstat -4<br />USER COMMAND PID FD PROTO LOCAL ADDRESS FOREIGN ADDRESS<br />root beam 2880 7 tcp4 192.168.32.202:64315 *:*<br />root beam 2880 8 tcp4 192.168.32.202:57386 192.168.32.202:4369<br />root beam 2880 10 tcp4 192.168.32.202:50430 192.168.32.40:61473<br />root beam 2880 11 tcp4 192.168.32.202:61991 192.168.32.201:63037<br />root epmd 1160 3 tcp4 192.168.32.202:4369 *:*<br />root epmd 1160 4 tcp4 192.168.32.202:4369 192.168.32.202:57386<br />root inetd 1024 5 tcp4 192.168.32.202:22 *:*<br />root sendmail 1002 4 tcp4 192.168.32.202:25 *:*<br />root syslogd 942 6 udp4 192.168.32.202:514 *:*<br /></pre><br /><br />Запуск процесса распределенного вычисления, оканчивающегося выдачей результатов. Получение списка присоединенных нод, остановка пула, выход из Erlang shell:<br /><pre style="background-color: black; color: rgb(255, 255, 255); font-weight: bold;">(poolmaster@conductor)13> pwnd:vStart[[1,4,-2,1]], [9,1,11,1], [3,-3,5,1], [1,1,1,1]], [1,5,1,-3]).<br />ResL = [{module,pwnd},{module,pwnd},{module,pwnd}]<br />PIDS = [<0.141.0>,<8877.51.0>,<8838.51.0>,<0.142.0>]<br />poolmaster@conductor: [<0.141.0>/1] V1=[1,4,-2,1] * V2=[1,5,1,-3] == [16,0,0,0]<br />poolmaster@conductor: [<0.142.0>/4] V1=[1,1,1,1] * V2=[1,5,1,-3] == [0,0,0,4]<br />crunchpool@j1: [<8838.51.0>/3] V1=[3,-3,5,1] * V2=[1,5,1,-3] == [0,0,-10,0]<br />crunchpool@j2: [<8877.51.0>/2] V1=[9,1,11,1] * V2=[1,5,1,-3] == [0,22,0,0]<br />[16,22,-10,4]<br />(poolmaster@conductor)14> nodes().<br />[crunchpool@j1,crunchpool@j2]<br />(poolmaster@conductor)15> pool:stop().<br />stopped<br />(poolmaster@conductor)16> nodes().<br />[]<br />(poolmaster@conductor)17> q().<br />ok<br />(poolmaster@conductor)18><br />[root@conductor ~/crunching]#<br /></pre><br /><br />В примере выше задан ключ -rsh ssh, сообщающий Erlang VM, что доступ к другим нодам должен осуществляться по протоколу SSH. В этой демонстрации доступ к узлам производится по SSH с применением аутентификации через публичный ключ. Можно также использовать другие методы аутентификации, например, Kerberos. Мастер-нода автоматически запускает Erlang VM удаленно на каждом из ведомых узлов пула. Т. о. налицо простота ввода новых мощностей в кластер. В идеале можно было бы свести к минимуму объем работы по конфигурированию окружения (ОС, VM etc.) и построить кластер на основе diskless узлов, загружающихся через LAN Boot, тем самым повысив надежность.<br /><br />Исходя из последнего вывода на stdout смею предположить, что запуск (pspawn) процессов в пуле в отсутствие нагрузки происходит на разных серверах циклически (in a round-robin fashion), в противном случае учитывается загруженность каждого индивидуального вычислительного узла и производится балансировка нагрузки, т. е. запуск каждого нового процесса (именно Erlang процесса в Erlang VM, а не процесса ОС, aka "green process") на одном из наименее загруженных узлов пула.<br /><br /><br /><span style="font-weight: bold;">Исходный код</span><br /><pre style="background-color: black; color: rgb(51, 255, 51); font-weight: bold;">-module(pwnd).<br /><br />-export([startSay/0, say/2]).<br />-export([vSum/2, vMul/2, vVec/3, vStart/2, vSpawn/1,<br /> vReduce/2, vScatter/5, vWorker/1]).<br /><br />-import(lists).<br /><br />vSum([], []) -><br /> [];<br />vSum([H1 | T1], [H2 | T2]) -><br /> [H1 + H2] ++ vSum(T1, T2).<br /><br />vMul([], []) -><br /> [];<br />vMul([H1 | T1], [H2 | T2]) -><br /> [H1 * H2] ++ vMul(T1, T2).<br /><br />vVec(N, I, EL)-><br /> ZERO = lists:map(fun(X)->0*X end, lists:seq(1, N)),<br /> lists:sublist(ZERO, I - 1) ++<br /> [EL] ++ lists:sublist(ZERO, N - I).<br /><br />vWorker(PID) -><br /> receive<br /> {V1, V2, N} -><br /> P = vVec(length(V1),N,lists:sum(vMul(V1,V2))),<br /> io:format("~w: [~w/~w] V1=~w * V2=~w == ~w~n",<br /> [node(), self(), N, V1, V2, P]),<br /> PID ! {vector, P}<br /> end.<br /><br />vScatter([], _V, [], 0, _TOT) -><br /> [];<br />vScatter([MH | MT], V, [PID | REST], N, TOT) -><br /> PID ! {MH, V, TOT - N + 1},<br /> vScatter(MT, V, REST, N - 1, TOT).<br /><br />vReduce(RES, 0) -><br /> RES;<br />vReduce(RES, N) -><br /> receive<br /> {vector, V} -><br /> vReduce(vSum(RES, V), N - 1)<br /> end.<br /><br />vSpawn([]) -><br /> [];<br />vSpawn([_H | T]) -><br /> [pool:pspawn_link(<br /> pwnd,<br /> vWorker,<br /> [self()]<br /> )] ++ vSpawn(T).<br /><br />vStart(M, V) -><br /> % Distribute code<br /> {Mod, Bin, Filename} = code:get_object_code(?MODULE),<br /> {ResL, []} = rpc:multicall(<br /> code,<br /> load_binary,<br /> [Mod, Filename, Bin]<br /> ),<br /> io:format("ResL = ~w~n", [ResL]),<br /> ZERO = lists:map(fun(X)->0*X end,<br /> lists:seq(1, length(V))<br /> ),<br /> PIDS = vSpawn(lists:seq(1, length(V))),<br /> io:format("PIDS = ~w~n", [PIDS]),<br /> vScatter(M, V, PIDS, length(PIDS), length(PIDS)),<br /> vReduce(ZERO, length(V)).<br /></pre><br /><span style="font-weight: bold;">Заключение<br /></span>Таким образом, отредактировав всего пару конфигурационных файлов и заменив spawn на pspawn, мы получили гибкое распределенное приложение, способное реагировать на изменения кода.<br />Для повышения общей производительности есть много вариантов. Например, компиляция BEAM модулей с нативным кодом (HiPE, изначально являлся проектом Upsala University). На тестовой non-SMP одноядерной платформе на базе Celeron 2400 MHz производительность перемножения векторов с количеством элементов ~108 при запуске HiPE модуля увеличилась на 30%. Есть возможность использования портов и драйверов (<a href="http://www.erlang.org/doc/tutorial/c_portdriver.html">ports and linked-in drivers</a>) для запуска приложений, написанных на С и других языках. Можно задействовать <a href="http://en.wikipedia.org/wiki/BLAS">BLAS</a>. Есть и другие варианты оптимизации.<br /><br />Ниже, в коде, функция vStart/2 использует автоматический механизм передачи и загрузки модулей (двоичного кода) на узлы кластера. Поэтому отпадает необходимость при изменении программы распространять ее на каждую машину вручную. Кроме того в Erlang реализована возможность горячей замены кода (hotswap) без остановки выполнения приложения, при этом в памяти может существовать 2 версии модуля. Это позволяет существенно снизить или совсем исключить простои, которые являются необходимой мерой при разработке приложений, например, на С, Java и т. д. (<a href="http://www.erlang.org/doc/">подробнее</a>). Некоторые системы, написанные разными разработчиками на Erlang, работают годами и регулярно обновляются.<br /><br />В 2005 году был представлен проект ERESYE, позволяющий программировать Artificial Intelligence (искусственную разумность:) и экспертные системы в Erlang. Есть <a href="http://kingping.blinkenshell.org/Expert_system_in_Erlang__the_Domain_of_Transport.html">пример использования</a> этой технологии.<br /><br />Т. о. можно наблюдать преимущества функционального программирования в среде Erlang/OTP, в котором за долгую историю языка воплощено и продолжает активно внедряться множество продвинутых технологий, которым даже подражают другие языки, например, Scala (<a href="http://yarivsblog.com/articles/2008/05/18/erlang-vs-scala/">Erlang vs. Scala</a>) и т. д.<br /><br /><br /><span style="font-weight: bold;">Trivia</span><br />При загрузке кода в ваш редактор отступы могут сбиться. Для vim в командном режиме перейдите в начало файла (gg) и наберите на клавиатуре команду =G<br />Это откорректирует отступы.<br /><br /><br /><span style="font-weight: bold;">Источники</span><br /><ul><li><a href="http://plm.dia.uniroma3.it/milicchio/wp-content/uploads/2009/03/erlang-walkthrough.pdf">Giving a taste of a parallelization</a></li><li><a href="http://www.erlang.org/workshop/2008/Sess23.pdf">High performance technical computing with erlang</a><br /></li></ul>Unknownnoreply@blogger.com3