СПОСОБ ОПРЕДЕЛЕНИЯ СТРУКТУРЫ ГИБРИДНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ
METHOD OF DETERMINING STRUCTURE OF HYBRID COMPUTER SYSTEM

Изобретение относится к области вычислительной техники и может применяться для построения гибридных вычислительных систем, содержащих MIMD-компоненту, состоящую из одного или нескольких процессоров, и SIMD-компоненту, состоящую из одного или нескольких арифметических ускорителей.
Гибридная система MIMD-SIMD (гибридная система) является сочетанием параллельно работающих SIMD и MIMD компонент. Эта параллельная архитектура способна достигать больший коэффициент ускорения вычислений по сравнению с одним процессором, чем соответствующая MIMD архитектура может достигать одна.
1
M
S
1
SIMD
Наиболее близким аналогом по совокупности существенных признаков к заявляемому изобретению является способ определения структуры гибридной вычислительной системы 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 и T (в аналоге T и T соответственно) исполнения MIMD и SIMD фрагментов программы одним процессором и одним ускорителем соответственно, определение удельного ускорения ρ (в аналоге X) длительности выполнения SIMD фрагмента программы одним ускорителем по сравнению с длительностью выполнения этого фрагмента одним процессором и на основе полученных данных изменение количества ускорителей, входящих в структуру гибридной вычислительной системы, и оценку значения коэффициента ускорения вычислений, достигаемого этой системой.
Недостатком изложенного способа является неполное использование возможностей гибридной вычислительной системы из-за неизменного количества процессоров в структуре гибридной системы, что исключает для определенного класса вычислительных процессов возможность достижения большего ускорения по сравнению с использованием систем с изменяемым количеством ускорителей.
Задачей, на решение которой направлено заявляемое изобретение, является создание способа, позволяющего создавать структуру гибридной вычислительной системы, в соответствии с особенностями исполняемого вычислительного процесса.
Технический результат заключается в уменьшении длительности вычислительного процесса за счет создания структуры гибридной вычислительной системы, учитывающей особенности конкретного процесса.
1
M
S
Данный технический результат достигается тем, что в заявляемом способе определения структуры гибридной вычислительной системы, содержащей MIMD-компоненту, состоящую по крайней мере из одного процессора, и SIMD-компоненту, состоящую по крайней мере из одного ускорителя, включающем измерение длительности T получения решения задачи посредством выполнения программы одним процессором, измерение длительностей T и T исполнения 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, используемый в наиболее близком аналоге. Их общей чертой является наличие большого количества «простых» арифметических устройств, имеющих в совокупности существенно большую по сравнению с процессором производительность, достигаемую на специфичных фрагментах программ.
Для осуществления заявляемого способа:
1
- измеряют системным таймером длительность T, требуемую для получения решения задачи посредством выполнения всей программы одним процессором,
M
- измеряют системным таймером длительность T выполнения MIMD фрагмента одним процессором,
S
- измеряют системным таймером длительность T выполнения SIMD фрагмента одним ускорителем,
- из полученных значений определяют долю длительности выполнения MIMD фрагмента  и величину удельного ускорения
- сравнивают отношение доли длительности вычислений, выполняемых одним ускорителем, к доле длительности вычислений, выполняемых одним процессором, с величиной удельного ускорения ρ. Если , то в вычислительной системе увеличивают количество процессоров. Если , то увеличивают количество ускорителей.
Работоспособность заявляемого способа подтверждается следующими соотношениями, которые излагаются применительно к распараллеливанию методом умножения для постоянного размера задачи (закон Густафсона [см., например, Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. С.-Пб, 2004 г., стр.488-490]) и применительно к распараллеливанию методом деления для изменяемого размера задачи (закон Амдаля [см., например, Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. С.-Пб, 2004 г., стр.486-488]).
1
Для решения задачи одним процессором требуется интервал длительностью T.
Полагаем, что процесс решения этой же задачи гибридной вычислительной системой, содержащей один процессор и один ускоритель, занимает интервал длительностью, вычисляемой по формуле
M
1
где T=Тφ - длительность выполнения 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 вычисляют по формуле
q,r
m,1
q,r
1,n
В общем случае K=K, если q>r, где  и K=К, если q<r, где ; полагаем, что q и r таковы, что m или n - целые.
Оценим условия, при которых , то есть увеличение количества процессоров 1 целесообразнее увеличения количества ускорителей 2.
Очевидно, для этого необходимо выполнение неравенства
которое выполняется, если .
Если , то увеличение количества процессоров, либо увеличение количества ускорителей одинаково влияют на длительность вычислительного процесса.
Итак, целесообразность наращивания того или иного компонента определяют из первичных свойств вычислительного процесса.
Коэффициент ускорения в режиме деления системой, содержащей q процессоров и один ускоритель, вычисляется по формуле
Получаем
При q→∞ имеем наибольшее значение
При ρ>q выполняется
Для системы, содержащей один процессор и r ускорителей, получаем
При r→∞ имеем
Значение  если
Коэффициент ускорения  достигаемый системой, содержащей q процессоров и r ускорителей при q=r, вычисляется по формуле
q,r
m,1
Очевидно, K=K, если q>r, где  и  если q<r, где  полагаем, что q и r таковы, что m или n - целые.
Оценим параметры процесса, для которого в режиме деления целесообразно увеличивать количество процессоров. Очевидно, должно выполняться условие
Это справедливо, если .
Если , то увеличение количества процессоров, либо увеличение количества ускорителей одинаково влияют на длительность вычислительного процесса.
То есть целесообразность ускорения процесса вычислений в режиме деления увеличением количества процессоров или количества ускорителей зависит, как и в режиме умножения, от значений параметров φ и ρ.
Полученные для режимов умножения и деления коэффициенты ускорения вычислений приведены в таблице 2.
Отметим идентичность этих коэффициентов для обоих режимов при одинаковом количественном и качественном составе вычислителей. Для обоих режимов целесообразно увеличивать количество процессоров, если выполняется .
Пример осуществления способа
Определим структуру гибридной вычислительной системы для решения задачи определения значений потенциала Морзе, используемых в молекулярной динамике.
1
Длительность вычислений одним процессором для задачи размером 55×55×55 периодов кристаллической решетки была измерена системным таймером, она составила T=22,96 с. Распараллеливание выполнялось в режиме умножения.
1,1
M
S
Определяем для этой же задачи системным таймером длительность вычисления гибридной системой, содержащей q=1 процессоров и r=1 ускоритель, она составила T=9,87 с; при этом длительность выполнения MIMD фрагмента одним процессором составила T=7,07 с, а длительность выполнения SIMD фрагмента одним ускорителем составила T=2,80 с.
Из измеренных значений определяем
Поскольку , то в структуре гибридной системы для этой программы целесообразно увеличить количество процессоров.
2,1
2,1
Например, если в этой системе применить q=2 процессоров и r=1 ускоритель, то согласно (2) получаем . Измеренное системным таймером экспериментальное значение Т=13,22 с. Соответствующие теоретическое и экспериментальное значения коэффициентов ускорения  и К=3,76.
Если для решения этой задачи применить, следуя прототипу, гибридную систему, содержащую q=1 процессор и r=2 ускорителей, то  и .
В рассмотренном примере заявляемый способ позволил создать гибридную вычислительную систему, которая предоставляет возможность решить данную задачу вычисления потенциалов в 1,3 раза быстрее по сравнению с системой, построенной ранее известным способом.
Аналогично, используя (2) и (6) и экспериментальные данные, можно показать, что гибридная система, содержащая q=4 процессора и r=1 ускоритель, позволяет решить указанную задачу в 1,67 раза быстрее по сравнению с системой из q=1 процессора и r=4 ускорителей, построенной ранее известным способом.
Таким образом, заявляемый способ позволяет создавать структуру гибридной вычислительной системы, учитывающую особенности исполняемого вычислительного процесса. Это в свою очередь позволяет уменьшить длительность вычислений и ускорить процесс решения прикладных задач.