Тема 2_2010 Сложные задачи их хараетристики пути эффективного решения (Лекции (ещё одни))

Тема. Сложные задачи, их характеристики и пути эффективногорешенияОсновные вопросы:1. Основные этапы решения сложной задачи на параллельных структурах2. Сложная задача. Характеристики сложности (размерность,трудоемкость, объем требуемой памяти и др.) Основные классысложных задач3. Характеристики параллельности (ускорение, эффективность, стоимостьи ценность параллельного решения)4. Закон Амдаля и его следствияОсновные этапы решения сложной задачи на параллельныхвычислительных системахВесь процесс решения некоторой задачи на параллельной ВС можноразбить на следующие этапы:• формулировка задачи;• составление модели исследуемого в задаче объекта;• определение метода решения задачи для получения необходимойрезультирующей информации на основании используемой модели;• разработка алгоритма решения задачи на основе используемого методаи модели исследуемого в задаче объекта;• выбор технологии программирования;• разработка программы для соответствующей параллельной ВС наоснове имеющегося алгоритма и получение результирующейинформации после выполнения программы.Данный процесс представлен на рис.1.

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

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

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

Не обладаетвыбранный метод такими свойствами, не будет их и в программе, а, значит, ине будет высокой эффективности выполнения задачи. Всё то же самоекасается и алгоритмов. При этом нужно всё же иметь в виду, что иногдаструктура программы и соответственно алгоритма не позволяет в принципеполучить эффективную реализацию задачи, но такая ситуация встречается нетак часто.Формулировка задачиОпределение методарешенияСоставление моделиисследуемого объектаРазработка алгоритмаВыбор технологиипрограммированияРазработка и выполнениепрограммыРис. 1. Процесс решения задачи на параллельной ВСЗадачаРазработка параллельных методов илимодификация последовательныхалгоритмов.Разработка параллельных алгоритмов.Модели и языкипараллельных вычисленийкодирование на ЯПВыполнение.Что подлежит распараллеливанию в процессе решения задачи насовременных архитектурах?1.Задача (декомпозиция на подзадачи меньшей размерности)2.Метод решения3.Алгоритм4.Программа5.Циклы6.ВыраженияСложная задача.

Характеристики сложности (размерность,трудоемкость, объем требуемой памяти и др.) Основные классысложных задачНеформальное определение: сложная задача – это задача, котораяне может быть эффективно решена на существующих массовыхвычислительных средствах с помощью традиционных методов иалгоритмов решенияХарактеристики сложности:1.

Т – трудоемкость решения задачи (часто определяется числоммультипликативных операций).2. О – объем обрабатываемой информации.3. t доп. – допустимое время решения задачи.4. Р – требуемая производительность, Р = Т/t доп.Декомпозиция процессов решения сложных задач – основа построенияэффективных параллельных алгоритмов и программОсновным подходом к решению любой сложной задачи являетсядекомпозиция (разбиение задачи на совокупность подзадач меньшейразмерности).Згдедекомпозиция{З1, З2, … Зi, … Зр, Зсв},Зi – i-ая подзадача.Зсв – задача связи.T1(n) - трудоемкость решения некоторой задачи З(n), где n – эторазмерность задачи, на одном вычислителе с помощью наилучшегопоследовательного алгоритма.Tр(n) – трудоемкость решения задачи З(n) на p вычислителях сиспользованием некоторого параллельного алгоритма.T(Зi) – трудоемкость решения подзадачи ЗiT(Зсв) – трудоемкость решения задачи связи ЗсвВ зависимости от соотношения трудоемкостей задачи связи и подзадачзависит, к какому классу относится исходная сложная задача З.Принято выделять четыре основных класса сложных задач:1.

Несвязная сложная задача.2. Слабосвязная сложная задача.3. Среднесвязная сложная задача4. Сильносвязная сложная задача.Пусть Wij – трудоемкость обменных взаимодействий между Зi-ой и Зj-ойподзадачами в процессе решения задачи З.Если:1. ΣΣ Wij → 0, или T(Зсв) → 0, то З относится к классу несвязных сложных.j i2. ΣΣ Wij< max T(Зi), или T(Зсв )< max T(Зi ),то З – слабосвязная задача.j i3. ΣΣ Wij≅ max T(Зi), или T(Зсв )≈ max T(Зi ), то З – среднесвязная задача.j i4.

