Программные продукты и системы

Параллельные вычисления особенно необходимы, когда задача требует высокой производительности компьютера. «Большие данные» (Big Data) становятся повседневной реальностью. Их обработка требует высокой производительности [1]. Распараллеливание по данным – один из главных приемов параллельного программирования, позволяющий ускорить обработку больших данных [2–4]. В данной работе анализируются результаты экспериментальных исследований, приводятся факты, выдвигаются гипотезы, даются рекомендации по организации распараллеливания по данным. О некоторых других проблемах параллельных вычислений при программировании на С# можно прочесть в [5–7].

Экспериментальные исследования представляют необходимый базис при построении математических основ параллельных вычислений [8].

Неоднозначная семантика: создание программного потока не приводит к созданию физического потока

Пусть в нашей программе есть цикл

for(int i = 0; i < N; i++)

   Body(i);

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

Если мы хотим управлять числом создаваемых в программе потоков – объектов класса Thread, то исходный цикл разумно разбить на два цикла, введя дополнительный параметр – число групп, на которые разбивается исходный интервал изменения параметра цикла. Причина такого разбиения понятна. Физическое создание N потоков явно неразумно при больших значениях N, поскольку накладные расходы на создание и удаление потоков могут не только свести на нет выигрыш от распараллеливания, но и ухудшить результаты.

Семантически эквивалентная замена исходного цикла двумя циклами сложнее одиночного цикла:

int m = N/k_group;

int groups = (N % k_group == 0) ? k_group : k_group + 1;

int start, finish;

for( int k = 0; k < groups; k++)

{

   start = k*m;

   finish = (start + m < N)? start + m : N;

   for(int i = start; i < finish; i++)

     Body(i)

}

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

int groups = (N % K_groups == 0)? K_groups : K_groups +1;

            Thread[] threads = new Thread[groups];

            for(int k = 0; k < groups; k++)

            {

                threads[k] = new Thread(Body);

                threads[k].Start(k);

            }

            for (int k = 0; k < groups; k++)

                threads[k].Join();

Метод Body, передаваемый конструктору каждого потока, выглядит следующим образом:

        void Body(object group)

        {

             int k = (int)group;

            int m = N / K_groups;

            int start = k * m;

             int gr = N % K_groups == 0 ? K_groups : K_groups + 1;

             int finish = (k != gr - 1) ? start + m - 1 : N - 1;

            BodyM(start, finish);

        }

Методу Body передается номер группы. Зная N и число групп, можно рассчитать начальный и конечный индексы группы, а затем вызвать метод BodyM, выполняющий итерации исходного цикла в заданном интервале.

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

Естественно, возникает ряд вопросов: каково оптимальное число групп? как влияет выбор на время вычислений? следует ли связывать это число с характеристиками компьютера, на котором будут производиться вычисления? Можно, например, предположить, что оптимальное значение параметра groups следует выбирать равным чис- лу виртуальных процессоров компьютера. Так верно ли то, что для компьютера с четырьмя ядрами, на каждом из которых одновременно можно запускать два потока, лучшие результаты достигаются, когда при распараллеливании в программе создаются восемь потоков – объектов класса Thread? Эксперименты опровергают это предположение.

Приведем результаты времени вычислений для задачи сортировки целочисленного массива, содержащего 200 000 элементов. Время работы последовательной версии Insert сортировки (сортировки вставкой) на таком массиве составило 64,9 секунды. Время работы параллельной версии в зависимости от числа групп (следовательно, от числа создаваемых программных потоков) приведено в таблице 1.

Таблица 1

Время сортировки массива в зависимости от уровня распараллеливания

Table 1

Array sorting time depending on paralleling level

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

Как показывают результаты вычислений, реализованный параллельный алгоритм позволил сократить время решения при правильно выбранном уровне распараллеливания более чем в 300 раз. Такое значительное ускорение является «странным» фактом и требует отдельного объяснения. Дело в том, что алгоритм сортировки вставкой имеет сложность O(N2). При сокращении размера массива в группе в k раз время сортировки одной группы сокращается в k2  раз. Конечно, из-за ограниченного числа физических потоков лишь немногие группы сортируются параллельно. Кроме того, приходится тратить время на слияние k отсортированных групп в единый отсортированный массив и, возможно, на создание k потоков. Тем не менее, как показывают результаты эксперимента, при обработке массива из 200 000 элементов алгоритмом с квадратичной сложностью можно получить значительный выигрыш при распараллеливании алгоритма.

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

Таблица 2

Время сортировки массива в зависимости от числа групп

Table 2

Array sorting time depending on group number

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

Более интересно рассмотреть два других «странных» факта, связанных с распараллеливанием:

−      оптимальное значение N достигается в точке N=400, что далеко от предполагаемого значения N=8 (число виртуальных процессоров компьютера);

−      при значениях N=20 000, что превосходит всякое «разумное» задание числа потоков для компьютера с четырьмя ядрами, время работы возрастает незначительно; это означает, что накладные расходы, связанные с созданием физических потоков, практически не появляются.

Гипотеза и рекомендации.

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

·       При работе с массивом программных потоков создание конструктором класса Thread элемента массива – объекта класса Thread не означает создание физического объекта – потока операционной системы.

·       Программный поток проецируется на существующий физический поток из пула потоков операционной системы.

·       Прямые наблюдения за числом потоков в диспетчере задач подтверждают эту гипотезу.

·       Для эффективного распараллеливания число программных потоков следует задавать намного больше числа виртуальных процессоров компьютера, на котором производятся вычисления. Если обозначить число виртуальных процессоров компьютера через V, то оптимальное число программных потоков равно k*V, где коэффициент k находится в диапазоне [10, 25].

·       Число создаваемых программных потоков не следует задавать больше k*V.

Неоднозначная семантика: создание программного потока приводит к созданию физического потока

Рассмотрена ситуация, когда в программе создается большой массив потоков. Но разрастание числа потоков необязательно связано с заданием массива потоков. Так, для рассматриваемой задачи сортировки массивов применяются методы сортировки со сложностью O(N*log N), которые, как правило, являются рекурсивными. В классическом последовательном варианте сортировки слиянием исходный массив разбивается пополам, и каждая часть сортируется независимо и рекурсивно. Отсортированные половинки сливаются в единый отсортированный массив. Алгоритм допускает естественное распараллеливание. Для сортировки половинок создаются два потока, каждая из половинок сортируется в своем потоке. Из-за рекурсии число потоков растет экспоненциально с ростом уровня рекурсии. Экспоненциальный рост следует ограничить. Для ограничения возрастания числа потоков можно применить следующий подход: новые потоки не создавать, когда длина сортируемого массива становится меньше заданной величины Limit.

Рассмотрим задачу сортировки целочисленного массива, содержащего 10 миллионов элементов. В последовательном варианте применялся классический рекурсивный алгоритм сортировки слиянием. Время работы последовательной версии на таком массиве составило 4,2 секунды. Заметьте, на больших массивах последовательный алгоритм сортировки слиянием существенно выигрывает не только у последовательного, но и у параллельного алгоритма сортировки вставкой.

В параллельном варианте сортировки слиянием рост числа потоков ограничивался, как было сказано, введением константы Limit. Результаты эксперимента приведены в таблице 3.

Таблица 3

Время сортировки массива методом слияния в зависимости от уровня распараллеливания

Table 3

Array sorting time by merging depending on paralleling level

Гипотеза и рекомендации.

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

·       Прямые наблюдения за числом потоков в диспетчере задач подтверждают эту гипотезу.

·       Программные потоки следует создавать только на верхних уровнях рекурсии. Для нашего алгоритма оптимальный уровень рекурсии p, на котором следует прекратить создание потоков, можно вычислить из соотношения 2p=V, где V – число виртуальных процессоров.

·       Если разумным способом не ограничить создание потоков, то можно не только проиграть во времени вычислений в сравнении с последовательным вариантом, но и не получить решение из-за возникновения исключительной ситуации – выхода за пределы допустимой памяти при создании новых потоков. В данном эксперименте такая ситуация возникает при значении Limit, равном 1 000.

·       При оптимальном задании уровня распараллеливания параллельный алгоритм выигрывает у последовательного алгоритма: время сокращается примерно в три раза. Не столь эффективное распараллеливание, как в случае алгоритма сортировки методом вставки, объясняется двумя факторами: сортировка слиянием имеет сложность, близкую к линейной, поэтому здесь не достигается выигрыш на подзадачах, характерный для алгоритма со сложностью O(N2); добавляются накладные расходы, связанные с созданием физических потоков.

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

Экспериментальная проверка гипотез и рекомендаций требует проведения более широких исследований. В качестве первого шага рассмотрим два других алгоритма сортировки: алгоритм пузырьковой сортировки со сложностью O(N2) и алгоритм быстрой сортировки со средней сложностью O(N*log N) (табл. 4).  

Таблица 4

Сравнение пузырьковой сортировки и сортировки вставкой

Table 4

Comparison of bubble sort and insertion sort

Для обоих методов оптимальное значение достигается в одной и той же точке (число групп N=400). Оба графика имеют одну и ту же тенденцию, подтверждающую ранее сделанные выводы. Можно лишь заметить, что распараллеливание для пузырьковой сортировки дает больший эффект, чем для сортировки вставкой. Так, для последовательных вариантов «пузырек» проигрывает «вставке» в три раза, а при оптимальном распараллеливании время сортировки обоими методами уравнивается.

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

Справедливы ли утверждения для рекурсивных методов, когда потоки создаются внутри работающего потока? Рассмотрим еще один, наиболее употребляемый рекурсивный метод быстрой сортировки Хоара. Результаты экспериментов, позволяющие сравнить два параллельных варианта сортировки массива из 10 миллионов элементов, приведены в таблице 5.

Таблица 5

Сравнение сортировки слиянием и быстрой сортировки

Table 5

Comparison of sorting by merging and quick sort

Как всегда, сортировка Хоара и в параллельном варианте выигрывает у всех своих конкурентов. Но тенденции зависимости времени сортировки от уровня распараллеливания для обоих методов одинаковы и оптимум достигается в одной и той же точке, когда число потоков равно 8, что в данном случае совпадает с числом виртуальных процессоров компьютера.

Некорректная работа анонимных методов в потоках

Анонимные методы – мощный и полезный механизм. Это константы в мире методов. Потоку в момент его создания необходимо передать метод, выполняемый потоком. Крайне удобно во многих ситуациях задавать именно константный, анонимный метод. Помимо прочего, это позволяет преодолевать синтаксические ограничения, накладываемые на метод, передаваемый потоку. Такой метод, как известно, должен быть процедурой без параметров или иметь один параметр универсального типа Object. При использовании анонимного метода эти ограничения легко обходятся.

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

Пример некорректного анонима при работе с объектами класса Thread

Для подтверждения факта некорректной работы анонимного метода в потоках автором сконструирован достаточно простой пример. Создается массив из N потоков. При создании потока с номером k ему передается анонимный метод, который добавляет целое число k в элемент массива с номером k. При корректной работе сумма элементов этого массива равна N*(N–1)/2.

Текст этого метода:

        ///

        /// Потоки с анонимным методом

        /// Пример некорректной работы

        ///

        /// true при корректной работе

        public bool Test_ThreadsWithAnonym()

        {

            threads = new Thread[N];

            for (int i = 0; i < N; i++)

                mas[i] = 0;

            for (int k = 0; k < N; k++)

            {

                threads[k] = new Thread(() =>

                {

                    mas[k] += k;

                });

                threads[k].Start();

            }

            for (int i = 0; i < N; i++)

                threads[i].Join();

            double S = 0;

            for (int i = 0; i < N; i++)

                S += mas[i];

            return S - N * (N - 1) / 2.0 < 1e-7;

        }

При запуске этого примера проявляются ошибки двух типов.

1. Некоторые элементы массива не заполняются. Это означает, что некоторые потоки threads[i] не создаются. С другой стороны, некоторые потоки threads[i] создаются дважды (как правило, соседние с пропущенными потоками), так что элементы массива получают удвоенное значение. Такой эффект, например, наблюдался при задании N равным 10 000. При малых значениях N, как правило, элементы заполняются корректно.

2. К счастью (или к несчастью), возникает еще и исключительная ситуация – индекс выходит за допустимые пределы. Это означает, что некорректно работает условие окончания цикла.

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

        public bool Test_ThreadsWithNamedMethods()

        {

            threads = new Thread[N];

            for (int i = 0; i < N; i++)

                mas[i] = 0;

            for (int k = 0; k < N; k++)

            {

                threads[k] = new Thread(Cort);

                threads[k].Start(k);

            }

            for (int i = 0; i < N; i++)

                threads[i].Join();

            double S = 0;

            for (int i = 0; i < N; i++)

                S += mas[i];

            return S - N * (N - 1) / 2.0 < 1e-7;

        }

        void Cort(object par)

        {

            int k = (int)par;

            mas[k] += k;

        }

