Время - умножение
Cтраница 3
После восприятия числа с карты начинается процесс умножения. Во время умножения число из регистра множимого через устройство сдвига и преобразователь кода подается в сумматор, где и производится последовательное сложение. Одновременно устройство управления посылает в младший разряд множителя единицы. Как только произойдет переполнение разряда регистра множителя, посылка импульсов в сумматор прекращается и происходит переключение сдвига разрядов на следующий разряд. После этого вновь возобновляется передача числа в сумматор. [31]
Для сокращения времени умножения необходимо увеличивать оборудование или пропускать такты суммирования, когда очередная цифра множителя нуль. [32]
Чем выше производительность ЭВМ, тем большим становится и ущерб ич, наносимый каждым часом ее простоя. В лучших современных серийных ЭВМ время выполнения операции логического сравнения уже не превышает 150 нсек, время умножения - 1 мксек. Поиск слова в массиве из 250 тыс. слов занимает менее 100 нсек, а в массиве из 3 - 10е слов, что соответствует библиотеке из нескольких тысяч томов, поиск длится не более 0 5 сек. [33]
В этой главе мы покажем, что для некоторых операций над целыми числами и полиномами, таких, как деление и возведение в квадрат, требуется время того же порядка, что и для умножения. Время выполнения других операций, таких, как упомянутые выше операции с вычетами или вычисление наибольших общих делителей, может превосходить время умножения не более чем в log n раз, где п - длина двоичного представления целого числа или степень полинома. Наша стратегия будет состоять в том, чтобы чередовать результаты для целых чисел с соответствующими результатами для полиномов, причем обычно мы будем доказывать эти результаты только для чего-то одного, а доказательство для другого будем оставлять в качестве упражнения. Как и в остальных главах, основное внимание будет уделяться алгоритмам, асимптотически наиболее эффективным среди известных. [34]
Следует отметить, что при использовании некоторых аппаратных методов ускорения умножения сокращение количества суммирований может не привести к уменьшению времени умножения. Например, если в АЛУ реализован сумматор с запоминанием переносов и сложение в сумматоре совмещено по времени со сдвигом, то время умножения определяется числом сдвигов ( количеством разрядов множителя) и уменьшение суммирований не приводит к сокращению времени умножения. [35]
Следует отметить, что при использовании некоторых аппаратных методов ускорения умножения сокращение количества суммирований может не привести к уменьшению времени умножения. Например, если в АЛУ реализован сумматор с запоминанием переносов и сложение в сумматоре совмещено по времени со сдвигом, то время умножения определяется числом сдвигов ( количеством разрядов множителя) и уменьшение суммирований не приводит к сокращению времени умножения. [36]
 |
