Параллельное программирование

С отображением результата на экране все понятно. Но вот действия, которые программа должна произвести "за кадром" иногда занимают достаточно много времени. Естественный вопрос для разработчика - как ускорить выполнение программы? Конечно, можно посоветовать пользователю использовать более быстрый компьютер, но это решение очень ограничено, да и скорости компьютеров сейчас несильно увеличиваются. А вот что увеличивается - это количество ядер на компьютере.

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

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

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

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

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

2. .Таксономия (Классификация) Флинна (англ. Flynn's taxonomy) — общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. Была предложена в 1970-е годы Майклом Флинном. Всё разнообразие архитектур ЭВМ в этой таксономии Флинна сводится к четырём классам:

• ОКОД — Вычислительная система с одиночным потоком команд и одиночным потоком данных
  (SISD, Single Instruction stream over a Single Data stream).
• ОКМД — Вычислительная система с одиночным потоком команд и множественным потоком данных
  (SIMD, Single Instruction, Multiple Data).
• МКОД — Вычислительная система со множественным потоком команд и одиночным потоком данных
  (MISD, Multiple Instruction Single Data).
• МКМД — Вычислительная система со множественным потоком команд и множественным потоком данных
  (MIMD, Multiple Instruction Multiple Data).

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

Отношение конкретных машин к конкретному классу сильно зависит от точки зрения исследователя. Так, конвейерные машины могут быть отнесены и к классу SISD (конвейер — единый процессор), и к классу SIMD (векторный поток данных с конвейерным процессором) и к классу MISD (множество процессоров конвейера обрабатывают один поток данных последовательно), и к классу MIMD — как выполнение последовательности различных команд (операций ступеней конвейера) на множественным скалярным потоком данных (вектором).

Билет 3

1.Преимущества параллельного программирования

Программы, надлежащее качество проектирования которых позволяет воспользоваться преимуществами параллелизма, могут выполняться быстрее, чем их последовательные эквиваленты, что повышает их рыночную стоимость. Иногда скорость может спасти жизнь. В таких случаях быстрее означает лучше. Иногда решение некоторых проблем представляется естественнее в виде коллекции одновременно выполняемых задач. Это характерно для таких областей, как научное программирование, математическое и программирование искусственного интеллекта. Это означает, что в некоторых ситуациях технологии параллельного программирования снижают трудозатраты разработчика ПО, позволяя ему напрямую реализовать структуры данных, алгоритмы и эвристические методы, разрабатываемые учеными. При этом используется специализированное оборудование. Например, в мультимедийной программе с широкими функциональными возможностями с целью получения более высокой производительности ее логика может быть распределена между такими специализированными процессорами, как микросхемы компьютерной графики, цифровые звуковые процессоры и математические спецпроцессоры. К таким процессорам обычно обеспечивается одновременный доступ. МРР-компьютеры (Massively Parallel Processors — процессоры с массовым параллелизмом) имеют сотни, а иногда и тысячи процессоров, что позволяет их использовать для решения проблем, которые просто не реально решить последовательными методами. Однако при использовании МРР-компьютеров (т.е. при объединении скорости и «грубой силы») невозможное становится возможным. К категории применимости МРР-компьютеров можно отнести моделирование экологической системы (или моделирование влияния различных факторов на окружающую среду), исследование космического пространства и ряд тем из области биологических исследований, например проект моделирования генома человека. Применение более совершенных технологий параллельного программирования открывает двери к архитектурам ПО, которые специально разрабатываются для параллельных сред. Например, существуют специальные мультиагентные архитектуры и архитектуры, использующие методологию «классной доски», разработанные специально для среды с параллельными процессорами.

2. .Зако́н Амдала — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента».^[1] Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.

Закон Густафсона (иногда Густавсона) — Барсиса — оценка максимально достижимого ускорения выполнения параллельной программы, в зависимости от количества одновременно выполняемых потоков вычислений («процессоров») и доли последовательных расчётов. Аналог закона Амдала.

Закон Густафсона — Барсиса выражается формулой: , где

g — доля последовательных расчётов в программе,

p — количество процессоров.

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

Билет 4

1. .Синхронизация процессов — приведение двух или нескольких процессов к такому их протеканию, когда определённые стадии разных процессов совершаются в определённом порядке, либо одновременно.

Синхронизация необходима в любых случаях, когда параллельно протекающим процессам необходимо взаимодействовать. Для её организации используются средства межпроцессного взаимодействия. Среди наиболее часто используемых средств — сигналы и сообщения, семафоры и мьютексы, каналы (англ. pipe), совместно используемая память.

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

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

Тем не менее, есть ряд частных способов, применимых в тех или иных случаях:

• Наиболее простой способ: предполагают, что изменения вносились лишь в одну из копий — «рабочую» — и другая копия просто перезаписывается её содержимым. Этот способ реализуют большинство приложений синхронизации; в силу необратимости делаемых изменений пользователю даётся выбор, какую копию считать «главной».
• Если данные представляют собой набор независимых записей (то есть любое сочетание записей является корректным — это, напр., телефонная книга), то можно просто объединить множества записей. Это ликвидирует риск потери информации, но чтобы удалить запись из набора, этот способ приходится сочетать с первым.
• Если наборы синхронизируются неоднократно, можно автоматически вводить в них дополнительную служебную информацию: дата и время последнего изменения записи, пометки об удалённых записях (стираются после следующей синхронизации или через достаточно большое время) и пр. . Этот подход используется, например, в Outlook.
• Обрабатывать конфликты правок: автоматически (если возможно), иначе — вручную. Этот, наиболее общий способ применяется только если указанные выше упрощённые недопустимы — например, в системах контроля версий. Так, CVS при обнаружении двух независимых изменений объявляет о «конфликте» и либо (в простых случаях) разрешает его автоматически, либо предоставляет пользователю разрешить его вручную. В этих случаях конфликтов стараются просто избегать — например, распределением областей компетенции.

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

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

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

Подразделы

• Алгоритм parallel_for
• Алгоритм parallel_for_each
• Алгоритм parallel_invoke
• Алгоритмы parallel_transform и parallel_reduce
• Алгоритм parallel_transform
• Алгоритм parallel_reduce
• Пример. Параллельное выполнение сопоставления и уменьшения
• Секционирование работы
• Параллельная сортировка
• Выбор алгоритма сортировки

· Пример

· В следующем примере показана основная структура алгоритма parallel_for.Этот пример параллельно выводит на консоль все значения в диапазоне [1, 5].

· C++

· // parallel-for-structure.cpp

· // compile with: /EHsc

· #include <ppl.h>

· #include <array>

· #include <sstream>

· #include <iostream>

·

· using namespace concurrency;

· using namespace std;

·

· int wmain()

· {

· // Print each value from 1 to 5 in parallel.

· parallel_for(1, 6, [](int value) {

· wstringstream ss;

· ss << value << L' ';

· wcout << ss.str();

· });

· }

· В данном примере получается следующий результат.

· 1 2 4 3 5

Билет 19

1.

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

Билет 17

1.Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной подписи (ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ^[1]. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

2. Шифр "двойной квадрат" Уитстона

В 1854 г. англичанин Чарльз Уитстон разработал новый метод шифрования биграммами, который называют "двойным квадратом". Свое название этот шифр получил по аналогии с полибианским квадратом. Шифр Уитстона открыл новый этап в истории развития криптографии. В отличие от полибианского шифр "двойной квадрат" использует сразу две таблицы, размещенные по одной горизонтали, а шифрование идет биграммами, как в шифре Плейфейра. Эти не столь сложные модификации привели к появлению на свет качественно новой криптографической системы ручного шифрования. Шифр "двойной квадрат" оказался очень надежным и удобным и применялся Германией даже в годы Второй мировой войны.

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

Рисунок 1 - Две таблицы со случайно расположенными символами русского алфавита для шифра "двойной квадрат"

Предположим, что шифруется биграмма исходного текста ИЛ. Буква И находится в столбце 1 и строке 2 левой таблицы. Буква Л находится в столбце 5 и строке 4 правой таблицы. Это означает, что прямоугольник образован строками 2 и 4, а также столбцами 1 левой таблицы и 5 правой таблицы. Следовательно, в биграмму шифртекста входят буква О, расположенная в столбце 5 и строке 2 правой таблицы, и буква В, расположенная в столбце 1 и строке 4 левой таблицы, т.е. получаем биграмму шифртекста ОВ.

Если обе буквы биграммы сообщения лежат в одной строке, то и буквы шифртекста берут из этой же строки. Первую букву биграммы открытого текста ищут в левой таблице, а соответствующая ей буква зашифрованной биграммы берётся из правой таблицы, в томже столбце, в котором находится символ открытого сообщения. Вторую букву биграммы открытого текста ищут в правой таблице, а соответствующая ей буква зашифрованной биграммы берётся из левой таблице в том же столбце, что и открытый символ биграммы. Поэтому биграмма сообщения ТО превращается в зашифрованную биграмму ЖБ. Аналогичным образом шифруются все биграммы сообщения:

Сообщение ПР ИЛ ЕТ АЮ Ш ЕС ТО ГО

Шифртекст ПЕ ОВ ЩН ФМ ЕШ РФ ЖБ ДЦ

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

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

Билет 18

1.Основные понятия защиты информации и информационной безопасности

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

Рассмотрим основные понятия защиты информации и информационной безопасности:

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

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

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

Эффективность защиты информации – степень соответствия результатов защиты информации по отношению к поставленной цели.

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

Защита информации от разглашения– предотвращение несанкционированного доведения защищаемой информации до неконтролируемого количества получателей информации.

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

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

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

2. Все возможные способы защиты информации сводятся к нескольким основным методикам:

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

скрытие достоверной информации;

предоставление ложной информации.

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

Самыми распространенными способами несанкционированного получения конфиденциальной информации являются:

прослушивание помещений с помощью технических средств;

наблюдение (в т. ч. фотографирование и видеосъемка);

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

хищение носителей информации и производственных отходов;

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

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

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

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

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

защита носителей информации от уничтожения в результате различных воздействий;

предотвращение утечки информации по различным техническим каналам.

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