Software & Systems

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

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

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

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

Но и это еще не все. Во многом условном различении трех диапазонов "доступной" производительности — скалярной, векторной и супервекторной — последняя относится к предельной производительности векторно-кон-вейеркой ЭВМ, и ее значение определяется исключительно скоростью работы векторных функциональных устройств. Поэтому работа с супервекторной производительностью оказывается практически достижимой в случае, когда векторные устройства длительное время работают только с векторными регистрами, не прибегая к обмену данными с оперативной памятью. Создание подобного режима работы при прогонах реальных программ часто оказывается возможным лишь за счет пересмотра представлений алгоритмов. Еще более тонкие

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

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

Все вышесказанное бесспорно и объективно определяет необходимость и крайнюю важность развития стандартного прикладного программного обеспечения, которым должна быть оснащена векторно-конвейерная ЭВМ "Электроника ССБИС". Стандартное прикладное обеспечение представляется в виде постоянно расширяющегося множества эффективно реализованных подпрограмм и программ, объединенных, как правило, в библиотеки или пакеты. Его состав должен охватывать как наиболее часто встречающиеся общеупотребительные задачи численного анализа и дискретной математики, так и задачи, связанные с отдельными предметными областями. Разработка стандартного обеспечения отделена от пользователя и является неотъемлемой частью реализации всего проекта создания новой машины. В этом смысле стандартные программы ничем не от-лкчаются от других видов программного продукта, создаваемого и поставляемого разработчиком вместе с аппаратурой, и соответственно должны обеспечивать устойчивые гарантированные характеристики при обращении к ним. Эффективная реализация стандартных программ обусловливается выбором или разработкой алгоритмов, в максимальной степени согласованных с архитектурой машины и сохраняющих при этом необходимые точность и устойчивость, а также значительным удельным весом программирования на языке ассемблера, позволяющим непосредственно, без потерь отобразить продукт "ручного" решения задач оптимизации и векторизации.

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

Разработка стандартного прикладного обеспечения для векторно-конвейерной ЭВМ "Электроника ССБИС" была начата с ядра, охватывающего первоочередные задачи общего назначения. К их числу были отнесены следующие задачи.

•    Библиотека стандартных подпрограмм вычисления элементарных математических функций (108 программных модулей, макро ассемблер).

-     Вычисление элементарных функций вещест венного аргумента (скалярный и векторный варианты).

-     Вычисление элементарных функций комп лексного аргумента (скалярный и векторный варианты).

-     Вычисления с двойной точностью (арифмети ческие операции, скалярный и векторный ва рианты вычисления элементарных функций).

-     Целочисленные вычисления (арифметические операции, преобразования типов представле ния, стандартные функции).

-     Обработка аварийных ситуаций.

•    Библиотека стандартных программ вычисления специальных функций скалярного и векторного вещественного аргумента (27 программных модулей, макроассемблер и ФОРТРАН).

-     Вычисления гамма-функции и ее логарифма. ■

-     Вычисления функций Бесселя первого и вто рого родов.

-     Вычисления значений интеграла вероятности (функции ошибок).

-     Вычисления значений многочленов Якоби, Лежандра, Чебышева (первого и второго ро дов), Гегенбауэра, Лагерра, Эрмита с ис пользованием обобщенной схемы Гориера.

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

•   Библиотека элементарных операций линейной алгебры СПЛАВ (17 программных модулей, макроассемблер, вещественные и комплексные аргументы).

-    Скалярное произведение векторов.

-    Умножение вектора на скаляр и сложение с другим вектором.

-    Копирование вектора.

-    Перемещение векторов.

-    Вычисление евклидовой нормы.

-    Вычисление суммы абсолютных значений элементов вектора.

-    Умножение вектора на константу (масштаби рование).

-    Вращение Гивенса.

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

•   Библиотека программ нечисловой обра ботки (36 программных модулей, макроас семблер),

-    Сжатие и расстановка по булеву вектору.

-    Сборка и разборка по списку индексов.

-    Упаковка и распаковка.

-    Поразрядное сложение массивов данных.

-    Удаление повторяющихся элементов после довательности.

-    Нахождение теоретико-множественной раз ности двух множеств.

