Организация процесса обработки данных в локальных сетях ЭВМ тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи УДК 519. 86

СМИРНОВ Алексей Владимирович

ОРГАНИЗАЦИЯ ПРОЦЕССА ОБРАБОТКИ ДАННЫХ В ЛОКАЛЬНЫХ СЕТЯХ ЭВМ

01. 01.09 - Математическая кибернетика

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

Москва - 1991

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

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

А. В. Михалев.

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

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

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

Защита состоится "/V 'фзА^ШАА г. в /■! час. 0_0 мин. на заседании Специализированного Совета К.053.05. 84 при Московском государственном университете им. М. В. Ломоносова. С диссертацией можно ознакомиться в НИВЦ МГУ.

Адрес - 117234, Москва, МГУ, НИВЦ.

Автореферат разослан "/V " Я 139^2 г.

Ученый секретарь Специализированного Совета К. 053. 05. 84 кандидат физико-математических наук

ОБВДЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Потребности в высоком быстродействии и большом объече оперативной памяти при проектировании локальных сетей ЭВМ обычно вступают в противоречие с ограниченными техническими и финансовыми возможностями. В связи с этим проблемы эффективного использования ресурсов локальных сетей не теряют своей актуальности.

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

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

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

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

Целью работы является

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

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

3. Получение оценок эффективности полиномиальных алгоритмов

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

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

Научная новизна результатов заключается в том, что

1. Получен быстрый полиномиальный алгоритм построения допустимого расписания в многопроцессорной системе обслуживания для требований порождаемых периодическими задачами. Число прерываний в расписании на порядок меньше оценки известной для общего случая ("теоремы 1.1-1.2).

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

Предложен полиномиальный алгоритм уменьшения числа прерываний в оптимальном расписании для одностадийной многопроцессорной системы обслуживания в общем случае, соогветствуодая оценка числа прерываний в ОСгР'5) раз лучше известной оценки (Гтеорема 1.4).

2. Получена оценка эффективности семейства приближенных полиномиальных алгоритмов упаковки в контейнеры, показывающая их высокую асимптотическую эффективность при некоторых естественных ограничениях С теорема 2.1-2.2).

Доказана асимптотическая оптимальность двух полиномиальных алгоритмов упаковки для некоторых классов функций распределения вероятностей, включающих в себя, в частности, все выпуклые функции распределения Стеореыы 2.3-2.5).

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

Нетодика исследования комбинаторно-логические методы дискретной математики, элементы теории расписаний, теории вероятностей и математической статистики, эксперименты на ЭВМ.

Практическая ценность. Предложенные в работе алгоритмы и оценки могут быть использованы при проектировании локальных сетей ЭВМ и многопроцессорных комплексов для управления АСУТП.

Публикации и апробация работы. По теме диссертации

опубликовано б печатных работ. Основные результаты докладывались на семинаре "Программирование" МГУ им. М.В. Ломоносова и на

семинарах сектора "Проектирование вычислительных систем реального времени" Вычислительного центра АН СССР.

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы С25 наименований). Объем работы страниц машинописного текста.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Во введении обосновывается актуальность темы, дается описание исследуемых моделей локальной сета ЭВМ и приводится краткое изложение основных результатов, полученных в диссертации.

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

В теоремах 1.1-1.2 исследована ситуация, когда требования порождаются множеством из п2 периодически выполняемых задач с целочисленными периодами выполнения Т^ и временами обслуживания требований W^, -сводимая к частному случаю следующей модели одностадийной детерминированной системы обслуживания.

Модель t. Требования множества N={ 1,2,... ,п) обслуживаются параллельными идентичными приборами. Прибор в каждый момент времени обслуживает не более одного требования, каждое требование в каждый момент времени может обслуживаться только одним прибором. Требование J поступает в очередь на обслуживание в момент d>.0 длительность его обслуживания равна tj>0. Известен директивный срок Dj>dj+tj к которому необходимо завершить обслуживание требования j. Допускаются прерывания обслуживания любого требования. Считается, что прерывания не сопряжены с временными затратами и число прерываний конечно. Обозначим Г= шах CDjJ.

Величины tydpDj .считаются неотрицательными рациональными числами. .

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

1) Танаев B.C., Гордон B.C., Шафранский Я. М. Теория расписаний. Одностадийные euerem. - М.: Наука, 1984.

