авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |
-- [ Страница 1 ] --

МИНОБРНАУКИ РОССИИ УДК 004.7(075.8)

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

ББК 32.97я73

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

У 91

«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕРВИСА»

(ФГБОУ ВПО «ПВГУС»)

Кафедра «Информационный и электронный сервис»

Рецензент к.т.н., доц. Воловач В. И.

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС Учебно-методический комплекс по дисциплине «Вычислитель по дисциплине «Вычислительные системы» У 91 ные системы» / сост. Н. В. Корнеев. – Тольятти : Изд-во ПВГУС, для студентов направления 2013. – 160 с.

230100.68 «Информатика и вычислительная техника» Для студентов направления 230100.68 «Информатика и вы числительная техника».

Одобрено Учебно-методический комплекс по дисциплине «Вычислитель Учебно-методическим ные системы» для студентов направления 230100.68 «Информатика и Советом университета вычислительная техника» предназначен для изучения основопола гающих разделов дисциплины, связанных с современными микропро Научно-техническим цессорами, высокопроизводительными серверами, вычислительными Советом университета системами кластерного типа, Grid-типа, реконфигурируемыми вычис лительными системами. Лабораторные работы выполняются на базе стенда SDK-1.1 с использованием компьютерных программ и пакетов приложения программирования учебного стенда на языке Си, исполь зуя компилятор SDCC и среду разработки Eclipse.

УДК 004.7(075.8) Составитель Корнеев Н. В. ББК 32.97я © Корнеев Н. В., составление, © Поволжский государственный Тольятти университет сервиса, Содержание Введение....................................................................................................................... 1. Рабочая учебная программа дисциплины..................................................... 1.1. Цели освоения дисциплины........................................................................... 1.2. Место дисциплины в структуре ООП направления................................ 1.3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Вычислительные системы».......................................................... 1.4. Структура и содержание дисциплины....................................................... 1.4.1. Структура дисциплины.................................................................................... 1.4.2. Содержание дисциплины................................................................................ 2. Конспект лекций............................................................................................... 2.1. Вычислительные системы, цели и области применения вычислительных систем, цели и способы повышения их производительности................................................................................................ Контрольные вопросы и задания............................................................................. 2.2. Классификации вычислительных систем, особенности разработки применения систем разных классов.

................................................................... Контрольные вопросы и задания............................................................................. 2.3. Модели и технологии параллельного программирования систем высокой производительности............................................................................... Контрольные вопросы и задания............................................................................. 2.4. Современные микропроцессоры, высокопроизводительные серверы, вычислительные системы кластерного типа, Grid- типа, реконфигурируемые вычислительные системы......................................................................................... Контрольные вопросы и задания............................................................................. 3. Лабораторный практикум..................................................................................... 3.1. Лабораторная работа 1. Взаимное исключение и условная синхронизация потоков....................................................................................................................... 3.2. Лабораторная работа 2. Основные типы синхронизации и способы выполнения параллельных вычислений................................................................. 3.3. Лабораторная работа 3. Устройство современного контроллера на примере SDK-1.1....................................................................................................... 3.4. Лабораторная работа 4. Инструментальные средства для работы со стендом SDK-1.1........................................................................................................ 3.5. Лабораторная работа 5. Дискретные порты ввода-вывода учебно лабораторного стенда SDK-1.1................................................................................ 3.6. Лабораторная работа 6. Таймеры. Система прерываний учебно лабораторного стенда SDK-1.1................................................................................ 3.7. Лабораторная работа 7. Последовательный интерфейс RS-232. UART учебно-лабораторного стенда SDK-1.1................................................................... 3.8. Лабораторная работа 8. Разработка драйвера клавиатуры учебно лабораторного стенда SDK-1.1.............................................................................. 3.9. Лабораторная работа 9. Разработка драйвера жидкокристаллического индикатора (ЖКИ) учебно-лабораторного стенда SDK-1.1...............................   3.10. Лабораторная работа 10. Разработка драйверов интерфейса I2C и I2C устройств учебно-лабораторного стенда SDK-1.1............................................... 4. Самостоятельная работа..................................................................................... 4.1. Организация самостоятельной работы.......................................................... 5. Образовательные технологии.......................................................................... 6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины (модуля)....................................... 7. Учебно-методическое и информационное обеспечение дисциплины (модуля)................................................................................................................................... 8. Материально-техническое обеспечение дисциплины................................... 9. Методические указания для выполнения курсовых проектов (работ). 10. Технологическая карта дисциплины............................................................... Приложение 1..........................................................................................................     Введение Учебно-методический комплекс по дисциплине «Вычислительные системы» для студентов направления 230100.68 «Информатика и вычислительная техника» предназначен для изучения основополагающих разделов дисциплины. Комплекс включает в себя:

- рабочую учебную программу, раскрывающую содержание основных дидактических единиц дисциплины согласно ФГОС направления 230100.68, а также содержащую требования к уровню освоения программы и формы текущего и промежуточного контроля и содержание самостоятельной работы студентов;

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

- лабораторный практикум, который включает 10 лабораторных работ, две из них направлены на получение студентами компетенций ПК-4, остальные связаны с современными микропроцессорами, высокопроизводительными серверами, вычислительными системами кластерного типа, Grid-типа, реконфигурируемыми вычислительными системами и направлены на получение студентами компетенций ОК-6, ПК-7. В каждой лабораторной приводится теоретические сведения, контрольные вопросы, порядок выполнения, защиты, пример выполнения. Лабораторные работы выполняются на базе стенда SDK-1.1 с использованием компьютерных программ и пакетов приложения программирования учебного стенда на языке Си, используя компилятор SDCC и среду разработки Eclipse, утилиту GNU Make для сборки проекта. Для доставки исполняемого модуля в стенд SDK–1.1 используется бесплатно распространяемая утилита M3P (ООО «ЛМТ»).

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

  1. Рабочая учебная программа дисциплины 1.1. Цели освоения дисциплины Целью освоения дисциплины «Вычислительные системы» (ВС) является получение студентами направления подготовки 230100.68 «Информатика и вычислительная техника» (квалификация (степень) «магистр») систематизированных представлений о современном состоянии и принципах действия высокопроизводительных вычислительных систем и их компонентов, а также методах их проектирования и моделирования.

Область профессиональной деятельности (информатика и вычислительная техника) и объекты профессиональной деятельности магистров направления подготовки 230100.68 «Информатика и вычислительная техника»

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

Вычислительные системы представляют собой динамично развивающуюся отрасль информатики и вычислительной техники и находят применение во всех областях профессиональной деятельности магистров направления подготовки 230100.68 «Информатика и вычислительная техника» (квалификация (степень) «магистр»): научно-исследовательской;

проектно-конструкторской;

проектно технологической;

организационно-управленческой.

Потребность решения сложных прикладных задач с большим объемом вычислений и принципиальная ограниченность максимального быстродействия "классических" – по схеме фон Неймана - ЭВМ привели к появлению многопроцессорных вычислительных систем (МВС). Особую значимость параллельные вычисления приобрели с переходом компьютерной индустрии на массовый выпуск многоядерных процессоров.

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

их применение принимает всеобщий характер.

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

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

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

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

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

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

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

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

1.2. Место дисциплины в структуре ООП направления Место дисциплины в учебном процессе: дисциплина «Вычислительные системы» относится к профессиональному циклу дисциплин;

базовой части.

Дисциплина «Вычислительные системы» базируется на входных знаниях, умениях и компетенциях, полученных студентами в процессе освоения программы ВПО уровня «бакалавриат» направления 230100.68 «Информатика и вычислительная техника» по дисциплинам: «Основы теории управления вычислительной техникой», «Организация ЭВМ и систем», «Микропроцессорные системы», «Цифровая обработка сигналов», «Цифровые системы обработки сигналов», «Теория цифровых сигналов и систем», «Аппаратные интерфейсы и протоколы», а также в процессе освоения программы ВПО уровня «магистратура» направления 230100.68 «Информатика и вычислительная техника» по дисциплинам: «Переферийные устройства и интерфейсы», «Сигналы, алгоритмы и устройства ВТ и ИС», «Элементная база и схемотехника устройств ВТ и ИС».

Полученные в ходе изучения дисциплины «Вычислительные системы»

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

  1.3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Вычислительные системы»

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

знать: современное состояние аппаратного и программного обеспечения высокопроизводительных вычислительных систем;

современные технологии программирования высокопроизводительных вычислительных систем (ОК-6);

уметь: использовать типовые программные продукты, ориентированные на решение научных, проектных и технологических задач, применять перспективные методы исследования и решения профессиональных задач на основе знания мировых тенденций развития вычислительной техники и информационных технологий, формировать технические задания и участвовать в разработке аппаратных и/или программных средств вычислительной техники (ПК-4) организовывать работу и руководить коллективами разработчиков аппаратных и/или программных средств информационных и автоматизированных систем (ПК-7) владеть: современными технологиями программирования многопроцессорных вычислительных систем;

навыками по профессиональной эксплуатации современного оборудования и приборов (ПК-4, ПК-7) 1.4. Структура и содержание дисциплины 1.4.1. Структура дисциплины Общая трудоемкость дисциплины составляет 5 зачетных единицы, часов.

