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

005005224

ЦВЕТКОВА Юлия Александровна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭЛЕМЕНТОВ И УСТРОЙСТВ ДЛЯ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЕЙ ОРИЕНТИРОВАННЫХ НА ОБРАБОТКУ МНОГОМЕРНЫХ ЗАДАЧ

Специальности: 05.13.05 - Элементы и устройства вычислительной техники и систем управления 05.13.17 - Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата технических наук

- 8 ДЕК 2011

Таганрог - 2011

005005224

Работа выполнена в Технологическом институте федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет»

в г. Таганроге

НАУЧНЫЙ РУКОВОДИТЕЛЬ:

доктор технических наук, профессор Золотовский Виктор Евдокимович

НАУЧНЫЙ КОНСУЛЬТАНТ:

доктор технических наук, профессор Гузик Вячеслав Филиппович

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

кандидат технических наук, с.н.с. Гречишников Анатолий Иванович

доктор технических наук, профессор Ромм Яков Евсеевич

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Донской государственный технический университет г. Ростов-на-Дону

Защита диссертации состоится « 23 » декабря 2011 г. в 1420 на заседании диссертационного совета Д.212.208.21 Южного федерального университета по адресу: 347928, г.Таганрог, Ростовской области, пер. Некрасовский, 44, корпус Д, ауд. 406.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу: г. Ростов-на-Дону, ул. Пушкинская, 148

Автореферат разослан ноября 2011г.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, ГСП-17А, Ростовская область, г. Таганрог, пер. Некрасовский, 44, диссертационный совет Д 212.208.21

Ученый секретарь

диссертационного совета Д 212.208.21, доктор технических наук, профессор

Чернов Н.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

техники Таганрогского технологического института Южного Федерального университета.

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

Основные задачи исследования. Достижение поставленной цели предполагает решение следующих основных задач:

1. Анализ проблем построения высокопроизводительных параллельных вычислителей и определение путей их решения на основе разработки элементов и устройств вычислительной техники.

2. Синтез масштабируемой структуры высокопроизводительного параллельного вычислителя на основе комплексной разработки элементов и устройств вычислительной техники.

3. Разработка алгоритма моделирования параллельного решения задач и методики его применения для статического оптимального планирования.

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

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

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

Научная новизна диссертационной работы. Научная новизна работы состоит в следующем:

1.На базе кластера универсальных ЭВМ и параллельного вычислителя БМР-структуры (симметричный мультипроцессор) синтезирована масштабируемая структура кластера с использованием многослойной коммутации, отличающаяся от существующих структур кластеров универсальных ЭВМ наличием нескольких слоёв акселераторов, что позволяет повысить производительность кластера при параллельном решении многомерных задач.

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

производительности кластера при решении сложных по структуре многомерных задач.

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

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

Практическая значимость полученных результатов.

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

Реализация результатов работы.

Научные и практические результаты диссертационной работы использованы в федеральном Научно-производственном центре ОАО «Марс» (г.Ульяновск), в «ООО АРМСофт» (г.Волгоград), на линейном ледоколе «Капитан Демидов», в учебном процессе на кафедре Автоматизированных систем обработки информации и управления Ижевского государственного технического университета, на факультете Электроники и вычислительной техники Волгоградского государственного технического университета, а также в научно-исследовательских работах и в учебном процессе на кафедре Вычислительной техники Таганрогского

технологического института Южного Федерального университета, что подтверждено соответствующими актами об использовании.

Основные положения и результаты, выносимые на защиту:

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

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

3. Методика применения алгоритма матрично-группового моделирования для оптимального статического планирования параллельного решения сложных по структуре задач с учетом процессов обмена для повышения эффективности планирования и производительности кластера.

Структура и объем работы. Результаты работы изложены во введении, четырех главах и заключении. Общий объем диссертации 158 страниц, включая 43 иллюстрации, 16 таблиц, список литературы из 101 наименования и 2 приложения.

Апробация результатов работы.

Основные результаты диссертации докладывались и обсуждались на Конгрессе по интеллектуальным системам и информационным технологиям, Международных и Всероссийских научно-технических конференциях, в том числе на:

