Анализ существующих процедур размещения задач в параллельных вычислительных системах с использованием аппаратных ускорителей

Последовательная архитектура представления вычислительных систем не удовлетворяет современным требованиям вычислительной техники. В это связи вычислительные системы с параллельной архитектурой находят все большее применение [1, c. 79]. Этому способствует развитие архитектур персональных и мобильный процессоров, которые строятся на многоядерной и многопоточной архитектурах. В таких системах характерна обработка нескольких потоков одновременно за счет использования ресурсов как одного так и нескольких ядер.

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

Решенные поставленной задачи целесообразно выполнять на аппаратном уровне, используя специализированные ускорители. Данный подход позволит уменьшить время поиска размещения и проводить его с большей оптимальностью на заданном временном интервале. Входными данными для ускорителя является исходные данные задачи от управляющего процесса. Ускоритель результат поиска размещения выдает в управляющий процесс, который осуществляет размещение в параллельной системе. Подобный подход ранее использовался при решении сходный по типу задач в многопроцессорных параллельных системах [2, c. 406]. Например при размещении монтажных схем в рамках коммутационно-монтажного проектирования ЭВМ.

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

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

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

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

Современные ПС распадаются на два крупных класса: системы с общей (SMP) и распределенной памятью (MPP). Существуют также системы, которые представляют промежуточный вариант между SMP и MPP-системами. Такие системы называются NUMA-архитектурами. В них память физически распределена, но логически общедоступна. В качестве коммерческих представителей этих классов выделяются Cray T3D, Origin, Intel Paragon.

Топологии современных ПС разбиваются на три класса в соответствии с предельным размером. Топологии малого размера используются, в основном, при построении ПС с количеством процессоров N=О(10). К ним относят системы с линейной, кольцевой, шинной и с некоторыми другими видами организации. Такие системы применяются в основном как «кластеры» для построения более сложных систем. В ПС со «средним» количеством модулей (N=О(100)) используются матричные и древовидные топологические модели. Они обеспечивают простой механизм наращивания и позволяют строить системы повышенной отказоустойчивости (особенно это касается матричной модели). Матричные ПС можно рассматривать как суперпозицию кольцевых или линейных структур. При необходимости построения систем с большим количеством процессоров (N>1000) применяются многомерные топологии: «гиперкуб», «куб циклов», «двухсвязный гиперкуб». Они также включают топологии меньшего размера в качестве кластеров.

Подходы к задаче размещения принято различать по следующим признакам: 1) по степени точности получаемого результата, 2) по способу формирования размещения и 3) по степени однородности ПС. По степени точности выделяются точные и приближенные методы. В свою очередь, точные методы подразделяются на графо-теоретические, методы математического программирования и основанные на методе ветвей и границ. Приближенные методы в зависимости от способа формирования размещения включают три группы: последовательные, параллельно-последовательные и итерационные. Выделяют методы размещения для однородных и неоднородных систем. Применительно к однородным системам, в частности, к матричным ПС, существует две принципиально различных формулировки задачи размещения. Первая предполагает поиск оптимального распределения подзадач (программных модулей) между процессорами заранее определенной группы процессоров. Вторая нацелена на выделение групп процессоров поступающим задачам с максимизацией загрузки ПС без учета размещения подзадач. В настоящей работе принята первая формулировка.

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

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