-    Поиск элементов и минимумов в массиве це лых чисел (максимальный, минимальный, за данный, из заданного интервала, первый неотрицательный, первый отрицательный, первый нулевой, первый ненулевой).

-    Лексикографический поиск по ключу.

-    Поиск координатных максимумов и минимумов массива чисел.

-    Поиск в таблице.

-    Базовые операции с (0,1)-матрицами (умно жение и возведение в степень), с целочислен ными, вещественными и булевыми матри цами).

•   Библиотека программ внутренней сорти ровки.

-    Пирамидальная сортировка.

-    Сортировка слиянием.

-    Сортировка Бэтчера.

-    Сортировка коротких последовательностей.

-    Сортировка коротких последовательностей с последующим слиянием.

-    "Пузырьковая" сортировка.

-    Лексикографические сортировки методами распределяющего подсчета и "черпачного" типа.

•   Библиотека стандартных программ ге нерирования псевдослучайных чисел (10 про граммных модулей, макроассемблер, скалярный и векторный варианты).

-    Линейно-конгруэнтные датчики (равномерное распределение).

-    Датчики, генерирующие "вполне случайные" последовательности.

-    Генераторы последовательностей с экспонен циальным распределением.

-    Генераторы последовательностей с нормаль ным распределением.

-    Определение длины периода генерируемой последовательности.

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

-    Вычисления по множеству наблюдений мате матического ожидания, дисперсии и средне квадратичного отклонения случайной вели чины.

-    Вычисления ошибки и достоверности средне го арифметического.

-    Вычисления коэффициентов эксцесса, вариа ции и асимметрии.

-    Вычисления стандартных ошибок асиммет рии и эксцесса.

-    Логическая обработка массивов наблюдений.

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

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

-    Вычисления квантилей стандартного нор мального и Хи-квадрат распределений.

-    Проверка согласия между эмпирическим и теоретическим распределениями.

-    Вычисления предельной функции распределе ния Колмогорова-Смирнова.

•   Библиотека программ интерполирования, аппроксимации и сглаживания функций (12 про граммных модулей, макроассемблер).

-    Линейная интерполяция.

-    Квадратичная интерполяция.

-    Построение интерполяционного многочлена Лагранжа.

-    Построение интерполяционной формулы Ньютона.

-    Сглаживание функций по точкам.

-    Построение естественного кубического сплайна.

-    Аппроксимация функций методом наимень ших квадратов.

•   Библиотека стандартных программ чис ленного интегрирования (12 программных мо дулей, макроассемблер и ФОРТРАН).

-    Вычисления интегралов по ограниченным об ластям.

-    Адаптивные программы вычисления интегра лов по ограниченным областям.

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

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

•   Библиотека программ решения систем обыкновенных дифференциальных уравнений пер вого порядка (макроассемблер и ФОРТРАН).

-  Интегрирование систем ОДУ методом Эйлера.

-    Интегрирование систем ОДУ методом Адамса.

-    Интегрирование систем ОДУ методом Рун- ге-Кутта-Фельберга четвертого порядка.

-    Интегрирование систем ОДУ методом Дор- мана-Принса восьмого порядка.

-    Интегрирование систем ОДУ методом Хэм- мннга четвертого порядка.

-    Интегрирование систем ОДУ с выдачей таб лицы решений.

•   Библиотека программ решения интег ральных уравнений (6 программных модулей, IIJljl и макроассемблер).

-    Решения линейного одномерного уравнения Вольтерра 1-го рода методом Апарцина с ре гуляризацией.

-    Решения линейного одномерного уравнения Вольтерра 1-го рода методом Тен Мен Яна с регуляризацией.

-    Решения линейного двухмерного уравнения Вольтерра 1-го рода методом Апарцина с ре гуляризацией.

-    Решения линейного трехмерного уравнения Вольтерра 1-го рода методом Апарцина с ре гуляризацией.

•   Библиотека базовых программ решения задач комбинаторной вычислительной геомет рии (II программных модулей, макроас семблер).

-    Определение принадлежности точки просто му н выпуклому многоугольникам.

-    Определение центров и радиусов вписанных и описанных окружностей треугольника.

-    Пересечение выпуклых многоугольников.