2) Танаев B.C., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. - М.: Наука, 1989.

Обозначая расписание обслуживания требований О),

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

Будем говорить, что в момент времени I^ имеет место прерывание обслуживания требования ) на приборе I, если з^О^рО,

р+0)*] и существует 1>1р такое, что з^СО^' для некоторого

к, ,2,... Пусть £ чипСЧп/СОгБ¡ХО=з,Л>1ср. Если

I <Н£м г

Сто назовем прерывание прерыванием первого рода, в

противном случае прерыванием второго рода.

Величину ы^У^Л^, где У^-время обслуживания, а -период выполнения, назовем нагрузкой ¿-ой задачи.

Теорема 1Л

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

£|д5

£ 1, í=l,... ,П2

и существует алгоритм А^ построения• допустимого расписания временной сложности ОСп2гО.

Теорема 1. 2

Пусть множество требований N порокдейо множеством периодических задач и для него существует допустимое расписание обслуживания требований т. параллельными приборами с р+1 различным моментом начала и завершения обслуживания требований Ср<а?.

Тогда

1. Существует алгоритм А^ временной сложности 0(тп1о§(10+тгУ, который строит допустимое расписание не более чем с п+тСр-1) прерыванием первого рода и 2рСш-1) прерыванием второго рода, такое что все требования имеющие прерывания второго рода, порожденные одной задачей, обслужичастся только двумя приборами.

2. Суаествует алгоритм А^ временной сложности ОСпп1о§(гО+шг), который строит допустимое расписание не более чем с 2глр+р+п-л прерываниями.

Оценки числа прерываний теоремы 1.2 имеют порядок ОСгО, что в ОСЮ раз лучше известной оценки для общего случая.

-т-

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

Модель 2. Множество требований К-(i ,2,... ,nJ обслуживается в системе состоящей иэ m приборов. Каждое требование поступает в систему в момент d£ и его обслуживание включает в себя гL последовательных стадий. Заданы длительность обслуживания на j-ofl стадии t^j и номер прибора L^j, обслуживающего требование на этой стадии, i=i,..,n, Одновременное обслуживание

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

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

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

FCx, y>*FCxtxin,.... xnj,.... xm, у, f,..., у im,.... yni.....уш)

невозраставцюв по аргументам x^j и неубывающую по аргументам y^j, где xtj- - моменты начала обслуживания i-го требования j'-ым прибором, а у- моменты окончания обслуживания t-ro требования j-m прибором, х-1,2,... п, j-i ,2.....та.

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

Расписание на котором функция FCx,у) принимает минимальное конечное значение назовем оптимальным.

Теорема i.3

Пусть задано множество требований N={ 1,2,.,. ,тО, произвольная функция штрафа FCx.jl) и строго многостадийная система обслуживания из т. приборов.

Тогда, если для множества требований N и функции FCx,уJ5

существует оптимальное расписание, то существует оптимальное

п

расписание не более чей с J r-ni прерываниями.

Эта теорема обобщает, а иногда и улучшает многочисленны оценки

такого рода для разнообразных частных случаев.

Вернемся теперь к расписания« одностадийных многопроцессорных систем для произвольного множества требований, минимизирующим функцию штрафа Г(х,у), введенного выше вида. Теорема 1.4.

Если для множества требований Н-{1,2,... ,п>, произвольной функции штрафа ГСх,у1 и системы обслуживания из т. параллельных приборов существует оптимальное расписание. Б с р+/ различным сроком начала и окончания обслуживания требований Ср&2п-1), то существует оптимальное расписание Бд не более, - чем с тхСп,р)у тпс +т1п(п, р)/2+тСр-13 прерыванием, которое может быть получено из £ алгоритмом сложности ОСпЪ.

Оценка числа прерываний теоремы 1.4 имеет порядок ¡Хп^'Ъ, что в ОСтР■ раз лучше известной • оценки для

многопроцессорных расписаний, соблсдающих директивные сроки.

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

Формулировка задачи.

Задано конечное множество и .. .и^) рациональных чисел

Требуется найти такое разбиение множества У на

непересекахвдеся подмножества .... ,ип, чтобы сумма чисел в

каждом подмножестве не превосходила 1 и. чтобы п было наименьшим

