14 сент. 2009 г.

Патент на высокоуровневый синтез

На прошлой неделе готовил лекцию о языке SystemC и наткнулся на статью Stephen A. Edwards, «The Challenges of Synthesizing Hardware from C-Like Languages», о различных С-подобных языках, применяющихся для описания аппаратуры. Среди различных языков и инструментов была ссылка на американский патент № 6 226 776 о синтезе С в железо, который сейчас якобы принадлежит фирме Synopsys. Автор статьи описывает патент, как «претендующий на широкую поддержку языка ANSI C»: упоминается поддержка указателей, рекурсии, динамического распределения памяти.

Я заинтересовался этим патентом. Около 85 страниц из всех 108-и — это примеры на С и соответствующие им результаты синтеза на Верилоге. Ещё 14 страниц — это словесное описание всех примеров. И последние четыре страницы посвящены описанию формулы изобретения. Модели в основном представлены в виде цифровых автоматов, намного реже — data-flow модели. Как такового метода преобразования С в цифровой автомат там не было. Я обратил внимание на один пример, в котором из одной функции вызывались две другие.

int sum1 (int n)
{
    int i, sum = 0;
    for (i = 0; i < n; i++)
        sum += i;
    return sum;
}

int sum2 (int array[], int size)
{
    int i, sum = 0;
    for (i = 0; i < size; i++)
        sum += array[i];
    return sum;
}

int f1()
{
    int i;
    int array[10];
    int size = sizeof(array)/sizeof(*array);
    for (i = 0; i < size; i++)
        array[i] = i * 2;
    return sum1(size) + sum2(array, size);
}

* This source code was highlighted with Source Code Highlighter.

Перед тем, как читать дальше, подумайте: сколько состояний автомата нужно, чтобы выполнить этот алгоритм? Мне тоже сначала показалось, что должно быть немного. Но в предложенном варианте синтеза для выполнения этого алгоритма нужно 16 состояний автомата. Так как мой компилятор С++ в VHDL ещё не способен откомпилировать такой код, то решил нарисовать граф-схему алгоритма вручную.

Все функции уже встроены, и предполагается, что инициализация переменных происходит по сигналу reset. Таким образом, в этом автомате получается всего лишь семь состояний (см. Баранов С. И. Синтез цифровых автоматов).

Вот не могу понять: у них там в 2001 году не знали то, что у нас было известно ещё в 1974?

11 комментариев:

  1. Баранов как то у нас на лекции говорил, что в США ещё многого не знают, из того чем он сам занимался лет 20 назад :) Интересно, что на такие вещи вообще патенты заводятся..

    ОтветитьУдалить
  2. В нашем ауле не то, что Баранова, его книг не все инженеры видели. :)

    ОтветитьУдалить
  3. Нэ знаю, щто там в ващэм ауле, но в нащэм отличные бараны! Вах!

    ОтветитьУдалить
  4. Анонимный26.12.2010, 3:52

    Хм, а о каком автомате вообще шла речь? Думаю, что для данного примера можно сделать автомат только с одним состоянием. Все что более - будет избыточно.

    ОтветитьУдалить
  5. Речь идёт о композиции управляющего и операционного автомата. Ваше мнение об автомате с одним состоянием очень интересно, и хотелось бы узнать, как он работает.

    ОтветитьУдалить
  6. Анонимный26.12.2010, 13:27

    Владимир, всё дело в том, что Аффтар жжот прямо при постановке задачи, написав классный, но не оптимизированный алгоритм. Ведь если еще немного подумать, или даже еще порисовать - то даже тот алгоритм, который нарисовали Вы, можно склеить не только вдвое по горизонтали, но и вчетверо по вертикали.
    И если при этом инициализировать две необходимые для его работы переменные по сбросу - то можно оставить на ГСА всего один операционный "прямоугольничек". Если очень нравится - то оставим и одну условную вершину для того, чтоб определить конец выполнения алгоритма.
    Что касается памяти, то для реализации такого алгоритма в железе, по сути - требуется один 4-битный счетчик (наверно именно его "держал в уме" Аффтар, когда говорил о 16 состояниях) и 8-битный регистр, в котором будет накапливаться результат. Для 10 итераций 8 бит результата должно хватить.

    ОтветитьУдалить
  7. Спасибо за пояснения. Я согласен с вами.

    ОтветитьУдалить
  8. Анонимный26.12.2010, 13:34

    ... кстати, а если еще немного подумать - то вся эта штука (результат выполнения функции) вообще в результате является константой. Можно, наверно, и вообще без автомата обойтись ;)

    ОтветитьУдалить
  9. Я вот ещё подумал, что на исходный пример на Си++ можно натравить разные высокоуровневые трансформации, вроде вычисления констант, развертки циклов и прочее. В результате окажется, что значение никаких вычислений нет вообще, потому что результат всегда константный. :)

    ОтветитьУдалить
  10. Анонимный26.12.2010, 13:52

    Почти одинаково мыслим, коллега! :)
    ... кстати, про интересные оптимизационные задачи, так сказать, "с ухмылкой":

    - Необходимо нарисовать схему "черного ящика" с тремя входами и тремя выходами, функционал которого можно описать ТРЕМЯ независимыми инверторами, с использованием ТОЛЬКО ДВУХ инверторов и неограниченного количества элементов И и ИЛИ.

    ОтветитьУдалить
  11. Ох, слышал я о такой задаче, лет пять назад. Но не садился. :)

    ОтветитьУдалить

Темы

2012 (2) амазон (1) анпакинг (1) артемий лебедев (4) атн (1) аудио (1) аэропорт (1) безопасность (3) бизнес (1) билайн (1) блог (2) будущее (2) видео (11) википедия (5) вымысел (16) гагарин (1) герман (1) гитхаб (1) гугл (3) дед мороз (1) декабрь (1) демотиватор (2) дети (2) дизайн (13) диссертация (2) документация (1) друзья (5) евпатория (1) евро-2012 (1) жадность (1) заяц (1) идея (1) имейл (1) инстаграм (1) интервью (5) интересное (20) интерфейс (13) история (7) как_выжить (4) календарь (1) капитализм (1) картина (1) кмб (6) книга (6) коллекция (4) компилятор (2) конкурс (5) космос (1) лаборатория (1) либералы (1) лингво (1) лузер (6) макаренко (2) макдональдс (2) математика (1) медиапорт (1) ментор (1) металлика (1) металлист (2) метро (7) микрософт (6) миргород (1) москва (2) музыка (3) наркомания (1) новости (17) образование (3) оптимизация (5) основы (14) открытки (3) ошибка (11) памятник (1) патриотизм (3) плагиат (1) плата (1) погода (3) поиск (1) политика (2) полтава (2) праздник (1) программирование (15) прошлое (2) путешествия (8) рейтинг (1) рендер (1) рисунок (2) русские (1) русский язык (1) сайт (4) санкт-петербург (1) сапр (7) сеть (1) си++ (1) синтез (1) системси (1) скриншот (40) социализм (1) соцопрос (3) спектрум (2) спорт (2) срач (2) статистика (1) такси (1) тбб (3) твитер (9) тимошенко (1) украина (5) униан (1) фан (30) фокус (1) фото (39) фотошоп (1) фурсенко (1) футбол (2) хабр (1) харьков (21) хнурэ (19) хобби (4) цитата (2) чехия (1) школа (1) эпл (1) эхостар (1) юмор (1) яндекс (1) clang (2) doxygen (1) english (3) ios (1) llvm (1) msdn (1) outlook (1) PHP (1) stackoverflow (1)

Поиск

Читатели