Распределение фонда времени по семестрам, неделям, видам занятий Количество часов Самостоятельная Количество часов по плану в неделю работа Число № недель Лабораторные Лабораторные Практические Практические семестра в В неделю занятия занятия Лекции Лекции работы семестре Всего Всего работы Дневная форма обучения 3 19 18 48 153 1 3 87 4,   1.4.2. Содержание дисциплины Распределение фонда времени по темам и видам занятий (дневная форма обучения) Виды учебной работы, Формы включая самостоятельную текущего работу и трудоемкость контроля (в часах) успеваемости (по неделям Самостоятельная № Лабораторные Практические Раздел дисциплины семестра) п/п занятия занятия Лекции работа Форма промежуточн ой аттестации (по семестрам) Тема 1. Вычислительные системы, цели и области применения вычислительных систем, 1 2 Сообщение цели и способы повышения их производительности Тема 2. Классификации вычислительных 2 4 Сообщение систем, особенности разработки применения систем разных классов Защита лабораторных Тема 3. Модели и технологии параллельного работ, 3 6 программирования систем высокой промежуточн производительности ое тестирование Защита Тема 4. Современные микропроцессоры, лабораторных высокопроизводительные серверы, 4 6 32 работ, вычислительные системы кластерного типа, Grid- типа, реконфигурируемые итоговое вычислительные системы тестирование Итого 18 48 87 Экзамен   2. Конспект лекций 2.1. Вычислительные системы, цели и области применения вычислительных систем, цели и способы повышения их производительности По мере развития технических средств изменения окружающего мира, меняются потребности человека к производительности вычислительных систем, меняются и требования приложений. Одним из возможных решений является разработка и применение систем с массовым параллелизмом кластеров, Grid-систем, многопроцессорных комплексов, систем на многоядерных процессорах.

Одну из фундаментальных слабостей современных компьютеров вскрыл в 1977 году Джон Бэкус в речи, с которой он выступил при получении Тьюринговской премии. С тех пор в ход пошло прозвучавшее в ней выражение "бутылочное горло фон Неймана", символизирующее собой органический недостаток архитектурной схемы, которая ассоциируется с именем Джона фон Неймана. Альтернативной архитектурой является "гарвардская" архитектура, называемая так по имени машины Говарда Ай-кена Harvard Mark I, где программы хранились на перфорированных лентах, а обрабатываемые данные в релейных массивах. В современных микроконтроллерах перфоленты заменила память ROM, реле - память RAM, но суть осталась прежней: в процессоре встречаются два независимых и не сдерживающих друг другапотока команди данных.

Происходит смена приоритетов при разработке процессоров, систем на их основе и, соответственно, программного обеспечения. Направление смены приоритетов выражает мнение Дэйва Паттерсона, профессора Калифорнийского университета в Беркли, изобретателя RISC-процессоров и RAID-массивов, который считает, что грядет новое время, когда перестанут действовать прежние прописные истины и им на смену придут новые. Однако переход этот осложняется наличием трех обстоятельств:

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

Нетрудно прийти к выводу, что если нельзя использовать возможности закона Мура на одном ядре из-за исключительной сложности такого ядра, то следует пойти по пути увеличения числа ядер. Именно так поступили в Sun   Microsystems, выпустив 8-ядерный процессор Niagara. На форуме IDF осенью 2004 года Пол Отеллини, генеральный директор Intel, заявил:"Мы связываем наше будущее с многоядерными продуктами;

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

Можно говорить о двух заметно разнящихся между собой тенденциях в процессе увеличения числа ядер. Одна носит названиемультиядерность(multi core). В этом случае предполагается, что ядра являются высокопроизводительными и их относительно немного;

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

Основных недостатков два: первый - высокое энергопотребление, второй высокая сложность чипа и, как следствие, низкий процент выхода готовой продукции. При производстве 8-ядерного процессора IBM Сell только 20% производимых кристаллов являются годными. Другой путь многоядерность(many-core). В таком случае на кристалле собирается на порядок большее число ядер, но имеющих более простую структуру и потребляющих миливатты мощности. Сейчас количество ядер варьируется от 40 до 200, и если закон Мура будет выполняться и для них, то можно ожидать появления процессоров с тысячами и десятками тысяч ядер. Данный подход попадает в категорию так называемых "разрушительных инноваций" (disruptiveinnovation).

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

На конференции HotChips, которая прошла в Стэнфордском университете в конце августа 2009 года, производители рассказали о своих планах по выпуску восьмиядерных серверных процессоров [4].

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

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

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

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

он остается неизменным по сей день.

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

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

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

От машины фон Неймана антимашина отличается наличием одного или нескольких счетчиков данных, управляющих потоками данных. Она программируется с использованием потокового обеспечения (Flowware), а роль центрального процессора в ней играют один или несколько процессоров данных (Data Path Unit, DPU). Центральной частью антимашины может стать память с автоматической последовательностью (Auto-Sequence Memory) (рис.

1.1).

