Исследование эффективности реализации численных методов на кластерах персональных ЭВМ

Вид материала

Исследование

Содержание ГЛАВА 1. Технология параллельного программирования 1.1 Классификация архитектур параллельных ЭВМ 1.2. Кластеры персональных ЭВМ 1.3. Интерфейс параллельного программирования ГЛАВА 2. Эффективность реализации численных методов 2.1 Метод формульного анализа масштабируемости (ФАМ) 2.1. Эффективность параллельных алгоритмов ГЛАВА 3. Решение задач линейного программирования 3.1. Постановка задачи линейного программирования 3.2. Двойственность задач линейного программирования 3.3. Постановка транспортной задачи 3.4. Общая схема программы 3.5. Генерирование исходных данных 3.6. Последовательный алгоритм Метод штрафов 3.7. Параллельный алгоритм 3.8. Проверка эффективности работы программы Список литературы

Подобный материал:

• Рабочей программы дисциплины «Численные методы и программирование» по направлению подготовки, 29.72kb.
• Решение физических задач на эвм" Лекции 20 ч. Практические занятия 96 ч. Учебная, 40.03kb.
• «Исследование и сопоставительный анализ численных методов решения задач не линейного, 321.81kb.
• Автономность эксплуатации без специальных требований к условиям окружающей среды, 258.87kb.
• Тема: «Интеграл» (заключительный урок), 49.41kb.
• Рабочая программа по разделу «Численные методы в строительстве», 71.92kb.
• На первой лекции мы рассмотрим общий смысл понятий бд и субд, 65.83kb.
• Лекция №7. Атрибутивная информация Лекция №7. Атрибутивные данные в гис, 283.92kb.
• Пояснительная записка к курсовой работе по предмету «Языки и технологии программирования», 353.31kb.
• Д. А. Силаев 1/2 года  Физическое явление и математическая модель. Математическое исследование, 20.76kb.

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


Факультет радиофизики и электроники


КАФЕДРА ИНФОРМАТИКИ


ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ РЕАЛИЗАЦИИ ЧИСЛЕННЫХ МЕТОДОВ НА КЛАСТЕРАХ ПЕРСОНАЛЬНЫХ ЭВМ


Магистерская работа студента
Северина Андрея Александровича


Руководитель:

Шпаковский Г.И.,

к.т.н., доцент кафедры информатики

Рецензент:

Шестаков К.М.

к.т.н.,

доцент кафедры интеллектуальных систем

Допустить к защите:

заведующий кафедрой информатики,

профессор С.Г.Мулярчик

«____» «_____________ » 2005 года


Минск, 2005

Содержание

Введение

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

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

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

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

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

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

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