1.VIII-ой Международной научно-технической конференции «Интеллектуальные системы» (AIS'08) и ХХШ-ой Международной научно-технической конференции «Интеллектуальные САПР» (CAD-2008), Дивноморское, 2008.

2. Международной молодежной научно-технической конференции «Высокопроизводительные вычислительные системы», Таганрог, 2008.

3. Конгрессе по интеллектуальным системам и информационным технологиям (AIS-IT'09) - (IX-ая Международная научно-техническая конференция «Интеллектуальные системы'09» (AIS'09), XXIV-ая Международная научно-техническая конференция «Интеллектуальные САПР-2009» (CAD-2009)), Дивноморское, 2009.

4. Конгрессе по интеллектуальным системам и информационным технологиям (AIS-IT'09) - (IX-ая Международная научно-техническая конференция «Интеллектуальные системы'09» (AIS'09), Молодежная научно-техническая конференция «Интеллектуальные системы - 2009»), Дивноморское, 2009.

5. Международной конференции «Информационные технологии в образовании, технике и медицине», Волгоград, 2009.

6. Международной научно-практической конференции «Инновационная экономика и промышленная политика региона (ЭКОПРОМ-2009)», Санкт-Петербург, 2009.

7. УП-ой Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», Таганрог, 2009.

8. Всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации», Ульяновск, 2009.

9.17-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2010», Москва, 2010.

10. Всероссийской научно-технической конференции аспирантов, студентов и молодых учёных «Информатика и вычислительная техника», Ульяновск, 2010.

11. Российской школе-семинаре аспирантов, студентов и молодых учёных «Информатика, моделирование, автоматизация проектирования», Ульяновск, 2010.

Публикации. По результатам проведенных исследований опубликовано 14 печатных работ, из них 3 статьи - в журналах, включенных в список изданий, рекомендованных ВАК.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Классы решаемых многомерных задач представлены задачами, математические модели которых относятся к распределенным и сосредоточенным. Многомерные задачи указанных классов относятся к категории вычислительно-трудоемких и для их решения за приемлемое время требуются высокопроизводительные вычислители уровня суперЭВМ.

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

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

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

Проведенные исследования показали, что наиболее эффективными направлениями повышения производительности вычислителей до уровня суперЭВМ при решении многомерных задач являются создание кластеров универсальных ЭВМ, введение ускорителей вычислительного процесса в универсальные ЭВМ и реализация многослойных вычислений. Перспективность кластеров ЭВМ подтверждается увеличением их доли в списке ТОР 500 за последнее десятилетие, так на июнь 2010г. их доля составила 84,8%. Основной недостаток кластеров универсальных ЭВМ - это резкое снижение их пиковой производительности на задачах, требующих большого времени обмена данными. Для повышения производительности кластеров универсальных ЭВМ предложены специальные меры: оснащение универсальных ЭВМ (персональных компьютеров) несколькими акселераторами; обеспечение одновременно несколько альтернативных путей между двумя вычислительными узлами; обеспечение (аппаратное и программное) выполнения процессов обмена данными на фоне процессов вычислений; выбор коммуникационной среды с высокой пропускной способностью и малой латентностью; оптимальное планирование параллельных вычислений с учетом процессов обмена.

Во второй главе синтезирована и исследована структура кластера ЭВМ на основе многослойной коммутации. Кластер включает один коммутируемый слой на основе универсальных ЭВМ, в качестве которых могут быть использованы персональные компьютеры, и несколько специализированных слоев на основе акселераторов (АК). Каждая ЭВМ оснащается несколькими АК, при этом каждый АК может быть ориентирован на выполнение разных спецопераций (арифметических, графических, логических) или на одну крупную спецоперацию. Сложность и быстродействие коммутационной системы определяется проблемной ориентацией кластера. Акселераторы одной ЭВМ взаимодействуют между собой и с ЭВМ по внутренней шине. Акселераторы разных ЭВМ, но одного слоя взаимодействуют через коммутатор (Ком). В каждом слое образуется Л/2 независимых каналов обмена, где Я - число портов коммутатора. Структура кластера с пятислойной коммутацией, в которой предусматривается полный обмен между акселераторами разных ЭВМ через коммутатор, структурно объединяющий несколько многослойных коммутаторов (в дальнейшее такой коммутатор именуется многомерным), (коммутаторы Ком1, КомЗ, Ком, Ком5) представлена на рис.1.

Рис. 1 - Структура кластера с пятислойной коммутацией

Акселератор представляет собой универсальный вычислительный модуль (рис.2), выполненной на плате стандарта РС1/РС1-Х 32/64 , который содержит процессоры цифровой обработки сигналов (универсальный

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

Вычислительный исдугь

Универсальный Акселератор <АК)

Х7

Блок связи с ЭВМ

А—

Локальная память

Конвейерное ядро

Интерфейсный блок

Вычислитель"«« модуль

Вычислительный модуль

Локальная память

Конвейерное ядро

Интерфейсный блок

1Z

Локальная память

Конвейерное ядро

Интерфейсный блок

Ф

Рис. 2 - Структурная схема универсального вычислительного модуля

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

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

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

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

Проведено теоретическое исследование эффективности разработанного кластера с многослойной коммутацией на задаче моделирования разработки нефтесодержащего пласта. Для организации кластера были проанализированы известные коммутаторы и выбраны матричные координатные коммутаторы с полем коммутации 16x16 - микросхема К1209КП2 (рабочая частота 10МГц), на основе которой образована коммутационная система с полем коммутации 32x32.

Для расчета эффективности (т]) кластера использовались следующие соотношения между параметрами параллельной обработки задач в статическом режиме: = 5(Л0=Г,/Г^(А0; Т^Щ^т+Т^Ы),

где 8(М) - ускорение параллельной обработки задачи; тх и Тобр(Щ - время обработки задачи одним и N вычислителями; т (Ы) и г (М) - критическое время обработки задачи N вычислителями соответственно по процессам счёта и обмена. Результаты расчета эффективности одного слоя однородного кластера для пяти значений производительности вычислителя (операций в секунду) - р] = ю6оп/с; Р2=ю7оп/с; />3=ю8оп/с; />4 = 2-103оп/с; Р5 =4-108оп/с и увеличения их числа до N=30 представлены на рис.3.

Рис.3 - Зависимость эффективности параллельной обработки задачи от числа вычислителей кластера и их производительности

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

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

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

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

операторы разбиваются на группы (К=0;1;2;......;Кшах) независимых

операторов по матрице смежности графа алгоритма задачи, начиная со входных операторов, и процесс моделирования представляется линейной матрично-групповой моделью (МГМ):

/рГО. . р72 , .pi, . , pTKmax-l . рКйг-ч

где С = А' + В"; А' _ матрица счета; я* - преобразованная матрица обмена, с0 = В" (А0 = 0) - матрица ввода исходных данных, ВКтх - матрица вывода результатов обработки задачи.

Преобразование в" = /(В*), где В* - матрица обмена, учитывает максимально возможное время задержки при последовательной передаче данных от нескольких операторов группы «К» к одному оператору группы «К+1» для случая размещения всех операторов в разных процессорах.

Число операторов в каждой группе определяет её параллелизм п'.

Все введенные матрицы размера (/xnftl). Матрицы А"', В* всегда одного размера и их сложение осуществляется по общепринятым правилам.

Для расчёта по МГМ (1) расписания обработки задачи на

операторном уровне вводится динамическая матрица DK (К=0,1,2,......

Ктах), в которой формируется необходимая для планирования информация.

(1)

Операторы счёта группы (К+1) определяются как отстоящие на одно ребро от операторов группы К. Входные операторы имеют группу К=1. При этом в одной группе могут появляться зависимые операторы, возможно повторение операторов в разных группах. Если оператор оказался одновременно в группах К и (К+с1), то он заносится и в промежуточные

группы (К+1; К+2;......;........;К+с1-1) в случае его отсутствия. Такая

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

Элементами всех введенных матриц могут быть: I) положительное число или нуль (а=0) - указывает на наличие логической связи между операторами двух смежных групп и количественную характеристику этой связи; 2) отрицательное число (а < 0; спецсимвол) - указывает на отсутствие логической связи между операторами двух смежных групп. В работе для определённости выбрано число «-1».

В основе алгоритма лежит одна операция - сложение двух чисел, которая выполняется по правилу:

с = = Приа'Ь~° (2)

[ -1 при а и(ши)Ь<0

Преобразование Вк=/(вк) осуществляется по столбцам 0), соответствующих реальным операторам, и состоит в следующем: все положительные элементы столбца заменяются на сумму этих элементов

—к

вц =

Л '"Рг,1-°/ = 1)2...../;/ = 1,2,...У

2Х ,прив;>о

(3)

Расчёт матрицы йк (К=0,1,2....... Ктах) осуществляется по

соотношениям:

вк = + с*, ¿к = тах(^-. + ) .

/ = 1,2,3,...,/; ) = 1,2,3,...,У; т = 1,2,3,...,М. (4)

Расчёт элементов осуществляется по правилу: элементы ¡-ой

строки левой матрицы суммируются с соответствующими элементами >го столбца правой матрицы по правилу (2); из всех сумм выбирается

максимальная, которая есть искомое значение ■ Расчет элементов ^

может осуществляться параллельно.

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

V ~ т2 •/, где I -общее число операторов задачи, а т — среднее число операторов в одной группе.

Одной из причин появления избыточного ресурса кластера является неравномерность распределения параллелизма задачи пк по группам. Для таких задач при росте параллелизма обработки до дгтах = ускорение 8(Ы) и эффективность т|(М) имеют противоположный характер изменения -7(Лг) = 5(Лг)/Л^- Дальнейший рост л^ к увеличению 8(М) не приводит, а

т}(Ы) резко падает. Эффективность т|(Ы) характеризует загруженность процессоров. При параллельной обработке одной задачи не всегда удается обеспечить высокую загруженность из-за связанности процессоров.

Алгоритм позволяет моделировать отдельно обработку задачи по процессу счёта (при Вк = 0 ), по процессу обмена (при Ак =0). Это позволяет определять ускорение только по процессу счёта и оценивать его снижение, обусловленное процессом обмена. Расчёт только величин Тсч(при Вк = 0),

То6м (при Ак - 0) или Тобр лля ускорения расчёта может выполняться над

разными парами смежных матриц МГМ (1) параллельно.

Исходя из отмеченной особенности задач и возможностей алгоритма разработана методика оптимального планирования параллельной обработки (ПО) задач. Методика включает три этапа.

На первом этапе принимается решение о переходе к ПО задачи. Для этого моделируется ПО только по процессу счета (Вх = 0). Процессоры выделяются согласно операторному расписанию задачи, причем очередной процессор выделяется только в случае занятости ранее выделенных. Определяются максимальный параллелизм задачи (№пах), Тсч(№пах), ускорение и эффективность по счету - БсчСЫтах), г|сч(Ктах), по которым принимается решение - о нецелесообразности ПО или, при наличии запаса по ускорению, о расчете времени обработки с учетом процесса обмена -Тобр(Ышах), для чего моделируется отдельно процесс обмена (Л* =0) и определяется Тобм(№пах). Затем определяются Тобр(Ытах), 8(№пах), г^тах), по которым принимается одно из решений: 1)ПО нецелесообразна;

