Система графического программирования-исполнения, построенная на принципах схемной эмуляции

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

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

Зачем изобретать велосипед, если он уже давно изобретен и с успехом используется? Это - методики проектирования электронных систем, на которые так любят ссылаться сами же программисты.

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

Схемная эмуляция и автоматное программирование

(система автоматного программирования, построенная на принципах схемной эмуляции)

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

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

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

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

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

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

Как избежать всех этих ужасов? Одной из панацей считается применение ФОРМАЛЬНЫХ методов проектирования программ. Что касается сегодняшнего состояния дел в этом направлении для задач логического управления, то значительный вклад в решение обозначенных выше проблем уже проделан путем переноса достижений теории конечных автоматов на область программирования.

Каким образом теория автоматов может иметь отношение к программированию? Чтобы понять это, достаточно вспомнить общеизвестный факт, что любой алгоритм управления может быть реализован как программно, так и аппаратно. Этот принцип, в свое время, еще Э.Э. Клингманом [1] был назван дуализмом.

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

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

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

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

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

Вот тут должна стать понятной ценность концепции, высказанной А.А. Шалыто и Н.И. Туккель, что, оказывается, графы переходов автоматов Мура-Мили прекрасным образом имеют изоморфность с обычной SWITCH структурой языка Си, или подобными структурами в любом другом языке программирования.

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

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

Наиболее полную информацию по теории автоматного программирования и последним достижениям в данной отрасли знаний можно найти на сайтах А. Шалыто (д.т.н., профессор, зав. кафедрой Технологии Программирования Санкт-Петербургского Государственного Универститета Информационных Технологий, Механики и Оптики) - http://is.ifmo.ru и А. Легалова (д.т.н., доцент, профессор кафедры НейроЭВМ Красноярского Государственного Технического Университета) - http://www.softcraft.ru/

Будет ошибочным полагать, что данная методика ограничена только разработкой программ логического управления. Потому как "цифра" с каждым днем находит все новые области применения: сегодня теория автоматов лежит в основе операционной системы UNIX, с успехом пишутся драйвера для компьютерных систем, фирма Boeing использует ее в основе построения автопилотов... Список этот, на самом деле, уже сегодня гораздо более длинный. Внушает оптимизм тот факт, что, как оказалось, и само объектно-ориентированное программирование (ООП) - столп современных технологий программирования прекрасным образом подходит для формализации упомянутой технологией. Один только этот факт внушает оптимизм, что не за горами день, когда программы станут такими же надежными, как электронные системы, а их разработка превратится из искусства в строгую науку.

Как выглядит технология автоматного программирования?

Я попытаюсь выразить идею буквально одним абзацем: специалист, опираясь на исходные данные проекта и математический аппарат теории автоматов, разрабатывает граф-схему (рисунок) переходов некоторого автомата. Затем (внимание!) ему предлагается использовать специальный компилятор, который по этой граф-схеме автоматически сгенерирует C/C++ исходный текст программы. А затем уже, используя обычный компилятор, по исходному тексту программы (полученному автоматически) сгенерировать исполняемый exe-файл. Конечно, можно написать коды программы по графу и "руками", что не меняет сути идеи.

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

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

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

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

Рассмотрим теперь конкретнее, каким образом автоматы можно эмулировать. Поскольку (каюсь) я не есть теоретик автоматного программирования, то представлю только два способа. Профессионалам, быть может, удастся развить эту тему глубже.

1-й способ. Собственно говоря, он "лежит на поверхности". Воспользуюсь готовым рисунком графа (рис. 8) переходов из работы [2]. Подразумевается, что человек его нарисовавший как бы предварительно получил задание на разработку в виде словесного описания, временных диаграмм или алгоритма. Конечно, мы его рассматриваем только как пример, поскольку графы реальных разработок несравненно сложнее.



Рис. 8 Граф схемы цифрового автомата

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

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

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



Рис. 9 Схема цифрового автомата

2-й способ. Это эмуляция непосредственно графа переходов (рис. 8). Только для этого необходимо доработать саму программу эмуляции. Дело в том, что основополагающий принцип любой программы моделирования цифровых устройств состоит в отыскании "активных" цепей. Активной считается та цепь, на которой произошло изменение уровня логического сигнала. Таким образом, связь ("дуга", если проводить аналогию с графом) - первична, а компонент ("вершина") - вторичен.

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

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

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

Литература:

[1] - Дейкстра Э. Дисциплина программирования. М: Мир, 1979

[2] - Шалыто А.А. Реализация алгоритмов логического управления программами на языке функциональных блоков. ж-л "Промышленные АСУ и контроллеры".2000 №4.

Архитектура потоковой суперЭВМ, построенной на принципах схемной эмуляции. Сравнительный анализ с известными архитектурами

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

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

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

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

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

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

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

Таким образом, реализация (коммерциализация) проекта "Пульс" придаст мощный импульс к развитию таких направлений как системы автоматики, АСУ ТП, интеллектуальные системы и суперЭВМ. Что, в свою очередь, послужит надежной базой для качественного развития большого числа различных отраслей знаний, часть из которых уже перечислена. Это позволит Украине со всей справедливостью занять лидирующие позиции в мире в деле построения постиндустриальной державы, совершить качественный рывок в этом направлении. И это в то время, когда мы пока далеки еще даже от уровня развитого индустриального государства, имея пока имидж сырьевой базы для мировой экономической системы. Именно развитие собственных высокоинтеллектуальных и высокопроизводительных вычислительных систем способны стать локомотивом развития всей отечественной экономики. Другого пути просто нет.

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

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

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

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

