Слайд 3Cache coherency protocol
Write through
Промах чтения (загрузка строки)
Попадание чтения (-)
Промах записи (запись в
![Cache coherency protocol Write through Промах чтения (загрузка строки) Попадание чтения (-)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-2.jpg)
память)
Попадание записи(обновление кэша, зпись в память)
Слайд 4MESI
Invalid
Shared
Exclusive
Modified
![MESI Invalid Shared Exclusive Modified](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-3.jpg)
Слайд 5Нужна коммутация
Перекрестная коммутация с n процессорами и k блоками памяти
![Нужна коммутация Перекрестная коммутация с n процессорами и k блоками памяти](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-4.jpg)
Слайд 7Мультикомпьютеры
Плохая масштабируемость
Конкуренция за доступ к памяти
Send & recieve
![Мультикомпьютеры Плохая масштабируемость Конкуренция за доступ к памяти Send & recieve](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-6.jpg)
Слайд 8Коммуникационные сети
Топология КС –схема рзмещений линий связи и коммутаторов. Часто – неорграф
![Коммуникационные сети Топология КС –схема рзмещений линий связи и коммутаторов. Часто –](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-7.jpg)
(V,E), V – линии связи, E – коммутаторы.
У каждого узла степень, влияющая на отказоустойчивость
Диаметр – большую задержку при передаче пакетов
Пропускная способность- объем данных в секунду
Размерность – количество вариантов перехода.
Слайд 10MPP
Обычные процессоры с дорогим ПО
Огромные объемы IO
Отказоустойчивость
![MPP Обычные процессоры с дорогим ПО Огромные объемы IO Отказоустойчивость](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-9.jpg)
Слайд 11Кластерные компьютеры
Несколько ПК или р\с
Централизованный и децентрализованные
![Кластерные компьютеры Несколько ПК или р\с Централизованный и децентрализованные](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-10.jpg)
Слайд 12Message Parsing Interface
Пользователь создает процессы.
Коммуникаторы
Тип данных
Операции отправки и получения
Виртуальные топологии
![Message Parsing Interface Пользователь создает процессы. Коммуникаторы Тип данных Операции отправки и получения Виртуальные топологии](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-11.jpg)
Слайд 13MPI_Send(буфер, число_элементов, тип_данных, получатель, тег, коммуникатор)
MPI_Recv(&буфер, число_элементов, тип_данных, отправитель, тег, коммуникатор,
![MPI_Send(буфер, число_элементов, тип_данных, получатель, тег, коммуникатор) MPI_Recv(&буфер, число_элементов, тип_данных, отправитель, тег, коммуникатор, &статус)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-12.jpg)
&статус)
Слайд 14Коммуникационные режимы
Синхронный
Буферизация
Стандарт
Готовность
![Коммуникационные режимы Синхронный Буферизация Стандарт Готовность](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-13.jpg)
Слайд 15MPI-2
ДП
Удаленный доступ
Масштабируемый IO
![MPI-2 ДП Удаленный доступ Масштабируемый IO](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-14.jpg)
Слайд 17Производительность
Добавить процессоры, но умно. Нужно соблюдать масштабируемость.
Решетка – хорошо.
![Производительность Добавить процессоры, но умно. Нужно соблюдать масштабируемость. Решетка – хорошо.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-16.jpg)
Слайд 19Пропускная способность растет, время запаздывания – тоже.
В идеале все должно быть
![Пропускная способность растет, время запаздывания – тоже. В идеале все должно быть](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-18.jpg)
неизменно
По факту – как есть.
Слайд 20Как сократить или замаскировать время запаздывания?
Репликация
Упреждающая выборка
Многопоточность
Неблокирующие записи
![Как сократить или замаскировать время запаздывания? Репликация Упреждающая выборка Многопоточность Неблокирующие записи](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-19.jpg)
Слайд 21Disturbed computing
Очень большой, интернациональный слабо связанный гетерогенный кластер
Цель – создать инфраструктуру,
![Disturbed computing Очень большой, интернациональный слабо связанный гетерогенный кластер Цель – создать](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-20.jpg)
которая бы из нескольких организаций сделала бы единую виртуальную организацию.
Многомерная система с одноранговыми узлами.
Куча ресурсов и организаций
Слайд 22Моделирование Системы распределенных вычислений
Уровень инфраструктуры – физ ресурсы, из которых построена система
![Моделирование Системы распределенных вычислений Уровень инфраструктуры – физ ресурсы, из которых построена система](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-21.jpg)
Слайд 23Моделирование Системы распределенных вычислений
Уровень инфраструктуры – физ. ресурсы, из которых построена система
Уровень
![Моделирование Системы распределенных вычислений Уровень инфраструктуры – физ. ресурсы, из которых построена](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-22.jpg)
ресурсов – управление отдельными ресурсами
Слайд 24Моделирование Системы распределенных вычислений
Уровень инфраструктуры – физ. ресурсы, из которых построена система
Уровень
![Моделирование Системы распределенных вычислений Уровень инфраструктуры – физ. ресурсы, из которых построена](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-23.jpg)
ресурсов – управление отдельными ресурсами
Уровень коллективов – исследование, посредничество, управление ресурсами.
Слайд 25Моделирование Системы распределенных вычислений
Уровень инфраструктуры – физ. ресурсы, из которых построена система
Уровень
![Моделирование Системы распределенных вычислений Уровень инфраструктуры – физ. ресурсы, из которых построена](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-24.jpg)
ресурсов – управление отдельными ресурсами
Уровень коллективов – исследование, посредничество, управление ресурсами.
Уровень приложений – приложения, которые совместно используют ресурсы
Слайд 26Безопасность
Однократная регистрация в системе
Нужны стандарты
Global Grid Forum, OGSA
![Безопасность Однократная регистрация в системе Нужны стандарты Global Grid Forum, OGSA](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-25.jpg)
Слайд 27Категрории стандартизированных служб
Службы инфраструктуры (обеспечивают взаимодействие между ресурсами).
Службы управления ресурсами (резервирование
![Категрории стандартизированных служб Службы инфраструктуры (обеспечивают взаимодействие между ресурсами). Службы управления ресурсами](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-26.jpg)
и освобождение ресурсов).
Службы данных (копирование и перемещение данных туда, где они нужны).
Контекстные службы (описание требуемых ресурсов и политик их использования).
Информационные службы (получение информации о доступности ресурса).
Службы самоконтроля (поддержание заявленного качества услуги).
Службы защиты (применение политик безопасности).
Службы управления выполнением (управление потоком задач)
Слайд 31Математика. Квантовый компьютер
Квантовый компьютер — гипотетическое вычислительное устройство, которое путем выполнения квантовых
![Математика. Квантовый компьютер Квантовый компьютер — гипотетическое вычислительное устройство, которое путем выполнения](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-30.jpg)
алгоритмов существенно использует при работе квантовомеханические эффекты, такие как квантовый параллелизм и квантовая запутанность.
Данные в процессе вычислений представляют собой квантовую информацию, которая по окончании процесса преобразуется в классическую путём измерения конечного состояния квантового регистра. Выигрыш в квантовых алгоритмах достигается за счет того, что при применении одной квантовой операции большое число коэффициентов суперпозиции квантовых состояний, которые в виртуальной форме содержат классическую информацию, преобразуется одновременно
Слайд 32Квантовый компьютер
Квантовая запутанность иногда называют квантовой суперпозицией.
Цифровое устройство с аналоговой природой
![Квантовый компьютер Квантовая запутанность иногда называют квантовой суперпозицией. Цифровое устройство с аналоговой природой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-31.jpg)
Слайд 33Бит – н/м единица измерения информации
Может быть только в двух базовых состояниях
![Бит – н/м единица измерения информации Может быть только в двух базовых](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-32.jpg)
- 0 или 1 и находиться только в одном из этих состояний
Слайд 34Бит – н/м единица измерения информации
Может быть только в двух базовых состояниях
![Бит – н/м единица измерения информации Может быть только в двух базовых](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-33.jpg)
- 0 или 1 и находиться только в одном из этих состояний
Квантовый бит – тоже может быть в двух основных состояниях…
Слайд 37При измерениях кубиты случайно переходят в одно из двух собственных состояний( с
![При измерениях кубиты случайно переходят в одно из двух собственных состояний( с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-36.jpg)
вероятностью A^2 и B^2)
Так же кубиты могут быть как-то связаны между собой так, что изменение одного кубита, может повлечь изменение другого.
Ну например если у меня в системе L кубитов, то имеется 2^L независимых состояний. Стало быть L – кубит – 2^L классических состояний.
Фотоны, излированные атомы и ионы
Слайд 40Почему гипотетическое?
необходимо обеспечить высокую точность измерений;
внешние воздействия могут разрушить квантовую систему или
![Почему гипотетическое? необходимо обеспечить высокую точность измерений; внешние воздействия могут разрушить квантовую](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-39.jpg)
внести в неё искажения
Слайд 41RSA
Назовем функцию F односторонней, если:
При известном х мы сможем посчитать F(x)
При известном
![RSA Назовем функцию F односторонней, если: При известном х мы сможем посчитать](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-40.jpg)
y=F(x) мы не сможем посчитать эффективно F(x)
В основе лежит задача факторизации произведения двух больших простых чисел
Шифрование – возведение в степень по модулю большого числа x
Дешифрование – подсчет φ(x) – функции Эйлера
Слайд 42Функция Эйлера
φ(x) = количество чисел от 1 до х-1, взаимно простых с
![Функция Эйлера φ(x) = количество чисел от 1 до х-1, взаимно простых](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-41.jpg)
х
φ(6) =2, φ(25) = 20, φ(11) = 10
Слайд 43Участник Боб и Алиса располагает как открытым ключом так и закрытым ключом
![Участник Боб и Алиса располагает как открытым ключом так и закрытым ключом](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-42.jpg)
Ключ – пара целых чисел
Каждый создает ключ сам.
Закрытый хранится при себе, открытый – в открытом доступе
Для каждого участника открытый и закрытый ключ образуют взаимно-обратные функции.
Слайд 44Выбираются два различных случайных простых числа p и q заданного размера (например,
![Выбираются два различных случайных простых числа p и q заданного размера (например,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-43.jpg)
1024 бита каждое).
Вычисляется их произведение n=p*q, которое называется модулем.
Вычисляется значение функции Эйлера от числа n: φ(n) = (p-1)(q-1)
Выбирается целое число e : 1Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.
Слайд 45RSA
Вычисляется число d, мультипликативно обратное к числу e по модулю то есть
![RSA Вычисляется число d, мультипликативно обратное к числу e по модулю то](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-44.jpg)
число, которое бы делилось в произведении на e на φ(n) то есть d*e делится на φ(n)
Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
Пара (e,n) публикуется в качестве открытого ключа RSA (англ. RSA public key).
Пара (d,n) играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.
Слайд 46Шлем m
Берем (e,n) у Алисы
Берем m, возводим в e и находим остаток
![Шлем m Берем (e,n) у Алисы Берем m, возводим в e и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-45.jpg)
при делении на n\
Отправляем ответ C
Как приняли – берем свой закрытый ключ (d,n)
Возводим ответ C в Степень d и ищем остаток при делении на n
Вуаля.
Слайд 50Алгоритм ШОРА
Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые
![Алгоритм ШОРА Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-49.jpg)
множители), позволяющий разложить число N за время O((log N)^3), затратив O(log N) кубитов
Вероятностный алгоритм
В 1994г Разработан Питером Шором, в 2001г IBM разложила 15 на 3*5
Слайд 51Принцип алгоритма Шора
Пусть M- число , которое хотим взять и разложить на
![Принцип алгоритма Шора Пусть M- число , которое хотим взять и разложить](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-50.jpg)
множители
поиск периода f(x) = p^x (mod M), a = random (Допустим M = 21, а в качестве p выберем 2
Слайд 54Недавний факт про алгоритм Шора
Число 15 разложили с помощью 5 кубитов с
![Недавний факт про алгоритм Шора Число 15 разложили с помощью 5 кубитов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-53.jpg)
вероятностью получения правильного ответа в 50%. И говорят, что
Слайд 55Некоторые другие алгоритмы
Алгоритм Донча-Йожи
Пусть f(a, b…k)- переключательная функция, которая может быть либо
![Некоторые другие алгоритмы Алгоритм Донча-Йожи Пусть f(a, b…k)- переключательная функция, которая может](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1083001/slide-54.jpg)
константой, либо сбалансированной функцией
Нужно определить F – сбалансирована или константа
Нужно 2^(n-1) +1 классических вычислений.