Динамо-машины  Обратные коды 

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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

что при сложении 40-разрядных двоичных чисел максимальная длина цепочки разрядов, в которой перенос из данного разряда определяется наличием или отсутствием переноса в него из предыдущего разряда, в среднем равна 5,6 разряда. Вероятность появления таких цепочек длиной более 12 разрядов ничтожно мала.

От npedtidi/щего разряда

\или\

U1 Т

или\

\или

переноса

К следующему разряду

Рис. 2-28. Возможное построение участка преноса для схемы двоичного сумматора, учитывающей статистическую структуру переносов.

Таким образом, выполнение переносов при сложении 40-разрядных двоичных чисел занимает в среднем примерно в 7 раз меньше времени, чем максимально возможное время выполнения этой операции. В схеме рис. 2-28 появление сигнала на выходе Е или на выходе Е некоторого разряда свидетельствует о том, что формирование сигнала переноса в данном разряде закончено; если сигналы окончания переносов от всех га разрядов ввести в общий элемент laquo;и raquo; (имеющий га входов), то его выходной сигнал будет являться сигналом окончания переносов по всему сумматору. Таким образом, на выполнение переносов можно

будет отводить ровно столько времени, сколько требуетсй Б каждом конкретном случае, а не каждый раз максимальное время, как делается обычно.

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

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

Идея сверхпараллельного сумматора состоит в том, чтобы выполнить максимальное количество подготовительных операций в старших разрядах сумматора до получения сигналов переноса из младших разрядов. Имея в старших разрядах заранее сформированные laquo;подготовительные функции raquo; (зависящие только от цифр слагаемых, но не от цифр переноса в данные разряды), можно затем ускорить прохождение через эти разряды сигналов переноса.-

Эта идея частично уже знакома нам по схеме цепи переносов, приведенной на рис. 2-25.

В схеме рис. 2-25 в каждом разряде формируются подготовительные функции D vi R, зависящие только от цифр слагаемых данного разряда. Функция D равна единице в том случае, когда перенос из данного разряда есть единица независимо от того, имеется ли перенос в данный разряд; если функция R равна единице, то это означает, что перенос из данного разряда в следующий должен получиться при условии, что будет перенос в данный разряд из предыдущего. Наличие заготовленных заранее функций D и R позЕслило нам сформировать сигнал переноса Е из данного разряда Б следующий всего в две ступени по уравнению

Е = D + Re,

рде g сигнал переноса в данный разряд. Функции D и R мы будем называть подготовительными функциями нулевого порядка.

Развивая эту идею дальше, поступим следуюш,им образом*). Подготовительные функции нулевого порядка D и R формируются по всем разрядам одновременно - вслед за приемом слагаемых в регистры. В младших разрядах они сразу же используются для образования сигналов переноса. Но пока сигнал переноса пройдет через несколько младших разрядов, в следующих разрядах из функций D и R можно сформировать подготовительные функции первого порядка.

С этой целью все разряды, старше некоторого s-ro разряда, разбиваются на группы по р разрядов (о выборе величин S и р мы скажем несколько позже). Пусть имеем группу из р последовательных разрядов - от номера ft + 1 (младший разряд этой группы) до номера ft + р. Перенос из (ft + р)-го разряда в следующий можно записать в виде

Екл-р = Dk+p + Rk+p вк+р,

где Dfe+p, i?ft+p - подготовительные функции нулевого порядка, сформированные в данном разряде, е+р - перенос Б данный разряд. Но входным сигналом переноса для данного разряда является выходной сигнал переноса предыдущего разряда,- поэтому

gft+p = fft+p-i = Dk-rp-г + Rk+p-iSk+p-i-

Подставляя это выражение е+р в уравнение для Ek+p, найдем

fe+p = {Dk+p + Rk+pDk+p-i) + {Rk+pRk+p-i) вк+р-1-Действуя таким же образом дальше, найдем

Ek+p = {Dk+p + Rk+pDk+p-i + Rk+pRk+p-xDk+p + . .. + + Rk+pRk+p-г Rk+iPk+i) + (Rk+pRk+p-iRk+p-2 - Rki) ek+i-

) Cm. a High-Speed Parallel Adder for Electronic Digital Computers. Techn. News Bull. NBS, 1956, 40, 6, a также Weinberger A.. S m i t h I. L., A One-microsecond Adder Using One-megacicle Circuitry, IRE Trans. Electronic Conip., 1956.