2) ПО целесообразна - перейти ко второму этапу, если №пах неоптимально;

3) ПО целесообразна - перейти к третьему этапу, если Ишах оптимально.

На втором этапе определяется оптимальное число процессоров, для чего проводится ряд циклов моделирования отдельно по процессам счёта и обмена при постепенном уменьшении числа процессоров (параллелизм обработки) до Ыопт, которое обеспечивает приемлемые значения ускорения и эффективности Б(Ыопт), пСЫопт). Затем переходят к третьему этапу.

На третьем этапе составляется расписание работы процессоров. Для этого: моделируется процесс ПО одновременно по процессам счёта и обмена; по динамическим матрицам составляется расписание ПО на операторном уровне; расписание с операторного уровня по таблице загрузки переносится на выбранные процессоры (Копт).

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

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

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

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

нефтеносном пласте в системе скважин без учета гравитационных и капиллярных сил. Расчет стационарного поля давлений осуществлялся сеточным методом на основе пятиточечного шаблона. Для аппаратной реализации ядра вычислительной функции использовалась ПЛИС АКегаБ^айхШ, разработка и моделирование проводилась в программе АКегаСЗиатвИ. Исходя из ядра функции была проведена оценка времени реализации функции при представлении чисел с плавающей запятой и выбрана оптимальная глубина конвейера.

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

