Растущая иерархическая сеть
Растущая ИС это сеть, число клаттеров которой растет согласно некоторому алгоритму. Этот рост будем связывать с операцией самокопирования ИС, которая заключается в следующем. Из двух, или большего числа клаттеров ИС собирает новый, устанавливает в себя, прокладывает связи и увеличивает свой размер на единицу. Рост ИС начинается с двух или большего числа клаттеров. Последовательность клаттеров, из которых собирается новый, назовем звеном цепи, или просто звеном. Новый клаттер собирается в процессе копирования элементами уровня носителя, связей каждого клаттера и узлов. Сборка ведется снизу вверх. Рост любой ИС можно условно разбить на три этапа.
- Первый этап - это рост от 2, 3, ... , до √P клаттеров.
- Второй этап - рост от √P , до Р клаттеров.
- Третий этап - репликация, создание одной, двух или
большего числа копий совершенной сети.
Рассмотрим все эти этапы на примере сети, ранга 3. Она содержит 256 носителей в клаттере. Стартовый размер сети может быть 2, 3 или более. Будем считать его равным двум. Первый этап.
Рис. 10. Старт сети 256
Алгоритм копирования следующий. На каждую связь и на каждый узел сети (узел - точка схождения связей) устанавливается носитель. В данном случае связь одна, узел всегда один. Всего два носителя на клаттере. Нужно собрать 256 носителей, поэтому переходим к следующему клаттеру. Копируем еще два носителя. Цикл закончился, он был пустым т.к. все имеющиеся на момент входа, клаттеры откопированы, а новый собрать не удалось. Здесь мы имеем 63 пустых цикла. На 64-м цикле и 128-ой по счету операции копирования, получаем 256 носителей. Из них собираем новый клаттер, устанавливаем в сеть, прокладываем связи.
Рис. 11. Собран первый клаттер
Теперь каждый клаттер имеет две связи, поэтому - три носителя с клаттера, девять за цикл. Здесь мы имеем 28 пустых циклов: 28*9=252. На 29-м цикле копируем два клаттера, получаем остаток. Остаток отбрасываем (см. ниже) 252+3+3=256+2. Собираем, устанавливаем, прокладываем.
Рис. 12. Собран второй клаттер
На каждый клаттер устанавливается 4 носителя, за цикл собирается 16.
Новый клаттер собирается за 16 циклов 16*16=256
Рис. 13. Собран третий клаттер
Пять носителей на клаттер, 25 с цикла - десять пустых циклов: 25*10=250 На одиннадцатом цикле, копируем 2 клаттера: 5+5=10. Берем 6 носителей и собираем новый. Здесь также получен остаток. Остаток отбрасываем (почему - ниже). И так далее. Доходим до 16 клаттеров. Теперь клаттер можно собрать за один цикл: 16*16=256. На этом первый этап заканчивается.
Рис. 14. Собрано 16 клаттеров
Переходим ко второму этапу. Допустим, сеть выросла до размера 71,
т.е. содержит 71 клаттер.
Рис. 15. Копирование фрагмента сети 256
В процессе копирования, для фрагмента сети изображенного на рисунке имеем: После копирования четырех клаттеров (длина звена = 4), получаем: (70+1)*4=284 носителя собираем новый клаттер, устанавливаем его в сеть, увеличиваем число связей на единицу (71). Остаток 284-256=28 носителей, остается лежать на узле и связях четвертого клаттера. Процесс копирования нового звена начинаем с последнего клаттера уже откопированного, т.е. с перехлестом. 28 носителей уже лежат на позициях, их копировать не нужно. Копируем 43+1=44 позиции и переносим все носители 28+44=72 в следующий на сборке клаттер. И так далее. Здесь важен следующий момент, в последнем копируемом клаттере первого звена возник остаток 28, формально можно его отбросить, а копирование следующего звена начать с него же и копировать с него узел и все связи - 72 позиции. Т.е. можно считать, что копирование происходит звеньями, на последнем клаттере звена остаток отбрасывается. Новое звено начинается с последнего клаттера предыдущего звена.
Дело в том, что эта математика имеет приложение, в котором носители рассматриваются как ресурс. Их остаток не может быть отброшен. Что и имеем. Действительно, в предыдущем звене, с последнего клаттера, было скопировано и установлено 43 носителя, в следующем звене берется остаток 28 и еще 44 (44, а не 43, т.к. была проложена связь). Получаем 43+28+44=115. По правилу отбрасывания остатка имеем 43 позиции с последнего клаттера предыдущего звена и 72 позиции с первого клаттера последующего звена: 43+72=115, т.е. в обоих случаях с граничного клаттера скопировано 115 позиций. Граничные клаттеры звеньев дают больший вклад (115>72), в дочерний клаттер, чем промежуточные.
Третий этап. Когда сеть 256 достигает совершенства, ее размер (число клаттеров в сети), становится равным весу клаттера Р (числу носителей в клаттере). Алгоритм роста не может больше работать, т.к. число связей плюс узел - становится равным весу клаттера, а копировать можно как минимум с двух клаттеров (в пределе с одного, но только на третьем этапе). Сеть приступает к заключительному этапу роста. Прежде всего, она добавляют по одной "свободной" связи каждому клаттеру, т.е. число его связей становится равным числу носителей в нем содержащихся. Будем считать, что максимальное число связей клаттера, равно его весу. Но, что такое связь? Ее можно представить как кабель, соединяющий два клаттера, с числом линий равным Р, который подключается к мультиплексору, обеспечивающему независимый обмен информацией между носителями. Здесь предполагается, что каждый носитель может быть связан в данный момент времени, только с каким ни будь одним носителем в другом клаттере. Для сети 256, добавочная связь на каждый клаттер, даст дополнительно 256 связей более низкого уровня, а т.к. клаттеров всего 256, то получается 65536 связей. Все они понадобятся при построении следующей ИС.
И, наконец ИСС переходит в режим репликации. Рассмотрим его подробнее. На последнем цикле роста сети, число операций копирования для сборки одного клаттера равно двум. В процессе роста сети, это число уменьшалось от 128 до 2. На последнем цикле, дочерний клаттер копировался с двух, а в конце цикла практически с одного материнского. Поэтому логично считать продолжением этого процесса операцию репликации, во время которой звено копирования минимально и равно единице, т.е. происходит точное копирование клаттер в клаттер, но с установкой в новую в сеть. Операцию репликации можно считать последней, предельной операцией копирования. Она состоит из одного или более циклов, т.е. ИСС создает еще одну, две или несколько собственных копий. Пусть для определенности сеть создает две копии (т.е. получается три ИСС). Каждая из них имеет 65536 свободных связей, две из которых идут на их (ИСС) соединение. Остальные понадобятся для дальнейшего роста. Итак, сеть вышла на новый виток эволюции, как ИС более высокого ранга.
Прежде чем перейти к математической реализации алгоритма растущей сети, уточним понятие цикла. С циклом сети связываем такую процедуру процесса ее самокопирования, когда копируются те клаттеры, которые имеются в наличии к моменту входа в цикл. Те же из них, что собираются в текущем цикле - в очередь на копирование не ставятся (исключение см. ниже). Алгоритм прохождения и финализации цикла может быть сформулирован в трех вариантах:
- Копируются все клаттеры, которые имеются в сети к моменту входа в цикл. Как только новый клаттер из оставшихся на копирование, по сумме позиций собрать становится невозможно, цикл завершается. При этом остаются не скопированные клаттеры из тех, что стояли на копирование по плану.
- Все то же самое, но как только новый клаттер из остатка собрать не получается, сеть заходит на следующий виток и финализирует цикл. При этом некоторые клаттеры оказываются скопированными дважды.
- Этот вариант, среднее между первым и вторым. Копируются клаттеры, устанавливаются в сеть, число связей растет. Если новый клаттер из оставшихся на копирование собрать невозможно, но общее число неоткопированных позиций превосходит половину веса клаттера, тогда сеть заходит на новый виток. В противном случае - нет.
Рассмотрим как пример сеть, с алгоритмом роста по третьему варианту. Пусть эта сеть, содержащая 20 клаттеров ранга 3, входит в цикл. Копирование идет с 13-ти клаттеров, составляющих одно звено, (13*20=260>256 остаток отбрасываем), клаттеров на копирование остается 7+1=8. Копируем их, так как 8*21=168>128 , заходим на второй виток и собираем еще один клаттер. На втором витке в процесс копирования будут вовлечены клаттеры, уже скопированные в данном цикле. Цикл может содержать от одного до двух витков он может быть пустым, когда все клаттеры скопированы, а новый так и не собран. Такой цикл состоит из одного звена и заканчивается на последнем клаттере, из стоящих в очередь на копирование в начале цикла. Нужно отметить следующее - в математической модели, клаттеры не обладают индивидуальностью, здесь не нужно рандомизировать их подачу на копирование для обеспечения эффективного кроссоверинга, достаточно только не копировать их дважды на первом витке.
При выборе алгоритма финализации цикла, важно чтобы он обеспечивал сети прохождение через все промежуточные гармонические стадии (с числом клаттеров, равным двойке в степени) и конечно достижение в финале совершенства. Как показывает математическое моделирование, третьему варианту следует отдать предпочтение, т.к. в этом случае рост ИС проходит ближе всего к гармоническим сетям. Кроме того, выясняется, что при заданном алгоритме и при различных сценариях финализации цикла, сеть проходит или почти проходит через все гармонические стадии роста. Т.е. они оказываются удивительно притягательными для растущей сети. Число циклов от одной точки роста до другой, слабо зависит от сценария.
Рост сети 256
Рассмотрим рост сети 256 на первом этапе от 2 клаттеров до 16. Вот пример программы подсчета числа клаттеров за цикл, в зависимости от номера цикла, реализованной в системе MathCAD:
Рис. 16. Алгоритм роста сети 256 от 2 клаттеров до 16
Здесь ceil(X) - ближайшее целое большее или равное X, ce(X) - ближайшее целое меньшее или равное X, cel(X) - ближайшее целое, меньшее X. Что представляет из себя функция U(C)? Это число клаттеров, собранных сетью за "С" циклов. U(133)=7, следовательно за 133 цикла собрано 7 клаттеров. C(i) - это номера циклов, соответствующие гармонической стадии роста сети.
Всего получается 156 циклов. Из них, пустых: 156-14=142. Соответственно, за каждый из оставшихся 14-ти циклов собирается один клаттер. Заходить на второй виток никогда не приходится. Сеть проходит четыре гармонические стадии роста - в момент старта, а также на 93-ем, 134-ом и 156-ом циклах, с числом 2, 4, 8 и 16 клаттеров соответственно. Переходим ко второму этапу.
Рис. 17. Алгоритм роста сети 256 от 17 клаттеров до 256
На этом этапе пройдено 15 циклов. Начало его сопровождается бурным ростом числа клаттеров. Это связано с тем, что уже за первый цикл, впервые с нуля собирается клаттер. Далее подключается правило второго витка, что еще более ускоряет рост. Для реализации прохода через гармонические сети понадобилась коррекция роста, но только в четырех точках, "близких" к гармоническим сетям.
Коррекция, представляла из себя малое возмущение в один клаттер, и была проведена на стадиях роста с числом клаттеров 20, 31, 65 и 127: ( 127+1)*2=256 (31+1)*8=256 (65-1)*4=256 Существует не одна такая коррекция, но результат, функция U(C) - тот же. Растущая сеть проходит через гармонические стадии 16, 32, 64, 128, 256. На последнем цикле, число клаттеров удваивается. U(14)=128, U(15)=256. Этот результат справедлив для сети любого ранга. Отметим также, что результаты работы алгоритма почти полностью совпадают со значениями функции:
 (8)
Назовем функцию U1(i) теоретической гиперболой сети 256. Этап заканчивается сборкой клаттера 65536. И, наконец, третий этап роста сети 256 - репликация. Здесь сеть собирает свою копию и прокладывает связь. Сеть 65536 - может стартовать. Подведем итог для сети 256. Всего имеем 156+15+1=172 цикла и восемь гармонических стадий роста: 2, 4, 8, 16, 32, 64, 128, 256.
Рейтинг публикации:
|
