архитектура параллельных вычислений. АПВ УМКД+++. Учебнометодический комплекс дисциплины csse 43057 Паралелльные и облачные вычисления
 Скачать 1 Mb.
|
Исходные данныеВажность этого этапа связана как с необходимостью упорядочивания требований к создаваемой ЛС и ее отдельным составляющим для обеспечения возможности принятия в будущем взвешенных конкретных решений, так и с ее обоснованием. При создании новой сети для какого-нибудь предприятия желательно учитывать следующие факторы: Требуемый размер сети (в настоящее время, в ближайшем будущем и по прогнозу на перспективу). Структура, иерархия и основные части сети (по подразделениям предприятия, а также по комнатам, этажам и зданиям предприятия). Основные направления и интенсивность информационных потоков в сети (в настоящее время, в ближайшем будущем и в дальней перспективе). Характер передаваемой по сети информации (данные, оцифрованная речь, изображения), который непосредственно сказывается на требуемой скорости передачи (до нескольких сотен Мбит/с для телевизионных изображений высокой четкости). Технические характеристики оборудования (компьютеров, адаптеров, кабелей, репитеров, концентраторов, коммутаторов) и его стоимость. Возможности прокладки кабельной системы в помещениях и между ними, а также меры обеспечения целостности кабеля. Обслуживание сети и контроль ее безотказности и безопасности. Требования к программным средствам по допустимому размеру сети, скорости, гибкости, разграничению прав доступа, стоимости, по возможностям контроля обмена информацией и т.д. Необходимость подключения к глобальным или к другим локальным сетям. Вполне возможно, что после изучения всех факторов выяснится, что можно обойтись без сети, избежав тем самым довольно больших затрат на аппаратуру и программное обеспечение, установку, эксплуатацию, поддержку и ремонт сети, зарплату обслуживающему персоналу, и т.д. Сеть по сравнению с автономными компьютерами порождает множество дополнительных проблем: от простейших механических (компьютеры, подключенные к сети, труднее перемещать с места на место) до сложных информационных (необходимость контролировать совместно используемые ресурсы, предотвращать заражение сети вирусами). К тому же пользователи сети уже не так независимы, как пользователи автономных компьютеров, им надо придерживаться определенных правил, подчиняться установленным требованиям, которым их необходимо научить. Наконец, сеть остро ставит вопрос о безопасности информации, защиты от несанкционированного доступа, ведь с любого компьютера сети можно считать данные с общих сетевых дисков. Защитить один компьютер или даже несколько одиночных гораздо проще, чем целую сеть. Поэтому приступать к установке сети целесообразно только тогда, когда без сети работа становится невозможной, непроизводительной, когда отсутствие межкомпьютерной связи сдерживает развитие дела. Требования и варианты решений при выборе размера и структуры сети, сетевого оборудования и программного обеспечения будут рассмотрены в последующих разделах. В начале проектирования сети необходимо провести полную "инвентаризацию" имеющихся компьютеров и их программного обеспечения, а также периферийных устройств (принтеров, сканеров и т.д.). Это позволит при организации сети исключить ненужное дублирование (оборудование и программное обеспечение теперь могут быть разделяемыми ресурсами), а также поставить задачи модернизации (апгрейда) как аппаратных, так и программных средств. Для корректного определения характеристик компьютеров целесообразно использовать специальные диагностические программы или встроенные программы ОС (например, в ОС WindowsMillennium это программа "Сведения о системе" из раздела служебных программ и программа "Система" из панели управления). Следует выбирать такие варианты программ, которые обеспечивают получение правильных данных ("старые" диагностические программы могут неверно указать тип процессора и версию ОС), а также сохранение данных в файле (это особенно ценно при большом числе компьютеров). Кроме того, следует уделить внимание наличию встроенной сетевой карты или сетевого контроллера на системной плате, а также типу поддерживаемых ими сетевых стандартов (как правило, поддерживается сеть Ethernet на витой паре, но принципиально знать ее разновидность – 10/100/1000 Мбит/c). Не все характеристики компьютеров, которые важны при их объединении в сеть, могут быть определены описанными выше способами. Из сопроводительной документации к компьютеру или после вскрытия системного блока можно и нужно определить число и тип свободных слотов (разъемов) расширения, а также максимальную мощность блока питания. Это необходимо для оценки возможности установки в компьютер новых плат. Контрольные вопросы: Проектирование взаимосвязанных сетей. Организационная структура. Оценка компромисса дизайна в топологии сети. Маршрутизация. Управление потоком Лекция №15. Задержка толерантности. Обзор задержки толерантности. Явная передача сообщений. Общее адресное пространство. Многопоточность в общем адресном пространстве. План лекции: Обзор задержки толерантности. Многопоточность в общем адресном пространстве. Синтаксическая конструкция, с помощью которой обеспечивается доступ к определенному объекту (переменной, полю записи, массиву или его элементу, файлу), называется неявным адресом(implied address). Примеры неявных адресов дают следующие конструкции: Point^.Name, arrA[4], intValue, D:\DelProj\Table.xls. Используя неявный адрес, программист или пользователь предполагает, что адресуемый объект хранится в некотором участке памяти. Доступ к этому участку со стороны программы осуществляется по логическому адресу (logical address), который идентифицирует объект в виртуальной памяти. Логический адрес преобразуются в реальный физический адрес (physical address) ячейки оперативной памяти или порта. Под адресным пространством компьютера понимается множество адресов памяти. Адресное пространство, понимаемое как множество адресов, доступных программе, еще называют виртуальным адресным пространством, а элемент этого пространства – виртуальным адресом. Определение «виртуальный», относящееся к техническим средствам или данным, указывает на то, что некоторый элемент представляется прикладному программисту существующим, тогда как фактически в представляемом виде он отсутствует. Например, при запуске приложения современная 32-разрядная операционная система, работая в так называемом защищенном режиме, представляет ему для кода и данных блок памяти размером 4 Гбайт. Понятно, что далеко не каждый пользователь может выделить 4 Гбайт ОЗУ под одно приложение. Фактически предоставляется пространство логических адресов, по которым, теоретически может храниться до 4 Гбайт информации. Это и есть виртуальное пространство. Компьютер незаметно для программиста компенсирует недостаток физической памяти, используя специальный страничный механизм, организующий обмен блоков данных или программ между оперативной и внешней памятью. Реальное адресное пространство – это множество адресов, существующих в памяти ЭВМ физически (реально). Элемент реального адресного пространства – реальный адрес. Реальное адресное пространство является лишь частью виртуального. Логическим адресным пространством называется множество адресов команд и данных, используемых в конкретной программе, потому иногда его называют адресным пространством программы. Логическое адресное пространство может быть частью реального адресного пространства или выходить за его пределы. Микропроцессор аппаратно поддерживает две модели оперативной памяти: - сегментированная модель, в которой программе выделяются непрерывные области памяти, называемые сегментами, а сама программа может обращаться только к информации, которая находится в этих сегментах; - страничная модель, которую можно рассматривать как надстройку над сегментированной моделью. Основное применение этой модели связано с организацией виртуальной памяти, что позволяет операционной системе использовать для работы программ пространство памяти большее, чем объем физической памяти. Для микропроцессоров Pentium размер доступной виртуальной памяти может достигать 4 Тбайт (терабайт – 240 байт). Особенности использования и реализации этих моделей зависят от режима работы микропроцессора: - режим реальных адресов, или просто реальный режим, - защищенный режим. Контрольные вопросы: Задержка толерантности. Обзор задержки толерантности. Явная передача сообщений. Общее адресное пространство. Многопоточность в общем адресном пространстве. Литература : Кудин А.В., Линёв А.В., Архитектура и операционные системы параллельных вычислительных систем. Нижний Новогород, 2007. 73с. El-Rewini H. Abd-El-Barr M. Advanced Computer Architecture and Parallel Proccesing. Wiley-Interscience, 2005. Dubois M., Annavaram M., Stenstrom P. Parallel Computer Organization and Design, Cambridge University Press, UK, 2010. Xingfu Wu, Performance Evaluation, Prediction and Visualization of Parallel Systems, Springer Science & Business Media, 2012. 319 c. Студенты должны: ПЛАНЫ ПРОВЕДЕНИЯ ПРАКТИЧЕСКИХ/СЕМИНАРСКИХ И ЛАБОРАТОРНЫХ / СТУДИЙНЫХ ЗАНЯТИЙ И МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ ЗАДАНИЙ Практическое занятие№1 МВС для высокопроизводительных вычислений. Задание дляработы: Основные понятия и определения. Сферы применения и типы многопроцессорных вычислительных систем. Краткое описание проводимогозанятия: На этапе подготовки к практическому занятию студенты должны, используя учебную литературу и материалы лекций углубить свои знания по методам оценки уязвимости информации. Во время проведения занятия Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к практическому занятию. Затем преподаватель разбивает группу студентов на несколько подгрупп по два студента в каждой. Каждая подгруппа получает от преподавателя индивидуальный вариант задания на практическое занятие. Студенты должны: Практическая работа№2. Архитектура высокопроизводительной системы. Задание дляработы: Архитектура высокопроизводительной системы Краткое описание проводимогозанятия: На этапе подготовки к практическому занятию студенты должны, используя учебную литературу и материалы лекций углубить свои знания по методам оценки уязвимости информации. Во время проведения занятия Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к практическому занятию. Затем преподаватель разбивает группу студентов на несколько подгрупп по два студента в каждой. Каждая подгруппа получает от преподавателя индивидуальный вариант задания на практическое занятие. Студенты должны: Практическая работа№3. SMP и MPP-архитектуры. Задание дляработы: SMP и MPP-архитектуры. На этапе подготовки к практическому занятию студенты должны, используя учебную литературу и материалы лекций углубить свои знания по методам оценки уязвимости информации. Во время проведения занятия Преподаватель перед проведением занятия проводит контрольный опрос студентов и определяет степень их готовности к практическому занятию. Затем преподаватель разбивает группу студентов на несколько подгрупп по два студента в каждой. Каждая подгруппа получает от преподавателя индивидуальный вариант задания на практическое занятие. Студенты должны: Практическая работа№4. Понятие о микропроцессоре. Развитие элементной базы ЭВМ и возможности интегральной технологии. Архитектурные особенности микропроцессоров для» (микро) ЭВМ и высокопроизводительных параллельных вычислительных систем Задание дляработы: Понятие о микропроцессоре. Развитие элементной базы ЭВМ и возможности интегральной технологии. Архитектурные особенности микропроцессоров для» (микро) ЭВМ и высокопроизводительных параллельных вычислительных систем
5 ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ОБУЧАЮЩЕГОСЯ И МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИХ ВЫПОЛНЕНИЮ
6 МАТЕРИАЛЫ ДЛЯ ТЕКУЩЕГО, РУБЕЖНОГО КОНТРОЛЯ, ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ Вопросы для текущего контроля Вопросы для подготовки к рубежному контролю 1,2. 1. Когда была создана первая супер ЭВМ? • в середине 70-х • в середине 60-х • в начале 80-х • в начале 80-х • в конце 70-х 2. Кем была разработана первая супер-ЭВМ? • Джоном фон Нейманом • Сеймуром Крэем • Томасом Стерлингом • Доном Беккером • Биллом Гейтсом 3. Матричный процессор - это ... • уст-во для передачи инф-ции из одного процесса в другой • уст-во для оповещения процесса со стороны ОС о событии • уст-во для выполнения оп-ций над матрицами, как примит. инстр-ми • уст-во для обр-ки больших объемов инф-ции в режиме реальн. Времени 4. Найдите верное утверждение. Конвейерные процессоры ... • выполн. оп-ции с массивами при помощи примитивных инструкций • выполн. оп-ции над матрицами при помощи примитивных инстр-ций • выполняют возврат выполнения операции • выделяют отдельные этапы выполнения общей операции • производят временнОе распараллеливание программы 5. Выделите верные утверждения. Архитектура компьютера - это... • его описание воплощения в "железе" • описание путей прохождения сигналов • описание основных компонентов компьютера • детальное описание его электронных компонентов и их соединений • описание внутренней структуры системы или микропроцессора • набор команд, разрядность машинного слова, методы адресации 6. Выделите основные термины, используемые в вычислительной технике для описания ЭВМ • архитектура ЭВМ • операционная система ЭВМ • размер ЭВМ • организация ЭВМ • производительность ЭВМ • схема ЭВМ 7. Количество схем, классифицирующих ЭВМ по Флинну. Введите только число.(4) 8. Укажите неправильное утверждение. • SISD - это обычные последовательные компьютеры • SIMD - большинство современных ЭВМ относятся к этой категории • MISD - вычислительных машин такого класса мало • MIMD -это реал-ция нескольких потоков команд и потоков данных 9. Верно ли утверждение, что матричный процессор - это типичный представитель SIMD архитектуры? (да) 10. Основные принципы архитектуры фон Неймана - это... • хранение прог-мы и данных для ее выполнения в ОЗУ • памяти для инструкций и данных разделены • примение в микроконтроллерах • наличие устройства управления • загрузка прог-мы в память программ происходит через спец. ОС • наличие устройства ввода-вывода • запуск из памяти только одной программы 11. Для конвейерной обработки присуще: • загрузка операндов в векторные регистры • операций с матрицами • выделение отдельных этапов выполнения общей операции • сложение 2-х операндов одновр-ным слож-ем всех их двоичных разрядов 12. Верно ли утверждение, что если один фрагмент программы может быть эффективно реализован на конвейерном устройстве, то он может быть также эфективно реализован в параллельном режиме на наборе последовательных устройств? (нет) 13. В Вашей программе доля последовательных операций равна 0,4. Какое ускорение расчета программы Вы получите на ЭВМ с 4 процессорами? Ответ округлить до сотых. (1,82) 14. Приоритет - это... • описание алгоритма на некотором формализованном языке • число, приписанное ОС каждому процессу или задаче • отдельный этап выполнения общей операции • оповещение со стороны ОС о той или иной форме взаимодействия 15. Стек - это... • "память", в адресном пространстве которой работает процесс • тот или иной способ передачи ин-ции из одного процесса в другой • обл. памяти для локальн. переменных, аргументов и возвр. функциями значений • орг-ция дост. 2х (или более) процессов к одному и тому же блоку памяти 16. Кластер (в контексте параллельного программироваиня)- это... • область оперативной памяти • упр. устр-во, выполненное на одном или более кристаллах • 2 или более узлов, соед-ных при помощи сетевых т-ий на базе ком-ров • раздел жесткого диска • суперкомпьютер для выполнения особых задач 17. Процесс - это... • сетевой интерфейс контроллера блочных передач • это число, приписанное операционной системой каждой задаче • это динам. сущность прог-мы, ее код в процессе своего выполнения • система, выполняющая повторяющуюся операцию 18. Конвейерному устройству требуется выполнить операцию сложения над двумя одномерными массивами по 100 элементов, причем операция суммирования состоит из 4 подопераций. Каково будет ускорение при расчете? Результат округлить до сотых. из пяти подопераций (3,85) 19. Выберите шаг(и), не присущий(е) для цикла выполнения команды: • запись результата в память • выборка команды • кэширование следующей команды • выполнение команды • декод-ние команды, вычисление адреса операнда и его выборка • обращение к памяти 20. Пусть имеется конвейер, состоящий из двух сегментов. Первый сегмент — выборка команды, второй — ее выполнение. Пусть время выполнения од- ной команды 10 мкс. Посчитайте время выполнения 7 команд. Ответ округлить до сотых и ввести только число (в мкс). (40) 21. Ресурс - это... • объект, необходимый для работы процессу или задаче • сообщение, доставляемое процессу посредст. ОС • процесс превращения скомпилированного кода в программу • число, приписанное ОС каждому процессу и задаче 22. Выберите верное утверждение. Активные ресурсы... • используют взаимные исключения • могут быть использованы одновременно несколькими процессами • способны изменять информацию (процессор) • исп-тся только одним пр-ссом пока тот не завершит работу с ресурсом 23. Какая ОС является первообразной в параллельном программировании? • DOS • Windows • Unix • Linux • MacOS • OS/2 24. Функцией мютекса является: • регистрация обработчика сообщения в операционной системе • распред. квантов времени в сист. между выполняющ-ся проц-сами • способ синхр-ции парал-ных задач через раздел-мый критич. Ресурс • способ обмена данными проц-рами через разд. память или ком. Канал 25. Процесс имеет: • собственное состояние • собственный процессор • собственную систему • собственный семафор 26. Основной механизм взаимодействия виртуальной и физической памяти: • Системный • Векторный • Матричный • Страничный 27. ... - это быстрое статическое ОЗУ, вставленное между исполнительными устройствами и системным ОЗУ. (кеш) 28. MPI - это ... • модуль параллельной обработки в системе • специальная ОС для параллельного программирования • ин-фейс, содежащий набор ф-ций, типов и констант для ПП • орг-ция, координирующая разработку параллельных интерфейсов 29. Таблица регистров позволяет проследить за: • характеристикой регистров • использованием регистров • переименованием регистров • блокировкой регистров 30. Какова структура объединения блоков системы HP Convex SPP1000? • кольцо (одномерный тор) • двумерный тор • куб • гиперкуб 31. Что является достоинством коммутаторов с пространственным разделением? • высокая надежность • возможность одновременного контакта со всеми устройствами • простота соединения 32. Другое название коммутаторов с временным разделением: • Мезонин • Шина • Колесо • Кольцо 33. Назовите два типа простых коммутаторов: • параллельные и последовательные • управляемые и неуправляемые • с временным и пространственным разделением • цифровые и аналоговые 34. Потоковые процессоры принадлежат к архитектуре: • SIMD • MISD • MIMD • SISD 35. Конвейерная технология предполагает … • последовательную обработку команд • обработку команд, удовлетворяющих определенным критериям • обработку несколько команд одновременно 36. Коммуникационной средой называется: • способ соед-ния проц-ров между собой, с памятью и с внеш. уст-вами • организация процесса преобразования информации • совокупность устройств, реализующих арифм. и лог. Операции 37. Транспьютер представляет собой … • коммуникационную среду • кластерную систему • микропроцессор • компьютер для конроля транспорта 38. Система, главной особенностью является наличие общей физической памяти, разделяемой всеми процессорами называется ... • NUMА • SMP • MPP • PVP 39. Главная особенность архитектуры NUMA? • неоднородный доступ к памяти • сверхвысокая производительность • наличие векторно-конвейерных процессоров • наличие общей физич. памяти, разделяемой всеми процессорами 40. Вычислительные машины с какой архитектурой наиболее дешевы? • с готической архитектурой • параллельная архитектура с векторными процессорами • кластерные системы • массивно-параллельная архитектура 41. Какая из приведенных ниже архитектур отсутствует в классификации Флинна? • MISD • SIND • MIMD • SIMD 42. Пиковая производительность системы определяется в: • Мегагерц • MIPS • МFlops • MBite 43. Пиковая производительность системы определяется: • временем выполнения реальных задач • произведен. пиковой произв-ти 1-го процессора на число проц. в сист. • временем выполнения тестовых задач • количеством переданной информации 44. Производительность многопроцессорной вычислительной системы характеризуется: • количеством операций, производимых за единицу времени • количеством байт информации, переданных в единицу времени • числом импульсов, генерируемых в единицу времени • объемом располагаемой для вычислений памяти 45. Посчитать ускорение для конвейера с 7 командами из 6 сегментов. (2) 46. Количество ... называют глубиной конвейера • Сегментов • Операций • Циклов • Регистров 47. Определите неверное утверждение. Для RISC архитектуры характерно: • набор ком-д должен быть огранич. и включать только простые ком-ды • команды в основном сложные или составные • быстрота исполнения зависит от реализации компилятора • более простая архитектура по сравнению с CISC • набор ком-д вкл. команды, близкие к операторам языка ВУ 48. Найдите неправильный ответ(ы). Составными частями процессора являются: • устройство ветвления • диспетчер • шина управления • устройство для чисел с плавающей запятой • ОЗУ • устройство для целых чисел • кэш 49. Найдите неверное утверждение. Векторные команды... • загружают операнд из оперативной памяти в векторный регистр • могут выполняться одновременно в одном процессоре • выполняют арифм. и логические операции над векторами • записывают операнд из регистра в память 50. Выделите случаи параллелизма на низком уровне: • параллелизм заданий • параллелизм команд • параллелизм на уровне программы • параллелизм на уровне маш. слов и арифм. Операций 51. ... характеризует возрастание сложности соединений при добавлении в конфигурацию новых узлов. (масштабируемость) 52. Коммуникационным ... сети именуется максимальный путь между любыми двумя узлами. (диаметром) 53. Найдите неверные утверждения. Примерами топологий являются • Гиперкуб • Бабочка • Квадрат • Баньян • Звезда • Ель • Кольцо 54. ... представляет собой часть сообщения, его длина ограничена, хотя и может варьироваться. (пакет) 55. Найдите неверное утверждение. По способу взаимодействия процессоров с оперативной памятью архитектуры бывают: • с распределенно-разделяемой памятью • с разделяемой памятью • с распределенной памятью • с когерентной кэш-памятью 56. Укажите наиболее быструю организацию сети для кластера. • Gigabit Ethernet • Myrinet • SCI • Ethernet 57. ... - это конечный набор правил, расположенных в определенном логическом порядке и позволяющий исполнителю решать любую конкретную задачу из некоторого класса однотипных задач. • Действие • Алгоритм • Программа • Процесс • Выражение 58. Найдите неверное(ые) утверждение(я). Основные модели программирования: • Распределенная • Параллельная • Последовательная • Синхронная • посредством передачи сообщений • параллелизм данных 59. Закон Амдала рассчитывает: • время, затрачиваемое на вычисления • количество вложенных операций • глубину конвейера • ускорение при расчетах на нескольких процессорах 60. Как быстро в последние годы удваивается производительность современных ЭВМ? • за 9 месяцев • за 12 месяцев • за 18 месяцев • за 24 месяца 61. Барьер - это... • подпр-ма опред-щая факт прихода сооб-ния, но реально его не принимающая • место в прог-ме, где процесс ожидает подхода к нему ост-ных пр-сов • блок-ка проц-са до тех пор, пока все оп-ции обмена не будут завершены • ожидание завершения асинхр. процедур, ассоциир. с идентиф-тором 62. Семафор - это ... • аппаратный коммутатор • устройство синхронизации для параллельных ЭВМ • прогр-ный комм-тор в виде переменной, имеющей общ. доступ к памяти 63. Сигналы... • позв. огр-чить область вид-сти сооб-ний рамками одной группы процессов • это сооб-ния, доставляемые процессу посредством ОС • осущ-ют передачу данных и управ-щей инф-ции между процессорами 64. Верно ли утверждение, что почтовые ящики увеличивают скорость и эффективность обработки за счет того, что обработка целого набора (вектора) данных выполняется одной командой. • Да • Нет 65. Пассивные ресурсы ... • способны изменять информацию • могут быть использованы одновременно несколькими процессами • могут быть одновременно использованы только одним процессом • используют совместно разделяемый ресурс 66. "Тупик" - это... • ожидание процессом ресурса, который никогда не освободится • монополизирование процессором задачи • ожидание процессорами занятого ресурса • зависание программы 67. Среда коммуникации характеризуется: • протоколом передачи • количеством узлов • пропускной способностью • типом шины 68. ... предназначен(о) для организации условных и безусловных переходов в программе. • устройство для работы с целыми числами • диспетчер • устройство ветвления • процессор • кэш • контроллер 69. Является ли указатель стека регистром? • Да • Нет 70. Какая из шин отсутствует в микропроцессорной системе? • Адреса • Управления • Согласования • Данных 71. Верно ли утверждение, что одним преимуществ архитектуры RISC процессора является ее простота? • Да • Нет 72. Найдите неверное утверждение. Устройство для работы с целыми числами может быть использовано для ... • выполнения инкремента на 1 • логического умножения • побитовой инверсии • арифметического сложения • выполнения исключающего "или" • кэширования результата • выполнения побитового сдвига влево 73. Наиболее быстрый доступ процессор имеет к ... • ROM • Cache • RAM • EPROM • Flash 74. Без наличия какой(их) функции(й) не возможна работа любой MPI программы? • MPI_Barrier( ) • MPI_Finalize( ) • MPI_Comm_rank ( ) • MPI_Init ( ) • MPI_Comm_size ( ) • MPI_Reduce ( ) 75. Для каких систем существует реализация MPI? • Unix • Windows ME • Windows NT • DOS • Windows 2000 • Windows 98 Тестовые задания для экзаменационной сесссии: 76. Коммуникатор - это ... • то же, что и коммутатор • переговорное устройство в параллельной системе • идентификатор группы процессоров • иммитатор связи в кластере 77. Кэш - это... • вид ОЗУ • вид ПЗУ • специальная память процессора • вид соединения в системе • одна из команд АЛУ 78. Какую стратегию использования памяти предполагает MPI? • Разделяемую • Распределенную • Удаленную • Локальную 79. Конкурирующие процессы - это ... • процессы, использующие совместно разделяемый ресурс • процессы, решающие одну задачу • независимые процессы на разных процессорах 80. Линковка или связывание - это ... • компиляция исходного кода • вызов процессора друг другом • превращение скомпилированного кода в загрузочный модуль • обмен сообщениями в системе 81. Параллельная программа – это… • программа, содержащая несколько процессов, работающих совместно • программа, работающая одновременно на нескольких компьютерах • 82. Многопоточные системы… • выполняется несколько потоков на одном процессоре по очереди, разделяя время процессора, ОП, другие ресурсы • компоненты выполняются на вычислительных системах, связанных сетью с помощью обмена сообщениями • научные вычисления, моделирование для суперкомпьютеров 83. Распределенные системы… • выполняется несколько потоков на одном процессоре по очереди, разделяя время процессора, ОП, другие ресурсы • компоненты выполняются на вычислительных системах, связанных сетью с помощью обмена сообщениями • научные вычисления, моделирование для суперкомпьютеров 84. Синхронные параллельные вычисления… • выполняется несколько потоков на одном процессоре по очереди, разделяя время процессора, ОП, другие ресурсы • компоненты выполняются на вычислительных системах, связанных сетью с помощью обмена сообщениями • научные вычисления, моделирование для суперкомпьютеров 85. Асинхронной моделью вычислений называется… • когда все процессы выполняют одни и те же действия с собственными данными • когда различные процессы решают разные задачи 86. Синхронной моделью вычислений называется… • когда все процессы выполняют одни и те же действия с собственными данными • когда различные процессы решают разные задачи 87. Две операции называются независимыми если • множество чтения одной не пересекается с множеством чтения другой • множество чтения одной не пересекается с множеством записи другой • множество чтения одной пересекается с множеством записи другой • множество чтения одной пересекается с множеством чтения другой 88. Что такое фильтр? 89. Что такое конвейер? 90. Какой процесс называется потребителем? 91. Какой процесс называется производителем? 92. Приведите примеры удаленного вызова процедуры (рандеву) • файловая система на сервере • web-сайт 93. Что такое клиент (клиентское приложение)? 94. Что такое сервер (серверное приложение)? 95. что такое суперскалярность? Исполнение нескольких инструкций одновременно 96. Взаимодействие чего осуществляется легче? • 2-х задач • 2-х процессов • Процесса и задачи 97. Что имеет собственную память? • Процесс • Поток • И процесс, и поток 98. Как организуется взаимодействие процессов? • Через общую память • Через обмен сообщениями 99. Какие общие ресурсы есть у потоков? • Память • Стек • Отображение виртуальной памяти на реальную • Все перечисленное • Ничего из перечисленного 100. Какие общие ресурсы есть у процессов? • Память • Стек • Отображение виртуальной памяти на реальную • Все перечисленное • Ничего из перечисленного 101. Чем характеризуется состояние параллельной программы? • значением переменных в некоторый момент времени • последовательностью состояний s0->s1->…->sn. 102. Чем характеризуется история параллельной программы? • значением переменных в некоторый момент времени • последовательностью состояний s0->s1->…->sn. 103. Цель синхронизации процессов • исключить нежелательные истории 104. Каким свойством должна обладать параллельная программа? • Живучесть • Безопасность 105. Какие существуют виды синхронизации? • Взаимное исключение • Условная синхронизация • Абсолютная синхронизация 106. Взаимное исключение состоит в… • задержке процесса, пока не выполнится некоторое условие • выделении в процессах критических секций, которые не прерываются другими процессами, использующими те же переменные 107. Условная синхронизация заключается в … • задержке процесса, пока не выполнится некоторое условие • выделении в процессах критических секций, которые не прерываются другими процессами, использующими те же переменные 108. Приведите пример правильной параллельной программы поиска максимального элемента в массиве • int m=0; parallel for (i=0; i if (a[i] > m) m = a[i]; • int m=0; parallel for (i=0; i < if (a[i] > m) m = a[i]; > • int m=0; parallel for (i=0; i if (a[i] > m) < m = a[i]; > • int m=0; parallel for (i=0; i if (a[i] > m) < if (a[i] > m) m = a[i]; > 109. Приведите пример неэффективной параллельной программы поиска максимального элемента в массиве • int m=0; parallel for (i=0; i if (a[i] > m) m = a[i]; • int m=0; parallel for (i=0; i < if (a[i] > m) m = a[i]; > • int m=0; parallel for (i=0; i if (a[i] > m) < m = a[i]; > • int m=0; parallel for (i=0; i if (a[i] > m) < if (a[i] > m) m = a[i]; > 110. Приведите все примеры неправильной параллельной программы поиска максимального элемента в массиве • int m=0; parallel for (i=0; i if (a[i] > m) m = a[i]; • int m=0; parallel for (i=0; i < if (a[i] > m) m = a[i]; > • int m=0; parallel for (i=0; i if (a[i] > m) < m = a[i]; > • int m=0; parallel for (i=0; i if (a[i] > m) < if (a[i] > m) m = a[i]; > 111. Какие из приведенных условий относятся к свойствам безопасности? • Взаимное исключение. В любой момент только один процесс может выполнять свою критическую секцию. • Отсутствие взаимной блокировки. Если несколько процессов пытаются войти в свои критические секции, хотя бы один сделает это. • Если процесс пытается войти в критическую секцию, а другие выполняют некритические секции, то ему разрешается вход • Процесс, который пытается войти в критическую секцию когда-нибудь это сделает. 111. Какие из приведенных условий относятся к свойствам живучести? • Взаимное исключение. В любой момент только один процесс может выполнять свою критическую секцию. • Отсутствие взаимной блокировки. Если несколько процессов пытаются войти в свои критические секции, хотя бы один сделает это. • Если процесс пытается войти в критическую секцию, а другие выполняют некритические секции, то ему разрешается вход • Процесс, который пытается войти в критическую секцию когда-нибудь это сделает. 112. Перечислите алгоритмы критической секции со справедливой стратегией • алгоритм разрыва узла • алгоритм билета • алгоритм поликлиники 113. Что представляет из себя справедливая стратегия? • дать возможность каждому процессу попасть в критическую секцию • дать возможность некоторым процессам попасть в критическую секцию 114. Недостатком алгоритма разрыва узла (Питерсона) является • сложно обобщается на случай двух процессов • сложность, отсутствие грани между переменными синхронизации и другими переменными, неэффективность (ожидающие процессы постоянно проверяют переменные, что занимает время процессора) 115. Алгоритм билета основан на том, что • обеспечивает поочередный вход двух процессов в критическую секцию • каждый процесс, который пытается войти в CS получает номер, который больше номера любого из ранее вошедших. Процесс ждет, пока не будут выполнены CS процессов, имеющих меньшие номера 116. Реализация критических секций в Windows 117. В чем отличие мьютекса от критической секции? • Критическая секция действует в пределах одного процесса, а мьютекс может использоваться для взаимодействия разных процессов (являются глобальными объектами ОС) • Мьютекс действует в пределах одного процесса, а критическая секция может использоваться для взаимодействия разных процессов (являются глобальными объектами ОС) 118. Что такое мьютекс? 119. Что такое семафор? • Процедура • Специальная переменная 120. Какую стратегию применяет операционная система при работе с семафорами? • справедливую стратегию • несправедливую стратегию 121. Что такое барьерная синхронизация? • синхронизация по времени окончания операций в разных процессах 122. Основное требование, предъявляемое к барьерной синхронизации? • ни один из процессов не должен перейти барьер, пока к нему не подошли все процессы 123. Какую роль играют семафоры в задаче о производителе и потребителе • счетчика ресурсов 124. В решении какой задачи используется метод передачи эстафеты? • Об обедающих философах • О производителе и потребителе • О писателях и читателях 125. Создание семафоров в Windows 126. Какая функция в Windows соответствует операции P для семафора • ReleaseSemaphore • WaitForSingleObject 127. Какая функция в Windows соответствует операции V для семафора • ReleaseSemaphore • WaitForSingleObject 128. Какая функция в Unix клонирует текущий процесс? • fork • execl, execv • waitpid • kill • signal 129. Какая функция в Unix позволяют заменить текущий процесс новым? • fork • execl, execv • waitpid • kill • signal 130. Какая функция в Unix позволяет ожидать окончания порожденного процесса? • fork • execl, execv • waitpid • kill • signal 131. Какая функция в Unix посылает сигнал процессу? • fork • execl, execv • waitpid • kill • signal 132. Какая функция в Unix позволяет указать функцию, выполняющуюся при получении сигнала? • fork • execl, execv • waitpid • kill • signal 133. Какая библиотека в Unix используется для реализации многопоточности? • PTHREAD 134. Какую функцию не содержит библиотека PTHREAD? • для создания потока с указанием выполняющейся в потоке функции • ожидания окончания потока • объекты синхронизации (мьютексы). 135. Пусть p – количество процессоров. Расписание Hp для каждой вершины (операции) i указывает номер процессора Pi и время начала операции ti. Расписание реализуемо, если • Для любых i,j : ti = tj => Pi ≠ Pj т.е. один и тот же процессор не должен назначаться разным операциям в один и тот же момент. • Для любой дуги (i,j) tj ≥ ti+1 т.е. к началу операции все данные должны быть вычислены. • Для любых i,j : ti <> tj => Pi ≠ Pj т.е. один и тот же процессор не должен назначаться разным операциям в один и тот же момент. • Для любой дуги (i,j) tj < ti+1 т.е. к началу операции все данные должны быть вычислены. 136. T∞ = D(G) (D(G) – …в графе G). • Длина максимального пути в графе • Максимальный поток • Максимальный поток минимальной стоимости 137. Выберете правильное утверждение • Tp < T∞ - T1/p • Tp < T∞ + T1/p • Tp >T∞ + T1/p • Tp > T∞ - T1/p 138. сверхлинейное ускорение - обычно возможно при • Нелинейной зависимости сложности алгоритма • Увеличением числа процессоров, что может привести к потере эффективности. 139. Пусть f – доля последовательных вычислений в алгоритме. Сформулируйте закон Амдаля • Sp > 1/(f + (1-f)/p) > 1/f • Sp ≤ 1/(f + (1-f)/p) ≤ 1/f • Sp ≤ 1/(f - (1+f)/p) ≤ 1/f • Sp ≤ 1/(f + (1-f)/p) ≤ f 140. Масштабируемость алгоритма определяет • степень сохранения эффективности при уменьшении количества процессоров. • степень сохранения эффективности при росте количества процессоров. 141. Для сохранения эффективности обычно требуется • Увеличивать объем обрабатываемой информации. • Уменьшать объем обрабатываемой информации. 142. Виды декомпозиции 143. При решении какой задачи используется ленточная схема? • Метод Гаусса 144. Интерфейс OpenMP задуман как стандарт параллельного программирования для • многопроцессорных систем с общей памятью (SMP, ccNUMA, …) • многопроцессорных систем с разделенной памятью ( …) 145. Основания для достижения эффекта • разделяемые для параллельных процессов данные располагаются в общей памяти • для организации взаимодействия не требуется операций передачи сообщений. • разделяемые для параллельных процессов данные располагаются в распределенной памяти 146. Положительные стороны использования технологии OPEN MP • Можно распараллеливать последовательные программы поэтапно, не меняя их структуру • Нет необходимости поддерживать последовательный и параллельный вариант программы, поскольку директивы игнорируются обычными компиляторами (в общем случае) • Учет и использование возможностей систем с общей памятью • Поддержка в наиболее распространенных языках (C/C++, Fortran) и платформах (Windows, Unix) 147. Принципы организации потоков • Использование потоков • Пульсирующий 148. При появлении директивы #parallel происходит • синхронизация, все потоки, кроме master, уничтожаются • продолжается последовательное выполнение кода (до очередного появления директивы #parallel) • создание “команды” (team) потоков для параллельного выполнения вычислений 149. После выхода из области действия директивы #parallel происходит • синхронизация, все потоки, кроме master, уничтожаются • продолжается последовательное выполнение кода (до очередного появления директивы #parallel) • создание “команды” (team) потоков для параллельного выполнения вычислений 150. Типы директив • Определение параллельной области • Разделение работы • Синхронизация 151. Перечислите возможные параметры директивы parallel • if (scalar_expression) • private (list) • firstprivate (list) • default (shared | none) • shared (list) • copyin (list) • reduction (operator: list) • num_threads(integer-expression) 152. Управление областью видимости обеспечивается при помощи параметров (clause) директив • private, • firstprivate, • lastprivate, • shared, • default, • reduction, • copyin 153. Параметр shared определяет список переменных, которые • будут общими для всех потоков параллельной области правильность использования таких переменных должна обеспечиваться программистом • будут локальными для каждого потока; переменные создаются в момент формирования потоков параллельной области; начальное значение переменных является неопределенным • перед использованием инициализируются значениями исходных переменных • запоминаются в исходных переменных после завершения параллельной области (используются значения потока, выполнившего последнюю итерацию цикла или последнюю секцию) 154. Параметр private определяет список переменных, которые • будут общими для всех потоков параллельной области правильность использования таких переменных должна обеспечиваться программистом • будут локальными для каждого потока; переменные создаются в момент формирования потоков параллельной области; начальное значение переменных является неопределенным • перед использованием инициализируются значениями исходных переменных • запоминаются в исходных переменных после завершения параллельной области (используются значения потока, выполнившего последнюю итерацию цикла или последнюю секцию) 155. Параметр firstprivate позволяет создать локальные переменные потоков, которые • будут общими для всех потоков параллельной области правильность использования таких переменных должна обеспечиваться программистом • будут локальными для каждого потока; переменные создаются в момент формирования потоков параллельной области; начальное значение переменных является неопределенным • перед использованием инициализируются значениями исходных переменных • запоминаются в исходных переменных после завершения параллельной области (используются значения потока, выполнившего последнюю итерацию цикла или последнюю секцию) 156. Параметр lastprivate позволяет создать локальные переменные потоков, значения которых • будут общими для всех потоков параллельной области правильность использования таких переменных должна обеспечиваться программистом • будут локальными для каждого потока; переменные создаются в момент формирования потоков параллельной области; начальное значение переменных является неопределенным • перед использованием инициализируются значениями исходных переменных • запоминаются в исходных переменных после завершения параллельной области (используются значения потока, выполнившего последнюю итерацию цикла или последнюю секцию) 157. Начало выполнения директив по умолчанию • не синхронизируется • синхронизировано 158. директива DO/for для распределения вычислений в параллельной области • распараллеливание циклов • распараллеливание раздельных фрагментов кода (функциональное распараллеливание) • директива для указания последовательного выполнения кода 159. директива sections для распределения вычислений в параллельной области • распараллеливание циклов • распараллеливание раздельных фрагментов кода (функциональное распараллеливание) • директива для указания последовательного выполнения кода 160. директива single для распределения вычислений в параллельной области • распараллеливание циклов • распараллеливание раздельных фрагментов кода (функциональное распараллеливание) • директива для указания последовательного выполнения кода 161. Распределение итераций в директиве for регулируется параметром (clause) schedule static • итерации делятся на блоки по chunk итераций и статически разделяются между потоками; если параметр chunk не определен, итерации делятся между потоками равномерно и непрерывно • распределение итерационных блоков осуществляется динамически (по умолчанию chunk=1) • размер итерационного блока уменьшается экспоненциально при каждом распределении; chunk определяет минимальный размер блока (по умолчанию chunk=1) • правило распределения определяется переменной OMP_SCHEDULE (при использовании runtime параметр chunk задаваться не должен) 162. Распределение итераций в директиве for регулируется параметром (clause) schedule dynamic • итерации делятся на блоки по chunk итераций и статически разделяются между потоками; если параметр chunk не определен, итерации делятся между потоками равномерно и непрерывно • распределение итерационных блоков осуществляется динамически (по умолчанию chunk=1) • размер итерационного блока уменьшается экспоненциально при каждом распределении; chunk определяет минимальный размер блока (по умолчанию chunk=1) • правило распределения определяется переменной OMP_SCHEDULE (при использовании runtime параметр chunk задаваться не должен) 163. Распределение итераций в директиве for регулируется параметром (clause) schedule guided • итерации делятся на блоки по chunk итераций и статически разделяются между потоками; если параметр chunk не определен, итерации делятся между потоками равномерно и непрерывно • распределение итерационных блоков осуществляется динамически (по умолчанию chunk=1) • размер итерационного блока уменьшается экспоненциально при каждом распределении; chunk определяет минимальный размер блока (по умолчанию chunk=1) • правило распределения определяется переменной OMP_SCHEDULE (при использовании runtime параметр chunk задаваться не должен) 164. Распределение итераций в директиве for регулируется параметром (clause) schedule runtime • итерации делятся на блоки по chunk итераций и статически разделяются между потоками; если параметр chunk не определен, итерации делятся между потоками равномерно и непрерывно • распределение итерационных блоков осуществляется динамически (по умолчанию chunk=1) • размер итерационного блока уменьшается экспоненциально при каждом распределении; chunk определяет минимальный размер блока (по умолчанию chunk=1) • правило распределения определяется переменной OMP_SCHEDULE (при использовании runtime параметр chunk задаваться не должен) 165. Директива master определяет фрагмент кода, который должен быть выполнен только основным потоком; все остальные потоки пропускают данный фрагмент кода (завершение директивы по умолчанию не синхронизируется) выполняться только одним потоком в каждый текущий момент времени (критическая секция) 166. Директива critical определяет фрагмент кода, который должен быть выполнен только основным потоком; все остальные потоки пропускают данный фрагмент кода (завершение директивы по умолчанию не синхронизируется) выполняться только одним потоком в каждый текущий момент времени (критическая секция) 167. Директива barrier – определяет • точку синхронизации, которую должны достигнуть все процессы для продолжения вычислений (директива должны быть вложена в блок) • переменную, доступ к которой (чтение/запись) должна быть выполнена как неделимая операция • точку синхронизации, в которой системой должно быть обеспечено единое для всех процессов состояние памяти (т.е. если потоком какое-либо значение извлекалось из памяти для модификации, измененное значение обязательно должно быть записано в общую память) 168. Директива atomic – определяет точку синхронизации, которую должны достигнуть все процессы для продолжения вычислений (директива должны быть вложена в блок) переменную, доступ к которой (чтение/запись) должна быть выполнена как неделимая операция точку синхронизации, в которой системой должно быть обеспечено единое для всех процессов состояние памяти (т.е. если потоком какое-либо значение извлекалось из памяти для модификации, измененное значение обязательно должно быть записано в общую память) 169. Директива flush – определяет точку синхронизации, в которой системой должно быть обеспечено единое для всех процессов состояние памяти (т.е. если потоком какое-либо значение извлекалось из памяти для модификации, измененное значение обязательно должно быть записано в общую память) точку синхронизации, которую должны достигнуть все процессы для продолжения вычислений (директива должны быть вложена в блок) переменную, доступ к которой (чтение/запись) должна быть выполнена как неделимая операция |