Рис. 4. - Последовательное формирование слоев

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

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

В заключении сформулированы основные выводы и результаты диссертационной работы.

В приложениях приведены: УШ)Ь описание коммутатора и акты об использовании результатов исследования кандидатской диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

В ходе выполнения работы были получены следующие результаты:

1.На основе анализа проблем построения высокопроизводительных параллельных вычислителей обоснован выбор параллельного вычислителя кластерной структуры, как наиболее перспективной по критерию «производительность/цена» для организации высокопроизводительных комплексов структурного моделирования, ориентированных на решение многомерных задач. Предложены пути повышения производительности кластера универсальных ЭВМ на основе комплексной разработки элементов и устройств вычислительной техники, а также программных методов.

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

3. Синтезирован алгоритм матрично-группового моделирования параллельного решения сложных по структуре задач и разработана методика

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК:

1.Цветкова Ю.А. Комплексный подход к разработке высокопроизводительных кластерных вычислительных систем II Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2009, №4(82). С. 15-22.

2. Золотовский В.Е., Цветкова Ю.А. К вопросу о моделировании параллельной обработки задач в вычислительных системах. // Известия высших учебных заведений. Северо-кавказский регион. Технические науки. 2008, №3(145). С. 5-10 (лично автора - 0,35 п.л.).

3. Цветкова Ю.А. Комплексный подход к повышению эффективности многомашинных вычислительных систем. // Известия ЮФУ. Технические науки, апрель 2008, №4. С. 207-211.

В других изданиях:

4. Цветкова Ю.А. Алгоритм моделирования параллельной обработки задач в вычислительных системах // Труды Международных научно-технических конференций «Интеллектуальные системы» (АК'Ов) и «Интеллектуальные САПР» (САО-2008). Научное издание в 4-х томах. М.: Физматлит, 2008, Т.З. С. 22-25.

5.Цветкова Ю.А. Кластерная вычислительная система на основе двухслойной коммутации. // Инновационная экономика и промышленная политика региона (ЭКОПРОМ-2009) / Под ред. д-ра эконом, наук, проф. А.В.Бабкина: Труды VII Международной научно-практической конференции. Научное издание в 2-х томах. СПб.: Изд-во Политехи, ун-та, 2009, Т.2. С. 429432..

6.Цветкова Ю.А. Кластер на основе многослойной коммутации для организации высокопроизводительных комплексов моделирования // Всероссийская конференция с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации». Сборник научных трудов в 4-х томах. Ульяновск. УлГТУ, 2009, ТЗ. С. 41-43.

7.Цветкова Ю.А. К вопросу о выборе сосредоточенных коммутаторов при организации кластерной вычислительной системы с многослойной коммутацией. // Микроэлектроника и информатика - 2010. 17-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. - М.: МИЭТ, 2010. С. 226.

8.Цветкова Ю.А. Программно-технический комплекс для повышения эффективности моделирования разработки нефтяных месторождений. П Информатика, моделирование, автоматизация проектирования: сборник научных трудов / под ред. Н.Н.Войта. - Ульяновск: УлГТУ, 2010. С. 501-503.

9.3олотовский В.Е., Цветкова Ю.А. Проблемы построения высокоэффективных систем моделирования и разработка путей их решения // Труды конгресса по интеллектуальным системам и информационным технологиям (AIS-IT09). Международные научно-технические конференции «Интеллектуальные системы'09» (AIS'09) и «Интеллектуальные САПР-2009» (CAD-2009). Научное издание в 4-х томах. М.: Физматлит, 2009, Т.2. С.42-44 (лично автора - 0,1 пл.).

