Алгоритмы на кристалле (анонс книги)

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

О чем и для кого эта книга

Я собираюсь рассказать об удивительном мире, где для решения любой алгоритмической задачи вы имеете право построить какую-угодно вычислительную машину и как угодно по своему желанию ее запрограммировать. Больше никаких чужих правил, чужих архитектур и чужих языков программирования – полная свобода фантазии и изобретательства. Это мир, в котором вы сами решаете, какую именно микросхему реализовать на полупроводниковом кристалле. Чтобы вам в этом помочь, я постарался собрать некий базовый набор приёмов того, как проектировать эффективные логические цифровые схемы.

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

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

График работы и приглашение к сотрудничеству

Хотя все содержание будущей книги у меня уже в голове, превратить его в удобочитаемый текст — для меня будет целым испытанием. Я боюсь, что не справлюсь, если попытаюсь сделать все разом. Мне кажется более разумным публиковать в качестве черновика, скажем каждую среду, все что я успею сделать за неделю.

Не все, о чем я собираюсь писать — лежит в зоне моей компетенции. Ко мне следует относится как к математику, который кое-что краем уха слышал о принципах работы микросхем. Тем не менее, разработка «в железе» одного довольно сложного устройства некоторое продолжительное время была моей работой.

Я не всегда в курсе общепринятой терминологии — исправляйте, если вдруг режет ухо.

Как мне кажется, я не плох в алгоритмах и математике, поэтому могу удивить читателя чем-то новым, что изобрел сам. В противовес этому моя способность поиска информации по свежим научным статьям, мягко говоря, страдает. Если вы интересуетесь последними исследованиями в какой-либо из затронутых тем, делитесь, пожалуйста, ссылками на литературу.

Чтобы поджечь искорку интереса у специалистов я упомяну о нескольких, как мне кажется, коммерчески интересных результатах:
\\произвольный неблокирующий коммутатор -битных источников в -битных стоков глубиной и объемом
\\конвейеризованная (порция данных каждый такт) память с -битными неблокирующими портами чтения/записи собранная из банков однопортовой RAM, содержащих каждый слов размера бит, которая:
вмещает слов размера бит(данные не дублируются),
имеет задержку тактов.
использует дополнительно не более регистров и элементарных логических блоков.

Ниже я привел предполагаемое оглавление.

Список и краткое содержание глав

Глава 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-подобные устройства.

Память, регистры, функциональные блоки, кросс-коммутация.

Ассемблер и оптимизация кода.

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

Надеюсь несколько первых параграфов смогу выложить в ближайшую среду.