Материал: Анализ эффективности функционального программирования на языке F# для многоядерных процессоров

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

Фату нашел, что орбита при этом преобразовании показывает достаточно сложное и интересное поведение. Существует бесконечное множество таких преобразований - своё для каждого значения. Основываясь на своих расчётах, он доказал, что орбита точки, лежащей на расстоянии больше 2 от начала координат, всегда уходит в бесконечность.

Фату никогда не видел изображений, которые мы сейчас знаем как изображения множества Мандельброта, потому что необходимое количество вычислений невозможно провести вручную. Профессор Бенуа Мандельброт был первым, кто использовал для этого компьютер.

Фракталы были описаны Мандельбротом в 1975 году в его книге «Les Objets Fractals: Forme, Hasard et Dimension» («Фрактальные объекты: форма, случайность и размерность») [24].

Фрактал (лат. fractus - дробленый, сломанный, разбитый) - сложная геометрическая фигура, обладающая свойством самоподобия, то есть составленная из нескольких частей, каждая из которых подобна всей фигуре целиком. В более широком смысле под фракталами понимают множества точек в евклидовом пространстве, имеющие дробную метрическую размерность (в смысле Минковского или Хаусдорфа), либо метрическую размерность, строго большую топологической [25].

Одной из идей, выросших из открытия фрактальной геометриим, была идея нецелых значений для количества измерений в пространстве. Конечно, мы не можем осознать четырехмерные вещи, хотя Lucky Tesseract и активно работает в этом направлении. Мандельброт назвал нецелые измерения такие как 2.76 фрактальными измерениями. Обыкновенная евклидова геометрия утверждает, что пространство ровное и плоское. Свойства такого пространства такого пространства задают точки, линии, углы, треугольники, кубы, сферы, тетраэдры и т. д.

Мандельброт верил, что действительный ландшафт пространства не ровный и что в нашем мире нет ничего, что было бы совершенно плоским, круглым, то есть все фрактально. Следовательно, объект, имеющий точно 3 измерения невозможен. Поэтому концепция фрактального измерения была нужна для измерения степени неровности вещей.

Первыми открытыми фракталами были т.н. детерминированные фракталы. Их отличительной чертой является свойство самоподобия, обусловленное особенностями метода их генерации.

Такие фракталы называются классическими, геометрическими фракталами или линейными фракталами. Эти фракталы обычно формируются начиная с инициатора - фигуры, к которой применяется определенный основной рисунок. Во всех детерминированных фракталах, само-подобие проявляется на всех уровнях. Это значит, что независимо от того насколько вы приближаете фрактал, вы увидите все тот же узор. Для сложных фракталов, которые будут рассмотрены позже, это не так. Детерминистские фракталы образуются в процессе, называемом итерацией, которая применяет основной рисунок к инициатору, после чего применяет его к результату и так далее. Из примеров можно выделить решетку Серпинского (рис. 8), фрактал Серпинского (рис. 9),крест Коха (рис. 10), фрактал Мандельброта (рис. 11), колбасу Минковского (рис. 12), пятиугольник Дарера (рис. 13), кривую Гильберта (рис 14), кривую Дракона (рис 15). Их фрактальные размерности находятся в пределах от 1.26 до 2.0.

Большая часть встречающихся сегодня фракталов не являются детерминированными. Они не линейны и не собраны из повторяющихся геометрических форм. Такие фракталы называются сложными. Если увеличить малую область фрактала до размера большей области то получатся два изображения, которые будут очень похожи в деталях, но они не будут полностью идентичными.

Детерминистские фракталы являются линейными, тогда как сложные фракталы таковыми не являются. Будучи нелинейными, эти фракталы генерируются нелинейными алгебраическими уравнениями.

Из самых известных недетерминированных фракталов можно выделить множества Мандельброта (рис. 16) и Жулиа (рис. 17).

Большинство фракталов, которые можно найти на сегодняшний день, представлены в богатой цветовой схеме. Возможно, фрактальные изображения получили такое большое эстетическое значение именно благодаря этой особенности. После того, как уравнение посчитано, начинается применение цвета. Если результаты остаются стабильными, или колеблются вокруг определенного значения, точка обычно принимает черный цвет. Если значение на том или ином шаге стремится к бесконечности, точку закрашивают в другой цвет, может быть в синий или красный. Во время этого процесса, компьютер назначает цвета для всех скоростей движения.

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

Наиболее полезным использованием фракталов в компьютерной науке является фрактальное сжатие данных. В основе этого вида сжатия лежит тот факт, что реальный мир хорошо описывается фрактальной геометрией. При этом, картинки сжимаются гораздо лучше, чем это делается обычными методами (такими как jpeg или gif). Другое преимущество фрактального сжатия в том, что при увеличении картинки, не наблюдается эффекта пикселизации (увеличения размеров точек до размеров, искажающих изображение). При фрактальном же сжатии, после увеличения, картинка часто выглядит даже лучше, чем до него.