Асимметриямежду машиной и антимашиной наблюдается во всем, за исключением того, что антимашина допускает параллелизм внутренних циклов, а это значит, что в ней решаетсяпроблема параллельной обработкиданных. В антимашине доступ к памяти обеспечивается не по адресу команды или фрагмента данных, записанному в соответствующий регистр, а посредством универсального генератора адресов (GenericAddress Generator, GAG). Его преимущество в том, что он позволяет передавать блоки и потоки данных. В то же время компиляция, посредством которой создается специализированная под определенную задачу система, заключается в объединении нужного количества настроенных процессоров данных в общий массив (Data ProcessArray, DPA), на котором выполняются алгоритмы Flowware и который может быть реконфигурируемым.

  Рис. 1.1. Антимашина Методология GAG непоследовательна, а потому обладает такими достоинствами, как возможность работы с двумерными адресами, что дает неоспоримые преимущества при работе с видеоданными и при выполнении параллельных вычислений. Счетчик данных (data counter) - альтернатива счетчику команд в машине фон Неймана;

его содержимым управляет Flowware.

Для новой методологии придумано и новое название -twin.paradigm;

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

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

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

Специализированные процессоры(Application-Specific Standard Processor).

Процессоры, имеющие набор команд, адаптированный к определенным приложениям.

Конфигурируемые процессоры(Configurable Processor). Своего рода "заготовки" для создания специализированных процессоров, содержат в себе необходимый набор компонентов, адаптируемый к требованиям приложений. В таком случае проектирование специализированного процессора оказывается проще, чем с чистого листа.

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

обычно это бывает программируемая логическая матрица (Field ProgrammableGate-Array,FPGA).

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

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

Таблица 1.1.

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

Основные постулаты современного этапа развития вычислительной техники - повышение энергоэффективности и снижение общего энергопотребления;

совершенствование подсистемы памяти при операциях обращения к памяти;

параллельное исполнение команд, возможно, на разных ядрах.

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

реконфигурируемые системы и процессы;

системы на основе алгоритмов и принципов искусственного интеллекта.

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

Контрольные вопросы и задания 1. В чем состоят проблемы выполнения закона Мура?

2. Охарактеризуйте особенности использования современных вычислительных систем.

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

4. Охарактеризуйте круг фундаментальных и прикладных проблем процессорной техники.

5. Проследите основные тенденции развития микропроцессоров за последние 10 лет.

6. Посмотрите характеристики энергопотребления современных приложений в различных областях.

Литература: [ 1 ], стр. 443- 2.2. Классификации вычислительных систем, особенности разработки применения систем разных классов Одной из наиболее известных схем классификации компьютерных архитектур является таксономия Флинна, предложенная Майклом Флинном в 1972 году. В ее основу положено описание работы компьютера с потоками   команд и данных. В классификации Флинна имеется четыре класса архитектур:

1. SISD (Single Instruction Stream - Single Data Stream) - один поток команд и один поток данных.

2. SIMD (Single Instruction Stream - Multiple Data Stream) - один поток команд и несколько потоков данных.

3. MISD (Multiple Instruction Stream - Single Data Stream) - несколько потоков команд и один поток данных.

4. MIMD (Multiple Instruction Stream - Multiple Data Stream) - несколько потоков команд и несколько потоков данных.

Рассмотрим эту классификацию более подробно.

SISD-компьютеры – это обычные последовательные компьютеры, выполняющие в каждый момент времени только одну операцию над одним элементом данных. Большинство современных персональных ЭВМ принадлежат именно этой категории.

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

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

Управляющий модуль принимает, анализирует и выполняет команды. Если в команде встречаются данные, контроллер рассылает на все ПЭ команду, и эта команда выполняется либо на нескольких, либо на всех процессорных элементах. Процессорные элементы в SIMD-компьютерах имеют относительно простое устройство, они содержат арифметико-логическое устройство (АЛУ), выполняющее команды, поступающие из устройства управления (УУ), несколько регистров и локальную оперативную память. Одним из преимуществ данной архитектуры считается эффективная реализация логики вычислений. До половины логических команд обычного процессора связано с управлением процессом выполнения машинных команд, а остальная их часть относится к работе с внутренней памятью процессора и выполнению арифметических операций. В SIMD-компьютере управление выполняется контроллером, а "арифметика" отдана процессорным элементам. Подклассом SIMD компьютеров являются векторные компьютеры. Пример такой вычислительной системы - Hitachi S3600.

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

MIMD-компьютеры. Этот класс архитектур наиболее богат примерами   успешных реализаций. В него попадают симметричные параллельные вычислительные системы, рабочие станции с несколькими процессорами, кластеры рабочих станций и т. д. Довольно давно появились компьютеры с несколькими независимыми процессорами, но вначале на них был реализован только принцип параллельного исполнения заданий, т.е. на разных процессорах одновременно выполнялись независимые программы. Разработке первых компьютеров для параллельных вычислений были посвящены проекты под условным названием СМ* и С.ММР в университете Карнеги (США).

