автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Устройства умножения на основе параллельных продукционных алгоритмов

Введение.

Глава 1. Аналитический обзор существующих средств умножения чисел и сущность предлагаемого подхода.

1.1. Общие сведения. Краткая история.

1.2. Особенности классификации методов умножения.

1.3. Средства аппаратной поддержки методов умножения.

1.3.1. Аппаратная поддержка методов умножения в универсальных процессорах фирмы Intel.

1.3.2. Аппаратная поддержка методов умножения в RISC процессорах.

1.3.3. Аппаратная поддержка методов умножения в DSP.

1.3.4. Аппаратная поддержка методов умножения в ПЛИС.

1.3.5. Аппаратная поддержка методов умножения в специализированных устройствах

1.4. Программная поддержка методов умножения.

1.5. Побудительные причины исследования и сущность предлагаемого подхода к созданию устройств умножения.

1.6. Выводы.

Глава 2. Разработка математические модели умножителя.

2.1. Основные принципы организации процесса умножения.

2.2. Основные понятия параллельных вычислений

2.3. Алгоритмы параллельных подстановок.

2.3.1. Алфавит, слово, переменное и обобщённое слово.

2.3.2. Определение подстановки, параллельные подстановки.

2.4. Построение модели данных.

2.5. Разработка математической модели процесса символьного умножения.

2.6. Выводы.

Глава 3. Разработка алгоритма, реализующего способ умножения, его проверка с использование математических моделей и экспериментальных данных.

3.1. Построение последовательного алгоритма умножения.

3.2. Построение параллельного синхронного алгоритма умножения.

3.3. Построение параллельного асинхронного алгоритма умножения.

3.4. Проверка способа умножения с использованием искусственных и полученных в результате математического моделирования данных.

3.5. Оценка скорости работы алгоритмов при реализации на универсальных процессорах.

3.6. Выводы.

Глава 4. Исследование и разработка аппаратных средств метода символьного умножения.

4.1. Специализированное устройство №1. Параллельный синхронный умножитель.

4.2. Специализированное устройство №2. Параллельный асинхронный умножитель.

4.3. Выводы.

Глава 5. Оценка скоростных характеристик разработанных специализированных устройств.

5.1. Краткое описание устройства (аналога), реализующего синхронное матричное умножение.

5.1.1. Структура и алгоритм работы устройства синхронного матричного умножения.

5.1.2 Быстродействие устройства (аналога) синхронного матричного умножения.

5.2. Быстродействие предлагаемого устройства параллельного синхронного умножения.

5.3. Быстродействие предлагаемого устройства параллельного асинхронного умножения.

5.4. Выводы.

Стремительный переход современных систем управления и связи на цифровые стандарты обработки и передачи данных, привёл к необходимости обрабатывать с высокой скоростью достаточно большие объёмы цифровой и символьной информации. Сложная обработка и фильтрация сигналов, например, распаковка сжатых аудиоданных и видеоданных, фильтр Собеля, быстрое преобразование Фурье, преобразование Уолша-Адамара, маршрутизация информационных потоков, генераторы хаотических последовательностей [15], требует применения высокопроизводительных цифровых и символьных вычислительных систем. Одной из самых часто выполнимых операций в данных алгоритмах является умножение. Следовательно, повышение эффективности выполнения операции умножения позволит повысить общее быстродействие вычислительных систем.

Над проблемами высокоскоростной обработки числовой информации работали известные исследователи, такие как Каменев А.В., Каляев А.В., Марков А.А, Нагорный М.Н., Бандман O.JI, Ачасова С.М. Были созданы высокопроизводительные арифметические алгоритмы и устройства последовательной, параллельной и конвейерной обработки, между тем, всё большее количество информации представляется не в числовом, а в символьном виде, хранимом во множестве электронных документов: базы данных, электронные таблицы и текстовые файлы. В связи с этим широкое распространение получили методы обработки символьной информации, базирующиеся на продукционной парадигме, которая позволяет эффективно обрабатывать массивы символьной информации и создавать высокоэффективные устройства. Над проблемами высокопроизводительной продукционной обработки информации работали известные исследователи, такие как Марков А.А.,

Нагорный М.В., Бандман O.JL, Ачасова С.М., Book R.V., Kung N.T., и другие.

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

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

Практическая часть решаемой проблемы заключается в создании алгоритма высокопроизводительного параллельного умножителя, разработке технических решений устройств умножения, уровень разработки которых соответствует требованиям постановки НИОКР по созданию специализированных СБИС для умножения чисел, представленных в символьной форме с фиксированной точкой и удвоенной разрядностью произведения, с последующим округлением результата.

