Пленарные доклады.

Гипервычисления и фундаментальные научные исследования

П.А. Правильщиков,
к.т.н., в.н.с.,

ИПУ  РАН, pavelp@ipu.ru, г. Москва

Вычислительная техника внедрилась почти во все области жизни и деятельности человека и, конечно же, в науку. Известно, что только современная и, прежде всего, фундаментальная наука позволяет двигаться по инновационному пути развития таким передовым государствам как США, Япония, Германия, Англия, Франция, Италия и др. Инновационный путь развития должен стать национальной идеей и для России. Наша страна давно пытается уйти от сырьевой направленности своей экономики, чтобы окончательно не превратиться в придаток нефтяной  трубы для развитых стран. Но современная наука требует больших инвестиционных затрат, в частности, затрат на приобретение и развитие вычислительной техники (ВТ) и соответствующего ПО, на создание локальных хранилищ данных и вычислительных сетей. Постоянно  растущий, постоянно  изменяющийся прогресс современной науки требует слияния больших объёмов сложных данных с незаурядными вычислительными возможностями. И фундаментальная наука здесь не является исключением. Задачи фундаментальной науки требуют сложнейших  вычислений[1] и больших ресурсов памяти. Например, данные, которые анализируются в современных моделях изменения климата, уже включают миллионы значений температуры и миллионы измерений для ливневых дождей, а также многие тенденции в загрязнении воздуха, параметры парниковых газов, влияние сельскохозяйственного производства на изменение климата. К вычислителям с быстродействием во многие терафлопы и даже в петафлопы в секунду следует добавить необходимость в собственном локальном хранилище (архиве) данных порядка 10-100 петабайт. При этом возникает необходимость работы с такими сетями, которые позволяют осуществить перемещение много терабайтных файлов своевременным и безопасным способом.  В данной работе исследованы названные вопросы и, прежде всего, вычислительные возможности нового направления в развитии вычислительной техники (ВТ) — гипервычислений.

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

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

           2.  Разработка и развитие теории (выдвижение теоретических и рабочих  гипотез).

           3.  Анализ экспериментальных результатов (например, анализ треков в экспериментах по столкновению
                элементарных частиц в ускорителях).

Степень интеграции этих компонент облегчает процесс исследования ранее неподатливых проблем во многих научных областях. Например, в области математики, такой неподатливой проблемой является центральная проблема (ЦП) дискретной математики, имеющая не только теоретическое, но и большое практическое значение. Напомним, что центральной проблемой (ЦП) современной дискретной математики является вопрос о равенстве или неравенстве класса P и класса NP: P = NP, либо P ¹ NP, где P — это класс задач, для которых найдены эффективные алгоритмы решения, NP — это класс задач для которых такие алгоритмы не найдены [1-4] [2]. В физике, например, такой неподатливой проблемой является обнаружения бозона Хиггса (или, как её ещё иногда называют, «частицы бога»). Неподатливые проблемы существуют в химии, фотонике, генетике, молекулярной биологии, медицине и др. научных дисциплинах. Фундаментальные вычисления в значительной степени могли бы способствовать решению подобных  проблем.    

Поэтому интеграции трёх перечисленных выше компонент фундаментальных  исследований должна соот-вествовать  интеграция трёх, можно сказать, технических  элементов фундаментальных  вычислений:

1.          Собственно высокопроизводительные вычисления.  

2.          Хранение данных.