Технической базой для этих проектов были процессоры DEC PDP-11. В начале 90-х годов прошлого века именно MIMD-компьютеры вышли в лидеры на рынке высокопроизводительных вычислительных систем.

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

Например, существуют такие подклассы MIMD-компьютеров, как системы с разделяемой памятью и системы с распределенной памятью. Системы с разделяемой памятью могут относиться по классификации Флинна как к MIMD, так и к SIMD-машинам. То же самое можно сказать и о системах с распределенной памятью.

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

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

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

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

• с разделяемой памятью;

• с распределенной памятью;

• с распределенно-разделяемой памятью.

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

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

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

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

• уровень выполнения программы/процесса;

• уровень выполнения команд;

• уровень подкоманд (уровень поразрядной обработки).

Основные типы архитектур высокопроизводительных вычислительных систем:

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

SIMD-машины с распределенной памятью SIMD-машины с распределенной памятью называют также матричными процессорами. В системах с такой архитектурой все процессоры в один и тот же момент времени выполняют одну команду. Имеется управляющий процессор, который передает команды процессорам массива. Обычно есть и "фронтальный" (front-end) процессор, которому отводится функция связи с пользователями, а также выполнение тех операций, которые не могут быть выполнены массивом процессоров (например, операции ввода/вывода).

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

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

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

В настоящее время наблюдается тенденция создания комбинированных систем (ccNUMA - Cache Coherent Non-Uniform Memory Access), в которых базовой архитектурной единицей является многопроцессорная конфигурация, составленная из небольшого числа RISC-процессоров (до 16) с одно-каскадным соединением. Системы такого рода можно отнести к MIMD-системам с разделяемой памятью, поскольку при необходимости все процессоры имеют доступ к единому адресному пространству. Необходимый элемент данных может располагаться в любом модуле памяти, однако логически он находится в едином адресном пространстве. Неоднородность заключается в том, что время выборки различных данных может быть разным, поскольку физически они могут располагаться в разных модулях памяти. В системах такого типа приходится решать проблему кэш-когерентности.

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

Кластерная система, при относительно невысокой стоимости, может обладать производительностью, сравнимой с производительностью суперкомпьютеров.

Кластеры рабочих станций обычно называют Беовульф-кластерами (Beowulf cluster - по одноименному проекту). Типичный современный Беовульф-кластер представляет собой кластер рабочих станций, связанных локальной сетью Ethernet и обычно работающих под управлением ОС Linux, хотя в настоящее время разнообразие Беовульф-кластеров достаточно велико.

MIMD-компьютеры с разделяемой памятью иногда называют мультипроцессорными системами. В некоторых мультипроцессорных системах отсутствует общая разделяемая память, вместо нее у каждого процессорного элемента имеется собственная локальная память, но, тем не менее, каждый процессорный элемент имеет доступ к локальной памяти любого процессорного элемента. В этом случае говорят о наличии глобального адресного пространства. Такая организация памяти называется распределенно разделяемой памятью. Передача данных между процессорными элементами осуществляется через разделяемую память - один ПЭ может произвести запись в ячейку памяти, а все остальные ПЭ могут это значение использовать. С точки зрения программиста, коммуникации реализуются посредством разделяемых переменных, т. е. переменных, доступ к которым имеют все параллельные процессы. Примерами вычислительных мультипроцессорных систем могут   служить: Cray X-MP, Cray Y-MP, Cray C90, Cray-3.

Симметричные многопроцессорные системы содержат несколько процессоров в одном компьютере. Каждый процессор имеет доступ к общему набору модулей памяти и работает как процессор общего назначения, который может выполнять любой процесс. Распределение процессов между процессорами осуществляет операционная система, причем алгоритм распределения должен обеспечивать равномерную загрузку процессоров. При этом процессы могут перемещаться на освободившиеся процессоры, что является непростой задачей, решение которой возлагается на операционную систему. Примерами симметричных многопроцессорных систем являются UltraSPARC, IBM RS/6000.

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

В настоящее время ведущими производителями высокопроизводительных вычислительных систем являются: Compaq (продолжение линии AlphaServer SC), Cray Inc. (Cray SV-1, SV-2, MTA-2), Hewlett Packard (HP SuperDome), IBM (ASCI Blue Pacific), SGI (Origin), SRC (SRC-6 и специализированные вычислительные системы). В скобках указаны выпускаемые в настоящее время высокопроизводительные вычислительные системы.

Краткий перечень современных высокопроизводительных вычислительных систем включает: Cambridge Parallel Processing Gamma II, C DAC Param 10000 OpenFrame, серию Compaq GS, серию Compaq AlphaServer SC, Cray SV1, Cray T3E, Cray MTA-2, Fujitsu AP3000, Fujitsu/Siemens PRIMEPOWER, серию Fujitsu VPP5000, Hitachi SR8000, HP 9000 SuperDome, IBM RS/6000 SP, NEC Cenju-4, NEC SX-5, Quadrics Apemille, серию SGI Origin 3000, Sun E10000 Starfire.

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

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

