Результат интеллектуальной деятельности: СПОСОБ ОПРЕДЕЛЕНИЯ СТРУКТУРЫ ГИБРИДНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ

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

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

Наиболее близким аналогом по совокупности существенных признаков к заявляемому изобретению является способ определения структуры гибридной вычислительной системы MIMD-SIMD (см. www.elsevier.com/locate/parco Parallel Computing 29 (2003) 21-36, MIMD-SIMD hybrid system-towards a new low cost parallel system, Leo Chin Sim, Heiko Schroder, Graham Leedham). Способ включает измерение длительности T₁ получения решения задачи посредством выполнения программы одним процессором, измерение длительностей T_M и T_S (в аналоге T₁ и T_SIMD соответственно) исполнения MIMD и SIMD фрагментов программы одним процессором и одним ускорителем соответственно, определение удельного ускорения ρ (в аналоге X) длительности выполнения SIMD фрагмента программы одним ускорителем по сравнению с длительностью выполнения этого фрагмента одним процессором и на основе полученных данных изменение количества ускорителей, входящих в структуру гибридной вычислительной системы, и оценку значения коэффициента ускорения вычислений, достигаемого этой системой.

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

Задачей, на решение которой направлено заявляемое изобретение, является создание способа, позволяющего создавать структуру гибридной вычислительной системы, в соответствии с особенностями исполняемого вычислительного процесса.

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

Данный технический результат достигается тем, что в заявляемом способе определения структуры гибридной вычислительной системы, содержащей MIMD-компоненту, состоящую по крайней мере из одного процессора, и SIMD-компоненту, состоящую по крайней мере из одного ускорителя, включающем измерение длительности T₁ получения решения задачи посредством выполнения программы одним процессором, измерение длительностей T_M и T_S исполнения MIMD и SIMD фрагментов программы одним процессором и одним ускорителем соответственно, определение удельного ускорения ρ длительности выполнения SIMD фрагмента программы одним ускорителем по сравнению с длительностью выполнения этого фрагмента одним процессором и на основании полученных данных изменение количества ускорителей, входящих в структуру гибридной вычислительной системы, в отличие от прототипа определяют долю φ длительности выполнения MIMD-фрагмента одним процессором и долю 1-φ длительности выполнения SIMD-фрагмента одним процессором относительно длительности выполнения программы одним процессором, сравнивают отношение доли длительности выполнения SIMD фрагмента одним процессором к доле длительности выполнения MIMD фрагмента одним процессором с величиной удельного ускорения длительности выполнения SIMD фрагмента одним ускорителем по сравнению с длительностью выполнения SIMD фрагмента одним процессором, при этом при увеличивают количество процессоров MIMD компоненты, а при увеличивают количество ускорителей SIMD компоненты.

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

Изобретение поясняется чертежами: на фиг.1 приведена структура гибридной вычислительной системы; на фиг.2 приведена схема определения доли длительности выполнения MIMD фрагмента и доли SIMD фрагмента и ускорения вычислений на этих фрагментах; на фиг.3 приведена таблица 1 с оценками длительностей вычислений; на фиг.4 в таблице 2 приведены значения коэффициентов ускорения.

Заявляемый способ осуществляется следующим образом.

Гибридная вычислительная система содержит q процессоров 1, образующих MIMD компоненту и выполняющих MIMD фрагмент программы вычислений, и r арифметических ускорителей 2, образующих SIMD компоненту и выполняющих SIMD фрагмент программы вычислений.

В качестве MIMD компоненты могут применяться любые вычислительные системы класса MIMD; процессор MIMD компоненты - отдельный процессорный элемент системы класса MIMD [Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. С.-Пб, 2004 г., стр.586].

Примерами SIMD-компонент, которые могут быть использованы при реализации способа, являются общеизвестные арифметические ускорители фирм NVIDIA и AMD, процессоры Cell фирмы IBM, ClearSpeed фирмы Intel, а также арифметический ускоритель Systola 1024, используемый в наиболее близком аналоге. Их общей чертой является наличие большого количества «простых» арифметических устройств, имеющих в совокупности существенно большую по сравнению с процессором производительность, достигаемую на специфичных фрагментах программ.

Для осуществления заявляемого способа:

- измеряют системным таймером длительность T₁, требуемую для получения решения задачи посредством выполнения всей программы одним процессором,

- измеряют системным таймером длительность T_M выполнения MIMD фрагмента одним процессором,

- измеряют системным таймером длительность T_S выполнения SIMD фрагмента одним ускорителем,

- из полученных значений определяют долю длительности выполнения MIMD фрагмента и величину удельного ускорения

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

Работоспособность заявляемого способа подтверждается следующими соотношениями, которые излагаются применительно к распараллеливанию методом умножения для постоянного размера задачи (закон Густафсона [см., например, Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. С.-Пб, 2004 г., стр.488-490]) и применительно к распараллеливанию методом деления для изменяемого размера задачи (закон Амдаля [см., например, Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. С.-Пб, 2004 г., стр.486-488]).

