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

• Новиков, Алексей Владимирович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Новиков, Алексей Владимирович

ВВЕДЕНИЕ.

1. АНАЛИЗ МЕТОДОВ МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ МНОГОПРОЦЕССОРНЫХ СИСТЕМ.

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

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

1.3. Анализ и синтез параллельного программного обеспечения. Преимущества графового метода и метода «ветвей и границ».

1.4. Выводы.

2. МОДЕЛЬ ПАРАЛЛЕЛЬНОГО ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА.

2.1. Представление вычислительного алгоритма в виде решетчатого орграфа.

2.2. Модель параллельного вычислительного процесса.

2.3. Определение временных характеристик исследуемого алгоритма

2.4. Формализация оптимизационных критериев.

2.5. Выводы.

3. МЕТОДИКА ОПТИМАЛЬНОГО РАСПАРАЛЛЕЛИВАНИЯ АЛГОРИТМА ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ.

3.1. Сегментация алгоритма.

3.2. Распараллеливание алгоритма на основе системы ордеров.

3.3. Распараллеливание линейных алгоритмов на основе целочисленного линейного программирования.

-33.4. Получение исходных данных о структуре и основных параметрах алгоритма.

3.5. Исследование точности получаемых результатов.

3.6. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МЕТОДИК АНАЛИЗА И СИНТЕЗА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ МНОГОПРОЦЕССОРНОЙ СИСТЕМЫ.

4.1. Программный комплекс для автоматического распараллеливания алгоритмов.

4.2. Пример синтеза программного обеспечения спецвычислителя

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

4.4. Исследование времени поиска оптимального решения.

4.5. Исследование эффективности распараллеливания при использовании разработанного подхода.

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

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

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

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

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

Эффективность параллельной обработки существенно зависит от правильности распараллеливания операций между исполнительными устройствами [7, 10, 11, 41]. Основное противоречие, которое должно быть преодолено в процессе решения задачи распараллеливания, заключается в том, что, с одной стороны, к разрабатываемой вычислительной системе предъявляются требования повышенного быстродействия, с другой - ставятся жесткие ограничения на объем используемых аппаратных ресурсов. Разрешение данного противоречия представляет собой сложную оптимизационную задачу большой размерности [7,10,31].

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

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

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

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

1. Формализация модели параллельных вычислений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация и внедрение результатов работы. Прикладные результаты диссертационной работы были внедрены: 1) ООО «Научно-производственная фирма ОВЕН-К», г. Москва. 2) компания «Трейд-М», г. Тула.

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

Апробация работы. Основные положения диссертационной работы легли в основу докладов на следующих конференциях: 1. Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2002, 2003, 2004, 2005, 2006 гг.) 2. Межрегиональная научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, Тул-ГУ, 2003, 2004, 2005). 3. 7-я всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, РГРТА, 2002). 4. 1-я Всероссийская научно-техническая конференция студентов и аспирантов «Идеи молодых - новой России» (Тула, ТулГУ, 2004). 5. IV Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск, ТПУ, 2006). 6. Международная научно-методическая конференция «Информатизация образования - 2006» (Тула, 2006). 7. Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации» (Новосибирск, НГТУ, 2006). 8. IV Международная научно-техническая конференция «Искусственный интеллект в XXI веке. Решения в условиях неопределенности» (Пенза, 2006). 9. I молодежная научно-практическая конференция Тульского государственного университета «Молодежные инновации» (Тула, ТулГУ, 2006).

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

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 142 страницах маши

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

3.6. Выводы

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

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

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

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

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

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МЕТОДИК АНАЛИЗА И СИНТЕЗА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ МНОГОПРОЦЕССОРНОЙ СИСТЕМЫ

4.1. Программный комплекс для автоматического распараллеливания алгоритмов

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

Разработанный программный комплекс позволяет:

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

- осуществлять определение временных параметров алгоритма на экспериментальном стенде;

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

Модуль визуального синтеза структуры алгоритма (рис. 4.1) позво ляет производить построение в визуальном режиме информационной структуры алгоритма в виде ориентированного графа, вершинами которого являются операторы (команды, подпрограммы), дуги - информационные связи между операторами (информационные дуги).

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

Файл Обработка

Прием данных

Идвкп*и*0х12

I данных

Рис. 4.1. Модуль визуального синтеза структуры алгоритма (главное окно и окно инспектора объектов)

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

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

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

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

Ограничена на время Число процессоров ииш

Канал обмена Вр 1°" | Время передав 1 пакета

И ' Г Период 110000

Построить программу

- л.