Литература: [ 1 ], стр. 463;

[ 6 ], стр. 256-270;

2.3. Модели и технологии параллельного программирования систем высокой производительности Без каких-либо особенных преувеличений можно заявить, что все развитие компьютерных систем происходило и происходит под девизом «Скорость и   быстрота вычислений». Если быстродействие первой вычислительной машины ENIAC составляло всего несколько тысяч операций в секунду, то самый быстрый на данный момент времени суперкомпьютер может выполнять уже квадриллионы команд.

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

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

Асинхронная передача сообщений Передача сообщений может быть асинхронной или синхронной.

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

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

Chanch(type1id1,type2id2,…);

Идентификатор ch– это имя канала, typei, idi - типы и имена полей данных в передаваемых по каналу сообщениях.

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

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

Идея сети слияния – циклически и параллельно сливать два отсортированных списка в один более длинный отсортированный список. Сеть состоит из процессов-фильтров Merge. Каждый фильтр получает значения из двух упорядоченных входных потоковin1 иin2 и производит один упорядоченный выходной out.

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

Клиенты и серверы Сервер– это процесс постоянно обрабатывающий запросы от клиентских процессов.

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

Рассмотренные монитор и сервер демонстрируют соответствие механизмов, используемых в программах с мониторами и с передачей сообщений (табл. 1.2).

Таблица 1. Программы с мониторами Программы с передачей сообщений Постоянные переменные Локальные переменные сервера Идентификаторы процедур Канал запроса и виды операций Вызов процедуры Send request();

receive reply Вход в монитор Receive request() Возврат в процедуру Send reply() Операторwait Сохранение ожидающего запроса ОператорSignal Получение и обработка ожидающего запроса Тела процедур Ветви оператора выбора по видам операций Поскольку тела процедур монитора аналогичны ветвям оператора выбора в сервере производительность программ с мониторами по сравнению с программами на основе передачи сообщений зависит только от относительной эффективности реализации различных механизмов. На машинах с разделяемой памятью вызовы процедур и действия с условными переменными более эффективны чем примитивы передачи сообщений. Поэтому большинство операционных систем для таких машин реализуются на основе мониторов. С другой стороны, большинство распределенных систем основаны на передаче сообщений, поскольку она является и эффективной и подходящей абстракцией.


Возможно сочетание обоих стилей и реализаций.

Взаимодействующие равные.

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

Пусть есть n процессов, каждый из которых имеет локальную   целочисленную переменную v. Задача процессов - определить наименьшее и набольшее значения среди этих n переменных Эту задачу можно решить так:

один из процессов, например Р [0], собирает все n чисел, находит минимальное и максимальное из них и рассылает результаты остальным процессам. Процесс Р[0] может использовать примитив broadcast, передающий копии сообщения всем остальным процессам;

тогда общее число сообщений будет n.

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

остальные просто отправляют свои значения и ждут результата. Второй способ решения задачи - использовать симметричный подход, в котором все процессы выполняют один и тот же алгоритм. Каждый процесс сначала отправляет свое значение всем остальным, затем все процессы параллельно вычисляют минимум и максимум из n значений. Это решение имеет структуру типа "одна программа- много данных" (singleprogram, multipledata-SPMD). Все процессы выполняют одну и ту же про грамму, но работают с разными данными. Всего используется n*(n-1) сообщений.(Если доступен примитив broadcast, число сообщений сократится до n.) Третий способ решения заключается в организации процессов в логическое кольцо, в котором каждый процесс Р [i] получает сообщения от своего предшественника и отправляет сообщения преемнику. Например, процесс Р [ 0 ] отправляет сообщения процессу Р [ 1 ], тот - процессу Р [ 2 ] и т.д., Р [n-1] - Р[0]. Каждый процесс проходит две стадии. На первой стадии процесс получает два числа, определяет минимальное и максимальное из них и своего значения, затем отправляет результаты своему преемнику. На второй стадии процесс получает значения глобальных минимума и максимума и передает их преемнику. Один процесс, скажем Р [0], действует как инициатор вычислений. Это решение почти симметрично (немного отличается лишь процесс Р [0]), и в нем используется 2*(n-1) сообщений.

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

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

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

Учебные примеры: CSP Язык CSP (Communicating Sequential Processes- взаимодействующие последовательные процессы) - это одна из важнейших разработок в истории параллельного программирования. CSP впервые был описан в статье Тони Хоара (Тоnу Ноаrе) в1978 г. В этой работе были представлены синхронная передача сообщений и так называемое защищенное взаимодействие. Язык CSP существенно повлиял на разработку языка программирования Occam и нескольких других языков, включая Ada и SR. Кроме того, язык CSP вызвал многочисленные исследования и публикации по формальным моделям и семантике передачи сообщений.

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

