Математические модели и методы оптимальной организации параллельных конкурирующих процессов и их реализация тема диссертации и автореферата по ВАК РФ 05.13.11, доктор физико-математических наук Коваленко, Николай Семенович

• Коваленко, Николай Семенович
• доктор физико-математических наук
• 1998

Оглавление диссертации доктор физико-математических наук Коваленко, Николай Семенович

Введение

Общая характеристика работы

Глава 1. Метод структурирования программных ресурсов

1.1. Концепция структурирования в параллельном программировании

1.2. Основные положения метода структурирования.

1.3. Языковые и программные средства поддержки структурирования

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

1.5. Дискретно-динамические системы и метод структурирования программных ресурсов.

Глава 2. Математическая модель сосредоточенной обработки конкурирующих процессов

2.1. Сосредоточенные конкурирующие процессы и режимы их взаимодействия.

2.2. Минимальное общее время выполнения неоднородных конкурирующих процессов в асинхронном режиме.

2.3. Синхронный режим с непрерывным выполнением процессов

2.4. Синхронный режим с непрерывным выполнением блоков

2.5. Однородные конкурирующие процессы.

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

Глава 3. Задачи оптимальной организации конкурирующих процессов при сосредоточенной обработке

3.1. Эффективность и оптимальность организации конкурирующих процессов при достаточном числе процессоров

3.2. Критерии эффективности и оптимальности структурирования программных ресурсов при ограниченном числе процессоров.

3.3. Оптимизация числа процессоров при выполнении конкурирующих процессов

3.4. Конкурирующие процессы при ограниченном числе копий структурированного программного ресурса

3.4.1. Неделимые копии программного ресурса.

3.4.2. Ограниченное число копий структурированного программного ресурса.

3.4.3. Эффективность и оптимальность структурирования программных ресурсов при ограниченном числе копий.

3.4.4. Коэффициенты ускорения и эффективности вычислений при ограниченном числе копий программного ресурса.

Глава 4. Распределенная обработка конкурирующих процессов

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

4.2. Неоднородные распределенные конкурирующие процессы в асинхронном режиме

4.3. Неоднородные распределенные конкурирующие процессы в синхронном режиме с непрерывным выполнением блоков

4.4. Неоднородные распределенные конкурирующие процессы в синхронном режиме с непрерывным переходом по процессам

4.5. Распределенная и сосредоточенная обработка конкурирующих процессов.

4.6. Задачи оптимизации числа блоков программного ресурса и процессоров при распределенной обработке

Глава 5. Конкурирующие процессы при макроконвейерной обработке

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

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

5.2.1. Время реализации асинхронных процессов при макроконвейерной организации вычислений.

5.3. Условия балансировки числа процессоров и каналов для класса асинхронных процессов.

5.4. Оптимизационные задачи организации макроконвейер-ных вычислений

5.4.1. Минимизация времени суммарных простоев процессоров и "пролеживаний" блоков обмена.

5.4.2. Оценка коэффициента эффективности макрокон-вейерных вычислений.

5.4.3. Стационарные процессы и минимизация числа каналов обмена.

5.4.4. Минимизация общего времени выполнения процессов и числа блоков.

Глава 6. Векторно-конвейерная обработка: проблемы и методы эффективного отображения алгоритмов логико-комбинаторных задач 131 6.1. Особенности векторно-конвейерной обработки.

6.1.1. Особенности системы программирования на базе языка Ассемблер.

6.1.2. Системы программирования на базе языков ПЛ/ и Фортран

-6.1.3. Имитационные комплексы КОМИКС, МИКСТ и особенности работы с ними.

6.1.4. Качество прикладного программного обеспечения для векторно-конвейерных ЭВМ и способы его оценки.

6.1.5. Параллельные алгоритмы

6.2. Приемы ускорения вычислений при векторно-конвейерной

6.2.2. Минимизация времени выполнения программных реализаций за счет приемов ускорения вычислений

6.2.3. Эффективность приемов ускорения вычислений

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

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

6.4. Ускорение вычислений циклических конструкций (разворот циклов).

