...
Уважаемые коллеги!
Пересылаю вам свои тезисы доклада на конференцию свободного софта и
заодно маленькую статейку.
1. Проблемы открытого софта для Pitecantropus informaticus и
Australopitecus Informaticus
2. развал образования; "информационное" поколение
3. Как приучать к открытому софту тех, кто привык к компьютерам с
детства, но на обезьяньем уровне?
4. http://udsu.ru
5. Непейвода Николай Николаевич
6. Удмуртский государственный университет
10.
В последние два года многие вузы России столкнулись с двумя проблемами:
падение на 70% уровня подготовки абитуриентов и появление на 1 курсах
поколения, которое обычно называется homo informaticus.
Анализируя встречающиеся в литературе характеристики homo informaticus
и сравнивая их с реальным уровнем абитуриентов даже на специальности
информатика в отнюдь не худшем российском университете, моджно
отметить следующее.
1. До уровня homo эти особи не доросли. Они работают с компьютерами
как обезьяны. Мышление их убито, они пытаются угадать желаемый ответ,
как и требуется в тестах.
2. Столкновение с открытым софтом вызывает у них шок. Командная
строка воспринимается как изощренная пытка: "Ты не умствуй, ты пальцем
покажи, куда ткнуть мышой!"
3. Полное неумение читать и клиповое мышление. Ввиду привычки к
копипасту и языку падонков, они не могут даже перепечатать без ошибок
в командную строку строку из учебного пособия, а тем более модифицировать ее
другими параметрами.
4. Неумение писать.
5. Неумение искать релевантную информацию.
Не учитывая все эти особенности, преподавать невозможно. Лишь 1-ый курс
--- то время, когда обезьянолюдей можно превратить хотя бы в
неандертальцев. Поэтому открытый софт и только открытый софт с самого
первого дня --- решение в данной критической ситуации.
Но преподавателям необходимо перестроиться психологически и понять,
что обезьянье поведение --- не столько вина этих молодых ребят,
сколько их беда. Практически весь первый семестр уходит на то, чтобы в
глазах появились искорки разума, а в решениях --- проблески
осмысленности.
Best regards,
N. N. Nepejvoda
...
...
ФИЗИЧЕСКИЕ И ЛОГИЧЕСКИЕ ПРОБЛЕМЫ СУПЕРВЫЧИСЛЕНИЙ
Непейвода Н.Н.
Удмуртский государственный университет, г. Ижевск
тел.: (3412) 91-60-69 e-mail: nnn@udsu.ru
Основное физическое ограничение вычислений общеизвестно: скорость света. Мы будем говорить о некоторых более тонких эффектах.
Одной из главных проблем в организации супервычислений является выделение тепла. Новейший суперкомпьютер МГУ, в частности, наполовину состоит из мощной охлаждающей системы. Эта проблема отнюдь не только техническая, что было показано еще в 60-х гг. прошлого века [1] и анализировалось в ряде работ, наиболее глубокой из которых является статья Р. Меркле [2]. А именно, в принципе выделения тепла можно было бы избежать физически, если бы все действия вычислителя производились на сверхпроводящих элементах и были бы обратимы (второе. как показал Р. Меркле, важнее). Поэтому проведем здесь анализ, принимающий во внимание три вида предупреждений: во-первых, предупреждение В. И. Арнольда о необходимости перепроверять выводы первоуровневых «линейных» моделей более глубокими моделями; во-вторых, предупреждения Р. Меркле [3] об опасностях, подстерегающих теоретиков на пути анализа невозможности; в-третьих, принципы взаимодействия теоретика и практика из [4].
Прежде всего, как отметил В. И. Арнольд, практические выводы из моделей первого уровня и моделей второго уровня зачастую прямо противоположны. Во-вторых, повышение уровня модели не всегда означает ее большую адекватность. Известный элементарный пример: с точки зрения качественного анализа нулевое приближение к синусу гораздо лучше, чем все остальные приближения n-го порядка через ряд Тейлора. Функция x.0 (постоянная) периодична, ограничена и даже имеет наименьшую абсолютную погрешность на всей оси.
На самом деле этот пример подчеркивает еще одну тонкость: исключительно важно, какой род моделей использовать. Приближения рядом Фурье для синуса сойдутся исключительно быстро и дадут правильную качественную картину.
Следующий пример из информатики показывает, насколько могут быть обманчивы даже исключительно точные теоретические оценки. Рассмотрим тупейшее возражение, высказываемое полуобразованными специалистами против необходимости владения нестандартными стилями и языками программирования: «Все, что угодно, можно запрограммировать на C++» (в зависимости от вкусов специалиста, вместо С могут стоять .Net, Java и даже FORTRAN). На него есть столь же тупой и убийственный ответ: «Все, что угодно, можно запрограммировать на машине Тьюринга». Хотя против демагогии чаще всего эффективна лишь демагогия (иначе толпа станет кричать: «Мужик дело говорит, а против него какие-то умствования пытаются плести!»), данный ответ не менее демагогичен, чем высказанный аргумент. В самом деле, время и расход памяти, требуемые машиной Тьюринга, несравнимы с временем и памятью, требуемыми компьютером приличной архитектуры, а именно на такой компьютер ориентирован С++. Да и длина самого текста программы станет неизмеримо больше. Перенося это на многостилевое программирование, можно заметить, что уже есть практические примеры программ, сокращающихся в десятки раз при использовании подходящего инструмента, причем совершенно без потерь эффективности. А человеческий ресурс (в том числе и время высококвалифицированного программиста на написание и отладку программы) — ныне один из самых дорогих и дефицитных.
А теперь рассмотрим все это строго, математически, теоретически. Длина программы, вычисляющей данный алгоритм --- одна из известных мер сложности алгоритмов: сложность по Колмогорову. Для нее есть потрясающая теорема, говорящая, что какой бы алгоритмический язык мы ни взяли, выигрыш в сложности будет не более фиксированной раз и навсегда для данного языка константы, то есть даже линейного сокращения длины программы не достичь. В таких случаях необходим анализ не только выводов, но и доказательства такой теоремы. Проанализировав доказательство, мы видим, что оно практически сводится к следующему. Напишите модуль интерпретатора для нестандартного языка и примонтируйте его к тексту программы. Вот вы и запрограммируете все на С++. Если же эффективности не хватает, постройте транслятор, а не интерпретатор, и проиграете лишь константу по времени и памяти.
Беда лишь в том, какова эта константа? Хватит ли у вас сил создать и поддержать такой транслятор? И не лучше ли воспользоваться накопленным знанием, чем отвергать его? Словом, мы имеем великолепную иллюстрацию принципа из [4]: «Если теоретик говорит, что это не имеет никакого значения, практик должен понимать его следующим образом: это имеет первостепенное значение».
Теперь возникает второй вопрос: а адекватна ли чисто алгоритмическая сложность для оценки программных объектов в информатике? Ответ на него требует глянуть на программу более системно.
Программа --- не последовательность команд для большого калькулятора. Она создается, поддерживается и используется людьми. Людям свойственно ошибаться. И отличить ошибку от «новой возможности» можно, лишь анализируя свойства, которым должна удовлетворять программа. Ввиду специфики нынешних языков программирования, этим свойствам вообще нет места в тексте программы (они являются с точки зрения программы и программиста призраками [5]). Точно таким же призраком является для специалиста, заинтересованного в результатах работы информатиков, созданная программа. Для него, наоборот, реальна задача. Поэтому нужно переходить к моделям, учитывающим взаимодействие между программой и создателем, между создателем и свойствами будущей программы. Одним из таких классов моделей являются конструктивные логики.
Ввиду полного отсутствия логического образования у подавляющего большинства специалистов нашей страны, логика отождествляется ими с вычислениями по таблицам истинности либо (кажется более умным, а на самом деле неизмеримо глупее) с языком Prolog. Под неклассической логикой, соответственно, автоматически понимается логика с многими логическими значениями вместо двух стандартных. Но многие логики вообще не апеллируют к понятию логического значения.
Л. Брауэр первым обратил внимание, что вся стандартная математика и логика направлена на обоснование. а не на построение. Он же показал, что логика построений другая --- конструктивная. А. Н. Колмогоров дал интерпретацию конструктивной логики как исчисления задач. Формула представляет собой задачу; доказательство --- ее решение. Само понятие истинности формулы заменяется на понятие реализуемости.
Это гораздо более тонкое и адекватное приближение к задаче программирования, и конструктивная логика зарекомендовала себя как мощное средство анализа концепций программирования и методов программирования. Конечно же, как всякое сильное и объективное средство анализа, оно приводит к весьма жестоким и печальными выводам, а это большинству не нравится. Гораздо легче требовать от теоретика: «Я тут нашел решение, а вы прочитайте над ним свою молитву и окропите его вашей математической святой водичкой, чтобы я мог ссылаться, что оно обосновано».
В конце XX века выяснилось, что конструктивные логики существеннейшим образом зависят от основного ресурса, принимаемого во внимание при решении задач. Исходная конструктивная логика Брауэра оказалась нацеленной на чистое знание. Логики времени и денег противоречат и ей, и друг другу, причем коренным образом. Попытки соединения в одной конструкции кусков (не изолированных и замкнутых в себе модулей, а именно переплетающихся кусков!) конструкций с несовместимой конструктивной логикой приводят к неистощимому источнику ошибок, которые ведут себя как головы гидры: одну срубишь, две отрастают (так называемые концептуальные противоречия, см. [5]).
В связи с этим проанализируем суперпроизводительные вычисления с точки зрения конструктивной логики. Поскольку каждое действие должно быть обратимым, при решении наших задач мы можем использовать лишь обратимые функции. Наиболее общей математической структурой, описывающей обратимые функции, являются группы. Таким образом, действия супервычислителя должны составлять группу.
Соответственно, в конструктивной логике супервычислений (реверсивная логика [6]) формула реализуется элементом группы. Эта же группа используется и для представления состояний вычислителя. И основная логическая связка конструктивной логики --- импликация --- задается определением: А ВАВ.
Анализируя получившуюся логику, получаем, что она противоречит другим конструктивным логикам. В ней две нестандартные связки: последовательная некоммутативная конъюнкция и превентивное отрицание (отмена действия). Дизъюнкции нет, поскольку соответствующей операции нет в категории групп. Каждая формула реализуема тогда и только тогда, когда реализуемо ее превентивное отрицание (поскольку действия обратимы, возможность решения задачи означает и возможность отменить ее решение).
Соответственно, реверсивная логика задает еще один стиль программирования, присущий, в частности, супервычислителям и несовместимый с обычными стилями программирования. Отличительными особенностями этого стиля являются следующие три: функциональное программирование с самого начала (изоморфизмы группы представляют собой группу), возможность отменить любую последовательность действий из уже произведенных и отсутствие условных операторов.
Проанализировав еще раз с точки зрения реверсивной логики результаты. накопленные в реверсивных вычислениях за 30 лет их развития, видим. что неявно такие ограничения уже были, но не осознавались. Условные операторы моделируются при помощи Toffoli Gate и Fredkin Gate, которые увеличивают требуемую память.
Все это высвечивает причины повторяющихся неудач с созданием сверхпроводящих суперкомпьютеров. Как и во всех грубо концептуально противоречивых системах, каждое решение весьма ограничено, а при попытке его расширения и модификации выявляются неожиданные ошибки. Так что основная причина неудач здесь — наличие «священных коров» и недостаточно комплексный подход. Проектировать такой процессор как традиционную машину нельзя.
Таким образом, приходим к принципиальному архитектурному выводу. Процессор для супервычислений должен состоять из реверсивной вычислительной мельницы и управляющего традиционного процессора. В процессе супервычислений нужно жесточайшим образом минимизировать количество условных решений. Бинарная архитектура вычислительной мельницы, видимо, одна из худших для суперпроцессора. Стоит вспомнить наши отечественные разработки по небинарным компьютерам (в частности, по вычислениям в остаточных классах). Далее, даже не было попыток ввести в реверсивный суперкомпьютинг функциональное программирование, а здесь нужно поддерживать его с самого начала, и стоит вспомнить опыт возрождаемой сейчас советской системы Эльбрус.
И, наконец, существующие методы программирования не позволят создать эффективные программы для суперкомпьютеров. Их нужно с самого начала программировать по-другому. И учить для них нужно студентов с самого начала, потом переучить не удастся!
Эти последние выводы на самом деле относится к еще одному классу вычислений. важных для суперкомпьютеров: к параллелизму. Все современные «промышленные» языки программирования основаны на предположении о последовательных вычислениях. В итоге программа с самого начала пишется последовательно, а затем уже изуродованную программу пытаются более или менее успешно «распараллелить». Удается это лишь в самых примитивных случаях, в частности, для параллельных программ даже нет наметок никакого функционального программирования.
Более того, разные стили программирования по-разному относятся к параллелизму. Если логически рассмотреть структурное программирование и традиционное функциональное программирование, то здесь видим еще одну беду современного программирования, которая, как обычно, тихонько сидит в уголке, пока мы не занимаемся действительно сложными задачами, а тут уж поднимается во весь рост и начинает мстить за пренебрежение.
В интуиционистской конструктивной логике, соответствующей структурному и функциональному программированию, параллелизм отсутствует в принципе, потому что исходная форма программы, получающейся из доказательства, совершенно нейтральна по отношению к тому, будет ли она исполняться последовательно или при помощи &-параллелизма. В ней фиксируются лишь абсолютно необходимые для сохранения логических взаимосвязей зависимости между операторами. А когда мы записываем такую программу на нелогичных нынешних языках, мы неизбежно вставляем в нее подпорки.
Видимые подпорки менее вредны, но часть из них невидимые. Например. в традиционном языке мы вынуждены писать x:=1;y:=2, зафиксировав порядок действий, который абсолютно неважен в данном случае, и здесь вставлена невидимая подпорка. Масса невидимых подпорок мешает естественному исполнению программы на подходящем для нее процессоре.
А самая большая гадость в том, что для других стилей соотношение между программой и параллелизмом абсолютно другое. В автоматном стиле параллелизм явный (автомат и совокупность взаимодействующих автоматов --- логически разные сущности). В событийном он неизбежно присутствует с самого начала. В сентенциальном ситуация более похожа на структурное, но естественен V-параллелизм.
Литература
1. Landauer R., Irreversibility and heat generation in the computing process // IBM Journal of Research and Development – 1961 -- vol. 5 -- pp. 183-191.
2. Merkle R.C.. Helical logic // Nanotechnology -- 1996 -- №7 — pp. 325—339.
3. Merkle R.C. That''s impossible: how good scientists reach bad conclusions, April 2001. URL: http://www.zyvex.com/nanotech/impossible.html (дата обращения: 18.01.2009).
4. Непейвода Н. Н. Математик и прикладник: о взаимо(не)понимании.// Вестник Удмуртского государственного университета — 2007 --- № 1 --- с. 251-268.
5. Непейвода Н. Н., Скопин И.Н.. Основания программирования. – М.: РХД, 2004. – 670 с.
6. Непейвода Н. Н. Реверсивная логика. // Логические исследования. вып. 15. -- М.: Наука, 2008.-- с.36—41.
...
E-mail: vlad.rykov@gmail.com
|