I. Архитектура фон Неймана

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

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

Вкратце приведу основные параметры такого разрыва.

¦ регистры процессора и модульность программ ¦

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

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

¦ рост объема программных кодов и ненадежность ПО ¦

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

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

Что трактуется как "абсорбирование" структуры (данных) в логике программы.

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

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

¦ команды и данные ¦

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

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

Все это нередко становится причиной сбоев в работе ПО и зависаний, например, при сбое в системе питания, которое может привести к случайному изменению значения Регистра Адреса.

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

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

¦ параллелизм ¦

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

К тому же, параллелизм на уровне команд, который можно найти в потоке команд традиционного компьютера, ограничен. Исследования показали пределы использования процессора даже для суперскалярных микропроцессоров. К примеру, на тесте SPEC92 микропроцессор PowerPC 620 показал, что в среднем исполняется от 0,96 до 1,77 команд за один такт, а 8-ми входовый процессор Alpha не смог исполнить 1,55 команд за такт. К тому же, зависимости по данным и управлению потенциально являются причиной сбоев конвейера микропроцессоров, в которых управление реализовано с помощью сложной логики продвижения команд

¦ мультипроцессорная обработка ¦

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

Согласно гипотезе Минского (Minsky), ускорение, достигаемое при использовании параллельной системы, пропорционально двоичному логарифму от числа процессоров. То есть, при использовании 1000 процессоров на одной платформе возможное ускорение оказывается равным всего 10 (!).

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

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

I - I. Архитектура многопроцессорной ЭВМ с жесткими связями

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

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

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

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

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

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

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

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

I - II. Архитектура кластерных структур

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

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

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

К тому же, организация большого числа платформ в единую структуру требует разработки сложнейшего программного обеспечения, зачастую граничащего с уровнем know-how.

II. Архитектура реконфигурируемых вычислительных структур*

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

Как бы не показалось странным на первый взгляд, но вычислительная мощность компьютерных систем за время их существования выросла, главным образом, далеко не за счет технологического развития. Ведь если со времен первых компьютеров (EDSAC, Кембридж, 1949 год) и до наших дней (суперкомпьютер Hewlett-Packard V2600) время такта выросло с 2 микросекунд до 1,8 наносекунды и прирост составил 1000 раз, то производительность выросла, соответственно, со 100 арифметических операций в секунду до 77 миллиардов. Прирост составляет более чем семьсот миллионов раз. Откуда же тогда взялась такая существенная разница? Ответ очевиден - от использования новых решений в архитектуре компьютеров.

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

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

Эта проблема имеет системный характер и является следствием неадекватности каждой конкретной архитектуры вычислительной системы внутренней структуре решаемой задачи. Вообще говоря, любую задачу пользователя можно представить системой S, процессы в которой описаны формой информационного графа (рис. 10а). Граф G(Q,X) содержит множество вершин giQ, каждой из которых приписана некоторая операция Oi, принадлежащая множеству допустимых операций O.Дуги графа определяют последовательность выполнения операций, приписанных вершинам. Множество входных дуг определяют источник входных данных, выходных - приемник результатов решения.

При исполнении задачи S в среде мультипроцессорной системы (S*), в последней организуется вычислительный процесс, который можно описать информационным графом G*(Q*,X*). Здесь множество вершин Q* определяется множеством процессоров вычислительной системы, а множество дуг X* представляет собой множество каналов коммуникаций между процессорами. В свою очередь, входные и выходные дуги определяются каналами связи с источником входных и приемником выходных данных.

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

Указанного недостатка вычислительной системы с "жесткой" архитектурой можно избежать, если обеспечить возможность ее реконфигурации таким образом, чтобы граф G* вычислительного процесса как можно ближе совпадал с графом G решаемой задачи.

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

Суть концепции РВС в том и заключается, чтобы архитектура вычислительной системы имела возможность адаптироваться под структуру решаемой задачи. В отличие от многопроцессорных вычислительных систем с жесткими межпроцессорными связями, а также кластерных систем, архитектура связей реконфигурируемых вычислителей может изменяться в процессе их функционирования. В результате у пользователя появляется возможность адаптации архитектуры вычислительной системы под структуру решаемой задачи. В качестве наиболее подходящей среды реализации идеи используются микросхемы программируемой логики (ПЛИС), как устройств наивысшей степени параллельного действия, известных на сегодняшний день. К тому же применение ПЛИС обеспечивает ускорение вычислительного процесса по сравнению с микропроцессором от 5 до 100 раз вследствие адаптации внутренней вычислительной структуры к информационной структуре решаемой задачи.

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

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

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

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

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

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

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

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

Суть этого подхода заключается в создании мультиконвейера с жесткой архитектурой и обеспечении коммутационных возможностей за счет придания каждому процессору дополнительных функций транзитной передачи информации. В такую структуру можно отобразить любой граф алгоритма G(Q,X), как показано на рис. 10

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

Рис. 10 Отображение графа G(Q,X) в матричную мультимикроконвейерную структуру

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

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

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

Реализация идеи реконфигурируемых МВС долгое время сдерживалось отсутствием подходящих компонент. Появления в конце 90-х годов XX века программируемых логических интегральных схем сверхвысокой степенью интеграции вдохнуло в идею второе дыхание. Микросхемы ПЛИС представляет собой матрицу логических ячеек (FPGA - Field Programmable Gates Array), путем программирования и коммутации которых можно создавать аппаратные реализации различных структур, причем перепрограммирование допускается многократно.

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

Рис. 11 Архитектура мультимакроконвейерной РВС с программируемой логикой.

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

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