uzluga.ru
добавить свой файл
  1 2 3 ... 13 14



Стоимость (cost) вычислений

  • Стоимость (cost) вычислений

  • Стоимостно-оптимальный (cost-optimal) параллельный алгоритм - метод, стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.



Оценка качества параллельных вычислений предполагает знание наилучших (максимально достижимых) значений показателей ускорения и эффективности

  • Оценка качества параллельных вычислений предполагает знание наилучших (максимально достижимых) значений показателей ускорения и эффективности

  • Получение идеальных величин Sp=p для ускорения и Ep=1 для эффективности может быть обеспечено не для всех вычислительно трудоемких задач



Закон Амдаля (Amdahl)

  • Закон Амдаля (Amdahl)



Модель в виде графа "операции-операнды" используется для описания существующих информационных зависимостей в выбираемых алгоритмах

  • Модель в виде графа "операции-операнды" используется для описания существующих информационных зависимостей в выбираемых алгоритмах

  • В наиболее простом виде модель основывается на предположениях:

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






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

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

  • Схемы вычислений обладают различными возможностями для распараллеливания, при построении модели вычислений может быть поставлена задача выбора наиболее подходящей для параллельного исполнения вычислительной схемы алгоритма



Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание):

  • Пусть p есть количество процессоров, используемых для выполнения алгоритма. Тогда для параллельного выполнения вычислений необходимо задать множество (расписание):

  • Должны выполняться условия:

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


Модель параллельного алгоритма:

  • Модель параллельного алгоритма:

  • Время выполнения параллельного алгоритма с заданным расписанием:

  • Время выполнения параллельного алгоритма с оптимальным расписанием:



Минимально возможное время решения задачи при заданном количестве процессоров (определение наилучшей вычислительной схемы):

  • Минимально возможное время решения задачи при заданном количестве процессоров (определение наилучшей вычислительной схемы):



<< предыдущая страница   следующая страница >>