processА{..В!е;

...} processВ{...А?х,...} Оператор B!е называется оператором вывода. Он задает процесс назначения В и выражение - значение которого нужно отправить этому процессу. Оператор А?х называется оператором ввода. Он указывает процесс источник А и переменную х, в которую должно быть записано принятое сообщение. Эти операторы называются операторами ввода и вывода, поскольку используются как для внешней связи, так и для межпроцессорного взаимодействия. (Оператор вывода ! читается "выдать", ? - "запросить".) Далее дается краткий разбор основных функций языка, а затем представляется пример.

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

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

Язык Occam включает совсем небольшое число механизмов (название языка происходит от выражения "бритва Оккама") и имеет весьма специфический синтаксис. Первая версия языка Occam была разработана в середине 1980-х годов, версия Occam2 появилась в1987 г., а сейчас ведется разработка Occam3. Хотя Occam является самостоятельным языком программирования, он разрабатывался для работы с транспьютером, ранней версией мультикомпьютера, и был, по существу, его машинным языком.

Базовыми элементами программы на языке Occam являются декларации и   три примитивных "процесса": присваивание, ввод и вывод. Процесс присваивания - это просто оператор присваивания. Процессы ввода и вывода аналогичны командам ввода и вывода для языка CSP, но каналы имеют имена и являются глобальными по отношению к процессам. Кроме того, каждый канал должен иметь только одного отправителя и одного получателя.

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

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

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

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

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

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

Оператор присоединения - используется для задания последовательного порядка событий. Если red и green являются событиями, то светофор, который один раз включает green, а затем red, может быть задан так:

green-red-STOP Последний элемент STOP- это простейший процесс CSP, который останавливается без взаимодействия.

Для описания повторения используется рекурсия. Например, следующий   код задает светофор, который циклически включает green, а затем red:

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


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

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

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

Пространство кортежей похоже на единый разделяемый канал связи, за исключением того, что кортежи не упорядочены. Операция помещения кортежа OUT аналогична оператору send, операция извлечения кортежа IN- оператору receive, операция просмотра кортежа RD- оператору receive, оставляющему сообщение в канале. Операция EVAL обеспечивает создание процесса, а операции INP и RDP- не блокирующие ввод и чтение.

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

Учебные примеры: библиотека MPI Интерфейс передачи сообщений (Message Passing Interface - MPI) - это библиотека процедур для передачи сообщений. При использовании библиотеки MPI процессы распределенной программы записываются на таком последовательном языке, как С или Fortran;

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

Интерфейс программирования MPI-приложений был создан в середине 1990-х годов большой группой разработчиков из университетов, правительственных и промышленных организаций. Он отражает опыт работы с такими библиотеками передачи сообщений, как PVM. Цель этой группы состояла в разработке единой библиотеки, которую можно было бы эффективно реализовать на различных многопроцессорных машинах. Теперь библиотека MPI стала стандартом де-факто;

существует несколько ее реализаций.

Программы, использующие библиотеку MPI, имеют так называемый SPMD-стиль (single program, multiple data- одна программа, много данных).

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

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

Учебные примеры: язык Java Язык Java поддерживает параллельное программирование с помощью потоков, разделяемых переменных и синхронизированных методов. Язык Java  можно использовать и для написания распределенных программ. В нем нет встроенных примитивов для передачи сообщений, но есть стандартный модуль Java.net. Классы этого модуля поддерживают низкоуровневое взаимодействие, используя дейтаграммы, связь более высокого уровня с помощью сокетов и взаимодействие через Internet с помощью адресов URL (uniform resource locator унифицированный указатель информационного ресурса).

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

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

все это ведет к увеличению числа каналов.

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

Удаленный вызов процедур Ранее были использованы два типа компонентов программ: мониторы и процессы. Мониторы инкапсулируют разделяемые переменные;

процессы взаимодействуют и синхронизируются, вызывая процедуры монитора.

Предполагается, что процессы и мониторы программы находятся в общем адресном пространстве.

При удаленном вызове процедуры (RPC) используется только один из этих компонентов - модуль, в котором есть и процессы, и процедуры. Модули могут   находиться в разных адресных пространствах, например, на различных узлах сети. Процессы внутри модуля могут разделять переменные и вызывать процедуры, объявленные в этом модуле. Но процессы из одного модуля могут связываться с процессами в другом модуле, только вызывая процедуры, экспортируемые другим модулем.

Следующая диаграмма (рис. 1.2) иллюстрирует взаимодействие между процессом, вызывающим процедуру, и процессом-сервером.

Рис. 1.2.

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

После того как сервер возвратит результаты, вызвавший процесс продолжается.

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

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

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

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

