Параллельное программирование: Учебное пособие, страница 12

3)  .  В этом случае

.                                                   (1.4)

Если предположить, что в параллельном алгоритме половина вычислительного времени процессов расходуется на вычисления со степенью параллелизма, равной единице, то есть , а остальное выполняется со степенью параллелизма , то

На рисунке 1.4 для  приведен график изменения ускорения по формуле (1.4), на котором доля времени вычислений со степенью 1 представлена в диапазоне значений .

Рисунок 1.4.

4)  . Используя (1.1) и (1.2), можно показать, что для этого случая выражение в скобках в формуле ускорения (1.3) не превышает единицы и оценивается  в общем случае так:

.

.

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

Из рассмотренных случаев можно сделать следующие выводы. Самым серьёзным замедлителем вычислений в параллельном алгоритме можно считать четвертый случай. Здесь необходимо принимать во внимание в первую очередь скорость передачи подготовленного количества данных по физической линии, соединяющей вычислительные машины. В линиях, со скоростью 10⁸ бит/сек, передача кода одного данного длиной 32 бита длится около 0.3 мксек. Служебные кодовые посылки, предваряющие последовательности самих данных, и возможные встречные протокольные пересылки, в среднем могут только увеличить время передачи.

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

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

Из литературных источников известно наиболее разумное среднее время подготовки и пересылки данных, которого рекомендуют добиваться при построении параллельных алгоритмов: – это 10-15% от времени вычисления алгоритма.

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

Из высказанного в данной главе следует, что программист, взявшийся за написание параллельной программы, кроме своих профессиональных навыков в кодировании алгоритмов на языке программирования, должен хорошо быть подготовлен и в таких областях знаний, как вычислительная математика и численные методы, алгоритмизация параллельных работ и построение алгоритмов, архитектура многомашинных вычислительных систем и схемотехнические решения коммуникационных систем и их интерфейсов. Естественно, программист должен понимать физику предметной области, для которой построена математическая модель. Это важно для правильной интерпретации результатов работы параллельного алгоритма и контроля адекватности математической, вычислительной и физической моделей объекта исследования.