Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Вт мар 19, 2024 15:56

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 14 ] 
Автор Сообщение
 Заголовок сообщения: Однобитный интерфейс к памяти команд
СообщениеДобавлено: Пн дек 21, 2009 02:05 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Раз уж пошла такая пьянка с экономией битов на команду, то вот еще одна идея - последовательный интерфейс к памяти команд :)
Чем это сразу хорошо? Тем, что последовательный интерфейс очень быстр и не имеет проблем с синхронизацией отдельных разрядов. В пределе это может быть самосинхронизируемый протокол. Еще это хорошо потенциальной возможностью получать высокую степень упаковки команд - об этом ниже.

Что мы можем получить "просто так"? Ну например, десериализатор на входе, и делать из одного бита 4, 8, 16 и т.д. Но такая схема оказывается прозрачной для прочих компонентов процессора, потому что команда у него все равно фиксированной ширины. Но тут мы можем выбрать разные варианты кодирования. К примеру: два нулевых бита подряд являются признаком конца команды. Тогда мы будем иметь такие команды

0
1
01
10
11
001 нельзя, есть запрещенная последовательность
010
011
100 нельзя, есть запрещенная последовательность

И так далее. И тут уже интересно то, что при разработке программ можно провести частотный анализ команд (причем делать это как для модели процессора, так и для каждой программы, если процессор допускает динамическую перезагрузку таблиц кодирования). Тогда появляются шансы получить существенное сокращение объемов программы, потому что уже для кодов 0 и 1 размер получается всего 3 бита (между командами идут "00"), и если таких команд будет достаточно много, то даже 4-х битный процессор начинает нервничать :)

Надо сказать, что идея не особо нова, оригинальна и перспективна. Собственно, вначале и было написано "раз уж пошла такая пьянка" :)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 07:47 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Была подобная мысля, только кажется, что "запрещенных последовательностей" не должно быть (или они называться должны иначе).
Просто они будут выполнять некую функцию.
Например, появление "00" может означать, что все предыдущие накопленные биты из потока являются целостной командой, которую надо исполнить, но это, имхо, сильно расточительно.

Лучше сделать так, что несколько комбинаций некоего минимального размера являются простейшими командами, а оставшиеся комбинации являются префиксами для команд большей разрядности. Например, 4-битные команды от 0000 до 1100 - все исполнимы, а 11xx являются префиксами и вслед за последовательностю 1100 следует несколько бит модификатора (не обязательно 4 бита, их может быть и 1, и 2, и 132 в зависимости от требуемой системы команд.

Команды при этом могут быть самые разные.
Например команда LIT должна исполняться так: "выбрать из потока 8(16/32/64) последующих бит в качестве операнда и положить на стек, независимо, от наличия/отсутствия запрещенных комбинаций, по окончании выборки операнда сбросить схему блока выделения команд в начальное состояние."
А сама команда LIT - это 4-хбитный префикс с 2 битами модификатора, который и определяет сколько последующих бит из потока брать в качестве операнда.

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 09:48 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
я не вижу смысла в таком подходе. Средняя длина команды будет больше. Уж лучше взять те же 5 бит на команду или 6 и иметь гарантированно 32-64 команды, чего для Форта вполне достаточно. Да и дешифратор команд будет проще.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 10:24 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
mOleg писал(а):
я не вижу смысла в таком подходе. Средняя длина команды будет больше. Уж лучше взять те же 5 бит на команду или 6

Здесь сразу возникает вопрос: на каких примерах проводилась оценка? :) Потому что говорить о средней длине команды можно только после того, как получены данные о частотном распределении команд. Тем более что кодирование с запрещенной последовательностью - прочитанный мной в незапамятные времена пример простейшего алгоритма сжатия. Так что говорить при этом что такой подход увеличивает среднюю длину, несколько странно. Другое дело, что время выполнения может оказаться больше, потому что последовательная память с десериализатором все же не в 100 раз быстрее, чем остальные узлы процессора.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 10:45 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
WingLion писал(а):
Например, появление "00" может означать, что все предыдущие накопленные биты из потока являются целостной командой, которую надо исполнить, но это, имхо, сильно расточительно.

