Make your own free website on Tripod.com

В. М. Глушков

О некоторых задачах вычислительной техники и связанных с ними задачах математики

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

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

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

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

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

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

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

Несмотря на то, что применяемые на многих действующих машинах сис­темы памяти на электронно-лучевых трубках в настоящее время сильно устарели, сам принцип коммутирования элементов памяти с помощью управляемого электронного луча далеко не исчерпал своих возможностей. О том, что это действительно так, свидетельствует хотя бы сообщение о разработанной в США так называемой сотовой памяти, использующей для записи и чтения информации весьма тонкий электронный луч в сочетании с системой микроскопических конденсаторов, образуемых металлическими вкраплениями в диэлектрике. Эта система позволяет запоминать до 800 000 двоичных цифр на площади в 1 кв. дюйм и знаменует собой несомненный качественный скачок в возможностях быстродействующих запоминающих устройств. Еще бульшие возможности открывает сочетание ферро-электри­ческих матриц с управляемыми электронными лучами; такое сочетание да­ет возможность разработать относительно простые быстродействующие за­поминающие устройства на многие сотни миллионов двоичных цифр.

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

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

Чрезвычайно большое значение имеет задача повышения надежности электронных цифровых машин. Один из путей решения этой задачи состоит в разработке и использовании более надежных элементов. В связи с этим большую роль призваны сыграть полупроводниковые элементы, решающие одновременно и другую важную задачу — уменьшение габаритов машин и значительное снижение потребляемой ими мощности. Другим, более ин­тересным, с точки зрения математиков, способом повышения надежности является построение надежно работающих схем из сравнительно мало на­дежных элементов. В этом направлении сделаны пока лишь первые шаги. Наиболее простое решение состоит в удвоении или даже утроении основ­ных узлов машины — арифметического устройства, устройств управления, памяти, вводных и выводных устройств. По такому пути пошла, например, американская фирма ИБМ, разработавшая для системы противовоздушной обороны «Сейдж» электронную цифровую машину AN/FSQ‑7. Эта машина имеет 58 000 электронных ламп, все ее основные узлы дублированы. Гораз­до более интересно, но вместе с тем и значительно труднее разработать та­кие схемы, в которых достаточно экономным образом осуществлялась бы автоматическая замена вышедших из строя элементарных ячеек. Возможно, что такие схемы потребуют значительного отступления от принятых в на­стоящее время принципов построения электронных цифровых машин.

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

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

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

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

Более простой, но тоже чрезвычайно важной задачей является разработ­ка рациональных методов радиотехнического расчета уже выбранных схем электронных вычислительных машин в целом (а не только поэлементно) с учетом возможных отклонений от номиналов отдельных элементов схемы (сопротивлений, конденсаторов и т. п.). Ясно, что такой расчет, а тем более расчет, соединенный с синтезом и минимизацией, потребует выполнения огромного числа арифметических и логических операций. В связи с этим возникает задача постановки таких расчетов на универсальные электронные цифровые машины. Решение этой задачи дало бы громадный эффект, на­много сократив сроки разработок новых вычислительных машин и значи­тельно улучшив их качество.

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

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

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

Решение всех этих задач требует дальнейшего развития аппарата мате­матической логики, особенно теории алгоритмов. Представляется целесо­образным, в частности, пересмотр марковской теории нормальных алго­ритмов с точки зрения приближения их к тем алгоритмам, которые факти­чески реализуются в цифровых машинах. Некоторые предварительные со­ображения по этому поводу были недавно высказаны Л. А. Калужниным.

