Лекции по дисциплине «Теория вычислительных процессов» (стр. 6 )

В1=(1,0 ... 0)

В2=(0,1 ... 0)

Вn=(0,0 ... 1)

В этом случае говорят, что величины Вi обладают свойствами ортогональности.

Тогда в случае ортогональных базисов получаем, что Мi=ai.

При этом базисы должны определяться по формуле Вi=Чpi P/pi, где
Чpi - целое положительное число, называемое весом базиса.

Обычно Чpi P/piº1 (modpi) (1)

Отсюда Чpi P/pi=lipi+1, где li - целое положительное число.

Найдем Чpi. Для этого обозначим P/pi=Pi. Пусть величина Pi вычислена. Так как Pi составлена из множителей взаимно постоянных с рi, то в результате деления Pi на pi получится остаток di. Тогда значение Чpi можно определить из формулы Чpidi-1=KPi

Чpidiº1 (mod pi)

Пример: Определить базисы для системы оснований pi=2, p2=7, р3=11, р4=19, р5=23.

Решение: Диапазон представления чисел является величиной Р=Пpi=67298.

В1=Чpi P/p1=Чpi 7 11 19 23

d1=P1/p1=(7 11 19 23)/2º1 (mod2)

Чpid1º1 (mod2)ÞЧpi=1; B1=1 7 11 19 23=33649

B2=Чр2Р2; d2=(2 11 19 23)/7º3 (mod 7)

Чр2 3-1=л 7 Чр2=(7к+1)/3

Методом подбора: Чр2=5(к=2)

В2=5 2 11 19 23=48070

Аналогично: Чр3=6 В3=36708

Чр4=12 В4=42504

Чр5-14 В5=40964

Переведем число А-234=(0, 3, 3, 6, 4) в позиционную десятичную систему:

А=0 33649+3 48070+3 3708+6 42504+4 40964=673214.

Полученный результат превышает диапазон представления числа во много раз. Чтобы перейти к истинному значению числа, необходимо вычесть из этого результата целое число раз величину Р:

А=673214-10 67298=234.

В приведенном выше примере для вычисления величины числа А было использовано число 10, показывающее, во сколько раз превышен диапазон представления чисел, и называемое рангом числа (ra).

Отсюда: А=a1b1+a2b2+ ... anbn-raP или Аºa1b1+ a2b2+ ... anbn (modP).

Формы представления чисел в СОК

Одним из ограничений для СОК является то, что в этих системах можно представлять только целые положительные числа. Для целых положительных чисел диапазон представления V=р1...рn. В случаях, когда необходимо представлять не только положительные, но и отрицательные целые числа, целесообразно сделать так, чтобы положительные числа располагались в диапазоне от Р/2 до Р, а отрицательные - в диапазоне от 0 до Р/2. Это означает условное перенесение начала отсчета числовой оси в точку с координатой Р/2. Так как в качестве оснований, как правило, выбирают нечетные простые числа, то в этом случае получают неравнозначные пространства для изображения положительных и отрицательных чисел. Чтобы уравнять их, обычно начало отсчета переносят в точку с координатой (р-1)/2. Тогда говорят об искусственной форме представления чисел А, определяемой следующим образом:

если А>0, то А=(р-1)/2+|A|

если А<0, то А=(р-1)/2-|A|.

Как было установлено ранее, для чисел, представленных в СОК, справедливо соотношение: А=a1b1+a2b2+ ... +anbn-rаР.

Разделим обе части на Р

А=a1Чр1+a2Чр2+anЧрn-ra=а

Р Р1 Р2 Рn

Ранг числа ra должен выбираться так, чтобы число входило в диапазон представления. В работах А. Свободы доказано, что каждому числу А в искусственной форме соответствует изображение А*, определяемое соотношением:

А*ºФА (modР) где Ф=(Чpi, ... Чpn) преобразующая функции

Аi*ºЧpiºa(mod pi)

Это соотношение позволяет представить правильные дроби в СОК:

А*=а*=a1*+a2*+ ... + an*-ra

P p1 p2 pn

где 0£а*<1, или для положительных и отрицательных дробей -0 5£а*<0 5.

Таким образом, можно говорить о представлении правильных дробей в форме с фиксированной запятой.

Пример: р1=2; р2=7; р3=11; р4=19; р5=23.

А=-234=-(0, 3, 3, 6, 4) в ФФЗ.

Решение:

А*=ФА (modР)

А=Р-А=(0, 4, 8, 13, 19)

A=(1, 5, 6, 12, 14)

А*=(1, 5, 6, 12, 14) (0, 4, 8, 13, 19)=(0, 6, 4, 4, 13).

а*=0+6+4+4+13-ra

2 7 11 19 23

ra=2 a*=-0 00348

F=p a&=67298(-0 00348)=-234

F=(0, 6, 4, 4, 13)

Правила выполнения АО

Пусть для заданного набора оснований р1, р2... рк числа А и В представлены в виде остатков:

А=(a1 ... ak) b=(b1...bk).

0£ai£pi-1; 0£bi£hi-1 A<P; B<P.

Тогда на основании свойств сравнений можно записать:

А+В=(a1+b1)a2+р2, ... ak+bk)

A-B=(a1-b1, a2-b2, ... ak-bk)

AB=(a1b1, a2b2 ... akbk).

При этом надо иметь в виду, что если a1+b1³Рi, то в качестве цифры i-го разряда берутся величины из условия: (a1+b1) - Sipi³0; (aibi)-mipi³0, где Si, mi - целые положительные числа. Если bi>ai, то вычитание остатков выполняется таким образом, что pi+aibi³0. Операция деления СОК может быть выполнена только в случае деления без остатка.

Пусть С=А/В=(gi...gk), где gi=[ai/bi]= ai[1/bi]pi.

Таким образом, деление остатка двух чисел может осуществляться умножением остатков делимого на обратную величину остатков делителя.

Величина х=[1/bi]pi есть решение сравнения хbiº1 (mod pi), которое однозначно определено, если bi и pi - взаимно простые числа.

Предположим, что bi =0. Это означает, что модуль pi является делителем числа В. Но так как, по условию, число А делится на число В без остатка, то модуль pi должен быть делителем и числа А, т. е. ai=0 и соответствующая цифра частного становится неопределенной. Тогда можно сократить это основание pi и вычислить цифры частного по значениями других остатков или путем расширение набора оснований.

Над числами, представленными в искусственной форме, АО выполняются по следующим правилам:

Сложение. Пусть A=А+Р; В=В+Р для Р=pi... pn. Необходимо получить:

(А+В)=Р+(А+В).

Если сложить два числа, представленных в искусственной форме, то А+В=А+В+2Р. Расширим систему оснований введением Ро=2. Вследствие того, что числа р1 ... рn - взаимно простые, величина Р изобразится в расширенной системе оснований:

р=(1, 0 ... 0)

Следовательно 2Р=(0 ... 0)

Отсюда: А+В=А+В

(А+В)=А+В+Р

Пример: А=234 В=-199

А=(0, 3, 3, 6, 4)

В=-(1, 3, 1, 9, 15)

Р= 7 11 19 12-33649.

А=(0, 3, 3, 6, 4)+(1, 0, 0, 0, 0)=(1, 3, 3, 6, 4)

В=(1, 0, 0, 0, 0)-(1, 3, 1, 9, 15)=(0, 4, 10, 10, 8)

C=А+В-Р=(1, 3, 3, 6, 4)+(0, 4, 10, 10, 8)+(1, 0, 0, 0, 0)=(0, 0, 2, 16, 12)=33649-35=33614.

Вычитание. Вместо операции вычитание будем выполнять сложение с числом с противоположным знаком.

С=А-В=А+В.

При переходе к искусственным формам необходимо учесть, что:

1) если величина В была отрицательной, то В=Р+В;

2) если величина В была положительной, то В=Р-В.

Для машинной реализации это проще всего осуществить по формуле (-В)=2Р-(В).

Пример: ро=2, р1=3, р3=7, р2=5

А=13В=8 р=3 5 7=105=(1, 0, 0, 0)

А=(0, 1, 3, 6) В=(1, 2, 3, 1)=(1, 1, 2, 6)

А+(-В)=(1, 2, 0, 5)

(А-В)=А+(-В)+Р=(0, 2, 0, 5)=105+5=110.

Умножение. Пусть для р1, р2 ...pn, где р1=2 и р=Пpi заданы А=Р+А и В=Р+В.

Тогда АВ=РР+РА+РВ+АВ=Р(Р+А+В)+АВ.

Результат должен быть равен

(АВ)=Р+АВ.

Тогда (АВ)=АВ+Р-Р(Р+А+В).

Так как величина Р нечетная, то значение последнего члена выражения зависит от четности А и В:

если А и В одинаковой четности, то остатки от модуля pi у них одинаковы и при их сложении всегда будем получать первый остаток для величины в скобках, равные единице. В противоположном случае остаток будет равен нулю. Отсюда следует, что при умножении двух чисел окончательный результат определяется так:

(АВ)={АВ+Р, если А и В разной четности;

АВ, если А и В одинаковой четности.

Положительное качество СОК:

1) сравнительная простота выполнения АО, которые часто реализуются табличным способом;

2) отсутствие связей между разрядами изображения числа;

3) высокая скорость выполнения АО.

Однако представление чисел в СОК исключает возможность их сравнения, что затрудняет выявление переполнения разрядной сетки. Кроме того затруднено выполнение операций, которые требуют округления результата.

СОК применяются в СВМ, для которых:

1) одним из основных требований является получение высокого быстродействия;

2) диапазон исходных чисел и промежуточных результатов строго фиксирован;

3) операция деления встречается крайне редко.

Параллельные процессы в ВС

Каждая ВС может обладать как собственной характеристикой лишь значением пиковой производительности - суммарным числом выполняемых в единицу времени операций при полной загрузке всех исполнительных устройств.

Для конкретных задач с учетом возможностей их распараллеливания, соотношения типов операций, режима вычисления на данной ВС и накладных расходов на организацию вычислительного процесса определяются значения реальной производительности.

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

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

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