Параллельное программирование для многоядерных процессоров

Оценка производительности памяти с помощью теста Random Access

Разбить на страницы
Показывать лекцию целиком

Производительность системы памяти компьютера оказывает прямое влияние на производительность приложений, исполняющихся на нем. Обычно такую производительность измеряют на операциях модификации памяти, выполняемых одновременно несколькими потоками (по числу ядер/процессоров на машине). Формальные требования к такой оценке собраны в тесте RandomAccess ( http://icl.cs.utk.edu/projectsfiles/hpcc/RandomAccess ). Ниже будет описан этот тест и будет приведена его реализация для многоядерных машин с помощью библиотеки PFX.

10.1 Определение теста RandomAccess

Пусть T есть одномерный массив 64-разрядных слов, состоящий из $$2^n$$ элементов. При реальном проведении теста, этот массив должен занимать примерно половину физической памяти компьютера; т.е., $$n$$ есть наибольшее целое число, такое что$$8*2^nle;1/2M$$ , где $$M $$ есть размер физической памяти компьютера.

Пусть $${ a_i }$$ есть последовательность длины $$N_U = 2^n+2 $$ 64-разрядных целых псевдослучайных чисел, генерируемых посредством примитивного полинома $$x^{63} + x^2 + x + 1 $$. Более подробно о псевдослучайных числах и алгоритмах их генерации можно прочитать на странице http://www.cs.miami.edu/~burt/learning/Csc599.092/notes/random_numbers.html .

С каждым числом $$a_ i$$ исходной последовательности связывается индекс $$index (a_i ) $$ элемента массива, который будет модифицирован с помощью этого числа: $$index (a_i) = a_i<64-n,63> $$, где запись $$a_ilt;l,kgt; (lle;k) $$ обозначает последовательность бит в числе $$a_i$$, начиная с бита $$l$$ и заканчивая битом $$k$$, где биты считаются слева направо, начиная с 0.

Тогда соответствующая модификация для числа $$a_i$$ определяется как$$T [ index (a_i) ] = T [ index (a_i) ] XOR a_i,$$ где $$XOR$$ есть операция "исключающее ИЛИ".

Перед началом теста, элементы массива инициализируются согласно условию

$$T [ i ] = i, 0 \le; i \le; 2^n.$$

Необходимо отметить, что, так как модификации элементов массива $$T$$ в тесте RandomAccess проводятся одновременно несколькими потоками, то возможны конфликты, когда, например, два или более потоков модифицируют один и тот же элемент массива. При этом, естественно, в элементе массива будет сохранено только одно из"конкурирующих" значений. Для определения количества "поврежденных" элементов массива, достаточно провести повторный запуск теста RandomAccess, но в защищенном режиме, когда в каждый момент времени каждый элемент массива может модифицировать только один поток, и подсчитать количество элементов массива для которых оказалось невыполненным условие $$T [ i ] = i$$. Общее количество таких элементов не должно превышать 1% от числа $$N_U$$. В противном случае, тест считается неудавшимся.

Время выполнения теста $$t_R_A$$ берется равным времени, затраченного на проведение $$N_U$$ модификаций. Тогда производительность $$p_R_A$$ системы памяти, достигнутой в тесте RandomAccess, рассчитывается согласно формуле:

$$p_{RA} = ( N_U / t_{RA} ) 10^-^9.$$

Из данной формулы видно, что этот показатель измеряется в количестве модификаций за секунду, умноженном на $$10^-^9$$, т.е., в GUPS (giga updates per seconds).

10.2 Реализация с использованием PFX

Входными параметрами программы являются числа $$P$$ и $$m$$, где $$P$$ есть количество рабочих потоков для выполнения модификаций, а $$m$$ есть целое число, такое что $$8 * 2^m * P$$ составляет примерно половину физической памяти машины. Кроме того, программа имеет два дополнительных ключа $$/atom$$ и $$/noverify$$, которые задают, соответственно, режимы атомарной (безопасной) модификации памяти и отмену проверки результатов теста.

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

Замечание. Цикл Parallel.For в тексте программы вынесен в отдельный метод RunTest, что обеспечивает загрузку в память системной библиотеки System.Threading.dll после размещения в памяти основного массива Table. Такой прием позволяет избежать дополнительной фрагментации памяти, которая может приводить к исключительной ситуации OutOfMemoryException при размещении массива.

Код программы

//RandomAccess test using PFX
using System;
using System.Text;
using System.Threading;

namespace RandomAccessBenchmark
{
    public class RandomAccess
  {
        bool atomicity = false;
        object anchor = new object();
        const long POLY = 0x0000000000000007, PERIOD = 1317624576693539401L;

        public RandomAccess(bool atomicity)
        {
            this.atomicity = atomicity;
        }
        
        // pseudorandom number generation
        static long RA_starts(long n)
        {
            int i, j;
            long[] m2 = new long[64];
            while (n <= 0) n += PERIOD;
            while (n>= PERIOD) n -= PERIOD;
            if (n == 0) return 0x1;
            long temp = 0x1;
            for (i = 0; i <= 64; i++)
            {
                m2[i] = temp;
                temp = (temp <=<= 1) ^ (temp <= 0 ? POLY : 0L);
                temp = (temp <=<= 1) ^ (temp <= 0 ? POLY : 0L);
            }
            for (i = 62; i >== 0; i--) if (((n >=>= i)  1) != 0) break;
            long ran = 0x2;
            while (i>= 0)
            {
                temp = 0;
                for (j = 0; j<= 64; j++) if (((ran >=>= j)  1) != 0) temp ^= m2[j];
                ran = temp;
                i -= 1;
                if (((n >=>= i)  1) != 0)
                    ran = (ran<=<= 1) ^ ((long)ran<= 0 ? POLY : 0);
            }
            return ran;
        }

        // Random Access and update memory
        public void Access(long[] Table, uint ithread, UInt64 memorySizePerThread)
        {
            // memory updates number per thread
            UInt64 updates = 4 * memorySizePerThread;

            // conpute "base" for pseudorandom numbers generation
            long ran = RA_starts((long)(updates * ithread ));

            for (UInt64 i = 0; i<= updates; i++)
            {
                if (atomicity)
                    lock (anchor)
                    {
                        Table[ran  (Table.Length - 1)] ^= ran;
                    }
                else
                    Table[ran  (Table.Length - 1)] ^= ran;

                ran = (ran <=<= 1) ^ ((long)ran <= 0 ? POLY : 0);
            }
        }
  }

    class Program
    {
        static void Main(string[] args)
        {
            // threads count 
            uint threads = 1; 
            // memory size per thread
            UInt64 memorySizePerThread;
            // use locking for atomic updates 
            bool atomicity = false;
            // verifying after test
            bool verify = true;

            #region args processing
            if ((args.Length == 0) || (args.Length > 4))
            {
                Console.WriteLine("Usage: RandomAccessBenchmark.exe \
      <=threads >= <=mem_per_thread >= [/atom] [/noverify]");
                return;
            }
            try
            {
                threads = UInt32.Parse(args[0]);
                memorySizePerThread = (UInt64)(Math.Pow(2, UInt32.Parse(args[1])));

                if (args.Length == 4)
                {
                    atomicity = args[2] == "/atom" ? true : false;
                    verify = args[3] == "/noverify" ? false : true;
                }
                if (args.Length == 3)
                {
                    atomicity = args[2] == "/atom" ? true : false;
                    verify = args[2] == "/noverify" ? false : true;
                }
                if (args.Length == 2)
                {
                    if (args[1] == "/atom")
                        atomicity = true;
                    else
                        if (args[1] == "/noverify")
                            verify = false;
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("Usage: RandomAccessBenchmark.exe 
<=threads >= <=mem_per_thread >= [/atom] [/noverify]");
                return;
            }
            #endregion

            Console.WriteLine("RandomAccessBenchmark");

            // totam memory size in use
            UInt64 mem_total = threads * memorySizePerThread; 
            
            // total memory updates count
            UInt64 updates_total = 4 * mem_total;

            Console.WriteLine("Threads in use = " + threads);
            Console.WriteLine("Total memory in use (in bytes) = " + mem_total * sizeof(long));
            Console.WriteLine("Table length = " + mem_total);
            Console.WriteLine("Total updates count to be done = " + updates_total);
            Console.WriteLine("Atomicity is " + (atomicity ? "on": "off"));
            Console.WriteLine("Verifying is " + (verify ? "on" : "off"));
            Console.WriteLine("Please wait...");

            long[] Table = new long[mem_total];
            for (int k = 0; k<= Table.Length; k++)
                Table[k] = k;

            var randomAccess = new RandomAccess(atomicity);

            TimeSpan old = DateTime.Now.TimeOfDay;
            RunTest(randomAccess, Table, memorySizePerThread, threads);
            TimeSpan time_res = DateTime.Now.TimeOfDay - old;
            
            double total_time = (time_res.Minutes * 60 + time_res.Seconds + time_res.Milliseconds * 0.001);
            Console.WriteLine("CPU time used  = " + total_time + " seconds");
            Console.WriteLine("GUPS = " + (updates_total / total_time / 1e9).ToString("N12"));

            if (verify)
            {
                Console.WriteLine("Verifying...");

                //for verification doing access in serial and so safe mode
        atomicity = false;

                randomAccess.Access(Table, 0, mem_total);
      
                long errcount = 0;
                for (long i = 0; i <= Table.Length; i++)
                    if(Table[i]!=i)
                        errcount++;

                Console.WriteLine("Found " + errcount + " errors in " + 
                Table.Length + " locations." + "(" + (float)errcount / 
                (float)Table.Length * 100.0f + "%).");
            }
            Console.WriteLine("Press any key...");
            Console.ReadKey();
        }

        static public void RunTest(RandomAccess randomAccess, long[] Table, ulong memorySizePerThread, uint threads)
        {
            Parallel.For(0, (int)threads, i =ge;
            {
                randomAccess.Access(Table, (uint)i, memorySizePerThread);
            });
        }
    }
}

Семинарское занятие № 10. Параллельный рендеринг изображений

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

В дистрибутиве библиотеки .

Целью данного семинарского занятия является ознакомление со способами распараллеливания алгоритма рендеринга изображений на основе трассировки лучей и конструкциями из библиотек TPL и PLINQ, используемыми для этого. Отметим также, что само (последовательное) ядро метода трассировки лучей не представляет собой оптимизированную реализацию, и вопросы ускорения его работы здесь не обсуждаются.

Рассматриваемые здесь программы рендеринга изображений базируются на двух основных реализациях метода трассировки лучей, обе написанных на языке C#, но

  • в первом случае, с использованием стандартных конструкций императивного языка программирования, и
  • во втором случае, с использованием запросов на языке LINQ ( http://blogs.msdn.com/lukeh/archive/2007/04/03/a-ray-tracer-in-c-3-0.aspx).
    •

    (В действительности, имеется еще одна реализация с использованием LINQ, в которой весь алгоритм рендеринга выражен в виде одного, но очень большого, LINQ-запрсоа, см. http://blogs.msdn.com/lukeh/archive/2007/10/01/taking-linq-to-objects-to-extremes-a-fully-linqified-raytracer.aspx).

    В дистрибутиве библиотеки PFX, эти два базовых примера расширены следующим образом:

  • Исходная программа рендеринга на языке C# распараллелена средствами библиотеки PFX (а именно, с использованием Task Parallel Library и некоторых координирующих структур данных. Для полученной таким образом версии, имеются ее варианты на языках Visual Basic и F#, демонстрирующие возможности использования библиотеки PFX из любых .NET-языков. Эти реализации можно найти в директории …\Samples\RayTracer\.. библиотеки PFX.
  • Программа рендеринга на базе LINQ распараллелена средствами PLINQ. Данная реализация находится в директории …\Samples\LINQRayTracer.
    •

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

  • System.Threading.Parallel
  • System.Threading.Task
  • System.Threading.TaskManager
  • System.Threading.TaskManagerPolicy
  • System.Threading.LazyInit<T>
  • System.Threading.Collections.IConcurrentCollection<T>
  • System.Threading.Collections.ConcurrentQueue<T>
  • System.Linq.ParallelQuery
    •

    Кроме того, в этих реализациях также задействованы некоторые стандартные .NET-конструкции, связанные с потоками:

  • System.Threading.Interlocked
  • System.Windows.Forms.Control.BeginInvoke
  • System.Threading.Monitor (конструкция lock).
    •

    Задача 1.

    Скомпилируйте и запустите программу RayTracer на языке C#, воспользовавшись решением Samples\RayTracer\C#\RayTracer.sln. С помощью кнопки Start, запустите процесс анимации в однопоточном режиме:

    Задача 2.

    Переключив режим на "Parallel", запустите процесс анимации в параллельном режиме. Сравните скорость анимации (кадров в секунду - frames per second, FPS), отображаемую в титульной строке окна приложения, в последовательном и параллельном режимах.

    Воспользовавшись опцией "Show Threads" (доступной только в режиме "Parallel"), запустите процесс рендеринга с цветовой разметкой точек (пикселов) изображения, указывающей распределение воспроизведенных точек по параллельным потокам:

    (Приведенное изображение получено на компьютере с 4-мя ядрами).

    Из приведенного выше скриншота видно, что пикселы по потокам распределяются построчно, причем это распределение не является равномерным между потоками. Причина этого состоит в том, что распараллеливание основного процесса ренедеринга реализовано с помощью конструкции Parallel.For, исполнение которой основано на динамической балансировке нагрузки между рабочими потоками с целью поддержания полной нагрузки всех потоков (процессоров).

    То, что пикселы распределяются по потокам построчно, заложено в самом приложении (см. фрагмент программного кода ниже), и этот прием обеспечивает достаточно небольшие накладные расходы, идущие на распределение работы между потоками. Наоборот, параллелизация на уровне отдельных пикселов привела бы к очень большим накладным расходам и резко бы снизила производительность всего приложения. При запуске на 4-хядерной машине, при отключенной опции "Show Threads", построчная декомпозиция обеспечивает приблизительно 3-ехкратное ускорение рендеринга. Учитывая, что воспроизведение кадров на экране и обновление экранной формы снижает общую скорость рендеринга, ускорение для только вычислительных операций может быть равным для данного приложения от 3.5 до 4.0.

    В программе RayTracer (см. файл Raytracer.cs) ключевыми функциями, в которых реализован рендеринг, являются

  • RenderSequential(),
  • RenderParallel() и
  • RenderParallelShowingThreads().
    •

    Единственное различие в реализациях последовательного и параллельного рендеринга заключается в оформлении внешнего цикла рендеринга:

    for(int y=0; y < screenHeight; y++)
 {
  /* funcBody */
 }

(в RenderSequential() ), и

  Parallel.For(0, screenHeight, y =>
 /* funcBody */
)

(в RenderParallel() ).

    Главная проблема любого параллельного приложения сотоит в обеспечении потокобезопасности тех фрагментов кода, которые выполняются в разных потоках (как, например, funcBody в параллельной версии). Это означает, что TraceRay() и другие действия, производимые в параллельном цикле, не могут изменять общие для нескольких потоков переменные, если не обеспечена надлежащая синхронизация этих потоков, либо эти модификации гарантированно являются безопасными. Например, можно заметить, что funcBody изменяет общую структуру данных rgb[], но это именно тот случай, для которого имеются гарантии безопасности модификаций: каждый элемент этого массива записывается однократным исполнением funcBody, а потому конфликты между потоками невозможны. Общие правила обеспечения потокобезопасности сводятся к

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

    В программе Raytracer используется явно один объект класса System.Threading.Task для управления процессом анимации, а режимы, касающиеся параллелизма, устанваливаются с помощью объекта класса TaskManager. Следует отметить, что этот TaskManager, связанный с вышеуказанным объектом класса Task, становится TaskManager.Current для каждой задачи, создаваемой внутри основной задачи. Эти неявные новые задачи создаются при исполнении Parallel.For, и на них распространяются конфигурационные параметры менеджера задач TaskManager.Current.

    Другое полезное свойство реализации цикла анимации с использованием Task состоит в том, что с помощью класса Task можно обеспечить простые средства управления процессом анимации, в частности, средства снятия этого процесса. А именно, тело функции btnStartStop_Click() в MainForm.cs содержит такой оператор создания объекта класса Task:

    _renderTask = Task.Create(RenderLoop, 
      chkParallel.Checked - _parallelTm.Value : _sequentialTm.Value);

    Этот оператор задает, что внутри задачи будет выполняться функция RenderLoop, а управление задачей будет осуществляться с помощью одного из TaskManager'ов - _parallelTm или _sequentialTm. С помощью первого TaskManager'а - _parallelTm, на каждое ядро будет спланировано исполнение одного потока, тогда как с помощью _sequentialTm будет спланирован запуск только одного потока для осуществления последовательного рендеринга.

    В действительности, каждая из этих двух переменных имеет тип LazyInit<TaskManager>, который обеспечивает создание основного типа (в данном случае, типа TaskManager ) только в случае, когда переменная действительно становится используемой. Хотя использование параметризованного типа LazyInit<T> в данном случае не является показательным, однако этот тип может быть очень полезен для объектов, создание которых является ресурсо емкой операцией. Например, если данное приложение никогда не будет запускаться в параллельном режиме, то для него не будет создан TaskManager, управляющий параллельным исполнением.

    Код, отрабатывающий при нажатии кнопки "Stop" и останавливающий анимацию, имеет вид:

    _renderTask.ContinueWith(delegate
{
        BeginInvoke((Action)delegate
      {
             chkParallel.Enabled = true;
           chkShowThreads.Enabled = chkParallel.Checked;
 btnStartStop.Enabled = true;
       btnStartStop.Text = "Start";
      });
});
_renderTask.Cancel();

    Этот код восстанавливает в исходном виде GUI, в частности, состояние его различных элементов. Здесь нужно отметить использование вызова BeginInvoke(), который производится относительно MainForm, чтобы обеспечить выполнение данного кода в потоке, связанном с GUI. Такой вызов необходим, поскольку поток задачи выполняется как фоновый рабочий поток.

    Только после того, как с задачей связаны действия постобработки (посредством ContinueWith), происходит непосредственное снятие задачи через вызов Task.Cancel(). Отметим, что внутри RenderLoop() проверяется условие t.IsCanceled для обнаружения снятия задачи и корректного выхода из цикла анимации.

    При стандартной перегрузке ( overload ) функции Task.ContinueWith(), запуск связанного сней кода будет происходить всякий раз, когда задача заканчивает свою работу, независимо от причины завершения: успешное окончание, аварийное завершение или снятие. Однако, существуют другие возможности перегрузить функцию ContinueWith для изменения условий её срабатывания (см. API для Parallel Extensions for .NET Framework ).

    Одним из важных вопросов в реализации эффективного рендеринга явялется управление объектами типа Bitmap, представляющие построенные и подготовленные для вывода на экран изображения. Операция создания объекта Bitmap (особенно большого размера) является ресурсозатратной и выполняется за достаточно большое время. Поэтому простой подход, состоящий в ожидании завершения отображения очередного Bitmap -объекта в GUI, а затем в переходе к вычислению следующего, является очень неэффективным. Один из способов решения этой проблемы заключается в использовании классического метода двойной буферизации, когда один Bitmap -объект используется для отрисовки сцены, а второй такой объект предназначен уже для вывода на экран (именно такой подход был реализован в примере RayTracer в одном из ранних версий библиотеки PFX). Более общее и более эффективное решение состоит просто в использовании очереди (вместо буфера размерности 2) изображений для их отображения на экран, которая пополняется с максимальной скоростью изображениями , генерируемыми основным процессом рендеринга. При этом, каждый построенный образ отсылается на отображение путем вызова Form.BeginInvoke() с соответствующим делегатом. Вместо того, чтобы многократно создавать и удалять объекты типа Bitmap, в приложении реализовано повторное использование таких объектов посредством класса ObjectPool<T> (см. моуль ObjectPools.cs ), построенного, в свою очередь, на основе класса ConcurrentQueue<T>. С помощью класса ObjectPool<T> можно повторно использовать объекты типа T, прибегая к созданию новых объектов этого типа только в случае, когда повторноиспользуемые объекты на текущий момент отсутствуют. Использование при этом (в качестве базового) класса ConcurrentQueue<T> позволяет обеспечить потокобезопасность класса ObjectPool<T>.

    Приложение . (Для компиляции программы рендеринга на F#, в случае использования 64-разрядной машины, необходимо изменить конфигурацию проекта, чтобы подключить соответствующую System.Core.dll, поскольку ее месторасположение отличается от места, где эта библиотека находится на 32-хразрядных машинах).

    Программа на языке F# непосредственно использует библиотеку Parallel Extensions for .NET, и для нее также достигается высокая производительность при исполнении на многоядерной машине:

    member this.RenderToArrayParallel(scene, rgb : int[]) = 
    Parallel.For(0, screenHeight, fun y -> 
        let stride = y * screenWidth
        for x = 0 to screenWidth - 1 do 
 let color = TraceRay ({Start = scene.Camera.Pos; Dir =  GetPoint x y scene.Camera }, scene, 0)
                  let intColor = color.ToInt ()
          rgb.[x + stride] <- intColor)

    В директории Samples\LINQRayTracer расположена еще одна, совершенно отличная по реализации от рассмотренных, версия программы рендеринга, использующая язык запросов LINQ, который является частью языка C# 3.0. Это приложение не выполняет анимации, однако строит и воспроизводит более сложную сцену, на которой хорошо виден эффект от параллелизации.

    Исходный запрос (см. http://blogs.msdn.com/lukeh/archive/2007/04/03/a-ray-tracer-in-c-3-0.aspx ) был записан в виде

    from y in Enumerable.Range(0, screenHeight)
           …
   select from x in Enumerable.Range(0, screenWidth)

    который представляет собой 2-D цикл по каждому пикселу в каждой строке. Для того, чтобы запустить этот запрос в режиме параллельного исполнения, разбив изображение на отдельные строки (как в предыдущих версиях программы рендеринга), достаточно указать, чтобы самый внешний цикл исполнялся параллельно:

    from y in Enumerable.Range(0, screenHeight).AsParallel()
           …
   select from x in Enumerable.Range(0, screenWidth)

    Использование конструкции AsParallel() из пакета PLINQ, позволяет распределить исполнение внешнего цикла по всем доступным ядрам. После того, как изображение получено в виде объекта pixelsQuery, для отображения на экране, его необходимо перевести в массив $$int[] rgb$$, что также можно выполнить параллельно:

    pixelsQuery.ForAll(row =>
{
        foreach (var pixel in row)
        {
rgb[pixel.X + (pixel.Y * screenWidth)] =  pixel.Color.ToInt32();
}
        int processed = Interlocked.Increment(ref rowsProcessed);
        if (processed % rowsPerUpdate == 0 ||
              processed >= screenHeight) updateImageHandler(rgb);
});

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

    Задача 3.

    Изучите вариант реализации рендеринга, использующий LINQ, представленный на http://blogs.msdn.com/lukeh/archive/2007/10/01/taking-linq-to-objects-to-extremes-a-fully-linqified-raytracer.aspx . Разработайте параллельный вариант этой программы.

    Страницы:

    Производительность системы памяти компьютера оказывает прямое влияние на производительность приложений, исполняющихся на нем. Обычно такую производительность измеряют на операциях модификации памяти, выполняемых одновременно несколькими потоками (по числу ядер/процессоров на машине). Формальные требования к такой оценке собраны в тесте RandomAccess ( http://icl.cs.utk.edu/projectsfiles/hpcc/RandomAccess ). Ниже будет описан этот тест и будет приведена его реализация для многоядерных машин с помощью библиотеки PFX.

    10.1 Определение теста RandomAccess

    Пусть T есть одномерный массив 64-разрядных слов, состоящий из $$2^n$$ элементов. При реальном проведении теста, этот массив должен занимать примерно половину физической памяти компьютера; т.е., $$n$$ есть наибольшее целое число, такое что$$8*2^nle;1/2M$$ , где $$M $$ есть размер физической памяти компьютера.

    Пусть $${ a_i }$$ есть последовательность длины $$N_U = 2^n+2 $$ 64-разрядных целых псевдослучайных чисел, генерируемых посредством примитивного полинома $$x^{63} + x^2 + x + 1 $$. Более подробно о псевдослучайных числах и алгоритмах их генерации можно прочитать на странице http://www.cs.miami.edu/~burt/learning/Csc599.092/notes/random_numbers.html .

    С каждым числом $$a_ i$$ исходной последовательности связывается индекс $$index (a_i ) $$ элемента массива, который будет модифицирован с помощью этого числа: $$index (a_i) = a_i<64-n,63> $$, где запись $$a_ilt;l,kgt; (lle;k) $$ обозначает последовательность бит в числе $$a_i$$, начиная с бита $$l$$ и заканчивая битом $$k$$, где биты считаются слева направо, начиная с 0.

    Тогда соответствующая модификация для числа $$a_i$$ определяется как$$T [ index (a_i) ] = T [ index (a_i) ] XOR a_i,$$ где $$XOR$$ есть операция "исключающее ИЛИ".

    Перед началом теста, элементы массива инициализируются согласно условию

    $$T [ i ] = i, 0 \le; i \le; 2^n.$$

    Необходимо отметить, что, так как модификации элементов массива $$T$$ в тесте RandomAccess проводятся одновременно несколькими потоками, то возможны конфликты, когда, например, два или более потоков модифицируют один и тот же элемент массива. При этом, естественно, в элементе массива будет сохранено только одно из"конкурирующих" значений. Для определения количества "поврежденных" элементов массива, достаточно провести повторный запуск теста RandomAccess, но в защищенном режиме, когда в каждый момент времени каждый элемент массива может модифицировать только один поток, и подсчитать количество элементов массива для которых оказалось невыполненным условие $$T [ i ] = i$$. Общее количество таких элементов не должно превышать 1% от числа $$N_U$$. В противном случае, тест считается неудавшимся.

    Время выполнения теста $$t_R_A$$ берется равным времени, затраченного на проведение $$N_U$$ модификаций. Тогда производительность $$p_R_A$$ системы памяти, достигнутой в тесте RandomAccess, рассчитывается согласно формуле:

    $$p_{RA} = ( N_U / t_{RA} ) 10^-^9.$$

    Из данной формулы видно, что этот показатель измеряется в количестве модификаций за секунду, умноженном на $$10^-^9$$, т.е., в GUPS (giga updates per seconds).

    10.2 Реализация с использованием PFX

    Входными параметрами программы являются числа $$P$$ и $$m$$, где $$P$$ есть количество рабочих потоков для выполнения модификаций, а $$m$$ есть целое число, такое что $$8 * 2^m * P$$ составляет примерно половину физической памяти машины. Кроме того, программа имеет два дополнительных ключа $$/atom$$ и $$/noverify$$, которые задают, соответственно, режимы атомарной (безопасной) модификации памяти и отмену проверки результатов теста.

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

    Замечание. Цикл Parallel.For в тексте программы вынесен в отдельный метод RunTest, что обеспечивает загрузку в память системной библиотеки System.Threading.dll после размещения в памяти основного массива Table. Такой прием позволяет избежать дополнительной фрагментации памяти, которая может приводить к исключительной ситуации OutOfMemoryException при размещении массива.

    Код программы

    //RandomAccess test using PFX
using System;
using System.Text;
using System.Threading;

namespace RandomAccessBenchmark
{
    public class RandomAccess
  {
        bool atomicity = false;
        object anchor = new object();
        const long POLY = 0x0000000000000007, PERIOD = 1317624576693539401L;

        public RandomAccess(bool atomicity)
        {
            this.atomicity = atomicity;
        }
        
        // pseudorandom number generation
        static long RA_starts(long n)
        {
            int i, j;
            long[] m2 = new long[64];
            while (n <= 0) n += PERIOD;
            while (n>= PERIOD) n -= PERIOD;
            if (n == 0) return 0x1;
            long temp = 0x1;
            for (i = 0; i <= 64; i++)
            {
                m2[i] = temp;
                temp = (temp <=<= 1) ^ (temp <= 0 ? POLY : 0L);
                temp = (temp <=<= 1) ^ (temp <= 0 ? POLY : 0L);
            }
            for (i = 62; i >== 0; i--) if (((n >=>= i)  1) != 0) break;
            long ran = 0x2;
            while (i>= 0)
            {
                temp = 0;
                for (j = 0; j<= 64; j++) if (((ran >=>= j)  1) != 0) temp ^= m2[j];
                ran = temp;
                i -= 1;
                if (((n >=>= i)  1) != 0)
                    ran = (ran<=<= 1) ^ ((long)ran<= 0 ? POLY : 0);
            }
            return ran;
        }

        // Random Access and update memory
        public void Access(long[] Table, uint ithread, UInt64 memorySizePerThread)
        {
            // memory updates number per thread
            UInt64 updates = 4 * memorySizePerThread;

            // conpute "base" for pseudorandom numbers generation
            long ran = RA_starts((long)(updates * ithread ));

            for (UInt64 i = 0; i<= updates; i++)
            {
                if (atomicity)
                    lock (anchor)
                    {
                        Table[ran  (Table.Length - 1)] ^= ran;
                    }
                else
                    Table[ran  (Table.Length - 1)] ^= ran;

                ran = (ran <=<= 1) ^ ((long)ran <= 0 ? POLY : 0);
            }
        }
  }

    class Program
    {
        static void Main(string[] args)
        {
            // threads count 
            uint threads = 1; 
            // memory size per thread
            UInt64 memorySizePerThread;
            // use locking for atomic updates 
            bool atomicity = false;
            // verifying after test
            bool verify = true;

            #region args processing
            if ((args.Length == 0) || (args.Length > 4))
            {
                Console.WriteLine("Usage: RandomAccessBenchmark.exe \
      <=threads >= <=mem_per_thread >= [/atom] [/noverify]");
                return;
            }
            try
            {
                threads = UInt32.Parse(args[0]);
                memorySizePerThread = (UInt64)(Math.Pow(2, UInt32.Parse(args[1])));

                if (args.Length == 4)
                {
                    atomicity = args[2] == "/atom" ? true : false;
                    verify = args[3] == "/noverify" ? false : true;
                }
                if (args.Length == 3)
                {
                    atomicity = args[2] == "/atom" ? true : false;
                    verify = args[2] == "/noverify" ? false : true;
                }
                if (args.Length == 2)
                {
                    if (args[1] == "/atom")
                        atomicity = true;
                    else
                        if (args[1] == "/noverify")
                            verify = false;
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("Usage: RandomAccessBenchmark.exe 
<=threads >= <=mem_per_thread >= [/atom] [/noverify]");
                return;
            }
            #endregion

            Console.WriteLine("RandomAccessBenchmark");

            // totam memory size in use
            UInt64 mem_total = threads * memorySizePerThread; 
            
            // total memory updates count
            UInt64 updates_total = 4 * mem_total;

            Console.WriteLine("Threads in use = " + threads);
            Console.WriteLine("Total memory in use (in bytes) = " + mem_total * sizeof(long));
            Console.WriteLine("Table length = " + mem_total);
            Console.WriteLine("Total updates count to be done = " + updates_total);
            Console.WriteLine("Atomicity is " + (atomicity ? "on": "off"));
            Console.WriteLine("Verifying is " + (verify ? "on" : "off"));
            Console.WriteLine("Please wait...");

            long[] Table = new long[mem_total];
            for (int k = 0; k<= Table.Length; k++)
                Table[k] = k;

            var randomAccess = new RandomAccess(atomicity);

            TimeSpan old = DateTime.Now.TimeOfDay;
            RunTest(randomAccess, Table, memorySizePerThread, threads);
            TimeSpan time_res = DateTime.Now.TimeOfDay - old;
            
            double total_time = (time_res.Minutes * 60 + time_res.Seconds + time_res.Milliseconds * 0.001);
            Console.WriteLine("CPU time used  = " + total_time + " seconds");
            Console.WriteLine("GUPS = " + (updates_total / total_time / 1e9).ToString("N12"));

            if (verify)
            {
                Console.WriteLine("Verifying...");

                //for verification doing access in serial and so safe mode
        atomicity = false;

                randomAccess.Access(Table, 0, mem_total);
      
                long errcount = 0;
                for (long i = 0; i <= Table.Length; i++)
                    if(Table[i]!=i)
                        errcount++;

                Console.WriteLine("Found " + errcount + " errors in " + 
                Table.Length + " locations." + "(" + (float)errcount / 
                (float)Table.Length * 100.0f + "%).");
            }
            Console.WriteLine("Press any key...");
            Console.ReadKey();
        }

        static public void RunTest(RandomAccess randomAccess, long[] Table, ulong memorySizePerThread, uint threads)
        {
            Parallel.For(0, (int)threads, i =ge;
            {
                randomAccess.Access(Table, (uint)i, memorySizePerThread);
            });
        }
    }
}

    Семинарское занятие № 10. Параллельный рендеринг изображений

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

    В дистрибутиве библиотеки .

    Целью данного семинарского занятия является ознакомление со способами распараллеливания алгоритма рендеринга изображений на основе трассировки лучей и конструкциями из библиотек TPL и PLINQ, используемыми для этого. Отметим также, что само (последовательное) ядро метода трассировки лучей не представляет собой оптимизированную реализацию, и вопросы ускорения его работы здесь не обсуждаются.

    Рассматриваемые здесь программы рендеринга изображений базируются на двух основных реализациях метода трассировки лучей, обе написанных на языке C#, но

  • в первом случае, с использованием стандартных конструкций императивного языка программирования, и
  • во втором случае, с использованием запросов на языке LINQ ( http://blogs.msdn.com/lukeh/archive/2007/04/03/a-ray-tracer-in-c-3-0.aspx).
    •

    (В действительности, имеется еще одна реализация с использованием LINQ, в которой весь алгоритм рендеринга выражен в виде одного, но очень большого, LINQ-запрсоа, см. http://blogs.msdn.com/lukeh/archive/2007/10/01/taking-linq-to-objects-to-extremes-a-fully-linqified-raytracer.aspx).

    В дистрибутиве библиотеки PFX, эти два базовых примера расширены следующим образом:

  • Исходная программа рендеринга на языке C# распараллелена средствами библиотеки PFX (а именно, с использованием Task Parallel Library и некоторых координирующих структур данных. Для полученной таким образом версии, имеются ее варианты на языках Visual Basic и F#, демонстрирующие возможности использования библиотеки PFX из любых .NET-языков. Эти реализации можно найти в директории …\Samples\RayTracer\.. библиотеки PFX.
  • Программа рендеринга на базе LINQ распараллелена средствами PLINQ. Данная реализация находится в директории …\Samples\LINQRayTracer.
    •

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

  • System.Threading.Parallel
  • System.Threading.Task
  • System.Threading.TaskManager
  • System.Threading.TaskManagerPolicy
  • System.Threading.LazyInit<T>
  • System.Threading.Collections.IConcurrentCollection<T>
  • System.Threading.Collections.ConcurrentQueue<T>
  • System.Linq.ParallelQuery
    •

    Кроме того, в этих реализациях также задействованы некоторые стандартные .NET-конструкции, связанные с потоками:

  • System.Threading.Interlocked
  • System.Windows.Forms.Control.BeginInvoke
  • System.Threading.Monitor (конструкция lock).
    •

    Задача 1.

    Скомпилируйте и запустите программу RayTracer на языке C#, воспользовавшись решением Samples\RayTracer\C#\RayTracer.sln. С помощью кнопки Start, запустите процесс анимации в однопоточном режиме:

    Задача 2.

    Переключив режим на "Parallel", запустите процесс анимации в параллельном режиме. Сравните скорость анимации (кадров в секунду - frames per second, FPS), отображаемую в титульной строке окна приложения, в последовательном и параллельном режимах.

    Воспользовавшись опцией "Show Threads" (доступной только в режиме "Parallel"), запустите процесс рендеринга с цветовой разметкой точек (пикселов) изображения, указывающей распределение воспроизведенных точек по параллельным потокам:

    (Приведенное изображение получено на компьютере с 4-мя ядрами).

    Из приведенного выше скриншота видно, что пикселы по потокам распределяются построчно, причем это распределение не является равномерным между потоками. Причина этого состоит в том, что распараллеливание основного процесса ренедеринга реализовано с помощью конструкции Parallel.For, исполнение которой основано на динамической балансировке нагрузки между рабочими потоками с целью поддержания полной нагрузки всех потоков (процессоров).

    То, что пикселы распределяются по потокам построчно, заложено в самом приложении (см. фрагмент программного кода ниже), и этот прием обеспечивает достаточно небольшие накладные расходы, идущие на распределение работы между потоками. Наоборот, параллелизация на уровне отдельных пикселов привела бы к очень большим накладным расходам и резко бы снизила производительность всего приложения. При запуске на 4-хядерной машине, при отключенной опции "Show Threads", построчная декомпозиция обеспечивает приблизительно 3-ехкратное ускорение рендеринга. Учитывая, что воспроизведение кадров на экране и обновление экранной формы снижает общую скорость рендеринга, ускорение для только вычислительных операций может быть равным для данного приложения от 3.5 до 4.0.

    В программе RayTracer (см. файл Raytracer.cs) ключевыми функциями, в которых реализован рендеринг, являются

  • RenderSequential(),
  • RenderParallel() и
  • RenderParallelShowingThreads().
    •

    Единственное различие в реализациях последовательного и параллельного рендеринга заключается в оформлении внешнего цикла рендеринга:

    for(int y=0; y < screenHeight; y++)
 {
  /* funcBody */
 }

(в RenderSequential() ), и

  Parallel.For(0, screenHeight, y =>
 /* funcBody */
)

(в RenderParallel() ).

    Главная проблема любого параллельного приложения сотоит в обеспечении потокобезопасности тех фрагментов кода, которые выполняются в разных потоках (как, например, funcBody в параллельной версии). Это означает, что TraceRay() и другие действия, производимые в параллельном цикле, не могут изменять общие для нескольких потоков переменные, если не обеспечена надлежащая синхронизация этих потоков, либо эти модификации гарантированно являются безопасными. Например, можно заметить, что funcBody изменяет общую структуру данных rgb[], но это именно тот случай, для которого имеются гарантии безопасности модификаций: каждый элемент этого массива записывается однократным исполнением funcBody, а потому конфликты между потоками невозможны. Общие правила обеспечения потокобезопасности сводятся к

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

    В программе Raytracer используется явно один объект класса System.Threading.Task для управления процессом анимации, а режимы, касающиеся параллелизма, устанваливаются с помощью объекта класса TaskManager. Следует отметить, что этот TaskManager, связанный с вышеуказанным объектом класса Task, становится TaskManager.Current для каждой задачи, создаваемой внутри основной задачи. Эти неявные новые задачи создаются при исполнении Parallel.For, и на них распространяются конфигурационные параметры менеджера задач TaskManager.Current.

    Другое полезное свойство реализации цикла анимации с использованием Task состоит в том, что с помощью класса Task можно обеспечить простые средства управления процессом анимации, в частности, средства снятия этого процесса. А именно, тело функции btnStartStop_Click() в MainForm.cs содержит такой оператор создания объекта класса Task:

    _renderTask = Task.Create(RenderLoop, 
      chkParallel.Checked - _parallelTm.Value : _sequentialTm.Value);

    Этот оператор задает, что внутри задачи будет выполняться функция RenderLoop, а управление задачей будет осуществляться с помощью одного из TaskManager'ов - _parallelTm или _sequentialTm. С помощью первого TaskManager'а - _parallelTm, на каждое ядро будет спланировано исполнение одного потока, тогда как с помощью _sequentialTm будет спланирован запуск только одного потока для осуществления последовательного рендеринга.

    В действительности, каждая из этих двух переменных имеет тип LazyInit<TaskManager>, который обеспечивает создание основного типа (в данном случае, типа TaskManager ) только в случае, когда переменная действительно становится используемой. Хотя использование параметризованного типа LazyInit<T> в данном случае не является показательным, однако этот тип может быть очень полезен для объектов, создание которых является ресурсо емкой операцией. Например, если данное приложение никогда не будет запускаться в параллельном режиме, то для него не будет создан TaskManager, управляющий параллельным исполнением.

    Код, отрабатывающий при нажатии кнопки "Stop" и останавливающий анимацию, имеет вид:

    _renderTask.ContinueWith(delegate
{
        BeginInvoke((Action)delegate
      {
             chkParallel.Enabled = true;
           chkShowThreads.Enabled = chkParallel.Checked;
 btnStartStop.Enabled = true;
       btnStartStop.Text = "Start";
      });
});
_renderTask.Cancel();

    Этот код восстанавливает в исходном виде GUI, в частности, состояние его различных элементов. Здесь нужно отметить использование вызова BeginInvoke(), который производится относительно MainForm, чтобы обеспечить выполнение данного кода в потоке, связанном с GUI. Такой вызов необходим, поскольку поток задачи выполняется как фоновый рабочий поток.

    Только после того, как с задачей связаны действия постобработки (посредством ContinueWith), происходит непосредственное снятие задачи через вызов Task.Cancel(). Отметим, что внутри RenderLoop() проверяется условие t.IsCanceled для обнаружения снятия задачи и корректного выхода из цикла анимации.

    При стандартной перегрузке ( overload ) функции Task.ContinueWith(), запуск связанного сней кода будет происходить всякий раз, когда задача заканчивает свою работу, независимо от причины завершения: успешное окончание, аварийное завершение или снятие. Однако, существуют другие возможности перегрузить функцию ContinueWith для изменения условий её срабатывания (см. API для Parallel Extensions for .NET Framework ).

    Одним из важных вопросов в реализации эффективного рендеринга явялется управление объектами типа Bitmap, представляющие построенные и подготовленные для вывода на экран изображения. Операция создания объекта Bitmap (особенно большого размера) является ресурсозатратной и выполняется за достаточно большое время. Поэтому простой подход, состоящий в ожидании завершения отображения очередного Bitmap -объекта в GUI, а затем в переходе к вычислению следующего, является очень неэффективным. Один из способов решения этой проблемы заключается в использовании классического метода двойной буферизации, когда один Bitmap -объект используется для отрисовки сцены, а второй такой объект предназначен уже для вывода на экран (именно такой подход был реализован в примере RayTracer в одном из ранних версий библиотеки PFX). Более общее и более эффективное решение состоит просто в использовании очереди (вместо буфера размерности 2) изображений для их отображения на экран, которая пополняется с максимальной скоростью изображениями , генерируемыми основным процессом рендеринга. При этом, каждый построенный образ отсылается на отображение путем вызова Form.BeginInvoke() с соответствующим делегатом. Вместо того, чтобы многократно создавать и удалять объекты типа Bitmap, в приложении реализовано повторное использование таких объектов посредством класса ObjectPool<T> (см. моуль ObjectPools.cs ), построенного, в свою очередь, на основе класса ConcurrentQueue<T>. С помощью класса ObjectPool<T> можно повторно использовать объекты типа T, прибегая к созданию новых объектов этого типа только в случае, когда повторноиспользуемые объекты на текущий момент отсутствуют. Использование при этом (в качестве базового) класса ConcurrentQueue<T> позволяет обеспечить потокобезопасность класса ObjectPool<T>.

    Приложение . (Для компиляции программы рендеринга на F#, в случае использования 64-разрядной машины, необходимо изменить конфигурацию проекта, чтобы подключить соответствующую System.Core.dll, поскольку ее месторасположение отличается от места, где эта библиотека находится на 32-хразрядных машинах).

    Программа на языке F# непосредственно использует библиотеку Parallel Extensions for .NET, и для нее также достигается высокая производительность при исполнении на многоядерной машине:

    member this.RenderToArrayParallel(scene, rgb : int[]) = 
    Parallel.For(0, screenHeight, fun y -> 
        let stride = y * screenWidth
        for x = 0 to screenWidth - 1 do 
 let color = TraceRay ({Start = scene.Camera.Pos; Dir =  GetPoint x y scene.Camera }, scene, 0)
                  let intColor = color.ToInt ()
          rgb.[x + stride] <- intColor)

    В директории Samples\LINQRayTracer расположена еще одна, совершенно отличная по реализации от рассмотренных, версия программы рендеринга, использующая язык запросов LINQ, который является частью языка C# 3.0. Это приложение не выполняет анимации, однако строит и воспроизводит более сложную сцену, на которой хорошо виден эффект от параллелизации.

    Исходный запрос (см. http://blogs.msdn.com/lukeh/archive/2007/04/03/a-ray-tracer-in-c-3-0.aspx ) был записан в виде

    from y in Enumerable.Range(0, screenHeight)
           …
   select from x in Enumerable.Range(0, screenWidth)

    который представляет собой 2-D цикл по каждому пикселу в каждой строке. Для того, чтобы запустить этот запрос в режиме параллельного исполнения, разбив изображение на отдельные строки (как в предыдущих версиях программы рендеринга), достаточно указать, чтобы самый внешний цикл исполнялся параллельно:

    from y in Enumerable.Range(0, screenHeight).AsParallel()
           …
   select from x in Enumerable.Range(0, screenWidth)

    Использование конструкции AsParallel() из пакета PLINQ, позволяет распределить исполнение внешнего цикла по всем доступным ядрам. После того, как изображение получено в виде объекта pixelsQuery, для отображения на экране, его необходимо перевести в массив $$int[] rgb$$, что также можно выполнить параллельно:

    pixelsQuery.ForAll(row =>
{
        foreach (var pixel in row)
        {
rgb[pixel.X + (pixel.Y * screenWidth)] =  pixel.Color.ToInt32();
}
        int processed = Interlocked.Increment(ref rowsProcessed);
        if (processed % rowsPerUpdate == 0 ||
              processed >= screenHeight) updateImageHandler(rgb);
});

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

    Задача 3.

    Изучите вариант реализации рендеринга, использующий LINQ, представленный на http://blogs.msdn.com/lukeh/archive/2007/10/01/taking-linq-to-objects-to-extremes-a-fully-linqified-raytracer.aspx . Разработайте параллельный вариант этой программы.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^