возможным. Множества и^ назовем контейнерами.

Пусть £ есть множество алгоритмов упаковки, каждый из которых

просматривает множество ■ и в порядке, определяемом нумерацией

предметов в У и, либо размещает очередное.и^ в один из непустых

контейнеров О,-, удовлетворяющих условию ¿¿,-5 1~иь, либо, если •/ ц .ЗУ •

ни один контейнер этому условию не удовлетворяет, открывает новый

пустой контейнер и помещает и^ в него.

Теорема 2.1.

Любой алгоритм АеЕ упакует ¡/ в число контейнеров не превосходящее

М =шох|" &,/Г1-ииЛ (13 1<к$п 1=11 к Число контейнеров, определяемое согласно СО, достигает

минимума, когда и упорядочено по невозрастанию - и^и^,...

Алгоритмы множества Е, которые упаковывают предметы множества U в порядке невозрастания их размеров назовем экономными алгоритмами.

Отметим, что известные алгоритмы FFD и BFD и многие другие обычно исследуемые полиномиальные алгоритмы упаковки являются экономными.

Формула С ID теоремы 2.1 позволяет исследовать поведение экономных алгоритмов при больших п. Далее будем считать, что множество U есть простая выборка объема п из генеральной совокупности с распределением Р. Обозначая такие выборки Un будем рассматривать их последовательности {if1} при п->оо. Числа и^ в дальнейшем удобно считать действительными.

Пусть п£А,Ю - число контейнеров, полученное в результате упаковки множества U с помощью алгоритма А и 5СЮ - сумма всех uLeU. Назовем относительной недогрузкой величину

гСА, Ш=т£А, Ю/SCU)-I.

Приводимые ниже оценки недогрузки в среднем для различных алгоритмов- существенно лучше известной оценки Джонасона ^ в наихудшем для алгоритма FFD.

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

Теорема г. 2.

Пусть FCx) функция квазиобратяая к функции распределения вероятностей генеральной совокупности РСх) и FCiXi.

Тогда для всякого экономного алгоритма /1 с вероятностью 1 выполнено .

ш zCA.ub < sup ееr; - i

П~>а> i 0<Т<1

где 6CrJ = J Fix) dx /СECu)Cl-F(r)))

' г

и ЕСгО - математическое ожидание и.

Следствие 2.2.1. Если ЛГх) имеет на 10,11 непрерывную производную, то с вероятностью i

Ш zC^.i/b < sup 6Cr ) - 1 n->a> t

где .. все корни уравнения

3J Тори М,Г., Джонсон Д. С. Вычислительные машины и труднорешает«? зялачи. - М.: Мир, 1982.

J 1

F/CrJ!FCxMx =FCrXt-F(r» г

Формулы теремы 2.2 и следствия 2.2.1 позволяют находить асимптотическую относительную недогрузку для конкретных распределений, а так&е получить еще одно следствие.

Следствие 2.2. 2 Пусть в некоторой окрестности нуля существует производная F/Cx) непрерывная в 0, а выборки if1 порождаются случайной величиной v = R и. Тогда с вероятностью 1

Ш zCA.l/1) < E(uJF/(03F?/2 oCR п->00

Полученные оценки интересны в силу своей общности, однако, ограничивая класс распределений, для отдельных алгоритмов можно получить существенно более сильные результаты. Далее алгоритм осуществляющий упаковку U в минимальное число контейнеров будем обозначать ОРТ.

Алгоритм А назовем асимптотически оптимальным для функции

распределения вероятностей РСх), если с вероятностью 1 выполнено

I imCzCA.Ub-zCOFT, Un))=0. а-.>х

Построим простой полиномиальный алгоритм, асимптотическая оптимальность которого может.быть доказана для достаточно широкого класса функций распределения. Алгоритм S/MCW

1. Добавляем в U вспомогательное Uq=0. Полагаем Q=h, J~l, Открываем для упаковки пустой контейнер U

2. Если U состоит из одного Uq, то кончаем работу.

3. Маем максимальное u^eU. Если Q/2, то полагаем Q = Q/2 и переходим к пункту 3, иначе ищем максимальное Uj такое, что u^Uj < Q. Если вместе с и^ не умещаются в Uj, то закрываем его, полагаем J = J+i и открываем пустой Uj . Перемещаем и ненулевое Uj из У в Uj. Переходим к пункту 2.