Оценка производительности нейровычислителей использует такие показатели, как CPS (connections per second) - число соединений (умножений с накоплением) в секунду (оценивается производительность), ММАС - миллионов умножений с накоплением в секунду. Эти показатели позволяют судить о том, что производительность нейровычислений прямо пропорциональна производительности и количеству подсистем умножения [14]. Создаваемые системы обработки сигналов реального времени (ДСП) используют базисную технологию асинхронного матричного умножения, систолические структуры и комбинации многоразрядных сумматоров, что позволяет производить вычисления за 1 такт процессора с гарантированным временем получения результата.

По совокупности приведённых обстоятельств создание высокоскоростных асинхронных умножителей с однородной компактной структурой остаётся актуальным и перспективным [13].

Основная часть диссертационной работы выполнялась в рамках НИР по распоряжению Госкомвуза № 10-36-41, ИН/10-20-03 от 16.03.92 г. (пролонгация до 2001г.), проводимой на кафедре ПО ВТ в Курском государственном техническом университете при непосредственном участии автора данной работы.

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

Поставленная цель достигается решением следующих задач:

1. Разработать модель данных и систему параллельных продукций для выполнения операции умножения чисел в формате с фиксированной точкой.

2. Разработать и исследовать систему параллельных подстановок на наличие опасных и неопасных пересечений, завершаемость вычислений и обеспечение однозначности формируемого результата.

3. Создать программные модели для исследования логической состоятельности способов и алгоритмов, а также для исследования скорости решения задачи умножения.

4. Разработать ряд специализированных устройств для решения задач символьного умножения на основе полученных алгоритмов и произвести оценку скоростных характеристик, аппаратных затрат разработанных устройств, а также провести сравнительный анализ разработанных устройств с устройствами аналогами.

Объектом исследования диссертационной работы являются: процессы символьного умножения, алгоритмические системы, конструктивные процессы, программная модель и технические средства их реализации.

Методы исследования базируются на математическом аппарате теории параллельных подстановок, асинхронных вычислений, теории алгоритмов, теории конечных автоматов и проектирования ЭЦВМ, конструктивной математической логики.

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

Получены следующие новые результаты:

1. Разработана модель данных, позволяющая представлять числовые нормализованные данные с фиксированной точкой в символьном виде, пригодном для обработки системой параллельных продукций.

2. Впервые разработана система параллельных продукций и выполнено её исследование и обоснование, которая позволяет выполнять матричное умножение двух чисел, заданных в формате с фиксированной точкой. При этом предлагается использовать две параллельные продукции для формирования частичных сумм произведения и их сложения, что обеспечивает функциональную полноту преобразований операндов при выполнении умножения.

3. В результате теоретических исследований установлена завершаемость и однозначность системы параллельных продукций умножения, что позволяет получить необходимые показатели для выбора средств акселерации процессов обработки операндов при разработке перспективных устройств умножения.

4. Созданы программные модели (на основе разработанных способов и алгоритмов синхронного и асинхронного умножения) с помощью которых произведена оценка логической состоятельности и скоростных характеристик алгоритмов, реализующих нечисловые (символьные) способы умножения.

5. Разработан способ системно-структурной организации умножителей синхронного и асинхронного типов и выполнены для каждого из них технические решения элементов однородной среды и обобщенные структуры умножителей, достигающие высоких показателей скорости выполнения матричного умножения по отношению к устройству аналогу. В результате применения способа создан новый класс устройств в виде нечисловых умножителей, функционирующих на основе параллельных подстановок. Сравнительный анализ самого скоростного известного матричного устройства умножения (аналог) и разработанного матричного синхронного умножителя показал, что он имеет скоростное преимущество в 3 - 5 раз, а аппаратная экономия - до 5 раз. Для матричного асинхронного варианта реализации устройства умножения скоростное преимущество - до 1.5 раз при росте аппаратных затрат - до 2 раз по отношению к разработанному синхронному умножителю.

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

- высокая скорость умножения достигается за счёт массового распараллеливания операций генерации частичных произведений и их суммирования;

- матричная структура с малым временем задержки элемента позволяет разрабатывать оптимальную топологию кристалла и использовать высокие тактирующие частоты;

- асинхронная реализация позволяет использовать вентили схемы с максимальной частотой, превосходящей синхронный вариант устройства в несколько раз;

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих научных конференциях, съездах и семинарах:

