Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Гимн однородным структурам
Читатели, наверное, заметили пристрастие авторов к однородным структурам с однотипно организованным взаимодействием. Это действительно так. Нас не перестают удивлять и восхищать огромные возможности, скрытые в этих простейших, структурах. Только что одномерная однородная, структура продемонстрировала нам свою способность к синхронизации без глобального синхронизующего, сигнала. Несколько ранее, в гл. 3 поливальные насосы включались на участках дач так, как нам этого хотелось. Здесь мы приведем еще несколько примеров из удивительного мира однородных структур. Отметим, что однородные структуры часто встречаются в биологии, а техника проявляет к ним особый интерес. Ведь однородные структуры легче производить, заменять и контролировать. Однородность и однотипность — идеал инженера. Вот почему в последние годы, особенно после появления микроэлектроники, так возрос интерес к однородным структурам. Мы думаем, что картина, описанная ниже, знакома всем читателям. В зале заседаний идет собрание. Председательствующий ставит на голосование какой-то проект или решение. «Прошу поднять руку тех, кто «за»,— говорит он. Поднимается лес рук. Подсчет числа голосов весьма трудоемок. Иногда председатель не справляется с ним и требуются специальные помощники — счетчики. «Кто «против»? — снова спрашивает председатель. И опять лес рук. И снова надо считать. Хорошо, когда одно из мнений собирает мизерное число сторонников. Тогда и считать не требуется. Общая картина достаточно красноречива. («Считать не будем? Я думаю, и так все ясно»,— говорит в этих случаях обычно председатель.) Но если «за» и «против» собрали примерно одинаковое число голосов, то публика начинает волноваться и требует перёголосования. Всегда возникает мнение, что счетчики ошиблись. Как избежать этой щекотливой ситуации? Можно ли 164 автоматизировать подсчет голосов и определение результатов голосования? Удастся ли создать «машинку для голосования», которая давала бы нужный результат независимо от числа голосующих? Ответы на все эти вопросы положительны. Все это можно сделать с помощью одномерных и двумерных однородных структур. Проиллюстрируем наше утверждение на наиболее простых примерах. Рассмотрим сначала простейшее голосование, при котором каждый его участник голосует «за» или «против», а окончательное решение принимается по простому большинству голосов. Тогда, очевидно, каждую пару «за—против» можно вычеркнуть из дальнейшего сравнения. Если вычеркнуть все такие пары, то останутся только те, кто проголосовал «за» (если их большинство), или те, кто проголосовал «против». Считать их число не надо. Для простого большинства хватает и одного лишнего голоса. Эту процедуру вычеркивания конкурентных пар легко реализовать на одномерной однородной структуре. Рассмотрим схему, показанную на рис. 5.5. Каждый автомат имеет два состояния, которые мы обозначим через а, b. Состояние а соответствует тому, что данный результат голосования еще не вычеркнут, состояние b — что он вычеркнут. На внешние входы автоматов поступают сигналы хi от участников голосования. При этом хi=1 означает, что i-й участник голосования проголосовал «против», a хi=0 — что он проголосовал «за». Если голосование происходит в специально для этого оборудованном месте, то сигнал от каждого голосующего поступает в наше устройство в результате нажатия им соответствующей кнопки на индивидуальном пульте. 165
Сигналы, передаваемые по горизонтальной шине между автоматами, являются для системы внутренними (рабочими). Работа автоматов в цепи задается табл. 5.1. Таблица 5.1
Поясним, как устроена эта таблица. В некотором такте работы на автомат Ai поступает входной сигнал Xi , равный 0 или 1, и один из четырех возможных рабочих сигналов. Сам Аi при этом находится в одном из двух возможных состояний (а или b). Значения входного и рабочего сигналов и состояние автомата определяют текущую ситуацию, которая записывается парой символов: значением рабочего сигнала, выдаваемого автоматом Ai в этой текущей ситуации, и новое состоянием, в которое он переходит. В начале работы системное устройство СУ, показанное на рис. 5.5 в виде кружка, выдает на боковой вход самого левого автомата цепи сигнал So. Все автоматы в начальном такте работы находятся в невычеркнутых состояниях а. Встретив первый автомат в состоянии а (в начальный такт работы это всегда будет крайний левый автомат в цепи), сигнал So переводит его в вычеркнутое состояние b. Если при этом на внешний вход автомата подавался сигнал «за», то далее по цепи будет вправо распространяться сигнал S1. Если же данный автомат имел на входе Xi=1 (т. е. сигнал «против»), то вправо будет распространяться сигнал S2. Сигналы S1 и S2 осуществляют поиск первого автомата, который мог бы составить вычеркиваемую 166 пару с отмеченным ими автоматом. Если при своем движении вправо сигналы S1 или S2 находят соответствующий автомат, то он переводится в вычеркнутое состояние, а рабочий сигнал становится равным S3. Этот сигнал есть свидетельство вычеркивания одной пары из множества голосующих. Сигнал S3 «проскакивает» через все оставшиеся автоматы цепи, ничего не меняя на своем пути. Его приход в СУ свидетельствует об окончании одного акта вычеркивания. Приход его в СУ заставляет системное устройство выдать на цепочку автоматов новый сигнал So. Окончание процесса вычеркивания произойдет тогда, когда сигнал S1 или сигнал S2 не найдут себе подходящей пары для вычеркивания. В этом случае на вход СУ поступит не сигнал S3, a S1 или S2. Появление сигнала S1 говорит о том, что большинство проголосовало «за», появление S2 — о противоположном результате голосования. Особым случаем является равенство голосов «за» и «против». В этой ситуации наше устройство посылает на боковой вход левого автомата цепи сигнал So, который «проскакивает» неизменным через все вычеркнутые автоматы и приходит на вход СУ. Это и есть сигнал о равенстве голосов. Отметим, что значение N нигде не фиксировалось и никакой роли для нас не играло. Устройство для подсчета голосов будет срабатывать верно при любом числе голосующих. Мы рассмотрели простейший случай голосования. Но и для более сложных случаев задача об определении результатов голосования оказывается разрешимой с помощью одномерной цепи автоматов, в которой сложность каждого автомата не зависит от того, сколько лиц приняло участие в процедуре голосования, а зависит лишь от вида голосования. Так, например, при голосовании по принципу 2/3 (решение принимается, если за него проголосовало не менее 2/3 голосующих) сложность автоматов не меняется, а лишь увеличивается до шести число различных рабочих сигналов. При одном «сканировании» с помощью сигнала So происходит вычеркивание тройки автоматов, на два из которых поступил сигнал «за», а на один — сигнал «против». Можно рассматривать задачу не с простым голосованием «за» и «против», а с выбором одного из К претендентов 167
по принципу большинства голосов. Это требует уже автоматов с четырьмя состояниями и восьми различных рабочих сигналов. При последовательном голосовании (например, сначала предлагается из трех претендентов B1, В2 и В3 выбрать либо B1, либо группу (В2, В3), и если выбран B1, то голосование заканчивается, а если группа, то на втором туре идет борьба между В2 и В3) требуется уже двумерная однородная структура. Такой же структуры требует и голосование, в котором каждый претендент на «призовое» место оценивается определенным коли-чеством очков. Видов голосования человечество придумало очень много. Но интересно, что все они (по крайней мере, известные сегодня) можно промоделировать на однородных структурах, сложность элементов которых никак не зависит от числа голосующих. Однородные структуры используются сейчас в самых разнообразных областях, хотя их применение и тормозится тем, что очень привычные вещи реализуются с их помощью весьма непривычным для человека образом. Возьмем, к примеру, операцию умножения. С детства мы привыкли умножать в столбик и верим, что этот способ самый простой и быстрый. На самом деле это совсем не так. Развитие вычислительной техники заставило нас перейти от десятичной системы к двоичной. В двоичной системе умножение оказалось куда более простым по своей структуре. Сдвиг на один разряд и сложение в определенной последовательности дают тот же эффект умножения в столбик без необходимости помнить таблицу умножения. Вот как выглядит умножение 12 на 14 в двоичной системе: Здесь мы умножали, начиная со старшего разряда множителя, и производили сдвиги вправо. Конечно, можно было бы умножать, начиная с младшего разряда множителя, и делать сдвиги влево. Результат 168 был бы одинаков. Как и при десятичном умножении, он равен 168. На рис. 5.6 показана однородная матрица, состоящая из трех столбцов, каждая клетка которых представляет собой однотипный автомат, имеющий три состояния D0 , D1 , D. Состояния D0 и D1 называются рабочими. Если автомат находится в них, то это означает, что он хранит в данной клетке значение двоичной цифры 0 и 1 соответственно. Состояние D является безразличным (нерабочим). Каждый
автомат имеет связи со всеми своими соседями. Эти входы и выходы мы будем обозначать буквами н, в, л, п (низ, верх, левый, правый). По ним могут передаваться сигналы пяти типов: безразличный (пустой) и B0, B1, Co, C1. Безразличный сигнал мы специально обозначать никак не будем. Сигналы Во и B1 несут информацию о значении цифр в соответствующем разряде множителя. Сигналы Со и С1, выдаваемые автоматами, соответствуют передаче соседу сигналов 0 и 1. Число строк в матрице зависит от разрядности перемножаемых чисел. При n разрядах число строк в первом столбце равно 2n + 1, во втором и третьем столбцах —2n. Матрица, показанная на нашем рисунке, предназначена для перемножения четырехразрядных двоичных чисел. Все автоматы, образующие матрицу, функционируют одинаково. Этот принцип проистекает из одно- 169
родности среды. Работа автоматов иллюстрируется табл. 5.2. Здесь индексы k, p, i могут принимать значения О или 1. В этой таблице заполнены только те места, которые соответствуют комбинациям сигналов и состояний, встречающихся в процессе умножения. Звездочка означает, что этого сигнала может и не быть. Как же происходит умножение? На рис. 5.6, а показано начальное заполнение матрицы. Множитель Таблица 5.2
записан в левом столбце так, что внизу находится младший разряд. Множимое написано в соседнем столбце. Правый столбец будет использоваться для получения произведения. Идея проста: если очередная цифра множителя есть 0, то множимое надо сдвинуть на один разряд вверх. Если же очередная цифра множителя есть 1, то до сдвига множителя его надо прибавить к той сумме, которая в этот момент будет накоплена в правом столбце матрицы. Процесс начинается с подачи сигнала Во справа на младший разряд множителя. Этот сигнал как бы 170 считывает значение разряда. Появление после этого состояния D означает, что разряд считан (рис. 5.6, б). Далее сигнал Во распространяется вверх по левой колонке и на каждом уровне порождает сигнал Во направо. Эти сигналы сдвигают множимое без прибавления в накопленную сумму правой колонки матрицы. В нашем примере это происходит потому, что на начальном цикле разряд множителя был равен 0. На рис. 5.6, в, г показаны еще два такта работы однородной среды. Появление на рис. 5.6 г сигнала Во, приходящего в левую колонку, соответствует началу работы с очередным разрядом множителя. Таким образом, на четвертом такте завершается микроцикл умножения. Общая картина распространения сигналов по однородной матрице при умножении двоичных чисел в столбик показана на рис. 5.7. На нем двойная стрелка изображает сигналы Bk, обычная стрелка — сигналы Ck. Светлый кружок означает переход автомата в данном такте в состояние D и выдачу вверх значения, соответствующего его состоянию, темный кружок — переход автомата в состояние Dp, соответствующего значению сигнала, поступившего на данный автомат снизу. Перечеркнутая стрелка означает, что передается либо сигнал Во, либо Со. За 18 тактов, как следует из рис. 5.7, цикл умножения двух четырехразрядных двоичных чисел завершается. Состояния автоматов правой колонки хранят результат умножения. Сигналы, которые на рис. 5.7 как бы выходят за пределы матрицы, пропадают и не оказывают влияния на дальнейшее функционирование матрицы. Читатель, пользуясь табл. 5.2 и рис. 5.7, может самостоятельно завершить умножение 12 на 14 с помощью однородной матрицы. Общее число тактов, которое нужно затратить на умножение двух n-разрядных двоичных чисел по предложенному методу, равно 8п+2. Если же отказаться от привычной нам логики умножения и перейти на более «изысканные» методы умножения, то однородная матрица позволяет найти произведение всего за 4n—1 такт работы. При этом сложность автоматов, образующих матрицу, даже меньше, чем при умножении в столбик. Правда, при умножении двух n-разрядных чисел потребуется в этом случае 171
n2 + 1 автомат, а для рассмотренного нами случая — 6n + 1 автомат. Кроме умножения, с помощью однородных матриц можно производить и деление. Один из способов деления на однородной матрице с двумя столбцами требует автоматов той же сложности, что и для умножения в столбик. Число необходимых автоматов равно 2п+3. Однородные среды открывают большие возможности в самых различных областях применения. Например, они оказываются незаменимыми при обработке зрительной информации, отображаемой на 172 устройствах типа фотоматриц. Однородные автоматные структуры позволяют в этом случае выделять контуры отображаемых рисунков, находить вершины углов и точки пересечения, определять расстояние между изображениями на матрице и т. п. Развитие робототехники в последние годы стимулировало это направление исследований. Для нас важно, что однородные структуры и однородные коллективы, состоящие из простых устройств, способны решать многие задачи, для которых мы привыкли использовать традиционные последовательные (централизованные) способы решений. А трудность перехода к параллельным (децентрализованным) методам решения кроется, в частности, в нестандартности методов и алгоритмов, реализуемых в однородных структурах. Наш гимн однородности не противоречит тому, что говорилось ранее о пользе неоднородности. В гл. 3 мы демонстрировали те новые качества, которые неоднородность вносит в поведение коллектива автоматов, решающих общую задачу. Ибо никто еще не доказал, что однородные коллективы и структуры могут эффективно решать все задачи, возникающие перед техническими системами. Но никто не доказал и противоположного! |
Последнее изменение этой страницы: 2019-05-06; Просмотров: 176; Нарушение авторского права страницы