10. Цветкова Ю.А. О повышении качества планирования параллельной обработки задач в вычислительных системах // Информационные технологии в образовании, технике и медицине: материалы международной конференции / ВолгГТУ. - Волгоград, 2009. С. 98.

11. Золотовский В.Е., Цветкова Ю.А. Моделирование сложных систем на базе кластеров // Сборник трудов VII Всероссийской научной конференции молодых ученых, аспирантов и студентов. «Информационные технологии, системный анализ и управление». Таганрог. Изд-во ТТИ ЮФУ, 2009. С. 8993 (лично автора-0,1 п.л.).

12. Цветкова Ю.А. Алгоритм для решения задачи оптимального управления движением робота // Высокопроизводительные вычислительные системы. Материалы Пятой Международной научной молодежной школы. Материалы Международной молодежной научно-технической конференции. - Таганрог. Изд-во ТТИ ЮФУ, 2008. С. 442-445.

13. Цветкова Ю.А. Эволюция архитектур высокопроизводительных вычислительных систем // Труды конгресса по интеллектуальным системам и информационным технологиям (AIS-IT'09). Молодежная научно-техническая конференция «Интеллектуальные системы - 2009». Научное издание в 4-х томах. М..-Физматлит, 2009, Т.З. С. 361-364.

14. Цветкова Ю.А. О повышении эффективности кластерных вычислительных систем // Информатика и вычислительная техника: сборник научных трудов / под ред. В.Н.Негоды. - Ульяновск: УлГТУ, 2010. С. 515516.

Личный вклад автора в работах, написанных в соавторстве, состоит в следующем: [2] - разработка алгоритма моделирования параллельной обработки задач одновременно по процессам вычислений и обмена; использование фиктивных операторов для перехода от нерегулярного графа алгоритма задачи к регулярному алгоритму моделирования параллельной обработки задачи; разработка матричных спецопераций для расчета динамических матриц; проведение расчетов, подтверждающих работоспособность алгоритма; [9] -обоснование необходимости разработки алгоритмов оптимального планирования параллельного решения задач; [11] - комплексный подход к организации кластера.

Соискатель /луг Цветкова Ю.А.

Тип.ТТИ ЮФУ Заказ №36£тир/Ю экз.

ВВЕДЕНИЕ

ГЛАВА I. АНАЛИЗ ВЫЧИСЛИТЕЛЬНЫХ СРЕДСТВ ДЛЯ

РЕШЕНИЯ МНОГОМЕРНЫХ ЗАДАЧ

1.1. Классы решаемых многомерных задач

1.2.Анализ возможностей суперкомпьютеров различных классов для решения многомерных задач

1.3. Исследование возможностей кластеров ЭВМ для решения многомерных задач

1.4. Пути повышения производительности кластеров ЭВМ

1.5. Выводы

ГЛАВА 2. РАЗРАБОТКА И ИССЛЕДОВАНИЕ ЭЛЕМЕНТОВ И

УСТРОЙСТВ КЛАСТЕРА ЭВМ НА ОСНОВЕ многослойной КОММУТАЦИИ

2.1. Разработка элементов и устройств высокопроизводительного кластера на основе многослойных вычислении

2.2. Выбор типа коммутатора для организации кластера

2.3. Исследование характеристик разработанной структуры кластера на примере моделирования разработки нефтесодержащего пласта

2.4. Выводы

ГЛАВА 3. ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ

КЛАСТЕРОВ ЭВМ НА ОСНОВЕ СТАТИЧЕСКОГО

ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ ПРИ ОБРАБОТКЕ

МНОГОМЕРНЫХ ЗАДАЧ

3.1. Задачи, методы и проблемы исследования сложных систем

3.2. Разработка алгоритма моделирования параллельной обработки задач и методики его применения для статического оптимального планирования

3.2.1.Общая характеристика выбранного метода планирования

3.2.2. Матричные последовательности (модели) задач

3.2.3. Расчет основных параметров параллельной обработки задачи на основе ее матричной групповой модели

3.2.4.Методика применения алгоритма для статического оптимального планирования параллельной обработки задач

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

3.4. Выводы

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И

ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

ХАРАКТЕРИСТИК ЭЛЕМЕНТОВ И УСТРОЙСТВ

РАЗРАБОТАННОГО КЛАСТЕРА ПРИ РЕШЕНИИ ЗАДАЧИ

МОДЕЛИРОВАНИЯ РАЗРАБОТКИ НЕФТЕСОДЕРЖАЩЕГО

ПЛАСТА

4.1.Задача моделирования разработки нефтесодержащего пласта

4.2. Выбор программно-технических средств

4.3.Разработка модели программной реализации основных алгоритмов системы

4.4 .Разработка и описание программы моделирования основных алгоритмов системы

4.5. Руководство пользователя

4.6. Выводы

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

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