Третья и последняя группа задач, на которой я хочу остановиться, связа­на с использованием уже существующих и перспективных вычислительных устройств. Из задач этой группы особый интерес представляет задача про­граммирования поиска доказательства новых теорем в тех или иных облас­тях математики. Для всякого, кто знаком с возможностями электронных цифровых машин, ясно, что в этой задаче нет ничего принципиально не­возможного, однако при практическом ее решении обнаруживается целый ряд трудностей. Дело, прежде всего, в том, что цепи умозаключений, со­ставляющие доказательство, будучи разложены на элементарные акты, ока­зываются, как правило, весьма длинными, поэтому для бессистемного по­иска требуется огромное число проб, превышающее в сколько-нибудь ин­тересных случаях возможности машины. Задача состоит в том, чтобы отыс­кать и запрограммировать стратегию поиска, позволяющую заранее отбро­сить подавляющее большинство комбинаций, которые заведомо не могут привести к цели. Такая стратегия призвана заменить то, что принято назы­вать математической интуицией. Она должна, разумеется, использовать сильную сторону машин, заключающуюся в более быстром по сравнению с человеком просмотре тех или иных вариантов. Благодаря этому последнему обстоятельству машинная стратегия может быть более грубой, чем обычная человеческая интуиция, и оставлять большую область для окончательных поисков. Это, в свою очередь, позволяет надеяться, что машина может су­щественно расширить возможности человека в области установления новых математических (да и не только математических) фактов. Немного фанта­зируя, можно говорить о том времени, когда плодотворная творческая ра­бота в области математики и других точных наук без применения электрон­ных вычислительных машин будет невозможной, а успех исследования бу­дет определяться прежде всего его искусством в программировании страте­гии научного поиска.

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

Одной из самых актуальных задач является применение электронных цифровых машин для управления производственными процессами. Реше­ние этой задачи на современном этапе требует больших усилий как от ин­женеров, которые должны создать надежные, экономичные и малогабарит­ные типы электронных цифровых машин, так и от математиков, которые должны заняться изучением и программированием процессов управления различными производственными объектами. Особый интерес представляет программирование самонастраивающихся и «самообучающихся» процес­сов. В связи с тем, что управляющие машины являются по существу одно­программными, большое значение приобретает задача построения алгорит­мов для преобразования программ и для их минимизации. Ясно, что для управляющих машин, повторяющих одну и ту же программу десятки, а тем более сотни тысяч раз за короткое время, уменьшение программы даже на одну команду может дать заметный эффект. Минимизация сколько-нибудь сложных программ представляет собою, разумеется, нелегкое дело. Выход из положения и в этом случае может быть найден в постановке задачи ми­нимизации на универсальные электронные вычислительные машины.

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

Появление электронных цифровых машин с программным управлением привело к изменению взгляда на предмет и методы всей вычислительной математики. В состав предмета вычислительной математики теперь естест­венно включать всю теорию программирования, благодаря чему устанавли­ваются прочные связи между вычислительной математикой и математичес­кой логикой. Что же касается методов, то и здесь электронные цифровые машины внесли много существенных изменений: значение методов, ис­пользующих тригонометрические ряды, уменьшилось; наоборот, для ста­тистических методов (методов Монте-Карло) появление электронных циф­ровых машин означало фактически второе рождение; сильно возросло зна­чение итерационных методов. Переоценка всего арсенала средств вычисли­тельной математики с точки зрения возможностей современной вычисли­тельной техники еще не окончилась. Быстрейшее завершение этого процес­са, наряду с разработкой новых методов, наиболее полно использующих возможности электронных цифровых машин, представляет собой важней­шую задачу вычислительной математики на современном этапе. Особенно большое значение имеет разработка новых эффективных методов решения многомерных задач математической физики.

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

Лаборатория вычислительной техники Института математики АН УССР в настоящее время также имеет ряд таких эмпирически найденных методов. Необходимо провести большую и кропотливую работу по сравнению раз­личных методов с точки зрения объема и точности вычислений, а также от­носительной сложности программирования.

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

В заключение кратко остановлюсь на работе в области вычислительной техники и вычислительной математики на Украине. В 1948–1951 гг. под руководством С. А. Лебедева в лаборатории вычислительной техники АН УССР была построена первая в Советском Союзе электронная цифровая машина (МЭСМ). В последующие годы коллективом лаборатории была со­оружена специализированная цифровая машина для решения систем линей­ных алгебраических уравнений и выполнен ряд работ по применению элек­тронных цифровых машин в народном хозяйстве. В настоящее время в ла­боратории разрабатывается большая универсальная цифровая электронная машина «Киев» со скоростью около 5 000 умножений 40-разрядных двоич­ных чисел в секунду и повышенной надежностью. По инициативе Б. В. Гне­денко начата и успешно проводится исследовательская работа в области программирования (программирующая программа, использование статис­тических методов и т. п.). Большая работа по теории чебышевских прибли­жений проводится в Институте математики АН УССР под руководством Е. Я. Ремеза.

Опубликовано в «Украинском математическом журнале», 1957, т. 9, № 4, с. 369–376.