Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров



Скачать 87.91 Kb.
Дата25.07.2014
Размер87.91 Kb.
ТипПрограмма дисциплины


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

«Национальный исследовательский университет

«Высшая школа экономики»
Факультет БИЗНЕС-ИНФОРМАТИКИ

Отделение ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ



Программа дисциплины
Распределенные системы
для направления 010400.68 «Прикладная математика и информатика» подготовки магистров

Автор Воронцов К.В. (voron@forecsys.ru)




Рекомендована секцией УМС

«Прикладная математика

и информатика»
Председатель

__________________ Кузнецов С.О.

«_____» __________________ 20____ г.


Одобрена на заседании базовой кафедры

Яндекса


Зав. кафедрой

__________________ Ройтберг М.А.

«_____» __________________ 20____ г.


Утверждена УС факультета

бизнес-информатики


Ученый секретарь

__________________ Фомичев В.А.

« ____» ___________________20____ г.





Москва


Пояснительная записка

Автор программы


Воронцов К.В., д.т.н.

Требования к студентам


Изучение курса «Распределенные системы» требует предварительных знаний по теории вероятностей и прикладной теории алноритмов.

Аннотация


Дисциплина «Распределенные системы» предназначена для подготовки магистров 010400.68 – Прикладная математика и информатика.

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

Программа курса предусматривает лекции (32 часа) и практические занятия (32 часа).

Учебные задачи курса


Цель курса – научить студентов основам теории параллельных вычислений методике разработки параллельных программ.

В результате изучения дисциплины «Распределенные системы» студенты должны:



  • знать основные модели параллельных вычислений;

  • уметь использовать основные технологии параллельного программирования

  • познакомиться с платформой для проведения распределенных вычислений ApacheHadoop

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

Тематический план дисциплины «Распределенные системы»





Название темы

Всего часов по дисциплине

Аудиторные часы

Самосто-ятельная работа

Лекции

Сем. и практика занятия

1

Тема 1.Введение в распределенные вычисления

50

10

10

30

2

Тема 2.Модель вычислений MapReduce и платформа ApacheHadoop

52

10

10

32

3

Тема 3.Обзор технологий распределенного программирования

60

12

12

36




Итого

162

32

32

98


I.Источники информации

Основная литература


1. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб: БХВ-Петербург, 2002.  608 с. 

2. J. Dean, S. Ghemawat. MapReduce: simplified data processing on large clusters

Communications of the ACM.Volume 51 Issue 1, January 2008. Pages 107-113

3. Эндрю Таненбаум, Мартин ванСтеен Распределенные системы. Принципы и парадигмы. — Санкт-Петербург: Питер, 2003

4. Tom White. Hadoop: The Definitive Guide. O'Reilly Media. 2009. 528 p.

Дополнительнаялитература


  1. Cheng-Tao Chu; Sang Kyun Kim, Yi-An Lin, YuanYuan Yu, Gary Bradski, Andrew Ng, and KunleOlukotun. "Map-Reduce for Machine Learning on Multicore". NIPS 2006.

  2. Colby Ranger; RamananRaghuraman, ArunPenmetsa, Gary Bradski, and Christos Kozyrakis. "Evaluating MapReduce for Multi-core and Multiprocessor Systems". HPCA 2007

II.Формы контроля и структура итоговой оценки


• Текущий контроль: - письменная аудиторная контрольная работа (60 мин.) и индивидуальноедомашнее задание.

• Итоговый контроль – письменный экзамен (120 мин.)

Формирование оценки.

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

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

Отекущий = 0,6·Ок/р+ 0,4·Оаудиторная;

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



Оитоговый1 =0,4·Озач +0,6·Отекущий·

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



Отекущий = 0,6Одз+ 0,4·Ок/р;

Результирующая оценка за итоговый контроль в форме экзамена выставляется по следующей формуле, где Оэкзамен – оценка за работу непосредственно на экзамене:



Оитоговый =0,4·Оэкзамен +0,3·Отекущий +0,3·Оитоговый1.

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


Таблица соответствия оценок по десятибалльной и системе зачет/незачет


Оценка по 10-балльной шкале

Оценка по 5-балльной шкале

1

Незачет

2

3

4

Зачет

5

6

7

8

9

10


Таблица соответствия оценок по десятибалльной и пятибалльной системе


По десятибалльной шкале

По пятибалльной системе

1 – неудовлетворительно

2 – очень плохо