ΣΣ Wij > max T(Зi), или T(Зсв )> max T(Зi ), то З – сильносвязная задача.j iИллюстрация классов сложных задач на примере решения СЛАУ (системалинейных алгебраических уравнений) большой размерностиПусть имеем: СЛАУ, которая представлена в матричной форме:А×Х = ВХ=А-1× ВХ–?Рассмотрим задачу как сложную, декомпозированную на р подзадач меньшейразмерности:З →{З1, З2, … Зi, … Зр, Зсв};Зi → АiХi = Bi,где dimA = n×n,dimAi ≅ (n/p)2 = ni×ni, где ni = n/p, где р – число подсистемВ зависимости от портрета матрицы коэффициентов эта задача можетбыть отнесена к несвязной, слабосвязной, среднесвязной исильносвязной.АХ...В=⇒n×nЕсли вне диагональных блоков все элементы равны 0, то имеем несвязнуюсложную задачу.Если же вне диагональных блоков имеются неравные 0 элементы, то задачурешения СЛАУ можно, в зависимости от числа этих вне диагональныхблоков, отнести к остальным классам: слабосвязной, среднесвязной илисильносвязной задачи.Для эффективного решения такого рода СЛАУ целесообразно преобразоватьматричную форму к виду блочно-диагональной с окаймлениями (БДМО)AX=B A1 Q1A2Q2ApQpC1 C2  Cp Wc X1   B1 X   B  2  2  =      X p  B p X c   Bc    (∗)Размерность «новой системы» равна (n×Nc)×(n+Nc), где Nc – число внешнихсвязей между подзадачами (подсистемами), n - размерность исходнойсистемы AX=Bp - число подсистем вида A i X i = Bidim A i = n i∑ ni = nQi , Ci - матрицы связи подсистемdim Q i = N c × n idim C i = n i × N cN c - размерность уравнений связиdim X c = N c ; dim B c = N c ; dim Wc = N c × N cИспользуя блочный (клеточный) подход к решению (∗) , запишем(∗) в виде:AQC X B = Wc  X c  B c Тогда имеем систему:AX + CX c = B ⇒ X c − ?QX + W X = B ⇒ X - ?c ccЕсли Nc<ni , то данная задача относится к классу слабосвязных.Если система линейных уравнений АХ = В имеет матрицу коэффициентов,плотно заполненную элементами, то данная СЛАУ относится к классусильносвязных задач.Характеристики параллельности (ускорение, эффективность,стоимость и ценность параллельного решения).Характеристики параллельностиУскорение параллельного вычисленияξ= T1(n) /Tр(n)Чем менее связная задача, тем больше число подсистем на которыецелесообразно разбивать исходные подзадачи.

Чем более связная задача, темменьше число подсистем р на которые следует разбивать исходныеподзадачи. Чем ближе значение ускорения к р (ξ→ р), тем лучшепараллельный алгоритм и соответствующая параллельная программаЭффективность параллельного вычисленияξ*= ξ/р=T1(n) /(Tр(n)*р)Чем ближе значение ускорения к р, тем более эффективен (ξ →1)параллельный алгоритм и соответствующая параллельная программа*Цена параллельного решенияCp = p*Tp(n)Ценность параллельного решенияFp = ξ/Cp = T1(n)/p*Tp2(n).Иллюстрация приведенных характеристик на примере решения СЛАУбольшой размерности путем декомпозиции на подзадачи меньших размеровξР/lnP -теория сложностирlog2P -гипотеза МинскогоЭффективность параллельных вычислений ξ*=ξ/р → 1, т.к.

ξ → р.(Реально 0.5-0.7)Пример:СЛАУ n = 104α - коэффициент связностиα→10-4р – число вычислителей и числоподзадачξ30α~10-320α~10-210р2101001000Чем менее связная задача, тем больше число подсистем, на которые целесообразноразбивать исходные подзадачи. Чем более связная задача, тем меньше число подсистем рна которые следует разбивать исходные подзадачи.ξ*1α~10-4α ~ 10-30.5α~10-2p2101001000ξ*= T1(n) /(Tр(n)*р)Закон Амдаля и его следствияИспользуется для оценки параллельных алгоритмов, структуракоторых предполагает выполнение всех операций либо с максимальной, либос минимальной степенью параллелизма, время на подготовку передачиданных отсутствует.Например, для структуры изображенной ниже, где минимальнаястепень =1, максимальная =3, можно использовать оценку ускорения позакону Амдаля.Определим ускорение параллельного алгоритма исходя из анализачастей алгоритма, выполняемых последовательно и параллельно:Предположим, что программе доля операций, которые нужновыполнять последовательно, равна β, где 0<= β <=1 (при этом доляпонимается не по статическому числу строк кода, а по числу операций впроцессе выполнения).Крайние случаи в значениях β соответствуют полностью параллельным(β =0) и полностью последовательным (β =1) программам.Чтобы оценить, какое ускорение S может быть получено накомпьютере из p процессоров при данном значении β, можновоспользоваться законом Амдала:S=T1 (n)1− β(β +)T1 (n) + t допp, где tдоп – время на накладные расходыβ - доля операций, выполнение которых невозможно одновременно сдругими операциями.Проанализируем полученное соотношение:1.