3.          Работа с вычислительными сетями.

     Если эти три элемента не будут сбалансированы, высокопроизводительные вычисления окажутся не эффективными при решении современных и будущих научных задач. Говоря о хранении данных и работе с сетями, мы имеем в виду то, что  использование и перемещение  данных для решения фундаментальных задач добавляет другой уровень сложности в требованиях к созданию вычислительных систем и вычислений с их использованием.
     Тогда фундаментальные вычисления будут интегрироваться прямо в эксперименты, анализируя данные непосредственно в процессе проведения натурных экспериментов. Это необходимо сделать для того, чтобы усовершенствовать  сам эксперимент, изменяя, адаптируя его к поставленным целям в реальном времени. Это необходимо сделать так же и для того, чтобы позволить ввести человеческую интуицию в процесс проведения самого эксперимента, делая его, таким образом, очень динамичным. Когда вычислительные (расчётные) модели работают совместно с натурными экспериментами, то каждая  компонента  может быть усовершенствована и исправлена на основе  их обоюдного  взаимодействия.

     Таким образом, интеграция вычислений с другими методами исследований повышает производительность исследователей  и, что особенно важно, открывает новые перспективы, новые  направления поиска. Во многих случаях в науке исследования были ограничены доступными вычислительными мощностями и доступным объёмом хранения данных. Именно эти ограничения, а не размерность  изучаемой проблемы, чаще определяли способности моделирования по её решению или по сложности выполняемого анализа. Здесь уместно вспомнить, что в начале семидесятых годов в нашем институте на каждую лабораторию выделялся диск, объёмом в 7,25 мегабайта, что, конечно, сильно тормозило проведение вычислительных экспериментов в области САПР, в области технической диагностики и в других областях computer science. Можно высказать некоторые опасения, что история может повториться с использованием ресурсов суперкомпьютера, установленного недавно в нашем институте.     
        По мере увеличения доступных вычислительных мощностей и увеличения объёма доступной оперативной памяти, по мере увеличение ёмкости доступной дисковой памяти исследования в фундаментальных областях науки могут быть расширены. Они не будут далее сдерживаться вычислительными ресурсами. Так, например, многие научные проекты включают в себя большие объёмы цифрового моделирования физических явлений, которые либо невозможно, либо слишком дорого осуществить в режиме натурного эксперимента. Приведём примеры таких фундаментальных вычислений.

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

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

3. Следующим примером генерации большого объема данных в процессе этапа компьютерного моделирования может служить моделирование столкновения черных дыр, выполненное в США в Национальном научно-исследовательском институте вычислительных средств для энергетики. (National  Energy  Research Scientific  Computing  Facility —NERSC). Была осуществлена имитация столкновения двух черных дыр. Имитировались также и  возникшие при этом столкновении гравитационные волны — см. рис. 1.  Так как гравитационный волновой сигнал, который может быть обнаружен интерферометрами в гравитационном поле, настолько слаб, что очень близок к уровню шумов в этих приборах, имитированные волновые рисунки — важные инструментальные средства для физической интерпретации данных.  Оказалось, что компьютерная  графика необходима и важна для фундаментальных исследований, также как и для САПР, и CALS-технологий.

 

Figure 1

рис.  1

Используемый программный код в процессе такой имитации выполняет прямой поиск  корней уравнений общей теории относительности Эйнштейна, которые являются системой спаренных нелинейных дифференциальных уравнений специального вида. Их решение сводится к решению систем алгебраических уравнений с миллионами уравнений.
     Следовательно, требования к вычислительным ресурсам и ресурсам памяти только для выполнения самых элементарных  процессов моделирования огромны. Такие процессы моделирования  ограничены, как доступным объёмом памяти, так и производительностью процессоров сегодняшних суперкомпьютеров.

     В computer  science и науках об управлении существуют свои фундаментальные проблемы, для решения которых  требуются огромные  вычислительные  мощности, связанные,  например, с решением логических уравнений (SAT-проблема), с поиском кратчайшего пути в графе (например, при решении задачи трассировки [5]), с проблемой  решение криптографических задач и задач  ускорения компьютерной графики. Опыт решения таких задач на суперкомпьютерах с механизмом  массового  параллелизма, в которых в качестве элементарного вычислительного модуля  используется процессор, приводят к ограниченному  успеху.

Так на основе опыта решения логических уравнений  проявились следующие проблемы вычислительных  систем с механизмом массового параллелизма (в вычислительных экспериментах использовалась система, содержащая 30 тыс. процессоров — см. [6]):

1)       проблема уменьшения повторной работы; 

2)       проблема “ленивых” процессоров, которые в данный момент не загружены работой;