Изучение турбулентности в потоках очень хорошо подстраивается под фракталы. Турбулентные потоки хаотичны и поэтому их сложно точно смоделировать. И здесь помогает переход к из фрактальному представлению, что сильно облегчает работу инженерам и физикам, позволяя им лучше понять динамику сложных потоков.

При помощи фракталов также можно смоделировать языки пламени.

Пористые материалы хорошо представляются в фрактальной форме в связи с тем, что они имеют очень сложную геометрию. Это используется в нефтяной науке.

Для передачи данных на расстояния используются антенны, имеющие фрактальные формы, что сильно уменьшает их размеры и вес.

Фракталы используются для описания кривизны поверхностей. Неровная поверхность характеризуется комбинацией из двух разных фракталов.

Биосенсорные взаимодействия и биения сердца в медицине.

Моделирование хаотических процессов, в частности при описании моделей популяций в биологии.

Применение фракталов в стеганографии и для шифрования данных.

Сегодня Мандельброт и другие ученые, такие как Клиффорд А. Пикковер (Clifford A. Pickover), Джеймс Глейк (James Gleick) или Г. О. Пейтген (H.O. Peitgen) пытаются расширить область фрактальной геометрии так, чтобы она могла быть применена практически ко всему в мире, от предсказания цен на рынке ценных бумаг до совершения новых открытий в теоретической физике [26].

Тем не менее и сама задача построения фракталов не завершилась а продолжила развитие в 3D-масштабах. Далее приведены примеры изображений, построенных с использованием фракталов.

Рис. 18 - 3D-изображения, построенные при помощи фракталов

Анализ эффективности параллельного программирования на F# для задачи обработки графического представления фрактальных функций

Задача графической реализации фрактального множества была выбрана не случайно, ведь, как и в большинстве задач по обработке изображений, в данной присутствует возможность для распараллеливания вычислений по данным. В программе было использовано распараллеливание по независимым рядам пикселей, что позволило равномерно распределить нагрузку между ядрами процессоров.

Для исследования эффективности использования языка F#, было реализовано 2D-изображение множества Мандельброта на 256 цветах в окне Windows. В качестве дополнительного функционала были реализованы такие функции как масштабирование окна, приближение и удаление картинки, восстановление первоначального приближения, перемещение по изображению.

Для тестирования было использовано следующее оборудование:Core 2 Duo, 2.4 Ghz, 3Mb Cache, 3Gb оперативной памяти, среда Visual Studio 2010 Ultimate, операционная система Microsoft Windows Vista Home Edition 32x.Intel Core i7, 2.6 Ghz, 6Mb Cache, 6Gb оперативной памяти, среда Visual Studio 2010 Ultimate, операционная система Microsoft Windows 7 Home Premium 64x.

Для тестирования исходное изображение десятикратно увеличивалось и сравнивалось время его перерисовки для языков F#, C++/CLR, C#.

Так выглядит окно программы после применения нескольких увеличений.

Рис. 19 - Окно программы Interactive Fractal

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

Результаты тестирования на первом оборудовании:

Рис. 20 - Скорость обработки пикселей на десяти шагах приближения для последовательной версии программы

Рис. 21 - Скорость обработки пикселей на десяти шагах приближения для параллельной версии программы

Рис. 22 - Коэффициент ускорения работы программы на десяти шагах приближения

Результаты тестирования на втором оборудовании:

Рис. 23 - Скорость обработки пикселей на десяти шагах приближения для последовательной версии программы

Рис. 24 - Скорость обработки пикселей на десяти шагах приближения для параллельной версии программы

Рис. 25 - Коэффициент ускорения работы программы на десяти шагах приближения

По полученным результатам можно сделать c выводы:

Результаты отличаются для двух- и четырехъядерных процессоров. Лучшие результаты язык F# показывает при тестировании параллельной версии программы на четырех ядрах.

Использование языка F# не дает выигрыша в скорости выполнения программы.

Так как все языки компилируются в CLI, результаты работы программы обработки изображения примерно одинаковы.# показывает лучший коэффициент ускорения на многоядерном процессоре, чем другие языки

В ряде тестов ускорение при работе нескольких ядер превышало их количество.

Проанализируем код программ для получения объяснения результатов эксперимента.

С++^ rrd = gcnew RenderImageData(position, width, height);(parallel)

{^options = gcnew ParallelOptions();>CancellationToken = cancellationToken;::For(0, rrd->ImageHeight, options, gcnew Action<int>(rrd, &RenderImageData::RenderRow));

}

{(int row = 0; row < rrd->ImageHeight; row++)

{.ThrowIfCancellationRequested();>RenderRow(row);

}

}

…= gcnew array<Byte>(Pixels);RenderRow(int row)

{initialY = row * RowToYTranslation + Top;(int col = 0, currentPixelIndex = row * ImageWidth; col < ImageWidth; col++, currentPixelIndex++)

{c = *(gcnew Complex(col * ColToXTranslation + Left, initialY));z = c;(int iteration = 0; iteration < MaxIterations; iteration++)

{(z.Magnitude > 4)

{[currentPixelIndex] = iteration;

break;

}= (z * z) + c;

}

}

}

