Мультипроцессоры UMA

Мультипроцессоры UMA

Cache coherency protocol
Write through
Промах чтения (загрузка строки)
Попадание чтения (-)
Промах записи (запись в память)
Попадание записи(обновление кэша, зпись в память)

MESI
Invalid
Shared
Exclusive
Modified

Нужна коммутация
Перекрестная коммутация с n процессорами и k блоками памяти

Мультикомпьютеры
Плохая масштабируемость
Конкуренция за доступ к памяти
Send & recieve

Коммуникационные сети
Топология КС –схема рзмещений линий связи и коммутаторов. Часто – неорграф (V,E), V – линии связи, E – коммутаторы.
У каждого узла степень, влияющая на отказоустойчивость
Диаметр – большую задержку при передаче пакетов
Пропускная способность- объем данных в секунду
Размерность – количество вариантов перехода.

Многомерность

MPP
Обычные процессоры с дорогим ПО
Огромные объемы IO
Отказоустойчивость

Кластерные компьютеры
Несколько ПК или р\с
Централизованный и децентрализованные

Message Parsing Interface
Пользователь создает процессы.
Коммуникаторы
Тип данных
Операции отправки и получения
Виртуальные топологии

MPI_Send(буфер, число_элементов, тип_данных, получатель, тег, коммуникатор)
MPI_Recv(&буфер, число_элементов, тип_данных, отправитель, тег, коммуникатор, &статус)

Коммуникационные режимы
Синхронный
Буферизация
Стандарт
Готовность

MPI-2
ДП
Удаленный доступ
Масштабируемый IO

Планирование

Производительность
Добавить процессоры, но умно. Нужно соблюдать масштабируемость.
Решетка – хорошо.

Пропускная способность растет, время запаздывания – тоже.
В идеале все должно быть неизменно
По факту – как есть.

Как сократить или замаскировать время запаздывания?
Репликация
Упреждающая выборка
Многопоточность
Неблокирующие записи

Disturbed computing
Очень большой, интернациональный слабо связанный гетерогенный кластер
Цель – создать инфраструктуру, которая бы из нескольких организаций сделала бы единую виртуальную организацию.
Многомерная система с одноранговыми узлами.
Куча ресурсов и организаций

Моделирование Системы распределенных вычислений
Уровень инфраструктуры – физ ресурсы, из которых построена система

Моделирование Системы распределенных вычислений
Уровень инфраструктуры – физ. ресурсы, из которых построена система
Уровень ресурсов – управление отдельными ресурсами

Моделирование Системы распределенных вычислений
Уровень инфраструктуры – физ. ресурсы, из которых построена система
Уровень ресурсов – управление отдельными ресурсами
Уровень коллективов – исследование, посредничество, управление ресурсами.

Моделирование Системы распределенных вычислений
Уровень инфраструктуры – физ. ресурсы, из которых построена система
Уровень ресурсов – управление отдельными ресурсами
Уровень коллективов – исследование, посредничество, управление ресурсами.
Уровень приложений – приложения, которые совместно используют ресурсы

Безопасность
Однократная регистрация в системе
Нужны стандарты
Global Grid Forum, OGSA

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

Математика

Следствия закона Амдала

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

Квантовый компьютер
Квантовая запутанность иногда называют квантовой суперпозицией.
Цифровое устройство с аналоговой природой

Бит – н/м единица измерения информации
Может быть только в двух базовых состояниях - 0 или 1 и находиться только в одном из этих состояний

Бит – н/м единица измерения информации
Может быть только в двух базовых состояниях - 0 или 1 и находиться только в одном из этих состояний
Квантовый бит – тоже может быть в двух основных состояниях…

При измерениях кубиты случайно переходят в одно из двух собственных состояний( с вероятностью A^2 и B^2)
Так же кубиты могут быть как-то связаны между собой так, что изменение одного кубита, может повлечь изменение другого.
Ну например если у меня в системе L кубитов, то имеется 2^L независимых состояний. Стало быть L – кубит – 2^L классических состояний.
Фотоны, излированные атомы и ионы

Пример

Запутывание

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

RSA
Назовем функцию F односторонней, если:
При известном х мы сможем посчитать F(x)
При известном y=F(x) мы не сможем посчитать эффективно F(x)
В основе лежит задача факторизации произведения двух больших простых чисел
Шифрование – возведение в степень по модулю большого числа x
Дешифрование – подсчет φ(x) – функции Эйлера

Функция Эйлера
φ(x) = количество чисел от 1 до х-1, взаимно простых с х
φ(6) =2, φ(25) = 20, φ(11) = 10

Участник Боб и Алиса располагает как открытым ключом так и закрытым ключом Ключ – пара целых чисел
Каждый создает ключ сам.
Закрытый хранится при себе, открытый – в открытом доступе
Для каждого участника открытый и закрытый ключ образуют взаимно-обратные функции.

Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое).
Вычисляется их произведение n=p*q, которое называется модулем.
Вычисляется значение функции Эйлера от числа n: φ(n) = (p-1)(q-1)
Выбирается целое число e : 1
Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA.

RSA
Вычисляется число d, мультипликативно обратное к числу e по модулю то есть число, которое бы делилось в произведении на e на φ(n) то есть d*e делится на φ(n)
Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
Пара (e,n) публикуется в качестве открытого ключа RSA (англ. RSA public key).
Пара (d,n) играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

Шлем m
Берем (e,n) у Алисы
Берем m, возводим в e и находим остаток при делении на n\
Отправляем ответ C
Как приняли – берем свой закрытый ключ (d,n)
Возводим ответ C в Степень d и ищем остаток при делении на n
Вуаля.

Пример

Коротко о квантовых алгоритмах

Алгоритм ШОРА
Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время O((log N)^3), затратив O(log N) кубитов
Вероятностный алгоритм
В 1994г Разработан Питером Шором, в 2001г IBM разложила 15 на 3*5

Принцип алгоритма Шора
Пусть M- число , которое хотим взять и разложить на множители
поиск периода f(x) = p^x (mod M), a = random (
Допустим M = 21, а в качестве p выберем 2

Недавний факт про алгоритм Шора
Число 15 разложили с помощью 5 кубитов с вероятностью получения правильного ответа в 50%. И говорят, что

Некоторые другие алгоритмы
Алгоритм Донча-Йожи
Пусть f(a, b…k)- переключательная функция, которая может быть либо константой, либо сбалансированной функцией
Нужно определить F – сбалансирована или константа
Нужно 2^(n-1) +1 классических вычислений.