Файл: Теоретические аспекты мультипроцессоров.pdf

Смысл этих работ заключается в том, что исследуется базовое понятие математики – структура, которая задаётся функциональным оператором на конечном множестве элементов. Основная масса исследований структур базируется на аналитической записи оператора и представляется как система манипуляции символическими конструкциями. Арнольд предложил представлять оператор и структуру в целом в виде ориентированного графа. Графовое представление возможно лишь в тех случаях, когда множество, образующее структуру конечно. Граф структуры строится по правилу – элементы структуры являются вершинам графа, а рёбра определяются как пары 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.

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

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

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

Фазовый портрет это математическая абстракция, Граф кодовых переходов не реализуется физически, например аппаратно как схемный лабиринт, по которому перемещаются самоопределяемые операнды или программно как сетевая структура данных. Фазовый портрет задаётся косвенным образом как результат взаимосвязанных трансформаций теговых кодов. Обширные фазовые портреты могут поддерживаться очень скромными аппаратными затратами. Если теговый код содержит 16 двоичных разрядов, а программа реализации оператора F состоит из менее чем десяти машинных команд, аттрактор поддерживает фазовый портрет в виде графа кодовых переходов, состоящего из сотен тысяч вершин. Уровень компрессии средств фиксации аттрактора в данном случае может составлять примерно 4 - 5 порядков. По этой причине появляется возможность не хранить детерминанты процесса в одном устройстве, осуществляющем сосредоточенное управление вычислениями, а разместить средства фиксации дискретного аттрактора непосредственно в каждом операнде и осуществить принцип распределённого управления.

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

---

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

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

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

---