Anatoly Levenchuk (ailev) wrote,
Anatoly Levenchuk
ailev

Categories:

Алгоритмика-2020

Алгоритмика -- это сердце информатики/вычислительного мышления. Алгоритмы изобретаются, их вычислимость проверяется экспериментально (ибо вычисляют их физические вычислители, а физика -- естественная наука, тем самым computer science тоже оказывается экспериментальной, "естественной" наукой).

Мой тезис в том, что алгоритмы многоуровневы, алгоритмика системна "из коробки" (мой заход 2016 года на системную информатику в https://ailev.livejournal.com/1272169.html, а самое свежее рассуждение недельной давности про нахождение в интеллект-стеке выше системного мышления -- https://ailev.livejournal.com/1544639.html, обсуждения курса вычислительного мышления идёт в чате https://t.me/comp_thinking).

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

Исторически развитие compute science рассматривалось как развитие алгоритмики: всё более и более кучерявые вычислители над сравнительно простыми данными. Потом жизнь резко изменилась:
-- в компьютерах медленно, но верно победила концепция RISC (споры на эту тему по факту утихли), и это даже не самый нижний уровень, ибо ниже идёт физика вычислений (а RISC это уже "программирование физики" в предположении, что она у нас классическая "кремниевая").
-- на среднем уровне победили простые алгоритмы обработки десятков тысяч плотно связанных таблиц в корпоративных базах данных (кучерявые реляционные и далее графовые модели данных)
-- на уровне, когда появляется слово "интеллект" (общий вычислитель, который можно настроить для разных типов задач) всерьёз рассматривается "горький урок Sutton" ровно про то же самое: все прорывы связаны с простыми алгоритмами, работающими над всё более сложными и объёмными структурами данных, просто этим алгоритмам в самом низу алгоритмического стека дают достаточную вычислительную мощь.

Развитие многоуровнево: на каком уровне сейчас развивается алгоритмика? Ответ: на всех.

1. Физика вычислителя.
-- Уже заговорили о "квантовом пузыре" (имеется ввиду инвестиционный пузырь), в прошлом году не очень уверенно, а сегодня уже уверенно: https://www.pcmag.com/news/quantum-computing-a-bubble-ready-to-burst. Квантовое превосходство (и тут политика: слово "превосходство"/supremacy некоторым намекает расовое превосходство белых над чёрными -- и хотят это слово заменить!) уже подтверждено, вот вчерашнее сообщение о "квантовом преимуществе" (таки заменили слово!): https://science.sciencemag.org/content/early/2020/12/02/science.abe8770, там преимущество в скорости квантового вычисления -- 10**14 (за 200 секунд работы квантового вычислителя было выполнено вычисление, которое требует 2.5млрд лет работы суперкомпьютера Fugaku). Алгоритмика никогда уже не будет прежней. И деньги в квантовый софт уже пошли, вот Zapata raises $38 million for quantum machine learning, https://venturebeat.com/2020/11/19/zapata-raises-38-million-for-quantum-machine-learning/
-- оптика тоже рулит, вот свежий декабрьский 2020 обзор по оптике в AI, https://www.nature.com/articles/s41586-020-2973-6 (увы, там paywall), но там просто вал новых работ. Скажем, кремниевый оптический передатчик на 100Gbps https://phys.org/news/2020-11-world-all-silicon-optical-transmitter-100gbps.html -- кремний вроде тот же (совместимый техпроцесс с CMOS), но физика другая.
-- и даже питание имеет свои новации, "анти-лазеры" уже доказано, что возможны: https://www.livescience.com/anti-laser-wireless-charging.html. The new anti-laser demonstrated in this experiment accounts for all that, and it receives scattered energy beamed around a space in an unpredictable pattern — still receiving 99.996% of the sent power. The formal term for the method they used is "coherent perfect absorption" (CPA). CPA uses one machine to send power across the room, and another (the "anti-laser") to suck it back up.

2. На уровне "железа" классических машин (это просто "реализация алгоритмов в железе"):
-- побеждает классическая архитектура с RISC, засилье wintel потихоньку заканчивается (например, https://www.zdnet.com/article/risc-v-the-linux-of-the-chip-world-is-starting-to-produce-technological-breakthroughs/ -- As just one example, a recent microprocessor design using RISC-V has a clock speed of 5 gigahertz, well above a recent, top-of-the-line Intel Xeon server chip, E7, running at 3.2 gigahertz. Yet the novel RISC-V chip burns just 1 watt of power at 1.1 volts, less than one percent of the power burned by the Intel Xeon. ... "It's kind of amazing," said David Patterson, a professor at the University of California at Berkeley who helped create RISC-V. "I think IBM mainframes have a 5-gigahertz product that's liquid-cooled, and takes 100 watts" to run).
-- GPU это "новый CPU", тут просто гонка (попытки угадать алгоритмы следующего поколения в AI, и подстроиться именно под них. Хотя NVIDIA делает ставку на то, что не только нейросетями будет живо человечество). Обсуждение железа для задач AI на русском ведётся в чате "железячников" в телеграме, https://t.me/hw_ml. Всякие заметки типа "Амазон сделал кастом чип для обучения нейросетей для своего облака" (декабрь 2020, https://venturebeat.com/2020/12/01/amazon-debuts-trainium-a-custom-chip-for-machine-learning-training-workloads/), скорее всего, будут там.
-- средства выражения алгоритмов (языки программирования): там после десятилетия застоя в нулевых годах наметилась тихая революция: Rust, Go, Julia. Тренд: высокий уровень абстракции при высокой скорости исполнения этих абстракций (в Julia это описывается как "проблема двух языков": чтобы писать быстро и высокоуровнево, как на Python, а исполнять на железе быстро, как на C". Интересно, что лет тридцать назад тренд был "поддержать язык железом" (типа LISP-машины и PROLOG-машины). А сейчас LLVM в компиляторах идёт как отдельный абстрагирующий слой от железа! То есть "железный вычислитель", далее LLVM-вычислитель, далее уже язык как вычислитель.
-- с базами данных идёт сдвиг к GPU ускорителям, "типовые алгоритмы должны уходить в железо": The global GPU Database market size is expected to gain market growth in the forecast period of 2020 to 2025, with a CAGR of 16.0% in the forecast period of 2020 to 2025 and will expected to reach USD 279 million by 2025, from USD 153.8 million in 2019. Это из https://www.orbisresearch.com/reports/index/global-gpu-database-market-2020-by-company-regions-type-and-application-forecast-to-2025, эти алгоритмы уходят в железо, что очень похоже на "мейнфреймы, команды которых микропрограммируются" (тоже несколько уровней вычислителей)
-- Intel не прекратила баловаться с нейроморфными архитектурами, вот https://venturebeat.com/2020/12/03/intel-showcases-neuromorphic-computing-innovations-at-labs-day/, Loihi solutions required 75 times less power than conventional mobile graphics cards without perceivable losses in performance. In fact, in a study accepted to the 2020 Conference on Robot Learning, the Rutgers team concluded that Loihi could learn tasks with 140 times lower energy consumption compared with a mobile graphics chip. Основная проблема как раз с алгоритмикой для этой архитектуры, и софтом с этой алгоритмикой. Но тут трудно говорить о "другой физике". Архитектура другая, но вот физика (пока в нейроморфной архитектуре не задействуют мемристоры) та же, что и у классики -- и там тоже два уровня, используется микропрограммирование (https://en.wikichip.org/wiki/intel/loihi).

3. На уровне "обычных алгоритмов" -- это предыдущая алгоритмика. Думать тут нужно о томах Кнута: алгоритмы сортировок последовательностей, генерации случайных чисел, обхода графов, удаления невидимых линий в трёхмерной графике и т.д.. Тут полно результатов, только они сегодня не так интересны. Например, Гугль сказал, что его квантовый компьютер решает за 200 секунд задачу, которую суперкомпьютер IBM решает за 10тыс. лет. IBM предложила новый алгоритм, и он решает на суперкомпьютере эту задачу за 2.5 дня (https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/). Но эти алгоритмы мало кого волнуют сегодня, это стало уделом узких спецов -- знание алгоритмики сегодня идёт в плюс программистам, но по большому счёту оно уже не считается фронтирным, рок-н-ролл ушёл в другие места. Да, кого-то ещё может взволновать крошечное (после 44 лет исследований!) улучшение алгоритма нахождения кратчайшего пути коммивояжёра -- https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/, но по большому счёту такие достижения вдруг перестали считаться интересными.

4. А вот "универсальные алгоритмы" (варианты The Master Algorithm, как он описан у Pedro Domingos в книжке https://yadi.sk/i/TxIe5tc1SWekdQ) как раз очень бурно развиваются. Именно про них был горький урок Sutton, именно им нужно добавлять вычислительную мощь. Вот только некоторые из результатов этой "новейшей алгоритмики":
-- по факту замена алгоритмов свёрточных нейронных сетей алгритмами архитектруры работы с вниманием -- трансформерами, впрямую использовали эту архитектуру для работы с изображениями и получили SoTA: https://ai.googleblog.com/2020/12/transformers-for-image-recognition-at.html. Теперь и CNN, и RNN заменены на трансформеры, появившиеся в 2017 (и появилось много вариантов, типа Reformer, эффективный вариант от января 2020 -- https://ai.googleblog.com/2020/01/reformer-efficient-transformer.html)/
-- алгоритмический прорыв в алгоритмах сворачивания белков, AlphaFold, 50 лет стояла эта задача в биологии, и оказалась решена (существенно раньше, чем в любых прогнозах. Так же, как задача победы человека в игре Го), https://deepmind.com/blog/article/alphafold-a-solution-to-a-50-year-old-grand-challenge-in-biology
-- алгоритмический прорыв в решении уравнения Шрёдингера, https://syncedreview.com/2019/09/18/quantum-chemistry-breakthrough-deepmind-uses-neural-networks-to-tackle-schrodinger-equation/
-- алгоритм NVIDIA, сокращающий требуемый для видеоконференций трафик вдесятеро, https://syncedreview.com/2020/12/02/nvidia-neural-talking-head-synthesis-makes-video-conferencing-10x-more-bandwidth-efficient/
-- ... и этот поток нескончаем. Универсальные алгоритмы -- это универсальные аппроксиматоры. Если их научиться обучать, то можно решить множество самых разных задач (в том числе, конечно, инженерные расчёты, химические расчёты, физические расчёты и т.д.). Вот, например, обзор расчётов турбулентности методами машинного обучения: https://www.tu-ilmenau.de/fileadmin/media/tsm/papers/Schumacher2020_3.pdf. Но рассчитывать этими методами можно очень много чего, практически всё! Можно ли из этих расчётов потом вынуть математическую модель, "физическую модель"? Да, таких алгоритмов тоже полно, этим не занимаются только ленивые. Вот пример: https://arxiv.org/abs/2009.11500, Discovery of Governing Equations with Recursive Deep Neural Networks или https://arxiv.org/abs/2012.00428 по попыткам подбирать уравнения покомпактнее -- таких работ множество, "перевести данные в какие-то короткие формулы" скоро будет уделом стандартных библиотек. Я бы выделил вот эту работу: https://arxiv.org/abs/2011.11981, там уравнения в частных производных открываются генетическим алгоритмом из редких и зашумленных данных. Законы Кеплера легко открываются из данных, не нужно ждать сотни лет. Неполноприводное движение тоже обеспечивается сегодня выучиванием алгоритмов этого движения, а не программированием.

Мой пойнт в том, что алгоритмика многоуровнева и стремительно развивается. И пока непонятно, чему учить в алгоритмике
-- "простых людей" (алгоритмика в составе трансдисциплины вычислительного мышления -- мой интерес. Думаем об абстрактном "директоре стадиона", который должен уметь поддержать разговор со своими айтишниками на уровне более детальном, чем "сделайте мне красиво", тьфу, "вычислите мне что-нибудь, и подешевле"),
-- прикладных специалистов (инженеров, которым нужно делать инженерные расчёты. Или учёным, которым нужно "открывать законы природы"),
-- программистов (которых разных сортов уже столько, что не факт, что их нужно учить одной и той же алгоритмике -- скажем, спецов по квантовым компьютерам какой алгоритмике учить? А спецов в data science? А спецов в AI? Или они все уже не "программисты"?

И спросить не у кого. Такой момент в истории, когда никто ничего про алгоритмику в целом не знает. Как в притче о слоне и семи мудрецах, один видит в алгоритмике продолжение дела Кнута, другой дифференцируемое программирование (differentiable programming, https://ailev.livejournal.com/1464563.html), третий рассуждения про применимость теоретических работ Тьюринга к нейроморфным компьютерам на мемристорах и квантовым компьютерам (computer science -- естественная наука), и алгоритмика как-то теряется как цельная дисциплина. И даже непонятно, нужно ли стремиться компактифицировать знание об алгоритмике, сделать его более универсальным, или плюнуть и считать алгоритмику разъехавшейся по каким-то частным дисциплинам?

И это даже не всё вычислительное мышление. Кроме алгоритмики в вычислительном мышлении что-то должно быть сказано и про моделирование данных. Ибо без данных алгоритмы не бывают. А там тоже всё чудесато. Ибо алгоритмы и данные -- это две стороны одной медали, и не только в классической информатике. Графы знаний и коннективистские модели данных (скажем, language models как те же нейросети), моделирование данных в ходе DDD (domain-driven development) -- и вот уже и моделирование данных оказывается весьма бурно развивающимся. Хотя результаты этого моделирования, скорее всего, мы узнаем как "вот открыли ещё один тип алгоритма, который эффективно работает с вот этим видом данных" -- и новизна вида данных потухнет перед новизной алгоритма. Эту ситуацию с недооценкой моделирования данных в информатике тоже нужно исправлять. Есть чат "Типы в языках программирования, моделирования, представления знаний", https://t.me/typeslife, там 439 интересующихся. И поддержать какой-то осмысленный разговор на тему связи структур данных (Arrays, Linked Lists, Stacks, Queues, Maps & Hash Tables, Graphs, Trees самых разных видов, Disjoint Set Union и т.д.), типов данных (целое, строка, плавающее и т.д. -- активно развиваются сейчас плавающие для ускорения вычислений универсальных алгоритмов AI, тех же нейронных сетей), типов (они ж необязательно "данных"), баз данных (где "модель данных" уже звучит вполне знакомо), баз знаний/онтологий/графов знаний и т.д. -- там это не получается почему-то. Разговор сразу рассыпается, увы. Но будем проблемы решать по очереди. Пока решим, что делать с алгоритмикой.

UPDATE: обсуждение в чате блога с https://t.me/ailev_blog_discussion/5058, в чате по типам -- https://t.me/typeslife/7958
Subscribe

Recent Posts from This Journal

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 4 comments