Золотой билет - Страница 51

Квантовое будущее

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

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

Что же может послужить очередным толчком в развитии вычислений? Какие еще грандиозные вычислительные задачи требуют нашего внимания? Читайте дальше – и вы все узнаете.

Глава 10. Будущее вычислений

Я уже смирился с тем, что проблему равенства P и NP ожидает довольно унылая перспектива. Думаю, классы все же не равны – правда, в этой жизни доказательства я уже не увижу. И, думаю, нам не придется жить в совершенном мире из второй главы, хотя полностью исключать такую возможность, конечно, нельзя. Вероятно, пройдет не один десяток (а может, и не одна сотня) лет, прежде чем тайна P и NP будет раскрыта.

«P против NP» – не просто хитрая математическая головоломка. Даже будучи неразгаданной, она дает нам некий каркас для размышлений и подсказывает способы борьбы с важнейшими вычислительными задачами. Приведем наиболее актуальные на сегодняшний момент проблемы.

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

• Большие данные. Каждый день в мире появляются тонны новых данных. Взять хотя бы интернет или многочисленные научные эксперименты… Как работать с такими огромными объемами информации? Как искать, структурировать, анализировать, делать прогнозы?

• Интернет вещей. Почти каждый современный человек пользуется компьютерными сетями – к примеру, общаясь на Facebook или отправляя письмо по электронной почте. Дело идет к тому, что скоро все произведенные человеком предметы, будь то одежда или лампочки для чтения, тоже станут частью сети. Как ориентироваться в мире с таким количеством связей?

Независимо от того, равны классы P и NP или не равны, изучение проблемы P и NP поможет выработать подход к решению данных вопросов.

Параллельные вычисления

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

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

И все же транзисторов на кристалле становится все больше и больше. Зачем это нужно? Чтобы запускать сразу несколько вычислений одновременно: распараллеливая работу, мы значительно уменьшаем время решения задач.

Возьмем для примера суперкомпьютер IBM по имени Уотсон, который в феврале 2011 победил в американской телевикторине «Jeopardy!». Уотсон состоит из 90 серверов IBM Power 750 по 4 процессора Power 7 в каждом. Один процессор Power 7 содержит восемь более мелких процессоров, или ядер, и может параллельно вести сразу восемь вычислений. В итоге получается 32 ядра в одном сервере и 2880 во всем компьютере, так что Уотсон может запускать 2880 процессов одновременно. Неудивительно, что он анализирует варианты ответа быстрее, чем соперники, и успевает нажать кнопку миллисекундой раньше! Впрочем, если производительность компьютеров продолжит расти по закону Мура, то уже через несколько лет 2880 параллельных процессов покажутся нам сущим пустяком; в ближайшие десятилетия могут появиться компьютеры с миллионами и даже миллиардами ядер.

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

К проблеме равенства P и NP тоже пытались применить распараллеливание. Помните Веруку Солт? Девочку из книги «Чарли и шоколадная фабрика», о которой мы говорили в первой главе? Верука очень хотела найти золотой билет, а все билеты были спрятаны в шоколадных плитках. Ее отец – владелец ореховой фабрики – распараллелил задачу, разделив шоколадки между всеми своими рабочими, которых у него было более ста. Так почему бы не сделать то же самое с задачами из класса NP? Например, распределить все потенциальные клики между разными ядрами и даже компьютерами? Иногда время перебора действительно может заметно сократиться – например, с нескольких недель до нескольких часов, однако некоторые NP-задачи и после распараллеливания останутся такими же неприступными. Будь у нас даже миллион компьютеров с триллионом ядер, каждое из которых выполняет квинтиллион операций в секунду, – для поиска клики размера 50 среди 20000 жителей Королевства все равно потребовалось бы в гугол раз больше лет, чем живет наша вселенная (а гугол, как уже говорилось, – это единица и сто нулей). В мире, где можно распараллелить любой процесс, вопрос о равенстве P и NP по-прежнему актуален.