[Из песочницы] Компьютер из маленьких фей
(Вычислительная машина с универсальной архитектурой)
Сказка ложь, да в ней намек…
• Найти Декарта; • В стране Лилипутов; • Бактериологическая почта; • Арифмометр в юбке; • Компьютер из маленьких фей.
Найти ДекартаДо нас дошла история, что известный философ в поисках свободного времени для размышлений и способа решения бытовых трудностей записался в армию. Там, между переходами, он, бывало, забирался в слегка протопленную голландскую печь, где, наконец, мог найти уединение со своими мыслями. Как и многие математики, Декарт питал взаимную слабость к общению с юными особами, одной из которых, чье имя слишком известно, чтобы о нем здесь упоминать, как-то, случайно проезжая мимо лагеря, захотелось повидаться со своим другом-философом. Но как его отыскать? Палаток было больше тысячи — за вечер все не обойдешь, да и титул не позволял. Надеюсь, читатель простит мне некоторые неточности в знании военного уклада, но пусть армия состояла из десяти полков, каждый полк из десяти батальонов, а в каждом батальоне было десять рот по десять человек и ротным во главе.Разумеется, в каждом подразделении был свой писарь и несколько «курьеров». Пользуясь высоким положением, путница попросила сделать запрос из штаба армии. Будучи размноженным писарем, он поступил в штабы полков. Там его размножили писари полков и разослали по батальонам, откуда подобным образом запрос поступил в роты. Ротному офицеру, под чьим началом служил Декарт, оставалось только послать положительный ответ вместе со своим подчиненным прямо в главный штаб. Солнце даже еще не успело сесть, а вечер обещал быть теплым и безмятежным.В качестве упражнения постарайтесь назвать:
а) третью сверху от кольца станцию красной ветки Московского метро; б) станцию, связанную ассоциативно с «теплом»; в) станцию, название которой ассоциировано с «холодом».
В Стране Лилипутов На одном не очень большом и не слишком маленьком острове в Тихом океане располагалось сразу два государства: Страна Лилипутов и Страна Великанов. В каждой из них было огромное количество городов со своими районными и областными центрами, несколькими метрополиями и ровно по одной столице. Жили они, в общем-то, мирно, в основном, потому что лилипуты устраивали свои поселения в недоступных для великанов уголках острова, а великаны просто не способны были из-за своих размеров заметить существование лилипутов.Но вот в один прекрасный день (в это время на острове была глубокая ночь) конгресс UN провозгласил равенство всех рас. Словно по мановению волшебной палочки лилипуты значительно подросли, а великаны изрядно измельчали, и все проснулись обычными людьми на этом не очень большом и не слишком маленьком острове. К счастью, это оказались две очень разумные нации: они сразу же пришли к идее объединить свои государства и произвести заодно новое административное районирование. Теперь немного о том, каким это районирование было. Остров представлял собой узкую вытянутую полоску суши, так, что все города на нем располагались вдоль единственной дороги.
Статусы районных центров были распределены между городами в каждой стране так, что крайний левый имел этот статус, любой город, либо сам был районным центром, либо располагался по соседству с таковым, любые два близлежащих районных центра были отделены друг от друга в точности одним или двумя городами, не обладавшими этим статусом.
По такому же принципу некоторые районные центры имели статус, в том числе и областных, а некоторые областные — в том числе и метрополий.
Описанное административное деление признавалось всеми как наиболее эффективное для управления и жизни. Однако, просто назначить районными, областными центрами и метрополиями нового государства, не говоря уже о столице, города, носившие такие статусы прежде, означало бы разрушить удобную структуру районирования (рис. 4).
Алгоритм действия в этом случае может быть таким:
1 шаг. Сохранить статус всех районных центров Страны Великанов в объединенной стране. Между назначенными таким образом районными центрами лежат не более двух городов Страны Великанов, однако могут вклиниваться целые куски Страны Лилипутов.
2 шаг. Сохранить статус тех районных центров Страны Лилипутов, которые не оказываются граничащими в объединенном государстве с районными центрами, унаследованными от Страны Великанов.
3 шаг. Локально выделив «некоторые» участники (длина каждого из них не превышает 5) подходящим способом назначить среди их городов районные центры.
Все перечисленные шаги локальны: назначить город на роль районного центра или нет, зависит лишь от небольшого участка, окружающего этот город, поэтому все действия могут выполняться «параллельно» и процесс занимает 0(1) времени независимо от общего количества городов. Остается только повторить его для остальных уровней административного деления.
Всего новое районирование занимает 0 (lnN) времени, где N- общее количество городов. Подобный метод «работает» не только на линейных государствах: подготовленному читателю предлагается обобщить его на случай плоских объектов, а также выяснить, сколько времени занимает введение административной структуры «с нуля».
Бактериологическая почта Перебои в работе почтовых служб — головная боль многих рядовых граждан, да и самих почтовых работников. Прежде чем описать некоторый метод, в определенных условиях улучшающий обслуживание в этой сфере, изложу упрощенно, как работает обычная почта. Автор еще помнит те времена, когда послания не набирались между салатом и супом в обеденный перерыв: они писались на бумаге, обдумчиво и со смыслом. Запечатанный конверт нужно было нести на почту, и каждый раз по утрам, почти как под елку, заглядывать в свой почтовый ящик. Сельский почтальон был уважаемой всеми должностью, а письма вместе с чувствами часто хранили изысканные ароматы женских духов.Будем считать, что районирование, принятое почтой бинарное: ток, вся страна делится на западную и восточную части, а те, в свою очередь, на южную и северную, и так далее.
Изначально все письма поступают на главную сортировочную базу, где разделяются на адресованные в восточную и западную часть страны. Административное деление стоит производить так, чтобы по вероятности эти порции писем были примерно равны. Все письма, адресованные в восточную часть, отправляются затем на сортировочную базу восточной части, а в западную — западной. Эти сортировочные базы принимают в среднем вдвое меньше писем, чем поступает на главную, поэтому складов оборудования и людских ресурсов на каждой из них вдвое меньше.
Дальнейшая сортировка происходит аналогичными методами, пока не дойдет до сельских почтовых офисов, где вряд ли нужно больше одного почтальона и сторожа. Описанная схема превосходно и экономично работает до тех пор, пока письма рассылаются «равномерно» по всей стране. Но вот беда, перед «Рождеством» вся страна отправила письма в маленький лапландский поселок, где живут только Дед Мороз и Санта Клаус, причем, и тому и другому писем адресовано примерно одинаково. Они как-то прошли сортировку на вышестоящих уровнях и все сто пятьдесят миллионов обрушились на одного бедного почтальона Лапландской деревушки. Стоит ли спрашивать, где велосипед, который вы просили на прошлое рождество,- да местный почтальон их до второго пришествия не разберет! Чтобы наладить сообщение в зимние праздники, опишу несколько футуристически устроенную почту. Принцип сортировки этой почты чем-то напоминает задачу районирования, основываясь на вложенных контейнерах, и происходит не «сверху вниз», а в основном «снизу вверх». Образующиеся при этом контейнеры схематически показаны на рис. 8. Каждый контейнер отвечает административному району некоторого уровня и содержит в точности один или два контейнера меньших уровней, а контейнеры самых низших уровней содержат письма, в них адресованные.
Сортировки на каждой стадии можно производить очень быстро, если задействовать сами контейнеры. Представьте, что контейнер — это оболочка бактерии. Ее генетический код хранит информацию о соответствующем ей административном уровне, а внутри плавают одна или две другие бактерии поменьше.
Тогда весь процесс промежуточной сортировки заключается в слиянии бактерии с одинаковыми пометками. Если две участвующие в слиянии бактерии имели lnK уровней вложения (K≤N), то оно занимает 0(lnK) времени. Всего происходит 0(lnN) промежуточных сортировок, поэтому одним контейнером их результат будет представлен через 0[(lnNl)(nN)] времени. После этого остается только разделять соответствующие контейнеры, разрывая всякий раз оболочку внешней бактерии (рис. 10), что не занимает много времени и, может быть, выполнено одним почтальоном-биологом.
При описанной реализации почты в Лапландскую деревушку без опоздания пребудет «мешок» с отдельным пакетом писем для Деда Мороза и отдельным для Санта Клауса.
Подготовленному читателю предлагается усилить результат.
1) Заметьте, что для следующего слияния самых внешних бактерий не обязательно дожидаться пока пройдут все их внутренние рекомбинации. Реализуйте почтовую рассылку тем же количеством бактерий за lnN времени.2) Используя методы этой и предыдущей главы, рассортируйте произвольное ленейно упорядочнное N-элементное множество за 0[(lnN)(lnN)] средствами 0(NlnN) бактерий.
Арифмометр в юбке
Всем известна способность представительниц прекрасной половины человечества, даже выполняя несколько дел сразу, в каждом из них проявлять исключительную шустрость и точность. Пользуются они такой способностью не всегда, но без нее с детьми никак: ведь в среднем нужно одновременно гладить белье, варить суп, присматривать за маленькой пронырой, да еще успеть по телефону переброситься «парой слов» со своей лучшей подругой. Эти качества позволили пол века назад создать из рассаженных в кинотеатре женщин суперкомпьютер, на котором был успешно выполнен расчет первой атомной бомбы. Увы! Рожденное созидать, не всегда созидает, однако сам метод заслуживает некоторого внимания. Приспособим его к умножению двух двоичных чисел. Например, пусть требуется умножить число длины 3 на число длины 5, как на рис. 11.
При умножении обычным «школьным» способом в столбик, задача попросту сводится к сложению нескольких чисел. При сложении же столбиком возникают «переносы» в следующий разряд, причем величина, перенося, может значительно превышать единицу (рис 12а):
Вместо того, чтобы общий перенос прибавлять к общей сумме следующего разряда можно, как только необходимость в переносе возникает, прибавлять его к самим суммируемым числам следующего разряда (рис. 2 б) Теперь представьте, что суммируемые числа из рис. 11 поразрядно написаны в блокнотах пятнадцати женщин (рис. 13)
Алгоритмом действия любой женщины будет дождаться результата суммы «сверху» и величины переноса справа и вычислить их сумму с хранимым в ее блокноте числом, после чего эту сумму за вычетом нового переноса отправить вниз, а сам перенос влево (рис. 14)
Не все женщины сразу задействованы в расчетах. Вычисление начинается с крайней правой в верхнем ряду: ей не от кого ждать промежуточных данных. Множество задействованных женщин в зависимости от времени показано на рис. 15.
Упомянутые множества получаются смещением трафарета Т вдаль шаблона S (рис. 16)
Этот факт наводит на мысль, что для вычисления произведения можно вместо 15 женщин S использовать всего трех из Т, причем величина их блокнотов и сложность производимых операций практически остаются теми же. Можно так же считать, что все блокноты на начало расчета пусты. Разряды первого числа будут подгружаться в верхний модуль Т, откуда по мере выполнения действий перетекать в нижние модули, а разряды второго оказываются удобнее подавать по скользящему вниз кондуктору (рис. 17)
Алгоритм действия модулей есть небольшое видоизменение алгоритма из рис. 14, он приведен на рис. 18. Данным методом можно перемножать числа любой длины. Количество женщин, которое при этом понадобится равно длине одного из сомножителей, причем совсем не обязательно держать большой расчетный штат все время: если отдел кадров работает быстро, то трафарет можно достраивать по мере необходимости уже после того, как начали поступать разряды сомножителей, даже не зная настоящей длины перемножаемых чисел. Скорость выполнения умножения таким способом оказывается не то что линейной — она почти поточная: разряды произведения появляются с небольшой задержкой после загрузки соответствующих разрядов сомножителей (если забыть про «консервные» эффекты).
Компьютер из маленьких фей Предыдущие главы служили иллюстрацией реализации алгоритмических задач с быстротой, недостижимой для любой к настоящему времени созданной вычислительной машины. Конечно, нельзя утверждать, что любой алгоритм может быть подобным образом ускорен: как отмечал мистер Нейман, любая вычислительная машина создается для решения определенного, зачастую очень узкого, круга задач и вне его может быть крайне неэффективной. Примером последнего служат аэродинамические трубы — эффективнейший метод решения уравнения движения жидкости, однако вряд ли пригодный для чего-либо другого. Но если во времена появления первых электронных вычислительных машин переключательные элементы (лампы, транзисторы) были чрезвычайно дороги и ненадежны, так что большую часть используемой информации приходилось хранить на пассивных носителях (магнитных лентах или перфокартах), то в настоящее время ситуация коренным образом поменялась. Бытовой флеш-носитель хранит огромное количество информации исключительно на переключательных элементах. Однако транзисторы последнего, в отличие от транзисторов внутри процессора, изменяют свое состояние крайне редко. Биологи же отмечают, что практически невозможно определить какой-либо участок нервной ткани, вся функция которого заключалась бы только в хранении информации — любой нейрон так или иначе включен в активные вычисления.Первый вопрос, побудивший автора к разработке приведенной ниже в несколько аллегорической форме вычислительной модели, -в каких случаях увеличение задействованных переключательных элементов ведет к увеличению скорости выполнения задачи и как должна (может быть) устроена машина, реализующая такой принцип.
Второй вопрос и во многом сама упомянутая модель связаны с идеями мистера Неймана, изложенным в курсе работ, объединенных под названием «Теория самопроизводящихся автоматов». Я настоятельно рекомендую читателя познакомиться с какими-нибудь работами. Джозефа фон Неймана — одного из самых крупных и, увы, последних математиков-зеркал: он отражал действительность в математике (теория игр, работы в области логики и основаниях квантовой механики) и математику в действительности (атомная энергия, создание первых вычислительных машин). К сожалению, с середины семидесятых годов в предисловиях к математическим книгам уже редко писали «зачем».
Собственно, если в «Теории самопроизводящихся автоматов» обсуждались математические принципы устройства простейших одноклеточных организмов, то естественное развитие задачи было бы в установлении принципов, позволяющих существовать многоклеточным. Не кажется ли Вам удивительным, что ваши соматические клетки, по сути, имеют одинаковый генный код, однако, в процессе роста организма образовали большое количество разнообразных тканей. Теперь надеюсь, понятно, почему автор избрал такую аллегорическую форму: феи способны взмахом волшебной палочки создавать еще одну фею.
Итак:
1) Феечка (рис. 19) способна производить несложные вычисления и хранить некоторое небольшое количество информации;
2) Все феи по сути устроены одинаково и каждая из них в процессе работы в состоянии поддерживать двусторонний канал связи с несколькими (ограниченным числом) феечками, общаясь, общаясь с ними с помощью определенного языка (множества команд).
В процессе общения феечка потенциально способна узнать любую информацию, которой владеет соединенная с нею каналом связи другая феечка;
3) При необходимости каналы связи могут прерываться по обоюдному согласию собеседников, однако на их образование наложим ограничение локальности: феечка может образовать канал связи с еще одной феечкой лишь в том случае, если они связаны через третью, причем образование нового канала связи не должно превысить их лимита для каждой из феечек.
4) При необходимости любая феечка способна создать еще одну феечку, соединенную изначально только с ней единственным каналом связи. Образование дочерней феечки не должно в итоге привести и превышению лимита каналов связи у материнской (рис. 21).
5) При необходимости любая феечка способна исчезать.
Эти основные пять правил в каждом конкретном случае должны быть дополнены точным описанием языка общения и правил действий феечек, образующих компьютер, как вида. На начало своей работы эти компьютеры состоят (чем вместе с поступающей в будущей внешней информацией полностью определяется их работа) из конечного числа феечек, для каждой из которых указано её внутреннее состояние и ведущие к ней каналы связи.
Вообще говоря, хотелось бы упомянутым компьютерам ставить задачи и получать от них какие-то результаты. Для этого дадим возможность феечкам образовывать наряду с внутренними каналами, каналы с внешними устройствами и дополним список правил:
3) Феечка способна устанавливать канал связи с внешним устройством лишь в том случае, если она уже связана с этим устройством через другую феечку (рис. 22)
Попробуйте теперь для любой машины Тюринга построить эквивалентный ей компьютер из подходящих фей. Последнее упражнение показывает, что для любой алгоритмической задачи найдется вид феи, способный ее решить, но этот вид совсем не обязательно должен быть в состоянии решать все алгоритмические задачи. Например, феи, которые ничего не умеют, прекрасно решают задачи, которые ни в чем не состоят, и только их. Однако, как и в случае машин Тюринга, существуют универсальные виды фей, своими конечными группами эмулирующие фей любого вида.
Приведу несколько примеров компьютеров из фей:
1) До некоторой степени всякий многоклеточный организм, где роль феечек выполняют отдельные клетки, а вычисление начинается в момент оплодотворения.2) Побеги на дереве появляются из почек побегов предыдущих лет, поэтому дерево можно разделить на участки — они и будут феечками, начальная — зародышевый побег в семени. В этом примере клетки дерева, как универсальные феички эмулируют более сложный вид фей.3) Сферу экономической деятельности людей можно разделить на ячейки- феички: фирмы, предприятия, конторы (корпорации общаются, плодятся и умирают- смотрите по этому поводу книгу С.Паркенсона). Люди и общество — ещё один пример, причем люди — универсальные вид фей для задач экономики.4) Появившиеся всевозможные социальные сети и их посетители вместе со вспыхнувшими по всему миру революциями — без сомнения талантливая реализация компьютера из маленьких фей и программы на нем. Не я один осознал уникально высокую скорость вычисления подобных машин — Привет вам, незримые «коллеги».5) Автору же такая машина нужна исключительно для работы с множествами и их свойствами, потому как обычный настольный «калькулятор» способен делать это, ну, очень медленно, однако в этом пункте преуспела пока только природа. Если вам показать какой-либо предмет, сколько времени потребуется вашему мозгу для его классификации? Сколько, по-вашему, вы различаете объектов и свойств (хотя объект — не более, чем ансамбль свойств)? Вряд ли хоть какая-нибудь последовательная машина с частотой в 40 Гц способна давать такие результаты.
На самом деле «задачу телефонисток» автор исследовал преимущественно в связи с экономическим обоснованием возможности реализации «компьютера из маленьких фей». Она получается, если взять достаточно много микропроцессов, скажем, величиной в тысячу транзисторов в качестве потенциальных фей и соединить их телефонной сетью, где вместо телефонисток используются модули из 5–7 транзисторов. Создание одной феей другой феи при такой реализации состоит в запросе у АТС выделить соединение с еще не задействованным в расчетах микропроцессором. Если бы такие компьютеры были построены, то, например, задачи волновой природы (поиск путей и расстояний, величины потоков) на графах, насыщенных ребрами, решались бы на них «намного» быстрее.
Напоследок предлагаю читателю, которому эта статья была интересна, для каждого ее параграфа построить подходящий компьютер из маленьких фей (на бумаге, конечно же) и формализовать в каждом случае приведенные вычислительные схемы.
