Золотой билет. P, NP и границы возможного - Лэнс Фортноу Страница 42

В 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 по-прежнему актуален.

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

Класс задач, которые можно быстро решить в параллельном режиме, тоже получил обозначение: его назвали NC, или Nick’s Class, – в честь пионера параллелизации алгоритмов Николаса Пиппенджера. Если P = NP (так ли это, мы пока не знаем), то задачи, для которых существует эффективный алгоритм, в параллельном режиме решаются в разы быстрее. А если NP = NC (что, опять-таки, пока находится под большим вопросом), то и любую переборную задачу из NP тоже можно решить практически мгновенно, распараллелив вычисления по разным машинам и ядрам, – т. е. мир, где NP = NC, еще более совершенен, чем тот, где P = NP. И хотя классы NC и NP вряд ли окажутся равны, отношения между ними не менее загадочны, чем отношения между P и NP.