Параллельные вычисления. Баканов В.М. - 13 стр.

                                                                   - 13 -



     1.2 Параллельная обработка данных

     1.2.1 Принципиальная возможность параллельной обработки

 Практически все разработанные к настоящему времени алгоритмы явля-
ются последовательными. Например, при вычислении выражения

       a + b×c ,

   сначала необходимо выполнить умножение и только потом выполнить
сложение. Если в ЭВМ присутствуют узлы сложения и умножения, которые
могут работать одновременно, то в данном случае узел сложения будет про-
стаивать в ожидании завершения работы узла умножения. Можно доказать
утверждение, состоящее в том, что возможно построить машину (разумеется,
гипотетическую), которая заданный алгоритм будет обрабатывать парал-
лельно (*).
  В самом деле, формула a + b × c фактически задает преобразование чи-
сел a,b,c в некоторое другое число r = a + b + c (причем без конкретизации
действий этого преобразования!). Без ограничений общности считаем, что
числа a,b,c заданы в двоичной формуле; тогда речь идет о преобразовании
некоторого набора нулей и единиц (битов), представляющих собой после-
довательность чисел a,b,c в некоторый другой набор битов последовательно-
сти r (результат вычисления). Возможно построить такое логическое уст-
ройство, на вход которого поступает любая допустимая комбинация a,b,c, а
на выходе сразу должна появиться комбинация, соответствующая результа-
ту r. Согласно алгебре логики для любой функции можно построить дизъ-
юнктивную нормальную формулу, тогда i-й двоичный разряд (i=1...n) резуль-
тата r будет рассматриваться как логическая функция

     r i = r i (a1, a 2 ... a n , b1, b 2 ...b n , c1, c 2 ... c n) ,

  где a j , b j , c j являются двоичными разрядами, представляющими воз-
можные значения a,b,c. Учитывая, что любая функция r i (любой i-тый
разряд двоичного r, i=1...m, где m - число разрядов результата) может
быть представлена дизъюнктивной нормальной формулой с участием логи-
ческих операций ‘И’, ‘ИЛИ’, ‘НЕ’, можно построить m процессоров (m ло-
гических схем, по одной для каждого бита числа r), которые при одновре-

*
    Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. –M.: Наука,
     1978, -352 c.