6.4.1. Операция разворота цикла.

6.4.2. Показатели эффективности разворота цикла

6.4.3. Ускорение вычислений при тиражировании

6.4.4. Ускорение вычислений при оптимизации.

6.4.5. Оптимизация периодических циклов

6.5. Классификация приемов ускорения вычислений по числу операций

Глава 7. Пакет программ решения задач оптимального распределения ресурсов на сетевых графах и библиотеки базовых стандартных логико-комбинаторных подпрограмм для векторно-конвейерной ЭВМ

7.1. Особенности, структура и основные математические за

7.1.1. Блочно-модульная структура пакета программ

7.1.2. Структура входных и выходных данных пакета

7.1.3. Основные математические задачи в пакете программ 174 7.2. Особенности разработки библиотек базовых стандартных программных модулей для решения логико-комбинаторных задач

7.2.1. Библиотека программ поиска

7.2.2. Библиотека программ сортировки. обработке

6.2.1. Основные понятия и определения дачи в пакете программ

7.2.3. Библиотека программ базовых операций алгебры логики и теории множеств.

7.2.4. Библиотека базовых операций с (ОД)-матрицами

7.3. Векторизованные алгоритмы анализа топологии графов и их программная реализация.

7.3.1. Связность графов.

7.3.2. Задачи о циклах и контурах на графах.

7.3.3. Нахождение фундаментального множества циклов графа

7.3.4. Точки сочленения и мосты графа.

7.4. Векторизованные алгоритмы нахождения расстояний в графах и их программная реализация.

7.4.1. Нахождение расстояний от источника до всех вершин в бесконтурном графе.21,

7.4.2. Нахождение расстояний от источника до всех вершин в графе, не содержащем контуров отрицательной длины

7.4.3. Нахождение расстояний от источника до всех вершин в графе с неотрицательными весами

7.4.4. Построение матрицы расстояний между всеми парами вершин в графе.

7.4.5. Эффективность программных реализаций векторизованных алгоритмов по решению задач на графах

Введение диссертации (часть автореферата) на тему «Математические модели и методы оптимальной организации параллельных конкурирующих процессов и их реализация»

С момента появления современных вычислительных средств происходит постоянный процесс их совершенствования. При этом одна из мировых тенденций в развитии вычислительного дела неразрывно связана с созданием высокопроизводительных вычислительных систем на базе фундаментальных принципов распараллеливания и конвейеризации, а также с интеграцией обработки потоков быстро поступающей информации на многопроцессорных системах, комплексах и сетях ЭВМ [13, 20, 61, 81, 83, 102,111,114, 123,124]. Это обусловлено как необходимостью достижения сверхвысокой производительности и надежности вычислительных средств, так и существенного ускорения решения реальных задач, повышения их размерности и точности результатов. В связи с этим происходит процесс создания принципиально новых и пересмотра существующих математических методов и алгоритмов решения задач в различных предметных областях с пересмотром алгоритмического багажа прикладной математики, выдвигаются новые требования к построению и исследованию математических моделей, касающихся различных аспектов параллельной и конвейерной обработки, организации параллельных вычислений [7, 14, 17, 38, 58, 60, 116, 121, 126]. Кроме того, принципы параллельной организации процессов являются не только одним из универсальных способов достижения высокой производительности и надежности вычислительных средств, но и носят достаточно общий характер и присущи процессам различной природы, прежде всего они свойственны системам управления, операционным системам, системам автоматизированного проектирования, промышленным технологиям, конвейерным и роторно-конвейерным линиям и т.д.

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

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

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

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

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

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

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

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

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

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

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