3)       проблема связности, т.е. проблема высокого отношения числа операций межпроцессорного обмена данными к числу булевых вычислений (обычно это отношение равно 1).

      Учитывая приведённые недостатки современных суперкомпьютеров (или кластеров) с механизмом массового параллелизма в 2004 г. (см. [7]) была предложена новая архитектура процессоров-ускорителей с механизмом гипермассового параллелизма[3]. В качестве элементарного вычислительного модуля в таком ускорителе используется небольшое комбинационное устройство (КУ): блок Bj пересечений. В настоящее время разработаны различные варианты блока Bj , различающиеся между собой реализуемыми функциями и содержащие от 10 до 46 транзисторов. Для сравнения напомним, что мощные процессоры, являющиеся элементарным вычислительным модулем в кластерах с механизмом массового параллелизма, содержат многие миллионы и даже миллиарды транзисторов[4]. Но число таких блоков Bj пересечений в ускорителях с механизмом гипермассового параллелизма может  исчисляться  сотнями  миллионов,  миллиардов  и  даже триллионов.   

     Естественно, идея использования процессоров-ускорителей с различной архитектурой возникла в головах разных учёных и инженеров. Так, в 2006 г. автора неожиданно пригласили на семинар, организованный компаниями Microsoft, Intel, AMD и одним из московских институтов. На этом семинаре один из представителей компании AMD заявил буквально следующее: «Возможности однородной многопроцессорности и многоядерности по повышению производительности современных компьютеров к 2010 году будут исчерпаны. После этого наступит эра процессоров-ускорителей. Мы в AMD никогда не занимались такими ускорителями, но в сложившихся условиях мы вынуждены заняться их разработкой».

    Известно, что в области ВТ единственной постоянной величиной, можно сказать, константой, является                                  постоянное изменение, постоянное движение вперёд. Сегодняшние самые мощные компьютеры никогда не бывают достаточно мощными для проблем, которые встанут завтра. Например, до второй половины 2008 г. лидером TOP500, т.е. списка самых мощных компьютеров мира был суперкомпьютер Blue Gene/L (IBM), содержащий 130 000 процессоров общего типа (процессоров Power 6). Его производительность равна 280 терафлопс. Во втором полугодии 2008 г. новым лидером, новым чемпионом TOP500 стал компьютер Roadrunner (IBM), содержащий 32 000 процессоров. Его производительность оценивается в 1,05 петафлопс. Возникает вопрос: почему кластер Blue Gene/L, число процессоров которого в 4 раза превосходит число процессоров в суперкомпьютере Roadrunner, обладает производительностью в 3 раза меньшей, чем суперкомпьютер Road-runner?

    Ответ на это вопрос достаточно прост: из 32 000 процессоров компьютера Roadrunner 16 000 процессоров — это процессоры ускорители. В качестве таких процессоров-ускорителей инженеры из IBM выбрали видеоускорители, разработанные той же корпорацией IBM для созданной ими игровой приставки Playstation-3. Всю черновую работу по перемалыванию огромных массивов чисел выполняют процессоры-ускорители с высокой степенью параллелизма. Ими управляют оставшиеся 16 000 процессоров общего типа, которые кроме функций управления видеоускорителями также осуществляют завершающую обработку информации, перед тем как вывести её на дисплеи суперкомпьютера. И хотя в новом чемпионе TOP-500 используются видеоускорители от игровой приставки, суперкомпьютер Roadrunner решает совсем не игрушечные задачи. Он стоит 110 млн. долларов и предназначен для решения уравнений математической физики, т.е. для моделирования цепных реакций на начальной стадии ядерных взрывов. Это позволяет американцам гарантировать исправное техническое состояние национальных ядерных боеприпасов, не проводя натурных экспериментов, т.е. не осуществляя выборочных взрывов ядерных бомб. Естественно, он может решать и другие задачи. Таким образом, появление суперкомпьютера Roadrunner ознаменовало начало новой эры в области вычислительной техники — эры процессоров-ускорителей. Начало этой эры предсказывали многие специалисты и, в частности, специалисты компании AMD.

     Процессор-ускоритель, который разрабатывается у нас в институте [5], имеет совершенно иную архитектуру (на первом слайде приведено и название доклада, и выбранный нами эпиграф, и название проекта РФФИ). Его архитектура полностью не похожа на архитектуру видеоускорителей. По нашему мнению, степень параллелизма (т.е. максимальное число Nmax одновременно выполняемых операций по обработке данных за один такт или за небольшой промежуток времени, например, 1 секунду) у нашего ускорителя с механизмом гипермассового параллелизма может быть значительно выше. Теоретическим аналогом процессора-ускорителя, разрабатываемого в ИПУ РАН, является идеальный генератор тестов (ИГТ), с неограниченным числом блоков пересечений, реализующих элементарные операции пересечения. Элементарная операция пересечения является основной операцией исчисления кубических комплексов (D-исчисления).

      Таким образом, теоретическое основание нашего ускорителя состоит из трёх компонент.
      1) Исчисление кубических комплексов и параллельно-последовательные D-алгоритмы. Исчисление кубических комплексов и последовательные D-алгоритмы были разработаны ещё в 1966 г. американским математиком Джоном Паулем Ротом. Для  краткости Рот  назвал своё  исчисление D-исчислением. 

      2) Идеальный генератор тестов (ИГТ) — теоретический аналог ускорителя с механизмом гипермассово-го параллелизма [7]. Подобные аналоги относятся к классу моделей вычислений, которые в последнее время называют гипермашинами. Гипермашины появились относительно недавно[6] и существенно отличаются от таких теоретических аналогов современных компьютеров, как машина Тьюринга. Некоторые математики утверждают, что гипермашины могут решать такие задачи и реализовать такие вычисления, которые не могут  быть выполнены на машинах Тьюринга[7]. Вычисления, которые могут быть реализованы с помощью таких моделей, называют гипревычислениями (hypercomputation). Напомним, что под гипервычислениями понимаются такие вычисления, при выполнении которых за фиксированный интервал времени может быть выполнено неограниченное число вычислительных операций.
    Появление таких моделей вычислений обусловлено тем, что в 90-е годы ХХ века были разработаны и даже стали коммерчески доступны новые виды компьютеров: ДНК-компьютеры, нейрокомпьютеры и аналоговые нейросети, оптические и квантовые компьютеры. В настоящее время существует около десяти подобных моделей. К ним, например, относятся: машина Зенона, аналоговая нейросеть Х. Зигельман [8], квантовый компьютер с неограниченным числом кубитов [9], релятивисткие модели вычислений [10] и др. Заметим, что многие из гипермашин в настоящее время не могут быть реализованы физически. Но среди них есть и физически реализуемые машины. Одной из таких моделей вычислений или одной из таких гипермашин является и наш ИГТ.

    Говоря о нереализуемых в настоящее время моделях вычислений, следует заметить, что когда-то то же самое можно было сказать и о классической машине Тьюринга. Когда-то и она считалась физически нереализуемой. Это в настоящее время она является, по мнению многих специалистов, теоретическим аналогом (математической моделью) однопроцессорных ЭВМ. Статья Тьюринга с описанием его машины появилась ещё в 1935 г. В то время не существовало никаких однопроцессорных ЭВМ. На самом деле, машина Тьюринга была моделью вычислений, которые выполняет очень терпеливый, очень аккуратный, методичный и педантичный математик. Он имеет в своём распоряжении неограниченную по длине полосу бумаги и неограниченное число карандашей. При этом математик, выполняя некоторую механическую процедуру, не использует свою интуицию, не использует знание и понимание математических зависимостей и закономерностей.

      3) Третьей компонентой теоретического обоснования нашего процессора-ускорителя с механизмом гипер-массового параллелизма является закон сохранения перебора, выведенный автором из дискретного аналога теоремы Нётер [2]. Простейшая формулировка оригинала, т.е. известной «физической» теоремы Нётер такова: «Для всякой физической системы, уравнения, движения которой могут быть получены из вариационного принципа, каждому непрерывному однопараметрическому преобразованию, оставляющему вариационный функционал инвариантным, отвечает один дифференциальный закон сохранения».  Под дифференциальным законом понимается закон сохранения в дифференциальной форме, например, закон сохранения энергии E:   
     Многие физики считают, что теорема Нётер является лучшим методом получения законов сохранения. Аналоги теоремы Нётер, доказанной для классической (аналитической) механики, существуют в различных научных дисциплинах: в квантовой механике, в теории элементарных частиц, в термодинамике, аэродинамики и др. Автором сформулирован и доказан дискретный аналог теоремы Нётер для движения, которое происходит в дискретном лабиринте [7].  Из дискретного аналога теоремы Нётер были выведены разные формы закона сохранения перебора для последовательных и параллельно-последовательных D-алгоритмов, которые и выполняют этот перебор при решении разных задач, в частности, при решении логических уравнений. Решение логических уравнений, как и решение алгебраических и дифференциальных уравнений, имеет важное практическое значение, например, для такой стратегически важной для электронной промышленности и вычислительной техники задачи как верификация БИС, для решения задач криптографии и логического управления.

     Закон сохранения перебора для одного из типов параллельно-последовательных алгоритмов (в [7] показано четыре типа таких алгоритмов, но на самом деле их существует значительно больше) имеет чрезвычайно простую полиномиальную форму:

Pr  £  (R + 1)  вдеп,                                                                  (1)

где R — число рангов в логическом уравнении или в логической сети КУ. Величина Pr перебора измеряется в таких единицах как вдеп (временная дискретная единица перебора).  Величина Pr = R + 1 в случае построения тестов и диагностического моделирования, когда используется алфавит A классического D-исчисления (A = {0, 1, ~, D, D', E, E'}) — см. [7]. В нашем случае, когда для решения логических уравнений используется алфавит A* = {0, 1, ~} величина Pr = R.

     Подчеркнём, что выражение (1) является полином первой степени и это означает, что такая фундаментальная проблема, как ЦП современной дискретной математики, решена (решена относительно временной сложности). Это объясняется тем, что для решения ЦП достаточно, как утверждается в [1], решить хотя бы одну из известных NP-полных задач, например, SAT-проблему. Последняя формулируется как проблема выполнимости для логических формул или уравнений. Показав, что решение логических уравнений может быть осуществлено в соответствии с (1) за полиномиальное время мы решили SAT-проблему относительно временной сложности. Для полного решения ЦП современной дискретной математики следует показать, что SAT- проблема может быть решена и с пространственной сложностью меньшей, чем «проклятие размерности», т.е экспонента 2n. Такое решение SAT-проблемы существует и существует соответствующий параллельно-последовательный D-алгоритм. Это решение SAT-проблемы с описанием этого D-алгоритма будет в ближайшее время опубликовано в журнале «Автоматика и телемеханика». Заметим, что указанный парал-лельно-последовательный D-алгоритм использует один из вариантов метода эффективных наборов, разработанный и опубликованный автором ещё в 1975 г. Метод эффективных наборов опирается на принцип сжатия пространства поиска решения (пространства входных воздействий для КУ).
   Но реальный процессор-ускоритель с механизмом гипермассового параллелизма и с ограниченным объёмом активной памяти будет работать, естественно, несколько медленнее, чем ИГТ с неограниченным объёмом такой памяти. Но с увеличением размерности практических задач всегда существует возможность повысить тактовую частоту и увеличить объём активной или процессирующей памяти ускорителя. В связи с этим подчеркнём, что всякий реальный компьютер (вычислитель или калькулятор) работает с конечными числами. Например, максимальное положительное число, которое можно ввести в современный инженерный калькулятор Casio fx-991MS равно 9,999999769×1099,99999999. Если попытаться ввести число 10100, то будет получено сообщение «Math ERROR». Попутно заметим, что калькуляторы подобного типа распродаются миллионными тиражами в год. Это значит, что потребность в них реально существует.

    Если взять более дорогой калькулятор, например, калькулятор Windows в ноутбуке (например, в ноутбуке SONY VAIO VGN-SZ7RVN/X), то этот калькулятор в ноутбуке позволяет работать с большими, но всё-таки конечными числами. Максимально возможное число, которое можно ввести в калькулятор Windows равно 1043429 . При попытке ввести число 1043430  калькулятор ноутбука выдаёт сообщение «Недопустимый аргумент функции». В этом и заключается принцип компьютерного финитизма: всякий реальный компьютер работает с конечными числами[11].  При этом следует учитывать принцип историзма: с развитием вычислительной техники числа, которые могут обрабатывать компьютеры, неуклонно возрастают. Но уже сегодня в математике (в частности, в теории чисел) и в методологии математики встречаются огромные числа, большие, чем число 1043429.  Например, в теории чисел известно число Скьюза  —  (имеется в виду второе число Скьюза, обозначаемое в математике символом Sk2, которое иногда округляют до числа ). В методологии математики приводится число Бирюкова .

     Конечно, хотелось бы иметь «числовые телескопы», которые могли бы обрабатывать и такие огромные числа. Но для записи, например, числа   в обычной десятичной форме не хватит никакого материального носителя, если учесть, что число элементарных частиц в наблюдаемой сегодня Вселенной оценивается физиками как число 1087. 
    То же самое можно сказать и о числе переменных в логических уравнениях. Конечно, хотелось бы иметь возможность решить любое логическое уравнение, например, содержащее 1000 и более независимых переменных. Но существуют ли практические (можно сказать, инженерные) задачи, которые приводят к таким уравнениям?  Пока таких практических задач, по крайне мере, не много, если они вообще существуют. Вряд ли сейчас существует большая потребность в создании таких компьютеров, которые могли бы решать подобные уравнения. Будущие компьютеры с новой архитектурой и на новых физических принципах работы возможно и будут решать такие сложные уравнения, но о них, о таких вычислительных системах мы пока может только мечтать. Пока же в данном докладе предлагается использовать именно процессор-ускоритель с механизмом гипермассового параллелизма, о котором и было рассказано.

    В заключение хотелось бы сказать и об эвристических параллельно-последовательных D-алгоритмах. В на-стоящее время существуют и достаточно известны эвристические последовательные D-алгоритмы. Необходимо создавать и эвристические параллельно-последовательные D-алгоритмы, которые смогут быстро находить решение для логических уравнений с большим числом переменных. Такие D-алгоритмы должны также работать на нашем ускорителе с механизмом гипермассового параллелизма. Но, известно, что эвристические алгоритмы не всегда могут найти решение, даже если это решение существует. Поэтому хотелось бы создать полные параллельно-последовательные D-алгоритмы, которые могли бы учитывать и не повторять тот перебор, которые выполнили эвристические алгоритмы. К сожалению, пока создать такие алгоритмы не удалось и не удалось доказать, что создать такие алгоритмы невозможно. В заключение следует привести список задач, которые, по нашему мнению, может решать наш ускоритель. Решение некоторых задач из этого списка уже опубликовано, решение других будет опубликовано в ближайшее время.

