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

Я начал работать над книгой.
Уже опубликованы:
Глава 1(начало): Вычислительная модель.
Глава 1(продолжение): Быстродействие элементарных схем.

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

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

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

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

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

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

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

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