3 – плохо


неудовлетворительно – 2

4 – удовлетворительно

5 – весьма удовлетворительно



удовлетворительно – 3

6 – хорошо

7 – очень хорошо



хорошо – 4

8 – почти отлично

9 – отлично

10 - блестяще


отлично – 5


III.Программа дисциплины «Распределенные системы»


Тема 1. Введение в распределенные вычисления
Многопроцессность (concurrency), асинхронность и параллелизм. Процессы и потоки, способы взаимодействия. Основы многопоточного программирования с общей памятью на примере языка Java. Недетерминированность, состояние гонки. Синхронизация доступа к общим данным, взаимное исключение, блокировка. Взаимная блокировка. Условная синхронизация потоков. Циклический барьер. Конфигурируемый пул потоков. Модель взаимодействия процессов, основанная на асинхронном обмене сообщениями, на примере языка Scala.

Цели применения параллельных вычислений. Пути достижения параллелизма. Классификация вычислительных систем. Системы с общей разделяемой памятью. Системы с распределенной памятью. Модель параллельного алгоритма, граф “операции-операнды”, расписание вычислений. Теоретические оценки времени выполнения параллельного алгоритма. Характеристики параллельных алгоритмов: ускорение, эффективность, стоимость. Теоретические оценки максимально достижимого ускорения, законы Амдала и Густавсона-Барсиса. Масштабируемость параллельного алгоритма, функция изоэффективности. Оценка коммуникационной сложности параллельных алгоритмов.

Принципы разработки параллельных алгоритмов. Декомпозиция исходной задачи на подзадачи. Типовые структуры алгоритмов. Функциональный параллелизм. Парадигма “разделяй и властвуй”. Геометрическая декомпозиция. Алгоритмы на рекурсивных структурах данных. Конвейерная обработка. Координация на основе событий. Анализ информационных зависимостей между подзадачами. Выбор вычислительной платформы. Масштабирование параллельного алгоритма. Распределение подзадач между исполнителями. Примеры параллельных алгоритмов: матричные вычисления, сортировка, алгоритмы на графах, задача N тел, рендеринг изображений.

Основная литература


1. Воеводин В. В., Воеводин Вл. В. Параллельныевычисления. — СПб: БХВ-Петербург, 2002. — 608 с. 

2. J. Dean, S. Ghemawat. MapReduce: simplified data processing on large clusters

Communications of the ACM.Volume 51 Issue 1, January 2008. Pages 107-113

3. Эндрю Таненбаум, Мартин ван Стеен Распределенные системы. Принципы и парадигмы. — Санкт-Петербург: Питер, 2003

4. Tom White. Hadoop: The Definitive Guide. O'Reilly Media. 2009. 528 p.

Дополнительнаялитература


  1. Cheng-Tao Chu; Sang Kyun Kim, Yi-An Lin, YuanYuan Yu, Gary Bradski, Andrew Ng, and KunleOlukotun. "Map-Reduce for Machine Learning on Multicore". NIPS 2006.

  2. Colby Ranger; RamananRaghuraman, ArunPenmetsa, Gary Bradski, and Christos Kozyrakis. "Evaluating MapReduce for Multi-core and Multiprocessor Systems". HPCA 2007

Тема 2.Модель вычислений MapReduce и платформа ApacheHadoop


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

Архитектура платформы ApacheHadoop и ее основные элементы – распределенная файловая система HDFS и реализация модели MapReduce. Интерфейс прикладного программирования и общие принципы реализации приложений для Hadoop на языке Java на примере задачи подсчета частоты встречаемости слов в тексте. Процесс установки Hadoop на локальной машине, с последующей компиляцией и запуском приложения. Принципы реализации функций map и reduce на языках, отличных от Java. Работе с данными и запуск приложений на учебном кластере, выбору значений параметров запуска заданий и отладке приложений.

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

Основная литература


1. Воеводин В. В., Воеводин Вл. В. Параллельныевычисления. — СПб: БХВ-Петербург, 2002. — 608 с. 

2. J. Dean, S. Ghemawat. MapReduce: simplified data processing on large clusters

Communications of the ACM.Volume 51 Issue 1, January 2008. Pages 107-113

3. Эндрю Таненбаум, Мартин ванСтеен Распределенные системы. Принципы и парадигмы. — Санкт-Петербург: Питер, 2003

4. Tom White. Hadoop: The Definitive Guide. O'Reilly Media. 2009. 528 p.