1.  Проблема верификации БИС.
2. Проблема построения тестов для аналоговых и дискретных устройств, а также для программ.
3. В сетевом планировании и управлении  задача нахождения критического пути;
4.  Задачи классического оптимального управления (они  сводятся к поиску  оптимальных маршрутов
     в пространстве состояний или фазовом пространстве, если последнее является дискретным).
5.  Задача решения систем алгебраических уравнений.  
6. Задача решения систем  дифференциальных уравнений.
7. Задача решения систем нечётких уравнений.
8.  Криптографические задачи.
9. Задача ускорения компьютерной графики.                               
10. Задачи логического синтеза (например, задача минимизации булевых функций).
11. Задача топологического синтеза (например, задачи построения кратчайшего пути в процессе трассировки). 

Литература

1.                   Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.  М.: Мир, 1982. — 584 с.

2.                   Пападимитриу Х., Стайглиц К.  Комбинаторная   оптимизация. Алгоритмы и сложность.  М.: Мир, 1985. ― 512 стр.

3.                   D. Harel.  Algorithmics: The Spirit of Computing.   Addison-Wesley, Reading, MA, 3rd edition                                                
(With  Y. Feldman), 2004.

4.                   Крупский В.Н. Введение в сложность вычислений. М.: «Факториал пресс», 2006.