В седьмой главе разработана структура и состав математических задач, включая структуры входных и выходных данных, пакета программ по решению задач оптимального распределения ресурсов на сетях большой размерности для векторно-конвейерных ЭВМ; разработаны библиотеки базовых стандартных программных модулей для решения логико-комбинаторных задач на векторно-конвейерной ЭВМ "Электроника ССБИС" по разделам: поиск, числовое и лексикографическое упорядочение, базовые операции алгебры логики и теории множеств, операции с (0,1)-матрицами, задачи анализа топологии сетевых графов и расчетные задачи на сетевых графах, операции представления и преобразования графовых структур данных и др.; разработаны векторно-конвейерные алгоритмы и соответствующие программные реализации по решению логико-комбинаторных задач с показателями векторной и супервекторной производительности при их отображении на векторно-конвейерную ЭВМ "Электроника ССБИС", для всех программных реализаций разработанных алгоритмов получены математические оценки их трудоемкости в тактах векторно-конвейерной ЭВМ в зависимости от длины обрабатываемых массивов.

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

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

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

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

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

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

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

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

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

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

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

• разработка, математическое обоснование и реализация метода организации параллельных конкурирующих процессов, базирующегося на структурировании программных ресурсов на параллельно-выполняемые блоки;

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

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

• решение оптимизационных задач по расчету характеристик многопроцессорных систем и комплексов при реализации заданных объемов вычислений в условиях сосредоточенной и распределенной обработки данных; исследование и сравнительный анализ базовых синхронных и асинхронного режимов взаимодействия конкурирующих процессов, а также сосредоточенной и распределенной обработки по времени выполнения заданных объемов вычислений; построение математической модели и исследование эффективности макроконвейерного способа организации вычислений при ограниченном числе каналов обмена, решение задач оптимальной балансировки числа процессоров и каналов, минимизации непроизводительных простоев процессоров, нахождения оптимального числа блоков обмена и счета; разработка показателей и критериев для оценки эффективности и классификации приемов ускорения вычислений при векторно-конвейерной обработке; математическое обоснование эффективности различных классов приемов ускорения вычислений при векторно-конвейерной обработке, в том числе базирующихся на избыточности операций и данных, а также операции разворота циклов; разработка структуры пакета программ по решению задач оптимального распределения ресурсов на сетях большой размерности для векторно-конвейерных ЭВМ; разработка базовых библиотек стандартных программных модулей для решения логико-комбинаторных задач на векторно-конвейерной ЭВМ "Электроника ССБИС" по разделам: поиск, числовое и лексикографическое упорядочение, базовые операции алгебры логики и теории множеств, операции с1 (0,1)-матрицами, задачи анализа топологии сетевых графов и расчетные задачи на сетевых графах, операции представления и преобразования графовых структур данных и др. разработка векторно-конвейерных алгоритмов и их программных реализаций по решению логико-комбинаторных задач с показателями векторной и супервекторной производительности при их отображении на векторно-конвейерную ЭВМ "Электроника ССБИС".

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

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

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

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

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

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

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

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

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

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

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

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

- разработаны библиотеки базовых стандартных программных модулей для решения логико-комбинаторных задач на векторно-конвеиер-ной ЭВМ "Электроника ССБИС" по разделам: поиск, числовое и лексикографическое упорядочение, базовые операции алгебры логики и теории множеств, операции с (ОД)-матрицами, задачи анализа топологии сетевых графов и расчетные задачи на сетевых графах, операции представления и преобразования графовых структур данных и др.;

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

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

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

Полученные в диссертации результаты реализованы в ряде реальных программных систем. Это прежде всего механизм управления параллельными процессами в универсальной операционной системе семейства мультипрограммных ЭВМ серии "Минск-32"; система коллективного пользования "Уголь" на базе многомашинного комплекса ЕС ЭВМ и "Минск-32" для Министерства угольной промышленности СССР; ряд проблемно-ориентированных пакетов программ специального назначения на базе ЕС ЭВМ. Все основные положения и идеи метода структурирования апробированы также при создании реальных многопроцессорных систем и комплексов макроконвейерного и векторно-конвейерного типов по линии Минрадиопрома СССР совместно с Институтом кибернетики имени В.М. Глушкова НАН Украины и Мин-электронпрома СССР совместно с НИИ "Дельта" и Институтом проблем кибернетики Российской академии наук. Отдельные параллельные алгоритмы, разработанные с использованием идей метода структурирования, защищены авторскими свидетельствами на изобретения и реализованы на Минском производственном объединении вычислительной техники в устройствах диагностики высокопроизводительной ЭВМ ЕС 1061.

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

