Методы параллельной обработки данных

Конвейерная обработка
Обеспечивает увеличение тактовой частоты обработки данных за счёт разделения задачи на фрагменты и временного совмещения выполнения различных фрагментов, относящихся к различным смежным наборам входных данных задачи. Одновременно с этим возрастает время решения задачи для каждого конкретного набора входных данных.
Метод заключается в использовании освободившихся в процессе сложения микроопераций, из последовательности которых состоит операция. Это микрооперации сравнение порядков, выравнивание порядков, сложение мантисс, нормализация. Использование освободившихся микроопераций становится возможным так как порядок их выполнения при обработке входных данных всегда один и тот же. Поэтому освободившаяся операция может быть использована для обработки следующей пары чисел на входе устройства. Устройство, использующее подобный механизм, размещает каждую микрооперацию в отдельной части и после окончания работы микрооперации передает обработанные данные следующей части. В то время как освободившаяся микрооперация может начать обрабатывать следующую порцию данных. Когда будет исчерпан входной набор данных, устройство выдает результат своей работы. Подобное устройство называется конвейером. Каждая часть устройства называется ступенью конвейера, а общее число ступеней - длиной конвейера. Время выполнения контейнером одной операции равно суммарному времени работы каждой ступени. При реализации суммирования векторов на конвейере на выполнение операции потребуется 104 такта (рис. 2). Таким образом, при наличии m ступеней в конвейере время обработки n операций, которые не зависят друг от друга - (m + n -1) единиц (время работы одной ступени - 1 единица). По сравнению с последовательным устройством при больших значениях n время обработки уменьшится приблизительно в m раз.





Рис. 2. Суммирование векторов C = A + B с помощью конвейерного устройства. Каждая из пяти ступеней конвейера срабатывает за один такт.





Рис. 3. Кривая зависимости производительности конвейерного устройства от длины входных данных

При возрастании числа входных данных реальная производительность E конвейерного устройства приближается к пиковой (рис.3). г - время такта работы компьютера.

Рассмотрим оптимизацию распределения данных. Одним из способов такой оптимизации является иерархическая организация памяти. Часто используемые данные оптимально хранить на регистрах. Скорость работы процессора всегда согласуется со временем выполнения операций на регистрах. Но в случае увеличения объемов данных привлекается уровень кэш-памяти. Далее, в случае повторения ситуации, привлекаются следующие уровни памяти (разные уровни кэш-памяти, оперативная, дисковая и т. д.). В связи с высокой стоимостью, объем высших уровней иерархии ограничен.
Выполнение стандартных вычислений зависит от времени обращения к запоминающему устройству. Использование сверхбыстродействующей дополнительной памяти небольшой емкости позволяет уменьшить это время. Например, цикл с телом из одного оператора и большим числом итераций является фрагментом программы с высокой локальностью вычислений. В этой связи тело цикла помещается в более быструю память. Такой шаг становится возможным, так как каждая итерация выполняет одни и те же команды.
Помимо цикла существуют следующие причины снижения степени локальности (данных и вычислений) в программах:

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

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

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