Сервер времени Рассматривается задача реализации сервера  времени - модуля, который обслуживает работу с временными интервалами клиентских процессов из   других модулей. Предположим, что в сервере времени определены две видимые операции: get_time и delay. Клиентский процесс получает время суток, вызывая операцию get_time, и блокируется на interval единиц времени с помощью операции delay. Сервер времени также содержит внутренний процесс, который постоянно запускает аппаратный таймер и при возникновении прерывания от таймера увеличивает время суток.

Кэширование в распределенной файловой системе Рассматривается упрощенная версия задачи, возникающей в распределенных файловых системах и базах данных. Предположим, что прикладные процессы выполняются на рабочей станции, а файлы данных хранятся на файловом сервере. Не будем останавливаться на том, как файлы открываются и закрываются, а сосредоточимся на их чтении и записи. Когда прикладной процесс хочет получить доступ к файлу, он вызывает процедуру read или write в локальном модуле FileCache. Будем считать, что приложения читают и записывают массивы символов (байтов). Иногда это может быть несколько символов, а иногда - тысячи.

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

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

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

Рандеву Сам по себе RPC обеспечивает только механизм межмодульного взаимодействия. Внутри модуля все равно нужно программировать синхронизацию. Иногда приходится определять дополнительные процессы, чтобы обрабатывать данные, передаваемые с помощью RPC. Это было показано в модуле Merge.

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

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

Следующий листинг содержит модуль, реализующий кольцевой буфер.

Процесс Buffer объявляет локальные переменные, которые представляют буфер, и затем циклически выполняет оператор ввода. На каждой итерации процесс Buffer ждет вызова операции deposit или fetch. Условия синхронизации в защитах обеспечивают необходимые задержки операций deposit и fetch.

Реализация кольцевого буфера с помощью рандеву module BoundedBuffer op deposit(typeT), fetch(result typeT);

body process Buffer { typeT buf[n];

int front = 0, rear = 0, count = 0;

while (true) in deposit(item) and count n buf[rear] = item;

rear = (rear+1) mod n;

count = count+1;

[] fetch(item) and count0 item = buf[front];

front = (front+1) mod n;

count = count-1;

ni } endBoundedBuffer Сортирующая сеть из фильтров слияния Снова рассмотрим задачу реализации сортирующей сети с использованием фильтров слияния и решим ее, используя механизм рандеву. Есть два пути.

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

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

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

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

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

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

Используя рандеву, процессы могут связываться между собой напрямую.

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

Таким образом, решение должно быть асимметричным;

один процесс должен выполнить оператор call и затем in, а другой – сначала in, а затем call.

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

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

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

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

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

callMname.opname(аргументы) ;

sendMname.opname(аргументы);

Оператор call завершается, когда операция обслужена и возвращены результирующие аргументы, а оператор send - как только вычислены аргументы. Если операция возвращает результат, ее можно вызывать в   выражении;

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

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

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

Дублируемые файлы Простой способ повысить доступность файла с критическими данными хранить его резервную копию на другом диске, обычно расположенном на другой машине. Пользователь может делать это вручную, периодически копируя файлы, либо файловая система будет автоматически поддерживать копию таких файлов. В любом случае при необходимости доступа к файлу пользователь должен сначала проверить доступность основной копии файла и, если она недоступна, использовать резервную копию. (С этой задачей связана проблема обновления основной копии, когда она вновь становится доступной.) Учебные примеры: язык Java Ранее был представлен язык Java  и программы для чтения и записи простой разделяемой базы данных, а также как создать приложение типа "клиент-сервер", используя передачу сообщений через сокеты и модуль Java.net. Язык Java также поддерживает RPC для распределенных программ.

Поскольку операции с объектами языка Java  называются методами, а не процедурами, RPC в языке Java называется удаленным вызовом метода(remote method invocation-RMI). Он поддерживается модулями Java.rmi и Java.rmi.server.

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

Учебные примеры: язык Ada Язык Ada был создан при содействии министерства обороны США в качестве стандартного языка программирования приложений для обороны (от встроенных систем реального времени до больших информационных систем).

Возможности параллелизма языка Ada являются его важной частью;

они критичны для его использования по назначению. В языке Ada также есть большой набор механизмов для последовательного программирования.

Язык Ada стал результатом широкого международного конкурса разработок в конце 1970-х годов и впервые был стандартизован в 1983 г. В языке Ada83 был представлен механизм рандеву для межпроцессного взаимодействия. Сам термин рандеву был выбран потому, что руководителем группы разработчиков был француз. Вторая версия языка Ada была стандартизована в 1995 г. Язык Ada95 совместим снизу вверх с языком Ada (поэтому старые программы остались работоспособными), но в нем появилось несколько новых свойств. Два самых интересных свойства, связанных с параллельным программированием, - это защищенные типы, подобные мониторам, и оператор requeue, позволяющий программисту более полно управлять синхронизацией и планированием.



Pages:   || 2 | 3 | 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.