Функциональная мера сложности вычисления в автоматных схемах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

% À*

г^ московски!! государственный университет имени м.в.Ломоносова

На правах рукописи УДК 519.7

ЛЛ-ДОЕРИ АБДУЛ САГТАР АБДУЛ ДХАБАР

ФУНКЦИОНАЛЬНАЯ KÎEPA СЛОЖНОСТИ ВЫЧИСЛЕНИИ В АВТОМАТНЫХ СХЕМАХ

Специальность 01.01 .OS - математическая кибернетика.

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва -

1994.

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета им. Ы.В.Ломоносова.

Научные руководители: кандидат физико-математических наук,

доцент А.С.Подколзин, кандидат физико-математических наук Э.З.Гасаноз.

Официальные оппоненты: доктор технических наук,

профессор А.Б.Фролов, кандидат физико-математических наук З.А.Применко.

"Ведущая организация - Вычислительный центр РАН.

Защита диссертации состоитсяИij\il?j{£4<d. -SS5 года в 16 час. 05 кн. на заседании диссертационного созета (£.053.05) при КГУ по адресу: II9899, ГСП, Москва, Воробьевы Горы, I.T7, механико-математический факультет, аудитория 14-08.

С диссертацией мокно ознакомиться в библиотеке механико-математического факультета 1,17 (Главное здание, 14 этая).

Автореферат разослан " $ " r'flC&tf-ik.f IS95 года.

Ученый секретарь диссертационного совета (Д.053.05) при ЩУ д.ф.ы.н., профессор

В.Н.Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность темы.

Рассматривается задача реализации последоЕательностнкх операторов посредством автоматных схем. Эта задача возникает при разработке СБИС и б исследованиях по оптимизации используемых для ее ведения процедур, и поэтому имеет больное прикладное значение.

При постановке задачи синтеза оптимальной автоматной схемы, эеализующей заданный последовательносткый оператор, центральным :вляется ьыСср критерия оптимизации. Этот критерий складывается из гвух составляющих - пространственного (площадь, занимаемая схемой, 7А"о суммарная сложность элементов схему) и временной (время выделений, осуществляемых схемой). В различных исследованиях рассматривались различные конкретные комбинации этих двух составляа-ул А (сложность схемы) и Т (время вычисления). Отметим, в первую чередь, такие варианты критериев оптимизации, как А, Т, А-Тг, А-Т другие. Выбор конкретного критерия оптимизации осуществляется на рактике с учетом специфики разрабатываемой вычислительной системы особенностей ее использования, и многообразие таких критериев одсказывает необходимость проведения исследований глобальных за-кскмостей А (?) и Т(Л) - минимальной сложности схемы А при за-энном времени вычислений Т и минимального времени вычислений при адгнной сложности А. Получение оценок для таких функциональных арактеристик слокности автоматной реализации конкретных опера-орон могло бы существенно упростить синтез схем для конкретных эитериев оптимизации указанного выше "смешанного" типа.

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

них операторов, и исследованию слозкости их рзахгзацзг (в смысле конкретных комбинация характеристик А и Т) было пэсвяшено большое количество работ.

Первая из указанных задач - задача о схемной реализации оператора умножения. Задача об умножении рассматривалась в 1962 г. А.А.Карацубой 1). Он рассматривал умножение двух Ы-разряднкх двоичных чисел на многоленточной машине Тьюринга, или посредством логической сети из логических элементов с двумя Еходами. Б обоих случаях сложность (в первом случае - Т, а ео втором - А) растет как Н2. Л.-А.А.КарацуОа предложил метод решения данной задачи, позволивший построить сеть с О (N10^3) элементами (1о£,3 = 1,58). Этот метод без затруднения переносится на машины Тьюринга.

Дальнейшее уменьшение оценки содержала появившаяся в следующем году заметка А.Л.Тоома 2), б которой была указана сеть

сопв!•У1ЕМ

для умножения К-разрядкых дваичннх чисел из О(К-2 ) ло-

гических элементов. Независимо от Тоома к совсем итак методами

Шенхаге 3) в 1965 г. показал, что на малине Тьюринга умножение

Уг1о3 ы' |

И-разряднкх чисел можно делать со сложность» О (И-2 ^ (1$»тг). Впоследствие алгоритм Тоома бил перенесен на машины Тьюринга с

более точной оценкой сложности: 0(К«2 с 101). Существенно различные методы Тоома и Шенхаге дакт практически одинаковые оценки слояности, и это позволяет считать оценки близкими к оптимальной.

1). Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах. ДАН СССР (1952), т.145, N 2, стр.293-294.

2). Тоом А.Л. О сложности схемы из функциональных элементов, 'реализующей умножение целых чисел. ДАН СССР (1953), т.150,

Л 3, с.496-498.

3). Шенхаге А., Штрасеен Б. Быстрое умножение больших' чисел. Кибернетический сборник. Л- 10, с.87-98.

В работе Шэнхаге указаны два способа умножения {{-разрядных двоичных чисел, которые допускают реализацию как в логической сети, так и на машине Тьюринга. Сложность одного способа -оамфгадел)148), другого - о<л»1йн.1£1ёю.

Вторая задача - задача об автоматной реализации оператора сортировки. Эта задача рассматривалась многими исследователями; в 1990 г. Дк.Д.Ульман 41 показал, что можно записать числа, подлежащие сортировке, в схему из К * N ячеек (для Н-К-разрядных чисел) и выполнить пузырьковую сортировку в пространстве размером 0(К*1МойК) за время порядка 0(М'1о&К). С другой стороны, известна схема сортировки Бэтчера, проводящая сортировку за время О(•1о§К),.но требующая пространства 0(К2»Кг).

В 1991 г. вышла работа В.В.Морозенко 55, в которой рассматривалась задача нахождения порядка на-п-элементном множестве, изоморфном булевой алгебре, путем последовательного попарного сравнения его элементов. Предложена процедура для решения этой задачи, сложность реализации которой асимптотически равна п-1х^2п.

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

4). Ульман Дж.Д. Аспекты вычисления СБИС (1990).

5). Морозенко В.В. О сложности сортировки булевой алгебры | дискретная математика. - 1991. - т.З, вып.1. - с.42-47.

ТТа гг. •поЛлтит — гтп тг«гьггг»а пттаиг'тт г^лгиг*ттт*лгго ттт.гг.-'г -г о^сг-тд-гтг^^т»^.-

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

: Методика исследований. В работе используются методы дискрет' ной математики и математической кибернетики.

Научная новизна. Все. основные результаты работы являются

новыми.

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

Апробация. Результаты работы докладывались на семинаре по теории автоматов (руководитель - академик'АТН РФ В.В.Кудрявцев).

Публикация ■ По теме диссертации автором представлены к .. опубликованию . 2 ' работы,; названия" которых приведены в конце • автореферата. '

д.. СОДЕРЖАНИЕ РАБОТУ. '

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

3 настоящей работе рассматривались для каждого оператора три .". метода. Первый метод синтеза схем Еыдает в качестве результата схемы, имеющие большую слозкностъ и малое время вычисления. Второй метод для схем с малыми слозкостями и большим временем вычисления.

Третий метод является комбинацией первого и второго.

диссертация состоит из введения и двух глав. Во введении содержится постановка задачи, обзор известных результатов, и формулируются основные теоремы диссертации. Первая глава посвящена изучению сложности вычисления оператора умножения, реализуемого структурным!* автомата?®.

В §1 рассматривается метод умножения с малым временем вычисления. Получены верхняя оценка сложности схем и условия, при которых зремя вычисления равно нулю, приведенные в следующей теоремеi

Теорема 1.

а: П L(t,K) ^ 11,5-К2 + 2CN - 12 Ъ: 1(1,К) = 0, если 1 » 11,5-Кг + 20N - 12. В §2 рассматривается метод умножения с малой- сложностью, с помощью которого получены оценки, приводящиеся в следукией тео-

Теорема 2,

a: L(t,N) ^ 4ON - 3, если t ? N + 2!I О: T(1,R) < N + 2К, если i 5 4ON - 3.

В §3 рассматривается "комбинированный метод" умножения, и получены оценки для слсхности и времени вычисления, являющиеся комбинациями первого (§1) и второго (§2). Теорема 3.

Пусть g(t,N) = (7Tlog2(t - 2N) - " H3losJt_gK)t)g -(21og,(t - 2K) + 16)(]loeJt-2K)[) - 26Iog2(t - 2N) + 22.

а: тогда, если t » ]|[-К + 2K, где К € i1,N),

то L(t,N) ^ g(t,H). Ь: если 1 » g(t,N), то T(1,K) ^ Ш-К + 2K.

Следствие: Если 2N ^ t í N + 2*4 то

L(t,K) $ (771oge(t - 2N> - -

.. .. . : ..(ZlOg^X - 2N)„t ,.16)(]losJt_2M)[) - 261og2(t - 2N) + 22.

Вторая глава посвящена изучению понятия сложности вычисления > оператора сортировки, реализуемого структурными автоматами. - " . Задача о сортировке. Имеется К двоичных наборов (ап .. .а^ у _ ..., (а1К...Ojjj.), рассматриваемых как записи чисел А,,...,^. Требуется определить группу (Рп.. .6К1 ^.....(р1К...рш) двоичных за..... писей чисел А,.- ,...\А,. , где А- А.. и (! ,...,!„) - пере'ста-

"1 TS "1

новка.чисел (1,...,К). Введем в рассмотрение два оператора Р1 и - F2, формализующие эту задачу при реализации ее с помощью логкчес-ких. сетей. •'

Оператор ?1 зависит от переменных ,... значениями которых являются наборы (ап,... .Ojj, j,..., (а1К,. ...cXjj..), и значением его является набор слов у..., (р,...... ,pJJ4)).

Оператор ?2 зависит от переменных значениями которых

являются наборы __(aN1 .с^-,. ■ - .а^у..., (аи ,а.г,... ,а.к), а ■ • значением • его является набор слов .((S,„,я ,

iv i bid ¿чг»)

.(Р,,,Р12,...,р1К)). Первый из этих операторов соответствует случаю, когда записи сравниваемых чисел подаются на различные входы ^логической сети в последовательные моменты времени г = 1,2,...,Н;

второй - случаи, когда каздая запись поступает в течение одного ' такта сразу на все входы логической сети.

В §4 рассматривается метод'сортировки "строк" (метод с малым "временем вычисления). Получены оценки для сложности, когда время вычисления малое, как в следующей теореме: Теорема 4.

L(t,N,K) ^ 16Ж + 10N + 2 J log Kt + 14, если t И и T(1,N,K) < К, если 1 > 16NK + ЮМ + 23log КГ + 14.

В §5 рассматривается метод сортировки "строк" (метод с малой сложностью). Получены малые оценки для сложности, когда время вычисления велико, как в следующей теореме: Теорема 5.

L(t,N,K) ^ П.К + 16Н + ЗК + 23, если t > Н-К и К1.НД) $ 1I-K, если 1 > N-K + 16N + ЗК + 23. В §5 рассматривается метод сортировки "строк" (комбинированный метод). Получены оценки для словности и времени вычисления в следующей теореме: Теорема в.

L(t,K,K) =$ 41J.K + 4415 + 11,5-К + 76, если t > N-K и T(1,N,K) < -1 N-K, если 1 > 4N-K + 44N + 11,5-К + 76.

В §7 рассматривается метод сортировки "столбцов" (метод с малым временем вычисления). Получены большие оценки для сложности, когда время вычисления равно нулю, как з следующей теореме: Теорема 7.

П Lit ,3i,K) 11Х(К - 1) и T(i,N,K) = О, если 1 ^ 11К(К - 1Ь В §8 рассматривается метод сортировки "столбцов" (метод с малой сложностью). Получены малые оценки для сложности, когда время вычисления велико, как в следующей теореме: Теорема 8.

L(t,N,K) i N-K + 41К + 10K]log2Ht + 4, если t 5 П-К И T(1,N,K) ^ N-K, если 1 » N-K + 41К + 10K]lOg2HC + 4.

В §9 рассматривается метод сортировки "столбцов" (комбинированный метод). Получены оценки для слокности и времени вычисления в следующей теореме: Теорема 9.

L(t,N,K) С 17/2-N-K + 23N + 11Кг/2 - 7К + 30, если t > N-K/8 и T(1,N,K) < N-K/8, если 1 5 17/2-N-K + 23N + 11Кг/2 - 7К + 30.

Ь §10 рассматривается метод сортировки столбцов" (связочные метод), где данные числа как столбец; "переворачиваем" эти столбцы как строки. Сортируем по порядку возрастания и опять "переворачиваем". Получены оценки для сложности и времени вычисления, приведенные в следующей теореме: Теорема 10.

ьи.Н.К) « 2611-Е + 6Н + ЗК + 2Пов К! + 12, если I > К + К и Т(1,М,К) II + К, если 1 26К-К + 6Н + ЗК + 2]Ю£ КС + 12.

Структура и объем диссертации. Диссертация состоит из введения, двух глав к списка литературы. Первая глава диссертации состоит из трех параграфов. Вторая глава диссертации состоит из двух частей, первая часть состоит из трех параграфов, а вторая часть состоит из четырех параграфов. Объем работы 127 страниц.

Автор выражает глубокую благодарность своим научным руководителям к.ф.-м.н. доценту А.С.Подколзину и к.ф.-м.н. Э.Э.Гасанову за постановку задач, постоянное внимание и помощь в работе.

Работы автора по теме диссертации:

1. Ал-Довря Абдул Саттар Абдул Джабар. Оценки функциональной сложности автоматной реализации оператора умножения. (Будет депонировано в ВИНИТИ РАН).

2. Ал-Доври Абдул Саттар Абдул Дкабар. Оценки функциональной сложности автоматного решения задачи о сортировке. (Будет депонировано в ВИНИТИ РАН).

Тираж 100 экз.