Временная сложность алгоритма ОСп logCrüj. Георема 2. 3

1. Если функция распределения случайной величины и представима

в виде

Р(х)= Z QXxi, i=0 1

где а^хЭ+в^г Vrr-целое, 0.^х),С{>0, т>1, то

алгоритм SlMCl/r} асимптотически оптимален и с вероятностью t выполнено

lim zCSUKi/rü.lfЪ = 0.

П->00

2. Если функция распределения случайной величины и для всякого x>i/2 удовлетворяет неравенству

РСЮ-РС1/2Ю)) < Р(1/2)-Р(1-хЮЭ, то алгоритм S/MC1J асимптотически оптимален и с вероятностью 1 выполнено

Lim zCSlK,Un)<P<v>i/2)+P{u=i/2)/2)/Z(u>l, n->to

где E(xD - математическое ожидание и.

Следствие 3. i . Алгоритм S1MC1) асимптотически оптимален для всех выпуклых функций распределения.

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

Теорема 2.4.

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

PfxJ>= Е i=0 1

где t^OcHQj-.d/r^-x)^, г£-целые, .

Тогда lim. 2C0PT,Un)=0

п-> оо

и существует алгоритм упаковки ACPJ временной сложности не более ОСтг) асимптотически оптимальный для Р(х?,

Условие нулеврй асимптотической относительной недогрузки теорем 2.3, 2.4 можно записать в рекуррентной форме. Исследование известного алгоритма FFD с помощью результатов полученных в теореме 2. 3 позволяет получить для него аналогичные условия асимптотической оптимальности.

Теорема 2.5

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

а0Сх; = PCxJ,

г^СхХЗ^СхХ Qi_iCl/i)-Qi_i(Cl-xD/i) J>/i, где xe[0J/i] есть последовательность несобственных функций распределения.

Тогда алгоритм KFD асимптотически оптимален и с вероятностью 1 выполнено

lim zCFFD,lß) = 0.

П~> 00

2. Пусть функция распределения случайной величины и для всякого

х>1/2 удовлетворяет неравенству

РСх)-РС1/2Ю)) < PC 1 /2)-PC 1 -х+О).

Тогда алгоритм FFD асимптотически оптимален и с вероятность» 1 выполнено

I lm zCSIM,Un)-CPCxOi /2)+P<tx=i /2>/2)/E(u)-l.

n->oa

где- ЕСЮ-- математическое ожидание u.

Следствие 2.5. i. Алгоритм ГГО асимптотически оптимален для всех выпуклых функций распределения.

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

Обозначим D множество всех функций распределения на [0,1]. Следущая теорема существования дает ответ на вопрос о существовании предельной оптимальной относительной недогрузки в общем случае и несколько проясняет вопрос о существовании асимптотически оптимальных полиномиальных алгоритмов для произвольной функции распределения вероятностей.

Теорема 2.6.

Пусть последовательность (if1) удовлетворяет равенству теоремы-Гливенко для функции распределения Р(х).

Тогда

1. ГШ z(OFT,Ua)=liin zCOPT,Un)=z(OPT,P) tl-> оо п->т

2. Отображение zCOPT,P.) из D в f0,1) непрерывно в метрике

s=sup|PfxJ-Qfx^i. х

3. Если PeD дискретная С кусочно-постоянная.) функция распределения с конечным числом скачков г, то существует алгоритм АС?) временной сложности ОСгО такой, что

zCACP),?) = tm z(ACP),Un) = zC0PT,P) n-> oa

4. Для всякой Рей и всякого e>0 существует алгоритм АСР,в) временной сложности OfnJ такой что

гСЛСР.е^.РЗ = lm гСАСРув),!/1) < zC0PT,P;>+<? n->oo

Отметим, что первое утверждение теоремы 2.б справедливо и для некоторых полиномиальных по времени алгоритмов упаковки Сно не для всех), а второе утверждение теоремы есть следствие первого для любого алгоритма.

В третьей глеве рассматривается NP-полная задача поиска

-/J-

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

Терминологию и постановку задачи можно найти, например, в if).

