Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 58

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

Шаг 5. Помещение результата c в регистр па­мяти, в котором он должен храниться.

Шаг 6. , = , + 1. Если ,>n, завершение вычисле­ния; иначе переход к Шагу 2.

Согласно ЛП схеме, для нахождения покомпо­нентной суммы необходимо выполнить следую­щий набор операций:

Шаг 1. Конкатенация:

А:{а1, а2, а3,..., а,-,..., а«}

а# =1 е а2 е а3 © ... © аі © ... © а«); (4)

B:{b1, b2, b3,_, b,,..., bn}

b# = (b1 © b2 © b3 © ... © bt© ... © bn).

Шаг 2. Извлечение значения операнда (конка-тенанда) а# из регистра памяти, в котором он хра­нится.

Шаг 3. Извлечение значения операнда (конка-тенанда) b# из регистра памяти, в котором он хра­нится.

Шаг 4. Суммирование конкатенандов: c# = а# + b#.

Шаг 5. Помещение результата c# в регистр па­мяти, в котором он должен храниться. Шаг 6. Деконкатенация:

c# = (c1 © c2 © c3 © ... © c, © ... © c«)

C:{cl, c2, c3,...,1 cг,..., cn}. (5)

Операции конкатенации и деконкатенации требуют дополнительного пояснения. Обычно эти термины применяются при описании обработки

БенаддияАбдельлатиф, О.Ф. Михаль

символьных последовательностей. В рассматрива­емом случае конкатенируются целые положитель­ные числа в двоичном представении.

Числа (исходные данные, промежуточные зна­чения, результаты) при их обработке располага­ются в центральном процессоре в отдельных реги­страх линейках бинарных ячеек памяти. Отсюда применяемый далее термин регистровое пред­ставление (РгП). В ЛП представлении результат конкатенации есть некоторое целое положитель­ное число, помещаемое в едином регистре, РгП, которое интерпретируется как состоящее из сег­ментов согласно длине конкатенантов. При декон-катенации сегменты извлекаются из РгП. Таким образом, конкатенация есть операция уплотнения представления компонентов векторов (1) в виде сегментов в РгП а# и b# вида (4). Содержимые РгП а# и b# обрабатываются целиком, как числа. Де-конкатенация — обратная операция — раскрытие РгП. Содержимое ,-го сегмента ci извлекается и помещается в индивидуальный регистр. В резуль­тате, согласно ЛП схеме, операция (в рассматри­ваемом случае суммирование соответствующих компонентов векторов) производится над РгП, а результат C:{c1, c2, c3,..., c,,..., cn} вьіглядит так, как если бы операции производились над парами опе­рандов раздельно.

Сравним представленные выше пошаговые по­следовательности операций. Вычислительные бло­ки операций Шаги 2 — 5 в последовательной и ЛП схемах совпадают. Различие состоит в том, что в по­следовательной схеме блок выполняется n-кратно, в ЛП схеме однократно. Этим обеспечивается выигрыш в производительности. Разумеется, про­цедуры конкатенация и деконкатенация (Шаги 1 и 6 ЛП схемы) являются протяженными во време­ни, т.е. связаны с дополнительным расходованием ресурсов ВС. Однако, если в системе реализуются сложные вычисления, например с последователь­ным применением нескольких ЛП алгоритмов, РгП составляются из исходных данных только в самом начале вычислительного блока, а результа­ты извлекаются из РгП только в самом конце. За­траты ресурсов на конкатенацию-деконкатенацию при этом могут быть пренебрежимо малы по срав­нению с общими затратами ресурсов ВС. При этом выигрыш в производительности приближается к n-кратному.

Очевидно, что ЛП схема тем более эффективна, чем больше число конкатенированных сегментов n. Приближенно (при больших объёмах вычисли­тельных ЛП блоков), выигрыш в производитель­ности пропорционален длине регистра вычисли­тельного устройства и обратно пропорционален длине сегмента [2, 3].

Для единства структуры данных, разрядности сегментов, задействованных под операнды а# и b# и результат c#, должны совпадать. При выполне­нии операции соседствующие сегменты не должны взаимодействовать, поэтому должны быть приня­ты меры по согласованию разрядностей. Форматы представления ЛП данных в системе должны быть организованы так, чтобы в сегментах c# было изна­чально зарезервировано достаточно места для раз­мещения результата операции над а# и b#.

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

Для операций должны быть разработаны соот­ветствующие алгоритмы, подобные ЛП алгорит­мам операций нечёткой логики, рассмотренным в [2, 3]. Имеются ограничения, определяемые дли­ной сегментов. В частности, рассмотренная ЛП операция суммирования реализуема только для положительных операндов ограниченного разме­ра. Этому условию удовлетворяют, в частности, значения ФП, применяемые в нечетком теоретико-множественном описании. Применительно к ЛП представлению они масштабированы в соответ­ствии с размерами сегментов и конкатенированы в РгП [2, 3]. Для ячеек КА так же имеется фиксиро­ванное число неотрицательных состояний. Следо­вательно, ЛП представление информации потен­циально применимо и к КА.

