МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего
«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
(ФГБОУ ВПО «КубГУ»)
Кафедра вычислительных технологий
«МНОГОПОТОЧНОЕ ПРОГРАММИРОВАНИЕ С
ИСПОЛЬЗОВАНИЕМ СТАНДАРТА С++ 11 НА ПРИМЕРЕ
ПРОГРАММЫ ОЦЕНКИ СТРУКТУРЫ AD-HOC СЕТИ»
Краснодар 2014
СОДЕРЖАНИЕ
ВВЕДЕНИЕ........................................................................................................... 3
1 Что такое параллелизм и зачем он нужен. .................................................. 5
1.1 Немного о распараллеливании приложений.................................................. 5
1.2 Средства управления потоками. ..................................................... 8
2 Разработка многопоточного ПО для исследования характеристик сети.... 9
2.1 Анализ задачи. ........................ 9
2.2 Проектирование. ........................................................................ 9
2.3 Стандарт С++ 11. ....................................................................... 10
2.4 Модель. ....................................................................................... 11
ЗАКЛЮЧЕНИЕ.................................................................................. 21
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.................. 22
ПРИЛОЖЕНИЕ А................................................................. 23
Класс node. ............................................................................. 23
ПРИЛОЖЕНИЕ Б........................................................................ 24
Класс grafe. ....................................................................... 24
ПРИЛОЖЕНИЕ В................................................................... 25
Класс T_Averaged_Components. ....................................... 25
ПРИЛОЖЕНИЕ Г............................................................. 26
Класс T_Bridges..................................................................... 26
ПРИЛОЖЕНИЕ Д............................................................. 27
Реализация методов класса grafe. ....................... 27
ПРИЛОЖЕНИЕ Е........................................................... 34
Подпрограмма многопоточного запуска.......................... 34
3
ВВЕДЕНИЕ
Телекоммуникационная отрасль – это та отрасль, без технологий
которой сегодня не может полноценно функционировать практически ни
одна организация, служба или предприятие. Таким образом, благосостояние,
эффективная работа государства – напрямую зависят от состояния его
информационной развитости. От того, какие услуги, с каким уровнем
качества и доступности могут обеспечить существующие сегодня
телекоммуникационные технологии.
Сегодня мы можем наблюдать стремительный рост количества
мобильных устройств у населения и, соответственно, потенциальных
пользователей, желающих иметь быстрый беспроводной доступ в Интернет,
причем в любой точке и без разрыва сеансов связи.
В прошлой работе были получены результаты:
Разработана программа, позволяющая исследовать имеющуюся
беспроводную ad hoc сеть, представленную неориентированным графом, на
предмет повреждений структуры сети и возможности восстановить
поврежденную структуру, а так же снизить риск нарушения структуры путем
выявления ненадежных участков сети – мостов.
Проведены испытания, показавшие, что при увеличении числа узлов в
сети, расположенных на фиксированной площади, растет и количество
ненадежных каналов связи, при разрыве которых сеть потеряет целостность,
распавшись на несколько несвязанных сегментов. При этом, количество
таких каналов возрастает в 2 раза при увеличении концентрации сетевых
узлов в 3 раза. По результатам испытаний установлено, что сбор информации
для восстановления структуры сети при числе узлов, большем чем 2000,
будет иметь, как верхнюю оценку времени и, если N ≤ 2000, то
временная оценка не больше, чем,.
Программа работала, с точки зрения ресурсозатрат, далеко не
оптимально. Главный недостаток разработанного продукта – длительное
4
время выполнения, достигавшее 5 часов (на некоторых конфигурациях – до 8
часов).
5
1 Что такое параллелизм и зачем он нужен.
1.1 Немного о распараллеливании приложений.
Первый способ распараллелить приложение – запустить несколько
однопоточных процессов, исполняемых одновременно. Процессы могут
обмениваться данными с помощью стандартных средств межпроцессной
коммуникации (файлы, сигналы, сокеты…). Благодаря использованию
стандартных системных механизмов коммуникации процессов код
получается более безопасным, чем при использовании потоков. Также,
процессы можно распределять по локальной сети между многими
компьютерами, значительно повышая вычислительную эффективность.
Однако, за безопасность приходится платить повышенными накладными
расходами на запуск процесса. В случаях, когда эти расходы слишком
велики, а процессы не планируется исполнять по сети, стоит рассмотреть
распараллеливание по потокам.
Второй способ. Несколько потоков. Потоки запускаются в рамках
общего процесса. Обмен данными происходит через общую разделяемую
память процесса. Этот способ характеризуется меньшими накладными
расходами на содержание нескольких потоков и коммуникацию со стороны
ОС. Однако, этот подход имеет свои недостатки. В частности, общая
разделяемая память потоков требует тщательного понимания возможных
ситуаций обращения потоков к ней, ибо непродуманное взаимодействие
потоков через общую память может обернуться весьма неприятными
последствиями – от задержек в работе программы до «мертвых блокировок».
Мертвая блокировка – ситуация в многопоточной среде, когда
несколько потоков находятся в состоянии бесконечного ожидания ресурсов,
занятых самими этими потоками.
Применение параллелизма в приложениях.
Разделение обязанностей, улучшение структуры кода программы.
Типичный случай – когда программа должна работать с несколькими
6
разнородными потоками данных одновременно (файловая система,
звуковой/видео канал, интерфейс пользователя). Если обработка всего этого
выполняется в одном потоке, то придется организовывать слежение за
действиями пользователя и переключение между соответствующими
задачами, что существенно усложнит понимание и разработку продукта.
Применение же нескольких потоков (на число ядер процессоров не
ориентируемся, ибо важна ясность структуры, а не скорость) позволит
разнести структуру приложения на несколько относительно независимых
частей, каждая из которых обрабатывает свою часть данных отдельно, при
необходимости связываясь с другими потоками (при чтении файла
произошла ошибка – идем к потоку интерфейса и показываем сообщение).
Обработчики взаимодействий потоков упростят отладку, т. к. не нужно искать
по всему коду места переключения задач.
Повышение производительности.
В 1965 году один из основателей Intel Гордон Мур обнаружил
закономерность: появление новых моделей микросхем наблюдалось спустя
примерно год после предшественников, при этом количество транзисторов в
них возрастало каждый раз приблизительно вдвое. Мур пришел к выводу,
что при сохранении этой тенденции мощность вычислительных устройств за
относительно короткий промежуток времени может вырасти
экспоненциально. Это наблюдение получило название — закон Мура.
В 1975 году Гордон Мур внёс в свой закон коррективы, согласно
которым удвоение числа транзисторов будет происходить каждые два года.
Однако, из-за физических ограничений, накладываемых на
вычислительные схемы (в т. ч. отвод выделяемого тепла и потери тока),
чтобы получить возможность задействовать на практике ту дополнительную
вычислительную мощность, которую предсказывает закон Мура, стало
необходимо задействовать параллельные вычисления. На протяжении
многих лет, производители процессоров постоянно увеличивали тактовую
частоту и параллелизм на уровне инструкций, так что на новых процессорах
7
старые однопоточные приложения исполнялись быстрее без каких-либо
изменений в программном коде. Сейчас по разным причинам производители
процессоров предпочитают многоядерные архитектуры, и для получения
всей выгоды от возросшей производительности ЦП программы должны
переписываться в соответствующей манере. Поэтому для повышения
эффективности от многоядерных, процессорных систем программы
необходимо проектировать как набор параллельных задач.
Используются два способа такого распараллеливания:
а. Распараллеливание по задачам (задача разбивается на части,
выполняющиеся параллельно)
б. Распараллеливание по данным (каждый поток выполняет
обработку своей части общих данных).
Рисунок 1 – Распараллеливание по задачам.
Рисунок 2 – Распараллеливание по данным.
8
Параллелизм не стоит применять, если выигрыш в производительности
параллельной версии относительно однопоточной перекрывается
накладными расходами, либо же неоправданным усложнением кода
программы, делающим ее дальнейшую разработку и сопровождение
затруднительным.
1.2 Средства управления потоками.
В случае, когда потоки имеют некоторые общие данные, которые они
могут изменять независимо друг от друга, могут произойти весьма
неприятные события – если объект изменяется одним потоком, и тут же
другой считывает из него же данные – хорошего мало, вплоть до аварийного
завершения работы приложения. Во избежание таких ситуаций, доступ к
общим данным обычно закрывается мьютексом, который позволяет
блокировать доступ к объекту, пока его изменение не завершено.
9
2 Разработка многопоточного ПО для исследования характеристик сети
2.1 Анализ задачи.
Необходимо разработать программный продукт, позволяющий:
· Принимать информацию о сети, сгенерированную определенным
образом.
· Строить на основе принятых данных о сети ее графовое
представление, необходимое для проведения дальнейших
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
