ГОСЫ / Bilety

биометрический образец к определённому человеку. Например, персональный идентификационный номер (PIN) прикрепляется к определённому образцу, либо смарт-карта, содержащая образец, вставляется в считывающее устройство. В таком случае, снова делается образец биометрической характеристики и сравнивается с представленным образцом. Идентификация по любой биометрической системе проходит четыре стадии:

Запись – физический или поведенческий образец запоминается системой;

Выделение – уникальная информация выносится из образца и составляется биометрический образец;

Сравнение – сохраненный образец сравнивается с представленным;

Совпадение/несовпадение - система решает, совпадают ли биометрические образцы, и выносит решение.

Подавляющее большинство людей считают, что в памяти компьютера хранится образец отпечатка пальца, голоса человека или картинка радужной оболочки его глаза. Но на самом деле в большинстве современных систем это не так. В специальной базе данных хранится цифровой код длиной до 1000 бит, который ассоциируется с конкретным человеком, имеющим право доступа. Сканер или любое другое устройство, используемое в системе, считывает определённый биологический параметр человека. Далее он обрабатывает полученное изображение или звук, преобразовывая их в цифровой код. Именно этот ключ и сравнивается с содержимым специальной базы данных для идентификации личности [19].

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

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

1.3 Способы идентификации личности по биометрическим параметрам.

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

Далее рассмотрим подробнее каждый способ биометрической идентификации.

1.3.1 Статические способы

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

Рассмотрим подробнее методы идентификации:

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

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

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

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

81

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

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

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

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

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

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

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

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

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

Этот способ относится к наиболее динамично развивающимся направлениям в индустрии биометрии. Его привлекательность основана на том, что не требуется специального дорогого оборудования. Достаточно персонального компьютера и видеокамеры. Кроме того, отсутствует физический контакт с устройствами. Не нужно прикасаться ни к чему, либо останавливаться, специально ожидая срабатывания системы [18].

–Термографическое наблюдение лицевых артерий и вен. Идентификация человека по лицу сильно упрощаются, если перейти в инфракрасный диапазон световых волн. Термография идентифицируемого лица выявляет уникальность расположения на лице артерий, снабжающих кожу кровью, которые выделяют тепло (Рис. 7). Для получения термограммы, используются специальные камеры инфракрасного диапазона. В отличие от идентификации по форме лица, этот метод позволяет различать близнецов, лицевые кровеносные сосуды которых сильно различаются. Вопроса подсветки для этих биометрических устройств не существует, поскольку они воспринимают лишь температурные перепады лица и свет им не нужен. Эффективность распознавания не зависит от перегрева или переохлаждения лица, естественного старения личности, пластических операций, так как они не изменяют внутреннее положение сосудов.

В этом способе идентификации используется специализированная видеокамера инфракрасного дальнего диапазона.

82

–Идентификация по венам руки. На биометрическом рынке присутствуют устройства, которые построены на анализе индивидуального расположения вен на руках. Во внимание принимается рисунок вен, расположенных на тыльной стороне кисти сжатой в кулак руки (Рис.8). Наблюдение за рисунком вен осуществляет телевизионная камера при инфракрасной подсветке. При вводе изображения производится его бинаризация, выделяющая вены. Подобное оборудование производит единственная английская фирма Vinchek.

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

–По форме уха. Ухо окончательно сформировано в момент рождения, а дальше только растет, полностью сохраняя свою форму (Рис. 9).

Марк Никсон, британский компьютерный исследователь из Университета Саутгемптона вместе с коллегами разработал компьютерный метод идентификации по уху, который он назвал «лучевое преобразование изображения». Метод довольно хитрый и сводится к «обстрелу» изображения разноцветными лучами, что позволяет с точностью 99,6% отследить все особенности ушной раковины и записать их в цифровом виде[1].

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

1.3.2 Динамические способы

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

Рассмотрим подробнее методы идентификации:

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

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

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

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

Вначале на этапе фильтрации удаляются данные о «служебных» клавишах – функциональных, управления курсором и т. д.

Потом выделяются следующие характеристики пользователя:

Число ошибок в процессе набора;

Время между нажатиями на клавиши;

Скорость набора.

Время на удержание клавиш;

Аритмичность при наборе.

83

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

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

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

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

84

Параллельные вычисления Фролова

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

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

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

Закон Амдаля

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

