Концепция построения параллельных компьютерных систем: от схем автоматной памяти до полиграммных устройств

Размещено на http://www.allbest.ru/

Концепция построения параллельных компьютерных систем: от схем автоматной памяти до полиграммных устройств

Мараховский Л.Ф.

г. Киев, Украина

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

Ключевые слова: схемы автоматной памяти, автоматное непрерывное время, автоматы третьего рода, параллельные иерархические автоматы, полиграммный уровень управления, принципы иерархического программного управления.

The conception of the construction of the parallel computer systems: from the automatical memory schemes till the poligrammaing units. L.F.Marahovsky

The new methods for the structural organization of the parallel hierarchial computer units on the elementary automatical memory schemes are concidered. The characteristic feature of the devices suggested is that the information processing may be performed at the intervals between the setting input signals.

Концепція побудови паралельних комп'ютерних систем: від схем автоматної пам'яті до поліграмного обладнання. Л.Ф. Мараховський

Розглянуті нові методи структурної організації паралельних ієрархічних пристроїв обчислювальної техніки на схемах автоматної пам'яті. Відмінною рисою запропонованих пристроїв є те, що обробку інформації можна вести в інтервалі між встановлюючими вхідними сигналами.

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

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

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

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

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

Перспективным направлением развития монофункциональных триггеров явилось создание многофункциональных схем автоматной памяти (МСП) [ 2-7]. В отличие от триггеров они имеют не только устанавливающие входные сигналы, но и сохраняющие входные сигналы, которые обеспечивают запоминание определенного подмножества (блока) состояний. Структурно МСП отличаются от триггеров тем, что в каждой группе имеют число логических элементов ИЛИ-НЕ (И-НЕ, И-ИЛИ-НЕ) более одного.

Была разработана теория проектирования МСП [ 5-7 ], а также система автоматизированного проектирования этих схем [ 8 ].

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

В направлении развития МСП, с целью ликвидации их недостатка, были созданы многоуровневые устройства автоматной памяти (МУП) [ 7 ]. Структурно МУП проектируются из МСП, взаимосвязанных по вертикали сохраняющими входными сигналами. Выходные сигналы нижних МСП, отождествляющие состояние МСП, поступают на входные узлы сохраняющих входных сигналов высших МСП. Таким образом, осуществляется внутренняя генерация сохраняющих входных сигналов внутри МУП. Все МСП в МУП могут одновременно устанавливаться информационными входными сигналами в определенные состояния, а внутренние сохраняющие входные сигналы определяют блоки состояний, в которых МСП в данный момент могут работать.

Структурно МУП представляют схему, изображенную на рис. 1, а иерархическая взаимосвязь состояний - на рис.2

МУП имеет ряд преимуществ по функциональным и конструктивным характеристикам по сравнению с многостабильными триггерами.

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

Рис. 1. Структура МУП

Рис. 2. Иерархическая взаимосвязь состояний МСП в МУП

По структурным свойствам:

а) имеют меньшее число внешних (в 2 раза) и внутренних (в 10 раз) связей при одном числе запоминаемых состояний (например, 18 состояний);

б) требуют меньшего числа логических элементов на одно состояние (на 23% меньше);

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

Методы синтеза схем автоматной памяти (МСП, МУП) с учетом ограничений логических элементов, с формульными выражениями по определению их основных параметров и сравнение характеристик с многостабильными триггерами представлены в работах [ 11-13 ], в которых и отражены их преимущества.

Основы теории автоматов на схемах автоматной памяти.

Известны теории последовательных автоматов первого и второго рода, использующих в качестве схем памяти триггеры [ 1 ].

На основе свойств схем автоматной памяти разработана качественно новая теория автоматов, функционирующих в автоматном непрерывном времени Ti = ti + i , в котором во время ti определяются входные воздействия информационных сигналов xi (t), а во времени i - входные воздействия сохраняющих сигналов ej(). Последовательная пара xi(t), ej() составляет элементарное входное слово Pk(T) = xi(t), ej().

Определение, задание и законы функционирования автоматов первого и второго родов (при ej() = const) и третьего рода даны в работах [ 7, 9, 14 ], а примеры устройств, проектируемых на их основе, в работах [ 7, 10-13 ].

Характерным свойством детерминированных автоматов является область допустимых информационных x(t) входных сигналов, cпособных переводить автомат в состояние a(t) определенного блока j состояний, сохраняемых под воздействием ej() входных сигналов.

Установленные аk(t) и незапоминаемое состояние аp(t) при последующем воздействии сохраняющих ej() входных сигналов в детерминированных автоматах первого и второго родов могут образовать область запрещенных входных слов Pp(T). В детерминированных автоматах третьего рода за счет укрупненных переходов под воздействием сохраняющих ej() входных сигналов область допустимых слов Pk(T) расширяется.

