Нет, этот шаг – не безумие, но моя попытка бороться с ним. Попытка сконцентрироваться на чем-то разумном, заставить свой мозг снова думать, преодолеть моральную травму и начать хоть как-то смотреть в будущее. Быть может, этот труд станет лекарством не только для меня.
О чем и для кого эта книга
Я собираюсь рассказать об удивительном мире, где для решения любой алгоритмической задачи вы имеете право построить какую-угодно вычислительную машину и как угодно по своему желанию ее запрограммировать. Больше никаких чужих правил, чужих архитектур и чужих языков программирования – полная свобода фантазии и изобретательства. Это мир, в котором вы сами решаете, какую именно микросхему реализовать на полупроводниковом кристалле. Чтобы вам в этом помочь, я постарался собрать некий базовый набор приёмов того, как проектировать эффективные логические цифровые схемы.
Основной акцент повествования сделан на математическую и алгоритмическую стороны решаемых задач. Это скорее не «еще одно» руководство по проектированию электронных схем, а учебник по очень специфическому способу реализации алгоритмов. Я надеюсь, что его содержание заинтересует и увлечет широкий круг любителей математики и программирования, даже если они раньше никогда и не сталкивались с разработкой микросхем. В то же время я старался подобрать материал так, чтобы и типичный hardware-разработчик мог легко в нем разобраться и с пользой применить в своем ремесле.
Хотя внутри книги вы и отыщете множество используемых на практике алгоритмических схем, ее не стоит считать простым инженерным справочником. Самое ценное, что вы можете почерпнуть – это специфический способ мышления и характерный набор приемов того, как подобные задачи решать. Конкретные алгоритмы и схемы служат здесь главным образом для демонстрации этих методов.
График работы и приглашение к сотрудничеству
Хотя все содержание будущей книги у меня уже в голове, превратить его в удобочитаемый текст — для меня будет целым испытанием. Я боюсь, что не справлюсь, если попытаюсь сделать все разом. Мне кажется более разумным публиковать в качестве черновика, скажем каждую среду, все что я успею сделать за неделю.
Не все, о чем я собираюсь писать — лежит в зоне моей компетенции. Ко мне следует относится как к математику, который кое-что краем уха слышал о принципах работы микросхем. Тем не менее, разработка «в железе» одного довольно сложного устройства некоторое продолжительное время была моей работой.
Я не всегда в курсе общепринятой терминологии — исправляйте, если вдруг режет ухо.
Как мне кажется, я не плох в алгоритмах и математике, поэтому могу удивить читателя чем-то новым, что изобрел сам. В противовес этому моя способность поиска информации по свежим научным статьям, мягко говоря, страдает. Если вы интересуетесь последними исследованиями в какой-либо из затронутых тем, делитесь, пожалуйста, ссылками на литературу.
Чтобы поджечь искорку интереса у специалистов я упомяну о нескольких, как мне кажется, коммерчески интересных результатах:
\\произвольный неблокирующий коммутатор
\\конвейеризованная (порция данных каждый такт) память с
вмещает
имеет задержку
использует дополнительно не более
Ниже я привел предполагаемое оглавление.
Список и краткое содержание глав
Глава 1. Знакомство и базовые принципы.
Уровень абстрактного представления вычислений на кристалле.
\ Дискретное время. Дискретный бинарный сигнал. Проводники сигналов. Абстракция регистра.
\ Элементарные логические блоки: «И», «ИЛИ», «НЕ», «0», «1», «+», прямой и обратный бинарные
мультиплексоры.
Комбинирование простых блоков в логические схемы.
\ «+» и обратный мультиплексор из логических элементов (нкф и ндф).
\Адресное дерево.
\Логические противоречия и требование ацикличности.
\Объем и глубина.
Примеры реализации простейших алгоритмов.
\Представление натуральных чисел.
\Каскадный компаратор.
\Каскадный счётчик.
\Прямой и дополнительный код представления целых.
\Каскадный сумматор.
Простейшие структуры данных.
\Каскадный стек.
\Простейшая очередь.
\Однопортовая RAM.
Некоторые замечания о физической аналогии работы логических схем: задержки в цепях и
проблемы тактирования.
Глава 2. Конвейеризация и параллелизм на примере арифметических алгоритмов
Конвейеризация, как способ борьбы со слишком большими задержками.
\Конвейеризованный каскадный сумматор.
\Конвейеризованное адресное дерево.
\Абстрактная задача конвейеризации ациклической схемы.
Разделяй и властвуй.
\Параллельный компаратор.
\Параллельный счётчик.
\Параллельный (префиксный)сумматор.
\Подсчет количества каналов, со значением X.
Сложение группы чисел.
\Древовидная схема соединения сумматоров.
\Сложение с неполным переносом.
\Схема с неполным переносом для подсчета суммы конечного ряда.
\Задача вычисления всех частичных сумм конечного ряда.
Умножение двух небольших чисел.
\Умножение столбиком.
\Экономичный алгоритм.
Замечание об алгоритме деления.
Глава 3. Задача параллельной сортировки. Сортировочные Сети
Знакомство с понятием.
\Параллельная реализация алгоритма сортировки пузырьком.
\Понятие сортирующей сети.
\Закон нуля и единицы для сортирующих сетей.
Алгоритм слияния, как элемент асимптотически быстрого способа сортировки на последовательной машине.
Сети Батчера, решающие задачу слияния двух множеств:
\Четно-нечетная сеть слияния.
\Битонная сеть слияния.
Битонная сортировочная сеть.
Задача отыскания статистик k-того порядка.
Глава 4. Задача параллельной сортировки. Быстрые несетевые алгоритмы
Обращения произвольной перестановки.
\Алгоритм реализации на последовательной машине.
\Схема, допускающая множественную запись в
\Стопка адресных деревьев и стопка деревьев слияния.
\Проблема квадратичного роста объема схем.
Задача дихатомной сортировки.
\Сведение задачи к проблеме упорядоченного уплотнения (удаления пустых позиций).
\Функция распределения пустых позиций.
\Сдвиговая шкала.
\Быстрая реализация алгоритма последовательных поразрядных сдвигов.
Экономная схема обращения перестановок.
\Поуровневая компрессия стопки адресных деревьев.
\Различные компромиссы объема и глубины.
Параллельная сортировка множества, помеченного плотной группой чисел.
\Сведение задачи к многократному повторению дихотомной сортировки.
\Обращение перестановки (упорядочивание чисел от 1 до N).
\Экспоненциальное разрастание объема при неаккуратной реализации общего случая.
\Более разумное распределение ресурсов сдвиговой шкалы. Простая реализация.
\Схема с опционально неполным прохождением сдвигающей шкалы.
Глава 5. Коммутация каналов
Коммутация с сохранением порядка.
\Непрерывная коммутация из N в M>N.
\Циклическая коммутация из N в N.
\Коммутация прямого и обратного упорядоченного уплотнения из N в N и из N в M>N.
\Коммутация разделение N каналов на два произвольных отрезка.
Простейшие схемы произвольная коммутация из N в N.
\Дорогая неблокирующая схема с минимальной глубиной.
\Дорогая неблокирующая схема с использованием адресных деревьев.
Аналогия между сортировкой и коммутацией.
\Коммутация, использующая схему обращения перестановки.
\Произвольная перестановочная коммутация из N в N с применением сети Батчера.
\Перестановочная коммутация с применением схемы поразрядной сортировки.
\Проблема дублирования и пропуска в общем случае.
Произвольная блокирующая коммутация из N в N.
\Схема использующая поуровневую компрессию стопки обратных адресных деревьев.
\Трудности модификации в неблокирующую схему.
\Компромиссы объема и глубины.
\Блокирующая коммутация из N в M>N.
Экономичная схема произвольной неблокирующей коммутации из N в N.
\Сортировка потоков по номеру источника.
\Схема, предназначенная для дублирования потоков.
\Соединение недублированных стоков с источниками.
Глава 6. Стек, очередь
Стек небольшого объема.
\Быстрый однопортовый стек на сдвиговых регистрах.
\Простая энергоэффективная однопортовая реализация.
\Реализация на базе RAM.
\Борьба за скорость. Буферизация головной части.
\Доказательство корректности работы.
\Многопортовая версия.
Очередь небольшого объема.
\Простая версия на сдвиговых регистрах (запись в конец стека, чтение из головы).
\Простая энергоэффективная однопортовая реализация с двумя точками доступа.
\Реализация на базе RAM.
\Борьба за скорость. Буферизация точек доступа.
\Доказательство корректности работы.
\Многопортовая версия.
Массивы стеков и очередей?
Глава 7.Задача «Вставить, найти, удалить»
Реализация задачи «Вставить, найти, удалить» на последовательной машине.
\Алгоритм сбалансированного дерева.
\Трудозатратность свободной коммутации узлов дерева.
Быстрый, но энергозатратный алгоритм для задачи небольшого ограниченного объема.
\Описание интерфейса (абстракция мгновенной вставки, мгновенного удаления, мгновенного
поиска с задержкой выдачи результата)
\Отдельно найти не более P элементов.
\Отдельно удалить не более P элементов.
\Отдельно вставить не более P элементов.
\P-портовая реализация, объединяющая поиск, вставку и удаление.
Каскадная логарифмическая схема.
\Идея алгоритма.
\Однотактовая и многотактовая реализации.
\Трудности конвейеризации.
\Дублирование средних секций.
\Особое дублирование первой секции.
Глава 8. Многопортовая RAM.
Многопортовая RAM с использованием регистров.
\Соглашения о правилах работы интерфейса.
\Многопортовое адресное дерево.
\Конфликт записи данных.
\Конвейризация
Неблокирующая многопортовая RAM с использованием небольших однопортовых RAM-блоков.
\Трудности из-за невозможности одновременного доступа более чем к одной ячейке каждого RAM-блока.
\Идея отложенной записи и чтения.
\Алгоритм буферизации.
\Алгоритм переноса данных из буфера в ячейки RAM блоков «Таянья льдов».
\Чтение «наперегонки».
\Полная схема.
Глава 9. Программирование поведения сложной логической схемы.
Принцип программируемого поведения.
Генерация команд в реальном времени.
\Вычисления с условно предсказуемым переходом.
\Необходимость экономии памяти, повторное использование последовательностей команд.
\Процедурный язык высокого уровня для генерации команд.
\Транслирование в программу реального времени (команда управления на каждый такт).
\RAM-машина, генерирующая команды в реальном времени.
Централизованное и распределенное командование устройством.
\Соединение генераторов команд между собой.
\Синхронизация задержек времени.
Глава 10. CPU-подобные устройства.
Память, регистры, функциональные блоки, кросс-коммутация.
Ассемблер и оптимизация кода.
Пример проектирования.
\Алгоритм вычисления расстояние между всеми парами вершин в графе.
\Случай, когда граф не помещается в память на кристалле.
\Анализ критических ресурсов.
\Выбор кванта информации.
\Функциональные блоки.
\Организация памяти.
\Регистровый файл.
\Программа высокого уровня.
\Сценарии команд управления для каждого блока.
Надеюсь несколько первых параграфов смогу выложить в ближайшую среду.
Комментарии (36)
hardtop
21.04.2022 22:31+5Очень фундаментально. Яб с удовольствием такую книгу купил. Продолжайте, пожалуйста!
VaalKIA
22.04.2022 02:04+2Под такую мощную аннотацию, как под бизнес план, можно (и нужно) собирать деньги, на каком-нибудь краудрафтинге. Думаю, что вам стоит проработать этот момент, с удовольствием заплачу вперёд.
P. S. Брендон Сандерсон на кикстартере собрал 24 миллиона долларов на выпуск 4 книг. Как гласит 37 статья конституции: любой труд должен быть оплачен (но это не точно :)
Sergey_Kovalenko Автор
22.04.2022 07:22+1Если одолею половину, спрошу у вас совета, как набрать деньги на хорошего переводчика. В любом случае мне бы хотелось какую-то версию книги в открытом доступе оставить. Про бумажную версию мечтал, но пока не более.
Rutel_Nsk
22.04.2022 05:04+3Про коммутаторы, если интересно прочитайте мое решение данной проблемы (меня здешние «филологи» не любят и потому на другом сервере):
1. aftershock.news/?q=node/1096748 — про компенсацию эффектов проскальзывания.
2. aftershock.news/?q=node/1096761 — про разделение одного канала на много разных
3. aftershock.news/?q=node/1098175 — про труктуру коммутатора
Если вы специалист (как написали), то сможете понять.
Если я прав лучше чем у меня сделать невозможно.
PS Минусаторы не скупимся, пусть будет -1000 ))))Sergey_Kovalenko Автор
22.04.2022 07:35+1Ох, у вас там реальная инженерная задача пакетной коммутации. Я о таких слышал, но глубоко не изучал. Там же статистика, тория массового обслуживания (разруливание очередей) и еще масса всего веселого. Можно на досуге подумать, конечно...
korean_pilot
22.04.2022 06:57Коллега! Вы намеренно не рассматриваете в Вашей книге конечные автоматы?
Sergey_Kovalenko Автор
22.04.2022 07:17Да, но фактически они есть повсюду, в каждой сложной схеме.
Наверное стоило бы пару слов сказать отдельно. Для тех, кто совсем не знаком с понятием, я рекомендую простенькую книгу:
Росс Эшби "Введение в кибернетику"
- приятно написана хорошим педагогом и доктором не только философии, но по совместительству еще и медицины.
KaminskyIlya
22.04.2022 07:40+2Тоже подписываюсь.
Немного не по теме... А Вы не подскажите, сколько транзисторов уходит, на реализацию 32-битного сумматора двух чисел? Я руководствовался описанием отсюда https://ru.wikipedia.org/wiki/Сумматор_с_переключением_переноса и насчитал 854. Буду очень благодарен за справку.
Sergey_Kovalenko Автор
22.04.2022 08:08+1Кажется, то о чем вы говорите - это один из вариантов сумматора с ускоренным переносом. Через пару недель я очень подробно опишу префиксный сумматор (не совсем то же самое, но во многом похоже) на уровне примитивных блоков вроде однобитного "+", "и", "не" "или", бинарного мультиплексора. Если вы представляете, как из транзисторов реализовать каждый блок, то сможете подсчитать их количество. Наверное САПР будет способен обойтись меньшим числом транзисторов.
В анонсированной книге я намеренно выбрал уровень элементарных логических блоков по нескольким причинам:
1) Уровня логических блоков уже достаточно для реализации O-большое эффективных алгоритмов.
2) Многие из простых математиков могут не знать, как функционируют электрические полупроводниковые схемы. (Целая профессия, ей наверное пару лет учат).
3) Я сам уже почти полностью забыл физику электричества.
Если вдруг вам будет необходим именно сумматор с ускоренным переносом, напишите мне - вместе что-нибудь придумаем.
Druj
22.04.2022 11:28Звучит слишком хорошо чтобы когда-нибудь стать реальностью, будем надеяться что всё получится.
Sergey_Kovalenko Автор
22.04.2022 12:37Я тоже часто склонен сомневаться. Говорят, что в умеренных количествах сомнение - это полезная черта характера)
gchebanov
22.04.2022 12:50Первый результат почти очевидный, если я правильно понял формулировку - OUT[I] = IN[SIGMA[I]]. берем сеть бетчера из коммутаторов размера 2, отдельно сортируем в ней перестановку inv(SIGMA), выходы компораторов подаем в качестве конфигурации соответствующих коммутаторов. Кажется это должно работать точно также если SIGMA произвольное отображение, только на вход коммутаторов подается два бита вмесио одного (вместо swap_inputs, sel_0+sel_1), и сортировать что то чуть более хитрое.
Sergey_Kovalenko Автор
22.04.2022 13:03Почти, тот метод, что описали вы, даст глубину log^2(N)loglogN, поскольку сама сеть Батчера имеет в глубину log^2(N) компараторов и каждый компаратор чисел величины порядка N будет в глубину loglog(N).
Ход вашей мысли верный, но получить log^2(N) лично для меня оказалось совсем не простой задачей.gchebanov
22.04.2022 13:49Смотрел с точки зрения того что перестановка редко меняется и мы вольны что угодно для нее посчитать заранее.
Вроде у Батчера на каждом слое мы можем смотреть на определенный бит, что то вроде 0102103210 - для 4 бит (N=16).Да, так действительно сложнее.Sergey_Kovalenko Автор
22.04.2022 14:02Батчер двигает токены вверх вниз очень сильно: одним битов в сравнении вряд ли получится отделаться. Настоящая сложность сетей Батчера не менее N*log^3(N) по объему и не менее log^2(N)loglog(N) по глубине. Несмотря на все это Батчер крут своей универсальностью (вставляй любой компаратор и все заработает) и тем, что его алгоритм - это именно сеть.
Sergey_Kovalenko Автор
22.04.2022 13:25loglogN - асимптотически очень медленно растущая функция, но c учетом необходимости округления в сторону большего loglog(16) = 2, loglog(17) = 3. Иметь коммутатор с в 2 или 3 раза меньшей глубиной, например коммутатор между мультипроцессором и памятью - даже очень заманчивая перспектива.
gchebanov
22.04.2022 14:55Безусловно правда. Правда я не удивлюсь что на практике лучше будет работать что-то ближе к наивному (log(n), n^2 log(n)). По исходной задаче пока только смог свести к pext/pdep с глубиной log(n), что наверное не возможно.
gchebanov
22.04.2022 13:08По второму результату кажется что O(H) довольно много на практике, или я не понял условие.
Sergey_Kovalenko Автор
22.04.2022 13:19Там вроде задача "вставить, найти, удалить" за O(H) не позволит. Еще объединение блоков RAM - это logk глубины, если вы не допускаете множественную запись в шину (то есть каждая шина присоединена только к 1 выходному порту). Интересно было бы взглянуть. Я думаю, авторы просто пренебрегли на их взгляд несущественными членами. Смогут ли они разогнать свои решения до частоты, сравнимой с предельной частотой работы регистра?
Sergey_Kovalenko Автор
22.04.2022 13:43Да простите, я не правильно понял ваш вопрос. Вы наверное имели ввиду, что при банке RAM в 16 или 32 слова, даже задержка в 16 или 32 тактов - это не позволительная роскошь? Есть задачи, в которых обращение к памяти можно без труда просчитать заранее и получается, что фиксированная задержка большой роли не играет, а пропускная способность и возможность параллельного доступа - наоборот. В другого типа задачах без особых упущений удается принять за единицу информации страницы слов большого объема. Там тоже задержка не будет так важна.
kostikov_pavel
22.04.2022 14:05Скажите пожалуйста, в качестве результата должны получится правила разработки и реализации алгоритмов на ПЛИС?
Sergey_Kovalenko Автор
22.04.2022 14:12Я надеюсь, что для разработчики в том числе и схем на ПЛИС, не будет сложным транслировать результаты книги в описание на используемом ими HDL. Более того, я думаю не только мне, но и многим читателям будет интересно узнать о результатах таких экспериментов.
kostikov_pavel
22.04.2022 14:29Т.е. задача книги шире, чем реализация алгоритмов с помощью известных ПЛИС ? А можно уточнить: задачи, решения которых будут описываться в книге, относятся к базовой математике? Решение задач оптимального управления не будет целью одного из разделов?
Sergey_Kovalenko Автор
22.04.2022 15:17+1Не только ПЛИС:
Разработка под ASIC,
Поломать голову и нескучно скоротать вечер,
Некоторые методы можно использовать для проектирования производственных конвейерных линий и управления крупным автоматизированным предприятием.
В книге математика - всего лишь слуга.
В оптимальном управлении не специалист, но если кто-то обнаружит пересечения, можно вместе обдумать.
Khort
23.04.2022 23:04Клюнул на название, и честно говоря слегка "прифигел". Потому что 20 лет занимаюсь пректированием чипов, но после первого прочтения "вскользь" не понял вообще ничего. После второго, подробного прочтения, уже понял, что это алгоритмика, никаких кристаллов здесь нет и в помине, но материал вполне попадает под классификацию чипостроения в качестве логического дизайна. Причем дизайна весьма специфического, поскольку, как я понимаю, для имплементации рассматриваемых алгоритмов предлагается не использование процессора с ограниченным числом инструкций, а имплементация "в лоб" путем построения автомата (поправьте, если не прав). И вот здесь я оказался в тупике, поскольку сходу не смог придумать, для чего это может быть нужно. Т.е. автору я бы посоветовал включить в книгу и практические примеры, где эти алгоритмы могут быть использованы.
Еще небольшой комментарий по вводной части. В логическом дизайне время различают на физическое и логическое. Логическое время измеряется в шагах алгоритма, и может течь как с той же скоростью, что и физическое время (синхронная работа от внешних "часов"), так и без привязки к физическому времени (асинхронная работа). Соотвественно, автомат может проектироваться как для синхронной работы по шагам state <= next_state (Мур, Мили), так и с использованием параллельных процессов (модель Хаффмана). Это более широкая классификация, чем просто "дискретное время". Полагаю, автор предлагает проектирование именно синхронных автоматов.
Ни на что не претендую, просто высказал свое мнение человека - не из целевой аудиотрии, т.е. случайно заглянувшего.
Sergey_Kovalenko Автор
23.04.2022 23:40Нет, нет, Вы все правильно сказали. Я не обидчивый: обратная связь, особенно с людьми из индустрии - это для меня просто подарок судьбы)
Да, я говорю именно об имплементации в лоб.
Применяется например в скоростной обработке сигналов (интересно что там F22?, не уж-то обычным CPU считают), девайсах для криптографии (майнить нынче выгодно тоже на асиках), тренировка и обработка на нейросетях, да что там, гуляя по улице в Москве, встретил человека, который FPGA под скоростной трейдинг перепрофилировал. Кто чем только не балуется!
Еще есть тенденция переноса расчётов в дата-центры. Почти для любой алгоритмической задачи, которая решается более чем за линейное время от своего размера и хорошо параллелится (та же сортировка или операция "найти все общие записи в двух таблицах", почти все алгоритмы на графах), в перспективе выгодно иметь отдельный специализированный девайс, который ее считает (при условии что в дата-центре его можно хорошенько загрузить).
В книге я собираюсь ограничиться только синхронными схемами. Однако когда речь идет о борьбе за скорость - это в том числе и борьба за частоту (то есть борьба против глубины). Мне видится (но я не настаиваю на своем видении), что все более продвинутое: много тактовых частот, разные клоковые зоны, срабатывание по обеим фронтам сигнала - требует каких-то отдельных технических приёмов, но не требует какой-то отдельной теории. Знаешь, как сделать синхронную схему, переделать ее в более продвинутую тоже сможешь.
Если вы дадите какие-то советы или исправите что-то в терминологии - тоже буду благодарен.
serginfo2009
Подпишусь. Это может быть интересно.
Sergey_Kovalenko Автор
Постараюсь оправдать ваши ожидания.