Диссертационная работа выполнена в рамках НИР по разработке теоретических основ организации параллельных вычислений и созданию программного обеспечения высокопроизводительных систем (1980 1998 гг.). Среди них госбюджетные темы "Разработка теоретических основ организации параллельных вычислений и создание программного обеспечения сверхбыстрых ЭВМ" (1986 - 1988 гг., Постановление Президиума АН БССР N° 39 от 3 апреля 1986 г. и № 139 от 24 декабря 1987 г., Договор о научно-техническом сотрудничестве с МПО ВТ на 1986 - 1988 гг., Программа научно-технического сотрудничества АН БССР с МРП СССР (п.11), Договор о научно-техническом сотрудничестве с ИПК АН СССР и МПО "Дельтой" МЭП СССР), "Разработка теоретических основ организации параллельных вычислений и создание программного обеспечения для супер-ЭВМ векторно-конвейерного типа" (1989 - 1991 гг., Постановление Президиума АН БССР № 115 от 6 декабря 1988 г., Договор о научно-техническом сотрудничестве с ИПК АН СССР и МПО "Дельтон" МЭП СССР), "Разработка теоретических основ организации параллельных вычислений и создание программного обеспечения для вычислительных систем с распределенной обработкой данных" (1991 - 1994 гг., Постановление Президиума АН Беларуси № 116 от 5 декабря 1990 г., Договор о научно-техническом сотрудничестве с ИПК АН СССР и МПО "Дельтон" МЭП СССР, Договор о научно-техническом сотрудничестве с ИК им. В. М. Глушко-ва АН УССР), "Методы моделирования процессов переноса в полупроводниковых структурах и отображение вычислительных алгоритмов на систолические спецпроцессоры" (1993 - 1995 г., Постановление Президиума АН Беларуси № 3 от 21 января 1993 г.), "Разработка и исследование математических моделей, методов и алгоритмов для реализации в системах с высокой степенью параллелизма" (государственная программа фундаментальных исследований Республики Беларусь на 1996 -2000 гг. "Методы и алгоритмы вычислительной и дискретной математики: разработка, анализ, оптимизация и отображение на архитектуру вычислительных систем"), а также на основании договоров с Фондом фундаментальных исследований Республики Беларусь № Ф94-205 от 30 января 1995 г. по теме "Методы построения максимальных параллельных форм информационно связанных алгоритмов" и № Ф96-181 от 17 февраля 1997 г. по теме "Методы построения оптимальных параллельных алгоритмов для реализации на матричных процессорах с локальными соединениями и организации распределенных вычислений".

Апробация результатов диссертации. Результаты, вошедшие в диссертационную работу, докладывались на Всесоюзных школах-семинарах и конференциях "Параллельное программирование и высокопроизводительные системы" (Новосибирск, 1980 г., Алушта, 1982 и 1988 гг., Киев, 1984 г., Бердянск, 1986 г., Уфа, 1990 г.), Всесоюзной школе-семинаре "Многопроцессорные вычислительные системы с общим управлением" (г. Звенигород. 1981 г.), Всесоюзной конференции "Системное и теоретическое программирование" (Кишинев, 1983 г.), I Всесоюзной конференции "Проблемы создания супер-ЭВМ, суперсистем и их применение" (Минск, 1987 г.), 7 Международной конференции "Применение ЭВМ в технике и управлении производством (COMPCONTROL'87)" (Москва, 1987 г.), Международных конференциях "Технологии параллельных вычислений" (РаСТ'91) (Новосибирск, 1991 г.) и (РаСТ'93) (Обнинск, 1993 г.), Международной конференции "Методы конструирования программ" (Планерское, Крым, 1992 г.), I Международной конференции "Parallel Processing and Applied Mathematics" ( Честохова, Польша, 1994 г.), Республиканской научно-методической конференции, посвященной 25-летию факультета прикладной математики и информатики Белгосуниверситета (Минск, 1995 г.), Международной конференции "Advanced mathematics, Computations and Applications" (Новосибирск, 1995 г.), Международной конференции "Автоматизация проектирования дискретных систем" (Минск, 1995), I Международной научно-практической конференции по программированию "UkrPROG'98" (Киев, 1998 г.), а также на научных семинарах в Институте математики НАН Беларуси, Институте кибернетики им. В. М. Глушкова НАН Украины, Институте проблем кибернетики РАН, Институте системного программирования РАН.