Для решения задачи одним процессором требуется интервал длительностью T₁.

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

где T_M=Т₁φ - длительность выполнения MIMD фрагмента одним процессором;

0≤φ≤1 - доля длительности выполнения MIMD фрагмента;

- длительность выполнения SIMD фрагмента одним ускорителем;

ρ>1 - удельное ускорение длительности выполнения SIMD фрагмента, достигаемое применением ускорителя, по сравнению с процессором.

Изложенная декомпозиция вычислительного процесса применительно к распараллеливанию методом деления для q процессоров 1 и одного ускорителя 2 представлена на фиг.2.

Длительность вычислений в режиме умножения системой, содержащей q процессоров 1 и один ускоритель 2, вычисляется по формуле

Если система содержит 1 процессор 1 и r ускорителей 2, то

Аналогично получаем - длительности вычислений в режиме деления системой, содержащей q процессоров 1, один ускоритель 2 и, соответственно, один процессор 1 и r ускорителей 2.

Оценки лительностей вычислений сведены в таблице 1.

Значения параметров ρ и φ определяют для простейшего вычислителя, содержащего один процессор и один ускоритель. Они называются первичными параметрами.

Коэффициент ускорения в режиме умножения системой, содержащей q процессоров 1 и один ускоритель 2, вычисляют по формуле

Подставляя

в формулу (4) находим

Очевидно, при q→∞ имеем максимальное значение .

Чтобы выполнялось (то есть, чтобы применение ускорителей 2 имело смысл по сравнению с простым увеличением количества процессоров 1), необходимо выполнение условия

Это достигается, если q≤ρ.

Для системы, содержащей один процессор и r ускорителей, коэффициент ускорения вычисляют по формуле

Очевидно при r→∞.

Значение , если .

Коэффициент ускорения для системы, содержащей q процессоров и r ускорителей, при q=r вычисляют по формуле

В общем случае K_q,r=K_m,1, если q>r, где и K_q,r=К_1,n, если q<r, где ; полагаем, что q и r таковы, что m или n - целые.

Оценим условия, при которых , то есть увеличение количества процессоров 1 целесообразнее увеличения количества ускорителей 2.

Очевидно, для этого необходимо выполнение неравенства

которое выполняется, если .

Если , то увеличение количества процессоров, либо увеличение количества ускорителей одинаково влияют на длительность вычислительного процесса.

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

Коэффициент ускорения в режиме деления системой, содержащей q процессоров и один ускоритель, вычисляется по формуле

Получаем

При q→∞ имеем наибольшее значение

При ρ>q выполняется

Для системы, содержащей один процессор и r ускорителей, получаем

При r→∞ имеем

Значение если

Коэффициент ускорения достигаемый системой, содержащей q процессоров и r ускорителей при q=r, вычисляется по формуле

Очевидно, K_q,r=K_m,1, если q>r, где и если q<r, где полагаем, что q и r таковы, что m или n - целые.

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

Это справедливо, если .

Если , то увеличение количества процессоров, либо увеличение количества ускорителей одинаково влияют на длительность вычислительного процесса.

То есть целесообразность ускорения процесса вычислений в режиме деления увеличением количества процессоров или количества ускорителей зависит, как и в режиме умножения, от значений параметров φ и ρ.

Полученные для режимов умножения и деления коэффициенты ускорения вычислений приведены в таблице 2.

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

Пример осуществления способа

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

Длительность вычислений одним процессором для задачи размером 55×55×55 периодов кристаллической решетки была измерена системным таймером, она составила T₁=22,96 с. Распараллеливание выполнялось в режиме умножения.

Определяем для этой же задачи системным таймером длительность вычисления гибридной системой, содержащей q=1 процессоров и r=1 ускоритель, она составила T_1,1=9,87 с; при этом длительность выполнения MIMD фрагмента одним процессором составила T_M=7,07 с, а длительность выполнения SIMD фрагмента одним ускорителем составила T_S=2,80 с.

Из измеренных значений определяем

Поскольку , то в структуре гибридной системы для этой программы целесообразно увеличить количество процессоров.

Например, если в этой системе применить q=2 процессоров и r=1 ускоритель, то согласно (2) получаем . Измеренное системным таймером экспериментальное значение Т_2,1=13,22 с. Соответствующие теоретическое и экспериментальное значения коэффициентов ускорения и К_2,1=3,76.

Если для решения этой задачи применить, следуя прототипу, гибридную систему, содержащую q=1 процессор и r=2 ускорителей, то и .

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

Аналогично, используя (2) и (6) и экспериментальные данные, можно показать, что гибридная система, содержащая q=4 процессора и r=1 ускоритель, позволяет решить указанную задачу в 1,67 раза быстрее по сравнению с системой из q=1 процессора и r=4 ускорителей, построенной ранее известным способом.

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