Скалярная и векторная обработка

Принципы векторной обработки данных

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

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

Для задания адреса скаляра в оперативной памяти необходимо задать только начальный адрес.

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

Что же такое векторизация и в чем е превосходство векторной обработки по сравнению с традиционной скалярной обработкой данных?

Что такое векторизация?

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

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

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

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

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

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

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

Как осуществить векторизацию?

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

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

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

Следовательно, если удастся семантически свести свою структуру к какой-либо структуре из области линейной алгебры, то чаще всего векторизация просто означает понимание того, что вы столкнулись с частным случаем общего метода. Например, пусть имеется описание набора сейсмических колебаний во времени и в пространстве. Традиционный способ их обработки, например вычисление быстрого преобразования Фурье (БПФ) – по одному колебанию за один раз. Этот подход отражал не только естественный образ мышления, но и был вынужденным из-за ограничения памяти предыдущих поколений вычислительных систем. Однако, стоит только заметить, что набор колебаний во времени и в пространстве образует заполненную матрицу, как можно применять хорошо известный способ оптимальной векторизации БПФ, при котором колебания рассматриваются как полный набор: вначале в пространстве, затем – во времени, т.е. используется транспонированная матрица.

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

Что обычно препятствует векторизации? В широком смысле таких препятствий 2. Во-первых, структура данных, над которой должна быть произведена та или иная операция, может не быть вектором. Это может происходить по разным причинам, начиная от постоянного присутствия «небольших» дыр до сильно разреженных структур. Первый случай имеет место в алгоритмах решения краевых задач, в которых дырам соответствуют граничные значения. Вторая ситуация характерна, например, для операций со строками матриц, которые хранятся по столбцам. Промежуточный случай возникает, когда из сетки, записанной в лексикографическом порядке, удаляются данные, соответствующие красным и (или) черным клеткам.

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

А(I+1) = А(I) + В(I) для I от 1 до N.

Здесь ясно, что ни одно значение А не может быть получено раньше, чем все предыдущие значения. Или все-таки может?

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

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

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

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

Дата добавления: 2014-01-04