5.                   Артамонов Е.И., Правильщиков П.А.  Проблема трассировки и параллельно-последовательные D-алгоритмы на платформе механизма гипермассового параллелизма / Материалы 6-й Международ-ной конференции СAD/CAM/PDM ― 2006.  М.: Институт проблем управления РАН им. В.А. Трапезни-кова, 2006. Стр. 17-20.

6.                   Kravitz S.A., Brayant R.E., Rutenbar R.A. Massively Parallel Switch-Level Simulation: A Fasibility Study // IEEE Trans. on computer-aided design, vol. 10, № 7, 1991, pp 871-874.

7.                   Правильщиков П.А. Закон сохранения перебора и естественный параллелизм D-алгоритмов для по-строения тестов и моделирования в технической диагностике // Автоматика и телемеханика. 2004. № 7. Стр. 156-199.


[1] Эти  сложнейшие вычисления в дальнейшем будем называть фундаментальными  вычислениями.

[2] Различные специалисты по-разному именуют ЦП. Иногда её называют основной или главной задачей современной дискретной математики, а иногда и главной задачей всей математики.  Такой «глобальный замах» (или «глобальный охват») объясняют тем, что математики стараются найти удовлетворительное  решение. Но, как утверждает известный американский математик А. Вигдерсон: «Центральное наблюдение математиков, популяризированное Гильбертом, состоит в том, что "удовлетворительные" решения обычно поставляют (явно или неявно) некоторые процедуры. Если они применены к объекту, то их цель определить (за конечное время), имеет он это свойство или нет». Учитывая то, что до сих пор ЦП оставалась нерешённой, Вигдерсон далее пишет: «… сегодня это сдерживает развитие многих направлений исследования различных структур по алгебре, топологии, геометрии, анализу, логике, и более того, даже тех направлений изучения структур, которые apriori, кажутся, полностью не связанными с вычислениями. Эта вездесущность ЦП делает каждого математика против его воли замаскированным потенциальным учёным в области computer science». 