В вероятностных и нечетких автоматах третьего рода могут использоваться вероятностные и нечеткие переходы под воздействием вероятностных элементарных слов первого и второго типов
Pв(Т) = хp(t), ej() и Pв(Т) = хi(t), ejв() входных слов и нечетких Pн(Т) = хр(t), ejв() входных слов. Вероятностные переходы способны осуществлять переходы из одного состояния в состояние вполне определенного блока состояний МСП с определенной мерой вероятности, а нечеткие переходы - переходы в состояние нечеткого подмножества, состоящего из вполне определенных блоков состояний МСП [ 14 ].

Графическое представление этих переходов дано на рис. 3.

Теория автоматов с памятью на МСП расширяет функциональные возможности известных теорий автоматов с памятью на триггерах [ 1 ].

а) однозначные переходы в детерминированных автоматах первого и второго родов (ej() = соnst)

б) укрупненные переходы в детерминированных автоматах третьего рода в состояние аj() блока j состояний (аi(t)j)

в) вероятностные переходы первого и второго типа в автоматах третьего рода в состояние блока j или блока i матричной памяти МСП.

г) нечеткий переход в автоматах третьего рода

Рис. 3. Типы переходов в устойчивые состояния, представленных в виде направленных графов

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

Разработанная математическая модель иерархического автомата способна описывать функционирование не только параллельно работающих подавтоматов Si, но и их межуровневое иерархическое взаимодействие за счет использования сохраняющих eij() входных сигналов. При разработке теории иерархических автоматов рассмотрены способы задания автоматов, формулирование полиграмм, синтеза автомата по полиграмме, синтеза автомата с использованием ПЗУ. Методы синтеза иерархических автоматов позволяют расширить функциональные возможности межуровневых иерархических структур компьютерных машин и систем за счет осуществления переходов во время внутреннего такта автоматного непрерывного времени Т.

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

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

Четвертый уровень управления

Микропрограммный уровень управления в основном определяет систему команд, которая в дальнейшем используется программным уровнем управления [ 1 ].

Четвертый уровень управления можно представить в виде параллельной структурной схемы так, как это дано на рис. 4.

Рис. 4. Параллельная двухуровневая структурная схема, использующая четвертый уровень управления

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

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

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

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

Заключение

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

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

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

Новое направление является дополнением к развитию компьютерной техники. Оно способно быть реализовано на современных логических элементах, используемых в СБИС, ПЛИС, ОЗУ, и оказать достаточно большое влияние на программное обеспечение компьютеров, компьютерных систем и сетей.

Литература

Справочник по цифровой вычислительной технике: (процессоры и память) / Б.Н.Малиновский, Е.И.Брюхович, Е.Л. Денисенко и др. Под ред. Б.Н.Малиновского. - К.:Техніка, 1979. - 366 с.

А.с. 403077 СССР, М.К.Н. 03К 29/00 - Многоустойчивый элемент / Мараховский Л.Ф., Сталоверов В.А. - Опубл. 19.10.73, Бюл. № 42.

А.с. 801100 СССР М.Кл.3 G11C11/56. Многостабильный тактируемый D-элемент / Мараховский Л.Ф., Байтлер В.И., Савченко Ю.Г. - Опубл. 30.01.81, Бюл. № 4.

А.с. 595865 СССР М.Кл.2Н. 03К29/00. Многоустойчивый синхронизируемый элемент / Мараховский Л.Ф., Байтлер В.И.- Опубл. 28.02.78, Бюл. № 8.

Мараховский Л.Ф., Байтлер В.И., Некоторые вопросы теории схем памяти типа R-S // Электроника и моделирование. - 1977. - № 16. - С.53-57.

Мараховский Л.Ф. Вопросы проектирования элементарных схем памяти // Механизация и автоматизация управления. - К., 1980.- № 3. - 13с. Деп. в УкрНИИНТИ.

Дискретные устройства с многофункциональной системой организации памяти / Мараховский Л.Ф.: Киев, ин-т народ. хоз-ва. - К., 1987. - 244с. Деп. в УкрНИИНТИ., 30.12.87, № 3346 - Ук87.

Мараховский Л.Ф. Система автоматизированного проектирования одноуровневых многофункциональных схем памяти // Машинная обработка информации. - К.: Либідь, 1990. - Вып. 51 - С.57-61.

Мараховский Л.Ф. Конечные автоматы с многофункциональной системой организации памяти: Учебн. пособие. - К.: УМК ВО, 1991. - 67с.

Мараховский Л.Ф. Устройства вычислительных машин с многофункциональной системой организации памяти: Учебн. пособие. - К.: УМК ВО. - 1992. - 56с.

Мараховский Л.Ф. Многофункциональные схемы памяти. - К.: Управляющие системы и машины, 1996. - № 6. - С.59-69.

Мараховский Л.Ф. Многоуровневые устройства автоматной памяти. - I ч. - К.: Управляющие системы и машины, 1998. - № 1. - С.66-72.

Мараховский Л.Ф. Многоуровневые устройства автоматной памяти. - II ч. - К.: Управляющие системы и машины, 1998. - № 2. - С.63-69.

Мараховский Л.Ф. Основы теории проектирования дискретных устройств. Логическое проектирование дискретных устройств на схемах автоматной памяти: Монография. - К.: КГЭУ, 1996. - 128с.

Размещено на Allbest.ru