- V Научно-технической конференции с международным участием "Материалы и упрочняющие технологии-97", Курск, Россия, 1997 год;

- Международная техническая конференция "Медико-экологические информационные технологии", Курск, Россия, 1998 год (2 доклада, по теме "Использование систем продукций А.А. Маркова для разработки суммирующих и множительных устройств" и "Вариант вычисления обратной функции на примере Y=Log2X и Y=2X с использованием символьного умножения" );

- I Всероссийской научно-технической конференции, часть XII "Компьютерные технологии в науке, проектировании и производстве",

Нижний Новгород, Россия, 1999 год (2 доклада, по теме "Разработка суммирующих и множительных устройств с использованием систем продукций" и "Применение алгоритмов вычисления обратной функции Y=f-l(X) для получения значений прямых функций Y=f(X) с использованием методов символьного умножения").

Основные положения, выносимые на защиту:

1. Модель представления числовых данных в символьной форме.

2. Система параллельных подстановок для выполнения операции умножения (формирование частичных произведений и их параллельного суммирования).

3. Результаты исследования скоростных характеристик алгоритмов и устройств синхронного и асинхронного умножения, реализующие разработанную систему параллельных подстановок.

4. Технические решения специализированных устройств символьного параллельного синхронного и асинхронного умножения.

Публикации по работе. По материалам диссертации опубликовано 7 печатных работ.

Структура и объем работы. Диссертация состоит из введения, пяти глав и заключения, изложенных на 122 страницах машинописного текста, содержит 48 рисунков, 6 таблиц, список литературы из 46 наименований и 3 приложений объемом в 46 страниц. Общий объем диссертации 168 страниц.

Основные результаты диссертации нашли отражения в работах: 1. В.Е. Абышкин, Д.Н. Тютюнов "Вариант ускоренного вычисления функции Y=Log2X в металловедческих исследованиях" / V Научно-техническая конференция с международным участием "Материалы и упрочняющие технологии-97", Курск, 1997г., 247с.

2. В.Е. Абышкин, Д.Н. Тютюнов, А.Д. Тютюнов "Использование систем продукций А.А. Маркова для разработки суммирующих устройств" / Международная техническая конференция "Медико-экологические информационные технологии", Курск, 1998г., 275с.

3. Д.Н. Тютюнов, А.Д. Тютюнов, В.Е. Абышкин "Вариант вычисления обратной функции на примере Y=Log2X и Y=2X" / Международная техническая конференция "Медико-экологические информационные технологии", Курск, 1998г., 275с.

4. В.Е. Абышкин, Д.Н. Тютюнов "Разработка суммирующих устройств с использованием систем продукций" // Тезисы докладов I Всероссийской научно-технической конференции, часть XII "Компьютерные технологии в науке, проектировании и производстве", Нижний Новгород, 1999г., 43с.

5. Д.Н. Тютюнов, В.Е. Абышкин "Применение алгоритмов вычисления обратной функции Y=f-l(X) для получения значений прямых функций Y=f(X) с заданной точностью" // Тезисы докладов I Всероссийской научно-технической конференции, часть XII "Компьютерные технологии в науке, проектировании и производстве", Нижний Новгород, 1999г., 43с.

6. А.Д. Тютюнов, В.Е. Абышкин, Д.Н. Тютюнов, B.JI. Хвтисиашвили "К вопросу о разработке алгоритма совместного доступа к базам данных" // Тезисы докладов I Всероссийской научно-технической конференции, часть XII "Компьютерные технологии в науке, проектировании и производстве", Нижний Новгород, 1999г., 43с.

7. Довгаль В.М., Елагин В.В., Абышкин В.Е. "Использование асинхронных вычислителей для решения проблемы вычислительной сложности в генераторах хаотических последовательностей", М.: ВИНИТИ депонент 6.09.2000 г. №2350-1300. 2000. 9 с.

Заключение

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

В ходе работы получены следующие результаты:

1. Разработана модель данных, позволяющая представлять числовые нормализованные данные с фиксированной точкой в символьном виде, пригодном для обработки системой параллельных подстановок.

2. Впервые разработана система параллельных подстановок для выполнения операции умножения и выполнены её исследование и обоснование. При этом предлагается использовать две параллельных подстановки для формирования частичных сумм произведения и их сложения, что обеспечивает функциональную полноту преобразований при выполнении операции умножения.

