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

1 Научно-исследовательский вычислительный центр МГУ Интеллектуальные информационные технологии Полиморфное кодирование кубических структур, операции над кубантами, моноид, хаусдорфова метрика и совмещенные машинные операции в супервычислениях Научный руководитель -Г.Г.Рябов Исполнители:, В.А.Серов, В.А.Толстошеев, Г.Г.Кузьмин, А.С.Фингеров Проект поддержан грантом РФФИ офи_м

2 План изложения Общее введение. Введение. Роль кубических структур в математических моделях. Часть 1. Определение кубантов. Операция умножения. Моноид. Часть 2. Метрика Хаусдорфа-Хэмминга на кубантах в I n. Часть 3. Метрика Евклида-Хаусдорфа в R n с. Часть 4.Элементы кубического синтеза. Часть 5.Элементы динамики на кубических структурах. Часть 6.Машинное представление данных и операций. Часть 7.Полиморфное кодирование и алгебраизация супервычислений. Часть 8. Инструментальная система на суперкомпьютере. Литература. Приложение 1.Непересекающиеся к-пути. Приложение 2. Примеры графического представления. Приложение 3. 3-пути через случайную окрестность.

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

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

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

6 Роль кубических структур в геометрико-топологической основе математических моделей Глобальная модель циркуляции (МТИ)- погодный и климатический прогноз. Конформная кубоидная сфера. Геометрическая основа науки о двоичном кодировании -n-мерный единичный куб. (R.Hamming)[8]

7 Изометрические вложения в кубические структуры Эффективное отображение на кубические структуры. Вложения плоских мозаик в реберный остов Z n. Работы- Деза, Долбилина, Штанько, Штогрина.[2,3,4]

8 Комбинаторные многогранники, кольцо граней Стенли-Райснера Для простого многогранника Р c гранями F1,…Fm и коммутативного кольца К с единицей кольцо граней Стенли-Райснера- факторкольцо К(Р)=К[v 1,…v m ]/ p, где р-идеал, порожденный мономами v i1,v i2,…v is, что F i1 … F is =Ø в Р, i 1

9 Триангуляции на кубических структурах и их динамика 6 типов примитивной триангуляции I 3. Марковские цепи в реберной динамике примитивных триангуляций в R 3 и R 4. Эргодические свойства. Распределение допустимых триангуляций в статистике Бозе- Эйнштейна. [18 ]

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

11 Принятые обозначения R n -n-мерное евклидово пространство. e 1,e 2,…e n -ортонормированный базис. Z n -подпространство целых точек в R n. I n -n-мерный единичный куб F(k)-k-мерная грань в I n (0-грани-вершины,1-грани- ребра, 2-грани-квадраты и т.д.) F n -множество всех граней I n.(k=0,1,…n). {0,1,2}-троичный алфавит. D n 3 - множество всех троичных кодов. {Ø,0,1,2}-четверичный алфавит. D n 4 – множество всех четверичных кодов. Sn- симметрическая группа подстановок.

12 Часть 1.Пирамида Паскаля и биекция F n D n 3 Пирамида Паскаля- 3d аналог треугольника Паскаля. Рекурсивная процедура вычисления триномиальных коэфициентов. Число в вершине- число крачайших путей в трехмерной решетке из (000) в данную вершину. Кодировка путевых перемещений :0- перемещение по х,1- по y, 2-по z. f k =C n k 2 n-k ; [19]

13 Биекция :мн-во всех n-разрядных троичных кодов мн-во всех граней n- куба. Е=e 1,e 2,…e n ; R n ; D=d 1,d 2,…d n ; d i {0,1,2}; F(k,p)=Пe i + Te j ; i:di=2;(k) j:dj=0,1;(n-k) Так – е 2 х е 4 х е 5 (трехмерная грань), транслированная в вершину в шестимерном кубе I 6. Кубант (кубический квант) – n- разрядный троичный код, однозначно определяющий размерность и положение грани в n-мерном единичном кубе I n. [21]

14 Троичное кодирование граней I 3. Вершины (0- грани): 001,010,… 111; Ребра (1-грани): 002,012,…211; Грани (2-грани): 022,122,…221; Весь I 3 : 222;

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