А так и есть, входной десериализатор работает, пока не увидит 00, тогда он и понимает, что все принятое - это команда. Расточительно или нет - зависит от частоты появления команд. Если их 5-6, то экономия будет иметь место. Но в любом случае надо оценивать по конкретным примерам.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 16:43 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
00
100
1100
0100
10100
11100
01100
010100
011100
110100
101100
111100

и так далее.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 17:54 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
а почему бы не декодировать дерево хаффмана? зачем нужны стоп-комбинации? и ещё, префиксный код, кстати, не самый эффективный, арифметическое кодирование (в его различных вариантах вроде ELS Coder или Range Coder) лучше.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 19:00 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
garbler писал(а):
а почему бы не декодировать дерево хаффмана? зачем нужны стоп-комбинации?

В первом посте не случайно написано "например". Декодировать можно как угодно, рассматривается подход "сократим ширину интерфейса, нацелившись на получение выигрыша за счет использования часто встречающихся коротких кодов". Что именно подойдет в конкретном случае - отдельный вопрос.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 21:51 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
Была подобная мысля, только кажется, что "запрещенных последовательностей" не должно быть (или они называться должны иначе).
Просто они будут выполнять некую функцию.
Экономия на экономии едет и экономией поганяет. :D Это, видимо, хорошо. Но я не пойму, что же при этом экономится - ведь скорость выполнения не вырастает оттого, что мы больше команд вложим в меньший объём памяти, всё-равно процессор должен исполнить операции в заданное количество тактов и опередить сам себя никак не может. Тогда экономится память? Или скорость выборки операций из памяти?

Вообще, идея напоминает мне вот что
http://algolist.ru/compress/standard/arithm.php
или
http://algolist.ru/compress/standard/huffman.php


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 22:00 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
Тогда экономится память? Или скорость выборки операций из памяти?

Да, экономится память. А скорость выборки ухудшается незначительно, поскольку последовательный интерфейс очень быстр сам по себе.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 22:00 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
вопрос писал(а):
Но я не пойму, что же при этом экономится

основная проблема скорости выполнения = это скорость доступа к памяти.
память-то общая. Данные в стековых архитектурах достаточно хорошо кэшируются самим стеком.
а код тянуть из памяти надо непрерывно. Чем более широкая команда тем больше надо данных прокачать между памятью и процессором.
Вот, при 4-х битах на команду и разрядности данных 32 бита за раз читается 8 команд, которые можно исполнять на частоте в 8 раз выше, чем скорость обмена данными с памятью. На широкой команде будет уже другая ситуация, если ширина команды 32 бита, то за одно обращение к памяти будет вытягиваться одна команда 8)

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 22:03 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
вопрос писал(а):
Но я не пойму, что же при этом экономится - ведь скорость выполнения не вырастает оттого, что мы больше команд вложим в меньший объём памяти, всё-равно процессор должен исполнить операции в заданное количество тактом и опередить сам себя никак не может. Тогда экономится память? Или скорость выборки операций из памяти?


"Экономика должна быть экономной" (с)...

Чем больше команд упакуется в один объем, тем больше будет и скорость исполнения этих команд.
Потому что скорость исполнения ограничивается не процессором, а скоростью выборки команд из памяти,
а она по сути является скоростью работы памяти, помноженной на количество команд, упакованных в одном слове.
Сумеем упаковать 10 команд в 32 бита - значит, можно добиться 10кратного увеличения скорости исполнения команд.
За счет удесятерения частоты работы процессора по отношению к частоте работы памяти (или даже распараллеливанием исполнения команд).

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн дек 21, 2009 22:37 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
Чем больше команд упакуется в один объем, тем больше будет и скорость исполнения этих команд.

Цитата:
основная проблема скорости выполнения = это скорость доступа к памяти.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт дек 22, 2009 00:28 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
mOleg писал(а):
основная проблема скорости выполнения = это скорость доступа к памяти.

Сама по себе память - блок с предсказуемыми и весьма неплохими характеристиками. Проблема процессоров - это проблема пропускной способности, формирования адреса и разрешения конфликтов одновременного доступа к данным на разных стадиях конвейера.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB