А И Рязанцев, Е В Щербаков, М Е Щербакова - Векторное распараллеливание серверной обработки данных - страница 1

Страницы:
1 

УДК 681.518

Рязанцев А.И., Щербаков Е.В., Щербакова М.Е.

ВЕКТОРНОЕ РАСПАРАЛЛЕЛИВАНИЕ СЕРВЕРНОЙ ОБРАБОТКИ ДАННЫХ

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

Введение.

Одним из наиболее важных средств повышения производительности систем обработки данных является векторное распараллеливание вычислительного процесса [1, 2]. При векторном расспараллеливании существенно ускоряется решение задач линейной алгебры, дифференциальных уравнений в частных производных, задачи статистической обработки данных и некоторые другие задачи.

В языке программирования C++ и производных от него языков для векторной обработки массивов данных используется шаблон классов valarray [3, 4]. Основным преимуществом этого шаблона является эффективность проведения одинаковых операций сразу над всеми элементами векторов, что является следствием агрессивной оптимизации, которую компиляторы языков программирования выполняют при использовании операций над этими типами данных. Стандартный шаблон valarray с использованием вспомогательных механизмов, таких как срезы, обобщённые срезы, маски или косвенные массивы, позволяет выполнять операции над подмножествами элементов векторов. Но использование этих механизмов затруднено из-за их нетрадиционного синтаксиса и приводит к сложным алгоритмическим и программным конструкциям. Их очень сложно использовать для регулярной векторной обработки по ветвящимся алгоритмам.

На серверах сети Интернет, серверах компьютерных систем управления и серверах баз данных [5, 6] также решаются задачи обрабатки больших массивов однотипных данных. Примерами таких задач могут служить задачи авторизации и аутентификации, задачи обработки массово поступающих на сервер заявок на обработку графической и текстовой информации, в частности, запросов на обработку веб-страниц, задачи первичной переработки технологических данных в системах управления технологическими процессами. Но, в отличие от перечисленных в начале статьи задач, обработка данных в таких задачах производится по ветвящимся алгоритмам в зависимости от условий, задаваемых статически на этапе конфигурирования или возникающих в вычислительной сети в произвольные моменты времени и влияющих на обработку каждого элемента массивов данных в отдельности.

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

Основная часть.

Для преодоления перечисленных недостатков предлагается специальный шаблон классов vcarray, который содержит как подмножество все операции стандартного шаблона valarray из библиотеки STL C++, но обеспечивает возможность ветвления векторной обработки данных. Кроме того, реализация нового шаблона vcarray обеспечивает более быстрое выполнение векторных операций по сравнению с выполнением этих же операций стандартным шаблоном valarray в его реализации фирмой Microsoft в рамках Visual Studio 2008.

Внешне объявление шаблона vcarray выглядит практически так же, как и объявление стандартного библиотечного шаблона valarray. В нем помимо одноместных и двуместных операторов, являющихся членами шаблона классов vcarray, реализован также полный набор трехместных операторов, которые не являются членами шаблона классов, и определены в ранге функций - помощников шаблона vcarray. Хотя синтаксис одноместных, двуместных и трёхместных операторов шаблона vcarray практически совпадает с синтаксисом этих же операторов для valarray, их семантика и реализация существенно отличаются. Чтобы обеспечить выборочную обработку элементов векторов в зависимости от динамически вырабатываемых векторных условий, все арифметические, логические операции и операции сравнения выполняются только для тех элементов векторов, индексы которых перечислены в текущем векторе ветвления. Текущий вектор ветвления формируется специальными функциями, речь о которых пойдет ниже. Эти функции добавляют в специальный массив (вектор ветвления) индексы элементов, соответствующих заданному условию, и в конце дописывается количество удовлетворяющих условию элементов. Текущий вектор ветвления всегда размещается на вершине специального управляющего массива, организованного по стековому принципу и предназначенного для хранения векторов ветвления, в общем случае, разной размерности (рис. 1).

