"We need to preserve the legacy of this computer. In other words, future generations need to understand, you know, we all came from two handred years from now. I want them to be able to see the Apollo Guidance Computer".
Чтобы компенсировать ошибку нужно увеличить число используемых мышей. Их у нас в избытке, так что не проблема. Можно попытаться натянуть код Хемминга на эту задачу.
Использование дополнительных пустых пробирок это что-то типа бита четности позволяющего понять (с опеределнной вероятностью) была ошибка или нет.
Ок, спасибо. Да, Ваш алгоритм эффективней, но мышей на водопой придется сводить 27+1 раз, а в моём всего 20+1. :-) Один последни раз требуется для проверки действитетельно ли в найденой пробирке яд. Также в моём предусметрена проверка на этапах которая может выявить ошибку заблаговременно. В таком деле я бы предпочел немного перебдеть. :-)
Если допустить автоматическое смешивание и автоматическую регистрацию результатов тестирования, то, наверное, более правильный алгоритм мог бы выглядет так:
Имеем 1000 пробирок с неизвестным составом, нумеруем пробирки начинается с 0 до 999.
Добавляем еще 24 пустые пробирки (всего от 0 до 1023), это будут контрольные пробирки для проверки правильности исполнения алгоритма по ходу исследования.
Создаем вектор длиной 1024 битов. Каждый бит этого вектора ассоциирован с одной из пробирок, фактически номер бита совпадает с номером пробирки.
Начинаем цикл пока оставшееся количество неисследованных пробирок > 1.
Формируем 8 векторов устанавливая в них биты следующим образом:
в нулевом векторе устанавливаем биты: 0, 8, 16, 24,...,1016;
в первом биты: 1,9,17,25,...,1017;
во втором векторе: 2,10,18,26,...,1018; и так продолжаем до
вектора 7 в котором устанавливаем биты: 7,15,23,31,...,1023.
Используем эти 8 векторов для формирования 8-ми смесей согласно правилу: если соответствующий бит установлен, то в данную смесь добавляется проба из пробирки с номером равной номеру бита.
Проводим тест: поим 7 мышей различными смесями (из 8 шт), одну смесь можно не тестировать.
Ждем 1 час результатов теста - одна из мышей должна погибнуть, или не погибнуть ни одной.
Выбираем пробирки для следующей итерации:
Если погибла только одна мышь, то выбираем для следующей итерации те пробирки которые были отмечены битом в её смеси.
Если не погибла ни одна мышь, то выбираем смесь номер 7 (ту, что не тестировали).
Если погибло две и более мыши, то в процессе эксперимента произошла ошибка (не врено произведены смеси или некачественные мыши). Эксперимент признаем неудачным и начинаем сначала.
Из отобранного вектора получаем 1024/8 = 128 пробирок для тестирования на следующей итерации. Сводим задачу к 128 пробиркам и 9-ю мышам (одна мышь израсходована ;)).
Проверяем содержимое вектора на наличие в нём пустых пробирок. Если в векторе все пробирки пустые, то произошла ошибка - останавливаем исследование.
Повторяем цикл.
В процессе решения приходим к следующей последовательности подзадач и состояний:
Шаг 1. 1024 пробирки, чередование 8, количество живых мышей после завершения - 9 шт.
Шаг 2. 128 пробирок, чередование 8, количество живых мышей после завершения - 8 шт.
Шаг 3. 16 пробирок, чередование 4, количество мышей после завершения - 7 шт.
Шаг 4. 4 пробирки, чередование 1, количество мышей после завершения - 6 шт.
Итого: Исследование длится 4 часа, 4 мыши израсходовано, всего поили мышей 7+7+3+3=20 раз.
Если результирующий номер пробирки с ядом > 999, то есть в финал вышла пустая пробирка, то в опыте возникла ошибка и опыт повторяется.
Пустые пробирки можно рассматривать как Redundancy Check и исходя из этого еще немного уменьшить число тестов, но я пока не придумал как. :-)
Тут результат может зависить от чего угодно - от качества пайки, от качества питания (пульсации), от того как плату обрабатывали в процессе сборки (мыли в ультразвуковой или струйной машине, при какой температуре проводилась пайка и т.д.)
Я полагал что они научились отключать блоки динамическй памяти и таким путём делают многократные измерения энтропии, потом берут наиболее подходящий вариант. Оказалось всё гораздо прозаичнее.
Дозатор на 1000 пробирок если и есть в природе, то это дико сложное изделие. Ну и мышей поить придется всё равно вручную, никакими форсунками напоить их не получится. Но основная проблема в том, что мышами придется жонглировать как клоун шарами в цирке, а это почти стопроцентная вероятность ошибки.
В Ваших решениях есть существенный недостаток - сложность и запутанность реализации. Лаборант который будет поить мышей c очень большой вероятностью сделает ошибку - случайно напоит не ту мышь не из той пробирки (человек не в состоянии выполнить 1000*10 различных действий не совершив хотя бы одну ошибку). Результат будет быстрый, но фатально неверный. Если использовать метод половинчатого деления, то задача для лаборанта существенно упрощается, но результат будет готов через 10 часов, при этом ошибка контроллируема в процессе эксперимента. Более того, если повезет, Вы сможете решить задачу за 1 час использовав только один пробник (одну мышь).
Также важен вопрос о концентациях вещества. Если напоить одну мышь из ста различных пробирок, то концентрация яда может понизиться до гомеопатических значений, что приведет к ложным результатам.
Вы посмотрите ютуб каналы американских техноархеологов, они не такую архаику восстанавливают и без документации. Это долго и очень муторно, приходится много информации собирать по крупицам, часть железа изготавливать самостоятельно или эмулировать. А тут почти не тронутая машина, скорее всего и доки сохранились.
Это всё равно что запустить 40 лет простоявший во дворе автомобиль, только сложнее
Грузовичок 1946 года провалялся в лесу 50 лет - восстановили и завели.
Ваша текущая реализация хороша своей простотой, она легка для понимания и вхождения в тему, но работает только в сферическом вакууме. Не спорю, какие-то простые приложения на нём можно реализовать уже сейчас. Однако, как только потребуется взаимодействие с внешними устройствами и динамической памятью, тут же вырастает проблема с регулированием доступа к шине и ожидания готовности устройств или памяти. Не менее сложная задача - обработка внешних прерываний. Для решения этих проблем в интерфейсе вычислительных ядер должны быть предусмотрены соответствующие сигналы и ядро должно быть спроектировано соответствующим образом - как минимум останов конвейра при отсутствии сигнала готовности. Есть несколько способов реализовать арбитраж и весь интерес как раз состоит в таких решениях. В общем, ждем "ч.2". :-)
На всякий случай, если Вы вдруг не знали, есть отличная Книга Двух Харрисов где детально обрисованы три реализации ядра RISC-V: однотактовая, многотактовая и конвейерная. Книга написана очень увлекательно, я её прочёл с большим удовольствием. RTL дизайнером себя не считаю, но свои ядра написать могу. :)
В интерфейсе модуля который Вы приводите в статье нет никакого намёка на арбитраж, он выглядит как однотактовый процессор без схем ожидания. У Вас уже есть конвейерная реализация ? Было бы интересно почитать. Особенно про то, как разрешены различные зависимости (hazards).
Icarus Verilog генерирует нетлист, но он не может проверить синтезируемость под конкрентый ПЛИС. Фактически это симулятор который используют для верификации и дебага. В сочетании с gtkwave - очень мощный тул.
Подступиться к Verilog-у совершенно не проблема, установите тулы и побалуйтесь с лабораторками от Юрия Панчулы, желательно имея в руках какую нибудь из поддерживаемых плат, но это не обязательно. Порог входжения в эту тему сейчас очень низкий - пару ночных сейшнов и можно писать своё ядро RISC-V. ;-)
Цитата из видео:
"We need to preserve the legacy of this computer. In other words, future generations need to understand, you know, we all came from two handred years from now. I want them to be able to see the Apollo Guidance Computer".
Чтобы компенсировать ошибку нужно увеличить число используемых мышей. Их у нас в избытке, так что не проблема. Можно попытаться натянуть код Хемминга на эту задачу.
Использование дополнительных пустых пробирок это что-то типа бита четности позволяющего понять (с опеределнной вероятностью) была ошибка или нет.
Ок, спасибо. Да, Ваш алгоритм эффективней, но мышей на водопой придется сводить 27+1 раз, а в моём всего 20+1. :-) Один последни раз требуется для проверки действитетельно ли в найденой пробирке яд. Также в моём предусметрена проверка на этапах которая может выявить ошибку заблаговременно. В таком деле я бы предпочел немного перебдеть. :-)
Как миниму одна потеря должна быть всегда, иначе это не исследование, а догадка. :)
Опишите свой алгоритм пожалуйста.
Если допустить автоматическое смешивание и автоматическую регистрацию результатов тестирования, то, наверное, более правильный алгоритм мог бы выглядет так:
Имеем 1000 пробирок с неизвестным составом, нумеруем пробирки начинается с 0 до 999.
Добавляем еще 24 пустые пробирки (всего от 0 до 1023), это будут контрольные пробирки для проверки правильности исполнения алгоритма по ходу исследования.
Создаем вектор длиной 1024 битов. Каждый бит этого вектора ассоциирован с одной из пробирок, фактически номер бита совпадает с номером пробирки.
Начинаем цикл пока оставшееся количество неисследованных пробирок > 1.
Формируем 8 векторов устанавливая в них биты следующим образом:
в нулевом векторе устанавливаем биты: 0, 8, 16, 24,...,1016;
в первом биты: 1,9,17,25,...,1017;
во втором векторе: 2,10,18,26,...,1018; и так продолжаем до
вектора 7 в котором устанавливаем биты: 7,15,23,31,...,1023.
Используем эти 8 векторов для формирования 8-ми смесей согласно правилу: если соответствующий бит установлен, то в данную смесь добавляется проба из пробирки с номером равной номеру бита.
Проводим тест: поим 7 мышей различными смесями (из 8 шт), одну смесь можно не тестировать.
Ждем 1 час результатов теста - одна из мышей должна погибнуть, или не погибнуть ни одной.
Выбираем пробирки для следующей итерации:
Если погибла только одна мышь, то выбираем для следующей итерации те пробирки которые были отмечены битом в её смеси.
Если не погибла ни одна мышь, то выбираем смесь номер 7 (ту, что не тестировали).
Если погибло две и более мыши, то в процессе эксперимента произошла ошибка (не врено произведены смеси или некачественные мыши). Эксперимент признаем неудачным и начинаем сначала.
Из отобранного вектора получаем 1024/8 = 128 пробирок для тестирования на следующей итерации. Сводим задачу к 128 пробиркам и 9-ю мышам (одна мышь израсходована ;)).
Проверяем содержимое вектора на наличие в нём пустых пробирок. Если в векторе все пробирки пустые, то произошла ошибка - останавливаем исследование.
Повторяем цикл.
В процессе решения приходим к следующей последовательности подзадач и состояний:
Шаг 1. 1024 пробирки, чередование 8, количество живых мышей после завершения - 9 шт.
Шаг 2. 128 пробирок, чередование 8, количество живых мышей после завершения - 8 шт.
Шаг 3. 16 пробирок, чередование 4, количество мышей после завершения - 7 шт.
Шаг 4. 4 пробирки, чередование 1, количество мышей после завершения - 6 шт.
Итого: Исследование длится 4 часа, 4 мыши израсходовано, всего поили мышей 7+7+3+3=20 раз.
Если результирующий номер пробирки с ядом > 999, то есть в финал вышла пустая пробирка, то в опыте возникла ошибка и опыт повторяется.
Пустые пробирки можно рассматривать как Redundancy Check и исходя из этого еще немного уменьшить число тестов, но я пока не придумал как. :-)
Тут результат может зависить от чего угодно - от качества пайки, от качества питания (пульсации), от того как плату обрабатывали в процессе сборки (мыли в ультразвуковой или струйной машине, при какой температуре проводилась пайка и т.д.)
Я полагал что они научились отключать блоки динамическй памяти и таким путём делают многократные измерения энтропии, потом берут наиболее подходящий вариант. Оказалось всё гораздо прозаичнее.
Сижу, перелистываю книгу "The Practice of Programming" от B. Kernighan и R.Pike, и вижу следующее:
И тут Ваша статья. Совпадение ? Не думаю. ;)
Дозатор на 1000 пробирок если и есть в природе, то это дико сложное изделие. Ну и мышей поить придется всё равно вручную, никакими форсунками напоить их не получится. Но основная проблема в том, что мышами придется жонглировать как клоун шарами в цирке, а это почти стопроцентная вероятность ошибки.
В Ваших решениях есть существенный недостаток - сложность и запутанность реализации. Лаборант который будет поить мышей c очень большой вероятностью сделает ошибку - случайно напоит не ту мышь не из той пробирки (человек не в состоянии выполнить 1000*10 различных действий не совершив хотя бы одну ошибку). Результат будет быстрый, но фатально неверный. Если использовать метод половинчатого деления, то задача для лаборанта существенно упрощается, но результат будет готов через 10 часов, при этом ошибка контроллируема в процессе эксперимента. Более того, если повезет, Вы сможете решить задачу за 1 час использовав только один пробник (одну мышь).
Также важен вопрос о концентациях вещества. Если напоить одну мышь из ста различных пробирок, то концентрация яда может понизиться до гомеопатических значений, что приведет к ложным результатам.
Вы посмотрите ютуб каналы американских техноархеологов, они не такую архаику восстанавливают и без документации. Это долго и очень муторно, приходится много информации собирать по крупицам, часть железа изготавливать самостоятельно или эмулировать. А тут почти не тронутая машина, скорее всего и доки сохранились.
Грузовичок 1946 года провалялся в лесу 50 лет - восстановили и завели.
Заводить надо с умом, а не просто "подать питание" и ждать пока бахнет. Всё это вполне возможно. Было бы что заводить.
Не, не так. Сначала изготовить прототип на ПЛИС, оттестировать, а потом повторить его на TTL (ЭСЛ) логике.
Будем надеяться, что её удастся запустить. Если требуется помощь с эмуляцией каких-то нерабочих устройств на ПЛИС - обращайтесь, помогу в меру сил.
Из статьи не понятно в каком состоянии этот экземпляр ЭВМ ЕС-1055М ? Машина всё еще "на ходу" или уже на половину раздербанен ?
Ваша текущая реализация хороша своей простотой, она легка для понимания и вхождения в тему, но работает только в сферическом вакууме. Не спорю, какие-то простые приложения на нём можно реализовать уже сейчас. Однако, как только потребуется взаимодействие с внешними устройствами и динамической памятью, тут же вырастает проблема с регулированием доступа к шине и ожидания готовности устройств или памяти. Не менее сложная задача - обработка внешних прерываний. Для решения этих проблем в интерфейсе вычислительных ядер должны быть предусмотрены соответствующие сигналы и ядро должно быть спроектировано соответствующим образом - как минимум останов конвейра при отсутствии сигнала готовности. Есть несколько способов реализовать арбитраж и весь интерес как раз состоит в таких решениях. В общем, ждем "ч.2". :-)
На всякий случай, если Вы вдруг не знали, есть отличная Книга Двух Харрисов где детально обрисованы три реализации ядра RISC-V: однотактовая, многотактовая и конвейерная. Книга написана очень увлекательно, я её прочёл с большим удовольствием. RTL дизайнером себя не считаю, но свои ядра написать могу. :)
В интерфейсе модуля который Вы приводите в статье нет никакого намёка на арбитраж, он выглядит как однотактовый процессор без схем ожидания. У Вас уже есть конвейерная реализация ? Было бы интересно почитать. Особенно про то, как разрешены различные зависимости (hazards).
А как Вы реализовали временное отключение обновления SDRAM, причем, небольшой её области ?
В Вашей статье тоже не все схемы генерируют синус. ;)
Icarus Verilog генерирует нетлист, но он не может проверить синтезируемость под конкрентый ПЛИС. Фактически это симулятор который используют для верификации и дебага. В сочетании с gtkwave - очень мощный тул.
Подступиться к Verilog-у совершенно не проблема, установите тулы и побалуйтесь с лабораторками от Юрия Панчулы, желательно имея в руках какую нибудь из поддерживаемых плат, но это не обязательно. Порог входжения в эту тему сейчас очень низкий - пару ночных сейшнов и можно писать своё ядро RISC-V. ;-)