Я начал работать над книгой.
Уже опубликовано: Глава 1 (начало): Вычислительная модель.
Глава 1 (продолжение): Работоспособность элементарных схем.
Нет, этот шаг не безумие, а моя попытка с ним бороться.
Попытка сконцентрироваться на чем-то разумном, заставить свой мозг снова задуматься, преодолеть моральную травму и начать как-то заглядывать в будущее.
Возможно, эта работа станет лекарством не только для меня.
О чем эта книга и для кого?
Я собираюсь рассказать об удивительном мире, где для решения любой алгоритмической задачи вы имеете право построить любой компьютер и запрограммировать его так, как захотите.Больше никаких иностранных правил, иностранных архитектур и иностранных языков программирования — полная свобода воображения и изобретений.
Это мир, в котором вы сами решаете, какой чип реализовать на полупроводниковом чипе.
Чтобы помочь вам в этом, я попытался собрать базовый набор методов проектирования эффективных цифровых логических схем.
Основной акцент в рассказе сделан на математических и алгоритмических аспектах решаемых задач.
Это не «просто еще одно» руководство по проектированию электронных схем, а учебник по очень специфическому способу реализации алгоритмов.
Я надеюсь, что ее содержание заинтересует и увлечет широкий круг любителей математики и программирования, даже если они никогда раньше не сталкивались с проектированием микросхем.
При этом я старался подбирать материал так, чтобы типичный разработчик железа мог легко его понять и с пользой применить в своем ремесле.
Хотя внутри книги вы найдете множество алгоритмических схем, используемых на практике, ее не следует рассматривать как простой инженерный справочник.
Самое ценное, чему вы можете научиться, — это конкретный образ мышления и характерный набор приемов решения подобных задач.
Конкретные алгоритмы и диаграммы здесь служат в первую очередь для демонстрации этих методов.
График работы и приглашение к сотрудничеству
Хотя все содержание будущей книги у меня уже есть в голове, превратить ее в читаемый текст будет для меня непростой задачей.Боюсь, я не справлюсь, если попытаюсь сделать все сразу.
Мне кажется более разумным публиковать в черновиках, скажем, каждую среду все, что успеваю сделать за неделю.
Не все, о чем я собираюсь написать, входит в мою компетенцию.
Относитесь ко мне как к математику, кое-что слышавшему о принципах работы микросхем.
Однако в течение некоторого времени моей работой была разработка довольно сложного в аппаратном отношении устройства.
Я не всегда в курсе общепринятой терминологии - поправьте меня, если вдруг ухо заболит. Мне кажется, я неплохо разбираюсь в алгоритмах и математике, поэтому могу удивить читателя чем-то новым, что придумал сам.
Напротив, моя способность искать информацию в последних научных статьях, мягко говоря, страдает. Если вас интересуют последние исследования по любой из обсуждаемых тем, поделитесь ссылками на литературу.
Чтобы вызвать интерес у специалистов, упомяну несколько, как мне кажется, коммерчески интересных результатов:
\\ произвольный неблокирующий переключатель 
-битные источники в
-бит истощается глубоко 
и объем 
\\конвейерная (часть данных за каждый такт) память с 
-битные неблокирующие порты чтения/записи, собранные из 
банки однопортовой оперативной памяти, содержащие каждый 
размер слова
бит который:
вмещает 
размер слова
бит (данные не дублируются),
имеет задержку 
бьет
использует не более 
регистры и элементарные логические блоки.
Ниже я предоставил рекомендуемое содержание.
Список и краткое содержание глав
Глава 1. Введение и основные принципы.
Уровень абстракции для вычислений на кристалле.
.
Дискретное время.
Дискретный двоичный сигнал.
Сигнальные проводники.
Регистрация абстракции.
.
элементарные логические блоки: «И», «ИЛИ», «НЕ», «0», «1», «+», прямой и обратный двоичные мультиплексоры.
Объединение простых блоков в логические схемы.
.
«+» и инверсный мультиплексор из логических элементов (НКФ и НДФ).
.
Дерево адресов.
.
Логические противоречия и требование ацикличности.
.
Объем и глубина.
Примеры реализации простейших алгоритмов.
.
Представление натуральных чисел.
.
Каскадный компаратор.
.
Каскадный счетчик.
.
Прямой и дополнительный код для представления целых чисел.
.
Каскадный сумматор.
Простейшие структуры данных.
.
Каскадный стек.
.
Самая простая очередь.
.
Однопортовая ОЗУ.
Некоторые замечания о физической аналогии работы логических схем: задержки в схемах и проблемы с таймингом.
Глава 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. Стек, очередь
Маленькая стопка..
Быстрый однопортовый стек с использованием сдвиговых регистров.
.
Простая, энергоэффективная однопортовая реализация.
.
Реализация на базе оперативной памяти.
.
Борьба за скорость.
Буферизация головной части.
.
Доказательство правильной работы.
.
Многопортовая версия.
Маленькая очередь.
.
Простой вариант с использованием сдвиговых регистров (запись в конец стека, чтение из головы).
.
Простая, энергоэффективная реализация с одним портом и двумя точками доступа.
.
Реализация на базе оперативной памяти.
.
Борьба за скорость.
Буферизация точек доступа.
.
Доказательство правильной работы.
.
Многопортовая версия.
Массивы стеков и очередей?
Глава 7. Задача «Вставить, найти, удалить»
Реализация задачи «Вставить, Найти, Удалить» на серийной машине..
Алгоритм сбалансированного дерева.
.
Трудозатраты на свободное переключение узлов дерева.
Быстрый, но энергоемкий алгоритм для небольшой задачи ограниченного объема.
.
Описание интерфейса (абстракция мгновенной вставки, мгновенного удаления, мгновенного поиск с отложенными результатами) … Найдите не более P элементов по отдельности.
.
Отдельно удалить не более P элементов.
.
Отдельно вставляйте не более P элементов.
.
Реализация P-порта, сочетающая поиск, вставку и удаление.
Каскадная логарифмическая схема.
.
Идея алгоритма.
.
Однотактные и многотактные реализации.
.
Трудности конвейерной транспортировки.
.
Дублирование средних секций.
.
Специальное дублирование первого раздела.
Глава 8. Многопортовая оперативная память.
Многопортовое ОЗУ с использованием регистров.
.
Соглашения о правилах интерфейса.
.
Многопортовое дерево адресов.
.
Конфликт записи данных.
.
Конвейеризация Неблокируемая многопортовая ОЗУ с использованием небольших однопортовых блоков ОЗУ.
.
Трудности из-за невозможности одновременного доступа более чем к одной ячейке каждого блока ОЗУ.
.
Идея отложенного письма и чтения.
.
Алгоритм буферизации.
.
Алгоритм передачи данных из буфера в ячейки оперативной памяти блоков «Таяние льда».
.
Чтение "наперегонки".
.
Полная схема.
Глава 9. Программирование поведения сложной логической схемы.
Принцип программированного поведения.
Генерация команд в реальном времени.
.
Вычисления с условно предсказуемым переходом.
.
Необходимость экономии памяти, повторного использования последовательностей команд. .
Процедурный язык высокого уровня для генерации команд. .
Трансляция в программу реального времени (команда управления на каждый такт).
\RAM машина, генерирующая команды в реальном времени.
Централизованное и распределенное управление устройствами.
.
Соединение генераторов команд между собой.
.
Синхронизация задержек.
Глава 10. CPU-подобные устройства.
Память, регистры, функциональные блоки, кроссировка.
Ассемблер и оптимизация кода.
Пример дизайна.
.
Алгоритм расчета расстояния между всеми парами вершин графа.
.
Тот случай, когда график не помещается в память на чипе.
.
Анализ критических ресурсов.
.
Выделение кванта информации.
.
Функциональные блоки.
.
Организация памяти.
.
Зарегистрировать файл.
.
Программа высокого уровня.
.
Скрипты управляющих команд для каждого блока.
Надеюсь, что смогу опубликовать первые несколько абзацев в следующую среду.
Теги: #Производство и разработка электроники #математика #Алгоритмы
-
Анимация Логотипа Сайта
19 Oct, 24 -
Третья Встреча Петербургской Группы Alt.net
19 Oct, 24 -
Приложения Для Пк В Chrome Store
19 Oct, 24 -
Скажите Пару Слов О Комментариях В Коде
19 Oct, 24