Т1, Т2, ... Тp – время последовательной работы, выполняемой каждым процессором без взаимодействия между собой. Тогда время выполнения задачи на p процессорах определяется неравенством:

Tpar	T0	max(Ti ) T0
		i

p

(Ti )

i 1		где i=1, 2, ... p. Равенство получается, когда Тi равны между собой.
	p

p

Отсюда, подставляя (Ti ) = Tseq – T0, где Tseq есть время выполнения задачи на одном процессоре,

		i 1
	получаем:
	Tpar ≥ T0 +	Tseq T0	. Делим на Tseq и, обозначая через f = T0 / Tseq - долю (fraction)
		p

последовательного участка в общем объеме вычислений, получим:

	Tpar	f	(1 f )	.	(1.1)
	Tseq		p

Ускорение (Speedup) – это отношение времени выполнения задачи в последовательном режиме (на 1 процессоре), ко времени выполнения задачи в параллельном режиме (на p процессорах).

STseq , используя неравенство (1.1), получим

Tpar

S

1

p

(1.2)

f

(1 f )

( p 1) f

1

p

Отсюда видно, что при f=0 и равенстве Ti получим S=p, при f >0 и p → ∞, получим

S

1

. Данная

f

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

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

85

Рассматривая закон Амдаля, мы предполагали, что доля последовательных расчетов f является постоянной величиной и не зависит от параметра n, определяющего вычислительную сложность решаемой задачи. Однако для большого ряда задач доля f=f(n) является убывающей функцией от n, и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет уменьшения доли последовательной работы, выполняемой каждым процессором. Иначе говоря, ускорение Sp= Sp(n) является возрастающей функцией от параметра n (данное утверждение часто называют эффектом Амдаля).

Эффективность распараллеливания.

Эффективность распараллеливания – это способность алгоритма использовать все задействованные в выполнении задачи процессоры на 100%. Формула вычисления эффективности:

S

E 100% (1.2)p

Т.е. если ускорение S = p (максимально возможное на p процессорной машине), то эффективность распараллеливания задачи равна 100%. Используя закон Амдаля получаем верхнюю оценку эффективности:

		1
E ≤ 100%				(1.3)
		(1 f ( p 1))

Например, E ≤ 52.25% для p=100 и f=0.01 и E ≤ 9.1% для p=1000 и f=0.01.

Вывод. При малой доли последовательной работы увеличение количества процессов приводит к ухудшению параллельной эффективности (причина – с ростом процессов растет количество обменов). Например, если f=0.01 (1%), то Е<100 и использовать для решения параллельной задачи более 100 процессоров нецелесообразно. Для повышения эффективности, как правило, не

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

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

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

Масштабируемость – это пропорциональное увеличение объема задачи с увеличением числа используемых для ее решения процессоров. Наличие масштабируемости задач является важным свойством тестовых систем оценки производительности параллельных вычислительных систем.

Плохая масштабируемость параллельного приложения на MPP-системе может быть вызвана а) ростом затрат на коммуникации при увеличении числа используемых процессоров; б) неравномерностью распределения вычислительной нагрузки между процессорами.

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

86

Оценим накладные расходы (total overhead), которые имеют место при выполнении параллельного алгоритма T0 = P*Tp − T1 , где T1 - время выполнения последовательного алгоритма задачи, Tp - время выполнения алгоритма задачи на P процессорах.

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

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

Tp = (T1 + T0)/P , Sp = T1/ Tp = (P* T1)/( T1 + T0)

Тогда эффективность использования процессоров можно выразить как

EP = Sp/P = T1/ (T1 + T0) = 1/(1+ T1/T0)

Тогда, если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0. При фиксированном числе процессоров, эффективность можно улучшить путем повышения сложности решаемой задачи T1, поскольку предполагается, что при увеличении сложности накладные расходы T0 растут медленнее, чем объем вычислений T1.

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

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

87

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

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

1.SISD (Single Instruction, Single Data) – системы с одиночным потоком команд и одиночным потоком данных; к данному типу систем можно отнести обычные последовательные ЭВМ;

2.SIMD (Single Instruction, Multiple Data) – системы с одиночным потоком команд и множественным потоком данных; это многопроцессорные вычислительные системы, в которых в каждый момент времени может выполняться одна и та же команда для обработки нескольких информационных элементов; подобной архитектурой обладают, например, многопроцессорные системы с единым устройством управления;