3. Установлено, что система параллельных продукций имеет свойство завершаемости и однозначности вычислительного процесса умножения, что позволяет получить необходимые показатели для выбора средств акселерации процессов обработки информации при разработке перспективных устройств умножения.

4. Созданы программные модели, реализующие способы и алгоритмы синхронного и асинхронного умножения, с помощью которых произведена оценка логической состоятельности и скоростных характеристик алгоритмов.

5. Разработан способ системно-структурной организации умножителей синхронного и асинхронного типов и выполнены для каждого из них технические решения элементов однородной среды и обобщенные структуры устройств, обеспечивающих высокую скорость выполнения матричного умножения. Сравнительный анализ самого скоростного известного матричного устройства умножения (аналог) и разработанных синхронных матричных устройств показал, что для них скоростное преимущество составляет от 3 до 5 раз, а аппаратная экономия - до 5 раз. Для асинхронного варианта реализации устройства умножения скоростное преимущество определено до 1.5 раз при росте аппаратных затрат - до 2 раз по отношению к разработанному синхронному умножителю.

6. Разработаны конкретные технические решения для нового класса устройств умножения, обладающего рядом положительных свойств: высокая скорость умножения, достигаемая за счёт массового распараллеливания операций генерации частичных произведений и их суммирования; матричная структура с малым временем задержки элемента, позволяющая разрабатывать топологию кристалла и использовать высокие тактирующие частоты; асинхронная реализация позволяет использовать вентили схемы, работающие с максимальной частотой; однородная структура элементов позволяет проводить их резервирование, дублирование и модульное наращивание умножителя и создает основу для реализации специализированных СБИС умножения.

Таким образом, совокупность полученных теоретических и практических результатов дает основание полагать, что цель диссертационной работы достигнута, а поставленные в ней задачи решены.

1. Марков А.А., Нагорный P.M. "Теория алгорифмов". М.: Наука, 1984г. 432 с.

2. Ачасова С.М., Бандман O.J1. "Корректность параллельных вычислительных процессов". Новосибирск: Наука, 1990г. 252 с.

3. Корнев Ю.Н., Пискунов С.В., Сергеев С.Н. "Алгоритмы обобщённых подстановок и вопросы их интерпретации сетями автоматов и однородными машинами". Изв. АН СССР. Техн. кибернетика, 1971г. №6. С. 131-142.

4. Джордейн Р. "Справочник программиста персональных компьютеров типа IBM PC, XN и AT". М: Финансы и статистика, 1992г, 543 с.

5. Смит Б.Э., Джонсон М.Т. "Архитектура и программирование микропроцессора Intel 80386". М: ТОО "Кондор", 1992г, 334 с.

6. Волш Д. "Технология программных модемов". М.: "ComputerWeek", 1997г, №32, С. 12-15.

7. Симэн Г. "Вейвлеты на программируемом кремнии". М.: "Компьютерра", 1998г, №9, С. 17-23.

8. Цифровая обработка сигналов на ПЛИС Xilinx: Каталог продукции. Scan Engineering Telecom (код DSP-CAT-9906).1999 г.

9. Мистюков В.Г., Капитанов В.Д. "Макромодули быстродействующих умножителей на ПЛИС Xilinx". Электроника и компоненты. 1998г. №3.

10. CORE Solutions Products Catalog. Xilinx Inc. 1999r.

11. П.Балашов Ю.С., Мистюков В.Г., Капитанов В.Д. "Библиотеки цифровых макромодулей для средств проектирования ПЛИС". Воронеж. Xilinx Inc. 1999г. С. 26.

12. Villasenor J., Mangione-Smith W. "Configurable Computing". Scientific American. June 1997r.

13. Алюшин М.В. "Аппаратная реализация быстродействующих нейросетей на основе программируемой логики фирм AMD, Altera, Xilinx". Нейроинформатика-99. М.: МИФИ. Часть 2. 1999г. С. 18-24.

14. Галушкин А.И. "Некоторые исторические аспекты развития элементной базы вычислительных систем с массовым параллелизмом (80- и 90- годы)". Нейрокомпьютер. 2000г. №1. С. 68-82.

15. Довгаль В.М., Елагин В.В., Абышкин В.Е. "Использование асинхронных вычислителей для решения проблемы вычислительной сложности в генераторах хаотических последовательностей" / М.: ВИНИТИ депонент 6.09.2000 г. №2350-1300. 2000г. 9 с.