При достигнутом уровне технологий, структурных и программных решений производительность процессоров можно считать практически постоянной, близкой к теоретическому пределу, поэтому повышение производительности вычислителей идёт по пути объединения процессоров, однопроцессорных и многопроцессорных ЭВМ в разнообразные параллельные вычислители и повышения эффективности использования вычислительных ресурсов [28].

При переходе к параллельным вычислениям возникает проблема отображения графа алгоритма задачи на структуру параллельного вычислителя. От качества решения проблемы отображения зависит эффективность использования вычислительных ресурсов и производительность параллельного вычислителя. Для решения этой проблемы необходимо исследовать сложную информационную структуру задачи в целом, что требует разработки эффективных по временной сложности алгоритмов. Накопленный опыт разработки высокопроизводительных компьютеров показывает, что проблема отображения решается наиболее эффективно созданием проблемно-ориентированных параллельных вычислителей и реализацией структурного подхода к параллельному решению задач. При этом остро стоит проблема повышения их производительности при увеличении числа процессоров. Возрастающая сложность управления параллельной обработкой данных для многомерных задач, обусловленная большим количеством разнообразных операторов и логических связей между ними, а также неадекватностью структуры параллельного вычислителя структуре обрабатываемых задач, приводит к увеличению времени обменных операций, простою процессоров и резкому падению реальной производительности параллельного вычислителя по сравнению с теоретической. В этих условиях резко возрастает значение структурных и программных методов повышения производительности параллельных вычислителей [18].

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

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

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

Основные задачи исследования. Достижение поставленной цели предполагает решение следующих основных задач:

1. Анализ проблем построения высокопроизводительных параллельных вычислителей и определение путей их решения на основе разработки элементов и устройств вычислительной техники.

2. Синтез масштабируемой структуры высокопроизводительного параллельного вычислителя на основе комплексной разработки элементов и устройств вычислительной техники.

3. Разработка алгоритма моделирования параллельного решения задач и методики его применения для статического оптимального планирования.

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

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

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

Научная новизна работы. Научная новизна работы состоит в следующем:

1. На базе кластера универсальных ЭВМ и параллельного вычислителя БМР-структуры (симметричный мультипроцессор) синтезирована масштабируемая структура кластера с использованием многослойной коммутации, отличающаяся от существующих структур кластеров универсальных ЭВМ наличием нескольких слоев акселераторов, что позволяет повысить производительность кластера при параллельном решении многомерных задач.

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

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

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

Практическая значимость полученных результатов.

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

Реализация результатов работы. Научные и практические результаты диссертационной работы использованы в федеральном Научно-производственном центре ОАО «Марс» (г.Ульяновск), в «ООО АРМСофт» (г.Волгоград), на линейном ледоколе «Капитан Демидов», в учебном процессе на кафедре Автоматизированных систем обработки информации и управления Ижевского государственного технического университета, на факультете Электроники и вычислительной техники Волгоградского государственного технического университета, а также в научно-исследовательских работах и в учебном процессе на кафедре Вычислительной техники Таганрогского технологического института Южного Федерального университета, что подтверждено соответствующими актами об использовании.

Основные положения и результаты, выносимые на защиту:

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

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

3. Методика применения алгоритма матрично-группового моделирования для оптимального статического планирования параллельного решения сложных по структуре задач с учетом процессов обмена для повышения эффективности планирования и производительности кластера.

Структура и объем работы. Результаты работы изложены во введении, четырех главах и заключении. Общий объем диссертации 158 страниц, включая 43 иллюстрации, 16 таблиц, список литературы из 101 наименования и 2 приложения.

Апробация, публикация результатов работы.

Основные результаты диссертации докладывались и обсуждались на Конгрессе по интеллектуальным системам и информационным технологиям, Международных и Всероссийских научно-технических конференциях, в том числе на:

1.VIII -ой Международной научно-технической конференции «Интеллектуальные системы» (AIS'08) и ХХШ-ой Международной научно-технической конференции «Интеллектуальные САПР» (CAD-2008), Дивноморское, 2008.

2.Международной молодежной научно-технической конференции «Высокопроизводительные вычислительные системы», Таганрог, 2008.

3.Конгрессе по интеллектуальным системам и информационным технологиям (AIS-IT 09) - (IX-ая Международная научно-техническая конференция «Интеллектуальные системы4 09» (AIS09), XXIV-ая Международная научно-техническая конференция «Интеллектуальные САПР-2009» (CAD-2009)), Дивноморское, 2009.

4.Конгрессе по интеллектуальным системам и информационным технологиям (AIS-IT 09) - (IX-ая Международная научно-техническая конференция «Интеллектуальные системы'09» (AIS'09), Молодежная научно-техническая конференция «Интеллектуальные системы - 2009»), Дивноморское, 2009.

5.Международной конференции «Информационные технологии в образовании, технике и медицине», Волгоград, 2009.

6.Международной научно-практической конференции «Инновационная экономика и промышленная политика региона (ЭКОПРОМ-2009)», Санкт-Петербург, 2009.

7.УП-0Й Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление», Таганрог, 2009.

8.Всероссийской конференции с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации», Ульяновск, 2009.