Видно, что основные вычисления происходят в циклах по высоте изображения, ширине и количеству итераций для определения цвета точки. Для осуществления распараллеливания используется конструкция for класса Parallel библиотеки TPL. Также очевиден и недостаток такой реализации - все процессы обращаются к общей структуре, что теоретически допускает возможность конфликтов между записывающими потоками. Из неудобств написания программы нужно выделить отсутствие поддержки IntelliSense, необходимость инициализации и выделения памяти массиву данных до его использования.

C#(parallelRendering)

{options = new ParallelOptions { CancellationToken = cancellationToken };.For(0, imageHeight, options, row =>

{initialY = row * rowToYTranslation + top;(byte* ptr = data)

{* currentPixel = &ptr[row * imageWidth];(int col = 0; col < imageWidth; col++, currentPixel++)

{c = new Complex(col * colToXTranslation + left, initialY);z = c;(int iteration = 0; iteration < maxIterations; iteration++)

{(z.Magnitude > 4)

{

*currentPixel = (byte)iteration;;

}= (z * z) + c;

}

}

}

});

}

{(int row = 0; row < imageHeight; row++)

{.ThrowIfCancellationRequested();initialY = row * rowToYTranslation + top;(byte* ptr = data)

{* currentPixel = &ptr[row * imageWidth];(int col = 0; col < imageWidth; col++, currentPixel++)

{c = new Complex(col * colToXTranslation + left, initialY);z = c;(int iteration = 0; iteration < maxIterations; iteration++)

{(z.Magnitude > 4)

{

*currentPixel = (byte)iteration;

break;

}= (z * z) + c;

}

}

}

};

}

Этот же способ был реализован и на C#, что в конечном итоге приводит к тем же проблемам. Кроме того, используется unsafe(небезопасный) код с указателями. Из-за того большая часть кода повторяется дважды, программа становится громоздкой и неудобной для повторного использования. Повторное написание кода вызвано использованием многих переменных класса, т.е. состояния программы.

F#rec drawBit (z : Complex) c curIter =curIter withwhen x = maxIterations ->byte 0

|_ ->z withwhen x.Magnitude > 4.0 -> byte curIter

|_ -> drawBit (z*z+c) c (curIter+1)getbyte initialY j =.ThrowIfCancellationRequested()c = new Complex((float j) * colToXTranslation + left, initialY)c c 0data =parallelRendering then.Parallel.init imageHeight (fun i -> Array.init newImageWidth (fun j -> getbyte ((float i) * rowToYTranslation + top) j)).init imageHeight (fun i -> Array.init newImageWidth (fun j -> getbyte ((float i) * rowToYTranslation + top) j))

Версия на F# имеет следующие отличия:

Отсутствуют операторы присваивания, что автоматически устраняет проблему конфликта между процессами

Циклы заменяются рекурсией, которая, в силу того, что она «хвостовая» компилируется обратно в цикл

Легче производить функциональную декомпозицию, код становится короче

Параллельная версия отличается от последовательной одним словом

Отсутствует необходимость инициализировать массив до его заполнения, так как эти операции можно выполнить одновременно

Результаты эксперимента несколько различаются для 2х и 4х ядерного процессора, наиболее эффективно проявляет себя параллельная версия программы на 4х ядерном процессоре

В этом эксперименте также проявился эффект сверхлинейного ускорения - скорость работы программы при подключении двух и четырех ядер увеличивалась более чем в два и четыре раза соответственно. Это объясняется использованием общего кэша L2 на процессоре Core 2 Duo и L3 на процессоре i7. Можно выделить следующие преимущества систем с общим кэшем:

Увеличивается коэффициент использования кэша.

Уменьшается сложность согласования кэшей.

Уменьшается количество промахов кэша.

Уменьшается расход памяти - одни и те же данные для нескольких процессоров записываются единожды.

Уменьшается нагрузка на шину данных - проблемы доступа к данным разрешаются на уровне кэша [27].

Так как массив бит для изображения в памяти располагается линейно, то достигается высокий процент попаданий в кэш, что серьезно увеличивает производительность уже для двухъядерного процессора. Для четырехъядерного процессора это приводит к сверхлинейному ускорению, невозможному без участия кэша.

ЗАКЛЮЧЕНИЕ

В результате проделанной работы можно утверждать, что язык F# является эффективным .NET языком программирования для реализации параллельных вычислений или параллельной обработки данных. В эксперименте с умножением матриц по алгоритму Штрассена с использованием Z-порядка реализация на F# оказалась эффективней другого .NET языка C#. В эксперименте с оконным приложением для обработки изображения недетерминированного фрактала язык показал лучший коэффициент ускорения при переходе с одного ядра на четыре, при этом обеспечивая безопасный доступ потоков различных ядер к общим данным. Кроме того, возможности асинхронной работы потоков, интеграции с другими .NET приложениями, интерактивного выполнения кода, статическая типизация, функциональная основа делают его незаменимым инструментов в руках профессионального разработчика. Поддержка своих механизмов и библиотек .NET для параллельного программирования для многоядерных процессоров позволяет F# успешно конкурировать с другими мощными языками поддерживающими возможности параллельной разработки.