3. Локально-параллельное представление КА

Упрощённо процессор ВУ Фон-Неймановского типа имеет два 32-разрядных регистра для хране­ния операндов и один 32-разрядн^ій регистр для помещения результата. Процессор реализует стан­дартный набор арифметических и логических опе­раций, включая поразрядную (побитовую) логику и регистровые сдвиги.

Как отмечалось (п. 2), при ЛП обработке пред­полагается хранение нескольких элементов ин­формации в виде раздельных непересекающихся сегментов РгП. В случае ЛП представления КА логично разместить в отдельных сегментах РгП от­дельные клетки КА. При этом формат размещения информации в РгП должен быть удобным для реа­лизации ЛП алгоритмов обработки.

В обычной записи для хранения решётки ячеек (матрицы) КА требуется двумерный массив. Приразмере поля M строк на N столбцов требуется MN индивидуально адресуемых элементов хранения информации. В случае 32-разрядного ВУ Фон-Неймановского типа это составляет 32-M-N6hl\ В ЛП представлении ячейки КА хранятся в сегмен­тах РгП. То есть индивидуально адресуемыми эле­ментами хранения становятся РгП, а не отдельные ячейка КА. В случае БКА в РгП может быть до 32 однобитовых сегментов. Строка поля БКА может быть помещена в / 32] + 1 РгП (квадратные скобки обозначают взятие целой части от деления). В результате для представления всего БКА необ­ходим массив из ([М/ 32] + 1)N« MN/ 32 РгП (индивидуально адресуемых элементов хранения информации). Соответственно, если ячейка КА имеет n состояний, для её представления требует­ся к бит с соблюдением соотношения > n, то есть к > log2 n, то есть к = [log2 n]+1 бит. Таким образом, в 32-разрядном ВУ для представления строки эле­ментов КА требуется [Мк / 32] + 1, а для представ­ления всего массива M-N / 32 индивидуально адресуемых элементов хранения информации.

Для БКА наиболее плотным (компактным, эко­номным, с минимальным расходованием ресурсов ВУ) является однобитовое сегментное представле­ние. Например, поле БКА размером 30 х 30 элемен­тов может быть размещено в одномерном массиве А из 30 штук 32-разрядных чисел в формате integer: (а1, а2,..., ау-,..., а29, а30). Сложность проявляется при реализации работы БКА. Как отмечалось, ал­горитм функционирования КА предполагает рас­смотрение окружения каждой клетки и принятие в зависимости от этого решения, будет ли клетка «живой» (значение «1») или «мёртвой» (значение «0») в следующем цикле жизни КА. В частности, для БКА с 8-ю соседями (рис. 1 а), согласно прави­лам (рис. 2), при ЛП вычислениях для j строки (j-го РгП а) должны суммироваться 8 штук РгП:

0-1)«р) + (/-1)) + и-1)»р) + Ц«р) +

+ Ц»р) + (,+1)«р) + (/+1)) + (аи+Х)»р). (6)

В (6) «<<р» и «>>р» означают процедуры реги­стрового сдвига на р бит (длину сегмента) в сторо­ну старших или младших разрядов соответственно. В рассматриваемом случае БКА р = 1, а для пред­ставления результата по каждому сегменту требу­ется 4 бита, поскольку имеется 9 градаций возмож­ных значений сегментной суммы: (0, 1, 2,..., 7, 8). Как отмечалось, соседние сегменты не должны взаимодействовать. Для этого ЛП система должна быть организована так, чтобы в сегментах было из­начально зарезервировано достаточно места для размещения результата. Типовым подходом при реализации подобных ЛП вычислений является прореживание РгП А [2, 3] с использованием бито­вых масок.

E1 = (000100010001...0001)2 ; E2 = (001000100010...0010)2 ; E3 = (010001000100...0100)2 ; E4 = (100010001000...1000)2 . (7)

При этом массив РгП А преобразуется в 4 мас­сива А,,: (а,1, а,2,..., ау,..., ат, а,30); ац = л E; , є (1, 2, 3, 4); где «л» побитовое логическое И. В полученных 4 массивах все сегменты содержатся в точности по одному разу. При этом они не вза­имодействуют при проведении операции. После прореживания процедура выполняется последо­вательно для каждого из А,, с последующим све-дениием результатов в единый РгП — сложением либо теоретико-множественным объединением. Эффективность ЛП алгоритма при этом снижается четырёхкратно.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа