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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В.ЛОМОНОСОВА

На правах рукописи

VT ист

АЛ-ДОВРИ АВДУЛ САТТАР АЕДУЛ Дл/ЗА?

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

гениальность 01.01.05 - математическая кпоезнеткка.

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

Москва - 1994

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

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

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

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

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

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

Защита диссертации состсится/4^£^/&^'1995 гсда б 16 час. 05 мин. на заседании диссертационного совета (Д.053.05) при ЫГ7 по адресу: 119899, ГСП, Иосква, Воробьевы Горы, 1.ТУ, механико-математический факультет, гудптооия 14-08.

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

Автореферат разослан ". /У " йСиЫгШ 1995

года.

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

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

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

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

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

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

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

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

Первая кз указанных задач - задача о схемной реализации оператора умножения. Задача об умвокении рассматривалась в 1552 г. А.А.Карацубой 1). Он рассматривал умножение двух N-рэзряднкх двоичных чисел ка многоленточной машине Тьюринга, или посредством логической сети из логических элементов с двумя входами, Б обоих случаях сложность (в первом случае - Т, а ео втором - А) растет как N2. Л.А.А.Карацуба предложил метод решения данной задачи, позволивший построить сеть с 0(Nlog,3) элементами (log23 = 1,58). Этот метод без затруднения переносится на машины Тьюринга.

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

const »Vigil

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

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

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

У21ое_ы §

N-разрядных чисел можно делать со сложностью 0(N-2 (IgN) ).

Впоследствие алгоритм Тоома был перенесен на малины Тьюринга с

/2iog„:j

более точной оценкой сложности: О(Н-2 1:1 IgN). Существенно различные методы Тоома и Шенхаге дают практически одинаковые оценки слогности, и это позволяет считать оценки Слизкими к оптимальной.

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

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

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

В работе Шешсгге указаны два способа у?ж»:еш'я И-разрядных хвоичшх чисел, которые допускают реализацию как в логической ;ети, так и на машине Тьюринга. Сложность одного способа -заМеЖ^ЕЮ14*5). другого - ООМёТЫв].^).

Вторая задача - задача об автоматной реализации оператора зортировки. Эта задача рассматривалась многими исследователями; в 1990 г. Дж.Д.Ульман показал, что мокно записать числа, подле-кащие сортировке, в схему из К * N ячеек (для ГЬК-разрядшх чисел) и ; вшолнить пузырьковую сортировку в пространстве размером Э(К-1Ыо£К) за время порядка 0(1Ыо^К). С другой стороны, известна схема сортировки Вэтчера, проводящая сортировку за время 0(1о^1Мо£К),.но требующая пространства 0(К2»Кг).

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

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

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

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

Т'огг. "паЛ-лт*.* _ гт.^тг\тсггтгд ^.ут^гтг"^гтоус.т*1.ОУтг.л^ту

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

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

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

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

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

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

СЮДЕРйСАНИЕ РАБОТЫ.

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

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

prio'piT^ уэтод явл^б^с^ комбтг^£1ЛГ1:1й геового и в^вого.

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

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

Теорема 1.

з: Vt L(t,N) < 11,5-К2 + 2GN - 12

b: T(1,N) = 0, если i £ 11,5-N2 + 20N - 12.

В §2 рассматривается метод умнскения с малой сложностью, с юмоыью которого получены оценки, 1гр;зодя2кеся в следующей тео-

Теооемэ 2.

a: L(t,N) « 4® - 3, ees í ? N + 2л;

b: T(1,N) < N + 2К, если 1 > 4 ON - 3.

В оЗ оассматопвзется "ксмоиниюовзнный метод" \тмно^еукя, и ¡олучены оценки для сло~1Ностп и воэкбки вычисления, являю'ш-'^ся ;омбинацияш первого (§1) и второго (§2).

Теооема 3.

[усть g(t.N) = (771og2(t - 2К) - 11 )(1IoeJ(:t.gK)n5 -21og2(t - 2N) + 16)(]IosJt_2,;i[) - 261og2(t - 2H) + 22.

.: тогда, если t £ ЗрС«К + 2К, где К с С1,Ю.

то L(t,}J) $ g(t,N). •: если 1 ? g (t, N), то Т (I,К) < ЗШ -К - 2К.

Следствие: Если 2N í t í N + 2", то

I(t,N) (771 og2(i - 2") - 11)(]loeg"t.2M)n2 -

(210^(1 - 2N) + 16)(3losJt_aN)[) - 261og2(t - 2H) + 22.

Вторая глаЕа посвязена изучению понятия сложности вычисления оператора сортировки, реализуемого структурными автоматами.

Задача о сортировке, веется К двоичных наборов (а^.-.а^, .... (aJK...aínt), рассматриваемых как записи чисел А1,...,Aj,. Требуется определить группу . л...р>п ^,..., (Р1К... двоичных записей чисел А,- , где А,- А,. и (l.,...,i„) - петеста-

-1 -V -1 ' п

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

Оператор F зависит от переменных х^...,х,с, значениями которых являются набора (ап,....а,., у .7.7(а1К,...,а,н), и значением

его является набор слов Ц^..., (р1К.....6^)).

Оператор Fg зависит с-т переменках х, ,...,5,,, значениями которых

являются наборы (с^ ,Oj„,. ...а^,..., (а,. ,а.г.....а1К), a

значением его является набор слов (,í¡JJ2,... • • •,

.....Pik'1^ Пе?ЕЫЙ кз этих операторов соответствует случаю, когда записи сравниваемых чисел подаются на различные входы логической сети в последовательные моменты Еремени t = 1,2,...,N; второй - случак, когда каздзя запись поступает з течение одного такта сразу на все входы логической сети.

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

Теорема 4.

L(t,N,K) 16NK + 10К + 231og КГ + 14, если t $ К к T(i,N,K) < К, если 1 > 16КК + 10М + 23l0g KÍ + 14.

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

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

L(t,N,K> < 4N-K.1- Ш + 11,5-К + 76, если \ N*K и T(1,N,K) < если 1 ^ 4N-K + 44N + 11,5-К + 76.

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

П L(t,K,K) 11К(К - 1) и T(1,N,K) = О, если 1 » 11К(К - 1). В 58 рассматривается метод сортировки "столбцов" (метод с злой сложность-}). Полечены малые сценки для сложности, когда 5ремя вычисления велико, как в следующей теореме: Теорема 8.

L(t,N,K) ^ К «К + 41К + 10K]log2IJi т 4, ее л*, t ^ П-К и T'l.N.K) N-K, если 1 ^ N*K + 41К + ICKllogjn + 4.

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

L(t,N,K) < 17/2• 2J-К + 22?; + 11Кг/2 - 7К + 30, если t >; N-K/8 и Т(1,К.К) N-K/8, если 1 ^ 17/2-N-K + 23N + 11Кг/2 - 7Х + 30.

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

1(1;,К,К) ^ 2611 • К + 6П + ЭК + 2]10£ КГ + 12, если г £ К + К и Т(1,1г,К) < N + К, если 1 » 26Ц.Х + 6Н + ЗК + 2Иов-К! + 12.

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

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

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

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

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

Тирах 100 экз.