Комментарии 51
Подпишусь. Это может быть интересно.
Очень фундаментально. Яб с удовольствием такую книгу купил. Продолжайте, пожалуйста!
Ждём прогресса, должно быть хорошая книга выйдет)
Желаю удачи в вашем начинании! Звучит интригующе
Одобрямс.
P. S. Брендон Сандерсон на кикстартере собрал 24 миллиона долларов на выпуск 4 книг. Как гласит 37 статья конституции: любой труд должен быть оплачен (но это не точно :)
1. aftershock.news/?q=node/1096748 — про компенсацию эффектов проскальзывания.
2. aftershock.news/?q=node/1096761 — про разделение одного канала на много разных
3. aftershock.news/?q=node/1098175 — про труктуру коммутатора
Если вы специалист (как написали), то сможете понять.
Если я прав лучше чем у меня сделать невозможно.
PS Минусаторы не скупимся, пусть будет -1000 ))))
Да, но фактически они есть повсюду, в каждой сложной схеме.
Наверное стоило бы пару слов сказать отдельно. Для тех, кто совсем не знаком с понятием, я рекомендую простенькую книгу:
Росс Эшби "Введение в кибернетику"
- приятно написана хорошим педагогом и доктором не только философии, но по совместительству еще и медицины.
Для меня автомат это газировка)
Тоже подписываюсь.
Немного не по теме... А Вы не подскажите, сколько транзисторов уходит, на реализацию 32-битного сумматора двух чисел? Я руководствовался описанием отсюда https://ru.wikipedia.org/wiki/Сумматор_с_переключением_переноса и насчитал 854. Буду очень благодарен за справку.
Кажется, то о чем вы говорите - это один из вариантов сумматора с ускоренным переносом. Через пару недель я очень подробно опишу префиксный сумматор (не совсем то же самое, но во многом похоже) на уровне примитивных блоков вроде однобитного "+", "и", "не" "или", бинарного мультиплексора. Если вы представляете, как из транзисторов реализовать каждый блок, то сможете подсчитать их количество. Наверное САПР будет способен обойтись меньшим числом транзисторов.
В анонсированной книге я намеренно выбрал уровень элементарных логических блоков по нескольким причинам:
1) Уровня логических блоков уже достаточно для реализации O-большое эффективных алгоритмов.
2) Многие из простых математиков могут не знать, как функционируют электрические полупроводниковые схемы. (Целая профессия, ей наверное пару лет учат).
3) Я сам уже почти полностью забыл физику электричества.
Если вдруг вам будет необходим именно сумматор с ускоренным переносом, напишите мне - вместе что-нибудь придумаем.
Да именно про него. Но вообще, я хочу примерно прикинуть, сколько транзисторов уйдет на аппаратную реализацию SHA-256, если её развернуть в конвейер.
Если вы представляете, как из транзисторов реализовать каждый блок,
Представляю. Но, я любопытствующий дилетант. Поэтому хочу уточнить у более сведущих людей.
Коллеги, поправьте ход моих мыслей. Полагаю, что на AND уйдет 2 транзистора, на XOR - 6, на OR - это вроде вообще спариванием контактов можно реализовать. Смотрел здесь (кстати, весьма недурной симулятор).
И еще вопрос, почему так популярны элементы И-НЕ, ИЛИ-НЕ? Я что-то упустил этот момент.
Транзисторы, боюсь, - это вне зоны моей компетенции. Синтез небольших схем я предполагал делом решенным, поскольку и САПРы хорошие есть да и слишком уж долго эта задача существует, чтобы ее вдоль и поперек человечество не исследовало. Наверное среди тех, кто заглянет в комментарии, обязательно найдется знающий специалист, который вам сможет подсказать. Не буду показывать пальцем))).
Про OR вы меня удивили, неужели даже по диоду перед "спариванием контактов" ставить не нужно. Там короткого замыкания на наборе 0-1 или 1-0 точно не произойдет?
Если вдруг вам будет необходим именно сумматор с ускоренным переносом
Не смею отвлекать по пустякам. У Вас и так задача грандиозная.
Просто тоже готовлю статью на Хабр про оптимизацию scrypt и имплементацию её на ASIC. Предварительно насчитал, сколько потребуется транзисторов на это. Но хотелось бы проверить себя.
Очень интересно.
Первый результат почти очевидный, если я правильно понял формулировку - OUT[I] = IN[SIGMA[I]]. берем сеть бетчера из коммутаторов размера 2, отдельно сортируем в ней перестановку inv(SIGMA), выходы компораторов подаем в качестве конфигурации соответствующих коммутаторов. Кажется это должно работать точно также если SIGMA произвольное отображение, только на вход коммутаторов подается два бита вмесио одного (вместо swap_inputs, sel_0+sel_1), и сортировать что то чуть более хитрое.
Почти, тот метод, что описали вы, даст глубину log^2(N)loglogN, поскольку сама сеть Батчера имеет в глубину log^2(N) компараторов и каждый компаратор чисел величины порядка N будет в глубину loglog(N).
Ход вашей мысли верный, но получить log^2(N) лично для меня оказалось совсем не простой задачей.
Смотрел с точки зрения того что перестановка редко меняется и мы вольны что угодно для нее посчитать заранее. Вроде у Батчера на каждом слое мы можем смотреть на определенный бит, что то вроде 0102103210 - для 4 бит (N=16).Да, так действительно сложнее.
Батчер двигает токены вверх вниз очень сильно: одним битов в сравнении вряд ли получится отделаться. Настоящая сложность сетей Батчера не менее N*log^3(N) по объему и не менее log^2(N)loglog(N) по глубине. Несмотря на все это Батчер крут своей универсальностью (вставляй любой компаратор и все заработает) и тем, что его алгоритм - это именно сеть.
loglogN - асимптотически очень медленно растущая функция, но c учетом необходимости округления в сторону большего loglog(16) = 2, loglog(17) = 3. Иметь коммутатор с в 2 или 3 раза меньшей глубиной, например коммутатор между мультипроцессором и памятью - даже очень заманчивая перспектива.
По второму результату кажется что O(H) довольно много на практике, или я не понял условие.
Там вроде задача "вставить, найти, удалить" за O(H) не позволит. Еще объединение блоков RAM - это logk глубины, если вы не допускаете множественную запись в шину (то есть каждая шина присоединена только к 1 выходному порту). Интересно было бы взглянуть. Я думаю, авторы просто пренебрегли на их взгляд несущественными членами. Смогут ли они разогнать свои решения до частоты, сравнимой с предельной частотой работы регистра?
Да простите, я не правильно понял ваш вопрос. Вы наверное имели ввиду, что при банке RAM в 16 или 32 слова, даже задержка в 16 или 32 тактов - это не позволительная роскошь? Есть задачи, в которых обращение к памяти можно без труда просчитать заранее и получается, что фиксированная задержка большой роли не играет, а пропускная способность и возможность параллельного доступа - наоборот. В другого типа задачах без особых упущений удается принять за единицу информации страницы слов большого объема. Там тоже задержка не будет так важна.
Скажите пожалуйста, в качестве результата должны получится правила разработки и реализации алгоритмов на ПЛИС?
Я надеюсь, что для разработчики в том числе и схем на ПЛИС, не будет сложным транслировать результаты книги в описание на используемом ими HDL. Более того, я думаю не только мне, но и многим читателям будет интересно узнать о результатах таких экспериментов.
Т.е. задача книги шире, чем реализация алгоритмов с помощью известных ПЛИС ? А можно уточнить: задачи, решения которых будут описываться в книге, относятся к базовой математике? Решение задач оптимального управления не будет целью одного из разделов?
Не только ПЛИС:
Разработка под ASIC,
Поломать голову и нескучно скоротать вечер,
Некоторые методы можно использовать для проектирования производственных конвейерных линий и управления крупным автоматизированным предприятием.
В книге математика - всего лишь слуга.
В оптимальном управлении не специалист, но если кто-то обнаружит пересечения, можно вместе обдумать.
Клюнул на название, и честно говоря слегка "прифигел". Потому что 20 лет занимаюсь пректированием чипов, но после первого прочтения "вскользь" не понял вообще ничего. После второго, подробного прочтения, уже понял, что это алгоритмика, никаких кристаллов здесь нет и в помине, но материал вполне попадает под классификацию чипостроения в качестве логического дизайна. Причем дизайна весьма специфического, поскольку, как я понимаю, для имплементации рассматриваемых алгоритмов предлагается не использование процессора с ограниченным числом инструкций, а имплементация "в лоб" путем построения автомата (поправьте, если не прав). И вот здесь я оказался в тупике, поскольку сходу не смог придумать, для чего это может быть нужно. Т.е. автору я бы посоветовал включить в книгу и практические примеры, где эти алгоритмы могут быть использованы.
Еще небольшой комментарий по вводной части. В логическом дизайне время различают на физическое и логическое. Логическое время измеряется в шагах алгоритма, и может течь как с той же скоростью, что и физическое время (синхронная работа от внешних "часов"), так и без привязки к физическому времени (асинхронная работа). Соотвественно, автомат может проектироваться как для синхронной работы по шагам state <= next_state (Мур, Мили), так и с использованием параллельных процессов (модель Хаффмана). Это более широкая классификация, чем просто "дискретное время". Полагаю, автор предлагает проектирование именно синхронных автоматов.
Ни на что не претендую, просто высказал свое мнение человека - не из целевой аудиотрии, т.е. случайно заглянувшего.
Нет, нет, Вы все правильно сказали. Я не обидчивый: обратная связь, особенно с людьми из индустрии - это для меня просто подарок судьбы)
Да, я говорю именно об имплементации в лоб.
Применяется например в скоростной обработке сигналов (интересно что там F22?, не уж-то обычным CPU считают), девайсах для криптографии (майнить нынче выгодно тоже на асиках), тренировка и обработка на нейросетях, да что там, гуляя по улице в Москве, встретил человека, который FPGA под скоростной трейдинг перепрофилировал. Кто чем только не балуется!
Еще есть тенденция переноса расчётов в дата-центры. Почти для любой алгоритмической задачи, которая решается более чем за линейное время от своего размера и хорошо параллелится (та же сортировка или операция "найти все общие записи в двух таблицах", почти все алгоритмы на графах), в перспективе выгодно иметь отдельный специализированный девайс, который ее считает (при условии что в дата-центре его можно хорошенько загрузить).
В книге я собираюсь ограничиться только синхронными схемами. Однако когда речь идет о борьбе за скорость - это в том числе и борьба за частоту (то есть борьба против глубины). Мне видится (но я не настаиваю на своем видении), что все более продвинутое: много тактовых частот, разные клоковые зоны, срабатывание по обеим фронтам сигнала - требует каких-то отдельных технических приёмов, но не требует какой-то отдельной теории. Знаешь, как сделать синхронную схему, переделать ее в более продвинутую тоже сможешь.
Если вы дадите какие-то советы или исправите что-то в терминологии - тоже буду благодарен.
Интересно! Желаю не потонуть в объеме информации!
P.S. И несколько пожеланий, возникших после прочтения оглавления:
Присоединюсь к пожеланию korean_pilot и включить описание конечных автоматов в 1ую главу. Вы планируете подробно описать логическую (комбинационную) часть, но без регистров и автоматов не получится полноценного фундамента.
IMHO функции (комбинационные схемы) и автоматы - два важнейших фундамента этой области. И первое время было тяжело научиться всё разлагать на эти два понятия. А как научился - легко всё пошло ;).
Да, еще стоит дать подробное описание "стоимости" реализации: площади и времени/частоты, задержки (в тактах) и пропускной способности конвейеров (вернее как часто можно подавать новые данные в конвейер). Эти метрики очень необычны для "обычного" программирования, поэтому стоит ясно и подробно о них поговорить.
Успехов!
Ничего не понятно, но очень интересно. Подпишусь в недежде, что придет когда-нибудь тот день когда я начну понимать такие сложные темы.)
Подпишусь в надежде поумнеть и понять все то умное что было в статье выше)
Очень интересная тема, жду с нетерпением! Подскажите пожалуйста, куда планируете выкладывать?
Черновики буду выкладывать по частям на хабр. Я обещал каждую неделю по средам. В прошедшую среду не выкладывал, потому как хотел дописать логически завершенный кусок, который можно было бы уже обдумать или покритиковать. Этот кусок я почти завершил (от руки нада сделать иллюстрации и привязать их к тексту, а сам текст перенести из ворда в редактор хабра).
Спасибо за ответ, будем ждать!
По своему опыту (два издания книги "Deep RL Hands-On"), лучше сразу выбирать максимально удобный инструмент для написания текста и формат "исходника" этого текста, чтобы уменьшить телодвижения по конвертации его потом туда-сюда и внесения неизбежных правок.
Например, в моем случае издатель требовал ворд, и я намучился с ним из-за кривых формул, нестыковок версий, плывущих стилей и прочих ограничений. Но у Packt на ворде построен весь процесс корректуры, поэтому выбора не было. Была бы моя воля - я бы взял LaTeX и сэкономил бы себе несколько недель времени.
Но решать, конечно, вам.
Рад сообщить, что почти половину первой главы я наконец-то закончил.
Приглашаю оценить: https://habr.com/ru/post/530470/
прочитал список тем - все такое классное, прямо вспоминается план Дональда Кнута (там у него был первоначальный список "всего на 10-12 тем") :)
Но тем не менее - обеими руками за (и тоже надеюсь купить в бумаге после издания).
Алгоритмы на кристалле (анонс книги)