Процессор 0 } Проце

Этап 1 Б04

Этап 2.Б02 Этап 2. БОЗ Этап 2. Б04 Этап 3, БОЗ Этап 3, Б04 Конец ООСООСЮ120112010020Ш2112222220322 = 1

Прием данных Этап 2, Б01 Этап1,Б02 Этап 2.Б02 Этап 1. Б01 Этап 1. БОЗ Этап 2, БОЗ Этап 2.Б04 Ятлп 1 РП4

1531 Время. мс:5551 »

Рис. 4.2. Окно модуля синтеза параллельной программы

Модуль измерительного монитора .(рис. 4.3) предназначен для испытания алгоритма функционирования системы на экспериментальном стенде. Связь с экспериментальным стендом осуществляется через ЬРТ-порт компьютера.

Программа сбора данных

Запуск

Стоп j

Число тактов ;1185000 Число записей 10 Сохранить

Отладка.

Импульс

Переключать О

Рис. 4.3. Главное окно модуля измерительного монитора

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

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

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

Для создания классов, реализующих указанные типы, используется механизм шаблонов, предоставляемый языком С++. Шаблон класса CDataObject<T> используется для замены типа Т переменных, хранящих обрабатываемые данные. Шаблон класса CIndexObject<T> используется для замены типа Т переменных, хранящих переменные цикла.

Для упрощения внесения построенных типов в текст программы, задаются следующие символические имена: typedef CDataObject<int> Datalnt; typedef CIndexObject<int> Indexint; Кроме того в данном модуле содержится описание класса CAnalizer. Данный класс используется для создания объекта Analizer, который осуществляет сбор статистики о чтении/записи данных в ячейки памяти и строит информационный граф.

В качестве примера рассмотрим вычисление одномерной свертки. Математически она выражается следующим образом y[i] = Nth[j]x[i-j],i = 0.N + M-2.

J=О

Программное представление на языке Си одного из возможных алгоритмов ее вычисления для случая N=M=3, реализованного на основе цикла с параметром, имеет следующий вид: double х[3], h[3], у[3] ; int i, j; for(i = 0; i<3; i++) for(j=0; j<3; j++) y[i+j] = у[i+j] + x[i]h[j]; Для построения информационного графа данного алгоритма, необходимо преобразовать программу к следующему виду: создать экземпляр объекта анализатора CAnalizer * Analizer = new CAnalizer; // объявить переменные-данные CDataDouble х[3], h[3], у[3]; // объявить переменные цикла CIndexInt i, j; // выполнить алгоритм for(i = 0; i<3; i++) for(j=0; j<3; j++) y[i+j] = у[i+j] + x[i]h[j]; удалить объект-анализатор delete Analizer;

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

Для преобразования полученных данных о структуре алгоритма к требуемому формату используется метод WriteDataGraph() объекта Analizer. Данный метод вызывается в деструкторе класса CAnalizer реализует вывод в файл данных, которые формируются в результате работы программы. В результате будет получен текстовый файл со следующим содержимым: <gxl> graph id="graphl"> node id="nodel" vars= 4=0;j =0"/> node id="node2" vars= 4=0; j =l"/> node id="node3" vars= 'i=0;j =2"/> node id="node4" vars= 'i=l;j =0M/> cnode id="node5" vars= 4=1; j =l"/> node id="node6" vars= 4=1; j =2"/> cnode id="node7" vars= 4=2; j =0"/> cnode id="node8" vars= 4=2; j =l"/> cnode id="node9" vars= 4=2; j =2"/>

Cedge from="node4 " to= 'node8 " id=" edgel cedge from="nodel " to= 'node5 " id=" edge2 cedge from="node5 " to= 'node9 " id=" edge3 cedge from="node2 " to= 'node6 " id=" edge4 graph> </gxl>

В данном файле элементы «node» обозначают вершины информационного графа, а элементы «edge» - его дуги. Полученный файл информационного графа экспортируется модулем синтеза визуальной структуры алгоритма, чем обеспечивается автоматизация задания" данной структуры.

4.2. Пример синтеза программного обеспечения спецвычислителя

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

Формат входных данных - 16 битное'целое. Входные данные представляют собой равномерно распределенную случайную величину.

Схема выполнения 8-точечного БПФ с прореживанием по частоте [28] представлена на рис. 4.4. т *0) *(2) *(3)

5) *(7)

J V.

J К J

ДО) Д4) Д2) т

Д1) Д5) ДЗ) Х{1)

Этап 1

Этап 2

Этап 3

Рис. 4.4. Схема выполнения 8-точечного БПФ с прореживанием по частоте

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

Данный алгоритм может быть записан в виде программы на языке Си следующим образом: объявление констант const int k[3][4]={{0,1,2,3},{0,1,4,5},{0,2,4,6}}; const int m[3] [4] = { {4,5,6,7}, {2',3,6,7}, {1,3,5,7}}; const int 1[3] [4] = {{0,1,2,3}, {0,2,0,2}, {0,0,0,0}}; объявление массивов и переменных int datare[8], dataim[8], i, j;

GetlnputData(); // Получить массив входных данных for(i=0; i<3; i++) for(j=0; j<4; j++)

BaseOper(k[i][j],m[i][j],1[i][j]); // базовая операция if(windowenabled) // Если включен режим обработки окном

WindowO; // выполнить оконное преобразование

WriteOutputData() ; // Выдать рассчитанные данные В данном фрагменте программы функция BaseOper(k, m, 1) осуществляет выполнения базовой операции БПФ над элементами к и ш массивов входных данных data re и dataim. Функция Window выполняет оконное преобразование выходного спектра и запускается при выставленном значении флага windowenabled.

Требуемый алгоритм будет включать 15 вычислительных операторов.

ЗАКЛЮЧЕИИЕ

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

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

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

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

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

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

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

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

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

10. Прикладные результаты работы внедрены в ООО «Научно-производственная фирма ОВЕН-К» (г. Москва), компании «Трейд-М» (г. Тула). Теоретические результаты работы внедрены в учебном курсе «Проектирование процессоров для цифровой обработки сигналов», а также в дипломном проектировании бакалавров и инженеров по специальности «Вычислительные машины, комплексы, системы и сети».

Список литературы диссертационного исследования кандидат технических наук Новиков, Алексей Владимирович, 2007 год

1. Алексеев О.Г., Комплексное применение методов дискретной оптимизации.-М.: Наука, 1987.-316 с.

2. Анализ производительности ЭВМ: Учеб. пособие / В.М. Игнатьев, Е.В. Ларкин; Тул. гос. техн. ун-т. Тула, 1994. 104 с.

3. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980. - 192 е., ил.

4. Берж X. Теория графов и ее применения. М.: Изд-во иностр. лит., 1962.-319 с.

5. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.:Мир, 1989. - 448 с.

6. Брахман Т.Р. Многокритериалность и выбор альтернативы в технике. М.: Радио и связь, 1984. - 288 с.

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

8. Вентцель Е.С. Исследование операций: задачи, принципы, методология. 2-е изд., стер. - М.: Наука. Гл. ред. физ.-мат. лит., 1988. - 208 с. -(Пробл. науки и техн. прогресса).

9. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. М.: Наука. Гл. ред. физ.-мат. лит. - 1988. -480 с.

10. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука. Гл. ред. физ.-мат. лит., 1986. - 296 с.

11. Воеводин В.В.,Воеводин Вл.В. "Параллельные вычисления", Спб, изд-во "БХВ-Петербург", 2002, 608 стр.

12. Глушков В.М, Капитонова Ю.В., Летичевский A.A. Автоматическое проектирование вычислительных машин. Киев., 1978. -230 с.

13. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980.-519 с.

14. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М. Радио и связь, 1983. - 272 с.

15. Горбунов B.J1., Панфилов Д.И., Преснухин Д.Л. Справочное пособие по микропроцессорам и микро-ЭВМ:/Под. Ред. Л.Н. Преснухина. М.: Высш. шк., 1988.-272 е.: ил.

16. Данилкин Ф.А., Новиков A.B. Построение информационного графа циклического алгоритма//Интеллектуальные и информационные системы: Материалы межрегиональной научно-технической конференции / Тульский государственный университет. Тула, 2005. - стр. 31-33.

17. Джордейн Р. Справочник программиста персональных компьютеров типа IBM РС,ХТ и AT: Пер. с англ. М: Финансы и статистика, 1992. - 544 с.

18. Долинский М., Толкачев А., Коршунов И. Программный комплекс для разработки параллельных вычислительных систем//Компоненты и технологии, 2004, №5, с. 94-100.

19. Евреинов Э.В. Однородные универсальные вычислительные системы высокой производительности. Новосибирск, Наука, 1966. -306 с.

20. Евстигнеев В.А. Применение теории графов в программировании. -М.: Наука, 1985.-352 с.

21. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука. 1990. 384 с.

22. Ильин A.A., Титов B.C., Евсюков Е.В. Быстрые алгоритмы цифровой обработки сигналов: Учебное пособие. Тула: Тульский государственный университет, 2003. - 125 с.

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

24. Карцев М.А. Архитектура цифровых вычислительных машин. М.: Наука, 1978.-295 с.

25. Касьянов В.Н. Методы оптимизации программ. Новосибирск: НГУ. 1984. 92 с.

26. Коваленко H.H., Филиппова A.A. Теория вероятностей и математическая статистика: Учеб. пособие. 2-е изд., перераб. И доп. - М.: Высш. Школа, 1982.-256 е., ил.

27. Колемаев В.А., Калинина В.Н. Теория вероятностей и математическая статистика: Учебник/ Под ред. В.А. Колемаева. М.: ИНФРА-М, 2001. -302 с. - (Серия «Высшее образование»).

28. Корнеев В.В. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, 1985. - 167 с.

29. Корячко В.П. Микропроцессоры и микроЭВМ в радиоэлектронных средствах: Учеб. для вузов по спец. «Конструирование и технология радиоэлектронных средств». М.: Высш. шк., 1990. - 407 е., ил.

30. Кофман А. Введение в прикладную комбинаторику. М.: Наука. Гл. ред. физ.-мат. лит., 1975. -480 е., ил.

31. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Целочисленное программирование. Пер. с франц. Б.Т. Вавилова, Е.В. Бабичевой, Г.Г. Устинченко. М.: Мир, 1977.-432 с.

32. Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. М.: Мир, 1978.-.432 с.

33. Левкин Г.Н., Левкина В.Е. Введение в схемотехнику ПЭВМ PC/AT. М.: Изд-во МПИ, 1991. - 96 е.: ил.

34. Литвин В.Г., Ададышев В.П., Винниченко А.И. Анализ производительности мультипрограммных ЭВМ. М.: Финансы и статистика, 1984. -159 е., ил.

35. Лорин Г. Распределенные вычислительные системы. М.: Радио игсвязь, 1984. -296 с.

36. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1985.-323 с.

37. Марков А.А, Нагорный Н.М. Теория алгоритмов. М.: Наука, 1984. -432 с.

38. Микропроцессорный комплект К1810: структура, программирование, применение. Справочная книга/ Ю.М. Казаринов, В.Н. Номоконов, Г.С. Подклетнов, Ф.В. Филиппов/. М.: Высшая школа, 1990. - 269 с.

39. Мультипроцессорные вычислительные системы/ Под. Ред. Я. А. Хетагурова. М.: Энергия, 1971. - 320 с.

40. Мультипроцессорные системы и параллельные вычисления/ Под. Ред. Ф.Г. Энслоу. М.: Мир, 1976. - 384 с.

41. Новиков A.B. Группировка операций в задачах распараллеливания вычислительных алгоритмов// Наука. Технологии. Инновации. Материалы всероссийской научонй конференции молодых ученых в 7-ми частях. Новосибирск: Изд-во НГТУ, 2006. Часть 2. с. 86-88.

42. Новиков A.B. Метод «ветвей и границ» в задаче планирования параллельных вычислительных процессов//ХХХ1 "Гагаринские чтения": Тез. докл. Международной молодежной научной конференции М.: MATH., 2004. Т.4., стр. 22-23.

43. Новиков A.B. Моделирование вычислительных систем на основе графовой структуры алгоритмов//ХХУИ "Гагаринские чтения": Тез. докл. Международной молодежной научной конференции М.: MATH., 2002. Т.5. Стр. 54-55.

44. Новиков A.B. Оптимальное распределение задач между модулями многопроцессорной системы//ХХХ Тагаринские чтения": Тез. докл. Международной молодежной научной конференции М.: МАТИ., 2004. Т.5. Стр. 46-47.

45. Новиков A.B. Разработка базы окончаний для шашечной програм-мы//ХХ1Х "Гагаринские чтения": Тез. докл. Международной молодежной научной конференции М.: МАТИ., 2003. Т.5. Стр. 52.

46. Новикова Н.М. Основы оптимизации (курс лекций). Электронный ресурс. Электрон, дан. - М.: МГУ, 1998. Режим доступа: http://www.ccas.ru/depart/malashen/papper/oonovikl .pdf, свободный. Требования: Adobe Acrobat Reader 3.0 или выше. - Заглавие с экрана.

47. Однородные микроэлектронные ассоциативные процессоры / Под. Ред. И.В. Прангишвили. М. Советское радио, 1973. - 280 с.

48. Панюков A.B. Линейное программирование: Конспект лекций. -Челябинск: Издательство ЮУрГУ, 2001. 59 с.

49. Пашкеев С.Д. Основы мультипрограммирования для специализированных систем. М.: Советское радио, 1972,183 с.

50. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. М.: Высшая школа, 1989. -367 стр.

51. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Сов. Радио, 1972.-280 с.

52. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. М.: Энергоатомиздат, 1983.-312 с.

53. Раскин Л.Г. Анализ сложных систем и элементы теории оптимального управления. М.: «Сов. радио», 1976. 344 е., ил.

54. Розен B.B. Цель, оптимальность, решение. Математические модели принятия оптимальных решений. М.: Радио и связь, 1982. 168 стр.

55. Рыбников К.А. Введение в комбинаторный анализ. М.: Издательство Московского университета, 1972. -256 с.

56. Сигнаевский В.А., Коган Я.А. Методы оценки быстродействия вычислительных систем / Под ред. О.И. Авена. М.: Наука, 1991. - 256 с.

57. Скэнлон J1. Персональные ЭВМ IBM PC и ХТ. Программирование на языке ассемблера. М.: Радио и связь. 1989. - 336 с.

58. Страуструп Б. Язык программирования С++. СПб.: БХВ-Петербург, 2001 - 863с.

59. Фет Я.И. Параллельные процессоры для управляющих систем. М. Энергоиздат, 1981. - 158 с.

60. Теория систем и методы системного анализа в управлении и связи/В.Н. Волкова, В.А. Воронков, A.A. Денисов и др. М.: Радио и связь, 1983.-248 с.

61. Толковый словарь по вычислительным системам/Под ред. В. Иллин-гуорта и др.: Пер. с англ. А.К. Белоцкого и др.; Под ред. Е.К. Масловского. -М.: Машиностроение, 1991. 560 е.: ил.

62. Транспьютеры. Архитектура и программное обеспечение. Под ред. Г.Хорна. М. Радио и связь 1993г. 304 с.

63. Трахтенгерц ЭЛ. Программное обеспечение параллельных процессов. Москва: Наука. 1987.

64. Ушкар М.Н. Микропроцессорные устройства в радиоэлектронной аппаратуре/Под ред. Б.Ф. Высоцкого. М.: Радио и связь, 1988. - 128 е.: ил. -(Массовая б-ка инженера «Электроника»).

65. Фор А. Восприятие и распознавание образов. М: Машиностроение, 1989 г. - 272 е.: ил.

66. Фостер К. Ассоциативные параллельные процессоры. М.: Энерго-издат, 1981.-240 с.

67. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977.

68. Хоккни Р., Джессхоуп К. Параллельные ЭВМ. Архитектура программирование и алгоритмы М.: Радио и связь, 1986. - 340с.

69. Цифровая и вычислительная техника: Учебник для вузов/Э.В. Ев-реинов, Ю.Т. Бутыльский, И.А. Мамзелев и др.; Под. ред. Э.В. Евреинова. -М.: Радио и связь, 1991.-464 е.: ил.

70. Шеннон Р. Имитационное моделирование систем искусство и наука. / Пер. с англ. под ред. Е.К. Масловского. М.: «Мир», 1978. - 418 с.

71. Шпаковский Г.И. Организация параллельных ЭВМ и суперскалярных процессоров: Учеб. пособие. Мн.: Белгосуниверситет, 1996. - 296 е.: ил.

72. Шрайбер Т. Моделирование на ОРББ. М.: Машиностроение, 1990.

73. Электронные промышленные устройства: Учеб. для студ. Вузов спец. «Пром. электрон.»/В.И. Васильев, Ю.М. Гусев, В.Н. Миронов и др. -М.: Высш. Шк., 1988. 303 е.: ил.

74. Элементы параллельного программирования/В.А. Вальковский, В.Е. Котов, А.Г.Марчук, Н.Н. Миренков. М.: Радио и связь, 1986. - 392 с.

75. Эффективность методов организации вычислительного процесса в АСУ. М.: Статистика, 1975. 255 с.

76. Языки и параллельные ЭВМ. Москва: Наука. 1990. серия Алгоритмы и алгоритмические языки. 93 с.

77. LPSOLVE: Linear Programming Code. Electronic resource. Electronic data and progr. - [USA]: 1996. Access: http://www.cs.sunysb.edu/~algorith/implement/lpsolve/implement.shtml, free. -Title from screen.

78. Mplab IDE, simulator, editor. User's guide. USA: Microchip Technology Inc., 2001.-272 p.

79. Smith S.W. The Scientist and Engineer's Guide to Digital Signal Processing. San Diego: California Technical Publishing, 1999, - 650 p.