Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 17 стр.

  4) Агломерация производит задачи с одинаковыми затратами вычислений и коммуни-
   каций? Если получается одна задача на процессор, то их размерности должны быть
   примерно одинаковы.

  5) Масштабируется ли число задач, получаемых при агломерации, с ростом входной
   размерности обрабатываемых данных. Если нет, то трудно использовать такой алго-
   ритм с ростом размерности и числа процессоров.

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

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

                       2.6 Распределение задач по процессорам
     На заключительной стадии проектирования параллельного алгоритма нужно опре-
делить какая задача на каком процессоре будет выполняться . В целом задача распределе-
ния остается трудной задачей, которая должна быть точно разрешена при проектировании
параллельного алгоритма. Цель распределения состоит в том чтобы минимизировать вре-
мя выполнения алгоритма (сумма времен вычисления, простоя и коммуникаций ) и затра-
ты памяти.
  Используются две стратегии для достижения этой цели:
  - размещение задач, которые могут выполняться параллельно на разных процессорах;
  - размещение задач, которые часто взаимодействуют, на одном и том же процессоре
       чтобы увеличить коммуникационную локальность.

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




                                         17