9.17-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2010», Москва, 2010.

10.Всероссийской научно-технической конференции аспирантов, студентов и молодых учёных «Информатика и вычислительная техника», Ульяновск, 2010.

11 .Российской школе-семинаре аспирантов, студентов и молодых учёных «Информатика, моделирование, автоматизация проектирования», Ульяновск, 2010.

По результатам проведенных исследований опубликовано 14 печатных работ [35-37; 87-97], из них 3 - в журналах, включенных в список изданий, рекомендованных ВАК [35, 87, 88].

4.6. Выводы

1. Разработанная практическая система моделирования позволяет исследовать многомерные задачи на кластере ЭВМ с высокой временной эффективностью. Экспериментальная проверка основных результатов работы осуществлена на примере моделирования разработки неоднородного нефтесодержащего пласта произвольной формы.

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

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

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

ЗАКЛЮЧЕНИЕ

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

В ходе выполнения работы были получены следующие результаты:

1. Установлено, что наиболее перспективным классом параллельных вычислителей по критерию «производительность/цена» для создания высокопроизводительных комплексов структурного моделирования, ориентированных на обработку многомерных задач, являются кластеры ЭВМ. Так, два кластерных двухпроцессорных узла в среднем на 35% дешевле, чем один четырёхпроцессорный SMP-сервер, причём с ростом количества процессоров преимущества кластерных решений по этому показателю увеличиваются. Например, производительность мощного сервера в 2-3 раза превышает производительность среднего персонального компьютера, а стоит он дороже обычно в 5-10 раз. Перспективность кластерной структуры подтверждается резким ростом за последнее десятилетие кластеров в списке ТОР500. На июнь 2010 года их доля составляет 84,8%.

2. Показано, что при разработке кластеров ЭВМ, ориентированных на обработку многомерных задач, для повышения их производительности необходимо принимать специальные меры: оснащение универсальных ЭВМ специализированными акселераторами; выбор топологии, обеспечивающей одновременно несколько альтернативных путей между вычислителями кластера; обеспечение выполнения процессов обмена на фоне процессов счёта; выбор интерконнекта с малой латентностью и высокой пропускной способностью; оптимальное планирование процесса обработки с учетом процессов обмена.

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

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

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

6. Синтезирован алгоритм матрично-группового моделирования параллельного решения сложных по структуре задач, отличающийся от известных алгоритмов моделирования параллельных процессов совмещением одновременно процессов вычисления и обмена, что позволяет на основе результатов моделирования повысить производительность кластера путем выполнения операций обмена на фоне процессов вычислений. Особенностью данного алгоритма является использование фиктивных операторов для перехода от нерегулярного графа алгоритма задачи к регулярному алгоритму моделирования параллельного решения задачи. Это позволяет представить алгоритм последовательным выполнением одинаковых спецопераций с матрицами групп в порядке возрастания их номера на единицу. Алгоритм моделирования параллельной обработки сложных по структуре задач позволяет автоматизировать процесс статического планирования и составлять расписание параллельной обработки на операторном уровне, как одновременно по процессам счёта и обмена, так и отдельно. Информация для составления операторного расписания формируется в динамических матрицах групп. Расчёт только критического времени счёта, обмена, критического времени обработки задачи одновременно по процессам счёта и обмена, а также расчёт элементов динамических матриц групп может для сокращения времени планирования выполняться параллельно.

Сложность алгоритма, оцененная по наибольшему количеству операций при расчёте динамических матриц определяется выражением V ~ т2 -I, где I - общее число операторов задачи, am- среднее число операторов в одной группе. Работоспособность алгоритма подтверждена расчётами.

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

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

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

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

1. Азиз X., Сеттари Э. Математическое моделирование пластовых систем.1. М.: Недра, 1982.-407с.

2. Александров А.Г., Артемьев В.М. и др. Справочник по теорииавтоматического управления. /Под ред. А.А.Красовского. М.: Наука, 1987.-712с.

3. Андреев А.Н.; Воеводин Вл.В., Жуматий С.А. Кластеры и суперкомпьютеры- близнецы или братья? // Открытые системы. 2000. - №5-6. - с.9 - 14.

4. Арсенин В.Я. Методы математической физики и специальные функции. -2-е изд., перераб. и доп. М.: Наука, 1984. - 384с.

5. Арбиб М.А. Искусственный интеллект: вычисления на основе кооперации и симбиоз человека и вычислительной машины (перев. с англ.) М.: Знание (Сер. «Математика, кибернетика», №12), 1980. с.42 - 61.

6. Бусленко Н. П. Моделирование сложных систем. М.: Наука, 1978. - 400с.

7. Барский А. Б. Параллельные информационные технологии: Учебноепособие. М.: Интернет - Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. - 503с.

8. Балашов Е. П. и др. Микро- и мини- ЭВМ. Учебное пособие для вузов. Л.:

9. Энергоатомиздат. Ленинградское отделение, 1984. 376с.

10. Бобрыщев Д. Н., Нисевич Е. В. Сетевые методы в управлении. М.: Моск.1. Рабочий, 1973. 160с.

11. Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М.: Наука, 1983. - 464с.

12. Воролевский В.Р., Максимов М.М. Система обработки информации при разработке нефтяных месторождений.- М., Недра,- 1975.

13. Васильев В. И. Распознающие системы. Справочник. Издание второе, переработанное и дополненное. Киев, Наукова думка, 1983. 424с.

14. Василенко Г.И. Теория восстановления сигналов: О редукции к идеальному прибору в физике и технике. М.: Сов. Радио, 1979. - 272с.

15. Василенко Г. И., Тараторин А. М. Восстановление изображений. М.: Радио и связь, 1986. - 304с.

16. Вальков В. М. Микроэлектронные управляющие вычислительные комплексы: Системное проектирование и конструирование. 2е изд. Перераб. и доп. - Л.: Машиностроение, Ленингр. отд-ние, 1990. -224с.

17. Волков А.М. Решение практических задач геологии на ЭВМ. -М.: Недра, 1980. -224с.

18. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПБ.: БХВ -Петербург, 2004. 608с.

19. Гантмахер Ф. Р. Теория матриц. 4-е изд. -М.: Наука, 1988. - 552с.

20. Глушков В. М. Основы безбумажной информатики. М.: Наука, 1982. -552с.

21. Гузик В.Ф. Модульные интегрирующие вычислительные структуры. М.: Радио и связь, 1984. 216с.

22. Гузик В.Ф., Золотовский В. Е. Многопроцессорные вычислительные системы с матрично-потоковой организацией архитектуры. Труды ТРТУ, Таганрог, 1995.

23. ГузикВ.Ф., ЗолотовскийВ.Е. Проблемно-ориентированные вычислительные системы: Учебное пособие. Таганрог: Изд-во Технологического института ЮФУ, 2007. - 306с.

24. Гузик В.Ф. Проектирование проблемно-ориентированных вычислительных систем. Часть 1: Монография:-Таганрог : Изд-во ТТИЮФУ, 2009.-463с.

25. Демидович Б. П., Марон И. А., Шувалова Э. 3. Численные методы анализа. М.: Физматгиз, 1963. - 400с .

26. Дружинин В.В., Конторов Д. С. Системотехника. М.: Радио и связь, 1985.-200с.

27. Емельянов В.В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. -М.: Физматлит, 2003. 432с.

28. Ершов В.А., Кузнецов H.A. Мультисервисные телекоммуникационные сети.-М.: Изд-во МГТУ им. А.Э. Баумана, 2003. 432с.

29. Желтов Ю.П.Разработка нефтяных месторождений. М.: Недра, 1988, 333с.

30. Завьялов Ю. С. и др. Сплайны в инженерной геометрии. М.: Машиностроение, 1985. -224с.

31. ЗеловС. Кластерные технологии Электронный ресурс. Режим доступа: http://www.compress.ru/article.aspx?id=9958&iid=416

32. Золотовский В.Е. Проблемно-ориентированные системы структурного моделирования,- Таганрог: Изд-во ТРТУ, 2006. 178с.

33. Золотовский В. Е. Разработка теории и методов структурной организации функционально-ориентированных многопроцессорных систем с программируемой архитектурой. Диссертация на соискание учёной степени доктора технических наук. Таганрог, 1986. 399с.

34. Золотовский В.Е., Цветкова Ю.А. К вопросу о моделировании параллельной обработки задач в вычислительных системах. //Известия высших учебных заведений. Северо-кавказский регион. Технические науки. 2008, №3(145).- с.5-10.

35. Каляев A.B. Многопроцессорные системы с программируемой архитектурой. М.: Радио и связь, 1984. 240с.

36. Каляев И.А., Лохин В.М., Макаров И.М. и др. /под общей ред. Юревича Е.И./. Интеллектуальные роботы: учебное пособие для вузов,- М.: Машиностроение, 2007. 360с.

37. Корнеев В.В. Параллельные вычислительные системы. М.: «Нолидж», 1999.-320с.

38. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). Перевод со 2-го переработанного американского издания. -М.: Наука, 1974. 832с.

39. Кузьминский М.Б., Волков Д. Современные суперкомпьютеры: состояния и перспективы // открытые системы,- 2004.-№9.

40. Крянев Д. Эффективность разработки нефтяных месторождений. Электронный ресурс. : [статья] / Крянев Д. 2010. - Режим доступа: http ://www. energyland. info/new/news/ neftgaz/neftegaz/52660

41. Кричлоу Г.Б. Современная разработка .нефтяных месторождений -проблемы моделирования-М.: Недра, 1979.

42. Левайн Р.Д. Суперкомпьютеры. // Современный компьютер: Пер. с англ. под ред. В. М. Курочкина. М.: Мир, 1986. - с. 9 - 31.

43. Шеннон Р. Имитационное моделирование систем искусство и наука. -М.: Мир, 1978. -418с.

44. ТОР500 Supercomputing Sites. Электронный ресурс. Режим доступа: http://www.top500.org

45. ТЮВЕ Programming Community Index for March 2011. Электронный ресурс. Режим доступа: http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html