I Указатель на первый элемент текущего вектора ветвления

n0=sizeof(BV[0])/sizeof(int) _BV[0][0]_

BV[0][n0-1]

n0=sizeof(BV[0])/sizeof(int) n1=sizeof(BV[1])/sizeof(int) _BV[1][0]_

BV[1][n1-1]

n1=sizeof(BV[1])/sizeof(int)

nk=sizeof(BV[k])/sizeof(int) _BV[k][0]_

BV[k][1]

BV[k][nk-1]

nk=sizeof(BV[k])/sizeof(int)

It

Рис. 1 Специальный массив для управления ветвлениями при обработке векторов

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

Разработанный шаблон классов vcarray, как показало тестирование, значительно превосходит по скорости выполнения почти всех операций стандартный шаблон классов valarray в его реализации в рамках Microsoft Visual Studio 2008. На гистограмме, представленной на рис. 2, показано время выполнения различных операций шаблонами vcarray и valarray. Тестирование проводилось на процессоре Intel Pentium 4 с тактовой частотой 2.4 ГГц.

Рис. 2 Сравнение скорости выполнения операций различными средствами обработки векторов

Шаблон vcarray построен так, что все арифметические операции выполняются над элементами, индексы которых входят в текущий вектор ветвления. Изначально это вектор ветвления, куда входят все элементы последовательности. Условные операторы -VcarrayIf(vcarray<bool>), VcarrayElse, операторы повторения - VcarrayWhile(vcarray<bool>) -EndVcarrayWhile, VcarrayDo - VcarrayDoWhile(vcarray<bool>) формируют новый вектор ветвления, ивнутри них обрабатываются лишь элементы последовательности, удовлетворяющие условию (входящие в vcarray<bool>). Инструкция EndVcarrayIf, а также инструкции завершения циклов удаляют последний вектор индексов, и происходит возвращение к предыдущему вектору индексов, с которым работали до начала цикла (условного оператора). Таким образом можно строить ветвящуюся обработку векторов любой степени вложенности - каждый цикл и условный оператор будет добавлять в специальный стек новый вектор индексов, а по его завершении этот вектор индексов будет удаляться. Стандартный шаблон valarray вообще не позволяет делать вложенную выборочную обработку.

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

Лемма 1. Для шаблона vcarray возможности векторных операторов присваивания с арифметическими и логическими векторными выражениями, отнесенные к одному индексу элементов обрабатываемых векторов, полностью соответствуют их скалярным аналогам - оператору присваивания и выражениям языка C++.

Действительно, для шаблона vcarray обеспечивается функционально полный набор одноместных, двуместных и трёхместных арифметических, логических операторов и операторов сравнения таких же, как и для шаблона valarray. Из этого следует, что с помощью шаблона vcarray для всех участвующих в операциях элементов векторов с одинаковыми индексами реализуются операторы присваивания с выражениями с правой стороны оператора "=", включающими любые операции и, при необходимости, неограниченное число возможно вложенных друг в друга подвыражений, ограниченных круглыми скобками, точно так же, как и при их скалярной обработке.

Лемма 2. Для шаблона vcarray ветвление векторной обработки по индивидуальным условиям для каждого из индексов элементов обрабатываемых векторов выполняется точно так же, как если бы элементы векторов обрабатывались скалярным алгоритмом с использованием оператора "if () {} else {}".

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

Рис. 3. Векторная реализация условия if () {}

То же относится к инструкции VcarrayIf() {} VcarrayElse {}. Инструкция VcarrayElse заменяет текущий вектор ветвления новым, с индексами, которых не было в заменяемом векторе. Вариант для инструкции if() {} else {} приведен на рис. 4. Из него видно, что, по аналогии с инструкцией if() {}, текст с использованием векторной обработки вполне можно заменить скалярной обработкой, как показано на рис. 4 справа.