Публикации. Основные результаты диссертации опубликованы в 50 работах. Из них 41 — основные, которые включают 19 статей в научных журналах АН СССР, РАН, НАН Украины и НАН Беларуси; 10 работ в трудах Международных и Всесоюзных конференций по па; раллельным вычислениям; 6 работ в периодических сборниках статей АН СССР, РАН и АН УССР; 2 отчета по темам НИР; 3 препринта Института математики НАН Беларуси; 1 авторское свидетельство на изобретение. Из 41 основных 9 работ опубликовано без соавторов.

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

Структура и объём диссертации. Диссертация состоит из введения, общей характеристики работы, семи глав, заключения и списка использованных источников из 176 наименований и содержит 221 страницу основного текста, включая 39 рисунков и 5 таблиц. Общий объем работы — 240 страниц.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Коваленко, Николай Семенович

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Разработана структура и состав математических задач, включая структуры входных и выходных данных, пакета программ по решению задач оптимального распределения ресурсов на сетях большой размерности для векторно-конвейерных ЭВМ; разработаны библиотеки базовых стандартных программных модулей для решения логико-комбинаторных задач на векторно-конвейерной ЭВМ "Электроника ССБИС" по разделам: поиск, числовое и лексикографическое упорядочение, базовые операции алгебры логики и теории множеств, операции с (ОД)-матрицами, задачи анализа топологии сетевых графов и расчетные задачи на сетевых графах, операции представления и преобразования графовых структур данных и др.

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

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

Список литературы диссертационного исследования доктор физико-математических наук Коваленко, Николай Семенович, 1998 год

1. Алгоритмический язык МАЯК / С. С. Гороховский, Ю. В. Капитонова, А. А. Летичевский и др. // Кибернетика. — 1984. — № 3. — С. 54 74.

2. Андон Ф. И., Лаврищева Е. М. Методы инженерии разработки распределенных компьютерных приложений. — Киев: Наук, думка, 1997. — 228 с.

3. Анишев П. А. Матричный алгоритм поиска контуров в ориентированном графе // Вычислительные системы. — Новосибирск, 1987. — № 119. — С. 62 70.

4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. — 536 с.

5. Ахьюджа X. Н. Сетевые методы управления в проектировании и производстве. — М.: Мир, 1979. — 638 с.

6. Бабаян Б. А., Сахин Ю. X. Система "Эльбрус" // Программирование. — 1980. — № 6. — С. 72 86.

7. Барский А. Б. Параллельные процессы в вычислительных системах. Планирование и организация. — М.: Радио и связь, 1990. — 256 с.

8. Бурдюк В. Я. О выборе последовательности загрузки станков // Экономика и математические методы. — 1970. — № 1. — С. 112 -116.

9. Вабищевич А. М. Методы поиска в графах и их отображение на архитектуру векторно-конвейерной ЭВМ // Вопросы кибернетики. Средства моделирования и разработка прикладных программ для супер-ЭВМ. — М., 1992. — С. 99 104.

10. Вальковский В. А. Распараллеливание алгоритмов и программ: Структурный подход. — М.: Радио и связь, 1989. — 175 с.

11. Векторизация программ: теория, методы, реализация // Сборник статей под ред. Г. Д. Чинина. — М.: Мир, 1991. — 275 с.

12. Воеводин А. В. Структура пакета программ для решения задач линейной алгебры на векторно-конвейерной ЭВМ и проблемы развития программного обеспечения // Вопросы кибернетики. Эффективное использование высокопроизводительных ЭВМ. — М., 1985. — С. 44 65.13