Дерево сумматоров операционного блока умножения матричного типа. [37] |
Для ускорения умножения в ЕС ЭВМ операционные блоки умножения содержат так называемое дерево ссумма-торов, позволяющее обрабатывать сразу все разряды множителя. В таких ОБУ умножение осуществляется по принципу одновременного образования всех частичных произведений и каскадно-параллельного их суммирования до получения полного произведения. Сокращение времени умножения производится за счет увеличения количества сумматоров. [38]
Ахга можно реализовать с той же скоростью, как одно произведение, то относительные скорости соперничающих методов могут сильно измениться, и наши привычные суждения будут нарушены. Относительно элементарных операций заметим, что затраты времени, требуемые для вызова, запоминания, сложения, умножения и деления становятся все ближе друг к другу, и эта тенденция приведет к тому, что многие обычные подсчеты числа операций будут только вводить в заблуждение. С другой стороны, важность отношения времени деления к времени умножения перевесится на более высокий уровень операций, а именно к проблеме отношения стоимости решения системы Ах Ь к стоимости формирования произведения АЬ. Здесь разреженность структуры и характеристики вычислительной системы решающим образом влияют на картину вычислительного процесса. [39]
Время умножения чисел с помощью одного 8-разрядного умножителя может быть слишком большим для некоторых динамических систем, работающих с большой пропускной способностью. Применяя мультиплексированный режим работы нескольких умножителей, можно существенно ускорить процесс умножения массивов чисел. Например, при использовании устройства по схеме на рис. 12.20 время умножения массивов чисел уменьшается в 2 раза по сравнению с устройством без мультиплексирования. [40]
Для ускорения операции сложения сумматор делится на группы, причем перенос в пределах разрядов группы образуется параллельно, а распространяется между группами последовательно; происходит частичное совмещение распространения переносов внутри различных групп. Для ускорения операций умножения и деления совмещаются элементарные операции сдвига и сложения ( вычитания); в сумматорах с запоминанием переносов используется форма незаверш. Часто умножение производится сразу на неск. В машине Стрсч имеет место одповрем. В результате время умножения ( 2 7 мксек) лишь в два раза превышает время сложения для операций с плавающей запятой. Подобным образом время операции деления может быть значительно сокращено за счет использования неск. Это позволяет за один цикл сложения ( вычитания) получать в среднем 3 5 цифры частного. В машине НОРК генератор произведений образует одновременно 9 кратных величин множимого и подает пх на вентили, управляемые определ. После соответствующего сдвига эти 9 частичных произведений суммируются на ряде суммирующих блоков. Здесь время умножения также лишь в 2 раза превышает время сложения. В УУ параллельно с др. операциями в оси. [41]
Для ускорения операции сложения сумматор делится на группы, причем перенос в пределах разрядов группы образуется параллельно, а распространяется между группами последовательно; происходит частичное совмещение распространения переносов внутри различных групп. Для ускорения операций умножения и деления совмещаются элементарные операции сдвига и сложения ( вычитания); в сумматорах с запоминанием переносов используется форма незаверш. Часто умножение производится сразу па неск. В машине Стреч имеет место одноврем. В результате время умножения ( 2 7 мксек) лишь в два раза превышает время сложения для операций с плавающей запятой. Подобным образом время операции деления может быть значительно сокращено за счет использования песк. Это позволяет за один цикл сложения ( вычитания) получать в среднем 3 5 цифры частного. В машине НОРК генератор произведений образует одновременно 9 кратных величин множимого и подает их на вентили, управляемые определ. После соответствующего сдвига эти 9 частичных произведений суммируются на ряде суммирующих блоков. Здесь время умножения также лишь в 2 раза превышает время сложения. В УУ параллельно с др. операциями в осн. [42]
Существуют различные методы сокращения времени выполнения умножения. Один из них состоит в том, что создаются комбинационные множительные устройства из логических быстродействующих элементов. Время выполнения операции умножения в таком устройстве определяется в основном переходными процессами в логических схемах. Количество оборудования в таком множительном устройстве резко растет с увеличением числа разрядов. Другим методом сокращения времени умножения явля - ется одновременное умножение на несколько разрядов множителя, что можно осуществить в множительных устройствах как с последовательным, так и с параллельным сумматором. [43]
Для ускорения операции сложения сумматор делится на группы, причем перенос в пределах разрядов группы образуется параллельно, а распространяется между группами последовательно; происходит частичное совмещение распространения переносов внутри различных групп. Для ускорения операций умножения и деления совмещаются элементарные операции сдвига и сложения ( вычитания); в сумматорах с запоминанием переносов используется форма незаверш. Часто умножение производится сразу на неск. В машине Стрсч имеет место одповрем. В результате время умножения ( 2 7 мксек) лишь в два раза превышает время сложения для операций с плавающей запятой. Подобным образом время операции деления может быть значительно сокращено за счет использования неск. Это позволяет за один цикл сложения ( вычитания) получать в среднем 3 5 цифры частного. В машине НОРК генератор произведений образует одновременно 9 кратных величин множимого и подает пх на вентили, управляемые определ. После соответствующего сдвига эти 9 частичных произведений суммируются на ряде суммирующих блоков. Здесь время умножения также лишь в 2 раза превышает время сложения. В УУ параллельно с др. операциями в оси. [44]
Для ускорения операции сложения сумматор делится на группы, причем перенос в пределах разрядов группы образуется параллельно, а распространяется между группами последовательно; происходит частичное совмещение распространения переносов внутри различных групп. Для ускорения операций умножения и деления совмещаются элементарные операции сдвига и сложения ( вычитания); в сумматорах с запоминанием переносов используется форма незаверш. Часто умножение производится сразу па неск. В машине Стреч имеет место одноврем. В результате время умножения ( 2 7 мксек) лишь в два раза превышает время сложения для операций с плавающей запятой. Подобным образом время операции деления может быть значительно сокращено за счет использования песк. Это позволяет за один цикл сложения ( вычитания) получать в среднем 3 5 цифры частного. В машине НОРК генератор произведений образует одновременно 9 кратных величин множимого и подает их на вентили, управляемые определ. После соответствующего сдвига эти 9 частичных произведений суммируются на ряде суммирующих блоков. Здесь время умножения также лишь в 2 раза превышает время сложения. В УУ параллельно с др. операциями в осн. [45]
Страницы: 1 2 3