лекция 10

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

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

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

Параллельные вычисления существуют в нескольких формах:

1.Параллелизм на уровне битов. Эта форма параллелизма основана на увеличении размера машинного слова. Увеличение размера машинного слова уменьшает количество операций, необходимых процессору для выполнения действий над переменными, чей размер превышает размер машинного слова. (8, 16, 32, 64 – битные процессоры).

2.Параллелизм на уровне инструкций. Программа — это, по существу, поток инструкций, выполняемых процессором. Но можно изменить порядок этих инструкций, распределить их по группам, которые будут выполняться параллельно, без изменения результата работы всей программы. Данный приѐм известен как параллелизм на уровне инструкций. Классический пример пятиступенчатого конвейера на RISC-машине (IF = выборка инструкции, ID = декодирование инструкции, EX = выполнение инструкции, MEM = доступ к памяти, WB = запись результата в регистры). Современные процессоры имеют многоступенчатый конвейер команд, например процессор Pentium 4 имеет 35-тиступенчатый конвейер.

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

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

Естественно, увеличение плотности размещения транзисторов на кристалле возможно лишь за счет сокращения размеров самих транзисторов. До какой степени можно уменьшать размеры транзисторов? Уже сейчас размеры отдельных элементов транзисторов в процессорах сопоставимы с атомарными.

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

создать транзистор или подобный ему элемент с размером менее 10-8 см (диаметр атома водорода) и рабочей частотой более 1015 Гц (частота атомных переходов). А потому, хотим мы того или нет, неизбежен тот день, когда закон Мура придется перестанет работать (если, конечно, его в очередной раз не подкорректируют).

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

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

нанотехнология.

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

Вклассической физике величины могут изменяться равномерно и непрерывно, принимая любые значения. Физика микромира дискретна: у величин есть ряд фиксированных значений, которые они могут принимать. Если пытаться вообразить такую ситуацию в макромире, то можно представить, например, что предметы имеют температуру, которая выражается только целым числом градусов. То есть 10, 20, 31, 36 градусов - может быть, а вот 36,6 - просто невозможно. Нагревать и охлаждать предметы можно, но при этом температура будет скакать туда-сюда сразу на градус. Примерно таким свойством обладают многие характеристики микромира.

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

Другим удивительным свойством фотонов, электронов и иных микрочастиц является то, что они могут проявлять свойства как частиц, так и волн (поэтому мы можем говорить и о том, что свет - это электромагнитная волна, и о частицах света - фотонах).

Частицы-волны обладают недоступной для макрообъектов способностью "находиться в нескольких местах одновременно". Говоря точнее, описать

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

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

Когда мы объекты не измеряем, они ведут себя еще хуже. Если квантовая система

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

Известным наглядным примером является мысленный эксперимент, называемый "кот Шредингера": в закрытый ящик помещены живой кот, емкость с ядовитым газом и радиоактивное ядро. Если ядро распадается, оно приводит в действие механизм, который открывает емкость с газом и тем самым убивает кота. Вероятность того, что ядро распадется за час, - 50 процентов. Через час кот в ящике жив с вероятностью 50 процентов. С точки зрения квантовой механики, пока ящик закрыт, кот находится в суперпозиции двух состояний («скорее жив, чем мертв»; «скорее мертв, чем жив». В тот момент, когда наблюдатель открывает ящик, он видит, жив кот или мертв.

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

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

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

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

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

В 1980 году советский математик Юрий Манин задумался: а нельзя ли посмотреть на задачу с другой стороны и, раз квантовая система может то, чего не могут наши компьютеры, использовать эти ее возможности с пользой, а именно - заставить ее производить вычисления? Сначала на идею не обратили внимания, пока через год эту же мысль не опубликовал Нобелевский лауреат Ричард Фейнман. И в 2001 - появился

первый прототип квантового компьютера.

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

Ячейкой хранения информации в квантовом компьютере является квантовый бит (quantum bit, qubit), или кубит. Это квантовая частица, которая может иметь два состояния (одно принимается за 0, другое - за 1).

Физически кубит может быть устроен по-разному:

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

атомное ядро или электрон, имеющий два возможных значения спина - вниз и вверх,

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

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

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

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

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

Алгоритм Шора имеет большое значение для современной криптографии. Если удастся создать достаточно мощные квантовые компьютеры, то часть использующихся систем шифрования с открытым ключом (например, RSA) станет уязвима для взлома: для подбора тайного ключа необходимо разложить открытый на простые множители. При достаточно длинном ключе даже современным суперкомпьютерам на это нужны сотни лет, а вот перед квантовыми он не устоит.

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

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

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

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

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

прогнозирования, распознавания образов, управления и др.

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

Нейронные сети не программируются в привычном смысле этого слова, они обучаются. Возможность обучения — одно из главных преимуществ нейронных сетей перед традиционными алгоритмами. Технически обучение заключается в нахождении коэффициентов связей между нейронами. В процессе обучения нейронная сеть способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что в случае успешного обучения сеть сможет вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке, а также неполных и/или «зашумленных», частично искаженных данных.

Практическое приложение - предсказание финансовых временных рядов

Входные данные — курс акций за год.

Задача — определить завтрашний курс.

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

На полученном наборе обучается сеть с 3 входами и одним выходом:

входы: курс на дату минус 1 день, минус 2 дня, минус 3 дня,

выход: курс на дату.

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

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

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

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

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

ДНК-компьютер — вычислительная система, использующая вычислительные возможности молекул ДНК. В 1994 году Леонард Адлеман, профессор университета Южной Калифорнии, продемонстрировал, что с помощью пробирки с ДНК можно весьма эффектно решать классическую комбинаторную «задачу о коммивояжере» (кратчайший маршрут обхода вершин графа). Классические компьютерные архитектуры требуют множества вычислений с опробованием каждого варианта.

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

Проблемы, возникающие при этом:

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

Существует проблема масштабирования задачи.

Биокомпьютер Адлемана отыскивал оптимальный маршрут обхода для 7 вершин графа. Но чем больше вершин графа, тем больше биокомпьютеру требуется ДНК - материала.

Было подсчитано, что при масштабировании методики Адлемана для решения задачи обхода не 7 пунктов, а около 200, масса количества ДНК, необходимого для представления всех возможных решений превысит массу нашей планеты.

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

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