Используем для распараллеливания прекрасный метод Parallel.For:

         ///

        /// Parallel.For с анонимным методом

        /// Работает корректно в тестируемых примерах

        ///

        /// true при корректной работе

        public bool Test_ParallelWithAnonym()

        {

            for (int i = 0; i < N; i++)

                mas[i] = 0;

            Parallel.For(0, N, (k) =>

            { mas[k] += k; });

            double S = 0;

            for (int i = 0; i < N; i++)

                S += mas[i];

            return S - N * (N - 1) / 2.0 < 1e-7;

        }

В данном примере для всех протестированных значений N метод Parallel.For в сочетании с анонимным методом работал корректно. К сожалению, это происходит не всегда.

Пример некорректного анонима  при работе Parallel.For

Для демонстрации некорректной работы Parallel.For в сочетании с анонимным методом пришлось сконструировать более сложный и вместе с тем более реалистичный пример. Рассмотрим задачу умножения квадратных матриц с той особенностью, что два внешних цикла по строкам и столбцам сворачиваются в один цикл, который и распараллеливается. На этом примере Parallel.For, использующий анонимный метод, «ломается». Приведем текст метода:

         ///

        /// Умножение матриц

        /// Метод Parallel.For используется для распараллеливания цикла,

        /// представляющего свертку циклов по строкам и столбцам

        /// результирующей матрицы D

        ///

        public void Mult_Par_Test()

        {

            int i = 0, j = 0;

            Parallel.For(0, N * N, (q) =>

                {

                    i = q / N;

                    j = q % N;

                    D[i, j] = 0;

                    for (int k = 0; k < N; k++)

                        D[i, j] += A[i, k] * B[k, j];

                });

        }

Для малых значений N (например N=5) метод, как правило, работает корректно. С увеличением N результаты вычислений неверны, но работа метода заканчивается без возникновения исключительных ситуаций.

На основании проведенных экспериментов можно сделать следующие выводы.

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

Если метод обработки не предполагает ре- курсию, для распараллеливания наряду с классом Parallel можно использовать и массив потоков – объектов класса Thread. Как показывают исследования, создание элементов этого массива – программных потоков не приводит к созданию физических потоков. Как следствие, оптимальное для распараллеливания число групп должно намного превышать число виртуальных процессоров компьютера.

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

При распараллеливании весьма удобным является механизм анонимных методов. К сожалению, как показывают проведенные исследования, взаимодействие этих двух важных механизмов может приводить к некорректной работе. Поэтому в настоящее время анонимный метод не следует использовать при организации параллельных вычислений на C#. Можно, конечно, надеяться, что в следующих после 13-й версиях Visual Studio некорректная совместная работа двух важных механизмов будет исправлена.

Литература

1.     Воеводин В.В., Воеводин Вл.В. Параллельные вычисления». СПб: БХВ-Петербург, 2002. 608 с.

2.     Антонов А.С. Технологии параллельного программирования MPI и Open MP: учеб. пособие. М.: Изд-во МГУ, 2012. 344 с.

3.     Гергель В.П. Высокопроизводительные вычисления для многопроцессорных многоядерных систем. М.: Изд-во МГУ, 2010. 544 с.

4.     Chapman B., Jost G., Ruud van der Pas. Using Open MP: portable shared memory parallel programming, Cambridge, MIT, 2008.

5.     Биллиг В.А. Параллельные вычисления и многопоточное программирование. М.–Тверь: ИНТУИТ–ЗАО НИИ ЦПС, 2013. 346 с.

6.     Биллиг В.А. Основы объектного программирования на С#. М.: ИНТУИТ–Бином. Лаборатория знаний, 2010.

7.     Параллельные вычисления на C#. URL: www.Coding­craft.ru (дата обращения: 15.03.2015).

8.     Воеводин В.В. Математические основы параллельных вычислений. URL: www.ict.edu.ru/ft/005115/math_parallel.pdf (дата обращения: 15.03.2015).