Дополнительнаялитература


  1. Cheng-Tao Chu; Sang Kyun Kim, Yi-An Lin, YuanYuan Yu, Gary Bradski, Andrew Ng, and KunleOlukotun. "Map-Reduce for Machine Learning on Multicore". NIPS 2006.

  2. Colby Ranger; RamananRaghuraman, ArunPenmetsa, Gary Bradski, and Christos Kozyrakis. "Evaluating MapReduce for Multi-core and Multiprocessor Systems". HPCA 2007

Тема 3. Обзор технологий распределенного программирования


Другие технологии, входящие в состав платформы Hadoop или основанных на ней.Высокоуровневый язык PigLatin, реализованный поверх модели MapReduce и призванный упростить описание процедур обработки данных.Распределенная система хранения данных HBase, особенности ее архитектуры, отличия от реляционных СУБД, области применения.Открытая реализация поисковой машины Nutch и использование модели ~MapReduce в работе Nutch. Библиотека Mahout, содержащая масштабируемые реализации алгоритмов машинного обучения на базе Hadoop.

Цели построения и виды распределенных систем. Способы взаимодействия распределенных процессов. Обмен сообщениями. Удаленные вызовы процедур. Пространство кортежей. Распределенная общая память. Современные технологии распределенного программирования: CORBA, ZeroCIce, ApacheThrift, Java RMI, Web-сервисы. Знакомство с языком Erlang. Проблемы построения распределенных систем, способы повышения отказоустойчивости. Консенсус в распределенной системе, алгоритм Paxos.

Требования к параллельным программам. Типовые шаблоны параллельных программ: SPMD, loopparallelism, master-worker, fork-join. ЗнакомствостехнологиямиOpenMP, MPI, Java Fork-Join Framework, Parallel Extensions для .NET.

Основная литература


1. Воеводин В. В., Воеводин Вл. В. Параллельныевычисления. — СПб: БХВ-Петербург, 2002. — 608 с. 

2. J. Dean, S. Ghemawat. MapReduce: simplified data processing on large clusters

Communications of the ACM.Volume 51 Issue 1, January 2008. Pages 107-113

3. Эндрю Таненбаум, Мартин ванСтеен Распределенные системы. Принципы и парадигмы. — Санкт-Петербург: Питер, 2003

4. Tom White. Hadoop: The Definitive Guide. O'Reilly Media. 2009. 528 p.

Дополнительнаялитература


  1. Cheng-Tao Chu; Sang Kyun Kim, Yi-An Lin, YuanYuan Yu, Gary Bradski, Andrew Ng, and KunleOlukotun. "Map-Reduce for Machine Learning on Multicore". NIPS 2006.

  2. Colby Ranger; RamananRaghuraman, ArunPenmetsa, Gary Bradski, and Christos Kozyrakis. "Evaluating MapReduce for Multi-core and Multiprocessor Systems". HPCA 2007

IV.Методические указания студентам


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

Автор программы: _____________________________/ <Воронцов К.В.> /




Похожие:

Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconПрограмма дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconПрограмма дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconПрограмма дисциплины Компьютерная лингвистика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconПрограмма дисциплины Автоматическая обработка текстов для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconРабочая программа дисциплины Прикладная статистика Направление подготовки 010400 Прикладная математики и информатика
Учебная дисциплина «Прикладная статистика» относится к вариативной части профессионального цикла (Б. 3) по направлению 010400 «Прикладная...
Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconПрограмма дисциплины Алгоритмы и структуры данных для направления 010400. 62 «Прикладная математика и информатика» подготовки бакалавров

Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconПрограмма дисциплины «Дискретная математика»
...
Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconПрограммы подготовки бакалавра по направлению 010400 прикладная математика и информатика
Код и наименование направления подготовки, наименование программы 010400. 62 «Прикладная математика и информатика», профиль «Прикладная...
Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconБакалаврской программы 010400. 62 «Прикладная математика и информатика» реализуемой на кафедре №31 «Прикладная математика»
Код и наименование направления подготовки, наименование программы: 010400. 62 «Прикладная математика и информатика»
Программа дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров iconПрограмма дисциплины математический анализ и обыкновенные дифференциальные уравнения. Дополнительные главы для направления 010500. 62 «Прикладная математика и информатика»
Для направления 010500. 62 – «Прикладная математика и информатика» подготовки бакалавра. 2 курс
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org