Обозначим неориентированные графи с помеченными вершинами -gСп,Ю, где n-число вершин, W-число ребер. Далее рассматривается ситуация, когда п, М=МСтО неограниченно возрастают и устанавливается, что максимальную клику при некоторых условиях можно с высокой вероятностью найти за полиномиальное время.

Случайным графом назовем множество различных графов вСп,Ю={, каждому из которых приписано неотрицательное число р^ так, что . Эти числа задают на множестве {§ьСп,Ю) меру Р.

Пусть заданы последовательность случайных графов {GCn,MCr03), и

последовательность подмножеств графов CBR>, B^G(n,M(rO),

n=l,2,..., обладающих некоторым свойством В. Если lira PCS_J=1, то

п-> со п

будем говорить, что В имеет место почти во всех случайных графах <GCn,MCrD}>.

Буква N далее обозначает число сочетаний из п по 2.

Графы бСп,М,гЗ

Пусть случайные графы 6<п,И,г) устроены следущим образом. Имеется г=гСтО фиксированных вершин, соединенных ребрами в

полносвязный подграф КСг,гО. Из оставшихся N-R. равноправных возможностей случайным образом выбирается М-Р, ребер. Иными словами всякому сочетанию M-R ребер из N-R возможных ребер и графу, полученному объединением этих ребер с К(г,гй и, возможно, с оставшимися изолированными вершинами припишем вероятность

Таким образом, во всех графах ("реализациях^ случайного графа 6Сп,М,г) присутствует "неслучайный" полносвязный подграф из г вершин.

Теорема 3.1

Пусть случайные графы (GCn,M,г}} таковы, что г>3/е+1 и, начиная с некоторого п, выполнено неравенство CM-PJ/CN-PJ < п~е, где е>0.

Тогда почти во всех графах {GCn,M,rD} подграф КСг,гО является максимальной кликой и почти во всех графах (6Сп,М,гУ} максимальная клика КО,а) может быть найдена за время алгоритмом А£ф, где а- Г1 /е~\+1._

¿О Харари Ф. Теория графов. - И.: Мир, 1973.

На практике параметр q определяется по исследуемому графу g(n,M) по формуле q=logii/pfnSp), где р-заданная вероятность ошибки.

Теорема 3. 2.

Пусть для случайных графов {GCri,M,r}} начиная с некоторого п выполнено г>Ьп и где 0<Ь<1 и а<1.

Тогда почти во всех графах {GCn,M,r)} КСг,гО является

максимальной кликой, которая может быть найдена почти во всех

2Hog СЮ+е

{GCn,M,r)) с помощью алгоритма А^СЬ,е) за время ОСп где е произвольное положительное число.

Оба алгоритма сконструированы для доказательства оценок и на практике могут быть существенно улучшены.

По теме диссертации опубликованы следующие работы

1. Дорофеева М. П. , Овсянкин Б. П. , Смирнов A.B., Шпенев В. И. , Автоматизация разработки управляющих программ для АСУ ТП. - В сб. Разработка и внедрение автоматизированных систем управления и средств автоматизации в нефтяной и газовой промышленности. - Киев, изд. Киевского института автоматики им. ХХУ съезда КПСС, 1933, с. 42-44.

2. Дорофеева М. П., Овсянкин Б. П. , Смирнов А. В. О многопроцессорных расписаниях с директивными сроками. -ДАН АрмССР, 1984, т.78, N4, с. 147-150.

3. Дорофеева М. П., Смирнов A.B., Шпенев В.М. Распределение задач в микропроцессорных системах. - В сб. Автоматизированные системы управления и средства автоматизации в нефтяной промышленности. - Киев, изд. Киевского института автоматики им. ХХУ съезда КПСС, 1988, с. 18-20.

4. Дорофеева М. П., Смирнов A.B., Шпенев В.М. Распределение ресурсов в микропроцессорных системах телемеханики. - Приборы и системы управления, 1988, N8, с.10-12.

5. Смирнов А. В. О сложности алгоритмов поиска максимальной клики в больших графах. - В сб. Алгоритмические и комбинаторные вопросы дискретных методов и ЭВМ, Иркутск, изд. ИГУ, 1990, с.65-67.

6. Смирнов А. В. О задаче упаковки в контейнеры. - Успехи математических наук, i9pi, т. 46, вып. 4, с. 173-174.