[3] На самом деле впервые идея создания ускорителя для решения различных задач и, прежде всего, для решения задач построения тестов и диагностического моделирования была впервые опубликована ещё в 1991 г. на семинаре П.П. Пархоменко в лаб. 27 ИПУ РАН (тогда ИПУ АН СССР).

[4] В таком процессоре, как например, процессор Pentium IV (Intel), содержится » 42 млн. транзисторов, в процессоре Centrino (Intel) — 77 млн., Yonah (Intel, 2 ядра) — 151,6 млн., Penryn (Intel, 4 ядра) — 820 млн., Neha-lem (Intel, 8 ядер) — 2,3 млрд. транзисторов.

[5] Проект РФФИ (08-07-00067-а)  «Теоретическое обоснование и разработка  макета  процессора-ускори-теля  на  основе  механизма  гипермассового   параллелизма  для  решения  труднорешаемых  (NP-полных)  задач»

[6] Относительно недавно, в 2007 г. Главный исследовательский центр  Великобритании при участии ряда английских университетов  (среди них и Кембриджский университет) организовали сайт, на котором представлены исследования в области  гипервычислений.  На этом сайте выложена большая библиография по данному вопросу. См. в Интернет сайт по адресу:    http://www.hypercomputation.net/bib_by_date.html

[7]  См., например, обзор  Ord T.  Hypercomputation: computing more than the Turing machine.

[8] Математик Хава Зигельман, разработавшая такую модель вычислений как аналоговые нейросети,  защитила докторскую диссертацию в университете Хайфы в Израиле (её называют новой Эмми Нётер).  В настоящее время она руководит большой лабораторией  в знаменитом Массачусетском технологическом институте  США. Лаборатория  Зигельман  выполняет заказы оборонного ведомства  DARPA и разрабатывает реальные нейросети, реализуя физически ту самую модель её аналоговых нейросетей. 

[9] В феврале 2007 г. канадская компания D-wave провела презентацию первого коммерчески доступного квантового компьютера Orion.  Компьютер Orion содержит всего 16 кубит, и его производительность сравнивают с производительностью серверных процессоров. По внешнему виду компьютер  Orion напоминает большой домашний двухдверный холодильник , которым он, по сути, и является, так как сцеплённое или перепутанное состояние, лежащее в основе его кубит, может существовать только при криогенных температурах. После презентации, которая вызвала небывалый ажиотаж в СМИ, представители  D-wave сделали ряд опрометчивых заявлений. В частности они пообещали, что в 2008 г. реализуют мечту американского математика П. Шора, создавшего первый квантовый алгоритм факторизации. П. Шор подсчитал, что квантовый компьютер, имеющий 1000 кубит, приблизительно за 7 секунд может взломать любой из существующих ныне паролей, чем немало взволновал руководителей  спецслужб всего мира. Сегодня завершается 2009 г. и стало известно,  что компания D-wave уже 9 месяцев проводит испытание и тестовое диагностирование нового квантового компьютера. Но число кубит в этом компьютере равно всего лишь 28.  

[10] В начале сентября 2009 г. на Азорских островах состоялась первая конференция по релятивистким гипер-вычислениям. Последние основаны на утверждениях теории относительности и теории чёрных дыр о том, что во Вселенной существуют области, в которых ход времени заметно отличается от земного течения времени. Такие области физики называют «кротовыми норами». Если взять пару одинаковых  часов и поместить одни в Москве, а другие часы в некоторой кротовой норе, а затем через интервал времени, который равен одному часу в Москве, возвратить часы из кротовой  норы, то возвращённые часы будут показывать время, отличающееся от московского времени  на 100 лет. Это означает, что в кротовой норе прошло 100 лет, тогда как в Москве всего лишь один час.  Если вместо часов в кротовую нору поместить компьютер, который начал решать сложную задачу в Москве, а затем через час московского времени извлечь этот компьютер обратно из норы, то окажется, что за один час по московскому времени компьютер решил задачу, на решение которой требовалось 100 лет московского времени.   

[11] Заметим, что в математике известен ультрафинитизм, как разновидность такого математического направления как ультраинтуиционизм. Сторонники ультрафинитизма не используют в своих работах понятие бесконечности.