16. Тютюнов Д.Н., Абышкин В.Е. "Вариант ускоренного вычисления функции Y=Log2X в металловедческих исследованиях" / V Научно-техническая конференция с международным участием "Материалы и упрочняющие технологии-97", Курск, 1997г. С. 211-213.

17. Абышкин В.Е., Тютюнов Д.Н., Тютюнов А.Д. "Использование систем продукций А.А. Маркова для разработки суммирующих устройств" / Международная техническая конференция "Медико-экологические информационные технологии", Курск, 1998г. С. 163-165.

18. Тютюнов Д.Н., Тютюнов А.Д., Абышкин В.Е. "Вариант вычисления обратной функции на примере Y=Log2X и Y=2 " / Международная техническая конференция "Медико-экологические информационные технологии", Курск, 1998г., С. 166-169.

19. Варшавский В.И. "Апериодические автоматы с самосинхронизацией". В кн.: Дискретные системы: Труды международного симпозиума ИФАК -Рига: Зинатне, 1974г., т.1.

20. Варшавский В.И. "Автоматное управление асинхронными процессами в ЭВМ и дискретных системах", М.: Наука, 1986г., 398 с.

21. Довгаль В.М. "Методы модификации формальных систем обработки символьной информации", Курск: Курск, гос. техн. ун-т, 1996. 115 с.

22. А.с. 1807481 СССР, МКИ G 06 F 7/52 / Устройство умножения /. Опубл. 1993 г.

23. А.с. 1783519 СССР, МКИ G 06 F 7/52 / Устройство умножения/. Опубл.1992 г.

24. А.с. 2021633 Россия, МКИ G 06 F 7/52 / Последовательный умножитель /. Опубл. 1994 г.

25. А.с. 1803914 СССР, МКИ G 06 F 7/52 / Устройство умножения/. Опубл.1993 г.

26. А.с. 1758644 СССР, МКИ G 06 F 7/52 / Устройство для умножения чисел с фиксированной запятой/. Опубл. 1992 г.

27. А.с. 1777134 СССР, МКИ G 06 F 7/52 / Отказоустойчивое устройство умножения/. Опубл. 1992 г.

28. А.с. 1789981 СССР, МКИ G 06 F 7/52 / Отказоустойчивое устройство умножения/. Опубл. 1993 г.

29. А.с. 2021631 Россия, МКИ G 06 F 7/52 / Отказоустойчивое устройство умножения /. Опубл. 1994 г.

30. А.с. 1833866 СССР, МКИ G 06 F 7/52 / Устройство умножения по методу Четвертьквадратичного умножения /. Опубл. 1993 г.

31. А.с. 1735843 СССР, МКИ G 06 F 7/52 / Матричное устройство умножения с модифицированной ячейкой /. Опубл. 1992 г.

32. А.с. 2018932 Россия, МКИ G 06 F 7/52 / Матричное устройство для умножения и деления /. Опубл. 1994 г.

33. А.с. 1741128 СССР, МКИ G 06 F 7/52 / Аппаратный контроль в умножителях /. Опубл. 1992 г.

34. А.с. 1784973 СССР, МКИ G 06 F 7/52 / Устройство для умножения двоичных чисел /. Опубл. 1992 г.

35. А.с. 1741129 СССР, МКИ G 06 F 7/52 / Устройство умножения для чисел /. Опубл. 1992 г.

36. А.с. 2054709 Россия, МКИ G 06 F 7/52 / Устройство для умножения чисел в позиционном коде /. Опубл. 1996 г.

37. А.с. 2022338 Россия, МКИ G 06 F 7/52 / Умножение чисел с плавающей запятой с использованием логарифмирования и экспоненцирования /. Опубл. 1994 г.

38. А.с. 1751748 СССР, МКИ G 06 F 7/52 / Устройство для умножения комплексных чисел /. Опубл. 1992 г.

39. А.с. 2012039 Россия, МКИ G 06 F 7/52 / Одно-тактовый умножитель двоичных чисел /. Опубл. 1994 г.

40. Красников Г.Я., Дорофеев А.П, Савенков В.Н. "БиКМОП ИС НОВАЯ ПЕРСПЕКТИВНАЯ ЭЛЕМЕНТНАЯ БАЗА МИКРОЭЛЕКТРОНИКИ". Обзор на официальном сайте фирмы Микрон корп. http: / / www.micron.ru/г ер ortr. html.

41. А.с. 2127324 Россия, МКИ G 06 F 7/52 / Устройство для умножения/. Бюл. №18, Опубл. 1999 г.