Учебные материалы АОИС часть 1 / part_1 / Теория / АОИС1

В завершение раздела рассмотрим основные принципы дальнейшего развития высокопроизводительных вычислительных систем (ВВС) семейства

«СКИФ».

Предпосылки для развития ВВС семейства «СКИФ»

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

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

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

188

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

В рамках программы «СКИФ» создан существенный научно-технический задел, позволяющий создавать суперкомпьютерные конфигурации в широком диапазоне производительности, вплоть до триллиона операций в секунду. Для решения задач на базе наукоемких технологий для различных областей применения в рамках программы «СКИФ» были созданы кластеры «СКИФ К- 500» и «СКИФ К-1000». Включение этих кластеров в список пятисот наиболее мощных вычислительных установок в мире означает достижение важного прямого политического эффекта – Республика Беларусь и Россия наравне с США, Японией и еще несколькими странами стали обладателями критической суперкомпьютерной технологии, повысив престиж Союзного государства как разработчика этой технологии.

Анализ хода реализации программы «СКИФ» с учетом реальных объемов финансирования работ позволяет сделать вывод, что благодаря ей обеспечены научно-технические и производственные предпосылки для широкого практического внедрения суперкомпьютерных технологий, включая создание суперкомпьютерных центров. Реализация этих предпосылок позволит уменьшить отставание стран–участниц Союзного государства от ведущих мировых держав в развитии и применении новейших наукоемких технологий в таких областях, как машиностроение, биотехнология, геологоразведка, контроль окружающей среды, транспорт и связь, в государственных, коммерческих, военных и других

189

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

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

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

Результаты комплексной реализации программы «СКИФ» являются существенным научно-техническим и организационным заделом для дальнейшего развития суперкомпьютерного направления, в том числе для формирования новых программ Союзного государства по развитию суперкомпьютерного направления «СКИФ».

Стратегия развития суперкомпьютерного направления «СКИФ»

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

190

Создаваемые суперкомпьютеры семейства «СКИФ» являются базой для реализации сформированной Министерством промышленности, науки и технологий Российской Федерации и Национальной академии наук Беларуси научно-технической программы Союзного государства «Развитие и внедрение в государствах – участниках Союзного государства наукоемких компьютерных технологий на базе мультипроцессорных вычислительных систем» (шифр «Триада»).

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

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

«СКИФ-2».

К основным возможным направлениям работ в рамках программы «СКИФ-2» относятся:

-гетерогенные кластерные и метакластерные системы;

191

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

-перспективные методы комплексирования (например Hyper-Transport, Infiniband etc);

-гибридные узлы и архитектуры (оригинальные СБИС, нейроструктуры, FPGA);

-Grid-конфигурации на базе суперкомпьютеров «СКИФ»;

-объединение внутренней шины и интерконнекта;

-эффективные механизмы (например альтернатива MPI) обмена данными (новый транспортный уровень);

-направление Lisa – самоконфигурирование, самодиагностика и т.п. (концепция IBM);

-системы разделения ресурсов в кластерных и метакластерных конфигурациях и GRID системах;

-защита данных (в том числе с учетом ПЭМИ);

-перспективные конструктивные решения («лезвие бритвы» и т.п.);

-мобильные (возимые) системы на базе Grid-технологий;

-условия эксплуатации;

-объединенная система управления и мониторинга кластерными структурами (развитие сервисной сети);

-развитие направления Т-система (T-Grid);

-апгрейдируемость (способность к модернизации).

192

Тема 6. АБСТРАКТНЫЕ ИНФОРМАЦИОННЫЕ МАШИНЫ

6.1Понятие абстрактной информационной машины

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

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

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

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

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

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

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

Машина Тьюринга является расширением модели конечного автомата и, согласно тезису Чѐрча — Тьюринга, способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

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

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

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

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

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

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

Тезис Чѐрча фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чѐрчем и Аланом Тьюрингом в середине 1930-х годов.

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

Тезис Чѐрча-Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции».

Физический тезис Чѐрча-Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.