16 Бинарная операция умножения D1=d 11,d 12,…d 1n ; D2=d 21,d 22,…d 2n ; Поразрядная операция умножения задается следующей таблицей В префиксной записи: П(022121,121012)= Ø21Ø11;(псевдокубант) П(022121,220112)= ;(кубант).

17 Расширение алфавита и доопределение операции умножения. Расширенный алфавит {Ø,0,1,2}. Операция умножения (поразрядная) на расширенном алфавите задается следующей таблицей По определению операция – коммутативна, ассоциативна и дистрибутивна.

18 Свойства произведения кубантов. (D)-число разрядов с символом Ø. (П(D1,D2)=0 П(D1,D2) = D3-кубант-пересечение. (П(D1,D2) 0 = L min (D1,D2); П(121012,022121)=Ø21Ø11; П(220112,022121)=020111;

19 Доказательство свойства ω(П(D1,D2))=L min (D1,D2). Пусть В1 и В2 два различных n-разрядных двоичных слова (алфавит {0;1}), число попарно несовпадающих разрядов m. Тогда длина минимального пути по ребрам I n между вершинами с координатами В1 и В2 равна m.(Хэммингово расстояние). Заменим в словах В1 и В2 один из совпадающих попарно n-m разрядов на противоположный. Тогда (В1*,В2*)=m. Заменим этот разряд в В1* и В2* на 2. Образовались 2 кубанта D1 и D2 (соответствующие ребрам),такие что В1,В1* D1, В2,В2* D2 и ω(П(B1,B2))= (П(В1*,В2*))=L min (B1,B2)=m; С одной стороны L min (D1,D2) должно быть m, т.к. к числу точек каждого множества добавились новые. Но поскольку добавились только внутренние точки ребер, то минимальный путь до таких точек по ребрам н-куба будет m+ m. Из этого противоречия следует (П(D1,D2))=m=Lmin(D1,D2). И так для любого числа совпадающих попарно разрядов В1 и В2, а следовательно и для любой пары кубантов, т.к. любой кубант можно образовать из двоичного слова заменой ряда разрядов на 2.

20 D n 4 -моноид относительно умножения. Все n-разрядные четверичные слова с алфавитом {Ø,0,1,2} - (кубанты и псевдокубанты) образуют полугруппу относительно введенного умножения. Умножение обладает свойством идемпотентности П(D,D)=D; (Маслов [15]) Единица в этой полугруппе – слово 22…2 (соответствует I n ). Т.о. D n 4 -моноид.

21 Подмножество кубантов матрица парных произведений (смежностей) D1,D2,…Ds M ; m ij =П(Di,Dj); i,j=1,2…n; D1=112202; D2=121122; D3=122211; D4=120122; D5=002212; Ø ØØ22Ø Ø122 Ø Ø02211 M = Ø00112 симметрия D1,D2,D3,D4-образуют цикл (общие ребра);D5 отстоит на Lmin=1 от D2,D3,D4 и на Lmin=3 от D1; Mpp-обобщение матрицы смежностей для графов.

22 Часть 2.Хаусдорфова метрика на кубантах. Обобщение метрики Хэмминга. HH (D1,D2)= max {maxLmin (D1 D2), maxLmin(D2 D1)}; D1=022211; D2=112222; Lmin(D1 D2) П=ØØ2211 max Lmin(D1 D2)=2; Lmin(D2 D1) П=Ø122ØØ max Lmin(D1 D2)=3; HH (D1,D2)=max{2,3}=3;

23 Хаусдорфова метрика на кубантах. Операция Н-сжатия. Н-сжатие Di относитльно Dj (Di*/Dj) - для вычисления самого длинного из кратчайших путей от Di до Dj Max{ П(Di*/Dj,Dj), П(Dj*/Di,Di} = HH (Di,Dj);

24 Полная матрица НН-метрики для кубантов I 3. Размерно- лексикографическое упорядочение троичных кодов: 000,001,010,011, … 111, 002,012,020,021, … 211, 022,122,202,212, … 221, 222; Черный- НН =3, Тем.серый- НН =2, Свет.серый- НН =1, Белый- НН =0.

25 Структура НН-метрики для I n. Н(k,m)-минор матрицы парных НН-расстояний, содержит все расстояния между k- и m- размерными кубантами. r =[r1,r2]- диапазон значений НН- расстояний.r1,r2- целые;r1 r2.

26 Распределение НН-расстояний между кубантами для I 2 -I 10. Таблица M(r,n)-число пар кубантов в I n с r HH =r; M(0,n)=3 n ; M(n,n)=4 n -2 n-1; Гистограмма по вертикали- в логарифм. масштабе. Горизонталь- почти симметрия.

27 Расширение матрицы парных произведений кубантов. Дополнение злементов матрицы парных произведений значениями HH-расстояний (/ нн ) между кубантами. В расширенном виде матрица содержит полную топологическую и HН-метрическую картину множества кубантов ( в т.ч. HН-диаметр множества, исходные данные для построения HН-кратчайшего связывающего дерева и т.д.) Ранее приведенный пример M с расширением приведен ниже. D1=112202; D2=121122; D3=122211; D4=120122; D5=002212; / /2 1112Ø1/ /2 ØØ22Ø2/ / /2 12Ø122/1 Ø01112/ / /2 Ø02211/2 симметрия /0 Ø00112/ /0

28 Часть 3.Подмножества кубантов в I n. Булеан n-кубантов-множество всех двоичных m-разрядных кодов при m=3 n ; Каждому кубанту соответствует номер в размерно- лексикографически упорядоченной последовательности троичных n-разрядных кодов, этот номер равен номеру разряда в булеане, если данный кубант входит в рассматриваемое подмножество. Каждое подмножество кубантов двоичное слово в булеане. 000,001,010,…022,122,220,221, , ; 001, ;-поглощение кубанта 001 кубантом 022. После поглощений число различных подмножеств < 2 m ; m=3 n ; Для n=2 ; m=9;|B|=512; |B*|=47; число всех пар подмножеств: 2209

29 Особенности хаусдорфовой метрики на подмножествах кубантов. Необходимость перехода к евклидовой метрике. Добавление к вершинам (целым точкам) «полуцелых» точек для каждой грани (кубанта) /2 1 0 ;

30 Соотношения между НН и ЕН в I n. Кубанты:D1=220000; D2=112200;D3=111122; D4=000022;D5=002211; D6=221111;D7=022120; HH (Di,D7)=3; EH (Di,D7)=3; i=1-6; Подмножества: K1={D1,D2,…D6}; K2={D7}; EH (K1,K2)= 7/2; Мах равноудаленная точка имеет нецелочисленные координаты, т.е. нецелая.

31 Вычисление равноудаленных точек в комплексах из кубантов разной размерности. Мах равноудаленная точка – в множестве пересечений прямых, ортогональных к кубантам другого комплекса в общей для комплексов выпуклой оболочке. Точка и инцидентное ребро считаются ортогональными. Для I 2 –построение отрезков прямых и окружностей с доп.условиями (см. пример). К1={22};K2={12;00;01}; Окружность касается ребра CD(кубант 12) и проходит через точки А(кубант 00) и В(кубант 01) Из приведенного построения ЕН (К1,К2)=5/8; Для I 3 окружности заменяются сферами.

32 К вычислению полной матрицы ЕН всех пар комплексов I n Среди множества всех подмножеств кубантов возможны «поглощения»: так код в булеане (для I 3 ) 00… … ,т.к. кубант 002 содержит вершину 000. Возможность сокращения общего числа (2^3 n ) комплексов за счет «поглощения» кубантов меньшей размерности не приводит к принципиальному результату. Так для I 3 общее число комплексов 2^27(точнее 2^26+1) за счет поглощения сводится к ~2^25. Оценка возможности полных вычислений для I 3 2^52~4 10^15. Задача для суперкомпьютера.

33 Два метода вычисления ЕН для двух множеств целых точек в R 3 c. Волновой алгоритм на {Z 3,V 3 },где V 3 - множество простых (примитивных) ребер, не содержащих внутренних целых точек.(Отображения целочисленных множеств и евклидовы приближения. 2007). Учет невыпуклости пространства, приближение к Е-метрике (длина ломаной на простых ребрах)- приближенное значение хаусдорфова расстояния. Алгебраический метод на основе свойств моноида. Точная Е-метрика, пространство-выпуклое.(2009).

34 Сравнение двух методов для мн-ств Z n. Волна от мн-ва 1 до последней (по шагам) точки мн- ва 2 –р(2,1)=max min (2 1), от мн-ва 2 до п.т. мн-ва 1- р(1,2)=max min(1 2), р ЕН (1,2)=mах{p(2,1);p(1,2)}. В примере с волной (окр.=2) р ЕН ~7,3006;(окр.=3)~7,2110; точ. p EH (1,2)=2 13~7,2110;

35 Часть 4.О подходе к задачам синтеза на кубантах Формирование в R n c (c множеством вершин в Z n ) конечного множества S комплексов кубантов K1,K2,…Km с заданными топологическими и метрическими условиями, а также на мощности множества S и комплексов кубантов. Формирование - представление, вычисление, преобразование, верификация.

36 О расширении некоторых понятий. Выпуклая оболочка комплекса внутри I n -кубант минимальной размерности,в который вложим комплекс. (рис.1.Выпуклая оболочка комплекса {000000,011111}=I 5 ) Связность-расширение понятия связности кубантов(k- связность)-общность граней не меньшей размерности чем k.(рис.2.2-связность) Путь-расширение понятия пути.Путь по ребрам-1-путь, путь по двумерным граням-2-путь и т.д. Минимальные k-пути. (рис.2.)- 3-путь

37 Примеры k-связности и k-пути. 2-связность комплекса кубантов. 3-путь минимальной длины из А в В внутри комплекса. Длина пути - 16.

38 Гамильтоновы циклы(HC(n)) на I n как циклы 1-кубантов. Представления гамильтонова цикла: Вершинное Реберное В случае реберного представления гамильтонова цикла выполняются: П(D i,D i+1 )=v i ;(v i - вершина n-куба) (П(D i,D i+2 ))=1;

39 Рекурсивная процедура генерации НС(n) HC(n+1). Склейка двух НС(n) HC(n+1); Склейка попарно двух ортогональных два ортогональных в следующей размерности. При n>3 I n cодержит по крайней мере два орт. НС. Гипотеза: I 2n (n>1) содержит n орт.НС

40 Циклические пути с неповторяющимися кубантами. Обобщение гамильтонова цикла-цикл по всем k- кубантам на k+1-кубантах. Динамическая интерпретация пути- «шаги землемера» в смежную грань. В «распоре»- ребро,квадрат, куб и т.д.(кубанты).

41 Пример топологического «строительства» Кубическая бутылка Клейна из панелей- комплексов гиперграней. Нумерация всех комплексов гиперграней и правил их сборки. Отображение в памяти компьютера.

42 Комплексы из гиперграней I 3 10 типов не гомеоморфных комплексов из гиперграней. 64 типа различных по положению в I 3 (различны коды кубантов).

43 Комплексы в I 4

44 Вычисление (построение) комплекса гиперграней в I n Исходные данные: размер,структура, метрика. Выходные : Комплекс(ы) кубантов или пустое мн-во. Алгоритм вычисления с помощью таблицы возможностей. Пример из I 4 : размер-4, цикл, число минимальных путей, отличных от 0 равно 2 {0222;2202;1222;2212;} 0хххх0хххх0хххх01хххх1хххх1хххх1 ΣП(0/1) * * * * 1 2/2 * * * * 2 * * * * 1 * * * * 0 1/3

45 Часть 5.Элементы динамики в кубических структурах Огромное число вариантов изменения структуры кубических комплексов(с сохранением k-связности между всеми подкомплексами или без, с сохранением общего числа кубантов или без и т.д.). Аналоги гомотопных преобразований. Изотропность и анизотропность преобразований.( Минск2007 ) Случайные преобразования-появление и исчезновение k-граней(кубантов) в n- мерных кубических комплексах.(Динамическая маркировка).

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

47 Пример маркировки. Случайный процесс в дискретном времени бросания множества целых точек, образования в каждый момент на этом множестве выпуклых оболочек (операция над кубантами) и развития общей перколяционной ситуации. Маркировки каждого 2- кубанта-момент рождения (1,2,… Z + ), длина ребер дерева Штейнера (L R + ) для локального связного множества.

48 Кодирование n-октантов, как расширение понятия кубанта Семиричный алфавит {Ø,Ø*,0,1,-1,2,-2} и множество n-октантов с одной общей целой точкой.(«-» вынесен как надстрочный символ). Табличное задание бинарной операции умножения кубантов в О n. Коммутативна, но не ассоциативна. Моноид на семиричном алфавите сохранение метрических и топологических свойств представления кубантов.

49 Октантная окрестность O n целой точки и комплекс кубантов на ней Все n-октанты, имеющие общую вершину (целую точку) образуют n-октантную окрестность этой точки. Любой комплекс октантов на окрестности – по к.м. 0-связный. Комплекс (рис)-1-связный. 22*1*,202*,02*2,2*02,2*2*0,2*02, 022, 202,212 (2-2-1=22*1*) Последовательный обход через 3- октанты(22*2*,222*,2*22*,2*2*2*, 2*2*2, 2*22,22*2,222)-3-путь в «разрешенном комплексом коридоре».

50 Матрица парных произведений кубантов в O n Множество кубантов в O 4 : {21*22;122*2*;2*212; 1*2*2*2*}; и матрица парных произведений (принятые обозначения -1=1*;-2=2*): 21*22 122*2* 2*212 1*2*2*2* 21*22 1Ø00 0 Ø12 Ø 1* *2* Ø2Ø0 Ø*0 2*2* 2*212 1* 0 Ø 0 1*2*2*2* Минимальные пути: Ø 1;Ø* 2; Множество-несвязное.

51 3-пути в октантных коридорах Полупрозрачные 2-грани открыты для прохода. Вариант древовидной структуры возможных 3- путей(3d). Изменения в октантных окрестностях в дискретном времени. (3d+1)

52 Один из вариантов топологической интерпретации алгебры Фробениуса октантными структурами Методы алгебраической топологии в теоретической физике – наиболее активная область исследований. [9,13- 15] Топологическое представление алгебры Фробениуса (АФ) наиболее полно дано А.Лаудой.[10] Общепринятые операторы АФ и октантные структуры. (рис)

53 Кодирование операторов через октантные структуры Оператор комплекс кубантов в О n (х 1,…х n ); Ситуация на стыках вычисляется как произведение. Рис. пример кодирования в О 3.

54 Марковские процессы-перестройки кубантов и состояния О n В R 3 общее число состояний О 3 равно 2 36, где 36-число 2-граней в О 3. Появление и исчезновение 2- грани – детерминированное или(и) случайное событие. Зависимость структуры ( радиус связности, род границы и др.) «большого» комплекса от процесса перестроек. Эргодичность процесса обобщенная картина динамики.

55 4d схема топологических коридоров в дискретном времени. Ось дискретного времени. Два различных 3- пути (коридора) за 4 дискретных момента времени. Условия допустимости (открытости соответствующих граней) для коридора не отображены.

56 Генерация комплексов в R n c. Склейка (join) комплексов из O n (x,y,z). Самоподобие и появление новых свойств пространства. Пример R 3 c формирование самоподобной картины со свойством перколяции. Расчеты результирующей топологической картины и определение общих свойств связности операции над кубантами в октантах.

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

58 Машинное представление кубантов Машинное представление четверичного алфавита: Ø 0;0 1;1 2;2 3 При двоичном представлении этого алфавита операция умножения кубантов совпадает с поразрядной(битовой) операцией логического умножения 2n-разрядных двоичных слов. Машинное табличное представление умножения

59 Машинное представление кубантов в O n Машинное представление семиричного алфавита: Ø 0;Ø* 1;0 2; 1 3;2 4; -1 5; -2 6; Машинное табличное представление операции умножения х

60 Основные структуры данных. Текстовый вид входных и выходных данных: {[ ] ( )( )…( )[ ]( )( )…}…{…} { }-комплекс из n-кубов; [ ]-координаты n-куба в составе комплекса; ( )-кубант в составе n-куба;Алфавит {Z,0,1,2} Основные структуры данных- набор классов. Класс «Куб» (координаты и набор кубантов) –реализация одномерный массив. Класс «Комплекс»(кубы в комплексе)-одномерный массив Реализация средствами библиотеки STL C++; Для кластерной реализации-представление кубанта как самостоятельного элемента: [идентификатор комплекса] [координаты n-куба] [кубант].

61 Основные функции Уровень кубантов (для двух кубантов): умножение и Н-сжатие. Уровень комплекса кубантов в n-кубе: вычисление матрицы парных произведений кубантов и следствий из нее-топологическая и НН-метрическая структура комплекса. Уровень комплекса из n-кубов: вычисление ЕН- расстояний между комплексами в Rn. Геометрические операции с n-мерными векторами-библиотеки Intel MKL,BLAS.

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

63 Некоторые обобщения Кубант обладает полиморфными свойствами: Четверичное n-разрядное слово. Представляет геометрический объект (n-мерный куб и его грани). Допускает рассмотрение как точка гиперметрического пространства с Хаусдорфовой метрикой (обобщение метрики Хэмминга для двоичных кодов). Представляет элемент топологических комплексов. Вместе с расширением (псевдокубанты) образует алгебраическую структуру (полугруппу с единицей- моноид ) относительно введенной операции умножения. Разряды слова с символом 2 можно рассматривать как обощение q-битов (значения 0 и 1 и все действительные числа отрезка 0,1) и в целом кодирование как полуквантовое.[12] В машинном представлении кубант 2n-разрядное двоичное число, к которому применим весь арсенал машинных операций. В целом эффективная масштабируемость ( в размерности n пространства).

64 Вычислительные особенности Выполнение основной операции (умножения) сводится к поразрядной операции логического умножения над 2n-разрядных двоичных кодов практически неограниченной длины- поразрядное перемножение стрингов потенциально может быть реализовано за один машинный такт. Совмещенное вычисление данных о связности и длине кратчайшего пути между кубантами. Вычисление матрицы парных произведений (обобщение матрицы смежностей) для комплекса из m кубантов имеет сложность m 2. Вычисление Хаусдорфова расстояния между n-мерными кубантами вместо задачи экспоненциальной сложности 2 n сводится к задаче сложности n.

65 Вычислительные особенности для суперкомпьютеров кластерного типа Линейный характер увеличения длины слова кубанта от размерности пространства n и поразрядные операции над кубантами позволяют задать вопрос об оценке предельных возможностей современных кластерных суперкомпьютеров в задачах подобного класса и на ближайшую перспективу при условии сохранения общих тенденций развития их архитектур. В качестве самого упрощенного (начального) подхода рассмотрим первый этап в задаче анализа структуры M комплексов (каждый по m кубантов) в n-мерном пространстве – вычисление матриц парных произведений.

66 Для оценок общих ресурсов по оперативной памяти и производительности необходимо учесть, что каждый кубант сопровождает значительный объем данных во много раз превосходящий представление его геометрико-топологической структуры. Обработка этих данных на данном этапе не рассматривается, но в оценке объема оперативной памяти они участвуют. Будем считать, что их объем 2 n v, где n- размерность пространства, а v-некоторая постоянная. Тогда грубая оценка оперативной памяти для хранения исходных данных в байтах Mm(2n/8)2 n v (при v=100 байт V 0 =100Mm(n/4)2 n ;а выходных данных (матриц) V 1 =Mm 2 (n/4); Оценка общего числа операций для одноразового вычисления всех M матриц парных произведений для комплексов из m кубантов Q= Mm 2 (n/4).При n=10; M=10^3;m=10^3; Q~10^10;(в настоящее время производительность нескольких процессоров) Sv 0 ~10^5 10^3 10^3=10^11

67 Часть 8. Инструментальный комплекс «Топологический процессор» Основная цель - разработать математическое и программное обеспечение для инструментальной системы, реализующей операции анализа и синтеза на многомерных кубических структурах, максимально используя методы совмещения и распараллеливания вычислений на архитектурах современных и перспективных суперкомпьютеров. Работы ведутся в НИВЦ МГУ с 2005 года. Программное обеспечение на С++.Графика openGL,VRML. Начало реализации на системе «Чебышев». («Волна» на решетке )-2008г Основные публикации по теме за прошлые годы: Рябов Г.Г.Метрические и топологические волны на решетках.//Изд. НИВЦ МГУ Алгоритмические основы топологического процессора.// Труды МСО-2005.МГУ. Рябов Г.Г.,Серов В.А. Отображения целочисленных множеств и евклидовы приближения.//Выч. методы и программирование.2007 Ryabov G.,Serov V. Simplicial-lattice model and metric-topological constructions.// Proc. IX PRIP-conference.Minsk.2007 Рябов Г.Г.,Серов В.А. Компьютерные комбинаторно-топологические построения и их преобразования.//Информационные технологии и выч. системы.РАН.2008

68 Схема работ по инструментальному комплексу «Топологический процессор».

69 Текущие технические задачи Разработка набора макроопераций на основе алгебры кубантов для инструментальной системы «Топологический процессор», являющейся инструментом фундаментальных исследований в части построения примеров и контрпримеров с определенными свойствами. Программная реализация и верификация набора макроопераций «Алгебра кубантов» для суперкомпьютера МГУ «Чебышев». Полное документирование математического и программного обеспечения «Алгебры кубантов». Подготовка и выпуск методического пособия по «Алгебре кубантов».

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

71 Литература. 1.Новиков С.П. Топология. Москва-Ижевск.РХД Долбилин Н.П.,Штанько М.А.,Штогрин М.И. Кубические многообразия в решетках.// Изв.РАН.Сер. матем вып Деза М.,Штогрин М. Вложение графов в гиперкубы и кубические решетки.// Успехи матем. наук Деза М.,Штогрин М. Мозаики и их изометрические вложения.// Изв. РАН.Сер. матем Бухштабер В.М. Кольцо простых многогранников и дифференциальные уравнения.// Трды матем. Ин-та РАН Кузнецов С.Д.,Кудрявцев Ю.А. Математическая модель OLAP- кубов. //Программирование Pedersen T.B. Multidimensional databases.// Industrial Information Technology.Handbook Hamming R.W. Error detecting and error correcting codes.// Bell system Tech.Journal (2) Baez J.,Lauda A. A Prehistory of n-categorical Physics.// arXiv: v1 [hep-th] 18 Aug Lauda A. Frobenius algebras and planar open string topological field theories.// arXiv: math( v1) [math QA] 18 Aug Stanley R. Combinatoric and Commutative Algebra.// Birkhauser Manin Yu.I. Classical computing, quantum computing and Shors factoring algorithm. // arXiv: quant-ph/ v1. 2 March 1999.

72 13.Ambjorn J.,Jurkevicz J.,Loll R. The Universe from Scratch. // arXiv: hep-th/ v3. 14 Oct Coecke B., Quantum picturalism.// arXiv: v1[quant- ph] 13 Aug Литвинов Г.Л.,Маслов В.П.,Шпиз Г.Б. Идемпотентный функциональный анализ. Алгебраический подход. Математ.заметки. 69:5(2001), Ryabov G.,Serov V., Simplicial-lattice model and metric- topological constructions.// Proc. of IX Conf. on Pattern Recognition and Inf. Processing. V2. Minsk Рябов Г.Г. О путевом кодировании k-граней в n-кубе. //Вычислительные методы и программирование N Марковские процессы в динамике примитивной триангуляции в пространствах R3 и R4.//Вычислительные методы и программирование N1, О четверичном кодировании кубических структур.// Вычислительные методы и программирование N2, Хаусдорфова метрика на гранях n-куба. //Фундаментальная и прикладная математика.2009.(в печати) Алгебраическое представление кубических структур и супервычисления.//Сб.Программные системы и инструменты. ВМиК МГУ ,12-26

73 Приложение 1.Генерация комплексов кубантов внутри I n (O n ). 1.Общие условия(ОУ) на множество комплексов. 2.Условия внутри комплексов.(УВК) 3.Условия между комплексами.(УМК) 4.Диагностика совместимости условий.(ДСУ) Рассмотрение на примере построения(вычисления) максимального числа непересекающихся минимальных (по длине) k- путей из одной вершины в другую n-мерного куба с максимальным разнесением их друг от друга.

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

75 Формальная постановка для I 9. Общие условия: размерность n=9;заданы вершины D1=(00…0) и D2=(11…1); определить три k-пути (три множества кубантов) K1{А1,A2…Am};K2{В1,B2,…Bm};K3{С1,C2,…Cm} размерности k=3 в I 9 таких, что m-min и выполняются УВК: dimП(Аi,Ai+1)=2; dimП(Bi,Bi+1)=2; dimП(Ci,Ci+1)=2; для i=1 m-1; П(A1,D1)=D1;П(B1,D1)=D1;П(С1,D1)=D1; П(Am,D2)=D2; П(Bm,D2)=D2; П(Cm,D2)=D2; УМК:П(Ai,Bi)=Ø;П(Ai,Ci)=Ø;П(Bi,Ci)=Ø; i=1 m; HH (Ai,Bi)= HH (Ai,Ci)= HH (Bi,Ci)=max;i=1 m; Кратчайший путь по ребрам(1-путь) между D1 и D2 равен 9, по квадратным граням (2-путь) – 8, по кубическим граням (3-путь)-7. Отсюда m=7; Общий вид Ai и Ai П= dim П=2;

76 К решению задачи Кубантный тензор- размер 9х7х3, где 9- размерность куба, 7- длина кратчайшего пути, 3-число путей. Простейший вид матрицы 9x7 (кубанты располагаются столбцом в лексикографическом порядке слов), выполняются УВК: K

77 К решению задачи Куб как объект с осевой (00…0,11…1) симметрией организация по той же схеме матриц К2 и К3 приводит к : К1 К2 К Выполняются все условия поставленной задачи при любой одновременной перестановке столбцов в К1,К2,К3 (коммутативность умножения), кроме максимальной удаленности друг от друга.

78 Хаусдорфова метрика в рассматриваемой задаче. Операция Н-сжатия не коммутативна и перестановки столбцов в к- тензоре могут менять р НН между кубантами в путях. На рис.слева показаны значения НН для вышеприведенного решения. Они максимальны для 9! перестановок столбцов.

79 Приложение 2. О некоторых графических отображениях кубических структур Основные цели графического отображения в рамках рассматриваемых методов: Визуальная ориентация пользователя в многомерных структурах. Для различных задач – различные методы. Выход в открытые графические системы (VRML) с полным набором их средств визуализации. Рис. традиционный метод отображения для I 6 (c кластеризацией вершин по 8).

80 Реперно-ориентированные отображения Более привычное для глаза восприятие граней в n-мерном кубе (меньший разброс в метрике ребер). Вариация репера вариация отображения. Рис. плоский репер и отображение вершин и ребер 9-мерного куба.

81 Кубанты и комплексы кубантов 3d-репер, цветовая идентификация, выход в VRML- оперативный инструментарий для отображения кубантов и комплексов из них. Рис.Отображения I 6 и решения задачи о 3- путях (приложение 1).

82 Приложение 3. 3-пути сквозь случайную О 3. Постановка задачи. Задан октант, в нем 2-грани двух типов ( кодировка: 0-закрыты,1-открыты – рис.серый цвет). Вычислить кратчайший(ие) 3-пути между входами (-1,.,.) и выходами (1,.,.)-число и их длину, проходя через открытые 2-грани.

83 К постановке задачи. 36-и разрядный двоичный код отражает какие грани открыты (1) и закрыты (0) для 3-путей. На множестве всех возможных разбиений всех 2-граней О 3 построить распределение кратчайших 3-путей по числу и длине. Для каждого кода вычислить топологический тип.

84 Допустимые кратчайшие 3-пути и их длины Для дальнейшего изучения марковских процессов в динамике случайного поведения 2- граней необхдима матрица переходных вероятностей между допустимыми состояниями.(20х20)

85 Допустимые топологические типы Соотношение числа входов и выходов. Структуры кратчайших связ. деревьев. Число изолированных деревьев. Характеристика каждого дерева. Дальнейшие расчеты на «Чебышеве».

86 Конец презентации по результатам проекта за 2009 г, поддержанного грантом РФФИ офи_м. Научно-исследовательский вычислительный центр МГУ