for (i=0; i<N; {.

if (sbExpr[i]) {

// последовательность // инструкций S1

}

else

{

// последовательность // инструкций S2 }

}

Рис. 4. Векторная реализация условия if() {} else {}

Лемма 3. Для шаблона vcarray циклы VcarrayWhile(vcarray<bool>) - EndVcarrayWhile; VcarrayDo -VcarrayDoWhile(vcarray<bool>) выполняются так же, как если бы каждый элемент вектора обрабатывался в отдельном цикле while() или do - while(), где условием выполнения цикла была бы проверка, удовлетворяет ли элемент вектора какому-то логическому условию.

В самом деле, циклы VcarrayWhile(vcarray<bool>) - EndVcarrayWhile; VcarrayDo -VcarrayDoWhile(vcarray<bool>) при каждой итерации заменяют текущий вектор индексов новым, куда записываются номера элементов, удовлетворяющих условию выполнения цикла. Все операции в цикле проводятся только для элементов из последнего вектора индексов; а так как цикл выполняется, пока условие выполняется хотя бы для 1 элемента, значит это то же самое, как если бы цикл выполнялся для каждого элемента вектора отдельно. Примеры векторной и обычной, скалярной, обработки последовательностей чисел в цикле приведены на рис. 5.

for (i=0; i<N; {

while (bExpr[i])

{

// последовательность S1 // скалярных инструкций, // обрабатывающих элементы // векторов с индексом i

}

}

Рис. 5. Векторная реализация цикла while() {}

Лемма 4. Приведенных инструкций следования, выбора и повторения достаточно, чтобы выполнить выборочную (ветвящуюся) векторную обработку любой степени вложенности.

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

Теорема. Шаблона vcarray, управляющего массива для организации ветвлений и набора макросов для ветвления обработки VcarrayIf(vcarray<bool>), VcarrayElse, EndVcarrayIf, макросов повторения VcarrayWhile(vcarray<bool>) - EndVcarrayWhile; VcarrayDo -VcarrayDoWhile(vcarray<bool>) и инструкций следования достаточно для построения программ ветвящейся векторной обработки любой степени сложности.

Действительно, в соответствии с правилами структурного программирования, для создания программы любого уровня сложности достаточно инструкции следования, ветвления и повторения. Шаблон vcarray предоставляет эти 3 вида инструкций, идентичных тем, что есть в языке программирования С++, что доказано в леммах; следовательно, с помощью этих средств также можно написать программу любой степени сложности.

SetVcarraySize(10);

VcarrayIf(vbExpr) // последовательность // инструкций S1

VcarrayElse // последовательность // инструкций S2

EndVcarrayIf

SetVcarraySize(N);

VcarrayWhile(bExpr) // последовательность S1 // векторных инструкций, // обрабатывающих все // элементы векторов

EndVcarrayWhile

Выводы.

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

Список литературы:

1. David E. Culler, Jaswinder Pal Singh. Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann Publishers. August 1998.

2. R. Michael Hord. Understanding parallel supercomputing. IEEE Press in New York. 1999.

3. Черносвитов А.Г. Visual C++ 7: Учебный курс - СПб., 2001.

4. Хортон Айвор. Visual C++ 2005: базовый курс. : Пер. с анг. - М.: ООО «И.Д. Вильямс», 2007.

5. Мак-Дональд Мэтью, Шпушта Марио. Microsoft ASP.NET 3.5 с примерами на C# 2008 для профессионалов, 2-е изд. : Пер. с англ. - М. : ООО "И.Д. Вильямс", 2008.

6. Щербаков Е.В., Щербакова М.Е., Охрамович В.К. Автоматизированное проектирование ППО КСУ на базе пакета программ "КВАРЦ". Монография /под ред. д.т.н., проф. А.Г. Руденко -Луганск: Издательство Восточноукраинского национального университета имени В.Даля, 2003.

Страницы:
1 


Похожие статьи

А И Рязанцев, Е В Щербаков, М Е Щербакова - Векторное распараллеливание серверной обработки данных