С момента появления современных вычислительных средств происходит постоянный процесс их совершенствования. При этом одна из мировых тенденций в развитии вычислительного дела неразрывно связана с созданием высокопроизводительных вычислительных систем на базе фундаментальных принципов распараллеливания и конвейеризации, а также с интеграцией обработки потоков быстро поступающей информации на многопроцессорных системах, комплексах и сетях ЭВМ [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 работанных приемов ускорения вычислений дает выигрыш по времени программных реализаций алгоритмов с квадратичной оценкой трудоемкости по отношению к программным реализациям алгоритмов с линейной трудоемкостьюдля всех разработанных программных реализаций алгоритмов по решению логико-комбинаторных задач получены математические оценки их производительности и трудоемкости в тактах в зависимости от длины обрабатываемых массивов.
