# Table of Contents 1. [Системотехника и вычислительные системы.](#org334e85b) 2. [Книга 1. "Principles of computer system design: an introduction".](#org7ac2358) 1. [Основная линия повествования:](#org933001b) 2. [Критика:](#orgdcd28e4) 3. [Книга 2. "An introduction to theory of complex systems. "](#orgd00d48e) 1. [Теория вероятностей](#orgabad116) 2. [Масштабирование (scaling) в системах и его причины.](#org3b26e05) 1. [Причина 1: criticality](#orgf3219bf) 2. [Причина 2: self-organized criticality](#orgfbbf0b2) 3. [Причина 3: процесс описывается как мультипликативный.](#org52878b6) 4. [Причина 4: preferential processes](#org282b002) 5. [Причина 5: sample space reducing процессы](#org50f5a44) 3. [Сети](#orgaa2d069) <a id="org334e85b"></a> # Системотехника и вычислительные системы. В этой заметке я дам краткие рецензии на две книги, интересные в контексте создания концепции курса по "архитектуре вычислительных систем": 1. "Principles of computer system design: an introduction", по ней читается курс в MIT [первая часть](https://yadi.sk/i/_SCh-7-ITP5vfA) [вторая часть](https://yadi.sk/i/ZxwJ0ObCRLVmrw) 2. "An introduction to the theory of complex systems", по ней в университете Вены читают двухсеместровый курс для математиков и физиков (внезапно). [ссылка](https://yadi.sk/i/0Ip8EAPxUkMyCQ) Первая книга подразумевает изучение общих черт вычислительных систем на высоком уровне абстракции и на уровне концепций, то есть без количественных оценок. Вторая книга изучает системы вообще, представляя их как многослойные реконфигурируемые сети из взаимодействующих компонентов. Большинство примеров взяты из физики, биологии или социальных наук, но есть и из IT, например, алгоритм PageRank, на котором были построены первые версии движка Google. В отличие от первой книги она концентрируется на способах количественного описания таких систем, для чего подтягивает достаточно высокого полёта (но не слишком) математику. Затем я попробую обосновать, не претендуя на полноту, какие разделы математики (фундаментальные и прикладные) наиболее явственно связаны с построением вычислительных систем и их количественным описанием. <a id="org7ac2358"></a> # Книга 1. "Principles of computer system design: an introduction". <a id="org933001b"></a> ## Основная линия повествования: - Системы это сложно и надо со сложностью бороться. - Для борьбы со сложностью используют модульную организацию систем, абстракцию, послойную и иерархическую организацию. - Упоминается проблема масштабирования : если один параметр системы изменяется во сколько-то раз, то другие могут измениться пропорционально так, что система развалится - Ресурсы системы надо использовать по максимуму, чтобы части не простаивали; однако это ведёт к усложнению систем - Три фундаментальные абстракции (типы функциональных компонентов): исполнитель (интерпретатор), память и канал обмена данными. Из них можно как правило построить любую вычислительную систему. - Свойства, которые проявляются в любой реализации этих абстракций. Например, для памяти это атомарность операций, volatility (необходимость в затратах энергии на функционирование), различные виды когерентности чтения/записи, время на запись… - Сильная и слабая модульность; слабая – когда ошибки между модулями легко распространяются, а сильная – когда ошибки контролируются - Клиент-сервисная архитектура как средство усиления границ между модулями; когда обмен сообщениями – единственный способ общения между модулями - Виртуализация как средство усиления границ между модулями; виртуализация одного функционального компонента на многих, многих на одном, одного на одном. - Что подразумевается под "производительностью" и какие бывают способы её повышать - Что подразумевается под "надёжностью" и какие бывают способы её повышать - Компьютерные сети как системы, послойная организация, распространённые проблемы в обмене сообщениями - Атомарность операций в системах - Безопасность: доверие, аутентификация, шифрование, контроль доступа к ресурсам в системах <a id="orgdcd28e4"></a> ## Критика: - "Исполнитель" или "Интерпретатор" в понятии авторов описывается прежде всего как последовательное выполнение команд. Но модели вычислений основанные на лямбда-исчислении, логике Хоара, выводе параметров распределений (вероятностное программирование), системах переходов и много что ещё так не описываются. Даже императивные языки типа C сейчас нельзя полностью описать как последовательное выполнение команд, так как компиляторам позволяется многие действия менять местами в целях оптимизации. - Неубедительно говорится про масштабирование, гораздо качественнее и глубже его изучает вторая книга (в т.ч. с математической точки зрения). - Хорошие идеи, распределение знаний по полочкам, связи между курсами – но никаких механизмов количественной оценки свойств систем (и понятно почему, для этого нужна математика) Такой курс наши хорошие студенты потянут уже сейчас, при разумном оформлении и выворачивании наизнанку (изложение от примеров к обобщениям, а не наоборот; примеры в книжке не очень хорошо продуманы, а иногда вообще некорректны). <a id="orgd00d48e"></a> # Книга 2. "An introduction to theory of complex systems. " Сложные системы, о которых говорится, рассматриваются на высоком уровне абстракции, как правило безотносительно конкретной области, в том числе вычислений. Однако признаётся и обосновывается, что сложные системы по своей природе алгоритмичны (и потому классический чистый аналитический подход в духе физики не подходит). Абстракция системы – это многослойная сеть взаимодействующих компонентов, в которой каждый слой может динамически реконфигурироваться. В книжке обзорно показывается разная математика, полезная для описания таких систем. Приведу краткий конспект основных идей, потому что тема для нас очень новая и непростая – хотя бы ключевые слова и идеи хотелось бы здесь изложить. <a id="orgabad116"></a> ## Теория вероятностей - понятия вероятности - разные распределения и откуда они возникают в реальном мире - стохастические процессы без памяти, с памятью разного размера (Марковские, с сохранением полной истории, с подкреплением), <a id="org3b26e05"></a> ## Масштабирование (scaling) в системах и его причины. Scaling это когда при изменении одной величины в системе другая величина изменяется кратно. Это требует степенной зависимости между несколькими параметрами, типа \[f(x) = x^c\] ; см. <https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BF%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%B7%D0%B0%D0%BA%D0%BE%D0%BD>. Интересны ситуации, когда стохастическая система сложно устроена, но на макроуровне просматриваются некоторые интегральные характеристики, и вот они часто тоже подчиняются степенным законам. Нет универсального для всех систем источника степенных зависимостей на таком макроуровне, но часто они имеют одну из пяти причин: <a id="orgf3219bf"></a> ### Причина 1: criticality … когда система находится в точке перехода из одного макросостояния в другое макросостояние. Пример. Представим, что есть некоторое количество агентов, расположенных в вершинах графа. Теперь случайно установим связи между ними так, что с вероятностью P между парой соседей образуется связь. Если мы будем менять P от 0 до 1, то как будет меняться связность? - При P = 0 никаких связей между агентами нет - При P = 1 все агенты окажутся связаны друг с другом, напрямую или косвенно. Будем увеличивать P начиная с нуля, и при некотором критическом значении Pc все агенты объединятся в большой кластер и станут связаны. В зависимости от удалёности P от Pc , две величины будут меняться по степенным законам: - размер максимального кластера - средняя дистанция между двумя агентами в рамках одного кластера. <a id="orgfbbf0b2"></a> ### Причина 2: self-organized criticality Это почти то же самое, но системы в процессе функционирования сами доходят до критической точки, а не помещаются в неё с помощью внешней подстройки. Можно по всякому менять параметры системы, но она всё равно сама дойдёт до критического состояния. Грубо говоря, системы накапливают некие изменения, а потом происходит Большое Событие, или каскад событий; как куча песка, в которую мы добавляем песка пока его не станет слишком много и куча обрушится с одного из склонов; затем мы опять добавляем песок, пока не дойдём до следующей критической точки, в которой песок обрушится. Или когда накапливаются мелкие ошибки и это приводит к крупному сбою. В моменты таких Больших Событий проявляются степенные законы, связывающие количественные характеристики системы. Этот тип систем малоизучен и применения в IT почти не нашлось, за исключением некоторых методов оптимизаций. Хотя сценарий с каскадом ошибок кажется перспективным для изучения. <a id="org52878b6"></a> ### Причина 3: процесс описывается как мультипликативный. Имя происходит от того, что в нём происходят произведения случайных величин. Например, у нас есть N компьютеров в сумме обрабатывающие одинаковое количество задач. Но на каждом из них обрабатывается переменное количество задач; количество задач на конкретном компьютере каждую минуту умножается на случайный коэффициент, специфичный для данного компьютера, и мы знаем распределение этой случайной величины. Если суммарное количество задач на всех компьютерах остаётся одинаковым, то колебания нагрузки на каждом компьютере будут описываться степенным распределением. <a id="org282b002"></a> ### Причина 4: preferential processes Такие процессы, когда вероятность перехода из состояния пропорциональна количеству раз, сколько этот переход был совершён в прошлом. Очень похоже на то, как смотрят на программы оптимизаторы, когда динамический анализ программы показывает, что некоторые переходы очень часто происходят. Зачастую в эту категорию попадают Марковские процессы или процессы с историей, в которых вероятности зависят от пути, которым мы пришли к состоянию. <a id="org50f5a44"></a> ### Причина 5: sample space reducing процессы Это процессы, которые в процессе работы становятся всё более предсказуемыми, то есть со временем могут принимать всё меньшее количество состояний. <a id="orgaa2d069"></a> ## Сети Это графы, случайные графы, спектральный анализ (это изучение собственных чисел матриц смежностей в графах сетей чтобы определять свойства сетей например "кучность" ), поиск кластеров в сетях, распределение количества связей в узлах в зависимости от того, как сеть формируется… Изучаются несколько классов случайных сетей. Вообще было эмпирически установлено, что т.н. безмасштабные сети, в которых количество узлов со степенью K пропорционально K<sup>(-x)</sup>, хорошо подходят для моделирования многих естественно возникающих сетей: социальных, биологических, графов цитирований, ссылок в интернете, компьютерных сетей вообще. Эти сети выглядят так: есть много хабов, которые имеют много соединений, а остальные узлы сети – меньше. Не все сети, которые так выглядят – безмасштабные. Примечание от меня: почитал статьи, и в CSE эти степенные законы периодически находят – например, в структуре исходного кода. Однако **сложно проверить, является ли сеть безмасштабной на самом деле**. В безмасштабной сети количество связей у узлов распределено по степенному закону, в то время как существуют похожие распределения, вроде лог-нормального, которые под степенные законы успешно маскируются, особенно на небольших данных. Изучены классы сетей, в которых новые узлы предпочитают соединяться с хабами, или наоборот. Рассматриваются разные способы поиска кластеров в графах, в т.ч. статистические; поиск наиболее важных/часто используемых/критических для функционирования маршрутов в сети. Затем мы переходим к использованию графов для моделирования сложных систем (которые, напомню, моделируются как многослойный пирог из изменчивых сетей). Рассматриваются три аспекта динамики: - аспект 1: распространение чего бы то ни было по сетям; это могут быть ресурсы, ошибки, информация, вирусы и т.д. - аспект 2: модели где у каждого узла сети есть внутреннее состояние. - аспект 3: одновременное распространение разных влияний в сетях и конкуренция за узлы. Механизм корреляционных сетей; они позволяют с помощью анализа серии состояний системы выделить в ней части, которые участвуют в одних и тех же процессах (это корреляционная связь, а не причинно-следственная). Рассматривается большой интересный пример с оценкой системного риска в финансовой сфере. Система – это сеть из банков. Каждый слой показывает один из типов взаимодействий между ними, каждый узел (банк) помечен его общим количеством денег. Сначала строится математическая модель для оценки рисков, которая показывает "долю вины" каждого банка в system failure. Затем она используется для реструктуризации системы для повышения её надёжности. Рассматриваются несколько таких моделей, например, PageRank (которая связана с ранним алгоритмом google для ранжирования веб-страниц), DebtRank. Интуиция подсказывает, что похожим образом можно оценивать надёжность в вычислительных системах. В продолжении опишу ещё два раздела: эволюционные процессы и статистическую механику/теорию информации применительно к сложным системам. Критика: - Книга объявляет, что у неё невысокие пререквизиты, но нашим студентам до этих пререквизитов два года нормальной математики с лучшими преподами. - Релевантные области математики описаны очень коротко и "на пальцах" – и хорошо и плохо, т.к. видно главное, но это не учебник по математике. - ОЧЕНЬ хорошо, дружественно к инженерам, описана связь математики и реального мира; глава по теории вероятностей, например, имеет лучшее описание того, откуда какие распределения появились, среди прочитанных мною книг, несмотря на свой обзорный характер. Главный автор – физик, что ощущается.