Файл: Мультипроцессоры (ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ МУЛЬТИ ПРОФЕССОРОВ И ИХ ИСПОЛЬЗОВАНИЯ).pdf

Рассмотренный пример показывает, что организация процессов в архитектуре самооопределяемых данных строится на базе двух компонент – динамического ядра и интерпретатора. Динамическое ядро порождает каркас процесса в виде графа кодовых переходов, а интерпретатор читает порождаемые коды теговых сопровождений операндов и придаёт им содержательное значение, например в виде арифметических операций. Архитектурная идея, не требуя изменений своей сути, допускает разнообразие интерпретаций. Информационные поля операндов могут содержать не только числа, а действия могут выполнять не только арифметические операции. Это могут быть символьные строки и текстовые объекты, это может быть фрагменты графики или структур данных. Рассмотренный нами пример можно воспринимать как вычисление заданного значения, а можно считать его процессом сборки символической записи из базовых лексических единиц. Возможно значительное разнообразие применений архитектурной идеи самоопределяемых данных для построения реальных информационных систем.

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

2.3 Краткое описание математического аппарата дискретной динамики

Мы будем опираться на ряд фундаментальных работ В.И. Арнольда, которые тематически объединяются одним названием – исследование геометрии функциональных пространств, заданных на конечных множествах. Работы изложены в целом ряде публикаций [34], [35], [36].

Смысл этих работ заключается в том, что исследуется базовое понятие математики – структура, которая задаётся функциональным оператором на конечном множестве элементов. Основная масса исследований структур базируется на аналитической записи оператора и представляется как система манипуляции символическими конструкциями. Арнольд предложил представлять оператор и структуру в целом в виде ориентированного графа. Графовое представление возможно лишь в тех случаях, когда множество, образующее структуру конечно. Граф структуры строится по правилу – элементы структуры являются вершинам графа, а рёбра определяются как пары x; F(x). Возможно только однократное вхождение элемента в граф. Арнольд назвал этот граф монадой. Этим архаичным названием подчёркивалось фундаментальное значение введенного понятия как древнего первоосновного. Традиция исследования монад восходит к Ньютону, Лейбницу и возможно имеет и более ранних предшественников. Арнольд отмечает, что первоначально построение монад носило эмпирический характер и оказалось интригующим и увлекательным занятием. В последствии ученики и аспиранты применили компьютеры для построения монад и дело двинулось более высокими темпами.

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

Рис. 28 Примеры графов монад

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

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

Разрядность 3.

Разрядность 4.

Разрядность 5.

Рис. 29 Зависимость структуры графа монады от числа элементов образующего множества

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

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

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

Рассмотрим график целочисленной функции, заданной на конечном отрезке. Это будет совокупность точек на целочисленной решётке. Линия, соединяющая точки носит условный характер и может быть опущена. Совокупность точек на квадратной целочисленной решётке можно рассматривать как матрицу смежности, задающую ориентированный граф, рёбра которого есть совокупность пар вида x; F(x). Так, что представление функции в виде ориентированного графа в данной ситуации совершенно естественно, хотя и непривычно. Поскольку функция определена на регистровых состояниях, станем называть этот граф графом кодовых переходов и обозначать G_F , граф, порождаемый функцией F.

Каждая точка графика целочисленной функции имеет две проекции - на ось x и на ось y. Если график функциональный, то на все точки оси x всегда имеется одна и только одна проекция графика. На точки оси y может проецироваться любое число точек графика, в том числе и ни одной. Из этого следует, что на графе кодовых переходов каждая вершина всегда имеет одно и только одно исходящее ребро. Входных рёбер может быть сколько угодно от 0 до N, где N число состояний регистра. Следовательно, все возможные графы кодовых переходов образуют специфический класс графов, ограниченный определёнными правилами структурообразования.

На рис. 30 можно проследить как свойства графика функции F проецируются на свойства графа кодовых переходов.

Рис. 30 Взаимосвязи графика функции и порождаемого графа G_F

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

Рис. 31а Суперпозиция

Рис. 31б Автосуперпозиция

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

А теперь можно сделать определения основных понятий дискретной динамики:

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

Фазовый портрет дискретного аттрактора это граф кодовых переходов G_F порождаемый функцией F.

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

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