Планирование распределения программных модулей по процессорам вычислительной системы
Авторы: Руденко Ю.М.
Опубликовано в выпуске: #11(23)/2013
DOI: 10.18698/2308-6033-2013-11-1010
Раздел: Информационные технологии | Рубрика: Компьютерные системы и сети
Рассмотрены вопросы планирования распределения программных модулей по узлам однородной вычислительной системы с разделяемой памятью. В качестве инструмента планирования использованы временные диаграммы ранних сроков окончания выполнения программных модулей. Это позволяет заранее распределять модули по узлам вычислительной системы и минимизировать время решения поставленной задачи и количество процессоров, используемых для ее решения. При вычислении ранних сроков окончания выполнения программных модулей учитывалось время передачи информации между нитями, составленными из программных модулей. На основе этих диаграмм созданы нити программных модулей, каждая из которых выполнена на своем процессоре. Между некоторыми процессорами существует обмен информацией, требующий определенных временных затрат, которые необходимо учесть, скорректировав соответствующим образом временные диаграммы. В ряде случаев некоторое количество процессоров может быть использовано в качестве передающих звеньев (транзитных вычислительных элементов). Построение плана распределения программных модулей по процессорам рассмотрено на примере структуры вычислительной системы из класса Бп-графов типа "Циркулянт" G(11, 1, 2, 5). Так как диаметр этой вычислительной системы равен двум, то максимальное количество транзитных процессоров для соответствующей передачи равно единице. Алгоритм обработки данных представлен в виде граф-схемы, в которой цикл по счетчику циклов приведен в явном виде, так как реализация этой части алгоритма является наиболее сложной. Вначале нити распределяются по процессорам произвольно, затем осуществляется построение межнитевых связей. Здесь важно, чтобы количество неиспользуемых в заданные отрезки времени процессоров было достаточным для построения этих связей. При этом в случае необходимости можно минимизировать количество транзитных процессоров и время решаемой задачи, осуществляя различные варианты размещения нитей на вычислительных модулях.
Литература
[1] Хорошевский В.Г. Архитектура вычислительных систем. Москва, Изд-во МГТУ им. Н.Э. Баумана, 2005, 511 с.
[2] Корнеев В.В. Параллельные вычислительные системы. Москва, Гелиос АРВ, 2004, 487 с.
[3] Водяхо А.И., Горнец Н.Н., Пузанков Д.В. Высокопроизводительные системы обработки данных. Москва, Высшая школа, 1997, 150 с.
[4] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт-Петербург, БХВ-Петербург, 2002, 600 с.
[5] Руденко Ю.М., Мельдианов П.В. Алгоритм преобразования последовательного алгоритма в параллельный. Информатика и системы управления в ХХ1 веке. Сб. тр. молодых ученых, аспирантов, студентов. Москва, 2007, вып. 5, с. 127-131
[6] Руденко Ю.М. Представление параллельных алгоритмов в виде граф-схем. Аэрокосмические технологии. Науч. материалы междунар. науч.-техн. конф. МНТК. Москва, 2009, с. 179-181
[7] Павлов А.Е., Руденко Ю.М. Представление трансляционно-циклического обмена в виде граф-схемы. Современные информационные технологии. Сб. тр. кафедры "Компьютерные системы и сети". Москва, НИИ РЛ МГТУ им. Н.Э. Баумана, 2011, с. 125-129
[8] Мусина Л.В., Руденко Ю.М. Учет времен задержек на вычислительных модулях при реализации граф-схем. Современные информационные технологии. Сб. тр. кафедры "Компьютерные системы и сети". Москва, НИИ РЛ МГТУ им. Н.Э. Баумана, 2011, с. 133-137
[9] Руденко Ю.М. Распределение программных модулей по узлам вычислительной сети с общим полем памяти для граф-схем параллельных алгоритмов. Наука и образование: электрон. науч.-техн. издание. 2011. № 10. URL: http://tehnomag.edu.ru/doc/235842.html DOI: 77-30569/235842 (дата обращения 15 марта 2013)
[10] Руденко Ю.М., Волкова Е.А. Вычислительные системы. Москва, Изд-во МгТУ им. Н.Э. Баумана, 2010, 211 с.
[11] Барский А.Б. Параллельные процессы в вычислительных системах. Москва, Радио и связь, 1990, 256 с.