-    Построение выпуклой оболочки.

-    Построение диаграммы Вороного.

•   Библиотека программ решения задач на графах (21 программный модуль, макроассемб лер).

-    Представление и преобразование структур данных для графов.

-    Топологический анализ графов.

-    Нахождение расстояний и кратчайшего пути.

t Пакет программ быстрого преобразования Фурье (37 программных модулей, ПЛ/1 и макроассем блер).

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

-    Быстрые циклическая и линейная свертки.

-    Транспортирование матриц.

-    Реверсирование векторов.

•   Пакет программ решения задач линейной алгебры с заполненными квадратными и прямо угольными матрицами общего вида, симмет ричными и треугольными матрицами (50 про граммных модулей, ФОРТРАН и макроассемб лер).

-    Решение .систем линейных уравнений с тре угольными матрицами.

-    Матричная арифметика.

-    Разложение матриц на множители.

-    Преобразование форм хранения матриц.

-     Решение систем линейных алгебраических уравнений.

-     Решение задач наименьших квадратов.

-     Матричные функции.

•    Пакет программ решения задач линейной алгебры с использованием внешней полупровод никовой памяти (30 программных модулей, ФОРТРАН и макроассемблер).

-     Базовые матричные операции.

-     Базовые операции обмена.

-     Решения СЛАУ и разложения матриц.

•    Пакет программ решения задач на собственные значения для заполненных симметричных положительно определенных матриц (4 программных модуля, ФОРТРАН и макроассем блер).

-     Приведения матриц преобразованиями отра жения к верхней хессенберговой форме и к трехдиагональному виду:

-     Вычисления собственных значений.

-     Вычисления собственных векторов.

•    Пакет программ решения задач линейной алгебры с разреженными матрицами (29 про граммных модулей, ФОРТРАН и макроассемб лер).

-     Элементарные операции с разреженными матрицами.

-     Анализ графовых представлений разрежен ных матриц.

-     Преобразование форм хранения и переупоря дочение структур разреженных матриц.

-     Разложения разреженных матриц и решения СЛАУ.

•    Пакет программ решения задач линейной алгебры с ленточными матрицами прямыми методами (38 программных модулей, ФОРТ РАН и макроассемблер).

-     Вычисления по схемам Горнера и цепной дроби.

-     Решение трехдиагональных систем уравне ний с диагонально доминантными матри цами.

-     Решение трехдиагональных систем уравне ний с произвольными невырожденными мат рицами.

-     Умножение ленточных матриц на векторы и матрицы.

-     Перепаковка ленточных матриц.

-     Отыскание треугольных разложений ленточ ных матриц.

-     Решение систем уравнений с треугольными ленточными матрицами.

-     Решение систем уравнений с произвольными ленточными матрицами.

•    Пакет программ решения систем линей ных уравнений с ленточными матрицами ите рационными методами (12 программных модулей, ФОРТРАН и макроассемблер).

-     Метод Якоби.

-     Метод Гаусса-Зейделя.

-     Метод Гаусса-Зейделя с последовательной верхней релаксацией.

-     Метод сопряженных градиентов.

•    Пакет программ решения задач спект рального анализа для симметричных трехдиагональных матриц (8 программных модулей, ФОРТРАН и макроассемблер).

-    Метод бисекций.

-    Ортоганализация Грамма-Шмидта.

-    QR-алгоритм в сочетании с методом Ньютона.

-    Метод Якоби.

-    Отыскание собственных векторов модифици рованным методом Штурма.

• Пакет программ решения задач оптимального распределения ресурсов на сетях большой размерности (39 программных модулей, ФОРТРАН и макроассемблер).

-    Поиск и сортировка (см. соответствующие библиотеки).

-    Задачи топологического анализа и преобра зования сети.

-    Задачи количественного анализа к расчета параметров сети.

-    Задачи распределения и оптимизации ресур сов сети.

В создании описанного программного продукта, получившего название Научная Библиотека "Электроники ССБИС" помимо сотрудников Отдела базового программного обеспечения Института проблем кибернетики РАН принимали участие сотрудники Института математики АН Беларуси и кафедры хибернетики Московского института электронного машиностроения.

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

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