3.MISD (Multiple Instruction, Single Data) – системы с множественным потоком команд и одиночным потоком данных. Относительно данного типа систем нет единого мнения – ряд специалистов говорят, что примеров конкретных ЭВМ, соответствующих данному типу вычислительных систем, не существует, и введение подобного класса предпринимается для полноты системы классификации; другие же относят к данному типу, например, системы с конвейерной обработкой данных;

4.MIMD (Multiple Instruction, Multiple Data) – системы с множественным потоком команд и множественным потоком данных; к подобному классу систем относится большинство параллельных многопроцессорных вычислительных систем.

Хотя система Флинна широко используется при конкретизации типов компьютерных систем, такая классификация приводит к тому, что практически все виды параллельных систем (несмотря на их существенную разнородность) относятся к одной группе MIMD. Неоднократные предпринимались попытки детализации системы Флинна. Так, например, для класса MIMD была предложена структурная схема, в которой дальнейшее разделение типов многопроцессорных систем основывается на способах организации памяти: системы на общей и распределенной памяти.

Существующие параллельные ВС класса MIMD образуют два технических подкласса: симметричные мультипроцессоры (SMP) и системы с массовым параллелизмом (МРР).

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

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

2.Системы с массовым параллелизмом (массивно-параллельные системы massively parallel processor или MPP), примером которых являются кластерные вычислительные системы − это совокупность вычислительных узлов, объединенных в рамках некоторой сети для решения одной задачи. В настоящее время, в качестве вычислительных узлов используются многоядерные процессорные элементы (SMP узлы). Каждый узел работает под управлением своей копии операционной системы, в качестве которой чаще всего используются юниксоподобные ОС (Linux, AIX и т.п) или OC WINDOWS. Состав и мощность узлов может меняться даже в рамках одного кластера, давая возможность создавать неоднородные (гетерогенные) вычислительные системы.

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

способность.

Понятие пропускной способности и латентности

88

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

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

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

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

1.пропускная способность однонаправленных пересылок ("точка-точка", uni-directional bandwidth), равная максимальной скорости, с которой процесс на одном узле может передавать данные другому процессу на другом узле.

2.пропускная способность двунаправленных пересылок (bidirectional bandwidth), равная максимальной скорости, с которой два процесса могут одновременно обмениваться данными по сети.

Методы измерения пропускной способности и латентности

Для измерения пропускной способности однонаправленных пересылок ("точка-точка") процесс с номером 0 посылает процессу с номером 1 сообщение длины L байт. Процесс 1, приняв сообщение от процесса 0, посылает ему ответное сообщение той же длины. Используются блокирующие вызовы MPI. Эти действия повторяются N раз с целью минимизировать погрешность за счет усреднения. Процесс 0 измеряет время T, затраченное на все эти обмены. Пропускная способность R определяется по формуле R=2NL/T.

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

Латентность измеряется как время, необходимое на передачу сигнала или сообщения нулевой длины. Для снижения влияния погрешности и низкого разрешения системного таймера (очень малые времена округляются до 0) важно повторить операцию посылки сигнала и получения ответа большое число раз. Таким образом, если время на N итераций пересылки сообщений нулевой длины туда и обратно составило T сек., то латентность измеряется как s=T/(2N).

89

5. Общие свойства параллельных алгоритмов. Полная и неполная параллельность. Особенности выбора способов распараллеливания.

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

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

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

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

итопологий сети. На сегодняшний день производительность самого мощного суперкомпьютера мира — IBM Roadrunner достигает 1,105 PFLOP.

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

Параллельный алгоритм должен быть эффективным и мобильным.

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

Свойство 1 - использование в алгоритме параллельной программы множественного выполнения (N раз) одного и того же элементарного алгоритма:

Этим свойством обладают алгоритмы задач, в которых надо найти состояния S1, S2, … Sn физической системы в разные последовательные моменты времени: T1, T2, …, Tn и дано состояние физической системы S0 в момент времени T0.

Состояние физической системы в момент времени i+1 можно описать как Si+1=Э(Si). Т.е. алгоритм представляет собой последовательное выполнение элементарного алгоритма Э с входными данными Si и выходными Si+1, где Э – не зависит от i. (от i зависят входные данные и результат). Нельзя вычислить состояние Si, не вычислив предыдущее состояние Si-1

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

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

Свойство 3 – параллельные алгоритмы допускают совмещение множества операций.

90