Машина Поста - абстрактная вычислительная машина, предложенная Эмилем Л. Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины эквивалентны и были созданы для уточнения понятия алгоритм. Прежде всего надо сказать, что машина Поста не есть реально существующее, сделанное кем-то устройство. Машина Поста, как и ее близкий родственник машина Тьюринга, представляет собой мысленную конструкцию, хотя устройство, позволяющее моделировать работу машины Поста в случае небольших программ и небольших объемов вычислений, было изготовлено в 1970 году в Симферопольском государственном университете. Однако для нас не будет существенным факт,

что машины Поста на самом деле нет. Напротив, мы будем предполагать ее как бы "существующей".

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера. Порядок, в котором расположены секции ленты, подобен порядку, в котором расположены все целые числа. Поэтому естественно ввести на ленте "целочисленную систему координат", занумеровав секции числами ..., -3 , -2 , -1 , 0 , 1 , 2 , 3,...

В каждой секции ленты может быть либо ничего не записано (такая секция называется пустой), либо стоять метка "V" (тогда секция называется отмеченной).

Информация о том, какие секции пустые, а какие отмеченные, образует состояние ленты. Иными словами, состояние ленты - это распределение меток по ее секциям. На точном математическом языке состояние ленты - это функция, которая каждому числу (номеру секции) ставит в соответствие либо метку, либо "пусто". Состояние ленты, в процессе работы, может меняться.

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

Таким образом, состояние машины Поста слагается из состояния ленты и указания номера той секции, которую обозревает каретка.

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

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

1)команда движения вправо: m . => n

2)команда движения влево: m . <= n

3)

команда печати метки:

m. p n

4)команда стирания метки: m. s n

5)	команда передачи:	m. ? n1,n2
6)	команда остановки:	m. stop

Число m, стоящее в начале команды, называется номером команды, а число n, стоящее после команды (а у команды передачи управления n1и n2), называется отсылкой. У команды остановки отсылка отсутствует.

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

1. На первом месте в этом списке стоит команда с номером 1, на втором месте (если оно есть) - команда с номером 2 и т.д.; вообще на k-м месте стоит команда с номером k.

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

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

Работа машины на основании заданной программы происходит следующим образом. Машина приводится в начальное состояние и приступает к выполнению первой команды программы. Каждая команда выполняется за один шаг, а переход от выполнения одной команды к выполнению другой происходит по следующему правилу: пусть на k-м шаге выполнялась команда с номером m, тогда,

1)если эта команда имеет единственную отсылку n, то на (k+1)-м шаге выполняется команда с номером n;

2)если эта команда имеет две отсылки n1 и n2, то на (k+1)-м шаге выполняется одна из двух команд - с номером n1 или с номером n2;

3)если же выполняющаяся на k-м шаге команда вовсе не имеет отсылки, то на (k+1)-м шаге и на всех последующих шагах не выполняется никакая команда - машина останавливается.

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

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

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

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

Выполнение команды передачи управления с отсылками n1 и n2 никак не изменяет состояние машины: ни одна из меток не уничтожается и не ставится, и каретка также остается неподвижной (машина делает "шаг на месте"). Однако если секция, обозреваемая перед началом выполнения

команды, была отмечена, то следующей должна выполняться команда с номером n1. Если же эта секция была пустая, то следующая должна выполняться команда с номером n2 (роль команды передачи управления сводится, следовательно, к тому, что каретка во время выполнения этой команды как бы "распознает", стоит ли перед ней метка).

Выполнение команды остановки тоже никак не меняет состояния машины и состоит в том, что машина останавливается.

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

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

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

3.В ходе выполнения программы машина не дойдет до выполнения ни одной из команд, указанных в первых двух вариантах. Выполнение

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

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

1.	<= 2		Поиск начала первого числа: сдвигаемся влево
2.	?	3,1	до тех пор, пока не встретим не отмеченную ячейку.
3.	=> 4		Сдвинуться вправо на одну метку и
4.	s	5	и удалить ее.
5.	=> 6		Поиск конца первого числа: сдвиг вправо
6.	?	7,5	пока головка не встанет на неотмеченную ячейку и
7.	p	8	ставим ее

8.=> 9 Проверить заполнен ли промежуток между числами

9.? 1,10 если промежуток не заполнился, то переход на начало.

10. stop Конец программы

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